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
30 #include "firm_types.h"
33 /** Accessing the dominator data structure.
35 * These routines only work properly if the ir_graph is in state
36 * dom_consistent or dom_inconsistent.
38 * If the block is not reachable from Start, returns a Bad node.
40 ir_node *get_Block_idom(const ir_node *bl);
41 void set_Block_idom(ir_node *bl, ir_node *n);
43 int get_Block_dom_depth(const ir_node *bl);
44 void set_Block_dom_depth(ir_node *bl, int depth);
46 int get_Block_dom_pre_num(const ir_node *bl);
47 void set_Block_dom_pre_num(ir_node *bl, int num);
49 /** Accessing the post dominator data structure.
51 * These routines only work properly if the ir_graph is in state
52 * dom_consistent or dom_inconsistent.
54 * If the block is not reachable from End, returns a Bad node.
56 ir_node *get_Block_ipostdom(const ir_node *bl);
57 void set_Block_ipostdom(ir_node *bl, ir_node *n);
59 int get_Block_postdom_depth(const ir_node *bl);
60 void set_Block_postdom_depth(ir_node *bl, int depth);
62 int get_Block_postdom_pre_num(const ir_node *bl);
63 void set_Block_postdom_pre_num(ir_node *bl, int num);
66 * Get the pre-order number of a block resulting from a
67 * Depth-First-Search walkover the dominator tree.
69 * @param bl The block.
70 * @return The pre-order number.
72 unsigned get_Block_dom_tree_pre_num(const ir_node *bl);
75 * Get the largest pre-order number found in the subtree of the
76 * dominator tree rooted at a given block.
77 * @param bl The block.
78 * @return The largest pre-order number of block's dominator subtree.
80 unsigned get_Block_dom_max_subtree_pre_num(const ir_node *bl);
83 * Get the first node in the list of nodes dominated by a given block.
85 * Each node keeps a list of nodes which it immediately dominates. The
86 * nodes are queued using the @c next pointer in the @c dom_info struct.
87 * Each node keeps a head of this list using the pointer @c first in the
90 * @param bl The block for which to get the first node dominated by @c bl.
91 * @return The first node dominated by @p bl.
93 ir_node *get_Block_dominated_first(const ir_node *bl);
96 * Get the next node in a list of nodes which are dominated by some
98 * @see get_Block_dominated_first().
99 * @param dom The previous node.
100 * @return The next node in this list or NULL if it was the last.
102 ir_node *get_Block_dominated_next(const ir_node *dom);
105 * Iterate over all nodes which are immediately dominated by a given
107 * @param bl The block whose dominated blocks shall be iterated on.
108 * @param curr An iterator variable of type ir_node*
110 #define dominates_for_each(bl,curr) \
111 for(curr = get_Block_dominated_first(bl); curr; \
112 curr = get_Block_dominated_next(curr))
115 * Iterate over all nodes which are immediately post dominated by a given
117 * @param bl The block whose post dominated blocks shall be iterated on.
118 * @param curr An iterator variable of type ir_node*
120 #define postdominates_for_each(bl,curr) \
121 for(curr = get_Block_postdominated_first(bl); curr; \
122 curr = get_Block_postdominated_next(curr))
125 * Check, if a block dominates another block.
126 * @param a The first block.
127 * @param b The second block.
128 * @return 1, if @p a dominates @p b, else 0.
130 int block_dominates(const ir_node *a, const ir_node *b);
133 * Returns the smallest common dominator block of two nodes.
135 * @param b Another node.
136 * @return The first block dominating @p a and @p b
138 ir_node *node_smallest_common_dominator(ir_node *a, ir_node *b);
141 * Returns the smallest common dominator block of all users of a node
142 * BEWARE: @p irn must not be a block
143 * If on or more users are Phi nodes, one can request special handling
144 * with @p handle_phi = 1. In this case the cfg predecessor block
145 * corresponding to the position of the irn in the argument list of the
146 * Phi is determined and treated as user.
149 * @param handle_phi 1 if Phis should be handled different
150 * @return The first block dominating all users of @irn
152 ir_node *node_users_smallest_common_dominator(ir_node *irn, int handle_phi);
155 * Check, if a block post dominates another block.
156 * @param a The first block.
157 * @param b The second block.
158 * @return 1, if @p a post dominates @p b, else 0.
160 int block_postdominates(const ir_node *a, const ir_node *b);
163 * Visit all nodes in the dominator subtree of a given node.
164 * Call a pre-visitor before descending to the children and call a
165 * post-visitor after returning from them.
166 * @param n The node to start walking from.
167 * @param pre The pre-visitor callback.
168 * @param post The post-visitor callback.
169 * @param env Some custom data passed to the visitors.
171 void dom_tree_walk(ir_node *n, irg_walk_func *pre,
172 irg_walk_func *post, void *env);
175 * Visit all nodes in the post dominator subtree of a given node.
176 * Call a pre-visitor before descending to the children and call a
177 * post-visitor after returning from them.
178 * @param n The node to start walking from.
179 * @param pre The pre-visitor callback.
180 * @param post The post-visitor callback.
181 * @param env Some custom data passed to the visitors.
183 void postdom_tree_walk(ir_node *n, irg_walk_func *pre,
184 irg_walk_func *post, void *env);
187 * Walk over the dominator tree of an irg starting at the root.
188 * @param irg The graph.
189 * @param pre A pre-visitor to call.
190 * @param post A post-visitor to call.
191 * @param env Some private data to give to the visitors.
193 void dom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
194 irg_walk_func *post, void *env);
197 * Walk over the post dominator tree of an irg starting at the root.
198 * @param irg The graph.
199 * @param pre A pre-visitor to call.
200 * @param post A post-visitor to call.
201 * @param env Some private data to give to the visitors.
203 void postdom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
204 irg_walk_func *post, void *env);
206 /* ------------ Building and Removing the dominator data structure ----------- */
208 /** Computes the dominator trees.
210 * Sets a flag in irg to "dom_consistent".
211 * If the control flow of the graph is changed this flag must be set to
212 * "dom_inconsistent".
213 * Does not compute dominator information for control dead code. Blocks
214 * not reachable from Start contain the following information:
220 * Also constructs outs information. As this information is correct after
221 * the run does not free the outs information.
223 void compute_doms(ir_graph *irg);
225 /** Computes the dominator trees on demand */
226 void assure_doms(ir_graph *irg);
228 /** Computes the post dominator trees.
230 * Sets a flag in irg to "dom_consistent".
231 * If the control flow of the graph is changed this flag must be set to
232 * "dom_inconsistent".
233 * Does not compute post dominator information for endless lops. Blocks
234 * not reachable from End contain the following information:
240 * Also constructs outs information. As this information is correct after
241 * the run does not free the outs information.
243 void compute_postdoms(ir_graph *irg);
245 /** Computes the dominator trees on demand */
246 void assure_postdoms(ir_graph *irg);
248 /** Frees the dominator data structures. Sets the flag in irg to "dom_none". */
249 void free_dom(ir_graph *irg);
251 /** Frees the post dominator data structures. Sets the flag in irg to "dom_none". */
252 void free_postdom(ir_graph *irg);
254 #endif /* _IRDOM_H_ */