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 isnt`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 isnt`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 apropriate "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 (get_kind(thing) == k_ir_loop);
 499 }
 500
 501 /* The outermost loop is remarked in the surrounding graph. */
 502 void     set_irg_loop(ir_graph *irg, ir_loop *loop) {
 503   assert(irg);
 504   irg->loop = loop;
 505 }
 506 ir_loop *get_irg_loop(ir_graph *irg) {
 507   assert(irg);
 508   return irg->loop;
 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 experimantal 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
 920 static void scc (ir_node *n) {
 921   int i;
 922   if (irn_visited(n)) return;
 923   mark_irn_visited(n);
 924
 925   /* Initialize the node */
 926   set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
 927   set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
 928   set_irn_loop(n, NULL);
 929   current_dfn ++;
 930   push(n);
 931
 932   /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
 933      array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
 934      so is_backedge does not access array[-1] but correctly returns false! */
 935
 936   if (!is_outermost_Start(n)) {
 937     int arity = get_irn_arity(n);
 938
 939     for (i = get_start_index(n); i < arity; i++) {
 940       ir_node *m;
 941       if (is_backedge(n, i)) continue;
 942       m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
 943       /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
 944       scc (m);
 945       if (irn_is_in_stack(m)) {
 946         /* Uplink of m is smaller if n->m is a backedge.
 947            Propagate the uplink to mark the loop. */
 948         if (get_irn_uplink(m) < get_irn_uplink(n))
 949           set_irn_uplink(n, get_irn_uplink(m));
 950       }
 951     }
 952   }
 953
 954   if (get_irn_dfn(n) == get_irn_uplink(n)) {
 955     /* This condition holds for
 956        1) the node with the incoming backedge.
 957           That is: We found a loop!
 958        2) Straight line code, because no uplink has been propagated, so the
 959           uplink still is the same as the dfn.
 960
 961        But n might not be a proper loop head for the analysis. Proper loop
 962        heads are Block and Phi nodes. find_tail searches the stack for
 963        Block's and Phi's and takes those nodes as loop heads for the current
 964        loop instead and marks the incoming edge as backedge. */
 965
 966     ir_node *tail = find_tail(n);
 967     if (tail) {
 968       /* We have a loop, that is no straight line code,
 969          because we found a loop head!
 970          Next actions: Open a new loop on the loop tree and
 971                        try to find inner loops */
 972
 973 #if NO_LOOPS_WITHOUT_HEAD
 974       /* This is an adaption of the algorithm from fiasco / optscc to
 975        * avoid loops without Block or Phi as first node.  This should
 976        * severely reduce the number of evaluations of nodes to detect
 977        * a fixpoint in the heap analysis.
 978        * Further it avoids loops without firm nodes that cause errors
 979        * in the heap analyses.
 980        * But attention:  don't do it for the outermost loop:  This loop
 981        * is not iterated.  A first block can be a loop head in case of
 982        * an endless recursion. */
 983
 984       ir_loop *l;
 985       int close;
 986       if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
 987         l = new_loop();
 988         close = 1;
 989       } else {
 990         l = current_loop;
 991         close = 0;
 992       }
 993 #else
 994       ir_loop *l = new_loop();
 995 #endif
 996
 997       /* Remove the loop from the stack ... */
 998       pop_scc_unmark_visit (n);
 999
1000       /* The current backedge has been marked, that is temporarily eliminated,
1001          by find tail. Start the scc algorithm
1002          anew on the subgraph thats left (the current loop without the backedge)
1003          in order to find more inner loops. */
1004       scc (tail);
1005
1006       assert (irn_visited(n));
1007 #if NO_LOOPS_WITHOUT_HEAD
1008       if (close)
1009 #endif
1010         close_loop(l);
1011     }
1012     else
1013       {
1014         /* No loop head was found, that is we have straightline code.
1015            Pop all nodes from the stack to the current loop. */
1016       pop_scc_to_loop(n);
1017     }
1018   }
1019 }
1020
1021 static void my_scc (ir_node *n) {
1022   int i;
1023   if (irn_visited(n)) return;
1024   mark_irn_visited(n);
1025
1026   /* Initialize the node */
1027   set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
1028   set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
1029   set_irn_loop(n, NULL);
1030   current_dfn ++;
1031   push(n);
1032
1033   /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
1034      array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
1035      so is_backedge does not access array[-1] but correctly returns false! */
1036
1037   if (!is_outermost_Start(n)) {
1038     int arity = get_irn_arity(n);
1039
1040     for (i = get_start_index(n); i < arity; i++) {
1041       ir_node *m;
1042       if (is_backedge(n, i)) continue;
1043       m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
1044       /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
1045       my_scc (m);
1046       if (irn_is_in_stack(m)) {
1047         /* Uplink of m is smaller if n->m is a backedge.
1048            Propagate the uplink to mark the loop. */
1049         if (get_irn_uplink(m) < get_irn_uplink(n))
1050           set_irn_uplink(n, get_irn_uplink(m));
1051       }
1052     }
1053   }
1054
1055   if (get_irn_dfn(n) == get_irn_uplink(n)) {
1056     /* This condition holds for
1057        1) the node with the incoming backedge.
1058           That is: We found a loop!
1059        2) Straight line code, because no uplink has been propagated, so the
1060           uplink still is the same as the dfn.
1061
1062        But n might not be a proper loop head for the analysis. Proper loop
1063        heads are Block and Phi nodes. find_tail searches the stack for
1064        Block's and Phi's and takes those nodes as loop heads for the current
1065        loop instead and marks the incoming edge as backedge. */
1066
1067     ir_node *tail = find_tail(n);
1068     if (tail) {
1069       /* We have a loop, that is no straight line code,
1070          because we found a loop head!
1071          Next actions: Open a new loop on the loop tree and
1072                        try to find inner loops */
1073
1074 #if NO_LOOPS_WITHOUT_HEAD
1075       /* This is an adaption of the algorithm from fiasco / optscc to
1076        * avoid loops without Block or Phi as first node.  This should
1077        * severely reduce the number of evaluations of nodes to detect
1078        * a fixpoint in the heap analysis.
1079        * Further it avoids loops without firm nodes that cause errors
1080        * in the heap analyses. */
1081
1082       ir_loop *l;
1083       int close;
1084       if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
1085         l = new_loop();
1086         close = 1;
1087       } else {
1088         l = current_loop;
1089         close = 0;
1090       }
1091 #else
1092       ir_loop *l = new_loop();
1093 #endif
1094
1095       /* Remove the loop from the stack ... */
1096       pop_scc_unmark_visit (n);
1097
1098       /* The current backedge has been marked, that is temporarily eliminated,
1099          by find tail. Start the scc algorithm
1100          anew on the subgraph thats left (the current loop without the backedge)
1101          in order to find more inner loops. */
1102       my_scc (tail);
1103
1104       assert (irn_visited(n));
1105 #if NO_LOOPS_WITHOUT_HEAD
1106       if (close)
1107 #endif
1108         close_loop(l);
1109     }
1110     else
1111       {
1112         /* No loop head was found, that is we have straightline code.
1113            Pop all nodes from the stack to the current loop. */
1114       pop_scc_to_loop(n);
1115     }
1116   }
1117 }
1118
1119 /* Constructs backedge information for irg. In interprocedural view constructs
1120    backedges for all methods called by irg, too. */
1121 int construct_backedges(ir_graph *irg) {
1122   ir_graph *rem = current_ir_graph;
1123   ir_loop *head_rem;
1124
1125   assert(!get_interprocedural_view() &&
1126      "not implemented, use construct_ip_backedges");
1127
1128   max_loop_depth = 0;
1129   current_ir_graph   = irg;
1130   outermost_ir_graph = irg;
1131
1132   init_scc(current_ir_graph);
1133
1134   current_loop = NULL;
1135   new_loop();  /* sets current_loop */
1136   head_rem = current_loop; /* Just for assertion */
1137
1138   inc_irg_visited(current_ir_graph);
1139
1140   scc(get_irg_end(current_ir_graph));
1141
1142   assert(head_rem == current_loop);
1143   set_irg_loop(current_ir_graph, current_loop);
1144   set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
1145   assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
1146   /*
1147   irg->loops = current_loop;
1148   if (icfg == 1) {
1149     int count = 0;
1150     int depth = 0;
1151     count_loop (the_loop, &count, &depth);
1152     }
1153   }
1154   */
1155   current_ir_graph = rem;
1156
1157   return max_loop_depth;
1158 }
1159
1160
1161 int construct_ip_backedges (void) {
1162   ir_graph *rem = current_ir_graph;
1163   int rem_ipv = get_interprocedural_view();
1164   int i;
1165
1166   max_loop_depth = 0;
1167   assert(get_irp_ip_view_state() == ip_view_valid);
1168
1169   outermost_ir_graph = get_irp_main_irg();
1170
1171   init_ip_scc();
1172
1173   current_loop = NULL;
1174   new_loop();  /* sets current_loop */
1175   set_interprocedural_view(true);
1176
1177   inc_max_irg_visited();
1178   for (i = 0; i < get_irp_n_irgs(); i++)
1179     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1180
1181   /** We have to start the walk at the same nodes as cg_walk. **/
1182   /* Walk starting at unreachable procedures. Only these
1183    * have End blocks visible in interprocedural view. */
1184   for (i = 0; i < get_irp_n_irgs(); i++) {
1185     ir_node *sb;
1186     current_ir_graph = get_irp_irg(i);
1187
1188     sb = get_irg_start_block(current_ir_graph);
1189
1190     if ((get_Block_n_cfgpreds(sb) > 1) ||
1191     (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1192
1193     scc(get_irg_end(current_ir_graph));
1194   }
1195
1196   /* Check whether we walked all procedures: there could be procedures
1197      with cyclic calls but no call from the outside. */
1198   for (i = 0; i < get_irp_n_irgs(); i++) {
1199     ir_node *sb;
1200     current_ir_graph = get_irp_irg(i);
1201
1202     /* Test start block: if inner procedure end and end block are not
1203      * visible and therefore not marked. */
1204     sb = get_irg_start_block(current_ir_graph);
1205     if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1206   }
1207
1208   /* Walk all endless loops in inner procedures.
1209    * We recognize an inner procedure if the End node is not visited. */
1210   for (i = 0; i < get_irp_n_irgs(); i++) {
1211     ir_node *e;
1212     current_ir_graph = get_irp_irg(i);
1213
1214     e = get_irg_end(current_ir_graph);
1215     if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1216       int j;
1217       /* Don't visit the End node. */
1218       for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1219     }
1220   }
1221
1222   set_irg_loop(outermost_ir_graph, current_loop);
1223   set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1224   assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1225
1226   current_ir_graph = rem;
1227   set_interprocedural_view(rem_ipv);
1228   return max_loop_depth;
1229 }
1230
1231 void my_construct_ip_backedges (void) {
1232   ir_graph *rem = current_ir_graph;
1233   int rem_ipv = get_interprocedural_view();
1234   int i;
1235
1236   assert(get_irp_ip_view_state() == ip_view_valid);
1237
1238   outermost_ir_graph = get_irp_main_irg();
1239
1240   init_ip_scc();
1241
1242   current_loop = NULL;
1243   new_loop();  /* sets current_loop */
1244   set_interprocedural_view(true);
1245
1246   inc_max_irg_visited();
1247   for (i = 0; i < get_irp_n_irgs(); i++)
1248     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1249
1250   /** We have to start the walk at the same nodes as cg_walk. **/
1251   /* Walk starting at unreachable procedures. Only these
1252    * have End blocks visible in interprocedural view. */
1253   for (i = 0; i < get_irp_n_irgs(); i++) {
1254     ir_node *sb;
1255     current_ir_graph = get_irp_irg(i);
1256
1257     sb = get_irg_start_block(current_ir_graph);
1258
1259     if ((get_Block_n_cfgpreds(sb) > 1) ||
1260     (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1261
1262     my_scc(get_irg_end(current_ir_graph));
1263   }
1264
1265   /* Check whether we walked all procedures: there could be procedures
1266      with cyclic calls but no call from the outside. */
1267   for (i = 0; i < get_irp_n_irgs(); i++) {
1268     ir_node *sb;
1269     current_ir_graph = get_irp_irg(i);
1270
1271     /* Test start block: if inner procedure end and end block are not
1272      * visible and therefore not marked. */
1273     sb = get_irg_start_block(current_ir_graph);
1274     if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1275   }
1276
1277   /* Walk all endless loops in inner procedures.
1278    * We recognize an inner procedure if the End node is not visited. */
1279   for (i = 0; i < get_irp_n_irgs(); i++) {
1280     ir_node *e;
1281     current_ir_graph = get_irp_irg(i);
1282
1283     e = get_irg_end(current_ir_graph);
1284     if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1285       int j;
1286       /* Don't visit the End node. */
1287       for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1288     }
1289   }
1290
1291   set_irg_loop(outermost_ir_graph, current_loop);
1292   set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1293   assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1294
1295   current_ir_graph = rem;
1296   set_interprocedural_view(rem_ipv);
1297 }
1298
1299 static void reset_backedges(ir_node *n) {
1300   if (is_possible_loop_head(n)) {
1301     int rem = get_interprocedural_view();
1302
1303     set_interprocedural_view(true);
1304     clear_backedges(n);
1305     set_interprocedural_view(true);
1306     clear_backedges(n);
1307     set_interprocedural_view(rem);
1308   }
1309 }
1310
1311
1312 /*
1313 static void loop_reset_backedges(ir_loop *l) {
1314   int i;
1315   reset_backedges(get_loop_node(l, 0));
1316   for (i = 0; i < get_loop_n_nodes(l); ++i)
1317     set_irn_loop(get_loop_node(l, i), NULL);
1318   for (i = 0; i < get_loop_n_sons(l); ++i) {
1319     loop_reset_backedges(get_loop_son(l, i));
1320   }
1321 }
1322 */
1323
1324 static void loop_reset_node(ir_node *n, void *env) {
1325   set_irn_loop(n, NULL);
1326   reset_backedges(n);
1327 }
1328
1329
1330 /** Removes all loop information.
1331     Resets all backedges */
1332 void free_loop_information(ir_graph *irg) {
1333   /* We can not use this recursion, as the loop might contain
1334      illegal nodes by now.  Why else would we throw away the
1335      representation?
1336   if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1337   */
1338   irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1339   set_irg_loop(irg, NULL);
1340   set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1341   /* We cannot free the loop nodes, they are on the obstack. */
1342 }
1343
1344
1345 void free_all_loop_information (void) {
1346   int i;
1347   int rem = get_interprocedural_view();
1348   set_interprocedural_view(true);  /* To visit all filter nodes */
1349   for (i = 0; i < get_irp_n_irgs(); i++) {
1350     free_loop_information(get_irp_irg(i));
1351   }
1352   set_interprocedural_view(rem);
1353 }
1354
1355
1356
1357
1358
1359 /* Debug stuff *************************************************/
1360
1361 static int test_loop_node(ir_loop *l) {
1362   int i, has_node = 0, found_problem = 0;
1363   loop_element le;
1364
1365   assert(l && l->kind == k_ir_loop);
1366
1367   if (get_loop_n_elements(l) == 0) {
1368     printf(" Loop completely empty! "); DDML(l);
1369     found_problem = 1;
1370     dump_loop(l, "-ha");
1371   }
1372
1373   le = get_loop_element(l, 0);
1374   if (*(le.kind) != k_ir_node) {
1375     assert(le.kind && *(le.kind) == k_ir_loop);
1376     printf(" First loop element is not a node! "); DDML(l);
1377     printf("                                   "); DDML(le.son);
1378
1379     found_problem = 1;
1380     dump_loop(l, "-ha");
1381   }
1382
1383   if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1384     printf(" Wrong node as head! "); DDML(l);
1385     printf("                     "); DDMN(le.node);
1386     found_problem = 1;
1387     dump_loop(l, "-ha");
1388   }
1389
1390   if ((get_loop_depth(l) != 0) &&
1391       (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1392     printf(" Loop head has no backedges! "); DDML(l);
1393     printf("                             "); DDMN(le.node);
1394     found_problem = 1;
1395     dump_loop(l, "-ha");
1396   }
1397
1398   /* Recur */
1399   has_node = 0;
1400   for (i = 0; i < get_loop_n_elements(l); ++i) {
1401     le = get_loop_element(l, i);
1402     if (*(le.kind) == k_ir_node)
1403       has_node++;
1404     else
1405       if (test_loop_node(le.son)) found_problem = 1;
1406   }
1407
1408   if (has_node == 0) {
1409     printf(" Loop has no firm node! "); DDML(l);
1410     found_problem = 1;
1411     dump_loop(l, "-ha");
1412   }
1413
1414   return found_problem;
1415 }
1416
1417 /** Prints all loop nodes that
1418  *  - do not have any firm nodes, only loop sons
1419  *  - the header is not a Phi, Block or Filter.
1420  */
1421 void find_strange_loop_nodes(ir_loop *l) {
1422   int found_problem = 0;
1423   printf("\nTesting loop "); DDML(l);
1424   found_problem = test_loop_node(l);
1425   printf("Finished Test\n\n");
1426   if (found_problem) exit(0);
1427
1428 }
1429
1430 /* ------------------------------------------------------------------- */
1431 /* Simple analyses based on the loop information                       */
1432 /* ------------------------------------------------------------------- */
1433
1434 int is_loop_variant(ir_loop *l, ir_loop *b) {
1435   int i, n_elems;
1436
1437   if (l == b) return true;
1438
1439   n_elems = get_loop_n_elements(l);
1440   for (i = 0; i < n_elems; ++i) {
1441     loop_element e = get_loop_element(l, i);
1442     if (is_ir_loop(e.kind))
1443       if (is_loop_variant(e.son, b))
1444         return true;
1445   }
1446
1447   return false;
1448 }
1449
1450 /* Test whether a value is loop invariant.
1451  *
1452  * @param n      The node to be tested.
1453  * @param block  A block node.  We pass the block, not the loop as we must
1454  *               start off with a block loop to find all proper uses.
1455  *
1456  * Returns true, if the node n is not changed in the loop block
1457  * belongs to or in inner loops of this blocks loop. */
1458 int is_loop_invariant(ir_node *n, ir_node *block) {
1459   ir_loop *l = get_irn_loop(block);
1460   ir_node *b = (is_Block(n)) ? n : get_nodes_block(n);
1461   return !is_loop_variant(l, get_irn_loop(b));
1462 }