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