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

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