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
38 #include "irgraph_t.h" /* To access state field. */
45 #define get_dom_info(bl) (&(bl)->attr.block.dom)
46 #define get_pdom_info(bl) (&(bl)->attr.block.pdom)
48 /*--------------------------------------------------------------------*/
49 /** Accessing the dominator and post dominator data structures **/
50 /*--------------------------------------------------------------------*/
52 ir_node *get_Block_idom(const ir_node *bl) {
54 if (get_Block_dom_depth(bl) == -1) {
55 /* This block is not reachable from Start */
58 return get_dom_info(bl)->idom;
61 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) {
83 if (get_Block_postdom_depth(bl) == -1) {
84 /* This block is not reachable from Start */
87 return get_pdom_info(bl)->idom;
90 void set_Block_ipostdom(ir_node *bl, ir_node *n) {
91 ir_dom_info *bli = get_pdom_info(bl);
95 /* Set the immediate post dominator of bl to n */
99 * If we don't set the root of the post dominator tree
100 * Append bl to the post dominates queue of n.
103 ir_dom_info *ni = get_pdom_info(n);
105 bli->next = ni->first;
110 int get_Block_dom_pre_num(const ir_node *bl) {
111 assert(is_Block(bl));
112 return get_dom_info(bl)->pre_num;
115 void set_Block_dom_pre_num(ir_node *bl, int num) {
116 assert(is_Block(bl));
117 get_dom_info(bl)->pre_num = num;
120 int get_Block_dom_depth(const ir_node *bl) {
121 assert(is_Block(bl));
122 return get_dom_info(bl)->dom_depth;
125 void set_Block_dom_depth(ir_node *bl, int depth) {
126 assert(is_Block(bl));
127 get_dom_info(bl)->dom_depth = depth;
131 int get_Block_postdom_pre_num(const ir_node *bl) {
132 assert(is_Block(bl));
133 return get_pdom_info(bl)->pre_num;
136 void set_Block_postdom_pre_num(ir_node *bl, int num) {
137 assert(is_Block(bl));
138 get_pdom_info(bl)->pre_num = num;
141 int get_Block_postdom_depth(const ir_node *bl) {
142 assert(is_Block(bl));
143 return get_pdom_info(bl)->dom_depth;
146 void set_Block_postdom_depth(ir_node *bl, int depth) {
147 assert(is_Block(bl));
148 get_pdom_info(bl)->dom_depth = depth;
151 unsigned get_Block_dom_tree_pre_num(const ir_node *bl) {
152 assert(is_Block(bl));
153 return get_dom_info(bl)->tree_pre_num;
156 unsigned get_Block_dom_max_subtree_pre_num(const ir_node *bl) {
157 assert(is_Block(bl));
158 return get_dom_info(bl)->max_subtree_pre_num;
161 unsigned get_Block_pdom_tree_pre_num(const ir_node *bl) {
162 assert(is_Block(bl));
163 return get_pdom_info(bl)->tree_pre_num;
166 unsigned get_Block_pdom_max_subtree_pre_num(const ir_node *bl) {
167 assert(is_Block(bl));
168 return get_pdom_info(bl)->max_subtree_pre_num;
171 /* Check, if a block dominates another block. */
172 int block_dominates(const ir_node *a, const ir_node *b) {
173 const ir_dom_info *ai, *bi;
175 if (is_Block(a) && is_Block(b)) {
176 ai = get_dom_info(a);
177 bi = get_dom_info(b);
178 return bi->tree_pre_num - ai->tree_pre_num
179 <= ai->max_subtree_pre_num - ai->tree_pre_num;
185 /* Check, if a block strictly dominates another block. */
186 int block_strictly_dominates(const ir_node *a, const ir_node *b) {
187 return (a != b) && block_dominates(a, b);
190 /* Returns the smallest common dominator block of two nodes. */
191 ir_node *node_smallest_common_dominator(ir_node *a, ir_node *b) {
192 ir_node *bl_a = is_Block(a) ? a : get_nodes_block(a);
193 ir_node *bl_b = is_Block(b) ? b : get_nodes_block(b);
194 ir_node *dom_bl = NULL;
196 /* Check if block of a dominates block of b */
197 if (block_dominates(bl_a, bl_b))
199 /* Check if block of b dominates block of a */
200 else if (block_dominates(bl_b, bl_a))
203 /* walk up dominator tree and search for first block dominating a and b */
205 bl_a = get_Block_idom(bl_a);
207 assert(! is_Bad(bl_a) && "block is dead?");
209 if (block_dominates(bl_a, bl_b))
217 /* Returns the smallest common dominator block of all users of a node. */
218 ir_node *node_users_smallest_common_dominator(ir_node *irn, int handle_phi) {
219 int n, j, i = 0, success;
220 ir_node **user_blocks, *dom_bl;
221 const ir_edge_t *edge;
223 assert(! is_Block(irn) && "WRONG USAGE of node_users_smallest_common_dominator");
224 assert(edges_activated(get_irn_irg(irn)) && "need edges activated");
226 n = get_irn_n_edges(irn);
228 /* get array to hold all block of the node users */
229 NEW_ARR_A(ir_node *, user_blocks, n);
230 foreach_out_edge(irn, edge) {
231 ir_node *src = get_edge_src_irn(edge);
233 if (is_Phi(src) && handle_phi) {
234 /* get the corresponding cfg predecessor block if phi handling requested */
235 j = get_edge_src_pos(edge);
236 assert(j >= 0 && "kaputt");
237 user_blocks[i++] = get_Block_cfgpred_block(get_nodes_block(src), j);
240 user_blocks[i++] = is_Block(src) ? src : get_nodes_block(src);
243 assert(i == n && "get_irn_n_edges probably broken");
245 /* in case of only one user: return the block of the user */
247 return user_blocks[0];
250 /* search the smallest block dominating all user blocks */
252 dom_bl = node_smallest_common_dominator(user_blocks[i], user_blocks[i + 1]);
255 /* check if this block dominates all remaining blocks as well */
256 for (j = i + 2; j < n; j++) {
257 if (! block_dominates(dom_bl, user_blocks[j]))
264 /* inherit the dominator block of the first (i + 1) users */
265 user_blocks[++i] = dom_bl;
268 assert(success && "no block found dominating all users");
274 /* Get the first node in the list of nodes dominated by a given block. */
275 ir_node *get_Block_dominated_first(const ir_node *bl) {
276 assert(is_Block(bl));
277 return get_dom_info(bl)->first;
280 /* Get the next node in a list of nodes which are dominated by some
282 ir_node *get_Block_dominated_next(const ir_node *bl) {
283 assert(is_Block(bl));
284 return get_dom_info(bl)->next;
287 /* Check, if a block post dominates another block. */
288 int block_postdominates(const ir_node *a, const ir_node *b) {
289 const ir_dom_info *ai, *bi;
291 if (is_Block(a) && is_Block(b)) {
292 ai = get_pdom_info(a);
293 bi = get_pdom_info(b);
294 return bi->tree_pre_num - ai->tree_pre_num
295 <= ai->max_subtree_pre_num - ai->tree_pre_num;
301 /* Check, if a block strictly dominates another block. */
302 int block_strictly_postdominates(const ir_node *a, const ir_node *b) {
303 return (a != b) && block_postdominates(a, b);
307 /* Get the first node in the list of nodes post dominated by a given block. */
308 ir_node *get_Block_postdominated_first(const ir_node *bl) {
309 assert(is_Block(bl));
310 return get_pdom_info(bl)->first;
313 /* Get the next node in a list of nodes which are post dominated by some
315 ir_node *get_Block_postdominated_next(const ir_node *bl) {
316 assert(is_Block(bl));
317 return get_pdom_info(bl)->next;
320 /* Visit all nodes in the dominator subtree of a given node. */
321 void dom_tree_walk(ir_node *bl, irg_walk_func *pre,
322 irg_walk_func *post, void *env)
329 dominates_for_each(bl, p) {
330 dom_tree_walk(p, pre, post, env);
337 /* Visit all nodes in the post dominator subtree of a given node. */
338 void postdom_tree_walk(ir_node *bl, irg_walk_func *pre,
339 irg_walk_func *post, void *env)
346 postdominates_for_each(bl, p) {
347 postdom_tree_walk(p, pre, post, env);
354 /* Walk over the dominator tree of an irg starting at the root. */
355 void dom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
356 irg_walk_func *post, void *env)
358 /* The root of the dominator tree should be the Start block. */
359 ir_node *root = get_irg_start_block(irg);
361 assert(irg->dom_state == dom_consistent
362 && "The dominators of the irg must be consistent");
363 assert(root && "The start block of the graph is NULL?");
364 assert(get_dom_info(root)->idom == NULL
365 && "The start node in the graph must be the root of the dominator tree");
366 dom_tree_walk(root, pre, post, env);
369 /* Walk over the post dominator tree of an irg starting at the root. */
370 void postdom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
371 irg_walk_func *post, void *env)
373 /* The root of the dominator tree should be the End block. */
374 ir_node *root = get_irg_end_block(irg);
376 assert(irg->pdom_state == dom_consistent
377 && "The dominators of the irg must be consistent");
378 assert(root && "The end block of the graph is NULL?");
379 assert(get_pdom_info(root)->idom == NULL
380 && "The End block node in the graph must be the root of the post dominator tree");
381 postdom_tree_walk(root, pre, post, env);
385 static void assign_tree_dom_pre_order(ir_node *bl, void *data)
387 unsigned *num = data;
388 ir_dom_info *bi = get_dom_info(bl);
390 bi->tree_pre_num = (*num)++;
393 static void assign_tree_dom_pre_order_max(ir_node *bl, void *data)
395 ir_dom_info *bi = get_dom_info(bl);
398 unsigned children = 0;
401 for(p = bi->first; p; p = get_dom_info(p)->next) {
402 unsigned max_p = get_dom_info(p)->max_subtree_pre_num;
403 max = max > max_p ? max : max_p;
407 bi->max_subtree_pre_num = children > 0 ? max : bi->tree_pre_num;
408 assert(bi->max_subtree_pre_num >= bi->tree_pre_num);
411 static void assign_tree_postdom_pre_order(ir_node *bl, void *data)
413 unsigned *num = data;
414 ir_dom_info *bi = get_pdom_info(bl);
416 bi->tree_pre_num = (*num)++;
419 static void assign_tree_postdom_pre_order_max(ir_node *bl, void *data)
421 ir_dom_info *bi = get_pdom_info(bl);
424 unsigned children = 0;
427 for(p = bi->first; p; p = get_pdom_info(p)->next) {
428 unsigned max_p = get_pdom_info(p)->max_subtree_pre_num;
429 max = max > max_p ? max : max_p;
433 bi->max_subtree_pre_num = children > 0 ? max : bi->tree_pre_num;
434 assert(bi->max_subtree_pre_num >= bi->tree_pre_num);
437 /*--------------------------------------------------------------------*/
438 /* Building and Removing the dominator data structure */
439 /*--------------------------------------------------------------------*/
442 * count the number of blocks and clears the post dominance info
444 static void count_and_init_blocks_pdom(ir_node *bl, void *env) {
445 int *n_blocks = (int *) env;
448 memset(get_pdom_info(bl), 0, sizeof(ir_dom_info));
449 set_Block_ipostdom(bl, NULL);
450 set_Block_postdom_pre_num(bl, -1);
451 set_Block_postdom_depth(bl, -1);
454 /** temporary type used while constructing the dominator / post dominator tree. */
455 typedef struct tmp_dom_info {
456 ir_node *block; /**< backlink */
458 struct tmp_dom_info *semi; /**< semidominator */
459 struct tmp_dom_info *parent;
460 struct tmp_dom_info *label; /**< used for LINK and EVAL */
461 struct tmp_dom_info *ancestor;/**< used for LINK and EVAL */
462 struct tmp_dom_info *dom; /**< After step 3, if the semidominator of w is
463 its immediate dominator, then w->dom is the
464 immediate dominator of w. Otherwise w->dom
465 is a vertex v whose number is smaller than
466 w and whose immediate dominator is also w's
467 immediate dominator. After step 4, w->dom
468 is the immediate dominator of w. */
469 struct tmp_dom_info *bucket; /**< set of vertices with same semidominator */
472 /** Struct to pass info through walker. */
480 * Walks Blocks along the out data structure. If recursion started with
481 * Start block misses control dead blocks.
483 static void init_tmp_dom_info(ir_node *bl, tmp_dom_info *parent,
484 tmp_dom_info *tdi_list, int *used, int n_blocks) {
488 assert(is_Block(bl));
489 if (get_irg_block_visited(current_ir_graph) == get_Block_block_visited(bl))
491 mark_Block_block_visited(bl);
492 set_Block_dom_pre_num(bl, *used);
494 assert(*used < n_blocks);
495 tdi = &tdi_list[*used];
500 tdi->ancestor = NULL;
502 tdi->parent = parent;
506 for (i = get_Block_n_cfg_outs_ka(bl) - 1; i >= 0; --i) {
507 ir_node *pred = get_Block_cfg_out_ka(bl, i);
508 assert(is_Block(pred));
509 init_tmp_dom_info(pred, tdi, tdi_list, used, n_blocks);
514 * Walks Blocks along the control flow. If recursion started with
515 * End block misses blocks in endless loops.
517 static void init_tmp_pdom_info(ir_node *bl, tmp_dom_info *parent,
518 tmp_dom_info *tdi_list, int* used, int n_blocks) {
522 assert(is_Block(bl));
523 if (get_irg_block_visited(current_ir_graph) == get_Block_block_visited(bl))
525 mark_Block_block_visited(bl);
526 set_Block_postdom_pre_num(bl, *used);
528 assert(*used < n_blocks);
529 tdi = &tdi_list[*used];
534 tdi->ancestor = NULL;
536 tdi->parent = parent;
540 for (i = get_Block_n_cfgpreds(bl) - 1; i >= 0; --i) {
541 ir_node *pred = get_Block_cfgpred_block(bl, i);
544 assert(is_Block(pred));
545 init_tmp_pdom_info(pred, tdi, tdi_list, used, n_blocks);
548 /* Handle keep-alives. Note that the preprocessing
549 in init_construction() had already killed all
550 phantom keep-alive edges. All remaining block keep-alives
551 are really edges to endless loops.
553 if (bl == get_irg_end_block(current_ir_graph)) {
554 ir_node *end = get_irg_end(current_ir_graph);
556 for (i = get_irn_arity(end) - 1; i >= 0; --i) {
557 ir_node *pred = get_irn_n(end, i);
560 init_tmp_pdom_info(pred, tdi, tdi_list, used, n_blocks);
565 static void dom_compress(tmp_dom_info *v) {
566 assert (v->ancestor);
567 if (v->ancestor->ancestor) {
568 dom_compress (v->ancestor);
569 if (v->ancestor->label->semi < v->label->semi) {
570 v->label = v->ancestor->label;
572 v->ancestor = v->ancestor->ancestor;
577 * if V is a root, return v, else return the vertex u, not being the
578 * root, with minimum u->semi on the path from v to its root.
580 inline static tmp_dom_info *dom_eval(tmp_dom_info *v) {
581 if (!v->ancestor) return v;
586 /** make V W's ancestor */
587 inline static void dom_link(tmp_dom_info *v, tmp_dom_info *w) {
592 * Walker: count the number of blocks and clears the dominance info
594 static void count_and_init_blocks_dom(ir_node *bl, void *env) {
595 int *n_blocks = (int *) env;
598 memset(get_dom_info(bl), 0, sizeof(ir_dom_info));
599 set_Block_idom(bl, NULL);
600 set_Block_dom_pre_num(bl, -1);
601 set_Block_dom_depth(bl, -1);
605 * Initialize the dominance/postdominance construction:
607 * - count the number of blocks
608 * - clear the dominance info
609 * - remove Block-keepalives of live blocks to reduce
610 * the number of "phantom" block edges
612 * @param irg the graph
613 * @param pre a walker function that will be called for every block in the graph
615 static int init_construction(ir_graph *irg, irg_walk_func *pre) {
616 ir_graph *rem = current_ir_graph;
621 current_ir_graph = irg;
623 /* this visits only the reachable blocks */
624 irg_block_walk(get_irg_end_block(irg), pre, NULL, &n_blocks);
626 /* now visit the unreachable (from End) Blocks and remove unnecessary keep-alives */
627 end = get_irg_end(irg);
628 arity = get_End_n_keepalives(end);
629 if (arity) { /* we have keep-alives */
633 NEW_ARR_A(ir_node *, in, arity);
634 for (i = j = 0; i < arity; i++) {
635 ir_node *pred = get_End_keepalive(end, i);
637 if (is_Block(pred)) {
638 if (Block_block_visited(pred))
641 /* we found an endless loop */
642 dec_irg_block_visited(irg);
643 irg_block_walk(pred, pre, NULL, &n_blocks);
648 /* we kill some Block keep-alives */
649 set_End_keepalives(end, j, in);
650 set_irg_outs_inconsistent(irg);
654 current_ir_graph = rem;
659 /* Computes the dominator trees. Sets a flag in irg to "dom_consistent".
660 If the control flow of the graph is changed this flag must be set to
661 "dom_inconsistent". */
662 void compute_doms(ir_graph *irg) {
663 ir_graph *rem = current_ir_graph;
664 int n_blocks, used, i, j;
665 tmp_dom_info *tdi_list; /* Ein Golf? */
667 current_ir_graph = irg;
669 /* Update graph state */
670 assert(get_irg_phase_state(irg) != phase_building);
671 irg->dom_state = dom_consistent;
673 /* Count the number of blocks in the graph. */
674 n_blocks = init_construction(irg, count_and_init_blocks_dom);
676 /* Memory for temporary information. */
677 tdi_list = XMALLOCNZ(tmp_dom_info, n_blocks);
679 /* We need the out data structure. */
680 assure_irg_outs(irg);
682 /* this with a standard walker as passing the parent to the sons isn't
685 inc_irg_block_visited(irg);
686 init_tmp_dom_info(get_irg_start_block(irg), NULL, tdi_list, &used, n_blocks);
687 /* If not all blocks are reachable from Start by out edges this assertion
689 assert(used == n_blocks && "Precondition for dom construction violated"); */
690 assert(used <= n_blocks && "Precondition for dom construction violated");
694 for (i = n_blocks-1; i > 0; i--) { /* Don't iterate the root, it's done. */
696 tmp_dom_info *w = &tdi_list[i];
700 irn_arity = get_irn_arity(w->block);
701 for (j = 0; j < irn_arity; j++) {
702 ir_node *pred = get_Block_cfgpred_block(w->block, j);
705 if (is_Bad(pred) || (get_Block_dom_pre_num (pred) == -1))
706 continue; /* control-dead */
708 u = dom_eval (&tdi_list[get_Block_dom_pre_num(pred)]);
709 if (u->semi < w->semi) w->semi = u->semi;
712 /* handle keep-alives if we are at the end block */
713 if (w->block == get_irg_end_block(irg)) {
714 ir_node *end = get_irg_end(irg);
716 irn_arity = get_irn_arity(end);
717 for (j = 0; j < irn_arity; j++) {
718 ir_node *pred = get_irn_n(end, j);
721 if (is_no_Block(pred) || get_Block_dom_pre_num(pred) == -1)
722 continue; /* control-dead */
724 u = dom_eval (&tdi_list[get_Block_dom_pre_num(pred)]);
725 if (u->semi < w->semi) w->semi = u->semi;
729 /* Add w to w->semi's bucket. w is in exactly one bucket, so
730 buckets can been implemented as linked lists. */
731 w->bucket = w->semi->bucket;
734 dom_link (w->parent, w);
737 while (w->parent->bucket) {
739 v = w->parent->bucket;
740 /* remove v from w->parent->bucket */
741 w->parent->bucket = v->bucket;
745 if (u->semi < v->semi)
752 tdi_list[0].dom = NULL;
753 set_Block_idom(tdi_list[0].block, NULL);
754 set_Block_dom_depth(tdi_list[0].block, 1);
755 for (i = 1; i < n_blocks; i++) {
756 tmp_dom_info *w = &tdi_list[i];
760 continue; /* control dead */
762 if (w->dom != w->semi) w->dom = w->dom->dom;
763 set_Block_idom(w->block, w->dom->block);
765 /* blocks dominated by dead one's are still dead */
766 depth = get_Block_dom_depth(w->dom->block);
769 set_Block_dom_depth(w->block, depth);
775 /* Do a walk over the tree and assign the tree pre orders. */
777 unsigned tree_pre_order = 0;
778 dom_tree_walk_irg(irg, assign_tree_dom_pre_order,
779 assign_tree_dom_pre_order_max, &tree_pre_order);
781 current_ir_graph = rem;
784 void assure_doms(ir_graph *irg) {
785 if (get_irg_dom_state(irg) != dom_consistent)
789 void free_dom(ir_graph *irg) {
790 /* Update graph state */
791 assert(get_irg_phase_state(irg) != phase_building);
792 irg->dom_state = dom_none;
794 /* With the implementation right now there is nothing to free,
795 but better call it anyways... */
798 /* Computes the post dominator trees. Sets a flag in irg to "dom_consistent".
799 If the control flow of the graph is changed this flag must be set to
800 "dom_inconsistent". */
801 void compute_postdoms(ir_graph *irg) {
802 ir_graph *rem = current_ir_graph;
803 int n_blocks, used, i, j;
804 tmp_dom_info *tdi_list;
806 current_ir_graph = irg;
808 /* Update graph state */
809 assert(get_irg_phase_state(irg) != phase_building);
810 irg->pdom_state = dom_consistent;
812 /* Count the number of blocks in the graph. */
813 n_blocks = init_construction(irg, count_and_init_blocks_pdom);
815 /* Memory for temporary information. */
816 tdi_list = XMALLOCNZ(tmp_dom_info, n_blocks);
818 /* We need the out data structure. */
819 assure_irg_outs(irg);
821 /* this with a standard walker as passing the parent to the sons isn't
824 inc_irg_block_visited(irg);
825 init_tmp_pdom_info(get_irg_end_block(irg), NULL, tdi_list, &used, n_blocks);
826 /* If not all blocks are reachable from End by cfg edges this assertion
828 assert(used == n_blocks && "Precondition for dom construction violated"); */
832 for (i = n_blocks-1; i > 0; i--) { /* Don't iterate the root, it's done. */
834 tmp_dom_info *w = &tdi_list[i];
838 irn_arity = get_Block_n_cfg_outs_ka(w->block);
839 for (j = 0; j < irn_arity; j++) {
840 ir_node *succ = get_Block_cfg_out_ka(w->block, j);
843 if (get_Block_postdom_pre_num (succ) == -1)
844 continue; /* endless-loop */
846 u = dom_eval (&tdi_list[get_Block_postdom_pre_num(succ)]);
847 if (u->semi < w->semi) w->semi = u->semi;
849 /* Add w to w->semi's bucket. w is in exactly one bucket, so
850 buckets can be implemented as linked lists. */
851 w->bucket = w->semi->bucket;
854 dom_link (w->parent, w);
857 while (w->parent->bucket) {
859 v = w->parent->bucket;
860 /* remove v from w->parent->bucket */
861 w->parent->bucket = v->bucket;
865 if (u->semi < v->semi)
872 tdi_list[0].dom = NULL;
873 set_Block_ipostdom(tdi_list[0].block, NULL);
874 set_Block_postdom_depth(tdi_list[0].block, 1);
875 for (i = 1; i < n_blocks; i++) {
876 tmp_dom_info *w = &tdi_list[i];
878 if (w->dom != w->semi) w->dom = w->dom->dom;
879 set_Block_ipostdom(w->block, w->dom->block);
880 set_Block_postdom_depth(w->block, get_Block_postdom_depth(w->dom->block) + 1);
886 /* Do a walk over the tree and assign the tree pre orders. */
888 unsigned tree_pre_order = 0;
889 postdom_tree_walk_irg(irg, assign_tree_postdom_pre_order,
890 assign_tree_postdom_pre_order_max, &tree_pre_order);
892 current_ir_graph = rem;
895 void assure_postdoms(ir_graph *irg) {
896 if (get_irg_postdom_state(irg) != dom_consistent)
897 compute_postdoms(irg);
900 void free_postdom(ir_graph *irg) {
901 /* Update graph state */
902 assert(get_irg_phase_state(irg) != phase_building);
903 irg->pdom_state = dom_none;
905 /* With the implementation right now there is nothing to free,
906 but better call it anyways... */