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