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