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:
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(ScopedArenaAllocator * allocator,InstructionSet instruction_set)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 
GetNumberOfStackMaps()154   size_t GetNumberOfStackMaps() const {
155     return stack_maps_.size();
156   }
157 
GetStackMap(size_t i)158   const StackMapEntry& GetStackMap(size_t i) const {
159     return stack_maps_[i];
160   }
161 
SetStackMapNativePcOffset(size_t i,uint32_t native_pc_offset)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