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