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);
