3 * File name: ir/ana/irdom.c
4 * Purpose: Construct and access dominator / post dominator tree.
5 * Author: Goetz Lindenmaier
6 * Modified by: Michael Beck, Rubino Geiss
9 * Copyright: (c) 2002-2003 Universitaet Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
26 #include "irgraph_t.h" /* To access state field. */
31 #define get_dom_info(bl) (&(bl)->attr.block.dom)
32 #define get_pdom_info(bl) (&(bl)->attr.block.pdom)
34 /*--------------------------------------------------------------------*/
35 /** Accessing the dominator and post dominator data structures **/
36 /*--------------------------------------------------------------------*/
38 ir_node *get_Block_idom(const ir_node *bl) {
40 if (get_Block_dom_depth(bl) == -1) {
41 /* This block is not reachable from Start */
44 return get_dom_info(bl)->idom;
47 void set_Block_idom(ir_node *bl, ir_node *n) {
48 dom_info *bli = get_dom_info(bl);
50 assert(get_irn_op(bl) == op_Block);
52 /* Set the immediate dominator of bl to n */
56 * If we don't set the root of the dominator tree
57 * Append bl to the dominates queue of n.
60 dom_info *ni = get_dom_info(n);
62 bli->next = ni->first;
67 ir_node *get_Block_ipostdom(const ir_node *bl) {
69 if (get_Block_postdom_depth(bl) == -1) {
70 /* This block is not reachable from Start */
73 return get_pdom_info(bl)->idom;
76 void set_Block_ipostdom(ir_node *bl, ir_node *n) {
77 dom_info *bli = get_pdom_info(bl);
79 assert(get_irn_op(bl) == op_Block);
81 /* Set the immediate post dominator of bl to n */
85 * If we don't set the root of the post dominator tree
86 * Append bl to the post dominates queue of n.
89 dom_info *ni = get_pdom_info(n);
91 bli->next = ni->first;
96 int get_Block_dom_pre_num(const ir_node *bl) {
97 assert(get_irn_op(bl) == op_Block);
98 return get_dom_info(bl)->pre_num;
101 void set_Block_dom_pre_num(ir_node *bl, int num) {
102 assert(get_irn_op(bl) == op_Block);
103 get_dom_info(bl)->pre_num = num;
106 int get_Block_dom_depth(const ir_node *bl) {
107 assert(get_irn_op(bl) == op_Block);
108 return get_dom_info(bl)->dom_depth;
111 void set_Block_dom_depth(ir_node *bl, int depth) {
112 assert(get_irn_op(bl) == op_Block);
113 get_dom_info(bl)->dom_depth = depth;
117 int get_Block_postdom_pre_num(const ir_node *bl) {
118 assert(get_irn_op(bl) == op_Block);
119 return get_pdom_info(bl)->pre_num;
122 void set_Block_postdom_pre_num(ir_node *bl, int num) {
123 assert(get_irn_op(bl) == op_Block);
124 get_pdom_info(bl)->pre_num = num;
127 int get_Block_postdom_depth(const ir_node *bl) {
128 assert(get_irn_op(bl) == op_Block);
129 return get_pdom_info(bl)->dom_depth;
132 void set_Block_postdom_depth(ir_node *bl, int depth) {
133 assert(get_irn_op(bl) == op_Block);
134 get_pdom_info(bl)->dom_depth = depth;
137 unsigned get_Block_dom_tree_pre_num(const ir_node *bl)
139 assert(is_Block(bl));
140 return get_dom_info(bl)->tree_pre_num;
143 unsigned get_Block_dom_max_subtree_pre_num(const ir_node *bl)
145 assert(is_Block(bl));
146 return get_dom_info(bl)->max_subtree_pre_num;
149 unsigned get_Block_pdom_tree_pre_num(const ir_node *bl)
151 assert(is_Block(bl));
152 return get_pdom_info(bl)->tree_pre_num;
155 unsigned get_Block_pdom_max_subtree_pre_num(const ir_node *bl)
157 assert(is_Block(bl));
158 return get_pdom_info(bl)->max_subtree_pre_num;
161 /* Check, if a block dominates another block. */
162 int block_dominates(const ir_node *a, const ir_node *b)
164 const dom_info *ai, *bi;
166 if (is_Block(a) && is_Block(b)) {
167 ai = get_dom_info(a);
168 bi = get_dom_info(b);
169 return bi->tree_pre_num - ai->tree_pre_num
170 <= ai->max_subtree_pre_num - ai->tree_pre_num;
176 /* Get the first node in the list of nodes dominated by a given block. */
177 ir_node *get_Block_dominated_first(const ir_node *bl)
179 assert(is_Block(bl));
180 return get_dom_info(bl)->first;
183 /* Get the next node in a list of nodes which are dominated by some
185 ir_node *get_Block_dominated_next(const ir_node *bl)
187 assert(is_Block(bl));
188 return get_dom_info(bl)->next;
191 /* Check, if a block post dominates another block. */
192 int block_postdominates(const ir_node *a, const ir_node *b)
194 const dom_info *ai, *bi;
196 if (is_Block(a) && is_Block(b)) {
197 ai = get_pdom_info(a);
198 bi = get_pdom_info(b);
199 return bi->tree_pre_num - ai->tree_pre_num
200 <= ai->max_subtree_pre_num - ai->tree_pre_num;
206 /* Get the first node in the list of nodes post dominated by a given block. */
207 ir_node *get_Block_postdominated_first(const ir_node *bl)
209 assert(is_Block(bl));
210 return get_pdom_info(bl)->first;
213 /* Get the next node in a list of nodes which are post dominated by some
215 ir_node *get_Block_postdominated_next(const ir_node *bl)
217 assert(is_Block(bl));
218 return get_pdom_info(bl)->next;
221 /* Visit all nodes in the dominator subtree of a given node. */
222 void dom_tree_walk(ir_node *bl, irg_walk_func *pre,
223 irg_walk_func *post, void *env)
230 dominates_for_each(bl, p) {
231 dom_tree_walk(p, pre, post, env);
238 /* Visit all nodes in the post dominator subtree of a given node. */
239 void postdom_tree_walk(ir_node *bl, irg_walk_func *pre,
240 irg_walk_func *post, void *env)
247 postdominates_for_each(bl, p) {
248 postdom_tree_walk(p, pre, post, env);
255 /* Walk over the dominator tree of an irg starting at the root. */
256 void dom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
257 irg_walk_func *post, void *env)
259 /* The root of the dominator tree should be the Start block. */
260 ir_node *root = get_irg_start_block(irg);
262 assert(irg->dom_state == dom_consistent
263 && "The dominators of the irg must be consistent");
264 assert(root && "The start block of the graph is NULL?");
265 assert(get_dom_info(root)->idom == NULL
266 && "The start node in the graph must be the root of the dominator tree");
267 dom_tree_walk(root, pre, post, env);
270 /* Walk over the post dominator tree of an irg starting at the root. */
271 void postdom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
272 irg_walk_func *post, void *env)
274 /* The root of the dominator tree should be the End block. */
275 ir_node *root = get_irg_end_block(irg);
277 assert(irg->pdom_state == dom_consistent
278 && "The dominators of the irg must be consistent");
279 assert(root && "The end block of the graph is NULL?");
280 assert(get_pdom_info(root)->idom == NULL
281 && "The End block node in the graph must be the root of the post dominator tree");
282 postdom_tree_walk(root, pre, post, env);
286 static void assign_tree_dom_pre_order(ir_node *bl, void *data)
288 unsigned *num = data;
289 dom_info *bi = get_dom_info(bl);
291 bi->tree_pre_num = (*num)++;
294 static void assign_tree_dom_pre_order_max(ir_node *bl, void *data)
296 dom_info *bi = get_dom_info(bl);
299 unsigned children = 0;
301 for(p = bi->first; p; p = get_dom_info(p)->next) {
302 unsigned max_p = get_dom_info(p)->max_subtree_pre_num;
303 max = max > max_p ? max : max_p;
307 bi->max_subtree_pre_num = children > 0 ? max : bi->tree_pre_num;
308 assert(bi->max_subtree_pre_num >= bi->tree_pre_num);
311 static void assign_tree_postdom_pre_order(ir_node *bl, void *data)
313 unsigned *num = data;
314 dom_info *bi = get_pdom_info(bl);
316 bi->tree_pre_num = (*num)++;
319 static void assign_tree_postdom_pre_order_max(ir_node *bl, void *data)
321 dom_info *bi = get_pdom_info(bl);
324 unsigned children = 0;
326 for(p = bi->first; p; p = get_pdom_info(p)->next) {
327 unsigned max_p = get_pdom_info(p)->max_subtree_pre_num;
328 max = max > max_p ? max : max_p;
332 bi->max_subtree_pre_num = children > 0 ? max : bi->tree_pre_num;
333 assert(bi->max_subtree_pre_num >= bi->tree_pre_num);
336 /*--------------------------------------------------------------------*/
337 /* Building and Removing the dominator datastructure */
338 /*--------------------------------------------------------------------*/
341 * count the number of blocks and clears the dominance info
343 static void count_and_init_blocks_dom(ir_node *bl, void *env) {
344 int *n_blocks = (int *) env;
347 memset(get_dom_info(bl), 0, sizeof(dom_info));
348 set_Block_idom(bl, NULL);
349 set_Block_dom_pre_num(bl, -1);
350 set_Block_dom_depth(bl, -1);
354 * count the number of blocks and clears the post dominance info
356 static void count_and_init_blocks_pdom(ir_node *bl, void *env) {
357 int *n_blocks = (int *) env;
360 memset(get_pdom_info(bl), 0, sizeof(dom_info));
361 set_Block_ipostdom(bl, NULL);
362 set_Block_postdom_pre_num(bl, -1);
363 set_Block_postdom_depth(bl, -1);
366 /** temporary type used while constructing the dominator / post dominator tree. */
367 typedef struct tmp_dom_info {
368 ir_node *block; /**< backlink */
370 struct tmp_dom_info *semi; /**< semidominator */
371 struct tmp_dom_info *parent;
372 struct tmp_dom_info *label; /**< used for LINK and EVAL */
373 struct tmp_dom_info *ancestor;/**< used for LINK and EVAL */
374 struct tmp_dom_info *dom; /**< After step 3, if the semidominator of w is
375 its immediate dominator, then w->dom is the
376 immediate dominator of w. Otherwise w->dom
377 is a vertex v whose number is smaller than
378 w and whose immediate dominator is also w's
379 immediate dominator. After step 4, w->dom
380 is the immediate dominator of w. */
381 struct tmp_dom_info *bucket; /**< set of vertices with same semidominator */
384 /** Struct to pass info through walker. */
392 * Walks Blocks along the out datastructure. If recursion started with
393 * Start block misses control dead blocks.
395 static void init_tmp_dom_info(ir_node *bl, tmp_dom_info *parent,
396 tmp_dom_info *tdi_list, int* used) {
400 assert(get_irn_op(bl) == op_Block);
401 if (get_irg_block_visited(current_ir_graph) == get_Block_block_visited(bl))
403 mark_Block_block_visited(bl);
404 set_Block_dom_pre_num(bl, *used);
406 tdi = &tdi_list[*used];
411 tdi->ancestor = NULL;
413 tdi->parent = parent;
417 for(i = 0; i < get_Block_n_cfg_outs(bl); i++) {
418 ir_node *pred = get_Block_cfg_out(bl, i);
419 assert(get_irn_opcode(pred) == iro_Block);
420 init_tmp_dom_info(pred, tdi, tdi_list, used);
425 * Walks Blocks along the control flow. If recursion started with
426 * End block misses blocks in endless loops.
428 static void init_tmp_pdom_info(ir_node *bl, tmp_dom_info *parent,
429 tmp_dom_info *tdi_list, int* used) {
433 assert(get_irn_op(bl) == op_Block);
434 if (get_irg_block_visited(current_ir_graph) == get_Block_block_visited(bl))
436 mark_Block_block_visited(bl);
437 set_Block_postdom_pre_num(bl, *used);
439 tdi = &tdi_list[*used];
444 tdi->ancestor = NULL;
446 tdi->parent = parent;
450 for(i = 0; i < get_Block_n_cfgpreds(bl); i++) {
451 ir_node *pred = get_Block_cfgpred_block(bl, i);
454 assert(is_Block(pred));
455 init_tmp_pdom_info(pred, tdi, tdi_list, used);
459 static void dom_compress(tmp_dom_info *v)
461 assert (v->ancestor);
462 if (v->ancestor->ancestor) {
463 dom_compress (v->ancestor);
464 if (v->ancestor->label->semi < v->label->semi) {
465 v->label = v->ancestor->label;
467 v->ancestor = v->ancestor->ancestor;
472 * if V is a root, return v, else return the vertex u, not being the
473 * root, with minimum u->semi on the path from v to its root.
475 INLINE static tmp_dom_info *dom_eval (tmp_dom_info *v)
477 if (!v->ancestor) return v;
482 /** make V W's ancestor */
483 INLINE static void dom_link(tmp_dom_info *v, tmp_dom_info *w)
488 /* Computes the dominator trees. Sets a flag in irg to "dom_consistent".
489 If the control flow of the graph is changed this flag must be set to
490 "dom_inconsistent". */
491 void compute_doms(ir_graph *irg) {
492 ir_graph *rem = current_ir_graph;
493 int n_blocks, used, i, j;
494 tmp_dom_info *tdi_list; /* Ein Golf? */
496 current_ir_graph = irg;
498 /* Update graph state */
499 assert(get_irg_phase_state(current_ir_graph) != phase_building);
500 current_ir_graph->dom_state = dom_consistent;
502 /* Count the number of blocks in the graph. */
504 irg_block_walk(get_irg_end(current_ir_graph), count_and_init_blocks_dom, NULL, &n_blocks);
506 /* Memory for temporary information. */
507 tdi_list = xcalloc(n_blocks, sizeof(tdi_list[0]));
509 /* We need the out datastructure. */
510 if (current_ir_graph->outs_state != outs_consistent)
511 compute_irg_outs(current_ir_graph);
513 /* this with a standard walker as passing the parent to the sons isn't
516 inc_irg_block_visited(current_ir_graph);
517 init_tmp_dom_info(get_irg_start_block(current_ir_graph), NULL, tdi_list, &used);
518 /* If not all blocks are reachable from Start by out edges this assertion
520 assert(used == n_blocks && "Precondition for dom construction violated"); */
524 for (i = n_blocks-1; i > 0; i--) { /* Don't iterate the root, it's done. */
526 tmp_dom_info *w = &tdi_list[i];
530 irn_arity = get_irn_arity(w->block);
531 for (j = 0; j < irn_arity; j++) {
532 ir_node *pred = get_Block_cfgpred_block(w->block, j);
535 if (is_Bad(pred) || (get_Block_dom_pre_num (pred) == -1))
536 continue; /* control-dead */
538 u = dom_eval (&tdi_list[get_Block_dom_pre_num(pred)]);
539 if (u->semi < w->semi) w->semi = u->semi;
541 /* Add w to w->semi's bucket. w is in exactly one bucket, so
542 buckets can ben implemented as linked lists. */
543 w->bucket = w->semi->bucket;
546 dom_link (w->parent, w);
549 while (w->parent->bucket) {
551 v = w->parent->bucket;
552 /* remove v from w->parent->bucket */
553 w->parent->bucket = v->bucket;
557 if (u->semi < v->semi)
564 tdi_list[0].dom = NULL;
565 set_Block_idom(tdi_list[0].block, NULL);
566 set_Block_dom_depth(tdi_list[0].block, 1);
567 for (i = 1; i < n_blocks; i++) {
568 tmp_dom_info *w = &tdi_list[i];
570 if (w->dom != w->semi) w->dom = w->dom->dom;
571 set_Block_idom(w->block, w->dom->block);
572 set_Block_dom_depth(w->block, get_Block_dom_depth(w->dom->block) + 1);
577 current_ir_graph = rem;
579 /* Do a walk over the tree and assign the tree pre orders. */
581 unsigned tree_pre_order = 0;
582 dom_tree_walk_irg(irg, assign_tree_dom_pre_order,
583 assign_tree_dom_pre_order_max, &tree_pre_order);
587 void free_dom(ir_graph *irg) {
588 /* Update graph state */
589 assert(get_irg_phase_state(current_ir_graph) != phase_building);
590 current_ir_graph->dom_state = dom_none;
592 /* With the implementation right now there is nothing to free,
593 but better call it anyways... */
596 /* Computes the post dominator trees. Sets a flag in irg to "dom_consistent".
597 If the control flow of the graph is changed this flag must be set to
598 "dom_inconsistent". */
599 void compute_postdoms(ir_graph *irg) {
600 ir_graph *rem = current_ir_graph;
601 int n_blocks, used, i, j;
602 tmp_dom_info *tdi_list;
604 current_ir_graph = irg;
606 /* Update graph state */
607 assert(get_irg_phase_state(current_ir_graph) != phase_building);
608 current_ir_graph->pdom_state = dom_consistent;
610 /* Count the number of blocks in the graph. */
612 irg_block_walk(get_irg_end(current_ir_graph), count_and_init_blocks_pdom, NULL, &n_blocks);
614 /* Memory for temporary information. */
615 tdi_list = xcalloc(n_blocks, sizeof(tdi_list[0]));
617 /* We need the out datastructure. */
618 if (current_ir_graph->outs_state != outs_consistent)
619 compute_irg_outs(current_ir_graph);
621 /* this with a standard walker as passing the parent to the sons isn't
624 inc_irg_block_visited(current_ir_graph);
625 init_tmp_pdom_info(get_irg_end_block(current_ir_graph), NULL, tdi_list, &used);
626 /* If not all blocks are reachable from End by cfg edges this assertion
628 assert(used == n_blocks && "Precondition for dom construction violated"); */
632 for (i = n_blocks-1; i > 0; i--) { /* Don't iterate the root, it's done. */
634 tmp_dom_info *w = &tdi_list[i];
638 irn_arity = get_Block_n_cfg_outs(w->block);
639 for (j = 0; j < irn_arity; j++) {
640 ir_node *succ = get_Block_cfg_out(w->block, j);
643 if (get_Block_postdom_pre_num (succ) == -1)
644 continue; /* endless-loop */
646 u = dom_eval (&tdi_list[get_Block_postdom_pre_num(succ)]);
647 if (u->semi < w->semi) w->semi = u->semi;
649 /* Add w to w->semi's bucket. w is in exactly one bucket, so
650 buckets can be implemented as linked lists. */
651 w->bucket = w->semi->bucket;
654 dom_link (w->parent, w);
657 while (w->parent->bucket) {
659 v = w->parent->bucket;
660 /* remove v from w->parent->bucket */
661 w->parent->bucket = v->bucket;
665 if (u->semi < v->semi)
672 tdi_list[0].dom = NULL;
673 set_Block_ipostdom(tdi_list[0].block, NULL);
674 set_Block_postdom_depth(tdi_list[0].block, 1);
675 for (i = 1; i < n_blocks; i++) {
676 tmp_dom_info *w = &tdi_list[i];
678 if (w->dom != w->semi) w->dom = w->dom->dom;
679 set_Block_ipostdom(w->block, w->dom->block);
680 set_Block_postdom_depth(w->block, get_Block_postdom_depth(w->dom->block) + 1);
685 current_ir_graph = rem;
687 /* Do a walk over the tree and assign the tree pre orders. */
689 unsigned tree_pre_order = 0;
690 postdom_tree_walk_irg(irg, assign_tree_postdom_pre_order,
691 assign_tree_postdom_pre_order_max, &tree_pre_order);
695 void free_postdom(ir_graph *irg) {
696 /* Update graph state */
697 assert(get_irg_phase_state(current_ir_graph) != phase_building);
698 current_ir_graph->pdom_state = dom_none;
700 /* With the implementation right now there is nothing to free,
701 but better call it anyways... */