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   current_ir_graph->outs_state = outs_consistent;
 421
 422   /* This first iteration counts the overall number of out edges and the
 423      number of out edges for each node. */
 424   n_out_edges = count_outs(irg);
 425
 426   /* allocate memory for all out edges. */
 427   irg->outs = xcalloc(n_out_edges, sizeof(irg->outs[0]));
 428 #ifdef DEBUG_libfirm
 429   irg->n_outs = n_out_edges;
 430 #endif /* defined DEBUG_libfirm */
 431
 432   /* The second iteration splits the irg->outs array into smaller arrays
 433      for each node and writes the back edges into this array. */
 434   end = set_out_edges(irg, irg->outs);
 435
 436   /* Check how much memory we have used */
 437   assert (end == (irg->outs + n_out_edges));
 438
 439   /* We want that the out of ProjX from Start contains the next block at
 440      position 1, the Start block at position 2.  This is necessary for
 441      the out block walker. */
 442   fix_start_proj(irg);
 443
 444   current_ir_graph = rem;
 445 }
 446
 447 void compute_irp_outs(void) {
 448   int i, n_irgs = get_irp_n_irgs();
 449   for (i = 0; i < n_irgs; ++i)
 450     compute_irg_outs(get_irp_irg(i));
 451 }
 452 void free_irp_outs(void) {
 453   int i, n_irgs = get_irp_n_irgs();
 454   for (i = 0; i < n_irgs; ++i)
 455     free_irg_outs(get_irp_irg(i));
 456 }
 457
 458
 459 /*------------------------------------------------------------*
 460  *  This computes the outedges for in interprocedural graph.  *
 461  *  There is one quirk:                                       *
 462  *  The number of the outedges for each node is saved in      *
 463  *  the first member of the ir_node** array. Maybe we should  *
 464  *  change this to make it more portable...                   *
 465  *------------------------------------------------------------*/
 466
 467
 468 /**
 469  * Inits the number of outedges for each node
 470  * before counting.
 471  */
 472 static void init_count(ir_node * node, void *env) {
 473   node->out = (ir_node **) 1; /* 1 for the array size */
 474 }
 475
 476
 477 /**
 478  * Adjusts the out edge count for its predecessors
 479  * and adds the current arity to the overall count,
 480  * which is saved in "env"
 481  */
 482 static void node_arity_count(ir_node * node, void * env)
 483 {
 484   int *anz = (int *) env, arity, n_outs, i, start;
 485   ir_node *succ;
 486
 487   arity = get_irn_arity(node);
 488   start = (is_Block(node)) ? 0 : -1;
 489
 490   n_outs = 1 + arity + (-start);  // ((is_Block(node)) ? 0 : 1);   // Why + 1??
 491   *anz += n_outs;
 492
 493   for(i = start; i < arity; i++) {
 494     succ = get_irn_n(node, i);
 495     succ->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(succ->out) + 1);
 496   }
 497 }
 498
 499
 500 /*
 501  * Inits all nodes for setting the outedges
 502  * Returns the overall count of edges
 503  */
 504 int count_ip_outs(void) {
 505
 506   int res = 0;
 507
 508   cg_walk(init_count, node_arity_count, &res);
 509
 510   return(res);
 511 }
 512
 513 static int dummy_count = 0, global_count; /* Only for debugging */
 514
 515 /**
 516  * For each node: Sets the pointer to array
 517  * in which the outedges are written later.
 518  * The current array start is transported in env
 519  */
 520 static void set_array_pointer(ir_node *node, void *env) {
 521
 522   int n_outs;
 523   ir_node ***free = (ir_node ***) env;
 524
 525   /* Allocate my array */
 526   n_outs = PTR_TO_INT(node->out);  /* We wrote the count here in count_ip_outs */
 527   dummy_count += n_outs;
 528   assert(dummy_count <= global_count && "More outedges than initially counted!");
 529   node -> out = *free;
 530   *free = &((*free)[n_outs]);
 531   /* We count the successors again, the space will be sufficient.
 532      We use this counter to remember the position for the next back
 533      edge. */
 534   node -> out[0] = (ir_node *) 0;
 535 }
 536
 537
 538 /**
 539  * Adds an outedge from the predecessor to the
 540  * current node.
 541  */
 542 static void set_out_pointer(ir_node * node, void * env) {
 543   int i, arity = get_irn_arity(node);
 544   ir_node *succ;
 545   int start = (!is_Block(node)) ? -1 : 0;
 546
 547   for (i = start; i < arity; i++) {
 548     succ = get_irn_n(node, i);
 549     succ->out[get_irn_n_outs(succ)+1] = node;
 550     succ->out[0] = INT_TO_PTR(get_irn_n_outs(succ) + 1);
 551   }
 552 }
 553
 554
 555 /*
 556  * Sets the outedges for all nodes.
 557  */
 558 void set_ip_outs(void)
 559 {
 560   ir_node **outedge_array = get_irp_ip_outedges();
 561   cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
 562 }
 563
 564
 565
 566 /*
 567  * Counts the outedges, allocates memory to save the
 568  * outedges and fills this outedge array in interprocedural
 569  * view!
 570  */
 571 void compute_ip_outs(void) {
 572
 573   int n_out_edges;
 574   ir_node **out_edges;
 575
 576   assert(get_irp_ip_view_state() == ip_view_valid &&
 577      "Cannot construct outs for invalid ip view.");
 578
 579   if (irp->outs_state != outs_none) {
 580     free_ip_outs();
 581   }
 582
 583   global_count = n_out_edges = count_ip_outs();
 584   out_edges = xcalloc(n_out_edges, sizeof(out_edges[0]));
 585   set_irp_ip_outedges(out_edges);
 586   set_ip_outs();
 587 }
 588
 589 void free_ip_outs(void)
 590 {
 591   ir_node **out_edges = get_irp_ip_outedges();
 592   if (out_edges != NULL) {
 593     free(out_edges);
 594     set_irp_ip_outedges(NULL);
 595   }
 596   irp->outs_state = outs_none;
 597 }
 598
 599
 600 void free_irg_outs(ir_graph *irg) {
 601
 602   /*   current_ir_graph->outs_state = outs_none; */
 603   irg->outs_state = outs_none;
 604
 605   if (irg->outs) {
 606 #ifdef DEBUG_libfirm
 607     memset(irg->outs, 0, irg->n_outs);
 608 #endif /* defined DEBUG_libfirm */
 609     free(irg->outs);
 610     irg->outs = NULL;
 611 #ifdef DEBUG_libfirm
 612     irg->n_outs = 0;
 613 #endif /* defined DEBUG_libfirm */
 614   }
 615
 616 #ifdef DEBUG_libfirm
 617   /* when debugging, *always* reset all nodes' outs!  irg->outs might
 618      have been lying to us */
 619   irg_walk_graph (irg, reset_outs, NULL, NULL);
 620 #endif /* defined DEBUG_libfirm */
 621 }