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