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