+/*
+ * Copyright (c) 1983 Regents of the University of California.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms are permitted
+ * provided that the above copyright notice and this paragraph are
+ * duplicated in all such forms and that any documentation,
+ * advertising materials, and other materials related to such
+ * distribution and use acknowledge that the software was developed
+ * by the University of California, Berkeley. The name of the
+ * University may not be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
+ * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
+ */
+
#ifndef lint
- static char *sccsid = "@(#)arcs.c 1.1 (Berkeley) %G%";
-#endif lint
+static char sccsid[] = "@(#)arcs.c 5.5 (Berkeley) %G%";
+#endif /* not lint */
-#include "dprof.h"
+#include "gprof.h"
-topcmp( npp1 , npp2 )
- nltype **npp1;
- nltype **npp2;
+ /*
+ * add (or just increment) an arc
+ */
+addarc( parentp , childp , count )
+ nltype *parentp;
+ nltype *childp;
+ long count;
{
- return (*npp1) -> toporder - (*npp2) -> toporder;
+ arctype *calloc();
+ arctype *arcp;
+
+# ifdef DEBUG
+ if ( debug & TALLYDEBUG ) {
+ printf( "[addarc] %d 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 %d += %d\n" ,
+ arcp -> arc_count , count );
+ }
+# endif DEBUG
+ arcp -> arc_count += count;
+ return;
+ }
+ arcp = 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;
}
/*
- * sort by decreasing total time (time+childtime)
- * if times are equal, but one is a cycle header,
- * say that's first (e.g. less)
+ * the code below topologically sorts the graph (collapsing cycles),
+ * and propagates time bottom up and flags top down.
+ */
+
+ /*
+ * the topologically sorted name list pointers
*/
-int
-totalcmp( npp1 , npp2 )
+nltype **topsortnlp;
+
+topcmp( npp1 , npp2 )
nltype **npp1;
nltype **npp2;
{
- register nltype *np1 = *npp1;
- register nltype *np2 = *npp2;
- double diff;
-
- diff = ( np1 -> time + np1 -> childtime )
- - ( np2 -> time + np2 -> childtime );
- if ( diff < 0.0 )
- return 1;
- if ( diff > 0.0 )
- return -1;
- if ( np1 -> name == 0 && np1 -> cycleno != 0 )
- return -1;
- if ( np2 -> name == 0 && np1 -> cycleno != 0 )
- return 1;
- return 0;
+ return (*npp1) -> toporder - (*npp2) -> toporder;
}
+nltype **
doarcs()
{
- nltype *parentp;
+ nltype *parentp, **timesortnlp;
arctype *arcp;
- nltype **topsortnlp;
long index;
- nltype *childp;
- double share;
/*
* initialize various things:
} else {
parentp -> selfcalls = 0;
}
- parentp -> toporder = 0;
+ 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 );
+ }
}
/*
* topologically order things
- * from each of the roots of the call graph
+ * if any node is unnumbered,
+ * number it and any of its descendents.
*/
for ( parentp = nl ; parentp < npe ; parentp++ ) {
- if ( parentp -> parents == 0 ) {
+ if ( parentp -> toporder == DFN_NAN ) {
dfn( parentp );
}
}
}
}
# 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,
- * propogate children times
+ * propogate 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 ) {
+ fprintf( stderr , "%s: ran out of memory for sorting\n" , whoami );
+ }
+ 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 );
+}
+
+dotime()
+{
+ int index;
+
+ cycletime();
for ( index = 0 ; index < nname ; index += 1 ) {
- parentp = topsortnlp[ index ];
- for ( arcp = parentp->children ; arcp ; arcp = arcp->arc_childlist ) {
- childp = arcp -> arc_childp;
-# ifdef DEBUG
- if ( debug & ARCDEBUG ) {
- printf( "[doarcs] " );
- printname( parentp );
- printf( " calls " );
- printname( childp );
- printf( " %d (%d) times\n" ,
- arcp -> arc_count , childp -> ncall );
- }
-# endif DEBUG
- if ( arcp -> arc_count == 0 ) {
+ timepropagate( topsortnlp[ index ] );
+ }
+}
+
+timepropagate( parentp )
+ 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_count == 0 ) {
+ continue;
+ }
+ if ( childp == parentp ) {
+ continue;
+ }
+ if ( childp -> propfraction == 0.0 ) {
+ continue;
+ }
+ if ( childp -> cyclehead != childp ) {
+ if ( parentp -> cycleno == childp -> cycleno ) {
continue;
}
- if ( childp -> ncall == 0 ) {
- continue;
+ if ( parentp -> toporder <= childp -> toporder ) {
+ fprintf( stderr , "[propagate] toporder botches\n" );
}
- if ( childp == parentp ) {
+ childp = childp -> cyclehead;
+ } else {
+ if ( parentp -> toporder <= childp -> toporder ) {
+ fprintf( stderr , "[propagate] toporder botches\n" );
continue;
}
- if ( childp -> cyclehead != childp ) {
- if ( parentp -> cycleno == childp -> cycleno ) {
- continue;
- }
-# ifdef DEBUG
- if ( debug & ARCDEBUG ) {
- printf( "[doarcs]\t it's a call into cycle %d\n" ,
- childp -> cycleno );
- }
-# endif DEBUG
- if ( parentp -> toporder <= childp -> toporder ) {
- fprintf( stderr , "[doarcs] toporder botches\n" );
- }
- childp = childp -> cyclehead;
- } else {
- if ( parentp -> toporder <= childp -> toporder ) {
- fprintf( stderr , "[doarcs] toporder botches\n" );
- continue;
- }
- }
- /*
- * distribute time for this arc
- */
- arcp -> arc_time = childp -> time *
- ( ( (double) arcp -> arc_count ) /
- ( (double) childp -> ncall ) );
- arcp -> arc_childtime = childp -> childtime *
- ( ( (double) arcp -> arc_count ) /
- ( (double) childp -> ncall ) );
- share = arcp -> arc_time + arcp -> arc_childtime;
-# ifdef DEBUG
- if ( debug & ARCDEBUG ) {
- printf( "[doarcs]\t " );
- printname( childp );
- printf( " time %8.2f + childtime %8.2f\n" ,
- childp -> time , childp -> childtime );
- printf( "[doarcs]\t this is %d arcs of the %d calls\n",
+ }
+ if ( childp -> ncall == 0 ) {
+ continue;
+ }
+ /*
+ * distribute time for this arc
+ */
+ arcp -> arc_time = childp -> time
+ * ( ( (double) arcp -> arc_count ) /
+ ( (double) childp -> ncall ) );
+ arcp -> arc_childtime = childp -> childtime
+ * ( ( (double) arcp -> arc_count ) /
+ ( (double) childp -> ncall ) );
+ 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 %d/%d\n" ,
+ childp -> time , childp -> childtime ,
arcp -> arc_count , childp -> ncall );
- printf( "[doarcs]\t so this gives %8.2f+%8.2f to %s\n" ,
- arcp -> arc_time , arcp -> arc_childtime ,
- parentp -> name );
- }
-# endif DEBUG
- parentp -> childtime += share;
- /*
- * add this share to the cycle header, if any
- */
- if ( parentp -> cyclehead != parentp ) {
-# ifdef DEBUG
- if ( debug & ARCDEBUG ) {
- printf( "[doarcs]\t and to cycle %d\n" ,
- parentp -> cycleno );
- }
-# endif DEBUG
- parentp -> cyclehead -> childtime += share;
+ printf( "[dotime] parent\t" );
+ printname( parentp );
+ printf( "\n[dotime] share %f\n" , share );
}
- }
+# endif DEBUG
}
- printdprof();
}
cyclelink()
{
register nltype *nlp;
- register nltype *parentp;
- register nltype *childp;
register nltype *cyclenlp;
int cycle;
+ nltype *memberp;
arctype *arcp;
- long ncall;
- double time;
- long callsamong;
/*
* Count the number of cycles, and initialze the cycle lists
*/
- cyclemax = 0;
+ ncycle = 0;
for ( nlp = nl ; nlp < npe ; nlp++ ) {
/*
* this is how you find unattached cycles
*/
if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) {
- cyclemax += 1;
+ ncycle += 1;
}
}
- if ( cyclemax > ncycles ) {
- fprintf( stderr , "prof: %d cycles in %d names exceeds %f%%\n" ,
- cyclemax , nname , CYCLEFRACTION * 100.0 );
- exit( 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 ) {
+ fprintf( stderr , "%s: No room for %d bytes of cycle headers\n" ,
+ whoami , ( ncycle + 1 ) * sizeof( nltype ) );
+ done();
}
/*
* now link cycles to true cycleheads,
*/
cycle = 0;
for ( nlp = nl ; nlp < npe ; nlp++ ) {
- if ( nlp -> cyclehead != nlp || nlp -> cnext == 0 ) {
+ if ( !( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) ) {
continue;
}
cycle += 1;
- cyclenlp = &nl[nname+cycle];
- cyclenlp -> cycleno = cycle;
- cyclenlp -> cyclehead = cyclenlp;
- cyclenlp -> cnext = nlp;
+ 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] " );
}
# endif DEBUG
/*
- * n-squaredly (in the size of the cycle)
- * find all the call within the cycle
- * (including self-recursive calls)
- * and remove them, thus making the cycle into
- * `node' with calls only from the outside.
- * note: that this doesn't deal with
- * self-recursive calls outside cycles (sigh).
+ * 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
*/
- callsamong = 0;
- for ( parentp = nlp ; parentp ; parentp = parentp -> cnext ) {
- parentp -> cycleno = cycle;
- parentp -> cyclehead = cyclenlp;
- for ( childp = nlp ; childp ; childp = childp -> cnext ) {
- if ( parentp == childp ) {
+ for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) {
+ for ( arcp=memberp->parents ; arcp ; arcp=arcp->arc_parentlist ) {
+ if ( arcp -> arc_parentp == memberp ) {
continue;
}
- arcp = arclookup( parentp , childp );
- if ( arcp != 0 ) {
- callsamong += arcp -> arc_count;
-# ifdef DEBUG
- if ( debug & CYCLEDEBUG ) {
- printf("[cyclelink] %s calls sibling %s %d times\n",
- parentp -> name , childp -> name ,
- arcp -> arc_count );
- }
-# endif DEBUG
+ if ( arcp -> arc_parentp -> cycleno == cycle ) {
+ cyclenlp -> selfcalls += arcp -> arc_count;
+ } else {
+ cyclenlp -> ncall += arcp -> arc_count;
}
}
}
+ }
+}
+
+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.
+ */
+doflags()
+{
+ int index;
+ nltype *childp;
+ nltype *oldhead;
+
+ oldhead = 0;
+ for ( index = nname-1 ; index >= 0 ; index -= 1 ) {
+ childp = topsortnlp[ index ];
/*
- * collect calls and time around the cycle,
- * and save it in the cycle header.
+ * 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.
*/
- ncall = -callsamong;
- time = 0.0;
- for ( parentp = nlp ; parentp ; parentp = parentp -> cnext ) {
- ncall += parentp -> ncall;
- time += parentp -> time;
+ if ( childp -> cyclehead != oldhead ) {
+ oldhead = childp -> cyclehead;
+ inheritflags( childp );
}
# ifdef DEBUG
- if ( debug & CYCLEDEBUG ) {
- printf( "[cyclelink] cycle %d %f ticks in %d (%d) calls\n" ,
- cycle , time , ncall , callsamong );
+ 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
- cyclenlp -> ncall = ncall;
- cyclenlp -> selfcalls = callsamong;
- cyclenlp -> time = time;
- cyclenlp -> childtime = 0.0;
+ }
+}
+
+ /*
+ * 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.
+ */
+inheritflags( childp )
+ 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 ( childp -> ncall ) {
+ childp -> propfraction += parentp -> propfraction
+ * ( ( (double) arcp -> arc_count )
+ / ( (double) childp -> ncall ) );
+ }
+ }
+ } 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 ( headp -> ncall ) {
+ headp -> propfraction += parentp -> propfraction
+ * ( ( (double) arcp -> arc_count )
+ / ( (double) headp -> ncall ) );
+ }
+ }
+ }
+ for ( memp = headp ; memp ; memp = memp -> cnext ) {
+ memp -> printflag = headp -> printflag;
+ memp -> propfraction = headp -> propfraction;
+ }
}
}