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