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