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

   1 /* Copyright (C) 2002 by Universitaet Karlsruhe
   2 ** All rights reserved.
   3 **
   4 ** Authors:  Goetz Lindenmaier
   5 **
   6 ** irscc.c  Computing the strongly connected regions and building
   7 ** backedge/loop datastructures.
   8 **
   9 */
  10
  11 /* $Id$ */
  12
  13 #include "irloop_t.h"
  14 #include "irnode.h"
  15 #include "irgraph_t.h"
  16 #include "array.h"
  17
  18 ir_graph *outermost_ir_graph;      /* The outermost graph the scc is computed
  19                                       for */
  20 static ir_loop *current_loop;      /* Current loop construction is working
  21                                       on. */
  22 static int loop_node_cnt = 0;      /* Counts the number of allocated loop nodes.
  23                                       Each loop node gets a unique number.
  24                                       What for? ev. remove. @@@ */
  25 static int current_dfn = 1;        /* Counter to generate depth first numbering
  26                                       of visited nodes.  */
  27
  28 /**********************************************************************/
  29 /* Node attributes needed for the construction.                      **/
  30 /**********************************************************************/
  31
  32 typedef struct scc_info {
  33   bool in_stack;         /* Marks whether node is on the stack. */
  34   int dfn;               /* Depth first search number. */
  35   int uplink;            /* dfn number of ancestor. */
  36   ir_loop *loop;         /* Refers to the containing loop. */
  37   /*
  38       struct section *section;
  39       xset def;
  40       xset use;
  41   */
  42 } scc_info;
  43
  44 static INLINE scc_info* new_scc_info() {
  45   scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
  46   memset (info, 0, sizeof (scc_info));
  47   return info;
  48 }
  49
  50 static INLINE void
  51 mark_irn_in_stack (ir_node *n) {
  52   assert(get_irn_link(n));
  53   ((scc_info *)get_irn_link(n))->in_stack = true;
  54 }
  55
  56 static INLINE void
  57 mark_irn_not_in_stack (ir_node *n) {
  58   assert(get_irn_link(n));
  59   ((scc_info *)get_irn_link(n))->in_stack = false;
  60 }
  61
  62 static INLINE bool
  63 irn_is_in_stack (ir_node *n) {
  64   assert(get_irn_link(n));
  65   return ((scc_info *)get_irn_link(n))->in_stack;
  66 }
  67
  68 static INLINE void
  69 set_irn_uplink (ir_node *n, int uplink) {
  70   assert(get_irn_link(n));
  71   ((scc_info *)get_irn_link(n))->uplink = uplink;
  72 }
  73
  74 static INLINE int
  75 get_irn_uplink (ir_node *n) {
  76   assert(get_irn_link(n));
  77   return ((scc_info *)get_irn_link(n))->uplink;
  78 }
  79
  80 static INLINE void
  81 set_irn_dfn (ir_node *n, int dfn) {
  82   if (! get_irn_link(n)) { DDMN(n); DDME(get_irg_ent(current_ir_graph));}
  83   assert(get_irn_link(n));
  84   ((scc_info *)get_irn_link(n))->dfn = dfn;
  85 }
  86
  87 static INLINE int
  88 get_irn_dfn (ir_node *n) {
  89   assert(get_irn_link(n));
  90   return ((scc_info *)get_irn_link(n))->dfn;
  91 }
  92
  93 /* Uses temporary information to set the loop */
  94 static INLINE void
  95 set_irn_loop_tmp (ir_node *n, ir_loop* loop) {
  96   assert(get_irn_link(n));
  97   ((scc_info *)get_irn_link(n))->loop = loop;
  98 }
  99
 100 /* Uses temporary information to get the loop */
 101 static INLINE ir_loop *
 102 get_irn_loop_tmp (ir_node *n) {
 103   assert(get_irn_link(n));
 104   return ((scc_info *)get_irn_link(n))->loop;
 105 }
 106
 107 ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
 108   int i;
 109   ir_loop *res = NULL;
 110
 111   /* Test whether n is contained in this loop. */
 112   for (i = 0; i < get_loop_n_nodes(l); i++)
 113     if (n == get_loop_node(l, i)) return l;
 114
 115   /* Is this a leave in the loop tree? If so loop not found. */
 116   if (get_loop_n_sons(l) == 0) return NULL;
 117
 118   /* Else descend in the loop tree. */
 119   for (i = 0; i < get_loop_n_sons(l); i++) {
 120     res = find_nodes_loop(n, get_loop_son(l, i));
 121     if (res) break;
 122   }
 123   return res;
 124 }
 125
 126 /* @@@ temporary implementation, costly!!! */
 127 ir_loop * get_irn_loop(ir_node *n) {
 128   ir_loop *l = get_irg_loop(current_ir_graph);
 129   l = find_nodes_loop(n, l);
 130   return l;
 131 }
 132
 133 /**********************************************************************/
 134 /* A stack.                                                          **/
 135 /**********************************************************************/
 136
 137 static ir_node **stack = NULL;
 138 static int tos = 0;                /* top of stack */
 139
 140 static INLINE void init_stack() {
 141   if (stack) {
 142     ARR_RESIZE (ir_node *, stack, 1000);
 143   } else {
 144     stack = NEW_ARR_F (ir_node *, 1000);
 145   }
 146   tos = 0;
 147 }
 148
 149 static INLINE void free_stack() {
 150   DEL_ARR_F(stack);
 151   stack = NULL;
 152   tos = 0;
 153 }
 154
 155 static INLINE void
 156 push (ir_node *n)
 157 {
 158   //DDMN(n);
 159
 160   if (tos == ARR_LEN (stack)) {
 161     int nlen = ARR_LEN (stack) * 2;
 162     ARR_RESIZE (ir_node *, stack, nlen);
 163   }
 164   stack [tos++] = n;
 165   mark_irn_in_stack(n);
 166 }
 167
 168 static INLINE ir_node *
 169 pop (void)
 170 {
 171   ir_node *n = stack[--tos];
 172   mark_irn_not_in_stack(n);
 173   return n;
 174 }
 175
 176 /* The nodes up to n belong to the current loop.
 177    Removes them from the stack and adds them to the current loop. */
 178 static INLINE void
 179 pop_scc_to_loop (ir_node *n)
 180 {
 181   ir_node *m;
 182
 183   for (;;) {
 184     m = pop();
 185     set_irn_dfn(m, loop_node_cnt);
 186     loop_node_cnt++;
 187     add_loop_node(current_loop, m);
 188     set_irn_loop_tmp(m, current_loop);
 189     if (m==n) break;
 190   }
 191 }
 192
 193 /* Removes and unmarks all nodes up to n from the stack.
 194    The nodes must be visited once more to assign them to a scc. */
 195 static INLINE void
 196 pop_scc_unmark_visit (ir_node *n)
 197 {
 198   ir_node *m = NULL;
 199
 200   while (m != n) {
 201     m = pop();
 202     set_irn_visited(m, 0);
 203   }
 204 }
 205
 206 /**********************************************************************/
 207 /* The loop datastructure.                                           **/
 208 /**********************************************************************/
 209
 210 /* Allocates a new loop as son of current_loop.  Sets current_loop
 211    to the new loop and returns the father. */
 212 ir_loop *new_loop (void) {
 213   ir_loop *father, *son;
 214
 215   father = current_loop;
 216
 217   son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
 218   memset (son, 0, sizeof (ir_loop));
 219   son->kind = k_ir_loop;
 220   son->sons = NEW_ARR_F (ir_loop *, 0);
 221   son->nodes = NEW_ARR_F (ir_node *, 0);
 222   if (father) {
 223     son->outer_loop = father;
 224     add_loop_son(father, son);
 225     son->depth = father->depth+1;
 226   } else {  /* The root loop */
 227     son->outer_loop = son;
 228     son->depth = 0;
 229   }
 230
 231   current_loop = son;
 232   return father;
 233 }
 234
 235 /* Finishes the datastructures, copies the arrays to the obstack
 236    of current_ir_graph. */
 237 void mature_loop (ir_loop *loop) {
 238   ir_loop **new_sons;
 239   ir_node **new_nods;
 240
 241   new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
 242   memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
 243   DEL_ARR_F(loop->sons);
 244   loop->sons = new_sons;
 245 }
 246
 247 /* Returns outer loop, itself if outermost. */
 248 ir_loop *get_loop_outer_loop (ir_loop *loop) {
 249   assert(loop && loop->kind == k_ir_loop);
 250   return loop->outer_loop;
 251 }
 252
 253 /* Returns nesting depth of this loop */
 254 int get_loop_depth (ir_loop *loop) {
 255   assert(loop); assert(loop->kind == k_ir_loop);
 256   return loop->depth;
 257 }
 258
 259 /* @@@ sons are the inner loops _and_ all nodes within them. */
 260 /* Returns the number of inner loops */
 261 int      get_loop_n_sons (ir_loop *loop) {
 262   assert(loop && loop->kind == k_ir_loop);
 263   return ARR_LEN(loop->sons);
 264 }
 265 ir_loop *get_loop_son (ir_loop *loop, int pos) {
 266   assert(loop && loop->kind == k_ir_loop);
 267   return loop->sons[pos];
 268 }
 269 static INLINE void
 270 add_loop_son(ir_loop *loop, ir_loop *son) {
 271   assert(loop && loop->kind == k_ir_loop);
 272   ARR_APP1 (ir_loop *, loop->sons, son);
 273 }
 274
 275 /* Returns the number of nodes in the loop */
 276 int      get_loop_n_nodes (ir_loop *loop) {
 277   assert(loop); assert(loop->kind == k_ir_loop);
 278   return ARR_LEN(loop->nodes);
 279 }
 280 ir_node *get_loop_node (ir_loop *loop, int pos) {
 281   assert(loop && loop->kind == k_ir_loop);
 282   return loop->nodes[pos];
 283 }
 284 static INLINE void
 285 add_loop_node(ir_loop *loop, ir_node *n) {
 286   assert(loop && loop->kind == k_ir_loop);
 287   ARR_APP1 (ir_node *, loop->nodes, n);
 288 }
 289
 290 /* The outermost loop is remarked in the surrounding graph. */
 291 void     set_irg_loop(ir_graph *irg, ir_loop *loop) {
 292   assert(irg);
 293   irg->loop = loop;
 294 }
 295 ir_loop *get_irg_loop(ir_graph *irg) {
 296   assert(irg);
 297   return irg->loop;
 298 }
 299
 300 /**********************************************************************/
 301 /* Constructing and destructing the loop/backedge information.       **/
 302 /**********************************************************************/
 303
 304 /* Initialization steps. **********************************************/
 305
 306 static INLINE void
 307 init_node (ir_node *n, void *env) {
 308   set_irn_link (n, new_scc_info());
 309   clear_backedges(n);
 310 }
 311
 312 static INLINE void
 313 init_scc (ir_graph *irg) {
 314   current_dfn = 1;
 315   loop_node_cnt = 0;
 316   init_stack();
 317   irg_walk_graph (irg, init_node, NULL, NULL);
 318   /*
 319   irg_walk (irg, link_to_reg_end, NULL, NULL);
 320   */
 321 }
 322
 323 /* Condition for breaking the recursion. */
 324 bool is_outermost_Start(ir_node *n) {
 325   /* Test whether this is the outermost Start node.  If so
 326      recursion must end. */
 327   if ((get_irn_op(n) == op_Block) &&
 328       (n == get_irg_start_block(current_ir_graph))) {
 329     if ((!interprocedural_view)  ||
 330         (current_ir_graph == outermost_ir_graph))
 331       return true;
 332   }
 333   return false;
 334 }
 335
 336 /* Don't walk from nodes to blocks except for Control flow operations. */
 337 static INLINE int
 338 get_start_index(ir_node *n) {
 339   if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
 340     return -1;
 341   else
 342     return 0;
 343 }
 344
 345 /* Returns current_ir_graph and set it to the irg of predecessor index
 346    of node n. */
 347 static INLINE ir_graph *
 348 switch_irg (ir_node *n, int index) {
 349   ir_graph *old_current = current_ir_graph;
 350
 351   if (interprocedural_view) {
 352     /* Only Filter and Block nodes can have predecessors in other graphs. */
 353     if (get_irn_op(n) == op_Filter)
 354       n = get_nodes_Block(n);
 355     if (get_irn_op(n) == op_Block) {
 356       ir_node *cfop = skip_Proj(get_Block_cfgpred(n, index));
 357       if (is_ip_cfop(cfop)) {
 358         current_ir_graph = get_irn_irg(cfop);
 359         set_irg_visited(current_ir_graph, get_max_irg_visited());
 360       }
 361     }
 362   }
 363
 364   return old_current;
 365 }
 366
 367 /* Walks up the stack passing n and then finding the node
 368    where we walked into the irg n is contained in.
 369    Here we switch the irg. */
 370 static ir_graph *
 371 find_irg_on_stack (ir_node *n) {
 372   ir_node *m;
 373   ir_graph *old_current = current_ir_graph;
 374   int i;
 375
 376   if (interprocedural_view) {
 377     for (i = tos; i >= 0; i--) {
 378       if (stack[i] == n) break;
 379     }
 380     if (i < 0) i = tos;
 381
 382     //printf(" Here\n");
 383
 384     assert (i >= 0);
 385     for (; i >= 0; i--) {
 386       m = stack[i];
 387       //printf(" Visiting %d ", i); DDMN(m);
 388       if (is_ip_cfop(m)) {
 389         current_ir_graph = get_irn_irg(m);
 390         break;
 391       }
 392       if (get_irn_op(m) == op_Filter) {
 393         /* Find the corresponding ip_cfop */
 394         ir_node *pred = stack[i+1];
 395         int j;
 396         for (j = 0; j < get_Filter_n_cg_preds(m); j++)
 397           if (get_Filter_cg_pred(m, j) == pred) break;
 398         if (j >= get_Filter_n_cg_preds(m))
 399           /* It is a filter we didn't pass as the predecessors are marked. */
 400           continue;
 401         assert(get_Filter_cg_pred(m, j) == pred);
 402         switch_irg(m, j);
 403         break;
 404       }
 405     }
 406   }
 407
 408   return old_current;
 409 }
 410
 411 /* Returns true if n is a loop header, i.e., it is a Block, Phi
 412    or Filter node and has predecessors within the loop and out
 413    of the loop. */
 414 static bool
 415 is_head (ir_node *n, ir_node *root)
 416 {
 417   int i;
 418   int some_outof_loop = 0,  some_in_loop = 0;
 419
 420   /* Test for legal loop header */
 421   if (!((get_irn_op(n) == op_Block) ||
 422         (get_irn_op(n) == op_Phi) ||
 423         ((get_irn_op(n) == op_Filter) && interprocedural_view)))
 424     return false;
 425
 426   if (!is_outermost_Start(n)) {
 427     for (i = get_start_index(n); i < get_irn_arity(n); i++) {
 428       ir_node *pred = get_irn_n(n, i);
 429       assert(pred);
 430       if (is_backedge(n, i)) continue;
 431       if (!irn_is_in_stack(pred)) {
 432         some_outof_loop = 1;
 433       } else {
 434         assert(get_irn_uplink(pred) >= get_irn_uplink(root));
 435         some_in_loop = 1;
 436       }
 437     }
 438   }
 439   return some_outof_loop && some_in_loop;
 440 }
 441
 442 /* Returns index of the predecessor with the smallest dfn number
 443    greater-equal than limit. */
 444 static int
 445 smallest_dfn_pred (ir_node *n, int limit)
 446 {
 447   int i, index = -2, min = -1;
 448
 449   if (!is_outermost_Start(n)) {
 450     for (i = get_start_index(n); i < get_irn_arity(n); i++) {
 451       ir_node *pred = get_irn_n(n, i);
 452       assert(pred);
 453       if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
 454       if (get_irn_dfn(pred) >= limit
 455         && (min == -1 || get_irn_dfn(pred) < min)) {
 456         index = i;
 457         min = get_irn_dfn(pred);
 458       }
 459     }
 460   }
 461   return index;
 462 }
 463
 464 /* Returns index of the predecessor with the largest dfn number. */
 465 static int
 466 largest_dfn_pred (ir_node *n)
 467 {
 468   int i, index = -2, max = -1;
 469
 470   if (!is_outermost_Start(n)) {
 471     for (i = get_start_index(n); i < get_irn_arity(n); i++) {
 472       ir_node *pred = get_irn_n(n, i);
 473       if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
 474       if (get_irn_dfn(pred) > max) {
 475         index = i;
 476         max = get_irn_dfn(pred);
 477       }
 478     }
 479   }
 480   return index;
 481 }
 482
 483 /* Searches the stack for possible loop heads.  Tests these for backedges.
 484    If it finds a head with an unmarked backedge it marks this edge and
 485    returns the tail of the loop.
 486    If it finds no backedge returns NULL. */
 487 static ir_node *
 488 find_tail (ir_node *n) {
 489   ir_node *m;
 490   int i, res_index = -2;
 491
 492   /*
 493     if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
 494   */
 495
 496   m = stack[tos-1];
 497   if (is_head (m, n)) {
 498     res_index = smallest_dfn_pred(m, 0);
 499     if ((res_index == -2) &&  /* no smallest dfn pred found. */
 500         (n == m))
 501       return NULL;
 502   } else {
 503     if (m == n) return NULL;
 504     for (i = tos-2; ; --i) {
 505       m = stack[i];
 506       if (is_head (m, n)) {
 507         res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
 508         if (res_index == -2)  /* no smallest dfn pred found. */
 509           res_index = largest_dfn_pred (m);
 510         break;
 511       }
 512     }
 513   }
 514   assert (res_index > -2);
 515
 516   set_backedge (m, res_index);
 517   return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
 518 }
 519
 520
 521 /* The core algorithm. *****************************************/
 522
 523 void scc (ir_node *n) {
 524   int i;
 525   ir_graph *rem;
 526
 527   if (irn_visited(n)) return;
 528   mark_irn_visited(n);
 529
 530   /* Initialize the node */
 531   set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
 532   set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
 533   set_irn_loop_tmp(n, NULL);
 534   current_dfn ++;
 535
 536   /* What's this good for?
 537   n->ana.scc.section = NULL;
 538   */
 539
 540   push(n);
 541
 542   if (!is_outermost_Start(n)) {
 543     for (i = get_start_index(n); i < get_irn_arity(n); i++) {
 544       ir_node *m;
 545       if (is_backedge(n, i)) continue;
 546
 547       m = get_irn_ip_pred(n, i);
 548       if (!m) continue;
 549       scc (m);
 550       return_recur(n, i);
 551
 552       if (irn_is_in_stack(m)) {
 553         /* Uplink of m is smaller if n->m is a backedge.
 554            Propagate the uplink to mark the loop. */
 555         if (get_irn_uplink(m) < get_irn_uplink(n))
 556           set_irn_uplink(n, get_irn_uplink(m));
 557       }
 558     }
 559   }
 560   if (get_irn_dfn(n) == get_irn_uplink(n)) {
 561     /* This condition holds for the node with the incoming backedge. */
 562     ir_node *tail = find_tail(n);
 563     if (tail) {
 564       /* We found a new loop! */
 565       ir_loop *l = new_loop();
 566       /* Remove the loop from the stack ... */
 567       pop_scc_unmark_visit (n);
 568       /* and recompute it in a better order; and so that it goes into
 569          the new loop. */
 570       rem = find_irg_on_stack(tail);
 571       scc (tail);
 572       current_ir_graph = rem;
 573
 574       assert (irn_visited(n));
 575
 576       current_loop = l;
 577     } else {
 578       pop_scc_to_loop(n);
 579     }
 580   }
 581 }
 582
 583 /* Constructs backedge information for irg. In interprocedural view constructs
 584    backedges for all methods called by irg, too. */
 585 void construct_backedges(ir_graph *irg) {
 586   ir_graph *rem = current_ir_graph;
 587   ir_loop *head_rem;
 588   int i;
 589
 590   current_ir_graph = irg;
 591   outermost_ir_graph = irg;
 592
 593   init_scc(irg);
 594
 595   current_loop = NULL;
 596   new_loop();  /* sets current_loop */
 597   head_rem = current_loop; /* Just for assertion */
 598
 599   if (interprocedural_view) {
 600     set_irg_visited(irg, inc_max_irg_visited());
 601     init_ip_walk ();
 602   } else {
 603     inc_irg_visited(irg);
 604   }
 605
 606   scc(get_irg_end(irg));
 607   for (i = 0; i < get_End_n_keepalives(get_irg_end(irg)); i++)
 608     scc(get_End_keepalive(get_irg_end(irg), i));
 609
 610   if (interprocedural_view) finish_ip_walk();
 611
 612   assert(head_rem == current_loop);
 613   set_irg_loop(irg, current_loop);
 614   assert(get_irg_loop(irg)->kind == k_ir_loop);
 615   /*
 616   irg->loops = current_loop;
 617   if (icfg == 1) {
 618     int count = 0;
 619     int depth = 0;
 620     count_loop (the_loop, &count, &depth);
 621     }
 622   }
 623   */
 624   current_ir_graph = rem;
 625 }