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