nsz Git - libfirm/blob - ir/ir/irgwalk.c

   1 /* Copyright (C) 1998 - 2000 by Universitaet Karlsruhe
   2 ** All rights reserved.
   3 **
   4 ** Author: Boris Boesler
   5 **
   6 ** traverse an ir graph
   7 ** - execute the pre function before recursion
   8 ** - execute the post function after recursion
   9 */
  10
  11 /* $Id$ */
  12
  13 #ifdef HAVE_CONFIG_H
  14 # include <config.h>
  15 #endif
  16
  17 # include "irnode.h"
  18 # include "irgraph.h" /* visited flag */
  19 # include "irprog.h"
  20 # include "irgwalk.h"
  21
  22 # include "eset.h"
  23 # include "array.h"
  24
  25 /* walk over an interprocedural graph (callgraph). Visits only graphs in irg_set. */
  26 static void irg_walk_cg(ir_node * node, int visited, eset * irg_set, irg_walk_func pre, irg_walk_func post, void * env) {
  27   int i;
  28   ir_graph * rem = current_ir_graph;
  29   ir_node * pred;
  30
  31   assert(node);
  32   if (get_irn_visited(node) >= visited) return;
  33
  34   set_irn_visited(node, visited);
  35
  36   pred = skip_Proj(node);
  37   if (get_irn_op(pred) == op_CallBegin
  38       || get_irn_op(pred) == op_EndReg
  39       || get_irn_op(pred) == op_EndExcept) {
  40     current_ir_graph = get_irn_irg(pred);
  41   }
  42
  43   if (pre) pre(node, env);
  44
  45   if (is_no_Block(node)) irg_walk_cg(get_nodes_Block(node), visited, irg_set, pre, post, env);
  46
  47   if (get_irn_op(node) == op_Block) { /* block */
  48     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
  49       ir_node * exec = get_irn_n(node, i);
  50       ir_node * pred = skip_Proj(exec);
  51       if ((get_irn_op(pred) != op_CallBegin
  52            && get_irn_op(pred) != op_EndReg
  53            && get_irn_op(pred) != op_EndExcept)
  54           || eset_contains(irg_set, get_irn_irg(pred))) {
  55         irg_walk_cg(exec, visited, irg_set, pre, post, env);
  56       }
  57     }
  58   } else if (get_irn_op(node) == op_Filter) {
  59     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
  60       ir_node * pred = get_irn_n(node, i);
  61       if (get_irn_op(pred) == op_Unknown || get_irn_op(pred) == op_Bad) {
  62         irg_walk_cg(pred, visited, irg_set, pre, post, env);
  63       } else {
  64         ir_node * exec;
  65         exec = skip_Proj(get_Block_cfgpred(get_nodes_Block(node), i));
  66         assert(get_irn_op(exec) == op_CallBegin
  67                || get_irn_op(exec) == op_EndReg
  68                || get_irn_op(exec) == op_EndExcept);
  69         if (eset_contains(irg_set, get_irn_irg(exec))) {
  70           current_ir_graph = get_irn_irg(exec);
  71           irg_walk_cg(pred, visited, irg_set, pre, post, env);
  72           current_ir_graph = rem;
  73         }
  74       }
  75     }
  76   } else {
  77     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
  78       irg_walk_cg(get_irn_n(node, i), visited, irg_set, pre, post, env);
  79     }
  80   }
  81
  82   if (post) post(node, env);
  83
  84   current_ir_graph = rem;
  85 }
  86
  87
  88 /* Insert all ir_graphs in irg_set, that are (transitive) reachable. */
  89 static void collect_irgs(ir_node * node, eset * irg_set) {
  90   if (get_irn_op(node) == op_Call) {
  91     int i;
  92     for (i = get_Call_n_callees(node) - 1; i >= 0; --i) {
  93       entity * ent = get_Call_callee(node, i);
  94       ir_graph * irg = ent ? get_entity_irg(ent) : NULL;
  95       if (irg && !eset_contains(irg_set, irg)) {
  96         eset_insert(irg_set, irg);
  97         irg_walk_graph(irg, (irg_walk_func) collect_irgs, NULL, irg_set);
  98       }
  99     }
 100   }
 101 }
 102
 103
 104 void irg_walk_2(ir_node *node, irg_walk_func pre, irg_walk_func post, void * env)
 105 {
 106   int i;
 107
 108
 109   assert(node);
 110   /*      printf(" - "); DDMSG2(node);  */
 111
 112   if (get_irn_visited(node) < get_irg_visited(current_ir_graph)) {
 113
 114 /*      printf(" -> "); DDMSG2(node);  */
 115     set_irn_visited(node, get_irg_visited(current_ir_graph));
 116
 117     if (pre) {
 118       pre(node, env);
 119     }
 120
 121     if (is_no_Block(node)) {
 122       irg_walk_2(get_nodes_Block(node), pre, post, env);
 123     }
 124     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 125       /* printf("   "); DDMSG2(node);
 126          printf("   "); DDMSG2(get_irn_n(node, i));  */
 127
 128       irg_walk_2(get_irn_n(node, i), pre, post, env);
 129     }
 130
 131 /*      printf(" <- "); DDMSG2(node);  */
 132     if (post)
 133       post(node, env);
 134   }
 135   return;
 136 }
 137
 138
 139 void irg_walk(ir_node *node, irg_walk_func pre, irg_walk_func post, void *env)
 140 {
 141   assert(node);
 142   if (interprocedural_view) {
 143     eset * irg_set = eset_create();
 144     int visited;
 145     ir_graph * irg;
 146     interprocedural_view = false;
 147     eset_insert(irg_set, current_ir_graph);
 148     irg_walk(node, (irg_walk_func) collect_irgs, NULL, irg_set);
 149     interprocedural_view = true;
 150     visited = get_max_irg_visited() + 1;
 151     irg_walk_cg(node, visited, irg_set, pre, post, env);
 152     for (irg = eset_first(irg_set); irg; irg = eset_next(irg_set)) {
 153       set_irg_visited(irg, visited);
 154     }
 155     eset_destroy(irg_set);
 156   } else {
 157     inc_irg_visited(current_ir_graph);
 158     irg_walk_2(node, pre, post, env);
 159   }
 160   return;
 161 }
 162
 163
 164 void irg_walk_graph(ir_graph *irg, irg_walk_func pre, irg_walk_func post, void *env) {
 165   ir_graph * rem = current_ir_graph;
 166   current_ir_graph = irg;
 167   irg_walk(get_irg_end(irg), pre, post, env);
 168   current_ir_graph = rem;
 169 }
 170
 171
 172 /***************************************************************************/
 173
 174 /* Executes irg_walk(end, pre, post, env) for all irgraphs in irprog.
 175    Sets current_ir_graph properly for each walk.  Conserves current
 176    current_ir_graph. */
 177 void all_irg_walk(irg_walk_func pre, irg_walk_func post, void *env) {
 178   int i;
 179   ir_graph *irg, *rem;
 180
 181   rem = current_ir_graph;
 182
 183   for (i = 0; i < get_irp_n_irgs(); i++) {
 184     irg = get_irp_irg(i);
 185     current_ir_graph = irg;
 186     irg_walk(get_irg_end(irg), pre, post, env);
 187   }
 188   current_ir_graph = rem;
 189 }
 190
 191 /***************************************************************************/
 192
 193 /* Walks back from n until it finds a real cf op. */
 194 ir_node *get_cf_op(ir_node *n) {
 195   ir_node *pred;
 196
 197   n = skip_nop(n);
 198   n = skip_Tuple(n);
 199   pred = skip_Proj(n);
 200   if (!(is_cfop(pred) || is_fragile_op(pred) ||
 201         (get_irn_op(pred) == op_Bad)))
 202     n = get_cf_op(n);
 203
 204   return skip_Proj(n);
 205 }
 206
 207 void irg_block_walk_2(ir_node *node, irg_walk_func pre, irg_walk_func post, void *env)
 208 {
 209   int i;
 210
 211   assert(get_irn_opcode(node) == iro_Block);
 212
 213   if(get_Block_block_visited(node) < get_irg_block_visited(current_ir_graph)) {
 214     set_Block_block_visited(node, get_irg_block_visited(current_ir_graph));
 215
 216     if(pre)
 217       pre(node, env);
 218
 219     for(i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
 220
 221       /* find the corresponding predecessor block. */
 222       ir_node *pred = get_cf_op(get_Block_cfgpred(node, i));
 223       /* GL: I'm not sure whether this assert must go through.  There
 224          could be Id chains?? Tuple/Proj .... */
 225
 226       assert(is_cfop(pred)
 227                          || is_fragile_op(pred)
 228                          || (get_irn_op(pred) == op_Bad));
 229
 230       pred = get_nodes_Block(pred);
 231       if(get_irn_opcode(pred) == iro_Block) {
 232         /* recursion */
 233         irg_block_walk_2(pred, pre, post, env);
 234       }
 235       else {
 236                 assert(get_irn_opcode(pred) == iro_Bad);
 237       }
 238     }
 239
 240     if(post)
 241       post(node, env);
 242   }
 243   return;
 244 }
 245
 246
 247 /* walks only over Block nodes in the graph.  Has it's own visited
 248    flag, so that it can be interleaved with the other walker.         */
 249 void irg_block_walk(ir_node *node, irg_walk_func pre, irg_walk_func post, void *env)
 250 {
 251   ir_node *block, *pred;
 252   int i;
 253
 254   assert(node);
 255   assert(!interprocedural_view);   /* interprocedural_view not implemented, because it
 256                                     * interleaves with irg_walk */
 257   inc_irg_block_visited(current_ir_graph);
 258   if (is_no_Block(node)) block = get_nodes_Block(node); else block = node;
 259   assert(get_irn_opcode(block)  == iro_Block);
 260   irg_block_walk_2(block, pre, post, env);
 261   /* keepalive: the endless loops ... */
 262   if (get_irn_op(node) == op_End)
 263     for (i = 0; i < get_irn_arity(node); i++) {
 264       pred = get_irn_n(node, i);
 265       if (get_irn_op(pred) == op_Block)
 266         irg_block_walk_2(pred, pre, post, env);
 267     }
 268
 269   return;
 270 }
 271
 272
 273 void irg_block_walk_graph(ir_graph *irg, irg_walk_func pre, irg_walk_func post, void *env) {
 274   ir_graph * rem = current_ir_graph;
 275   current_ir_graph = irg;
 276   irg_block_walk(get_irg_end(irg), pre, post, env);
 277   current_ir_graph = rem;
 278 }
 279
 280
 281
 282 /********************************************************************/
 283 /** Walking support for interprocedural analysis                   **/
 284 /********************************************************************/
 285
 286 #define MIN_STACK_SIZE 40
 287
 288 typedef struct callsite_stack {
 289   int tos;
 290   ir_node **s;
 291 } callsite_stack;
 292
 293 /* Access the stack in the irg **************************************/
 294
 295 static INLINE void
 296 set_irg_callsite_stack(ir_graph *g, callsite_stack *s) {
 297   set_irg_link(g, s);
 298 }
 299
 300 static INLINE callsite_stack *
 301 get_irg_callsite_stack(ir_graph *g) {
 302   return (callsite_stack *) get_irg_link(g);
 303 }
 304
 305 /* A stack of callsites *********************************************/
 306
 307 /* @@@ eventually change the implementation so the new_ only sets the field
 308    to NULL, and the stack is only allocated if used.  Saves Memory! */
 309 static INLINE callsite_stack *
 310 new_callsite_stack(ir_graph *g) {
 311   callsite_stack *res = (callsite_stack *)malloc(sizeof(callsite_stack));
 312   res->tos = 0;
 313   res->s = NEW_ARR_F (ir_node *, MIN_STACK_SIZE);
 314   set_irg_callsite_stack(g, res);
 315 }
 316
 317 static INLINE void
 318 free_callsite_stack(ir_graph *g) {
 319   callsite_stack *s = get_irg_callsite_stack(g);
 320   DEL_ARR_F(s->s);
 321   free(s);
 322 }
 323
 324 static INLINE void
 325 push_callsite(ir_graph *callee, ir_node *callsite) {
 326   callsite_stack *s = get_irg_callsite_stack(callee);
 327   if (s->tos == ARR_LEN(s->s)) {
 328     int nlen = ARR_LEN (s->s) * 2;
 329     ARR_RESIZE (ir_node *, s->s, nlen);
 330   }
 331   s->s[s->tos] = callsite;
 332   s->tos++;
 333 }
 334
 335 static INLINE ir_node *
 336 get_top_of_callsite_stack(ir_graph *callee) {
 337   callsite_stack *s = get_irg_callsite_stack(callee);
 338   return (s->s[s->tos-1]);
 339 }
 340
 341 static INLINE
 342 ir_node * pop_callsite(ir_graph *callee) {
 343   callsite_stack *s = get_irg_callsite_stack(callee);
 344   s->tos--;
 345   return (s->s[s->tos]);
 346 }
 347
 348
 349 /* Initialization routines ******************************************/
 350
 351 void init_ip_walk () {
 352   int i;
 353   for (i = 0; i < get_irp_n_irgs(); i++)
 354     new_callsite_stack(get_irp_irg(i));
 355 }
 356
 357 void finish_ip_walk() {
 358   int i;
 359   for (i = 0; i < get_irp_n_irgs(); i++)
 360     free_callsite_stack(get_irp_irg(i));
 361   set_irg_link(get_irp_irg(i), NULL);
 362 }
 363
 364 /* walker routines **************************************************/
 365
 366 /* cf_pred is End* */
 367 static INLINE void
 368 enter_procedure(ir_node *block, ir_node *cf_pred, int pos) {
 369   ir_node *callbegin;
 370   ir_graph *irg = get_irn_irg(cf_pred);
 371
 372   assert(interprocedural_view);
 373
 374   interprocedural_view = 0;
 375   callbegin = skip_Proj(get_irn_n(block, 0));
 376   assert(get_irn_op(callbegin) == op_CallBegin);
 377   interprocedural_view = 1;
 378
 379   push_callsite(irg, callbegin);
 380   current_ir_graph = irg;
 381 }
 382
 383 /* cf_pred is CallBegin */
 384 static INLINE bool
 385 leave_procedure(ir_node *block, ir_node *cf_pred, int pos) {
 386   ir_node *tos = get_top_of_callsite_stack(current_ir_graph);
 387
 388   assert(get_irn_op(cf_pred) == op_CallBegin);
 389
 390   if (tos == cf_pred) {
 391     /* We entered this procedure by the call pred pos refers to. */
 392     pop_callsite(current_ir_graph);
 393     current_ir_graph = get_CallBegin_irg(cf_pred);
 394     return true;
 395   } else {
 396     /* We won't walk. */
 397     return false;
 398   }
 399 }
 400
 401 ir_node *get_irn_ip_pred(ir_node *n, int pos) {
 402
 403   if (interprocedural_view) {
 404
 405     /* Find the cf_pred refering to pos. */
 406     ir_node *block = n;
 407     ir_node *cf_pred;
 408     if (get_irn_opcode(n) == iro_Filter) block = get_nodes_Block(n);
 409     cf_pred = skip_Proj(get_irn_n(block, pos));
 410
 411     /* Check whether we enter or leave a procedure and act according. */
 412     if ((get_irn_op(cf_pred) == op_EndReg) ||
 413         (get_irn_op(cf_pred) == op_EndExcept))
 414       enter_procedure(block, cf_pred, pos);
 415     if (get_irn_op(cf_pred) == op_CallBegin)
 416       if (!leave_procedure(block, cf_pred, pos)) return NULL;
 417   }
 418
 419   return get_irn_n(n, pos);
 420 }
 421
 422 static INLINE void
 423 re_enter_procedure(ir_node *block, ir_node *cf_pred, int pos) {
 424   ir_node *callbegin = pop_callsite(current_ir_graph);
 425   assert(interprocedural_view);
 426   current_ir_graph = get_CallBegin_irg(callbegin);
 427 }
 428
 429 static INLINE void
 430 re_leave_procedure(ir_node *block, ir_node *cf_pred, int pos) {
 431   ir_node *proj;
 432   ir_graph *callee;
 433
 434   assert(get_irn_op(cf_pred) == op_CallBegin);
 435
 436   /* Find the irg block is in. */
 437   proj = get_Block_cg_cfgpred(block, pos);
 438   assert(is_Proj(proj));
 439   callee = get_entity_irg(get_Call_callee(get_CallBegin_call(cf_pred),
 440                                           get_Proj_proj(proj)));
 441   current_ir_graph = callee;
 442   push_callsite(callee, cf_pred);
 443 }
 444
 445 void
 446 return_recur(ir_node *n, int pos) {
 447   ir_node *block;
 448   ir_node *cf_pred;
 449
 450   if (!interprocedural_view) return;
 451
 452   /* Find the cf_pred refering to pos. */
 453   block = n;
 454   if (get_irn_opcode(n) == iro_Filter) block = get_nodes_Block(n);
 455   cf_pred = skip_Proj(get_irn_n(block, pos));
 456
 457   /* Check whether we re_enter or re_leave a procedure and act according. */
 458   if ((get_irn_op(cf_pred) == op_EndReg) ||
 459       (get_irn_op(cf_pred) == op_EndExcept))
 460     re_enter_procedure(block, cf_pred, pos);
 461   if (get_irn_op(cf_pred) == op_CallBegin)
 462     re_leave_procedure(block, cf_pred, pos);
 463 }