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