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

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ana/irscc.c
   4  * Purpose:     Compute the strongly connected regions and build
   5  *              backedge/cfloop datastructures.
   6  *              A variation on the Tarjan algorithm. See also [Trapp:99],
   7  *              Chapter 5.2.1.2.
   8  * Author:      Goetz Lindenmaier
   9  * Modified by:
  10  * Created:     7.2002
  11  * CVS-ID:      $Id$
  12  * Copyright:   (c) 2002-2003 Universität Karlsruhe
  13  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  14  */
  15
  16 #ifdef HAVE_CONFIG_H
  17 #include "config.h"
  18 #endif
  19
  20 #include <string.h>
  21
  22 #include "irloop_t.h"
  23 #include "irnode_t.h"
  24 #include "irgraph_t.h"
  25 #include "array.h"
  26 #include "pmap.h"
  27 #include "irgwalk.h"
  28 #include "irprog_t.h"
  29 #include "irdump.h"
  30
  31 static ir_graph *outermost_ir_graph;      /* The outermost graph the scc is computed
  32                       for */
  33 static ir_loop *current_loop;      /* Current cfloop construction is working
  34                       on. */
  35 static int loop_node_cnt = 0;      /* Counts the number of allocated cfloop nodes.
  36                       Each cfloop node gets a unique number.
  37                       What for? ev. remove. @@@ */
  38 static int current_dfn = 1;        /* Counter to generate depth first numbering
  39                       of visited nodes.  */
  40
  41 void link_to_reg_end (ir_node *n, void *env);
  42
  43 /**********************************************************************/
  44 /* Node attributes                                                   **/
  45 /**********************************************************************/
  46
  47 /**********************************************************************/
  48 /* Node attributes needed for the construction.                      **/
  49 /**********************************************************************/
  50
  51 typedef struct scc_info {
  52   bool in_stack;         /* Marks whether node is on the stack. */
  53   int dfn;               /* Depth first search number. */
  54   int uplink;            /* dfn number of ancestor. */
  55 } scc_info;
  56
  57 static INLINE scc_info* new_scc_info(void) {
  58   scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
  59   memset (info, 0, sizeof (scc_info));
  60   return info;
  61 }
  62
  63 static INLINE void
  64 mark_irn_in_stack (ir_node *n) {
  65   assert(get_irn_link(n));
  66   ((scc_info *)n->link)->in_stack = true;
  67 }
  68
  69 static INLINE void
  70 mark_irn_not_in_stack (ir_node *n) {
  71   assert(get_irn_link(n));
  72   ((scc_info *)n->link)->in_stack = false;
  73 }
  74
  75 static INLINE bool
  76 irn_is_in_stack (ir_node *n) {
  77   assert(get_irn_link(n));
  78   return ((scc_info *)n->link)->in_stack;
  79 }
  80
  81 static INLINE void
  82 set_irn_uplink (ir_node *n, int uplink) {
  83   assert(get_irn_link(n));
  84   ((scc_info *)n->link)->uplink = uplink;
  85 }
  86
  87 static INLINE int
  88 get_irn_uplink (ir_node *n) {
  89   assert(get_irn_link(n));
  90   return ((scc_info *)n->link)->uplink;
  91 }
  92
  93 static INLINE void
  94 set_irn_dfn (ir_node *n, int dfn) {
  95   assert(get_irn_link(n));
  96   ((scc_info *)n->link)->dfn = dfn;
  97 }
  98
  99 static INLINE int
 100 get_irn_dfn (ir_node *n) {
 101   assert(get_irn_link(n));
 102   return ((scc_info *)n->link)->dfn;
 103 }
 104
 105 /**********************************************************************/
 106 /* A stack.                                                          **/
 107 /**********************************************************************/
 108
 109 static ir_node **stack = NULL;
 110 static int tos = 0;                /* top of stack */
 111
 112 static INLINE void init_stack(void) {
 113   if (stack) {
 114     ARR_RESIZE (ir_node *, stack, 1000);
 115   } else {
 116     stack = NEW_ARR_F (ir_node *, 1000);
 117   }
 118   tos = 0;
 119 }
 120
 121
 122 static INLINE void
 123 push (ir_node *n)
 124 {
 125   if (tos == ARR_LEN (stack)) {
 126     int nlen = ARR_LEN (stack) * 2;
 127     ARR_RESIZE (ir_node *, stack, nlen);
 128   }
 129   stack [tos++] = n;
 130   mark_irn_in_stack(n);
 131 }
 132
 133 static INLINE ir_node *
 134 pop (void)
 135 {
 136   ir_node *n = stack[--tos];
 137   mark_irn_not_in_stack(n);
 138   return n;
 139 }
 140
 141 /* The nodes up to n belong to the current loop.
 142    Removes them from the stack and adds them to the current loop. */
 143 static INLINE void
 144 pop_scc_to_loop (ir_node *n)
 145 {
 146   ir_node *m;
 147
 148   /*for (;;) {*/
 149   do {
 150     m = pop();
 151     loop_node_cnt++;
 152     set_irn_dfn(m, loop_node_cnt);
 153     add_loop_node(current_loop, m);
 154     set_irn_loop(m, current_loop);
 155     /*    if (m==n) break;*/
 156   } while(m != n);
 157 }
 158
 159 /* GL ??? my last son is my grandson???  Removes cfloops with no
 160    ir_nodes in them.  Such loops have only another loop as son. (Why
 161    can't they have two loops as sons? Does it never get that far? ) */
 162 static void close_loop (ir_loop *l)
 163 {
 164   int last = get_loop_n_elements(l) - 1;
 165   loop_element lelement = get_loop_element(l, last);
 166   ir_loop *last_son = lelement.son;
 167
 168   if (get_kind(last_son) == k_ir_loop &&
 169       get_loop_n_elements(last_son) == 1) {
 170     ir_loop *gson;
 171
 172     lelement = get_loop_element(last_son, 0);
 173     gson = lelement.son;
 174     if(get_kind(gson) == k_ir_loop) {
 175       loop_element new_last_son;
 176
 177       gson -> outer_loop = l;
 178       new_last_son.son = gson;
 179       l -> children[last] = new_last_son;
 180     }
 181   }
 182
 183   current_loop = l;
 184 }
 185
 186 /* Removes and unmarks all nodes up to n from the stack.
 187    The nodes must be visited once more to assign them to a scc. */
 188 static INLINE void
 189 pop_scc_unmark_visit (ir_node *n)
 190 {
 191   ir_node *m = NULL;
 192
 193   while (m != n) {
 194     m = pop();
 195     set_irn_visited(m, 0);
 196   }
 197 }
 198
 199 /**********************************************************************/
 200 /* The loop datastructure.                                           **/
 201 /**********************************************************************/
 202
 203 /* Allocates a new loop as son of current_loop.  Sets current_loop
 204    to the new loop and returns the father. */
 205 static ir_loop *new_loop (void) {
 206   ir_loop *father, *son;
 207
 208   father = current_loop;
 209
 210   son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
 211   memset (son, 0, sizeof (ir_loop));
 212   son->kind = k_ir_loop;
 213   son->children = NEW_ARR_F (loop_element, 0);
 214   son->n_nodes = 0;
 215   son->n_sons=0;
 216   if (father) {
 217     son->outer_loop = father;
 218     add_loop_son(father, son);
 219     son->depth = father->depth+1;
 220   } else {  /* The root loop */
 221     son->outer_loop = son;
 222     son->depth = 0;
 223   }
 224
 225 #ifdef DEBUG_libfirm
 226   son->loop_nr = get_irp_new_node_nr();
 227   son->link = NULL;
 228 #endif
 229
 230   current_loop = son;
 231   return father;
 232 }
 233
 234 /**********************************************************************/
 235 /* Constructing and destructing the loop/backedge information.       **/
 236 /**********************************************************************/
 237
 238 /* Initialization steps. **********************************************/
 239
 240 static INLINE void
 241 init_node (ir_node *n, void *env) {
 242   if (is_Block(n))
 243     set_irn_link (n, new_scc_info());
 244   clear_backedges(n);
 245 }
 246
 247 static INLINE void
 248 init_scc_common (void) {
 249   current_dfn = 1;
 250   loop_node_cnt = 0;
 251   init_stack();
 252 }
 253
 254 static INLINE void
 255 init_scc (ir_graph *irg) {
 256   init_scc_common();
 257   irg_walk_graph (irg, init_node, NULL, NULL);
 258 }
 259
 260 static INLINE void
 261 init_ip_scc (void) {
 262   init_scc_common();
 263   cg_walk (init_node, NULL, NULL);
 264
 265 #if EXPERIMENTAL_CFLOOP_TREE
 266   cg_walk (link_to_reg_end, NULL, NULL);
 267 #endif
 268 }
 269
 270 /* Condition for breaking the recursion. */
 271 static bool is_outermost_StartBlock(ir_node *n) {
 272   /* Test whether this is the outermost Start node.  If so
 273      recursion must end. */
 274   assert(is_Block(n));
 275   if ((get_Block_n_cfgpreds(n) == 1)  &&
 276       (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
 277       (get_nodes_Block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
 278     return true;
 279   }
 280   return false;
 281 }
 282
 283 /** Returns true if n is a loop header, i.e., it is a Block node
 284  *  and has predecessors within the cfloop and out of the cfloop.
 285  *
 286  *  @param root: only needed for assertion.
 287  */
 288 static bool
 289 is_head (ir_node *n, ir_node *root)
 290 {
 291   int i, arity;
 292   int some_outof_loop = 0, some_in_loop = 0;
 293
 294   assert(is_Block(n));
 295
 296   if (!is_outermost_StartBlock(n)) {
 297     arity = get_irn_arity(n);
 298     for (i = 0; i < arity; i++) {
 299       ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
 300       if (is_backedge(n, i)) continue;
 301       if (!irn_is_in_stack(pred)) {
 302         some_outof_loop = 1;
 303       } else {
 304         if (get_irn_uplink(pred) < get_irn_uplink(root))  {
 305           DDMN(pred); DDMN(root);
 306           assert(get_irn_uplink(pred) >= get_irn_uplink(root));
 307         }
 308         some_in_loop = 1;
 309       }
 310     }
 311   }
 312   return some_outof_loop && some_in_loop;
 313 }
 314
 315 /* Returns index of the predecessor with the smallest dfn number
 316    greater-equal than limit. */
 317 static int
 318 smallest_dfn_pred (ir_node *n, int limit)
 319 {
 320   int i, index = -2, min = -1;
 321
 322   if (!is_outermost_StartBlock(n)) {
 323     int arity = get_irn_arity(n);
 324     for (i = 0; i < arity; i++) {
 325       ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
 326       if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
 327       if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
 328         index = i;
 329         min = get_irn_dfn(pred);
 330       }
 331     }
 332   }
 333   return index;
 334 }
 335
 336 /* Returns index of the predecessor with the largest dfn number. */
 337 static int
 338 largest_dfn_pred (ir_node *n)
 339 {
 340   int i, index = -2, max = -1;
 341
 342   if (!is_outermost_StartBlock(n)) {
 343     int arity = get_irn_arity(n);
 344     for (i = 0; i < arity; i++) {
 345       ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
 346       if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
 347       if (get_irn_dfn(pred) > max) {
 348         index = i;
 349         max = get_irn_dfn(pred);
 350       }
 351     }
 352   }
 353   return index;
 354 }
 355
 356 /* Searches the stack for possible loop heads.  Tests these for backedges.
 357    If it finds a head with an unmarked backedge it marks this edge and
 358    returns the tail of the loop.
 359    If it finds no backedge returns NULL.
 360    ("disable_backedge" in fiasco) */
 361 static ir_node *
 362 find_tail (ir_node *n) {
 363   ir_node *m;
 364   int i, res_index = -2;
 365
 366   m = stack[tos-1];  /* tos = top of stack */
 367   if (is_head (m, n)) {
 368     res_index = smallest_dfn_pred(m, 0);
 369     if ((res_index == -2) &&  /* no smallest dfn pred found. */
 370         (n ==  m))
 371       return NULL;
 372   } else {
 373     if (m == n) return NULL;
 374     for (i = tos-2; ; --i) {
 375       m = stack[i];
 376       if (is_head (m, n)) {
 377         res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
 378         if (res_index == -2)  /* no smallest dfn pred found. */
 379           res_index = largest_dfn_pred (m);
 380         break;
 381       }
 382     }
 383   }
 384   assert (res_index > -2);
 385
 386   set_backedge (m, res_index);
 387   return is_outermost_StartBlock(n) ? NULL : get_nodes_block(skip_Proj(get_irn_n(m, res_index)));
 388 }
 389
 390 /*-----------------------------------------------------------*
 391  *                   The core algorithm.                     *
 392  *-----------------------------------------------------------*/
 393
 394
 395 static void cfscc (ir_node *n) {
 396   int i;
 397
 398   assert(is_Block(n));
 399
 400   if (irn_visited(n)) return;
 401   mark_irn_visited(n);
 402
 403   /* Initialize the node */
 404   set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
 405   set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
 406   set_irn_loop(n, NULL);
 407   current_dfn ++;
 408   push(n);
 409
 410   /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
 411      array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
 412      so is_backedge does not access array[-1] but correctly returns false! */
 413
 414   if (!is_outermost_StartBlock(n)) {
 415     int arity = get_irn_arity(n);
 416
 417     for (i = 0; i < arity; i++) {
 418       ir_node *m;
 419       if (is_backedge(n, i)) continue;
 420       m = get_nodes_block(skip_Proj(get_irn_n(n, i)));
 421
 422       cfscc (m);
 423       if (irn_is_in_stack(m)) {
 424         /* Uplink of m is smaller if n->m is a backedge.
 425            Propagate the uplink to mark the cfloop. */
 426         if (get_irn_uplink(m) < get_irn_uplink(n))
 427           set_irn_uplink(n, get_irn_uplink(m));
 428       }
 429     }
 430   }
 431
 432   if (get_irn_dfn(n) == get_irn_uplink(n)) {
 433     /* This condition holds for
 434        1) the node with the incoming backedge.
 435           That is: We found a cfloop!
 436        2) Straight line code, because no uplink has been propagated, so the
 437           uplink still is the same as the dfn.
 438
 439        But n might not be a proper cfloop head for the analysis. Proper cfloop
 440        heads are Block and Phi nodes. find_tail searches the stack for
 441        Block's and Phi's and takes those nodes as cfloop heads for the current
 442        cfloop instead and marks the incoming edge as backedge. */
 443
 444     ir_node *tail = find_tail(n);
 445     if (tail) {
 446       /* We have a cfloop, that is no straight line code,
 447          because we found a cfloop head!
 448          Next actions: Open a new cfloop on the cfloop tree and
 449                        try to find inner cfloops */
 450
 451
 452 #define NO_CFLOOPS_WITHOUT_HEAD 1
 453 #if NO_CFLOOPS_WITHOUT_HEAD
 454
 455       /* This is an adaption of the algorithm from fiasco / optscc to
 456        * avoid cfloops without Block or Phi as first node.  This should
 457        * severely reduce the number of evaluations of nodes to detect
 458        * a fixpoint in the heap analysis.
 459        * Further it avoids cfloops without firm nodes that cause errors
 460        * in the heap analyses. */
 461
 462       ir_loop *l;
 463       int close;
 464       if (get_loop_n_elements(current_loop) > 0) {
 465         l = new_loop();
 466         close = 1;
 467       } else {
 468         l = current_loop;
 469         close = 0;
 470       }
 471
 472 #else
 473
 474       ir_loop *l = new_loop();
 475
 476 #endif
 477
 478       /* Remove the cfloop from the stack ... */
 479       pop_scc_unmark_visit (n);
 480
 481       /* The current backedge has been marked, that is temporarily eliminated,
 482          by find tail. Start the scc algorithm
 483          anew on the subgraph thats left (the current cfloop without the backedge)
 484          in order to find more inner cfloops. */
 485
 486       cfscc (tail);
 487
 488       assert (irn_visited(n));
 489 #if NO_CFLOOPS_WITHOUT_HEAD
 490       if (close)
 491 #endif
 492         close_loop(l);
 493     }
 494     else
 495       {
 496         /* AS: No cfloop head was found, that is we have straightline code.
 497                Pop all nodes from the stack to the current cfloop. */
 498       pop_scc_to_loop(n);
 499     }
 500   }
 501 }
 502
 503 /* Constructs backedge information for irg. */
 504 void construct_cf_backedges(ir_graph *irg) {
 505   ir_graph *rem = current_ir_graph;
 506   ir_loop *head_rem;
 507   ir_node *end = get_irg_end(irg);
 508   int i;
 509
 510   assert(!interprocedural_view &&
 511      "use construct_ip_backedges");
 512
 513   current_ir_graph = irg;
 514   outermost_ir_graph = irg;
 515
 516   init_scc(current_ir_graph);
 517
 518   current_loop = NULL;
 519   new_loop();  /* sets current_loop */
 520   head_rem = current_loop; /* Just for assertion */
 521
 522   inc_irg_visited(current_ir_graph);
 523
 524   cfscc(get_irg_end_block(current_ir_graph));
 525   for (i = 0; i < get_End_n_keepalives(end); i++) {
 526     ir_node *el = get_End_keepalive(end, i);
 527     if (is_Block(el)) cfscc(el);
 528   }
 529
 530   assert(head_rem == current_loop);
 531   set_irg_loop(current_ir_graph, current_loop);
 532   set_irg_loopinfo_state(current_ir_graph, loopinfo_cf_consistent);
 533   assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
 534
 535   current_ir_graph = rem;
 536 }
 537
 538
 539 void construct_ip_cf_backedges (void) {
 540   ir_graph *rem = current_ir_graph;
 541   int rem_ipv = interprocedural_view;
 542   int i;
 543
 544   assert(get_irp_ip_view_state() == ip_view_valid);
 545
 546   outermost_ir_graph = get_irp_main_irg();
 547
 548   init_ip_scc();
 549
 550   current_loop = NULL;
 551   new_loop();  /* sets current_loop */
 552   interprocedural_view = 1;
 553
 554   inc_max_irg_visited();
 555   for (i = 0; i < get_irp_n_irgs(); i++)
 556     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
 557
 558   /** We have to start the walk at the same nodes as cg_walk. **/
 559   /* Walk starting at unreachable procedures. Only these
 560    * have End blocks visible in interprocedural view. */
 561   for (i = 0; i < get_irp_n_irgs(); i++) {
 562     ir_node *sb;
 563     current_ir_graph = get_irp_irg(i);
 564
 565     sb = get_irg_start_block(current_ir_graph);
 566
 567     if ((get_Block_n_cfgpreds(sb) > 1) ||
 568         (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
 569
 570     cfscc(get_irg_end_block(current_ir_graph));
 571   }
 572
 573   /* Check whether we walked all procedures: there could be procedures
 574      with cyclic calls but no call from the outside. */
 575   for (i = 0; i < get_irp_n_irgs(); i++) {
 576     ir_node *sb;
 577     current_ir_graph = get_irp_irg(i);
 578
 579     /* Test start block: if inner procedure end and end block are not
 580      * visible and therefore not marked. */
 581     sb = get_irg_start_block(current_ir_graph);
 582     if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) cfscc(sb);
 583   }
 584
 585   /* Walk all endless cfloops in inner procedures.
 586    * We recognize an inner procedure if the End node is not visited. */
 587   for (i = 0; i < get_irp_n_irgs(); i++) {
 588     ir_node *e;
 589     current_ir_graph = get_irp_irg(i);
 590
 591     e = get_irg_end(current_ir_graph);
 592     if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
 593       int j;
 594       /* Don't visit the End node. */
 595       for (j = 0; j < get_End_n_keepalives(e); j++) {
 596         ir_node *el = get_End_keepalive(e, j);
 597         if (is_Block(el)) cfscc(el);
 598       }
 599     }
 600   }
 601
 602   set_irg_loop(outermost_ir_graph, current_loop);
 603   set_irg_loopinfo_state(current_ir_graph, loopinfo_cf_ip_consistent);
 604   assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
 605
 606   current_ir_graph = rem;
 607   interprocedural_view = rem_ipv;
 608 }
 609
 610
 611 static void reset_backedges(ir_node *n) {
 612   assert(is_Block(n));
 613   int rem = interprocedural_view;
 614   interprocedural_view = 1;
 615   clear_backedges(n);
 616   interprocedural_view = 0;
 617   clear_backedges(n);
 618   interprocedural_view = rem;
 619 }
 620
 621 static void loop_reset_backedges(ir_loop *l) {
 622   int i;
 623   reset_backedges(get_loop_node(l, 0));
 624   for (i = 0; i < get_loop_n_nodes(l); ++i)
 625     set_irn_loop(get_loop_node(l, i), NULL);
 626   for (i = 0; i < get_loop_n_sons(l); ++i) {
 627     loop_reset_backedges(get_loop_son(l, i));
 628   }
 629 }
 630
 631 /* Removes all cfloop information.
 632    Resets all backedges */
 633 void free_cfloop_information(ir_graph *irg) {
 634   if (get_irg_loop(irg))
 635     loop_reset_backedges(get_irg_loop(irg));
 636   set_irg_loop(irg, NULL);
 637   set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
 638   /* We cannot free the cfloop nodes, they are on the obstack. */
 639 }
 640
 641
 642 void free_all_cfloop_information (void) {
 643   int i;
 644   int rem = interprocedural_view;
 645   interprocedural_view = 1;  /* To visit all filter nodes */
 646   for (i = 0; i < get_irp_n_irgs(); i++) {
 647     free_cfloop_information(get_irp_irg(i));
 648   }
 649   interprocedural_view = rem;
 650 }