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