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  * @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 unsigned 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 = (scc_info*) 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 = (scc_info*) 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 = (scc_info*) 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 = (scc_info*) 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 = (scc_info*) 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 = (scc_info*) 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 = (scc_info*) 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 size_t 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                 size_t 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;
 247
 248         assert(tos > 0);
 249         n = stack[--tos];
 250         mark_irn_not_in_stack(n);
 251         return n;
 252 }
 253
 254 /**
 255  * The nodes up to n belong to the current loop.
 256  * Removes them from the stack and adds them to the current loop.
 257  */
 258 static inline void pop_scc_to_loop(ir_node *n)
 259 {
 260         ir_node *m;
 261
 262         do {
 263                 m = pop();
 264
 265                 loop_node_cnt++;
 266                 set_irn_dfn(m, loop_node_cnt);
 267                 add_loop_node(current_loop, m);
 268                 set_irn_loop(m, current_loop);
 269         } while (m != n);
 270 }
 271
 272 /* GL ??? my last son is my grandson???  Removes loops with no
 273    ir_nodes in them.  Such loops have only another loop as son. (Why
 274    can't they have two loops as sons? Does it never get that far? ) */
 275 static void close_loop(ir_loop *l)
 276 {
 277         size_t last = get_loop_n_elements(l) - 1;
 278         loop_element lelement = get_loop_element(l, last);
 279         ir_loop *last_son = lelement.son;
 280
 281         if (get_kind(last_son) == k_ir_loop &&
 282                 get_loop_n_elements(last_son) == 1) {
 283                         ir_loop *gson;
 284
 285                         lelement = get_loop_element(last_son, 0);
 286                         gson = lelement.son;
 287
 288                         if (get_kind(gson) == k_ir_loop) {
 289                                 loop_element new_last_son;
 290
 291                                 gson->outer_loop = l;
 292                                 new_last_son.son = gson;
 293                                 l->children[last] = new_last_son;
 294                         }
 295         }
 296
 297         current_loop = l;
 298 }
 299
 300 /* Removes and unmarks all nodes up to n from the stack.
 301    The nodes must be visited once more to assign them to a scc. */
 302 static inline void pop_scc_unmark_visit(ir_node *n)
 303 {
 304         ir_node *m = NULL;
 305
 306         while (m != n) {
 307                 m = pop();
 308                 set_irn_visited(m, 0);
 309         }
 310 }
 311
 312 /**********************************************************************/
 313 /* The loop datastructure.                                           **/
 314 /**********************************************************************/
 315
 316 /* Allocates a new loop as son of current_loop.  Sets current_loop
 317    to the new loop and returns the father. */
 318 static ir_loop *new_loop(void)
 319 {
 320         ir_loop *father = current_loop;
 321         ir_loop *son    = alloc_loop(father, outermost_ir_graph->obst);
 322
 323         if (son->depth > max_loop_depth) max_loop_depth = son->depth;
 324         current_loop = son;
 325         return father;
 326 }
 327
 328 /**********************************************************************/
 329 /* Constructing and destructing the loop/backedge information.       **/
 330 /**********************************************************************/
 331
 332 /* Initialization steps. **********************************************/
 333
 334 static inline void init_node(ir_node *n, void *env)
 335 {
 336         struct obstack *obst = (struct obstack*) env;
 337         set_irn_link(n, new_scc_info(obst));
 338         clear_backedges(n);
 339 }
 340
 341 static inline void init_scc_common(void)
 342 {
 343         current_dfn = 1;
 344         loop_node_cnt = 0;
 345         init_stack();
 346 }
 347
 348 static inline void init_scc(ir_graph *irg, struct obstack *obst)
 349 {
 350         init_scc_common();
 351         irg_walk_graph(irg, init_node, NULL, obst);
 352         /*
 353         irg_walk (irg, link_to_reg_end, NULL, NULL);
 354         */
 355 }
 356
 357 static inline void finish_scc(void)
 358 {
 359         finish_stack();
 360 }
 361
 362 /**
 363  * Check weather a given node represents the outer most Start
 364  * block. In intra-procedural view this is the start block of the
 365  * current graph, in interprocedural view it is the start block
 366  * of the outer most graph.
 367  *
 368  * @param n  the node to check
 369  *
 370  * This is the condition for breaking the scc recursion.
 371  */
 372 static int is_outermost_Start(ir_node *n)
 373 {
 374         /* Test whether this is the outermost Start node. */
 375         if (is_Block(n) && get_Block_n_cfgpreds(n) == 1) {
 376                 ir_node *pred = skip_Proj(get_Block_cfgpred(n, 0));
 377             if (is_Start(pred) && get_nodes_block(pred) == n)
 378                         return 1;
 379         }
 380         return 0;
 381 }
 382
 383 /* When to walk from nodes to blocks. Only for Control flow operations? */
 384 static inline int get_start_index(ir_node *n)
 385 {
 386 #undef BLOCK_BEFORE_NODE
 387 #define BLOCK_BEFORE_NODE 1
 388
 389 #if BLOCK_BEFORE_NODE
 390
 391         /* This version assures, that all nodes are ordered absolutely.  This allows
 392            to undef all nodes in the heap analysis if the block is false, which
 393            means not reachable.
 394            I.e., with this code, the order on the loop tree is correct. But a
 395            (single) test showed the loop tree is deeper. */
 396         if (get_irn_op(n) == op_Phi  ||
 397             is_Block(n)              ||
 398             (get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
 399               get_irn_pinned(n)              == op_pin_state_floats))
 400                 // Here we could test for backedge at -1 which is illegal
 401                 return 0;
 402         else
 403                 return -1;
 404
 405 #else
 406
 407         /* This version causes deeper loop trees (at least we verified this
 408            for Polymor).
 409            But it guarantees that Blocks are analysed before nodes contained in the
 410            block.  If so, we can set the value to undef if the block is not \
 411            executed. */
 412         if (is_cfop(n) || is_fragile_op(n) || is_Start(n))
 413                 return -1;
 414         else
 415                 return 0;
 416
 417 #endif
 418 }
 419
 420 /**
 421  * Return non-zero if the given node is a legal loop header:
 422  * Block, Phi
 423  *
 424  * @param n  the node to check
 425  */
 426 static inline int is_possible_loop_head(ir_node *n)
 427 {
 428         ir_op *op = get_irn_op(n);
 429         return ((op == op_Block) ||
 430                 (op == op_Phi));
 431 }
 432
 433 /**
 434  * Returns non-zero if n is a loop header, i.e., it is a Block or Phi
 435  * node and has predecessors within the loop and out of the loop.
 436  *
 437  * @param n    the node to check
 438  * @param root only needed for assertion.
 439  */
 440 static int is_head(ir_node *n, ir_node *root)
 441 {
 442         int i, arity;
 443         int some_outof_loop = 0, some_in_loop = 0;
 444
 445         /* Test for legal loop header: Block, Phi, ... */
 446         if (!is_possible_loop_head(n))
 447                 return 0;
 448
 449         if (!is_outermost_Start(n)) {
 450 #ifndef NDEBUG
 451                 int uplink = get_irn_uplink(root);
 452 #else
 453                 (void) root;
 454 #endif
 455                 arity = get_irn_arity(n);
 456                 for (i = get_start_index(n); i < arity; i++) {
 457                         ir_node *pred;
 458                         if (is_backedge(n, i))
 459                                 continue;
 460                         pred = get_irn_n(n, i);
 461                         if (! irn_is_in_stack(pred)) {
 462                                 some_outof_loop = 1;
 463                         } else {
 464                                 assert(get_irn_uplink(pred) >= uplink);
 465                                 some_in_loop = 1;
 466                         }
 467                 }
 468         }
 469         return some_outof_loop & some_in_loop;
 470 }
 471
 472 /**
 473  * Returns non-zero if n is possible loop head of an endless loop.
 474  * I.e., it is a Block or Phi node and has only predecessors
 475  * within the loop.
 476  *
 477  * @param n    the node to check
 478  * @param root only needed for assertion.
 479  */
 480 static int is_endless_head(ir_node *n, ir_node *root)
 481 {
 482         int i, arity;
 483         int none_outof_loop = 1, some_in_loop = 0;
 484
 485         /* Test for legal loop header: Block, Phi, ... */
 486         if (!is_possible_loop_head(n))
 487                 return 0;
 488
 489         if (!is_outermost_Start(n)) {
 490 #ifndef NDEBUG
 491                 int uplink = get_irn_uplink(root);
 492 #else
 493                 (void) root;
 494 #endif
 495                 arity = get_irn_arity(n);
 496                 for (i = get_start_index(n); i < arity; i++) {
 497                         ir_node *pred;
 498                         if (is_backedge(n, i))
 499                                 continue;
 500                         pred = get_irn_n(n, i);
 501                         if (!irn_is_in_stack(pred)) {
 502                                 none_outof_loop = 0;
 503                         } else {
 504                                 assert(get_irn_uplink(pred) >= uplink);
 505                                 some_in_loop = 1;
 506                         }
 507                 }
 508         }
 509         return none_outof_loop & some_in_loop;
 510 }
 511
 512 /** Returns index of the predecessor with the smallest dfn number
 513     greater-equal than limit. */
 514 static int smallest_dfn_pred(ir_node *n, int limit)
 515 {
 516         int i, index = -2, min = -1;
 517
 518         if (!is_outermost_Start(n)) {
 519                 int arity = get_irn_arity(n);
 520                 for (i = get_start_index(n); i < arity; i++) {
 521                         ir_node *pred = get_irn_n(n, i);
 522                         if (is_backedge(n, i) || !irn_is_in_stack(pred))
 523                                 continue;
 524                         if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
 525                                 index = i;
 526                                 min = get_irn_dfn(pred);
 527                         }
 528                 }
 529         }
 530         return index;
 531 }
 532
 533 /**
 534  * Returns index of the predecessor with the largest dfn number.
 535  */
 536 static int largest_dfn_pred(ir_node *n)
 537 {
 538         int i, index = -2, max = -1;
 539
 540         if (!is_outermost_Start(n)) {
 541                 int arity = get_irn_arity(n);
 542                 for (i = get_start_index(n); i < arity; i++) {
 543                         ir_node *pred = get_irn_n(n, i);
 544                         if (is_backedge (n, i) || !irn_is_in_stack(pred))
 545                                 continue;
 546                         if (get_irn_dfn(pred) > max) {
 547                                 index = i;
 548                                 max = get_irn_dfn(pred);
 549                         }
 550                 }
 551         }
 552         return index;
 553 }
 554
 555 /**
 556  * Searches the stack for possible loop heads.  Tests these for backedges.
 557  * If it finds a head with an unmarked backedge it marks this edge and
 558  * returns the tail of the loop.
 559  * If it finds no backedge returns NULL.
 560  * ("disable_backedge" in fiasco)
 561  *
 562  * @param n  A node where uplink == dfn.
 563  */
 564 static ir_node *find_tail(ir_node *n)
 565 {
 566         ir_node *m;
 567         int i, res_index = -2;
 568
 569         /*
 570         if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
 571          */
 572         m = stack[tos-1];  /* tos = top of stack */
 573         if (is_head(m, n)) {
 574                 res_index = smallest_dfn_pred(m, 0);
 575                 if ((res_index == -2) &&  /* no smallest dfn pred found. */
 576                         (n ==  m))
 577                         return NULL;
 578         } else {
 579                 if (m == n) return NULL;    // Is this to catch Phi - self loops?
 580                 for (i = tos-2; i >= 0; --i) {
 581                         m = stack[i];
 582
 583                         if (is_head(m, n)) {
 584                                 res_index = smallest_dfn_pred(m, get_irn_dfn(m) + 1);
 585                                 if (res_index == -2)  /* no smallest dfn pred found. */
 586                                         res_index = largest_dfn_pred(m);
 587
 588                                 if ((m == n) && (res_index == -2)) {  /* don't walk past loop head. */
 589                                         i = -1;
 590                                 }
 591                                 break;
 592                         }
 593
 594                         /* We should not walk past our selves on the stack:  The upcoming nodes
 595                            are not in this loop. We assume a loop not reachable from Start. */
 596                         if (m == n) {
 597                                 i = -1;
 598                                 break;
 599                         }
 600                 }
 601
 602                 if (i < 0) {
 603                         /* A dead loop not reachable from Start. */
 604                         for (i = tos-2; i >= 0; --i) {
 605                                 m = stack[i];
 606                                 if (is_endless_head(m, n)) {
 607                                         res_index = smallest_dfn_pred(m, get_irn_dfn(m) + 1);
 608                                         if (res_index == -2)  /* no smallest dfn pred found. */
 609                                                 res_index = largest_dfn_pred (m);
 610                                         break;
 611                                 }
 612                                 if (m == n) { break; }  /* It's not an unreachable loop, either. */
 613                         }
 614                         //assert(0 && "no head found on stack");
 615                 }
 616
 617         }
 618         if (res_index <= -2) {
 619                 /* It's a completely bad loop: without Phi/Block nodes that can
 620                    be a head. I.e., the code is "dying".  We break the loop by
 621                    setting Bad nodes. */
 622                 ir_graph *irg   = get_irn_irg(n);
 623                 ir_mode  *mode  = get_irn_mode(n);
 624                 ir_node  *bad   = new_r_Bad(irg, mode);
 625                 int       arity = get_irn_arity(n);
 626                 for (i = -1; i < arity; ++i) {
 627                         set_irn_n(n, i, bad);
 628                 }
 629                 return NULL;
 630         }
 631         assert(res_index > -2);
 632
 633         set_backedge(m, res_index);
 634         return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
 635 }
 636
 637 static inline int is_outermost_loop(ir_loop *l)
 638 {
 639         return l == get_loop_outer_loop(l);
 640 }
 641
 642 /*-----------------------------------------------------------*
 643  *                   The core algorithm.                     *
 644  *-----------------------------------------------------------*/
 645
 646 /**
 647  * The core algorithm: Find strongly coupled components.
 648  *
 649  * @param n  node to start
 650  */
 651 static void scc(ir_node *n)
 652 {
 653         if (irn_visited_else_mark(n))
 654                 return;
 655
 656         /* Initialize the node */
 657         set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
 658         set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
 659         set_irn_loop(n, NULL);
 660         ++current_dfn;
 661         push(n);
 662
 663         /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
 664            array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
 665            so is_backedge does not access array[-1] but correctly returns false! */
 666
 667         if (!is_outermost_Start(n)) {
 668                 int i, arity = get_irn_arity(n);
 669
 670                 for (i = get_start_index(n); i < arity; ++i) {
 671                         ir_node *m;
 672                         if (is_backedge(n, i))
 673                                 continue;
 674                         m = get_irn_n(n, i);
 675                         scc(m);
 676                         if (irn_is_in_stack(m)) {
 677                                 /* Uplink of m is smaller if n->m is a backedge.
 678                                    Propagate the uplink to mark the loop. */
 679                                 if (get_irn_uplink(m) < get_irn_uplink(n))
 680                                         set_irn_uplink(n, get_irn_uplink(m));
 681                         }
 682                 }
 683         }
 684
 685         if (get_irn_dfn(n) == get_irn_uplink(n)) {
 686                 /* This condition holds for
 687                    1) the node with the incoming backedge.
 688                       That is: We found a loop!
 689                    2) Straight line code, because no uplink has been propagated, so the
 690                       uplink still is the same as the dfn.
 691
 692                    But n might not be a proper loop head for the analysis. Proper loop
 693                    heads are Block and Phi nodes. find_tail() searches the stack for
 694                    Block's and Phi's and takes those nodes as loop heads for the current
 695                    loop instead and marks the incoming edge as backedge. */
 696
 697                 ir_node *tail = find_tail(n);
 698                 if (tail != NULL) {
 699                         /* We have a loop, that is no straight line code,
 700                            because we found a loop head!
 701                            Next actions: Open a new loop on the loop tree and
 702                                          try to find inner loops */
 703
 704 #if NO_LOOPS_WITHOUT_HEAD
 705                         /* This is an adaption of the algorithm from fiasco / optscc to
 706                          * avoid loops without Block or Phi as first node.  This should
 707                          * severely reduce the number of evaluations of nodes to detect
 708                          * a fixpoint in the heap analysis.
 709                          * Further it avoids loops without firm nodes that cause errors
 710                          * in the heap analyses.
 711                          * But attention:  don't do it for the outermost loop:  This loop
 712                          * is not iterated.  A first block can be a loop head in case of
 713                          * an endless recursion. */
 714
 715                         ir_loop *l;
 716                         int close;
 717                         if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
 718                                 l = new_loop();
 719                                 close = 1;
 720                         } else {
 721                                 l = current_loop;
 722                                 close = 0;
 723                         }
 724 #else
 725                         ir_loop *l = new_loop();
 726 #endif
 727
 728                         /* Remove the loop from the stack ... */
 729                         pop_scc_unmark_visit(n);
 730
 731                         /* The current backedge has been marked, that is temporarily eliminated,
 732                            by find tail. Start the scc algorithm
 733                            again on the subgraph that is left (the current loop without the backedge)
 734                            in order to find more inner loops. */
 735                         scc(tail);
 736
 737                         assert(irn_visited(n));
 738 #if NO_LOOPS_WITHOUT_HEAD
 739                         if (close)
 740 #endif
 741                                 close_loop(l);
 742                 } else {
 743                         /* No loop head was found, that is we have straight line code.
 744                            Pop all nodes from the stack to the current loop. */
 745                         pop_scc_to_loop(n);
 746                 }
 747         }
 748 }
 749
 750 /* Constructs backedge information for irg. In interprocedural view constructs
 751    backedges for all methods called by irg, too. */
 752 int construct_backedges(ir_graph *irg)
 753 {
 754         ir_graph *rem = current_ir_graph;
 755         ir_loop *head_rem;
 756         struct obstack temp;
 757
 758         max_loop_depth = 0;
 759         current_ir_graph   = irg;
 760         outermost_ir_graph = irg;
 761
 762         obstack_init(&temp);
 763         init_scc(irg, &temp);
 764
 765         current_loop = NULL;
 766         new_loop();  /* sets current_loop */
 767         head_rem = current_loop; /* Just for assertion */
 768
 769         inc_irg_visited(irg);
 770
 771         scc(get_irg_end(irg));
 772
 773         finish_scc();
 774         obstack_free(&temp, NULL);
 775
 776         assert(head_rem == current_loop);
 777         mature_loops(current_loop, irg->obst);
 778         set_irg_loop(irg, current_loop);
 779         set_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_LOOPINFO);
 780         assert(get_irg_loop(irg)->kind == k_ir_loop);
 781         current_ir_graph = rem;
 782         return max_loop_depth;
 783 }
 784
 785 static void reset_backedges(ir_node *n)
 786 {
 787         if (is_possible_loop_head(n)) {
 788                 clear_backedges(n);
 789         }
 790 }
 791
 792 /*
 793 static void loop_reset_backedges(ir_loop *l)
 794 {
 795         int i;
 796         reset_backedges(get_loop_node(l, 0));
 797         for (i = 0; i < get_loop_n_nodes(l); ++i)
 798                 set_irn_loop(get_loop_node(l, i), NULL);
 799         for (i = 0; i < get_loop_n_sons(l); ++i) {
 800                 loop_reset_backedges(get_loop_son(l, i));
 801         }
 802 }
 803 */
 804
 805 static void loop_reset_node(ir_node *n, void *env)
 806 {
 807         (void) env;
 808         set_irn_loop(n, NULL);
 809         reset_backedges(n);
 810 }
 811
 812 /** Removes all loop information.
 813     Resets all backedges */
 814 void free_loop_information(ir_graph *irg)
 815 {
 816         /* We can not use this recursion, as the loop might contain
 817            illegal nodes by now.  Why else would we throw away the
 818            representation?
 819         if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
 820         */
 821         irg_walk_graph(irg, loop_reset_node, NULL, NULL);
 822         set_irg_loop(irg, NULL);
 823         clear_irg_state(current_ir_graph, IR_GRAPH_STATE_CONSISTENT_LOOPINFO);
 824         /* We cannot free the loop nodes, they are on the obstack. */
 825 }
 826
 827 void free_all_loop_information(void)
 828 {
 829         size_t i;
 830         for (i = 0; i < get_irp_n_irgs(); i++) {
 831                 free_loop_information(get_irp_irg(i));
 832         }
 833 }
 834
 835 /* ------------------------------------------------------------------- */
 836 /* Simple analyses based on the loop information                       */
 837 /* ------------------------------------------------------------------- */
 838
 839 static int is_loop_variant(ir_loop *l, ir_loop *b)
 840 {
 841         size_t i, n_elems;
 842
 843         if (l == b) return 1;
 844
 845         n_elems = get_loop_n_elements(l);
 846         for (i = 0; i < n_elems; ++i) {
 847                 loop_element e = get_loop_element(l, i);
 848                 if (is_ir_loop(e.kind))
 849                         if (is_loop_variant(e.son, b))
 850                                 return 1;
 851         }
 852
 853         return 0;
 854 }
 855
 856 /* Test whether a value is loop invariant.
 857  *
 858  * @param n      The node to be tested.
 859  * @param block  A block node.  We pass the block, not the loop as we must
 860  *               start off with a block loop to find all proper uses.
 861  *
 862  * Returns non-zero, if the node n is not changed in the loop block
 863  * belongs to or in inner loops of this blocks loop. */
 864 int is_loop_invariant(const ir_node *n, const ir_node *block)
 865 {
 866         ir_loop *l = get_irn_loop(block);
 867         const ir_node *b = is_Block(n) ? n : get_nodes_block(n);
 868         return !is_loop_variant(l, get_irn_loop(b));
 869 }