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 */
36void
37addarc(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 */
99nltype	**topsortnlp;
100
101static int
102topcmp(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
110static void
111timepropagate(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
198static void
199cycletime(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
222static void
223dotime(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
234static void
235cyclelink(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 */
356static void
357inheritflags(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 */
430static int
431check_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 */
449static int
450check_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 */
471static void
472doflags(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
570nltype **
571doarcs(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