[PATCH v2 4/4] gold: Fix non-deterministic behaviour of Mips gold.

[Vladimir Radosavljevic <Vladimir dot Radosavljevic at imgtec dot com>]

Nothing is changed. Patch is in attachment.

Regards,
Vladimir.

Changelog -
    * mips.cc (Mips_got_entry::hash): Delete.
    (class Mips_got_entry_hash): Likewise.
    (struct Got_page_entry_hash): Likewise.
    (Mips_got_entry::equals): Change to compare_less.
    (class Mips_got_entry_eq): Change to Mips_got_entry_compare_less.
    (struct Got_page_entry_eq): Change to Got_page_entry_compare_less.
    (Got_entry_set): Change from Unordered_set to std::set.
    (Got_page_entry_set): Likewise.
    (global_got_symbols_): Likewise.
    (Mips_output_data_mips_stubs::symbols_): Likewise.
    (Mips_output_data_la25_stub::symbols_): Likewise.
    (Mips_got_info::record_got_entry): Don't use find before insert.
    (Mips_got_info::record_got_page_entry): Likewise.

diff --git a/gold/mips.cc b/gold/mips.cc
index 051d49a..934ae6d 100644
--- a/gold/mips.cc
+++ b/gold/mips.cc
@@ -420,38 +420,24 @@ class Mips_got_entry
   is_for_global_symbol() const
   { return this->symndx_ == -1U; }
 
-  // Return the hash of this entry.
-  size_t
-  hash() const
-  {
-    if (this->tls_type_ == GOT_TLS_LDM)
-      return this->symndx_ + (1 << 18);
-    if (this->symndx_ != -1U)
-      {
-        uintptr_t object_id = reinterpret_cast<uintptr_t>(this->object());
-        return this->symndx_ + object_id + this->d.addend;
-      }
-    else
-      {
-        uintptr_t sym_id = reinterpret_cast<uintptr_t>(this->d.sym);
-        return this->symndx_ + sym_id;
-      }
-  }
-
-  // Return whether this entry is equal to OTHER.
   bool
-  equals(Mips_got_entry<size, big_endian>* other) const
+  compare_less(Mips_got_entry<size, big_endian>* other) const
   {
-    if (this->symndx_ != other->symndx_
-        || this->tls_type_ != other->tls_type_)
-      return false;
+    if (this->symndx_ != other->symndx_)
+      return this->symndx_ < other->symndx_;
+    if (this->tls_type_ != other->tls_type_)
+      return this->tls_type_ < other->tls_type_;
     if (this->tls_type_ == GOT_TLS_LDM)
-      return true;
+      return false;
+
     if (this->symndx_ != -1U)
-      return (this->object() == other->object()
-              && this->d.addend == other->d.addend);
-    else
-      return this->d.sym == other->d.sym;
+    {
+      if (this->object() != other->object())
+        return this->object() < other->object();
+
+      return this->d.addend < other->d.addend;
+    }
+    return this->d.sym < other->d.sym;
   }
 
   // Return input object that needs this GOT entry.
@@ -526,27 +512,16 @@ class Mips_got_entry
   unsigned int shndx_;
 };
 
-// Hash for Mips_got_entry.
-
-template<int size, bool big_endian>
-class Mips_got_entry_hash
-{
- public:
-  size_t
-  operator()(Mips_got_entry<size, big_endian>* entry) const
-  { return entry->hash(); }
-};
-
 // Equality for Mips_got_entry.
 
 template<int size, bool big_endian>
-class Mips_got_entry_eq
+class Mips_got_entry_compare_less
 {
  public:
   bool
   operator()(Mips_got_entry<size, big_endian>* e1,
              Mips_got_entry<size, big_endian>* e2) const
-  { return e1->equals(e2); }
+  { return e1->compare_less(e2); }
 };
 
 // Got_page_range.  This class describes a range of addends: [MIN_ADDEND,
@@ -592,23 +567,17 @@ struct Got_page_entry
   unsigned int num_pages;
 };
 
-// Hash for Got_page_entry.
+// Compare less for Got_page_entry.
 
-struct Got_page_entry_hash
-{
-  size_t
-  operator()(Got_page_entry* entry) const
-  { return reinterpret_cast<uintptr_t>(entry->object) + entry->symndx; }
-};
-
-// Equality for Got_page_entry.
-
-struct Got_page_entry_eq
+struct Got_page_entry_compare_less
 {
   bool
   operator()(Got_page_entry* entry1, Got_page_entry* entry2) const
   {
-    return entry1->object == entry2->object && entry1->symndx == entry2->symndx;
+    if (entry1->object != entry2->object)
+      return entry1->object < entry2->object;
+
+    return entry1->symndx < entry2->symndx;
   }
 };
 
@@ -622,14 +591,13 @@ class Mips_got_info
     Reloc_section;
   typedef Unordered_map<unsigned int, unsigned int> Got_page_offsets;
 
-  // Unordered set of GOT entries.
-  typedef Unordered_set<Mips_got_entry<size, big_endian>*,
-      Mips_got_entry_hash<size, big_endian>,
-      Mips_got_entry_eq<size, big_endian> > Got_entry_set;
+  // Ordered set of GOT entries.
+  typedef std::set<Mips_got_entry<size, big_endian>*,
+      Mips_got_entry_compare_less<size, big_endian> > Got_entry_set;
 
-  // Unordered set of GOT page entries.
-  typedef Unordered_set<Got_page_entry*,
-      Got_page_entry_hash, Got_page_entry_eq> Got_page_entry_set;
+  // Ordered set of GOT page entries.
+  typedef std::set<Got_page_entry*,
+      Got_page_entry_compare_less> Got_page_entry_set;
 
  public:
   Mips_got_info()
@@ -809,7 +777,7 @@ class Mips_got_info
   set_tls_ldm_offset(unsigned int tls_ldm_offset)
   { this->tls_ldm_offset_ = tls_ldm_offset; }
 
-  Unordered_set<Mips_symbol<size>*>&
+  std::set<Mips_symbol<size>*>&
   global_got_symbols()
   { return this->global_got_symbols_; }
 
@@ -864,10 +832,10 @@ class Mips_got_info
   // The offset of TLS LDM entry for this GOT.
   unsigned int tls_ldm_offset_;
   // All symbols that have global GOT entry.
-  Unordered_set<Mips_symbol<size>*> global_got_symbols_;
-  // A hash table holding GOT entries.
+  std::set<Mips_symbol<size>*> global_got_symbols_;
+  // A set holding GOT entries.
   Got_entry_set got_entries_;
-  // A hash table of GOT page entries.
+  // A set of GOT page entries.
   Got_page_entry_set got_page_entries_;
   // The offset of first GOT page entry for this GOT.
   unsigned int got_page_offset_start_;
@@ -2251,7 +2219,7 @@ class Mips_output_data_la25_stub : public Output_section_data
   do_write(Output_file*);
 
   // Symbols that have LA25 stubs.
-  Unordered_set<Mips_symbol<size>*> symbols_;
+  std::set<Mips_symbol<size>*> symbols_;
 };
 
 // A class to handle the PLT data.
@@ -2573,7 +2541,7 @@ class Mips_output_data_mips_stubs : public Output_section_data
   do_write(Output_file*);
 
   // .MIPS.stubs symbols
-  Unordered_set<Mips_symbol<size>*> symbols_;
+  std::set<Mips_symbol<size>*> symbols_;
   // Number of entries in dynamic symbol table.
   unsigned int dynsym_count_;
   // Whether the stub offsets are set.
@@ -4812,16 +4780,12 @@ Mips_got_info<size, big_endian>::record_got_entry(
     Mips_got_entry<size, big_endian>* entry,
     Mips_relobj<size, big_endian>* object)
 {
-  if (this->got_entries_.find(entry) == this->got_entries_.end())
-    this->got_entries_.insert(entry);
+  this->got_entries_.insert(entry);
 
   // Create the GOT entry for the OBJECT's GOT.
   Mips_got_info<size, big_endian>* g = object->get_or_create_got_info();
-  Mips_got_entry<size, big_endian>* entry2 =
-    new Mips_got_entry<size, big_endian>(*entry);
 
-  if (g->got_entries_.find(entry2) == g->got_entries_.end())
-    g->got_entries_.insert(entry2);
+  g->got_entries_.insert(entry);
 }
 
 // Record that OBJECT has a page relocation against symbol SYMNDX and
@@ -4840,13 +4804,12 @@ Mips_got_info<size, big_endian>::record_got_page_entry(
 
   // Find the Got_page_entry for this symbol.
   Got_page_entry* entry = new Got_page_entry(object, symndx);
-  typename Got_page_entry_set::iterator it =
-    this->got_page_entries_.find(entry);
-  if (it != this->got_page_entries_.end())
-    entry = *it;
-  else
+  std::pair<Got_page_entry_set::iterator, bool> new_entry =
     this->got_page_entries_.insert(entry);
 
+  if (!new_entry.second)
+    entry = *new_entry.first;
+
   // Add the same entry to the OBJECT's GOT.
   Got_page_entry* entry2 = NULL;
   Mips_got_info<size, big_endian>* g2 = object->get_or_create_got_info();
@@ -5088,7 +5051,7 @@ void
 Mips_got_info<size, big_endian>::add_reloc_only_entries(
     Mips_output_data_got<size, big_endian>* got)
 {
-  for (typename Unordered_set<Mips_symbol<size>*>::iterator
+  for (typename std::set<Mips_symbol<size>*>::iterator
        p = this->global_got_symbols_.begin();
        p != this->global_got_symbols_.end();
        ++p)
@@ -5267,7 +5230,7 @@ template<int size, bool big_endian>
 void
 Mips_got_info<size, big_endian>::count_got_symbols(Symbol_table* symtab)
 {
-  for (typename Unordered_set<Mips_symbol<size>*>::iterator
+  for (typename std::set<Mips_symbol<size>*>::iterator
        p = this->global_got_symbols_.begin();
        p != this->global_got_symbols_.end();
        ++p)
@@ -5636,7 +5599,7 @@ Mips_output_data_got<size, big_endian>::do_write(Output_file* of)
   this->got_view_ = oview;
 
   // Write lazy stub addresses.
-  for (typename Unordered_set<Mips_symbol<size>*>::iterator
+  for (typename std::set<Mips_symbol<size>*>::iterator
        p = this->master_got_info_->global_got_symbols().begin();
        p != this->master_got_info_->global_got_symbols().end();
        ++p)
@@ -5653,7 +5616,7 @@ Mips_output_data_got<size, big_endian>::do_write(Output_file* of)
     }
 
   // Add +1 to GGA_NONE nonzero MIPS16 and microMIPS entries.
-  for (typename Unordered_set<Mips_symbol<size>*>::iterator
+  for (typename std::set<Mips_symbol<size>*>::iterator
        p = this->master_got_info_->global_got_symbols().begin();
        p != this->master_got_info_->global_got_symbols().end();
        ++p)
@@ -6106,7 +6069,7 @@ Mips_output_data_la25_stub<size, big_endian>::do_write(Output_file* of)
     convert_to_section_size_type(this->data_size());
   unsigned char* const oview = of->get_output_view(offset, oview_size);
 
-  for (typename Unordered_set<Mips_symbol<size>*>::iterator
+  for (typename std::set<Mips_symbol<size>*>::iterator
        p = this->symbols_.begin();
        p != this->symbols_.end();
        ++p)
@@ -6905,7 +6868,7 @@ Mips_output_data_mips_stubs<size, big_endian>::set_lazy_stub_offsets()
 
   unsigned int stub_size = this->stub_size();
   unsigned int offset = 0;
-  for (typename Unordered_set<Mips_symbol<size>*>::const_iterator
+  for (typename std::set<Mips_symbol<size>*>::const_iterator
        p = this->symbols_.begin();
        p != this->symbols_.end();
        ++p, offset += stub_size)
@@ -6920,7 +6883,7 @@ template<int size, bool big_endian>
 void
 Mips_output_data_mips_stubs<size, big_endian>::set_needs_dynsym_value()
 {
-  for (typename Unordered_set<Mips_symbol<size>*>::const_iterator
+  for (typename std::set<Mips_symbol<size>*>::const_iterator
        p = this->symbols_.begin(); p != this->symbols_.end(); ++p)
     {
       Mips_symbol<size>* sym = *p;
@@ -6944,7 +6907,7 @@ Mips_output_data_mips_stubs<size, big_endian>::do_write(Output_file* of)
   bool big_stub = this->dynsym_count_ > 0x10000;
 
   unsigned char* pov = oview;
-  for (typename Unordered_set<Mips_symbol<size>*>::const_iterator
+  for (typename std::set<Mips_symbol<size>*>::const_iterator
        p = this->symbols_.begin(); p != this->symbols_.end(); ++p)
     {
       Mips_symbol<size>* sym = *p;