nsz Git - libfirm/blob - ir/ana/ircfscc.c

   1 /*
   2  * Copyright (C) 1995-2007 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   if (is_Block(n))
 309     set_irn_link (n, new_scc_info());
 310   clear_backedges(n);
 311 }
 312
 313 /**
 314  * Initializes the common global settings for the scc algorithm
 315  */
 316 static INLINE void
 317 init_scc_common (void) {
 318   current_dfn   = 1;
 319   loop_node_cnt = 0;
 320   init_stack();
 321 }
 322
 323 /**
 324  * Initializes the scc algorithm for the intraprocedural case.
 325  * Add scc info to every block node.
 326  */
 327 static INLINE void
 328 init_scc (ir_graph *irg) {
 329   init_scc_common();
 330   irg_walk_graph(irg, init_node, NULL, NULL);
 331 }
 332
 333 /**
 334  * Initializes the scc algorithm for the interprocedural case.
 335  */
 336 static INLINE void
 337 init_ip_scc (void) {
 338   init_scc_common();
 339   cg_walk (init_node, NULL, NULL);
 340
 341 #if EXPERIMENTAL_CFLOOP_TREE
 342   cg_walk (link_to_reg_end, NULL, NULL);
 343 #endif
 344 }
 345
 346 /**
 347  * Condition for breaking the recursion: n is the block
 348  * that gets the initial control flow from the Start node.
 349  */
 350 static int is_outermost_StartBlock(ir_node *n) {
 351   /* Test whether this is the outermost Start node.  If so
 352      recursion must end. */
 353   assert(is_Block(n));
 354   if ((get_Block_n_cfgpreds(n) == 1)  &&
 355       (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
 356       (get_nodes_block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
 357     return 1;
 358   }
 359   return 0;
 360 }
 361
 362 /** Returns non-zero if n is a loop header, i.e., it is a Block node
 363  *  and has predecessors within the cfloop and out of the cfloop.
 364  *
 365  *  @param n     the block node to check
 366  *  @param root  only needed for assertion.
 367  */
 368 static int
 369 is_head (ir_node *n, ir_node *root)
 370 {
 371   int i, arity;
 372   int some_outof_loop = 0, some_in_loop = 0;
 373
 374   assert(is_Block(n));
 375
 376   if (!is_outermost_StartBlock(n)) {
 377     arity = get_irn_arity(n);
 378     for (i = 0; i < arity; i++) {
 379       ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
 380       if (is_backedge(n, i)) continue;
 381       if (!irn_is_in_stack(pred)) {
 382         some_outof_loop = 1;
 383       } else {
 384         if (get_irn_uplink(pred) < get_irn_uplink(root))  {
 385           assert(get_irn_uplink(pred) >= get_irn_uplink(root));
 386         }
 387         some_in_loop = 1;
 388       }
 389     }
 390   }
 391   return some_outof_loop & some_in_loop;
 392 }
 393
 394
 395 /**
 396  * Returns non-zero if n is possible loop head of an endless loop.
 397  * I.e., it is a Block, Phi or Filter node and has only predecessors
 398  * within the loop.
 399  *
 400  * @param n     the block node to check
 401  * @param root  only needed for assertion.
 402  */
 403 static int
 404 is_endless_head (ir_node *n, ir_node *root)
 405 {
 406   int i, arity;
 407   int some_outof_loop = 0, some_in_loop = 0;
 408
 409   assert(is_Block(n));
 410   /* Test for legal loop header: Block, Phi, ... */
 411   if (!is_outermost_StartBlock(n)) {
 412     arity = get_irn_arity(n);
 413     for (i = 0; i < arity; i++) {
 414       ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
 415       assert(pred);
 416       if (is_backedge(n, i)) { continue; }
 417       if (!irn_is_in_stack(pred)) {
 418               some_outof_loop = 1; //printf(" some out of loop ");
 419       } else {
 420               if(get_irn_uplink(pred) < get_irn_uplink(root)) {
 421                 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
 422               }
 423               some_in_loop = 1;
 424       }
 425     }
 426   }
 427   return !some_outof_loop && some_in_loop;
 428 }
 429
 430 /**
 431  * Returns index of the predecessor with the smallest dfn number
 432  * greater-equal than limit.
 433  */
 434 static int
 435 smallest_dfn_pred (ir_node *n, int limit)
 436 {
 437   int i, index = -2, min = -1;
 438
 439   if (!is_outermost_StartBlock(n)) {
 440     int arity = get_irn_arity(n);
 441     for (i = 0; i < arity; i++) {
 442       ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
 443       if (is_backedge(n, i) || !irn_is_in_stack(pred))
 444         continue;
 445       if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
 446               index = i;
 447               min = get_irn_dfn(pred);
 448       }
 449     }
 450   }
 451   return index;
 452 }
 453
 454 /**
 455  * Returns index of the predecessor with the largest dfn number.
 456  */
 457 static int
 458 largest_dfn_pred (ir_node *n)
 459 {
 460   int i, index = -2, max = -1;
 461
 462   if (!is_outermost_StartBlock(n)) {
 463     int arity = get_irn_arity(n);
 464     for (i = 0; i < arity; i++) {
 465       ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
 466       if (is_backedge (n, i) || !irn_is_in_stack(pred))
 467         continue;
 468       if (get_irn_dfn(pred) > max) {
 469               index = i;
 470               max = get_irn_dfn(pred);
 471       }
 472     }
 473   }
 474   return index;
 475 }
 476
 477 /**
 478  * Searches the stack for possible loop heads.  Tests these for backedges.
 479  * If it finds a head with an unmarked backedge it marks this edge and
 480  * returns the tail of the loop.
 481  * If it finds no backedge returns NULL.
 482  */
 483 static ir_node *
 484 find_tail (ir_node *n) {
 485   ir_node *m;
 486   int i, res_index = -2;
 487
 488   m = stack[tos-1];  /* tos = top of stack */
 489   if (is_head(m, n)) {
 490     res_index = smallest_dfn_pred(m, 0);
 491     if ((res_index == -2) &&  /* no smallest dfn pred found. */
 492               (n ==  m))
 493       return NULL;
 494   } else {
 495     if (m == n) return NULL;
 496     for (i = tos-2; i >= 0; --i) {
 497
 498       m = stack[i];
 499       if (is_head (m, n)) {
 500               res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
 501               if (res_index == -2)  /* no smallest dfn pred found. */
 502                 res_index = largest_dfn_pred (m);
 503
 504               if ((m == n) && (res_index == -2)) {
 505                 i = -1;
 506               }
 507               break;
 508       }
 509
 510
 511       /* We should not walk past our selves on the stack:  The upcoming nodes
 512                are not in this loop. We assume a loop not reachable from Start. */
 513       if (m == n) {
 514               i = -1;
 515               break;
 516       }
 517     }
 518
 519     if (i < 0) {
 520       /* A dead loop not reachable from Start. */
 521       for (i = tos-2; i >= 0; --i) {
 522               m = stack[i];
 523               if (is_endless_head (m, n)) {
 524                 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
 525                 if (res_index == -2)  /* no smallest dfn pred found. */
 526                   res_index = largest_dfn_pred (m);
 527                 break;
 528               }
 529               if (m == n) break;   /* It's not an unreachable loop, either. */
 530       }
 531       //assert(0 && "no head found on stack");
 532     }
 533
 534   }
 535   assert (res_index > -2);
 536
 537   set_backedge (m, res_index);
 538   return is_outermost_StartBlock(n) ? NULL : get_nodes_block(skip_Proj(get_irn_n(m, res_index)));
 539 }
 540
 541 /**
 542  * returns non.zero if l is the outermost loop.
 543  */
 544 INLINE static int
 545 is_outermost_loop(ir_loop *l) {
 546   return l == get_loop_outer_loop(l);
 547 }
 548
 549 /*-----------------------------------------------------------*
 550  *                   The core algorithm.                     *
 551  *-----------------------------------------------------------*/
 552
 553 /**
 554  * Walks over all blocks of a graph
 555  */
 556 static void cfscc (ir_node *n) {
 557   int i;
 558
 559   assert(is_Block(n));
 560
 561   if (irn_visited(n)) return;
 562   mark_irn_visited(n);
 563
 564   /* Initialize the node */
 565   set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
 566   set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
 567   set_irn_loop(n, NULL);
 568   ++current_dfn;
 569   push(n);
 570
 571   if (!is_outermost_StartBlock(n)) {
 572     int arity = get_irn_arity(n);
 573
 574     for (i = 0; i < arity; i++) {
 575       ir_node *m;
 576
 577       if (is_backedge(n, i))
 578         continue;
 579       m = get_nodes_block(skip_Proj(get_irn_n(n, i)));
 580
 581       cfscc(m);
 582       if (irn_is_in_stack(m)) {
 583               /* Uplink of m is smaller if n->m is a backedge.
 584                  Propagate the uplink to mark the cfloop. */
 585               if (get_irn_uplink(m) < get_irn_uplink(n))
 586                 set_irn_uplink(n, get_irn_uplink(m));
 587       }
 588     }
 589   }
 590
 591   if (get_irn_dfn(n) == get_irn_uplink(n)) {
 592     /* This condition holds for
 593        1) the node with the incoming backedge.
 594           That is: We found a cfloop!
 595        2) Straight line code, because no uplink has been propagated, so the
 596           uplink still is the same as the dfn.
 597
 598        But n might not be a proper cfloop head for the analysis. Proper cfloop
 599        heads are Block and Phi nodes. find_tail searches the stack for
 600        Block's and Phi's and takes those nodes as cfloop heads for the current
 601        cfloop instead and marks the incoming edge as backedge. */
 602
 603     ir_node *tail = find_tail(n);
 604     if (tail) {
 605       /* We have a cfloop, that is no straight line code,
 606          because we found a cfloop head!
 607          Next actions: Open a new cfloop on the cfloop tree and
 608          try to find inner cfloops */
 609
 610 #if NO_CFLOOPS_WITHOUT_HEAD
 611
 612       /* This is an adaption of the algorithm from fiasco / optscc to
 613        * avoid cfloops without Block or Phi as first node.  This should
 614        * severely reduce the number of evaluations of nodes to detect
 615        * a fixpoint in the heap analysis.
 616        * Further it avoids cfloops without firm nodes that cause errors
 617        * in the heap analyses. */
 618
 619       ir_loop *l;
 620       int close;
 621       if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
 622               l = new_loop();
 623               close = 1;
 624       } else {
 625               l = current_loop;
 626               close = 0;
 627       }
 628
 629 #else
 630
 631       ir_loop *l = new_loop();
 632
 633 #endif
 634
 635       /* Remove the cfloop from the stack ... */
 636       pop_scc_unmark_visit (n);
 637
 638       /* The current backedge has been marked, that is temporarily eliminated,
 639                by find tail. Start the scc algorithm
 640                anew on the subgraph thats left (the current cfloop without the backedge)
 641                in order to find more inner cfloops. */
 642
 643       cfscc (tail);
 644
 645       assert (irn_visited(n));
 646 #if NO_CFLOOPS_WITHOUT_HEAD
 647       if (close)
 648 #endif
 649         close_loop(l);
 650     }
 651     else {
 652             /* AS: No cfloop head was found, that is we have straight line code.
 653                    Pop all nodes from the stack to the current cfloop. */
 654       pop_scc_to_loop(n);
 655     }
 656   }
 657 }
 658
 659 /* Constructs control flow backedge information for irg. */
 660 int construct_cf_backedges(ir_graph *irg) {
 661   ir_graph *rem = current_ir_graph;
 662   ir_loop *head_rem;
 663   ir_node *end = get_irg_end(irg);
 664   int i;
 665
 666   assert(!get_interprocedural_view() &&
 667      "use construct_ip_cf_backedges()");
 668   max_loop_depth = 0;
 669
 670   current_ir_graph   = irg;
 671   outermost_ir_graph = irg;
 672
 673   init_scc(current_ir_graph);
 674
 675   current_loop = NULL;
 676   new_loop();  /* sets current_loop */
 677   head_rem = current_loop; /* Just for assertion */
 678
 679   inc_irg_visited(current_ir_graph);
 680
 681   /* walk over all blocks of the graph, including keep alives */
 682   cfscc(get_irg_end_block(current_ir_graph));
 683   for (i = 0; i < get_End_n_keepalives(end); i++) {
 684     ir_node *el = get_End_keepalive(end, i);
 685     if (is_Block(el)) cfscc(el);
 686   }
 687
 688   assert(head_rem == current_loop);
 689   set_irg_loop(current_ir_graph, current_loop);
 690   set_irg_loopinfo_state(current_ir_graph, loopinfo_cf_consistent);
 691   assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
 692
 693   current_ir_graph = rem;
 694   return max_loop_depth;
 695 }
 696
 697
 698 int construct_ip_cf_backedges (void) {
 699   ir_graph *rem = current_ir_graph;
 700   int rem_ipv = get_interprocedural_view();
 701   int i;
 702
 703   assert(get_irp_ip_view_state() == ip_view_valid);
 704   max_loop_depth = 0;
 705   outermost_ir_graph = get_irp_main_irg();
 706
 707   init_ip_scc();
 708
 709   current_loop = NULL;
 710   new_loop();  /* sets current_loop */
 711   set_interprocedural_view(1);
 712
 713   inc_max_irg_visited();
 714   for (i = 0; i < get_irp_n_irgs(); i++)
 715     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
 716
 717   /** We have to start the walk at the same nodes as cg_walk. **/
 718   /* Walk starting at unreachable procedures. Only these
 719    * have End blocks visible in interprocedural view. */
 720   for (i = 0; i < get_irp_n_irgs(); i++) {
 721     ir_node *sb;
 722     current_ir_graph = get_irp_irg(i);
 723
 724     sb = get_irg_start_block(current_ir_graph);
 725
 726     if ((get_Block_n_cfgpreds(sb) > 1) ||
 727         (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
 728
 729     cfscc(get_irg_end_block(current_ir_graph));
 730   }
 731
 732   /* Check whether we walked all procedures: there could be procedures
 733      with cyclic calls but no call from the outside. */
 734   for (i = 0; i < get_irp_n_irgs(); i++) {
 735     ir_node *sb;
 736     current_ir_graph = get_irp_irg(i);
 737
 738     /* Test start block: if inner procedure end and end block are not
 739      * visible and therefore not marked. */
 740     sb = get_irg_start_block(current_ir_graph);
 741     if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) cfscc(sb);
 742   }
 743
 744   /* Walk all endless cfloops in inner procedures.
 745    * We recognize an inner procedure if the End node is not visited. */
 746   for (i = 0; i < get_irp_n_irgs(); i++) {
 747     ir_node *e;
 748     current_ir_graph = get_irp_irg(i);
 749
 750     e = get_irg_end(current_ir_graph);
 751     if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
 752       int j;
 753       /* Don't visit the End node. */
 754       for (j = 0; j < get_End_n_keepalives(e); j++) {
 755               ir_node *el = get_End_keepalive(e, j);
 756               if (is_Block(el)) cfscc(el);
 757       }
 758     }
 759   }
 760
 761   set_irg_loop(outermost_ir_graph, current_loop);
 762   set_irg_loopinfo_state(current_ir_graph, loopinfo_cf_ip_consistent);
 763   assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
 764
 765   current_ir_graph = rem;
 766   set_interprocedural_view(rem_ipv);
 767   return max_loop_depth;
 768 }
 769
 770 /**
 771  * Clear the intra- and the interprocedural
 772  * backedge information pf a block.
 773  */
 774 static void reset_backedges(ir_node *block) {
 775   int rem = get_interprocedural_view();
 776
 777   assert(is_Block(block));
 778   set_interprocedural_view(1);
 779   clear_backedges(block);
 780   set_interprocedural_view(0);
 781   clear_backedges(block);
 782   set_interprocedural_view(rem);
 783 }
 784
 785 /**
 786  * Reset all backedges of the first block of
 787  * a loop as well as all loop info for all nodes of this loop.
 788  * Recurse into all nested loops.
 789  */
 790 static void loop_reset_backedges(ir_loop *l) {
 791   int i;
 792   reset_backedges(get_loop_node(l, 0));
 793   for (i = 0; i < get_loop_n_nodes(l); ++i)
 794     set_irn_loop(get_loop_node(l, i), NULL);
 795   for (i = 0; i < get_loop_n_sons(l); ++i) {
 796     loop_reset_backedges(get_loop_son(l, i));
 797   }
 798 }
 799
 800 /* Removes all cfloop information.
 801    Resets all backedges */
 802 void free_cfloop_information(ir_graph *irg) {
 803   if (get_irg_loop(irg))
 804     loop_reset_backedges(get_irg_loop(irg));
 805   set_irg_loop(irg, NULL);
 806   set_irg_loopinfo_state(irg, loopinfo_none);
 807   /* We cannot free the cfloop nodes, they are on the obstack. */
 808 }
 809
 810
 811 void free_all_cfloop_information (void) {
 812   int i;
 813   int rem = get_interprocedural_view();
 814   set_interprocedural_view(1);  /* To visit all filter nodes */
 815   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 816     free_cfloop_information(get_irp_irg(i));
 817   }
 818   set_interprocedural_view(rem);
 819 }