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, 337 insertions, 54 deletions

diff --git a/gold/layout.cc b/gold/layout.cc
index 6907295..1b836de 100644
--- a/gold/layout.cc
+++ b/gold/layout.cc
@@ -53,6 +53,79 @@
 namespace gold
 {
 
+// Layout::Relaxation_debug_check methods.
+
+// Check that sections and special data are in reset states.
+// We do not save states for Output_sections and special Output_data.
+// So we check that they have not assigned any addresses or offsets.
+// clean_up_after_relaxation simply resets their addresses and offsets.
+void
+Layout::Relaxation_debug_check::check_output_data_for_reset_values(
+    const Layout::Section_list& sections,
+    const Layout::Data_list& special_outputs)
+{
+  for(Layout::Section_list::const_iterator p = sections.begin();
+      p != sections.end();
+      ++p)
+    gold_assert((*p)->address_and_file_offset_have_reset_values());
+
+  for(Layout::Data_list::const_iterator p = special_outputs.begin();
+      p != special_outputs.end();
+      ++p)
+    gold_assert((*p)->address_and_file_offset_have_reset_values());
+}
+  
+// Save information of SECTIONS for checking later.
+
+void
+Layout::Relaxation_debug_check::read_sections(
+    const Layout::Section_list& sections)
+{
+  for(Layout::Section_list::const_iterator p = sections.begin();
+      p != sections.end();
+      ++p)
+    {
+      Output_section* os = *p;
+      Section_info info;
+      info.output_section = os;
+      info.address = os->is_address_valid() ? os->address() : 0;
+      info.data_size = os->is_data_size_valid() ? os->data_size() : -1;
+      info.offset = os->is_offset_valid()? os->offset() : -1 ;
+      this->section_infos_.push_back(info);
+    }
+}
+
+// Verify SECTIONS using previously recorded information.
+
+void
+Layout::Relaxation_debug_check::verify_sections(
+    const Layout::Section_list& sections)
+{
+  size_t i = 0;
+  for(Layout::Section_list::const_iterator p = sections.begin();
+      p != sections.end();
+      ++p, ++i)
+    {
+      Output_section* os = *p;
+      uint64_t address = os->is_address_valid() ? os->address() : 0;
+      off_t data_size = os->is_data_size_valid() ? os->data_size() : -1;
+      off_t offset = os->is_offset_valid()? os->offset() : -1 ;
+
+      if (i >= this->section_infos_.size())
+	{
+	  gold_fatal("Section_info of %s missing.\n", os->name());
+	}
+      const Section_info& info = this->section_infos_[i];
+      if (os != info.output_section)
+	gold_fatal("Section order changed.  Expecting %s but see %s\n",
+		   info.output_section->name(), os->name());
+      if (address != info.address
+	  || data_size != info.data_size
+	  || offset != info.offset)
+	gold_fatal("Section %s changed.\n", os->name());
+    }
+}
+
 // Layout_task_runner methods.
 
 // Lay out the sections.  This is called after all the input objects
@@ -125,7 +198,11 @@ Layout::Layout(int number_of_input_files, Script_options* script_options)
     any_postprocessing_sections_(false),
     resized_signatures_(false),
     have_stabstr_section_(false),
-    incremental_inputs_(NULL)
+    incremental_inputs_(NULL),
+    record_output_section_data_from_script_(false),
+    script_output_section_data_list_(),
+    segment_states_(NULL),
+    relaxation_debug_check_(NULL)
 {
   // Make space for more than enough segments for a typical file.
   // This is just for efficiency--it's OK if we wind up needing more.
@@ -1170,6 +1247,226 @@ Layout::find_first_load_seg()
   return load_seg;
 }
 
+// Save states of all current output segments.  Store saved states
+// in SEGMENT_STATES.
+
+void
+Layout::save_segments(Segment_states* segment_states)
+{
+  for (Segment_list::const_iterator p = this->segment_list_.begin();
+       p != this->segment_list_.end();
+       ++p)
+    {
+      Output_segment* segment = *p;
+      // Shallow copy.
+      Output_segment* copy = new Output_segment(*segment);
+      (*segment_states)[segment] = copy;
+    }
+}
+
+// Restore states of output segments and delete any segment not found in
+// SEGMENT_STATES.
+
+void
+Layout::restore_segments(const Segment_states* segment_states)
+{
+  // Go through the segment list and remove any segment added in the
+  // relaxation loop.
+  this->tls_segment_ = NULL;
+  this->relro_segment_ = NULL;
+  Segment_list::iterator list_iter = this->segment_list_.begin();
+  while (list_iter != this->segment_list_.end())
+    {
+      Output_segment* segment = *list_iter;
+      Segment_states::const_iterator states_iter =
+	  segment_states->find(segment);
+      if (states_iter != segment_states->end())
+	{
+	  const Output_segment* copy = states_iter->second;
+	  // Shallow copy to restore states.
+	  *segment = *copy;
+
+	  // Also fix up TLS and RELRO segment pointers as appropriate.
+	  if (segment->type() == elfcpp::PT_TLS)
+	    this->tls_segment_ = segment;
+	  else if (segment->type() == elfcpp::PT_GNU_RELRO)
+	    this->relro_segment_ = segment;
+
+	  ++list_iter;
+	} 
+      else
+	{
+	  list_iter = this->segment_list_.erase(list_iter); 
+	  // This is a segment created during section layout.  It should be
+	  // safe to remove it since we should have removed all pointers to it.
+	  delete segment;
+	}
+    }
+}
+
+// Clean up after relaxation so that sections can be laid out again.
+
+void
+Layout::clean_up_after_relaxation()
+{
+  // Restore the segments to point state just prior to the relaxation loop.
+  Script_sections* script_section = this->script_options_->script_sections();
+  script_section->release_segments();
+  this->restore_segments(this->segment_states_);
+
+  // Reset section addresses and file offsets
+  for (Section_list::iterator p = this->section_list_.begin();
+       p != this->section_list_.end();
+       ++p)
+    {
+      (*p)->reset_address_and_file_offset();
+      (*p)->restore_states();
+    }
+  
+  // Reset special output object address and file offsets.
+  for (Data_list::iterator p = this->special_output_list_.begin();
+       p != this->special_output_list_.end();
+       ++p)
+    (*p)->reset_address_and_file_offset();
+
+  // A linker script may have created some output section data objects.
+  // They are useless now.
+  for (Output_section_data_list::const_iterator p =
+	 this->script_output_section_data_list_.begin();
+       p != this->script_output_section_data_list_.end();
+       ++p)
+    delete *p;
+  this->script_output_section_data_list_.clear(); 
+}
+
+// Prepare for relaxation.
+
+void
+Layout::prepare_for_relaxation()
+{
+  // Create an relaxation debug check if in debugging mode.
+  if (is_debugging_enabled(DEBUG_RELAXATION))
+    this->relaxation_debug_check_ = new Relaxation_debug_check();
+
+  // Save segment states.
+  this->segment_states_ = new Segment_states();
+  this->save_segments(this->segment_states_);
+
+  for(Section_list::const_iterator p = this->section_list_.begin();
+      p != this->section_list_.end();
+      ++p)
+    (*p)->save_states();
+
+  if (is_debugging_enabled(DEBUG_RELAXATION))
+    this->relaxation_debug_check_->check_output_data_for_reset_values(
+        this->section_list_, this->special_output_list_);
+
+  // Also enable recording of output section data from scripts.
+  this->record_output_section_data_from_script_ = true;
+}
+
+// Relaxation loop body:  If target has no relaxation, this runs only once
+// Otherwise, the target relaxation hook is called at the end of
+// each iteration.  If the hook returns true, it means re-layout of
+// section is required.  
+//
+// The number of segments created by a linking script without a PHDRS
+// clause may be affected by section sizes and alignments.  There is
+// a remote chance that relaxation causes different number of PT_LOAD
+// segments are created and sections are attached to different segments.
+// Therefore, we always throw away all segments created during section
+// layout.  In order to be able to restart the section layout, we keep
+// a copy of the segment list right before the relaxation loop and use
+// that to restore the segments.
+// 
+// PASS is the current relaxation pass number. 
+// SYMTAB is a symbol table.
+// PLOAD_SEG is the address of a pointer for the load segment.
+// PHDR_SEG is a pointer to the PHDR segment.
+// SEGMENT_HEADERS points to the output segment header.
+// FILE_HEADER points to the output file header.
+// PSHNDX is the address to store the output section index.
+
+off_t inline
+Layout::relaxation_loop_body(
+    int pass,
+    Target* target,
+    Symbol_table* symtab,
+    Output_segment** pload_seg,
+    Output_segment* phdr_seg,
+    Output_segment_headers* segment_headers,
+    Output_file_header* file_header,
+    unsigned int* pshndx)
+{
+  // If this is not the first iteration, we need to clean up after
+  // relaxation so that we can lay out the sections again.
+  if (pass != 0)
+    this->clean_up_after_relaxation();
+
+  // If there is a SECTIONS clause, put all the input sections into
+  // the required order.
+  Output_segment* load_seg;
+  if (this->script_options_->saw_sections_clause())
+    load_seg = this->set_section_addresses_from_script(symtab);
+  else if (parameters->options().relocatable())
+    load_seg = NULL;
+  else
+    load_seg = this->find_first_load_seg();
+
+  if (parameters->options().oformat_enum()
+      != General_options::OBJECT_FORMAT_ELF)
+    load_seg = NULL;
+
+  gold_assert(phdr_seg == NULL || load_seg != NULL);
+
+  // Lay out the segment headers.
+  if (!parameters->options().relocatable())
+    {
+      gold_assert(segment_headers != NULL);
+      if (load_seg != NULL)
+        load_seg->add_initial_output_data(segment_headers);
+      if (phdr_seg != NULL)
+        phdr_seg->add_initial_output_data(segment_headers);
+    }
+
+  // Lay out the file header.
+  if (load_seg != NULL)
+    load_seg->add_initial_output_data(file_header);
+
+  if (this->script_options_->saw_phdrs_clause()
+      && !parameters->options().relocatable())
+    {
+      // Support use of FILEHDRS and PHDRS attachments in a PHDRS
+      // clause in a linker script.
+      Script_sections* ss = this->script_options_->script_sections();
+      ss->put_headers_in_phdrs(file_header, segment_headers);
+    }
+
+  // We set the output section indexes in set_segment_offsets and
+  // set_section_indexes.
+  *pshndx = 1;
+
+  // Set the file offsets of all the segments, and all the sections
+  // they contain.
+  off_t off;
+  if (!parameters->options().relocatable())
+    off = this->set_segment_offsets(target, load_seg, pshndx);
+  else
+    off = this->set_relocatable_section_offsets(file_header, pshndx);
+
+   // Verify that the dummy relaxation does not change anything.
+  if (is_debugging_enabled(DEBUG_RELAXATION))
+    {
+      if (pass == 0)
+	this->relaxation_debug_check_->read_sections(this->section_list_);
+      else
+	this->relaxation_debug_check_->verify_sections(this->section_list_);
+    }
+
+  *pload_seg = load_seg;
+  return off;
+}
+
 // Finalize the layout.  When this is called, we have created all the
 // output sections and all the output segments which are based on
 // input sections.  We have several things to do, and we have to do
@@ -1258,66 +1555,44 @@ Layout::finalize(const Input_objects* input_objects, Symbol_table* symtab,
       this->create_incremental_info_sections();
     }
 
-  // If there is a SECTIONS clause, put all the input sections into
-  // the required order.
-  Output_segment* load_seg;
-  if (this->script_options_->saw_sections_clause())
-    load_seg = this->set_section_addresses_from_script(symtab);
-  else if (parameters->options().relocatable())
-    load_seg = NULL;
-  else
-    load_seg = this->find_first_load_seg();
-
-  if (parameters->options().oformat_enum()
-      != General_options::OBJECT_FORMAT_ELF)
-    load_seg = NULL;
-
-  gold_assert(phdr_seg == NULL || load_seg != NULL);
-
-  // Lay out the segment headers.
-  Output_segment_headers* segment_headers;
-  if (parameters->options().relocatable())
-    segment_headers = NULL;
-  else
-    {
-      segment_headers = new Output_segment_headers(this->segment_list_);
-      if (load_seg != NULL)
-	load_seg->add_initial_output_data(segment_headers);
-      if (phdr_seg != NULL)
-	phdr_seg->add_initial_output_data(segment_headers);
-    }
+  // Create segment headers.
+  Output_segment_headers* segment_headers =
+    (parameters->options().relocatable()
+     ? NULL
+     : new Output_segment_headers(this->segment_list_));
 
   // Lay out the file header.
-  Output_file_header* file_header;
-  file_header = new Output_file_header(target, symtab, segment_headers,
-				       parameters->options().entry());
-  if (load_seg != NULL)
-    load_seg->add_initial_output_data(file_header);
+  Output_file_header* file_header
+    = new Output_file_header(target, symtab, segment_headers,
+			     parameters->options().entry());
 
   this->special_output_list_.push_back(file_header);
   if (segment_headers != NULL)
     this->special_output_list_.push_back(segment_headers);
 
-  if (this->script_options_->saw_phdrs_clause()
-      && !parameters->options().relocatable())
+  // Find approriate places for orphan output sections if we are using
+  // a linker script.
+  if (this->script_options_->saw_sections_clause())
+    this->place_orphan_sections_in_script();
+  
+  Output_segment* load_seg;
+  off_t off;
+  unsigned int shndx;
+  int pass = 0;
+
+  // Take a snapshot of the section layout as needed.
+  if (target->may_relax())
+    this->prepare_for_relaxation();
+  
+  // Run the relaxation loop to lay out sections.
+  do
     {
-      // Support use of FILEHDRS and PHDRS attachments in a PHDRS
-      // clause in a linker script.
-      Script_sections* ss = this->script_options_->script_sections();
-      ss->put_headers_in_phdrs(file_header, segment_headers);
+      off = this->relaxation_loop_body(pass, target, symtab, &load_seg,
+				       phdr_seg, segment_headers, file_header,
+				       &shndx);
+      pass++;
     }
-
-  // We set the output section indexes in set_segment_offsets and
-  // set_section_indexes.
-  unsigned int shndx = 1;
-
-  // Set the file offsets of all the segments, and all the sections
-  // they contain.
-  off_t off;
-  if (!parameters->options().relocatable())
-    off = this->set_segment_offsets(target, load_seg, &shndx);
-  else
-    off = this->set_relocatable_section_offsets(file_header, &shndx);
+  while (target->may_relax() && target->relax(pass));
 
   // Set the file offsets of all the non-data sections we've seen so
   // far which don't have to wait for the input sections.  We need
@@ -2151,6 +2426,16 @@ Layout::set_section_addresses_from_script(Symbol_table* symtab)
 {
   Script_sections* ss = this->script_options_->script_sections();
   gold_assert(ss->saw_sections_clause());
+  return this->script_options_->set_section_addresses(symtab, this);
+}
+
+// Place the orphan sections in the linker script.
+
+void
+Layout::place_orphan_sections_in_script()
+{
+  Script_sections* ss = this->script_options_->script_sections();
+  gold_assert(ss->saw_sections_clause());
 
   // Place each orphaned output section in the script.
   for (Section_list::iterator p = this->section_list_.begin();
@@ -2160,8 +2445,6 @@ Layout::set_section_addresses_from_script(Symbol_table* symtab)
       if (!(*p)->found_in_sections_clause())
 	ss->place_orphan(*p);
     }
-
-  return this->script_options_->set_section_addresses(symtab, this);
 }
 
 // Count the local symbols in the regular symbol table and the dynamic