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_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
164 inc_irg_visited(current_ir_graph);
165 assert(current_ir_graph == get_irn_irg(node));
166 irg_walk_core(node, pre, post, env);
167 ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
173 void irg_walk_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
175 ir_graph * rem = current_ir_graph;
177 hook_irg_walk(irg, (generic_func *)pre, (generic_func *)post);
178 current_ir_graph = irg;
179 irg_walk(get_irg_end(irg), pre, post, env);
180 irg->estimated_node_count = nodes_touched;
181 current_ir_graph = rem;
184 /* Executes irg_walk(end, pre, post, env) for all irgraphs in irprog.
185 Sets current_ir_graph properly for each walk. Conserves current
187 void all_irg_walk(irg_walk_func *pre, irg_walk_func *post, void *env)
192 for (i = 0, n = get_irp_n_irgs(); i < n; i++) {
193 irg = get_irp_irg(i);
194 irg_walk_graph(irg, pre, post, env);
198 /***************************************************************************/
201 * specialized version of irg_walk_in_or_dep_2, called if only pre callback exists
203 * @return number of visited nodes
205 static unsigned irg_walk_in_or_dep_2_pre(ir_node *node, irg_walk_func *pre, void *env)
209 ir_graph *irg = get_irn_irg(node);
211 set_irn_visited(node, irg->visited);
215 if (node->op != op_Block) {
216 ir_node *pred = get_irn_n(node, -1);
217 if (pred->visited < irg->visited)
218 cnt += irg_walk_in_or_dep_2_pre(pred, pre, env);
220 for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
221 ir_node *pred = get_irn_in_or_dep(node, i);
222 if (pred->visited < irg->visited)
223 cnt += irg_walk_in_or_dep_2_pre(pred, pre, env);
229 * specialized version of irg_walk_in_or_dep_2, called if only post callback exists
231 * @return number of visited nodes
233 static unsigned irg_walk_in_or_dep_2_post(ir_node *node, irg_walk_func *post, void *env)
237 ir_graph *irg = get_irn_irg(node);
239 set_irn_visited(node, irg->visited);
241 if (node->op != op_Block) {
242 ir_node *pred = get_irn_n(node, -1);
243 if (pred->visited < irg->visited)
244 cnt += irg_walk_in_or_dep_2_post(pred, post, env);
246 for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
247 ir_node *pred = get_irn_in_or_dep(node, i);
248 if (pred->visited < irg->visited)
249 cnt += irg_walk_in_or_dep_2_post(pred, post, env);
258 * specialized version of irg_walk_in_or_dep_2, called if pre and post callbacks exist
260 * @return number of visited nodes
262 static unsigned irg_walk_in_or_dep_2_both(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
266 ir_graph *irg = get_irn_irg(node);
268 set_irn_visited(node, irg->visited);
272 if (node->op != op_Block) {
273 ir_node *pred = get_irn_n(node, -1);
274 if (pred->visited < irg->visited)
275 cnt += irg_walk_in_or_dep_2_both(pred, pre, post, env);
277 for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
278 ir_node *pred = get_irn_in_or_dep(node, i);
279 if (pred->visited < irg->visited)
280 cnt += irg_walk_in_or_dep_2_both(pred, pre, post, env);
289 * Intraprozedural graph walker. Follows dependency edges as well.
291 * @return number of visited nodes
293 static unsigned irg_walk_in_or_dep_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
295 if (irn_visited(node))
298 if (! post) return irg_walk_in_or_dep_2_pre (node, pre, env);
299 else if (! pre) return irg_walk_in_or_dep_2_post(node, post, env);
300 else return irg_walk_in_or_dep_2_both(node, pre, post, env);
304 * Generic graph walker. Follows dependency edges as well.
306 void irg_walk_in_or_dep(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
308 assert(is_ir_node(node));
310 ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
311 inc_irg_visited(current_ir_graph);
312 nodes_touched = irg_walk_in_or_dep_2(node, pre, post, env);
313 ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
317 * Walk over a graph. Follow all edges (including dependencies)
319 void irg_walk_in_or_dep_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
321 ir_graph * rem = current_ir_graph;
323 hook_irg_walk(irg, (generic_func *)pre, (generic_func *)post);
324 current_ir_graph = irg;
325 irg_walk_in_or_dep(get_irg_end(irg), pre, post, env);
326 irg->estimated_node_count = nodes_touched;
327 current_ir_graph = rem;
330 /***************************************************************************/
332 /* Walks back from n until it finds a real cf op. */
333 static ir_node *get_cf_op(ir_node *n)
335 while (!is_cfop(n) && !is_fragile_op(n) && !is_Bad(n)) {
343 static void irg_block_walk_2(ir_node *node, irg_walk_func *pre,
344 irg_walk_func *post, void *env)
348 if (Block_block_visited(node))
350 mark_Block_block_visited(node);
355 for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
356 /* find the corresponding predecessor block. */
357 ir_node *pred = get_cf_op(get_Block_cfgpred(node, i));
358 pred = get_nodes_block(pred);
359 if (get_irn_opcode(pred) == iro_Block) {
361 irg_block_walk_2(pred, pre, post, env);
363 assert(get_irn_opcode(pred) == iro_Bad);
372 /* walks only over Block nodes in the graph. Has it's own visited
373 flag, so that it can be interleaved with the other walker. */
374 void irg_block_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
376 ir_graph *irg = get_irn_irg(node);
377 ir_node *block, *pred;
380 hook_irg_block_walk(irg, node, (generic_func *)pre, (generic_func *)post);
383 ir_reserve_resources(irg, IR_RESOURCE_BLOCK_VISITED);
384 inc_irg_block_visited(irg);
385 block = is_Block(node) ? node : get_nodes_block(node);
386 assert(is_Block(block));
387 irg_block_walk_2(block, pre, post, env);
389 /* keepalive: the endless loops ... */
391 int arity = get_irn_arity(node);
392 for (i = 0; i < arity; i++) {
393 pred = get_irn_n(node, i);
394 if (!is_Block(pred)) {
395 pred = get_nodes_block(pred);
396 if (!is_Block(pred)) {
397 /* if rare cases a kept node might have a bad block input */
401 /* Sometimes the blocks died, but are still reachable through kept nodes.
402 * Make sure the algorithms that try to remove these reach them. */
403 irg_block_walk_2(pred, pre, post, env);
407 ir_free_resources(irg, IR_RESOURCE_BLOCK_VISITED);
411 * walk over a graph block wise
413 void irg_block_walk_graph(ir_graph *irg, irg_walk_func *pre,
414 irg_walk_func *post, void *env)
416 ir_graph * rem = current_ir_graph;
417 current_ir_graph = irg;
418 irg_block_walk(get_irg_end(irg), pre, post, env);
419 current_ir_graph = rem;
423 * Additionally walk over all anchors. Do NOT increase the visit flag.
425 void irg_walk_anchors(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
427 ir_graph * rem = current_ir_graph;
428 current_ir_graph = irg;
430 inc_irg_visited(irg);
431 irg_walk_2(irg->anchor, pre, post, env);
433 current_ir_graph = rem;
436 /********************************************************************/
438 typedef struct walk_env {
444 static void walk_initializer(ir_initializer_t *initializer, walk_env *env)
446 switch (initializer->kind) {
447 case IR_INITIALIZER_CONST:
448 irg_walk(initializer->consti.value, env->pre, env->post, env->env);
450 case IR_INITIALIZER_TARVAL:
451 case IR_INITIALIZER_NULL:
454 case IR_INITIALIZER_COMPOUND: {
456 for (i = 0; i < initializer->compound.n_initializers; ++i) {
457 ir_initializer_t *subinitializer
458 = initializer->compound.initializers[i];
459 walk_initializer(subinitializer, env);
464 panic("invalid initializer found");
468 * Walk to all constant expressions in this entity.
470 static void walk_entity(ir_entity *ent, void *env)
472 walk_env *my_env = (walk_env *)env;
474 if (ent->initializer != NULL) {
475 walk_initializer(ent->initializer, my_env);
476 } else if (entity_has_compound_ent_values(ent)) {
477 int i, n_vals = get_compound_ent_n_values(ent);
479 for (i = 0; i < n_vals; i++)
480 irg_walk(get_compound_ent_value(ent, i), my_env->pre, my_env->post, my_env->env);
484 /* Walks over all code in const_code_irg. */
485 void walk_const_code(irg_walk_func *pre, irg_walk_func *post, void *env)
491 ir_graph *rem = current_ir_graph;
492 current_ir_graph = get_const_code_irg();
493 inc_irg_visited(current_ir_graph);
499 /* Walk all types that can contain constant entities. */
500 for (s = IR_SEGMENT_FIRST; s <= IR_SEGMENT_LAST; s++)
501 walk_types_entities(get_segment_type(s), &walk_entity, &my_env);
502 n_types = get_irp_n_types();
503 for (i = 0; i < n_types; i++)
504 walk_types_entities(get_irp_type(i), &walk_entity, &my_env);
505 for (i = 0; i < get_irp_n_irgs(); i++)
506 walk_types_entities(get_irg_frame_type(get_irp_irg(i)), &walk_entity, &my_env);
508 /* Walk constant array bounds. */
509 for (i = 0; i < n_types; i++) {
510 ir_type *tp = get_irp_type(i);
511 if (is_Array_type(tp)) {
512 int n_dim = get_array_n_dimensions(tp);
513 for (j = 0; j < n_dim; j++) {
514 ir_node *n = get_array_lower_bound(tp, j);
515 if (n) irg_walk(n, pre, post, env);
516 n = get_array_upper_bound(tp, j);
517 if (n) irg_walk(n, pre, post, env);
522 current_ir_graph = rem;