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