2009-10-09 Doug Kwan <dougkwan@google.com>

	* layout.cc (Layout::make_output_section): Call target hook to make
	ordinary output section.
	(Layout::finalize): Adjust parameter list of call the
	Target::may_relax().
	* layout.h (class Layout::section_list): New method.
	* merge.h (Output_merge_base::entsize): Change visibility to public.
	(Output_merge_base::is_string, Output_merge_base::do_is_string):
	New methods.
	(Output_merge_string::do_is_string): New method.
	* object.cc (Sized_relobj::do_setup): renamed from
	Sized_relobj::set_up.
	* object.h (Sized_relobj::adjust_shndx,
	Sized_relobj::initializ_input_to_output_maps,
	Sized_relobj::free_input_to_output_maps): Change visibilities to
	protected.
	(Sized_relobj::setup): Virtualize.
	(Sized_relobj::do_setup): New method declaration.
	(Sized_relobj::invalidate_section_offset,
	Sized_relobj::do_invalidate_section_offset): New method decfinitions.
	(Sized_relobj::elf_file, Sized_relobj::local_values): New methods.
	* options.cc (parse_int): New function.
	* options.h (parse_int): New declaration.
	(DEFINE_int): New macro.
	(stub_group_size): New option.
	* output.cc (Output_section::Output_section): Initialize memebers
	merge_section_map_, merge_section_by_properties_map_,
	relaxed_input_section_map_, is_relaxed_input_section_map_valid_.
	(Output_section::add_input_section): Handled deferred code-fill
	generation and remove an old comment.
	(Output_section::add_relaxed_input_section): New method definition.
	(Output_section::add_merge_input_section): Use merge section by
	properties map to speed to search.  Update merge section maps
	as appropriate.
	(Output_section::build_relaxation_map): New method definition.
	(Output_section::convert_input_sections_in_list_to_relaxed_sections):
	Same.
	(Output_section::relax_input_section): Renamed to
	Output_section::convert_input_sections_to_relaxed_sections and change
	interface to take a vector of pointers to relaxed sections.
	(Output_section::find_merge_section,
	Output_section::find_relaxed_input_section): New method definitions.
	(Output_section::is_input_address_mapped,
	Output_section::output_offset, Output_section::output_address):
	Use output section data maps to speed up searching.
	(Output_section::find_starting_output_address): Add comments.
	(Output_section::do_write,
	Output_section::write_to_postprocessing_buffer): Do code-fill
	generation as appropriate.
	(Output_section::get_input_sections): Invalidate relaxed input section
	map.
	(Output_section::restore_states): Adjust type of checkpoint .
	Invalidate relaxed input section map.
	* output.h (Output_merge_base): New class declaration.
	(Input_section_specifier): New class defintion.
	(class Output_relaxed_input_section) Change base class to
	Output_section_data_build.
	(Output_relaxed_input_section::Output_relaxed_input_section): Adjust
	base class initializer.
	(Output_section::add_relaxed_input_section): New method declaration.
	(Output_section::Input_section): Change visibility to protected.
     	(Output_section::Input_section::relobj,
	Output_section::Input_section::shndx): Handle relaxed input sections.
	Output_section::input_sections) Change visibility to protected.  Also
	define overload to return a non-const pointer.
	(Output_section::Merge_section_properties): New class defintion.
	(Output_section::Merge_section_by_properties_map,
	Output_section::Output_section_data_by_input_section_map,
	Output_section::Relaxation_map): New types.
	(Output_section::relax_input_section): Rename method to
	Output_section::convert_input_sections_to_relaxed_sections and change
	interface to take a vector of relaxed section pointers.
	(Output_section::find_merge_section,
	Output_section::find_relaxed_input_section,
	Output_section::build_relaxation_map,
	Output_section::convert_input_sections_in_list_to_relaxed_sections):
	New method declarations.
	(Output_section::merge_section_map_
	Output_section::merge_section_by_properties_map_,
	Output_section::relaxed_input_section_map_,
	Output_section::is_relaxed_input_section_map_valid_,
	Output_section::generate_code_fills_at_write_): New data members.
	* script-sections.cc
	(Output_section_element_input::set_section_addresses): Call
	current_data_size and addralign methods of relaxed input sections.
	(Orphan_output_section::set_section_addresses): Call current_data_size
	and addralign methods of relaxed input sections.
	* symtab.cc (Symbol_table::compute_final_value): Extract template
	from the body of Symbol_table::sized_finalize_symbol.
	(Symbol_table::sized_finalized_symbol): Call
	Symbol_table::compute_final_value.
	* symtab.h (Symbol_table::Compute_final_value_status): New enum type.
	(Symbol_table::compute_final_value): New templated method declaration.
	* target.cc (Target::do_make_output_section): New method defintion.
	* target.h (Target::make_output_section): New method declaration.
	(Target::relax): Add more parameters for input objects, symbol table
	and layout.  Adjust call to do_relax.
	(Target::do_make_output_section): New method declaration.
	(Target::do_relax): Add parameters for input objects, symbol table
	and layout.

1 files changed, 210 insertions, 15 deletions

diff --git a/gold/output.h b/gold/output.h
index 377864c..bc10950 100644
--- a/gold/output.h
+++ b/gold/output.h
@@ -38,6 +38,7 @@ class General_options;
 class Object;
 class Symbol;
 class Output_file;
+class Output_merge_base;
 class Output_section;
 class Relocatable_relocs;
 class Target;
@@ -46,6 +47,71 @@ class Sized_target;
 template<int size, bool big_endian>
 class Sized_relobj;
 
+// This class specifies an input section.  It is used as a key type
+// for maps.
+
+class Input_section_specifier
+{
+ public:
+  Input_section_specifier(const Relobj* relobj, unsigned int shndx)
+    : relobj_(relobj), shndx_(shndx)
+  { }
+   
+  // Return Relobj of this.
+  const Relobj*
+  relobj() const
+  { return this->relobj_; }
+
+  // Return section index of this.
+  unsigned int
+  shndx() const
+  { return this->shndx_; }
+
+  // Whether this equals to another specifier ISS.
+  bool
+  eq(const Input_section_specifier& iss) const
+  { return this->relobj_ == iss.relobj_ && this->shndx_ == iss.shndx_; }
+
+  // Compute a hash value of this.
+  size_t
+  hash_value() const
+  { return this->string_hash(this->relobj_->name().c_str()) ^ this->shndx_; }
+
+  // Functors for containers.
+  struct equal_to
+  {
+    bool
+    operator()(const Input_section_specifier& iss1,
+	       const Input_section_specifier& iss2) const
+    { return iss1.eq(iss2); }
+  };
+ 
+  struct hash
+  {
+    size_t
+    operator()(const Input_section_specifier& iss) const
+    { return iss.hash_value(); }
+  };
+
+ private:
+  // For portability, we use our own string hash function instead of assuming
+  // __gnu_cxx::hash or std::tr1::hash is available.  This is the same hash
+  // function used in Stringpool_template::string_hash.
+  static size_t
+  string_hash(const char* s)
+  {
+    size_t h = 5381;
+    while (*s != '\0')
+      h = h * 33 + *s++;
+    return h;
+  }
+
+  // An object.
+  const Relobj* relobj_;
+  // A section index. 
+  unsigned int shndx_;
+};
+
 // An abtract class for data which has to go into the output file.
 
 class Output_data
@@ -1987,7 +2053,7 @@ class Output_symtab_xindex : public Output_section_data
 };
 
 // A relaxed input section.
-class Output_relaxed_input_section : public Output_section_data
+class Output_relaxed_input_section : public Output_section_data_build
 {
  public:
   // We would like to call relobj->section_addralign(shndx) to get the
@@ -1995,7 +2061,7 @@ class Output_relaxed_input_section : public Output_section_data
   // are repsonsible for ensuring that.
   Output_relaxed_input_section(Relobj* relobj, unsigned int shndx,
 			       uint64_t addralign)
-    : Output_section_data(addralign), relobj_(relobj), shndx_(shndx)
+    : Output_section_data_build(addralign), relobj_(relobj), shndx_(shndx)
   { }
  
   // Return the Relobj of this relaxed input section.
@@ -2041,6 +2107,10 @@ class Output_section : public Output_data
   void
   add_output_section_data(Output_section_data* posd);
 
+  // Add a relaxed input section PORIS to this output section.
+  void
+  add_relaxed_input_section(Output_relaxed_input_section* poris);
+
   // Return the section name.
   const char*
   name() const
@@ -2510,6 +2580,11 @@ class Output_section : public Output_data
   void
   restore_states();
 
+  // Convert existing input sections to relaxed input sections.
+  void
+  convert_input_sections_to_relaxed_sections(
+      const std::vector<Output_relaxed_input_section*>& sections);
+
   // Print merge statistics to stderr.
   void
   print_merge_stats();
@@ -2625,7 +2700,6 @@ class Output_section : public Output_data
   void
   write_to_postprocessing_buffer();
 
- private:
   // In some cases we need to keep a list of the input sections
   // associated with this output section.  We only need the list if we
   // might have to change the offsets of the input section within the
@@ -2741,16 +2815,24 @@ class Output_section : public Output_data
     Relobj*
     relobj() const
     {
-      gold_assert(this->is_input_section());
-      return this->u2_.object;
+      if (this->is_input_section())
+        return this->u2_.object;
+      else if (this->is_relaxed_input_section())
+	return this->u2_.poris->relobj();
+      else
+	gold_unreachable();
     }
 
     // Return the input section index for an input section.
     unsigned int
     shndx() const
     {
-      gold_assert(this->is_input_section());
-      return this->shndx_;
+      if (this->is_input_section())
+        return this->shndx_;
+      else if (this->is_relaxed_input_section())
+	return this->u2_.poris->shndx();
+      else
+	gold_unreachable();
     }
 
     // For non-input-sections, return the associated Output_section_data
@@ -2891,6 +2973,12 @@ class Output_section : public Output_data
 
   typedef std::vector<Input_section> Input_section_list;
 
+  // Allow a child class to access the input sections.
+  const Input_section_list&
+  input_sections() const
+  { return this->input_sections_; }
+
+ private:
   // We only save enough information to undo the effects of section layout.
   class Checkpoint_output_section
   {
@@ -2921,9 +3009,9 @@ class Output_section : public Output_data
     { return this->flags_; }
 
     // Return a reference to the input section list copy.
-    const Input_section_list&
-    input_sections() const
-    { return this->input_sections_copy_; }
+    Input_section_list*
+    input_sections()
+    { return &this->input_sections_copy_; }
 
     // Return the size of input_sections at the time when checkpoint is
     // taken.
@@ -2974,7 +3062,6 @@ class Output_section : public Output_data
     bool attached_input_sections_are_sorted_;
   };
 
- private:
   // This class is used to sort the input sections.
   class Input_section_sort_entry;
 
@@ -3018,6 +3105,82 @@ class Output_section : public Output_data
 
   typedef std::vector<Fill> Fill_list;
 
+  // This class describes properties of merge data sections.  It is used
+  // as a key type for maps.
+  class Merge_section_properties
+  {
+   public:
+    Merge_section_properties(bool is_string, uint64_t entsize,
+			     uint64_t addralign)
+      : is_string_(is_string), entsize_(entsize), addralign_(addralign)
+    { }
+
+    // Whether this equals to another Merge_section_properties MSP.
+    bool
+    eq(const Merge_section_properties& msp) const
+    {
+      return ((this->is_string_ == msp.is_string_)
+	      && (this->entsize_ == msp.entsize_)
+	      && (this->addralign_ == msp.addralign_));
+    }
+
+    // Compute a hash value for this using 64-bit FNV-1a hash.
+    size_t
+    hash_value() const
+    {
+      uint64_t h = 14695981039346656037ULL;	// FNV offset basis.
+      uint64_t prime = 1099511628211ULL;
+      h = (h ^ static_cast<uint64_t>(this->is_string_)) * prime;
+      h = (h ^ static_cast<uint64_t>(this->entsize_)) * prime;
+      h = (h ^ static_cast<uint64_t>(this->addralign_)) * prime;
+      return h;
+    }
+    
+    // Functors for associative containers.
+    struct equal_to
+    {
+      bool
+      operator()(const Merge_section_properties& msp1,
+		 const Merge_section_properties& msp2) const
+      { return msp1.eq(msp2); }
+    };
+
+    struct hash
+    {
+      size_t
+      operator()(const Merge_section_properties& msp) const
+      { return msp.hash_value(); }
+    };
+
+   private:
+    // Whether this merge data section is for strings.
+    bool is_string_;
+    // Entsize of this merge data section.
+    uint64_t entsize_;
+    // Address alignment.
+    uint64_t addralign_;
+  };
+
+  // Map that link Merge_section_properties to Output_merge_base.
+  typedef Unordered_map<Merge_section_properties, Output_merge_base*,
+			Merge_section_properties::hash,
+			Merge_section_properties::equal_to>
+    Merge_section_by_properties_map;
+
+  // Map that link Input_section_specifier to Output_section_data.
+  typedef Unordered_map<Input_section_specifier, Output_section_data*,
+			Input_section_specifier::hash,
+			Input_section_specifier::equal_to>
+    Output_section_data_by_input_section_map;
+
+  // Map used during relaxation of existing sections.  This map
+  // an input section specifier to an input section list index.
+  // We assume that Input_section_list is a vector.
+  typedef Unordered_map<Input_section_specifier, size_t,
+			Input_section_specifier::hash,
+			Input_section_specifier::equal_to>
+    Relaxation_map;
+
   // Add a new output section by Input_section.
   void
   add_output_section_data(Input_section*);
@@ -3036,14 +3199,34 @@ class Output_section : public Output_data
   add_output_merge_section(Output_section_data* posd, bool is_string,
 			   uint64_t entsize);
 
-  // Relax an existing input section.
-  void
-  relax_input_section(Output_relaxed_input_section*);
-
   // Sort the attached input sections.
   void
   sort_attached_input_sections();
 
+  // Find the merge section into which an input section with index SHNDX in
+  // OBJECT has been added.  Return NULL if none found.
+  Output_section_data*
+  find_merge_section(const Relobj* object, unsigned int shndx) const;
+
+  // Find a relaxed input section to an input section in OBJECT
+  // with index SHNDX.  Return NULL if none is found.
+  const Output_section_data*
+  find_relaxed_input_section(const Relobj* object, unsigned int shndx) const;
+  
+  // Build a relaxation map.
+  void
+  build_relaxation_map(
+      const Input_section_list& input_sections,
+      size_t limit,
+      Relaxation_map* map) const;
+
+  // Convert input sections in an input section list into relaxed sections.
+  void
+  convert_input_sections_in_list_to_relaxed_sections(
+      const std::vector<Output_relaxed_input_section*>& relaxed_sections,
+      const Relaxation_map& map,
+      Input_section_list* input_sections);
+
   // Most of these fields are only valid after layout.
 
   // The name of the section.  This will point into a Stringpool.
@@ -3149,6 +3332,18 @@ class Output_section : public Output_data
   uint64_t tls_offset_;
   // Saved checkpoint.
   Checkpoint_output_section* checkpoint_;
+  // Map from input sections to merge sections.
+  Output_section_data_by_input_section_map merge_section_map_;
+  // Map from merge section properties to merge_sections;
+  Merge_section_by_properties_map merge_section_by_properties_map_;
+  // Map from input sections to relaxed input sections.  This is mutable
+  // beacause it is udpated lazily.  We may need to update it in a
+  // const qualified method.
+  mutable Output_section_data_by_input_section_map relaxed_input_section_map_;
+  // Whether relaxed_input_section_map_ is valid.
+  mutable bool is_relaxed_input_section_map_valid_;
+  // Whether code-fills are generated at write.
+  bool generate_code_fills_at_write_;
 };
 
 // An output segment.  PT_LOAD segments are built from collections of