1 /* cg_print.c - Print routines for displaying call graphs.
3 Copyright 2000, 2001, 2002 Free Software Foundation, Inc.
5 This file is part of GNU Binutils.
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.
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.
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
22 #include "libiberty.h"
24 #include "search_list.h"
32 /* Return value of comparison functions used to sort tables. */
37 static void order_and_dump_functions_by_arcs PARAMS ((Arc **, unsigned long,
40 /* Declarations of automatically generated functions to output blurbs. */
41 extern void bsd_callg_blurb PARAMS ((FILE * fp));
42 extern void fsf_callg_blurb PARAMS ((FILE * fp));
44 double print_time = 0.0;
48 DEFUN_VOID (print_header)
55 if (!bsd_style_output)
57 if (print_descriptions)
58 printf (_("\t\t Call graph (explanation follows)\n\n"));
60 printf (_("\t\t\tCall graph\n\n"));
63 printf (_("\ngranularity: each sample hit covers %ld byte(s)"),
64 (long) hist_scale * sizeof (UNIT));
67 printf (_(" for %.2f%% of %.2f seconds\n\n"),
68 100.0 / print_time, print_time / hz);
71 printf (_(" no time propagated\n\n"));
73 /* This doesn't hurt, since all the numerators will be 0.0. */
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",
82 _("index"), _("%time"), _("self"), _("descendants"),
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"));
90 printf (_("index %% time self children called name\n"));
94 /* Print a cycle header. */
97 DEFUN (print_cycle, (cyc), Sym * cyc)
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);
108 if (cyc->cg.self_calls != 0)
109 printf ("+%-7lu", cyc->cg.self_calls);
111 printf (" %7.7s", "");
113 printf (_(" <cycle %d as a whole> [%d]\n"), cyc->cg.cyc.num, cyc->cg.index);
116 /* Compare LEFT and RIGHT membmer. Major comparison key is
117 CG.PROP.SELF+CG.PROP.CHILD, secondary key is NCALLS+CG.SELF_CALLS. */
120 DEFUN (cmp_member, (left, right), Sym * left AND Sym * right)
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;
127 if (left_time > right_time)
130 if (left_time < right_time)
133 if (left_calls > right_calls)
136 if (left_calls < right_calls)
142 /* Sort members of a cycle. */
145 DEFUN (sort_members, (cyc), Sym * cyc)
147 Sym *todo, *doing, *prev;
149 /* Detach cycle members from cyclehead,
150 and insertion sort them back on. */
151 todo = cyc->cg.cyc.next;
152 cyc->cg.cyc.next = 0;
154 for (doing = todo; doing && doing->cg.cyc.next; doing = todo)
156 todo = doing->cg.cyc.next;
158 for (prev = cyc; prev->cg.cyc.next; prev = prev->cg.cyc.next)
160 if (cmp_member (doing, prev->cg.cyc.next) == GREATERTHAN)
164 doing->cg.cyc.next = prev->cg.cyc.next;
165 prev->cg.cyc.next = doing;
169 /* Print the members of a cycle. */
172 DEFUN (print_members, (cyc), Sym * cyc)
178 for (member = cyc->cg.cyc.next; member; member = member->cg.cyc.next)
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,
186 if (member->cg.self_calls != 0)
187 printf ("+%-7lu", member->cg.self_calls);
189 printf (" %7.7s", "");
197 /* Compare two arcs to/from the same child/parent.
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. */
206 DEFUN (cmp_arc, (left, right), Arc * left AND Arc * right)
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;
215 printf ("[cmp_arc] ");
216 print_name (left_parent);
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);
224 print_name (right_child);
225 printf (" %f + %f %lu/%lu\n", right->time, right->child_time,
226 right->count, right_child->ncalls);
230 if (left_parent == left_child)
231 return LESSTHAN; /* Left is a self call. */
233 if (right_parent == right_child)
234 return GREATERTHAN; /* Right is a self call. */
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)
239 /* Left is a call within a cycle. */
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)
243 /* Right is a call within the cycle, too. */
244 if (left->count < right->count)
247 if (left->count > right->count)
254 /* Right isn't a call within the cycle. */
260 /* Left isn't a call within a cycle. */
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)
264 /* Right is a call within a cycle. */
269 /* Neither is a call within a cycle. */
270 left_time = left->time + left->child_time;
271 right_time = right->time + right->child_time;
273 if (left_time < right_time)
276 if (left_time > right_time)
279 if (left->count < right->count)
282 if (left->count > right->count)
292 DEFUN (sort_parents, (child), Sym * child)
294 Arc *arc, *detached, sorted, *prev;
296 /* Unlink parents from child, then insertion sort back on to
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. */
302 sorted.next_parent = 0;
304 for (arc = child->cg.parents; arc; arc = detached)
306 detached = arc->next_parent;
308 /* Consider *arc as disconnected; insert it into sorted. */
309 for (prev = &sorted; prev->next_parent; prev = prev->next_parent)
311 if (cmp_arc (arc, prev->next_parent) != GREATERTHAN)
315 arc->next_parent = prev->next_parent;
316 prev->next_parent = arc;
319 /* Reattach sorted arcs to child. */
320 child->cg.parents = sorted.next_parent;
325 DEFUN (print_parents, (child), Sym * child)
331 if (child->cg.cyc.head != 0)
332 cycle_head = child->cg.cyc.head;
336 if (!child->cg.parents)
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 "", "", "", "", "", "");
345 sort_parents (child);
347 for (arc = child->cg.parents; arc; arc = arc->next_parent)
349 parent = arc->parent;
350 if (child == parent || (child->cg.cyc.num != 0
351 && parent->cg.cyc.num == child->cg.cyc.num))
353 /* Selfcall or call among siblings. */
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 ",
364 /* Regular parent of child. */
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 ",
369 arc->time / hz, arc->child_time / hz,
370 arc->count, cycle_head->ncalls);
379 DEFUN (sort_children, (parent), Sym * parent)
381 Arc *arc, *detached, sorted, *prev;
383 /* Unlink children from parent, then insertion sort back on to
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. */
389 sorted.next_child = 0;
391 for (arc = parent->cg.children; arc; arc = detached)
393 detached = arc->next_child;
395 /* Consider *arc as disconnected; insert it into sorted. */
396 for (prev = &sorted; prev->next_child; prev = prev->next_child)
398 if (cmp_arc (arc, prev->next_child) != LESSTHAN)
402 arc->next_child = prev->next_child;
403 prev->next_child = arc;
406 /* Reattach sorted children to parent. */
407 parent->cg.children = sorted.next_child;
412 DEFUN (print_children, (parent), Sym * parent)
417 sort_children (parent);
418 arc = parent->cg.children;
420 for (arc = parent->cg.children; arc; arc = arc->next_child)
423 if (child == parent || (child->cg.cyc.num != 0
424 && child->cg.cyc.num == parent->cg.cyc.num))
426 /* Self call or call to sibling. */
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, "");
436 /* Regular child of parent. */
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 ",
441 arc->time / hz, arc->child_time / hz,
442 arc->count, child->cg.cyc.head->ncalls);
451 DEFUN (print_line, (np), Sym * np)
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);
462 if ((np->ncalls + np->cg.self_calls) != 0)
464 printf (" %7lu", np->ncalls);
466 if (np->cg.self_calls != 0)
467 printf ("+%-7lu ", np->cg.self_calls);
469 printf (" %7.7s ", "");
473 printf (" %7.7s %7.7s ", "", "");
481 /* Print dynamic call graph. */
484 DEFUN (cg_print, (timesortsym), Sym ** timesortsym)
489 if (print_descriptions && bsd_style_output)
490 bsd_callg_blurb (stdout);
494 for (index = 0; index < symtab.len + num_cycles; ++index)
496 parent = timesortsym[index];
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))
505 if (!parent->name && parent->cg.cyc.num != 0)
508 print_cycle (parent);
509 print_members (parent);
513 print_parents (parent);
515 print_children (parent);
518 if (bsd_style_output)
521 printf ("-----------------------------------------------\n");
523 if (bsd_style_output)
529 if (print_descriptions && !bsd_style_output)
530 fsf_callg_blurb (stdout);
535 DEFUN (cmp_name, (left, right), const PTR left AND const PTR right)
537 const Sym **npp1 = (const Sym **) left;
538 const Sym **npp2 = (const Sym **) right;
540 return strcmp ((*npp1)->name, (*npp2)->name);
545 DEFUN_VOID (cg_print_index)
548 unsigned int nnames, todo, i, j;
549 int col, starting_col;
550 Sym **name_sorted_syms, *sym;
551 const char *filename;
553 int column_width = (output_width - 1) / 3; /* Don't write in last col! */
555 /* Now, sort regular function name
556 alphabetically to create an index. */
557 name_sorted_syms = (Sym **) xmalloc ((symtab.len + num_cycles) * sizeof (Sym *));
559 for (index = 0, nnames = 0; index < symtab.len; index++)
561 if (ignore_zeros && symtab.base[index].ncalls == 0
562 && symtab.base[index].hist.time == 0)
565 name_sorted_syms[nnames++] = &symtab.base[index];
568 qsort (name_sorted_syms, nnames, sizeof (Sym *), cmp_name);
570 for (index = 1, todo = nnames; index <= num_cycles; index++)
571 name_sorted_syms[todo++] = &cycle_header[index];
574 printf (_("Index by function name\n\n"));
575 index = (todo + 2) / 3;
577 for (i = 0; i < index; i++)
582 for (j = i; j < todo; j += index)
584 sym = name_sorted_syms[j];
586 if (sym->cg.print_flag)
587 sprintf (buf, "[%d]", sym->cg.index);
589 sprintf (buf, "(%d)", sym->cg.index);
593 if (bsd_style_output)
595 printf ("%6.6s %-19.19s", buf, sym->name);
601 for (; col < starting_col + 5; ++col)
604 printf (" %s ", buf);
605 col += print_name_only (sym);
607 if (!line_granularity && sym->is_static && sym->file)
609 filename = sym->file->name;
613 filename = strrchr (filename, '/');
618 filename = sym->file->name;
621 printf (" (%s)", filename);
622 col += strlen (filename) + 3;
628 if (bsd_style_output)
630 printf ("%6.6s ", buf);
631 sprintf (buf, _("<cycle %d>"), sym->cg.cyc.num);
632 printf ("%-19.19s", buf);
637 for (; col < starting_col + 5; ++col)
639 printf (" %s ", buf);
640 sprintf (buf, _("<cycle %d>"), sym->cg.cyc.num);
646 starting_col += column_width;
652 free (name_sorted_syms);
655 /* Compare two arcs based on their usage counts.
656 We want to sort in descending order. */
659 DEFUN (cmp_arc_count, (left, right), const PTR left AND const PTR right)
661 const Arc **npp1 = (const Arc **) left;
662 const Arc **npp2 = (const Arc **) right;
664 if ((*npp1)->count > (*npp2)->count)
666 else if ((*npp1)->count < (*npp2)->count)
672 /* Compare two funtions based on their usage counts.
673 We want to sort in descending order. */
676 DEFUN (cmp_fun_nuses, (left, right), const PTR left AND const PTR right)
678 const Sym **npp1 = (const Sym **) left;
679 const Sym **npp2 = (const Sym **) right;
681 if ((*npp1)->nuses > (*npp2)->nuses)
683 else if ((*npp1)->nuses < (*npp2)->nuses)
689 /* Print a suggested function ordering based on the profiling data.
691 We perform 4 major steps when ordering functions:
693 * Group unused functions together and place them at the
694 end of the function order.
696 * Search the highest use arcs (those which account for 90% of
697 the total arc count) for functions which have several parents.
699 Group those with the most call sites together (currently the
700 top 1.25% which have at least five different call sites).
702 These are emitted at the start of the function order.
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.
709 * Run the same greedy placement algorithm on the remaining
710 arcs to place the leftover functions.
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
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.
724 * Place the functions with many callers near the middle of the
725 list to reduce long calls.
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.
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
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.
741 * Use better profiling information; many published algorithms
742 are based on call sequences through time, rather than just
745 * Prodecure cloning could improve performance when a small number
746 of arcs account for most of the calls to a particular function.
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.
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). */
758 DEFUN_VOID (cg_print_function_ordering)
760 unsigned long index, used, unused, scratch_index;
761 unsigned long unplaced_arc_count, high_arc_count, scratch_arc_count;
763 unsigned long long total_arcs, tmp_arcs_count;
765 unsigned long total_arcs, tmp_arcs_count;
767 Sym **unused_syms, **used_syms, **scratch_syms;
768 Arc **unplaced_arcs, **high_arcs, **scratch_arcs;
774 unplaced_arc_count = 0;
776 scratch_arc_count = 0;
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 *));
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++)
790 if (symtab.base[index].ncalls == 0)
792 /* Filter out gprof generated names. */
793 if (strcmp (symtab.base[index].name, "<locore>")
794 && strcmp (symtab.base[index].name, "<hicore>"))
796 unused_syms[unused++] = &symtab.base[index];
797 symtab.base[index].has_been_placed = 1;
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;
810 /* Sort the arcs from most used to least used. */
811 qsort (arcs, numarcs, sizeof (Arc *), cmp_arc_count);
813 /* Compute the total arc count. Also mark arcs as unplaced.
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. */
819 for (index = 0; index < numarcs; index++)
821 total_arcs += arcs[index]->count;
822 arcs[index]->has_been_placed = 0;
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. */
829 for (index = 0; index < numarcs; index++)
831 tmp_arcs_count += arcs[index]->count;
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)
838 arcs[index]->child->nuses++;
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);
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++)
850 Sym *sym = scratch_syms[index];
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. */
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
863 which are uninteresting.
865 An interesting variation would be to quit when we found
866 multi-call site functions which account for some percentage
868 arc = sym->cg.children;
872 if (arc->parent != arc->child)
873 scratch_arcs[scratch_arc_count++] = arc;
874 arc->has_been_placed = 1;
875 arc = arc->next_child;
878 arc = sym->cg.parents;
882 if (arc->parent != arc->child)
883 scratch_arcs[scratch_arc_count++] = arc;
884 arc->has_been_placed = 1;
885 arc = arc->next_parent;
888 /* Keep track of how many symbols we're going to place. */
889 scratch_index = index;
891 /* A lie, but it makes identifying
892 these functions easier later. */
893 sym->has_been_placed = 1;
896 /* Now walk through the temporary arcs and copy
897 those we care about into the high arcs array. */
898 for (index = 0; index < scratch_arc_count; index++)
900 Arc *arc = scratch_arcs[index];
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)
907 high_arcs[high_arc_count++] = scratch_arcs[index];
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;
916 /* Dump the multi-site high usage functions which are not
917 going to be ordered by the main ordering algorithm. */
918 for (index = 0; index < scratch_index; index++)
920 if (scratch_syms[index]->has_been_placed)
921 printf ("%s\n", scratch_syms[index]->name);
924 /* Now we can order the multi-site high use
925 functions based on the arcs between them. */
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);
930 /* Order and dump the high use functions left,
931 these typically have only a few call sites. */
932 order_and_dump_functions_by_arcs (arcs, numarcs, 0,
933 unplaced_arcs, &unplaced_arc_count);
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);
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);
944 /* Output the unused functions. */
945 for (index = 0; index < unused; index++)
946 printf("%s\n", unused_syms[index]->name);
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 *));
960 free (unplaced_arcs);
963 /* Place functions based on the arcs in ARCS with NUMARCS entries;
964 place unused arcs into UNPLACED_ARCS/UNPLACED_ARC_COUNT.
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. */
971 order_and_dump_functions_by_arcs (arcs, numarcs, all,
972 unplaced_arcs, unplaced_arc_count)
974 unsigned long numarcs;
977 unsigned long *unplaced_arc_count;
980 unsigned long long tmp_arcs, total_arcs;
982 unsigned long tmp_arcs, total_arcs;
986 /* If needed, compute the total arc count.
988 Note we don't compensate for overflow if that happens! */
992 for (index = 0; index < numarcs; index++)
993 total_arcs += arcs[index]->count;
1000 for (index = 0; index < numarcs; index++)
1003 Sym *child, *parent;
1005 tmp_arcs += arcs[index]->count;
1007 /* Ignore this arc if it's already been placed. */
1008 if (arcs[index]->has_been_placed)
1011 child = arcs[index]->child;
1012 parent = arcs[index]->parent;
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)
1020 unplaced_arcs[(*unplaced_arc_count)++] = arcs[index];
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)
1030 unplaced_arcs[(*unplaced_arc_count)++] = arcs[index];
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)
1044 /* Walk to the beginning and end of the child's chain. */
1057 /* Choose the closest. */
1058 child = next_count < prev_count ? next : prev;
1060 else if (! child->next && !child->prev)
1079 parent = prev_count < next_count ? prev : next;
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];
1089 /* Make sure we don't tie two ends together. */
1109 /* This would tie two ends together. */
1110 unplaced_arcs[(*unplaced_arc_count)++] = arcs[index];
1116 /* Must attach to the parent's prev field. */
1119 /* parent-prev and child-next */
1120 parent->prev = child;
1121 child->next = parent;
1122 arcs[index]->has_been_placed = 1;
1125 else if (parent->prev)
1127 /* Must attach to the parent's next field. */
1130 /* parent-next and child-prev */
1131 parent->next = child;
1132 child->prev = parent;
1133 arcs[index]->has_been_placed = 1;
1138 /* Can attach to either field in the parent, depends
1139 on where we've got space in the child. */
1142 /* parent-prev and child-next. */
1143 parent->prev = child;
1144 child->next = parent;
1145 arcs[index]->has_been_placed = 1;
1149 /* parent-next and child-prev. */
1150 parent->next = child;
1151 child->prev = parent;
1152 arcs[index]->has_been_placed = 1;
1157 /* Dump the chains of functions we've made. */
1158 for (index = 0; index < numarcs; index++)
1161 if (arcs[index]->parent->has_been_placed
1162 || arcs[index]->child->has_been_placed)
1165 sym = arcs[index]->parent;
1167 /* If this symbol isn't attached to any other
1168 symbols, then we've got a rarely used arc.
1170 Skip it for now, we'll deal with them later. */
1171 if (sym->next == NULL
1172 && sym->prev == NULL)
1175 /* Get to the start of this chain. */
1181 /* Mark it as placed. */
1182 sym->has_been_placed = 1;
1183 printf ("%s\n", sym->name);
1188 /* If we want to place all the arcs, then output
1189 those which weren't placed by the main algorithm. */
1191 for (index = 0; index < numarcs; index++)
1194 if (arcs[index]->parent->has_been_placed
1195 || arcs[index]->child->has_been_placed)
1198 sym = arcs[index]->parent;
1200 sym->has_been_placed = 1;
1201 printf ("%s\n", sym->name);
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. */
1211 char *function_name;
1216 DEFUN_VOID (cg_print_file_ordering)
1218 unsigned long scratch_arc_count, index;
1220 extern struct function_map *symbol_map;
1221 extern unsigned int symbol_map_count;
1224 scratch_arc_count = 0;
1226 scratch_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
1227 for (index = 0; index < numarcs; index++)
1229 if (! arcs[index]->parent->mapped
1230 || ! arcs[index]->child->mapped)
1231 arcs[index]->has_been_placed = 1;
1234 order_and_dump_functions_by_arcs (arcs, numarcs, 0,
1235 scratch_arcs, &scratch_arc_count);
1237 /* Output .o's not handled by the main placement algorithm. */
1238 for (index = 0; index < symtab.len; index++)
1240 if (symtab.base[index].mapped
1241 && ! symtab.base[index].has_been_placed)
1242 printf ("%s\n", symtab.base[index].name);
1245 /* Now output any .o's that didn't have any text symbols. */
1247 for (index = 0; index < symbol_map_count; index++)
1249 unsigned int index2;
1251 /* Don't bother searching if this symbol
1252 is the same as the previous one. */
1253 if (last && !strcmp (last, symbol_map[index].file_name))
1256 for (index2 = 0; index2 < symtab.len; index2++)
1258 if (! symtab.base[index2].mapped)
1261 if (!strcmp (symtab.base[index2].name, symbol_map[index].file_name))
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. */
1267 if (index2 == symtab.len)
1268 printf ("%s\n", symbol_map[index].file_name);
1269 last = symbol_map[index].file_name;