xref: /original-bsd/usr.bin/gprof/arcs.c (revision e7d21e74)
1 /*
2  * Copyright (c) 1983, 1993
3  *	The Regents of the University of California.  All rights reserved.
4  *
5  * %sccs.include.redist.c%
6  */
7 
8 #ifndef lint
9 static char sccsid[] = "@(#)arcs.c	8.1 (Berkeley) 06/06/93";
10 #endif /* not lint */
11 
12 #include "gprof.h"
13 
14 #ifdef DEBUG
15 int visited;
16 int viable;
17 int newcycle;
18 int oldcycle;
19 #endif DEBUG
20 
21     /*
22      *	add (or just increment) an arc
23      */
addarc(parentp,childp,count)24 addarc( parentp , childp , count )
25     nltype	*parentp;
26     nltype	*childp;
27     long	count;
28 {
29     arctype		*arcp;
30 
31 #   ifdef DEBUG
32 	if ( debug & TALLYDEBUG ) {
33 	    printf( "[addarc] %d arcs from %s to %s\n" ,
34 		    count , parentp -> name , childp -> name );
35 	}
36 #   endif DEBUG
37     arcp = arclookup( parentp , childp );
38     if ( arcp != 0 ) {
39 	    /*
40 	     *	a hit:  just increment the count.
41 	     */
42 #	ifdef DEBUG
43 	    if ( debug & TALLYDEBUG ) {
44 		printf( "[tally] hit %d += %d\n" ,
45 			arcp -> arc_count , count );
46 	    }
47 #	endif DEBUG
48 	arcp -> arc_count += count;
49 	return;
50     }
51     arcp = (arctype *)calloc( 1 , sizeof *arcp );
52     arcp -> arc_parentp = parentp;
53     arcp -> arc_childp = childp;
54     arcp -> arc_count = count;
55 	/*
56 	 *	prepend this child to the children of this parent
57 	 */
58     arcp -> arc_childlist = parentp -> children;
59     parentp -> children = arcp;
60 	/*
61 	 *	prepend this parent to the parents of this child
62 	 */
63     arcp -> arc_parentlist = childp -> parents;
64     childp -> parents = arcp;
65 }
66 
67     /*
68      *	the code below topologically sorts the graph (collapsing cycles),
69      *	and propagates time bottom up and flags top down.
70      */
71 
72     /*
73      *	the topologically sorted name list pointers
74      */
75 nltype	**topsortnlp;
76 
topcmp(npp1,npp2)77 topcmp( npp1 , npp2 )
78     nltype	**npp1;
79     nltype	**npp2;
80 {
81     return (*npp1) -> toporder - (*npp2) -> toporder;
82 }
83 
84 nltype **
doarcs()85 doarcs()
86 {
87     nltype	*parentp, **timesortnlp;
88     arctype	*arcp;
89     long	index;
90     long	pass;
91 
92 	/*
93 	 *	initialize various things:
94 	 *	    zero out child times.
95 	 *	    count self-recursive calls.
96 	 *	    indicate that nothing is on cycles.
97 	 */
98     for ( parentp = nl ; parentp < npe ; parentp++ ) {
99 	parentp -> childtime = 0.0;
100 	arcp = arclookup( parentp , parentp );
101 	if ( arcp != 0 ) {
102 	    parentp -> ncall -= arcp -> arc_count;
103 	    parentp -> selfcalls = arcp -> arc_count;
104 	} else {
105 	    parentp -> selfcalls = 0;
106 	}
107 	parentp -> npropcall = parentp -> ncall;
108 	parentp -> propfraction = 0.0;
109 	parentp -> propself = 0.0;
110 	parentp -> propchild = 0.0;
111 	parentp -> printflag = FALSE;
112 	parentp -> toporder = DFN_NAN;
113 	parentp -> cycleno = 0;
114 	parentp -> cyclehead = parentp;
115 	parentp -> cnext = 0;
116 	if ( cflag ) {
117 	    findcall( parentp , parentp -> value , (parentp+1) -> value );
118 	}
119     }
120     for ( pass = 1 ; ; pass++ ) {
121 	    /*
122 	     *	topologically order things
123 	     *	if any node is unnumbered,
124 	     *	    number it and any of its descendents.
125 	     */
126 	for ( dfn_init() , parentp = nl ; parentp < npe ; parentp++ ) {
127 	    if ( parentp -> toporder == DFN_NAN ) {
128 		dfn( parentp );
129 	    }
130 	}
131 	    /*
132 	     *	link together nodes on the same cycle
133 	     */
134 	cyclelink();
135 	    /*
136 	     *	if no cycles to break up, proceed
137 	     */
138 	if ( ! Cflag )
139 	    break;
140 	    /*
141 	     *	analyze cycles to determine breakup
142 	     */
143 #	ifdef DEBUG
144 	    if ( debug & BREAKCYCLE ) {
145 		printf("[doarcs] pass %d, cycle(s) %d\n" , pass , ncycle );
146 	    }
147 #	endif DEBUG
148 	if ( pass == 1 ) {
149 	    printf( "\n\n%s %s\n%s %d:\n" ,
150 		"The following arcs were deleted" ,
151 		"from the propagation calculation" ,
152 		"to reduce the maximum cycle size to", cyclethreshold );
153 	}
154 	if ( cycleanalyze() )
155 	    break;
156 	free ( cyclenl );
157 	ncycle = 0;
158 	for ( parentp = nl ; parentp < npe ; parentp++ ) {
159 	    parentp -> toporder = DFN_NAN;
160 	    parentp -> cycleno = 0;
161 	    parentp -> cyclehead = parentp;
162 	    parentp -> cnext = 0;
163 	}
164     }
165     if ( pass > 1 ) {
166 	printf( "\f\n" );
167     } else {
168 	printf( "\tNone\n\n" );
169     }
170 	/*
171 	 *	Sort the symbol table in reverse topological order
172 	 */
173     topsortnlp = (nltype **) calloc( nname , sizeof(nltype *) );
174     if ( topsortnlp == (nltype **) 0 ) {
175 	fprintf( stderr , "[doarcs] ran out of memory for topo sorting\n" );
176     }
177     for ( index = 0 ; index < nname ; index += 1 ) {
178 	topsortnlp[ index ] = &nl[ index ];
179     }
180     qsort( topsortnlp , nname , sizeof(nltype *) , topcmp );
181 #   ifdef DEBUG
182 	if ( debug & DFNDEBUG ) {
183 	    printf( "[doarcs] topological sort listing\n" );
184 	    for ( index = 0 ; index < nname ; index += 1 ) {
185 		printf( "[doarcs] " );
186 		printf( "%d:" , topsortnlp[ index ] -> toporder );
187 		printname( topsortnlp[ index ] );
188 		printf( "\n" );
189 	    }
190 	}
191 #   endif DEBUG
192 	/*
193 	 *	starting from the topological top,
194 	 *	propagate print flags to children.
195 	 *	also, calculate propagation fractions.
196 	 *	this happens before time propagation
197 	 *	since time propagation uses the fractions.
198 	 */
199     doflags();
200 	/*
201 	 *	starting from the topological bottom,
202 	 *	propogate children times up to parents.
203 	 */
204     dotime();
205 	/*
206 	 *	Now, sort by propself + propchild.
207 	 *	sorting both the regular function names
208 	 *	and cycle headers.
209 	 */
210     timesortnlp = (nltype **) calloc( nname + ncycle , sizeof(nltype *) );
211     if ( timesortnlp == (nltype **) 0 ) {
212 	fprintf( stderr , "%s: ran out of memory for sorting\n" , whoami );
213     }
214     for ( index = 0 ; index < nname ; index++ ) {
215 	timesortnlp[index] = &nl[index];
216     }
217     for ( index = 1 ; index <= ncycle ; index++ ) {
218 	timesortnlp[nname+index-1] = &cyclenl[index];
219     }
220     qsort( timesortnlp , nname + ncycle , sizeof(nltype *) , totalcmp );
221     for ( index = 0 ; index < nname + ncycle ; index++ ) {
222 	timesortnlp[ index ] -> index = index + 1;
223     }
224     return( timesortnlp );
225 }
226 
dotime()227 dotime()
228 {
229     int	index;
230 
231     cycletime();
232     for ( index = 0 ; index < nname ; index += 1 ) {
233 	timepropagate( topsortnlp[ index ] );
234     }
235 }
236 
timepropagate(parentp)237 timepropagate( parentp )
238     nltype	*parentp;
239 {
240     arctype	*arcp;
241     nltype	*childp;
242     double	share;
243     double	propshare;
244 
245     if ( parentp -> propfraction == 0.0 ) {
246 	return;
247     }
248 	/*
249 	 *	gather time from children of this parent.
250 	 */
251     for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
252 	childp = arcp -> arc_childp;
253 	if ( arcp -> arc_flags & DEADARC ) {
254 	    continue;
255 	}
256 	if ( arcp -> arc_count == 0 ) {
257 	    continue;
258 	}
259 	if ( childp == parentp ) {
260 	    continue;
261 	}
262 	if ( childp -> propfraction == 0.0 ) {
263 	    continue;
264 	}
265 	if ( childp -> cyclehead != childp ) {
266 	    if ( parentp -> cycleno == childp -> cycleno ) {
267 		continue;
268 	    }
269 	    if ( parentp -> toporder <= childp -> toporder ) {
270 		fprintf( stderr , "[propagate] toporder botches\n" );
271 	    }
272 	    childp = childp -> cyclehead;
273 	} else {
274 	    if ( parentp -> toporder <= childp -> toporder ) {
275 		fprintf( stderr , "[propagate] toporder botches\n" );
276 		continue;
277 	    }
278 	}
279 	if ( childp -> npropcall == 0 ) {
280 	    continue;
281 	}
282 	    /*
283 	     *	distribute time for this arc
284 	     */
285 	arcp -> arc_time = childp -> time
286 			        * ( ( (double) arcp -> arc_count ) /
287 				    ( (double) childp -> npropcall ) );
288 	arcp -> arc_childtime = childp -> childtime
289 			        * ( ( (double) arcp -> arc_count ) /
290 				    ( (double) childp -> npropcall ) );
291 	share = arcp -> arc_time + arcp -> arc_childtime;
292 	parentp -> childtime += share;
293 	    /*
294 	     *	( 1 - propfraction ) gets lost along the way
295 	     */
296 	propshare = parentp -> propfraction * share;
297 	    /*
298 	     *	fix things for printing
299 	     */
300 	parentp -> propchild += propshare;
301 	arcp -> arc_time *= parentp -> propfraction;
302 	arcp -> arc_childtime *= parentp -> propfraction;
303 	    /*
304 	     *	add this share to the parent's cycle header, if any.
305 	     */
306 	if ( parentp -> cyclehead != parentp ) {
307 	    parentp -> cyclehead -> childtime += share;
308 	    parentp -> cyclehead -> propchild += propshare;
309 	}
310 #	ifdef DEBUG
311 	    if ( debug & PROPDEBUG ) {
312 		printf( "[dotime] child \t" );
313 		printname( childp );
314 		printf( " with %f %f %d/%d\n" ,
315 			childp -> time , childp -> childtime ,
316 			arcp -> arc_count , childp -> npropcall );
317 		printf( "[dotime] parent\t" );
318 		printname( parentp );
319 		printf( "\n[dotime] share %f\n" , share );
320 	    }
321 #	endif DEBUG
322     }
323 }
324 
cyclelink()325 cyclelink()
326 {
327     register nltype	*nlp;
328     register nltype	*cyclenlp;
329     int			cycle;
330     nltype		*memberp;
331     arctype		*arcp;
332 
333 	/*
334 	 *	Count the number of cycles, and initialze the cycle lists
335 	 */
336     ncycle = 0;
337     for ( nlp = nl ; nlp < npe ; nlp++ ) {
338 	    /*
339 	     *	this is how you find unattached cycles
340 	     */
341 	if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) {
342 	    ncycle += 1;
343 	}
344     }
345 	/*
346 	 *	cyclenl is indexed by cycle number:
347 	 *	i.e. it is origin 1, not origin 0.
348 	 */
349     cyclenl = (nltype *) calloc( ncycle + 1 , sizeof( nltype ) );
350     if ( cyclenl == 0 ) {
351 	fprintf( stderr , "%s: No room for %d bytes of cycle headers\n" ,
352 		whoami , ( ncycle + 1 ) * sizeof( nltype ) );
353 	done();
354     }
355 	/*
356 	 *	now link cycles to true cycleheads,
357 	 *	number them, accumulate the data for the cycle
358 	 */
359     cycle = 0;
360     for ( nlp = nl ; nlp < npe ; nlp++ ) {
361 	if ( !( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) ) {
362 	    continue;
363 	}
364 	cycle += 1;
365 	cyclenlp = &cyclenl[cycle];
366         cyclenlp -> name = 0;		/* the name */
367         cyclenlp -> value = 0;		/* the pc entry point */
368         cyclenlp -> time = 0.0;		/* ticks in this routine */
369         cyclenlp -> childtime = 0.0;	/* cumulative ticks in children */
370 	cyclenlp -> ncall = 0;		/* how many times called */
371 	cyclenlp -> selfcalls = 0;	/* how many calls to self */
372 	cyclenlp -> propfraction = 0.0;	/* what % of time propagates */
373 	cyclenlp -> propself = 0.0;	/* how much self time propagates */
374 	cyclenlp -> propchild = 0.0;	/* how much child time propagates */
375 	cyclenlp -> printflag = TRUE;	/* should this be printed? */
376 	cyclenlp -> index = 0;		/* index in the graph list */
377 	cyclenlp -> toporder = DFN_NAN;	/* graph call chain top-sort order */
378 	cyclenlp -> cycleno = cycle;	/* internal number of cycle on */
379 	cyclenlp -> cyclehead = cyclenlp;	/* pointer to head of cycle */
380 	cyclenlp -> cnext = nlp;	/* pointer to next member of cycle */
381 	cyclenlp -> parents = 0;	/* list of caller arcs */
382 	cyclenlp -> children = 0;	/* list of callee arcs */
383 #	ifdef DEBUG
384 	    if ( debug & CYCLEDEBUG ) {
385 		printf( "[cyclelink] " );
386 		printname( nlp );
387 		printf( " is the head of cycle %d\n" , cycle );
388 	    }
389 #	endif DEBUG
390 	    /*
391 	     *	link members to cycle header
392 	     */
393 	for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) {
394 	    memberp -> cycleno = cycle;
395 	    memberp -> cyclehead = cyclenlp;
396 	}
397 	    /*
398 	     *	count calls from outside the cycle
399 	     *	and those among cycle members
400 	     */
401 	for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) {
402 	    for ( arcp=memberp->parents ; arcp ; arcp=arcp->arc_parentlist ) {
403 		if ( arcp -> arc_parentp == memberp ) {
404 		    continue;
405 		}
406 		if ( arcp -> arc_parentp -> cycleno == cycle ) {
407 		    cyclenlp -> selfcalls += arcp -> arc_count;
408 		} else {
409 		    cyclenlp -> npropcall += arcp -> arc_count;
410 		}
411 	    }
412 	}
413     }
414 }
415 
416     /*
417      *	analyze cycles to determine breakup
418      */
cycleanalyze()419 cycleanalyze()
420 {
421     arctype	**cyclestack;
422     arctype	**stkp;
423     arctype	**arcpp;
424     arctype	**endlist;
425     arctype	*arcp;
426     nltype	*nlp;
427     cltype	*clp;
428     bool	ret;
429     bool	done;
430     int		size;
431     int		cycleno;
432 
433 	/*
434 	 *	calculate the size of the cycle, and find nodes that
435 	 *	exit the cycle as they are desirable targets to cut
436 	 *	some of their parents
437 	 */
438     for ( done = TRUE , cycleno = 1 ; cycleno <= ncycle ; cycleno++ ) {
439 	size = 0;
440 	for (nlp = cyclenl[ cycleno ] . cnext; nlp; nlp = nlp -> cnext) {
441 	    size += 1;
442 	    nlp -> parentcnt = 0;
443 	    nlp -> flags &= ~HASCYCLEXIT;
444 	    for ( arcp = nlp -> parents; arcp; arcp = arcp -> arc_parentlist ) {
445 		nlp -> parentcnt += 1;
446 		if ( arcp -> arc_parentp -> cycleno != cycleno )
447 		    nlp -> flags |= HASCYCLEXIT;
448 	    }
449 	}
450 	if ( size <= cyclethreshold )
451 	    continue;
452 	done = FALSE;
453         cyclestack = (arctype **) calloc( size + 1 , sizeof( arctype *) );
454 	if ( cyclestack == 0 ) {
455 	    fprintf( stderr , "%s: No room for %d bytes of cycle stack\n" ,
456 		whoami , ( size + 1 ) * sizeof( arctype * ) );
457 	    return;
458 	}
459 #	ifdef DEBUG
460 	    if ( debug & BREAKCYCLE ) {
461 		printf( "[cycleanalyze] starting cycle %d of %d, size %d\n" ,
462 		    cycleno , ncycle , size );
463 	    }
464 #	endif DEBUG
465 	for ( nlp = cyclenl[ cycleno ] . cnext ; nlp ; nlp = nlp -> cnext ) {
466 	    stkp = &cyclestack[0];
467 	    nlp -> flags |= CYCLEHEAD;
468 	    ret = descend ( nlp , cyclestack , stkp );
469 	    nlp -> flags &= ~CYCLEHEAD;
470 	    if ( ret == FALSE )
471 		break;
472 	}
473 	free( cyclestack );
474 	if ( cyclecnt > 0 ) {
475 	    compresslist();
476 	    for ( clp = cyclehead ; clp ; ) {
477 		endlist = &clp -> list[ clp -> size ];
478 		for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
479 		    (*arcpp) -> arc_cyclecnt--;
480 		cyclecnt--;
481 		clp = clp -> next;
482 		free( clp );
483 	    }
484 	    cyclehead = 0;
485 	}
486     }
487 #   ifdef DEBUG
488 	if ( debug & BREAKCYCLE ) {
489 	    printf("%s visited %d, viable %d, newcycle %d, oldcycle %d\n",
490 		"[doarcs]" , visited , viable , newcycle , oldcycle);
491 	}
492 #   endif DEBUG
493     return( done );
494 }
495 
descend(node,stkstart,stkp)496 descend( node , stkstart , stkp )
497     nltype	*node;
498     arctype	**stkstart;
499     arctype	**stkp;
500 {
501     arctype	*arcp;
502     bool	ret;
503 
504     for ( arcp = node -> children ; arcp ; arcp = arcp -> arc_childlist ) {
505 #	ifdef DEBUG
506 	    visited++;
507 #	endif DEBUG
508 	if ( arcp -> arc_childp -> cycleno != node -> cycleno
509 	    || ( arcp -> arc_childp -> flags & VISITED )
510 	    || ( arcp -> arc_flags & DEADARC ) )
511 	    continue;
512 #	ifdef DEBUG
513 	    viable++;
514 #	endif DEBUG
515 	*stkp = arcp;
516 	if ( arcp -> arc_childp -> flags & CYCLEHEAD ) {
517 	    if ( addcycle( stkstart , stkp ) == FALSE )
518 		return( FALSE );
519 	    continue;
520 	}
521 	arcp -> arc_childp -> flags |= VISITED;
522 	ret = descend( arcp -> arc_childp , stkstart , stkp + 1 );
523 	arcp -> arc_childp -> flags &= ~VISITED;
524 	if ( ret == FALSE )
525 	    return( FALSE );
526     }
527 }
528 
addcycle(stkstart,stkend)529 addcycle( stkstart , stkend )
530     arctype	**stkstart;
531     arctype	**stkend;
532 {
533     arctype	**arcpp;
534     arctype	**stkloc;
535     arctype	**stkp;
536     arctype	**endlist;
537     arctype	*minarc;
538     arctype	*arcp;
539     cltype	*clp;
540     int		size;
541 
542     size = stkend - stkstart + 1;
543     if ( size <= 1 )
544 	return( TRUE );
545     for ( arcpp = stkstart , minarc = *arcpp ; arcpp <= stkend ; arcpp++ ) {
546 	if ( *arcpp > minarc )
547 	    continue;
548 	minarc = *arcpp;
549 	stkloc = arcpp;
550     }
551     for ( clp = cyclehead ; clp ; clp = clp -> next ) {
552 	if ( clp -> size != size )
553 	    continue;
554 	stkp = stkloc;
555 	endlist = &clp -> list[ size ];
556 	for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) {
557 	    if ( *stkp++ != *arcpp )
558 		break;
559 	    if ( stkp > stkend )
560 		stkp = stkstart;
561 	}
562 	if ( arcpp == endlist ) {
563 #	    ifdef DEBUG
564 		oldcycle++;
565 #	    endif DEBUG
566 	    return( TRUE );
567 	}
568     }
569     clp = (cltype *)
570 	calloc( 1 , sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) );
571     if ( clp == 0 ) {
572 	fprintf( stderr , "%s: No room for %d bytes of subcycle storage\n" ,
573 	    whoami , sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) );
574 	return( FALSE );
575     }
576     stkp = stkloc;
577     endlist = &clp -> list[ size ];
578     for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) {
579 	arcp = *arcpp = *stkp++;
580 	if ( stkp > stkend )
581 	    stkp = stkstart;
582 	arcp -> arc_cyclecnt++;
583 	if ( ( arcp -> arc_flags & ONLIST ) == 0 ) {
584 	    arcp -> arc_flags |= ONLIST;
585 	    arcp -> arc_next = archead;
586 	    archead = arcp;
587 	}
588     }
589     clp -> size = size;
590     clp -> next = cyclehead;
591     cyclehead = clp;
592 #   ifdef DEBUG
593 	newcycle++;
594 	if ( debug & SUBCYCLELIST ) {
595 	    printsubcycle( clp );
596 	}
597 #   endif DEBUG
598     cyclecnt++;
599     if ( cyclecnt >= CYCLEMAX )
600 	return( FALSE );
601     return( TRUE );
602 }
603 
compresslist()604 compresslist()
605 {
606     cltype	*clp;
607     cltype	**prev;
608     arctype	**arcpp;
609     arctype	**endlist;
610     arctype	*arcp;
611     arctype	*maxarcp;
612     arctype	*maxexitarcp;
613     arctype	*maxwithparentarcp;
614     arctype	*maxnoparentarcp;
615     int		maxexitcnt;
616     int		maxwithparentcnt;
617     int		maxnoparentcnt;
618     char	*type;
619 
620     maxexitcnt = 0;
621     maxwithparentcnt = 0;
622     maxnoparentcnt = 0;
623     for ( endlist = &archead , arcp = archead ; arcp ; ) {
624 	if ( arcp -> arc_cyclecnt == 0 ) {
625 	    arcp -> arc_flags &= ~ONLIST;
626 	    *endlist = arcp -> arc_next;
627 	    arcp -> arc_next = 0;
628 	    arcp = *endlist;
629 	    continue;
630 	}
631 	if ( arcp -> arc_childp -> flags & HASCYCLEXIT ) {
632 	    if ( arcp -> arc_cyclecnt > maxexitcnt ||
633 		( arcp -> arc_cyclecnt == maxexitcnt &&
634 		arcp -> arc_cyclecnt < maxexitarcp -> arc_count ) ) {
635 		maxexitcnt = arcp -> arc_cyclecnt;
636 		maxexitarcp = arcp;
637 	    }
638 	} else if ( arcp -> arc_childp -> parentcnt > 1 ) {
639 	    if ( arcp -> arc_cyclecnt > maxwithparentcnt ||
640 		( arcp -> arc_cyclecnt == maxwithparentcnt &&
641 		arcp -> arc_cyclecnt < maxwithparentarcp -> arc_count ) ) {
642 		maxwithparentcnt = arcp -> arc_cyclecnt;
643 		maxwithparentarcp = arcp;
644 	    }
645 	} else {
646 	    if ( arcp -> arc_cyclecnt > maxnoparentcnt ||
647 		( arcp -> arc_cyclecnt == maxnoparentcnt &&
648 		arcp -> arc_cyclecnt < maxnoparentarcp -> arc_count ) ) {
649 		maxnoparentcnt = arcp -> arc_cyclecnt;
650 		maxnoparentarcp = arcp;
651 	    }
652 	}
653 	endlist = &arcp -> arc_next;
654 	arcp = arcp -> arc_next;
655     }
656     if ( maxexitcnt > 0 ) {
657 	/*
658 	 *	first choice is edge leading to node with out-of-cycle parent
659 	 */
660 	maxarcp = maxexitarcp;
661 #	ifdef DEBUG
662 	    type = "exit";
663 #	endif DEBUG
664     } else if ( maxwithparentcnt > 0 ) {
665 	/*
666 	 *	second choice is edge leading to node with at least one
667 	 *	other in-cycle parent
668 	 */
669 	maxarcp = maxwithparentarcp;
670 #	ifdef DEBUG
671 	    type = "internal";
672 #	endif DEBUG
673     } else {
674 	/*
675 	 *	last choice is edge leading to node with only this arc as
676 	 *	a parent (as it will now be orphaned)
677 	 */
678 	maxarcp = maxnoparentarcp;
679 #	ifdef DEBUG
680 	    type = "orphan";
681 #	endif DEBUG
682     }
683     maxarcp -> arc_flags |= DEADARC;
684     maxarcp -> arc_childp -> parentcnt -= 1;
685     maxarcp -> arc_childp -> npropcall -= maxarcp -> arc_count;
686 #   ifdef DEBUG
687 	if ( debug & BREAKCYCLE ) {
688 	    printf( "%s delete %s arc: %s (%d) -> %s from %d cycle(s)\n" ,
689 		"[compresslist]" , type , maxarcp -> arc_parentp -> name ,
690 		maxarcp -> arc_count , maxarcp -> arc_childp -> name ,
691 		maxarcp -> arc_cyclecnt );
692 	}
693 #   endif DEBUG
694     printf( "\t%s to %s with %d calls\n" , maxarcp -> arc_parentp -> name ,
695 	maxarcp -> arc_childp -> name , maxarcp -> arc_count );
696     prev = &cyclehead;
697     for ( clp = cyclehead ; clp ; ) {
698 	endlist = &clp -> list[ clp -> size ];
699 	for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
700 	    if ( (*arcpp) -> arc_flags & DEADARC )
701 		break;
702 	if ( arcpp == endlist ) {
703 	    prev = &clp -> next;
704 	    clp = clp -> next;
705 	    continue;
706 	}
707 	for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
708 	    (*arcpp) -> arc_cyclecnt--;
709 	cyclecnt--;
710 	*prev = clp -> next;
711 	clp = clp -> next;
712 	free( clp );
713     }
714 }
715 
716 #ifdef DEBUG
printsubcycle(clp)717 printsubcycle( clp )
718     cltype	*clp;
719 {
720     arctype	**arcpp;
721     arctype	**endlist;
722 
723     arcpp = clp -> list;
724     printf( "%s <cycle %d>\n" , (*arcpp) -> arc_parentp -> name ,
725 	(*arcpp) -> arc_parentp -> cycleno ) ;
726     for ( endlist = &clp -> list[ clp -> size ]; arcpp < endlist ; arcpp++ )
727 	printf( "\t(%d) -> %s\n" , (*arcpp) -> arc_count ,
728 	    (*arcpp) -> arc_childp -> name ) ;
729 }
730 #endif DEBUG
731 
cycletime()732 cycletime()
733 {
734     int			cycle;
735     nltype		*cyclenlp;
736     nltype		*childp;
737 
738     for ( cycle = 1 ; cycle <= ncycle ; cycle += 1 ) {
739 	cyclenlp = &cyclenl[ cycle ];
740 	for ( childp = cyclenlp -> cnext ; childp ; childp = childp -> cnext ) {
741 	    if ( childp -> propfraction == 0.0 ) {
742 		    /*
743 		     * all members have the same propfraction except those
744 		     *	that were excluded with -E
745 		     */
746 		continue;
747 	    }
748 	    cyclenlp -> time += childp -> time;
749 	}
750 	cyclenlp -> propself = cyclenlp -> propfraction * cyclenlp -> time;
751     }
752 }
753 
754     /*
755      *	in one top to bottom pass over the topologically sorted namelist
756      *	propagate:
757      *		printflag as the union of parents' printflags
758      *		propfraction as the sum of fractional parents' propfractions
759      *	and while we're here, sum time for functions.
760      */
doflags()761 doflags()
762 {
763     int		index;
764     nltype	*childp;
765     nltype	*oldhead;
766 
767     oldhead = 0;
768     for ( index = nname-1 ; index >= 0 ; index -= 1 ) {
769 	childp = topsortnlp[ index ];
770 	    /*
771 	     *	if we haven't done this function or cycle,
772 	     *	inherit things from parent.
773 	     *	this way, we are linear in the number of arcs
774 	     *	since we do all members of a cycle (and the cycle itself)
775 	     *	as we hit the first member of the cycle.
776 	     */
777 	if ( childp -> cyclehead != oldhead ) {
778 	    oldhead = childp -> cyclehead;
779 	    inheritflags( childp );
780 	}
781 #	ifdef DEBUG
782 	    if ( debug & PROPDEBUG ) {
783 		printf( "[doflags] " );
784 		printname( childp );
785 		printf( " inherits printflag %d and propfraction %f\n" ,
786 			childp -> printflag , childp -> propfraction );
787 	    }
788 #	endif DEBUG
789 	if ( ! childp -> printflag ) {
790 		/*
791 		 *	printflag is off
792 		 *	it gets turned on by
793 		 *	being on -f list,
794 		 *	or there not being any -f list and not being on -e list.
795 		 */
796 	    if (   onlist( flist , childp -> name )
797 		|| ( !fflag && !onlist( elist , childp -> name ) ) ) {
798 		childp -> printflag = TRUE;
799 	    }
800 	} else {
801 		/*
802 		 *	this function has printing parents:
803 		 *	maybe someone wants to shut it up
804 		 *	by putting it on -e list.  (but favor -f over -e)
805 		 */
806 	    if (  ( !onlist( flist , childp -> name ) )
807 		&& onlist( elist , childp -> name ) ) {
808 		childp -> printflag = FALSE;
809 	    }
810 	}
811 	if ( childp -> propfraction == 0.0 ) {
812 		/*
813 		 *	no parents to pass time to.
814 		 *	collect time from children if
815 		 *	its on -F list,
816 		 *	or there isn't any -F list and its not on -E list.
817 		 */
818 	    if ( onlist( Flist , childp -> name )
819 		|| ( !Fflag && !onlist( Elist , childp -> name ) ) ) {
820 		    childp -> propfraction = 1.0;
821 	    }
822 	} else {
823 		/*
824 		 *	it has parents to pass time to,
825 		 *	but maybe someone wants to shut it up
826 		 *	by puttting it on -E list.  (but favor -F over -E)
827 		 */
828 	    if (  !onlist( Flist , childp -> name )
829 		&& onlist( Elist , childp -> name ) ) {
830 		childp -> propfraction = 0.0;
831 	    }
832 	}
833 	childp -> propself = childp -> time * childp -> propfraction;
834 	printtime += childp -> propself;
835 #	ifdef DEBUG
836 	    if ( debug & PROPDEBUG ) {
837 		printf( "[doflags] " );
838 		printname( childp );
839 		printf( " ends up with printflag %d and propfraction %f\n" ,
840 			childp -> printflag , childp -> propfraction );
841 		printf( "time %f propself %f printtime %f\n" ,
842 			childp -> time , childp -> propself , printtime );
843 	    }
844 #	endif DEBUG
845     }
846 }
847 
848     /*
849      *	check if any parent of this child
850      *	(or outside parents of this cycle)
851      *	have their print flags on and set the
852      *	print flag of the child (cycle) appropriately.
853      *	similarly, deal with propagation fractions from parents.
854      */
inheritflags(childp)855 inheritflags( childp )
856     nltype	*childp;
857 {
858     nltype	*headp;
859     arctype	*arcp;
860     nltype	*parentp;
861     nltype	*memp;
862 
863     headp = childp -> cyclehead;
864     if ( childp == headp ) {
865 	    /*
866 	     *	just a regular child, check its parents
867 	     */
868 	childp -> printflag = FALSE;
869 	childp -> propfraction = 0.0;
870 	for (arcp = childp -> parents ; arcp ; arcp = arcp -> arc_parentlist) {
871 	    parentp = arcp -> arc_parentp;
872 	    if ( childp == parentp ) {
873 		continue;
874 	    }
875 	    childp -> printflag |= parentp -> printflag;
876 		/*
877 		 *	if the child was never actually called
878 		 *	(e.g. this arc is static (and all others are, too))
879 		 *	no time propagates along this arc.
880 		 */
881 	    if ( arcp -> arc_flags & DEADARC ) {
882 		continue;
883 	    }
884 	    if ( childp -> npropcall ) {
885 		childp -> propfraction += parentp -> propfraction
886 					* ( ( (double) arcp -> arc_count )
887 					  / ( (double) childp -> npropcall ) );
888 	    }
889 	}
890     } else {
891 	    /*
892 	     *	its a member of a cycle, look at all parents from
893 	     *	outside the cycle
894 	     */
895 	headp -> printflag = FALSE;
896 	headp -> propfraction = 0.0;
897 	for ( memp = headp -> cnext ; memp ; memp = memp -> cnext ) {
898 	    for (arcp = memp->parents ; arcp ; arcp = arcp->arc_parentlist) {
899 		if ( arcp -> arc_parentp -> cyclehead == headp ) {
900 		    continue;
901 		}
902 		parentp = arcp -> arc_parentp;
903 		headp -> printflag |= parentp -> printflag;
904 		    /*
905 		     *	if the cycle was never actually called
906 		     *	(e.g. this arc is static (and all others are, too))
907 		     *	no time propagates along this arc.
908 		     */
909 		if ( arcp -> arc_flags & DEADARC ) {
910 		    continue;
911 		}
912 		if ( headp -> npropcall ) {
913 		    headp -> propfraction += parentp -> propfraction
914 					* ( ( (double) arcp -> arc_count )
915 					  / ( (double) headp -> npropcall ) );
916 		}
917 	    }
918 	}
919 	for ( memp = headp ; memp ; memp = memp -> cnext ) {
920 	    memp -> printflag = headp -> printflag;
921 	    memp -> propfraction = headp -> propfraction;
922 	}
923     }
924 }
925