X-Git-Url: http://drtracing.org/?a=blobdiff_plain;f=gprof%2Fcg_print.c;h=1722adfe22132d6652f8fdd9ef555b4090538f7b;hb=d835a58baae720abe909795cb68763040d1750a8;hp=d83fbb73fe072311a0ee34f15265b69bd1f9edd7;hpb=03c35bcb6ec00adf7bff3a0e51370718c03d5f90;p=deliverable%2Fbinutils-gdb.git diff --git a/gprof/cg_print.c b/gprof/cg_print.c index d83fbb73fe..1722adfe22 100644 --- a/gprof/cg_print.c +++ b/gprof/cg_print.c @@ -1,204 +1,228 @@ +/* cg_print.c - Print routines for displaying call graphs. + + Copyright (C) 2000-2020 Free Software Foundation, Inc. + + This file is part of GNU Binutils. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA + 02110-1301, USA. */ + +#include "gprof.h" #include "libiberty.h" +#include "filenames.h" +#include "search_list.h" +#include "source.h" +#include "symtab.h" #include "cg_arcs.h" #include "cg_print.h" #include "hist.h" #include "utils.h" +#include "corefile.h" -/* - * Return value of comparison functions used to sort tables: - */ +/* Return value of comparison functions used to sort tables. */ #define LESSTHAN -1 #define EQUALTO 0 #define GREATERTHAN 1 -/* declarations of automatically generated functions to output blurbs: */ -extern void bsd_callg_blurb PARAMS ((FILE * fp)); -extern void fsf_callg_blurb PARAMS ((FILE * fp)); +static void print_header (void); +static void print_cycle (Sym *); +static int cmp_member (Sym *, Sym *); +static void sort_members (Sym *); +static void print_members (Sym *); +static int cmp_arc (Arc *, Arc *); +static void sort_parents (Sym *); +static void print_parents (Sym *); +static void sort_children (Sym *); +static void print_children (Sym *); +static void print_line (Sym *); +static int cmp_name (const PTR, const PTR); +static int cmp_arc_count (const PTR, const PTR); +static int cmp_fun_nuses (const PTR, const PTR); +static void order_and_dump_functions_by_arcs + (Arc **, unsigned long, int, Arc **, unsigned long *); + +/* Declarations of automatically generated functions to output blurbs. */ +extern void bsd_callg_blurb (FILE * fp); +extern void fsf_callg_blurb (FILE * fp); double print_time = 0.0; static void -DEFUN_VOID (print_header) +print_header (void) { if (first_output) - { - first_output = FALSE; - } + first_output = FALSE; else - { - printf ("\f\n"); - } + printf ("\f\n"); + if (!bsd_style_output) { if (print_descriptions) - { - printf ("\t\t Call graph (explanation follows)\n\n"); - } + printf (_("\t\t Call graph (explanation follows)\n\n")); else - { - printf ("\t\t\tCall graph\n\n"); - } + printf (_("\t\t\tCall graph\n\n")); } - printf ("\ngranularity: each sample hit covers %ld byte(s)", - (long) hist_scale * sizeof (UNIT)); + + printf (_("\ngranularity: each sample hit covers %ld byte(s)"), + (long) hist_scale * (long) sizeof (UNIT)); + if (print_time > 0.0) - { - printf (" for %.2f%% of %.2f seconds\n\n", - 100.0 / print_time, print_time / hz); - } + printf (_(" for %.2f%% of %.2f seconds\n\n"), + 100.0 / print_time, print_time / hz); else { - printf (" no time propagated\n\n"); - /* - * This doesn't hurt, since all the numerators will be 0.0: - */ + printf (_(" no time propagated\n\n")); + + /* This doesn't hurt, since all the numerators will be 0.0. */ print_time = 1.0; } + if (bsd_style_output) { printf ("%6.6s %5.5s %7.7s %11.11s %7.7s/%-7.7s %-8.8s\n", - "", "", "", "", "called", "total", "parents"); + "", "", "", "", _("called"), _("total"), _("parents")); printf ("%-6.6s %5.5s %7.7s %11.11s %7.7s+%-7.7s %-8.8s\t%5.5s\n", - "index", "%time", "self", "descendents", - "called", "self", "name", "index"); + _("index"), + /* xgettext:no-c-format */ + _("%time"), + _("self"), _("descendants"), _("called"), _("self"), + _("name"), _("index")); printf ("%6.6s %5.5s %7.7s %11.11s %7.7s/%-7.7s %-8.8s\n", - "", "", "", "", "called", "total", "children"); + "", "", "", "", _("called"), _("total"), _("children")); printf ("\n"); } else { - printf ("index %% time self children called name\n"); + printf (_("index %% time self children called name\n")); } } +/* Print a cycle header. */ -/* - * Print a cycle header. - */ static void -DEFUN (print_cycle, (cyc), Sym * cyc) +print_cycle (Sym *cyc) { char buf[BUFSIZ]; sprintf (buf, "[%d]", cyc->cg.index); - printf ("%-6.6s %5.1f %7.2f %11.2f %7d", buf, + printf (bsd_style_output + ? "%-6.6s %5.1f %7.2f %11.2f %7lu" + : "%-6.6s %5.1f %7.2f %7.2f %7lu", buf, 100 * (cyc->cg.prop.self + cyc->cg.prop.child) / print_time, cyc->cg.prop.self / hz, cyc->cg.prop.child / hz, cyc->ncalls); + if (cyc->cg.self_calls != 0) - { - printf ("+%-7d", cyc->cg.self_calls); - } + printf ("+%-7lu", cyc->cg.self_calls); else - { - printf (" %7.7s", ""); - } - printf (" \t[%d]\n", cyc->cg.cyc.num, cyc->cg.index); + printf (" %7.7s", ""); + + printf (_(" [%d]\n"), cyc->cg.cyc.num, cyc->cg.index); } +/* Compare LEFT and RIGHT membmer. Major comparison key is + CG.PROP.SELF+CG.PROP.CHILD, secondary key is NCALLS+CG.SELF_CALLS. */ -/* - * Compare LEFT and RIGHT membmer. Major comparison key is - * CG.PROP.SELF+CG.PROP.CHILD, secondary key is NCALLS+CG.SELF_CALLS. - */ static int -DEFUN (cmp_member, (left, right), Sym * left AND Sym * right) +cmp_member (Sym *left, Sym *right) { double left_time = left->cg.prop.self + left->cg.prop.child; double right_time = right->cg.prop.self + right->cg.prop.child; - long left_calls = left->ncalls + left->cg.self_calls; - long right_calls = right->ncalls + right->cg.self_calls; + unsigned long left_calls = left->ncalls + left->cg.self_calls; + unsigned long right_calls = right->ncalls + right->cg.self_calls; if (left_time > right_time) - { - return GREATERTHAN; - } + return GREATERTHAN; + if (left_time < right_time) - { - return LESSTHAN; - } + return LESSTHAN; if (left_calls > right_calls) - { - return GREATERTHAN; - } + return GREATERTHAN; + if (left_calls < right_calls) - { - return LESSTHAN; - } + return LESSTHAN; + return EQUALTO; } +/* Sort members of a cycle. */ -/* - * Sort members of a cycle. - */ static void -DEFUN (sort_members, (cyc), Sym * cyc) +sort_members (Sym *cyc) { Sym *todo, *doing, *prev; - /* - * Detach cycle members from cyclehead, and insertion sort them - * back on. - */ + + /* Detach cycle members from cyclehead, + and insertion sort them back on. */ todo = cyc->cg.cyc.next; cyc->cg.cyc.next = 0; - for (doing = todo; doing && doing->cg.cyc.next; doing = todo) + + for (doing = todo; doing != NULL; doing = todo) { todo = doing->cg.cyc.next; + for (prev = cyc; prev->cg.cyc.next; prev = prev->cg.cyc.next) { if (cmp_member (doing, prev->cg.cyc.next) == GREATERTHAN) - { - break; - } + break; } + doing->cg.cyc.next = prev->cg.cyc.next; prev->cg.cyc.next = doing; } } +/* Print the members of a cycle. */ -/* - * Print the members of a cycle. - */ static void -DEFUN (print_members, (cyc), Sym * cyc) +print_members (Sym *cyc) { Sym *member; sort_members (cyc); + for (member = cyc->cg.cyc.next; member; member = member->cg.cyc.next) { - printf ("%6.6s %5.5s %7.2f %11.2f %7d", + printf (bsd_style_output + ? "%6.6s %5.5s %7.2f %11.2f %7lu" + : "%6.6s %5.5s %7.2f %7.2f %7lu", "", "", member->cg.prop.self / hz, member->cg.prop.child / hz, member->ncalls); + if (member->cg.self_calls != 0) - { - printf ("+%-7d", member->cg.self_calls); - } + printf ("+%-7lu", member->cg.self_calls); else - { - printf (" %7.7s", ""); - } + printf (" %7.7s", ""); + printf (" "); print_name (member); printf ("\n"); } } +/* Compare two arcs to/from the same child/parent. + - if one arc is a self arc, it's least. + - if one arc is within a cycle, it's less than. + - if both arcs are within a cycle, compare arc counts. + - if neither arc is within a cycle, compare with + time + child_time as major key + arc count as minor key. */ -/* - * Compare two arcs to/from the same child/parent. - * - if one arc is a self arc, it's least. - * - if one arc is within a cycle, it's less than. - * - if both arcs are within a cycle, compare arc counts. - * - if neither arc is within a cycle, compare with - * time + child_time as major key - * arc count as minor key - */ static int -DEFUN (cmp_arc, (left, right), Arc * left AND Arc * right) +cmp_arc (Arc *left, Arc *right) { Sym *left_parent = left->parent; Sym *left_child = left->child; @@ -211,79 +235,72 @@ DEFUN (cmp_arc, (left, right), Arc * left AND Arc * right) print_name (left_parent); printf (" calls "); print_name (left_child); - printf (" %f + %f %d/%d\n", left->time, left->child_time, + printf (" %f + %f %lu/%lu\n", left->time, left->child_time, left->count, left_child->ncalls); printf ("[cmp_arc] "); print_name (right_parent); printf (" calls "); print_name (right_child); - printf (" %f + %f %d/%d\n", right->time, right->child_time, + printf (" %f + %f %lu/%lu\n", right->time, right->child_time, right->count, right_child->ncalls); printf ("\n"); ); + if (left_parent == left_child) - { - return LESSTHAN; /* left is a self call */ - } + return LESSTHAN; /* Left is a self call. */ + if (right_parent == right_child) - { - return GREATERTHAN; /* right is a self call */ - } + return GREATERTHAN; /* Right is a self call. */ if (left_parent->cg.cyc.num != 0 && left_child->cg.cyc.num != 0 && left_parent->cg.cyc.num == left_child->cg.cyc.num) { - /* left is a call within a cycle */ + /* Left is a call within a cycle. */ if (right_parent->cg.cyc.num != 0 && right_child->cg.cyc.num != 0 && right_parent->cg.cyc.num == right_child->cg.cyc.num) { - /* right is a call within the cycle, too */ + /* Right is a call within the cycle, too. */ if (left->count < right->count) - { - return LESSTHAN; - } + return LESSTHAN; + if (left->count > right->count) - { - return GREATERTHAN; - } + return GREATERTHAN; + return EQUALTO; } else { - /* right isn't a call within the cycle */ + /* Right isn't a call within the cycle. */ return LESSTHAN; } } else { - /* left isn't a call within a cycle */ + /* Left isn't a call within a cycle. */ if (right_parent->cg.cyc.num != 0 && right_child->cg.cyc.num != 0 && right_parent->cg.cyc.num == right_child->cg.cyc.num) { - /* right is a call within a cycle */ + /* Right is a call within a cycle. */ return GREATERTHAN; } else { - /* neither is a call within a cycle */ + /* Neither is a call within a cycle. */ left_time = left->time + left->child_time; right_time = right->time + right->child_time; + if (left_time < right_time) - { - return LESSTHAN; - } + return LESSTHAN; + if (left_time > right_time) - { - return GREATERTHAN; - } + return GREATERTHAN; + if (left->count < right->count) - { - return LESSTHAN; - } + return LESSTHAN; + if (left->count > right->count) - { - return GREATERTHAN; - } + return GREATERTHAN; + return EQUALTO; } } @@ -291,74 +308,71 @@ DEFUN (cmp_arc, (left, right), Arc * left AND Arc * right) static void -DEFUN (sort_parents, (child), Sym * child) +sort_parents (Sym * child) { Arc *arc, *detached, sorted, *prev; - /* - * Unlink parents from child, then insertion sort back on to - * sorted's parents. - * *arc the arc you have detached and are inserting. - * *detached the rest of the arcs to be sorted. - * sorted arc list onto which you insertion sort. - * *prev arc before the arc you are comparing. - */ + /* Unlink parents from child, then insertion sort back on to + sorted's parents. + *arc the arc you have detached and are inserting. + *detached the rest of the arcs to be sorted. + sorted arc list onto which you insertion sort. + *prev arc before the arc you are comparing. */ sorted.next_parent = 0; + for (arc = child->cg.parents; arc; arc = detached) { detached = arc->next_parent; - /* consider *arc as disconnected; insert it into sorted: */ + /* Consider *arc as disconnected; insert it into sorted. */ for (prev = &sorted; prev->next_parent; prev = prev->next_parent) { if (cmp_arc (arc, prev->next_parent) != GREATERTHAN) - { - break; - } + break; } + arc->next_parent = prev->next_parent; prev->next_parent = arc; } - /* reattach sorted arcs to child: */ + /* Reattach sorted arcs to child. */ child->cg.parents = sorted.next_parent; } static void -DEFUN (print_parents, (child), Sym * child) +print_parents (Sym *child) { Sym *parent; Arc *arc; Sym *cycle_head; if (child->cg.cyc.head != 0) - { - cycle_head = child->cg.cyc.head; - } + cycle_head = child->cg.cyc.head; else - { - cycle_head = child; - } + cycle_head = child; + if (!child->cg.parents) { printf (bsd_style_output - ? "%6.6s %5.5s %7.7s %11.11s %7.7s %7.7s \n" - : "%6.6s %5.5s %7.7s %7.7s %7.7s %7.7s \n", + ? _("%6.6s %5.5s %7.7s %11.11s %7.7s %7.7s \n") + : _("%6.6s %5.5s %7.7s %7.7s %7.7s %7.7s \n"), "", "", "", "", "", ""); return; } + sort_parents (child); + for (arc = child->cg.parents; arc; arc = arc->next_parent) { parent = arc->parent; if (child == parent || (child->cg.cyc.num != 0 && parent->cg.cyc.num == child->cg.cyc.num)) { - /* selfcall or call among siblings: */ + /* Selfcall or call among siblings. */ printf (bsd_style_output - ? "%6.6s %5.5s %7.7s %11.11s %7d %7.7s " - : "%6.6s %5.5s %7.7s %7.7s %7d %7.7s ", + ? "%6.6s %5.5s %7.7s %11.11s %7lu %7.7s " + : "%6.6s %5.5s %7.7s %7.7s %7lu %7.7s ", "", "", "", "", arc->count, ""); print_name (parent); @@ -366,10 +380,10 @@ DEFUN (print_parents, (child), Sym * child) } else { - /* regular parent of child: */ + /* Regular parent of child. */ printf (bsd_style_output - ? "%6.6s %5.5s %7.2f %11.2f %7d/%-7d " - : "%6.6s %5.5s %7.2f %7.2f %7d/%-7d ", + ? "%6.6s %5.5s %7.2f %11.2f %7lu/%-7lu " + : "%6.6s %5.5s %7.2f %7.2f %7lu/%-7lu ", "", "", arc->time / hz, arc->child_time / hz, arc->count, cycle_head->ncalls); @@ -381,67 +395,67 @@ DEFUN (print_parents, (child), Sym * child) static void -DEFUN (sort_children, (parent), Sym * parent) +sort_children (Sym *parent) { Arc *arc, *detached, sorted, *prev; - /* - * Unlink children from parent, then insertion sort back on to - * sorted's children. - * *arc the arc you have detached and are inserting. - * *detached the rest of the arcs to be sorted. - * sorted arc list onto which you insertion sort. - * *prev arc before the arc you are comparing. - */ + + /* Unlink children from parent, then insertion sort back on to + sorted's children. + *arc the arc you have detached and are inserting. + *detached the rest of the arcs to be sorted. + sorted arc list onto which you insertion sort. + *prev arc before the arc you are comparing. */ sorted.next_child = 0; + for (arc = parent->cg.children; arc; arc = detached) { detached = arc->next_child; - /* consider *arc as disconnected; insert it into sorted: */ + /* Consider *arc as disconnected; insert it into sorted. */ for (prev = &sorted; prev->next_child; prev = prev->next_child) { if (cmp_arc (arc, prev->next_child) != LESSTHAN) - { - break; - } + break; } + arc->next_child = prev->next_child; prev->next_child = arc; } - /* reattach sorted children to parent: */ + /* Reattach sorted children to parent. */ parent->cg.children = sorted.next_child; } static void -DEFUN (print_children, (parent), Sym * parent) +print_children (Sym *parent) { Sym *child; Arc *arc; sort_children (parent); arc = parent->cg.children; + for (arc = parent->cg.children; arc; arc = arc->next_child) { child = arc->child; if (child == parent || (child->cg.cyc.num != 0 && child->cg.cyc.num == parent->cg.cyc.num)) { - /* self call or call to sibling: */ + /* Self call or call to sibling. */ printf (bsd_style_output - ? "%6.6s %5.5s %7.7s %11.11s %7d %7.7s " - : "%6.6s %5.5s %7.7s %7.7s %7d %7.7s ", + ? "%6.6s %5.5s %7.7s %11.11s %7lu %7.7s " + : "%6.6s %5.5s %7.7s %7.7s %7lu %7.7s ", "", "", "", "", arc->count, ""); print_name (child); printf ("\n"); } else { - /* regular child of parent: */ + /* Regular child of parent. */ printf (bsd_style_output - ? "%6.6s %5.5s %7.2f %11.2f %7d/%-7d " - : "%6.6s %5.5s %7.2f %7.2f %7d/%-7d ", + ? "%6.6s %5.5s %7.2f %11.2f %7lu/%-7lu " + : "%6.6s %5.5s %7.2f %7.2f %7lu/%-7lu ", "", "", arc->time / hz, arc->child_time / hz, arc->count, child->cg.cyc.head->ncalls); @@ -453,7 +467,7 @@ DEFUN (print_children, (parent), Sym * parent) static void -DEFUN (print_line, (np), Sym * np) +print_line (Sym *np) { char buf[BUFSIZ]; @@ -463,56 +477,53 @@ DEFUN (print_line, (np), Sym * np) : "%-6.6s %5.1f %7.2f %7.2f", buf, 100 * (np->cg.prop.self + np->cg.prop.child) / print_time, np->cg.prop.self / hz, np->cg.prop.child / hz); + if ((np->ncalls + np->cg.self_calls) != 0) { - printf (" %7d", np->ncalls); + printf (" %7lu", np->ncalls); + if (np->cg.self_calls != 0) - { - printf ("+%-7d ", np->cg.self_calls); - } + printf ("+%-7lu ", np->cg.self_calls); else - { printf (" %7.7s ", ""); - } } else { printf (" %7.7s %7.7s ", "", ""); } + print_name (np); printf ("\n"); } -/* - * Print dynamic call graph. - */ +/* Print dynamic call graph. */ + void -DEFUN (cg_print, (timesortsym), Sym ** timesortsym) +cg_print (Sym ** timesortsym) { - int index; + unsigned int sym_index; Sym *parent; if (print_descriptions && bsd_style_output) - { - bsd_callg_blurb (stdout); - } + bsd_callg_blurb (stdout); print_header (); - for (index = 0; index < symtab.len + num_cycles; ++index) + for (sym_index = 0; sym_index < symtab.len + num_cycles; ++sym_index) { - parent = timesortsym[index]; + parent = timesortsym[sym_index]; + if ((ignore_zeros && parent->ncalls == 0 && parent->cg.self_calls == 0 && parent->cg.prop.self == 0 && parent->cg.prop.child == 0) - || !parent->cg.print_flag) - { - continue; - } + || !parent->cg.print_flag + || (line_granularity && ! parent->is_func)) + continue; + if (!parent->name && parent->cg.cyc.num != 0) { - /* cycle header: */ + /* Cycle header. */ print_cycle (parent); print_members (parent); } @@ -522,22 +533,25 @@ DEFUN (cg_print, (timesortsym), Sym ** timesortsym) print_line (parent); print_children (parent); } + if (bsd_style_output) printf ("\n"); + printf ("-----------------------------------------------\n"); + if (bsd_style_output) printf ("\n"); } + free (timesortsym); + if (print_descriptions && !bsd_style_output) - { - fsf_callg_blurb (stdout); - } + fsf_callg_blurb (stdout); } static int -DEFUN (cmp_name, (left, right), const PTR left AND const PTR right) +cmp_name (const PTR left, const PTR right) { const Sym **npp1 = (const Sym **) left; const Sym **npp2 = (const Sym **) right; @@ -547,49 +561,52 @@ DEFUN (cmp_name, (left, right), const PTR left AND const PTR right) void -DEFUN_VOID (cg_print_index) +cg_print_index (void) { - int index, nnames, todo, i, j, col, starting_col; + unsigned int sym_index; + unsigned int nnames, todo, i, j; + int col, starting_col; Sym **name_sorted_syms, *sym; const char *filename; char buf[20]; - int column_width = (output_width - 1) / 3; /* don't write in last col! */ - /* - * Now, sort regular function name alphabetically to create an - * index: - */ + int column_width = (output_width - 1) / 3; /* Don't write in last col! */ + + /* Now, sort regular function name + alphabetically to create an index. */ name_sorted_syms = (Sym **) xmalloc ((symtab.len + num_cycles) * sizeof (Sym *)); - for (index = 0, nnames = 0; index < symtab.len; index++) + + for (sym_index = 0, nnames = 0; sym_index < symtab.len; sym_index++) { - if (ignore_zeros && symtab.base[index].ncalls == 0 - && symtab.base[index].hist.time == 0) - { - continue; - } - name_sorted_syms[nnames++] = &symtab.base[index]; + if (ignore_zeros && symtab.base[sym_index].ncalls == 0 + && symtab.base[sym_index].hist.time == 0) + continue; + + name_sorted_syms[nnames++] = &symtab.base[sym_index]; } + qsort (name_sorted_syms, nnames, sizeof (Sym *), cmp_name); - for (index = 1, todo = nnames; index <= num_cycles; index++) - { - name_sorted_syms[todo++] = &cycle_header[index]; - } - printf ("\f\nIndex by function name\n\n"); - index = (todo + 2) / 3; - for (i = 0; i < index; i++) + + for (sym_index = 1, todo = nnames; sym_index <= num_cycles; sym_index++) + name_sorted_syms[todo++] = &cycle_header[sym_index]; + + printf ("\f\n"); + printf (_("Index by function name\n\n")); + sym_index = (todo + 2) / 3; + + for (i = 0; i < sym_index; i++) { col = 0; starting_col = 0; - for (j = i; j < todo; j += index) + + for (j = i; j < todo; j += sym_index) { sym = name_sorted_syms[j]; + if (sym->cg.print_flag) - { - sprintf (buf, "[%d]", sym->cg.index); - } + sprintf (buf, "[%d]", sym->cg.index); else - { - sprintf (buf, "(%d)", sym->cg.index); - } + sprintf (buf, "(%d)", sym->cg.index); + if (j < nnames) { if (bsd_style_output) @@ -599,27 +616,27 @@ DEFUN_VOID (cg_print_index) else { col += strlen (buf); + for (; col < starting_col + 5; ++col) - { - putchar (' '); - } + putchar (' '); + printf (" %s ", buf); col += print_name_only (sym); + if (!line_granularity && sym->is_static && sym->file) { filename = sym->file->name; + if (!print_path) { filename = strrchr (filename, '/'); + if (filename) - { - ++filename; - } + ++filename; else - { - filename = sym->file->name; - } + filename = sym->file->name; } + printf (" (%s)", filename); col += strlen (filename) + 3; } @@ -627,13 +644,647 @@ DEFUN_VOID (cg_print_index) } else { - printf ("%6.6s ", buf); - sprintf (buf, "", sym->cg.cyc.num); - printf ("%-19.19s", buf); + if (bsd_style_output) + { + printf ("%6.6s ", buf); + sprintf (buf, _(""), sym->cg.cyc.num); + printf ("%-19.19s", buf); + } + else + { + col += strlen (buf); + for (; col < starting_col + 5; ++col) + putchar (' '); + printf (" %s ", buf); + sprintf (buf, _(""), sym->cg.cyc.num); + printf ("%s", buf); + col += strlen (buf); + } } + starting_col += column_width; } + printf ("\n"); } + free (name_sorted_syms); } + +/* Compare two arcs based on their usage counts. + We want to sort in descending order. */ + +static int +cmp_arc_count (const PTR left, const PTR right) +{ + const Arc **npp1 = (const Arc **) left; + const Arc **npp2 = (const Arc **) right; + + if ((*npp1)->count > (*npp2)->count) + return -1; + else if ((*npp1)->count < (*npp2)->count) + return 1; + else + return 0; +} + +/* Compare two funtions based on their usage counts. + We want to sort in descending order. */ + +static int +cmp_fun_nuses (const PTR left, const PTR right) +{ + const Sym **npp1 = (const Sym **) left; + const Sym **npp2 = (const Sym **) right; + + if ((*npp1)->nuses > (*npp2)->nuses) + return -1; + else if ((*npp1)->nuses < (*npp2)->nuses) + return 1; + else + return 0; +} + +/* Print a suggested function ordering based on the profiling data. + + We perform 4 major steps when ordering functions: + + * Group unused functions together and place them at the + end of the function order. + + * Search the highest use arcs (those which account for 90% of + the total arc count) for functions which have several parents. + + Group those with the most call sites together (currently the + top 1.25% which have at least five different call sites). + + These are emitted at the start of the function order. + + * Use a greedy placement algorithm to place functions which + occur in the top 99% of the arcs in the profile. Some provisions + are made to handle high usage arcs where the parent and/or + child has already been placed. + + * Run the same greedy placement algorithm on the remaining + arcs to place the leftover functions. + + + The various "magic numbers" should (one day) be tuneable by command + line options. They were arrived at by benchmarking a few applications + with various values to see which values produced better overall function + orderings. + + Of course, profiling errors, machine limitations (PA long calls), and + poor cutoff values for the placement algorithm may limit the usefullness + of the resulting function order. Improvements would be greatly appreciated. + + Suggestions: + + * Place the functions with many callers near the middle of the + list to reduce long calls. + + * Propagate arc usage changes as functions are placed. Ie if + func1 and func2 are placed together, arcs to/from those arcs + to the same parent/child should be combined, then resort the + arcs to choose the next one. + + * Implement some global positioning algorithm to place the + chains made by the greedy local positioning algorithm. Probably + by examining arcs which haven't been placed yet to tie two + chains together. + + * Take a function's size and time into account in the algorithm; + size in particular is important on the PA (long calls). Placing + many small functions onto their own page may be wise. + + * Use better profiling information; many published algorithms + are based on call sequences through time, rather than just + arc counts. + + * Prodecure cloning could improve performance when a small number + of arcs account for most of the calls to a particular function. + + * Use relocation information to avoid moving unused functions + completely out of the code stream; this would avoid severe lossage + when the profile data bears little resemblance to actual runs. + + * Propagation of arc usages should also improve .o link line + ordering which shares the same arc placement algorithm with + the function ordering code (in fact it is a degenerate case + of function ordering). */ + +void +cg_print_function_ordering (void) +{ + unsigned long sym_index; + unsigned long arc_index; + unsigned long used, unused, scratch_index; + unsigned long unplaced_arc_count, high_arc_count, scratch_arc_count; +#ifdef __GNUC__ + unsigned long long total_arcs, tmp_arcs_count; +#else + unsigned long total_arcs, tmp_arcs_count; +#endif + Sym **unused_syms, **used_syms, **scratch_syms; + Arc **unplaced_arcs, **high_arcs, **scratch_arcs; + + sym_index = 0; + used = 0; + unused = 0; + scratch_index = 0; + unplaced_arc_count = 0; + high_arc_count = 0; + scratch_arc_count = 0; + + /* First group all the unused functions together. */ + unused_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *)); + used_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *)); + scratch_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *)); + high_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *)); + scratch_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *)); + unplaced_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *)); + + /* Walk through all the functions; mark those which are never + called as placed (we'll emit them as a group later). */ + for (sym_index = 0, used = 0, unused = 0; sym_index < symtab.len; sym_index++) + { + if (symtab.base[sym_index].ncalls == 0) + { + unused_syms[unused++] = &symtab.base[sym_index]; + symtab.base[sym_index].has_been_placed = 1; + } + else + { + used_syms[used++] = &symtab.base[sym_index]; + symtab.base[sym_index].has_been_placed = 0; + symtab.base[sym_index].next = 0; + symtab.base[sym_index].prev = 0; + symtab.base[sym_index].nuses = 0; + } + } + + /* Sort the arcs from most used to least used. */ + qsort (arcs, numarcs, sizeof (Arc *), cmp_arc_count); + + /* Compute the total arc count. Also mark arcs as unplaced. + + Note we don't compensate for overflow if that happens! + Overflow is much less likely when this file is compiled + with GCC as it can double-wide integers via long long. */ + total_arcs = 0; + for (arc_index = 0; arc_index < numarcs; arc_index++) + { + total_arcs += arcs[arc_index]->count; + arcs[arc_index]->has_been_placed = 0; + } + + /* We want to pull out those functions which are referenced + by many highly used arcs and emit them as a group. This + could probably use some tuning. */ + tmp_arcs_count = 0; + for (arc_index = 0; arc_index < numarcs; arc_index++) + { + tmp_arcs_count += arcs[arc_index]->count; + + /* Count how many times each parent and child are used up + to our threshold of arcs (90%). */ + if ((double)tmp_arcs_count / (double)total_arcs > 0.90) + break; + + arcs[arc_index]->child->nuses++; + } + + /* Now sort a temporary symbol table based on the number of + times each function was used in the highest used arcs. */ + memcpy (scratch_syms, used_syms, used * sizeof (Sym *)); + qsort (scratch_syms, used, sizeof (Sym *), cmp_fun_nuses); + + /* Now pick out those symbols we're going to emit as + a group. We take up to 1.25% of the used symbols. */ + for (sym_index = 0; sym_index < used / 80; sym_index++) + { + Sym *sym = scratch_syms[sym_index]; + Arc *arc; + + /* If we hit symbols that aren't used from many call sites, + then we can quit. We choose five as the low limit for + no particular reason. */ + if (sym->nuses == 5) + break; + + /* We're going to need the arcs between these functions. + Unfortunately, we don't know all these functions + until we're done. So we keep track of all the arcs + to the functions we care about, then prune out those + which are uninteresting. + + An interesting variation would be to quit when we found + multi-call site functions which account for some percentage + of the arcs. */ + arc = sym->cg.children; + + while (arc) + { + if (arc->parent != arc->child) + scratch_arcs[scratch_arc_count++] = arc; + arc->has_been_placed = 1; + arc = arc->next_child; + } + + arc = sym->cg.parents; + + while (arc) + { + if (arc->parent != arc->child) + scratch_arcs[scratch_arc_count++] = arc; + arc->has_been_placed = 1; + arc = arc->next_parent; + } + + /* Keep track of how many symbols we're going to place. */ + scratch_index = sym_index; + + /* A lie, but it makes identifying + these functions easier later. */ + sym->has_been_placed = 1; + } + + /* Now walk through the temporary arcs and copy + those we care about into the high arcs array. */ + for (arc_index = 0; arc_index < scratch_arc_count; arc_index++) + { + Arc *arc = scratch_arcs[arc_index]; + + /* If this arc refers to highly used functions, then + then we want to keep it. */ + if (arc->child->has_been_placed + && arc->parent->has_been_placed) + { + high_arcs[high_arc_count++] = scratch_arcs[arc_index]; + + /* We need to turn of has_been_placed since we're going to + use the main arc placement algorithm on these arcs. */ + arc->child->has_been_placed = 0; + arc->parent->has_been_placed = 0; + } + } + + /* Dump the multi-site high usage functions which are not + going to be ordered by the main ordering algorithm. */ + for (sym_index = 0; sym_index < scratch_index; sym_index++) + { + if (scratch_syms[sym_index]->has_been_placed) + printf ("%s\n", scratch_syms[sym_index]->name); + } + + /* Now we can order the multi-site high use + functions based on the arcs between them. */ + qsort (high_arcs, high_arc_count, sizeof (Arc *), cmp_arc_count); + order_and_dump_functions_by_arcs (high_arcs, high_arc_count, 1, + unplaced_arcs, &unplaced_arc_count); + + /* Order and dump the high use functions left, + these typically have only a few call sites. */ + order_and_dump_functions_by_arcs (arcs, numarcs, 0, + unplaced_arcs, &unplaced_arc_count); + + /* Now place the rarely used functions. */ + order_and_dump_functions_by_arcs (unplaced_arcs, unplaced_arc_count, 1, + scratch_arcs, &scratch_arc_count); + + /* Output any functions not emitted by the order_and_dump calls. */ + for (sym_index = 0; sym_index < used; sym_index++) + if (used_syms[sym_index]->has_been_placed == 0) + printf("%s\n", used_syms[sym_index]->name); + + /* Output the unused functions. */ + for (sym_index = 0; sym_index < unused; sym_index++) + printf("%s\n", unused_syms[sym_index]->name); + + unused_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *)); + used_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *)); + scratch_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *)); + high_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *)); + scratch_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *)); + unplaced_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *)); + + free (unused_syms); + free (used_syms); + free (scratch_syms); + free (high_arcs); + free (scratch_arcs); + free (unplaced_arcs); +} + +/* Place functions based on the arcs in THE_ARCS with ARC_COUNT entries; + place unused arcs into UNPLACED_ARCS/UNPLACED_ARC_COUNT. + + If ALL is nonzero, then place all functions referenced by THE_ARCS, + else only place those referenced in the top 99% of the arcs in THE_ARCS. */ + +#define MOST 0.99 +static void +order_and_dump_functions_by_arcs (Arc **the_arcs, unsigned long arc_count, + int all, Arc **unplaced_arcs, + unsigned long *unplaced_arc_count) +{ +#ifdef __GNUC__ + unsigned long long tmp_arcs, total_arcs; +#else + unsigned long tmp_arcs, total_arcs; +#endif + unsigned int arc_index; + + /* If needed, compute the total arc count. + + Note we don't compensate for overflow if that happens! */ + if (! all) + { + total_arcs = 0; + for (arc_index = 0; arc_index < arc_count; arc_index++) + total_arcs += the_arcs[arc_index]->count; + } + else + total_arcs = 0; + + tmp_arcs = 0; + + for (arc_index = 0; arc_index < arc_count; arc_index++) + { + Sym *sym1, *sym2; + Sym *child, *parent; + + tmp_arcs += the_arcs[arc_index]->count; + + /* Ignore this arc if it's already been placed. */ + if (the_arcs[arc_index]->has_been_placed) + continue; + + child = the_arcs[arc_index]->child; + parent = the_arcs[arc_index]->parent; + + /* If we're not using all arcs, and this is a rarely used + arc, then put it on the unplaced_arc list. Similarly + if both the parent and child of this arc have been placed. */ + if ((! all && (double)tmp_arcs / (double)total_arcs > MOST) + || child->has_been_placed || parent->has_been_placed) + { + unplaced_arcs[(*unplaced_arc_count)++] = the_arcs[arc_index]; + continue; + } + + /* If all slots in the parent and child are full, then there isn't + anything we can do right now. We'll place this arc on the + unplaced arc list in the hope that a global positioning + algorithm can use it to place function chains. */ + if (parent->next && parent->prev && child->next && child->prev) + { + unplaced_arcs[(*unplaced_arc_count)++] = the_arcs[arc_index]; + continue; + } + + /* If the parent is unattached, then find the closest + place to attach it onto child's chain. Similarly + for the opposite case. */ + if (!parent->next && !parent->prev) + { + int next_count = 0; + int prev_count = 0; + Sym *prev = child; + Sym *next = child; + + /* Walk to the beginning and end of the child's chain. */ + while (next->next) + { + next = next->next; + next_count++; + } + + while (prev->prev) + { + prev = prev->prev; + prev_count++; + } + + /* Choose the closest. */ + child = next_count < prev_count ? next : prev; + } + else if (! child->next && !child->prev) + { + int next_count = 0; + int prev_count = 0; + Sym *prev = parent; + Sym *next = parent; + + while (next->next) + { + next = next->next; + next_count++; + } + + while (prev->prev) + { + prev = prev->prev; + prev_count++; + } + + parent = prev_count < next_count ? prev : next; + } + else + { + /* Couldn't find anywhere to attach the functions, + put the arc on the unplaced arc list. */ + unplaced_arcs[(*unplaced_arc_count)++] = the_arcs[arc_index]; + continue; + } + + /* Make sure we don't tie two ends together. */ + sym1 = parent; + if (sym1->next) + while (sym1->next) + sym1 = sym1->next; + else + while (sym1->prev) + sym1 = sym1->prev; + + sym2 = child; + if (sym2->next) + while (sym2->next) + sym2 = sym2->next; + else + while (sym2->prev) + sym2 = sym2->prev; + + if (sym1 == child + && sym2 == parent) + { + /* This would tie two ends together. */ + unplaced_arcs[(*unplaced_arc_count)++] = the_arcs[arc_index]; + continue; + } + + if (parent->next) + { + /* Must attach to the parent's prev field. */ + if (! child->next) + { + /* parent-prev and child-next */ + parent->prev = child; + child->next = parent; + the_arcs[arc_index]->has_been_placed = 1; + } + } + else if (parent->prev) + { + /* Must attach to the parent's next field. */ + if (! child->prev) + { + /* parent-next and child-prev */ + parent->next = child; + child->prev = parent; + the_arcs[arc_index]->has_been_placed = 1; + } + } + else + { + /* Can attach to either field in the parent, depends + on where we've got space in the child. */ + if (child->prev) + { + /* parent-prev and child-next. */ + parent->prev = child; + child->next = parent; + the_arcs[arc_index]->has_been_placed = 1; + } + else + { + /* parent-next and child-prev. */ + parent->next = child; + child->prev = parent; + the_arcs[arc_index]->has_been_placed = 1; + } + } + } + + /* Dump the chains of functions we've made. */ + for (arc_index = 0; arc_index < arc_count; arc_index++) + { + Sym *sym; + if (the_arcs[arc_index]->parent->has_been_placed + || the_arcs[arc_index]->child->has_been_placed) + continue; + + sym = the_arcs[arc_index]->parent; + + /* If this symbol isn't attached to any other + symbols, then we've got a rarely used arc. + + Skip it for now, we'll deal with them later. */ + if (sym->next == NULL + && sym->prev == NULL) + continue; + + /* Get to the start of this chain. */ + while (sym->prev) + sym = sym->prev; + + while (sym) + { + /* Mark it as placed. */ + sym->has_been_placed = 1; + printf ("%s\n", sym->name); + sym = sym->next; + } + } + + /* If we want to place all the arcs, then output + those which weren't placed by the main algorithm. */ + if (all) + for (arc_index = 0; arc_index < arc_count; arc_index++) + { + Sym *sym; + if (the_arcs[arc_index]->parent->has_been_placed + || the_arcs[arc_index]->child->has_been_placed) + continue; + + sym = the_arcs[arc_index]->parent; + + sym->has_been_placed = 1; + printf ("%s\n", sym->name); + } +} + +/* Compare two function_map structs based on file name. + We want to sort in ascending order. */ + +static int +cmp_symbol_map (const void * l, const void * r) +{ + return filename_cmp (((struct function_map *) l)->file_name, + ((struct function_map *) r)->file_name); +} + +/* Print a suggested .o ordering for files on a link line based + on profiling information. This uses the function placement + code for the bulk of its work. */ + +void +cg_print_file_ordering (void) +{ + unsigned long scratch_arc_count; + unsigned long arc_index; + unsigned long sym_index; + Arc **scratch_arcs; + char *last; + + scratch_arc_count = 0; + + scratch_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *)); + for (arc_index = 0; arc_index < numarcs; arc_index++) + { + if (! arcs[arc_index]->parent->mapped + || ! arcs[arc_index]->child->mapped) + arcs[arc_index]->has_been_placed = 1; + } + + order_and_dump_functions_by_arcs (arcs, numarcs, 0, + scratch_arcs, &scratch_arc_count); + + /* Output .o's not handled by the main placement algorithm. */ + for (sym_index = 0; sym_index < symtab.len; sym_index++) + { + if (symtab.base[sym_index].mapped + && ! symtab.base[sym_index].has_been_placed) + printf ("%s\n", symtab.base[sym_index].name); + } + + qsort (symbol_map, symbol_map_count, sizeof (struct function_map), cmp_symbol_map); + + /* Now output any .o's that didn't have any text symbols. */ + last = NULL; + for (sym_index = 0; sym_index < symbol_map_count; sym_index++) + { + unsigned int index2; + + /* Don't bother searching if this symbol + is the same as the previous one. */ + if (last && !filename_cmp (last, symbol_map[sym_index].file_name)) + continue; + + for (index2 = 0; index2 < symtab.len; index2++) + { + if (! symtab.base[index2].mapped) + continue; + + if (!filename_cmp (symtab.base[index2].name, + symbol_map[sym_index].file_name)) + break; + } + + /* If we didn't find it in the symbol table, then it must + be a .o with no text symbols. Output it last. */ + if (index2 == symtab.len) + printf ("%s\n", symbol_map[sym_index].file_name); + last = symbol_map[sym_index].file_name; + } +}