Commit | Line | Data |
---|---|---|
c0bc4ef7 DF |
1 | /* |
2 | * Copyright (c) 1983 Regents of the University of California. | |
ddb85eed KB |
3 | * All rights reserved. |
4 | * | |
6ecf3d85 | 5 | * %sccs.include.redist.c% |
c0bc4ef7 DF |
6 | */ |
7 | ||
4f1db472 | 8 | #ifndef lint |
91541716 | 9 | static char sccsid[] = "@(#)dfn.c 5.5 (Berkeley) %G%"; |
ddb85eed | 10 | #endif /* not lint */ |
4f1db472 PK |
11 | |
12 | #include <stdio.h> | |
31f0a970 | 13 | #include "gprof.h" |
4f1db472 PK |
14 | |
15 | #define DFN_DEPTH 100 | |
16 | struct dfnstruct { | |
17 | nltype *nlentryp; | |
18 | int cycletop; | |
19 | }; | |
20 | typedef struct dfnstruct dfntype; | |
21 | ||
22 | dfntype dfn_stack[ DFN_DEPTH ]; | |
91541716 | 23 | int dfn_depth; |
4f1db472 | 24 | |
91541716 KM |
25 | int dfn_counter; |
26 | ||
27 | dfn_init() | |
28 | { | |
29 | ||
30 | dfn_depth = 0; | |
31 | dfn_counter = DFN_NAN; | |
32 | } | |
4f1db472 PK |
33 | |
34 | /* | |
35 | * given this parent, depth first number its children. | |
36 | */ | |
37 | dfn( parentp ) | |
38 | nltype *parentp; | |
39 | { | |
40 | arctype *arcp; | |
41 | ||
42 | # ifdef DEBUG | |
43 | if ( debug & DFNDEBUG ) { | |
44 | printf( "[dfn] dfn(" ); | |
45 | printname( parentp ); | |
46 | printf( ")\n" ); | |
47 | } | |
48 | # endif DEBUG | |
49 | /* | |
50 | * if we're already numbered, no need to look any furthur. | |
51 | */ | |
52 | if ( dfn_numbered( parentp ) ) { | |
53 | return; | |
54 | } | |
55 | /* | |
56 | * if we're already busy, must be a cycle | |
57 | */ | |
58 | if ( dfn_busy( parentp ) ) { | |
59 | dfn_findcycle( parentp ); | |
60 | return; | |
61 | } | |
62 | /* | |
63 | * visit yourself before your children | |
64 | */ | |
65 | dfn_pre_visit( parentp ); | |
66 | /* | |
67 | * visit children | |
68 | */ | |
69 | for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) { | |
91541716 KM |
70 | if ( arcp -> arc_flags & DEADARC ) |
71 | continue; | |
4f1db472 PK |
72 | dfn( arcp -> arc_childp ); |
73 | } | |
74 | /* | |
75 | * visit yourself after your children | |
76 | */ | |
77 | dfn_post_visit( parentp ); | |
78 | } | |
79 | ||
80 | /* | |
81 | * push a parent onto the stack and mark it busy | |
82 | */ | |
83 | dfn_pre_visit( parentp ) | |
84 | nltype *parentp; | |
85 | { | |
86 | ||
87 | dfn_depth += 1; | |
88 | if ( dfn_depth >= DFN_DEPTH ) { | |
89 | fprintf( stderr , "[dfn] out of my depth (dfn_stack overflow)\n" ); | |
90 | exit( 1 ); | |
91 | } | |
92 | dfn_stack[ dfn_depth ].nlentryp = parentp; | |
93 | dfn_stack[ dfn_depth ].cycletop = dfn_depth; | |
94 | parentp -> toporder = DFN_BUSY; | |
95 | # ifdef DEBUG | |
96 | if ( debug & DFNDEBUG ) { | |
97 | printf( "[dfn_pre_visit]\t\t%d:" , dfn_depth ); | |
98 | printname( parentp ); | |
99 | printf( "\n" ); | |
100 | } | |
101 | # endif DEBUG | |
102 | } | |
103 | ||
104 | /* | |
105 | * are we already numbered? | |
106 | */ | |
107 | bool | |
108 | dfn_numbered( childp ) | |
109 | nltype *childp; | |
110 | { | |
111 | ||
80ebf400 | 112 | return ( childp -> toporder != DFN_NAN && childp -> toporder != DFN_BUSY ); |
4f1db472 PK |
113 | } |
114 | ||
115 | /* | |
116 | * are we already busy? | |
117 | */ | |
118 | bool | |
119 | dfn_busy( childp ) | |
120 | nltype *childp; | |
121 | { | |
122 | ||
80ebf400 | 123 | if ( childp -> toporder == DFN_NAN ) { |
4f1db472 PK |
124 | return FALSE; |
125 | } | |
126 | return TRUE; | |
127 | } | |
128 | ||
129 | /* | |
130 | * MISSING: an explanation | |
131 | */ | |
132 | dfn_findcycle( childp ) | |
133 | nltype *childp; | |
134 | { | |
135 | int cycletop; | |
136 | nltype *cycleheadp; | |
137 | nltype *tailp; | |
138 | int index; | |
139 | ||
140 | for ( cycletop = dfn_depth ; cycletop > 0 ; cycletop -= 1 ) { | |
141 | cycleheadp = dfn_stack[ cycletop ].nlentryp; | |
142 | if ( childp == cycleheadp ) { | |
143 | break; | |
144 | } | |
145 | if ( childp -> cyclehead != childp && | |
146 | childp -> cyclehead == cycleheadp ) { | |
147 | break; | |
148 | } | |
149 | } | |
150 | if ( cycletop <= 0 ) { | |
151 | fprintf( stderr , "[dfn_findcycle] couldn't find head of cycle\n" ); | |
152 | exit( 1 ); | |
153 | } | |
154 | # ifdef DEBUG | |
155 | if ( debug & DFNDEBUG ) { | |
156 | printf( "[dfn_findcycle] dfn_depth %d cycletop %d " , | |
157 | dfn_depth , cycletop ); | |
158 | printname( cycleheadp ); | |
159 | printf( "\n" ); | |
160 | } | |
161 | # endif DEBUG | |
162 | if ( cycletop == dfn_depth ) { | |
163 | /* | |
164 | * this is previous function, e.g. this calls itself | |
165 | * sort of boring | |
166 | */ | |
167 | dfn_self_cycle( childp ); | |
168 | } else { | |
169 | /* | |
170 | * glom intervening functions that aren't already | |
171 | * glommed into this cycle. | |
172 | * things have been glommed when their cyclehead field | |
173 | * points to the head of the cycle they are glommed into. | |
174 | */ | |
175 | for ( tailp = cycleheadp ; tailp -> cnext ; tailp = tailp -> cnext ) { | |
176 | /* void: chase down to tail of things already glommed */ | |
177 | # ifdef DEBUG | |
178 | if ( debug & DFNDEBUG ) { | |
179 | printf( "[dfn_findcycle] tail " ); | |
180 | printname( tailp ); | |
181 | printf( "\n" ); | |
182 | } | |
183 | # endif DEBUG | |
184 | } | |
185 | /* | |
186 | * if what we think is the top of the cycle | |
187 | * has a cyclehead field, then it's not really the | |
188 | * head of the cycle, which is really what we want | |
189 | */ | |
190 | if ( cycleheadp -> cyclehead != cycleheadp ) { | |
191 | cycleheadp = cycleheadp -> cyclehead; | |
192 | # ifdef DEBUG | |
193 | if ( debug & DFNDEBUG ) { | |
194 | printf( "[dfn_findcycle] new cyclehead " ); | |
195 | printname( cycleheadp ); | |
196 | printf( "\n" ); | |
197 | } | |
198 | # endif DEBUG | |
199 | } | |
200 | for ( index = cycletop + 1 ; index <= dfn_depth ; index += 1 ) { | |
201 | childp = dfn_stack[ index ].nlentryp; | |
202 | if ( childp -> cyclehead == childp ) { | |
203 | /* | |
204 | * not yet glommed anywhere, glom it | |
205 | * and fix any children it has glommed | |
206 | */ | |
207 | tailp -> cnext = childp; | |
208 | childp -> cyclehead = cycleheadp; | |
209 | # ifdef DEBUG | |
210 | if ( debug & DFNDEBUG ) { | |
211 | printf( "[dfn_findcycle] glomming " ); | |
212 | printname( childp ); | |
213 | printf( " onto " ); | |
214 | printname( cycleheadp ); | |
215 | printf( "\n" ); | |
216 | } | |
217 | # endif DEBUG | |
218 | for ( tailp = childp ; tailp->cnext ; tailp = tailp->cnext ) { | |
219 | tailp -> cnext -> cyclehead = cycleheadp; | |
220 | # ifdef DEBUG | |
221 | if ( debug & DFNDEBUG ) { | |
222 | printf( "[dfn_findcycle] and its tail " ); | |
223 | printname( tailp -> cnext ); | |
224 | printf( " onto " ); | |
225 | printname( cycleheadp ); | |
226 | printf( "\n" ); | |
227 | } | |
228 | # endif DEBUG | |
229 | } | |
230 | } else if ( childp -> cyclehead != cycleheadp /* firewall */ ) { | |
231 | fprintf( stderr , | |
232 | "[dfn_busy] glommed, but not to cyclehead\n" ); | |
233 | } | |
234 | } | |
235 | } | |
236 | } | |
237 | ||
238 | /* | |
239 | * deal with self-cycles | |
240 | * for lint: ARGSUSED | |
241 | */ | |
242 | dfn_self_cycle( parentp ) | |
243 | nltype *parentp; | |
244 | { | |
245 | /* | |
246 | * since we are taking out self-cycles elsewhere | |
247 | * no need for the special case, here. | |
248 | */ | |
249 | # ifdef DEBUG | |
250 | if ( debug & DFNDEBUG ) { | |
251 | printf( "[dfn_self_cycle] " ); | |
252 | printname( parentp ); | |
253 | printf( "\n" ); | |
254 | } | |
255 | # endif DEBUG | |
256 | } | |
257 | ||
258 | /* | |
259 | * visit a node after all its children | |
260 | * [MISSING: an explanation] | |
261 | * and pop it off the stack | |
262 | */ | |
263 | dfn_post_visit( parentp ) | |
264 | nltype *parentp; | |
265 | { | |
266 | nltype *memberp; | |
267 | ||
268 | # ifdef DEBUG | |
269 | if ( debug & DFNDEBUG ) { | |
270 | printf( "[dfn_post_visit]\t%d: " , dfn_depth ); | |
271 | printname( parentp ); | |
272 | printf( "\n" ); | |
273 | } | |
274 | # endif DEBUG | |
275 | /* | |
276 | * number functions and things in their cycles | |
277 | * unless the function is itself part of a cycle | |
278 | */ | |
279 | if ( parentp -> cyclehead == parentp ) { | |
280 | dfn_counter += 1; | |
281 | for ( memberp = parentp ; memberp ; memberp = memberp -> cnext ) { | |
282 | memberp -> toporder = dfn_counter; | |
283 | # ifdef DEBUG | |
284 | if ( debug & DFNDEBUG ) { | |
285 | printf( "[dfn_post_visit]\t\tmember " ); | |
286 | printname( memberp ); | |
287 | printf( " -> toporder = %d\n" , dfn_counter ); | |
288 | } | |
289 | # endif DEBUG | |
290 | } | |
291 | } else { | |
292 | # ifdef DEBUG | |
293 | if ( debug & DFNDEBUG ) { | |
294 | printf( "[dfn_post_visit]\t\tis part of a cycle\n" ); | |
295 | } | |
296 | # endif DEBUG | |
297 | } | |
298 | dfn_depth -= 1; | |
299 | } |