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