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

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