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