![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to arcs.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / pgrm / gprof|
Return to arcs.c CVS log | Up to [CSRG BSD Unix] / 43BSDReno / pgrm / gprof |
1.1 root 1: /*
2: * Copyright (c) 1983 Regents of the University of California.
3: * All rights reserved.
4: *
5: * Redistribution and use in source and binary forms are permitted
6: * provided that: (1) source distributions retain this entire copyright
7: * notice and comment, and (2) distributions including binaries display
8: * the following acknowledgement: ``This product includes software
9: * developed by the University of California, Berkeley and its contributors''
10: * in the documentation or other materials provided with the distribution
11: * and in all advertising materials mentioning features or use of this
12: * software. Neither the name of the University nor the names of its
13: * contributors may be used to endorse or promote products derived
14: * from this software without specific prior written permission.
15: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
16: * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
17: * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
18: */
19:
20: #ifndef lint
21: static char sccsid[] = "@(#)arcs.c 5.6 (Berkeley) 6/1/90";
22: #endif /* not lint */
23:
24: #include "gprof.h"
25:
26: /*
27: * add (or just increment) an arc
28: */
29: addarc( parentp , childp , count )
30: nltype *parentp;
31: nltype *childp;
32: long count;
33: {
34: arctype *calloc();
35: arctype *arcp;
36:
37: # ifdef DEBUG
38: if ( debug & TALLYDEBUG ) {
39: printf( "[addarc] %d arcs from %s to %s\n" ,
40: count , parentp -> name , childp -> name );
41: }
42: # endif DEBUG
43: arcp = arclookup( parentp , childp );
44: if ( arcp != 0 ) {
45: /*
46: * a hit: just increment the count.
47: */
48: # ifdef DEBUG
49: if ( debug & TALLYDEBUG ) {
50: printf( "[tally] hit %d += %d\n" ,
51: arcp -> arc_count , count );
52: }
53: # endif DEBUG
54: arcp -> arc_count += count;
55: return;
56: }
57: arcp = calloc( 1 , sizeof *arcp );
58: arcp -> arc_parentp = parentp;
59: arcp -> arc_childp = childp;
60: arcp -> arc_count = count;
61: /*
62: * prepend this child to the children of this parent
63: */
64: arcp -> arc_childlist = parentp -> children;
65: parentp -> children = arcp;
66: /*
67: * prepend this parent to the parents of this child
68: */
69: arcp -> arc_parentlist = childp -> parents;
70: childp -> parents = arcp;
71: }
72:
73: /*
74: * the code below topologically sorts the graph (collapsing cycles),
75: * and propagates time bottom up and flags top down.
76: */
77:
78: /*
79: * the topologically sorted name list pointers
80: */
81: nltype **topsortnlp;
82:
83: topcmp( npp1 , npp2 )
84: nltype **npp1;
85: nltype **npp2;
86: {
87: return (*npp1) -> toporder - (*npp2) -> toporder;
88: }
89:
90: nltype **
91: doarcs()
92: {
93: nltype *parentp, **timesortnlp;
94: arctype *arcp;
95: long index;
96:
97: /*
98: * initialize various things:
99: * zero out child times.
100: * count self-recursive calls.
101: * indicate that nothing is on cycles.
102: */
103: for ( parentp = nl ; parentp < npe ; parentp++ ) {
104: parentp -> childtime = 0.0;
105: arcp = arclookup( parentp , parentp );
106: if ( arcp != 0 ) {
107: parentp -> ncall -= arcp -> arc_count;
108: parentp -> selfcalls = arcp -> arc_count;
109: } else {
110: parentp -> selfcalls = 0;
111: }
112: parentp -> propfraction = 0.0;
113: parentp -> propself = 0.0;
114: parentp -> propchild = 0.0;
115: parentp -> printflag = FALSE;
116: parentp -> toporder = DFN_NAN;
117: parentp -> cycleno = 0;
118: parentp -> cyclehead = parentp;
119: parentp -> cnext = 0;
120: if ( cflag ) {
121: findcall( parentp , parentp -> value , (parentp+1) -> value );
122: }
123: }
124: /*
125: * topologically order things
126: * if any node is unnumbered,
127: * number it and any of its descendents.
128: */
129: for ( parentp = nl ; parentp < npe ; parentp++ ) {
130: if ( parentp -> toporder == DFN_NAN ) {
131: dfn( parentp );
132: }
133: }
134: /*
135: * link together nodes on the same cycle
136: */
137: cyclelink();
138: /*
139: * Sort the symbol table in reverse topological order
140: */
141: topsortnlp = (nltype **) calloc( nname , sizeof(nltype *) );
142: if ( topsortnlp == (nltype **) 0 ) {
143: fprintf( stderr , "[doarcs] ran out of memory for topo sorting\n" );
144: }
145: for ( index = 0 ; index < nname ; index += 1 ) {
146: topsortnlp[ index ] = &nl[ index ];
147: }
148: qsort( topsortnlp , nname , sizeof(nltype *) , topcmp );
149: # ifdef DEBUG
150: if ( debug & DFNDEBUG ) {
151: printf( "[doarcs] topological sort listing\n" );
152: for ( index = 0 ; index < nname ; index += 1 ) {
153: printf( "[doarcs] " );
154: printf( "%d:" , topsortnlp[ index ] -> toporder );
155: printname( topsortnlp[ index ] );
156: printf( "\n" );
157: }
158: }
159: # endif DEBUG
160: /*
161: * starting from the topological top,
162: * propagate print flags to children.
163: * also, calculate propagation fractions.
164: * this happens before time propagation
165: * since time propagation uses the fractions.
166: */
167: doflags();
168: /*
169: * starting from the topological bottom,
170: * propogate children times up to parents.
171: */
172: dotime();
173: /*
174: * Now, sort by propself + propchild.
175: * sorting both the regular function names
176: * and cycle headers.
177: */
178: timesortnlp = (nltype **) calloc( nname + ncycle , sizeof(nltype *) );
179: if ( timesortnlp == (nltype **) 0 ) {
180: fprintf( stderr , "%s: ran out of memory for sorting\n" , whoami );
181: }
182: for ( index = 0 ; index < nname ; index++ ) {
183: timesortnlp[index] = &nl[index];
184: }
185: for ( index = 1 ; index <= ncycle ; index++ ) {
186: timesortnlp[nname+index-1] = &cyclenl[index];
187: }
188: qsort( timesortnlp , nname + ncycle , sizeof(nltype *) , totalcmp );
189: for ( index = 0 ; index < nname + ncycle ; index++ ) {
190: timesortnlp[ index ] -> index = index + 1;
191: }
192: return( timesortnlp );
193: }
194:
195: dotime()
196: {
197: int index;
198:
199: cycletime();
200: for ( index = 0 ; index < nname ; index += 1 ) {
201: timepropagate( topsortnlp[ index ] );
202: }
203: }
204:
205: timepropagate( parentp )
206: nltype *parentp;
207: {
208: arctype *arcp;
209: nltype *childp;
210: double share;
211: double propshare;
212:
213: if ( parentp -> propfraction == 0.0 ) {
214: return;
215: }
216: /*
217: * gather time from children of this parent.
218: */
219: for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
220: childp = arcp -> arc_childp;
221: if ( arcp -> arc_count == 0 ) {
222: continue;
223: }
224: if ( childp == parentp ) {
225: continue;
226: }
227: if ( childp -> propfraction == 0.0 ) {
228: continue;
229: }
230: if ( childp -> cyclehead != childp ) {
231: if ( parentp -> cycleno == childp -> cycleno ) {
232: continue;
233: }
234: if ( parentp -> toporder <= childp -> toporder ) {
235: fprintf( stderr , "[propagate] toporder botches\n" );
236: }
237: childp = childp -> cyclehead;
238: } else {
239: if ( parentp -> toporder <= childp -> toporder ) {
240: fprintf( stderr , "[propagate] toporder botches\n" );
241: continue;
242: }
243: }
244: if ( childp -> ncall == 0 ) {
245: continue;
246: }
247: /*
248: * distribute time for this arc
249: */
250: arcp -> arc_time = childp -> time
251: * ( ( (double) arcp -> arc_count ) /
252: ( (double) childp -> ncall ) );
253: arcp -> arc_childtime = childp -> childtime
254: * ( ( (double) arcp -> arc_count ) /
255: ( (double) childp -> ncall ) );
256: share = arcp -> arc_time + arcp -> arc_childtime;
257: parentp -> childtime += share;
258: /*
259: * ( 1 - propfraction ) gets lost along the way
260: */
261: propshare = parentp -> propfraction * share;
262: /*
263: * fix things for printing
264: */
265: parentp -> propchild += propshare;
266: arcp -> arc_time *= parentp -> propfraction;
267: arcp -> arc_childtime *= parentp -> propfraction;
268: /*
269: * add this share to the parent's cycle header, if any.
270: */
271: if ( parentp -> cyclehead != parentp ) {
272: parentp -> cyclehead -> childtime += share;
273: parentp -> cyclehead -> propchild += propshare;
274: }
275: # ifdef DEBUG
276: if ( debug & PROPDEBUG ) {
277: printf( "[dotime] child \t" );
278: printname( childp );
279: printf( " with %f %f %d/%d\n" ,
280: childp -> time , childp -> childtime ,
281: arcp -> arc_count , childp -> ncall );
282: printf( "[dotime] parent\t" );
283: printname( parentp );
284: printf( "\n[dotime] share %f\n" , share );
285: }
286: # endif DEBUG
287: }
288: }
289:
290: cyclelink()
291: {
292: register nltype *nlp;
293: register nltype *cyclenlp;
294: int cycle;
295: nltype *memberp;
296: arctype *arcp;
297:
298: /*
299: * Count the number of cycles, and initialze the cycle lists
300: */
301: ncycle = 0;
302: for ( nlp = nl ; nlp < npe ; nlp++ ) {
303: /*
304: * this is how you find unattached cycles
305: */
306: if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) {
307: ncycle += 1;
308: }
309: }
310: /*
311: * cyclenl is indexed by cycle number:
312: * i.e. it is origin 1, not origin 0.
313: */
314: cyclenl = (nltype *) calloc( ncycle + 1 , sizeof( nltype ) );
315: if ( cyclenl == 0 ) {
316: fprintf( stderr , "%s: No room for %d bytes of cycle headers\n" ,
317: whoami , ( ncycle + 1 ) * sizeof( nltype ) );
318: done();
319: }
320: /*
321: * now link cycles to true cycleheads,
322: * number them, accumulate the data for the cycle
323: */
324: cycle = 0;
325: for ( nlp = nl ; nlp < npe ; nlp++ ) {
326: if ( !( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) ) {
327: continue;
328: }
329: cycle += 1;
330: cyclenlp = &cyclenl[cycle];
331: cyclenlp -> name = 0; /* the name */
332: cyclenlp -> value = 0; /* the pc entry point */
333: cyclenlp -> time = 0.0; /* ticks in this routine */
334: cyclenlp -> childtime = 0.0; /* cumulative ticks in children */
335: cyclenlp -> ncall = 0; /* how many times called */
336: cyclenlp -> selfcalls = 0; /* how many calls to self */
337: cyclenlp -> propfraction = 0.0; /* what % of time propagates */
338: cyclenlp -> propself = 0.0; /* how much self time propagates */
339: cyclenlp -> propchild = 0.0; /* how much child time propagates */
340: cyclenlp -> printflag = TRUE; /* should this be printed? */
341: cyclenlp -> index = 0; /* index in the graph list */
342: cyclenlp -> toporder = DFN_NAN; /* graph call chain top-sort order */
343: cyclenlp -> cycleno = cycle; /* internal number of cycle on */
344: cyclenlp -> cyclehead = cyclenlp; /* pointer to head of cycle */
345: cyclenlp -> cnext = nlp; /* pointer to next member of cycle */
346: cyclenlp -> parents = 0; /* list of caller arcs */
347: cyclenlp -> children = 0; /* list of callee arcs */
348: # ifdef DEBUG
349: if ( debug & CYCLEDEBUG ) {
350: printf( "[cyclelink] " );
351: printname( nlp );
352: printf( " is the head of cycle %d\n" , cycle );
353: }
354: # endif DEBUG
355: /*
356: * link members to cycle header
357: */
358: for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) {
359: memberp -> cycleno = cycle;
360: memberp -> cyclehead = cyclenlp;
361: }
362: /*
363: * count calls from outside the cycle
364: * and those among cycle members
365: */
366: for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) {
367: for ( arcp=memberp->parents ; arcp ; arcp=arcp->arc_parentlist ) {
368: if ( arcp -> arc_parentp == memberp ) {
369: continue;
370: }
371: if ( arcp -> arc_parentp -> cycleno == cycle ) {
372: cyclenlp -> selfcalls += arcp -> arc_count;
373: } else {
374: cyclenlp -> ncall += arcp -> arc_count;
375: }
376: }
377: }
378: }
379: }
380:
381: cycletime()
382: {
383: int cycle;
384: nltype *cyclenlp;
385: nltype *childp;
386:
387: for ( cycle = 1 ; cycle <= ncycle ; cycle += 1 ) {
388: cyclenlp = &cyclenl[ cycle ];
389: for ( childp = cyclenlp -> cnext ; childp ; childp = childp -> cnext ) {
390: if ( childp -> propfraction == 0.0 ) {
391: /*
392: * all members have the same propfraction except those
393: * that were excluded with -E
394: */
395: continue;
396: }
397: cyclenlp -> time += childp -> time;
398: }
399: cyclenlp -> propself = cyclenlp -> propfraction * cyclenlp -> time;
400: }
401: }
402:
403: /*
404: * in one top to bottom pass over the topologically sorted namelist
405: * propagate:
406: * printflag as the union of parents' printflags
407: * propfraction as the sum of fractional parents' propfractions
408: * and while we're here, sum time for functions.
409: */
410: doflags()
411: {
412: int index;
413: nltype *childp;
414: nltype *oldhead;
415:
416: oldhead = 0;
417: for ( index = nname-1 ; index >= 0 ; index -= 1 ) {
418: childp = topsortnlp[ index ];
419: /*
420: * if we haven't done this function or cycle,
421: * inherit things from parent.
422: * this way, we are linear in the number of arcs
423: * since we do all members of a cycle (and the cycle itself)
424: * as we hit the first member of the cycle.
425: */
426: if ( childp -> cyclehead != oldhead ) {
427: oldhead = childp -> cyclehead;
428: inheritflags( childp );
429: }
430: # ifdef DEBUG
431: if ( debug & PROPDEBUG ) {
432: printf( "[doflags] " );
433: printname( childp );
434: printf( " inherits printflag %d and propfraction %f\n" ,
435: childp -> printflag , childp -> propfraction );
436: }
437: # endif DEBUG
438: if ( ! childp -> printflag ) {
439: /*
440: * printflag is off
441: * it gets turned on by
442: * being on -f list,
443: * or there not being any -f list and not being on -e list.
444: */
445: if ( onlist( flist , childp -> name )
446: || ( !fflag && !onlist( elist , childp -> name ) ) ) {
447: childp -> printflag = TRUE;
448: }
449: } else {
450: /*
451: * this function has printing parents:
452: * maybe someone wants to shut it up
453: * by putting it on -e list. (but favor -f over -e)
454: */
455: if ( ( !onlist( flist , childp -> name ) )
456: && onlist( elist , childp -> name ) ) {
457: childp -> printflag = FALSE;
458: }
459: }
460: if ( childp -> propfraction == 0.0 ) {
461: /*
462: * no parents to pass time to.
463: * collect time from children if
464: * its on -F list,
465: * or there isn't any -F list and its not on -E list.
466: */
467: if ( onlist( Flist , childp -> name )
468: || ( !Fflag && !onlist( Elist , childp -> name ) ) ) {
469: childp -> propfraction = 1.0;
470: }
471: } else {
472: /*
473: * it has parents to pass time to,
474: * but maybe someone wants to shut it up
475: * by puttting it on -E list. (but favor -F over -E)
476: */
477: if ( !onlist( Flist , childp -> name )
478: && onlist( Elist , childp -> name ) ) {
479: childp -> propfraction = 0.0;
480: }
481: }
482: childp -> propself = childp -> time * childp -> propfraction;
483: printtime += childp -> propself;
484: # ifdef DEBUG
485: if ( debug & PROPDEBUG ) {
486: printf( "[doflags] " );
487: printname( childp );
488: printf( " ends up with printflag %d and propfraction %f\n" ,
489: childp -> printflag , childp -> propfraction );
490: printf( "time %f propself %f printtime %f\n" ,
491: childp -> time , childp -> propself , printtime );
492: }
493: # endif DEBUG
494: }
495: }
496:
497: /*
498: * check if any parent of this child
499: * (or outside parents of this cycle)
500: * have their print flags on and set the
501: * print flag of the child (cycle) appropriately.
502: * similarly, deal with propagation fractions from parents.
503: */
504: inheritflags( childp )
505: nltype *childp;
506: {
507: nltype *headp;
508: arctype *arcp;
509: nltype *parentp;
510: nltype *memp;
511:
512: headp = childp -> cyclehead;
513: if ( childp == headp ) {
514: /*
515: * just a regular child, check its parents
516: */
517: childp -> printflag = FALSE;
518: childp -> propfraction = 0.0;
519: for (arcp = childp -> parents ; arcp ; arcp = arcp -> arc_parentlist) {
520: parentp = arcp -> arc_parentp;
521: if ( childp == parentp ) {
522: continue;
523: }
524: childp -> printflag |= parentp -> printflag;
525: /*
526: * if the child was never actually called
527: * (e.g. this arc is static (and all others are, too))
528: * no time propagates along this arc.
529: */
530: if ( childp -> ncall ) {
531: childp -> propfraction += parentp -> propfraction
532: * ( ( (double) arcp -> arc_count )
533: / ( (double) childp -> ncall ) );
534: }
535: }
536: } else {
537: /*
538: * its a member of a cycle, look at all parents from
539: * outside the cycle
540: */
541: headp -> printflag = FALSE;
542: headp -> propfraction = 0.0;
543: for ( memp = headp -> cnext ; memp ; memp = memp -> cnext ) {
544: for (arcp = memp->parents ; arcp ; arcp = arcp->arc_parentlist) {
545: if ( arcp -> arc_parentp -> cyclehead == headp ) {
546: continue;
547: }
548: parentp = arcp -> arc_parentp;
549: headp -> printflag |= parentp -> printflag;
550: /*
551: * if the cycle was never actually called
552: * (e.g. this arc is static (and all others are, too))
553: * no time propagates along this arc.
554: */
555: if ( headp -> ncall ) {
556: headp -> propfraction += parentp -> propfraction
557: * ( ( (double) arcp -> arc_count )
558: / ( (double) headp -> ncall ) );
559: }
560: }
561: }
562: for ( memp = headp ; memp ; memp = memp -> cnext ) {
563: memp -> printflag = headp -> printflag;
564: memp -> propfraction = headp -> propfraction;
565: }
566: }
567: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.