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"
35 * @defgroup irdom Dominance Information
37 * The dominator information is stored in three fields of block nodes:
38 * - idom: a reference to the block that is the immediate dominator of
40 * - dom_depth: a number giving the depth of the block in the dominator
42 * - pre_num: Number in preorder traversal.
44 * We generally presume (like Tarjan) that endless loops do not exist. The
45 * implementation assumes a control dependency from End to loop header.
50 /** return immediate dominator of block */
51 FIRM_API ir_node *get_Block_idom(const ir_node *block);
53 /** return immediate postdominator of a block */
54 FIRM_API ir_node *get_Block_ipostdom(const ir_node *block);
57 * Check, if a block dominates another block.
59 * @param a The potential dominator block.
60 * @param b The potentially dominated block.
62 * @return 1, if @p a dominates @p b, else 0.
64 FIRM_API int block_dominates(const ir_node *a, const ir_node *b);
67 * Check, if a block strictly dominates another block, i.e. a != b.
69 * @param a The potential dominator block.
70 * @param b The potentially dominated block.
72 * @return 1, if @p a strictly dominates @p b, else 0.
74 FIRM_API int block_strictly_dominates(const ir_node *a, const ir_node *b);
77 * Check, if a block post dominates another block.
79 * @param a The potential post dominator block.
80 * @param b The potentially post dominated block.
82 * @return 1, if @p a post dominates @p b, else 0.
84 FIRM_API int block_postdominates(const ir_node *a, const ir_node *b);
87 * Check, if a block strictly post dominates another block, i.e. a != b.
89 * @param a The potential post dominator block.
90 * @param b The potentially post dominated block.
92 * @return 1, if @p a strictly post dominates @p b, else 0.
94 FIRM_API int block_strictly_postdominates(const ir_node *a, const ir_node *b);
97 * Returns the first node in the list of nodes dominated by a given block.
99 * Each node keeps a list of nodes which it immediately dominates. The
100 * nodes are queued using the @c next pointer in the @c dom_info struct.
101 * Each node keeps a head of this list using the pointer @c first in the
104 * @param block The block for which to get the first node dominated by @c bl.
105 * @return The first node dominated by @p bl.
107 FIRM_API ir_node *get_Block_dominated_first(const ir_node *block);
109 * Returns the first node in the list of nodes postdominated by a given blcok.
111 FIRM_API ir_node *get_Block_postdominated_first(const ir_node *bl);
114 * Returns the next node in a list of nodes which are dominated by some
116 * @see get_Block_dominated_first().
117 * @param node The previous node.
118 * @return The next node in this list or NULL if it was the last.
120 FIRM_API ir_node *get_Block_dominated_next(const ir_node *node);
122 * Returns the next node in a list of nodes which are postdominated by another node
124 FIRM_API ir_node *get_Block_postdominated_next(const ir_node *node);
127 * Iterate over all nodes which are immediately dominated by a given
129 * @param bl The block whose dominated blocks shall be iterated on.
130 * @param curr An iterator variable of type ir_node*
132 #define dominates_for_each(bl,curr) \
133 for(curr = get_Block_dominated_first(bl); curr; \
134 curr = get_Block_dominated_next(curr))
137 * Iterate over all nodes which are immediately post dominated by a given
139 * @param bl The block whose post dominated blocks shall be iterated on.
140 * @param curr An iterator variable of type ir_node*
142 #define postdominates_for_each(bl,curr) \
143 for(curr = get_Block_postdominated_first(bl); curr; \
144 curr = get_Block_postdominated_next(curr))
147 * Returns the smallest common dominator block of two nodes.
149 * @param b Another node.
150 * @return The first block dominating @p a and @p b
152 FIRM_API ir_node *node_smallest_common_dominator(ir_node *a, ir_node *b);
155 * Visit all nodes in the dominator subtree of a given node.
156 * Call a pre-visitor before descending to the children and call a
157 * post-visitor after returning from them.
158 * @param n The node to start walking from.
159 * @param pre The pre-visitor callback.
160 * @param post The post-visitor callback.
161 * @param env Some custom data passed to the visitors.
163 FIRM_API void dom_tree_walk(ir_node *n, irg_walk_func *pre,
164 irg_walk_func *post, void *env);
167 * Visit all nodes in the post dominator subtree of a given node.
168 * Call a pre-visitor before descending to the children and call a
169 * post-visitor after returning from them.
170 * @param n The node to start walking from.
171 * @param pre The pre-visitor callback.
172 * @param post The post-visitor callback.
173 * @param env Some custom data passed to the visitors.
175 FIRM_API void postdom_tree_walk(ir_node *n, irg_walk_func *pre,
176 irg_walk_func *post, void *env);
179 * Walk over the dominator tree of an irg starting at the root.
180 * @param irg The graph.
181 * @param pre A pre-visitor to call.
182 * @param post A post-visitor to call.
183 * @param env Some private data to give to the visitors.
185 FIRM_API void dom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
186 irg_walk_func *post, void *env);
189 * Walk over the post dominator tree of an irg starting at the root.
190 * @param irg The graph.
191 * @param pre A pre-visitor to call.
192 * @param post A post-visitor to call.
193 * @param env Some private data to give to the visitors.
195 FIRM_API void postdom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
196 irg_walk_func *post, void *env);
198 /** Computes the dominance relation for all basic blocks of a given graph.
200 * Sets a flag in irg to "dom_consistent".
201 * If the control flow of the graph is changed this flag must be set to
202 * "dom_inconsistent".
203 * Does not compute dominator information for control dead code. Blocks
204 * not reachable from Start contain the following information:
210 * Also constructs outs information. As this information is correct after
211 * the run does not free the outs information.
213 FIRM_API void compute_doms(ir_graph *irg);
215 /** Recomputes dominator relation of a graph if necessary */
216 FIRM_API void assure_doms(ir_graph *irg);
218 /** Computes the post dominance relation for all basic blocks of a given graph.
220 * Sets a flag in irg to "dom_consistent".
221 * If the control flow of the graph is changed this flag must be set to
222 * "dom_inconsistent".
223 * Does not compute post dominator information for endless lops. Blocks
224 * not reachable from End contain the following information:
230 * Also constructs outs information. As this information is correct after
231 * the run does not free the outs information.
233 FIRM_API void compute_postdoms(ir_graph *irg);
235 /** Recompute postdominance relation if necessary */
236 FIRM_API void assure_postdoms(ir_graph *irg);
238 /** Frees the dominance data structures. Sets the flag in irg to "dom_none". */
239 FIRM_API void free_dom(ir_graph *irg);
242 * Frees the postdominance data structures. Sets the flag in irg to "dom_none".
244 FIRM_API void free_postdom(ir_graph *irg);