2009-11-06 Doug Kwan <dougkwan@google.com>

	* arm.cc (class Reloc_stub): Correct a comment.
	(Target_arm::Target_arm): Initialize arm_input_section_map_.
	(Target_arm::scan_section_for_stubs): New method declaration.
	(Target_arm::do_make_elf_object, Target_arm::do_make_output_section):
	Change methods from private to protected.
	(Target_arm::do_may_relax): New method definition.
	(Target_arm::do_relax, Target_arm::group_sections,
	Target_arm::scan_reloc_for_stub,
	Target_arm::scan_reloc_section_for_stubs): New method declarations.
	(Target_arm::arm_input_section_map_): New data member declaration.
	(Target_arm::scan_reloc_for_stub,
	Target_arm::scan_reloc_section_for_stubs,
	Target_arm::scan_section_for_stubs, Target_arm::group_sections,
	Target_arm::do_relax): New method definitions.

2 files changed, 511 insertions, 17 deletions

diff --git a/gold/ChangeLog b/gold/ChangeLog
index c8210ba6e9..4afda97069 100644
--- a/gold/ChangeLog
+++ b/gold/ChangeLog
@@ -1,3 +1,20 @@
+2009-11-06  Doug Kwan  <dougkwan@google.com>
+
+	* arm.cc (class Reloc_stub): Correct a comment.
+	(Target_arm::Target_arm): Initialize arm_input_section_map_.
+	(Target_arm::scan_section_for_stubs): New method declaration.
+	(Target_arm::do_make_elf_object, Target_arm::do_make_output_section):
+	Change methods from private to protected.
+	(Target_arm::do_may_relax): New method definition.
+	(Target_arm::do_relax, Target_arm::group_sections,
+	Target_arm::scan_reloc_for_stub,
+	Target_arm::scan_reloc_section_for_stubs): New method declarations.
+	(Target_arm::arm_input_section_map_): New data member declaration.
+	(Target_arm::scan_reloc_for_stub,
+	Target_arm::scan_reloc_section_for_stubs,
+	Target_arm::scan_section_for_stubs, Target_arm::group_sections,
+	Target_arm::do_relax): New method definitions.
+
 2009-11-06  Mikolaj Zalewski  <mikolaj@google.com>
 
 	* configure.ac: Check for (struct stat)::st_mtim
diff --git a/gold/arm.cc b/gold/arm.cc
index e0c4a9a524..38ff3ac4ba 100644
--- a/gold/arm.cc
+++ b/gold/arm.cc
@@ -572,7 +572,7 @@ class Reloc_stub : public Stub
     unsigned int r_sym_;
     // If r_sym_ is invalid index.  This points to a global symbol.
     // Otherwise, this points a relobj.  We used the unsized and target
-    // independent Symbol and Relobj classes instead of Arm_symbol and  
+    // independent Symbol and Relobj classes instead of Sized_symbol<32> and  
     // Arm_relobj.  This is done to avoid making the stub class a template
     // as most of the stub machinery is endianity-neutral.  However, it
     // may require a bit of casting done by users of this class.
@@ -1145,7 +1145,8 @@ class Target_arm : public Sized_target<32, big_endian>
       got_(NULL), plt_(NULL), got_plt_(NULL), rel_dyn_(NULL),
       copy_relocs_(elfcpp::R_ARM_COPY), dynbss_(NULL), stub_tables_(),
       stub_factory_(Stub_factory::get_instance()),
-      may_use_blx_(true), should_force_pic_veneer_(false)
+      may_use_blx_(true), should_force_pic_veneer_(false),
+      arm_input_section_map_()
   { }
 
   // Whether we can use BLX.
@@ -1304,6 +1305,13 @@ class Target_arm : public Sized_target<32, big_endian>
   Stub_table<big_endian>*
   new_stub_table(Arm_input_section<big_endian>*);
 
+  // Scan a section for stub generation.
+  void
+  scan_section_for_stubs(const Relocate_info<32, big_endian>*, unsigned int,
+			 const unsigned char*, size_t, Output_section*,
+			 bool, const unsigned char*, Arm_address,
+			 section_size_type);
+
   // Get the default ARM target.
   static const Target_arm<big_endian>&
   default_target()
@@ -1318,9 +1326,44 @@ class Target_arm : public Sized_target<32, big_endian>
   reloc_uses_thumb_bit(unsigned int r_type);
 
  protected:
+  // Make an ELF object.
+  Object*
+  do_make_elf_object(const std::string&, Input_file*, off_t,
+		     const elfcpp::Ehdr<32, big_endian>& ehdr);
+
+  Object*
+  do_make_elf_object(const std::string&, Input_file*, off_t,
+		     const elfcpp::Ehdr<32, !big_endian>&)
+  { gold_unreachable(); }
+
+  Object*
+  do_make_elf_object(const std::string&, Input_file*, off_t,
+		      const elfcpp::Ehdr<64, false>&)
+  { gold_unreachable(); }
+
+  Object*
+  do_make_elf_object(const std::string&, Input_file*, off_t,
+		     const elfcpp::Ehdr<64, true>&)
+  { gold_unreachable(); }
+
+  // Make an output section.
+  Output_section*
+  do_make_output_section(const char* name, elfcpp::Elf_Word type,
+			 elfcpp::Elf_Xword flags)
+  { return new Arm_output_section<big_endian>(name, type, flags); }
+
   void
   do_adjust_elf_header(unsigned char* view, int len) const;
 
+  // We only need to generate stubs, and hence perform relaxation if we are
+  // not doing relocatable linking.
+  bool
+  do_may_relax() const
+  { return !parameters->options().relocatable(); }
+
+  bool
+  do_relax(int, const Input_objects*, Symbol_table*, Layout*);
+
  private:
   // The class which scans relocations.
   class Scan
@@ -1500,24 +1543,33 @@ class Target_arm : public Sized_target<32, big_endian>
   void
   merge_processor_specific_flags(const std::string&, elfcpp::Elf_Word);
 
-  Object*
-  do_make_elf_object(const std::string&, Input_file*, off_t,
-		     const elfcpp::Ehdr<32, big_endian>& ehdr);
+  //
+  // Methods to support stub-generations.
+  //
 
-  Object*
-  do_make_elf_object(const std::string&, Input_file*, off_t,
-		     const elfcpp::Ehdr<32, !big_endian>&)
-  { gold_unreachable(); }
+  // Group input sections for stub generation.
+  void
+  group_sections(Layout*, section_size_type, bool);
 
-  Object*
-  do_make_elf_object(const std::string&, Input_file*, off_t,
-		      const elfcpp::Ehdr<64, false>&)
-  { gold_unreachable(); }
+  // Scan a relocation for stub generation.
+  void
+  scan_reloc_for_stub(const Relocate_info<32, big_endian>*, unsigned int,
+		      const Sized_symbol<32>*, unsigned int,
+		      const Symbol_value<32>*,
+		      elfcpp::Elf_types<32>::Elf_Swxword, Arm_address);
 
-  Object*
-  do_make_elf_object(const std::string&, Input_file*, off_t,
-		     const elfcpp::Ehdr<64, true>&)
-  { gold_unreachable(); }
+  // Scan a relocation section for stub.
+  template<int sh_type>
+  void
+  scan_reloc_section_for_stubs(
+      const Relocate_info<32, big_endian>* relinfo,
+      const unsigned char* prelocs,
+      size_t reloc_count,
+      Output_section* output_section,
+      bool needs_special_offset_handling,
+      const unsigned char* view,
+      elfcpp::Elf_types<32>::Elf_Addr view_address,
+      section_size_type);
 
   // Information about this specific target which we pass to the
   // general Target structure.
@@ -1558,6 +1610,8 @@ class Target_arm : public Sized_target<32, big_endian>
   bool may_use_blx_;
   // Whether we force PIC branch veneers.
   bool should_force_pic_veneer_;
+  // Map for locating Arm_input_sections.
+  Arm_input_section_map arm_input_section_map_;
 };
 
 template<bool big_endian>
@@ -5119,6 +5173,429 @@ Target_arm<big_endian>::new_stub_table(Arm_input_section<big_endian>* owner)
   return stub_table;
 }
 
+// Scan a relocation for stub generation.
+
+template<bool big_endian>
+void
+Target_arm<big_endian>::scan_reloc_for_stub(
+    const Relocate_info<32, big_endian>* relinfo,
+    unsigned int r_type,
+    const Sized_symbol<32>* gsym,
+    unsigned int r_sym,
+    const Symbol_value<32>* psymval,
+    elfcpp::Elf_types<32>::Elf_Swxword addend,
+    Arm_address address)
+{
+  typedef typename Target_arm<big_endian>::Relocate Relocate;
+
+  const Arm_relobj<big_endian>* arm_relobj =
+    Arm_relobj<big_endian>::as_arm_relobj(relinfo->object);
+
+  bool target_is_thumb;
+  Symbol_value<32> symval;
+  if (gsym != NULL)
+    {
+      // This is a global symbol.  Determine if we use PLT and if the
+      // final target is THUMB.
+      if (gsym->use_plt_offset(Relocate::reloc_is_non_pic(r_type)))
+	{
+	  // This uses a PLT, change the symbol value.
+	  symval.set_output_value(this->plt_section()->address()
+				  + gsym->plt_offset());
+	  psymval = &symval;
+	  target_is_thumb = false;
+	}
+      else if (gsym->is_undefined())
+	// There is no need to generate a stub symbol is undefined.
+	return;
+      else
+	{
+	  target_is_thumb =
+	    ((gsym->type() == elfcpp::STT_ARM_TFUNC)
+	     || (gsym->type() == elfcpp::STT_FUNC
+		 && !gsym->is_undefined()
+		 && ((psymval->value(arm_relobj, 0) & 1) != 0)));
+	}
+    }
+  else
+    {
+      // This is a local symbol.  Determine if the final target is THUMB.
+      target_is_thumb = arm_relobj->local_symbol_is_thumb_function(r_sym);
+    }
+
+  // Strip LSB if this points to a THUMB target.
+  if (target_is_thumb
+      && Target_arm<big_endian>::reloc_uses_thumb_bit(r_type)
+      && ((psymval->value(arm_relobj, 0) & 1) != 0))
+    {
+      Arm_address stripped_value =
+	psymval->value(arm_relobj, 0) & ~static_cast<Arm_address>(1);
+      symval.set_output_value(stripped_value);
+      psymval = &symval;
+    } 
+
+  // Get the symbol value.
+  Symbol_value<32>::Value value = psymval->value(arm_relobj, 0);
+
+  // Owing to pipelining, the PC relative branches below actually skip
+  // two instructions when the branch offset is 0.
+  Arm_address destination;
+  switch (r_type)
+    {
+    case elfcpp::R_ARM_CALL:
+    case elfcpp::R_ARM_JUMP24:
+    case elfcpp::R_ARM_PLT32:
+      // ARM branches.
+      destination = value + addend + 8;
+      break;
+    case elfcpp::R_ARM_THM_CALL:
+    case elfcpp::R_ARM_THM_XPC22:
+    case elfcpp::R_ARM_THM_JUMP24:
+    case elfcpp::R_ARM_THM_JUMP19:
+      // THUMB branches.
+      destination = value + addend + 4;
+      break;
+    default:
+      gold_unreachable();
+    }
+
+  Stub_type stub_type =
+    Reloc_stub::stub_type_for_reloc(r_type, address, destination,
+				    target_is_thumb);
+
+  // This reloc does not need a stub.
+  if (stub_type == arm_stub_none)
+    return;
+
+  // Try looking up an existing stub from a stub table.
+  Stub_table<big_endian>* stub_table = 
+    arm_relobj->stub_table(relinfo->data_shndx);
+  gold_assert(stub_table != NULL);
+   
+  // Locate stub by destination.
+  Reloc_stub::Key stub_key(stub_type, gsym, arm_relobj, r_sym, addend);
+
+  // Create a stub if there is not one already
+  Reloc_stub* stub = stub_table->find_reloc_stub(stub_key);
+  if (stub == NULL)
+    {
+      // create a new stub and add it to stub table.
+      stub = this->stub_factory().make_reloc_stub(stub_type);
+      stub_table->add_reloc_stub(stub, stub_key);
+    }
+
+  // Record the destination address.
+  stub->set_destination_address(destination
+				| (target_is_thumb ? 1 : 0));
+}
+
+// This function scans a relocation sections for stub generation.
+// The template parameter Relocate must be a class type which provides
+// a single function, relocate(), which implements the machine
+// specific part of a relocation.
+
+// BIG_ENDIAN is the endianness of the data.  SH_TYPE is the section type:
+// SHT_REL or SHT_RELA.
+
+// PRELOCS points to the relocation data.  RELOC_COUNT is the number
+// of relocs.  OUTPUT_SECTION is the output section.
+// NEEDS_SPECIAL_OFFSET_HANDLING is true if input offsets need to be
+// mapped to output offsets.
+
+// VIEW is the section data, VIEW_ADDRESS is its memory address, and
+// VIEW_SIZE is the size.  These refer to the input section, unless
+// NEEDS_SPECIAL_OFFSET_HANDLING is true, in which case they refer to
+// the output section.
+
+template<bool big_endian>
+template<int sh_type>
+void inline
+Target_arm<big_endian>::scan_reloc_section_for_stubs(
+    const Relocate_info<32, big_endian>* relinfo,
+    const unsigned char* prelocs,
+    size_t reloc_count,
+    Output_section* output_section,
+    bool needs_special_offset_handling,
+    const unsigned char* view,
+    elfcpp::Elf_types<32>::Elf_Addr view_address,
+    section_size_type)
+{
+  typedef typename Reloc_types<sh_type, 32, big_endian>::Reloc Reltype;
+  const int reloc_size =
+    Reloc_types<sh_type, 32, big_endian>::reloc_size;
+
+  Arm_relobj<big_endian>* arm_object =
+    Arm_relobj<big_endian>::as_arm_relobj(relinfo->object);
+  unsigned int local_count = arm_object->local_symbol_count();
+
+  Comdat_behavior comdat_behavior = CB_UNDETERMINED;
+
+  for (size_t i = 0; i < reloc_count; ++i, prelocs += reloc_size)
+    {
+      Reltype reloc(prelocs);
+
+      typename elfcpp::Elf_types<32>::Elf_WXword r_info = reloc.get_r_info();
+      unsigned int r_sym = elfcpp::elf_r_sym<32>(r_info);
+      unsigned int r_type = elfcpp::elf_r_type<32>(r_info);
+
+      r_type = this->get_real_reloc_type(r_type);
+
+      // Only a few relocation types need stubs.
+      if ((r_type != elfcpp::R_ARM_CALL)
+         && (r_type != elfcpp::R_ARM_JUMP24)
+         && (r_type != elfcpp::R_ARM_PLT32)
+         && (r_type != elfcpp::R_ARM_THM_CALL)
+         && (r_type != elfcpp::R_ARM_THM_XPC22)
+         && (r_type != elfcpp::R_ARM_THM_JUMP24)
+         && (r_type != elfcpp::R_ARM_THM_JUMP19))
+	continue;
+
+      section_offset_type offset =
+	convert_to_section_size_type(reloc.get_r_offset());
+
+      if (needs_special_offset_handling)
+	{
+	  offset = output_section->output_offset(relinfo->object,
+						 relinfo->data_shndx,
+						 offset);
+	  if (offset == -1)
+	    continue;
+	}
+
+      // Get the addend.
+      Stub_addend_reader<sh_type, big_endian> stub_addend_reader;
+      elfcpp::Elf_types<32>::Elf_Swxword addend =
+	stub_addend_reader(r_type, view + offset, reloc);
+
+      const Sized_symbol<32>* sym;
+
+      Symbol_value<32> symval;
+      const Symbol_value<32> *psymval;
+      if (r_sym < local_count)
+	{
+	  sym = NULL;
+	  psymval = arm_object->local_symbol(r_sym);
+
+          // If the local symbol belongs to a section we are discarding,
+          // and that section is a debug section, try to find the
+          // corresponding kept section and map this symbol to its
+          // counterpart in the kept section.  The symbol must not 
+          // correspond to a section we are folding.
+	  bool is_ordinary;
+	  unsigned int shndx = psymval->input_shndx(&is_ordinary);
+	  if (is_ordinary
+	      && shndx != elfcpp::SHN_UNDEF
+	      && !arm_object->is_section_included(shndx) 
+              && !(relinfo->symtab->is_section_folded(arm_object, shndx)))
+	    {
+	      if (comdat_behavior == CB_UNDETERMINED)
+	        {
+	          std::string name =
+		    arm_object->section_name(relinfo->data_shndx);
+	          comdat_behavior = get_comdat_behavior(name.c_str());
+	        }
+	      if (comdat_behavior == CB_PRETEND)
+	        {
+                  bool found;
+	          typename elfcpp::Elf_types<32>::Elf_Addr value =
+	            arm_object->map_to_kept_section(shndx, &found);
+	          if (found)
+	            symval.set_output_value(value + psymval->input_value());
+                  else
+                    symval.set_output_value(0);
+	        }
+	      else
+	        {
+                  symval.set_output_value(0);
+	        }
+	      symval.set_no_output_symtab_entry();
+	      psymval = &symval;
+	    }
+	}
+      else
+	{
+	  const Symbol* gsym = arm_object->global_symbol(r_sym);
+	  gold_assert(gsym != NULL);
+	  if (gsym->is_forwarder())
+	    gsym = relinfo->symtab->resolve_forwards(gsym);
+
+	  sym = static_cast<const Sized_symbol<32>*>(gsym);
+	  if (sym->has_symtab_index())
+	    symval.set_output_symtab_index(sym->symtab_index());
+	  else
+	    symval.set_no_output_symtab_entry();
+
+	  // We need to compute the would-be final value of this global
+	  // symbol.
+	  const Symbol_table* symtab = relinfo->symtab;
+	  const Sized_symbol<32>* sized_symbol =
+	    symtab->get_sized_symbol<32>(gsym);
+	  Symbol_table::Compute_final_value_status status;
+	  Arm_address value =
+	    symtab->compute_final_value<32>(sized_symbol, &status);
+
+	  // Skip this if the symbol has not output section.
+	  if (status == Symbol_table::CFVS_NO_OUTPUT_SECTION)
+	    continue;
+
+	  symval.set_output_value(value);
+	  psymval = &symval;
+	}
+
+      // If symbol is a section symbol, we don't know the actual type of
+      // destination.  Give up.
+      if (psymval->is_section_symbol())
+	continue;
+
+      this->scan_reloc_for_stub(relinfo, r_type, sym, r_sym, psymval,
+				addend, view_address + offset);
+    }
+}
+
+// Scan an input section for stub generation.
+
+template<bool big_endian>
+void
+Target_arm<big_endian>::scan_section_for_stubs(
+    const Relocate_info<32, big_endian>* relinfo,
+    unsigned int sh_type,
+    const unsigned char* prelocs,
+    size_t reloc_count,
+    Output_section* output_section,
+    bool needs_special_offset_handling,
+    const unsigned char* view,
+    Arm_address view_address,
+    section_size_type view_size)
+{
+  if (sh_type == elfcpp::SHT_REL)
+    this->scan_reloc_section_for_stubs<elfcpp::SHT_REL>(
+	relinfo,
+	prelocs,
+	reloc_count,
+	output_section,
+	needs_special_offset_handling,
+	view,
+	view_address,
+	view_size);
+  else if (sh_type == elfcpp::SHT_RELA)
+    // We do not support RELA type relocations yet.  This is provided for
+    // completeness.
+    this->scan_reloc_section_for_stubs<elfcpp::SHT_RELA>(
+	relinfo,
+	prelocs,
+	reloc_count,
+	output_section,
+	needs_special_offset_handling,
+	view,
+	view_address,
+	view_size);
+  else
+    gold_unreachable();
+}
+
+// Group input sections for stub generation.
+//
+// We goup input sections in an output sections so that the total size,
+// including any padding space due to alignment is smaller than GROUP_SIZE
+// unless the only input section in group is bigger than GROUP_SIZE already.
+// Then an ARM stub table is created to follow the last input section
+// in group.  For each group an ARM stub table is created an is placed
+// after the last group.  If STUB_ALWATS_AFTER_BRANCH is false, we further
+// extend the group after the stub table.
+
+template<bool big_endian>
+void
+Target_arm<big_endian>::group_sections(
+    Layout* layout,
+    section_size_type group_size,
+    bool stubs_always_after_branch)
+{
+  // Group input sections and insert stub table
+  Layout::Section_list section_list;
+  layout->get_allocated_sections(&section_list);
+  for (Layout::Section_list::const_iterator p = section_list.begin();
+       p != section_list.end();
+       ++p)
+    {
+      Arm_output_section<big_endian>* output_section =
+	Arm_output_section<big_endian>::as_arm_output_section(*p);
+      output_section->group_sections(group_size, stubs_always_after_branch,
+				     this);
+    }
+}
+
+// Relaxation hook.  This is where we do stub generation.
+
+template<bool big_endian>
+bool
+Target_arm<big_endian>::do_relax(
+    int pass,
+    const Input_objects* input_objects,
+    Symbol_table* symtab,
+    Layout* layout)
+{
+  // No need to generate stubs if this is a relocatable link.
+  gold_assert(!parameters->options().relocatable());
+
+  // If this is the first pass, we need to group input sections into
+  // stub groups.
+  if (pass == 1)
+    {
+      // Determine the stub group size.  The group size is the absolute
+      // value of the parameter --stub-group-size.  If --stub-group-size
+      // is passed a negative value, we restict stubs to be always after
+      // the stubbed branches.
+      int32_t stub_group_size_param =
+	parameters->options().stub_group_size();
+      bool stubs_always_after_branch = stub_group_size_param < 0;
+      section_size_type stub_group_size = abs(stub_group_size_param);
+
+      if (stub_group_size == 1)
+	{
+	  // Default value.
+	  // Thumb branch range is +-4MB has to be used as the default
+	  // maximum size (a given section can contain both ARM and Thumb
+	  // code, so the worst case has to be taken into account).
+	  //
+	  // This value is 24K less than that, which allows for 2025
+	  // 12-byte stubs.  If we exceed that, then we will fail to link.
+	  // The user will have to relink with an explicit group size
+	  // option.
+	  stub_group_size = 4170000;
+	}
+
+      group_sections(layout, stub_group_size, stubs_always_after_branch);
+    }
+
+  // clear changed flags for all stub_tables
+  typedef typename Stub_table_list::iterator Stub_table_iterator;
+  for (Stub_table_iterator sp = this->stub_tables_.begin();
+       sp != this->stub_tables_.end();
+       ++sp)
+    (*sp)->set_has_been_changed(false);
+
+  // scan relocs for stubs
+  for (Input_objects::Relobj_iterator op = input_objects->relobj_begin();
+       op != input_objects->relobj_end();
+       ++op)
+    {
+      Arm_relobj<big_endian>* arm_relobj =
+	Arm_relobj<big_endian>::as_arm_relobj(*op);
+      arm_relobj->scan_sections_for_stubs(this, symtab, layout);
+    }
+
+  bool any_stub_table_changed = false;
+  for (Stub_table_iterator sp = this->stub_tables_.begin();
+       (sp != this->stub_tables_.end()) && !any_stub_table_changed;
+       ++sp)
+    {
+      if ((*sp)->has_been_changed())
+	any_stub_table_changed = true;
+    }
+
+  return any_stub_table_changed;
+}
+
 // The selector for arm object files.
 
 template<bool big_endian>