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