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

   1 /* Copyright (C) 2002 by Universitaet Karlsruhe
   2 * All rights reserved.
   3 *
   4 * Authors:  Goetz Lindenmaier
   5 *
   6 * irscc.c  Computing the strongly connected regions and building
   7 * backedge/loop datastructures.
   8 *
   9 */
  10
  11 /* $Id$ */
  12
  13 #include <string.h>
  14
  15 #include "irloop_t.h"
  16 #include "irnode.h"
  17 #include "irgraph_t.h"
  18 #include "array.h"
  19 #include "xprintf.h"
  20 #include "irgwalk.h"
  21 #include "irprog.h"
  22
  23 ir_graph *outermost_ir_graph;      /* The outermost graph the scc is computed
  24                                       for */
  25 static ir_loop *current_loop;      /* Current loop construction is working
  26                                       on. */
  27 static int loop_node_cnt = 0;      /* Counts the number of allocated loop nodes.
  28                                       Each loop node gets a unique number.
  29                                       What for? ev. remove. @@@ */
  30 static int current_dfn = 1;        /* Counter to generate depth first numbering
  31                                       of visited nodes.  */
  32
  33 /**********************************************************************/
  34 /* Node attributes needed for the construction.                      **/
  35 /**********************************************************************/
  36
  37 typedef struct scc_info {
  38   bool in_stack;         /* Marks whether node is on the stack. */
  39   int dfn;               /* Depth first search number. */
  40   int uplink;            /* dfn number of ancestor. */
  41   ir_loop *loop;         /* Refers to the containing loop. */
  42   /*
  43       struct section *section;
  44       xset def;
  45       xset use;
  46   */
  47 } scc_info;
  48
  49 static INLINE scc_info* new_scc_info() {
  50   scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
  51   memset (info, 0, sizeof (scc_info));
  52   return info;
  53 }
  54
  55 static INLINE void
  56 mark_irn_in_stack (ir_node *n) {
  57   assert(get_irn_link(n));
  58   ((scc_info *)get_irn_link(n))->in_stack = true;
  59 }
  60
  61 static INLINE void
  62 mark_irn_not_in_stack (ir_node *n) {
  63   assert(get_irn_link(n));
  64   ((scc_info *)get_irn_link(n))->in_stack = false;
  65 }
  66
  67 static INLINE bool
  68 irn_is_in_stack (ir_node *n) {
  69   assert(get_irn_link(n));
  70   return ((scc_info *)get_irn_link(n))->in_stack;
  71 }
  72
  73 static INLINE void
  74 set_irn_uplink (ir_node *n, int uplink) {
  75   assert(get_irn_link(n));
  76   ((scc_info *)get_irn_link(n))->uplink = uplink;
  77 }
  78
  79 static INLINE int
  80 get_irn_uplink (ir_node *n) {
  81   assert(get_irn_link(n));
  82   return ((scc_info *)get_irn_link(n))->uplink;
  83 }
  84
  85 static INLINE void
  86 set_irn_dfn (ir_node *n, int dfn) {
  87   if (! get_irn_link(n)) { DDMN(n); DDME(get_irg_ent(current_ir_graph));}
  88   assert(get_irn_link(n));
  89   ((scc_info *)get_irn_link(n))->dfn = dfn;
  90 }
  91
  92 static INLINE int
  93 get_irn_dfn (ir_node *n) {
  94   assert(get_irn_link(n));
  95   return ((scc_info *)get_irn_link(n))->dfn;
  96 }
  97
  98 /* Uses temporary information to set the loop */
  99 static INLINE void
 100 set_irn_loop_tmp (ir_node *n, ir_loop* loop) {
 101   assert(get_irn_link(n));
 102   ((scc_info *)get_irn_link(n))->loop = loop;
 103 }
 104
 105 /* Uses temporary information to get the loop */
 106 static INLINE ir_loop *
 107 get_irn_loop_tmp (ir_node *n) {
 108   assert(get_irn_link(n));
 109   return ((scc_info *)get_irn_link(n))->loop;
 110 }
 111
 112 static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
 113   int i;
 114   ir_loop *res = NULL;
 115
 116   /* Test whether n is contained in this loop. */
 117   for (i = 0; i < get_loop_n_nodes(l); i++)
 118     if (n == get_loop_node(l, i)) return l;
 119
 120   /* Is this a leave in the loop tree? If so loop not found. */
 121   if (get_loop_n_sons(l) == 0) return NULL;
 122
 123   /* Else descend in the loop tree. */
 124   for (i = 0; i < get_loop_n_sons(l); i++) {
 125     res = find_nodes_loop(n, get_loop_son(l, i));
 126     if (res) break;
 127   }
 128   return res;
 129 }
 130
 131 /* @@@ temporary implementation, costly!!! */
 132 ir_loop * get_irn_loop(ir_node *n) {
 133   ir_loop *l = get_irg_loop(current_ir_graph);
 134   l = find_nodes_loop(n, l);
 135   return l;
 136 }
 137
 138 /**********************************************************************/
 139 /* A stack.                                                          **/
 140 /**********************************************************************/
 141
 142 static ir_node **stack = NULL;
 143 static int tos = 0;                /* top of stack */
 144
 145 static INLINE void init_stack() {
 146   if (stack) {
 147     ARR_RESIZE (ir_node *, stack, 1000);
 148   } else {
 149     stack = NEW_ARR_F (ir_node *, 1000);
 150   }
 151   tos = 0;
 152 }
 153
 154 static INLINE void free_stack() {
 155   DEL_ARR_F(stack);
 156   stack = NULL;
 157   tos = 0;
 158 }
 159
 160 static INLINE void
 161 push (ir_node *n)
 162 {
 163   //DDMN(n);
 164
 165   if (tos == ARR_LEN (stack)) {
 166     int nlen = ARR_LEN (stack) * 2;
 167     ARR_RESIZE (ir_node *, stack, nlen);
 168   }
 169   stack [tos++] = n;
 170   mark_irn_in_stack(n);
 171 }
 172
 173 static INLINE ir_node *
 174 pop (void)
 175 {
 176   ir_node *n = stack[--tos];
 177   mark_irn_not_in_stack(n);
 178   return n;
 179 }
 180
 181 /* The nodes up to n belong to the current loop.
 182    Removes them from the stack and adds them to the current loop. */
 183 static INLINE void
 184 pop_scc_to_loop (ir_node *n)
 185 {
 186   ir_node *m;
 187
 188   for (;;) {
 189     m = pop();
 190     set_irn_dfn(m, loop_node_cnt);
 191     loop_node_cnt++;
 192     add_loop_node(current_loop, m);
 193     set_irn_loop_tmp(m, current_loop);
 194     if (m==n) break;
 195   }
 196 }
 197
 198 /* Removes and unmarks all nodes up to n from the stack.
 199    The nodes must be visited once more to assign them to a scc. */
 200 static INLINE void
 201 pop_scc_unmark_visit (ir_node *n)
 202 {
 203   ir_node *m = NULL;
 204
 205   while (m != n) {
 206     m = pop();
 207     set_irn_visited(m, 0);
 208   }
 209 }
 210
 211 /**********************************************************************/
 212 /* The loop datastructure.                                           **/
 213 /**********************************************************************/
 214
 215 /* Allocates a new loop as son of current_loop.  Sets current_loop
 216    to the new loop and returns the father. */
 217 static ir_loop *new_loop (void) {
 218   ir_loop *father, *son;
 219
 220   father = current_loop;
 221
 222   son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
 223   memset (son, 0, sizeof (ir_loop));
 224   son->kind = k_ir_loop;
 225   son->sons = NEW_ARR_F (ir_loop *, 0);
 226   son->nodes = NEW_ARR_F (ir_node *, 0);
 227   if (father) {
 228     son->outer_loop = father;
 229     add_loop_son(father, son);
 230     son->depth = father->depth+1;
 231   } else {  /* The root loop */
 232     son->outer_loop = son;
 233     son->depth = 0;
 234   }
 235
 236   current_loop = son;
 237   return father;
 238 }
 239
 240 /* Finishes the datastructures, copies the arrays to the obstack
 241    of current_ir_graph. */
 242 static void mature_loop (ir_loop *loop) {
 243   ir_loop **new_sons;
 244   ir_node **new_nods;
 245
 246   new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
 247   memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
 248   DEL_ARR_F(loop->sons);
 249   loop->sons = new_sons;
 250 }
 251
 252 /* Returns outer loop, itself if outermost. */
 253 ir_loop *get_loop_outer_loop (ir_loop *loop) {
 254   assert(loop && loop->kind == k_ir_loop);
 255   return loop->outer_loop;
 256 }
 257
 258 /* Returns nesting depth of this loop */
 259 int get_loop_depth (ir_loop *loop) {
 260   assert(loop); assert(loop->kind == k_ir_loop);
 261   return loop->depth;
 262 }
 263
 264 /* Returns the number of inner loops */
 265 int      get_loop_n_sons (ir_loop *loop) {
 266   assert(loop && loop->kind == k_ir_loop);
 267   return ARR_LEN(loop->sons);
 268 }
 269 ir_loop *get_loop_son (ir_loop *loop, int pos) {
 270   assert(loop && loop->kind == k_ir_loop);
 271   return loop->sons[pos];
 272 }
 273 static INLINE void
 274 add_loop_son(ir_loop *loop, ir_loop *son) {
 275   assert(loop && loop->kind == k_ir_loop);
 276   ARR_APP1 (ir_loop *, loop->sons, son);
 277 }
 278
 279 /* Returns the number of nodes in the loop */
 280 int      get_loop_n_nodes (ir_loop *loop) {
 281   assert(loop); assert(loop->kind == k_ir_loop);
 282   return ARR_LEN(loop->nodes);
 283 }
 284 ir_node *get_loop_node (ir_loop *loop, int pos) {
 285   assert(loop && loop->kind == k_ir_loop);
 286   return loop->nodes[pos];
 287 }
 288 static INLINE void
 289 add_loop_node(ir_loop *loop, ir_node *n) {
 290   assert(loop && loop->kind == k_ir_loop);
 291   ARR_APP1 (ir_node *, loop->nodes, n);
 292 }
 293
 294 /* The outermost loop is remarked in the surrounding graph. */
 295 void     set_irg_loop(ir_graph *irg, ir_loop *loop) {
 296   assert(irg);
 297   irg->loop = loop;
 298 }
 299 ir_loop *get_irg_loop(ir_graph *irg) {
 300   assert(irg);
 301   return irg->loop;
 302 }
 303
 304 /**********************************************************************/
 305 /* Constructing and destructing the loop/backedge information.       **/
 306 /**********************************************************************/
 307
 308 /* Initialization steps. **********************************************/
 309
 310 static INLINE void
 311 init_node (ir_node *n, void *env) {
 312   int i;
 313   set_irn_link (n, new_scc_info());
 314   clear_backedges(n);
 315 #if 0
 316   /* Also init nodes not visible in intraproc_view. */
 317     /* @@@ init_node is called for too many nodes -- this wastes memory!.
 318        The mem is not lost as its on the obstack. */
 319   if (get_irn_op(n) == op_Filter) {
 320     for (i = 0; i < get_Filter_n_cg_preds(n); i++)
 321       init_node(get_Filter_cg_pred(n, i), NULL);
 322   }
 323   if (get_irn_op(n) == op_Block) {
 324     for (i = 0; i < get_Block_cg_n_cfgpreds(n); i++) {
 325       init_node(get_Block_cg_cfgpred(n, i), NULL);
 326     }
 327   }
 328   /* The following pattern matches only after a call from above pattern. */
 329   if ((get_irn_op(n) == op_Proj) /*&& (get_Proj_proj(n) == 0)*/) {
 330     /* @@@ init_node is called for every proj -- this wastes memory!.
 331        The mem is not lost as its on the obstack. */
 332     ir_node *cb = get_Proj_pred(n);
 333     if ((get_irn_op(cb) == op_CallBegin) ||
 334         (get_irn_op(cb) == op_EndReg) ||
 335         (get_irn_op(cb) == op_EndExcept)) {
 336       init_node(cb, NULL);
 337       init_node(get_nodes_Block(cb), NULL);
 338     }
 339 #endif
 340 }
 341
 342 static INLINE void
 343 init_scc (ir_graph *irg) {
 344   current_dfn = 1;
 345   loop_node_cnt = 0;
 346   init_stack();
 347   irg_walk_graph (irg, init_node, NULL, NULL);
 348   /*
 349   irg_walk (irg, link_to_reg_end, NULL, NULL);
 350   */
 351 }
 352
 353 static INLINE void
 354 init_ip_scc () {
 355   current_dfn = 1;
 356   loop_node_cnt = 0;
 357   init_stack();
 358   cg_walk (init_node, NULL, NULL);
 359 }
 360
 361 #if 0
 362 Works, but is inefficient.
 363 static INLINE void
 364 init_ip_scc () {
 365   int i;
 366   interprocedural_view = 1;
 367   current_dfn = 1;
 368   loop_node_cnt = 0;
 369   init_stack();
 370   for (i = 0; i < get_irp_n_irgs(); i++) {
 371     current_ir_graph = get_irp_irg(i);
 372     irg_walk_graph (current_ir_graph, init_node, NULL, NULL);
 373     /* @@@ decrease max_visited to avoide double walks */
 374   }
 375 }
 376 #endif
 377
 378 /* Condition for breaking the recursion. */
 379 static bool is_outermost_Start(ir_node *n) {
 380   /* Test whether this is the outermost Start node.  If so
 381      recursion must end. */
 382   if ((get_irn_op(n) == op_Block)     &&
 383       (get_Block_n_cfgpreds(n) == 1)  &&
 384       (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
 385       (get_nodes_Block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
 386     return true;
 387   }
 388 #if 0
 389   /*  @@@ Bad condition:
 390       not possible in interprocedural view as outermost_graph is
 391       not necessarily the only with a dead-end start block.
 392       Besides current_ir_graph is not set properly. */
 393   if ((get_irn_op(n) == op_Block) &&
 394       (n == get_irg_start_block(current_ir_graph))) {
 395     if ((!interprocedural_view)  ||
 396         (current_ir_graph == outermost_ir_graph))
 397       return true;
 398   }
 399 #endif
 400   return false;
 401 }
 402
 403 /* Don't walk from nodes to blocks except for Control flow operations. */
 404 static INLINE int
 405 get_start_index(ir_node *n) {
 406   if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
 407     return -1;
 408   else
 409     return 0;
 410 }
 411
 412 /* Returns current_ir_graph and set it to the irg of predecessor index
 413    of node n. */
 414 static INLINE ir_graph *
 415 switch_irg (ir_node *n, int index) {
 416   ir_graph *old_current = current_ir_graph;
 417
 418   if (interprocedural_view) {
 419     /* Only Filter and Block nodes can have predecessors in other graphs. */
 420     if (get_irn_op(n) == op_Filter)
 421       n = get_nodes_Block(n);
 422     if (get_irn_op(n) == op_Block) {
 423       ir_node *cfop = skip_Proj(get_Block_cfgpred(n, index));
 424       if (is_ip_cfop(cfop)) {
 425         current_ir_graph = get_irn_irg(cfop);
 426         set_irg_visited(current_ir_graph, get_max_irg_visited());
 427       }
 428     }
 429   }
 430
 431   return old_current;
 432 }
 433
 434 /* Walks up the stack passing n and then finding the node
 435    where we walked into the irg n is contained in.
 436    Here we switch the irg. */
 437 static ir_graph *
 438 find_irg_on_stack (ir_node *n) {
 439   ir_node *m;
 440   ir_graph *old_current = current_ir_graph;
 441   int i;
 442
 443   if (interprocedural_view) {
 444     for (i = tos; i >= 0; i--) {
 445       if (stack[i] == n) break;
 446     }
 447     if (i < 0) i = tos;
 448
 449     //printf(" Here\n");
 450
 451     assert (i >= 0);
 452     for (; i >= 0; i--) {
 453       m = stack[i];
 454       //printf(" Visiting %d ", i); DDMN(m);
 455       if (is_ip_cfop(m)) {
 456         current_ir_graph = get_irn_irg(m);
 457         break;
 458       }
 459       if (get_irn_op(m) == op_Filter) {
 460         /* Find the corresponding ip_cfop */
 461         ir_node *pred = stack[i+1];
 462         int j;
 463         for (j = 0; j < get_Filter_n_cg_preds(m); j++)
 464           if (get_Filter_cg_pred(m, j) == pred) break;
 465         if (j >= get_Filter_n_cg_preds(m))
 466           /* It is a filter we didn't pass as the predecessors are marked. */
 467           continue;
 468         assert(get_Filter_cg_pred(m, j) == pred);
 469         switch_irg(m, j);
 470         break;
 471       }
 472     }
 473   }
 474
 475   return old_current;
 476 }
 477
 478 static void test(ir_node *pred, ir_node *root, ir_node *this) {
 479   int i;
 480   if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
 481
 482   printf("this: %d ", get_irn_uplink(this)); DDMN(this);
 483   printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
 484   printf("root: %d ", get_irn_uplink(root)); DDMN(root);
 485
 486   printf("tos: %d\n", tos);
 487
 488   for (i = tos; i >= 0; i--) {
 489     ir_node *n = stack[i];
 490     if (!n) continue;
 491     printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
 492   }
 493 }
 494
 495 /* Returns true if n is a loop header, i.e., it is a Block, Phi
 496    or Filter node and has predecessors within the loop and out
 497    of the loop. */
 498 static bool
 499 is_head (ir_node *n, ir_node *root)
 500 {
 501   int i;
 502   int some_outof_loop = 0,  some_in_loop = 0;
 503
 504   /* Test for legal loop header */
 505   if (!((get_irn_op(n) == op_Block) ||
 506         (get_irn_op(n) == op_Phi) ||
 507         ((get_irn_op(n) == op_Filter) && interprocedural_view)))
 508     return false;
 509
 510   if (!is_outermost_Start(n)) {
 511     for (i = get_start_index(n); i < get_irn_arity(n); i++) {
 512       ir_node *pred = get_irn_n(n, i);
 513       assert(pred);
 514       if (is_backedge(n, i)) continue;
 515       if (!irn_is_in_stack(pred)) {
 516         some_outof_loop = 1;
 517       } else {
 518         assert(get_irn_uplink(pred) >= get_irn_uplink(root));
 519         some_in_loop = 1;
 520       }
 521     }
 522   }
 523   return some_outof_loop && some_in_loop;
 524 }
 525
 526 /* Returns index of the predecessor with the smallest dfn number
 527    greater-equal than limit. */
 528 static int
 529 smallest_dfn_pred (ir_node *n, int limit)
 530 {
 531   int i, index = -2, min = -1;
 532
 533   if (!is_outermost_Start(n)) {
 534     for (i = get_start_index(n); i < get_irn_arity(n); i++) {
 535       ir_node *pred = get_irn_n(n, i);
 536       assert(pred);
 537       if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
 538       if (get_irn_dfn(pred) >= limit
 539         && (min == -1 || get_irn_dfn(pred) < min)) {
 540         index = i;
 541         min = get_irn_dfn(pred);
 542       }
 543     }
 544   }
 545   return index;
 546 }
 547
 548 /* Returns index of the predecessor with the largest dfn number. */
 549 static int
 550 largest_dfn_pred (ir_node *n)
 551 {
 552   int i, index = -2, max = -1;
 553
 554   if (!is_outermost_Start(n)) {
 555     for (i = get_start_index(n); i < get_irn_arity(n); i++) {
 556       ir_node *pred = get_irn_n(n, i);
 557       if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
 558       if (get_irn_dfn(pred) > max) {
 559         index = i;
 560         max = get_irn_dfn(pred);
 561       }
 562     }
 563   }
 564   return index;
 565 }
 566
 567 /* Searches the stack for possible loop heads.  Tests these for backedges.
 568    If it finds a head with an unmarked backedge it marks this edge and
 569    returns the tail of the loop.
 570    If it finds no backedge returns NULL. */
 571 static ir_node *
 572 find_tail (ir_node *n) {
 573   ir_node *m;
 574   int i, res_index = -2;
 575
 576   /*
 577     if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
 578   */
 579
 580   m = stack[tos-1];
 581   if (is_head (m, n)) {
 582     res_index = smallest_dfn_pred(m, 0);
 583     if ((res_index == -2) &&  /* no smallest dfn pred found. */
 584         (n == m))
 585       return NULL;
 586   } else {
 587     if (m == n) return NULL;
 588     for (i = tos-2; ; --i) {
 589       m = stack[i];
 590       if (is_head (m, n)) {
 591         res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
 592         if (res_index == -2)  /* no smallest dfn pred found. */
 593           res_index = largest_dfn_pred (m);
 594         break;
 595       }
 596     }
 597   }
 598   assert (res_index > -2);
 599
 600   set_backedge (m, res_index);
 601   return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
 602 }
 603
 604
 605 /* The core algorithm. *****************************************/
 606
 607 static void scc (ir_node *n) {
 608   int i;
 609   ir_graph *rem;
 610
 611   if (irn_visited(n)) return;
 612   mark_irn_visited(n);
 613   //printf("mark: %d ", get_irn_visited(n)); DDMN(n);
 614   //DDME(get_irg_ent(current_ir_graph));
 615
 616   /* Initialize the node */
 617   set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
 618   set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
 619   set_irn_loop_tmp(n, NULL);
 620   current_dfn ++;
 621
 622   /* What's this good for?
 623   n->ana.scc.section = NULL;
 624   */
 625
 626   push(n);
 627
 628   if (!is_outermost_Start(n)) {
 629     for (i = get_start_index(n); i < get_irn_arity(n); i++) {
 630       ir_node *m;
 631       if (is_backedge(n, i)) continue;
 632
 633       m = get_irn_n(n, i); //get_irn_ip_pred(n, i);
 634       if ((!m) || (get_irn_op(m) == op_Unknown)) continue;
 635       scc (m);
 636       //return_recur(n, i);
 637
 638       if (irn_is_in_stack(m)) {
 639         /* Uplink of m is smaller if n->m is a backedge.
 640            Propagate the uplink to mark the loop. */
 641         if (get_irn_uplink(m) < get_irn_uplink(n))
 642           set_irn_uplink(n, get_irn_uplink(m));
 643       }
 644     }
 645   }
 646   if (get_irn_dfn(n) == get_irn_uplink(n)) {
 647     /* This condition holds for the node with the incoming backedge. */
 648     ir_node *tail = find_tail(n);
 649     if (tail) {
 650       /* We found a new loop! */
 651       ir_loop *l = new_loop();
 652       /* Remove the loop from the stack ... */
 653       pop_scc_unmark_visit (n);
 654       /* and recompute it in a better order; and so that it goes into
 655          the new loop. */
 656       rem = find_irg_on_stack(tail);
 657       scc (tail);
 658       current_ir_graph = rem;
 659
 660       assert (irn_visited(n));
 661
 662       current_loop = l;
 663     } else {
 664       pop_scc_to_loop(n);
 665     }
 666   }
 667 }
 668
 669 /* Constructs backedge information for irg. In interprocedural view constructs
 670    backedges for all methods called by irg, too. */
 671 void construct_backedges(ir_graph *irg) {
 672   ir_graph *rem = current_ir_graph;
 673   ir_loop *head_rem;
 674   int i;
 675
 676   assert(!interprocedural_view &&
 677          "not implemented, use construct_ip_backedges");
 678
 679   current_ir_graph = irg;
 680   outermost_ir_graph = irg;
 681
 682   init_scc(irg);
 683
 684   current_loop = NULL;
 685   new_loop();  /* sets current_loop */
 686   head_rem = current_loop; /* Just for assertion */
 687
 688   if (interprocedural_view) {
 689     set_irg_visited(irg, inc_max_irg_visited());
 690     init_ip_walk ();
 691   } else {
 692     inc_irg_visited(irg);
 693   }
 694
 695   scc(get_irg_end(irg));
 696   for (i = 0; i < get_End_n_keepalives(get_irg_end(irg)); i++)
 697     scc(get_End_keepalive(get_irg_end(irg), i));
 698
 699   if (interprocedural_view) finish_ip_walk();
 700
 701   assert(head_rem == current_loop);
 702   set_irg_loop(irg, current_loop);
 703   assert(get_irg_loop(irg)->kind == k_ir_loop);
 704   /*
 705   irg->loops = current_loop;
 706   if (icfg == 1) {
 707     int count = 0;
 708     int depth = 0;
 709     count_loop (the_loop, &count, &depth);
 710     }
 711   }
 712   */
 713   current_ir_graph = rem;
 714 }
 715
 716
 717
 718 void construct_ip_backedges () {
 719   ir_graph *rem = current_ir_graph;
 720   int rem_ipv = interprocedural_view;
 721   int i, j;
 722
 723   outermost_ir_graph = get_irp_main_irg();
 724
 725   init_ip_scc();
 726
 727   current_loop = NULL;
 728   new_loop();  /* sets current_loop */
 729   interprocedural_view = 1;
 730
 731   inc_max_irg_visited();
 732   for (i = 0; i < get_irp_n_irgs(); i++)
 733     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
 734
 735   for (i = 0; i < get_irp_n_irgs(); i++) {
 736     ir_node *sb;
 737     current_ir_graph = get_irp_irg(i);
 738     //DDME(get_irg_ent(current_ir_graph));
 739     /* Find real entry points */
 740     sb = get_irg_start_block(current_ir_graph);
 741     if ((get_Block_n_cfgpreds(sb) > 1) ||
 742         (get_nodes_Block(get_Block_cfgpred(sb, 0)) != sb)) continue;
 743     //    printf("running scc for "); DDME(get_irg_ent(current_ir_graph));
 744     /* Compute scc for this graph */
 745     outermost_ir_graph = current_ir_graph;
 746     set_irg_visited(outermost_ir_graph, get_max_irg_visited());
 747     scc(get_irg_end(current_ir_graph));
 748     for (j = 0; j < get_End_n_keepalives(get_irg_end(outermost_ir_graph)); j++)
 749       scc(get_End_keepalive(get_irg_end(outermost_ir_graph), j));
 750   }
 751
 752   set_irg_loop(outermost_ir_graph, current_loop);
 753   assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
 754
 755   current_ir_graph = rem;
 756   interprocedural_view = rem_ipv;
 757 }