2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Traverse an ir graph
9 * @author Boris Boesler, Goetz Lindenmaier
11 #ifndef FIRM_IR_IRGWALK_H
12 #define FIRM_IR_IRGWALK_H
14 #include "firm_types.h"
19 * @defgroup irgwalk Traversing
22 * - execute the pre function before recursion
23 * - execute the post function after recursion
28 * Walks over the ir graph.
30 * Walks over the ir graph, starting at the node given as first argument.
31 * Executes pre before visiting the predecessor of a node, post after.
32 * irg_walk uses the visited flag in irg and the nodes to determine visited
33 * nodes. It executes inc_irg_visited(current_ir_graph) to generate a new
34 * flag. Therefore current_ir_graph must be set before calling the walker.
35 * It marks the node as visited before executing pre.
36 * The void* env can be used to pass status information between the
37 * pre and post functions. Does not use the link fields.
39 * @param node the start node
40 * @param pre walker function, executed before the predecessor of a node are visited
41 * @param post walker function, executed after the predecessor of a node are visited
42 * @param env environment, passed to pre and post
45 FIRM_API void irg_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
49 * core walker function. Does NOT touch current_ir_graph and does not call
50 * inc_irg_visited before walking
52 FIRM_API void irg_walk_core(ir_node *node, irg_walk_func *pre,
53 irg_walk_func *post, void *env);
56 * Walks over all reachable nodes in the ir graph.
58 * @param irg the irg graph
59 * @param pre walker function, executed before the predecessor of a node are visited
60 * @param post walker function, executed after the predecessor of a node are visited
61 * @param env environment, passed to pre and post
63 * Like irg_walk(), but walks over all reachable nodes in the ir
64 * graph, starting at the end operation. During the walk current_ir_graph
65 * is set to irg. Does not use the link field.
67 FIRM_API void irg_walk_graph(ir_graph *irg, irg_walk_func *pre,
68 irg_walk_func *post, void *env);
71 * Walks over the ir graph.
73 * Walks over the ir graph, starting at the node given as first argument.
74 * Executes pre before visiting the predecessor of a node, post after.
75 * irg_walk uses the visited flag in irg and the nodes to determine visited
76 * nodes. It executes inc_irg_visited(current_ir_graph) to generate a new
77 * flag. Therefore current_ir_graph must be set before calling the walker.
78 * It marks the node as visited before executing pre.
79 * The void* env can be used to pass status information between the
80 * pre and post functions. Does not use the link fields.
81 * This walker also follows additional dependency egdes.
83 * @param node the start node
84 * @param pre walker function, executed before the predecessor of a node are visited
85 * @param post walker function, executed after the predecessor of a node are visited
86 * @param env environment, passed to pre and post
89 FIRM_API void irg_walk_in_or_dep(ir_node *node, irg_walk_func *pre,
90 irg_walk_func *post, void *env);
93 * Walks over all reachable nodes in the ir graph.
95 * @param irg the irg graph
96 * @param pre walker function, executed before the predecessor of a node are visited
97 * @param post walker function, executed after the predecessor of a node are visited
98 * @param env environment, passed to pre and post
100 * Like irg_walk(), but walks over all reachable nodes in the ir
101 * graph, starting at the end operation. During the walk current_ir_graph
102 * is set to irg. Does not use the link field.
103 * This walker also follows additional dependency egdes.
105 FIRM_API void irg_walk_in_or_dep_graph(ir_graph *irg, irg_walk_func *pre,
106 irg_walk_func *post, void *env);
109 * Executes irg_walk(end, pre, post, env) for all irgraphs in irprog.
111 * @param pre walker function, executed before the predecessor of a node are visited
112 * @param post walker function, executed after the predecessor of a node are visited
113 * @param env environment, passed to pre and post
115 * This function executes irg_walk(end, pre, post, env) for all irgraphs in irprog.
116 * Sets current_ir_graph properly for each walk. Conserves current
117 * current_ir_graph. Does not use the link field.
119 FIRM_API void all_irg_walk(irg_walk_func *pre, irg_walk_func *post, void *env);
121 /** Walks only over Block nodes in the graph.
123 * @param node the start node
124 * @param pre walker function, executed before the predecessor of a node are visited
125 * @param post walker function, executed after the predecessor of a node are visited
126 * @param env environment, passed to pre and post
128 * This function Walks only over Block nodes in the graph. Has its own visited
129 * flag, so that it can be interleaved with the other walker.
130 * If a non-block is passed, starts at the block this node belongs to.
131 * If end is passed also visits kept alive blocks. Does not use the link field.
133 FIRM_API void irg_block_walk(ir_node *node, irg_walk_func *pre,
134 irg_walk_func *post, void *env);
137 * Walks only over reachable Block nodes in the graph.
139 * @param irg the irg graph
140 * @param pre walker function, executed before the predecessor of a node are visited
141 * @param post walker function, executed after the predecessor of a node are visited
142 * @param env environment, passed to pre and post
144 * Like irg_block_walk(), but walks over all reachable blocks in the
145 * ir graph, starting at the end block. Does not use the link field.
147 FIRM_API void irg_block_walk_graph(ir_graph *irg, irg_walk_func *pre,
148 irg_walk_func *post, void *env);
151 * Walks over all code in const_code_irg.
153 * @param pre walker function, executed before the predecessor of a node are visited
154 * @param post walker function, executed after the predecessor of a node are visited
155 * @param env environment, passed to pre and post
157 * This function walks over all code in const_code_irg.
158 * Uses visited flag in const_code_irg. Does not use the link field.
160 FIRM_API void walk_const_code(irg_walk_func *pre, irg_walk_func *post,
164 * Walks over reachable nodes in block-wise topological order, i.e. visit
165 * all nodes in a block before going to another block, starting at the end operation.
166 * Executes pre before visiting the predecessor of a node, post after.
167 * irg_walk_blkwise_graph() uses the visited flag in irg and the nodes to
168 * determine visited nodes.
169 * It executes inc_irg_visited(current_ir_graph) to generate a new
170 * flag. It marks the node as visited before executing pre.
171 * The void *env can be used to pass status information between the
172 * pre and post functions. Does not use the link fields.
174 * @param irg the irg graph
175 * @param pre walker function, executed before the predecessor of a node are visited
176 * @param post walker function, executed after the predecessor of a node are visited
177 * @param env environment, passed to pre and post
179 FIRM_API void irg_walk_blkwise_graph(ir_graph *irg, irg_walk_func *pre,
180 irg_walk_func *post, void *env);
183 * Walks over reachable nodes in block-wise topological order, i.e. visit
184 * all nodes in a block before going to another block, starting at the end operation.
185 * Executes pre before visiting the predecessor of a node, post after.
186 * irg_walk_blkwise_graph() uses the visited flag in irg and the nodes to
187 * determine visited nodes.
188 * It executes inc_irg_visited(current_ir_graph) to generate a new
189 * flag. It marks the node as visited before executing pre.
190 * The void *env can be used to pass status information between the
191 * pre and post functions. Does not use the link fields.
192 * This walker also follows dependency edges.
194 * @param irg the irg graph
195 * @param pre walker function, executed before the predecessor of a node are visited
196 * @param post walker function, executed after the predecessor of a node are visited
197 * @param env environment, passed to pre and post
199 FIRM_API void irg_walk_in_or_dep_blkwise_graph(ir_graph *irg,
201 irg_walk_func *post, void *env);
204 * Walks over reachable nodes in block-wise topological order, i.e. visit
205 * all nodes in a block before going to another block, starting at the end operation.
206 * Visit the blocks in dominator tree top-down order.
207 * Executes pre before visiting the predecessor of a node, post after.
208 * irg_walk_blkwise_graph() uses the visited flag in irg and the nodes to
209 * determine visited nodes.
210 * It executes inc_irg_visited(current_ir_graph) to generate a new
211 * flag. It marks the node as visited before executing pre.
212 * The void *env can be used to pass status information between the
213 * pre and post functions. Does not use the link fields.
215 * @param irg the irg graph
216 * @param pre walker function, executed before the predecessor of a node are visited
217 * @param post walker function, executed after the predecessor of a node are visited
218 * @param env environment, passed to pre and post
220 FIRM_API void irg_walk_blkwise_dom_top_down(ir_graph *irg, irg_walk_func *pre,
221 irg_walk_func *post, void *env);
224 * Additionally walk over all anchors.
225 * This function visits all anchor nodes that otherwise might not been visited in a
226 * walk, for instance the Bad() node.
228 * @param irg the irg graph
229 * @param pre walker function, executed before the predecessor of a node are visited
230 * @param post walker function, executed after the predecessor of a node are visited
231 * @param env environment, passed to pre and post
233 FIRM_API void irg_walk_anchors(ir_graph *irg, irg_walk_func *pre,
234 irg_walk_func *post, void *env);
237 * Walker function which does not increase the visited flag before walking.
238 * Do not use this unless you know what you are doing.
240 FIRM_API void irg_walk_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post,