nsz Git - libfirm/blob - ir/ana/irscc.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
  23  *              backedge/loop datastructures.
  24  *              A variation on the Tarjan algorithm. See also [Trapp:99],
  25  *              Chapter 5.2.1.2.
  26  * @author   Goetz Lindenmaier
  27  * @date     7.2002
  28  * @version  $Id$
  29  */
  30 #include "config.h"
  31
  32 #include <string.h>
  33 #include <stdlib.h>
  34
  35 #include "irloop_t.h"
  36
  37 #include "irprog_t.h"
  38 #include "irgraph_t.h"
  39 #include "irnode_t.h"
  40 #include "irgwalk.h"
  41 #include "irdump.h"
  42 #include "array.h"
  43 #include "pmap.h"
  44
  45 /* A variant of the loop tree that avoids loops without head.
  46    This reduces the depth of the loop tree. */
  47 #define NO_LOOPS_WITHOUT_HEAD 1
  48
  49 /** The outermost graph the scc is computed for. */
  50 static ir_graph *outermost_ir_graph;
  51 /** Current loop construction is working on. */
  52 static ir_loop *current_loop;
  53 /** Counts the number of allocated loop nodes.
  54  *  Each loop node gets a unique number.
  55  *  @todo What for? ev. remove.
  56  */
  57 static int loop_node_cnt = 0;
  58 /** Counter to generate depth first numbering of visited nodes. */
  59 static int current_dfn = 1;
  60
  61 static int max_loop_depth = 0;
  62
  63 void link_to_reg_end(ir_node *n, void *env);
  64 void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
  65 ir_node *get_projx_link(ir_node *cb_projx);
  66
  67 /**********************************************************************/
  68 /* Node attributes                                                   **/
  69 /**********************************************************************/
  70
  71 /**********************************************************************/
  72 /* Node attributes needed for the construction.                      **/
  73 /**********************************************************************/
  74
  75 typedef struct scc_info {
  76         int in_stack;          /**< Marks whether node is on the stack. */
  77         int dfn;               /**< Depth first search number. */
  78         int uplink;            /**< dfn number of ancestor. */
  79         /*  ir_loop *loop;         *//* Refers to the containing loop. */
  80         /*
  81             struct section *section;
  82             xset def;
  83             xset use;
  84         */
  85 } scc_info;
  86
  87 /**
  88  * Allocates a new SCC info on the given obstack.
  89  */
  90 static inline scc_info *new_scc_info(struct obstack *obst) {
  91         return OALLOCZ(obst, scc_info);
  92 }
  93
  94 /**
  95  * Mark node n being on the SCC stack.
  96  */
  97 static inline void mark_irn_in_stack(ir_node *n) {
  98         scc_info *scc = get_irn_link(n);
  99         assert(scc);
 100         scc->in_stack = 1;
 101 }
 102
 103 /**
 104 * Mark node n NOT being on the SCC stack.
 105 */
 106 static inline void mark_irn_not_in_stack(ir_node *n) {
 107         scc_info *scc = get_irn_link(n);
 108         assert(scc);
 109         scc->in_stack = 0;
 110 }
 111
 112 /**
 113  * Checks if a node is on the SCC stack.
 114  */
 115 static inline int irn_is_in_stack(ir_node *n) {
 116         scc_info *scc = get_irn_link(n);
 117         assert(scc);
 118         return scc->in_stack;
 119 }
 120
 121 /**
 122  * Sets the uplink number for a node.
 123  */
 124 static inline void set_irn_uplink(ir_node *n, int uplink) {
 125         scc_info *scc = get_irn_link(n);
 126         assert(scc);
 127         scc->uplink = uplink;
 128 }
 129
 130 /**
 131  * Returns the uplink number for a node.
 132  */
 133 static int get_irn_uplink(ir_node *n) {
 134         scc_info *scc = get_irn_link(n);
 135         assert(scc);
 136         return scc->uplink;
 137 }
 138
 139 /**
 140  * Sets the depth-first-search number for a node.
 141  */
 142 static inline void set_irn_dfn(ir_node *n, int dfn) {
 143         scc_info *scc = get_irn_link(n);
 144         assert(scc);
 145         scc->dfn = dfn;
 146 }
 147
 148 /**
 149  * Returns the depth-first-search number of a node.
 150  */
 151 static int get_irn_dfn(ir_node *n) {
 152         scc_info *scc = get_irn_link(n);
 153         assert(scc);
 154         return scc->dfn;
 155 }
 156
 157 #if 0
 158 static ir_loop *find_nodes_loop(ir_node *n, ir_loop *l) {
 159         int i;
 160         ir_loop *res = NULL;
 161
 162         /* Test whether n is contained in this loop. */
 163         for (i = 0; i < get_loop_n_nodes(l); i++)
 164                 if (n == get_loop_node(l, i)) return l;
 165
 166         /* Is this a leave in the loop tree? If so loop not found. */
 167         if (get_loop_n_sons(l) == 0) return NULL;
 168
 169         /* Else descend in the loop tree. */
 170         for (i = 0; i < get_loop_n_sons(l); i++) {
 171                 res = find_nodes_loop(n, get_loop_son(l, i));
 172                 if (res) break;
 173         }
 174         return res;
 175 }
 176
 177 /* @@@ temporary implementation, costly!!! */
 178 ir_loop * get_irn_loop(ir_node *n) {
 179         ir_loop *l = get_irg_loop(current_ir_graph);
 180         l = find_nodes_loop(n, l);
 181         return l;
 182 }
 183 #endif
 184
 185 /**********************************************************************/
 186 /* A stack.                                                          **/
 187 /**********************************************************************/
 188
 189 static ir_node **stack = NULL;
 190 static int tos = 0;                /* top of stack */
 191
 192 /**
 193  * initializes the stack
 194  */
 195 static inline void init_stack(void) {
 196         if (stack) {
 197                 ARR_RESIZE(ir_node *, stack, 1000);
 198         } else {
 199                 stack = NEW_ARR_F(ir_node *, 1000);
 200         }
 201         tos = 0;
 202 }
 203
 204 /**
 205  * Frees the stack.
 206  */
 207 static void finish_stack(void) {
 208         DEL_ARR_F(stack);
 209         stack = NULL;
 210 }
 211
 212 /**
 213  * push a node onto the stack
 214  *
 215  * @param n  The node to push
 216  */
 217 static inline void push(ir_node *n) {
 218         if (tos == ARR_LEN(stack)) {
 219                 int nlen = ARR_LEN(stack) * 2;
 220                 ARR_RESIZE(ir_node *, stack, nlen);
 221         }
 222         stack [tos++] = n;
 223         mark_irn_in_stack(n);
 224 }
 225
 226 /**
 227  * pop a node from the stack
 228  *
 229  * @return  The topmost node
 230  */
 231 static inline ir_node *pop(void) {
 232         ir_node *n = stack[--tos];
 233         mark_irn_not_in_stack(n);
 234         return n;
 235 }
 236
 237 /**
 238  * The nodes up to n belong to the current loop.
 239  * Removes them from the stack and adds them to the current loop.
 240  */
 241 static inline void pop_scc_to_loop(ir_node *n) {
 242         ir_node *m;
 243         int i = 0;
 244
 245         do {
 246                 m = pop();
 247
 248                 loop_node_cnt++;
 249                 set_irn_dfn(m, loop_node_cnt);
 250                 add_loop_node(current_loop, m);
 251                 set_irn_loop(m, current_loop);
 252                 ++i;
 253         } while (m != n);
 254
 255         /* i might be bigger than 1 for dead (and that's why bad) loops */
 256         /* if(i > 1)
 257                 printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!11111\n");
 258          */
 259 }
 260
 261 /* GL ??? my last son is my grandson???  Removes loops with no
 262    ir_nodes in them.  Such loops have only another loop as son. (Why
 263    can't they have two loops as sons? Does it never get that far? ) */
 264 static void close_loop(ir_loop *l) {
 265         int last = get_loop_n_elements(l) - 1;
 266         loop_element lelement = get_loop_element(l, last);
 267         ir_loop *last_son = lelement.son;
 268
 269         if (get_kind(last_son) == k_ir_loop &&
 270                 get_loop_n_elements(last_son) == 1) {
 271                         ir_loop *gson;
 272
 273                         lelement = get_loop_element(last_son, 0);
 274                         gson = lelement.son;
 275
 276                         if (get_kind(gson) == k_ir_loop) {
 277                                 loop_element new_last_son;
 278
 279                                 gson->outer_loop = l;
 280                                 new_last_son.son = gson;
 281                                 l->children[last] = new_last_son;
 282                         }
 283         }
 284
 285         current_loop = l;
 286 }
 287
 288 /* Removes and unmarks all nodes up to n from the stack.
 289    The nodes must be visited once more to assign them to a scc. */
 290 static inline void pop_scc_unmark_visit(ir_node *n) {
 291         ir_node *m = NULL;
 292
 293         while (m != n) {
 294                 m = pop();
 295                 set_irn_visited(m, 0);
 296         }
 297 }
 298
 299 /**********************************************************************/
 300 /* The loop datastructure.                                           **/
 301 /**********************************************************************/
 302
 303 /* Allocates a new loop as son of current_loop.  Sets current_loop
 304    to the new loop and returns the father. */
 305 static ir_loop *new_loop(void) {
 306         ir_loop *father = current_loop;
 307         ir_loop *son    = alloc_loop(father, outermost_ir_graph->obst);
 308
 309         if (son->depth > max_loop_depth) max_loop_depth = son->depth;
 310         current_loop = son;
 311         return father;
 312 }
 313
 314 /**********************************************************************/
 315 /* Constructing and destructing the loop/backedge information.       **/
 316 /**********************************************************************/
 317
 318 /* Initialization steps. **********************************************/
 319
 320 static inline void init_node(ir_node *n, void *env) {
 321         struct obstack *obst = env;
 322         set_irn_link(n, new_scc_info(obst));
 323         clear_backedges(n);
 324 }
 325
 326 static inline void init_scc_common(void) {
 327         current_dfn = 1;
 328         loop_node_cnt = 0;
 329         init_stack();
 330 }
 331
 332 static inline void init_scc(ir_graph *irg, struct obstack *obst) {
 333         init_scc_common();
 334         irg_walk_graph(irg, init_node, NULL, obst);
 335         /*
 336         irg_walk (irg, link_to_reg_end, NULL, NULL);
 337         */
 338 }
 339
 340 static inline void finish_scc(void)
 341 {
 342         finish_stack();
 343 }
 344
 345 #ifdef INTERPROCEDURAL_VIEW
 346 static inline void init_ip_scc(struct obstack *obst) {
 347         init_scc_common();
 348         cg_walk(init_node, NULL, obst);
 349
 350 #if EXPERIMENTAL_LOOP_TREE
 351         cg_walk(link_to_reg_end, NULL, NULL);
 352 #endif
 353 }
 354 #endif
 355
 356 /**
 357  * Check weather a given node represents the outer most Start
 358  * block. In intra-procedural view this is the start block of the
 359  * current graph, in interprocedural view it is the start block
 360  * of the outer most graph.
 361  *
 362  * @param n  the node to check
 363  *
 364  * This is the condition for breaking the scc recursion.
 365  */
 366 static int is_outermost_Start(ir_node *n) {
 367         /* Test whether this is the outermost Start node. */
 368         if (is_Block(n) && get_Block_n_cfgpreds(n) == 1) {
 369                 ir_node *pred = skip_Proj(get_Block_cfgpred(n, 0));
 370             if (is_Start(pred) && get_nodes_block(pred) == n)
 371                         return 1;
 372         }
 373         return 0;
 374 }
 375
 376 /* When to walk from nodes to blocks. Only for Control flow operations? */
 377 static inline int get_start_index(ir_node *n) {
 378 #undef BLOCK_BEFORE_NODE
 379 #define BLOCK_BEFORE_NODE 1
 380
 381 #if BLOCK_BEFORE_NODE
 382
 383         /* This version assures, that all nodes are ordered absolutely.  This allows
 384            to undef all nodes in the heap analysis if the block is false, which means
 385            not reachable.
 386            I.e., with this code, the order on the loop tree is correct. But a (single)
 387            test showed the loop tree is deeper.   */
 388         if (get_irn_op(n) == op_Phi                      ||
 389             is_Block(n)                                  ||
 390             (is_Filter(n) && get_interprocedural_view()) || (
 391               get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
 392               get_irn_pinned(n)              == op_pin_state_floats
 393             ))
 394                 // Here we could test for backedge at -1 which is illegal
 395                 return 0;
 396         else
 397                 return -1;
 398
 399 #else
 400
 401         /* This version causes deeper loop trees (at least we verified this
 402            for Polymor).
 403            But it guarantees that Blocks are analysed before nodes contained in the
 404            block.  If so, we can set the value to undef if the block is not \
 405            executed. */
 406         if (is_cfop(n) || is_fragile_op(n) || is_Start(n))
 407                 return -1;
 408         else
 409                 return 0;
 410
 411 #endif
 412 }
 413
 414 /**
 415  * Return non-zero if the given node is a legal loop header:
 416  * Block, Phi, Filter.
 417  *
 418  * @param n  the node to check
 419  */
 420 static inline int is_possible_loop_head(ir_node *n) {
 421         ir_op *op = get_irn_op(n);
 422         return ((op == op_Block) ||
 423                 (op == op_Phi) ||
 424                 ((op == op_Filter) && get_interprocedural_view()));
 425 }
 426
 427 /**
 428  * Returns non-zero if n is a loop header, i.e., it is a Block, Phi
 429  * or Filter node and has predecessors within the loop and out
 430  * of the loop.
 431  *
 432  * @param n    the node to check
 433  * @param root only needed for assertion.
 434  */
 435 static int is_head(ir_node *n, ir_node *root) {
 436         int i, arity;
 437         int some_outof_loop = 0, some_in_loop = 0;
 438
 439         /* Test for legal loop header: Block, Phi, ... */
 440         if (!is_possible_loop_head(n))
 441                 return 0;
 442
 443         if (!is_outermost_Start(n)) {
 444 #ifndef NDEBUG
 445                 int uplink = get_irn_uplink(root);
 446 #else
 447                 (void) root;
 448 #endif
 449                 arity = get_irn_arity(n);
 450                 for (i = get_start_index(n); i < arity; i++) {
 451                         ir_node *pred;
 452                         if (is_backedge(n, i))
 453                                 continue;
 454                         pred = get_irn_n(n, i);
 455                         if (! irn_is_in_stack(pred)) {
 456                                 some_outof_loop = 1;
 457                         } else {
 458                                 assert(get_irn_uplink(pred) >= uplink);
 459                                 some_in_loop = 1;
 460                         }
 461                 }
 462         }
 463         return some_outof_loop & some_in_loop;
 464 }
 465
 466 /**
 467  * Returns non-zero if n is possible loop head of an endless loop.
 468  * I.e., it is a Block, Phi or Filter node and has only predecessors
 469  * within the loop.
 470  *
 471  * @param n    the node to check
 472  * @param root only needed for assertion.
 473  */
 474 static int is_endless_head(ir_node *n, ir_node *root) {
 475         int i, arity;
 476         int none_outof_loop = 1, some_in_loop = 0;
 477
 478         /* Test for legal loop header: Block, Phi, ... */
 479         if (!is_possible_loop_head(n))
 480                 return 0;
 481
 482         if (!is_outermost_Start(n)) {
 483 #ifndef NDEBUG
 484                 int uplink = get_irn_uplink(root);
 485 #else
 486                 (void) root;
 487 #endif
 488                 arity = get_irn_arity(n);
 489                 for (i = get_start_index(n); i < arity; i++) {
 490                         ir_node *pred;
 491                         if (is_backedge(n, i))
 492                                 continue;
 493                         pred = get_irn_n(n, i);
 494                         if (!irn_is_in_stack(pred)) {
 495                                 none_outof_loop = 0;
 496                         } else {
 497                                 assert(get_irn_uplink(pred) >= uplink);
 498                                 some_in_loop = 1;
 499                         }
 500                 }
 501         }
 502         return none_outof_loop & some_in_loop;
 503 }
 504
 505 /** Returns index of the predecessor with the smallest dfn number
 506     greater-equal than limit. */
 507 static int smallest_dfn_pred(ir_node *n, int limit) {
 508         int i, index = -2, min = -1;
 509
 510         if (!is_outermost_Start(n)) {
 511                 int arity = get_irn_arity(n);
 512                 for (i = get_start_index(n); i < arity; i++) {
 513                         ir_node *pred = get_irn_n(n, i);
 514                         if (is_backedge(n, i) || !irn_is_in_stack(pred))
 515                                 continue;
 516                         if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
 517                                 index = i;
 518                                 min = get_irn_dfn(pred);
 519                         }
 520                 }
 521         }
 522         return index;
 523 }
 524
 525 /**
 526  * Returns index of the predecessor with the largest dfn number.
 527  */
 528 static int largest_dfn_pred(ir_node *n) {
 529         int i, index = -2, max = -1;
 530
 531         if (!is_outermost_Start(n)) {
 532                 int arity = get_irn_arity(n);
 533                 for (i = get_start_index(n); i < arity; i++) {
 534                         ir_node *pred = get_irn_n(n, i);
 535                         if (is_backedge (n, i) || !irn_is_in_stack(pred))
 536                                 continue;
 537                         if (get_irn_dfn(pred) > max) {
 538                                 index = i;
 539                                 max = get_irn_dfn(pred);
 540                         }
 541                 }
 542         }
 543         return index;
 544 }
 545
 546 /**
 547  * Searches the stack for possible loop heads.  Tests these for backedges.
 548  * If it finds a head with an unmarked backedge it marks this edge and
 549  * returns the tail of the loop.
 550  * If it finds no backedge returns NULL.
 551  * ("disable_backedge" in fiasco)
 552  *
 553  * @param n  A node where uplink == dfn.
 554  */
 555 static ir_node *find_tail(ir_node *n) {
 556         ir_node *m;
 557         int i, res_index = -2;
 558
 559         /*
 560         if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
 561          */
 562         m = stack[tos-1];  /* tos = top of stack */
 563         if (is_head(m, n)) {
 564                 res_index = smallest_dfn_pred(m, 0);
 565                 if ((res_index == -2) &&  /* no smallest dfn pred found. */
 566                         (n ==  m))
 567                         return NULL;
 568         } else {
 569                 if (m == n) return NULL;    // Is this to catch Phi - self loops?
 570                 for (i = tos-2; i >= 0; --i) {
 571                         m = stack[i];
 572
 573                         if (is_head(m, n)) {
 574                                 res_index = smallest_dfn_pred(m, get_irn_dfn(m) + 1);
 575                                 if (res_index == -2)  /* no smallest dfn pred found. */
 576                                         res_index = largest_dfn_pred(m);
 577
 578                                 if ((m == n) && (res_index == -2)) {  /* don't walk past loop head. */
 579                                         i = -1;
 580                                 }
 581                                 break;
 582                         }
 583
 584                         /* We should not walk past our selves on the stack:  The upcoming nodes
 585                            are not in this loop. We assume a loop not reachable from Start. */
 586                         if (m == n) {
 587                                 i = -1;
 588                                 break;
 589                         }
 590                 }
 591
 592                 if (i < 0) {
 593                         /* A dead loop not reachable from Start. */
 594                         for (i = tos-2; i >= 0; --i) {
 595                                 m = stack[i];
 596                                 if (is_endless_head(m, n)) {
 597                                         res_index = smallest_dfn_pred(m, get_irn_dfn(m) + 1);
 598                                         if (res_index == -2)  /* no smallest dfn pred found. */
 599                                                 res_index = largest_dfn_pred (m);
 600                                         break;
 601                                 }
 602                                 if (m == n) { break; }  /* It's not an unreachable loop, either. */
 603                         }
 604                         //assert(0 && "no head found on stack");
 605                 }
 606
 607         }
 608         if (res_index <= -2) {
 609                 /* It's a completely bad loop: without Phi/Block nodes that can
 610                    be a head. I.e., the code is "dying".  We break the loop by
 611                    setting Bad nodes. */
 612                 int arity = get_irn_arity(n);
 613                 ir_node *bad = get_irg_bad(get_irn_irg(n));
 614                 for (i = -1; i < arity; ++i) {
 615                         set_irn_n(n, i, bad);
 616                 }
 617                 return NULL;
 618         }
 619         assert(res_index > -2);
 620
 621         set_backedge(m, res_index);
 622         return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
 623 }
 624
 625
 626 #if EXPERIMENTAL_LOOP_TREE
 627
 628 /*  ----------------------------------------------------------------
 629     AS:  This is experimental code to build loop trees suitable for
 630     the heap analysis. Does not work correctly right now... :-(
 631
 632
 633     Search in stack for the corresponding first Call-End-ProjX that
 634     corresponds to one of the control flow predecessors of the given
 635     block, that is the possible callers.
 636     returns: the control predecessor to chose\
 637     or       -1 if no corresponding Call-End-Node could be found
 638              on the stack.
 639     - -------------------------------------------------------------- */
 640
 641 int search_endproj_in_stack(ir_node *start_block) {
 642         int i, j;
 643         assert(is_Block(start_block));
 644         for(i = tos - 1; i >= 0; --i)
 645         {
 646                 if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
 647                         get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
 648                 {
 649                         printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
 650                         ir_node *end_projx = stack[i];
 651
 652                         int arity = get_irn_arity(start_block);
 653                         for(j = 0; j < arity; j++)
 654                         {
 655                                 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
 656                                         get_Proj_proj(end_projx));
 657                                 if(get_irn_n(start_block, j) == begin_projx)
 658                                 {
 659                                         printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
 660                                         return(j);
 661                                 }
 662                         }
 663                 }
 664         }
 665         return(-1);
 666 }
 667
 668
 669 static pmap *projx_link = NULL;
 670
 671 void link_to_reg_end (ir_node *n, void *env) {
 672         if(get_irn_op(n) == op_Proj &&
 673                 get_irn_mode(n) == mode_X &&
 674                 get_irn_op(get_irn_n(n, 0)) == op_EndReg) {
 675                         /* Reg End Projx -> Find the CallBegin Projx and hash it */
 676                         ir_node *end_projx = n;
 677                         ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
 678                                 get_Proj_proj(end_projx));
 679                         set_projx_link(begin_projx, end_projx);
 680         }
 681 }
 682
 683 void set_projx_link(ir_node *cb_projx, ir_node *end_projx) {
 684         if(projx_link == NULL)
 685                 projx_link = pmap_create();
 686         pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
 687 }
 688
 689 ir_node *get_projx_link(ir_node *cb_projx) {
 690         return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
 691 }
 692
 693 #endif
 694
 695 static inline int is_outermost_loop(ir_loop *l) {
 696         return l == get_loop_outer_loop(l);
 697 }
 698
 699
 700 /*-----------------------------------------------------------*
 701  *                   The core algorithm.                     *
 702  *-----------------------------------------------------------*/
 703
 704 /**
 705  * The core algorithm: Find strongly coupled components.
 706  *
 707  * @param n  node to start
 708  */
 709 static void scc(ir_node *n) {
 710         if (irn_visited_else_mark(n))
 711                 return;
 712
 713         /* Initialize the node */
 714         set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
 715         set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
 716         set_irn_loop(n, NULL);
 717         ++current_dfn;
 718         push(n);
 719
 720         /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
 721            array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
 722            so is_backedge does not access array[-1] but correctly returns false! */
 723
 724         if (!is_outermost_Start(n)) {
 725                 int i, arity = get_irn_arity(n);
 726
 727                 for (i = get_start_index(n); i < arity; ++i) {
 728                         ir_node *m;
 729                         if (is_backedge(n, i))
 730                                 continue;
 731                         m = get_irn_n(n, i);
 732                         scc(m);
 733                         if (irn_is_in_stack(m)) {
 734                                 /* Uplink of m is smaller if n->m is a backedge.
 735                                    Propagate the uplink to mark the loop. */
 736                                 if (get_irn_uplink(m) < get_irn_uplink(n))
 737                                         set_irn_uplink(n, get_irn_uplink(m));
 738                         }
 739                 }
 740         }
 741
 742         if (get_irn_dfn(n) == get_irn_uplink(n)) {
 743                 /* This condition holds for
 744                    1) the node with the incoming backedge.
 745                       That is: We found a loop!
 746                    2) Straight line code, because no uplink has been propagated, so the
 747                       uplink still is the same as the dfn.
 748
 749                    But n might not be a proper loop head for the analysis. Proper loop
 750                    heads are Block and Phi nodes. find_tail() searches the stack for
 751                    Block's and Phi's and takes those nodes as loop heads for the current
 752                    loop instead and marks the incoming edge as backedge. */
 753
 754                 ir_node *tail = find_tail(n);
 755                 if (tail != NULL) {
 756                         /* We have a loop, that is no straight line code,
 757                            because we found a loop head!
 758                            Next actions: Open a new loop on the loop tree and
 759                                          try to find inner loops */
 760
 761 #if NO_LOOPS_WITHOUT_HEAD
 762                         /* This is an adaption of the algorithm from fiasco / optscc to
 763                          * avoid loops without Block or Phi as first node.  This should
 764                          * severely reduce the number of evaluations of nodes to detect
 765                          * a fixpoint in the heap analysis.
 766                          * Further it avoids loops without firm nodes that cause errors
 767                          * in the heap analyses.
 768                          * But attention:  don't do it for the outermost loop:  This loop
 769                          * is not iterated.  A first block can be a loop head in case of
 770                          * an endless recursion. */
 771
 772                         ir_loop *l;
 773                         int close;
 774                         if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
 775                                 l = new_loop();
 776                                 close = 1;
 777                         } else {
 778                                 l = current_loop;
 779                                 close = 0;
 780                         }
 781 #else
 782                         ir_loop *l = new_loop();
 783 #endif
 784
 785                         /* Remove the loop from the stack ... */
 786                         pop_scc_unmark_visit(n);
 787
 788                         /* The current backedge has been marked, that is temporarily eliminated,
 789                            by find tail. Start the scc algorithm
 790                            again on the subgraph that is left (the current loop without the backedge)
 791                            in order to find more inner loops. */
 792                         scc(tail);
 793
 794                         assert(irn_visited(n));
 795 #if NO_LOOPS_WITHOUT_HEAD
 796                         if (close)
 797 #endif
 798                                 close_loop(l);
 799                 } else {
 800                         /* No loop head was found, that is we have straight line code.
 801                            Pop all nodes from the stack to the current loop. */
 802                         pop_scc_to_loop(n);
 803                 }
 804         }
 805 }
 806
 807 #ifdef INTERPROCEDURAL_VIEW
 808 static void my_scc(ir_node *n) {
 809         int i;
 810         if (irn_visited_else_mark(n))
 811                 return;
 812
 813         /* Initialize the node */
 814         set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
 815         set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
 816         set_irn_loop(n, NULL);
 817         current_dfn ++;
 818         push(n);
 819
 820         /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
 821            array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
 822            so is_backedge does not access array[-1] but correctly returns false! */
 823
 824         if (!is_outermost_Start(n)) {
 825                 int arity = get_irn_arity(n);
 826
 827                 for (i = get_start_index(n); i < arity; i++) {
 828                         ir_node *m;
 829                         if (is_backedge(n, i)) continue;
 830                         m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
 831                         /* if (!m || is_Unknown(m)) continue; */
 832                         my_scc(m);
 833                         if (irn_is_in_stack(m)) {
 834                                 /* Uplink of m is smaller if n->m is a backedge.
 835                                    Propagate the uplink to mark the loop. */
 836                                 if (get_irn_uplink(m) < get_irn_uplink(n))
 837                                         set_irn_uplink(n, get_irn_uplink(m));
 838                         }
 839                 }
 840         }
 841
 842         if (get_irn_dfn(n) == get_irn_uplink(n)) {
 843                 /* This condition holds for
 844                    1) the node with the incoming backedge.
 845                       That is: We found a loop!
 846                    2) Straight line code, because no uplink has been propagated, so the
 847                       uplink still is the same as the dfn.
 848
 849                    But n might not be a proper loop head for the analysis. Proper loop
 850                    heads are Block and Phi nodes. find_tail searches the stack for
 851                    Block's and Phi's and takes those nodes as loop heads for the current
 852                    loop instead and marks the incoming edge as backedge. */
 853
 854                 ir_node *tail = find_tail(n);
 855                 if (tail) {
 856                         /* We have a loop, that is no straight line code,
 857                            because we found a loop head!
 858                            Next actions: Open a new loop on the loop tree and
 859                                          try to find inner loops */
 860
 861 #if NO_LOOPS_WITHOUT_HEAD
 862                         /* This is an adaption of the algorithm from fiasco / optscc to
 863                          * avoid loops without Block or Phi as first node.  This should
 864                          * severely reduce the number of evaluations of nodes to detect
 865                          * a fixpoint in the heap analysis.
 866                          * Further it avoids loops without firm nodes that cause errors
 867                          * in the heap analyses. */
 868
 869                         ir_loop *l;
 870                         int close;
 871                         if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
 872                                 l = new_loop();
 873                                 close = 1;
 874                         } else {
 875                                 l = current_loop;
 876                                 close = 0;
 877                         }
 878 #else
 879                         ir_loop *l = new_loop();
 880 #endif
 881
 882                         /* Remove the loop from the stack ... */
 883                         pop_scc_unmark_visit(n);
 884
 885                         /* The current backedge has been marked, that is temporarily eliminated,
 886                            by find tail. Start the scc algorithm
 887                            anew on the subgraph that is left (the current loop without the backedge)
 888                            in order to find more inner loops. */
 889                         my_scc(tail);
 890
 891                         assert(irn_visited(n));
 892 #if NO_LOOPS_WITHOUT_HEAD
 893                         if (close)
 894 #endif
 895                                 close_loop(l);
 896                 } else {
 897                         /* No loop head was found, that is we have straightline code.
 898                            Pop all nodes from the stack to the current loop. */
 899                         pop_scc_to_loop(n);
 900                 }
 901         }
 902 }
 903 #endif /* INTERPROCEDURAL_VIEW */
 904
 905 /* Constructs backedge information for irg. In interprocedural view constructs
 906    backedges for all methods called by irg, too. */
 907 int construct_backedges(ir_graph *irg) {
 908         ir_graph *rem = current_ir_graph;
 909         ir_loop *head_rem;
 910         struct obstack temp;
 911
 912         assert(!get_interprocedural_view() &&
 913                "not implemented, use construct_ip_backedges()");
 914
 915         max_loop_depth = 0;
 916         current_ir_graph   = irg;
 917         outermost_ir_graph = irg;
 918
 919         obstack_init(&temp);
 920         init_scc(irg, &temp);
 921
 922         current_loop = NULL;
 923         new_loop();  /* sets current_loop */
 924         head_rem = current_loop; /* Just for assertion */
 925
 926         inc_irg_visited(irg);
 927
 928         scc(get_irg_end(irg));
 929
 930         finish_scc();
 931         obstack_free(&temp, NULL);
 932
 933         assert(head_rem == current_loop);
 934         mature_loops(current_loop, irg->obst);
 935         set_irg_loop(irg, current_loop);
 936         set_irg_loopinfo_state(irg, loopinfo_consistent);
 937         assert(get_irg_loop(irg)->kind == k_ir_loop);
 938         current_ir_graph = rem;
 939         return max_loop_depth;
 940 }
 941
 942
 943 #ifdef INTERPROCEDURAL_VIEW
 944 int construct_ip_backedges(void) {
 945         ir_graph *rem = current_ir_graph;
 946         int rem_ipv = get_interprocedural_view();
 947         int i;
 948         strcut obstack temp;
 949
 950         max_loop_depth = 0;
 951         assert(get_irp_ip_view_state() == ip_view_valid);
 952
 953         outermost_ir_graph = get_irp_main_irg();
 954
 955         obstack_init(&temp);
 956         init_ip_scc(&temp);
 957
 958         current_loop = NULL;
 959         new_loop();  /* sets current_loop */
 960         set_interprocedural_view(1);
 961
 962         inc_max_irg_visited();
 963         for (i = 0; i < get_irp_n_irgs(); i++)
 964                 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
 965
 966         /** We have to start the walk at the same nodes as cg_walk. **/
 967         /* Walk starting at unreachable procedures. Only these
 968          * have End blocks visible in interprocedural view. */
 969         for (i = 0; i < get_irp_n_irgs(); i++) {
 970                 ir_node *sb;
 971                 current_ir_graph = get_irp_irg(i);
 972
 973                 sb = get_irg_start_block(current_ir_graph);
 974
 975                 if ((get_Block_n_cfgpreds(sb) > 1) ||
 976                     (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb))
 977                         continue;
 978
 979                 scc(get_irg_end(current_ir_graph));
 980         }
 981
 982         /* Check whether we walked all procedures: there could be procedures
 983            with cyclic calls but no call from the outside. */
 984         for (i = 0; i < get_irp_n_irgs(); i++) {
 985                 ir_node *sb;
 986                 current_ir_graph = get_irp_irg(i);
 987
 988                 /* Test start block: if inner procedure end and end block are not
 989                  * visible and therefore not marked. */
 990                 sb = get_irg_start_block(current_ir_graph);
 991                 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
 992         }
 993
 994         /* Walk all endless loops in inner procedures.
 995          * We recognize an inner procedure if the End node is not visited. */
 996         for (i = 0; i < get_irp_n_irgs(); i++) {
 997                 ir_node *e;
 998                 current_ir_graph = get_irp_irg(i);
 999
1000                 e = get_irg_end(current_ir_graph);
1001                 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1002                         int j;
1003                         /* Don't visit the End node. */
1004                         for (j = 0; j < get_End_n_keepalives(e); j++)
1005                                 scc(get_End_keepalive(e, j));
1006                 }
1007         }
1008
1009         set_irg_loop(outermost_ir_graph, current_loop);
1010         set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1011         assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1012
1013         obstack_free(&temp, NULL);
1014         current_ir_graph = rem;
1015         set_interprocedural_view(rem_ipv);
1016         return max_loop_depth;
1017 }
1018
1019 void my_construct_ip_backedges(void) {
1020         ir_graph *rem = current_ir_graph;
1021         int rem_ipv = get_interprocedural_view();
1022         int i;
1023
1024         assert(get_irp_ip_view_state() == ip_view_valid);
1025
1026         outermost_ir_graph = get_irp_main_irg();
1027
1028         init_ip_scc();
1029
1030         current_loop = NULL;
1031         new_loop();  /* sets current_loop */
1032         set_interprocedural_view(1);
1033
1034         inc_max_irg_visited();
1035         for (i = 0; i < get_irp_n_irgs(); i++)
1036                 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1037
1038         /** We have to start the walk at the same nodes as cg_walk. **/
1039         /* Walk starting at unreachable procedures. Only these
1040          * have End blocks visible in interprocedural view. */
1041         for (i = 0; i < get_irp_n_irgs(); i++) {
1042                 ir_node *sb;
1043                 current_ir_graph = get_irp_irg(i);
1044
1045                 sb = get_irg_start_block(current_ir_graph);
1046
1047                 if ((get_Block_n_cfgpreds(sb) > 1) ||
1048                     (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1049
1050                 my_scc(get_irg_end(current_ir_graph));
1051         }
1052
1053         /* Check whether we walked all procedures: there could be procedures
1054            with cyclic calls but no call from the outside. */
1055         for (i = 0; i < get_irp_n_irgs(); i++) {
1056                 ir_node *sb;
1057                 current_ir_graph = get_irp_irg(i);
1058
1059                 /* Test start block: if inner procedure end and end block are not
1060                  * visible and therefore not marked. */
1061                 sb = get_irg_start_block(current_ir_graph);
1062                 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph))
1063                         scc(sb);
1064         }
1065
1066         /* Walk all endless loops in inner procedures.
1067          * We recognize an inner procedure if the End node is not visited. */
1068         for (i = 0; i < get_irp_n_irgs(); i++) {
1069                 ir_node *e;
1070                 current_ir_graph = get_irp_irg(i);
1071
1072                 e = get_irg_end(current_ir_graph);
1073                 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1074                         int j;
1075                         /* Don't visit the End node. */
1076                         for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1077                 }
1078         }
1079
1080         set_irg_loop(outermost_ir_graph, current_loop);
1081         set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1082         assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1083
1084         current_ir_graph = rem;
1085         set_interprocedural_view(rem_ipv);
1086 }
1087 #endif
1088
1089 static void reset_backedges(ir_node *n) {
1090         if (is_possible_loop_head(n)) {
1091 #ifdef INTERPROCEDURAL_VIEW
1092                 int rem = get_interprocedural_view();
1093
1094                 set_interprocedural_view(1);
1095                 clear_backedges(n);
1096                 set_interprocedural_view(1);
1097                 clear_backedges(n);
1098                 set_interprocedural_view(rem);
1099 #else
1100                 clear_backedges(n);
1101 #endif
1102         }
1103 }
1104
1105
1106 /*
1107 static void loop_reset_backedges(ir_loop *l) {
1108         int i;
1109         reset_backedges(get_loop_node(l, 0));
1110         for (i = 0; i < get_loop_n_nodes(l); ++i)
1111                 set_irn_loop(get_loop_node(l, i), NULL);
1112         for (i = 0; i < get_loop_n_sons(l); ++i) {
1113                 loop_reset_backedges(get_loop_son(l, i));
1114         }
1115 }
1116 */
1117
1118 static void loop_reset_node(ir_node *n, void *env) {
1119         (void) env;
1120         set_irn_loop(n, NULL);
1121         reset_backedges(n);
1122 }
1123
1124
1125 /** Removes all loop information.
1126     Resets all backedges */
1127 void free_loop_information(ir_graph *irg) {
1128         /* We can not use this recursion, as the loop might contain
1129            illegal nodes by now.  Why else would we throw away the
1130            representation?
1131         if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1132         */
1133         irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1134         set_irg_loop(irg, NULL);
1135         set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1136         /* We cannot free the loop nodes, they are on the obstack. */
1137 }
1138
1139
1140 void free_all_loop_information(void) {
1141         int i;
1142 #ifdef INTERPROCEDURAL_VIEW
1143         int rem = get_interprocedural_view();
1144         set_interprocedural_view(1);  /* To visit all filter nodes */
1145 #endif
1146         for (i = 0; i < get_irp_n_irgs(); i++) {
1147                 free_loop_information(get_irp_irg(i));
1148         }
1149 #ifdef INTERPROCEDURAL_VIEW
1150         set_interprocedural_view(rem);
1151 #endif
1152 }
1153
1154
1155
1156
1157
1158 /* Debug stuff *************************************************/
1159
1160 static int test_loop_node(ir_loop *l) {
1161         int i, has_node = 0, found_problem = 0;
1162         loop_element le;
1163
1164         assert(l && l->kind == k_ir_loop);
1165
1166         if (get_loop_n_elements(l) == 0) {
1167                 found_problem = 1;
1168                 dump_loop(l, "-ha");
1169         }
1170
1171         le = get_loop_element(l, 0);
1172         if (*(le.kind) != k_ir_node) {
1173                 assert(le.kind && *(le.kind) == k_ir_loop);
1174
1175                 found_problem = 1;
1176                 dump_loop(l, "-ha");
1177         }
1178
1179         if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1180                 found_problem = 1;
1181                 dump_loop(l, "-ha");
1182         }
1183
1184         if ((get_loop_depth(l) != 0) &&
1185                 (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1186                         found_problem = 1;
1187                         dump_loop(l, "-ha");
1188         }
1189
1190         /* Recur */
1191         has_node = 0;
1192         for (i = 0; i < get_loop_n_elements(l); ++i) {
1193                 le = get_loop_element(l, i);
1194                 if (*(le.kind) == k_ir_node)
1195                         has_node++;
1196                 else
1197                         if (test_loop_node(le.son)) found_problem = 1;
1198         }
1199
1200         if (has_node == 0) {
1201                 found_problem = 1;
1202                 dump_loop(l, "-ha");
1203         }
1204
1205         return found_problem;
1206 }
1207
1208 /** Prints all loop nodes that
1209  *  - do not have any firm nodes, only loop sons
1210  *  - the header is not a Phi, Block or Filter.
1211  */
1212 void find_strange_loop_nodes(ir_loop *l) {
1213         int found_problem = 0;
1214         found_problem = test_loop_node(l);
1215         printf("Finished Test\n\n");
1216         if (found_problem) exit(0);
1217
1218 }
1219
1220 /* ------------------------------------------------------------------- */
1221 /* Simple analyses based on the loop information                       */
1222 /* ------------------------------------------------------------------- */
1223
1224 int is_loop_variant(ir_loop *l, ir_loop *b) {
1225         int i, n_elems;
1226
1227         if (l == b) return 1;
1228
1229         n_elems = get_loop_n_elements(l);
1230         for (i = 0; i < n_elems; ++i) {
1231                 loop_element e = get_loop_element(l, i);
1232                 if (is_ir_loop(e.kind))
1233                         if (is_loop_variant(e.son, b))
1234                                 return 1;
1235         }
1236
1237         return 0;
1238 }
1239
1240 /* Test whether a value is loop invariant.
1241  *
1242  * @param n      The node to be tested.
1243  * @param block  A block node.  We pass the block, not the loop as we must
1244  *               start off with a block loop to find all proper uses.
1245  *
1246  * Returns non-zero, if the node n is not changed in the loop block
1247  * belongs to or in inner loops of this blocks loop. */
1248 int is_loop_invariant(const ir_node *n, const ir_node *block) {
1249         ir_loop *l = get_irn_loop(block);
1250         const ir_node *b = is_Block(n) ? n : get_nodes_block(n);
1251         return !is_loop_variant(l, get_irn_loop(b));
1252 }