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