2 * Copyright (C) 1995-2011 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.
27 * Two block are congruent, if they contains only equal calculations.
31 #include "iroptimize.h"
34 #include "irgraph_t.h"
45 /* define this for general block shaping: congruent blocks
46 are found not only before the end block but anywhere in the graph */
49 typedef struct partition_t partition_t;
50 typedef struct block_t block_t;
51 typedef struct node_t node_t;
52 typedef struct pair_t pair_t;
53 typedef struct phi_t phi_t;
54 typedef struct opcode_key_t opcode_key_t;
55 typedef struct listmap_entry_t listmap_entry_t;
56 typedef struct environment_t environment_t;
57 typedef struct pred_t pred_t;
59 /** An opcode map key. */
61 unsigned code; /**< The Firm opcode. */
62 ir_mode *mode; /**< The mode of all nodes in the partition. */
63 int arity; /**< The arity of this opcode (needed for Phi etc. */
65 long proj; /**< For Proj nodes, its proj number */
66 ir_entity *ent; /**< For Sel nodes, its entity */
67 ir_tarval *tv; /**< For Const nodes, its tarval */
68 symconst_symbol sym; /**< For SymConst nodes, its symbol .*/
69 void *addr; /**< Alias all addresses. */
70 int intVal; /**< For Conv/Div nodes: strict/remainderless. */
74 /** A partition contains all congruent blocks. */
76 list_head part_list; /**< Double linked list of partitions. */
77 list_head blocks; /**< List of blocks in this partition. */
78 unsigned n_blocks; /**< Number of block in this partition. */
79 ir_node *meet_block; /**< The control flow meet block of this partition. */
81 unsigned nr; /**< For debugging: number of this partition. */
87 list_head block_list; /**< Double linked list of block inside a partition. */
88 list_head nodes; /**< Wait-queue of nodes that must be checked for congruence. */
89 block_t *next; /**< Next block of a split list. */
90 ir_node *block; /**< Pointer to the associated IR-node block. */
91 ir_node **roots; /**< An array of all root nodes. */
92 node_t *cf_root; /**< The control flow root node of this block. */
93 pair_t *input_pairs; /**< The list of inputs to this block. */
94 phi_t *phis; /**< The list of Phis in this block. */
95 block_t *all_next; /**< Links all created blocks. */
96 int meet_input; /**< Input number of this block in the meet-block. */
101 list_head node_list; /**< Double linked list of block inside a partition. */
102 ir_node *node; /**< Pointer to the associated IR-node or NULL for block inputs. */
103 char is_input; /**< Set if this node is an input from other block. */
106 /** The environment. */
107 struct environment_t {
108 list_head partitions; /**< list of partitions. */
109 list_head ready; /**< list of ready partitions. */
110 set *opcode2id_map; /**< The opcodeMode->id map. */
111 ir_node **live_outs; /**< Live out only nodes. */
112 block_t *all_blocks; /**< List of all created blocks. */
113 struct obstack obst; /** obstack for temporary data */
116 /** A (node, input index) pair. */
118 pair_t *next; /**< Points to the next pair entry. */
119 ir_node *irn; /**< The IR-node. */
120 int index; /**< An input index. */
121 ir_node **ins; /**< A new in array once allocated. */
124 /** A Phi, inputs pair. */
126 phi_t *next; /**< Points to the next Phi pair entry. */
127 ir_node *phi; /**< The Phi node. */
128 ir_node **ins; /**< A new in array once allocated. */
131 /** Describes a predecessor input. */
133 ir_node *pred; /**< The predecessor. */
134 int index; /**< Its input index. */
138 * An entry in the list_map.
140 struct listmap_entry_t {
141 void *id; /**< The id. */
142 block_t *list; /**< The associated list for this id. */
143 listmap_entry_t *next; /**< Link to the next entry in the map. */
146 /** We must map id's to lists. */
147 typedef struct listmap_t {
148 set *map; /**< Map id's to listmap_entry_t's */
149 listmap_entry_t *values; /**< List of all values in the map. */
152 #define get_Block_entry(block) ((block_t *)get_irn_link(block))
154 /** The debug module handle. */
155 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
157 /** Next partition number. */
158 DEBUG_ONLY(static unsigned part_nr = 0);
162 * Dump partition to output.
164 static void dump_partition(const char *msg, const partition_t *part)
166 const block_t *block;
169 DB((dbg, LEVEL_2, " %s part%u (%u blocks) {\n ", msg, part->nr, part->n_blocks));
170 list_for_each_entry(block_t, block, &part->blocks, block_list) {
171 DB((dbg, LEVEL_2, "%s%+F", first ? "" : ", ", block->block));
174 DB((dbg, LEVEL_2, "\n }\n"));
175 } /* dump_partition */
180 static void dump_list(const char *msg, const block_t *block)
185 DB((dbg, LEVEL_3, " %s = {\n ", msg));
186 for (p = block; p != NULL; p = p->next) {
187 DB((dbg, LEVEL_3, "%s%+F", first ? "" : ", ", p->block));
190 DB((dbg, LEVEL_3, "\n }\n"));
193 #define dump_partition(msg, part)
194 #define dump_list(msg, block)
198 * Compare two pointer values of a listmap.
200 static int listmap_cmp_ptr(const void *elt, const void *key, size_t size)
202 const listmap_entry_t *e1 = (const listmap_entry_t*)elt;
203 const listmap_entry_t *e2 = (const listmap_entry_t*)key;
206 return e1->id != e2->id;
207 } /* listmap_cmp_ptr */
210 * Initializes a listmap.
212 * @param map the listmap
214 static void listmap_init(listmap_t *map)
216 map->map = new_set(listmap_cmp_ptr, 16);
221 * Terminates a listmap.
223 * @param map the listmap
225 static void listmap_term(listmap_t *map)
231 * Return the associated listmap entry for a given id.
233 * @param map the listmap
234 * @param id the id to search for
236 * @return the associated listmap entry for the given id
238 static listmap_entry_t *listmap_find(listmap_t *map, void *id)
240 listmap_entry_t key, *entry;
245 entry = (listmap_entry_t*)set_insert(map->map, &key, sizeof(key), HASH_PTR(id));
247 if (entry->list == NULL) {
248 /* a new entry, put into the list */
249 entry->next = map->values;
256 * Calculate the hash value for an opcode map entry.
258 * @param entry an opcode map entry
260 * @return a hash value for the given opcode map entry
262 static unsigned opcode_hash(const opcode_key_t *entry)
264 /* assume long >= int */
265 return (unsigned)(PTR_TO_INT(entry->mode) * 9 + entry->code + entry->u.proj * 3 + HASH_PTR(entry->u.addr) + entry->arity);
269 * Compare two entries in the opcode map.
271 static int cmp_opcode(const void *elt, const void *key, size_t size)
273 const opcode_key_t *o1 = (opcode_key_t*)elt;
274 const opcode_key_t *o2 = (opcode_key_t*)key;
277 return o1->code != o2->code || o1->mode != o2->mode ||
278 o1->arity != o2->arity ||
279 o1->u.proj != o2->u.proj || o1->u.addr != o2->u.addr;
283 * Creates a new empty partition and put in on the
286 * @param meet_block the control flow meet block of this partition
287 * @param env the environment
289 static partition_t *create_partition(ir_node *meet_block, environment_t *env)
291 partition_t *part = OALLOC(&env->obst, partition_t);
293 INIT_LIST_HEAD(&part->blocks);
294 part->meet_block = meet_block;
296 DEBUG_ONLY(part->nr = part_nr++);
297 list_add_tail(&part->part_list, &env->partitions);
299 } /* create_partition */
302 * Allocate a new block in the given partition.
304 * @param block the IR-node
305 * @param meet_input Input number of this block in the meet-block
306 * @param partition the partition to add to
307 * @param env the environment
309 static block_t *create_block(ir_node *block, int meet_input, partition_t *partition, environment_t *env)
311 block_t *bl = OALLOC(&env->obst, block_t);
313 set_irn_link(block, bl);
315 INIT_LIST_HEAD(&bl->nodes);
318 bl->roots = NEW_ARR_F(ir_node *, 0);
320 bl->input_pairs = NULL;
322 bl->meet_input = meet_input;
324 /* put it into the list of partition blocks */
325 list_add_tail(&bl->block_list, &partition->blocks);
326 ++partition->n_blocks;
328 /* put in into the list of all blocks */
329 bl->all_next = env->all_blocks;
330 env->all_blocks = bl;
336 * Allocate a new node and add it to a blocks wait queue.
338 * @param irn the IR-node
339 * @param block the block to add to
340 * @param env the environment
342 static node_t *create_node(ir_node *irn, block_t *block, environment_t *env)
344 node_t *node = OALLOC(&env->obst, node_t);
349 list_add_tail(&node->node_list, &block->nodes);
355 * Add an input pair to a block.
357 * @param block the block
358 * @param irn the IR-node that has an block input
359 * @param idx the index of the block input in node's predecessors
360 * @param env the environment
362 static void add_pair(block_t *block, ir_node *irn, int idx, environment_t *env)
364 pair_t *pair = OALLOC(&env->obst, pair_t);
366 pair->next = block->input_pairs;
371 block->input_pairs = pair;
375 * Add a Phi to a block.
377 * @param block the block
378 * @param phi the Phi node
379 * @param env the environment
381 static void add_phi(block_t *block, ir_node *phi, environment_t *env)
383 phi_t *node = OALLOC(&env->obst, phi_t);
385 node->next = block->phis;
393 * Creates an opcode from a node.
395 static opcode_key_t *opcode(const node_t *node, environment_t *env)
397 opcode_key_t key, *entry;
398 ir_node *irn = node->node;
400 if (node->is_input) {
401 /* Node: as Block nodes are never propagated, it is safe to
402 use its code for "input" node */
403 key.code = iro_Block;
406 key.code = get_irn_opcode(irn);
407 key.arity = get_irn_arity(irn);
409 key.mode = get_irn_mode(node->node);
415 key.u.proj = get_Proj_proj(irn);
418 key.u.ent = get_Sel_entity(irn);
421 key.u.sym = get_SymConst_symbol(irn);
424 key.u.tv = get_Const_tarval(irn);
427 key.u.intVal = get_Conv_strict(irn);
430 key.mode = get_Load_mode(irn);
433 key.u.intVal = get_Div_no_remainder(irn);
436 key.u.intVal = get_Builtin_kind(irn);
442 entry = (opcode_key_t*)set_insert(env->opcode2id_map, &key, sizeof(key), opcode_hash(&key));
447 * Split a partition by a local list.
449 * @param Z partition to split
450 * @param g a (non-empty) block list
451 * @param env the environment
453 * @return a new partition containing the nodes of g
455 static partition_t *split(partition_t *Z, block_t *g, environment_t *env)
457 partition_t *Z_prime;
461 dump_partition("Splitting ", Z);
462 dump_list("by list ", g);
466 /* Remove g from Z. */
467 for (block = g; block != NULL; block = block->next) {
468 list_del(&block->block_list);
471 assert(n < Z->n_blocks);
474 /* Move g to a new partition, Z'. */
475 Z_prime = create_partition(Z->meet_block, env);
476 for (block = g; block != NULL; block = block->next) {
477 list_add_tail(&block->block_list, &Z_prime->blocks);
479 Z_prime->n_blocks = n;
481 dump_partition("Now ", Z);
482 dump_partition("Created new ", Z_prime);
487 * Return non-zero if pred should be tread as a input node.
489 static int is_input_node(ir_node *pred, ir_node *irn, int index)
491 /* for now, do NOT turn direct calls into indirect one */
494 if (! is_SymConst_addr_ent(pred))
499 } /* is_input_node */
502 * Propagate nodes on all wait queues of the given partition.
504 * @param part the partition
505 * @param env the environment
507 static void propagate_blocks(partition_t *part, environment_t *env)
509 block_t *ready_blocks = NULL;
510 unsigned n_ready = 0;
513 listmap_entry_t *iter;
515 DB((dbg, LEVEL_2, " Propagate blocks on part%u\n", part->nr));
517 /* Let map be an empty mapping from the range of Opcodes to (local) list of blocks. */
519 list_for_each_entry_safe(block_t, bl, next, &part->blocks, block_list) {
521 listmap_entry_t *entry;
524 if (list_empty(&bl->nodes)) {
525 bl->next = ready_blocks;
528 DB((dbg, LEVEL_2, " Block %+F completely processed\n", bl->block));
532 /* get the first node from the wait queue */
533 node = list_entry(bl->nodes.next, node_t, node_list);
534 list_del(&node->node_list);
536 /* put all not-visited predecessors to the wait queue */
537 if (! node->is_input) {
538 ir_node *irn = node->node;
541 DB((dbg, LEVEL_3, " propagate %+F\n", irn));
542 ir_normalize_node(node->node);
543 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
544 ir_node *pred = get_irn_n(irn, i);
545 ir_node *block = get_nodes_block(skip_Proj(pred));
548 if (block != bl->block) {
549 p_node = create_node(pred, bl, env);
550 if (is_input_node(pred, irn, i)) {
551 /* is a block live input */
552 p_node->is_input = 1;
554 add_pair(bl, irn, i, env);
555 } else if (is_Phi(pred)) {
556 /* update the Phi list */
557 add_phi(bl, pred, env);
559 } else if (! irn_visited_else_mark(pred)) {
560 /* not yet visited, ok */
561 p_node = create_node(pred, bl, env);
564 /* update the Phi list */
565 add_phi(bl, pred, env);
570 DB((dbg, LEVEL_3, " propagate Input %+F\n", node->node));
573 /* Add bl to map[opcode(n)]. */
574 id = opcode(node, env);
575 entry = listmap_find(&map, id);
576 bl->next = entry->list;
580 /* split out ready blocks */
584 if (n_ready < part->n_blocks)
585 Z = split(part, ready_blocks, env);
588 list_del(&Z->part_list);
590 if (Z->n_blocks > 1) {
591 DB((dbg, LEVEL_2, " Partition %u is ready\n", Z->nr));
592 list_add(&Z->part_list, &env->ready);
594 DB((dbg, LEVEL_2, " Partition %u contains only one block, killed\n", Z->nr));
598 /* for all sets S except one in the range of map do */
599 for (iter = map.values; iter != NULL; iter = iter->next) {
602 if (iter->next == NULL) {
603 /* this is the last entry, ignore */
608 /* Add SPLIT( X, S ) to P. */
612 } /* propagate_blocks */
615 * Propagate nodes on all wait queues.
617 * @param env the environment
619 static void propagate(environment_t *env)
621 partition_t *part, *next;
623 list_for_each_entry_safe(partition_t, part, next, &env->partitions, part_list) {
624 if (part->n_blocks < 2) {
625 /* zero or one block left, kill this partition */
626 list_del(&part->part_list);
627 DB((dbg, LEVEL_2, " Partition %u contains less than 2 blocks, killed\n", part->nr));
629 propagate_blocks(part, env);
634 * Map a block to the phi[block->input] live-trough.
636 static void *live_throughs(const block_t *bl, const ir_node *phi)
638 ir_node *input = get_Phi_pred(phi, bl->meet_input);
640 /* If this input is inside our block, this
641 is a live-out and not a live trough.
642 Live-outs are tested inside propagate, so map all of
643 them to the "general" value NULL */
644 if (get_nodes_block(input) == bl->block)
647 } /* live_throughs */
650 * Split partition by live-outs and live-troughs.
652 * @param part the partition
653 * @param env the environment
655 static void propagate_blocks_live_troughs(partition_t *part, environment_t *env)
657 const ir_node *meet_block = part->meet_block;
660 listmap_entry_t *iter;
663 DB((dbg, LEVEL_2, " Propagate live-troughs on part%u\n", part->nr));
665 for (phi = get_Block_phis(meet_block); phi != NULL; phi = get_Phi_next(phi)) {
666 /* propagate on all Phis of the meet-block */
668 if (part->n_blocks < 2) {
669 /* zero or one block left, kill this partition */
670 list_del(&part->part_list);
671 DB((dbg, LEVEL_2, " Partition %u contains less than 2 blocks, killed\n", part->nr));
675 /* Let map be an empty mapping from the range of live-troughs to (local) list of blocks. */
677 list_for_each_entry_safe(block_t, bl, next, &part->blocks, block_list) {
679 listmap_entry_t *entry;
681 /* Add bl to map[live_trough(bl)]. */
682 id = (opcode_key_t*)live_throughs(bl, phi);
683 entry = listmap_find(&map, id);
684 bl->next = entry->list;
688 /* for all sets S except one in the range of map do */
689 for (iter = map.values; iter != NULL; iter = iter->next) {
692 if (iter->next == NULL) {
693 /* this is the last entry, ignore */
698 /* Add SPLIT( X, S ) to P. */
703 } /* propagate_blocks_live_troughs */
706 * Propagate live-troughs on all partitions on the partition list.
708 * @param env the environment
710 static void propagate_live_troughs(environment_t *env)
712 partition_t *part, *next;
714 list_for_each_entry_safe(partition_t, part, next, &env->partitions, part_list) {
715 propagate_blocks_live_troughs(part, env);
717 } /* propagate_live_troughs */
720 * Apply analysis results by replacing all blocks of a partition
721 * by one representative.
723 * Route all inputs from all block of the partition to the one
725 * Enhance all existing Phis by combining them.
726 * Create new Phis for all previous input nodes.
728 * @param part the partition to process
730 static void apply(ir_graph *irg, partition_t *part)
732 block_t *repr = list_entry(part->blocks.next, block_t, block_list);
734 ir_node *block, *end, *meet_block, *p, *next;
735 ir_node **ins, **phi_ins;
736 phi_t *repr_phi, *phi;
737 pair_t *repr_pair, *pair;
738 int i, j, k, n, block_nr, n_phis;
740 list_del(&repr->block_list);
742 /* prepare new in arrays for the block ... */
744 n = get_Block_n_cfgpreds(block);
745 ins = NEW_ARR_F(ir_node *, n);
747 for (i = 0; i < n; ++i) {
748 ins[i] = get_Block_cfgpred(block, i);
751 /* ... for all existing Phis ... */
752 for (repr_phi = repr->phis; repr_phi != NULL; repr_phi = repr_phi->next) {
753 repr_phi->ins = NEW_ARR_F(ir_node *, n);
755 for (i = 0; i < n; ++i)
756 repr_phi->ins[i] = get_Phi_pred(repr_phi->phi, i);
759 /* ... and all newly created Phis */
760 for (repr_pair = repr->input_pairs; repr_pair != NULL; repr_pair = repr_pair->next) {
761 ir_node *input = get_irn_n(repr_pair->irn, repr_pair->index);
763 repr_pair->ins = NEW_ARR_F(ir_node *, n);
764 for (i = 0; i < n; ++i)
765 repr_pair->ins[i] = input;
768 DB((dbg, LEVEL_1, "Replacing "));
770 /* collect new in arrays */
771 end = get_irg_end(irg);
773 list_for_each_entry(block_t, bl, &part->blocks, block_list) {
777 DB((dbg, LEVEL_1, "%+F, ", block));
779 /* first step: kill any keep-alive from this block */
780 for (i = get_End_n_keepalives(end) - 1; i >= 0; --i) {
781 ir_node *ka = get_End_keepalive(end, i);
785 remove_End_keepalive(end, ka);
787 if (get_nodes_block(ka) == block)
788 remove_End_keepalive(end, ka);
792 /* second step: update control flow */
793 n = get_Block_n_cfgpreds(block);
794 for (i = 0; i < n; ++i) {
795 ir_node *pred = get_Block_cfgpred(block, i);
796 ARR_APP1(ir_node *, ins, pred);
799 /* third step: update Phis */
800 for (repr_phi = repr->phis, phi = bl->phis;
802 repr_phi = repr_phi->next, phi = phi->next) {
803 for (i = 0; i < n; ++i) {
804 ir_node *pred = get_Phi_pred(phi->phi, i);
805 ARR_APP1(ir_node *, repr_phi->ins, pred);
809 /* fourth step: update inputs for new Phis */
810 for (repr_pair = repr->input_pairs, pair = bl->input_pairs;
812 repr_pair = repr_pair->next, pair = pair->next) {
813 ir_node *input = get_irn_n(pair->irn, pair->index);
815 for (i = 0; i < n; ++i)
816 ARR_APP1(ir_node *, repr_pair->ins, input);
820 DB((dbg, LEVEL_1, "by %+F\n", repr->block));
822 /* rewire block input ... */
826 * Some problem here. For:
827 * if (x) y = 1; else y = 2;
829 * the following code is constructed:
831 * b0: if (x) goto b1; else goto b1;
834 * However, both predecessors of b1 are b0, making the Phi
837 * We solve this by fixing critical edges.
839 for (i = 0; i < n; ++i) {
840 ir_node *pred = ins[i];
846 cfop = get_irn_op(skip_Proj(pred));
847 if (is_op_fragile(cfop)) {
848 /* ignore exception flow */
851 if (is_op_forking(cfop)) {
852 /* a critical edge */
853 ir_node *block = new_r_Block(irg, 1, &ins[i]);
854 ir_node *jmp = new_r_Jmp(block);
860 set_irn_in(block, n, ins);
863 /* ... existing Phis ... */
864 for (repr_phi = repr->phis; repr_phi != NULL; repr_phi = repr_phi->next) {
865 set_irn_in(repr_phi->phi, n, repr_phi->ins);
866 DEL_ARR_F(repr_phi->ins);
869 /* ... and all inputs by creating new Phis ... */
870 for (repr_pair = repr->input_pairs; repr_pair != NULL; repr_pair = repr_pair->next) {
871 ir_node *input = get_irn_n(repr_pair->irn, repr_pair->index);
872 ir_mode *mode = get_irn_mode(input);
873 ir_node *phi = new_r_Phi(block, n, repr_pair->ins, mode);
875 set_irn_n(repr_pair->irn, repr_pair->index, phi);
876 DEL_ARR_F(repr_pair->ins);
878 /* might be optimized away */
880 add_Block_phi(block, phi);
883 /* ... finally rewire the meet block and fix its Phi-nodes */
884 meet_block = part->meet_block;
885 n = get_Block_n_cfgpreds(meet_block);
887 ins = NEW_ARR_F(ir_node *, n);
890 for (p = get_Block_phis(meet_block); p != NULL; p = get_Phi_next(p)) {
894 phi_ins = NEW_ARR_F(ir_node *, n_phis * n);
896 for (i = j = 0; i < n; ++i) {
897 ir_node *pred = get_Block_cfgpred(meet_block, i);
899 list_for_each_entry(block_t, bl, &part->blocks, block_list) {
900 if (bl->cf_root->node == pred)
905 for (k = 0, p = get_Block_phis(meet_block); p != NULL; p = get_Phi_next(p), ++k) {
906 phi_ins[k * n + j] = get_Phi_pred(p, i);
916 for (k = 0, p = get_Block_phis(meet_block); p != NULL; p = next, ++k) {
917 next = get_Phi_next(p);
919 exchange(p, phi_ins[k * n]);
921 /* all Phis killed */
922 set_Block_phis(meet_block, NULL);
924 for (k = 0, p = get_Block_phis(meet_block); p != NULL; p = next, ++k) {
925 next = get_Phi_next(p);
927 set_irn_in(p, j, &phi_ins[k * n]);
932 /* fix inputs of the meet block */
933 set_irn_in(meet_block, j, ins);
938 * Create a partition for a the end block.
940 * @param end_block the end block
941 * @param env the environment
943 static void partition_for_end_block(ir_node *end_block, environment_t *env)
945 partition_t *part = create_partition(end_block, env);
949 /* collect normal blocks */
950 for (i = get_Block_n_cfgpreds(end_block) - 1; i >= 0; --i) {
951 ir_node *pred = get_Block_cfgpred(end_block, i);
956 mark_irn_visited(pred);
958 block = get_nodes_block(pred);
959 bl = create_block(block, i, part, env);
960 node = create_node(pred, bl, env);
965 /* collect all no-return blocks */
966 end = get_irg_end(get_irn_irg(end_block));
967 for (i = get_End_n_keepalives(end) - 1; i >= 0; --i) {
968 ir_node *ka = get_End_keepalive(end, i);
975 mark_irn_visited(ka);
978 block = get_nodes_block(ka);
979 bl = create_block(block, -1, part, env);
980 node = create_node(ka, bl, env);
985 dump_partition("Created", part);
986 } /* partition_for_end_block */
990 * Create a partition for a given meet block.
992 * @param block the meet block
993 * @param preds array of candidate predecessors
994 * @param n_preds number of elements in preds
995 * @param env the environment
997 static void partition_for_block(ir_node *block, pred_t preds[], int n_preds, environment_t *env)
999 partition_t *part = create_partition(block, env);
1002 for (i = n_preds - 1; i >= 0; --i) {
1003 ir_node *pred = preds[i].pred;
1008 mark_irn_visited(pred);
1010 block = get_nodes_block(pred);
1011 bl = create_block(block, preds[i].index, part, env);
1012 node = create_node(pred, bl, env);
1017 dump_partition("Created", part);
1018 } /* partition_for_block */
1021 * Walker: clear the links of all block phi lists and normal
1024 static void clear_phi_links(ir_node *irn, void *env)
1027 if (is_Block(irn)) {
1028 set_Block_phis(irn, NULL);
1029 set_irn_link(irn, NULL);
1031 } /* clear_phi_links */
1034 * Walker, detect live-out nodes.
1036 static void find_liveouts(ir_node *irn, void *ctx)
1038 environment_t *env = (environment_t*)ctx;
1039 ir_node **live_outs = env->live_outs;
1040 ir_node *this_block;
1046 /* ignore Keep-alives */
1050 this_block = get_nodes_block(irn);
1053 /* update the Phi list */
1054 add_Block_phi(this_block, irn);
1057 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
1058 ir_node *pred_block;
1059 ir_node *pred = get_irn_n(irn, i);
1060 int idx = get_irn_idx(pred);
1062 if (live_outs[idx] != NULL) {
1063 /* already marked as live-out */
1067 pred_block = get_nodes_block(pred);
1068 /* Phi nodes always refer to live-outs */
1069 if (is_Phi(irn) || this_block != pred_block) {
1070 /* pred is a live-out */
1071 live_outs[idx] = pred_block;
1074 } /* find_liveouts */
1077 * Check if the current block is the meet block of a its predecessors.
1079 static void check_for_cf_meet(ir_node *block, void *ctx)
1081 environment_t *env = (environment_t*)ctx;
1085 if (block == get_irg_end_block(get_irn_irg(block))) {
1086 /* always create a partition for the end block */
1087 partition_for_end_block(block, env);
1091 n = get_Block_n_cfgpreds(block);
1093 /* Must have at least two predecessors */
1097 NEW_ARR_A(pred_t, preds, n);
1099 for (i = n - 1; i >= 0; --i) {
1100 ir_node *pred = get_Block_cfgpred(block, i);
1101 ir_node *pred_block;
1103 /* pred must be a direct jump to us */
1104 if (! is_Jmp(pred) && ! is_Raise(pred) && !is_Bad(pred))
1107 pred_block = get_nodes_block(skip_Proj(pred));
1109 preds[k].pred = pred;
1114 partition_for_block(block, preds, k, env);
1115 } /* check_for_cf_meet */
1118 * Compare two nodes for root ordering.
1120 static int cmp_nodes(const void *a, const void *b)
1122 const ir_node *const *pa = (const ir_node*const*)a;
1123 const ir_node *const *pb = (const ir_node*const*)b;
1124 const ir_node *irn_a = *pa;
1125 const ir_node *irn_b = *pb;
1126 unsigned code_a = get_irn_opcode(irn_a);
1127 unsigned code_b = get_irn_opcode(irn_b);
1128 ir_mode *mode_a, *mode_b;
1129 unsigned idx_a, idx_b;
1131 /* try opcode first */
1132 if (code_a != code_b)
1133 return code_a - code_b;
1136 mode_a = get_irn_mode(irn_a);
1137 mode_b = get_irn_mode(irn_b);
1139 if (mode_a != mode_b)
1140 return mode_a < mode_b ? -1 : +1;
1142 /* last resort: index */
1143 idx_a = get_irn_idx(irn_a);
1144 idx_b = get_irn_idx(irn_b);
1146 return (idx_a > idx_b) - (idx_a < idx_b);
1150 * Add the roots to all blocks.
1152 static void add_roots(ir_graph *irg, environment_t *env)
1154 unsigned idx, n = get_irg_last_idx(irg);
1155 ir_node **live_outs = env->live_outs;
1158 for (idx = 0; idx < n; ++idx) {
1159 ir_node *block = live_outs[idx];
1161 if (block != NULL && is_Block(block)) {
1162 block_t *bl = get_Block_entry(block);
1165 ir_node *irn = get_idx_irn(irg, idx);
1167 if (!irn_visited_else_mark(irn)) {
1168 ARR_APP1(ir_node *, bl->roots, irn);
1174 * Now sort the roots to normalize them as good as possible.
1175 * Else, we will split identical blocks if we start which different roots.
1177 for (bl = env->all_blocks; bl != NULL; bl = bl->all_next) {
1178 size_t i, n = ARR_LEN(bl->roots);
1181 /* TODO: is this really needed? The roots are already in
1182 idx-order by construction, which might be good enough. */
1183 qsort(bl->roots, n, sizeof(bl->roots[0]), cmp_nodes);
1186 DB((dbg, LEVEL_2, " Adding Roots for block %+F\n ", bl->block));
1187 /* ok, add them sorted */
1188 for (i = 0; i < n; ++i) {
1189 DB((dbg, LEVEL_2, "%+F, ", bl->roots[i]));
1190 create_node(bl->roots[i], bl, env);
1192 DB((dbg, LEVEL_2, "\n"));
1193 DEL_ARR_F(bl->roots);
1197 #endif /* GENERAL_SHAPE */
1199 /* Combines congruent end blocks into one. */
1200 int shape_blocks(ir_graph *irg)
1207 /* register a debug mask */
1208 FIRM_DBG_REGISTER(dbg, "firm.opt.blocks");
1210 DEBUG_ONLY(part_nr = 0);
1211 DB((dbg, LEVEL_1, "Shaping blocks for %+F\n", irg));
1213 /* works better, when returns are placed at the end of the blocks */
1214 normalize_n_returns(irg);
1216 obstack_init(&env.obst);
1217 INIT_LIST_HEAD(&env.partitions);
1218 INIT_LIST_HEAD(&env.ready);
1219 env.opcode2id_map = new_set(cmp_opcode, iro_Last * 4);
1221 n = get_irg_last_idx(irg);
1222 env.live_outs = NEW_ARR_F(ir_node *, n);
1223 memset(env.live_outs, 0, sizeof(*env.live_outs) * n);
1225 env.all_blocks = NULL;
1227 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
1229 #ifdef GENERAL_SHAPE
1231 * Detect, which nodes are live-out only: these are the roots of our blocks.
1234 irg_walk_graph(irg, clear_phi_links, find_liveouts, &env);
1237 ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
1239 inc_irg_visited(irg);
1240 #ifdef GENERAL_SHAPE
1242 * Detect all control flow meets and create partitions.
1244 irg_block_walk_graph(irg, NULL, check_for_cf_meet, &env);
1246 /* add root nodes to the partition blocks */
1247 add_roots(irg, &env);
1249 partition_for_end_block(get_irg_end_block(irg), &env);
1252 propagate_live_troughs(&env);
1253 while (! list_empty(&env.partitions))
1256 res = !list_empty(&env.ready);
1257 //if (res) dump_ir_block_graph(irg, "-before");
1260 list_for_each_entry(partition_t, part, &env.ready, part_list) {
1261 dump_partition("Ready Partition", part);
1264 ir_free_resources(irg, IR_RESOURCE_IRN_VISITED | IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
1267 /* control flow changed */
1268 set_irg_outs_inconsistent(irg);
1269 set_irg_extblk_inconsistent(irg);
1270 set_irg_doms_inconsistent(irg);
1271 set_irg_loopinfo_inconsistent(irg);
1273 /* Calls might be removed. */
1274 set_trouts_inconsistent();
1277 for (bl = env.all_blocks; bl != NULL; bl = bl->all_next) {
1278 DEL_ARR_F(bl->roots);
1281 DEL_ARR_F(env.live_outs);
1282 del_set(env.opcode2id_map);
1283 obstack_free(&env.obst, NULL);
1286 } /* shape_blocks */
1288 ir_graph_pass_t *shape_blocks_pass(const char *name)
1290 return def_graph_pass_ret(name ? name : "shape_blocks", shape_blocks);
1291 } /* shape_blocks_pass */