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