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