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 #include <sys/cdefs.h>
33 #include <err.h>
34 #include "gprof.h"
35
36 #ifdef DEBUG
37 int visited;
38 int viable;
39 int newcycle;
40 int oldcycle;
41 #endif /* DEBUG */
42
43 int topcmp(const void *, const void *);
44
45 /*
46 * add (or just increment) an arc
47 */
48 void
addarc(nltype * parentp,nltype * childp,long count)49 addarc(nltype *parentp, nltype *childp, long count)
50 {
51 arctype *arcp;
52
53 # ifdef DEBUG
54 if ( debug & TALLYDEBUG ) {
55 printf( "[addarc] %ld arcs from %s to %s\n" ,
56 count , parentp -> name , childp -> name );
57 }
58 # endif /* DEBUG */
59 arcp = arclookup( parentp , childp );
60 if ( arcp != 0 ) {
61 /*
62 * a hit: just increment the count.
63 */
64 # ifdef DEBUG
65 if ( debug & TALLYDEBUG ) {
66 printf( "[tally] hit %ld += %ld\n" ,
67 arcp -> arc_count , count );
68 }
69 # endif /* DEBUG */
70 arcp -> arc_count += count;
71 return;
72 }
73 arcp = (arctype *)calloc( 1 , sizeof *arcp );
74 if (arcp == NULL)
75 errx( 1 , "malloc failed" );
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 int
topcmp(const void * v1,const void * v2)102 topcmp(const void *v1, const void *v2)
103 {
104 const nltype **npp1 = (const nltype **)v1;
105 const nltype **npp2 = (const nltype **)v2;
106
107 return (*npp1) -> toporder - (*npp2) -> toporder;
108 }
109
110 nltype **
doarcs(void)111 doarcs(void)
112 {
113 nltype *parentp, **timesortnlp;
114 arctype *arcp;
115 long index;
116 long pass;
117
118 /*
119 * initialize various things:
120 * zero out child times.
121 * count self-recursive calls.
122 * indicate that nothing is on cycles.
123 */
124 for ( parentp = nl ; parentp < npe ; parentp++ ) {
125 parentp -> childtime = 0.0;
126 arcp = arclookup( parentp , parentp );
127 if ( arcp != 0 ) {
128 parentp -> ncall -= arcp -> arc_count;
129 parentp -> selfcalls = arcp -> arc_count;
130 } else {
131 parentp -> selfcalls = 0;
132 }
133 parentp -> npropcall = parentp -> ncall;
134 parentp -> propfraction = 0.0;
135 parentp -> propself = 0.0;
136 parentp -> propchild = 0.0;
137 parentp -> printflag = FALSE;
138 parentp -> toporder = DFN_NAN;
139 parentp -> cycleno = 0;
140 parentp -> cyclehead = parentp;
141 parentp -> cnext = 0;
142 }
143 for ( pass = 1 ; ; pass++ ) {
144 /*
145 * topologically order things
146 * if any node is unnumbered,
147 * number it and any of its descendents.
148 */
149 for ( dfn_init() , parentp = nl ; parentp < npe ; parentp++ ) {
150 if ( parentp -> toporder == DFN_NAN ) {
151 dfn( parentp );
152 }
153 }
154 /*
155 * link together nodes on the same cycle
156 */
157 cyclelink();
158 /*
159 * if no cycles to break up, proceed
160 */
161 if ( ! Cflag )
162 break;
163 /*
164 * analyze cycles to determine breakup
165 */
166 # ifdef DEBUG
167 if ( debug & BREAKCYCLE ) {
168 printf("[doarcs] pass %ld, cycle(s) %d\n" , pass , ncycle );
169 }
170 # endif /* DEBUG */
171 if ( pass == 1 ) {
172 printf( "\n\n%s %s\n%s %d:\n" ,
173 "The following arcs were deleted" ,
174 "from the propagation calculation" ,
175 "to reduce the maximum cycle size to", cyclethreshold );
176 }
177 if ( cycleanalyze() )
178 break;
179 free ( cyclenl );
180 ncycle = 0;
181 for ( parentp = nl ; parentp < npe ; parentp++ ) {
182 parentp -> toporder = DFN_NAN;
183 parentp -> cycleno = 0;
184 parentp -> cyclehead = parentp;
185 parentp -> cnext = 0;
186 }
187 }
188 if ( pass > 1 ) {
189 printf( "\f\n" );
190 } else {
191 printf( "\tNone\n\n" );
192 }
193 /*
194 * Sort the symbol table in reverse topological order
195 */
196 topsortnlp = (nltype **) calloc( nname , sizeof(nltype *) );
197 if ( topsortnlp == (nltype **) 0 )
198 errx( 1 , "[doarcs] ran out of memory for topo sorting" );
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 * propagate 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 errx( 1 , "ran out of memory for sorting" );
235 for ( index = 0 ; index < nname ; index++ ) {
236 timesortnlp[index] = &nl[index];
237 }
238 for ( index = 1 ; index <= ncycle ; index++ ) {
239 timesortnlp[nname+index-1] = &cyclenl[index];
240 }
241 qsort( timesortnlp , nname + ncycle , sizeof(nltype *) , totalcmp );
242 for ( index = 0 ; index < nname + ncycle ; index++ ) {
243 timesortnlp[ index ] -> index = index + 1;
244 }
245 return( timesortnlp );
246 }
247
248 void
dotime(void)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 void
timepropagate(nltype * parentp)260 timepropagate(nltype *parentp)
261 {
262 arctype *arcp;
263 nltype *childp;
264 double share;
265 double propshare;
266
267 if ( parentp -> propfraction == 0.0 ) {
268 return;
269 }
270 /*
271 * gather time from children of this parent.
272 */
273 for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
274 childp = arcp -> arc_childp;
275 if ( arcp -> arc_flags & DEADARC ) {
276 continue;
277 }
278 if ( arcp -> arc_count == 0 ) {
279 continue;
280 }
281 if ( childp == parentp ) {
282 continue;
283 }
284 if ( childp -> propfraction == 0.0 ) {
285 continue;
286 }
287 if ( childp -> cyclehead != childp ) {
288 if ( parentp -> cycleno == childp -> cycleno ) {
289 continue;
290 }
291 if ( parentp -> toporder <= childp -> toporder ) {
292 fprintf( stderr , "[propagate] toporder botches\n" );
293 }
294 childp = childp -> cyclehead;
295 } else {
296 if ( parentp -> toporder <= childp -> toporder ) {
297 fprintf( stderr , "[propagate] toporder botches\n" );
298 continue;
299 }
300 }
301 if ( childp -> npropcall == 0 ) {
302 continue;
303 }
304 /*
305 * distribute time for this arc
306 */
307 arcp -> arc_time = childp -> time
308 * ( ( (double) arcp -> arc_count ) /
309 ( (double) childp -> npropcall ) );
310 arcp -> arc_childtime = childp -> childtime
311 * ( ( (double) arcp -> arc_count ) /
312 ( (double) childp -> npropcall ) );
313 share = arcp -> arc_time + arcp -> arc_childtime;
314 parentp -> childtime += share;
315 /*
316 * ( 1 - propfraction ) gets lost along the way
317 */
318 propshare = parentp -> propfraction * share;
319 /*
320 * fix things for printing
321 */
322 parentp -> propchild += propshare;
323 arcp -> arc_time *= parentp -> propfraction;
324 arcp -> arc_childtime *= parentp -> propfraction;
325 /*
326 * add this share to the parent's cycle header, if any.
327 */
328 if ( parentp -> cyclehead != parentp ) {
329 parentp -> cyclehead -> childtime += share;
330 parentp -> cyclehead -> propchild += propshare;
331 }
332 # ifdef DEBUG
333 if ( debug & PROPDEBUG ) {
334 printf( "[dotime] child \t" );
335 printname( childp );
336 printf( " with %f %f %ld/%ld\n" ,
337 childp -> time , childp -> childtime ,
338 arcp -> arc_count , childp -> npropcall );
339 printf( "[dotime] parent\t" );
340 printname( parentp );
341 printf( "\n[dotime] share %f\n" , share );
342 }
343 # endif /* DEBUG */
344 }
345 }
346
347 void
cyclelink(void)348 cyclelink(void)
349 {
350 register nltype *nlp;
351 register nltype *cyclenlp;
352 int cycle;
353 nltype *memberp;
354 arctype *arcp;
355
356 /*
357 * Count the number of cycles, and initialize the cycle lists
358 */
359 ncycle = 0;
360 for ( nlp = nl ; nlp < npe ; nlp++ ) {
361 /*
362 * this is how you find unattached cycles
363 */
364 if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) {
365 ncycle += 1;
366 }
367 }
368 /*
369 * cyclenl is indexed by cycle number:
370 * i.e. it is origin 1, not origin 0.
371 */
372 cyclenl = (nltype *) calloc( ncycle + 1 , sizeof( nltype ) );
373 if ( cyclenl == NULL )
374 errx( 1 , "no room for %zu bytes of cycle headers" ,
375 ( ncycle + 1 ) * sizeof( nltype ) );
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 bool
cycleanalyze(void)441 cycleanalyze(void)
442 {
443 arctype **cyclestack;
444 arctype **stkp;
445 arctype **arcpp;
446 arctype **endlist;
447 arctype *arcp;
448 nltype *nlp;
449 cltype *clp;
450 bool ret;
451 bool done;
452 int size;
453 int cycleno;
454
455 /*
456 * calculate the size of the cycle, and find nodes that
457 * exit the cycle as they are desirable targets to cut
458 * some of their parents
459 */
460 for ( done = TRUE , cycleno = 1 ; cycleno <= ncycle ; cycleno++ ) {
461 size = 0;
462 for (nlp = cyclenl[ cycleno ] . cnext; nlp; nlp = nlp -> cnext) {
463 size += 1;
464 nlp -> parentcnt = 0;
465 nlp -> flags &= ~HASCYCLEXIT;
466 for ( arcp = nlp -> parents; arcp; arcp = arcp -> arc_parentlist ) {
467 nlp -> parentcnt += 1;
468 if ( arcp -> arc_parentp -> cycleno != cycleno )
469 nlp -> flags |= HASCYCLEXIT;
470 }
471 }
472 if ( size <= cyclethreshold )
473 continue;
474 done = FALSE;
475 cyclestack = (arctype **) calloc( size + 1 , sizeof( arctype *) );
476 if ( cyclestack == NULL )
477 errx( 1, "no room for %zu bytes of cycle stack" ,
478 ( size + 1 ) * sizeof( arctype * ) );
479 # ifdef DEBUG
480 if ( debug & BREAKCYCLE ) {
481 printf( "[cycleanalyze] starting cycle %d of %d, size %d\n" ,
482 cycleno , ncycle , size );
483 }
484 # endif /* DEBUG */
485 for ( nlp = cyclenl[ cycleno ] . cnext ; nlp ; nlp = nlp -> cnext ) {
486 stkp = &cyclestack[0];
487 nlp -> flags |= CYCLEHEAD;
488 ret = descend ( nlp , cyclestack , stkp );
489 nlp -> flags &= ~CYCLEHEAD;
490 if ( ret == FALSE )
491 break;
492 }
493 free( cyclestack );
494 if ( cyclecnt > 0 ) {
495 compresslist();
496 for ( clp = cyclehead ; clp ; ) {
497 endlist = &clp -> list[ clp -> size ];
498 for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
499 (*arcpp) -> arc_cyclecnt--;
500 cyclecnt--;
501 clp = clp -> next;
502 free( clp );
503 }
504 cyclehead = 0;
505 }
506 }
507 # ifdef DEBUG
508 if ( debug & BREAKCYCLE ) {
509 printf("%s visited %d, viable %d, newcycle %d, oldcycle %d\n",
510 "[doarcs]" , visited , viable , newcycle , oldcycle);
511 }
512 # endif /* DEBUG */
513 return( done );
514 }
515
516 bool
descend(nltype * node,arctype ** stkstart,arctype ** stkp)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 return( TRUE );
546 }
547
548 bool
addcycle(arctype ** stkstart,arctype ** stkend)549 addcycle(arctype **stkstart, arctype **stkend)
550 {
551 arctype **arcpp;
552 arctype **stkloc;
553 arctype **stkp;
554 arctype **endlist;
555 arctype *minarc;
556 arctype *arcp;
557 cltype *clp;
558 int size;
559
560 size = stkend - stkstart + 1;
561 if ( size <= 1 )
562 return( TRUE );
563 for ( arcpp = stkstart , minarc = *arcpp ; arcpp <= stkend ; arcpp++ ) {
564 if ( *arcpp > minarc )
565 continue;
566 minarc = *arcpp;
567 stkloc = arcpp;
568 }
569 for ( clp = cyclehead ; clp ; clp = clp -> next ) {
570 if ( clp -> size != size )
571 continue;
572 stkp = stkloc;
573 endlist = &clp -> list[ size ];
574 for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) {
575 if ( *stkp++ != *arcpp )
576 break;
577 if ( stkp > stkend )
578 stkp = stkstart;
579 }
580 if ( arcpp == endlist ) {
581 # ifdef DEBUG
582 oldcycle++;
583 # endif /* DEBUG */
584 return( TRUE );
585 }
586 }
587 clp = (cltype *)
588 calloc( 1 , sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) );
589 if ( clp == NULL ) {
590 warnx( "no room for %zu bytes of subcycle storage" ,
591 sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) );
592 return( FALSE );
593 }
594 stkp = stkloc;
595 endlist = &clp -> list[ size ];
596 for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) {
597 arcp = *arcpp = *stkp++;
598 if ( stkp > stkend )
599 stkp = stkstart;
600 arcp -> arc_cyclecnt++;
601 if ( ( arcp -> arc_flags & ONLIST ) == 0 ) {
602 arcp -> arc_flags |= ONLIST;
603 arcp -> arc_next = archead;
604 archead = arcp;
605 }
606 }
607 clp -> size = size;
608 clp -> next = cyclehead;
609 cyclehead = clp;
610 # ifdef DEBUG
611 newcycle++;
612 if ( debug & SUBCYCLELIST ) {
613 printsubcycle( clp );
614 }
615 # endif /* DEBUG */
616 cyclecnt++;
617 if ( cyclecnt >= CYCLEMAX )
618 return( FALSE );
619 return( TRUE );
620 }
621
622 void
compresslist(void)623 compresslist(void)
624 {
625 cltype *clp;
626 cltype **prev;
627 arctype **arcpp;
628 arctype **endlist;
629 arctype *arcp;
630 arctype *maxarcp;
631 arctype *maxexitarcp;
632 arctype *maxwithparentarcp;
633 arctype *maxnoparentarcp;
634 int maxexitcnt;
635 int maxwithparentcnt;
636 int maxnoparentcnt;
637 # ifdef DEBUG
638 const char *type;
639 # endif /* DEBUG */
640
641 maxexitcnt = 0;
642 maxwithparentcnt = 0;
643 maxnoparentcnt = 0;
644 for ( endlist = &archead , arcp = archead ; arcp ; ) {
645 if ( arcp -> arc_cyclecnt == 0 ) {
646 arcp -> arc_flags &= ~ONLIST;
647 *endlist = arcp -> arc_next;
648 arcp -> arc_next = 0;
649 arcp = *endlist;
650 continue;
651 }
652 if ( arcp -> arc_childp -> flags & HASCYCLEXIT ) {
653 if ( arcp -> arc_cyclecnt > maxexitcnt ||
654 ( arcp -> arc_cyclecnt == maxexitcnt &&
655 arcp -> arc_cyclecnt < maxexitarcp -> arc_count ) ) {
656 maxexitcnt = arcp -> arc_cyclecnt;
657 maxexitarcp = arcp;
658 }
659 } else if ( arcp -> arc_childp -> parentcnt > 1 ) {
660 if ( arcp -> arc_cyclecnt > maxwithparentcnt ||
661 ( arcp -> arc_cyclecnt == maxwithparentcnt &&
662 arcp -> arc_cyclecnt < maxwithparentarcp -> arc_count ) ) {
663 maxwithparentcnt = arcp -> arc_cyclecnt;
664 maxwithparentarcp = arcp;
665 }
666 } else {
667 if ( arcp -> arc_cyclecnt > maxnoparentcnt ||
668 ( arcp -> arc_cyclecnt == maxnoparentcnt &&
669 arcp -> arc_cyclecnt < maxnoparentarcp -> arc_count ) ) {
670 maxnoparentcnt = arcp -> arc_cyclecnt;
671 maxnoparentarcp = arcp;
672 }
673 }
674 endlist = &arcp -> arc_next;
675 arcp = arcp -> arc_next;
676 }
677 if ( maxexitcnt > 0 ) {
678 /*
679 * first choice is edge leading to node with out-of-cycle parent
680 */
681 maxarcp = maxexitarcp;
682 # ifdef DEBUG
683 type = "exit";
684 # endif /* DEBUG */
685 } else if ( maxwithparentcnt > 0 ) {
686 /*
687 * second choice is edge leading to node with at least one
688 * other in-cycle parent
689 */
690 maxarcp = maxwithparentarcp;
691 # ifdef DEBUG
692 type = "internal";
693 # endif /* DEBUG */
694 } else {
695 /*
696 * last choice is edge leading to node with only this arc as
697 * a parent (as it will now be orphaned)
698 */
699 maxarcp = maxnoparentarcp;
700 # ifdef DEBUG
701 type = "orphan";
702 # endif /* DEBUG */
703 }
704 maxarcp -> arc_flags |= DEADARC;
705 maxarcp -> arc_childp -> parentcnt -= 1;
706 maxarcp -> arc_childp -> npropcall -= maxarcp -> arc_count;
707 # ifdef DEBUG
708 if ( debug & BREAKCYCLE ) {
709 printf( "%s delete %s arc: %s (%ld) -> %s from %u cycle(s)\n" ,
710 "[compresslist]" , type , maxarcp -> arc_parentp -> name ,
711 maxarcp -> arc_count , maxarcp -> arc_childp -> name ,
712 maxarcp -> arc_cyclecnt );
713 }
714 # endif /* DEBUG */
715 printf( "\t%s to %s with %ld calls\n" , maxarcp -> arc_parentp -> name ,
716 maxarcp -> arc_childp -> name , maxarcp -> arc_count );
717 prev = &cyclehead;
718 for ( clp = cyclehead ; clp ; ) {
719 endlist = &clp -> list[ clp -> size ];
720 for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
721 if ( (*arcpp) -> arc_flags & DEADARC )
722 break;
723 if ( arcpp == endlist ) {
724 prev = &clp -> next;
725 clp = clp -> next;
726 continue;
727 }
728 for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
729 (*arcpp) -> arc_cyclecnt--;
730 cyclecnt--;
731 *prev = clp -> next;
732 clp = clp -> next;
733 free( clp );
734 }
735 }
736
737 #ifdef DEBUG
738 void
printsubcycle(cltype * clp)739 printsubcycle(cltype *clp)
740 {
741 arctype **arcpp;
742 arctype **endlist;
743
744 arcpp = clp -> list;
745 printf( "%s <cycle %d>\n" , (*arcpp) -> arc_parentp -> name ,
746 (*arcpp) -> arc_parentp -> cycleno ) ;
747 for ( endlist = &clp -> list[ clp -> size ]; arcpp < endlist ; arcpp++ )
748 printf( "\t(%ld) -> %s\n" , (*arcpp) -> arc_count ,
749 (*arcpp) -> arc_childp -> name ) ;
750 }
751 #endif /* DEBUG */
752
753 void
cycletime(void)754 cycletime(void)
755 {
756 int cycle;
757 nltype *cyclenlp;
758 nltype *childp;
759
760 for ( cycle = 1 ; cycle <= ncycle ; cycle += 1 ) {
761 cyclenlp = &cyclenl[ cycle ];
762 for ( childp = cyclenlp -> cnext ; childp ; childp = childp -> cnext ) {
763 if ( childp -> propfraction == 0.0 ) {
764 /*
765 * all members have the same propfraction except those
766 * that were excluded with -E
767 */
768 continue;
769 }
770 cyclenlp -> time += childp -> time;
771 }
772 cyclenlp -> propself = cyclenlp -> propfraction * cyclenlp -> time;
773 }
774 }
775
776 /*
777 * in one top to bottom pass over the topologically sorted namelist
778 * propagate:
779 * printflag as the union of parents' printflags
780 * propfraction as the sum of fractional parents' propfractions
781 * and while we're here, sum time for functions.
782 */
783 void
doflags(void)784 doflags(void)
785 {
786 int index;
787 nltype *childp;
788 nltype *oldhead;
789
790 oldhead = 0;
791 for ( index = nname-1 ; index >= 0 ; index -= 1 ) {
792 childp = topsortnlp[ index ];
793 /*
794 * if we haven't done this function or cycle,
795 * inherit things from parent.
796 * this way, we are linear in the number of arcs
797 * since we do all members of a cycle (and the cycle itself)
798 * as we hit the first member of the cycle.
799 */
800 if ( childp -> cyclehead != oldhead ) {
801 oldhead = childp -> cyclehead;
802 inheritflags( childp );
803 }
804 # ifdef DEBUG
805 if ( debug & PROPDEBUG ) {
806 printf( "[doflags] " );
807 printname( childp );
808 printf( " inherits printflag %d and propfraction %f\n" ,
809 childp -> printflag , childp -> propfraction );
810 }
811 # endif /* DEBUG */
812 if ( ! childp -> printflag ) {
813 /*
814 * printflag is off
815 * it gets turned on by
816 * being on -f list,
817 * or there not being any -f list and not being on -e list.
818 */
819 if ( onlist( flist , childp -> name )
820 || ( !fflag && !onlist( elist , childp -> name ) ) ) {
821 childp -> printflag = TRUE;
822 }
823 } else {
824 /*
825 * this function has printing parents:
826 * maybe someone wants to shut it up
827 * by putting it on -e list. (but favor -f over -e)
828 */
829 if ( ( !onlist( flist , childp -> name ) )
830 && onlist( elist , childp -> name ) ) {
831 childp -> printflag = FALSE;
832 }
833 }
834 if ( childp -> propfraction == 0.0 ) {
835 /*
836 * no parents to pass time to.
837 * collect time from children if
838 * its on -F list,
839 * or there isn't any -F list and its not on -E list.
840 */
841 if ( onlist( Flist , childp -> name )
842 || ( !Fflag && !onlist( Elist , childp -> name ) ) ) {
843 childp -> propfraction = 1.0;
844 }
845 } else {
846 /*
847 * it has parents to pass time to,
848 * but maybe someone wants to shut it up
849 * by putting it on -E list. (but favor -F over -E)
850 */
851 if ( !onlist( Flist , childp -> name )
852 && onlist( Elist , childp -> name ) ) {
853 childp -> propfraction = 0.0;
854 }
855 }
856 childp -> propself = childp -> time * childp -> propfraction;
857 printtime += childp -> propself;
858 # ifdef DEBUG
859 if ( debug & PROPDEBUG ) {
860 printf( "[doflags] " );
861 printname( childp );
862 printf( " ends up with printflag %d and propfraction %f\n" ,
863 childp -> printflag , childp -> propfraction );
864 printf( "time %f propself %f printtime %f\n" ,
865 childp -> time , childp -> propself , printtime );
866 }
867 # endif /* DEBUG */
868 }
869 }
870
871 /*
872 * check if any parent of this child
873 * (or outside parents of this cycle)
874 * have their print flags on and set the
875 * print flag of the child (cycle) appropriately.
876 * similarly, deal with propagation fractions from parents.
877 */
878 void
inheritflags(nltype * childp)879 inheritflags(nltype *childp)
880 {
881 nltype *headp;
882 arctype *arcp;
883 nltype *parentp;
884 nltype *memp;
885
886 headp = childp -> cyclehead;
887 if ( childp == headp ) {
888 /*
889 * just a regular child, check its parents
890 */
891 childp -> printflag = FALSE;
892 childp -> propfraction = 0.0;
893 for (arcp = childp -> parents ; arcp ; arcp = arcp -> arc_parentlist) {
894 parentp = arcp -> arc_parentp;
895 if ( childp == parentp ) {
896 continue;
897 }
898 childp -> printflag |= parentp -> printflag;
899 /*
900 * if the child was never actually called
901 * (e.g. this arc is static (and all others are, too))
902 * no time propagates along this arc.
903 */
904 if ( arcp -> arc_flags & DEADARC ) {
905 continue;
906 }
907 if ( childp -> npropcall ) {
908 childp -> propfraction += parentp -> propfraction
909 * ( ( (double) arcp -> arc_count )
910 / ( (double) childp -> npropcall ) );
911 }
912 }
913 } else {
914 /*
915 * its a member of a cycle, look at all parents from
916 * outside the cycle
917 */
918 headp -> printflag = FALSE;
919 headp -> propfraction = 0.0;
920 for ( memp = headp -> cnext ; memp ; memp = memp -> cnext ) {
921 for (arcp = memp->parents ; arcp ; arcp = arcp->arc_parentlist) {
922 if ( arcp -> arc_parentp -> cyclehead == headp ) {
923 continue;
924 }
925 parentp = arcp -> arc_parentp;
926 headp -> printflag |= parentp -> printflag;
927 /*
928 * if the cycle was never actually called
929 * (e.g. this arc is static (and all others are, too))
930 * no time propagates along this arc.
931 */
932 if ( arcp -> arc_flags & DEADARC ) {
933 continue;
934 }
935 if ( headp -> npropcall ) {
936 headp -> propfraction += parentp -> propfraction
937 * ( ( (double) arcp -> arc_count )
938 / ( (double) headp -> npropcall ) );
939 }
940 }
941 }
942 for ( memp = headp ; memp ; memp = memp -> cnext ) {
943 memp -> printflag = headp -> printflag;
944 memp -> propfraction = headp -> propfraction;
945 }
946 }
947 }
948