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