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.

9 files changed, 1307 insertions, 175 deletions

diff --git a/gold/ChangeLog b/gold/ChangeLog
index c4c8c00..0a1f815 100644
--- a/gold/ChangeLog
+++ b/gold/ChangeLog
@@ -1,3 +1,159 @@
+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.
+
 2009-09-17  Viktor Kutuzov  <vkutuzov@accesssoftek.com>
 
 	* arm.cc (has_signed_unsigned_overflow): New function.
diff --git a/gold/debug.h b/gold/debug.h
index 8428dc8..4b9ef19 100644
--- a/gold/debug.h
+++ b/gold/debug.h
@@ -36,8 +36,10 @@ namespace gold
 const int DEBUG_TASK = 0x1;
 const int DEBUG_SCRIPT = 0x2;
 const int DEBUG_FILES = 0x4;
+const int DEBUG_RELAXATION = 0x8;
 
-const int DEBUG_ALL = DEBUG_TASK | DEBUG_SCRIPT | DEBUG_FILES;
+const int DEBUG_ALL = (DEBUG_TASK | DEBUG_SCRIPT | DEBUG_FILES
+		       | DEBUG_RELAXATION);
 
 // Convert a debug string to the appropriate enum.
 inline int
@@ -49,6 +51,7 @@ debug_string_to_enum(const char* arg)
     { "task", DEBUG_TASK },
     { "script", DEBUG_SCRIPT },
     { "files", DEBUG_FILES },
+    { "relaxation", DEBUG_RELAXATION },
     { "all", DEBUG_ALL }
   };
 
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
diff --git a/gold/layout.h b/gold/layout.h
index 0affa81..8856125 100644
--- a/gold/layout.h
+++ b/gold/layout.h
@@ -47,6 +47,8 @@ class Symbol_table;
 class Output_section_data;
 class Output_section;
 class Output_section_headers;
+class Output_segment_headers;
+class Output_file_header;
 class Output_segment;
 class Output_data;
 class Output_data_dynamic;
@@ -286,6 +288,12 @@ class Layout
  public:
   Layout(int number_of_input_files, Script_options*);
 
+  ~Layout()
+  {
+    delete this->relaxation_debug_check_;
+    delete this->segment_states_;
+  }
+
   // Given an input section SHNDX, named NAME, with data in SHDR, from
   // the object file OBJECT, return the output section where this
   // input section should go.  RELOC_SHNDX is the index of a
@@ -585,6 +593,15 @@ class Layout
   void
   attach_sections_to_segments();
 
+  // For relaxation clean up, we need to know output section data created
+  // from a linker script.
+  void
+  new_output_section_data_from_script(Output_section_data* posd)
+  {
+    if (this->record_output_section_data_from_script_)
+      this->script_output_section_data_list_.push_back(posd);
+  }
+
  private:
   Layout(const Layout&);
   Layout& operator=(const Layout&);
@@ -777,10 +794,42 @@ class Layout
   Output_segment*
   set_section_addresses_from_script(Symbol_table*);
 
+  // Find appropriate places or orphan sections in a script.
+  void
+  place_orphan_sections_in_script();
+
   // Return whether SEG1 comes before SEG2 in the output file.
   static bool
   segment_precedes(const Output_segment* seg1, const Output_segment* seg2);
 
+  // Use to save and restore segments during relaxation. 
+  typedef Unordered_map<const Output_segment*, const Output_segment*>
+    Segment_states;
+
+  // Save states of current output segments.
+  void
+  save_segments(Segment_states*);
+
+  // Restore output segment states.
+  void
+  restore_segments(const Segment_states*);
+
+  // Clean up after relaxation so that it is possible to lay out the
+  // sections and segments again.
+  void
+  clean_up_after_relaxation();
+
+  // Doing preparation work for relaxation.  This is factored out to make
+  // Layout::finalized a bit smaller and easier to read.
+  void
+  prepare_for_relaxation();
+
+  // Main body of the relaxation loop, which lays out the section.
+  off_t
+  relaxation_loop_body(int, Target*, Symbol_table*, Output_segment**,
+		       Output_segment*, Output_segment_headers*,
+		       Output_file_header*, unsigned int*);
+
   // A mapping used for kept comdats/.gnu.linkonce group signatures.
   typedef Unordered_map<std::string, Kept_section> Signatures;
 
@@ -807,6 +856,47 @@ class Layout
     { return Layout::segment_precedes(seg1, seg2); }
   };
 
+  typedef std::vector<Output_section_data*> Output_section_data_list;
+
+  // Debug checker class.
+  class Relaxation_debug_check
+  {
+   public:
+    Relaxation_debug_check()
+      : section_infos_()
+    { }
+ 
+    // Check that sections and special data are in reset states.
+    void
+    check_output_data_for_reset_values(const Layout::Section_list&,
+				       const Layout::Data_list&);
+  
+    // Record information of a section list.
+    void
+    read_sections(const Layout::Section_list&);
+
+    // Verify a section list with recorded information.
+    void
+    verify_sections(const Layout::Section_list&);
+ 
+   private:
+    // Information we care about a section.
+    struct Section_info
+    {
+      // Output section described by this.
+      Output_section* output_section;
+      // Load address.
+      uint64_t address;
+      // Data size.
+      off_t data_size;
+      // File offset.
+      off_t offset;
+    };
+
+    // Section information.
+    std::vector<Section_info> section_infos_;
+  };
+
   // The number of input files, for sizing tables.
   int number_of_input_files_;
   // Information set by scripts or by command line options.
@@ -889,6 +979,14 @@ class Layout
   // In incremental build, holds information check the inputs and build the
   // .gnu_incremental_inputs section.
   Incremental_inputs* incremental_inputs_;
+  // Whether we record output section data created in script
+  bool record_output_section_data_from_script_;
+  // List of output data that needs to be removed at relexation clean up.
+  Output_section_data_list script_output_section_data_list_;
+  // Structure to save segment states before entering the relaxation loop.
+  Segment_states* segment_states_;
+  // A relaxation debug checker.  We only create one when in debugging mode.
+  Relaxation_debug_check* relaxation_debug_check_;
 };
 
 // This task handles writing out data in output sections which is not
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.
diff --git a/gold/output.h b/gold/output.h
index 7bd0cf3..6de6e69 100644
--- a/gold/output.h
+++ b/gold/output.h
@@ -54,7 +54,7 @@ class Output_data
   explicit Output_data()
     : address_(0), data_size_(0), offset_(-1),
       is_address_valid_(false), is_data_size_valid_(false),
-      is_offset_valid_(false),
+      is_offset_valid_(false), is_data_size_fixed_(false),
       dynamic_reloc_count_(0)
   { }
 
@@ -80,6 +80,11 @@ class Output_data
     return this->data_size_;
   }
 
+  // Return true if data size is fixed.
+  bool
+  is_data_size_fixed() const
+  { return this->is_data_size_fixed_; }
+  
   // Return the file offset.  This is only valid after
   // Layout::finalize is finished.  For some non-allocated sections,
   // it may not be valid until near the end of the link.
@@ -97,10 +102,17 @@ class Output_data
   {
     this->is_address_valid_ = false;
     this->is_offset_valid_ = false;
-    this->is_data_size_valid_ = false;
+    if (!this->is_data_size_fixed_)
+      this->is_data_size_valid_ = false;
     this->do_reset_address_and_file_offset();
   }
 
+  // Return true if address and file offset already have reset values. In
+  // other words, calling reset_address_and_file_offset will not change them.
+  bool
+  address_and_file_offset_have_reset_values() const
+  { return this->do_address_and_file_offset_have_reset_values(); }
+
   // Return the required alignment.
   uint64_t
   addralign() const
@@ -311,6 +323,14 @@ class Output_data
   do_reset_address_and_file_offset()
   { }
 
+  // Return true if address and file offset already have reset values. In
+  // other words, calling reset_address_and_file_offset will not change them.
+  // A child class overriding do_reset_address_and_file_offset may need to
+  // also override this.
+  virtual bool
+  do_address_and_file_offset_have_reset_values() const
+  { return !this->is_address_valid_ && !this->is_offset_valid_; }
+
   // Set the TLS offset.  Called only for SHT_TLS sections.
   virtual void
   do_set_tls_offset(uint64_t)
@@ -341,11 +361,21 @@ class Output_data
   void
   set_data_size(off_t data_size)
   {
-    gold_assert(!this->is_data_size_valid_);
+    gold_assert(!this->is_data_size_valid_
+		&& !this->is_data_size_fixed_);
     this->data_size_ = data_size;
     this->is_data_size_valid_ = true;
   }
 
+  // Fix the data size.  Once it is fixed, it cannot be changed
+  // and the data size remains always valid. 
+  void
+  fix_data_size()
+  {
+    gold_assert(this->is_data_size_valid_);
+    this->is_data_size_fixed_ = true;
+  }
+
   // Get the current data size--this is for the convenience of
   // sections which build up their size over time.
   off_t
@@ -390,6 +420,8 @@ class Output_data
   bool is_data_size_valid_;
   // Whether offset_ is valid.
   bool is_offset_valid_;
+  // Whether data size is fixed.
+  bool is_data_size_fixed_;
   // Count of dynamic relocations applied to this section.
   unsigned int dynamic_reloc_count_;
 };
@@ -421,12 +453,21 @@ class Output_section_headers : public Output_data
   do_print_to_mapfile(Mapfile* mapfile) const
   { mapfile->print_output_data(this, _("** section headers")); }
 
+  // Set final data size.
+  void
+  set_final_data_size()
+  { this->set_data_size(this->do_size()); }
+
  private:
   // Write the data to the file with the right size and endianness.
   template<int size, bool big_endian>
   void
   do_sized_write(Output_file*);
 
+  // Compute data size.
+  off_t
+  do_size() const;
+
   const Layout* layout_;
   const Layout::Segment_list* segment_list_;
   const Layout::Section_list* section_list_;
@@ -457,12 +498,21 @@ class Output_segment_headers : public Output_data
   do_print_to_mapfile(Mapfile* mapfile) const
   { mapfile->print_output_data(this, _("** segment headers")); }
 
+  // Set final data size.
+  void
+  set_final_data_size()
+  { this->set_data_size(this->do_size()); }
+
  private:
   // Write the data to the file with the right size and endianness.
   template<int size, bool big_endian>
   void
   do_sized_write(Output_file*);
 
+  // Compute the current size.
+  off_t
+  do_size() const;
+
   const Layout::Segment_list& segment_list_;
 };
 
@@ -496,6 +546,11 @@ class Output_file_header : public Output_data
   do_print_to_mapfile(Mapfile* mapfile) const
   { mapfile->print_output_data(this, _("** file header")); }
 
+  // Set final data size.
+  void
+  set_final_data_size(void)
+  { this->set_data_size(this->do_size()); }
+
  private:
   // Write the data to the file with the right size and endianness.
   template<int size, bool big_endian>
@@ -507,6 +562,10 @@ class Output_file_header : public Output_data
   typename elfcpp::Elf_types<size>::Elf_Addr
   entry();
 
+  // Compute the current data size.
+  off_t
+  do_size() const;
+
   const Target* target_;
   const Symbol_table* symtab_;
   const Output_segment_headers* segment_header_;
@@ -523,9 +582,14 @@ class Output_file_header : public Output_data
 class Output_section_data : public Output_data
 {
  public:
-  Output_section_data(off_t data_size, uint64_t addralign)
+  Output_section_data(off_t data_size, uint64_t addralign,
+		      bool is_data_size_fixed)
     : Output_data(), output_section_(NULL), addralign_(addralign)
-  { this->set_data_size(data_size); }
+  {
+    this->set_data_size(data_size);
+    if (is_data_size_fixed)
+      this->fix_data_size();
+  }
 
   Output_section_data(uint64_t addralign)
     : Output_data(), output_section_(NULL), addralign_(addralign)
@@ -675,15 +739,15 @@ class Output_data_const : public Output_section_data
 {
  public:
   Output_data_const(const std::string& data, uint64_t addralign)
-    : Output_section_data(data.size(), addralign), data_(data)
+    : Output_section_data(data.size(), addralign, true), data_(data)
   { }
 
   Output_data_const(const char* p, off_t len, uint64_t addralign)
-    : Output_section_data(len, addralign), data_(p, len)
+    : Output_section_data(len, addralign, true), data_(p, len)
   { }
 
   Output_data_const(const unsigned char* p, off_t len, uint64_t addralign)
-    : Output_section_data(len, addralign),
+    : Output_section_data(len, addralign, true),
       data_(reinterpret_cast<const char*>(p), len)
   { }
 
@@ -714,7 +778,7 @@ class Output_data_const_buffer : public Output_section_data
  public:
   Output_data_const_buffer(const unsigned char* p, off_t len,
 			   uint64_t addralign, const char* map_name)
-    : Output_section_data(len, addralign),
+    : Output_section_data(len, addralign, true),
       p_(p), map_name_(map_name)
   { }
 
@@ -749,7 +813,7 @@ class Output_data_fixed_space : public Output_section_data
  public:
   Output_data_fixed_space(off_t data_size, uint64_t addralign,
 			  const char* map_name)
-    : Output_section_data(data_size, addralign),
+    : Output_section_data(data_size, addralign, true),
       map_name_(map_name)
   { }
 
@@ -812,7 +876,7 @@ class Output_data_zero_fill : public Output_section_data
 {
  public:
   Output_data_zero_fill(off_t data_size, uint64_t addralign)
-    : Output_section_data(data_size, addralign)
+    : Output_section_data(data_size, addralign, true)
   { }
 
  protected:
@@ -1531,6 +1595,11 @@ class Output_data_group : public Output_section_data
   do_print_to_mapfile(Mapfile* mapfile) const
   { mapfile->print_output_data(this, _("** group")); }
 
+  // Set final data size.
+  void
+  set_final_data_size()
+  { this->set_data_size((this->input_shndxes_.size() + 1) * 4); }
+
  private:
   // The input object.
   Sized_relobj<size, big_endian>* relobj_;
@@ -1814,6 +1883,11 @@ class Output_data_dynamic : public Output_section_data
       : tag_(tag), offset_(DYNAMIC_STRING)
     { this->u_.str = str; }
 
+    // Return the tag of this entry.
+    elfcpp::DT
+    tag() const
+    { return this->tag_; }
+
     // Write the dynamic entry to an output view.
     template<int size, bool big_endian>
     void
@@ -1880,7 +1954,7 @@ class Output_symtab_xindex : public Output_section_data
 {
  public:
   Output_symtab_xindex(size_t symcount)
-    : Output_section_data(symcount * 4, 4),
+    : Output_section_data(symcount * 4, 4, true),
       entries_()
   { }
 
@@ -1912,6 +1986,33 @@ class Output_symtab_xindex : public Output_section_data
   Xindex_entries entries_;
 };
 
+// A relaxed input section.
+class Output_relaxed_input_section : public Output_section_data
+{
+ public:
+  // We would like to call relobj->section_addralign(shndx) to get the
+  // alignment but we do not want the constructor to fail.  So callers
+  // 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)
+  { }
+ 
+  // Return the Relobj of this relaxed input section.
+  Relobj*
+  relobj() const
+  { return this->relobj_; }
+ 
+  // Return the section index of this relaxed input section.
+  unsigned int
+  shndx() const
+  { return this->shndx_; }
+
+ private:
+  Relobj* relobj_;
+  unsigned int shndx_;
+};
+
 // An output section.  We don't expect to have too many output
 // sections, so we don't bother to do a template on the size.
 
@@ -2310,6 +2411,69 @@ class Output_section : public Output_data
 
   // The next few calls are for linker script support.
 
+  // We need to export the input sections to linker scripts.  Previously
+  // we export a pair of Relobj pointer and section index.  We now need to
+  // handle relaxed input sections as well.  So we use this class.
+  class Simple_input_section
+  {
+   private:
+    static const unsigned int invalid_shndx = static_cast<unsigned int>(-1);
+
+   public:
+    Simple_input_section(Relobj *relobj, unsigned int shndx)
+      : shndx_(shndx)
+    {
+      gold_assert(shndx != invalid_shndx);
+      this->u_.relobj = relobj;
+    }
+ 
+    Simple_input_section(Output_relaxed_input_section* section)
+      : shndx_(invalid_shndx)
+    { this->u_.relaxed_input_section = section; }
+
+    // Whether this is a relaxed section.
+    bool
+    is_relaxed_input_section() const
+    { return this->shndx_ == invalid_shndx; }
+
+    // Return object of an input section.
+    Relobj*
+    relobj() const
+    {
+      return ((this->shndx_ != invalid_shndx)
+	      ? this->u_.relobj
+	      : this->u_.relaxed_input_section->relobj());
+    }
+
+    // Return index of an input section.
+    unsigned int
+    shndx() const
+    {
+      return ((this->shndx_ != invalid_shndx)
+	      ? this->shndx_
+	      : this->u_.relaxed_input_section->shndx());
+    }
+
+    // Return the Output_relaxed_input_section object of a relaxed section.
+    Output_relaxed_input_section*
+    relaxed_input_section() const
+    {
+      gold_assert(this->shndx_ == invalid_shndx);
+      return this->u_.relaxed_input_section;
+    }
+
+   private:
+    // Pointer to either an Relobj or an Output_relaxed_input_section.
+    union
+    {
+      Relobj* relobj;
+      Output_relaxed_input_section* relaxed_input_section;
+    } u_;
+    // Section index for an non-relaxed section or invalid_shndx for
+    // a relaxed section.
+    unsigned int shndx_;
+  };
+ 
   // Store the list of input sections for this Output_section into the
   // list passed in.  This removes the input sections, leaving only
   // any Output_section_data elements.  This returns the size of those
@@ -2318,11 +2482,11 @@ class Output_section : public Output_data
   // any spaces between the remaining Output_section_data elements.
   uint64_t
   get_input_sections(uint64_t address, const std::string& fill,
-		     std::list<std::pair<Relobj*, unsigned int > >*);
+		     std::list<Simple_input_section>*);
 
   // Add an input section from a script.
   void
-  add_input_section_for_script(Relobj* object, unsigned int shndx,
+  add_input_section_for_script(const Simple_input_section& input_section,
 			       off_t data_size, uint64_t addralign);
 
   // Set the current size of the output section.
@@ -2337,6 +2501,15 @@ class Output_section : public Output_data
 
   // End of linker script support.
 
+  // Save states before doing section layout.
+  // This is used for relaxation.
+  void
+  save_states();
+
+  // Restore states prior to section layout.
+  void
+  restore_states();
+
   // Print merge statistics to stderr.
   void
   print_merge_stats();
@@ -2374,6 +2547,11 @@ class Output_section : public Output_data
   void
   do_reset_address_and_file_offset();
 
+  // Return true if address and file offset already have reset values. In
+  // other words, calling reset_address_and_file_offset will not change them.
+  bool
+  do_address_and_file_offset_have_reset_values() const;
+
   // Write the data to the file.  For a typical Output_section, this
   // does nothing: the data is written out by calling Object::Relocate
   // on each input object.  But if there are any Output_section_data
@@ -2476,7 +2654,8 @@ class Output_section : public Output_data
     {
       gold_assert(shndx != OUTPUT_SECTION_CODE
 		  && shndx != MERGE_DATA_SECTION_CODE
-		  && shndx != MERGE_STRING_SECTION_CODE);
+		  && shndx != MERGE_STRING_SECTION_CODE
+		  && shndx != RELAXED_INPUT_SECTION_CODE);
       this->u1_.data_size = data_size;
       this->u2_.object = object;
     }
@@ -2500,6 +2679,14 @@ class Output_section : public Output_data
       this->u2_.posd = posd;
     }
 
+    // For a relaxed input section.
+    Input_section(Output_relaxed_input_section *psection)
+      : shndx_(RELAXED_INPUT_SECTION_CODE), p2align_(0)
+    {
+      this->u1_.data_size = 0;
+      this->u2_.poris = psection;
+    }
+
     // The required alignment.
     uint64_t
     addralign() const
@@ -2521,7 +2708,8 @@ class Output_section : public Output_data
     {
       return (this->shndx_ != OUTPUT_SECTION_CODE
 	      && this->shndx_ != MERGE_DATA_SECTION_CODE
-	      && this->shndx_ != MERGE_STRING_SECTION_CODE);
+	      && this->shndx_ != MERGE_STRING_SECTION_CODE
+	      && this->shndx_ != RELAXED_INPUT_SECTION_CODE);
     }
 
     // Return whether this is a merge section which matches the
@@ -2537,6 +2725,18 @@ class Output_section : public Output_data
               && this->addralign() == addralign);
     }
 
+    // Return whether this is a relaxed input section.
+    bool
+    is_relaxed_input_section() const
+    { return this->shndx_ == RELAXED_INPUT_SECTION_CODE; }
+
+    // Return whether this is a generic Output_section_data.
+    bool
+    is_output_section_data() const
+    {
+      return this->shndx_ == OUTPUT_SECTION_CODE;
+    }
+
     // Return the object for an input section.
     Relobj*
     relobj() const
@@ -2553,12 +2753,31 @@ class Output_section : public Output_data
       return this->shndx_;
     }
 
+    // For non-input-sections, return the associated Output_section_data
+    // object.
+    Output_section_data*
+    output_section_data() const
+    {
+      gold_assert(!this->is_input_section());
+      return this->u2_.posd;
+    }
+ 
+    // Return the Output_relaxed_input_section object.
+    Output_relaxed_input_section*
+    relaxed_input_section() const
+    {
+      gold_assert(this->is_relaxed_input_section());
+      return this->u2_.poris;
+    }
+
     // Set the output section.
     void
     set_output_section(Output_section* os)
     {
       gold_assert(!this->is_input_section());
-      this->u2_.posd->set_output_section(os);
+      Output_section_data *posd = 
+        this->is_relaxed_input_section() ? this->u2_.poris : this->u2_.posd;
+      posd->set_output_section(os);
     }
 
     // Set the address and file offset.  This is called during
@@ -2636,7 +2855,9 @@ class Output_section : public Output_data
       MERGE_DATA_SECTION_CODE = -2U,
       // An Output_section_data for an SHF_MERGE section with
       // SHF_STRINGS set.
-      MERGE_STRING_SECTION_CODE = -3U
+      MERGE_STRING_SECTION_CODE = -3U,
+      // An Output_section_data for a relaxed input section.
+      RELAXED_INPUT_SECTION_CODE = -4U
     };
 
     // For an ordinary input section, this is the section index in the
@@ -2650,8 +2871,8 @@ class Output_section : public Output_data
     {
       // For an ordinary input section, the section size.
       off_t data_size;
-      // For OUTPUT_SECTION_CODE, this is not used.  For
-      // MERGE_DATA_SECTION_CODE or MERGE_STRING_SECTION_CODE, the
+      // For OUTPUT_SECTION_CODE or RELAXED_INPUT_SECTION_CODE, this is not
+      // used.  For MERGE_DATA_SECTION_CODE or MERGE_STRING_SECTION_CODE, the
       // entity size.
       uint64_t entsize;
     } u1_;
@@ -2663,11 +2884,97 @@ class Output_section : public Output_data
       // For OUTPUT_SECTION_CODE or MERGE_DATA_SECTION_CODE or
       // MERGE_STRING_SECTION_CODE, the data.
       Output_section_data* posd;
+      // For RELAXED_INPUT_SECTION_CODE, the data.
+      Output_relaxed_input_section* poris;
     } u2_;
   };
 
   typedef std::vector<Input_section> Input_section_list;
 
+  // We only save enough information to undo the effects of section layout.
+  class Checkpoint_output_section
+  {
+   public:
+    Checkpoint_output_section(uint64_t addralign, elfcpp::Elf_Xword flags,
+			      const Input_section_list& input_sections,
+			      off_t first_input_offset,
+			      bool attached_input_sections_are_sorted)
+      : addralign_(addralign), flags_(flags),
+	input_sections_(input_sections),
+	input_sections_size_(input_sections_.size()),
+	input_sections_copy_(), first_input_offset_(first_input_offset),
+	attached_input_sections_are_sorted_(attached_input_sections_are_sorted)
+    { }
+
+    virtual
+    ~Checkpoint_output_section()
+    { }
+
+    // Return the address alignment.
+    uint64_t
+    addralign() const
+    { return this->addralign_; }
+
+    // Return the section flags.
+    elfcpp::Elf_Xword
+    flags() const
+    { return this->flags_; }
+
+    // Return a reference to the input section list copy.
+    const Input_section_list&
+    input_sections() const
+    { return this->input_sections_copy_; }
+
+    // Return the size of input_sections at the time when checkpoint is
+    // taken.
+    size_t
+    input_sections_size() const
+    { return this->input_sections_size_; }
+
+    // Whether input sections are copied.
+    bool
+    input_sections_saved() const
+    { return this->input_sections_copy_.size() == this->input_sections_size_; }
+
+    off_t
+    first_input_offset() const
+    { return this->first_input_offset_; }
+
+    bool
+    attached_input_sections_are_sorted() const
+    { return this->attached_input_sections_are_sorted_; }
+
+    // Save input sections.
+    void
+    save_input_sections()
+    {
+      this->input_sections_copy_.reserve(this->input_sections_size_);
+      this->input_sections_copy_.clear();
+      Input_section_list::const_iterator p = this->input_sections_.begin();
+      gold_assert(this->input_sections_size_ >= this->input_sections_.size());
+      for(size_t i = 0; i < this->input_sections_size_ ; i++, ++p)
+	this->input_sections_copy_.push_back(*p);
+    }
+
+   private:
+    // The section alignment.
+    uint64_t addralign_;
+    // The section flags.
+    elfcpp::Elf_Xword flags_;
+    // Reference to the input sections to be checkpointed.
+    const Input_section_list& input_sections_;
+    // Size of the checkpointed portion of input_sections_;
+    size_t input_sections_size_;
+    // Copy of input sections.
+    Input_section_list input_sections_copy_;
+    // The offset of the first entry in input_sections_.
+    off_t first_input_offset_;
+    // True if the input sections attached to this output section have
+    // already been sorted.
+    bool attached_input_sections_are_sorted_;
+  };
+
+ private:
   // This class is used to sort the input sections.
   class Input_section_sort_entry;
 
@@ -2729,6 +3036,10 @@ 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();
@@ -2836,11 +3147,19 @@ class Output_section : public Output_data
   // For SHT_TLS sections, the offset of this section relative to the base
   // of the TLS segment.
   uint64_t tls_offset_;
+  // Saved checkpoint.
+  Checkpoint_output_section* checkpoint_;
 };
 
 // An output segment.  PT_LOAD segments are built from collections of
 // output sections.  Other segments typically point within PT_LOAD
 // segments, and are built directly as needed.
+//
+// NOTE: We want to use the copy constructor for this class.  During
+// relaxation, we may try built the segments multiple times.  We do
+// that by copying the original segment list before lay-out, doing
+// a trial lay-out and roll-back to the saved copied if we need to
+// to the lay-out again.
 
 class Output_segment
 {
@@ -2998,9 +3317,6 @@ class Output_segment
   print_sections_to_mapfile(Mapfile*) const;
 
  private:
-  Output_segment(const Output_segment&);
-  Output_segment& operator=(const Output_segment&);
-
   typedef std::list<Output_data*> Output_data_list;
 
   // Find the maximum alignment in an Output_data_list.
@@ -3043,6 +3359,9 @@ class Output_segment
   void
   print_section_list_to_mapfile(Mapfile*, const Output_data_list*) const;
 
+  // NOTE: We want to use the copy constructor.  Currently, shallow copy
+  // works for us so we do not need to write our own copy constructor.
+  
   // The list of output data with contents attached to this segment.
   Output_data_list output_data_;
   // The list of output data without contents attached to this segment.
diff --git a/gold/script-sections.cc b/gold/script-sections.cc
index 7396b3b..d6e2b72 100644
--- a/gold/script-sections.cc
+++ b/gold/script-sections.cc
@@ -524,7 +524,7 @@ class Output_section_element
 {
  public:
   // A list of input sections.
-  typedef std::list<std::pair<Relobj*, unsigned int> > Input_section_list;
+  typedef std::list<Output_section::Simple_input_section> Input_section_list;
 
   Output_section_element()
   { }
@@ -701,6 +701,7 @@ Output_section_element_dot_assignment::set_section_addresses(
 	  posd = new Output_data_const(this_fill, 0);
 	}
       output_section->add_output_section_data(posd);
+      layout->new_output_section_data_from_script(posd);
     }
   *dot_value = next_dot;
 }
@@ -736,7 +737,7 @@ class Output_data_expression : public Output_section_data
   Output_data_expression(int size, bool is_signed, Expression* val,
 			 const Symbol_table* symtab, const Layout* layout,
 			 uint64_t dot_value, Output_section* dot_section)
-    : Output_section_data(size, 0),
+    : Output_section_data(size, 0, true),
       is_signed_(is_signed), val_(val), symtab_(symtab),
       layout_(layout), dot_value_(dot_value), dot_section_(dot_section)
   { }
@@ -877,13 +878,11 @@ Output_section_element_data::set_section_addresses(
     Input_section_list*)
 {
   gold_assert(os != NULL);
-  os->add_output_section_data(new Output_data_expression(this->size_,
-							 this->is_signed_,
-							 this->val_,
-							 symtab,
-							 layout,
-							 *dot_value,
-							 *dot_section));
+  Output_data_expression* expression =
+    new Output_data_expression(this->size_, this->is_signed_, this->val_,
+			       symtab, layout, *dot_value, *dot_section);
+  os->add_output_section_data(expression);
+  layout->new_output_section_data_from_script(expression);
   *dot_value += this->size_;
 }
 
@@ -1169,13 +1168,68 @@ Output_section_element_input::match_name(const char* file_name,
 
 // Information we use to sort the input sections.
 
-struct Input_section_info
+class Input_section_info
 {
-  Relobj* relobj;
-  unsigned int shndx;
-  std::string section_name;
-  uint64_t size;
-  uint64_t addralign;
+ public:
+  Input_section_info(const Output_section::Simple_input_section& input_section)
+    : input_section_(input_section), section_name_(),
+      size_(0), addralign_(1)
+  { }
+
+  // Return the simple input section.
+  const Output_section::Simple_input_section&
+  input_section() const
+  { return this->input_section_; }
+
+  // Return the object.
+  Relobj*
+  relobj() const
+  { return this->input_section_.relobj(); }
+
+  // Return the section index.
+  unsigned int
+  shndx()
+  { return this->input_section_.shndx(); }
+
+  // Return the section name.
+  const std::string&
+  section_name() const
+  { return this->section_name_; }
+
+  // Set the section name.
+  void
+  set_section_name(const std::string name)
+  { this->section_name_ = name; }
+
+  // Return the section size.
+  uint64_t
+  size() const
+  { return this->size_; }
+
+  // Set the section size.
+  void
+  set_size(uint64_t size)
+  { this->size_ = size; }
+
+  // Return the address alignment.
+  uint64_t
+  addralign() const
+  { return this->addralign_; }
+
+  // Set the address alignment.
+  void
+  set_addralign(uint64_t addralign)
+  { this->addralign_ = addralign; }
+
+ private:
+  // Input section, can be a relaxed section.
+  Output_section::Simple_input_section input_section_;
+  // Name of the section. 
+  std::string section_name_;
+  // Section size.
+  uint64_t size_;
+  // Address alignment.
+  uint64_t addralign_;
 };
 
 // A class to sort the input sections.
@@ -1202,22 +1256,22 @@ Input_section_sorter::operator()(const Input_section_info& isi1,
   if (this->section_sort_ == SORT_WILDCARD_BY_NAME
       || this->section_sort_ == SORT_WILDCARD_BY_NAME_BY_ALIGNMENT
       || (this->section_sort_ == SORT_WILDCARD_BY_ALIGNMENT_BY_NAME
-	  && isi1.addralign == isi2.addralign))
+	  && isi1.addralign() == isi2.addralign()))
     {
-      if (isi1.section_name != isi2.section_name)
-	return isi1.section_name < isi2.section_name;
+      if (isi1.section_name() != isi2.section_name())
+	return isi1.section_name() < isi2.section_name();
     }
   if (this->section_sort_ == SORT_WILDCARD_BY_ALIGNMENT
       || this->section_sort_ == SORT_WILDCARD_BY_NAME_BY_ALIGNMENT
       || this->section_sort_ == SORT_WILDCARD_BY_ALIGNMENT_BY_NAME)
     {
-      if (isi1.addralign != isi2.addralign)
-	return isi1.addralign < isi2.addralign;
+      if (isi1.addralign() != isi2.addralign())
+	return isi1.addralign() < isi2.addralign();
     }
   if (this->filename_sort_ == SORT_WILDCARD_BY_NAME)
     {
-      if (isi1.relobj->name() != isi2.relobj->name())
-	return isi1.relobj->name() < isi2.relobj->name();
+      if (isi1.relobj()->name() != isi2.relobj()->name())
+	return (isi1.relobj()->name() < isi2.relobj()->name());
     }
 
   // Otherwise we leave them in the same order.
@@ -1231,7 +1285,7 @@ Input_section_sorter::operator()(const Input_section_info& isi1,
 void
 Output_section_element_input::set_section_addresses(
     Symbol_table*,
-    Layout*,
+    Layout* layout,
     Output_section* output_section,
     uint64_t subalign,
     uint64_t* dot_value,
@@ -1255,25 +1309,29 @@ Output_section_element_input::set_section_addresses(
   Input_section_list::iterator p = input_sections->begin();
   while (p != input_sections->end())
     {
+      Relobj* relobj = p->relobj();
+      unsigned int shndx = p->shndx();      
+      Input_section_info isi(*p);
+
       // Calling section_name and section_addralign is not very
       // efficient.
-      Input_section_info isi;
-      isi.relobj = p->first;
-      isi.shndx = p->second;
 
       // Lock the object so that we can get information about the
       // section.  This is OK since we know we are single-threaded
       // here.
       {
 	const Task* task = reinterpret_cast<const Task*>(-1);
-	Task_lock_obj<Object> tl(task, p->first);
-
-	isi.section_name = p->first->section_name(p->second);
-	isi.size = p->first->section_size(p->second);
-	isi.addralign = p->first->section_addralign(p->second);
+	Task_lock_obj<Object> tl(task, relobj);
+
+	isi.set_section_name(relobj->section_name(shndx));
+	if (p->is_relaxed_input_section())
+	  isi.set_size(p->relaxed_input_section()->data_size());
+	else
+	  isi.set_size(relobj->section_size(shndx));
+	isi.set_addralign(relobj->section_addralign(shndx));
       }
 
-      if (!this->match_file_name(isi.relobj->name().c_str()))
+      if (!this->match_file_name(relobj->name().c_str()))
 	++p;
       else if (this->input_section_patterns_.empty())
 	{
@@ -1287,7 +1345,7 @@ Output_section_element_input::set_section_addresses(
 	    {
 	      const Input_section_pattern&
 		isp(this->input_section_patterns_[i]);
-	      if (match(isi.section_name.c_str(), isp.pattern.c_str(),
+	      if (match(isi.section_name().c_str(), isp.pattern.c_str(),
 			isp.pattern_is_wildcard))
 		break;
 	    }
@@ -1327,7 +1385,7 @@ Output_section_element_input::set_section_addresses(
 	   p != matching_sections[i].end();
 	   ++p)
 	{
-	  uint64_t this_subalign = p->addralign;
+	  uint64_t this_subalign = p->addralign();
 	  if (this_subalign < subalign)
 	    this_subalign = subalign;
 
@@ -1340,14 +1398,14 @@ Output_section_element_input::set_section_addresses(
 	      std::string this_fill = this->get_fill_string(fill, length);
 	      Output_section_data* posd = new Output_data_const(this_fill, 0);
 	      output_section->add_output_section_data(posd);
+	      layout->new_output_section_data_from_script(posd);
 	    }
 
-	  output_section->add_input_section_for_script(p->relobj,
-						       p->shndx,
-						       p->size,
+	  output_section->add_input_section_for_script(p->input_section(),
+						       p->size(),
 						       this_subalign);
 
-	  *dot_value = address + p->size;
+	  *dot_value = address + p->size();
 	}
     }
 
@@ -2202,7 +2260,7 @@ Orphan_output_section::set_section_addresses(Symbol_table*, Layout*,
 					     uint64_t* dot_value,
                                              uint64_t* load_address)
 {
-  typedef std::list<std::pair<Relobj*, unsigned int> > Input_section_list;
+  typedef std::list<Output_section::Simple_input_section> Input_section_list;
 
   bool have_load_address = *load_address != *dot_value;
 
@@ -2231,14 +2289,16 @@ Orphan_output_section::set_section_addresses(Symbol_table*, Layout*,
       // object.
       {
 	const Task* task = reinterpret_cast<const Task*>(-1);
-	Task_lock_obj<Object> tl(task, p->first);
-	addralign = p->first->section_addralign(p->second);
-	size = p->first->section_size(p->second);
+	Task_lock_obj<Object> tl(task, p->relobj());
+	addralign = p->relobj()->section_addralign(p->shndx());
+	if (p->is_relaxed_input_section())
+	  size = p->relaxed_input_section()->data_size();
+	else
+	  size = p->relobj()->section_size(p->shndx());
       }
 
       address = align_address(address, addralign);
-      this->os_->add_input_section_for_script(p->first, p->second, size,
-                                              addralign);
+      this->os_->add_input_section_for_script(*p, size, addralign);
       address += size;
     }
 
@@ -2333,6 +2393,11 @@ class Phdrs_element
   segment()
   { return this->segment_; }
 
+  // Release the segment.
+  void
+  release_segment()
+  { this->segment_ = NULL; }
+
   // Set the segment flags if appropriate.
   void
   set_flags_if_valid()
@@ -3165,12 +3230,15 @@ Script_sections::attach_sections_using_phdrs_clause(Layout* layout)
   // Output sections in the script which do not list segments are
   // attached to the same set of segments as the immediately preceding
   // output section.
+  
   String_list* phdr_names = NULL;
+  bool load_segments_only = false;
   for (Sections_elements::const_iterator p = this->sections_elements_->begin();
        p != this->sections_elements_->end();
        ++p)
     {
       bool orphan;
+      String_list* old_phdr_names = phdr_names;
       Output_section* os = (*p)->allocate_to_segment(&phdr_names, &orphan);
       if (os == NULL)
 	continue;
@@ -3181,6 +3249,11 @@ Script_sections::attach_sections_using_phdrs_clause(Layout* layout)
 	  continue;
 	}
 
+      // We see a list of segments names.  Disable PT_LOAD segment only
+      // filtering.
+      if (old_phdr_names != phdr_names)
+	load_segments_only = false;
+		
       // If this is an orphan section--one that was not explicitly
       // mentioned in the linker script--then it should not inherit
       // any segment type other than PT_LOAD.  Otherwise, e.g., the
@@ -3189,17 +3262,9 @@ Script_sections::attach_sections_using_phdrs_clause(Layout* layout)
       // we trust the linker script.
       if (orphan)
 	{
-	  String_list::iterator q = phdr_names->begin();
-	  while (q != phdr_names->end())
-	    {
-	      Name_to_segment::const_iterator r = name_to_segment.find(*q);
-	      // We give errors about unknown segments below.
-	      if (r == name_to_segment.end()
-		  || r->second->type() == elfcpp::PT_LOAD)
-		++q;
-	      else
-		q = phdr_names->erase(q);
-	    }
+	  // Enable PT_LOAD segments only filtering until we see another
+	  // list of segment names.
+	  load_segments_only = true;
 	}
 
       bool in_load_segment = false;
@@ -3212,6 +3277,10 @@ Script_sections::attach_sections_using_phdrs_clause(Layout* layout)
 	    gold_error(_("no segment %s"), q->c_str());
 	  else
 	    {
+	      if (load_segments_only
+		  && r->second->type() != elfcpp::PT_LOAD)
+		continue;
+
 	      elfcpp::Elf_Word seg_flags =
 		Layout::section_flags_to_segment(os->flags());
 	      r->second->add_output_section(os, seg_flags);
@@ -3366,6 +3435,21 @@ Script_sections::get_output_section_info(const char* name, uint64_t* address,
   return false;
 }
 
+// Release all Output_segments.  This remove all pointers to all
+// Output_segments.
+
+void
+Script_sections::release_segments()
+{
+  if (this->saw_phdrs_clause())
+    {
+      for (Phdrs_elements::const_iterator p = this->phdrs_elements_->begin();
+	   p != this->phdrs_elements_->end();
+	   ++p)
+	(*p)->release_segment();
+    }
+}
+
 // Print the SECTIONS clause to F for debugging.
 
 void
diff --git a/gold/script-sections.h b/gold/script-sections.h
index 390c350..b326eae 100644
--- a/gold/script-sections.h
+++ b/gold/script-sections.h
@@ -187,6 +187,10 @@ class Script_sections
                           uint64_t* load_address, uint64_t* addralign,
                           uint64_t* size) const;
 
+  // Release all Output_segments.  This is used in relaxation.
+  void
+  release_segments();
+
   // Print the contents to the FILE.  This is for debugging.
   void
   print(FILE*) const;
diff --git a/gold/target.h b/gold/target.h
index c9b07a8..ac59fb2 100644
--- a/gold/target.h
+++ b/gold/target.h
@@ -36,6 +36,7 @@
 #include "elfcpp.h"
 #include "options.h"
 #include "parameters.h"
+#include "debug.h"
 
 namespace gold
 {
@@ -223,6 +224,28 @@ class Target
 		  off_t offset, const elfcpp::Ehdr<size, big_endian>& ehdr)
   { return this->do_make_elf_object(name, input_file, offset, ehdr); }
 
+  // Return true if target wants to perform relaxation.
+  bool
+  may_relax() const
+  {
+    // Run the dummy relaxation pass twice if relaxation debugging is enabled.
+    if (is_debugging_enabled(DEBUG_RELAXATION))
+      return true;
+
+     return this->do_may_relax();
+  }
+
+  // Perform a relaxation pass.  Return true if layout may be changed.
+  bool
+  relax(int pass)
+  {
+    // Run the dummy relaxation pass twice if relaxation debugging is enabled.
+    if (is_debugging_enabled(DEBUG_RELAXATION))
+      return pass < 2;
+
+    return this->do_relax(pass);
+  } 
+
  protected:
   // This struct holds the constant information for a child class.  We
   // use a struct to avoid the overhead of virtual function calls for
@@ -339,6 +362,16 @@ class Target
 		     off_t offset, const elfcpp::Ehdr<64, true>& ehdr);
 #endif
 
+  // Virtual function which may be overriden by the child class.
+  virtual bool
+  do_may_relax() const
+  { return parameters->options().relax(); }
+
+  // Virtual function which may be overriden by the child class.
+  virtual bool
+  do_relax(int)
+  { return false; }
+
  private:
   // The implementations of the four do_make_elf_object virtual functions are
   // almost identical except for their sizes and endianity.  We use a template.