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/value_object.h"
     23 #include "memory_region.h"
     24 #include "nodes.h"
     25 #include "stack_map.h"
     26 #include "utils/growable_array.h"
     27 
     28 namespace art {
     29 
     30 // Helper to build art::StackMapStream::LocationCatalogEntriesIndices.
     31 class 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.
     43 class 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  */
     60 class StackMapStream : public ValueObject {
     61  public:
     62   explicit StackMapStream(ArenaAllocator* allocator)
     63       : allocator_(allocator),
     64         stack_maps_(allocator, 10),
     65         location_catalog_entries_(allocator, 4),
     66         dex_register_locations_(allocator, 10 * 4),
     67         inline_infos_(allocator, 2),
     68         stack_mask_max_(-1),
     69         dex_pc_max_(0),
     70         native_pc_offset_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>(), allocator->Adapter()),
     74         current_entry_(),
     75         stack_mask_size_(0),
     76         inline_info_size_(0),
     77         dex_register_maps_size_(0),
     78         stack_maps_size_(0),
     79         dex_register_location_catalog_size_(0),
     80         dex_register_location_catalog_start_(0),
     81         stack_maps_start_(0),
     82         dex_register_maps_start_(0),
     83         inline_infos_start_(0),
     84         needed_size_(0) {}
     85 
     86   // See runtime/stack_map.h to know what these fields contain.
     87   struct StackMapEntry {
     88     uint32_t dex_pc;
     89     uint32_t native_pc_offset;
     90     uint32_t register_mask;
     91     BitVector* sp_mask;
     92     uint32_t num_dex_registers;
     93     uint8_t inlining_depth;
     94     size_t dex_register_locations_start_index;
     95     size_t inline_infos_start_index;
     96     BitVector* live_dex_registers_mask;
     97     uint32_t dex_register_map_hash;
     98     size_t same_dex_register_map_as_;
     99   };
    100 
    101   struct InlineInfoEntry {
    102     uint32_t method_index;
    103   };
    104 
    105   void BeginStackMapEntry(uint32_t dex_pc,
    106                           uint32_t native_pc_offset,
    107                           uint32_t register_mask,
    108                           BitVector* sp_mask,
    109                           uint32_t num_dex_registers,
    110                           uint8_t inlining_depth);
    111   void EndStackMapEntry();
    112 
    113   void AddDexRegisterEntry(uint16_t dex_register,
    114                            DexRegisterLocation::Kind kind,
    115                            int32_t value);
    116 
    117   void AddInlineInfoEntry(uint32_t method_index);
    118 
    119   // Prepares the stream to fill in a memory region. Must be called before FillIn.
    120   // Returns the size (in bytes) needed to store this stream.
    121   size_t PrepareForFillIn();
    122   void FillIn(MemoryRegion region);
    123 
    124  private:
    125   size_t ComputeDexRegisterLocationCatalogSize() const;
    126   size_t ComputeDexRegisterMapSize(const StackMapEntry& entry) const;
    127   size_t ComputeDexRegisterMapsSize() const;
    128   size_t ComputeInlineInfoSize() const;
    129 
    130   // Returns the index of an entry with the same dex register map as the current_entry,
    131   // or kNoSameDexMapFound if no such entry exists.
    132   size_t FindEntryWithTheSameDexMap();
    133   bool HaveTheSameDexMaps(const StackMapEntry& a, const StackMapEntry& b) const;
    134 
    135   ArenaAllocator* allocator_;
    136   GrowableArray<StackMapEntry> stack_maps_;
    137 
    138   // A catalog of unique [location_kind, register_value] pairs (per method).
    139   GrowableArray<DexRegisterLocation> location_catalog_entries_;
    140   // Map from Dex register location catalog entries to their indices in the
    141   // location catalog.
    142   typedef HashMap<DexRegisterLocation, size_t, LocationCatalogEntriesIndicesEmptyFn,
    143                   DexRegisterLocationHashFn> LocationCatalogEntriesIndices;
    144   LocationCatalogEntriesIndices location_catalog_entries_indices_;
    145 
    146   // A set of concatenated maps of Dex register locations indices to `location_catalog_entries_`.
    147   GrowableArray<size_t> dex_register_locations_;
    148   GrowableArray<InlineInfoEntry> inline_infos_;
    149   int stack_mask_max_;
    150   uint32_t dex_pc_max_;
    151   uint32_t native_pc_offset_max_;
    152   uint32_t register_mask_max_;
    153   size_t number_of_stack_maps_with_inline_info_;
    154 
    155   ArenaSafeMap<uint32_t, GrowableArray<uint32_t>> dex_map_hash_to_stack_map_indices_;
    156 
    157   StackMapEntry current_entry_;
    158   size_t stack_mask_size_;
    159   size_t inline_info_size_;
    160   size_t dex_register_maps_size_;
    161   size_t stack_maps_size_;
    162   size_t dex_register_location_catalog_size_;
    163   size_t dex_register_location_catalog_start_;
    164   size_t stack_maps_start_;
    165   size_t dex_register_maps_start_;
    166   size_t inline_infos_start_;
    167   size_t needed_size_;
    168 
    169   static constexpr uint32_t kNoSameDexMapFound = -1;
    170 
    171   DISALLOW_COPY_AND_ASSIGN(StackMapStream);
    172 };
    173 
    174 }  // namespace art
    175 
    176 #endif  // ART_COMPILER_OPTIMIZING_STACK_MAP_STREAM_H_
    177