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 "ircons.h"
  32 #include "iroptimize.h"
  33 #include "irgmod.h"
  34 #include "irgraph_t.h"
  35 #include "irnode_t.h"
  36 #include "iropt_t.h"
  37 #include "array_t.h"
  38 #include "trouts.h"
  39 #include "irgwalk.h"
  40 #include "set.h"
  41 #include "debug.h"
  42
  43 /* define this for gneral block shaping (buggy yet) */
  44 #undef GENERAL_SHAPE
  45
  46 typedef struct partition_t     partition_t;
  47 typedef struct block_t         block_t;
  48 typedef struct node_t          node_t;
  49 typedef struct pair_t          pair_t;
  50 typedef struct phi_t           phi_t;
  51 typedef struct opcode_key_t    opcode_key_t;
  52 typedef struct listmap_entry_t listmap_entry_t;
  53 typedef struct environment_t   environment_t;
  54
  55 /** An opcode map key. */
  56 struct opcode_key_t {
  57         ir_opcode   code;   /**< The Firm opcode. */
  58         ir_mode     *mode;  /**< The mode of all nodes in the partition. */
  59         int         arity;  /**< The arity of this opcode (needed for Phi etc. */
  60         union {
  61                 long      proj;   /**< For Proj nodes, its proj number */
  62                 ir_entity *ent;   /**< For Sel Nodes, its entity */
  63         } u;
  64 };
  65
  66 /** A partition contains all congruent blocks. */
  67 struct partition_t {
  68         list_head part_list;     /**< Double linked list of partitions. */
  69         list_head blocks;        /**< List of blocks in this partition. */
  70         unsigned  n_blocks;      /**< Number of block in this partition. */
  71         ir_node   *meet_block;   /**< The control flow meet block of this partition. */
  72 #ifdef DEBUG_libfirm
  73         unsigned  nr;            /**< For debugging: number of this partition. */
  74 #endif
  75 };
  76
  77 /** A block. */
  78 struct block_t {
  79         list_head  block_list;   /**< Double linked list of block inside a partition. */
  80         list_head  nodes;        /**< Wait-queue of nodes that must be checked for congruence. */
  81         block_t    *next;        /**< Next block of a split list. */
  82         ir_node    *block;       /**< Pointer to the associated IR-node block. */
  83         ir_node    **roots;      /**< An array of all root nodes. */
  84         node_t     *cf_root;     /**< The control flow root node of this block. */
  85         pair_t     *input_pairs; /**< The list of inputs to this block. */
  86         phi_t      *phis;        /**< The list of Phis in this block. */
  87         block_t    *all_next;    /**< links all craeted blocks. */
  88 };
  89
  90 /** A node. */
  91 struct node_t {
  92         list_head  node_list;    /**< Double linked list of block inside a partition. */
  93         ir_node    *node;        /**< Pointer to the associated IR-node or NULL for block inputs. */
  94         char       is_input;     /**< Set if this node is an input from other block. */
  95 };
  96
  97 /** The environment. */
  98 struct environment_t {
  99         list_head       partitions;     /**< list of partitions. */
 100         list_head       ready;          /**< list of ready partitions. */
 101         set             *opcode2id_map; /**< The opcodeMode->id map. */
 102         ir_node         **live_outs;    /**< Live out only nodes. */
 103         block_t         *all_blocks;    /**< List of all created blocks. */
 104         struct obstack  obst;           /** obstack for temporary data */
 105 };
 106
 107 /** A node, input index pair. */
 108 struct pair_t {
 109         pair_t  *next;    /**< Points to the next pair entry. */
 110         ir_node *irn;     /**< The IR-node. */
 111         int     index;    /**< An input index. */
 112         ir_node **ins;    /**< A new in array once allocated. */
 113 };
 114
 115 /** A Phi, inputs pair. */
 116 struct phi_t {
 117         phi_t   *next;    /**< Points to the next Phi pair entry. */
 118         ir_node *phi;     /**< The Phi node. */
 119         ir_node **ins;    /**< A new in array once allocated. */
 120 };
 121
 122 /**
 123  * An entry in the list_map.
 124  */
 125 struct listmap_entry_t {
 126         void            *id;    /**< The id. */
 127         block_t         *list;  /**< The associated list for this id. */
 128         listmap_entry_t *next;  /**< Link to the next entry in the map. */
 129 };
 130
 131 /** We must map id's to lists. */
 132 typedef struct listmap_t {
 133         set             *map;    /**< Map id's to listmap_entry_t's */
 134         listmap_entry_t *values; /**< List of all values in the map. */
 135 } listmap_t;
 136
 137 #define get_Block_entry(block)  ((block_t *)get_irn_link(block))
 138
 139 /** The debug module handle. */
 140 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
 141
 142 /** Next partition number. */
 143 DEBUG_ONLY(static unsigned part_nr = 0);
 144
 145 #ifdef DEBUG_libfirm
 146 /**
 147  * Dump partition to output.
 148  */
 149 static void dump_partition(const char *msg, const partition_t *part) {
 150         const block_t *block;
 151         int           first = 1;
 152
 153         DB((dbg, LEVEL_2, " %s part%u (%u blocks) {\n  ", msg, part->nr, part->n_blocks));
 154         list_for_each_entry(block_t, block, &part->blocks, block_list) {
 155                 DB((dbg, LEVEL_2, "%s%+F", first ? "" : ", ", block->block));
 156                 first = 0;
 157         }
 158         DB((dbg, LEVEL_2, "\n }\n"));
 159 }  /* dump_partition */
 160
 161 /**
 162  * Dumps a list.
 163  */
 164 static void dump_list(const char *msg, const block_t *block) {
 165         const block_t *p;
 166         int           first = 1;
 167
 168         DB((dbg, LEVEL_3, "  %s = {\n   ", msg));
 169         for (p = block; p != NULL; p = p->next) {
 170                 DB((dbg, LEVEL_3, "%s%+F", first ? "" : ", ", p->block));
 171                 first = 0;
 172         }
 173         DB((dbg, LEVEL_3, "\n  }\n"));
 174 }  /* do_dump_list */
 175 #else
 176 #define dump_partition(msg, part)
 177 #define dump_list(msg, block)
 178 #endif
 179
 180 /**
 181  * Compare two pointer values of a listmap.
 182  */
 183 static int listmap_cmp_ptr(const void *elt, const void *key, size_t size) {
 184         const listmap_entry_t *e1 = elt;
 185         const listmap_entry_t *e2 = key;
 186
 187         (void) size;
 188         return e1->id != e2->id;
 189 }  /* listmap_cmp_ptr */
 190
 191 /**
 192  * Initializes a listmap.
 193  *
 194  * @param map  the listmap
 195  */
 196 static void listmap_init(listmap_t *map) {
 197         map->map    = new_set(listmap_cmp_ptr, 16);
 198         map->values = NULL;
 199 }  /* listmap_init */
 200
 201 /**
 202  * Terminates a listmap.
 203  *
 204  * @param map  the listmap
 205  */
 206 static void listmap_term(listmap_t *map) {
 207         del_set(map->map);
 208 }  /* listmap_term */
 209
 210 /**
 211  * Return the associated listmap entry for a given id.
 212  *
 213  * @param map  the listmap
 214  * @param id   the id to search for
 215  *
 216  * @return the associated listmap entry for the given id
 217  */
 218 static listmap_entry_t *listmap_find(listmap_t *map, void *id) {
 219         listmap_entry_t key, *entry;
 220
 221         key.id   = id;
 222         key.list = NULL;
 223         key.next = NULL;
 224         entry = set_insert(map->map, &key, sizeof(key), HASH_PTR(id));
 225
 226         if (entry->list == NULL) {
 227                 /* a new entry, put into the list */
 228                 entry->next = map->values;
 229                 map->values = entry;
 230         }
 231         return entry;
 232 }  /* listmap_find */
 233
 234 /**
 235  * Calculate the hash value for an opcode map entry.
 236  *
 237  * @param entry  an opcode map entry
 238  *
 239  * @return a hash value for the given opcode map entry
 240  */
 241 static unsigned opcode_hash(const opcode_key_t *entry) {
 242         return (entry->mode - (ir_mode *)0) * 9 + entry->code + entry->u.proj * 3 + HASH_PTR(entry->u.ent) + entry->arity;
 243 }  /* opcode_hash */
 244
 245 /**
 246  * Compare two entries in the opcode map.
 247  */
 248 static int cmp_opcode(const void *elt, const void *key, size_t size) {
 249         const opcode_key_t *o1 = elt;
 250         const opcode_key_t *o2 = key;
 251
 252         (void) size;
 253         return o1->code != o2->code || o1->mode != o2->mode ||
 254                o1->arity != o2->arity ||
 255                o1->u.proj != o2->u.proj || o1->u.ent != o2->u.ent;
 256 }  /* cmp_opcode */
 257
 258 /**
 259  * Creates a new empty partition and put in on the
 260  * partitions list.
 261  *
 262  * @param meet_block  the control flow meet block of thi partition
 263  * @param env         the environment
 264  */
 265 static partition_t *create_partition(ir_node *meet_block, environment_t *env) {
 266         partition_t *part = obstack_alloc(&env->obst, sizeof(*part));
 267
 268         INIT_LIST_HEAD(&part->blocks);
 269         part->meet_block = meet_block;
 270         part->n_blocks   = 0;
 271         DEBUG_ONLY(part->nr = part_nr++);
 272         list_add_tail(&part->part_list, &env->partitions);
 273         return part;
 274 }  /* create_partition */
 275
 276 /**
 277  * Allocate a new block in the given partition.
 278  *
 279  * @param block      the IR-node
 280  * @param partition  the partition to add to
 281  * @param env        the environment
 282  */
 283 static block_t *create_block(ir_node *block, partition_t *partition, environment_t *env) {
 284         block_t *bl = obstack_alloc(&env->obst, sizeof(*bl));
 285
 286         set_irn_link(block, bl);
 287
 288         INIT_LIST_HEAD(&bl->nodes);
 289         bl->next        = NULL;
 290         bl->block       = block;
 291         bl->roots       = NEW_ARR_F(ir_node *, 0);
 292         bl->cf_root     = NULL;
 293         bl->input_pairs = NULL;
 294         bl->phis        = NULL;
 295
 296         /* put it into the list of partition blocks */
 297         list_add_tail(&bl->block_list, &partition->blocks);
 298         ++partition->n_blocks;
 299
 300         /* put in into the list of all blocks */
 301         bl->all_next    = env->all_blocks;
 302         env->all_blocks = bl;
 303
 304         return bl;
 305 }  /* create_block */
 306
 307 /**
 308  * Allocate a new node and add it to a blocks wait queue.
 309  *
 310  * @param irn    the IR-node
 311  * @param block  the block to add to
 312  * @param env    the environment
 313  */
 314 static node_t *create_node(ir_node *irn, block_t *block, environment_t *env) {
 315         node_t *node = obstack_alloc(&env->obst, sizeof(*node));
 316
 317         node->node     = irn;
 318         node->is_input = 0;
 319
 320         list_add_tail(&node->node_list, &block->nodes);
 321
 322         return node;
 323 }  /* create_node */
 324
 325 /**
 326  * Add an input pair to a block.
 327  *
 328  * @param block  the block
 329  * @param irn    the IR-node that has an block input
 330  * @param idx    the index of the block input in node's predecessors
 331  * @param env    the environment
 332  */
 333 static void add_pair(block_t *block, ir_node *irn, int idx, environment_t *env) {
 334         pair_t *pair = obstack_alloc(&env->obst, sizeof(*pair));
 335
 336         pair->next  = block->input_pairs;
 337         pair->irn   = irn;
 338         pair->index = idx;
 339         pair->ins   = NULL;
 340
 341         block->input_pairs = pair;
 342 }  /* add_pair */
 343
 344 /**
 345  * Add a Phi to a block.
 346  *
 347  * @param block  the block
 348  * @param phi    the Phi node
 349  * @param env    the environment
 350  */
 351 static void add_phi(block_t *block, ir_node *phi, environment_t *env) {
 352         phi_t *node = obstack_alloc(&env->obst, sizeof(*node));
 353
 354         node->next = block->phis;
 355         node->phi  = phi;
 356         node->ins  = NULL;
 357
 358         block->phis = node;
 359 }  /** add_phi */
 360
 361 /**
 362  * Creates an opcode from a node.
 363  */
 364 static opcode_key_t *opcode(const node_t *node, environment_t *env) {
 365         opcode_key_t key, *entry;
 366         ir_node      *irn = node->node;
 367
 368         if (node->is_input) {
 369                 /* Node: as Block nodes are never propagated, it is safe to
 370                    use its code for "input" node */
 371                 key.code   = iro_Block;
 372                 key.arity  = 0;
 373         } else {
 374                 key.code   = get_irn_opcode(irn);
 375                 key.arity  = get_irn_arity(irn);
 376         }
 377         key.mode   = get_irn_mode(node->node);
 378         key.u.proj = 0;
 379         key.u.ent  = NULL;
 380
 381         switch (key.code) {
 382         case iro_Proj:
 383                 key.u.proj = get_Proj_proj(irn);
 384                 break;
 385         case iro_Sel:
 386                 key.u.ent = get_Sel_entity(irn);
 387                 break;
 388         default:
 389                 break;
 390         }
 391
 392         entry = set_insert(env->opcode2id_map, &key, sizeof(key), opcode_hash(&key));
 393         return entry;
 394 }  /* opcode */
 395
 396 /**
 397  * Split a partition by a local list.
 398  *
 399  * @param Z    partition to split
 400  * @param g    a (non-empty) block list
 401  * @param env  the environment
 402  *
 403  * @return  a new partition containing the nodes of g
 404  */
 405 static partition_t *split(partition_t *Z, block_t *g, environment_t *env) {
 406         partition_t *Z_prime;
 407         block_t     *block;
 408         unsigned    n = 0;
 409
 410         dump_partition("Splitting ", Z);
 411         dump_list("by list ", g);
 412
 413         assert(g != NULL);
 414
 415         /* Remove g from Z. */
 416         for (block = g; block != NULL; block = block->next) {
 417                 list_del(&block->block_list);
 418                 ++n;
 419         }
 420         assert(n < Z->n_blocks);
 421         Z->n_blocks -= n;
 422
 423         /* Move g to a new partition, Z'. */
 424         Z_prime = create_partition(Z->meet_block, env);
 425         for (block = g; block != NULL; block = block->next) {
 426                 list_add_tail(&block->block_list, &Z_prime->blocks);
 427         }
 428         Z_prime->n_blocks = n;
 429
 430         dump_partition("Now ", Z);
 431         dump_partition("Created new ", Z_prime);
 432         return Z_prime;
 433 }  /* split */
 434
 435 /**
 436  * Propagate nodes on all wait queues of the given partition.
 437  *
 438  * @param part  the partition
 439  * @param env    the environment
 440  */
 441 void propagate_blocks(partition_t *part, environment_t *env) {
 442         block_t         *ready_blocks = NULL;
 443         unsigned        n_ready       = 0;
 444         block_t         *bl, *next;
 445         listmap_t       map;
 446         listmap_entry_t *iter;
 447
 448         DB((dbg, LEVEL_2, " Propagate blocks on part%u\n", part->nr));
 449
 450         /* Let map be an empty mapping from the range of Opcodes to (local) list of Nodes. */
 451         listmap_init(&map);
 452         list_for_each_entry_safe(block_t, bl, next, &part->blocks, block_list) {
 453                 opcode_key_t    *id;
 454                 listmap_entry_t *entry;
 455                 node_t          *node;
 456
 457                 if (list_empty(&bl->nodes)) {
 458                         bl->next     = ready_blocks;
 459                         ready_blocks = bl;
 460                         ++n_ready;
 461                         DB((dbg, LEVEL_2, " Block %+F completely processed\n", bl->block));
 462                         continue;
 463                 }
 464
 465                 /* get the first node from the wait queue */
 466                 node = list_entry(bl->nodes.next, node_t, node_list);
 467                 list_del(&node->node_list);
 468
 469                 /* put all not-visited predecessors to the wait queue */
 470                 if (! node->is_input) {
 471                         ir_node *irn = node->node;
 472                         int     i;
 473
 474                         DB((dbg, LEVEL_3, "  propagate %+F\n", irn));
 475                         ir_normalize_node(node->node);
 476                         for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
 477                                 ir_node *pred  = get_irn_n(irn, i);
 478                                 ir_node *block = get_nodes_block(skip_Proj(pred));
 479                                 node_t *p_node;
 480
 481                                 if (block != bl->block) {
 482                                         p_node = create_node(pred, bl, env);
 483                                         /* do not threat Constants like live-ins */
 484                                         if (! is_irn_constlike(pred)) {
 485                                                 p_node->is_input = 1;
 486                                                 if (! is_Phi(irn))
 487                                                         add_pair(bl, irn, i, env);
 488                                         }
 489                                 } else if (! irn_visited_else_mark(pred)) {
 490                                         /* not yet visited, ok */
 491                                         p_node = create_node(pred, bl, env);
 492
 493                                         if (is_Phi(pred)) {
 494                                                 /* update the Phi list */
 495                                                 add_phi(bl, pred, env);
 496                                         }
 497                                 }
 498                         }
 499                 } else {
 500                         DB((dbg, LEVEL_3, "  propagate Input %+F\n", node->node));
 501                 }
 502
 503                 /* Add bl to map[opcode(bl)]. */
 504                 id          = opcode(node, env);
 505                 entry       = listmap_find(&map, id);
 506                 bl->next    = entry->list;
 507                 entry->list = bl;
 508         }
 509
 510         /* split out ready blocks */
 511         if (n_ready > 0) {
 512                 partition_t *Z;
 513
 514                 if (n_ready < part->n_blocks)
 515                         Z = split(part, ready_blocks, env);
 516                 else
 517                         Z = part;
 518                 list_del(&Z->part_list);
 519
 520                 if (Z->n_blocks > 1) {
 521                         DB((dbg, LEVEL_2, " Partition %u is ready\n", Z->nr));
 522                         list_add(&Z->part_list, &env->ready);
 523                 } else {
 524                         DB((dbg, LEVEL_2, " Partition %u contains only one block, killed\n", Z->nr));
 525                 }
 526         }
 527
 528         /* for all sets S except one in the range of map do */
 529         for (iter = map.values; iter != NULL; iter = iter->next) {
 530                 block_t *S;
 531
 532                 if (iter->next == NULL) {
 533                         /* this is the last entry, ignore */
 534                         break;
 535                 }
 536                 S = iter->list;
 537
 538                 /* Add SPLIT( X, S ) to P. */
 539                 split(part, S, env);
 540         }
 541         listmap_term(&map);
 542 }  /* propagate_blocks */
 543
 544 /**
 545  * Propagate nodes on all wait queues.
 546  *
 547  * @param env    the environment
 548  */
 549 void propagate(environment_t *env) {
 550         partition_t *part, *next;
 551
 552         list_for_each_entry_safe(partition_t, part, next, &env->partitions, part_list) {
 553                 if (part->n_blocks < 2) {
 554                         /* zero or one block left, kill this partition */
 555                         list_del(&part->part_list);
 556                         DB((dbg, LEVEL_2, " Partition %u contains less than 2 blocks, killed\n", part->nr));
 557                 } else
 558                         propagate_blocks(part, env);
 559         }
 560 }  /* propagate */
 561
 562 /**
 563  * Apply analysis results by replacing all blocks of a partition
 564  * by one representative.
 565  *
 566  * Route all inputs from all block of the partition to the one
 567  * representative.
 568  * Enhance all existing Phis by combining them.
 569  * Create new Phis for all previous input nodes.
 570  *
 571  * @param part  the partition to process
 572  */
 573 static void apply(ir_graph *irg, partition_t *part) {
 574         block_t *repr = list_entry(part->blocks.next, block_t, block_list);
 575         block_t *bl;
 576         ir_node *block, *end, *meet_block, *p, *next;
 577         ir_node **ins, **phi_ins;
 578         phi_t   *repr_phi, *phi;
 579         pair_t  *repr_pair, *pair;
 580         int     i, j, k, n, block_nr, n_phis;
 581
 582         list_del(&repr->block_list);
 583
 584         /* prepare new in arrays for the block ... */
 585         block = repr->block;
 586         n     = get_Block_n_cfgpreds(block);
 587         ins   = NEW_ARR_F(ir_node *, n);
 588
 589         for (i = 0; i < n; ++i) {
 590                 ins[i] = get_Block_cfgpred(block, i);
 591         }
 592
 593         /* ... for all existing Phis ... */
 594         for (repr_phi = repr->phis; repr_phi != NULL; repr_phi = repr_phi->next) {
 595                 repr_phi->ins = NEW_ARR_F(ir_node *, n);
 596
 597                 for (i = 0; i < n; ++i)
 598                         repr_phi->ins[i] = get_Phi_pred(repr_phi->phi, i);
 599         }
 600
 601         /* ... and all newly created Phis */
 602         for (repr_pair = repr->input_pairs; repr_pair != NULL; repr_pair = repr_pair->next) {
 603                 ir_node *input = get_irn_n(repr_pair->irn, repr_pair->index);
 604
 605                 repr_pair->ins = NEW_ARR_F(ir_node *, n);
 606                 for (i = 0; i < n; ++i)
 607                         repr_pair->ins[i] = input;
 608         }
 609
 610         DB((dbg, LEVEL_1, "Replacing "));
 611
 612         /* collect new in arrays */
 613         end = get_irg_end(irg);
 614         block_nr = 0;
 615         list_for_each_entry(block_t, bl, &part->blocks, block_list) {
 616                 block = bl->block;
 617                 ++block_nr;
 618
 619                 DB((dbg, LEVEL_1, "%+F, ", block));
 620
 621                 /* first step: kill any keep-alive from this block */
 622                 for (i = get_End_n_keepalives(end) - 1; i >= 0; --i) {
 623                         ir_node *ka = get_End_keepalive(end, i);
 624
 625                         if (is_Block(ka)) {
 626                                 if (ka == block)
 627                                         remove_End_keepalive(end, ka);
 628                         } else {
 629                                 if (get_nodes_block(ka) == block)
 630                                         remove_End_keepalive(end, ka);
 631                         }
 632                 }
 633
 634                 /* second step: update control flow */
 635                 n = get_Block_n_cfgpreds(block);
 636                 for (i = 0; i < n; ++i) {
 637                         ir_node *pred = get_Block_cfgpred(block, i);
 638                         ARR_APP1(ir_node *, ins, pred);
 639                 }
 640
 641                 /* third step: update Phis */
 642                 for (repr_phi = repr->phis, phi = bl->phis;
 643                      repr_phi != NULL;
 644                      repr_phi = repr_phi->next, phi = phi->next) {
 645                         for (i = 0; i < n; ++i) {
 646                                 ir_node *pred = get_Phi_pred(phi->phi, i);
 647                                 ARR_APP1(ir_node *, repr_phi->ins, pred);
 648                         }
 649                 }
 650
 651                 /* fourth step: update inputs for new Phis */
 652                 for (repr_pair = repr->input_pairs, pair = bl->input_pairs;
 653                      repr_pair != NULL;
 654                      repr_pair = repr_pair->next, pair = pair->next) {
 655                         ir_node *input = get_irn_n(pair->irn, pair->index);
 656
 657                         for (i = 0; i < n; ++i)
 658                                 ARR_APP1(ir_node *, repr_pair->ins, input);
 659                 }
 660         }
 661
 662         DB((dbg, LEVEL_1, "by %+F\n", repr->block));
 663
 664         /* rewire block input ... */
 665         n = ARR_LEN(ins);
 666
 667         /*
 668          * Some problem here. For:
 669          * if (x) y = 1; else y = 2;
 670          *
 671          * the following code is constructed:
 672          *
 673          * b0: if (x) goto b1; else goto b1;
 674          * b1: y = Phi(1,2)
 675          *
 676          * However, both predecessors of b1 are b0, making the Phi
 677          * "wrong".
 678          *
 679          * We solve this by fixing critical edges.
 680          */
 681         for (i = 0; i < n; ++i) {
 682                 ir_node     *pred = ins[i];
 683                 const ir_op *cfop;
 684
 685                 if (is_Bad(pred))
 686                         continue;
 687
 688                 cfop = get_irn_op(skip_Proj(pred));
 689                 if (is_op_fragile(cfop)) {
 690                         /* ignore exception flow */
 691                         continue;
 692                 }
 693                 if (is_op_forking(cfop)) {
 694                         /* a critical edge */
 695                         ir_node *block = new_r_Block(irg, 1, &ins[i]);
 696                         ir_node *jmp   = new_r_Jmp(irg, block);
 697                         ins[i] = jmp;
 698                 }
 699         }
 700
 701         block = repr->block;
 702         set_irn_in(block, n, ins);
 703         DEL_ARR_F(ins);
 704
 705         /* ... existing Phis ... */
 706         for (repr_phi = repr->phis; repr_phi != NULL; repr_phi = repr_phi->next) {
 707                 set_irn_in(repr_phi->phi, n, repr_phi->ins);
 708                 DEL_ARR_F(repr_phi->ins);
 709         }
 710
 711         /* ... and all inputs by creating new Phis ... */
 712         for (repr_pair = repr->input_pairs; repr_pair != NULL; repr_pair = repr_pair->next) {
 713                 ir_node *input = get_irn_n(repr_pair->irn, repr_pair->index);
 714                 ir_mode *mode  = get_irn_mode(input);
 715                 ir_node *phi   = new_r_Phi(current_ir_graph, block, n, repr_pair->ins, mode);
 716
 717                 set_irn_n(repr_pair->irn, repr_pair->index, phi);
 718                 DEL_ARR_F(repr_pair->ins);
 719
 720                 /* might be optimized away */
 721                 if (is_Phi(phi))
 722                         add_Block_phi(block, phi);
 723         }
 724
 725         /* ... finally rewire the meet block and fix its Phi-nodes */
 726         meet_block = part->meet_block;
 727         n         = get_Block_n_cfgpreds(meet_block);
 728
 729         ins = NEW_ARR_F(ir_node *, n);
 730
 731         n_phis = 0;
 732         for (p = get_Block_phis(meet_block); p != NULL; p = get_Phi_next(p)) {
 733                 ++n_phis;
 734         }
 735
 736         phi_ins = NEW_ARR_F(ir_node *, n_phis * n);
 737
 738         for (i = j = 0; i < n; ++i) {
 739                 ir_node *pred = get_Block_cfgpred(meet_block, i);
 740
 741                 list_for_each_entry(block_t, bl, &part->blocks, block_list) {
 742                         if (bl->cf_root->node == pred)
 743                                 goto continue_outer;
 744                 }
 745                 ins[j] = pred;
 746
 747                 for (k = 0, p = get_Block_phis(meet_block); p != NULL; p = get_Phi_next(p), ++k) {
 748                         phi_ins[k * n + j] = get_Phi_pred(p, i);
 749                 }
 750                 ++j;
 751
 752 continue_outer:
 753                 ;
 754         }
 755
 756         /* fix phis */
 757         if (j == 1) {
 758                 for (k = 0, p = get_Block_phis(meet_block); p != NULL; p = next, ++k) {
 759                         next = get_Phi_next(p);
 760
 761                         exchange(p, phi_ins[k * n]);
 762                 }
 763                 /* all Phis killed */
 764                 set_Block_phis(meet_block, NULL);
 765         } else {
 766                 for (k = 0, p = get_Block_phis(meet_block); p != NULL; p = next, ++k) {
 767                         next = get_Phi_next(p);
 768
 769                         set_irn_in(p, j, &phi_ins[k * n]);
 770                 }
 771         }
 772         DEL_ARR_F(phi_ins);
 773
 774         /* fix inputs of the meet block */
 775         set_irn_in(meet_block, j, ins);
 776         DEL_ARR_F(ins);
 777 }  /* apply */
 778
 779 /**
 780  * Create a partition for a the end block.
 781  *
 782  * @param end_block  the end block
 783  * @param env        the environment
 784  */
 785 static void partition_for_end_block(ir_node *end_block, environment_t *env) {
 786         partition_t *part = create_partition(end_block, env);
 787         ir_node     *end;
 788         int         i;
 789
 790         /* collect normal blocks */
 791         for (i = get_Block_n_cfgpreds(end_block) - 1; i >= 0; --i) {
 792                 ir_node *pred = get_Block_cfgpred(end_block, i);
 793                 ir_node *block;
 794                 block_t *bl;
 795                 node_t  *node;
 796
 797                 mark_irn_visited(pred);
 798
 799                 block = get_nodes_block(pred);
 800                 bl    = create_block(block, part, env);
 801                 node  = create_node(pred, bl, env);
 802
 803                 bl->cf_root = node;
 804         }
 805
 806         /* collect all no-return blocks */
 807         end = get_irg_end(current_ir_graph);
 808         for (i = get_End_n_keepalives(end) - 1; i >= 0; --i) {
 809                 ir_node *ka    = get_End_keepalive(end, i);
 810                 ir_node *block;
 811                 block_t *bl;
 812                 node_t  *node;
 813
 814                 if (! is_Call(ka))
 815                         continue;
 816                 mark_irn_visited(ka);
 817
 818                 /* found one */
 819                 block = get_nodes_block(ka);
 820                 bl    = create_block(block, part, env);
 821                 node  = create_node(ka, bl, env);
 822
 823                 bl->cf_root = node;
 824         }
 825
 826         dump_partition("Created", part);
 827 }  /* partition_for_end_block */
 828
 829 #ifdef GENERAL_SHAPE
 830 /**
 831  * Create a partition for a given meet block.
 832  *
 833  * @param block    the meet block
 834  * @param preds    array of candidate predecessors
 835  * @param n_preds  number of elements in preds
 836  * @param env      the environment
 837  */
 838 static void partition_for_block(ir_node *block, ir_node *preds[], int n_preds, environment_t *env) {
 839         partition_t *part = create_partition(block, env);
 840         int         i;
 841
 842         for (i = n_preds - 1; i >= 0; --i) {
 843                 ir_node *pred = preds[i];
 844                 ir_node *block;
 845                 block_t *bl;
 846                 node_t  *node;
 847
 848                 mark_irn_visited(pred);
 849
 850                 block = get_nodes_block(pred);
 851                 bl    = create_block(block, part, env);
 852                 node  = create_node(pred, bl, env);
 853
 854                 bl->cf_root = node;
 855         }
 856
 857         dump_partition("Created", part);
 858 }  /* partition_for_block */
 859
 860 /**
 861  * Walker: clear the links of all block phi lists and normal
 862  * links.
 863  */
 864 static void clear_phi_links(ir_node *irn, void *env) {
 865         (void) env;
 866         if (is_Block(irn)) {
 867                 set_Block_phis(irn, NULL);
 868                 set_irn_link(irn, NULL);
 869         }
 870 }  /* clear_phi_links */
 871
 872 /**
 873  * Walker, detect live-out only nodes.
 874  */
 875 static void find_liveouts(ir_node *irn, void *ctx) {
 876         environment_t *env        = ctx;
 877         ir_node       **live_outs = env->live_outs;
 878         ir_node       *this_block;
 879         int           i;
 880
 881         if (is_Block(irn))
 882                 return;
 883
 884         /* ignore Keep-alives */
 885         if (is_End(irn))
 886                 return;
 887
 888         this_block = get_nodes_block(irn);
 889
 890         if (is_Phi(irn)) {
 891                 /* update the Phi list */
 892                 add_Block_phi(this_block, irn);
 893         }
 894
 895         for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
 896                 ir_node *pred_block;
 897                 ir_node *pred = get_irn_n(irn, i);
 898                 int     idx   = get_irn_idx(pred);
 899
 900                 if (live_outs[idx] == pred) {
 901                         /* referenced by other nodes inside this block */
 902                         return;
 903                 }
 904
 905                 pred_block = get_nodes_block(pred);
 906                 if (this_block != pred_block) {
 907                         /* pred is a live-out */
 908                         live_outs[idx] = pred_block;
 909                 } else {
 910                         /* this node is referenced from inside this block */
 911                         live_outs[idx] = pred;
 912                 }
 913         }
 914 }
 915
 916 /**
 917  * Check if the current block is the meet block of a its predecessors.
 918  */
 919 static void check_for_cf_meet(ir_node *block, void *ctx) {
 920         environment_t *env = ctx;
 921         int           i, k, n;
 922         ir_node       **preds;
 923
 924         if (block == get_irg_end_block(current_ir_graph)) {
 925                 /* always create a partition for the end block */
 926                 partition_for_end_block(block, env);
 927                 return;
 928         }
 929
 930         n = get_Block_n_cfgpreds(block);
 931         if (n <= 1) {
 932                 /* Must have at least two predecessors */
 933                 return;
 934         }
 935         NEW_ARR_A(ir_node *, preds, n);
 936
 937         k = 0;
 938         for (i = n - 1; i >= 0; --i) {
 939                 ir_node *pred = get_Block_cfgpred(block, i);
 940
 941                 /* pred must be a direct jump to us */
 942                 if (! is_Jmp(pred) && ! is_Raise(pred))
 943                         continue;
 944                 preds[k++] = pred;
 945         }
 946
 947         if (k > 1)
 948                 partition_for_block(block, preds, k, env);
 949 }  /* check_for_cf_meet */
 950
 951 /**
 952  * Compare two nodes for root ordering.
 953  */
 954 static int cmp_nodes(const void *a, const void *b) {
 955         ir_node *const *pa     = a;
 956         ir_node *const *pb     = b;
 957         const ir_node  *irn_a  = *pa;
 958         const ir_node  *irn_b  = *pb;
 959         ir_opcode      code_a  = get_irn_opcode(irn_a);
 960         ir_opcode      code_b  = get_irn_opcode(irn_b);
 961         ir_mode        *mode_a, *mode_b;
 962         unsigned       idx_a, idx_b;
 963
 964         /* try opcode first */
 965         if (code_a != code_b)
 966                 return code_a - code_b;
 967
 968         /* try mode */
 969         mode_a = get_irn_mode(irn_a);
 970         mode_b = get_irn_mode(irn_b);
 971
 972         if (mode_a != mode_b)
 973                 return mode_a < mode_b ? -1 : +1;
 974
 975         /* last resort: index */
 976         idx_a = get_irn_idx(irn_a);
 977         idx_b = get_irn_idx(irn_b);
 978
 979         return (idx_a > idx_b) - (idx_a < idx_b);
 980 }  /* cmp_nodes */
 981
 982 /**
 983  * Add the roots to all blocks.
 984  */
 985 static void add_roots(ir_graph *irg, environment_t *env) {
 986         unsigned idx, n      = get_irg_last_idx(irg);
 987         ir_node  **live_outs = env->live_outs;
 988         block_t  *bl;
 989
 990         for (idx = 0; idx < n; ++idx) {
 991                 ir_node *block = live_outs[idx];
 992
 993                 if (block != NULL && is_Block(block)) {
 994                         block_t *bl = get_Block_entry(block);
 995
 996                         if (bl != NULL) {
 997                                 ir_node *irn = get_idx_irn(irg, idx);
 998
 999                                 if (!irn_visited_else_mark(irn)) {
1000                                         ARR_APP1(ir_node *, bl->roots, irn);
1001                                 }
1002                         }
1003                 }
1004         }
1005         /*
1006          * Now sort the roots to normalize them as good as possible.
1007      * Else, we will split identical blocks if we start which different roots
1008          */
1009         for (bl = env->all_blocks; bl != NULL; bl = bl->all_next) {
1010                 int i, n = ARR_LEN(bl->roots);
1011
1012 #if 1
1013                 /* TODO: is this really needed? The roots are already in
1014                    idx-order by construction, which might be good enough. */
1015                 qsort(bl->roots, n, sizeof(bl->roots[0]), cmp_nodes);
1016 #endif
1017
1018                 DB((dbg, LEVEL_2, " Adding Roots for block %+F\n  ", bl->block));
1019                 /* ok, add them sorted */
1020                 for (i = 0; i < n; ++i) {
1021                         DB((dbg, LEVEL_2, "%+F, ", bl->roots[i]));
1022                         create_node(bl->roots[i], bl, env);
1023                 }
1024                 DB((dbg, LEVEL_2, "\n"));
1025                 DEL_ARR_F(bl->roots);
1026                 bl->roots = NULL;
1027         }
1028 }  /* add_roots */
1029 #endif /* GENERAL_SHAPE */
1030
1031 /* Combines congruent end blocks into one. */
1032 int shape_blocks(ir_graph *irg) {
1033         ir_graph      *rem;
1034         environment_t env;
1035         partition_t   *part;
1036         int           res, n;
1037
1038         rem = current_ir_graph;
1039         current_ir_graph = irg;
1040
1041         /* register a debug mask */
1042         FIRM_DBG_REGISTER(dbg, "firm.opt.blocks");
1043
1044         DEBUG_ONLY(part_nr = 0);
1045         DB((dbg, LEVEL_1, "Shaping blocks for %+F\n", irg));
1046
1047         /* works better, when returns are placed at the end of the blocks */
1048         normalize_n_returns(irg);
1049
1050         obstack_init(&env.obst);
1051         INIT_LIST_HEAD(&env.partitions);
1052         INIT_LIST_HEAD(&env.ready);
1053         env.opcode2id_map  = new_set(cmp_opcode, iro_Last * 4);
1054
1055         n             = get_irg_last_idx(irg);
1056         env.live_outs = NEW_ARR_F(ir_node *, n);
1057         memset(env.live_outs, 0, sizeof(*env.live_outs) * n);
1058
1059         env.all_blocks = NULL;
1060
1061         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
1062
1063 #ifdef GENERAL_SHAPE
1064         /*
1065          * Detect, which nodes are live-out only: these are the roots of our blocks.
1066          * Build phi lists.
1067          */
1068         irg_walk_graph(irg, clear_phi_links, find_liveouts, &env);
1069 #endif
1070
1071         ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
1072
1073         inc_irg_visited(irg);
1074 #ifdef GENERAL_SHAPE
1075         /*
1076          * Detect all control flow meets and create partitions.
1077          */
1078         irg_block_walk_graph(irg, NULL, check_for_cf_meet, &env);
1079
1080         /* add root nodes to the partition blocks */
1081         add_roots(irg, &env);
1082 #else
1083         partition_for_end_block(get_irg_end_block(irg), &env);
1084 #endif
1085
1086         while (! list_empty(&env.partitions))
1087                 propagate(&env);
1088
1089         res = !list_empty(&env.ready);
1090
1091         list_for_each_entry(partition_t, part, &env.ready, part_list) {
1092                 dump_partition("Ready Partition", part);
1093                 apply(irg, part);
1094         }
1095         ir_free_resources(irg, IR_RESOURCE_IRN_VISITED | IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
1096
1097         if (res) {
1098                 /* control flow changed */
1099                 set_irg_outs_inconsistent(irg);
1100                 set_irg_extblk_inconsistent(irg);
1101                 set_irg_doms_inconsistent(irg);
1102                 /* Hmm, only the root loop is inconsistent */
1103                 set_irg_loopinfo_inconsistent(irg);
1104
1105                 /* Calls might be removed. */
1106                 set_trouts_inconsistent();
1107         }
1108
1109         DEL_ARR_F(env.live_outs);
1110         del_set(env.opcode2id_map);
1111         obstack_free(&env.obst, NULL);
1112         current_ir_graph = rem;
1113
1114         return res;
1115 }  /* shape_blocks */