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