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