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