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  * Enter memory for the outs to a node.
 241  *
 242  * @param n      current node
 243  * @param free   current free address in the chunk allocated for the outs
 244  *
 245  * @return The next free address
 246  */
 247 static ir_node **set_out_edges(ir_node *n, ir_node **free) {
 248   int n_outs, start, i, irn_arity;
 249   ir_node *succ;
 250
 251   set_irn_visited(n, get_irg_visited(current_ir_graph));
 252
 253   /* Allocate my array */
 254   n_outs = (int) n->out;
 255   n->out = free;
 256 #ifdef DEBUG_libfirm
 257   n->out_valid = 1;
 258 #endif /* defined DEBUG_libfirm */
 259   free += n_outs;
 260   /* We count the successors again, the space will be sufficient.
 261      We use this counter to remember the position for the next back
 262      edge. */
 263   n->out[0] = (ir_node *)0;
 264
 265   start = is_Block(n) ? 0 : -1;
 266   irn_arity = get_irn_arity(n);
 267
 268   for (i = start; i < irn_arity; i++) {
 269     succ = get_irn_n(n, i);
 270     /* Recursion */
 271     if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
 272       free = set_out_edges(succ, free);
 273     /* Remember our back edge */
 274     succ->out[get_irn_n_outs(succ)+1] = n;
 275     succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
 276   }
 277   return free;
 278 }
 279
 280 /* We want that the out of ProjX from Start contains the next block at
 281    position 1, the Start block at position 2.  This is necessary for
 282    the out block walker. */
 283 static INLINE void fix_start_proj(ir_graph *irg) {
 284   ir_node *proj    = NULL;
 285   ir_node *startbl = get_irg_start_block(irg);
 286   int i;
 287
 288   if (get_Block_n_cfg_outs(startbl)) {
 289     for (i = 0; i < get_irn_n_outs(startbl); i++)
 290       if (get_irn_mode(get_irn_out(startbl, i)) == mode_X) {
 291         proj = get_irn_out(startbl, i);
 292         break;
 293       }
 294
 295     if (get_irn_out(proj, 0) == startbl) {
 296       assert(get_irn_n_outs(proj) == 2);
 297       set_irn_out(proj, 0, get_irn_out(proj, 1));
 298       set_irn_out(proj, 1, startbl);
 299     }
 300   }
 301 }
 302
 303 /* compute the outs for a given graph */
 304 void compute_outs(ir_graph *irg) {
 305   ir_graph *rem = current_ir_graph;
 306   int n_out_edges = 0;
 307   ir_node **end = NULL;         /* Only for debugging */
 308
 309   current_ir_graph = irg;
 310
 311   /* Update graph state */
 312   assert(get_irg_phase_state(current_ir_graph) != phase_building);
 313
 314   if (current_ir_graph->outs_state != outs_none)
 315     free_outs(current_ir_graph);
 316   current_ir_graph->outs_state = outs_consistent;
 317
 318   /* This first iteration counts the overall number of out edges and the
 319      number of out edges for each node. */
 320   inc_irg_visited(irg);
 321   n_out_edges = count_outs(get_irg_end(irg));
 322
 323   /* allocate memory for all out edges. */
 324   irg->outs = xcalloc(n_out_edges, sizeof(irg->outs[0]));
 325 #ifdef DEBUG_libfirm
 326   irg->n_outs = n_out_edges;
 327 #endif /* defined DEBUG_libfirm */
 328
 329   /* The second iteration splits the irg->outs array into smaller arrays
 330      for each node and writes the back edges into this array. */
 331   inc_irg_visited(irg);
 332   end = set_out_edges(get_irg_end(irg), irg->outs);
 333
 334   /* Check how much memory we have used */
 335   assert (end == (irg->outs + n_out_edges));
 336
 337   /* We want that the out of ProjX from Start contains the next block at
 338      position 1, the Start block at position 2.  This is necessary for
 339      the out block walker. */
 340   fix_start_proj(irg);
 341
 342   current_ir_graph = rem;
 343 }
 344
 345
 346
 347
 348 /*------------------------------------------------------------*
 349  *  This computes the outedges for in interprocedural graph.  *
 350  *  There is one quirk:                                       *
 351  *  The number of the outedges for each node is saved in      *
 352  *  the first member of the ir_node** array. Maybe we should  *
 353  *  change this to make it more portable...                   *
 354  *------------------------------------------------------------*/
 355
 356
 357 /**
 358  * Inits the number of outedges for each node
 359  * before counting.
 360  */
 361 static void init_count(ir_node * node, void *env) {
 362   node->out = (ir_node **) 1; /* 1 for the array size */
 363 }
 364
 365
 366 /**
 367  * Adjusts the out edge count for its predecessors
 368  * and adds the current arity to the overall count,
 369  * which is saved in "env"
 370  */
 371 static void node_arity_count(ir_node * node, void * env)
 372 {
 373   int *anz = (int *) env, arity, n_outs, i, start;
 374   ir_node *succ;
 375
 376   arity = get_irn_arity(node);
 377   start = (is_Block(node)) ? 0 : -1;
 378
 379   n_outs = 1 + arity + (-start);  // ((is_Block(node)) ? 0 : 1);   // Why + 1??
 380   *anz += n_outs;
 381
 382   for(i = start; i < arity; i++) {
 383     succ = get_irn_n(node, i);
 384     succ->out = (ir_node **)((int)succ->out + 1);
 385   }
 386 }
 387
 388
 389 /*
 390  * Inits all nodes for setting the outedges
 391  * Returns the overall count of edges
 392  */
 393 int count_ip_outs(void) {
 394
 395   int res = 0;
 396
 397   cg_walk(init_count, node_arity_count, &res);
 398
 399   return(res);
 400 }
 401
 402 static int dummy_count = 0, global_count; /* Only for debugging */
 403
 404 /**
 405  * For each node: Sets the pointer to array
 406  * in which the outedges are written later.
 407  * The current array start is transported in env
 408  */
 409 static void set_array_pointer(ir_node *node, void *env) {
 410
 411   int n_outs;
 412   ir_node ***free = (ir_node ***) env;
 413
 414   /* Allocate my array */
 415   n_outs = (int) node -> out;  /* We wrote the count here in count_ip_outs */
 416   dummy_count += n_outs;
 417   assert(dummy_count <= global_count && "More outedges than initially counted!");
 418   node -> out = *free;
 419   *free = &((*free)[n_outs]);
 420   /* We count the successors again, the space will be sufficient.
 421      We use this counter to remember the position for the next back
 422      edge. */
 423   node -> out[0] = (ir_node *) 0;
 424 }
 425
 426
 427 /**
 428  * Adds an outedge from the predecessor to the
 429  * current node.
 430  */
 431 static void set_out_pointer(ir_node * node, void * env) {
 432   int i, arity = get_irn_arity(node);
 433   ir_node *succ;
 434   int start = (!is_Block(node)) ? -1 : 0;
 435
 436   for(i = start; i < arity; i++) {
 437     succ = get_irn_n(node, i);
 438     succ->out[get_irn_n_outs(succ)+1] = node;
 439     succ->out[0] = (ir_node *) (get_irn_n_outs(succ) + 1);
 440   }
 441 }
 442
 443
 444 /*
 445  * Sets the outedges for all nodes.
 446  */
 447 void set_ip_outs(void)
 448 {
 449   ir_node **outedge_array = get_irp_ip_outedges();
 450   cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
 451 }
 452
 453
 454
 455 /*
 456  * Counts the outedges, allocates memory to save the
 457  * outedges and fills this outedge array in interprocedural
 458  * view!
 459  */
 460 void compute_ip_outs(void) {
 461
 462   int n_out_edges;
 463   ir_node **out_edges;
 464
 465   assert(get_irp_ip_view_state() == ip_view_valid &&
 466      "Cannot construct outs for invalid ip view.");
 467
 468   if (irp->outs_state != outs_none) {
 469     free_ip_outs();
 470   }
 471
 472   global_count = n_out_edges = count_ip_outs();
 473   out_edges = xcalloc(n_out_edges, sizeof(out_edges[0]));
 474   set_irp_ip_outedges(out_edges);
 475   set_ip_outs();
 476 }
 477
 478 void free_ip_outs(void)
 479 {
 480   ir_node **out_edges = get_irp_ip_outedges();
 481   if (out_edges != NULL) {
 482     free(out_edges);
 483     set_irp_ip_outedges(NULL);
 484   }
 485   irp->outs_state = outs_none;
 486 }
 487
 488
 489 void free_outs(ir_graph *irg) {
 490
 491   /*   current_ir_graph->outs_state = outs_none; */
 492   irg->outs_state = outs_none;
 493
 494   if (irg->outs) {
 495 #ifdef DEBUG_libfirm
 496     memset(irg->outs, 0, irg->n_outs);
 497 #endif /* defined DEBUG_libfirm */
 498     free(irg->outs);
 499     irg->outs = NULL;
 500 #ifdef DEBUG_libfirm
 501     irg->n_outs = 0;
 502 #endif /* defined DEBUG_libfirm */
 503   }
 504
 505 #ifdef DEBUG_libfirm
 506   /* when debugging, *always* reset all nodes' outs!  irg->outs might
 507      have been lying to us */
 508   irg_walk_graph (irg, reset_outs, NULL, NULL);
 509 #endif /* defined DEBUG_libfirm */
 510 }