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 Functions for traversing ir graphs
23 * @author Boris Boesler, Goetz Lindenmaier, Michael Beck
26 * traverse an ir graph
27 * - execute the pre function before recursion
28 * - execute the post function after recursion
35 #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 (node->op != op_Block) {
61 ir_node *pred = get_irn_n(node, -1);
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 (node->op != op_Block) {
87 ir_node *pred = get_irn_n(node, -1);
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 (node->op != op_Block) {
119 ir_node *pred = get_irn_n(node, -1);
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);
135 * Intraprozedural graph walker.
137 * @return number of visited nodes
139 unsigned irg_walk_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
142 if (irn_visited(node))
145 if (!post) return irg_walk_2_pre (node, pre, env);
146 else if (!pre) return irg_walk_2_post(node, post, env);
147 else return irg_walk_2_both(node, pre, post, env);
151 static unsigned nodes_touched = 0;
153 void irg_walk_core(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
156 assert(is_ir_node(node));
157 nodes_touched = irg_walk_2(node, pre, post, env);
160 void irg_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
163 ir_graph *irg = get_irn_irg(node);
164 ir_graph *rem = current_ir_graph;
166 current_ir_graph = irg;
167 ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
168 inc_irg_visited(irg);
169 irg_walk_core(node, pre, post, env);
170 ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
171 current_ir_graph = rem;
177 void irg_walk_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
179 ir_graph * rem = current_ir_graph;
181 hook_irg_walk(irg, (generic_func *)pre, (generic_func *)post);
182 current_ir_graph = irg;
183 irg_walk(get_irg_end(irg), pre, post, env);
184 irg->estimated_node_count = nodes_touched;
185 current_ir_graph = rem;
188 /* Executes irg_walk(end, pre, post, env) for all irgraphs in irprog.
189 Sets current_ir_graph properly for each walk. Conserves current
191 void all_irg_walk(irg_walk_func *pre, irg_walk_func *post, void *env)
196 for (i = 0, n = get_irp_n_irgs(); i < n; i++) {
197 irg = get_irp_irg(i);
198 irg_walk_graph(irg, pre, post, env);
202 /***************************************************************************/
205 * specialized version of irg_walk_in_or_dep_2, called if only pre callback exists
207 * @return number of visited nodes
209 static unsigned irg_walk_in_or_dep_2_pre(ir_node *node, irg_walk_func *pre, void *env)
213 ir_graph *irg = get_irn_irg(node);
215 set_irn_visited(node, irg->visited);
219 if (node->op != op_Block) {
220 ir_node *pred = get_irn_n(node, -1);
221 if (pred->visited < irg->visited)
222 cnt += irg_walk_in_or_dep_2_pre(pred, pre, 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 cnt += irg_walk_in_or_dep_2_pre(pred, pre, env);
233 * specialized version of irg_walk_in_or_dep_2, called if only post callback exists
235 * @return number of visited nodes
237 static unsigned irg_walk_in_or_dep_2_post(ir_node *node, irg_walk_func *post, void *env)
241 ir_graph *irg = get_irn_irg(node);
243 set_irn_visited(node, irg->visited);
245 if (node->op != op_Block) {
246 ir_node *pred = get_irn_n(node, -1);
247 if (pred->visited < irg->visited)
248 cnt += irg_walk_in_or_dep_2_post(pred, post, env);
250 for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
251 ir_node *pred = get_irn_in_or_dep(node, i);
252 if (pred->visited < irg->visited)
253 cnt += irg_walk_in_or_dep_2_post(pred, post, env);
262 * specialized version of irg_walk_in_or_dep_2, called if pre and post callbacks exist
264 * @return number of visited nodes
266 static unsigned irg_walk_in_or_dep_2_both(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
270 ir_graph *irg = get_irn_irg(node);
272 set_irn_visited(node, irg->visited);
276 if (node->op != op_Block) {
277 ir_node *pred = get_irn_n(node, -1);
278 if (pred->visited < irg->visited)
279 cnt += irg_walk_in_or_dep_2_both(pred, pre, post, env);
281 for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
282 ir_node *pred = get_irn_in_or_dep(node, i);
283 if (pred->visited < irg->visited)
284 cnt += irg_walk_in_or_dep_2_both(pred, pre, post, env);
293 * Intraprozedural graph walker. Follows dependency edges as well.
295 * @return number of visited nodes
297 static unsigned irg_walk_in_or_dep_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
299 if (irn_visited(node))
302 if (! post) return irg_walk_in_or_dep_2_pre (node, pre, env);
303 else if (! pre) return irg_walk_in_or_dep_2_post(node, post, env);
304 else return irg_walk_in_or_dep_2_both(node, pre, post, env);
308 * Generic graph walker. Follows dependency edges as well.
310 void irg_walk_in_or_dep(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
312 assert(is_ir_node(node));
314 ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
315 inc_irg_visited(current_ir_graph);
316 nodes_touched = irg_walk_in_or_dep_2(node, pre, post, env);
317 ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
321 * Walk over a graph. Follow all edges (including dependencies)
323 void irg_walk_in_or_dep_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
325 ir_graph * rem = current_ir_graph;
327 hook_irg_walk(irg, (generic_func *)pre, (generic_func *)post);
328 current_ir_graph = irg;
329 irg_walk_in_or_dep(get_irg_end(irg), pre, post, env);
330 irg->estimated_node_count = nodes_touched;
331 current_ir_graph = rem;
334 /***************************************************************************/
336 /* Walks back from n until it finds a real cf op. */
337 static ir_node *get_cf_op(ir_node *n)
339 while (!is_cfop(n) && !is_fragile_op(n) && !is_Bad(n)) {
347 static void irg_block_walk_2(ir_node *node, irg_walk_func *pre,
348 irg_walk_func *post, void *env)
352 if (Block_block_visited(node))
354 mark_Block_block_visited(node);
359 for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
360 /* find the corresponding predecessor block. */
361 ir_node *pred = get_cf_op(get_Block_cfgpred(node, i));
362 pred = get_nodes_block(pred);
363 if (get_irn_opcode(pred) == iro_Block) {
365 irg_block_walk_2(pred, pre, post, env);
367 assert(get_irn_opcode(pred) == iro_Bad);
376 /* walks only over Block nodes in the graph. Has it's own visited
377 flag, so that it can be interleaved with the other walker. */
378 void irg_block_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
380 ir_graph *irg = get_irn_irg(node);
381 ir_node *block, *pred;
384 hook_irg_block_walk(irg, node, (generic_func *)pre, (generic_func *)post);
387 ir_reserve_resources(irg, IR_RESOURCE_BLOCK_VISITED);
388 inc_irg_block_visited(irg);
389 block = is_Block(node) ? node : get_nodes_block(node);
390 assert(is_Block(block));
391 irg_block_walk_2(block, pre, post, env);
393 /* keepalive: the endless loops ... */
395 int arity = get_irn_arity(node);
396 for (i = 0; i < arity; i++) {
397 pred = get_irn_n(node, i);
398 if (!is_Block(pred)) {
399 pred = get_nodes_block(pred);
400 if (!is_Block(pred)) {
401 /* if rare cases a kept node might have a bad block input */
405 /* Sometimes the blocks died, but are still reachable through kept nodes.
406 * Make sure the algorithms that try to remove these reach them. */
407 irg_block_walk_2(pred, pre, post, env);
411 ir_free_resources(irg, IR_RESOURCE_BLOCK_VISITED);
415 * walk over a graph block wise
417 void irg_block_walk_graph(ir_graph *irg, irg_walk_func *pre,
418 irg_walk_func *post, void *env)
420 ir_graph * rem = current_ir_graph;
421 current_ir_graph = irg;
422 irg_block_walk(get_irg_end(irg), pre, post, env);
423 current_ir_graph = rem;
427 * Additionally walk over all anchors. Do NOT increase the visit flag.
429 void irg_walk_anchors(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
431 ir_graph * rem = current_ir_graph;
432 current_ir_graph = irg;
434 inc_irg_visited(irg);
435 irg_walk_2(irg->anchor, pre, post, env);
437 current_ir_graph = rem;
440 /********************************************************************/
442 typedef struct walk_env {
448 static void walk_initializer(ir_initializer_t *initializer, walk_env *env)
450 switch (initializer->kind) {
451 case IR_INITIALIZER_CONST:
452 irg_walk(initializer->consti.value, env->pre, env->post, env->env);
454 case IR_INITIALIZER_TARVAL:
455 case IR_INITIALIZER_NULL:
458 case IR_INITIALIZER_COMPOUND: {
460 for (i = 0; i < initializer->compound.n_initializers; ++i) {
461 ir_initializer_t *subinitializer
462 = initializer->compound.initializers[i];
463 walk_initializer(subinitializer, env);
468 panic("invalid initializer found");
472 * Walk to all constant expressions in this entity.
474 static void walk_entity(ir_entity *ent, void *env)
476 walk_env *my_env = (walk_env *)env;
478 if (ent->initializer != NULL) {
479 walk_initializer(ent->initializer, my_env);
480 } else if (entity_has_compound_ent_values(ent)) {
481 int i, n_vals = get_compound_ent_n_values(ent);
483 for (i = 0; i < n_vals; i++)
484 irg_walk(get_compound_ent_value(ent, i), my_env->pre, my_env->post, my_env->env);
488 /* Walks over all code in const_code_irg. */
489 void walk_const_code(irg_walk_func *pre, irg_walk_func *post, void *env)
497 ir_graph *rem = current_ir_graph;
498 current_ir_graph = get_const_code_irg();
499 inc_irg_visited(current_ir_graph);
505 /* Walk all types that can contain constant entities. */
506 for (s = IR_SEGMENT_FIRST; s <= IR_SEGMENT_LAST; ++s)
507 walk_types_entities(get_segment_type(s), &walk_entity, &my_env);
508 n_types = get_irp_n_types();
509 for (i = 0; i < n_types; i++)
510 walk_types_entities(get_irp_type(i), &walk_entity, &my_env);
511 for (i = 0; i < get_irp_n_irgs(); i++)
512 walk_types_entities(get_irg_frame_type(get_irp_irg(i)), &walk_entity, &my_env);
514 /* Walk constant array bounds. */
515 for (i = 0; i < n_types; i++) {
516 ir_type *tp = get_irp_type(i);
517 if (is_Array_type(tp)) {
518 int n_dim = get_array_n_dimensions(tp);
519 for (j = 0; j < n_dim; j++) {
520 ir_node *n = get_array_lower_bound(tp, j);
521 if (n) irg_walk(n, pre, post, env);
522 n = get_array_upper_bound(tp, j);
523 if (n) irg_walk(n, pre, post, env);
528 current_ir_graph = rem;