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 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   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 *pred;
 271
 272   set_irn_visited(n, get_irg_visited(current_ir_graph));
 273
 274   /* Allocate my array */
 275   n_outs = PTR_TO_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     pred = get_irn_n(n, i);
 291     /* Recursion */
 292     if (get_irn_visited(pred) < get_irg_visited(current_ir_graph))
 293       free = _set_out_edges(pred, free);
 294     /* Remember our back edge */
 295     pred->out[get_irn_n_outs(pred)+1] = n;
 296     pred->out[0] = INT_TO_PTR(get_irn_n_outs(pred) + 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 = PTR_TO_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_irg_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_irg_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 void compute_irp_outs(void) {
 394   int i, n_irgs = get_irp_n_irgs();
 395   for (i = 0; i < n_irgs; ++i)
 396     compute_irg_outs(get_irp_irg(i));
 397 }
 398 void free_irp_outs(void) {
 399   int i, n_irgs = get_irp_n_irgs();
 400   for (i = 0; i < n_irgs; ++i)
 401     free_irg_outs(get_irp_irg(i));
 402 }
 403
 404
 405 /*------------------------------------------------------------*
 406  *  This computes the outedges for in interprocedural graph.  *
 407  *  There is one quirk:                                       *
 408  *  The number of the outedges for each node is saved in      *
 409  *  the first member of the ir_node** array. Maybe we should  *
 410  *  change this to make it more portable...                   *
 411  *------------------------------------------------------------*/
 412
 413
 414 /**
 415  * Inits the number of outedges for each node
 416  * before counting.
 417  */
 418 static void init_count(ir_node * node, void *env) {
 419   node->out = (ir_node **) 1; /* 1 for the array size */
 420 }
 421
 422
 423 /**
 424  * Adjusts the out edge count for its predecessors
 425  * and adds the current arity to the overall count,
 426  * which is saved in "env"
 427  */
 428 static void node_arity_count(ir_node * node, void * env)
 429 {
 430   int *anz = (int *) env, arity, n_outs, i, start;
 431   ir_node *succ;
 432
 433   arity = get_irn_arity(node);
 434   start = (is_Block(node)) ? 0 : -1;
 435
 436   n_outs = 1 + arity + (-start);  // ((is_Block(node)) ? 0 : 1);   // Why + 1??
 437   *anz += n_outs;
 438
 439   for(i = start; i < arity; i++) {
 440     succ = get_irn_n(node, i);
 441     succ->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(succ->out) + 1);
 442   }
 443 }
 444
 445
 446 /*
 447  * Inits all nodes for setting the outedges
 448  * Returns the overall count of edges
 449  */
 450 int count_ip_outs(void) {
 451
 452   int res = 0;
 453
 454   cg_walk(init_count, node_arity_count, &res);
 455
 456   return(res);
 457 }
 458
 459 static int dummy_count = 0, global_count; /* Only for debugging */
 460
 461 /**
 462  * For each node: Sets the pointer to array
 463  * in which the outedges are written later.
 464  * The current array start is transported in env
 465  */
 466 static void set_array_pointer(ir_node *node, void *env) {
 467
 468   int n_outs;
 469   ir_node ***free = (ir_node ***) env;
 470
 471   /* Allocate my array */
 472   n_outs = PTR_TO_INT(node->out);  /* We wrote the count here in count_ip_outs */
 473   dummy_count += n_outs;
 474   assert(dummy_count <= global_count && "More outedges than initially counted!");
 475   node -> out = *free;
 476   *free = &((*free)[n_outs]);
 477   /* We count the successors again, the space will be sufficient.
 478      We use this counter to remember the position for the next back
 479      edge. */
 480   node -> out[0] = (ir_node *) 0;
 481 }
 482
 483
 484 /**
 485  * Adds an outedge from the predecessor to the
 486  * current node.
 487  */
 488 static void set_out_pointer(ir_node * node, void * env) {
 489   int i, arity = get_irn_arity(node);
 490   ir_node *succ;
 491   int start = (!is_Block(node)) ? -1 : 0;
 492
 493   for (i = start; i < arity; i++) {
 494     succ = get_irn_n(node, i);
 495     succ->out[get_irn_n_outs(succ)+1] = node;
 496     succ->out[0] = INT_TO_PTR(get_irn_n_outs(succ) + 1);
 497   }
 498 }
 499
 500
 501 /*
 502  * Sets the outedges for all nodes.
 503  */
 504 void set_ip_outs(void)
 505 {
 506   ir_node **outedge_array = get_irp_ip_outedges();
 507   cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
 508 }
 509
 510
 511
 512 /*
 513  * Counts the outedges, allocates memory to save the
 514  * outedges and fills this outedge array in interprocedural
 515  * view!
 516  */
 517 void compute_ip_outs(void) {
 518
 519   int n_out_edges;
 520   ir_node **out_edges;
 521
 522   assert(get_irp_ip_view_state() == ip_view_valid &&
 523      "Cannot construct outs for invalid ip view.");
 524
 525   if (irp->outs_state != outs_none) {
 526     free_ip_outs();
 527   }
 528
 529   global_count = n_out_edges = count_ip_outs();
 530   out_edges = xcalloc(n_out_edges, sizeof(out_edges[0]));
 531   set_irp_ip_outedges(out_edges);
 532   set_ip_outs();
 533 }
 534
 535 void free_ip_outs(void)
 536 {
 537   ir_node **out_edges = get_irp_ip_outedges();
 538   if (out_edges != NULL) {
 539     free(out_edges);
 540     set_irp_ip_outedges(NULL);
 541   }
 542   irp->outs_state = outs_none;
 543 }
 544
 545
 546 void free_irg_outs(ir_graph *irg) {
 547
 548   /*   current_ir_graph->outs_state = outs_none; */
 549   irg->outs_state = outs_none;
 550
 551   if (irg->outs) {
 552 #ifdef DEBUG_libfirm
 553     memset(irg->outs, 0, irg->n_outs);
 554 #endif /* defined DEBUG_libfirm */
 555     free(irg->outs);
 556     irg->outs = NULL;
 557 #ifdef DEBUG_libfirm
 558     irg->n_outs = 0;
 559 #endif /* defined DEBUG_libfirm */
 560   }
 561
 562 #ifdef DEBUG_libfirm
 563   /* when debugging, *always* reset all nodes' outs!  irg->outs might
 564      have been lying to us */
 565   irg_walk_graph (irg, reset_outs, NULL, NULL);
 566 #endif /* defined DEBUG_libfirm */
 567 }