Rework merge_map for speed.

3 files changed, 263 insertions, 90 deletions

diff --git a/gold/merge.cc b/gold/merge.cc
index 0c4256b..d8648d6 100644
--- a/gold/merge.cc
+++ b/gold/merge.cc
@@ -30,31 +30,239 @@
 namespace gold
 {
 
-// Class Merge_map::Merge_key_less.
+// For each object with merge sections, we store an Object_merge_map.
+// This is used to map locations in input sections to a merged output
+// section.  The output section itself is not recorded here--it can be
+// found in the map_to_output_ field of the Object.
 
-// Sort the entries in a merge mapping.  The key is an input object, a
-// section index in that object, and an offset in that section.
+class Object_merge_map
+{
+ public:
+  Object_merge_map()
+    : first_shnum_(-1U), first_map_(),
+      second_shnum_(-1U), second_map_(),
+      section_merge_maps_()
+  { }
+
+  ~Object_merge_map();
+
+  // Add a mapping for MERGE_MAP, for the bytes from OFFSET to OFFSET
+  // + LENGTH in the input section SHNDX to OUTPUT_OFFSET in the
+  // output section.  An OUTPUT_OFFSET of -1 means that the bytes are
+  // discarded.
+  void
+  add_mapping(const Merge_map*, unsigned int shndx, off_t offset, off_t length,
+	      off_t output_offset);
+
+  // Get the output offset for an input address in MERGE_MAP.  The
+  // input address is at offset OFFSET in section SHNDX.  This sets
+  // *OUTPUT_OFFSET to the offset in the output section; this will be
+  // -1 if the bytes are not being copied to the output.  This returns
+  // true if the mapping is known, false otherwise.
+  bool
+  get_output_offset(const Merge_map*, unsigned int shndx, off_t offset,
+		    off_t *output_offset);
+
+ private:
+  // Map input section offsets to a length and an output section
+  // offset.  An output section offset of -1 means that this part of
+  // the input section is being discarded.
+  struct Input_merge_entry
+  {
+    // The offset in the input section.
+    off_t input_offset;
+    // The length.
+    off_t length;
+    // The offset in the output section.
+    off_t output_offset;
+  };
+
+  // A less-than comparison routine for Input_merge_entry.
+  struct Input_merge_compare
+  {
+    bool
+    operator()(const Input_merge_entry& i1, const Input_merge_entry& i2) const
+    { return i1.input_offset < i2.input_offset; }
+  };
+
+  // A list of entries for a particular section.
+  struct Input_merge_map
+  {
+    // The Merge_map for this section.
+    const Merge_map* merge_map;
+    // The list of mappings.
+    std::vector<Input_merge_entry> entries;
+    // Whether the ENTRIES field is sorted by input_offset.
+    bool sorted;
+
+    Input_merge_map()
+      : merge_map(NULL), entries(), sorted(true)
+    { }
+  };
+
+  // Map input section indices to merge maps.
+  typedef std::map<unsigned int, Input_merge_map*> Section_merge_maps;
+
+  // Return a pointer to the Input_merge_map to use for the input
+  // section SHNDX, or NULL.
+  Input_merge_map*
+  get_input_merge_map(unsigned int shndx);
+
+  // Get or make the the Input_merge_map to use for the section SHNDX
+  // with MERGE_MAP.
+  Input_merge_map*
+  get_or_make_input_merge_map(const Merge_map* merge_map, unsigned int shndx);
+
+  // Any given object file will normally only have a couple of input
+  // sections with mergeable contents.  So we keep the first two input
+  // section numbers inline, and push any further ones into a map.  A
+  // value of -1U in first_shnum_ or second_shnum_ means that we don't
+  // have a corresponding entry.
+  unsigned int first_shnum_;
+  Input_merge_map first_map_;
+  unsigned int second_shnum_;
+  Input_merge_map second_map_;
+  Section_merge_maps section_merge_maps_;
+};
+
+// Destructor.
+
+Object_merge_map::~Object_merge_map()
+{
+  for (Section_merge_maps::iterator p = this->section_merge_maps_.begin();
+       p != this->section_merge_maps_.end();
+       ++p)
+    delete p->second;
+}
+
+// Get the Input_merge_map to use for an input section, or NULL.
+
+Object_merge_map::Input_merge_map*
+Object_merge_map::get_input_merge_map(unsigned int shndx)
+{
+  gold_assert(shndx != -1U);
+  if (shndx == this->first_shnum_)
+    return &this->first_map_;
+  if (shndx == this->second_shnum_)
+    return &this->second_map_;
+  Section_merge_maps::const_iterator p = this->section_merge_maps_.find(shndx);
+  if (p != this->section_merge_maps_.end())
+    return p->second;
+  return NULL;
+}
 
-inline bool
-Merge_map::Merge_key_less::operator()(const Merge_key& mk1,
-				      const Merge_key& mk2) const
+// Get or create the Input_merge_map to use for an input section.
+
+Object_merge_map::Input_merge_map*
+Object_merge_map::get_or_make_input_merge_map(const Merge_map* merge_map,
+					      unsigned int shndx)
 {
-  // The order of different objects and different sections doesn't
-  // matter.  We want to get consistent results across links so we
-  // don't use pointer comparison.
-  if (mk1.object != mk2.object)
+  Input_merge_map* map = this->get_input_merge_map(shndx);
+  if (map != NULL)
+    {
+      // For a given input section in a given object, every mapping
+      // must be donw with the same Merge_map.
+      gold_assert(map->merge_map == merge_map);
+      return map;
+    }
+
+  // We need to create a new entry.
+  if (this->first_shnum_ == -1U)
     {
-      // Two different object files can have the same name: if foo.a
-      // includes both bar/qux.o and baz/qux.o, then both end up with
-      // the name foo.a(qux.o).  But it's impossible for two different
-      // object files to have both the same name and the same offset.
-      if (mk1.object->offset() != mk2.object->offset())
-        return mk1.object->offset() < mk2.object->offset();
-      return mk1.object->name() < mk2.object->name();
+      this->first_shnum_ = shndx;
+      this->first_map_.merge_map = merge_map;
+      return &this->first_map_;
     }
-  if (mk1.shndx != mk2.shndx)
-    return mk1.shndx < mk2.shndx;
-  return mk1.offset < mk2.offset;
+  if (this->second_shnum_ == -1U)
+    {
+      this->second_shnum_ = shndx;
+      this->second_map_.merge_map = merge_map;
+      return &this->second_map_;
+    }
+
+  Input_merge_map* new_map = new Input_merge_map;
+  new_map->merge_map = merge_map;
+  this->section_merge_maps_[shndx] = new_map;
+  return new_map;
+}
+
+// Add a mapping.
+
+void
+Object_merge_map::add_mapping(const Merge_map* merge_map, unsigned int shndx,
+			      off_t input_offset, off_t length,
+			      off_t output_offset)
+{
+  Input_merge_map* map = this->get_or_make_input_merge_map(merge_map, shndx);
+
+  // Try to merge the new entry in the last one we saw.
+  if (!map->entries.empty())
+    {
+      Input_merge_entry& entry(map->entries.back());
+
+      // If this entry is not in order, we need to sort the vector
+      // before looking anything up.
+      if (input_offset < entry.input_offset + entry.length)
+	{
+	  gold_assert(input_offset < entry.input_offset
+		      && input_offset + length <= entry.input_offset);
+	  map->sorted = false;
+	}
+      else if (entry.input_offset + entry.length == input_offset
+	       && (output_offset == -1
+		   ? entry.output_offset == -1
+		   : entry.output_offset + entry.length == output_offset))
+	{
+	  entry.length += length;
+	  return;
+	}
+    }
+
+  Input_merge_entry entry;
+  entry.input_offset = input_offset;
+  entry.length = length;
+  entry.output_offset = output_offset;
+  map->entries.push_back(entry);
+}
+
+// Get the output offset for an input address.
+
+bool
+Object_merge_map::get_output_offset(const Merge_map* merge_map,
+				    unsigned int shndx, off_t input_offset,
+				    off_t *output_offset)
+{
+  Input_merge_map* map = this->get_input_merge_map(shndx);
+  if (map == NULL || map->merge_map != merge_map)
+    return false;
+
+  if (!map->sorted)
+    {
+      std::sort(map->entries.begin(), map->entries.end(),
+		Input_merge_compare());
+      map->sorted = true;
+    }
+
+  Input_merge_entry entry;
+  entry.input_offset = input_offset;
+  std::vector<Input_merge_entry>::const_iterator p =
+    std::lower_bound(map->entries.begin(), map->entries.end(),
+		     entry, Input_merge_compare());
+  if (p == map->entries.end() || p->input_offset > input_offset)
+    {
+      if (p == map->entries.begin())
+	return false;
+      --p;
+      gold_assert(p->input_offset <= input_offset);
+    }
+
+  if (input_offset - p->input_offset >= p->length)
+    return false;
+
+  *output_offset = p->output_offset;
+  if (*output_offset != -1)
+    *output_offset += (input_offset - p->input_offset);
+  return true;
 }
 
 // Class Merge_map.
@@ -67,18 +275,14 @@ void
 Merge_map::add_mapping(Relobj* object, unsigned int shndx,
 		       off_t offset, off_t length, off_t output_offset)
 {
-  Merge_key mk;
-  mk.object = object;
-  mk.shndx = shndx;
-  mk.offset = offset;
-
-  Merge_value mv;
-  mv.length = length;
-  mv.output_offset = output_offset;
-
-  std::pair<Merge_mapping::iterator, bool> ins =
-    this->merge_map_.insert(std::make_pair(mk, mv));
-  gold_assert(ins.second);
+  Object_merge_map* object_merge_map = object->merge_map();
+  if (object_merge_map == NULL)
+    {
+      object_merge_map = new Object_merge_map();
+      object->set_merge_map(object_merge_map);
+    }
+
+  object_merge_map->add_mapping(this, shndx, offset, length, output_offset);
 }
 
 // Return the output offset for an input address.  The input address
@@ -90,34 +294,11 @@ bool
 Merge_map::get_output_offset(const Relobj* object, unsigned int shndx,
 			     off_t offset, off_t* output_offset) const
 {
-  Merge_key mk;
-  mk.object = object;
-  mk.shndx = shndx;
-  mk.offset = offset;
-  Merge_mapping::const_iterator p = this->merge_map_.lower_bound(mk);
-
-  // If MK is not in the map, lower_bound returns the next iterator
-  // larger than it.
-  if (p == this->merge_map_.end()
-      || p->first.object != object
-      || p->first.shndx != shndx
-      || p->first.offset != offset)
-    {
-      if (p == this->merge_map_.begin())
-	return false;
-      --p;
-    }
-
-  if (p->first.object != object || p->first.shndx != shndx)
-    return false;
-
-  if (offset - p->first.offset >= p->second.length)
+  Object_merge_map* object_merge_map = object->merge_map();
+  if (object_merge_map == NULL)
     return false;
-
-  *output_offset = p->second.output_offset;
-  if (*output_offset != -1)
-    *output_offset += (offset - p->first.offset);
-  return true;
+  return object_merge_map->get_output_offset(this, shndx, offset,
+					     output_offset);
 }
 
 // Class Output_merge_base.
diff --git a/gold/merge.h b/gold/merge.h
index 1f750c5..ad00997 100644
--- a/gold/merge.h
+++ b/gold/merge.h
@@ -32,13 +32,13 @@ namespace gold
 {
 
 // This class manages mappings from input sections to offsets in an
-// output section.  This is used where input sections are merged.
+// output section.  This is used where input sections are merged.  The
+// actual data is stored in fields in Object.
 
 class Merge_map
 {
  public:
   Merge_map()
-    : merge_map_()
   { }
 
   // Add a mapping for the bytes from OFFSET to OFFSET + LENGTH in the
@@ -57,34 +57,6 @@ class Merge_map
   bool
   get_output_offset(const Relobj* object, unsigned int shndx, off_t offset,
 		    off_t *output_offset) const;
-
- private:
-  // We build a mapping from OBJECT/SHNDX/OFFSET to an offset and
-  // length in the output section.
-  struct Merge_key
-  {
-    const Relobj* object;
-    unsigned int shndx;
-    off_t offset;
-  };
-
-  struct Merge_key_less
-  {
-    inline bool
-    operator()(const Merge_key&, const Merge_key&) const;
-  };
-
-  struct Merge_value
-  {
-    off_t length;
-    off_t output_offset;
-  };
-
-  typedef std::map<Merge_key, Merge_value, Merge_key_less> Merge_mapping;
-
-  // A mapping from input object/section/offset to offset in output
-  // section.
-  Merge_mapping merge_map_;
 };
 
 // A general class for SHF_MERGE data, to hold functions shared by
diff --git a/gold/object.h b/gold/object.h
index 6f06fa8..6991d26 100644
--- a/gold/object.h
+++ b/gold/object.h
@@ -39,6 +39,7 @@ class Layout;
 class Output_section;
 class Output_file;
 class Dynobj;
+class Object_merge_map;
 
 template<typename Stringpool_char>
 class Stringpool_template;
@@ -411,7 +412,10 @@ class Relobj : public Object
 {
  public:
   Relobj(const std::string& name, Input_file* input_file, off_t offset = 0)
-    : Object(name, input_file, false, offset)
+    : Object(name, input_file, false, offset),
+      map_to_output_(),
+      object_merge_map_(NULL),
+      relocs_must_follow_section_writes_(false)
   { }
 
   // Read the relocs.
@@ -481,6 +485,19 @@ class Relobj : public Object
   relocs_must_follow_section_writes()
   { return this->relocs_must_follow_section_writes_; }
 
+  // Return the object merge map.
+  Object_merge_map*
+  merge_map() const
+  { return this->object_merge_map_; }
+
+  // Set the object merge map.
+  void
+  set_merge_map(Object_merge_map* object_merge_map)
+  {
+    gold_assert(this->object_merge_map_ == NULL);
+    this->object_merge_map_ = object_merge_map;
+  }
+
  protected:
   // What we need to know to map an input section to an output
   // section.  We keep an array of these, one for each input section,
@@ -533,6 +550,9 @@ class Relobj : public Object
  private:
   // Mapping from input sections to output section.
   std::vector<Map_to_output> map_to_output_;
+  // Mappings for merge sections.  This is managed by the code in the
+  // Merge_map class.
+  Object_merge_map* object_merge_map_;
   // Whether we need to wait for output sections to be written before
   // we can apply relocations.
   bool relocs_must_follow_section_writes_;