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 <stdlib.h>
  18
  19 # include "irnode.h"
  20 # include "irgraph.h" /* visited flag */
  21 # include "irprog.h"
  22 # include "irgwalk.h"
  23
  24 # include "eset.h"
  25 # include "array.h"
  26
  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) {
  29   int i;
  30   ir_graph * rem = current_ir_graph;
  31   ir_node * pred;
  32
  33   assert(node);
  34   if (get_irn_visited(node) >= visited) return;
  35
  36   set_irn_visited(node, visited);
  37
  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);
  43   }
  44
  45   if (pre) pre(node, env);
  46
  47   if (is_no_Block(node)) irg_walk_cg(get_nodes_Block(node), visited, irg_set, pre, post, env);
  48
  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);
  58       }
  59     }
  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);
  65       } else {
  66         ir_node * exec;
  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;
  75         }
  76       }
  77     }
  78   } else {
  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);
  81     }
  82   }
  83
  84   if (post) post(node, env);
  85
  86   current_ir_graph = rem;
  87 }
  88
  89
  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) {
  93     int i;
  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);
 100       }
 101     }
 102   }
 103 }
 104
 105
 106 void irg_walk_2(ir_node *node, irg_walk_func pre, irg_walk_func post, void * env)
 107 {
 108   int i;
 109
 110
 111   assert(node);
 112   /*      printf(" - "); DDMSG2(node);  */
 113
 114   if (get_irn_visited(node) < get_irg_visited(current_ir_graph)) {
 115
 116 /*      printf(" -> "); DDMSG2(node);  */
 117     set_irn_visited(node, get_irg_visited(current_ir_graph));
 118
 119     if (pre) {
 120       pre(node, env);
 121     }
 122
 123     if (is_no_Block(node)) {
 124       irg_walk_2(get_nodes_Block(node), pre, post, env);
 125     }
 126     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 127       /* printf("   "); DDMSG2(node);
 128          printf("   "); DDMSG2(get_irn_n(node, i));  */
 129
 130       irg_walk_2(get_irn_n(node, i), pre, post, env);
 131     }
 132
 133 /*      printf(" <- "); DDMSG2(node);  */
 134     if (post)
 135       post(node, env);
 136   }
 137   return;
 138 }
 139
 140
 141 void irg_walk(ir_node *node, irg_walk_func pre, irg_walk_func post, void *env)
 142 {
 143   assert(node);
 144   if (interprocedural_view) {
 145     eset * irg_set = eset_create();
 146     int visited;
 147     ir_graph * irg;
 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);
 156     }
 157     eset_destroy(irg_set);
 158   } else {
 159     inc_irg_visited(current_ir_graph);
 160     irg_walk_2(node, pre, post, env);
 161   }
 162   return;
 163 }
 164
 165
 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;
 171 }
 172
 173
 174 /***************************************************************************/
 175
 176 /* Executes irg_walk(end, pre, post, env) for all irgraphs in irprog.
 177    Sets current_ir_graph properly for each walk.  Conserves current
 178    current_ir_graph. */
 179 void all_irg_walk(irg_walk_func pre, irg_walk_func post, void *env) {
 180   int i;
 181   ir_graph *irg, *rem;
 182
 183   rem = current_ir_graph;
 184
 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);
 189   }
 190   current_ir_graph = rem;
 191 }
 192
 193 /***************************************************************************/
 194
 195 /* Walks back from n until it finds a real cf op. */
 196 ir_node *get_cf_op(ir_node *n) {
 197   ir_node *pred;
 198
 199   n = skip_nop(n);
 200   n = skip_Tuple(n);
 201   pred = skip_Proj(n);
 202   if (!(is_cfop(pred) || is_fragile_op(pred) ||
 203         (get_irn_op(pred) == op_Bad)))
 204     n = get_cf_op(n);
 205
 206   return skip_Proj(n);
 207 }
 208
 209 void irg_block_walk_2(ir_node *node, irg_walk_func pre, irg_walk_func post, void *env)
 210 {
 211   int i;
 212
 213   assert(get_irn_opcode(node) == iro_Block);
 214
 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));
 217
 218     if(pre)
 219       pre(node, env);
 220
 221     for(i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
 222
 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 .... */
 227
 228       assert(is_cfop(pred)
 229                          || is_fragile_op(pred)
 230                          || (get_irn_op(pred) == op_Bad));
 231
 232       pred = get_nodes_Block(pred);
 233       if(get_irn_opcode(pred) == iro_Block) {
 234         /* recursion */
 235         irg_block_walk_2(pred, pre, post, env);
 236       }
 237       else {
 238                 assert(get_irn_opcode(pred) == iro_Bad);
 239       }
 240     }
 241
 242     if(post)
 243       post(node, env);
 244   }
 245   return;
 246 }
 247
 248
 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)
 252 {
 253   ir_node *block, *pred;
 254   int i;
 255
 256   assert(node);
 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);
 269     }
 270
 271   return;
 272 }
 273
 274
 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;
 280 }
 281
 282
 283
 284 /********************************************************************/
 285 /** Walking support for interprocedural analysis                   **/
 286 /********************************************************************/
 287
 288 #define MIN_STACK_SIZE 40
 289
 290 typedef struct callsite_stack {
 291   int tos;
 292   ir_node **s;
 293 } callsite_stack;
 294
 295 /* Access the stack in the irg **************************************/
 296
 297 static INLINE void
 298 set_irg_callsite_stack(ir_graph *g, callsite_stack *s) {
 299   set_irg_link(g, s);
 300 }
 301
 302 static INLINE callsite_stack *
 303 get_irg_callsite_stack(ir_graph *g) {
 304   return (callsite_stack *) get_irg_link(g);
 305 }
 306
 307 /* A stack of callsites *********************************************/
 308
 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));
 314   res->tos = 0;
 315   res->s = NEW_ARR_F (ir_node *, MIN_STACK_SIZE);
 316   set_irg_callsite_stack(g, res);
 317   return(res);
 318 }
 319
 320 static INLINE void
 321 free_callsite_stack(ir_graph *g) {
 322   callsite_stack *s = get_irg_callsite_stack(g);
 323   DEL_ARR_F(s->s);
 324   free(s);
 325 }
 326
 327 static INLINE void
 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);
 333   }
 334   s->s[s->tos] = callsite;
 335   s->tos++;
 336 }
 337
 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]);
 342 }
 343
 344 static INLINE
 345 ir_node * pop_callsite(ir_graph *callee) {
 346   callsite_stack *s = get_irg_callsite_stack(callee);
 347   s->tos--;
 348   return (s->s[s->tos]);
 349 }
 350
 351
 352 /* Initialization routines ******************************************/
 353
 354 void init_ip_walk () {
 355   int i;
 356   for (i = 0; i < get_irp_n_irgs(); i++)
 357     new_callsite_stack(get_irp_irg(i));
 358 }
 359
 360 void finish_ip_walk() {
 361   int i;
 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);
 365 }
 366
 367 /* walker routines **************************************************/
 368
 369 /* cf_pred is End* */
 370 static INLINE void
 371 enter_procedure(ir_node *block, ir_node *cf_pred, int pos) {
 372   ir_node *callbegin;
 373   ir_graph *irg = get_irn_irg(cf_pred);
 374
 375   assert(interprocedural_view);
 376
 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;
 381
 382   push_callsite(irg, callbegin);
 383   current_ir_graph = irg;
 384 }
 385
 386 /* cf_pred is CallBegin */
 387 static INLINE bool
 388 leave_procedure(ir_node *block, ir_node *cf_pred, int pos) {
 389   ir_node *tos = get_top_of_callsite_stack(current_ir_graph);
 390
 391   assert(get_irn_op(cf_pred) == op_CallBegin);
 392
 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);
 397     return true;
 398   } else {
 399     /* We won't walk. */
 400     return false;
 401   }
 402 }
 403
 404 ir_node *get_irn_ip_pred(ir_node *n, int pos) {
 405
 406   if (interprocedural_view) {
 407
 408     /* Find the cf_pred refering to pos. */
 409     ir_node *block = n;
 410     ir_node *cf_pred;
 411     if (get_irn_opcode(n) == iro_Filter) block = get_nodes_Block(n);
 412     cf_pred = skip_Proj(get_irn_n(block, pos));
 413
 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;
 420   }
 421
 422   return get_irn_n(n, pos);
 423 }
 424
 425 static INLINE void
 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);
 430 }
 431
 432 static INLINE void
 433 re_leave_procedure(ir_node *block, ir_node *cf_pred, int pos) {
 434   ir_node *proj;
 435   ir_graph *callee;
 436
 437   assert(get_irn_op(cf_pred) == op_CallBegin);
 438
 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);
 446 }
 447
 448 void
 449 return_recur(ir_node *n, int pos) {
 450   ir_node *block;
 451   ir_node *cf_pred;
 452
 453   if (!interprocedural_view) return;
 454
 455   /* Find the cf_pred refering to pos. */
 456   block = n;
 457   if (get_irn_opcode(n) == iro_Filter) block = get_nodes_Block(n);
 458   cf_pred = skip_Proj(get_irn_n(block, pos));
 459
 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);
 466 }