Commit | Line | Data |
---|---|---|
c0bc4ef7 | 1 | /* |
7e9de516 KB |
2 | * Copyright (c) 1983, 1993 |
3 | * The Regents of the University of California. All rights reserved. | |
ddb85eed | 4 | * |
6ecf3d85 | 5 | * %sccs.include.redist.c% |
c0bc4ef7 DF |
6 | */ |
7 | ||
ca41b3be | 8 | #ifndef lint |
7e9de516 | 9 | static char sccsid[] = "@(#)arcs.c 8.1 (Berkeley) %G%"; |
ddb85eed | 10 | #endif /* not lint */ |
ca41b3be | 11 | |
31f0a970 | 12 | #include "gprof.h" |
ca41b3be | 13 | |
91541716 KM |
14 | #ifdef DEBUG |
15 | int visited; | |
16 | int viable; | |
17 | int newcycle; | |
18 | int oldcycle; | |
19 | #endif DEBUG | |
20 | ||
29da1d26 PK |
21 | /* |
22 | * add (or just increment) an arc | |
23 | */ | |
24 | addarc( parentp , childp , count ) | |
25 | nltype *parentp; | |
26 | nltype *childp; | |
27 | long count; | |
28 | { | |
29da1d26 PK |
29 | arctype *arcp; |
30 | ||
31 | # ifdef DEBUG | |
32 | if ( debug & TALLYDEBUG ) { | |
33 | printf( "[addarc] %d arcs from %s to %s\n" , | |
34 | count , parentp -> name , childp -> name ); | |
35 | } | |
36 | # endif DEBUG | |
37 | arcp = arclookup( parentp , childp ); | |
38 | if ( arcp != 0 ) { | |
39 | /* | |
40 | * a hit: just increment the count. | |
41 | */ | |
42 | # ifdef DEBUG | |
43 | if ( debug & TALLYDEBUG ) { | |
44 | printf( "[tally] hit %d += %d\n" , | |
45 | arcp -> arc_count , count ); | |
46 | } | |
47 | # endif DEBUG | |
48 | arcp -> arc_count += count; | |
49 | return; | |
50 | } | |
4dbb4bf2 | 51 | arcp = (arctype *)calloc( 1 , sizeof *arcp ); |
29da1d26 PK |
52 | arcp -> arc_parentp = parentp; |
53 | arcp -> arc_childp = childp; | |
54 | arcp -> arc_count = count; | |
55 | /* | |
56 | * prepend this child to the children of this parent | |
57 | */ | |
58 | arcp -> arc_childlist = parentp -> children; | |
59 | parentp -> children = arcp; | |
60 | /* | |
61 | * prepend this parent to the parents of this child | |
62 | */ | |
63 | arcp -> arc_parentlist = childp -> parents; | |
64 | childp -> parents = arcp; | |
65 | } | |
66 | ||
7ec9eedc PK |
67 | /* |
68 | * the code below topologically sorts the graph (collapsing cycles), | |
69 | * and propagates time bottom up and flags top down. | |
70 | */ | |
71 | ||
72 | /* | |
73 | * the topologically sorted name list pointers | |
74 | */ | |
75 | nltype **topsortnlp; | |
76 | ||
ca41b3be PK |
77 | topcmp( npp1 , npp2 ) |
78 | nltype **npp1; | |
79 | nltype **npp2; | |
80 | { | |
81 | return (*npp1) -> toporder - (*npp2) -> toporder; | |
82 | } | |
83 | ||
072ff9b6 | 84 | nltype ** |
ca41b3be PK |
85 | doarcs() |
86 | { | |
072ff9b6 | 87 | nltype *parentp, **timesortnlp; |
ca41b3be | 88 | arctype *arcp; |
ca41b3be | 89 | long index; |
91541716 | 90 | long pass; |
ca41b3be PK |
91 | |
92 | /* | |
93 | * initialize various things: | |
94 | * zero out child times. | |
95 | * count self-recursive calls. | |
96 | * indicate that nothing is on cycles. | |
97 | */ | |
98 | for ( parentp = nl ; parentp < npe ; parentp++ ) { | |
99 | parentp -> childtime = 0.0; | |
100 | arcp = arclookup( parentp , parentp ); | |
101 | if ( arcp != 0 ) { | |
102 | parentp -> ncall -= arcp -> arc_count; | |
103 | parentp -> selfcalls = arcp -> arc_count; | |
104 | } else { | |
105 | parentp -> selfcalls = 0; | |
106 | } | |
91541716 | 107 | parentp -> npropcall = parentp -> ncall; |
a441395b PK |
108 | parentp -> propfraction = 0.0; |
109 | parentp -> propself = 0.0; | |
110 | parentp -> propchild = 0.0; | |
7ec9eedc | 111 | parentp -> printflag = FALSE; |
80ebf400 | 112 | parentp -> toporder = DFN_NAN; |
ca41b3be PK |
113 | parentp -> cycleno = 0; |
114 | parentp -> cyclehead = parentp; | |
115 | parentp -> cnext = 0; | |
7ec9eedc | 116 | if ( cflag ) { |
da50c4dd | 117 | findcall( parentp , parentp -> value , (parentp+1) -> value ); |
7ec9eedc | 118 | } |
ca41b3be | 119 | } |
91541716 KM |
120 | for ( pass = 1 ; ; pass++ ) { |
121 | /* | |
122 | * topologically order things | |
123 | * if any node is unnumbered, | |
124 | * number it and any of its descendents. | |
125 | */ | |
126 | for ( dfn_init() , parentp = nl ; parentp < npe ; parentp++ ) { | |
127 | if ( parentp -> toporder == DFN_NAN ) { | |
128 | dfn( parentp ); | |
129 | } | |
130 | } | |
131 | /* | |
132 | * link together nodes on the same cycle | |
133 | */ | |
134 | cyclelink(); | |
135 | /* | |
136 | * if no cycles to break up, proceed | |
137 | */ | |
138 | if ( ! Cflag ) | |
139 | break; | |
140 | /* | |
141 | * analyze cycles to determine breakup | |
142 | */ | |
143 | # ifdef DEBUG | |
144 | if ( debug & BREAKCYCLE ) { | |
145 | printf("[doarcs] pass %d, cycle(s) %d\n" , pass , ncycle ); | |
146 | } | |
147 | # endif DEBUG | |
148 | if ( pass == 1 ) { | |
149 | printf( "\n\n%s %s\n%s %d:\n" , | |
150 | "The following arcs were deleted" , | |
151 | "from the propagation calculation" , | |
152 | "to reduce the maximum cycle size to", cyclethreshold ); | |
153 | } | |
154 | if ( cycleanalyze() ) | |
155 | break; | |
156 | free ( cyclenl ); | |
157 | ncycle = 0; | |
158 | for ( parentp = nl ; parentp < npe ; parentp++ ) { | |
159 | parentp -> toporder = DFN_NAN; | |
160 | parentp -> cycleno = 0; | |
161 | parentp -> cyclehead = parentp; | |
162 | parentp -> cnext = 0; | |
ca41b3be PK |
163 | } |
164 | } | |
91541716 KM |
165 | if ( pass > 1 ) { |
166 | printf( "\f\n" ); | |
167 | } else { | |
168 | printf( "\tNone\n\n" ); | |
169 | } | |
ca41b3be PK |
170 | /* |
171 | * Sort the symbol table in reverse topological order | |
172 | */ | |
173 | topsortnlp = (nltype **) calloc( nname , sizeof(nltype *) ); | |
174 | if ( topsortnlp == (nltype **) 0 ) { | |
175 | fprintf( stderr , "[doarcs] ran out of memory for topo sorting\n" ); | |
176 | } | |
177 | for ( index = 0 ; index < nname ; index += 1 ) { | |
178 | topsortnlp[ index ] = &nl[ index ]; | |
179 | } | |
180 | qsort( topsortnlp , nname , sizeof(nltype *) , topcmp ); | |
181 | # ifdef DEBUG | |
182 | if ( debug & DFNDEBUG ) { | |
183 | printf( "[doarcs] topological sort listing\n" ); | |
184 | for ( index = 0 ; index < nname ; index += 1 ) { | |
185 | printf( "[doarcs] " ); | |
186 | printf( "%d:" , topsortnlp[ index ] -> toporder ); | |
187 | printname( topsortnlp[ index ] ); | |
188 | printf( "\n" ); | |
189 | } | |
190 | } | |
191 | # endif DEBUG | |
7ec9eedc PK |
192 | /* |
193 | * starting from the topological top, | |
194 | * propagate print flags to children. | |
a441395b PK |
195 | * also, calculate propagation fractions. |
196 | * this happens before time propagation | |
197 | * since time propagation uses the fractions. | |
ca41b3be | 198 | */ |
7ec9eedc | 199 | doflags(); |
a441395b PK |
200 | /* |
201 | * starting from the topological bottom, | |
202 | * propogate children times up to parents. | |
203 | */ | |
204 | dotime(); | |
072ff9b6 KM |
205 | /* |
206 | * Now, sort by propself + propchild. | |
207 | * sorting both the regular function names | |
208 | * and cycle headers. | |
209 | */ | |
210 | timesortnlp = (nltype **) calloc( nname + ncycle , sizeof(nltype *) ); | |
211 | if ( timesortnlp == (nltype **) 0 ) { | |
212 | fprintf( stderr , "%s: ran out of memory for sorting\n" , whoami ); | |
213 | } | |
214 | for ( index = 0 ; index < nname ; index++ ) { | |
215 | timesortnlp[index] = &nl[index]; | |
216 | } | |
217 | for ( index = 1 ; index <= ncycle ; index++ ) { | |
218 | timesortnlp[nname+index-1] = &cyclenl[index]; | |
219 | } | |
220 | qsort( timesortnlp , nname + ncycle , sizeof(nltype *) , totalcmp ); | |
221 | for ( index = 0 ; index < nname + ncycle ; index++ ) { | |
222 | timesortnlp[ index ] -> index = index + 1; | |
223 | } | |
224 | return( timesortnlp ); | |
7ec9eedc PK |
225 | } |
226 | ||
227 | dotime() | |
228 | { | |
229 | int index; | |
230 | ||
231 | cycletime(); | |
ca41b3be | 232 | for ( index = 0 ; index < nname ; index += 1 ) { |
7ec9eedc | 233 | timepropagate( topsortnlp[ index ] ); |
ad3b82ad | 234 | } |
ad3b82ad PK |
235 | } |
236 | ||
7ec9eedc | 237 | timepropagate( parentp ) |
ad3b82ad PK |
238 | nltype *parentp; |
239 | { | |
240 | arctype *arcp; | |
241 | nltype *childp; | |
242 | double share; | |
a441395b | 243 | double propshare; |
ad3b82ad | 244 | |
a441395b PK |
245 | if ( parentp -> propfraction == 0.0 ) { |
246 | return; | |
247 | } | |
ad3b82ad PK |
248 | /* |
249 | * gather time from children of this parent. | |
250 | */ | |
7ec9eedc | 251 | for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) { |
ad3b82ad | 252 | childp = arcp -> arc_childp; |
91541716 KM |
253 | if ( arcp -> arc_flags & DEADARC ) { |
254 | continue; | |
255 | } | |
ad3b82ad PK |
256 | if ( arcp -> arc_count == 0 ) { |
257 | continue; | |
258 | } | |
a441395b | 259 | if ( childp == parentp ) { |
ad3b82ad PK |
260 | continue; |
261 | } | |
a441395b | 262 | if ( childp -> propfraction == 0.0 ) { |
ad3b82ad PK |
263 | continue; |
264 | } | |
265 | if ( childp -> cyclehead != childp ) { | |
266 | if ( parentp -> cycleno == childp -> cycleno ) { | |
267 | continue; | |
268 | } | |
ad3b82ad PK |
269 | if ( parentp -> toporder <= childp -> toporder ) { |
270 | fprintf( stderr , "[propagate] toporder botches\n" ); | |
ca41b3be | 271 | } |
ad3b82ad PK |
272 | childp = childp -> cyclehead; |
273 | } else { | |
274 | if ( parentp -> toporder <= childp -> toporder ) { | |
275 | fprintf( stderr , "[propagate] toporder botches\n" ); | |
ca41b3be PK |
276 | continue; |
277 | } | |
a441395b | 278 | } |
91541716 | 279 | if ( childp -> npropcall == 0 ) { |
a441395b | 280 | continue; |
ad3b82ad PK |
281 | } |
282 | /* | |
283 | * distribute time for this arc | |
284 | */ | |
a441395b PK |
285 | arcp -> arc_time = childp -> time |
286 | * ( ( (double) arcp -> arc_count ) / | |
91541716 | 287 | ( (double) childp -> npropcall ) ); |
a441395b PK |
288 | arcp -> arc_childtime = childp -> childtime |
289 | * ( ( (double) arcp -> arc_count ) / | |
91541716 | 290 | ( (double) childp -> npropcall ) ); |
ad3b82ad | 291 | share = arcp -> arc_time + arcp -> arc_childtime; |
ad3b82ad PK |
292 | parentp -> childtime += share; |
293 | /* | |
a441395b PK |
294 | * ( 1 - propfraction ) gets lost along the way |
295 | */ | |
296 | propshare = parentp -> propfraction * share; | |
297 | /* | |
298 | * fix things for printing | |
299 | */ | |
300 | parentp -> propchild += propshare; | |
301 | arcp -> arc_time *= parentp -> propfraction; | |
302 | arcp -> arc_childtime *= parentp -> propfraction; | |
303 | /* | |
304 | * add this share to the parent's cycle header, if any. | |
ad3b82ad PK |
305 | */ |
306 | if ( parentp -> cyclehead != parentp ) { | |
ad3b82ad | 307 | parentp -> cyclehead -> childtime += share; |
a441395b | 308 | parentp -> cyclehead -> propchild += propshare; |
ca41b3be | 309 | } |
a441395b PK |
310 | # ifdef DEBUG |
311 | if ( debug & PROPDEBUG ) { | |
312 | printf( "[dotime] child \t" ); | |
313 | printname( childp ); | |
314 | printf( " with %f %f %d/%d\n" , | |
315 | childp -> time , childp -> childtime , | |
91541716 | 316 | arcp -> arc_count , childp -> npropcall ); |
a441395b PK |
317 | printf( "[dotime] parent\t" ); |
318 | printname( parentp ); | |
319 | printf( "\n[dotime] share %f\n" , share ); | |
320 | } | |
321 | # endif DEBUG | |
ca41b3be | 322 | } |
ca41b3be PK |
323 | } |
324 | ||
325 | cyclelink() | |
326 | { | |
327 | register nltype *nlp; | |
ca41b3be PK |
328 | register nltype *cyclenlp; |
329 | int cycle; | |
7ec9eedc | 330 | nltype *memberp; |
fb403b71 | 331 | arctype *arcp; |
ca41b3be PK |
332 | |
333 | /* | |
334 | * Count the number of cycles, and initialze the cycle lists | |
335 | */ | |
ad3b82ad | 336 | ncycle = 0; |
ca41b3be PK |
337 | for ( nlp = nl ; nlp < npe ; nlp++ ) { |
338 | /* | |
339 | * this is how you find unattached cycles | |
340 | */ | |
341 | if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) { | |
ad3b82ad | 342 | ncycle += 1; |
ca41b3be PK |
343 | } |
344 | } | |
ad3b82ad PK |
345 | /* |
346 | * cyclenl is indexed by cycle number: | |
347 | * i.e. it is origin 1, not origin 0. | |
348 | */ | |
349 | cyclenl = (nltype *) calloc( ncycle + 1 , sizeof( nltype ) ); | |
350 | if ( cyclenl == 0 ) { | |
351 | fprintf( stderr , "%s: No room for %d bytes of cycle headers\n" , | |
352 | whoami , ( ncycle + 1 ) * sizeof( nltype ) ); | |
353 | done(); | |
ca41b3be PK |
354 | } |
355 | /* | |
356 | * now link cycles to true cycleheads, | |
357 | * number them, accumulate the data for the cycle | |
358 | */ | |
359 | cycle = 0; | |
360 | for ( nlp = nl ; nlp < npe ; nlp++ ) { | |
80ebf400 | 361 | if ( !( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) ) { |
ca41b3be PK |
362 | continue; |
363 | } | |
364 | cycle += 1; | |
ad3b82ad | 365 | cyclenlp = &cyclenl[cycle]; |
149140d5 | 366 | cyclenlp -> name = 0; /* the name */ |
a441395b PK |
367 | cyclenlp -> value = 0; /* the pc entry point */ |
368 | cyclenlp -> time = 0.0; /* ticks in this routine */ | |
369 | cyclenlp -> childtime = 0.0; /* cumulative ticks in children */ | |
370 | cyclenlp -> ncall = 0; /* how many times called */ | |
371 | cyclenlp -> selfcalls = 0; /* how many calls to self */ | |
372 | cyclenlp -> propfraction = 0.0; /* what % of time propagates */ | |
373 | cyclenlp -> propself = 0.0; /* how much self time propagates */ | |
374 | cyclenlp -> propchild = 0.0; /* how much child time propagates */ | |
375 | cyclenlp -> printflag = TRUE; /* should this be printed? */ | |
376 | cyclenlp -> index = 0; /* index in the graph list */ | |
80ebf400 | 377 | cyclenlp -> toporder = DFN_NAN; /* graph call chain top-sort order */ |
a441395b PK |
378 | cyclenlp -> cycleno = cycle; /* internal number of cycle on */ |
379 | cyclenlp -> cyclehead = cyclenlp; /* pointer to head of cycle */ | |
380 | cyclenlp -> cnext = nlp; /* pointer to next member of cycle */ | |
381 | cyclenlp -> parents = 0; /* list of caller arcs */ | |
382 | cyclenlp -> children = 0; /* list of callee arcs */ | |
ca41b3be PK |
383 | # ifdef DEBUG |
384 | if ( debug & CYCLEDEBUG ) { | |
385 | printf( "[cyclelink] " ); | |
386 | printname( nlp ); | |
387 | printf( " is the head of cycle %d\n" , cycle ); | |
388 | } | |
389 | # endif DEBUG | |
fb403b71 PK |
390 | /* |
391 | * link members to cycle header | |
392 | */ | |
7ec9eedc PK |
393 | for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) { |
394 | memberp -> cycleno = cycle; | |
395 | memberp -> cyclehead = cyclenlp; | |
396 | } | |
fb403b71 PK |
397 | /* |
398 | * count calls from outside the cycle | |
399 | * and those among cycle members | |
400 | */ | |
401 | for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) { | |
402 | for ( arcp=memberp->parents ; arcp ; arcp=arcp->arc_parentlist ) { | |
403 | if ( arcp -> arc_parentp == memberp ) { | |
404 | continue; | |
405 | } | |
406 | if ( arcp -> arc_parentp -> cycleno == cycle ) { | |
407 | cyclenlp -> selfcalls += arcp -> arc_count; | |
408 | } else { | |
91541716 | 409 | cyclenlp -> npropcall += arcp -> arc_count; |
fb403b71 PK |
410 | } |
411 | } | |
412 | } | |
7ec9eedc PK |
413 | } |
414 | } | |
415 | ||
91541716 KM |
416 | /* |
417 | * analyze cycles to determine breakup | |
418 | */ | |
419 | cycleanalyze() | |
420 | { | |
421 | arctype **cyclestack; | |
422 | arctype **stkp; | |
423 | arctype **arcpp; | |
424 | arctype **endlist; | |
425 | arctype *arcp; | |
426 | nltype *nlp; | |
427 | cltype *clp; | |
428 | bool ret; | |
429 | bool done; | |
430 | int size; | |
431 | int cycleno; | |
432 | ||
433 | /* | |
434 | * calculate the size of the cycle, and find nodes that | |
435 | * exit the cycle as they are desirable targets to cut | |
436 | * some of their parents | |
437 | */ | |
438 | for ( done = TRUE , cycleno = 1 ; cycleno <= ncycle ; cycleno++ ) { | |
439 | size = 0; | |
440 | for (nlp = cyclenl[ cycleno ] . cnext; nlp; nlp = nlp -> cnext) { | |
441 | size += 1; | |
442 | nlp -> parentcnt = 0; | |
443 | nlp -> flags &= ~HASCYCLEXIT; | |
444 | for ( arcp = nlp -> parents; arcp; arcp = arcp -> arc_parentlist ) { | |
445 | nlp -> parentcnt += 1; | |
446 | if ( arcp -> arc_parentp -> cycleno != cycleno ) | |
447 | nlp -> flags |= HASCYCLEXIT; | |
448 | } | |
449 | } | |
450 | if ( size <= cyclethreshold ) | |
451 | continue; | |
452 | done = FALSE; | |
453 | cyclestack = (arctype **) calloc( size + 1 , sizeof( arctype *) ); | |
454 | if ( cyclestack == 0 ) { | |
455 | fprintf( stderr , "%s: No room for %d bytes of cycle stack\n" , | |
456 | whoami , ( size + 1 ) * sizeof( arctype * ) ); | |
457 | return; | |
458 | } | |
459 | # ifdef DEBUG | |
460 | if ( debug & BREAKCYCLE ) { | |
461 | printf( "[cycleanalyze] starting cycle %d of %d, size %d\n" , | |
462 | cycleno , ncycle , size ); | |
463 | } | |
464 | # endif DEBUG | |
465 | for ( nlp = cyclenl[ cycleno ] . cnext ; nlp ; nlp = nlp -> cnext ) { | |
466 | stkp = &cyclestack[0]; | |
467 | nlp -> flags |= CYCLEHEAD; | |
468 | ret = descend ( nlp , cyclestack , stkp ); | |
469 | nlp -> flags &= ~CYCLEHEAD; | |
470 | if ( ret == FALSE ) | |
471 | break; | |
472 | } | |
473 | free( cyclestack ); | |
474 | if ( cyclecnt > 0 ) { | |
475 | compresslist(); | |
476 | for ( clp = cyclehead ; clp ; ) { | |
477 | endlist = &clp -> list[ clp -> size ]; | |
478 | for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) | |
479 | (*arcpp) -> arc_cyclecnt--; | |
480 | cyclecnt--; | |
481 | clp = clp -> next; | |
482 | free( clp ); | |
483 | } | |
484 | cyclehead = 0; | |
485 | } | |
486 | } | |
487 | # ifdef DEBUG | |
488 | if ( debug & BREAKCYCLE ) { | |
489 | printf("%s visited %d, viable %d, newcycle %d, oldcycle %d\n", | |
490 | "[doarcs]" , visited , viable , newcycle , oldcycle); | |
491 | } | |
492 | # endif DEBUG | |
493 | return( done ); | |
494 | } | |
495 | ||
496 | descend( node , stkstart , stkp ) | |
497 | nltype *node; | |
498 | arctype **stkstart; | |
499 | arctype **stkp; | |
500 | { | |
501 | arctype *arcp; | |
502 | bool ret; | |
503 | ||
504 | for ( arcp = node -> children ; arcp ; arcp = arcp -> arc_childlist ) { | |
505 | # ifdef DEBUG | |
506 | visited++; | |
507 | # endif DEBUG | |
508 | if ( arcp -> arc_childp -> cycleno != node -> cycleno | |
509 | || ( arcp -> arc_childp -> flags & VISITED ) | |
510 | || ( arcp -> arc_flags & DEADARC ) ) | |
511 | continue; | |
512 | # ifdef DEBUG | |
513 | viable++; | |
514 | # endif DEBUG | |
515 | *stkp = arcp; | |
516 | if ( arcp -> arc_childp -> flags & CYCLEHEAD ) { | |
517 | if ( addcycle( stkstart , stkp ) == FALSE ) | |
518 | return( FALSE ); | |
519 | continue; | |
520 | } | |
521 | arcp -> arc_childp -> flags |= VISITED; | |
522 | ret = descend( arcp -> arc_childp , stkstart , stkp + 1 ); | |
523 | arcp -> arc_childp -> flags &= ~VISITED; | |
524 | if ( ret == FALSE ) | |
525 | return( FALSE ); | |
526 | } | |
527 | } | |
528 | ||
529 | addcycle( stkstart , stkend ) | |
530 | arctype **stkstart; | |
531 | arctype **stkend; | |
532 | { | |
533 | arctype **arcpp; | |
534 | arctype **stkloc; | |
535 | arctype **stkp; | |
536 | arctype **endlist; | |
537 | arctype *minarc; | |
538 | arctype *arcp; | |
539 | cltype *clp; | |
540 | int size; | |
541 | ||
542 | size = stkend - stkstart + 1; | |
543 | if ( size <= 1 ) | |
544 | return( TRUE ); | |
545 | for ( arcpp = stkstart , minarc = *arcpp ; arcpp <= stkend ; arcpp++ ) { | |
546 | if ( *arcpp > minarc ) | |
547 | continue; | |
548 | minarc = *arcpp; | |
549 | stkloc = arcpp; | |
550 | } | |
551 | for ( clp = cyclehead ; clp ; clp = clp -> next ) { | |
552 | if ( clp -> size != size ) | |
553 | continue; | |
554 | stkp = stkloc; | |
555 | endlist = &clp -> list[ size ]; | |
556 | for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) { | |
557 | if ( *stkp++ != *arcpp ) | |
558 | break; | |
559 | if ( stkp > stkend ) | |
560 | stkp = stkstart; | |
561 | } | |
562 | if ( arcpp == endlist ) { | |
563 | # ifdef DEBUG | |
564 | oldcycle++; | |
565 | # endif DEBUG | |
566 | return( TRUE ); | |
567 | } | |
568 | } | |
569 | clp = (cltype *) | |
570 | calloc( 1 , sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) ); | |
571 | if ( clp == 0 ) { | |
572 | fprintf( stderr , "%s: No room for %d bytes of subcycle storage\n" , | |
573 | whoami , sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) ); | |
574 | return( FALSE ); | |
575 | } | |
576 | stkp = stkloc; | |
577 | endlist = &clp -> list[ size ]; | |
578 | for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) { | |
579 | arcp = *arcpp = *stkp++; | |
580 | if ( stkp > stkend ) | |
581 | stkp = stkstart; | |
582 | arcp -> arc_cyclecnt++; | |
583 | if ( ( arcp -> arc_flags & ONLIST ) == 0 ) { | |
584 | arcp -> arc_flags |= ONLIST; | |
585 | arcp -> arc_next = archead; | |
586 | archead = arcp; | |
587 | } | |
588 | } | |
589 | clp -> size = size; | |
590 | clp -> next = cyclehead; | |
591 | cyclehead = clp; | |
592 | # ifdef DEBUG | |
593 | newcycle++; | |
594 | if ( debug & SUBCYCLELIST ) { | |
595 | printsubcycle( clp ); | |
596 | } | |
597 | # endif DEBUG | |
598 | cyclecnt++; | |
599 | if ( cyclecnt >= CYCLEMAX ) | |
600 | return( FALSE ); | |
601 | return( TRUE ); | |
602 | } | |
603 | ||
604 | compresslist() | |
605 | { | |
606 | cltype *clp; | |
607 | cltype **prev; | |
608 | arctype **arcpp; | |
609 | arctype **endlist; | |
610 | arctype *arcp; | |
611 | arctype *maxarcp; | |
612 | arctype *maxexitarcp; | |
613 | arctype *maxwithparentarcp; | |
614 | arctype *maxnoparentarcp; | |
615 | int maxexitcnt; | |
616 | int maxwithparentcnt; | |
617 | int maxnoparentcnt; | |
618 | char *type; | |
619 | ||
620 | maxexitcnt = 0; | |
621 | maxwithparentcnt = 0; | |
622 | maxnoparentcnt = 0; | |
623 | for ( endlist = &archead , arcp = archead ; arcp ; ) { | |
624 | if ( arcp -> arc_cyclecnt == 0 ) { | |
625 | arcp -> arc_flags &= ~ONLIST; | |
626 | *endlist = arcp -> arc_next; | |
627 | arcp -> arc_next = 0; | |
628 | arcp = *endlist; | |
629 | continue; | |
630 | } | |
631 | if ( arcp -> arc_childp -> flags & HASCYCLEXIT ) { | |
632 | if ( arcp -> arc_cyclecnt > maxexitcnt || | |
633 | ( arcp -> arc_cyclecnt == maxexitcnt && | |
634 | arcp -> arc_cyclecnt < maxexitarcp -> arc_count ) ) { | |
635 | maxexitcnt = arcp -> arc_cyclecnt; | |
636 | maxexitarcp = arcp; | |
637 | } | |
638 | } else if ( arcp -> arc_childp -> parentcnt > 1 ) { | |
639 | if ( arcp -> arc_cyclecnt > maxwithparentcnt || | |
640 | ( arcp -> arc_cyclecnt == maxwithparentcnt && | |
641 | arcp -> arc_cyclecnt < maxwithparentarcp -> arc_count ) ) { | |
642 | maxwithparentcnt = arcp -> arc_cyclecnt; | |
643 | maxwithparentarcp = arcp; | |
644 | } | |
645 | } else { | |
646 | if ( arcp -> arc_cyclecnt > maxnoparentcnt || | |
647 | ( arcp -> arc_cyclecnt == maxnoparentcnt && | |
648 | arcp -> arc_cyclecnt < maxnoparentarcp -> arc_count ) ) { | |
649 | maxnoparentcnt = arcp -> arc_cyclecnt; | |
650 | maxnoparentarcp = arcp; | |
651 | } | |
652 | } | |
653 | endlist = &arcp -> arc_next; | |
654 | arcp = arcp -> arc_next; | |
655 | } | |
656 | if ( maxexitcnt > 0 ) { | |
657 | /* | |
658 | * first choice is edge leading to node with out-of-cycle parent | |
659 | */ | |
660 | maxarcp = maxexitarcp; | |
661 | # ifdef DEBUG | |
662 | type = "exit"; | |
663 | # endif DEBUG | |
664 | } else if ( maxwithparentcnt > 0 ) { | |
665 | /* | |
666 | * second choice is edge leading to node with at least one | |
667 | * other in-cycle parent | |
668 | */ | |
669 | maxarcp = maxwithparentarcp; | |
670 | # ifdef DEBUG | |
671 | type = "internal"; | |
672 | # endif DEBUG | |
673 | } else { | |
674 | /* | |
675 | * last choice is edge leading to node with only this arc as | |
676 | * a parent (as it will now be orphaned) | |
677 | */ | |
678 | maxarcp = maxnoparentarcp; | |
679 | # ifdef DEBUG | |
680 | type = "orphan"; | |
681 | # endif DEBUG | |
682 | } | |
683 | maxarcp -> arc_flags |= DEADARC; | |
684 | maxarcp -> arc_childp -> parentcnt -= 1; | |
685 | maxarcp -> arc_childp -> npropcall -= maxarcp -> arc_count; | |
686 | # ifdef DEBUG | |
687 | if ( debug & BREAKCYCLE ) { | |
688 | printf( "%s delete %s arc: %s (%d) -> %s from %d cycle(s)\n" , | |
689 | "[compresslist]" , type , maxarcp -> arc_parentp -> name , | |
690 | maxarcp -> arc_count , maxarcp -> arc_childp -> name , | |
691 | maxarcp -> arc_cyclecnt ); | |
692 | } | |
693 | # endif DEBUG | |
694 | printf( "\t%s to %s with %d calls\n" , maxarcp -> arc_parentp -> name , | |
695 | maxarcp -> arc_childp -> name , maxarcp -> arc_count ); | |
696 | prev = &cyclehead; | |
697 | for ( clp = cyclehead ; clp ; ) { | |
698 | endlist = &clp -> list[ clp -> size ]; | |
699 | for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) | |
700 | if ( (*arcpp) -> arc_flags & DEADARC ) | |
701 | break; | |
702 | if ( arcpp == endlist ) { | |
703 | prev = &clp -> next; | |
704 | clp = clp -> next; | |
705 | continue; | |
706 | } | |
707 | for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) | |
708 | (*arcpp) -> arc_cyclecnt--; | |
709 | cyclecnt--; | |
710 | *prev = clp -> next; | |
711 | clp = clp -> next; | |
712 | free( clp ); | |
713 | } | |
714 | } | |
715 | ||
716 | #ifdef DEBUG | |
717 | printsubcycle( clp ) | |
718 | cltype *clp; | |
719 | { | |
720 | arctype **arcpp; | |
721 | arctype **endlist; | |
722 | ||
723 | arcpp = clp -> list; | |
724 | printf( "%s <cycle %d>\n" , (*arcpp) -> arc_parentp -> name , | |
725 | (*arcpp) -> arc_parentp -> cycleno ) ; | |
726 | for ( endlist = &clp -> list[ clp -> size ]; arcpp < endlist ; arcpp++ ) | |
727 | printf( "\t(%d) -> %s\n" , (*arcpp) -> arc_count , | |
728 | (*arcpp) -> arc_childp -> name ) ; | |
729 | } | |
730 | #endif DEBUG | |
731 | ||
7ec9eedc PK |
732 | cycletime() |
733 | { | |
734 | int cycle; | |
735 | nltype *cyclenlp; | |
7ec9eedc | 736 | nltype *childp; |
7ec9eedc PK |
737 | |
738 | for ( cycle = 1 ; cycle <= ncycle ; cycle += 1 ) { | |
739 | cyclenlp = &cyclenl[ cycle ]; | |
a441395b PK |
740 | for ( childp = cyclenlp -> cnext ; childp ; childp = childp -> cnext ) { |
741 | if ( childp -> propfraction == 0.0 ) { | |
742 | /* | |
743 | * all members have the same propfraction except those | |
744 | * that were excluded with -E | |
745 | */ | |
746 | continue; | |
747 | } | |
748 | cyclenlp -> time += childp -> time; | |
ca41b3be | 749 | } |
a441395b | 750 | cyclenlp -> propself = cyclenlp -> propfraction * cyclenlp -> time; |
ca41b3be PK |
751 | } |
752 | } | |
7ec9eedc PK |
753 | |
754 | /* | |
755 | * in one top to bottom pass over the topologically sorted namelist | |
a441395b PK |
756 | * propagate: |
757 | * printflag as the union of parents' printflags | |
758 | * propfraction as the sum of fractional parents' propfractions | |
759 | * and while we're here, sum time for functions. | |
7ec9eedc PK |
760 | */ |
761 | doflags() | |
762 | { | |
763 | int index; | |
764 | nltype *childp; | |
765 | nltype *oldhead; | |
766 | ||
767 | oldhead = 0; | |
768 | for ( index = nname-1 ; index >= 0 ; index -= 1 ) { | |
769 | childp = topsortnlp[ index ]; | |
770 | /* | |
771 | * if we haven't done this function or cycle, | |
a441395b | 772 | * inherit things from parent. |
7ec9eedc PK |
773 | * this way, we are linear in the number of arcs |
774 | * since we do all members of a cycle (and the cycle itself) | |
775 | * as we hit the first member of the cycle. | |
776 | */ | |
777 | if ( childp -> cyclehead != oldhead ) { | |
778 | oldhead = childp -> cyclehead; | |
a441395b | 779 | inheritflags( childp ); |
7ec9eedc | 780 | } |
a441395b PK |
781 | # ifdef DEBUG |
782 | if ( debug & PROPDEBUG ) { | |
783 | printf( "[doflags] " ); | |
784 | printname( childp ); | |
785 | printf( " inherits printflag %d and propfraction %f\n" , | |
786 | childp -> printflag , childp -> propfraction ); | |
787 | } | |
788 | # endif DEBUG | |
7ec9eedc PK |
789 | if ( ! childp -> printflag ) { |
790 | /* | |
a441395b PK |
791 | * printflag is off |
792 | * it gets turned on by | |
793 | * being on -f list, | |
794 | * or there not being any -f list and not being on -e list. | |
7ec9eedc | 795 | */ |
a441395b PK |
796 | if ( onlist( flist , childp -> name ) |
797 | || ( !fflag && !onlist( elist , childp -> name ) ) ) { | |
7ec9eedc | 798 | childp -> printflag = TRUE; |
7ec9eedc | 799 | } |
a441395b PK |
800 | } else { |
801 | /* | |
802 | * this function has printing parents: | |
803 | * maybe someone wants to shut it up | |
804 | * by putting it on -e list. (but favor -f over -e) | |
805 | */ | |
806 | if ( ( !onlist( flist , childp -> name ) ) | |
807 | && onlist( elist , childp -> name ) ) { | |
808 | childp -> printflag = FALSE; | |
7ec9eedc | 809 | } |
7ec9eedc | 810 | } |
a441395b PK |
811 | if ( childp -> propfraction == 0.0 ) { |
812 | /* | |
813 | * no parents to pass time to. | |
814 | * collect time from children if | |
815 | * its on -F list, | |
816 | * or there isn't any -F list and its not on -E list. | |
817 | */ | |
818 | if ( onlist( Flist , childp -> name ) | |
819 | || ( !Fflag && !onlist( Elist , childp -> name ) ) ) { | |
820 | childp -> propfraction = 1.0; | |
821 | } | |
822 | } else { | |
823 | /* | |
824 | * it has parents to pass time to, | |
825 | * but maybe someone wants to shut it up | |
826 | * by puttting it on -E list. (but favor -F over -E) | |
827 | */ | |
828 | if ( !onlist( Flist , childp -> name ) | |
829 | && onlist( Elist , childp -> name ) ) { | |
830 | childp -> propfraction = 0.0; | |
831 | } | |
7ec9eedc | 832 | } |
a441395b PK |
833 | childp -> propself = childp -> time * childp -> propfraction; |
834 | printtime += childp -> propself; | |
835 | # ifdef DEBUG | |
836 | if ( debug & PROPDEBUG ) { | |
837 | printf( "[doflags] " ); | |
838 | printname( childp ); | |
839 | printf( " ends up with printflag %d and propfraction %f\n" , | |
840 | childp -> printflag , childp -> propfraction ); | |
80a80acc PK |
841 | printf( "time %f propself %f printtime %f\n" , |
842 | childp -> time , childp -> propself , printtime ); | |
a441395b PK |
843 | } |
844 | # endif DEBUG | |
7ec9eedc PK |
845 | } |
846 | } | |
847 | ||
848 | /* | |
849 | * check if any parent of this child | |
850 | * (or outside parents of this cycle) | |
851 | * have their print flags on and set the | |
852 | * print flag of the child (cycle) appropriately. | |
a441395b | 853 | * similarly, deal with propagation fractions from parents. |
7ec9eedc | 854 | */ |
a441395b | 855 | inheritflags( childp ) |
7ec9eedc PK |
856 | nltype *childp; |
857 | { | |
858 | nltype *headp; | |
7ec9eedc | 859 | arctype *arcp; |
a441395b PK |
860 | nltype *parentp; |
861 | nltype *memp; | |
7ec9eedc PK |
862 | |
863 | headp = childp -> cyclehead; | |
864 | if ( childp == headp ) { | |
865 | /* | |
866 | * just a regular child, check its parents | |
867 | */ | |
a441395b PK |
868 | childp -> printflag = FALSE; |
869 | childp -> propfraction = 0.0; | |
870 | for (arcp = childp -> parents ; arcp ; arcp = arcp -> arc_parentlist) { | |
871 | parentp = arcp -> arc_parentp; | |
80a80acc PK |
872 | if ( childp == parentp ) { |
873 | continue; | |
874 | } | |
a441395b | 875 | childp -> printflag |= parentp -> printflag; |
1617cc07 PK |
876 | /* |
877 | * if the child was never actually called | |
878 | * (e.g. this arc is static (and all others are, too)) | |
879 | * no time propagates along this arc. | |
880 | */ | |
91541716 KM |
881 | if ( arcp -> arc_flags & DEADARC ) { |
882 | continue; | |
883 | } | |
884 | if ( childp -> npropcall ) { | |
1617cc07 | 885 | childp -> propfraction += parentp -> propfraction |
91541716 KM |
886 | * ( ( (double) arcp -> arc_count ) |
887 | / ( (double) childp -> npropcall ) ); | |
1617cc07 | 888 | } |
7ec9eedc | 889 | } |
a441395b PK |
890 | } else { |
891 | /* | |
892 | * its a member of a cycle, look at all parents from | |
893 | * outside the cycle | |
894 | */ | |
895 | headp -> printflag = FALSE; | |
896 | headp -> propfraction = 0.0; | |
897 | for ( memp = headp -> cnext ; memp ; memp = memp -> cnext ) { | |
898 | for (arcp = memp->parents ; arcp ; arcp = arcp->arc_parentlist) { | |
899 | if ( arcp -> arc_parentp -> cyclehead == headp ) { | |
900 | continue; | |
901 | } | |
902 | parentp = arcp -> arc_parentp; | |
903 | headp -> printflag |= parentp -> printflag; | |
1617cc07 PK |
904 | /* |
905 | * if the cycle was never actually called | |
906 | * (e.g. this arc is static (and all others are, too)) | |
907 | * no time propagates along this arc. | |
908 | */ | |
91541716 KM |
909 | if ( arcp -> arc_flags & DEADARC ) { |
910 | continue; | |
911 | } | |
912 | if ( headp -> npropcall ) { | |
1617cc07 | 913 | headp -> propfraction += parentp -> propfraction |
91541716 KM |
914 | * ( ( (double) arcp -> arc_count ) |
915 | / ( (double) headp -> npropcall ) ); | |
1617cc07 | 916 | } |
7ec9eedc PK |
917 | } |
918 | } | |
a441395b PK |
919 | for ( memp = headp ; memp ; memp = memp -> cnext ) { |
920 | memp -> printflag = headp -> printflag; | |
921 | memp -> propfraction = headp -> propfraction; | |
922 | } | |
7ec9eedc PK |
923 | } |
924 | } |