Delta-compress register maps in stack maps.
The register maps tend to be similar from stack map to stack map,
so instead of encoding them again, store only the modified ones.
The dex register bitmap stores the delta now - if register has
been modified since the previous stack map, the bit will be set.
The decoding logic scans backwards through stack maps until it
eventfully finds the most recent value of each register.
This CL saves ~2.5% of .oat file size (~10% of stackmap size).
Due to the scan, this makes dex register decoding slower by factor
of 2.5, but that still beats the old algorithm before refactoring.
Test: test-art-host-gtest-stack_map_test
Change-Id: Id5217a329eb757954e0c9447f38b05ec34118f84
diff --git a/compiler/optimizing/stack_map_stream.cc b/compiler/optimizing/stack_map_stream.cc
index 3685ab2..094b75d 100644
--- a/compiler/optimizing/stack_map_stream.cc
+++ b/compiler/optimizing/stack_map_stream.cc
@@ -46,6 +46,13 @@
uint8_t inlining_depth) {
DCHECK(!in_stack_map_) << "Mismatched Begin/End calls";
in_stack_map_ = true;
+ // num_dex_registers_ is the constant per-method number of registers.
+ // However we initially don't know what the value is, so lazily initialize it.
+ if (num_dex_registers_ == 0) {
+ num_dex_registers_ = num_dex_registers;
+ } else if (num_dex_registers > 0) {
+ DCHECK_EQ(num_dex_registers_, num_dex_registers) << "Inconsistent register count";
+ }
current_stack_map_ = StackMapEntry {
.packed_native_pc = StackMap::PackNativePc(native_pc_offset, instruction_set_),
@@ -85,7 +92,6 @@
}
CHECK_EQ(stack_map.HasInlineInfo(), (inlining_depth != 0));
CHECK_EQ(code_info.GetInlineDepthOf(stack_map), inlining_depth);
- CHECK_EQ(stack_map.HasDexRegisterMap(), (num_dex_registers != 0));
});
}
}
@@ -102,16 +108,14 @@
inline_infos_.Dedup(current_inline_infos_.data(), current_inline_infos_.size());
}
+ // Generate delta-compressed dex register map.
+ CreateDexRegisterMap();
+
stack_maps_.Add(current_stack_map_);
}
void StackMapStream::AddDexRegisterEntry(DexRegisterLocation::Kind kind, int32_t value) {
current_dex_registers_.push_back(DexRegisterLocation(kind, value));
-
- // We have collected all the dex registers for StackMap/InlineInfo - create the map.
- if (current_dex_registers_.size() == expected_num_dex_registers_) {
- CreateDexRegisterMap();
- }
}
void StackMapStream::AddInvoke(InvokeType invoke_type, uint32_t dex_method_index) {
@@ -142,14 +146,15 @@
in_inline_info_ = true;
DCHECK_EQ(expected_num_dex_registers_, current_dex_registers_.size());
+ expected_num_dex_registers_ += num_dex_registers;
+
InlineInfoEntry entry = {
.is_last = InlineInfo::kMore,
.dex_pc = dex_pc,
.method_info_index = kNoValue,
.art_method_hi = kNoValue,
.art_method_lo = kNoValue,
- .dex_register_mask_index = kNoValue,
- .dex_register_map_index = kNoValue,
+ .num_dex_registers = static_cast<uint32_t>(expected_num_dex_registers_),
};
if (EncodeArtMethodInInlineInfo(method)) {
entry.art_method_hi = High32Bits(reinterpret_cast<uintptr_t>(method));
@@ -164,9 +169,6 @@
}
current_inline_infos_.push_back(entry);
- current_dex_registers_.clear();
- expected_num_dex_registers_ = num_dex_registers;
-
if (kVerifyStackMaps) {
size_t stack_map_index = stack_maps_.size();
size_t depth = current_inline_infos_.size() - 1;
@@ -182,7 +184,6 @@
CHECK_EQ(method_infos_[inline_info.GetMethodInfoIndex()],
method->GetDexMethodIndexUnchecked());
}
- CHECK_EQ(inline_info.HasDexRegisterMap(), (num_dex_registers != 0));
});
}
}
@@ -193,56 +194,68 @@
DCHECK_EQ(expected_num_dex_registers_, current_dex_registers_.size());
}
-// Create dex register map (bitmap + indices + catalogue entries)
-// based on the currently accumulated list of DexRegisterLocations.
+// Create delta-compressed dex register map based on the current list of DexRegisterLocations.
+// All dex registers for a stack map are concatenated - inlined registers are just appended.
void StackMapStream::CreateDexRegisterMap() {
- // Create mask and map based on current registers.
+ // These are fields rather than local variables so that we can reuse the reserved memory.
temp_dex_register_mask_.ClearAllBits();
temp_dex_register_map_.clear();
+
+ // Ensure that the arrays that hold previous state are big enough to be safely indexed below.
+ if (previous_dex_registers_.size() < current_dex_registers_.size()) {
+ previous_dex_registers_.resize(current_dex_registers_.size(), DexRegisterLocation::None());
+ dex_register_timestamp_.resize(current_dex_registers_.size(), 0u);
+ }
+
+ // Set bit in the mask for each register that has been changed since the previous stack map.
+ // Modified registers are stored in the catalogue and the catalogue index added to the list.
for (size_t i = 0; i < current_dex_registers_.size(); i++) {
DexRegisterLocation reg = current_dex_registers_[i];
- if (reg.IsLive()) {
- DexRegisterEntry entry = DexRegisterEntry {
+ // Distance is difference between this index and the index of last modification.
+ uint32_t distance = stack_maps_.size() - dex_register_timestamp_[i];
+ if (previous_dex_registers_[i] != reg || distance > kMaxDexRegisterMapSearchDistance) {
+ DexRegisterEntry entry = DexRegisterEntry{
.kind = static_cast<uint32_t>(reg.GetKind()),
.packed_value = DexRegisterInfo::PackValue(reg.GetKind(), reg.GetValue()),
};
+ uint32_t index = reg.IsLive() ? dex_register_catalog_.Dedup(&entry) : kNoValue;
temp_dex_register_mask_.SetBit(i);
- temp_dex_register_map_.push_back(dex_register_catalog_.Dedup(&entry));
+ temp_dex_register_map_.push_back(index);
+ previous_dex_registers_[i] = reg;
+ dex_register_timestamp_[i] = stack_maps_.size();
}
}
- // Set the mask and map for the current StackMap/InlineInfo.
- uint32_t mask_index = StackMap::kNoValue; // Represents mask with all zero bits.
+ // Set the mask and map for the current StackMap (which includes inlined registers).
if (temp_dex_register_mask_.GetNumberOfBits() != 0) {
- mask_index = dex_register_masks_.Dedup(temp_dex_register_mask_.GetRawStorage(),
- temp_dex_register_mask_.GetNumberOfBits());
+ current_stack_map_.dex_register_mask_index =
+ dex_register_masks_.Dedup(temp_dex_register_mask_.GetRawStorage(),
+ temp_dex_register_mask_.GetNumberOfBits());
}
- uint32_t map_index = dex_register_maps_.Dedup(temp_dex_register_map_.data(),
- temp_dex_register_map_.size());
- if (!current_inline_infos_.empty()) {
- current_inline_infos_.back().dex_register_mask_index = mask_index;
- current_inline_infos_.back().dex_register_map_index = map_index;
- } else {
- current_stack_map_.dex_register_mask_index = mask_index;
- current_stack_map_.dex_register_map_index = map_index;
+ if (!current_dex_registers_.empty()) {
+ current_stack_map_.dex_register_map_index =
+ dex_register_maps_.Dedup(temp_dex_register_map_.data(),
+ temp_dex_register_map_.size());
}
if (kVerifyStackMaps) {
size_t stack_map_index = stack_maps_.size();
- int32_t depth = current_inline_infos_.size() - 1;
+ uint32_t depth = current_inline_infos_.size();
// We need to make copy of the current registers for later (when the check is run).
- auto expected_dex_registers = std::make_shared<std::vector<DexRegisterLocation>>(
+ auto expected_dex_registers = std::make_shared<dchecked_vector<DexRegisterLocation>>(
current_dex_registers_.begin(), current_dex_registers_.end());
dchecks_.emplace_back([=](const CodeInfo& code_info) {
StackMap stack_map = code_info.GetStackMapAt(stack_map_index);
- size_t num_dex_registers = expected_dex_registers->size();
- DexRegisterMap map = (depth == -1)
- ? code_info.GetDexRegisterMapOf(stack_map, num_dex_registers)
- : code_info.GetDexRegisterMapAtDepth(depth, stack_map, num_dex_registers);
- CHECK_EQ(map.size(), num_dex_registers);
- for (size_t r = 0; r < num_dex_registers; r++) {
- CHECK_EQ(expected_dex_registers->at(r), map.Get(r));
+ uint32_t expected_reg = 0;
+ for (DexRegisterLocation reg : code_info.GetDexRegisterMapOf(stack_map)) {
+ CHECK_EQ((*expected_dex_registers)[expected_reg++], reg);
}
+ for (uint32_t d = 0; d < depth; d++) {
+ for (DexRegisterLocation reg : code_info.GetDexRegisterMapAtDepth(d, stack_map)) {
+ CHECK_EQ((*expected_dex_registers)[expected_reg++], reg);
+ }
+ }
+ CHECK_EQ(expected_reg, expected_dex_registers->size());
});
}
}
@@ -290,6 +303,7 @@
dex_register_masks_.Encode(&out_, &bit_offset);
dex_register_maps_.Encode(&out_, &bit_offset);
dex_register_catalog_.Encode(&out_, &bit_offset);
+ EncodeVarintBits(&out_, &bit_offset, num_dex_registers_);
return UnsignedLeb128Size(out_.size()) + out_.size();
}
diff --git a/compiler/optimizing/stack_map_stream.h b/compiler/optimizing/stack_map_stream.h
index d634c70..02fb6cb 100644
--- a/compiler/optimizing/stack_map_stream.h
+++ b/compiler/optimizing/stack_map_stream.h
@@ -55,6 +55,8 @@
in_inline_info_(false),
current_inline_infos_(allocator->Adapter(kArenaAllocStackMapStream)),
current_dex_registers_(allocator->Adapter(kArenaAllocStackMapStream)),
+ previous_dex_registers_(allocator->Adapter(kArenaAllocStackMapStream)),
+ dex_register_timestamp_(allocator->Adapter(kArenaAllocStackMapStream)),
temp_dex_register_mask_(allocator, 32, true, kArenaAllocStackMapStream),
temp_dex_register_map_(allocator->Adapter(kArenaAllocStackMapStream)) {
}
@@ -113,8 +115,7 @@
uint32_t method_info_index;
uint32_t art_method_hi;
uint32_t art_method_lo;
- uint32_t dex_register_mask_index;
- uint32_t dex_register_map_index;
+ uint32_t num_dex_registers;
};
// The fields must be uint32_t and mirror the InvokeInfo accessor in stack_map.h!
@@ -147,6 +148,7 @@
BitmapTableBuilder dex_register_masks_;
BitTableBuilder<uint32_t> dex_register_maps_;
BitTableBuilder<DexRegisterEntry> dex_register_catalog_;
+ uint32_t num_dex_registers_ = 0; // TODO: Make this const and get the value in constructor.
ScopedArenaVector<uint8_t> out_;
BitTableBuilder<uint32_t> method_infos_;
@@ -159,6 +161,8 @@
StackMapEntry current_stack_map_;
ScopedArenaVector<InlineInfoEntry> current_inline_infos_;
ScopedArenaVector<DexRegisterLocation> current_dex_registers_;
+ ScopedArenaVector<DexRegisterLocation> previous_dex_registers_;
+ ScopedArenaVector<uint32_t> dex_register_timestamp_; // Stack map index of last change.
size_t expected_num_dex_registers_;
// Temporary variables used in CreateDexRegisterMap.
diff --git a/compiler/optimizing/stack_map_test.cc b/compiler/optimizing/stack_map_test.cc
index 77aa3ef..0be276c 100644
--- a/compiler/optimizing/stack_map_test.cc
+++ b/compiler/optimizing/stack_map_test.cc
@@ -358,13 +358,6 @@
ASSERT_EQ(Kind::kConstant, location1.GetKind());
ASSERT_EQ(0, location0.GetValue());
ASSERT_EQ(-2, location1.GetValue());
-
- // Test that the inline info dex register map deduplicated to the same offset as the stack map
- // one.
- ASSERT_TRUE(stack_map.HasInlineInfo());
- InlineInfo inline_info = code_info.GetInlineInfoAtDepth(stack_map, 0);
- EXPECT_EQ(inline_info.GetDexRegisterMapIndex(),
- stack_map.GetDexRegisterMapIndex());
}
}
@@ -466,13 +459,9 @@
ASSERT_EQ(2, dex_registers2.GetMachineRegister(0));
ASSERT_EQ(-2, dex_registers2.GetConstant(1));
- // Verify dex register map offsets.
- ASSERT_EQ(sm0.GetDexRegisterMapIndex(),
- sm1.GetDexRegisterMapIndex());
- ASSERT_NE(sm0.GetDexRegisterMapIndex(),
- sm2.GetDexRegisterMapIndex());
- ASSERT_NE(sm1.GetDexRegisterMapIndex(),
- sm2.GetDexRegisterMapIndex());
+ // Verify dex register mask offsets.
+ ASSERT_FALSE(sm1.HasDexRegisterMaskIndex()); // No delta.
+ ASSERT_TRUE(sm2.HasDexRegisterMaskIndex()); // Has delta.
}
TEST(StackMapTest, TestNoDexRegisterMap) {
@@ -649,8 +638,6 @@
ASSERT_EQ(80, dex_registers2.GetStackOffsetInBytes(0));
ASSERT_EQ(10, dex_registers2.GetConstant(1));
ASSERT_EQ(5, dex_registers2.GetMachineRegister(2));
-
- ASSERT_FALSE(if1_2.HasDexRegisterMap());
}
{
@@ -682,8 +669,6 @@
ASSERT_EQ(10u, if2_2.GetDexPc());
ASSERT_TRUE(if2_2.EncodesArtMethod());
- ASSERT_FALSE(if2_0.HasDexRegisterMap());
-
DexRegisterMap dex_registers1 = ci.GetDexRegisterMapAtDepth(1, sm3, 1);
ASSERT_EQ(2, dex_registers1.GetMachineRegister(0));