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

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