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