dfn.c revision 105243
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 * 3. All advertising materials mentioning features or use of this software 141590Srgrimes * must display the following acknowledgement: 151590Srgrimes * This product includes software developed by the University of 161590Srgrimes * California, Berkeley and its contributors. 171590Srgrimes * 4. Neither the name of the University nor the names of its contributors 181590Srgrimes * may be used to endorse or promote products derived from this software 191590Srgrimes * without specific prior written permission. 201590Srgrimes * 211590Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 221590Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 231590Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 241590Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 251590Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 261590Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 271590Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 281590Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 291590Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 301590Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 311590Srgrimes * SUCH DAMAGE. 321590Srgrimes */ 331590Srgrimes 34105243Scharnier#if 0 351590Srgrimes#ifndef lint 361590Srgrimesstatic char sccsid[] = "@(#)dfn.c 8.1 (Berkeley) 6/6/93"; 37105243Scharnier#endif /* not lint */ 3897631Swollman#endif 39105243Scharnier 4099112Sobrien#include <sys/cdefs.h> 4199112Sobrien__FBSDID("$FreeBSD: head/usr.bin/gprof/dfn.c 105243 2002-10-16 13:50:09Z charnier $"); 421590Srgrimes 43105243Scharnier#include <err.h> 441590Srgrimes#include "gprof.h" 451590Srgrimes 461590Srgrimes#define DFN_DEPTH 100 471590Srgrimesstruct dfnstruct { 481590Srgrimes nltype *nlentryp; 491590Srgrimes int cycletop; 501590Srgrimes}; 511590Srgrimestypedef struct dfnstruct dfntype; 521590Srgrimes 531590Srgrimesdfntype dfn_stack[ DFN_DEPTH ]; 541590Srgrimesint dfn_depth; 551590Srgrimes 561590Srgrimesint dfn_counter; 571590Srgrimes 58105243Scharniervoid 591590Srgrimesdfn_init() 601590Srgrimes{ 611590Srgrimes 621590Srgrimes dfn_depth = 0; 631590Srgrimes dfn_counter = DFN_NAN; 641590Srgrimes} 651590Srgrimes 661590Srgrimes /* 671590Srgrimes * given this parent, depth first number its children. 681590Srgrimes */ 69105243Scharniervoid 701590Srgrimesdfn( parentp ) 711590Srgrimes nltype *parentp; 721590Srgrimes{ 731590Srgrimes arctype *arcp; 741590Srgrimes 751590Srgrimes# ifdef DEBUG 761590Srgrimes if ( debug & DFNDEBUG ) { 771590Srgrimes printf( "[dfn] dfn(" ); 781590Srgrimes printname( parentp ); 791590Srgrimes printf( ")\n" ); 801590Srgrimes } 8197631Swollman# endif /* DEBUG */ 821590Srgrimes /* 83105243Scharnier * if we're already numbered, no need to look any further. 841590Srgrimes */ 851590Srgrimes if ( dfn_numbered( parentp ) ) { 861590Srgrimes return; 871590Srgrimes } 881590Srgrimes /* 891590Srgrimes * if we're already busy, must be a cycle 901590Srgrimes */ 911590Srgrimes if ( dfn_busy( parentp ) ) { 921590Srgrimes dfn_findcycle( parentp ); 931590Srgrimes return; 941590Srgrimes } 951590Srgrimes /* 961590Srgrimes * visit yourself before your children 971590Srgrimes */ 981590Srgrimes dfn_pre_visit( parentp ); 991590Srgrimes /* 1001590Srgrimes * visit children 1011590Srgrimes */ 1021590Srgrimes for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) { 1031590Srgrimes if ( arcp -> arc_flags & DEADARC ) 1041590Srgrimes continue; 1051590Srgrimes dfn( arcp -> arc_childp ); 1061590Srgrimes } 1071590Srgrimes /* 1081590Srgrimes * visit yourself after your children 1091590Srgrimes */ 1101590Srgrimes dfn_post_visit( parentp ); 1111590Srgrimes} 1121590Srgrimes 1131590Srgrimes /* 1141590Srgrimes * push a parent onto the stack and mark it busy 1151590Srgrimes */ 116105243Scharniervoid 1171590Srgrimesdfn_pre_visit( parentp ) 1181590Srgrimes nltype *parentp; 1191590Srgrimes{ 1201590Srgrimes 1211590Srgrimes dfn_depth += 1; 122105243Scharnier if ( dfn_depth >= DFN_DEPTH ) 123105243Scharnier errx( 1 , "[dfn] out of my depth (dfn_stack overflow)" ); 1241590Srgrimes dfn_stack[ dfn_depth ].nlentryp = parentp; 1251590Srgrimes dfn_stack[ dfn_depth ].cycletop = dfn_depth; 1261590Srgrimes parentp -> toporder = DFN_BUSY; 1271590Srgrimes# ifdef DEBUG 1281590Srgrimes if ( debug & DFNDEBUG ) { 1291590Srgrimes printf( "[dfn_pre_visit]\t\t%d:" , dfn_depth ); 1301590Srgrimes printname( parentp ); 1311590Srgrimes printf( "\n" ); 1321590Srgrimes } 13397631Swollman# endif /* DEBUG */ 1341590Srgrimes} 1351590Srgrimes 1361590Srgrimes /* 1371590Srgrimes * are we already numbered? 1381590Srgrimes */ 1391590Srgrimesbool 1401590Srgrimesdfn_numbered( childp ) 1411590Srgrimes nltype *childp; 1421590Srgrimes{ 1438874Srgrimes 1441590Srgrimes return ( childp -> toporder != DFN_NAN && childp -> toporder != DFN_BUSY ); 1451590Srgrimes} 1461590Srgrimes 1471590Srgrimes /* 1481590Srgrimes * are we already busy? 1491590Srgrimes */ 1501590Srgrimesbool 1511590Srgrimesdfn_busy( childp ) 1521590Srgrimes nltype *childp; 1531590Srgrimes{ 1541590Srgrimes 1551590Srgrimes if ( childp -> toporder == DFN_NAN ) { 1561590Srgrimes return FALSE; 1571590Srgrimes } 1581590Srgrimes return TRUE; 1591590Srgrimes} 1601590Srgrimes 1611590Srgrimes /* 1621590Srgrimes * MISSING: an explanation 1631590Srgrimes */ 164105243Scharniervoid 1651590Srgrimesdfn_findcycle( childp ) 1661590Srgrimes nltype *childp; 1671590Srgrimes{ 1681590Srgrimes int cycletop; 1691590Srgrimes nltype *cycleheadp; 1701590Srgrimes nltype *tailp; 1711590Srgrimes int index; 1721590Srgrimes 1731590Srgrimes for ( cycletop = dfn_depth ; cycletop > 0 ; cycletop -= 1 ) { 1741590Srgrimes cycleheadp = dfn_stack[ cycletop ].nlentryp; 1751590Srgrimes if ( childp == cycleheadp ) { 1761590Srgrimes break; 1771590Srgrimes } 1781590Srgrimes if ( childp -> cyclehead != childp && 1791590Srgrimes childp -> cyclehead == cycleheadp ) { 1801590Srgrimes break; 1811590Srgrimes } 1821590Srgrimes } 183105243Scharnier if ( cycletop <= 0 ) 184105243Scharnier errx( 1 , "[dfn_findcycle] couldn't find head of cycle" ); 1851590Srgrimes# ifdef DEBUG 1861590Srgrimes if ( debug & DFNDEBUG ) { 1871590Srgrimes printf( "[dfn_findcycle] dfn_depth %d cycletop %d " , 1881590Srgrimes dfn_depth , cycletop ); 1891590Srgrimes printname( cycleheadp ); 1901590Srgrimes printf( "\n" ); 1911590Srgrimes } 19297631Swollman# endif /* DEBUG */ 1931590Srgrimes if ( cycletop == dfn_depth ) { 1941590Srgrimes /* 1951590Srgrimes * this is previous function, e.g. this calls itself 1961590Srgrimes * sort of boring 1971590Srgrimes */ 1981590Srgrimes dfn_self_cycle( childp ); 1991590Srgrimes } else { 2001590Srgrimes /* 2011590Srgrimes * glom intervening functions that aren't already 2021590Srgrimes * glommed into this cycle. 2031590Srgrimes * things have been glommed when their cyclehead field 2041590Srgrimes * points to the head of the cycle they are glommed into. 2051590Srgrimes */ 2061590Srgrimes for ( tailp = cycleheadp ; tailp -> cnext ; tailp = tailp -> cnext ) { 2071590Srgrimes /* void: chase down to tail of things already glommed */ 2081590Srgrimes# ifdef DEBUG 2091590Srgrimes if ( debug & DFNDEBUG ) { 2101590Srgrimes printf( "[dfn_findcycle] tail " ); 2111590Srgrimes printname( tailp ); 2121590Srgrimes printf( "\n" ); 2131590Srgrimes } 21497631Swollman# endif /* DEBUG */ 2151590Srgrimes } 2161590Srgrimes /* 2171590Srgrimes * if what we think is the top of the cycle 2181590Srgrimes * has a cyclehead field, then it's not really the 2191590Srgrimes * head of the cycle, which is really what we want 2208874Srgrimes */ 2211590Srgrimes if ( cycleheadp -> cyclehead != cycleheadp ) { 2221590Srgrimes cycleheadp = cycleheadp -> cyclehead; 2231590Srgrimes# ifdef DEBUG 2241590Srgrimes if ( debug & DFNDEBUG ) { 2251590Srgrimes printf( "[dfn_findcycle] new cyclehead " ); 2261590Srgrimes printname( cycleheadp ); 2271590Srgrimes printf( "\n" ); 2281590Srgrimes } 22997631Swollman# endif /* DEBUG */ 2301590Srgrimes } 2311590Srgrimes for ( index = cycletop + 1 ; index <= dfn_depth ; index += 1 ) { 2321590Srgrimes childp = dfn_stack[ index ].nlentryp; 2331590Srgrimes if ( childp -> cyclehead == childp ) { 2341590Srgrimes /* 2351590Srgrimes * not yet glommed anywhere, glom it 2361590Srgrimes * and fix any children it has glommed 2371590Srgrimes */ 2381590Srgrimes tailp -> cnext = childp; 2391590Srgrimes childp -> cyclehead = cycleheadp; 2401590Srgrimes# ifdef DEBUG 2411590Srgrimes if ( debug & DFNDEBUG ) { 2421590Srgrimes printf( "[dfn_findcycle] glomming " ); 2431590Srgrimes printname( childp ); 2441590Srgrimes printf( " onto " ); 2451590Srgrimes printname( cycleheadp ); 2461590Srgrimes printf( "\n" ); 2471590Srgrimes } 24897631Swollman# endif /* DEBUG */ 2491590Srgrimes for ( tailp = childp ; tailp->cnext ; tailp = tailp->cnext ) { 2501590Srgrimes tailp -> cnext -> cyclehead = cycleheadp; 2511590Srgrimes# ifdef DEBUG 2521590Srgrimes if ( debug & DFNDEBUG ) { 2531590Srgrimes printf( "[dfn_findcycle] and its tail " ); 2541590Srgrimes printname( tailp -> cnext ); 2551590Srgrimes printf( " onto " ); 2561590Srgrimes printname( cycleheadp ); 2571590Srgrimes printf( "\n" ); 2581590Srgrimes } 25997631Swollman# endif /* DEBUG */ 2601590Srgrimes } 2611590Srgrimes } else if ( childp -> cyclehead != cycleheadp /* firewall */ ) { 2621590Srgrimes fprintf( stderr , 2631590Srgrimes "[dfn_busy] glommed, but not to cyclehead\n" ); 2641590Srgrimes } 2651590Srgrimes } 2661590Srgrimes } 2671590Srgrimes} 2681590Srgrimes 2691590Srgrimes /* 2701590Srgrimes * deal with self-cycles 2711590Srgrimes * for lint: ARGSUSED 2721590Srgrimes */ 273105243Scharniervoid 2741590Srgrimesdfn_self_cycle( parentp ) 2751590Srgrimes nltype *parentp; 2761590Srgrimes{ 2771590Srgrimes /* 2781590Srgrimes * since we are taking out self-cycles elsewhere 2791590Srgrimes * no need for the special case, here. 2801590Srgrimes */ 2811590Srgrimes# ifdef DEBUG 2821590Srgrimes if ( debug & DFNDEBUG ) { 2831590Srgrimes printf( "[dfn_self_cycle] " ); 2841590Srgrimes printname( parentp ); 2851590Srgrimes printf( "\n" ); 2861590Srgrimes } 28797631Swollman# endif /* DEBUG */ 2881590Srgrimes} 2891590Srgrimes 2901590Srgrimes /* 2911590Srgrimes * visit a node after all its children 2921590Srgrimes * [MISSING: an explanation] 2931590Srgrimes * and pop it off the stack 2941590Srgrimes */ 295105243Scharniervoid 2961590Srgrimesdfn_post_visit( parentp ) 2971590Srgrimes nltype *parentp; 2981590Srgrimes{ 2991590Srgrimes nltype *memberp; 3001590Srgrimes 3011590Srgrimes# ifdef DEBUG 3021590Srgrimes if ( debug & DFNDEBUG ) { 3031590Srgrimes printf( "[dfn_post_visit]\t%d: " , dfn_depth ); 3041590Srgrimes printname( parentp ); 3051590Srgrimes printf( "\n" ); 3061590Srgrimes } 30797631Swollman# endif /* DEBUG */ 3081590Srgrimes /* 3091590Srgrimes * number functions and things in their cycles 3101590Srgrimes * unless the function is itself part of a cycle 3111590Srgrimes */ 3121590Srgrimes if ( parentp -> cyclehead == parentp ) { 3131590Srgrimes dfn_counter += 1; 3141590Srgrimes for ( memberp = parentp ; memberp ; memberp = memberp -> cnext ) { 3151590Srgrimes memberp -> toporder = dfn_counter; 3161590Srgrimes# ifdef DEBUG 3171590Srgrimes if ( debug & DFNDEBUG ) { 3181590Srgrimes printf( "[dfn_post_visit]\t\tmember " ); 3191590Srgrimes printname( memberp ); 3201590Srgrimes printf( " -> toporder = %d\n" , dfn_counter ); 3211590Srgrimes } 32297631Swollman# endif /* DEBUG */ 3231590Srgrimes } 3241590Srgrimes } else { 3251590Srgrimes# ifdef DEBUG 3261590Srgrimes if ( debug & DFNDEBUG ) { 3271590Srgrimes printf( "[dfn_post_visit]\t\tis part of a cycle\n" ); 3281590Srgrimes } 32997631Swollman# endif /* DEBUG */ 3301590Srgrimes } 3311590Srgrimes dfn_depth -= 1; 3321590Srgrimes} 333