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