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