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