1 /* 2 * Copyright (c) 1983, 1993, 2001 3 * The Regents of the University of California. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. Neither the name of the University nor the names of its contributors 14 * may be used to endorse or promote products derived from this software 15 * without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 * SUCH DAMAGE. 28 */ 29 #include "gprof.h" 30 #include "libiberty.h" 31 #include "search_list.h" 32 #include "source.h" 33 #include "symtab.h" 34 #include "call_graph.h" 35 #include "cg_arcs.h" 36 #include "cg_dfn.h" 37 #include "cg_print.h" 38 #include "utils.h" 39 #include "sym_ids.h" 40 41 static int cmp_topo (const PTR, const PTR); 42 static void propagate_time (Sym *); 43 static void cycle_time (void); 44 static void cycle_link (void); 45 static void inherit_flags (Sym *); 46 static void propagate_flags (Sym **); 47 static int cmp_total (const PTR, const PTR); 48 49 Sym *cycle_header; 50 unsigned int num_cycles; 51 Arc **arcs; 52 unsigned int numarcs; 53 54 /* 55 * Return TRUE iff PARENT has an arc to covers the address 56 * range covered by CHILD. 57 */ 58 Arc * 59 arc_lookup (Sym *parent, Sym *child) 60 { 61 Arc *arc; 62 63 if (!parent || !child) 64 { 65 printf ("[arc_lookup] parent == 0 || child == 0\n"); 66 return 0; 67 } 68 DBG (LOOKUPDEBUG, printf ("[arc_lookup] parent %s child %s\n", 69 parent->name, child->name)); 70 for (arc = parent->cg.children; arc; arc = arc->next_child) 71 { 72 DBG (LOOKUPDEBUG, printf ("[arc_lookup]\t parent %s child %s\n", 73 arc->parent->name, arc->child->name)); 74 if (child->addr >= arc->child->addr 75 && child->end_addr <= arc->child->end_addr) 76 { 77 return arc; 78 } 79 } 80 return 0; 81 } 82 83 84 /* 85 * Add (or just increment) an arc: 86 */ 87 void 88 arc_add (Sym *parent, Sym *child, unsigned long count) 89 { 90 static unsigned int maxarcs = 0; 91 Arc *arc, **newarcs; 92 93 DBG (TALLYDEBUG, printf ("[arc_add] %lu arcs from %s to %s\n", 94 count, parent->name, child->name)); 95 arc = arc_lookup (parent, child); 96 if (arc) 97 { 98 /* 99 * A hit: just increment the count. 100 */ 101 DBG (TALLYDEBUG, printf ("[tally] hit %lu += %lu\n", 102 arc->count, count)); 103 arc->count += count; 104 return; 105 } 106 arc = (Arc *) xmalloc (sizeof (*arc)); 107 memset (arc, 0, sizeof (*arc)); 108 arc->parent = parent; 109 arc->child = child; 110 arc->count = count; 111 112 /* If this isn't an arc for a recursive call to parent, then add it 113 to the array of arcs. */ 114 if (parent != child) 115 { 116 /* If we've exhausted space in our current array, get a new one 117 and copy the contents. We might want to throttle the doubling 118 factor one day. */ 119 if (numarcs == maxarcs) 120 { 121 /* Determine how much space we want to allocate. */ 122 if (maxarcs == 0) 123 maxarcs = 1; 124 maxarcs *= 2; 125 126 /* Allocate the new array. */ 127 newarcs = (Arc **)xmalloc(sizeof (Arc *) * maxarcs); 128 129 /* Copy the old array's contents into the new array. */ 130 memcpy (newarcs, arcs, numarcs * sizeof (Arc *)); 131 132 /* Free up the old array. */ 133 free (arcs); 134 135 /* And make the new array be the current array. */ 136 arcs = newarcs; 137 } 138 139 /* Place this arc in the arc array. */ 140 arcs[numarcs++] = arc; 141 } 142 143 /* prepend this child to the children of this parent: */ 144 arc->next_child = parent->cg.children; 145 parent->cg.children = arc; 146 147 /* prepend this parent to the parents of this child: */ 148 arc->next_parent = child->cg.parents; 149 child->cg.parents = arc; 150 } 151 152 153 static int 154 cmp_topo (const PTR lp, const PTR rp) 155 { 156 const Sym *left = *(const Sym **) lp; 157 const Sym *right = *(const Sym **) rp; 158 159 return left->cg.top_order - right->cg.top_order; 160 } 161 162 163 static void 164 propagate_time (Sym *parent) 165 { 166 Arc *arc; 167 Sym *child; 168 double share, prop_share; 169 170 if (parent->cg.prop.fract == 0.0) 171 { 172 return; 173 } 174 175 /* gather time from children of this parent: */ 176 177 for (arc = parent->cg.children; arc; arc = arc->next_child) 178 { 179 child = arc->child; 180 if (arc->count == 0 || child == parent || child->cg.prop.fract == 0) 181 { 182 continue; 183 } 184 if (child->cg.cyc.head != child) 185 { 186 if (parent->cg.cyc.num == child->cg.cyc.num) 187 { 188 continue; 189 } 190 if (parent->cg.top_order <= child->cg.top_order) 191 { 192 fprintf (stderr, "[propagate] toporder botches\n"); 193 } 194 child = child->cg.cyc.head; 195 } 196 else 197 { 198 if (parent->cg.top_order <= child->cg.top_order) 199 { 200 fprintf (stderr, "[propagate] toporder botches\n"); 201 continue; 202 } 203 } 204 if (child->ncalls == 0) 205 { 206 continue; 207 } 208 209 /* distribute time for this arc: */ 210 arc->time = child->hist.time * (((double) arc->count) 211 / ((double) child->ncalls)); 212 arc->child_time = child->cg.child_time 213 * (((double) arc->count) / ((double) child->ncalls)); 214 share = arc->time + arc->child_time; 215 parent->cg.child_time += share; 216 217 /* (1 - cg.prop.fract) gets lost along the way: */ 218 prop_share = parent->cg.prop.fract * share; 219 220 /* fix things for printing: */ 221 parent->cg.prop.child += prop_share; 222 arc->time *= parent->cg.prop.fract; 223 arc->child_time *= parent->cg.prop.fract; 224 225 /* add this share to the parent's cycle header, if any: */ 226 if (parent->cg.cyc.head != parent) 227 { 228 parent->cg.cyc.head->cg.child_time += share; 229 parent->cg.cyc.head->cg.prop.child += prop_share; 230 } 231 DBG (PROPDEBUG, 232 printf ("[prop_time] child \t"); 233 print_name (child); 234 printf (" with %f %f %lu/%lu\n", child->hist.time, 235 child->cg.child_time, arc->count, child->ncalls); 236 printf ("[prop_time] parent\t"); 237 print_name (parent); 238 printf ("\n[prop_time] share %f\n", share)); 239 } 240 } 241 242 243 /* 244 * Compute the time of a cycle as the sum of the times of all 245 * its members. 246 */ 247 static void 248 cycle_time (void) 249 { 250 Sym *member, *cyc; 251 252 for (cyc = &cycle_header[1]; cyc <= &cycle_header[num_cycles]; ++cyc) 253 { 254 for (member = cyc->cg.cyc.next; member; member = member->cg.cyc.next) 255 { 256 if (member->cg.prop.fract == 0.0) 257 { 258 /* 259 * All members have the same propfraction except those 260 * that were excluded with -E. 261 */ 262 continue; 263 } 264 cyc->hist.time += member->hist.time; 265 } 266 cyc->cg.prop.self = cyc->cg.prop.fract * cyc->hist.time; 267 } 268 } 269 270 271 static void 272 cycle_link (void) 273 { 274 Sym *sym, *cyc, *member; 275 Arc *arc; 276 int num; 277 278 /* count the number of cycles, and initialize the cycle lists: */ 279 280 num_cycles = 0; 281 for (sym = symtab.base; sym < symtab.limit; ++sym) 282 { 283 /* this is how you find unattached cycles: */ 284 if (sym->cg.cyc.head == sym && sym->cg.cyc.next) 285 { 286 ++num_cycles; 287 } 288 } 289 290 /* 291 * cycle_header is indexed by cycle number: i.e. it is origin 1, 292 * not origin 0. 293 */ 294 cycle_header = (Sym *) xmalloc ((num_cycles + 1) * sizeof (Sym)); 295 296 /* 297 * Now link cycles to true cycle-heads, number them, accumulate 298 * the data for the cycle. 299 */ 300 num = 0; 301 cyc = cycle_header; 302 for (sym = symtab.base; sym < symtab.limit; ++sym) 303 { 304 if (!(sym->cg.cyc.head == sym && sym->cg.cyc.next != 0)) 305 { 306 continue; 307 } 308 ++num; 309 ++cyc; 310 sym_init (cyc); 311 cyc->cg.print_flag = TRUE; /* should this be printed? */ 312 cyc->cg.top_order = DFN_NAN; /* graph call chain top-sort order */ 313 cyc->cg.cyc.num = num; /* internal number of cycle on */ 314 cyc->cg.cyc.head = cyc; /* pointer to head of cycle */ 315 cyc->cg.cyc.next = sym; /* pointer to next member of cycle */ 316 DBG (CYCLEDEBUG, printf ("[cycle_link] "); 317 print_name (sym); 318 printf (" is the head of cycle %d\n", num)); 319 320 /* link members to cycle header: */ 321 for (member = sym; member; member = member->cg.cyc.next) 322 { 323 member->cg.cyc.num = num; 324 member->cg.cyc.head = cyc; 325 } 326 327 /* 328 * Count calls from outside the cycle and those among cycle 329 * members: 330 */ 331 for (member = sym; member; member = member->cg.cyc.next) 332 { 333 for (arc = member->cg.parents; arc; arc = arc->next_parent) 334 { 335 if (arc->parent == member) 336 { 337 continue; 338 } 339 if (arc->parent->cg.cyc.num == num) 340 { 341 cyc->cg.self_calls += arc->count; 342 } 343 else 344 { 345 cyc->ncalls += arc->count; 346 } 347 } 348 } 349 } 350 } 351 352 353 /* 354 * Check if any parent of this child (or outside parents of this 355 * cycle) have their print flags on and set the print flag of the 356 * child (cycle) appropriately. Similarly, deal with propagation 357 * fractions from parents. 358 */ 359 static void 360 inherit_flags (Sym *child) 361 { 362 Sym *head, *parent, *member; 363 Arc *arc; 364 365 head = child->cg.cyc.head; 366 if (child == head) 367 { 368 /* just a regular child, check its parents: */ 369 child->cg.print_flag = FALSE; 370 child->cg.prop.fract = 0.0; 371 for (arc = child->cg.parents; arc; arc = arc->next_parent) 372 { 373 parent = arc->parent; 374 if (child == parent) 375 { 376 continue; 377 } 378 child->cg.print_flag |= parent->cg.print_flag; 379 /* 380 * If the child was never actually called (e.g., this arc 381 * is static (and all others are, too)) no time propagates 382 * along this arc. 383 */ 384 if (child->ncalls != 0) 385 { 386 child->cg.prop.fract += parent->cg.prop.fract 387 * (((double) arc->count) / ((double) child->ncalls)); 388 } 389 } 390 } 391 else 392 { 393 /* 394 * Its a member of a cycle, look at all parents from outside 395 * the cycle. 396 */ 397 head->cg.print_flag = FALSE; 398 head->cg.prop.fract = 0.0; 399 for (member = head->cg.cyc.next; member; member = member->cg.cyc.next) 400 { 401 for (arc = member->cg.parents; arc; arc = arc->next_parent) 402 { 403 if (arc->parent->cg.cyc.head == head) 404 { 405 continue; 406 } 407 parent = arc->parent; 408 head->cg.print_flag |= parent->cg.print_flag; 409 /* 410 * If the cycle was never actually called (e.g. this 411 * arc is static (and all others are, too)) no time 412 * propagates along this arc. 413 */ 414 if (head->ncalls != 0) 415 { 416 head->cg.prop.fract += parent->cg.prop.fract 417 * (((double) arc->count) / ((double) head->ncalls)); 418 } 419 } 420 } 421 for (member = head; member; member = member->cg.cyc.next) 422 { 423 member->cg.print_flag = head->cg.print_flag; 424 member->cg.prop.fract = head->cg.prop.fract; 425 } 426 } 427 } 428 429 430 /* 431 * In one top-to-bottom pass over the topologically sorted symbols 432 * propagate: 433 * cg.print_flag as the union of parents' print_flags 434 * propfraction as the sum of fractional parents' propfractions 435 * and while we're here, sum time for functions. 436 */ 437 static void 438 propagate_flags (Sym **symbols) 439 { 440 int sym_index; 441 Sym *old_head, *child; 442 443 old_head = 0; 444 for (sym_index = symtab.len - 1; sym_index >= 0; --sym_index) 445 { 446 child = symbols[sym_index]; 447 /* 448 * If we haven't done this function or cycle, inherit things 449 * from parent. This way, we are linear in the number of arcs 450 * since we do all members of a cycle (and the cycle itself) 451 * as we hit the first member of the cycle. 452 */ 453 if (child->cg.cyc.head != old_head) 454 { 455 old_head = child->cg.cyc.head; 456 inherit_flags (child); 457 } 458 DBG (PROPDEBUG, 459 printf ("[prop_flags] "); 460 print_name (child); 461 printf ("inherits print-flag %d and prop-fract %f\n", 462 child->cg.print_flag, child->cg.prop.fract)); 463 if (!child->cg.print_flag) 464 { 465 /* 466 * Printflag is off. It gets turned on by being in the 467 * INCL_GRAPH table, or there being an empty INCL_GRAPH 468 * table and not being in the EXCL_GRAPH table. 469 */ 470 if (sym_lookup (&syms[INCL_GRAPH], child->addr) 471 || (syms[INCL_GRAPH].len == 0 472 && !sym_lookup (&syms[EXCL_GRAPH], child->addr))) 473 { 474 child->cg.print_flag = TRUE; 475 } 476 } 477 else 478 { 479 /* 480 * This function has printing parents: maybe someone wants 481 * to shut it up by putting it in the EXCL_GRAPH table. 482 * (But favor INCL_GRAPH over EXCL_GRAPH.) 483 */ 484 if (!sym_lookup (&syms[INCL_GRAPH], child->addr) 485 && sym_lookup (&syms[EXCL_GRAPH], child->addr)) 486 { 487 child->cg.print_flag = FALSE; 488 } 489 } 490 if (child->cg.prop.fract == 0.0) 491 { 492 /* 493 * No parents to pass time to. Collect time from children 494 * if its in the INCL_TIME table, or there is an empty 495 * INCL_TIME table and its not in the EXCL_TIME table. 496 */ 497 if (sym_lookup (&syms[INCL_TIME], child->addr) 498 || (syms[INCL_TIME].len == 0 499 && !sym_lookup (&syms[EXCL_TIME], child->addr))) 500 { 501 child->cg.prop.fract = 1.0; 502 } 503 } 504 else 505 { 506 /* 507 * It has parents to pass time to, but maybe someone wants 508 * to shut it up by puttting it in the EXCL_TIME table. 509 * (But favor being in INCL_TIME tabe over being in 510 * EXCL_TIME table.) 511 */ 512 if (!sym_lookup (&syms[INCL_TIME], child->addr) 513 && sym_lookup (&syms[EXCL_TIME], child->addr)) 514 { 515 child->cg.prop.fract = 0.0; 516 } 517 } 518 child->cg.prop.self = child->hist.time * child->cg.prop.fract; 519 print_time += child->cg.prop.self; 520 DBG (PROPDEBUG, 521 printf ("[prop_flags] "); 522 print_name (child); 523 printf (" ends up with printflag %d and prop-fract %f\n", 524 child->cg.print_flag, child->cg.prop.fract); 525 printf ("[prop_flags] time %f propself %f print_time %f\n", 526 child->hist.time, child->cg.prop.self, print_time)); 527 } 528 } 529 530 531 /* 532 * Compare by decreasing propagated time. If times are equal, but one 533 * is a cycle header, say that's first (e.g. less, i.e. -1). If one's 534 * name doesn't have an underscore and the other does, say that one is 535 * first. All else being equal, compare by names. 536 */ 537 static int 538 cmp_total (const PTR lp, const PTR rp) 539 { 540 const Sym *left = *(const Sym **) lp; 541 const Sym *right = *(const Sym **) rp; 542 double diff; 543 544 diff = (left->cg.prop.self + left->cg.prop.child) 545 - (right->cg.prop.self + right->cg.prop.child); 546 if (diff < 0.0) 547 { 548 return 1; 549 } 550 if (diff > 0.0) 551 { 552 return -1; 553 } 554 if (!left->name && left->cg.cyc.num != 0) 555 { 556 return -1; 557 } 558 if (!right->name && right->cg.cyc.num != 0) 559 { 560 return 1; 561 } 562 if (!left->name) 563 { 564 return -1; 565 } 566 if (!right->name) 567 { 568 return 1; 569 } 570 if (left->name[0] != '_' && right->name[0] == '_') 571 { 572 return -1; 573 } 574 if (left->name[0] == '_' && right->name[0] != '_') 575 { 576 return 1; 577 } 578 if (left->ncalls > right->ncalls) 579 { 580 return -1; 581 } 582 if (left->ncalls < right->ncalls) 583 { 584 return 1; 585 } 586 return strcmp (left->name, right->name); 587 } 588 589 590 /* Topologically sort the graph (collapsing cycles), and propagates 591 time bottom up and flags top down. */ 592 593 Sym ** 594 cg_assemble (void) 595 { 596 Sym *parent, **time_sorted_syms, **top_sorted_syms; 597 unsigned int sym_index; 598 Arc *arc; 599 600 /* Initialize various things: 601 Zero out child times. 602 Count self-recursive calls. 603 Indicate that nothing is on cycles. */ 604 for (parent = symtab.base; parent < symtab.limit; parent++) 605 { 606 parent->cg.child_time = 0.0; 607 arc = arc_lookup (parent, parent); 608 if (arc && parent == arc->child) 609 { 610 parent->ncalls -= arc->count; 611 parent->cg.self_calls = arc->count; 612 } 613 else 614 { 615 parent->cg.self_calls = 0; 616 } 617 parent->cg.prop.fract = 0.0; 618 parent->cg.prop.self = 0.0; 619 parent->cg.prop.child = 0.0; 620 parent->cg.print_flag = FALSE; 621 parent->cg.top_order = DFN_NAN; 622 parent->cg.cyc.num = 0; 623 parent->cg.cyc.head = parent; 624 parent->cg.cyc.next = 0; 625 if (ignore_direct_calls) 626 find_call (parent, parent->addr, (parent + 1)->addr); 627 } 628 629 /* Topologically order things. If any node is unnumbered, number 630 it and any of its descendents. */ 631 for (parent = symtab.base; parent < symtab.limit; parent++) 632 { 633 if (parent->cg.top_order == DFN_NAN) 634 cg_dfn (parent); 635 } 636 637 /* Link together nodes on the same cycle. */ 638 cycle_link (); 639 640 /* Sort the symbol table in reverse topological order. */ 641 top_sorted_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *)); 642 for (sym_index = 0; sym_index < symtab.len; ++sym_index) 643 top_sorted_syms[sym_index] = &symtab.base[sym_index]; 644 645 qsort (top_sorted_syms, symtab.len, sizeof (Sym *), cmp_topo); 646 DBG (DFNDEBUG, 647 printf ("[cg_assemble] topological sort listing\n"); 648 for (sym_index = 0; sym_index < symtab.len; ++sym_index) 649 { 650 printf ("[cg_assemble] "); 651 printf ("%d:", top_sorted_syms[sym_index]->cg.top_order); 652 print_name (top_sorted_syms[sym_index]); 653 printf ("\n"); 654 } 655 ); 656 657 /* Starting from the topological top, propagate print flags to 658 children. also, calculate propagation fractions. this happens 659 before time propagation since time propagation uses the 660 fractions. */ 661 propagate_flags (top_sorted_syms); 662 663 /* Starting from the topological bottom, propogate children times 664 up to parents. */ 665 cycle_time (); 666 for (sym_index = 0; sym_index < symtab.len; ++sym_index) 667 propagate_time (top_sorted_syms[sym_index]); 668 669 free (top_sorted_syms); 670 671 /* Now, sort by CG.PROP.SELF + CG.PROP.CHILD. Sorting both the regular 672 function names and cycle headers. */ 673 time_sorted_syms = (Sym **) xmalloc ((symtab.len + num_cycles) * sizeof (Sym *)); 674 for (sym_index = 0; sym_index < symtab.len; sym_index++) 675 time_sorted_syms[sym_index] = &symtab.base[sym_index]; 676 677 for (sym_index = 1; sym_index <= num_cycles; sym_index++) 678 time_sorted_syms[symtab.len + sym_index - 1] = &cycle_header[sym_index]; 679 680 qsort (time_sorted_syms, symtab.len + num_cycles, sizeof (Sym *), 681 cmp_total); 682 683 for (sym_index = 0; sym_index < symtab.len + num_cycles; sym_index++) 684 time_sorted_syms[sym_index]->cg.index = sym_index + 1; 685 686 return time_sorted_syms; 687 } 688