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: stable/10/usr.bin/gprof/arcs.c 246783 2013-02-14 08:16:03Z charnier $");
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 int topcmp(const void *, const void *);
50
51 /*
52 * add (or just increment) an arc
53 */
54 void
addarc(nltype * parentp,nltype * childp,long count)55 addarc(nltype *parentp, nltype *childp, long count)
56 {
57 arctype *arcp;
58
59 # ifdef DEBUG
60 if ( debug & TALLYDEBUG ) {
61 printf( "[addarc] %ld arcs from %s to %s\n" ,
62 count , parentp -> name , childp -> name );
63 }
64 # endif /* DEBUG */
65 arcp = arclookup( parentp , childp );
66 if ( arcp != 0 ) {
67 /*
68 * a hit: just increment the count.
69 */
70 # ifdef DEBUG
71 if ( debug & TALLYDEBUG ) {
72 printf( "[tally] hit %ld += %ld\n" ,
73 arcp -> arc_count , count );
74 }
75 # endif /* DEBUG */
76 arcp -> arc_count += count;
77 return;
78 }
79 arcp = (arctype *)calloc( 1 , sizeof *arcp );
80 if (arcp == NULL)
81 errx( 1 , "malloc failed" );
82 arcp -> arc_parentp = parentp;
83 arcp -> arc_childp = childp;
84 arcp -> arc_count = count;
85 /*
86 * prepend this child to the children of this parent
87 */
88 arcp -> arc_childlist = parentp -> children;
89 parentp -> children = arcp;
90 /*
91 * prepend this parent to the parents of this child
92 */
93 arcp -> arc_parentlist = childp -> parents;
94 childp -> parents = arcp;
95 }
96
97 /*
98 * the code below topologically sorts the graph (collapsing cycles),
99 * and propagates time bottom up and flags top down.
100 */
101
102 /*
103 * the topologically sorted name list pointers
104 */
105 nltype **topsortnlp;
106
107 int
topcmp(const void * v1,const void * v2)108 topcmp(const void *v1, const void *v2)
109 {
110 const nltype **npp1 = (const nltype **)v1;
111 const nltype **npp2 = (const nltype **)v2;
112
113 return (*npp1) -> toporder - (*npp2) -> toporder;
114 }
115
116 nltype **
doarcs(void)117 doarcs(void)
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
dotime(void)255 dotime(void)
256 {
257 int index;
258
259 cycletime();
260 for ( index = 0 ; index < nname ; index += 1 ) {
261 timepropagate( topsortnlp[ index ] );
262 }
263 }
264
265 void
timepropagate(nltype * parentp)266 timepropagate(nltype *parentp)
267 {
268 arctype *arcp;
269 nltype *childp;
270 double share;
271 double propshare;
272
273 if ( parentp -> propfraction == 0.0 ) {
274 return;
275 }
276 /*
277 * gather time from children of this parent.
278 */
279 for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
280 childp = arcp -> arc_childp;
281 if ( arcp -> arc_flags & DEADARC ) {
282 continue;
283 }
284 if ( arcp -> arc_count == 0 ) {
285 continue;
286 }
287 if ( childp == parentp ) {
288 continue;
289 }
290 if ( childp -> propfraction == 0.0 ) {
291 continue;
292 }
293 if ( childp -> cyclehead != childp ) {
294 if ( parentp -> cycleno == childp -> cycleno ) {
295 continue;
296 }
297 if ( parentp -> toporder <= childp -> toporder ) {
298 fprintf( stderr , "[propagate] toporder botches\n" );
299 }
300 childp = childp -> cyclehead;
301 } else {
302 if ( parentp -> toporder <= childp -> toporder ) {
303 fprintf( stderr , "[propagate] toporder botches\n" );
304 continue;
305 }
306 }
307 if ( childp -> npropcall == 0 ) {
308 continue;
309 }
310 /*
311 * distribute time for this arc
312 */
313 arcp -> arc_time = childp -> time
314 * ( ( (double) arcp -> arc_count ) /
315 ( (double) childp -> npropcall ) );
316 arcp -> arc_childtime = childp -> childtime
317 * ( ( (double) arcp -> arc_count ) /
318 ( (double) childp -> npropcall ) );
319 share = arcp -> arc_time + arcp -> arc_childtime;
320 parentp -> childtime += share;
321 /*
322 * ( 1 - propfraction ) gets lost along the way
323 */
324 propshare = parentp -> propfraction * share;
325 /*
326 * fix things for printing
327 */
328 parentp -> propchild += propshare;
329 arcp -> arc_time *= parentp -> propfraction;
330 arcp -> arc_childtime *= parentp -> propfraction;
331 /*
332 * add this share to the parent's cycle header, if any.
333 */
334 if ( parentp -> cyclehead != parentp ) {
335 parentp -> cyclehead -> childtime += share;
336 parentp -> cyclehead -> propchild += propshare;
337 }
338 # ifdef DEBUG
339 if ( debug & PROPDEBUG ) {
340 printf( "[dotime] child \t" );
341 printname( childp );
342 printf( " with %f %f %ld/%ld\n" ,
343 childp -> time , childp -> childtime ,
344 arcp -> arc_count , childp -> npropcall );
345 printf( "[dotime] parent\t" );
346 printname( parentp );
347 printf( "\n[dotime] share %f\n" , share );
348 }
349 # endif /* DEBUG */
350 }
351 }
352
353 void
cyclelink(void)354 cyclelink(void)
355 {
356 register nltype *nlp;
357 register nltype *cyclenlp;
358 int cycle;
359 nltype *memberp;
360 arctype *arcp;
361
362 /*
363 * Count the number of cycles, and initialize the cycle lists
364 */
365 ncycle = 0;
366 for ( nlp = nl ; nlp < npe ; nlp++ ) {
367 /*
368 * this is how you find unattached cycles
369 */
370 if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) {
371 ncycle += 1;
372 }
373 }
374 /*
375 * cyclenl is indexed by cycle number:
376 * i.e. it is origin 1, not origin 0.
377 */
378 cyclenl = (nltype *) calloc( ncycle + 1 , sizeof( nltype ) );
379 if ( cyclenl == 0 )
380 errx( 1 , "no room for %zu bytes of cycle headers" ,
381 ( ncycle + 1 ) * sizeof( nltype ) );
382 /*
383 * now link cycles to true cycleheads,
384 * number them, accumulate the data for the cycle
385 */
386 cycle = 0;
387 for ( nlp = nl ; nlp < npe ; nlp++ ) {
388 if ( !( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) ) {
389 continue;
390 }
391 cycle += 1;
392 cyclenlp = &cyclenl[cycle];
393 cyclenlp -> name = 0; /* the name */
394 cyclenlp -> value = 0; /* the pc entry point */
395 cyclenlp -> time = 0.0; /* ticks in this routine */
396 cyclenlp -> childtime = 0.0; /* cumulative ticks in children */
397 cyclenlp -> ncall = 0; /* how many times called */
398 cyclenlp -> selfcalls = 0; /* how many calls to self */
399 cyclenlp -> propfraction = 0.0; /* what % of time propagates */
400 cyclenlp -> propself = 0.0; /* how much self time propagates */
401 cyclenlp -> propchild = 0.0; /* how much child time propagates */
402 cyclenlp -> printflag = TRUE; /* should this be printed? */
403 cyclenlp -> index = 0; /* index in the graph list */
404 cyclenlp -> toporder = DFN_NAN; /* graph call chain top-sort order */
405 cyclenlp -> cycleno = cycle; /* internal number of cycle on */
406 cyclenlp -> cyclehead = cyclenlp; /* pointer to head of cycle */
407 cyclenlp -> cnext = nlp; /* pointer to next member of cycle */
408 cyclenlp -> parents = 0; /* list of caller arcs */
409 cyclenlp -> children = 0; /* list of callee arcs */
410 # ifdef DEBUG
411 if ( debug & CYCLEDEBUG ) {
412 printf( "[cyclelink] " );
413 printname( nlp );
414 printf( " is the head of cycle %d\n" , cycle );
415 }
416 # endif /* DEBUG */
417 /*
418 * link members to cycle header
419 */
420 for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) {
421 memberp -> cycleno = cycle;
422 memberp -> cyclehead = cyclenlp;
423 }
424 /*
425 * count calls from outside the cycle
426 * and those among cycle members
427 */
428 for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) {
429 for ( arcp=memberp->parents ; arcp ; arcp=arcp->arc_parentlist ) {
430 if ( arcp -> arc_parentp == memberp ) {
431 continue;
432 }
433 if ( arcp -> arc_parentp -> cycleno == cycle ) {
434 cyclenlp -> selfcalls += arcp -> arc_count;
435 } else {
436 cyclenlp -> npropcall += arcp -> arc_count;
437 }
438 }
439 }
440 }
441 }
442
443 /*
444 * analyze cycles to determine breakup
445 */
446 bool
cycleanalyze(void)447 cycleanalyze(void)
448 {
449 arctype **cyclestack;
450 arctype **stkp;
451 arctype **arcpp;
452 arctype **endlist;
453 arctype *arcp;
454 nltype *nlp;
455 cltype *clp;
456 bool ret;
457 bool done;
458 int size;
459 int cycleno;
460
461 /*
462 * calculate the size of the cycle, and find nodes that
463 * exit the cycle as they are desirable targets to cut
464 * some of their parents
465 */
466 for ( done = TRUE , cycleno = 1 ; cycleno <= ncycle ; cycleno++ ) {
467 size = 0;
468 for (nlp = cyclenl[ cycleno ] . cnext; nlp; nlp = nlp -> cnext) {
469 size += 1;
470 nlp -> parentcnt = 0;
471 nlp -> flags &= ~HASCYCLEXIT;
472 for ( arcp = nlp -> parents; arcp; arcp = arcp -> arc_parentlist ) {
473 nlp -> parentcnt += 1;
474 if ( arcp -> arc_parentp -> cycleno != cycleno )
475 nlp -> flags |= HASCYCLEXIT;
476 }
477 }
478 if ( size <= cyclethreshold )
479 continue;
480 done = FALSE;
481 cyclestack = (arctype **) calloc( size + 1 , sizeof( arctype *) );
482 if ( cyclestack == 0 )
483 errx( 1, "no room for %zu bytes of cycle stack" ,
484 ( size + 1 ) * sizeof( arctype * ) );
485 # ifdef DEBUG
486 if ( debug & BREAKCYCLE ) {
487 printf( "[cycleanalyze] starting cycle %d of %d, size %d\n" ,
488 cycleno , ncycle , size );
489 }
490 # endif /* DEBUG */
491 for ( nlp = cyclenl[ cycleno ] . cnext ; nlp ; nlp = nlp -> cnext ) {
492 stkp = &cyclestack[0];
493 nlp -> flags |= CYCLEHEAD;
494 ret = descend ( nlp , cyclestack , stkp );
495 nlp -> flags &= ~CYCLEHEAD;
496 if ( ret == FALSE )
497 break;
498 }
499 free( cyclestack );
500 if ( cyclecnt > 0 ) {
501 compresslist();
502 for ( clp = cyclehead ; clp ; ) {
503 endlist = &clp -> list[ clp -> size ];
504 for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
505 (*arcpp) -> arc_cyclecnt--;
506 cyclecnt--;
507 clp = clp -> next;
508 free( clp );
509 }
510 cyclehead = 0;
511 }
512 }
513 # ifdef DEBUG
514 if ( debug & BREAKCYCLE ) {
515 printf("%s visited %d, viable %d, newcycle %d, oldcycle %d\n",
516 "[doarcs]" , visited , viable , newcycle , oldcycle);
517 }
518 # endif /* DEBUG */
519 return( done );
520 }
521
522 bool
descend(nltype * node,arctype ** stkstart,arctype ** stkp)523 descend(nltype *node, arctype **stkstart, arctype **stkp)
524 {
525 arctype *arcp;
526 bool ret;
527
528 for ( arcp = node -> children ; arcp ; arcp = arcp -> arc_childlist ) {
529 # ifdef DEBUG
530 visited++;
531 # endif /* DEBUG */
532 if ( arcp -> arc_childp -> cycleno != node -> cycleno
533 || ( arcp -> arc_childp -> flags & VISITED )
534 || ( arcp -> arc_flags & DEADARC ) )
535 continue;
536 # ifdef DEBUG
537 viable++;
538 # endif /* DEBUG */
539 *stkp = arcp;
540 if ( arcp -> arc_childp -> flags & CYCLEHEAD ) {
541 if ( addcycle( stkstart , stkp ) == FALSE )
542 return( FALSE );
543 continue;
544 }
545 arcp -> arc_childp -> flags |= VISITED;
546 ret = descend( arcp -> arc_childp , stkstart , stkp + 1 );
547 arcp -> arc_childp -> flags &= ~VISITED;
548 if ( ret == FALSE )
549 return( FALSE );
550 }
551 return( TRUE );
552 }
553
554 bool
addcycle(arctype ** stkstart,arctype ** stkend)555 addcycle(arctype **stkstart, arctype **stkend)
556 {
557 arctype **arcpp;
558 arctype **stkloc;
559 arctype **stkp;
560 arctype **endlist;
561 arctype *minarc;
562 arctype *arcp;
563 cltype *clp;
564 int size;
565
566 size = stkend - stkstart + 1;
567 if ( size <= 1 )
568 return( TRUE );
569 for ( arcpp = stkstart , minarc = *arcpp ; arcpp <= stkend ; arcpp++ ) {
570 if ( *arcpp > minarc )
571 continue;
572 minarc = *arcpp;
573 stkloc = arcpp;
574 }
575 for ( clp = cyclehead ; clp ; clp = clp -> next ) {
576 if ( clp -> size != size )
577 continue;
578 stkp = stkloc;
579 endlist = &clp -> list[ size ];
580 for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) {
581 if ( *stkp++ != *arcpp )
582 break;
583 if ( stkp > stkend )
584 stkp = stkstart;
585 }
586 if ( arcpp == endlist ) {
587 # ifdef DEBUG
588 oldcycle++;
589 # endif /* DEBUG */
590 return( TRUE );
591 }
592 }
593 clp = (cltype *)
594 calloc( 1 , sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) );
595 if ( clp == 0 ) {
596 warnx( "no room for %zu bytes of subcycle storage" ,
597 sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) );
598 return( FALSE );
599 }
600 stkp = stkloc;
601 endlist = &clp -> list[ size ];
602 for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) {
603 arcp = *arcpp = *stkp++;
604 if ( stkp > stkend )
605 stkp = stkstart;
606 arcp -> arc_cyclecnt++;
607 if ( ( arcp -> arc_flags & ONLIST ) == 0 ) {
608 arcp -> arc_flags |= ONLIST;
609 arcp -> arc_next = archead;
610 archead = arcp;
611 }
612 }
613 clp -> size = size;
614 clp -> next = cyclehead;
615 cyclehead = clp;
616 # ifdef DEBUG
617 newcycle++;
618 if ( debug & SUBCYCLELIST ) {
619 printsubcycle( clp );
620 }
621 # endif /* DEBUG */
622 cyclecnt++;
623 if ( cyclecnt >= CYCLEMAX )
624 return( FALSE );
625 return( TRUE );
626 }
627
628 void
compresslist(void)629 compresslist(void)
630 {
631 cltype *clp;
632 cltype **prev;
633 arctype **arcpp;
634 arctype **endlist;
635 arctype *arcp;
636 arctype *maxarcp;
637 arctype *maxexitarcp;
638 arctype *maxwithparentarcp;
639 arctype *maxnoparentarcp;
640 int maxexitcnt;
641 int maxwithparentcnt;
642 int maxnoparentcnt;
643 # ifdef DEBUG
644 const char *type;
645 # endif /* DEBUG */
646
647 maxexitcnt = 0;
648 maxwithparentcnt = 0;
649 maxnoparentcnt = 0;
650 for ( endlist = &archead , arcp = archead ; arcp ; ) {
651 if ( arcp -> arc_cyclecnt == 0 ) {
652 arcp -> arc_flags &= ~ONLIST;
653 *endlist = arcp -> arc_next;
654 arcp -> arc_next = 0;
655 arcp = *endlist;
656 continue;
657 }
658 if ( arcp -> arc_childp -> flags & HASCYCLEXIT ) {
659 if ( arcp -> arc_cyclecnt > maxexitcnt ||
660 ( arcp -> arc_cyclecnt == maxexitcnt &&
661 arcp -> arc_cyclecnt < maxexitarcp -> arc_count ) ) {
662 maxexitcnt = arcp -> arc_cyclecnt;
663 maxexitarcp = arcp;
664 }
665 } else if ( arcp -> arc_childp -> parentcnt > 1 ) {
666 if ( arcp -> arc_cyclecnt > maxwithparentcnt ||
667 ( arcp -> arc_cyclecnt == maxwithparentcnt &&
668 arcp -> arc_cyclecnt < maxwithparentarcp -> arc_count ) ) {
669 maxwithparentcnt = arcp -> arc_cyclecnt;
670 maxwithparentarcp = arcp;
671 }
672 } else {
673 if ( arcp -> arc_cyclecnt > maxnoparentcnt ||
674 ( arcp -> arc_cyclecnt == maxnoparentcnt &&
675 arcp -> arc_cyclecnt < maxnoparentarcp -> arc_count ) ) {
676 maxnoparentcnt = arcp -> arc_cyclecnt;
677 maxnoparentarcp = arcp;
678 }
679 }
680 endlist = &arcp -> arc_next;
681 arcp = arcp -> arc_next;
682 }
683 if ( maxexitcnt > 0 ) {
684 /*
685 * first choice is edge leading to node with out-of-cycle parent
686 */
687 maxarcp = maxexitarcp;
688 # ifdef DEBUG
689 type = "exit";
690 # endif /* DEBUG */
691 } else if ( maxwithparentcnt > 0 ) {
692 /*
693 * second choice is edge leading to node with at least one
694 * other in-cycle parent
695 */
696 maxarcp = maxwithparentarcp;
697 # ifdef DEBUG
698 type = "internal";
699 # endif /* DEBUG */
700 } else {
701 /*
702 * last choice is edge leading to node with only this arc as
703 * a parent (as it will now be orphaned)
704 */
705 maxarcp = maxnoparentarcp;
706 # ifdef DEBUG
707 type = "orphan";
708 # endif /* DEBUG */
709 }
710 maxarcp -> arc_flags |= DEADARC;
711 maxarcp -> arc_childp -> parentcnt -= 1;
712 maxarcp -> arc_childp -> npropcall -= maxarcp -> arc_count;
713 # ifdef DEBUG
714 if ( debug & BREAKCYCLE ) {
715 printf( "%s delete %s arc: %s (%ld) -> %s from %u cycle(s)\n" ,
716 "[compresslist]" , type , maxarcp -> arc_parentp -> name ,
717 maxarcp -> arc_count , maxarcp -> arc_childp -> name ,
718 maxarcp -> arc_cyclecnt );
719 }
720 # endif /* DEBUG */
721 printf( "\t%s to %s with %ld calls\n" , maxarcp -> arc_parentp -> name ,
722 maxarcp -> arc_childp -> name , maxarcp -> arc_count );
723 prev = &cyclehead;
724 for ( clp = cyclehead ; clp ; ) {
725 endlist = &clp -> list[ clp -> size ];
726 for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
727 if ( (*arcpp) -> arc_flags & DEADARC )
728 break;
729 if ( arcpp == endlist ) {
730 prev = &clp -> next;
731 clp = clp -> next;
732 continue;
733 }
734 for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
735 (*arcpp) -> arc_cyclecnt--;
736 cyclecnt--;
737 *prev = clp -> next;
738 clp = clp -> next;
739 free( clp );
740 }
741 }
742
743 #ifdef DEBUG
744 void
printsubcycle(cltype * clp)745 printsubcycle(cltype *clp)
746 {
747 arctype **arcpp;
748 arctype **endlist;
749
750 arcpp = clp -> list;
751 printf( "%s <cycle %d>\n" , (*arcpp) -> arc_parentp -> name ,
752 (*arcpp) -> arc_parentp -> cycleno ) ;
753 for ( endlist = &clp -> list[ clp -> size ]; arcpp < endlist ; arcpp++ )
754 printf( "\t(%ld) -> %s\n" , (*arcpp) -> arc_count ,
755 (*arcpp) -> arc_childp -> name ) ;
756 }
757 #endif /* DEBUG */
758
759 void
cycletime(void)760 cycletime(void)
761 {
762 int cycle;
763 nltype *cyclenlp;
764 nltype *childp;
765
766 for ( cycle = 1 ; cycle <= ncycle ; cycle += 1 ) {
767 cyclenlp = &cyclenl[ cycle ];
768 for ( childp = cyclenlp -> cnext ; childp ; childp = childp -> cnext ) {
769 if ( childp -> propfraction == 0.0 ) {
770 /*
771 * all members have the same propfraction except those
772 * that were excluded with -E
773 */
774 continue;
775 }
776 cyclenlp -> time += childp -> time;
777 }
778 cyclenlp -> propself = cyclenlp -> propfraction * cyclenlp -> time;
779 }
780 }
781
782 /*
783 * in one top to bottom pass over the topologically sorted namelist
784 * propagate:
785 * printflag as the union of parents' printflags
786 * propfraction as the sum of fractional parents' propfractions
787 * and while we're here, sum time for functions.
788 */
789 void
doflags(void)790 doflags(void)
791 {
792 int index;
793 nltype *childp;
794 nltype *oldhead;
795
796 oldhead = 0;
797 for ( index = nname-1 ; index >= 0 ; index -= 1 ) {
798 childp = topsortnlp[ index ];
799 /*
800 * if we haven't done this function or cycle,
801 * inherit things from parent.
802 * this way, we are linear in the number of arcs
803 * since we do all members of a cycle (and the cycle itself)
804 * as we hit the first member of the cycle.
805 */
806 if ( childp -> cyclehead != oldhead ) {
807 oldhead = childp -> cyclehead;
808 inheritflags( childp );
809 }
810 # ifdef DEBUG
811 if ( debug & PROPDEBUG ) {
812 printf( "[doflags] " );
813 printname( childp );
814 printf( " inherits printflag %d and propfraction %f\n" ,
815 childp -> printflag , childp -> propfraction );
816 }
817 # endif /* DEBUG */
818 if ( ! childp -> printflag ) {
819 /*
820 * printflag is off
821 * it gets turned on by
822 * being on -f list,
823 * or there not being any -f list and not being on -e list.
824 */
825 if ( onlist( flist , childp -> name )
826 || ( !fflag && !onlist( elist , childp -> name ) ) ) {
827 childp -> printflag = TRUE;
828 }
829 } else {
830 /*
831 * this function has printing parents:
832 * maybe someone wants to shut it up
833 * by putting it on -e list. (but favor -f over -e)
834 */
835 if ( ( !onlist( flist , childp -> name ) )
836 && onlist( elist , childp -> name ) ) {
837 childp -> printflag = FALSE;
838 }
839 }
840 if ( childp -> propfraction == 0.0 ) {
841 /*
842 * no parents to pass time to.
843 * collect time from children if
844 * its on -F list,
845 * or there isn't any -F list and its not on -E list.
846 */
847 if ( onlist( Flist , childp -> name )
848 || ( !Fflag && !onlist( Elist , childp -> name ) ) ) {
849 childp -> propfraction = 1.0;
850 }
851 } else {
852 /*
853 * it has parents to pass time to,
854 * but maybe someone wants to shut it up
855 * by putting it on -E list. (but favor -F over -E)
856 */
857 if ( !onlist( Flist , childp -> name )
858 && onlist( Elist , childp -> name ) ) {
859 childp -> propfraction = 0.0;
860 }
861 }
862 childp -> propself = childp -> time * childp -> propfraction;
863 printtime += childp -> propself;
864 # ifdef DEBUG
865 if ( debug & PROPDEBUG ) {
866 printf( "[doflags] " );
867 printname( childp );
868 printf( " ends up with printflag %d and propfraction %f\n" ,
869 childp -> printflag , childp -> propfraction );
870 printf( "time %f propself %f printtime %f\n" ,
871 childp -> time , childp -> propself , printtime );
872 }
873 # endif /* DEBUG */
874 }
875 }
876
877 /*
878 * check if any parent of this child
879 * (or outside parents of this cycle)
880 * have their print flags on and set the
881 * print flag of the child (cycle) appropriately.
882 * similarly, deal with propagation fractions from parents.
883 */
884 void
inheritflags(nltype * childp)885 inheritflags(nltype *childp)
886 {
887 nltype *headp;
888 arctype *arcp;
889 nltype *parentp;
890 nltype *memp;
891
892 headp = childp -> cyclehead;
893 if ( childp == headp ) {
894 /*
895 * just a regular child, check its parents
896 */
897 childp -> printflag = FALSE;
898 childp -> propfraction = 0.0;
899 for (arcp = childp -> parents ; arcp ; arcp = arcp -> arc_parentlist) {
900 parentp = arcp -> arc_parentp;
901 if ( childp == parentp ) {
902 continue;
903 }
904 childp -> printflag |= parentp -> printflag;
905 /*
906 * if the child was never actually called
907 * (e.g. this arc is static (and all others are, too))
908 * no time propagates along this arc.
909 */
910 if ( arcp -> arc_flags & DEADARC ) {
911 continue;
912 }
913 if ( childp -> npropcall ) {
914 childp -> propfraction += parentp -> propfraction
915 * ( ( (double) arcp -> arc_count )
916 / ( (double) childp -> npropcall ) );
917 }
918 }
919 } else {
920 /*
921 * its a member of a cycle, look at all parents from
922 * outside the cycle
923 */
924 headp -> printflag = FALSE;
925 headp -> propfraction = 0.0;
926 for ( memp = headp -> cnext ; memp ; memp = memp -> cnext ) {
927 for (arcp = memp->parents ; arcp ; arcp = arcp->arc_parentlist) {
928 if ( arcp -> arc_parentp -> cyclehead == headp ) {
929 continue;
930 }
931 parentp = arcp -> arc_parentp;
932 headp -> printflag |= parentp -> printflag;
933 /*
934 * if the cycle was never actually called
935 * (e.g. this arc is static (and all others are, too))
936 * no time propagates along this arc.
937 */
938 if ( arcp -> arc_flags & DEADARC ) {
939 continue;
940 }
941 if ( headp -> npropcall ) {
942 headp -> propfraction += parentp -> propfraction
943 * ( ( (double) arcp -> arc_count )
944 / ( (double) headp -> npropcall ) );
945 }
946 }
947 }
948 for ( memp = headp ; memp ; memp = memp -> cnext ) {
949 memp -> printflag = headp -> printflag;
950 memp -> propfraction = headp -> propfraction;
951 }
952 }
953 }
954