2008-05-05 Ian Lance Taylor <iant@google.com>

	* options.h (DEFINE_bool): For DASH_Z, create the negative option
	as noVARNAME rather than no-VARNAME.
	(class General_options): Add option -z combreloc.
	* output.h (class Output_reloc) [SHT_REL]: Declare compare and
	get_address.
	(Output_reloc::sort_before) [SHT_REL]: New function.
	(Output_reloc::sort_before) [SHT_RELA]: New function.
	(class Output_data_reloc_base): Add sort_relocs_ field.  Define
	Sort_relocs_comparison.
	(Output_data_reloc_base::Output_data_reloc_base): Add sort_relocs
	parameter.  Change all callers.
	(Output_data_reloc::Output_data_reloc) [both versions]: Add
	sort_relocs parameter.  Change all callers.
	* output.cc (Output_reloc::get_address): New function, broken out
	of write_rel.
	(Output_reloc::write_rel): Call it.
	(Output_reloc::compare): New function.
	(Output_data_reloc_base::do_write): Optionally sort relocs.

7 files changed, 159 insertions, 23 deletions

diff --git a/gold/ChangeLog b/gold/ChangeLog
index 1d9f9d91961..3ae464f53b0 100644
--- a/gold/ChangeLog
+++ b/gold/ChangeLog
@@ -1,5 +1,24 @@
 2008-05-05  Ian Lance Taylor  <iant@google.com>
 
+	* options.h (DEFINE_bool): For DASH_Z, create the negative option
+	as noVARNAME rather than no-VARNAME.
+	(class General_options): Add option -z combreloc.
+	* output.h (class Output_reloc) [SHT_REL]: Declare compare and
+	get_address.
+	(Output_reloc::sort_before) [SHT_REL]: New function.
+	(Output_reloc::sort_before) [SHT_RELA]: New function.
+	(class Output_data_reloc_base): Add sort_relocs_ field.  Define
+	Sort_relocs_comparison.
+	(Output_data_reloc_base::Output_data_reloc_base): Add sort_relocs
+	parameter.  Change all callers.
+	(Output_data_reloc::Output_data_reloc) [both versions]: Add
+	sort_relocs parameter.  Change all callers.
+	* output.cc (Output_reloc::get_address): New function, broken out
+	of write_rel.
+	(Output_reloc::write_rel): Call it.
+	(Output_reloc::compare): New function.
+	(Output_data_reloc_base::do_write): Optionally sort relocs.
+
 	* configure.ac: If targ_extra_obj is set, link it in.
 	* configure.tgt: Initialize all variables.
 	(x86_64*): Set targ_extra_obj and targ_extra_size.
diff --git a/gold/i386.cc b/gold/i386.cc
index 6fb096ea9cd..9f86229eb0a 100644
--- a/gold/i386.cc
+++ b/gold/i386.cc
@@ -462,7 +462,7 @@ Target_i386::rel_dyn_section(Layout* layout)
   if (this->rel_dyn_ == NULL)
     {
       gold_assert(layout != NULL);
-      this->rel_dyn_ = new Reloc_section();
+      this->rel_dyn_ = new Reloc_section(parameters->options().combreloc());
       layout->add_output_section_data(".rel.dyn", elfcpp::SHT_REL,
 				      elfcpp::SHF_ALLOC, this->rel_dyn_);
     }
@@ -532,7 +532,7 @@ Output_data_plt_i386::Output_data_plt_i386(Layout* layout,
 					   Output_data_space* got_plt)
   : Output_section_data(4), got_plt_(got_plt), count_(0)
 {
-  this->rel_ = new Reloc_section();
+  this->rel_ = new Reloc_section(false);
   layout->add_output_section_data(".rel.plt", elfcpp::SHT_REL,
 				  elfcpp::SHF_ALLOC, this->rel_);
 }
diff --git a/gold/options.h b/gold/options.h
index 419e70bb4e1..0dd822104d4 100644
--- a/gold/options.h
+++ b/gold/options.h
@@ -268,7 +268,8 @@ struct Struct_special : public Struct_var
 // These macros allow for easy addition of a new commandline option.
 
 // If no_helpstring__ is not NULL, then in addition to creating
-// VARNAME, we also create an option called no-VARNAME.
+// VARNAME, we also create an option called no-VARNAME (or, for a -z
+// option, noVARNAME).
 #define DEFINE_bool(varname__, dashes__, shortname__, default_value__,   \
                     helpstring__, no_helpstring__)                       \
   DEFINE_var(varname__, dashes__, shortname__, default_value__,          \
@@ -276,7 +277,10 @@ struct Struct_special : public Struct_var
              false, bool, bool, options::parse_bool)			 \
   struct Struct_no_##varname__ : public options::Struct_var              \
   {                                                                      \
-    Struct_no_##varname__() : option("no-" #varname__, dashes__, '\0',   \
+    Struct_no_##varname__() : option((dashes__ == options::DASH_Z	 \
+				      ? "no" #varname__			 \
+				      : "no-" #varname__),		 \
+				     dashes__, '\0',			 \
                                      default_value__ ? "false" : "true", \
                                      no_helpstring__, NULL, false, this) \
     { }                                                                  \
@@ -699,8 +703,9 @@ class General_options
 
   // The -z options.
 
-  // Both execstack and noexecstack differ from the default execstack_
-  // value, so we need to use different variables for them.
+  DEFINE_bool(combreloc, options::DASH_Z, '\0', true,
+	      N_("Sort dynamic relocs"),
+	      N_("Do not sort dynamic relocs"));
   DEFINE_uint64(common_page_size, options::DASH_Z, '\0', 0,
                 N_("Set common page size to SIZE"), N_("SIZE"));
   DEFINE_bool(defs, options::DASH_Z, '\0', false,
diff --git a/gold/output.cc b/gold/output.cc
index a3c1f856902..12858964850 100644
--- a/gold/output.cc
+++ b/gold/output.cc
@@ -851,14 +851,11 @@ Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::
   return offset;
 }
 
-// Write out the offset and info fields of a Rel or Rela relocation
-// entry.
+// Get the output address of a relocation.
 
 template<bool dynamic, int size, bool big_endian>
-template<typename Write_rel>
-void
-Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::write_rel(
-    Write_rel* wr) const
+section_offset_type
+Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::get_address() const
 {
   Address address = this->address_;
   if (this->shndx_ != INVALID_CODE)
@@ -878,7 +875,19 @@ Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::write_rel(
     }
   else if (this->u2_.od != NULL)
     address += this->u2_.od->address();
-  wr->put_r_offset(address);
+  return address;
+}
+
+// Write out the offset and info fields of a Rel or Rela relocation
+// entry.
+
+template<bool dynamic, int size, bool big_endian>
+template<typename Write_rel>
+void
+Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::write_rel(
+    Write_rel* wr) const
+{
+  wr->put_r_offset(this->get_address());
   unsigned int sym_index = this->is_relative_ ? 0 : this->get_symbol_index();
   wr->put_r_info(elfcpp::elf_r_info<size>(sym_index, this->type_));
 }
@@ -915,6 +924,57 @@ Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::symbol_value(
   return symval->value(this->u1_.relobj, addend);
 }
 
+// Reloc comparison.  This function sorts the dynamic relocs for the
+// benefit of the dynamic linker.  First we sort all relative relocs
+// to the front.  Among relative relocs, we sort by output address.
+// Among non-relative relocs, we sort by symbol index, then by output
+// address.
+
+template<bool dynamic, int size, bool big_endian>
+int
+Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>::
+  compare(const Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>& r2)
+    const
+{
+  if (this->is_relative_)
+    {
+      if (!r2.is_relative_)
+	return -1;
+      // Otherwise sort by reloc address below.
+    }
+  else if (r2.is_relative_)
+    return 1;
+  else
+    {
+      unsigned int sym1 = this->get_symbol_index();
+      unsigned int sym2 = r2.get_symbol_index();
+      if (sym1 < sym2)
+	return -1;
+      else if (sym1 > sym2)
+	return 1;
+      // Otherwise sort by reloc address.
+    }
+
+  section_offset_type addr1 = this->get_address();
+  section_offset_type addr2 = r2.get_address();
+  if (addr1 < addr2)
+    return -1;
+  else if (addr1 > addr2)
+    return 1;
+
+  // Final tie breaker, in order to generate the same output on any
+  // host: reloc type.
+  unsigned int type1 = this->type_;
+  unsigned int type2 = r2.type_;
+  if (type1 < type2)
+    return -1;
+  else if (type1 > type2)
+    return 1;
+
+  // These relocs appear to be exactly the same.
+  return 0;
+}
+
 // Write out a Rela relocation.
 
 template<bool dynamic, int size, bool big_endian>
@@ -964,6 +1024,13 @@ Output_data_reloc_base<sh_type, dynamic, size, big_endian>::do_write(
   const off_t oview_size = this->data_size();
   unsigned char* const oview = of->get_output_view(off, oview_size);
 
+  if (this->sort_relocs_)
+    {
+      gold_assert(dynamic);
+      std::sort(this->relocs_.begin(), this->relocs_.end(),
+		Sort_relocs_comparison());
+    }
+
   unsigned char* pov = oview;
   for (typename Relocs::const_iterator p = this->relocs_.begin();
        p != this->relocs_.end();
diff --git a/gold/output.h b/gold/output.h
index 9d6577e376e..89c6eeb4487 100644
--- a/gold/output.h
+++ b/gold/output.h
@@ -855,6 +855,19 @@ class Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>
   template<typename Write_rel>
   void write_rel(Write_rel*) const;
 
+  // This is used when sorting dynamic relocs.  Return -1 to sort this
+  // reloc before R2, 0 to sort the same as R2, 1 to sort after R2.
+  int
+  compare(const Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>& r2)
+    const;
+
+  // Return whether this reloc should be sorted before the argument
+  // when sorting dynamic relocs.
+  bool
+  sort_before(const Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>&
+	      r2) const
+  { return this->compare(r2) < 0; }
+
  private:
   // Record that we need a dynamic symbol index.
   void
@@ -864,6 +877,10 @@ class Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>
   unsigned int
   get_symbol_index() const;
 
+  // Return the output address.
+  section_offset_type
+  get_address() const;
+
   // Codes for local_sym_index_.
   enum
   {
@@ -986,6 +1003,21 @@ class Output_reloc<elfcpp::SHT_RELA, dynamic, size, big_endian>
   void
   write(unsigned char* pov) const;
 
+  // Return whether this reloc should be sorted before the argument
+  // when sorting dynamic relocs.
+  bool
+  sort_before(const Output_reloc<elfcpp::SHT_RELA, dynamic, size, big_endian>&
+	      r2) const
+  {
+    int i = this->rel_.compare(r2.rel_);
+    if (i < 0)
+      return false;
+    else if (i > 0)
+      return true;
+    else
+      return this->addend_ < r2.addend_;
+  }
+
  private:
   // The basic reloc.
   Output_reloc<elfcpp::SHT_REL, dynamic, size, big_endian> rel_;
@@ -1010,8 +1042,9 @@ class Output_data_reloc_base : public Output_section_data_build
     Reloc_types<sh_type, size, big_endian>::reloc_size;
 
   // Construct the section.
-  Output_data_reloc_base()
-    : Output_section_data_build(Output_data::default_alignment_for_size(size))
+  Output_data_reloc_base(bool sort_relocs)
+    : Output_section_data_build(Output_data::default_alignment_for_size(size)),
+      sort_relocs_(sort_relocs)
   { }
 
  protected:
@@ -1035,7 +1068,19 @@ class Output_data_reloc_base : public Output_section_data_build
  private:
   typedef std::vector<Output_reloc_type> Relocs;
 
+  // The class used to sort the relocations.
+  struct Sort_relocs_comparison
+  {
+    bool
+    operator()(const Output_reloc_type& r1, const Output_reloc_type& r2) const
+    { return r1.sort_before(r2); }
+  };
+
+  // The relocations in this section.
   Relocs relocs_;
+  // Whether to sort the relocations when writing them out, to make
+  // the dynamic linker more efficient.
+  bool sort_relocs_;
 };
 
 // The class which callers actually create.
@@ -1057,8 +1102,8 @@ class Output_data_reloc<elfcpp::SHT_REL, dynamic, size, big_endian>
   typedef typename Base::Output_reloc_type Output_reloc_type;
   typedef typename Output_reloc_type::Address Address;
 
-  Output_data_reloc()
-    : Output_data_reloc_base<elfcpp::SHT_REL, dynamic, size, big_endian>()
+  Output_data_reloc(bool sr)
+    : Output_data_reloc_base<elfcpp::SHT_REL, dynamic, size, big_endian>(sr)
   { }
 
   // Add a reloc against a global symbol.
@@ -1199,8 +1244,8 @@ class Output_data_reloc<elfcpp::SHT_RELA, dynamic, size, big_endian>
   typedef typename Output_reloc_type::Address Address;
   typedef typename Output_reloc_type::Addend Addend;
 
-  Output_data_reloc()
-    : Output_data_reloc_base<elfcpp::SHT_RELA, dynamic, size, big_endian>()
+  Output_data_reloc(bool sr)
+    : Output_data_reloc_base<elfcpp::SHT_RELA, dynamic, size, big_endian>(sr)
   { }
 
   // Add a reloc against a global symbol.
diff --git a/gold/sparc.cc b/gold/sparc.cc
index 60e85241d71..0472fa14c9f 100644
--- a/gold/sparc.cc
+++ b/gold/sparc.cc
@@ -1026,7 +1026,7 @@ Target_sparc<size, big_endian>::rela_dyn_section(Layout* layout)
   if (this->rela_dyn_ == NULL)
     {
       gold_assert(layout != NULL);
-      this->rela_dyn_ = new Reloc_section();
+      this->rela_dyn_ = new Reloc_section(parameters->options().combreloc());
       layout->add_output_section_data(".rela.dyn", elfcpp::SHT_RELA,
 				      elfcpp::SHF_ALLOC, this->rela_dyn_);
     }
@@ -1123,7 +1123,7 @@ template<int size, bool big_endian>
 Output_data_plt_sparc<size, big_endian>::Output_data_plt_sparc(Layout* layout)
   : Output_section_data(size == 32 ? 4 : 8), count_(0)
 {
-  this->rel_ = new Reloc_section();
+  this->rel_ = new Reloc_section(false);
   layout->add_output_section_data(".rela.plt", elfcpp::SHT_RELA,
 				  elfcpp::SHF_ALLOC, this->rel_);
 }
diff --git a/gold/x86_64.cc b/gold/x86_64.cc
index 927ed39be0f..6459e500827 100644
--- a/gold/x86_64.cc
+++ b/gold/x86_64.cc
@@ -465,7 +465,7 @@ Target_x86_64::rela_dyn_section(Layout* layout)
   if (this->rela_dyn_ == NULL)
     {
       gold_assert(layout != NULL);
-      this->rela_dyn_ = new Reloc_section();
+      this->rela_dyn_ = new Reloc_section(parameters->options().combreloc());
       layout->add_output_section_data(".rela.dyn", elfcpp::SHT_RELA,
 				      elfcpp::SHF_ALLOC, this->rela_dyn_);
     }
@@ -560,7 +560,7 @@ Output_data_plt_x86_64::Output_data_plt_x86_64(Layout* layout,
   : Output_section_data(8), got_(got), got_plt_(got_plt), count_(0),
     tlsdesc_got_offset_(-1U)
 {
-  this->rel_ = new Reloc_section();
+  this->rel_ = new Reloc_section(false);
   layout->add_output_section_data(".rela.plt", elfcpp::SHT_RELA,
 				  elfcpp::SHF_ALLOC, this->rel_);
 }