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