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  *              A variation on the Tarjan algorithm. See also [Trapp:99],
   7  *              Chapter 5.2.1.2.
   8  * Author:      Goetz Lindenmaier
   9  * Modified by:
  10  * Created:     7.2002
  11  * CVS-ID:      $Id$
  12  * Copyright:   (c) 2002-2003 Universität Karlsruhe
  13  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  14  */
  15
  16 #ifdef HAVE_CONFIG_H
  17 #include "config.h"
  18 #endif
  19
  20 #include <string.h>
  21
  22 #include "irloop_t.h"
  23 #include "irnode.h"
  24 #include "irgraph_t.h"
  25 #include "array.h"
  26 #include "pmap.h"
  27 #include "irgwalk.h"
  28 #include "irprog_t.h"
  29
  30 ir_graph *outermost_ir_graph;      /* The outermost graph the scc is computed
  31                                       for */
  32 static ir_loop *current_loop;      /* Current loop construction is working
  33                                       on. */
  34 static int loop_node_cnt = 0;      /* Counts the number of allocated loop nodes.
  35                                       Each loop node gets a unique number.
  36                                       What for? ev. remove. @@@ */
  37 static int current_dfn = 1;        /* Counter to generate depth first numbering
  38                                       of visited nodes.  */
  39
  40 /**********************************************************************/
  41 /* Node attributes                                                   **/
  42 /**********************************************************************/
  43
  44 /* A map to get from irnodes to loop nodes. */
  45 static pmap *node_loop_map = NULL;
  46
  47 /**********************************************************************/
  48 /* Node attributes needed for the construction.                      **/
  49 /**********************************************************************/
  50
  51 typedef struct scc_info {
  52   bool in_stack;         /* Marks whether node is on the stack. */
  53   int dfn;               /* Depth first search number. */
  54   int uplink;            /* dfn number of ancestor. */
  55   //  ir_loop *loop;         /* Refers to the containing loop. */
  56   /*
  57       struct section *section;
  58       xset def;
  59       xset use;
  60   */
  61 } scc_info;
  62
  63 static INLINE scc_info* new_scc_info(void) {
  64   scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
  65   memset (info, 0, sizeof (scc_info));
  66   return info;
  67 }
  68
  69 static INLINE void
  70 mark_irn_in_stack (ir_node *n) {
  71   assert(get_irn_link(n));
  72   ((scc_info *)get_irn_link(n))->in_stack = true;
  73 }
  74
  75 static INLINE void
  76 mark_irn_not_in_stack (ir_node *n) {
  77   assert(get_irn_link(n));
  78   ((scc_info *)get_irn_link(n))->in_stack = false;
  79 }
  80
  81 static INLINE bool
  82 irn_is_in_stack (ir_node *n) {
  83   assert(get_irn_link(n));
  84   return ((scc_info *)get_irn_link(n))->in_stack;
  85 }
  86
  87 static INLINE void
  88 set_irn_uplink (ir_node *n, int uplink) {
  89   assert(get_irn_link(n));
  90   ((scc_info *)get_irn_link(n))->uplink = uplink;
  91 }
  92
  93 static INLINE int
  94 get_irn_uplink (ir_node *n) {
  95   assert(get_irn_link(n));
  96   return ((scc_info *)get_irn_link(n))->uplink;
  97 }
  98
  99 static INLINE void
 100 set_irn_dfn (ir_node *n, int dfn) {
 101   if (! get_irn_link(n)) { DDMN(n); DDME(get_irg_ent(current_ir_graph));}
 102   assert(get_irn_link(n));
 103   ((scc_info *)get_irn_link(n))->dfn = dfn;
 104 }
 105
 106 static INLINE int
 107 get_irn_dfn (ir_node *n) {
 108   assert(get_irn_link(n));
 109   return ((scc_info *)get_irn_link(n))->dfn;
 110 }
 111
 112 /* Uses temporary information to set the loop */
 113 static INLINE void
 114 set_irn_loop (ir_node *n, ir_loop* loop) {
 115   //assert(get_irn_link(n));
 116   //((scc_info *)get_irn_link(n))->loop = loop;
 117   assert(node_loop_map && "not initialized!");
 118   pmap_insert(node_loop_map, (void *)n, (void *)loop);
 119 }
 120
 121 /* Uses temporary information to get the loop */
 122 INLINE ir_loop *
 123 get_irn_loop (ir_node *n) {
 124   ir_loop *res = NULL;
 125   //assert(get_irn_link(n));
 126   //return ((scc_info *)get_irn_link(n))->loop;
 127   assert(node_loop_map && "not initialized!");
 128
 129   if (pmap_contains(node_loop_map, (void *)n))
 130     res = (ir_loop *) pmap_get(node_loop_map, (void *)n);
 131
 132   return res;
 133 }
 134
 135 #if 0
 136 static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
 137   int i;
 138   ir_loop *res = NULL;
 139
 140   /* Test whether n is contained in this loop. */
 141   for (i = 0; i < get_loop_n_nodes(l); i++)
 142     if (n == get_loop_node(l, i)) return l;
 143
 144   /* Is this a leave in the loop tree? If so loop not found. */
 145   if (get_loop_n_sons(l) == 0) return NULL;
 146
 147   /* Else descend in the loop tree. */
 148   for (i = 0; i < get_loop_n_sons(l); i++) {
 149     res = find_nodes_loop(n, get_loop_son(l, i));
 150     if (res) break;
 151   }
 152   return res;
 153 }
 154
 155 /* @@@ temporary implementation, costly!!! */
 156 ir_loop * get_irn_loop(ir_node *n) {
 157   ir_loop *l = get_irg_loop(current_ir_graph);
 158   l = find_nodes_loop(n, l);
 159   return l;
 160 }
 161 #endif
 162
 163 /**********************************************************************/
 164 /* A stack.                                                          **/
 165 /**********************************************************************/
 166
 167 static ir_node **stack = NULL;
 168 static int tos = 0;                /* top of stack */
 169
 170 static INLINE void init_stack(void) {
 171   if (stack) {
 172     ARR_RESIZE (ir_node *, stack, 1000);
 173   } else {
 174     stack = NEW_ARR_F (ir_node *, 1000);
 175   }
 176   tos = 0;
 177 }
 178
 179 #if 0
 180 static INLINE void free_stack(void) {
 181   DEL_ARR_F(stack);
 182   stack = NULL;
 183   tos = 0;
 184 }
 185 #endif
 186
 187 static INLINE void
 188 push (ir_node *n)
 189 {
 190   /*DDMN(n);*/
 191
 192   if (tos == ARR_LEN (stack)) {
 193     int nlen = ARR_LEN (stack) * 2;
 194     ARR_RESIZE (ir_node *, stack, nlen);
 195   }
 196   stack [tos++] = n;
 197   mark_irn_in_stack(n);
 198 }
 199
 200 static INLINE ir_node *
 201 pop (void)
 202 {
 203   ir_node *n = stack[--tos];
 204   mark_irn_not_in_stack(n);
 205   return n;
 206 }
 207
 208 /* The nodes up to n belong to the current loop.
 209    Removes them from the stack and adds them to the current loop. */
 210 static INLINE void
 211 pop_scc_to_loop (ir_node *n)
 212 {
 213   ir_node *m;
 214   int i = 0;
 215
 216   /*for (;;) {*/
 217   do
 218     {
 219     m = pop();
 220     loop_node_cnt++;
 221     set_irn_dfn(m, loop_node_cnt);
 222     add_loop_node(current_loop, m);
 223     set_irn_loop(m, current_loop);
 224     i++;
 225     /*    if (m==n) break;*/
 226     } while(m != n);
 227
 228   if(i > 1)
 229     printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
 230 }
 231
 232 /* GL ??? my last son is my grandson???  Removes loops with no
 233    ir_nodes in them.  Such loops have only another loop as son. (Why
 234    can't they have two loops as sons? Does it never get that far? ) */
 235 void close_loop (ir_loop *l)
 236 {
 237   int last = get_loop_n_elements(l) - 1;
 238   loop_element lelement = get_loop_element(l, last);
 239   ir_loop *last_son = lelement.son;
 240
 241   if (get_kind(last_son) == k_ir_loop &&
 242       get_loop_n_elements(last_son) == 1)
 243     {
 244       ir_loop *gson;
 245
 246       lelement = get_loop_element(last_son, 0);
 247       gson = lelement.son;
 248       if(get_kind(gson) == k_ir_loop)
 249         {
 250           loop_element new_last_son;
 251
 252           gson -> outer_loop = l;
 253           new_last_son.son = gson;
 254           l -> children[last] = new_last_son;
 255         }
 256     }
 257
 258   current_loop = l;
 259 }
 260
 261 /* Removes and unmarks all nodes up to n from the stack.
 262    The nodes must be visited once more to assign them to a scc. */
 263 static INLINE void
 264 pop_scc_unmark_visit (ir_node *n)
 265 {
 266   ir_node *m = NULL;
 267
 268   while (m != n) {
 269     m = pop();
 270     set_irn_visited(m, 0);
 271   }
 272 }
 273
 274 /**********************************************************************/
 275 /* The loop datastructure.                                           **/
 276 /**********************************************************************/
 277
 278 /* Allocates a new loop as son of current_loop.  Sets current_loop
 279    to the new loop and returns the father. */
 280 static ir_loop *new_loop (void) {
 281   ir_loop *father, *son;
 282
 283   father = current_loop;
 284
 285   son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
 286   memset (son, 0, sizeof (ir_loop));
 287   son->kind = k_ir_loop;
 288   son->children = NEW_ARR_F (loop_element, 0);
 289   son->n_nodes = 0;
 290   son->n_sons=0;
 291   if (father) {
 292     son->outer_loop = father;
 293     add_loop_son(father, son);
 294     son->depth = father->depth+1;
 295   } else {  /* The root loop */
 296     son->outer_loop = son;
 297     son->depth = 0;
 298   }
 299
 300 #ifdef DEBUG_libfirm
 301   son->loop_nr = get_irp_new_node_nr();
 302   son->link = NULL;
 303 #endif
 304
 305   current_loop = son;
 306   return father;
 307 }
 308
 309 #if 0
 310 /* Finishes the datastructures, copies the arrays to the obstack
 311    of current_ir_graph.
 312    A. Schoesser: Caution: loop -> sons is gone. */
 313 static void mature_loop (ir_loop *loop) {
 314   ir_loop **new_sons;
 315
 316   new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
 317   memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
 318   DEL_ARR_F(loop->sons);
 319   loop->sons = new_sons;
 320 }
 321 #endif
 322
 323 /* Returns outer loop, itself if outermost. */
 324 ir_loop *get_loop_outer_loop (ir_loop *loop) {
 325   assert(loop && loop->kind == k_ir_loop);
 326   return loop->outer_loop;
 327 }
 328
 329 /* Returns nesting depth of this loop */
 330 int get_loop_depth (ir_loop *loop) {
 331   assert(loop); assert(loop->kind == k_ir_loop);
 332   return loop->depth;
 333 }
 334
 335 /* Returns the number of inner loops */
 336 int      get_loop_n_sons (ir_loop *loop) {
 337   assert(loop && loop->kind == k_ir_loop);
 338   return(loop -> n_sons);
 339 }
 340
 341 /* Returns the pos`th loop_node-child              *
 342  * TODO: This method isn`t very efficient !        *
 343  * Returns NULL if there isnt`t a pos`th loop_node */
 344 ir_loop *get_loop_son (ir_loop *loop, int pos) {
 345   int child_nr = 0, loop_nr = -1;
 346
 347   assert(loop && loop->kind == k_ir_loop);
 348   while(child_nr < ARR_LEN(loop->children))
 349    {
 350     if(*(loop -> children[child_nr].kind) == k_ir_loop)
 351       loop_nr++;
 352     if(loop_nr == pos)
 353       return(loop -> children[child_nr].son);
 354     child_nr++;
 355    }
 356   return NULL;
 357 }
 358
 359 /* Use EXCLUSIVELY this function to add sons, otherwise the loop->n_sons
 360    is invalid! */
 361
 362 static INLINE void
 363 add_loop_son(ir_loop *loop, ir_loop *son) {
 364   loop_element lson;
 365   lson.son = son;
 366   assert(loop && loop->kind == k_ir_loop);
 367   assert(get_kind(son) == k_ir_loop);
 368   ARR_APP1 (loop_element, loop->children, lson);
 369   loop -> n_sons++;
 370 }
 371
 372 /* Returns the number of nodes in the loop */
 373 int      get_loop_n_nodes (ir_loop *loop) {
 374   assert(loop); assert(loop->kind == k_ir_loop);
 375   return loop -> n_nodes;
 376 /*  return ARR_LEN(loop->nodes); */
 377 }
 378
 379 /* Returns the pos`th ir_node-child                *
 380  * TODO: This method isn`t very efficient !        *
 381  * Returns NULL if there isnt`t a pos`th ir_node   */
 382 ir_node *get_loop_node (ir_loop *loop, int pos) {
 383   int child_nr, node_nr = -1;
 384
 385   assert(loop && loop->kind == k_ir_loop);
 386   assert(pos < get_loop_n_nodes(loop));
 387
 388   for (child_nr = 0; child_nr < ARR_LEN(loop->children); child_nr++) {
 389     if(*(loop -> children[child_nr].kind) == k_ir_node)
 390       node_nr++;
 391     if(node_nr == pos)
 392       return(loop -> children[child_nr].node);
 393   }
 394   assert(0 && "no child at pos found");
 395   return NULL;
 396 }
 397
 398 /* Use EXCLUSIVELY this function to add nodes, otherwise the loop->n_nodes
 399    is invalid! */
 400
 401 static INLINE void
 402 add_loop_node(ir_loop *loop, ir_node *n) {
 403   loop_element ln;
 404   ln.node=n;
 405   assert(loop && loop->kind == k_ir_loop);
 406   assert(get_kind(n) == k_ir_node);
 407   ARR_APP1 (loop_element, loop->children, ln);
 408   loop->n_nodes++;
 409 }
 410
 411 /** Returns the number of elements contained in loop.  */
 412 int get_loop_n_elements (ir_loop *loop) {
 413   assert(loop && loop->kind == k_ir_loop);
 414   return(ARR_LEN(loop->children));
 415 }
 416
 417 /*
 418  Returns the pos`th loop element.
 419  This may be a loop_node or a ir_node. The caller of this function has
 420  to check the *(loop_element.kind) field for "k_ir_node" or "k_ir_loop"
 421  and then select the apropriate "loop_element.node" or "loop_element.son".
 422 */
 423
 424 loop_element get_loop_element (ir_loop *loop, int pos) {
 425   assert(loop && loop->kind == k_ir_loop && pos < ARR_LEN(loop->children));
 426
 427   return(loop -> children[pos]);
 428 }
 429
 430 int get_loop_element_pos(ir_loop *loop, void *le) {
 431   assert(loop && loop->kind == k_ir_loop);
 432   int i;
 433
 434   for (i = 0; i < get_loop_n_elements(loop); i++)
 435     if (get_loop_element(loop, i).node == le) return i;
 436   return -1;
 437 }
 438
 439 int get_loop_loop_nr(ir_loop *loop) {
 440   assert(loop && loop->kind == k_ir_loop);
 441 #ifdef DEBUG_libfirm
 442   return loop->loop_nr;
 443 #else
 444   return (int)loop;
 445 #endif
 446 }
 447
 448
 449 /** A field to connect additional information to a loop.  Only valid
 450     if libfirm_debug is set. */
 451 void  set_loop_link (ir_loop *loop, void *link) {
 452   assert(loop && loop->kind == k_ir_loop);
 453 #ifdef DEBUG_libfirm
 454   loop->link = link;
 455 #endif
 456 }
 457 void *get_loop_link (const ir_loop *loop) {
 458   assert(loop && loop->kind == k_ir_loop);
 459 #ifdef DEBUG_libfirm
 460   return loop->link;
 461 #else
 462   return NULL;
 463 #endif
 464 }
 465
 466 /* The outermost loop is remarked in the surrounding graph. */
 467 void     set_irg_loop(ir_graph *irg, ir_loop *loop) {
 468   assert(irg);
 469   irg->loop = loop;
 470 }
 471 ir_loop *get_irg_loop(ir_graph *irg) {
 472   assert(irg);
 473   return irg->loop;
 474 }
 475
 476
 477 /**********************************************************************/
 478 /* Constructing and destructing the loop/backedge information.       **/
 479 /**********************************************************************/
 480
 481 /* Initialization steps. **********************************************/
 482
 483 static INLINE void
 484 init_node (ir_node *n, void *env) {
 485   set_irn_link (n, new_scc_info());
 486   clear_backedges(n);
 487 #if 0
 488   /* Also init nodes not visible in intraproc_view. */
 489     /* @@@ init_node is called for too many nodes -- this wastes memory!.
 490        The mem is not lost as its on the obstack. */
 491   if (get_irn_op(n) == op_Filter) {
 492     for (i = 0; i < get_Filter_n_cg_preds(n); i++)
 493       init_node(get_Filter_cg_pred(n, i), NULL);
 494   }
 495   if (get_irn_op(n) == op_Block) {
 496     for (i = 0; i < get_Block_cg_n_cfgpreds(n); i++) {
 497       init_node(get_Block_cg_cfgpred(n, i), NULL);
 498     }
 499   }
 500   /* The following pattern matches only after a call from above pattern. */
 501   if ((get_irn_op(n) == op_Proj) /*&& (get_Proj_proj(n) == 0)*/) {
 502     /* @@@ init_node is called for every proj -- this wastes memory!.
 503        The mem is not lost as its on the obstack. */
 504     ir_node *cb = get_Proj_pred(n);
 505     if ((get_irn_op(cb) == op_CallBegin) ||
 506         (get_irn_op(cb) == op_EndReg) ||
 507         (get_irn_op(cb) == op_EndExcept)) {
 508       init_node(cb, NULL);
 509       init_node(get_nodes_Block(cb), NULL);
 510     }
 511   }
 512 #endif
 513 }
 514
 515 static INLINE void
 516 init_scc_common (void) {
 517   current_dfn = 1;
 518   loop_node_cnt = 0;
 519   if (!node_loop_map) node_loop_map = pmap_create();
 520   init_stack();
 521 }
 522
 523 static INLINE void
 524 init_scc (ir_graph *irg) {
 525   init_scc_common();
 526   irg_walk_graph (irg, init_node, NULL, NULL);
 527   /*
 528   irg_walk (irg, link_to_reg_end, NULL, NULL);
 529   */
 530 }
 531
 532 static INLINE void
 533 init_ip_scc (void) {
 534   init_scc_common();
 535   cg_walk (init_node, NULL, NULL);
 536 }
 537
 538 /* Condition for breaking the recursion. */
 539 static bool is_outermost_Start(ir_node *n) {
 540   /* Test whether this is the outermost Start node.  If so
 541      recursion must end. */
 542   if ((get_irn_op(n) == op_Block)     &&
 543       (get_Block_n_cfgpreds(n) == 1)  &&
 544       (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
 545       (get_nodes_Block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
 546     return true;
 547   }
 548 #if 0
 549   /*  @@@ Bad condition:
 550       not possible in interprocedural view as outermost_graph is
 551       not necessarily the only with a dead-end start block.
 552       Besides current_ir_graph is not set properly. */
 553   if ((get_irn_op(n) == op_Block) &&
 554       (n == get_irg_start_block(current_ir_graph))) {
 555     if ((!interprocedural_view)  ||
 556         (current_ir_graph == outermost_ir_graph))
 557       return true;
 558   }
 559 #endif
 560   return false;
 561 }
 562
 563 /* Don't walk from nodes to blocks except for Control flow operations. */
 564 static INLINE int
 565 get_start_index(ir_node *n) {
 566   if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
 567     return -1;
 568   else
 569     return 0;
 570 }
 571
 572 /* Returns current_ir_graph and set it to the irg of predecessor index
 573    of node n. */
 574 static INLINE ir_graph *
 575 switch_irg (ir_node *n, int index) {
 576   ir_graph *old_current = current_ir_graph;
 577
 578   if (interprocedural_view) {
 579     /* Only Filter and Block nodes can have predecessors in other graphs. */
 580     if (get_irn_op(n) == op_Filter)
 581       n = get_nodes_Block(n);
 582     if (get_irn_op(n) == op_Block) {
 583       ir_node *cfop = skip_Proj(get_Block_cfgpred(n, index));
 584       if (is_ip_cfop(cfop)) {
 585         current_ir_graph = get_irn_irg(cfop);
 586         set_irg_visited(current_ir_graph, get_max_irg_visited());
 587       }
 588     }
 589   }
 590
 591   return old_current;
 592 }
 593
 594 #if 0
 595 /* Walks up the stack passing n and then finding the node
 596    where we walked into the irg n is contained in.
 597    Here we switch the irg. */
 598 static ir_graph *
 599 find_irg_on_stack (ir_node *n) {
 600   ir_node *m;
 601   ir_graph *old_current = current_ir_graph;
 602   int i;
 603
 604   if (interprocedural_view) {
 605     for (i = tos; i >= 0; i--) {
 606       if (stack[i] == n) break;
 607     }
 608     if (i < 0) i = tos;
 609
 610     assert (i >= 0);
 611     for (; i >= 0; i--) {
 612       m = stack[i];
 613       /*printf(" Visiting %d ", i); DDMN(m);*/
 614       if (is_ip_cfop(m)) {
 615         current_ir_graph = get_irn_irg(m);
 616         break;
 617       }
 618       if (get_irn_op(m) == op_Filter) {
 619         /* Find the corresponding ip_cfop */
 620         ir_node *pred = stack[i+1];
 621         int j;
 622         for (j = 0; j < get_Filter_n_cg_preds(m); j++)
 623           if (get_Filter_cg_pred(m, j) == pred) break;
 624         if (j >= get_Filter_n_cg_preds(m))
 625           /* It is a filter we didn't pass as the predecessors are marked. */
 626           continue;
 627         assert(get_Filter_cg_pred(m, j) == pred);
 628         switch_irg(m, j);
 629         break;
 630       }
 631     }
 632   }
 633
 634   return old_current;
 635 }
 636 #endif
 637
 638 #if 0
 639 static void test(ir_node *pred, ir_node *root, ir_node *this) {
 640   int i;
 641   if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
 642
 643   printf("this: %d ", get_irn_uplink(this)); DDMN(this);
 644   printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
 645   printf("root: %d ", get_irn_uplink(root)); DDMN(root);
 646
 647   printf("tos: %d\n", tos);
 648
 649   for (i = tos; i >= 0; i--) {
 650     ir_node *n = stack[i];
 651     if (!n) continue;
 652     printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
 653   }
 654 }
 655 #endif
 656
 657 /* Test for legal loop header: Block, Phi, ... */
 658 INLINE static bool is_possible_loop_head(ir_node *n) {
 659   return ((get_irn_op(n) == op_Block) ||
 660           (get_irn_op(n) == op_Phi) ||
 661           ((get_irn_op(n) == op_Filter) && interprocedural_view));
 662 }
 663
 664 /* Returns true if n is a loop header, i.e., it is a Block, Phi
 665    or Filter node and has predecessors within the loop and out
 666    of the loop.
 667    @arg root: only needed for assertion. */
 668 static bool
 669 is_head (ir_node *n, ir_node *root)
 670 {
 671   int i;
 672   int some_outof_loop = 0, some_in_loop = 0;
 673
 674   /* Test for legal loop header: Block, Phi, ... */
 675   if (!is_possible_loop_head(n))
 676     return false;
 677
 678   if (!is_outermost_Start(n)) {
 679     for (i = get_start_index(n); i < get_irn_arity(n); i++) {
 680       ir_node *pred = get_irn_n(n, i);
 681       assert(pred);
 682       if (is_backedge(n, i)) continue;
 683       if (!irn_is_in_stack(pred)) {
 684         some_outof_loop = 1;
 685       } else {
 686         assert(get_irn_uplink(pred) >= get_irn_uplink(root));
 687         some_in_loop = 1;
 688       }
 689     }
 690   }
 691   return some_outof_loop && some_in_loop;
 692 }
 693
 694 /* Returns index of the predecessor with the smallest dfn number
 695    greater-equal than limit. */
 696 static int
 697 smallest_dfn_pred (ir_node *n, int limit)
 698 {
 699   int i, index = -2, min = -1;
 700
 701   if (!is_outermost_Start(n)) {
 702     for (i = get_start_index(n); i < get_irn_arity(n); i++) {
 703       ir_node *pred = get_irn_n(n, i);
 704       assert(pred);
 705       if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
 706       if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
 707         index = i;
 708         min = get_irn_dfn(pred);
 709       }
 710     }
 711   }
 712   return index;
 713 }
 714
 715 /* Returns index of the predecessor with the largest dfn number. */
 716 static int
 717 largest_dfn_pred (ir_node *n)
 718 {
 719   int i, index = -2, max = -1;
 720
 721   if (!is_outermost_Start(n)) {
 722     for (i = get_start_index(n); i < get_irn_arity(n); i++) {
 723       ir_node *pred = get_irn_n(n, i);
 724       if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
 725       if (get_irn_dfn(pred) > max) {
 726         index = i;
 727         max = get_irn_dfn(pred);
 728       }
 729     }
 730   }
 731   return index;
 732 }
 733
 734 /* Searches the stack for possible loop heads.  Tests these for backedges.
 735    If it finds a head with an unmarked backedge it marks this edge and
 736    returns the tail of the loop.
 737    If it finds no backedge returns NULL.
 738    ("disable_backedge" in fiasco) */
 739
 740 static ir_node *
 741 find_tail (ir_node *n) {
 742   ir_node *m;
 743   int i, res_index = -2;
 744
 745   /*
 746     if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
 747   */
 748
 749   m = stack[tos-1];  /* tos = top of stack */
 750   if (is_head (m, n)) {
 751     res_index = smallest_dfn_pred(m, 0);
 752     if ((res_index == -2) &&  /* no smallest dfn pred found. */
 753         (n == m))
 754       return NULL;
 755   } else {
 756     if (m == n) return NULL;
 757     for (i = tos-2; ; --i) {
 758       m = stack[i];
 759       if (is_head (m, n)) {
 760         res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
 761         if (res_index == -2)  /* no smallest dfn pred found. */
 762           res_index = largest_dfn_pred (m);
 763         break;
 764       }
 765     }
 766   }
 767   assert (res_index > -2);
 768
 769   set_backedge (m, res_index);
 770   return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
 771 }
 772
 773
 774 /* The core algorithm. *****************************************/
 775
 776 static void scc (ir_node *n) {
 777   int i;
 778   // GL @@@ remove experimental stuff ir_graph *rem;
 779
 780   if (irn_visited(n)) return;
 781   mark_irn_visited(n);
 782
 783   /* Initialize the node */
 784   set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
 785   set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
 786   set_irn_loop(n, NULL);
 787   current_dfn ++;
 788
 789   /* What's this good for?
 790   n->ana.scc.section = NULL;
 791   */
 792
 793   push(n);
 794
 795   /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
 796      array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
 797      so is_backedge does not access array[-1] but correctly returns false! */
 798
 799   if (!is_outermost_Start(n)) {
 800     for (i = get_start_index(n); i < get_irn_arity(n); i++) {
 801       ir_node *m;
 802       if (is_backedge(n, i)) continue;
 803
 804       m = get_irn_n(n, i); /*get_irn_ip_pred(n, i);*/
 805       assert(m);
 806       //if ((!m) || (get_irn_op(m) == op_Unknown)) continue;
 807       scc (m);
 808       // GL @@@ remove experimental stuff /*return_recur(n, i);*/
 809
 810       if (irn_is_in_stack(m)) {
 811         /* Uplink of m is smaller if n->m is a backedge.
 812            Propagate the uplink to mark the loop. */
 813         if (get_irn_uplink(m) < get_irn_uplink(n))
 814           set_irn_uplink(n, get_irn_uplink(m));
 815       }
 816     }
 817   }
 818
 819   if (get_irn_dfn(n) == get_irn_uplink(n)) {
 820     /* This condition holds for the node with the incoming backedge.
 821        AS: That is: For the loop head. */
 822     ir_node *tail = find_tail(n);
 823     if (tail) {
 824       /* We found a new inner loop! */
 825
 826       /* This is an adaption of the algorithm from fiasco / optscc to
 827        * avoid loops without Block or Phi as first node.  This should
 828        * severely reduce the number of evaluations of nodes to detect
 829        * a fixpoint in the heap analyses.
 830        * Further it avoids loops without firm nodes that cause errors
 831        * in the heap analyses. */
 832 #define NO_LOOPS_WITHOUT_HEAD 1
 833 #if NO_LOOPS_WITHOUT_HEAD
 834       ir_loop *l;
 835       int close;
 836       if (get_loop_n_elements(current_loop) > 0) {
 837         l = new_loop();
 838         close = 1;
 839       } else {
 840         l = current_loop;
 841         close = 0;
 842       }
 843 #else
 844       ir_loop *l = new_loop();
 845 #endif
 846
 847       /* Remove the loop from the stack ... */
 848       pop_scc_unmark_visit (n);
 849       /* and recompute it in a better order; and so that it goes into
 850          the new loop. */
 851       // GL @@@ remove experimental stuff rem = find_irg_on_stack(tail);
 852
 853       scc (tail);
 854       // GL @@@ remove experimental stuff current_ir_graph = rem;
 855
 856       assert (irn_visited(n));
 857 #if NO_LOOPS_WITHOUT_HEAD
 858       if (close)
 859 #endif
 860       close_loop(l);
 861     } else {
 862       /* AS: No inner loop was found. Pop all nodes from the stack
 863          to the current loop. */
 864       pop_scc_to_loop(n);
 865     }
 866   }
 867 }
 868
 869 /* Constructs backedge information for irg. In interprocedural view constructs
 870    backedges for all methods called by irg, too. */
 871 void construct_backedges(ir_graph *irg) {
 872   ir_graph *rem = current_ir_graph;
 873   ir_loop *head_rem;
 874
 875   assert(!interprocedural_view &&
 876          "not implemented, use construct_ip_backedges");
 877
 878   current_ir_graph = irg;
 879   outermost_ir_graph = irg;
 880
 881   init_scc(current_ir_graph);
 882
 883   current_loop = NULL;
 884   new_loop();  /* sets current_loop */
 885   head_rem = current_loop; /* Just for assertion */
 886
 887   if (interprocedural_view) {
 888     set_irg_visited(current_ir_graph, inc_max_irg_visited());
 889     init_ip_walk ();
 890   } else {
 891     inc_irg_visited(current_ir_graph);
 892   }
 893
 894   scc(get_irg_end(current_ir_graph));
 895
 896   if (interprocedural_view) finish_ip_walk();
 897
 898   assert(head_rem == current_loop);
 899   set_irg_loop(current_ir_graph, current_loop);
 900   assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
 901   /*
 902   irg->loops = current_loop;
 903   if (icfg == 1) {
 904     int count = 0;
 905     int depth = 0;
 906     count_loop (the_loop, &count, &depth);
 907     }
 908   }
 909   */
 910   current_ir_graph = rem;
 911 }
 912
 913
 914 #if 0
 915 void construct_ip_backedges (void) {
 916   ir_graph *rem = current_ir_graph;
 917   int rem_ipv = interprocedural_view;
 918   int i, j;
 919
 920   outermost_ir_graph = get_irp_main_irg();
 921
 922   init_ip_scc();
 923
 924   current_loop = NULL;
 925   new_loop();  /* sets current_loop */
 926   interprocedural_view = 1;
 927
 928   inc_max_irg_visited();
 929   for (i = 0; i < get_irp_n_irgs(); i++)
 930     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
 931
 932   for (i = 0; i < get_irp_n_irgs(); i++) {
 933     ir_node *sb;
 934     current_ir_graph = get_irp_irg(i);
 935     /* Find real entry points */
 936     sb = get_irg_start_block(current_ir_graph);
 937     if ((get_Block_n_cfgpreds(sb) > 1) ||
 938         (get_nodes_Block(get_Block_cfgpred(sb, 0)) != sb)) continue;
 939     /* Compute scc for this graph */
 940     outermost_ir_graph = current_ir_graph;
 941     set_irg_visited(outermost_ir_graph, get_max_irg_visited());
 942     scc(get_irg_end(current_ir_graph));
 943     for (j = 0; j < get_End_n_keepalives(get_irg_end(outermost_ir_graph)); j++)
 944       scc(get_End_keepalive(get_irg_end(outermost_ir_graph), j));
 945   }
 946
 947   set_irg_loop(outermost_ir_graph, current_loop);
 948   assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
 949
 950   current_ir_graph = rem;
 951   interprocedural_view = rem_ipv;
 952 }
 953 #else
 954 void construct_ip_backedges (void) {
 955   ir_graph *rem = current_ir_graph;
 956   int rem_ipv = interprocedural_view;
 957   int i;
 958
 959   outermost_ir_graph = get_irp_main_irg();
 960
 961   init_ip_scc();
 962
 963   current_loop = NULL;
 964   new_loop();  /* sets current_loop */
 965   interprocedural_view = 1;
 966
 967   inc_max_irg_visited();
 968   for (i = 0; i < get_irp_n_irgs(); i++)
 969     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
 970
 971   /** We have to start the walk at the same nodes as cg_walk. **/
 972   /* Walk starting at unreachable procedures. Only these
 973    * have End blocks visible in interprocedural view. */
 974   for (i = 0; i < get_irp_n_irgs(); i++) {
 975     ir_node *sb;
 976     current_ir_graph = get_irp_irg(i);
 977
 978     sb = get_irg_start_block(current_ir_graph);
 979
 980     if ((get_Block_n_cfgpreds(sb) > 1) ||
 981         (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
 982
 983     scc(get_irg_end(current_ir_graph));
 984   }
 985
 986   /* Check whether we walked all procedures: there could be procedures
 987      with cyclic calls but no call from the outside. */
 988   for (i = 0; i < get_irp_n_irgs(); i++) {
 989     ir_node *sb;
 990     current_ir_graph = get_irp_irg(i);
 991
 992     /* Test start block: if inner procedure end and end block are not
 993      * visible and therefore not marked. */
 994     sb = get_irg_start_block(current_ir_graph);
 995     if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
 996   }
 997
 998   /* Walk all endless loops in inner procedures.
 999    * We recognize an inner procedure if the End node is not visited. */
1000   for (i = 0; i < get_irp_n_irgs(); i++) {
1001     ir_node *e;
1002     current_ir_graph = get_irp_irg(i);
1003
1004     e = get_irg_end(current_ir_graph);
1005     if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1006       int j;
1007       /* Don't visit the End node. */
1008       for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1009     }
1010   }
1011
1012   set_irg_loop(outermost_ir_graph, current_loop);
1013   assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1014
1015   current_ir_graph = rem;
1016   interprocedural_view = rem_ipv;
1017 }
1018 #endif
1019
1020 static void reset_backedges(ir_node *n) {
1021   if (is_possible_loop_head(n)) {
1022     int rem = interprocedural_view;
1023     interprocedural_view = 1;
1024     clear_backedges(n);
1025     interprocedural_view = 0;
1026     clear_backedges(n);
1027     interprocedural_view = rem;
1028   }
1029 }
1030
1031 static void loop_reset_backedges(ir_loop *l) {
1032   int i;
1033   reset_backedges(get_loop_node(l, 0));
1034   for (i = 0; i < get_loop_n_sons(l); ++i) {
1035     loop_reset_backedges(get_loop_son(l, i));
1036   }
1037 }
1038
1039 /** Removes all loop information.
1040     Resets all backedges */
1041 void free_loop_information(ir_graph *irg) {
1042   if (get_irg_loop(irg))
1043     loop_reset_backedges(get_irg_loop(irg));
1044   set_irg_loop(irg, NULL);
1045   /* We cannot free the loop nodes, they are on the obstack. */
1046 }
1047
1048
1049 void free_all_loop_information (void) {
1050   int i;
1051   int rem = interprocedural_view;
1052   interprocedural_view = 1;  /* To visit all filter nodes */
1053   for (i = 0; i < get_irp_n_irgs(); i++) {
1054     free_loop_information(get_irp_irg(i));
1055   }
1056   pmap_destroy(node_loop_map);
1057   node_loop_map = NULL;
1058   interprocedural_view = rem;
1059 }
1060
1061
1062
1063
1064
1065 /* Debug stuff *************************************************/
1066
1067 static int test_loop_node(ir_loop *l) {
1068   int i, has_node = 0, found_problem = 0;
1069   loop_element le;
1070   assert(l && l->kind == k_ir_loop);
1071
1072   if (get_loop_n_elements(l) == 0) {
1073     printf(" Loop completely empty! "); DDML(l);
1074     found_problem = 1;
1075     dump_loop(l, "-ha");
1076   }
1077
1078   le = get_loop_element(l, 0);
1079   if (*(le.kind) != k_ir_node) {
1080     assert(le.kind && *(le.kind) == k_ir_loop);
1081     printf(" First loop element is not a node! "); DDML(l);
1082     printf("                                   "); DDML(le.son);
1083
1084     found_problem = 1;
1085     dump_loop(l, "-ha");
1086   }
1087
1088   if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1089     printf(" Wrong node as head! "); DDML(l);
1090     printf("                     "); DDMN(le.node);
1091     found_problem = 1;
1092     dump_loop(l, "-ha");
1093   }
1094
1095   if ((get_loop_depth(l) != 0) &&
1096       (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1097     printf(" Loop head has no backedges! "); DDML(l);
1098     printf("                             "); DDMN(le.node);
1099     found_problem = 1;
1100     dump_loop(l, "-ha");
1101   }
1102
1103   /* Recur */
1104   has_node = 0;
1105   for (i = 0; i < get_loop_n_elements(l); ++i) {
1106     le = get_loop_element(l, i);
1107     if (*(le.kind) == k_ir_node)
1108       has_node++;
1109     else
1110       if (test_loop_node(le.son)) found_problem = 1;
1111   }
1112
1113   if (has_node == 0) {
1114     printf(" Loop has no firm node! "); DDML(l);
1115     found_problem = 1;
1116     dump_loop(l, "-ha");
1117   }
1118
1119   if (get_loop_loop_nr(l) == 11819)
1120     dump_loop(l, "-ha-debug");
1121
1122   return found_problem;
1123 }
1124
1125 /** Prints all loop nodes that
1126  *  - do not have any firm nodes, only loop sons
1127  *  - the header is not a Phi, Block or Filter.
1128  */
1129 void find_strange_loop_nodes(ir_loop *l) {
1130   int found_problem = 0;
1131   printf("\nTesting loop "); DDML(l);
1132   found_problem = test_loop_node(l);
1133   printf("Finished Test\n\n");
1134   if (found_problem) exit(0);
1135
1136 }