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

   1 /*
   2  * Copyright (C) 1995-2008 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 the strongly connected regions and build
  23  *              backedge/loop datastructures.
  24  *              A variation on the Tarjan algorithm. See also [Trapp:99],
  25  *              Chapter 5.2.1.2.
  26  * @author   Goetz Lindenmaier
  27  * @date     7.2002
  28  * @version  $Id$
  29  */
  30 #include "config.h"
  31
  32 #include <string.h>
  33 #include <stdlib.h>
  34
  35 #include "irloop_t.h"
  36
  37 #include "irprog_t.h"
  38 #include "irgraph_t.h"
  39 #include "irnode_t.h"
  40 #include "irgwalk.h"
  41 #include "irdump.h"
  42 #include "array.h"
  43 #include "pmap.h"
  44
  45 /* A variant of the loop tree that avoids loops without head.
  46    This reduces the depth of the loop tree. */
  47 #define NO_LOOPS_WITHOUT_HEAD 1
  48
  49 /** The outermost graph the scc is computed for. */
  50 static ir_graph *outermost_ir_graph;
  51 /** Current loop construction is working on. */
  52 static ir_loop *current_loop;
  53 /** Counts the number of allocated loop nodes.
  54  *  Each loop node gets a unique number.
  55  *  @todo What for? ev. remove.
  56  */
  57 static int loop_node_cnt = 0;
  58 /** Counter to generate depth first numbering of visited nodes. */
  59 static int current_dfn = 1;
  60
  61 static int max_loop_depth = 0;
  62
  63 void link_to_reg_end(ir_node *n, void *env);
  64 void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
  65 ir_node *get_projx_link(ir_node *cb_projx);
  66
  67 /**********************************************************************/
  68 /* Node attributes                                                   **/
  69 /**********************************************************************/
  70
  71 /**********************************************************************/
  72 /* Node attributes needed for the construction.                      **/
  73 /**********************************************************************/
  74
  75 typedef struct scc_info {
  76         int in_stack;          /**< Marks whether node is on the stack. */
  77         int dfn;               /**< Depth first search number. */
  78         int uplink;            /**< dfn number of ancestor. */
  79         /*  ir_loop *loop;         *//* Refers to the containing loop. */
  80         /*
  81             struct section *section;
  82             xset def;
  83             xset use;
  84         */
  85 } scc_info;
  86
  87 /**
  88  * Allocates a new SCC info on the given obstack.
  89  */
  90 static inline scc_info *new_scc_info(struct obstack *obst)
  91 {
  92         return OALLOCZ(obst, scc_info);
  93 }
  94
  95 /**
  96  * Mark node n being on the SCC stack.
  97  */
  98 static inline void mark_irn_in_stack(ir_node *n)
  99 {
 100         scc_info *scc = get_irn_link(n);
 101         assert(scc);
 102         scc->in_stack = 1;
 103 }
 104
 105 /**
 106 * Mark node n NOT being on the SCC stack.
 107 */
 108 static inline void mark_irn_not_in_stack(ir_node *n)
 109 {
 110         scc_info *scc = get_irn_link(n);
 111         assert(scc);
 112         scc->in_stack = 0;
 113 }
 114
 115 /**
 116  * Checks if a node is on the SCC stack.
 117  */
 118 static inline int irn_is_in_stack(ir_node *n)
 119 {
 120         scc_info *scc = get_irn_link(n);
 121         assert(scc);
 122         return scc->in_stack;
 123 }
 124
 125 /**
 126  * Sets the uplink number for a node.
 127  */
 128 static inline void set_irn_uplink(ir_node *n, int uplink)
 129 {
 130         scc_info *scc = get_irn_link(n);
 131         assert(scc);
 132         scc->uplink = uplink;
 133 }
 134
 135 /**
 136  * Returns the uplink number for a node.
 137  */
 138 static int get_irn_uplink(ir_node *n)
 139 {
 140         scc_info *scc = get_irn_link(n);
 141         assert(scc);
 142         return scc->uplink;
 143 }
 144
 145 /**
 146  * Sets the depth-first-search number for a node.
 147  */
 148 static inline void set_irn_dfn(ir_node *n, int dfn)
 149 {
 150         scc_info *scc = get_irn_link(n);
 151         assert(scc);
 152         scc->dfn = dfn;
 153 }
 154
 155 /**
 156  * Returns the depth-first-search number of a node.
 157  */
 158 static int get_irn_dfn(ir_node *n)
 159 {
 160         scc_info *scc = get_irn_link(n);
 161         assert(scc);
 162         return scc->dfn;
 163 }
 164
 165 #if 0
 166 static ir_loop *find_nodes_loop(ir_node *n, ir_loop *l)
 167 {
 168         int i;
 169         ir_loop *res = NULL;
 170
 171         /* Test whether n is contained in this loop. */
 172         for (i = 0; i < get_loop_n_nodes(l); i++)
 173                 if (n == get_loop_node(l, i)) return l;
 174
 175         /* Is this a leave in the loop tree? If so loop not found. */
 176         if (get_loop_n_sons(l) == 0) return NULL;
 177
 178         /* Else descend in the loop tree. */
 179         for (i = 0; i < get_loop_n_sons(l); i++) {
 180                 res = find_nodes_loop(n, get_loop_son(l, i));
 181                 if (res) break;
 182         }
 183         return res;
 184 }
 185
 186 /* @@@ temporary implementation, costly!!! */
 187 ir_loop * get_irn_loop(ir_node *n)
 188 {
 189         ir_loop *l = get_irg_loop(current_ir_graph);
 190         l = find_nodes_loop(n, l);
 191         return l;
 192 }
 193 #endif
 194
 195 /**********************************************************************/
 196 /* A stack.                                                          **/
 197 /**********************************************************************/
 198
 199 static ir_node **stack = NULL;
 200 static int tos = 0;                /* top of stack */
 201
 202 /**
 203  * initializes the stack
 204  */
 205 static inline void init_stack(void)
 206 {
 207         if (stack) {
 208                 ARR_RESIZE(ir_node *, stack, 1000);
 209         } else {
 210                 stack = NEW_ARR_F(ir_node *, 1000);
 211         }
 212         tos = 0;
 213 }
 214
 215 /**
 216  * Frees the stack.
 217  */
 218 static void finish_stack(void)
 219 {
 220         DEL_ARR_F(stack);
 221         stack = NULL;
 222 }
 223
 224 /**
 225  * push a node onto the stack
 226  *
 227  * @param n  The node to push
 228  */
 229 static inline void push(ir_node *n)
 230 {
 231         if (tos == ARR_LEN(stack)) {
 232                 int nlen = ARR_LEN(stack) * 2;
 233                 ARR_RESIZE(ir_node *, stack, nlen);
 234         }
 235         stack [tos++] = n;
 236         mark_irn_in_stack(n);
 237 }
 238
 239 /**
 240  * pop a node from the stack
 241  *
 242  * @return  The topmost node
 243  */
 244 static inline ir_node *pop(void)
 245 {
 246         ir_node *n = stack[--tos];
 247         mark_irn_not_in_stack(n);
 248         return n;
 249 }
 250
 251 /**
 252  * The nodes up to n belong to the current loop.
 253  * Removes them from the stack and adds them to the current loop.
 254  */
 255 static inline void pop_scc_to_loop(ir_node *n)
 256 {
 257         ir_node *m;
 258         int i = 0;
 259
 260         do {
 261                 m = pop();
 262
 263                 loop_node_cnt++;
 264                 set_irn_dfn(m, loop_node_cnt);
 265                 add_loop_node(current_loop, m);
 266                 set_irn_loop(m, current_loop);
 267                 ++i;
 268         } while (m != n);
 269
 270         /* i might be bigger than 1 for dead (and that's why bad) loops */
 271         /* if (i > 1)
 272                 printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!11111\n");
 273          */
 274 }
 275
 276 /* GL ??? my last son is my grandson???  Removes loops with no
 277    ir_nodes in them.  Such loops have only another loop as son. (Why
 278    can't they have two loops as sons? Does it never get that far? ) */
 279 static void close_loop(ir_loop *l)
 280 {
 281         int last = get_loop_n_elements(l) - 1;
 282         loop_element lelement = get_loop_element(l, last);
 283         ir_loop *last_son = lelement.son;
 284
 285         if (get_kind(last_son) == k_ir_loop &&
 286                 get_loop_n_elements(last_son) == 1) {
 287                         ir_loop *gson;
 288
 289                         lelement = get_loop_element(last_son, 0);
 290                         gson = lelement.son;
 291
 292                         if (get_kind(gson) == k_ir_loop) {
 293                                 loop_element new_last_son;
 294
 295                                 gson->outer_loop = l;
 296                                 new_last_son.son = gson;
 297                                 l->children[last] = new_last_son;
 298                         }
 299         }
 300
 301         current_loop = l;
 302 }
 303
 304 /* Removes and unmarks all nodes up to n from the stack.
 305    The nodes must be visited once more to assign them to a scc. */
 306 static inline void pop_scc_unmark_visit(ir_node *n)
 307 {
 308         ir_node *m = NULL;
 309
 310         while (m != n) {
 311                 m = pop();
 312                 set_irn_visited(m, 0);
 313         }
 314 }
 315
 316 /**********************************************************************/
 317 /* The loop datastructure.                                           **/
 318 /**********************************************************************/
 319
 320 /* Allocates a new loop as son of current_loop.  Sets current_loop
 321    to the new loop and returns the father. */
 322 static ir_loop *new_loop(void)
 323 {
 324         ir_loop *father = current_loop;
 325         ir_loop *son    = alloc_loop(father, outermost_ir_graph->obst);
 326
 327         if (son->depth > max_loop_depth) max_loop_depth = son->depth;
 328         current_loop = son;
 329         return father;
 330 }
 331
 332 /**********************************************************************/
 333 /* Constructing and destructing the loop/backedge information.       **/
 334 /**********************************************************************/
 335
 336 /* Initialization steps. **********************************************/
 337
 338 static inline void init_node(ir_node *n, void *env)
 339 {
 340         struct obstack *obst = env;
 341         set_irn_link(n, new_scc_info(obst));
 342         clear_backedges(n);
 343 }
 344
 345 static inline void init_scc_common(void)
 346 {
 347         current_dfn = 1;
 348         loop_node_cnt = 0;
 349         init_stack();
 350 }
 351
 352 static inline void init_scc(ir_graph *irg, struct obstack *obst)
 353 {
 354         init_scc_common();
 355         irg_walk_graph(irg, init_node, NULL, obst);
 356         /*
 357         irg_walk (irg, link_to_reg_end, NULL, NULL);
 358         */
 359 }
 360
 361 static inline void finish_scc(void)
 362 {
 363         finish_stack();
 364 }
 365
 366 #ifdef INTERPROCEDURAL_VIEW
 367 static inline void init_ip_scc(struct obstack *obst)
 368 {
 369         init_scc_common();
 370         cg_walk(init_node, NULL, obst);
 371
 372 #if EXPERIMENTAL_LOOP_TREE
 373         cg_walk(link_to_reg_end, NULL, NULL);
 374 #endif
 375 }
 376 #endif
 377
 378 /**
 379  * Check weather a given node represents the outer most Start
 380  * block. In intra-procedural view this is the start block of the
 381  * current graph, in interprocedural view it is the start block
 382  * of the outer most graph.
 383  *
 384  * @param n  the node to check
 385  *
 386  * This is the condition for breaking the scc recursion.
 387  */
 388 static int is_outermost_Start(ir_node *n)
 389 {
 390         /* Test whether this is the outermost Start node. */
 391         if (is_Block(n) && get_Block_n_cfgpreds(n) == 1) {
 392                 ir_node *pred = skip_Proj(get_Block_cfgpred(n, 0));
 393             if (is_Start(pred) && get_nodes_block(pred) == n)
 394                         return 1;
 395         }
 396         return 0;
 397 }
 398
 399 static inline int is_ip_Filter(ir_node *n)
 400 {
 401 #ifdef INTERPROCEDURAL_VIEW
 402         return is_Filter(n) && get_interprocedural_view();
 403 #else
 404         (void) n;
 405         return 0;
 406 #endif
 407 }
 408
 409 /* When to walk from nodes to blocks. Only for Control flow operations? */
 410 static inline int get_start_index(ir_node *n)
 411 {
 412 #undef BLOCK_BEFORE_NODE
 413 #define BLOCK_BEFORE_NODE 1
 414
 415 #if BLOCK_BEFORE_NODE
 416
 417         /* This version assures, that all nodes are ordered absolutely.  This allows
 418            to undef all nodes in the heap analysis if the block is false, which
 419            means not reachable.
 420            I.e., with this code, the order on the loop tree is correct. But a
 421            (single) test showed the loop tree is deeper. */
 422         if (get_irn_op(n) == op_Phi  ||
 423             is_Block(n)              ||
 424             (is_ip_Filter(n))        || (
 425               get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
 426               get_irn_pinned(n)              == op_pin_state_floats
 427             ))
 428                 // Here we could test for backedge at -1 which is illegal
 429                 return 0;
 430         else
 431                 return -1;
 432
 433 #else
 434
 435         /* This version causes deeper loop trees (at least we verified this
 436            for Polymor).
 437            But it guarantees that Blocks are analysed before nodes contained in the
 438            block.  If so, we can set the value to undef if the block is not \
 439            executed. */
 440         if (is_cfop(n) || is_fragile_op(n) || is_Start(n))
 441                 return -1;
 442         else
 443                 return 0;
 444
 445 #endif
 446 }
 447
 448 /**
 449  * Return non-zero if the given node is a legal loop header:
 450  * Block, Phi, Filter.
 451  *
 452  * @param n  the node to check
 453  */
 454 static inline int is_possible_loop_head(ir_node *n)
 455 {
 456         ir_op *op = get_irn_op(n);
 457         return ((op == op_Block) ||
 458                 (op == op_Phi) ||
 459                 (is_ip_Filter(n)));
 460 }
 461
 462 /**
 463  * Returns non-zero if n is a loop header, i.e., it is a Block, Phi
 464  * or Filter node and has predecessors within the loop and out
 465  * of the loop.
 466  *
 467  * @param n    the node to check
 468  * @param root only needed for assertion.
 469  */
 470 static int is_head(ir_node *n, ir_node *root)
 471 {
 472         int i, arity;
 473         int some_outof_loop = 0, some_in_loop = 0;
 474
 475         /* Test for legal loop header: Block, Phi, ... */
 476         if (!is_possible_loop_head(n))
 477                 return 0;
 478
 479         if (!is_outermost_Start(n)) {
 480 #ifndef NDEBUG
 481                 int uplink = get_irn_uplink(root);
 482 #else
 483                 (void) root;
 484 #endif
 485                 arity = get_irn_arity(n);
 486                 for (i = get_start_index(n); i < arity; i++) {
 487                         ir_node *pred;
 488                         if (is_backedge(n, i))
 489                                 continue;
 490                         pred = get_irn_n(n, i);
 491                         if (! irn_is_in_stack(pred)) {
 492                                 some_outof_loop = 1;
 493                         } else {
 494                                 assert(get_irn_uplink(pred) >= uplink);
 495                                 some_in_loop = 1;
 496                         }
 497                 }
 498         }
 499         return some_outof_loop & some_in_loop;
 500 }
 501
 502 /**
 503  * Returns non-zero if n is possible loop head of an endless loop.
 504  * I.e., it is a Block, Phi or Filter node and has only predecessors
 505  * within the loop.
 506  *
 507  * @param n    the node to check
 508  * @param root only needed for assertion.
 509  */
 510 static int is_endless_head(ir_node *n, ir_node *root)
 511 {
 512         int i, arity;
 513         int none_outof_loop = 1, some_in_loop = 0;
 514
 515         /* Test for legal loop header: Block, Phi, ... */
 516         if (!is_possible_loop_head(n))
 517                 return 0;
 518
 519         if (!is_outermost_Start(n)) {
 520 #ifndef NDEBUG
 521                 int uplink = get_irn_uplink(root);
 522 #else
 523                 (void) root;
 524 #endif
 525                 arity = get_irn_arity(n);
 526                 for (i = get_start_index(n); i < arity; i++) {
 527                         ir_node *pred;
 528                         if (is_backedge(n, i))
 529                                 continue;
 530                         pred = get_irn_n(n, i);
 531                         if (!irn_is_in_stack(pred)) {
 532                                 none_outof_loop = 0;
 533                         } else {
 534                                 assert(get_irn_uplink(pred) >= uplink);
 535                                 some_in_loop = 1;
 536                         }
 537                 }
 538         }
 539         return none_outof_loop & some_in_loop;
 540 }
 541
 542 /** Returns index of the predecessor with the smallest dfn number
 543     greater-equal than limit. */
 544 static int smallest_dfn_pred(ir_node *n, int limit)
 545 {
 546         int i, index = -2, min = -1;
 547
 548         if (!is_outermost_Start(n)) {
 549                 int arity = get_irn_arity(n);
 550                 for (i = get_start_index(n); i < arity; i++) {
 551                         ir_node *pred = get_irn_n(n, i);
 552                         if (is_backedge(n, i) || !irn_is_in_stack(pred))
 553                                 continue;
 554                         if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
 555                                 index = i;
 556                                 min = get_irn_dfn(pred);
 557                         }
 558                 }
 559         }
 560         return index;
 561 }
 562
 563 /**
 564  * Returns index of the predecessor with the largest dfn number.
 565  */
 566 static int largest_dfn_pred(ir_node *n)
 567 {
 568         int i, index = -2, max = -1;
 569
 570         if (!is_outermost_Start(n)) {
 571                 int arity = get_irn_arity(n);
 572                 for (i = get_start_index(n); i < arity; i++) {
 573                         ir_node *pred = get_irn_n(n, i);
 574                         if (is_backedge (n, i) || !irn_is_in_stack(pred))
 575                                 continue;
 576                         if (get_irn_dfn(pred) > max) {
 577                                 index = i;
 578                                 max = get_irn_dfn(pred);
 579                         }
 580                 }
 581         }
 582         return index;
 583 }
 584
 585 /**
 586  * Searches the stack for possible loop heads.  Tests these for backedges.
 587  * If it finds a head with an unmarked backedge it marks this edge and
 588  * returns the tail of the loop.
 589  * If it finds no backedge returns NULL.
 590  * ("disable_backedge" in fiasco)
 591  *
 592  * @param n  A node where uplink == dfn.
 593  */
 594 static ir_node *find_tail(ir_node *n)
 595 {
 596         ir_node *m;
 597         int i, res_index = -2;
 598
 599         /*
 600         if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
 601          */
 602         m = stack[tos-1];  /* tos = top of stack */
 603         if (is_head(m, n)) {
 604                 res_index = smallest_dfn_pred(m, 0);
 605                 if ((res_index == -2) &&  /* no smallest dfn pred found. */
 606                         (n ==  m))
 607                         return NULL;
 608         } else {
 609                 if (m == n) return NULL;    // Is this to catch Phi - self loops?
 610                 for (i = tos-2; i >= 0; --i) {
 611                         m = stack[i];
 612
 613                         if (is_head(m, n)) {
 614                                 res_index = smallest_dfn_pred(m, get_irn_dfn(m) + 1);
 615                                 if (res_index == -2)  /* no smallest dfn pred found. */
 616                                         res_index = largest_dfn_pred(m);
 617
 618                                 if ((m == n) && (res_index == -2)) {  /* don't walk past loop head. */
 619                                         i = -1;
 620                                 }
 621                                 break;
 622                         }
 623
 624                         /* We should not walk past our selves on the stack:  The upcoming nodes
 625                            are not in this loop. We assume a loop not reachable from Start. */
 626                         if (m == n) {
 627                                 i = -1;
 628                                 break;
 629                         }
 630                 }
 631
 632                 if (i < 0) {
 633                         /* A dead loop not reachable from Start. */
 634                         for (i = tos-2; i >= 0; --i) {
 635                                 m = stack[i];
 636                                 if (is_endless_head(m, n)) {
 637                                         res_index = smallest_dfn_pred(m, get_irn_dfn(m) + 1);
 638                                         if (res_index == -2)  /* no smallest dfn pred found. */
 639                                                 res_index = largest_dfn_pred (m);
 640                                         break;
 641                                 }
 642                                 if (m == n) { break; }  /* It's not an unreachable loop, either. */
 643                         }
 644                         //assert(0 && "no head found on stack");
 645                 }
 646
 647         }
 648         if (res_index <= -2) {
 649                 /* It's a completely bad loop: without Phi/Block nodes that can
 650                    be a head. I.e., the code is "dying".  We break the loop by
 651                    setting Bad nodes. */
 652                 int arity = get_irn_arity(n);
 653                 ir_node *bad = get_irg_bad(get_irn_irg(n));
 654                 for (i = -1; i < arity; ++i) {
 655                         set_irn_n(n, i, bad);
 656                 }
 657                 return NULL;
 658         }
 659         assert(res_index > -2);
 660
 661         set_backedge(m, res_index);
 662         return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
 663 }
 664
 665
 666 #if EXPERIMENTAL_LOOP_TREE
 667
 668 /*  ----------------------------------------------------------------
 669     AS:  This is experimental code to build loop trees suitable for
 670     the heap analysis. Does not work correctly right now... :-(
 671
 672
 673     Search in stack for the corresponding first Call-End-ProjX that
 674     corresponds to one of the control flow predecessors of the given
 675     block, that is the possible callers.
 676     returns: the control predecessor to chose\
 677     or       -1 if no corresponding Call-End-Node could be found
 678              on the stack.
 679     - -------------------------------------------------------------- */
 680
 681 int search_endproj_in_stack(ir_node *start_block)
 682 {
 683         int i, j;
 684         assert(is_Block(start_block));
 685         for (i = tos - 1; i >= 0; --i)
 686         {
 687                 if (get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
 688                         get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
 689                 {
 690                         printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
 691                         ir_node *end_projx = stack[i];
 692
 693                         int arity = get_irn_arity(start_block);
 694                         for (j = 0; j < arity; j++)
 695                         {
 696                                 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
 697                                         get_Proj_proj(end_projx));
 698                                 if (get_irn_n(start_block, j) == begin_projx)
 699                                 {
 700                                         printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
 701                                         return(j);
 702                                 }
 703                         }
 704                 }
 705         }
 706         return(-1);
 707 }
 708
 709
 710 static pmap *projx_link = NULL;
 711
 712 void link_to_reg_end (ir_node *n, void *env)
 713 {
 714         if (get_irn_op(n) == op_Proj &&
 715                 get_irn_mode(n) == mode_X &&
 716                 get_irn_op(get_irn_n(n, 0)) == op_EndReg) {
 717                         /* Reg End Projx -> Find the CallBegin Projx and hash it */
 718                         ir_node *end_projx = n;
 719                         ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
 720                                 get_Proj_proj(end_projx));
 721                         set_projx_link(begin_projx, end_projx);
 722         }
 723 }
 724
 725 void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
 726 {
 727         if (projx_link == NULL)
 728                 projx_link = pmap_create();
 729         pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
 730 }
 731
 732 ir_node *get_projx_link(ir_node *cb_projx)
 733 {
 734         return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
 735 }
 736
 737 #endif
 738
 739 static inline int is_outermost_loop(ir_loop *l)
 740 {
 741         return l == get_loop_outer_loop(l);
 742 }
 743
 744
 745 /*-----------------------------------------------------------*
 746  *                   The core algorithm.                     *
 747  *-----------------------------------------------------------*/
 748
 749 /**
 750  * The core algorithm: Find strongly coupled components.
 751  *
 752  * @param n  node to start
 753  */
 754 static void scc(ir_node *n)
 755 {
 756         if (irn_visited_else_mark(n))
 757                 return;
 758
 759         /* Initialize the node */
 760         set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
 761         set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
 762         set_irn_loop(n, NULL);
 763         ++current_dfn;
 764         push(n);
 765
 766         /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
 767            array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
 768            so is_backedge does not access array[-1] but correctly returns false! */
 769
 770         if (!is_outermost_Start(n)) {
 771                 int i, arity = get_irn_arity(n);
 772
 773                 for (i = get_start_index(n); i < arity; ++i) {
 774                         ir_node *m;
 775                         if (is_backedge(n, i))
 776                                 continue;
 777                         m = get_irn_n(n, i);
 778                         scc(m);
 779                         if (irn_is_in_stack(m)) {
 780                                 /* Uplink of m is smaller if n->m is a backedge.
 781                                    Propagate the uplink to mark the loop. */
 782                                 if (get_irn_uplink(m) < get_irn_uplink(n))
 783                                         set_irn_uplink(n, get_irn_uplink(m));
 784                         }
 785                 }
 786         }
 787
 788         if (get_irn_dfn(n) == get_irn_uplink(n)) {
 789                 /* This condition holds for
 790                    1) the node with the incoming backedge.
 791                       That is: We found a loop!
 792                    2) Straight line code, because no uplink has been propagated, so the
 793                       uplink still is the same as the dfn.
 794
 795                    But n might not be a proper loop head for the analysis. Proper loop
 796                    heads are Block and Phi nodes. find_tail() searches the stack for
 797                    Block's and Phi's and takes those nodes as loop heads for the current
 798                    loop instead and marks the incoming edge as backedge. */
 799
 800                 ir_node *tail = find_tail(n);
 801                 if (tail != NULL) {
 802                         /* We have a loop, that is no straight line code,
 803                            because we found a loop head!
 804                            Next actions: Open a new loop on the loop tree and
 805                                          try to find inner loops */
 806
 807 #if NO_LOOPS_WITHOUT_HEAD
 808                         /* This is an adaption of the algorithm from fiasco / optscc to
 809                          * avoid loops without Block or Phi as first node.  This should
 810                          * severely reduce the number of evaluations of nodes to detect
 811                          * a fixpoint in the heap analysis.
 812                          * Further it avoids loops without firm nodes that cause errors
 813                          * in the heap analyses.
 814                          * But attention:  don't do it for the outermost loop:  This loop
 815                          * is not iterated.  A first block can be a loop head in case of
 816                          * an endless recursion. */
 817
 818                         ir_loop *l;
 819                         int close;
 820                         if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
 821                                 l = new_loop();
 822                                 close = 1;
 823                         } else {
 824                                 l = current_loop;
 825                                 close = 0;
 826                         }
 827 #else
 828                         ir_loop *l = new_loop();
 829 #endif
 830
 831                         /* Remove the loop from the stack ... */
 832                         pop_scc_unmark_visit(n);
 833
 834                         /* The current backedge has been marked, that is temporarily eliminated,
 835                            by find tail. Start the scc algorithm
 836                            again on the subgraph that is left (the current loop without the backedge)
 837                            in order to find more inner loops. */
 838                         scc(tail);
 839
 840                         assert(irn_visited(n));
 841 #if NO_LOOPS_WITHOUT_HEAD
 842                         if (close)
 843 #endif
 844                                 close_loop(l);
 845                 } else {
 846                         /* No loop head was found, that is we have straight line code.
 847                            Pop all nodes from the stack to the current loop. */
 848                         pop_scc_to_loop(n);
 849                 }
 850         }
 851 }
 852
 853 #ifdef INTERPROCEDURAL_VIEW
 854 static void my_scc(ir_node *n)
 855 {
 856         int i;
 857         if (irn_visited_else_mark(n))
 858                 return;
 859
 860         /* Initialize the node */
 861         set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
 862         set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
 863         set_irn_loop(n, NULL);
 864         current_dfn ++;
 865         push(n);
 866
 867         /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
 868            array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
 869            so is_backedge does not access array[-1] but correctly returns false! */
 870
 871         if (!is_outermost_Start(n)) {
 872                 int arity = get_irn_arity(n);
 873
 874                 for (i = get_start_index(n); i < arity; i++) {
 875                         ir_node *m;
 876                         if (is_backedge(n, i)) continue;
 877                         m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
 878                         /* if (!m || is_Unknown(m)) continue; */
 879                         my_scc(m);
 880                         if (irn_is_in_stack(m)) {
 881                                 /* Uplink of m is smaller if n->m is a backedge.
 882                                    Propagate the uplink to mark the loop. */
 883                                 if (get_irn_uplink(m) < get_irn_uplink(n))
 884                                         set_irn_uplink(n, get_irn_uplink(m));
 885                         }
 886                 }
 887         }
 888
 889         if (get_irn_dfn(n) == get_irn_uplink(n)) {
 890                 /* This condition holds for
 891                    1) the node with the incoming backedge.
 892                       That is: We found a loop!
 893                    2) Straight line code, because no uplink has been propagated, so the
 894                       uplink still is the same as the dfn.
 895
 896                    But n might not be a proper loop head for the analysis. Proper loop
 897                    heads are Block and Phi nodes. find_tail searches the stack for
 898                    Block's and Phi's and takes those nodes as loop heads for the current
 899                    loop instead and marks the incoming edge as backedge. */
 900
 901                 ir_node *tail = find_tail(n);
 902                 if (tail) {
 903                         /* We have a loop, that is no straight line code,
 904                            because we found a loop head!
 905                            Next actions: Open a new loop on the loop tree and
 906                                          try to find inner loops */
 907
 908 #if NO_LOOPS_WITHOUT_HEAD
 909                         /* This is an adaption of the algorithm from fiasco / optscc to
 910                          * avoid loops without Block or Phi as first node.  This should
 911                          * severely reduce the number of evaluations of nodes to detect
 912                          * a fixpoint in the heap analysis.
 913                          * Further it avoids loops without firm nodes that cause errors
 914                          * in the heap analyses. */
 915
 916                         ir_loop *l;
 917                         int close;
 918                         if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
 919                                 l = new_loop();
 920                                 close = 1;
 921                         } else {
 922                                 l = current_loop;
 923                                 close = 0;
 924                         }
 925 #else
 926                         ir_loop *l = new_loop();
 927 #endif
 928
 929                         /* Remove the loop from the stack ... */
 930                         pop_scc_unmark_visit(n);
 931
 932                         /* The current backedge has been marked, that is temporarily eliminated,
 933                            by find tail. Start the scc algorithm
 934                            anew on the subgraph that is left (the current loop without the backedge)
 935                            in order to find more inner loops. */
 936                         my_scc(tail);
 937
 938                         assert(irn_visited(n));
 939 #if NO_LOOPS_WITHOUT_HEAD
 940                         if (close)
 941 #endif
 942                                 close_loop(l);
 943                 } else {
 944                         /* No loop head was found, that is we have straightline code.
 945                            Pop all nodes from the stack to the current loop. */
 946                         pop_scc_to_loop(n);
 947                 }
 948         }
 949 }
 950 #endif /* INTERPROCEDURAL_VIEW */
 951
 952 /* Constructs backedge information for irg. In interprocedural view constructs
 953    backedges for all methods called by irg, too. */
 954 int construct_backedges(ir_graph *irg)
 955 {
 956         ir_graph *rem = current_ir_graph;
 957         ir_loop *head_rem;
 958         struct obstack temp;
 959
 960 #ifdef INTERPROCEDURAL_VIEW
 961         assert(!get_interprocedural_view() &&
 962                "not implemented, use construct_ip_backedges()");
 963 #endif
 964
 965         max_loop_depth = 0;
 966         current_ir_graph   = irg;
 967         outermost_ir_graph = irg;
 968
 969         obstack_init(&temp);
 970         init_scc(irg, &temp);
 971
 972         current_loop = NULL;
 973         new_loop();  /* sets current_loop */
 974         head_rem = current_loop; /* Just for assertion */
 975
 976         inc_irg_visited(irg);
 977
 978         scc(get_irg_end(irg));
 979
 980         finish_scc();
 981         obstack_free(&temp, NULL);
 982
 983         assert(head_rem == current_loop);
 984         mature_loops(current_loop, irg->obst);
 985         set_irg_loop(irg, current_loop);
 986         set_irg_loopinfo_state(irg, loopinfo_consistent);
 987         assert(get_irg_loop(irg)->kind == k_ir_loop);
 988         current_ir_graph = rem;
 989         return max_loop_depth;
 990 }
 991
 992
 993 #ifdef INTERPROCEDURAL_VIEW
 994 int construct_ip_backedges(void)
 995 {
 996         ir_graph *rem = current_ir_graph;
 997         int rem_ipv = get_interprocedural_view();
 998         int i;
 999         strcut obstack temp;
1000
1001         max_loop_depth = 0;
1002         assert(get_irp_ip_view_state() == ip_view_valid);
1003
1004         outermost_ir_graph = get_irp_main_irg();
1005
1006         obstack_init(&temp);
1007         init_ip_scc(&temp);
1008
1009         current_loop = NULL;
1010         new_loop();  /* sets current_loop */
1011         set_interprocedural_view(1);
1012
1013         inc_max_irg_visited();
1014         for (i = 0; i < get_irp_n_irgs(); i++)
1015                 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1016
1017         /** We have to start the walk at the same nodes as cg_walk. **/
1018         /* Walk starting at unreachable procedures. Only these
1019          * have End blocks visible in interprocedural view. */
1020         for (i = 0; i < get_irp_n_irgs(); i++) {
1021                 ir_node *sb;
1022                 current_ir_graph = get_irp_irg(i);
1023
1024                 sb = get_irg_start_block(current_ir_graph);
1025
1026                 if ((get_Block_n_cfgpreds(sb) > 1) ||
1027                     (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb))
1028                         continue;
1029
1030                 scc(get_irg_end(current_ir_graph));
1031         }
1032
1033         /* Check whether we walked all procedures: there could be procedures
1034            with cyclic calls but no call from the outside. */
1035         for (i = 0; i < get_irp_n_irgs(); i++) {
1036                 ir_node *sb;
1037                 current_ir_graph = get_irp_irg(i);
1038
1039                 /* Test start block: if inner procedure end and end block are not
1040                  * visible and therefore not marked. */
1041                 sb = get_irg_start_block(current_ir_graph);
1042                 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1043         }
1044
1045         /* Walk all endless loops in inner procedures.
1046          * We recognize an inner procedure if the End node is not visited. */
1047         for (i = 0; i < get_irp_n_irgs(); i++) {
1048                 ir_node *e;
1049                 current_ir_graph = get_irp_irg(i);
1050
1051                 e = get_irg_end(current_ir_graph);
1052                 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1053                         int j;
1054                         /* Don't visit the End node. */
1055                         for (j = 0; j < get_End_n_keepalives(e); j++)
1056                                 scc(get_End_keepalive(e, j));
1057                 }
1058         }
1059
1060         set_irg_loop(outermost_ir_graph, current_loop);
1061         set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1062         assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1063
1064         obstack_free(&temp, NULL);
1065         current_ir_graph = rem;
1066         set_interprocedural_view(rem_ipv);
1067         return max_loop_depth;
1068 }
1069
1070 void my_construct_ip_backedges(void)
1071 {
1072         ir_graph *rem = current_ir_graph;
1073         int rem_ipv = get_interprocedural_view();
1074         int i;
1075
1076         assert(get_irp_ip_view_state() == ip_view_valid);
1077
1078         outermost_ir_graph = get_irp_main_irg();
1079
1080         init_ip_scc();
1081
1082         current_loop = NULL;
1083         new_loop();  /* sets current_loop */
1084         set_interprocedural_view(1);
1085
1086         inc_max_irg_visited();
1087         for (i = 0; i < get_irp_n_irgs(); i++)
1088                 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1089
1090         /** We have to start the walk at the same nodes as cg_walk. **/
1091         /* Walk starting at unreachable procedures. Only these
1092          * have End blocks visible in interprocedural view. */
1093         for (i = 0; i < get_irp_n_irgs(); i++) {
1094                 ir_node *sb;
1095                 current_ir_graph = get_irp_irg(i);
1096
1097                 sb = get_irg_start_block(current_ir_graph);
1098
1099                 if ((get_Block_n_cfgpreds(sb) > 1) ||
1100                     (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1101
1102                 my_scc(get_irg_end(current_ir_graph));
1103         }
1104
1105         /* Check whether we walked all procedures: there could be procedures
1106            with cyclic calls but no call from the outside. */
1107         for (i = 0; i < get_irp_n_irgs(); i++) {
1108                 ir_node *sb;
1109                 current_ir_graph = get_irp_irg(i);
1110
1111                 /* Test start block: if inner procedure end and end block are not
1112                  * visible and therefore not marked. */
1113                 sb = get_irg_start_block(current_ir_graph);
1114                 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph))
1115                         scc(sb);
1116         }
1117
1118         /* Walk all endless loops in inner procedures.
1119          * We recognize an inner procedure if the End node is not visited. */
1120         for (i = 0; i < get_irp_n_irgs(); i++) {
1121                 ir_node *e;
1122                 current_ir_graph = get_irp_irg(i);
1123
1124                 e = get_irg_end(current_ir_graph);
1125                 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1126                         int j;
1127                         /* Don't visit the End node. */
1128                         for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1129                 }
1130         }
1131
1132         set_irg_loop(outermost_ir_graph, current_loop);
1133         set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1134         assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1135
1136         current_ir_graph = rem;
1137         set_interprocedural_view(rem_ipv);
1138 }
1139 #endif
1140
1141 static void reset_backedges(ir_node *n)
1142 {
1143         if (is_possible_loop_head(n)) {
1144 #ifdef INTERPROCEDURAL_VIEW
1145                 int rem = get_interprocedural_view();
1146
1147                 set_interprocedural_view(1);
1148                 clear_backedges(n);
1149                 set_interprocedural_view(1);
1150                 clear_backedges(n);
1151                 set_interprocedural_view(rem);
1152 #else
1153                 clear_backedges(n);
1154 #endif
1155         }
1156 }
1157
1158
1159 /*
1160 static void loop_reset_backedges(ir_loop *l)
1161 {
1162         int i;
1163         reset_backedges(get_loop_node(l, 0));
1164         for (i = 0; i < get_loop_n_nodes(l); ++i)
1165                 set_irn_loop(get_loop_node(l, i), NULL);
1166         for (i = 0; i < get_loop_n_sons(l); ++i) {
1167                 loop_reset_backedges(get_loop_son(l, i));
1168         }
1169 }
1170 */
1171
1172 static void loop_reset_node(ir_node *n, void *env)
1173 {
1174         (void) env;
1175         set_irn_loop(n, NULL);
1176         reset_backedges(n);
1177 }
1178
1179
1180 /** Removes all loop information.
1181     Resets all backedges */
1182 void free_loop_information(ir_graph *irg)
1183 {
1184         /* We can not use this recursion, as the loop might contain
1185            illegal nodes by now.  Why else would we throw away the
1186            representation?
1187         if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1188         */
1189         irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1190         set_irg_loop(irg, NULL);
1191         set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1192         /* We cannot free the loop nodes, they are on the obstack. */
1193 }
1194
1195
1196 void free_all_loop_information(void)
1197 {
1198         int i;
1199 #ifdef INTERPROCEDURAL_VIEW
1200         int rem = get_interprocedural_view();
1201         set_interprocedural_view(1);  /* To visit all filter nodes */
1202 #endif
1203         for (i = 0; i < get_irp_n_irgs(); i++) {
1204                 free_loop_information(get_irp_irg(i));
1205         }
1206 #ifdef INTERPROCEDURAL_VIEW
1207         set_interprocedural_view(rem);
1208 #endif
1209 }
1210
1211 /* ------------------------------------------------------------------- */
1212 /* Simple analyses based on the loop information                       */
1213 /* ------------------------------------------------------------------- */
1214
1215 static int is_loop_variant(ir_loop *l, ir_loop *b)
1216 {
1217         int i, n_elems;
1218
1219         if (l == b) return 1;
1220
1221         n_elems = get_loop_n_elements(l);
1222         for (i = 0; i < n_elems; ++i) {
1223                 loop_element e = get_loop_element(l, i);
1224                 if (is_ir_loop(e.kind))
1225                         if (is_loop_variant(e.son, b))
1226                                 return 1;
1227         }
1228
1229         return 0;
1230 }
1231
1232 /* Test whether a value is loop invariant.
1233  *
1234  * @param n      The node to be tested.
1235  * @param block  A block node.  We pass the block, not the loop as we must
1236  *               start off with a block loop to find all proper uses.
1237  *
1238  * Returns non-zero, if the node n is not changed in the loop block
1239  * belongs to or in inner loops of this blocks loop. */
1240 int is_loop_invariant(const ir_node *n, const ir_node *block)
1241 {
1242         ir_loop *l = get_irn_loop(block);
1243         const ir_node *b = is_Block(n) ? n : get_nodes_block(n);
1244         return !is_loop_variant(l, get_irn_loop(b));
1245 }