Skip to content

Commit dc808f3

Browse files
sstricklcommit-bot@chromium.org
sstrickl
authored and
[email protected]
committed
[vm/compiler] Canonicalize CompressedStackMaps payloads when possible.
When we are writing a snapshot, canonicalize all entries within CompressedStackMaps payloads. We do this by creating a global table of stack map information (bit counts + bit payload) that we store in the isolate object store, and then for each existing CSM, we replace it with an alternate version that refers to the global table. This gets back some of the canonicalization we lost when we moved from individual StackMap objects to per-Code CompressedStackMaps objects. Here, we also represent the global table as a CompressedStackMaps object. This means that there are three types of CompressedStackMaps: * The original version that directly contains all entry information. * The version where each entry is just the PC offset delta and an offset into the global table payload. * A version representing the global table where the entries are like the original version except they don't contain a PC offset delta. ----- The impact on AOT snapshot size when compiling the Flutter Gallery in release mode: armv7: Total size -0.88% (Isolate RO: -5.05%, Isolate snapshot: +0.00%) armv8: Total size -1.04% (Isolate RO: -5.28%, Isolate snapshot: +0.00%) ----- Bug: #35274 Change-Id: I1ce0f8b3cc58e2f11584f3c218e0fdf8984b799b Cq-Include-Trybots: luci.dart.try:vm-kernel-precomp-linux-debug-x64-try,vm-kernel-precomp-linux-debug-simarm_x64-try Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/120667 Commit-Queue: Teagan Strickland <[email protected]> Reviewed-by: Martin Kustermann <[email protected]>
1 parent 6e85f33 commit dc808f3

12 files changed

Lines changed: 519 additions & 153 deletions

‎runtime/vm/bitmap_test.cc‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -56,8 +56,8 @@ ISOLATE_UNIT_TEST_CASE(BitmapBuilder) {
5656
EXPECT(it1.MoveNext());
5757

5858
EXPECT_EQ(kTestPcOffset, it1.pc_offset());
59-
EXPECT_EQ(kTestSpillSlotBitCount, it1.spill_slot_bit_count());
60-
EXPECT_EQ(1024, it1.length());
59+
EXPECT_EQ(kTestSpillSlotBitCount, it1.SpillSlotBitCount());
60+
EXPECT_EQ(1024, it1.Length());
6161
value = true;
6262
for (int32_t i = 0; i < 1024; i++) {
6363
EXPECT_EQ(value, it1.IsObject(i));
@@ -88,8 +88,8 @@ ISOLATE_UNIT_TEST_CASE(BitmapBuilder) {
8888
EXPECT(it2.MoveNext());
8989

9090
EXPECT_EQ(kTestPcOffset, it2.pc_offset());
91-
EXPECT_EQ(kTestSpillSlotBitCount, it2.spill_slot_bit_count());
92-
EXPECT_EQ(2049, it2.length());
91+
EXPECT_EQ(kTestSpillSlotBitCount, it2.SpillSlotBitCount());
92+
EXPECT_EQ(2049, it2.Length());
9393
for (int32_t i = 0; i <= 256; i++) {
9494
EXPECT(!it2.IsObject(i));
9595
}

‎runtime/vm/code_descriptors.cc‎

Lines changed: 79 additions & 43 deletions
Original file line numberDiff line numberDiff line change
@@ -47,7 +47,8 @@ RawPcDescriptors* DescriptorList::FinalizePcDescriptors(uword entry_point) {
4747
}
4848

4949
// Encode unsigned integer |value| in LEB128 format and store into |data|.
50-
static void EncodeLEB128(GrowableArray<uint8_t>* data, uintptr_t value) {
50+
void CompressedStackMapsBuilder::EncodeLEB128(GrowableArray<uint8_t>* data,
51+
uintptr_t value) {
5152
while (true) {
5253
uint8_t part = value & 0x7f;
5354
value >>= 7;
@@ -74,19 +75,20 @@ void CompressedStackMapsBuilder::AddEntry(intptr_t pc_offset,
7475

7576
RawCompressedStackMaps* CompressedStackMapsBuilder::Finalize() const {
7677
if (encoded_bytes_.length() == 0) return CompressedStackMaps::null();
77-
return CompressedStackMaps::New(encoded_bytes_);
78+
return CompressedStackMaps::NewInlined(encoded_bytes_);
7879
}
7980

80-
// Decode unsigned integer in LEB128 format from |data| and update |byte_index|.
81-
static uintptr_t DecodeLEB128(const uint8_t* data,
82-
const intptr_t data_length,
83-
intptr_t* byte_index) {
84-
ASSERT(*byte_index < data_length);
81+
// Decode unsigned integer in LEB128 format from the payload of |maps| and
82+
// update |byte_index|.
83+
uintptr_t CompressedStackMapsIterator::DecodeLEB128(
84+
const CompressedStackMaps& maps,
85+
uintptr_t* byte_index) {
8586
uword shift = 0;
8687
uintptr_t value = 0;
8788
uint8_t part = 0;
8889
do {
89-
part = data[(*byte_index)++];
90+
ASSERT(*byte_index < maps.payload_size());
91+
part = maps.PayloadByte((*byte_index)++);
9092
value |= static_cast<uintptr_t>(part & 0x7f) << shift;
9193
shift += 7;
9294
} while ((part & 0x80) != 0);
@@ -97,51 +99,85 @@ static uintptr_t DecodeLEB128(const uint8_t* data,
9799
bool CompressedStackMapsIterator::MoveNext() {
98100
// Empty CompressedStackMaps are represented as null values.
99101
if (maps_.IsNull() || next_offset_ >= maps_.payload_size()) return false;
100-
intptr_t offset = next_offset_;
101-
102-
// We decode three LEB128 encoded integers after this, so there should be
103-
// at least three bytes remaining in the payload.
104-
ASSERT(offset <= maps_.payload_size() - 3);
105-
auto const pc_delta =
106-
DecodeLEB128(maps_.Payload(), maps_.payload_size(), &offset);
107-
ASSERT(pc_delta <= kIntptrMax);
108-
109-
ASSERT(offset <= maps_.payload_size() - 2);
110-
auto const spill_slot_bit_count =
111-
DecodeLEB128(maps_.Payload(), maps_.payload_size(), &offset);
112-
ASSERT(spill_slot_bit_count <= kIntptrMax);
113-
114-
ASSERT(offset <= maps_.payload_size() - 1);
115-
auto const non_spill_slot_bit_count =
116-
DecodeLEB128(maps_.Payload(), maps_.payload_size(), &offset);
117-
ASSERT(non_spill_slot_bit_count <= kIntptrMax);
118-
119-
const auto stackmap_bits = spill_slot_bit_count + non_spill_slot_bit_count;
120-
const intptr_t stackmap_size =
121-
Utils::RoundUp(stackmap_bits, kBitsPerByte) >> kBitsPerByteLog2;
122-
const intptr_t space_remaining = maps_.payload_size() - offset;
123-
if (stackmap_size > space_remaining) return false;
102+
uintptr_t offset = next_offset_;
124103

125-
// Now that the current entry has been completely decoded without errors, set
126-
// the fields appropriately.
104+
auto const pc_delta = DecodeLEB128(maps_, &offset);
127105
ASSERT(pc_delta <= (kMaxUint32 - current_pc_offset_));
128106
current_pc_offset_ += pc_delta;
129-
current_spill_slot_bit_count_ = spill_slot_bit_count;
130-
current_non_spill_slot_bit_count_ = non_spill_slot_bit_count;
131-
current_bits_offset_ = offset;
132-
next_offset_ = offset + stackmap_size;
133107

108+
// Table-using CSMs have a table offset after the PC offset delta, whereas
109+
// the post-delta part of inlined entries has the same information as
110+
// global table entries.
111+
if (maps_.UsesGlobalTable()) {
112+
current_global_table_offset_ = DecodeLEB128(maps_, &offset);
113+
ASSERT(current_global_table_offset_ < bits_container_.payload_size());
114+
115+
// Since generally we only use entries in the GC and the GC only needs
116+
// the rest of the entry information if the PC offset matches, we lazily
117+
// load and cache the information stored in the global object when it is
118+
// actually requested.
119+
current_spill_slot_bit_count_ = -1;
120+
current_non_spill_slot_bit_count_ = -1;
121+
current_bits_offset_ = -1;
122+
} else {
123+
current_spill_slot_bit_count_ = DecodeLEB128(maps_, &offset);
124+
ASSERT(current_spill_slot_bit_count_ >= 0);
125+
126+
current_non_spill_slot_bit_count_ = DecodeLEB128(maps_, &offset);
127+
ASSERT(current_non_spill_slot_bit_count_ >= 0);
128+
129+
const auto stackmap_bits =
130+
current_spill_slot_bit_count_ + current_non_spill_slot_bit_count_;
131+
const uintptr_t stackmap_size =
132+
Utils::RoundUp(stackmap_bits, kBitsPerByte) >> kBitsPerByteLog2;
133+
ASSERT(stackmap_size <= (maps_.payload_size() - offset));
134+
135+
current_bits_offset_ = offset;
136+
offset += stackmap_size;
137+
}
138+
139+
next_offset_ = offset;
134140
return true;
135141
}
136142

137-
bool CompressedStackMapsIterator::IsObject(intptr_t bit_index) const {
138-
ASSERT(HasLoadedEntry());
139-
ASSERT(bit_index >= 0 && bit_index < length());
143+
intptr_t CompressedStackMapsIterator::Length() {
144+
EnsureFullyLoadedEntry();
145+
return current_spill_slot_bit_count_ + current_non_spill_slot_bit_count_;
146+
}
147+
intptr_t CompressedStackMapsIterator::SpillSlotBitCount() {
148+
EnsureFullyLoadedEntry();
149+
return current_spill_slot_bit_count_;
150+
}
151+
152+
bool CompressedStackMapsIterator::IsObject(intptr_t bit_index) {
153+
EnsureFullyLoadedEntry();
154+
ASSERT(!bits_container_.IsNull());
155+
ASSERT(bit_index >= 0 && bit_index < Length());
140156
const intptr_t byte_index = bit_index >> kBitsPerByteLog2;
141157
const intptr_t bit_remainder = bit_index & (kBitsPerByte - 1);
142158
uint8_t byte_mask = 1U << bit_remainder;
143-
uint8_t byte = maps_.Payload()[current_bits_offset_ + byte_index];
144-
return (byte & byte_mask) != 0;
159+
const intptr_t byte_offset = current_bits_offset_ + byte_index;
160+
return (bits_container_.PayloadByte(byte_offset) & byte_mask) != 0;
161+
}
162+
163+
void CompressedStackMapsIterator::LazyLoadGlobalTableEntry() {
164+
ASSERT(maps_.UsesGlobalTable() && bits_container_.IsGlobalTable());
165+
ASSERT(HasLoadedEntry());
166+
ASSERT(current_global_table_offset_ < bits_container_.payload_size());
167+
168+
uintptr_t offset = current_global_table_offset_;
169+
current_spill_slot_bit_count_ = DecodeLEB128(bits_container_, &offset);
170+
ASSERT(current_spill_slot_bit_count_ >= 0);
171+
172+
current_non_spill_slot_bit_count_ = DecodeLEB128(bits_container_, &offset);
173+
ASSERT(current_non_spill_slot_bit_count_ >= 0);
174+
175+
const auto stackmap_bits = Length();
176+
const uintptr_t stackmap_size =
177+
Utils::RoundUp(stackmap_bits, kBitsPerByte) >> kBitsPerByteLog2;
178+
ASSERT(stackmap_size <= (bits_container_.payload_size() - offset));
179+
180+
current_bits_offset_ = offset;
145181
}
146182

147183
RawExceptionHandlers* ExceptionHandlerList::FinalizeExceptionHandlers(

‎runtime/vm/code_descriptors.h‎

Lines changed: 32 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -48,6 +48,8 @@ class CompressedStackMapsBuilder : public ZoneAllocated {
4848
public:
4949
CompressedStackMapsBuilder() : encoded_bytes_() {}
5050

51+
static void EncodeLEB128(GrowableArray<uint8_t>* data, uintptr_t value);
52+
5153
void AddEntry(intptr_t pc_offset,
5254
BitmapBuilder* bitmap,
5355
intptr_t spill_slot_bit_count);
@@ -64,8 +66,16 @@ class CompressedStackMapsIterator : public ValueObject {
6466
public:
6567
// We use the null value to represent CompressedStackMaps with no
6668
// entries, so the constructor allows them.
69+
CompressedStackMapsIterator(const CompressedStackMaps& maps,
70+
const CompressedStackMaps& global_table)
71+
: maps_(maps),
72+
bits_container_(maps_.UsesGlobalTable() ? global_table : maps_) {
73+
ASSERT(!maps_.IsGlobalTable());
74+
ASSERT(!maps_.UsesGlobalTable() || bits_container_.IsGlobalTable());
75+
}
76+
6777
explicit CompressedStackMapsIterator(const CompressedStackMaps& maps)
68-
: maps_(maps) {}
78+
: CompressedStackMapsIterator(maps, CompressedStackMaps::Handle()) {}
6979

7080
// Loads the next entry from [maps_], if any. If [maps_] is the null
7181
// value, this always returns false.
@@ -91,25 +101,38 @@ class CompressedStackMapsIterator : public ValueObject {
91101
ASSERT(HasLoadedEntry());
92102
return current_pc_offset_;
93103
}
94-
intptr_t length() const {
95-
ASSERT(HasLoadedEntry());
96-
return current_spill_slot_bit_count_ + current_non_spill_slot_bit_count_;
97-
}
98-
intptr_t spill_slot_bit_count() const {
104+
// We lazily load and cache information from the global table if the
105+
// CSM uses it, so these methods cannot be const.
106+
intptr_t Length();
107+
intptr_t SpillSlotBitCount();
108+
bool IsObject(intptr_t bit_offset);
109+
110+
void EnsureFullyLoadedEntry() {
99111
ASSERT(HasLoadedEntry());
100-
return current_spill_slot_bit_count_;
112+
if (current_spill_slot_bit_count_ < 0) {
113+
LazyLoadGlobalTableEntry();
114+
}
115+
ASSERT(current_spill_slot_bit_count_ >= 0);
101116
}
102-
bool IsObject(intptr_t bit_offset) const;
103117

104118
private:
119+
static uintptr_t DecodeLEB128(const CompressedStackMaps& data,
120+
uintptr_t* byte_index);
105121
bool HasLoadedEntry() const { return next_offset_ > 0; }
122+
void LazyLoadGlobalTableEntry();
106123

107124
const CompressedStackMaps& maps_;
108-
intptr_t next_offset_ = 0;
125+
const CompressedStackMaps& bits_container_;
126+
127+
uintptr_t next_offset_ = 0;
109128
uint32_t current_pc_offset_ = 0;
129+
// Only used when looking up non-PC information in the global table.
130+
uintptr_t current_global_table_offset_ = 0;
110131
intptr_t current_spill_slot_bit_count_ = -1;
111132
intptr_t current_non_spill_slot_bit_count_ = -1;
112133
intptr_t current_bits_offset_ = -1;
134+
135+
friend class StackMapEntry;
113136
};
114137

115138
class ExceptionHandlerList : public ZoneAllocated {

‎runtime/vm/image_snapshot.cc‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -183,7 +183,7 @@ intptr_t ImageWriter::SizeInSnapshot(RawObject* raw_object) {
183183
case kCompressedStackMapsCid: {
184184
RawCompressedStackMaps* raw_maps =
185185
static_cast<RawCompressedStackMaps*>(raw_object);
186-
return CompressedStackMapsSizeInSnapshot(raw_maps->ptr()->payload_size_);
186+
return CompressedStackMapsSizeInSnapshot(raw_maps->ptr()->payload_size());
187187
}
188188
case kOneByteStringCid:
189189
case kTwoByteStringCid: {
@@ -381,9 +381,9 @@ void ImageWriter::WriteROData(WriteStream* stream) {
381381
marked_tags = RawObject::SizeTag::update(size_in_bytes * 2, marked_tags);
382382

383383
stream->WriteTargetWord(marked_tags);
384-
stream->WriteFixed<uint32_t>(payload_size);
385384
// We do not need to align the stream to a word boundary on 64-bit because
386385
// sizeof(RawCompressedStackMaps) is 12, even there.
386+
stream->WriteFixed<uint32_t>(map.raw()->ptr()->flags_and_size_);
387387
stream->WriteBytes(map.raw()->ptr()->data(), payload_size);
388388
stream->Align(compiler::target::ObjectAlignment::kObjectAlignment);
389389
} else if (obj.IsString()) {

‎runtime/vm/object.cc‎

Lines changed: 18 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -12962,22 +12962,23 @@ const char* CodeSourceMap::ToCString() const {
1296212962
return "CodeSourceMap";
1296312963
}
1296412964

12965-
intptr_t CompressedStackMaps::Hash() const {
12966-
uint32_t hash = 0;
12967-
for (intptr_t i = 0; i < payload_size(); i++) {
12968-
uint8_t byte = Payload()[i];
12965+
intptr_t CompressedStackMaps::Hashcode() const {
12966+
uint32_t hash = payload_size();
12967+
for (uintptr_t i = 0; i < payload_size(); i++) {
12968+
uint8_t byte = PayloadByte(i);
1296912969
hash = CombineHashes(hash, byte);
1297012970
}
1297112971
return FinalizeHash(hash, kHashBits);
1297212972
}
1297312973

1297412974
RawCompressedStackMaps* CompressedStackMaps::New(
12975-
const GrowableArray<uint8_t>& payload) {
12975+
const GrowableArray<uint8_t>& payload,
12976+
RawCompressedStackMaps::Kind kind) {
1297612977
ASSERT(Object::compressed_stackmaps_class() != Class::null());
1297712978
auto& result = CompressedStackMaps::Handle();
1297812979

1297912980
const uintptr_t payload_size = payload.length();
12980-
if (payload_size > kMaxInt32) {
12981+
if (!RawCompressedStackMaps::SizeField::is_valid(payload_size)) {
1298112982
FATAL1(
1298212983
"Fatal error in CompressedStackMaps::New: "
1298312984
"invalid payload size %" Pu "\n",
@@ -12991,7 +12992,7 @@ RawCompressedStackMaps* CompressedStackMaps::New(
1299112992
CompressedStackMaps::InstanceSize(payload_size), Heap::kOld);
1299212993
NoSafepointScope no_safepoint;
1299312994
result ^= raw;
12994-
result.set_payload_size(payload_size);
12995+
result.set_payload_size(payload_size, kind);
1299512996
}
1299612997
result.SetPayload(payload);
1299712998

@@ -13000,19 +13001,24 @@ RawCompressedStackMaps* CompressedStackMaps::New(
1300013001

1300113002
void CompressedStackMaps::SetPayload(
1300213003
const GrowableArray<uint8_t>& payload) const {
13003-
auto const array_length = payload.length();
13004+
const uintptr_t array_length = payload.length();
1300413005
ASSERT(array_length <= payload_size());
1300513006

1300613007
NoSafepointScope no_safepoint;
1300713008
uint8_t* payload_start = UnsafeMutableNonPointer(raw_ptr()->data());
13008-
for (intptr_t i = 0; i < array_length; i++) {
13009+
for (uintptr_t i = 0; i < array_length; i++) {
1300913010
payload_start[i] = payload.At(i);
1301013011
}
1301113012
}
1301213013

1301313014
const char* CompressedStackMaps::ToCString() const {
13014-
ZoneTextBuffer b(Thread::Current()->zone(), 100);
13015-
CompressedStackMapsIterator it(*this);
13015+
ASSERT(!IsGlobalTable());
13016+
auto const t = Thread::Current();
13017+
auto zone = t->zone();
13018+
ZoneTextBuffer b(zone, 100);
13019+
const auto& global_table = CompressedStackMaps::Handle(
13020+
zone, t->isolate()->object_store()->canonicalized_stack_map_entries());
13021+
CompressedStackMapsIterator it(*this, global_table);
1301613022
bool first_entry = true;
1301713023
while (it.MoveNext()) {
1301813024
if (first_entry) {
@@ -13021,7 +13027,7 @@ const char* CompressedStackMaps::ToCString() const {
1302113027
b.AddString("\n");
1302213028
}
1302313029
b.Printf("0x%08x: ", it.pc_offset());
13024-
for (intptr_t i = 0, n = it.length(); i < n; i++) {
13030+
for (intptr_t i = 0, n = it.Length(); i < n; i++) {
1302513031
b.AddString(it.IsObject(i) ? "1" : "0");
1302613032
}
1302713033
}

0 commit comments

Comments
 (0)