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