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