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

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