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