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