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