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