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 unsigned long 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, unsigned long 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(ir_entity **roots, unsigned n_roots,
 390                 callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
 391         //int i, n_irgs = get_irp_n_irgs();
 392         unsigned r;
 393         ++master_cg_visited;
 394
 395         for (r = 0; r < n_roots; ++r) {
 396                 ir_graph *irg = get_entity_irg(roots[r]);
 397                 if (irg == NULL)
 398                         continue;
 399
 400                 do_walk(irg, pre, post, env);
 401         }
 402
 403 #if 0
 404         for (i = 0; i < n_irgs; i++) {
 405                 ir_graph *irg = get_irp_irg(i);
 406                 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
 407                         do_walk(irg, pre, post, env);
 408         }
 409         for (i = 0; i < n_irgs; i++) {
 410                 ir_graph *irg = get_irp_irg(i);
 411                 if (!cg_irg_visited(irg))
 412                         do_walk(irg, pre, post, env);
 413         }
 414 #endif
 415 }
 416
 417 /* ----------------------------------------------------------------------------------- */
 418 /* loop construction algorithm                                                         */
 419 /* ----------------------------------------------------------------------------------- */
 420
 421 static ir_graph *outermost_ir_graph;   /**< The outermost graph the scc is computed
 422                                             for */
 423 static ir_loop *current_loop;      /**< Current cfloop construction is working
 424                                         on. */
 425 static int loop_node_cnt = 0;      /**< Counts the number of allocated cfloop nodes.
 426                                         Each cfloop node gets a unique number.
 427                                         What for? ev. remove. @@@ */
 428 static int current_dfn = 1;        /**< Counter to generate depth first numbering
 429                                         of visited nodes.  */
 430
 431 /*-----------------*/
 432 /* Node attributes */
 433 /*-----------------*/
 434
 435 typedef struct scc_info {
 436         int in_stack;          /**< Marks whether node is on the stack. */
 437         int dfn;               /**< Depth first search number. */
 438         int uplink;            /**< dfn number of ancestor. */
 439         int visited;
 440 } scc_info;
 441
 442 /**
 443  * allocates a new scc_info on the obstack
 444  */
 445 static INLINE scc_info *new_scc_info(struct obstack *obst) {
 446         scc_info *info = obstack_alloc(obst, sizeof(*info));
 447         memset(info, 0, sizeof(*info));
 448         return info;
 449 }
 450
 451 /**
 452  * Returns non-zero if a graph was already visited.
 453  */
 454 static INLINE int cg_irg_visited(ir_graph *irg) {
 455         return irg->self_visited >= master_cg_visited;
 456 }
 457
 458 /**
 459  * Marks a graph as visited.
 460  */
 461 static INLINE void mark_cg_irg_visited(ir_graph *irg) {
 462         irg->self_visited = master_cg_visited;
 463 }
 464
 465 /**
 466  * Set a graphs visited flag to i.
 467  */
 468 static INLINE void set_cg_irg_visited(ir_graph *irg, unsigned long i) {
 469         irg->self_visited = i;
 470 }
 471
 472 /**
 473  * Returns the visited flag of a graph.
 474  */
 475 static INLINE unsigned long get_cg_irg_visited(ir_graph *irg) {
 476         return irg->self_visited;
 477 }
 478
 479 static INLINE void mark_irg_in_stack(ir_graph *irg) {
 480         scc_info *info = get_irg_link(irg);
 481         assert(info && "missing call to init_scc()");
 482         info->in_stack = 1;
 483 }
 484
 485 static INLINE void mark_irg_not_in_stack(ir_graph *irg) {
 486         scc_info *info = get_irg_link(irg);
 487         assert(info && "missing call to init_scc()");
 488         info->in_stack = 0;
 489 }
 490
 491 static INLINE int irg_is_in_stack(ir_graph *irg) {
 492         scc_info *info = get_irg_link(irg);
 493         assert(info && "missing call to init_scc()");
 494         return info->in_stack;
 495 }
 496
 497 static INLINE void set_irg_uplink(ir_graph *irg, int uplink) {
 498         scc_info *info = get_irg_link(irg);
 499         assert(info && "missing call to init_scc()");
 500         info->uplink = uplink;
 501 }
 502
 503 static INLINE int get_irg_uplink(ir_graph *irg) {
 504         scc_info *info = get_irg_link(irg);
 505         assert(info && "missing call to init_scc()");
 506         return info->uplink;
 507 }
 508
 509 static INLINE void set_irg_dfn(ir_graph *irg, int dfn) {
 510         scc_info *info = get_irg_link(irg);
 511         assert(info && "missing call to init_scc()");
 512         info->dfn = dfn;
 513 }
 514
 515 static INLINE int get_irg_dfn(ir_graph *irg) {
 516         scc_info *info = get_irg_link(irg);
 517         assert(info && "missing call to init_scc()");
 518         return info->dfn;
 519 }
 520
 521 /**********************************************************************/
 522 /* A stack.                                                          **/
 523 /**********************************************************************/
 524
 525 static ir_graph **stack = NULL;
 526 static int tos = 0;                /**< top of stack */
 527
 528 /**
 529  * Initialize the irg stack.
 530  */
 531 static INLINE void init_stack(void) {
 532         if (stack) {
 533                 ARR_RESIZE(ir_graph *, stack, 1000);
 534         } else {
 535                 stack = NEW_ARR_F(ir_graph *, 1000);
 536         }
 537         tos = 0;
 538 }
 539
 540 /**
 541  * push a graph on the irg stack
 542  * @param n the graph to be pushed
 543  */
 544 static INLINE void push(ir_graph *irg) {
 545         if (tos == ARR_LEN(stack)) {
 546                 int nlen = ARR_LEN(stack) * 2;
 547                 ARR_RESIZE(ir_node *, stack, nlen);
 548         }
 549         stack [tos++] = irg;
 550         mark_irg_in_stack(irg);
 551 }
 552
 553 /**
 554  * return the topmost graph on the stack and pop it
 555  */
 556 static INLINE ir_graph *pop(void) {
 557         ir_graph *irg = stack[--tos];
 558         mark_irg_not_in_stack(irg);
 559         return irg;
 560 }
 561
 562 /**
 563  * The nodes up to irg belong to the current loop.
 564  * Removes them from the stack and adds them to the current loop.
 565  */
 566 static INLINE void pop_scc_to_loop(ir_graph *irg) {
 567         ir_graph *m;
 568
 569         do {
 570                 m = pop();
 571                 loop_node_cnt++;
 572                 set_irg_dfn(m, loop_node_cnt);
 573                 add_loop_irg(current_loop, m);
 574                 m->l = current_loop;
 575                 //m->callgraph_loop_depth = current_loop->depth;
 576         } while(m != irg);
 577 }
 578
 579 /* GL ??? my last son is my grandson???  Removes cfloops with no
 580    ir_nodes in them.  Such loops have only another loop as son. (Why
 581    can't they have two loops as sons? Does it never get that far? ) */
 582 static void close_loop(ir_loop *l) {
 583         int last = get_loop_n_elements(l) - 1;
 584         loop_element lelement = get_loop_element(l, last);
 585         ir_loop *last_son = lelement.son;
 586
 587         if (get_kind(last_son) == k_ir_loop &&
 588             get_loop_n_elements(last_son) == 1) {
 589                 ir_loop *gson;
 590
 591                 lelement = get_loop_element(last_son, 0);
 592                 gson = lelement.son;
 593                 if (get_kind(gson) == k_ir_loop) {
 594                         loop_element new_last_son;
 595
 596                         gson->outer_loop = l;
 597                         new_last_son.son = gson;
 598                         l->children[last] = new_last_son;
 599                 }
 600         }
 601         current_loop = l;
 602 }
 603
 604 /**
 605  * Removes and unmarks all nodes up to n from the stack.
 606  * The nodes must be visited once more to assign them to a scc.
 607  */
 608 static INLINE void pop_scc_unmark_visit(ir_graph *n) {
 609         ir_graph *m = NULL;
 610
 611         while (m != n) {
 612                 m = pop();
 613                 set_cg_irg_visited(m, 0);
 614         }
 615 }
 616
 617 /**********************************************************************/
 618 /* The loop data structure.                                          **/
 619 /**********************************************************************/
 620
 621 /**
 622  * Allocates a new loop as son of current_loop.  Sets current_loop
 623  * to the new loop and returns the father.
 624  */
 625 static ir_loop *new_loop(void) {
 626         ir_loop *father = current_loop;
 627         ir_loop *son    = alloc_loop(father, outermost_ir_graph->obst);
 628
 629         current_loop = son;
 630         return father;
 631 }
 632
 633
 634 /**********************************************************************/
 635 /* Constructing and destructing the loop/backedge information.       **/
 636 /**********************************************************************/
 637
 638 /* Initialization steps. **********************************************/
 639
 640 static void init_scc(struct obstack *obst) {
 641         int i;
 642         int n_irgs;
 643
 644         current_dfn   = 1;
 645         loop_node_cnt = 0;
 646         init_stack();
 647
 648         n_irgs = get_irp_n_irgs();
 649         for (i = 0; i < n_irgs; ++i) {
 650                 ir_graph *irg = get_irp_irg(i);
 651                 set_irg_link(irg, new_scc_info(obst));
 652                 irg->callgraph_recursion_depth = 0;
 653                 irg->callgraph_loop_depth      = 0;
 654         }
 655 }
 656
 657 /** Returns non-zero if n is a loop header, i.e., it is a Block node
 658  *  and has predecessors within the cfloop and out of the cfloop.
 659  *
 660  *  @param root: only needed for assertion.
 661  */
 662 static int is_head(ir_graph *n, ir_graph *root) {
 663         int i, arity;
 664         int some_outof_loop = 0, some_in_loop = 0;
 665
 666         arity = get_irg_n_callees(n);
 667         for (i = 0; i < arity; i++) {
 668                 ir_graph *pred = get_irg_callee(n, i);
 669                 if (is_irg_callee_backedge(n, i)) continue;
 670                 if (!irg_is_in_stack(pred)) {
 671                         some_outof_loop = 1;
 672                 } else {
 673                         if (get_irg_uplink(pred) < get_irg_uplink(root))  {
 674                                 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
 675                         }
 676                         some_in_loop = 1;
 677                 }
 678         }
 679
 680         return some_outof_loop & some_in_loop;
 681 }
 682
 683 /**
 684  * Returns non-zero if n is possible loop head of an endless loop.
 685  * I.e., it is a Block, Phi or Filter node and has only predecessors
 686  * within the loop.
 687  * @arg root: only needed for assertion.
 688  */
 689 static int is_endless_head(ir_graph *n, ir_graph *root)
 690 {
 691         int i, arity;
 692         int some_outof_loop = 0, some_in_loop = 0;
 693
 694         arity = get_irg_n_callees(n);
 695         for (i = 0; i < arity; i++) {
 696                 ir_graph *pred = get_irg_callee(n, i);
 697                 assert(pred);
 698                 if (is_irg_callee_backedge(n, i))
 699                         continue;
 700                 if (!irg_is_in_stack(pred)) {
 701                         some_outof_loop = 1;
 702                 } else {
 703                         if (get_irg_uplink(pred) < get_irg_uplink(root)) {
 704                                 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
 705                         }
 706                         some_in_loop = 1;
 707                 }
 708         }
 709         return !some_outof_loop & some_in_loop;
 710 }
 711
 712 #ifdef INTERPROCEDURAL_VIEW
 713 /**
 714  * Check whether there is a parallel edge in the ip control flow.
 715  * Only
 716  */
 717 static int is_ip_head(ir_graph *n, ir_graph *pred)
 718 {
 719         int is_be = 0;
 720
 721         int iv_rem = get_interprocedural_view();
 722         set_interprocedural_view(1);
 723         {
 724                 ir_node *sblock = get_irg_start_block(n);
 725                 int i, arity = get_Block_n_cfgpreds(sblock);
 726
 727                 //printf(" edge from "); DDMG(n);
 728                 //printf(" to pred   "); DDMG(pred);
 729                 //printf(" sblock    "); DDMN(sblock);
 730
 731                 for (i = 0; i < arity; i++) {
 732                         ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
 733                         //printf("  "); DDMN(pred_cfop);
 734                         if (is_CallBegin(pred_cfop)) { /* could be Unknown */
 735                                 ir_graph *ip_pred = get_irn_irg(pred_cfop);
 736                                 //printf("   "); DDMG(ip_pred);
 737                                 if ((ip_pred == pred) && is_backedge(sblock, i)) {
 738                                         //printf("   found\n");
 739                                         is_be = 1;
 740                                 }
 741                         }
 742                 }
 743         }
 744         set_interprocedural_view(iv_rem);
 745         return is_be;
 746 }
 747 #endif /* INTERPROCEDURAL_VIEW */
 748
 749 /**
 750  * Returns index of the predecessor with the smallest dfn number
 751  * greater-equal than limit.
 752  */
 753 static int smallest_dfn_pred(ir_graph *n, int limit)
 754 {
 755         int i, index = -2, min = -1;
 756
 757         int arity = get_irg_n_callees(n);
 758         for (i = 0; i < arity; i++) {
 759                 ir_graph *pred = get_irg_callee(n, i);
 760                 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred))
 761                         continue;
 762                 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
 763                         index = i;
 764                         min = get_irg_dfn(pred);
 765                 }
 766         }
 767
 768         return index;
 769 }
 770
 771 /** Returns index of the predecessor with the largest dfn number. */
 772 static int largest_dfn_pred(ir_graph *n) {
 773         int i, index = -2, max = -1;
 774
 775         int arity = get_irg_n_callees(n);
 776         for (i = 0; i < arity; ++i) {
 777                 ir_graph *pred = get_irg_callee(n, i);
 778                 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
 779                 if (get_irg_dfn(pred) > max) {
 780                         index = i;
 781                         max = get_irg_dfn(pred);
 782                 }
 783         }
 784
 785         return index;
 786 }
 787
 788 #ifndef INTERPROCEDURAL_VIEW
 789 static ir_graph *find_tail(ir_graph *n) {
 790         ir_graph *m;
 791         int i, res_index = -2;
 792
 793         /*
 794         if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
 795         */
 796         m = stack[tos-1];  /* tos = top of stack */
 797         if (is_head (m, n)) {
 798                 res_index = smallest_dfn_pred(m, 0);
 799                 if ((res_index == -2) &&  /* no smallest dfn pred found. */
 800                         (n == m))
 801                         return NULL;
 802         } else {
 803                 if (m == n) return NULL;    // Is this to catch Phi - self loops?
 804                 for (i = tos-2; i >= 0; --i) {
 805                         m = stack[i];
 806
 807                         if (is_head(m, n)) {
 808                                 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
 809                                 if (res_index == -2)  /* no smallest dfn pred found. */
 810                                         res_index = largest_dfn_pred(m);
 811
 812                                 if ((m == n) && (res_index == -2)) {
 813                                         i = -1;
 814                                 }
 815                                 break;
 816                         }
 817
 818                         /* We should not walk past our selves on the stack:  The upcoming nodes
 819                            are not in this loop. We assume a loop not reachable from Start. */
 820                         if (m == n) {
 821                                 i = -1;
 822                                 break;
 823                         }
 824
 825                 }
 826
 827                 if (i < 0) {
 828                         /* A dead loop not reachable from Start. */
 829                         for (i = tos-2; i >= 0; --i) {
 830                                 m = stack[i];
 831                                 if (is_endless_head(m, n)) {
 832                                         res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
 833                                         if (res_index == -2)  /* no smallest dfn pred found. */
 834                                                 res_index = largest_dfn_pred(m);
 835                                         break;
 836                                 }
 837                                 if (m == n) { break; }  /* It's not an unreachable loop, either. */
 838                         }
 839                         //assert(0 && "no head found on stack");
 840                 }
 841
 842         }
 843         assert (res_index > -2);
 844
 845         set_irg_callee_backedge(m, res_index);
 846         return get_irg_callee(m, res_index);
 847 }
 848 #else
 849 static ir_graph *find_tail(ir_graph *n) {
 850         ir_graph *m;
 851         int i, res_index = -2;
 852
 853         ir_graph *res;
 854         ir_graph *in_and_out    = NULL;
 855         ir_graph *only_in       = NULL;
 856         ir_graph *ip_in_and_out = NULL;
 857         ir_graph *ip_only_in    = NULL;
 858
 859         //printf("find tail for "); DDMG(n);
 860
 861         for (i = tos-1; i >= 0; --i) {
 862                 ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
 863                 m = stack[i];
 864
 865                 if (is_head(m, n)) {
 866                         //printf(" found 1a! "); DDM;
 867                         in_and_out = m;
 868                         if (is_ip_head(pred, m)) {
 869                                 //printf(" found 1b! "); DDM;
 870                                 ip_in_and_out = m;
 871                         }
 872                 } else if (!ip_only_in && is_endless_head(m, n)) {
 873                         only_in = m;
 874                         //printf(" found 2a! "); DDM;
 875                         if (is_ip_head(pred, m)) {
 876                                 //printf(" found 2b! "); DDM;
 877                                 ip_only_in = m;
 878                         }
 879                 } else if (is_ip_head(pred, m)) {
 880                         //printf(" found 3! "); DDM;   This happens for self recursions in the second
 881                         //assert(0);                   scc iteration (the one to flip the loop.)
 882                 }
 883
 884                 if (ip_in_and_out) break;    /* That's what we really want. */
 885
 886                 if (m == n) break;   /* Don't walk past n on the stack! */
 887         }
 888
 889
 890         if (!in_and_out && !only_in)
 891                 /* There is no loop */
 892                 return NULL;
 893
 894
 895         /* Is there a head in the callgraph without a head in the
 896            ip cf graph? */
 897         assert(in_and_out || only_in);
 898
 899         m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
 900
 901         if (!m)
 902                 m = (in_and_out) ? in_and_out : only_in;
 903
 904         //printf("*** head is "); DDMG(m);
 905
 906         res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
 907         if (res_index == -2)  /* no smallest dfn pred found. */
 908                 res_index = largest_dfn_pred(m);
 909
 910         set_irg_callee_backedge(m, res_index);
 911         res = get_irg_callee(m, res_index);
 912         //printf("*** tail is "); DDMG(res);
 913         return res;
 914 }
 915 #endif /* INTERPROCEDURAL_VIEW */
 916
 917 /*-----------------------------------------------------------*
 918  *                   The core algorithm.                     *
 919  *-----------------------------------------------------------*/
 920
 921
 922 static void cgscc(ir_graph *n) {
 923         int i, arity;
 924
 925         if (cg_irg_visited(n)) return;
 926         mark_cg_irg_visited(n);
 927
 928         /* Initialize the node */
 929         set_irg_dfn(n, current_dfn);      /* Depth first number for this node */
 930         set_irg_uplink(n, current_dfn);   /* ... is default uplink. */
 931         current_dfn ++;
 932         push(n);
 933
 934         arity = get_irg_n_callees(n);
 935         for (i = 0; i < arity; i++) {
 936                 ir_graph *m;
 937                 if (is_irg_callee_backedge(n, i)) continue;
 938                 m = get_irg_callee(n, i);
 939
 940                 /** This marks the backedge, but does it guarantee a correct loop tree? */
 941                 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
 942
 943                 cgscc (m);
 944                 if (irg_is_in_stack(m)) {
 945                         /* Uplink of m is smaller if n->m is a backedge.
 946                            Propagate the uplink to mark the cfloop. */
 947                         if (get_irg_uplink(m) < get_irg_uplink(n))
 948                                 set_irg_uplink(n, get_irg_uplink(m));
 949                 }
 950         }
 951
 952         if (get_irg_dfn(n) == get_irg_uplink(n)) {
 953                 /* This condition holds for
 954                    1) the node with the incoming backedge.
 955                    That is: We found a cfloop!
 956                    2) Straight line code, because no uplink has been propagated, so the
 957                    uplink still is the same as the dfn.
 958
 959                    But n might not be a proper cfloop head for the analysis. Proper cfloop
 960                    heads are Block and Phi nodes. find_tail searches the stack for
 961                    Block's and Phi's and takes those nodes as cfloop heads for the current
 962                    cfloop instead and marks the incoming edge as backedge. */
 963
 964                 ir_graph *tail = find_tail(n);
 965                 if (tail) {
 966                         /* We have a cfloop, that is no straight line code,
 967                            because we found a cfloop head!
 968                            Next actions: Open a new cfloop on the cfloop tree and
 969                            try to find inner cfloops */
 970
 971
 972                         ir_loop *l = new_loop();
 973
 974                         /* Remove the cfloop from the stack ... */
 975                         pop_scc_unmark_visit(n);
 976
 977                         /* The current backedge has been marked, that is temporarily eliminated,
 978                            by find tail. Start the scc algorithm
 979                            anew on the subgraph thats left (the current cfloop without the backedge)
 980                            in order to find more inner cfloops. */
 981
 982                         cgscc(tail);
 983
 984                         assert(cg_irg_visited(n));
 985                         close_loop(l);
 986                 } else {
 987                         pop_scc_to_loop(n);
 988                 }
 989         }
 990 }
 991
 992
 993 /**
 994  * reset the backedge information for all callers in all irgs
 995  */
 996 static void reset_isbe(void) {
 997         int i, n_irgs = get_irp_n_irgs();
 998
 999         for (i = 0; i < n_irgs; ++i) {
1000                 ir_graph *irg = get_irp_irg(i);
1001
1002                 if (irg->caller_isbe)
1003                         xfree(irg->caller_isbe);
1004                 irg->caller_isbe = NULL;
1005
1006                 if (irg->callee_isbe)
1007                         xfree(irg->callee_isbe);
1008                 irg->callee_isbe = NULL;
1009         }
1010 }
1011
1012 /* ----------------------------------------------------------------------------------- */
1013 /* Another algorithm to compute recursion nesting depth                                */
1014 /* Walk the callgraph.  For each crossed edge increase the loop depth by the edge      */
1015 /* weight. Assign graphs the maximal depth.                                            */
1016 /* ----------------------------------------------------------------------------------- */
1017
1018 static void compute_loop_depth(ir_graph *irg, void *env) {
1019         int current_nesting = *(int *) env;
1020         int old_nesting = irg->callgraph_loop_depth;
1021         unsigned long old_visited = get_cg_irg_visited(irg);
1022         int i, n_callees;
1023
1024         //return ;
1025
1026         if (cg_irg_visited(irg)) return;
1027
1028         mark_cg_irg_visited(irg);
1029
1030         //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
1031
1032
1033         if (old_nesting < current_nesting)
1034                 irg->callgraph_loop_depth = current_nesting;
1035
1036         if (current_nesting > irp->max_callgraph_loop_depth)
1037                 irp->max_callgraph_loop_depth = current_nesting;
1038
1039         if ((old_visited +1 < get_cg_irg_visited(irg)) ||   /* not yet visited */
1040                 (old_nesting < current_nesting)) {        /* propagate larger nesting */
1041                         /* Don't walk the graph, but a tree that is an unfolded graph. */
1042                         n_callees = get_irg_n_callees(irg);
1043                         for (i = 0; i < n_callees; i++) {
1044                                 ir_graph *m = get_irg_callee(irg, i);
1045                                 *(int *)env += get_irg_callee_loop_depth(irg, i);
1046                                 compute_loop_depth(m, env);
1047                                 *(int *)env -= get_irg_callee_loop_depth(irg, i);
1048                         }
1049         }
1050
1051         set_cg_irg_visited(irg, master_cg_visited-1);
1052 }
1053
1054 /* ------------------------------------------------------------------------------------ */
1055 /* Another algorithm to compute recursion nesting depth                                 */
1056 /* Walk the callgraph.  For each crossed loop increase the nesting depth by one.        */
1057 /* Assign graphs the maximal nesting depth.   Don't increase if passing loops more than */
1058 /* once.                                                                               */
1059 /* ------------------------------------------------------------------------------------ */
1060
1061
1062 /* For callees, we want to remember the Call nodes, too. */
1063 typedef struct ana_entry2 {
1064         ir_loop **loop_stack;   /**< a stack of ir_loop entries */
1065         int tos;                /**< the top of stack entry */
1066         int recursion_nesting;
1067 } ana_entry2;
1068
1069 /**
1070  * push a loop entry on the stack
1071  */
1072 static void push2(ana_entry2 *e, ir_loop *g) {
1073         if (ARR_LEN(e->loop_stack) == e->tos) {
1074                 ARR_APP1(ir_loop *, e->loop_stack, g);
1075         } else {
1076                 e->loop_stack[e->tos] = g;
1077         }
1078         ++e->tos;
1079 }
1080
1081 /**
1082  * returns the top of stack and pop it
1083  */
1084 static ir_loop *pop2(ana_entry2 *e) {
1085         return e->loop_stack[--e->tos];
1086 }
1087
1088 /**
1089  * check if a loop g in on the stack. Did not check the TOS.
1090  */
1091 static int in_stack(ana_entry2 *e, ir_loop *g) {
1092         int i;
1093         for (i = e->tos-1; i >= 0; --i) {
1094                 if (e->loop_stack[i] == g) return 1;
1095         }
1096         return 0;
1097 }
1098
1099 static void compute_rec_depth(ir_graph *irg, void *env) {
1100         ana_entry2 *e = (ana_entry2 *)env;
1101         ir_loop *l = irg->l;
1102         int depth, old_depth = irg->callgraph_recursion_depth;
1103         int i, n_callees;
1104         int pushed = 0;
1105
1106         if (cg_irg_visited(irg))
1107                 return;
1108         mark_cg_irg_visited(irg);
1109
1110         /* -- compute and set the new nesting value -- */
1111         if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1112                 push2(e, l);
1113                 e->recursion_nesting++;
1114                 pushed = 1;
1115         }
1116         depth = e->recursion_nesting;
1117
1118         if (old_depth < depth)
1119                 irg->callgraph_recursion_depth = depth;
1120
1121         if (depth > irp->max_callgraph_recursion_depth)
1122                 irp->max_callgraph_recursion_depth = depth;
1123
1124         /* -- spread the nesting value -- */
1125         if (depth == 0 || old_depth < depth) {
1126                 /* Don't walk the graph, but a tree that is an unfolded graph.
1127                    Therefore we unset the visited flag at the end. */
1128                 n_callees = get_irg_n_callees(irg);
1129                 for (i = 0; i < n_callees; ++i) {
1130                         ir_graph *m = get_irg_callee(irg, i);
1131                         compute_rec_depth(m, env);
1132                 }
1133         }
1134
1135         /* -- clean up -- */
1136         if (pushed) {
1137                 pop2(e);
1138                 e->recursion_nesting--;
1139         }
1140         set_cg_irg_visited(irg, master_cg_visited-1);
1141 }
1142
1143
1144 /* ----------------------------------------------------------------------------------- */
1145 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1146 /* Walk the callgraph.  Ignore backedges.  Use sum of execution frequencies of Call     */
1147 /* nodes to evaluate a callgraph edge.                                                 */
1148 /* ----------------------------------------------------------------------------------- */
1149
1150 /* Returns the method execution frequency of a graph. */
1151 double get_irg_method_execution_frequency(ir_graph *irg) {
1152         return irg->method_execution_frequency;
1153 }
1154
1155 /**
1156  * Increase the method execution frequency to freq if its current value is
1157  * smaller then this.
1158  */
1159 static void set_irg_method_execution_frequency(ir_graph *irg, double freq) {
1160         irg->method_execution_frequency = freq;
1161
1162         if (irp->max_method_execution_frequency < freq)
1163                 irp->max_method_execution_frequency = freq;
1164 }
1165
1166 static void compute_method_execution_frequency(ir_graph *irg, void *env) {
1167         int i, n_callers;
1168         double freq;
1169         int    found_edge;
1170         int    n_callees;
1171         (void) env;
1172
1173         if (cg_irg_visited(irg))
1174                 return;
1175
1176         /* We need the values of all predecessors (except backedges).
1177            So they must be marked.  Else we will reach the node through
1178            one of the unmarked ones. */
1179         n_callers = get_irg_n_callers(irg);
1180         for (i = 0; i < n_callers; ++i) {
1181                 ir_graph *m = get_irg_caller(irg, i);
1182                 if (is_irg_caller_backedge(irg, i))
1183                         continue;
1184                 if (!cg_irg_visited(m)) {
1185                         return;
1186                 }
1187         }
1188         mark_cg_irg_visited(irg);
1189
1190         /* Compute the new frequency. */
1191         freq = 0;
1192         found_edge = 0;
1193         for (i = 0; i < n_callers; i++) {
1194                 if (! is_irg_caller_backedge(irg, i)) {
1195                         double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1196                         assert(edge_freq >= 0);
1197                         freq += edge_freq;
1198                         found_edge = 1;
1199                 }
1200         }
1201
1202         if (!found_edge) {
1203                 /* A starting point: method only called from outside,
1204                 or only backedges as predecessors. */
1205                 freq = 1;
1206         }
1207
1208         set_irg_method_execution_frequency(irg, freq);
1209
1210         /* recur */
1211         n_callees = get_irg_n_callees(irg);
1212         for (i = 0; i < n_callees; ++i) {
1213                 compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
1214         }
1215 }
1216
1217
1218 /* ----------------------------------------------------------------------------------- */
1219 /* The recursion stuff driver.                                                         */
1220 /* ----------------------------------------------------------------------------------- */
1221
1222 /* Compute the backedges that represent recursions. */
1223 void find_callgraph_recursions(void) {
1224         int i, n_irgs = get_irp_n_irgs();
1225         struct obstack temp;
1226
1227         reset_isbe();
1228
1229         /* -- compute the looptree. -- */
1230
1231         /* The outermost graph.  We start here.  Then we start at all
1232         functions in irg list that are never called, then at the remaining
1233         unvisited ones. The third step is needed for functions that are not
1234         reachable from the outermost graph, but call themselves in a cycle. */
1235         assert(get_irp_main_irg());
1236         outermost_ir_graph = get_irp_main_irg();
1237         obstack_init(&temp);
1238         init_scc(&temp);
1239
1240         current_loop = NULL;
1241         new_loop();  /* sets current_loop */
1242
1243         ++master_cg_visited;
1244         cgscc(outermost_ir_graph);
1245         for (i = 0; i < n_irgs; ++i) {
1246                 ir_graph *irg = get_irp_irg(i);
1247                 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1248                         cgscc(irg);
1249         }
1250         for (i = 0; i < n_irgs; ++i) {
1251                 ir_graph *irg = get_irp_irg(i);
1252                 if (!cg_irg_visited(irg))
1253                         cgscc(irg);
1254         }
1255         obstack_free(&temp, NULL);
1256
1257         irp->outermost_cg_loop = current_loop;
1258         mature_loops(current_loop, outermost_ir_graph->obst);
1259
1260         /* -- Reverse the backedge information. -- */
1261         for (i = 0; i < n_irgs; ++i) {
1262                 ir_graph *irg = get_irp_irg(i);
1263                 int j, n_callees = get_irg_n_callees(irg);
1264                 for (j = 0; j < n_callees; ++j) {
1265                         if (is_irg_callee_backedge(irg, j))
1266                                 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1267                 }
1268         }
1269
1270         irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1271 }
1272
1273 /* Compute interprocedural performance estimates. */
1274 void compute_performance_estimates(void) {
1275         int i, n_irgs = get_irp_n_irgs();
1276         int current_nesting;
1277         ana_entry2 e;
1278
1279         assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated");
1280
1281         /* -- compute the loop depth  -- */
1282         current_nesting = 0;
1283         irp->max_callgraph_loop_depth = 0;
1284         master_cg_visited += 2;
1285         //printf(" ** starting at      "); DDMG(get_irp_main_irg());
1286         compute_loop_depth(get_irp_main_irg(), &current_nesting);
1287         for (i = 0; i < n_irgs; i++) {
1288                 ir_graph *irg = get_irp_irg(i);
1289                 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1290                         get_irg_n_callers(irg) == 0) {
1291                                 compute_loop_depth(irg, &current_nesting);
1292                                 //printf(" ** starting at      "); DDMG(irg);
1293                 }
1294         }
1295         for (i = 0; i < n_irgs; i++) {
1296                 ir_graph *irg = get_irp_irg(i);
1297                 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1298                         compute_loop_depth(irg, &current_nesting);
1299                         //printf(" ** starting at      "); DDMG(irg);
1300                 }
1301         }
1302
1303
1304         /* -- compute the recursion depth -- */
1305         e.loop_stack        = NEW_ARR_F(ir_loop *, 0);
1306         e.tos               = 0;
1307         e.recursion_nesting = 0;
1308
1309         irp->max_callgraph_recursion_depth = 0;
1310
1311         master_cg_visited += 2;
1312         compute_rec_depth(get_irp_main_irg(), &e);
1313         //printf(" ++ starting at "); DDMG(get_irp_main_irg());
1314         for (i = 0; i < n_irgs; i++) {
1315                 ir_graph *irg = get_irp_irg(i);
1316                 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1317                         get_irg_n_callers(irg) == 0) {
1318                                 compute_rec_depth(irg, &e);
1319                                 //printf(" ++ starting at "); DDMG(irg);
1320                 }
1321         }
1322         for (i = 0; i < n_irgs; i++) {
1323                 ir_graph *irg = get_irp_irg(i);
1324                 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1325                         compute_rec_depth(irg, &e);
1326                         //printf(" ++ starting at "); DDMG(irg);
1327                 }
1328         }
1329
1330         DEL_ARR_F(e.loop_stack);
1331
1332         /* -- compute the execution frequency -- */
1333         irp->max_method_execution_frequency = 0;
1334         master_cg_visited += 2;
1335         assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1336         compute_method_execution_frequency(get_irp_main_irg(), NULL);
1337         for (i = 0; i < n_irgs; i++) {
1338                 ir_graph *irg = get_irp_irg(i);
1339                 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1340                         get_irg_n_callers(irg) == 0) {
1341                                 compute_method_execution_frequency(irg, NULL);
1342                 }
1343         }
1344         for (i = 0; i < n_irgs; i++) {
1345                 ir_graph *irg = get_irp_irg(i);
1346                 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1347                         compute_method_execution_frequency(irg, NULL);
1348                 }
1349         }
1350 }
1351
1352 /* Returns the maximal loop depth of all paths from an external visible method to
1353    this irg. */
1354 int  get_irg_loop_depth(ir_graph *irg) {
1355         assert(irp->callgraph_state == irp_callgraph_consistent ||
1356                 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1357         return  irg->callgraph_loop_depth;
1358 }
1359
1360 /* Returns the maximal recursion depth of all paths from an external visible method to
1361    this irg. */
1362 int get_irg_recursion_depth(ir_graph *irg) {
1363         assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1364         return irg->callgraph_recursion_depth;
1365 }
1366
1367 /* Computes the interprocedural loop nesting information. */
1368 void analyse_loop_nesting_depth(void) {
1369         ir_entity **free_methods = NULL;
1370         int arr_len;
1371
1372         /* establish preconditions. */
1373         if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1374                 cgana(&arr_len, &free_methods);
1375         }
1376
1377         if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1378                 compute_callgraph();
1379         }
1380
1381         find_callgraph_recursions();
1382
1383         compute_performance_estimates();
1384
1385         set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1386 }
1387
1388 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) {
1389         return irp->lnd_state;
1390 }
1391 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) {
1392         irp->lnd_state = s;
1393 }
1394 void set_irp_loop_nesting_depth_state_inconsistent(void) {
1395         if (irp->lnd_state == loop_nesting_depth_consistent)
1396                 irp->lnd_state = loop_nesting_depth_inconsistent;
1397 }