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