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