dfn.c revision 97631 
1/*
2 * Copyright (c) 1983, 1993
3 *	The Regents of the University of California.  All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in the
12 *    documentation and/or other materials provided with the distribution.
13 * 3. All advertising materials mentioning features or use of this software
14 *    must display the following acknowledgement:
15 *	This product includes software developed by the University of
16 *	California, Berkeley and its contributors.
17 * 4. Neither the name of the University nor the names of its contributors
18 *    may be used to endorse or promote products derived from this software
19 *    without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 */
33
34#ifndef lint
35#if 0
36static char sccsid[] = "@(#)dfn.c	8.1 (Berkeley) 6/6/93";
37#endif
38static const char rcsid[] =
39  "$FreeBSD: head/usr.bin/gprof/dfn.c 97631 2002-05-30 21:18:01Z wollman $";
40#endif /* not lint */
41
42#include <stdio.h>
43#include "gprof.h"
44
45#define	DFN_DEPTH	100
46struct dfnstruct {
47    nltype	*nlentryp;
48    int		cycletop;
49};
50typedef struct dfnstruct	dfntype;
51
52dfntype	dfn_stack[ DFN_DEPTH ];
53int	dfn_depth;
54
55int	dfn_counter;
56
57dfn_init()
58{
59
60    dfn_depth = 0;
61    dfn_counter = DFN_NAN;
62}
63
64    /*
65     *	given this parent, depth first number its children.
66     */
67dfn( parentp )
68    nltype	*parentp;
69{
70    arctype	*arcp;
71
72#   ifdef DEBUG
73	if ( debug & DFNDEBUG ) {
74	    printf( "[dfn] dfn(" );
75	    printname( parentp );
76	    printf( ")\n" );
77	}
78#   endif /* DEBUG */
79	/*
80	 *	if we're already numbered, no need to look any furthur.
81	 */
82    if ( dfn_numbered( parentp ) ) {
83	return;
84    }
85	/*
86	 *	if we're already busy, must be a cycle
87	 */
88    if ( dfn_busy( parentp ) ) {
89	dfn_findcycle( parentp );
90	return;
91    }
92	/*
93	 *	visit yourself before your children
94	 */
95    dfn_pre_visit( parentp );
96	/*
97	 *	visit children
98	 */
99    for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
100	    if ( arcp -> arc_flags & DEADARC )
101		continue;
102	    dfn( arcp -> arc_childp );
103    }
104	/*
105	 *	visit yourself after your children
106	 */
107    dfn_post_visit( parentp );
108}
109
110    /*
111     *	push a parent onto the stack and mark it busy
112     */
113dfn_pre_visit( parentp )
114    nltype	*parentp;
115{
116
117    dfn_depth += 1;
118    if ( dfn_depth >= DFN_DEPTH ) {
119	fprintf( stderr , "[dfn] out of my depth (dfn_stack overflow)\n" );
120	exit( 1 );
121    }
122    dfn_stack[ dfn_depth ].nlentryp = parentp;
123    dfn_stack[ dfn_depth ].cycletop = dfn_depth;
124    parentp -> toporder = DFN_BUSY;
125#   ifdef DEBUG
126	if ( debug & DFNDEBUG ) {
127	    printf( "[dfn_pre_visit]\t\t%d:" , dfn_depth );
128	    printname( parentp );
129	    printf( "\n" );
130	}
131#   endif /* DEBUG */
132}
133
134    /*
135     *	are we already numbered?
136     */
137bool
138dfn_numbered( childp )
139    nltype	*childp;
140{
141
142    return ( childp -> toporder != DFN_NAN && childp -> toporder != DFN_BUSY );
143}
144
145    /*
146     *	are we already busy?
147     */
148bool
149dfn_busy( childp )
150    nltype	*childp;
151{
152
153    if ( childp -> toporder == DFN_NAN ) {
154	return FALSE;
155    }
156    return TRUE;
157}
158
159    /*
160     *	MISSING: an explanation
161     */
162dfn_findcycle( childp )
163    nltype	*childp;
164{
165    int		cycletop;
166    nltype	*cycleheadp;
167    nltype	*tailp;
168    int		index;
169
170    for ( cycletop = dfn_depth ; cycletop > 0 ; cycletop -= 1 ) {
171	cycleheadp = dfn_stack[ cycletop ].nlentryp;
172	if ( childp == cycleheadp ) {
173	    break;
174	}
175	if ( childp -> cyclehead != childp &&
176	    childp -> cyclehead == cycleheadp ) {
177	    break;
178	}
179    }
180    if ( cycletop <= 0 ) {
181	fprintf( stderr , "[dfn_findcycle] couldn't find head of cycle\n" );
182	exit( 1 );
183    }
184#   ifdef DEBUG
185	if ( debug & DFNDEBUG ) {
186	    printf( "[dfn_findcycle] dfn_depth %d cycletop %d " ,
187		    dfn_depth , cycletop  );
188	    printname( cycleheadp );
189	    printf( "\n" );
190	}
191#   endif /* DEBUG */
192    if ( cycletop == dfn_depth ) {
193	    /*
194	     *	this is previous function, e.g. this calls itself
195	     *	sort of boring
196	     */
197	dfn_self_cycle( childp );
198    } else {
199	    /*
200	     *	glom intervening functions that aren't already
201	     *	glommed into this cycle.
202	     *	things have been glommed when their cyclehead field
203	     *	points to the head of the cycle they are glommed into.
204	     */
205	for ( tailp = cycleheadp ; tailp -> cnext ; tailp = tailp -> cnext ) {
206	    /* void: chase down to tail of things already glommed */
207#	    ifdef DEBUG
208		if ( debug & DFNDEBUG ) {
209		    printf( "[dfn_findcycle] tail " );
210		    printname( tailp );
211		    printf( "\n" );
212		}
213#	    endif /* DEBUG */
214	}
215	    /*
216	     *	if what we think is the top of the cycle
217	     *	has a cyclehead field, then it's not really the
218	     *	head of the cycle, which is really what we want
219	     */
220	if ( cycleheadp -> cyclehead != cycleheadp ) {
221	    cycleheadp = cycleheadp -> cyclehead;
222#	    ifdef DEBUG
223		if ( debug & DFNDEBUG ) {
224		    printf( "[dfn_findcycle] new cyclehead " );
225		    printname( cycleheadp );
226		    printf( "\n" );
227		}
228#	    endif /* DEBUG */
229	}
230	for ( index = cycletop + 1 ; index <= dfn_depth ; index += 1 ) {
231	    childp = dfn_stack[ index ].nlentryp;
232	    if ( childp -> cyclehead == childp ) {
233		    /*
234		     *	not yet glommed anywhere, glom it
235		     *	and fix any children it has glommed
236		     */
237		tailp -> cnext = childp;
238		childp -> cyclehead = cycleheadp;
239#		ifdef DEBUG
240		    if ( debug & DFNDEBUG ) {
241			printf( "[dfn_findcycle] glomming " );
242			printname( childp );
243			printf( " onto " );
244			printname( cycleheadp );
245			printf( "\n" );
246		    }
247#		endif /* DEBUG */
248		for ( tailp = childp ; tailp->cnext ; tailp = tailp->cnext ) {
249		    tailp -> cnext -> cyclehead = cycleheadp;
250#		    ifdef DEBUG
251			if ( debug & DFNDEBUG ) {
252			    printf( "[dfn_findcycle] and its tail " );
253			    printname( tailp -> cnext );
254			    printf( " onto " );
255			    printname( cycleheadp );
256			    printf( "\n" );
257			}
258#		    endif /* DEBUG */
259		}
260	    } else if ( childp -> cyclehead != cycleheadp /* firewall */ ) {
261		fprintf( stderr ,
262			"[dfn_busy] glommed, but not to cyclehead\n" );
263	    }
264	}
265    }
266}
267
268    /*
269     *	deal with self-cycles
270     *	for lint: ARGSUSED
271     */
272dfn_self_cycle( parentp )
273    nltype	*parentp;
274{
275	/*
276	 *	since we are taking out self-cycles elsewhere
277	 *	no need for the special case, here.
278	 */
279#   ifdef DEBUG
280	if ( debug & DFNDEBUG ) {
281	    printf( "[dfn_self_cycle] " );
282	    printname( parentp );
283	    printf( "\n" );
284	}
285#   endif /* DEBUG */
286}
287
288    /*
289     *	visit a node after all its children
290     *	[MISSING: an explanation]
291     *	and pop it off the stack
292     */
293dfn_post_visit( parentp )
294    nltype	*parentp;
295{
296    nltype	*memberp;
297
298#   ifdef DEBUG
299	if ( debug & DFNDEBUG ) {
300	    printf( "[dfn_post_visit]\t%d: " , dfn_depth );
301	    printname( parentp );
302	    printf( "\n" );
303	}
304#   endif /* DEBUG */
305	/*
306	 *	number functions and things in their cycles
307	 *	unless the function is itself part of a cycle
308	 */
309    if ( parentp -> cyclehead == parentp ) {
310	dfn_counter += 1;
311	for ( memberp = parentp ; memberp ; memberp = memberp -> cnext ) {
312	    memberp -> toporder = dfn_counter;
313#	    ifdef DEBUG
314		if ( debug & DFNDEBUG ) {
315		    printf( "[dfn_post_visit]\t\tmember " );
316		    printname( memberp );
317		    printf( " -> toporder = %d\n" , dfn_counter );
318		}
319#	    endif /* DEBUG */
320	}
321    } else {
322#	ifdef DEBUG
323	    if ( debug & DFNDEBUG ) {
324		printf( "[dfn_post_visit]\t\tis part of a cycle\n" );
325	    }
326#	endif /* DEBUG */
327    }
328    dfn_depth -= 1;
329}
330