1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* 23 * Copyright (c) 1990-1998,2001 by Sun Microsystems, Inc. 24 * All rights reserved. 25 */ 26 27 #pragma ident "%Z%%M% %I% %E% SMI" 28 29 #include <stdlib.h> 30 #include "gprof.h" 31 32 /* 33 * add (or just increment) an arc 34 */ 35 void 36 addarc(nltype *parentp, nltype *childp, actype count) 37 { 38 arctype *arcp; 39 40 #ifdef DEBUG 41 if (debug & TALLYDEBUG) { 42 printf("[addarc] %lld arcs from %s to %s\n", 43 count, parentp->name, childp->name); 44 } 45 #endif /* DEBUG */ 46 arcp = arclookup(parentp, childp); 47 if (arcp != 0) { 48 /* 49 * a hit: just increment the count. 50 */ 51 #ifdef DEBUG 52 if (!Dflag) { 53 if (debug & TALLYDEBUG) { 54 printf("[tally] hit %lld += %lld\n", 55 arcp->arc_count, count); 56 } 57 } else { 58 if (debug & TALLYDEBUG) { 59 printf("[tally] hit %lld -= %lld\n", 60 arcp->arc_count, count); 61 } 62 } 63 64 #endif /* DEBUG */ 65 if (!Dflag) 66 arcp->arc_count += count; 67 else { 68 arcp->arc_count -= count; 69 if (arcp->arc_count < 0) 70 arcp->arc_count = 0; 71 } 72 return; 73 } 74 arcp = (arctype *)calloc(1, sizeof (*arcp)); 75 arcp->arc_parentp = parentp; 76 arcp->arc_childp = childp; 77 arcp->arc_count = count; 78 /* 79 * prepend this child to the children of this parent 80 */ 81 arcp->arc_childlist = parentp->children; 82 parentp->children = arcp; 83 /* 84 * prepend this parent to the parents of this child 85 */ 86 arcp->arc_parentlist = childp->parents; 87 childp->parents = arcp; 88 } 89 90 /* 91 * the code below topologically sorts the graph (collapsing cycles), 92 * and propagates time bottom up and flags top down. 93 */ 94 95 /* 96 * the topologically sorted name list pointers 97 */ 98 nltype **topsortnlp; 99 100 static int 101 topcmp(nltype **npp1, nltype **npp2) 102 { 103 return ((*npp1)->toporder - (*npp2)->toporder); 104 } 105 106 static void 107 timepropagate(nltype *parentp) 108 { 109 arctype *arcp; 110 nltype *childp; 111 double share; 112 double propshare; 113 114 if (parentp->propfraction == 0.0) { 115 return; 116 } 117 /* 118 * gather time from children of this parent. 119 */ 120 for (arcp = parentp->children; arcp; arcp = arcp->arc_childlist) { 121 childp = arcp->arc_childp; 122 if (arcp->arc_count == 0) { 123 continue; 124 } 125 if (childp == parentp) { 126 continue; 127 } 128 if (childp->propfraction == 0.0) { 129 continue; 130 } 131 if (childp->cyclehead != childp) { 132 if (parentp->cycleno == childp->cycleno) { 133 continue; 134 } 135 if (parentp->toporder <= childp->toporder) { 136 fprintf(stderr, 137 "[propagate] toporder botches\n"); 138 } 139 childp = childp->cyclehead; 140 } else { 141 if (parentp->toporder <= childp->toporder) { 142 fprintf(stderr, 143 "[propagate] toporder botches\n"); 144 continue; 145 } 146 } 147 if (childp->ncall == 0) { 148 continue; 149 } 150 /* 151 * distribute time for this arc 152 */ 153 arcp->arc_time = childp->time 154 * (((double)arcp->arc_count) / 155 ((double)childp->ncall)); 156 arcp->arc_childtime = childp->childtime 157 * (((double)arcp->arc_count) / 158 ((double)childp->ncall)); 159 share = arcp->arc_time + arcp->arc_childtime; 160 parentp->childtime += share; 161 /* 162 * (1 - propfraction) gets lost along the way 163 */ 164 propshare = parentp->propfraction * share; 165 /* 166 * fix things for printing 167 */ 168 parentp->propchild += propshare; 169 arcp->arc_time *= parentp->propfraction; 170 arcp->arc_childtime *= parentp->propfraction; 171 /* 172 * add this share to the parent's cycle header, if any. 173 */ 174 if (parentp->cyclehead != parentp) { 175 parentp->cyclehead->childtime += share; 176 parentp->cyclehead->propchild += propshare; 177 } 178 #ifdef DEBUG 179 if (debug & PROPDEBUG) { 180 printf("[dotime] child \t"); 181 printname(childp); 182 printf(" with %f %f %lld/%lld\n", 183 childp->time, childp->childtime, 184 arcp->arc_count, childp->ncall); 185 printf("[dotime] parent\t"); 186 printname(parentp); 187 printf("\n[dotime] share %f\n", share); 188 } 189 #endif /* DEBUG */ 190 } 191 } 192 193 194 static void 195 cycletime() 196 { 197 int cycle; 198 nltype *cyclenlp; 199 nltype *childp; 200 201 for (cycle = 1; cycle <= ncycle; cycle += 1) { 202 cyclenlp = &cyclenl[cycle]; 203 for (childp = cyclenlp->cnext; childp; childp = childp->cnext) { 204 if (childp->propfraction == 0.0) { 205 /* 206 * all members have the same propfraction 207 * except those that were excluded with -E 208 */ 209 continue; 210 } 211 cyclenlp->time += childp->time; 212 } 213 cyclenlp->propself = cyclenlp->propfraction * cyclenlp->time; 214 } 215 } 216 217 218 static void 219 dotime() 220 { 221 int index; 222 223 cycletime(); 224 for (index = 0; index < total_names; index += 1) { 225 timepropagate(topsortnlp[index]); 226 } 227 } 228 229 230 static void 231 cyclelink() 232 { 233 register nltype *nlp; 234 register nltype *cyclenlp; 235 int cycle; 236 nltype *memberp; 237 arctype *arcp; 238 mod_info_t *mi; 239 240 /* 241 * Count the number of cycles, and initialize the cycle lists 242 */ 243 ncycle = 0; 244 for (mi = &modules; mi; mi = mi->next) { 245 for (nlp = mi->nl; nlp < mi->npe; nlp++) { 246 /* 247 * this is how you find unattached cycles 248 */ 249 if (nlp->cyclehead == nlp && nlp->cnext != 0) { 250 ncycle += 1; 251 } 252 } 253 } 254 255 /* 256 * cyclenl is indexed by cycle number: 257 * i.e. it is origin 1, not origin 0. 258 */ 259 cyclenl = (nltype *) calloc(ncycle + 1, sizeof (nltype)); 260 if (cyclenl == 0) { 261 fprintf(stderr, 262 "%s: No room for %d bytes of cycle headers\n", 263 whoami, (ncycle + 1) * sizeof (nltype)); 264 done(); 265 } 266 267 /* 268 * now link cycles to true cycleheads, 269 * number them, accumulate the data for the cycle 270 */ 271 cycle = 0; 272 for (mi = &modules; mi; mi = mi->next) { 273 for (nlp = mi->nl; nlp < mi->npe; nlp++) { 274 if (!(nlp->cyclehead == nlp && nlp->cnext != 0)) { 275 continue; 276 } 277 cycle += 1; 278 cyclenlp = &cyclenl[cycle]; 279 cyclenlp->name = 0; /* the name */ 280 cyclenlp->value = 0; /* pc entry point */ 281 cyclenlp->time = 0.0; /* ticks in routine */ 282 cyclenlp->childtime = 0.0; /* cumulative ticks */ 283 /* in children */ 284 cyclenlp->ncall = 0; /* how many times */ 285 /* called */ 286 cyclenlp->selfcalls = 0; /* how many calls */ 287 /* to self */ 288 cyclenlp->propfraction = 0.0; /* what % of time */ 289 /* propagates */ 290 cyclenlp->propself = 0.0; /* how much self time */ 291 /* propagates */ 292 cyclenlp->propchild = 0.0; /* how much of child */ 293 /* time propagates */ 294 cyclenlp->printflag = TRUE; /* should this be */ 295 /* printed? */ 296 cyclenlp->index = 0; /* index in the */ 297 /* graph list */ 298 cyclenlp->toporder = DFN_NAN; /* graph call chain */ 299 /* top-sort order */ 300 cyclenlp->cycleno = cycle; /* internal number */ 301 /* of cycle on */ 302 cyclenlp->cyclehead = cyclenlp; /* head of cycle ptr */ 303 cyclenlp->cnext = nlp; /* ptr to next member */ 304 /* of cycle */ 305 cyclenlp->parents = 0; /* caller arcs list */ 306 cyclenlp->children = 0; /* callee arcs list */ 307 #ifdef DEBUG 308 if (debug & CYCLEDEBUG) { 309 printf("[cyclelink] "); 310 printname(nlp); 311 printf(" is the head of cycle %d\n", cycle); 312 } 313 #endif /* DEBUG */ 314 /* 315 * link members to cycle header 316 */ 317 for (memberp = nlp; memberp; memberp = memberp->cnext) { 318 memberp->cycleno = cycle; 319 memberp->cyclehead = cyclenlp; 320 } 321 /* 322 * count calls from outside the cycle 323 * and those among cycle members 324 */ 325 for (memberp = nlp; memberp; memberp = memberp->cnext) { 326 for (arcp = memberp->parents; arcp; 327 arcp = arcp->arc_parentlist) { 328 if (arcp->arc_parentp == memberp) 329 continue; 330 331 if (arcp->arc_parentp->cycleno == 332 cycle) { 333 cyclenlp->selfcalls += 334 arcp->arc_count; 335 } else 336 cyclenlp->ncall += arcp->arc_count; 337 } 338 } 339 } 340 } 341 } 342 343 344 /* 345 * check if any parent of this child 346 * (or outside parents of this cycle) 347 * have their print flags on and set the 348 * print flag of the child (cycle) appropriately. 349 * similarly, deal with propagation fractions from parents. 350 */ 351 static void 352 inheritflags(nltype *childp) 353 { 354 nltype *headp; 355 arctype *arcp; 356 nltype *parentp; 357 nltype *memp; 358 359 headp = childp->cyclehead; 360 if (childp == headp) { 361 /* 362 * just a regular child, check its parents 363 */ 364 childp->printflag = FALSE; 365 childp->propfraction = 0.0; 366 for (arcp = childp->parents; arcp; 367 arcp = arcp->arc_parentlist) { 368 parentp = arcp->arc_parentp; 369 if (childp == parentp) { 370 continue; 371 } 372 childp->printflag |= parentp->printflag; 373 /* 374 * if the child was never actually called 375 * (e.g. this arc is static (and all others 376 * are, too)) no time propagates along this arc. 377 */ 378 if (childp->ncall) { 379 childp->propfraction += parentp->propfraction 380 * (((double)arcp->arc_count) 381 / ((double)childp->ncall)); 382 } 383 } 384 } else { 385 /* 386 * its a member of a cycle, look at all parents from 387 * outside the cycle 388 */ 389 headp->printflag = FALSE; 390 headp->propfraction = 0.0; 391 for (memp = headp->cnext; memp; memp = memp->cnext) { 392 for (arcp = memp->parents; arcp; 393 arcp = arcp->arc_parentlist) { 394 if (arcp->arc_parentp->cyclehead == headp) { 395 continue; 396 } 397 parentp = arcp->arc_parentp; 398 headp->printflag |= parentp->printflag; 399 /* 400 * if the cycle was never actually called 401 * (e.g. this arc is static (and all 402 * others are, too)) no time propagates 403 * along this arc. 404 */ 405 if (headp->ncall) { 406 headp->propfraction += 407 parentp->propfraction 408 * (((double)arcp->arc_count) 409 / ((double)headp->ncall)); 410 } 411 } 412 } 413 for (memp = headp; memp; memp = memp->cnext) { 414 memp->printflag = headp->printflag; 415 memp->propfraction = headp->propfraction; 416 } 417 } 418 } 419 420 421 /* 422 * check here if *any* of its parents is printable 423 * then return true else return false 424 */ 425 static int 426 check_ancestors(nltype *siblingp) 427 { 428 arctype *parentsp; 429 if (!siblingp->parents) 430 return (1); 431 for (parentsp = siblingp->parents; parentsp; 432 parentsp = parentsp->arc_parentlist) { 433 if (parentsp->arc_parentp->printflag) 434 return (1); 435 } 436 return (0); 437 } 438 439 440 /* 441 * check if the parents it passes time are *all* on 442 * the Elist in which case we do not pass the time 443 */ 444 static int 445 check_parents(nltype *siblingp) 446 { 447 arctype *parentsp; 448 if (!siblingp->parents) 449 return (1); 450 for (parentsp = siblingp->parents; parentsp; 451 parentsp = parentsp->arc_parentlist) { 452 if (!onlist(Elist, parentsp->arc_parentp->name)) 453 return (1); 454 } 455 return (0); 456 } 457 458 459 /* 460 * in one top to bottom pass over the topologically sorted namelist 461 * propagate: 462 * printflag as the union of parents' printflags 463 * propfraction as the sum of fractional parents' propfractions 464 * and while we're here, sum time for functions. 465 */ 466 static void 467 doflags() 468 { 469 int index; 470 nltype *childp; 471 nltype *oldhead; 472 473 oldhead = 0; 474 for (index = total_names - 1; index >= 0; index -= 1) { 475 childp = topsortnlp[index]; 476 /* 477 * if we haven't done this function or cycle, 478 * inherit things from parent. 479 * this way, we are linear in the number of arcs 480 * since we do all members of a cycle (and the 481 * cycle itself) as we hit the first member 482 * of the cycle. 483 */ 484 if (childp->cyclehead != oldhead) { 485 oldhead = childp->cyclehead; 486 inheritflags(childp); 487 } 488 #ifdef DEBUG 489 if (debug & PROPDEBUG) { 490 printf("[doflags] "); 491 printname(childp); 492 printf(" inherits printflag %d and propfraction %f\n", 493 childp->printflag, childp->propfraction); 494 } 495 #endif /* DEBUG */ 496 if (!childp->printflag) { 497 bool on_flist; 498 /* 499 * printflag is off 500 * it gets turned on by 501 * being on -f list, 502 * or there not being any -f list 503 * and not being on -e list. 504 */ 505 if (((on_flist = onlist(flist, childp->name)) != 0) || 506 (!fflag && !onlist(elist, childp->name))) { 507 if (on_flist || check_ancestors(childp)) 508 childp->printflag = TRUE; 509 } 510 } else { 511 /* 512 * this function has printing parents: 513 * maybe someone wants to shut it up 514 * by putting it on -e list. (but favor -f 515 * over -e) 516 */ 517 if ((!onlist(flist, childp->name)) && 518 onlist(elist, childp->name)) { 519 childp->printflag = FALSE; 520 } 521 } 522 if (childp->propfraction == 0.0) { 523 /* 524 * no parents to pass time to. 525 * collect time from children if 526 * its on -F list, 527 * or there isn't any -F list and its not 528 * on -E list. 529 */ 530 if (onlist(Flist, childp->name) || 531 (!Fflag && !onlist(Elist, childp->name))) { 532 childp->propfraction = 1.0; 533 } 534 } else { 535 /* 536 * it has parents to pass time to, 537 * but maybe someone wants to shut it up 538 * by putting it on -E list. (but favor -F 539 * over -E) 540 */ 541 if (!onlist(Flist, childp->name) && 542 onlist(Elist, childp->name)) { 543 if (check_parents(childp)) 544 childp->propfraction = 0.0; 545 } 546 } 547 childp->propself = childp->time * childp->propfraction; 548 printtime += childp->propself; 549 #ifdef DEBUG 550 if (debug & PROPDEBUG) { 551 printf("[doflags] "); 552 printname(childp); 553 printf(" ends up with printflag %d and " 554 "propfraction %f\n", 555 childp->printflag, childp->propfraction); 556 printf("time %f propself %f printtime %f\n", 557 childp->time, childp->propself, printtime); 558 } 559 #endif /* DEBUG */ 560 } 561 } 562 563 564 nltype ** 565 doarcs() 566 { 567 nltype *parentp, **timesortnlp; 568 arctype *arcp; 569 long i, index; 570 571 extern mod_info_t modules; 572 mod_info_t *mi; 573 574 /* 575 * initialize various things: 576 * zero out child times. 577 * count self-recursive calls. 578 * indicate that nothing is on cycles. 579 */ 580 for (mi = &modules; mi; mi = mi->next) { 581 for (parentp = mi->nl; parentp < mi->npe; parentp++) { 582 parentp->childtime = 0.0; 583 arcp = arclookup(parentp, parentp); 584 if (arcp != 0) { 585 parentp->ncall -= arcp->arc_count; 586 parentp->selfcalls = arcp->arc_count; 587 } else { 588 parentp->selfcalls = 0; 589 } 590 parentp->propfraction = 0.0; 591 parentp->propself = 0.0; 592 parentp->propchild = 0.0; 593 parentp->printflag = FALSE; 594 parentp->toporder = DFN_NAN; 595 parentp->cycleno = 0; 596 parentp->cyclehead = parentp; 597 parentp->cnext = 0; 598 599 /* 600 * Inspecting text space is valid only for 601 * the program executable. 602 */ 603 if (cflag && (mi == &modules)) { 604 findcalls( 605 parentp, 606 parentp->value, 607 parentp->value + parentp->sz); 608 } 609 } 610 } 611 612 /* 613 * topologically order things 614 * if any node is unnumbered, 615 * number it and any of its descendents. 616 */ 617 for (mi = &modules; mi; mi = mi->next) { 618 for (parentp = mi->nl; parentp < mi->npe; parentp++) { 619 if (parentp->toporder == DFN_NAN) { 620 dfn(parentp); 621 } 622 } 623 } 624 625 /* 626 * link together nodes on the same cycle 627 */ 628 cyclelink(); 629 /* 630 * Sort the symbol tables in reverse topological order 631 */ 632 topsortnlp = (nltype **) calloc(total_names, sizeof (nltype *)); 633 if (topsortnlp == (nltype **) 0) { 634 fprintf(stderr, 635 "[doarcs] ran out of memory for topo sorting\n"); 636 } 637 index = 0; 638 for (mi = &modules; mi; mi = mi->next) { 639 for (i = 0; i < mi->nname; i++) 640 topsortnlp[index++] = &(mi->nl[i]); 641 } 642 643 qsort(topsortnlp, total_names, sizeof (nltype *), 644 (int (*)(const void *, const void *))topcmp); 645 #ifdef DEBUG 646 if (debug & DFNDEBUG) { 647 printf("[doarcs] topological sort listing\n"); 648 for (index = 0; index < total_names; index += 1) { 649 printf("[doarcs] "); 650 printf("%d:", topsortnlp[ index ]->toporder); 651 printname(topsortnlp[ index ]); 652 printf("\n"); 653 } 654 } 655 #endif /* DEBUG */ 656 /* 657 * starting from the topological top, 658 * propagate print flags to children. 659 * also, calculate propagation fractions. 660 * this happens before time propagation 661 * since time propagation uses the fractions. 662 */ 663 doflags(); 664 /* 665 * starting from the topological bottom, 666 * propogate children times up to parents. 667 */ 668 dotime(); 669 /* 670 * Now, sort by propself + propchild. 671 * sorting both the regular function names 672 * and cycle headers. 673 */ 674 timesortnlp = (nltype **) calloc(total_names + ncycle, 675 sizeof (nltype *)); 676 if (timesortnlp == (nltype **) 0) { 677 fprintf(stderr, "%s: ran out of memory for sorting\n", whoami); 678 } 679 680 index = 0; 681 for (mi = &modules; mi; mi = mi->next) { 682 for (i = 0; i < mi->nname; i++) 683 timesortnlp[index++] = &(mi->nl[i]); 684 } 685 686 for (index = 1; index <= ncycle; index++) 687 timesortnlp[total_names+index-1] = &cyclenl[index]; 688 689 qsort(timesortnlp, total_names + ncycle, sizeof (nltype *), 690 (int(*)(const void *, const void *))totalcmp); 691 692 for (index = 0; index < total_names + ncycle; index++) 693 timesortnlp[index]->index = index + 1; 694 695 return (timesortnlp); 696 } 697