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 Construct and access dominator / post dominator tree.
23 * @author Goetz Lindenmaier, Michael Beck, Rubino Geiss
35 #include "irgraph_t.h"
42 #define get_dom_info(bl) (&(bl)->attr.block.dom)
43 #define get_pdom_info(bl) (&(bl)->attr.block.pdom)
45 /*--------------------------------------------------------------------*/
46 /** Accessing the dominator and post dominator data structures **/
47 /*--------------------------------------------------------------------*/
49 ir_node *get_Block_idom(const ir_node *bl)
52 if (get_Block_dom_depth(bl) == -1) {
53 /* This block is not reachable from Start */
54 ir_graph *irg = get_irn_irg(bl);
55 return new_r_Bad(irg, mode_BB);
57 return get_dom_info(bl)->idom;
60 void set_Block_idom(ir_node *bl, ir_node *n)
62 ir_dom_info *bli = get_dom_info(bl);
66 /* Set the immediate dominator of bl to n */
70 * If we don't set the root of the dominator tree
71 * Append bl to the dominates queue of n.
74 ir_dom_info *ni = get_dom_info(n);
76 bli->next = ni->first;
81 ir_node *get_Block_ipostdom(const ir_node *bl)
84 if (get_Block_postdom_depth(bl) == -1) {
85 /* This block is not reachable from Start */
86 ir_graph *irg = get_irn_irg(bl);
87 return new_r_Bad(irg, mode_BB);
89 return get_pdom_info(bl)->idom;
92 void set_Block_ipostdom(ir_node *bl, ir_node *n)
94 ir_dom_info *bli = get_pdom_info(bl);
98 /* Set the immediate post dominator of bl to n */
102 * If we don't set the root of the post dominator tree
103 * Append bl to the post dominates queue of n.
106 ir_dom_info *ni = get_pdom_info(n);
108 bli->next = ni->first;
113 int get_Block_dom_pre_num(const ir_node *bl)
115 assert(is_Block(bl));
116 return get_dom_info(bl)->pre_num;
119 void set_Block_dom_pre_num(ir_node *bl, int num)
121 assert(is_Block(bl));
122 get_dom_info(bl)->pre_num = num;
125 int get_Block_dom_depth(const ir_node *bl)
127 assert(is_Block(bl));
128 return get_dom_info(bl)->dom_depth;
131 void set_Block_dom_depth(ir_node *bl, int depth)
133 assert(is_Block(bl));
134 get_dom_info(bl)->dom_depth = depth;
138 int get_Block_postdom_pre_num(const ir_node *bl)
140 assert(is_Block(bl));
141 return get_pdom_info(bl)->pre_num;
144 void set_Block_postdom_pre_num(ir_node *bl, int num)
146 assert(is_Block(bl));
147 get_pdom_info(bl)->pre_num = num;
150 int get_Block_postdom_depth(const ir_node *bl)
152 assert(is_Block(bl));
153 return get_pdom_info(bl)->dom_depth;
156 void set_Block_postdom_depth(ir_node *bl, int depth)
158 assert(is_Block(bl));
159 get_pdom_info(bl)->dom_depth = depth;
162 unsigned get_Block_dom_tree_pre_num(const ir_node *bl)
164 assert(is_Block(bl));
165 return get_dom_info(bl)->tree_pre_num;
168 unsigned get_Block_dom_max_subtree_pre_num(const ir_node *bl)
170 assert(is_Block(bl));
171 return get_dom_info(bl)->max_subtree_pre_num;
174 unsigned get_Block_pdom_tree_pre_num(const ir_node *bl)
176 assert(is_Block(bl));
177 return get_pdom_info(bl)->tree_pre_num;
180 unsigned get_Block_pdom_max_subtree_pre_num(const ir_node *bl)
182 assert(is_Block(bl));
183 return get_pdom_info(bl)->max_subtree_pre_num;
186 /* Check, if a block dominates another block. */
187 int block_dominates(const ir_node *a, const ir_node *b)
189 const ir_dom_info *ai, *bi;
191 if (is_Block(a) && is_Block(b)) {
192 ai = get_dom_info(a);
193 bi = get_dom_info(b);
194 return bi->tree_pre_num - ai->tree_pre_num
195 <= ai->max_subtree_pre_num - ai->tree_pre_num;
201 /* Check, if a block strictly dominates another block. */
202 int block_strictly_dominates(const ir_node *a, const ir_node *b)
204 return (a != b) && block_dominates(a, b);
207 /* Returns the smallest common dominator block of two nodes. */
208 ir_node *node_smallest_common_dominator(ir_node *a, ir_node *b)
210 ir_node *bl_a = is_Block(a) ? a : get_nodes_block(a);
211 ir_node *bl_b = is_Block(b) ? b : get_nodes_block(b);
212 ir_node *dom_bl = NULL;
214 /* Check if block of a dominates block of b */
215 if (block_dominates(bl_a, bl_b))
217 /* Check if block of b dominates block of a */
218 else if (block_dominates(bl_b, bl_a))
221 /* walk up dominator tree and search for first block dominating a and b */
223 bl_a = get_Block_idom(bl_a);
225 assert(! is_Bad(bl_a) && "block is dead?");
227 if (block_dominates(bl_a, bl_b))
235 /* Returns the smallest common dominator block of all users of a node. */
236 ir_node *node_users_smallest_common_dominator(ir_node *irn, int handle_phi)
238 int n, j, i = 0, success;
239 ir_node **user_blocks, *dom_bl;
240 const ir_edge_t *edge;
242 assert(! is_Block(irn) && "WRONG USAGE of node_users_smallest_common_dominator");
243 assert(edges_activated(get_irn_irg(irn)) && "need edges activated");
245 n = get_irn_n_edges(irn);
247 /* get array to hold all block of the node users */
248 NEW_ARR_A(ir_node *, user_blocks, n);
249 foreach_out_edge(irn, edge) {
250 ir_node *src = get_edge_src_irn(edge);
252 if (is_Phi(src) && handle_phi) {
253 /* get the corresponding cfg predecessor block if phi handling requested */
254 j = get_edge_src_pos(edge);
255 assert(j >= 0 && "kaputt");
256 user_blocks[i++] = get_Block_cfgpred_block(get_nodes_block(src), j);
259 user_blocks[i++] = is_Block(src) ? src : get_nodes_block(src);
262 assert(i == n && "get_irn_n_edges probably broken");
264 /* in case of only one user: return the block of the user */
266 return user_blocks[0];
269 /* search the smallest block dominating all user blocks */
271 dom_bl = node_smallest_common_dominator(user_blocks[i], user_blocks[i + 1]);
274 /* check if this block dominates all remaining blocks as well */
275 for (j = i + 2; j < n; j++) {
276 if (! block_dominates(dom_bl, user_blocks[j]))
283 /* inherit the dominator block of the first (i + 1) users */
284 user_blocks[++i] = dom_bl;
287 assert(success && "no block found dominating all users");
293 /* Get the first node in the list of nodes dominated by a given block. */
294 ir_node *get_Block_dominated_first(const ir_node *bl)
296 assert(is_Block(bl));
297 return get_dom_info(bl)->first;
300 /* Get the next node in a list of nodes which are dominated by some
302 ir_node *get_Block_dominated_next(const ir_node *bl)
304 assert(is_Block(bl));
305 return get_dom_info(bl)->next;
308 /* Check, if a block post dominates another block. */
309 int block_postdominates(const ir_node *a, const ir_node *b)
311 const ir_dom_info *ai, *bi;
313 if (is_Block(a) && is_Block(b)) {
314 ai = get_pdom_info(a);
315 bi = get_pdom_info(b);
316 return bi->tree_pre_num - ai->tree_pre_num
317 <= ai->max_subtree_pre_num - ai->tree_pre_num;
323 /* Check, if a block strictly dominates another block. */
324 int block_strictly_postdominates(const ir_node *a, const ir_node *b)
326 return (a != b) && block_postdominates(a, b);
330 /* Get the first node in the list of nodes post dominated by a given block. */
331 ir_node *get_Block_postdominated_first(const ir_node *bl)
333 assert(is_Block(bl));
334 return get_pdom_info(bl)->first;
337 /* Get the next node in a list of nodes which are post dominated by some
339 ir_node *get_Block_postdominated_next(const ir_node *bl)
341 assert(is_Block(bl));
342 return get_pdom_info(bl)->next;
345 /* Visit all nodes in the dominator subtree of a given node. */
346 void dom_tree_walk(ir_node *bl, irg_walk_func *pre,
347 irg_walk_func *post, void *env)
354 dominates_for_each(bl, p) {
355 dom_tree_walk(p, pre, post, env);
362 /* Visit all nodes in the post dominator subtree of a given node. */
363 void postdom_tree_walk(ir_node *bl, irg_walk_func *pre,
364 irg_walk_func *post, void *env)
371 postdominates_for_each(bl, p) {
372 postdom_tree_walk(p, pre, post, env);
379 /* Walk over the dominator tree of an irg starting at the root. */
380 void dom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
381 irg_walk_func *post, void *env)
383 /* The root of the dominator tree should be the Start block. */
384 ir_node *root = get_irg_start_block(irg);
386 assert(is_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_DOMINANCE)
387 && "The dominators of the irg must be consistent");
388 assert(root && "The start block of the graph is NULL?");
389 assert(get_dom_info(root)->idom == NULL
390 && "The start node in the graph must be the root of the dominator tree");
391 dom_tree_walk(root, pre, post, env);
394 /* Walk over the post dominator tree of an irg starting at the root. */
395 void postdom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
396 irg_walk_func *post, void *env)
398 /* The root of the post dominator tree should be the End block. */
399 ir_node *root = get_irg_end_block(irg);
401 assert(is_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_POSTDOMINANCE)
402 && "The dominators of the irg must be consistent");
403 assert(root && "The end block of the graph is NULL?");
404 assert(get_pdom_info(root)->idom == NULL
405 && "The End block node in the graph must be the root of the post dominator tree");
406 postdom_tree_walk(root, pre, post, env);
410 static void assign_tree_dom_pre_order(ir_node *bl, void *data)
412 unsigned *num = (unsigned*) data;
413 ir_dom_info *bi = get_dom_info(bl);
415 bi->tree_pre_num = (*num)++;
418 static void assign_tree_dom_pre_order_max(ir_node *bl, void *data)
420 ir_dom_info *bi = get_dom_info(bl);
423 unsigned children = 0;
426 for (p = bi->first; p; p = get_dom_info(p)->next) {
427 unsigned max_p = get_dom_info(p)->max_subtree_pre_num;
428 max = max > max_p ? max : max_p;
432 bi->max_subtree_pre_num = children > 0 ? max : bi->tree_pre_num;
433 assert(bi->max_subtree_pre_num >= bi->tree_pre_num);
436 static void assign_tree_postdom_pre_order(ir_node *bl, void *data)
438 unsigned *num = (unsigned*) data;
439 ir_dom_info *bi = get_pdom_info(bl);
441 bi->tree_pre_num = (*num)++;
444 static void assign_tree_postdom_pre_order_max(ir_node *bl, void *data)
446 ir_dom_info *bi = get_pdom_info(bl);
449 unsigned children = 0;
452 for (p = bi->first; p; p = get_pdom_info(p)->next) {
453 unsigned max_p = get_pdom_info(p)->max_subtree_pre_num;
454 max = max > max_p ? max : max_p;
458 bi->max_subtree_pre_num = children > 0 ? max : bi->tree_pre_num;
459 assert(bi->max_subtree_pre_num >= bi->tree_pre_num);
462 /*--------------------------------------------------------------------*/
463 /* Building and Removing the dominator data structure */
464 /*--------------------------------------------------------------------*/
467 * count the number of blocks and clears the post dominance info
469 static void count_and_init_blocks_pdom(ir_node *bl, void *env)
471 int *n_blocks = (int *) env;
475 memset(get_pdom_info(bl), 0, sizeof(ir_dom_info));
476 set_Block_ipostdom(bl, NULL);
477 set_Block_postdom_pre_num(bl, -1);
478 set_Block_postdom_depth(bl, -1);
481 /** temporary type used while constructing the dominator / post dominator tree. */
482 typedef struct tmp_dom_info {
483 ir_node *block; /**< backlink */
485 struct tmp_dom_info *semi; /**< semidominator */
486 struct tmp_dom_info *parent;
487 struct tmp_dom_info *label; /**< used for LINK and EVAL */
488 struct tmp_dom_info *ancestor;/**< used for LINK and EVAL */
489 struct tmp_dom_info *dom; /**< After step 3, if the semidominator of w is
490 its immediate dominator, then w->dom is the
491 immediate dominator of w. Otherwise w->dom
492 is a vertex v whose number is smaller than
493 w and whose immediate dominator is also w's
494 immediate dominator. After step 4, w->dom
495 is the immediate dominator of w. */
496 struct tmp_dom_info *bucket; /**< set of vertices with same semidominator */
499 /** Struct to pass info through walker. */
507 * Walks Blocks along the out data structure. If recursion started with
508 * Start block misses control dead blocks.
510 static void init_tmp_dom_info(ir_node *bl, tmp_dom_info *parent,
511 tmp_dom_info *tdi_list, int *used, int n_blocks)
516 assert(is_Block(bl));
517 if (Block_block_visited(bl))
519 mark_Block_block_visited(bl);
520 set_Block_dom_pre_num(bl, *used);
522 assert(*used < n_blocks);
523 tdi = &tdi_list[*used];
528 tdi->ancestor = NULL;
530 tdi->parent = parent;
534 for (i = get_Block_n_cfg_outs_ka(bl) - 1; i >= 0; --i) {
535 ir_node *pred = get_Block_cfg_out_ka(bl, i);
536 /* can happen for half-optimized dead code (I've seen this in student
541 init_tmp_dom_info(pred, tdi, tdi_list, used, n_blocks);
546 * Walks Blocks along the control flow. If recursion started with
547 * End block misses blocks in endless loops.
549 static void init_tmp_pdom_info(ir_node *bl, tmp_dom_info *parent,
550 tmp_dom_info *tdi_list, int* used, int n_blocks)
555 assert(is_Block(bl));
556 if (get_irg_block_visited(current_ir_graph) == get_Block_block_visited(bl))
558 mark_Block_block_visited(bl);
559 set_Block_postdom_pre_num(bl, *used);
561 assert(*used < n_blocks);
562 tdi = &tdi_list[*used];
567 tdi->ancestor = NULL;
569 tdi->parent = parent;
573 for (i = get_Block_n_cfgpreds(bl) - 1; i >= 0; --i) {
574 ir_node *pred = get_Block_cfgpred_block(bl, i);
577 assert(is_Block(pred));
578 init_tmp_pdom_info(pred, tdi, tdi_list, used, n_blocks);
581 /* Handle keep-alives. Note that the preprocessing
582 in init_construction() had already killed all
583 phantom keep-alive edges. All remaining block keep-alives
584 are really edges to endless loops.
586 if (bl == get_irg_end_block(current_ir_graph)) {
587 ir_node *end = get_irg_end(current_ir_graph);
589 for (i = get_irn_arity(end) - 1; i >= 0; --i) {
590 ir_node *pred = get_irn_n(end, i);
593 init_tmp_pdom_info(pred, tdi, tdi_list, used, n_blocks);
598 static void dom_compress(tmp_dom_info *v)
600 assert (v->ancestor);
601 if (v->ancestor->ancestor) {
602 dom_compress (v->ancestor);
603 if (v->ancestor->label->semi < v->label->semi) {
604 v->label = v->ancestor->label;
606 v->ancestor = v->ancestor->ancestor;
611 * if V is a root, return v, else return the vertex u, not being the
612 * root, with minimum u->semi on the path from v to its root.
614 inline static tmp_dom_info *dom_eval(tmp_dom_info *v)
616 if (!v->ancestor) return v;
621 /** make V W's ancestor */
622 inline static void dom_link(tmp_dom_info *v, tmp_dom_info *w)
628 * Walker: count the number of blocks and clears the dominance info
630 static void count_and_init_blocks_dom(ir_node *bl, void *env)
632 int *n_blocks = (int *) env;
636 memset(get_dom_info(bl), 0, sizeof(ir_dom_info));
637 set_Block_idom(bl, NULL);
638 set_Block_dom_pre_num(bl, -1);
639 set_Block_dom_depth(bl, -1);
642 /* Computes the dominator trees. */
643 void compute_doms(ir_graph *irg)
645 ir_graph *rem = current_ir_graph;
646 int n_blocks, used, i, j;
647 tmp_dom_info *tdi_list; /* Ein Golf? */
649 current_ir_graph = irg;
651 /* Update graph state */
652 assert(get_irg_phase_state(irg) != phase_building);
654 /* Count the number of blocks in the graph. */
656 irg_block_walk_graph(irg, count_and_init_blocks_dom, NULL, &n_blocks);
658 /* Memory for temporary information. */
659 tdi_list = XMALLOCNZ(tmp_dom_info, n_blocks);
661 /* We need the out data structure. */
662 assure_irg_outs(irg);
664 /* this with a standard walker as passing the parent to the sons isn't
667 inc_irg_block_visited(irg);
668 init_tmp_dom_info(get_irg_start_block(irg), NULL, tdi_list, &used, n_blocks);
669 /* If not all blocks are reachable from Start by out edges this assertion
671 assert(used == n_blocks && "Precondition for dom construction violated"); */
672 assert(used <= n_blocks && "Precondition for dom construction violated");
676 for (i = n_blocks-1; i > 0; i--) { /* Don't iterate the root, it's done. */
677 tmp_dom_info *w = &tdi_list[i];
678 ir_node *block = w->block;
683 irn_arity = get_irn_arity(block);
684 for (j = 0; j < irn_arity; j++) {
685 ir_node *pred = get_Block_cfgpred(block, j);
686 ir_node *pred_block = get_nodes_block(pred);
689 if (is_Bad(pred) || (get_Block_dom_pre_num (pred_block) == -1))
690 continue; /* unreachable */
692 u = dom_eval (&tdi_list[get_Block_dom_pre_num(pred_block)]);
693 if (u->semi < w->semi)
697 /* handle keep-alives if we are at the end block */
698 if (block == get_irg_end_block(irg)) {
699 ir_node *end = get_irg_end(irg);
701 irn_arity = get_irn_arity(end);
702 for (j = 0; j < irn_arity; j++) {
703 ir_node *pred = get_irn_n(end, j);
706 if (!is_Block(pred) || get_Block_dom_pre_num(pred) == -1)
707 continue; /* unreachable */
709 u = dom_eval (&tdi_list[get_Block_dom_pre_num(pred)]);
710 if (u->semi < w->semi)
715 /* Add w to w->semi's bucket. w is in exactly one bucket, so
716 buckets can been implemented as linked lists. */
717 w->bucket = w->semi->bucket;
720 dom_link (w->parent, w);
723 while (w->parent->bucket) {
725 v = w->parent->bucket;
726 /* remove v from w->parent->bucket */
727 w->parent->bucket = v->bucket;
731 if (u->semi < v->semi)
738 tdi_list[0].dom = NULL;
739 set_Block_idom(tdi_list[0].block, NULL);
740 set_Block_dom_depth(tdi_list[0].block, 1);
741 for (i = 1; i < n_blocks; i++) {
742 tmp_dom_info *w = &tdi_list[i];
746 continue; /* control dead */
748 if (w->dom != w->semi)
749 w->dom = w->dom->dom;
750 set_Block_idom(w->block, w->dom->block);
752 /* blocks dominated by dead one's are still dead */
753 depth = get_Block_dom_depth(w->dom->block);
756 set_Block_dom_depth(w->block, depth);
762 /* Do a walk over the tree and assign the tree pre orders. */
764 unsigned tree_pre_order = 0;
765 dom_tree_walk(get_irg_start_block(irg), assign_tree_dom_pre_order,
766 assign_tree_dom_pre_order_max, &tree_pre_order);
768 current_ir_graph = rem;
769 set_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_DOMINANCE);
772 void assure_doms(ir_graph *irg)
774 if (! is_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_DOMINANCE))
778 void free_dom(ir_graph *irg)
780 /* Update graph state */
781 assert(get_irg_phase_state(irg) != phase_building);
782 clear_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_DOMINANCE);
784 /* With the implementation right now there is nothing to free,
785 but better call it anyways... */
788 /* Computes the post dominator trees. */
789 void compute_postdoms(ir_graph *irg)
791 ir_graph *rem = current_ir_graph;
792 int n_blocks, used, i, j;
793 tmp_dom_info *tdi_list;
795 current_ir_graph = irg;
797 /* Update graph state */
798 assert(get_irg_phase_state(irg) != phase_building);
800 /* Count the number of blocks in the graph. */
802 irg_block_walk_graph(irg, count_and_init_blocks_pdom, NULL, &n_blocks);
804 /* Memory for temporary information. */
805 tdi_list = XMALLOCNZ(tmp_dom_info, n_blocks);
807 /* We need the out data structure. */
808 assure_irg_outs(irg);
810 /* this with a standard walker as passing the parent to the sons isn't
813 inc_irg_block_visited(irg);
814 init_tmp_pdom_info(get_irg_end_block(irg), NULL, tdi_list, &used, n_blocks);
815 /* If not all blocks are reachable from End by cfg edges this assertion
817 assert(used == n_blocks && "Precondition for dom construction violated"); */
821 for (i = n_blocks-1; i > 0; i--) { /* Don't iterate the root, it's done. */
823 tmp_dom_info *w = &tdi_list[i];
827 irn_arity = get_Block_n_cfg_outs_ka(w->block);
828 for (j = 0; j < irn_arity; j++) {
829 ir_node *succ = get_Block_cfg_out_ka(w->block, j);
832 if (get_Block_postdom_pre_num (succ) == -1)
833 continue; /* endless-loop */
835 u = dom_eval (&tdi_list[get_Block_postdom_pre_num(succ)]);
836 if (u->semi < w->semi) w->semi = u->semi;
838 /* Add w to w->semi's bucket. w is in exactly one bucket, so
839 buckets can be implemented as linked lists. */
840 w->bucket = w->semi->bucket;
843 dom_link (w->parent, w);
846 while (w->parent->bucket) {
848 v = w->parent->bucket;
849 /* remove v from w->parent->bucket */
850 w->parent->bucket = v->bucket;
854 if (u->semi < v->semi)
861 tdi_list[0].dom = NULL;
862 set_Block_ipostdom(tdi_list[0].block, NULL);
863 set_Block_postdom_depth(tdi_list[0].block, 1);
864 for (i = 1; i < n_blocks; i++) {
865 tmp_dom_info *w = &tdi_list[i];
867 if (w->dom != w->semi) w->dom = w->dom->dom;
868 set_Block_ipostdom(w->block, w->dom->block);
869 set_Block_postdom_depth(w->block, get_Block_postdom_depth(w->dom->block) + 1);
875 /* Do a walk over the tree and assign the tree pre orders. */
877 unsigned tree_pre_order = 0;
878 postdom_tree_walk(get_irg_end_block(irg), assign_tree_postdom_pre_order,
879 assign_tree_postdom_pre_order_max, &tree_pre_order);
881 current_ir_graph = rem;
882 set_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_POSTDOMINANCE);
885 void assure_postdoms(ir_graph *irg)
887 if (! is_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_POSTDOMINANCE))
888 compute_postdoms(irg);
891 void free_postdom(ir_graph *irg)
893 /* Update graph state */
894 assert(get_irg_phase_state(irg) != phase_building);
895 clear_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_POSTDOMINANCE);
897 /* With the implementation right now there is nothing to free,
898 but better call it anyways... */