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

	* debug.h (DEBUG_RELAXATION): New constant.
	(DEBUG_ALL): Add DEBUG_RELAXATION.
	(debug_string_to_enum): Add relaxation debug option.
	* layout.cc
	(Layout::Relaxation_debug_check::check_output_data_for_reset_values,
	Layout::Relaxation_debug_check::read_sections,
	Layout::Relaxation_debug_check::read_sections): New method definitions.
	(Layout::Layout): Initialize data members
	record_output_section_data_from_scrips_,
	script_output_section_data_list_ and relaxation_debug_check_.
	(Layout::save_segments, Layout::restore_segments,
	Layout::clean_up_after_relaxation, Layout::prepare_for_relaxation,
	Layout::relaxation_loop_body): New method definitions.
	(Layout::finalize): Support relaxation.  Move section layout code to
	Layout::relaxation_loop_body.
	(Layout::set_asection_address_from_script): Move code for orphan
	section placement out.
	(Layout::place_orphan_sections_in_script): New method definition.
	* layout.h (Output_segment_headers, Output_file_header):
	New forward class declarations.
	(Layout::~Layout): Define.
	(Layout::new_output_section_data_from_script): New method definition.
	(Layout::place_orphan_sections_in_script): New method declaration.
	(Layout::Segment_states): New type declaration.
	(Layout::save_segments, Layout::restore_segments,
	Layout::clean_up_after_relaxation, Layout::prepare_for_relaxation,
	Layout::relaxation_loop_body): New method declarations.
	(Layout::Output_section_data_list): New type declaration.
	(Layout::Relaxation_debug_check): New class definition.
	(Layout::record_output_section_data_from_script_,
	Layout::script_output_section_data_list_, Layout::segment_states_,
	Layout::relaxation_debug_check_): New data members.
	* output.cc: (Output_section_headers::do_size): New method definition.
	(Output_section_headers::Output_section_headers): Move size
	computation to Output_section_headers::do_size.
	(Output_segment_headers::do_size): New method definition.
	(Output_file_header::Output_file_header): Move size computation to
	Output_file_header::do_size and call it.
	(Output_file_header::do_size): New method definition.
	(Output_data_group::Output_data_group): Adjust call to
	Output_section_data.
	(Output_data_dynamic::set_final_data_size): Add DT_NULL tag only once.
	(Output_symtab_xindex::do_write): Add array bound check.
 	(Output_section::Input_section::print_to_mapfile): Handle
	RELAXED_INPUT_SECTION_CODE.
	(Output_section::Output_section): Initialize data member checkpoint_.
	(Output_section::~Output_section): Delete checkpoint object pointed
	by checkpoint_.
	(Output_section::add_input_section): Always add an Input_section if
	relaxing.
	(Output_section::add_merge_input_section): Add assert.
	(Output_section::relax_input_section): New method definition.
	(Output_section::set_final_data_size): Set load address to zero for
	an unallocated section.
	(Output_section::do_address_and_file_offset_have_reset_values):
	New method definition.
	(Output_section::Input_section_sort_enty::Input_section_sort_enty):
	Handle relaxed input section.
	(Output_section::sort_attached_input_sections): Checkpoint input
	section list lazily.
	(Output_section::get_input_sections): Change type of input_sections to
	list of Simple_input_section pointers.  Checkpoint input section list
	lazily.  Also handle relaxed input sections.
	(Output_section::add_input_section_for_script): Take a reference to
	a Simple_input_section object instead of Relobj pointer and section
	index as parameter.  Handle relaxed input sections.
	(Output_section::save_states, Output_section::restore_states): New
	method definitions.
	* output.h (Output_data::Output_data): Initialize is_data_size_fixed_.
	(Output_data::is_data_size_fixed): New method definition.
	(Output_data::reset_addresss_and_file_offset): Do not reset data size
	if it is fixed.
	(Output_data::address_and_file_offset_have_reset_values): New method
	definition.
	(Output_data::do_address_and_file_offset_have_reset_values): New method
	definition.
	(Output_data::set_data_size): Check that data size is not fixed.
	(Output_data::fix_data_size): New method definition.
	(Output_data::is_data_size_fixed_): New data member.
	(Output_section_headers::set_final_data_size): New method definition.
	(Output_section_headers::do_size): New method declaration.
	(Output_segment_headers::set_final_data_size): New method definition.
	(Output_segment_headers::do_size): New method declaration.
	(Output_file_header::set_final_data_size)::New method definition.
	(Output_file_header::do_size)::New method declaration.
	(Output_section_data::Output_section_data): Add new parameter
	is_data_size_fixed and use it to fix data size.
	(Output_data_const::Output_data_const): Adjust call to base class
	constructor and fix data size.
	(Output_data_const_buffer::Output_data_const_buffer): Adjust call to
	base class constructor and fix data size.
	(Output_data_fixed_space::Output_data_fixed_space): Adjust call to
	base class constructor and fix data size.
	(Output_data_zero_fill::Output_data_zero_fill): Adjust call to base
	class constructor and fix data size.
	(Output_data_group::set_final_data_size): New method definition.
	(Output_data_dynamic::Dynamic_entry::tag): New method definition.
	(Output_symtab_xindex::Output_symtab_xindex): Adjust call to base
	class constructor and fix data size.
	(Output_relaxed_input_section): New class definition.
	(Output_section::Simple_input_section): New class definition.
	(Output_section::get_input_sections): Adjust parameter list.
	(Output_section::add_input_section_for_script): Same.
	(Output_section::save_states, Output_section::restore_states,
	Output_section::do_address_and_file_offset_have_reset_values,
	(Output_section::Input_section::Input_section): Handle
	RELAXED_INPUT_SECTION_CODE.  Add new overload for
	Output_relaxed_input_section.
	(Output_section::Input_section::is_input_section,
	Output_section::Input_section::set_output_section): Handle relaxed
	input section.
	(Output_section::Input_section::is_relaxed_input_section,
	Output_section::Input_section::output_section_data,
	Output_section::Input_section::relaxed_input_section): New method
	definitions.
	(Output_section::Input_section::RELAXED_INPUT_SECTION_CODE): New enum
	value.
	(Output_section::Input_section::u1_): Update comments.
	(Output_section::Input_section::u2_): Add new union member poris.
	(Output_section::Checkpoint_output_section): New classs definition.
	(Output_section::relax_input_section): New method declaration.
	(Output_section::checkpoint_): New data member.
	(Output_segment): Update comments.
	(Output_segment::Output_segment): Un-privatize copy constructor.
	(Output_segment::operator=): Un-privatize.
	* script-sections.cc (Output_section_element::Input_section_list):
	Change element type to Output_section::Simple_input_section.
	(Output_section_element_dot_assignment::set_section_addresses):
	Register output section data for relaxation clean up.
	(Output_data_exression::Output_data_expression): Adjust call to base
	constructor to fix data size.
	(Output_section_element_data::set_section_addresses): Register
	Output_data_expression object for relaxation clean up.
	(struct Input_section_info): Replace Relobj pointer and section index
	pair with Output_section::Simple_input_section and Convert struct to a
	class.
	(Input_section_sorter::operator()): Adjust access to
	Input_section_info data member to use accessors.
	(Output_section_element_input::set_section_addresses): Use layout
	parameter.  Adjust code to use Output_section::Simple_input_section
	and Input_secction_info classes.  Register filler for relaxation
	clean up.
	(Orphan_output_section::set_section_addresses): Replace Relobj pointer
	and section index pair with Output_section::Simple_input_section
	class.  Adjust code accordingly.
	(Phdrs_element::release_segment): New method definition.
	(Script_sections::attach_sections_using_phdrs_clause): Do not modify
	segment list.
	(Script_sections::release_segments): New method definition.
	* gold/script-sections.h (Script_sections::release_segments): New
	method declaration.
	* gold/target.h (Target::may_relax, Target::relax,
	Target::do_may_relax, Target::do_relax): New method definitions.

1 files changed, 194 insertions, 42 deletions

diff --git a/gold/output.cc b/gold/output.cc
index e99464b..4ef0a30 100644
--- a/gold/output.cc
+++ b/gold/output.cc
@@ -109,25 +109,34 @@ Output_section_headers::Output_section_headers(
     secnamepool_(secnamepool),
     shstrtab_section_(shstrtab_section)
 {
+}
+
+// Compute the current data size.
+
+off_t
+Output_section_headers::do_size() const
+{
   // Count all the sections.  Start with 1 for the null section.
   off_t count = 1;
   if (!parameters->options().relocatable())
     {
-      for (Layout::Segment_list::const_iterator p = segment_list->begin();
-	   p != segment_list->end();
+      for (Layout::Segment_list::const_iterator p =
+	     this->segment_list_->begin();
+	   p != this->segment_list_->end();
 	   ++p)
 	if ((*p)->type() == elfcpp::PT_LOAD)
 	  count += (*p)->output_section_count();
     }
   else
     {
-      for (Layout::Section_list::const_iterator p = section_list->begin();
-	   p != section_list->end();
+      for (Layout::Section_list::const_iterator p =
+	     this->section_list_->begin();
+	   p != this->section_list_->end();
 	   ++p)
 	if (((*p)->flags() & elfcpp::SHF_ALLOC) != 0)
 	  ++count;
     }
-  count += unattached_section_list->size();
+  count += this->unattached_section_list_->size();
 
   const int size = parameters->target().get_size();
   int shdr_size;
@@ -138,7 +147,7 @@ Output_section_headers::Output_section_headers(
   else
     gold_unreachable();
 
-  this->set_data_size(count * shdr_size);
+  return count * shdr_size;
 }
 
 // Write out the section headers.
@@ -269,16 +278,6 @@ Output_segment_headers::Output_segment_headers(
     const Layout::Segment_list& segment_list)
   : segment_list_(segment_list)
 {
-  const int size = parameters->target().get_size();
-  int phdr_size;
-  if (size == 32)
-    phdr_size = elfcpp::Elf_sizes<32>::phdr_size;
-  else if (size == 64)
-    phdr_size = elfcpp::Elf_sizes<64>::phdr_size;
-  else
-    gold_unreachable();
-
-  this->set_data_size(segment_list.size() * phdr_size);
 }
 
 void
@@ -335,6 +334,21 @@ Output_segment_headers::do_sized_write(Output_file* of)
   of->write_output_view(this->offset(), all_phdrs_size, view);
 }
 
+off_t
+Output_segment_headers::do_size() const
+{
+  const int size = parameters->target().get_size();
+  int phdr_size;
+  if (size == 32)
+    phdr_size = elfcpp::Elf_sizes<32>::phdr_size;
+  else if (size == 64)
+    phdr_size = elfcpp::Elf_sizes<64>::phdr_size;
+  else
+    gold_unreachable();
+
+  return this->segment_list_.size() * phdr_size;
+}
+
 // Output_file_header methods.
 
 Output_file_header::Output_file_header(const Target* target,
@@ -348,16 +362,7 @@ Output_file_header::Output_file_header(const Target* target,
     shstrtab_(NULL),
     entry_(entry)
 {
-  const int size = parameters->target().get_size();
-  int ehdr_size;
-  if (size == 32)
-    ehdr_size = elfcpp::Elf_sizes<32>::ehdr_size;
-  else if (size == 64)
-    ehdr_size = elfcpp::Elf_sizes<64>::ehdr_size;
-  else
-    gold_unreachable();
-
-  this->set_data_size(ehdr_size);
+  this->set_data_size(this->do_size());
 }
 
 // Set the section table information for a file header.
@@ -539,6 +544,20 @@ Output_file_header::entry()
   return v;
 }
 
+// Compute the current data size.
+
+off_t
+Output_file_header::do_size() const
+{
+  const int size = parameters->target().get_size();
+  if (size == 32)
+    return elfcpp::Elf_sizes<32>::ehdr_size;
+  else if (size == 64)
+    return elfcpp::Elf_sizes<64>::ehdr_size;
+  else
+    gold_unreachable();
+}
+
 // Output_data_const methods.
 
 void
@@ -1075,7 +1094,7 @@ Output_data_group<size, big_endian>::Output_data_group(
     section_size_type entry_count,
     elfcpp::Elf_Word flags,
     std::vector<unsigned int>* input_shndxes)
-  : Output_section_data(entry_count * 4, 4),
+  : Output_section_data(entry_count * 4, 4, false),
     relobj_(relobj),
     flags_(flags)
 {
@@ -1501,8 +1520,11 @@ Output_data_dynamic::do_adjust_output_section(Output_section* os)
 void
 Output_data_dynamic::set_final_data_size()
 {
-  // Add the terminating entry.
-  this->add_constant(elfcpp::DT_NULL, 0);
+  // Add the terminating entry if it hasn't been added.
+  // Because of relaxation, we can run this multiple times.
+  if (this->entries_.empty()
+      || this->entries_.rbegin()->tag() != elfcpp::DT_NULL)
+    this->add_constant(elfcpp::DT_NULL, 0);
 
   int dyn_size;
   if (parameters->target().get_size() == 32)
@@ -1602,7 +1624,11 @@ Output_symtab_xindex::endian_do_write(unsigned char* const oview)
   for (Xindex_entries::const_iterator p = this->entries_.begin();
        p != this->entries_.end();
        ++p)
-    elfcpp::Swap<32, big_endian>::writeval(oview + p->first * 4, p->second);
+    {
+      unsigned int symndx = p->first;
+      gold_assert(symndx * 4 < this->data_size());
+      elfcpp::Swap<32, big_endian>::writeval(oview + symndx * 4, p->second);
+    }
 }
 
 // Output_section::Input_section methods.
@@ -1720,6 +1746,14 @@ Output_section::Input_section::print_to_mapfile(Mapfile* mapfile) const
       this->u2_.posd->print_to_mapfile(mapfile);
       break;
 
+    case RELAXED_INPUT_SECTION_CODE:
+      {
+        Output_relaxed_input_section* relaxed_section =
+	  this->relaxed_input_section();
+        mapfile->print_input_section(relaxed_section->relobj(),
+				     relaxed_section->shndx());
+      }
+      break;
     default:
       mapfile->print_input_section(this->u2_.object, this->shndx_);
       break;
@@ -1766,7 +1800,8 @@ Output_section::Output_section(const char* name, elfcpp::Elf_Word type,
     is_relro_local_(false),
     is_small_section_(false),
     is_large_section_(false),
-    tls_offset_(0)
+    tls_offset_(0),
+    checkpoint_(NULL)
 {
   // An unallocated section has no address.  Forcing this means that
   // we don't need special treatment for symbols defined in debug
@@ -1777,6 +1812,7 @@ Output_section::Output_section(const char* name, elfcpp::Elf_Word type,
 
 Output_section::~Output_section()
 {
+  delete this->checkpoint_;
 }
 
 // Set the entry size.
@@ -1883,13 +1919,13 @@ Output_section::add_input_section(Sized_relobj<size, big_endian>* object,
   // We need to keep track of this section if we are already keeping
   // track of sections, or if we are relaxing.  Also, if this is a
   // section which requires sorting, or which may require sorting in
-  // the future, we keep track of the sections.  FIXME: Add test for
-  // relaxing.
+  // the future, we keep track of the sections.
   if (have_sections_script
       || !this->input_sections_.empty()
       || this->may_sort_attached_input_sections()
       || this->must_sort_attached_input_sections()
-      || parameters->options().user_set_Map())
+      || parameters->options().user_set_Map()
+      || object->target()->may_relax())
     this->input_sections_.push_back(Input_section(object, shndx,
 						  shdr.get_sh_size(),
 						  addralign));
@@ -1956,6 +1992,9 @@ Output_section::add_merge_input_section(Relobj* object, unsigned int shndx,
   if (is_string && addralign > entsize)
     return false;
 
+  // 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();
@@ -1995,6 +2034,36 @@ Output_section::add_merge_input_section(Relobj* object, unsigned int shndx,
   return true;
 }
 
+// Relax an existing input section.
+void
+Output_section::relax_input_section(Output_relaxed_input_section *psection)
+{
+  Relobj* relobj = psection->relobj();
+  unsigned int shndx = psection->shndx();
+
+  gold_assert(relobj->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)
+    {
+      if (p->is_input_section())
+	{
+	  if (p->relobj() == relobj && p->shndx() == shndx)
+	    {
+	      gold_assert(p->addralign() == psection->addralign());
+	      *p = Input_section(psection);
+	      return;
+	    }
+	}
+      else if (p->is_relaxed_input_section())
+	gold_assert(p->relobj() != relobj || p->shndx() != shndx);
+
+    }
+}
+
 // Update the output section flags based on input section flags.
 
 void
@@ -2160,11 +2229,32 @@ Output_section::set_final_data_size()
 void
 Output_section::do_reset_address_and_file_offset()
 {
+  // An unallocated section has no address.  Forcing this means that
+  // we don't need special treatment for symbols defined in debug
+  // sections.  We do the same in the constructor.
+  if ((this->flags_ & elfcpp::SHF_ALLOC) == 0)
+     this->set_address(0);
+
   for (Input_section_list::iterator p = this->input_sections_.begin();
        p != this->input_sections_.end();
        ++p)
     p->reset_address_and_file_offset();
 }
+  
+// Return true if address and file offset have the values after reset.
+
+bool
+Output_section::do_address_and_file_offset_have_reset_values() const
+{
+  if (this->is_offset_valid())
+    return false;
+
+  // An unallocated section has address 0 after its construction or a reset.
+  if ((this->flags_ & elfcpp::SHF_ALLOC) == 0)
+    return this->is_address_valid() && this->address() == 0;
+  else
+    return !this->is_address_valid();
+}
 
 // Set the TLS offset.  Called only for SHT_TLS sections.
 
@@ -2193,7 +2283,8 @@ class Output_section::Input_section_sort_entry
   Input_section_sort_entry(const Input_section& input_section,
 			   unsigned int index)
     : input_section_(input_section), index_(index),
-      section_has_name_(input_section.is_input_section())
+      section_has_name_(input_section.is_input_section()
+			|| input_section.is_relaxed_input_section())
   {
     if (this->section_has_name_)
       {
@@ -2201,7 +2292,9 @@ class Output_section::Input_section_sort_entry
 	// so it is OK to lock.  Unfortunately we have no way to pass
 	// in a Task token.
 	const Task* dummy_task = reinterpret_cast<const Task*>(-1);
-	Object* obj = input_section.relobj();
+	Object* obj = (input_section.is_input_section()
+		       ? input_section.relobj()
+		       : input_section.relaxed_input_section()->relobj());
 	Task_lock_obj<Object> tl(dummy_task, obj);
 
 	// This is a slow operation, which should be cached in
@@ -2350,6 +2443,10 @@ Output_section::sort_attached_input_sections()
   if (this->attached_input_sections_are_sorted_)
     return;
 
+  if (this->checkpoint_ != NULL
+      && !this->checkpoint_->input_sections_saved())
+    this->checkpoint_->save_input_sections();
+
   // The only thing we know about an input section is the object and
   // the section index.  We need the section name.  Recomputing this
   // is slow but this is an unusual case.  If this becomes a speed
@@ -2524,8 +2621,12 @@ uint64_t
 Output_section::get_input_sections(
     uint64_t address,
     const std::string& fill,
-    std::list<std::pair<Relobj*, unsigned int> >* input_sections)
+    std::list<Simple_input_section>* input_sections)
 {
+  if (this->checkpoint_ != NULL
+      && !this->checkpoint_->input_sections_saved())
+    this->checkpoint_->save_input_sections();
+
   uint64_t orig_address = address;
 
   address = align_address(address, this->addralign());
@@ -2536,7 +2637,11 @@ Output_section::get_input_sections(
        ++p)
     {
       if (p->is_input_section())
-	input_sections->push_back(std::make_pair(p->relobj(), p->shndx()));
+	input_sections->push_back(Simple_input_section(p->relobj(),
+						       p->shndx()));
+      else if (p->is_relaxed_input_section())
+	input_sections->push_back(
+	    Simple_input_section(p->relaxed_input_section()));
       else
 	{
 	  uint64_t aligned_address = align_address(address, p->addralign());
@@ -2574,8 +2679,7 @@ Output_section::get_input_sections(
 // Add an input section from a script.
 
 void
-Output_section::add_input_section_for_script(Relobj* object,
-					     unsigned int shndx,
+Output_section::add_input_section_for_script(const Simple_input_section& sis,
 					     off_t data_size,
 					     uint64_t addralign)
 {
@@ -2589,8 +2693,56 @@ Output_section::add_input_section_for_script(Relobj* object,
   this->set_current_data_size_for_child(aligned_offset_in_section
 					+ data_size);
 
-  this->input_sections_.push_back(Input_section(object, shndx,
-						data_size, addralign));
+  Input_section is =
+    (sis.is_relaxed_input_section()
+     ? Input_section(sis.relaxed_input_section())
+     : Input_section(sis.relobj(), sis.shndx(), data_size, addralign));
+  this->input_sections_.push_back(is);
+}
+
+//
+
+void
+Output_section::save_states()
+{
+  gold_assert(this->checkpoint_ == NULL);
+  Checkpoint_output_section* checkpoint =
+    new Checkpoint_output_section(this->addralign_, this->flags_,
+				  this->input_sections_,
+				  this->first_input_offset_,
+				  this->attached_input_sections_are_sorted_);
+  this->checkpoint_ = checkpoint;
+  gold_assert(this->fills_.empty());
+}
+
+void
+Output_section::restore_states()
+{
+  gold_assert(this->checkpoint_ != NULL);
+  Checkpoint_output_section* checkpoint = this->checkpoint_;
+
+  this->addralign_ = checkpoint->addralign();
+  this->flags_ = checkpoint->flags();
+  this->first_input_offset_ = checkpoint->first_input_offset();
+
+  if (!checkpoint->input_sections_saved())
+    {
+      // If we have not copied the input sections, just resize it.
+      size_t old_size = checkpoint->input_sections_size();
+      gold_assert(this->input_sections_.size() >= old_size);
+      this->input_sections_.resize(old_size);
+    }
+  else
+    {
+      // We need to copy the whole list.  This is not efficient for
+      // 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->attached_input_sections_are_sorted_ =
+    checkpoint->attached_input_sections_are_sorted();
 }
 
 // Print to the map file.