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