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