[google][4.6] Bug fixes to function reordering linker plugin to handle local and comdat functions. (issue5851044)

[tmsriram at google dot com (Sriraman Tallam)]

This patch fixes bugs in section_ordering linker plugin to correctly handle functions that are file local or comdat. Such functions could be
defined more than once in different object files and can have the same name. The callgraph edge profiles should be attributed to the right local function. Also, comdat functions in the same group must be treated as one function.

This linker plugin is only available in the google/gcc-4_6 branch. I am working on preparing a patch for trunk.


	* callgraph.h (push_mm_ptr): New function.
	(make_edge_list): Call push_mm_ptr for heap allocs.
	(make_mode): Ditto.
	(make_edge): Ditto.
	(section_type, comdat_group, next, group): Add new fields
	to struct Section_id.
	(make_section_id): Initialize new fields. Add new args.
	(parse_callgraph_section_contents): Add args.
	* function_reordering_plugin.c (claim_file_hook): Call
	push_mm_ptr. Fix call to parse_callgraph_section_contents.
	(all_symbols_read_hook): Call push_mm_ptr. Remove calls to free.
	* callgraph.c (mm_node): New struct.
	(push_mm_ptr): New function.
	(canonicalize_function_name): New function.
	(parse_callgraph_section_contents): Add args. Call
	canonicalize_function_name.
	(num_sections): New global.
	(NUM_SECTION_TYPES): New constant.
	(section_types): New constant.
	(section_priority): New constant.
	(map_section_name_to_index): Remove sections. Replace sections with
	section_types. Call canonicalize_function_name.	Chain all created
	sections. Check for comdat sections and group them together.
	(write_out_node): Output sections into section_start and section_end
	chain. Handle comdats.
	(get_layout): Make new chains for each section type. Output each chain
	one by one into handles and shndx. Output all the sections created.
	(cleanup): Free all heap allocated objects tracked by mm_node_chain.


Index: callgraph.h
===================================================================
--- callgraph.h	(revision 185543)
+++ callgraph.h	(working copy)
@@ -1,6 +1,7 @@
 /* Callgraph implementation.
    Copyright (C) 2011 Free Software Foundation, Inc.
-   Contributed by Sriraman Tallam (tmsriram@google.com).
+   Contributed by Sriraman Tallam (tmsriram@google.com)
+   and Easwaran Raman (eraman@google.com).
 
 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
@@ -26,6 +27,9 @@ along with this program; see the file COPYING3.  I
 #include <string.h>
 #include "libiberty.h"
 
+/* Push a pointer that should be freed after the plugin is done.  */
+void push_mm_ptr (void *ptr);
+
 struct edge_d;
 typedef struct edge_d Edge;
 
@@ -41,6 +45,7 @@ inline static Edge_list *
 make_edge_list (Edge *e)
 {
   Edge_list *list = XNEW (Edge_list);
+  push_mm_ptr (list);
   list->edge = e;
   list->next = NULL;
   list->prev = NULL;
@@ -69,6 +74,7 @@ inline static Node *
 make_node (unsigned int id, char *name)
 {
   Node *node = XNEW (Node);
+  push_mm_ptr (node);
   node->id = id;
   node->name = name;
   node->is_real_node = 0;
@@ -86,9 +92,9 @@ make_node (unsigned int id, char *name)
 inline static void
 merge_node (Node *merger, Node *mergee)
 {
-    merger->last_merge_node->merge_next = mergee;
-    merger->last_merge_node = mergee->last_merge_node;
-    mergee->is_merged = 1;
+  merger->last_merge_node->merge_next = mergee;
+  merger->last_merge_node = mergee->last_merge_node;
+  mergee->is_merged = 1;
 }
 
 inline static void
@@ -136,6 +142,7 @@ inline static Edge *
 make_edge (Node *first, Node *second, unsigned int weight)
 {
   Edge *edge = XNEW (Edge);
+  push_mm_ptr (edge);
   edge->first_function = first;
   edge->second_function = second;
   edge->weight = weight;
@@ -148,21 +155,7 @@ make_edge (Node *first, Node *second, unsigned int
   return edge;
 }
 
-/* Frees the chain of edges.  */
 inline static void
-free_edge_chain (Edge *edge_chain)
-{
-  Edge *edge;
-
-  for (edge = edge_chain; edge != NULL; )
-    {
-      Edge *next_edge = edge->next;
-      free (edge);
-      edge = next_edge;
-    }
-}
-
-inline static void
 set_edge_type (Edge *edge)
 {
   if (edge->first_function->is_real_node
@@ -200,7 +193,7 @@ reset_functions (Edge *e, Node *n1, Node *n2)
 }
 
 /* A Section is represented by its object handle and the section index. */
-typedef struct
+typedef struct section_id_
 {
   /* Name of the function.  */
   char *name;
@@ -208,16 +201,34 @@ reset_functions (Edge *e, Node *n1, Node *n2)
   char *full_name;
   void *handle;
   int shndx;
+  /* Type of prefix in section name.  */
+  int section_type;
+  /* Pointer to the next section in the same comdat_group.  */
+  struct section_id_ *comdat_group;
+  /* Chain all the sections created.  */
+  struct section_id_ *next;
+  /* Used for grouping sections.  */
+  struct section_id_ *group;
+  /* Check if this section has been considered for output.  */
+  char processed;
 } Section_id;
 
 inline static Section_id *
-make_section_id (char *name, char *full_name, void *handle, int shndx)
+make_section_id (char *name, char *full_name,
+		 int section_type,
+		 void *handle, int shndx)
 {
   Section_id *s = XNEW (Section_id);
+  push_mm_ptr (s);
   s->name = name;
   s->full_name = full_name;
+  s->section_type = section_type;
   s->handle = handle;
   s->shndx = shndx;
+  s->comdat_group = NULL;
+  s->next = NULL;
+  s->group = NULL;
+  s->processed = 0;
 
   return s;
 }
@@ -256,8 +267,9 @@ void
 map_section_name_to_index (char *section_name, void *handle, int shndx);
 
 void
-parse_callgraph_section_contents (unsigned char *section_contents,
-                                  unsigned int length);
+parse_callgraph_section_contents (void *handle,
+				  unsigned char *section_contents,
+				  unsigned int length);
 
 void dump_functions ();
 void dump_edges ();
Index: function_reordering_plugin.c
===================================================================
--- function_reordering_plugin.c	(revision 185543)
+++ function_reordering_plugin.c	(working copy)
@@ -1,6 +1,7 @@
 /* Function re-ordering plugin for gold.
    Copyright (C) 2011 Free Software Foundation, Inc.
-   Contributed by Sriraman Tallam (tmsriram@google.com).
+   Contributed by Sriraman Tallam (tmsriram@google.com)
+   and Easwaran Raman (eraman@google.com).
 
 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
@@ -89,6 +90,7 @@ static int no_op = 0;
 void get_filename (const char *name)
 {
   out_file = (char *) malloc (strlen (name) + 1);
+  push_mm_ptr (out_file);
   strcpy (out_file, name);
 }
 
@@ -230,6 +232,7 @@ claim_file_hook (const struct ld_plugin_input_file
       (*get_input_section_type) (section, &type);
 
       (*get_input_section_name) (section, &name);
+      push_mm_ptr (name);
       if (type == SHT_PROGBITS && is_prefix_of (".text.", name))
         {
           map_section_name_to_index (name, file->handle, shndx);
@@ -244,11 +247,12 @@ claim_file_hook (const struct ld_plugin_input_file
 	    &length);
 	  unsigned char *section_contents;
 	  section_contents = (unsigned char *) malloc (length);
+	  push_mm_ptr (section_contents);
 	  memcpy (section_contents, section_contents_ptr, length);
-          parse_callgraph_section_contents (section_contents, (unsigned int)length);
+          parse_callgraph_section_contents (file->handle,
+					    section_contents,
+					    (unsigned int)length);
         }
-      else if (name != NULL)
-        free (name);
     }
 
   return LDPS_OK;
@@ -290,6 +294,8 @@ all_symbols_read_hook (void)
   num_entries = get_layout (fp, &handles, &shndx);
   section_list = (struct ld_plugin_section *)
 		  malloc (num_entries * sizeof (struct ld_plugin_section));
+  push_mm_ptr (section_list);
+
   for (i = 0; i < num_entries; i++)
     {
       section_list[i].handle = handles[i];
@@ -301,9 +307,6 @@ all_symbols_read_hook (void)
     fclose (fp);
   /* Pass the new order of functions to the linker.  */
   update_section_order (section_list, num_entries);
-  free (section_list);
-  free (handles);
-  free (shndx);
   cleanup ();
   return LDPS_OK;
 }
Index: callgraph.c
===================================================================
--- callgraph.c	(revision 185543)
+++ callgraph.c	(working copy)
@@ -1,6 +1,7 @@
 /* Callgraph implementation.
    Copyright (C) 2011 Free Software Foundation, Inc.
-   Contributed by Sriraman Tallam (tmsriram@google.com).
+   Contributed by Sriraman Tallam (tmsriram@google.com)
+   and Easwaran Raman (eraman@google.com).
 
 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
@@ -110,6 +111,25 @@ edge_map_htab_eq_descriptor (const void *p1, const
 
 /*****************************************************************************/
 
+
+/* Keep track of all allocated memory.  */
+typedef struct
+{
+  void *ptr;
+  void *next;
+} mm_node;
+
+mm_node *mm_node_chain = NULL;
+
+void
+push_mm_ptr (void *ptr)
+{
+  mm_node *node = XNEW (mm_node);
+  node->ptr = ptr;
+  node->next = mm_node_chain;
+  mm_node_chain = node;
+}
+
 /* Chain of all the created nodes.  */
 Node *node_chain = NULL;
 /* Number of nodes that correspond to functions which will be reordered.  */
@@ -275,9 +295,26 @@ void dump_edges (FILE *fp)
     }
 }
 
-/* HEADER_LEN is the length of string 'Function '.  */
-const int HEADER_LEN = 9;
+/* For file local functions, append a unique identifier corresponding to
+   the file, FILE_HANDLE, to the NAME to keep the name unique.  */
 
+static char *
+canonicalize_function_name (void *file_handle, char *name)
+{
+  /* Number of hexadecimal digits in file_handle, plus length of "0x".  */
+  const int FILE_HANDLE_LEN = sizeof (void *) * 2 + 2;
+  char *canonical_name;
+
+  /* File local functions have _ZL prefix in the mangled name.  */
+  if (!is_prefix_of ("_ZL", name))
+    return name;
+
+  canonical_name = (char *) malloc (strlen(name) + FILE_HANDLE_LEN + 2);
+  push_mm_ptr (canonical_name);
+  sprintf (canonical_name, "%s.%p", name, file_handle);
+  return canonical_name;
+}
+
 /* Parse the section contents of ".gnu.callgraph.text"  sections and create
    call graph edges with appropriate weights. The section contents have the
    following format :
@@ -288,7 +325,8 @@ void dump_edges (FILE *fp)
    <edge count between caller and callee_2>
    ....  */
 void
-parse_callgraph_section_contents (unsigned char *section_contents,
+parse_callgraph_section_contents (void *file_handle,
+				  unsigned char *section_contents,
 				  unsigned int length)
 {
   char *contents;
@@ -296,12 +334,15 @@ void
   unsigned int read_length = 0, curr_length = 0;
   Node *caller_node;
 
+  /* HEADER_LEN is the length of string 'Function '.  */
+  const int HEADER_LEN = 9;
+
    /* First string in contents is 'Function <function-name>'.  */
   assert (length > 0);
   contents = (char*) (section_contents);
   caller = get_next_string (&contents, &read_length);
   assert (read_length > HEADER_LEN);
-  caller = caller + HEADER_LEN;
+  caller = canonicalize_function_name (file_handle, caller + HEADER_LEN);
   curr_length = read_length;
   caller_node = get_function_node (caller);
 
@@ -314,6 +355,7 @@ void
       Node *callee_node;
 
       callee = get_next_string (&contents, &read_length);
+      callee = canonicalize_function_name (file_handle, callee);
       curr_length += read_length;
       callee_node = get_function_node (callee);
 
@@ -456,6 +498,20 @@ find_pettis_hansen_function_layout (FILE *fp)
     }
 }
 
+/* The list of sections created, excluding comdat duplicates.  */
+Section_id *first_section = NULL;
+/* The number of sections.  */
+int num_sections = 0;
+
+const int NUM_SECTION_TYPES = 5;
+const char *section_types[] = {".text.hot.",
+				".text.cold.",
+				".text.unlikely.",
+				".text.startup.",
+				".text." };
+
+const int section_priority[] = {0, 3, 4, 2, 1};
+
 /* Maps the function name corresponding to section SECTION_NAME to the
    object handle and the section index.  */
 
@@ -463,24 +519,23 @@ void
 map_section_name_to_index (char *section_name, void *handle, int shndx)
 {
   void **slot;
-  const char *sections[] = {".text.hot.",
-			    ".text.unlikely.",
-			    ".text.cold.",
-			    ".text.startup.",
-			    ".text." };
   char *function_name = NULL;
-  int i;
+  int i, section_type = -1;
 
-  for (i = 0; i < ARRAY_SIZE (sections); ++i)
+  for (i = 0; i < ARRAY_SIZE (section_types); ++i)
     {
-      if (is_prefix_of (sections[i], section_name))
+      if (is_prefix_of (section_types[i], section_name))
         {
-          function_name = section_name + strlen (sections[i]);
+          function_name = section_name + strlen (section_types[i]);
+  	  section_type = i;
 	  break;
         }
     }
-  assert (function_name != NULL);
 
+  assert (function_name != NULL && section_type >= 0);
+  function_name = canonicalize_function_name (handle, function_name);
+  num_sections++;
+
   /* Allocate section_map.  */
   if (section_map == NULL)
     {
@@ -494,24 +549,67 @@ map_section_name_to_index (char *section_name, voi
 				   htab_hash_string (function_name),
 				   INSERT);
   if (*slot == NULL)
-    *slot = make_section_id (function_name, section_name, handle, shndx);
+    {
+      Section_id *section = make_section_id (function_name, section_name,
+					     section_type, handle, shndx);
+      /* Chain it to the list of sections.  */
+      section->next = first_section;
+      first_section = section;
+      *slot = section;
+    }
+  else
+    {
+      /* The function already exists, it must be a COMDAT.  Only one section
+	 in the comdat group will be kept, we don't know which.  Chain all the
+         comdat sections in the same comdat group to be emitted together later.
+         Keep one section as representative (kept) and update its section_type
+         to be equal to the type of the highest priority section in the
+         group.  */
+      Section_id *kept = (Section_id *)(*slot);
+      Section_id *section = make_section_id (function_name, section_name,
+                                             section_type, handle, shndx);
+      if (section_priority[kept->section_type]
+	  > section_priority[section_type])
+        kept->section_type = section_type;
+
+      section->comdat_group = kept->comdat_group;
+      kept->comdat_group = section;
+    }
 }
 
+/* Find the section corresponding to function name NAME.  If it is a comdat,
+   get all the comdat sections in the group.  Chain these sections to
+   SECTION_END.  Set SECTION_START if it is NULL.  */
+
 static void
-write_out_node (FILE *fp, char *name,
-		void **handles, unsigned int *shndx, int position)
+write_out_node (char *name, Section_id **section_start,
+	        Section_id **section_end)
 {
   void *slot;
   slot = htab_find_with_hash (section_map, name, htab_hash_string (name));
   if (slot != NULL)
     {
       Section_id *s = (Section_id *)slot;
-      handles[position] = s->handle;
-      shndx[position] = s->shndx;
-      if (fp != NULL)
-	fprintf (fp, "%s\n", s->full_name);
-      /* No more use of full_name  */
-      free (s->full_name);
+      s->processed = 1;
+      if (*section_start == NULL)
+	{
+	  *section_start = s;
+	  *section_end = s;
+	}
+      else
+	{
+	  (*section_end)->group = s;
+	  *section_end = s;
+	}
+
+      /* Print all other sections in the same comdat group.  */
+      while (s->comdat_group)
+        {
+          s = s->comdat_group;
+          s->processed = 1;
+	  (*section_end)->group = s;
+	  *section_end = s;
+	}
     }
 }
 
@@ -521,67 +619,95 @@ unsigned int
 get_layout (FILE *fp, void*** handles,
             unsigned int** shndx)
 {
-  Node *it;
-  int position = 0;
+  Node *n_it;
+  int  i = 0;
+  int position;
+  /* Form NUM_SECTION_TYPES + 1 groups of sections.  Index 0 corresponds
+     to the list of sections that correspond to functions in the callgraph.
+     For other sections, they are grouped by section_type and stored in
+     index: (section_type + 1).   SECTION_START points to the first
+     section in each section group and SECTION_END points to the last.  */
+  Section_id *section_start[NUM_SECTION_TYPES + 1];
+  Section_id *section_end[NUM_SECTION_TYPES + 1];
+  Section_id *s_it;
 
-  *handles = XNEWVEC (void *, num_real_nodes);
-  *shndx = XNEWVEC (unsigned int, num_real_nodes);
+  *handles = XNEWVEC (void *, num_sections);
+  *shndx = XNEWVEC (unsigned int, num_sections);
 
-  /* Dump edges to the final reordering file.  */
+  push_mm_ptr (*handles);
+  push_mm_ptr (*shndx);
 
-  for (it = node_chain; it != NULL; it = it->next)
+  for (i = 0; i < NUM_SECTION_TYPES + 1; i++)
     {
+      section_start[i] = NULL;
+      section_end[i] = NULL;
+    }
+
+  /* Dump edges to the final reordering file.  */
+  for (n_it = node_chain; n_it != NULL; n_it = n_it->next)
+    {
       Node *node;
-      if (it->is_merged)
+      /* First, only consider nodes that are real and that have other
+	 nodes merged with it. */
+      if (n_it->is_merged || !n_it->is_real_node || !n_it->merge_next)
         continue;
-      if (it->is_real_node)
-        {
-	  write_out_node (fp, it->name, *handles, *shndx, position);
-	  position++;
-        }
-      node = it->merge_next;
+	
+      write_out_node (n_it->name, &section_start[0], &section_end[0]);
+      node = n_it->merge_next;
       while (node != NULL)
         {
           if (node->is_real_node)
-	    {
-	      write_out_node (fp, node->name, *handles, *shndx, position);
-	      position++;
-	    }
+	    write_out_node (node->name, &section_start[0], &section_end[0]);
           node = node->merge_next;
 	}
     }
+
+  /* Go through all the sections and sort unprocessed sections into different
+     section_type groups.  */
+  s_it = first_section;
+  while (s_it)
+    {
+      if (!s_it->processed)
+	{
+	  write_out_node (s_it->name, &section_start[s_it->section_type + 1],
+			  &section_end[s_it->section_type + 1]);
+	  s_it->processed = 1;
+	}
+      s_it = s_it->next;
+    } 
+     
+
+  position = 0;
+  for (i=0; i < NUM_SECTION_TYPES + 1; i++)
+    {
+      s_it = section_start[i];
+      while (s_it)
+        {
+	  assert (position < num_sections);
+          (*handles)[position] = s_it->handle;
+          (*shndx)[position] = s_it->shndx;
+          position++;
+	  if (fp != NULL)
+            fprintf (fp, "%s\n", s_it->full_name);
+	  s_it = s_it->group;
+        }
+    }
   return position;
 }
 
-/* Free all heap objects.  */
-
 void
 cleanup ()
 {
-  Node *node;
-
-  /* Free all nodes and edge_lists.  */
-  for (node = node_chain; node != NULL; )
+  /* Go through heap allocated objects and free them.  */
+  while (mm_node_chain)
     {
-      Node *next_node = node->next;
-      Edge_list *it;
-      for (it = node->edge_list; it != NULL; )
-        {
-          Edge_list *next_it = it->next;
-          free (it);
-          it = next_it;
-        }
+      mm_node *node = mm_node_chain;
+      free (node->ptr);
+      mm_node_chain = node->next;
       free (node);
-      node = next_node;
     }
 
-  /* Free all active_edges.  */
-  free_edge_chain (active_edges);
-
-  /* Free all inactive edges.  */
-  free_edge_chain (inactive_edges);
-
-  /* Delete all htabs.  */
+  /*  Delete all htabs. */
   htab_delete (section_map);
   htab_delete (function_map);
   htab_delete (edge_map);

--
This patch is available for review at http://codereview.appspot.com/5851044