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