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 void irg_out_walk_2(ir_node *node,  void (pre)(ir_node*, void*),
  41                     void (post)(ir_node*, void*), void *env) {
  42   int i;
  43   ir_node *succ;
  44
  45   //printf("++ in walker (%d outs) ", get_irn_n_outs(node)); DDMSG2(node);
  46
  47   assert(node);
  48   assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
  49
  50   set_irn_visited(node, get_irg_visited(current_ir_graph));
  51
  52   if (pre) pre(node, env);
  53
  54   for (i = 0; i < get_irn_n_outs(node); i++) {
  55     succ = get_irn_out(node, i);
  56     if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
  57       irg_out_walk_2(succ, pre, post, env);
  58   }
  59
  60   if (post) post(node, env);
  61
  62   //printf("++ done walking "); DDMSG2(node);
  63   return;
  64 }
  65
  66 void irg_out_walk(ir_node *node,
  67                   void (pre)(ir_node*, void*), void (post)(ir_node*, void*),
  68                   void *env) {
  69   assert(node);
  70   if (get_irg_outs_state(current_ir_graph) != no_outs) {
  71     inc_irg_visited (current_ir_graph);
  72     irg_out_walk_2(node, pre, post, env);
  73   }
  74   return;
  75 }
  76
  77 /* Walks only over Block nodes in the graph.  Has it's own visited
  78    flag, so that it can be interleaved with the other walker.         */
  79 void irg_out_block_walk(ir_node *node,
  80                         void (pre)(ir_node*, void*), void (post)(ir_node*, void*),
  81                         void *env) {
  82 }
  83
  84 /**********************************************************************/
  85 /** Building and Removing the out datasturcture                      **/
  86 /**                                                                  **/
  87 /** The outs of a graph are allocated in a single, large array.      **/
  88 /** This allows to allocate and deallocate the memory for the outs   **/
  89 /** on demand.  The large array is separated into many small ones    **/
  90 /** for each node.  Only a single field to reference the out array   **/
  91 /** is stored in each node and a field referencing the large out     **/
  92 /** array in irgraph.  The 0 field of each out array contains the    **/
  93 /** size of this array.  This saves memory in the irnodes themselves.**/
  94 /** The construction does two passes over the graph.  The first pass **/
  95 /** counts the overall number of outs and the outs of each node.  It **/
  96 /** stores the outs of each node in the out reference of the node.   **/
  97 /** Then the large array is allocated.  The second iteration chops   **/
  98 /** the large array into smaller parts, sets the out edges and       **/
  99 /** recounts the out edges.                                          **/
 100 /**********************************************************************/
 101
 102
 103 /* Returns the amount of out edges for not yet visited successors. */
 104 int count_outs(ir_node *n) {
 105   int start, i, res;
 106   ir_node *succ;
 107
 108   set_irn_visited(n, get_irg_visited(current_ir_graph));
 109   n->out = (ir_node **) 1;     /* Space for array size. */
 110
 111   if ((get_irn_op(n) == op_Block)) start = 0; else start = -1;
 112   res = get_irn_arity(n) - start +1;  /* --1 or --0; 1 for array size. */
 113   for (i = start; i < get_irn_arity(n); i++) {
 114     succ = get_irn_n(n, i);
 115     /* count outs for successors */
 116     if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
 117       res += count_outs(succ);
 118     /* Count my outs */
 119     succ->out = (ir_node **)( (int)succ->out +1);
 120   }
 121   return res;
 122 }
 123
 124 ir_node **set_out_edges(ir_node *n, ir_node **free) {
 125   int n_outs, start, i;
 126   ir_node *succ;
 127
 128   set_irn_visited(n, get_irg_visited(current_ir_graph));
 129
 130   /* Allocate my array */
 131   n_outs = (int) n->out;
 132   n->out = free;
 133   free = &free[n_outs];
 134   /* We count the successors again, the space will be sufficient.
 135      We use this counter to remember the position for the next back
 136      edge. */
 137   n->out[0] = (ir_node *)0;
 138
 139   if (get_irn_op(n) == op_Block) start = 0; else start = -1;
 140   for (i = start; i < get_irn_arity(n); i++) {
 141     succ = get_irn_n(n, i);
 142     /* Recursion */
 143     if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
 144       free = set_out_edges(succ, free);
 145     /* Remember our back edge */
 146     succ->out[get_irn_n_outs(succ)+1] = n;
 147     succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
 148   }
 149   return free;
 150 }
 151
 152 void compute_outs(ir_graph *irg) {
 153   ir_graph *rem = current_ir_graph;
 154   int n_out_edges = 0;
 155
 156   current_ir_graph = irg;
 157
 158   /* Update graph state */
 159   assert(get_irg_phase_state(current_ir_graph) != phase_building);
 160   current_ir_graph->outs_state = outs_consistent;
 161
 162   /* This first iteration counts the overall number of out edges and the
 163      number of out edges for each node. */
 164   inc_irg_visited(irg);
 165   n_out_edges = count_outs(get_irg_end(irg));
 166
 167   /* allocate memory for all out edges. */
 168   irg->outs = (ir_node **) malloc (n_out_edges * sizeof(ir_node *));
 169
 170   /* The second iteration splits the irg->outs array into smaller arrays
 171      for each node and writes the back edges into this array. */
 172   inc_irg_visited(irg);
 173   set_out_edges(get_irg_end(irg), irg->outs);
 174
 175   current_ir_graph = rem;
 176 }
 177
 178 void free_outs(ir_graph *irg) {
 179
 180   /* Update graph state */
 181   // assert(get_irg_phase_state(current_ir_graph) != phase_building);
 182   current_ir_graph->outs_state = no_outs;
 183
 184   if (irg->outs) free(irg->outs);
 185   irg->outs = NULL;
 186 }