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