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