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