1 /*
2 * Copyright (C) 2015 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "stack_map.h"
18
19 #include <iomanip>
20 #include <stdint.h>
21
22 #include "art_method.h"
23 #include "base/indenter.h"
24 #include "base/stats-inl.h"
25 #include "oat_quick_method_header.h"
26 #include "scoped_thread_state_change-inl.h"
27
28 namespace art {
29
30 // The callback is used to inform the caller about memory bounds of the bit-tables.
31 template<typename DecodeCallback>
CodeInfo(const uint8_t * data,size_t * num_read_bits,DecodeCallback callback)32 CodeInfo::CodeInfo(const uint8_t* data, size_t* num_read_bits, DecodeCallback callback) {
33 BitMemoryReader reader(data);
34 std::array<uint32_t, kNumHeaders> header = reader.ReadInterleavedVarints<kNumHeaders>();
35 ForEachHeaderField([this, &header](size_t i, auto member_pointer) {
36 this->*member_pointer = header[i];
37 });
38 ForEachBitTableField([this, &reader, &callback](size_t i, auto member_pointer) {
39 auto& table = this->*member_pointer;
40 if (LIKELY(HasBitTable(i))) {
41 if (UNLIKELY(IsBitTableDeduped(i))) {
42 ssize_t bit_offset = reader.NumberOfReadBits() - reader.ReadVarint();
43 BitMemoryReader reader2(reader.data(), bit_offset); // The offset is negative.
44 table.Decode(reader2);
45 callback(i, &table, reader2.GetReadRegion());
46 } else {
47 ssize_t bit_offset = reader.NumberOfReadBits();
48 table.Decode(reader);
49 callback(i, &table, reader.GetReadRegion().Subregion(bit_offset));
50 }
51 }
52 });
53 if (num_read_bits != nullptr) {
54 *num_read_bits = reader.NumberOfReadBits();
55 }
56 }
57
CodeInfo(const uint8_t * data,size_t * num_read_bits)58 CodeInfo::CodeInfo(const uint8_t* data, size_t* num_read_bits)
59 : CodeInfo(data, num_read_bits, [](size_t, auto*, BitMemoryRegion){}) {}
60
CodeInfo(const OatQuickMethodHeader * header)61 CodeInfo::CodeInfo(const OatQuickMethodHeader* header)
62 : CodeInfo(header->GetOptimizedCodeInfoPtr()) {}
63
DecodeGcMasksOnly(const OatQuickMethodHeader * header)64 CodeInfo CodeInfo::DecodeGcMasksOnly(const OatQuickMethodHeader* header) {
65 CodeInfo code_info(header->GetOptimizedCodeInfoPtr());
66 CodeInfo copy; // Copy to dead-code-eliminate all fields that we do not need.
67 copy.stack_maps_ = code_info.stack_maps_;
68 copy.register_masks_ = code_info.register_masks_;
69 copy.stack_masks_ = code_info.stack_masks_;
70 return copy;
71 }
72
DecodeInlineInfoOnly(const OatQuickMethodHeader * header)73 CodeInfo CodeInfo::DecodeInlineInfoOnly(const OatQuickMethodHeader* header) {
74 CodeInfo code_info(header->GetOptimizedCodeInfoPtr());
75 CodeInfo copy; // Copy to dead-code-eliminate all fields that we do not need.
76 copy.number_of_dex_registers_ = code_info.number_of_dex_registers_;
77 copy.stack_maps_ = code_info.stack_maps_;
78 copy.inline_infos_ = code_info.inline_infos_;
79 copy.method_infos_ = code_info.method_infos_;
80 return copy;
81 }
82
Dedupe(const uint8_t * code_info_data)83 size_t CodeInfo::Deduper::Dedupe(const uint8_t* code_info_data) {
84 writer_.ByteAlign();
85 size_t deduped_offset = writer_.NumberOfWrittenBits() / kBitsPerByte;
86
87 // The back-reference offset takes space so dedupe is not worth it for tiny tables.
88 constexpr size_t kMinDedupSize = 32; // Assume 32-bit offset on average.
89
90 // Read the existing code info and find (and keep) dedup-map iterator for each table.
91 // The iterator stores BitMemoryRegion and bit_offset of previous identical BitTable.
92 std::map<BitMemoryRegion, uint32_t, BitMemoryRegion::Less>::iterator it[kNumBitTables];
93 CodeInfo code_info(code_info_data, nullptr, [&](size_t i, auto*, BitMemoryRegion region) {
94 it[i] = dedupe_map_.emplace(region, /*bit_offset=*/0).first;
95 if (it[i]->second != 0 && region.size_in_bits() > kMinDedupSize) { // Seen before and large?
96 code_info.SetBitTableDeduped(i); // Mark as deduped before we write header.
97 }
98 });
99
100 // Write the code info back, but replace deduped tables with relative offsets.
101 std::array<uint32_t, kNumHeaders> header;
102 ForEachHeaderField([&code_info, &header](size_t i, auto member_pointer) {
103 header[i] = code_info.*member_pointer;
104 });
105 writer_.WriteInterleavedVarints(header);
106 ForEachBitTableField([this, &code_info, &it](size_t i, auto) {
107 if (code_info.HasBitTable(i)) {
108 uint32_t& bit_offset = it[i]->second;
109 if (code_info.IsBitTableDeduped(i)) {
110 DCHECK_NE(bit_offset, 0u);
111 writer_.WriteVarint(writer_.NumberOfWrittenBits() - bit_offset);
112 } else {
113 bit_offset = writer_.NumberOfWrittenBits(); // Store offset in dedup map.
114 writer_.WriteRegion(it[i]->first);
115 }
116 }
117 });
118
119 if (kIsDebugBuild) {
120 CodeInfo old_code_info(code_info_data);
121 CodeInfo new_code_info(writer_.data() + deduped_offset);
122 ForEachHeaderField([&old_code_info, &new_code_info](size_t, auto member_pointer) {
123 if (member_pointer != &CodeInfo::bit_table_flags_) { // Expected to differ.
124 DCHECK_EQ(old_code_info.*member_pointer, new_code_info.*member_pointer);
125 }
126 });
127 ForEachBitTableField([&old_code_info, &new_code_info](size_t i, auto member_pointer) {
128 DCHECK_EQ(old_code_info.HasBitTable(i), new_code_info.HasBitTable(i));
129 DCHECK((old_code_info.*member_pointer).Equals(new_code_info.*member_pointer));
130 });
131 }
132
133 return deduped_offset;
134 }
135
GetStackMapForNativePcOffset(uintptr_t pc,InstructionSet isa) const136 StackMap CodeInfo::GetStackMapForNativePcOffset(uintptr_t pc, InstructionSet isa) const {
137 uint32_t packed_pc = StackMap::PackNativePc(pc, isa);
138 // Binary search. All catch stack maps are stored separately at the end.
139 auto it = std::partition_point(
140 stack_maps_.begin(),
141 stack_maps_.end(),
142 [packed_pc](const StackMap& sm) {
143 return sm.GetPackedNativePc() < packed_pc && sm.GetKind() != StackMap::Kind::Catch;
144 });
145 // Start at the lower bound and iterate over all stack maps with the given native pc.
146 for (; it != stack_maps_.end() && (*it).GetNativePcOffset(isa) == pc; ++it) {
147 StackMap::Kind kind = static_cast<StackMap::Kind>((*it).GetKind());
148 if (kind == StackMap::Kind::Default || kind == StackMap::Kind::OSR) {
149 return *it;
150 }
151 }
152 return stack_maps_.GetInvalidRow();
153 }
154
155 // Scan backward to determine dex register locations at given stack map.
156 // All registers for a stack map are combined - inlined registers are just appended,
157 // therefore 'first_dex_register' allows us to select a sub-range to decode.
DecodeDexRegisterMap(uint32_t stack_map_index,uint32_t first_dex_register,DexRegisterMap * map) const158 void CodeInfo::DecodeDexRegisterMap(uint32_t stack_map_index,
159 uint32_t first_dex_register,
160 /*out*/ DexRegisterMap* map) const {
161 // Count remaining work so we know when we have finished.
162 uint32_t remaining_registers = map->size();
163
164 // Keep scanning backwards and collect the most recent location of each register.
165 for (int32_t s = stack_map_index; s >= 0 && remaining_registers != 0; s--) {
166 StackMap stack_map = GetStackMapAt(s);
167 DCHECK_LE(stack_map_index - s, kMaxDexRegisterMapSearchDistance) << "Unbounded search";
168
169 // The mask specifies which registers where modified in this stack map.
170 // NB: the mask can be shorter than expected if trailing zero bits were removed.
171 uint32_t mask_index = stack_map.GetDexRegisterMaskIndex();
172 if (mask_index == StackMap::kNoValue) {
173 continue; // Nothing changed at this stack map.
174 }
175 BitMemoryRegion mask = dex_register_masks_.GetBitMemoryRegion(mask_index);
176 if (mask.size_in_bits() <= first_dex_register) {
177 continue; // Nothing changed after the first register we are interested in.
178 }
179
180 // The map stores one catalogue index per each modified register location.
181 uint32_t map_index = stack_map.GetDexRegisterMapIndex();
182 DCHECK_NE(map_index, StackMap::kNoValue);
183
184 // Skip initial registers which we are not interested in (to get to inlined registers).
185 map_index += mask.PopCount(0, first_dex_register);
186 mask = mask.Subregion(first_dex_register, mask.size_in_bits() - first_dex_register);
187
188 // Update registers that we see for first time (i.e. most recent value).
189 DexRegisterLocation* regs = map->data();
190 const uint32_t end = std::min<uint32_t>(map->size(), mask.size_in_bits());
191 const size_t kNumBits = BitSizeOf<uint32_t>();
192 for (uint32_t reg = 0; reg < end; reg += kNumBits) {
193 // Process the mask in chunks of kNumBits for performance.
194 uint32_t bits = mask.LoadBits(reg, std::min<uint32_t>(end - reg, kNumBits));
195 while (bits != 0) {
196 uint32_t bit = CTZ(bits);
197 if (regs[reg + bit].GetKind() == DexRegisterLocation::Kind::kInvalid) {
198 regs[reg + bit] = GetDexRegisterCatalogEntry(dex_register_maps_.Get(map_index));
199 remaining_registers--;
200 }
201 map_index++;
202 bits ^= 1u << bit; // Clear the bit.
203 }
204 }
205 }
206
207 // Set any remaining registers to None (which is the default state at first stack map).
208 if (remaining_registers != 0) {
209 DexRegisterLocation* regs = map->data();
210 for (uint32_t r = 0; r < map->size(); r++) {
211 if (regs[r].GetKind() == DexRegisterLocation::Kind::kInvalid) {
212 regs[r] = DexRegisterLocation::None();
213 }
214 }
215 }
216 }
217
218 // Decode the CodeInfo while collecting size statistics.
CollectSizeStats(const uint8_t * code_info_data,Stats & stats)219 void CodeInfo::CollectSizeStats(const uint8_t* code_info_data, /*out*/ Stats& stats) {
220 BitMemoryReader reader(code_info_data);
221 reader.ReadInterleavedVarints<kNumHeaders>();
222 stats["Header"].AddBits(reader.NumberOfReadBits());
223 size_t num_bits;
224 CodeInfo code_info(code_info_data, &num_bits, [&](size_t i, auto* table, BitMemoryRegion region) {
225 if (!code_info.IsBitTableDeduped(i)) {
226 Stats& table_stats = stats[table->GetName()];
227 table_stats.AddBits(region.size_in_bits());
228 table_stats["Header"].AddBits(region.size_in_bits() - table->DataBitSize());
229 const char* const* column_names = table->GetColumnNames();
230 for (size_t c = 0; c < table->NumColumns(); c++) {
231 if (table->NumColumnBits(c) > 0) {
232 Stats& column_stats = table_stats[column_names[c]];
233 column_stats.AddBits(table->NumRows() * table->NumColumnBits(c), table->NumRows());
234 }
235 }
236 }
237 });
238 stats.AddBytes(BitsToBytesRoundUp(num_bits));
239 }
240
Dump(VariableIndentationOutputStream * vios) const241 void DexRegisterMap::Dump(VariableIndentationOutputStream* vios) const {
242 if (HasAnyLiveDexRegisters()) {
243 ScopedIndentation indent1(vios);
244 for (size_t i = 0; i < size(); ++i) {
245 DexRegisterLocation reg = (*this)[i];
246 if (reg.IsLive()) {
247 vios->Stream() << "v" << i << ":" << reg << " ";
248 }
249 }
250 vios->Stream() << "\n";
251 }
252 }
253
Dump(VariableIndentationOutputStream * vios,uint32_t code_offset,bool verbose,InstructionSet instruction_set) const254 void CodeInfo::Dump(VariableIndentationOutputStream* vios,
255 uint32_t code_offset,
256 bool verbose,
257 InstructionSet instruction_set) const {
258 vios->Stream() << "CodeInfo"
259 << " CodeSize:" << code_size_
260 << " FrameSize:" << packed_frame_size_ * kStackAlignment
261 << " CoreSpillMask:" << std::hex << core_spill_mask_
262 << " FpSpillMask:" << std::hex << fp_spill_mask_
263 << " NumberOfDexRegisters:" << std::dec << number_of_dex_registers_
264 << "\n";
265 ScopedIndentation indent1(vios);
266 ForEachBitTableField([this, &vios, verbose](size_t, auto member_pointer) {
267 const auto& table = this->*member_pointer;
268 if (table.NumRows() != 0) {
269 vios->Stream() << table.GetName() << " BitSize=" << table.DataBitSize();
270 vios->Stream() << " Rows=" << table.NumRows() << " Bits={";
271 const char* const* column_names = table.GetColumnNames();
272 for (size_t c = 0; c < table.NumColumns(); c++) {
273 vios->Stream() << (c != 0 ? " " : "");
274 vios->Stream() << column_names[c] << "=" << table.NumColumnBits(c);
275 }
276 vios->Stream() << "}\n";
277 if (verbose) {
278 ScopedIndentation indent1(vios);
279 for (size_t r = 0; r < table.NumRows(); r++) {
280 vios->Stream() << "[" << std::right << std::setw(3) << r << "]={";
281 for (size_t c = 0; c < table.NumColumns(); c++) {
282 vios->Stream() << (c != 0 ? " " : "");
283 if (&table == static_cast<const void*>(&stack_masks_) ||
284 &table == static_cast<const void*>(&dex_register_masks_)) {
285 BitMemoryRegion bits = table.GetBitMemoryRegion(r, c);
286 for (size_t b = 0, e = bits.size_in_bits(); b < e; b++) {
287 vios->Stream() << bits.LoadBit(e - b - 1);
288 }
289 } else {
290 vios->Stream() << std::right << std::setw(8) << static_cast<int32_t>(table.Get(r, c));
291 }
292 }
293 vios->Stream() << "}\n";
294 }
295 }
296 }
297 });
298
299 // Display stack maps along with (live) Dex register maps.
300 if (verbose) {
301 for (StackMap stack_map : stack_maps_) {
302 stack_map.Dump(vios, *this, code_offset, instruction_set);
303 }
304 }
305 }
306
Dump(VariableIndentationOutputStream * vios,const CodeInfo & code_info,uint32_t code_offset,InstructionSet instruction_set) const307 void StackMap::Dump(VariableIndentationOutputStream* vios,
308 const CodeInfo& code_info,
309 uint32_t code_offset,
310 InstructionSet instruction_set) const {
311 const uint32_t pc_offset = GetNativePcOffset(instruction_set);
312 vios->Stream()
313 << "StackMap[" << Row() << "]"
314 << std::hex
315 << " (native_pc=0x" << code_offset + pc_offset
316 << ", dex_pc=0x" << GetDexPc()
317 << ", register_mask=0x" << code_info.GetRegisterMaskOf(*this)
318 << std::dec
319 << ", stack_mask=0b";
320 BitMemoryRegion stack_mask = code_info.GetStackMaskOf(*this);
321 for (size_t i = 0, e = stack_mask.size_in_bits(); i < e; ++i) {
322 vios->Stream() << stack_mask.LoadBit(e - i - 1);
323 }
324 switch (static_cast<Kind>(GetKind())) {
325 case Kind::Default: break;
326 case Kind::Catch: vios->Stream() << ", Catch"; break;
327 case Kind::OSR: vios->Stream() << ", OSR"; break;
328 case Kind::Debug: vios->Stream() << ", Debug"; break;
329 }
330 vios->Stream() << ")\n";
331 code_info.GetDexRegisterMapOf(*this).Dump(vios);
332 for (InlineInfo inline_info : code_info.GetInlineInfosOf(*this)) {
333 inline_info.Dump(vios, code_info, *this);
334 }
335 }
336
Dump(VariableIndentationOutputStream * vios,const CodeInfo & code_info,const StackMap & stack_map) const337 void InlineInfo::Dump(VariableIndentationOutputStream* vios,
338 const CodeInfo& code_info,
339 const StackMap& stack_map) const {
340 uint32_t depth = Row() - stack_map.GetInlineInfoIndex();
341 vios->Stream()
342 << "InlineInfo[" << Row() << "]"
343 << " (depth=" << depth
344 << std::hex
345 << ", dex_pc=0x" << GetDexPc();
346 if (EncodesArtMethod()) {
347 ScopedObjectAccess soa(Thread::Current());
348 vios->Stream() << ", method=" << GetArtMethod()->PrettyMethod();
349 } else {
350 vios->Stream()
351 << std::dec
352 << ", method_index=" << code_info.GetMethodIndexOf(*this);
353 }
354 vios->Stream() << ")\n";
355 code_info.GetInlineDexRegisterMapOf(stack_map, *this).Dump(vios);
356 }
357
358 } // namespace art
359