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

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ana/callgraph.c
   4  * Purpose:     Representation and computation of the callgraph.
   5  * Author:      Goetz Lindenmaier
   6  * Modified by:
   7  * Created:     21.7.2004
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 2004 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 #include "config.h"
  14 #include "callgraph.h"
  15
  16 #include "irloop_t.h"
  17 #include "irprog_t.h"
  18 #include "irgraph_t.h"
  19 #include "irnode_t.h"
  20
  21 #include "cgana.h"
  22
  23 #include "array.h"
  24 #include "pmap.h"
  25
  26 #include "irgwalk.h"
  27
  28 /* For callees, we want to remember the Call nodes, too. */
  29 struct ana_entry {
  30   ir_graph *irg;
  31   ir_node  *call_list;
  32   int       max_depth;
  33 };
  34
  35 typedef struct ana_entry ana_entry;
  36
  37 static int master_cg_visited = 0;
  38 static INLINE int  cg_irg_visited     (ir_graph *n);
  39 static INLINE void mark_cg_irg_visited(ir_graph *n);
  40 static INLINE void set_cg_irg_visited (ir_graph *n, int i);
  41
  42 irp_callgraph_state get_irp_callgraph_state(void) {
  43   return irp->callgraph_state;
  44 }
  45 void                set_irp_callgraph_state(irp_callgraph_state s) {
  46   irp->callgraph_state = s;
  47 }
  48
  49 /* The functions that call irg. */
  50 int       get_irg_n_callers(ir_graph *irg) {
  51   if (irg->callers) return ARR_LEN(irg->callers);
  52   return -1;
  53 }
  54 ir_graph *get_irg_caller(ir_graph *irg, int pos) {
  55   assert (pos >= 0 && pos < get_irg_n_callers(irg));
  56   if (irg->callers) return irg->callers[pos];
  57   return NULL;
  58 }
  59 int       is_irg_caller_backedge(ir_graph *irg, int pos) {
  60   assert (pos >= 0 && pos < get_irg_n_callers(irg));
  61   return  irg->caller_isbe[pos];
  62 }
  63
  64 static void       set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) {
  65   int i, n_callers = get_irg_n_callers(irg);
  66   for (i = 0; i < n_callers; ++i) {
  67     if (get_irg_caller(irg, i) == caller) {
  68       irg->caller_isbe[i] = 1;
  69       break;
  70     }
  71   }
  72 }
  73
  74 int       has_irg_caller_backedge(ir_graph *irg) {
  75   int i, n_callers = get_irg_n_callers(irg);
  76   for (i = 0; i < n_callers; ++i)
  77     if (is_irg_caller_backedge(irg, i)) return 1;
  78   return 0;
  79 }
  80
  81 int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
  82   ir_graph *caller = get_irg_caller(irg, pos);
  83
  84   /* search the other relation for the corresponding edge. */
  85   int pos_callee = -1;
  86   int i, n_callees = get_irg_n_callees(caller);
  87   for (i = 0; i < n_callees; ++i) {
  88     if (get_irg_callee(caller, i) == irg) {
  89       pos_callee = i;
  90       break;
  91     }
  92   }
  93
  94   assert(pos_callee >= 0);
  95
  96   return get_irg_callee_loop_depth(caller, pos_callee);
  97 }
  98
  99
 100 /* The functions called by irg. */
 101 int       get_irg_n_callees(ir_graph *irg) {
 102   if (irg->callees) return ARR_LEN(irg->callees);
 103   return -1;
 104 }
 105 ir_graph *get_irg_callee(ir_graph *irg, int pos) {
 106   assert (pos >= 0 && pos < get_irg_n_callees(irg));
 107   if (irg->callees) return ((ana_entry *)irg->callees[pos])->irg;
 108   return NULL;
 109 }
 110 int       is_irg_callee_backedge(ir_graph *irg, int pos) {
 111   assert (pos >= 0 && pos < get_irg_n_callees(irg));
 112   return irg->callee_isbe[pos];
 113 }
 114 int       has_irg_callee_backedge(ir_graph *irg) {
 115   int i, n_callees = get_irg_n_callees(irg);
 116   for (i = 0; i < n_callees; ++i)
 117     if (is_irg_callee_backedge(irg, i)) return 1;
 118   return 0;
 119 }
 120 void       set_irg_callee_backedge(ir_graph *irg, int pos) {
 121   assert (pos >= 0 && pos < get_irg_n_callees(irg));
 122   irg->callee_isbe[pos] = 1;
 123 }
 124
 125 int get_irg_callee_loop_depth(ir_graph *irg, int pos) {
 126   assert (pos >= 0 && pos < get_irg_n_callees(irg));
 127   if (irg->callees) return ((ana_entry *)irg->callees[pos])->max_depth;
 128   return -1;
 129 }
 130
 131 /* --------------------- Compute the callgraph ------------------------ */
 132
 133 /* Hash an address */
 134 #define HASH_ADDRESS(adr)       (((unsigned)(adr)) >> 3)
 135
 136 /**
 137  * Walker called by compute_callgraph()
 138  */
 139 static void ana_Call(ir_node *n, void *env) {
 140   int i, n_callees;
 141   ir_graph *irg;
 142
 143   if (get_irn_op(n) != op_Call) return;
 144
 145   irg = get_irn_irg(n);
 146   n_callees = get_Call_n_callees(n);
 147   for (i = 0; i < n_callees; ++i) {
 148     entity *callee_e = get_Call_callee(n, i);
 149     ir_graph *callee = get_entity_irg(callee_e);
 150     if (callee) {  /* For unknown caller */
 151       pset_insert((pset *)callee->callers, irg, (unsigned)irg >> 3);
 152       ana_entry buf = { callee, NULL, 0};
 153       ana_entry *found = pset_find((pset *)irg->callees, &buf, HASH_ADDRESS(callee));
 154       if (found) {  /* add Call node to list, compute new nesting. */
 155       } else { /* New node, add Call node and init nesting. */
 156         found = (ana_entry *) obstack_alloc (irg->obst, sizeof (ana_entry));
 157         found->irg = callee;
 158         found->call_list = NULL;
 159         found->max_depth = 0;
 160         pset_insert((pset *)irg->callees, found, HASH_ADDRESS(callee));
 161       }
 162       int depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
 163       found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
 164     }
 165   }
 166 }
 167
 168 /** compare two ir graphs in a ana_entry */
 169 static int ana_entry_cmp(const void *elt, const void *key) {
 170   const ana_entry *e1 = elt;
 171   const ana_entry *e2 = key;
 172   return e1->irg != e2->irg;
 173 }
 174
 175 /** compare two ir graphs */
 176 static int graph_cmp(const void *elt, const void *key) {
 177   return elt != key;
 178 }
 179
 180
 181 /* Construct and destruct the callgraph. */
 182 void compute_callgraph(void) {
 183   int i, n_irgs = get_irp_n_irgs();
 184
 185   assert(! get_interprocedural_view());  /* Else walking will not reach the Call nodes. */
 186
 187   /* initialize */
 188   free_callgraph();
 189   for (i = 0; i < n_irgs; ++i) {
 190     ir_graph *irg = get_irp_irg(i);
 191     assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
 192     irg->callees = (ir_graph **)new_pset(ana_entry_cmp, 8);
 193     irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
 194     construct_cf_backedges(irg);
 195   }
 196
 197   /* Compute the call graph */
 198   for (i = 0; i < n_irgs; ++i) {
 199     ir_graph *irg = get_irp_irg(i);
 200     construct_cf_backedges(irg);
 201     irg_walk_graph(irg, ana_Call, NULL, NULL);
 202   }
 203
 204   /* Change the sets to arrays. */
 205   for (i = 0; i < n_irgs; ++i) {
 206     int j, count;
 207     ir_graph *c, *irg = get_irp_irg(i);
 208
 209     pset *callee_set = (pset *)irg->callees;
 210     count = pset_count(callee_set);
 211     irg->callees = NEW_ARR_F(ir_graph *, count);
 212     irg->callee_isbe = calloc(count, sizeof(int));
 213     c = pset_first(callee_set);
 214     for (j = 0; j < count; ++j) {
 215       irg->callees[j] = c;
 216       c = pset_next(callee_set);
 217     }
 218     del_pset(callee_set);
 219     assert(c == NULL);
 220
 221     pset *caller_set = (pset *)irg->callers;
 222     count = pset_count(caller_set);
 223     irg->callers = NEW_ARR_F(ir_graph *, count);
 224     irg->caller_isbe =  calloc(count, sizeof(int));
 225     c = pset_first(caller_set);
 226     for (j = 0; j < count; ++j) {
 227       irg->callers[j] = c;
 228       c = pset_next(caller_set);
 229     }
 230     del_pset(caller_set);
 231     assert(c == NULL);
 232   }
 233   set_irp_callgraph_state(irp_callgraph_consistent);
 234 }
 235
 236 void free_callgraph(void) {
 237   int i, n_irgs = get_irp_n_irgs();
 238   for (i = 0; i < n_irgs; ++i) {
 239     ir_graph *irg = get_irp_irg(i);
 240     if (irg->callees) DEL_ARR_F(irg->callees);
 241     if (irg->callers) DEL_ARR_F(irg->callers);
 242     if (irg->callee_isbe) DEL_ARR_F(irg->callee_isbe);
 243     if (irg->caller_isbe) DEL_ARR_F(irg->caller_isbe);
 244     irg->callees = NULL;
 245     irg->callers = NULL;
 246     irg->callee_isbe = NULL;
 247     irg->caller_isbe = NULL;
 248   }
 249   set_irp_callgraph_state(irp_callgraph_none);
 250 }
 251
 252 /* ----------------------------------------------------------------------------------- */
 253 /* A walker for the callgraph                                                          */
 254 /* ----------------------------------------------------------------------------------- */
 255
 256
 257 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
 258   int i, n_callees;
 259
 260   if (cg_irg_visited(irg)) return;
 261   mark_cg_irg_visited(irg);
 262
 263   pre(irg, env);
 264
 265   n_callees = get_irg_n_callees(irg);
 266   for (i = 0; i < n_callees; i++) {
 267     ir_graph *m = get_irg_callee(irg, i);
 268     do_walk(m, pre, post, env);
 269   }
 270
 271   post(irg, env);
 272 }
 273
 274 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
 275   int i, n_irgs = get_irp_n_irgs();
 276   master_cg_visited++;
 277
 278   do_walk(get_irp_main_irg(), pre, post, env);
 279   for (i = 0; i < n_irgs; i++) {
 280     ir_graph *irg = get_irp_irg(i);
 281     if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
 282       do_walk(irg, pre, post, env);
 283   }
 284   for (i = 0; i < n_irgs; i++) {
 285     ir_graph *irg = get_irp_irg(i);
 286     if (!cg_irg_visited(irg))
 287       do_walk(irg, pre, post, env);
 288   }
 289 }
 290
 291 /* ----------------------------------------------------------------------------------- */
 292 /* loop construction algorithm                                                         */
 293 /* ----------------------------------------------------------------------------------- */
 294
 295 static ir_graph *outermost_ir_graph;      /* The outermost graph the scc is computed
 296                       for */
 297 static ir_loop *current_loop;      /* Current cfloop construction is working
 298                       on. */
 299 static int loop_node_cnt = 0;      /* Counts the number of allocated cfloop nodes.
 300                       Each cfloop node gets a unique number.
 301                       What for? ev. remove. @@@ */
 302 static int current_dfn = 1;        /* Counter to generate depth first numbering
 303                       of visited nodes.  */
 304
 305
 306 /**********************************************************************/
 307 /* Node attributes                                                   **/
 308 /**********************************************************************/
 309
 310 typedef struct scc_info {
 311   bool in_stack;         /* Marks whether node is on the stack. */
 312   int dfn;               /* Depth first search number. */
 313   int uplink;            /* dfn number of ancestor. */
 314   int visited;
 315 } scc_info;
 316
 317 static INLINE scc_info* new_scc_info(void) {
 318   scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
 319   memset (info, 0, sizeof (scc_info));
 320   return info;
 321 }
 322
 323 static INLINE int
 324 cg_irg_visited(ir_graph *n) {
 325   return (((scc_info *)n->link)->visited >= master_cg_visited);
 326 }
 327
 328 static INLINE void
 329 mark_cg_irg_visited(ir_graph *n) {
 330   ((scc_info *)n->link)->visited = master_cg_visited;
 331 }
 332
 333 static INLINE void
 334 set_cg_irg_visited(ir_graph *n, int i) {
 335   ((scc_info *)n->link)->visited = i;
 336 }
 337
 338 static INLINE int
 339 get_cg_irg_visited(ir_graph *n) {
 340   return ((scc_info *)n->link)->visited;
 341 }
 342
 343 static INLINE void
 344 mark_irg_in_stack (ir_graph *n) {
 345   assert(get_irg_link(n));
 346   ((scc_info *)n->link)->in_stack = true;
 347 }
 348
 349 static INLINE void
 350 mark_irg_not_in_stack (ir_graph *n) {
 351   assert(get_irg_link(n));
 352   ((scc_info *)n->link)->in_stack = false;
 353 }
 354
 355 static INLINE bool
 356 irg_is_in_stack (ir_graph *n) {
 357   assert(get_irg_link(n));
 358   return ((scc_info *)n->link)->in_stack;
 359 }
 360
 361 static INLINE void
 362 set_irg_uplink (ir_graph *n, int uplink) {
 363   assert(get_irg_link(n));
 364   ((scc_info *)n->link)->uplink = uplink;
 365 }
 366
 367 static INLINE int
 368 get_irg_uplink (ir_graph *n) {
 369   assert(get_irg_link(n));
 370   return ((scc_info *)n->link)->uplink;
 371 }
 372
 373 static INLINE void
 374 set_irg_dfn (ir_graph *n, int dfn) {
 375   assert(get_irg_link(n));
 376   ((scc_info *)n->link)->dfn = dfn;
 377 }
 378
 379 static INLINE int
 380 get_irg_dfn (ir_graph *n) {
 381   assert(get_irg_link(n));
 382   return ((scc_info *)n->link)->dfn;
 383 }
 384
 385 /**********************************************************************/
 386 /* A stack.                                                          **/
 387 /**********************************************************************/
 388
 389 static ir_graph **stack = NULL;
 390 static int tos = 0;                /* top of stack */
 391
 392 static INLINE void init_stack(void) {
 393   if (stack) {
 394     ARR_RESIZE (ir_graph *, stack, 1000);
 395   } else {
 396     stack = NEW_ARR_F (ir_graph *, 1000);
 397   }
 398   tos = 0;
 399 }
 400
 401
 402 static INLINE void
 403 push (ir_graph *n)
 404 {
 405   if (tos == ARR_LEN (stack)) {
 406     int nlen = ARR_LEN (stack) * 2;
 407     ARR_RESIZE (ir_node *, stack, nlen);
 408   }
 409   stack [tos++] = n;
 410   mark_irg_in_stack(n);
 411 }
 412
 413 static INLINE ir_graph *
 414 pop (void)
 415 {
 416   ir_graph *n = stack[--tos];
 417   mark_irg_not_in_stack(n);
 418   return n;
 419 }
 420
 421 /* The nodes up to n belong to the current loop.
 422    Removes them from the stack and adds them to the current loop. */
 423 static INLINE void
 424 pop_scc_to_loop (ir_graph *n)
 425 {
 426   ir_graph *m;
 427
 428   do {
 429     m = pop();
 430     loop_node_cnt++;
 431     set_irg_dfn(m, loop_node_cnt);
 432     add_loop_node(current_loop, (ir_node *)m);
 433     m->l = current_loop;
 434     //m->callgraph_loop_depth = current_loop->depth;
 435   } while(m != n);
 436 }
 437
 438 /* GL ??? my last son is my grandson???  Removes cfloops with no
 439    ir_nodes in them.  Such loops have only another loop as son. (Why
 440    can't they have two loops as sons? Does it never get that far? ) */
 441 static void close_loop (ir_loop *l)
 442 {
 443   int last = get_loop_n_elements(l) - 1;
 444   loop_element lelement = get_loop_element(l, last);
 445   ir_loop *last_son = lelement.son;
 446
 447   if (get_kind(last_son) == k_ir_loop &&
 448       get_loop_n_elements(last_son) == 1) {
 449     ir_loop *gson;
 450
 451     lelement = get_loop_element(last_son, 0);
 452     gson = lelement.son;
 453     if(get_kind(gson) == k_ir_loop) {
 454       loop_element new_last_son;
 455
 456       gson -> outer_loop = l;
 457       new_last_son.son = gson;
 458       l -> children[last] = new_last_son;
 459     }
 460   }
 461
 462   current_loop = l;
 463 }
 464
 465 /* Removes and unmarks all nodes up to n from the stack.
 466    The nodes must be visited once more to assign them to a scc. */
 467 static INLINE void
 468 pop_scc_unmark_visit (ir_graph *n)
 469 {
 470   ir_graph *m = NULL;
 471
 472   while (m != n) {
 473     m = pop();
 474     set_cg_irg_visited(m, 0);
 475   }
 476 }
 477
 478 /**********************************************************************/
 479 /* The loop datastructure.                                           **/
 480 /**********************************************************************/
 481
 482 /* Allocates a new loop as son of current_loop.  Sets current_loop
 483    to the new loop and returns the father. */
 484 static ir_loop *new_loop (void) {
 485   ir_loop *father, *son;
 486
 487   father = current_loop;
 488
 489   son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
 490   memset (son, 0, sizeof (ir_loop));
 491   son->kind = k_ir_loop;
 492   son->children = NEW_ARR_F (loop_element, 0);
 493   son->n_nodes = 0;
 494   son->n_sons = 0;
 495   if (father) {
 496     son->outer_loop = father;
 497     add_loop_son(father, son);
 498     son->depth = father->depth+1;
 499   } else {  /* The root loop */
 500     son->outer_loop = son;
 501     son->depth = 0;
 502   }
 503
 504 #ifdef DEBUG_libfirm
 505   son->loop_nr = get_irp_new_node_nr();
 506   son->link = NULL;
 507 #endif
 508
 509   current_loop = son;
 510   return father;
 511 }
 512
 513 /**********************************************************************/
 514 /* Constructing and destructing the loop/backedge information.       **/
 515 /**********************************************************************/
 516
 517 /* Initialization steps. **********************************************/
 518
 519 static INLINE void
 520 init_scc (void) {
 521   int i;
 522   current_dfn = 1;
 523   loop_node_cnt = 0;
 524   init_stack();
 525   for (i = 0; i < get_irp_n_irgs(); ++i) {
 526     set_irg_link(get_irp_irg(i), new_scc_info());
 527     get_irp_irg(i)->callgraph_recursion_depth = 0;
 528     get_irp_irg(i)->callgraph_loop_depth = 0;
 529   }
 530 }
 531
 532 /** Returns true if n is a loop header, i.e., it is a Block node
 533  *  and has predecessors within the cfloop and out of the cfloop.
 534  *
 535  *  @param root: only needed for assertion.
 536  */
 537 static bool
 538 is_head (ir_graph *n, ir_graph *root)
 539 {
 540   int i, arity;
 541   int some_outof_loop = 0, some_in_loop = 0;
 542
 543   arity = get_irg_n_callees(n);
 544   for (i = 0; i < arity; i++) {
 545     ir_graph *pred = get_irg_callee(n, i);
 546     if (is_irg_callee_backedge(n, i)) continue;
 547     if (!irg_is_in_stack(pred)) {
 548       some_outof_loop = 1;
 549     } else {
 550       if (get_irg_uplink(pred) < get_irg_uplink(root))  {
 551         DDMG(pred); DDMG(root);
 552         assert(get_irg_uplink(pred) >= get_irg_uplink(root));
 553       }
 554       some_in_loop = 1;
 555     }
 556   }
 557
 558   return some_outof_loop && some_in_loop;
 559 }
 560 /* Returns true if n is possible loop head of an endless loop.
 561    I.e., it is a Block, Phi or Filter node and has only predecessors
 562    within the loop.
 563    @arg root: only needed for assertion. */
 564 static bool
 565 is_endless_head (ir_graph *n, ir_graph *root)
 566 {
 567   int i, arity;
 568   int some_outof_loop = 0, some_in_loop = 0;
 569
 570   arity = get_irg_n_callees(n);
 571   for (i = 0; i < arity; i++) {
 572     ir_graph *pred = get_irg_callee(n, i);
 573     assert(pred);
 574     if (is_irg_callee_backedge(n, i)) { continue; }
 575     if (!irg_is_in_stack(pred)) {
 576         some_outof_loop = 1;
 577     } else {
 578       if(get_irg_uplink(pred) < get_irg_uplink(root)) {
 579         DDMG(pred); DDMG(root);
 580         assert(get_irg_uplink(pred) >= get_irg_uplink(root));
 581       }
 582       some_in_loop = 1;
 583     }
 584   }
 585
 586   return !some_outof_loop && some_in_loop;
 587 }
 588
 589
 590 /* Check whether there is a parallel edge in the ip control flow.
 591    Only */
 592 static bool
 593 is_ip_head (ir_graph *n, ir_graph *pred)
 594 {
 595   int iv_rem = get_interprocedural_view();
 596   set_interprocedural_view(true);
 597   ir_node *sblock = get_irg_start_block(n);
 598   int i, arity = get_Block_n_cfgpreds(sblock);
 599   int is_be = 0;
 600
 601   //printf(" edge from "); DDMG(n);
 602   //printf(" to pred   "); DDMG(pred);
 603   //printf(" sblock    "); DDMN(sblock);
 604
 605   for (i = 0; i < arity; i++) {
 606     ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
 607     //printf("  "); DDMN(pred_cfop);
 608     if (get_irn_op(pred_cfop) == op_CallBegin) {  /* could be Unknown */
 609       ir_graph *ip_pred = get_irn_irg(pred_cfop);
 610       //printf("   "); DDMG(ip_pred);
 611       if ((ip_pred == pred) && is_backedge(sblock, i)) {
 612         //printf("   found\n");
 613         is_be = 1;
 614       }
 615     }
 616   }
 617
 618   set_interprocedural_view(iv_rem);
 619   return is_be;
 620 }
 621
 622 /* Returns index of the predecessor with the smallest dfn number
 623    greater-equal than limit. */
 624 static int
 625 smallest_dfn_pred (ir_graph *n, int limit)
 626 {
 627   int i, index = -2, min = -1;
 628
 629   int arity = get_irg_n_callees(n);
 630   for (i = 0; i < arity; i++) {
 631     ir_graph *pred = get_irg_callee(n, i);
 632     if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue;
 633     if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
 634       index = i;
 635       min = get_irg_dfn(pred);
 636     }
 637   }
 638
 639   return index;
 640 }
 641
 642 /* Returns index of the predecessor with the largest dfn number. */
 643 static int
 644 largest_dfn_pred (ir_graph *n)
 645 {
 646   int i, index = -2, max = -1;
 647
 648   int arity = get_irg_n_callees(n);
 649   for (i = 0; i < arity; i++) {
 650     ir_graph *pred = get_irg_callee(n, i);
 651     if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
 652     if (get_irg_dfn(pred) > max) {
 653       index = i;
 654       max = get_irg_dfn(pred);
 655     }
 656   }
 657
 658   return index;
 659 }
 660
 661 #if 0
 662 static ir_graph *
 663 find_tail (ir_graph *n) {
 664   ir_graph *m;
 665   int i, res_index = -2;
 666
 667   /*
 668     if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
 669   */
 670   m = stack[tos-1];  /* tos = top of stack */
 671   if (is_head (m, n)) {
 672     res_index = smallest_dfn_pred(m, 0);
 673     if ((res_index == -2) &&  /* no smallest dfn pred found. */
 674     (n == m))
 675       return NULL;
 676   } else {
 677     if (m == n) return NULL;    // Is this to catch Phi - self loops?
 678     for (i = tos-2; i >= 0; --i) {
 679       m = stack[i];
 680
 681       if (is_head (m, n)) {
 682         res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
 683         if (res_index == -2)  /* no smallest dfn pred found. */
 684           res_index = largest_dfn_pred (m);
 685
 686         if ((m == n) && (res_index == -2)) {
 687           i = -1;
 688         }
 689         break;
 690       }
 691
 692       /* We should not walk past our selves on the stack:  The upcoming nodes
 693          are not in this loop. We assume a loop not reachable from Start. */
 694       if (m == n) {
 695         i = -1;
 696         break;
 697       }
 698
 699     }
 700
 701     if (i < 0) {
 702       /* A dead loop not reachable from Start. */
 703       for (i = tos-2; i >= 0; --i) {
 704         m = stack[i];
 705         if (is_endless_head (m, n)) {
 706           res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
 707           if (res_index == -2)  /* no smallest dfn pred found. */
 708             res_index = largest_dfn_pred (m);
 709           break;
 710         }
 711         if (m == n) { break; }  /* It's not an unreachable loop, either. */
 712       }
 713       //assert(0 && "no head found on stack");
 714     }
 715
 716   }
 717   assert (res_index > -2);
 718
 719   set_irg_callee_backedge (m, res_index);
 720   return get_irg_callee(m, res_index);
 721 }
 722 #else
 723 static ir_graph *
 724 find_tail (ir_graph *n) {
 725   ir_graph *m;
 726   int i, res_index = -2;
 727
 728   ir_graph *in_and_out    = NULL;
 729   ir_graph *only_in       = NULL;
 730   ir_graph *ip_in_and_out = NULL;
 731   ir_graph *ip_only_in    = NULL;
 732
 733   //printf("find tail for "); DDMG(n);
 734
 735   for (i = tos-1; i >= 0; --i) {
 736     ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
 737     m = stack[i];
 738
 739     if (is_head (m, n)) {
 740       //printf(" found 1a! "); DDM;
 741       in_and_out = m;
 742       if (is_ip_head(pred, m)) {
 743         //printf(" found 1b! "); DDM;
 744         ip_in_and_out = m;
 745       }
 746     } else if (!ip_only_in && is_endless_head(m, n)) {
 747       only_in = m;
 748       //printf(" found 2a! "); DDM;
 749       if (is_ip_head(pred, m)) {
 750         //printf(" found 2b! "); DDM;
 751         ip_only_in = m;
 752       }
 753     } else if (is_ip_head(pred, m)) {
 754       //printf(" found 3! "); DDM;   This happens for self recursions in the second
 755       //assert(0);                   scc iteration (the one to flip the loop.)
 756     }
 757
 758     if (ip_in_and_out) break;    /* That's what we really want. */
 759
 760     if (m == n) break;   /* Don't walk past n on the stack! */
 761   }
 762
 763
 764   if (!in_and_out && !only_in)
 765     /* There is no loop */
 766     return NULL;
 767
 768
 769   /* Is there a head in the callgraph without a head in the
 770      ip cf graph? */
 771   assert(in_and_out || only_in);
 772
 773   m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
 774
 775   if (!m)
 776     m = (in_and_out) ? in_and_out : only_in;
 777
 778   //printf("*** head is "); DDMG(m);
 779
 780   res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
 781   if (res_index == -2)  /* no smallest dfn pred found. */
 782     res_index = largest_dfn_pred (m);
 783
 784   set_irg_callee_backedge (m, res_index);
 785   ir_graph *res = get_irg_callee(m, res_index);
 786   //printf("*** tail is "); DDMG(res);
 787   return res;
 788 }
 789 #endif
 790
 791
 792 /*-----------------------------------------------------------*
 793  *                   The core algorithm.                     *
 794  *-----------------------------------------------------------*/
 795
 796
 797 static void cgscc (ir_graph *n) {
 798   int i;
 799
 800   if (cg_irg_visited(n)) return;
 801   mark_cg_irg_visited(n);
 802
 803   /* Initialize the node */
 804   set_irg_dfn(n, current_dfn);      /* Depth first number for this node */
 805   set_irg_uplink(n, current_dfn);   /* ... is default uplink. */
 806   current_dfn ++;
 807   push(n);
 808
 809   int arity = get_irg_n_callees(n);
 810
 811   for (i = 0; i < arity; i++) {
 812     ir_graph *m;
 813     if (is_irg_callee_backedge(n, i)) continue;
 814     m = get_irg_callee(n, i);
 815
 816     /** This marks the backedge, but does it guarantee a correct loop tree? */
 817     //if (m == n) { set_irg_callee_backedge(n, i); continue; }
 818
 819     cgscc (m);
 820     if (irg_is_in_stack(m)) {
 821       /* Uplink of m is smaller if n->m is a backedge.
 822          Propagate the uplink to mark the cfloop. */
 823       if (get_irg_uplink(m) < get_irg_uplink(n))
 824         set_irg_uplink(n, get_irg_uplink(m));
 825     }
 826   }
 827
 828   if (get_irg_dfn(n) == get_irg_uplink(n)) {
 829     /* This condition holds for
 830        1) the node with the incoming backedge.
 831        That is: We found a cfloop!
 832        2) Straight line code, because no uplink has been propagated, so the
 833        uplink still is the same as the dfn.
 834
 835        But n might not be a proper cfloop head for the analysis. Proper cfloop
 836        heads are Block and Phi nodes. find_tail searches the stack for
 837        Block's and Phi's and takes those nodes as cfloop heads for the current
 838        cfloop instead and marks the incoming edge as backedge. */
 839
 840     ir_graph *tail = find_tail(n);
 841     if (tail) {
 842       /* We have a cfloop, that is no straight line code,
 843          because we found a cfloop head!
 844          Next actions: Open a new cfloop on the cfloop tree and
 845          try to find inner cfloops */
 846
 847
 848       ir_loop *l = new_loop();
 849
 850       /* Remove the cfloop from the stack ... */
 851       pop_scc_unmark_visit (n);
 852
 853       /* The current backedge has been marked, that is temporarily eliminated,
 854          by find tail. Start the scc algorithm
 855          anew on the subgraph thats left (the current cfloop without the backedge)
 856          in order to find more inner cfloops. */
 857
 858       cgscc (tail);
 859
 860       assert (cg_irg_visited(n));
 861       close_loop(l);
 862     } else {
 863       pop_scc_to_loop(n);
 864     }
 865   }
 866 }
 867
 868
 869
 870 static void reset_isbe(void) {
 871   int i, n_irgs = get_irp_n_irgs();
 872
 873   for (i = 0; i < n_irgs; ++i) {
 874     int j, n_cs;
 875     ir_graph *irg = get_irp_irg(i);
 876
 877     n_cs = get_irg_n_callers(irg);
 878     for (j = 0; j < n_cs; ++j) {
 879       irg->caller_isbe[j] = 0;
 880     }
 881     n_cs = get_irg_n_callees(irg);
 882     for (j = 0; j < n_cs; ++j) {
 883       irg->callee_isbe[j] = 0;
 884     }
 885   }
 886 }
 887
 888
 889
 890
 891 /* ----------------------------------------------------------------------------------- */
 892 /* Another algorithm to compute recursion nesting depth                                */
 893 /* Walk the callgraph.  For each crossed edge increase the loop depth by the edge      */
 894 /* weight. Assign graphs the maximal depth.                                            */
 895 /* ----------------------------------------------------------------------------------- */
 896
 897 void compute_loop_depth (ir_graph *irg, void *env) {
 898   int current_nesting = *(int *) env;
 899   int old_nesting = irg->callgraph_loop_depth;
 900   int old_visited = get_cg_irg_visited(irg);
 901   int i, n_callees;
 902
 903   //return ;
 904
 905   if (cg_irg_visited(irg)) return;
 906
 907   mark_cg_irg_visited(irg);
 908
 909   //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
 910
 911
 912   if (old_nesting < current_nesting)
 913     irg->callgraph_loop_depth = current_nesting;
 914
 915   if (current_nesting > irp->max_callgraph_loop_depth)
 916     irp->max_callgraph_loop_depth = current_nesting;
 917
 918   if ((old_visited +1 < get_cg_irg_visited(irg)) ||   /* not yet visited */
 919       (old_nesting < current_nesting)) {        /* propagate larger nesting */
 920     /* Don't walk the graph, but a tree that is an unfolded graph. */
 921     n_callees = get_irg_n_callees(irg);
 922     for (i = 0; i < n_callees; i++) {
 923       ir_graph *m = get_irg_callee(irg, i);
 924       *(int *)env += get_irg_callee_loop_depth(irg, i);
 925       compute_loop_depth(m, env);
 926       *(int *)env -= get_irg_callee_loop_depth(irg, i);
 927     }
 928   }
 929
 930   set_cg_irg_visited(irg, master_cg_visited-1);
 931 }
 932
 933
 934 /* ----------------------------------------------------------------------------------- */
 935 /* Another algorithm to compute recursion nesting depth                                */
 936 /* Walk the callgraph.  For each crossed loop increase the nesting depth by one.       */
 937 /* Assign graphs the maximal nesting depth.   Don't increas if passing loops more than */
 938 /* once.                                                                               */
 939 /* ----------------------------------------------------------------------------------- */
 940
 941
 942 /* For callees, we want to remember the Call nodes, too. */
 943 struct ana_entry2 {
 944   ir_loop **loop_stack;
 945   int tos;
 946   int recursion_nesting;
 947 };
 948
 949 typedef struct ana_entry2 ana_entry2;
 950
 951 static void push2(ana_entry2 *e, ir_loop *g) {
 952   if (ARR_LEN(e->loop_stack) == e->tos) {
 953     ARR_APP1(ir_loop *, e->loop_stack, g);
 954   } else {
 955     e->loop_stack[e->tos] = g;
 956   }
 957   e->tos ++;
 958 }
 959
 960 static ir_loop *pop2(ana_entry2 *e) {
 961   e->tos --;
 962   return e->loop_stack[e->tos+1];
 963 }
 964
 965 static int in_stack(ana_entry2 *e, ir_loop *g) {
 966   int i;
 967   for (i = e->tos-1; i >= 0; --i) {
 968     if (e->loop_stack[i] == g) return 1;
 969   }
 970   return 0;
 971 }
 972
 973 void compute_rec_depth (ir_graph *irg, void *env) {
 974   ana_entry2 *e = (ana_entry2 *)env;
 975   ir_loop *l = irg->l;
 976   int depth, old_depth = irg->callgraph_recursion_depth;
 977   int i, n_callees;
 978   int pushed = 0;
 979
 980   if (cg_irg_visited(irg)) return;
 981   mark_cg_irg_visited(irg);
 982
 983   /* -- compute and set the new nesting value -- */
 984   if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
 985     push2(e, l);
 986     e->recursion_nesting++;
 987     pushed = 1;
 988   }
 989   depth = e->recursion_nesting;
 990
 991   if (old_depth < depth)
 992     irg->callgraph_recursion_depth = depth;
 993
 994   if (depth > irp->max_callgraph_recursion_depth)
 995     irp->max_callgraph_recursion_depth = depth;
 996
 997   /* -- spread the nesting value -- */
 998   if (depth == 0 || old_depth < depth) {
 999     /* Don't walk the graph, but a tree that is an unfolded graph. */
1000     n_callees = get_irg_n_callees(irg);
1001     for (i = 0; i < n_callees; i++) {
1002       ir_graph *m = get_irg_callee(irg, i);
1003       compute_rec_depth(m, env);
1004     }
1005   }
1006
1007   /* -- clean up -- */
1008   if (pushed) {
1009     pop2(e);
1010     e->recursion_nesting--;
1011   }
1012   set_cg_irg_visited(irg, master_cg_visited-1);
1013 }
1014
1015
1016 /* Compute the backedges that represent recursions. */
1017 void find_callgraph_recursions(void) {
1018   int i, n_irgs = get_irp_n_irgs();
1019
1020   reset_isbe();
1021
1022   /* -- Compute the looptree -- */
1023
1024   /* The outermost graph.  We start here.  Then we start at all
1025      functions in irg list that are never called, then at the remaining
1026      unvisited ones. */
1027   assert(get_irp_main_irg());
1028   outermost_ir_graph = get_irp_main_irg();
1029   init_scc();
1030
1031   current_loop = NULL;
1032   new_loop();  /* sets current_loop */
1033
1034   master_cg_visited++;
1035   cgscc(outermost_ir_graph);
1036   for (i = 0; i < n_irgs; i++) {
1037     ir_graph *irg = get_irp_irg(i);
1038     if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1039       cgscc(irg);
1040   }
1041   for (i = 0; i < n_irgs; i++) {
1042     ir_graph *irg = get_irp_irg(i);
1043     if (!cg_irg_visited(irg))
1044       cgscc(irg);
1045   }
1046   irp->outermost_cg_loop = current_loop;
1047
1048   /* -- Reverse the backedge information. -- */
1049   for (i = 0; i < n_irgs; i++) {
1050     ir_graph *irg = get_irp_irg(i);
1051     int j, n_callees = get_irg_n_callees(irg);
1052     for (j = 0; j < n_callees; ++j) {
1053       if (is_irg_callee_backedge(irg, j))
1054         set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1055     }
1056   }
1057
1058   /* -- compute the loop depth  -- */
1059   int current_nesting = 0;
1060   irp->max_callgraph_loop_depth = 0;
1061   master_cg_visited += 2;
1062   //printf (" ** starting at      "); DDMG(get_irp_main_irg());
1063   compute_loop_depth(get_irp_main_irg(), &current_nesting);
1064   for (i = 0; i < n_irgs; i++) {
1065     ir_graph *irg = get_irp_irg(i);
1066     if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1067         get_irg_n_callers(irg) == 0) {
1068       compute_loop_depth(irg, &current_nesting);
1069       //printf (" ** starting at      "); DDMG(irg);
1070     }
1071   }
1072   for (i = 0; i < n_irgs; i++) {
1073     ir_graph *irg = get_irp_irg(i);
1074     if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1075       compute_loop_depth(irg, &current_nesting);
1076       //printf (" ** starting at      "); DDMG(irg);
1077     }
1078   }
1079
1080   /* -- compute the recursion depth -- */
1081   ana_entry2 e;
1082   e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1083   e.tos = 0;
1084   e.recursion_nesting = 0;
1085   irp->max_callgraph_recursion_depth = 0;
1086
1087   master_cg_visited += 2;
1088   compute_rec_depth(get_irp_main_irg(), &e);
1089   //printf (" ++ starting at "); DDMG(get_irp_main_irg());
1090   for (i = 0; i < n_irgs; i++) {
1091     ir_graph *irg = get_irp_irg(i);
1092     if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1093         get_irg_n_callers(irg) == 0) {
1094       compute_rec_depth(irg, &e);
1095       //printf (" ++ starting at "); DDMG(irg);
1096     }
1097   }
1098   for (i = 0; i < n_irgs; i++) {
1099     ir_graph *irg = get_irp_irg(i);
1100     if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1101       compute_rec_depth(irg, &e);
1102       //printf (" ++ starting at "); DDMG(irg);
1103     }
1104   }
1105
1106   DEL_ARR_F(e.loop_stack);
1107
1108   //dump_callgraph("-with_nesting");
1109
1110   //dump_callgraph_loop_tree(current_loop, "-after_cons");
1111   irp->callgraph_state =  irp_callgraph_and_calltree_consistent;
1112 }
1113
1114 /* Maximal loop depth of all paths from an external visible method to
1115     this irg. */
1116 int       get_irg_loop_depth(ir_graph *irg) {
1117   assert(irp->callgraph_state == irp_callgraph_consistent ||
1118          irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1119   return  irg->callgraph_loop_depth;
1120 }
1121
1122 /* Maximal recursion depth of all paths from an external visible method to
1123    this irg. */
1124 int       get_irg_recursion_depth(ir_graph *irg) {
1125   assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1126   return irg->callgraph_recursion_depth;
1127 }
1128
1129 void analyse_loop_nesting_depth(void) {
1130   entity **free_methods = NULL;
1131   int arr_len;
1132
1133   /* establish preconditions. */
1134   if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1135     cgana(&arr_len, &free_methods);
1136   }
1137
1138   if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1139     compute_callgraph();
1140   }
1141
1142   find_callgraph_recursions();
1143 }