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 /**
 213  * Frees the stack.
 214  */
 215 static void finish_stack(void) {
 216         DEL_ARR_F(stack);
 217         stack = NULL;
 218 }
 219
 220 /**
 221  * push a node onto the stack
 222  *
 223  * @param n  The node to push
 224  */
 225 static INLINE void push(ir_node *n) {
 226         if (tos == ARR_LEN(stack)) {
 227                 int nlen = ARR_LEN(stack) * 2;
 228                 ARR_RESIZE(ir_node *, stack, nlen);
 229         }
 230         stack [tos++] = n;
 231         mark_irn_in_stack(n);
 232 }
 233
 234 /**
 235  * pop a node from the stack
 236  *
 237  * @return  The topmost node
 238  */
 239 static INLINE ir_node *pop(void) {
 240         ir_node *n = stack[--tos];
 241         mark_irn_not_in_stack(n);
 242         return n;
 243 }
 244
 245 /**
 246  * The nodes up to n belong to the current loop.
 247  * Removes them from the stack and adds them to the current loop.
 248  */
 249 static INLINE void pop_scc_to_loop(ir_node *n) {
 250         ir_node *m;
 251         int i = 0;
 252
 253         do {
 254                 m = pop();
 255
 256                 loop_node_cnt++;
 257                 set_irn_dfn(m, loop_node_cnt);
 258                 add_loop_node(current_loop, m);
 259                 set_irn_loop(m, current_loop);
 260                 ++i;
 261         } while (m != n);
 262
 263         /* i might be bigger than 1 for dead (and that's why bad) loops */
 264         /* if(i > 1)
 265                 printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!11111\n");
 266          */
 267 }
 268
 269 /* GL ??? my last son is my grandson???  Removes loops with no
 270    ir_nodes in them.  Such loops have only another loop as son. (Why
 271    can't they have two loops as sons? Does it never get that far? ) */
 272 static void close_loop(ir_loop *l) {
 273         int last = get_loop_n_elements(l) - 1;
 274         loop_element lelement = get_loop_element(l, last);
 275         ir_loop *last_son = lelement.son;
 276
 277         if (get_kind(last_son) == k_ir_loop &&
 278                 get_loop_n_elements(last_son) == 1) {
 279                         ir_loop *gson;
 280
 281                         lelement = get_loop_element(last_son, 0);
 282                         gson = lelement.son;
 283
 284                         if (get_kind(gson) == k_ir_loop) {
 285                                 loop_element new_last_son;
 286
 287                                 gson->outer_loop = l;
 288                                 new_last_son.son = gson;
 289                                 l->children[last] = new_last_son;
 290                         }
 291         }
 292
 293         current_loop = l;
 294 }
 295
 296 /* Removes and unmarks all nodes up to n from the stack.
 297    The nodes must be visited once more to assign them to a scc. */
 298 static INLINE void pop_scc_unmark_visit(ir_node *n) {
 299         ir_node *m = NULL;
 300
 301         while (m != n) {
 302                 m = pop();
 303                 set_irn_visited(m, 0);
 304         }
 305 }
 306
 307 /**********************************************************************/
 308 /* The loop datastructure.                                           **/
 309 /**********************************************************************/
 310
 311 /* Allocates a new loop as son of current_loop.  Sets current_loop
 312    to the new loop and returns the father. */
 313 static ir_loop *new_loop(void) {
 314         ir_loop *father = current_loop;
 315         ir_loop *son    = alloc_loop(father, outermost_ir_graph->obst);
 316
 317         if (son->depth > max_loop_depth) max_loop_depth = son->depth;
 318         current_loop = son;
 319         return father;
 320 }
 321
 322 /**********************************************************************/
 323 /* Constructing and destructing the loop/backedge information.       **/
 324 /**********************************************************************/
 325
 326 /* Initialization steps. **********************************************/
 327
 328 static INLINE void init_node(ir_node *n, void *env) {
 329         struct obstack *obst = env;
 330         set_irn_link(n, new_scc_info(obst));
 331         clear_backedges(n);
 332 }
 333
 334 static INLINE void init_scc_common(void) {
 335         current_dfn = 1;
 336         loop_node_cnt = 0;
 337         init_stack();
 338 }
 339
 340 static INLINE void init_scc(ir_graph *irg, struct obstack *obst) {
 341         init_scc_common();
 342         irg_walk_graph(irg, init_node, NULL, obst);
 343         /*
 344         irg_walk (irg, link_to_reg_end, NULL, NULL);
 345         */
 346 }
 347
 348 static INLINE void finish_scc(void)
 349 {
 350         finish_stack();
 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
 935         finish_scc();
 936         obstack_free(&temp, NULL);
 937
 938         assert(head_rem == current_loop);
 939         mature_loops(current_loop, irg->obst);
 940         set_irg_loop(irg, current_loop);
 941         set_irg_loopinfo_state(irg, loopinfo_consistent);
 942         assert(get_irg_loop(irg)->kind == k_ir_loop);
 943         current_ir_graph = rem;
 944         return max_loop_depth;
 945 }
 946
 947
 948 #ifdef INTERPROCEDURAL_VIEW
 949 int construct_ip_backedges(void) {
 950         ir_graph *rem = current_ir_graph;
 951         int rem_ipv = get_interprocedural_view();
 952         int i;
 953         strcut obstack temp;
 954
 955         max_loop_depth = 0;
 956         assert(get_irp_ip_view_state() == ip_view_valid);
 957
 958         outermost_ir_graph = get_irp_main_irg();
 959
 960         obstack_init(&temp);
 961         init_ip_scc(&temp);
 962
 963         current_loop = NULL;
 964         new_loop();  /* sets current_loop */
 965         set_interprocedural_view(1);
 966
 967         inc_max_irg_visited();
 968         for (i = 0; i < get_irp_n_irgs(); i++)
 969                 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
 970
 971         /** We have to start the walk at the same nodes as cg_walk. **/
 972         /* Walk starting at unreachable procedures. Only these
 973          * have End blocks visible in interprocedural view. */
 974         for (i = 0; i < get_irp_n_irgs(); i++) {
 975                 ir_node *sb;
 976                 current_ir_graph = get_irp_irg(i);
 977
 978                 sb = get_irg_start_block(current_ir_graph);
 979
 980                 if ((get_Block_n_cfgpreds(sb) > 1) ||
 981                     (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb))
 982                         continue;
 983
 984                 scc(get_irg_end(current_ir_graph));
 985         }
 986
 987         /* Check whether we walked all procedures: there could be procedures
 988            with cyclic calls but no call from the outside. */
 989         for (i = 0; i < get_irp_n_irgs(); i++) {
 990                 ir_node *sb;
 991                 current_ir_graph = get_irp_irg(i);
 992
 993                 /* Test start block: if inner procedure end and end block are not
 994                  * visible and therefore not marked. */
 995                 sb = get_irg_start_block(current_ir_graph);
 996                 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
 997         }
 998
 999         /* Walk all endless loops in inner procedures.
1000          * We recognize an inner procedure if the End node is not visited. */
1001         for (i = 0; i < get_irp_n_irgs(); i++) {
1002                 ir_node *e;
1003                 current_ir_graph = get_irp_irg(i);
1004
1005                 e = get_irg_end(current_ir_graph);
1006                 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1007                         int j;
1008                         /* Don't visit the End node. */
1009                         for (j = 0; j < get_End_n_keepalives(e); j++)
1010                                 scc(get_End_keepalive(e, j));
1011                 }
1012         }
1013
1014         set_irg_loop(outermost_ir_graph, current_loop);
1015         set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1016         assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1017
1018         obstack_free(&temp, NULL);
1019         current_ir_graph = rem;
1020         set_interprocedural_view(rem_ipv);
1021         return max_loop_depth;
1022 }
1023
1024 void my_construct_ip_backedges(void) {
1025         ir_graph *rem = current_ir_graph;
1026         int rem_ipv = get_interprocedural_view();
1027         int i;
1028
1029         assert(get_irp_ip_view_state() == ip_view_valid);
1030
1031         outermost_ir_graph = get_irp_main_irg();
1032
1033         init_ip_scc();
1034
1035         current_loop = NULL;
1036         new_loop();  /* sets current_loop */
1037         set_interprocedural_view(1);
1038
1039         inc_max_irg_visited();
1040         for (i = 0; i < get_irp_n_irgs(); i++)
1041                 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1042
1043         /** We have to start the walk at the same nodes as cg_walk. **/
1044         /* Walk starting at unreachable procedures. Only these
1045          * have End blocks visible in interprocedural view. */
1046         for (i = 0; i < get_irp_n_irgs(); i++) {
1047                 ir_node *sb;
1048                 current_ir_graph = get_irp_irg(i);
1049
1050                 sb = get_irg_start_block(current_ir_graph);
1051
1052                 if ((get_Block_n_cfgpreds(sb) > 1) ||
1053                     (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1054
1055                 my_scc(get_irg_end(current_ir_graph));
1056         }
1057
1058         /* Check whether we walked all procedures: there could be procedures
1059            with cyclic calls but no call from the outside. */
1060         for (i = 0; i < get_irp_n_irgs(); i++) {
1061                 ir_node *sb;
1062                 current_ir_graph = get_irp_irg(i);
1063
1064                 /* Test start block: if inner procedure end and end block are not
1065                  * visible and therefore not marked. */
1066                 sb = get_irg_start_block(current_ir_graph);
1067                 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph))
1068                         scc(sb);
1069         }
1070
1071         /* Walk all endless loops in inner procedures.
1072          * We recognize an inner procedure if the End node is not visited. */
1073         for (i = 0; i < get_irp_n_irgs(); i++) {
1074                 ir_node *e;
1075                 current_ir_graph = get_irp_irg(i);
1076
1077                 e = get_irg_end(current_ir_graph);
1078                 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1079                         int j;
1080                         /* Don't visit the End node. */
1081                         for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1082                 }
1083         }
1084
1085         set_irg_loop(outermost_ir_graph, current_loop);
1086         set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1087         assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1088
1089         current_ir_graph = rem;
1090         set_interprocedural_view(rem_ipv);
1091 }
1092 #endif
1093
1094 static void reset_backedges(ir_node *n) {
1095         if (is_possible_loop_head(n)) {
1096 #ifdef INTERPROCEDURAL_VIEW
1097                 int rem = get_interprocedural_view();
1098
1099                 set_interprocedural_view(1);
1100                 clear_backedges(n);
1101                 set_interprocedural_view(1);
1102                 clear_backedges(n);
1103                 set_interprocedural_view(rem);
1104 #else
1105                 clear_backedges(n);
1106 #endif
1107         }
1108 }
1109
1110
1111 /*
1112 static void loop_reset_backedges(ir_loop *l) {
1113         int i;
1114         reset_backedges(get_loop_node(l, 0));
1115         for (i = 0; i < get_loop_n_nodes(l); ++i)
1116                 set_irn_loop(get_loop_node(l, i), NULL);
1117         for (i = 0; i < get_loop_n_sons(l); ++i) {
1118                 loop_reset_backedges(get_loop_son(l, i));
1119         }
1120 }
1121 */
1122
1123 static void loop_reset_node(ir_node *n, void *env) {
1124         (void) env;
1125         set_irn_loop(n, NULL);
1126         reset_backedges(n);
1127 }
1128
1129
1130 /** Removes all loop information.
1131     Resets all backedges */
1132 void free_loop_information(ir_graph *irg) {
1133         /* We can not use this recursion, as the loop might contain
1134            illegal nodes by now.  Why else would we throw away the
1135            representation?
1136         if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1137         */
1138         irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1139         set_irg_loop(irg, NULL);
1140         set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1141         /* We cannot free the loop nodes, they are on the obstack. */
1142 }
1143
1144
1145 void free_all_loop_information(void) {
1146         int i;
1147 #ifdef INTERPROCEDURAL_VIEW
1148         int rem = get_interprocedural_view();
1149         set_interprocedural_view(1);  /* To visit all filter nodes */
1150 #endif
1151         for (i = 0; i < get_irp_n_irgs(); i++) {
1152                 free_loop_information(get_irp_irg(i));
1153         }
1154 #ifdef INTERPROCEDURAL_VIEW
1155         set_interprocedural_view(rem);
1156 #endif
1157 }
1158
1159
1160
1161
1162
1163 /* Debug stuff *************************************************/
1164
1165 static int test_loop_node(ir_loop *l) {
1166         int i, has_node = 0, found_problem = 0;
1167         loop_element le;
1168
1169         assert(l && l->kind == k_ir_loop);
1170
1171         if (get_loop_n_elements(l) == 0) {
1172                 found_problem = 1;
1173                 dump_loop(l, "-ha");
1174         }
1175
1176         le = get_loop_element(l, 0);
1177         if (*(le.kind) != k_ir_node) {
1178                 assert(le.kind && *(le.kind) == k_ir_loop);
1179
1180                 found_problem = 1;
1181                 dump_loop(l, "-ha");
1182         }
1183
1184         if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1185                 found_problem = 1;
1186                 dump_loop(l, "-ha");
1187         }
1188
1189         if ((get_loop_depth(l) != 0) &&
1190                 (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1191                         found_problem = 1;
1192                         dump_loop(l, "-ha");
1193         }
1194
1195         /* Recur */
1196         has_node = 0;
1197         for (i = 0; i < get_loop_n_elements(l); ++i) {
1198                 le = get_loop_element(l, i);
1199                 if (*(le.kind) == k_ir_node)
1200                         has_node++;
1201                 else
1202                         if (test_loop_node(le.son)) found_problem = 1;
1203         }
1204
1205         if (has_node == 0) {
1206                 found_problem = 1;
1207                 dump_loop(l, "-ha");
1208         }
1209
1210         return found_problem;
1211 }
1212
1213 /** Prints all loop nodes that
1214  *  - do not have any firm nodes, only loop sons
1215  *  - the header is not a Phi, Block or Filter.
1216  */
1217 void find_strange_loop_nodes(ir_loop *l) {
1218         int found_problem = 0;
1219         found_problem = test_loop_node(l);
1220         printf("Finished Test\n\n");
1221         if (found_problem) exit(0);
1222
1223 }
1224
1225 /* ------------------------------------------------------------------- */
1226 /* Simple analyses based on the loop information                       */
1227 /* ------------------------------------------------------------------- */
1228
1229 int is_loop_variant(ir_loop *l, ir_loop *b) {
1230         int i, n_elems;
1231
1232         if (l == b) return 1;
1233
1234         n_elems = get_loop_n_elements(l);
1235         for (i = 0; i < n_elems; ++i) {
1236                 loop_element e = get_loop_element(l, i);
1237                 if (is_ir_loop(e.kind))
1238                         if (is_loop_variant(e.son, b))
1239                                 return 1;
1240         }
1241
1242         return 0;
1243 }
1244
1245 /* Test whether a value is loop invariant.
1246  *
1247  * @param n      The node to be tested.
1248  * @param block  A block node.  We pass the block, not the loop as we must
1249  *               start off with a block loop to find all proper uses.
1250  *
1251  * Returns non-zero, if the node n is not changed in the loop block
1252  * belongs to or in inner loops of this blocks loop. */
1253 int is_loop_invariant(const ir_node *n, const ir_node *block) {
1254         ir_loop *l = get_irn_loop(block);
1255         const ir_node *b = is_Block(n) ? n : get_nodes_block(n);
1256         return !is_loop_variant(l, get_irn_loop(b));
1257 }