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