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