[unix-history] / usr / src / usr.bin / gprof / arcs.c

#ifndef lint
    static	char *sccsid = "@(#)arcs.c	1.2 (Berkeley) %G%";
#endif lint

#include "gprof.h"

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

    /*
     *	sort by decreasing total time (time+childtime)
     *	if times are equal, but one is a cycle header,
     *	say that's first (e.g. less)
     */
int
totalcmp( 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;
}

doarcs()
{
    nltype	*parentp;
    arctype	*arcp;
    nltype	**topsortnlp;
    long	index;
    nltype	*childp;
    double	share;

	/*
	 *	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 -> toporder = 0;
	parentp -> cycleno = 0;
	parentp -> cyclehead = parentp;
	parentp -> cnext = 0;
    }
	/*
	 *	topologically order things
	 *	from each of the roots of the call graph
	 */
    for ( parentp = nl ; parentp < npe ; parentp++ ) {
	if ( parentp -> parents == 0 ) {
	    dfn( parentp );
	}
    }
	/*
	 *	link together nodes on the same cycle
	 */
    cyclelink();
	/*
	 *	Sort the symbol table in reverse topological order
	 */
    topsortnlp = (nltype **) calloc( nname , sizeof(nltype *) );
    if ( topsortnlp == (nltype **) 0 ) {
	fprintf( stderr , "[doarcs] ran out of memory for topo sorting\n" );
    }
    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 bottom, 
	 *	propogate children times
	 */
    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 ) {
		continue;
	    }
	    if ( childp -> ncall == 0 ) {
		continue;
	    }
	    if ( childp == parentp ) {
		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",
			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;
	    }
	}
    }
    printgprof();
}

cyclelink()
{
    register nltype	*nlp;
    register nltype	*parentp;
    register nltype	*childp;
    register nltype	*cyclenlp;
    int			cycle;
    arctype		*arcp;
    long		ncall;
    double		time;
    long		callsamong;

	/*
	 *	Count the number of cycles, and initialze the cycle lists
	 */
    cyclemax = 0;
    for ( nlp = nl ; nlp < npe ; nlp++ ) {
	    /*
	     *	this is how you find unattached cycles
	     */
	if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) {
	    cyclemax += 1;
	}
    }
    if ( cyclemax > ncycles ) {
	fprintf( stderr , "prof: %d cycles in %d names exceeds %f%%\n" ,
		cyclemax , nname , CYCLEFRACTION * 100.0 );
	exit( 1 );
    }
	/*
	 *	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 = &nl[nname+cycle];
	cyclenlp -> cycleno = cycle;
	cyclenlp -> cyclehead = cyclenlp;
	cyclenlp -> cnext = nlp;
#	ifdef DEBUG
	    if ( debug & CYCLEDEBUG ) {
		printf( "[cyclelink] " );
		printname( nlp );
		printf( " is the head of cycle %d\n" , cycle );
	    }
#	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).
	     */
	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 ) {
		    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
		}
	    }
	}
	    /*
	     *	collect calls and time around the cycle,
	     *	and save it in the cycle header.
	     */
	ncall = -callsamong;
	time = 0.0;
	for ( parentp = nlp ; parentp ; parentp = parentp -> cnext ) {
	    ncall += parentp -> ncall;
	    time += parentp -> time;
	}
#	ifdef DEBUG
	    if ( debug & CYCLEDEBUG ) {
		printf( "[cyclelink] cycle %d %f ticks in %d (%d) calls\n" ,
			cycle , time , ncall , callsamong );
	    }
#	endif DEBUG
	cyclenlp -> ncall = ncall;
	cyclenlp -> selfcalls = callsamong;
	cyclenlp -> time = time;
	cyclenlp -> childtime = 0.0;
    }
}
Commit	Line	Data
ca41b3be	1	#ifndef lint
31f0a970	2	static char *sccsid = "@(#)arcs.c 1.2 (Berkeley) %G%";
ca41b3be PK	3	#endif lint
ca41b3be PK	4
31f0a970	5	#include "gprof.h"
ca41b3be PK	6
	7	topcmp( npp1 , npp2 )
	8	nltype **npp1;
	9	nltype **npp2;
	10	{
	11	return (npp1) -> toporder - (npp2) -> toporder;
	12	}
	13
	14	/*
	15	* sort by decreasing total time (time+childtime)
	16	* if times are equal, but one is a cycle header,
	17	* say that's first (e.g. less)
	18	*/
	19	int
	20	totalcmp( npp1 , npp2 )
	21	nltype **npp1;
	22	nltype **npp2;
	23	{
	24	register nltype np1 = npp1;
	25	register nltype np2 = npp2;
	26	double diff;
	27
	28	diff = ( np1 -> time + np1 -> childtime )
	29	- ( np2 -> time + np2 -> childtime );
	30	if ( diff < 0.0 )
	31	return 1;
	32	if ( diff > 0.0 )
	33	return -1;
	34	if ( np1 -> name == 0 && np1 -> cycleno != 0 )
	35	return -1;
	36	if ( np2 -> name == 0 && np1 -> cycleno != 0 )
	37	return 1;
	38	return 0;
	39	}
	40
	41	doarcs()
	42	{
	43	nltype *parentp;
	44	arctype *arcp;
	45	nltype **topsortnlp;
	46	long index;
	47	nltype *childp;
	48	double share;
	49
	50	/*
	51	* initialize various things:
	52	* zero out child times.
	53	* count self-recursive calls.
	54	* indicate that nothing is on cycles.
	55	*/
	56	for ( parentp = nl ; parentp < npe ; parentp++ ) {
	57	parentp -> childtime = 0.0;
	58	arcp = arclookup( parentp , parentp );
	59	if ( arcp != 0 ) {
	60	parentp -> ncall -= arcp -> arc_count;
	61	parentp -> selfcalls = arcp -> arc_count;
	62	} else {
	63	parentp -> selfcalls = 0;
	64	}
	65	parentp -> toporder = 0;
	66	parentp -> cycleno = 0;
	67	parentp -> cyclehead = parentp;
	68	parentp -> cnext = 0;
	69	}
70	/*
71	* topologically order things
72	* from each of the roots of the call graph
73	*/
74	for ( parentp = nl ; parentp < npe ; parentp++ ) {
75	if ( parentp -> parents == 0 ) {
76	dfn( parentp );
77	}
78	}
79	/*
80	* link together nodes on the same cycle
81	*/
82	cyclelink();
83	/*
84	* Sort the symbol table in reverse topological order
85	*/
86	topsortnlp = (nltype *) calloc( nname , sizeof(nltype ) );
87	if ( topsortnlp == (nltype **) 0 ) {
88	fprintf( stderr , "[doarcs] ran out of memory for topo sorting\n" );
89	}
90	for ( index = 0 ; index < nname ; index += 1 ) {
91	topsortnlp[ index ] = &nl[ index ];
92	}
93	qsort( topsortnlp , nname , sizeof(nltype *) , topcmp );
94	# ifdef DEBUG
95	if ( debug & DFNDEBUG ) {
96	printf( "[doarcs] topological sort listing\n" );
97	for ( index = 0 ; index < nname ; index += 1 ) {
98	printf( "[doarcs] " );
99	printf( "%d:" , topsortnlp[ index ] -> toporder );
100	printname( topsortnlp[ index ] );
101	printf( "\n" );
102	}
103	}
104	# endif DEBUG
105	/*
106	* starting from the topological bottom,
107	* propogate children times
108	*/
109	for ( index = 0 ; index < nname ; index += 1 ) {
110	parentp = topsortnlp[ index ];
111	for ( arcp = parentp->children ; arcp ; arcp = arcp->arc_childlist ) {
112	childp = arcp -> arc_childp;
113	# ifdef DEBUG
114	if ( debug & ARCDEBUG ) {
115	printf( "[doarcs] " );
116	printname( parentp );
117	printf( " calls " );
118	printname( childp );
119	printf( " %d (%d) times\n" ,
120	arcp -> arc_count , childp -> ncall );
121	}
122	# endif DEBUG
123	if ( arcp -> arc_count == 0 ) {
124	continue;
125	}
126	if ( childp -> ncall == 0 ) {
127	continue;
128	}
129	if ( childp == parentp ) {
130	continue;
131	}
132	if ( childp -> cyclehead != childp ) {
133	if ( parentp -> cycleno == childp -> cycleno ) {
134	continue;
135	}
136	# ifdef DEBUG
137	if ( debug & ARCDEBUG ) {
138	printf( "[doarcs]\t it's a call into cycle %d\n" ,
139	childp -> cycleno );
140	}
141	# endif DEBUG
142	if ( parentp -> toporder <= childp -> toporder ) {
143	fprintf( stderr , "[doarcs] toporder botches\n" );
144	}
145	childp = childp -> cyclehead;
146	} else {
147	if ( parentp -> toporder <= childp -> toporder ) {
148	fprintf( stderr , "[doarcs] toporder botches\n" );
149	continue;
150	}
151	}
152	/*
153	* distribute time for this arc
154	*/
155	arcp -> arc_time = childp -> time *
156	( ( (double) arcp -> arc_count ) /
157	( (double) childp -> ncall ) );
158	arcp -> arc_childtime = childp -> childtime *
159	( ( (double) arcp -> arc_count ) /
160	( (double) childp -> ncall ) );
161	share = arcp -> arc_time + arcp -> arc_childtime;
162	# ifdef DEBUG
163	if ( debug & ARCDEBUG ) {
164	printf( "[doarcs]\t " );
165	printname( childp );
166	printf( " time %8.2f + childtime %8.2f\n" ,
167	childp -> time , childp -> childtime );
168	printf( "[doarcs]\t this is %d arcs of the %d calls\n",
169	arcp -> arc_count , childp -> ncall );
170	printf( "[doarcs]\t so this gives %8.2f+%8.2f to %s\n" ,
171	arcp -> arc_time , arcp -> arc_childtime ,
172	parentp -> name );
173	}
174	# endif DEBUG
175	parentp -> childtime += share;
176	/*
177	* add this share to the cycle header, if any
178	*/
179	if ( parentp -> cyclehead != parentp ) {
180	# ifdef DEBUG
181	if ( debug & ARCDEBUG ) {
182	printf( "[doarcs]\t and to cycle %d\n" ,
183	parentp -> cycleno );
184	}
185	# endif DEBUG
186	parentp -> cyclehead -> childtime += share;
187	}
188	}
189	}
31f0a970	190	printgprof();
ca41b3be PK	191	}
	192
	193	cyclelink()
	194	{
	195	register nltype *nlp;
	196	register nltype *parentp;
	197	register nltype *childp;
	198	register nltype *cyclenlp;
	199	int cycle;
	200	arctype *arcp;
	201	long ncall;
	202	double time;
	203	long callsamong;
	204
	205	/*
	206	* Count the number of cycles, and initialze the cycle lists
	207	*/
	208	cyclemax = 0;
	209	for ( nlp = nl ; nlp < npe ; nlp++ ) {
	210	/*
	211	* this is how you find unattached cycles
	212	*/
	213	if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) {
	214	cyclemax += 1;
	215	}
	216	}
	217	if ( cyclemax > ncycles ) {
	218	fprintf( stderr , "prof: %d cycles in %d names exceeds %f%%\n" ,
	219	cyclemax , nname , CYCLEFRACTION * 100.0 );
	220	exit( 1 );
	221	}
	222	/*
	223	* now link cycles to true cycleheads,
	224	* number them, accumulate the data for the cycle
	225	*/
	226	cycle = 0;
	227	for ( nlp = nl ; nlp < npe ; nlp++ ) {
	228	if ( nlp -> cyclehead != nlp \|\| nlp -> cnext == 0 ) {
	229	continue;
	230	}
	231	cycle += 1;
	232	cyclenlp = &nl[nname+cycle];
	233	cyclenlp -> cycleno = cycle;
	234	cyclenlp -> cyclehead = cyclenlp;
	235	cyclenlp -> cnext = nlp;
	236	# ifdef DEBUG
	237	if ( debug & CYCLEDEBUG ) {
	238	printf( "[cyclelink] " );
	239	printname( nlp );
	240	printf( " is the head of cycle %d\n" , cycle );
	241	}
	242	# endif DEBUG
	243	/*
	244	* n-squaredly (in the size of the cycle)
	245	* find all the call within the cycle
	246	* (including self-recursive calls)
	247	* and remove them, thus making the cycle into
	248	* `node' with calls only from the outside.
	249	* note: that this doesn't deal with
	250	* self-recursive calls outside cycles (sigh).
	251	*/
	252	callsamong = 0;
	253	for ( parentp = nlp ; parentp ; parentp = parentp -> cnext ) {
	254	parentp -> cycleno = cycle;
255	parentp -> cyclehead = cyclenlp;
256	for ( childp = nlp ; childp ; childp = childp -> cnext ) {
257	if ( parentp == childp ) {
258	continue;
259	}
260	arcp = arclookup( parentp , childp );
261	if ( arcp != 0 ) {
262	callsamong += arcp -> arc_count;
263	# ifdef DEBUG
264	if ( debug & CYCLEDEBUG ) {
265	printf("[cyclelink] %s calls sibling %s %d times\n",
266	parentp -> name , childp -> name ,
267	arcp -> arc_count );
268	}
269	# endif DEBUG
270	}
271	}
272	}
273	/*
274	* collect calls and time around the cycle,
275	* and save it in the cycle header.
276	*/
277	ncall = -callsamong;
278	time = 0.0;
279	for ( parentp = nlp ; parentp ; parentp = parentp -> cnext ) {
280	ncall += parentp -> ncall;
281	time += parentp -> time;
282	}
283	# ifdef DEBUG
284	if ( debug & CYCLEDEBUG ) {
285	printf( "[cyclelink] cycle %d %f ticks in %d (%d) calls\n" ,
286	cycle , time , ncall , callsamong );
287	}
288	# endif DEBUG
289	cyclenlp -> ncall = ncall;
290	cyclenlp -> selfcalls = callsamong;
291	cyclenlp -> time = time;
292	cyclenlp -> childtime = 0.0;
293	}
294	}