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 "irgraph_t.h"
  34 #include "irnode_t.h"
  35 #include "iropt_t.h"
  36 #include "trouts.h"
  37 #include "set.h"
  38 #include "debug.h"
  39
  40 typedef struct partition_t     partition_t;
  41 typedef struct block_t         block_t;
  42 typedef struct node_t          node_t;
  43 typedef struct pair_t          pair_t;
  44 typedef struct phi_t           phi_t;
  45 typedef struct opcode_key_t    opcode_key_t;
  46 typedef struct listmap_entry_t listmap_entry_t;
  47 typedef struct environment_t   environment_t;
  48
  49 /** An opcode map key. */
  50 struct opcode_key_t {
  51         ir_opcode   code;   /**< The Firm opcode. */
  52         ir_mode     *mode;  /**< The mode of all nodes in the partition. */
  53         int         arity;  /**< The arity of this opcode (needed for Phi etc. */
  54         union {
  55                 long      proj;   /**< For Proj nodes, its proj number */
  56                 ir_entity *ent;   /**< For Sel Nodes, its entity */
  57         } u;
  58 };
  59
  60 /** A partition contains all congruent blocks. */
  61 struct partition_t {
  62         list_head part_list;     /**< Double linked list of partitions. */
  63         list_head blocks;        /**< List of blocks in this partition. */
  64         unsigned  n_blocks;      /**< Number of block in this partition. */
  65         ir_node   *meet_block;   /**< The control flow meet block of this partition. */
  66 #ifdef DEBUG_libfirm
  67         unsigned  nr;            /**< For debugging: number of this partition. */
  68 #endif
  69 };
  70
  71 /** A block. */
  72 struct block_t {
  73         list_head  block_list;   /**< Double linked list of block inside a partition. */
  74         list_head  nodes;        /**< Wait-queue of nodes that must be checked for congruence. */
  75         block_t    *next;        /**< Next block of a split list. */
  76         ir_node    *block;       /**< Pointer to the associated IR-node block. */
  77         node_t     *roots;       /**< The list of all root nodes. */
  78         pair_t     *input_pairs; /**< The list of inputs to this block. */
  79         phi_t      *phis;        /**< The list of Phis in this block. */
  80 };
  81
  82 /** A node. */
  83 struct node_t {
  84         list_head  node_list;    /**< Double linked list of block inside a partition. */
  85         ir_node    *node;        /**< Pointer to the associated IR-node or NULL for block inputs. */
  86         node_t     *next;        /**< Link to the next node in the root set. */
  87         char       is_input;     /**< Set if this node is an input from other block. */
  88 };
  89
  90 /** The environment. */
  91 struct environment_t {
  92         list_head       partitions;     /**< list of partitions. */
  93         list_head       ready;          /**< list of ready partitions. */
  94         set             *opcode2id_map; /**< The opcodeMode->id map. */
  95         struct obstack  obst;           /** obstack for temporary data */
  96 };
  97
  98 /** A node, input index pair. */
  99 struct pair_t {
 100         pair_t  *next;    /**< Points to the next pair entry. */
 101         ir_node *irn;     /**< The IR-node. */
 102         int     index;    /**< An input index. */
 103         ir_node **ins;    /**< A new in array once allocated. */
 104 };
 105
 106 /** A Phi, inputs pair. */
 107 struct phi_t {
 108         phi_t   *next;    /**< Points to the next Phi pair entry. */
 109         ir_node *phi;     /**< The Phi node. */
 110         ir_node **ins;    /**< A new in array once allocated. */
 111 };
 112
 113 /**
 114  * An entry in the list_map.
 115  */
 116 struct listmap_entry_t {
 117         void            *id;    /**< The id. */
 118         block_t         *list;  /**< The associated list for this id. */
 119         listmap_entry_t *next;  /**< Link to the next entry in the map. */
 120 };
 121
 122 /** We must map id's to lists. */
 123 typedef struct listmap_t {
 124         set             *map;    /**< Map id's to listmap_entry_t's */
 125         listmap_entry_t *values; /**< List of all values in the map. */
 126 } listmap_t;
 127
 128 /** The debug module handle. */
 129 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
 130
 131 /** Next partition number. */
 132 DEBUG_ONLY(static unsigned part_nr = 0);
 133
 134 #ifdef DEBUG_libfirm
 135 /**
 136  * Dump partition to output.
 137  */
 138 static void dump_partition(const char *msg, const partition_t *part) {
 139         const block_t *block;
 140         int           first = 1;
 141
 142         DB((dbg, LEVEL_2, " %s part%u (%u blocks) {\n  ", msg, part->nr, part->n_blocks));
 143         list_for_each_entry(block_t, block, &part->blocks, block_list) {
 144                 DB((dbg, LEVEL_2, "%s%+F", first ? "" : ", ", block->block));
 145                 first = 0;
 146         }
 147         DB((dbg, LEVEL_2, "\n }\n"));
 148 }  /* dump_partition */
 149
 150 /**
 151  * Dumps a list.
 152  */
 153 static void dump_list(const char *msg, const block_t *block) {
 154         const block_t *p;
 155         int           first = 1;
 156
 157         DB((dbg, LEVEL_3, "  %s = {\n   ", msg));
 158         for (p = block; p != NULL; p = p->next) {
 159                 DB((dbg, LEVEL_3, "%s%+F", first ? "" : ", ", p->block));
 160                 first = 0;
 161         }
 162         DB((dbg, LEVEL_3, "\n  }\n"));
 163 }  /* do_dump_list */
 164 #else
 165 #define dump_partition(msg, part)
 166 #define dump_list(msg, block)
 167 #endif
 168
 169 /**
 170  * Compare two pointer values of a listmap.
 171  */
 172 static int listmap_cmp_ptr(const void *elt, const void *key, size_t size) {
 173         const listmap_entry_t *e1 = elt;
 174         const listmap_entry_t *e2 = key;
 175
 176         (void) size;
 177         return e1->id != e2->id;
 178 }  /* listmap_cmp_ptr */
 179
 180 /**
 181  * Initializes a listmap.
 182  *
 183  * @param map  the listmap
 184  */
 185 static void listmap_init(listmap_t *map) {
 186         map->map    = new_set(listmap_cmp_ptr, 16);
 187         map->values = NULL;
 188 }  /* listmap_init */
 189
 190 /**
 191  * Terminates a listmap.
 192  *
 193  * @param map  the listmap
 194  */
 195 static void listmap_term(listmap_t *map) {
 196         del_set(map->map);
 197 }  /* listmap_term */
 198
 199 /**
 200  * Return the associated listmap entry for a given id.
 201  *
 202  * @param map  the listmap
 203  * @param id   the id to search for
 204  *
 205  * @return the associated listmap entry for the given id
 206  */
 207 static listmap_entry_t *listmap_find(listmap_t *map, void *id) {
 208         listmap_entry_t key, *entry;
 209
 210         key.id   = id;
 211         key.list = NULL;
 212         key.next = NULL;
 213         entry = set_insert(map->map, &key, sizeof(key), HASH_PTR(id));
 214
 215         if (entry->list == NULL) {
 216                 /* a new entry, put into the list */
 217                 entry->next = map->values;
 218                 map->values = entry;
 219         }
 220         return entry;
 221 }  /* listmap_find */
 222
 223 /**
 224  * Calculate the hash value for an opcode map entry.
 225  *
 226  * @param entry  an opcode map entry
 227  *
 228  * @return a hash value for the given opcode map entry
 229  */
 230 static unsigned opcode_hash(const opcode_key_t *entry) {
 231         return (entry->mode - (ir_mode *)0) * 9 + entry->code + entry->u.proj * 3 + HASH_PTR(entry->u.ent) + entry->arity;
 232 }  /* opcode_hash */
 233
 234 /**
 235  * Compare two entries in the opcode map.
 236  */
 237 static int cmp_opcode(const void *elt, const void *key, size_t size) {
 238         const opcode_key_t *o1 = elt;
 239         const opcode_key_t *o2 = key;
 240
 241         (void) size;
 242         return o1->code != o2->code || o1->mode != o2->mode ||
 243                o1->arity != o2->arity ||
 244                o1->u.proj != o2->u.proj || o1->u.ent != o2->u.ent;
 245 }  /* cmp_opcode */
 246
 247 /**
 248  * Creates a new empty partition and put in on the
 249  * partitions list.
 250  *
 251  * @param meet_block  the control flow meet block of thi partition
 252  * @param env         the environment
 253  */
 254 static partition_t *create_partition(ir_node *meet_block, environment_t *env) {
 255         partition_t *part = obstack_alloc(&env->obst, sizeof(*part));
 256
 257         INIT_LIST_HEAD(&part->blocks);
 258         part->meet_block = meet_block;
 259         part->n_blocks   = 0;
 260         DEBUG_ONLY(part->nr = part_nr++);
 261         list_add_tail(&part->part_list, &env->partitions);
 262         return part;
 263 }  /* create_partition */
 264
 265 /**
 266  * Allocate a new block in the given partition.
 267  *
 268  * @param block      the IR-node
 269  * @param partition  the partition to add to
 270  * @param env        the environment
 271  */
 272 static block_t *create_block(ir_node *block, partition_t *partition, environment_t *env) {
 273         block_t *bl = obstack_alloc(&env->obst, sizeof(*bl));
 274
 275         INIT_LIST_HEAD(&bl->nodes);
 276         bl->next        = NULL;
 277         bl->block       = block;
 278         bl->roots       = NULL;
 279         bl->input_pairs = NULL;
 280         bl->phis        = NULL;
 281
 282         list_add_tail(&bl->block_list, &partition->blocks);
 283         ++partition->n_blocks;
 284
 285         return bl;
 286 }  /* create_block */
 287
 288 /**
 289  * Allocate a new node and add it to a blocks wait queue.
 290  *
 291  * @param irn    the IR-node
 292  * @param block  the block to add to
 293  * @param env    the environment
 294  */
 295 static node_t *create_node(ir_node *irn, block_t *block, environment_t *env) {
 296         node_t *node = obstack_alloc(&env->obst, sizeof(*node));
 297
 298         node->node     = irn;
 299         node->next     = NULL;
 300         node->is_input = 0;
 301
 302         list_add_tail(&node->node_list, &block->nodes);
 303
 304         return node;
 305 }  /* create_node */
 306
 307 /**
 308  * Add an input pair to a block.
 309  *
 310  * @param block  the block
 311  * @param irn    the IR-node that has an block input
 312  * @param idx    the index of the block input in node's predecessors
 313  * @param env    the environment
 314  */
 315 static void add_pair(block_t *block, ir_node *irn, int idx, environment_t *env) {
 316         pair_t *pair = obstack_alloc(&env->obst, sizeof(*pair));
 317
 318         pair->next  = block->input_pairs;
 319         pair->irn   = irn;
 320         pair->index = idx;
 321         pair->ins   = NULL;
 322
 323         block->input_pairs = pair;
 324 }  /* add_pair */
 325
 326 /**
 327  * Add a Phi to a block.
 328  *
 329  * @param block  the block
 330  * @param phi    the Phi node
 331  * @param env    the environment
 332  */
 333 static void add_phi(block_t *block, ir_node *phi, environment_t *env) {
 334         phi_t *node = obstack_alloc(&env->obst, sizeof(*node));
 335
 336         node->next = block->phis;
 337         node->phi  = phi;
 338         node->ins  = NULL;
 339
 340         block->phis = node;
 341 }  /** add_phi */
 342
 343 /**
 344  * Creates an opcode from a node.
 345  */
 346 static opcode_key_t *opcode(const node_t *node, environment_t *env) {
 347         opcode_key_t key, *entry;
 348         ir_node      *irn = node->node;
 349
 350         if (node->is_input) {
 351                 /* Node: as Block nodes are never propagated, it is safe to
 352                    use its code for "input" node */
 353                 key.code   = iro_Block;
 354                 key.arity  = 0;
 355         } else {
 356                 key.code   = get_irn_opcode(irn);
 357                 key.arity  = get_irn_arity(irn);
 358         }
 359         key.mode   = get_irn_mode(node->node);
 360         key.u.proj = 0;
 361         key.u.ent  = NULL;
 362
 363         switch (key.code) {
 364         case iro_Proj:
 365                 key.u.proj = get_Proj_proj(irn);
 366                 break;
 367         case iro_Sel:
 368                 key.u.ent = get_Sel_entity(irn);
 369                 break;
 370         default:
 371                 break;
 372         }
 373
 374         entry = set_insert(env->opcode2id_map, &key, sizeof(key), opcode_hash(&key));
 375         return entry;
 376 }  /* opcode */
 377
 378 /**
 379  * Split a partition by a local list.
 380  *
 381  * @param Z    partition to split
 382  * @param g    a (non-empty) block list
 383  * @param env  the environment
 384  *
 385  * @return  a new partition containing the nodes of g
 386  */
 387 static partition_t *split(partition_t *Z, block_t *g, environment_t *env) {
 388         partition_t *Z_prime;
 389         block_t     *block;
 390         unsigned    n = 0;
 391
 392         dump_partition("Splitting ", Z);
 393         dump_list("by list ", g);
 394
 395         assert(g != NULL);
 396
 397         /* Remove g from Z. */
 398         for (block = g; block != NULL; block = block->next) {
 399                 list_del(&block->block_list);
 400                 ++n;
 401         }
 402         assert(n < Z->n_blocks);
 403         Z->n_blocks -= n;
 404
 405         /* Move g to a new partition, Z'. */
 406         Z_prime = create_partition(Z->meet_block, env);
 407         for (block = g; block != NULL; block = block->next) {
 408                 list_add_tail(&block->block_list, &Z_prime->blocks);
 409         }
 410         Z_prime->n_blocks = n;
 411
 412         dump_partition("Now ", Z);
 413         dump_partition("Created new ", Z_prime);
 414         return Z_prime;
 415 }  /* split */
 416
 417 /**
 418  * Propagate nodes on all wait queues of the given partition.
 419  *
 420  * @param part  the partition
 421  * @param env    the environment
 422  */
 423 void propagate_blocks(partition_t *part, environment_t *env) {
 424         block_t         *ready_blocks = NULL;
 425         unsigned        n_ready       = 0;
 426         block_t         *bl, *next;
 427         listmap_t       map;
 428         listmap_entry_t *iter;
 429
 430         DB((dbg, LEVEL_2, " Propagate blocks on part%u\n", part->nr));
 431
 432         /* Let map be an empty mapping from the range of Opcodes to (local) list of Nodes. */
 433         listmap_init(&map);
 434         list_for_each_entry_safe(block_t, bl, next, &part->blocks, block_list) {
 435                 opcode_key_t    *id;
 436                 listmap_entry_t *entry;
 437                 node_t          *node;
 438
 439                 if (list_empty(&bl->nodes)) {
 440                         bl->next     = ready_blocks;
 441                         ready_blocks = bl;
 442                         ++n_ready;
 443                         DB((dbg, LEVEL_2, " Block %+F completely processed\n", bl->block));
 444                         continue;
 445                 }
 446
 447                 /* get the first node from the wait queue */
 448                 node = list_entry(bl->nodes.next, node_t, node_list);
 449                 list_del(&node->node_list);
 450
 451                 /* put all not-visited predecessors to the wait queue */
 452                 if (! node->is_input) {
 453                         ir_node *irn = node->node;
 454                         int     i;
 455
 456                         DB((dbg, LEVEL_3, "  propagate %+F\n", irn));
 457                         ir_normalize_node(node->node);
 458                         for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
 459                                 ir_node *pred  = get_irn_n(irn, i);
 460                                 ir_node *block = get_nodes_block(skip_Proj(pred));
 461                                 node_t *p_node;
 462
 463                                 if (block != bl->block) {
 464                                         p_node = create_node(pred, bl, env);
 465                                         /* do not threat Constants like live-ins */
 466                                         if (! is_irn_constlike(irn)) {
 467                                                 p_node->is_input = 1;
 468                                                 if (! is_Phi(irn))
 469                                                         add_pair(bl, irn, i, env);
 470                                         }
 471                                 } else if (! irn_visited_else_mark(pred)) {
 472                                         /* not yet visited, ok */
 473                                         p_node = create_node(pred, bl, env);
 474
 475                                         if (is_Phi(pred)) {
 476                                                 /* update the Phi list */
 477                                                 add_phi(bl, pred, env);
 478                                         }
 479                                 }
 480                         }
 481                 } else {
 482                         DB((dbg, LEVEL_3, "  propagate Input %+F\n", node->node));
 483                 }
 484
 485                 /* Add bl to map[opcode(bl)]. */
 486                 id          = opcode(node, env);
 487                 entry       = listmap_find(&map, id);
 488                 bl->next    = entry->list;
 489                 entry->list = bl;
 490         }
 491
 492         /* split out ready blocks */
 493         if (n_ready > 0) {
 494                 partition_t *Z;
 495
 496                 if (n_ready < part->n_blocks)
 497                         Z = split(part, ready_blocks, env);
 498                 else
 499                         Z = part;
 500                 list_del(&Z->part_list);
 501
 502                 if (Z->n_blocks > 1) {
 503                         DB((dbg, LEVEL_2, " Partition %u is ready\n", Z->nr));
 504                         list_add(&Z->part_list, &env->ready);
 505                 } else {
 506                         DB((dbg, LEVEL_2, " Partition %u contains only one block, killed\n", Z->nr));
 507                 }
 508         }
 509
 510         /* for all sets S except one in the range of map do */
 511         for (iter = map.values; iter != NULL; iter = iter->next) {
 512                 block_t *S;
 513
 514                 if (iter->next == NULL) {
 515                         /* this is the last entry, ignore */
 516                         break;
 517                 }
 518                 S = iter->list;
 519
 520                 /* Add SPLIT( X, S ) to P. */
 521                 split(part, S, env);
 522         }
 523         listmap_term(&map);
 524 }  /* propagate_blocks */
 525
 526 /**
 527  * Propagate nodes on all wait queues.
 528  *
 529  * @param env    the environment
 530  */
 531 void propagate(environment_t *env) {
 532         partition_t *part, *next;
 533
 534         list_for_each_entry_safe(partition_t, part, next, &env->partitions, part_list) {
 535                 if (part->n_blocks < 2) {
 536                         /* zero or one block left, kill this partition */
 537                         list_del(&part->part_list);
 538                         DB((dbg, LEVEL_2, " Partition %u contains less than 2 blocks, killed\n", part->nr));
 539                 } else
 540                         propagate_blocks(part, env);
 541         }
 542 }  /* propagate */
 543
 544 /**
 545  * Apply analysis results by replacing all blocks of a partition
 546  * by one representative.
 547  *
 548  * Route all inputs from all block of the partition to the one
 549  * representative.
 550  * Enhance all existing Phis by combining them.
 551  * Create new Phis for all previous input nodes.
 552  *
 553  * @param part  the partition to process
 554  */
 555 static void apply(ir_graph *irg, partition_t *part) {
 556         block_t *repr = list_entry(part->blocks.next, block_t, block_list);
 557         block_t *bl;
 558         ir_node *block, *end, *end_block;
 559         ir_node **ins;
 560         phi_t   *repr_phi, *phi;
 561         pair_t  *repr_pair, *pair;
 562         int     i, j, n, block_nr;
 563
 564         list_del(&repr->block_list);
 565
 566         /* prepare new in arrays for the block ... */
 567         block = repr->block;
 568         n     = get_Block_n_cfgpreds(block);
 569         ins   = NEW_ARR_F(ir_node *, n);
 570
 571         for (i = 0; i < n; ++i) {
 572                 ins[i] = get_Block_cfgpred(block, i);
 573         }
 574
 575         /* ... for all existing Phis ... */
 576         for (repr_phi = repr->phis; repr_phi != NULL; repr_phi = repr_phi->next) {
 577                 repr_phi->ins = NEW_ARR_F(ir_node *, n);
 578
 579                 for (i = 0; i < n; ++i)
 580                         repr_phi->ins[i] = get_Phi_pred(repr_phi->phi, i);
 581         }
 582
 583         /* ... and all newly created Phis */
 584         for (repr_pair = repr->input_pairs; repr_pair != NULL; repr_pair = repr_pair->next) {
 585                 ir_node *input = get_irn_n(repr_pair->irn, repr_pair->index);
 586
 587                 repr_pair->ins = NEW_ARR_F(ir_node *, n);
 588                 for (i = 0; i < n; ++i)
 589                         repr_pair->ins[i] = input;
 590         }
 591
 592         DB((dbg, LEVEL_1, "Replacing "));
 593
 594         /* collect new in arrays */
 595         end = get_irg_end(irg);
 596         block_nr = 0;
 597         list_for_each_entry(block_t, bl, &part->blocks, block_list) {
 598                 block = bl->block;
 599                 ++block_nr;
 600
 601                 DB((dbg, LEVEL_1, "%+F, ", block));
 602
 603                 /* first step: kill any keep-alive from this block */
 604                 for (i = get_End_n_keepalives(end) - 1; i >= 0; --i) {
 605                         ir_node *ka = get_End_keepalive(end, i);
 606
 607                         if (is_Block(ka)) {
 608                                 if (ka == block)
 609                                         remove_End_keepalive(end, ka);
 610                         } else {
 611                                 if (get_nodes_block(ka) == block)
 612                                         remove_End_keepalive(end, ka);
 613                         }
 614                 }
 615
 616                 /* second step: update control flow */
 617                 n = get_Block_n_cfgpreds(block);
 618                 for (i = 0; i < n; ++i) {
 619                         ir_node *pred = get_Block_cfgpred(block, i);
 620                         ARR_APP1(ir_node *, ins, pred);
 621                 }
 622
 623                 /* third step: update Phis */
 624                 for (repr_phi = repr->phis, phi = bl->phis;
 625                      repr_phi != NULL;
 626                      repr_phi = repr_phi->next, phi = phi->next) {
 627                         for (i = 0; i < n; ++i) {
 628                                 ir_node *pred = get_Phi_pred(phi->phi, i);
 629                                 ARR_APP1(ir_node *, repr_phi->ins, pred);
 630                         }
 631                 }
 632
 633                 /* fourth step: update inputs for new Phis */
 634                 for (repr_pair = repr->input_pairs, pair = bl->input_pairs;
 635                      repr_pair != NULL;
 636                      repr_pair = repr_pair->next, pair = pair->next) {
 637                         ir_node *input = get_irn_n(pair->irn, pair->index);
 638
 639                         for (i = 0; i < n; ++i)
 640                                 ARR_APP1(ir_node *, repr_pair->ins, input);
 641                 }
 642         }
 643
 644         DB((dbg, LEVEL_1, "by %+F\n", repr->block));
 645
 646         /* rewire block input ... */
 647         n = ARR_LEN(ins);
 648
 649         /*
 650          * Some problem here. For:
 651          * if (x) y = 1; else y = 2;
 652          *
 653          * the following code is constructed:
 654          *
 655          * b0: if (x) goto b1; else goto b1;
 656          * b1: y = Phi(1,2)
 657          *
 658          * However, both predecessors of b1 are b0, making the Phi
 659          * "wrong".
 660          *
 661          * We solve this by fixing critical edges.
 662          */
 663         for (i = 0; i < n; ++i) {
 664                 ir_node     *pred = ins[i];
 665                 const ir_op *cfop;
 666
 667                 if (is_Bad(pred))
 668                         continue;
 669
 670                 cfop = get_irn_op(skip_Proj(pred));
 671                 if (is_op_fragile(cfop)) {
 672                         /* ignore exception flow */
 673                         continue;
 674                 }
 675                 if (is_op_forking(cfop)) {
 676                         /* a critical edge */
 677                         ir_node *block = new_r_Block(irg, 1, &ins[i]);
 678                         ir_node *jmp   = new_r_Jmp(irg, block);
 679                         ins[i] = jmp;
 680                 }
 681         }
 682
 683         block = repr->block;
 684         set_irn_in(block, n, ins);
 685         DEL_ARR_F(ins);
 686
 687         /* ... existing Phis ... */
 688         for (repr_phi = repr->phis; repr_phi != NULL; repr_phi = repr_phi->next) {
 689                 set_irn_in(repr_phi->phi, n, repr_phi->ins);
 690                 DEL_ARR_F(repr_phi->ins);
 691         }
 692
 693         /* ... and all inputs by creating new Phis ... */
 694         for (repr_pair = repr->input_pairs; repr_pair != NULL; repr_pair = repr_pair->next) {
 695                 ir_node *input = get_irn_n(repr_pair->irn, repr_pair->index);
 696                 ir_mode *mode  = get_irn_mode(input);
 697                 ir_node *phi   = new_r_Phi(current_ir_graph, block, n, repr_pair->ins, mode);
 698
 699                 set_irn_n(repr_pair->irn, repr_pair->index, phi);
 700                 DEL_ARR_F(repr_pair->ins);
 701         }
 702
 703         /* ... finally rewire the end block */
 704         end_block = get_irg_end_block(irg);
 705         n         = get_Block_n_cfgpreds(end_block);
 706
 707         ins = NEW_ARR_F(ir_node *, n);
 708
 709         for (i = j = 0; i < n; ++i) {
 710                 ir_node *out = get_Block_cfgpred(end_block, i);
 711
 712                 list_for_each_entry(block_t, bl, &part->blocks, block_list) {
 713                         node_t *root;
 714
 715                         for (root = bl->roots; root != NULL; root = root->next) {
 716                                 if (root->node == out)
 717                                         goto found;
 718                         }
 719                 }
 720                 ins[j++] = out;
 721 found:
 722                 ;
 723         }
 724
 725         set_irn_in(end_block, j, ins);
 726         DEL_ARR_F(ins);
 727
 728         /* control flow changed */
 729         set_irg_outs_inconsistent(irg);
 730         set_irg_extblk_inconsistent(irg);
 731         set_irg_doms_inconsistent(irg);
 732         /* Hmm, only the root loop is inconsistent */
 733         set_irg_loopinfo_inconsistent(irg);
 734
 735         /* Calls might be removed. */
 736         set_trouts_inconsistent();
 737 }  /* apply */
 738
 739 /**
 740  * Create a partition for a given meet block.
 741  *
 742  * @param block  the meet block
 743  * @param env    the environment
 744  */
 745 static void partition_for_block(ir_node *block, environment_t *env) {
 746         partition_t *part = create_partition(block, env);
 747         int         i;
 748
 749         /* collect normal blocks */
 750         for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i) {
 751                 ir_node *pred = get_Block_cfgpred(block, i);
 752                 ir_node *block;
 753                 block_t *bl;
 754                 node_t  *node;
 755
 756                 mark_irn_visited(pred);
 757
 758                 block = get_nodes_block(pred);
 759                 bl    = create_block(block, part, env);
 760                 node  = create_node(pred, bl, env);
 761
 762                 node->next = bl->roots;
 763                 bl->roots  = node;
 764         }
 765
 766         if (block == get_irg_end_block(current_ir_graph)) {
 767                 /* collect all no-return blocks */
 768                 ir_node *end = get_irg_end(current_ir_graph);
 769                 for (i = get_End_n_keepalives(end) - 1; i >= 0; --i) {
 770                         ir_node *ka    = get_End_keepalive(end, i);
 771                         ir_node *block;
 772                         block_t *bl;
 773                         node_t  *node;
 774
 775                         if (! is_Call(ka))
 776                                 continue;
 777                         mark_irn_visited(ka);
 778
 779                         /* found one */
 780                         block = get_nodes_block(ka);
 781                         bl    = create_block(block, part, env);
 782                         node  = create_node(ka, bl, env);
 783
 784                         node->next = bl->roots;
 785                         bl->roots  = node;
 786                 }
 787         }
 788
 789         dump_partition("Created", part);
 790 }  /* partition for block */
 791
 792 /* Combines congruent end blocks into one. */
 793 int melt_end_blocks(ir_graph *irg) {
 794         ir_graph      *rem;
 795         ir_node       *end_block;
 796         environment_t env;
 797         partition_t   *part;
 798         int           res;
 799
 800         rem = current_ir_graph;
 801         current_ir_graph = irg;
 802
 803         /* register a debug mask */
 804         FIRM_DBG_REGISTER(dbg, "firm.opt.blocks");
 805
 806         DEBUG_ONLY(part_nr = 0);
 807         DB((dbg, LEVEL_1, "Shaping blocks for %+F\n", irg));
 808
 809         /* works better, when returns are placed at the end of the blocks */
 810         normalize_n_returns(irg);
 811
 812         ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
 813         inc_irg_visited(irg);
 814
 815         obstack_init(&env.obst);
 816         INIT_LIST_HEAD(&env.partitions);
 817         INIT_LIST_HEAD(&env.ready);
 818         env.opcode2id_map  = new_set(cmp_opcode, iro_Last * 4);
 819
 820         end_block = get_irg_end_block(irg);
 821         partition_for_block(end_block, &env);
 822         while (! list_empty(&env.partitions))
 823                 propagate(&env);
 824
 825         res = !list_empty(&env.ready);
 826
 827         list_for_each_entry(partition_t, part, &env.ready, part_list) {
 828                 dump_partition("Ready Partition", part);
 829                 apply(irg, part);
 830         }
 831         ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
 832         del_set(env.opcode2id_map);
 833         obstack_free(&env.obst, NULL);
 834         current_ir_graph = rem;
 835
 836         return res;
 837 }  /* melt_end_blocks */