Commit | Line | Data |
---|---|---|
ef368dac NC |
1 | /* cg_print.c - Print routines for displaying call graphs. |
2 | ||
af6dfb5b | 3 | Copyright 2000, 2001, 2002 Free Software Foundation, Inc. |
ef368dac NC |
4 | |
5 | This file is part of GNU Binutils. | |
6 | ||
7 | This program is free software; you can redistribute it and/or modify | |
8 | it under the terms of the GNU General Public License as published by | |
9 | the Free Software Foundation; either version 2 of the License, or | |
10 | (at your option) any later version. | |
11 | ||
12 | This program is distributed in the hope that it will be useful, | |
13 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | GNU General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
18 | along with this program; if not, write to the Free Software | |
19 | Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA | |
20 | 02111-1307, USA. */ | |
21 | \f | |
252b5132 | 22 | #include "libiberty.h" |
6d9c411a AM |
23 | #include "gprof.h" |
24 | #include "search_list.h" | |
25 | #include "source.h" | |
26 | #include "symtab.h" | |
252b5132 RH |
27 | #include "cg_arcs.h" |
28 | #include "cg_print.h" | |
29 | #include "hist.h" | |
30 | #include "utils.h" | |
31 | ||
ef368dac | 32 | /* Return value of comparison functions used to sort tables. */ |
252b5132 RH |
33 | #define LESSTHAN -1 |
34 | #define EQUALTO 0 | |
35 | #define GREATERTHAN 1 | |
36 | ||
37 | static void order_and_dump_functions_by_arcs PARAMS ((Arc **, unsigned long, | |
38 | int, Arc **, | |
39 | unsigned long *)); | |
ef368dac | 40 | /* Declarations of automatically generated functions to output blurbs. */ |
252b5132 RH |
41 | extern void bsd_callg_blurb PARAMS ((FILE * fp)); |
42 | extern void fsf_callg_blurb PARAMS ((FILE * fp)); | |
43 | ||
44 | double print_time = 0.0; | |
45 | ||
46 | ||
47 | static void | |
48 | DEFUN_VOID (print_header) | |
49 | { | |
50 | if (first_output) | |
ef368dac | 51 | first_output = FALSE; |
252b5132 | 52 | else |
ef368dac | 53 | printf ("\f\n"); |
0eee5820 | 54 | |
252b5132 RH |
55 | if (!bsd_style_output) |
56 | { | |
57 | if (print_descriptions) | |
ef368dac | 58 | printf (_("\t\t Call graph (explanation follows)\n\n")); |
252b5132 | 59 | else |
ef368dac | 60 | printf (_("\t\t\tCall graph\n\n")); |
252b5132 | 61 | } |
0eee5820 | 62 | |
252b5132 RH |
63 | printf (_("\ngranularity: each sample hit covers %ld byte(s)"), |
64 | (long) hist_scale * sizeof (UNIT)); | |
0eee5820 | 65 | |
252b5132 | 66 | if (print_time > 0.0) |
ef368dac NC |
67 | printf (_(" for %.2f%% of %.2f seconds\n\n"), |
68 | 100.0 / print_time, print_time / hz); | |
252b5132 RH |
69 | else |
70 | { | |
71 | printf (_(" no time propagated\n\n")); | |
0eee5820 | 72 | |
ef368dac | 73 | /* This doesn't hurt, since all the numerators will be 0.0. */ |
252b5132 RH |
74 | print_time = 1.0; |
75 | } | |
0eee5820 | 76 | |
252b5132 RH |
77 | if (bsd_style_output) |
78 | { | |
79 | printf ("%6.6s %5.5s %7.7s %11.11s %7.7s/%-7.7s %-8.8s\n", | |
80 | "", "", "", "", _("called"), _("total"), _("parents")); | |
81 | printf ("%-6.6s %5.5s %7.7s %11.11s %7.7s+%-7.7s %-8.8s\t%5.5s\n", | |
af6dfb5b | 82 | _("index"), _("%time"), _("self"), _("descendants"), |
252b5132 RH |
83 | _("called"), _("self"), _("name"), _("index")); |
84 | printf ("%6.6s %5.5s %7.7s %11.11s %7.7s/%-7.7s %-8.8s\n", | |
85 | "", "", "", "", _("called"), _("total"), _("children")); | |
86 | printf ("\n"); | |
87 | } | |
88 | else | |
89 | { | |
90 | printf (_("index %% time self children called name\n")); | |
91 | } | |
92 | } | |
93 | ||
ef368dac | 94 | /* Print a cycle header. */ |
252b5132 | 95 | |
252b5132 RH |
96 | static void |
97 | DEFUN (print_cycle, (cyc), Sym * cyc) | |
98 | { | |
99 | char buf[BUFSIZ]; | |
100 | ||
101 | sprintf (buf, "[%d]", cyc->cg.index); | |
102 | printf (bsd_style_output | |
103 | ? "%-6.6s %5.1f %7.2f %11.2f %7lu" | |
104 | : "%-6.6s %5.1f %7.2f %7.2f %7lu", buf, | |
105 | 100 * (cyc->cg.prop.self + cyc->cg.prop.child) / print_time, | |
106 | cyc->cg.prop.self / hz, cyc->cg.prop.child / hz, cyc->ncalls); | |
0eee5820 | 107 | |
252b5132 | 108 | if (cyc->cg.self_calls != 0) |
ef368dac | 109 | printf ("+%-7lu", cyc->cg.self_calls); |
252b5132 | 110 | else |
ef368dac NC |
111 | printf (" %7.7s", ""); |
112 | ||
252b5132 RH |
113 | printf (_(" <cycle %d as a whole> [%d]\n"), cyc->cg.cyc.num, cyc->cg.index); |
114 | } | |
115 | ||
ef368dac NC |
116 | /* Compare LEFT and RIGHT membmer. Major comparison key is |
117 | CG.PROP.SELF+CG.PROP.CHILD, secondary key is NCALLS+CG.SELF_CALLS. */ | |
252b5132 | 118 | |
252b5132 RH |
119 | static int |
120 | DEFUN (cmp_member, (left, right), Sym * left AND Sym * right) | |
121 | { | |
122 | double left_time = left->cg.prop.self + left->cg.prop.child; | |
123 | double right_time = right->cg.prop.self + right->cg.prop.child; | |
124 | unsigned long left_calls = left->ncalls + left->cg.self_calls; | |
125 | unsigned long right_calls = right->ncalls + right->cg.self_calls; | |
126 | ||
127 | if (left_time > right_time) | |
ef368dac NC |
128 | return GREATERTHAN; |
129 | ||
252b5132 | 130 | if (left_time < right_time) |
ef368dac | 131 | return LESSTHAN; |
252b5132 RH |
132 | |
133 | if (left_calls > right_calls) | |
ef368dac NC |
134 | return GREATERTHAN; |
135 | ||
252b5132 | 136 | if (left_calls < right_calls) |
ef368dac NC |
137 | return LESSTHAN; |
138 | ||
252b5132 RH |
139 | return EQUALTO; |
140 | } | |
141 | ||
ef368dac | 142 | /* Sort members of a cycle. */ |
252b5132 | 143 | |
252b5132 RH |
144 | static void |
145 | DEFUN (sort_members, (cyc), Sym * cyc) | |
146 | { | |
147 | Sym *todo, *doing, *prev; | |
0eee5820 | 148 | |
ef368dac NC |
149 | /* Detach cycle members from cyclehead, |
150 | and insertion sort them back on. */ | |
252b5132 RH |
151 | todo = cyc->cg.cyc.next; |
152 | cyc->cg.cyc.next = 0; | |
0eee5820 | 153 | |
252b5132 RH |
154 | for (doing = todo; doing && doing->cg.cyc.next; doing = todo) |
155 | { | |
156 | todo = doing->cg.cyc.next; | |
0eee5820 | 157 | |
252b5132 RH |
158 | for (prev = cyc; prev->cg.cyc.next; prev = prev->cg.cyc.next) |
159 | { | |
160 | if (cmp_member (doing, prev->cg.cyc.next) == GREATERTHAN) | |
ef368dac | 161 | break; |
252b5132 | 162 | } |
0eee5820 | 163 | |
252b5132 RH |
164 | doing->cg.cyc.next = prev->cg.cyc.next; |
165 | prev->cg.cyc.next = doing; | |
166 | } | |
167 | } | |
168 | ||
ef368dac | 169 | /* Print the members of a cycle. */ |
252b5132 | 170 | |
252b5132 RH |
171 | static void |
172 | DEFUN (print_members, (cyc), Sym * cyc) | |
173 | { | |
174 | Sym *member; | |
175 | ||
176 | sort_members (cyc); | |
0eee5820 | 177 | |
252b5132 RH |
178 | for (member = cyc->cg.cyc.next; member; member = member->cg.cyc.next) |
179 | { | |
180 | printf (bsd_style_output | |
181 | ? "%6.6s %5.5s %7.2f %11.2f %7lu" | |
182 | : "%6.6s %5.5s %7.2f %7.2f %7lu", | |
183 | "", "", member->cg.prop.self / hz, member->cg.prop.child / hz, | |
184 | member->ncalls); | |
0eee5820 | 185 | |
252b5132 | 186 | if (member->cg.self_calls != 0) |
ef368dac | 187 | printf ("+%-7lu", member->cg.self_calls); |
252b5132 | 188 | else |
ef368dac NC |
189 | printf (" %7.7s", ""); |
190 | ||
252b5132 RH |
191 | printf (" "); |
192 | print_name (member); | |
193 | printf ("\n"); | |
194 | } | |
195 | } | |
196 | ||
ef368dac | 197 | /* Compare two arcs to/from the same child/parent. |
0eee5820 AM |
198 | - if one arc is a self arc, it's least. |
199 | - if one arc is within a cycle, it's less than. | |
200 | - if both arcs are within a cycle, compare arc counts. | |
201 | - if neither arc is within a cycle, compare with | |
202 | time + child_time as major key | |
203 | arc count as minor key. */ | |
252b5132 | 204 | |
252b5132 RH |
205 | static int |
206 | DEFUN (cmp_arc, (left, right), Arc * left AND Arc * right) | |
207 | { | |
208 | Sym *left_parent = left->parent; | |
209 | Sym *left_child = left->child; | |
210 | Sym *right_parent = right->parent; | |
211 | Sym *right_child = right->child; | |
212 | double left_time, right_time; | |
213 | ||
214 | DBG (TIMEDEBUG, | |
215 | printf ("[cmp_arc] "); | |
216 | print_name (left_parent); | |
217 | printf (" calls "); | |
218 | print_name (left_child); | |
219 | printf (" %f + %f %lu/%lu\n", left->time, left->child_time, | |
220 | left->count, left_child->ncalls); | |
221 | printf ("[cmp_arc] "); | |
222 | print_name (right_parent); | |
223 | printf (" calls "); | |
224 | print_name (right_child); | |
225 | printf (" %f + %f %lu/%lu\n", right->time, right->child_time, | |
226 | right->count, right_child->ncalls); | |
227 | printf ("\n"); | |
228 | ); | |
0eee5820 | 229 | |
252b5132 | 230 | if (left_parent == left_child) |
ef368dac NC |
231 | return LESSTHAN; /* Left is a self call. */ |
232 | ||
252b5132 | 233 | if (right_parent == right_child) |
ef368dac | 234 | return GREATERTHAN; /* Right is a self call. */ |
252b5132 RH |
235 | |
236 | if (left_parent->cg.cyc.num != 0 && left_child->cg.cyc.num != 0 | |
237 | && left_parent->cg.cyc.num == left_child->cg.cyc.num) | |
238 | { | |
ef368dac | 239 | /* Left is a call within a cycle. */ |
252b5132 RH |
240 | if (right_parent->cg.cyc.num != 0 && right_child->cg.cyc.num != 0 |
241 | && right_parent->cg.cyc.num == right_child->cg.cyc.num) | |
242 | { | |
ef368dac | 243 | /* Right is a call within the cycle, too. */ |
252b5132 | 244 | if (left->count < right->count) |
ef368dac NC |
245 | return LESSTHAN; |
246 | ||
252b5132 | 247 | if (left->count > right->count) |
ef368dac NC |
248 | return GREATERTHAN; |
249 | ||
252b5132 RH |
250 | return EQUALTO; |
251 | } | |
252 | else | |
253 | { | |
ef368dac | 254 | /* Right isn't a call within the cycle. */ |
252b5132 RH |
255 | return LESSTHAN; |
256 | } | |
257 | } | |
258 | else | |
259 | { | |
ef368dac | 260 | /* Left isn't a call within a cycle. */ |
252b5132 RH |
261 | if (right_parent->cg.cyc.num != 0 && right_child->cg.cyc.num != 0 |
262 | && right_parent->cg.cyc.num == right_child->cg.cyc.num) | |
263 | { | |
ef368dac | 264 | /* Right is a call within a cycle. */ |
252b5132 RH |
265 | return GREATERTHAN; |
266 | } | |
267 | else | |
268 | { | |
ef368dac | 269 | /* Neither is a call within a cycle. */ |
252b5132 RH |
270 | left_time = left->time + left->child_time; |
271 | right_time = right->time + right->child_time; | |
0eee5820 | 272 | |
252b5132 | 273 | if (left_time < right_time) |
ef368dac NC |
274 | return LESSTHAN; |
275 | ||
252b5132 | 276 | if (left_time > right_time) |
ef368dac NC |
277 | return GREATERTHAN; |
278 | ||
252b5132 | 279 | if (left->count < right->count) |
ef368dac NC |
280 | return LESSTHAN; |
281 | ||
252b5132 | 282 | if (left->count > right->count) |
ef368dac NC |
283 | return GREATERTHAN; |
284 | ||
252b5132 RH |
285 | return EQUALTO; |
286 | } | |
287 | } | |
288 | } | |
289 | ||
290 | ||
291 | static void | |
292 | DEFUN (sort_parents, (child), Sym * child) | |
293 | { | |
294 | Arc *arc, *detached, sorted, *prev; | |
295 | ||
ef368dac NC |
296 | /* Unlink parents from child, then insertion sort back on to |
297 | sorted's parents. | |
0eee5820 AM |
298 | *arc the arc you have detached and are inserting. |
299 | *detached the rest of the arcs to be sorted. | |
300 | sorted arc list onto which you insertion sort. | |
301 | *prev arc before the arc you are comparing. */ | |
252b5132 | 302 | sorted.next_parent = 0; |
0eee5820 | 303 | |
252b5132 RH |
304 | for (arc = child->cg.parents; arc; arc = detached) |
305 | { | |
306 | detached = arc->next_parent; | |
307 | ||
ef368dac | 308 | /* Consider *arc as disconnected; insert it into sorted. */ |
252b5132 RH |
309 | for (prev = &sorted; prev->next_parent; prev = prev->next_parent) |
310 | { | |
311 | if (cmp_arc (arc, prev->next_parent) != GREATERTHAN) | |
ef368dac | 312 | break; |
252b5132 | 313 | } |
0eee5820 | 314 | |
252b5132 RH |
315 | arc->next_parent = prev->next_parent; |
316 | prev->next_parent = arc; | |
317 | } | |
318 | ||
ef368dac | 319 | /* Reattach sorted arcs to child. */ |
252b5132 RH |
320 | child->cg.parents = sorted.next_parent; |
321 | } | |
322 | ||
323 | ||
324 | static void | |
325 | DEFUN (print_parents, (child), Sym * child) | |
326 | { | |
327 | Sym *parent; | |
328 | Arc *arc; | |
329 | Sym *cycle_head; | |
330 | ||
331 | if (child->cg.cyc.head != 0) | |
ef368dac | 332 | cycle_head = child->cg.cyc.head; |
252b5132 | 333 | else |
ef368dac | 334 | cycle_head = child; |
0eee5820 | 335 | |
252b5132 RH |
336 | if (!child->cg.parents) |
337 | { | |
338 | printf (bsd_style_output | |
339 | ? _("%6.6s %5.5s %7.7s %11.11s %7.7s %7.7s <spontaneous>\n") | |
340 | : _("%6.6s %5.5s %7.7s %7.7s %7.7s %7.7s <spontaneous>\n"), | |
341 | "", "", "", "", "", ""); | |
342 | return; | |
343 | } | |
0eee5820 | 344 | |
252b5132 | 345 | sort_parents (child); |
0eee5820 | 346 | |
252b5132 RH |
347 | for (arc = child->cg.parents; arc; arc = arc->next_parent) |
348 | { | |
349 | parent = arc->parent; | |
350 | if (child == parent || (child->cg.cyc.num != 0 | |
351 | && parent->cg.cyc.num == child->cg.cyc.num)) | |
352 | { | |
ef368dac | 353 | /* Selfcall or call among siblings. */ |
252b5132 RH |
354 | printf (bsd_style_output |
355 | ? "%6.6s %5.5s %7.7s %11.11s %7lu %7.7s " | |
356 | : "%6.6s %5.5s %7.7s %7.7s %7lu %7.7s ", | |
357 | "", "", "", "", | |
358 | arc->count, ""); | |
359 | print_name (parent); | |
360 | printf ("\n"); | |
361 | } | |
362 | else | |
363 | { | |
ef368dac | 364 | /* Regular parent of child. */ |
252b5132 RH |
365 | printf (bsd_style_output |
366 | ? "%6.6s %5.5s %7.2f %11.2f %7lu/%-7lu " | |
367 | : "%6.6s %5.5s %7.2f %7.2f %7lu/%-7lu ", | |
368 | "", "", | |
369 | arc->time / hz, arc->child_time / hz, | |
370 | arc->count, cycle_head->ncalls); | |
371 | print_name (parent); | |
372 | printf ("\n"); | |
373 | } | |
374 | } | |
375 | } | |
376 | ||
377 | ||
378 | static void | |
379 | DEFUN (sort_children, (parent), Sym * parent) | |
380 | { | |
381 | Arc *arc, *detached, sorted, *prev; | |
0eee5820 | 382 | |
ef368dac NC |
383 | /* Unlink children from parent, then insertion sort back on to |
384 | sorted's children. | |
0eee5820 AM |
385 | *arc the arc you have detached and are inserting. |
386 | *detached the rest of the arcs to be sorted. | |
387 | sorted arc list onto which you insertion sort. | |
388 | *prev arc before the arc you are comparing. */ | |
252b5132 | 389 | sorted.next_child = 0; |
0eee5820 | 390 | |
252b5132 RH |
391 | for (arc = parent->cg.children; arc; arc = detached) |
392 | { | |
393 | detached = arc->next_child; | |
394 | ||
ef368dac | 395 | /* Consider *arc as disconnected; insert it into sorted. */ |
252b5132 RH |
396 | for (prev = &sorted; prev->next_child; prev = prev->next_child) |
397 | { | |
398 | if (cmp_arc (arc, prev->next_child) != LESSTHAN) | |
ef368dac | 399 | break; |
252b5132 | 400 | } |
0eee5820 | 401 | |
252b5132 RH |
402 | arc->next_child = prev->next_child; |
403 | prev->next_child = arc; | |
404 | } | |
405 | ||
ef368dac | 406 | /* Reattach sorted children to parent. */ |
252b5132 RH |
407 | parent->cg.children = sorted.next_child; |
408 | } | |
409 | ||
410 | ||
411 | static void | |
412 | DEFUN (print_children, (parent), Sym * parent) | |
413 | { | |
414 | Sym *child; | |
415 | Arc *arc; | |
416 | ||
417 | sort_children (parent); | |
418 | arc = parent->cg.children; | |
0eee5820 | 419 | |
252b5132 RH |
420 | for (arc = parent->cg.children; arc; arc = arc->next_child) |
421 | { | |
422 | child = arc->child; | |
423 | if (child == parent || (child->cg.cyc.num != 0 | |
424 | && child->cg.cyc.num == parent->cg.cyc.num)) | |
425 | { | |
ef368dac | 426 | /* Self call or call to sibling. */ |
252b5132 RH |
427 | printf (bsd_style_output |
428 | ? "%6.6s %5.5s %7.7s %11.11s %7lu %7.7s " | |
429 | : "%6.6s %5.5s %7.7s %7.7s %7lu %7.7s ", | |
430 | "", "", "", "", arc->count, ""); | |
431 | print_name (child); | |
432 | printf ("\n"); | |
433 | } | |
434 | else | |
435 | { | |
ef368dac | 436 | /* Regular child of parent. */ |
252b5132 RH |
437 | printf (bsd_style_output |
438 | ? "%6.6s %5.5s %7.2f %11.2f %7lu/%-7lu " | |
439 | : "%6.6s %5.5s %7.2f %7.2f %7lu/%-7lu ", | |
440 | "", "", | |
441 | arc->time / hz, arc->child_time / hz, | |
442 | arc->count, child->cg.cyc.head->ncalls); | |
443 | print_name (child); | |
444 | printf ("\n"); | |
445 | } | |
446 | } | |
447 | } | |
448 | ||
449 | ||
450 | static void | |
451 | DEFUN (print_line, (np), Sym * np) | |
452 | { | |
453 | char buf[BUFSIZ]; | |
454 | ||
455 | sprintf (buf, "[%d]", np->cg.index); | |
456 | printf (bsd_style_output | |
457 | ? "%-6.6s %5.1f %7.2f %11.2f" | |
458 | : "%-6.6s %5.1f %7.2f %7.2f", buf, | |
459 | 100 * (np->cg.prop.self + np->cg.prop.child) / print_time, | |
460 | np->cg.prop.self / hz, np->cg.prop.child / hz); | |
0eee5820 | 461 | |
252b5132 RH |
462 | if ((np->ncalls + np->cg.self_calls) != 0) |
463 | { | |
464 | printf (" %7lu", np->ncalls); | |
0eee5820 | 465 | |
252b5132 | 466 | if (np->cg.self_calls != 0) |
252b5132 | 467 | printf ("+%-7lu ", np->cg.self_calls); |
252b5132 | 468 | else |
252b5132 | 469 | printf (" %7.7s ", ""); |
252b5132 RH |
470 | } |
471 | else | |
472 | { | |
473 | printf (" %7.7s %7.7s ", "", ""); | |
474 | } | |
0eee5820 | 475 | |
252b5132 RH |
476 | print_name (np); |
477 | printf ("\n"); | |
478 | } | |
479 | ||
480 | ||
ef368dac NC |
481 | /* Print dynamic call graph. */ |
482 | ||
252b5132 RH |
483 | void |
484 | DEFUN (cg_print, (timesortsym), Sym ** timesortsym) | |
485 | { | |
486 | unsigned int index; | |
487 | Sym *parent; | |
488 | ||
489 | if (print_descriptions && bsd_style_output) | |
ef368dac | 490 | bsd_callg_blurb (stdout); |
252b5132 RH |
491 | |
492 | print_header (); | |
493 | ||
494 | for (index = 0; index < symtab.len + num_cycles; ++index) | |
495 | { | |
496 | parent = timesortsym[index]; | |
0eee5820 | 497 | |
252b5132 RH |
498 | if ((ignore_zeros && parent->ncalls == 0 |
499 | && parent->cg.self_calls == 0 && parent->cg.prop.self == 0 | |
500 | && parent->cg.prop.child == 0) | |
501 | || !parent->cg.print_flag | |
502 | || (line_granularity && ! parent->is_func)) | |
ef368dac | 503 | continue; |
0eee5820 | 504 | |
252b5132 RH |
505 | if (!parent->name && parent->cg.cyc.num != 0) |
506 | { | |
ef368dac | 507 | /* Cycle header. */ |
252b5132 RH |
508 | print_cycle (parent); |
509 | print_members (parent); | |
510 | } | |
511 | else | |
512 | { | |
513 | print_parents (parent); | |
514 | print_line (parent); | |
515 | print_children (parent); | |
516 | } | |
0eee5820 | 517 | |
252b5132 RH |
518 | if (bsd_style_output) |
519 | printf ("\n"); | |
0eee5820 | 520 | |
252b5132 | 521 | printf ("-----------------------------------------------\n"); |
0eee5820 | 522 | |
252b5132 RH |
523 | if (bsd_style_output) |
524 | printf ("\n"); | |
525 | } | |
0eee5820 | 526 | |
252b5132 | 527 | free (timesortsym); |
0eee5820 | 528 | |
252b5132 | 529 | if (print_descriptions && !bsd_style_output) |
ef368dac | 530 | fsf_callg_blurb (stdout); |
252b5132 RH |
531 | } |
532 | ||
533 | ||
534 | static int | |
535 | DEFUN (cmp_name, (left, right), const PTR left AND const PTR right) | |
536 | { | |
537 | const Sym **npp1 = (const Sym **) left; | |
538 | const Sym **npp2 = (const Sym **) right; | |
539 | ||
540 | return strcmp ((*npp1)->name, (*npp2)->name); | |
541 | } | |
542 | ||
543 | ||
544 | void | |
545 | DEFUN_VOID (cg_print_index) | |
546 | { | |
547 | unsigned int index; | |
548 | unsigned int nnames, todo, i, j; | |
549 | int col, starting_col; | |
550 | Sym **name_sorted_syms, *sym; | |
551 | const char *filename; | |
552 | char buf[20]; | |
ef368dac | 553 | int column_width = (output_width - 1) / 3; /* Don't write in last col! */ |
0eee5820 | 554 | |
ef368dac NC |
555 | /* Now, sort regular function name |
556 | alphabetically to create an index. */ | |
252b5132 | 557 | name_sorted_syms = (Sym **) xmalloc ((symtab.len + num_cycles) * sizeof (Sym *)); |
0eee5820 | 558 | |
252b5132 RH |
559 | for (index = 0, nnames = 0; index < symtab.len; index++) |
560 | { | |
561 | if (ignore_zeros && symtab.base[index].ncalls == 0 | |
562 | && symtab.base[index].hist.time == 0) | |
ef368dac NC |
563 | continue; |
564 | ||
252b5132 RH |
565 | name_sorted_syms[nnames++] = &symtab.base[index]; |
566 | } | |
0eee5820 | 567 | |
252b5132 | 568 | qsort (name_sorted_syms, nnames, sizeof (Sym *), cmp_name); |
0eee5820 | 569 | |
252b5132 | 570 | for (index = 1, todo = nnames; index <= num_cycles; index++) |
ef368dac NC |
571 | name_sorted_syms[todo++] = &cycle_header[index]; |
572 | ||
252b5132 RH |
573 | printf ("\f\n"); |
574 | printf (_("Index by function name\n\n")); | |
575 | index = (todo + 2) / 3; | |
0eee5820 | 576 | |
252b5132 RH |
577 | for (i = 0; i < index; i++) |
578 | { | |
579 | col = 0; | |
580 | starting_col = 0; | |
0eee5820 | 581 | |
252b5132 RH |
582 | for (j = i; j < todo; j += index) |
583 | { | |
584 | sym = name_sorted_syms[j]; | |
0eee5820 | 585 | |
252b5132 | 586 | if (sym->cg.print_flag) |
ef368dac | 587 | sprintf (buf, "[%d]", sym->cg.index); |
252b5132 | 588 | else |
ef368dac NC |
589 | sprintf (buf, "(%d)", sym->cg.index); |
590 | ||
252b5132 RH |
591 | if (j < nnames) |
592 | { | |
593 | if (bsd_style_output) | |
594 | { | |
595 | printf ("%6.6s %-19.19s", buf, sym->name); | |
596 | } | |
597 | else | |
598 | { | |
599 | col += strlen (buf); | |
0eee5820 | 600 | |
252b5132 | 601 | for (; col < starting_col + 5; ++col) |
ef368dac NC |
602 | putchar (' '); |
603 | ||
252b5132 RH |
604 | printf (" %s ", buf); |
605 | col += print_name_only (sym); | |
0eee5820 | 606 | |
252b5132 RH |
607 | if (!line_granularity && sym->is_static && sym->file) |
608 | { | |
609 | filename = sym->file->name; | |
0eee5820 | 610 | |
252b5132 RH |
611 | if (!print_path) |
612 | { | |
613 | filename = strrchr (filename, '/'); | |
0eee5820 | 614 | |
252b5132 | 615 | if (filename) |
ef368dac | 616 | ++filename; |
252b5132 | 617 | else |
ef368dac | 618 | filename = sym->file->name; |
252b5132 | 619 | } |
0eee5820 | 620 | |
252b5132 RH |
621 | printf (" (%s)", filename); |
622 | col += strlen (filename) + 3; | |
623 | } | |
624 | } | |
625 | } | |
626 | else | |
627 | { | |
628 | if (bsd_style_output) | |
629 | { | |
630 | printf ("%6.6s ", buf); | |
631 | sprintf (buf, _("<cycle %d>"), sym->cg.cyc.num); | |
632 | printf ("%-19.19s", buf); | |
633 | } | |
634 | else | |
635 | { | |
636 | col += strlen (buf); | |
637 | for (; col < starting_col + 5; ++col) | |
638 | putchar (' '); | |
639 | printf (" %s ", buf); | |
640 | sprintf (buf, _("<cycle %d>"), sym->cg.cyc.num); | |
641 | printf ("%s", buf); | |
642 | col += strlen (buf); | |
643 | } | |
644 | } | |
0eee5820 | 645 | |
252b5132 RH |
646 | starting_col += column_width; |
647 | } | |
0eee5820 | 648 | |
252b5132 RH |
649 | printf ("\n"); |
650 | } | |
0eee5820 | 651 | |
252b5132 RH |
652 | free (name_sorted_syms); |
653 | } | |
654 | ||
ef368dac NC |
655 | /* Compare two arcs based on their usage counts. |
656 | We want to sort in descending order. */ | |
657 | ||
252b5132 RH |
658 | static int |
659 | DEFUN (cmp_arc_count, (left, right), const PTR left AND const PTR right) | |
660 | { | |
661 | const Arc **npp1 = (const Arc **) left; | |
662 | const Arc **npp2 = (const Arc **) right; | |
663 | ||
664 | if ((*npp1)->count > (*npp2)->count) | |
665 | return -1; | |
666 | else if ((*npp1)->count < (*npp2)->count) | |
667 | return 1; | |
668 | else | |
669 | return 0; | |
670 | } | |
671 | ||
ef368dac NC |
672 | /* Compare two funtions based on their usage counts. |
673 | We want to sort in descending order. */ | |
674 | ||
252b5132 RH |
675 | static int |
676 | DEFUN (cmp_fun_nuses, (left, right), const PTR left AND const PTR right) | |
677 | { | |
678 | const Sym **npp1 = (const Sym **) left; | |
679 | const Sym **npp2 = (const Sym **) right; | |
680 | ||
681 | if ((*npp1)->nuses > (*npp2)->nuses) | |
682 | return -1; | |
683 | else if ((*npp1)->nuses < (*npp2)->nuses) | |
684 | return 1; | |
685 | else | |
686 | return 0; | |
687 | } | |
688 | ||
689 | /* Print a suggested function ordering based on the profiling data. | |
690 | ||
691 | We perform 4 major steps when ordering functions: | |
692 | ||
693 | * Group unused functions together and place them at the | |
694 | end of the function order. | |
695 | ||
696 | * Search the highest use arcs (those which account for 90% of | |
697 | the total arc count) for functions which have several parents. | |
698 | ||
699 | Group those with the most call sites together (currently the | |
700 | top 1.25% which have at least five different call sites). | |
701 | ||
702 | These are emitted at the start of the function order. | |
703 | ||
704 | * Use a greedy placement algorithm to place functions which | |
705 | occur in the top 99% of the arcs in the profile. Some provisions | |
706 | are made to handle high usage arcs where the parent and/or | |
707 | child has already been placed. | |
708 | ||
709 | * Run the same greedy placement algorithm on the remaining | |
710 | arcs to place the leftover functions. | |
711 | ||
712 | ||
713 | The various "magic numbers" should (one day) be tuneable by command | |
714 | line options. They were arrived at by benchmarking a few applications | |
715 | with various values to see which values produced better overall function | |
716 | orderings. | |
717 | ||
718 | Of course, profiling errors, machine limitations (PA long calls), and | |
719 | poor cutoff values for the placement algorithm may limit the usefullness | |
720 | of the resulting function order. Improvements would be greatly appreciated. | |
0eee5820 | 721 | |
252b5132 RH |
722 | Suggestions: |
723 | ||
724 | * Place the functions with many callers near the middle of the | |
725 | list to reduce long calls. | |
726 | ||
727 | * Propagate arc usage changes as functions are placed. Ie if | |
728 | func1 and func2 are placed together, arcs to/from those arcs | |
729 | to the same parent/child should be combined, then resort the | |
730 | arcs to choose the next one. | |
731 | ||
732 | * Implement some global positioning algorithm to place the | |
733 | chains made by the greedy local positioning algorithm. Probably | |
734 | by examining arcs which haven't been placed yet to tie two | |
735 | chains together. | |
736 | ||
737 | * Take a function's size and time into account in the algorithm; | |
738 | size in particular is important on the PA (long calls). Placing | |
739 | many small functions onto their own page may be wise. | |
740 | ||
741 | * Use better profiling information; many published algorithms | |
742 | are based on call sequences through time, rather than just | |
743 | arc counts. | |
744 | ||
745 | * Prodecure cloning could improve performance when a small number | |
746 | of arcs account for most of the calls to a particular function. | |
747 | ||
748 | * Use relocation information to avoid moving unused functions | |
749 | completely out of the code stream; this would avoid severe lossage | |
750 | when the profile data bears little resemblance to actual runs. | |
751 | ||
752 | * Propagation of arc usages should also improve .o link line | |
753 | ordering which shares the same arc placement algorithm with | |
754 | the function ordering code (in fact it is a degenerate case | |
755 | of function ordering). */ | |
0eee5820 | 756 | |
252b5132 RH |
757 | void |
758 | DEFUN_VOID (cg_print_function_ordering) | |
759 | { | |
760 | unsigned long index, used, unused, scratch_index; | |
761 | unsigned long unplaced_arc_count, high_arc_count, scratch_arc_count; | |
762 | #ifdef __GNUC__ | |
763 | unsigned long long total_arcs, tmp_arcs_count; | |
764 | #else | |
765 | unsigned long total_arcs, tmp_arcs_count; | |
766 | #endif | |
767 | Sym **unused_syms, **used_syms, **scratch_syms; | |
768 | Arc **unplaced_arcs, **high_arcs, **scratch_arcs; | |
769 | ||
770 | index = 0; | |
771 | used = 0; | |
772 | unused = 0; | |
773 | scratch_index = 0; | |
774 | unplaced_arc_count = 0; | |
775 | high_arc_count = 0; | |
776 | scratch_arc_count = 0; | |
777 | ||
778 | /* First group all the unused functions together. */ | |
779 | unused_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *)); | |
780 | used_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *)); | |
781 | scratch_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *)); | |
782 | high_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *)); | |
783 | scratch_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *)); | |
784 | unplaced_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *)); | |
785 | ||
786 | /* Walk through all the functions; mark those which are never | |
787 | called as placed (we'll emit them as a group later). */ | |
788 | for (index = 0, used = 0, unused = 0; index < symtab.len; index++) | |
789 | { | |
790 | if (symtab.base[index].ncalls == 0) | |
791 | { | |
792 | /* Filter out gprof generated names. */ | |
793 | if (strcmp (symtab.base[index].name, "<locore>") | |
794 | && strcmp (symtab.base[index].name, "<hicore>")) | |
795 | { | |
796 | unused_syms[unused++] = &symtab.base[index]; | |
797 | symtab.base[index].has_been_placed = 1; | |
798 | } | |
799 | } | |
800 | else | |
801 | { | |
802 | used_syms[used++] = &symtab.base[index]; | |
803 | symtab.base[index].has_been_placed = 0; | |
804 | symtab.base[index].next = 0; | |
805 | symtab.base[index].prev = 0; | |
806 | symtab.base[index].nuses = 0; | |
807 | } | |
808 | } | |
809 | ||
810 | /* Sort the arcs from most used to least used. */ | |
811 | qsort (arcs, numarcs, sizeof (Arc *), cmp_arc_count); | |
812 | ||
813 | /* Compute the total arc count. Also mark arcs as unplaced. | |
814 | ||
815 | Note we don't compensate for overflow if that happens! | |
816 | Overflow is much less likely when this file is compiled | |
817 | with GCC as it can double-wide integers via long long. */ | |
818 | total_arcs = 0; | |
819 | for (index = 0; index < numarcs; index++) | |
820 | { | |
821 | total_arcs += arcs[index]->count; | |
822 | arcs[index]->has_been_placed = 0; | |
823 | } | |
824 | ||
825 | /* We want to pull out those functions which are referenced | |
826 | by many highly used arcs and emit them as a group. This | |
827 | could probably use some tuning. */ | |
828 | tmp_arcs_count = 0; | |
829 | for (index = 0; index < numarcs; index++) | |
830 | { | |
831 | tmp_arcs_count += arcs[index]->count; | |
832 | ||
833 | /* Count how many times each parent and child are used up | |
834 | to our threshhold of arcs (90%). */ | |
835 | if ((double)tmp_arcs_count / (double)total_arcs > 0.90) | |
836 | break; | |
837 | ||
838 | arcs[index]->child->nuses++; | |
839 | } | |
840 | ||
841 | /* Now sort a temporary symbol table based on the number of | |
842 | times each function was used in the highest used arcs. */ | |
843 | memcpy (scratch_syms, used_syms, used * sizeof (Sym *)); | |
844 | qsort (scratch_syms, used, sizeof (Sym *), cmp_fun_nuses); | |
845 | ||
846 | /* Now pick out those symbols we're going to emit as | |
847 | a group. We take up to 1.25% of the used symbols. */ | |
848 | for (index = 0; index < used / 80; index++) | |
849 | { | |
850 | Sym *sym = scratch_syms[index]; | |
851 | Arc *arc; | |
852 | ||
853 | /* If we hit symbols that aren't used from many call sites, | |
854 | then we can quit. We choose five as the low limit for | |
855 | no particular reason. */ | |
856 | if (sym->nuses == 5) | |
857 | break; | |
858 | ||
859 | /* We're going to need the arcs between these functions. | |
860 | Unfortunately, we don't know all these functions | |
861 | until we're done. So we keep track of all the arcs | |
862 | to the functions we care about, then prune out those | |
0eee5820 | 863 | which are uninteresting. |
252b5132 RH |
864 | |
865 | An interesting variation would be to quit when we found | |
866 | multi-call site functions which account for some percentage | |
867 | of the arcs. */ | |
252b5132 | 868 | arc = sym->cg.children; |
0eee5820 | 869 | |
252b5132 RH |
870 | while (arc) |
871 | { | |
872 | if (arc->parent != arc->child) | |
873 | scratch_arcs[scratch_arc_count++] = arc; | |
874 | arc->has_been_placed = 1; | |
875 | arc = arc->next_child; | |
876 | } | |
877 | ||
878 | arc = sym->cg.parents; | |
0eee5820 | 879 | |
252b5132 RH |
880 | while (arc) |
881 | { | |
882 | if (arc->parent != arc->child) | |
883 | scratch_arcs[scratch_arc_count++] = arc; | |
884 | arc->has_been_placed = 1; | |
885 | arc = arc->next_parent; | |
886 | } | |
887 | ||
888 | /* Keep track of how many symbols we're going to place. */ | |
889 | scratch_index = index; | |
890 | ||
ef368dac NC |
891 | /* A lie, but it makes identifying |
892 | these functions easier later. */ | |
252b5132 RH |
893 | sym->has_been_placed = 1; |
894 | } | |
895 | ||
ef368dac NC |
896 | /* Now walk through the temporary arcs and copy |
897 | those we care about into the high arcs array. */ | |
252b5132 RH |
898 | for (index = 0; index < scratch_arc_count; index++) |
899 | { | |
900 | Arc *arc = scratch_arcs[index]; | |
901 | ||
902 | /* If this arc refers to highly used functions, then | |
903 | then we want to keep it. */ | |
904 | if (arc->child->has_been_placed | |
905 | && arc->parent->has_been_placed) | |
906 | { | |
907 | high_arcs[high_arc_count++] = scratch_arcs[index]; | |
908 | ||
909 | /* We need to turn of has_been_placed since we're going to | |
910 | use the main arc placement algorithm on these arcs. */ | |
911 | arc->child->has_been_placed = 0; | |
912 | arc->parent->has_been_placed = 0; | |
913 | } | |
914 | } | |
915 | ||
ef368dac NC |
916 | /* Dump the multi-site high usage functions which are not |
917 | going to be ordered by the main ordering algorithm. */ | |
252b5132 RH |
918 | for (index = 0; index < scratch_index; index++) |
919 | { | |
920 | if (scratch_syms[index]->has_been_placed) | |
921 | printf ("%s\n", scratch_syms[index]->name); | |
922 | } | |
923 | ||
ef368dac NC |
924 | /* Now we can order the multi-site high use |
925 | functions based on the arcs between them. */ | |
252b5132 RH |
926 | qsort (high_arcs, high_arc_count, sizeof (Arc *), cmp_arc_count); |
927 | order_and_dump_functions_by_arcs (high_arcs, high_arc_count, 1, | |
928 | unplaced_arcs, &unplaced_arc_count); | |
929 | ||
ef368dac NC |
930 | /* Order and dump the high use functions left, |
931 | these typically have only a few call sites. */ | |
252b5132 RH |
932 | order_and_dump_functions_by_arcs (arcs, numarcs, 0, |
933 | unplaced_arcs, &unplaced_arc_count); | |
934 | ||
935 | /* Now place the rarely used functions. */ | |
936 | order_and_dump_functions_by_arcs (unplaced_arcs, unplaced_arc_count, 1, | |
937 | scratch_arcs, &scratch_arc_count); | |
938 | ||
939 | /* Output any functions not emitted by the order_and_dump calls. */ | |
940 | for (index = 0; index < used; index++) | |
941 | if (used_syms[index]->has_been_placed == 0) | |
942 | printf("%s\n", used_syms[index]->name); | |
943 | ||
944 | /* Output the unused functions. */ | |
945 | for (index = 0; index < unused; index++) | |
946 | printf("%s\n", unused_syms[index]->name); | |
947 | ||
948 | unused_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *)); | |
949 | used_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *)); | |
950 | scratch_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *)); | |
951 | high_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *)); | |
952 | scratch_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *)); | |
953 | unplaced_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *)); | |
954 | ||
955 | free (unused_syms); | |
956 | free (used_syms); | |
957 | free (scratch_syms); | |
958 | free (high_arcs); | |
959 | free (scratch_arcs); | |
960 | free (unplaced_arcs); | |
961 | } | |
962 | ||
963 | /* Place functions based on the arcs in ARCS with NUMARCS entries; | |
964 | place unused arcs into UNPLACED_ARCS/UNPLACED_ARC_COUNT. | |
965 | ||
966 | If ALL is nonzero, then place all functions referenced by ARCS, | |
967 | else only place those referenced in the top 99% of the arcs in ARCS. */ | |
968 | ||
969 | #define MOST 0.99 | |
970 | static void | |
971 | order_and_dump_functions_by_arcs (arcs, numarcs, all, | |
972 | unplaced_arcs, unplaced_arc_count) | |
973 | Arc **arcs; | |
974 | unsigned long numarcs; | |
975 | int all; | |
976 | Arc **unplaced_arcs; | |
977 | unsigned long *unplaced_arc_count; | |
978 | { | |
979 | #ifdef __GNUC__ | |
980 | unsigned long long tmp_arcs, total_arcs; | |
981 | #else | |
982 | unsigned long tmp_arcs, total_arcs; | |
983 | #endif | |
984 | unsigned int index; | |
985 | ||
986 | /* If needed, compute the total arc count. | |
987 | ||
988 | Note we don't compensate for overflow if that happens! */ | |
989 | if (! all) | |
990 | { | |
991 | total_arcs = 0; | |
992 | for (index = 0; index < numarcs; index++) | |
993 | total_arcs += arcs[index]->count; | |
994 | } | |
995 | else | |
996 | total_arcs = 0; | |
997 | ||
998 | tmp_arcs = 0; | |
0eee5820 | 999 | |
252b5132 RH |
1000 | for (index = 0; index < numarcs; index++) |
1001 | { | |
1002 | Sym *sym1, *sym2; | |
1003 | Sym *child, *parent; | |
1004 | ||
1005 | tmp_arcs += arcs[index]->count; | |
1006 | ||
1007 | /* Ignore this arc if it's already been placed. */ | |
1008 | if (arcs[index]->has_been_placed) | |
1009 | continue; | |
1010 | ||
1011 | child = arcs[index]->child; | |
1012 | parent = arcs[index]->parent; | |
1013 | ||
1014 | /* If we're not using all arcs, and this is a rarely used | |
1015 | arc, then put it on the unplaced_arc list. Similarly | |
1016 | if both the parent and child of this arc have been placed. */ | |
1017 | if ((! all && (double)tmp_arcs / (double)total_arcs > MOST) | |
1018 | || child->has_been_placed || parent->has_been_placed) | |
1019 | { | |
1020 | unplaced_arcs[(*unplaced_arc_count)++] = arcs[index]; | |
1021 | continue; | |
1022 | } | |
1023 | ||
1024 | /* If all slots in the parent and child are full, then there isn't | |
1025 | anything we can do right now. We'll place this arc on the | |
1026 | unplaced arc list in the hope that a global positioning | |
1027 | algorithm can use it to place function chains. */ | |
1028 | if (parent->next && parent->prev && child->next && child->prev) | |
1029 | { | |
1030 | unplaced_arcs[(*unplaced_arc_count)++] = arcs[index]; | |
1031 | continue; | |
1032 | } | |
1033 | ||
1034 | /* If the parent is unattached, then find the closest | |
1035 | place to attach it onto child's chain. Similarly | |
1036 | for the opposite case. */ | |
1037 | if (!parent->next && !parent->prev) | |
1038 | { | |
1039 | int next_count = 0; | |
1040 | int prev_count = 0; | |
1041 | Sym *prev = child; | |
1042 | Sym *next = child; | |
1043 | ||
1044 | /* Walk to the beginning and end of the child's chain. */ | |
1045 | while (next->next) | |
1046 | { | |
1047 | next = next->next; | |
1048 | next_count++; | |
1049 | } | |
1050 | ||
1051 | while (prev->prev) | |
1052 | { | |
1053 | prev = prev->prev; | |
1054 | prev_count++; | |
1055 | } | |
0eee5820 | 1056 | |
252b5132 RH |
1057 | /* Choose the closest. */ |
1058 | child = next_count < prev_count ? next : prev; | |
ef368dac | 1059 | } |
252b5132 RH |
1060 | else if (! child->next && !child->prev) |
1061 | { | |
1062 | int next_count = 0; | |
1063 | int prev_count = 0; | |
1064 | Sym *prev = parent; | |
1065 | Sym *next = parent; | |
1066 | ||
1067 | while (next->next) | |
1068 | { | |
1069 | next = next->next; | |
1070 | next_count++; | |
1071 | } | |
1072 | ||
1073 | while (prev->prev) | |
1074 | { | |
1075 | prev = prev->prev; | |
1076 | prev_count++; | |
1077 | } | |
1078 | ||
1079 | parent = prev_count < next_count ? prev : next; | |
1080 | } | |
1081 | else | |
1082 | { | |
1083 | /* Couldn't find anywhere to attach the functions, | |
1084 | put the arc on the unplaced arc list. */ | |
1085 | unplaced_arcs[(*unplaced_arc_count)++] = arcs[index]; | |
1086 | continue; | |
1087 | } | |
1088 | ||
1089 | /* Make sure we don't tie two ends together. */ | |
1090 | sym1 = parent; | |
1091 | if (sym1->next) | |
1092 | while (sym1->next) | |
1093 | sym1 = sym1->next; | |
1094 | else | |
1095 | while (sym1->prev) | |
1096 | sym1 = sym1->prev; | |
1097 | ||
1098 | sym2 = child; | |
1099 | if (sym2->next) | |
1100 | while (sym2->next) | |
1101 | sym2 = sym2->next; | |
1102 | else | |
1103 | while (sym2->prev) | |
1104 | sym2 = sym2->prev; | |
1105 | ||
1106 | if (sym1 == child | |
1107 | && sym2 == parent) | |
1108 | { | |
1109 | /* This would tie two ends together. */ | |
1110 | unplaced_arcs[(*unplaced_arc_count)++] = arcs[index]; | |
1111 | continue; | |
1112 | } | |
1113 | ||
1114 | if (parent->next) | |
1115 | { | |
1116 | /* Must attach to the parent's prev field. */ | |
1117 | if (! child->next) | |
1118 | { | |
1119 | /* parent-prev and child-next */ | |
1120 | parent->prev = child; | |
1121 | child->next = parent; | |
1122 | arcs[index]->has_been_placed = 1; | |
1123 | } | |
1124 | } | |
1125 | else if (parent->prev) | |
1126 | { | |
1127 | /* Must attach to the parent's next field. */ | |
1128 | if (! child->prev) | |
1129 | { | |
1130 | /* parent-next and child-prev */ | |
1131 | parent->next = child; | |
1132 | child->prev = parent; | |
1133 | arcs[index]->has_been_placed = 1; | |
1134 | } | |
1135 | } | |
1136 | else | |
1137 | { | |
1138 | /* Can attach to either field in the parent, depends | |
1139 | on where we've got space in the child. */ | |
1140 | if (child->prev) | |
1141 | { | |
ef368dac | 1142 | /* parent-prev and child-next. */ |
252b5132 RH |
1143 | parent->prev = child; |
1144 | child->next = parent; | |
1145 | arcs[index]->has_been_placed = 1; | |
1146 | } | |
1147 | else | |
1148 | { | |
ef368dac | 1149 | /* parent-next and child-prev. */ |
252b5132 RH |
1150 | parent->next = child; |
1151 | child->prev = parent; | |
1152 | arcs[index]->has_been_placed = 1; | |
1153 | } | |
1154 | } | |
1155 | } | |
1156 | ||
1157 | /* Dump the chains of functions we've made. */ | |
1158 | for (index = 0; index < numarcs; index++) | |
1159 | { | |
1160 | Sym *sym; | |
1161 | if (arcs[index]->parent->has_been_placed | |
1162 | || arcs[index]->child->has_been_placed) | |
1163 | continue; | |
1164 | ||
1165 | sym = arcs[index]->parent; | |
1166 | ||
1167 | /* If this symbol isn't attached to any other | |
1168 | symbols, then we've got a rarely used arc. | |
1169 | ||
1170 | Skip it for now, we'll deal with them later. */ | |
1171 | if (sym->next == NULL | |
1172 | && sym->prev == NULL) | |
1173 | continue; | |
1174 | ||
1175 | /* Get to the start of this chain. */ | |
1176 | while (sym->prev) | |
1177 | sym = sym->prev; | |
1178 | ||
1179 | while (sym) | |
1180 | { | |
1181 | /* Mark it as placed. */ | |
1182 | sym->has_been_placed = 1; | |
1183 | printf ("%s\n", sym->name); | |
1184 | sym = sym->next; | |
1185 | } | |
1186 | } | |
1187 | ||
ef368dac NC |
1188 | /* If we want to place all the arcs, then output |
1189 | those which weren't placed by the main algorithm. */ | |
252b5132 RH |
1190 | if (all) |
1191 | for (index = 0; index < numarcs; index++) | |
1192 | { | |
1193 | Sym *sym; | |
1194 | if (arcs[index]->parent->has_been_placed | |
1195 | || arcs[index]->child->has_been_placed) | |
1196 | continue; | |
1197 | ||
1198 | sym = arcs[index]->parent; | |
1199 | ||
1200 | sym->has_been_placed = 1; | |
1201 | printf ("%s\n", sym->name); | |
1202 | } | |
1203 | } | |
1204 | ||
1205 | /* Print a suggested .o ordering for files on a link line based | |
1206 | on profiling information. This uses the function placement | |
1207 | code for the bulk of its work. */ | |
1208 | ||
ef368dac NC |
1209 | struct function_map |
1210 | { | |
252b5132 RH |
1211 | char *function_name; |
1212 | char *file_name; | |
1213 | }; | |
1214 | ||
1215 | void | |
1216 | DEFUN_VOID (cg_print_file_ordering) | |
1217 | { | |
1218 | unsigned long scratch_arc_count, index; | |
1219 | Arc **scratch_arcs; | |
1220 | extern struct function_map *symbol_map; | |
1221 | extern unsigned int symbol_map_count; | |
1222 | char *last; | |
1223 | ||
1224 | scratch_arc_count = 0; | |
1225 | ||
1226 | scratch_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *)); | |
1227 | for (index = 0; index < numarcs; index++) | |
1228 | { | |
1229 | if (! arcs[index]->parent->mapped | |
1230 | || ! arcs[index]->child->mapped) | |
1231 | arcs[index]->has_been_placed = 1; | |
1232 | } | |
1233 | ||
1234 | order_and_dump_functions_by_arcs (arcs, numarcs, 0, | |
1235 | scratch_arcs, &scratch_arc_count); | |
1236 | ||
1237 | /* Output .o's not handled by the main placement algorithm. */ | |
1238 | for (index = 0; index < symtab.len; index++) | |
1239 | { | |
1240 | if (symtab.base[index].mapped | |
1241 | && ! symtab.base[index].has_been_placed) | |
1242 | printf ("%s\n", symtab.base[index].name); | |
1243 | } | |
1244 | ||
1245 | /* Now output any .o's that didn't have any text symbols. */ | |
1246 | last = NULL; | |
1247 | for (index = 0; index < symbol_map_count; index++) | |
1248 | { | |
1249 | unsigned int index2; | |
1250 | ||
ef368dac NC |
1251 | /* Don't bother searching if this symbol |
1252 | is the same as the previous one. */ | |
252b5132 RH |
1253 | if (last && !strcmp (last, symbol_map[index].file_name)) |
1254 | continue; | |
1255 | ||
1256 | for (index2 = 0; index2 < symtab.len; index2++) | |
1257 | { | |
1258 | if (! symtab.base[index2].mapped) | |
1259 | continue; | |
1260 | ||
1261 | if (!strcmp (symtab.base[index2].name, symbol_map[index].file_name)) | |
1262 | break; | |
1263 | } | |
1264 | ||
ef368dac NC |
1265 | /* If we didn't find it in the symbol table, then it must |
1266 | be a .o with no text symbols. Output it last. */ | |
252b5132 RH |
1267 | if (index2 == symtab.len) |
1268 | printf ("%s\n", symbol_map[index].file_name); | |
1269 | last = symbol_map[index].file_name; | |
0eee5820 | 1270 | } |
252b5132 | 1271 | } |