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-1997,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 <stdio.h> 30*0Sstevel@tonic-gate #include "gprof.h" 31*0Sstevel@tonic-gate 32*0Sstevel@tonic-gate #define DFN_DEPTH 100 33*0Sstevel@tonic-gate 34*0Sstevel@tonic-gate struct dfnstruct { 35*0Sstevel@tonic-gate nltype *nlentryp; 36*0Sstevel@tonic-gate int cycletop; 37*0Sstevel@tonic-gate }; 38*0Sstevel@tonic-gate 39*0Sstevel@tonic-gate typedef struct dfnstruct dfntype; 40*0Sstevel@tonic-gate 41*0Sstevel@tonic-gate dfntype *dfn_stack = NULL; 42*0Sstevel@tonic-gate int dfn_depth = 0; 43*0Sstevel@tonic-gate int dfn_sz = 0; 44*0Sstevel@tonic-gate 45*0Sstevel@tonic-gate int dfn_counter = DFN_NAN; 46*0Sstevel@tonic-gate 47*0Sstevel@tonic-gate /* 48*0Sstevel@tonic-gate * given this parent, depth first number its children. 49*0Sstevel@tonic-gate */ 50*0Sstevel@tonic-gate void 51*0Sstevel@tonic-gate dfn(nltype *parentp) 52*0Sstevel@tonic-gate { 53*0Sstevel@tonic-gate arctype *arcp; 54*0Sstevel@tonic-gate 55*0Sstevel@tonic-gate #ifdef DEBUG 56*0Sstevel@tonic-gate if (debug & DFNDEBUG) { 57*0Sstevel@tonic-gate printf("[dfn] dfn("); 58*0Sstevel@tonic-gate printname(parentp); 59*0Sstevel@tonic-gate printf(")\n"); 60*0Sstevel@tonic-gate } 61*0Sstevel@tonic-gate #endif /* DEBUG */ 62*0Sstevel@tonic-gate 63*0Sstevel@tonic-gate if (!dfn_stack) { 64*0Sstevel@tonic-gate dfn_sz = DFN_DEPTH; 65*0Sstevel@tonic-gate dfn_stack = (dfntype *) malloc(dfn_sz * sizeof (dfntype)); 66*0Sstevel@tonic-gate if (!dfn_stack) { 67*0Sstevel@tonic-gate fprintf(stderr, 68*0Sstevel@tonic-gate "fatal: can't malloc %d objects\n", dfn_sz); 69*0Sstevel@tonic-gate exit(1); 70*0Sstevel@tonic-gate } 71*0Sstevel@tonic-gate } 72*0Sstevel@tonic-gate 73*0Sstevel@tonic-gate /* 74*0Sstevel@tonic-gate * if we're already numbered, no need to look any furthur. 75*0Sstevel@tonic-gate */ 76*0Sstevel@tonic-gate if (dfn_numbered(parentp)) 77*0Sstevel@tonic-gate return; 78*0Sstevel@tonic-gate 79*0Sstevel@tonic-gate /* 80*0Sstevel@tonic-gate * if we're already busy, must be a cycle 81*0Sstevel@tonic-gate */ 82*0Sstevel@tonic-gate if (dfn_busy(parentp)) { 83*0Sstevel@tonic-gate dfn_findcycle(parentp); 84*0Sstevel@tonic-gate return; 85*0Sstevel@tonic-gate } 86*0Sstevel@tonic-gate 87*0Sstevel@tonic-gate /* 88*0Sstevel@tonic-gate * visit yourself before your children 89*0Sstevel@tonic-gate */ 90*0Sstevel@tonic-gate dfn_pre_visit(parentp); 91*0Sstevel@tonic-gate 92*0Sstevel@tonic-gate /* 93*0Sstevel@tonic-gate * visit children 94*0Sstevel@tonic-gate */ 95*0Sstevel@tonic-gate for (arcp = parentp->children; arcp; arcp = arcp->arc_childlist) 96*0Sstevel@tonic-gate dfn(arcp->arc_childp); 97*0Sstevel@tonic-gate 98*0Sstevel@tonic-gate /* 99*0Sstevel@tonic-gate * visit yourself after your children 100*0Sstevel@tonic-gate */ 101*0Sstevel@tonic-gate dfn_post_visit(parentp); 102*0Sstevel@tonic-gate } 103*0Sstevel@tonic-gate 104*0Sstevel@tonic-gate /* 105*0Sstevel@tonic-gate * push a parent onto the stack and mark it busy 106*0Sstevel@tonic-gate */ 107*0Sstevel@tonic-gate void 108*0Sstevel@tonic-gate dfn_pre_visit(nltype *parentp) 109*0Sstevel@tonic-gate { 110*0Sstevel@tonic-gate 111*0Sstevel@tonic-gate if (!dfn_stack) { 112*0Sstevel@tonic-gate dfn_sz = DFN_DEPTH; 113*0Sstevel@tonic-gate dfn_stack = (dfntype *) malloc(dfn_sz * sizeof (dfntype)); 114*0Sstevel@tonic-gate if (!dfn_stack) { 115*0Sstevel@tonic-gate printf("fatal: can't malloc %d objects\n", dfn_sz); 116*0Sstevel@tonic-gate exit(1); 117*0Sstevel@tonic-gate } 118*0Sstevel@tonic-gate } 119*0Sstevel@tonic-gate 120*0Sstevel@tonic-gate dfn_depth += 1; 121*0Sstevel@tonic-gate 122*0Sstevel@tonic-gate if (dfn_depth >= dfn_sz) { 123*0Sstevel@tonic-gate dfn_sz += DFN_DEPTH; 124*0Sstevel@tonic-gate dfn_stack = (dfntype *) realloc(dfn_stack, 125*0Sstevel@tonic-gate dfn_sz * sizeof (dfntype)); 126*0Sstevel@tonic-gate 127*0Sstevel@tonic-gate if (!dfn_stack) { 128*0Sstevel@tonic-gate fprintf(stderr, 129*0Sstevel@tonic-gate "fatal: can't realloc %d objects\n", dfn_sz); 130*0Sstevel@tonic-gate exit(1); 131*0Sstevel@tonic-gate } 132*0Sstevel@tonic-gate } 133*0Sstevel@tonic-gate 134*0Sstevel@tonic-gate dfn_stack[dfn_depth].nlentryp = parentp; 135*0Sstevel@tonic-gate dfn_stack[dfn_depth].cycletop = dfn_depth; 136*0Sstevel@tonic-gate parentp->toporder = DFN_BUSY; 137*0Sstevel@tonic-gate 138*0Sstevel@tonic-gate #ifdef DEBUG 139*0Sstevel@tonic-gate if (debug & DFNDEBUG) { 140*0Sstevel@tonic-gate printf("[dfn_pre_visit]\t\t%d:", dfn_depth); 141*0Sstevel@tonic-gate printname(parentp); 142*0Sstevel@tonic-gate printf("\n"); 143*0Sstevel@tonic-gate } 144*0Sstevel@tonic-gate #endif /* DEBUG */ 145*0Sstevel@tonic-gate } 146*0Sstevel@tonic-gate 147*0Sstevel@tonic-gate /* 148*0Sstevel@tonic-gate * are we already numbered? 149*0Sstevel@tonic-gate */ 150*0Sstevel@tonic-gate bool 151*0Sstevel@tonic-gate dfn_numbered(nltype *childp) 152*0Sstevel@tonic-gate { 153*0Sstevel@tonic-gate return (childp->toporder != DFN_NAN && childp->toporder != DFN_BUSY); 154*0Sstevel@tonic-gate } 155*0Sstevel@tonic-gate 156*0Sstevel@tonic-gate /* 157*0Sstevel@tonic-gate * are we already busy? 158*0Sstevel@tonic-gate */ 159*0Sstevel@tonic-gate bool 160*0Sstevel@tonic-gate dfn_busy(nltype *childp) 161*0Sstevel@tonic-gate { 162*0Sstevel@tonic-gate if (childp->toporder == DFN_NAN) 163*0Sstevel@tonic-gate return (FALSE); 164*0Sstevel@tonic-gate 165*0Sstevel@tonic-gate return (TRUE); 166*0Sstevel@tonic-gate } 167*0Sstevel@tonic-gate 168*0Sstevel@tonic-gate void 169*0Sstevel@tonic-gate dfn_findcycle(nltype *childp) 170*0Sstevel@tonic-gate { 171*0Sstevel@tonic-gate int cycletop; 172*0Sstevel@tonic-gate nltype *cycleheadp; 173*0Sstevel@tonic-gate nltype *tailp; 174*0Sstevel@tonic-gate int index; 175*0Sstevel@tonic-gate 176*0Sstevel@tonic-gate for (cycletop = dfn_depth; cycletop > 0; cycletop -= 1) { 177*0Sstevel@tonic-gate cycleheadp = dfn_stack[cycletop].nlentryp; 178*0Sstevel@tonic-gate if (childp == cycleheadp) 179*0Sstevel@tonic-gate break; 180*0Sstevel@tonic-gate 181*0Sstevel@tonic-gate if (childp->cyclehead != childp && 182*0Sstevel@tonic-gate childp->cyclehead == cycleheadp) 183*0Sstevel@tonic-gate break; 184*0Sstevel@tonic-gate } 185*0Sstevel@tonic-gate 186*0Sstevel@tonic-gate if (cycletop <= 0) { 187*0Sstevel@tonic-gate /* 188*0Sstevel@tonic-gate * don't report non existent functions 189*0Sstevel@tonic-gate */ 190*0Sstevel@tonic-gate if (childp->value) { 191*0Sstevel@tonic-gate fprintf(stderr, "[dfn_findcycle] couldn't find head " 192*0Sstevel@tonic-gate "of cycle for %s\n", childp->name); 193*0Sstevel@tonic-gate return; 194*0Sstevel@tonic-gate } 195*0Sstevel@tonic-gate } 196*0Sstevel@tonic-gate 197*0Sstevel@tonic-gate #ifdef DEBUG 198*0Sstevel@tonic-gate if (debug & DFNDEBUG) { 199*0Sstevel@tonic-gate printf("[dfn_findcycle] dfn_depth %d cycletop %d ", 200*0Sstevel@tonic-gate dfn_depth, cycletop); 201*0Sstevel@tonic-gate printname(cycleheadp); 202*0Sstevel@tonic-gate printf("\n"); 203*0Sstevel@tonic-gate } 204*0Sstevel@tonic-gate #endif /* DEBUG */ 205*0Sstevel@tonic-gate 206*0Sstevel@tonic-gate if (cycletop == dfn_depth) { 207*0Sstevel@tonic-gate /* 208*0Sstevel@tonic-gate * this is previous function, e.g. this calls itself 209*0Sstevel@tonic-gate * sort of boring 210*0Sstevel@tonic-gate */ 211*0Sstevel@tonic-gate dfn_self_cycle(childp); 212*0Sstevel@tonic-gate } else { 213*0Sstevel@tonic-gate /* 214*0Sstevel@tonic-gate * glom intervening functions that aren't already 215*0Sstevel@tonic-gate * glommed into this cycle. 216*0Sstevel@tonic-gate * things have been glommed when their cyclehead field 217*0Sstevel@tonic-gate * points to the head of the cycle they are glommed into. 218*0Sstevel@tonic-gate */ 219*0Sstevel@tonic-gate for (tailp = cycleheadp; tailp->cnext; tailp = tailp->cnext) { 220*0Sstevel@tonic-gate /* void: chase down to tail of things already glommed */ 221*0Sstevel@tonic-gate #ifdef DEBUG 222*0Sstevel@tonic-gate if (debug & DFNDEBUG) { 223*0Sstevel@tonic-gate printf("[dfn_findcycle] tail "); 224*0Sstevel@tonic-gate printname(tailp); 225*0Sstevel@tonic-gate printf("\n"); 226*0Sstevel@tonic-gate } 227*0Sstevel@tonic-gate #endif /* DEBUG */ 228*0Sstevel@tonic-gate } 229*0Sstevel@tonic-gate 230*0Sstevel@tonic-gate /* 231*0Sstevel@tonic-gate * if what we think is the top of the cycle 232*0Sstevel@tonic-gate * has a cyclehead field, then it's not really the 233*0Sstevel@tonic-gate * head of the cycle, which is really what we want 234*0Sstevel@tonic-gate */ 235*0Sstevel@tonic-gate if (cycleheadp->cyclehead != cycleheadp) { 236*0Sstevel@tonic-gate cycleheadp = cycleheadp->cyclehead; 237*0Sstevel@tonic-gate #ifdef DEBUG 238*0Sstevel@tonic-gate if (debug & DFNDEBUG) { 239*0Sstevel@tonic-gate printf("[dfn_findcycle] new cyclehead "); 240*0Sstevel@tonic-gate printname(cycleheadp); 241*0Sstevel@tonic-gate printf("\n"); 242*0Sstevel@tonic-gate } 243*0Sstevel@tonic-gate #endif /* DEBUG */ 244*0Sstevel@tonic-gate } 245*0Sstevel@tonic-gate 246*0Sstevel@tonic-gate for (index = cycletop + 1; index <= dfn_depth; index += 1) { 247*0Sstevel@tonic-gate 248*0Sstevel@tonic-gate childp = dfn_stack[index].nlentryp; 249*0Sstevel@tonic-gate if (childp->cyclehead == childp) { 250*0Sstevel@tonic-gate /* 251*0Sstevel@tonic-gate * not yet glommed anywhere, glom it 252*0Sstevel@tonic-gate * and fix any children it has glommed 253*0Sstevel@tonic-gate */ 254*0Sstevel@tonic-gate tailp->cnext = childp; 255*0Sstevel@tonic-gate childp->cyclehead = cycleheadp; 256*0Sstevel@tonic-gate #ifdef DEBUG 257*0Sstevel@tonic-gate if (debug & DFNDEBUG) { 258*0Sstevel@tonic-gate printf("[dfn_findcycle] glomming "); 259*0Sstevel@tonic-gate printname(childp); 260*0Sstevel@tonic-gate printf(" onto "); 261*0Sstevel@tonic-gate printname(cycleheadp); 262*0Sstevel@tonic-gate printf("\n"); 263*0Sstevel@tonic-gate } 264*0Sstevel@tonic-gate #endif /* DEBUG */ 265*0Sstevel@tonic-gate for (tailp = childp; tailp->cnext; 266*0Sstevel@tonic-gate tailp = tailp->cnext) { 267*0Sstevel@tonic-gate tailp->cnext->cyclehead = cycleheadp; 268*0Sstevel@tonic-gate #ifdef DEBUG 269*0Sstevel@tonic-gate if (debug & DFNDEBUG) { 270*0Sstevel@tonic-gate printf("[dfn_findcycle]" 271*0Sstevel@tonic-gate " and its tail "); 272*0Sstevel@tonic-gate printname(tailp->cnext); 273*0Sstevel@tonic-gate printf(" onto "); 274*0Sstevel@tonic-gate printname(cycleheadp); 275*0Sstevel@tonic-gate printf("\n"); 276*0Sstevel@tonic-gate } 277*0Sstevel@tonic-gate #endif /* DEBUG */ 278*0Sstevel@tonic-gate } 279*0Sstevel@tonic-gate } else if (childp->cyclehead != cycleheadp) { 280*0Sstevel@tonic-gate fprintf(stderr, "[dfn_busy] glommed," 281*0Sstevel@tonic-gate " but not to cyclehead\n"); 282*0Sstevel@tonic-gate } 283*0Sstevel@tonic-gate } 284*0Sstevel@tonic-gate } 285*0Sstevel@tonic-gate } 286*0Sstevel@tonic-gate 287*0Sstevel@tonic-gate /* 288*0Sstevel@tonic-gate * deal with self-cycles 289*0Sstevel@tonic-gate * for lint: ARGSUSED 290*0Sstevel@tonic-gate */ 291*0Sstevel@tonic-gate /* ARGSUSED */ 292*0Sstevel@tonic-gate void 293*0Sstevel@tonic-gate dfn_self_cycle(nltype *parentp) 294*0Sstevel@tonic-gate { 295*0Sstevel@tonic-gate /* 296*0Sstevel@tonic-gate * since we are taking out self-cycles elsewhere 297*0Sstevel@tonic-gate * no need for the special case, here. 298*0Sstevel@tonic-gate */ 299*0Sstevel@tonic-gate #ifdef DEBUG 300*0Sstevel@tonic-gate if (debug & DFNDEBUG) { 301*0Sstevel@tonic-gate printf("[dfn_self_cycle] "); 302*0Sstevel@tonic-gate printname(parentp); 303*0Sstevel@tonic-gate printf("\n"); 304*0Sstevel@tonic-gate } 305*0Sstevel@tonic-gate #endif /* DEBUG */ 306*0Sstevel@tonic-gate } 307*0Sstevel@tonic-gate 308*0Sstevel@tonic-gate /* 309*0Sstevel@tonic-gate * visit a node after all its children 310*0Sstevel@tonic-gate * [MISSING: an explanation] 311*0Sstevel@tonic-gate * and pop it off the stack 312*0Sstevel@tonic-gate */ 313*0Sstevel@tonic-gate void 314*0Sstevel@tonic-gate dfn_post_visit(nltype *parentp) 315*0Sstevel@tonic-gate { 316*0Sstevel@tonic-gate nltype *memberp; 317*0Sstevel@tonic-gate 318*0Sstevel@tonic-gate #ifdef DEBUG 319*0Sstevel@tonic-gate if (debug & DFNDEBUG) { 320*0Sstevel@tonic-gate printf("[dfn_post_visit]\t%d: ", dfn_depth); 321*0Sstevel@tonic-gate printname(parentp); 322*0Sstevel@tonic-gate printf("\n"); 323*0Sstevel@tonic-gate } 324*0Sstevel@tonic-gate #endif /* DEBUG */ 325*0Sstevel@tonic-gate /* 326*0Sstevel@tonic-gate * number functions and things in their cycles 327*0Sstevel@tonic-gate * unless the function is itself part of a cycle 328*0Sstevel@tonic-gate */ 329*0Sstevel@tonic-gate if (parentp->cyclehead == parentp) { 330*0Sstevel@tonic-gate dfn_counter += 1; 331*0Sstevel@tonic-gate 332*0Sstevel@tonic-gate for (memberp = parentp; memberp; memberp = memberp->cnext) { 333*0Sstevel@tonic-gate 334*0Sstevel@tonic-gate memberp->toporder = dfn_counter; 335*0Sstevel@tonic-gate #ifdef DEBUG 336*0Sstevel@tonic-gate if (debug & DFNDEBUG) { 337*0Sstevel@tonic-gate printf("[dfn_post_visit]\t\tmember "); 338*0Sstevel@tonic-gate printname(memberp); 339*0Sstevel@tonic-gate printf(" -> toporder = %d\n", dfn_counter); 340*0Sstevel@tonic-gate } 341*0Sstevel@tonic-gate #endif /* DEBUG */ 342*0Sstevel@tonic-gate } 343*0Sstevel@tonic-gate #ifdef DEBUG 344*0Sstevel@tonic-gate } else { 345*0Sstevel@tonic-gate if (debug & DFNDEBUG) 346*0Sstevel@tonic-gate printf("[dfn_post_visit]\t\tis part of a cycle\n"); 347*0Sstevel@tonic-gate #endif /* DEBUG */ 348*0Sstevel@tonic-gate } 349*0Sstevel@tonic-gate dfn_depth -= 1; 350*0Sstevel@tonic-gate } 351