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