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 # include "irgwalk.h"
  21
  22 # include "eset.h"
  23
  24
  25 /* walk over an interprocedural graph (callgraph). Visits only graphs in irg_set. */
  26 static void irg_walk_cg(ir_node * node, int visited, eset * irg_set, irg_walk_func pre, irg_walk_func post, void * env) {
  27   int i;
  28   ir_graph * rem = current_ir_graph;
  29   ir_node * pred;
  30
  31   assert(node);
  32   if (get_irn_visited(node) >= visited) return;
  33
  34   set_irn_visited(node, visited);
  35
  36   pred = skip_Proj(node);
  37   if (get_irn_op(pred) == op_CallBegin
  38       || get_irn_op(pred) == op_EndReg
  39       || get_irn_op(pred) == op_EndExcept) {
  40     current_ir_graph = get_irn_irg(pred);
  41   }
  42
  43   if (pre) pre(node, env);
  44
  45   if (is_no_Block(node)) irg_walk_cg(get_nodes_Block(node), visited, irg_set, pre, post, env);
  46
  47   if (get_irn_op(node) == op_Block) { /* block */
  48     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
  49       ir_node * exec = get_irn_n(node, i);
  50       ir_node * pred = skip_Proj(exec);
  51       if ((get_irn_op(pred) != op_CallBegin
  52            && get_irn_op(pred) != op_EndReg
  53            && get_irn_op(pred) != op_EndExcept)
  54           || eset_contains(irg_set, get_irn_irg(pred))) {
  55         irg_walk_cg(exec, visited, irg_set, pre, post, env);
  56       }
  57     }
  58   } else if (get_irn_op(node) == op_Filter) {
  59     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
  60       ir_node * pred = get_irn_n(node, i);
  61       if (get_irn_op(pred) == op_Unknown || get_irn_op(pred) == op_Bad) {
  62         irg_walk_cg(pred, visited, irg_set, pre, post, env);
  63       } else {
  64         ir_node * exec;
  65         exec = skip_Proj(get_Block_cfgpred(get_nodes_Block(node), i));
  66         assert(get_irn_op(exec) == op_CallBegin
  67                || get_irn_op(exec) == op_EndReg
  68                || get_irn_op(exec) == op_EndExcept);
  69         if (eset_contains(irg_set, get_irn_irg(exec))) {
  70           current_ir_graph = get_irn_irg(exec);
  71           irg_walk_cg(pred, visited, irg_set, pre, post, env);
  72           current_ir_graph = rem;
  73         }
  74       }
  75     }
  76   } else {
  77     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
  78       irg_walk_cg(get_irn_n(node, i), visited, irg_set, pre, post, env);
  79     }
  80   }
  81
  82   if (post) post(node, env);
  83
  84   current_ir_graph = rem;
  85 }
  86
  87
  88 /* Insert all ir_graphs in irg_set, that are (transitive) reachable. */
  89 static void collect_irgs(ir_node * node, eset * irg_set) {
  90   if (get_irn_op(node) == op_Call) {
  91     int i;
  92     for (i = get_Call_n_callees(node) - 1; i >= 0; --i) {
  93       entity * ent = get_Call_callee(node, i);
  94       ir_graph * irg = ent ? get_entity_irg(ent) : NULL;
  95       if (irg && !eset_contains(irg_set, irg)) {
  96         eset_insert(irg_set, irg);
  97         irg_walk_graph(irg, (irg_walk_func) collect_irgs, NULL, irg_set);
  98       }
  99     }
 100   }
 101 }
 102
 103
 104 void irg_walk_2(ir_node *node, irg_walk_func pre, irg_walk_func post, void * env)
 105 {
 106   int i;
 107
 108
 109   assert(node);
 110   /*      printf(" - "); DDMSG2(node);  */
 111
 112   if (get_irn_visited(node) < get_irg_visited(current_ir_graph)) {
 113
 114 /*      printf(" -> "); DDMSG2(node);  */
 115     set_irn_visited(node, get_irg_visited(current_ir_graph));
 116
 117     if (pre) {
 118       pre(node, env);
 119     }
 120
 121     if (is_no_Block(node)) {
 122       irg_walk_2(get_nodes_Block(node), pre, post, env);
 123     }
 124     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 125       /* printf("   "); DDMSG2(node);
 126          printf("   "); DDMSG2(get_irn_n(node, i));  */
 127
 128       irg_walk_2(get_irn_n(node, i), pre, post, env);
 129     }
 130
 131 /*      printf(" <- "); DDMSG2(node);  */
 132     if (post)
 133       post(node, env);
 134   }
 135   return;
 136 }
 137
 138
 139 void irg_walk(ir_node *node, irg_walk_func pre, irg_walk_func post, void *env)
 140 {
 141   assert(node);
 142   if (interprocedural_view) {
 143     eset * irg_set = eset_create();
 144     int visited;
 145     ir_graph * irg;
 146     interprocedural_view = false;
 147     eset_insert(irg_set, current_ir_graph);
 148     irg_walk(node, (irg_walk_func) collect_irgs, NULL, irg_set);
 149     interprocedural_view = true;
 150     visited = get_max_irg_visited() + 1;
 151     irg_walk_cg(node, visited, irg_set, pre, post, env);
 152     for (irg = eset_first(irg_set); irg; irg = eset_next(irg_set)) {
 153       set_irg_visited(irg, visited);
 154     }
 155     eset_destroy(irg_set);
 156   } else {
 157     inc_irg_visited(current_ir_graph);
 158     irg_walk_2(node, pre, post, env);
 159   }
 160   return;
 161 }
 162
 163
 164 void irg_walk_graph(ir_graph *irg, irg_walk_func pre, irg_walk_func post, void *env) {
 165   ir_graph * rem = current_ir_graph;
 166   current_ir_graph = irg;
 167   irg_walk(get_irg_end(irg), pre, post, env);
 168   current_ir_graph = rem;
 169 }
 170
 171
 172 /***************************************************************************/
 173
 174 /* Executes irg_walk(end, pre, post, env) for all irgraphs in irprog.
 175    Sets current_ir_graph properly for each walk.  Conserves current
 176    current_ir_graph. */
 177 void all_irg_walk(irg_walk_func pre, irg_walk_func post, void *env) {
 178   int i;
 179   ir_graph *irg, *rem;
 180
 181   rem = current_ir_graph;
 182
 183   for (i = 0; i < get_irp_n_irgs(); i++) {
 184     irg = get_irp_irg(i);
 185     current_ir_graph = irg;
 186     irg_walk(get_irg_end(irg), pre, post, env);
 187   }
 188   current_ir_graph = rem;
 189 }
 190
 191 /***************************************************************************/
 192
 193 /* Walks back from n until it finds a real cf op. */
 194 ir_node *get_cf_op(ir_node *n) {
 195   ir_node *pred;
 196
 197   n = skip_nop(n);
 198   n = skip_Tuple(n);
 199   pred = skip_Proj(n);
 200   if (!(is_cfop(pred) || is_fragile_op(pred) ||
 201         (get_irn_op(pred) == op_Bad)))
 202     n = get_cf_op(n);
 203
 204   return skip_Proj(n);
 205 }
 206
 207 void irg_block_walk_2(ir_node *node, irg_walk_func pre, irg_walk_func post, void *env)
 208 {
 209   int i;
 210
 211   assert(get_irn_opcode(node) == iro_Block);
 212
 213   if(get_Block_block_visited(node) < get_irg_block_visited(current_ir_graph)) {
 214     set_Block_block_visited(node, get_irg_block_visited(current_ir_graph));
 215
 216     if(pre)
 217       pre(node, env);
 218
 219     for(i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
 220
 221       /* find the corresponding predecessor block. */
 222       ir_node *pred = get_cf_op(get_Block_cfgpred(node, i));
 223       /* GL: I'm not sure whether this assert must go through.  There
 224          could be Id chains?? Tuple/Proj .... */
 225
 226       assert(is_cfop(pred)
 227                          || is_fragile_op(pred)
 228                          || (get_irn_op(pred) == op_Bad));
 229
 230       pred = get_nodes_Block(pred);
 231       if(get_irn_opcode(pred) == iro_Block) {
 232         /* recursion */
 233         irg_block_walk_2(pred, pre, post, env);
 234       }
 235       else {
 236                 assert(get_irn_opcode(pred) == iro_Bad);
 237       }
 238     }
 239
 240     if(post)
 241       post(node, env);
 242   }
 243   return;
 244 }
 245
 246
 247 /* walks only over Block nodes in the graph.  Has it's own visited
 248    flag, so that it can be interleaved with the other walker.         */
 249 void irg_block_walk(ir_node *node, irg_walk_func pre, irg_walk_func post, void *env)
 250 {
 251   ir_node *block, *pred;
 252   int i;
 253
 254   assert(node);
 255   assert(!interprocedural_view);   /* interprocedural_view not implemented, because it
 256                                     * interleaves with irg_walk */
 257   inc_irg_block_visited(current_ir_graph);
 258   if (is_no_Block(node)) block = get_nodes_Block(node); else block = node;
 259   assert(get_irn_opcode(block)  == iro_Block);
 260   irg_block_walk_2(block, pre, post, env);
 261   /* keepalive: the endless loops ... */
 262   if (get_irn_op(node) == op_End)
 263     for (i = 0; i < get_irn_arity(node); i++) {
 264       pred = get_irn_n(node, i);
 265       if (get_irn_op(pred) == op_Block)
 266         irg_block_walk_2(pred, pre, post, env);
 267     }
 268
 269   return;
 270 }
 271
 272
 273 void irg_block_walk_graph(ir_graph *irg, irg_walk_func pre, irg_walk_func post, void *env) {
 274   ir_graph * rem = current_ir_graph;
 275   current_ir_graph = irg;
 276   irg_block_walk(get_irg_end(irg), pre, post, env);
 277   current_ir_graph = rem;
 278 }