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