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

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