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