3 * File name: ir/ana/irdom.h
4 * Purpose: Construct and access dominator tree.
5 * Author: Goetz Lindenmaier
9 * Copyright: (c) 2002-2003 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
16 * This file contains routines to construct and access dominator information.
18 * The dominator information is stored in three fields of block nodes:
19 * - idom: a reference to the block that is the immediate dominator of
21 * - dom_depth: a number giving the depth of the block in the dominator
23 * - pre_num: Number in preorder traversal.
25 * @author Goetz Lindenmaier
37 /** Accessing the dominator datastructure.
39 * These routines only work properly if the ir_graph is in state
40 * dom_consistent or dom_inconsistent.
42 * If the block is not reachable from Start, returns a Bad node.
44 ir_node *get_Block_idom(const ir_node *bl);
45 void set_Block_idom(ir_node *bl, ir_node *n);
47 int get_Block_dom_depth(const ir_node *bl);
48 void set_Block_dom_depth(ir_node *bl, int depth);
50 int get_Block_pre_num(const ir_node *bl);
51 void set_Block_pre_num(ir_node *bl, int num);
54 * Get the pre-order number of a block resulting from a dfs walk
55 * over the dominator tree.
56 * @param bl The block.
57 * @return The pre-order number.
59 unsigned get_Block_dom_tree_pre_num(const ir_node *bl);
62 * Get the largest pre-order number found in the subtree of the
63 * dominator tree rooted at a given block.
64 * @param bl The block.
65 * @return The largest pre-order number of block's dominator subtree.
67 unsigned get_Block_dom_max_subtree_pre_num(const ir_node *bl);
70 * Get the first node in the list of nodes dominated by a given block.
72 * Each node keeps a list of nodes which it immediately dominates. The
73 * nodes are queued using the @c next pointer in the @c dom_info struct.
74 * Each node keeps a head of this list using the pointer @c first in the
77 * @param bl The block for which to get the first node dominated by @c bl.
78 * @return The first node dominated by @p bl.
80 ir_node *get_Block_dominated_first(const ir_node *bl);
83 * Get the next node in a list of nodes which are dominated by some
85 * @see get_Block_dominated_first().
86 * @param dom The previous node.
87 * @return The next node in this list or NULL if it was the last.
89 ir_node *get_Block_dominated_next(const ir_node *dom);
92 * Check, if a block dominates another block.
93 * @param a The first block.
94 * @param b The second block.
95 * @return 1, if @p a dominates @p b, else 0.
97 int block_dominates(const ir_node *a, const ir_node *b);
100 * Visit all nodes in the dominator subtree of a given node.
101 * Call a pre-visitor before descending to the children and call a
102 * post-visitor after returning from them.
103 * @param n The node to start walking from.
104 * @param pre The pre-visitor callback.
105 * @param post The post-visitor callback.
106 * @param env Some custom data passed to the visitors.
108 void dom_tree_walk(ir_node *n, irg_walk_func *pre,
109 irg_walk_func *post, void *env);
113 * Walk over the dominator tree of an irg starting at the root.
114 * @param irg The graph.
115 * @param pre A pre-visitor to call.
116 * @param post A post-visitor to call.
117 * @param env Some private data to give to the visitors.
119 void dom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
120 irg_walk_func *post, void *env);
122 /* ------------ Building and Removing the dominator datasturcture ----------- */
124 /** Computes the dominator trees.
126 * Sets a flag in irg to "dom_consistent".
127 * If the control flow of the graph is changed this flag must be set to
128 * "dom_inconsistent".
129 * Does not compute dominator information for control dead code. Blocks
130 * not reachable from Start contain the following information:
134 * Also constructs outs information. As this information is correct after
135 * the run does not free the outs information.
137 void compute_doms(ir_graph *irg);
139 /** Frees the dominator datastructures. Sets the flag in irg to "dom_none". */
140 void free_dom_and_peace(ir_graph *irg);
142 #endif /* _IRDOM_H_ */