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