dfn.c revision 8874 
1107457Snyan/*
2107457Snyan * Copyright (c) 1983, 1993
3107457Snyan *	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
35static char sccsid[] = "@(#)dfn.c	8.1 (Berkeley) 6/6/93";
36#endif /* not lint */
37
38#include <stdio.h>
39#include "gprof.h"
40
41#define	DFN_DEPTH	100
42struct dfnstruct {
43    nltype	*nlentryp;
44    int		cycletop;
45};
46typedef struct dfnstruct	dfntype;
47
48dfntype	dfn_stack[ DFN_DEPTH ];
49int	dfn_depth;
50
51int	dfn_counter;
52
53dfn_init()
54{
55
56    dfn_depth = 0;
57    dfn_counter = DFN_NAN;
58}
59
60    /*
61     *	given this parent, depth first number its children.
62     */
63dfn( parentp )
64    nltype	*parentp;
65{
66    arctype	*arcp;
67
68#   ifdef DEBUG
69	if ( debug & DFNDEBUG ) {
70	    printf( "[dfn] dfn(" );
71	    printname( parentp );
72	    printf( ")\n" );
73	}
74#   endif DEBUG
75	/*
76	 *	if we're already numbered, no need to look any furthur.
77	 */
78    if ( dfn_numbered( parentp ) ) {
79	return;
80    }
81	/*
82	 *	if we're already busy, must be a cycle
83	 */
84    if ( dfn_busy( parentp ) ) {
85	dfn_findcycle( parentp );
86	return;
87    }
88	/*
89	 *	visit yourself before your children
90	 */
91    dfn_pre_visit( parentp );
92	/*
93	 *	visit children
94	 */
95    for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
96	    if ( arcp -> arc_flags & DEADARC )
97		continue;
98	    dfn( arcp -> arc_childp );
99    }
100	/*
101	 *	visit yourself after your children
102	 */
103    dfn_post_visit( parentp );
104}
105
106    /*
107     *	push a parent onto the stack and mark it busy
108     */
109dfn_pre_visit( parentp )
110    nltype	*parentp;
111{
112
113    dfn_depth += 1;
114    if ( dfn_depth >= DFN_DEPTH ) {
115	fprintf( stderr , "[dfn] out of my depth (dfn_stack overflow)\n" );
116	exit( 1 );
117    }
118    dfn_stack[ dfn_depth ].nlentryp = parentp;
119    dfn_stack[ dfn_depth ].cycletop = dfn_depth;
120    parentp -> toporder = DFN_BUSY;
121#   ifdef DEBUG
122	if ( debug & DFNDEBUG ) {
123	    printf( "[dfn_pre_visit]\t\t%d:" , dfn_depth );
124	    printname( parentp );
125	    printf( "\n" );
126	}
127#   endif DEBUG
128}
129
130    /*
131     *	are we already numbered?
132     */
133bool
134dfn_numbered( childp )
135    nltype	*childp;
136{
137
138    return ( childp -> toporder != DFN_NAN && childp -> toporder != DFN_BUSY );
139}
140
141    /*
142     *	are we already busy?
143     */
144bool
145dfn_busy( childp )
146    nltype	*childp;
147{
148
149    if ( childp -> toporder == DFN_NAN ) {
150	return FALSE;
151    }
152    return TRUE;
153}
154
155    /*
156     *	MISSING: an explanation
157     */
158dfn_findcycle( childp )
159    nltype	*childp;
160{
161    int		cycletop;
162    nltype	*cycleheadp;
163    nltype	*tailp;
164    int		index;
165
166    for ( cycletop = dfn_depth ; cycletop > 0 ; cycletop -= 1 ) {
167	cycleheadp = dfn_stack[ cycletop ].nlentryp;
168	if ( childp == cycleheadp ) {
169	    break;
170	}
171	if ( childp -> cyclehead != childp &&
172	    childp -> cyclehead == cycleheadp ) {
173	    break;
174	}
175    }
176    if ( cycletop <= 0 ) {
177	fprintf( stderr , "[dfn_findcycle] couldn't find head of cycle\n" );
178	exit( 1 );
179    }
180#   ifdef DEBUG
181	if ( debug & DFNDEBUG ) {
182	    printf( "[dfn_findcycle] dfn_depth %d cycletop %d " ,
183		    dfn_depth , cycletop  );
184	    printname( cycleheadp );
185	    printf( "\n" );
186	}
187#   endif DEBUG
188    if ( cycletop == dfn_depth ) {
189	    /*
190	     *	this is previous function, e.g. this calls itself
191	     *	sort of boring
192	     */
193	dfn_self_cycle( childp );
194    } else {
195	    /*
196	     *	glom intervening functions that aren't already
197	     *	glommed into this cycle.
198	     *	things have been glommed when their cyclehead field
199	     *	points to the head of the cycle they are glommed into.
200	     */
201	for ( tailp = cycleheadp ; tailp -> cnext ; tailp = tailp -> cnext ) {
202	    /* void: chase down to tail of things already glommed */
203#	    ifdef DEBUG
204		if ( debug & DFNDEBUG ) {
205		    printf( "[dfn_findcycle] tail " );
206		    printname( tailp );
207		    printf( "\n" );
208		}
209#	    endif DEBUG
210	}
211	    /*
212	     *	if what we think is the top of the cycle
213	     *	has a cyclehead field, then it's not really the
214	     *	head of the cycle, which is really what we want
215	     */
216	if ( cycleheadp -> cyclehead != cycleheadp ) {
217	    cycleheadp = cycleheadp -> cyclehead;
218#	    ifdef DEBUG
219		if ( debug & DFNDEBUG ) {
220		    printf( "[dfn_findcycle] new cyclehead " );
221		    printname( cycleheadp );
222		    printf( "\n" );
223		}
224#	    endif DEBUG
225	}
226	for ( index = cycletop + 1 ; index <= dfn_depth ; index += 1 ) {
227	    childp = dfn_stack[ index ].nlentryp;
228	    if ( childp -> cyclehead == childp ) {
229		    /*
230		     *	not yet glommed anywhere, glom it
231		     *	and fix any children it has glommed
232		     */
233		tailp -> cnext = childp;
234		childp -> cyclehead = cycleheadp;
235#		ifdef DEBUG
236		    if ( debug & DFNDEBUG ) {
237			printf( "[dfn_findcycle] glomming " );
238			printname( childp );
239			printf( " onto " );
240			printname( cycleheadp );
241			printf( "\n" );
242		    }
243#		endif DEBUG
244		for ( tailp = childp ; tailp->cnext ; tailp = tailp->cnext ) {
245		    tailp -> cnext -> cyclehead = cycleheadp;
246#		    ifdef DEBUG
247			if ( debug & DFNDEBUG ) {
248			    printf( "[dfn_findcycle] and its tail " );
249			    printname( tailp -> cnext );
250			    printf( " onto " );
251			    printname( cycleheadp );
252			    printf( "\n" );
253			}
254#		    endif DEBUG
255		}
256	    } else if ( childp -> cyclehead != cycleheadp /* firewall */ ) {
257		fprintf( stderr ,
258			"[dfn_busy] glommed, but not to cyclehead\n" );
259	    }
260	}
261    }
262}
263
264    /*
265     *	deal with self-cycles
266     *	for lint: ARGSUSED
267     */
268dfn_self_cycle( parentp )
269    nltype	*parentp;
270{
271	/*
272	 *	since we are taking out self-cycles elsewhere
273	 *	no need for the special case, here.
274	 */
275#   ifdef DEBUG
276	if ( debug & DFNDEBUG ) {
277	    printf( "[dfn_self_cycle] " );
278	    printname( parentp );
279	    printf( "\n" );
280	}
281#   endif DEBUG
282}
283
284    /*
285     *	visit a node after all its children
286     *	[MISSING: an explanation]
287     *	and pop it off the stack
288     */
289dfn_post_visit( parentp )
290    nltype	*parentp;
291{
292    nltype	*memberp;
293
294#   ifdef DEBUG
295	if ( debug & DFNDEBUG ) {
296	    printf( "[dfn_post_visit]\t%d: " , dfn_depth );
297	    printname( parentp );
298	    printf( "\n" );
299	}
300#   endif DEBUG
301	/*
302	 *	number functions and things in their cycles
303	 *	unless the function is itself part of a cycle
304	 */
305    if ( parentp -> cyclehead == parentp ) {
306	dfn_counter += 1;
307	for ( memberp = parentp ; memberp ; memberp = memberp -> cnext ) {
308	    memberp -> toporder = dfn_counter;
309#	    ifdef DEBUG
310		if ( debug & DFNDEBUG ) {
311		    printf( "[dfn_post_visit]\t\tmember " );
312		    printname( memberp );
313		    printf( " -> toporder = %d\n" , dfn_counter );
314		}
315#	    endif DEBUG
316	}
317    } else {
318#	ifdef DEBUG
319	    if ( debug & DFNDEBUG ) {
320		printf( "[dfn_post_visit]\t\tis part of a cycle\n" );
321	    }
322#	endif DEBUG
323    }
324    dfn_depth -= 1;
325}
326