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

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