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