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 <string.h>
  14
  15 #include "irloop_t.h"
  16 #include "irnode.h"
  17 #include "irgraph_t.h"
  18 #include "array.h"
  19 #include "irgwalk.h"
  20 #include "irprog.h"
  21
  22 ir_graph *outermost_ir_graph;      /* The outermost graph the scc is computed
  23                                       for */
  24 static ir_loop *current_loop;      /* Current loop construction is working
  25                                       on. */
  26 static int loop_node_cnt = 0;      /* Counts the number of allocated loop nodes.
  27                                       Each loop node gets a unique number.
  28                                       What for? ev. remove. @@@ */
  29 static int current_dfn = 1;        /* Counter to generate depth first numbering
  30                                       of visited nodes.  */
  31
  32 /**********************************************************************/
  33 /* Node attributes needed for the construction.                      **/
  34 /**********************************************************************/
  35
  36 typedef struct scc_info {
  37   bool in_stack;         /* Marks whether node is on the stack. */
  38   int dfn;               /* Depth first search number. */
  39   int uplink;            /* dfn number of ancestor. */
  40   ir_loop *loop;         /* Refers to the containing loop. */
  41   /*
  42       struct section *section;
  43       xset def;
  44       xset use;
  45   */
  46 } scc_info;
  47
  48 static INLINE scc_info* new_scc_info(void) {
  49   scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
  50   memset (info, 0, sizeof (scc_info));
  51   return info;
  52 }
  53
  54 static INLINE void
  55 mark_irn_in_stack (ir_node *n) {
  56   assert(get_irn_link(n));
  57   ((scc_info *)get_irn_link(n))->in_stack = true;
  58 }
  59
  60 static INLINE void
  61 mark_irn_not_in_stack (ir_node *n) {
  62   assert(get_irn_link(n));
  63   ((scc_info *)get_irn_link(n))->in_stack = false;
  64 }
  65
  66 static INLINE bool
  67 irn_is_in_stack (ir_node *n) {
  68   assert(get_irn_link(n));
  69   return ((scc_info *)get_irn_link(n))->in_stack;
  70 }
  71
  72 static INLINE void
  73 set_irn_uplink (ir_node *n, int uplink) {
  74   assert(get_irn_link(n));
  75   ((scc_info *)get_irn_link(n))->uplink = uplink;
  76 }
  77
  78 static INLINE int
  79 get_irn_uplink (ir_node *n) {
  80   assert(get_irn_link(n));
  81   return ((scc_info *)get_irn_link(n))->uplink;
  82 }
  83
  84 static INLINE void
  85 set_irn_dfn (ir_node *n, int dfn) {
  86   if (! get_irn_link(n)) { DDMN(n); DDME(get_irg_ent(current_ir_graph));}
  87   assert(get_irn_link(n));
  88   ((scc_info *)get_irn_link(n))->dfn = dfn;
  89 }
  90
  91 static INLINE int
  92 get_irn_dfn (ir_node *n) {
  93   assert(get_irn_link(n));
  94   return ((scc_info *)get_irn_link(n))->dfn;
  95 }
  96
  97 /* Uses temporary information to set the loop */
  98 static INLINE void
  99 set_irn_loop_tmp (ir_node *n, ir_loop* loop) {
 100   assert(get_irn_link(n));
 101   ((scc_info *)get_irn_link(n))->loop = loop;
 102 }
 103
 104 #if 0
 105 /* Uses temporary information to get the loop */
 106 static INLINE ir_loop *
 107 get_irn_loop_tmp (ir_node *n) {
 108   assert(get_irn_link(n));
 109   return ((scc_info *)get_irn_link(n))->loop;
 110 }
 111 #endif
 112
 113 static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
 114   int i;
 115   ir_loop *res = NULL;
 116
 117   /* Test whether n is contained in this loop. */
 118   for (i = 0; i < get_loop_n_nodes(l); i++)
 119     if (n == get_loop_node(l, i)) return l;
 120
 121   /* Is this a leave in the loop tree? If so loop not found. */
 122   if (get_loop_n_sons(l) == 0) return NULL;
 123
 124   /* Else descend in the loop tree. */
 125   for (i = 0; i < get_loop_n_sons(l); i++) {
 126     res = find_nodes_loop(n, get_loop_son(l, i));
 127     if (res) break;
 128   }
 129   return res;
 130 }
 131
 132 /* @@@ temporary implementation, costly!!! */
 133 ir_loop * get_irn_loop(ir_node *n) {
 134   ir_loop *l = get_irg_loop(current_ir_graph);
 135   l = find_nodes_loop(n, l);
 136   return l;
 137 }
 138
 139 /**********************************************************************/
 140 /* A stack.                                                          **/
 141 /**********************************************************************/
 142
 143 static ir_node **stack = NULL;
 144 static int tos = 0;                /* top of stack */
 145
 146 static INLINE void init_stack(void) {
 147   if (stack) {
 148     ARR_RESIZE (ir_node *, stack, 1000);
 149   } else {
 150     stack = NEW_ARR_F (ir_node *, 1000);
 151   }
 152   tos = 0;
 153 }
 154
 155 #if 0
 156 static INLINE void free_stack(void) {
 157   DEL_ARR_F(stack);
 158   stack = NULL;
 159   tos = 0;
 160 }
 161 #endif
 162
 163 static INLINE void
 164 push (ir_node *n)
 165 {
 166   //DDMN(n);
 167
 168   if (tos == ARR_LEN (stack)) {
 169     int nlen = ARR_LEN (stack) * 2;
 170     ARR_RESIZE (ir_node *, stack, nlen);
 171   }
 172   stack [tos++] = n;
 173   mark_irn_in_stack(n);
 174 }
 175
 176 static INLINE ir_node *
 177 pop (void)
 178 {
 179   ir_node *n = stack[--tos];
 180   mark_irn_not_in_stack(n);
 181   return n;
 182 }
 183
 184 /* The nodes up to n belong to the current loop.
 185    Removes them from the stack and adds them to the current loop. */
 186 static INLINE void
 187 pop_scc_to_loop (ir_node *n)
 188 {
 189   ir_node *m;
 190
 191   for (;;) {
 192     m = pop();
 193     set_irn_dfn(m, loop_node_cnt);
 194     loop_node_cnt++;
 195     add_loop_node(current_loop, m);
 196     set_irn_loop_tmp(m, current_loop);
 197     if (m==n) break;
 198   }
 199 }
 200
 201 /* Removes and unmarks all nodes up to n from the stack.
 202    The nodes must be visited once more to assign them to a scc. */
 203 static INLINE void
 204 pop_scc_unmark_visit (ir_node *n)
 205 {
 206   ir_node *m = NULL;
 207
 208   while (m != n) {
 209     m = pop();
 210     set_irn_visited(m, 0);
 211   }
 212 }
 213
 214 /**********************************************************************/
 215 /* The loop datastructure.                                           **/
 216 /**********************************************************************/
 217
 218 /* Allocates a new loop as son of current_loop.  Sets current_loop
 219    to the new loop and returns the father. */
 220 static ir_loop *new_loop (void) {
 221   ir_loop *father, *son;
 222
 223   father = current_loop;
 224
 225   son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
 226   memset (son, 0, sizeof (ir_loop));
 227   son->kind = k_ir_loop;
 228 /*  son->sons = NEW_ARR_F (ir_loop *, 0);
 229   son->nodes = NEW_ARR_F (ir_node *, 0);
 230   A. Schoesser: Removed, because array children was introduced,
 231                 which contains both, nodes AND sons.
 232                 This comment may be removed after beeing read by all important persons :) */
 233   son->children = NEW_ARR_F (loop_element, 0);
 234   son->n_nodes = 0;
 235   son->n_sons=0;
 236   if (father) {
 237     son->outer_loop = father;
 238     add_loop_son(father, son);
 239     son->depth = father->depth+1;
 240   } else {  /* The root loop */
 241     son->outer_loop = son;
 242     son->depth = 0;
 243   }
 244
 245   current_loop = son;
 246   return father;
 247 }
 248
 249 #if 0
 250 /* Finishes the datastructures, copies the arrays to the obstack
 251    of current_ir_graph.
 252    A. Schoesser: Caution: loop -> sons is gone. */
 253 static void mature_loop (ir_loop *loop) {
 254   ir_loop **new_sons;
 255
 256   new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
 257   memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
 258   DEL_ARR_F(loop->sons);
 259   loop->sons = new_sons;
 260 }
 261 #endif
 262
 263 /* Returns outer loop, itself if outermost. */
 264 ir_loop *get_loop_outer_loop (ir_loop *loop) {
 265   assert(loop && loop->kind == k_ir_loop);
 266   return loop->outer_loop;
 267 }
 268
 269 /* Returns nesting depth of this loop */
 270 int get_loop_depth (ir_loop *loop) {
 271   assert(loop); assert(loop->kind == k_ir_loop);
 272   return loop->depth;
 273 }
 274
 275 /* Returns the number of inner loops */
 276 int      get_loop_n_sons (ir_loop *loop) {
 277   assert(loop && loop->kind == k_ir_loop);
 278   return(loop -> n_sons);
 279 }
 280
 281 /* Returns the pos`th loop_node-child              *
 282  * TODO: This method isn`t very efficient !        *
 283  * Returns NULL if there isnt`t a pos`th loop_node */
 284 ir_loop *get_loop_son (ir_loop *loop, int pos) {
 285   int child_nr = 0, loop_nr = -1;
 286
 287   assert(loop && loop->kind == k_ir_loop);
 288   while(child_nr < ARR_LEN(loop->children))
 289    {
 290     if(*(loop -> children[child_nr].kind) == k_ir_loop)
 291       loop_nr++;
 292     if(loop_nr == pos)
 293       return(loop -> children[child_nr].son);
 294     child_nr++;
 295    }
 296   return NULL;
 297 }
 298
 299 /* Use EXCLUSIVELY this function to add sons, otherwise the loop->n_sons
 300    is invalid! */
 301
 302 static INLINE void
 303 add_loop_son(ir_loop *loop, ir_loop *son) {
 304   assert(loop && loop->kind == k_ir_loop);
 305   assert(get_kind(son) == k_ir_loop);
 306   ARR_APP1 (loop_element, loop->children, (loop_element) son);
 307   loop -> n_sons++;
 308 }
 309
 310 /* Returns the number of nodes in the loop */
 311 int      get_loop_n_nodes (ir_loop *loop) {
 312   assert(loop); assert(loop->kind == k_ir_loop);
 313   return loop -> n_nodes;
 314 /*  return ARR_LEN(loop->nodes); */
 315 }
 316
 317 /* Returns the pos`th ir_node-child                *
 318  * TODO: This method isn`t very efficient !        *
 319  * Returns NULL if there isnt`t a pos`th ir_node   */
 320 ir_node *get_loop_node (ir_loop *loop, int pos) {
 321   int child_nr, node_nr = -1;
 322
 323   assert(loop && loop->kind == k_ir_loop);
 324   assert(pos < get_loop_n_nodes(loop));
 325
 326   for (child_nr = 0; child_nr < ARR_LEN(loop->children); child_nr++) {
 327     if(*(loop -> children[child_nr].kind) == k_ir_node)
 328       node_nr++;
 329     if(node_nr == pos)
 330       return(loop -> children[child_nr].node);
 331   }
 332   assert(0 && "no child at pos found");
 333   return NULL;
 334 }
 335
 336 /* Use EXCLUSIVELY this function to add nodes, otherwise the loop->n_nodes
 337    is invalid! */
 338
 339 static INLINE void
 340 add_loop_node(ir_loop *loop, ir_node *n) {
 341   assert(loop && loop->kind == k_ir_loop);
 342   assert(get_kind(n) == k_ir_node);
 343   ARR_APP1 (loop_element, loop->children, (loop_element) n);
 344   loop->n_nodes++;
 345 }
 346
 347 /** Returns the number of elements contained in loop.  */
 348 int get_loop_n_elements (ir_loop *loop) {
 349   assert(loop && loop->kind == k_ir_loop);
 350   return(ARR_LEN(loop->children));
 351 }
 352
 353 /*
 354  Returns the pos`th loop element.
 355  This may be a loop_node or a ir_node. The caller of this function has
 356  to check the *(loop_element.kind) field for "k_ir_node" or "k_ir_loop"
 357  and then select the apropriate "loop_element.node" or "loop_element.son".
 358 */
 359
 360 loop_element get_loop_element (ir_loop *loop, int pos) {
 361   assert(loop && loop->kind == k_ir_loop && pos < ARR_LEN(loop->children));
 362
 363   return(loop -> children[pos]);
 364 }
 365
 366 /* The outermost loop is remarked in the surrounding graph. */
 367 void     set_irg_loop(ir_graph *irg, ir_loop *loop) {
 368   assert(irg);
 369   irg->loop = loop;
 370 }
 371 ir_loop *get_irg_loop(ir_graph *irg) {
 372   assert(irg);
 373   return irg->loop;
 374 }
 375
 376 /**********************************************************************/
 377 /* Constructing and destructing the loop/backedge information.       **/
 378 /**********************************************************************/
 379
 380 /* Initialization steps. **********************************************/
 381
 382 static INLINE void
 383 init_node (ir_node *n, void *env) {
 384   set_irn_link (n, new_scc_info());
 385   clear_backedges(n);
 386 #if 0
 387   /* Also init nodes not visible in intraproc_view. */
 388     /* @@@ init_node is called for too many nodes -- this wastes memory!.
 389        The mem is not lost as its on the obstack. */
 390   if (get_irn_op(n) == op_Filter) {
 391     for (i = 0; i < get_Filter_n_cg_preds(n); i++)
 392       init_node(get_Filter_cg_pred(n, i), NULL);
 393   }
 394   if (get_irn_op(n) == op_Block) {
 395     for (i = 0; i < get_Block_cg_n_cfgpreds(n); i++) {
 396       init_node(get_Block_cg_cfgpred(n, i), NULL);
 397     }
 398   }
 399   /* The following pattern matches only after a call from above pattern. */
 400   if ((get_irn_op(n) == op_Proj) /*&& (get_Proj_proj(n) == 0)*/) {
 401     /* @@@ init_node is called for every proj -- this wastes memory!.
 402        The mem is not lost as its on the obstack. */
 403     ir_node *cb = get_Proj_pred(n);
 404     if ((get_irn_op(cb) == op_CallBegin) ||
 405         (get_irn_op(cb) == op_EndReg) ||
 406         (get_irn_op(cb) == op_EndExcept)) {
 407       init_node(cb, NULL);
 408       init_node(get_nodes_Block(cb), NULL);
 409     }
 410 #endif
 411 }
 412
 413 static INLINE void
 414 init_scc (ir_graph *irg) {
 415   current_dfn = 1;
 416   loop_node_cnt = 0;
 417   init_stack();
 418   irg_walk_graph (irg, init_node, NULL, NULL);
 419   /*
 420   irg_walk (irg, link_to_reg_end, NULL, NULL);
 421   */
 422 }
 423
 424 static INLINE void
 425 init_ip_scc (void) {
 426   current_dfn = 1;
 427   loop_node_cnt = 0;
 428   init_stack();
 429   cg_walk (init_node, NULL, NULL);
 430 }
 431
 432 #if 0
 433 Works, but is inefficient.
 434 static INLINE void
 435 init_ip_scc (void) {
 436   int i;
 437   interprocedural_view = 1;
 438   current_dfn = 1;
 439   loop_node_cnt = 0;
 440   init_stack();
 441   for (i = 0; i < get_irp_n_irgs(); i++) {
 442     current_ir_graph = get_irp_irg(i);
 443     irg_walk_graph (current_ir_graph, init_node, NULL, NULL);
 444     /* @@@ decrease max_visited to avoide double walks */
 445   }
 446 }
 447 #endif
 448
 449 /* Condition for breaking the recursion. */
 450 static bool is_outermost_Start(ir_node *n) {
 451   /* Test whether this is the outermost Start node.  If so
 452      recursion must end. */
 453   if ((get_irn_op(n) == op_Block)     &&
 454       (get_Block_n_cfgpreds(n) == 1)  &&
 455       (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
 456       (get_nodes_Block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
 457     return true;
 458   }
 459 #if 0
 460   /*  @@@ Bad condition:
 461       not possible in interprocedural view as outermost_graph is
 462       not necessarily the only with a dead-end start block.
 463       Besides current_ir_graph is not set properly. */
 464   if ((get_irn_op(n) == op_Block) &&
 465       (n == get_irg_start_block(current_ir_graph))) {
 466     if ((!interprocedural_view)  ||
 467         (current_ir_graph == outermost_ir_graph))
 468       return true;
 469   }
 470 #endif
 471   return false;
 472 }
 473
 474 /* Don't walk from nodes to blocks except for Control flow operations. */
 475 static INLINE int
 476 get_start_index(ir_node *n) {
 477   if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
 478     return -1;
 479   else
 480     return 0;
 481 }
 482
 483 /* Returns current_ir_graph and set it to the irg of predecessor index
 484    of node n. */
 485 static INLINE ir_graph *
 486 switch_irg (ir_node *n, int index) {
 487   ir_graph *old_current = current_ir_graph;
 488
 489   if (interprocedural_view) {
 490     /* Only Filter and Block nodes can have predecessors in other graphs. */
 491     if (get_irn_op(n) == op_Filter)
 492       n = get_nodes_Block(n);
 493     if (get_irn_op(n) == op_Block) {
 494       ir_node *cfop = skip_Proj(get_Block_cfgpred(n, index));
 495       if (is_ip_cfop(cfop)) {
 496         current_ir_graph = get_irn_irg(cfop);
 497         set_irg_visited(current_ir_graph, get_max_irg_visited());
 498       }
 499     }
 500   }
 501
 502   return old_current;
 503 }
 504
 505 /* Walks up the stack passing n and then finding the node
 506    where we walked into the irg n is contained in.
 507    Here we switch the irg. */
 508 static ir_graph *
 509 find_irg_on_stack (ir_node *n) {
 510   ir_node *m;
 511   ir_graph *old_current = current_ir_graph;
 512   int i;
 513
 514   if (interprocedural_view) {
 515     for (i = tos; i >= 0; i--) {
 516       if (stack[i] == n) break;
 517     }
 518     if (i < 0) i = tos;
 519
 520     //printf(" Here\n");
 521
 522     assert (i >= 0);
 523     for (; i >= 0; i--) {
 524       m = stack[i];
 525       //printf(" Visiting %d ", i); DDMN(m);
 526       if (is_ip_cfop(m)) {
 527         current_ir_graph = get_irn_irg(m);
 528         break;
 529       }
 530       if (get_irn_op(m) == op_Filter) {
 531         /* Find the corresponding ip_cfop */
 532         ir_node *pred = stack[i+1];
 533         int j;
 534         for (j = 0; j < get_Filter_n_cg_preds(m); j++)
 535           if (get_Filter_cg_pred(m, j) == pred) break;
 536         if (j >= get_Filter_n_cg_preds(m))
 537           /* It is a filter we didn't pass as the predecessors are marked. */
 538           continue;
 539         assert(get_Filter_cg_pred(m, j) == pred);
 540         switch_irg(m, j);
 541         break;
 542       }
 543     }
 544   }
 545
 546   return old_current;
 547 }
 548
 549 #if 0
 550 static void test(ir_node *pred, ir_node *root, ir_node *this) {
 551   int i;
 552   if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
 553
 554   printf("this: %d ", get_irn_uplink(this)); DDMN(this);
 555   printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
 556   printf("root: %d ", get_irn_uplink(root)); DDMN(root);
 557
 558   printf("tos: %d\n", tos);
 559
 560   for (i = tos; i >= 0; i--) {
 561     ir_node *n = stack[i];
 562     if (!n) continue;
 563     printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
 564   }
 565 }
 566 #endif
 567
 568 /* Returns true if n is a loop header, i.e., it is a Block, Phi
 569    or Filter node and has predecessors within the loop and out
 570    of the loop. */
 571 static bool
 572 is_head (ir_node *n, ir_node *root)
 573 {
 574   int i;
 575   int some_outof_loop = 0,  some_in_loop = 0;
 576
 577   /* Test for legal loop header */
 578   if (!((get_irn_op(n) == op_Block) ||
 579         (get_irn_op(n) == op_Phi) ||
 580         ((get_irn_op(n) == op_Filter) && interprocedural_view)))
 581     return false;
 582
 583   if (!is_outermost_Start(n)) {
 584     for (i = get_start_index(n); i < get_irn_arity(n); i++) {
 585       ir_node *pred = get_irn_n(n, i);
 586       assert(pred);
 587       if (is_backedge(n, i)) continue;
 588       if (!irn_is_in_stack(pred)) {
 589         some_outof_loop = 1;
 590       } else {
 591         assert(get_irn_uplink(pred) >= get_irn_uplink(root));
 592         some_in_loop = 1;
 593       }
 594     }
 595   }
 596   return some_outof_loop && some_in_loop;
 597 }
 598
 599 /* Returns index of the predecessor with the smallest dfn number
 600    greater-equal than limit. */
 601 static int
 602 smallest_dfn_pred (ir_node *n, int limit)
 603 {
 604   int i, index = -2, min = -1;
 605
 606   if (!is_outermost_Start(n)) {
 607     for (i = get_start_index(n); i < get_irn_arity(n); i++) {
 608       ir_node *pred = get_irn_n(n, i);
 609       assert(pred);
 610       if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
 611       if (get_irn_dfn(pred) >= limit
 612         && (min == -1 || get_irn_dfn(pred) < min)) {
 613         index = i;
 614         min = get_irn_dfn(pred);
 615       }
 616     }
 617   }
 618   return index;
 619 }
 620
 621 /* Returns index of the predecessor with the largest dfn number. */
 622 static int
 623 largest_dfn_pred (ir_node *n)
 624 {
 625   int i, index = -2, max = -1;
 626
 627   if (!is_outermost_Start(n)) {
 628     for (i = get_start_index(n); i < get_irn_arity(n); i++) {
 629       ir_node *pred = get_irn_n(n, i);
 630       if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
 631       if (get_irn_dfn(pred) > max) {
 632         index = i;
 633         max = get_irn_dfn(pred);
 634       }
 635     }
 636   }
 637   return index;
 638 }
 639
 640 /* Searches the stack for possible loop heads.  Tests these for backedges.
 641    If it finds a head with an unmarked backedge it marks this edge and
 642    returns the tail of the loop.
 643    If it finds no backedge returns NULL. */
 644 static ir_node *
 645 find_tail (ir_node *n) {
 646   ir_node *m;
 647   int i, res_index = -2;
 648
 649   /*
 650     if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
 651   */
 652
 653   m = stack[tos-1];
 654   if (is_head (m, n)) {
 655     res_index = smallest_dfn_pred(m, 0);
 656     if ((res_index == -2) &&  /* no smallest dfn pred found. */
 657         (n == m))
 658       return NULL;
 659   } else {
 660     if (m == n) return NULL;
 661     for (i = tos-2; ; --i) {
 662       m = stack[i];
 663       if (is_head (m, n)) {
 664         res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
 665         if (res_index == -2)  /* no smallest dfn pred found. */
 666           res_index = largest_dfn_pred (m);
 667         break;
 668       }
 669     }
 670   }
 671   assert (res_index > -2);
 672
 673   set_backedge (m, res_index);
 674   return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
 675 }
 676
 677
 678 /* The core algorithm. *****************************************/
 679
 680 static void scc (ir_node *n) {
 681   int i;
 682   ir_graph *rem;
 683
 684   if (irn_visited(n)) return;
 685   mark_irn_visited(n);
 686   //printf("mark: %d ", get_irn_visited(n)); DDMN(n);
 687   //DDME(get_irg_ent(current_ir_graph));
 688
 689   /* Initialize the node */
 690   set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
 691   set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
 692   set_irn_loop_tmp(n, NULL);
 693   current_dfn ++;
 694
 695   /* What's this good for?
 696   n->ana.scc.section = NULL;
 697   */
 698
 699   push(n);
 700
 701   if (!is_outermost_Start(n)) {
 702     for (i = get_start_index(n); i < get_irn_arity(n); i++) {
 703       ir_node *m;
 704       if (is_backedge(n, i)) continue;
 705
 706       m = get_irn_n(n, i); //get_irn_ip_pred(n, i);
 707       if ((!m) || (get_irn_op(m) == op_Unknown)) continue;
 708       scc (m);
 709       //return_recur(n, i);
 710
 711       if (irn_is_in_stack(m)) {
 712         /* Uplink of m is smaller if n->m is a backedge.
 713            Propagate the uplink to mark the loop. */
 714         if (get_irn_uplink(m) < get_irn_uplink(n))
 715           set_irn_uplink(n, get_irn_uplink(m));
 716       }
 717     }
 718   }
 719   if (get_irn_dfn(n) == get_irn_uplink(n)) {
 720     /* This condition holds for the node with the incoming backedge. */
 721     ir_node *tail = find_tail(n);
 722     if (tail) {
 723       /* We found a new loop! */
 724       ir_loop *l = new_loop();
 725       /* Remove the loop from the stack ... */
 726       pop_scc_unmark_visit (n);
 727       /* and recompute it in a better order; and so that it goes into
 728          the new loop. */
 729       rem = find_irg_on_stack(tail);
 730       scc (tail);
 731       current_ir_graph = rem;
 732
 733       assert (irn_visited(n));
 734
 735       current_loop = l;
 736     } else {
 737       pop_scc_to_loop(n);
 738     }
 739   }
 740 }
 741
 742 /* Constructs backedge information for irg. In interprocedural view constructs
 743    backedges for all methods called by irg, too. */
 744 void construct_backedges(ir_graph *irg) {
 745   ir_graph *rem = current_ir_graph;
 746   ir_loop *head_rem;
 747   int i;
 748
 749   assert(!interprocedural_view &&
 750          "not implemented, use construct_ip_backedges");
 751
 752   current_ir_graph = irg;
 753   outermost_ir_graph = irg;
 754
 755   init_scc(irg);
 756
 757   current_loop = NULL;
 758   new_loop();  /* sets current_loop */
 759   head_rem = current_loop; /* Just for assertion */
 760
 761   if (interprocedural_view) {
 762     set_irg_visited(irg, inc_max_irg_visited());
 763     init_ip_walk ();
 764   } else {
 765     inc_irg_visited(irg);
 766   }
 767
 768   scc(get_irg_end(irg));
 769   for (i = 0; i < get_End_n_keepalives(get_irg_end(irg)); i++)
 770     scc(get_End_keepalive(get_irg_end(irg), i));
 771
 772   if (interprocedural_view) finish_ip_walk();
 773
 774   assert(head_rem == current_loop);
 775   set_irg_loop(irg, current_loop);
 776   assert(get_irg_loop(irg)->kind == k_ir_loop);
 777   /*
 778   irg->loops = current_loop;
 779   if (icfg == 1) {
 780     int count = 0;
 781     int depth = 0;
 782     count_loop (the_loop, &count, &depth);
 783     }
 784   }
 785   */
 786   current_ir_graph = rem;
 787 }
 788
 789
 790
 791 void construct_ip_backedges (void) {
 792   ir_graph *rem = current_ir_graph;
 793   int rem_ipv = interprocedural_view;
 794   int i, j;
 795
 796   outermost_ir_graph = get_irp_main_irg();
 797
 798   init_ip_scc();
 799
 800   current_loop = NULL;
 801   new_loop();  /* sets current_loop */
 802   interprocedural_view = 1;
 803
 804   inc_max_irg_visited();
 805   for (i = 0; i < get_irp_n_irgs(); i++)
 806     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
 807
 808   for (i = 0; i < get_irp_n_irgs(); i++) {
 809     ir_node *sb;
 810     current_ir_graph = get_irp_irg(i);
 811     //DDME(get_irg_ent(current_ir_graph));
 812     /* Find real entry points */
 813     sb = get_irg_start_block(current_ir_graph);
 814     if ((get_Block_n_cfgpreds(sb) > 1) ||
 815         (get_nodes_Block(get_Block_cfgpred(sb, 0)) != sb)) continue;
 816     //    printf("running scc for "); DDME(get_irg_ent(current_ir_graph));
 817     /* Compute scc for this graph */
 818     outermost_ir_graph = current_ir_graph;
 819     set_irg_visited(outermost_ir_graph, get_max_irg_visited());
 820     scc(get_irg_end(current_ir_graph));
 821     for (j = 0; j < get_End_n_keepalives(get_irg_end(outermost_ir_graph)); j++)
 822       scc(get_End_keepalive(get_irg_end(outermost_ir_graph), j));
 823   }
 824
 825   set_irg_loop(outermost_ir_graph, current_loop);
 826   assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
 827
 828   current_ir_graph = rem;
 829   interprocedural_view = rem_ipv;
 830 }