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

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