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