2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
22 * @brief Combining congruent blocks
23 * @author Michael Beck
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.
32 #include "iroptimize.h"
33 #include "irgraph_t.h"
40 typedef struct partition_t partition_t;
41 typedef struct block_t block_t;
42 typedef struct node_t node_t;
43 typedef struct pair_t pair_t;
44 typedef struct phi_t phi_t;
45 typedef struct opcode_key_t opcode_key_t;
46 typedef struct listmap_entry_t listmap_entry_t;
47 typedef struct environment_t environment_t;
49 /** An opcode map key. */
51 ir_opcode code; /**< The Firm opcode. */
52 ir_mode *mode; /**< The mode of all nodes in the partition. */
53 int arity; /**< The arity of this opcode (needed for Phi etc. */
55 long proj; /**< For Proj nodes, its proj number */
56 ir_entity *ent; /**< For Sel Nodes, its entity */
60 /** A partition contains all congruent blocks. */
62 list_head part_list; /**< Double linked list of partitions. */
63 list_head blocks; /**< List of blocks in this partition. */
64 unsigned n_blocks; /**< Number of block in this partition. */
65 ir_node *meet_block; /**< The control flow meet block of this partition. */
67 unsigned nr; /**< For debugging: number of this partition. */
73 list_head block_list; /**< Double linked list of block inside a partition. */
74 list_head nodes; /**< Wait-queue of nodes that must be checked for congruence. */
75 block_t *next; /**< Next block of a split list. */
76 ir_node *block; /**< Pointer to the associated IR-node block. */
77 node_t *roots; /**< The list of all root nodes. */
78 pair_t *input_pairs; /**< The list of inputs to this block. */
79 phi_t *phis; /**< The list of Phis in this block. */
84 list_head node_list; /**< Double linked list of block inside a partition. */
85 ir_node *node; /**< Pointer to the associated IR-node or NULL for block inputs. */
86 node_t *next; /**< Link to the next node in the root set. */
87 char is_input; /**< Set if this node is an input from other block. */
90 /** The environment. */
91 struct environment_t {
92 list_head partitions; /**< list of partitions. */
93 list_head ready; /**< list of ready partitions. */
94 set *opcode2id_map; /**< The opcodeMode->id map. */
95 struct obstack obst; /** obstack for temporary data */
98 /** A node, input index pair. */
100 pair_t *next; /**< Points to the next pair entry. */
101 ir_node *irn; /**< The IR-node. */
102 int index; /**< An input index. */
103 ir_node **ins; /**< A new in array once allocated. */
106 /** A Phi, inputs pair. */
108 phi_t *next; /**< Points to the next Phi pair entry. */
109 ir_node *phi; /**< The Phi node. */
110 ir_node **ins; /**< A new in array once allocated. */
114 * An entry in the list_map.
116 struct listmap_entry_t {
117 void *id; /**< The id. */
118 block_t *list; /**< The associated list for this id. */
119 listmap_entry_t *next; /**< Link to the next entry in the map. */
122 /** We must map id's to lists. */
123 typedef struct listmap_t {
124 set *map; /**< Map id's to listmap_entry_t's */
125 listmap_entry_t *values; /**< List of all values in the map. */
128 /** The debug module handle. */
129 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
131 /** Next partition number. */
132 DEBUG_ONLY(static unsigned part_nr = 0);
136 * Dump partition to output.
138 static void dump_partition(const char *msg, const partition_t *part) {
139 const block_t *block;
142 DB((dbg, LEVEL_2, " %s part%u (%u blocks) {\n ", msg, part->nr, part->n_blocks));
143 list_for_each_entry(block_t, block, &part->blocks, block_list) {
144 DB((dbg, LEVEL_2, "%s%+F", first ? "" : ", ", block->block));
147 DB((dbg, LEVEL_2, "\n }\n"));
148 } /* dump_partition */
153 static void dump_list(const char *msg, const block_t *block) {
157 DB((dbg, LEVEL_3, " %s = {\n ", msg));
158 for (p = block; p != NULL; p = p->next) {
159 DB((dbg, LEVEL_3, "%s%+F", first ? "" : ", ", p->block));
162 DB((dbg, LEVEL_3, "\n }\n"));
165 #define dump_partition(msg, part)
166 #define dump_list(msg, block)
170 * Compare two pointer values of a listmap.
172 static int listmap_cmp_ptr(const void *elt, const void *key, size_t size) {
173 const listmap_entry_t *e1 = elt;
174 const listmap_entry_t *e2 = key;
177 return e1->id != e2->id;
178 } /* listmap_cmp_ptr */
181 * Initializes a listmap.
183 * @param map the listmap
185 static void listmap_init(listmap_t *map) {
186 map->map = new_set(listmap_cmp_ptr, 16);
191 * Terminates a listmap.
193 * @param map the listmap
195 static void listmap_term(listmap_t *map) {
200 * Return the associated listmap entry for a given id.
202 * @param map the listmap
203 * @param id the id to search for
205 * @return the associated listmap entry for the given id
207 static listmap_entry_t *listmap_find(listmap_t *map, void *id) {
208 listmap_entry_t key, *entry;
213 entry = set_insert(map->map, &key, sizeof(key), HASH_PTR(id));
215 if (entry->list == NULL) {
216 /* a new entry, put into the list */
217 entry->next = map->values;
224 * Calculate the hash value for an opcode map entry.
226 * @param entry an opcode map entry
228 * @return a hash value for the given opcode map entry
230 static unsigned opcode_hash(const opcode_key_t *entry) {
231 return (entry->mode - (ir_mode *)0) * 9 + entry->code + entry->u.proj * 3 + HASH_PTR(entry->u.ent) + entry->arity;
235 * Compare two entries in the opcode map.
237 static int cmp_opcode(const void *elt, const void *key, size_t size) {
238 const opcode_key_t *o1 = elt;
239 const opcode_key_t *o2 = key;
242 return o1->code != o2->code || o1->mode != o2->mode ||
243 o1->arity != o2->arity ||
244 o1->u.proj != o2->u.proj || o1->u.ent != o2->u.ent;
248 * Creates a new empty partition and put in on the
251 * @param meet_block the control flow meet block of thi partition
252 * @param env the environment
254 static partition_t *create_partition(ir_node *meet_block, environment_t *env) {
255 partition_t *part = obstack_alloc(&env->obst, sizeof(*part));
257 INIT_LIST_HEAD(&part->blocks);
258 part->meet_block = meet_block;
260 DEBUG_ONLY(part->nr = part_nr++);
261 list_add_tail(&part->part_list, &env->partitions);
263 } /* create_partition */
266 * Allocate a new block in the given partition.
268 * @param block the IR-node
269 * @param partition the partition to add to
270 * @param env the environment
272 static block_t *create_block(ir_node *block, partition_t *partition, environment_t *env) {
273 block_t *bl = obstack_alloc(&env->obst, sizeof(*bl));
275 INIT_LIST_HEAD(&bl->nodes);
279 bl->input_pairs = NULL;
282 list_add_tail(&bl->block_list, &partition->blocks);
283 ++partition->n_blocks;
289 * Allocate a new node and add it to a blocks wait queue.
291 * @param irn the IR-node
292 * @param block the block to add to
293 * @param env the environment
295 static node_t *create_node(ir_node *irn, block_t *block, environment_t *env) {
296 node_t *node = obstack_alloc(&env->obst, sizeof(*node));
302 list_add_tail(&node->node_list, &block->nodes);
308 * Add an input pair to a block.
310 * @param block the block
311 * @param irn the IR-node that has an block input
312 * @param idx the index of the block input in node's predecessors
313 * @param env the environment
315 static void add_pair(block_t *block, ir_node *irn, int idx, environment_t *env) {
316 pair_t *pair = obstack_alloc(&env->obst, sizeof(*pair));
318 pair->next = block->input_pairs;
323 block->input_pairs = pair;
327 * Add a Phi to a block.
329 * @param block the block
330 * @param phi the Phi node
331 * @param env the environment
333 static void add_phi(block_t *block, ir_node *phi, environment_t *env) {
334 phi_t *node = obstack_alloc(&env->obst, sizeof(*node));
336 node->next = block->phis;
344 * Creates an opcode from a node.
346 static opcode_key_t *opcode(const node_t *node, environment_t *env) {
347 opcode_key_t key, *entry;
348 ir_node *irn = node->node;
350 if (node->is_input) {
351 /* Node: as Block nodes are never propagated, it is safe to
352 use its code for "input" node */
353 key.code = iro_Block;
356 key.code = get_irn_opcode(irn);
357 key.arity = get_irn_arity(irn);
359 key.mode = get_irn_mode(node->node);
365 key.u.proj = get_Proj_proj(irn);
368 key.u.ent = get_Sel_entity(irn);
374 entry = set_insert(env->opcode2id_map, &key, sizeof(key), opcode_hash(&key));
379 * Split a partition by a local list.
381 * @param Z partition to split
382 * @param g a (non-empty) block list
383 * @param env the environment
385 * @return a new partition containing the nodes of g
387 static partition_t *split(partition_t *Z, block_t *g, environment_t *env) {
388 partition_t *Z_prime;
392 dump_partition("Splitting ", Z);
393 dump_list("by list ", g);
397 /* Remove g from Z. */
398 for (block = g; block != NULL; block = block->next) {
399 list_del(&block->block_list);
402 assert(n < Z->n_blocks);
405 /* Move g to a new partition, Z'. */
406 Z_prime = create_partition(Z->meet_block, env);
407 for (block = g; block != NULL; block = block->next) {
408 list_add_tail(&block->block_list, &Z_prime->blocks);
410 Z_prime->n_blocks = n;
412 dump_partition("Now ", Z);
413 dump_partition("Created new ", Z_prime);
418 * Propagate nodes on all wait queues of the given partition.
420 * @param part the partition
421 * @param env the environment
423 void propagate_blocks(partition_t *part, environment_t *env) {
424 block_t *ready_blocks = NULL;
425 unsigned n_ready = 0;
428 listmap_entry_t *iter;
430 DB((dbg, LEVEL_2, " Propagate blocks on part%u\n", part->nr));
432 /* Let map be an empty mapping from the range of Opcodes to (local) list of Nodes. */
434 list_for_each_entry_safe(block_t, bl, next, &part->blocks, block_list) {
436 listmap_entry_t *entry;
439 if (list_empty(&bl->nodes)) {
440 bl->next = ready_blocks;
443 DB((dbg, LEVEL_2, " Block %+F completely processed\n", bl->block));
447 /* get the first node from the wait queue */
448 node = list_entry(bl->nodes.next, node_t, node_list);
449 list_del(&node->node_list);
451 /* put all not-visited predecessors to the wait queue */
452 if (! node->is_input) {
453 ir_node *irn = node->node;
456 DB((dbg, LEVEL_3, " propagate %+F\n", irn));
457 ir_normalize_node(node->node);
458 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
459 ir_node *pred = get_irn_n(irn, i);
460 ir_node *block = get_nodes_block(skip_Proj(pred));
463 if (block != bl->block) {
464 p_node = create_node(pred, bl, env);
465 /* do not threat Constants like live-ins */
466 if (! is_irn_constlike(irn)) {
467 p_node->is_input = 1;
469 add_pair(bl, irn, i, env);
471 } else if (! irn_visited_else_mark(pred)) {
472 /* not yet visited, ok */
473 p_node = create_node(pred, bl, env);
476 /* update the Phi list */
477 add_phi(bl, pred, env);
482 DB((dbg, LEVEL_3, " propagate Input %+F\n", node->node));
485 /* Add bl to map[opcode(bl)]. */
486 id = opcode(node, env);
487 entry = listmap_find(&map, id);
488 bl->next = entry->list;
492 /* split out ready blocks */
496 if (n_ready < part->n_blocks)
497 Z = split(part, ready_blocks, env);
500 list_del(&Z->part_list);
502 if (Z->n_blocks > 1) {
503 DB((dbg, LEVEL_2, " Partition %u is ready\n", Z->nr));
504 list_add(&Z->part_list, &env->ready);
506 DB((dbg, LEVEL_2, " Partition %u contains only one block, killed\n", Z->nr));
510 /* for all sets S except one in the range of map do */
511 for (iter = map.values; iter != NULL; iter = iter->next) {
514 if (iter->next == NULL) {
515 /* this is the last entry, ignore */
520 /* Add SPLIT( X, S ) to P. */
524 } /* propagate_blocks */
527 * Propagate nodes on all wait queues.
529 * @param env the environment
531 void propagate(environment_t *env) {
532 partition_t *part, *next;
534 list_for_each_entry_safe(partition_t, part, next, &env->partitions, part_list) {
535 if (part->n_blocks < 2) {
536 /* zero or one block left, kill this partition */
537 list_del(&part->part_list);
538 DB((dbg, LEVEL_2, " Partition %u contains less than 2 blocks, killed\n", part->nr));
540 propagate_blocks(part, env);
545 * Apply analysis results by replacing all blocks of a partition
546 * by one representative.
548 * Route all inputs from all block of the partition to the one
550 * Enhance all existing Phis by combining them.
551 * Create new Phis for all previous input nodes.
553 * @param part the partition to process
555 static void apply(ir_graph *irg, partition_t *part) {
556 block_t *repr = list_entry(part->blocks.next, block_t, block_list);
558 ir_node *block, *end, *end_block;
560 phi_t *repr_phi, *phi;
561 pair_t *repr_pair, *pair;
562 int i, j, n, block_nr;
564 list_del(&repr->block_list);
566 /* prepare new in arrays for the block ... */
568 n = get_Block_n_cfgpreds(block);
569 ins = NEW_ARR_F(ir_node *, n);
571 for (i = 0; i < n; ++i) {
572 ins[i] = get_Block_cfgpred(block, i);
575 /* ... for all existing Phis ... */
576 for (repr_phi = repr->phis; repr_phi != NULL; repr_phi = repr_phi->next) {
577 repr_phi->ins = NEW_ARR_F(ir_node *, n);
579 for (i = 0; i < n; ++i)
580 repr_phi->ins[i] = get_Phi_pred(repr_phi->phi, i);
583 /* ... and all newly created Phis */
584 for (repr_pair = repr->input_pairs; repr_pair != NULL; repr_pair = repr_pair->next) {
585 ir_node *input = get_irn_n(repr_pair->irn, repr_pair->index);
587 repr_pair->ins = NEW_ARR_F(ir_node *, n);
588 for (i = 0; i < n; ++i)
589 repr_pair->ins[i] = input;
592 DB((dbg, LEVEL_1, "Replacing "));
594 /* collect new in arrays */
595 end = get_irg_end(irg);
597 list_for_each_entry(block_t, bl, &part->blocks, block_list) {
601 DB((dbg, LEVEL_1, "%+F, ", block));
603 /* first step: kill any keep-alive from this block */
604 for (i = get_End_n_keepalives(end) - 1; i >= 0; --i) {
605 ir_node *ka = get_End_keepalive(end, i);
609 remove_End_keepalive(end, ka);
611 if (get_nodes_block(ka) == block)
612 remove_End_keepalive(end, ka);
616 /* second step: update control flow */
617 n = get_Block_n_cfgpreds(block);
618 for (i = 0; i < n; ++i) {
619 ir_node *pred = get_Block_cfgpred(block, i);
620 ARR_APP1(ir_node *, ins, pred);
623 /* third step: update Phis */
624 for (repr_phi = repr->phis, phi = bl->phis;
626 repr_phi = repr_phi->next, phi = phi->next) {
627 for (i = 0; i < n; ++i) {
628 ir_node *pred = get_Phi_pred(phi->phi, i);
629 ARR_APP1(ir_node *, repr_phi->ins, pred);
633 /* fourth step: update inputs for new Phis */
634 for (repr_pair = repr->input_pairs, pair = bl->input_pairs;
636 repr_pair = repr_pair->next, pair = pair->next) {
637 ir_node *input = get_irn_n(pair->irn, pair->index);
639 for (i = 0; i < n; ++i)
640 ARR_APP1(ir_node *, repr_pair->ins, input);
644 DB((dbg, LEVEL_1, "by %+F\n", repr->block));
646 /* rewire block input ... */
650 * Some problem here. For:
651 * if (x) y = 1; else y = 2;
653 * the following code is constructed:
655 * b0: if (x) goto b1; else goto b1;
658 * However, both predecessors of b1 are b0, making the Phi
661 * We solve this by fixing critical edges.
663 for (i = 0; i < n; ++i) {
664 ir_node *pred = ins[i];
670 cfop = get_irn_op(skip_Proj(pred));
671 if (is_op_fragile(cfop)) {
672 /* ignore exception flow */
675 if (is_op_forking(cfop)) {
676 /* a critical edge */
677 ir_node *block = new_r_Block(irg, 1, &ins[i]);
678 ir_node *jmp = new_r_Jmp(irg, block);
684 set_irn_in(block, n, ins);
687 /* ... existing Phis ... */
688 for (repr_phi = repr->phis; repr_phi != NULL; repr_phi = repr_phi->next) {
689 set_irn_in(repr_phi->phi, n, repr_phi->ins);
690 DEL_ARR_F(repr_phi->ins);
693 /* ... and all inputs by creating new Phis ... */
694 for (repr_pair = repr->input_pairs; repr_pair != NULL; repr_pair = repr_pair->next) {
695 ir_node *input = get_irn_n(repr_pair->irn, repr_pair->index);
696 ir_mode *mode = get_irn_mode(input);
697 ir_node *phi = new_r_Phi(current_ir_graph, block, n, repr_pair->ins, mode);
699 set_irn_n(repr_pair->irn, repr_pair->index, phi);
700 DEL_ARR_F(repr_pair->ins);
703 /* ... finally rewire the end block */
704 end_block = get_irg_end_block(irg);
705 n = get_Block_n_cfgpreds(end_block);
707 ins = NEW_ARR_F(ir_node *, n);
709 for (i = j = 0; i < n; ++i) {
710 ir_node *out = get_Block_cfgpred(end_block, i);
712 list_for_each_entry(block_t, bl, &part->blocks, block_list) {
715 for (root = bl->roots; root != NULL; root = root->next) {
716 if (root->node == out)
725 set_irn_in(end_block, j, ins);
728 /* control flow changed */
729 set_irg_outs_inconsistent(irg);
730 set_irg_extblk_inconsistent(irg);
731 set_irg_doms_inconsistent(irg);
732 /* Hmm, only the root loop is inconsistent */
733 set_irg_loopinfo_inconsistent(irg);
735 /* Calls might be removed. */
736 set_trouts_inconsistent();
740 * Create a partition for a given meet block.
742 * @param block the meet block
743 * @param env the environment
745 static void partition_for_block(ir_node *block, environment_t *env) {
746 partition_t *part = create_partition(block, env);
749 /* collect normal blocks */
750 for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i) {
751 ir_node *pred = get_Block_cfgpred(block, i);
756 mark_irn_visited(pred);
758 block = get_nodes_block(pred);
759 bl = create_block(block, part, env);
760 node = create_node(pred, bl, env);
762 node->next = bl->roots;
766 if (block == get_irg_end_block(current_ir_graph)) {
767 /* collect all no-return blocks */
768 ir_node *end = get_irg_end(current_ir_graph);
769 for (i = get_End_n_keepalives(end) - 1; i >= 0; --i) {
770 ir_node *ka = get_End_keepalive(end, i);
777 mark_irn_visited(ka);
780 block = get_nodes_block(ka);
781 bl = create_block(block, part, env);
782 node = create_node(ka, bl, env);
784 node->next = bl->roots;
789 dump_partition("Created", part);
790 } /* partition for block */
792 /* Combines congruent end blocks into one. */
793 int melt_end_blocks(ir_graph *irg) {
800 rem = current_ir_graph;
801 current_ir_graph = irg;
803 /* register a debug mask */
804 FIRM_DBG_REGISTER(dbg, "firm.opt.blocks");
806 DEBUG_ONLY(part_nr = 0);
807 DB((dbg, LEVEL_1, "Shaping blocks for %+F\n", irg));
809 /* works better, when returns are placed at the end of the blocks */
810 normalize_n_returns(irg);
812 ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
813 inc_irg_visited(irg);
815 obstack_init(&env.obst);
816 INIT_LIST_HEAD(&env.partitions);
817 INIT_LIST_HEAD(&env.ready);
818 env.opcode2id_map = new_set(cmp_opcode, iro_Last * 4);
820 end_block = get_irg_end_block(irg);
821 partition_for_block(end_block, &env);
822 while (! list_empty(&env.partitions))
825 res = !list_empty(&env.ready);
827 list_for_each_entry(partition_t, part, &env.ready, part_list) {
828 dump_partition("Ready Partition", part);
831 ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
832 del_set(env.opcode2id_map);
833 obstack_free(&env.obst, NULL);
834 current_ir_graph = rem;
837 } /* melt_end_blocks */