17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate * CDDL HEADER START
37c478bd9Sstevel@tonic-gate *
47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the
57c478bd9Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only
67c478bd9Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance
77c478bd9Sstevel@tonic-gate * with the License.
87c478bd9Sstevel@tonic-gate *
97c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
107c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
117c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions
127c478bd9Sstevel@tonic-gate * and limitations under the License.
137c478bd9Sstevel@tonic-gate *
147c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
157c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
167c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
177c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
187c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
197c478bd9Sstevel@tonic-gate *
207c478bd9Sstevel@tonic-gate * CDDL HEADER END
217c478bd9Sstevel@tonic-gate */
2292ed1782Smike_s
237c478bd9Sstevel@tonic-gate /*
2492ed1782Smike_s * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
2592ed1782Smike_s * Use is subject to license terms.
267c478bd9Sstevel@tonic-gate */
277c478bd9Sstevel@tonic-gate
287c478bd9Sstevel@tonic-gate #include <stdlib.h>
297c478bd9Sstevel@tonic-gate #include "gprof.h"
307c478bd9Sstevel@tonic-gate
31*14448871SToomas Soome double printtime;
32*14448871SToomas Soome sztype total_names;
33*14448871SToomas Soome int ncycle;
34*14448871SToomas Soome nltype *cyclenl;
35*14448871SToomas Soome
367c478bd9Sstevel@tonic-gate /*
377c478bd9Sstevel@tonic-gate * add (or just increment) an arc
387c478bd9Sstevel@tonic-gate */
397c478bd9Sstevel@tonic-gate void
addarc(nltype * parentp,nltype * childp,actype count)407c478bd9Sstevel@tonic-gate addarc(nltype *parentp, nltype *childp, actype count)
417c478bd9Sstevel@tonic-gate {
427c478bd9Sstevel@tonic-gate arctype *arcp;
437c478bd9Sstevel@tonic-gate
447c478bd9Sstevel@tonic-gate #ifdef DEBUG
457c478bd9Sstevel@tonic-gate if (debug & TALLYDEBUG) {
4692ed1782Smike_s (void) printf("[addarc] %lld arcs from %s to %s\n",
477c478bd9Sstevel@tonic-gate count, parentp->name, childp->name);
487c478bd9Sstevel@tonic-gate }
497c478bd9Sstevel@tonic-gate #endif /* DEBUG */
507c478bd9Sstevel@tonic-gate arcp = arclookup(parentp, childp);
517c478bd9Sstevel@tonic-gate if (arcp != 0) {
527c478bd9Sstevel@tonic-gate /*
537c478bd9Sstevel@tonic-gate * a hit: just increment the count.
547c478bd9Sstevel@tonic-gate */
557c478bd9Sstevel@tonic-gate #ifdef DEBUG
567c478bd9Sstevel@tonic-gate if (!Dflag) {
577c478bd9Sstevel@tonic-gate if (debug & TALLYDEBUG) {
5892ed1782Smike_s (void) printf("[tally] hit %lld += %lld\n",
597c478bd9Sstevel@tonic-gate arcp->arc_count, count);
607c478bd9Sstevel@tonic-gate }
617c478bd9Sstevel@tonic-gate } else {
627c478bd9Sstevel@tonic-gate if (debug & TALLYDEBUG) {
6392ed1782Smike_s (void) printf("[tally] hit %lld -= %lld\n",
647c478bd9Sstevel@tonic-gate arcp->arc_count, count);
657c478bd9Sstevel@tonic-gate }
667c478bd9Sstevel@tonic-gate }
677c478bd9Sstevel@tonic-gate
687c478bd9Sstevel@tonic-gate #endif /* DEBUG */
697c478bd9Sstevel@tonic-gate if (!Dflag)
707c478bd9Sstevel@tonic-gate arcp->arc_count += count;
717c478bd9Sstevel@tonic-gate else {
727c478bd9Sstevel@tonic-gate arcp->arc_count -= count;
737c478bd9Sstevel@tonic-gate if (arcp->arc_count < 0)
747c478bd9Sstevel@tonic-gate arcp->arc_count = 0;
757c478bd9Sstevel@tonic-gate }
767c478bd9Sstevel@tonic-gate return;
777c478bd9Sstevel@tonic-gate }
787c478bd9Sstevel@tonic-gate arcp = (arctype *)calloc(1, sizeof (*arcp));
797c478bd9Sstevel@tonic-gate arcp->arc_parentp = parentp;
807c478bd9Sstevel@tonic-gate arcp->arc_childp = childp;
817c478bd9Sstevel@tonic-gate arcp->arc_count = count;
827c478bd9Sstevel@tonic-gate /*
837c478bd9Sstevel@tonic-gate * prepend this child to the children of this parent
847c478bd9Sstevel@tonic-gate */
857c478bd9Sstevel@tonic-gate arcp->arc_childlist = parentp->children;
867c478bd9Sstevel@tonic-gate parentp->children = arcp;
877c478bd9Sstevel@tonic-gate /*
887c478bd9Sstevel@tonic-gate * prepend this parent to the parents of this child
897c478bd9Sstevel@tonic-gate */
907c478bd9Sstevel@tonic-gate arcp->arc_parentlist = childp->parents;
917c478bd9Sstevel@tonic-gate childp->parents = arcp;
927c478bd9Sstevel@tonic-gate }
937c478bd9Sstevel@tonic-gate
947c478bd9Sstevel@tonic-gate /*
957c478bd9Sstevel@tonic-gate * the code below topologically sorts the graph (collapsing cycles),
967c478bd9Sstevel@tonic-gate * and propagates time bottom up and flags top down.
977c478bd9Sstevel@tonic-gate */
987c478bd9Sstevel@tonic-gate
997c478bd9Sstevel@tonic-gate /*
1007c478bd9Sstevel@tonic-gate * the topologically sorted name list pointers
1017c478bd9Sstevel@tonic-gate */
1027c478bd9Sstevel@tonic-gate nltype **topsortnlp;
1037c478bd9Sstevel@tonic-gate
1047c478bd9Sstevel@tonic-gate static int
topcmp(const void * arg1,const void * arg2)10592ed1782Smike_s topcmp(const void *arg1, const void *arg2)
1067c478bd9Sstevel@tonic-gate {
10792ed1782Smike_s nltype **npp1 = (nltype **)arg1;
10892ed1782Smike_s nltype **npp2 = (nltype **)arg2;
10992ed1782Smike_s
1107c478bd9Sstevel@tonic-gate return ((*npp1)->toporder - (*npp2)->toporder);
1117c478bd9Sstevel@tonic-gate }
1127c478bd9Sstevel@tonic-gate
1137c478bd9Sstevel@tonic-gate static void
timepropagate(nltype * parentp)1147c478bd9Sstevel@tonic-gate timepropagate(nltype *parentp)
1157c478bd9Sstevel@tonic-gate {
1167c478bd9Sstevel@tonic-gate arctype *arcp;
1177c478bd9Sstevel@tonic-gate nltype *childp;
1187c478bd9Sstevel@tonic-gate double share;
1197c478bd9Sstevel@tonic-gate double propshare;
1207c478bd9Sstevel@tonic-gate
1217c478bd9Sstevel@tonic-gate if (parentp->propfraction == 0.0) {
1227c478bd9Sstevel@tonic-gate return;
1237c478bd9Sstevel@tonic-gate }
1247c478bd9Sstevel@tonic-gate /*
1257c478bd9Sstevel@tonic-gate * gather time from children of this parent.
1267c478bd9Sstevel@tonic-gate */
1277c478bd9Sstevel@tonic-gate for (arcp = parentp->children; arcp; arcp = arcp->arc_childlist) {
1287c478bd9Sstevel@tonic-gate childp = arcp->arc_childp;
1297c478bd9Sstevel@tonic-gate if (arcp->arc_count == 0) {
1307c478bd9Sstevel@tonic-gate continue;
1317c478bd9Sstevel@tonic-gate }
1327c478bd9Sstevel@tonic-gate if (childp == parentp) {
1337c478bd9Sstevel@tonic-gate continue;
1347c478bd9Sstevel@tonic-gate }
1357c478bd9Sstevel@tonic-gate if (childp->propfraction == 0.0) {
1367c478bd9Sstevel@tonic-gate continue;
1377c478bd9Sstevel@tonic-gate }
1387c478bd9Sstevel@tonic-gate if (childp->cyclehead != childp) {
1397c478bd9Sstevel@tonic-gate if (parentp->cycleno == childp->cycleno) {
1407c478bd9Sstevel@tonic-gate continue;
1417c478bd9Sstevel@tonic-gate }
1427c478bd9Sstevel@tonic-gate if (parentp->toporder <= childp->toporder) {
14392ed1782Smike_s (void) fprintf(stderr,
1447c478bd9Sstevel@tonic-gate "[propagate] toporder botches\n");
1457c478bd9Sstevel@tonic-gate }
1467c478bd9Sstevel@tonic-gate childp = childp->cyclehead;
1477c478bd9Sstevel@tonic-gate } else {
1487c478bd9Sstevel@tonic-gate if (parentp->toporder <= childp->toporder) {
14992ed1782Smike_s (void) fprintf(stderr,
1507c478bd9Sstevel@tonic-gate "[propagate] toporder botches\n");
1517c478bd9Sstevel@tonic-gate continue;
1527c478bd9Sstevel@tonic-gate }
1537c478bd9Sstevel@tonic-gate }
1547c478bd9Sstevel@tonic-gate if (childp->ncall == 0) {
1557c478bd9Sstevel@tonic-gate continue;
1567c478bd9Sstevel@tonic-gate }
1577c478bd9Sstevel@tonic-gate /*
1587c478bd9Sstevel@tonic-gate * distribute time for this arc
1597c478bd9Sstevel@tonic-gate */
1607c478bd9Sstevel@tonic-gate arcp->arc_time = childp->time
1617c478bd9Sstevel@tonic-gate * (((double)arcp->arc_count) /
1627c478bd9Sstevel@tonic-gate ((double)childp->ncall));
1637c478bd9Sstevel@tonic-gate arcp->arc_childtime = childp->childtime
1647c478bd9Sstevel@tonic-gate * (((double)arcp->arc_count) /
1657c478bd9Sstevel@tonic-gate ((double)childp->ncall));
1667c478bd9Sstevel@tonic-gate share = arcp->arc_time + arcp->arc_childtime;
1677c478bd9Sstevel@tonic-gate parentp->childtime += share;
1687c478bd9Sstevel@tonic-gate /*
1697c478bd9Sstevel@tonic-gate * (1 - propfraction) gets lost along the way
1707c478bd9Sstevel@tonic-gate */
1717c478bd9Sstevel@tonic-gate propshare = parentp->propfraction * share;
1727c478bd9Sstevel@tonic-gate /*
1737c478bd9Sstevel@tonic-gate * fix things for printing
1747c478bd9Sstevel@tonic-gate */
1757c478bd9Sstevel@tonic-gate parentp->propchild += propshare;
1767c478bd9Sstevel@tonic-gate arcp->arc_time *= parentp->propfraction;
1777c478bd9Sstevel@tonic-gate arcp->arc_childtime *= parentp->propfraction;
1787c478bd9Sstevel@tonic-gate /*
1797c478bd9Sstevel@tonic-gate * add this share to the parent's cycle header, if any.
1807c478bd9Sstevel@tonic-gate */
1817c478bd9Sstevel@tonic-gate if (parentp->cyclehead != parentp) {
1827c478bd9Sstevel@tonic-gate parentp->cyclehead->childtime += share;
1837c478bd9Sstevel@tonic-gate parentp->cyclehead->propchild += propshare;
1847c478bd9Sstevel@tonic-gate }
1857c478bd9Sstevel@tonic-gate #ifdef DEBUG
1867c478bd9Sstevel@tonic-gate if (debug & PROPDEBUG) {
18792ed1782Smike_s (void) printf("[dotime] child \t");
1887c478bd9Sstevel@tonic-gate printname(childp);
18992ed1782Smike_s (void) printf(" with %f %f %lld/%lld\n",
1907c478bd9Sstevel@tonic-gate childp->time, childp->childtime,
1917c478bd9Sstevel@tonic-gate arcp->arc_count, childp->ncall);
19292ed1782Smike_s (void) printf("[dotime] parent\t");
1937c478bd9Sstevel@tonic-gate printname(parentp);
19492ed1782Smike_s (void) printf("\n[dotime] share %f\n", share);
1957c478bd9Sstevel@tonic-gate }
1967c478bd9Sstevel@tonic-gate #endif /* DEBUG */
1977c478bd9Sstevel@tonic-gate }
1987c478bd9Sstevel@tonic-gate }
1997c478bd9Sstevel@tonic-gate
2007c478bd9Sstevel@tonic-gate
2017c478bd9Sstevel@tonic-gate static void
cycletime(void)20292ed1782Smike_s cycletime(void)
2037c478bd9Sstevel@tonic-gate {
2047c478bd9Sstevel@tonic-gate int cycle;
2057c478bd9Sstevel@tonic-gate nltype *cyclenlp;
2067c478bd9Sstevel@tonic-gate nltype *childp;
2077c478bd9Sstevel@tonic-gate
2087c478bd9Sstevel@tonic-gate for (cycle = 1; cycle <= ncycle; cycle += 1) {
2097c478bd9Sstevel@tonic-gate cyclenlp = &cyclenl[cycle];
2107c478bd9Sstevel@tonic-gate for (childp = cyclenlp->cnext; childp; childp = childp->cnext) {
2117c478bd9Sstevel@tonic-gate if (childp->propfraction == 0.0) {
2127c478bd9Sstevel@tonic-gate /*
2137c478bd9Sstevel@tonic-gate * all members have the same propfraction
2147c478bd9Sstevel@tonic-gate * except those that were excluded with -E
2157c478bd9Sstevel@tonic-gate */
2167c478bd9Sstevel@tonic-gate continue;
2177c478bd9Sstevel@tonic-gate }
2187c478bd9Sstevel@tonic-gate cyclenlp->time += childp->time;
2197c478bd9Sstevel@tonic-gate }
2207c478bd9Sstevel@tonic-gate cyclenlp->propself = cyclenlp->propfraction * cyclenlp->time;
2217c478bd9Sstevel@tonic-gate }
2227c478bd9Sstevel@tonic-gate }
2237c478bd9Sstevel@tonic-gate
2247c478bd9Sstevel@tonic-gate
2257c478bd9Sstevel@tonic-gate static void
dotime(void)22692ed1782Smike_s dotime(void)
2277c478bd9Sstevel@tonic-gate {
2287c478bd9Sstevel@tonic-gate int index;
2297c478bd9Sstevel@tonic-gate
2307c478bd9Sstevel@tonic-gate cycletime();
2317c478bd9Sstevel@tonic-gate for (index = 0; index < total_names; index += 1) {
2327c478bd9Sstevel@tonic-gate timepropagate(topsortnlp[index]);
2337c478bd9Sstevel@tonic-gate }
2347c478bd9Sstevel@tonic-gate }
2357c478bd9Sstevel@tonic-gate
2367c478bd9Sstevel@tonic-gate
2377c478bd9Sstevel@tonic-gate static void
cyclelink(void)23892ed1782Smike_s cyclelink(void)
2397c478bd9Sstevel@tonic-gate {
24092ed1782Smike_s nltype *nlp;
24192ed1782Smike_s nltype *cyclenlp;
2427c478bd9Sstevel@tonic-gate int cycle;
2437c478bd9Sstevel@tonic-gate nltype *memberp;
2447c478bd9Sstevel@tonic-gate arctype *arcp;
2457c478bd9Sstevel@tonic-gate mod_info_t *mi;
2467c478bd9Sstevel@tonic-gate
2477c478bd9Sstevel@tonic-gate /*
2487c478bd9Sstevel@tonic-gate * Count the number of cycles, and initialize the cycle lists
2497c478bd9Sstevel@tonic-gate */
2507c478bd9Sstevel@tonic-gate ncycle = 0;
2517c478bd9Sstevel@tonic-gate for (mi = &modules; mi; mi = mi->next) {
2527c478bd9Sstevel@tonic-gate for (nlp = mi->nl; nlp < mi->npe; nlp++) {
2537c478bd9Sstevel@tonic-gate /*
2547c478bd9Sstevel@tonic-gate * this is how you find unattached cycles
2557c478bd9Sstevel@tonic-gate */
2567c478bd9Sstevel@tonic-gate if (nlp->cyclehead == nlp && nlp->cnext != 0) {
2577c478bd9Sstevel@tonic-gate ncycle += 1;
2587c478bd9Sstevel@tonic-gate }
2597c478bd9Sstevel@tonic-gate }
2607c478bd9Sstevel@tonic-gate }
2617c478bd9Sstevel@tonic-gate
2627c478bd9Sstevel@tonic-gate /*
2637c478bd9Sstevel@tonic-gate * cyclenl is indexed by cycle number:
2647c478bd9Sstevel@tonic-gate * i.e. it is origin 1, not origin 0.
2657c478bd9Sstevel@tonic-gate */
2667c478bd9Sstevel@tonic-gate cyclenl = (nltype *) calloc(ncycle + 1, sizeof (nltype));
2677c478bd9Sstevel@tonic-gate if (cyclenl == 0) {
26892ed1782Smike_s (void) fprintf(stderr,
2697c478bd9Sstevel@tonic-gate "%s: No room for %d bytes of cycle headers\n",
2707c478bd9Sstevel@tonic-gate whoami, (ncycle + 1) * sizeof (nltype));
2717c478bd9Sstevel@tonic-gate done();
2727c478bd9Sstevel@tonic-gate }
2737c478bd9Sstevel@tonic-gate
2747c478bd9Sstevel@tonic-gate /*
2757c478bd9Sstevel@tonic-gate * now link cycles to true cycleheads,
2767c478bd9Sstevel@tonic-gate * number them, accumulate the data for the cycle
2777c478bd9Sstevel@tonic-gate */
2787c478bd9Sstevel@tonic-gate cycle = 0;
2797c478bd9Sstevel@tonic-gate for (mi = &modules; mi; mi = mi->next) {
2807c478bd9Sstevel@tonic-gate for (nlp = mi->nl; nlp < mi->npe; nlp++) {
2817c478bd9Sstevel@tonic-gate if (!(nlp->cyclehead == nlp && nlp->cnext != 0)) {
2827c478bd9Sstevel@tonic-gate continue;
2837c478bd9Sstevel@tonic-gate }
2847c478bd9Sstevel@tonic-gate cycle += 1;
2857c478bd9Sstevel@tonic-gate cyclenlp = &cyclenl[cycle];
2867c478bd9Sstevel@tonic-gate cyclenlp->name = 0; /* the name */
2877c478bd9Sstevel@tonic-gate cyclenlp->value = 0; /* pc entry point */
2887c478bd9Sstevel@tonic-gate cyclenlp->time = 0.0; /* ticks in routine */
2897c478bd9Sstevel@tonic-gate cyclenlp->childtime = 0.0; /* cumulative ticks */
2907c478bd9Sstevel@tonic-gate /* in children */
2917c478bd9Sstevel@tonic-gate cyclenlp->ncall = 0; /* how many times */
2927c478bd9Sstevel@tonic-gate /* called */
2937c478bd9Sstevel@tonic-gate cyclenlp->selfcalls = 0; /* how many calls */
2947c478bd9Sstevel@tonic-gate /* to self */
2957c478bd9Sstevel@tonic-gate cyclenlp->propfraction = 0.0; /* what % of time */
2967c478bd9Sstevel@tonic-gate /* propagates */
2977c478bd9Sstevel@tonic-gate cyclenlp->propself = 0.0; /* how much self time */
2987c478bd9Sstevel@tonic-gate /* propagates */
2997c478bd9Sstevel@tonic-gate cyclenlp->propchild = 0.0; /* how much of child */
3007c478bd9Sstevel@tonic-gate /* time propagates */
3017c478bd9Sstevel@tonic-gate cyclenlp->printflag = TRUE; /* should this be */
3027c478bd9Sstevel@tonic-gate /* printed? */
3037c478bd9Sstevel@tonic-gate cyclenlp->index = 0; /* index in the */
3047c478bd9Sstevel@tonic-gate /* graph list */
3057c478bd9Sstevel@tonic-gate cyclenlp->toporder = DFN_NAN; /* graph call chain */
3067c478bd9Sstevel@tonic-gate /* top-sort order */
3077c478bd9Sstevel@tonic-gate cyclenlp->cycleno = cycle; /* internal number */
3087c478bd9Sstevel@tonic-gate /* of cycle on */
3097c478bd9Sstevel@tonic-gate cyclenlp->cyclehead = cyclenlp; /* head of cycle ptr */
3107c478bd9Sstevel@tonic-gate cyclenlp->cnext = nlp; /* ptr to next member */
3117c478bd9Sstevel@tonic-gate /* of cycle */
3127c478bd9Sstevel@tonic-gate cyclenlp->parents = 0; /* caller arcs list */
3137c478bd9Sstevel@tonic-gate cyclenlp->children = 0; /* callee arcs list */
3147c478bd9Sstevel@tonic-gate #ifdef DEBUG
3157c478bd9Sstevel@tonic-gate if (debug & CYCLEDEBUG) {
31692ed1782Smike_s (void) printf("[cyclelink] ");
3177c478bd9Sstevel@tonic-gate printname(nlp);
31892ed1782Smike_s (void) printf(" is the head of cycle %d\n",
31992ed1782Smike_s cycle);
3207c478bd9Sstevel@tonic-gate }
3217c478bd9Sstevel@tonic-gate #endif /* DEBUG */
3227c478bd9Sstevel@tonic-gate /*
3237c478bd9Sstevel@tonic-gate * link members to cycle header
3247c478bd9Sstevel@tonic-gate */
3257c478bd9Sstevel@tonic-gate for (memberp = nlp; memberp; memberp = memberp->cnext) {
3267c478bd9Sstevel@tonic-gate memberp->cycleno = cycle;
3277c478bd9Sstevel@tonic-gate memberp->cyclehead = cyclenlp;
3287c478bd9Sstevel@tonic-gate }
3297c478bd9Sstevel@tonic-gate /*
3307c478bd9Sstevel@tonic-gate * count calls from outside the cycle
3317c478bd9Sstevel@tonic-gate * and those among cycle members
3327c478bd9Sstevel@tonic-gate */
3337c478bd9Sstevel@tonic-gate for (memberp = nlp; memberp; memberp = memberp->cnext) {
3347c478bd9Sstevel@tonic-gate for (arcp = memberp->parents; arcp;
3357c478bd9Sstevel@tonic-gate arcp = arcp->arc_parentlist) {
3367c478bd9Sstevel@tonic-gate if (arcp->arc_parentp == memberp)
3377c478bd9Sstevel@tonic-gate continue;
3387c478bd9Sstevel@tonic-gate
3397c478bd9Sstevel@tonic-gate if (arcp->arc_parentp->cycleno ==
340*14448871SToomas Soome cycle) {
341*14448871SToomas Soome cyclenlp->selfcalls +=
342*14448871SToomas Soome arcp->arc_count;
343*14448871SToomas Soome } else {
344*14448871SToomas Soome cyclenlp->ncall +=
345*14448871SToomas Soome arcp->arc_count;
346*14448871SToomas Soome }
3477c478bd9Sstevel@tonic-gate }
3487c478bd9Sstevel@tonic-gate }
3497c478bd9Sstevel@tonic-gate }
3507c478bd9Sstevel@tonic-gate }
3517c478bd9Sstevel@tonic-gate }
3527c478bd9Sstevel@tonic-gate
3537c478bd9Sstevel@tonic-gate
3547c478bd9Sstevel@tonic-gate /*
3557c478bd9Sstevel@tonic-gate * check if any parent of this child
3567c478bd9Sstevel@tonic-gate * (or outside parents of this cycle)
3577c478bd9Sstevel@tonic-gate * have their print flags on and set the
3587c478bd9Sstevel@tonic-gate * print flag of the child (cycle) appropriately.
3597c478bd9Sstevel@tonic-gate * similarly, deal with propagation fractions from parents.
3607c478bd9Sstevel@tonic-gate */
3617c478bd9Sstevel@tonic-gate static void
inheritflags(nltype * childp)3627c478bd9Sstevel@tonic-gate inheritflags(nltype *childp)
3637c478bd9Sstevel@tonic-gate {
3647c478bd9Sstevel@tonic-gate nltype *headp;
3657c478bd9Sstevel@tonic-gate arctype *arcp;
3667c478bd9Sstevel@tonic-gate nltype *parentp;
3677c478bd9Sstevel@tonic-gate nltype *memp;
3687c478bd9Sstevel@tonic-gate
3697c478bd9Sstevel@tonic-gate headp = childp->cyclehead;
3707c478bd9Sstevel@tonic-gate if (childp == headp) {
3717c478bd9Sstevel@tonic-gate /*
3727c478bd9Sstevel@tonic-gate * just a regular child, check its parents
3737c478bd9Sstevel@tonic-gate */
3747c478bd9Sstevel@tonic-gate childp->printflag = FALSE;
3757c478bd9Sstevel@tonic-gate childp->propfraction = 0.0;
3767c478bd9Sstevel@tonic-gate for (arcp = childp->parents; arcp;
3777c478bd9Sstevel@tonic-gate arcp = arcp->arc_parentlist) {
3787c478bd9Sstevel@tonic-gate parentp = arcp->arc_parentp;
3797c478bd9Sstevel@tonic-gate if (childp == parentp) {
3807c478bd9Sstevel@tonic-gate continue;
3817c478bd9Sstevel@tonic-gate }
3827c478bd9Sstevel@tonic-gate childp->printflag |= parentp->printflag;
3837c478bd9Sstevel@tonic-gate /*
3847c478bd9Sstevel@tonic-gate * if the child was never actually called
3857c478bd9Sstevel@tonic-gate * (e.g. this arc is static (and all others
3867c478bd9Sstevel@tonic-gate * are, too)) no time propagates along this arc.
3877c478bd9Sstevel@tonic-gate */
3887c478bd9Sstevel@tonic-gate if (childp->ncall) {
3897c478bd9Sstevel@tonic-gate childp->propfraction += parentp->propfraction
3907c478bd9Sstevel@tonic-gate * (((double)arcp->arc_count)
3917c478bd9Sstevel@tonic-gate / ((double)childp->ncall));
3927c478bd9Sstevel@tonic-gate }
3937c478bd9Sstevel@tonic-gate }
3947c478bd9Sstevel@tonic-gate } else {
3957c478bd9Sstevel@tonic-gate /*
3967c478bd9Sstevel@tonic-gate * its a member of a cycle, look at all parents from
3977c478bd9Sstevel@tonic-gate * outside the cycle
3987c478bd9Sstevel@tonic-gate */
3997c478bd9Sstevel@tonic-gate headp->printflag = FALSE;
4007c478bd9Sstevel@tonic-gate headp->propfraction = 0.0;
4017c478bd9Sstevel@tonic-gate for (memp = headp->cnext; memp; memp = memp->cnext) {
4027c478bd9Sstevel@tonic-gate for (arcp = memp->parents; arcp;
4037c478bd9Sstevel@tonic-gate arcp = arcp->arc_parentlist) {
4047c478bd9Sstevel@tonic-gate if (arcp->arc_parentp->cyclehead == headp) {
4057c478bd9Sstevel@tonic-gate continue;
4067c478bd9Sstevel@tonic-gate }
4077c478bd9Sstevel@tonic-gate parentp = arcp->arc_parentp;
4087c478bd9Sstevel@tonic-gate headp->printflag |= parentp->printflag;
4097c478bd9Sstevel@tonic-gate /*
4107c478bd9Sstevel@tonic-gate * if the cycle was never actually called
4117c478bd9Sstevel@tonic-gate * (e.g. this arc is static (and all
4127c478bd9Sstevel@tonic-gate * others are, too)) no time propagates
4137c478bd9Sstevel@tonic-gate * along this arc.
4147c478bd9Sstevel@tonic-gate */
4157c478bd9Sstevel@tonic-gate if (headp->ncall) {
4167c478bd9Sstevel@tonic-gate headp->propfraction +=
4177c478bd9Sstevel@tonic-gate parentp->propfraction
4187c478bd9Sstevel@tonic-gate * (((double)arcp->arc_count)
4197c478bd9Sstevel@tonic-gate / ((double)headp->ncall));
4207c478bd9Sstevel@tonic-gate }
4217c478bd9Sstevel@tonic-gate }
4227c478bd9Sstevel@tonic-gate }
4237c478bd9Sstevel@tonic-gate for (memp = headp; memp; memp = memp->cnext) {
4247c478bd9Sstevel@tonic-gate memp->printflag = headp->printflag;
4257c478bd9Sstevel@tonic-gate memp->propfraction = headp->propfraction;
4267c478bd9Sstevel@tonic-gate }
4277c478bd9Sstevel@tonic-gate }
4287c478bd9Sstevel@tonic-gate }
4297c478bd9Sstevel@tonic-gate
4307c478bd9Sstevel@tonic-gate
4317c478bd9Sstevel@tonic-gate /*
4327c478bd9Sstevel@tonic-gate * check here if *any* of its parents is printable
4337c478bd9Sstevel@tonic-gate * then return true else return false
4347c478bd9Sstevel@tonic-gate */
4357c478bd9Sstevel@tonic-gate static int
check_ancestors(nltype * siblingp)4367c478bd9Sstevel@tonic-gate check_ancestors(nltype *siblingp)
4377c478bd9Sstevel@tonic-gate {
4387c478bd9Sstevel@tonic-gate arctype *parentsp;
4397c478bd9Sstevel@tonic-gate if (!siblingp->parents)
4407c478bd9Sstevel@tonic-gate return (1);
4417c478bd9Sstevel@tonic-gate for (parentsp = siblingp->parents; parentsp;
4427c478bd9Sstevel@tonic-gate parentsp = parentsp->arc_parentlist) {
4437c478bd9Sstevel@tonic-gate if (parentsp->arc_parentp->printflag)
4447c478bd9Sstevel@tonic-gate return (1);
4457c478bd9Sstevel@tonic-gate }
4467c478bd9Sstevel@tonic-gate return (0);
4477c478bd9Sstevel@tonic-gate }
4487c478bd9Sstevel@tonic-gate
4497c478bd9Sstevel@tonic-gate
4507c478bd9Sstevel@tonic-gate /*
4517c478bd9Sstevel@tonic-gate * check if the parents it passes time are *all* on
4527c478bd9Sstevel@tonic-gate * the Elist in which case we do not pass the time
4537c478bd9Sstevel@tonic-gate */
4547c478bd9Sstevel@tonic-gate static int
check_parents(nltype * siblingp)4557c478bd9Sstevel@tonic-gate check_parents(nltype *siblingp)
4567c478bd9Sstevel@tonic-gate {
4577c478bd9Sstevel@tonic-gate arctype *parentsp;
4587c478bd9Sstevel@tonic-gate if (!siblingp->parents)
4597c478bd9Sstevel@tonic-gate return (1);
4607c478bd9Sstevel@tonic-gate for (parentsp = siblingp->parents; parentsp;
4617c478bd9Sstevel@tonic-gate parentsp = parentsp->arc_parentlist) {
4627c478bd9Sstevel@tonic-gate if (!onlist(Elist, parentsp->arc_parentp->name))
4637c478bd9Sstevel@tonic-gate return (1);
4647c478bd9Sstevel@tonic-gate }
4657c478bd9Sstevel@tonic-gate return (0);
4667c478bd9Sstevel@tonic-gate }
4677c478bd9Sstevel@tonic-gate
4687c478bd9Sstevel@tonic-gate
4697c478bd9Sstevel@tonic-gate /*
4707c478bd9Sstevel@tonic-gate * in one top to bottom pass over the topologically sorted namelist
4717c478bd9Sstevel@tonic-gate * propagate:
4727c478bd9Sstevel@tonic-gate * printflag as the union of parents' printflags
4737c478bd9Sstevel@tonic-gate * propfraction as the sum of fractional parents' propfractions
4747c478bd9Sstevel@tonic-gate * and while we're here, sum time for functions.
4757c478bd9Sstevel@tonic-gate */
4767c478bd9Sstevel@tonic-gate static void
doflags(void)47792ed1782Smike_s doflags(void)
4787c478bd9Sstevel@tonic-gate {
4797c478bd9Sstevel@tonic-gate int index;
4807c478bd9Sstevel@tonic-gate nltype *childp;
4817c478bd9Sstevel@tonic-gate nltype *oldhead;
4827c478bd9Sstevel@tonic-gate
4837c478bd9Sstevel@tonic-gate oldhead = 0;
4847c478bd9Sstevel@tonic-gate for (index = total_names - 1; index >= 0; index -= 1) {
4857c478bd9Sstevel@tonic-gate childp = topsortnlp[index];
4867c478bd9Sstevel@tonic-gate /*
4877c478bd9Sstevel@tonic-gate * if we haven't done this function or cycle,
4887c478bd9Sstevel@tonic-gate * inherit things from parent.
4897c478bd9Sstevel@tonic-gate * this way, we are linear in the number of arcs
4907c478bd9Sstevel@tonic-gate * since we do all members of a cycle (and the
4917c478bd9Sstevel@tonic-gate * cycle itself) as we hit the first member
4927c478bd9Sstevel@tonic-gate * of the cycle.
4937c478bd9Sstevel@tonic-gate */
4947c478bd9Sstevel@tonic-gate if (childp->cyclehead != oldhead) {
4957c478bd9Sstevel@tonic-gate oldhead = childp->cyclehead;
4967c478bd9Sstevel@tonic-gate inheritflags(childp);
4977c478bd9Sstevel@tonic-gate }
4987c478bd9Sstevel@tonic-gate #ifdef DEBUG
4997c478bd9Sstevel@tonic-gate if (debug & PROPDEBUG) {
50092ed1782Smike_s (void) printf("[doflags] ");
5017c478bd9Sstevel@tonic-gate printname(childp);
50292ed1782Smike_s (void) printf(
50392ed1782Smike_s " inherits printflag %d and propfraction %f\n",
5047c478bd9Sstevel@tonic-gate childp->printflag, childp->propfraction);
5057c478bd9Sstevel@tonic-gate }
5067c478bd9Sstevel@tonic-gate #endif /* DEBUG */
5077c478bd9Sstevel@tonic-gate if (!childp->printflag) {
5087c478bd9Sstevel@tonic-gate bool on_flist;
5097c478bd9Sstevel@tonic-gate /*
5107c478bd9Sstevel@tonic-gate * printflag is off
5117c478bd9Sstevel@tonic-gate * it gets turned on by
5127c478bd9Sstevel@tonic-gate * being on -f list,
5137c478bd9Sstevel@tonic-gate * or there not being any -f list
5147c478bd9Sstevel@tonic-gate * and not being on -e list.
5157c478bd9Sstevel@tonic-gate */
5167c478bd9Sstevel@tonic-gate if (((on_flist = onlist(flist, childp->name)) != 0) ||
5177c478bd9Sstevel@tonic-gate (!fflag && !onlist(elist, childp->name))) {
5187c478bd9Sstevel@tonic-gate if (on_flist || check_ancestors(childp))
5197c478bd9Sstevel@tonic-gate childp->printflag = TRUE;
5207c478bd9Sstevel@tonic-gate }
5217c478bd9Sstevel@tonic-gate } else {
5227c478bd9Sstevel@tonic-gate /*
5237c478bd9Sstevel@tonic-gate * this function has printing parents:
5247c478bd9Sstevel@tonic-gate * maybe someone wants to shut it up
5257c478bd9Sstevel@tonic-gate * by putting it on -e list. (but favor -f
5267c478bd9Sstevel@tonic-gate * over -e)
5277c478bd9Sstevel@tonic-gate */
5287c478bd9Sstevel@tonic-gate if ((!onlist(flist, childp->name)) &&
5297c478bd9Sstevel@tonic-gate onlist(elist, childp->name)) {
5307c478bd9Sstevel@tonic-gate childp->printflag = FALSE;
5317c478bd9Sstevel@tonic-gate }
5327c478bd9Sstevel@tonic-gate }
5337c478bd9Sstevel@tonic-gate if (childp->propfraction == 0.0) {
5347c478bd9Sstevel@tonic-gate /*
5357c478bd9Sstevel@tonic-gate * no parents to pass time to.
5367c478bd9Sstevel@tonic-gate * collect time from children if
5377c478bd9Sstevel@tonic-gate * its on -F list,
5387c478bd9Sstevel@tonic-gate * or there isn't any -F list and its not
5397c478bd9Sstevel@tonic-gate * on -E list.
5407c478bd9Sstevel@tonic-gate */
5417c478bd9Sstevel@tonic-gate if (onlist(Flist, childp->name) ||
5427c478bd9Sstevel@tonic-gate (!Fflag && !onlist(Elist, childp->name))) {
5437c478bd9Sstevel@tonic-gate childp->propfraction = 1.0;
5447c478bd9Sstevel@tonic-gate }
5457c478bd9Sstevel@tonic-gate } else {
5467c478bd9Sstevel@tonic-gate /*
5477c478bd9Sstevel@tonic-gate * it has parents to pass time to,
5487c478bd9Sstevel@tonic-gate * but maybe someone wants to shut it up
5497c478bd9Sstevel@tonic-gate * by putting it on -E list. (but favor -F
5507c478bd9Sstevel@tonic-gate * over -E)
5517c478bd9Sstevel@tonic-gate */
5527c478bd9Sstevel@tonic-gate if (!onlist(Flist, childp->name) &&
5537c478bd9Sstevel@tonic-gate onlist(Elist, childp->name)) {
5547c478bd9Sstevel@tonic-gate if (check_parents(childp))
5557c478bd9Sstevel@tonic-gate childp->propfraction = 0.0;
5567c478bd9Sstevel@tonic-gate }
5577c478bd9Sstevel@tonic-gate }
5587c478bd9Sstevel@tonic-gate childp->propself = childp->time * childp->propfraction;
5597c478bd9Sstevel@tonic-gate printtime += childp->propself;
5607c478bd9Sstevel@tonic-gate #ifdef DEBUG
5617c478bd9Sstevel@tonic-gate if (debug & PROPDEBUG) {
56292ed1782Smike_s (void) printf("[doflags] ");
5637c478bd9Sstevel@tonic-gate printname(childp);
56492ed1782Smike_s (void) printf(" ends up with printflag %d and "
5657c478bd9Sstevel@tonic-gate "propfraction %f\n",
5667c478bd9Sstevel@tonic-gate childp->printflag, childp->propfraction);
56792ed1782Smike_s (void) printf("time %f propself %f printtime %f\n",
5687c478bd9Sstevel@tonic-gate childp->time, childp->propself, printtime);
5697c478bd9Sstevel@tonic-gate }
5707c478bd9Sstevel@tonic-gate #endif /* DEBUG */
5717c478bd9Sstevel@tonic-gate }
5727c478bd9Sstevel@tonic-gate }
5737c478bd9Sstevel@tonic-gate
5747c478bd9Sstevel@tonic-gate
5757c478bd9Sstevel@tonic-gate nltype **
doarcs(void)57692ed1782Smike_s doarcs(void)
5777c478bd9Sstevel@tonic-gate {
5787c478bd9Sstevel@tonic-gate nltype *parentp, **timesortnlp;
5797c478bd9Sstevel@tonic-gate arctype *arcp;
5807c478bd9Sstevel@tonic-gate long i, index;
5817c478bd9Sstevel@tonic-gate
5827c478bd9Sstevel@tonic-gate extern mod_info_t modules;
5837c478bd9Sstevel@tonic-gate mod_info_t *mi;
5847c478bd9Sstevel@tonic-gate
5857c478bd9Sstevel@tonic-gate /*
5867c478bd9Sstevel@tonic-gate * initialize various things:
5877c478bd9Sstevel@tonic-gate * zero out child times.
5887c478bd9Sstevel@tonic-gate * count self-recursive calls.
5897c478bd9Sstevel@tonic-gate * indicate that nothing is on cycles.
5907c478bd9Sstevel@tonic-gate */
5917c478bd9Sstevel@tonic-gate for (mi = &modules; mi; mi = mi->next) {
5927c478bd9Sstevel@tonic-gate for (parentp = mi->nl; parentp < mi->npe; parentp++) {
5937c478bd9Sstevel@tonic-gate parentp->childtime = 0.0;
5947c478bd9Sstevel@tonic-gate arcp = arclookup(parentp, parentp);
5957c478bd9Sstevel@tonic-gate if (arcp != 0) {
5967c478bd9Sstevel@tonic-gate parentp->ncall -= arcp->arc_count;
5977c478bd9Sstevel@tonic-gate parentp->selfcalls = arcp->arc_count;
5987c478bd9Sstevel@tonic-gate } else {
5997c478bd9Sstevel@tonic-gate parentp->selfcalls = 0;
6007c478bd9Sstevel@tonic-gate }
6017c478bd9Sstevel@tonic-gate parentp->propfraction = 0.0;
6027c478bd9Sstevel@tonic-gate parentp->propself = 0.0;
6037c478bd9Sstevel@tonic-gate parentp->propchild = 0.0;
6047c478bd9Sstevel@tonic-gate parentp->printflag = FALSE;
6057c478bd9Sstevel@tonic-gate parentp->toporder = DFN_NAN;
6067c478bd9Sstevel@tonic-gate parentp->cycleno = 0;
6077c478bd9Sstevel@tonic-gate parentp->cyclehead = parentp;
6087c478bd9Sstevel@tonic-gate parentp->cnext = 0;
6097c478bd9Sstevel@tonic-gate
6107c478bd9Sstevel@tonic-gate /*
6117c478bd9Sstevel@tonic-gate * Inspecting text space is valid only for
6127c478bd9Sstevel@tonic-gate * the program executable.
6137c478bd9Sstevel@tonic-gate */
6147c478bd9Sstevel@tonic-gate if (cflag && (mi == &modules)) {
615*14448871SToomas Soome findcalls(parentp, parentp->value,
616*14448871SToomas Soome parentp->value + parentp->sz);
6177c478bd9Sstevel@tonic-gate }
6187c478bd9Sstevel@tonic-gate }
6197c478bd9Sstevel@tonic-gate }
6207c478bd9Sstevel@tonic-gate
6217c478bd9Sstevel@tonic-gate /*
6227c478bd9Sstevel@tonic-gate * topologically order things
6237c478bd9Sstevel@tonic-gate * if any node is unnumbered,
6247c478bd9Sstevel@tonic-gate * number it and any of its descendents.
6257c478bd9Sstevel@tonic-gate */
6267c478bd9Sstevel@tonic-gate for (mi = &modules; mi; mi = mi->next) {
6277c478bd9Sstevel@tonic-gate for (parentp = mi->nl; parentp < mi->npe; parentp++) {
6287c478bd9Sstevel@tonic-gate if (parentp->toporder == DFN_NAN) {
6297c478bd9Sstevel@tonic-gate dfn(parentp);
6307c478bd9Sstevel@tonic-gate }
6317c478bd9Sstevel@tonic-gate }
6327c478bd9Sstevel@tonic-gate }
6337c478bd9Sstevel@tonic-gate
6347c478bd9Sstevel@tonic-gate /*
6357c478bd9Sstevel@tonic-gate * link together nodes on the same cycle
6367c478bd9Sstevel@tonic-gate */
6377c478bd9Sstevel@tonic-gate cyclelink();
6387c478bd9Sstevel@tonic-gate /*
6397c478bd9Sstevel@tonic-gate * Sort the symbol tables in reverse topological order
6407c478bd9Sstevel@tonic-gate */
6417c478bd9Sstevel@tonic-gate topsortnlp = (nltype **) calloc(total_names, sizeof (nltype *));
6427c478bd9Sstevel@tonic-gate if (topsortnlp == (nltype **) 0) {
64392ed1782Smike_s (void) fprintf(stderr,
6447c478bd9Sstevel@tonic-gate "[doarcs] ran out of memory for topo sorting\n");
6457c478bd9Sstevel@tonic-gate }
6467c478bd9Sstevel@tonic-gate index = 0;
6477c478bd9Sstevel@tonic-gate for (mi = &modules; mi; mi = mi->next) {
6487c478bd9Sstevel@tonic-gate for (i = 0; i < mi->nname; i++)
649*14448871SToomas Soome topsortnlp[index++] = &(mi->nl[i]);
6507c478bd9Sstevel@tonic-gate }
6517c478bd9Sstevel@tonic-gate
65292ed1782Smike_s qsort(topsortnlp, total_names, sizeof (nltype *), topcmp);
6537c478bd9Sstevel@tonic-gate #ifdef DEBUG
6547c478bd9Sstevel@tonic-gate if (debug & DFNDEBUG) {
65592ed1782Smike_s (void) printf("[doarcs] topological sort listing\n");
6567c478bd9Sstevel@tonic-gate for (index = 0; index < total_names; index += 1) {
65792ed1782Smike_s (void) printf("[doarcs] ");
65892ed1782Smike_s (void) printf("%d:", topsortnlp[ index ]->toporder);
6597c478bd9Sstevel@tonic-gate printname(topsortnlp[ index ]);
66092ed1782Smike_s (void) printf("\n");
6617c478bd9Sstevel@tonic-gate }
6627c478bd9Sstevel@tonic-gate }
6637c478bd9Sstevel@tonic-gate #endif /* DEBUG */
6647c478bd9Sstevel@tonic-gate /*
6657c478bd9Sstevel@tonic-gate * starting from the topological top,
6667c478bd9Sstevel@tonic-gate * propagate print flags to children.
6677c478bd9Sstevel@tonic-gate * also, calculate propagation fractions.
6687c478bd9Sstevel@tonic-gate * this happens before time propagation
6697c478bd9Sstevel@tonic-gate * since time propagation uses the fractions.
6707c478bd9Sstevel@tonic-gate */
6717c478bd9Sstevel@tonic-gate doflags();
6727c478bd9Sstevel@tonic-gate /*
6737c478bd9Sstevel@tonic-gate * starting from the topological bottom,
6747c478bd9Sstevel@tonic-gate * propogate children times up to parents.
6757c478bd9Sstevel@tonic-gate */
6767c478bd9Sstevel@tonic-gate dotime();
6777c478bd9Sstevel@tonic-gate /*
6787c478bd9Sstevel@tonic-gate * Now, sort by propself + propchild.
6797c478bd9Sstevel@tonic-gate * sorting both the regular function names
6807c478bd9Sstevel@tonic-gate * and cycle headers.
6817c478bd9Sstevel@tonic-gate */
6827c478bd9Sstevel@tonic-gate timesortnlp = (nltype **) calloc(total_names + ncycle,
683*14448871SToomas Soome sizeof (nltype *));
6847c478bd9Sstevel@tonic-gate if (timesortnlp == (nltype **) 0) {
68592ed1782Smike_s (void) fprintf(stderr,
68692ed1782Smike_s "%s: ran out of memory for sorting\n", whoami);
6877c478bd9Sstevel@tonic-gate }
6887c478bd9Sstevel@tonic-gate
6897c478bd9Sstevel@tonic-gate index = 0;
6907c478bd9Sstevel@tonic-gate for (mi = &modules; mi; mi = mi->next) {
6917c478bd9Sstevel@tonic-gate for (i = 0; i < mi->nname; i++)
692*14448871SToomas Soome timesortnlp[index++] = &(mi->nl[i]);
6937c478bd9Sstevel@tonic-gate }
6947c478bd9Sstevel@tonic-gate
6957c478bd9Sstevel@tonic-gate for (index = 1; index <= ncycle; index++)
6967c478bd9Sstevel@tonic-gate timesortnlp[total_names+index-1] = &cyclenl[index];
6977c478bd9Sstevel@tonic-gate
69892ed1782Smike_s qsort(timesortnlp, total_names + ncycle, sizeof (nltype *), totalcmp);
6997c478bd9Sstevel@tonic-gate
7007c478bd9Sstevel@tonic-gate for (index = 0; index < total_names + ncycle; index++)
7017c478bd9Sstevel@tonic-gate timesortnlp[index]->index = index + 1;
7027c478bd9Sstevel@tonic-gate
7037c478bd9Sstevel@tonic-gate return (timesortnlp);
7047c478bd9Sstevel@tonic-gate }
705