1 files changed, 161 insertions, 58 deletions

diff --git a/runtime/stack_map.cc b/runtime/stack_map.cc
index a5749b84a7..7e46eb7e47 100644
--- a/runtime/stack_map.cc
+++ b/runtime/stack_map.cc
@@ -21,58 +21,173 @@
 
 #include "art_method.h"
 #include "base/indenter.h"
+#include "base/stats.h"
+#include "oat_quick_method_header.h"
 #include "scoped_thread_state_change-inl.h"
 
 namespace art {
 
-std::ostream& operator<<(std::ostream& stream, const DexRegisterLocation& reg) {
-  using Kind = DexRegisterLocation::Kind;
-  switch (reg.GetKind()) {
-    case Kind::kNone:
-      return stream << "None";
-    case Kind::kInStack:
-      return stream << "sp+" << reg.GetValue();
-    case Kind::kInRegister:
-      return stream << "r" << reg.GetValue();
-    case Kind::kInRegisterHigh:
-      return stream << "r" << reg.GetValue() << "/hi";
-    case Kind::kInFpuRegister:
-      return stream << "f" << reg.GetValue();
-    case Kind::kInFpuRegisterHigh:
-      return stream << "f" << reg.GetValue() << "/hi";
-    case Kind::kConstant:
-      return stream << "#" << reg.GetValue();
-    default:
-      return stream << "DexRegisterLocation(" << static_cast<uint32_t>(reg.GetKind())
-                    << "," << reg.GetValue() << ")";
+CodeInfo::CodeInfo(const OatQuickMethodHeader* header)
+  : CodeInfo(header->GetOptimizedCodeInfoPtr()) {
+}
+
+void CodeInfo::Decode(const uint8_t* data) {
+  const uint8_t* begin = data;
+  frame_size_in_bytes_ = DecodeUnsignedLeb128(&data);
+  core_spill_mask_ = DecodeUnsignedLeb128(&data);
+  fp_spill_mask_ = DecodeUnsignedLeb128(&data);
+  number_of_dex_registers_ = DecodeUnsignedLeb128(&data);
+  BitMemoryReader reader(data, /* bit_offset */ 0);
+  stack_maps_.Decode(reader);
+  register_masks_.Decode(reader);
+  stack_masks_.Decode(reader);
+  invoke_infos_.Decode(reader);
+  inline_infos_.Decode(reader);
+  dex_register_masks_.Decode(reader);
+  dex_register_maps_.Decode(reader);
+  dex_register_catalog_.Decode(reader);
+  size_in_bits_ = (data - begin) * kBitsPerByte + reader.GetBitOffset();
+}
+
+BitTable<StackMap>::const_iterator CodeInfo::BinarySearchNativePc(uint32_t packed_pc) const {
+  return std::partition_point(
+      stack_maps_.begin(),
+      stack_maps_.end(),
+      [packed_pc](const StackMap& sm) {
+        return sm.GetPackedNativePc() < packed_pc && sm.GetKind() != StackMap::Kind::Catch;
+      });
+}
+
+StackMap CodeInfo::GetStackMapForNativePcOffset(uint32_t pc, InstructionSet isa) const {
+  auto it = BinarySearchNativePc(StackMap::PackNativePc(pc, isa));
+  // Start at the lower bound and iterate over all stack maps with the given native pc.
+  for (; it != stack_maps_.end() && (*it).GetNativePcOffset(isa) == pc; ++it) {
+    StackMap::Kind kind = static_cast<StackMap::Kind>((*it).GetKind());
+    if (kind == StackMap::Kind::Default || kind == StackMap::Kind::OSR) {
+      return *it;
+    }
   }
+  return stack_maps_.GetInvalidRow();
 }
 
-static void DumpDexRegisterMap(VariableIndentationOutputStream* vios,
-                               const DexRegisterMap& map) {
-  if (map.IsValid()) {
+// Scan backward to determine dex register locations at given stack map.
+// All registers for a stack map are combined - inlined registers are just appended,
+// therefore 'first_dex_register' allows us to select a sub-range to decode.
+void CodeInfo::DecodeDexRegisterMap(uint32_t stack_map_index,
+                                    uint32_t first_dex_register,
+                                    /*out*/ DexRegisterMap* map) const {
+  // Count remaining work so we know when we have finished.
+  uint32_t remaining_registers = map->size();
+
+  // Keep scanning backwards and collect the most recent location of each register.
+  for (int32_t s = stack_map_index; s >= 0 && remaining_registers != 0; s--) {
+    StackMap stack_map = GetStackMapAt(s);
+    DCHECK_LE(stack_map_index - s, kMaxDexRegisterMapSearchDistance) << "Unbounded search";
+
+    // The mask specifies which registers where modified in this stack map.
+    // NB: the mask can be shorter than expected if trailing zero bits were removed.
+    uint32_t mask_index = stack_map.GetDexRegisterMaskIndex();
+    if (mask_index == StackMap::kNoValue) {
+      continue;  // Nothing changed at this stack map.
+    }
+    BitMemoryRegion mask = dex_register_masks_.GetBitMemoryRegion(mask_index);
+    if (mask.size_in_bits() <= first_dex_register) {
+      continue;  // Nothing changed after the first register we are interested in.
+    }
+
+    // The map stores one catalogue index per each modified register location.
+    uint32_t map_index = stack_map.GetDexRegisterMapIndex();
+    DCHECK_NE(map_index, StackMap::kNoValue);
+
+    // Skip initial registers which we are not interested in (to get to inlined registers).
+    map_index += mask.PopCount(0, first_dex_register);
+    mask = mask.Subregion(first_dex_register, mask.size_in_bits() - first_dex_register);
+
+    // Update registers that we see for first time (i.e. most recent value).
+    DexRegisterLocation* regs = map->data();
+    const uint32_t end = std::min<uint32_t>(map->size(), mask.size_in_bits());
+    const size_t kNumBits = BitSizeOf<uint32_t>();
+    for (uint32_t reg = 0; reg < end; reg += kNumBits) {
+      // Process the mask in chunks of kNumBits for performance.
+      uint32_t bits = mask.LoadBits(reg, std::min<uint32_t>(end - reg, kNumBits));
+      while (bits != 0) {
+        uint32_t bit = CTZ(bits);
+        if (regs[reg + bit].GetKind() == DexRegisterLocation::Kind::kInvalid) {
+          regs[reg + bit] = GetDexRegisterCatalogEntry(dex_register_maps_.Get(map_index));
+          remaining_registers--;
+        }
+        map_index++;
+        bits ^= 1u << bit;  // Clear the bit.
+      }
+    }
+  }
+
+  // Set any remaining registers to None (which is the default state at first stack map).
+  if (remaining_registers != 0) {
+    DexRegisterLocation* regs = map->data();
+    for (uint32_t r = 0; r < map->size(); r++) {
+      if (regs[r].GetKind() == DexRegisterLocation::Kind::kInvalid) {
+        regs[r] = DexRegisterLocation::None();
+      }
+    }
+  }
+}
+
+template<typename Accessor>
+static void AddTableSizeStats(const char* table_name,
+                              const BitTable<Accessor>& table,
+                              /*out*/ Stats* parent) {
+  Stats* table_stats = parent->Child(table_name);
+  table_stats->AddBits(table.BitSize());
+  table_stats->Child("Header")->AddBits(table.HeaderBitSize());
+  const char* const* column_names = GetBitTableColumnNames<Accessor>();
+  for (size_t c = 0; c < table.NumColumns(); c++) {
+    if (table.NumColumnBits(c) > 0) {
+      Stats* column_stats = table_stats->Child(column_names[c]);
+      column_stats->AddBits(table.NumRows() * table.NumColumnBits(c), table.NumRows());
+    }
+  }
+}
+
+void CodeInfo::AddSizeStats(/*out*/ Stats* parent) const {
+  Stats* stats = parent->Child("CodeInfo");
+  stats->AddBytes(Size());
+  AddTableSizeStats<StackMap>("StackMaps", stack_maps_, stats);
+  AddTableSizeStats<RegisterMask>("RegisterMasks", register_masks_, stats);
+  AddTableSizeStats<MaskInfo>("StackMasks", stack_masks_, stats);
+  AddTableSizeStats<InvokeInfo>("InvokeInfos", invoke_infos_, stats);
+  AddTableSizeStats<InlineInfo>("InlineInfos", inline_infos_, stats);
+  AddTableSizeStats<MaskInfo>("DexRegisterMasks", dex_register_masks_, stats);
+  AddTableSizeStats<DexRegisterMapInfo>("DexRegisterMaps", dex_register_maps_, stats);
+  AddTableSizeStats<DexRegisterInfo>("DexRegisterCatalog", dex_register_catalog_, stats);
+}
+
+void DexRegisterMap::Dump(VariableIndentationOutputStream* vios) const {
+  if (HasAnyLiveDexRegisters()) {
     ScopedIndentation indent1(vios);
-    for (size_t i = 0; i < map.size(); ++i) {
-      if (map.IsDexRegisterLive(i)) {
-        vios->Stream() << "v" << i << ":" << map.Get(i) << " ";
+    for (size_t i = 0; i < size(); ++i) {
+      DexRegisterLocation reg = (*this)[i];
+      if (reg.IsLive()) {
+        vios->Stream() << "v" << i << ":" << reg << " ";
       }
     }
     vios->Stream() << "\n";
   }
 }
 
-template<uint32_t kNumColumns>
+template<typename Accessor>
 static void DumpTable(VariableIndentationOutputStream* vios,
                       const char* table_name,
-                      const BitTable<kNumColumns>& table,
+                      const BitTable<Accessor>& table,
                       bool verbose,
                       bool is_mask = false) {
   if (table.NumRows() != 0) {
-    vios->Stream() << table_name << " BitSize=" << table.NumRows() * table.NumRowBits();
+    vios->Stream() << table_name << " BitSize=" << table.BitSize();
     vios->Stream() << " Rows=" << table.NumRows() << " Bits={";
+    const char* const* column_names = GetBitTableColumnNames<Accessor>();
     for (size_t c = 0; c < table.NumColumns(); c++) {
       vios->Stream() << (c != 0 ? " " : "");
-      vios->Stream() << table.NumColumnBits(c);
+      vios->Stream() << column_names[c] << "=" << table.NumColumnBits(c);
     }
     vios->Stream() << "}\n";
     if (verbose) {
@@ -98,29 +213,27 @@ static void DumpTable(VariableIndentationOutputStream* vios,
 
 void CodeInfo::Dump(VariableIndentationOutputStream* vios,
                     uint32_t code_offset,
-                    uint16_t num_dex_registers,
                     bool verbose,
                     InstructionSet instruction_set,
                     const MethodInfo& method_info) const {
   vios->Stream()
       << "CodeInfo"
-      << " BitSize="  << size_ * kBitsPerByte
+      << " BitSize="  << size_in_bits_
       << "\n";
   ScopedIndentation indent1(vios);
-  DumpTable(vios, "StackMaps", stack_maps_, verbose);
-  DumpTable(vios, "RegisterMasks", register_masks_, verbose);
-  DumpTable(vios, "StackMasks", stack_masks_, verbose, true /* is_mask */);
-  DumpTable(vios, "InvokeInfos", invoke_infos_, verbose);
-  DumpTable(vios, "InlineInfos", inline_infos_, verbose);
-  DumpTable(vios, "DexRegisterMasks", dex_register_masks_, verbose, true /* is_mask */);
-  DumpTable(vios, "DexRegisterMaps", dex_register_maps_, verbose);
-  DumpTable(vios, "DexRegisterCatalog", dex_register_catalog_, verbose);
+  DumpTable<StackMap>(vios, "StackMaps", stack_maps_, verbose);
+  DumpTable<RegisterMask>(vios, "RegisterMasks", register_masks_, verbose);
+  DumpTable<MaskInfo>(vios, "StackMasks", stack_masks_, verbose, true /* is_mask */);
+  DumpTable<InvokeInfo>(vios, "InvokeInfos", invoke_infos_, verbose);
+  DumpTable<InlineInfo>(vios, "InlineInfos", inline_infos_, verbose);
+  DumpTable<MaskInfo>(vios, "DexRegisterMasks", dex_register_masks_, verbose, true /* is_mask */);
+  DumpTable<DexRegisterMapInfo>(vios, "DexRegisterMaps", dex_register_maps_, verbose);
+  DumpTable<DexRegisterInfo>(vios, "DexRegisterCatalog", dex_register_catalog_, verbose);
 
   // Display stack maps along with (live) Dex register maps.
   if (verbose) {
-    for (size_t i = 0; i < GetNumberOfStackMaps(); ++i) {
-      StackMap stack_map = GetStackMapAt(i);
-      stack_map.Dump(vios, *this, method_info, code_offset, num_dex_registers, instruction_set);
+    for (StackMap stack_map : stack_maps_) {
+      stack_map.Dump(vios, *this, method_info, code_offset, instruction_set);
     }
   }
 }
@@ -129,7 +242,6 @@ void StackMap::Dump(VariableIndentationOutputStream* vios,
                     const CodeInfo& code_info,
                     const MethodInfo& method_info,
                     uint32_t code_offset,
-                    uint16_t number_of_dex_registers,
                     InstructionSet instruction_set) const {
   const uint32_t pc_offset = GetNativePcOffset(instruction_set);
   vios->Stream()
@@ -145,22 +257,16 @@ void StackMap::Dump(VariableIndentationOutputStream* vios,
     vios->Stream() << stack_mask.LoadBit(e - i - 1);
   }
   vios->Stream() << ")\n";
-  DumpDexRegisterMap(vios, code_info.GetDexRegisterMapOf(*this, number_of_dex_registers));
-  uint32_t depth = code_info.GetInlineDepthOf(*this);
-  for (size_t d = 0; d < depth; d++) {
-    InlineInfo inline_info = code_info.GetInlineInfoAtDepth(*this, d);
-    // We do not know the length of the dex register maps of inlined frames
-    // at this level, so we just pass null to `InlineInfo::Dump` to tell
-    // it not to look at these maps.
-    inline_info.Dump(vios, code_info, *this, method_info, 0);
+  code_info.GetDexRegisterMapOf(*this).Dump(vios);
+  for (InlineInfo inline_info : code_info.GetInlineInfosOf(*this)) {
+    inline_info.Dump(vios, code_info, *this, method_info);
   }
 }
 
 void InlineInfo::Dump(VariableIndentationOutputStream* vios,
                       const CodeInfo& code_info,
                       const StackMap& stack_map,
-                      const MethodInfo& method_info,
-                      uint16_t number_of_dex_registers) const {
+                      const MethodInfo& method_info) const {
   uint32_t depth = Row() - stack_map.GetInlineInfoIndex();
   vios->Stream()
       << "InlineInfo[" << Row() << "]"
@@ -176,10 +282,7 @@ void InlineInfo::Dump(VariableIndentationOutputStream* vios,
         << ", method_index=" << GetMethodIndex(method_info);
   }
   vios->Stream() << ")\n";
-  if (number_of_dex_registers != 0) {
-    uint16_t vregs = number_of_dex_registers;
-    DumpDexRegisterMap(vios, code_info.GetDexRegisterMapAtDepth(depth, stack_map, vregs));
-  }
+  code_info.GetInlineDexRegisterMapOf(stack_map, *this).Dump(vios);
 }
 
 }  // namespace art