+ 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 threshhold 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 (the_arcs, arc_count, all,
+ unplaced_arcs, unplaced_arc_count)
+ 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)