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