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