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

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