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 * Copyright (c) 1990-1997,2001 by Sun Microsystems, Inc. 24 * All rights reserved. 25 */ 26 27 #pragma ident "%Z%%M% %I% %E% SMI" 28 29 #include <stdio.h> 30 #include "gprof.h" 31 32 #define DFN_DEPTH 100 33 34 struct dfnstruct { 35 nltype *nlentryp; 36 int cycletop; 37 }; 38 39 typedef struct dfnstruct dfntype; 40 41 dfntype *dfn_stack = NULL; 42 int dfn_depth = 0; 43 int dfn_sz = 0; 44 45 int dfn_counter = DFN_NAN; 46 47 /* 48 * given this parent, depth first number its children. 49 */ 50 void 51 dfn(nltype *parentp) 52 { 53 arctype *arcp; 54 55 #ifdef DEBUG 56 if (debug & DFNDEBUG) { 57 printf("[dfn] dfn("); 58 printname(parentp); 59 printf(")\n"); 60 } 61 #endif /* DEBUG */ 62 63 if (!dfn_stack) { 64 dfn_sz = DFN_DEPTH; 65 dfn_stack = (dfntype *) malloc(dfn_sz * sizeof (dfntype)); 66 if (!dfn_stack) { 67 fprintf(stderr, 68 "fatal: can't malloc %d objects\n", dfn_sz); 69 exit(1); 70 } 71 } 72 73 /* 74 * if we're already numbered, no need to look any furthur. 75 */ 76 if (dfn_numbered(parentp)) 77 return; 78 79 /* 80 * if we're already busy, must be a cycle 81 */ 82 if (dfn_busy(parentp)) { 83 dfn_findcycle(parentp); 84 return; 85 } 86 87 /* 88 * visit yourself before your children 89 */ 90 dfn_pre_visit(parentp); 91 92 /* 93 * visit children 94 */ 95 for (arcp = parentp->children; arcp; arcp = arcp->arc_childlist) 96 dfn(arcp->arc_childp); 97 98 /* 99 * visit yourself after your children 100 */ 101 dfn_post_visit(parentp); 102 } 103 104 /* 105 * push a parent onto the stack and mark it busy 106 */ 107 void 108 dfn_pre_visit(nltype *parentp) 109 { 110 111 if (!dfn_stack) { 112 dfn_sz = DFN_DEPTH; 113 dfn_stack = (dfntype *) malloc(dfn_sz * sizeof (dfntype)); 114 if (!dfn_stack) { 115 printf("fatal: can't malloc %d objects\n", 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 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 printf("[dfn_pre_visit]\t\t%d:", dfn_depth); 141 printname(parentp); 142 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; 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 fprintf(stderr, "[dfn_findcycle] couldn't find head " 192 "of cycle for %s\n", childp->name); 193 return; 194 } 195 } 196 197 #ifdef DEBUG 198 if (debug & DFNDEBUG) { 199 printf("[dfn_findcycle] dfn_depth %d cycletop %d ", 200 dfn_depth, cycletop); 201 printname(cycleheadp); 202 printf("\n"); 203 } 204 #endif /* DEBUG */ 205 206 if (cycletop == dfn_depth) { 207 /* 208 * this is previous function, e.g. this calls itself 209 * sort of boring 210 */ 211 dfn_self_cycle(childp); 212 } else { 213 /* 214 * glom intervening functions that aren't already 215 * glommed into this cycle. 216 * things have been glommed when their cyclehead field 217 * points to the head of the cycle they are glommed into. 218 */ 219 for (tailp = cycleheadp; tailp->cnext; tailp = tailp->cnext) { 220 /* void: chase down to tail of things already glommed */ 221 #ifdef DEBUG 222 if (debug & DFNDEBUG) { 223 printf("[dfn_findcycle] tail "); 224 printname(tailp); 225 printf("\n"); 226 } 227 #endif /* DEBUG */ 228 } 229 230 /* 231 * if what we think is the top of the cycle 232 * has a cyclehead field, then it's not really the 233 * head of the cycle, which is really what we want 234 */ 235 if (cycleheadp->cyclehead != cycleheadp) { 236 cycleheadp = cycleheadp->cyclehead; 237 #ifdef DEBUG 238 if (debug & DFNDEBUG) { 239 printf("[dfn_findcycle] new cyclehead "); 240 printname(cycleheadp); 241 printf("\n"); 242 } 243 #endif /* DEBUG */ 244 } 245 246 for (index = cycletop + 1; index <= dfn_depth; index += 1) { 247 248 childp = dfn_stack[index].nlentryp; 249 if (childp->cyclehead == childp) { 250 /* 251 * not yet glommed anywhere, glom it 252 * and fix any children it has glommed 253 */ 254 tailp->cnext = childp; 255 childp->cyclehead = cycleheadp; 256 #ifdef DEBUG 257 if (debug & DFNDEBUG) { 258 printf("[dfn_findcycle] glomming "); 259 printname(childp); 260 printf(" onto "); 261 printname(cycleheadp); 262 printf("\n"); 263 } 264 #endif /* DEBUG */ 265 for (tailp = childp; tailp->cnext; 266 tailp = tailp->cnext) { 267 tailp->cnext->cyclehead = cycleheadp; 268 #ifdef DEBUG 269 if (debug & DFNDEBUG) { 270 printf("[dfn_findcycle]" 271 " and its tail "); 272 printname(tailp->cnext); 273 printf(" onto "); 274 printname(cycleheadp); 275 printf("\n"); 276 } 277 #endif /* DEBUG */ 278 } 279 } else if (childp->cyclehead != cycleheadp) { 280 fprintf(stderr, "[dfn_busy] glommed," 281 " but not to cyclehead\n"); 282 } 283 } 284 } 285 } 286 287 /* 288 * deal with self-cycles 289 * for lint: ARGSUSED 290 */ 291 /* ARGSUSED */ 292 void 293 dfn_self_cycle(nltype *parentp) 294 { 295 /* 296 * since we are taking out self-cycles elsewhere 297 * no need for the special case, here. 298 */ 299 #ifdef DEBUG 300 if (debug & DFNDEBUG) { 301 printf("[dfn_self_cycle] "); 302 printname(parentp); 303 printf("\n"); 304 } 305 #endif /* DEBUG */ 306 } 307 308 /* 309 * visit a node after all its children 310 * [MISSING: an explanation] 311 * and pop it off the stack 312 */ 313 void 314 dfn_post_visit(nltype *parentp) 315 { 316 nltype *memberp; 317 318 #ifdef DEBUG 319 if (debug & DFNDEBUG) { 320 printf("[dfn_post_visit]\t%d: ", dfn_depth); 321 printname(parentp); 322 printf("\n"); 323 } 324 #endif /* DEBUG */ 325 /* 326 * number functions and things in their cycles 327 * unless the function is itself part of a cycle 328 */ 329 if (parentp->cyclehead == parentp) { 330 dfn_counter += 1; 331 332 for (memberp = parentp; memberp; memberp = memberp->cnext) { 333 334 memberp->toporder = dfn_counter; 335 #ifdef DEBUG 336 if (debug & DFNDEBUG) { 337 printf("[dfn_post_visit]\t\tmember "); 338 printname(memberp); 339 printf(" -> toporder = %d\n", dfn_counter); 340 } 341 #endif /* DEBUG */ 342 } 343 #ifdef DEBUG 344 } else { 345 if (debug & DFNDEBUG) 346 printf("[dfn_post_visit]\t\tis part of a cycle\n"); 347 #endif /* DEBUG */ 348 } 349 dfn_depth -= 1; 350 } 351