Re: [PATCH] gold: make the kept comdat structure have a direct link to sections map

[Ian Lance Taylor <iant at google dot com>]

Mikolaj Zalewski <mikolajz@google.com> writes:

>   Currently, if a comdat is already declared in a previous object and
> we need to access its sections, Layout needs to map the comdat name to
> original object/section index and the obejct must map section the
> index to comdat information. With this patch, the Layout's
> Kept_section structure has already all the information about the
> comdat. The patch also changes the way comdat information is accessed
> - it only does one insert, instead of an insert and if insert failed
> then a find for the entry. This decreased linking CPU time on a sample
> test by 2-2,5%. It produces the same binary as the previous version
> and make check passed.
>
> 2009-02-27  Mikolaj Zalewski  <mikolajz@google.com>
> 	* layout.cc (find_or_add_comdat): a more generic version of add_comdat
> 	(add_comdat): removed
> 	* layout.h (Kept_section): move out of Layout
> 	(Kept_section::group_sections_): new field
> 	(Layout::Kep_section): remove
> 	(find_or_add_comdat): a more generic version of add_comdat
> 	(add_comdat): removed
> 	* object.cc (include_section_group): use find_or_add_comdat and
> Kept_section::group_sections_
> 	(include_linkonce_section): use find_or_add_comdat and
> Kept_section::group_sections_
> 	* object.cc (Comdat_group): removed
> 	(Comdat_group_table): removed
> 	(find_comdat_grouop): removed
> 	(add_comdat_group): removed
> 	(comdat_groups_): removed
> 	* plugin.cc (include_comdat_group): use the new Layout::find_or_add_comdat


Thanks!

I took the opportunity to clean up some style issues--field in a struct
should not use a trailing underscore, and I changed some indentation.
This is what I committed.

Ian


2009-03-01  Mikolaj Zalewski  <mikolajz@google.com>

	* layout.cc (Layout::find_or_add_kept_section): New function.
	(Layout::add_comdat): Removed.
	* layout.h (struct Kept_section): Move out of class Layout.
	Remove trailing underscores from field names.  Add group_sections
	field.  Rename group_ field to is_group.  Change all uses.
	(class Layout): Declare find_or_add_kept_section, not add_comdat.
	* object.cc (Sized_relobj::Sized_relobj): Don't initialize
	comdat_groups_ field.
	(Sized_relobj::include_section_group): Use
	find_or_add_kept_section and Kept_section::group_sections.
	(Sized_relobj::include_linkonce_section): Likewise.
	* object.cc (class Sized_relobj): Don't define Comdat_group or
	Comdat_group_table.  Remove find_comdat_group and
	add_comdat_group.  Remove comdat_groups_ field.
	* plugin.cc (include_comdat_group): Use
	Layout::find_or_add_kept_section.


Index: layout.cc
===================================================================
RCS file: /cvs/src/src/gold/layout.cc,v
retrieving revision 1.118
diff -p -u -r1.118 layout.cc
--- layout.cc	28 Feb 2009 04:39:57 -0000	1.118
+++ layout.cc	1 Mar 2009 22:16:19 -0000
@@ -2930,46 +2930,50 @@ Layout::output_section_name(const char* 
   return name;
 }
 
-// Record the signature of a comdat section, and return whether to
-// include it in the link.  If GROUP is true, this is a regular
-// section group.  If GROUP is false, this is a group signature
-// derived from the name of a linkonce section.  We want linkonce
-// signatures and group signatures to block each other, but we don't
-// want a linkonce signature to block another linkonce signature.
+// Check if a comdat group or .gnu.linkonce section with the given
+// NAME is selected for the link.  If there is already a section,
+// *KEPT_SECTION is set to point to the signature and the function
+// returns false.  Otherwise, the CANDIDATE signature is recorded for
+// this NAME in the layout object, *KEPT_SECTION is set to the
+// internal copy and the function return false.  In some cases, with
+// CANDIDATE->GROUP_ being false, KEPT_SECTION can point back to
+// CANDIDATE.
 
 bool
-Layout::add_comdat(Relobj* object, unsigned int shndx,
-                   const std::string& signature, bool group)
+Layout::find_or_add_kept_section(const std::string name,
+                                 Kept_section* candidate,
+                                 Kept_section** kept_section)
 {
-  Kept_section kept(object, shndx, group);
   std::pair<Signatures::iterator, bool> ins(
-    this->signatures_.insert(std::make_pair(signature, kept)));
+    this->signatures_.insert(std::make_pair(name, *candidate)));
 
+  if (kept_section)
+    *kept_section = &ins.first->second;
   if (ins.second)
     {
       // This is the first time we've seen this signature.
       return true;
     }
 
-  if (ins.first->second.group_)
+  if (ins.first->second.is_group)
     {
       // We've already seen a real section group with this signature.
       // If the kept group is from a plugin object, and we're in
       // the replacement phase, accept the new one as a replacement.
-      if (ins.first->second.object_ == NULL
+      if (ins.first->second.object == NULL
           && parameters->options().plugins()->in_replacement_phase())
         {
-          ins.first->second = kept;
+          ins.first->second = *candidate;
           return true;
         }
       return false;
     }
-  else if (group)
+  else if (candidate->is_group)
     {
       // This is a real section group, and we've already seen a
       // linkonce section with this signature.  Record that we've seen
       // a section group, and don't include this section group.
-      ins.first->second.group_ = true;
+      ins.first->second.is_group = true;
       return false;
     }
   else
@@ -2977,6 +2981,7 @@ Layout::add_comdat(Relobj* object, unsig
       // We've already seen a linkonce section and this is a linkonce
       // section.  These don't block each other--this may be the same
       // symbol name with different section types.
+      *kept_section = candidate;
       return true;
     }
 }
@@ -2991,8 +2996,8 @@ Layout::find_kept_object(const std::stri
   if (p == this->signatures_.end())
     return NULL;
   if (pshndx != NULL)
-    *pshndx = p->second.shndx_;
-  return p->second.object_;
+    *pshndx = p->second.shndx;
+  return p->second.object;
 }
 
 // Store the allocated sections into the section list.
@@ -3101,7 +3106,7 @@ Layout::write_sections_after_input_secti
     {
       off_t off = this->output_file_size_;
       off = this->set_section_offsets(off, POSTPROCESSING_SECTIONS_PASS);
-      
+
       // Now that we've finalized the names, we can finalize the shstrab.
       off =
 	this->set_section_offsets(off,
Index: layout.h
===================================================================
RCS file: /cvs/src/src/gold/layout.h,v
retrieving revision 1.60
diff -p -u -r1.60 layout.h
--- layout.h	28 May 2008 20:48:16 -0000	1.60
+++ layout.h	1 Mar 2009 22:16:19 -0000
@@ -1,6 +1,6 @@
 // layout.h -- lay out output file sections for gold  -*- C++ -*-
 
-// Copyright 2006, 2007, 2008 Free Software Foundation, Inc.
+// Copyright 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
 // Written by Ian Lance Taylor <iant@google.com>.
 
 // This file is part of gold.
@@ -89,6 +89,37 @@ class Layout_task_runner : public Task_f
   Mapfile* mapfile_;
 };
 
+// This struct holds information about the comdat or .gnu.linkonce
+// that will be kept.
+
+struct Kept_section
+{
+  Kept_section()
+    : object(NULL), shndx(0), is_group(false), group_sections(NULL)
+  { }
+  Kept_section(Relobj* a_object, unsigned int a_shndx, bool a_is_group)
+    : object(a_object), shndx(a_shndx), is_group(a_is_group),
+      group_sections(NULL)
+  { }
+
+  typedef Unordered_map<std::string, unsigned int> Comdat_group;
+
+  // The object containing the comdat or .gnu.linkonce.
+  Relobj* object;
+  // Index to the group section for comdats and the section itself for
+  // .gnu.linkonce.
+  unsigned int shndx;
+  // The Kept_sections are values of a mapping, that maps names to
+  // them.  This field is true if this struct is associated with the
+  // name of a comdat or .gnu.linkonce, false if it is associated with
+  // the name of a symbol obtained from the .gnu.linkonce.* name
+  // through some heuristics.
+  bool is_group;
+  // For comdats, a map from names of the sections in the group to
+  // indexes in OBJECT_.  NULL for .gnu.linkonce.
+  Comdat_group* group_sections;
+};
+
 // This class handles the details of laying out input sections.
 
 class Layout
@@ -225,18 +256,24 @@ class Layout
   {
     // Debugging sections can only be recognized by name.
     return (strncmp(name, ".debug", sizeof(".debug") - 1) == 0
-            || strncmp(name, ".gnu.linkonce.wi.", 
+            || strncmp(name, ".gnu.linkonce.wi.",
                        sizeof(".gnu.linkonce.wi.") - 1) == 0
             || strncmp(name, ".line", sizeof(".line") - 1) == 0
             || strncmp(name, ".stab", sizeof(".stab") - 1) == 0);
   }
 
-  // Record the signature of a comdat section, and return whether to
-  // include it in the link.  The GROUP parameter is true for a
-  // section group signature, false for a signature derived from a
-  // .gnu.linkonce section.
+  // Check if a comdat group or .gnu.linkonce section with the given
+  // NAME is selected for the link.  If there is already a section,
+  // *KEPT_SECTION is set to point to the signature and the function
+  // returns false.  Otherwise, the CANDIDATE signature is recorded
+  // for this NAME in the layout object, *KEPT_SECTION is set to the
+  // internal copy and the function return false.  In some cases, with
+  // CANDIDATE->GROUP_ being false, KEPT_SECTION can point back to
+  // CANDIDATE.
   bool
-  add_comdat(Relobj*, unsigned int, const std::string&, bool group);
+  find_or_add_kept_section(const std::string name,
+                           Kept_section* candidate,
+                           Kept_section** kept_section);
 
   // Find the given comdat signature, and return the object and section
   // index of the kept group.
@@ -577,19 +614,7 @@ class Layout
   static bool
   segment_precedes(const Output_segment* seg1, const Output_segment* seg2);
 
-  // A mapping used for group signatures.
-  struct Kept_section
-    {
-      Kept_section()
-        : object_(NULL), shndx_(0), group_(false)
-      { }
-      Kept_section(Relobj* object, unsigned int shndx, bool group)
-        : object_(object), shndx_(shndx), group_(group)
-      { }
-      Relobj* object_;
-      unsigned int shndx_;
-      bool group_;
-    };
+  // A mapping used for kept comdats/.gnu.linkonce group signatures.
   typedef Unordered_map<std::string, Kept_section> Signatures;
 
   // Mapping from input section name/type/flags to output section.  We
Index: object.cc
===================================================================
RCS file: /cvs/src/src/gold/object.cc,v
retrieving revision 1.87
diff -p -u -r1.87 object.cc
--- object.cc	28 Feb 2009 17:53:16 -0000	1.87
+++ object.cc	1 Mar 2009 22:16:20 -0000
@@ -327,7 +327,6 @@ Sized_relobj<size, big_endian>::Sized_re
     local_values_(),
     local_got_offsets_(),
     kept_comdat_sections_(),
-    comdat_groups_(),
     has_eh_frame_(false)
 {
 }
@@ -674,29 +673,25 @@ Sized_relobj<size, big_endian>::include_
 
   // Record this section group in the layout, and see whether we've already
   // seen one with the same signature.
-  bool include_group = ((flags & elfcpp::GRP_COMDAT) == 0
-                        || layout->add_comdat(this, index, signature, true));
-
+  bool include_group;
   Sized_relobj<size, big_endian>* kept_object = NULL;
-  Comdat_group* kept_group = NULL;
+  Kept_section::Comdat_group* kept_group = NULL;
 
-  if (!include_group)
+  if ((flags & elfcpp::GRP_COMDAT) == 0)
+    include_group = true;
+  else
     {
-      // This group is being discarded.  Find the object and group
-      // that was kept in its place.
-      unsigned int kept_group_index = 0;
-      Relobj* kept_relobj = layout->find_kept_object(signature,
-                                                     &kept_group_index);
-      kept_object = static_cast<Sized_relobj<size, big_endian>*>(kept_relobj);
-      if (kept_object != NULL)
-        kept_group = kept_object->find_comdat_group(kept_group_index);
-    }
-  else if (flags & elfcpp::GRP_COMDAT)
-    {
-      // This group is being kept.  Create the table to map section names
-      // to section indexes and add it to the table of groups.
-      kept_group = new Comdat_group();
-      this->add_comdat_group(index, kept_group);
+      Kept_section this_group(this, index, true);
+      Kept_section *kept_section_group;
+      include_group = layout->find_or_add_kept_section(signature,
+                                                       &this_group,
+                                                       &kept_section_group);
+      if (include_group)
+        kept_section_group->group_sections = new Kept_section::Comdat_group;
+
+      kept_group = kept_section_group->group_sections;
+      kept_object = (static_cast<Sized_relobj<size, big_endian>*>
+		     (kept_section_group->object));
     }
 
   size_t count = shdr.get_sh_size() / sizeof(elfcpp::Elf_Word);
@@ -745,7 +740,8 @@ Sized_relobj<size, big_endian>::include_
             {
               // Find the corresponding kept section, and store that info
               // in the discarded section table.
-              Comdat_group::const_iterator p = kept_group->find(mname);
+              Kept_section::Comdat_group::const_iterator p =
+                kept_group->find(mname);
               if (p != kept_group->end())
                 {
                   Kept_comdat_section* kept =
@@ -808,8 +804,12 @@ Sized_relobj<size, big_endian>::include_
     symname = strrchr(name, '.') + 1;
   std::string sig1(symname);
   std::string sig2(name);
-  bool include1 = layout->add_comdat(this, index, sig1, false);
-  bool include2 = layout->add_comdat(this, index, sig2, true);
+  Kept_section candidate1(this, index, false);
+  Kept_section candidate2(this, index, true);
+  Kept_section* kept1;
+  Kept_section* kept2;
+  bool include1 = layout->find_or_add_kept_section(sig1, &candidate1, &kept1);
+  bool include2 = layout->find_or_add_kept_section(sig2, &candidate2, &kept2);
 
   if (!include2)
     {
@@ -817,12 +817,12 @@ Sized_relobj<size, big_endian>::include_
       // name (i.e., the kept section was also a linkonce section).
       // In this case, the section index stored with the layout object
       // is the linkonce section that was kept.
-      unsigned int kept_group_index = 0;
-      Relobj* kept_relobj = layout->find_kept_object(sig2, &kept_group_index);
+      unsigned int kept_group_index = kept2->shndx;
+      Relobj* kept_relobj = kept2->object;
       if (kept_relobj != NULL)
         {
-          Sized_relobj<size, big_endian>* kept_object
-              = static_cast<Sized_relobj<size, big_endian>*>(kept_relobj);
+          Sized_relobj<size, big_endian>* kept_object =
+	    static_cast<Sized_relobj<size, big_endian>*>(kept_relobj);
           Kept_comdat_section* kept =
             new Kept_comdat_section(kept_object, kept_group_index);
           this->set_kept_comdat_section(index, kept);
@@ -837,17 +837,16 @@ Sized_relobj<size, big_endian>::include_
       // this linkonce section.  We'll handle the simple case where
       // the group has only one member section.  Otherwise, it's not
       // worth the effort.
-      unsigned int kept_group_index = 0;
-      Relobj* kept_relobj = layout->find_kept_object(sig1, &kept_group_index);
+      Relobj* kept_relobj = kept1->object;
       if (kept_relobj != NULL)
         {
           Sized_relobj<size, big_endian>* kept_object =
-              static_cast<Sized_relobj<size, big_endian>*>(kept_relobj);
-          Comdat_group* kept_group =
-            kept_object->find_comdat_group(kept_group_index);
+	    static_cast<Sized_relobj<size, big_endian>*>(kept_relobj);
+          Kept_section::Comdat_group* kept_group = kept1->group_sections;
           if (kept_group != NULL && kept_group->size() == 1)
             {
-              Comdat_group::const_iterator p = kept_group->begin();
+              Kept_section::Comdat_group::const_iterator p =
+		kept_group->begin();
               gold_assert(p != kept_group->end());
               Kept_comdat_section* kept =
                 new Kept_comdat_section(kept_object, p->second);
Index: object.h
===================================================================
RCS file: /cvs/src/src/gold/object.h,v
retrieving revision 1.70
diff -p -u -r1.70 object.h
--- object.h	28 Feb 2009 04:39:57 -0000	1.70
+++ object.h	1 Mar 2009 22:16:20 -0000
@@ -1584,32 +1584,6 @@ class Sized_relobj : public Relobj
   typedef std::map<unsigned int, Kept_comdat_section*>
       Kept_comdat_section_table;
 
-  // Information needed to keep track of kept comdat groups.  This is
-  // simply a map from the section name to its section index.  This may
-  // not be a one-to-one mapping, but we ignore that possibility since
-  // this is used only to attempt to handle stray relocations from
-  // non-comdat debug sections that refer to comdat loadable sections.
-  typedef Unordered_map<std::string, unsigned int> Comdat_group;
-
-  // A map from group section index to the table of group members.
-  typedef std::map<unsigned int, Comdat_group*> Comdat_group_table;
-
-  // Find a comdat group table given its group section SHNDX.
-  Comdat_group*
-  find_comdat_group(unsigned int shndx) const
-  {
-    Comdat_group_table::const_iterator p =
-      this->comdat_groups_.find(shndx);
-    if (p != this->comdat_groups_.end())
-      return p->second;
-    return NULL;
-  }
-
-  // Record a new comdat group whose group section index is SHNDX.
-  void
-  add_comdat_group(unsigned int shndx, Comdat_group* group)
-  { this->comdat_groups_[shndx] = group; }
-
   // Adjust a section index if necessary.
   unsigned int
   adjust_shndx(unsigned int shndx)
@@ -1823,8 +1797,6 @@ class Sized_relobj : public Relobj
   std::vector<Address> section_offsets_;
   // Table mapping discarded comdat sections to corresponding kept sections.
   Kept_comdat_section_table kept_comdat_sections_;
-  // Table of kept comdat groups.
-  Comdat_group_table comdat_groups_;
   // Whether this object has a GNU style .eh_frame section.
   bool has_eh_frame_;
   // The list of sections whose layout was deferred.
Index: plugin.cc
===================================================================
RCS file: /cvs/src/src/gold/plugin.cc,v
retrieving revision 1.11
diff -p -u -r1.11 plugin.cc
--- plugin.cc	13 Feb 2009 19:04:45 -0000	1.11
+++ plugin.cc	1 Mar 2009 22:16:20 -0000
@@ -506,7 +506,12 @@ Pluginobj::include_comdat_group(std::str
   // If this is the first time we've seen this comdat key, ask the
   // layout object whether it should be included.
   if (ins.second)
-    ins.first->second = layout->add_comdat(NULL, 1, comdat_key, true);
+    {
+      Kept_section to_add(NULL, 1, true);
+      ins.first->second = layout->find_or_add_kept_section(comdat_key,
+							   &to_add,
+							   NULL);
+    }
 
   return ins.first->second;
 }