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 tree.
23 * @author Goetz Lindenmaier
25 * @brief This file contains routines to construct and access dominator information.
27 #ifndef FIRM_ANA_IRDOM_H
28 #define FIRM_ANA_IRDOM_H
30 #include "firm_types.h"
33 /** @defgroup irana Analyses */
37 * @defgroup irdom Dominance Information
39 * The dominator information is stored in three fields of block nodes:
40 * - idom: a reference to the block that is the immediate dominator of
42 * - dom_depth: a number giving the depth of the block in the dominator
44 * - pre_num: Number in preorder traversal.
46 * We generally presume (like Tarjan) that endless loops do not exist. The
47 * implementation assumes a control dependency from End to loop header.
52 /** Accessing the dominator data structure.
54 * These routines only work properly if the ir_graph is in state
55 * dom_consistent or dom_inconsistent.
57 * If the block is not reachable from Start, returns a Bad node.
59 FIRM_API ir_node *get_Block_idom(const ir_node *bl);
60 FIRM_API void set_Block_idom(ir_node *bl, ir_node *n);
62 FIRM_API int get_Block_dom_depth(const ir_node *bl);
63 FIRM_API void set_Block_dom_depth(ir_node *bl, int depth);
65 FIRM_API int get_Block_dom_pre_num(const ir_node *bl);
66 FIRM_API void set_Block_dom_pre_num(ir_node *bl, int num);
68 /** Accessing the post dominator data structure.
70 * These routines only work properly if the ir_graph is in state
71 * dom_consistent or dom_inconsistent.
73 FIRM_API ir_node *get_Block_ipostdom(const ir_node *bl);
74 FIRM_API void set_Block_ipostdom(ir_node *bl, ir_node *n);
76 FIRM_API int get_Block_postdom_depth(const ir_node *bl);
77 FIRM_API void set_Block_postdom_depth(ir_node *bl, int depth);
79 FIRM_API int get_Block_postdom_pre_num(const ir_node *bl);
80 FIRM_API void set_Block_postdom_pre_num(ir_node *bl, int num);
83 * Get the pre-order number of a block resulting from a
84 * Depth-First-Search walkover the dominator tree.
86 * @param bl The block.
87 * @return The pre-order number.
89 FIRM_API unsigned get_Block_dom_tree_pre_num(const ir_node *bl);
90 FIRM_API unsigned get_Block_pdom_tree_pre_num(const ir_node *bl);
93 * Get the largest pre-order number found in the subtree of the
94 * dominator tree rooted at a given block.
95 * @param bl The block.
96 * @return The largest pre-order number of block's dominator subtree.
98 FIRM_API unsigned get_Block_dom_max_subtree_pre_num(const ir_node *bl);
99 FIRM_API unsigned get_Block_pdom_max_subtree_pre_num(const ir_node *bl);
102 * Get the first node in the list of nodes dominated by a given block.
104 * Each node keeps a list of nodes which it immediately dominates. The
105 * nodes are queued using the @c next pointer in the @c dom_info struct.
106 * Each node keeps a head of this list using the pointer @c first in the
109 * @param bl The block for which to get the first node dominated by @c bl.
110 * @return The first node dominated by @p bl.
112 FIRM_API ir_node *get_Block_dominated_first(const ir_node *bl);
113 FIRM_API ir_node *get_Block_postdominated_first(const ir_node *bl);
116 * Get the next node in a list of nodes which are dominated by some
118 * @see get_Block_dominated_first().
119 * @param dom The previous node.
120 * @return The next node in this list or NULL if it was the last.
122 FIRM_API ir_node *get_Block_dominated_next(const ir_node *dom);
123 FIRM_API ir_node *get_Block_postdominated_next(const ir_node *dom);
126 * Iterate over all nodes which are immediately dominated by a given
128 * @param bl The block whose dominated blocks shall be iterated on.
129 * @param curr An iterator variable of type ir_node*
131 #define dominates_for_each(bl,curr) \
132 for(curr = get_Block_dominated_first(bl); curr; \
133 curr = get_Block_dominated_next(curr))
136 * Iterate over all nodes which are immediately post dominated by a given
138 * @param bl The block whose post dominated blocks shall be iterated on.
139 * @param curr An iterator variable of type ir_node*
141 #define postdominates_for_each(bl,curr) \
142 for(curr = get_Block_postdominated_first(bl); curr; \
143 curr = get_Block_postdominated_next(curr))
146 * Check, if a block dominates another block.
148 * @param a The potential dominator block.
149 * @param b The potentially dominated block.
151 * @return 1, if @p a dominates @p b, else 0.
153 FIRM_API int block_dominates(const ir_node *a, const ir_node *b);
156 * Check, if a block strictly dominates another block, i.e. a != b.
158 * @param a The potential dominator block.
159 * @param b The potentially dominated block.
161 * @return 1, if @p a strictly dominates @p b, else 0.
163 FIRM_API int block_strictly_dominates(const ir_node *a, const ir_node *b);
166 * Returns the smallest common dominator block of two nodes.
168 * @param b Another node.
169 * @return The first block dominating @p a and @p b
171 FIRM_API ir_node *node_smallest_common_dominator(ir_node *a, ir_node *b);
174 * Returns the smallest common dominator block of all users of a node
175 * BEWARE: @p irn must not be a block
176 * If on or more users are Phi nodes, one can request special handling
177 * with @p handle_phi = 1. In this case the cfg predecessor block
178 * corresponding to the position of the irn in the argument list of the
179 * Phi is determined and treated as user.
182 * @param handle_phi 1 if Phis should be handled different
183 * @return The first block dominating all users of @p irn
185 FIRM_API ir_node *node_users_smallest_common_dominator(ir_node *irn,
189 * Check, if a block post dominates another block.
191 * @param a The potential post dominator block.
192 * @param b The potentially post dominated block.
194 * @return 1, if @p a post dominates @p b, else 0.
196 FIRM_API int block_postdominates(const ir_node *a, const ir_node *b);
199 * Check, if a block strictly post dominates another block, i.e. a != b.
201 * @param a The potential post dominator block.
202 * @param b The potentially post dominated block.
204 * @return 1, if @p a strictly post dominates @p b, else 0.
206 FIRM_API int block_strictly_postdominates(const ir_node *a, const ir_node *b);
209 * Visit all nodes in the dominator subtree of a given node.
210 * Call a pre-visitor before descending to the children and call a
211 * post-visitor after returning from them.
212 * @param n The node to start walking from.
213 * @param pre The pre-visitor callback.
214 * @param post The post-visitor callback.
215 * @param env Some custom data passed to the visitors.
217 FIRM_API void dom_tree_walk(ir_node *n, irg_walk_func *pre,
218 irg_walk_func *post, void *env);
221 * Visit all nodes in the post dominator subtree of a given node.
222 * Call a pre-visitor before descending to the children and call a
223 * post-visitor after returning from them.
224 * @param n The node to start walking from.
225 * @param pre The pre-visitor callback.
226 * @param post The post-visitor callback.
227 * @param env Some custom data passed to the visitors.
229 FIRM_API void postdom_tree_walk(ir_node *n, irg_walk_func *pre,
230 irg_walk_func *post, void *env);
233 * Walk over the dominator tree of an irg starting at the root.
234 * @param irg The graph.
235 * @param pre A pre-visitor to call.
236 * @param post A post-visitor to call.
237 * @param env Some private data to give to the visitors.
239 FIRM_API void dom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
240 irg_walk_func *post, void *env);
243 * Walk over the post dominator tree of an irg starting at the root.
244 * @param irg The graph.
245 * @param pre A pre-visitor to call.
246 * @param post A post-visitor to call.
247 * @param env Some private data to give to the visitors.
249 FIRM_API void postdom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
250 irg_walk_func *post, void *env);
252 /* ------------ Building and Removing the dominator data structure ----------- */
254 /** Computes the dominator trees.
256 * Sets a flag in irg to "dom_consistent".
257 * If the control flow of the graph is changed this flag must be set to
258 * "dom_inconsistent".
259 * Does not compute dominator information for control dead code. Blocks
260 * not reachable from Start contain the following information:
266 * Also constructs outs information. As this information is correct after
267 * the run does not free the outs information.
269 FIRM_API void compute_doms(ir_graph *irg);
271 /** Computes the dominator trees on demand, @see compute_doms(). */
272 FIRM_API void assure_doms(ir_graph *irg);
274 /** Computes the post dominator trees.
276 * Sets a flag in irg to "dom_consistent".
277 * If the control flow of the graph is changed this flag must be set to
278 * "dom_inconsistent".
279 * Does not compute post dominator information for endless lops. Blocks
280 * not reachable from End contain the following information:
286 * Also constructs outs information. As this information is correct after
287 * the run does not free the outs information.
289 FIRM_API void compute_postdoms(ir_graph *irg);
291 /** Computes the dominator trees on demand */
292 FIRM_API void assure_postdoms(ir_graph *irg);
294 /** Frees the dominator data structures. Sets the flag in irg to "dom_none". */
295 FIRM_API void free_dom(ir_graph *irg);
298 * Frees the post dominator data structures.
299 * Sets the flag in irg to "dom_none".
301 FIRM_API void free_postdom(ir_graph *irg);