2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Functions for traversing ir graphs
9 * @author Boris Boesler, Goetz Lindenmaier, Michael Beck
11 * traverse an ir graph
12 * - execute the pre function before recursion
13 * - execute the post function after recursion
20 #include "irgraph_t.h"
32 * specialized version of irg_walk_2, called if only pre callback exists
34 static void irg_walk_2_pre(ir_node *node, irg_walk_func *pre, void *env)
37 ir_graph *irg = get_irn_irg(node);
39 set_irn_visited(node, irg->visited);
43 if (!is_Block(node)) {
44 ir_node *pred = get_nodes_block(node);
45 if (pred->visited < irg->visited)
46 irg_walk_2_pre(pred, pre, env);
48 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
49 ir_node *pred = get_irn_n(node, i);
50 if (pred->visited < irg->visited)
51 irg_walk_2_pre(pred, pre, env);
56 * specialized version of irg_walk_2, called if only post callback exists
58 static void irg_walk_2_post(ir_node *node, irg_walk_func *post, void *env)
61 ir_graph *irg = get_irn_irg(node);
63 set_irn_visited(node, irg->visited);
65 if (!is_Block(node)) {
66 ir_node *pred = get_nodes_block(node);
67 if (pred->visited < irg->visited)
68 irg_walk_2_post(pred, post, env);
70 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
71 ir_node *pred = get_irn_n(node, i);
72 if (pred->visited < irg->visited)
73 irg_walk_2_post(pred, post, env);
80 * specialized version of irg_walk_2, called if pre and post callbacks exist
82 static void irg_walk_2_both(ir_node *node, irg_walk_func *pre,
83 irg_walk_func *post, void *env)
86 ir_graph *irg = get_irn_irg(node);
88 set_irn_visited(node, irg->visited);
92 if (!is_Block(node)) {
93 ir_node *pred = get_nodes_block(node);
94 if (pred->visited < irg->visited)
95 irg_walk_2_both(pred, pre, post, env);
97 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
98 ir_node *pred = get_irn_n(node, i);
99 if (pred->visited < irg->visited)
100 irg_walk_2_both(pred, pre, post, env);
106 void irg_walk_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
109 if (irn_visited(node))
112 if (!post) irg_walk_2_pre (node, pre, env);
113 else if (!pre) irg_walk_2_post(node, post, env);
114 else irg_walk_2_both(node, pre, post, env);
117 void irg_walk_core(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
120 assert(is_ir_node(node));
121 irg_walk_2(node, pre, post, env);
124 void irg_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
127 ir_graph *irg = get_irn_irg(node);
128 ir_graph *rem = current_ir_graph;
130 current_ir_graph = irg;
131 ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
132 inc_irg_visited(irg);
133 irg_walk_core(node, pre, post, env);
134 ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
135 current_ir_graph = rem;
138 void irg_walk_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
140 ir_graph * rem = current_ir_graph;
142 hook_irg_walk(irg, (generic_func *)pre, (generic_func *)post);
143 current_ir_graph = irg;
144 irg_walk(get_irg_end(irg), pre, post, env);
145 current_ir_graph = rem;
148 void all_irg_walk(irg_walk_func *pre, irg_walk_func *post, void *env)
153 for (i = 0, n = get_irp_n_irgs(); i < n; i++) {
154 irg = get_irp_irg(i);
155 irg_walk_graph(irg, pre, post, env);
160 * specialized version of irg_walk_in_or_dep_2, called if only pre callback exists
162 static void irg_walk_in_or_dep_2_pre(ir_node *node, irg_walk_func *pre, void *env)
165 ir_graph *irg = get_irn_irg(node);
167 set_irn_visited(node, irg->visited);
171 if (!is_Block(node)) {
172 ir_node *pred = get_nodes_block(node);
173 if (pred->visited < irg->visited)
174 irg_walk_in_or_dep_2_pre(pred, pre, env);
176 for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
177 ir_node *pred = get_irn_in_or_dep(node, i);
178 if (pred->visited < irg->visited)
179 irg_walk_in_or_dep_2_pre(pred, pre, env);
184 * specialized version of irg_walk_in_or_dep_2, called if only post callback exists
186 static void irg_walk_in_or_dep_2_post(ir_node *node, irg_walk_func *post, void *env)
189 ir_graph *irg = get_irn_irg(node);
191 set_irn_visited(node, irg->visited);
193 if (!is_Block(node)) {
194 ir_node *pred = get_nodes_block(node);
195 if (pred->visited < irg->visited)
196 irg_walk_in_or_dep_2_post(pred, post, env);
198 for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
199 ir_node *pred = get_irn_in_or_dep(node, i);
200 if (pred->visited < irg->visited)
201 irg_walk_in_or_dep_2_post(pred, post, env);
208 * specialized version of irg_walk_in_or_dep_2, called if pre and post callbacks exist
210 static void irg_walk_in_or_dep_2_both(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
213 ir_graph *irg = get_irn_irg(node);
215 set_irn_visited(node, irg->visited);
219 if (!is_Block(node)) {
220 ir_node *pred = get_nodes_block(node);
221 if (pred->visited < irg->visited)
222 irg_walk_in_or_dep_2_both(pred, pre, post, env);
224 for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
225 ir_node *pred = get_irn_in_or_dep(node, i);
226 if (pred->visited < irg->visited)
227 irg_walk_in_or_dep_2_both(pred, pre, post, env);
234 * Intraprozedural graph walker. Follows dependency edges as well.
236 static void irg_walk_in_or_dep_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
238 if (irn_visited(node))
241 if (! post) irg_walk_in_or_dep_2_pre (node, pre, env);
242 else if (! pre) irg_walk_in_or_dep_2_post(node, post, env);
243 else irg_walk_in_or_dep_2_both(node, pre, post, env);
246 void irg_walk_in_or_dep(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
248 assert(is_ir_node(node));
250 ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
251 inc_irg_visited(current_ir_graph);
252 irg_walk_in_or_dep_2(node, pre, post, env);
253 ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
256 void irg_walk_in_or_dep_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
258 ir_graph * rem = current_ir_graph;
260 hook_irg_walk(irg, (generic_func *)pre, (generic_func *)post);
261 current_ir_graph = irg;
262 irg_walk_in_or_dep(get_irg_end(irg), pre, post, env);
263 current_ir_graph = rem;
266 /* Walks back from n until it finds a real cf op. */
267 static ir_node *get_cf_op(ir_node *n)
269 while (!is_cfop(n) && !is_fragile_op(n) && !is_Bad(n)) {
276 static void irg_block_walk_2(ir_node *node, irg_walk_func *pre,
277 irg_walk_func *post, void *env)
281 if (Block_block_visited(node))
283 mark_Block_block_visited(node);
288 for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
289 /* find the corresponding predecessor block. */
290 ir_node *pred = get_cf_op(get_Block_cfgpred(node, i));
291 pred = get_nodes_block(pred);
292 if (get_irn_opcode(pred) == iro_Block) {
294 irg_block_walk_2(pred, pre, post, env);
296 assert(get_irn_opcode(pred) == iro_Bad);
304 void irg_block_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
307 ir_graph *irg = get_irn_irg(node);
308 ir_node *block = is_Block(node) ? node : get_nodes_block(node);
310 hook_irg_block_walk(irg, node, (generic_func *)pre, (generic_func *)post);
312 ir_reserve_resources(irg, IR_RESOURCE_BLOCK_VISITED);
313 inc_irg_block_visited(irg);
314 irg_block_walk_2(block, pre, post, env);
316 /* Some blocks might be only reachable through keep-alive edges */
318 int arity = get_irn_arity(node);
320 for (i = 0; i < arity; i++) {
321 ir_node *pred = get_irn_n(node, i);
324 irg_block_walk_2(pred, pre, post, env);
328 ir_free_resources(irg, IR_RESOURCE_BLOCK_VISITED);
331 void irg_block_walk_graph(ir_graph *irg, irg_walk_func *pre,
332 irg_walk_func *post, void *env)
334 ir_graph * rem = current_ir_graph;
335 current_ir_graph = irg;
336 irg_block_walk(get_irg_end(irg), pre, post, env);
337 current_ir_graph = rem;
340 void irg_walk_anchors(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
342 ir_graph * rem = current_ir_graph;
343 current_ir_graph = irg;
345 ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
346 inc_irg_visited(irg);
347 irg_walk_2(irg->anchor, pre, post, env);
348 ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
350 current_ir_graph = rem;
353 typedef struct walk_env {
359 static void walk_initializer(ir_initializer_t *initializer, walk_env *env)
361 switch (initializer->kind) {
362 case IR_INITIALIZER_CONST:
363 irg_walk(initializer->consti.value, env->pre, env->post, env->env);
365 case IR_INITIALIZER_TARVAL:
366 case IR_INITIALIZER_NULL:
369 case IR_INITIALIZER_COMPOUND: {
371 for (i = 0; i < initializer->compound.n_initializers; ++i) {
372 ir_initializer_t *subinitializer
373 = initializer->compound.initializers[i];
374 walk_initializer(subinitializer, env);
379 panic("invalid initializer found");
383 * Walk to all constant expressions in this entity.
385 static void walk_entity(ir_entity *ent, void *env)
387 walk_env *my_env = (walk_env *)env;
389 if (ent->initializer != NULL) {
390 walk_initializer(ent->initializer, my_env);
394 void walk_const_code(irg_walk_func *pre, irg_walk_func *post, void *env)
401 ir_graph *rem = current_ir_graph;
402 current_ir_graph = get_const_code_irg();
403 inc_irg_visited(current_ir_graph);
409 /* Walk all types that can contain constant entities. */
410 for (s = IR_SEGMENT_FIRST; s <= IR_SEGMENT_LAST; ++s)
411 walk_types_entities(get_segment_type(s), &walk_entity, &my_env);
412 n_types = get_irp_n_types();
413 for (i = 0; i < n_types; i++)
414 walk_types_entities(get_irp_type(i), &walk_entity, &my_env);
415 for (i = 0; i < get_irp_n_irgs(); i++)
416 walk_types_entities(get_irg_frame_type(get_irp_irg(i)), &walk_entity, &my_env);
418 /* Walk constant array bounds. */
419 for (i = 0; i < n_types; i++) {
420 ir_type *tp = get_irp_type(i);
421 if (is_Array_type(tp)) {
422 size_t j, n_dim = get_array_n_dimensions(tp);
423 for (j = 0; j < n_dim; j++) {
424 ir_node *n = get_array_lower_bound(tp, j);
425 if (n) irg_walk(n, pre, post, env);
426 n = get_array_upper_bound(tp, j);
427 if (n) irg_walk(n, pre, post, env);
432 current_ir_graph = rem;