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