#define EQUALTO 0
#define GREATERTHAN 1
+static void order_and_dump_functions_by_arcs PARAMS ((Arc **, unsigned long,
+ int, Arc **,
+ unsigned long *));
/* declarations of automatically generated functions to output blurbs: */
extern void bsd_callg_blurb PARAMS ((FILE * fp));
extern void fsf_callg_blurb PARAMS ((FILE * fp));
else
{
printf ("\f\n");
- } /* if */
+ }
if (!bsd_style_output)
{
if (print_descriptions)
else
{
printf ("\t\t\tCall graph\n\n");
- } /* if */
- } /* if */
+ }
+ }
printf ("\ngranularity: each sample hit covers %ld byte(s)",
(long) hist_scale * sizeof (UNIT));
if (print_time > 0.0)
* This doesn't hurt, since all the numerators will be 0.0:
*/
print_time = 1.0;
- } /* if */
+ }
if (bsd_style_output)
{
printf ("%6.6s %5.5s %7.7s %11.11s %7.7s/%-7.7s %-8.8s\n",
else
{
printf ("index %% time self children called name\n");
- } /* if */
-} /* print_header */
+ }
+}
/*
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 %7d"
+ : "%-6.6s %5.1f %7.2f %7.2f %7d", 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)
else
{
printf (" %7.7s", "");
- } /* if */
- printf (" <cycle %d as a whole>\t[%d]\n", cyc->cg.cyc.num, cyc->cg.index);
-} /* print_cycle */
+ }
+ printf (" <cycle %d as a whole> [%d]\n", cyc->cg.cyc.num, cyc->cg.index);
+}
/*
if (left_time > right_time)
{
return GREATERTHAN;
- } /* if */
+ }
if (left_time < right_time)
{
return LESSTHAN;
- } /* if */
+ }
if (left_calls > right_calls)
{
return GREATERTHAN;
- } /* if */
+ }
if (left_calls < right_calls)
{
return LESSTHAN;
- } /* if */
+ }
return EQUALTO;
-} /* cmp_member */
+}
/*
if (cmp_member (doing, prev->cg.cyc.next) == GREATERTHAN)
{
break;
- } /* if */
- } /* for */
+ }
+ }
doing->cg.cyc.next = prev->cg.cyc.next;
prev->cg.cyc.next = doing;
- } /* for */
-} /* sort_members */
+ }
+}
/*
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 %7d"
+ : "%6.6s %5.5s %7.2f %7.2f %7d",
"", "", member->cg.prop.self / hz, member->cg.prop.child / hz,
member->ncalls);
if (member->cg.self_calls != 0)
else
{
printf (" %7.7s", "");
- } /* if */
+ }
printf (" ");
print_name (member);
printf ("\n");
- } /* for */
-} /* print_members */
+ }
+}
/*
if (left_parent == left_child)
{
return LESSTHAN; /* left is a self call */
- } /* if */
+ }
if (right_parent == right_child)
{
return GREATERTHAN; /* right is a self call */
- } /* if */
+ }
if (left_parent->cg.cyc.num != 0 && left_child->cg.cyc.num != 0
&& left_parent->cg.cyc.num == left_child->cg.cyc.num)
if (left->count < right->count)
{
return LESSTHAN;
- } /* if */
+ }
if (left->count > right->count)
{
return GREATERTHAN;
- } /* if */
+ }
return EQUALTO;
}
else
{
/* right isn't a call within the cycle */
return LESSTHAN;
- } /* if */
+ }
}
else
{
if (left_time < right_time)
{
return LESSTHAN;
- } /* if */
+ }
if (left_time > right_time)
{
return GREATERTHAN;
- } /* if */
+ }
if (left->count < right->count)
{
return LESSTHAN;
- } /* if */
+ }
if (left->count > right->count)
{
return GREATERTHAN;
- } /* if */
+ }
return EQUALTO;
- } /* if */
- } /* if */
-} /* cmp_arc */
+ }
+ }
+}
static void
if (cmp_arc (arc, prev->next_parent) != GREATERTHAN)
{
break;
- } /* if */
- } /* for */
+ }
+ }
arc->next_parent = prev->next_parent;
prev->next_parent = arc;
- } /* for */
+ }
/* reattach sorted arcs to child: */
child->cg.parents = sorted.next_parent;
-} /* sort_parents */
+}
static void
else
{
cycle_head = child;
- } /* if */
+ }
if (!child->cg.parents)
{
printf (bsd_style_output
: "%6.6s %5.5s %7.7s %7.7s %7.7s %7.7s <spontaneous>\n",
"", "", "", "", "", "");
return;
- } /* if */
+ }
sort_parents (child);
for (arc = child->cg.parents; arc; arc = arc->next_parent)
{
arc->count, cycle_head->ncalls);
print_name (parent);
printf ("\n");
- } /* if */
- } /* for */
-} /* print_parents */
+ }
+ }
+}
static void
if (cmp_arc (arc, prev->next_child) != LESSTHAN)
{
break;
- } /* if */
- } /* for */
+ }
+ }
arc->next_child = prev->next_child;
prev->next_child = arc;
- } /* for */
+ }
/* reattach sorted children to parent: */
parent->cg.children = sorted.next_child;
-} /* sort_children */
+}
static void
arc->count, child->cg.cyc.head->ncalls);
print_name (child);
printf ("\n");
- } /* if */
- } /* for */
-} /* print_children */
+ }
+ }
+}
static void
else
{
printf (" %7.7s ", "");
- } /* if */
+ }
}
else
{
printf (" %7.7s %7.7s ", "", "");
- } /* if */
+ }
print_name (np);
printf ("\n");
-} /* print_line */
+}
/*
if (print_descriptions && bsd_style_output)
{
bsd_callg_blurb (stdout);
- } /* if */
+ }
print_header ();
|| !parent->cg.print_flag)
{
continue;
- } /* if */
+ }
if (!parent->name && parent->cg.cyc.num != 0)
{
/* cycle header: */
print_parents (parent);
print_line (parent);
print_children (parent);
- } /* if */
+ }
if (bsd_style_output)
printf ("\n");
printf ("-----------------------------------------------\n");
{
fsf_callg_blurb (stdout);
}
-} /* cg_print */
+}
static int
const Sym **npp2 = (const Sym **) right;
return strcmp ((*npp1)->name, (*npp2)->name);
-} /* cmp_name */
+}
void
&& symtab.base[index].hist.time == 0)
{
continue;
- } /* if */
+ }
name_sorted_syms[nnames++] = &symtab.base[index];
- } /* for */
+ }
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];
- } /* for */
+ }
printf ("\f\nIndex by function name\n\n");
index = (todo + 2) / 3;
for (i = 0; i < index; i++)
else
{
sprintf (buf, "(%d)", sym->cg.index);
- } /* if */
+ }
if (j < nnames)
{
if (bsd_style_output)
for (; col < starting_col + 5; ++col)
{
putchar (' ');
- } /* for */
+ }
printf (" %s ", buf);
col += print_name_only (sym);
if (!line_granularity && sym->is_static && sym->file)
else
{
filename = sym->file->name;
- } /* if */
- } /* if */
+ }
+ }
printf (" (%s)", filename);
col += strlen (filename) + 3;
- } /* if */
- } /* if */
+ }
+ }
}
else
{
- printf ("%6.6s ", buf);
- sprintf (buf, "<cycle %d>", sym->cg.cyc.num);
- printf ("%-19.19s", buf);
- } /* if */
+ if (bsd_style_output)
+ {
+ printf ("%6.6s ", buf);
+ sprintf (buf, "<cycle %d>", sym->cg.cyc.num);
+ printf ("%-19.19s", buf);
+ }
+ else
+ {
+ col += strlen (buf);
+ for (; col < starting_col + 5; ++col)
+ putchar (' ');
+ printf (" %s ", buf);
+ sprintf (buf, "<cycle %d>", sym->cg.cyc.num);
+ printf ("%s", buf);
+ col += strlen (buf);
+ }
+ }
starting_col += column_width;
- } /* for */
+ }
printf ("\n");
- } /* for */
+ }
free (name_sorted_syms);
-} /* cg_print_index */
+}
+
+/* Compare two arcs based on their usage counts. We want to sort
+ in descending order. */
+static int
+DEFUN (cmp_arc_count, (left, right), const PTR left AND 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
+DEFUN (cmp_fun_nuses, (left, right), const PTR left AND 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
+DEFUN_VOID (cg_print_function_ordering)
+{
+ unsigned long index, used, unused, scratch_index;
+ unsigned long unplaced_arc_count, high_arc_count, scratch_arc_count;
+#ifdef __GNU_C__
+ 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;
+
+ 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 (index = 0, used = 0, unused = 0; index < symtab.len; index++)
+ {
+ if (symtab.base[index].ncalls == 0)
+ {
+ /* Filter out gprof generated names. */
+ if (strcmp (symtab.base[index].name, "<locore>")
+ && strcmp (symtab.base[index].name, "<hicore>"))
+ {
+ unused_syms[unused++] = &symtab.base[index];
+ symtab.base[index].has_been_placed = 1;
+ }
+ }
+ else
+ {
+ used_syms[used++] = &symtab.base[index];
+ symtab.base[index].has_been_placed = 0;
+ symtab.base[index].next = 0;
+ symtab.base[index].prev = 0;
+ symtab.base[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 (index = 0; index < numarcs; index++)
+ {
+ total_arcs += arcs[index]->count;
+ arcs[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 (index = 0; index < numarcs; index++)
+ {
+ tmp_arcs_count += arcs[index]->count;
+
+ /* Count how many times each parent and child are used up
+ to our threshhold of arcs (90%). */
+ if ((double)tmp_arcs_count / (double)total_arcs > 0.90)
+ break;
+
+ arcs[index]->child->nuses++;
+ }
+
+ /* Now sort a temporary symbol table based on the number of
+ times each function was used in the highest used arcs. */
+ bcopy (used_syms, scratch_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 (index = 0; index < used / 80; index++)
+ {
+ Sym *sym = scratch_syms[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 = 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 (index = 0; index < scratch_arc_count; index++)
+ {
+ Arc *arc = scratch_arcs[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[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 (index = 0; index < scratch_index; index++)
+ {
+ if (scratch_syms[index]->has_been_placed)
+ printf ("%s\n", scratch_syms[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 (index = 0; index < used; index++)
+ if (used_syms[index]->has_been_placed == 0)
+ printf("%s\n", used_syms[index]->name);
+
+ /* Output the unused functions. */
+ for (index = 0; index < unused; index++)
+ printf("%s\n", unused_syms[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 ARCS with NUMARCS entries;
+ place unused arcs into UNPLACED_ARCS/UNPLACED_ARC_COUNT.
+
+ If ALL is nonzero, then place all functions referenced by ARCS,
+ else only place those referenced in the top 99% of the arcs in ARCS. */
+
+#define MOST 0.99
+static void
+order_and_dump_functions_by_arcs (arcs, numarcs, all,
+ unplaced_arcs, unplaced_arc_count)
+ Arc **arcs;
+ unsigned long numarcs;
+ int all;
+ Arc **unplaced_arcs;
+ unsigned long *unplaced_arc_count;
+{
+#ifdef __GNU_C__
+ unsigned long long tmp_arcs, total_arcs;
+#else
+ unsigned long tmp_arcs, total_arcs;
+#endif
+ unsigned int index;
+
+ /* If needed, compute the total arc count.
+
+ Note we don't compensate for overflow if that happens! */
+ if (! all)
+ {
+ total_arcs = 0;
+ for (index = 0; index < numarcs; index++)
+ total_arcs += arcs[index]->count;
+ }
+ else
+ total_arcs = 0;
+
+ tmp_arcs = 0;
+ for (index = 0; index < numarcs; index++)
+ {
+ Sym *sym1, *sym2;
+ Sym *child, *parent;
+
+ tmp_arcs += arcs[index]->count;
+
+ /* Ignore this arc if it's already been placed. */
+ if (arcs[index]->has_been_placed)
+ continue;
+
+ child = arcs[index]->child;
+ parent = arcs[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)++] = arcs[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)++] = arcs[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)++] = arcs[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)++] = arcs[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;
+ arcs[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;
+ arcs[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;
+ arcs[index]->has_been_placed = 1;
+ }
+ else
+ {
+ /* parent-next and child-prev */
+ parent->next = child;
+ child->prev = parent;
+ arcs[index]->has_been_placed = 1;
+ }
+ }
+ }
+
+ /* Dump the chains of functions we've made. */
+ for (index = 0; index < numarcs; index++)
+ {
+ Sym *sym;
+ if (arcs[index]->parent->has_been_placed
+ || arcs[index]->child->has_been_placed)
+ continue;
+
+ sym = arcs[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 (index = 0; index < numarcs; index++)
+ {
+ Sym *sym;
+ if (arcs[index]->parent->has_been_placed
+ || arcs[index]->child->has_been_placed)
+ continue;
+
+ sym = arcs[index]->parent;
+
+ sym->has_been_placed = 1;
+ printf ("%s\n", sym->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. */
+
+struct function_map {
+ char *function_name;
+ char *file_name;
+};
+
+void
+DEFUN_VOID (cg_print_file_ordering)
+{
+ unsigned long scratch_arc_count, index;
+ Arc **scratch_arcs;
+ extern struct function_map *symbol_map;
+ extern int symbol_map_count;
+ char *last;
+
+ scratch_arc_count = 0;
+
+ scratch_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
+ for (index = 0; index < numarcs; index++)
+ {
+ if (! arcs[index]->parent->mapped
+ || ! arcs[index]->child->mapped)
+ arcs[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 (index = 0; index < symtab.len; index++)
+ {
+ if (symtab.base[index].mapped
+ && ! symtab.base[index].has_been_placed)
+ printf ("%s\n", symtab.base[index].name);
+ }
+
+ /* Now output any .o's that didn't have any text symbols. */
+ last = NULL;
+ for (index = 0; index < symbol_map_count; index++)
+ {
+ int index2;
+
+ /* Don't bother searching if this symbol is the
+ same as the previous one. */
+ if (last && !strcmp (last, symbol_map[index].file_name))
+ continue;
+
+ for (index2 = 0; index2 < symtab.len; index2++)
+ {
+ if (! symtab.base[index2].mapped)
+ continue;
+
+ if (!strcmp (symtab.base[index2].name, symbol_map[index].file_name))
+ break;
+ }
-/*** end of cg_print.c ***/
+ /* 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[index].file_name);
+ last = symbol_map[index].file_name;
+ }
+}