nsz Git - libfirm/blob - ir/ana/ircfscc.c

   1 /*
   2  * Copyright (C) 1995-2011 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 backedge/cfloop
  23  *            datastructures. A variation on the Tarjan algorithm. See also
  24  *            [Trapp:99], Chapter 5.2.1.2.
  25  * @author    Goetz Lindenmaier
  26  * @date      7.2002
  27  * @version   $Id$
  28  */
  29 #include "config.h"
  30
  31 #include <string.h>
  32
  33 #include "irloop_t.h"
  34 #include "irnode_t.h"
  35 #include "irgraph_t.h"
  36 #include "array.h"
  37 #include "pmap.h"
  38 #include "irgwalk.h"
  39 #include "irprog_t.h"
  40 #include "irdump.h"
  41
  42 #define NO_CFLOOPS_WITHOUT_HEAD 1
  43
  44 /** The outermost graph the scc is computed for */
  45 static ir_graph *outermost_ir_graph;
  46 /** Current cfloop construction is working on. */
  47 static ir_loop *current_loop;
  48 /** Counts the number of allocated cfloop nodes.
  49  * Each cfloop node gets a unique number.
  50  * @todo What for? ev. remove.
  51  */
  52 static int loop_node_cnt = 0;
  53 /** Counter to generate depth first numbering of visited nodes. */
  54 static int current_dfn = 1;
  55
  56 static unsigned max_loop_depth = 0;
  57
  58 void link_to_reg_end(ir_node *n, void *env);
  59
  60 /**********************************************************************/
  61 /* Node attributes                                                   **/
  62 /**********************************************************************/
  63
  64 /**********************************************************************/
  65 /* Node attributes needed for the construction.                      **/
  66 /**********************************************************************/
  67
  68 /**
  69  * The SCC info. Additional fields for an ir-node needed for the
  70  * construction.
  71  */
  72 typedef struct scc_info {
  73         int in_stack;          /**< Marks whether node is on the stack. */
  74         int dfn;               /**< Depth first search number. */
  75         int uplink;            /**< dfn number of ancestor. */
  76 } scc_info;
  77
  78 /** Allocate a new scc_info on the given obstack */
  79 static inline scc_info *new_scc_info(struct obstack *obst)
  80 {
  81         return OALLOCZ(obst, scc_info);
  82 }
  83
  84 /**
  85  * Marks the node n to be on the stack.
  86  */
  87 static inline void mark_irn_in_stack(ir_node *n)
  88 {
  89         scc_info *info = (scc_info*) get_irn_link(n);
  90         info->in_stack = 1;
  91 }
  92
  93 /**
  94  * Marks the node n to be not on the stack.
  95  */
  96 static inline void mark_irn_not_in_stack(ir_node *n)
  97 {
  98         scc_info *info = (scc_info*) get_irn_link(n);
  99         info->in_stack = 0;
 100 }
 101
 102 /**
 103  * Returns whether node n is on the stack.
 104  */
 105 static inline int irn_is_in_stack(ir_node *n)
 106 {
 107         scc_info *info = (scc_info*) get_irn_link(n);
 108         return info->in_stack;
 109 }
 110
 111 /**
 112  * Sets node n uplink value.
 113  */
 114 static inline void set_irn_uplink(ir_node *n, int uplink)
 115 {
 116         scc_info *info = (scc_info*) get_irn_link(n);
 117         info->uplink = uplink;
 118 }
 119
 120 /**
 121  * Return node n uplink value.
 122  */
 123 static inline int get_irn_uplink(ir_node *n)
 124 {
 125         scc_info *info = (scc_info*) get_irn_link(n);
 126         return info->uplink;
 127 }
 128
 129 /**
 130  * Sets node n dfn value.
 131  */
 132 static inline void set_irn_dfn(ir_node *n, int dfn)
 133 {
 134         scc_info *info = (scc_info*) get_irn_link(n);
 135         info->dfn = dfn;
 136 }
 137
 138 /**
 139  * Returns node n dfn value.
 140  */
 141 static inline int get_irn_dfn(ir_node *n)
 142 {
 143         scc_info *info = (scc_info*) get_irn_link(n);
 144         return info->dfn;
 145 }
 146
 147 /**********************************************************************/
 148 /* A stack.                                                          **/
 149 /**********************************************************************/
 150
 151 /** An IR-node stack */
 152 static ir_node **stack = NULL;
 153 /** The top (index) of the IR-node stack */
 154 static size_t    tos = 0;
 155
 156 /**
 157  * Initializes the IR-node stack
 158  */
 159 static inline void init_stack(void)
 160 {
 161         if (stack) {
 162                 ARR_RESIZE(ir_node *, stack, 1000);
 163         } else {
 164                 stack = NEW_ARR_F(ir_node *, 1000);
 165         }
 166         tos = 0;
 167 }
 168
 169 static void finish_stack(void)
 170 {
 171         DEL_ARR_F(stack);
 172         stack = NULL;
 173 }
 174
 175 /**
 176  * Push a node n onto the IR-node stack.
 177  */
 178 static inline void push(ir_node *n)
 179 {
 180         if (tos == ARR_LEN(stack)) {
 181                 size_t nlen = ARR_LEN(stack) * 2;
 182                 ARR_RESIZE(ir_node *, stack, nlen);
 183         }
 184         stack[tos++] = n;
 185         mark_irn_in_stack(n);
 186 }
 187
 188 /**
 189  * Pop a node from the IR-node stack and return it.
 190  */
 191 static inline ir_node *pop(void)
 192 {
 193         ir_node *n = stack[--tos];
 194         mark_irn_not_in_stack(n);
 195         return n;
 196 }
 197
 198 /**
 199  * The nodes from tos up to n belong to the current loop.
 200  * Removes them from the stack and adds them to the current loop.
 201  */
 202 static inline void pop_scc_to_loop(ir_node *n)
 203 {
 204         ir_node *m;
 205
 206         do {
 207                 m = pop();
 208                 loop_node_cnt++;
 209                 set_irn_dfn(m, loop_node_cnt);
 210                 add_loop_node(current_loop, m);
 211                 set_irn_loop(m, current_loop);
 212         } while (m != n);
 213 }
 214
 215 /* GL ??? my last son is my grandson???  Removes cfloops with no
 216    ir_nodes in them.  Such loops have only another loop as son. (Why
 217    can't they have two loops as sons? Does it never get that far? ) */
 218 static void close_loop(ir_loop *l)
 219 {
 220         size_t last = get_loop_n_elements(l) - 1;
 221         loop_element lelement = get_loop_element(l, last);
 222         ir_loop *last_son = lelement.son;
 223
 224         if (get_kind(last_son) == k_ir_loop &&
 225             get_loop_n_elements(last_son) == 1) {
 226                 ir_loop *gson;
 227
 228                 lelement = get_loop_element(last_son, 0);
 229                 gson = lelement.son;
 230                 if (get_kind(gson) == k_ir_loop) {
 231                         loop_element new_last_son;
 232
 233                         gson->outer_loop = l;
 234                         new_last_son.son = gson;
 235                         l->children[last] = new_last_son;
 236
 237                         /* the loop last_son is dead now, recover at least some memory */
 238                         DEL_ARR_F(last_son->children);
 239                 }
 240         }
 241
 242         current_loop = l;
 243 }
 244
 245 /**
 246  * Removes and unmarks all nodes up to n from the stack.
 247  * The nodes must be visited once more to assign them to a scc.
 248  */
 249 static inline void pop_scc_unmark_visit(ir_node *n)
 250 {
 251         ir_node *m;
 252
 253         do {
 254                 m = pop();
 255                 set_irn_visited(m, 0);
 256         } while (m != n);
 257 }
 258
 259 /**********************************************************************/
 260 /* The loop datastructure.                                           **/
 261 /**********************************************************************/
 262
 263 /**
 264  * Allocates a new loop as son of current_loop.  Sets current_loop
 265  * to the new loop and returns its father.
 266  * The loop is allocated on the outermost_ir_graphs's obstack.
 267  */
 268 static ir_loop *new_loop(void)
 269 {
 270         ir_loop *father = current_loop;
 271         ir_loop *son    = alloc_loop(father, outermost_ir_graph->obst);
 272
 273         if (son->depth > max_loop_depth) max_loop_depth = son->depth;
 274         current_loop = son;
 275         return father;
 276 }
 277
 278 /**********************************************************************/
 279 /* Constructing and destructing the loop/backedge information.       **/
 280 /**********************************************************************/
 281
 282 /* Initialization steps. **********************************************/
 283
 284 /**
 285  * Allocates a scc_info for every Block node n.
 286  * Clear the backedges for all nodes.
 287  * Called from a walker.
 288  */
 289 static inline void init_node(ir_node *n, void *env)
 290 {
 291         struct obstack *obst = (struct obstack*) env;
 292         if (is_Block(n))
 293                 set_irn_link(n, new_scc_info(obst));
 294         clear_backedges(n);
 295 }
 296
 297 /**
 298  * Initializes the common global settings for the scc algorithm
 299  */
 300 static inline void init_scc_common(void)
 301 {
 302         current_dfn   = 1;
 303         loop_node_cnt = 0;
 304         init_stack();
 305 }
 306
 307 /**
 308  * Initializes the scc algorithm for the intraprocedural case.
 309  * Add scc info to every block node.
 310  */
 311 static inline void init_scc(ir_graph *irg, struct obstack *obst)
 312 {
 313         init_scc_common();
 314         irg_walk_graph(irg, init_node, NULL, obst);
 315 }
 316
 317 static inline void finish_scc(void)
 318 {
 319         finish_stack();
 320 }
 321
 322 /**
 323  * Condition for breaking the recursion: n is the block
 324  * that gets the initial control flow from the Start node.
 325  */
 326 static int is_outermost_StartBlock(ir_node *n)
 327 {
 328         /* Test whether this is the outermost Start node.  If so
 329            recursion must end. */
 330         assert(is_Block(n));
 331         if (get_Block_n_cfgpreds(n) == 1  &&
 332             is_Start(skip_Proj(get_Block_cfgpred(n, 0))) &&
 333             get_Block_cfgpred_block(n, 0) == n) {
 334                 return 1;
 335         }
 336         return 0;
 337 }
 338
 339 /** Returns non-zero if n is a loop header, i.e., it is a Block node
 340  *  and has predecessors within the cfloop and out of the cfloop.
 341  *
 342  *  @param n     the block node to check
 343  *  @param root  only needed for assertion.
 344  */
 345 static int is_head(ir_node *n, ir_node *root)
 346 {
 347         int i, arity;
 348         int some_outof_loop = 0, some_in_loop = 0;
 349         (void) root;
 350
 351         assert(is_Block(n));
 352
 353         if (!is_outermost_StartBlock(n)) {
 354                 arity = get_Block_n_cfgpreds(n);
 355                 for (i = 0; i < arity; i++) {
 356                         ir_node *pred = get_Block_cfgpred_block(n, i);
 357                         /* ignore Bad control flow: it cannot happen */
 358                         if (is_Bad(pred))
 359                                 continue;
 360                         if (is_backedge(n, i))
 361                                 continue;
 362                         if (!irn_is_in_stack(pred)) {
 363                                 some_outof_loop = 1;
 364                         } else {
 365                                 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
 366                                 some_in_loop = 1;
 367                         }
 368                 }
 369         }
 370         return some_outof_loop & some_in_loop;
 371 }
 372
 373
 374 /**
 375  * Returns non-zero if n is possible loop head of an endless loop.
 376  * I.e., it is a Block node and has only predecessors
 377  * within the loop.
 378  *
 379  * @param n     the block node to check
 380  * @param root  only needed for assertion.
 381  */
 382 static int is_endless_head(ir_node *n, ir_node *root)
 383 {
 384         int i, arity;
 385         int none_outof_loop = 1, some_in_loop = 0;
 386         (void) root;
 387
 388         assert(is_Block(n));
 389         /* Test for legal loop header: Block, Phi, ... */
 390         if (!is_outermost_StartBlock(n)) {
 391                 arity = get_Block_n_cfgpreds(n);
 392                 for (i = 0; i < arity; i++) {
 393                         ir_node *pred = get_Block_cfgpred_block(n, i);
 394                         /* ignore Bad control flow: it cannot happen */
 395                         if (is_Bad(pred))
 396                                 continue;
 397                         if (is_backedge(n, i))
 398                                 continue;
 399                         if (!irn_is_in_stack(pred)) {
 400                                 none_outof_loop = 0;
 401                         } else {
 402                                 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
 403                                 some_in_loop = 1;
 404                         }
 405                 }
 406         }
 407         return none_outof_loop && some_in_loop;
 408 }
 409
 410 /**
 411  * Returns index of the predecessor with the smallest dfn number
 412  * greater-equal than limit.
 413  */
 414 static int smallest_dfn_pred(ir_node *n, int limit)
 415 {
 416         int i, index = -2, min = -1;
 417
 418         if (!is_outermost_StartBlock(n)) {
 419                 int arity = get_Block_n_cfgpreds(n);
 420                 for (i = 0; i < arity; i++) {
 421                         ir_node *pred = get_Block_cfgpred_block(n, i);
 422                         /* ignore Bad control flow: it cannot happen */
 423                         if (is_Bad(pred))
 424                                 continue;
 425                         if (is_backedge(n, i) || !irn_is_in_stack(pred))
 426                                 continue;
 427                         if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
 428                                 index = i;
 429                                 min = get_irn_dfn(pred);
 430                         }
 431                 }
 432         }
 433         return index;
 434 }
 435
 436 /**
 437  * Returns index of the predecessor with the largest dfn number.
 438  */
 439 static int largest_dfn_pred(ir_node *n)
 440 {
 441         int i, index = -2, max = -1;
 442
 443         if (!is_outermost_StartBlock(n)) {
 444                 int arity = get_Block_n_cfgpreds(n);
 445                 for (i = 0; i < arity; i++) {
 446                         ir_node *pred = get_Block_cfgpred_block(n, i);
 447                         /* ignore Bad control flow: it cannot happen */
 448                         if (is_Bad(pred))
 449                                 continue;
 450                         if (is_backedge(n, i) || !irn_is_in_stack(pred))
 451                                 continue;
 452                         if (get_irn_dfn(pred) > max) {
 453                                 index = i;
 454                                 max = get_irn_dfn(pred);
 455                         }
 456                 }
 457         }
 458         return index;
 459 }
 460
 461 /**
 462  * Searches the stack for possible loop heads.  Tests these for backedges.
 463  * If it finds a head with an unmarked backedge it marks this edge and
 464  * returns the tail of the loop.
 465  * If it finds no backedge returns NULL.
 466  */
 467 static ir_node *find_tail(ir_node *n)
 468 {
 469         ir_node *m;
 470         int      res_index = -2;
 471         size_t   i;
 472
 473         m = stack[tos - 1];  /* tos = top of stack */
 474         if (is_head(m, n)) {
 475                 res_index = smallest_dfn_pred(m, 0);
 476                 if ((res_index == -2) &&  /* no smallest dfn pred found. */
 477                         (n ==  m))
 478                         return NULL;
 479         } else {
 480                 if (m == n)
 481                         return NULL;
 482                 for (i = tos - 1; i != 0;) {
 483                         m = stack[--i];
 484                         if (is_head(m, n)) {
 485                                 res_index = smallest_dfn_pred(m, get_irn_dfn(m) + 1);
 486                                 if (res_index == -2)  /* no smallest dfn pred found. */
 487                                         res_index = largest_dfn_pred(m);
 488
 489                                 if ((m == n) && (res_index == -2)) {
 490                                         i = (size_t)-1;
 491                                 }
 492                                 break;
 493                         }
 494
 495
 496                         /* We should not walk past our selves on the stack:  The upcoming nodes
 497                            are not in this loop. We assume a loop not reachable from Start. */
 498                         if (m == n) {
 499                                 i = (size_t)-1;
 500                                 break;
 501                         }
 502                 }
 503
 504                 if (i == (size_t)-1) {
 505                         /* A dead loop not reachable from Start. */
 506                         for (i = tos - 1; i != 0;) {
 507                                 m = stack[--i];
 508                                 if (is_endless_head(m, n)) {
 509                                         res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
 510                                         if (res_index == -2)  /* no smallest dfn pred found. */
 511                                                 res_index = largest_dfn_pred(m);
 512                                         break;
 513                                 }
 514                                 if (m == n) break;   /* It's not an unreachable loop, either. */
 515                         }
 516                         //assert(0 && "no head found on stack");
 517                 }
 518         }
 519         assert(res_index > -2);
 520
 521         set_backedge(m, res_index);
 522         return is_outermost_StartBlock(n) ? NULL : get_Block_cfgpred_block(m, res_index);
 523 }
 524
 525 /**
 526  * returns non.zero if l is the outermost loop.
 527  */
 528 inline static int is_outermost_loop(ir_loop *l)
 529 {
 530         return l == get_loop_outer_loop(l);
 531 }
 532
 533 /*-----------------------------------------------------------*
 534  *                   The core algorithm.                     *
 535  *-----------------------------------------------------------*/
 536
 537 /**
 538  * Walks over all blocks of a graph
 539  */
 540 static void cfscc(ir_node *n)
 541 {
 542         int i;
 543
 544         assert(is_Block(n));
 545
 546         if (irn_visited_else_mark(n)) return;
 547
 548         /* Initialize the node */
 549         set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
 550         set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
 551         set_irn_loop(n, NULL);
 552         ++current_dfn;
 553         push(n);
 554
 555         if (!is_outermost_StartBlock(n)) {
 556                 int arity = get_Block_n_cfgpreds(n);
 557
 558                 for (i = 0; i < arity; i++) {
 559                         ir_node *m;
 560
 561                         if (is_backedge(n, i))
 562                                 continue;
 563                         m = get_Block_cfgpred_block(n, i);
 564                         /* ignore Bad control flow: it cannot happen */
 565                         if (is_Bad(m))
 566                                 continue;
 567
 568                         cfscc(m);
 569                         if (irn_is_in_stack(m)) {
 570                                 /* Uplink of m is smaller if n->m is a backedge.
 571                                    Propagate the uplink to mark the cfloop. */
 572                                 if (get_irn_uplink(m) < get_irn_uplink(n))
 573                                         set_irn_uplink(n, get_irn_uplink(m));
 574                         }
 575                 }
 576         }
 577
 578         if (get_irn_dfn(n) == get_irn_uplink(n)) {
 579                 /* This condition holds for
 580                    1) the node with the incoming backedge.
 581                       That is: We found a cfloop!
 582                    2) Straight line code, because no uplink has been propagated, so the
 583                       uplink still is the same as the dfn.
 584
 585                    But n might not be a proper cfloop head for the analysis. Proper cfloop
 586                    heads are Block and Phi nodes. find_tail searches the stack for
 587                    Block's and Phi's and takes those nodes as cfloop heads for the current
 588                    cfloop instead and marks the incoming edge as backedge. */
 589
 590                 ir_node *tail = find_tail(n);
 591                 if (tail) {
 592                         /* We have a cfloop, that is no straight line code,
 593                            because we found a cfloop head!
 594                            Next actions: Open a new cfloop on the cfloop tree and
 595                            try to find inner cfloops */
 596
 597 #if NO_CFLOOPS_WITHOUT_HEAD
 598
 599                         /* This is an adaption of the algorithm from fiasco / optscc to
 600                          * avoid cfloops without Block or Phi as first node.  This should
 601                          * severely reduce the number of evaluations of nodes to detect
 602                          * a fixpoint in the heap analysis.
 603                          * Further it avoids cfloops without firm nodes that cause errors
 604                          * in the heap analyses. */
 605
 606                         ir_loop *l;
 607                         int close;
 608                         if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
 609                                 l = new_loop();
 610                                 close = 1;
 611                         } else {
 612                                 l = current_loop;
 613                                 close = 0;
 614                         }
 615
 616 #else
 617
 618                         ir_loop *l = new_loop();
 619
 620 #endif
 621
 622                         /* Remove the cfloop from the stack ... */
 623                         pop_scc_unmark_visit(n);
 624
 625                         /* The current backedge has been marked, that is temporarily eliminated,
 626                            by find tail. Start the scc algorithm
 627                            anew on the subgraph thats left (the current cfloop without the backedge)
 628                            in order to find more inner cfloops. */
 629
 630                         cfscc(tail);
 631
 632                         assert(irn_visited(n));
 633 #if NO_CFLOOPS_WITHOUT_HEAD
 634                         if (close)
 635 #endif
 636                                 close_loop(l);
 637                 } else {
 638                         /* AS: No cfloop head was found, that is we have straight line code.
 639                                Pop all nodes from the stack to the current cfloop. */
 640                         pop_scc_to_loop(n);
 641                 }
 642         }
 643 }
 644
 645 /* Constructs control flow backedge information for irg. */
 646 int construct_cf_backedges(ir_graph *irg)
 647 {
 648         ir_graph *rem = current_ir_graph;
 649         ir_loop *head_rem;
 650         ir_node *end = get_irg_end(irg);
 651         struct obstack temp;
 652         int i;
 653
 654         max_loop_depth = 0;
 655
 656         current_ir_graph   = irg;
 657         outermost_ir_graph = irg;
 658
 659         obstack_init(&temp);
 660         init_scc(irg, &temp);
 661
 662         current_loop = NULL;
 663         new_loop();  /* sets current_loop */
 664         head_rem = current_loop; /* Just for assertion */
 665
 666         inc_irg_visited(irg);
 667
 668         /* walk over all blocks of the graph, including keep alives */
 669         cfscc(get_irg_end_block(irg));
 670         for (i = get_End_n_keepalives(end) - 1; i >= 0; --i) {
 671                 ir_node *el = get_End_keepalive(end, i);
 672                 if (is_Block(el))
 673                         cfscc(el);
 674         }
 675         finish_scc();
 676         obstack_free(&temp, NULL);
 677
 678         assert(head_rem == current_loop);
 679         mature_loops(current_loop, irg->obst);
 680         set_irg_loop(irg, current_loop);
 681         set_irg_loopinfo_state(irg, loopinfo_cf_consistent);
 682         assert(get_irg_loop(irg)->kind == k_ir_loop);
 683
 684         current_ir_graph = rem;
 685         return max_loop_depth;
 686 }
 687
 688 void assure_cf_loop(ir_graph *irg)
 689 {
 690         irg_loopinfo_state state = get_irg_loopinfo_state(irg);
 691
 692         if (state != loopinfo_cf_consistent)
 693                 construct_cf_backedges(irg);
 694 }