2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Construct and access dominator tree.
9 * @author Goetz Lindenmaier
11 * @brief This file contains routines to construct and access dominator information.
13 #ifndef FIRM_ANA_IRDOM_H
14 #define FIRM_ANA_IRDOM_H
16 #include "firm_types.h"
21 * @defgroup irdom Dominance Information
23 * The dominator information is stored in three fields of block nodes:
24 * - idom: a reference to the block that is the immediate dominator of
26 * - dom_depth: a number giving the depth of the block in the dominator
28 * - pre_num: Number in preorder traversal.
30 * We generally presume (like Tarjan) that endless loops do not exist. The
31 * implementation assumes a control dependency from End to loop header.
36 /** return immediate dominator of block */
37 FIRM_API ir_node *get_Block_idom(const ir_node *block);
39 /** return immediate postdominator of a block */
40 FIRM_API ir_node *get_Block_ipostdom(const ir_node *block);
43 * Check, if a block dominates another block.
45 * @param a The potential dominator block.
46 * @param b The potentially dominated block.
48 * @return 1, if @p a dominates @p b, else 0.
50 FIRM_API int block_dominates(const ir_node *a, const ir_node *b);
53 * Check, if a block strictly dominates another block, i.e. a != b.
55 * @param a The potential dominator block.
56 * @param b The potentially dominated block.
58 * @return 1, if @p a strictly dominates @p b, else 0.
60 FIRM_API int block_strictly_dominates(const ir_node *a, const ir_node *b);
63 * Check, if a block post dominates another block.
65 * @param a The potential post dominator block.
66 * @param b The potentially post dominated block.
68 * @return 1, if @p a post dominates @p b, else 0.
70 FIRM_API int block_postdominates(const ir_node *a, const ir_node *b);
73 * Check, if a block strictly post dominates another block, i.e. a != b.
75 * @param a The potential post dominator block.
76 * @param b The potentially post dominated block.
78 * @return 1, if @p a strictly post dominates @p b, else 0.
80 FIRM_API int block_strictly_postdominates(const ir_node *a, const ir_node *b);
83 * Returns 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 block The block for which to get the first node dominated by @c bl.
91 * @return The first node dominated by @p bl.
93 FIRM_API ir_node *get_Block_dominated_first(const ir_node *block);
95 * Returns the first node in the list of nodes postdominated by a given blcok.
97 FIRM_API ir_node *get_Block_postdominated_first(const ir_node *bl);
100 * Returns the next node in a list of nodes which are dominated by some
102 * @see get_Block_dominated_first().
103 * @param node The previous node.
104 * @return The next node in this list or NULL if it was the last.
106 FIRM_API ir_node *get_Block_dominated_next(const ir_node *node);
108 * Returns the next node in a list of nodes which are postdominated by another node
110 FIRM_API ir_node *get_Block_postdominated_next(const ir_node *node);
113 * Iterate over all nodes which are immediately dominated by a given
115 * @param bl The block whose dominated blocks shall be iterated on.
116 * @param curr An iterator variable of type ir_node*
118 #define dominates_for_each(bl,curr) \
119 for(curr = get_Block_dominated_first(bl); curr; \
120 curr = get_Block_dominated_next(curr))
123 * Iterate over all nodes which are immediately post dominated by a given
125 * @param bl The block whose post dominated blocks shall be iterated on.
126 * @param curr An iterator variable of type ir_node*
128 #define postdominates_for_each(bl,curr) \
129 for(curr = get_Block_postdominated_first(bl); curr; \
130 curr = get_Block_postdominated_next(curr))
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 FIRM_API ir_node *node_smallest_common_dominator(ir_node *a, ir_node *b);
141 * Visit all nodes in the dominator subtree of a given node.
142 * Call a pre-visitor before descending to the children and call a
143 * post-visitor after returning from them.
144 * @param n The node to start walking from.
145 * @param pre The pre-visitor callback.
146 * @param post The post-visitor callback.
147 * @param env Some custom data passed to the visitors.
149 FIRM_API void dom_tree_walk(ir_node *n, irg_walk_func *pre,
150 irg_walk_func *post, void *env);
153 * Visit all nodes in the post dominator subtree of a given node.
154 * Call a pre-visitor before descending to the children and call a
155 * post-visitor after returning from them.
156 * @param n The node to start walking from.
157 * @param pre The pre-visitor callback.
158 * @param post The post-visitor callback.
159 * @param env Some custom data passed to the visitors.
161 FIRM_API void postdom_tree_walk(ir_node *n, irg_walk_func *pre,
162 irg_walk_func *post, void *env);
165 * Walk over the dominator tree of an irg starting at the root.
166 * @param irg The graph.
167 * @param pre A pre-visitor to call.
168 * @param post A post-visitor to call.
169 * @param env Some private data to give to the visitors.
171 FIRM_API void dom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
172 irg_walk_func *post, void *env);
175 * Walk over the post dominator tree of an irg starting at the root.
176 * @param irg The graph.
177 * @param pre A pre-visitor to call.
178 * @param post A post-visitor to call.
179 * @param env Some private data to give to the visitors.
181 FIRM_API void postdom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
182 irg_walk_func *post, void *env);
184 /** Computes the dominance relation for all basic blocks of a given graph.
186 * Sets a flag in irg to "dom_consistent".
187 * If the control flow of the graph is changed this flag must be set to
188 * "dom_inconsistent".
189 * Does not compute dominator information for control dead code. Blocks
190 * not reachable from Start contain the following information:
196 * Also constructs outs information. As this information is correct after
197 * the run does not free the outs information.
199 FIRM_API void compute_doms(ir_graph *irg);
201 /** Recomputes dominator relation of a graph if necessary */
202 FIRM_API void assure_doms(ir_graph *irg);
204 /** Computes the post dominance relation for all basic blocks of a given graph.
206 * Sets a flag in irg to "dom_consistent".
207 * If the control flow of the graph is changed this flag must be set to
208 * "dom_inconsistent".
209 * Does not compute post dominator information for endless lops. Blocks
210 * not reachable from End contain the following information:
216 * Also constructs outs information. As this information is correct after
217 * the run does not free the outs information.
219 FIRM_API void compute_postdoms(ir_graph *irg);
221 /** Recompute postdominance relation if necessary */
222 FIRM_API void assure_postdoms(ir_graph *irg);
224 /** Frees the dominance data structures. Sets the flag in irg to "dom_none". */
225 FIRM_API void free_dom(ir_graph *irg);
228 * Frees the postdominance data structures. Sets the flag in irg to "dom_none".
230 FIRM_API void free_postdom(ir_graph *irg);
233 * Compute the dominance frontiers for a given graph.
234 * The information is freed automatically when dominance info is freed.
236 FIRM_API void ir_compute_dominance_frontiers(ir_graph *irg);
239 * Get the dominance frontier of a block.
240 * @param block The block whose dominance frontier you want.
241 * @return A list containing all blocks in the dominance frontier of
242 * @p block (as array, use ARR_LEN() to determine the size)
244 FIRM_API ir_node **ir_get_dominance_frontier(const ir_node *block);