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