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 "irnode.h"
  18 # include "irgraph.h" /* visited flag */
  19 # include "irprog.h"
  20
  21 void irg_walk_2(ir_node *node,
  22               void (pre)(ir_node*, void*), void (post)(ir_node*, void*),
  23               void *env)
  24 {
  25   int i;
  26
  27
  28   assert(node);
  29   /*      printf(" - "); DDMSG2(node);  */
  30
  31   if (get_irn_visited(node) < get_irg_visited(current_ir_graph)) {
  32
  33 /*      printf(" -> "); DDMSG2(node);  */
  34     set_irn_visited(node, get_irg_visited(current_ir_graph));
  35
  36     if (pre) {
  37       pre(node, env);
  38     }
  39
  40     if (is_no_Block(node)) {
  41       irg_walk_2(get_nodes_Block(node), pre, post, env);
  42     }
  43     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
  44       /* printf("   "); DDMSG2(node);
  45          printf("   "); DDMSG2(get_irn_n(node, i));  */
  46
  47       irg_walk_2(get_irn_n(node, i), pre, post, env);
  48     }
  49
  50 /*      printf(" <- "); DDMSG2(node);  */
  51     if (post)
  52       post(node, env);
  53   }
  54   return;
  55 }
  56
  57
  58 void irg_walk(ir_node *node,
  59               void (pre)(ir_node*, void*), void (post)(ir_node*, void*),
  60               void *env)
  61 {
  62   assert(node);
  63   inc_irg_visited (current_ir_graph);
  64   irg_walk_2(node, pre, post, env);
  65   return;
  66 }
  67
  68 /***************************************************************************/
  69
  70 /* Executes irg_walk(end, pre, post, env) for all irgraphs in irprog.
  71    Sets current_ir_graph properly for each walk.  Conserves current
  72    current_ir_graph. */
  73 void all_irg_walk(void (pre)(ir_node*, void*), void (post)(ir_node*, void*),
  74                   void *env) {
  75   int i;
  76   ir_graph *irg, *rem;
  77
  78   rem = current_ir_graph;
  79
  80   for (i = 0; i < get_irp_n_irgs(); i++) {
  81     irg = get_irp_irg(i);
  82     current_ir_graph = irg;
  83     irg_walk(get_irg_end(irg), pre, post, env);
  84   }
  85   current_ir_graph = rem;
  86 }
  87
  88 /***************************************************************************/
  89
  90 /* Walks back from n until it finds a real cf op. */
  91 ir_node *get_cf_op(ir_node *n) {
  92   ir_node *pred;
  93
  94   n = skip_nop(n);
  95   n = skip_Tuple(n);
  96   pred = skip_Proj(n);
  97   if (!(is_cfop(pred) || is_fragile_op(pred) ||
  98         (get_irn_op(pred) == op_Bad)))
  99     n = get_cf_op(n);
 100
 101   return skip_Proj(n);
 102 }
 103
 104 void irg_block_walk_2(ir_node *node, void (pre)(ir_node*, void*),
 105                                           void (post)(ir_node*, void*), void *env)
 106 {
 107   int i;
 108
 109   assert(get_irn_opcode(node) == iro_Block);
 110
 111   if(get_Block_block_visited(node) < get_irg_block_visited(current_ir_graph)) {
 112     set_Block_block_visited(node, get_irg_block_visited(current_ir_graph));
 113
 114     if(pre)
 115       pre(node, env);
 116
 117     for(i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
 118
 119       /* find the corresponding predecessor block. */
 120       ir_node *pred = get_cf_op(get_Block_cfgpred(node, i));
 121       /* GL: I'm not sure whether this assert must go through.  There
 122          could be Id chains?? Tuple/Proj .... */
 123
 124       assert(is_cfop(pred)
 125                          || is_fragile_op(pred)
 126                          || (get_irn_op(pred) == op_Bad));
 127
 128       pred = get_nodes_Block(pred);
 129       if(get_irn_opcode(pred) == iro_Block) {
 130                 /* recursion */
 131                 irg_block_walk_2(pred, pre, post, env);
 132       }
 133       else {
 134                 assert(get_irn_opcode(pred) == iro_Bad);
 135       }
 136     }
 137
 138     if(post)
 139       post(node, env);
 140   }
 141   return;
 142 }
 143
 144
 145 /* walks only over Block nodes in the graph.  Has it's own visited
 146    flag, so that it can be interleaved with the other walker.         */
 147 void irg_block_walk(ir_node *node,
 148                     void (pre)(ir_node*, void*), void (post)(ir_node*, void*),
 149                     void *env)
 150 {
 151   ir_node *block, *pred;
 152   int i;
 153
 154   assert(node);
 155   inc_irg_block_visited(current_ir_graph);
 156   if (is_no_Block(node)) block = get_nodes_Block(node); else block = node;
 157   assert(get_irn_opcode(block)  == iro_Block);
 158   irg_block_walk_2(block, pre, post, env);
 159   /* keepalive: the endless loops ... */
 160   if (get_irn_op(node) == op_End)
 161     for (i = 0; i < get_irn_arity(node); i++) {
 162       pred = get_irn_n(node, i);
 163       if (get_irn_op(pred) == op_Block)
 164         irg_block_walk_2(pred, pre, post, env);
 165     }
 166
 167   return;
 168 }