Re: [patch/rfc][pr17902] GC unused parts of mergeable sections

[Rafael EspÃndola <rafael dot espindola at gmail dot com>]

A new wip version is attached.

In comparison with the previous one, this version

* Handles non-string SHF_MERGE.
* Handles symbol making part of a section referenced.
* Mix fixes.

It reduces the .rodata section in chrome from 6985174 to 6851542 bytes.

Cheers,
Rafael

diff --git a/gold/gc.cc b/gold/gc.cc
index 843b2b8..c96faf4 100644
--- a/gold/gc.cc
+++ b/gold/gc.cc
@@ -29,6 +29,34 @@
 namespace gold
 {
 
+void Worklist::just_push(const Section_id &val) { this->work_list_.push(val); }
+
+void Worklist::push(const Section_id &val) {
+  this->work_list_.push(val);
+  Object *obj = val.first;
+  unsigned int shndx = val.second;
+  uint64_t flags = obj->section_flags(shndx);
+  gold_assert((flags & elfcpp::SHF_MERGE) == 0);
+}
+
+void Worklist::push(const Section_id &val, uint64_t offset) {
+  this->work_list_.push(val);
+  Object *obj = val.first;
+  unsigned int shndx = val.second;
+  uint64_t flags = obj->section_flags(shndx);
+  if ((flags & elfcpp::SHF_MERGE) == 0)
+    return;
+
+  // FIXME: what is the safe way to do this cast?
+  Relobj* r_obj = static_cast<Relobj*>(obj);
+  Object::Offsets_reachable &offsets = r_obj->referenced_offsets()[shndx];
+  Object::Offsets_reachable::iterator I =
+    std::lower_bound(offsets.begin(), offsets.end(), offset);
+  // FIXME: duplicated code with Garbage_collection::do_transitive_closure.
+  if (I == offsets.end() || *I != offset)
+    offsets.insert(I, offset);
+}
+
 // Garbage collection uses a worklist style algorithm to determine the 
 // transitive closure of all referenced sections.
 void 
@@ -63,11 +91,34 @@ Garbage_collection::do_transitive_closure()
           if (this->referenced_list().find(*it_v)
               == this->referenced_list().end())
             {
-              this->worklist().push(*it_v);   
+              this->worklist().just_push(*it_v);   
             }
         }
     }
   this->worklist_ready();
+  for (Sections_reachable::iterator I = this->referenced_list().begin(),
+                                    E = this->referenced_list().end();
+       I != E; ++I) {
+    Atom_reachable &atoms = this->atom_reloc_map()[*I];
+    for (Atom_reachable::iterator I2 = atoms.begin(), E2 = atoms.end();
+         I2 != E2; ++I2) {
+      const Atom &atom = *I2;
+      const Section_id id = atom.first;
+      Object* obj = id.first;
+      unsigned int sec_num = id.second;
+      // FIXME: what is the safe way to do this cast?
+      Relobj* r_obj = static_cast<Relobj*>(obj);
+      Object::Offsets_reachable &offsets = r_obj->referenced_offsets()[sec_num];
+      uint64_t new_offset = atom.second;
+      Object::Offsets_reachable::iterator I =
+        std::lower_bound(offsets.begin(), offsets.end(), new_offset);
+      // FIXME: Consider different algorithms:
+      // just push_back and sort/uniq afterwards
+      // use a set on the side to avoid inserting duplicates
+      if (I == offsets.end() || *I != new_offset)
+        offsets.insert(I, new_offset);
+    }
+  }
 }
 
 } // End namespace gold.
diff --git a/gold/gc.h b/gold/gc.h
index 2db7cb9..7effbe1 100644
--- a/gold/gc.h
+++ b/gold/gc.h
@@ -46,18 +46,49 @@ class Output_section;
 class General_options;
 class Layout;
 
+class Worklist
+{
+ public:
+  bool empty() const {
+    return work_list_.empty();
+  }
+  Section_id &front() {
+    return work_list_.front();
+  }
+  void pop() {
+    work_list_.pop();
+  }
+  void just_push(const Section_id& val);
+  void push(const Section_id& val);
+  void push(const Section_id& val, uint64_t offset);
+
+ private:
+  typedef std::queue<Section_id> Worklist_type;
+  Worklist_type work_list_;
+};
+
 class Garbage_collection
 {
  public:
 
   typedef Unordered_set<Section_id, Section_id_hash> Sections_reachable;
   typedef std::map<Section_id, Sections_reachable> Section_ref;
-  typedef std::queue<Section_id> Worklist_type;
+
   // This maps the name of the section which can be represented as a C
   // identifier (cident) to the list of sections that have that name.
   // Different object files can have cident sections with the same name.
   typedef std::map<std::string, Sections_reachable> Cident_section_map;
 
+  typedef std::pair<Section_id, uint64_t> Atom;
+  struct Atom_hash {
+    size_t operator()(const Atom &a) const {
+      const Section_id &s = a.first;
+      return reinterpret_cast<uintptr_t>(s.first) ^ s.second ^ a.second;
+    }
+  };
+  typedef Unordered_set<Atom, Atom_hash> Atom_reachable;
+  typedef std::map<Section_id, Atom_reachable> Atom_ref;
+
   Garbage_collection()
   : is_worklist_ready_(false)
   { }
@@ -72,7 +103,11 @@ class Garbage_collection
   section_reloc_map()
   { return this->section_reloc_map_; }
 
-  Worklist_type&
+  Atom_ref&
+  atom_reloc_map()
+  { return this->atom_reloc_map_; }
+
+  Worklist&
   worklist()
   { return this->work_list_; }
 
@@ -116,13 +151,26 @@ class Garbage_collection
       p->second.insert(dst_id);
   }
 
+  void add_reference_to_merge_section(Object *src_object,
+                                      unsigned int src_shndx,
+                                      Object *dst_object,
+                                      unsigned int dst_shndx, uint64_t offset) {
+    add_reference(src_object, src_shndx, dst_object, dst_shndx);
+    Section_id src_id(src_object, src_shndx);
+    Section_id dst_id(dst_object, dst_shndx);
+    Atom atom(dst_id, offset);
+    this->atom_reloc_map_[src_id].insert(atom);
+  }
+
  private:
 
-  Worklist_type work_list_;
+  Worklist work_list_;
   bool is_worklist_ready_;
   Section_ref section_reloc_map_;
   Sections_reachable referenced_list_;
   Cident_section_map cident_sections_;
+
+  Atom_ref atom_reloc_map_;
 };
 
 // Data to pass between successive invocations of do_layout
@@ -238,6 +286,10 @@ gc_process_relocs(
       typedef typename elfcpp::Elf_types<size>::Elf_Addr Address;
       Address dst_off;
 
+      // If the relocation points to a section, this includes the addend.
+      // Otherwise it doesn't.
+      Address gc_ref_off;
+
       if (r_sym < local_count)
         {
           gold_assert(plocal_syms != NULL);
@@ -247,7 +299,10 @@ gc_process_relocs(
           bool is_ordinary;
 	  dst_indx = src_obj->adjust_sym_shndx(r_sym, dst_indx, &is_ordinary);
           dst_obj = src_obj;
-	  dst_off = lsym.get_st_value() + addend;
+	  gc_ref_off = dst_off = lsym.get_st_value();
+	  dst_off += addend;
+	  if (lsym.get_st_type() == elfcpp::STT_SECTION)
+	    gc_ref_off += addend;
 
           if (is_icf_tracked)
             {
@@ -299,6 +354,7 @@ gc_process_relocs(
               dst_indx = gsym->shndx(&is_ordinary);
             }
 	  dst_off = static_cast<const Sized_symbol<size>*>(gsym)->value();
+	  gc_ref_off = dst_off;
 	  dst_off += addend;
 
 	  // When doing safe folding, check to see if this relocation is that
@@ -351,7 +407,14 @@ gc_process_relocs(
         }
       if (parameters->options().gc_sections())
         {
-	  symtab->gc()->add_reference(src_obj, src_indx, dst_obj, dst_indx);
+	  Garbage_collection* gc = symtab->gc();
+	  uint64_t dst_flags = dst_obj->section_flags(dst_indx);
+	  if (dst_flags & elfcpp::SHF_MERGE)
+	    gc->add_reference_to_merge_section(src_obj, src_indx, dst_obj,
+					       dst_indx, gc_ref_off);
+	  else
+	    gc->add_reference(src_obj, src_indx, dst_obj, dst_indx);
+
 	  parameters->sized_target<size, big_endian>()
 	    ->gc_add_reference(symtab, src_obj, src_indx,
 			       dst_obj, dst_indx, dst_off);
diff --git a/gold/merge.cc b/gold/merge.cc
index f547388..5776735 100644
--- a/gold/merge.cc
+++ b/gold/merge.cc
@@ -423,6 +423,9 @@ Output_merge_data::do_add_input_section(Relobj* object, unsigned int shndx)
 
   for (section_size_type i = 0; i < len; i += entsize, p += entsize)
     {
+      if (!object->is_offset_referenced(shndx, i, entsize))
+        continue;
+
       // Add the constant to the section contents.  If we find that it
       // is already in the hash table, we will remove it again.
       Merge_data_key k = this->len_;
@@ -567,6 +570,7 @@ Output_merge_string<Char_type>::do_add_input_section(Relobj* object,
   while (p < pend)
     {
       size_t len = p < pend0 ? string_length(p) : pend - p;
+      size_t num_bytes = (len + 1) * sizeof(Char_type);
 
       // Within merge input section each string must be aligned.
       if (len != 0
@@ -574,12 +578,15 @@ Output_merge_string<Char_type>::do_add_input_section(Relobj* object,
 	      != init_align_modulo))
 	  has_misaligned_strings = true;
 
-      Stringpool::Key key;
-      this->stringpool_.add_with_length(p, len, true, &key);
+      // FIXME: replace offset with i.
+      if (object->is_offset_referenced(shndx, i, num_bytes)) {
+        Stringpool::Key key;
+        this->stringpool_.add_with_length(p, len, true, &key);
 
-      merged_strings.push_back(Merged_string(i, key));
+        merged_strings.push_back(Merged_string(i, key));
+      }
       p += len + 1;
-      i += (len + 1) * sizeof(Char_type);
+      i += num_bytes;
     }
 
   // Record the last offset in the input section so that we can
diff --git a/gold/object.cc b/gold/object.cc
index 8f16fe7..4c08dd3 100644
--- a/gold/object.cc
+++ b/gold/object.cc
@@ -368,6 +368,30 @@ Relobj::finalize_incremental_relocs(Layout* layout, bool clear_counts)
   layout->incremental_inputs()->set_reloc_count(rindex);
 }
 
+bool Relobj::is_offset_referenced(unsigned int shndx, uint64_t offset,
+                                  size_t len) {
+  if (!parameters->options().gc_sections())
+    return true;
+
+  uint64_t flags = this->section_flags(shndx);
+  // We don't gc non alloc sections.
+  if ((flags & elfcpp::SHF_ALLOC) == 0)
+    return true;
+
+  // Only SHF_MERGE sections are partially gced.
+  if ((flags & elfcpp::SHF_MERGE) == 0)
+    return true;
+
+  Object::Offsets_reachable &offsets = this->referenced_offsets()[shndx];
+  Object::Offsets_reachable::iterator I =
+      std::lower_bound(offsets.begin(), offsets.end(), offset);
+  if (I == offsets.end())
+    return false;
+  if (*I >= offset + len)
+    return false;
+  return true;
+}
+
 // Class Sized_relobj.
 
 // Iterate over local symbols, calling a visitor class V for each GOT offset
@@ -2154,7 +2178,10 @@ Sized_relobj_file<size, big_endian>::do_count_local_symbols(Stringpool* pool,
 
       // Decide whether this symbol should go into the output file.
 
-      if ((shndx < shnum && out_sections[shndx] == NULL)
+      if ((shndx < shnum
+	   && (out_sections[shndx] == NULL ||
+	       !this->is_offset_referenced(shndx, sym.get_st_value(),
+					   /*FIXME*/ 4)))
 	  || shndx == this->discarded_eh_frame_shndx_)
 	{
 	  lv.set_no_output_symtab_entry();
@@ -2327,6 +2354,10 @@ Sized_relobj_file<size, big_endian>::compute_final_local_value_internal(
 	    }
 	  else if (!lv_in->is_section_symbol())
 	    {
+              if (!this->is_offset_referenced(shndx, lv_in->input_value(),
+                                              /*FIXME*/4))
+                return This::CFLV_DISCARDED;
+
 	      // This is not a section symbol.  We can determine
 	      // the final value now.
 	      lv_out->set_output_value(
@@ -2589,7 +2620,7 @@ Sized_relobj_file<size, big_endian>::write_local_symbols(
     dyn_oview = of->get_output_view(this->local_dynsym_offset_,
 				    dyn_output_size);
 
-  const Output_sections out_sections(this->output_sections());
+  const Output_sections& out_sections(this->output_sections());
 
   gold_assert(this->local_values_.size() == loccount);
 
diff --git a/gold/object.h b/gold/object.h
index cce6c8c..fe66d1a 100644
--- a/gold/object.h
+++ b/gold/object.h
@@ -322,6 +322,8 @@ class Object
 {
  public:
   typedef std::vector<Symbol*> Symbols;
+  typedef std::vector<uint64_t> Offsets_reachable;
+  typedef std::map<unsigned int, Offsets_reachable> Offset_ref;
 
   // NAME is the name of the object as we would report it to the user
   // (e.g., libfoo.a(bar.o) if this is in an archive.  INPUT_FILE is
@@ -1255,6 +1257,13 @@ class Relobj : public Object
   is_big_endian() const
   { return this->do_is_big_endian(); }
 
+  Offset_ref&
+  referenced_offsets()
+  { return this->referenced_offsets_; }
+
+  bool
+  is_offset_referenced(unsigned int shndx, uint64_t offset, size_t len);
+
  protected:
   // The output section to be used for each input section, indexed by
   // the input section number.  The output section is NULL if the
@@ -1454,6 +1463,8 @@ class Relobj : public Object
   unsigned int first_dyn_reloc_;
   // Count of dynamic relocations for this object.
   unsigned int dyn_reloc_count_;
+
+  Offset_ref referenced_offsets_;
 };
 
 // This class is used to handle relocations against a section symbol
diff --git a/gold/symtab.cc b/gold/symtab.cc
index 045327a..435ee5d 100644
--- a/gold/symtab.cc
+++ b/gold/symtab.cc
@@ -637,8 +637,9 @@ Symbol_table::gc_mark_undef_symbols(Layout* layout)
     }
 }
 
+template<int size>
 void
-Symbol_table::gc_mark_symbol(Symbol* sym)
+Symbol_table::gc_mark_sized_symbol(Sized_symbol<size>* sym)
 {
   // Add the object and section to the work list.
   bool is_ordinary;
@@ -646,11 +647,22 @@ Symbol_table::gc_mark_symbol(Symbol* sym)
   if (is_ordinary && shndx != elfcpp::SHN_UNDEF)
     {
       gold_assert(this->gc_!= NULL);
-      this->gc_->worklist().push(Section_id(sym->object(), shndx));
+      this->gc_->worklist().push(Section_id(sym->object(), shndx),
+                                 sym->value());
     }
   parameters->target().gc_mark_symbol(this, sym);
 }
 
+void
+Symbol_table::gc_mark_symbol(Symbol* sym)
+{
+  const int size = parameters->target().get_size();
+  if (size == 32)
+    gc_mark_sized_symbol(this->get_sized_symbol<32>(sym));
+  else
+    gc_mark_sized_symbol(this->get_sized_symbol<64>(sym));
+}
+
 // When doing garbage collection, keep symbols that have been seen in
 // dynamic objects.
 inline void 
diff --git a/gold/symtab.h b/gold/symtab.h
index aa0cb68..5f245c6 100644
--- a/gold/symtab.h
+++ b/gold/symtab.h
@@ -1387,6 +1387,10 @@ class Symbol_table
   gc_mark_undef_symbols(Layout*);
 
   // This tells garbage collection that this symbol is referenced.
+  template<int size>
+  void
+  gc_mark_sized_symbol(Sized_symbol<size>* sym);
+
   void
   gc_mark_symbol(Symbol* sym);