1 /* 2 * Copyright (C) 2014 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 #ifndef ART_COMPILER_OPTIMIZING_STACK_MAP_STREAM_H_ 18 #define ART_COMPILER_OPTIMIZING_STACK_MAP_STREAM_H_ 19 20 #include "base/bit_vector-inl.h" 21 #include "base/hash_map.h" 22 #include "base/scoped_arena_containers.h" 23 #include "base/value_object.h" 24 #include "memory_region.h" 25 #include "method_info.h" 26 #include "nodes.h" 27 #include "stack_map.h" 28 29 namespace art { 30 31 // Helper to build art::StackMapStream::LocationCatalogEntriesIndices. 32 class LocationCatalogEntriesIndicesEmptyFn { 33 public: 34 void MakeEmpty(std::pair<DexRegisterLocation, size_t>& item) const { 35 item.first = DexRegisterLocation::None(); 36 } 37 bool IsEmpty(const std::pair<DexRegisterLocation, size_t>& item) const { 38 return item.first == DexRegisterLocation::None(); 39 } 40 }; 41 42 // Hash function for art::StackMapStream::LocationCatalogEntriesIndices. 43 // This hash function does not create collisions. 44 class DexRegisterLocationHashFn { 45 public: 46 size_t operator()(DexRegisterLocation key) const { 47 // Concatenate `key`s fields to create a 64-bit value to be hashed. 48 int64_t kind_and_value = 49 (static_cast<int64_t>(key.kind_) << 32) | static_cast<int64_t>(key.value_); 50 return inner_hash_fn_(kind_and_value); 51 } 52 private: 53 std::hash<int64_t> inner_hash_fn_; 54 }; 55 56 57 /** 58 * Collects and builds stack maps for a method. All the stack maps 59 * for a method are placed in a CodeInfo object. 60 */ 61 class StackMapStream : public ValueObject { 62 public: 63 explicit StackMapStream(ScopedArenaAllocator* allocator, InstructionSet instruction_set) 64 : allocator_(allocator), 65 instruction_set_(instruction_set), 66 stack_maps_(allocator->Adapter(kArenaAllocStackMapStream)), 67 location_catalog_entries_(allocator->Adapter(kArenaAllocStackMapStream)), 68 location_catalog_entries_indices_(allocator->Adapter(kArenaAllocStackMapStream)), 69 dex_register_locations_(allocator->Adapter(kArenaAllocStackMapStream)), 70 inline_infos_(allocator->Adapter(kArenaAllocStackMapStream)), 71 stack_masks_(allocator->Adapter(kArenaAllocStackMapStream)), 72 register_masks_(allocator->Adapter(kArenaAllocStackMapStream)), 73 method_indices_(allocator->Adapter(kArenaAllocStackMapStream)), 74 dex_register_entries_(allocator->Adapter(kArenaAllocStackMapStream)), 75 stack_mask_max_(-1), 76 dex_pc_max_(kNoDexPc), 77 register_mask_max_(0), 78 number_of_stack_maps_with_inline_info_(0), 79 dex_map_hash_to_stack_map_indices_(std::less<uint32_t>(), 80 allocator->Adapter(kArenaAllocStackMapStream)), 81 current_entry_(), 82 current_inline_info_(), 83 code_info_encoding_(allocator->Adapter(kArenaAllocStackMapStream)), 84 needed_size_(0), 85 current_dex_register_(0), 86 in_inline_frame_(false) { 87 stack_maps_.reserve(10); 88 location_catalog_entries_.reserve(4); 89 dex_register_locations_.reserve(10 * 4); 90 inline_infos_.reserve(2); 91 code_info_encoding_.reserve(16); 92 } 93 94 // A dex register map entry for a single stack map entry, contains what registers are live as 95 // well as indices into the location catalog. 96 class DexRegisterMapEntry { 97 public: 98 static const size_t kOffsetUnassigned = -1; 99 100 BitVector* live_dex_registers_mask; 101 uint32_t num_dex_registers; 102 size_t locations_start_index; 103 // Computed fields 104 size_t hash = 0; 105 size_t offset = kOffsetUnassigned; 106 107 size_t ComputeSize(size_t catalog_size) const; 108 }; 109 110 // See runtime/stack_map.h to know what these fields contain. 111 struct StackMapEntry { 112 uint32_t dex_pc; 113 CodeOffset native_pc_code_offset; 114 uint32_t register_mask; 115 BitVector* sp_mask; 116 uint8_t inlining_depth; 117 size_t inline_infos_start_index; 118 uint32_t stack_mask_index; 119 uint32_t register_mask_index; 120 DexRegisterMapEntry dex_register_entry; 121 size_t dex_register_map_index; 122 InvokeType invoke_type; 123 uint32_t dex_method_index; 124 uint32_t dex_method_index_idx; // Index into dex method index table. 125 }; 126 127 struct InlineInfoEntry { 128 uint32_t dex_pc; // dex::kDexNoIndex for intrinsified native methods. 129 ArtMethod* method; 130 uint32_t method_index; 131 DexRegisterMapEntry dex_register_entry; 132 size_t dex_register_map_index; 133 uint32_t dex_method_index_idx; // Index into the dex method index table. 134 }; 135 136 void BeginStackMapEntry(uint32_t dex_pc, 137 uint32_t native_pc_offset, 138 uint32_t register_mask, 139 BitVector* sp_mask, 140 uint32_t num_dex_registers, 141 uint8_t inlining_depth); 142 void EndStackMapEntry(); 143 144 void AddDexRegisterEntry(DexRegisterLocation::Kind kind, int32_t value); 145 146 void AddInvoke(InvokeType type, uint32_t dex_method_index); 147 148 void BeginInlineInfoEntry(ArtMethod* method, 149 uint32_t dex_pc, 150 uint32_t num_dex_registers, 151 const DexFile* outer_dex_file = nullptr); 152 void EndInlineInfoEntry(); 153 154 size_t GetNumberOfStackMaps() const { 155 return stack_maps_.size(); 156 } 157 158 const StackMapEntry& GetStackMap(size_t i) const { 159 return stack_maps_[i]; 160 } 161 162 void SetStackMapNativePcOffset(size_t i, uint32_t native_pc_offset) { 163 stack_maps_[i].native_pc_code_offset = 164 CodeOffset::FromOffset(native_pc_offset, instruction_set_); 165 } 166 167 // Prepares the stream to fill in a memory region. Must be called before FillIn. 168 // Returns the size (in bytes) needed to store this stream. 169 size_t PrepareForFillIn(); 170 void FillInCodeInfo(MemoryRegion region); 171 void FillInMethodInfo(MemoryRegion region); 172 173 size_t ComputeMethodInfoSize() const; 174 175 private: 176 size_t ComputeDexRegisterLocationCatalogSize() const; 177 size_t ComputeDexRegisterMapsSize() const; 178 void ComputeInlineInfoEncoding(InlineInfoEncoding* encoding, 179 size_t dex_register_maps_bytes); 180 181 CodeOffset ComputeMaxNativePcCodeOffset() const; 182 183 // Returns the number of unique stack masks. 184 size_t PrepareStackMasks(size_t entry_size_in_bits); 185 186 // Returns the number of unique register masks. 187 size_t PrepareRegisterMasks(); 188 189 // Prepare and deduplicate method indices. 190 void PrepareMethodIndices(); 191 192 // Deduplicate entry if possible and return the corresponding index into dex_register_entries_ 193 // array. If entry is not a duplicate, a new entry is added to dex_register_entries_. 194 size_t AddDexRegisterMapEntry(const DexRegisterMapEntry& entry); 195 196 // Return true if the two dex register map entries are equal. 197 bool DexRegisterMapEntryEquals(const DexRegisterMapEntry& a, const DexRegisterMapEntry& b) const; 198 199 // Fill in the corresponding entries of a register map. 200 void ComputeInvokeInfoEncoding(CodeInfoEncoding* encoding); 201 202 // Returns the index of an entry with the same dex register map as the current_entry, 203 // or kNoSameDexMapFound if no such entry exists. 204 size_t FindEntryWithTheSameDexMap(); 205 bool HaveTheSameDexMaps(const StackMapEntry& a, const StackMapEntry& b) const; 206 207 // Fill in the corresponding entries of a register map. 208 void FillInDexRegisterMap(DexRegisterMap dex_register_map, 209 uint32_t num_dex_registers, 210 const BitVector& live_dex_registers_mask, 211 uint32_t start_index_in_dex_register_locations) const; 212 213 // Returns the offset for the dex register inside of the dex register location region. See FillIn. 214 // Only copies the dex register map if the offset for the entry is not already assigned. 215 size_t MaybeCopyDexRegisterMap(DexRegisterMapEntry& entry, 216 size_t* current_offset, 217 MemoryRegion dex_register_locations_region); 218 void CheckDexRegisterMap(const CodeInfo& code_info, 219 const DexRegisterMap& dex_register_map, 220 size_t num_dex_registers, 221 BitVector* live_dex_registers_mask, 222 size_t dex_register_locations_index) const; 223 void CheckCodeInfo(MemoryRegion region) const; 224 225 ScopedArenaAllocator* const allocator_; 226 const InstructionSet instruction_set_; 227 ScopedArenaVector<StackMapEntry> stack_maps_; 228 229 // A catalog of unique [location_kind, register_value] pairs (per method). 230 ScopedArenaVector<DexRegisterLocation> location_catalog_entries_; 231 // Map from Dex register location catalog entries to their indices in the 232 // location catalog. 233 using LocationCatalogEntriesIndices = ScopedArenaHashMap<DexRegisterLocation, 234 size_t, 235 LocationCatalogEntriesIndicesEmptyFn, 236 DexRegisterLocationHashFn>; 237 LocationCatalogEntriesIndices location_catalog_entries_indices_; 238 239 // A set of concatenated maps of Dex register locations indices to `location_catalog_entries_`. 240 ScopedArenaVector<size_t> dex_register_locations_; 241 ScopedArenaVector<InlineInfoEntry> inline_infos_; 242 ScopedArenaVector<uint8_t> stack_masks_; 243 ScopedArenaVector<uint32_t> register_masks_; 244 ScopedArenaVector<uint32_t> method_indices_; 245 ScopedArenaVector<DexRegisterMapEntry> dex_register_entries_; 246 int stack_mask_max_; 247 uint32_t dex_pc_max_; 248 uint32_t register_mask_max_; 249 size_t number_of_stack_maps_with_inline_info_; 250 251 ScopedArenaSafeMap<uint32_t, ScopedArenaVector<uint32_t>> dex_map_hash_to_stack_map_indices_; 252 253 StackMapEntry current_entry_; 254 InlineInfoEntry current_inline_info_; 255 ScopedArenaVector<uint8_t> code_info_encoding_; 256 size_t needed_size_; 257 uint32_t current_dex_register_; 258 bool in_inline_frame_; 259 260 static constexpr uint32_t kNoSameDexMapFound = -1; 261 262 DISALLOW_COPY_AND_ASSIGN(StackMapStream); 263 }; 264 265 } // namespace art 266 267 #endif // ART_COMPILER_OPTIMIZING_STACK_MAP_STREAM_H_ 268