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

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