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