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