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 /** return immediate dominator of block */
53 FIRM_API ir_node *get_Block_idom(const ir_node *block);
55 /** return immediate postdominator of a block */
56 FIRM_API ir_node *get_Block_ipostdom(const ir_node *block);
59 * Check, if a block dominates another block.
61 * @param a The potential dominator block.
62 * @param b The potentially dominated block.
64 * @return 1, if @p a dominates @p b, else 0.
66 FIRM_API int block_dominates(const ir_node *a, const ir_node *b);
69 * Check, if a block strictly dominates another block, i.e. a != b.
71 * @param a The potential dominator block.
72 * @param b The potentially dominated block.
74 * @return 1, if @p a strictly dominates @p b, else 0.
76 FIRM_API int block_strictly_dominates(const ir_node *a, const ir_node *b);
79 * Check, if a block post dominates another block.
81 * @param a The potential post dominator block.
82 * @param b The potentially post dominated block.
84 * @return 1, if @p a post dominates @p b, else 0.
86 FIRM_API int block_postdominates(const ir_node *a, const ir_node *b);
89 * Check, if a block strictly post dominates another block, i.e. a != b.
91 * @param a The potential post dominator block.
92 * @param b The potentially post dominated block.
94 * @return 1, if @p a strictly post dominates @p b, else 0.
96 FIRM_API int block_strictly_postdominates(const ir_node *a, const ir_node *b);
99 * Get the first node in the list of nodes dominated by a given block.
101 * Each node keeps a list of nodes which it immediately dominates. The
102 * nodes are queued using the @c next pointer in the @c dom_info struct.
103 * Each node keeps a head of this list using the pointer @c first in the
106 * @param bl The block for which to get the first node dominated by @c bl.
107 * @return The first node dominated by @p bl.
109 FIRM_API ir_node *get_Block_dominated_first(const ir_node *block);
111 * Get the first node in the list of nodes postdominated by a given blcok.
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 *node);
124 * Get the next node in a list of nodes which are postdominated by another node
126 FIRM_API ir_node *get_Block_postdominated_next(const ir_node *node);
129 * Iterate over all nodes which are immediately dominated by a given
131 * @param bl The block whose dominated blocks shall be iterated on.
132 * @param curr An iterator variable of type ir_node*
134 #define dominates_for_each(bl,curr) \
135 for(curr = get_Block_dominated_first(bl); curr; \
136 curr = get_Block_dominated_next(curr))
139 * Iterate over all nodes which are immediately post dominated by a given
141 * @param bl The block whose post dominated blocks shall be iterated on.
142 * @param curr An iterator variable of type ir_node*
144 #define postdominates_for_each(bl,curr) \
145 for(curr = get_Block_postdominated_first(bl); curr; \
146 curr = get_Block_postdominated_next(curr))
149 * Returns the smallest common dominator block of two nodes.
151 * @param b Another node.
152 * @return The first block dominating @p a and @p b
154 FIRM_API ir_node *node_smallest_common_dominator(ir_node *a, ir_node *b);
157 * Visit all nodes in the dominator subtree of a given node.
158 * Call a pre-visitor before descending to the children and call a
159 * post-visitor after returning from them.
160 * @param n The node to start walking from.
161 * @param pre The pre-visitor callback.
162 * @param post The post-visitor callback.
163 * @param env Some custom data passed to the visitors.
165 FIRM_API void dom_tree_walk(ir_node *n, irg_walk_func *pre,
166 irg_walk_func *post, void *env);
169 * Visit all nodes in the post dominator subtree of a given node.
170 * Call a pre-visitor before descending to the children and call a
171 * post-visitor after returning from them.
172 * @param n The node to start walking from.
173 * @param pre The pre-visitor callback.
174 * @param post The post-visitor callback.
175 * @param env Some custom data passed to the visitors.
177 FIRM_API void postdom_tree_walk(ir_node *n, irg_walk_func *pre,
178 irg_walk_func *post, void *env);
181 * Walk over the dominator tree of an irg starting at the root.
182 * @param irg The graph.
183 * @param pre A pre-visitor to call.
184 * @param post A post-visitor to call.
185 * @param env Some private data to give to the visitors.
187 FIRM_API void dom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
188 irg_walk_func *post, void *env);
191 * Walk over the post dominator tree of an irg starting at the root.
192 * @param irg The graph.
193 * @param pre A pre-visitor to call.
194 * @param post A post-visitor to call.
195 * @param env Some private data to give to the visitors.
197 FIRM_API void postdom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
198 irg_walk_func *post, void *env);
200 /** Computes the dominance relation for all basic blocks of a given graph.
202 * Sets a flag in irg to "dom_consistent".
203 * If the control flow of the graph is changed this flag must be set to
204 * "dom_inconsistent".
205 * Does not compute dominator information for control dead code. Blocks
206 * not reachable from Start contain the following information:
212 * Also constructs outs information. As this information is correct after
213 * the run does not free the outs information.
215 FIRM_API void compute_doms(ir_graph *irg);
217 /** Recomputes dominator relation of a graph if necessary */
218 FIRM_API void assure_doms(ir_graph *irg);
220 /** Computes the post dominance relation for all basic blocks of a given graph.
222 * Sets a flag in irg to "dom_consistent".
223 * If the control flow of the graph is changed this flag must be set to
224 * "dom_inconsistent".
225 * Does not compute post dominator information for endless lops. Blocks
226 * not reachable from End contain the following information:
232 * Also constructs outs information. As this information is correct after
233 * the run does not free the outs information.
235 FIRM_API void compute_postdoms(ir_graph *irg);
237 /** Recompute postdominance relation if necessary */
238 FIRM_API void assure_postdoms(ir_graph *irg);
240 /** Frees the dominance data structures. Sets the flag in irg to "dom_none". */
241 FIRM_API void free_dom(ir_graph *irg);
244 * Frees the postdominance data structures. Sets the flag in irg to "dom_none".
246 FIRM_API void free_postdom(ir_graph *irg);