nsz Git - libfirm/blob - ir/ana/irscc.c

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