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