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