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