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))
  49     irg_walk_cg(get_nodes_Block(node), visited, irg_set, pre, post, env);
  50
  51   if (get_irn_op(node) == op_Block) { /* block */
  52     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
  53       ir_node * exec = get_irn_n(node, i);
  54       ir_node * pred = skip_Proj(exec);
  55       if ((get_irn_op(pred) != op_CallBegin
  56            && get_irn_op(pred) != op_EndReg
  57            && get_irn_op(pred) != op_EndExcept)
  58           || eset_contains(irg_set, get_irn_irg(pred))) {
  59         irg_walk_cg(exec, visited, irg_set, pre, post, env);
  60       }
  61     }
  62   } else if (get_irn_op(node) == op_Filter) {
  63     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
  64       ir_node * pred = get_irn_n(node, i);
  65       if (get_irn_op(pred) == op_Unknown || get_irn_op(pred) == op_Bad) {
  66         irg_walk_cg(pred, visited, irg_set, pre, post, env);
  67       } else {
  68         ir_node * exec;
  69         exec = skip_Proj(get_Block_cfgpred(get_nodes_Block(node), i));
  70         assert(get_irn_op(exec) == op_CallBegin
  71                || get_irn_op(exec) == op_EndReg
  72                || get_irn_op(exec) == op_EndExcept);
  73         if (eset_contains(irg_set, get_irn_irg(exec))) {
  74           current_ir_graph = get_irn_irg(exec);
  75           irg_walk_cg(pred, visited, irg_set, pre, post, env);
  76           current_ir_graph = rem;
  77         }
  78       }
  79     }
  80   } else {
  81     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
  82       irg_walk_cg(get_irn_n(node, i), visited, irg_set, pre, post, env);
  83     }
  84   }
  85
  86   if (post) post(node, env);
  87
  88   current_ir_graph = rem;
  89 }
  90
  91
  92 /* Insert all ir_graphs in irg_set, that are (transitive) reachable. */
  93 static void collect_irgs(ir_node * node, eset * irg_set) {
  94   if (get_irn_op(node) == op_Call) {
  95     int i;
  96     for (i = get_Call_n_callees(node) - 1; i >= 0; --i) {
  97       entity * ent = get_Call_callee(node, i);
  98       ir_graph * irg = ent ? get_entity_irg(ent) : NULL;
  99       if (irg && !eset_contains(irg_set, irg)) {
 100         eset_insert(irg_set, irg);
 101         irg_walk_graph(irg, (irg_walk_func *) collect_irgs, NULL, irg_set);
 102       }
 103     }
 104   }
 105 }
 106
 107 static void
 108 irg_walk_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void * env)
 109 {
 110   int i;
 111   assert(node);
 112
 113   if (get_irn_visited(node) < get_irg_visited(current_ir_graph)) {
 114     set_irn_visited(node, get_irg_visited(current_ir_graph));
 115
 116     if (pre) pre(node, env);
 117
 118     if (is_no_Block(node))
 119       irg_walk_2(get_nodes_Block(node), pre, post, env);
 120     for (i = get_irn_arity(node) - 1; i >= 0; --i)
 121       irg_walk_2(get_irn_n(node, i), pre, post, env);
 122
 123     if (post) post(node, env);
 124   }
 125   return;
 126 }
 127
 128
 129 void irg_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
 130 {
 131   assert(node);
 132   if (interprocedural_view) {
 133     eset * irg_set = eset_create();
 134     int visited;
 135     ir_graph * irg;
 136     interprocedural_view = false;
 137     eset_insert(irg_set, current_ir_graph);
 138     irg_walk(node, (irg_walk_func *) collect_irgs, NULL, irg_set);
 139     interprocedural_view = true;
 140     visited = get_max_irg_visited() + 1;
 141     irg_walk_cg(node, visited, irg_set, pre, post, env);
 142     for (irg = eset_first(irg_set); irg; irg = eset_next(irg_set)) {
 143       set_irg_visited(irg, visited);
 144     }
 145     eset_destroy(irg_set);
 146   } else {
 147     inc_irg_visited(current_ir_graph);
 148     irg_walk_2(node, pre, post, env);
 149   }
 150   return;
 151 }
 152
 153
 154 void irg_walk_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env) {
 155   ir_graph * rem = current_ir_graph;
 156   current_ir_graph = irg;
 157   irg_walk(get_irg_end(irg), pre, post, env);
 158   current_ir_graph = rem;
 159 }
 160
 161 /* Executes irg_walk(end, pre, post, env) for all irgraphs in irprog.
 162    Sets current_ir_graph properly for each walk.  Conserves current
 163    current_ir_graph. */
 164 void all_irg_walk(irg_walk_func *pre, irg_walk_func *post, void *env) {
 165   int i;
 166   ir_graph *irg, *rem;
 167
 168   rem = current_ir_graph;
 169
 170   for (i = 0; i < get_irp_n_irgs(); i++) {
 171     irg = get_irp_irg(i);
 172     current_ir_graph = irg;
 173     irg_walk(get_irg_end(irg), pre, post, env);
 174   }
 175   current_ir_graph = rem;
 176 }
 177
 178 /***************************************************************************/
 179
 180 /* Returns current_ir_graph and sets it to the irg of predecessor index
 181    of node n. */
 182 static INLINE ir_graph *
 183 switch_irg (ir_node *n, int index) {
 184   ir_graph *old_current = current_ir_graph;
 185
 186   if (interprocedural_view) {
 187     /* Only Filter and Block nodes can have predecessors in other graphs. */
 188     if (get_irn_op(n) == op_Filter)
 189       n = get_nodes_Block(n);
 190     if (get_irn_op(n) == op_Block) {
 191       ir_node *cfop = skip_Proj(get_Block_cfgpred(n, index));
 192       if (is_ip_cfop(cfop)) {
 193         current_ir_graph = get_irn_irg(cfop);
 194       }
 195     }
 196   }
 197
 198   return old_current;
 199 }
 200
 201 static void
 202 cg_walk_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void * env)
 203 {
 204   int i;
 205   ir_graph *rem = NULL;
 206   assert(node);
 207
 208   if (get_irn_visited(node) < get_irg_visited(current_ir_graph)) {
 209     set_irn_visited(node, get_irg_visited(current_ir_graph));
 210
 211     if (pre) pre(node, env);
 212
 213     if (is_no_Block(node))
 214       cg_walk_2(get_nodes_Block(node), pre, post, env);
 215     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 216       rem = switch_irg(node, i);
 217       cg_walk_2(get_irn_n(node, i), pre, post, env);
 218       current_ir_graph = rem;
 219     }
 220
 221     if (post) post(node, env);
 222   }
 223   return;
 224 }
 225
 226
 227 /* Walks all irgs in interprocedural view.  Visits each node only once. */
 228 void cg_walk(irg_walk_func *pre, irg_walk_func *post, void *env) {
 229   int i;
 230   ir_graph *rem = current_ir_graph;
 231   int rem_view = interprocedural_view;
 232
 233   interprocedural_view = true;
 234
 235   inc_max_irg_visited();
 236   /* Fix all irg_visited flags */
 237   for (i = 0; i < get_irp_n_irgs(); i++)
 238     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
 239
 240   /* Walk starting at unreachable procedures. */
 241   for (i = 0; i < get_irp_n_irgs(); i++) {
 242     ir_node *sb;
 243     current_ir_graph = get_irp_irg(i);
 244
 245     sb = get_irg_start_block(current_ir_graph);
 246     if ((get_Block_n_cfgpreds(sb) > 1) ||
 247         (get_nodes_Block(get_Block_cfgpred(sb, 0)) != sb)) continue;
 248
 249     cg_walk_2(get_irg_end(current_ir_graph), pre, post, env);
 250   }
 251
 252   interprocedural_view = rem_view;
 253   current_ir_graph = rem;
 254 }
 255
 256
 257 /***************************************************************************/
 258
 259 /* Walks back from n until it finds a real cf op. */
 260 static ir_node *get_cf_op(ir_node *n) {
 261   ir_node *pred;
 262
 263   n = skip_nop(n);
 264   n = skip_Tuple(n);
 265   pred = skip_Proj(n);
 266   if (!(is_cfop(pred) || is_fragile_op(pred) ||
 267         (get_irn_op(pred) == op_Bad)))
 268     n = get_cf_op(n);
 269
 270   return skip_Proj(n);
 271 }
 272
 273 static void irg_block_walk_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
 274 {
 275   int i;
 276   assert(get_irn_opcode(node) == iro_Block);
 277
 278   if(get_Block_block_visited(node) < get_irg_block_visited(current_ir_graph)) {
 279     set_Block_block_visited(node, get_irg_block_visited(current_ir_graph));
 280
 281     if(pre) pre(node, env);
 282
 283     for(i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
 284       /* find the corresponding predecessor block. */
 285       ir_node *pred = get_cf_op(get_Block_cfgpred(node, i));
 286       pred = get_nodes_Block(pred);
 287       if(get_irn_opcode(pred) == iro_Block) {
 288         /* recursion */
 289         irg_block_walk_2(pred, pre, post, env);
 290       }
 291       else {
 292         assert(get_irn_opcode(pred) == iro_Bad);
 293       }
 294     }
 295
 296     if(post) post(node, env);
 297   }
 298   return;
 299 }
 300
 301
 302 /* walks only over Block nodes in the graph.  Has it's own visited
 303    flag, so that it can be interleaved with the other walker.         */
 304 void irg_block_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
 305 {
 306   ir_node *block, *pred;
 307   int i;
 308
 309   assert(node);
 310   assert(!interprocedural_view);   /* interprocedural_view not implemented, because it
 311                                     * interleaves with irg_walk */
 312   inc_irg_block_visited(current_ir_graph);
 313   if (is_no_Block(node)) block = get_nodes_Block(node); else block = node;
 314   assert(get_irn_opcode(block)  == iro_Block);
 315   irg_block_walk_2(block, pre, post, env);
 316   /* keepalive: the endless loops ... */
 317   if (get_irn_op(node) == op_End)
 318     for (i = 0; i < get_irn_arity(node); i++) {
 319       pred = get_irn_n(node, i);
 320       if (get_irn_op(pred) == op_Block)
 321         irg_block_walk_2(pred, pre, post, env);
 322     }
 323
 324   return;
 325 }
 326
 327
 328 void irg_block_walk_graph(ir_graph *irg, irg_walk_func *pre,
 329                           irg_walk_func *post, void *env) {
 330   ir_graph * rem = current_ir_graph;
 331   current_ir_graph = irg;
 332   irg_block_walk(get_irg_end(irg), pre, post, env);
 333   current_ir_graph = rem;
 334 }
 335
 336 /********************************************************************/
 337
 338 typedef struct walk_env {
 339   void *pre;
 340   void *post;
 341   void *env;
 342 } walk_env;
 343
 344 /* Walk to all constant expressions in this entity. */
 345 static void walk_entity(entity *ent, void *env) {
 346   walk_env *my_env = (walk_env *)env;
 347   if (get_entity_variability(ent) != uninitialized) {
 348     if (is_atomic_entity(ent)) {
 349       irg_walk(get_atomic_ent_value(ent), my_env->pre, my_env->post, my_env->env);
 350     } else {
 351       int i;
 352       for (i = 0; i < get_compound_ent_n_values(ent); i++) {
 353         irg_walk(get_compound_ent_value(ent, i), my_env->pre, my_env->post, my_env->env);
 354       }
 355     }
 356   }
 357 }
 358
 359 /* Walks over all code in const_code_irg. */
 360 void walk_const_code(irg_walk_func *pre, irg_walk_func *post, void *env) {
 361   int i, j;
 362   walk_env my_env;
 363
 364   ir_graph *rem = current_ir_graph;
 365   current_ir_graph = get_const_code_irg();
 366   inc_irg_visited(current_ir_graph);
 367
 368   my_env.pre = pre;
 369   my_env.post = post;
 370   my_env.env = env;
 371
 372   /* Walk all types that can contain constant entities.  */
 373   walk_types_entities(get_glob_type(), &walk_entity, &my_env);
 374   for (i = 0; i < get_irp_n_types(); i++)
 375     walk_types_entities(get_irp_type(i), &walk_entity, &my_env);
 376   for (i = 0; i < get_irp_n_irgs(); i++)
 377     walk_types_entities(get_irg_frame_type(get_irp_irg(i)), &walk_entity, &my_env);
 378
 379   /* Walk constant array bounds. */
 380   for (i = 0; i < get_irp_n_types(); i++) {
 381     type *tp = get_irp_type(i);
 382     if (is_array_type(tp)) {
 383       for (j = 0; j < get_array_n_dimensions(tp); j++) {
 384         ir_node *n;
 385         n = get_array_lower_bound(tp, j);
 386         if (n) irg_walk(n, pre, post, env);
 387         n = get_array_upper_bound(tp, j);
 388         if (n) irg_walk(n, pre, post, env);
 389       }
 390     }
 391   }
 392
 393   current_ir_graph = rem;
 394 }
 395
 396
 397 /********************************************************************/
 398 /** Walking support for interprocedural analysis                   **/
 399 /**                                                                **/
 400 /** @@@ Don't use, not operational yet, doesn't grok recursions!!  **/
 401 /** @@@ Header for irgwalk.h, here until it works. **/
 402 /**                                                                **/
 403 /** Interprocedural walking should not walk all predecessors of    **/
 404 /** all nodes.  When leaving a procedure the walker should only    **/
 405 /** follow the edge corresponding to the most recent entry of the  **/
 406 /** procedure.  The following functions use an internal stack to   **/
 407 /** remember the current call site of a procedure.                 **/
 408 /** They also set current_ir_graph correctly.                      **/
 409 /**                                                                **/
 410 /** Usage example:                                                 **/
 411 /**                                                                **/
 412 /** void init_ip_walk ();                                          **/
 413 /** work_on_graph(some_end_node);                                  **/
 414 /** void finish_ip_walk();                                         **/
 415 /**                                                                **/
 416 /** work_on_graph(ir_node *n) {                                    **/
 417 /**   for (i = 0; i < get_irn_arity(n); i++) {                     **/
 418 /**     if (...) continue;                                         **/
 419 /**     ir_node *m = get_irn_ip_pred(n, i);                        **/
 420 /**     if !m continue;                                            **/
 421 /**     work_on_graph(m);                                          **/
 422 /**     return_recur(n, i);                                        **/
 423 /**   }                                                            **/
 424 /** }                                                              **/
 425 /********************************************************************/
 426
 427 /* Call for i in {0|-1 ... get_irn_arity(n)}.
 428    If n is a conventional node returns the same node as get_irn_n(n, i).
 429    If the predecessors of n are in the callee of the procedure n belongs
 430    to, returns get_irn_n(n, i) if this node is in the callee on the top
 431    of the stack, else returns NULL.
 432    If the predecessors of n are in a procedure called by the procedure n
 433    belongs to pushes the caller on the caller stack in the callee.
 434    Sets current_ir_graph to the graph the node returned is in. */
 435 ir_node *get_irn_ip_pred(ir_node *n, int pos);
 436
 437 /* If get_irn_ip_pred() returned a node (not NULL) this must be
 438    called to clear up the stacks.
 439    Sets current_ir_graph to the graph n is in. */
 440 void return_recur(ir_node *n, int pos);
 441
 442
 443 /********************************************************************/
 444 /** Walking support for interprocedural analysis                   **/
 445 /********************************************************************/
 446
 447 #define MIN_STACK_SIZE 40
 448
 449 typedef struct callsite_stack {
 450   int tos;
 451   ir_node **s;
 452 } callsite_stack;
 453
 454 /* Access the stack in the irg **************************************/
 455
 456 static INLINE void
 457 set_irg_callsite_stack(ir_graph *g, callsite_stack *s) {
 458   set_irg_link(g, s);
 459 }
 460
 461 static INLINE callsite_stack *
 462 get_irg_callsite_stack(ir_graph *g) {
 463   return (callsite_stack *) get_irg_link(g);
 464 }
 465
 466 /* A stack of callsites *********************************************/
 467
 468 /* @@@ eventually change the implementation so the new_ only sets the field
 469    to NULL, and the stack is only allocated if used.  Saves Memory! */
 470 static INLINE callsite_stack *
 471 new_callsite_stack(ir_graph *g) {
 472   callsite_stack *res = (callsite_stack *)malloc(sizeof(callsite_stack));
 473   res->tos = 0;
 474   res->s = NEW_ARR_F (ir_node *, MIN_STACK_SIZE);
 475   set_irg_callsite_stack(g, res);
 476   return(res);
 477 }
 478
 479 static INLINE void
 480 free_callsite_stack(ir_graph *g) {
 481   callsite_stack *s = get_irg_callsite_stack(g);
 482   DEL_ARR_F(s->s);
 483   free(s);
 484 }
 485
 486 static INLINE void
 487 push_callsite(ir_graph *callee, ir_node *callsite) {
 488   callsite_stack *s = get_irg_callsite_stack(callee);
 489   if (s->tos == ARR_LEN(s->s)) {
 490     int nlen = ARR_LEN (s->s) * 2;
 491     ARR_RESIZE (ir_node *, s->s, nlen);
 492   }
 493   s->s[s->tos] = callsite;
 494   s->tos++;
 495 }
 496
 497 static INLINE ir_node *
 498 get_top_of_callsite_stack(ir_graph *callee) {
 499   callsite_stack *s = get_irg_callsite_stack(callee);
 500   return (s->s[s->tos-1]);
 501 }
 502
 503 static INLINE
 504 ir_node * pop_callsite(ir_graph *callee) {
 505   callsite_stack *s = get_irg_callsite_stack(callee);
 506   s->tos--;
 507   return (s->s[s->tos]);
 508 }
 509
 510
 511 /* Initialization routines ******************************************/
 512
 513 void init_ip_walk (void) {
 514   int i;
 515   for (i = 0; i < get_irp_n_irgs(); i++)
 516     new_callsite_stack(get_irp_irg(i));
 517 }
 518
 519 void finish_ip_walk(void) {
 520   int i;
 521   for (i = 0; i < get_irp_n_irgs(); i++)
 522     free_callsite_stack(get_irp_irg(i));
 523   set_irg_link(get_irp_irg(i), NULL);
 524 }
 525
 526 /* walker routines **************************************************/
 527
 528 /* cf_pred is End* */
 529 static INLINE void
 530 enter_procedure(ir_node *block, ir_node *cf_pred, int pos) {
 531   ir_node *callbegin;
 532   ir_graph *irg = get_irn_irg(cf_pred);
 533
 534   assert(interprocedural_view);
 535
 536   interprocedural_view = 0;
 537   callbegin = skip_Proj(get_irn_n(block, 0));
 538   assert(get_irn_op(callbegin) == op_CallBegin);
 539   interprocedural_view = 1;
 540
 541   push_callsite(irg, callbegin);
 542   current_ir_graph = irg;
 543 }
 544
 545 /* cf_pred is CallBegin */
 546 static INLINE bool
 547 leave_procedure(ir_node *block, ir_node *cf_pred, int pos) {
 548   ir_node *tos = get_top_of_callsite_stack(current_ir_graph);
 549
 550   assert(get_irn_op(cf_pred) == op_CallBegin);
 551
 552   if (tos == cf_pred) {
 553     /* We entered this procedure by the call pred pos refers to. */
 554     pop_callsite(current_ir_graph);
 555     current_ir_graph = get_CallBegin_irg(cf_pred);
 556     return true;
 557   } else {
 558     /* We won't walk. */
 559     return false;
 560   }
 561 }
 562
 563 ir_node *get_irn_ip_pred(ir_node *n, int pos) {
 564
 565   if (interprocedural_view) {
 566
 567     /* Find the cf_pred refering to pos. */
 568     ir_node *block = n;
 569     ir_node *cf_pred;
 570     if (get_irn_opcode(n) == iro_Filter) block = get_nodes_Block(n);
 571     cf_pred = skip_Proj(get_irn_n(block, pos));
 572
 573     /* Check whether we enter or leave a procedure and act according. */
 574     if ((get_irn_op(cf_pred) == op_EndReg) ||
 575         (get_irn_op(cf_pred) == op_EndExcept))
 576       enter_procedure(block, cf_pred, pos);
 577     if (get_irn_op(cf_pred) == op_CallBegin)
 578       if (!leave_procedure(block, cf_pred, pos)) return NULL;
 579   }
 580
 581   return get_irn_n(n, pos);
 582 }
 583
 584 static INLINE void
 585 re_enter_procedure(ir_node *block, ir_node *cf_pred, int pos) {
 586   ir_node *callbegin = pop_callsite(current_ir_graph);
 587   assert(interprocedural_view);
 588   current_ir_graph = get_CallBegin_irg(callbegin);
 589 }
 590
 591 static INLINE void
 592 re_leave_procedure(ir_node *block, ir_node *cf_pred, int pos) {
 593   ir_node *proj;
 594   ir_graph *callee;
 595
 596   assert(get_irn_op(cf_pred) == op_CallBegin);
 597
 598   /* Find the irg block is in. */
 599   proj = get_Block_cg_cfgpred(block, pos);
 600   assert(is_Proj(proj));
 601   callee = get_entity_irg(get_Call_callee(get_CallBegin_call(cf_pred),
 602                                           get_Proj_proj(proj)));
 603   current_ir_graph = callee;
 604   push_callsite(callee, cf_pred);
 605 }
 606
 607 void
 608 return_recur(ir_node *n, int pos) {
 609   ir_node *block;
 610   ir_node *cf_pred;
 611
 612   if (!interprocedural_view) return;
 613
 614   /* Find the cf_pred refering to pos. */
 615   block = n;
 616   if (get_irn_opcode(n) == iro_Filter) block = get_nodes_Block(n);
 617   cf_pred = skip_Proj(get_irn_n(block, pos));
 618
 619   /* Check whether we re_enter or re_leave a procedure and act according. */
 620   if ((get_irn_op(cf_pred) == op_EndReg) ||
 621       (get_irn_op(cf_pred) == op_EndExcept))
 622     re_enter_procedure(block, cf_pred, pos);
 623   if (get_irn_op(cf_pred) == op_CallBegin)
 624     re_leave_procedure(block, cf_pred, pos);
 625 }