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