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