xref: /freebsd/usr.bin/gprof/dfn.c (revision e026a48c34d396fe7d0e382673a69bc047c0bfca)
19b50d902SRodney W. Grimes /*
29b50d902SRodney W. Grimes  * Copyright (c) 1983, 1993
39b50d902SRodney W. Grimes  *	The Regents of the University of California.  All rights reserved.
49b50d902SRodney W. Grimes  *
59b50d902SRodney W. Grimes  * Redistribution and use in source and binary forms, with or without
69b50d902SRodney W. Grimes  * modification, are permitted provided that the following conditions
79b50d902SRodney W. Grimes  * are met:
89b50d902SRodney W. Grimes  * 1. Redistributions of source code must retain the above copyright
99b50d902SRodney W. Grimes  *    notice, this list of conditions and the following disclaimer.
109b50d902SRodney W. Grimes  * 2. Redistributions in binary form must reproduce the above copyright
119b50d902SRodney W. Grimes  *    notice, this list of conditions and the following disclaimer in the
129b50d902SRodney W. Grimes  *    documentation and/or other materials provided with the distribution.
139b50d902SRodney W. Grimes  * 3. All advertising materials mentioning features or use of this software
149b50d902SRodney W. Grimes  *    must display the following acknowledgement:
159b50d902SRodney W. Grimes  *	This product includes software developed by the University of
169b50d902SRodney W. Grimes  *	California, Berkeley and its contributors.
179b50d902SRodney W. Grimes  * 4. Neither the name of the University nor the names of its contributors
189b50d902SRodney W. Grimes  *    may be used to endorse or promote products derived from this software
199b50d902SRodney W. Grimes  *    without specific prior written permission.
209b50d902SRodney W. Grimes  *
219b50d902SRodney W. Grimes  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
229b50d902SRodney W. Grimes  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
239b50d902SRodney W. Grimes  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
249b50d902SRodney W. Grimes  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
259b50d902SRodney W. Grimes  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
269b50d902SRodney W. Grimes  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
279b50d902SRodney W. Grimes  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
289b50d902SRodney W. Grimes  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
299b50d902SRodney W. Grimes  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
309b50d902SRodney W. Grimes  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
319b50d902SRodney W. Grimes  * SUCH DAMAGE.
329b50d902SRodney W. Grimes  */
339b50d902SRodney W. Grimes 
349b50d902SRodney W. Grimes #ifndef lint
350fb7a0beSGarrett Wollman #if 0
369b50d902SRodney W. Grimes static char sccsid[] = "@(#)dfn.c	8.1 (Berkeley) 6/6/93";
370fb7a0beSGarrett Wollman #endif
380fb7a0beSGarrett Wollman static const char rcsid[] =
390fb7a0beSGarrett Wollman   "$FreeBSD$";
409b50d902SRodney W. Grimes #endif /* not lint */
41e026a48cSDavid E. O'Brien #include <sys/cdefs.h>
42e026a48cSDavid E. O'Brien __FBSDID("$FreeBSD$");
439b50d902SRodney W. Grimes 
449b50d902SRodney W. Grimes #include <stdio.h>
459b50d902SRodney W. Grimes #include "gprof.h"
469b50d902SRodney W. Grimes 
479b50d902SRodney W. Grimes #define	DFN_DEPTH	100
489b50d902SRodney W. Grimes struct dfnstruct {
499b50d902SRodney W. Grimes     nltype	*nlentryp;
509b50d902SRodney W. Grimes     int		cycletop;
519b50d902SRodney W. Grimes };
529b50d902SRodney W. Grimes typedef struct dfnstruct	dfntype;
539b50d902SRodney W. Grimes 
549b50d902SRodney W. Grimes dfntype	dfn_stack[ DFN_DEPTH ];
559b50d902SRodney W. Grimes int	dfn_depth;
569b50d902SRodney W. Grimes 
579b50d902SRodney W. Grimes int	dfn_counter;
589b50d902SRodney W. Grimes 
599b50d902SRodney W. Grimes dfn_init()
609b50d902SRodney W. Grimes {
619b50d902SRodney W. Grimes 
629b50d902SRodney W. Grimes     dfn_depth = 0;
639b50d902SRodney W. Grimes     dfn_counter = DFN_NAN;
649b50d902SRodney W. Grimes }
659b50d902SRodney W. Grimes 
669b50d902SRodney W. Grimes     /*
679b50d902SRodney W. Grimes      *	given this parent, depth first number its children.
689b50d902SRodney W. Grimes      */
699b50d902SRodney W. Grimes dfn( parentp )
709b50d902SRodney W. Grimes     nltype	*parentp;
719b50d902SRodney W. Grimes {
729b50d902SRodney W. Grimes     arctype	*arcp;
739b50d902SRodney W. Grimes 
749b50d902SRodney W. Grimes #   ifdef DEBUG
759b50d902SRodney W. Grimes 	if ( debug & DFNDEBUG ) {
769b50d902SRodney W. Grimes 	    printf( "[dfn] dfn(" );
779b50d902SRodney W. Grimes 	    printname( parentp );
789b50d902SRodney W. Grimes 	    printf( ")\n" );
799b50d902SRodney W. Grimes 	}
800fb7a0beSGarrett Wollman #   endif /* DEBUG */
819b50d902SRodney W. Grimes 	/*
829b50d902SRodney W. Grimes 	 *	if we're already numbered, no need to look any furthur.
839b50d902SRodney W. Grimes 	 */
849b50d902SRodney W. Grimes     if ( dfn_numbered( parentp ) ) {
859b50d902SRodney W. Grimes 	return;
869b50d902SRodney W. Grimes     }
879b50d902SRodney W. Grimes 	/*
889b50d902SRodney W. Grimes 	 *	if we're already busy, must be a cycle
899b50d902SRodney W. Grimes 	 */
909b50d902SRodney W. Grimes     if ( dfn_busy( parentp ) ) {
919b50d902SRodney W. Grimes 	dfn_findcycle( parentp );
929b50d902SRodney W. Grimes 	return;
939b50d902SRodney W. Grimes     }
949b50d902SRodney W. Grimes 	/*
959b50d902SRodney W. Grimes 	 *	visit yourself before your children
969b50d902SRodney W. Grimes 	 */
979b50d902SRodney W. Grimes     dfn_pre_visit( parentp );
989b50d902SRodney W. Grimes 	/*
999b50d902SRodney W. Grimes 	 *	visit children
1009b50d902SRodney W. Grimes 	 */
1019b50d902SRodney W. Grimes     for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
1029b50d902SRodney W. Grimes 	    if ( arcp -> arc_flags & DEADARC )
1039b50d902SRodney W. Grimes 		continue;
1049b50d902SRodney W. Grimes 	    dfn( arcp -> arc_childp );
1059b50d902SRodney W. Grimes     }
1069b50d902SRodney W. Grimes 	/*
1079b50d902SRodney W. Grimes 	 *	visit yourself after your children
1089b50d902SRodney W. Grimes 	 */
1099b50d902SRodney W. Grimes     dfn_post_visit( parentp );
1109b50d902SRodney W. Grimes }
1119b50d902SRodney W. Grimes 
1129b50d902SRodney W. Grimes     /*
1139b50d902SRodney W. Grimes      *	push a parent onto the stack and mark it busy
1149b50d902SRodney W. Grimes      */
1159b50d902SRodney W. Grimes dfn_pre_visit( parentp )
1169b50d902SRodney W. Grimes     nltype	*parentp;
1179b50d902SRodney W. Grimes {
1189b50d902SRodney W. Grimes 
1199b50d902SRodney W. Grimes     dfn_depth += 1;
1209b50d902SRodney W. Grimes     if ( dfn_depth >= DFN_DEPTH ) {
1219b50d902SRodney W. Grimes 	fprintf( stderr , "[dfn] out of my depth (dfn_stack overflow)\n" );
1229b50d902SRodney W. Grimes 	exit( 1 );
1239b50d902SRodney W. Grimes     }
1249b50d902SRodney W. Grimes     dfn_stack[ dfn_depth ].nlentryp = parentp;
1259b50d902SRodney W. Grimes     dfn_stack[ dfn_depth ].cycletop = dfn_depth;
1269b50d902SRodney W. Grimes     parentp -> toporder = DFN_BUSY;
1279b50d902SRodney W. Grimes #   ifdef DEBUG
1289b50d902SRodney W. Grimes 	if ( debug & DFNDEBUG ) {
1299b50d902SRodney W. Grimes 	    printf( "[dfn_pre_visit]\t\t%d:" , dfn_depth );
1309b50d902SRodney W. Grimes 	    printname( parentp );
1319b50d902SRodney W. Grimes 	    printf( "\n" );
1329b50d902SRodney W. Grimes 	}
1330fb7a0beSGarrett Wollman #   endif /* DEBUG */
1349b50d902SRodney W. Grimes }
1359b50d902SRodney W. Grimes 
1369b50d902SRodney W. Grimes     /*
1379b50d902SRodney W. Grimes      *	are we already numbered?
1389b50d902SRodney W. Grimes      */
1399b50d902SRodney W. Grimes bool
1409b50d902SRodney W. Grimes dfn_numbered( childp )
1419b50d902SRodney W. Grimes     nltype	*childp;
1429b50d902SRodney W. Grimes {
1439b50d902SRodney W. Grimes 
1449b50d902SRodney W. Grimes     return ( childp -> toporder != DFN_NAN && childp -> toporder != DFN_BUSY );
1459b50d902SRodney W. Grimes }
1469b50d902SRodney W. Grimes 
1479b50d902SRodney W. Grimes     /*
1489b50d902SRodney W. Grimes      *	are we already busy?
1499b50d902SRodney W. Grimes      */
1509b50d902SRodney W. Grimes bool
1519b50d902SRodney W. Grimes dfn_busy( childp )
1529b50d902SRodney W. Grimes     nltype	*childp;
1539b50d902SRodney W. Grimes {
1549b50d902SRodney W. Grimes 
1559b50d902SRodney W. Grimes     if ( childp -> toporder == DFN_NAN ) {
1569b50d902SRodney W. Grimes 	return FALSE;
1579b50d902SRodney W. Grimes     }
1589b50d902SRodney W. Grimes     return TRUE;
1599b50d902SRodney W. Grimes }
1609b50d902SRodney W. Grimes 
1619b50d902SRodney W. Grimes     /*
1629b50d902SRodney W. Grimes      *	MISSING: an explanation
1639b50d902SRodney W. Grimes      */
1649b50d902SRodney W. Grimes dfn_findcycle( childp )
1659b50d902SRodney W. Grimes     nltype	*childp;
1669b50d902SRodney W. Grimes {
1679b50d902SRodney W. Grimes     int		cycletop;
1689b50d902SRodney W. Grimes     nltype	*cycleheadp;
1699b50d902SRodney W. Grimes     nltype	*tailp;
1709b50d902SRodney W. Grimes     int		index;
1719b50d902SRodney W. Grimes 
1729b50d902SRodney W. Grimes     for ( cycletop = dfn_depth ; cycletop > 0 ; cycletop -= 1 ) {
1739b50d902SRodney W. Grimes 	cycleheadp = dfn_stack[ cycletop ].nlentryp;
1749b50d902SRodney W. Grimes 	if ( childp == cycleheadp ) {
1759b50d902SRodney W. Grimes 	    break;
1769b50d902SRodney W. Grimes 	}
1779b50d902SRodney W. Grimes 	if ( childp -> cyclehead != childp &&
1789b50d902SRodney W. Grimes 	    childp -> cyclehead == cycleheadp ) {
1799b50d902SRodney W. Grimes 	    break;
1809b50d902SRodney W. Grimes 	}
1819b50d902SRodney W. Grimes     }
1829b50d902SRodney W. Grimes     if ( cycletop <= 0 ) {
1839b50d902SRodney W. Grimes 	fprintf( stderr , "[dfn_findcycle] couldn't find head of cycle\n" );
1849b50d902SRodney W. Grimes 	exit( 1 );
1859b50d902SRodney W. Grimes     }
1869b50d902SRodney W. Grimes #   ifdef DEBUG
1879b50d902SRodney W. Grimes 	if ( debug & DFNDEBUG ) {
1889b50d902SRodney W. Grimes 	    printf( "[dfn_findcycle] dfn_depth %d cycletop %d " ,
1899b50d902SRodney W. Grimes 		    dfn_depth , cycletop  );
1909b50d902SRodney W. Grimes 	    printname( cycleheadp );
1919b50d902SRodney W. Grimes 	    printf( "\n" );
1929b50d902SRodney W. Grimes 	}
1930fb7a0beSGarrett Wollman #   endif /* DEBUG */
1949b50d902SRodney W. Grimes     if ( cycletop == dfn_depth ) {
1959b50d902SRodney W. Grimes 	    /*
1969b50d902SRodney W. Grimes 	     *	this is previous function, e.g. this calls itself
1979b50d902SRodney W. Grimes 	     *	sort of boring
1989b50d902SRodney W. Grimes 	     */
1999b50d902SRodney W. Grimes 	dfn_self_cycle( childp );
2009b50d902SRodney W. Grimes     } else {
2019b50d902SRodney W. Grimes 	    /*
2029b50d902SRodney W. Grimes 	     *	glom intervening functions that aren't already
2039b50d902SRodney W. Grimes 	     *	glommed into this cycle.
2049b50d902SRodney W. Grimes 	     *	things have been glommed when their cyclehead field
2059b50d902SRodney W. Grimes 	     *	points to the head of the cycle they are glommed into.
2069b50d902SRodney W. Grimes 	     */
2079b50d902SRodney W. Grimes 	for ( tailp = cycleheadp ; tailp -> cnext ; tailp = tailp -> cnext ) {
2089b50d902SRodney W. Grimes 	    /* void: chase down to tail of things already glommed */
2099b50d902SRodney W. Grimes #	    ifdef DEBUG
2109b50d902SRodney W. Grimes 		if ( debug & DFNDEBUG ) {
2119b50d902SRodney W. Grimes 		    printf( "[dfn_findcycle] tail " );
2129b50d902SRodney W. Grimes 		    printname( tailp );
2139b50d902SRodney W. Grimes 		    printf( "\n" );
2149b50d902SRodney W. Grimes 		}
2150fb7a0beSGarrett Wollman #	    endif /* DEBUG */
2169b50d902SRodney W. Grimes 	}
2179b50d902SRodney W. Grimes 	    /*
2189b50d902SRodney W. Grimes 	     *	if what we think is the top of the cycle
2199b50d902SRodney W. Grimes 	     *	has a cyclehead field, then it's not really the
2209b50d902SRodney W. Grimes 	     *	head of the cycle, which is really what we want
2219b50d902SRodney W. Grimes 	     */
2229b50d902SRodney W. Grimes 	if ( cycleheadp -> cyclehead != cycleheadp ) {
2239b50d902SRodney W. Grimes 	    cycleheadp = cycleheadp -> cyclehead;
2249b50d902SRodney W. Grimes #	    ifdef DEBUG
2259b50d902SRodney W. Grimes 		if ( debug & DFNDEBUG ) {
2269b50d902SRodney W. Grimes 		    printf( "[dfn_findcycle] new cyclehead " );
2279b50d902SRodney W. Grimes 		    printname( cycleheadp );
2289b50d902SRodney W. Grimes 		    printf( "\n" );
2299b50d902SRodney W. Grimes 		}
2300fb7a0beSGarrett Wollman #	    endif /* DEBUG */
2319b50d902SRodney W. Grimes 	}
2329b50d902SRodney W. Grimes 	for ( index = cycletop + 1 ; index <= dfn_depth ; index += 1 ) {
2339b50d902SRodney W. Grimes 	    childp = dfn_stack[ index ].nlentryp;
2349b50d902SRodney W. Grimes 	    if ( childp -> cyclehead == childp ) {
2359b50d902SRodney W. Grimes 		    /*
2369b50d902SRodney W. Grimes 		     *	not yet glommed anywhere, glom it
2379b50d902SRodney W. Grimes 		     *	and fix any children it has glommed
2389b50d902SRodney W. Grimes 		     */
2399b50d902SRodney W. Grimes 		tailp -> cnext = childp;
2409b50d902SRodney W. Grimes 		childp -> cyclehead = cycleheadp;
2419b50d902SRodney W. Grimes #		ifdef DEBUG
2429b50d902SRodney W. Grimes 		    if ( debug & DFNDEBUG ) {
2439b50d902SRodney W. Grimes 			printf( "[dfn_findcycle] glomming " );
2449b50d902SRodney W. Grimes 			printname( childp );
2459b50d902SRodney W. Grimes 			printf( " onto " );
2469b50d902SRodney W. Grimes 			printname( cycleheadp );
2479b50d902SRodney W. Grimes 			printf( "\n" );
2489b50d902SRodney W. Grimes 		    }
2490fb7a0beSGarrett Wollman #		endif /* DEBUG */
2509b50d902SRodney W. Grimes 		for ( tailp = childp ; tailp->cnext ; tailp = tailp->cnext ) {
2519b50d902SRodney W. Grimes 		    tailp -> cnext -> cyclehead = cycleheadp;
2529b50d902SRodney W. Grimes #		    ifdef DEBUG
2539b50d902SRodney W. Grimes 			if ( debug & DFNDEBUG ) {
2549b50d902SRodney W. Grimes 			    printf( "[dfn_findcycle] and its tail " );
2559b50d902SRodney W. Grimes 			    printname( tailp -> cnext );
2569b50d902SRodney W. Grimes 			    printf( " onto " );
2579b50d902SRodney W. Grimes 			    printname( cycleheadp );
2589b50d902SRodney W. Grimes 			    printf( "\n" );
2599b50d902SRodney W. Grimes 			}
2600fb7a0beSGarrett Wollman #		    endif /* DEBUG */
2619b50d902SRodney W. Grimes 		}
2629b50d902SRodney W. Grimes 	    } else if ( childp -> cyclehead != cycleheadp /* firewall */ ) {
2639b50d902SRodney W. Grimes 		fprintf( stderr ,
2649b50d902SRodney W. Grimes 			"[dfn_busy] glommed, but not to cyclehead\n" );
2659b50d902SRodney W. Grimes 	    }
2669b50d902SRodney W. Grimes 	}
2679b50d902SRodney W. Grimes     }
2689b50d902SRodney W. Grimes }
2699b50d902SRodney W. Grimes 
2709b50d902SRodney W. Grimes     /*
2719b50d902SRodney W. Grimes      *	deal with self-cycles
2729b50d902SRodney W. Grimes      *	for lint: ARGSUSED
2739b50d902SRodney W. Grimes      */
2749b50d902SRodney W. Grimes dfn_self_cycle( parentp )
2759b50d902SRodney W. Grimes     nltype	*parentp;
2769b50d902SRodney W. Grimes {
2779b50d902SRodney W. Grimes 	/*
2789b50d902SRodney W. Grimes 	 *	since we are taking out self-cycles elsewhere
2799b50d902SRodney W. Grimes 	 *	no need for the special case, here.
2809b50d902SRodney W. Grimes 	 */
2819b50d902SRodney W. Grimes #   ifdef DEBUG
2829b50d902SRodney W. Grimes 	if ( debug & DFNDEBUG ) {
2839b50d902SRodney W. Grimes 	    printf( "[dfn_self_cycle] " );
2849b50d902SRodney W. Grimes 	    printname( parentp );
2859b50d902SRodney W. Grimes 	    printf( "\n" );
2869b50d902SRodney W. Grimes 	}
2870fb7a0beSGarrett Wollman #   endif /* DEBUG */
2889b50d902SRodney W. Grimes }
2899b50d902SRodney W. Grimes 
2909b50d902SRodney W. Grimes     /*
2919b50d902SRodney W. Grimes      *	visit a node after all its children
2929b50d902SRodney W. Grimes      *	[MISSING: an explanation]
2939b50d902SRodney W. Grimes      *	and pop it off the stack
2949b50d902SRodney W. Grimes      */
2959b50d902SRodney W. Grimes dfn_post_visit( parentp )
2969b50d902SRodney W. Grimes     nltype	*parentp;
2979b50d902SRodney W. Grimes {
2989b50d902SRodney W. Grimes     nltype	*memberp;
2999b50d902SRodney W. Grimes 
3009b50d902SRodney W. Grimes #   ifdef DEBUG
3019b50d902SRodney W. Grimes 	if ( debug & DFNDEBUG ) {
3029b50d902SRodney W. Grimes 	    printf( "[dfn_post_visit]\t%d: " , dfn_depth );
3039b50d902SRodney W. Grimes 	    printname( parentp );
3049b50d902SRodney W. Grimes 	    printf( "\n" );
3059b50d902SRodney W. Grimes 	}
3060fb7a0beSGarrett Wollman #   endif /* DEBUG */
3079b50d902SRodney W. Grimes 	/*
3089b50d902SRodney W. Grimes 	 *	number functions and things in their cycles
3099b50d902SRodney W. Grimes 	 *	unless the function is itself part of a cycle
3109b50d902SRodney W. Grimes 	 */
3119b50d902SRodney W. Grimes     if ( parentp -> cyclehead == parentp ) {
3129b50d902SRodney W. Grimes 	dfn_counter += 1;
3139b50d902SRodney W. Grimes 	for ( memberp = parentp ; memberp ; memberp = memberp -> cnext ) {
3149b50d902SRodney W. Grimes 	    memberp -> toporder = dfn_counter;
3159b50d902SRodney W. Grimes #	    ifdef DEBUG
3169b50d902SRodney W. Grimes 		if ( debug & DFNDEBUG ) {
3179b50d902SRodney W. Grimes 		    printf( "[dfn_post_visit]\t\tmember " );
3189b50d902SRodney W. Grimes 		    printname( memberp );
3199b50d902SRodney W. Grimes 		    printf( " -> toporder = %d\n" , dfn_counter );
3209b50d902SRodney W. Grimes 		}
3210fb7a0beSGarrett Wollman #	    endif /* DEBUG */
3229b50d902SRodney W. Grimes 	}
3239b50d902SRodney W. Grimes     } else {
3249b50d902SRodney W. Grimes #	ifdef DEBUG
3259b50d902SRodney W. Grimes 	    if ( debug & DFNDEBUG ) {
3269b50d902SRodney W. Grimes 		printf( "[dfn_post_visit]\t\tis part of a cycle\n" );
3279b50d902SRodney W. Grimes 	    }
3280fb7a0beSGarrett Wollman #	endif /* DEBUG */
3299b50d902SRodney W. Grimes     }
3309b50d902SRodney W. Grimes     dfn_depth -= 1;
3319b50d902SRodney W. Grimes }
332