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