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

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ana/callgraph.c
   4  * Purpose:     Representation and computation of the callgraph.
   5  * Author:      Goetz Lindenmaier
   6  * Modified by:
   7  * Created:     21.7.2004
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 2004 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12 #ifdef HAVE_CONFIG_H
  13 #include "config.h"
  14 #endif
  15
  16 #ifdef HAVE_STRING_H
  17 #include <string.h>
  18 #endif
  19
  20 #include <stdlib.h>
  21
  22 #include "callgraph.h"
  23
  24 #include "irloop_t.h"
  25 #include "irprog_t.h"
  26 #include "irgraph_t.h"
  27 #include "irnode_t.h"
  28
  29 #include "cgana.h"
  30
  31 #include "array.h"
  32 #include "pmap.h"
  33
  34 #include "irgwalk.h"
  35
  36 /* For callees, we want to remember the Call nodes, too. */
  37 struct ana_entry {
  38   ir_graph *irg;
  39   ir_node  *call_list;
  40   int       max_depth;
  41 };
  42
  43 typedef struct ana_entry ana_entry;
  44
  45 static int master_cg_visited = 0;
  46 static INLINE int  cg_irg_visited     (ir_graph *n);
  47 static INLINE void mark_cg_irg_visited(ir_graph *n);
  48 static INLINE void set_cg_irg_visited (ir_graph *n, int i);
  49
  50 irp_callgraph_state get_irp_callgraph_state(void) {
  51   return irp->callgraph_state;
  52 }
  53 void                set_irp_callgraph_state(irp_callgraph_state s) {
  54   irp->callgraph_state = s;
  55 }
  56
  57 /* The functions that call irg. */
  58 int       get_irg_n_callers(ir_graph *irg) {
  59   if (irg->callers) return ARR_LEN(irg->callers);
  60   return -1;
  61 }
  62 ir_graph *get_irg_caller(ir_graph *irg, int pos) {
  63   assert (pos >= 0 && pos < get_irg_n_callers(irg));
  64   if (irg->callers) return irg->callers[pos];
  65   return NULL;
  66 }
  67 int       is_irg_caller_backedge(ir_graph *irg, int pos) {
  68   assert (pos >= 0 && pos < get_irg_n_callers(irg));
  69   return  irg->caller_isbe[pos];
  70 }
  71
  72 static void       set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) {
  73   int i, n_callers = get_irg_n_callers(irg);
  74   for (i = 0; i < n_callers; ++i) {
  75     if (get_irg_caller(irg, i) == caller) {
  76       irg->caller_isbe[i] = 1;
  77       break;
  78     }
  79   }
  80 }
  81
  82 int       has_irg_caller_backedge(ir_graph *irg) {
  83   int i, n_callers = get_irg_n_callers(irg);
  84   for (i = 0; i < n_callers; ++i)
  85     if (is_irg_caller_backedge(irg, i)) return 1;
  86   return 0;
  87 }
  88
  89 int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
  90   ir_graph *caller = get_irg_caller(irg, pos);
  91
  92   /* search the other relation for the corresponding edge. */
  93   int pos_callee = -1;
  94   int i, n_callees = get_irg_n_callees(caller);
  95   for (i = 0; i < n_callees; ++i) {
  96     if (get_irg_callee(caller, i) == irg) {
  97       pos_callee = i;
  98       break;
  99     }
 100   }
 101
 102   assert(pos_callee >= 0);
 103
 104   return get_irg_callee_loop_depth(caller, pos_callee);
 105 }
 106
 107
 108 /* The functions called by irg. */
 109 int       get_irg_n_callees(ir_graph *irg) {
 110   if (irg->callees) return ARR_LEN(irg->callees);
 111   return -1;
 112 }
 113 ir_graph *get_irg_callee(ir_graph *irg, int pos) {
 114   assert (pos >= 0 && pos < get_irg_n_callees(irg));
 115   if (irg->callees) return ((ana_entry *)irg->callees[pos])->irg;
 116   return NULL;
 117 }
 118 int       is_irg_callee_backedge(ir_graph *irg, int pos) {
 119   assert (pos >= 0 && pos < get_irg_n_callees(irg));
 120   return irg->callee_isbe[pos];
 121 }
 122 int       has_irg_callee_backedge(ir_graph *irg) {
 123   int i, n_callees = get_irg_n_callees(irg);
 124   for (i = 0; i < n_callees; ++i)
 125     if (is_irg_callee_backedge(irg, i)) return 1;
 126   return 0;
 127 }
 128 void       set_irg_callee_backedge(ir_graph *irg, int pos) {
 129   assert (pos >= 0 && pos < get_irg_n_callees(irg));
 130   irg->callee_isbe[pos] = 1;
 131 }
 132
 133 int get_irg_callee_loop_depth(ir_graph *irg, int pos) {
 134   assert (pos >= 0 && pos < get_irg_n_callees(irg));
 135   if (irg->callees) return ((ana_entry *)irg->callees[pos])->max_depth;
 136   return -1;
 137 }
 138
 139 /* --------------------- Compute the callgraph ------------------------ */
 140
 141 /* Hash an address */
 142 #define HASH_ADDRESS(adr)       (((unsigned)(adr)) >> 3)
 143
 144 /**
 145  * Walker called by compute_callgraph()
 146  */
 147 static void ana_Call(ir_node *n, void *env) {
 148   int i, n_callees;
 149   ir_graph *irg;
 150
 151   if (get_irn_op(n) != op_Call) return;
 152
 153   irg = get_irn_irg(n);
 154   n_callees = get_Call_n_callees(n);
 155   for (i = 0; i < n_callees; ++i) {
 156     entity *callee_e = get_Call_callee(n, i);
 157     ir_graph *callee = get_entity_irg(callee_e);
 158     if (callee) {  /* For unknown caller */
 159       ana_entry buf = { callee, NULL, 0};
 160       ana_entry *found;
 161       int depth;
 162
 163       pset_insert((pset *)callee->callers, irg, (unsigned)irg >> 3);
 164       found = pset_find((pset *)irg->callees, &buf, HASH_ADDRESS(callee));
 165       if (found) {  /* add Call node to list, compute new nesting. */
 166       } else { /* New node, add Call node and init nesting. */
 167             found = (ana_entry *) obstack_alloc (irg->obst, sizeof (ana_entry));
 168             found->irg = callee;
 169             found->call_list = NULL;
 170             found->max_depth = 0;
 171             pset_insert((pset *)irg->callees, found, HASH_ADDRESS(callee));
 172       }
 173       depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
 174       found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
 175     }
 176   }
 177 }
 178
 179 /** compare two ir graphs in a ana_entry */
 180 static int ana_entry_cmp(const void *elt, const void *key) {
 181   const ana_entry *e1 = elt;
 182   const ana_entry *e2 = key;
 183   return e1->irg != e2->irg;
 184 }
 185
 186 /** compare two ir graphs */
 187 static int graph_cmp(const void *elt, const void *key) {
 188   return elt != key;
 189 }
 190
 191
 192 /* Construct and destruct the callgraph. */
 193 void compute_callgraph(void) {
 194   int i, n_irgs = get_irp_n_irgs();
 195
 196   assert(! get_interprocedural_view());  /* Else walking will not reach the Call nodes. */
 197
 198   /* initialize */
 199   free_callgraph();
 200   for (i = 0; i < n_irgs; ++i) {
 201     ir_graph *irg = get_irp_irg(i);
 202     assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
 203     irg->callees = (ir_graph **)new_pset(ana_entry_cmp, 8);
 204     irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
 205     construct_cf_backedges(irg);
 206   }
 207
 208   /* Compute the call graph */
 209   for (i = 0; i < n_irgs; ++i) {
 210     ir_graph *irg = get_irp_irg(i);
 211     construct_cf_backedges(irg);
 212     irg_walk_graph(irg, ana_Call, NULL, NULL);
 213   }
 214
 215   /* Change the sets to arrays. */
 216   for (i = 0; i < n_irgs; ++i) {
 217     int j, count;
 218     ir_graph *c, *irg = get_irp_irg(i);
 219     pset *callee_set, *caller_set;
 220
 221     callee_set = (pset *)irg->callees;
 222     count = pset_count(callee_set);
 223     irg->callees = NEW_ARR_F(ir_graph *, count);
 224     irg->callee_isbe = calloc(count, sizeof(int));
 225     c = pset_first(callee_set);
 226     for (j = 0; j < count; ++j) {
 227       irg->callees[j] = c;
 228       c = pset_next(callee_set);
 229     }
 230     del_pset(callee_set);
 231     assert(c == NULL);
 232
 233     caller_set = (pset *)irg->callers;
 234     count = pset_count(caller_set);
 235     irg->callers = NEW_ARR_F(ir_graph *, count);
 236     irg->caller_isbe =  calloc(count, sizeof(int));
 237     c = pset_first(caller_set);
 238     for (j = 0; j < count; ++j) {
 239       irg->callers[j] = c;
 240       c = pset_next(caller_set);
 241     }
 242     del_pset(caller_set);
 243     assert(c == NULL);
 244   }
 245   set_irp_callgraph_state(irp_callgraph_consistent);
 246 }
 247
 248 void free_callgraph(void) {
 249   int i, n_irgs = get_irp_n_irgs();
 250   for (i = 0; i < n_irgs; ++i) {
 251     ir_graph *irg = get_irp_irg(i);
 252     if (irg->callees) DEL_ARR_F(irg->callees);
 253     if (irg->callers) DEL_ARR_F(irg->callers);
 254     if (irg->callee_isbe) free(irg->callee_isbe);
 255     if (irg->caller_isbe) free(irg->caller_isbe);
 256     irg->callees = NULL;
 257     irg->callers = NULL;
 258     irg->callee_isbe = NULL;
 259     irg->caller_isbe = NULL;
 260   }
 261   set_irp_callgraph_state(irp_callgraph_none);
 262 }
 263
 264 /* ----------------------------------------------------------------------------------- */
 265 /* A walker for the callgraph                                                          */
 266 /* ----------------------------------------------------------------------------------- */
 267
 268
 269 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
 270   int i, n_callees;
 271
 272   if (cg_irg_visited(irg)) return;
 273   mark_cg_irg_visited(irg);
 274
 275   pre(irg, env);
 276
 277   n_callees = get_irg_n_callees(irg);
 278   for (i = 0; i < n_callees; i++) {
 279     ir_graph *m = get_irg_callee(irg, i);
 280     do_walk(m, pre, post, env);
 281   }
 282
 283   post(irg, env);
 284 }
 285
 286 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
 287   int i, n_irgs = get_irp_n_irgs();
 288   master_cg_visited++;
 289
 290   do_walk(get_irp_main_irg(), pre, post, env);
 291   for (i = 0; i < n_irgs; i++) {
 292     ir_graph *irg = get_irp_irg(i);
 293     if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
 294       do_walk(irg, pre, post, env);
 295   }
 296   for (i = 0; i < n_irgs; i++) {
 297     ir_graph *irg = get_irp_irg(i);
 298     if (!cg_irg_visited(irg))
 299       do_walk(irg, pre, post, env);
 300   }
 301 }
 302
 303 /* ----------------------------------------------------------------------------------- */
 304 /* loop construction algorithm                                                         */
 305 /* ----------------------------------------------------------------------------------- */
 306
 307 static ir_graph *outermost_ir_graph;      /* The outermost graph the scc is computed
 308                       for */
 309 static ir_loop *current_loop;      /* Current cfloop construction is working
 310                       on. */
 311 static int loop_node_cnt = 0;      /* Counts the number of allocated cfloop nodes.
 312                       Each cfloop node gets a unique number.
 313                       What for? ev. remove. @@@ */
 314 static int current_dfn = 1;        /* Counter to generate depth first numbering
 315                       of visited nodes.  */
 316
 317
 318 /**********************************************************************/
 319 /* Node attributes                                                   **/
 320 /**********************************************************************/
 321
 322 typedef struct scc_info {
 323   bool in_stack;         /* Marks whether node is on the stack. */
 324   int dfn;               /* Depth first search number. */
 325   int uplink;            /* dfn number of ancestor. */
 326   int visited;
 327 } scc_info;
 328
 329 static INLINE scc_info* new_scc_info(void) {
 330   scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
 331   memset (info, 0, sizeof (scc_info));
 332   return info;
 333 }
 334
 335 static INLINE int
 336 cg_irg_visited(ir_graph *n) {
 337   return (((scc_info *)n->link)->visited >= master_cg_visited);
 338 }
 339
 340 static INLINE void
 341 mark_cg_irg_visited(ir_graph *n) {
 342   ((scc_info *)n->link)->visited = master_cg_visited;
 343 }
 344
 345 static INLINE void
 346 set_cg_irg_visited(ir_graph *n, int i) {
 347   ((scc_info *)n->link)->visited = i;
 348 }
 349
 350 static INLINE int
 351 get_cg_irg_visited(ir_graph *n) {
 352   return ((scc_info *)n->link)->visited;
 353 }
 354
 355 static INLINE void
 356 mark_irg_in_stack (ir_graph *n) {
 357   assert(get_irg_link(n));
 358   ((scc_info *)n->link)->in_stack = true;
 359 }
 360
 361 static INLINE void
 362 mark_irg_not_in_stack (ir_graph *n) {
 363   assert(get_irg_link(n));
 364   ((scc_info *)n->link)->in_stack = false;
 365 }
 366
 367 static INLINE bool
 368 irg_is_in_stack (ir_graph *n) {
 369   assert(get_irg_link(n));
 370   return ((scc_info *)n->link)->in_stack;
 371 }
 372
 373 static INLINE void
 374 set_irg_uplink (ir_graph *n, int uplink) {
 375   assert(get_irg_link(n));
 376   ((scc_info *)n->link)->uplink = uplink;
 377 }
 378
 379 static INLINE int
 380 get_irg_uplink (ir_graph *n) {
 381   assert(get_irg_link(n));
 382   return ((scc_info *)n->link)->uplink;
 383 }
 384
 385 static INLINE void
 386 set_irg_dfn (ir_graph *n, int dfn) {
 387   assert(get_irg_link(n));
 388   ((scc_info *)n->link)->dfn = dfn;
 389 }
 390
 391 static INLINE int
 392 get_irg_dfn (ir_graph *n) {
 393   assert(get_irg_link(n));
 394   return ((scc_info *)n->link)->dfn;
 395 }
 396
 397 /**********************************************************************/
 398 /* A stack.                                                          **/
 399 /**********************************************************************/
 400
 401 static ir_graph **stack = NULL;
 402 static int tos = 0;                /* top of stack */
 403
 404 static INLINE void init_stack(void) {
 405   if (stack) {
 406     ARR_RESIZE (ir_graph *, stack, 1000);
 407   } else {
 408     stack = NEW_ARR_F (ir_graph *, 1000);
 409   }
 410   tos = 0;
 411 }
 412
 413
 414 static INLINE void
 415 push (ir_graph *n)
 416 {
 417   if (tos == ARR_LEN (stack)) {
 418     int nlen = ARR_LEN (stack) * 2;
 419     ARR_RESIZE (ir_node *, stack, nlen);
 420   }
 421   stack [tos++] = n;
 422   mark_irg_in_stack(n);
 423 }
 424
 425 static INLINE ir_graph *
 426 pop (void)
 427 {
 428   ir_graph *n = stack[--tos];
 429   mark_irg_not_in_stack(n);
 430   return n;
 431 }
 432
 433 /* The nodes up to n belong to the current loop.
 434    Removes them from the stack and adds them to the current loop. */
 435 static INLINE void
 436 pop_scc_to_loop (ir_graph *n)
 437 {
 438   ir_graph *m;
 439
 440   do {
 441     m = pop();
 442     loop_node_cnt++;
 443     set_irg_dfn(m, loop_node_cnt);
 444     add_loop_node(current_loop, (ir_node *)m);
 445     m->l = current_loop;
 446     //m->callgraph_loop_depth = current_loop->depth;
 447   } while(m != n);
 448 }
 449
 450 /* GL ??? my last son is my grandson???  Removes cfloops with no
 451    ir_nodes in them.  Such loops have only another loop as son. (Why
 452    can't they have two loops as sons? Does it never get that far? ) */
 453 static void close_loop (ir_loop *l)
 454 {
 455   int last = get_loop_n_elements(l) - 1;
 456   loop_element lelement = get_loop_element(l, last);
 457   ir_loop *last_son = lelement.son;
 458
 459   if (get_kind(last_son) == k_ir_loop &&
 460       get_loop_n_elements(last_son) == 1) {
 461     ir_loop *gson;
 462
 463     lelement = get_loop_element(last_son, 0);
 464     gson = lelement.son;
 465     if(get_kind(gson) == k_ir_loop) {
 466       loop_element new_last_son;
 467
 468       gson -> outer_loop = l;
 469       new_last_son.son = gson;
 470       l -> children[last] = new_last_son;
 471     }
 472   }
 473
 474   current_loop = l;
 475 }
 476
 477 /* Removes and unmarks all nodes up to n from the stack.
 478    The nodes must be visited once more to assign them to a scc. */
 479 static INLINE void
 480 pop_scc_unmark_visit (ir_graph *n)
 481 {
 482   ir_graph *m = NULL;
 483
 484   while (m != n) {
 485     m = pop();
 486     set_cg_irg_visited(m, 0);
 487   }
 488 }
 489
 490 /**********************************************************************/
 491 /* The loop datastructure.                                           **/
 492 /**********************************************************************/
 493
 494 /* Allocates a new loop as son of current_loop.  Sets current_loop
 495    to the new loop and returns the father. */
 496 static ir_loop *new_loop (void) {
 497   ir_loop *father, *son;
 498
 499   father = current_loop;
 500
 501   son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
 502   memset (son, 0, sizeof (ir_loop));
 503   son->kind = k_ir_loop;
 504   son->children = NEW_ARR_F (loop_element, 0);
 505   son->n_nodes = 0;
 506   son->n_sons = 0;
 507   if (father) {
 508     son->outer_loop = father;
 509     add_loop_son(father, son);
 510     son->depth = father->depth+1;
 511   } else {  /* The root loop */
 512     son->outer_loop = son;
 513     son->depth = 0;
 514   }
 515
 516 #ifdef DEBUG_libfirm
 517   son->loop_nr = get_irp_new_node_nr();
 518   son->link = NULL;
 519 #endif
 520
 521   current_loop = son;
 522   return father;
 523 }
 524
 525 /**********************************************************************/
 526 /* Constructing and destructing the loop/backedge information.       **/
 527 /**********************************************************************/
 528
 529 /* Initialization steps. **********************************************/
 530
 531 static INLINE void
 532 init_scc (void) {
 533   int i;
 534   current_dfn = 1;
 535   loop_node_cnt = 0;
 536   init_stack();
 537   for (i = 0; i < get_irp_n_irgs(); ++i) {
 538     set_irg_link(get_irp_irg(i), new_scc_info());
 539     get_irp_irg(i)->callgraph_recursion_depth = 0;
 540     get_irp_irg(i)->callgraph_loop_depth = 0;
 541   }
 542 }
 543
 544 /** Returns true if n is a loop header, i.e., it is a Block node
 545  *  and has predecessors within the cfloop and out of the cfloop.
 546  *
 547  *  @param root: only needed for assertion.
 548  */
 549 static bool
 550 is_head (ir_graph *n, ir_graph *root)
 551 {
 552   int i, arity;
 553   int some_outof_loop = 0, some_in_loop = 0;
 554
 555   arity = get_irg_n_callees(n);
 556   for (i = 0; i < arity; i++) {
 557     ir_graph *pred = get_irg_callee(n, i);
 558     if (is_irg_callee_backedge(n, i)) continue;
 559     if (!irg_is_in_stack(pred)) {
 560       some_outof_loop = 1;
 561     } else {
 562       if (get_irg_uplink(pred) < get_irg_uplink(root))  {
 563         DDMG(pred); DDMG(root);
 564         assert(get_irg_uplink(pred) >= get_irg_uplink(root));
 565       }
 566       some_in_loop = 1;
 567     }
 568   }
 569
 570   return some_outof_loop && some_in_loop;
 571 }
 572 /* Returns true if n is possible loop head of an endless loop.
 573    I.e., it is a Block, Phi or Filter node and has only predecessors
 574    within the loop.
 575    @arg root: only needed for assertion. */
 576 static bool
 577 is_endless_head (ir_graph *n, ir_graph *root)
 578 {
 579   int i, arity;
 580   int some_outof_loop = 0, some_in_loop = 0;
 581
 582   arity = get_irg_n_callees(n);
 583   for (i = 0; i < arity; i++) {
 584     ir_graph *pred = get_irg_callee(n, i);
 585     assert(pred);
 586     if (is_irg_callee_backedge(n, i)) { continue; }
 587     if (!irg_is_in_stack(pred)) {
 588         some_outof_loop = 1;
 589     } else {
 590       if(get_irg_uplink(pred) < get_irg_uplink(root)) {
 591         DDMG(pred); DDMG(root);
 592         assert(get_irg_uplink(pred) >= get_irg_uplink(root));
 593       }
 594       some_in_loop = 1;
 595     }
 596   }
 597
 598   return !some_outof_loop && some_in_loop;
 599 }
 600
 601
 602 /* Check whether there is a parallel edge in the ip control flow.
 603    Only */
 604 static bool
 605 is_ip_head (ir_graph *n, ir_graph *pred)
 606 {
 607   int is_be = 0;
 608   int iv_rem = get_interprocedural_view();
 609   set_interprocedural_view(true);
 610   {
 611     ir_node *sblock = get_irg_start_block(n);
 612     int i, arity = get_Block_n_cfgpreds(sblock);
 613
 614     //printf(" edge from "); DDMG(n);
 615     //printf(" to pred   "); DDMG(pred);
 616     //printf(" sblock    "); DDMN(sblock);
 617
 618     for (i = 0; i < arity; i++) {
 619       ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
 620       //printf("  "); DDMN(pred_cfop);
 621       if (get_irn_op(pred_cfop) == op_CallBegin) {  /* could be Unknown */
 622         ir_graph *ip_pred = get_irn_irg(pred_cfop);
 623         //printf("   "); DDMG(ip_pred);
 624         if ((ip_pred == pred) && is_backedge(sblock, i)) {
 625               //printf("   found\n");
 626               is_be = 1;
 627         }
 628       }
 629     }
 630   }
 631   set_interprocedural_view(iv_rem);
 632   return is_be;
 633 }
 634
 635 /* Returns index of the predecessor with the smallest dfn number
 636    greater-equal than limit. */
 637 static int
 638 smallest_dfn_pred (ir_graph *n, int limit)
 639 {
 640   int i, index = -2, min = -1;
 641
 642   int arity = get_irg_n_callees(n);
 643   for (i = 0; i < arity; i++) {
 644     ir_graph *pred = get_irg_callee(n, i);
 645     if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue;
 646     if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
 647       index = i;
 648       min = get_irg_dfn(pred);
 649     }
 650   }
 651
 652   return index;
 653 }
 654
 655 /* Returns index of the predecessor with the largest dfn number. */
 656 static int
 657 largest_dfn_pred (ir_graph *n)
 658 {
 659   int i, index = -2, max = -1;
 660
 661   int arity = get_irg_n_callees(n);
 662   for (i = 0; i < arity; i++) {
 663     ir_graph *pred = get_irg_callee(n, i);
 664     if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
 665     if (get_irg_dfn(pred) > max) {
 666       index = i;
 667       max = get_irg_dfn(pred);
 668     }
 669   }
 670
 671   return index;
 672 }
 673
 674 #if 0
 675 static ir_graph *
 676 find_tail (ir_graph *n) {
 677   ir_graph *m;
 678   int i, res_index = -2;
 679
 680   /*
 681     if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
 682   */
 683   m = stack[tos-1];  /* tos = top of stack */
 684   if (is_head (m, n)) {
 685     res_index = smallest_dfn_pred(m, 0);
 686     if ((res_index == -2) &&  /* no smallest dfn pred found. */
 687     (n == m))
 688       return NULL;
 689   } else {
 690     if (m == n) return NULL;    // Is this to catch Phi - self loops?
 691     for (i = tos-2; i >= 0; --i) {
 692       m = stack[i];
 693
 694       if (is_head (m, n)) {
 695         res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
 696         if (res_index == -2)  /* no smallest dfn pred found. */
 697           res_index = largest_dfn_pred (m);
 698
 699         if ((m == n) && (res_index == -2)) {
 700           i = -1;
 701         }
 702         break;
 703       }
 704
 705       /* We should not walk past our selves on the stack:  The upcoming nodes
 706          are not in this loop. We assume a loop not reachable from Start. */
 707       if (m == n) {
 708         i = -1;
 709         break;
 710       }
 711
 712     }
 713
 714     if (i < 0) {
 715       /* A dead loop not reachable from Start. */
 716       for (i = tos-2; i >= 0; --i) {
 717         m = stack[i];
 718         if (is_endless_head (m, n)) {
 719           res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
 720           if (res_index == -2)  /* no smallest dfn pred found. */
 721             res_index = largest_dfn_pred (m);
 722           break;
 723         }
 724         if (m == n) { break; }  /* It's not an unreachable loop, either. */
 725       }
 726       //assert(0 && "no head found on stack");
 727     }
 728
 729   }
 730   assert (res_index > -2);
 731
 732   set_irg_callee_backedge (m, res_index);
 733   return get_irg_callee(m, res_index);
 734 }
 735 #else
 736 static ir_graph *
 737 find_tail (ir_graph *n) {
 738   ir_graph *m;
 739   int i, res_index = -2;
 740
 741   ir_graph *res;
 742   ir_graph *in_and_out    = NULL;
 743   ir_graph *only_in       = NULL;
 744   ir_graph *ip_in_and_out = NULL;
 745   ir_graph *ip_only_in    = NULL;
 746
 747   //printf("find tail for "); DDMG(n);
 748
 749   for (i = tos-1; i >= 0; --i) {
 750     ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
 751     m = stack[i];
 752
 753     if (is_head (m, n)) {
 754       //printf(" found 1a! "); DDM;
 755       in_and_out = m;
 756       if (is_ip_head(pred, m)) {
 757         //printf(" found 1b! "); DDM;
 758         ip_in_and_out = m;
 759       }
 760     } else if (!ip_only_in && is_endless_head(m, n)) {
 761       only_in = m;
 762       //printf(" found 2a! "); DDM;
 763       if (is_ip_head(pred, m)) {
 764         //printf(" found 2b! "); DDM;
 765         ip_only_in = m;
 766       }
 767     } else if (is_ip_head(pred, m)) {
 768       //printf(" found 3! "); DDM;   This happens for self recursions in the second
 769       //assert(0);                   scc iteration (the one to flip the loop.)
 770     }
 771
 772     if (ip_in_and_out) break;    /* That's what we really want. */
 773
 774     if (m == n) break;   /* Don't walk past n on the stack! */
 775   }
 776
 777
 778   if (!in_and_out && !only_in)
 779     /* There is no loop */
 780     return NULL;
 781
 782
 783   /* Is there a head in the callgraph without a head in the
 784      ip cf graph? */
 785   assert(in_and_out || only_in);
 786
 787   m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
 788
 789   if (!m)
 790     m = (in_and_out) ? in_and_out : only_in;
 791
 792   //printf("*** head is "); DDMG(m);
 793
 794   res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
 795   if (res_index == -2)  /* no smallest dfn pred found. */
 796     res_index = largest_dfn_pred (m);
 797
 798   set_irg_callee_backedge (m, res_index);
 799   res = get_irg_callee(m, res_index);
 800   //printf("*** tail is "); DDMG(res);
 801   return res;
 802 }
 803 #endif
 804
 805
 806 /*-----------------------------------------------------------*
 807  *                   The core algorithm.                     *
 808  *-----------------------------------------------------------*/
 809
 810
 811 static void cgscc (ir_graph *n) {
 812   int i, arity;
 813
 814   if (cg_irg_visited(n)) return;
 815   mark_cg_irg_visited(n);
 816
 817   /* Initialize the node */
 818   set_irg_dfn(n, current_dfn);      /* Depth first number for this node */
 819   set_irg_uplink(n, current_dfn);   /* ... is default uplink. */
 820   current_dfn ++;
 821   push(n);
 822
 823   arity = get_irg_n_callees(n);
 824   for (i = 0; i < arity; i++) {
 825     ir_graph *m;
 826     if (is_irg_callee_backedge(n, i)) continue;
 827     m = get_irg_callee(n, i);
 828
 829     /** This marks the backedge, but does it guarantee a correct loop tree? */
 830     //if (m == n) { set_irg_callee_backedge(n, i); continue; }
 831
 832     cgscc (m);
 833     if (irg_is_in_stack(m)) {
 834       /* Uplink of m is smaller if n->m is a backedge.
 835              Propagate the uplink to mark the cfloop. */
 836       if (get_irg_uplink(m) < get_irg_uplink(n))
 837             set_irg_uplink(n, get_irg_uplink(m));
 838     }
 839   }
 840
 841   if (get_irg_dfn(n) == get_irg_uplink(n)) {
 842     /* This condition holds for
 843        1) the node with the incoming backedge.
 844        That is: We found a cfloop!
 845        2) Straight line code, because no uplink has been propagated, so the
 846        uplink still is the same as the dfn.
 847
 848        But n might not be a proper cfloop head for the analysis. Proper cfloop
 849        heads are Block and Phi nodes. find_tail searches the stack for
 850        Block's and Phi's and takes those nodes as cfloop heads for the current
 851        cfloop instead and marks the incoming edge as backedge. */
 852
 853     ir_graph *tail = find_tail(n);
 854     if (tail) {
 855       /* We have a cfloop, that is no straight line code,
 856              because we found a cfloop head!
 857              Next actions: Open a new cfloop on the cfloop tree and
 858              try to find inner cfloops */
 859
 860
 861       ir_loop *l = new_loop();
 862
 863       /* Remove the cfloop from the stack ... */
 864       pop_scc_unmark_visit (n);
 865
 866       /* The current backedge has been marked, that is temporarily eliminated,
 867              by find tail. Start the scc algorithm
 868              anew on the subgraph thats left (the current cfloop without the backedge)
 869              in order to find more inner cfloops. */
 870
 871       cgscc (tail);
 872
 873       assert (cg_irg_visited(n));
 874       close_loop(l);
 875     } else {
 876       pop_scc_to_loop(n);
 877     }
 878   }
 879 }
 880
 881
 882
 883 static void reset_isbe(void) {
 884   int i, n_irgs = get_irp_n_irgs();
 885
 886   for (i = 0; i < n_irgs; ++i) {
 887     int j, n_cs;
 888     ir_graph *irg = get_irp_irg(i);
 889
 890     n_cs = get_irg_n_callers(irg);
 891     for (j = 0; j < n_cs; ++j) {
 892       irg->caller_isbe[j] = 0;
 893     }
 894     n_cs = get_irg_n_callees(irg);
 895     for (j = 0; j < n_cs; ++j) {
 896       irg->callee_isbe[j] = 0;
 897     }
 898   }
 899 }
 900
 901
 902
 903
 904 /* ----------------------------------------------------------------------------------- */
 905 /* Another algorithm to compute recursion nesting depth                                */
 906 /* Walk the callgraph.  For each crossed edge increase the loop depth by the edge      */
 907 /* weight. Assign graphs the maximal depth.                                            */
 908 /* ----------------------------------------------------------------------------------- */
 909
 910 void compute_loop_depth (ir_graph *irg, void *env) {
 911   int current_nesting = *(int *) env;
 912   int old_nesting = irg->callgraph_loop_depth;
 913   int old_visited = get_cg_irg_visited(irg);
 914   int i, n_callees;
 915
 916   //return ;
 917
 918   if (cg_irg_visited(irg)) return;
 919
 920   mark_cg_irg_visited(irg);
 921
 922   //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
 923
 924
 925   if (old_nesting < current_nesting)
 926     irg->callgraph_loop_depth = current_nesting;
 927
 928   if (current_nesting > irp->max_callgraph_loop_depth)
 929     irp->max_callgraph_loop_depth = current_nesting;
 930
 931   if ((old_visited +1 < get_cg_irg_visited(irg)) ||   /* not yet visited */
 932       (old_nesting < current_nesting)) {        /* propagate larger nesting */
 933     /* Don't walk the graph, but a tree that is an unfolded graph. */
 934     n_callees = get_irg_n_callees(irg);
 935     for (i = 0; i < n_callees; i++) {
 936       ir_graph *m = get_irg_callee(irg, i);
 937       *(int *)env += get_irg_callee_loop_depth(irg, i);
 938       compute_loop_depth(m, env);
 939       *(int *)env -= get_irg_callee_loop_depth(irg, i);
 940     }
 941   }
 942
 943   set_cg_irg_visited(irg, master_cg_visited-1);
 944 }
 945
 946
 947 /* ----------------------------------------------------------------------------------- */
 948 /* Another algorithm to compute recursion nesting depth                                */
 949 /* Walk the callgraph.  For each crossed loop increase the nesting depth by one.       */
 950 /* Assign graphs the maximal nesting depth.   Don't increas if passing loops more than */
 951 /* once.                                                                               */
 952 /* ----------------------------------------------------------------------------------- */
 953
 954
 955 /* For callees, we want to remember the Call nodes, too. */
 956 struct ana_entry2 {
 957   ir_loop **loop_stack;
 958   int tos;
 959   int recursion_nesting;
 960 };
 961
 962 typedef struct ana_entry2 ana_entry2;
 963
 964 static void push2(ana_entry2 *e, ir_loop *g) {
 965   if (ARR_LEN(e->loop_stack) == e->tos) {
 966     ARR_APP1(ir_loop *, e->loop_stack, g);
 967   } else {
 968     e->loop_stack[e->tos] = g;
 969   }
 970   e->tos ++;
 971 }
 972
 973 static ir_loop *pop2(ana_entry2 *e) {
 974   e->tos --;
 975   return e->loop_stack[e->tos+1];
 976 }
 977
 978 static int in_stack(ana_entry2 *e, ir_loop *g) {
 979   int i;
 980   for (i = e->tos-1; i >= 0; --i) {
 981     if (e->loop_stack[i] == g) return 1;
 982   }
 983   return 0;
 984 }
 985
 986 void compute_rec_depth (ir_graph *irg, void *env) {
 987   ana_entry2 *e = (ana_entry2 *)env;
 988   ir_loop *l = irg->l;
 989   int depth, old_depth = irg->callgraph_recursion_depth;
 990   int i, n_callees;
 991   int pushed = 0;
 992
 993   if (cg_irg_visited(irg)) return;
 994   mark_cg_irg_visited(irg);
 995
 996   /* -- compute and set the new nesting value -- */
 997   if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
 998     push2(e, l);
 999     e->recursion_nesting++;
1000     pushed = 1;
1001   }
1002   depth = e->recursion_nesting;
1003
1004   if (old_depth < depth)
1005     irg->callgraph_recursion_depth = depth;
1006
1007   if (depth > irp->max_callgraph_recursion_depth)
1008     irp->max_callgraph_recursion_depth = depth;
1009
1010   /* -- spread the nesting value -- */
1011   if (depth == 0 || old_depth < depth) {
1012     /* Don't walk the graph, but a tree that is an unfolded graph. */
1013     n_callees = get_irg_n_callees(irg);
1014     for (i = 0; i < n_callees; i++) {
1015       ir_graph *m = get_irg_callee(irg, i);
1016       compute_rec_depth(m, env);
1017     }
1018   }
1019
1020   /* -- clean up -- */
1021   if (pushed) {
1022     pop2(e);
1023     e->recursion_nesting--;
1024   }
1025   set_cg_irg_visited(irg, master_cg_visited-1);
1026 }
1027
1028
1029 /* Compute the backedges that represent recursions. */
1030 void find_callgraph_recursions(void) {
1031   int i, n_irgs = get_irp_n_irgs();
1032   int current_nesting;
1033   ana_entry2 e;
1034
1035   reset_isbe();
1036
1037   /* -- Compute the looptree -- */
1038
1039   /* The outermost graph.  We start here.  Then we start at all
1040      functions in irg list that are never called, then at the remaining
1041      unvisited ones. */
1042   assert(get_irp_main_irg());
1043   outermost_ir_graph = get_irp_main_irg();
1044   init_scc();
1045
1046   current_loop = NULL;
1047   new_loop();  /* sets current_loop */
1048
1049   master_cg_visited++;
1050   cgscc(outermost_ir_graph);
1051   for (i = 0; i < n_irgs; i++) {
1052     ir_graph *irg = get_irp_irg(i);
1053     if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1054       cgscc(irg);
1055   }
1056   for (i = 0; i < n_irgs; i++) {
1057     ir_graph *irg = get_irp_irg(i);
1058     if (!cg_irg_visited(irg))
1059       cgscc(irg);
1060   }
1061   irp->outermost_cg_loop = current_loop;
1062
1063   /* -- Reverse the backedge information. -- */
1064   for (i = 0; i < n_irgs; i++) {
1065     ir_graph *irg = get_irp_irg(i);
1066     int j, n_callees = get_irg_n_callees(irg);
1067     for (j = 0; j < n_callees; ++j) {
1068       if (is_irg_callee_backedge(irg, j))
1069         set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1070     }
1071   }
1072
1073   /* -- compute the loop depth  -- */
1074   current_nesting = 0;
1075   irp->max_callgraph_loop_depth = 0;
1076   master_cg_visited += 2;
1077   //printf (" ** starting at      "); DDMG(get_irp_main_irg());
1078   compute_loop_depth(get_irp_main_irg(), &current_nesting);
1079   for (i = 0; i < n_irgs; i++) {
1080     ir_graph *irg = get_irp_irg(i);
1081     if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1082         get_irg_n_callers(irg) == 0) {
1083       compute_loop_depth(irg, &current_nesting);
1084       //printf (" ** starting at      "); DDMG(irg);
1085     }
1086   }
1087   for (i = 0; i < n_irgs; i++) {
1088     ir_graph *irg = get_irp_irg(i);
1089     if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1090       compute_loop_depth(irg, &current_nesting);
1091       //printf (" ** starting at      "); DDMG(irg);
1092     }
1093   }
1094
1095   /* -- compute the recursion depth -- */
1096   e.loop_stack = NEW_ARR_F(ir_loop *, 0);
1097   e.tos = 0;
1098   e.recursion_nesting = 0;
1099   irp->max_callgraph_recursion_depth = 0;
1100
1101   master_cg_visited += 2;
1102   compute_rec_depth(get_irp_main_irg(), &e);
1103   //printf (" ++ starting at "); DDMG(get_irp_main_irg());
1104   for (i = 0; i < n_irgs; i++) {
1105     ir_graph *irg = get_irp_irg(i);
1106     if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1107         get_irg_n_callers(irg) == 0) {
1108       compute_rec_depth(irg, &e);
1109       //printf (" ++ starting at "); DDMG(irg);
1110     }
1111   }
1112   for (i = 0; i < n_irgs; i++) {
1113     ir_graph *irg = get_irp_irg(i);
1114     if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1115       compute_rec_depth(irg, &e);
1116       //printf (" ++ starting at "); DDMG(irg);
1117     }
1118   }
1119
1120   DEL_ARR_F(e.loop_stack);
1121
1122   //dump_callgraph("-with_nesting");
1123
1124   //dump_callgraph_loop_tree(current_loop, "-after_cons");
1125   irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1126 }
1127
1128 /* Maximal loop depth of all paths from an external visible method to
1129     this irg. */
1130 int       get_irg_loop_depth(ir_graph *irg) {
1131   assert(irp->callgraph_state == irp_callgraph_consistent ||
1132          irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1133   return  irg->callgraph_loop_depth;
1134 }
1135
1136 /* Maximal recursion depth of all paths from an external visible method to
1137    this irg. */
1138 int       get_irg_recursion_depth(ir_graph *irg) {
1139   assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1140   return irg->callgraph_recursion_depth;
1141 }
1142
1143 void analyse_loop_nesting_depth(void) {
1144   entity **free_methods = NULL;
1145   int arr_len;
1146
1147   /* establish preconditions. */
1148   if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1149     cgana(&arr_len, &free_methods);
1150   }
1151
1152   if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1153     compute_callgraph();
1154   }
1155
1156   find_callgraph_recursions();
1157 }