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 "nodes.h"
26 #include "stack_map.h"
27 
28 namespace art {
29 
30 // Helper to build art::StackMapStream::LocationCatalogEntriesIndices.
31 class LocationCatalogEntriesIndicesEmptyFn {
32  public:
MakeEmpty(std::pair<DexRegisterLocation,size_t> & item)33   void MakeEmpty(std::pair<DexRegisterLocation, size_t>& item) const {
34     item.first = DexRegisterLocation::None();
35   }
IsEmpty(const std::pair<DexRegisterLocation,size_t> & item)36   bool IsEmpty(const std::pair<DexRegisterLocation, size_t>& item) const {
37     return item.first == DexRegisterLocation::None();
38   }
39 };
40 
41 // Hash function for art::StackMapStream::LocationCatalogEntriesIndices.
42 // This hash function does not create collisions.
43 class DexRegisterLocationHashFn {
44  public:
operator()45   size_t operator()(DexRegisterLocation key) const {
46     // Concatenate `key`s fields to create a 64-bit value to be hashed.
47     int64_t kind_and_value =
48         (static_cast<int64_t>(key.kind_) << 32) | static_cast<int64_t>(key.value_);
49     return inner_hash_fn_(kind_and_value);
50   }
51  private:
52   std::hash<int64_t> inner_hash_fn_;
53 };
54 
55 
56 /**
57  * Collects and builds stack maps for a method. All the stack maps
58  * for a method are placed in a CodeInfo object.
59  */
60 class StackMapStream : public ValueObject {
61  public:
StackMapStream(ArenaAllocator * allocator)62   explicit StackMapStream(ArenaAllocator* allocator)
63       : allocator_(allocator),
64         stack_maps_(allocator->Adapter(kArenaAllocStackMapStream)),
65         location_catalog_entries_(allocator->Adapter(kArenaAllocStackMapStream)),
66         location_catalog_entries_indices_(allocator->Adapter(kArenaAllocStackMapStream)),
67         dex_register_locations_(allocator->Adapter(kArenaAllocStackMapStream)),
68         inline_infos_(allocator->Adapter(kArenaAllocStackMapStream)),
69         stack_mask_max_(-1),
70         dex_pc_max_(0),
71         register_mask_max_(0),
72         number_of_stack_maps_with_inline_info_(0),
73         dex_map_hash_to_stack_map_indices_(std::less<uint32_t>(),
74                                            allocator->Adapter(kArenaAllocStackMapStream)),
75         current_entry_(),
76         current_inline_info_(),
77         code_info_encoding_(allocator->Adapter(kArenaAllocStackMapStream)),
78         inline_info_size_(0),
79         dex_register_maps_size_(0),
80         stack_maps_size_(0),
81         dex_register_location_catalog_size_(0),
82         dex_register_location_catalog_start_(0),
83         dex_register_maps_start_(0),
84         inline_infos_start_(0),
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   // See runtime/stack_map.h to know what these fields contain.
96   struct StackMapEntry {
97     uint32_t dex_pc;
98     uint32_t native_pc_offset;
99     uint32_t register_mask;
100     BitVector* sp_mask;
101     uint32_t num_dex_registers;
102     uint8_t inlining_depth;
103     size_t dex_register_locations_start_index;
104     size_t inline_infos_start_index;
105     BitVector* live_dex_registers_mask;
106     uint32_t dex_register_map_hash;
107     size_t same_dex_register_map_as_;
108   };
109 
110   struct InlineInfoEntry {
111     uint32_t dex_pc;
112     uint32_t method_index;
113     InvokeType invoke_type;
114     uint32_t num_dex_registers;
115     BitVector* live_dex_registers_mask;
116     size_t dex_register_locations_start_index;
117   };
118 
119   void BeginStackMapEntry(uint32_t dex_pc,
120                           uint32_t native_pc_offset,
121                           uint32_t register_mask,
122                           BitVector* sp_mask,
123                           uint32_t num_dex_registers,
124                           uint8_t inlining_depth);
125   void EndStackMapEntry();
126 
127   void AddDexRegisterEntry(DexRegisterLocation::Kind kind, int32_t value);
128 
129   void BeginInlineInfoEntry(uint32_t method_index,
130                             uint32_t dex_pc,
131                             InvokeType invoke_type,
132                             uint32_t num_dex_registers);
133   void EndInlineInfoEntry();
134 
GetNumberOfStackMaps()135   size_t GetNumberOfStackMaps() const {
136     return stack_maps_.size();
137   }
138 
GetStackMap(size_t i)139   const StackMapEntry& GetStackMap(size_t i) const {
140     return stack_maps_[i];
141   }
142 
SetStackMapNativePcOffset(size_t i,uint32_t native_pc_offset)143   void SetStackMapNativePcOffset(size_t i, uint32_t native_pc_offset) {
144     stack_maps_[i].native_pc_offset = native_pc_offset;
145   }
146 
147   uint32_t ComputeMaxNativePcOffset() const;
148 
149   // Prepares the stream to fill in a memory region. Must be called before FillIn.
150   // Returns the size (in bytes) needed to store this stream.
151   size_t PrepareForFillIn();
152   void FillIn(MemoryRegion region);
153 
154  private:
155   size_t ComputeDexRegisterLocationCatalogSize() const;
156   size_t ComputeDexRegisterMapSize(uint32_t num_dex_registers,
157                                    const BitVector* live_dex_registers_mask) const;
158   size_t ComputeDexRegisterMapsSize() const;
159   void ComputeInlineInfoEncoding();
160 
161   // Returns the index of an entry with the same dex register map as the current_entry,
162   // or kNoSameDexMapFound if no such entry exists.
163   size_t FindEntryWithTheSameDexMap();
164   bool HaveTheSameDexMaps(const StackMapEntry& a, const StackMapEntry& b) const;
165   void FillInDexRegisterMap(DexRegisterMap dex_register_map,
166                             uint32_t num_dex_registers,
167                             const BitVector& live_dex_registers_mask,
168                             uint32_t start_index_in_dex_register_locations) const;
169 
170   void CheckDexRegisterMap(const CodeInfo& code_info,
171                            const DexRegisterMap& dex_register_map,
172                            size_t num_dex_registers,
173                            BitVector* live_dex_registers_mask,
174                            size_t dex_register_locations_index) const;
175   void CheckCodeInfo(MemoryRegion region) const;
176 
177   ArenaAllocator* allocator_;
178   ArenaVector<StackMapEntry> stack_maps_;
179 
180   // A catalog of unique [location_kind, register_value] pairs (per method).
181   ArenaVector<DexRegisterLocation> location_catalog_entries_;
182   // Map from Dex register location catalog entries to their indices in the
183   // location catalog.
184   using LocationCatalogEntriesIndices = ArenaHashMap<DexRegisterLocation,
185                                                      size_t,
186                                                      LocationCatalogEntriesIndicesEmptyFn,
187                                                      DexRegisterLocationHashFn>;
188   LocationCatalogEntriesIndices location_catalog_entries_indices_;
189 
190   // A set of concatenated maps of Dex register locations indices to `location_catalog_entries_`.
191   ArenaVector<size_t> dex_register_locations_;
192   ArenaVector<InlineInfoEntry> inline_infos_;
193   int stack_mask_max_;
194   uint32_t dex_pc_max_;
195   uint32_t register_mask_max_;
196   size_t number_of_stack_maps_with_inline_info_;
197 
198   ArenaSafeMap<uint32_t, ArenaVector<uint32_t>> dex_map_hash_to_stack_map_indices_;
199 
200   StackMapEntry current_entry_;
201   InlineInfoEntry current_inline_info_;
202   StackMapEncoding stack_map_encoding_;
203   InlineInfoEncoding inline_info_encoding_;
204   ArenaVector<uint8_t> code_info_encoding_;
205   size_t inline_info_size_;
206   size_t dex_register_maps_size_;
207   size_t stack_maps_size_;
208   size_t dex_register_location_catalog_size_;
209   size_t dex_register_location_catalog_start_;
210   size_t dex_register_maps_start_;
211   size_t inline_infos_start_;
212   size_t needed_size_;
213   uint32_t current_dex_register_;
214   bool in_inline_frame_;
215 
216   static constexpr uint32_t kNoSameDexMapFound = -1;
217 
218   DISALLOW_COPY_AND_ASSIGN(StackMapStream);
219 };
220 
221 }  // namespace art
222 
223 #endif  // ART_COMPILER_OPTIMIZING_STACK_MAP_STREAM_H_
224