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
dfn(nltype * parentp)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
dfn_pre_visit(nltype * parentp)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
dfn_numbered(nltype * childp)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
dfn_busy(nltype * childp)160 dfn_busy(nltype *childp)
161 {
162 if (childp->toporder == DFN_NAN)
163 return (FALSE);
164
165 return (TRUE);
166 }
167
168 void
dfn_findcycle(nltype * childp)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
dfn_self_cycle(nltype * parentp)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
dfn_post_visit(nltype * parentp)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