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 #include "irtools.h"
  37
  38 #ifdef DEBUG_libfirm
  39 /* Note:  ir_node.out_valid and ir_graph.n_outs are only present when DEBUG_libfirm is defined */
  40 /* Accesses to out_valid and n_outs are fenced out to avoid breakage
  41    when compiling with neither DEBUG_libfirm or NDEBUG defined */
  42 #endif /* defined DEBUG_libfirm */
  43
  44 /*--------------------------------------------------------------------*/
  45 /** Accessing the out datastructures                                 **/
  46 /*--------------------------------------------------------------------*/
  47
  48 /** Clear the outs of a node */
  49 static void reset_outs (ir_node *node, void *unused)
  50 {
  51   node->out = NULL;
  52 #ifdef DEBUG_libfirm
  53   node->out_valid = 0;
  54 #endif /* defined DEBUG_libfirm */
  55 }
  56
  57 /* returns the number of successors of the node: */
  58 int get_irn_n_outs    (ir_node *node) {
  59   assert(node && node->kind == k_ir_node);
  60 #ifdef DEBUG_libfirm
  61   /* assert (node->out_valid); */
  62 #endif /* defined DEBUG_libfirm */
  63   return PTR_TO_INT(node->out[0]);
  64 }
  65
  66 /* Access successor n */
  67 ir_node *get_irn_out      (ir_node *node, int pos) {
  68   assert(pos >= 0 && pos < get_irn_n_outs(node));
  69 #ifdef DEBUG_libfirm
  70   /* assert (node->out_valid); */
  71 #endif /* defined DEBUG_libfirm */
  72   return node->out[pos+1];
  73 }
  74
  75 void set_irn_out      (ir_node *node, int pos, ir_node *out) {
  76   assert(node && out);
  77   assert(pos >= 0 && pos < get_irn_n_outs(node));
  78 #ifdef DEBUG_libfirm
  79   node->out_valid = 1;          /* assume that this function is used correctly */
  80 #endif /* defined DEBUG_libfirm */
  81   node->out[pos+1] = out;
  82 }
  83
  84
  85 int get_Block_n_cfg_outs(ir_node *bl) {
  86   int i, n_cfg_outs = 0;
  87   assert(bl && is_Block(bl));
  88 #ifdef DEBUG_libfirm
  89   assert (bl->out_valid);
  90 #endif /* defined DEBUG_libfirm */
  91   for (i = 1; i <= PTR_TO_INT(bl->out[0]); i++)
  92     if ((get_irn_mode(bl->out[i]) == mode_X) &&
  93         (get_irn_op(bl->out[i]) != op_End))
  94       n_cfg_outs++;
  95   return n_cfg_outs;
  96 }
  97
  98
  99 ir_node *get_Block_cfg_out(ir_node *bl, int pos) {
 100   int i, out_pos = 0;
 101   assert(bl && (get_irn_op(bl) == op_Block));
 102 #ifdef DEBUG_libfirm
 103   assert (bl->out_valid);
 104 #endif /* defined DEBUG_libfirm */
 105   for (i = 1; i <= PTR_TO_INT(bl->out[0]); i++)
 106     if ((get_irn_mode(bl->out[i]) == mode_X)  &&
 107         (get_irn_op(bl->out[i]) != op_End)) {
 108       if (out_pos == pos) {
 109         ir_node *cfop = bl->out[i];
 110         return cfop->out[1];
 111       } else
 112         out_pos++;
 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   mark_irn_visited(n);
 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 *pred = skip_Tuple(get_irn_n(n, i));
 227     set_irn_n(n, i, pred);
 228
 229     /* count outs for successors */
 230     if (irn_not_visited(pred))
 231       res += _count_outs(pred);
 232
 233     /* Count my outs */
 234     pred->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(pred->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, irg_args 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 (irn_not_visited(n)) {
 253     n->out = (ir_node **)1;
 254     ++res;
 255   }
 256
 257   n = get_irg_args(irg);
 258   if (irn_not_visited(n)) {
 259     n->out = (ir_node **)1;
 260     ++res;
 261   }
 262
 263   return res;
 264 }
 265
 266 /**
 267  * Enter memory for the outs to a node.
 268  *
 269  * @param n      current node
 270  * @param free   current free address in the chunk allocated for the outs
 271  *
 272  * @return The next free address
 273  */
 274 static ir_node **_set_out_edges(ir_node *n, ir_node **free) {
 275   int n_outs, start, i, irn_arity;
 276   ir_node *pred;
 277
 278   set_irn_visited(n, get_irg_visited(current_ir_graph));
 279
 280   /* Allocate my array */
 281   n_outs = PTR_TO_INT(n->out);
 282   n->out = free;
 283 #ifdef DEBUG_libfirm
 284   n->out_valid = 1;
 285 #endif /* defined DEBUG_libfirm */
 286   free += n_outs;
 287   /* We count the successors again, the space will be sufficient.
 288      We use this counter to remember the position for the next back
 289      edge. */
 290   n->out[0] = (ir_node *)0;
 291
 292   start = is_Block(n) ? 0 : -1;
 293   irn_arity = get_irn_arity(n);
 294
 295   for (i = start; i < irn_arity; i++) {
 296     pred = get_irn_n(n, i);
 297     /* Recursion */
 298     if (get_irn_visited(pred) < get_irg_visited(current_ir_graph))
 299       free = _set_out_edges(pred, free);
 300     /* Remember our back edge */
 301     pred->out[get_irn_n_outs(pred)+1] = n;
 302     pred->out[0] = INT_TO_PTR(get_irn_n_outs(pred) + 1);
 303   }
 304   return free;
 305 }
 306
 307 /**
 308  * Enter memory for the outs to a node. Handles special nodes
 309  *
 310  * @param irg    the graph
 311  * @param free   current free address in the chunk allocated for the outs
 312  *
 313  * @return The next free address
 314  */
 315 static ir_node **set_out_edges(ir_graph *irg, ir_node **free) {
 316   ir_node *n, *special[2];
 317   int i, n_outs;
 318
 319   inc_irg_visited(irg);
 320   free = _set_out_edges(get_irg_end(irg), free);
 321
 322   /* handle special nodes */
 323   special[0] = get_irg_frame(irg);
 324   special[1] = get_irg_args(irg);
 325
 326   for (i = 1; i >= 0; --i) {
 327     n = special[i];
 328
 329     if (get_irn_visited(n) < get_irg_visited(current_ir_graph)) {
 330       n_outs = PTR_TO_INT(n->out);
 331       n->out = free;
 332 #ifdef DEBUG_libfirm
 333       n->out_valid = 1;
 334 #endif /* defined DEBUG_libfirm */
 335       free += n_outs;
 336     }
 337   }
 338
 339   return free;
 340 }
 341
 342
 343 /* We want that the out of ProjX from Start contains the next block at
 344    position 1, the Start block at position 2.  This is necessary for
 345    the out block walker. */
 346 static INLINE void fix_start_proj(ir_graph *irg) {
 347   ir_node *proj    = NULL;
 348   ir_node *startbl = get_irg_start_block(irg);
 349   int i;
 350
 351   if (get_Block_n_cfg_outs(startbl)) {
 352     for (i = 0; i < get_irn_n_outs(startbl); i++)
 353       if (get_irn_mode(get_irn_out(startbl, i)) == mode_X) {
 354         proj = get_irn_out(startbl, i);
 355         break;
 356       }
 357
 358     if (get_irn_out(proj, 0) == startbl) {
 359       assert(get_irn_n_outs(proj) == 2);
 360       set_irn_out(proj, 0, get_irn_out(proj, 1));
 361       set_irn_out(proj, 1, startbl);
 362     }
 363   }
 364 }
 365
 366 /* compute the outs for a given graph */
 367 void compute_irg_outs(ir_graph *irg) {
 368   ir_graph *rem = current_ir_graph;
 369   int n_out_edges = 0;
 370   ir_node **end = NULL;         /* Only for debugging */
 371
 372   current_ir_graph = irg;
 373
 374   /* Update graph state */
 375   assert(get_irg_phase_state(current_ir_graph) != phase_building);
 376
 377   if (current_ir_graph->outs_state != outs_none)
 378     free_irg_outs(current_ir_graph);
 379   current_ir_graph->outs_state = outs_consistent;
 380
 381   /* This first iteration counts the overall number of out edges and the
 382      number of out edges for each node. */
 383   n_out_edges = count_outs(irg);
 384
 385   /* allocate memory for all out edges. */
 386   irg->outs = xcalloc(n_out_edges, sizeof(irg->outs[0]));
 387 #ifdef DEBUG_libfirm
 388   irg->n_outs = n_out_edges;
 389 #endif /* defined DEBUG_libfirm */
 390
 391   /* The second iteration splits the irg->outs array into smaller arrays
 392      for each node and writes the back edges into this array. */
 393   end = set_out_edges(irg, irg->outs);
 394
 395   /* Check how much memory we have used */
 396   assert (end == (irg->outs + n_out_edges));
 397
 398   /* We want that the out of ProjX from Start contains the next block at
 399      position 1, the Start block at position 2.  This is necessary for
 400      the out block walker. */
 401   fix_start_proj(irg);
 402
 403   current_ir_graph = rem;
 404 }
 405
 406 void compute_irp_outs(void) {
 407   int i, n_irgs = get_irp_n_irgs();
 408   for (i = 0; i < n_irgs; ++i)
 409     compute_irg_outs(get_irp_irg(i));
 410 }
 411 void free_irp_outs(void) {
 412   int i, n_irgs = get_irp_n_irgs();
 413   for (i = 0; i < n_irgs; ++i)
 414     free_irg_outs(get_irp_irg(i));
 415 }
 416
 417
 418 /*------------------------------------------------------------*
 419  *  This computes the outedges for in interprocedural graph.  *
 420  *  There is one quirk:                                       *
 421  *  The number of the outedges for each node is saved in      *
 422  *  the first member of the ir_node** array. Maybe we should  *
 423  *  change this to make it more portable...                   *
 424  *------------------------------------------------------------*/
 425
 426
 427 /**
 428  * Inits the number of outedges for each node
 429  * before counting.
 430  */
 431 static void init_count(ir_node * node, void *env) {
 432   node->out = (ir_node **) 1; /* 1 for the array size */
 433 }
 434
 435
 436 /**
 437  * Adjusts the out edge count for its predecessors
 438  * and adds the current arity to the overall count,
 439  * which is saved in "env"
 440  */
 441 static void node_arity_count(ir_node * node, void * env)
 442 {
 443   int *anz = (int *) env, arity, n_outs, i, start;
 444   ir_node *succ;
 445
 446   arity = get_irn_arity(node);
 447   start = (is_Block(node)) ? 0 : -1;
 448
 449   n_outs = 1 + arity + (-start);  // ((is_Block(node)) ? 0 : 1);   // Why + 1??
 450   *anz += n_outs;
 451
 452   for(i = start; i < arity; i++) {
 453     succ = get_irn_n(node, i);
 454     succ->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(succ->out) + 1);
 455   }
 456 }
 457
 458
 459 /*
 460  * Inits all nodes for setting the outedges
 461  * Returns the overall count of edges
 462  */
 463 int count_ip_outs(void) {
 464
 465   int res = 0;
 466
 467   cg_walk(init_count, node_arity_count, &res);
 468
 469   return(res);
 470 }
 471
 472 static int dummy_count = 0, global_count; /* Only for debugging */
 473
 474 /**
 475  * For each node: Sets the pointer to array
 476  * in which the outedges are written later.
 477  * The current array start is transported in env
 478  */
 479 static void set_array_pointer(ir_node *node, void *env) {
 480
 481   int n_outs;
 482   ir_node ***free = (ir_node ***) env;
 483
 484   /* Allocate my array */
 485   n_outs = PTR_TO_INT(node->out);  /* We wrote the count here in count_ip_outs */
 486   dummy_count += n_outs;
 487   assert(dummy_count <= global_count && "More outedges than initially counted!");
 488   node -> out = *free;
 489   *free = &((*free)[n_outs]);
 490   /* We count the successors again, the space will be sufficient.
 491      We use this counter to remember the position for the next back
 492      edge. */
 493   node -> out[0] = (ir_node *) 0;
 494 }
 495
 496
 497 /**
 498  * Adds an outedge from the predecessor to the
 499  * current node.
 500  */
 501 static void set_out_pointer(ir_node * node, void * env) {
 502   int i, arity = get_irn_arity(node);
 503   ir_node *succ;
 504   int start = (!is_Block(node)) ? -1 : 0;
 505
 506   for (i = start; i < arity; i++) {
 507     succ = get_irn_n(node, i);
 508     succ->out[get_irn_n_outs(succ)+1] = node;
 509     succ->out[0] = INT_TO_PTR(get_irn_n_outs(succ) + 1);
 510   }
 511 }
 512
 513
 514 /*
 515  * Sets the outedges for all nodes.
 516  */
 517 void set_ip_outs(void)
 518 {
 519   ir_node **outedge_array = get_irp_ip_outedges();
 520   cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
 521 }
 522
 523
 524
 525 /*
 526  * Counts the outedges, allocates memory to save the
 527  * outedges and fills this outedge array in interprocedural
 528  * view!
 529  */
 530 void compute_ip_outs(void) {
 531
 532   int n_out_edges;
 533   ir_node **out_edges;
 534
 535   assert(get_irp_ip_view_state() == ip_view_valid &&
 536      "Cannot construct outs for invalid ip view.");
 537
 538   if (irp->outs_state != outs_none) {
 539     free_ip_outs();
 540   }
 541
 542   global_count = n_out_edges = count_ip_outs();
 543   out_edges = xcalloc(n_out_edges, sizeof(out_edges[0]));
 544   set_irp_ip_outedges(out_edges);
 545   set_ip_outs();
 546 }
 547
 548 void free_ip_outs(void)
 549 {
 550   ir_node **out_edges = get_irp_ip_outedges();
 551   if (out_edges != NULL) {
 552     free(out_edges);
 553     set_irp_ip_outedges(NULL);
 554   }
 555   irp->outs_state = outs_none;
 556 }
 557
 558
 559 void free_irg_outs(ir_graph *irg) {
 560
 561   /*   current_ir_graph->outs_state = outs_none; */
 562   irg->outs_state = outs_none;
 563
 564   if (irg->outs) {
 565 #ifdef DEBUG_libfirm
 566     memset(irg->outs, 0, irg->n_outs);
 567 #endif /* defined DEBUG_libfirm */
 568     free(irg->outs);
 569     irg->outs = NULL;
 570 #ifdef DEBUG_libfirm
 571     irg->n_outs = 0;
 572 #endif /* defined DEBUG_libfirm */
 573   }
 574
 575 #ifdef DEBUG_libfirm
 576   /* when debugging, *always* reset all nodes' outs!  irg->outs might
 577      have been lying to us */
 578   irg_walk_graph (irg, reset_outs, NULL, NULL);
 579 #endif /* defined DEBUG_libfirm */
 580 }