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