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
29namespace art {
30
31// Helper to build art::StackMapStream::LocationCatalogEntriesIndices.
32class 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.
44class 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 */
61class 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