Rewrite dex register map encoding in stackmaps.
Simplify code by encoding dex register maps using BitTables.
The overall design is unchanged (bitmask+indices+catalogue).
This CL saves ~0.4% of .oat file size.
The dex register map decoding is factor of 3 faster now
(based on the time to verify the register maps on Arm).
This is not too surprising as the old version was O(n^2).
It also reduces compiler arena memory usage by 11% since the
BitTableBuilder is more memory efficient, we store less
intermediate data, and we deduplicate most data on the fly.
Test: test-art-host-gtest-stack_map_test
Change-Id: Ib703a5ddf7f581280522d589e4a2bfebe53c26a9
diff --git a/compiler/optimizing/stack_map_stream.h b/compiler/optimizing/stack_map_stream.h
index 6d505b9..cefe165 100644
--- a/compiler/optimizing/stack_map_stream.h
+++ b/compiler/optimizing/stack_map_stream.h
@@ -17,42 +17,20 @@
#ifndef ART_COMPILER_OPTIMIZING_STACK_MAP_STREAM_H_
#define ART_COMPILER_OPTIMIZING_STACK_MAP_STREAM_H_
+#include "base/allocator.h"
+#include "base/arena_bit_vector.h"
+#include "base/bit_table.h"
#include "base/bit_vector-inl.h"
-#include "base/hash_map.h"
#include "base/memory_region.h"
#include "base/scoped_arena_containers.h"
#include "base/value_object.h"
+#include "dex_register_location.h"
#include "method_info.h"
#include "nodes.h"
-#include "stack_map.h"
namespace art {
-// Helper to build art::StackMapStream::LocationCatalogEntriesIndices.
-class LocationCatalogEntriesIndicesEmptyFn {
- public:
- void MakeEmpty(std::pair<DexRegisterLocation, size_t>& item) const {
- item.first = DexRegisterLocation::None();
- }
- bool IsEmpty(const std::pair<DexRegisterLocation, size_t>& item) const {
- return item.first == DexRegisterLocation::None();
- }
-};
-
-// Hash function for art::StackMapStream::LocationCatalogEntriesIndices.
-// This hash function does not create collisions.
-class DexRegisterLocationHashFn {
- public:
- size_t operator()(DexRegisterLocation key) const {
- // Concatenate `key`s fields to create a 64-bit value to be hashed.
- int64_t kind_and_value =
- (static_cast<int64_t>(key.kind_) << 32) | static_cast<int64_t>(key.value_);
- return inner_hash_fn_(kind_and_value);
- }
- private:
- std::hash<int64_t> inner_hash_fn_;
-};
-
+class DexRegisterMap;
/**
* Collects and builds stack maps for a method. All the stack maps
@@ -61,71 +39,26 @@
class StackMapStream : public ValueObject {
public:
explicit StackMapStream(ScopedArenaAllocator* allocator, InstructionSet instruction_set)
- : allocator_(allocator),
- instruction_set_(instruction_set),
- stack_maps_(allocator->Adapter(kArenaAllocStackMapStream)),
- location_catalog_entries_(allocator->Adapter(kArenaAllocStackMapStream)),
- location_catalog_entries_indices_(allocator->Adapter(kArenaAllocStackMapStream)),
- dex_register_locations_(allocator->Adapter(kArenaAllocStackMapStream)),
- inline_infos_(allocator->Adapter(kArenaAllocStackMapStream)),
- method_indices_(allocator->Adapter(kArenaAllocStackMapStream)),
- dex_register_entries_(allocator->Adapter(kArenaAllocStackMapStream)),
+ : instruction_set_(instruction_set),
+ stack_maps_(allocator),
+ register_masks_(allocator),
+ stack_masks_(allocator),
+ invoke_infos_(allocator),
+ inline_infos_(allocator),
+ dex_register_masks_(allocator),
+ dex_register_maps_(allocator),
+ dex_register_catalog_(allocator),
out_(allocator->Adapter(kArenaAllocStackMapStream)),
- dex_map_hash_to_stack_map_indices_(std::less<uint32_t>(),
- allocator->Adapter(kArenaAllocStackMapStream)),
- current_entry_(),
- current_inline_info_(),
- current_dex_register_(0),
- in_inline_frame_(false) {
- stack_maps_.reserve(10);
- out_.reserve(64);
- location_catalog_entries_.reserve(4);
- dex_register_locations_.reserve(10 * 4);
- inline_infos_.reserve(2);
+ method_infos_(allocator),
+ lazy_stack_masks_(allocator->Adapter(kArenaAllocStackMapStream)),
+ in_stack_map_(false),
+ in_inline_info_(false),
+ current_inline_infos_(0),
+ current_dex_registers_(allocator->Adapter(kArenaAllocStackMapStream)),
+ temp_dex_register_mask_(allocator, 32, true, kArenaAllocStackMapStream),
+ temp_dex_register_map_(allocator->Adapter(kArenaAllocStackMapStream)) {
}
- // A dex register map entry for a single stack map entry, contains what registers are live as
- // well as indices into the location catalog.
- class DexRegisterMapEntry {
- public:
- static const uint32_t kOffsetUnassigned = -1;
-
- BitVector* live_dex_registers_mask;
- uint32_t num_dex_registers;
- size_t locations_start_index;
- // Computed fields
- size_t hash = 0;
- uint32_t offset = kOffsetUnassigned;
-
- size_t ComputeSize(size_t catalog_size) const;
- };
-
- // See runtime/stack_map.h to know what these fields contain.
- struct StackMapEntry {
- uint32_t dex_pc;
- uint32_t packed_native_pc;
- uint32_t register_mask;
- BitVector* sp_mask;
- uint32_t inlining_depth;
- size_t inline_infos_start_index;
- uint32_t stack_mask_index;
- uint32_t register_mask_index;
- DexRegisterMapEntry dex_register_entry;
- size_t dex_register_map_index;
- InvokeType invoke_type;
- uint32_t dex_method_index;
- uint32_t dex_method_index_idx; // Index into dex method index table.
- };
-
- struct InlineInfoEntry {
- uint32_t dex_pc; // dex::kDexNoIndex for intrinsified native methods.
- ArtMethod* method;
- uint32_t method_index;
- DexRegisterMapEntry dex_register_entry;
- size_t dex_register_map_index;
- uint32_t dex_method_index_idx; // Index into the dex method index table.
- };
-
void BeginStackMapEntry(uint32_t dex_pc,
uint32_t native_pc_offset,
uint32_t register_mask,
@@ -160,58 +93,87 @@
size_t ComputeMethodInfoSize() const;
private:
- size_t ComputeDexRegisterLocationCatalogSize() const;
+ static constexpr uint32_t kNoValue = -1;
- // Prepare and deduplicate method indices.
- void PrepareMethodIndices();
+ // The fields must be uint32_t and mirror the StackMap accessor in stack_map.h!
+ struct StackMapEntry {
+ uint32_t packed_native_pc;
+ uint32_t dex_pc;
+ uint32_t register_mask_index;
+ uint32_t stack_mask_index;
+ uint32_t inline_info_index;
+ uint32_t dex_register_mask_index;
+ uint32_t dex_register_map_index;
+ };
- // Deduplicate entry if possible and return the corresponding index into dex_register_entries_
- // array. If entry is not a duplicate, a new entry is added to dex_register_entries_.
- size_t AddDexRegisterMapEntry(const DexRegisterMapEntry& entry);
+ // The fields must be uint32_t and mirror the InlineInfo accessor in stack_map.h!
+ struct InlineInfoEntry {
+ uint32_t is_last;
+ uint32_t dex_pc;
+ uint32_t method_info_index;
+ uint32_t art_method_hi;
+ uint32_t art_method_lo;
+ uint32_t dex_register_mask_index;
+ uint32_t dex_register_map_index;
+ };
- // Return true if the two dex register map entries are equal.
- bool DexRegisterMapEntryEquals(const DexRegisterMapEntry& a, const DexRegisterMapEntry& b) const;
+ // The fields must be uint32_t and mirror the InvokeInfo accessor in stack_map.h!
+ struct InvokeInfoEntry {
+ uint32_t packed_native_pc;
+ uint32_t invoke_type;
+ uint32_t method_info_index;
+ };
- // Fill in the corresponding entries of a register map.
- void FillInDexRegisterMap(DexRegisterMap dex_register_map,
- uint32_t num_dex_registers,
- const BitVector& live_dex_registers_mask,
- uint32_t start_index_in_dex_register_locations) const;
+ // The fields must be uint32_t and mirror the DexRegisterInfo accessor in stack_map.h!
+ struct DexRegisterEntry {
+ uint32_t kind;
+ uint32_t packed_value;
+ };
+
+ // The fields must be uint32_t and mirror the RegisterMask accessor in stack_map.h!
+ struct RegisterMaskEntry {
+ uint32_t value;
+ uint32_t shift;
+ };
+
+ void CreateDexRegisterMap();
void CheckDexRegisterMap(const DexRegisterMap& dex_register_map,
- size_t num_dex_registers,
- BitVector* live_dex_registers_mask,
- size_t dex_register_locations_index) const;
+ size_t dex_register_mask_index,
+ size_t dex_register_map_index) const;
void CheckCodeInfo(MemoryRegion region) const;
- ScopedArenaAllocator* const allocator_;
const InstructionSet instruction_set_;
- ScopedArenaVector<StackMapEntry> stack_maps_;
-
- // A catalog of unique [location_kind, register_value] pairs (per method).
- ScopedArenaVector<DexRegisterLocation> location_catalog_entries_;
- // Map from Dex register location catalog entries to their indices in the
- // location catalog.
- using LocationCatalogEntriesIndices = ScopedArenaHashMap<DexRegisterLocation,
- size_t,
- LocationCatalogEntriesIndicesEmptyFn,
- DexRegisterLocationHashFn>;
- LocationCatalogEntriesIndices location_catalog_entries_indices_;
-
- // A set of concatenated maps of Dex register locations indices to `location_catalog_entries_`.
- ScopedArenaVector<size_t> dex_register_locations_;
- ScopedArenaVector<InlineInfoEntry> inline_infos_;
- ScopedArenaVector<uint32_t> method_indices_;
- ScopedArenaVector<DexRegisterMapEntry> dex_register_entries_;
-
+ BitTableBuilder<StackMapEntry> stack_maps_;
+ BitTableBuilder<RegisterMaskEntry> register_masks_;
+ BitmapTableBuilder stack_masks_;
+ BitTableBuilder<InvokeInfoEntry> invoke_infos_;
+ BitTableBuilder<InlineInfoEntry> inline_infos_;
+ BitmapTableBuilder dex_register_masks_;
+ BitTableBuilder<uint32_t> dex_register_maps_;
+ BitTableBuilder<DexRegisterEntry> dex_register_catalog_;
ScopedArenaVector<uint8_t> out_;
- ScopedArenaSafeMap<uint32_t, ScopedArenaVector<uint32_t>> dex_map_hash_to_stack_map_indices_;
+ BitTableBuilder<uint32_t> method_infos_;
- StackMapEntry current_entry_;
- InlineInfoEntry current_inline_info_;
- uint32_t current_dex_register_;
- bool in_inline_frame_;
+ ScopedArenaVector<BitVector*> lazy_stack_masks_;
+
+ // Variables which track the current state between Begin/End calls;
+ bool in_stack_map_;
+ bool in_inline_info_;
+ StackMapEntry current_stack_map_;
+ uint32_t current_inline_infos_;
+ ScopedArenaVector<DexRegisterLocation> current_dex_registers_;
+ size_t expected_num_dex_registers_;
+
+ // Temporary variables used in CreateDexRegisterMap.
+ // They are here so that we can reuse the reserved memory.
+ ArenaBitVector temp_dex_register_mask_;
+ ScopedArenaVector<uint32_t> temp_dex_register_map_;
+
+ // Records num_dex_registers for every StackMapEntry and InlineInfoEntry.
+ // Only used in debug builds to verify the dex registers at the end.
+ std::vector<uint32_t> dcheck_num_dex_registers_;
DISALLOW_COPY_AND_ASSIGN(StackMapStream);
};