Commit | Line | Data |
---|---|---|
ca41b3be | 1 | #ifndef lint |
80ebf400 | 2 | static char *sccsid = "@(#)arcs.c 1.13 (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; |
80ebf400 | 96 | parentp -> toporder = DFN_NAN; |
ca41b3be PK |
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 | |
80ebf400 PK |
106 | * if any node is unnumbered, |
107 | * number it and any of its descendents. | |
ca41b3be PK |
108 | */ |
109 | for ( parentp = nl ; parentp < npe ; parentp++ ) { | |
80ebf400 | 110 | if ( parentp -> toporder == DFN_NAN ) { |
ca41b3be PK |
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 | |
7ec9eedc PK |
140 | /* |
141 | * starting from the topological top, | |
142 | * propagate print flags to children. | |
a441395b PK |
143 | * also, calculate propagation fractions. |
144 | * this happens before time propagation | |
145 | * since time propagation uses the fractions. | |
ca41b3be | 146 | */ |
7ec9eedc | 147 | doflags(); |
a441395b PK |
148 | /* |
149 | * starting from the topological bottom, | |
150 | * propogate children times up to parents. | |
151 | */ | |
152 | dotime(); | |
7ec9eedc PK |
153 | printgprof(); |
154 | } | |
155 | ||
156 | dotime() | |
157 | { | |
158 | int index; | |
159 | ||
160 | cycletime(); | |
ca41b3be | 161 | for ( index = 0 ; index < nname ; index += 1 ) { |
7ec9eedc | 162 | timepropagate( topsortnlp[ index ] ); |
ad3b82ad | 163 | } |
ad3b82ad PK |
164 | } |
165 | ||
7ec9eedc | 166 | timepropagate( parentp ) |
ad3b82ad PK |
167 | nltype *parentp; |
168 | { | |
169 | arctype *arcp; | |
170 | nltype *childp; | |
171 | double share; | |
a441395b | 172 | double propshare; |
ad3b82ad | 173 | |
a441395b PK |
174 | if ( parentp -> propfraction == 0.0 ) { |
175 | return; | |
176 | } | |
ad3b82ad PK |
177 | /* |
178 | * gather time from children of this parent. | |
179 | */ | |
7ec9eedc | 180 | for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) { |
ad3b82ad | 181 | childp = arcp -> arc_childp; |
ad3b82ad PK |
182 | if ( arcp -> arc_count == 0 ) { |
183 | continue; | |
184 | } | |
a441395b | 185 | if ( childp == parentp ) { |
ad3b82ad PK |
186 | continue; |
187 | } | |
a441395b | 188 | if ( childp -> propfraction == 0.0 ) { |
ad3b82ad PK |
189 | continue; |
190 | } | |
191 | if ( childp -> cyclehead != childp ) { | |
192 | if ( parentp -> cycleno == childp -> cycleno ) { | |
193 | continue; | |
194 | } | |
ad3b82ad PK |
195 | if ( parentp -> toporder <= childp -> toporder ) { |
196 | fprintf( stderr , "[propagate] toporder botches\n" ); | |
ca41b3be | 197 | } |
ad3b82ad PK |
198 | childp = childp -> cyclehead; |
199 | } else { | |
200 | if ( parentp -> toporder <= childp -> toporder ) { | |
201 | fprintf( stderr , "[propagate] toporder botches\n" ); | |
ca41b3be PK |
202 | continue; |
203 | } | |
a441395b PK |
204 | } |
205 | if ( childp -> ncall == 0 ) { | |
206 | continue; | |
ad3b82ad PK |
207 | } |
208 | /* | |
209 | * distribute time for this arc | |
210 | */ | |
a441395b PK |
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 ) ); | |
ad3b82ad | 217 | share = arcp -> arc_time + arcp -> arc_childtime; |
ad3b82ad PK |
218 | parentp -> childtime += share; |
219 | /* | |
a441395b PK |
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. | |
ad3b82ad PK |
231 | */ |
232 | if ( parentp -> cyclehead != parentp ) { | |
ad3b82ad | 233 | parentp -> cyclehead -> childtime += share; |
a441395b | 234 | parentp -> cyclehead -> propchild += propshare; |
ca41b3be | 235 | } |
a441395b PK |
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 | |
ca41b3be | 248 | } |
ca41b3be PK |
249 | } |
250 | ||
251 | cyclelink() | |
252 | { | |
253 | register nltype *nlp; | |
ca41b3be PK |
254 | register nltype *cyclenlp; |
255 | int cycle; | |
7ec9eedc | 256 | nltype *memberp; |
fb403b71 | 257 | arctype *arcp; |
ca41b3be PK |
258 | |
259 | /* | |
260 | * Count the number of cycles, and initialze the cycle lists | |
261 | */ | |
ad3b82ad | 262 | ncycle = 0; |
ca41b3be PK |
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 ) { | |
ad3b82ad | 268 | ncycle += 1; |
ca41b3be PK |
269 | } |
270 | } | |
ad3b82ad PK |
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(); | |
ca41b3be PK |
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++ ) { | |
80ebf400 | 287 | if ( !( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) ) { |
ca41b3be PK |
288 | continue; |
289 | } | |
290 | cycle += 1; | |
ad3b82ad | 291 | cyclenlp = &cyclenl[cycle]; |
149140d5 | 292 | cyclenlp -> name = 0; /* the name */ |
a441395b PK |
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 */ | |
80ebf400 | 303 | cyclenlp -> toporder = DFN_NAN; /* graph call chain top-sort order */ |
a441395b PK |
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 */ | |
ca41b3be PK |
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 | |
fb403b71 PK |
316 | /* |
317 | * link members to cycle header | |
318 | */ | |
7ec9eedc PK |
319 | for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) { |
320 | memberp -> cycleno = cycle; | |
321 | memberp -> cyclehead = cyclenlp; | |
322 | } | |
fb403b71 PK |
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 | } | |
7ec9eedc PK |
339 | } |
340 | } | |
341 | ||
342 | cycletime() | |
343 | { | |
344 | int cycle; | |
345 | nltype *cyclenlp; | |
7ec9eedc | 346 | nltype *childp; |
7ec9eedc PK |
347 | |
348 | for ( cycle = 1 ; cycle <= ncycle ; cycle += 1 ) { | |
349 | cyclenlp = &cyclenl[ cycle ]; | |
a441395b PK |
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; | |
ca41b3be | 359 | } |
a441395b | 360 | cyclenlp -> propself = cyclenlp -> propfraction * cyclenlp -> time; |
ca41b3be PK |
361 | } |
362 | } | |
7ec9eedc PK |
363 | |
364 | /* | |
365 | * in one top to bottom pass over the topologically sorted namelist | |
a441395b PK |
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. | |
7ec9eedc PK |
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, | |
a441395b | 382 | * inherit things from parent. |
7ec9eedc PK |
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; | |
a441395b | 389 | inheritflags( childp ); |
7ec9eedc | 390 | } |
a441395b PK |
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 | |
7ec9eedc PK |
399 | if ( ! childp -> printflag ) { |
400 | /* | |
a441395b PK |
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. | |
7ec9eedc | 405 | */ |
a441395b PK |
406 | if ( onlist( flist , childp -> name ) |
407 | || ( !fflag && !onlist( elist , childp -> name ) ) ) { | |
7ec9eedc | 408 | childp -> printflag = TRUE; |
7ec9eedc | 409 | } |
a441395b PK |
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; | |
7ec9eedc | 419 | } |
7ec9eedc | 420 | } |
a441395b PK |
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 | } | |
7ec9eedc | 442 | } |
a441395b PK |
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 ); | |
80a80acc PK |
451 | printf( "time %f propself %f printtime %f\n" , |
452 | childp -> time , childp -> propself , printtime ); | |
a441395b PK |
453 | } |
454 | # endif DEBUG | |
7ec9eedc PK |
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. | |
a441395b | 463 | * similarly, deal with propagation fractions from parents. |
7ec9eedc | 464 | */ |
a441395b | 465 | inheritflags( childp ) |
7ec9eedc PK |
466 | nltype *childp; |
467 | { | |
468 | nltype *headp; | |
7ec9eedc | 469 | arctype *arcp; |
a441395b PK |
470 | nltype *parentp; |
471 | nltype *memp; | |
7ec9eedc PK |
472 | |
473 | headp = childp -> cyclehead; | |
474 | if ( childp == headp ) { | |
475 | /* | |
476 | * just a regular child, check its parents | |
477 | */ | |
a441395b PK |
478 | childp -> printflag = FALSE; |
479 | childp -> propfraction = 0.0; | |
480 | for (arcp = childp -> parents ; arcp ; arcp = arcp -> arc_parentlist) { | |
481 | parentp = arcp -> arc_parentp; | |
80a80acc PK |
482 | if ( childp == parentp ) { |
483 | continue; | |
484 | } | |
a441395b PK |
485 | childp -> printflag |= parentp -> printflag; |
486 | childp -> propfraction += parentp -> propfraction | |
487 | * ( ( (double) arcp -> arc_count ) | |
fb403b71 | 488 | / ( (double) childp -> ncall ) ); |
7ec9eedc | 489 | } |
a441395b PK |
490 | } else { |
491 | /* | |
492 | * its a member of a cycle, look at all parents from | |
493 | * outside the cycle | |
494 | */ | |
495 | headp -> printflag = FALSE; | |
496 | headp -> propfraction = 0.0; | |
497 | for ( memp = headp -> cnext ; memp ; memp = memp -> cnext ) { | |
498 | for (arcp = memp->parents ; arcp ; arcp = arcp->arc_parentlist) { | |
499 | if ( arcp -> arc_parentp -> cyclehead == headp ) { | |
500 | continue; | |
501 | } | |
502 | parentp = arcp -> arc_parentp; | |
503 | headp -> printflag |= parentp -> printflag; | |
fb403b71 PK |
504 | headp -> propfraction += parentp -> propfraction |
505 | * ( ( (double) arcp -> arc_count ) | |
506 | / ( (double) headp -> ncall ) ); | |
7ec9eedc PK |
507 | } |
508 | } | |
a441395b PK |
509 | for ( memp = headp ; memp ; memp = memp -> cnext ) { |
510 | memp -> printflag = headp -> printflag; | |
511 | memp -> propfraction = headp -> propfraction; | |
512 | } | |
7ec9eedc PK |
513 | } |
514 | } |