nsz Git - libfirm/blob - ir/ana/irouts.c

   1  /* Copyright (C) 2002 by Universitaet Karlsruhe
   2 ** All rights reserved.
   3 **
   4 ** Authors:  Goetz Lindenmaier
   5 **
   6 ** irouts.c --- Compute out edges for ir nodes (also called def-use
   7 ** edges).
   8 **
   9 */
  10
  11 /* $Id$ */
  12
  13 #include "irouts.h"
  14 #include "irnode_t.h"
  15 #include "irgraph_t.h"     /* To access irg->outs field (which is private to this module)
  16                               without public access routine */
  17
  18 /**********************************************************************/
  19 /** Accessing the out datastructures                                 **/
  20 /**********************************************************************/
  21
  22 /* returns the number of successors of the node: */
  23 inline int get_irn_n_outs    (ir_node *node) {
  24   return (int)(node->out[0]);
  25 }
  26
  27 /* Access successor n */
  28 inline ir_node *get_irn_out      (ir_node *node, int pos) {
  29   assert(node);
  30   assert(pos >= 0 && pos < get_irn_n_outs(node));
  31   return node->out[pos+1];
  32 }
  33
  34 inline void set_irn_out      (ir_node *node, int pos, ir_node *out) {
  35   assert(node && out);
  36   assert(pos >= 0 && pos < get_irn_n_outs(node));
  37   node->out[pos+1] = out;
  38 }
  39
  40
  41 inline int get_Block_n_cfg_outs (ir_node *bl) {
  42   int i, n_cfg_outs = 0;
  43   assert(bl && (get_irn_op(bl) == op_Block));
  44   for (i = 0; i < (int)bl->out[0]; i++)
  45     if ((get_irn_mode(bl->out[i+1]) == mode_X) &&
  46         (get_irn_op(bl->out[i+1]) != op_End)) n_cfg_outs++;
  47   return n_cfg_outs;
  48 }
  49
  50
  51 inline ir_node *get_Block_cfg_out  (ir_node *bl, int pos) {
  52   int i, out_pos = 0;
  53   assert(bl && (get_irn_op(bl) == op_Block));
  54   for (i = 0; i < (int)bl->out[0]; i++)
  55     if ((get_irn_mode(bl->out[i+1]) == mode_X)  &&
  56         (get_irn_op(bl->out[i+1]) != op_End)) {
  57       if (out_pos == pos) {
  58         ir_node *cfop = bl->out[i+1];
  59         return cfop->out[0+1];
  60       } else {
  61         out_pos++;
  62       }
  63     }
  64   return NULL;
  65 }
  66
  67 void irg_out_walk_2(ir_node *node,  void (pre)(ir_node*, void*),
  68                     void (post)(ir_node*, void*), void *env) {
  69   int i;
  70   ir_node *succ;
  71
  72   //printf("++ in walker (%d outs) ", get_irn_n_outs(node)); DDMSG2(node);
  73
  74   assert(node);
  75   assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
  76
  77   set_irn_visited(node, get_irg_visited(current_ir_graph));
  78
  79   if (pre) pre(node, env);
  80
  81   for (i = 0; i < get_irn_n_outs(node); i++) {
  82     succ = get_irn_out(node, i);
  83     if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
  84       irg_out_walk_2(succ, pre, post, env);
  85   }
  86
  87   if (post) post(node, env);
  88
  89   //printf("++ done walking "); DDMSG2(node);
  90   return;
  91 }
  92
  93 void irg_out_walk(ir_node *node,
  94                   void (pre)(ir_node*, void*), void (post)(ir_node*, void*),
  95                   void *env) {
  96   assert(node);
  97   if (get_irg_outs_state(current_ir_graph) != no_outs) {
  98     inc_irg_visited (current_ir_graph);
  99     irg_out_walk_2(node, pre, post, env);
 100   }
 101   return;
 102 }
 103
 104 void irg_out_block_walk2(ir_node *bl,
 105                         void (pre)(ir_node*, void*), void (post)(ir_node*, void*),
 106                         void *env) {
 107   int i;
 108
 109   assert(get_irn_opcode(bl) == iro_Block);
 110
 111   if(get_Block_block_visited(bl) < get_irg_block_visited(current_ir_graph)) {
 112     set_Block_block_visited(bl, get_irg_block_visited(current_ir_graph));
 113
 114     if(pre)
 115       pre(bl, env);
 116
 117     for(i = 0; i < get_Block_n_cfg_outs(bl); i++) {
 118       /* find the corresponding predecessor block. */
 119       ir_node *pred = get_Block_cfg_out(bl, i);
 120       assert(get_irn_opcode(pred) == iro_Block);
 121       /* recursion */
 122       irg_out_block_walk2(pred, pre, post, env);
 123     }
 124
 125     if(post)
 126       post(bl, env);
 127   }
 128   return;
 129 }
 130
 131 /* Walks only over Block nodes in the graph.  Has it's own visited
 132    flag, so that it can be interleaved with the other walker.         */
 133 void irg_out_block_walk(ir_node *node,
 134                         void (pre)(ir_node*, void*), void (post)(ir_node*, void*),
 135                         void *env) {
 136
 137   assert((get_irn_op(node) == op_Block) || (get_irn_mode(node) == mode_X));
 138
 139   inc_irg_block_visited(current_ir_graph);
 140
 141   if (get_irn_mode(node) == mode_X) node = node->out[1];
 142   assert(get_irn_opcode(node)  == iro_Block);
 143
 144   irg_out_block_walk2(node, pre, post, env);
 145
 146   return;
 147
 148 }
 149
 150 /**********************************************************************/
 151 /** Building and Removing the out datasturcture                      **/
 152 /**                                                                  **/
 153 /** The outs of a graph are allocated in a single, large array.      **/
 154 /** This allows to allocate and deallocate the memory for the outs   **/
 155 /** on demand.  The large array is separated into many small ones    **/
 156 /** for each node.  Only a single field to reference the out array   **/
 157 /** is stored in each node and a field referencing the large out     **/
 158 /** array in irgraph.  The 0 field of each out array contains the    **/
 159 /** size of this array.  This saves memory in the irnodes themselves.**/
 160 /** The construction does two passes over the graph.  The first pass **/
 161 /** counts the overall number of outs and the outs of each node.  It **/
 162 /** stores the outs of each node in the out reference of the node.   **/
 163 /** Then the large array is allocated.  The second iteration chops   **/
 164 /** the large array into smaller parts, sets the out edges and       **/
 165 /** recounts the out edges.                                          **/
 166 /**********************************************************************/
 167
 168
 169 /* Returns the amount of out edges for not yet visited successors. */
 170 int count_outs(ir_node *n) {
 171   int start, i, res;
 172   ir_node *succ;
 173
 174   set_irn_visited(n, get_irg_visited(current_ir_graph));
 175   n->out = (ir_node **) 1;     /* Space for array size. */
 176
 177   if ((get_irn_op(n) == op_Block)) start = 0; else start = -1;
 178   res = get_irn_arity(n) - start +1;  /* --1 or --0; 1 for array size. */
 179   for (i = start; i < get_irn_arity(n); i++) {
 180     /* Optimize Tuples.  They annoy if walking the cfg. */
 181     succ = skip_Tuple(get_irn_n(n, i));
 182     set_irn_n(n, i, succ);
 183     /* count outs for successors */
 184     if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
 185       res += count_outs(succ);
 186     /* Count my outs */
 187     succ->out = (ir_node **)( (int)succ->out +1);
 188   }
 189   return res;
 190 }
 191
 192 ir_node **set_out_edges(ir_node *n, ir_node **free) {
 193   int n_outs, start, i;
 194   ir_node *succ;
 195
 196   set_irn_visited(n, get_irg_visited(current_ir_graph));
 197
 198   /* Allocate my array */
 199   n_outs = (int) n->out;
 200   n->out = free;
 201   free = &free[n_outs];
 202   /* We count the successors again, the space will be sufficient.
 203      We use this counter to remember the position for the next back
 204      edge. */
 205   n->out[0] = (ir_node *)0;
 206
 207   if (get_irn_op(n) == op_Block) start = 0; else start = -1;
 208   for (i = start; i < get_irn_arity(n); i++) {
 209     succ = get_irn_n(n, i);
 210     /* Recursion */
 211     if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
 212       free = set_out_edges(succ, free);
 213     /* Remember our back edge */
 214     succ->out[get_irn_n_outs(succ)+1] = n;
 215     succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
 216   }
 217   return free;
 218 }
 219
 220 inline void fix_start_proj(ir_graph *irg) {
 221   ir_node *proj = NULL, *startbl;
 222   int i;
 223   if (get_Block_n_cfg_outs(get_irg_start_block(irg))) {
 224     startbl = get_irg_start_block(irg);
 225     for (i = 0; i < get_irn_n_outs(startbl); i++)
 226       if (get_irn_mode(get_irn_out(startbl, i)) == mode_X)
 227         proj = get_irn_out(startbl, i);
 228     if (get_irn_out(proj, 0) == startbl) {
 229       assert(get_irn_n_outs(proj) == 2);
 230       set_irn_out(proj, 0, get_irn_out(proj, 1));
 231       set_irn_out(proj, 1, startbl);
 232     }
 233   }
 234 }
 235
 236 void compute_outs(ir_graph *irg) {
 237   ir_graph *rem = current_ir_graph;
 238   int n_out_edges = 0;
 239
 240   current_ir_graph = irg;
 241
 242   /* Update graph state */
 243   assert(get_irg_phase_state(current_ir_graph) != phase_building);
 244   current_ir_graph->outs_state = outs_consistent;
 245
 246   /* This first iteration counts the overall number of out edges and the
 247      number of out edges for each node. */
 248   inc_irg_visited(irg);
 249   n_out_edges = count_outs(get_irg_end(irg));
 250
 251   /* allocate memory for all out edges. */
 252   irg->outs = (ir_node **) malloc (n_out_edges * sizeof(ir_node *));
 253
 254   /* The second iteration splits the irg->outs array into smaller arrays
 255      for each node and writes the back edges into this array. */
 256   inc_irg_visited(irg);
 257   set_out_edges(get_irg_end(irg), irg->outs);
 258
 259   /* We want that the out of ProjX from Start contains the next block at
 260      position 1, the Start block at position 2.  This is necessary for
 261      the out block walker. */
 262   fix_start_proj(irg);
 263
 264   current_ir_graph = rem;
 265 }
 266
 267 void free_outs(ir_graph *irg) {
 268
 269   /* Update graph state */
 270   assert(get_irg_phase_state(current_ir_graph) != phase_building);
 271   current_ir_graph->outs_state = no_outs;
 272
 273   if (irg->outs) free(irg->outs);
 274   irg->outs = NULL;
 275 }