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