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