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

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