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 "array.h"
  22 #include "pmap.h"
  23
  24 #include "irgwalk.h"
  25
  26 /* The functions that call irg. */
  27 int       get_irg_n_callers(ir_graph *irg) {
  28   if (irg->callers) return ARR_LEN(irg->callers);
  29   return -1;
  30 }
  31 ir_graph *get_irg_caller(ir_graph *irg, int pos) {
  32   assert (pos >= 0 && pos < get_irg_n_callers(irg));
  33   if (irg->callers) return irg->callers[pos];
  34   return NULL;
  35 }
  36 int       is_irg_caller_backedge(ir_graph *irg, int pos) {
  37   assert (pos >= 0 && pos < get_irg_n_callers(irg));
  38   return  irg->caller_isbe[pos];
  39 }
  40 static void       set_irg_caller_backedge(ir_graph *irg, int pos) {
  41   assert (pos >= 0 && pos < get_irg_n_callers(irg));
  42   irg->caller_isbe[pos] = 1;
  43 }
  44
  45 /* The functions called by irg. */
  46 int       get_irg_n_callees(ir_graph *irg) {
  47   if (irg->callees) return ARR_LEN(irg->callees);
  48   return -1;
  49 }
  50 ir_graph *get_irg_callee(ir_graph *irg, int pos) {
  51   assert (pos >= 0 && pos < get_irg_n_callees(irg));
  52   if (irg->callees) return irg->callees[pos];
  53   return NULL;
  54 }
  55 int       is_irg_callee_backedge(ir_graph *irg, int pos) {
  56   assert (pos >= 0 && pos < get_irg_n_callees(irg));
  57   return irg->callee_isbe[pos];
  58 }
  59 void       set_irg_callee_backedge(ir_graph *irg, int pos) {
  60   assert (pos >= 0 && pos < get_irg_n_callees(irg));
  61   irg->callee_isbe[pos] = 1;
  62 }
  63
  64
  65 static void ana_Call(ir_node *n, void *env) {
  66   int i, n_callees;
  67   ir_graph *irg;
  68
  69   if (get_irn_op(n) != op_Call) return;
  70
  71   irg = get_irn_irg(n);
  72   n_callees = get_Call_n_callees(n);
  73   for (i = 0; i < n_callees; ++i) {
  74     entity *callee_e = get_Call_callee(n, i);
  75     if (callee_e) {
  76       ir_graph *callee = get_entity_irg(callee_e);
  77       pset_insert((pset *)irg->callees,    callee, (unsigned)callee >> 3);
  78       pset_insert((pset *)callee->callers, irg,    (unsigned)irg >> 3);
  79     }
  80   }
  81 }
  82
  83
  84 /* compare two ir graphs */
  85 static int graph_cmp(const void *elt, const void *key) {
  86   return elt != key;
  87 }
  88
  89
  90 /* Construct and destruct the callgraph. */
  91 void compute_callgraph(void) {
  92   int i, n_irgs = get_irp_n_irgs();
  93
  94   assert(interprocedural_view == 0);  /* Else walking will not reach the Call nodes. */
  95
  96   /* initialize */
  97   free_callgraph();
  98   for (i = 0; i < n_irgs; ++i) {
  99     ir_graph *irg = get_irp_irg(i);
 100     assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
 101     irg->callees = (ir_graph **)new_pset(graph_cmp, 8);
 102     irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
 103   }
 104
 105   /* Compute the call graph */
 106   for (i = 0; i < n_irgs; ++i) {
 107     ir_graph *irg = get_irp_irg(i);
 108     irg_walk_graph(irg, ana_Call, NULL, NULL);
 109   }
 110
 111   /* Change the sets to arrays. */
 112   for (i = 0; i < n_irgs; ++i) {
 113     int j, count;
 114     ir_graph *c, *irg = get_irp_irg(i);
 115
 116     pset *callee_set = (pset *)irg->callees;
 117     count = pset_count(callee_set);
 118     irg->callees = NEW_ARR_F(ir_graph *, count);
 119     irg->callee_isbe = calloc(count, sizeof(int));
 120     c = pset_first(callee_set);
 121     for (j = 0; j < count; ++j) {
 122       irg->callees[j] = c;
 123       c = pset_next(callee_set);
 124     }
 125     del_pset(callee_set);
 126     assert(c == NULL);
 127
 128     pset *caller_set = (pset *)irg->callers;
 129     count = pset_count(caller_set);
 130     irg->callers = NEW_ARR_F(ir_graph *, count);
 131     irg->caller_isbe =  calloc(count, sizeof(int));
 132     c = pset_first(caller_set);
 133     for (j = 0; j < count; ++j) {
 134       irg->callers[j] = c;
 135       c = pset_next(caller_set);
 136     }
 137     del_pset(caller_set);
 138     assert(c == NULL);
 139   }
 140 }
 141
 142 void free_callgraph(void) {
 143   int i, n_irgs = get_irp_n_irgs();
 144   for (i = 0; i < n_irgs; ++i) {
 145     ir_graph *irg = get_irp_irg(i);
 146     if (irg->callees) DEL_ARR_F(irg->callees);
 147     if (irg->callers) DEL_ARR_F(irg->callers);
 148     if (irg->callee_isbe) DEL_ARR_F(irg->callee_isbe);
 149     if (irg->caller_isbe) DEL_ARR_F(irg->caller_isbe);
 150     irg->callees = NULL;
 151     irg->callers = NULL;
 152     irg->callee_isbe = NULL;
 153     irg->caller_isbe = NULL;
 154   }
 155 }
 156
 157
 158 /* ----------------------------------------------------------------------------------- */
 159 /* loop construction algorithm                                                         */
 160 /* ----------------------------------------------------------------------------------- */
 161
 162 static ir_graph *outermost_ir_graph;      /* The outermost graph the scc is computed
 163                       for */
 164 static ir_loop *current_loop;      /* Current cfloop construction is working
 165                       on. */
 166 static int loop_node_cnt = 0;      /* Counts the number of allocated cfloop nodes.
 167                       Each cfloop node gets a unique number.
 168                       What for? ev. remove. @@@ */
 169 static int current_dfn = 1;        /* Counter to generate depth first numbering
 170                       of visited nodes.  */
 171
 172
 173 /**********************************************************************/
 174 /* Node attributes                                                   **/
 175 /**********************************************************************/
 176
 177 typedef struct scc_info {
 178   bool in_stack;         /* Marks whether node is on the stack. */
 179   int dfn;               /* Depth first search number. */
 180   int uplink;            /* dfn number of ancestor. */
 181   int visited;
 182 } scc_info;
 183
 184 static INLINE scc_info* new_scc_info(void) {
 185   scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
 186   memset (info, 0, sizeof (scc_info));
 187   return info;
 188 }
 189
 190 static INLINE int
 191 cg_irg_visited(ir_graph *n) {
 192   return ((scc_info *)n->link)->visited;
 193 }
 194
 195 static INLINE void
 196 mark_cg_irg_visited(ir_graph *n) {
 197   ((scc_info *)n->link)->visited = 1;
 198 }
 199
 200 static INLINE void
 201 set_cg_irg_visited(ir_graph *n, int i) {
 202   ((scc_info *)n->link)->visited = i;
 203 }
 204
 205 static INLINE void
 206 mark_irg_in_stack (ir_graph *n) {
 207   assert(get_irg_link(n));
 208   ((scc_info *)n->link)->in_stack = true;
 209 }
 210
 211 static INLINE void
 212 mark_irg_not_in_stack (ir_graph *n) {
 213   assert(get_irg_link(n));
 214   ((scc_info *)n->link)->in_stack = false;
 215 }
 216
 217 static INLINE bool
 218 irg_is_in_stack (ir_graph *n) {
 219   assert(get_irg_link(n));
 220   return ((scc_info *)n->link)->in_stack;
 221 }
 222
 223 static INLINE void
 224 set_irg_uplink (ir_graph *n, int uplink) {
 225   assert(get_irg_link(n));
 226   ((scc_info *)n->link)->uplink = uplink;
 227 }
 228
 229 static INLINE int
 230 get_irg_uplink (ir_graph *n) {
 231   assert(get_irg_link(n));
 232   return ((scc_info *)n->link)->uplink;
 233 }
 234
 235 static INLINE void
 236 set_irg_dfn (ir_graph *n, int dfn) {
 237   assert(get_irg_link(n));
 238   ((scc_info *)n->link)->dfn = dfn;
 239 }
 240
 241 static INLINE int
 242 get_irg_dfn (ir_graph *n) {
 243   assert(get_irg_link(n));
 244   return ((scc_info *)n->link)->dfn;
 245 }
 246
 247 /**********************************************************************/
 248 /* A stack.                                                          **/
 249 /**********************************************************************/
 250
 251 static ir_graph **stack = NULL;
 252 static int tos = 0;                /* top of stack */
 253
 254 static INLINE void init_stack(void) {
 255   if (stack) {
 256     ARR_RESIZE (ir_graph *, stack, 1000);
 257   } else {
 258     stack = NEW_ARR_F (ir_graph *, 1000);
 259   }
 260   tos = 0;
 261 }
 262
 263
 264 static INLINE void
 265 push (ir_graph *n)
 266 {
 267   if (tos == ARR_LEN (stack)) {
 268     int nlen = ARR_LEN (stack) * 2;
 269     ARR_RESIZE (ir_node *, stack, nlen);
 270   }
 271   stack [tos++] = n;
 272   mark_irg_in_stack(n);
 273 }
 274
 275 static INLINE ir_graph *
 276 pop (void)
 277 {
 278   ir_graph *n = stack[--tos];
 279   mark_irg_not_in_stack(n);
 280   return n;
 281 }
 282
 283 /* The nodes up to n belong to the current loop.
 284    Removes them from the stack and adds them to the current loop. */
 285 static INLINE void
 286 pop_scc_to_loop (ir_graph *n)
 287 {
 288   ir_graph *m;
 289
 290   /*for (;;) {*/
 291   do {
 292     m = pop();
 293     loop_node_cnt++;
 294     set_irg_dfn(m, loop_node_cnt);
 295     add_loop_node(current_loop, (ir_node *)m);
 296     set_irg_loop(m, current_loop);
 297     /*    if (m==n) break;*/
 298   } while(m != n);
 299 }
 300
 301 /* GL ??? my last son is my grandson???  Removes cfloops with no
 302    ir_nodes in them.  Such loops have only another loop as son. (Why
 303    can't they have two loops as sons? Does it never get that far? ) */
 304 static void close_loop (ir_loop *l)
 305 {
 306   int last = get_loop_n_elements(l) - 1;
 307   loop_element lelement = get_loop_element(l, last);
 308   ir_loop *last_son = lelement.son;
 309
 310   if (get_kind(last_son) == k_ir_loop &&
 311       get_loop_n_elements(last_son) == 1) {
 312     ir_loop *gson;
 313
 314     lelement = get_loop_element(last_son, 0);
 315     gson = lelement.son;
 316     if(get_kind(gson) == k_ir_loop) {
 317       loop_element new_last_son;
 318
 319       gson -> outer_loop = l;
 320       new_last_son.son = gson;
 321       l -> children[last] = new_last_son;
 322     }
 323   }
 324
 325   current_loop = l;
 326 }
 327
 328 /* Removes and unmarks all nodes up to n from the stack.
 329    The nodes must be visited once more to assign them to a scc. */
 330 static INLINE void
 331 pop_scc_unmark_visit (ir_graph *n)
 332 {
 333   ir_graph *m = NULL;
 334
 335   while (m != n) {
 336     m = pop();
 337     set_cg_irg_visited(m, 0);
 338   }
 339 }
 340
 341 /**********************************************************************/
 342 /* The loop datastructure.                                           **/
 343 /**********************************************************************/
 344
 345 /* Allocates a new loop as son of current_loop.  Sets current_loop
 346    to the new loop and returns the father. */
 347 static ir_loop *new_loop (void) {
 348   ir_loop *father, *son;
 349
 350   father = current_loop;
 351
 352   son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
 353   memset (son, 0, sizeof (ir_loop));
 354   son->kind = k_ir_loop;
 355   son->children = NEW_ARR_F (loop_element, 0);
 356   son->n_nodes = 0;
 357   son->n_sons = 0;
 358   if (father) {
 359     son->outer_loop = father;
 360     add_loop_son(father, son);
 361     son->depth = father->depth+1;
 362   } else {  /* The root loop */
 363     son->outer_loop = son;
 364     son->depth = 0;
 365   }
 366
 367 #ifdef DEBUG_libfirm
 368   son->loop_nr = get_irp_new_node_nr();
 369   son->link = NULL;
 370 #endif
 371
 372   current_loop = son;
 373   return father;
 374 }
 375
 376 /**********************************************************************/
 377 /* Constructing and destructing the loop/backedge information.       **/
 378 /**********************************************************************/
 379
 380 /* Initialization steps. **********************************************/
 381
 382 static INLINE void
 383 init_scc (ir_graph *irg) {
 384   int i;
 385   current_dfn = 1;
 386   loop_node_cnt = 0;
 387   init_stack();
 388   for (i = 0; i < get_irp_n_irgs(); ++i) {
 389     set_irg_link(get_irp_irg(i), new_scc_info());
 390   }
 391 }
 392
 393 /** Returns true if n is a loop header, i.e., it is a Block node
 394  *  and has predecessors within the cfloop and out of the cfloop.
 395  *
 396  *  @param root: only needed for assertion.
 397  */
 398 static bool
 399 is_head (ir_graph *n, ir_graph *root)
 400 {
 401   int i, arity;
 402   int some_outof_loop = 0, some_in_loop = 0;
 403
 404   arity = get_irg_n_callees(n);
 405   for (i = 0; i < arity; i++) {
 406     ir_graph *pred = get_irg_callee(n, i);
 407     if (is_irg_callee_backedge(n, i)) continue;
 408     if (!irg_is_in_stack(pred)) {
 409       some_outof_loop = 1;
 410     } else {
 411       if (get_irg_uplink(pred) < get_irg_uplink(root))  {
 412         DDMG(pred); DDMG(root);
 413         assert(get_irg_uplink(pred) >= get_irg_uplink(root));
 414       }
 415       some_in_loop = 1;
 416     }
 417   }
 418
 419   return some_outof_loop && some_in_loop;
 420 }
 421 /* Returns true if n is possible loop head of an endless loop.
 422    I.e., it is a Block, Phi or Filter node and has only predecessors
 423    within the loop.
 424    @arg root: only needed for assertion. */
 425 static bool
 426 is_endless_head (ir_graph *n, ir_graph *root)
 427 {
 428   int i, arity;
 429   int some_outof_loop = 0, some_in_loop = 0;
 430
 431   arity = get_irg_n_callees(n);
 432   for (i = 0; i < arity; i++) {
 433     ir_graph *pred = get_irg_callee(n, i);
 434     assert(pred);
 435     if (is_irg_callee_backedge(n, i)) { continue; }
 436     if (!irg_is_in_stack(pred)) {
 437         some_outof_loop = 1;
 438     } else {
 439       if(get_irg_uplink(pred) < get_irg_uplink(root)) {
 440         DDMG(pred); DDMG(root);
 441         assert(get_irg_uplink(pred) >= get_irg_uplink(root));
 442       }
 443       some_in_loop = 1;
 444     }
 445   }
 446
 447   return !some_outof_loop && some_in_loop;
 448 }
 449
 450 /* Returns index of the predecessor with the smallest dfn number
 451    greater-equal than limit. */
 452 static int
 453 smallest_dfn_pred (ir_graph *n, int limit)
 454 {
 455   int i, index = -2, min = -1;
 456
 457   int arity = get_irg_n_callees(n);
 458   for (i = 0; i < arity; i++) {
 459     ir_graph *pred = get_irg_callee(n, i);
 460     if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue;
 461     if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
 462       index = i;
 463       min = get_irg_dfn(pred);
 464     }
 465   }
 466
 467   return index;
 468 }
 469
 470 /* Returns index of the predecessor with the largest dfn number. */
 471 static int
 472 largest_dfn_pred (ir_graph *n)
 473 {
 474   int i, index = -2, max = -1;
 475
 476   int arity = get_irg_n_callees(n);
 477   for (i = 0; i < arity; i++) {
 478     ir_graph *pred = get_irg_callee(n, i);
 479     if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
 480     if (get_irg_dfn(pred) > max) {
 481       index = i;
 482       max = get_irg_dfn(pred);
 483     }
 484   }
 485
 486   return index;
 487 }
 488
 489 static ir_graph *
 490 find_tail (ir_graph *n) {
 491   ir_graph *m;
 492   int i, res_index = -2;
 493
 494   /*
 495     if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
 496   */
 497   m = stack[tos-1];  /* tos = top of stack */
 498   if (is_head (m, n)) {
 499     res_index = smallest_dfn_pred(m, 0);
 500     if ((res_index == -2) &&  /* no smallest dfn pred found. */
 501     (n ==  m))
 502       return NULL;
 503   } else {
 504     if (m == n) return NULL;    // Is this to catch Phi - self loops?
 505     for (i = tos-2; i >= 0; --i) {
 506       m = stack[i];
 507
 508       if (is_head (m, n)) {
 509         res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
 510         if (res_index == -2)  /* no smallest dfn pred found. */
 511           res_index = largest_dfn_pred (m);
 512
 513         if ((m == n) && (res_index == -2)) {
 514           i = -1;
 515         }
 516         break;
 517       }
 518
 519       /* We should not walk past our selves on the stack:  The upcoming nodes
 520          are not in this loop. We assume a loop not reachable from Start. */
 521       if (m == n) {
 522         i = -1;
 523         break;
 524       }
 525
 526     }
 527
 528     if (i < 0) {
 529       /* A dead loop not reachable from Start. */
 530       for (i = tos-2; i >= 0; --i) {
 531         m = stack[i];
 532         if (is_endless_head (m, n)) {
 533           res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
 534           if (res_index == -2)  /* no smallest dfn pred found. */
 535             res_index = largest_dfn_pred (m);
 536           break;
 537         }
 538         if (m == n) { break; }  /* It's not an unreachable loop, either. */
 539       }
 540       //assert(0 && "no head found on stack");
 541     }
 542
 543   }
 544   assert (res_index > -2);
 545
 546   set_irg_callee_backedge (m, res_index);
 547   return get_irg_callee(m, res_index);
 548 }
 549
 550
 551
 552 /*-----------------------------------------------------------*
 553  *                   The core algorithm.                     *
 554  *-----------------------------------------------------------*/
 555
 556
 557 static void cgscc (ir_graph *n) {
 558   int i;
 559
 560   if (cg_irg_visited(n)) return;
 561   mark_cg_irg_visited(n);
 562
 563   /* Initialize the node */
 564   set_irg_dfn(n, current_dfn);      /* Depth first number for this node */
 565   set_irg_uplink(n, current_dfn);   /* ... is default uplink. */
 566   set_irg_loop(n, NULL);
 567   current_dfn ++;
 568   push(n);
 569
 570   int arity = get_irg_n_callees(n);
 571
 572   for (i = 0; i < arity; i++) {
 573     ir_graph *m;
 574     if (is_irg_callee_backedge(n, i)) continue;
 575     m = get_irg_callee(n, i);
 576
 577     /** This marks the backedge, but does it guarantee a correct loop tree? */
 578     if (m == n) { set_irg_callee_backedge(n, i); continue; }
 579
 580     cgscc (m);
 581     if (irg_is_in_stack(m)) {
 582       /* Uplink of m is smaller if n->m is a backedge.
 583          Propagate the uplink to mark the cfloop. */
 584       if (get_irg_uplink(m) < get_irg_uplink(n))
 585         set_irg_uplink(n, get_irg_uplink(m));
 586     }
 587   }
 588
 589   if (get_irg_dfn(n) == get_irg_uplink(n)) {
 590     /* This condition holds for
 591        1) the node with the incoming backedge.
 592        That is: We found a cfloop!
 593        2) Straight line code, because no uplink has been propagated, so the
 594        uplink still is the same as the dfn.
 595
 596        But n might not be a proper cfloop head for the analysis. Proper cfloop
 597        heads are Block and Phi nodes. find_tail searches the stack for
 598        Block's and Phi's and takes those nodes as cfloop heads for the current
 599        cfloop instead and marks the incoming edge as backedge. */
 600
 601     ir_graph *tail = find_tail(n);
 602     if (tail) {
 603       /* We have a cfloop, that is no straight line code,
 604          because we found a cfloop head!
 605          Next actions: Open a new cfloop on the cfloop tree and
 606          try to find inner cfloops */
 607
 608
 609       ir_loop *l = new_loop();
 610
 611       /* Remove the cfloop from the stack ... */
 612       pop_scc_unmark_visit (n);
 613
 614       /* The current backedge has been marked, that is temporarily eliminated,
 615          by find tail. Start the scc algorithm
 616          anew on the subgraph thats left (the current cfloop without the backedge)
 617          in order to find more inner cfloops. */
 618
 619       cgscc (tail);
 620
 621       assert (cg_irg_visited(n));
 622       close_loop(l);
 623     } else {
 624       pop_scc_to_loop(n);
 625     }
 626   }
 627 }
 628
 629
 630
 631 static void reset_isbe(void) {
 632   int i, n_irgs = get_irp_n_irgs();
 633
 634   for (i = 0; i < n_irgs; ++i) {
 635     int j, n_cs;
 636     ir_graph *irg = get_irp_irg(i);
 637
 638     n_cs = get_irg_n_callers(irg);
 639     for (j = 0; j < n_cs; ++j) {
 640       irg->caller_isbe[j] = 0;
 641     }
 642     n_cs = get_irg_n_callees(irg);
 643     for (j = 0; j < n_cs; ++j) {
 644       irg->callee_isbe[j] = 0;
 645     }
 646   }
 647 }
 648
 649 /* Compute the backedges that represent recursions. */
 650 void find_callgraph_recursions(void) {
 651   int i, n_irgs = get_irp_n_irgs();
 652
 653   reset_isbe();
 654
 655   assert(get_irp_main_irg()); /* The outermost graph.  We start here.  Then we start at all
 656                                  external visible functions in irg list, then at the remaining
 657                                  unvisited ones. */
 658   outermost_ir_graph = get_irp_main_irg();
 659
 660   assert(!interprocedural_view &&
 661      "use construct_ip_backedges");
 662
 663   init_scc(current_ir_graph);
 664
 665   current_loop = NULL;
 666   new_loop();  /* sets current_loop */
 667
 668   cgscc(outermost_ir_graph);
 669
 670   for (i = 0; i < n_irgs; i++) {
 671     ir_graph *irg = get_irp_irg(i);
 672     if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
 673       cgscc(irg);
 674   }
 675   for (i = 0; i < n_irgs; i++) {
 676     ir_graph *irg = get_irp_irg(i);
 677     if (!cg_irg_visited(irg))
 678       cgscc(irg);
 679   }
 680
 681   /* We can not use the looptree -- it has no real meaning.
 682      There is a working dumper, but commented out.
 683      assert(current_loop && current_loop == get_loop_outer_loop(current_loop));
 684      dump_callgraph_loop_tree(current_loop, ""); */
 685 }