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