11590Srgrimes/* 21590Srgrimes * Copyright (c) 1983, 1993 31590Srgrimes * The Regents of the University of California. All rights reserved. 41590Srgrimes * 51590Srgrimes * Redistribution and use in source and binary forms, with or without 61590Srgrimes * modification, are permitted provided that the following conditions 71590Srgrimes * are met: 81590Srgrimes * 1. Redistributions of source code must retain the above copyright 91590Srgrimes * notice, this list of conditions and the following disclaimer. 101590Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 111590Srgrimes * notice, this list of conditions and the following disclaimer in the 121590Srgrimes * documentation and/or other materials provided with the distribution. 131590Srgrimes * 4. Neither the name of the University nor the names of its contributors 141590Srgrimes * may be used to endorse or promote products derived from this software 151590Srgrimes * without specific prior written permission. 161590Srgrimes * 171590Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 181590Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 191590Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 201590Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 211590Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 221590Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 231590Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 241590Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 251590Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 261590Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 271590Srgrimes * SUCH DAMAGE. 281590Srgrimes */ 291590Srgrimes 30105243Scharnier#if 0 311590Srgrimes#ifndef lint 321590Srgrimesstatic char sccsid[] = "@(#)dfn.c 8.1 (Berkeley) 6/6/93"; 33105243Scharnier#endif /* not lint */ 3497631Swollman#endif 35105243Scharnier 3699112Sobrien#include <sys/cdefs.h> 3799112Sobrien__FBSDID("$FreeBSD$"); 381590Srgrimes 39105243Scharnier#include <err.h> 401590Srgrimes#include "gprof.h" 411590Srgrimes 421590Srgrimes#define DFN_DEPTH 100 431590Srgrimesstruct dfnstruct { 441590Srgrimes nltype *nlentryp; 451590Srgrimes int cycletop; 461590Srgrimes}; 471590Srgrimestypedef struct dfnstruct dfntype; 481590Srgrimes 491590Srgrimesdfntype dfn_stack[ DFN_DEPTH ]; 501590Srgrimesint dfn_depth; 511590Srgrimes 521590Srgrimesint dfn_counter; 531590Srgrimes 54105243Scharniervoid 551590Srgrimesdfn_init() 561590Srgrimes{ 571590Srgrimes 581590Srgrimes dfn_depth = 0; 591590Srgrimes dfn_counter = DFN_NAN; 601590Srgrimes} 611590Srgrimes 621590Srgrimes /* 631590Srgrimes * given this parent, depth first number its children. 641590Srgrimes */ 65105243Scharniervoid 661590Srgrimesdfn( parentp ) 671590Srgrimes nltype *parentp; 681590Srgrimes{ 691590Srgrimes arctype *arcp; 701590Srgrimes 711590Srgrimes# ifdef DEBUG 721590Srgrimes if ( debug & DFNDEBUG ) { 731590Srgrimes printf( "[dfn] dfn(" ); 741590Srgrimes printname( parentp ); 751590Srgrimes printf( ")\n" ); 761590Srgrimes } 7797631Swollman# endif /* DEBUG */ 781590Srgrimes /* 79105243Scharnier * if we're already numbered, no need to look any further. 801590Srgrimes */ 811590Srgrimes if ( dfn_numbered( parentp ) ) { 821590Srgrimes return; 831590Srgrimes } 841590Srgrimes /* 851590Srgrimes * if we're already busy, must be a cycle 861590Srgrimes */ 871590Srgrimes if ( dfn_busy( parentp ) ) { 881590Srgrimes dfn_findcycle( parentp ); 891590Srgrimes return; 901590Srgrimes } 911590Srgrimes /* 921590Srgrimes * visit yourself before your children 931590Srgrimes */ 941590Srgrimes dfn_pre_visit( parentp ); 951590Srgrimes /* 961590Srgrimes * visit children 971590Srgrimes */ 981590Srgrimes for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) { 991590Srgrimes if ( arcp -> arc_flags & DEADARC ) 1001590Srgrimes continue; 1011590Srgrimes dfn( arcp -> arc_childp ); 1021590Srgrimes } 1031590Srgrimes /* 1041590Srgrimes * visit yourself after your children 1051590Srgrimes */ 1061590Srgrimes dfn_post_visit( parentp ); 1071590Srgrimes} 1081590Srgrimes 1091590Srgrimes /* 1101590Srgrimes * push a parent onto the stack and mark it busy 1111590Srgrimes */ 112105243Scharniervoid 1131590Srgrimesdfn_pre_visit( parentp ) 1141590Srgrimes nltype *parentp; 1151590Srgrimes{ 1161590Srgrimes 1171590Srgrimes dfn_depth += 1; 118105243Scharnier if ( dfn_depth >= DFN_DEPTH ) 119105243Scharnier errx( 1 , "[dfn] out of my depth (dfn_stack overflow)" ); 1201590Srgrimes dfn_stack[ dfn_depth ].nlentryp = parentp; 1211590Srgrimes dfn_stack[ dfn_depth ].cycletop = dfn_depth; 1221590Srgrimes parentp -> toporder = DFN_BUSY; 1231590Srgrimes# ifdef DEBUG 1241590Srgrimes if ( debug & DFNDEBUG ) { 1251590Srgrimes printf( "[dfn_pre_visit]\t\t%d:" , dfn_depth ); 1261590Srgrimes printname( parentp ); 1271590Srgrimes printf( "\n" ); 1281590Srgrimes } 12997631Swollman# endif /* DEBUG */ 1301590Srgrimes} 1311590Srgrimes 1321590Srgrimes /* 1331590Srgrimes * are we already numbered? 1341590Srgrimes */ 1351590Srgrimesbool 1361590Srgrimesdfn_numbered( childp ) 1371590Srgrimes nltype *childp; 1381590Srgrimes{ 1398874Srgrimes 1401590Srgrimes return ( childp -> toporder != DFN_NAN && childp -> toporder != DFN_BUSY ); 1411590Srgrimes} 1421590Srgrimes 1431590Srgrimes /* 1441590Srgrimes * are we already busy? 1451590Srgrimes */ 1461590Srgrimesbool 1471590Srgrimesdfn_busy( childp ) 1481590Srgrimes nltype *childp; 1491590Srgrimes{ 1501590Srgrimes 1511590Srgrimes if ( childp -> toporder == DFN_NAN ) { 1521590Srgrimes return FALSE; 1531590Srgrimes } 1541590Srgrimes return TRUE; 1551590Srgrimes} 1561590Srgrimes 1571590Srgrimes /* 1581590Srgrimes * MISSING: an explanation 1591590Srgrimes */ 160105243Scharniervoid 1611590Srgrimesdfn_findcycle( childp ) 1621590Srgrimes nltype *childp; 1631590Srgrimes{ 1641590Srgrimes int cycletop; 1651590Srgrimes nltype *cycleheadp; 1661590Srgrimes nltype *tailp; 1671590Srgrimes int index; 1681590Srgrimes 1691590Srgrimes for ( cycletop = dfn_depth ; cycletop > 0 ; cycletop -= 1 ) { 1701590Srgrimes cycleheadp = dfn_stack[ cycletop ].nlentryp; 1711590Srgrimes if ( childp == cycleheadp ) { 1721590Srgrimes break; 1731590Srgrimes } 1741590Srgrimes if ( childp -> cyclehead != childp && 1751590Srgrimes childp -> cyclehead == cycleheadp ) { 1761590Srgrimes break; 1771590Srgrimes } 1781590Srgrimes } 179105243Scharnier if ( cycletop <= 0 ) 180105243Scharnier errx( 1 , "[dfn_findcycle] couldn't find head of cycle" ); 1811590Srgrimes# ifdef DEBUG 1821590Srgrimes if ( debug & DFNDEBUG ) { 1831590Srgrimes printf( "[dfn_findcycle] dfn_depth %d cycletop %d " , 1841590Srgrimes dfn_depth , cycletop ); 1851590Srgrimes printname( cycleheadp ); 1861590Srgrimes printf( "\n" ); 1871590Srgrimes } 18897631Swollman# endif /* DEBUG */ 1891590Srgrimes if ( cycletop == dfn_depth ) { 1901590Srgrimes /* 1911590Srgrimes * this is previous function, e.g. this calls itself 1921590Srgrimes * sort of boring 1931590Srgrimes */ 1941590Srgrimes dfn_self_cycle( childp ); 1951590Srgrimes } else { 1961590Srgrimes /* 1971590Srgrimes * glom intervening functions that aren't already 1981590Srgrimes * glommed into this cycle. 1991590Srgrimes * things have been glommed when their cyclehead field 2001590Srgrimes * points to the head of the cycle they are glommed into. 2011590Srgrimes */ 2021590Srgrimes for ( tailp = cycleheadp ; tailp -> cnext ; tailp = tailp -> cnext ) { 2031590Srgrimes /* void: chase down to tail of things already glommed */ 2041590Srgrimes# ifdef DEBUG 2051590Srgrimes if ( debug & DFNDEBUG ) { 2061590Srgrimes printf( "[dfn_findcycle] tail " ); 2071590Srgrimes printname( tailp ); 2081590Srgrimes printf( "\n" ); 2091590Srgrimes } 21097631Swollman# endif /* DEBUG */ 2111590Srgrimes } 2121590Srgrimes /* 2131590Srgrimes * if what we think is the top of the cycle 2141590Srgrimes * has a cyclehead field, then it's not really the 2151590Srgrimes * head of the cycle, which is really what we want 2168874Srgrimes */ 2171590Srgrimes if ( cycleheadp -> cyclehead != cycleheadp ) { 2181590Srgrimes cycleheadp = cycleheadp -> cyclehead; 2191590Srgrimes# ifdef DEBUG 2201590Srgrimes if ( debug & DFNDEBUG ) { 2211590Srgrimes printf( "[dfn_findcycle] new cyclehead " ); 2221590Srgrimes printname( cycleheadp ); 2231590Srgrimes printf( "\n" ); 2241590Srgrimes } 22597631Swollman# endif /* DEBUG */ 2261590Srgrimes } 2271590Srgrimes for ( index = cycletop + 1 ; index <= dfn_depth ; index += 1 ) { 2281590Srgrimes childp = dfn_stack[ index ].nlentryp; 2291590Srgrimes if ( childp -> cyclehead == childp ) { 2301590Srgrimes /* 2311590Srgrimes * not yet glommed anywhere, glom it 2321590Srgrimes * and fix any children it has glommed 2331590Srgrimes */ 2341590Srgrimes tailp -> cnext = childp; 2351590Srgrimes childp -> cyclehead = cycleheadp; 2361590Srgrimes# ifdef DEBUG 2371590Srgrimes if ( debug & DFNDEBUG ) { 2381590Srgrimes printf( "[dfn_findcycle] glomming " ); 2391590Srgrimes printname( childp ); 2401590Srgrimes printf( " onto " ); 2411590Srgrimes printname( cycleheadp ); 2421590Srgrimes printf( "\n" ); 2431590Srgrimes } 24497631Swollman# endif /* DEBUG */ 2451590Srgrimes for ( tailp = childp ; tailp->cnext ; tailp = tailp->cnext ) { 2461590Srgrimes tailp -> cnext -> cyclehead = cycleheadp; 2471590Srgrimes# ifdef DEBUG 2481590Srgrimes if ( debug & DFNDEBUG ) { 2491590Srgrimes printf( "[dfn_findcycle] and its tail " ); 2501590Srgrimes printname( tailp -> cnext ); 2511590Srgrimes printf( " onto " ); 2521590Srgrimes printname( cycleheadp ); 2531590Srgrimes printf( "\n" ); 2541590Srgrimes } 25597631Swollman# endif /* DEBUG */ 2561590Srgrimes } 2571590Srgrimes } else if ( childp -> cyclehead != cycleheadp /* firewall */ ) { 2581590Srgrimes fprintf( stderr , 2591590Srgrimes "[dfn_busy] glommed, but not to cyclehead\n" ); 2601590Srgrimes } 2611590Srgrimes } 2621590Srgrimes } 2631590Srgrimes} 2641590Srgrimes 2651590Srgrimes /* 2661590Srgrimes * deal with self-cycles 2671590Srgrimes * for lint: ARGSUSED 2681590Srgrimes */ 269105243Scharniervoid 2701590Srgrimesdfn_self_cycle( parentp ) 2711590Srgrimes nltype *parentp; 2721590Srgrimes{ 2731590Srgrimes /* 2741590Srgrimes * since we are taking out self-cycles elsewhere 2751590Srgrimes * no need for the special case, here. 2761590Srgrimes */ 2771590Srgrimes# ifdef DEBUG 2781590Srgrimes if ( debug & DFNDEBUG ) { 2791590Srgrimes printf( "[dfn_self_cycle] " ); 2801590Srgrimes printname( parentp ); 2811590Srgrimes printf( "\n" ); 2821590Srgrimes } 28397631Swollman# endif /* DEBUG */ 2841590Srgrimes} 2851590Srgrimes 2861590Srgrimes /* 2871590Srgrimes * visit a node after all its children 2881590Srgrimes * [MISSING: an explanation] 2891590Srgrimes * and pop it off the stack 2901590Srgrimes */ 291105243Scharniervoid 2921590Srgrimesdfn_post_visit( parentp ) 2931590Srgrimes nltype *parentp; 2941590Srgrimes{ 2951590Srgrimes nltype *memberp; 2961590Srgrimes 2971590Srgrimes# ifdef DEBUG 2981590Srgrimes if ( debug & DFNDEBUG ) { 2991590Srgrimes printf( "[dfn_post_visit]\t%d: " , dfn_depth ); 3001590Srgrimes printname( parentp ); 3011590Srgrimes printf( "\n" ); 3021590Srgrimes } 30397631Swollman# endif /* DEBUG */ 3041590Srgrimes /* 3051590Srgrimes * number functions and things in their cycles 3061590Srgrimes * unless the function is itself part of a cycle 3071590Srgrimes */ 3081590Srgrimes if ( parentp -> cyclehead == parentp ) { 3091590Srgrimes dfn_counter += 1; 3101590Srgrimes for ( memberp = parentp ; memberp ; memberp = memberp -> cnext ) { 3111590Srgrimes memberp -> toporder = dfn_counter; 3121590Srgrimes# ifdef DEBUG 3131590Srgrimes if ( debug & DFNDEBUG ) { 3141590Srgrimes printf( "[dfn_post_visit]\t\tmember " ); 3151590Srgrimes printname( memberp ); 3161590Srgrimes printf( " -> toporder = %d\n" , dfn_counter ); 3171590Srgrimes } 31897631Swollman# endif /* DEBUG */ 3191590Srgrimes } 3201590Srgrimes } else { 3211590Srgrimes# ifdef DEBUG 3221590Srgrimes if ( debug & DFNDEBUG ) { 3231590Srgrimes printf( "[dfn_post_visit]\t\tis part of a cycle\n" ); 3241590Srgrimes } 32597631Swollman# endif /* DEBUG */ 3261590Srgrimes } 3271590Srgrimes dfn_depth -= 1; 3281590Srgrimes} 329