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