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

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