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