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