ART source line debug info in OAT files

OAT files have source line information enough for ART runtime needs like
jump to/from interpreter and thread suspension. But this information
is not enough for finer grained source level debugging and low-level
profiling (VTune or perf).

This patch adds to OAT files two additional sections:
.debug_line - DWARF formatted Elf32 section with detailed source line
              information (mapping from native PC to Java source lines).

In addition to the debugging symbols added using the dex2oat option
--include-debug-symbols, the source line information is added to
the section .debug_line.

The source line info can be read by many Elf reading tools like objdump,
readelf, dwarfdump, gdb, perf, VTune, ...

gdb can use this debug line information in x86. In 64-bit mode
the information can be used if the oat file is mapped in the lower
address space (address has higher 32 bits zeroed). Relocation works.

Testing:
1. art/test/run-test --host --gdb [--64] 001-HelloWorld
2. in gdb: break Main.java:19
3. in gdb: break Runtime.java:111
4. in gdb: run  - stops at void java.lang.Runtime.<init>()
5. in gdb: backtrace  - shows call stack down to main()
6. in gdb: continue - stops at void Main.main() (only in 32-bit mode)
7. in gdb: backtrace  - shows call stack down to main()
8. objdump -W <oat-file> - addresses are from VMA range of .text
   section reported by objdump -h <file>
9. dwarfdump -ka <oat-file> - no errors expected

Size of aosp-x86-eng boot.oat increased by 11% from 80.5Mb to 89.2Mb
with two sections added .debug_line (7.2Mb) and .rel.debug (1.5Mb).

Change-Id: Ib8828832686e49782a63d5529008ff4814ed9cda
Signed-off-by: Yevgeny Rouban <yevgeny.y.rouban@intel.com>
diff --git a/compiler/compiled_method.h b/compiler/compiled_method.h
index c98d06a..d02cbff 100644
--- a/compiler/compiled_method.h
+++ b/compiler/compiled_method.h
@@ -100,7 +100,97 @@
   std::vector<uint32_t> oatdata_offsets_to_compiled_code_offset_;
 };
 
-class CompiledMethod : public CompiledCode {
+class SrcMapElem {
+ public:
+  uint32_t from_;
+  int32_t to_;
+
+  bool operator<(const SrcMapElem& sme) const {
+    uint64_t lhs = (static_cast<uint64_t>(from_) << 32) + to_;
+    uint64_t rhs = (static_cast<uint64_t>(sme.from_) << 32) + sme.to_;
+    return lhs < rhs;
+  }
+
+  operator uint8_t() const {
+    return static_cast<uint8_t>(from_ + to_);
+  }
+};
+
+class SrcMap FINAL : public std::vector<SrcMapElem> {
+ public:
+  struct CompareByTo {
+    bool operator()(const SrcMapElem& lhs, const SrcMapElem& rhs) {
+      return lhs.to_ < rhs.to_;
+    }
+  };
+
+  struct CompareByFrom {
+    bool operator()(const SrcMapElem& lhs, const SrcMapElem& rhs) {
+      return lhs.from_ < rhs.from_;
+    }
+  };
+
+  void SortByTo() {
+    std::sort(begin(), end(), CompareByTo());
+  }
+
+  void SortByFrom() {
+    std::sort(begin(), end(), CompareByFrom());
+  }
+
+  const_iterator FindByTo(int32_t to) const {
+    return std::lower_bound(begin(), end(), SrcMapElem({0, to}), CompareByTo());
+  }
+
+  SrcMap& Arrange() {
+    SortByTo();
+
+    // Remove duplicate pairs.
+    if (!empty()) {
+      SrcMap tmp;
+      tmp.swap(*this);
+      iterator it = tmp.begin();
+      iterator prev = it;
+      it++;
+      push_back(*prev);
+      for (; it != tmp.end(); it++) {
+        if (prev->from_ != it->from_ || prev->to_ != it->to_) {
+          push_back(*(prev = it));
+        }
+      }
+    }
+    return *this;
+  }
+
+  void DeltaFormat(const SrcMapElem& start, uint32_t highest_pc) {
+    // Convert from abs values to deltas.
+    if (!empty()) {
+      SortByFrom();
+
+      // TODO: one PC can be mapped to several Java src lines.
+      // do we want such a one-to-many correspondence?
+
+      // get rid of the highest values
+      size_t i = size() - 1;
+      for (; i > 0 ; i--) {
+        if ((*this)[i].from_ >= highest_pc) {
+          break;
+        }
+      }
+      this->resize(i + 1);
+
+      for (size_t i = size(); --i >= 1; ) {
+        (*this)[i].from_ -= (*this)[i-1].from_;
+        (*this)[i].to_ -= (*this)[i-1].to_;
+      }
+      DCHECK((*this)[0].from_ >= start.from_);
+      (*this)[0].from_ -= start.from_;
+      (*this)[0].to_ -= start.to_;
+    }
+  }
+};
+
+class CompiledMethod FINAL : public CompiledCode {
  public:
   // Constructs a CompiledMethod for the non-LLVM compilers.
   CompiledMethod(CompilerDriver* driver,
@@ -109,6 +199,7 @@
                  const size_t frame_size_in_bytes,
                  const uint32_t core_spill_mask,
                  const uint32_t fp_spill_mask,
+                 SrcMap* src_mapping_table,
                  const std::vector<uint8_t>& mapping_table,
                  const std::vector<uint8_t>& vmap_table,
                  const std::vector<uint8_t>& native_gc_map,
@@ -145,6 +236,11 @@
     return fp_spill_mask_;
   }
 
+  const SrcMap& GetSrcMappingTable() const {
+    DCHECK(src_mapping_table_ != nullptr);
+    return *src_mapping_table_;
+  }
+
   const std::vector<uint8_t>& GetMappingTable() const {
     DCHECK(mapping_table_ != nullptr);
     return *mapping_table_;
@@ -171,6 +267,8 @@
   const uint32_t core_spill_mask_;
   // For quick code, a bit mask describing spilled FPR callee-save registers.
   const uint32_t fp_spill_mask_;
+  // For quick code, a set of pairs (PC, Line) mapping from native PC offset to Java line
+  SrcMap* src_mapping_table_;
   // For quick code, a uleb128 encoded map from native PC offset to dex PC aswell as dex PC to
   // native PC offset. Size prefixed.
   std::vector<uint8_t>* mapping_table_;