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"
45 * specialized version of irg_walk_2, called if only pre callback exists
47 * @return number of visited nodes
49 static unsigned irg_walk_2_pre(ir_node *node, irg_walk_func *pre, void *env)
53 ir_graph *irg = get_irn_irg(node);
55 set_irn_visited(node, irg->visited);
59 if (node->op != op_Block) {
60 ir_node *pred = get_irn_n(node, -1);
61 if (pred->visited < irg->visited)
62 cnt += irg_walk_2_pre(pred, pre, env);
64 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
65 ir_node *pred = get_irn_n(node, i);
66 if (pred->visited < irg->visited)
67 cnt += irg_walk_2_pre(pred, pre, env);
73 * specialized version of irg_walk_2, called if only post callback exists
75 * @return number of visited nodes
77 static unsigned irg_walk_2_post(ir_node *node, irg_walk_func *post, void *env)
81 ir_graph *irg = get_irn_irg(node);
83 set_irn_visited(node, irg->visited);
85 if (node->op != op_Block) {
86 ir_node *pred = get_irn_n(node, -1);
87 if (pred->visited < irg->visited)
88 cnt += irg_walk_2_post(pred, post, env);
90 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
91 ir_node *pred = get_irn_n(node, i);
92 if (pred->visited < irg->visited)
93 cnt += irg_walk_2_post(pred, post, env);
102 * specialized version of irg_walk_2, called if pre and post callbacks exist
104 * @return number of visited nodes
106 static unsigned irg_walk_2_both(ir_node *node, irg_walk_func *pre,
107 irg_walk_func *post, void *env)
111 ir_graph *irg = get_irn_irg(node);
113 set_irn_visited(node, irg->visited);
117 if (node->op != op_Block) {
118 ir_node *pred = get_irn_n(node, -1);
119 if (pred->visited < irg->visited)
120 cnt += irg_walk_2_both(pred, pre, post, env);
122 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
123 ir_node *pred = get_irn_n(node, i);
124 if (pred->visited < irg->visited)
125 cnt += irg_walk_2_both(pred, pre, post, env);
134 * Intraprozedural graph walker.
136 * @return number of visited nodes
138 unsigned irg_walk_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
141 if (irn_visited(node))
144 if (!post) return irg_walk_2_pre (node, pre, env);
145 else if (!pre) return irg_walk_2_post(node, post, env);
146 else return irg_walk_2_both(node, pre, post, env);
150 static unsigned nodes_touched = 0;
152 void irg_walk_core(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
155 assert(is_ir_node(node));
156 nodes_touched = irg_walk_2(node, pre, post, env);
159 void irg_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
162 ir_graph *irg = get_irn_irg(node);
163 ir_graph *rem = current_ir_graph;
165 current_ir_graph = irg;
166 ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
167 inc_irg_visited(irg);
168 irg_walk_core(node, pre, post, env);
169 ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
170 current_ir_graph = rem;
176 void irg_walk_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
178 ir_graph * rem = current_ir_graph;
180 hook_irg_walk(irg, (generic_func *)pre, (generic_func *)post);
181 current_ir_graph = irg;
182 irg_walk(get_irg_end(irg), pre, post, env);
183 irg->estimated_node_count = nodes_touched;
184 current_ir_graph = rem;
187 /* Executes irg_walk(end, pre, post, env) for all irgraphs in irprog.
188 Sets current_ir_graph properly for each walk. Conserves current
190 void all_irg_walk(irg_walk_func *pre, irg_walk_func *post, void *env)
195 for (i = 0, n = get_irp_n_irgs(); i < n; i++) {
196 irg = get_irp_irg(i);
197 irg_walk_graph(irg, pre, post, env);
201 /***************************************************************************/
204 * specialized version of irg_walk_in_or_dep_2, called if only pre callback exists
206 * @return number of visited nodes
208 static unsigned irg_walk_in_or_dep_2_pre(ir_node *node, irg_walk_func *pre, void *env)
212 ir_graph *irg = get_irn_irg(node);
214 set_irn_visited(node, irg->visited);
218 if (node->op != op_Block) {
219 ir_node *pred = get_irn_n(node, -1);
220 if (pred->visited < irg->visited)
221 cnt += irg_walk_in_or_dep_2_pre(pred, pre, env);
223 for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
224 ir_node *pred = get_irn_in_or_dep(node, i);
225 if (pred->visited < irg->visited)
226 cnt += irg_walk_in_or_dep_2_pre(pred, pre, env);
232 * specialized version of irg_walk_in_or_dep_2, called if only post callback exists
234 * @return number of visited nodes
236 static unsigned irg_walk_in_or_dep_2_post(ir_node *node, irg_walk_func *post, void *env)
240 ir_graph *irg = get_irn_irg(node);
242 set_irn_visited(node, irg->visited);
244 if (node->op != op_Block) {
245 ir_node *pred = get_irn_n(node, -1);
246 if (pred->visited < irg->visited)
247 cnt += irg_walk_in_or_dep_2_post(pred, post, env);
249 for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
250 ir_node *pred = get_irn_in_or_dep(node, i);
251 if (pred->visited < irg->visited)
252 cnt += irg_walk_in_or_dep_2_post(pred, post, env);
261 * specialized version of irg_walk_in_or_dep_2, called if pre and post callbacks exist
263 * @return number of visited nodes
265 static unsigned irg_walk_in_or_dep_2_both(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
269 ir_graph *irg = get_irn_irg(node);
271 set_irn_visited(node, irg->visited);
275 if (node->op != op_Block) {
276 ir_node *pred = get_irn_n(node, -1);
277 if (pred->visited < irg->visited)
278 cnt += irg_walk_in_or_dep_2_both(pred, pre, post, env);
280 for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
281 ir_node *pred = get_irn_in_or_dep(node, i);
282 if (pred->visited < irg->visited)
283 cnt += irg_walk_in_or_dep_2_both(pred, pre, post, env);
292 * Intraprozedural graph walker. Follows dependency edges as well.
294 * @return number of visited nodes
296 static unsigned irg_walk_in_or_dep_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
298 if (irn_visited(node))
301 if (! post) return irg_walk_in_or_dep_2_pre (node, pre, env);
302 else if (! pre) return irg_walk_in_or_dep_2_post(node, post, env);
303 else return irg_walk_in_or_dep_2_both(node, pre, post, env);
307 * Generic graph walker. Follows dependency edges as well.
309 void irg_walk_in_or_dep(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
311 assert(is_ir_node(node));
313 ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
314 inc_irg_visited(current_ir_graph);
315 nodes_touched = irg_walk_in_or_dep_2(node, pre, post, env);
316 ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
320 * Walk over a graph. Follow all edges (including dependencies)
322 void irg_walk_in_or_dep_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
324 ir_graph * rem = current_ir_graph;
326 hook_irg_walk(irg, (generic_func *)pre, (generic_func *)post);
327 current_ir_graph = irg;
328 irg_walk_in_or_dep(get_irg_end(irg), pre, post, env);
329 irg->estimated_node_count = nodes_touched;
330 current_ir_graph = rem;
333 /***************************************************************************/
335 /* Walks back from n until it finds a real cf op. */
336 static ir_node *get_cf_op(ir_node *n)
338 while (!is_cfop(n) && !is_fragile_op(n) && !is_Bad(n)) {
346 static void irg_block_walk_2(ir_node *node, irg_walk_func *pre,
347 irg_walk_func *post, void *env)
351 if (Block_block_visited(node))
353 mark_Block_block_visited(node);
358 for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
359 /* find the corresponding predecessor block. */
360 ir_node *pred = get_cf_op(get_Block_cfgpred(node, i));
361 pred = get_nodes_block(pred);
362 if (get_irn_opcode(pred) == iro_Block) {
364 irg_block_walk_2(pred, pre, post, env);
366 assert(get_irn_opcode(pred) == iro_Bad);
375 /* walks only over Block nodes in the graph. Has its own visited
376 flag, so that it can be interleaved with the other walker. */
377 void irg_block_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
380 ir_graph *irg = get_irn_irg(node);
381 ir_node *block = is_Block(node) ? node : get_nodes_block(node);
383 hook_irg_block_walk(irg, node, (generic_func *)pre, (generic_func *)post);
385 ir_reserve_resources(irg, IR_RESOURCE_BLOCK_VISITED);
386 inc_irg_block_visited(irg);
387 irg_block_walk_2(block, pre, post, env);
389 /* Some blocks might be only reachable through keep-alive edges */
391 int arity = get_irn_arity(node);
393 for (i = 0; i < arity; i++) {
394 ir_node *pred = get_irn_n(node, i);
397 irg_block_walk_2(pred, pre, post, env);
401 ir_free_resources(irg, IR_RESOURCE_BLOCK_VISITED);
405 * walk over a graph block wise
407 void irg_block_walk_graph(ir_graph *irg, irg_walk_func *pre,
408 irg_walk_func *post, void *env)
410 ir_graph * rem = current_ir_graph;
411 current_ir_graph = irg;
412 irg_block_walk(get_irg_end(irg), pre, post, env);
413 current_ir_graph = rem;
417 * Additionally walk over all anchors. Do NOT increase the visit flag.
419 void irg_walk_anchors(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
421 ir_graph * rem = current_ir_graph;
422 current_ir_graph = irg;
424 ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
425 inc_irg_visited(irg);
426 irg_walk_2(irg->anchor, pre, post, env);
427 ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
429 current_ir_graph = rem;
432 /********************************************************************/
434 typedef struct walk_env {
440 static void walk_initializer(ir_initializer_t *initializer, walk_env *env)
442 switch (initializer->kind) {
443 case IR_INITIALIZER_CONST:
444 irg_walk(initializer->consti.value, env->pre, env->post, env->env);
446 case IR_INITIALIZER_TARVAL:
447 case IR_INITIALIZER_NULL:
450 case IR_INITIALIZER_COMPOUND: {
452 for (i = 0; i < initializer->compound.n_initializers; ++i) {
453 ir_initializer_t *subinitializer
454 = initializer->compound.initializers[i];
455 walk_initializer(subinitializer, env);
460 panic("invalid initializer found");
464 * Walk to all constant expressions in this entity.
466 static void walk_entity(ir_entity *ent, void *env)
468 walk_env *my_env = (walk_env *)env;
470 if (ent->initializer != NULL) {
471 walk_initializer(ent->initializer, my_env);
472 } else if (entity_has_compound_ent_values(ent)) {
473 size_t i, n_vals = get_compound_ent_n_values(ent);
475 for (i = 0; i < n_vals; i++)
476 irg_walk(get_compound_ent_value(ent, i), my_env->pre, my_env->post, my_env->env);
480 /* Walks over all code in const_code_irg. */
481 void walk_const_code(irg_walk_func *pre, irg_walk_func *post, void *env)
488 ir_graph *rem = current_ir_graph;
489 current_ir_graph = get_const_code_irg();
490 inc_irg_visited(current_ir_graph);
496 /* Walk all types that can contain constant entities. */
497 for (s = IR_SEGMENT_FIRST; s <= IR_SEGMENT_LAST; ++s)
498 walk_types_entities(get_segment_type(s), &walk_entity, &my_env);
499 n_types = get_irp_n_types();
500 for (i = 0; i < n_types; i++)
501 walk_types_entities(get_irp_type(i), &walk_entity, &my_env);
502 for (i = 0; i < get_irp_n_irgs(); i++)
503 walk_types_entities(get_irg_frame_type(get_irp_irg(i)), &walk_entity, &my_env);
505 /* Walk constant array bounds. */
506 for (i = 0; i < n_types; i++) {
507 ir_type *tp = get_irp_type(i);
508 if (is_Array_type(tp)) {
509 size_t j, n_dim = get_array_n_dimensions(tp);
510 for (j = 0; j < n_dim; j++) {
511 ir_node *n = get_array_lower_bound(tp, j);
512 if (n) irg_walk(n, pre, post, env);
513 n = get_array_upper_bound(tp, j);
514 if (n) irg_walk(n, pre, post, env);
519 current_ir_graph = rem;