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