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
  24 #include "irprog_t.h"
  25 #include "irgraph_t.h"
  26 #include "irnode_t.h"
  27 #include "irgwalk.h"
  28 #include "array.h"
  29 #include "pmap.h"
  30
  31 #include "irdump.h"
  32
  33 /* A variant of the loop tree that avoids loops without head.
  34    This reduces the depth of the loop tree. */
  35 #define NO_LOOPS_WITHOUT_HEAD 1
  36
  37
  38 INLINE void add_loop_son(ir_loop *loop, ir_loop *son);
  39
  40 INLINE void add_loop_node(ir_loop *loop, ir_node *n);
  41
  42 static ir_graph *outermost_ir_graph;      /* The outermost graph the scc is computed
  43                       for */
  44 static ir_loop *current_loop;      /* Current loop construction is working
  45                       on. */
  46 static int loop_node_cnt = 0;      /* Counts the number of allocated loop nodes.
  47                       Each loop node gets a unique number.
  48                       What for? ev. remove. @@@ */
  49 static int current_dfn = 1;        /* Counter to generate depth first numbering
  50                       of visited nodes.  */
  51
  52 void link_to_reg_end (ir_node *n, void *env);
  53 void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
  54 ir_node *get_projx_link(ir_node *cb_projx);
  55
  56 /**********************************************************************/
  57 /* Node attributes                                                   **/
  58 /**********************************************************************/
  59
  60 /**********************************************************************/
  61 /* Node attributes needed for the construction.                      **/
  62 /**********************************************************************/
  63
  64 typedef struct scc_info {
  65   bool in_stack;         /* Marks whether node is on the stack. */
  66   int dfn;               /* Depth first search number. */
  67   int uplink;            /* dfn number of ancestor. */
  68   /*  ir_loop *loop;         *//* Refers to the containing loop. */
  69   /*
  70       struct section *section;
  71       xset def;
  72       xset use;
  73   */
  74 } scc_info;
  75
  76 static INLINE scc_info* new_scc_info(void) {
  77   scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
  78   memset (info, 0, sizeof (scc_info));
  79   return info;
  80 }
  81
  82 static INLINE void
  83 mark_irn_in_stack (ir_node *n) {
  84   assert(get_irn_link(n));
  85   /*  to slow */
  86   /* ((scc_info *)get_irn_link(n))->in_stack = true; */
  87   ((scc_info *)n->link)->in_stack = true;
  88 }
  89
  90 static INLINE void
  91 mark_irn_not_in_stack (ir_node *n) {
  92   assert(get_irn_link(n));
  93   /*  to slow */
  94   /* ((scc_info *)get_irn_link(n))->in_stack = false; */
  95   ((scc_info *)n->link)->in_stack = false;
  96 }
  97
  98 static INLINE bool
  99 irn_is_in_stack (ir_node *n) {
 100   assert(get_irn_link(n));
 101   /*  to slow */
 102   /* return ((scc_info *)get_irn_link(n))->in_stack; */
 103   return ((scc_info *)n->link)->in_stack;
 104 }
 105
 106 static INLINE void
 107 set_irn_uplink (ir_node *n, int uplink) {
 108   assert(get_irn_link(n));
 109   /*  to slow */
 110   /* ((scc_info *)get_irn_link(n))->uplink = uplink; */
 111   ((scc_info *)n->link)->uplink = uplink;
 112 }
 113
 114 INLINE int
 115 get_irn_uplink (ir_node *n) {
 116   assert(get_irn_link(n));
 117   /*  from fast to slow */
 118   /* return ((scc_info *)get_irn_link(n))->uplink; */
 119   return ((scc_info *)n->link)->uplink;
 120 }
 121
 122 static INLINE void
 123 set_irn_dfn (ir_node *n, int dfn) {
 124   assert(get_irn_link(n));
 125   /*  to slow */
 126   /* ((scc_info *)get_irn_link(n))->dfn = dfn; */
 127   ((scc_info *)n->link)->dfn = dfn;
 128 }
 129
 130 INLINE int
 131 get_irn_dfn (ir_node *n) {
 132   assert(get_irn_link(n));
 133   /*  to slow */
 134   /* return ((scc_info *)get_irn_link(n))->dfn; */
 135   return ((scc_info *)n->link)->dfn;
 136 }
 137
 138
 139 INLINE void
 140 set_irn_loop (ir_node *n, ir_loop* loop) {
 141   n->loop = loop;
 142 }
 143
 144 /* Uses temporary information to get the loop */
 145 INLINE ir_loop *
 146 get_irn_loop (ir_node *n) {
 147   return n->loop;
 148 }
 149
 150
 151 #if 0
 152 static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
 153   int i;
 154   ir_loop *res = NULL;
 155
 156   /* Test whether n is contained in this loop. */
 157   for (i = 0; i < get_loop_n_nodes(l); i++)
 158     if (n == get_loop_node(l, i)) return l;
 159
 160   /* Is this a leave in the loop tree? If so loop not found. */
 161   if (get_loop_n_sons(l) == 0) return NULL;
 162
 163   /* Else descend in the loop tree. */
 164   for (i = 0; i < get_loop_n_sons(l); i++) {
 165     res = find_nodes_loop(n, get_loop_son(l, i));
 166     if (res) break;
 167   }
 168   return res;
 169 }
 170
 171 /* @@@ temporary implementation, costly!!! */
 172 ir_loop * get_irn_loop(ir_node *n) {
 173   ir_loop *l = get_irg_loop(current_ir_graph);
 174   l = find_nodes_loop(n, l);
 175   return l;
 176 }
 177 #endif
 178
 179 /**********************************************************************/
 180 /* A stack.                                                          **/
 181 /**********************************************************************/
 182
 183 static ir_node **stack = NULL;
 184 static int tos = 0;                /* top of stack */
 185
 186 static INLINE void init_stack(void) {
 187   if (stack) {
 188     ARR_RESIZE (ir_node *, stack, 1000);
 189   } else {
 190     stack = NEW_ARR_F (ir_node *, 1000);
 191   }
 192   tos = 0;
 193 }
 194
 195 #if 0
 196 static INLINE void free_stack(void) {
 197   DEL_ARR_F(stack);
 198   stack = NULL;
 199   tos = 0;
 200 }
 201 #endif
 202
 203 static INLINE void
 204 push (ir_node *n)
 205 {
 206   /*DDMN(n);*/
 207
 208   if (tos == ARR_LEN (stack)) {
 209     int nlen = ARR_LEN (stack) * 2;
 210     ARR_RESIZE (ir_node *, stack, nlen);
 211   }
 212   stack [tos++] = n;
 213   mark_irn_in_stack(n);
 214 }
 215
 216 static INLINE ir_node *
 217 pop (void)
 218 {
 219   ir_node *n = stack[--tos];
 220   mark_irn_not_in_stack(n);
 221   return n;
 222 }
 223
 224 /* The nodes up to n belong to the current loop.
 225    Removes them from the stack and adds them to the current loop. */
 226 static INLINE void
 227 pop_scc_to_loop (ir_node *n)
 228 {
 229   ir_node *m;
 230   int i = 0;
 231
 232   do {
 233     m = pop();
 234
 235     //printf(" dfn: %d, upl %d upl-new %d ", get_irn_dfn(m), get_irn_uplink(m), loop_node_cnt+1); DDMN(m);
 236
 237     loop_node_cnt++;
 238     set_irn_dfn(m, loop_node_cnt);
 239     add_loop_node(current_loop, m);
 240     set_irn_loop(m, current_loop);
 241     i++;
 242     /*    if (m==n) break;*/
 243   } while(m != n);
 244
 245   /* i might be bigger than 1 for dead (and that's why bad) loops */
 246   /* if(i > 1)
 247     printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!11111\n");
 248    */
 249 }
 250
 251 /* GL ??? my last son is my grandson???  Removes loops with no
 252    ir_nodes in them.  Such loops have only another loop as son. (Why
 253    can't they have two loops as sons? Does it never get that far? ) */
 254 static void close_loop (ir_loop *l)
 255 {
 256   int last = get_loop_n_elements(l) - 1;
 257   loop_element lelement = get_loop_element(l, last);
 258   ir_loop *last_son = lelement.son;
 259
 260   if (get_kind(last_son) == k_ir_loop &&
 261       get_loop_n_elements(last_son) == 1)
 262     {
 263       ir_loop *gson;
 264
 265       lelement = get_loop_element(last_son, 0);
 266       gson = lelement.son;
 267       if(get_kind(gson) == k_ir_loop)
 268     {
 269           loop_element new_last_son;
 270
 271       gson -> outer_loop = l;
 272           new_last_son.son = gson;
 273       l -> children[last] = new_last_son;
 274     }
 275     }
 276
 277   current_loop = l;
 278 }
 279
 280 /* Removes and unmarks all nodes up to n from the stack.
 281    The nodes must be visited once more to assign them to a scc. */
 282 static INLINE void
 283 pop_scc_unmark_visit (ir_node *n)
 284 {
 285   ir_node *m = NULL;
 286
 287   while (m != n) {
 288     m = pop();
 289     set_irn_visited(m, 0);
 290   }
 291 }
 292
 293 /**********************************************************************/
 294 /* The loop datastructure.                                           **/
 295 /**********************************************************************/
 296
 297 /* Allocates a new loop as son of current_loop.  Sets current_loop
 298    to the new loop and returns the father. */
 299 ir_loop *new_loop (void) {
 300   ir_loop *father, *son;
 301
 302   father = current_loop;
 303
 304   son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
 305   memset (son, 0, sizeof (ir_loop));
 306   son->kind = k_ir_loop;
 307   son->children = NEW_ARR_F (loop_element, 0);
 308   son->n_nodes = 0;
 309   son->n_sons=0;
 310   if (father) {
 311     son->outer_loop = father;
 312     add_loop_son(father, son);
 313     son->depth = father->depth+1;
 314   } else {  /* The root loop */
 315     son->outer_loop = son;
 316     son->depth = 0;
 317   }
 318
 319 #ifdef DEBUG_libfirm
 320   son->loop_nr = get_irp_new_node_nr();
 321   son->link = NULL;
 322 #endif
 323
 324   current_loop = son;
 325   return father;
 326 }
 327
 328 #if 0
 329 /* Finishes the datastructures, copies the arrays to the obstack
 330    of current_ir_graph.
 331    A. Schoesser: Caution: loop -> sons is gone. */
 332 static void mature_loop (ir_loop *loop) {
 333   ir_loop **new_sons;
 334
 335   new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
 336   memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
 337   DEL_ARR_F(loop->sons);
 338   loop->sons = new_sons;
 339 }
 340 #endif
 341
 342 /* Returns outer loop, itself if outermost. */
 343 ir_loop *get_loop_outer_loop (ir_loop *loop) {
 344   assert(loop && loop->kind == k_ir_loop);
 345   return loop->outer_loop;
 346 }
 347
 348 /* Returns nesting depth of this loop */
 349 int get_loop_depth (ir_loop *loop) {
 350   assert(loop); assert(loop->kind == k_ir_loop);
 351   return loop->depth;
 352 }
 353
 354 /* Returns the number of inner loops */
 355 int      get_loop_n_sons (ir_loop *loop) {
 356   assert(loop && loop->kind == k_ir_loop);
 357   return(loop -> n_sons);
 358 }
 359
 360 /* Returns the pos`th loop_node-child              *
 361  * TODO: This method isn`t very efficient !        *
 362  * Returns NULL if there isnt`t a pos`th loop_node */
 363 ir_loop *get_loop_son (ir_loop *loop, int pos) {
 364   int child_nr = 0, loop_nr = -1;
 365
 366   assert(loop && loop->kind == k_ir_loop);
 367   while(child_nr < ARR_LEN(loop->children))
 368    {
 369     if(*(loop -> children[child_nr].kind) == k_ir_loop)
 370       loop_nr++;
 371     if(loop_nr == pos)
 372       return(loop -> children[child_nr].son);
 373     child_nr++;
 374    }
 375   return NULL;
 376 }
 377
 378 /* Use EXCLUSIVELY this function to add sons, otherwise the loop->n_sons
 379    is invalid! */
 380
 381 INLINE void
 382 add_loop_son(ir_loop *loop, ir_loop *son) {
 383   loop_element lson;
 384   lson.son = son;
 385   assert(loop && loop->kind == k_ir_loop);
 386   assert(get_kind(son) == k_ir_loop);
 387   ARR_APP1 (loop_element, loop->children, lson);
 388   loop -> n_sons++;
 389 }
 390
 391 /* Returns the number of nodes in the loop */
 392 int      get_loop_n_nodes (ir_loop *loop) {
 393   assert(loop); assert(loop->kind == k_ir_loop);
 394   return loop -> n_nodes;
 395 /*  return ARR_LEN(loop->nodes); */
 396 }
 397
 398 /* Returns the pos`th ir_node-child                *
 399  * TODO: This method isn`t very efficient !        *
 400  * Returns NULL if there isnt`t a pos`th ir_node   */
 401 ir_node *get_loop_node (ir_loop *loop, int pos) {
 402   int child_nr, node_nr = -1;
 403
 404   assert(loop && loop->kind == k_ir_loop);
 405   assert(pos < get_loop_n_nodes(loop));
 406
 407   for (child_nr = 0; child_nr < ARR_LEN(loop->children); child_nr++) {
 408     if(*(loop -> children[child_nr].kind) == k_ir_node)
 409       node_nr++;
 410     if(node_nr == pos)
 411       return(loop -> children[child_nr].node);
 412   }
 413   DDML(loop);
 414   printf("pos: %d\n", pos);
 415   assert(0 && "no child at pos found");
 416   return NULL;
 417 }
 418
 419 /* Use EXCLUSIVELY this function to add nodes, otherwise the loop->n_nodes
 420    is invalid! */
 421
 422 INLINE void
 423 add_loop_node(ir_loop *loop, ir_node *n) {
 424   loop_element ln;
 425   ln.node = n;
 426   assert(loop && loop->kind == k_ir_loop);
 427   assert(get_kind(n) == k_ir_node || get_kind(n) == k_ir_graph);  /* used in callgraph.c */
 428   ARR_APP1 (loop_element, loop->children, ln);
 429   loop->n_nodes++;
 430 }
 431
 432 /** Returns the number of elements contained in loop.  */
 433 int get_loop_n_elements (ir_loop *loop) {
 434   assert(loop && loop->kind == k_ir_loop);
 435   return(ARR_LEN(loop->children));
 436 }
 437
 438 /*
 439  Returns the pos`th loop element.
 440  This may be a loop_node or a ir_node. The caller of this function has
 441  to check the *(loop_element.kind) field for "k_ir_node" or "k_ir_loop"
 442  and then select the apropriate "loop_element.node" or "loop_element.son".
 443 */
 444
 445 loop_element get_loop_element (ir_loop *loop, int pos) {
 446   assert(loop && loop->kind == k_ir_loop && pos < ARR_LEN(loop->children));
 447
 448   return(loop -> children[pos]);
 449 }
 450
 451 int get_loop_element_pos(ir_loop *loop, void *le) {
 452   int i;
 453   assert(loop && loop->kind == k_ir_loop);
 454
 455   for (i = 0; i < get_loop_n_elements(loop); i++)
 456     if (get_loop_element(loop, i).node == le) return i;
 457   return -1;
 458 }
 459
 460 int get_loop_loop_nr(ir_loop *loop) {
 461   assert(loop && loop->kind == k_ir_loop);
 462 #ifdef DEBUG_libfirm
 463   return loop->loop_nr;
 464 #else
 465   return (int)loop;
 466 #endif
 467 }
 468
 469
 470 /** A field to connect additional information to a loop.  Only valid
 471     if libfirm_debug is set. */
 472 void  set_loop_link (ir_loop *loop, void *link) {
 473   assert(loop && loop->kind == k_ir_loop);
 474 #ifdef DEBUG_libfirm
 475   loop->link = link;
 476 #endif
 477 }
 478 void *get_loop_link (const ir_loop *loop) {
 479   assert(loop && loop->kind == k_ir_loop);
 480 #ifdef DEBUG_libfirm
 481   return loop->link;
 482 #else
 483   return NULL;
 484 #endif
 485 }
 486
 487 /* The outermost loop is remarked in the surrounding graph. */
 488 void     set_irg_loop(ir_graph *irg, ir_loop *loop) {
 489   assert(irg);
 490   irg->loop = loop;
 491 }
 492 ir_loop *get_irg_loop(ir_graph *irg) {
 493   assert(irg);
 494   return irg->loop;
 495 }
 496
 497
 498 /**********************************************************************/
 499 /* Constructing and destructing the loop/backedge information.       **/
 500 /**********************************************************************/
 501
 502 /* Initialization steps. **********************************************/
 503
 504 static INLINE void
 505 init_node (ir_node *n, void *env) {
 506   set_irn_link (n, new_scc_info());
 507   clear_backedges(n);
 508 #if 0
 509   /* Also init nodes not visible in intraproc_view. */
 510     /* @@@ init_node is called for too many nodes -- this wastes memory!.
 511        The mem is not lost as its on the obstack. */
 512   if (get_irn_op(n) == op_Filter) {
 513     for (i = 0; i < get_Filter_n_cg_preds(n); i++)
 514       init_node(get_Filter_cg_pred(n, i), NULL);
 515   }
 516   if (get_irn_op(n) == op_Block) {
 517     for (i = 0; i < get_Block_cg_n_cfgpreds(n); i++) {
 518       init_node(get_Block_cg_cfgpred(n, i), NULL);
 519     }
 520   }
 521   /* The following pattern matches only after a call from above pattern. */
 522   if ((get_irn_op(n) == op_Proj) /*&& (get_Proj_proj(n) == 0)*/) {
 523     /* @@@ init_node is called for every proj -- this wastes memory!.
 524        The mem is not lost as its on the obstack. */
 525     ir_node *cb = get_Proj_pred(n);
 526     if ((get_irn_op(cb) == op_CallBegin) ||
 527     (get_irn_op(cb) == op_EndReg) ||
 528     (get_irn_op(cb) == op_EndExcept)) {
 529       init_node(cb, NULL);
 530       init_node(get_nodes_block(cb), NULL);
 531     }
 532   }
 533 #endif
 534 }
 535
 536 static INLINE void
 537 init_scc_common (void) {
 538   current_dfn = 1;
 539   loop_node_cnt = 0;
 540   init_stack();
 541 }
 542
 543 static INLINE void
 544 init_scc (ir_graph *irg) {
 545   init_scc_common();
 546   irg_walk_graph (irg, init_node, NULL, NULL);
 547   /*
 548   irg_walk (irg, link_to_reg_end, NULL, NULL);
 549   */
 550 }
 551
 552 static INLINE void
 553 init_ip_scc (void) {
 554   init_scc_common();
 555   cg_walk (init_node, NULL, NULL);
 556
 557 #if EXPERIMENTAL_LOOP_TREE
 558   cg_walk (link_to_reg_end, NULL, NULL);
 559 #endif
 560 }
 561
 562 /* Condition for breaking the recursion. */
 563 static bool is_outermost_Start(ir_node *n) {
 564   /* Test whether this is the outermost Start node.  If so
 565      recursion must end. */
 566   if ((get_irn_op(n) == op_Block)     &&
 567       (get_Block_n_cfgpreds(n) == 1)  &&
 568       (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
 569       (get_nodes_block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
 570     return true;
 571   }
 572 #if 0
 573   /*  @@@ Bad condition:
 574       not possible in interprocedural view as outermost_graph is
 575       not necessarily the only with a dead-end start block.
 576       Besides current_ir_graph is not set properly. */
 577   if ((get_irn_op(n) == op_Block) &&
 578       (n == get_irg_start_block(current_ir_graph))) {
 579     if ((!interprocedural_view)  ||
 580     (current_ir_graph == outermost_ir_graph))
 581       return true;
 582   }
 583 #endif
 584   return false;
 585 }
 586
 587 /* When to walk from nodes to blocks. Only for Control flow operations? */
 588 static INLINE int
 589 get_start_index(ir_node *n) {
 590 #undef BLOCK_BEFORE_NODE
 591 #define BLOCK_BEFORE_NODE 1
 592
 593 #if BLOCK_BEFORE_NODE
 594
 595   /* This version assures, that all nodes are ordered absolutely.  This allows
 596      to undef all nodes in the heap analysis if the block is false, which means
 597      not reachable.
 598      I.e., with this code, the order on the loop tree is correct. But a (single)
 599      test showed the loop tree is deeper.   */
 600   if (get_irn_op(n) == op_Phi   ||
 601       get_irn_op(n) == op_Block ||
 602       (get_irn_op(n) == op_Filter && interprocedural_view) ||
 603       (get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
 604        get_op_pinned(get_irn_op(n)) == op_pin_state_floats))
 605     // Here we could test for backedge at -1 which is illegal
 606     return 0;
 607   else
 608     return -1;
 609
 610 #else
 611
 612   /* This version causes deeper loop trees (at least we verified this
 613      for Polymor).
 614      But it guarantees that Blocks are analysed before nodes contained in the
 615      block.  If so, we can set the value to undef if the block is not \
 616      executed. */
 617    if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
 618      return -1;
 619    else
 620      return 0;
 621
 622 #endif
 623 }
 624
 625
 626 #if 0
 627 static void test(ir_node *pred, ir_node *root, ir_node *this) {
 628   int i;
 629   if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
 630
 631   printf("this: %d ", get_irn_uplink(this)); DDMN(this);
 632   printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
 633   printf("root: %d ", get_irn_uplink(root)); DDMN(root);
 634
 635   printf("tos: %d\n", tos);
 636
 637   for (i = tos; i >= 0; i--) {
 638     ir_node *n = stack[i];
 639     if (!n) continue;
 640     printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
 641   }
 642 }
 643 #endif
 644
 645 /* Test for legal loop header: Block, Phi, ... */
 646 INLINE static bool is_possible_loop_head(ir_node *n) {
 647   ir_op *op = get_irn_op(n);
 648   return ((op == op_Block) ||
 649           (op == op_Phi) ||
 650           ((op == op_Filter) && interprocedural_view));
 651 }
 652
 653 /* Returns true if n is a loop header, i.e., it is a Block, Phi
 654    or Filter node and has predecessors within the loop and out
 655    of the loop.
 656    @arg root: only needed for assertion. */
 657 static bool
 658 is_head (ir_node *n, ir_node *root)
 659 {
 660   int i, arity;
 661   int some_outof_loop = 0, some_in_loop = 0;
 662
 663   /* Test for legal loop header: Block, Phi, ... */
 664   if (!is_possible_loop_head(n))
 665     return false;
 666
 667   if (!is_outermost_Start(n)) {
 668     arity = get_irn_arity(n);
 669     for (i = get_start_index(n); i < arity; i++) {
 670       ir_node *pred = get_irn_n(n, i);
 671       assert(pred);
 672       if (is_backedge(n, i)) continue;
 673       if (!irn_is_in_stack(pred)) {
 674         some_outof_loop = 1;
 675       } else {
 676         if(get_irn_uplink(pred) < get_irn_uplink(root)) {
 677           DDMN(n); DDMN(pred); DDMN(root);
 678           assert(get_irn_uplink(pred) >= get_irn_uplink(root));
 679         }
 680         some_in_loop = 1;
 681       }
 682     }
 683   }
 684   return some_outof_loop && some_in_loop;
 685 }
 686
 687 /* Returns true if n is possible loop head of an endless loop.
 688    I.e., it is a Block, Phi or Filter node and has only predecessors
 689    within the loop.
 690    @arg root: only needed for assertion. */
 691 static bool
 692 is_endless_head (ir_node *n, ir_node *root)
 693 {
 694   int i, arity;
 695   int some_outof_loop = 0, some_in_loop = 0;
 696
 697   /* Test for legal loop header: Block, Phi, ... */
 698   if (!is_possible_loop_head(n))
 699     return false;
 700
 701   if (!is_outermost_Start(n)) {
 702     arity = get_irn_arity(n);
 703     for (i = get_start_index(n); i < arity; i++) {
 704       ir_node *pred = get_irn_n(n, i);
 705       assert(pred);
 706       if (is_backedge(n, i)) { continue; }
 707       if (!irn_is_in_stack(pred)) {
 708         some_outof_loop = 1; //printf(" some out of loop ");
 709       } else {
 710         if(get_irn_uplink(pred) < get_irn_uplink(root)) {
 711           DDMN(pred); DDMN(root);
 712           assert(get_irn_uplink(pred) >= get_irn_uplink(root));
 713         }
 714         some_in_loop = 1;
 715       }
 716     }
 717   }
 718   return !some_outof_loop && some_in_loop;
 719 }
 720
 721 /* Returns index of the predecessor with the smallest dfn number
 722    greater-equal than limit. */
 723 static int
 724 smallest_dfn_pred (ir_node *n, int limit)
 725 {
 726   int i, index = -2, min = -1;
 727
 728   if (!is_outermost_Start(n)) {
 729     int arity = get_irn_arity(n);
 730     for (i = get_start_index(n); i < arity; i++) {
 731       ir_node *pred = get_irn_n(n, i);
 732       assert(pred);
 733       if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
 734       if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
 735         index = i;
 736         min = get_irn_dfn(pred);
 737       }
 738     }
 739   }
 740   return index;
 741 }
 742
 743 /* Returns index of the predecessor with the largest dfn number. */
 744 static int
 745 largest_dfn_pred (ir_node *n)
 746 {
 747   int i, index = -2, max = -1;
 748
 749   if (!is_outermost_Start(n)) {
 750     int arity = get_irn_arity(n);
 751     for (i = get_start_index(n); i < arity; i++) {
 752       ir_node *pred = get_irn_n(n, i);
 753       if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
 754       if (get_irn_dfn(pred) > max) {
 755         index = i;
 756         max = get_irn_dfn(pred);
 757       }
 758     }
 759   }
 760   return index;
 761 }
 762
 763 /** Searches the stack for possible loop heads.  Tests these for backedges.
 764     If it finds a head with an unmarked backedge it marks this edge and
 765     returns the tail of the loop.
 766     If it finds no backedge returns NULL.
 767     ("disable_backedge" in fiasco)
 768 *
 769 *  @param n  A node where uplink == dfn.
 770 **/
 771
 772 static ir_node *
 773 find_tail (ir_node *n) {
 774   ir_node *m;
 775   int i, res_index = -2;
 776
 777   /*
 778     if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
 779   */
 780   m = stack[tos-1];  /* tos = top of stack */
 781   if (is_head (m, n)) {
 782     res_index = smallest_dfn_pred(m, 0);
 783     if ((res_index == -2) &&  /* no smallest dfn pred found. */
 784     (n ==  m))
 785       return NULL;
 786   } else {
 787     if (m == n) return NULL;    // Is this to catch Phi - self loops?
 788     for (i = tos-2; i >= 0; --i) {
 789       m = stack[i];
 790
 791       if (is_head (m, n)) {
 792         res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
 793         if (res_index == -2)  /* no smallest dfn pred found. */
 794           res_index = largest_dfn_pred (m);
 795
 796         if ((m == n) && (res_index == -2)) {  /* dont walk past loop head. */
 797           i = -1;
 798         }
 799         break;
 800       }
 801
 802       /* We should not walk past our selves on the stack:  The upcoming nodes
 803          are not in this loop. We assume a loop not reachable from Start. */
 804       if (m == n) {
 805         i = -1;
 806         break;
 807       }
 808
 809     }
 810
 811     if (i < 0) {
 812       /* A dead loop not reachable from Start. */
 813       for (i = tos-2; i >= 0; --i) {
 814         m = stack[i];
 815         if (is_endless_head (m, n)) {
 816           res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
 817           if (res_index == -2)  /* no smallest dfn pred found. */
 818             res_index = largest_dfn_pred (m);
 819           break;
 820         }
 821         if (m == n) { break; }  /* It's not an unreachable loop, either. */
 822       }
 823       //assert(0 && "no head found on stack");
 824     }
 825
 826   }
 827   if (res_index <= -2) {
 828     /* It's a completely bad loop: without Phi/Block nodes that can
 829        be a head. I.e., the code is "dying".  We break the loop by
 830        setting Bad nodes. */
 831     int arity = get_irn_arity(n);
 832     for (i = -1; i < arity; ++i) {
 833       set_irn_n(n, i, get_irg_bad(get_irn_irg(n)));
 834     }
 835     return NULL;
 836   }
 837   assert (res_index > -2);
 838
 839   set_backedge (m, res_index);
 840   return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
 841 }
 842
 843
 844 #if EXPERIMENTAL_LOOP_TREE
 845
 846 /*  ----------------------------------------------------------------
 847     AS:  This is experimantal code to build loop trees suitable for
 848     the heap analysis. Does not work correctly right now... :-(
 849
 850
 851     Search in stack for the corresponding first Call-End-ProjX that
 852     corresponds to one of the control flow predecessors of the given
 853     block, that is the possible callers.
 854     returns: the control predecessor to chose\
 855     or       -1 if no corresponding Call-End-Node could be found
 856              on the stack.
 857     - -------------------------------------------------------------- */
 858
 859 int search_endproj_in_stack(ir_node *start_block)
 860 {
 861   int i, j;
 862   assert(is_Block(start_block));
 863   for(i = tos - 1; i >= 0; --i)
 864     {
 865       DDMN(stack[i]);
 866       if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
 867          get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
 868         {
 869           printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
 870           ir_node *end_projx = stack[i];
 871
 872           int arity = get_irn_arity(start_block);
 873           for(j = 0; j < arity; j++)
 874             {
 875               ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
 876                                                        get_Proj_proj(end_projx));
 877               DDMN(begin_projx);
 878               if(get_irn_n(start_block, j) == begin_projx)
 879                 {
 880                   printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
 881                   return(j);
 882                 }
 883             }
 884         }
 885     }
 886   return(-1);
 887 }
 888
 889
 890 static pmap *projx_link = NULL;
 891
 892 void link_to_reg_end (ir_node *n, void *env) {
 893   if(get_irn_op(n) == op_Proj &&
 894      get_irn_mode(n) == mode_X &&
 895      get_irn_op(get_irn_n(n, 0)) == op_EndReg) {
 896       /* Reg End Projx -> Find the CallBegin Projx and hash it */
 897       ir_node *end_projx = n;
 898       ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
 899                                                get_Proj_proj(end_projx));
 900       printf("Linked the following ProjxNodes:\n");
 901       DDMN(begin_projx);
 902       DDMN(end_projx);
 903       set_projx_link(begin_projx, end_projx);
 904     }
 905 }
 906
 907 void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
 908 {
 909   if(projx_link == NULL)
 910     projx_link = pmap_create();
 911   pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
 912 }
 913
 914 ir_node *get_projx_link(ir_node *cb_projx)
 915 {
 916   return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
 917 }
 918
 919 #endif
 920
 921 INLINE static int
 922 is_outermost_loop(ir_loop *l) {
 923   return l == get_loop_outer_loop(l);
 924 }
 925
 926
 927 /*-----------------------------------------------------------*
 928  *                   The core algorithm.                     *
 929  *-----------------------------------------------------------*/
 930
 931
 932 static void scc (ir_node *n) {
 933   int i;
 934   if (irn_visited(n)) return;
 935   mark_irn_visited(n);
 936
 937   /* Initialize the node */
 938   set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
 939   set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
 940   set_irn_loop(n, NULL);
 941   current_dfn ++;
 942   push(n);
 943
 944   /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
 945      array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
 946      so is_backedge does not access array[-1] but correctly returns false! */
 947
 948   if (!is_outermost_Start(n)) {
 949     int arity = get_irn_arity(n);
 950
 951     for (i = get_start_index(n); i < arity; i++) {
 952       ir_node *m;
 953       if (is_backedge(n, i)) continue;
 954       m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
 955       /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
 956       scc (m);
 957       if (irn_is_in_stack(m)) {
 958         /* Uplink of m is smaller if n->m is a backedge.
 959            Propagate the uplink to mark the loop. */
 960         if (get_irn_uplink(m) < get_irn_uplink(n))
 961           set_irn_uplink(n, get_irn_uplink(m));
 962       }
 963     }
 964   }
 965
 966   if (get_irn_dfn(n) == get_irn_uplink(n)) {
 967     /* This condition holds for
 968        1) the node with the incoming backedge.
 969           That is: We found a loop!
 970        2) Straight line code, because no uplink has been propagated, so the
 971           uplink still is the same as the dfn.
 972
 973        But n might not be a proper loop head for the analysis. Proper loop
 974        heads are Block and Phi nodes. find_tail searches the stack for
 975        Block's and Phi's and takes those nodes as loop heads for the current
 976        loop instead and marks the incoming edge as backedge. */
 977
 978     ir_node *tail = find_tail(n);
 979     if (tail) {
 980       /* We have a loop, that is no straight line code,
 981          because we found a loop head!
 982          Next actions: Open a new loop on the loop tree and
 983                        try to find inner loops */
 984
 985 #if NO_LOOPS_WITHOUT_HEAD
 986       /* This is an adaption of the algorithm from fiasco / optscc to
 987        * avoid loops without Block or Phi as first node.  This should
 988        * severely reduce the number of evaluations of nodes to detect
 989        * a fixpoint in the heap analysis.
 990        * Further it avoids loops without firm nodes that cause errors
 991        * in the heap analyses.
 992        * But attention:  don't do it for the outermost loop:  This loop
 993        * is not iterated.  A first block can be a loop head in case of
 994        * an endless recursion. */
 995
 996       ir_loop *l;
 997       int close;
 998       if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
 999         l = new_loop();
1000         close = 1;
1001       } else {
1002         l = current_loop;
1003         close = 0;
1004       }
1005 #else
1006       ir_loop *l = new_loop();
1007 #endif
1008
1009       /* Remove the loop from the stack ... */
1010       pop_scc_unmark_visit (n);
1011
1012       /* The current backedge has been marked, that is temporarily eliminated,
1013          by find tail. Start the scc algorithm
1014          anew on the subgraph thats left (the current loop without the backedge)
1015          in order to find more inner loops. */
1016       scc (tail);
1017
1018       assert (irn_visited(n));
1019 #if NO_LOOPS_WITHOUT_HEAD
1020       if (close)
1021 #endif
1022         close_loop(l);
1023     }
1024     else
1025       {
1026         /* No loop head was found, that is we have straightline code.
1027            Pop all nodes from the stack to the current loop. */
1028       pop_scc_to_loop(n);
1029     }
1030   }
1031 }
1032
1033 static void my_scc (ir_node *n) {
1034   int i;
1035   if (irn_visited(n)) return;
1036   mark_irn_visited(n);
1037
1038   /* Initialize the node */
1039   set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
1040   set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
1041   set_irn_loop(n, NULL);
1042   current_dfn ++;
1043   push(n);
1044
1045   /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
1046      array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
1047      so is_backedge does not access array[-1] but correctly returns false! */
1048
1049   if (!is_outermost_Start(n)) {
1050     int arity = get_irn_arity(n);
1051
1052     for (i = get_start_index(n); i < arity; i++) {
1053       ir_node *m;
1054       if (is_backedge(n, i)) continue;
1055       m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
1056       /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
1057       my_scc (m);
1058       if (irn_is_in_stack(m)) {
1059         /* Uplink of m is smaller if n->m is a backedge.
1060            Propagate the uplink to mark the loop. */
1061         if (get_irn_uplink(m) < get_irn_uplink(n))
1062           set_irn_uplink(n, get_irn_uplink(m));
1063       }
1064     }
1065   }
1066
1067   if (get_irn_dfn(n) == get_irn_uplink(n)) {
1068     /* This condition holds for
1069        1) the node with the incoming backedge.
1070           That is: We found a loop!
1071        2) Straight line code, because no uplink has been propagated, so the
1072           uplink still is the same as the dfn.
1073
1074        But n might not be a proper loop head for the analysis. Proper loop
1075        heads are Block and Phi nodes. find_tail searches the stack for
1076        Block's and Phi's and takes those nodes as loop heads for the current
1077        loop instead and marks the incoming edge as backedge. */
1078
1079     ir_node *tail = find_tail(n);
1080     if (tail) {
1081       /* We have a loop, that is no straight line code,
1082          because we found a loop head!
1083          Next actions: Open a new loop on the loop tree and
1084                        try to find inner loops */
1085
1086 #if NO_LOOPS_WITHOUT_HEAD
1087       /* This is an adaption of the algorithm from fiasco / optscc to
1088        * avoid loops without Block or Phi as first node.  This should
1089        * severely reduce the number of evaluations of nodes to detect
1090        * a fixpoint in the heap analysis.
1091        * Further it avoids loops without firm nodes that cause errors
1092        * in the heap analyses. */
1093
1094       ir_loop *l;
1095       int close;
1096       if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
1097         l = new_loop();
1098         close = 1;
1099       } else {
1100         l = current_loop;
1101         close = 0;
1102       }
1103 #else
1104       ir_loop *l = new_loop();
1105 #endif
1106
1107       /* Remove the loop from the stack ... */
1108       pop_scc_unmark_visit (n);
1109
1110       /* The current backedge has been marked, that is temporarily eliminated,
1111          by find tail. Start the scc algorithm
1112          anew on the subgraph thats left (the current loop without the backedge)
1113          in order to find more inner loops. */
1114       my_scc (tail);
1115
1116       assert (irn_visited(n));
1117 #if NO_LOOPS_WITHOUT_HEAD
1118       if (close)
1119 #endif
1120         close_loop(l);
1121     }
1122     else
1123       {
1124         /* No loop head was found, that is we have straightline code.
1125            Pop all nodes from the stack to the current loop. */
1126       pop_scc_to_loop(n);
1127     }
1128   }
1129 }
1130
1131 /* Constructs backedge information for irg. In interprocedural view constructs
1132    backedges for all methods called by irg, too. */
1133 void construct_backedges(ir_graph *irg) {
1134   ir_graph *rem = current_ir_graph;
1135   ir_loop *head_rem;
1136
1137   assert(!interprocedural_view &&
1138      "not implemented, use construct_ip_backedges");
1139
1140   current_ir_graph   = irg;
1141   outermost_ir_graph = irg;
1142
1143   init_scc(current_ir_graph);
1144
1145   current_loop = NULL;
1146   new_loop();  /* sets current_loop */
1147   head_rem = current_loop; /* Just for assertion */
1148
1149   inc_irg_visited(current_ir_graph);
1150
1151   scc(get_irg_end(current_ir_graph));
1152
1153   assert(head_rem == current_loop);
1154   set_irg_loop(current_ir_graph, current_loop);
1155   set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
1156   assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
1157   /*
1158   irg->loops = current_loop;
1159   if (icfg == 1) {
1160     int count = 0;
1161     int depth = 0;
1162     count_loop (the_loop, &count, &depth);
1163     }
1164   }
1165   */
1166   current_ir_graph = rem;
1167 }
1168
1169
1170 #if 0
1171 void construct_ip_backedges (void) {
1172   ir_graph *rem = current_ir_graph;
1173   int rem_ipv = interprocedural_view;
1174   int i, j;
1175
1176   outermost_ir_graph = get_irp_main_irg();
1177
1178   init_ip_scc();
1179
1180   current_loop = NULL;
1181   new_loop();  /* sets current_loop */
1182   interprocedural_view = 1;
1183
1184   inc_max_irg_visited();
1185   for (i = 0; i < get_irp_n_irgs(); i++)
1186     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1187
1188   for (i = 0; i < get_irp_n_irgs(); i++) {
1189     ir_node *sb;
1190     current_ir_graph = get_irp_irg(i);
1191     /* Find real entry points */
1192     sb = get_irg_start_block(current_ir_graph);
1193     if ((get_Block_n_cfgpreds(sb) > 1) ||
1194     (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1195     /* Compute scc for this graph */
1196     outermost_ir_graph = current_ir_graph;
1197     set_irg_visited(outermost_ir_graph, get_max_irg_visited());
1198     scc(get_irg_end(current_ir_graph));
1199     for (j = 0; j < get_End_n_keepalives(get_irg_end(outermost_ir_graph)); j++)
1200       scc(get_End_keepalive(get_irg_end(outermost_ir_graph), j));
1201   }
1202
1203   set_irg_loop(outermost_ir_graph, current_loop);
1204   set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1205   assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1206
1207   current_ir_graph = rem;
1208   interprocedural_view = rem_ipv;
1209 }
1210 #else
1211 void construct_ip_backedges (void) {
1212   ir_graph *rem = current_ir_graph;
1213   int rem_ipv = interprocedural_view;
1214   int i;
1215
1216   assert(get_irp_ip_view_state() == ip_view_valid);
1217
1218   outermost_ir_graph = get_irp_main_irg();
1219
1220   init_ip_scc();
1221
1222   current_loop = NULL;
1223   new_loop();  /* sets current_loop */
1224   interprocedural_view = 1;
1225
1226   inc_max_irg_visited();
1227   for (i = 0; i < get_irp_n_irgs(); i++)
1228     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1229
1230   /** We have to start the walk at the same nodes as cg_walk. **/
1231   /* Walk starting at unreachable procedures. Only these
1232    * have End blocks visible in interprocedural view. */
1233   for (i = 0; i < get_irp_n_irgs(); i++) {
1234     ir_node *sb;
1235     current_ir_graph = get_irp_irg(i);
1236
1237     sb = get_irg_start_block(current_ir_graph);
1238
1239     if ((get_Block_n_cfgpreds(sb) > 1) ||
1240     (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1241
1242     scc(get_irg_end(current_ir_graph));
1243   }
1244
1245   /* Check whether we walked all procedures: there could be procedures
1246      with cyclic calls but no call from the outside. */
1247   for (i = 0; i < get_irp_n_irgs(); i++) {
1248     ir_node *sb;
1249     current_ir_graph = get_irp_irg(i);
1250
1251     /* Test start block: if inner procedure end and end block are not
1252      * visible and therefore not marked. */
1253     sb = get_irg_start_block(current_ir_graph);
1254     if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1255   }
1256
1257   /* Walk all endless loops in inner procedures.
1258    * We recognize an inner procedure if the End node is not visited. */
1259   for (i = 0; i < get_irp_n_irgs(); i++) {
1260     ir_node *e;
1261     current_ir_graph = get_irp_irg(i);
1262
1263     e = get_irg_end(current_ir_graph);
1264     if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1265       int j;
1266       /* Don't visit the End node. */
1267       for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1268     }
1269   }
1270
1271   set_irg_loop(outermost_ir_graph, current_loop);
1272   set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1273   assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1274
1275   current_ir_graph = rem;
1276   interprocedural_view = rem_ipv;
1277 }
1278 #endif
1279 void my_construct_ip_backedges (void) {
1280   ir_graph *rem = current_ir_graph;
1281   int rem_ipv = interprocedural_view;
1282   int i;
1283
1284   assert(get_irp_ip_view_state() == ip_view_valid);
1285
1286   outermost_ir_graph = get_irp_main_irg();
1287
1288   init_ip_scc();
1289
1290   current_loop = NULL;
1291   new_loop();  /* sets current_loop */
1292   interprocedural_view = 1;
1293
1294   inc_max_irg_visited();
1295   for (i = 0; i < get_irp_n_irgs(); i++)
1296     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1297
1298   /** We have to start the walk at the same nodes as cg_walk. **/
1299   /* Walk starting at unreachable procedures. Only these
1300    * have End blocks visible in interprocedural view. */
1301   for (i = 0; i < get_irp_n_irgs(); i++) {
1302     ir_node *sb;
1303     current_ir_graph = get_irp_irg(i);
1304
1305     sb = get_irg_start_block(current_ir_graph);
1306
1307     if ((get_Block_n_cfgpreds(sb) > 1) ||
1308     (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1309
1310     my_scc(get_irg_end(current_ir_graph));
1311   }
1312
1313   /* Check whether we walked all procedures: there could be procedures
1314      with cyclic calls but no call from the outside. */
1315   for (i = 0; i < get_irp_n_irgs(); i++) {
1316     ir_node *sb;
1317     current_ir_graph = get_irp_irg(i);
1318
1319     /* Test start block: if inner procedure end and end block are not
1320      * visible and therefore not marked. */
1321     sb = get_irg_start_block(current_ir_graph);
1322     if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1323   }
1324
1325   /* Walk all endless loops in inner procedures.
1326    * We recognize an inner procedure if the End node is not visited. */
1327   for (i = 0; i < get_irp_n_irgs(); i++) {
1328     ir_node *e;
1329     current_ir_graph = get_irp_irg(i);
1330
1331     e = get_irg_end(current_ir_graph);
1332     if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1333       int j;
1334       /* Don't visit the End node. */
1335       for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1336     }
1337   }
1338
1339   set_irg_loop(outermost_ir_graph, current_loop);
1340   set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1341   assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1342
1343   current_ir_graph = rem;
1344   interprocedural_view = rem_ipv;
1345 }
1346
1347 static void reset_backedges(ir_node *n) {
1348   if (is_possible_loop_head(n)) {
1349     int rem = interprocedural_view;
1350     interprocedural_view = 1;
1351     clear_backedges(n);
1352     interprocedural_view = 0;
1353     clear_backedges(n);
1354     interprocedural_view = rem;
1355   }
1356 }
1357
1358
1359 /*
1360 static void loop_reset_backedges(ir_loop *l) {
1361   int i;
1362   reset_backedges(get_loop_node(l, 0));
1363   for (i = 0; i < get_loop_n_nodes(l); ++i)
1364     set_irn_loop(get_loop_node(l, i), NULL);
1365   for (i = 0; i < get_loop_n_sons(l); ++i) {
1366     loop_reset_backedges(get_loop_son(l, i));
1367   }
1368 }
1369 */
1370
1371 static void loop_reset_node(ir_node *n, void *env) {
1372   set_irn_loop(n, NULL);
1373   reset_backedges(n);
1374 }
1375
1376
1377 /** Removes all loop information.
1378     Resets all backedges */
1379 void free_loop_information(ir_graph *irg) {
1380   /* We can not use this recursion, as the loop might contain
1381      illegal nodes by now.  Why else would we throw away the
1382      representation?
1383   if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1384   */
1385   irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1386   set_irg_loop(irg, NULL);
1387   set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1388   /* We cannot free the loop nodes, they are on the obstack. */
1389 }
1390
1391
1392 void free_all_loop_information (void) {
1393   int i;
1394   int rem = interprocedural_view;
1395   interprocedural_view = 1;  /* To visit all filter nodes */
1396   for (i = 0; i < get_irp_n_irgs(); i++) {
1397     free_loop_information(get_irp_irg(i));
1398   }
1399   interprocedural_view = rem;
1400 }
1401
1402
1403
1404
1405
1406 /* Debug stuff *************************************************/
1407
1408 static int test_loop_node(ir_loop *l) {
1409   int i, has_node = 0, found_problem = 0;
1410   loop_element le;
1411
1412   assert(l && l->kind == k_ir_loop);
1413
1414   if (get_loop_n_elements(l) == 0) {
1415     printf(" Loop completely empty! "); DDML(l);
1416     found_problem = 1;
1417     dump_loop(l, "-ha");
1418   }
1419
1420   le = get_loop_element(l, 0);
1421   if (*(le.kind) != k_ir_node) {
1422     assert(le.kind && *(le.kind) == k_ir_loop);
1423     printf(" First loop element is not a node! "); DDML(l);
1424     printf("                                   "); DDML(le.son);
1425
1426     found_problem = 1;
1427     dump_loop(l, "-ha");
1428   }
1429
1430   if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1431     printf(" Wrong node as head! "); DDML(l);
1432     printf("                     "); DDMN(le.node);
1433     found_problem = 1;
1434     dump_loop(l, "-ha");
1435   }
1436
1437   if ((get_loop_depth(l) != 0) &&
1438       (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1439     printf(" Loop head has no backedges! "); DDML(l);
1440     printf("                             "); DDMN(le.node);
1441     found_problem = 1;
1442     dump_loop(l, "-ha");
1443   }
1444
1445   /* Recur */
1446   has_node = 0;
1447   for (i = 0; i < get_loop_n_elements(l); ++i) {
1448     le = get_loop_element(l, i);
1449     if (*(le.kind) == k_ir_node)
1450       has_node++;
1451     else
1452       if (test_loop_node(le.son)) found_problem = 1;
1453   }
1454
1455   if (has_node == 0) {
1456     printf(" Loop has no firm node! "); DDML(l);
1457     found_problem = 1;
1458     dump_loop(l, "-ha");
1459   }
1460
1461   if (get_loop_loop_nr(l) == 11819)
1462     dump_loop(l, "-ha-debug");
1463
1464   return found_problem;
1465 }
1466
1467 /** Prints all loop nodes that
1468  *  - do not have any firm nodes, only loop sons
1469  *  - the header is not a Phi, Block or Filter.
1470  */
1471 void find_strange_loop_nodes(ir_loop *l) {
1472   int found_problem = 0;
1473   printf("\nTesting loop "); DDML(l);
1474   found_problem = test_loop_node(l);
1475   printf("Finished Test\n\n");
1476   if (found_problem) exit(0);
1477
1478 }