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