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

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