X-Git-Url: https://git.subgeniuskitty.com/unix-history/.git/blobdiff_plain/29da1d2654c266a2f3bfdf1610389234ec4db45a..77002fe106c8c541f942bf42dcc1c061a0a614ae:/usr/src/usr.bin/gprof/arcs.c

diff --git a/usr/src/usr.bin/gprof/arcs.c b/usr/src/usr.bin/gprof/arcs.c
index 450a48ae08..dd3118d940 100644
--- a/usr/src/usr.bin/gprof/arcs.c
+++ b/usr/src/usr.bin/gprof/arcs.c
@@ -1,5 +1,5 @@
 #ifndef lint
-    static	char *sccsid = "@(#)arcs.c	1.3 (Berkeley) %G%";
+    static	char *sccsid = "@(#)arcs.c	1.13 (Berkeley) %G%";
 #endif lint
 
 #include "gprof.h"
@@ -12,7 +12,7 @@ addarc( parentp , childp , count )
     nltype	*childp;
     long	count;
 {
-    arctype		*malloc();
+    arctype		*calloc();
     arctype		*arcp;
 
 #   ifdef DEBUG
@@ -35,7 +35,7 @@ addarc( parentp , childp , count )
 	arcp -> arc_count += count;
 	return;
     }
-    arcp = malloc( sizeof *arcp );
+    arcp = calloc( 1 , sizeof *arcp );
     arcp -> arc_parentp = parentp;
     arcp -> arc_childp = childp;
     arcp -> arc_count = count;
@@ -51,48 +51,28 @@ addarc( parentp , childp , count )
     childp -> parents = arcp;
 }
 
-topcmp( npp1 , npp2 )
-    nltype	**npp1;
-    nltype	**npp2;
-{
-    return (*npp1) -> toporder - (*npp2) -> toporder;
-}
+    /*
+     *	the code below topologically sorts the graph (collapsing cycles),
+     *	and propagates time bottom up and flags top down.
+     */
 
     /*
-     *	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 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;
 }
 
 doarcs()
 {
     nltype	*parentp;
     arctype	*arcp;
-    nltype	**topsortnlp;
     long	index;
-    nltype	*childp;
-    double	share;
 
 	/*
 	 *	initialize various things:
@@ -109,20 +89,25 @@ doarcs()
 	} else {
 	    parentp -> selfcalls = 0;
 	}
-	if ( cflag ) {
-	    findcalls( parentp , parentp -> value , (parentp+1) -> value );
-	}
-	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 ) {
+	    findcalls( 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 );
 	}
     }
@@ -152,122 +137,146 @@ doarcs()
 	    }
 	}
 #   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();
+    printgprof();
+}
+
+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
     }
-    printgprof();
 }
 
 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,
@@ -275,14 +284,28 @@ cyclelink()
 	 */
     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] " );
@@ -291,54 +314,201 @@ 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
-	cyclenlp -> ncall = ncall;
-	cyclenlp -> selfcalls = callsamong;
-	cyclenlp -> time = time;
-	cyclenlp -> childtime = 0.0;
+	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.
+     */
+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;
+	    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;
+		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;
+	}
     }
 }