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

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