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