Commit | Line | Data |
---|---|---|
252b5132 RH |
1 | /* |
2 | * Copyright (c) 1983 Regents of the University of California. | |
3 | * All rights reserved. | |
4 | * | |
5 | * Redistribution and use in source and binary forms are permitted | |
6 | * provided that: (1) source distributions retain this entire copyright | |
7 | * notice and comment, and (2) distributions including binaries display | |
8 | * the following acknowledgement: ``This product includes software | |
9 | * developed by the University of California, Berkeley and its contributors'' | |
10 | * in the documentation or other materials provided with the distribution | |
11 | * and in all advertising materials mentioning features or use of this | |
12 | * software. Neither the name of the University nor the names of its | |
13 | * contributors may be used to endorse or promote products derived | |
14 | * from this software without specific prior written permission. | |
15 | * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR | |
16 | * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED | |
17 | * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. | |
18 | */ | |
bd917ff6 | 19 | #include "libiberty.h" |
252b5132 | 20 | #include "gprof.h" |
6d9c411a AM |
21 | #include "search_list.h" |
22 | #include "source.h" | |
23 | #include "symtab.h" | |
252b5132 RH |
24 | #include "cg_arcs.h" |
25 | #include "cg_dfn.h" | |
252b5132 RH |
26 | #include "utils.h" |
27 | ||
bd917ff6 | 28 | #define DFN_INCR_DEPTH (128) |
252b5132 RH |
29 | |
30 | typedef struct | |
31 | { | |
32 | Sym *sym; | |
33 | int cycle_top; | |
34 | } | |
35 | DFN_Stack; | |
36 | ||
bd917ff6 ILT |
37 | DFN_Stack *dfn_stack = NULL; |
38 | int dfn_maxdepth = 0; | |
252b5132 RH |
39 | int dfn_depth = 0; |
40 | int dfn_counter = DFN_NAN; | |
41 | ||
42 | ||
43 | /* | |
44 | * Is CHILD already numbered? | |
45 | */ | |
bde52789 | 46 | static boolean |
252b5132 RH |
47 | DEFUN (is_numbered, (child), Sym * child) |
48 | { | |
49 | return child->cg.top_order != DFN_NAN && child->cg.top_order != DFN_BUSY; | |
50 | } | |
51 | ||
52 | ||
53 | /* | |
54 | * Is CHILD already busy? | |
55 | */ | |
bde52789 | 56 | static boolean |
252b5132 RH |
57 | DEFUN (is_busy, (child), Sym * child) |
58 | { | |
59 | if (child->cg.top_order == DFN_NAN) | |
60 | { | |
bde52789 | 61 | return false; |
252b5132 | 62 | } |
bde52789 | 63 | return true; |
252b5132 RH |
64 | } |
65 | ||
66 | ||
67 | /* | |
68 | * CHILD is part of a cycle. Find the top caller into this cycle | |
69 | * that is not part of the cycle and make all functions in cycle | |
70 | * members of that cycle (top caller == caller with smallest | |
71 | * depth-first number). | |
72 | */ | |
73 | static void | |
74 | DEFUN (find_cycle, (child), Sym * child) | |
75 | { | |
76 | Sym *head = 0; | |
77 | Sym *tail; | |
78 | int cycle_top; | |
79 | int index; | |
80 | ||
81 | for (cycle_top = dfn_depth; cycle_top > 0; --cycle_top) | |
82 | { | |
83 | head = dfn_stack[cycle_top].sym; | |
84 | if (child == head) | |
85 | { | |
86 | break; | |
87 | } | |
88 | if (child->cg.cyc.head != child && child->cg.cyc.head == head) | |
89 | { | |
90 | break; | |
91 | } | |
92 | } | |
93 | if (cycle_top <= 0) | |
94 | { | |
95 | fprintf (stderr, "[find_cycle] couldn't find head of cycle\n"); | |
96 | done (1); | |
97 | } | |
98 | #ifdef DEBUG | |
99 | if (debug_level & DFNDEBUG) | |
100 | { | |
101 | printf ("[find_cycle] dfn_depth %d cycle_top %d ", | |
102 | dfn_depth, cycle_top); | |
103 | if (head) | |
104 | { | |
105 | print_name (head); | |
106 | } | |
107 | else | |
108 | { | |
109 | printf ("<unknown>"); | |
110 | } | |
111 | printf ("\n"); | |
112 | } | |
113 | #endif | |
114 | if (cycle_top == dfn_depth) | |
115 | { | |
116 | /* | |
117 | * This is previous function, e.g. this calls itself. Sort of | |
118 | * boring. | |
119 | * | |
120 | * Since we are taking out self-cycles elsewhere no need for | |
121 | * the special case, here. | |
122 | */ | |
123 | DBG (DFNDEBUG, | |
124 | printf ("[find_cycle] "); | |
125 | print_name (child); | |
126 | printf ("\n")); | |
127 | } | |
128 | else | |
129 | { | |
130 | /* | |
131 | * Glom intervening functions that aren't already glommed into | |
132 | * this cycle. Things have been glommed when their cyclehead | |
133 | * field points to the head of the cycle they are glommed | |
134 | * into. | |
135 | */ | |
136 | for (tail = head; tail->cg.cyc.next; tail = tail->cg.cyc.next) | |
137 | { | |
138 | /* void: chase down to tail of things already glommed */ | |
139 | DBG (DFNDEBUG, | |
140 | printf ("[find_cycle] tail "); | |
141 | print_name (tail); | |
142 | printf ("\n")); | |
143 | } | |
144 | /* | |
145 | * If what we think is the top of the cycle has a cyclehead | |
146 | * field, then it's not really the head of the cycle, which is | |
147 | * really what we want. | |
148 | */ | |
149 | if (head->cg.cyc.head != head) | |
150 | { | |
151 | head = head->cg.cyc.head; | |
152 | DBG (DFNDEBUG, printf ("[find_cycle] new cyclehead "); | |
153 | print_name (head); | |
154 | printf ("\n")); | |
155 | } | |
156 | for (index = cycle_top + 1; index <= dfn_depth; ++index) | |
157 | { | |
158 | child = dfn_stack[index].sym; | |
159 | if (child->cg.cyc.head == child) | |
160 | { | |
161 | /* | |
162 | * Not yet glommed anywhere, glom it and fix any | |
163 | * children it has glommed. | |
164 | */ | |
165 | tail->cg.cyc.next = child; | |
166 | child->cg.cyc.head = head; | |
167 | DBG (DFNDEBUG, printf ("[find_cycle] glomming "); | |
168 | print_name (child); | |
169 | printf (" onto "); | |
170 | print_name (head); | |
171 | printf ("\n")); | |
172 | for (tail = child; tail->cg.cyc.next; tail = tail->cg.cyc.next) | |
173 | { | |
174 | tail->cg.cyc.next->cg.cyc.head = head; | |
175 | DBG (DFNDEBUG, printf ("[find_cycle] and its tail "); | |
176 | print_name (tail->cg.cyc.next); | |
177 | printf (" onto "); | |
178 | print_name (head); | |
179 | printf ("\n")); | |
180 | } | |
181 | } | |
182 | else if (child->cg.cyc.head != head /* firewall */ ) | |
183 | { | |
184 | fprintf (stderr, "[find_cycle] glommed, but not to head\n"); | |
185 | done (1); | |
186 | } | |
187 | } | |
188 | } | |
189 | } | |
190 | ||
191 | ||
192 | /* | |
193 | * Prepare for visiting the children of PARENT. Push a parent onto | |
194 | * the stack and mark it busy. | |
195 | */ | |
196 | static void | |
197 | DEFUN (pre_visit, (parent), Sym * parent) | |
198 | { | |
199 | ++dfn_depth; | |
bd917ff6 ILT |
200 | |
201 | if (dfn_depth >= dfn_maxdepth) | |
252b5132 | 202 | { |
bd917ff6 ILT |
203 | dfn_maxdepth += DFN_INCR_DEPTH; |
204 | dfn_stack = xrealloc (dfn_stack, dfn_maxdepth * sizeof *dfn_stack); | |
252b5132 | 205 | } |
bd917ff6 | 206 | |
252b5132 RH |
207 | dfn_stack[dfn_depth].sym = parent; |
208 | dfn_stack[dfn_depth].cycle_top = dfn_depth; | |
209 | parent->cg.top_order = DFN_BUSY; | |
210 | DBG (DFNDEBUG, printf ("[pre_visit]\t\t%d:", dfn_depth); | |
211 | print_name (parent); | |
212 | printf ("\n")); | |
213 | } | |
214 | ||
215 | ||
216 | /* | |
217 | * Done with visiting node PARENT. Pop PARENT off dfn_stack | |
218 | * and number functions if PARENT is head of a cycle. | |
219 | */ | |
220 | static void | |
221 | DEFUN (post_visit, (parent), Sym * parent) | |
222 | { | |
223 | Sym *member; | |
224 | ||
225 | DBG (DFNDEBUG, printf ("[post_visit]\t%d: ", dfn_depth); | |
226 | print_name (parent); | |
227 | printf ("\n")); | |
228 | /* | |
229 | * Number functions and things in their cycles unless the function | |
230 | * is itself part of a cycle: | |
231 | */ | |
232 | if (parent->cg.cyc.head == parent) | |
233 | { | |
234 | ++dfn_counter; | |
235 | for (member = parent; member; member = member->cg.cyc.next) | |
236 | { | |
237 | member->cg.top_order = dfn_counter; | |
238 | DBG (DFNDEBUG, printf ("[post_visit]\t\tmember "); | |
239 | print_name (member); | |
240 | printf ("-> cg.top_order = %d\n", dfn_counter)); | |
241 | } | |
242 | } | |
243 | else | |
244 | { | |
245 | DBG (DFNDEBUG, printf ("[post_visit]\t\tis part of a cycle\n")); | |
246 | } | |
247 | --dfn_depth; | |
248 | } | |
249 | ||
250 | ||
251 | /* | |
252 | * Given this PARENT, depth first number its children. | |
253 | */ | |
254 | void | |
255 | DEFUN (cg_dfn, (parent), Sym * parent) | |
256 | { | |
257 | Arc *arc; | |
258 | ||
259 | DBG (DFNDEBUG, printf ("[dfn] dfn( "); | |
260 | print_name (parent); | |
261 | printf (")\n")); | |
262 | /* | |
263 | * If we're already numbered, no need to look any further: | |
264 | */ | |
265 | if (is_numbered (parent)) | |
266 | { | |
267 | return; | |
268 | } | |
269 | /* | |
270 | * If we're already busy, must be a cycle: | |
271 | */ | |
272 | if (is_busy (parent)) | |
273 | { | |
274 | find_cycle (parent); | |
275 | return; | |
276 | } | |
277 | pre_visit (parent); | |
278 | /* | |
279 | * Recursively visit children: | |
280 | */ | |
281 | for (arc = parent->cg.children; arc; arc = arc->next_child) | |
282 | { | |
283 | cg_dfn (arc->child); | |
284 | } | |
285 | post_visit (parent); | |
286 | } |