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

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