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

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