1 /* Copyright (C) 1998 - 2000 by Universitaet Karlsruhe
2 ** All rights reserved.
4 ** Author: Boris Boesler
6 ** traverse an ir graph
7 ** - execute the pre function before recursion
8 ** - execute the post function after recursion
20 # include "irgraph.h" /* visited flag */
27 /* walk over an interprocedural graph (callgraph). Visits only graphs in irg_set. */
28 static void irg_walk_cg(ir_node * node, int visited, eset * irg_set, irg_walk_func pre, irg_walk_func post, void * env) {
30 ir_graph * rem = current_ir_graph;
34 if (get_irn_visited(node) >= visited) return;
36 set_irn_visited(node, visited);
38 pred = skip_Proj(node);
39 if (get_irn_op(pred) == op_CallBegin
40 || get_irn_op(pred) == op_EndReg
41 || get_irn_op(pred) == op_EndExcept) {
42 current_ir_graph = get_irn_irg(pred);
45 if (pre) pre(node, env);
47 if (is_no_Block(node)) irg_walk_cg(get_nodes_Block(node), visited, irg_set, pre, post, env);
49 if (get_irn_op(node) == op_Block) { /* block */
50 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
51 ir_node * exec = get_irn_n(node, i);
52 ir_node * pred = skip_Proj(exec);
53 if ((get_irn_op(pred) != op_CallBegin
54 && get_irn_op(pred) != op_EndReg
55 && get_irn_op(pred) != op_EndExcept)
56 || eset_contains(irg_set, get_irn_irg(pred))) {
57 irg_walk_cg(exec, visited, irg_set, pre, post, env);
60 } else if (get_irn_op(node) == op_Filter) {
61 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
62 ir_node * pred = get_irn_n(node, i);
63 if (get_irn_op(pred) == op_Unknown || get_irn_op(pred) == op_Bad) {
64 irg_walk_cg(pred, visited, irg_set, pre, post, env);
67 exec = skip_Proj(get_Block_cfgpred(get_nodes_Block(node), i));
68 assert(get_irn_op(exec) == op_CallBegin
69 || get_irn_op(exec) == op_EndReg
70 || get_irn_op(exec) == op_EndExcept);
71 if (eset_contains(irg_set, get_irn_irg(exec))) {
72 current_ir_graph = get_irn_irg(exec);
73 irg_walk_cg(pred, visited, irg_set, pre, post, env);
74 current_ir_graph = rem;
79 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
80 irg_walk_cg(get_irn_n(node, i), visited, irg_set, pre, post, env);
84 if (post) post(node, env);
86 current_ir_graph = rem;
90 /* Insert all ir_graphs in irg_set, that are (transitive) reachable. */
91 static void collect_irgs(ir_node * node, eset * irg_set) {
92 if (get_irn_op(node) == op_Call) {
94 for (i = get_Call_n_callees(node) - 1; i >= 0; --i) {
95 entity * ent = get_Call_callee(node, i);
96 ir_graph * irg = ent ? get_entity_irg(ent) : NULL;
97 if (irg && !eset_contains(irg_set, irg)) {
98 eset_insert(irg_set, irg);
99 irg_walk_graph(irg, (irg_walk_func) collect_irgs, NULL, irg_set);
106 void irg_walk_2(ir_node *node, irg_walk_func pre, irg_walk_func post, void * env)
112 /* printf(" - "); DDMSG2(node); */
114 if (get_irn_visited(node) < get_irg_visited(current_ir_graph)) {
116 /* printf(" -> "); DDMSG2(node); */
117 set_irn_visited(node, get_irg_visited(current_ir_graph));
123 if (is_no_Block(node)) {
124 irg_walk_2(get_nodes_Block(node), pre, post, env);
126 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
127 /* printf(" "); DDMSG2(node);
128 printf(" "); DDMSG2(get_irn_n(node, i)); */
130 irg_walk_2(get_irn_n(node, i), pre, post, env);
133 /* printf(" <- "); DDMSG2(node); */
141 void irg_walk(ir_node *node, irg_walk_func pre, irg_walk_func post, void *env)
144 if (interprocedural_view) {
145 eset * irg_set = eset_create();
148 interprocedural_view = false;
149 eset_insert(irg_set, current_ir_graph);
150 irg_walk(node, (irg_walk_func) collect_irgs, NULL, irg_set);
151 interprocedural_view = true;
152 visited = get_max_irg_visited() + 1;
153 irg_walk_cg(node, visited, irg_set, pre, post, env);
154 for (irg = eset_first(irg_set); irg; irg = eset_next(irg_set)) {
155 set_irg_visited(irg, visited);
157 eset_destroy(irg_set);
159 inc_irg_visited(current_ir_graph);
160 irg_walk_2(node, pre, post, env);
166 void irg_walk_graph(ir_graph *irg, irg_walk_func pre, irg_walk_func post, void *env) {
167 ir_graph * rem = current_ir_graph;
168 current_ir_graph = irg;
169 irg_walk(get_irg_end(irg), pre, post, env);
170 current_ir_graph = rem;
174 /***************************************************************************/
176 /* Executes irg_walk(end, pre, post, env) for all irgraphs in irprog.
177 Sets current_ir_graph properly for each walk. Conserves current
179 void all_irg_walk(irg_walk_func pre, irg_walk_func post, void *env) {
183 rem = current_ir_graph;
185 for (i = 0; i < get_irp_n_irgs(); i++) {
186 irg = get_irp_irg(i);
187 current_ir_graph = irg;
188 irg_walk(get_irg_end(irg), pre, post, env);
190 current_ir_graph = rem;
193 /***************************************************************************/
195 /* Walks back from n until it finds a real cf op. */
196 ir_node *get_cf_op(ir_node *n) {
202 if (!(is_cfop(pred) || is_fragile_op(pred) ||
203 (get_irn_op(pred) == op_Bad)))
209 void irg_block_walk_2(ir_node *node, irg_walk_func pre, irg_walk_func post, void *env)
213 assert(get_irn_opcode(node) == iro_Block);
215 if(get_Block_block_visited(node) < get_irg_block_visited(current_ir_graph)) {
216 set_Block_block_visited(node, get_irg_block_visited(current_ir_graph));
221 for(i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
223 /* find the corresponding predecessor block. */
224 ir_node *pred = get_cf_op(get_Block_cfgpred(node, i));
225 /* GL: I'm not sure whether this assert must go through. There
226 could be Id chains?? Tuple/Proj .... */
229 || is_fragile_op(pred)
230 || (get_irn_op(pred) == op_Bad));
232 pred = get_nodes_Block(pred);
233 if(get_irn_opcode(pred) == iro_Block) {
235 irg_block_walk_2(pred, pre, post, env);
238 assert(get_irn_opcode(pred) == iro_Bad);
249 /* walks only over Block nodes in the graph. Has it's own visited
250 flag, so that it can be interleaved with the other walker. */
251 void irg_block_walk(ir_node *node, irg_walk_func pre, irg_walk_func post, void *env)
253 ir_node *block, *pred;
257 assert(!interprocedural_view); /* interprocedural_view not implemented, because it
258 * interleaves with irg_walk */
259 inc_irg_block_visited(current_ir_graph);
260 if (is_no_Block(node)) block = get_nodes_Block(node); else block = node;
261 assert(get_irn_opcode(block) == iro_Block);
262 irg_block_walk_2(block, pre, post, env);
263 /* keepalive: the endless loops ... */
264 if (get_irn_op(node) == op_End)
265 for (i = 0; i < get_irn_arity(node); i++) {
266 pred = get_irn_n(node, i);
267 if (get_irn_op(pred) == op_Block)
268 irg_block_walk_2(pred, pre, post, env);
275 void irg_block_walk_graph(ir_graph *irg, irg_walk_func pre, irg_walk_func post, void *env) {
276 ir_graph * rem = current_ir_graph;
277 current_ir_graph = irg;
278 irg_block_walk(get_irg_end(irg), pre, post, env);
279 current_ir_graph = rem;
284 /********************************************************************/
285 /** Walking support for interprocedural analysis **/
286 /********************************************************************/
288 #define MIN_STACK_SIZE 40
290 typedef struct callsite_stack {
295 /* Access the stack in the irg **************************************/
298 set_irg_callsite_stack(ir_graph *g, callsite_stack *s) {
302 static INLINE callsite_stack *
303 get_irg_callsite_stack(ir_graph *g) {
304 return (callsite_stack *) get_irg_link(g);
307 /* A stack of callsites *********************************************/
309 /* @@@ eventually change the implementation so the new_ only sets the field
310 to NULL, and the stack is only allocated if used. Saves Memory! */
311 static INLINE callsite_stack *
312 new_callsite_stack(ir_graph *g) {
313 callsite_stack *res = (callsite_stack *)malloc(sizeof(callsite_stack));
315 res->s = NEW_ARR_F (ir_node *, MIN_STACK_SIZE);
316 set_irg_callsite_stack(g, res);
321 free_callsite_stack(ir_graph *g) {
322 callsite_stack *s = get_irg_callsite_stack(g);
328 push_callsite(ir_graph *callee, ir_node *callsite) {
329 callsite_stack *s = get_irg_callsite_stack(callee);
330 if (s->tos == ARR_LEN(s->s)) {
331 int nlen = ARR_LEN (s->s) * 2;
332 ARR_RESIZE (ir_node *, s->s, nlen);
334 s->s[s->tos] = callsite;
338 static INLINE ir_node *
339 get_top_of_callsite_stack(ir_graph *callee) {
340 callsite_stack *s = get_irg_callsite_stack(callee);
341 return (s->s[s->tos-1]);
345 ir_node * pop_callsite(ir_graph *callee) {
346 callsite_stack *s = get_irg_callsite_stack(callee);
348 return (s->s[s->tos]);
352 /* Initialization routines ******************************************/
354 void init_ip_walk () {
356 for (i = 0; i < get_irp_n_irgs(); i++)
357 new_callsite_stack(get_irp_irg(i));
360 void finish_ip_walk() {
362 for (i = 0; i < get_irp_n_irgs(); i++)
363 free_callsite_stack(get_irp_irg(i));
364 set_irg_link(get_irp_irg(i), NULL);
367 /* walker routines **************************************************/
369 /* cf_pred is End* */
371 enter_procedure(ir_node *block, ir_node *cf_pred, int pos) {
373 ir_graph *irg = get_irn_irg(cf_pred);
375 assert(interprocedural_view);
377 interprocedural_view = 0;
378 callbegin = skip_Proj(get_irn_n(block, 0));
379 assert(get_irn_op(callbegin) == op_CallBegin);
380 interprocedural_view = 1;
382 push_callsite(irg, callbegin);
383 current_ir_graph = irg;
386 /* cf_pred is CallBegin */
388 leave_procedure(ir_node *block, ir_node *cf_pred, int pos) {
389 ir_node *tos = get_top_of_callsite_stack(current_ir_graph);
391 assert(get_irn_op(cf_pred) == op_CallBegin);
393 if (tos == cf_pred) {
394 /* We entered this procedure by the call pred pos refers to. */
395 pop_callsite(current_ir_graph);
396 current_ir_graph = get_CallBegin_irg(cf_pred);
404 ir_node *get_irn_ip_pred(ir_node *n, int pos) {
406 if (interprocedural_view) {
408 /* Find the cf_pred refering to pos. */
411 if (get_irn_opcode(n) == iro_Filter) block = get_nodes_Block(n);
412 cf_pred = skip_Proj(get_irn_n(block, pos));
414 /* Check whether we enter or leave a procedure and act according. */
415 if ((get_irn_op(cf_pred) == op_EndReg) ||
416 (get_irn_op(cf_pred) == op_EndExcept))
417 enter_procedure(block, cf_pred, pos);
418 if (get_irn_op(cf_pred) == op_CallBegin)
419 if (!leave_procedure(block, cf_pred, pos)) return NULL;
422 return get_irn_n(n, pos);
426 re_enter_procedure(ir_node *block, ir_node *cf_pred, int pos) {
427 ir_node *callbegin = pop_callsite(current_ir_graph);
428 assert(interprocedural_view);
429 current_ir_graph = get_CallBegin_irg(callbegin);
433 re_leave_procedure(ir_node *block, ir_node *cf_pred, int pos) {
437 assert(get_irn_op(cf_pred) == op_CallBegin);
439 /* Find the irg block is in. */
440 proj = get_Block_cg_cfgpred(block, pos);
441 assert(is_Proj(proj));
442 callee = get_entity_irg(get_Call_callee(get_CallBegin_call(cf_pred),
443 get_Proj_proj(proj)));
444 current_ir_graph = callee;
445 push_callsite(callee, cf_pred);
449 return_recur(ir_node *n, int pos) {
453 if (!interprocedural_view) return;
455 /* Find the cf_pred refering to pos. */
457 if (get_irn_opcode(n) == iro_Filter) block = get_nodes_Block(n);
458 cf_pred = skip_Proj(get_irn_n(block, pos));
460 /* Check whether we re_enter or re_leave a procedure and act according. */
461 if ((get_irn_op(cf_pred) == op_EndReg) ||
462 (get_irn_op(cf_pred) == op_EndExcept))
463 re_enter_procedure(block, cf_pred, pos);
464 if (get_irn_op(cf_pred) == op_CallBegin)
465 re_leave_procedure(block, cf_pred, pos);