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