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 int is_ir_loop(const void *thing) {
 491   return (get_kind(thing) == k_ir_loop);
 492 }
 493
 494 /* The outermost loop is remarked in the surrounding graph. */
 495 void     set_irg_loop(ir_graph *irg, ir_loop *loop) {
 496   assert(irg);
 497   irg->loop = loop;
 498 }
 499 ir_loop *get_irg_loop(ir_graph *irg) {
 500   assert(irg);
 501   return irg->loop;
 502 }
 503
 504
 505 /**********************************************************************/
 506 /* Constructing and destructing the loop/backedge information.       **/
 507 /**********************************************************************/
 508
 509 /* Initialization steps. **********************************************/
 510
 511 static INLINE void
 512 init_node (ir_node *n, void *env) {
 513   set_irn_link (n, new_scc_info());
 514   clear_backedges(n);
 515 }
 516
 517 static INLINE void
 518 init_scc_common (void) {
 519   current_dfn = 1;
 520   loop_node_cnt = 0;
 521   init_stack();
 522 }
 523
 524 static INLINE void
 525 init_scc (ir_graph *irg) {
 526   init_scc_common();
 527   irg_walk_graph (irg, init_node, NULL, NULL);
 528   /*
 529   irg_walk (irg, link_to_reg_end, NULL, NULL);
 530   */
 531 }
 532
 533 static INLINE void
 534 init_ip_scc (void) {
 535   init_scc_common();
 536   cg_walk (init_node, NULL, NULL);
 537
 538 #if EXPERIMENTAL_LOOP_TREE
 539   cg_walk (link_to_reg_end, NULL, NULL);
 540 #endif
 541 }
 542
 543 /* Condition for breaking the recursion. */
 544 static bool is_outermost_Start(ir_node *n) {
 545   /* Test whether this is the outermost Start node.  If so
 546      recursion must end. */
 547   if ((get_irn_op(n) == op_Block)     &&
 548       (get_Block_n_cfgpreds(n) == 1)  &&
 549       (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
 550       (get_nodes_block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
 551     return true;
 552   }
 553 #if 0
 554   /*  @@@ Bad condition:
 555       not possible in interprocedural view as outermost_graph is
 556       not necessarily the only with a dead-end start block.
 557       Besides current_ir_graph is not set properly. */
 558   if ((get_irn_op(n) == op_Block) &&
 559       (n == get_irg_start_block(current_ir_graph))) {
 560     if ((!get_interprocedural_view())  ||
 561     (current_ir_graph == outermost_ir_graph))
 562       return true;
 563   }
 564 #endif
 565   return false;
 566 }
 567
 568 /* When to walk from nodes to blocks. Only for Control flow operations? */
 569 static INLINE int
 570 get_start_index(ir_node *n) {
 571 #undef BLOCK_BEFORE_NODE
 572 #define BLOCK_BEFORE_NODE 1
 573
 574 #if BLOCK_BEFORE_NODE
 575
 576   /* This version assures, that all nodes are ordered absolutely.  This allows
 577      to undef all nodes in the heap analysis if the block is false, which means
 578      not reachable.
 579      I.e., with this code, the order on the loop tree is correct. But a (single)
 580      test showed the loop tree is deeper.   */
 581   if (get_irn_op(n) == op_Phi   ||
 582       get_irn_op(n) == op_Block ||
 583       (get_irn_op(n) == op_Filter && get_interprocedural_view()) ||
 584       (get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
 585        get_irn_pinned(n) == op_pin_state_floats))
 586     // Here we could test for backedge at -1 which is illegal
 587     return 0;
 588   else
 589     return -1;
 590
 591 #else
 592
 593   /* This version causes deeper loop trees (at least we verified this
 594      for Polymor).
 595      But it guarantees that Blocks are analysed before nodes contained in the
 596      block.  If so, we can set the value to undef if the block is not \
 597      executed. */
 598    if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
 599      return -1;
 600    else
 601      return 0;
 602
 603 #endif
 604 }
 605
 606
 607 #if 0
 608 static void test(ir_node *pred, ir_node *root, ir_node *this) {
 609   int i;
 610   if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
 611
 612   printf("this: %d ", get_irn_uplink(this)); DDMN(this);
 613   printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
 614   printf("root: %d ", get_irn_uplink(root)); DDMN(root);
 615
 616   printf("tos: %d\n", tos);
 617
 618   for (i = tos; i >= 0; i--) {
 619     ir_node *n = stack[i];
 620     if (!n) continue;
 621     printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
 622   }
 623 }
 624 #endif
 625
 626 /* Test for legal loop header: Block, Phi, ... */
 627 INLINE static bool is_possible_loop_head(ir_node *n) {
 628   ir_op *op = get_irn_op(n);
 629   return ((op == op_Block) ||
 630           (op == op_Phi) ||
 631           ((op == op_Filter) && get_interprocedural_view()));
 632 }
 633
 634 /* Returns true if n is a loop header, i.e., it is a Block, Phi
 635    or Filter node and has predecessors within the loop and out
 636    of the loop.
 637    @arg root: only needed for assertion. */
 638 static bool
 639 is_head (ir_node *n, ir_node *root)
 640 {
 641   int i, arity;
 642   int some_outof_loop = 0, some_in_loop = 0;
 643
 644   /* Test for legal loop header: Block, Phi, ... */
 645   if (!is_possible_loop_head(n))
 646     return false;
 647
 648   if (!is_outermost_Start(n)) {
 649     arity = get_irn_arity(n);
 650     for (i = get_start_index(n); i < arity; i++) {
 651       ir_node *pred = get_irn_n(n, i);
 652       assert(pred);
 653       if (is_backedge(n, i)) continue;
 654       if (!irn_is_in_stack(pred)) {
 655         some_outof_loop = 1;
 656       } else {
 657         if(get_irn_uplink(pred) < get_irn_uplink(root)) {
 658           DDMN(n); DDMN(pred); DDMN(root);
 659           assert(get_irn_uplink(pred) >= get_irn_uplink(root));
 660         }
 661         some_in_loop = 1;
 662       }
 663     }
 664   }
 665   return some_outof_loop && some_in_loop;
 666 }
 667
 668 /* Returns true if n is possible loop head of an endless loop.
 669    I.e., it is a Block, Phi or Filter node and has only predecessors
 670    within the loop.
 671    @arg root: only needed for assertion. */
 672 static bool
 673 is_endless_head (ir_node *n, ir_node *root)
 674 {
 675   int i, arity;
 676   int some_outof_loop = 0, some_in_loop = 0;
 677
 678   /* Test for legal loop header: Block, Phi, ... */
 679   if (!is_possible_loop_head(n))
 680     return false;
 681
 682   if (!is_outermost_Start(n)) {
 683     arity = get_irn_arity(n);
 684     for (i = get_start_index(n); i < arity; i++) {
 685       ir_node *pred = get_irn_n(n, i);
 686       assert(pred);
 687       if (is_backedge(n, i)) { continue; }
 688       if (!irn_is_in_stack(pred)) {
 689         some_outof_loop = 1; //printf(" some out of loop ");
 690       } else {
 691         if(get_irn_uplink(pred) < get_irn_uplink(root)) {
 692           DDMN(pred); DDMN(root);
 693           assert(get_irn_uplink(pred) >= get_irn_uplink(root));
 694         }
 695         some_in_loop = 1;
 696       }
 697     }
 698   }
 699   return !some_outof_loop && some_in_loop;
 700 }
 701
 702 /* Returns index of the predecessor with the smallest dfn number
 703    greater-equal than limit. */
 704 static int
 705 smallest_dfn_pred (ir_node *n, int limit)
 706 {
 707   int i, index = -2, min = -1;
 708
 709   if (!is_outermost_Start(n)) {
 710     int arity = get_irn_arity(n);
 711     for (i = get_start_index(n); i < arity; i++) {
 712       ir_node *pred = get_irn_n(n, i);
 713       assert(pred);
 714       if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
 715       if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
 716         index = i;
 717         min = get_irn_dfn(pred);
 718       }
 719     }
 720   }
 721   return index;
 722 }
 723
 724 /* Returns index of the predecessor with the largest dfn number. */
 725 static int
 726 largest_dfn_pred (ir_node *n)
 727 {
 728   int i, index = -2, max = -1;
 729
 730   if (!is_outermost_Start(n)) {
 731     int arity = get_irn_arity(n);
 732     for (i = get_start_index(n); i < arity; i++) {
 733       ir_node *pred = get_irn_n(n, i);
 734       if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
 735       if (get_irn_dfn(pred) > max) {
 736         index = i;
 737         max = get_irn_dfn(pred);
 738       }
 739     }
 740   }
 741   return index;
 742 }
 743
 744 /** Searches the stack for possible loop heads.  Tests these for backedges.
 745     If it finds a head with an unmarked backedge it marks this edge and
 746     returns the tail of the loop.
 747     If it finds no backedge returns NULL.
 748     ("disable_backedge" in fiasco)
 749 *
 750 *  @param n  A node where uplink == dfn.
 751 **/
 752
 753 static ir_node *
 754 find_tail (ir_node *n) {
 755   ir_node *m;
 756   int i, res_index = -2;
 757
 758   /*
 759     if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
 760   */
 761   m = stack[tos-1];  /* tos = top of stack */
 762   if (is_head (m, n)) {
 763     res_index = smallest_dfn_pred(m, 0);
 764     if ((res_index == -2) &&  /* no smallest dfn pred found. */
 765     (n ==  m))
 766       return NULL;
 767   } else {
 768     if (m == n) return NULL;    // Is this to catch Phi - self loops?
 769     for (i = tos-2; i >= 0; --i) {
 770       m = stack[i];
 771
 772       if (is_head (m, n)) {
 773         res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
 774         if (res_index == -2)  /* no smallest dfn pred found. */
 775           res_index = largest_dfn_pred (m);
 776
 777         if ((m == n) && (res_index == -2)) {  /* dont walk past loop head. */
 778           i = -1;
 779         }
 780         break;
 781       }
 782
 783       /* We should not walk past our selves on the stack:  The upcoming nodes
 784          are not in this loop. We assume a loop not reachable from Start. */
 785       if (m == n) {
 786         i = -1;
 787         break;
 788       }
 789
 790     }
 791
 792     if (i < 0) {
 793       /* A dead loop not reachable from Start. */
 794       for (i = tos-2; i >= 0; --i) {
 795         m = stack[i];
 796         if (is_endless_head (m, n)) {
 797           res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
 798           if (res_index == -2)  /* no smallest dfn pred found. */
 799             res_index = largest_dfn_pred (m);
 800           break;
 801         }
 802         if (m == n) { break; }  /* It's not an unreachable loop, either. */
 803       }
 804       //assert(0 && "no head found on stack");
 805     }
 806
 807   }
 808   if (res_index <= -2) {
 809     /* It's a completely bad loop: without Phi/Block nodes that can
 810        be a head. I.e., the code is "dying".  We break the loop by
 811        setting Bad nodes. */
 812     int arity = get_irn_arity(n);
 813     for (i = -1; i < arity; ++i) {
 814       set_irn_n(n, i, get_irg_bad(get_irn_irg(n)));
 815     }
 816     return NULL;
 817   }
 818   assert (res_index > -2);
 819
 820   set_backedge (m, res_index);
 821   return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
 822 }
 823
 824
 825 #if EXPERIMENTAL_LOOP_TREE
 826
 827 /*  ----------------------------------------------------------------
 828     AS:  This is experimantal code to build loop trees suitable for
 829     the heap analysis. Does not work correctly right now... :-(
 830
 831
 832     Search in stack for the corresponding first Call-End-ProjX that
 833     corresponds to one of the control flow predecessors of the given
 834     block, that is the possible callers.
 835     returns: the control predecessor to chose\
 836     or       -1 if no corresponding Call-End-Node could be found
 837              on the stack.
 838     - -------------------------------------------------------------- */
 839
 840 int search_endproj_in_stack(ir_node *start_block)
 841 {
 842   int i, j;
 843   assert(is_Block(start_block));
 844   for(i = tos - 1; i >= 0; --i)
 845     {
 846       DDMN(stack[i]);
 847       if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
 848          get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
 849         {
 850           printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
 851           ir_node *end_projx = stack[i];
 852
 853           int arity = get_irn_arity(start_block);
 854           for(j = 0; j < arity; j++)
 855             {
 856               ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
 857                                                        get_Proj_proj(end_projx));
 858               DDMN(begin_projx);
 859               if(get_irn_n(start_block, j) == begin_projx)
 860                 {
 861                   printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
 862                   return(j);
 863                 }
 864             }
 865         }
 866     }
 867   return(-1);
 868 }
 869
 870
 871 static pmap *projx_link = NULL;
 872
 873 void link_to_reg_end (ir_node *n, void *env) {
 874   if(get_irn_op(n) == op_Proj &&
 875      get_irn_mode(n) == mode_X &&
 876      get_irn_op(get_irn_n(n, 0)) == op_EndReg) {
 877       /* Reg End Projx -> Find the CallBegin Projx and hash it */
 878       ir_node *end_projx = n;
 879       ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
 880                                                get_Proj_proj(end_projx));
 881       printf("Linked the following ProjxNodes:\n");
 882       DDMN(begin_projx);
 883       DDMN(end_projx);
 884       set_projx_link(begin_projx, end_projx);
 885     }
 886 }
 887
 888 void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
 889 {
 890   if(projx_link == NULL)
 891     projx_link = pmap_create();
 892   pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
 893 }
 894
 895 ir_node *get_projx_link(ir_node *cb_projx)
 896 {
 897   return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
 898 }
 899
 900 #endif
 901
 902 INLINE static int
 903 is_outermost_loop(ir_loop *l) {
 904   return l == get_loop_outer_loop(l);
 905 }
 906
 907
 908 /*-----------------------------------------------------------*
 909  *                   The core algorithm.                     *
 910  *-----------------------------------------------------------*/
 911
 912
 913 static void scc (ir_node *n) {
 914   int i;
 915   if (irn_visited(n)) return;
 916   mark_irn_visited(n);
 917
 918   /* Initialize the node */
 919   set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
 920   set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
 921   set_irn_loop(n, NULL);
 922   current_dfn ++;
 923   push(n);
 924
 925   /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
 926      array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
 927      so is_backedge does not access array[-1] but correctly returns false! */
 928
 929   if (!is_outermost_Start(n)) {
 930     int arity = get_irn_arity(n);
 931
 932     for (i = get_start_index(n); i < arity; i++) {
 933       ir_node *m;
 934       if (is_backedge(n, i)) continue;
 935       m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
 936       /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
 937       scc (m);
 938       if (irn_is_in_stack(m)) {
 939         /* Uplink of m is smaller if n->m is a backedge.
 940            Propagate the uplink to mark the loop. */
 941         if (get_irn_uplink(m) < get_irn_uplink(n))
 942           set_irn_uplink(n, get_irn_uplink(m));
 943       }
 944     }
 945   }
 946
 947   if (get_irn_dfn(n) == get_irn_uplink(n)) {
 948     /* This condition holds for
 949        1) the node with the incoming backedge.
 950           That is: We found a loop!
 951        2) Straight line code, because no uplink has been propagated, so the
 952           uplink still is the same as the dfn.
 953
 954        But n might not be a proper loop head for the analysis. Proper loop
 955        heads are Block and Phi nodes. find_tail searches the stack for
 956        Block's and Phi's and takes those nodes as loop heads for the current
 957        loop instead and marks the incoming edge as backedge. */
 958
 959     ir_node *tail = find_tail(n);
 960     if (tail) {
 961       /* We have a loop, that is no straight line code,
 962          because we found a loop head!
 963          Next actions: Open a new loop on the loop tree and
 964                        try to find inner loops */
 965
 966 #if NO_LOOPS_WITHOUT_HEAD
 967       /* This is an adaption of the algorithm from fiasco / optscc to
 968        * avoid loops without Block or Phi as first node.  This should
 969        * severely reduce the number of evaluations of nodes to detect
 970        * a fixpoint in the heap analysis.
 971        * Further it avoids loops without firm nodes that cause errors
 972        * in the heap analyses.
 973        * But attention:  don't do it for the outermost loop:  This loop
 974        * is not iterated.  A first block can be a loop head in case of
 975        * an endless recursion. */
 976
 977       ir_loop *l;
 978       int close;
 979       if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
 980         l = new_loop();
 981         close = 1;
 982       } else {
 983         l = current_loop;
 984         close = 0;
 985       }
 986 #else
 987       ir_loop *l = new_loop();
 988 #endif
 989
 990       /* Remove the loop from the stack ... */
 991       pop_scc_unmark_visit (n);
 992
 993       /* The current backedge has been marked, that is temporarily eliminated,
 994          by find tail. Start the scc algorithm
 995          anew on the subgraph thats left (the current loop without the backedge)
 996          in order to find more inner loops. */
 997       scc (tail);
 998
 999       assert (irn_visited(n));
1000 #if NO_LOOPS_WITHOUT_HEAD
1001       if (close)
1002 #endif
1003         close_loop(l);
1004     }
1005     else
1006       {
1007         /* No loop head was found, that is we have straightline code.
1008            Pop all nodes from the stack to the current loop. */
1009       pop_scc_to_loop(n);
1010     }
1011   }
1012 }
1013
1014 static void my_scc (ir_node *n) {
1015   int i;
1016   if (irn_visited(n)) return;
1017   mark_irn_visited(n);
1018
1019   /* Initialize the node */
1020   set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
1021   set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
1022   set_irn_loop(n, NULL);
1023   current_dfn ++;
1024   push(n);
1025
1026   /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
1027      array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
1028      so is_backedge does not access array[-1] but correctly returns false! */
1029
1030   if (!is_outermost_Start(n)) {
1031     int arity = get_irn_arity(n);
1032
1033     for (i = get_start_index(n); i < arity; i++) {
1034       ir_node *m;
1035       if (is_backedge(n, i)) continue;
1036       m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
1037       /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
1038       my_scc (m);
1039       if (irn_is_in_stack(m)) {
1040         /* Uplink of m is smaller if n->m is a backedge.
1041            Propagate the uplink to mark the loop. */
1042         if (get_irn_uplink(m) < get_irn_uplink(n))
1043           set_irn_uplink(n, get_irn_uplink(m));
1044       }
1045     }
1046   }
1047
1048   if (get_irn_dfn(n) == get_irn_uplink(n)) {
1049     /* This condition holds for
1050        1) the node with the incoming backedge.
1051           That is: We found a loop!
1052        2) Straight line code, because no uplink has been propagated, so the
1053           uplink still is the same as the dfn.
1054
1055        But n might not be a proper loop head for the analysis. Proper loop
1056        heads are Block and Phi nodes. find_tail searches the stack for
1057        Block's and Phi's and takes those nodes as loop heads for the current
1058        loop instead and marks the incoming edge as backedge. */
1059
1060     ir_node *tail = find_tail(n);
1061     if (tail) {
1062       /* We have a loop, that is no straight line code,
1063          because we found a loop head!
1064          Next actions: Open a new loop on the loop tree and
1065                        try to find inner loops */
1066
1067 #if NO_LOOPS_WITHOUT_HEAD
1068       /* This is an adaption of the algorithm from fiasco / optscc to
1069        * avoid loops without Block or Phi as first node.  This should
1070        * severely reduce the number of evaluations of nodes to detect
1071        * a fixpoint in the heap analysis.
1072        * Further it avoids loops without firm nodes that cause errors
1073        * in the heap analyses. */
1074
1075       ir_loop *l;
1076       int close;
1077       if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
1078         l = new_loop();
1079         close = 1;
1080       } else {
1081         l = current_loop;
1082         close = 0;
1083       }
1084 #else
1085       ir_loop *l = new_loop();
1086 #endif
1087
1088       /* Remove the loop from the stack ... */
1089       pop_scc_unmark_visit (n);
1090
1091       /* The current backedge has been marked, that is temporarily eliminated,
1092          by find tail. Start the scc algorithm
1093          anew on the subgraph thats left (the current loop without the backedge)
1094          in order to find more inner loops. */
1095       my_scc (tail);
1096
1097       assert (irn_visited(n));
1098 #if NO_LOOPS_WITHOUT_HEAD
1099       if (close)
1100 #endif
1101         close_loop(l);
1102     }
1103     else
1104       {
1105         /* No loop head was found, that is we have straightline code.
1106            Pop all nodes from the stack to the current loop. */
1107       pop_scc_to_loop(n);
1108     }
1109   }
1110 }
1111
1112 /* Constructs backedge information for irg. In interprocedural view constructs
1113    backedges for all methods called by irg, too. */
1114 int construct_backedges(ir_graph *irg) {
1115   ir_graph *rem = current_ir_graph;
1116   ir_loop *head_rem;
1117
1118   assert(!get_interprocedural_view() &&
1119      "not implemented, use construct_ip_backedges");
1120
1121   max_loop_depth = 0;
1122   current_ir_graph   = irg;
1123   outermost_ir_graph = irg;
1124
1125   init_scc(current_ir_graph);
1126
1127   current_loop = NULL;
1128   new_loop();  /* sets current_loop */
1129   head_rem = current_loop; /* Just for assertion */
1130
1131   inc_irg_visited(current_ir_graph);
1132
1133   scc(get_irg_end(current_ir_graph));
1134
1135   assert(head_rem == current_loop);
1136   set_irg_loop(current_ir_graph, current_loop);
1137   set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
1138   assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
1139   /*
1140   irg->loops = current_loop;
1141   if (icfg == 1) {
1142     int count = 0;
1143     int depth = 0;
1144     count_loop (the_loop, &count, &depth);
1145     }
1146   }
1147   */
1148   current_ir_graph = rem;
1149
1150   return max_loop_depth;
1151 }
1152
1153
1154 int construct_ip_backedges (void) {
1155   ir_graph *rem = current_ir_graph;
1156   int rem_ipv = get_interprocedural_view();
1157   int i;
1158
1159   max_loop_depth = 0;
1160   assert(get_irp_ip_view_state() == ip_view_valid);
1161
1162   outermost_ir_graph = get_irp_main_irg();
1163
1164   init_ip_scc();
1165
1166   current_loop = NULL;
1167   new_loop();  /* sets current_loop */
1168   set_interprocedural_view(true);
1169
1170   inc_max_irg_visited();
1171   for (i = 0; i < get_irp_n_irgs(); i++)
1172     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1173
1174   /** We have to start the walk at the same nodes as cg_walk. **/
1175   /* Walk starting at unreachable procedures. Only these
1176    * have End blocks visible in interprocedural view. */
1177   for (i = 0; i < get_irp_n_irgs(); i++) {
1178     ir_node *sb;
1179     current_ir_graph = get_irp_irg(i);
1180
1181     sb = get_irg_start_block(current_ir_graph);
1182
1183     if ((get_Block_n_cfgpreds(sb) > 1) ||
1184     (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1185
1186     scc(get_irg_end(current_ir_graph));
1187   }
1188
1189   /* Check whether we walked all procedures: there could be procedures
1190      with cyclic calls but no call from the outside. */
1191   for (i = 0; i < get_irp_n_irgs(); i++) {
1192     ir_node *sb;
1193     current_ir_graph = get_irp_irg(i);
1194
1195     /* Test start block: if inner procedure end and end block are not
1196      * visible and therefore not marked. */
1197     sb = get_irg_start_block(current_ir_graph);
1198     if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1199   }
1200
1201   /* Walk all endless loops in inner procedures.
1202    * We recognize an inner procedure if the End node is not visited. */
1203   for (i = 0; i < get_irp_n_irgs(); i++) {
1204     ir_node *e;
1205     current_ir_graph = get_irp_irg(i);
1206
1207     e = get_irg_end(current_ir_graph);
1208     if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1209       int j;
1210       /* Don't visit the End node. */
1211       for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1212     }
1213   }
1214
1215   set_irg_loop(outermost_ir_graph, current_loop);
1216   set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1217   assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1218
1219   current_ir_graph = rem;
1220   set_interprocedural_view(rem_ipv);
1221   return max_loop_depth;
1222 }
1223
1224 void my_construct_ip_backedges (void) {
1225   ir_graph *rem = current_ir_graph;
1226   int rem_ipv = get_interprocedural_view();
1227   int i;
1228
1229   assert(get_irp_ip_view_state() == ip_view_valid);
1230
1231   outermost_ir_graph = get_irp_main_irg();
1232
1233   init_ip_scc();
1234
1235   current_loop = NULL;
1236   new_loop();  /* sets current_loop */
1237   set_interprocedural_view(true);
1238
1239   inc_max_irg_visited();
1240   for (i = 0; i < get_irp_n_irgs(); i++)
1241     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1242
1243   /** We have to start the walk at the same nodes as cg_walk. **/
1244   /* Walk starting at unreachable procedures. Only these
1245    * have End blocks visible in interprocedural view. */
1246   for (i = 0; i < get_irp_n_irgs(); i++) {
1247     ir_node *sb;
1248     current_ir_graph = get_irp_irg(i);
1249
1250     sb = get_irg_start_block(current_ir_graph);
1251
1252     if ((get_Block_n_cfgpreds(sb) > 1) ||
1253     (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1254
1255     my_scc(get_irg_end(current_ir_graph));
1256   }
1257
1258   /* Check whether we walked all procedures: there could be procedures
1259      with cyclic calls but no call from the outside. */
1260   for (i = 0; i < get_irp_n_irgs(); i++) {
1261     ir_node *sb;
1262     current_ir_graph = get_irp_irg(i);
1263
1264     /* Test start block: if inner procedure end and end block are not
1265      * visible and therefore not marked. */
1266     sb = get_irg_start_block(current_ir_graph);
1267     if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1268   }
1269
1270   /* Walk all endless loops in inner procedures.
1271    * We recognize an inner procedure if the End node is not visited. */
1272   for (i = 0; i < get_irp_n_irgs(); i++) {
1273     ir_node *e;
1274     current_ir_graph = get_irp_irg(i);
1275
1276     e = get_irg_end(current_ir_graph);
1277     if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1278       int j;
1279       /* Don't visit the End node. */
1280       for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1281     }
1282   }
1283
1284   set_irg_loop(outermost_ir_graph, current_loop);
1285   set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1286   assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1287
1288   current_ir_graph = rem;
1289   set_interprocedural_view(rem_ipv);
1290 }
1291
1292 static void reset_backedges(ir_node *n) {
1293   if (is_possible_loop_head(n)) {
1294     int rem = get_interprocedural_view();
1295
1296     set_interprocedural_view(true);
1297     clear_backedges(n);
1298     set_interprocedural_view(true);
1299     clear_backedges(n);
1300     set_interprocedural_view(rem);
1301   }
1302 }
1303
1304
1305 /*
1306 static void loop_reset_backedges(ir_loop *l) {
1307   int i;
1308   reset_backedges(get_loop_node(l, 0));
1309   for (i = 0; i < get_loop_n_nodes(l); ++i)
1310     set_irn_loop(get_loop_node(l, i), NULL);
1311   for (i = 0; i < get_loop_n_sons(l); ++i) {
1312     loop_reset_backedges(get_loop_son(l, i));
1313   }
1314 }
1315 */
1316
1317 static void loop_reset_node(ir_node *n, void *env) {
1318   set_irn_loop(n, NULL);
1319   reset_backedges(n);
1320 }
1321
1322
1323 /** Removes all loop information.
1324     Resets all backedges */
1325 void free_loop_information(ir_graph *irg) {
1326   /* We can not use this recursion, as the loop might contain
1327      illegal nodes by now.  Why else would we throw away the
1328      representation?
1329   if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1330   */
1331   irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1332   set_irg_loop(irg, NULL);
1333   set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1334   /* We cannot free the loop nodes, they are on the obstack. */
1335 }
1336
1337
1338 void free_all_loop_information (void) {
1339   int i;
1340   int rem = get_interprocedural_view();
1341   set_interprocedural_view(true);  /* To visit all filter nodes */
1342   for (i = 0; i < get_irp_n_irgs(); i++) {
1343     free_loop_information(get_irp_irg(i));
1344   }
1345   set_interprocedural_view(rem);
1346 }
1347
1348
1349
1350
1351
1352 /* Debug stuff *************************************************/
1353
1354 static int test_loop_node(ir_loop *l) {
1355   int i, has_node = 0, found_problem = 0;
1356   loop_element le;
1357
1358   assert(l && l->kind == k_ir_loop);
1359
1360   if (get_loop_n_elements(l) == 0) {
1361     printf(" Loop completely empty! "); DDML(l);
1362     found_problem = 1;
1363     dump_loop(l, "-ha");
1364   }
1365
1366   le = get_loop_element(l, 0);
1367   if (*(le.kind) != k_ir_node) {
1368     assert(le.kind && *(le.kind) == k_ir_loop);
1369     printf(" First loop element is not a node! "); DDML(l);
1370     printf("                                   "); DDML(le.son);
1371
1372     found_problem = 1;
1373     dump_loop(l, "-ha");
1374   }
1375
1376   if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1377     printf(" Wrong node as head! "); DDML(l);
1378     printf("                     "); DDMN(le.node);
1379     found_problem = 1;
1380     dump_loop(l, "-ha");
1381   }
1382
1383   if ((get_loop_depth(l) != 0) &&
1384       (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1385     printf(" Loop head has no backedges! "); DDML(l);
1386     printf("                             "); DDMN(le.node);
1387     found_problem = 1;
1388     dump_loop(l, "-ha");
1389   }
1390
1391   /* Recur */
1392   has_node = 0;
1393   for (i = 0; i < get_loop_n_elements(l); ++i) {
1394     le = get_loop_element(l, i);
1395     if (*(le.kind) == k_ir_node)
1396       has_node++;
1397     else
1398       if (test_loop_node(le.son)) found_problem = 1;
1399   }
1400
1401   if (has_node == 0) {
1402     printf(" Loop has no firm node! "); DDML(l);
1403     found_problem = 1;
1404     dump_loop(l, "-ha");
1405   }
1406
1407   if (get_loop_loop_nr(l) == 11819)
1408     dump_loop(l, "-ha-debug");
1409
1410   return found_problem;
1411 }
1412
1413 /** Prints all loop nodes that
1414  *  - do not have any firm nodes, only loop sons
1415  *  - the header is not a Phi, Block or Filter.
1416  */
1417 void find_strange_loop_nodes(ir_loop *l) {
1418   int found_problem = 0;
1419   printf("\nTesting loop "); DDML(l);
1420   found_problem = test_loop_node(l);
1421   printf("Finished Test\n\n");
1422   if (found_problem) exit(0);
1423
1424 }
1425
1426 /* ------------------------------------------------------------------- */
1427 /* Simple analyses based on the loop information                       */
1428 /* ------------------------------------------------------------------- */
1429
1430 int is_loop_variant(ir_loop *l, ir_loop *b) {
1431   int i, n_elems;
1432
1433   if (l == b) return true;
1434
1435   n_elems = get_loop_n_elements(l);
1436   for (i = 0; i < n_elems; ++i) {
1437     loop_element e = get_loop_element(l, i);
1438     if (is_ir_loop(e.kind))
1439       if (is_loop_variant(e.son, b))
1440         return true;
1441   }
1442
1443   return false;
1444 }
1445
1446 /* Test whether a value is loop invariant.
1447  *
1448  * @param n      The node to be tested.
1449  * @param block  A block node.  We pass the block, not the loop as we must
1450  *               start off with a block loop to find all proper uses.
1451  *
1452  * Returns true, if the node n is not changed in the loop block
1453  * belongs to or in inner loops of this block. */
1454 int is_loop_invariant(ir_node *n, ir_node *block) {
1455   ir_loop *l = get_irn_loop(block);
1456   ir_node *b = (is_Block(n)) ? n : get_nodes_block(n);
1457   return !is_loop_variant(l, get_irn_loop(b));
1458 }