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