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