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  * Author:      Goetz Lindenmaier
   7  * Modified by:
   8  * Created:     7.2002
   9  * CVS-ID:      $Id$
  10  * Copyright:   (c) 2002-2003 Universität Karlsruhe
  11  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  12  */
  13
  14 #ifdef HAVE_CONFIG_H
  15 #include "config.h"
  16 #endif
  17
  18 #include <string.h>
  19
  20 #include "irloop_t.h"
  21 #include "irnode.h"
  22 #include "irgraph_t.h"
  23 #include "array.h"
  24 #include "pmap.h"
  25 #include "irgwalk.h"
  26 #include "irprog.h"
  27
  28 ir_graph *outermost_ir_graph;      /* The outermost graph the scc is computed
  29                                       for */
  30 static ir_loop *current_loop;      /* Current loop construction is working
  31                                       on. */
  32 static int loop_node_cnt = 0;      /* Counts the number of allocated loop nodes.
  33                                       Each loop node gets a unique number.
  34                                       What for? ev. remove. @@@ */
  35 static int current_dfn = 1;        /* Counter to generate depth first numbering
  36                                       of visited nodes.  */
  37
  38 /**********************************************************************/
  39 /* Node attributes                                                   **/
  40 /**********************************************************************/
  41
  42 /* A map to get from irnodes to loop nodes. */
  43 static pmap *node_loop_map = NULL;
  44
  45 /**********************************************************************/
  46 /* Node attributes needed for the construction.                      **/
  47 /**********************************************************************/
  48
  49 typedef struct scc_info {
  50   bool in_stack;         /* Marks whether node is on the stack. */
  51   int dfn;               /* Depth first search number. */
  52   int uplink;            /* dfn number of ancestor. */
  53   //  ir_loop *loop;         /* Refers to the containing loop. */
  54   /*
  55       struct section *section;
  56       xset def;
  57       xset use;
  58   */
  59 } scc_info;
  60
  61 static INLINE scc_info* new_scc_info(void) {
  62   scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
  63   memset (info, 0, sizeof (scc_info));
  64   return info;
  65 }
  66
  67 static INLINE void
  68 mark_irn_in_stack (ir_node *n) {
  69   assert(get_irn_link(n));
  70   ((scc_info *)get_irn_link(n))->in_stack = true;
  71 }
  72
  73 static INLINE void
  74 mark_irn_not_in_stack (ir_node *n) {
  75   assert(get_irn_link(n));
  76   ((scc_info *)get_irn_link(n))->in_stack = false;
  77 }
  78
  79 static INLINE bool
  80 irn_is_in_stack (ir_node *n) {
  81   assert(get_irn_link(n));
  82   return ((scc_info *)get_irn_link(n))->in_stack;
  83 }
  84
  85 static INLINE void
  86 set_irn_uplink (ir_node *n, int uplink) {
  87   assert(get_irn_link(n));
  88   ((scc_info *)get_irn_link(n))->uplink = uplink;
  89 }
  90
  91 static INLINE int
  92 get_irn_uplink (ir_node *n) {
  93   assert(get_irn_link(n));
  94   return ((scc_info *)get_irn_link(n))->uplink;
  95 }
  96
  97 static INLINE void
  98 set_irn_dfn (ir_node *n, int dfn) {
  99   if (! get_irn_link(n)) { DDMN(n); DDME(get_irg_ent(current_ir_graph));}
 100   assert(get_irn_link(n));
 101   ((scc_info *)get_irn_link(n))->dfn = dfn;
 102 }
 103
 104 static INLINE int
 105 get_irn_dfn (ir_node *n) {
 106   assert(get_irn_link(n));
 107   return ((scc_info *)get_irn_link(n))->dfn;
 108 }
 109
 110 /* Uses temporary information to set the loop */
 111 static INLINE void
 112 set_irn_loop (ir_node *n, ir_loop* loop) {
 113   //assert(get_irn_link(n));
 114   //((scc_info *)get_irn_link(n))->loop = loop;
 115   assert(node_loop_map && "not initialized!");
 116   pmap_insert(node_loop_map, (void *)n, (void *)loop);
 117 }
 118
 119 /* Uses temporary information to get the loop */
 120 INLINE ir_loop *
 121 get_irn_loop (ir_node *n) {
 122   ir_loop *res = NULL;
 123   //assert(get_irn_link(n));
 124   //return ((scc_info *)get_irn_link(n))->loop;
 125   assert(node_loop_map && "not initialized!");
 126
 127   if (pmap_contains(node_loop_map, (void *)n))
 128     res = (ir_loop *) pmap_get(node_loop_map, (void *)n);
 129
 130   return res;
 131 }
 132
 133 #if 0
 134 static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
 135   int i;
 136   ir_loop *res = NULL;
 137
 138   /* Test whether n is contained in this loop. */
 139   for (i = 0; i < get_loop_n_nodes(l); i++)
 140     if (n == get_loop_node(l, i)) return l;
 141
 142   /* Is this a leave in the loop tree? If so loop not found. */
 143   if (get_loop_n_sons(l) == 0) return NULL;
 144
 145   /* Else descend in the loop tree. */
 146   for (i = 0; i < get_loop_n_sons(l); i++) {
 147     res = find_nodes_loop(n, get_loop_son(l, i));
 148     if (res) break;
 149   }
 150   return res;
 151 }
 152
 153 /* @@@ temporary implementation, costly!!! */
 154 ir_loop * get_irn_loop(ir_node *n) {
 155   ir_loop *l = get_irg_loop(current_ir_graph);
 156   l = find_nodes_loop(n, l);
 157   return l;
 158 }
 159 #endif
 160
 161 /**********************************************************************/
 162 /* A stack.                                                          **/
 163 /**********************************************************************/
 164
 165 static ir_node **stack = NULL;
 166 static int tos = 0;                /* top of stack */
 167
 168 static INLINE void init_stack(void) {
 169   if (stack) {
 170     ARR_RESIZE (ir_node *, stack, 1000);
 171   } else {
 172     stack = NEW_ARR_F (ir_node *, 1000);
 173   }
 174   tos = 0;
 175 }
 176
 177 #if 0
 178 static INLINE void free_stack(void) {
 179   DEL_ARR_F(stack);
 180   stack = NULL;
 181   tos = 0;
 182 }
 183 #endif
 184
 185 static INLINE void
 186 push (ir_node *n)
 187 {
 188   /*DDMN(n);*/
 189
 190   if (tos == ARR_LEN (stack)) {
 191     int nlen = ARR_LEN (stack) * 2;
 192     ARR_RESIZE (ir_node *, stack, nlen);
 193   }
 194   stack [tos++] = n;
 195   mark_irn_in_stack(n);
 196 }
 197
 198 static INLINE ir_node *
 199 pop (void)
 200 {
 201   ir_node *n = stack[--tos];
 202   mark_irn_not_in_stack(n);
 203   return n;
 204 }
 205
 206 /* The nodes up to n belong to the current loop.
 207    Removes them from the stack and adds them to the current loop. */
 208 static INLINE void
 209 pop_scc_to_loop (ir_node *n)
 210 {
 211   ir_node *m;
 212   int i = 0;
 213
 214   /*for (;;) {*/
 215   do
 216     {
 217     m = pop();
 218     loop_node_cnt++;
 219     set_irn_dfn(m, loop_node_cnt);
 220     add_loop_node(current_loop, m);
 221     set_irn_loop(m, current_loop);
 222     i++;
 223     /*    if (m==n) break;*/
 224     } while(m != n);
 225
 226   if(i > 1)
 227     printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
 228 }
 229
 230 /* GL ??? my last son is my grandson???  Removes loops with no
 231    ir_nodes in them.  Such loops have only another loop as son. (Why
 232    can't they have two loops as sons? Does it never get that far? ) */
 233 void close_loop (ir_loop *l)
 234 {
 235   int last = get_loop_n_elements(l) - 1;
 236   loop_element lelement = get_loop_element(l, last);
 237   ir_loop *last_son = lelement.son;
 238
 239   if (get_kind(last_son) == k_ir_loop &&
 240       get_loop_n_elements(last_son) == 1)
 241     {
 242       ir_loop *gson;
 243
 244       lelement = get_loop_element(last_son, 0);
 245       gson = lelement.son;
 246       if(get_kind(gson) == k_ir_loop)
 247         {
 248           loop_element new_last_son;
 249
 250           gson -> outer_loop = l;
 251           new_last_son.son = gson;
 252           l -> children[last] = new_last_son;
 253         }
 254     }
 255
 256   current_loop = l;
 257 }
 258
 259 /* Removes and unmarks all nodes up to n from the stack.
 260    The nodes must be visited once more to assign them to a scc. */
 261 static INLINE void
 262 pop_scc_unmark_visit (ir_node *n)
 263 {
 264   ir_node *m = NULL;
 265
 266   while (m != n) {
 267     m = pop();
 268     set_irn_visited(m, 0);
 269   }
 270 }
 271
 272 /**********************************************************************/
 273 /* The loop datastructure.                                           **/
 274 /**********************************************************************/
 275
 276 /* Allocates a new loop as son of current_loop.  Sets current_loop
 277    to the new loop and returns the father. */
 278 static ir_loop *new_loop (void) {
 279   ir_loop *father, *son;
 280
 281   father = current_loop;
 282
 283   son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
 284   memset (son, 0, sizeof (ir_loop));
 285   son->kind = k_ir_loop;
 286   son->children = NEW_ARR_F (loop_element, 0);
 287   son->n_nodes = 0;
 288   son->n_sons=0;
 289   if (father) {
 290     son->outer_loop = father;
 291     add_loop_son(father, son);
 292     son->depth = father->depth+1;
 293   } else {  /* The root loop */
 294     son->outer_loop = son;
 295     son->depth = 0;
 296   }
 297
 298   current_loop = son;
 299   return father;
 300 }
 301
 302 #if 0
 303 /* Finishes the datastructures, copies the arrays to the obstack
 304    of current_ir_graph.
 305    A. Schoesser: Caution: loop -> sons is gone. */
 306 static void mature_loop (ir_loop *loop) {
 307   ir_loop **new_sons;
 308
 309   new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
 310   memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
 311   DEL_ARR_F(loop->sons);
 312   loop->sons = new_sons;
 313 }
 314 #endif
 315
 316 /* Returns outer loop, itself if outermost. */
 317 ir_loop *get_loop_outer_loop (ir_loop *loop) {
 318   assert(loop && loop->kind == k_ir_loop);
 319   return loop->outer_loop;
 320 }
 321
 322 /* Returns nesting depth of this loop */
 323 int get_loop_depth (ir_loop *loop) {
 324   assert(loop); assert(loop->kind == k_ir_loop);
 325   return loop->depth;
 326 }
 327
 328 /* Returns the number of inner loops */
 329 int      get_loop_n_sons (ir_loop *loop) {
 330   assert(loop && loop->kind == k_ir_loop);
 331   return(loop -> n_sons);
 332 }
 333
 334 /* Returns the pos`th loop_node-child              *
 335  * TODO: This method isn`t very efficient !        *
 336  * Returns NULL if there isnt`t a pos`th loop_node */
 337 ir_loop *get_loop_son (ir_loop *loop, int pos) {
 338   int child_nr = 0, loop_nr = -1;
 339
 340   assert(loop && loop->kind == k_ir_loop);
 341   while(child_nr < ARR_LEN(loop->children))
 342    {
 343     if(*(loop -> children[child_nr].kind) == k_ir_loop)
 344       loop_nr++;
 345     if(loop_nr == pos)
 346       return(loop -> children[child_nr].son);
 347     child_nr++;
 348    }
 349   return NULL;
 350 }
 351
 352 /* Use EXCLUSIVELY this function to add sons, otherwise the loop->n_sons
 353    is invalid! */
 354
 355 static INLINE void
 356 add_loop_son(ir_loop *loop, ir_loop *son) {
 357   loop_element lson;
 358   lson.son = son;
 359   assert(loop && loop->kind == k_ir_loop);
 360   assert(get_kind(son) == k_ir_loop);
 361   ARR_APP1 (loop_element, loop->children, lson);
 362   loop -> n_sons++;
 363 }
 364
 365 /* Returns the number of nodes in the loop */
 366 int      get_loop_n_nodes (ir_loop *loop) {
 367   assert(loop); assert(loop->kind == k_ir_loop);
 368   return loop -> n_nodes;
 369 /*  return ARR_LEN(loop->nodes); */
 370 }
 371
 372 /* Returns the pos`th ir_node-child                *
 373  * TODO: This method isn`t very efficient !        *
 374  * Returns NULL if there isnt`t a pos`th ir_node   */
 375 ir_node *get_loop_node (ir_loop *loop, int pos) {
 376   int child_nr, node_nr = -1;
 377
 378   assert(loop && loop->kind == k_ir_loop);
 379   assert(pos < get_loop_n_nodes(loop));
 380
 381   for (child_nr = 0; child_nr < ARR_LEN(loop->children); child_nr++) {
 382     if(*(loop -> children[child_nr].kind) == k_ir_node)
 383       node_nr++;
 384     if(node_nr == pos)
 385       return(loop -> children[child_nr].node);
 386   }
 387   assert(0 && "no child at pos found");
 388   return NULL;
 389 }
 390
 391 /* Use EXCLUSIVELY this function to add nodes, otherwise the loop->n_nodes
 392    is invalid! */
 393
 394 static INLINE void
 395 add_loop_node(ir_loop *loop, ir_node *n) {
 396   loop_element ln;
 397   ln.node=n;
 398   assert(loop && loop->kind == k_ir_loop);
 399   assert(get_kind(n) == k_ir_node);
 400   ARR_APP1 (loop_element, loop->children, ln);
 401   loop->n_nodes++;
 402 }
 403
 404 /** Returns the number of elements contained in loop.  */
 405 int get_loop_n_elements (ir_loop *loop) {
 406   assert(loop && loop->kind == k_ir_loop);
 407   return(ARR_LEN(loop->children));
 408 }
 409
 410 /*
 411  Returns the pos`th loop element.
 412  This may be a loop_node or a ir_node. The caller of this function has
 413  to check the *(loop_element.kind) field for "k_ir_node" or "k_ir_loop"
 414  and then select the apropriate "loop_element.node" or "loop_element.son".
 415 */
 416
 417 loop_element get_loop_element (ir_loop *loop, int pos) {
 418   assert(loop && loop->kind == k_ir_loop && pos < ARR_LEN(loop->children));
 419
 420   return(loop -> children[pos]);
 421 }
 422
 423 /* The outermost loop is remarked in the surrounding graph. */
 424 void     set_irg_loop(ir_graph *irg, ir_loop *loop) {
 425   assert(irg);
 426   irg->loop = loop;
 427 }
 428 ir_loop *get_irg_loop(ir_graph *irg) {
 429   assert(irg);
 430   return irg->loop;
 431 }
 432
 433
 434 /**********************************************************************/
 435 /* Constructing and destructing the loop/backedge information.       **/
 436 /**********************************************************************/
 437
 438 /* Initialization steps. **********************************************/
 439
 440 static INLINE void
 441 init_node (ir_node *n, void *env) {
 442   set_irn_link (n, new_scc_info());
 443   clear_backedges(n);
 444 #if 0
 445   /* Also init nodes not visible in intraproc_view. */
 446     /* @@@ init_node is called for too many nodes -- this wastes memory!.
 447        The mem is not lost as its on the obstack. */
 448   if (get_irn_op(n) == op_Filter) {
 449     for (i = 0; i < get_Filter_n_cg_preds(n); i++)
 450       init_node(get_Filter_cg_pred(n, i), NULL);
 451   }
 452   if (get_irn_op(n) == op_Block) {
 453     for (i = 0; i < get_Block_cg_n_cfgpreds(n); i++) {
 454       init_node(get_Block_cg_cfgpred(n, i), NULL);
 455     }
 456   }
 457   /* The following pattern matches only after a call from above pattern. */
 458   if ((get_irn_op(n) == op_Proj) /*&& (get_Proj_proj(n) == 0)*/) {
 459     /* @@@ init_node is called for every proj -- this wastes memory!.
 460        The mem is not lost as its on the obstack. */
 461     ir_node *cb = get_Proj_pred(n);
 462     if ((get_irn_op(cb) == op_CallBegin) ||
 463         (get_irn_op(cb) == op_EndReg) ||
 464         (get_irn_op(cb) == op_EndExcept)) {
 465       init_node(cb, NULL);
 466       init_node(get_nodes_Block(cb), NULL);
 467     }
 468   }
 469 #endif
 470 }
 471
 472 static INLINE void
 473 init_scc_common (void) {
 474   current_dfn = 1;
 475   loop_node_cnt = 0;
 476   if (!node_loop_map) node_loop_map = pmap_create();
 477   init_stack();
 478 }
 479
 480 static INLINE void
 481 init_scc (ir_graph *irg) {
 482   init_scc_common();
 483   irg_walk_graph (irg, init_node, NULL, NULL);
 484   /*
 485   irg_walk (irg, link_to_reg_end, NULL, NULL);
 486   */
 487 }
 488
 489 static INLINE void
 490 init_ip_scc (void) {
 491   init_scc_common();
 492   cg_walk (init_node, NULL, NULL);
 493 }
 494
 495 #if 0
 496 Works, but is inefficient.
 497 static INLINE void
 498 init_ip_scc (void) {
 499   int i;
 500   interprocedural_view = 1;
 501   current_dfn = 1;
 502   loop_node_cnt = 0;
 503   init_stack();
 504   for (i = 0; i < get_irp_n_irgs(); i++) {
 505     current_ir_graph = get_irp_irg(i);
 506     irg_walk_graph (current_ir_graph, init_node, NULL, NULL);
 507     /* @@@ decrease max_visited to avoide double walks */
 508   }
 509 }
 510 #endif
 511
 512 /* Condition for breaking the recursion. */
 513 static bool is_outermost_Start(ir_node *n) {
 514   /* Test whether this is the outermost Start node.  If so
 515      recursion must end. */
 516   if ((get_irn_op(n) == op_Block)     &&
 517       (get_Block_n_cfgpreds(n) == 1)  &&
 518       (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
 519       (get_nodes_Block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
 520     return true;
 521   }
 522 #if 0
 523   /*  @@@ Bad condition:
 524       not possible in interprocedural view as outermost_graph is
 525       not necessarily the only with a dead-end start block.
 526       Besides current_ir_graph is not set properly. */
 527   if ((get_irn_op(n) == op_Block) &&
 528       (n == get_irg_start_block(current_ir_graph))) {
 529     if ((!interprocedural_view)  ||
 530         (current_ir_graph == outermost_ir_graph))
 531       return true;
 532   }
 533 #endif
 534   return false;
 535 }
 536
 537 /* Don't walk from nodes to blocks except for Control flow operations. */
 538 static INLINE int
 539 get_start_index(ir_node *n) {
 540   if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
 541     return -1;
 542   else
 543     return 0;
 544 }
 545
 546 /* Returns current_ir_graph and set it to the irg of predecessor index
 547    of node n. */
 548 static INLINE ir_graph *
 549 switch_irg (ir_node *n, int index) {
 550   ir_graph *old_current = current_ir_graph;
 551
 552   if (interprocedural_view) {
 553     /* Only Filter and Block nodes can have predecessors in other graphs. */
 554     if (get_irn_op(n) == op_Filter)
 555       n = get_nodes_Block(n);
 556     if (get_irn_op(n) == op_Block) {
 557       ir_node *cfop = skip_Proj(get_Block_cfgpred(n, index));
 558       if (is_ip_cfop(cfop)) {
 559         current_ir_graph = get_irn_irg(cfop);
 560         set_irg_visited(current_ir_graph, get_max_irg_visited());
 561       }
 562     }
 563   }
 564
 565   return old_current;
 566 }
 567
 568 /* Walks up the stack passing n and then finding the node
 569    where we walked into the irg n is contained in.
 570    Here we switch the irg. */
 571 static ir_graph *
 572 find_irg_on_stack (ir_node *n) {
 573   ir_node *m;
 574   ir_graph *old_current = current_ir_graph;
 575   int i;
 576
 577   if (interprocedural_view) {
 578     for (i = tos; i >= 0; i--) {
 579       if (stack[i] == n) break;
 580     }
 581     if (i < 0) i = tos;
 582
 583     assert (i >= 0);
 584     for (; i >= 0; i--) {
 585       m = stack[i];
 586       /*printf(" Visiting %d ", i); DDMN(m);*/
 587       if (is_ip_cfop(m)) {
 588         current_ir_graph = get_irn_irg(m);
 589         break;
 590       }
 591       if (get_irn_op(m) == op_Filter) {
 592         /* Find the corresponding ip_cfop */
 593         ir_node *pred = stack[i+1];
 594         int j;
 595         for (j = 0; j < get_Filter_n_cg_preds(m); j++)
 596           if (get_Filter_cg_pred(m, j) == pred) break;
 597         if (j >= get_Filter_n_cg_preds(m))
 598           /* It is a filter we didn't pass as the predecessors are marked. */
 599           continue;
 600         assert(get_Filter_cg_pred(m, j) == pred);
 601         switch_irg(m, j);
 602         break;
 603       }
 604     }
 605   }
 606
 607   return old_current;
 608 }
 609
 610 #if 0
 611 static void test(ir_node *pred, ir_node *root, ir_node *this) {
 612   int i;
 613   if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
 614
 615   printf("this: %d ", get_irn_uplink(this)); DDMN(this);
 616   printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
 617   printf("root: %d ", get_irn_uplink(root)); DDMN(root);
 618
 619   printf("tos: %d\n", tos);
 620
 621   for (i = tos; i >= 0; i--) {
 622     ir_node *n = stack[i];
 623     if (!n) continue;
 624     printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
 625   }
 626 }
 627 #endif
 628
 629 /* Test for legal loop header: Block, Phi, ... */
 630 INLINE static bool is_possible_loop_head(ir_node *n) {
 631   return ((get_irn_op(n) == op_Block) ||
 632           (get_irn_op(n) == op_Phi) ||
 633           ((get_irn_op(n) == op_Filter) && interprocedural_view));
 634 }
 635
 636 /* Returns true if n is a loop header, i.e., it is a Block, Phi
 637    or Filter node and has predecessors within the loop and out
 638    of the loop.
 639    @arg root: only needed for assertion. */
 640 static bool
 641 is_head (ir_node *n, ir_node *root)
 642 {
 643   int i;
 644   int some_outof_loop = 0, some_in_loop = 0;
 645
 646   /* Test for legal loop header: Block, Phi, ... */
 647   if (!is_possible_loop_head(n))
 648     return false;
 649
 650   if (!is_outermost_Start(n)) {
 651     for (i = get_start_index(n); i < get_irn_arity(n); i++) {
 652       ir_node *pred = get_irn_n(n, i);
 653       assert(pred);
 654       if (is_backedge(n, i)) continue;
 655       if (!irn_is_in_stack(pred)) {
 656         some_outof_loop = 1;
 657       } else {
 658         assert(get_irn_uplink(pred) >= get_irn_uplink(root));
 659         some_in_loop = 1;
 660       }
 661     }
 662   }
 663   return some_outof_loop && some_in_loop;
 664 }
 665
 666 /* Returns index of the predecessor with the smallest dfn number
 667    greater-equal than limit. */
 668 static int
 669 smallest_dfn_pred (ir_node *n, int limit)
 670 {
 671   int i, index = -2, min = -1;
 672
 673   if (!is_outermost_Start(n)) {
 674     for (i = get_start_index(n); i < get_irn_arity(n); i++) {
 675       ir_node *pred = get_irn_n(n, i);
 676       assert(pred);
 677       if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
 678       if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
 679         index = i;
 680         min = get_irn_dfn(pred);
 681       }
 682     }
 683   }
 684   return index;
 685 }
 686
 687 /* Returns index of the predecessor with the largest dfn number. */
 688 static int
 689 largest_dfn_pred (ir_node *n)
 690 {
 691   int i, index = -2, max = -1;
 692
 693   if (!is_outermost_Start(n)) {
 694     for (i = get_start_index(n); i < get_irn_arity(n); i++) {
 695       ir_node *pred = get_irn_n(n, i);
 696       if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
 697       if (get_irn_dfn(pred) > max) {
 698         index = i;
 699         max = get_irn_dfn(pred);
 700       }
 701     }
 702   }
 703   return index;
 704 }
 705
 706 /* Searches the stack for possible loop heads.  Tests these for backedges.
 707    If it finds a head with an unmarked backedge it marks this edge and
 708    returns the tail of the loop.
 709    If it finds no backedge returns NULL.
 710    ("disable_backedge" in fiasco) */
 711
 712 static ir_node *
 713 find_tail (ir_node *n) {
 714   ir_node *m;
 715   int i, res_index = -2;
 716
 717   /*
 718     if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
 719   */
 720
 721   m = stack[tos-1];  /* tos = top of stack */
 722   if (is_head (m, n)) {
 723     res_index = smallest_dfn_pred(m, 0);
 724     if ((res_index == -2) &&  /* no smallest dfn pred found. */
 725         (n == m))
 726       return NULL;
 727   } else {
 728     if (m == n) return NULL;
 729     for (i = tos-2; ; --i) {
 730       m = stack[i];
 731       if (is_head (m, n)) {
 732         res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
 733         if (res_index == -2)  /* no smallest dfn pred found. */
 734           res_index = largest_dfn_pred (m);
 735         break;
 736       }
 737     }
 738   }
 739   assert (res_index > -2);
 740
 741   set_backedge (m, res_index);
 742   return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
 743 }
 744
 745
 746 /* The core algorithm. *****************************************/
 747
 748 static void scc (ir_node *n) {
 749   int i;
 750   ir_graph *rem;
 751
 752   if (irn_visited(n)) return;
 753   mark_irn_visited(n);
 754   /*printf("mark: %d ", get_irn_visited(n)); DDMN(n);
 755   DDME(get_irg_ent(current_ir_graph));*/
 756
 757   /* Initialize the node */
 758   set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
 759   set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
 760   set_irn_loop(n, NULL);
 761   current_dfn ++;
 762
 763   /* What's this good for?
 764   n->ana.scc.section = NULL;
 765   */
 766
 767   push(n);
 768
 769   /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
 770      array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
 771      so is_backedge does not access array[-1] but correctly returns false! */
 772
 773   if (!is_outermost_Start(n)) {
 774     for (i = get_start_index(n); i < get_irn_arity(n); i++) {
 775       ir_node *m;
 776       if (is_backedge(n, i)) continue;
 777
 778       m = get_irn_n(n, i); /*get_irn_ip_pred(n, i);*/
 779       if ((!m) || (get_irn_op(m) == op_Unknown)) continue;
 780       scc (m);
 781       /*return_recur(n, i);*/
 782
 783       if (irn_is_in_stack(m)) {
 784         /* Uplink of m is smaller if n->m is a backedge.
 785            Propagate the uplink to mark the loop. */
 786         if (get_irn_uplink(m) < get_irn_uplink(n))
 787           set_irn_uplink(n, get_irn_uplink(m));
 788       }
 789     }
 790   }
 791
 792   if (get_irn_dfn(n) == get_irn_uplink(n)) {
 793     /* This condition holds for the node with the incoming backedge.
 794        AS: That is: For the loop head. */
 795     ir_node *tail = find_tail(n);
 796     if (tail) {
 797       /* We found a new inner loop! */
 798       ir_loop *l = new_loop();
 799
 800       /* Remove the loop from the stack ... */
 801       pop_scc_unmark_visit (n);
 802       /* and recompute it in a better order; and so that it goes into
 803          the new loop. */
 804       rem = find_irg_on_stack(tail);
 805
 806       scc (tail);
 807       current_ir_graph = rem;
 808
 809       assert (irn_visited(n));
 810       close_loop(l);
 811     } else {
 812       /* AS: No inner loop was found. Pop all nodes from the stack
 813          to the current loop. */
 814       pop_scc_to_loop(n);
 815     }
 816   }
 817 }
 818
 819 /* Constructs backedge information for irg. In interprocedural view constructs
 820    backedges for all methods called by irg, too. */
 821 void construct_backedges(ir_graph *irg) {
 822   ir_graph *rem = current_ir_graph;
 823   ir_loop *head_rem;
 824   int i;
 825
 826   assert(!interprocedural_view &&
 827          "not implemented, use construct_ip_backedges");
 828
 829   current_ir_graph = irg;
 830   outermost_ir_graph = irg;
 831
 832   init_scc(irg);
 833
 834   current_loop = NULL;
 835   new_loop();  /* sets current_loop */
 836   head_rem = current_loop; /* Just for assertion */
 837
 838   if (interprocedural_view) {
 839     set_irg_visited(irg, inc_max_irg_visited());
 840     init_ip_walk ();
 841   } else {
 842     inc_irg_visited(irg);
 843   }
 844
 845   scc(get_irg_end(irg));
 846   for (i = 0; i < get_End_n_keepalives(get_irg_end(irg)); i++)
 847     scc(get_End_keepalive(get_irg_end(irg), i));
 848
 849   if (interprocedural_view) finish_ip_walk();
 850
 851   assert(head_rem == current_loop);
 852   set_irg_loop(irg, current_loop);
 853   assert(get_irg_loop(irg)->kind == k_ir_loop);
 854   /*
 855   irg->loops = current_loop;
 856   if (icfg == 1) {
 857     int count = 0;
 858     int depth = 0;
 859     count_loop (the_loop, &count, &depth);
 860     }
 861   }
 862   */
 863   current_ir_graph = rem;
 864 }
 865
 866
 867
 868 void construct_ip_backedges (void) {
 869   ir_graph *rem = current_ir_graph;
 870   int rem_ipv = interprocedural_view;
 871   int i, j;
 872
 873   outermost_ir_graph = get_irp_main_irg();
 874
 875   init_ip_scc();
 876
 877   current_loop = NULL;
 878   new_loop();  /* sets current_loop */
 879   interprocedural_view = 1;
 880
 881   inc_max_irg_visited();
 882   for (i = 0; i < get_irp_n_irgs(); i++)
 883     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
 884
 885   for (i = 0; i < get_irp_n_irgs(); i++) {
 886     ir_node *sb;
 887     current_ir_graph = get_irp_irg(i);
 888     /*DDME(get_irg_ent(current_ir_graph));*/
 889     /* Find real entry points */
 890     sb = get_irg_start_block(current_ir_graph);
 891     if ((get_Block_n_cfgpreds(sb) > 1) ||
 892         (get_nodes_Block(get_Block_cfgpred(sb, 0)) != sb)) continue;
 893     /*    printf("running scc for "); DDME(get_irg_ent(current_ir_graph));   */
 894     /* Compute scc for this graph */
 895     outermost_ir_graph = current_ir_graph;
 896     set_irg_visited(outermost_ir_graph, get_max_irg_visited());
 897     scc(get_irg_end(current_ir_graph));
 898     for (j = 0; j < get_End_n_keepalives(get_irg_end(outermost_ir_graph)); j++)
 899       scc(get_End_keepalive(get_irg_end(outermost_ir_graph), j));
 900   }
 901
 902   set_irg_loop(outermost_ir_graph, current_loop);
 903   assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
 904
 905   current_ir_graph = rem;
 906   interprocedural_view = rem_ipv;
 907 }
 908
 909
 910 static void reset_backedges(ir_node *n, void *env) {
 911   if (is_possible_loop_head(n))
 912     clear_backedges(n);
 913 }
 914
 915 /** Removes all loop information.
 916     Resets all backedges */
 917 void free_loop_information(ir_graph *irg) {
 918   set_irg_loop(irg, NULL);
 919   /* We cannot free the loop nodes, they are on the obstack. */
 920   irg_walk_graph(irg, NULL, reset_backedges, NULL);
 921 }
 922
 923
 924 void free_all_loop_information (void) {
 925   int i;
 926   int rem = interprocedural_view;
 927   interprocedural_view = 1;  /* To visit all filter nodes */
 928   for (i = 0; i < get_irp_n_irgs(); i++) {
 929     free_loop_information(get_irp_irg(i));
 930   }
 931   pmap_destroy(node_loop_map);
 932   node_loop_map = NULL;
 933   interprocedural_view = rem;
 934 }