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

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