2 * Copyright (C) 1995-2011 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 Functions for traversing ir graphs
23 * @author Boris Boesler, Goetz Lindenmaier, Michael Beck
25 * traverse an ir graph
26 * - execute the pre function before recursion
27 * - execute the post function after recursion
34 #include "irgraph_t.h"
46 * specialized version of irg_walk_2, called if only pre callback exists
48 * @return number of visited nodes
50 static unsigned irg_walk_2_pre(ir_node *node, irg_walk_func *pre, void *env)
54 ir_graph *irg = get_irn_irg(node);
56 set_irn_visited(node, irg->visited);
60 if (!is_Block(node)) {
61 ir_node *pred = get_nodes_block(node);
62 if (pred->visited < irg->visited)
63 cnt += irg_walk_2_pre(pred, pre, env);
65 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
66 ir_node *pred = get_irn_n(node, i);
67 if (pred->visited < irg->visited)
68 cnt += irg_walk_2_pre(pred, pre, env);
74 * specialized version of irg_walk_2, called if only post callback exists
76 * @return number of visited nodes
78 static unsigned irg_walk_2_post(ir_node *node, irg_walk_func *post, void *env)
82 ir_graph *irg = get_irn_irg(node);
84 set_irn_visited(node, irg->visited);
86 if (!is_Block(node)) {
87 ir_node *pred = get_nodes_block(node);
88 if (pred->visited < irg->visited)
89 cnt += irg_walk_2_post(pred, post, env);
91 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
92 ir_node *pred = get_irn_n(node, i);
93 if (pred->visited < irg->visited)
94 cnt += irg_walk_2_post(pred, post, env);
103 * specialized version of irg_walk_2, called if pre and post callbacks exist
105 * @return number of visited nodes
107 static unsigned irg_walk_2_both(ir_node *node, irg_walk_func *pre,
108 irg_walk_func *post, void *env)
112 ir_graph *irg = get_irn_irg(node);
114 set_irn_visited(node, irg->visited);
118 if (!is_Block(node)) {
119 ir_node *pred = get_nodes_block(node);
120 if (pred->visited < irg->visited)
121 cnt += irg_walk_2_both(pred, pre, post, env);
123 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
124 ir_node *pred = get_irn_n(node, i);
125 if (pred->visited < irg->visited)
126 cnt += irg_walk_2_both(pred, pre, post, env);
134 unsigned irg_walk_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
137 if (irn_visited(node))
140 if (!post) return irg_walk_2_pre (node, pre, env);
141 else if (!pre) return irg_walk_2_post(node, post, env);
142 else return irg_walk_2_both(node, pre, post, env);
146 static unsigned nodes_touched = 0;
148 void irg_walk_core(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
151 assert(is_ir_node(node));
152 nodes_touched = irg_walk_2(node, pre, post, env);
155 void irg_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
158 ir_graph *irg = get_irn_irg(node);
159 ir_graph *rem = current_ir_graph;
161 current_ir_graph = irg;
162 ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
163 inc_irg_visited(irg);
164 irg_walk_core(node, pre, post, env);
165 ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
166 current_ir_graph = rem;
169 void irg_walk_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
171 ir_graph * rem = current_ir_graph;
173 hook_irg_walk(irg, (generic_func *)pre, (generic_func *)post);
174 current_ir_graph = irg;
175 irg_walk(get_irg_end(irg), pre, post, env);
176 irg->estimated_node_count = nodes_touched;
177 current_ir_graph = rem;
180 void all_irg_walk(irg_walk_func *pre, irg_walk_func *post, void *env)
185 for (i = 0, n = get_irp_n_irgs(); i < n; i++) {
186 irg = get_irp_irg(i);
187 irg_walk_graph(irg, pre, post, env);
192 * specialized version of irg_walk_in_or_dep_2, called if only pre callback exists
194 * @return number of visited nodes
196 static unsigned irg_walk_in_or_dep_2_pre(ir_node *node, irg_walk_func *pre, void *env)
200 ir_graph *irg = get_irn_irg(node);
202 set_irn_visited(node, irg->visited);
206 if (!is_Block(node)) {
207 ir_node *pred = get_nodes_block(node);
208 if (pred->visited < irg->visited)
209 cnt += irg_walk_in_or_dep_2_pre(pred, pre, env);
211 for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
212 ir_node *pred = get_irn_in_or_dep(node, i);
213 if (pred->visited < irg->visited)
214 cnt += irg_walk_in_or_dep_2_pre(pred, pre, env);
220 * specialized version of irg_walk_in_or_dep_2, called if only post callback exists
222 * @return number of visited nodes
224 static unsigned irg_walk_in_or_dep_2_post(ir_node *node, irg_walk_func *post, void *env)
228 ir_graph *irg = get_irn_irg(node);
230 set_irn_visited(node, irg->visited);
232 if (!is_Block(node)) {
233 ir_node *pred = get_nodes_block(node);
234 if (pred->visited < irg->visited)
235 cnt += irg_walk_in_or_dep_2_post(pred, post, env);
237 for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
238 ir_node *pred = get_irn_in_or_dep(node, i);
239 if (pred->visited < irg->visited)
240 cnt += irg_walk_in_or_dep_2_post(pred, post, env);
249 * specialized version of irg_walk_in_or_dep_2, called if pre and post callbacks exist
251 * @return number of visited nodes
253 static unsigned irg_walk_in_or_dep_2_both(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
257 ir_graph *irg = get_irn_irg(node);
259 set_irn_visited(node, irg->visited);
263 if (!is_Block(node)) {
264 ir_node *pred = get_nodes_block(node);
265 if (pred->visited < irg->visited)
266 cnt += irg_walk_in_or_dep_2_both(pred, pre, post, env);
268 for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
269 ir_node *pred = get_irn_in_or_dep(node, i);
270 if (pred->visited < irg->visited)
271 cnt += irg_walk_in_or_dep_2_both(pred, pre, post, env);
280 * Intraprozedural graph walker. Follows dependency edges as well.
282 * @return number of visited nodes
284 static unsigned irg_walk_in_or_dep_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
286 if (irn_visited(node))
289 if (! post) return irg_walk_in_or_dep_2_pre (node, pre, env);
290 else if (! pre) return irg_walk_in_or_dep_2_post(node, post, env);
291 else return irg_walk_in_or_dep_2_both(node, pre, post, env);
294 void irg_walk_in_or_dep(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
296 assert(is_ir_node(node));
298 ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
299 inc_irg_visited(current_ir_graph);
300 nodes_touched = irg_walk_in_or_dep_2(node, pre, post, env);
301 ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
304 void irg_walk_in_or_dep_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
306 ir_graph * rem = current_ir_graph;
308 hook_irg_walk(irg, (generic_func *)pre, (generic_func *)post);
309 current_ir_graph = irg;
310 irg_walk_in_or_dep(get_irg_end(irg), pre, post, env);
311 irg->estimated_node_count = nodes_touched;
312 current_ir_graph = rem;
315 /* Walks back from n until it finds a real cf op. */
316 static ir_node *get_cf_op(ir_node *n)
318 while (!is_cfop(n) && !is_fragile_op(n) && !is_Bad(n)) {
326 static void irg_block_walk_2(ir_node *node, irg_walk_func *pre,
327 irg_walk_func *post, void *env)
331 if (Block_block_visited(node))
333 mark_Block_block_visited(node);
338 for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
339 /* find the corresponding predecessor block. */
340 ir_node *pred = get_cf_op(get_Block_cfgpred(node, i));
341 pred = get_nodes_block(pred);
342 if (get_irn_opcode(pred) == iro_Block) {
344 irg_block_walk_2(pred, pre, post, env);
346 assert(get_irn_opcode(pred) == iro_Bad);
354 void irg_block_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
357 ir_graph *irg = get_irn_irg(node);
358 ir_node *block = is_Block(node) ? node : get_nodes_block(node);
360 hook_irg_block_walk(irg, node, (generic_func *)pre, (generic_func *)post);
362 ir_reserve_resources(irg, IR_RESOURCE_BLOCK_VISITED);
363 inc_irg_block_visited(irg);
364 irg_block_walk_2(block, pre, post, env);
366 /* Some blocks might be only reachable through keep-alive edges */
368 int arity = get_irn_arity(node);
370 for (i = 0; i < arity; i++) {
371 ir_node *pred = get_irn_n(node, i);
374 irg_block_walk_2(pred, pre, post, env);
378 ir_free_resources(irg, IR_RESOURCE_BLOCK_VISITED);
381 void irg_block_walk_graph(ir_graph *irg, irg_walk_func *pre,
382 irg_walk_func *post, void *env)
384 ir_graph * rem = current_ir_graph;
385 current_ir_graph = irg;
386 irg_block_walk(get_irg_end(irg), pre, post, env);
387 current_ir_graph = rem;
390 void irg_walk_anchors(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
392 ir_graph * rem = current_ir_graph;
393 current_ir_graph = irg;
395 ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
396 inc_irg_visited(irg);
397 irg_walk_2(irg->anchor, pre, post, env);
398 ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
400 current_ir_graph = rem;
403 typedef struct walk_env {
409 static void walk_initializer(ir_initializer_t *initializer, walk_env *env)
411 switch (initializer->kind) {
412 case IR_INITIALIZER_CONST:
413 irg_walk(initializer->consti.value, env->pre, env->post, env->env);
415 case IR_INITIALIZER_TARVAL:
416 case IR_INITIALIZER_NULL:
419 case IR_INITIALIZER_COMPOUND: {
421 for (i = 0; i < initializer->compound.n_initializers; ++i) {
422 ir_initializer_t *subinitializer
423 = initializer->compound.initializers[i];
424 walk_initializer(subinitializer, env);
429 panic("invalid initializer found");
433 * Walk to all constant expressions in this entity.
435 static void walk_entity(ir_entity *ent, void *env)
437 walk_env *my_env = (walk_env *)env;
439 if (ent->initializer != NULL) {
440 walk_initializer(ent->initializer, my_env);
444 void walk_const_code(irg_walk_func *pre, irg_walk_func *post, void *env)
451 ir_graph *rem = current_ir_graph;
452 current_ir_graph = get_const_code_irg();
453 inc_irg_visited(current_ir_graph);
459 /* Walk all types that can contain constant entities. */
460 for (s = IR_SEGMENT_FIRST; s <= IR_SEGMENT_LAST; ++s)
461 walk_types_entities(get_segment_type(s), &walk_entity, &my_env);
462 n_types = get_irp_n_types();
463 for (i = 0; i < n_types; i++)
464 walk_types_entities(get_irp_type(i), &walk_entity, &my_env);
465 for (i = 0; i < get_irp_n_irgs(); i++)
466 walk_types_entities(get_irg_frame_type(get_irp_irg(i)), &walk_entity, &my_env);
468 /* Walk constant array bounds. */
469 for (i = 0; i < n_types; i++) {
470 ir_type *tp = get_irp_type(i);
471 if (is_Array_type(tp)) {
472 size_t j, n_dim = get_array_n_dimensions(tp);
473 for (j = 0; j < n_dim; j++) {
474 ir_node *n = get_array_lower_bound(tp, j);
475 if (n) irg_walk(n, pre, post, env);
476 n = get_array_upper_bound(tp, j);
477 if (n) irg_walk(n, pre, post, env);
482 current_ir_graph = rem;