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, 296 insertions, 45 deletions

diff --git a/gold/output.cc b/gold/output.cc
index e3b1171..7d869b3 100644
--- a/gold/output.cc
+++ b/gold/output.cc
@@ -1801,7 +1801,12 @@ Output_section::Output_section(const char* name, elfcpp::Elf_Word type,
     is_small_section_(false),
     is_large_section_(false),
     tls_offset_(0),
-    checkpoint_(NULL)
+    checkpoint_(NULL),
+    merge_section_map_(),
+    merge_section_by_properties_map_(),
+    relaxed_input_section_map_(),
+    is_relaxed_input_section_map_valid_(true),
+    generate_code_fills_at_write_(false)
 {
   // An unallocated section has no address.  Forcing this means that
   // we don't need special treatment for symbols defined in debug
@@ -1892,7 +1897,21 @@ Output_section::add_input_section(Sized_relobj<size, big_endian>* object,
   off_t aligned_offset_in_section = align_address(offset_in_section,
                                                   addralign);
 
+  // Determine if we want to delay code-fill generation until the output
+  // section is written.  When the target is relaxing, we want to delay fill
+  // generating to avoid adjusting them during relaxation.
+  if (!this->generate_code_fills_at_write_
+      && !have_sections_script
+      && (sh_flags & elfcpp::SHF_EXECINSTR) != 0
+      && parameters->target().has_code_fill()
+      && parameters->target().may_relax())
+    {
+      gold_assert(this->fills_.empty());
+      this->generate_code_fills_at_write_ = true;
+    }
+
   if (aligned_offset_in_section > offset_in_section
+      && !this->generate_code_fills_at_write_
       && !have_sections_script
       && (sh_flags & elfcpp::SHF_EXECINSTR) != 0
       && parameters->target().has_code_fill())
@@ -1905,8 +1924,6 @@ Output_section::add_input_section(Sized_relobj<size, big_endian>* object,
         this->fills_.push_back(Fill(offset_in_section, fill_len));
       else
         {
-          // FIXME: When relaxing, the size needs to adjust to
-          // maintain a constant alignment.
           std::string fill_data(parameters->target().code_fill(fill_len));
           Output_data_const* odc = new Output_data_const(fill_data, 1);
           this->input_sections_.push_back(Input_section(odc));
@@ -1951,6 +1968,31 @@ Output_section::add_output_section_data(Output_section_data* posd)
     }
 }
 
+// Add a relaxed input section.
+
+void
+Output_section::add_relaxed_input_section(Output_relaxed_input_section* poris)
+{
+  Input_section inp(poris);
+  this->add_output_section_data(&inp);
+  if (this->is_relaxed_input_section_map_valid_)
+    {
+      Input_section_specifier iss(poris->relobj(), poris->shndx());
+      this->relaxed_input_section_map_[iss] = poris;
+    }
+
+  // For a relaxed section, we use the current data size.  Linker scripts
+  // get all the input sections, including relaxed one from an output
+  // section and add them back to them same output section to compute the
+  // output section size.  If we do not account for sizes of relaxed input
+  // sections,  an output section would be incorrectly sized.
+  off_t offset_in_section = this->current_data_size_for_child();
+  off_t aligned_offset_in_section = align_address(offset_in_section,
+						  poris->addralign());
+  this->set_current_data_size_for_child(aligned_offset_in_section
+					+ poris->current_data_size());
+}
+
 // Add arbitrary data to an output section by Input_section.
 
 void
@@ -1995,73 +2037,151 @@ Output_section::add_merge_input_section(Relobj* object, unsigned int shndx,
   // We cannot restore merged input section states.
   gold_assert(this->checkpoint_ == NULL);
 
-  Input_section_list::iterator p;
-  for (p = this->input_sections_.begin();
-       p != this->input_sections_.end();
-       ++p)
-    if (p->is_merge_section(is_string, entsize, addralign))
-      {
-        p->add_input_section(object, shndx);
-        return true;
-      }
+  // Look up merge sections by required properties.
+  Merge_section_properties msp(is_string, entsize, addralign);
+  Merge_section_by_properties_map::const_iterator p =
+    this->merge_section_by_properties_map_.find(msp);
+  if (p != this->merge_section_by_properties_map_.end())
+    {
+      Output_merge_base* merge_section = p->second;
+      merge_section->add_input_section(object, shndx);
+      gold_assert(merge_section->is_string() == is_string
+		  && merge_section->entsize() == entsize
+		  && merge_section->addralign() == addralign);
+
+      // Link input section to found merge section.
+      Input_section_specifier iss(object, shndx);
+      this->merge_section_map_[iss] = merge_section;
+      return true;
+    }
 
   // We handle the actual constant merging in Output_merge_data or
   // Output_merge_string_data.
-  Output_section_data* posd;
+  Output_merge_base* pomb;
   if (!is_string)
-    posd = new Output_merge_data(entsize, addralign);
+    pomb = new Output_merge_data(entsize, addralign);
   else
     {
       switch (entsize)
 	{
         case 1:
-	  posd = new Output_merge_string<char>(addralign);
+	  pomb = new Output_merge_string<char>(addralign);
 	  break;
         case 2:
-	  posd = new Output_merge_string<uint16_t>(addralign);
+	  pomb = new Output_merge_string<uint16_t>(addralign);
 	  break;
         case 4:
-	  posd = new Output_merge_string<uint32_t>(addralign);
+	  pomb = new Output_merge_string<uint32_t>(addralign);
 	  break;
         default:
 	  return false;
 	}
     }
 
-  this->add_output_merge_section(posd, is_string, entsize);
-  posd->add_input_section(object, shndx);
+  // Add new merge section to this output section and link merge section
+  // properties to new merge section in map.
+  this->add_output_merge_section(pomb, is_string, entsize);
+  this->merge_section_by_properties_map_[msp] = pomb;
+
+  // Add input section to new merge section and link input section to new
+  // merge section in map.
+  pomb->add_input_section(object, shndx);
+  Input_section_specifier iss(object, shndx);
+  this->merge_section_map_[iss] = pomb;
 
   return true;
 }
 
-// Relax an existing input section.
+// Build a relaxation map to speed up relaxation of existing input sections.
+// Look up to the first LIMIT elements in INPUT_SECTIONS.
+
 void
-Output_section::relax_input_section(Output_relaxed_input_section *psection)
+Output_section::build_relaxation_map(
+  const Input_section_list& input_sections,
+  size_t limit,
+  Relaxation_map* relaxation_map) const
 {
-  Relobj* relobj = psection->relobj();
-  unsigned int shndx = psection->shndx();
+  for (size_t i = 0; i < limit; ++i)
+    {
+      const Input_section& is(input_sections[i]);
+      if (is.is_input_section() || is.is_relaxed_input_section())
+	{
+	  Input_section_specifier iss(is.relobj(), is.shndx());
+	  (*relaxation_map)[iss] = i;
+	}
+    }
+}
+
+// Convert regular input sections in INPUT_SECTIONS into relaxed input
+// sections in RELAXED_SECTIONS.  MAP is a prebuilt map from input section
+// specifier to indices of INPUT_SECTIONS.
+
+void
+Output_section::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)
+{
+  for (size_t i = 0; i < relaxed_sections.size(); ++i)
+    {
+      Output_relaxed_input_section* poris = relaxed_sections[i];
+      Input_section_specifier iss(poris->relobj(), poris->shndx());
+      Relaxation_map::const_iterator p = map.find(iss);
+      gold_assert(p != map.end());
+      gold_assert((*input_sections)[p->second].is_input_section());
+      (*input_sections)[p->second] = Input_section(poris);
+    }
+}
+  
+// Convert regular input sections into relaxed input sections. RELAXED_SECTIONS
+// is a vector of pointers to Output_relaxed_input_section or its derived
+// classes.  The relaxed sections must correspond to existing input sections.
 
+void
+Output_section::convert_input_sections_to_relaxed_sections(
+  const std::vector<Output_relaxed_input_section*>& relaxed_sections)
+{
   gold_assert(parameters->target().may_relax());
 
-  // This is not very efficient if we a going to relax a number of sections
-  // in an Output_section with lot of Input_sections.
-  for (Input_section_list::iterator p = this->input_sections_.begin();
-       p != this->input_sections_.end();
-       ++p)
+  // We want to make sure that restore_states does not undo the effect of
+  // this.  If there is no checkpoint active, just search the current
+  // input section list and replace the sections there.  If there is
+  // a checkpoint, also replace the sections there.
+  
+  // By default, we look at the whole list.
+  size_t limit = this->input_sections_.size();
+
+  if (this->checkpoint_ != NULL)
     {
-      if (p->is_input_section())
+      // Replace input sections with relaxed input section in the saved
+      // copy of the input section list.
+      if (this->checkpoint_->input_sections_saved())
 	{
-	  if (p->relobj() == relobj && p->shndx() == shndx)
-	    {
-	      gold_assert(p->addralign() == psection->addralign());
-	      *p = Input_section(psection);
-	      return;
-	    }
+	  Relaxation_map map;
+	  this->build_relaxation_map(
+		    *(this->checkpoint_->input_sections()),
+		    this->checkpoint_->input_sections()->size(),
+		    &map);
+	  this->convert_input_sections_in_list_to_relaxed_sections(
+		    relaxed_sections,
+		    map,
+		    this->checkpoint_->input_sections());
+	}
+      else
+	{
+	  // We have not copied the input section list yet.  Instead, just
+	  // look at the portion that would be saved.
+	  limit = this->checkpoint_->input_sections_size();
 	}
-      else if (p->is_relaxed_input_section())
-	gold_assert(p->relobj() != relobj || p->shndx() != shndx);
-
     }
+
+  // Convert input sections in input_section_list.
+  Relaxation_map map;
+  this->build_relaxation_map(this->input_sections_, limit, &map);
+  this->convert_input_sections_in_list_to_relaxed_sections(
+	    relaxed_sections,
+	    map,
+	    &this->input_sections_);
 }
 
 // Update the output section flags based on input section flags.
@@ -2082,6 +2202,60 @@ Output_section::update_flags_for_input_section(elfcpp::Elf_Xword flags)
 		      | elfcpp::SHF_EXECINSTR));
 }
 
+// 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*
+Output_section::find_merge_section(const Relobj* object,
+				   unsigned int shndx) const
+{
+  Input_section_specifier iss(object, shndx);
+  Output_section_data_by_input_section_map::const_iterator p =
+    this->merge_section_map_.find(iss);
+  if (p != this->merge_section_map_.end())
+    {
+      Output_section_data* posd = p->second;
+      gold_assert(posd->is_merge_section_for(object, shndx));
+      return posd;
+    }
+  else
+    return NULL;
+}
+
+// Find an relaxed input section corresponding to an input section
+// in OBJECT with index SHNDX.
+
+const Output_section_data*
+Output_section::find_relaxed_input_section(const Relobj* object,
+					   unsigned int shndx) const
+{
+  // Be careful that the map may not be valid due to input section export
+  // to scripts or a check-point restore.
+  if (!this->is_relaxed_input_section_map_valid_)
+    {
+      // Rebuild the map as needed.
+      this->relaxed_input_section_map_.clear();
+      for (Input_section_list::const_iterator p = this->input_sections_.begin();
+	   p != this->input_sections_.end();
+	   ++p)
+	if (p->is_relaxed_input_section())
+	  {
+	    Input_section_specifier iss(p->relobj(), p->shndx());
+	    this->relaxed_input_section_map_[iss] =
+	      p->relaxed_input_section();
+	  }
+      this->is_relaxed_input_section_map_valid_ = true;
+    }
+
+  Input_section_specifier iss(object, shndx);
+  Output_section_data_by_input_section_map::const_iterator p =
+    this->relaxed_input_section_map_.find(iss);
+  if (p != this->relaxed_input_section_map_.end())
+    return p->second;
+  else
+    return NULL;
+}
+
 // Given an address OFFSET relative to the start of input section
 // SHNDX in OBJECT, return whether this address is being included in
 // the final link.  This should only be called if SHNDX in OBJECT has
@@ -2092,6 +2266,20 @@ Output_section::is_input_address_mapped(const Relobj* object,
 					unsigned int shndx,
 					off_t offset) const
 {
+  // Look at the Output_section_data_maps first.
+  const Output_section_data* posd = this->find_merge_section(object, shndx);
+  if (posd == NULL)
+    posd = this->find_relaxed_input_section(object, shndx);
+
+  if (posd != NULL)
+    {
+      section_offset_type output_offset;
+      bool found = posd->output_offset(object, shndx, offset, &output_offset);
+      gold_assert(found);   
+      return output_offset != -1;
+    }
+
+  // Fall back to the slow look-up.
   for (Input_section_list::const_iterator p = this->input_sections_.begin();
        p != this->input_sections_.end();
        ++p)
@@ -2116,9 +2304,23 @@ section_offset_type
 Output_section::output_offset(const Relobj* object, unsigned int shndx,
 			      section_offset_type offset) const
 {
-  // This can only be called meaningfully when layout is complete.
-  gold_assert(Output_data::is_layout_complete());
+  // This can only be called meaningfully when we know the data size
+  // of this.
+  gold_assert(this->is_data_size_valid());
 
+  // Look at the Output_section_data_maps first.
+  const Output_section_data* posd = this->find_merge_section(object, shndx);
+  if (posd == NULL) 
+    posd = this->find_relaxed_input_section(object, shndx);
+  if (posd != NULL)
+    {
+      section_offset_type output_offset;
+      bool found = posd->output_offset(object, shndx, offset, &output_offset);
+      gold_assert(found);   
+      return output_offset;
+    }
+
+  // Fall back to the slow look-up.
   for (Input_section_list::const_iterator p = this->input_sections_.begin();
        p != this->input_sections_.end();
        ++p)
@@ -2138,6 +2340,20 @@ Output_section::output_address(const Relobj* object, unsigned int shndx,
 			       off_t offset) const
 {
   uint64_t addr = this->address() + this->first_input_offset_;
+
+  // Look at the Output_section_data_maps first.
+  const Output_section_data* posd = this->find_merge_section(object, shndx);
+  if (posd == NULL) 
+    posd = this->find_relaxed_input_section(object, shndx);
+  if (posd != NULL && posd->is_address_valid())
+    {
+      section_offset_type output_offset;
+      bool found = posd->output_offset(object, shndx, offset, &output_offset);
+      gold_assert(found);
+      return posd->address() + output_offset;
+    }
+
+  // Fall back to the slow look-up.
   for (Input_section_list::const_iterator p = this->input_sections_.begin();
        p != this->input_sections_.end();
        ++p)
@@ -2169,6 +2385,9 @@ Output_section::find_starting_output_address(const Relobj* object,
 					     unsigned int shndx,
 					     uint64_t* paddr) const
 {
+  // FIXME: This becomes a bottle-neck if we have many relaxed sections.
+  // Looking up the merge section map does not always work as we sometimes
+  // find a merge section without its address set.
   uint64_t addr = this->address() + this->first_input_offset_;
   for (Input_section_list::const_iterator p = this->input_sections_.begin();
        p != this->input_sections_.end();
@@ -2532,6 +2751,9 @@ Output_section::do_write(Output_file* of)
 {
   gold_assert(!this->requires_postprocessing());
 
+  // If the target performs relaxation, we delay filler generation until now.
+  gold_assert(!this->generate_code_fills_at_write_ || this->fills_.empty());
+
   off_t output_section_file_offset = this->offset();
   for (Fill_list::iterator p = this->fills_.begin();
        p != this->fills_.end();
@@ -2542,10 +2764,22 @@ Output_section::do_write(Output_file* of)
 		fill_data.data(), fill_data.size());
     }
 
+  off_t off = this->offset() + this->first_input_offset_;
   for (Input_section_list::iterator p = this->input_sections_.begin();
        p != this->input_sections_.end();
        ++p)
-    p->write(of);
+    {
+      off_t aligned_off = align_address(off, p->addralign());
+      if (this->generate_code_fills_at_write_ && (off != aligned_off))
+	{
+	  size_t fill_len = aligned_off - off;
+	  std::string fill_data(parameters->target().code_fill(fill_len));
+	  of->write(off, fill_data.data(), fill_data.size());
+	}
+
+      p->write(of);
+      off = aligned_off + p->data_size();
+    }
 }
 
 // If a section requires postprocessing, create the buffer to use.
@@ -2586,6 +2820,9 @@ Output_section::write_to_postprocessing_buffer()
 {
   gold_assert(this->requires_postprocessing());
 
+  // If the target performs relaxation, we delay filler generation until now.
+  gold_assert(!this->generate_code_fills_at_write_ || this->fills_.empty());
+
   unsigned char* buffer = this->postprocessing_buffer();
   for (Fill_list::iterator p = this->fills_.begin();
        p != this->fills_.end();
@@ -2601,9 +2838,16 @@ Output_section::write_to_postprocessing_buffer()
        p != this->input_sections_.end();
        ++p)
     {
-      off = align_address(off, p->addralign());
-      p->write_to_buffer(buffer + off);
-      off += p->data_size();
+      off_t aligned_off = align_address(off, p->addralign());
+      if (this->generate_code_fills_at_write_ && (off != aligned_off))
+	{
+	  size_t fill_len = aligned_off - off;
+	  std::string fill_data(parameters->target().code_fill(fill_len));
+	  memcpy(buffer + off, fill_data.data(), fill_data.size());
+	}
+
+      p->write_to_buffer(buffer + aligned_off);
+      off = aligned_off + p->data_size();
     }
 }
 
@@ -2627,6 +2871,9 @@ Output_section::get_input_sections(
       && !this->checkpoint_->input_sections_saved())
     this->checkpoint_->save_input_sections();
 
+  // Invalidate the relaxed input section map.
+  this->is_relaxed_input_section_map_valid_ = false;
+
   uint64_t orig_address = address;
 
   address = align_address(address, this->addralign());
@@ -2738,11 +2985,15 @@ Output_section::restore_states()
       // extremely large output with hundreads of thousands of input
       // objects.  We may need to re-think how we should pass sections
       // to scripts.
-      this->input_sections_ = checkpoint->input_sections();
+      this->input_sections_ = *checkpoint->input_sections();
     }
 
   this->attached_input_sections_are_sorted_ =
     checkpoint->attached_input_sections_are_sorted();
+
+  // Simply invalidate the relaxed input section map since we do not keep
+  // track of it.
+  this->is_relaxed_input_section_map_valid_ = false;
 }
 
 // Print to the map file.