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

   1 /*
   2  * Copyright (C) 1995-2011 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         size_t 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 = (cg_callee_entry*) 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 = (const cg_callee_entry*) elt;
 286         const cg_callee_entry *e2 = (const cg_callee_entry*) 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 = (const ir_graph*) elt;
 294         const ir_graph *e2 = (const ir_graph*) key;
 295         return e1 != e2;
 296 }
 297
 298
 299 /* Construct and destruct the callgraph. */
 300 void compute_callgraph(void)
 301 {
 302         size_t 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                 size_t 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 = (cg_callee_entry*) pset_first(callee_set);
 335                 for (j = 0; j < count; ++j) {
 336                         irg->callees[j] = callee;
 337                         callee = (cg_callee_entry*) 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 = (ir_graph*) pset_first(caller_set);
 347                 for (j = 0; j < count; ++j) {
 348                         irg->callers[j] = c;
 349                         c = (ir_graph*) 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         size_t 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         size_t 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 = (scc_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 = (scc_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 = (scc_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 = (scc_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 = (scc_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 = (scc_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 = (scc_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 size_t 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                 size_t nlen = ARR_LEN(stack) * 2;
 563                 ARR_RESIZE(ir_graph*, 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;
 575
 576         assert(tos > 0);
 577         irg = stack[--tos];
 578         mark_irg_not_in_stack(irg);
 579         return irg;
 580 }
 581
 582 /**
 583  * The nodes up to irg belong to the current loop.
 584  * Removes them from the stack and adds them to the current loop.
 585  */
 586 static inline void pop_scc_to_loop(ir_graph *irg)
 587 {
 588         ir_graph *m;
 589
 590         do {
 591                 m = pop();
 592                 loop_node_cnt++;
 593                 set_irg_dfn(m, loop_node_cnt);
 594                 add_loop_irg(current_loop, m);
 595                 m->l = current_loop;
 596                 //m->callgraph_loop_depth = current_loop->depth;
 597         } while (m != irg);
 598 }
 599
 600 /* GL ??? my last son is my grandson???  Removes cfloops with no
 601    ir_nodes in them.  Such loops have only another loop as son. (Why
 602    can't they have two loops as sons? Does it never get that far? ) */
 603 static void close_loop(ir_loop *l)
 604 {
 605         int last = get_loop_n_elements(l) - 1;
 606         loop_element lelement = get_loop_element(l, last);
 607         ir_loop *last_son = lelement.son;
 608
 609         if (get_kind(last_son) == k_ir_loop &&
 610             get_loop_n_elements(last_son) == 1) {
 611                 ir_loop *gson;
 612
 613                 lelement = get_loop_element(last_son, 0);
 614                 gson = lelement.son;
 615                 if (get_kind(gson) == k_ir_loop) {
 616                         loop_element new_last_son;
 617
 618                         gson->outer_loop = l;
 619                         new_last_son.son = gson;
 620                         l->children[last] = new_last_son;
 621                 }
 622         }
 623         current_loop = l;
 624 }
 625
 626 /**
 627  * Removes and unmarks all nodes up to n from the stack.
 628  * The nodes must be visited once more to assign them to a scc.
 629  */
 630 static inline void pop_scc_unmark_visit(ir_graph *n)
 631 {
 632         ir_graph *m = NULL;
 633
 634         while (m != n) {
 635                 m = pop();
 636                 set_cg_irg_visited(m, 0);
 637         }
 638 }
 639
 640 /**********************************************************************/
 641 /* The loop data structure.                                          **/
 642 /**********************************************************************/
 643
 644 /**
 645  * Allocates a new loop as son of current_loop.  Sets current_loop
 646  * to the new loop and returns the father.
 647  */
 648 static ir_loop *new_loop(void)
 649 {
 650         ir_loop *father = current_loop;
 651         ir_loop *son    = alloc_loop(father, outermost_ir_graph->obst);
 652
 653         current_loop = son;
 654         return father;
 655 }
 656
 657
 658 /**********************************************************************/
 659 /* Constructing and destructing the loop/backedge information.       **/
 660 /**********************************************************************/
 661
 662 /* Initialization steps. **********************************************/
 663
 664 static void init_scc(struct obstack *obst)
 665 {
 666         size_t i, n_irgs;
 667
 668         current_dfn   = 1;
 669         loop_node_cnt = 0;
 670         init_stack();
 671
 672         n_irgs = get_irp_n_irgs();
 673         for (i = 0; i < n_irgs; ++i) {
 674                 ir_graph *irg = get_irp_irg(i);
 675                 set_irg_link(irg, new_scc_info(obst));
 676                 irg->callgraph_recursion_depth = 0;
 677                 irg->callgraph_loop_depth      = 0;
 678         }
 679 }
 680
 681 /** Returns non-zero if n is a loop header, i.e., it is a Block node
 682  *  and has predecessors within the cfloop and out of the cfloop.
 683  *
 684  *  @param root: only needed for assertion.
 685  */
 686 static int is_head(ir_graph *n, ir_graph *root)
 687 {
 688         int i, arity;
 689         int some_outof_loop = 0, some_in_loop = 0;
 690
 691         arity = get_irg_n_callees(n);
 692         for (i = 0; i < arity; i++) {
 693                 ir_graph *pred = get_irg_callee(n, i);
 694                 if (is_irg_callee_backedge(n, i)) continue;
 695                 if (!irg_is_in_stack(pred)) {
 696                         some_outof_loop = 1;
 697                 } else {
 698                         if (get_irg_uplink(pred) < get_irg_uplink(root))  {
 699                                 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
 700                         }
 701                         some_in_loop = 1;
 702                 }
 703         }
 704
 705         return some_outof_loop && some_in_loop;
 706 }
 707
 708 /**
 709  * Returns non-zero if n is possible loop head of an endless loop.
 710  * I.e., it is a Block or Phi node and has only predecessors
 711  * within the loop.
 712  * @arg root: only needed for assertion.
 713  */
 714 static int is_endless_head(ir_graph *n, ir_graph *root)
 715 {
 716         int i, arity;
 717         int some_outof_loop = 0, some_in_loop = 0;
 718
 719         arity = get_irg_n_callees(n);
 720         for (i = 0; i < arity; i++) {
 721                 ir_graph *pred = get_irg_callee(n, i);
 722                 assert(pred);
 723                 if (is_irg_callee_backedge(n, i))
 724                         continue;
 725                 if (!irg_is_in_stack(pred)) {
 726                         some_outof_loop = 1;
 727                 } else {
 728                         if (get_irg_uplink(pred) < get_irg_uplink(root)) {
 729                                 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
 730                         }
 731                         some_in_loop = 1;
 732                 }
 733         }
 734         return !some_outof_loop && some_in_loop;
 735 }
 736
 737 /**
 738  * Returns index of the predecessor with the smallest dfn number
 739  * greater-equal than limit.
 740  */
 741 static int smallest_dfn_pred(ir_graph *n, int limit)
 742 {
 743         int i, index = -2, min = -1;
 744
 745         int arity = get_irg_n_callees(n);
 746         for (i = 0; i < arity; i++) {
 747                 ir_graph *pred = get_irg_callee(n, i);
 748                 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred))
 749                         continue;
 750                 if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
 751                         index = i;
 752                         min = get_irg_dfn(pred);
 753                 }
 754         }
 755
 756         return index;
 757 }
 758
 759 /** Returns index of the predecessor with the largest dfn number. */
 760 static int largest_dfn_pred(ir_graph *n)
 761 {
 762         int i, index = -2, max = -1;
 763
 764         int arity = get_irg_n_callees(n);
 765         for (i = 0; i < arity; ++i) {
 766                 ir_graph *pred = get_irg_callee(n, i);
 767                 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
 768                 if (get_irg_dfn(pred) > max) {
 769                         index = i;
 770                         max = get_irg_dfn(pred);
 771                 }
 772         }
 773
 774         return index;
 775 }
 776
 777 static ir_graph *find_tail(ir_graph *n)
 778 {
 779         ir_graph *m;
 780         int i, res_index = -2;
 781
 782         /*
 783         if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
 784         */
 785         m = stack[tos-1];  /* tos = top of stack */
 786         if (is_head (m, n)) {
 787                 res_index = smallest_dfn_pred(m, 0);
 788                 if ((res_index == -2) &&  /* no smallest dfn pred found. */
 789                         (n == m))
 790                         return NULL;
 791         } else {
 792                 if (m == n) return NULL;    // Is this to catch Phi - self loops?
 793                 for (i = tos-2; i >= 0; --i) {
 794                         m = stack[i];
 795
 796                         if (is_head(m, n)) {
 797                                 res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
 798                                 if (res_index == -2)  /* no smallest dfn pred found. */
 799                                         res_index = largest_dfn_pred(m);
 800
 801                                 if ((m == n) && (res_index == -2)) {
 802                                         i = -1;
 803                                 }
 804                                 break;
 805                         }
 806
 807                         /* We should not walk past our selves on the stack:  The upcoming nodes
 808                            are not in this loop. We assume a loop not reachable from Start. */
 809                         if (m == n) {
 810                                 i = -1;
 811                                 break;
 812                         }
 813
 814                 }
 815
 816                 if (i < 0) {
 817                         /* A dead loop not reachable from Start. */
 818                         for (i = tos-2; i >= 0; --i) {
 819                                 m = stack[i];
 820                                 if (is_endless_head(m, n)) {
 821                                         res_index = smallest_dfn_pred(m, get_irg_dfn(m) + 1);
 822                                         if (res_index == -2)  /* no smallest dfn pred found. */
 823                                                 res_index = largest_dfn_pred(m);
 824                                         break;
 825                                 }
 826                                 if (m == n) { break; }  /* It's not an unreachable loop, either. */
 827                         }
 828                         //assert(0 && "no head found on stack");
 829                 }
 830
 831         }
 832         assert (res_index > -2);
 833
 834         set_irg_callee_backedge(m, res_index);
 835         return get_irg_callee(m, res_index);
 836 }
 837
 838 /*-----------------------------------------------------------*
 839  *                   The core algorithm.                     *
 840  *-----------------------------------------------------------*/
 841
 842
 843 static void cgscc(ir_graph *n)
 844 {
 845         int i, arity;
 846
 847         if (cg_irg_visited(n)) return;
 848         mark_cg_irg_visited(n);
 849
 850         /* Initialize the node */
 851         set_irg_dfn(n, current_dfn);      /* Depth first number for this node */
 852         set_irg_uplink(n, current_dfn);   /* ... is default uplink. */
 853         current_dfn ++;
 854         push(n);
 855
 856         arity = get_irg_n_callees(n);
 857         for (i = 0; i < arity; i++) {
 858                 ir_graph *m;
 859                 if (is_irg_callee_backedge(n, i)) continue;
 860                 m = get_irg_callee(n, i);
 861
 862                 /** This marks the backedge, but does it guarantee a correct loop tree? */
 863                 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
 864
 865                 cgscc(m);
 866                 if (irg_is_in_stack(m)) {
 867                         /* Uplink of m is smaller if n->m is a backedge.
 868                            Propagate the uplink to mark the cfloop. */
 869                         if (get_irg_uplink(m) < get_irg_uplink(n))
 870                                 set_irg_uplink(n, get_irg_uplink(m));
 871                 }
 872         }
 873
 874         if (get_irg_dfn(n) == get_irg_uplink(n)) {
 875                 /* This condition holds for
 876                    1) the node with the incoming backedge.
 877                    That is: We found a cfloop!
 878                    2) Straight line code, because no uplink has been propagated, so the
 879                    uplink still is the same as the dfn.
 880
 881                    But n might not be a proper cfloop head for the analysis. Proper cfloop
 882                    heads are Block and Phi nodes. find_tail searches the stack for
 883                    Block's and Phi's and takes those nodes as cfloop heads for the current
 884                    cfloop instead and marks the incoming edge as backedge. */
 885
 886                 ir_graph *tail = find_tail(n);
 887                 if (tail) {
 888                         /* We have a cfloop, that is no straight line code,
 889                            because we found a cfloop head!
 890                            Next actions: Open a new cfloop on the cfloop tree and
 891                            try to find inner cfloops */
 892
 893
 894                         ir_loop *l = new_loop();
 895
 896                         /* Remove the cfloop from the stack ... */
 897                         pop_scc_unmark_visit(n);
 898
 899                         /* The current backedge has been marked, that is temporarily eliminated,
 900                            by find tail. Start the scc algorithm
 901                            anew on the subgraph thats left (the current cfloop without the backedge)
 902                            in order to find more inner cfloops. */
 903
 904                         cgscc(tail);
 905
 906                         assert(cg_irg_visited(n));
 907                         close_loop(l);
 908                 } else {
 909                         pop_scc_to_loop(n);
 910                 }
 911         }
 912 }
 913
 914
 915 /**
 916  * reset the backedge information for all callers in all irgs
 917  */
 918 static void reset_isbe(void)
 919 {
 920         size_t i, n_irgs = get_irp_n_irgs();
 921
 922         for (i = 0; i < n_irgs; ++i) {
 923                 ir_graph *irg = get_irp_irg(i);
 924
 925                 if (irg->caller_isbe)
 926                         xfree(irg->caller_isbe);
 927                 irg->caller_isbe = NULL;
 928
 929                 if (irg->callee_isbe)
 930                         xfree(irg->callee_isbe);
 931                 irg->callee_isbe = NULL;
 932         }
 933 }
 934
 935 /* ----------------------------------------------------------------------------------- */
 936 /* Another algorithm to compute recursion nesting depth                                */
 937 /* Walk the callgraph.  For each crossed edge increase the loop depth by the edge      */
 938 /* weight. Assign graphs the maximal depth.                                            */
 939 /* ----------------------------------------------------------------------------------- */
 940
 941 static void compute_loop_depth(ir_graph *irg, void *env)
 942 {
 943         int current_nesting = *(int *) env;
 944         int old_nesting = irg->callgraph_loop_depth;
 945         ir_visited_t old_visited = get_cg_irg_visited(irg);
 946         int i, n_callees;
 947
 948         //return ;
 949
 950         if (cg_irg_visited(irg)) return;
 951
 952         mark_cg_irg_visited(irg);
 953
 954         if (old_nesting < current_nesting)
 955                 irg->callgraph_loop_depth = current_nesting;
 956
 957         if (current_nesting > irp->max_callgraph_loop_depth)
 958                 irp->max_callgraph_loop_depth = current_nesting;
 959
 960         if ((old_visited +1 < get_cg_irg_visited(irg)) ||   /* not yet visited */
 961                 (old_nesting < current_nesting)) {        /* propagate larger nesting */
 962                         /* Don't walk the graph, but a tree that is an unfolded graph. */
 963                         n_callees = get_irg_n_callees(irg);
 964                         for (i = 0; i < n_callees; i++) {
 965                                 ir_graph *m = get_irg_callee(irg, i);
 966                                 *(int *)env += get_irg_callee_loop_depth(irg, i);
 967                                 compute_loop_depth(m, env);
 968                                 *(int *)env -= get_irg_callee_loop_depth(irg, i);
 969                         }
 970         }
 971
 972         set_cg_irg_visited(irg, master_cg_visited-1);
 973 }
 974
 975 /* ------------------------------------------------------------------------------------ */
 976 /* Another algorithm to compute recursion nesting depth                                 */
 977 /* Walk the callgraph.  For each crossed loop increase the nesting depth by one.        */
 978 /* Assign graphs the maximal nesting depth.   Don't increase if passing loops more than */
 979 /* once.                                                                               */
 980 /* ------------------------------------------------------------------------------------ */
 981
 982
 983 /* For callees, we want to remember the Call nodes, too. */
 984 typedef struct ana_entry2 {
 985         ir_loop **loop_stack;   /**< a stack of ir_loop entries */
 986         size_t    tos;          /**< the top of stack entry */
 987         int recursion_nesting;
 988 } ana_entry2;
 989
 990 /**
 991  * push a loop entry on the stack
 992  */
 993 static void push2(ana_entry2 *e, ir_loop *g)
 994 {
 995         if (ARR_LEN(e->loop_stack) == e->tos) {
 996                 ARR_APP1(ir_loop *, e->loop_stack, g);
 997         } else {
 998                 e->loop_stack[e->tos] = g;
 999         }
1000         ++e->tos;
1001 }
1002
1003 /**
1004  * returns the top of stack and pop it
1005  */
1006 static ir_loop *pop2(ana_entry2 *e)
1007 {
1008         return e->loop_stack[--e->tos];
1009 }
1010
1011 /**
1012  * check if a loop g in on the stack. Did not check the TOS.
1013  */
1014 static int in_stack(ana_entry2 *e, ir_loop *g)
1015 {
1016         size_t i;
1017         for (i = e->tos; i != 0;) {
1018                 if (e->loop_stack[--i] == g) return 1;
1019         }
1020         return 0;
1021 }
1022
1023 static void compute_rec_depth(ir_graph *irg, void *env)
1024 {
1025         ana_entry2 *e = (ana_entry2 *)env;
1026         ir_loop *l = irg->l;
1027         int depth, old_depth = irg->callgraph_recursion_depth;
1028         int i, n_callees;
1029         int pushed = 0;
1030
1031         if (cg_irg_visited(irg))
1032                 return;
1033         mark_cg_irg_visited(irg);
1034
1035         /* -- compute and set the new nesting value -- */
1036         if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1037                 push2(e, l);
1038                 e->recursion_nesting++;
1039                 pushed = 1;
1040         }
1041         depth = e->recursion_nesting;
1042
1043         if (old_depth < depth)
1044                 irg->callgraph_recursion_depth = depth;
1045
1046         if (depth > irp->max_callgraph_recursion_depth)
1047                 irp->max_callgraph_recursion_depth = depth;
1048
1049         /* -- spread the nesting value -- */
1050         if (depth == 0 || old_depth < depth) {
1051                 /* Don't walk the graph, but a tree that is an unfolded graph.
1052                    Therefore we unset the visited flag at the end. */
1053                 n_callees = get_irg_n_callees(irg);
1054                 for (i = 0; i < n_callees; ++i) {
1055                         ir_graph *m = get_irg_callee(irg, i);
1056                         compute_rec_depth(m, env);
1057                 }
1058         }
1059
1060         /* -- clean up -- */
1061         if (pushed) {
1062                 pop2(e);
1063                 e->recursion_nesting--;
1064         }
1065         set_cg_irg_visited(irg, master_cg_visited-1);
1066 }
1067
1068
1069 /* ----------------------------------------------------------------------------------- */
1070 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1071 /* Walk the callgraph.  Ignore backedges.  Use sum of execution frequencies of Call     */
1072 /* nodes to evaluate a callgraph edge.                                                 */
1073 /* ----------------------------------------------------------------------------------- */
1074
1075 /* Returns the method execution frequency of a graph. */
1076 double get_irg_method_execution_frequency(const ir_graph *irg)
1077 {
1078         return irg->method_execution_frequency;
1079 }
1080
1081 /**
1082  * Increase the method execution frequency to freq if its current value is
1083  * smaller then this.
1084  */
1085 static void set_irg_method_execution_frequency(ir_graph *irg, double freq)
1086 {
1087         irg->method_execution_frequency = freq;
1088
1089         if (irp->max_method_execution_frequency < freq)
1090                 irp->max_method_execution_frequency = freq;
1091 }
1092
1093 static void compute_method_execution_frequency(ir_graph *irg, void *env)
1094 {
1095         int i, n_callers;
1096         double freq;
1097         int    found_edge;
1098         int    n_callees;
1099         (void) env;
1100
1101         if (cg_irg_visited(irg))
1102                 return;
1103
1104         /* We need the values of all predecessors (except backedges).
1105            So they must be marked.  Else we will reach the node through
1106            one of the unmarked ones. */
1107         n_callers = get_irg_n_callers(irg);
1108         for (i = 0; i < n_callers; ++i) {
1109                 ir_graph *m = get_irg_caller(irg, i);
1110                 if (is_irg_caller_backedge(irg, i))
1111                         continue;
1112                 if (!cg_irg_visited(m)) {
1113                         return;
1114                 }
1115         }
1116         mark_cg_irg_visited(irg);
1117
1118         /* Compute the new frequency. */
1119         freq = 0;
1120         found_edge = 0;
1121         for (i = 0; i < n_callers; i++) {
1122                 if (! is_irg_caller_backedge(irg, i)) {
1123                         double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1124                         assert(edge_freq >= 0);
1125                         freq += edge_freq;
1126                         found_edge = 1;
1127                 }
1128         }
1129
1130         if (!found_edge) {
1131                 /* A starting point: method only called from outside,
1132                 or only backedges as predecessors. */
1133                 freq = 1;
1134         }
1135
1136         set_irg_method_execution_frequency(irg, freq);
1137
1138         /* recur */
1139         n_callees = get_irg_n_callees(irg);
1140         for (i = 0; i < n_callees; ++i) {
1141                 compute_method_execution_frequency(get_irg_callee(irg, i), NULL);
1142         }
1143 }
1144
1145
1146 /* ----------------------------------------------------------------------------------- */
1147 /* The recursion stuff driver.                                                         */
1148 /* ----------------------------------------------------------------------------------- */
1149
1150 /* Compute the backedges that represent recursions. */
1151 void find_callgraph_recursions(void)
1152 {
1153         size_t i, n_irgs;
1154         struct obstack temp;
1155
1156         reset_isbe();
1157
1158         /* -- compute the looptree. -- */
1159
1160         /* The outermost graph.  We start here.  Then we start at all
1161         functions in irg list that are never called, then at the remaining
1162         unvisited ones. The third step is needed for functions that are not
1163         reachable from the outermost graph, but call themselves in a cycle. */
1164         assert(get_irp_main_irg());
1165         outermost_ir_graph = get_irp_main_irg();
1166         obstack_init(&temp);
1167         init_scc(&temp);
1168
1169         current_loop = NULL;
1170         new_loop();  /* sets current_loop */
1171
1172         ++master_cg_visited;
1173         cgscc(outermost_ir_graph);
1174         n_irgs = get_irp_n_irgs();
1175         for (i = 0; i < n_irgs; ++i) {
1176                 ir_graph *irg = get_irp_irg(i);
1177                 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1178                         cgscc(irg);
1179         }
1180         for (i = 0; i < n_irgs; ++i) {
1181                 ir_graph *irg = get_irp_irg(i);
1182                 if (!cg_irg_visited(irg))
1183                         cgscc(irg);
1184         }
1185         obstack_free(&temp, NULL);
1186
1187         irp->outermost_cg_loop = current_loop;
1188         mature_loops(current_loop, outermost_ir_graph->obst);
1189
1190         /* -- Reverse the backedge information. -- */
1191         for (i = 0; i < n_irgs; ++i) {
1192                 ir_graph *irg = get_irp_irg(i);
1193                 int j, n_callees = get_irg_n_callees(irg);
1194                 for (j = 0; j < n_callees; ++j) {
1195                         if (is_irg_callee_backedge(irg, j))
1196                                 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1197                 }
1198         }
1199
1200         irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1201 }
1202
1203 /* Compute interprocedural performance estimates. */
1204 void compute_performance_estimates(void)
1205 {
1206         int i, n_irgs = get_irp_n_irgs();
1207         int current_nesting;
1208         ana_entry2 e;
1209
1210         assert(get_irp_exec_freq_state() != exec_freq_none && "execution frequency not calculated");
1211
1212         /* -- compute the loop depth  -- */
1213         current_nesting = 0;
1214         irp->max_callgraph_loop_depth = 0;
1215         master_cg_visited += 2;
1216         compute_loop_depth(get_irp_main_irg(), &current_nesting);
1217         for (i = 0; i < n_irgs; i++) {
1218                 ir_graph *irg = get_irp_irg(i);
1219                 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1220                         get_irg_n_callers(irg) == 0) {
1221                                 compute_loop_depth(irg, &current_nesting);
1222                 }
1223         }
1224         for (i = 0; i < n_irgs; i++) {
1225                 ir_graph *irg = get_irp_irg(i);
1226                 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1227                         compute_loop_depth(irg, &current_nesting);
1228                 }
1229         }
1230
1231
1232         /* -- compute the recursion depth -- */
1233         e.loop_stack        = NEW_ARR_F(ir_loop *, 0);
1234         e.tos               = 0;
1235         e.recursion_nesting = 0;
1236
1237         irp->max_callgraph_recursion_depth = 0;
1238
1239         master_cg_visited += 2;
1240         compute_rec_depth(get_irp_main_irg(), &e);
1241         for (i = 0; i < n_irgs; i++) {
1242                 ir_graph *irg = get_irp_irg(i);
1243                 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1244                         get_irg_n_callers(irg) == 0) {
1245                                 compute_rec_depth(irg, &e);
1246                 }
1247         }
1248         for (i = 0; i < n_irgs; i++) {
1249                 ir_graph *irg = get_irp_irg(i);
1250                 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1251                         compute_rec_depth(irg, &e);
1252                 }
1253         }
1254
1255         DEL_ARR_F(e.loop_stack);
1256
1257         /* -- compute the execution frequency -- */
1258         irp->max_method_execution_frequency = 0;
1259         master_cg_visited += 2;
1260         assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1261         compute_method_execution_frequency(get_irp_main_irg(), NULL);
1262         for (i = 0; i < n_irgs; i++) {
1263                 ir_graph *irg = get_irp_irg(i);
1264                 if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1265                         get_irg_n_callers(irg) == 0) {
1266                                 compute_method_execution_frequency(irg, NULL);
1267                 }
1268         }
1269         for (i = 0; i < n_irgs; i++) {
1270                 ir_graph *irg = get_irp_irg(i);
1271                 if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1272                         compute_method_execution_frequency(irg, NULL);
1273                 }
1274         }
1275 }
1276
1277 /* Returns the maximal loop depth of all paths from an external visible method to
1278    this irg. */
1279 int  get_irg_loop_depth(const ir_graph *irg)
1280 {
1281         assert(irp->callgraph_state == irp_callgraph_consistent ||
1282                 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1283         return  irg->callgraph_loop_depth;
1284 }
1285
1286 /* Returns the maximal recursion depth of all paths from an external visible method to
1287    this irg. */
1288 int get_irg_recursion_depth(const ir_graph *irg)
1289 {
1290         assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1291         return irg->callgraph_recursion_depth;
1292 }
1293
1294 /* Computes the interprocedural loop nesting information. */
1295 void analyse_loop_nesting_depth(void)
1296 {
1297         /* establish preconditions. */
1298         if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1299                 ir_entity **free_methods = NULL;
1300
1301                 cgana(&free_methods);
1302                 xfree(free_methods);
1303         }
1304
1305         if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1306                 compute_callgraph();
1307         }
1308
1309         find_callgraph_recursions();
1310
1311         compute_performance_estimates();
1312
1313         set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1314 }
1315
1316 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void)
1317 {
1318         return irp->lnd_state;
1319 }
1320 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s)
1321 {
1322         irp->lnd_state = s;
1323 }
1324 void set_irp_loop_nesting_depth_state_inconsistent(void)
1325 {
1326         if (irp->lnd_state == loop_nesting_depth_consistent)
1327                 irp->lnd_state = loop_nesting_depth_inconsistent;
1328 }