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
 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 */
 319         n = get_irg_frame(irg);
 320         if (irn_not_visited(n)) {
 321                 n->out = (ir_node **)1;
 322                 ++res;
 323         }
 324
 325         n = get_irg_args(irg);
 326         if (irn_not_visited(n)) {
 327                 n->out = (ir_node **)1;
 328                 ++res;
 329         }
 330
 331         return res;
 332 }
 333
 334 /**
 335  * Enter memory for the outs to a node.
 336  *
 337  * @param n      current node
 338  * @param free   current free address in the chunk allocated for the outs
 339  *
 340  * @return The next free address
 341  */
 342 static ir_node **_set_out_edges(ir_node *n, ir_node **free) {
 343         int n_outs, start, i, irn_arity;
 344         ir_node *pred;
 345
 346         set_irn_visited(n, get_irg_visited(current_ir_graph));
 347
 348         /* Allocate my array */
 349         n_outs = PTR_TO_INT(n->out);
 350         n->out = free;
 351 #ifdef DEBUG_libfirm
 352         n->out_valid = 1;
 353 #endif /* defined DEBUG_libfirm */
 354         free += n_outs;
 355         /* We count the successors again, the space will be sufficient.
 356            We use this counter to remember the position for the next back
 357            edge. */
 358         n->out[0] = (ir_node *)0;
 359
 360         start = is_Block(n) ? 0 : -1;
 361         irn_arity = get_irn_arity(n);
 362
 363         for (i = start; i < irn_arity; ++i) {
 364                 pred = get_irn_n(n, i);
 365                 /* Recursion */
 366                 if (get_irn_visited(pred) < get_irg_visited(current_ir_graph))
 367                         free = _set_out_edges(pred, free);
 368                 /* Remember our back edge */
 369                 pred->out[get_irn_n_outs(pred)+1] = n;
 370                 pred->out[0] = INT_TO_PTR(get_irn_n_outs(pred) + 1);
 371         }
 372         return free;
 373 }
 374
 375 /**
 376  * Enter memory for the outs to a node. Handles special nodes
 377  *
 378  * @param irg    the graph
 379  * @param free   current free address in the chunk allocated for the outs
 380  *
 381  * @return The next free address
 382  */
 383 static ir_node **set_out_edges(ir_graph *irg, ir_node **free) {
 384         ir_node *n, *special[2];
 385         int i, n_outs;
 386
 387         inc_irg_visited(irg);
 388         free = _set_out_edges(get_irg_end(irg), free);
 389
 390         /* handle special nodes */
 391         special[0] = get_irg_frame(irg);
 392         special[1] = get_irg_args(irg);
 393
 394         for (i = 1; i >= 0; --i) {
 395                 n = special[i];
 396
 397                 if (get_irn_visited(n) < get_irg_visited(current_ir_graph)) {
 398                         n_outs = PTR_TO_INT(n->out);
 399                         n->out = free;
 400 #ifdef DEBUG_libfirm
 401                         n->out_valid = 1;
 402 #endif /* defined DEBUG_libfirm */
 403                         free += n_outs;
 404                 }
 405         }
 406
 407         return free;
 408 }
 409
 410
 411 /**
 412  * We want that the out of ProjX from Start contains the next block at
 413  * position 1, the Start block at position 2.  This is necessary for
 414  * the out block walker.
 415  */
 416 static INLINE void fix_start_proj(ir_graph *irg) {
 417         ir_node *proj    = NULL;
 418         ir_node *startbl = get_irg_start_block(irg);
 419         int i;
 420
 421         if (get_Block_n_cfg_outs(startbl)) {
 422                 for (i = get_irn_n_outs(startbl) - 1; i >= 0; --i)
 423                         if (get_irn_mode(get_irn_out(startbl, i)) == mode_X) {
 424                                 proj = get_irn_out(startbl, i);
 425                                 break;
 426                         }
 427
 428                 if (get_irn_out(proj, 0) == startbl) {
 429                         assert(get_irn_n_outs(proj) == 2);
 430                         set_irn_out(proj, 0, get_irn_out(proj, 1));
 431                         set_irn_out(proj, 1, startbl);
 432                 }
 433         }
 434 }
 435
 436 /* compute the outs for a given graph */
 437 void compute_irg_outs(ir_graph *irg) {
 438         ir_graph *rem = current_ir_graph;
 439         int n_out_edges = 0;
 440         ir_node **end = NULL;         /* Only for debugging */
 441
 442         current_ir_graph = irg;
 443
 444         /* Update graph state */
 445         assert(get_irg_phase_state(current_ir_graph) != phase_building);
 446
 447         if (current_ir_graph->outs_state != outs_none)
 448                 free_irg_outs(current_ir_graph);
 449
 450         /* This first iteration counts the overall number of out edges and the
 451            number of out edges for each node. */
 452         n_out_edges = count_outs(irg);
 453
 454         /* allocate memory for all out edges. */
 455         irg->outs = xcalloc(n_out_edges, sizeof(irg->outs[0]));
 456 #ifdef DEBUG_libfirm
 457         irg->n_outs = n_out_edges;
 458 #endif /* defined DEBUG_libfirm */
 459
 460         /* The second iteration splits the irg->outs array into smaller arrays
 461            for each node and writes the back edges into this array. */
 462         end = set_out_edges(irg, irg->outs);
 463
 464         /* Check how much memory we have used */
 465         assert (end == (irg->outs + n_out_edges));
 466
 467         /* We want that the out of ProjX from Start contains the next block at
 468            position 1, the Start block at position 2.  This is necessary for
 469            the out block walker. */
 470         fix_start_proj(irg);
 471
 472         current_ir_graph->outs_state = outs_consistent;
 473         current_ir_graph = rem;
 474 }
 475
 476 void assure_irg_outs(ir_graph *irg) {
 477         if (get_irg_outs_state(irg) != outs_consistent)
 478                 compute_irg_outs(irg);
 479 }
 480
 481 void compute_irp_outs(void) {
 482         int i;
 483         for (i = get_irp_n_irgs() -1; i >= 0; --i)
 484                 compute_irg_outs(get_irp_irg(i));
 485 }
 486
 487 void free_irp_outs(void) {
 488         int i;
 489         for (i = get_irp_n_irgs() -1; i >= 0; --i)
 490                 free_irg_outs(get_irp_irg(i));
 491 }
 492
 493
 494 /*------------------------------------------------------------*
 495  *  This computes the outedges for in interprocedural graph.  *
 496  *  There is one quirk:                                       *
 497  *  The number of the outedges for each node is saved in      *
 498  *  the first member of the ir_node** array. Maybe we should  *
 499  *  change this to make it more portable...                   *
 500  *------------------------------------------------------------*/
 501
 502
 503 /**
 504  * Inits the number of outedges for each node
 505  * before counting.
 506  */
 507 static void init_count(ir_node * node, void *env) {
 508         (void) env;
 509         node->out = (ir_node **) 1; /* 1 for the array size */
 510 }
 511
 512
 513 /**
 514  * Adjusts the out edge count for its predecessors
 515  * and adds the current arity to the overall count,
 516  * which is saved in "env"
 517  */
 518 static void node_arity_count(ir_node * node, void * env) {
 519         int *anz = (int *) env, arity, n_outs, i, start;
 520         ir_node *succ;
 521
 522         arity = get_irn_arity(node);
 523         start = (is_Block(node)) ? 0 : -1;
 524
 525         n_outs = 1 + arity + (-start);  // ((is_Block(node)) ? 0 : 1);   // Why + 1??
 526         *anz += n_outs;
 527
 528         for(i = start; i < arity; i++) {
 529                 succ = get_irn_n(node, i);
 530                 succ->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(succ->out) + 1);
 531         }
 532 }
 533
 534
 535 /*
 536  * Inits all nodes for setting the outedges
 537  * Returns the overall count of edges
 538  */
 539 int count_ip_outs(void) {
 540         int res = 0;
 541
 542         cg_walk(init_count, node_arity_count, &res);
 543
 544         return(res);
 545 }
 546
 547 static int dummy_count = 0, global_count; /* Only for debugging */
 548
 549 /**
 550  * For each node: Sets the pointer to array
 551  * in which the outedges are written later.
 552  * The current array start is transported in env
 553  */
 554 static void set_array_pointer(ir_node *node, void *env) {
 555         int n_outs;
 556         ir_node ***free = (ir_node ***) env;
 557
 558         /* Allocate my array */
 559         n_outs = PTR_TO_INT(node->out);  /* We wrote the count here in count_ip_outs */
 560         dummy_count += n_outs;
 561         assert(dummy_count <= global_count && "More outedges than initially counted!");
 562         node -> out = *free;
 563         *free = &((*free)[n_outs]);
 564         /* We count the successors again, the space will be sufficient.
 565            We use this counter to remember the position for the next back
 566            edge. */
 567         node -> out[0] = (ir_node *) 0;
 568 }
 569
 570
 571 /**
 572  * Adds an outedge from the predecessor to the
 573  * current node.
 574  */
 575 static void set_out_pointer(ir_node * node, void *env) {
 576         int i, arity = get_irn_arity(node);
 577         ir_node *succ;
 578         int start = (!is_Block(node)) ? -1 : 0;
 579         (void) env;
 580
 581         for (i = start; i < arity; ++i) {
 582                 succ = get_irn_n(node, i);
 583                 succ->out[get_irn_n_outs(succ)+1] = node;
 584                 succ->out[0] = INT_TO_PTR(get_irn_n_outs(succ) + 1);
 585         }
 586 }
 587
 588
 589 /*
 590  * Sets the outedges for all nodes.
 591  */
 592 void set_ip_outs(void) {
 593         ir_node **outedge_array = get_irp_ip_outedges();
 594         cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
 595 }
 596
 597
 598
 599 /*
 600  * Counts the outedges, allocates memory to save the
 601  * outedges and fills this outedge array in interprocedural
 602  * view!
 603  */
 604 void compute_ip_outs(void) {
 605         int n_out_edges;
 606         ir_node **out_edges;
 607
 608         assert(get_irp_ip_view_state() == ip_view_valid &&
 609          "Cannot construct outs for invalid ip view.");
 610
 611         if (irp->outs_state != outs_none) {
 612                 free_ip_outs();
 613         }
 614
 615         global_count = n_out_edges = count_ip_outs();
 616         out_edges = xcalloc(n_out_edges, sizeof(out_edges[0]));
 617         set_irp_ip_outedges(out_edges);
 618         set_ip_outs();
 619 }
 620
 621 void free_ip_outs(void) {
 622         ir_node **out_edges = get_irp_ip_outedges();
 623         if (out_edges != NULL) {
 624                 free(out_edges);
 625                 set_irp_ip_outedges(NULL);
 626         }
 627         irp->outs_state = outs_none;
 628 }
 629
 630
 631 void free_irg_outs(ir_graph *irg) {
 632         /*   current_ir_graph->outs_state = outs_none; */
 633         irg->outs_state = outs_none;
 634
 635         if (irg->outs) {
 636 #ifdef DEBUG_libfirm
 637                 memset(irg->outs, 0, irg->n_outs);
 638 #endif /* defined DEBUG_libfirm */
 639                 free(irg->outs);
 640                 irg->outs = NULL;
 641 #ifdef DEBUG_libfirm
 642                 irg->n_outs = 0;
 643 #endif /* defined DEBUG_libfirm */
 644         }
 645
 646 #ifdef DEBUG_libfirm
 647         /* when debugging, *always* reset all nodes' outs!  irg->outs might
 648            have been lying to us */
 649         irg_walk_graph (irg, reset_outs, NULL, NULL);
 650 #endif /* defined DEBUG_libfirm */
 651 }