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
28namespace art {
29
30// Helper to build art::StackMapStream::LocationCatalogEntriesIndices.
31class LocationCatalogEntriesIndicesEmptyFn {
32 public:
33  void MakeEmpty(std::pair<DexRegisterLocation, size_t>& item) const {
34    item.first = DexRegisterLocation::None();
35  }
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.
43class DexRegisterLocationHashFn {
44 public:
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 */
60class StackMapStream : public ValueObject {
61 public:
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
135  size_t GetNumberOfStackMaps() const {
136    return stack_maps_.size();
137  }
138
139  const StackMapEntry& GetStackMap(size_t i) const {
140    return stack_maps_[i];
141  }
142
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