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