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
35struct dfnstruct {
36	nltype	*nlentryp;
37	int	cycletop;
38};
39
40typedef struct dfnstruct	dfntype;
41
42dfntype	*dfn_stack = NULL;
43int	dfn_depth = 0;
44int	dfn_sz = 0;
45
46int	dfn_counter = DFN_NAN;
47
48/*
49 *	given this parent, depth first number its children.
50 */
51void
52dfn(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 */
108void
109dfn_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 */
152bool
153dfn_numbered(nltype *childp)
154{
155	return (childp->toporder != DFN_NAN && childp->toporder != DFN_BUSY);
156}
157
158/*
159 *	are we already busy?
160 */
161bool
162dfn_busy(nltype *childp)
163{
164	if (childp->toporder == DFN_NAN)
165		return (FALSE);
166
167	return (TRUE);
168}
169
170void
171dfn_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 */
296void
297dfn_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 */
317void
318dfn_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