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 #ifdef HAVE_CONFIG_H
  27 #include "config.h"
  28 #endif
  29
  30 #include "irouts.h"
  31 #include "irnode_t.h"
  32 #include "irgraph_t.h"     /* To access irg->outs field (which is private to this module)
  33                               without public access routine */
  34 #include "irprog.h"
  35
  36 /**********************************************************************/
  37 /** Accessing the out datastructures                                 **/
  38 /**********************************************************************/
  39
  40 /* returns the number of successors of the node: */
  41 INLINE int get_irn_n_outs    (ir_node *node) {
  42   return (int)(node->out[0]);
  43 }
  44
  45 /* Access successor n */
  46 INLINE ir_node *get_irn_out      (ir_node *node, int pos) {
  47   assert(node);
  48   assert(pos >= 0 && pos < get_irn_n_outs(node));
  49   return node->out[pos+1];
  50 }
  51
  52 INLINE void set_irn_out      (ir_node *node, int pos, ir_node *out) {
  53   assert(node && out);
  54   assert(pos >= 0 && pos < get_irn_n_outs(node));
  55   node->out[pos+1] = out;
  56 }
  57
  58
  59 INLINE int get_Block_n_cfg_outs (ir_node *bl) {
  60   int i, n_cfg_outs = 0;
  61   assert(bl && (get_irn_op(bl) == op_Block));
  62   for (i = 0; i < (int)bl->out[0]; i++)
  63     if ((get_irn_mode(bl->out[i+1]) == mode_X) &&
  64         (get_irn_op(bl->out[i+1]) != op_End)) n_cfg_outs++;
  65   return n_cfg_outs;
  66 }
  67
  68
  69 INLINE ir_node *get_Block_cfg_out  (ir_node *bl, int pos) {
  70   int i, out_pos = 0;
  71   assert(bl && (get_irn_op(bl) == op_Block));
  72   for (i = 0; i < (int)bl->out[0]; i++)
  73     if ((get_irn_mode(bl->out[i+1]) == mode_X)  &&
  74         (get_irn_op(bl->out[i+1]) != op_End)) {
  75       if (out_pos == pos) {
  76         ir_node *cfop = bl->out[i+1];
  77         return cfop->out[0+1];
  78       } else {
  79         out_pos++;
  80       }
  81     }
  82   return NULL;
  83 }
  84
  85 void irg_out_walk_2(ir_node *node,  irg_walk_func *pre,
  86                     irg_walk_func *post, void *env) {
  87   int i;
  88   ir_node *succ;
  89
  90   assert(node);
  91   assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
  92
  93   set_irn_visited(node, get_irg_visited(current_ir_graph));
  94
  95   if (pre) pre(node, env);
  96
  97   for (i = 0; i < get_irn_n_outs(node); i++) {
  98     succ = get_irn_out(node, i);
  99     if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
 100       irg_out_walk_2(succ, pre, post, env);
 101   }
 102
 103   if (post) post(node, env);
 104
 105   return;
 106 }
 107
 108 void irg_out_walk(ir_node *node,
 109                         irg_walk_func *pre, irg_walk_func *post,
 110                         void *env) {
 111   assert(node);
 112   if (get_irg_outs_state(current_ir_graph) != no_outs) {
 113     inc_irg_visited (current_ir_graph);
 114     irg_out_walk_2(node, pre, post, env);
 115   }
 116   return;
 117 }
 118
 119 void irg_out_block_walk2(ir_node *bl,
 120                         irg_walk_func *pre, irg_walk_func *post,
 121                         void *env) {
 122   int i;
 123
 124   assert(get_irn_opcode(bl) == iro_Block);
 125
 126   if(get_Block_block_visited(bl) < get_irg_block_visited(current_ir_graph)) {
 127     set_Block_block_visited(bl, get_irg_block_visited(current_ir_graph));
 128
 129     if(pre)
 130       pre(bl, env);
 131
 132     for(i = 0; i < get_Block_n_cfg_outs(bl); i++) {
 133       /* find the corresponding predecessor block. */
 134       ir_node *pred = get_Block_cfg_out(bl, i);
 135       assert(get_irn_opcode(pred) == iro_Block);
 136       /* recursion */
 137       irg_out_block_walk2(pred, pre, post, env);
 138     }
 139
 140     if(post)
 141       post(bl, env);
 142   }
 143   return;
 144 }
 145
 146 /* Walks only over Block nodes in the graph.  Has it's own visited
 147    flag, so that it can be interleaved with the other walker.         */
 148 void irg_out_block_walk(ir_node *node,
 149                         irg_walk_func *pre, irg_walk_func *post,
 150                         void *env) {
 151
 152   assert((get_irn_op(node) == op_Block) || (get_irn_mode(node) == mode_X));
 153
 154   inc_irg_block_visited(current_ir_graph);
 155
 156   if (get_irn_mode(node) == mode_X) node = node->out[1];
 157   assert(get_irn_opcode(node)  == iro_Block);
 158
 159   irg_out_block_walk2(node, pre, post, env);
 160
 161   return;
 162
 163 }
 164
 165 /**********************************************************************/
 166 /** Building and Removing the out datasturcture                      **/
 167 /**                                                                  **/
 168 /** The outs of a graph are allocated in a single, large array.      **/
 169 /** This allows to allocate and deallocate the memory for the outs   **/
 170 /** on demand.  The large array is separated into many small ones    **/
 171 /** for each node.  Only a single field to reference the out array   **/
 172 /** is stored in each node and a field referencing the large out     **/
 173 /** array in irgraph.  The 0 field of each out array contains the    **/
 174 /** size of this array.  This saves memory in the irnodes themselves.**/
 175 /** The construction does two passes over the graph.  The first pass **/
 176 /** counts the overall number of outs and the outs of each node.  It **/
 177 /** stores the outs of each node in the out reference of the node.   **/
 178 /** Then the large array is allocated.  The second iteration chops   **/
 179 /** the large array into smaller parts, sets the out edges and       **/
 180 /** recounts the out edges.                                          **/
 181 /**********************************************************************/
 182
 183
 184 /* Returns the amount of out edges for not yet visited successors. */
 185 static int count_outs(ir_node *n) {
 186   int start, i, res, irn_arity;
 187   ir_node *succ;
 188
 189   set_irn_visited(n, get_irg_visited(current_ir_graph));
 190   n->out = (ir_node **) 1;     /* Space for array size. */
 191
 192   if ((get_irn_op(n) == op_Block)) start = 0; else start = -1;
 193   irn_arity = get_irn_arity(n);
 194   res = irn_arity - start +1;  /* --1 or --0; 1 for array size. */
 195   for (i = start; i < irn_arity; i++) {
 196     /* Optimize Tuples.  They annoy if walking the cfg. */
 197     succ = skip_Tuple(get_irn_n(n, i));
 198     set_irn_n(n, i, succ);
 199     /* count outs for successors */
 200     if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
 201       res += count_outs(succ);
 202     /* Count my outs */
 203     succ->out = (ir_node **)( (int)succ->out +1);
 204   }
 205   return res;
 206 }
 207
 208 static ir_node **set_out_edges(ir_node *n, ir_node **free) {
 209   int n_outs, start, i, irn_arity;
 210   ir_node *succ;
 211
 212   set_irn_visited(n, get_irg_visited(current_ir_graph));
 213
 214   /* Allocate my array */
 215   n_outs = (int) n->out;
 216   n->out = free;
 217   free = &free[n_outs];
 218   /* We count the successors again, the space will be sufficient.
 219      We use this counter to remember the position for the next back
 220      edge. */
 221   n->out[0] = (ir_node *)0;
 222
 223   if (get_irn_op(n) == op_Block) start = 0; else start = -1;
 224   irn_arity = get_irn_arity(n);
 225   for (i = start; i < irn_arity; i++) {
 226     succ = get_irn_n(n, i);
 227     /* Recursion */
 228     if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
 229       free = set_out_edges(succ, free);
 230     /* Remember our back edge */
 231     succ->out[get_irn_n_outs(succ)+1] = n;
 232     succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
 233   }
 234   return free;
 235 }
 236
 237 static INLINE void fix_start_proj(ir_graph *irg) {
 238   ir_node *proj = NULL, *startbl;
 239   int i;
 240   if (get_Block_n_cfg_outs(get_irg_start_block(irg))) {
 241     startbl = get_irg_start_block(irg);
 242     for (i = 0; i < get_irn_n_outs(startbl); i++)
 243       if (get_irn_mode(get_irn_out(startbl, i)) == mode_X)
 244         proj = get_irn_out(startbl, i);
 245     if (get_irn_out(proj, 0) == startbl) {
 246       assert(get_irn_n_outs(proj) == 2);
 247       set_irn_out(proj, 0, get_irn_out(proj, 1));
 248       set_irn_out(proj, 1, startbl);
 249     }
 250   }
 251 }
 252
 253 void compute_outs(ir_graph *irg) {
 254   ir_graph *rem = current_ir_graph;
 255   int n_out_edges = 0;
 256
 257   current_ir_graph = irg;
 258
 259   /* Update graph state */
 260   assert(get_irg_phase_state(current_ir_graph) != phase_building);
 261   current_ir_graph->outs_state = outs_consistent;
 262
 263   /* This first iteration counts the overall number of out edges and the
 264      number of out edges for each node. */
 265   inc_irg_visited(irg);
 266   n_out_edges = count_outs(get_irg_end(irg));
 267
 268   /* allocate memory for all out edges. */
 269   irg->outs = (ir_node **) malloc (n_out_edges * sizeof(ir_node *));
 270
 271   /* The second iteration splits the irg->outs array into smaller arrays
 272      for each node and writes the back edges into this array. */
 273   inc_irg_visited(irg);
 274   set_out_edges(get_irg_end(irg), irg->outs);
 275
 276   /* We want that the out of ProjX from Start contains the next block at
 277      position 1, the Start block at position 2.  This is necessary for
 278      the out block walker. */
 279   fix_start_proj(irg);
 280
 281   current_ir_graph = rem;
 282 }
 283
 284
 285 void compute_ip_outs(ir_graph *irg) { /*irg_walk_func *pre, irg_walk_func *post, void *env) { */
 286   int i;
 287   ir_graph *rem = current_ir_graph;
 288   int rem_view = interprocedural_view;
 289
 290   interprocedural_view = true;
 291
 292   inc_max_irg_visited();
 293   /* Fix all irg_visited flags */
 294   for (i = 0; i < get_irp_n_irgs(); i++)
 295     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
 296
 297   /* Walk starting at unreachable procedures. Only these
 298    * have End blocks visible in interprocedural view. */
 299   for (i = 0; i < get_irp_n_irgs(); i++) {
 300     ir_node *sb;
 301     current_ir_graph = get_irp_irg(i);
 302
 303     sb = get_irg_start_block(current_ir_graph);
 304
 305     if ((get_Block_n_cfgpreds(sb) > 1) ||
 306         (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
 307
 308     compute_outs(current_ir_graph); /*cg_walk_2(get_irg_end(current_ir_graph), pre, post, env);*/
 309   }
 310
 311   /* Check whether we walked all procedures: there could be procedures
 312      with cyclic calls but no call from the outside. */
 313   for (i = 0; i < get_irp_n_irgs(); i++) {
 314     ir_node *sb;
 315     current_ir_graph = get_irp_irg(i);
 316
 317     /* Test start block: if inner procedure end and end block are not
 318      * visible and therefore not marked. */
 319     sb = get_irg_start_block(current_ir_graph);
 320     if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) {
 321       compute_outs(current_ir_graph); /*cg_walk_2(sb, pre, post, env);    */
 322     }
 323   }
 324
 325   /* Walk all endless loops in inner procedures.
 326    * We recognize an inner procedure if the End node is not visited. */
 327   for (i = 0; i < get_irp_n_irgs(); i++) {
 328     ir_node *e;
 329     current_ir_graph = get_irp_irg(i);
 330     e = get_irg_end(current_ir_graph);
 331     if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
 332       /* Don't visit the End node. */
 333       /* int j;
 334          for (j = 0; j < get_End_n_keepalives(e); j++)
 335            cg_walk_2(get_End_keepalive(e, j), pre, post, env);*/
 336       compute_outs(current_ir_graph);
 337     }
 338   }
 339
 340   interprocedural_view = rem_view;
 341   current_ir_graph = rem;
 342 }
 343
 344
 345
 346
 347 void free_outs(ir_graph *irg) {
 348
 349   /* Update graph state */
 350   assert(get_irg_phase_state(current_ir_graph) != phase_building);
 351   current_ir_graph->outs_state = no_outs;
 352
 353   if (irg->outs) free(irg->outs);
 354   irg->outs = NULL;
 355 }