[unix-history] / usr.bin / gprof / dfn.c

/*
 * Copyright (c) 1983 Regents of the University of California.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by the University of
 *	California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#ifndef lint
static char sccsid[] = "@(#)dfn.c	5.4 (Berkeley) 6/1/90";
#endif /* not lint */

#include <stdio.h>
#include "gprof.h"

#define	DFN_DEPTH	100
struct dfnstruct {
    nltype	*nlentryp;
    int		cycletop;
};
typedef struct dfnstruct	dfntype;

dfntype	dfn_stack[ DFN_DEPTH ];
int	dfn_depth = 0;

int	dfn_counter = DFN_NAN;

    /*
     *	given this parent, depth first number its children.
     */
dfn( parentp )
    nltype	*parentp;
{
    arctype	*arcp;

#   ifdef DEBUG
	if ( debug & DFNDEBUG ) {
	    printf( "[dfn] dfn(" );
	    printname( parentp );
	    printf( ")\n" );
	}
#   endif DEBUG
	/*
	 *	if we're already numbered, no need to look any furthur.
	 */
    if ( dfn_numbered( parentp ) ) {
	return;
    }
	/*
	 *	if we're already busy, must be a cycle
	 */
    if ( dfn_busy( parentp ) ) {
	dfn_findcycle( parentp );
	return;
    }
	/*
	 *	visit yourself before your children
	 */
    dfn_pre_visit( parentp );
	/*
	 *	visit children
	 */
    for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
	    dfn( arcp -> arc_childp );
    }
	/*
	 *	visit yourself after your children
	 */
    dfn_post_visit( parentp );
}

    /*
     *	push a parent onto the stack and mark it busy
     */
dfn_pre_visit( parentp )
    nltype	*parentp;
{

    dfn_depth += 1;
    if ( dfn_depth >= DFN_DEPTH ) {
	fprintf( stderr , "[dfn] out of my depth (dfn_stack overflow)\n" );
	exit( 1 );
    }
    dfn_stack[ dfn_depth ].nlentryp = parentp;
    dfn_stack[ dfn_depth ].cycletop = dfn_depth;
    parentp -> toporder = DFN_BUSY;
#   ifdef DEBUG
	if ( debug & DFNDEBUG ) {
	    printf( "[dfn_pre_visit]\t\t%d:" , dfn_depth );
	    printname( parentp );
	    printf( "\n" );
	}
#   endif DEBUG
}

    /*
     *	are we already numbered?
     */
bool
dfn_numbered( childp )
    nltype	*childp;
{
    
    return ( childp -> toporder != DFN_NAN && childp -> toporder != DFN_BUSY );
}

    /*
     *	are we already busy?
     */
bool
dfn_busy( childp )
    nltype	*childp;
{

    if ( childp -> toporder == DFN_NAN ) {
	return FALSE;
    }
    return TRUE;
}

    /*
     *	MISSING: an explanation
     */
dfn_findcycle( childp )
    nltype	*childp;
{
    int		cycletop;
    nltype	*cycleheadp;
    nltype	*tailp;
    int		index;

    for ( cycletop = dfn_depth ; cycletop > 0 ; cycletop -= 1 ) {
	cycleheadp = dfn_stack[ cycletop ].nlentryp;
	if ( childp == cycleheadp ) {
	    break;
	}
	if ( childp -> cyclehead != childp &&
	    childp -> cyclehead == cycleheadp ) {
	    break;
	}
    }
    if ( cycletop <= 0 ) {
	fprintf( stderr , "[dfn_findcycle] couldn't find head of cycle\n" );
	exit( 1 );
    }
#   ifdef DEBUG
	if ( debug & DFNDEBUG ) {
	    printf( "[dfn_findcycle] dfn_depth %d cycletop %d " ,
		    dfn_depth , cycletop  );
	    printname( cycleheadp );
	    printf( "\n" );
	}
#   endif DEBUG
    if ( cycletop == dfn_depth ) {
	    /*
	     *	this is previous function, e.g. this calls itself
	     *	sort of boring
	     */
	dfn_self_cycle( childp );
    } else {
	    /*
	     *	glom intervening functions that aren't already
	     *	glommed into this cycle.
	     *	things have been glommed when their cyclehead field
	     *	points to the head of the cycle they are glommed into.
	     */
	for ( tailp = cycleheadp ; tailp -> cnext ; tailp = tailp -> cnext ) {
	    /* void: chase down to tail of things already glommed */
#	    ifdef DEBUG
		if ( debug & DFNDEBUG ) {
		    printf( "[dfn_findcycle] tail " );
		    printname( tailp );
		    printf( "\n" );
		}
#	    endif DEBUG
	}
	    /*
	     *	if what we think is the top of the cycle
	     *	has a cyclehead field, then it's not really the
	     *	head of the cycle, which is really what we want
	     */	
	if ( cycleheadp -> cyclehead != cycleheadp ) {
	    cycleheadp = cycleheadp -> cyclehead;
#	    ifdef DEBUG
		if ( debug & DFNDEBUG ) {
		    printf( "[dfn_findcycle] new cyclehead " );
		    printname( cycleheadp );
		    printf( "\n" );
		}
#	    endif DEBUG
	}
	for ( index = cycletop + 1 ; index <= dfn_depth ; index += 1 ) {
	    childp = dfn_stack[ index ].nlentryp;
	    if ( childp -> cyclehead == childp ) {
		    /*
		     *	not yet glommed anywhere, glom it
		     *	and fix any children it has glommed
		     */
		tailp -> cnext = childp;
		childp -> cyclehead = cycleheadp;
#		ifdef DEBUG
		    if ( debug & DFNDEBUG ) {
			printf( "[dfn_findcycle] glomming " );
			printname( childp );
			printf( " onto " );
			printname( cycleheadp );
			printf( "\n" );
		    }
#		endif DEBUG
		for ( tailp = childp ; tailp->cnext ; tailp = tailp->cnext ) {
		    tailp -> cnext -> cyclehead = cycleheadp;
#		    ifdef DEBUG
			if ( debug & DFNDEBUG ) {
			    printf( "[dfn_findcycle] and its tail " );
			    printname( tailp -> cnext );
			    printf( " onto " );
			    printname( cycleheadp );
			    printf( "\n" );
			}
#		    endif DEBUG
		}
	    } else if ( childp -> cyclehead != cycleheadp /* firewall */ ) {
		fprintf( stderr ,
			"[dfn_busy] glommed, but not to cyclehead\n" );
	    }
	}
    }
}

    /*
     *	deal with self-cycles
     *	for lint: ARGSUSED
     */
dfn_self_cycle( parentp )
    nltype	*parentp;
{
	/*
	 *	since we are taking out self-cycles elsewhere
	 *	no need for the special case, here.
	 */
#   ifdef DEBUG
	if ( debug & DFNDEBUG ) {
	    printf( "[dfn_self_cycle] " );
	    printname( parentp );
	    printf( "\n" );
	}
#   endif DEBUG
}

    /*
     *	visit a node after all its children
     *	[MISSING: an explanation]
     *	and pop it off the stack
     */
dfn_post_visit( parentp )
    nltype	*parentp;
{
    nltype	*memberp;

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