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