* gprof.c (long_options): Add "--function-ordering" and

	"--file-ordering" options.
	(usage): Add new options to usage message.
	(main): Handle new options.
	* gprof.h (STYLE_FUNCTION_ORDER): Define.
	(STYLE_FILE_ORDER): Define.
	(function_mapping_file): Declare.
	* cg_arcs.c (arcs, numarcs): New globals.
	(arc_add): Put new arcs into the arc array so the function/file
	ordering code can examine them.
	* cg_arcs.h (struct arc): New field "has_been_placed".
	(arcs, numarcs): Declare new globals.
	* core.c (symbol_map, symbol_map_count): New globals.
	(read_function_mappings): New function to read in a function
	to object map file.
	(core_init): Call read_function_mappings if a function mapping
	file exists.
	(core_create_function_syms): Handle function to object file
	mappings.
	* symtab.h (struct sym): New fields "mapped", "has_been_placed",
	"nuses", "prev".
	* cg_print.c (cmp_arc_count): New function for sorting arcs.
	(cmp_fun_nuses): Likewise for functions.
	(cg_print_function_ordering): New function to print a suggested
	function ordering.
	(cg_print_file_ordering): Likewise for ordering .o files.
	(order_and_dump_functions_by_arcs): Helper function for function
	and object file ordering code.
Gprof changes for mentor vm work.

1 files changed, 616 insertions, 0 deletions

diff --git a/gprof/cg_print.c b/gprof/cg_print.c
index 460bc04..c2f6ecb 100644
--- a/gprof/cg_print.c
+++ b/gprof/cg_print.c
@@ -11,6 +11,9 @@
 #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));
@@ -654,3 +657,616 @@ DEFUN_VOID (cg_print_index)
     }
   free (name_sorted_syms);
 }
+
+/* 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;
+	}
+
+      /* 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;
+    } 
+}