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 typedef struct scc_info {
  58   bool in_stack;         /* Marks whether node is on the stack. */
  59   int dfn;               /* Depth first search number. */
  60   int uplink;            /* dfn number of ancestor. */
  61 } scc_info;
  62
  63 static INLINE scc_info* new_scc_info(void) {
  64   scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
  65   memset (info, 0, sizeof (scc_info));
  66   return info;
  67 }
  68
  69 static INLINE void
  70 mark_irn_in_stack (ir_node *n) {
  71   assert(get_irn_link(n));
  72   ((scc_info *)n->link)->in_stack = true;
  73 }
  74
  75 static INLINE void
  76 mark_irn_not_in_stack (ir_node *n) {
  77   assert(get_irn_link(n));
  78   ((scc_info *)n->link)->in_stack = false;
  79 }
  80
  81 static INLINE bool
  82 irn_is_in_stack (ir_node *n) {
  83   assert(get_irn_link(n));
  84   return ((scc_info *)n->link)->in_stack;
  85 }
  86
  87 static INLINE void
  88 set_irn_uplink (ir_node *n, int uplink) {
  89   assert(get_irn_link(n));
  90   ((scc_info *)n->link)->uplink = uplink;
  91 }
  92
  93 static INLINE int
  94 get_irn_uplink (ir_node *n) {
  95   assert(get_irn_link(n));
  96   return ((scc_info *)n->link)->uplink;
  97 }
  98
  99 static INLINE void
 100 set_irn_dfn (ir_node *n, int dfn) {
 101   assert(get_irn_link(n));
 102   ((scc_info *)n->link)->dfn = dfn;
 103 }
 104
 105 static INLINE int
 106 get_irn_dfn (ir_node *n) {
 107   assert(get_irn_link(n));
 108   return ((scc_info *)n->link)->dfn;
 109 }
 110
 111 /**********************************************************************/
 112 /* A stack.                                                          **/
 113 /**********************************************************************/
 114
 115 static ir_node **stack = NULL;
 116 static int tos = 0;                /* top of stack */
 117
 118 static INLINE void init_stack(void) {
 119   if (stack) {
 120     ARR_RESIZE (ir_node *, stack, 1000);
 121   } else {
 122     stack = NEW_ARR_F (ir_node *, 1000);
 123   }
 124   tos = 0;
 125 }
 126
 127
 128 static INLINE void
 129 push (ir_node *n)
 130 {
 131   if (tos == ARR_LEN (stack)) {
 132     int nlen = ARR_LEN (stack) * 2;
 133     ARR_RESIZE (ir_node *, stack, nlen);
 134   }
 135   stack [tos++] = n;
 136   mark_irn_in_stack(n);
 137 }
 138
 139 static INLINE ir_node *
 140 pop (void)
 141 {
 142   ir_node *n = stack[--tos];
 143   mark_irn_not_in_stack(n);
 144   return n;
 145 }
 146
 147 /* The nodes up to n belong to the current loop.
 148    Removes them from the stack and adds them to the current loop. */
 149 static INLINE void
 150 pop_scc_to_loop (ir_node *n)
 151 {
 152   ir_node *m;
 153
 154   /*for (;;) {*/
 155   do {
 156     m = pop();
 157     loop_node_cnt++;
 158     set_irn_dfn(m, loop_node_cnt);
 159     add_loop_node(current_loop, m);
 160     set_irn_loop(m, current_loop);
 161     /*    if (m==n) break;*/
 162   } while(m != n);
 163 }
 164
 165 /* GL ??? my last son is my grandson???  Removes cfloops with no
 166    ir_nodes in them.  Such loops have only another loop as son. (Why
 167    can't they have two loops as sons? Does it never get that far? ) */
 168 static void close_loop (ir_loop *l)
 169 {
 170   int last = get_loop_n_elements(l) - 1;
 171   loop_element lelement = get_loop_element(l, last);
 172   ir_loop *last_son = lelement.son;
 173
 174   if (get_kind(last_son) == k_ir_loop &&
 175       get_loop_n_elements(last_son) == 1) {
 176     ir_loop *gson;
 177
 178     lelement = get_loop_element(last_son, 0);
 179     gson = lelement.son;
 180     if(get_kind(gson) == k_ir_loop) {
 181       loop_element new_last_son;
 182
 183       gson -> outer_loop = l;
 184       new_last_son.son = gson;
 185       l -> children[last] = new_last_son;
 186     }
 187   }
 188
 189   current_loop = l;
 190 }
 191
 192 /* Removes and unmarks all nodes up to n from the stack.
 193    The nodes must be visited once more to assign them to a scc. */
 194 static INLINE void
 195 pop_scc_unmark_visit (ir_node *n)
 196 {
 197   ir_node *m = NULL;
 198
 199   while (m != n) {
 200     m = pop();
 201     set_irn_visited(m, 0);
 202   }
 203 }
 204
 205 /**********************************************************************/
 206 /* The loop datastructure.                                           **/
 207 /**********************************************************************/
 208
 209 /* Allocates a new loop as son of current_loop.  Sets current_loop
 210    to the new loop and returns the father. */
 211 static ir_loop *new_loop (void) {
 212   ir_loop *father, *son;
 213
 214   father = current_loop;
 215
 216   son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
 217   memset (son, 0, sizeof (ir_loop));
 218   son->kind = k_ir_loop;
 219   son->children = NEW_ARR_F (loop_element, 0);
 220   son->n_nodes = 0;
 221   son->n_sons=0;
 222   if (father) {
 223     son->outer_loop = father;
 224     add_loop_son(father, son);
 225     son->depth = father->depth+1;
 226     if (son->depth > max_loop_depth) max_loop_depth = son->depth;
 227   } else {  /* The root loop */
 228     son->outer_loop = son;
 229     son->depth = 0;
 230   }
 231
 232 #ifdef DEBUG_libfirm
 233   son->loop_nr = get_irp_new_node_nr();
 234   son->link = NULL;
 235 #endif
 236
 237   current_loop = son;
 238   return father;
 239 }
 240
 241 /**********************************************************************/
 242 /* Constructing and destructing the loop/backedge information.       **/
 243 /**********************************************************************/
 244
 245 /* Initialization steps. **********************************************/
 246
 247 static INLINE void
 248 init_node (ir_node *n, void *env) {
 249   if (is_Block(n))
 250     set_irn_link (n, new_scc_info());
 251   clear_backedges(n);
 252 }
 253
 254 static INLINE void
 255 init_scc_common (void) {
 256   current_dfn = 1;
 257   loop_node_cnt = 0;
 258   init_stack();
 259 }
 260
 261 static INLINE void
 262 init_scc (ir_graph *irg) {
 263   init_scc_common();
 264   irg_walk_graph (irg, init_node, NULL, NULL);
 265 }
 266
 267 static INLINE void
 268 init_ip_scc (void) {
 269   init_scc_common();
 270   cg_walk (init_node, NULL, NULL);
 271
 272 #if EXPERIMENTAL_CFLOOP_TREE
 273   cg_walk (link_to_reg_end, NULL, NULL);
 274 #endif
 275 }
 276
 277 /* Condition for breaking the recursion. */
 278 static bool is_outermost_StartBlock(ir_node *n) {
 279   /* Test whether this is the outermost Start node.  If so
 280      recursion must end. */
 281   assert(is_Block(n));
 282   if ((get_Block_n_cfgpreds(n) == 1)  &&
 283       (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
 284       (get_nodes_block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
 285     return true;
 286   }
 287   return false;
 288 }
 289
 290 /** Returns true if n is a loop header, i.e., it is a Block node
 291  *  and has predecessors within the cfloop and out of the cfloop.
 292  *
 293  *  @param root: only needed for assertion.
 294  */
 295 static bool
 296 is_head (ir_node *n, ir_node *root)
 297 {
 298   int i, arity;
 299   int some_outof_loop = 0, some_in_loop = 0;
 300
 301   assert(is_Block(n));
 302
 303   if (!is_outermost_StartBlock(n)) {
 304     arity = get_irn_arity(n);
 305     for (i = 0; i < arity; i++) {
 306       ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
 307       if (is_backedge(n, i)) continue;
 308       if (!irn_is_in_stack(pred)) {
 309         some_outof_loop = 1;
 310       } else {
 311         if (get_irn_uplink(pred) < get_irn_uplink(root))  {
 312           DDMN(pred); DDMN(root);
 313           assert(get_irn_uplink(pred) >= get_irn_uplink(root));
 314         }
 315         some_in_loop = 1;
 316       }
 317     }
 318   }
 319   return some_outof_loop && some_in_loop;
 320 }
 321
 322
 323 /* Returns true if n is possible loop head of an endless loop.
 324    I.e., it is a Block, Phi or Filter node and has only predecessors
 325    within the loop.
 326    @arg root: only needed for assertion. */
 327 static bool
 328 is_endless_head (ir_node *n, ir_node *root)
 329 {
 330   int i, arity;
 331   int some_outof_loop = 0, some_in_loop = 0;
 332
 333   assert(is_Block(n));
 334   /* Test for legal loop header: Block, Phi, ... */
 335   if (!is_outermost_StartBlock(n)) {
 336     arity = get_irn_arity(n);
 337     for (i = 0; i < arity; i++) {
 338       ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
 339       assert(pred);
 340       if (is_backedge(n, i)) { continue; }
 341       if (!irn_is_in_stack(pred)) {
 342         some_outof_loop = 1; //printf(" some out of loop ");
 343       } else {
 344         if(get_irn_uplink(pred) < get_irn_uplink(root)) {
 345           DDMN(pred); DDMN(root);
 346           assert(get_irn_uplink(pred) >= get_irn_uplink(root));
 347         }
 348         some_in_loop = 1;
 349       }
 350     }
 351   }
 352   return !some_outof_loop && some_in_loop;
 353 }
 354
 355 /* Returns index of the predecessor with the smallest dfn number
 356    greater-equal than limit. */
 357 static int
 358 smallest_dfn_pred (ir_node *n, int limit)
 359 {
 360   int i, index = -2, min = -1;
 361
 362   if (!is_outermost_StartBlock(n)) {
 363     int 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) || !irn_is_in_stack(pred)) continue;
 367       if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
 368         index = i;
 369         min = get_irn_dfn(pred);
 370       }
 371     }
 372   }
 373   return index;
 374 }
 375
 376 /* Returns index of the predecessor with the largest dfn number. */
 377 static int
 378 largest_dfn_pred (ir_node *n)
 379 {
 380   int i, index = -2, max = -1;
 381
 382   if (!is_outermost_StartBlock(n)) {
 383     int arity = get_irn_arity(n);
 384     for (i = 0; i < arity; i++) {
 385       ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
 386       if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
 387       if (get_irn_dfn(pred) > max) {
 388         index = i;
 389         max = get_irn_dfn(pred);
 390       }
 391     }
 392   }
 393   return index;
 394 }
 395
 396 /* Searches the stack for possible loop heads.  Tests these for backedges.
 397    If it finds a head with an unmarked backedge it marks this edge and
 398    returns the tail of the loop.
 399    If it finds no backedge returns NULL. */
 400 static ir_node *
 401 find_tail (ir_node *n) {
 402   ir_node *m;
 403   int i, res_index = -2;
 404
 405   m = stack[tos-1];  /* tos = top of stack */
 406   if (is_head (m, n)) {
 407     res_index = smallest_dfn_pred(m, 0);
 408     if ((res_index == -2) &&  /* no smallest dfn pred found. */
 409         (n ==  m))
 410       return NULL;
 411   } else {
 412     if (m == n) return NULL;
 413     for (i = tos-2; i >= 0; --i) {
 414
 415       m = stack[i];
 416       if (is_head (m, n)) {
 417         res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
 418         if (res_index == -2)  /* no smallest dfn pred found. */
 419           res_index = largest_dfn_pred (m);
 420
 421         if ((m == n) && (res_index == -2)) {
 422           i = -1;
 423         }
 424         break;
 425       }
 426
 427
 428       /* We should not walk past our selves on the stack:  The upcoming nodes
 429          are not in this loop. We assume a loop not reachable from Start. */
 430       if (m == n) {
 431         i = -1;
 432         break;
 433       }
 434
 435     }
 436
 437
 438     if (i < 0) {
 439       /* A dead loop not reachable from Start. */
 440       for (i = tos-2; i >= 0; --i) {
 441         m = stack[i];
 442         if (is_endless_head (m, n)) {
 443           res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
 444           if (res_index == -2)  /* no smallest dfn pred found. */
 445             res_index = largest_dfn_pred (m);
 446           break;
 447         }
 448         if (m == n) { break; }  /* It's not an unreachable loop, either. */
 449       }
 450       //assert(0 && "no head found on stack");
 451     }
 452
 453   }
 454   assert (res_index > -2);
 455
 456   set_backedge (m, res_index);
 457   return is_outermost_StartBlock(n) ? NULL : get_nodes_block(skip_Proj(get_irn_n(m, res_index)));
 458 }
 459
 460 INLINE static int
 461 is_outermost_loop(ir_loop *l) {
 462   return l == get_loop_outer_loop(l);
 463 }
 464
 465 /*-----------------------------------------------------------*
 466  *                   The core algorithm.                     *
 467  *-----------------------------------------------------------*/
 468
 469
 470 static void cfscc (ir_node *n) {
 471   int i;
 472
 473   assert(is_Block(n));
 474
 475   if (irn_visited(n)) return;
 476   mark_irn_visited(n);
 477
 478   /* Initialize the node */
 479   set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
 480   set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
 481   set_irn_loop(n, NULL);
 482   current_dfn ++;
 483   push(n);
 484
 485   /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
 486      array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
 487      so is_backedge does not access array[-1] but correctly returns false! */
 488
 489   if (!is_outermost_StartBlock(n)) {
 490     int arity = get_irn_arity(n);
 491
 492     for (i = 0; i < arity; i++) {
 493       ir_node *m;
 494       if (is_backedge(n, i)) continue;
 495       m = get_nodes_block(skip_Proj(get_irn_n(n, i)));
 496
 497       cfscc (m);
 498       if (irn_is_in_stack(m)) {
 499         /* Uplink of m is smaller if n->m is a backedge.
 500            Propagate the uplink to mark the cfloop. */
 501         if (get_irn_uplink(m) < get_irn_uplink(n))
 502           set_irn_uplink(n, get_irn_uplink(m));
 503       }
 504     }
 505   }
 506
 507   if (get_irn_dfn(n) == get_irn_uplink(n)) {
 508     /* This condition holds for
 509        1) the node with the incoming backedge.
 510           That is: We found a cfloop!
 511        2) Straight line code, because no uplink has been propagated, so the
 512           uplink still is the same as the dfn.
 513
 514        But n might not be a proper cfloop head for the analysis. Proper cfloop
 515        heads are Block and Phi nodes. find_tail searches the stack for
 516        Block's and Phi's and takes those nodes as cfloop heads for the current
 517        cfloop instead and marks the incoming edge as backedge. */
 518
 519     ir_node *tail = find_tail(n);
 520     if (tail) {
 521       /* We have a cfloop, that is no straight line code,
 522          because we found a cfloop head!
 523          Next actions: Open a new cfloop on the cfloop tree and
 524                        try to find inner cfloops */
 525
 526 #if NO_CFLOOPS_WITHOUT_HEAD
 527
 528       /* This is an adaption of the algorithm from fiasco / optscc to
 529        * avoid cfloops without Block or Phi as first node.  This should
 530        * severely reduce the number of evaluations of nodes to detect
 531        * a fixpoint in the heap analysis.
 532        * Further it avoids cfloops without firm nodes that cause errors
 533        * in the heap analyses. */
 534
 535       ir_loop *l;
 536       int close;
 537       if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
 538         l = new_loop();
 539         close = 1;
 540       } else {
 541         l = current_loop;
 542         close = 0;
 543       }
 544
 545 #else
 546
 547       ir_loop *l = new_loop();
 548
 549 #endif
 550
 551       /* Remove the cfloop from the stack ... */
 552       pop_scc_unmark_visit (n);
 553
 554       /* The current backedge has been marked, that is temporarily eliminated,
 555          by find tail. Start the scc algorithm
 556          anew on the subgraph thats left (the current cfloop without the backedge)
 557          in order to find more inner cfloops. */
 558
 559       cfscc (tail);
 560
 561       assert (irn_visited(n));
 562 #if NO_CFLOOPS_WITHOUT_HEAD
 563       if (close)
 564 #endif
 565         close_loop(l);
 566     }
 567     else
 568       {
 569         /* AS: No cfloop head was found, that is we have straightline code.
 570                Pop all nodes from the stack to the current cfloop. */
 571       pop_scc_to_loop(n);
 572     }
 573   }
 574 }
 575
 576 /* Constructs backedge information for irg. */
 577 int construct_cf_backedges(ir_graph *irg) {
 578   ir_graph *rem = current_ir_graph;
 579   ir_loop *head_rem;
 580   ir_node *end = get_irg_end(irg);
 581   int i;
 582
 583   assert(!get_interprocedural_view() &&
 584      "use construct_ip_backedges");
 585   max_loop_depth = 0;
 586
 587   current_ir_graph = irg;
 588   outermost_ir_graph = irg;
 589
 590   init_scc(current_ir_graph);
 591
 592   current_loop = NULL;
 593   new_loop();  /* sets current_loop */
 594   head_rem = current_loop; /* Just for assertion */
 595
 596   inc_irg_visited(current_ir_graph);
 597
 598   cfscc(get_irg_end_block(current_ir_graph));
 599   for (i = 0; i < get_End_n_keepalives(end); i++) {
 600     ir_node *el = get_End_keepalive(end, i);
 601     if (is_Block(el)) cfscc(el);
 602   }
 603
 604   assert(head_rem == current_loop);
 605   set_irg_loop(current_ir_graph, current_loop);
 606   set_irg_loopinfo_state(current_ir_graph, loopinfo_cf_consistent);
 607   assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
 608
 609   current_ir_graph = rem;
 610   return max_loop_depth;
 611 }
 612
 613
 614 int construct_ip_cf_backedges (void) {
 615   ir_graph *rem = current_ir_graph;
 616   int rem_ipv = get_interprocedural_view();
 617   int i;
 618
 619   assert(get_irp_ip_view_state() == ip_view_valid);
 620   max_loop_depth = 0;
 621   outermost_ir_graph = get_irp_main_irg();
 622
 623   init_ip_scc();
 624
 625   current_loop = NULL;
 626   new_loop();  /* sets current_loop */
 627   set_interprocedural_view(true);
 628
 629   inc_max_irg_visited();
 630   for (i = 0; i < get_irp_n_irgs(); i++)
 631     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
 632
 633   /** We have to start the walk at the same nodes as cg_walk. **/
 634   /* Walk starting at unreachable procedures. Only these
 635    * have End blocks visible in interprocedural view. */
 636   for (i = 0; i < get_irp_n_irgs(); i++) {
 637     ir_node *sb;
 638     current_ir_graph = get_irp_irg(i);
 639
 640     sb = get_irg_start_block(current_ir_graph);
 641
 642     if ((get_Block_n_cfgpreds(sb) > 1) ||
 643         (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
 644
 645     cfscc(get_irg_end_block(current_ir_graph));
 646   }
 647
 648   /* Check whether we walked all procedures: there could be procedures
 649      with cyclic calls but no call from the outside. */
 650   for (i = 0; i < get_irp_n_irgs(); i++) {
 651     ir_node *sb;
 652     current_ir_graph = get_irp_irg(i);
 653
 654     /* Test start block: if inner procedure end and end block are not
 655      * visible and therefore not marked. */
 656     sb = get_irg_start_block(current_ir_graph);
 657     if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) cfscc(sb);
 658   }
 659
 660   /* Walk all endless cfloops in inner procedures.
 661    * We recognize an inner procedure if the End node is not visited. */
 662   for (i = 0; i < get_irp_n_irgs(); i++) {
 663     ir_node *e;
 664     current_ir_graph = get_irp_irg(i);
 665
 666     e = get_irg_end(current_ir_graph);
 667     if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
 668       int j;
 669       /* Don't visit the End node. */
 670       for (j = 0; j < get_End_n_keepalives(e); j++) {
 671         ir_node *el = get_End_keepalive(e, j);
 672         if (is_Block(el)) cfscc(el);
 673       }
 674     }
 675   }
 676
 677   set_irg_loop(outermost_ir_graph, current_loop);
 678   set_irg_loopinfo_state(current_ir_graph, loopinfo_cf_ip_consistent);
 679   assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
 680
 681   current_ir_graph = rem;
 682   set_interprocedural_view(rem_ipv);
 683   return max_loop_depth;
 684 }
 685
 686
 687 static void reset_backedges(ir_node *n) {
 688   int rem = get_interprocedural_view();
 689
 690   assert(is_Block(n));
 691   set_interprocedural_view(true);
 692   clear_backedges(n);
 693   set_interprocedural_view(false);
 694   clear_backedges(n);
 695   set_interprocedural_view(rem);
 696 }
 697
 698 static void loop_reset_backedges(ir_loop *l) {
 699   int i;
 700   reset_backedges(get_loop_node(l, 0));
 701   for (i = 0; i < get_loop_n_nodes(l); ++i)
 702     set_irn_loop(get_loop_node(l, i), NULL);
 703   for (i = 0; i < get_loop_n_sons(l); ++i) {
 704     loop_reset_backedges(get_loop_son(l, i));
 705   }
 706 }
 707
 708 /* Removes all cfloop information.
 709    Resets all backedges */
 710 void free_cfloop_information(ir_graph *irg) {
 711   if (get_irg_loop(irg))
 712     loop_reset_backedges(get_irg_loop(irg));
 713   set_irg_loop(irg, NULL);
 714   set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
 715   /* We cannot free the cfloop nodes, they are on the obstack. */
 716 }
 717
 718
 719 void free_all_cfloop_information (void) {
 720   int i;
 721   int rem = get_interprocedural_view();
 722   set_interprocedural_view(true);  /* To visit all filter nodes */
 723   for (i = 0; i < get_irp_n_irgs(); i++) {
 724     free_cfloop_information(get_irp_irg(i));
 725   }
 726   set_interprocedural_view(rem);
 727 }