Share DWARF .debug_abbrev sections.

Restructure the code so that all compilation units share the same
.debug_abbrev sections.  This deduplicates many of the abbrevs.

Change-Id: I7da07a8c850871786df52674183c16d574684729

5 files changed, 150 insertions, 100 deletions

diff --git a/compiler/dwarf/debug_abbrev_writer.h b/compiler/dwarf/debug_abbrev_writer.h
new file mode 100644
index 0000000000..71367e85ad
--- /dev/null
+++ b/compiler/dwarf/debug_abbrev_writer.h
@@ -0,0 +1,98 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_COMPILER_DWARF_DEBUG_ABBREV_WRITER_H_
+#define ART_COMPILER_DWARF_DEBUG_ABBREV_WRITER_H_
+
+#include <cstdint>
+#include <type_traits>
+#include <unordered_map>
+
+#include "base/casts.h"
+#include "base/stl_util.h"
+#include "dwarf/dwarf_constants.h"
+#include "dwarf/writer.h"
+#include "leb128.h"
+
+namespace art {
+namespace dwarf {
+
+// Writer for the .debug_abbrev.
+//
+// Abbreviations specify the format of entries in .debug_info.
+// Each entry specifies abbreviation code, which in turns
+// determines all the attributes and their format.
+// It is possible to think of them as type definitions.
+template <typename Vector = std::vector<uint8_t>>
+class DebugAbbrevWriter FINAL : private Writer<Vector> {
+  static_assert(std::is_same<typename Vector::value_type, uint8_t>::value, "Invalid value type");
+
+ public:
+  explicit DebugAbbrevWriter(Vector* buffer)
+      : Writer<Vector>(buffer),
+        current_abbrev_(buffer->get_allocator()) {
+    this->PushUint8(0);  // Add abbrev table terminator.
+  }
+
+  // Start abbreviation declaration.
+  void StartAbbrev(Tag tag) {
+    DCHECK(current_abbrev_.empty());
+    EncodeUnsignedLeb128(&current_abbrev_, tag);
+    has_children_offset_ = current_abbrev_.size();
+    current_abbrev_.push_back(0);  // Place-holder for DW_CHILDREN.
+  }
+
+  // Add attribute specification.
+  void AddAbbrevAttribute(Attribute name, Form type) {
+    EncodeUnsignedLeb128(&current_abbrev_, name);
+    EncodeUnsignedLeb128(&current_abbrev_, type);
+  }
+
+  // End abbreviation declaration and return its code.
+  // This will deduplicate abbreviations.
+  uint32_t EndAbbrev(Children has_children) {
+    DCHECK(!current_abbrev_.empty());
+    current_abbrev_[has_children_offset_] = has_children;
+    auto it = abbrev_codes_.insert(std::make_pair(std::move(current_abbrev_), NextAbbrevCode()));
+    uint32_t abbrev_code = it.first->second;
+    if (UNLIKELY(it.second)) {  // Inserted new entry.
+      const Vector& abbrev = it.first->first;
+      this->Pop();  // Remove abbrev table terminator.
+      this->PushUleb128(abbrev_code);
+      this->PushData(abbrev.data(), abbrev.size());
+      this->PushUint8(0);  // Attribute list end.
+      this->PushUint8(0);  // Attribute list end.
+      this->PushUint8(0);  // Add abbrev table terminator.
+    }
+    current_abbrev_.clear();
+    return abbrev_code;
+  }
+
+  // Get the next free abbrev code.
+  uint32_t NextAbbrevCode() {
+    return dchecked_integral_cast<uint32_t>(1 + abbrev_codes_.size());
+  }
+
+ private:
+  Vector current_abbrev_;
+  size_t has_children_offset_ = 0;
+  std::unordered_map<Vector, uint32_t, FNVHash<Vector> > abbrev_codes_;
+};
+
+}  // namespace dwarf
+}  // namespace art
+
+#endif  // ART_COMPILER_DWARF_DEBUG_ABBREV_WRITER_H_
diff --git a/compiler/dwarf/debug_info_entry_writer.h b/compiler/dwarf/debug_info_entry_writer.h
index 5e3d2c8dfd..1e298595a1 100644
--- a/compiler/dwarf/debug_info_entry_writer.h
+++ b/compiler/dwarf/debug_info_entry_writer.h
@@ -21,6 +21,7 @@
 #include <unordered_map>
 
 #include "base/casts.h"
+#include "dwarf/debug_abbrev_writer.h"
 #include "dwarf/dwarf_constants.h"
 #include "dwarf/expression.h"
 #include "dwarf/writer.h"
@@ -29,24 +30,8 @@
 namespace art {
 namespace dwarf {
 
-// 32-bit FNV-1a hash function which we use to find duplicate abbreviations.
-// See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
-template <typename Vector>
-struct FNVHash {
-  static_assert(std::is_same<typename Vector::value_type, uint8_t>::value, "Invalid value type");
-
-  size_t operator()(const Vector& v) const {
-    uint32_t hash = 2166136261u;
-    for (size_t i = 0; i < v.size(); i++) {
-      hash = (hash ^ v[i]) * 16777619u;
-    }
-    return hash;
-  }
-};
-
 /*
  * Writer for debug information entries (DIE).
- * It also handles generation of abbreviations.
  *
  * Usage:
  *   StartTag(DW_TAG_compile_unit);
@@ -69,13 +54,13 @@ class DebugInfoEntryWriter FINAL : private Writer<Vector> {
     if (inside_entry_) {
       // Write abbrev code for the previous entry.
       // Parent entry is finalized before any children are written.
-      this->UpdateUleb128(abbrev_code_offset_, EndAbbrev(DW_CHILDREN_yes));
+      this->UpdateUleb128(abbrev_code_offset_, debug_abbrev_->EndAbbrev(DW_CHILDREN_yes));
       inside_entry_ = false;
     }
-    StartAbbrev(tag);
+    debug_abbrev_->StartAbbrev(tag);
     // Abbrev code placeholder of sufficient size.
     abbrev_code_offset_ = this->data()->size();
-    this->PushUleb128(NextAbbrevCode());
+    this->PushUleb128(debug_abbrev_->NextAbbrevCode());
     depth_++;
     inside_entry_ = true;
     return abbrev_code_offset_ + kCompilationUnitHeaderSize;
@@ -86,7 +71,7 @@ class DebugInfoEntryWriter FINAL : private Writer<Vector> {
     DCHECK_GT(depth_, 0);
     if (inside_entry_) {
       // Write abbrev code for this entry.
-      this->UpdateUleb128(abbrev_code_offset_, EndAbbrev(DW_CHILDREN_no));
+      this->UpdateUleb128(abbrev_code_offset_, debug_abbrev_->EndAbbrev(DW_CHILDREN_no));
       inside_entry_ = false;
       // This entry has no children and so there is no terminator.
     } else {
@@ -98,7 +83,7 @@ class DebugInfoEntryWriter FINAL : private Writer<Vector> {
   }
 
   void WriteAddr(Attribute attrib, uint64_t value) {
-    AddAbbrevAttribute(attrib, DW_FORM_addr);
+    debug_abbrev_->AddAbbrevAttribute(attrib, DW_FORM_addr);
     patch_locations_.push_back(this->data()->size());
     if (is64bit_) {
       this->PushUint64(value);
@@ -108,89 +93,89 @@ class DebugInfoEntryWriter FINAL : private Writer<Vector> {
   }
 
   void WriteBlock(Attribute attrib, const uint8_t* ptr, size_t num_bytes) {
-    AddAbbrevAttribute(attrib, DW_FORM_block);
+    debug_abbrev_->AddAbbrevAttribute(attrib, DW_FORM_block);
     this->PushUleb128(num_bytes);
     this->PushData(ptr, num_bytes);
   }
 
   void WriteExprLoc(Attribute attrib, const Expression& expr) {
-    AddAbbrevAttribute(attrib, DW_FORM_exprloc);
+    debug_abbrev_->AddAbbrevAttribute(attrib, DW_FORM_exprloc);
     this->PushUleb128(dchecked_integral_cast<uint32_t>(expr.size()));
     this->PushData(expr.data());
   }
 
   void WriteData1(Attribute attrib, uint8_t value) {
-    AddAbbrevAttribute(attrib, DW_FORM_data1);
+    debug_abbrev_->AddAbbrevAttribute(attrib, DW_FORM_data1);
     this->PushUint8(value);
   }
 
   void WriteData2(Attribute attrib, uint16_t value) {
-    AddAbbrevAttribute(attrib, DW_FORM_data2);
+    debug_abbrev_->AddAbbrevAttribute(attrib, DW_FORM_data2);
     this->PushUint16(value);
   }
 
   void WriteData4(Attribute attrib, uint32_t value) {
-    AddAbbrevAttribute(attrib, DW_FORM_data4);
+    debug_abbrev_->AddAbbrevAttribute(attrib, DW_FORM_data4);
     this->PushUint32(value);
   }
 
   void WriteData8(Attribute attrib, uint64_t value) {
-    AddAbbrevAttribute(attrib, DW_FORM_data8);
+    debug_abbrev_->AddAbbrevAttribute(attrib, DW_FORM_data8);
     this->PushUint64(value);
   }
 
   void WriteSecOffset(Attribute attrib, uint32_t offset) {
-    AddAbbrevAttribute(attrib, DW_FORM_sec_offset);
+    debug_abbrev_->AddAbbrevAttribute(attrib, DW_FORM_sec_offset);
     this->PushUint32(offset);
   }
 
   void WriteSdata(Attribute attrib, int value) {
-    AddAbbrevAttribute(attrib, DW_FORM_sdata);
+    debug_abbrev_->AddAbbrevAttribute(attrib, DW_FORM_sdata);
     this->PushSleb128(value);
   }
 
   void WriteUdata(Attribute attrib, int value) {
-    AddAbbrevAttribute(attrib, DW_FORM_udata);
+    debug_abbrev_->AddAbbrevAttribute(attrib, DW_FORM_udata);
     this->PushUleb128(value);
   }
 
   void WriteUdata(Attribute attrib, uint32_t value) {
-    AddAbbrevAttribute(attrib, DW_FORM_udata);
+    debug_abbrev_->AddAbbrevAttribute(attrib, DW_FORM_udata);
     this->PushUleb128(value);
   }
 
   void WriteFlag(Attribute attrib, bool value) {
-    AddAbbrevAttribute(attrib, DW_FORM_flag);
+    debug_abbrev_->AddAbbrevAttribute(attrib, DW_FORM_flag);
     this->PushUint8(value ? 1 : 0);
   }
 
   void WriteFlagPresent(Attribute attrib) {
-    AddAbbrevAttribute(attrib, DW_FORM_flag_present);
+    debug_abbrev_->AddAbbrevAttribute(attrib, DW_FORM_flag_present);
   }
 
   void WriteRef4(Attribute attrib, uint32_t cu_offset) {
-    AddAbbrevAttribute(attrib, DW_FORM_ref4);
+    debug_abbrev_->AddAbbrevAttribute(attrib, DW_FORM_ref4);
     this->PushUint32(cu_offset);
   }
 
   void WriteRef(Attribute attrib, uint32_t cu_offset) {
-    AddAbbrevAttribute(attrib, DW_FORM_ref_udata);
+    debug_abbrev_->AddAbbrevAttribute(attrib, DW_FORM_ref_udata);
     this->PushUleb128(cu_offset);
   }
 
   void WriteString(Attribute attrib, const char* value) {
-    AddAbbrevAttribute(attrib, DW_FORM_string);
+    debug_abbrev_->AddAbbrevAttribute(attrib, DW_FORM_string);
     this->PushString(value);
   }
 
   void WriteStrp(Attribute attrib, size_t debug_str_offset) {
-    AddAbbrevAttribute(attrib, DW_FORM_strp);
+    debug_abbrev_->AddAbbrevAttribute(attrib, DW_FORM_strp);
     this->PushUint32(dchecked_integral_cast<uint32_t>(debug_str_offset));
   }
 
   void WriteStrp(Attribute attrib, const char* str, size_t len,
                  std::vector<uint8_t>* debug_str) {
-    AddAbbrevAttribute(attrib, DW_FORM_strp);
+    debug_abbrev_->AddAbbrevAttribute(attrib, DW_FORM_strp);
     this->PushUint32(debug_str->size());
     debug_str->insert(debug_str->end(), str, str + len);
     debug_str->push_back(0);
@@ -213,16 +198,13 @@ class DebugInfoEntryWriter FINAL : private Writer<Vector> {
   using Writer<Vector>::UpdateUint32;
 
   DebugInfoEntryWriter(bool is64bitArch,
-                       Vector* debug_abbrev,
+                       DebugAbbrevWriter<Vector>* debug_abbrev,
                        const typename Vector::allocator_type& alloc =
                            typename Vector::allocator_type())
       : Writer<Vector>(&entries_),
         debug_abbrev_(debug_abbrev),
-        current_abbrev_(alloc),
-        abbrev_codes_(alloc),
         entries_(alloc),
         is64bit_(is64bitArch) {
-    debug_abbrev_.PushUint8(0);  // Add abbrev table terminator.
   }
 
   ~DebugInfoEntryWriter() {
@@ -231,53 +213,7 @@ class DebugInfoEntryWriter FINAL : private Writer<Vector> {
   }
 
  private:
-  // Start abbreviation declaration.
-  void StartAbbrev(Tag tag) {
-    current_abbrev_.clear();
-    EncodeUnsignedLeb128(&current_abbrev_, tag);
-    has_children_offset_ = current_abbrev_.size();
-    current_abbrev_.push_back(0);  // Place-holder for DW_CHILDREN.
-  }
-
-  // Add attribute specification.
-  void AddAbbrevAttribute(Attribute name, Form type) {
-    DCHECK(inside_entry_) << "Call StartTag before adding attributes.";
-    EncodeUnsignedLeb128(&current_abbrev_, name);
-    EncodeUnsignedLeb128(&current_abbrev_, type);
-  }
-
-  int NextAbbrevCode() {
-    return 1 + abbrev_codes_.size();
-  }
-
-  // End abbreviation declaration and return its code.
-  int EndAbbrev(Children has_children) {
-    DCHECK(!current_abbrev_.empty());
-    current_abbrev_[has_children_offset_] = has_children;
-    auto it = abbrev_codes_.insert(std::make_pair(std::move(current_abbrev_),
-                                                  NextAbbrevCode()));
-    int abbrev_code = it.first->second;
-    if (UNLIKELY(it.second)) {  // Inserted new entry.
-      const Vector& abbrev = it.first->first;
-      debug_abbrev_.Pop();  // Remove abbrev table terminator.
-      debug_abbrev_.PushUleb128(abbrev_code);
-      debug_abbrev_.PushData(abbrev.data(), abbrev.size());
-      debug_abbrev_.PushUint8(0);  // Attribute list end.
-      debug_abbrev_.PushUint8(0);  // Attribute list end.
-      debug_abbrev_.PushUint8(0);  // Add abbrev table terminator.
-    }
-    return abbrev_code;
-  }
-
- private:
-  // Fields for writing and deduplication of abbrevs.
-  Writer<Vector> debug_abbrev_;
-  Vector current_abbrev_;
-  size_t has_children_offset_ = 0;
-  std::unordered_map<Vector, int,
-                     FNVHash<Vector> > abbrev_codes_;
-
-  // Fields for writing of debugging information entries.
+  DebugAbbrevWriter<Vector>* debug_abbrev_;
   Vector entries_;
   bool is64bit_;
   int depth_ = 0;
diff --git a/compiler/dwarf/dwarf_test.cc b/compiler/dwarf/dwarf_test.cc
index e9cd421da9..32373119b2 100644
--- a/compiler/dwarf/dwarf_test.cc
+++ b/compiler/dwarf/dwarf_test.cc
@@ -283,7 +283,8 @@ TEST_F(DwarfTest, DebugLineSpecialOpcodes) {
 
 TEST_F(DwarfTest, DebugInfo) {
   constexpr bool is64bit = false;
-  DebugInfoEntryWriter<> info(is64bit, &debug_abbrev_data_);
+  DebugAbbrevWriter<> debug_abbrev(&debug_abbrev_data_);
+  DebugInfoEntryWriter<> info(is64bit, &debug_abbrev);
   DW_CHECK("Contents of the .debug_info section:");
   info.StartTag(dwarf::DW_TAG_compile_unit);
   DW_CHECK("Abbrev Number: 1 (DW_TAG_compile_unit)");
diff --git a/compiler/elf_writer_debug.cc b/compiler/elf_writer_debug.cc
index b43b86eb28..e1116fd6d2 100644
--- a/compiler/elf_writer_debug.cc
+++ b/compiler/elf_writer_debug.cc
@@ -486,7 +486,7 @@ class DebugInfoWriter {
    public:
     explicit CompilationUnitWriter(DebugInfoWriter* owner)
       : owner_(owner),
-        info_(Is64BitInstructionSet(owner_->builder_->GetIsa()), &debug_abbrev_) {
+        info_(Is64BitInstructionSet(owner_->builder_->GetIsa()), &owner->debug_abbrev_) {
     }
 
     void Write(const CompilationUnit& compilation_unit) {
@@ -622,8 +622,8 @@ class DebugInfoWriter {
       std::vector<uint8_t> buffer;
       buffer.reserve(info_.data()->size() + KB);
       const size_t offset = owner_->builder_->GetDebugInfo()->GetSize();
-      const size_t debug_abbrev_offset =
-          owner_->debug_abbrev_.Insert(debug_abbrev_.data(), debug_abbrev_.size());
+      // All compilation units share single table which is at the start of .debug_abbrev.
+      const size_t debug_abbrev_offset = 0;
       WriteDebugInfoCU(debug_abbrev_offset, info_, offset, &buffer, &owner_->debug_info_patches_);
       owner_->builder_->GetDebugInfo()->WriteFully(buffer.data(), buffer.size());
     }
@@ -785,8 +785,8 @@ class DebugInfoWriter {
       std::vector<uint8_t> buffer;
       buffer.reserve(info_.data()->size() + KB);
       const size_t offset = owner_->builder_->GetDebugInfo()->GetSize();
-      const size_t debug_abbrev_offset =
-          owner_->debug_abbrev_.Insert(debug_abbrev_.data(), debug_abbrev_.size());
+      // All compilation units share single table which is at the start of .debug_abbrev.
+      const size_t debug_abbrev_offset = 0;
       WriteDebugInfoCU(debug_abbrev_offset, info_, offset, &buffer, &owner_->debug_info_patches_);
       owner_->builder_->GetDebugInfo()->WriteFully(buffer.data(), buffer.size());
     }
@@ -1118,8 +1118,6 @@ class DebugInfoWriter {
 
     // For access to the ELF sections.
     DebugInfoWriter<ElfTypes>* owner_;
-    // Debug abbrevs for this compilation unit only.
-    std::vector<uint8_t> debug_abbrev_;
     // Temporary buffer to create and store the entries.
     DebugInfoEntryWriter<> info_;
     // Cache of already translated type descriptors.
@@ -1132,7 +1130,9 @@ class DebugInfoWriter {
   };
 
  public:
-  explicit DebugInfoWriter(ElfBuilder<ElfTypes>* builder) : builder_(builder) {
+  explicit DebugInfoWriter(ElfBuilder<ElfTypes>* builder)
+      : builder_(builder),
+        debug_abbrev_(&debug_abbrev_buffer_) {
   }
 
   void Start() {
@@ -1153,7 +1153,7 @@ class DebugInfoWriter {
     builder_->GetDebugInfo()->End();
     builder_->WritePatches(".debug_info.oat_patches",
                            ArrayRef<const uintptr_t>(debug_info_patches_));
-    builder_->WriteSection(".debug_abbrev", &debug_abbrev_.Data());
+    builder_->WriteSection(".debug_abbrev", &debug_abbrev_buffer_);
     builder_->WriteSection(".debug_str", &debug_str_.Data());
     builder_->WriteSection(".debug_loc", &debug_loc_);
     builder_->WriteSection(".debug_ranges", &debug_ranges_);
@@ -1166,7 +1166,8 @@ class DebugInfoWriter {
 
   ElfBuilder<ElfTypes>* builder_;
   std::vector<uintptr_t> debug_info_patches_;
-  DedupVector debug_abbrev_;
+  std::vector<uint8_t> debug_abbrev_buffer_;
+  DebugAbbrevWriter<> debug_abbrev_;
   DedupVector debug_str_;
   std::vector<uint8_t> debug_loc_;
   std::vector<uint8_t> debug_ranges_;
diff --git a/runtime/base/stl_util.h b/runtime/base/stl_util.h
index ad03c319d9..a53dcea2d7 100644
--- a/runtime/base/stl_util.h
+++ b/runtime/base/stl_util.h
@@ -156,6 +156,20 @@ struct CStringLess {
   }
 };
 
+// 32-bit FNV-1a hash function suitable for std::unordered_map.
+// It can be used with any container which works with range-based for loop.
+// See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
+template <typename Vector>
+struct FNVHash {
+  size_t operator()(const Vector& vector) const {
+    uint32_t hash = 2166136261u;
+    for (const auto& value : vector) {
+      hash = (hash ^ value) * 16777619u;
+    }
+    return hash;
+  }
+};
+
 // Use to suppress type deduction for a function argument.
 // See std::identity<> for more background:
 // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1856.html#20.2.2 - move/forward helpers