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

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