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

   1 /*
   2  * Copyright (C) 1995-2011 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  */
  29 #include "config.h"
  30
  31 #include <string.h>
  32 #include <stdlib.h>
  33
  34 #include "irloop_t.h"
  35
  36 #include "irprog_t.h"
  37 #include "irgraph_t.h"
  38 #include "irnode_t.h"
  39 #include "irgwalk.h"
  40 #include "irdump.h"
  41 #include "array.h"
  42 #include "pmap.h"
  43
  44 /* A variant of the loop tree that avoids loops without head.
  45    This reduces the depth of the loop tree. */
  46 #define NO_LOOPS_WITHOUT_HEAD 1
  47
  48 /** The outermost graph the scc is computed for. */
  49 static ir_graph *outermost_ir_graph;
  50 /** Current loop construction is working on. */
  51 static ir_loop *current_loop;
  52 /** Counts the number of allocated loop nodes.
  53  *  Each loop node gets a unique number.
  54  *  @todo What for? ev. remove.
  55  */
  56 static int loop_node_cnt = 0;
  57 /** Counter to generate depth first numbering of visited nodes. */
  58 static int current_dfn = 1;
  59
  60 static unsigned max_loop_depth = 0;
  61
  62 void link_to_reg_end(ir_node *n, void *env);
  63 void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
  64 ir_node *get_projx_link(ir_node *cb_projx);
  65
  66 /**********************************************************************/
  67 /* Node attributes                                                   **/
  68 /**********************************************************************/
  69
  70 /**********************************************************************/
  71 /* Node attributes needed for the construction.                      **/
  72 /**********************************************************************/
  73
  74 typedef struct scc_info {
  75         int in_stack;          /**< Marks whether node is on the stack. */
  76         int dfn;               /**< Depth first search number. */
  77         int uplink;            /**< dfn number of ancestor. */
  78         /*  ir_loop *loop;         *//* Refers to the containing loop. */
  79         /*
  80             struct section *section;
  81             xset def;
  82             xset use;
  83         */
  84 } scc_info;
  85
  86 /**
  87  * Allocates a new SCC info on the given obstack.
  88  */
  89 static inline scc_info *new_scc_info(struct obstack *obst)
  90 {
  91         return OALLOCZ(obst, scc_info);
  92 }
  93
  94 /**
  95  * Mark node n being on the SCC stack.
  96  */
  97 static inline void mark_irn_in_stack(ir_node *n)
  98 {
  99         scc_info *scc = (scc_info*) get_irn_link(n);
 100         assert(scc);
 101         scc->in_stack = 1;
 102 }
 103
 104 /**
 105 * Mark node n NOT being on the SCC stack.
 106 */
 107 static inline void mark_irn_not_in_stack(ir_node *n)
 108 {
 109         scc_info *scc = (scc_info*) get_irn_link(n);
 110         assert(scc);
 111         scc->in_stack = 0;
 112 }
 113
 114 /**
 115  * Checks if a node is on the SCC stack.
 116  */
 117 static inline int irn_is_in_stack(ir_node *n)
 118 {
 119         scc_info *scc = (scc_info*) get_irn_link(n);
 120         assert(scc);
 121         return scc->in_stack;
 122 }
 123
 124 /**
 125  * Sets the uplink number for a node.
 126  */
 127 static inline void set_irn_uplink(ir_node *n, int uplink)
 128 {
 129         scc_info *scc = (scc_info*) get_irn_link(n);
 130         assert(scc);
 131         scc->uplink = uplink;
 132 }
 133
 134 /**
 135  * Returns the uplink number for a node.
 136  */
 137 static int get_irn_uplink(ir_node *n)
 138 {
 139         scc_info *scc = (scc_info*) get_irn_link(n);
 140         assert(scc);
 141         return scc->uplink;
 142 }
 143
 144 /**
 145  * Sets the depth-first-search number for a node.
 146  */
 147 static inline void set_irn_dfn(ir_node *n, int dfn)
 148 {
 149         scc_info *scc = (scc_info*) get_irn_link(n);
 150         assert(scc);
 151         scc->dfn = dfn;
 152 }
 153
 154 /**
 155  * Returns the depth-first-search number of a node.
 156  */
 157 static int get_irn_dfn(ir_node *n)
 158 {
 159         scc_info *scc = (scc_info*) get_irn_link(n);
 160         assert(scc);
 161         return scc->dfn;
 162 }
 163
 164 #if 0
 165 static ir_loop *find_nodes_loop(ir_node *n, ir_loop *l)
 166 {
 167         int i;
 168         ir_loop *res = NULL;
 169
 170         /* Test whether n is contained in this loop. */
 171         for (i = 0; i < get_loop_n_nodes(l); i++)
 172                 if (n == get_loop_node(l, i)) return l;
 173
 174         /* Is this a leave in the loop tree? If so loop not found. */
 175         if (get_loop_n_sons(l) == 0) return NULL;
 176
 177         /* Else descend in the loop tree. */
 178         for (i = 0; i < get_loop_n_sons(l); i++) {
 179                 res = find_nodes_loop(n, get_loop_son(l, i));
 180                 if (res) break;
 181         }
 182         return res;
 183 }
 184
 185 /* @@@ temporary implementation, costly!!! */
 186 ir_loop * get_irn_loop(ir_node *n)
 187 {
 188         ir_loop *l = get_irg_loop(current_ir_graph);
 189         l = find_nodes_loop(n, l);
 190         return l;
 191 }
 192 #endif
 193
 194 /**********************************************************************/
 195 /* A stack.                                                          **/
 196 /**********************************************************************/
 197
 198 static ir_node **stack = NULL;
 199 static size_t tos = 0;                /* top of stack */
 200
 201 /**
 202  * initializes the stack
 203  */
 204 static inline void init_stack(void)
 205 {
 206         if (stack) {
 207                 ARR_RESIZE(ir_node *, stack, 1000);
 208         } else {
 209                 stack = NEW_ARR_F(ir_node *, 1000);
 210         }
 211         tos = 0;
 212 }
 213
 214 /**
 215  * Frees the stack.
 216  */
 217 static void finish_stack(void)
 218 {
 219         DEL_ARR_F(stack);
 220         stack = NULL;
 221 }
 222
 223 /**
 224  * push a node onto the stack
 225  *
 226  * @param n  The node to push
 227  */
 228 static inline void push(ir_node *n)
 229 {
 230         if (tos == ARR_LEN(stack)) {
 231                 size_t nlen = ARR_LEN(stack) * 2;
 232                 ARR_RESIZE(ir_node *, stack, nlen);
 233         }
 234         stack[tos++] = n;
 235         mark_irn_in_stack(n);
 236 }
 237
 238 /**
 239  * pop a node from the stack
 240  *
 241  * @return  The topmost node
 242  */
 243 static inline ir_node *pop(void)
 244 {
 245         ir_node *n;
 246
 247         assert(tos > 0);
 248         n = stack[--tos];
 249         mark_irn_not_in_stack(n);
 250         return n;
 251 }
 252
 253 /**
 254  * The nodes up to n belong to the current loop.
 255  * Removes them from the stack and adds them to the current loop.
 256  */
 257 static inline void pop_scc_to_loop(ir_node *n)
 258 {
 259         ir_node *m;
 260
 261         do {
 262                 m = pop();
 263
 264                 loop_node_cnt++;
 265                 set_irn_dfn(m, loop_node_cnt);
 266                 add_loop_node(current_loop, m);
 267                 set_irn_loop(m, current_loop);
 268         } while (m != n);
 269 }
 270
 271 /* GL ??? my last son is my grandson???  Removes loops with no
 272    ir_nodes in them.  Such loops have only another loop as son. (Why
 273    can't they have two loops as sons? Does it never get that far? ) */
 274 static void close_loop(ir_loop *l)
 275 {
 276         size_t last = get_loop_n_elements(l) - 1;
 277         loop_element lelement = get_loop_element(l, last);
 278         ir_loop *last_son = lelement.son;
 279
 280         if (get_kind(last_son) == k_ir_loop &&
 281                 get_loop_n_elements(last_son) == 1) {
 282                         ir_loop *gson;
 283
 284                         lelement = get_loop_element(last_son, 0);
 285                         gson = lelement.son;
 286
 287                         if (get_kind(gson) == k_ir_loop) {
 288                                 loop_element new_last_son;
 289
 290                                 gson->outer_loop = l;
 291                                 new_last_son.son = gson;
 292                                 l->children[last] = new_last_son;
 293                         }
 294         }
 295
 296         current_loop = l;
 297 }
 298
 299 /* Removes and unmarks all nodes up to n from the stack.
 300    The nodes must be visited once more to assign them to a scc. */
 301 static inline void pop_scc_unmark_visit(ir_node *n)
 302 {
 303         ir_node *m = NULL;
 304
 305         while (m != n) {
 306                 m = pop();
 307                 set_irn_visited(m, 0);
 308         }
 309 }
 310
 311 /**********************************************************************/
 312 /* The loop datastructure.                                           **/
 313 /**********************************************************************/
 314
 315 /* Allocates a new loop as son of current_loop.  Sets current_loop
 316    to the new loop and returns the father. */
 317 static ir_loop *new_loop(void)
 318 {
 319         ir_loop *father = current_loop;
 320         ir_loop *son    = alloc_loop(father, outermost_ir_graph->obst);
 321
 322         if (son->depth > max_loop_depth) max_loop_depth = son->depth;
 323         current_loop = son;
 324         return father;
 325 }
 326
 327 /**********************************************************************/
 328 /* Constructing and destructing the loop/backedge information.       **/
 329 /**********************************************************************/
 330
 331 /* Initialization steps. **********************************************/
 332
 333 static inline void init_node(ir_node *n, void *env)
 334 {
 335         struct obstack *obst = (struct obstack*) env;
 336         set_irn_link(n, new_scc_info(obst));
 337         clear_backedges(n);
 338 }
 339
 340 static inline void init_scc_common(void)
 341 {
 342         current_dfn = 1;
 343         loop_node_cnt = 0;
 344         init_stack();
 345 }
 346
 347 static inline void init_scc(ir_graph *irg, struct obstack *obst)
 348 {
 349         init_scc_common();
 350         irg_walk_graph(irg, init_node, NULL, obst);
 351         /*
 352         irg_walk (irg, link_to_reg_end, NULL, NULL);
 353         */
 354 }
 355
 356 static inline void finish_scc(void)
 357 {
 358         finish_stack();
 359 }
 360
 361 /**
 362  * Check weather a given node represents the outer most Start
 363  * block. In intra-procedural view this is the start block of the
 364  * current graph, in interprocedural view it is the start block
 365  * of the outer most graph.
 366  *
 367  * @param n  the node to check
 368  *
 369  * This is the condition for breaking the scc recursion.
 370  */
 371 static int is_outermost_Start(ir_node *n)
 372 {
 373         /* Test whether this is the outermost Start node. */
 374         if (is_Block(n) && get_Block_n_cfgpreds(n) == 1) {
 375                 ir_node *pred = skip_Proj(get_Block_cfgpred(n, 0));
 376             if (is_Start(pred) && get_nodes_block(pred) == n)
 377                         return 1;
 378         }
 379         return 0;
 380 }
 381
 382 /* When to walk from nodes to blocks. Only for Control flow operations? */
 383 static inline int get_start_index(ir_node *n)
 384 {
 385 #undef BLOCK_BEFORE_NODE
 386 #define BLOCK_BEFORE_NODE 1
 387
 388 #if BLOCK_BEFORE_NODE
 389
 390         /* This version assures, that all nodes are ordered absolutely.  This allows
 391            to undef all nodes in the heap analysis if the block is false, which
 392            means not reachable.
 393            I.e., with this code, the order on the loop tree is correct. But a
 394            (single) test showed the loop tree is deeper. */
 395         if (get_irn_op(n) == op_Phi  ||
 396             is_Block(n)              ||
 397             (get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
 398               get_irn_pinned(n)              == op_pin_state_floats))
 399                 // Here we could test for backedge at -1 which is illegal
 400                 return 0;
 401         else
 402                 return -1;
 403
 404 #else
 405
 406         /* This version causes deeper loop trees (at least we verified this
 407            for Polymor).
 408            But it guarantees that Blocks are analysed before nodes contained in the
 409            block.  If so, we can set the value to undef if the block is not \
 410            executed. */
 411         if (is_cfop(n) || is_fragile_op(n) || is_Start(n))
 412                 return -1;
 413         else
 414                 return 0;
 415
 416 #endif
 417 }
 418
 419 /**
 420  * Return non-zero if the given node is a legal loop header:
 421  * Block, Phi
 422  *
 423  * @param n  the node to check
 424  */
 425 static inline int is_possible_loop_head(ir_node *n)
 426 {
 427         ir_op *op = get_irn_op(n);
 428         return ((op == op_Block) ||
 429                 (op == op_Phi));
 430 }
 431
 432 /**
 433  * Returns non-zero if n is a loop header, i.e., it is a Block or Phi
 434  * node and has predecessors within the loop and out of the loop.
 435  *
 436  * @param n    the node to check
 437  * @param root only needed for assertion.
 438  */
 439 static int is_head(ir_node *n, ir_node *root)
 440 {
 441         int i, arity;
 442         int some_outof_loop = 0, some_in_loop = 0;
 443
 444         /* Test for legal loop header: Block, Phi, ... */
 445         if (!is_possible_loop_head(n))
 446                 return 0;
 447
 448         if (!is_outermost_Start(n)) {
 449 #ifndef NDEBUG
 450                 int uplink = get_irn_uplink(root);
 451 #else
 452                 (void) root;
 453 #endif
 454                 arity = get_irn_arity(n);
 455                 for (i = get_start_index(n); i < arity; i++) {
 456                         ir_node *pred;
 457                         if (is_backedge(n, i))
 458                                 continue;
 459                         pred = get_irn_n(n, i);
 460                         if (! irn_is_in_stack(pred)) {
 461                                 some_outof_loop = 1;
 462                         } else {
 463                                 assert(get_irn_uplink(pred) >= uplink);
 464                                 some_in_loop = 1;
 465                         }
 466                 }
 467         }
 468         return some_outof_loop & some_in_loop;
 469 }
 470
 471 /**
 472  * Returns non-zero if n is possible loop head of an endless loop.
 473  * I.e., it is a Block or Phi node and has only predecessors
 474  * within the loop.
 475  *
 476  * @param n    the node to check
 477  * @param root only needed for assertion.
 478  */
 479 static int is_endless_head(ir_node *n, ir_node *root)
 480 {
 481         int i, arity;
 482         int none_outof_loop = 1, some_in_loop = 0;
 483
 484         /* Test for legal loop header: Block, Phi, ... */
 485         if (!is_possible_loop_head(n))
 486                 return 0;
 487
 488         if (!is_outermost_Start(n)) {
 489 #ifndef NDEBUG
 490                 int uplink = get_irn_uplink(root);
 491 #else
 492                 (void) root;
 493 #endif
 494                 arity = get_irn_arity(n);
 495                 for (i = get_start_index(n); i < arity; i++) {
 496                         ir_node *pred;
 497                         if (is_backedge(n, i))
 498                                 continue;
 499                         pred = get_irn_n(n, i);
 500                         if (!irn_is_in_stack(pred)) {
 501                                 none_outof_loop = 0;
 502                         } else {
 503                                 assert(get_irn_uplink(pred) >= uplink);
 504                                 some_in_loop = 1;
 505                         }
 506                 }
 507         }
 508         return none_outof_loop & some_in_loop;
 509 }
 510
 511 /** Returns index of the predecessor with the smallest dfn number
 512     greater-equal than limit. */
 513 static int smallest_dfn_pred(ir_node *n, int limit)
 514 {
 515         int i, index = -2, min = -1;
 516
 517         if (!is_outermost_Start(n)) {
 518                 int arity = get_irn_arity(n);
 519                 for (i = get_start_index(n); i < arity; i++) {
 520                         ir_node *pred = get_irn_n(n, i);
 521                         if (is_backedge(n, i) || !irn_is_in_stack(pred))
 522                                 continue;
 523                         if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
 524                                 index = i;
 525                                 min = get_irn_dfn(pred);
 526                         }
 527                 }
 528         }
 529         return index;
 530 }
 531
 532 /**
 533  * Returns index of the predecessor with the largest dfn number.
 534  */
 535 static int largest_dfn_pred(ir_node *n)
 536 {
 537         int i, index = -2, max = -1;
 538
 539         if (!is_outermost_Start(n)) {
 540                 int arity = get_irn_arity(n);
 541                 for (i = get_start_index(n); i < arity; i++) {
 542                         ir_node *pred = get_irn_n(n, i);
 543                         if (is_backedge (n, i) || !irn_is_in_stack(pred))
 544                                 continue;
 545                         if (get_irn_dfn(pred) > max) {
 546                                 index = i;
 547                                 max = get_irn_dfn(pred);
 548                         }
 549                 }
 550         }
 551         return index;
 552 }
 553
 554 /**
 555  * Searches the stack for possible loop heads.  Tests these for backedges.
 556  * If it finds a head with an unmarked backedge it marks this edge and
 557  * returns the tail of the loop.
 558  * If it finds no backedge returns NULL.
 559  * ("disable_backedge" in fiasco)
 560  *
 561  * @param n  A node where uplink == dfn.
 562  */
 563 static ir_node *find_tail(ir_node *n)
 564 {
 565         ir_node *m;
 566         int i, res_index = -2;
 567
 568         /*
 569         if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
 570          */
 571         m = stack[tos-1];  /* tos = top of stack */
 572         if (is_head(m, n)) {
 573                 res_index = smallest_dfn_pred(m, 0);
 574                 if ((res_index == -2) &&  /* no smallest dfn pred found. */
 575                         (n ==  m))
 576                         return NULL;
 577         } else {
 578                 if (m == n) return NULL;    // Is this to catch Phi - self loops?
 579                 for (i = tos-2; i >= 0; --i) {
 580                         m = stack[i];
 581
 582                         if (is_head(m, n)) {
 583                                 res_index = smallest_dfn_pred(m, get_irn_dfn(m) + 1);
 584                                 if (res_index == -2)  /* no smallest dfn pred found. */
 585                                         res_index = largest_dfn_pred(m);
 586
 587                                 if ((m == n) && (res_index == -2)) {  /* don't walk past loop head. */
 588                                         i = -1;
 589                                 }
 590                                 break;
 591                         }
 592
 593                         /* We should not walk past our selves on the stack:  The upcoming nodes
 594                            are not in this loop. We assume a loop not reachable from Start. */
 595                         if (m == n) {
 596                                 i = -1;
 597                                 break;
 598                         }
 599                 }
 600
 601                 if (i < 0) {
 602                         /* A dead loop not reachable from Start. */
 603                         for (i = tos-2; i >= 0; --i) {
 604                                 m = stack[i];
 605                                 if (is_endless_head(m, n)) {
 606                                         res_index = smallest_dfn_pred(m, get_irn_dfn(m) + 1);
 607                                         if (res_index == -2)  /* no smallest dfn pred found. */
 608                                                 res_index = largest_dfn_pred (m);
 609                                         break;
 610                                 }
 611                                 /* It's not an unreachable loop, either. */
 612                                 if (m == n)
 613                                         break;
 614                         }
 615                         //assert(0 && "no head found on stack");
 616                 }
 617
 618         }
 619         if (res_index <= -2) {
 620                 /* It's a completely bad loop: without Phi/Block nodes that can
 621                    be a head. I.e., the code is "dying".  We break the loop by
 622                    setting Bad nodes. */
 623                 ir_graph *irg   = get_irn_irg(n);
 624                 ir_mode  *mode  = get_irn_mode(n);
 625                 ir_node  *bad   = new_r_Bad(irg, mode);
 626                 int       arity = get_irn_arity(n);
 627                 for (i = -1; i < arity; ++i) {
 628                         set_irn_n(n, i, bad);
 629                 }
 630                 return NULL;
 631         }
 632         assert(res_index > -2);
 633
 634         set_backedge(m, res_index);
 635         return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
 636 }
 637
 638 static inline int is_outermost_loop(ir_loop *l)
 639 {
 640         return l == get_loop_outer_loop(l);
 641 }
 642
 643 /*-----------------------------------------------------------*
 644  *                   The core algorithm.                     *
 645  *-----------------------------------------------------------*/
 646
 647 /**
 648  * The core algorithm: Find strongly coupled components.
 649  *
 650  * @param n  node to start
 651  */
 652 static void scc(ir_node *n)
 653 {
 654         if (irn_visited_else_mark(n))
 655                 return;
 656
 657         /* Initialize the node */
 658         set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
 659         set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
 660         set_irn_loop(n, NULL);
 661         ++current_dfn;
 662         push(n);
 663
 664         /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
 665            array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
 666            so is_backedge does not access array[-1] but correctly returns false! */
 667
 668         if (!is_outermost_Start(n)) {
 669                 int i, arity = get_irn_arity(n);
 670
 671                 for (i = get_start_index(n); i < arity; ++i) {
 672                         ir_node *m;
 673                         if (is_backedge(n, i))
 674                                 continue;
 675                         m = get_irn_n(n, i);
 676                         scc(m);
 677                         if (irn_is_in_stack(m)) {
 678                                 /* Uplink of m is smaller if n->m is a backedge.
 679                                    Propagate the uplink to mark the loop. */
 680                                 if (get_irn_uplink(m) < get_irn_uplink(n))
 681                                         set_irn_uplink(n, get_irn_uplink(m));
 682                         }
 683                 }
 684         }
 685
 686         if (get_irn_dfn(n) == get_irn_uplink(n)) {
 687                 /* This condition holds for
 688                    1) the node with the incoming backedge.
 689                       That is: We found a loop!
 690                    2) Straight line code, because no uplink has been propagated, so the
 691                       uplink still is the same as the dfn.
 692
 693                    But n might not be a proper loop head for the analysis. Proper loop
 694                    heads are Block and Phi nodes. find_tail() searches the stack for
 695                    Block's and Phi's and takes those nodes as loop heads for the current
 696                    loop instead and marks the incoming edge as backedge. */
 697
 698                 ir_node *tail = find_tail(n);
 699                 if (tail != NULL) {
 700                         /* We have a loop, that is no straight line code,
 701                            because we found a loop head!
 702                            Next actions: Open a new loop on the loop tree and
 703                                          try to find inner loops */
 704
 705 #if NO_LOOPS_WITHOUT_HEAD
 706                         /* This is an adaption of the algorithm from fiasco / optscc to
 707                          * avoid loops without Block or Phi as first node.  This should
 708                          * severely reduce the number of evaluations of nodes to detect
 709                          * a fixpoint in the heap analysis.
 710                          * Further it avoids loops without firm nodes that cause errors
 711                          * in the heap analyses.
 712                          * But attention:  don't do it for the outermost loop:  This loop
 713                          * is not iterated.  A first block can be a loop head in case of
 714                          * an endless recursion. */
 715
 716                         ir_loop *l;
 717                         int close;
 718                         if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
 719                                 l = new_loop();
 720                                 close = 1;
 721                         } else {
 722                                 l = current_loop;
 723                                 close = 0;
 724                         }
 725 #else
 726                         ir_loop *l = new_loop();
 727 #endif
 728
 729                         /* Remove the loop from the stack ... */
 730                         pop_scc_unmark_visit(n);
 731
 732                         /* The current backedge has been marked, that is temporarily eliminated,
 733                            by find tail. Start the scc algorithm
 734                            again on the subgraph that is left (the current loop without the backedge)
 735                            in order to find more inner loops. */
 736                         scc(tail);
 737
 738                         assert(irn_visited(n));
 739 #if NO_LOOPS_WITHOUT_HEAD
 740                         if (close)
 741 #endif
 742                                 close_loop(l);
 743                 } else {
 744                         /* No loop head was found, that is we have straight line code.
 745                            Pop all nodes from the stack to the current loop. */
 746                         pop_scc_to_loop(n);
 747                 }
 748         }
 749 }
 750
 751 /* Constructs backedge information for irg. In interprocedural view constructs
 752    backedges for all methods called by irg, too. */
 753 int construct_backedges(ir_graph *irg)
 754 {
 755         ir_graph *rem = current_ir_graph;
 756         ir_loop *head_rem;
 757         struct obstack temp;
 758
 759         max_loop_depth = 0;
 760         current_ir_graph   = irg;
 761         outermost_ir_graph = irg;
 762
 763         obstack_init(&temp);
 764         init_scc(irg, &temp);
 765
 766         current_loop = NULL;
 767         new_loop();  /* sets current_loop */
 768         head_rem = current_loop; /* Just for assertion */
 769
 770         inc_irg_visited(irg);
 771
 772         scc(get_irg_end(irg));
 773
 774         finish_scc();
 775         obstack_free(&temp, NULL);
 776
 777         assert(head_rem == current_loop);
 778         mature_loops(current_loop, irg->obst);
 779         set_irg_loop(irg, current_loop);
 780         set_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_LOOPINFO);
 781         assert(get_irg_loop(irg)->kind == k_ir_loop);
 782         current_ir_graph = rem;
 783         return max_loop_depth;
 784 }
 785
 786 static void reset_backedges(ir_node *n)
 787 {
 788         if (is_possible_loop_head(n)) {
 789                 clear_backedges(n);
 790         }
 791 }
 792
 793 /*
 794 static void loop_reset_backedges(ir_loop *l)
 795 {
 796         int i;
 797         reset_backedges(get_loop_node(l, 0));
 798         for (i = 0; i < get_loop_n_nodes(l); ++i)
 799                 set_irn_loop(get_loop_node(l, i), NULL);
 800         for (i = 0; i < get_loop_n_sons(l); ++i) {
 801                 loop_reset_backedges(get_loop_son(l, i));
 802         }
 803 }
 804 */
 805
 806 static void loop_reset_node(ir_node *n, void *env)
 807 {
 808         (void) env;
 809         set_irn_loop(n, NULL);
 810         reset_backedges(n);
 811 }
 812
 813 /** Removes all loop information.
 814     Resets all backedges */
 815 void free_loop_information(ir_graph *irg)
 816 {
 817         /* We can not use this recursion, as the loop might contain
 818            illegal nodes by now.  Why else would we throw away the
 819            representation?
 820         if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
 821         */
 822         irg_walk_graph(irg, loop_reset_node, NULL, NULL);
 823         set_irg_loop(irg, NULL);
 824         clear_irg_state(current_ir_graph, IR_GRAPH_STATE_CONSISTENT_LOOPINFO);
 825         /* We cannot free the loop nodes, they are on the obstack. */
 826 }
 827
 828 void free_all_loop_information(void)
 829 {
 830         size_t i;
 831         for (i = 0; i < get_irp_n_irgs(); i++) {
 832                 free_loop_information(get_irp_irg(i));
 833         }
 834 }
 835
 836 /* ------------------------------------------------------------------- */
 837 /* Simple analyses based on the loop information                       */
 838 /* ------------------------------------------------------------------- */
 839
 840 static int is_loop_variant(ir_loop *l, ir_loop *b)
 841 {
 842         size_t i, n_elems;
 843
 844         if (l == b) return 1;
 845
 846         n_elems = get_loop_n_elements(l);
 847         for (i = 0; i < n_elems; ++i) {
 848                 loop_element e = get_loop_element(l, i);
 849                 if (is_ir_loop(e.kind))
 850                         if (is_loop_variant(e.son, b))
 851                                 return 1;
 852         }
 853
 854         return 0;
 855 }
 856
 857 /* Test whether a value is loop invariant.
 858  *
 859  * @param n      The node to be tested.
 860  * @param block  A block node.  We pass the block, not the loop as we must
 861  *               start off with a block loop to find all proper uses.
 862  *
 863  * Returns non-zero, if the node n is not changed in the loop block
 864  * belongs to or in inner loops of this blocks loop. */
 865 int is_loop_invariant(const ir_node *n, const ir_node *block)
 866 {
 867         ir_loop *l = get_irn_loop(block);
 868         const ir_node *b = is_Block(n) ? n : get_nodes_block(n);
 869         return !is_loop_variant(l, get_irn_loop(b));
 870 }