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

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