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

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