Commit | Line | Data |
---|---|---|
ca41b3be PK |
1 | #ifndef lint |
2 | static char *sccsid = "@(#)arcs.c 1.1 (Berkeley) %G%"; | |
3 | #endif lint | |
4 | ||
5 | #include "dprof.h" | |
6 | ||
7 | topcmp( npp1 , npp2 ) | |
8 | nltype **npp1; | |
9 | nltype **npp2; | |
10 | { | |
11 | return (*npp1) -> toporder - (*npp2) -> toporder; | |
12 | } | |
13 | ||
14 | /* | |
15 | * sort by decreasing total time (time+childtime) | |
16 | * if times are equal, but one is a cycle header, | |
17 | * say that's first (e.g. less) | |
18 | */ | |
19 | int | |
20 | totalcmp( npp1 , npp2 ) | |
21 | nltype **npp1; | |
22 | nltype **npp2; | |
23 | { | |
24 | register nltype *np1 = *npp1; | |
25 | register nltype *np2 = *npp2; | |
26 | double diff; | |
27 | ||
28 | diff = ( np1 -> time + np1 -> childtime ) | |
29 | - ( np2 -> time + np2 -> childtime ); | |
30 | if ( diff < 0.0 ) | |
31 | return 1; | |
32 | if ( diff > 0.0 ) | |
33 | return -1; | |
34 | if ( np1 -> name == 0 && np1 -> cycleno != 0 ) | |
35 | return -1; | |
36 | if ( np2 -> name == 0 && np1 -> cycleno != 0 ) | |
37 | return 1; | |
38 | return 0; | |
39 | } | |
40 | ||
41 | doarcs() | |
42 | { | |
43 | nltype *parentp; | |
44 | arctype *arcp; | |
45 | nltype **topsortnlp; | |
46 | long index; | |
47 | nltype *childp; | |
48 | double share; | |
49 | ||
50 | /* | |
51 | * initialize various things: | |
52 | * zero out child times. | |
53 | * count self-recursive calls. | |
54 | * indicate that nothing is on cycles. | |
55 | */ | |
56 | for ( parentp = nl ; parentp < npe ; parentp++ ) { | |
57 | parentp -> childtime = 0.0; | |
58 | arcp = arclookup( parentp , parentp ); | |
59 | if ( arcp != 0 ) { | |
60 | parentp -> ncall -= arcp -> arc_count; | |
61 | parentp -> selfcalls = arcp -> arc_count; | |
62 | } else { | |
63 | parentp -> selfcalls = 0; | |
64 | } | |
65 | parentp -> toporder = 0; | |
66 | parentp -> cycleno = 0; | |
67 | parentp -> cyclehead = parentp; | |
68 | parentp -> cnext = 0; | |
69 | } | |
70 | /* | |
71 | * topologically order things | |
72 | * from each of the roots of the call graph | |
73 | */ | |
74 | for ( parentp = nl ; parentp < npe ; parentp++ ) { | |
75 | if ( parentp -> parents == 0 ) { | |
76 | dfn( parentp ); | |
77 | } | |
78 | } | |
79 | /* | |
80 | * link together nodes on the same cycle | |
81 | */ | |
82 | cyclelink(); | |
83 | /* | |
84 | * Sort the symbol table in reverse topological order | |
85 | */ | |
86 | topsortnlp = (nltype **) calloc( nname , sizeof(nltype *) ); | |
87 | if ( topsortnlp == (nltype **) 0 ) { | |
88 | fprintf( stderr , "[doarcs] ran out of memory for topo sorting\n" ); | |
89 | } | |
90 | for ( index = 0 ; index < nname ; index += 1 ) { | |
91 | topsortnlp[ index ] = &nl[ index ]; | |
92 | } | |
93 | qsort( topsortnlp , nname , sizeof(nltype *) , topcmp ); | |
94 | # ifdef DEBUG | |
95 | if ( debug & DFNDEBUG ) { | |
96 | printf( "[doarcs] topological sort listing\n" ); | |
97 | for ( index = 0 ; index < nname ; index += 1 ) { | |
98 | printf( "[doarcs] " ); | |
99 | printf( "%d:" , topsortnlp[ index ] -> toporder ); | |
100 | printname( topsortnlp[ index ] ); | |
101 | printf( "\n" ); | |
102 | } | |
103 | } | |
104 | # endif DEBUG | |
105 | /* | |
106 | * starting from the topological bottom, | |
107 | * propogate children times | |
108 | */ | |
109 | for ( index = 0 ; index < nname ; index += 1 ) { | |
110 | parentp = topsortnlp[ index ]; | |
111 | for ( arcp = parentp->children ; arcp ; arcp = arcp->arc_childlist ) { | |
112 | childp = arcp -> arc_childp; | |
113 | # ifdef DEBUG | |
114 | if ( debug & ARCDEBUG ) { | |
115 | printf( "[doarcs] " ); | |
116 | printname( parentp ); | |
117 | printf( " calls " ); | |
118 | printname( childp ); | |
119 | printf( " %d (%d) times\n" , | |
120 | arcp -> arc_count , childp -> ncall ); | |
121 | } | |
122 | # endif DEBUG | |
123 | if ( arcp -> arc_count == 0 ) { | |
124 | continue; | |
125 | } | |
126 | if ( childp -> ncall == 0 ) { | |
127 | continue; | |
128 | } | |
129 | if ( childp == parentp ) { | |
130 | continue; | |
131 | } | |
132 | if ( childp -> cyclehead != childp ) { | |
133 | if ( parentp -> cycleno == childp -> cycleno ) { | |
134 | continue; | |
135 | } | |
136 | # ifdef DEBUG | |
137 | if ( debug & ARCDEBUG ) { | |
138 | printf( "[doarcs]\t it's a call into cycle %d\n" , | |
139 | childp -> cycleno ); | |
140 | } | |
141 | # endif DEBUG | |
142 | if ( parentp -> toporder <= childp -> toporder ) { | |
143 | fprintf( stderr , "[doarcs] toporder botches\n" ); | |
144 | } | |
145 | childp = childp -> cyclehead; | |
146 | } else { | |
147 | if ( parentp -> toporder <= childp -> toporder ) { | |
148 | fprintf( stderr , "[doarcs] toporder botches\n" ); | |
149 | continue; | |
150 | } | |
151 | } | |
152 | /* | |
153 | * distribute time for this arc | |
154 | */ | |
155 | arcp -> arc_time = childp -> time * | |
156 | ( ( (double) arcp -> arc_count ) / | |
157 | ( (double) childp -> ncall ) ); | |
158 | arcp -> arc_childtime = childp -> childtime * | |
159 | ( ( (double) arcp -> arc_count ) / | |
160 | ( (double) childp -> ncall ) ); | |
161 | share = arcp -> arc_time + arcp -> arc_childtime; | |
162 | # ifdef DEBUG | |
163 | if ( debug & ARCDEBUG ) { | |
164 | printf( "[doarcs]\t " ); | |
165 | printname( childp ); | |
166 | printf( " time %8.2f + childtime %8.2f\n" , | |
167 | childp -> time , childp -> childtime ); | |
168 | printf( "[doarcs]\t this is %d arcs of the %d calls\n", | |
169 | arcp -> arc_count , childp -> ncall ); | |
170 | printf( "[doarcs]\t so this gives %8.2f+%8.2f to %s\n" , | |
171 | arcp -> arc_time , arcp -> arc_childtime , | |
172 | parentp -> name ); | |
173 | } | |
174 | # endif DEBUG | |
175 | parentp -> childtime += share; | |
176 | /* | |
177 | * add this share to the cycle header, if any | |
178 | */ | |
179 | if ( parentp -> cyclehead != parentp ) { | |
180 | # ifdef DEBUG | |
181 | if ( debug & ARCDEBUG ) { | |
182 | printf( "[doarcs]\t and to cycle %d\n" , | |
183 | parentp -> cycleno ); | |
184 | } | |
185 | # endif DEBUG | |
186 | parentp -> cyclehead -> childtime += share; | |
187 | } | |
188 | } | |
189 | } | |
190 | printdprof(); | |
191 | } | |
192 | ||
193 | cyclelink() | |
194 | { | |
195 | register nltype *nlp; | |
196 | register nltype *parentp; | |
197 | register nltype *childp; | |
198 | register nltype *cyclenlp; | |
199 | int cycle; | |
200 | arctype *arcp; | |
201 | long ncall; | |
202 | double time; | |
203 | long callsamong; | |
204 | ||
205 | /* | |
206 | * Count the number of cycles, and initialze the cycle lists | |
207 | */ | |
208 | cyclemax = 0; | |
209 | for ( nlp = nl ; nlp < npe ; nlp++ ) { | |
210 | /* | |
211 | * this is how you find unattached cycles | |
212 | */ | |
213 | if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) { | |
214 | cyclemax += 1; | |
215 | } | |
216 | } | |
217 | if ( cyclemax > ncycles ) { | |
218 | fprintf( stderr , "prof: %d cycles in %d names exceeds %f%%\n" , | |
219 | cyclemax , nname , CYCLEFRACTION * 100.0 ); | |
220 | exit( 1 ); | |
221 | } | |
222 | /* | |
223 | * now link cycles to true cycleheads, | |
224 | * number them, accumulate the data for the cycle | |
225 | */ | |
226 | cycle = 0; | |
227 | for ( nlp = nl ; nlp < npe ; nlp++ ) { | |
228 | if ( nlp -> cyclehead != nlp || nlp -> cnext == 0 ) { | |
229 | continue; | |
230 | } | |
231 | cycle += 1; | |
232 | cyclenlp = &nl[nname+cycle]; | |
233 | cyclenlp -> cycleno = cycle; | |
234 | cyclenlp -> cyclehead = cyclenlp; | |
235 | cyclenlp -> cnext = nlp; | |
236 | # ifdef DEBUG | |
237 | if ( debug & CYCLEDEBUG ) { | |
238 | printf( "[cyclelink] " ); | |
239 | printname( nlp ); | |
240 | printf( " is the head of cycle %d\n" , cycle ); | |
241 | } | |
242 | # endif DEBUG | |
243 | /* | |
244 | * n-squaredly (in the size of the cycle) | |
245 | * find all the call within the cycle | |
246 | * (including self-recursive calls) | |
247 | * and remove them, thus making the cycle into | |
248 | * `node' with calls only from the outside. | |
249 | * note: that this doesn't deal with | |
250 | * self-recursive calls outside cycles (sigh). | |
251 | */ | |
252 | callsamong = 0; | |
253 | for ( parentp = nlp ; parentp ; parentp = parentp -> cnext ) { | |
254 | parentp -> cycleno = cycle; | |
255 | parentp -> cyclehead = cyclenlp; | |
256 | for ( childp = nlp ; childp ; childp = childp -> cnext ) { | |
257 | if ( parentp == childp ) { | |
258 | continue; | |
259 | } | |
260 | arcp = arclookup( parentp , childp ); | |
261 | if ( arcp != 0 ) { | |
262 | callsamong += arcp -> arc_count; | |
263 | # ifdef DEBUG | |
264 | if ( debug & CYCLEDEBUG ) { | |
265 | printf("[cyclelink] %s calls sibling %s %d times\n", | |
266 | parentp -> name , childp -> name , | |
267 | arcp -> arc_count ); | |
268 | } | |
269 | # endif DEBUG | |
270 | } | |
271 | } | |
272 | } | |
273 | /* | |
274 | * collect calls and time around the cycle, | |
275 | * and save it in the cycle header. | |
276 | */ | |
277 | ncall = -callsamong; | |
278 | time = 0.0; | |
279 | for ( parentp = nlp ; parentp ; parentp = parentp -> cnext ) { | |
280 | ncall += parentp -> ncall; | |
281 | time += parentp -> time; | |
282 | } | |
283 | # ifdef DEBUG | |
284 | if ( debug & CYCLEDEBUG ) { | |
285 | printf( "[cyclelink] cycle %d %f ticks in %d (%d) calls\n" , | |
286 | cycle , time , ncall , callsamong ); | |
287 | } | |
288 | # endif DEBUG | |
289 | cyclenlp -> ncall = ncall; | |
290 | cyclenlp -> selfcalls = callsamong; | |
291 | cyclenlp -> time = time; | |
292 | cyclenlp -> childtime = 0.0; | |
293 | } | |
294 | } |