nsz Git - libfirm/blob - ir/opt/opt_blocks.c

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief   Combining congruent blocks
  23  * @author  Michael Beck
  24  * @version $Id$
  25  *
  26  * This phase find congruent blocks. Works currently for
  27  * predecessors of the end block only.
  28  * Two block are congruent, if they contains only equal calculations.
  29  */
  30 #include "config.h"
  31 #include "irgraph_t.h"
  32 #include "irnode_t.h"
  33 #include "iropt_t.h"
  34 #include "set.h"
  35 #include "debug.h"
  36
  37 typedef struct partition_t     partition_t;
  38 typedef struct block_t         block_t;
  39 typedef struct node_t          node_t;
  40 typedef struct opcode_key_t    opcode_key_t;
  41 typedef struct listmap_entry_t listmap_entry_t;
  42 typedef struct environment_t   environment_t;
  43
  44 /** An opcode map key. */
  45 struct opcode_key_t {
  46         ir_opcode   code;   /**< The Firm opcode. */
  47         ir_mode     *mode;  /**< The mode of all nodes in the partition. */
  48         int         arity;  /**< The arity of this opcode (needed for Phi etc. */
  49         union {
  50                 long      proj;   /**< For Proj nodes, its proj number */
  51                 ir_entity *ent;   /**< For Sel Nodes, its entity */
  52         } u;
  53 };
  54
  55 /** A partition contains all congruent blocks. */
  56 struct partition_t {
  57         list_head part_list;     /**< Double linked list of partitions. */
  58         list_head blocks;        /**< List of blocks in this partition. */
  59         unsigned  n_blocks;      /**< Number of block in this partition. */
  60 #ifdef DEBUG_libfirm
  61         unsigned  nr;            /**< For debugging: number of this partition. */
  62 #endif
  63 };
  64
  65 /** A block. */
  66 struct block_t {
  67         list_head  block_list;   /**< Double linked list of block inside a partition. */
  68         list_head  nodes;        /**< Wait-queue of nodes that must be checked for congruence. */
  69         block_t    *next;        /**< Next block of a split list. */
  70         ir_node    *block;       /**< Pointer to the associated IR-node block. */
  71         node_t     **roots;      /**< The array of the root nodes. */
  72 };
  73
  74 /** A node. */
  75 struct node_t {
  76         list_head  node_list;    /**< Double linked list of block inside a partition. */
  77         ir_node    *node;        /**< Pointer to the associated IR-node or NULL for block inputs. */
  78         char       is_input;     /**< Set if this node is an input from other block. */
  79 };
  80
  81 /** The environment. */
  82 typedef struct environment_t {
  83         list_head       partitions;     /**< list of partitions. */
  84         list_head       ready;          /**< list of ready partitions. */
  85         set             *opcode2id_map; /**< The opcodeMode->id map. */
  86         struct obstack  obst;           /** obstack for temporary data */
  87 };
  88
  89 /**
  90  * An entry in the list_map.
  91  */
  92 struct listmap_entry_t {
  93         void            *id;    /**< The id. */
  94         block_t         *list;  /**< The associated list for this id. */
  95         listmap_entry_t *next;  /**< Link to the next entry in the map. */
  96 };
  97
  98 /** We must map id's to lists. */
  99 typedef struct listmap_t {
 100         set             *map;    /**< Map id's to listmap_entry_t's */
 101         listmap_entry_t *values; /**< List of all values in the map. */
 102 } listmap_t;
 103
 104 #define get_irn_node(irn)         ((node_t *)get_irn_link(irn))
 105 #define set_irn_node(irn, node)   set_irn_link(irn, node)
 106 #define get_irn_block(irn)        ((block_t *)get_irn_link(irn))
 107 #define set_irn_block(irn, block) set_irn_link(irn, block)
 108
 109 /** The debug module handle. */
 110 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
 111
 112 /** Next partition number. */
 113 DEBUG_ONLY(static unsigned part_nr = 0);
 114
 115 #ifdef DEBUG_libfirm
 116 /**
 117  * Dump partition to output.
 118  */
 119 static void dump_partition(const char *msg, const partition_t *part) {
 120         const block_t *block;
 121         int           first = 1;
 122
 123         DB((dbg, LEVEL_2, "%s part%u (%u) {\n  ", msg, part->nr, part->n_blocks));
 124         list_for_each_entry(block_t, block, &part->blocks, block_list) {
 125                 DB((dbg, LEVEL_2, "%s%+F", first ? "" : ", ", block->block));
 126                 first = 0;
 127         }
 128         DB((dbg, LEVEL_2, "\n}\n"));
 129 }  /* dump_partition */
 130
 131 /**
 132  * Dumps a list.
 133  */
 134 static void dump_list(const char *msg, const block_t *block) {
 135         const block_t *p;
 136         int           first = 1;
 137
 138         DB((dbg, LEVEL_3, "%s = {\n  ", msg));
 139         for (p = block; p != NULL; p = p->next) {
 140                 DB((dbg, LEVEL_3, "%s%+F", first ? "" : ", ", p->block));
 141                 first = 0;
 142         }
 143         DB((dbg, LEVEL_3, "\n}\n"));
 144 }  /* do_dump_list */
 145 #else
 146 #define dump_partition(msg, part)
 147 #define dump_list(msg, block)
 148 #endif
 149
 150 /**
 151  * Compare two pointer values of a listmap.
 152  */
 153 static int listmap_cmp_ptr(const void *elt, const void *key, size_t size) {
 154         const listmap_entry_t *e1 = elt;
 155         const listmap_entry_t *e2 = key;
 156
 157         (void) size;
 158         return e1->id != e2->id;
 159 }  /* listmap_cmp_ptr */
 160
 161 /**
 162  * Initializes a listmap.
 163  *
 164  * @param map  the listmap
 165  */
 166 static void listmap_init(listmap_t *map) {
 167         map->map    = new_set(listmap_cmp_ptr, 16);
 168         map->values = NULL;
 169 }  /* listmap_init */
 170
 171 /**
 172  * Terminates a listmap.
 173  *
 174  * @param map  the listmap
 175  */
 176 static void listmap_term(listmap_t *map) {
 177         del_set(map->map);
 178 }  /* listmap_term */
 179
 180 /**
 181  * Return the associated listmap entry for a given id.
 182  *
 183  * @param map  the listmap
 184  * @param id   the id to search for
 185  *
 186  * @return the associated listmap entry for the given id
 187  */
 188 static listmap_entry_t *listmap_find(listmap_t *map, void *id) {
 189         listmap_entry_t key, *entry;
 190
 191         key.id   = id;
 192         key.list = NULL;
 193         key.next = NULL;
 194         entry = set_insert(map->map, &key, sizeof(key), HASH_PTR(id));
 195
 196         if (entry->list == NULL) {
 197                 /* a new entry, put into the list */
 198                 entry->next = map->values;
 199                 map->values = entry;
 200         }
 201         return entry;
 202 }  /* listmap_find */
 203
 204 /**
 205  * Calculate the hash value for an opcode map entry.
 206  *
 207  * @param entry  an opcode map entry
 208  *
 209  * @return a hash value for the given opcode map entry
 210  */
 211 static unsigned opcode_hash(const opcode_key_t *entry) {
 212         return (entry->mode - (ir_mode *)0) * 9 + entry->code + entry->u.proj * 3 + HASH_PTR(entry->u.ent) + entry->arity;
 213 }  /* opcode_hash */
 214
 215 /**
 216  * Compare two entries in the opcode map.
 217  */
 218 static int cmp_opcode(const void *elt, const void *key, size_t size) {
 219         const opcode_key_t *o1 = elt;
 220         const opcode_key_t *o2 = key;
 221
 222         (void) size;
 223         return o1->code != o2->code || o1->mode != o2->mode ||
 224                o1->arity != o2->arity ||
 225                o1->u.proj != o2->u.proj || o1->u.ent != o2->u.ent;
 226 }  /* cmp_opcode */
 227
 228 /**
 229  * Creates a new empty partition.
 230  */
 231 static partition_t *create_partition(environment_t *env) {
 232         partition_t *part = obstack_alloc(&env->obst, sizeof(*part));
 233
 234         INIT_LIST_HEAD(&part->blocks);
 235         part->n_blocks = 0;
 236         DEBUG_ONLY(part->nr = part_nr++);
 237         list_add_tail(&part->part_list, &env->partitions);
 238         return part;
 239 }  /* create_partition */
 240
 241 /**
 242  * Allocate a new block.
 243  *
 244  * @param block  the IR-node
 245  * @param env    the environment
 246  */
 247 static block_t *create_block(ir_node *block, environment_t *env) {
 248         block_t *bl = obstack_alloc(&env->obst, sizeof(*bl));
 249
 250         INIT_LIST_HEAD(&bl->nodes);
 251         bl->next  = NULL;
 252         bl->block = block;
 253         bl->roots = NULL;
 254         set_irn_block(block, bl);
 255         return bl;
 256 }  /* create_block */
 257
 258 /**
 259  * Adds a block to a partition.
 260  *
 261  * @param partition  the partition to add to
 262  * @param block      the block to add
 263  */
 264 static void add_block(partition_t *partition, block_t *block) {
 265         list_add_tail(&block->block_list, &partition->blocks);
 266         ++partition->n_blocks;
 267 }  /* add_block */
 268
 269 /**
 270  * Allocate a new node.
 271  *
 272  * @param irn    the IR-node
 273  * @param env    the environment
 274  */
 275 static node_t *create_node(ir_node *irn, environment_t *env) {
 276         node_t *node = obstack_alloc(&env->obst, sizeof(*node));
 277
 278         node->node     = irn;
 279         node->is_input = 0;
 280         return node;
 281 }  /* create_node */
 282
 283 /**
 284  * Adds a node to a block wait queue.
 285  *
 286  * @param block  the block to add to
 287  * @param node   the node to add
 288  */
 289 static void add_node(block_t *block, node_t *node) {
 290         list_add_tail(&node->node_list, &block->nodes);
 291 }  /* add_node */
 292
 293 /** creates an opcode */
 294 static opcode_key_t *opcode(const node_t *node, environment_t *env) {
 295         opcode_key_t key, *entry;
 296         ir_node      *irn = node->node;
 297
 298         if (node->is_input) {
 299                 /* Node: as Block nodes are never propagated, it is safe to
 300                    use its code for "input" node */
 301                 key.code   = iro_Block;
 302                 key.arity  = 0;
 303         } else {
 304                 key.code   = get_irn_opcode(irn);
 305                 key.arity  = get_irn_arity(irn);
 306         }
 307         key.mode   = get_irn_mode(node->node);
 308         key.u.proj = 0;
 309         key.u.ent  = NULL;
 310
 311         switch (key.code) {
 312         case iro_Proj:
 313                 key.u.proj = get_Proj_proj(irn);
 314                 break;
 315         case iro_Sel:
 316                 key.u.ent = get_Sel_entity(irn);
 317                 break;
 318         default:
 319                 break;
 320         }
 321
 322         entry = set_insert(env->opcode2id_map, &key, sizeof(key), opcode_hash(&key));
 323         return entry;
 324 }  /* opcode */
 325
 326 /**
 327  * Split a partition by a local list.
 328  *
 329  * @param Z    partition to split
 330  * @param g    a (non-empty) block list
 331  * @param env  the environment
 332  *
 333  * @return  a new partition containing the nodes of g
 334  */
 335 static partition_t *split(partition_t *Z, block_t *g, environment_t *env) {
 336         partition_t *Z_prime;
 337         block_t     *block;
 338         unsigned    n = 0;
 339
 340         dump_partition("Splitting ", Z);
 341         dump_list("by list ", g);
 342
 343         assert(g != NULL);
 344
 345         /* Remove g from Z. */
 346         for (block = g; block != NULL; block = block->next) {
 347                 list_del(&block->block_list);
 348                 ++n;
 349         }
 350         assert(n < Z->n_blocks);
 351         Z->n_blocks -= n;
 352
 353         /* Move g to a new partition, Z'. */
 354         Z_prime = create_partition(env);
 355         for (block = g; block != NULL; block = block->next) {
 356                 list_add_tail(&block->block_list, &Z_prime->blocks);
 357         }
 358         Z_prime->n_blocks = n;
 359
 360         dump_partition("Now ", Z);
 361         dump_partition("Created new ", Z_prime);
 362         return Z_prime;
 363 }  /* split */
 364
 365 /**
 366  * Propagate nodes on all wait queues of the given partition.
 367  *
 368  * @param part  the partition
 369  * @param env    the environment
 370  */
 371 void propagate_blocks(partition_t *part, environment_t *env) {
 372         block_t         *ready_blocks = NULL;
 373         unsigned        n_ready       = 0;
 374         block_t         *bl, *next;
 375         listmap_t       map;
 376         listmap_entry_t *iter;
 377
 378         DB((dbg, LEVEL_2, "Propagate blocks on part%u\n", part->nr));
 379
 380         /* Let map be an empty mapping from the range of Opcodes to (local) list of Nodes. */
 381         listmap_init(&map);
 382         list_for_each_entry_safe(block_t, bl, next, &part->blocks, block_list) {
 383                 opcode_key_t    *id;
 384                 listmap_entry_t *entry;
 385                 node_t          *node;
 386
 387                 if (list_empty(&bl->nodes)) {
 388                         bl->next     = ready_blocks;
 389                         ready_blocks = bl;
 390                         ++n_ready;
 391                         DB((dbg, LEVEL_1, "Block %+F ready\n", bl->block));
 392                         continue;
 393                 }
 394
 395                 /* get the first node from the wait queue */
 396                 node = list_entry(bl->nodes.next, node_t, node_list);
 397                 list_del(&node->node_list);
 398
 399                 /* put all not-visited predecessors to the wait queue */
 400                 if (! node->is_input) {
 401                         ir_node *irn = node->node;
 402                         int     i;
 403
 404                         DB((dbg, LEVEL_3, "  propagate %+F\n", node->node));
 405                         ir_normalize_node(node->node);
 406                         for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
 407                                 ir_node *pred  = get_irn_n(irn, i);
 408                                 ir_node *block = get_nodes_block(skip_Proj(pred));
 409                                 node_t *p_node;
 410
 411                                 if (block != bl->block) {
 412                                         p_node = create_node(pred, env);
 413                                         p_node->is_input = 1;
 414                                         add_node(bl, p_node);
 415                                 } else if (! irn_visited_else_mark(pred)) {
 416                                         /* not yet visited, ok */
 417                                         p_node = create_node(pred, env);
 418                                         set_irn_node(pred, p_node);
 419                                         add_node(bl, p_node);
 420                                 }
 421                         }
 422                 } else {
 423                         DB((dbg, LEVEL_3, "  propagate Input %+F\n", node->node));
 424                 }
 425
 426                 /* Add bl to map[opcode(bl)]. */
 427                 id          = opcode(node, env);
 428                 entry       = listmap_find(&map, id);
 429                 bl->next    = entry->list;
 430                 entry->list = bl;
 431         }
 432
 433         /* split out ready blocks */
 434         if (n_ready > 0) {
 435                 partition_t *Z;
 436
 437                 if (n_ready < part->n_blocks)
 438                         Z = split(part, ready_blocks, env);
 439                 else
 440                         Z = part;
 441                 list_del(&Z->part_list);
 442
 443                 if (Z->n_blocks > 1) {
 444                         DB((dbg, LEVEL_1, "Partition %u is ready\n", Z->nr));
 445                         list_add(&Z->part_list, &env->ready);
 446                 } else {
 447                         DB((dbg, LEVEL_1, "Partition %u contains only one block, killed\n", Z->nr));
 448                 }
 449         }
 450
 451         /* for all sets S except one in the range of map do */
 452         for (iter = map.values; iter != NULL; iter = iter->next) {
 453                 block_t *S;
 454
 455                 if (iter->next == NULL) {
 456                         /* this is the last entry, ignore */
 457                         break;
 458                 }
 459                 S = iter->list;
 460
 461                 /* Add SPLIT( X, S ) to P. */
 462                 split(part, S, env);
 463         }
 464         listmap_term(&map);
 465 }  /* propagate_blocks */
 466
 467 /**
 468  * Propagate nodes on all wait queues.
 469  *
 470  * @param env    the environment
 471  */
 472 void propagate(environment_t *env) {
 473         partition_t *part, *next;
 474
 475         list_for_each_entry_safe(partition_t, part, next, &env->partitions, part_list) {
 476                 if (part->n_blocks == 1) {
 477                         /* only one block left, move to ready */
 478                         list_del(&part->part_list);
 479                         DB((dbg, LEVEL_1, "Partition %u contains only one block, killed\n", part->nr));
 480                 } else
 481                         propagate_blocks(part, env);
 482         }
 483 }  /* propagate */
 484
 485 void melt_end_blocks(ir_graph *irg) {
 486         ir_graph      *rem;
 487         ir_node       *end;
 488         environment_t env;
 489         partition_t   *part;
 490         int           i;
 491
 492         rem = current_ir_graph;
 493         current_ir_graph = irg;
 494
 495         /* register a debug mask */
 496         FIRM_DBG_REGISTER(dbg, "firm.opt.blocks");
 497         firm_dbg_set_mask(dbg, SET_LEVEL_3);
 498
 499         DB((dbg, LEVEL_1, "Melting end blocks for %+F\n", irg));
 500
 501         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_IRN_VISITED);
 502         inc_irg_visited(irg);
 503
 504         obstack_init(&env.obst);
 505         INIT_LIST_HEAD(&env.partitions);
 506         INIT_LIST_HEAD(&env.ready);
 507         env.opcode2id_map  = new_set(cmp_opcode, iro_Last * 4);
 508
 509         part = create_partition(&env);
 510
 511         /* collect all no-return blocks */
 512         end = get_irg_end(irg);
 513         for (i = get_End_n_keepalives(end) - 1; i >= 0; --i) {
 514                 ir_node *ka    = get_End_keepalive(end, i);
 515                 ir_node *block;
 516                 block_t *bl;
 517                 node_t  *node;
 518
 519                 if (! is_Call(ka))
 520                         continue;
 521                 mark_irn_visited(ka);
 522
 523                 /* found one */
 524                 block = get_nodes_block(ka);
 525                 bl    = create_block(block, &env);
 526                 add_block(part, bl);
 527                 node  = create_node(ka, &env);
 528                 add_node(bl, node);
 529
 530                 /* currently we support only one root */
 531                 bl->roots = NEW_ARR_D(node_t*, &env.obst, 1);
 532                 bl->roots[0] = node;
 533         }
 534
 535         /* collect normal blocks */
 536         end = get_irg_end_block(irg);
 537         for (i = get_Block_n_cfgpreds(end) - 1; i >= 0; --i) {
 538                 ir_node *pred = get_Block_cfgpred(end, i);
 539                 ir_node *block;
 540                 block_t *bl;
 541                 node_t  *node;
 542
 543                 mark_irn_visited(pred);
 544
 545                 block = get_nodes_block(pred);
 546                 bl    = create_block(block, &env);
 547                 add_block(part, bl);
 548                 node  = create_node(pred, &env);
 549                 add_node(bl, node);
 550
 551                 /* currently we support only one root */
 552                 bl->roots = NEW_ARR_D(node_t*, &env.obst, 1);
 553                 bl->roots[0] = node;
 554         }
 555
 556         while (! list_empty(&env.partitions))
 557                 propagate(&env);
 558
 559         list_for_each_entry(partition_t, part, &env.ready, part_list) {
 560                 dump_partition("Ready Partition", part);
 561         }
 562         ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_IRN_VISITED);
 563         del_set(env.opcode2id_map);
 564         obstack_free(&env.obst, NULL);
 565         current_ir_graph = rem;
 566 }  /* melt_end_blocks */