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-2006 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 #ifdef HAVE_STDLIB_H
  24 # include <stdlib.h>
  25 #endif
  26
  27 #include "irloop_t.h"
  28
  29 #include "irprog_t.h"
  30 #include "irgraph_t.h"
  31 #include "irnode_t.h"
  32 #include "irgwalk.h"
  33 #include "array.h"
  34 #include "pmap.h"
  35
  36 #include "irdump.h"
  37
  38 /* A variant of the loop tree that avoids loops without head.
  39    This reduces the depth of the loop tree. */
  40 #define NO_LOOPS_WITHOUT_HEAD 1
  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   int 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   scc_info *scc = get_irn_link(n);
  87   assert(scc);
  88   scc->in_stack = 1;
  89 }
  90
  91 static INLINE void
  92 mark_irn_not_in_stack (ir_node *n) {
  93   scc_info *scc = get_irn_link(n);
  94   assert(scc);
  95   scc->in_stack = 0;
  96 }
  97
  98 static INLINE int
  99 irn_is_in_stack (ir_node *n) {
 100   scc_info *scc = get_irn_link(n);
 101   assert(scc);
 102   return scc->in_stack;
 103 }
 104
 105 static INLINE void
 106 set_irn_uplink (ir_node *n, int uplink) {
 107   scc_info *scc = get_irn_link(n);
 108   assert(scc);
 109   scc->uplink = uplink;
 110 }
 111
 112 int
 113 get_irn_uplink (ir_node *n) {
 114   scc_info *scc = get_irn_link(n);
 115   assert(scc);
 116   return scc->uplink;
 117 }
 118
 119 static INLINE void
 120 set_irn_dfn (ir_node *n, int dfn) {
 121   scc_info *scc = get_irn_link(n);
 122   assert(scc);
 123   scc->dfn = dfn;
 124 }
 125
 126 int
 127 get_irn_dfn (ir_node *n) {
 128   scc_info *scc = get_irn_link(n);
 129   assert(scc);
 130   return scc->dfn;
 131 }
 132
 133
 134 void
 135 set_irn_loop (ir_node *n, ir_loop *loop) {
 136   n->loop = loop;
 137 }
 138
 139 /* Uses temporary information to get the loop */
 140 ir_loop *(get_irn_loop)(const ir_node *n) {
 141   return _get_irn_loop(n);
 142 }
 143
 144
 145 #if 0
 146 static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
 147   int i;
 148   ir_loop *res = NULL;
 149
 150   /* Test whether n is contained in this loop. */
 151   for (i = 0; i < get_loop_n_nodes(l); i++)
 152     if (n == get_loop_node(l, i)) return l;
 153
 154   /* Is this a leave in the loop tree? If so loop not found. */
 155   if (get_loop_n_sons(l) == 0) return NULL;
 156
 157   /* Else descend in the loop tree. */
 158   for (i = 0; i < get_loop_n_sons(l); i++) {
 159     res = find_nodes_loop(n, get_loop_son(l, i));
 160     if (res) break;
 161   }
 162   return res;
 163 }
 164
 165 /* @@@ temporary implementation, costly!!! */
 166 ir_loop * get_irn_loop(ir_node *n) {
 167   ir_loop *l = get_irg_loop(current_ir_graph);
 168   l = find_nodes_loop(n, l);
 169   return l;
 170 }
 171 #endif
 172
 173 /**********************************************************************/
 174 /* A stack.                                                          **/
 175 /**********************************************************************/
 176
 177 static ir_node **stack = NULL;
 178 static int tos = 0;                /* top of stack */
 179
 180 /**
 181  * initializes the stack
 182  */
 183 static INLINE void init_stack(void) {
 184   if (stack) {
 185     ARR_RESIZE (ir_node *, stack, 1000);
 186   } else {
 187     stack = NEW_ARR_F (ir_node *, 1000);
 188   }
 189   tos = 0;
 190 }
 191
 192 #if 0
 193 static INLINE void free_stack(void) {
 194   DEL_ARR_F(stack);
 195   stack = NULL;
 196   tos = 0;
 197 }
 198 #endif
 199
 200 /**
 201  * push a node onto the stack
 202  *
 203  * @param n  The node to push
 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 /**
 219  * pop a node from the stack
 220  *
 221  * @return  The topmost node
 222  */
 223 static INLINE ir_node *
 224 pop (void)
 225 {
 226   ir_node *n = stack[--tos];
 227   mark_irn_not_in_stack(n);
 228   return n;
 229 }
 230
 231 /**
 232  * The nodes up to n belong to the current loop.
 233  * Removes them from the stack and adds them to the current loop.
 234  */
 235 static INLINE void
 236 pop_scc_to_loop (ir_node *n)
 237 {
 238   ir_node *m;
 239   int i = 0;
 240
 241   do {
 242     m = pop();
 243
 244     //printf(" dfn: %d, upl %d upl-new %d ", get_irn_dfn(m), get_irn_uplink(m), loop_node_cnt+1); DDMN(m);
 245
 246     loop_node_cnt++;
 247     set_irn_dfn(m, loop_node_cnt);
 248     add_loop_node(current_loop, m);
 249     set_irn_loop(m, current_loop);
 250     i++;
 251
 252     /*    if (m==n) break;*/
 253   } while(m != n);
 254
 255   /* i might be bigger than 1 for dead (and that's why bad) loops */
 256   /* if(i > 1)
 257     printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!11111\n");
 258    */
 259 }
 260
 261 /* GL ??? my last son is my grandson???  Removes loops with no
 262    ir_nodes in them.  Such loops have only another loop as son. (Why
 263    can't they have two loops as sons? Does it never get that far? ) */
 264 static void close_loop (ir_loop *l)
 265 {
 266   int last = get_loop_n_elements(l) - 1;
 267   loop_element lelement = get_loop_element(l, last);
 268   ir_loop *last_son = lelement.son;
 269
 270   if (get_kind(last_son) == k_ir_loop &&
 271       get_loop_n_elements(last_son) == 1) {
 272     ir_loop *gson;
 273
 274     lelement = get_loop_element(last_son, 0);
 275     gson = lelement.son;
 276
 277     if (get_kind(gson) == k_ir_loop) {
 278       loop_element new_last_son;
 279
 280       gson->outer_loop = l;
 281       new_last_son.son = gson;
 282       l->children[last] = new_last_son;
 283     }
 284   }
 285
 286   current_loop = l;
 287 }
 288
 289 /* Removes and unmarks all nodes up to n from the stack.
 290    The nodes must be visited once more to assign them to a scc. */
 291 static INLINE void
 292 pop_scc_unmark_visit (ir_node *n)
 293 {
 294   ir_node *m = NULL;
 295
 296   while (m != n) {
 297     m = pop();
 298     set_irn_visited(m, 0);
 299   }
 300 }
 301
 302 /**********************************************************************/
 303 /* The loop datastructure.                                           **/
 304 /**********************************************************************/
 305
 306 /* Allocates a new loop as son of current_loop.  Sets current_loop
 307    to the new loop and returns the father. */
 308 ir_loop *new_loop (void) {
 309   ir_loop *father, *son;
 310
 311   father = current_loop;
 312
 313   son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
 314   memset (son, 0, sizeof (ir_loop));
 315   son->kind = k_ir_loop;
 316   son->children = NEW_ARR_F (loop_element, 0);
 317   son->n_nodes = 0;
 318   son->n_sons=0;
 319   if (father) {
 320     son->outer_loop = father;
 321     add_loop_son(father, son);
 322     son->depth = father->depth+1;
 323     if (son->depth > max_loop_depth) max_loop_depth = son->depth;
 324   } else {  /* The root loop */
 325     son->outer_loop = son;
 326     son->depth = 0;
 327   }
 328
 329 #ifdef DEBUG_libfirm
 330   son->loop_nr = get_irp_new_node_nr();
 331   son->link = NULL;
 332 #endif
 333
 334   current_loop = son;
 335   return father;
 336 }
 337
 338 #if 0
 339 /* Finishes the datastructures, copies the arrays to the obstack
 340    of current_ir_graph.
 341    A. Schoesser: Caution: loop -> sons is gone. */
 342 static void mature_loop (ir_loop *loop) {
 343   ir_loop **new_sons;
 344
 345   new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
 346   memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
 347   DEL_ARR_F(loop->sons);
 348   loop->sons = new_sons;
 349 }
 350 #endif
 351
 352 /* Returns outer loop, itself if outermost. */
 353 ir_loop *(get_loop_outer_loop)(const ir_loop *loop) {
 354   return _get_loop_outer_loop(loop);
 355 }
 356
 357 /* Returns nesting depth of this loop */
 358 int (get_loop_depth)(const ir_loop *loop) {
 359   return _get_loop_depth(loop);
 360 }
 361
 362 /* Returns the number of inner loops */
 363 int (get_loop_n_sons)(const ir_loop *loop) {
 364   return _get_loop_n_sons(loop);
 365 }
 366
 367 /* Returns the pos`th loop_node-child              *
 368  * TODO: This method isn`t very efficient !        *
 369  * Returns NULL if there isn`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 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 isn`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 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 (const 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 appropriate "loop_element.node" or "loop_element.son".
 450 */
 451
 452 loop_element get_loop_element(const ir_loop *loop, int pos) {
 453   assert(loop && loop->kind == k_ir_loop && pos < ARR_LEN(loop->children));
 454   return(loop -> children[pos]);
 455 }
 456
 457 int get_loop_element_pos(const ir_loop *loop, void *le) {
 458   int i, n;
 459   assert(loop && loop->kind == k_ir_loop);
 460
 461   n = get_loop_n_elements(loop);
 462   for (i = 0; i < n; i++)
 463     if (get_loop_element(loop, i).node == le) return i;
 464   return -1;
 465 }
 466
 467 int get_loop_loop_nr(const 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 _is_ir_loop(thing);
 496 }
 497
 498 /* The outermost loop is remarked in the surrounding graph. */
 499 void (set_irg_loop)(ir_graph *irg, ir_loop *loop) {
 500   _set_irg_loop(irg, loop);
 501 }
 502
 503 /* Returns the root loop info (if exists) for an irg. */
 504 ir_loop *(get_irg_loop)(ir_graph *irg) {
 505   return _get_irg_loop(irg);
 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 int 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 1;
 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 1;
 567   }
 568 #endif
 569   return 0;
 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 static INLINE int 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 non-zero 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 int
 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 0;
 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 /**
 673  * Returns non-zero if n is possible loop head of an endless loop.
 674  * I.e., it is a Block, Phi or Filter node and has only predecessors
 675  * within the loop.
 676  * @param root: only needed for assertion.
 677  */
 678 static int
 679 is_endless_head (ir_node *n, ir_node *root)
 680 {
 681   int i, arity;
 682   int some_outof_loop = 0, some_in_loop = 0;
 683
 684   /* Test for legal loop header: Block, Phi, ... */
 685   if (!is_possible_loop_head(n))
 686     return 0;
 687
 688   if (!is_outermost_Start(n)) {
 689     arity = get_irn_arity(n);
 690     for (i = get_start_index(n); i < arity; i++) {
 691       ir_node *pred = get_irn_n(n, i);
 692       assert(pred);
 693       if (is_backedge(n, i)) { continue; }
 694       if (!irn_is_in_stack(pred)) {
 695         some_outof_loop = 1; //printf(" some out of loop ");
 696       } else {
 697         if(get_irn_uplink(pred) < get_irn_uplink(root)) {
 698           DDMN(pred); DDMN(root);
 699           assert(get_irn_uplink(pred) >= get_irn_uplink(root));
 700         }
 701         some_in_loop = 1;
 702       }
 703     }
 704   }
 705   return !some_outof_loop && some_in_loop;
 706 }
 707
 708 /* Returns index of the predecessor with the smallest dfn number
 709    greater-equal than limit. */
 710 static int
 711 smallest_dfn_pred (ir_node *n, int limit)
 712 {
 713   int i, index = -2, min = -1;
 714
 715   if (!is_outermost_Start(n)) {
 716     int arity = get_irn_arity(n);
 717     for (i = get_start_index(n); i < arity; i++) {
 718       ir_node *pred = get_irn_n(n, i);
 719       assert(pred);
 720       if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
 721       if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
 722         index = i;
 723         min = get_irn_dfn(pred);
 724       }
 725     }
 726   }
 727   return index;
 728 }
 729
 730 /* Returns index of the predecessor with the largest dfn number. */
 731 static int
 732 largest_dfn_pred (ir_node *n)
 733 {
 734   int i, index = -2, max = -1;
 735
 736   if (!is_outermost_Start(n)) {
 737     int arity = get_irn_arity(n);
 738     for (i = get_start_index(n); i < arity; i++) {
 739       ir_node *pred = get_irn_n(n, i);
 740       if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
 741       if (get_irn_dfn(pred) > max) {
 742         index = i;
 743         max = get_irn_dfn(pred);
 744       }
 745     }
 746   }
 747   return index;
 748 }
 749
 750 /** Searches the stack for possible loop heads.  Tests these for backedges.
 751     If it finds a head with an unmarked backedge it marks this edge and
 752     returns the tail of the loop.
 753     If it finds no backedge returns NULL.
 754     ("disable_backedge" in fiasco)
 755 *
 756 *  @param n  A node where uplink == dfn.
 757 **/
 758
 759 static ir_node *
 760 find_tail (ir_node *n) {
 761   ir_node *m;
 762   int i, res_index = -2;
 763
 764   /*
 765     if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
 766   */
 767   m = stack[tos-1];  /* tos = top of stack */
 768   if (is_head (m, n)) {
 769     res_index = smallest_dfn_pred(m, 0);
 770     if ((res_index == -2) &&  /* no smallest dfn pred found. */
 771     (n ==  m))
 772       return NULL;
 773   } else {
 774     if (m == n) return NULL;    // Is this to catch Phi - self loops?
 775     for (i = tos-2; i >= 0; --i) {
 776       m = stack[i];
 777
 778       if (is_head (m, n)) {
 779         res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
 780         if (res_index == -2)  /* no smallest dfn pred found. */
 781           res_index = largest_dfn_pred (m);
 782
 783         if ((m == n) && (res_index == -2)) {  /* dont walk past loop head. */
 784           i = -1;
 785         }
 786         break;
 787       }
 788
 789       /* We should not walk past our selves on the stack:  The upcoming nodes
 790          are not in this loop. We assume a loop not reachable from Start. */
 791       if (m == n) {
 792         i = -1;
 793         break;
 794       }
 795
 796     }
 797
 798     if (i < 0) {
 799       /* A dead loop not reachable from Start. */
 800       for (i = tos-2; i >= 0; --i) {
 801         m = stack[i];
 802         if (is_endless_head (m, n)) {
 803           res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
 804           if (res_index == -2)  /* no smallest dfn pred found. */
 805             res_index = largest_dfn_pred (m);
 806           break;
 807         }
 808         if (m == n) { break; }  /* It's not an unreachable loop, either. */
 809       }
 810       //assert(0 && "no head found on stack");
 811     }
 812
 813   }
 814   if (res_index <= -2) {
 815     /* It's a completely bad loop: without Phi/Block nodes that can
 816        be a head. I.e., the code is "dying".  We break the loop by
 817        setting Bad nodes. */
 818     int arity = get_irn_arity(n);
 819     for (i = -1; i < arity; ++i) {
 820       set_irn_n(n, i, get_irg_bad(get_irn_irg(n)));
 821     }
 822     return NULL;
 823   }
 824   assert (res_index > -2);
 825
 826   set_backedge (m, res_index);
 827   return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
 828 }
 829
 830
 831 #if EXPERIMENTAL_LOOP_TREE
 832
 833 /*  ----------------------------------------------------------------
 834     AS:  This is experimental code to build loop trees suitable for
 835     the heap analysis. Does not work correctly right now... :-(
 836
 837
 838     Search in stack for the corresponding first Call-End-ProjX that
 839     corresponds to one of the control flow predecessors of the given
 840     block, that is the possible callers.
 841     returns: the control predecessor to chose\
 842     or       -1 if no corresponding Call-End-Node could be found
 843              on the stack.
 844     - -------------------------------------------------------------- */
 845
 846 int search_endproj_in_stack(ir_node *start_block)
 847 {
 848   int i, j;
 849   assert(is_Block(start_block));
 850   for(i = tos - 1; i >= 0; --i)
 851   {
 852     DDMN(stack[i]);
 853     if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
 854        get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
 855     {
 856       printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
 857       ir_node *end_projx = stack[i];
 858
 859       int arity = get_irn_arity(start_block);
 860       for(j = 0; j < arity; j++)
 861       {
 862         ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
 863                                                  get_Proj_proj(end_projx));
 864         DDMN(begin_projx);
 865         if(get_irn_n(start_block, j) == begin_projx)
 866               {
 867                 printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
 868                 return(j);
 869               }
 870       }
 871     }
 872   }
 873   return(-1);
 874 }
 875
 876
 877 static pmap *projx_link = NULL;
 878
 879 void link_to_reg_end (ir_node *n, void *env) {
 880   if(get_irn_op(n) == op_Proj &&
 881      get_irn_mode(n) == mode_X &&
 882      get_irn_op(get_irn_n(n, 0)) == op_EndReg) {
 883       /* Reg End Projx -> Find the CallBegin Projx and hash it */
 884       ir_node *end_projx = n;
 885       ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
 886                                                get_Proj_proj(end_projx));
 887       printf("Linked the following ProjxNodes:\n");
 888       DDMN(begin_projx);
 889       DDMN(end_projx);
 890       set_projx_link(begin_projx, end_projx);
 891     }
 892 }
 893
 894 void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
 895 {
 896   if(projx_link == NULL)
 897     projx_link = pmap_create();
 898   pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
 899 }
 900
 901 ir_node *get_projx_link(ir_node *cb_projx)
 902 {
 903   return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
 904 }
 905
 906 #endif
 907
 908 static INLINE int
 909 is_outermost_loop(ir_loop *l) {
 910   return l == get_loop_outer_loop(l);
 911 }
 912
 913
 914 /*-----------------------------------------------------------*
 915  *                   The core algorithm.                     *
 916  *-----------------------------------------------------------*/
 917
 918 static void scc (ir_node *n) {
 919   int i;
 920   if (irn_visited(n)) return;
 921   mark_irn_visited(n);
 922
 923   /* Initialize the node */
 924   set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
 925   set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
 926   set_irn_loop(n, NULL);
 927   current_dfn ++;
 928   push(n);
 929
 930   /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
 931      array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
 932      so is_backedge does not access array[-1] but correctly returns false! */
 933
 934   if (!is_outermost_Start(n)) {
 935     int arity = get_irn_arity(n);
 936
 937     for (i = get_start_index(n); i < arity; i++) {
 938       ir_node *m;
 939       if (is_backedge(n, i)) continue;
 940       m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
 941       /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
 942       scc (m);
 943       if (irn_is_in_stack(m)) {
 944         /* Uplink of m is smaller if n->m is a backedge.
 945            Propagate the uplink to mark the loop. */
 946         if (get_irn_uplink(m) < get_irn_uplink(n))
 947           set_irn_uplink(n, get_irn_uplink(m));
 948       }
 949     }
 950   }
 951
 952   if (get_irn_dfn(n) == get_irn_uplink(n)) {
 953     /* This condition holds for
 954        1) the node with the incoming backedge.
 955           That is: We found a loop!
 956        2) Straight line code, because no uplink has been propagated, so the
 957           uplink still is the same as the dfn.
 958
 959        But n might not be a proper loop head for the analysis. Proper loop
 960        heads are Block and Phi nodes. find_tail searches the stack for
 961        Block's and Phi's and takes those nodes as loop heads for the current
 962        loop instead and marks the incoming edge as backedge. */
 963
 964     ir_node *tail = find_tail(n);
 965     if (tail) {
 966       /* We have a loop, that is no straight line code,
 967          because we found a loop head!
 968          Next actions: Open a new loop on the loop tree and
 969                        try to find inner loops */
 970
 971 #if NO_LOOPS_WITHOUT_HEAD
 972       /* This is an adaption of the algorithm from fiasco / optscc to
 973        * avoid loops without Block or Phi as first node.  This should
 974        * severely reduce the number of evaluations of nodes to detect
 975        * a fixpoint in the heap analysis.
 976        * Further it avoids loops without firm nodes that cause errors
 977        * in the heap analyses.
 978        * But attention:  don't do it for the outermost loop:  This loop
 979        * is not iterated.  A first block can be a loop head in case of
 980        * an endless recursion. */
 981
 982       ir_loop *l;
 983       int close;
 984       if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
 985         l = new_loop();
 986         close = 1;
 987       } else {
 988         l = current_loop;
 989         close = 0;
 990       }
 991 #else
 992       ir_loop *l = new_loop();
 993 #endif
 994
 995       /* Remove the loop from the stack ... */
 996       pop_scc_unmark_visit (n);
 997
 998       /* The current backedge has been marked, that is temporarily eliminated,
 999          by find tail. Start the scc algorithm
1000          anew on the subgraph that is left (the current loop without the backedge)
1001          in order to find more inner loops. */
1002       scc (tail);
1003
1004       assert (irn_visited(n));
1005 #if NO_LOOPS_WITHOUT_HEAD
1006       if (close)
1007 #endif
1008         close_loop(l);
1009     }
1010     else
1011     {
1012       /* No loop head was found, that is we have straightline code.
1013          Pop all nodes from the stack to the current loop. */
1014       pop_scc_to_loop(n);
1015     }
1016   }
1017 }
1018
1019 static void my_scc (ir_node *n) {
1020   int i;
1021   if (irn_visited(n)) return;
1022   mark_irn_visited(n);
1023
1024   /* Initialize the node */
1025   set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
1026   set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
1027   set_irn_loop(n, NULL);
1028   current_dfn ++;
1029   push(n);
1030
1031   /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
1032      array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
1033      so is_backedge does not access array[-1] but correctly returns false! */
1034
1035   if (!is_outermost_Start(n)) {
1036     int arity = get_irn_arity(n);
1037
1038     for (i = get_start_index(n); i < arity; i++) {
1039       ir_node *m;
1040       if (is_backedge(n, i)) continue;
1041       m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
1042       /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
1043       my_scc (m);
1044       if (irn_is_in_stack(m)) {
1045         /* Uplink of m is smaller if n->m is a backedge.
1046            Propagate the uplink to mark the loop. */
1047         if (get_irn_uplink(m) < get_irn_uplink(n))
1048           set_irn_uplink(n, get_irn_uplink(m));
1049       }
1050     }
1051   }
1052
1053   if (get_irn_dfn(n) == get_irn_uplink(n)) {
1054     /* This condition holds for
1055        1) the node with the incoming backedge.
1056           That is: We found a loop!
1057        2) Straight line code, because no uplink has been propagated, so the
1058           uplink still is the same as the dfn.
1059
1060        But n might not be a proper loop head for the analysis. Proper loop
1061        heads are Block and Phi nodes. find_tail searches the stack for
1062        Block's and Phi's and takes those nodes as loop heads for the current
1063        loop instead and marks the incoming edge as backedge. */
1064
1065     ir_node *tail = find_tail(n);
1066     if (tail) {
1067       /* We have a loop, that is no straight line code,
1068          because we found a loop head!
1069          Next actions: Open a new loop on the loop tree and
1070                        try to find inner loops */
1071
1072 #if NO_LOOPS_WITHOUT_HEAD
1073       /* This is an adaption of the algorithm from fiasco / optscc to
1074        * avoid loops without Block or Phi as first node.  This should
1075        * severely reduce the number of evaluations of nodes to detect
1076        * a fixpoint in the heap analysis.
1077        * Further it avoids loops without firm nodes that cause errors
1078        * in the heap analyses. */
1079
1080       ir_loop *l;
1081       int close;
1082       if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
1083         l = new_loop();
1084         close = 1;
1085       } else {
1086         l = current_loop;
1087         close = 0;
1088       }
1089 #else
1090       ir_loop *l = new_loop();
1091 #endif
1092
1093       /* Remove the loop from the stack ... */
1094       pop_scc_unmark_visit (n);
1095
1096       /* The current backedge has been marked, that is temporarily eliminated,
1097          by find tail. Start the scc algorithm
1098          anew on the subgraph that is left (the current loop without the backedge)
1099          in order to find more inner loops. */
1100       my_scc (tail);
1101
1102       assert (irn_visited(n));
1103 #if NO_LOOPS_WITHOUT_HEAD
1104       if (close)
1105 #endif
1106         close_loop(l);
1107     }
1108     else
1109     {
1110       /* No loop head was found, that is we have straightline code.
1111          Pop all nodes from the stack to the current loop. */
1112       pop_scc_to_loop(n);
1113     }
1114   }
1115 }
1116
1117 /* Constructs backedge information for irg. In interprocedural view constructs
1118    backedges for all methods called by irg, too. */
1119 int construct_backedges(ir_graph *irg) {
1120   ir_graph *rem = current_ir_graph;
1121   ir_loop *head_rem;
1122
1123   assert(!get_interprocedural_view() &&
1124      "not implemented, use construct_ip_backedges");
1125
1126   max_loop_depth = 0;
1127   current_ir_graph   = irg;
1128   outermost_ir_graph = irg;
1129
1130   init_scc(current_ir_graph);
1131
1132   current_loop = NULL;
1133   new_loop();  /* sets current_loop */
1134   head_rem = current_loop; /* Just for assertion */
1135
1136   inc_irg_visited(current_ir_graph);
1137
1138   scc(get_irg_end(current_ir_graph));
1139
1140   assert(head_rem == current_loop);
1141   set_irg_loop(current_ir_graph, current_loop);
1142   set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
1143   assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
1144   /*
1145   irg->loops = current_loop;
1146   if (icfg == 1) {
1147     int count = 0;
1148     int depth = 0;
1149     count_loop (the_loop, &count, &depth);
1150     }
1151   }
1152   */
1153   current_ir_graph = rem;
1154
1155   return max_loop_depth;
1156 }
1157
1158
1159 int construct_ip_backedges (void) {
1160   ir_graph *rem = current_ir_graph;
1161   int rem_ipv = get_interprocedural_view();
1162   int i;
1163
1164   max_loop_depth = 0;
1165   assert(get_irp_ip_view_state() == ip_view_valid);
1166
1167   outermost_ir_graph = get_irp_main_irg();
1168
1169   init_ip_scc();
1170
1171   current_loop = NULL;
1172   new_loop();  /* sets current_loop */
1173   set_interprocedural_view(1);
1174
1175   inc_max_irg_visited();
1176   for (i = 0; i < get_irp_n_irgs(); i++)
1177     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1178
1179   /** We have to start the walk at the same nodes as cg_walk. **/
1180   /* Walk starting at unreachable procedures. Only these
1181    * have End blocks visible in interprocedural view. */
1182   for (i = 0; i < get_irp_n_irgs(); i++) {
1183     ir_node *sb;
1184     current_ir_graph = get_irp_irg(i);
1185
1186     sb = get_irg_start_block(current_ir_graph);
1187
1188     if ((get_Block_n_cfgpreds(sb) > 1) ||
1189     (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1190
1191     scc(get_irg_end(current_ir_graph));
1192   }
1193
1194   /* Check whether we walked all procedures: there could be procedures
1195      with cyclic calls but no call from the outside. */
1196   for (i = 0; i < get_irp_n_irgs(); i++) {
1197     ir_node *sb;
1198     current_ir_graph = get_irp_irg(i);
1199
1200     /* Test start block: if inner procedure end and end block are not
1201      * visible and therefore not marked. */
1202     sb = get_irg_start_block(current_ir_graph);
1203     if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1204   }
1205
1206   /* Walk all endless loops in inner procedures.
1207    * We recognize an inner procedure if the End node is not visited. */
1208   for (i = 0; i < get_irp_n_irgs(); i++) {
1209     ir_node *e;
1210     current_ir_graph = get_irp_irg(i);
1211
1212     e = get_irg_end(current_ir_graph);
1213     if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1214       int j;
1215       /* Don't visit the End node. */
1216       for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1217     }
1218   }
1219
1220   set_irg_loop(outermost_ir_graph, current_loop);
1221   set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1222   assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1223
1224   current_ir_graph = rem;
1225   set_interprocedural_view(rem_ipv);
1226   return max_loop_depth;
1227 }
1228
1229 void my_construct_ip_backedges (void) {
1230   ir_graph *rem = current_ir_graph;
1231   int rem_ipv = get_interprocedural_view();
1232   int i;
1233
1234   assert(get_irp_ip_view_state() == ip_view_valid);
1235
1236   outermost_ir_graph = get_irp_main_irg();
1237
1238   init_ip_scc();
1239
1240   current_loop = NULL;
1241   new_loop();  /* sets current_loop */
1242   set_interprocedural_view(1);
1243
1244   inc_max_irg_visited();
1245   for (i = 0; i < get_irp_n_irgs(); i++)
1246     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1247
1248   /** We have to start the walk at the same nodes as cg_walk. **/
1249   /* Walk starting at unreachable procedures. Only these
1250    * have End blocks visible in interprocedural view. */
1251   for (i = 0; i < get_irp_n_irgs(); i++) {
1252     ir_node *sb;
1253     current_ir_graph = get_irp_irg(i);
1254
1255     sb = get_irg_start_block(current_ir_graph);
1256
1257     if ((get_Block_n_cfgpreds(sb) > 1) ||
1258     (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1259
1260     my_scc(get_irg_end(current_ir_graph));
1261   }
1262
1263   /* Check whether we walked all procedures: there could be procedures
1264      with cyclic calls but no call from the outside. */
1265   for (i = 0; i < get_irp_n_irgs(); i++) {
1266     ir_node *sb;
1267     current_ir_graph = get_irp_irg(i);
1268
1269     /* Test start block: if inner procedure end and end block are not
1270      * visible and therefore not marked. */
1271     sb = get_irg_start_block(current_ir_graph);
1272     if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1273   }
1274
1275   /* Walk all endless loops in inner procedures.
1276    * We recognize an inner procedure if the End node is not visited. */
1277   for (i = 0; i < get_irp_n_irgs(); i++) {
1278     ir_node *e;
1279     current_ir_graph = get_irp_irg(i);
1280
1281     e = get_irg_end(current_ir_graph);
1282     if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1283       int j;
1284       /* Don't visit the End node. */
1285       for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1286     }
1287   }
1288
1289   set_irg_loop(outermost_ir_graph, current_loop);
1290   set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1291   assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1292
1293   current_ir_graph = rem;
1294   set_interprocedural_view(rem_ipv);
1295 }
1296
1297 static void reset_backedges(ir_node *n) {
1298   if (is_possible_loop_head(n)) {
1299     int rem = get_interprocedural_view();
1300
1301     set_interprocedural_view(1);
1302     clear_backedges(n);
1303     set_interprocedural_view(1);
1304     clear_backedges(n);
1305     set_interprocedural_view(rem);
1306   }
1307 }
1308
1309
1310 /*
1311 static void loop_reset_backedges(ir_loop *l) {
1312   int i;
1313   reset_backedges(get_loop_node(l, 0));
1314   for (i = 0; i < get_loop_n_nodes(l); ++i)
1315     set_irn_loop(get_loop_node(l, i), NULL);
1316   for (i = 0; i < get_loop_n_sons(l); ++i) {
1317     loop_reset_backedges(get_loop_son(l, i));
1318   }
1319 }
1320 */
1321
1322 static void loop_reset_node(ir_node *n, void *env) {
1323   set_irn_loop(n, NULL);
1324   reset_backedges(n);
1325 }
1326
1327
1328 /** Removes all loop information.
1329     Resets all backedges */
1330 void free_loop_information(ir_graph *irg) {
1331   /* We can not use this recursion, as the loop might contain
1332      illegal nodes by now.  Why else would we throw away the
1333      representation?
1334   if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1335   */
1336   irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1337   set_irg_loop(irg, NULL);
1338   set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1339   /* We cannot free the loop nodes, they are on the obstack. */
1340 }
1341
1342
1343 void free_all_loop_information (void) {
1344   int i;
1345   int rem = get_interprocedural_view();
1346   set_interprocedural_view(1);  /* To visit all filter nodes */
1347   for (i = 0; i < get_irp_n_irgs(); i++) {
1348     free_loop_information(get_irp_irg(i));
1349   }
1350   set_interprocedural_view(rem);
1351 }
1352
1353
1354
1355
1356
1357 /* Debug stuff *************************************************/
1358
1359 static int test_loop_node(ir_loop *l) {
1360   int i, has_node = 0, found_problem = 0;
1361   loop_element le;
1362
1363   assert(l && l->kind == k_ir_loop);
1364
1365   if (get_loop_n_elements(l) == 0) {
1366     printf(" Loop completely empty! "); DDML(l);
1367     found_problem = 1;
1368     dump_loop(l, "-ha");
1369   }
1370
1371   le = get_loop_element(l, 0);
1372   if (*(le.kind) != k_ir_node) {
1373     assert(le.kind && *(le.kind) == k_ir_loop);
1374     printf(" First loop element is not a node! "); DDML(l);
1375     printf("                                   "); DDML(le.son);
1376
1377     found_problem = 1;
1378     dump_loop(l, "-ha");
1379   }
1380
1381   if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1382     printf(" Wrong node as head! "); DDML(l);
1383     printf("                     "); DDMN(le.node);
1384     found_problem = 1;
1385     dump_loop(l, "-ha");
1386   }
1387
1388   if ((get_loop_depth(l) != 0) &&
1389       (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1390     printf(" Loop head has no backedges! "); DDML(l);
1391     printf("                             "); DDMN(le.node);
1392     found_problem = 1;
1393     dump_loop(l, "-ha");
1394   }
1395
1396   /* Recur */
1397   has_node = 0;
1398   for (i = 0; i < get_loop_n_elements(l); ++i) {
1399     le = get_loop_element(l, i);
1400     if (*(le.kind) == k_ir_node)
1401       has_node++;
1402     else
1403       if (test_loop_node(le.son)) found_problem = 1;
1404   }
1405
1406   if (has_node == 0) {
1407     printf(" Loop has no firm node! "); DDML(l);
1408     found_problem = 1;
1409     dump_loop(l, "-ha");
1410   }
1411
1412   return found_problem;
1413 }
1414
1415 /** Prints all loop nodes that
1416  *  - do not have any firm nodes, only loop sons
1417  *  - the header is not a Phi, Block or Filter.
1418  */
1419 void find_strange_loop_nodes(ir_loop *l) {
1420   int found_problem = 0;
1421   printf("\nTesting loop "); DDML(l);
1422   found_problem = test_loop_node(l);
1423   printf("Finished Test\n\n");
1424   if (found_problem) exit(0);
1425
1426 }
1427
1428 /* ------------------------------------------------------------------- */
1429 /* Simple analyses based on the loop information                       */
1430 /* ------------------------------------------------------------------- */
1431
1432 int is_loop_variant(ir_loop *l, ir_loop *b) {
1433   int i, n_elems;
1434
1435   if (l == b) return 1;
1436
1437   n_elems = get_loop_n_elements(l);
1438   for (i = 0; i < n_elems; ++i) {
1439     loop_element e = get_loop_element(l, i);
1440     if (is_ir_loop(e.kind))
1441       if (is_loop_variant(e.son, b))
1442         return 1;
1443   }
1444
1445   return 0;
1446 }
1447
1448 /* Test whether a value is loop invariant.
1449  *
1450  * @param n      The node to be tested.
1451  * @param block  A block node.  We pass the block, not the loop as we must
1452  *               start off with a block loop to find all proper uses.
1453  *
1454  * Returns non-zero, if the node n is not changed in the loop block
1455  * belongs to or in inner loops of this blocks loop. */
1456 int is_loop_invariant(ir_node *n, ir_node *block) {
1457   ir_loop *l = get_irn_loop(block);
1458   ir_node *b = (is_Block(n)) ? n : get_nodes_block(n);
1459   return !is_loop_variant(l, get_irn_loop(b));
1460 }