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