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