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