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_t.h"
  35 #include "irgwalk.h"
  36
  37 /**********************************************************************/
  38 /** Accessing the out datastructures                                 **/
  39 /**********************************************************************/
  40
  41 /* returns the number of successors of the node: */
  42 INLINE int get_irn_n_outs    (ir_node *node) {
  43   return (int)(node->out[0]);
  44 }
  45
  46 /* Access successor n */
  47 INLINE ir_node *get_irn_out      (ir_node *node, int pos) {
  48   assert(node);
  49   assert(pos >= 0 && pos < get_irn_n_outs(node));
  50   return node->out[pos+1];
  51 }
  52
  53 INLINE void set_irn_out      (ir_node *node, int pos, ir_node *out) {
  54   assert(node && out);
  55   assert(pos >= 0 && pos < get_irn_n_outs(node));
  56   node->out[pos+1] = out;
  57 }
  58
  59
  60 INLINE int get_Block_n_cfg_outs (ir_node *bl) {
  61   int i, n_cfg_outs = 0;
  62   assert(bl && (get_irn_op(bl) == op_Block));
  63   for (i = 0; i < (int)bl->out[0]; i++)
  64     if ((intern_get_irn_mode(bl->out[i+1]) == mode_X) &&
  65     (intern_get_irn_op(bl->out[i+1]) != op_End)) n_cfg_outs++;
  66   return n_cfg_outs;
  67 }
  68
  69
  70 INLINE ir_node *get_Block_cfg_out  (ir_node *bl, int pos) {
  71   int i, out_pos = 0;
  72   assert(bl && (get_irn_op(bl) == op_Block));
  73   for (i = 0; i < (int)bl->out[0]; i++)
  74     if ((intern_get_irn_mode(bl->out[i+1]) == mode_X)  &&
  75     (intern_get_irn_op(bl->out[i+1]) != op_End)) {
  76       if (out_pos == pos) {
  77     ir_node *cfop = bl->out[i+1];
  78     return cfop->out[0+1];
  79       } else {
  80     out_pos++;
  81       }
  82     }
  83   return NULL;
  84 }
  85
  86 void irg_out_walk_2(ir_node *node,  irg_walk_func *pre,
  87             irg_walk_func *post, void *env) {
  88   int i;
  89   ir_node *succ;
  90
  91   assert(node);
  92   assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
  93
  94   set_irn_visited(node, get_irg_visited(current_ir_graph));
  95
  96   if (pre) pre(node, env);
  97
  98   for (i = 0; i < get_irn_n_outs(node); i++) {
  99     succ = get_irn_out(node, i);
 100     if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
 101       irg_out_walk_2(succ, pre, post, env);
 102   }
 103
 104   if (post) post(node, env);
 105
 106   return;
 107 }
 108
 109 void irg_out_walk(ir_node *node,
 110             irg_walk_func *pre, irg_walk_func *post,
 111             void *env) {
 112   assert(node);
 113   if (get_irg_outs_state(current_ir_graph) != no_outs) {
 114     inc_irg_visited (current_ir_graph);
 115     irg_out_walk_2(node, pre, post, env);
 116   }
 117   return;
 118 }
 119
 120 void irg_out_block_walk2(ir_node *bl,
 121             irg_walk_func *pre, irg_walk_func *post,
 122             void *env) {
 123   int i;
 124
 125   if(get_Block_block_visited(bl) < get_irg_block_visited(current_ir_graph)) {
 126     set_Block_block_visited(bl, get_irg_block_visited(current_ir_graph));
 127
 128     if(pre)
 129       pre(bl, env);
 130
 131     for(i = 0; i < get_Block_n_cfg_outs(bl); i++) {
 132       /* find the corresponding predecessor block. */
 133       ir_node *pred = get_Block_cfg_out(bl, i);
 134       /* recursion */
 135       irg_out_block_walk2(pred, pre, post, env);
 136     }
 137
 138     if(post)
 139       post(bl, env);
 140   }
 141   return;
 142 }
 143
 144 /* Walks only over Block nodes in the graph.  Has it's own visited
 145    flag, so that it can be interleaved with the other walker.         */
 146 void irg_out_block_walk(ir_node *node,
 147             irg_walk_func *pre, irg_walk_func *post,
 148             void *env) {
 149
 150   assert((get_irn_op(node) == op_Block) || (intern_get_irn_mode(node) == mode_X));
 151
 152   inc_irg_block_visited(current_ir_graph);
 153
 154   if (intern_get_irn_mode(node) == mode_X) node = node->out[1];
 155
 156   irg_out_block_walk2(node, pre, post, env);
 157
 158   return;
 159
 160 }
 161
 162 /**********************************************************************/
 163 /** Building and Removing the out datasturcture                      **/
 164 /**                                                                  **/
 165 /** The outs of a graph are allocated in a single, large array.      **/
 166 /** This allows to allocate and deallocate the memory for the outs   **/
 167 /** on demand.  The large array is separated into many small ones    **/
 168 /** for each node.  Only a single field to reference the out array   **/
 169 /** is stored in each node and a field referencing the large out     **/
 170 /** array in irgraph.  The 0 field of each out array contains the    **/
 171 /** size of this array.  This saves memory in the irnodes themselves.**/
 172 /** The construction does two passes over the graph.  The first pass **/
 173 /** counts the overall number of outs and the outs of each node.  It **/
 174 /** stores the outs of each node in the out reference of the node.   **/
 175 /** Then the large array is allocated.  The second iteration chops   **/
 176 /** the large array into smaller parts, sets the out edges and       **/
 177 /** recounts the out edges.                                          **/
 178 /** Removes Tuple nodes!                                             **/
 179 /**********************************************************************/
 180
 181
 182 /* Returns the amount of out edges for not yet visited successors. */
 183 static int count_outs(ir_node *n) {
 184   int start, i, res, irn_arity;
 185   ir_node *succ;
 186
 187   set_irn_visited(n, get_irg_visited(current_ir_graph));
 188   n->out = (ir_node **) 1;     /* Space for array size. */
 189
 190   if ((intern_get_irn_op(n) == op_Block)) start = 0; else start = -1;
 191   irn_arity = intern_get_irn_arity(n);
 192   res = irn_arity - start +1;  /* --1 or --0; 1 for array size. */
 193   for (i = start; i < irn_arity; i++) {
 194     /* Optimize Tuples.  They annoy if walking the cfg. */
 195     succ = skip_Tuple(intern_get_irn_n(n, i));
 196     set_irn_n(n, i, succ);
 197     /* count outs for successors */
 198     if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
 199       res += count_outs(succ);
 200     /* Count my outs */
 201     succ->out = (ir_node **)( (int)succ->out +1);
 202   }
 203   return res;
 204 }
 205
 206 static ir_node **set_out_edges(ir_node *n, ir_node **free) {
 207   int n_outs, start, i, irn_arity;
 208   ir_node *succ;
 209
 210   set_irn_visited(n, get_irg_visited(current_ir_graph));
 211
 212   /* Allocate my array */
 213   n_outs = (int) n->out;
 214   n->out = free;
 215   free = &free[n_outs];
 216   /* We count the successors again, the space will be sufficient.
 217      We use this counter to remember the position for the next back
 218      edge. */
 219   n->out[0] = (ir_node *)0;
 220
 221   if (intern_get_irn_op(n) == op_Block) start = 0; else start = -1;
 222   irn_arity = intern_get_irn_arity(n);
 223   for (i = start; i < irn_arity; i++) {
 224     succ = intern_get_irn_n(n, i);
 225     /* Recursion */
 226     if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
 227       free = set_out_edges(succ, free);
 228     /* Remember our back edge */
 229     succ->out[get_irn_n_outs(succ)+1] = n;
 230     succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
 231   }
 232   return free;
 233 }
 234
 235 static INLINE void fix_start_proj(ir_graph *irg) {
 236   ir_node *proj = NULL, *startbl;
 237   int i;
 238   if (get_Block_n_cfg_outs(get_irg_start_block(irg))) {
 239     startbl = get_irg_start_block(irg);
 240     for (i = 0; i < get_irn_n_outs(startbl); i++)
 241       if (intern_get_irn_mode(get_irn_out(startbl, i)) == mode_X)
 242     proj = get_irn_out(startbl, i);
 243     if (get_irn_out(proj, 0) == startbl) {
 244       assert(get_irn_n_outs(proj) == 2);
 245       set_irn_out(proj, 0, get_irn_out(proj, 1));
 246       set_irn_out(proj, 1, startbl);
 247     }
 248   }
 249 }
 250
 251 void compute_outs(ir_graph *irg) {
 252   ir_graph *rem = current_ir_graph;
 253   int n_out_edges = 0;
 254
 255   current_ir_graph = irg;
 256
 257   /* Update graph state */
 258   assert(get_irg_phase_state(current_ir_graph) != phase_building);
 259   if (current_ir_graph->outs_state != no_outs) free_outs(current_ir_graph);
 260   current_ir_graph->outs_state = outs_consistent;
 261
 262   /* This first iteration counts the overall number of out edges and the
 263      number of out edges for each node. */
 264   inc_irg_visited(irg);
 265   n_out_edges = count_outs(get_irg_end(irg));
 266
 267   /* allocate memory for all out edges. */
 268   irg->outs = (ir_node **) malloc (n_out_edges * sizeof(ir_node *));
 269
 270   /* The second iteration splits the irg->outs array into smaller arrays
 271      for each node and writes the back edges into this array. */
 272   inc_irg_visited(irg);
 273   set_out_edges(get_irg_end(irg), irg->outs);
 274
 275   /* We want that the out of ProjX from Start contains the next block at
 276      position 1, the Start block at position 2.  This is necessary for
 277      the out block walker. */
 278   fix_start_proj(irg);
 279
 280   current_ir_graph = rem;
 281 }
 282
 283
 284
 285
 286 /****************************************************************
 287  **  This computes the outedges for in interprocedural graph.  **
 288  **  There is one quirk:                                       **
 289  **  The number of the outedges for each node is saved in      **
 290  **  the first member of the ir_node** array. Maybe we should  **
 291  **  change this to make it more portable...                   **
 292  ****************************************************************/
 293
 294
 295 /* ------------------------------------------
 296    Inits the number of outedges for each node
 297    before counting.
 298    ------------------------------------------ */
 299
 300 static void init_count(ir_node * node, void * env)
 301 {
 302   node->out = (ir_node **) 1; /* 1 for the array size */
 303 }
 304
 305
 306 /* -----------------------------------------------
 307    Adjusts the out edge count for its predecessors
 308    and adds the current arity to the overall count,
 309    which is saved in "env"
 310    ------------------------------------------------ */
 311
 312 static void node_arity_count(ir_node * node, void * env)
 313 {
 314   int *anz = (int *) env, arity, i, start;
 315   ir_node *succ;
 316
 317   arity = 1 + intern_get_irn_arity(node)
 318             + ((is_Block(node)) ? 0 : 1);
 319   *anz += arity;
 320
 321   start = (is_Block(node)) ? 0 : -1;
 322   for(i = start; i < intern_get_irn_arity(node); i++)
 323     {
 324       succ = intern_get_irn_n(node, i);
 325       succ->out = (ir_node **)((int)succ->out + 1);
 326     }
 327 }
 328
 329
 330 /* ----------------------------------------
 331    Inits all nodes for setting the outedges
 332    Returns the overall count of edges
 333    ---------------------------------------- */
 334
 335 int count_ip_outs(void) {
 336
 337   int res = 0;
 338
 339   cg_walk(init_count, node_arity_count, &res);
 340
 341   return(res);
 342 }
 343
 344 int dummy_count = 0, global_count; /* Only for debugging */
 345
 346 /* ---------------------------------------------
 347    For each node: Sets the pointer to array
 348    in which the outedges are written later.
 349    The current array start is transported in env
 350    --------------------------------------------- */
 351
 352 static void set_array_pointer(ir_node *node, void *env) {
 353
 354   int n_outs;
 355   ir_node ***free = (ir_node ***) env;
 356
 357   /* Allocate my array */
 358   n_outs = (int) node -> out;  /* We wrote the count here in count_ip_outs */
 359   dummy_count += n_outs;
 360   assert(dummy_count <= global_count && "More outedges than initialliy counted!");
 361   node -> out = *free;
 362   *free = &((*free)[n_outs]);
 363   /* We count the successors again, the space will be sufficient.
 364      We use this counter to remember the position for the next back
 365      edge. */
 366   node -> out[0] = (ir_node *) 0;
 367 }
 368
 369
 370 /* -------------------------------------------
 371    Adds an outedge from the predecessor to the
 372    current node.
 373    ------------------------------------------- */
 374
 375 static void set_out_pointer(ir_node * node, void * env) {
 376   int i;
 377   ir_node *succ;
 378   int start = (!is_Block(node)) ? -1 : 0;
 379
 380   for(i = start; i < intern_get_irn_arity(node); i++)
 381     {
 382       succ = intern_get_irn_n(node, i);
 383       succ->out[get_irn_n_outs(succ)+1] = node;
 384       succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
 385     }
 386 }
 387
 388
 389 /* -------------------------------
 390    Sets the outedges for all nodes.
 391    -------------------------------- */
 392
 393 void set_ip_outs(void)
 394 {
 395   ir_node **outedge_array = get_irp_ip_outedges();
 396   cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
 397 }
 398
 399
 400
 401 /* --------------------------------------------------------
 402    Counts the outedges, allocates memory to save the
 403    outedges and fills this outedge array in interprocedural
 404    view!
 405    -------------------------------------------------------- */
 406
 407 void compute_ip_outs(void) {
 408
 409   int n_out_edges;
 410   ir_node **out_edges;
 411
 412   assert(get_irp_ip_view_state() == ip_view_valid &&
 413          "Cannot construct outs for invalid ip view.");
 414
 415   if (irp->outs_state != no_outs) free_ip_outs();
 416
 417   global_count = n_out_edges = count_ip_outs();
 418   out_edges = (ir_node **) malloc (n_out_edges * sizeof(ir_node *));
 419   set_irp_ip_outedges(out_edges);
 420   set_ip_outs();
 421 }
 422
 423 void free_ip_outs(void)
 424 {
 425   ir_node **out_edges = get_irp_ip_outedges();
 426   if (out_edges != NULL)
 427     {
 428       free(out_edges);
 429       set_irp_ip_outedges(NULL);
 430     }
 431   irp->outs_state = no_outs;
 432 }
 433
 434
 435 void free_outs(ir_graph *irg) {
 436
 437   current_ir_graph->outs_state = no_outs;
 438
 439   if (irg->outs) free(irg->outs);
 440   irg->outs = NULL;
 441 }