Return to arcs.c CVS log

Up to [local] / src / usr.bin / gprof

rcsid[] and sccsid[] and copyright[] are essentially unmaintained (and
unmaintainable).  these days, people use source.  these id's do not provide
any benefit, and do hurt the small install media
(the 33,000 line diff is essentially mechanical)
ok with the idea millert, ok dms

/*	$OpenBSD: arcs.c,v 1.12 2009/10/27 23:59:38 deraadt Exp $	*/
/*	$NetBSD: arcs.c,v 1.6 1995/04/19 07:15:52 cgd Exp $	*/

/*
 * Copyright (c) 1983, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include "gprof.h"

#ifdef DEBUG
int visited;
int viable;
int newcycle;
int oldcycle;
void printsubcycle(cltype *);
#endif /* DEBUG */

    /*
     *	add (or just increment) an arc
     */
void
addarc(nltype *parentp, nltype *childp, long count)
{
    arctype		*arcp;

#   ifdef DEBUG
	if ( debug & TALLYDEBUG ) {
	    printf( "[addarc] %ld arcs from %s to %s\n" ,
		    count , parentp -> name , childp -> name );
	}
#   endif /* DEBUG */
    arcp = arclookup( parentp , childp );
    if ( arcp != 0 ) {
	    /*
	     *	a hit:  just increment the count.
	     */
#	ifdef DEBUG
	    if ( debug & TALLYDEBUG ) {
		printf( "[tally] hit %ld += %ld\n" ,
			arcp -> arc_count , count );
	    }
#	endif /* DEBUG */
	arcp -> arc_count += count;
	return;
    }
    arcp = (arctype *)calloc( 1 , sizeof *arcp );
    arcp -> arc_parentp = parentp;
    arcp -> arc_childp = childp;
    arcp -> arc_count = count;
	/*
	 *	prepend this child to the children of this parent
	 */
    arcp -> arc_childlist = parentp -> children;
    parentp -> children = arcp;
	/*
	 *	prepend this parent to the parents of this child
	 */
    arcp -> arc_parentlist = childp -> parents;
    childp -> parents = arcp;
}

    /*
     *	the code below topologically sorts the graph (collapsing cycles),
     *	and propagates time bottom up and flags top down.
     */

    /*
     *	the topologically sorted name list pointers
     */
nltype	**topsortnlp;

int
topcmp(nltype **npp1, nltype **npp2)
{
    return (*npp1) -> toporder - (*npp2) -> toporder;
}

nltype **
doarcs()
{
    nltype	*parentp, **timesortnlp;
    arctype	*arcp;
    long	index;
    long	pass;

	/*
	 *	initialize various things:
	 *	    zero out child times.
	 *	    count self-recursive calls.
	 *	    indicate that nothing is on cycles.
	 */
    for ( parentp = nl ; parentp < npe ; parentp++ ) {
	parentp -> childtime = 0.0;
	arcp = arclookup( parentp , parentp );
	if ( arcp != 0 ) {
	    parentp -> ncall -= arcp -> arc_count;
	    parentp -> selfcalls = arcp -> arc_count;
	} else {
	    parentp -> selfcalls = 0;
	}
	parentp -> npropcall = parentp -> ncall;
	parentp -> propfraction = 0.0;
	parentp -> propself = 0.0;
	parentp -> propchild = 0.0;
	parentp -> printflag = FALSE;
	parentp -> toporder = DFN_NAN;
	parentp -> cycleno = 0;
	parentp -> cyclehead = parentp;
	parentp -> cnext = 0;
	if ( cflag ) {
	    findcall( parentp , parentp -> value , (parentp+1) -> value );
	}
    }
    for ( pass = 1 ; ; pass++ ) {
	    /*
	     *	topologically order things
	     *	if any node is unnumbered,
	     *	    number it and any of its descendents.
	     */
	for ( dfn_init() , parentp = nl ; parentp < npe ; parentp++ ) {
	    if ( parentp -> toporder == DFN_NAN ) {
		dfn( parentp );
	    }
	}
	    /*
	     *	link together nodes on the same cycle
	     */
	cyclelink();
	    /*
	     *	if no cycles to break up, proceed
	     */
	if ( ! Cflag )
	    break;
	    /*
	     *	analyze cycles to determine breakup
	     */
#	ifdef DEBUG
	    if ( debug & BREAKCYCLE ) {
		printf("[doarcs] pass %ld, cycle(s) %d\n" , pass , ncycle );
	    }
#	endif /* DEBUG */
	if ( pass == 1 ) {
	    printf( "\n\n%s %s\n%s %d:\n" ,
		"The following arcs were deleted" ,
		"from the propagation calculation" ,
		"to reduce the maximum cycle size to", cyclethreshold );
	}
	if ( cycleanalyze() )
	    break;
	free ( cyclenl );
	ncycle = 0;
	for ( parentp = nl ; parentp < npe ; parentp++ ) {
	    parentp -> toporder = DFN_NAN;
	    parentp -> cycleno = 0;
	    parentp -> cyclehead = parentp;
	    parentp -> cnext = 0;
	}
    }
    if ( pass > 1 ) {
	printf( "\f\n" );
    } else {
	printf( "\tNone\n\n" );
    }
	/*
	 *	Sort the symbol table in reverse topological order
	 */
    topsortnlp = (nltype **) calloc( nname , sizeof(nltype *) );
    if ( topsortnlp == (nltype **) 0 )
	warnx("[doarcs] ran out of memory for topo sorting");
    for ( index = 0 ; index < nname ; index += 1 ) {
	topsortnlp[ index ] = &nl[ index ];
    }
    qsort( topsortnlp , nname , sizeof(nltype *) , topcmp );
#   ifdef DEBUG
	if ( debug & DFNDEBUG ) {
	    printf( "[doarcs] topological sort listing\n" );
	    for ( index = 0 ; index < nname ; index += 1 ) {
		printf( "[doarcs] " );
		printf( "%d:" , topsortnlp[ index ] -> toporder );
		printname( topsortnlp[ index ] );
		printf( "\n" );
	    }
	}
#   endif /* DEBUG */
	/*
	 *	starting from the topological top,
	 *	propagate print flags to children.
	 *	also, calculate propagation fractions.
	 *	this happens before time propagation
	 *	since time propagation uses the fractions.
	 */
    doflags();
	/*
	 *	starting from the topological bottom,
	 *	propagate children times up to parents.
	 */
    dotime();
	/*
	 *	Now, sort by propself + propchild.
	 *	sorting both the regular function names
	 *	and cycle headers.
	 */
    timesortnlp = (nltype **) calloc( nname + ncycle , sizeof(nltype *) );
    if ( timesortnlp == (nltype **) 0 )
	warnx("ran out of memory for sorting");
    for ( index = 0 ; index < nname ; index++ ) {
	timesortnlp[index] = &nl[index];
    }
    for ( index = 1 ; index <= ncycle ; index++ ) {
	timesortnlp[nname+index-1] = &cyclenl[index];
    }
    qsort( timesortnlp , nname + ncycle , sizeof(nltype *) , totalcmp );
    for ( index = 0 ; index < nname + ncycle ; index++ ) {
	timesortnlp[ index ] -> index = index + 1;
    }
    return( timesortnlp );
}

void
dotime()
{
    int	index;

    cycletime();
    for ( index = 0 ; index < nname ; index += 1 ) {
	timepropagate( topsortnlp[ index ] );
    }
}

void
timepropagate(nltype *parentp)
{
    arctype	*arcp;
    nltype	*childp;
    double	share;
    double	propshare;

    if ( parentp -> propfraction == 0.0 ) {
	return;
    }
	/*
	 *	gather time from children of this parent.
	 */
    for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
	childp = arcp -> arc_childp;
	if ( arcp -> arc_flags & DEADARC ) {
	    continue;
	}
	if ( arcp -> arc_count == 0 ) {
	    continue;
	}
	if ( childp == parentp ) {
	    continue;
	}
	if ( childp -> propfraction == 0.0 ) {
	    continue;
	}
	if ( childp -> cyclehead != childp ) {
	    if ( parentp -> cycleno == childp -> cycleno ) {
		continue;
	    }
	    if ( parentp -> toporder <= childp -> toporder )
		warnx("[propagate] toporder botches");
	    childp = childp -> cyclehead;
	} else {
	    if ( parentp -> toporder <= childp -> toporder ) {
		warnx("[propagate] toporder botches");
		continue;
	    }
	}
	if ( childp -> npropcall == 0 ) {
	    continue;
	}
	    /*
	     *	distribute time for this arc
	     */
	arcp -> arc_time = childp -> time
			        * ( ( (double) arcp -> arc_count ) /
				    ( (double) childp -> npropcall ) );
	arcp -> arc_childtime = childp -> childtime
			        * ( ( (double) arcp -> arc_count ) /
				    ( (double) childp -> npropcall ) );
	share = arcp -> arc_time + arcp -> arc_childtime;
	parentp -> childtime += share;
	    /*
	     *	( 1 - propfraction ) gets lost along the way
	     */
	propshare = parentp -> propfraction * share;
	    /*
	     *	fix things for printing
	     */
	parentp -> propchild += propshare;
	arcp -> arc_time *= parentp -> propfraction;
	arcp -> arc_childtime *= parentp -> propfraction;
	    /*
	     *	add this share to the parent's cycle header, if any.
	     */
	if ( parentp -> cyclehead != parentp ) {
	    parentp -> cyclehead -> childtime += share;
	    parentp -> cyclehead -> propchild += propshare;
	}
#	ifdef DEBUG
	    if ( debug & PROPDEBUG ) {
		printf( "[dotime] child \t" );
		printname( childp );
		printf( " with %f %f %ld/%ld\n" ,
			childp -> time , childp -> childtime ,
			arcp -> arc_count , childp -> npropcall );
		printf( "[dotime] parent\t" );
		printname( parentp );
		printf( "\n[dotime] share %f\n" , share );
	    }
#	endif /* DEBUG */
    }
}

void
cyclelink()
{
    nltype	*nlp;
    nltype	*cyclenlp;
    int			cycle;
    nltype		*memberp;
    arctype		*arcp;

	/*
	 *	Count the number of cycles, and initialze the cycle lists
	 */
    ncycle = 0;
    for ( nlp = nl ; nlp < npe ; nlp++ ) {
	    /*
	     *	this is how you find unattached cycles
	     */
	if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) {
	    ncycle += 1;
	}
    }
	/*
	 *	cyclenl is indexed by cycle number:
	 *	i.e. it is origin 1, not origin 0.
	 */
    cyclenl = (nltype *) calloc( ncycle + 1 , sizeof( nltype ) );
    if ( cyclenl == 0 )
	errx(0, "No room for %ld bytes of cycle headers",
	    (ncycle + 1) * sizeof(nltype));
	/*
	 *	now link cycles to true cycleheads,
	 *	number them, accumulate the data for the cycle
	 */
    cycle = 0;
    for ( nlp = nl ; nlp < npe ; nlp++ ) {
	if ( !( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) ) {
	    continue;
	}
	cycle += 1;
	cyclenlp = &cyclenl[cycle];
        cyclenlp -> name = 0;		/* the name */
        cyclenlp -> value = 0;		/* the pc entry point */
        cyclenlp -> time = 0.0;		/* ticks in this routine */
        cyclenlp -> childtime = 0.0;	/* cumulative ticks in children */
	cyclenlp -> ncall = 0;		/* how many times called */
	cyclenlp -> selfcalls = 0;	/* how many calls to self */
	cyclenlp -> propfraction = 0.0;	/* what % of time propagates */
	cyclenlp -> propself = 0.0;	/* how much self time propagates */
	cyclenlp -> propchild = 0.0;	/* how much child time propagates */
	cyclenlp -> printflag = TRUE;	/* should this be printed? */
	cyclenlp -> index = 0;		/* index in the graph list */
	cyclenlp -> toporder = DFN_NAN;	/* graph call chain top-sort order */
	cyclenlp -> cycleno = cycle;	/* internal number of cycle on */
	cyclenlp -> cyclehead = cyclenlp;	/* pointer to head of cycle */
	cyclenlp -> cnext = nlp;	/* pointer to next member of cycle */
	cyclenlp -> parents = 0;	/* list of caller arcs */
	cyclenlp -> children = 0;	/* list of callee arcs */
#	ifdef DEBUG
	    if ( debug & CYCLEDEBUG ) {
		printf( "[cyclelink] " );
		printname( nlp );
		printf( " is the head of cycle %d\n" , cycle );
	    }
#	endif /* DEBUG */
	    /*
	     *	link members to cycle header
	     */
	for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) {
	    memberp -> cycleno = cycle;
	    memberp -> cyclehead = cyclenlp;
	}
	    /*
	     *	count calls from outside the cycle
	     *	and those among cycle members
	     */
	for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) {
	    for ( arcp=memberp->parents ; arcp ; arcp=arcp->arc_parentlist ) {
		if ( arcp -> arc_parentp == memberp ) {
		    continue;
		}
		if ( arcp -> arc_parentp -> cycleno == cycle ) {
		    cyclenlp -> selfcalls += arcp -> arc_count;
		} else {
		    cyclenlp -> npropcall += arcp -> arc_count;
		}
	    }
	}
    }
}

    /*
     *	analyze cycles to determine breakup
     */
int
cycleanalyze()
{
    arctype	**cyclestack;
    arctype	**stkp;
    arctype	**arcpp;
    arctype	**endlist;
    arctype	*arcp;
    nltype	*nlp;
    cltype	*clp;
    bool	ret;
    bool	done;
    int		size;
    int		cycleno;

	/*
	 *	calculate the size of the cycle, and find nodes that
	 *	exit the cycle as they are desirable targets to cut
	 *	some of their parents
	 */
    for ( done = TRUE , cycleno = 1 ; cycleno <= ncycle ; cycleno++ ) {
	size = 0;
	for (nlp = cyclenl[ cycleno ] . cnext; nlp; nlp = nlp -> cnext) {
	    size += 1;
	    nlp -> parentcnt = 0;
	    nlp -> flags &= ~HASCYCLEXIT;
	    for ( arcp = nlp -> parents; arcp; arcp = arcp -> arc_parentlist ) {
		nlp -> parentcnt += 1;
		if ( arcp -> arc_parentp -> cycleno != cycleno )
		    nlp -> flags |= HASCYCLEXIT;
	    }
	}
	if ( size <= cyclethreshold )
	    continue;
	done = FALSE;
        cyclestack = (arctype **) calloc( size + 1 , sizeof( arctype *) );
	if ( cyclestack == 0 ) {
	    warnx("No room for %ld bytes of cycle stack" ,
		(size + 1) * sizeof(arctype *));
	    return (done);
	}
#	ifdef DEBUG
	    if ( debug & BREAKCYCLE ) {
		printf( "[cycleanalyze] starting cycle %d of %d, size %d\n" ,
		    cycleno , ncycle , size );
	    }
#	endif /* DEBUG */
	for ( nlp = cyclenl[ cycleno ] . cnext ; nlp ; nlp = nlp -> cnext ) {
	    stkp = &cyclestack[0];
	    nlp -> flags |= CYCLEHEAD;
	    ret = descend ( nlp , cyclestack , stkp );
	    nlp -> flags &= ~CYCLEHEAD;
	    if ( ret == FALSE )
		break;
	}
	free( cyclestack );
	if ( cyclecnt > 0 ) {
	    compresslist();
	    for ( clp = cyclehead ; clp ; ) {
		endlist = &clp -> list[ clp -> size ];
		for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
		    (*arcpp) -> arc_cyclecnt--;
		cyclecnt--;
		clp = clp -> next;
		free( clp );
	    }
	    cyclehead = 0;
	}
    }
#   ifdef DEBUG
	if ( debug & BREAKCYCLE ) {
	    printf("%s visited %d, viable %d, newcycle %d, oldcycle %d\n",
		"[doarcs]" , visited , viable , newcycle , oldcycle);
	}
#   endif /* DEBUG */
    return (done);
}

int
descend(nltype *node, arctype **stkstart, arctype **stkp)
{
    arctype	*arcp;
    bool	ret;

    for ( arcp = node -> children ; arcp ; arcp = arcp -> arc_childlist ) {
#	ifdef DEBUG
	    visited++;
#	endif /* DEBUG */
	if ( arcp -> arc_childp -> cycleno != node -> cycleno
	    || ( arcp -> arc_childp -> flags & VISITED )
	    || ( arcp -> arc_flags & DEADARC ) )
	    continue;
#	ifdef DEBUG
	    viable++;
#	endif /* DEBUG */
	*stkp = arcp;
	if ( arcp -> arc_childp -> flags & CYCLEHEAD ) {
	    if ( addcycle( stkstart , stkp ) == FALSE )
		return( FALSE );
	    continue;
	}
	arcp -> arc_childp -> flags |= VISITED;
	ret = descend( arcp -> arc_childp , stkstart , stkp + 1 );
	arcp -> arc_childp -> flags &= ~VISITED;
	if ( ret == FALSE )
	    return( FALSE );
    }
    return (TRUE);
}

int
addcycle(arctype **stkstart, arctype **stkend)
{
    arctype	**arcpp;
    arctype	**stkloc;
    arctype	**stkp;
    arctype	**endlist;
    arctype	*minarc;
    arctype	*arcp;
    cltype	*clp;
    int		size;

    size = stkend - stkstart + 1;
    if ( size <= 1 )
	return( TRUE );
    for ( arcpp = stkstart , minarc = *arcpp ; arcpp <= stkend ; arcpp++ ) {
	if ( *arcpp > minarc )
	    continue;
	minarc = *arcpp;
	stkloc = arcpp;
    }
    for ( clp = cyclehead ; clp ; clp = clp -> next ) {
	if ( clp -> size != size )
	    continue;
	stkp = stkloc;
	endlist = &clp -> list[ size ];
	for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) {
	    if ( *stkp++ != *arcpp )
		break;
	    if ( stkp > stkend )
		stkp = stkstart;
	}
	if ( arcpp == endlist ) {
#	    ifdef DEBUG
		oldcycle++;
#	    endif /* DEBUG */
	    return( TRUE );
	}
    }
    clp = (cltype *)
	calloc( 1 , sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) );
    if ( clp == 0 ) {
	warnx("No room for %ld bytes of subcycle storage" ,
	    sizeof(cltype) + (size - 1) * sizeof(arctype *));
	return( FALSE );
    }
    stkp = stkloc;
    endlist = &clp -> list[ size ];
    for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) {
	arcp = *arcpp = *stkp++;
	if ( stkp > stkend )
	    stkp = stkstart;
	arcp -> arc_cyclecnt++;
	if ( ( arcp -> arc_flags & ONLIST ) == 0 ) {
	    arcp -> arc_flags |= ONLIST;
	    arcp -> arc_next = archead;
	    archead = arcp;
	}
    }
    clp -> size = size;
    clp -> next = cyclehead;
    cyclehead = clp;
#   ifdef DEBUG
	newcycle++;
	if ( debug & SUBCYCLELIST ) {
	    printsubcycle( clp );
	}
#   endif /* DEBUG */
    cyclecnt++;
    if ( cyclecnt >= CYCLEMAX )
	return( FALSE );
    return( TRUE );
}

void
compresslist()
{
    cltype	*clp;
    cltype	**prev;
    arctype	**arcpp;
    arctype	**endlist;
    arctype	*arcp;
    arctype	*maxarcp;
    arctype	*maxexitarcp;
    arctype	*maxwithparentarcp;
    arctype	*maxnoparentarcp;
    int		maxexitcnt;
    int		maxwithparentcnt;
    int		maxnoparentcnt;
#   ifdef DEBUG
        char	*type;
#   endif

    maxexitcnt = 0;
    maxwithparentcnt = 0;
    maxnoparentcnt = 0;
    for ( endlist = &archead , arcp = archead ; arcp ; ) {
	if ( arcp -> arc_cyclecnt == 0 ) {
	    arcp -> arc_flags &= ~ONLIST;
	    *endlist = arcp -> arc_next;
	    arcp -> arc_next = 0;
	    arcp = *endlist;
	    continue;
	}
	if ( arcp -> arc_childp -> flags & HASCYCLEXIT ) {
	    if ( arcp -> arc_cyclecnt > maxexitcnt ||
		( arcp -> arc_cyclecnt == maxexitcnt &&
		arcp -> arc_cyclecnt < maxexitarcp -> arc_count ) ) {
		maxexitcnt = arcp -> arc_cyclecnt;
		maxexitarcp = arcp;
	    }
	} else if ( arcp -> arc_childp -> parentcnt > 1 ) {
	    if ( arcp -> arc_cyclecnt > maxwithparentcnt ||
		( arcp -> arc_cyclecnt == maxwithparentcnt &&
		arcp -> arc_cyclecnt < maxwithparentarcp -> arc_count ) ) {
		maxwithparentcnt = arcp -> arc_cyclecnt;
		maxwithparentarcp = arcp;
	    }
	} else {
	    if ( arcp -> arc_cyclecnt > maxnoparentcnt ||
		( arcp -> arc_cyclecnt == maxnoparentcnt &&
		arcp -> arc_cyclecnt < maxnoparentarcp -> arc_count ) ) {
		maxnoparentcnt = arcp -> arc_cyclecnt;
		maxnoparentarcp = arcp;
	    }
	}
	endlist = &arcp -> arc_next;
	arcp = arcp -> arc_next;
    }
    if ( maxexitcnt > 0 ) {
	/*
	 *	first choice is edge leading to node with out-of-cycle parent
	 */
	maxarcp = maxexitarcp;
#	ifdef DEBUG
	    type = "exit";
#	endif /* DEBUG */
    } else if ( maxwithparentcnt > 0 ) {
	/*
	 *	second choice is edge leading to node with at least one
	 *	other in-cycle parent
	 */
	maxarcp = maxwithparentarcp;
#	ifdef DEBUG
	    type = "internal";
#	endif /* DEBUG */
    } else {
	/*
	 *	last choice is edge leading to node with only this arc as
	 *	a parent (as it will now be orphaned)
	 */
	maxarcp = maxnoparentarcp;
#	ifdef DEBUG
	    type = "orphan";
#	endif /* DEBUG */
    }
    maxarcp -> arc_flags |= DEADARC;
    maxarcp -> arc_childp -> parentcnt -= 1;
    maxarcp -> arc_childp -> npropcall -= maxarcp -> arc_count;
#   ifdef DEBUG
	if ( debug & BREAKCYCLE ) {
	    printf("[compresslist] delete %s arc: "
		"%s (%ld) -> %s from %d cycle(s)\n", type,
		maxarcp -> arc_parentp -> name, maxarcp -> arc_count,
		maxarcp -> arc_childp -> name, maxarcp -> arc_cyclecnt);
	}
#   endif /* DEBUG */
    printf("\t%s to %s with %ld calls\n", maxarcp->arc_parentp -> name,
	maxarcp->arc_childp->name, maxarcp->arc_count);
    prev = &cyclehead;
    for ( clp = cyclehead ; clp ; ) {
	endlist = &clp -> list[ clp -> size ];
	for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
	    if ( (*arcpp) -> arc_flags & DEADARC )
		break;
	if ( arcpp == endlist ) {
	    prev = &clp -> next;
	    clp = clp -> next;
	    continue;
	}
	for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
	    (*arcpp) -> arc_cyclecnt--;
	cyclecnt--;
	*prev = clp -> next;
	free( clp );
	clp = *prev;
    }
}

#ifdef DEBUG
void
printsubcycle(cltype *clp)
{
    arctype	**arcpp;
    arctype	**endlist;

    arcpp = clp -> list;
    printf( "%s <cycle %d>\n" , (*arcpp) -> arc_parentp -> name ,
	(*arcpp) -> arc_parentp -> cycleno ) ;
    for ( endlist = &clp -> list[ clp -> size ]; arcpp < endlist ; arcpp++ )
	printf( "\t(%ld) -> %s\n" , (*arcpp) -> arc_count ,
	    (*arcpp) -> arc_childp -> name ) ;
}
#endif /* DEBUG */

void
cycletime()
{
    int			cycle;
    nltype		*cyclenlp;
    nltype		*childp;

    for ( cycle = 1 ; cycle <= ncycle ; cycle += 1 ) {
	cyclenlp = &cyclenl[ cycle ];
	for ( childp = cyclenlp -> cnext ; childp ; childp = childp -> cnext ) {
	    if ( childp -> propfraction == 0.0 ) {
		    /*
		     * all members have the same propfraction except those
		     *	that were excluded with -E
		     */
		continue;
	    }
	    cyclenlp -> time += childp -> time;
	}
	cyclenlp -> propself = cyclenlp -> propfraction * cyclenlp -> time;
    }
}

    /*
     *	in one top to bottom pass over the topologically sorted namelist
     *	propagate:
     *		printflag as the union of parents' printflags
     *		propfraction as the sum of fractional parents' propfractions
     *	and while we're here, sum time for functions.
     */
void
doflags()
{
    int		index;
    nltype	*childp;
    nltype	*oldhead;

    oldhead = 0;
    for ( index = nname-1 ; index >= 0 ; index -= 1 ) {
	childp = topsortnlp[ index ];
	    /*
	     *	if we haven't done this function or cycle,
	     *	inherit things from parent.
	     *	this way, we are linear in the number of arcs
	     *	since we do all members of a cycle (and the cycle itself)
	     *	as we hit the first member of the cycle.
	     */
	if ( childp -> cyclehead != oldhead ) {
	    oldhead = childp -> cyclehead;
	    inheritflags( childp );
	}
#	ifdef DEBUG
	    if ( debug & PROPDEBUG ) {
		printf( "[doflags] " );
		printname( childp );
		printf( " inherits printflag %d and propfraction %f\n" ,
			childp -> printflag , childp -> propfraction );
	    }
#	endif /* DEBUG */
	if ( ! childp -> printflag ) {
		/*
		 *	printflag is off
		 *	it gets turned on by
		 *	being on -f list,
		 *	or there not being any -f list and not being on -e list.
		 */
	    if (   onlist( flist , childp -> name )
		|| ( !fflag && !onlist( elist , childp -> name ) ) ) {
		childp -> printflag = TRUE;
	    }
	} else {
		/*
		 *	this function has printing parents:
		 *	maybe someone wants to shut it up
		 *	by putting it on -e list.  (but favor -f over -e)
		 */
	    if (  ( !onlist( flist , childp -> name ) )
		&& onlist( elist , childp -> name ) ) {
		childp -> printflag = FALSE;
	    }
	}
	if ( childp -> propfraction == 0.0 ) {
		/*
		 *	no parents to pass time to.
		 *	collect time from children if
		 *	its on -F list,
		 *	or there isn't any -F list and its not on -E list.
		 */
	    if ( onlist( Flist , childp -> name )
		|| ( !Fflag && !onlist( Elist , childp -> name ) ) ) {
		    childp -> propfraction = 1.0;
	    }
	} else {
		/*
		 *	it has parents to pass time to,
		 *	but maybe someone wants to shut it up
		 *	by puttting it on -E list.  (but favor -F over -E)
		 */
	    if (  !onlist( Flist , childp -> name )
		&& onlist( Elist , childp -> name ) ) {
		childp -> propfraction = 0.0;
	    }
	}
	childp -> propself = childp -> time * childp -> propfraction;
	printtime += childp -> propself;
#	ifdef DEBUG
	    if ( debug & PROPDEBUG ) {
		printf( "[doflags] " );
		printname( childp );
		printf( " ends up with printflag %d and propfraction %f\n" ,
			childp -> printflag , childp -> propfraction );
		printf( "time %f propself %f printtime %f\n" ,
			childp -> time , childp -> propself , printtime );
	    }
#	endif /* DEBUG */
    }
}

    /*
     *	check if any parent of this child
     *	(or outside parents of this cycle)
     *	have their print flags on and set the
     *	print flag of the child (cycle) appropriately.
     *	similarly, deal with propagation fractions from parents.
     */
void
inheritflags(nltype *childp)
{
    nltype	*headp;
    arctype	*arcp;
    nltype	*parentp;
    nltype	*memp;

    headp = childp -> cyclehead;
    if ( childp == headp ) {
	    /*
	     *	just a regular child, check its parents
	     */
	childp -> printflag = FALSE;
	childp -> propfraction = 0.0;
	for (arcp = childp -> parents ; arcp ; arcp = arcp -> arc_parentlist) {
	    parentp = arcp -> arc_parentp;
	    if ( childp == parentp ) {
		continue;
	    }
	    childp -> printflag |= parentp -> printflag;
		/*
		 *	if the child was never actually called
		 *	(e.g. this arc is static (and all others are, too))
		 *	no time propagates along this arc.
		 */
	    if ( arcp -> arc_flags & DEADARC ) {
		continue;
	    }
	    if ( childp -> npropcall ) {
		childp -> propfraction += parentp -> propfraction
					* ( ( (double) arcp -> arc_count )
					  / ( (double) childp -> npropcall ) );
	    }
	}
    } else {
	    /*
	     *	its a member of a cycle, look at all parents from
	     *	outside the cycle
	     */
	headp -> printflag = FALSE;
	headp -> propfraction = 0.0;
	for ( memp = headp -> cnext ; memp ; memp = memp -> cnext ) {
	    for (arcp = memp->parents ; arcp ; arcp = arcp->arc_parentlist) {
		if ( arcp -> arc_parentp -> cyclehead == headp ) {
		    continue;
		}
		parentp = arcp -> arc_parentp;
		headp -> printflag |= parentp -> printflag;
		    /*
		     *	if the cycle was never actually called
		     *	(e.g. this arc is static (and all others are, too))
		     *	no time propagates along this arc.
		     */
		if ( arcp -> arc_flags & DEADARC ) {
		    continue;
		}
		if ( headp -> npropcall ) {
		    headp -> propfraction += parentp -> propfraction
					* ( ( (double) arcp -> arc_count )
					  / ( (double) headp -> npropcall ) );
		}
	    }
	}
	for ( memp = headp ; memp ; memp = memp -> cnext ) {
	    memp -> printflag = headp -> printflag;
	    memp -> propfraction = headp -> propfraction;
	}
    }
}