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
  41 #include "array.h"
  42 #include "pmap.h"
  43 #include "hashptr.h"
  44 #include "raw_bitset.h"
  45
  46 #include "irgwalk.h"
  47
  48 static ir_visited_t master_cg_visited = 0;
  49 static inline int cg_irg_visited      (ir_graph *n);
  50 static inline void mark_cg_irg_visited(ir_graph *n);
  51
  52 /** Returns the callgraph state of the program representation. */
  53 irp_callgraph_state get_irp_callgraph_state(void)
  54 {
  55         return irp->callgraph_state;
  56 }
  57
  58 /* Sets the callgraph state of the program representation. */
  59 void set_irp_callgraph_state(irp_callgraph_state s)
  60 {
  61         irp->callgraph_state = s;
  62 }
  63
  64 /* Returns the number of procedures that call the given irg. */
  65 size_t get_irg_n_callers(const ir_graph *irg)
  66 {
  67         assert(irg->callers);
  68         return irg->callers ? ARR_LEN(irg->callers) : 0;
  69 }
  70
  71 /* Returns the caller at position pos. */
  72 ir_graph *get_irg_caller(const ir_graph *irg, size_t pos)
  73 {
  74         assert(pos < get_irg_n_callers(irg));
  75         return irg->callers ? irg->callers[pos] : NULL;
  76 }
  77
  78 /* Returns non-zero if the caller at position pos is "a backedge", i.e. a recursion. */
  79 int is_irg_caller_backedge(const ir_graph *irg, size_t pos)
  80 {
  81         assert(pos < get_irg_n_callers(irg));
  82         return irg->caller_isbe != NULL ? rbitset_is_set(irg->caller_isbe, pos) : 0;
  83 }
  84
  85 /** Search the caller in the list of all callers and set its backedge property. */
  86 static void set_irg_caller_backedge(ir_graph *irg, const ir_graph *caller)
  87 {
  88         size_t i, n_callers = get_irg_n_callers(irg);
  89
  90         /* allocate a new array on demand */
  91         if (irg->caller_isbe == NULL)
  92                 irg->caller_isbe = rbitset_malloc(n_callers);
  93         for (i = 0; i < n_callers; ++i) {
  94                 if (get_irg_caller(irg, i) == caller) {
  95                         rbitset_set(irg->caller_isbe, i);
  96                         break;
  97                 }
  98         }
  99 }
 100
 101 /* Returns non-zero if the irg has a backedge caller. */
 102 int has_irg_caller_backedge(const ir_graph *irg)
 103 {
 104         size_t i, n_callers = get_irg_n_callers(irg);
 105
 106         if (irg->caller_isbe != NULL) {
 107                 for (i = 0; i < n_callers; ++i)
 108                         if (rbitset_is_set(irg->caller_isbe, i))
 109                                 return 1;
 110         }
 111         return 0;
 112 }
 113
 114 /**
 115  * Find the reversion position of a caller.
 116  * Given the position pos_caller of an caller of irg, return
 117  * irg's callee position on that caller.
 118  */
 119 static size_t reverse_pos(const ir_graph *callee, size_t pos_caller)
 120 {
 121         ir_graph *caller = get_irg_caller(callee, pos_caller);
 122         /* search the other relation for the corresponding edge. */
 123         size_t i, n_callees = get_irg_n_callees(caller);
 124         for (i = 0; i < n_callees; ++i) {
 125                 if (get_irg_callee(caller, i) == callee) {
 126                         return i;
 127                 }
 128         }
 129
 130         assert(!"reverse_pos() did not find position");
 131
 132         return 0;
 133 }
 134
 135 /* Returns the maximal loop depth of call nodes that call along this edge. */
 136 size_t get_irg_caller_loop_depth(const ir_graph *irg, size_t pos)
 137 {
 138         ir_graph *caller     = get_irg_caller(irg, pos);
 139         size_t    pos_callee = reverse_pos(irg, pos);
 140
 141         return get_irg_callee_loop_depth(caller, pos_callee);
 142 }
 143
 144
 145 /* Returns the number of procedures that are called by the given irg. */
 146 size_t get_irg_n_callees(const ir_graph *irg)
 147 {
 148         assert(irg->callees);
 149         return irg->callees ? ARR_LEN(irg->callees) : 0;
 150 }
 151
 152 /* Returns the callee at position pos. */
 153 ir_graph *get_irg_callee(const ir_graph *irg, size_t pos)
 154 {
 155         assert(pos < get_irg_n_callees(irg));
 156         return irg->callees ? irg->callees[pos]->irg : NULL;
 157 }
 158
 159 /* Returns non-zero if the callee at position pos is "a backedge", i.e. a recursion. */
 160 int is_irg_callee_backedge(const ir_graph *irg, size_t pos)
 161 {
 162         assert(pos < get_irg_n_callees(irg));
 163         return irg->callee_isbe != NULL ? rbitset_is_set(irg->callee_isbe, pos) : 0;
 164 }
 165
 166 /* Returns non-zero if the irg has a backedge callee. */
 167 int has_irg_callee_backedge(const ir_graph *irg)
 168 {
 169         size_t i, n_callees = get_irg_n_callees(irg);
 170
 171         if (irg->callee_isbe != NULL) {
 172                 for (i = 0; i < n_callees; ++i)
 173                         if (rbitset_is_set(irg->callee_isbe, i))
 174                                 return 1;
 175         }
 176         return 0;
 177 }
 178
 179 /**
 180  * Mark the callee at position pos as a backedge.
 181  */
 182 static void set_irg_callee_backedge(ir_graph *irg, size_t pos)
 183 {
 184         size_t n = get_irg_n_callees(irg);
 185
 186         /* allocate a new array on demand */
 187         if (irg->callee_isbe == NULL)
 188                 irg->callee_isbe = rbitset_malloc(n);
 189         assert(pos < n);
 190         rbitset_set(irg->callee_isbe, pos);
 191 }
 192
 193 /* Returns the maximal loop depth of call nodes that call along this edge. */
 194 size_t get_irg_callee_loop_depth(const ir_graph *irg, size_t pos)
 195 {
 196         assert(pos < get_irg_n_callees(irg));
 197         return irg->callees ? irg->callees[pos]->max_depth : 0;
 198 }
 199
 200
 201 /* --------------------- Compute the callgraph ------------------------ */
 202
 203 /**
 204  * Pre-Walker called by compute_callgraph(), analyses all Call nodes.
 205  */
 206 static void ana_Call(ir_node *n, void *env)
 207 {
 208         size_t i, n_callees;
 209         ir_graph *irg;
 210         (void) env;
 211
 212         if (! is_Call(n)) return;
 213
 214         irg = get_irn_irg(n);
 215         n_callees = get_Call_n_callees(n);
 216         for (i = 0; i < n_callees; ++i) {
 217                 ir_entity *callee_e = get_Call_callee(n, i);
 218                 ir_graph *callee = get_entity_irg(callee_e);
 219
 220                 if (callee) {
 221                         cg_callee_entry buf;
 222                         cg_callee_entry *found;
 223                         unsigned        depth;
 224
 225                         buf.irg = callee;
 226
 227                         pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
 228                         found = (cg_callee_entry*) pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
 229                         if (found) {  /* add Call node to list, compute new nesting. */
 230                                 ir_node **arr = found->call_list;
 231                                 ARR_APP1(ir_node *, arr, n);
 232                                 found->call_list = arr;
 233                         } else { /* New node, add Call node and init nesting. */
 234                                 found = OALLOC(irg->obst, cg_callee_entry);
 235                                 found->irg = callee;
 236                                 found->call_list = NEW_ARR_F(ir_node *, 1);
 237                                 found->call_list[0] = n;
 238                                 found->max_depth = 0;
 239                                 pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
 240                         }
 241                         depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
 242                         found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
 243                 }
 244         }
 245 }
 246
 247 /** compare two ir graphs in a cg_callee_entry */
 248 static int cg_callee_entry_cmp(const void *elt, const void *key)
 249 {
 250         const cg_callee_entry *e1 = (const cg_callee_entry*) elt;
 251         const cg_callee_entry *e2 = (const cg_callee_entry*) key;
 252         return e1->irg != e2->irg;
 253 }
 254
 255 /** compare two ir graphs for pointer identity */
 256 static int graph_cmp(const void *elt, const void *key)
 257 {
 258         const ir_graph *e1 = (const ir_graph*) elt;
 259         const ir_graph *e2 = (const ir_graph*) key;
 260         return e1 != e2;
 261 }
 262
 263
 264 /* Construct and destruct the callgraph. */
 265 void compute_callgraph(void)
 266 {
 267         size_t i, n_irgs;
 268
 269         /* initialize */
 270         free_callgraph();
 271
 272         n_irgs = get_irp_n_irgs();
 273         for (i = 0; i < n_irgs; ++i) {
 274                 ir_graph *irg = get_irp_irg(i);
 275                 assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
 276                 irg->callees = (cg_callee_entry **)new_pset(cg_callee_entry_cmp, 8);
 277                 irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
 278                 //construct_cf_backedges(irg);
 279         }
 280
 281         /* Compute the call graph */
 282         for (i = 0; i < n_irgs; ++i) {
 283                 ir_graph *irg = get_irp_irg(i);
 284                 construct_cf_backedges(irg);   // We also find the maximal loop depth of a call.
 285                 irg_walk_graph(irg, ana_Call, NULL, NULL);
 286         }
 287
 288         /* Change the sets to arrays. */
 289         for (i = 0; i < n_irgs; ++i) {
 290                 size_t j, count;
 291                 cg_callee_entry *callee;
 292                 ir_graph *c, *irg = get_irp_irg(i);
 293                 pset *callee_set, *caller_set;
 294
 295                 callee_set = (pset *)irg->callees;
 296                 count = pset_count(callee_set);
 297                 irg->callees = NEW_ARR_F(cg_callee_entry *, count);
 298                 irg->callee_isbe = NULL;
 299                 callee = (cg_callee_entry*) pset_first(callee_set);
 300                 for (j = 0; j < count; ++j) {
 301                         irg->callees[j] = callee;
 302                         callee = (cg_callee_entry*) pset_next(callee_set);
 303                 }
 304                 del_pset(callee_set);
 305                 assert(callee == NULL);
 306
 307                 caller_set = (pset *)irg->callers;
 308                 count = pset_count(caller_set);
 309                 irg->callers = NEW_ARR_F(ir_graph *, count);
 310                 irg->caller_isbe =  NULL;
 311                 c = (ir_graph*) pset_first(caller_set);
 312                 for (j = 0; j < count; ++j) {
 313                         irg->callers[j] = c;
 314                         c = (ir_graph*) pset_next(caller_set);
 315                 }
 316                 del_pset(caller_set);
 317                 assert(c == NULL);
 318         }
 319         set_irp_callgraph_state(irp_callgraph_consistent);
 320 }
 321
 322 /* Destruct the callgraph. */
 323 void free_callgraph(void)
 324 {
 325         size_t i, n_irgs = get_irp_n_irgs();
 326         for (i = 0; i < n_irgs; ++i) {
 327                 ir_graph *irg = get_irp_irg(i);
 328                 if (irg->callees) DEL_ARR_F(irg->callees);
 329                 if (irg->callers) DEL_ARR_F(irg->callers);
 330                 if (irg->callee_isbe) free(irg->callee_isbe);
 331                 if (irg->caller_isbe) free(irg->caller_isbe);
 332                 irg->callees = NULL;
 333                 irg->callers = NULL;
 334                 irg->callee_isbe = NULL;
 335                 irg->caller_isbe = NULL;
 336         }
 337         set_irp_callgraph_state(irp_callgraph_none);
 338 }
 339
 340 /* ----------------------------------------------------------------------------------- */
 341 /* A walker for the callgraph                                                          */
 342 /* ----------------------------------------------------------------------------------- */
 343
 344
 345 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env)
 346 {
 347         size_t i, n_callees;
 348
 349         if (cg_irg_visited(irg))
 350                 return;
 351         mark_cg_irg_visited(irg);
 352
 353         if (pre)
 354                 pre(irg, env);
 355
 356         n_callees = get_irg_n_callees(irg);
 357         for (i = 0; i < n_callees; i++) {
 358                 ir_graph *m = get_irg_callee(irg, i);
 359                 do_walk(m, pre, post, env);
 360         }
 361
 362         if (post)
 363                 post(irg, env);
 364 }
 365
 366 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env)
 367 {
 368         size_t i, n_irgs = get_irp_n_irgs();
 369         ++master_cg_visited;
 370
 371         /* roots are methods which have no callers in the current program */
 372         for (i = 0; i < n_irgs; ++i) {
 373                 ir_graph *irg = get_irp_irg(i);
 374
 375                 if (get_irg_n_callers(irg) == 0)
 376                         do_walk(irg, pre, post, env);
 377         }
 378
 379         /* in case of unreachable call loops we haven't visited some irgs yet */
 380         for (i = 0; i < n_irgs; i++) {
 381                 ir_graph *irg = get_irp_irg(i);
 382                 do_walk(irg, pre, post, env);
 383         }
 384 }
 385
 386 /* ----------------------------------------------------------------------------------- */
 387 /* loop construction algorithm                                                         */
 388 /* ----------------------------------------------------------------------------------- */
 389
 390 static ir_graph *outermost_ir_graph;   /**< The outermost graph the scc is computed
 391                                             for */
 392 static ir_loop *current_loop;      /**< Current cfloop construction is working
 393                                         on. */
 394 static size_t loop_node_cnt = 0;   /**< Counts the number of allocated cfloop nodes.
 395                                         Each cfloop node gets a unique number.
 396                                         What for? ev. remove. @@@ */
 397 static size_t current_dfn = 1;     /**< Counter to generate depth first numbering
 398                                         of visited nodes.  */
 399
 400 /*-----------------*/
 401 /* Node attributes */
 402 /*-----------------*/
 403
 404 typedef struct scc_info {
 405         size_t dfn;            /**< Depth first search number. */
 406         size_t uplink;         /**< dfn number of ancestor. */
 407         ir_visited_t visited;  /**< visited counter */
 408         int in_stack;          /**< Marks whether node is on the stack. */
 409 } scc_info;
 410
 411 /**
 412  * allocates a new scc_info on the obstack
 413  */
 414 static inline scc_info *new_scc_info(struct obstack *obst)
 415 {
 416         return OALLOCZ(obst, scc_info);
 417 }
 418
 419 /**
 420  * Returns non-zero if a graph was already visited.
 421  */
 422 static inline int cg_irg_visited(ir_graph *irg)
 423 {
 424         return irg->self_visited >= master_cg_visited;
 425 }
 426
 427 /**
 428  * Marks a graph as visited.
 429  */
 430 static inline void mark_cg_irg_visited(ir_graph *irg)
 431 {
 432         irg->self_visited = master_cg_visited;
 433 }
 434
 435 /**
 436  * Set a graphs visited flag to i.
 437  */
 438 static inline void set_cg_irg_visited(ir_graph *irg, ir_visited_t i)
 439 {
 440         irg->self_visited = i;
 441 }
 442
 443 /**
 444  * Returns the visited flag of a graph.
 445  */
 446 static inline ir_visited_t get_cg_irg_visited(const ir_graph *irg)
 447 {
 448         return irg->self_visited;
 449 }
 450
 451 static inline void mark_irg_in_stack(ir_graph *irg)
 452 {
 453         scc_info *info = (scc_info*) get_irg_link(irg);
 454         assert(info && "missing call to init_scc()");
 455         info->in_stack = 1;
 456 }
 457
 458 static inline void mark_irg_not_in_stack(ir_graph *irg)
 459 {
 460         scc_info *info = (scc_info*) get_irg_link(irg);
 461         assert(info && "missing call to init_scc()");
 462         info->in_stack = 0;
 463 }
 464
 465 static inline int irg_is_in_stack(const ir_graph *irg)
 466 {
 467         scc_info *info = (scc_info*) get_irg_link(irg);
 468         assert(info && "missing call to init_scc()");
 469         return info->in_stack;
 470 }
 471
 472 static inline void set_irg_uplink(ir_graph *irg, size_t uplink)
 473 {
 474         scc_info *info = (scc_info*) get_irg_link(irg);
 475         assert(info && "missing call to init_scc()");
 476         info->uplink = uplink;
 477 }
 478
 479 static inline size_t get_irg_uplink(const ir_graph *irg)
 480 {
 481         const scc_info *info = (scc_info*) get_irg_link(irg);
 482         assert(info && "missing call to init_scc()");
 483         return info->uplink;
 484 }
 485
 486 static inline void set_irg_dfn(ir_graph *irg, size_t dfn)
 487 {
 488         scc_info *info = (scc_info*) get_irg_link(irg);
 489         assert(info && "missing call to init_scc()");
 490         info->dfn = dfn;
 491 }
 492
 493 static inline size_t get_irg_dfn(const ir_graph *irg)
 494 {
 495         const scc_info *info = (scc_info*) get_irg_link(irg);
 496         assert(info && "missing call to init_scc()");
 497         return info->dfn;
 498 }
 499
 500 /**********************************************************************/
 501 /* A stack.                                                          **/
 502 /**********************************************************************/
 503
 504 static ir_graph **stack = NULL;
 505 static size_t tos = 0;                /**< top of stack */
 506
 507 /**
 508  * Initialize the irg stack.
 509  */
 510 static inline void init_stack(void)
 511 {
 512         if (stack) {
 513                 ARR_RESIZE(ir_graph *, stack, 1000);
 514         } else {
 515                 stack = NEW_ARR_F(ir_graph *, 1000);
 516         }
 517         tos = 0;
 518 }
 519
 520 /**
 521  * push a graph on the irg stack
 522  * @param n the graph to be pushed
 523  */
 524 static inline void push(ir_graph *irg)
 525 {
 526         if (tos == ARR_LEN(stack)) {
 527                 size_t nlen = ARR_LEN(stack) * 2;
 528                 ARR_RESIZE(ir_graph*, stack, nlen);
 529         }
 530         stack [tos++] = irg;
 531         mark_irg_in_stack(irg);
 532 }
 533
 534 /**
 535  * return the topmost graph on the stack and pop it
 536  */
 537 static inline ir_graph *pop(void)
 538 {
 539         ir_graph *irg;
 540
 541         assert(tos > 0);
 542         irg = stack[--tos];
 543         mark_irg_not_in_stack(irg);
 544         return irg;
 545 }
 546
 547 /**
 548  * The nodes up to irg belong to the current loop.
 549  * Removes them from the stack and adds them to the current loop.
 550  */
 551 static inline void pop_scc_to_loop(ir_graph *irg)
 552 {
 553         ir_graph *m;
 554
 555         do {
 556                 m = pop();
 557                 ++loop_node_cnt;
 558                 set_irg_dfn(m, loop_node_cnt);
 559                 add_loop_irg(current_loop, m);
 560                 m->l = current_loop;
 561                 //m->callgraph_loop_depth = current_loop->depth;
 562         } while (m != irg);
 563 }
 564
 565 /* GL ??? my last son is my grandson???  Removes cfloops with no
 566    ir_nodes in them.  Such loops have only another loop as son. (Why
 567    can't they have two loops as sons? Does it never get that far? ) */
 568 static void close_loop(ir_loop *l)
 569 {
 570         size_t last = get_loop_n_elements(l) - 1;
 571         loop_element lelement = get_loop_element(l, last);
 572         ir_loop *last_son = lelement.son;
 573
 574         if (get_kind(last_son) == k_ir_loop &&
 575             get_loop_n_elements(last_son) == 1) {
 576                 ir_loop *gson;
 577
 578                 lelement = get_loop_element(last_son, 0);
 579                 gson = lelement.son;
 580                 if (get_kind(gson) == k_ir_loop) {
 581                         loop_element new_last_son;
 582
 583                         gson->outer_loop = l;
 584                         new_last_son.son = gson;
 585                         l->children[last] = new_last_son;
 586                 }
 587         }
 588         current_loop = l;
 589 }
 590
 591 /**
 592  * Removes and unmarks all nodes up to n from the stack.
 593  * The nodes must be visited once more to assign them to a scc.
 594  */
 595 static inline void pop_scc_unmark_visit(ir_graph *n)
 596 {
 597         ir_graph *m = NULL;
 598
 599         while (m != n) {
 600                 m = pop();
 601                 set_cg_irg_visited(m, 0);
 602         }
 603 }
 604
 605 /**********************************************************************/
 606 /* The loop data structure.                                          **/
 607 /**********************************************************************/
 608
 609 /**
 610  * Allocates a new loop as son of current_loop.  Sets current_loop
 611  * to the new loop and returns the father.
 612  */
 613 static ir_loop *new_loop(void)
 614 {
 615         ir_loop *father = current_loop;
 616         ir_loop *son    = alloc_loop(father, outermost_ir_graph->obst);
 617
 618         current_loop = son;
 619         return father;
 620 }
 621
 622
 623 /**********************************************************************/
 624 /* Constructing and destructing the loop/backedge information.       **/
 625 /**********************************************************************/
 626
 627 /* Initialization steps. **********************************************/
 628
 629 static void init_scc(struct obstack *obst)
 630 {
 631         size_t i, n_irgs;
 632
 633         current_dfn   = 1;
 634         loop_node_cnt = 0;
 635         init_stack();
 636
 637         n_irgs = get_irp_n_irgs();
 638         for (i = 0; i < n_irgs; ++i) {
 639                 ir_graph *irg = get_irp_irg(i);
 640                 set_irg_link(irg, new_scc_info(obst));
 641                 irg->callgraph_recursion_depth = 0;
 642                 irg->callgraph_loop_depth      = 0;
 643         }
 644 }
 645
 646 /** Returns non-zero if n is a loop header, i.e., it is a Block node
 647  *  and has predecessors within the cfloop and out of the cfloop.
 648  *
 649  *  @param root: only needed for assertion.
 650  */
 651 static int is_head(const ir_graph *n, const ir_graph *root)
 652 {
 653         size_t i, n_callees;
 654         int some_outof_loop = 0, some_in_loop = 0;
 655
 656         n_callees = get_irg_n_callees(n);
 657         for (i = 0; i < n_callees; ++i) {
 658                 const ir_graph *pred = get_irg_callee(n, i);
 659                 if (is_irg_callee_backedge(n, i)) continue;
 660                 if (!irg_is_in_stack(pred)) {
 661                         some_outof_loop = 1;
 662                 } else {
 663                         if (get_irg_uplink(pred) < get_irg_uplink(root))  {
 664                                 assert(get_irg_uplink(pred) >= get_irg_uplink(root));
 665                         }
 666                         some_in_loop = 1;
 667                 }
 668         }
 669
 670         return some_outof_loop && some_in_loop;
 671 }
 672
 673 /**
 674  * Returns non-zero if n is possible loop head of an endless loop.
 675  * I.e., it is a Block or Phi node and has only predecessors
 676  * within the loop.
 677  * @arg root: only needed for assertion.
 678  */
 679 static int is_endless_head(const ir_graph *n, const ir_graph *root)
 680 {
 681         size_t i, n_calless;
 682         int some_outof_loop = 0, some_in_loop = 0;
 683
 684         n_calless = get_irg_n_callees(n);
 685         for (i = 0; i < n_calless; ++i) {
 686                 const ir_graph *pred = get_irg_callee(n, i);
 687                 assert(pred);
 688                 if (is_irg_callee_backedge(n, i))
 689                         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         return !some_outof_loop && some_in_loop;
 700 }
 701
 702 /**
 703  * Finds index of the predecessor with the smallest dfn number
 704  * greater-equal than limit.
 705  */
 706 static bool smallest_dfn_pred(const ir_graph *n, size_t limit, size_t *result)
 707 {
 708         size_t index = 0, min = 0;
 709         bool found = false;
 710
 711         size_t i, n_callees = get_irg_n_callees(n);
 712         for (i = 0; i < n_callees; ++i) {
 713                 const ir_graph *pred = get_irg_callee(n, i);
 714                 if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred))
 715                         continue;
 716                 if (get_irg_dfn(pred) >= limit && (!found || get_irg_dfn(pred) < min)) {
 717                         index = i;
 718                         min = get_irg_dfn(pred);
 719                         found = true;
 720                 }
 721         }
 722
 723         *result = index;
 724         return found;
 725 }
 726
 727 /** Finds index of the predecessor with the largest dfn number. */
 728 static bool largest_dfn_pred(const ir_graph *n, size_t *result)
 729 {
 730         size_t index = 0, max = 0;
 731         bool found = false;
 732
 733         size_t i, n_callees = get_irg_n_callees(n);
 734         for (i = 0; i < n_callees; ++i) {
 735                 const ir_graph *pred = get_irg_callee(n, i);
 736                 if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred))
 737                         continue;
 738                 /* Note: dfn is always > 0 */
 739                 if (get_irg_dfn(pred) > max) {
 740                         index = i;
 741                         max = get_irg_dfn(pred);
 742                         found = true;
 743                 }
 744         }
 745
 746         *result = index;
 747         return found;
 748 }
 749
 750 static ir_graph *find_tail(const ir_graph *n)
 751 {
 752         bool found = false;
 753         ir_graph *m;
 754         size_t i, res_index;
 755
 756         /*
 757         if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
 758         */
 759         m = stack[tos - 1];  /* tos = top of stack */
 760         if (is_head(m, n)) {
 761                 found = smallest_dfn_pred(m, 0, &res_index);
 762                 if (!found &&  /* no smallest dfn pred found. */
 763                         n == m)
 764                         return NULL;
 765         } else {
 766                 if (m == n) return NULL;    // Is this to catch Phi - self loops?
 767                 for (i = tos - 1; i > 0;) {
 768                         m = stack[--i];
 769
 770                         if (is_head(m, n)) {
 771                                 found = smallest_dfn_pred(m, get_irg_dfn(m) + 1, &res_index);
 772                                 if (! found)  /* no smallest dfn pred found. */
 773                                         found = largest_dfn_pred(m, &res_index);
 774
 775                                 break;
 776                         }
 777
 778                         /* We should not walk past our selves on the stack:  The upcoming nodes
 779                            are not in this loop. We assume a loop not reachable from Start. */
 780                         if (m == n) {
 781                                 found = false;
 782                                 break;
 783                         }
 784
 785                 }
 786
 787                 if (! found) {
 788                         /* A dead loop not reachable from Start. */
 789                         for (i = tos-1; i > 0;) {
 790                                 m = stack[--i];
 791                                 if (is_endless_head(m, n)) {
 792                                         found = smallest_dfn_pred(m, get_irg_dfn(m) + 1, &res_index);
 793                                         if (!found)  /* no smallest dfn pred found. */
 794                                                 found = largest_dfn_pred(m, &res_index);
 795                                         break;
 796                                 }
 797                                 if (m == n) { break; }  /* It's not an unreachable loop, either. */
 798                         }
 799                         //assert(0 && "no head found on stack");
 800                 }
 801
 802         }
 803         assert(found);
 804
 805         set_irg_callee_backedge(m, res_index);
 806         return get_irg_callee(m, res_index);
 807 }
 808
 809 /*-----------------------------------------------------------*
 810  *                   The core algorithm.                     *
 811  *-----------------------------------------------------------*/
 812
 813
 814 static void cgscc(ir_graph *n)
 815 {
 816         size_t i, n_callees;
 817
 818         if (cg_irg_visited(n)) return;
 819         mark_cg_irg_visited(n);
 820
 821         /* Initialize the node */
 822         set_irg_dfn(n, current_dfn);      /* Depth first number for this node */
 823         set_irg_uplink(n, current_dfn);   /* ... is default uplink. */
 824         ++current_dfn;
 825         push(n);
 826
 827         n_callees = get_irg_n_callees(n);
 828         for (i = 0; i < n_callees; ++i) {
 829                 ir_graph *m;
 830                 if (is_irg_callee_backedge(n, i)) continue;
 831                 m = get_irg_callee(n, i);
 832
 833                 /** This marks the backedge, but does it guarantee a correct loop tree? */
 834                 //if (m == n) { set_irg_callee_backedge(n, i); continue; }
 835
 836                 cgscc(m);
 837                 if (irg_is_in_stack(m)) {
 838                         /* Uplink of m is smaller if n->m is a backedge.
 839                            Propagate the uplink to mark the cfloop. */
 840                         if (get_irg_uplink(m) < get_irg_uplink(n))
 841                                 set_irg_uplink(n, get_irg_uplink(m));
 842                 }
 843         }
 844
 845         if (get_irg_dfn(n) == get_irg_uplink(n)) {
 846                 /* This condition holds for
 847                    1) the node with the incoming backedge.
 848                    That is: We found a cfloop!
 849                    2) Straight line code, because no uplink has been propagated, so the
 850                    uplink still is the same as the dfn.
 851
 852                    But n might not be a proper cfloop head for the analysis. Proper cfloop
 853                    heads are Block and Phi nodes. find_tail searches the stack for
 854                    Block's and Phi's and takes those nodes as cfloop heads for the current
 855                    cfloop instead and marks the incoming edge as backedge. */
 856
 857                 ir_graph *tail = find_tail(n);
 858                 if (tail) {
 859                         /* We have a cfloop, that is no straight line code,
 860                            because we found a cfloop head!
 861                            Next actions: Open a new cfloop on the cfloop tree and
 862                            try to find inner cfloops */
 863
 864
 865                         ir_loop *l = new_loop();
 866
 867                         /* Remove the cfloop from the stack ... */
 868                         pop_scc_unmark_visit(n);
 869
 870                         /* The current backedge has been marked, that is temporarily eliminated,
 871                            by find tail. Start the scc algorithm
 872                            anew on the subgraph thats left (the current cfloop without the backedge)
 873                            in order to find more inner cfloops. */
 874
 875                         cgscc(tail);
 876
 877                         assert(cg_irg_visited(n));
 878                         close_loop(l);
 879                 } else {
 880                         pop_scc_to_loop(n);
 881                 }
 882         }
 883 }
 884
 885
 886 /**
 887  * reset the backedge information for all callers in all irgs
 888  */
 889 static void reset_isbe(void)
 890 {
 891         size_t i, n_irgs = get_irp_n_irgs();
 892
 893         for (i = 0; i < n_irgs; ++i) {
 894                 ir_graph *irg = get_irp_irg(i);
 895
 896                 if (irg->caller_isbe)
 897                         xfree(irg->caller_isbe);
 898                 irg->caller_isbe = NULL;
 899
 900                 if (irg->callee_isbe)
 901                         xfree(irg->callee_isbe);
 902                 irg->callee_isbe = NULL;
 903         }
 904 }
 905
 906 /* ----------------------------------------------------------------------------------- */
 907 /* The recursion stuff driver.                                                         */
 908 /* ----------------------------------------------------------------------------------- */
 909
 910 /* Compute the backedges that represent recursions. */
 911 void find_callgraph_recursions(void)
 912 {
 913         size_t i, n_irgs;
 914         struct obstack temp;
 915
 916         reset_isbe();
 917
 918         /* -- compute the looptree. -- */
 919
 920         /* The outermost graph.  We start here.  Then we start at all
 921         functions in irg list that are never called, then at the remaining
 922         unvisited ones. The third step is needed for functions that are not
 923         reachable from the outermost graph, but call themselves in a cycle. */
 924         assert(get_irp_main_irg());
 925         outermost_ir_graph = get_irp_main_irg();
 926         obstack_init(&temp);
 927         init_scc(&temp);
 928
 929         current_loop = NULL;
 930         new_loop();  /* sets current_loop */
 931
 932         ++master_cg_visited;
 933         cgscc(outermost_ir_graph);
 934         n_irgs = get_irp_n_irgs();
 935         for (i = 0; i < n_irgs; ++i) {
 936                 ir_graph *irg = get_irp_irg(i);
 937                 if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
 938                         cgscc(irg);
 939         }
 940         for (i = 0; i < n_irgs; ++i) {
 941                 ir_graph *irg = get_irp_irg(i);
 942                 if (!cg_irg_visited(irg))
 943                         cgscc(irg);
 944         }
 945         obstack_free(&temp, NULL);
 946
 947         irp->outermost_cg_loop = current_loop;
 948         mature_loops(current_loop, outermost_ir_graph->obst);
 949
 950         /* -- Reverse the backedge information. -- */
 951         for (i = 0; i < n_irgs; ++i) {
 952                 ir_graph *irg = get_irp_irg(i);
 953                 size_t j, n_callees = get_irg_n_callees(irg);
 954                 for (j = 0; j < n_callees; ++j) {
 955                         if (is_irg_callee_backedge(irg, j))
 956                                 set_irg_caller_backedge(get_irg_callee(irg, j), irg);
 957                 }
 958         }
 959
 960         irp->callgraph_state = irp_callgraph_and_calltree_consistent;
 961 }
 962
 963 /* Returns the maximal loop depth of all paths from an external visible method to
 964    this irg. */
 965 size_t get_irg_loop_depth(const ir_graph *irg)
 966 {
 967         assert(irp->callgraph_state == irp_callgraph_consistent ||
 968                 irp->callgraph_state == irp_callgraph_and_calltree_consistent);
 969         return irg->callgraph_loop_depth;
 970 }
 971
 972 /* Returns the maximal recursion depth of all paths from an external visible method to
 973    this irg. */
 974 size_t get_irg_recursion_depth(const ir_graph *irg)
 975 {
 976         assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
 977         return irg->callgraph_recursion_depth;
 978 }
 979
 980 /* Computes the interprocedural loop nesting information. */
 981 void analyse_loop_nesting_depth(void)
 982 {
 983         /* establish preconditions. */
 984         if (get_irp_callee_info_state() != irg_callee_info_consistent) {
 985                 ir_entity **free_methods = NULL;
 986
 987                 cgana(&free_methods);
 988                 xfree(free_methods);
 989         }
 990
 991         if (irp_callgraph_consistent != get_irp_callgraph_state()) {
 992                 compute_callgraph();
 993         }
 994
 995         find_callgraph_recursions();
 996
 997         set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
 998 }
 999
1000 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void)
1001 {
1002         return irp->lnd_state;
1003 }
1004 void set_irp_loop_nesting_depth_state(loop_nesting_depth_state s)
1005 {
1006         irp->lnd_state = s;
1007 }
1008 void set_irp_loop_nesting_depth_state_inconsistent(void)
1009 {
1010         if (irp->lnd_state == loop_nesting_depth_consistent)
1011                 irp->lnd_state = loop_nesting_depth_inconsistent;
1012 }