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_stream.h" 18 19 namespace art { 20 21 void StackMapStream::BeginStackMapEntry(uint32_t dex_pc, 22 uint32_t native_pc_offset, 23 uint32_t register_mask, 24 BitVector* sp_mask, 25 uint32_t num_dex_registers, 26 uint8_t inlining_depth) { 27 DCHECK_EQ(0u, current_entry_.dex_pc) << "EndStackMapEntry not called after BeginStackMapEntry"; 28 current_entry_.dex_pc = dex_pc; 29 current_entry_.native_pc_offset = native_pc_offset; 30 current_entry_.register_mask = register_mask; 31 current_entry_.sp_mask = sp_mask; 32 current_entry_.num_dex_registers = num_dex_registers; 33 current_entry_.inlining_depth = inlining_depth; 34 current_entry_.dex_register_locations_start_index = dex_register_locations_.Size(); 35 current_entry_.inline_infos_start_index = inline_infos_.Size(); 36 current_entry_.dex_register_map_hash = 0; 37 current_entry_.same_dex_register_map_as_ = kNoSameDexMapFound; 38 if (num_dex_registers != 0) { 39 current_entry_.live_dex_registers_mask = 40 new (allocator_) ArenaBitVector(allocator_, num_dex_registers, true); 41 } else { 42 current_entry_.live_dex_registers_mask = nullptr; 43 } 44 45 if (sp_mask != nullptr) { 46 stack_mask_max_ = std::max(stack_mask_max_, sp_mask->GetHighestBitSet()); 47 } 48 if (inlining_depth > 0) { 49 number_of_stack_maps_with_inline_info_++; 50 } 51 52 dex_pc_max_ = std::max(dex_pc_max_, dex_pc); 53 native_pc_offset_max_ = std::max(native_pc_offset_max_, native_pc_offset); 54 register_mask_max_ = std::max(register_mask_max_, register_mask); 55 } 56 57 void StackMapStream::EndStackMapEntry() { 58 current_entry_.same_dex_register_map_as_ = FindEntryWithTheSameDexMap(); 59 stack_maps_.Add(current_entry_); 60 current_entry_ = StackMapEntry(); 61 } 62 63 void StackMapStream::AddDexRegisterEntry(uint16_t dex_register, 64 DexRegisterLocation::Kind kind, 65 int32_t value) { 66 DCHECK_LT(dex_register, current_entry_.num_dex_registers); 67 68 if (kind != DexRegisterLocation::Kind::kNone) { 69 // Ensure we only use non-compressed location kind at this stage. 70 DCHECK(DexRegisterLocation::IsShortLocationKind(kind)) 71 << DexRegisterLocation::PrettyDescriptor(kind); 72 DexRegisterLocation location(kind, value); 73 74 // Look for Dex register `location` in the location catalog (using the 75 // companion hash map of locations to indices). Use its index if it 76 // is already in the location catalog. If not, insert it (in the 77 // location catalog and the hash map) and use the newly created index. 78 auto it = location_catalog_entries_indices_.Find(location); 79 if (it != location_catalog_entries_indices_.end()) { 80 // Retrieve the index from the hash map. 81 dex_register_locations_.Add(it->second); 82 } else { 83 // Create a new entry in the location catalog and the hash map. 84 size_t index = location_catalog_entries_.Size(); 85 location_catalog_entries_.Add(location); 86 dex_register_locations_.Add(index); 87 location_catalog_entries_indices_.Insert(std::make_pair(location, index)); 88 } 89 90 current_entry_.live_dex_registers_mask->SetBit(dex_register); 91 current_entry_.dex_register_map_hash += 92 (1 << (dex_register % (sizeof(current_entry_.dex_register_map_hash) * kBitsPerByte))); 93 current_entry_.dex_register_map_hash += static_cast<uint32_t>(value); 94 current_entry_.dex_register_map_hash += static_cast<uint32_t>(kind); 95 } 96 } 97 98 void StackMapStream::AddInlineInfoEntry(uint32_t method_index) { 99 InlineInfoEntry entry; 100 entry.method_index = method_index; 101 inline_infos_.Add(entry); 102 } 103 104 size_t StackMapStream::PrepareForFillIn() { 105 int stack_mask_number_of_bits = stack_mask_max_ + 1; // Need room for max element too. 106 stack_mask_size_ = RoundUp(stack_mask_number_of_bits, kBitsPerByte) / kBitsPerByte; 107 inline_info_size_ = ComputeInlineInfoSize(); 108 dex_register_maps_size_ = ComputeDexRegisterMapsSize(); 109 stack_maps_size_ = stack_maps_.Size() 110 * StackMap::ComputeStackMapSize(stack_mask_size_, 111 inline_info_size_, 112 dex_register_maps_size_, 113 dex_pc_max_, 114 native_pc_offset_max_, 115 register_mask_max_); 116 dex_register_location_catalog_size_ = ComputeDexRegisterLocationCatalogSize(); 117 118 // Note: use RoundUp to word-size here if you want CodeInfo objects to be word aligned. 119 needed_size_ = CodeInfo::kFixedSize 120 + dex_register_location_catalog_size_ 121 + stack_maps_size_ 122 + dex_register_maps_size_ 123 + inline_info_size_; 124 125 dex_register_location_catalog_start_ = CodeInfo::kFixedSize; 126 stack_maps_start_ = dex_register_location_catalog_start_ + dex_register_location_catalog_size_; 127 dex_register_maps_start_ = stack_maps_start_ + stack_maps_size_; 128 inline_infos_start_ = dex_register_maps_start_ + dex_register_maps_size_; 129 130 return needed_size_; 131 } 132 133 size_t StackMapStream::ComputeDexRegisterLocationCatalogSize() const { 134 size_t size = DexRegisterLocationCatalog::kFixedSize; 135 for (size_t location_catalog_entry_index = 0; 136 location_catalog_entry_index < location_catalog_entries_.Size(); 137 ++location_catalog_entry_index) { 138 DexRegisterLocation dex_register_location = 139 location_catalog_entries_.Get(location_catalog_entry_index); 140 size += DexRegisterLocationCatalog::EntrySize(dex_register_location); 141 } 142 return size; 143 } 144 145 size_t StackMapStream::ComputeDexRegisterMapSize(const StackMapEntry& entry) const { 146 // Size of the map in bytes. 147 size_t size = DexRegisterMap::kFixedSize; 148 // Add the live bit mask for the Dex register liveness. 149 size += DexRegisterMap::GetLiveBitMaskSize(entry.num_dex_registers); 150 // Compute the size of the set of live Dex register entries. 151 size_t number_of_live_dex_registers = 0; 152 for (size_t dex_register_number = 0; 153 dex_register_number < entry.num_dex_registers; 154 ++dex_register_number) { 155 if (entry.live_dex_registers_mask->IsBitSet(dex_register_number)) { 156 ++number_of_live_dex_registers; 157 } 158 } 159 size_t map_entries_size_in_bits = 160 DexRegisterMap::SingleEntrySizeInBits(location_catalog_entries_.Size()) 161 * number_of_live_dex_registers; 162 size_t map_entries_size_in_bytes = 163 RoundUp(map_entries_size_in_bits, kBitsPerByte) / kBitsPerByte; 164 size += map_entries_size_in_bytes; 165 return size; 166 } 167 168 size_t StackMapStream::ComputeDexRegisterMapsSize() const { 169 size_t size = 0; 170 for (size_t i = 0; i < stack_maps_.Size(); ++i) { 171 StackMapEntry entry = stack_maps_.Get(i); 172 if (entry.same_dex_register_map_as_ == kNoSameDexMapFound) { 173 // Entries with the same dex map will have the same offset. 174 size += ComputeDexRegisterMapSize(entry); 175 } 176 } 177 return size; 178 } 179 180 size_t StackMapStream::ComputeInlineInfoSize() const { 181 return inline_infos_.Size() * InlineInfo::SingleEntrySize() 182 // For encoding the depth. 183 + (number_of_stack_maps_with_inline_info_ * InlineInfo::kFixedSize); 184 } 185 186 void StackMapStream::FillIn(MemoryRegion region) { 187 DCHECK_EQ(0u, current_entry_.dex_pc) << "EndStackMapEntry not called after BeginStackMapEntry"; 188 DCHECK_NE(0u, needed_size_) << "PrepareForFillIn not called before FillIn"; 189 190 CodeInfo code_info(region); 191 DCHECK_EQ(region.size(), needed_size_); 192 code_info.SetOverallSize(region.size()); 193 194 MemoryRegion dex_register_locations_region = region.Subregion( 195 dex_register_maps_start_, dex_register_maps_size_); 196 197 MemoryRegion inline_infos_region = region.Subregion( 198 inline_infos_start_, inline_info_size_); 199 200 code_info.SetEncoding(inline_info_size_, 201 dex_register_maps_size_, 202 dex_pc_max_, 203 native_pc_offset_max_, 204 register_mask_max_); 205 code_info.SetNumberOfStackMaps(stack_maps_.Size()); 206 code_info.SetStackMaskSize(stack_mask_size_); 207 DCHECK_EQ(code_info.GetStackMapsSize(), stack_maps_size_); 208 209 // Set the Dex register location catalog. 210 code_info.SetNumberOfDexRegisterLocationCatalogEntries(location_catalog_entries_.Size()); 211 MemoryRegion dex_register_location_catalog_region = region.Subregion( 212 dex_register_location_catalog_start_, dex_register_location_catalog_size_); 213 DexRegisterLocationCatalog dex_register_location_catalog(dex_register_location_catalog_region); 214 // Offset in `dex_register_location_catalog` where to store the next 215 // register location. 216 size_t location_catalog_offset = DexRegisterLocationCatalog::kFixedSize; 217 for (size_t i = 0, e = location_catalog_entries_.Size(); i < e; ++i) { 218 DexRegisterLocation dex_register_location = location_catalog_entries_.Get(i); 219 dex_register_location_catalog.SetRegisterInfo(location_catalog_offset, dex_register_location); 220 location_catalog_offset += DexRegisterLocationCatalog::EntrySize(dex_register_location); 221 } 222 // Ensure we reached the end of the Dex registers location_catalog. 223 DCHECK_EQ(location_catalog_offset, dex_register_location_catalog_region.size()); 224 225 uintptr_t next_dex_register_map_offset = 0; 226 uintptr_t next_inline_info_offset = 0; 227 for (size_t i = 0, e = stack_maps_.Size(); i < e; ++i) { 228 StackMap stack_map = code_info.GetStackMapAt(i); 229 StackMapEntry entry = stack_maps_.Get(i); 230 231 stack_map.SetDexPc(code_info, entry.dex_pc); 232 stack_map.SetNativePcOffset(code_info, entry.native_pc_offset); 233 stack_map.SetRegisterMask(code_info, entry.register_mask); 234 if (entry.sp_mask != nullptr) { 235 stack_map.SetStackMask(code_info, *entry.sp_mask); 236 } 237 238 if (entry.num_dex_registers == 0) { 239 // No dex map available. 240 stack_map.SetDexRegisterMapOffset(code_info, StackMap::kNoDexRegisterMap); 241 } else { 242 // Search for an entry with the same dex map. 243 if (entry.same_dex_register_map_as_ != kNoSameDexMapFound) { 244 // If we have a hit reuse the offset. 245 stack_map.SetDexRegisterMapOffset(code_info, 246 code_info.GetStackMapAt(entry.same_dex_register_map_as_) 247 .GetDexRegisterMapOffset(code_info)); 248 } else { 249 // New dex registers maps should be added to the stack map. 250 MemoryRegion register_region = 251 dex_register_locations_region.Subregion( 252 next_dex_register_map_offset, 253 ComputeDexRegisterMapSize(entry)); 254 next_dex_register_map_offset += register_region.size(); 255 DexRegisterMap dex_register_map(register_region); 256 stack_map.SetDexRegisterMapOffset( 257 code_info, register_region.start() - dex_register_locations_region.start()); 258 259 // Set the live bit mask. 260 dex_register_map.SetLiveBitMask(entry.num_dex_registers, *entry.live_dex_registers_mask); 261 262 // Set the dex register location mapping data. 263 for (size_t dex_register_number = 0, index_in_dex_register_locations = 0; 264 dex_register_number < entry.num_dex_registers; 265 ++dex_register_number) { 266 if (entry.live_dex_registers_mask->IsBitSet(dex_register_number)) { 267 size_t location_catalog_entry_index = 268 dex_register_locations_.Get(entry.dex_register_locations_start_index 269 + index_in_dex_register_locations); 270 dex_register_map.SetLocationCatalogEntryIndex( 271 index_in_dex_register_locations, 272 location_catalog_entry_index, 273 entry.num_dex_registers, 274 location_catalog_entries_.Size()); 275 ++index_in_dex_register_locations; 276 } 277 } 278 } 279 } 280 281 // Set the inlining info. 282 if (entry.inlining_depth != 0) { 283 MemoryRegion inline_region = inline_infos_region.Subregion( 284 next_inline_info_offset, 285 InlineInfo::kFixedSize + entry.inlining_depth * InlineInfo::SingleEntrySize()); 286 next_inline_info_offset += inline_region.size(); 287 InlineInfo inline_info(inline_region); 288 289 // Currently relative to the dex register map. 290 stack_map.SetInlineDescriptorOffset( 291 code_info, inline_region.start() - dex_register_locations_region.start()); 292 293 inline_info.SetDepth(entry.inlining_depth); 294 for (size_t j = 0; j < entry.inlining_depth; ++j) { 295 InlineInfoEntry inline_entry = inline_infos_.Get(j + entry.inline_infos_start_index); 296 inline_info.SetMethodReferenceIndexAtDepth(j, inline_entry.method_index); 297 } 298 } else { 299 if (inline_info_size_ != 0) { 300 stack_map.SetInlineDescriptorOffset(code_info, StackMap::kNoInlineInfo); 301 } 302 } 303 } 304 } 305 306 size_t StackMapStream::FindEntryWithTheSameDexMap() { 307 size_t current_entry_index = stack_maps_.Size(); 308 auto entries_it = dex_map_hash_to_stack_map_indices_.find(current_entry_.dex_register_map_hash); 309 if (entries_it == dex_map_hash_to_stack_map_indices_.end()) { 310 // We don't have a perfect hash functions so we need a list to collect all stack maps 311 // which might have the same dex register map. 312 GrowableArray<uint32_t> stack_map_indices(allocator_, 1); 313 stack_map_indices.Add(current_entry_index); 314 dex_map_hash_to_stack_map_indices_.Put(current_entry_.dex_register_map_hash, stack_map_indices); 315 return kNoSameDexMapFound; 316 } 317 318 // We might have collisions, so we need to check whether or not we really have a match. 319 for (size_t i = 0; i < entries_it->second.Size(); i++) { 320 size_t test_entry_index = entries_it->second.Get(i); 321 if (HaveTheSameDexMaps(stack_maps_.Get(test_entry_index), current_entry_)) { 322 return test_entry_index; 323 } 324 } 325 entries_it->second.Add(current_entry_index); 326 return kNoSameDexMapFound; 327 } 328 329 bool StackMapStream::HaveTheSameDexMaps(const StackMapEntry& a, const StackMapEntry& b) const { 330 if (a.live_dex_registers_mask == nullptr && b.live_dex_registers_mask == nullptr) { 331 return true; 332 } 333 if (a.live_dex_registers_mask == nullptr || b.live_dex_registers_mask == nullptr) { 334 return false; 335 } 336 if (a.num_dex_registers != b.num_dex_registers) { 337 return false; 338 } 339 340 int index_in_dex_register_locations = 0; 341 for (uint32_t i = 0; i < a.num_dex_registers; i++) { 342 if (a.live_dex_registers_mask->IsBitSet(i) != b.live_dex_registers_mask->IsBitSet(i)) { 343 return false; 344 } 345 if (a.live_dex_registers_mask->IsBitSet(i)) { 346 size_t a_loc = dex_register_locations_.Get( 347 a.dex_register_locations_start_index + index_in_dex_register_locations); 348 size_t b_loc = dex_register_locations_.Get( 349 b.dex_register_locations_start_index + index_in_dex_register_locations); 350 if (a_loc != b_loc) { 351 return false; 352 } 353 ++index_in_dex_register_locations; 354 } 355 } 356 return true; 357 } 358 359 } // namespace art 360