Home | History | Annotate | Download | only in optimizing 
      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:
     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.
     44 class 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  */
     61 class StackMapStream : public ValueObject {
     62  public:
     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 
    155   size_t GetNumberOfStackMaps() const {
    156     return stack_maps_.size();
    157   }
    158 
    159   const StackMapEntry& GetStackMap(size_t i) const {
    160     return stack_maps_[i];
    161   }
    162 
    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