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