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