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