nsz Git - libfirm/blob - ir/ana/irouts.c

   1 /*
   2  * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief    Compute and access out edges (also called def-use edges).
  23  * @author   Goetz Lindenmaier, Michael Beck
  24  * @date     1.2002
  25  * @version  $Id$
  26  */
  27 #ifdef HAVE_CONFIG_H
  28 #include "config.h"
  29 #endif
  30
  31 #ifdef HAVE_STRING_H
  32 #include <string.h>
  33 #endif
  34
  35 #include "xmalloc.h"
  36 #include "irouts.h"
  37 #include "irnode_t.h"
  38 #include "irgraph_t.h"
  39 #include "irprog_t.h"
  40 #include "irgwalk.h"
  41 #include "irtools.h"
  42
  43 #ifdef DEBUG_libfirm
  44 /* Note:  ir_node.out_valid and ir_graph.n_outs are only present when DEBUG_libfirm is defined */
  45 /* Accesses to out_valid and n_outs are fenced out to avoid breakage
  46    when compiling with neither DEBUG_libfirm or NDEBUG defined */
  47 #endif /* defined DEBUG_libfirm */
  48
  49 /*--------------------------------------------------------------------*/
  50 /** Accessing the out datastructures                                 **/
  51 /*--------------------------------------------------------------------*/
  52
  53 #ifdef DEBUG_libfirm
  54 /** Clear the outs of a node */
  55 static void reset_outs(ir_node *node, void *unused) {
  56         (void) unused;
  57         node->out       = NULL;
  58         node->out_valid = 0;
  59 }
  60 #endif
  61
  62 /* returns the number of successors of the node: */
  63 int get_irn_n_outs(ir_node *node) {
  64         assert(node && node->kind == k_ir_node);
  65 #ifdef DEBUG_libfirm
  66         /* assert(node->out_valid); */
  67 #endif /* defined DEBUG_libfirm */
  68         return PTR_TO_INT(node->out[0]);
  69 }
  70
  71 /* Access successor n */
  72 ir_node *get_irn_out(ir_node *node, int pos) {
  73         assert(pos >= 0 && pos < get_irn_n_outs(node));
  74 #ifdef DEBUG_libfirm
  75         /* assert(node->out_valid); */
  76 #endif /* defined DEBUG_libfirm */
  77 return node->out[pos+1];
  78 }
  79
  80 void set_irn_out(ir_node *node, int pos, ir_node *out) {
  81         assert(node && out);
  82         assert(pos >= 0 && pos < get_irn_n_outs(node));
  83 #ifdef DEBUG_libfirm
  84         node->out_valid = 1;          /* assume that this function is used correctly */
  85 #endif /* defined DEBUG_libfirm */
  86         node->out[pos+1] = out;
  87 }
  88
  89 /* Return the number of control flow successors, ignore keep-alives. */
  90 int get_Block_n_cfg_outs(ir_node *bl) {
  91         int i, n_cfg_outs = 0;
  92         assert(bl && is_Block(bl));
  93 #ifdef DEBUG_libfirm
  94         assert(bl->out_valid);
  95 #endif /* defined DEBUG_libfirm */
  96   for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i) {
  97     ir_node *succ = bl->out[i];
  98                 if (get_irn_mode(succ) == mode_X && get_irn_op(succ) != op_End)
  99                         n_cfg_outs += PTR_TO_INT(succ->out[0]);
 100   }
 101         return n_cfg_outs;
 102 }
 103
 104 /* Return the number of control flow successors, honor keep-alives. */
 105 int get_Block_n_cfg_outs_ka(ir_node *bl) {
 106         int i, n_cfg_outs = 0;
 107         assert(bl && is_Block(bl));
 108 #ifdef DEBUG_libfirm
 109         assert(bl->out_valid);
 110 #endif /* defined DEBUG_libfirm */
 111   for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i) {
 112     ir_node *succ = bl->out[i];
 113                 if (get_irn_mode(succ) == mode_X) {
 114                         /* ignore End if we are in the Endblock */
 115                         if (get_irn_op(succ) == op_End &&
 116                             get_irn_n(succ, -1) == bl)
 117                                 continue;
 118                         else
 119                                 n_cfg_outs += PTR_TO_INT(succ->out[0]);
 120                 }
 121   }
 122         return n_cfg_outs;
 123 }
 124
 125 /* Access predecessor n, ignore keep-alives. */
 126 ir_node *get_Block_cfg_out(ir_node *bl, int pos) {
 127         int i;
 128         assert(bl && is_Block(bl));
 129 #ifdef DEBUG_libfirm
 130         assert (bl->out_valid);
 131 #endif /* defined DEBUG_libfirm */
 132   for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i) {
 133     ir_node *succ = bl->out[i];
 134                 if (get_irn_mode(succ) == mode_X  && get_irn_op(succ) != op_End) {
 135       int n_outs = PTR_TO_INT(succ->out[0]);
 136                         if (pos < n_outs)
 137                                 return succ->out[pos + 1];
 138                         else
 139                                 pos -= n_outs;
 140                 }
 141   }
 142         return NULL;
 143 }
 144
 145 /* Access predecessor n, honor keep-alives. */
 146 ir_node *get_Block_cfg_out_ka(ir_node *bl, int pos) {
 147         int i, n_outs;
 148         assert(bl && is_Block(bl));
 149 #ifdef DEBUG_libfirm
 150         assert (bl->out_valid);
 151 #endif /* defined DEBUG_libfirm */
 152   for (i = 1; i <= PTR_TO_INT(bl->out[0]); ++i) {
 153                 ir_node *succ = bl->out[i];
 154     if (get_irn_mode(succ) == mode_X) {
 155                         /* ignore End if we are in the Endblock */
 156                         if (get_irn_op(succ) == op_End &&       get_irn_n(succ, -1) == bl)
 157                                 continue;
 158       n_outs = PTR_TO_INT(succ->out[0]);
 159                         if (pos < n_outs) {
 160                                 /* handle keep-alive here: return the Endblock instead of the End node */
 161                                 if (get_irn_op(succ) == op_End)
 162                                         return get_irn_n(succ, -1);
 163                                 return succ->out[pos + 1];
 164                         } else
 165                                 pos -= n_outs;
 166                 }
 167   }
 168         return NULL;
 169 }
 170
 171 static void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
 172             irg_walk_func *post, void *env) {
 173         int     i, n;
 174         ir_node *succ;
 175
 176         assert(node);
 177         assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
 178
 179         set_irn_visited(node, get_irg_visited(current_ir_graph));
 180
 181         if (pre) pre(node, env);
 182
 183         for (i = 0, n = get_irn_n_outs(node); i < n; ++i) {
 184                 succ = get_irn_out(node, i);
 185                 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
 186                         irg_out_walk_2(succ, pre, post, env);
 187         }
 188
 189         if (post) post(node, env);
 190
 191         return;
 192 }
 193
 194 void irg_out_walk(ir_node *node,
 195                   irg_walk_func *pre, irg_walk_func *post,
 196                   void *env) {
 197         assert(node);
 198         if (get_irg_outs_state(current_ir_graph) != outs_none) {
 199                 inc_irg_visited (current_ir_graph);
 200                 irg_out_walk_2(node, pre, post, env);
 201         }
 202         return;
 203 }
 204
 205 static void irg_out_block_walk2(ir_node *bl,
 206                                 irg_walk_func *pre, irg_walk_func *post,
 207                                 void *env) {
 208         int i, n;
 209
 210         if (Block_not_block_visited(bl)) {
 211                 mark_Block_block_visited(bl);
 212
 213                 if (pre)
 214                         pre(bl, env);
 215
 216                 for (i = 0, n =  get_Block_n_cfg_outs(bl); i < n; ++i) {
 217                         /* find the corresponding predecessor block. */
 218                         ir_node *pred = get_Block_cfg_out(bl, i);
 219                         /* recursion */
 220                         irg_out_block_walk2(pred, pre, post, env);
 221                 }
 222
 223                 if (post)
 224                         post(bl, env);
 225         }
 226 }
 227
 228 /* Walks only over Block nodes in the graph.  Has it's own visited
 229    flag, so that it can be interleaved with the other walker.         */
 230 void irg_out_block_walk(ir_node *node,
 231                         irg_walk_func *pre, irg_walk_func *post,
 232                         void *env) {
 233
 234         assert(is_Block(node) || (get_irn_mode(node) == mode_X));
 235
 236         inc_irg_block_visited(current_ir_graph);
 237
 238   if (get_irn_mode(node) == mode_X) {
 239     int i, n;
 240
 241           for (i = 0, n = get_irn_n_outs(node); i < n; ++i) {
 242                   ir_node *succ = get_irn_out(node, i);
 243                   if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
 244                           irg_out_walk_2(succ, pre, post, env);
 245           }
 246   }
 247   else {
 248           irg_out_block_walk2(node, pre, post, env);
 249   }
 250 }
 251
 252 /*--------------------------------------------------------------------*/
 253 /** Building and Removing the out datastructure                      **/
 254 /**                                                                  **/
 255 /** The outs of a graph are allocated in a single, large array.      **/
 256 /** This allows to allocate and deallocate the memory for the outs   **/
 257 /** on demand.  The large array is separated into many small ones    **/
 258 /** for each node.  Only a single field to reference the out array   **/
 259 /** is stored in each node and a field referencing the large out     **/
 260 /** array in irgraph.  The 0 field of each out array contains the    **/
 261 /** size of this array.  This saves memory in the irnodes themselves.**/
 262 /** The construction does two passes over the graph.  The first pass **/
 263 /** counts the overall number of outs and the outs of each node.  It **/
 264 /** stores the outs of each node in the out reference of the node.   **/
 265 /** Then the large array is allocated.  The second iteration chops   **/
 266 /** the large array into smaller parts, sets the out edges and       **/
 267 /** recounts the out edges.                                          **/
 268 /** Removes Tuple nodes!                                             **/
 269 /*--------------------------------------------------------------------*/
 270
 271
 272 /** Returns the amount of out edges for not yet visited successors. */
 273 static int _count_outs(ir_node *n) {
 274         int start, i, res, irn_arity;
 275
 276         mark_irn_visited(n);
 277         n->out = (ir_node **) 1;     /* Space for array size. */
 278
 279         start = is_Block(n) ? 0 : -1;
 280         irn_arity = get_irn_arity(n);
 281         res = irn_arity - start + 1;  /* --1 or --0; 1 for array size. */
 282
 283         for (i = start; i < irn_arity; ++i) {
 284                 /* Optimize Tuples.  They annoy if walking the cfg. */
 285                 ir_node *pred = skip_Tuple(get_irn_n(n, i));
 286                 set_irn_n(n, i, pred);
 287
 288                 /* count outs for successors */
 289                 if (irn_not_visited(pred))
 290                         res += _count_outs(pred);
 291
 292                 /* Count my outs */
 293                 pred->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(pred->out) + 1);
 294         }
 295         return res;
 296 }
 297
 298
 299 /** Returns the amount of out edges for not yet visited successors.
 300  *  This version handles some special nodes like irg_frame, irg_args etc.
 301  */
 302 static int count_outs(ir_graph *irg) {
 303         ir_node *n;
 304         int res;
 305
 306         inc_irg_visited(irg);
 307         res = _count_outs(get_irg_end(irg));
 308
 309         /* now handle special nodes */
 310         n = get_irg_frame(irg);
 311         if (irn_not_visited(n)) {
 312                 n->out = (ir_node **)1;
 313                 ++res;
 314         }
 315
 316         n = get_irg_args(irg);
 317         if (irn_not_visited(n)) {
 318                 n->out = (ir_node **)1;
 319                 ++res;
 320         }
 321
 322         return res;
 323 }
 324
 325 /**
 326  * Enter memory for the outs to a node.
 327  *
 328  * @param n      current node
 329  * @param free   current free address in the chunk allocated for the outs
 330  *
 331  * @return The next free address
 332  */
 333 static ir_node **_set_out_edges(ir_node *n, ir_node **free) {
 334         int n_outs, start, i, irn_arity;
 335         ir_node *pred;
 336
 337         set_irn_visited(n, get_irg_visited(current_ir_graph));
 338
 339         /* Allocate my array */
 340         n_outs = PTR_TO_INT(n->out);
 341         n->out = free;
 342 #ifdef DEBUG_libfirm
 343         n->out_valid = 1;
 344 #endif /* defined DEBUG_libfirm */
 345         free += n_outs;
 346         /* We count the successors again, the space will be sufficient.
 347            We use this counter to remember the position for the next back
 348            edge. */
 349         n->out[0] = (ir_node *)0;
 350
 351         start = is_Block(n) ? 0 : -1;
 352         irn_arity = get_irn_arity(n);
 353
 354         for (i = start; i < irn_arity; ++i) {
 355                 pred = get_irn_n(n, i);
 356                 /* Recursion */
 357                 if (get_irn_visited(pred) < get_irg_visited(current_ir_graph))
 358                         free = _set_out_edges(pred, free);
 359                 /* Remember our back edge */
 360                 pred->out[get_irn_n_outs(pred)+1] = n;
 361                 pred->out[0] = INT_TO_PTR(get_irn_n_outs(pred) + 1);
 362         }
 363         return free;
 364 }
 365
 366 /**
 367  * Enter memory for the outs to a node. Handles special nodes
 368  *
 369  * @param irg    the graph
 370  * @param free   current free address in the chunk allocated for the outs
 371  *
 372  * @return The next free address
 373  */
 374 static ir_node **set_out_edges(ir_graph *irg, ir_node **free) {
 375         ir_node *n, *special[2];
 376         int i, n_outs;
 377
 378         inc_irg_visited(irg);
 379         free = _set_out_edges(get_irg_end(irg), free);
 380
 381         /* handle special nodes */
 382         special[0] = get_irg_frame(irg);
 383         special[1] = get_irg_args(irg);
 384
 385         for (i = 1; i >= 0; --i) {
 386                 n = special[i];
 387
 388                 if (get_irn_visited(n) < get_irg_visited(current_ir_graph)) {
 389                         n_outs = PTR_TO_INT(n->out);
 390                         n->out = free;
 391 #ifdef DEBUG_libfirm
 392                         n->out_valid = 1;
 393 #endif /* defined DEBUG_libfirm */
 394                         free += n_outs;
 395                 }
 396         }
 397
 398         return free;
 399 }
 400
 401
 402 /**
 403  * We want that the out of ProjX from Start contains the next block at
 404  * position 1, the Start block at position 2.  This is necessary for
 405  * the out block walker.
 406  */
 407 static INLINE void fix_start_proj(ir_graph *irg) {
 408         ir_node *proj    = NULL;
 409         ir_node *startbl = get_irg_start_block(irg);
 410         int i;
 411
 412         if (get_Block_n_cfg_outs(startbl)) {
 413                 for (i = get_irn_n_outs(startbl) - 1; i >= 0; --i)
 414                         if (get_irn_mode(get_irn_out(startbl, i)) == mode_X) {
 415                                 proj = get_irn_out(startbl, i);
 416                                 break;
 417                         }
 418
 419                 if (get_irn_out(proj, 0) == startbl) {
 420                         assert(get_irn_n_outs(proj) == 2);
 421                         set_irn_out(proj, 0, get_irn_out(proj, 1));
 422                         set_irn_out(proj, 1, startbl);
 423                 }
 424         }
 425 }
 426
 427 /* compute the outs for a given graph */
 428 void compute_irg_outs(ir_graph *irg) {
 429         ir_graph *rem = current_ir_graph;
 430         int n_out_edges = 0;
 431         ir_node **end = NULL;         /* Only for debugging */
 432
 433         current_ir_graph = irg;
 434
 435         /* Update graph state */
 436         assert(get_irg_phase_state(current_ir_graph) != phase_building);
 437
 438         if (current_ir_graph->outs_state != outs_none)
 439                 free_irg_outs(current_ir_graph);
 440
 441         /* This first iteration counts the overall number of out edges and the
 442            number of out edges for each node. */
 443         n_out_edges = count_outs(irg);
 444
 445         /* allocate memory for all out edges. */
 446         irg->outs = xcalloc(n_out_edges, sizeof(irg->outs[0]));
 447 #ifdef DEBUG_libfirm
 448         irg->n_outs = n_out_edges;
 449 #endif /* defined DEBUG_libfirm */
 450
 451         /* The second iteration splits the irg->outs array into smaller arrays
 452            for each node and writes the back edges into this array. */
 453         end = set_out_edges(irg, irg->outs);
 454
 455         /* Check how much memory we have used */
 456         assert (end == (irg->outs + n_out_edges));
 457
 458         /* We want that the out of ProjX from Start contains the next block at
 459            position 1, the Start block at position 2.  This is necessary for
 460            the out block walker. */
 461         fix_start_proj(irg);
 462
 463         current_ir_graph->outs_state = outs_consistent;
 464         current_ir_graph = rem;
 465 }
 466
 467 void assure_irg_outs(ir_graph *irg) {
 468         if (get_irg_outs_state(irg) != outs_consistent)
 469                 compute_irg_outs(irg);
 470 }
 471
 472 void compute_irp_outs(void) {
 473         int i;
 474         for (i = get_irp_n_irgs() -1; i >= 0; --i)
 475                 compute_irg_outs(get_irp_irg(i));
 476 }
 477
 478 void free_irp_outs(void) {
 479         int i;
 480         for (i = get_irp_n_irgs() -1; i >= 0; --i)
 481                 free_irg_outs(get_irp_irg(i));
 482 }
 483
 484
 485 /*------------------------------------------------------------*
 486  *  This computes the outedges for in interprocedural graph.  *
 487  *  There is one quirk:                                       *
 488  *  The number of the outedges for each node is saved in      *
 489  *  the first member of the ir_node** array. Maybe we should  *
 490  *  change this to make it more portable...                   *
 491  *------------------------------------------------------------*/
 492
 493
 494 /**
 495  * Inits the number of outedges for each node
 496  * before counting.
 497  */
 498 static void init_count(ir_node * node, void *env) {
 499         (void) env;
 500         node->out = (ir_node **) 1; /* 1 for the array size */
 501 }
 502
 503
 504 /**
 505  * Adjusts the out edge count for its predecessors
 506  * and adds the current arity to the overall count,
 507  * which is saved in "env"
 508  */
 509 static void node_arity_count(ir_node * node, void * env) {
 510         int *anz = (int *) env, arity, n_outs, i, start;
 511         ir_node *succ;
 512
 513         arity = get_irn_arity(node);
 514         start = (is_Block(node)) ? 0 : -1;
 515
 516         n_outs = 1 + arity + (-start);  // ((is_Block(node)) ? 0 : 1);   // Why + 1??
 517         *anz += n_outs;
 518
 519         for(i = start; i < arity; i++) {
 520                 succ = get_irn_n(node, i);
 521                 succ->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(succ->out) + 1);
 522         }
 523 }
 524
 525
 526 /*
 527  * Inits all nodes for setting the outedges
 528  * Returns the overall count of edges
 529  */
 530 int count_ip_outs(void) {
 531         int res = 0;
 532
 533         cg_walk(init_count, node_arity_count, &res);
 534
 535         return(res);
 536 }
 537
 538 static int dummy_count = 0, global_count; /* Only for debugging */
 539
 540 /**
 541  * For each node: Sets the pointer to array
 542  * in which the outedges are written later.
 543  * The current array start is transported in env
 544  */
 545 static void set_array_pointer(ir_node *node, void *env) {
 546         int n_outs;
 547         ir_node ***free = (ir_node ***) env;
 548
 549         /* Allocate my array */
 550         n_outs = PTR_TO_INT(node->out);  /* We wrote the count here in count_ip_outs */
 551         dummy_count += n_outs;
 552         assert(dummy_count <= global_count && "More outedges than initially counted!");
 553         node -> out = *free;
 554         *free = &((*free)[n_outs]);
 555         /* We count the successors again, the space will be sufficient.
 556            We use this counter to remember the position for the next back
 557            edge. */
 558         node -> out[0] = (ir_node *) 0;
 559 }
 560
 561
 562 /**
 563  * Adds an outedge from the predecessor to the
 564  * current node.
 565  */
 566 static void set_out_pointer(ir_node * node, void *env) {
 567         int i, arity = get_irn_arity(node);
 568         ir_node *succ;
 569         int start = (!is_Block(node)) ? -1 : 0;
 570         (void) env;
 571
 572         for (i = start; i < arity; ++i) {
 573                 succ = get_irn_n(node, i);
 574                 succ->out[get_irn_n_outs(succ)+1] = node;
 575                 succ->out[0] = INT_TO_PTR(get_irn_n_outs(succ) + 1);
 576         }
 577 }
 578
 579
 580 /*
 581  * Sets the outedges for all nodes.
 582  */
 583 void set_ip_outs(void) {
 584         ir_node **outedge_array = get_irp_ip_outedges();
 585         cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
 586 }
 587
 588
 589
 590 /*
 591  * Counts the outedges, allocates memory to save the
 592  * outedges and fills this outedge array in interprocedural
 593  * view!
 594  */
 595 void compute_ip_outs(void) {
 596         int n_out_edges;
 597         ir_node **out_edges;
 598
 599         assert(get_irp_ip_view_state() == ip_view_valid &&
 600          "Cannot construct outs for invalid ip view.");
 601
 602         if (irp->outs_state != outs_none) {
 603                 free_ip_outs();
 604         }
 605
 606         global_count = n_out_edges = count_ip_outs();
 607         out_edges = xcalloc(n_out_edges, sizeof(out_edges[0]));
 608         set_irp_ip_outedges(out_edges);
 609         set_ip_outs();
 610 }
 611
 612 void free_ip_outs(void) {
 613         ir_node **out_edges = get_irp_ip_outedges();
 614         if (out_edges != NULL) {
 615                 free(out_edges);
 616                 set_irp_ip_outedges(NULL);
 617         }
 618         irp->outs_state = outs_none;
 619 }
 620
 621
 622 void free_irg_outs(ir_graph *irg) {
 623         /*   current_ir_graph->outs_state = outs_none; */
 624         irg->outs_state = outs_none;
 625
 626         if (irg->outs) {
 627 #ifdef DEBUG_libfirm
 628                 memset(irg->outs, 0, irg->n_outs);
 629 #endif /* defined DEBUG_libfirm */
 630                 free(irg->outs);
 631                 irg->outs = NULL;
 632 #ifdef DEBUG_libfirm
 633                 irg->n_outs = 0;
 634 #endif /* defined DEBUG_libfirm */
 635         }
 636
 637 #ifdef DEBUG_libfirm
 638         /* when debugging, *always* reset all nodes' outs!  irg->outs might
 639            have been lying to us */
 640         irg_walk_graph (irg, reset_outs, NULL, NULL);
 641 #endif /* defined DEBUG_libfirm */
 642 }