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