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/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:
     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(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