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