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