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