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 */ 22*92ed1782Smike_s 237c478bd9Sstevel@tonic-gate /* 24*92ed1782Smike_s * Copyright 2005 Sun Microsystems, Inc. All rights reserved. 25*92ed1782Smike_s * Use is subject to license terms. 267c478bd9Sstevel@tonic-gate */ 277c478bd9Sstevel@tonic-gate 287c478bd9Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI" 297c478bd9Sstevel@tonic-gate 307c478bd9Sstevel@tonic-gate #include <stdlib.h> 317c478bd9Sstevel@tonic-gate #include "gprof.h" 327c478bd9Sstevel@tonic-gate 337c478bd9Sstevel@tonic-gate /* 347c478bd9Sstevel@tonic-gate * add (or just increment) an arc 357c478bd9Sstevel@tonic-gate */ 367c478bd9Sstevel@tonic-gate void 377c478bd9Sstevel@tonic-gate addarc(nltype *parentp, nltype *childp, actype count) 387c478bd9Sstevel@tonic-gate { 397c478bd9Sstevel@tonic-gate arctype *arcp; 407c478bd9Sstevel@tonic-gate 417c478bd9Sstevel@tonic-gate #ifdef DEBUG 427c478bd9Sstevel@tonic-gate if (debug & TALLYDEBUG) { 43*92ed1782Smike_s (void) printf("[addarc] %lld arcs from %s to %s\n", 447c478bd9Sstevel@tonic-gate count, parentp->name, childp->name); 457c478bd9Sstevel@tonic-gate } 467c478bd9Sstevel@tonic-gate #endif /* DEBUG */ 477c478bd9Sstevel@tonic-gate arcp = arclookup(parentp, childp); 487c478bd9Sstevel@tonic-gate if (arcp != 0) { 497c478bd9Sstevel@tonic-gate /* 507c478bd9Sstevel@tonic-gate * a hit: just increment the count. 517c478bd9Sstevel@tonic-gate */ 527c478bd9Sstevel@tonic-gate #ifdef DEBUG 537c478bd9Sstevel@tonic-gate if (!Dflag) { 547c478bd9Sstevel@tonic-gate if (debug & TALLYDEBUG) { 55*92ed1782Smike_s (void) printf("[tally] hit %lld += %lld\n", 567c478bd9Sstevel@tonic-gate arcp->arc_count, count); 577c478bd9Sstevel@tonic-gate } 587c478bd9Sstevel@tonic-gate } else { 597c478bd9Sstevel@tonic-gate if (debug & TALLYDEBUG) { 60*92ed1782Smike_s (void) printf("[tally] hit %lld -= %lld\n", 617c478bd9Sstevel@tonic-gate arcp->arc_count, count); 627c478bd9Sstevel@tonic-gate } 637c478bd9Sstevel@tonic-gate } 647c478bd9Sstevel@tonic-gate 657c478bd9Sstevel@tonic-gate #endif /* DEBUG */ 667c478bd9Sstevel@tonic-gate if (!Dflag) 677c478bd9Sstevel@tonic-gate arcp->arc_count += count; 687c478bd9Sstevel@tonic-gate else { 697c478bd9Sstevel@tonic-gate arcp->arc_count -= count; 707c478bd9Sstevel@tonic-gate if (arcp->arc_count < 0) 717c478bd9Sstevel@tonic-gate arcp->arc_count = 0; 727c478bd9Sstevel@tonic-gate } 737c478bd9Sstevel@tonic-gate return; 747c478bd9Sstevel@tonic-gate } 757c478bd9Sstevel@tonic-gate arcp = (arctype *)calloc(1, sizeof (*arcp)); 767c478bd9Sstevel@tonic-gate arcp->arc_parentp = parentp; 777c478bd9Sstevel@tonic-gate arcp->arc_childp = childp; 787c478bd9Sstevel@tonic-gate arcp->arc_count = count; 797c478bd9Sstevel@tonic-gate /* 807c478bd9Sstevel@tonic-gate * prepend this child to the children of this parent 817c478bd9Sstevel@tonic-gate */ 827c478bd9Sstevel@tonic-gate arcp->arc_childlist = parentp->children; 837c478bd9Sstevel@tonic-gate parentp->children = arcp; 847c478bd9Sstevel@tonic-gate /* 857c478bd9Sstevel@tonic-gate * prepend this parent to the parents of this child 867c478bd9Sstevel@tonic-gate */ 877c478bd9Sstevel@tonic-gate arcp->arc_parentlist = childp->parents; 887c478bd9Sstevel@tonic-gate childp->parents = arcp; 897c478bd9Sstevel@tonic-gate } 907c478bd9Sstevel@tonic-gate 917c478bd9Sstevel@tonic-gate /* 927c478bd9Sstevel@tonic-gate * the code below topologically sorts the graph (collapsing cycles), 937c478bd9Sstevel@tonic-gate * and propagates time bottom up and flags top down. 947c478bd9Sstevel@tonic-gate */ 957c478bd9Sstevel@tonic-gate 967c478bd9Sstevel@tonic-gate /* 977c478bd9Sstevel@tonic-gate * the topologically sorted name list pointers 987c478bd9Sstevel@tonic-gate */ 997c478bd9Sstevel@tonic-gate nltype **topsortnlp; 1007c478bd9Sstevel@tonic-gate 1017c478bd9Sstevel@tonic-gate static int 102*92ed1782Smike_s topcmp(const void *arg1, const void *arg2) 1037c478bd9Sstevel@tonic-gate { 104*92ed1782Smike_s nltype **npp1 = (nltype **)arg1; 105*92ed1782Smike_s nltype **npp2 = (nltype **)arg2; 106*92ed1782Smike_s 1077c478bd9Sstevel@tonic-gate return ((*npp1)->toporder - (*npp2)->toporder); 1087c478bd9Sstevel@tonic-gate } 1097c478bd9Sstevel@tonic-gate 1107c478bd9Sstevel@tonic-gate static void 1117c478bd9Sstevel@tonic-gate timepropagate(nltype *parentp) 1127c478bd9Sstevel@tonic-gate { 1137c478bd9Sstevel@tonic-gate arctype *arcp; 1147c478bd9Sstevel@tonic-gate nltype *childp; 1157c478bd9Sstevel@tonic-gate double share; 1167c478bd9Sstevel@tonic-gate double propshare; 1177c478bd9Sstevel@tonic-gate 1187c478bd9Sstevel@tonic-gate if (parentp->propfraction == 0.0) { 1197c478bd9Sstevel@tonic-gate return; 1207c478bd9Sstevel@tonic-gate } 1217c478bd9Sstevel@tonic-gate /* 1227c478bd9Sstevel@tonic-gate * gather time from children of this parent. 1237c478bd9Sstevel@tonic-gate */ 1247c478bd9Sstevel@tonic-gate for (arcp = parentp->children; arcp; arcp = arcp->arc_childlist) { 1257c478bd9Sstevel@tonic-gate childp = arcp->arc_childp; 1267c478bd9Sstevel@tonic-gate if (arcp->arc_count == 0) { 1277c478bd9Sstevel@tonic-gate continue; 1287c478bd9Sstevel@tonic-gate } 1297c478bd9Sstevel@tonic-gate if (childp == parentp) { 1307c478bd9Sstevel@tonic-gate continue; 1317c478bd9Sstevel@tonic-gate } 1327c478bd9Sstevel@tonic-gate if (childp->propfraction == 0.0) { 1337c478bd9Sstevel@tonic-gate continue; 1347c478bd9Sstevel@tonic-gate } 1357c478bd9Sstevel@tonic-gate if (childp->cyclehead != childp) { 1367c478bd9Sstevel@tonic-gate if (parentp->cycleno == childp->cycleno) { 1377c478bd9Sstevel@tonic-gate continue; 1387c478bd9Sstevel@tonic-gate } 1397c478bd9Sstevel@tonic-gate if (parentp->toporder <= childp->toporder) { 140*92ed1782Smike_s (void) fprintf(stderr, 1417c478bd9Sstevel@tonic-gate "[propagate] toporder botches\n"); 1427c478bd9Sstevel@tonic-gate } 1437c478bd9Sstevel@tonic-gate childp = childp->cyclehead; 1447c478bd9Sstevel@tonic-gate } else { 1457c478bd9Sstevel@tonic-gate if (parentp->toporder <= childp->toporder) { 146*92ed1782Smike_s (void) fprintf(stderr, 1477c478bd9Sstevel@tonic-gate "[propagate] toporder botches\n"); 1487c478bd9Sstevel@tonic-gate continue; 1497c478bd9Sstevel@tonic-gate } 1507c478bd9Sstevel@tonic-gate } 1517c478bd9Sstevel@tonic-gate if (childp->ncall == 0) { 1527c478bd9Sstevel@tonic-gate continue; 1537c478bd9Sstevel@tonic-gate } 1547c478bd9Sstevel@tonic-gate /* 1557c478bd9Sstevel@tonic-gate * distribute time for this arc 1567c478bd9Sstevel@tonic-gate */ 1577c478bd9Sstevel@tonic-gate arcp->arc_time = childp->time 1587c478bd9Sstevel@tonic-gate * (((double)arcp->arc_count) / 1597c478bd9Sstevel@tonic-gate ((double)childp->ncall)); 1607c478bd9Sstevel@tonic-gate arcp->arc_childtime = childp->childtime 1617c478bd9Sstevel@tonic-gate * (((double)arcp->arc_count) / 1627c478bd9Sstevel@tonic-gate ((double)childp->ncall)); 1637c478bd9Sstevel@tonic-gate share = arcp->arc_time + arcp->arc_childtime; 1647c478bd9Sstevel@tonic-gate parentp->childtime += share; 1657c478bd9Sstevel@tonic-gate /* 1667c478bd9Sstevel@tonic-gate * (1 - propfraction) gets lost along the way 1677c478bd9Sstevel@tonic-gate */ 1687c478bd9Sstevel@tonic-gate propshare = parentp->propfraction * share; 1697c478bd9Sstevel@tonic-gate /* 1707c478bd9Sstevel@tonic-gate * fix things for printing 1717c478bd9Sstevel@tonic-gate */ 1727c478bd9Sstevel@tonic-gate parentp->propchild += propshare; 1737c478bd9Sstevel@tonic-gate arcp->arc_time *= parentp->propfraction; 1747c478bd9Sstevel@tonic-gate arcp->arc_childtime *= parentp->propfraction; 1757c478bd9Sstevel@tonic-gate /* 1767c478bd9Sstevel@tonic-gate * add this share to the parent's cycle header, if any. 1777c478bd9Sstevel@tonic-gate */ 1787c478bd9Sstevel@tonic-gate if (parentp->cyclehead != parentp) { 1797c478bd9Sstevel@tonic-gate parentp->cyclehead->childtime += share; 1807c478bd9Sstevel@tonic-gate parentp->cyclehead->propchild += propshare; 1817c478bd9Sstevel@tonic-gate } 1827c478bd9Sstevel@tonic-gate #ifdef DEBUG 1837c478bd9Sstevel@tonic-gate if (debug & PROPDEBUG) { 184*92ed1782Smike_s (void) printf("[dotime] child \t"); 1857c478bd9Sstevel@tonic-gate printname(childp); 186*92ed1782Smike_s (void) printf(" with %f %f %lld/%lld\n", 1877c478bd9Sstevel@tonic-gate childp->time, childp->childtime, 1887c478bd9Sstevel@tonic-gate arcp->arc_count, childp->ncall); 189*92ed1782Smike_s (void) printf("[dotime] parent\t"); 1907c478bd9Sstevel@tonic-gate printname(parentp); 191*92ed1782Smike_s (void) printf("\n[dotime] share %f\n", share); 1927c478bd9Sstevel@tonic-gate } 1937c478bd9Sstevel@tonic-gate #endif /* DEBUG */ 1947c478bd9Sstevel@tonic-gate } 1957c478bd9Sstevel@tonic-gate } 1967c478bd9Sstevel@tonic-gate 1977c478bd9Sstevel@tonic-gate 1987c478bd9Sstevel@tonic-gate static void 199*92ed1782Smike_s cycletime(void) 2007c478bd9Sstevel@tonic-gate { 2017c478bd9Sstevel@tonic-gate int cycle; 2027c478bd9Sstevel@tonic-gate nltype *cyclenlp; 2037c478bd9Sstevel@tonic-gate nltype *childp; 2047c478bd9Sstevel@tonic-gate 2057c478bd9Sstevel@tonic-gate for (cycle = 1; cycle <= ncycle; cycle += 1) { 2067c478bd9Sstevel@tonic-gate cyclenlp = &cyclenl[cycle]; 2077c478bd9Sstevel@tonic-gate for (childp = cyclenlp->cnext; childp; childp = childp->cnext) { 2087c478bd9Sstevel@tonic-gate if (childp->propfraction == 0.0) { 2097c478bd9Sstevel@tonic-gate /* 2107c478bd9Sstevel@tonic-gate * all members have the same propfraction 2117c478bd9Sstevel@tonic-gate * except those that were excluded with -E 2127c478bd9Sstevel@tonic-gate */ 2137c478bd9Sstevel@tonic-gate continue; 2147c478bd9Sstevel@tonic-gate } 2157c478bd9Sstevel@tonic-gate cyclenlp->time += childp->time; 2167c478bd9Sstevel@tonic-gate } 2177c478bd9Sstevel@tonic-gate cyclenlp->propself = cyclenlp->propfraction * cyclenlp->time; 2187c478bd9Sstevel@tonic-gate } 2197c478bd9Sstevel@tonic-gate } 2207c478bd9Sstevel@tonic-gate 2217c478bd9Sstevel@tonic-gate 2227c478bd9Sstevel@tonic-gate static void 223*92ed1782Smike_s dotime(void) 2247c478bd9Sstevel@tonic-gate { 2257c478bd9Sstevel@tonic-gate int index; 2267c478bd9Sstevel@tonic-gate 2277c478bd9Sstevel@tonic-gate cycletime(); 2287c478bd9Sstevel@tonic-gate for (index = 0; index < total_names; index += 1) { 2297c478bd9Sstevel@tonic-gate timepropagate(topsortnlp[index]); 2307c478bd9Sstevel@tonic-gate } 2317c478bd9Sstevel@tonic-gate } 2327c478bd9Sstevel@tonic-gate 2337c478bd9Sstevel@tonic-gate 2347c478bd9Sstevel@tonic-gate static void 235*92ed1782Smike_s cyclelink(void) 2367c478bd9Sstevel@tonic-gate { 237*92ed1782Smike_s nltype *nlp; 238*92ed1782Smike_s nltype *cyclenlp; 2397c478bd9Sstevel@tonic-gate int cycle; 2407c478bd9Sstevel@tonic-gate nltype *memberp; 2417c478bd9Sstevel@tonic-gate arctype *arcp; 2427c478bd9Sstevel@tonic-gate mod_info_t *mi; 2437c478bd9Sstevel@tonic-gate 2447c478bd9Sstevel@tonic-gate /* 2457c478bd9Sstevel@tonic-gate * Count the number of cycles, and initialize the cycle lists 2467c478bd9Sstevel@tonic-gate */ 2477c478bd9Sstevel@tonic-gate ncycle = 0; 2487c478bd9Sstevel@tonic-gate for (mi = &modules; mi; mi = mi->next) { 2497c478bd9Sstevel@tonic-gate for (nlp = mi->nl; nlp < mi->npe; nlp++) { 2507c478bd9Sstevel@tonic-gate /* 2517c478bd9Sstevel@tonic-gate * this is how you find unattached cycles 2527c478bd9Sstevel@tonic-gate */ 2537c478bd9Sstevel@tonic-gate if (nlp->cyclehead == nlp && nlp->cnext != 0) { 2547c478bd9Sstevel@tonic-gate ncycle += 1; 2557c478bd9Sstevel@tonic-gate } 2567c478bd9Sstevel@tonic-gate } 2577c478bd9Sstevel@tonic-gate } 2587c478bd9Sstevel@tonic-gate 2597c478bd9Sstevel@tonic-gate /* 2607c478bd9Sstevel@tonic-gate * cyclenl is indexed by cycle number: 2617c478bd9Sstevel@tonic-gate * i.e. it is origin 1, not origin 0. 2627c478bd9Sstevel@tonic-gate */ 2637c478bd9Sstevel@tonic-gate cyclenl = (nltype *) calloc(ncycle + 1, sizeof (nltype)); 2647c478bd9Sstevel@tonic-gate if (cyclenl == 0) { 265*92ed1782Smike_s (void) fprintf(stderr, 2667c478bd9Sstevel@tonic-gate "%s: No room for %d bytes of cycle headers\n", 2677c478bd9Sstevel@tonic-gate whoami, (ncycle + 1) * sizeof (nltype)); 2687c478bd9Sstevel@tonic-gate done(); 2697c478bd9Sstevel@tonic-gate } 2707c478bd9Sstevel@tonic-gate 2717c478bd9Sstevel@tonic-gate /* 2727c478bd9Sstevel@tonic-gate * now link cycles to true cycleheads, 2737c478bd9Sstevel@tonic-gate * number them, accumulate the data for the cycle 2747c478bd9Sstevel@tonic-gate */ 2757c478bd9Sstevel@tonic-gate cycle = 0; 2767c478bd9Sstevel@tonic-gate for (mi = &modules; mi; mi = mi->next) { 2777c478bd9Sstevel@tonic-gate for (nlp = mi->nl; nlp < mi->npe; nlp++) { 2787c478bd9Sstevel@tonic-gate if (!(nlp->cyclehead == nlp && nlp->cnext != 0)) { 2797c478bd9Sstevel@tonic-gate continue; 2807c478bd9Sstevel@tonic-gate } 2817c478bd9Sstevel@tonic-gate cycle += 1; 2827c478bd9Sstevel@tonic-gate cyclenlp = &cyclenl[cycle]; 2837c478bd9Sstevel@tonic-gate cyclenlp->name = 0; /* the name */ 2847c478bd9Sstevel@tonic-gate cyclenlp->value = 0; /* pc entry point */ 2857c478bd9Sstevel@tonic-gate cyclenlp->time = 0.0; /* ticks in routine */ 2867c478bd9Sstevel@tonic-gate cyclenlp->childtime = 0.0; /* cumulative ticks */ 2877c478bd9Sstevel@tonic-gate /* in children */ 2887c478bd9Sstevel@tonic-gate cyclenlp->ncall = 0; /* how many times */ 2897c478bd9Sstevel@tonic-gate /* called */ 2907c478bd9Sstevel@tonic-gate cyclenlp->selfcalls = 0; /* how many calls */ 2917c478bd9Sstevel@tonic-gate /* to self */ 2927c478bd9Sstevel@tonic-gate cyclenlp->propfraction = 0.0; /* what % of time */ 2937c478bd9Sstevel@tonic-gate /* propagates */ 2947c478bd9Sstevel@tonic-gate cyclenlp->propself = 0.0; /* how much self time */ 2957c478bd9Sstevel@tonic-gate /* propagates */ 2967c478bd9Sstevel@tonic-gate cyclenlp->propchild = 0.0; /* how much of child */ 2977c478bd9Sstevel@tonic-gate /* time propagates */ 2987c478bd9Sstevel@tonic-gate cyclenlp->printflag = TRUE; /* should this be */ 2997c478bd9Sstevel@tonic-gate /* printed? */ 3007c478bd9Sstevel@tonic-gate cyclenlp->index = 0; /* index in the */ 3017c478bd9Sstevel@tonic-gate /* graph list */ 3027c478bd9Sstevel@tonic-gate cyclenlp->toporder = DFN_NAN; /* graph call chain */ 3037c478bd9Sstevel@tonic-gate /* top-sort order */ 3047c478bd9Sstevel@tonic-gate cyclenlp->cycleno = cycle; /* internal number */ 3057c478bd9Sstevel@tonic-gate /* of cycle on */ 3067c478bd9Sstevel@tonic-gate cyclenlp->cyclehead = cyclenlp; /* head of cycle ptr */ 3077c478bd9Sstevel@tonic-gate cyclenlp->cnext = nlp; /* ptr to next member */ 3087c478bd9Sstevel@tonic-gate /* of cycle */ 3097c478bd9Sstevel@tonic-gate cyclenlp->parents = 0; /* caller arcs list */ 3107c478bd9Sstevel@tonic-gate cyclenlp->children = 0; /* callee arcs list */ 3117c478bd9Sstevel@tonic-gate #ifdef DEBUG 3127c478bd9Sstevel@tonic-gate if (debug & CYCLEDEBUG) { 313*92ed1782Smike_s (void) printf("[cyclelink] "); 3147c478bd9Sstevel@tonic-gate printname(nlp); 315*92ed1782Smike_s (void) printf(" is the head of cycle %d\n", 316*92ed1782Smike_s cycle); 3177c478bd9Sstevel@tonic-gate } 3187c478bd9Sstevel@tonic-gate #endif /* DEBUG */ 3197c478bd9Sstevel@tonic-gate /* 3207c478bd9Sstevel@tonic-gate * link members to cycle header 3217c478bd9Sstevel@tonic-gate */ 3227c478bd9Sstevel@tonic-gate for (memberp = nlp; memberp; memberp = memberp->cnext) { 3237c478bd9Sstevel@tonic-gate memberp->cycleno = cycle; 3247c478bd9Sstevel@tonic-gate memberp->cyclehead = cyclenlp; 3257c478bd9Sstevel@tonic-gate } 3267c478bd9Sstevel@tonic-gate /* 3277c478bd9Sstevel@tonic-gate * count calls from outside the cycle 3287c478bd9Sstevel@tonic-gate * and those among cycle members 3297c478bd9Sstevel@tonic-gate */ 3307c478bd9Sstevel@tonic-gate for (memberp = nlp; memberp; memberp = memberp->cnext) { 3317c478bd9Sstevel@tonic-gate for (arcp = memberp->parents; arcp; 3327c478bd9Sstevel@tonic-gate arcp = arcp->arc_parentlist) { 3337c478bd9Sstevel@tonic-gate if (arcp->arc_parentp == memberp) 3347c478bd9Sstevel@tonic-gate continue; 3357c478bd9Sstevel@tonic-gate 3367c478bd9Sstevel@tonic-gate if (arcp->arc_parentp->cycleno == 3377c478bd9Sstevel@tonic-gate cycle) { 3387c478bd9Sstevel@tonic-gate cyclenlp->selfcalls += 3397c478bd9Sstevel@tonic-gate arcp->arc_count; 3407c478bd9Sstevel@tonic-gate } else 3417c478bd9Sstevel@tonic-gate cyclenlp->ncall += arcp->arc_count; 3427c478bd9Sstevel@tonic-gate } 3437c478bd9Sstevel@tonic-gate } 3447c478bd9Sstevel@tonic-gate } 3457c478bd9Sstevel@tonic-gate } 3467c478bd9Sstevel@tonic-gate } 3477c478bd9Sstevel@tonic-gate 3487c478bd9Sstevel@tonic-gate 3497c478bd9Sstevel@tonic-gate /* 3507c478bd9Sstevel@tonic-gate * check if any parent of this child 3517c478bd9Sstevel@tonic-gate * (or outside parents of this cycle) 3527c478bd9Sstevel@tonic-gate * have their print flags on and set the 3537c478bd9Sstevel@tonic-gate * print flag of the child (cycle) appropriately. 3547c478bd9Sstevel@tonic-gate * similarly, deal with propagation fractions from parents. 3557c478bd9Sstevel@tonic-gate */ 3567c478bd9Sstevel@tonic-gate static void 3577c478bd9Sstevel@tonic-gate inheritflags(nltype *childp) 3587c478bd9Sstevel@tonic-gate { 3597c478bd9Sstevel@tonic-gate nltype *headp; 3607c478bd9Sstevel@tonic-gate arctype *arcp; 3617c478bd9Sstevel@tonic-gate nltype *parentp; 3627c478bd9Sstevel@tonic-gate nltype *memp; 3637c478bd9Sstevel@tonic-gate 3647c478bd9Sstevel@tonic-gate headp = childp->cyclehead; 3657c478bd9Sstevel@tonic-gate if (childp == headp) { 3667c478bd9Sstevel@tonic-gate /* 3677c478bd9Sstevel@tonic-gate * just a regular child, check its parents 3687c478bd9Sstevel@tonic-gate */ 3697c478bd9Sstevel@tonic-gate childp->printflag = FALSE; 3707c478bd9Sstevel@tonic-gate childp->propfraction = 0.0; 3717c478bd9Sstevel@tonic-gate for (arcp = childp->parents; arcp; 3727c478bd9Sstevel@tonic-gate arcp = arcp->arc_parentlist) { 3737c478bd9Sstevel@tonic-gate parentp = arcp->arc_parentp; 3747c478bd9Sstevel@tonic-gate if (childp == parentp) { 3757c478bd9Sstevel@tonic-gate continue; 3767c478bd9Sstevel@tonic-gate } 3777c478bd9Sstevel@tonic-gate childp->printflag |= parentp->printflag; 3787c478bd9Sstevel@tonic-gate /* 3797c478bd9Sstevel@tonic-gate * if the child was never actually called 3807c478bd9Sstevel@tonic-gate * (e.g. this arc is static (and all others 3817c478bd9Sstevel@tonic-gate * are, too)) no time propagates along this arc. 3827c478bd9Sstevel@tonic-gate */ 3837c478bd9Sstevel@tonic-gate if (childp->ncall) { 3847c478bd9Sstevel@tonic-gate childp->propfraction += parentp->propfraction 3857c478bd9Sstevel@tonic-gate * (((double)arcp->arc_count) 3867c478bd9Sstevel@tonic-gate / ((double)childp->ncall)); 3877c478bd9Sstevel@tonic-gate } 3887c478bd9Sstevel@tonic-gate } 3897c478bd9Sstevel@tonic-gate } else { 3907c478bd9Sstevel@tonic-gate /* 3917c478bd9Sstevel@tonic-gate * its a member of a cycle, look at all parents from 3927c478bd9Sstevel@tonic-gate * outside the cycle 3937c478bd9Sstevel@tonic-gate */ 3947c478bd9Sstevel@tonic-gate headp->printflag = FALSE; 3957c478bd9Sstevel@tonic-gate headp->propfraction = 0.0; 3967c478bd9Sstevel@tonic-gate for (memp = headp->cnext; memp; memp = memp->cnext) { 3977c478bd9Sstevel@tonic-gate for (arcp = memp->parents; arcp; 3987c478bd9Sstevel@tonic-gate arcp = arcp->arc_parentlist) { 3997c478bd9Sstevel@tonic-gate if (arcp->arc_parentp->cyclehead == headp) { 4007c478bd9Sstevel@tonic-gate continue; 4017c478bd9Sstevel@tonic-gate } 4027c478bd9Sstevel@tonic-gate parentp = arcp->arc_parentp; 4037c478bd9Sstevel@tonic-gate headp->printflag |= parentp->printflag; 4047c478bd9Sstevel@tonic-gate /* 4057c478bd9Sstevel@tonic-gate * if the cycle was never actually called 4067c478bd9Sstevel@tonic-gate * (e.g. this arc is static (and all 4077c478bd9Sstevel@tonic-gate * others are, too)) no time propagates 4087c478bd9Sstevel@tonic-gate * along this arc. 4097c478bd9Sstevel@tonic-gate */ 4107c478bd9Sstevel@tonic-gate if (headp->ncall) { 4117c478bd9Sstevel@tonic-gate headp->propfraction += 4127c478bd9Sstevel@tonic-gate parentp->propfraction 4137c478bd9Sstevel@tonic-gate * (((double)arcp->arc_count) 4147c478bd9Sstevel@tonic-gate / ((double)headp->ncall)); 4157c478bd9Sstevel@tonic-gate } 4167c478bd9Sstevel@tonic-gate } 4177c478bd9Sstevel@tonic-gate } 4187c478bd9Sstevel@tonic-gate for (memp = headp; memp; memp = memp->cnext) { 4197c478bd9Sstevel@tonic-gate memp->printflag = headp->printflag; 4207c478bd9Sstevel@tonic-gate memp->propfraction = headp->propfraction; 4217c478bd9Sstevel@tonic-gate } 4227c478bd9Sstevel@tonic-gate } 4237c478bd9Sstevel@tonic-gate } 4247c478bd9Sstevel@tonic-gate 4257c478bd9Sstevel@tonic-gate 4267c478bd9Sstevel@tonic-gate /* 4277c478bd9Sstevel@tonic-gate * check here if *any* of its parents is printable 4287c478bd9Sstevel@tonic-gate * then return true else return false 4297c478bd9Sstevel@tonic-gate */ 4307c478bd9Sstevel@tonic-gate static int 4317c478bd9Sstevel@tonic-gate check_ancestors(nltype *siblingp) 4327c478bd9Sstevel@tonic-gate { 4337c478bd9Sstevel@tonic-gate arctype *parentsp; 4347c478bd9Sstevel@tonic-gate if (!siblingp->parents) 4357c478bd9Sstevel@tonic-gate return (1); 4367c478bd9Sstevel@tonic-gate for (parentsp = siblingp->parents; parentsp; 4377c478bd9Sstevel@tonic-gate parentsp = parentsp->arc_parentlist) { 4387c478bd9Sstevel@tonic-gate if (parentsp->arc_parentp->printflag) 4397c478bd9Sstevel@tonic-gate return (1); 4407c478bd9Sstevel@tonic-gate } 4417c478bd9Sstevel@tonic-gate return (0); 4427c478bd9Sstevel@tonic-gate } 4437c478bd9Sstevel@tonic-gate 4447c478bd9Sstevel@tonic-gate 4457c478bd9Sstevel@tonic-gate /* 4467c478bd9Sstevel@tonic-gate * check if the parents it passes time are *all* on 4477c478bd9Sstevel@tonic-gate * the Elist in which case we do not pass the time 4487c478bd9Sstevel@tonic-gate */ 4497c478bd9Sstevel@tonic-gate static int 4507c478bd9Sstevel@tonic-gate check_parents(nltype *siblingp) 4517c478bd9Sstevel@tonic-gate { 4527c478bd9Sstevel@tonic-gate arctype *parentsp; 4537c478bd9Sstevel@tonic-gate if (!siblingp->parents) 4547c478bd9Sstevel@tonic-gate return (1); 4557c478bd9Sstevel@tonic-gate for (parentsp = siblingp->parents; parentsp; 4567c478bd9Sstevel@tonic-gate parentsp = parentsp->arc_parentlist) { 4577c478bd9Sstevel@tonic-gate if (!onlist(Elist, parentsp->arc_parentp->name)) 4587c478bd9Sstevel@tonic-gate return (1); 4597c478bd9Sstevel@tonic-gate } 4607c478bd9Sstevel@tonic-gate return (0); 4617c478bd9Sstevel@tonic-gate } 4627c478bd9Sstevel@tonic-gate 4637c478bd9Sstevel@tonic-gate 4647c478bd9Sstevel@tonic-gate /* 4657c478bd9Sstevel@tonic-gate * in one top to bottom pass over the topologically sorted namelist 4667c478bd9Sstevel@tonic-gate * propagate: 4677c478bd9Sstevel@tonic-gate * printflag as the union of parents' printflags 4687c478bd9Sstevel@tonic-gate * propfraction as the sum of fractional parents' propfractions 4697c478bd9Sstevel@tonic-gate * and while we're here, sum time for functions. 4707c478bd9Sstevel@tonic-gate */ 4717c478bd9Sstevel@tonic-gate static void 472*92ed1782Smike_s doflags(void) 4737c478bd9Sstevel@tonic-gate { 4747c478bd9Sstevel@tonic-gate int index; 4757c478bd9Sstevel@tonic-gate nltype *childp; 4767c478bd9Sstevel@tonic-gate nltype *oldhead; 4777c478bd9Sstevel@tonic-gate 4787c478bd9Sstevel@tonic-gate oldhead = 0; 4797c478bd9Sstevel@tonic-gate for (index = total_names - 1; index >= 0; index -= 1) { 4807c478bd9Sstevel@tonic-gate childp = topsortnlp[index]; 4817c478bd9Sstevel@tonic-gate /* 4827c478bd9Sstevel@tonic-gate * if we haven't done this function or cycle, 4837c478bd9Sstevel@tonic-gate * inherit things from parent. 4847c478bd9Sstevel@tonic-gate * this way, we are linear in the number of arcs 4857c478bd9Sstevel@tonic-gate * since we do all members of a cycle (and the 4867c478bd9Sstevel@tonic-gate * cycle itself) as we hit the first member 4877c478bd9Sstevel@tonic-gate * of the cycle. 4887c478bd9Sstevel@tonic-gate */ 4897c478bd9Sstevel@tonic-gate if (childp->cyclehead != oldhead) { 4907c478bd9Sstevel@tonic-gate oldhead = childp->cyclehead; 4917c478bd9Sstevel@tonic-gate inheritflags(childp); 4927c478bd9Sstevel@tonic-gate } 4937c478bd9Sstevel@tonic-gate #ifdef DEBUG 4947c478bd9Sstevel@tonic-gate if (debug & PROPDEBUG) { 495*92ed1782Smike_s (void) printf("[doflags] "); 4967c478bd9Sstevel@tonic-gate printname(childp); 497*92ed1782Smike_s (void) printf( 498*92ed1782Smike_s " inherits printflag %d and propfraction %f\n", 4997c478bd9Sstevel@tonic-gate childp->printflag, childp->propfraction); 5007c478bd9Sstevel@tonic-gate } 5017c478bd9Sstevel@tonic-gate #endif /* DEBUG */ 5027c478bd9Sstevel@tonic-gate if (!childp->printflag) { 5037c478bd9Sstevel@tonic-gate bool on_flist; 5047c478bd9Sstevel@tonic-gate /* 5057c478bd9Sstevel@tonic-gate * printflag is off 5067c478bd9Sstevel@tonic-gate * it gets turned on by 5077c478bd9Sstevel@tonic-gate * being on -f list, 5087c478bd9Sstevel@tonic-gate * or there not being any -f list 5097c478bd9Sstevel@tonic-gate * and not being on -e list. 5107c478bd9Sstevel@tonic-gate */ 5117c478bd9Sstevel@tonic-gate if (((on_flist = onlist(flist, childp->name)) != 0) || 5127c478bd9Sstevel@tonic-gate (!fflag && !onlist(elist, childp->name))) { 5137c478bd9Sstevel@tonic-gate if (on_flist || check_ancestors(childp)) 5147c478bd9Sstevel@tonic-gate childp->printflag = TRUE; 5157c478bd9Sstevel@tonic-gate } 5167c478bd9Sstevel@tonic-gate } else { 5177c478bd9Sstevel@tonic-gate /* 5187c478bd9Sstevel@tonic-gate * this function has printing parents: 5197c478bd9Sstevel@tonic-gate * maybe someone wants to shut it up 5207c478bd9Sstevel@tonic-gate * by putting it on -e list. (but favor -f 5217c478bd9Sstevel@tonic-gate * over -e) 5227c478bd9Sstevel@tonic-gate */ 5237c478bd9Sstevel@tonic-gate if ((!onlist(flist, childp->name)) && 5247c478bd9Sstevel@tonic-gate onlist(elist, childp->name)) { 5257c478bd9Sstevel@tonic-gate childp->printflag = FALSE; 5267c478bd9Sstevel@tonic-gate } 5277c478bd9Sstevel@tonic-gate } 5287c478bd9Sstevel@tonic-gate if (childp->propfraction == 0.0) { 5297c478bd9Sstevel@tonic-gate /* 5307c478bd9Sstevel@tonic-gate * no parents to pass time to. 5317c478bd9Sstevel@tonic-gate * collect time from children if 5327c478bd9Sstevel@tonic-gate * its on -F list, 5337c478bd9Sstevel@tonic-gate * or there isn't any -F list and its not 5347c478bd9Sstevel@tonic-gate * on -E list. 5357c478bd9Sstevel@tonic-gate */ 5367c478bd9Sstevel@tonic-gate if (onlist(Flist, childp->name) || 5377c478bd9Sstevel@tonic-gate (!Fflag && !onlist(Elist, childp->name))) { 5387c478bd9Sstevel@tonic-gate childp->propfraction = 1.0; 5397c478bd9Sstevel@tonic-gate } 5407c478bd9Sstevel@tonic-gate } else { 5417c478bd9Sstevel@tonic-gate /* 5427c478bd9Sstevel@tonic-gate * it has parents to pass time to, 5437c478bd9Sstevel@tonic-gate * but maybe someone wants to shut it up 5447c478bd9Sstevel@tonic-gate * by putting it on -E list. (but favor -F 5457c478bd9Sstevel@tonic-gate * over -E) 5467c478bd9Sstevel@tonic-gate */ 5477c478bd9Sstevel@tonic-gate if (!onlist(Flist, childp->name) && 5487c478bd9Sstevel@tonic-gate onlist(Elist, childp->name)) { 5497c478bd9Sstevel@tonic-gate if (check_parents(childp)) 5507c478bd9Sstevel@tonic-gate childp->propfraction = 0.0; 5517c478bd9Sstevel@tonic-gate } 5527c478bd9Sstevel@tonic-gate } 5537c478bd9Sstevel@tonic-gate childp->propself = childp->time * childp->propfraction; 5547c478bd9Sstevel@tonic-gate printtime += childp->propself; 5557c478bd9Sstevel@tonic-gate #ifdef DEBUG 5567c478bd9Sstevel@tonic-gate if (debug & PROPDEBUG) { 557*92ed1782Smike_s (void) printf("[doflags] "); 5587c478bd9Sstevel@tonic-gate printname(childp); 559*92ed1782Smike_s (void) printf(" ends up with printflag %d and " 5607c478bd9Sstevel@tonic-gate "propfraction %f\n", 5617c478bd9Sstevel@tonic-gate childp->printflag, childp->propfraction); 562*92ed1782Smike_s (void) printf("time %f propself %f printtime %f\n", 5637c478bd9Sstevel@tonic-gate childp->time, childp->propself, printtime); 5647c478bd9Sstevel@tonic-gate } 5657c478bd9Sstevel@tonic-gate #endif /* DEBUG */ 5667c478bd9Sstevel@tonic-gate } 5677c478bd9Sstevel@tonic-gate } 5687c478bd9Sstevel@tonic-gate 5697c478bd9Sstevel@tonic-gate 5707c478bd9Sstevel@tonic-gate nltype ** 571*92ed1782Smike_s doarcs(void) 5727c478bd9Sstevel@tonic-gate { 5737c478bd9Sstevel@tonic-gate nltype *parentp, **timesortnlp; 5747c478bd9Sstevel@tonic-gate arctype *arcp; 5757c478bd9Sstevel@tonic-gate long i, index; 5767c478bd9Sstevel@tonic-gate 5777c478bd9Sstevel@tonic-gate extern mod_info_t modules; 5787c478bd9Sstevel@tonic-gate mod_info_t *mi; 5797c478bd9Sstevel@tonic-gate 5807c478bd9Sstevel@tonic-gate /* 5817c478bd9Sstevel@tonic-gate * initialize various things: 5827c478bd9Sstevel@tonic-gate * zero out child times. 5837c478bd9Sstevel@tonic-gate * count self-recursive calls. 5847c478bd9Sstevel@tonic-gate * indicate that nothing is on cycles. 5857c478bd9Sstevel@tonic-gate */ 5867c478bd9Sstevel@tonic-gate for (mi = &modules; mi; mi = mi->next) { 5877c478bd9Sstevel@tonic-gate for (parentp = mi->nl; parentp < mi->npe; parentp++) { 5887c478bd9Sstevel@tonic-gate parentp->childtime = 0.0; 5897c478bd9Sstevel@tonic-gate arcp = arclookup(parentp, parentp); 5907c478bd9Sstevel@tonic-gate if (arcp != 0) { 5917c478bd9Sstevel@tonic-gate parentp->ncall -= arcp->arc_count; 5927c478bd9Sstevel@tonic-gate parentp->selfcalls = arcp->arc_count; 5937c478bd9Sstevel@tonic-gate } else { 5947c478bd9Sstevel@tonic-gate parentp->selfcalls = 0; 5957c478bd9Sstevel@tonic-gate } 5967c478bd9Sstevel@tonic-gate parentp->propfraction = 0.0; 5977c478bd9Sstevel@tonic-gate parentp->propself = 0.0; 5987c478bd9Sstevel@tonic-gate parentp->propchild = 0.0; 5997c478bd9Sstevel@tonic-gate parentp->printflag = FALSE; 6007c478bd9Sstevel@tonic-gate parentp->toporder = DFN_NAN; 6017c478bd9Sstevel@tonic-gate parentp->cycleno = 0; 6027c478bd9Sstevel@tonic-gate parentp->cyclehead = parentp; 6037c478bd9Sstevel@tonic-gate parentp->cnext = 0; 6047c478bd9Sstevel@tonic-gate 6057c478bd9Sstevel@tonic-gate /* 6067c478bd9Sstevel@tonic-gate * Inspecting text space is valid only for 6077c478bd9Sstevel@tonic-gate * the program executable. 6087c478bd9Sstevel@tonic-gate */ 6097c478bd9Sstevel@tonic-gate if (cflag && (mi == &modules)) { 6107c478bd9Sstevel@tonic-gate findcalls( 6117c478bd9Sstevel@tonic-gate parentp, 6127c478bd9Sstevel@tonic-gate parentp->value, 6137c478bd9Sstevel@tonic-gate parentp->value + parentp->sz); 6147c478bd9Sstevel@tonic-gate } 6157c478bd9Sstevel@tonic-gate } 6167c478bd9Sstevel@tonic-gate } 6177c478bd9Sstevel@tonic-gate 6187c478bd9Sstevel@tonic-gate /* 6197c478bd9Sstevel@tonic-gate * topologically order things 6207c478bd9Sstevel@tonic-gate * if any node is unnumbered, 6217c478bd9Sstevel@tonic-gate * number it and any of its descendents. 6227c478bd9Sstevel@tonic-gate */ 6237c478bd9Sstevel@tonic-gate for (mi = &modules; mi; mi = mi->next) { 6247c478bd9Sstevel@tonic-gate for (parentp = mi->nl; parentp < mi->npe; parentp++) { 6257c478bd9Sstevel@tonic-gate if (parentp->toporder == DFN_NAN) { 6267c478bd9Sstevel@tonic-gate dfn(parentp); 6277c478bd9Sstevel@tonic-gate } 6287c478bd9Sstevel@tonic-gate } 6297c478bd9Sstevel@tonic-gate } 6307c478bd9Sstevel@tonic-gate 6317c478bd9Sstevel@tonic-gate /* 6327c478bd9Sstevel@tonic-gate * link together nodes on the same cycle 6337c478bd9Sstevel@tonic-gate */ 6347c478bd9Sstevel@tonic-gate cyclelink(); 6357c478bd9Sstevel@tonic-gate /* 6367c478bd9Sstevel@tonic-gate * Sort the symbol tables in reverse topological order 6377c478bd9Sstevel@tonic-gate */ 6387c478bd9Sstevel@tonic-gate topsortnlp = (nltype **) calloc(total_names, sizeof (nltype *)); 6397c478bd9Sstevel@tonic-gate if (topsortnlp == (nltype **) 0) { 640*92ed1782Smike_s (void) fprintf(stderr, 6417c478bd9Sstevel@tonic-gate "[doarcs] ran out of memory for topo sorting\n"); 6427c478bd9Sstevel@tonic-gate } 6437c478bd9Sstevel@tonic-gate index = 0; 6447c478bd9Sstevel@tonic-gate for (mi = &modules; mi; mi = mi->next) { 6457c478bd9Sstevel@tonic-gate for (i = 0; i < mi->nname; i++) 6467c478bd9Sstevel@tonic-gate topsortnlp[index++] = &(mi->nl[i]); 6477c478bd9Sstevel@tonic-gate } 6487c478bd9Sstevel@tonic-gate 649*92ed1782Smike_s qsort(topsortnlp, total_names, sizeof (nltype *), topcmp); 6507c478bd9Sstevel@tonic-gate #ifdef DEBUG 6517c478bd9Sstevel@tonic-gate if (debug & DFNDEBUG) { 652*92ed1782Smike_s (void) printf("[doarcs] topological sort listing\n"); 6537c478bd9Sstevel@tonic-gate for (index = 0; index < total_names; index += 1) { 654*92ed1782Smike_s (void) printf("[doarcs] "); 655*92ed1782Smike_s (void) printf("%d:", topsortnlp[ index ]->toporder); 6567c478bd9Sstevel@tonic-gate printname(topsortnlp[ index ]); 657*92ed1782Smike_s (void) printf("\n"); 6587c478bd9Sstevel@tonic-gate } 6597c478bd9Sstevel@tonic-gate } 6607c478bd9Sstevel@tonic-gate #endif /* DEBUG */ 6617c478bd9Sstevel@tonic-gate /* 6627c478bd9Sstevel@tonic-gate * starting from the topological top, 6637c478bd9Sstevel@tonic-gate * propagate print flags to children. 6647c478bd9Sstevel@tonic-gate * also, calculate propagation fractions. 6657c478bd9Sstevel@tonic-gate * this happens before time propagation 6667c478bd9Sstevel@tonic-gate * since time propagation uses the fractions. 6677c478bd9Sstevel@tonic-gate */ 6687c478bd9Sstevel@tonic-gate doflags(); 6697c478bd9Sstevel@tonic-gate /* 6707c478bd9Sstevel@tonic-gate * starting from the topological bottom, 6717c478bd9Sstevel@tonic-gate * propogate children times up to parents. 6727c478bd9Sstevel@tonic-gate */ 6737c478bd9Sstevel@tonic-gate dotime(); 6747c478bd9Sstevel@tonic-gate /* 6757c478bd9Sstevel@tonic-gate * Now, sort by propself + propchild. 6767c478bd9Sstevel@tonic-gate * sorting both the regular function names 6777c478bd9Sstevel@tonic-gate * and cycle headers. 6787c478bd9Sstevel@tonic-gate */ 6797c478bd9Sstevel@tonic-gate timesortnlp = (nltype **) calloc(total_names + ncycle, 6807c478bd9Sstevel@tonic-gate sizeof (nltype *)); 6817c478bd9Sstevel@tonic-gate if (timesortnlp == (nltype **) 0) { 682*92ed1782Smike_s (void) fprintf(stderr, 683*92ed1782Smike_s "%s: ran out of memory for sorting\n", whoami); 6847c478bd9Sstevel@tonic-gate } 6857c478bd9Sstevel@tonic-gate 6867c478bd9Sstevel@tonic-gate index = 0; 6877c478bd9Sstevel@tonic-gate for (mi = &modules; mi; mi = mi->next) { 6887c478bd9Sstevel@tonic-gate for (i = 0; i < mi->nname; i++) 6897c478bd9Sstevel@tonic-gate timesortnlp[index++] = &(mi->nl[i]); 6907c478bd9Sstevel@tonic-gate } 6917c478bd9Sstevel@tonic-gate 6927c478bd9Sstevel@tonic-gate for (index = 1; index <= ncycle; index++) 6937c478bd9Sstevel@tonic-gate timesortnlp[total_names+index-1] = &cyclenl[index]; 6947c478bd9Sstevel@tonic-gate 695*92ed1782Smike_s qsort(timesortnlp, total_names + ncycle, sizeof (nltype *), totalcmp); 6967c478bd9Sstevel@tonic-gate 6977c478bd9Sstevel@tonic-gate for (index = 0; index < total_names + ncycle; index++) 6987c478bd9Sstevel@tonic-gate timesortnlp[index]->index = index + 1; 6997c478bd9Sstevel@tonic-gate 7007c478bd9Sstevel@tonic-gate return (timesortnlp); 7017c478bd9Sstevel@tonic-gate } 702