Merge "Use unique location catalogs to encode Dex register maps."

1 files changed, 129 insertions, 31 deletions

diff --git a/compiler/optimizing/stack_map_stream.h b/compiler/optimizing/stack_map_stream.h
index 5818a37a46..b77e60471b 100644
--- a/compiler/optimizing/stack_map_stream.h
+++ b/compiler/optimizing/stack_map_stream.h
@@ -27,6 +27,32 @@
 
 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_;
+};
+
+
 /**
  * Collects and builds stack maps for a method. All the stack maps
  * for a method are placed in a CodeInfo object.
@@ -36,6 +62,7 @@ class StackMapStream : public ValueObject {
   explicit StackMapStream(ArenaAllocator* allocator)
       : allocator_(allocator),
         stack_maps_(allocator, 10),
+        location_catalog_entries_(allocator, 4),
         dex_register_locations_(allocator, 10 * 4),
         inline_infos_(allocator, 2),
         stack_mask_max_(-1),
@@ -111,6 +138,7 @@ class StackMapStream : public ValueObject {
 
   size_t ComputeNeededSize() {
     size_t size = CodeInfo::kFixedSize
+        + ComputeDexRegisterLocationCatalogSize()
         + ComputeStackMapsSize()
         + ComputeDexRegisterMapsSize()
         + ComputeInlineInfoSize();
@@ -131,21 +159,39 @@ class StackMapStream : public ValueObject {
         native_pc_offset_max_);
   }
 
-  // Compute the size of the Dex register map of `entry`.
+  // Compute the size of the Dex register location catalog of `entry`.
+  size_t ComputeDexRegisterLocationCatalogSize() const {
+    size_t size = DexRegisterLocationCatalog::kFixedSize;
+    for (size_t location_catalog_entry_index = 0;
+         location_catalog_entry_index < location_catalog_entries_.Size();
+         ++location_catalog_entry_index) {
+      DexRegisterLocation dex_register_location =
+          location_catalog_entries_.Get(location_catalog_entry_index);
+      size += DexRegisterLocationCatalog::EntrySize(dex_register_location);
+    }
+    return size;
+  }
+
   size_t ComputeDexRegisterMapSize(const StackMapEntry& entry) const {
+    // Size of the map in bytes.
     size_t size = DexRegisterMap::kFixedSize;
-    // Add the bit mask for the dex register liveness.
-    size += DexRegisterMap::LiveBitMaskSize(entry.num_dex_registers);
-    for (size_t dex_register_number = 0, index_in_dex_register_locations = 0;
+    // Add the live bit mask for the Dex register liveness.
+    size += DexRegisterMap::GetLiveBitMaskSize(entry.num_dex_registers);
+    // Compute the size of the set of live Dex register entries.
+    size_t number_of_live_dex_registers = 0;
+    for (size_t dex_register_number = 0;
          dex_register_number < entry.num_dex_registers;
          ++dex_register_number) {
       if (entry.live_dex_registers_mask->IsBitSet(dex_register_number)) {
-        DexRegisterLocation dex_register_location = dex_register_locations_.Get(
-            entry.dex_register_locations_start_index + index_in_dex_register_locations);
-        size += DexRegisterMap::EntrySize(dex_register_location);
-        index_in_dex_register_locations++;
+        ++number_of_live_dex_registers;
       }
     }
+    size_t map_entries_size_in_bits =
+        DexRegisterMap::SingleEntrySizeInBits(location_catalog_entries_.Size())
+        * number_of_live_dex_registers;
+    size_t map_entries_size_in_bytes =
+        RoundUp(map_entries_size_in_bits, kBitsPerByte) / kBitsPerByte;
+    size += map_entries_size_in_bytes;
     return size;
   }
 
@@ -168,8 +214,16 @@ class StackMapStream : public ValueObject {
       + (number_of_stack_maps_with_inline_info_ * InlineInfo::kFixedSize);
   }
 
+  size_t ComputeDexRegisterLocationCatalogStart() const {
+    return CodeInfo::kFixedSize;
+  }
+
+  size_t ComputeStackMapsStart() const {
+    return ComputeDexRegisterLocationCatalogStart() + ComputeDexRegisterLocationCatalogSize();
+  }
+
   size_t ComputeDexRegisterMapsStart() {
-    return CodeInfo::kFixedSize + ComputeStackMapsSize();
+    return ComputeStackMapsStart() + ComputeStackMapsSize();
   }
 
   size_t ComputeInlineInfoStart() {
@@ -198,7 +252,25 @@ class StackMapStream : public ValueObject {
         inline_info_size, dex_register_map_size, dex_pc_max_, native_pc_offset_max_);
     code_info.SetNumberOfStackMaps(stack_maps_.Size());
     code_info.SetStackMaskSize(stack_mask_size);
-    DCHECK_EQ(code_info.StackMapsSize(), ComputeStackMapsSize());
+    DCHECK_EQ(code_info.GetStackMapsSize(), ComputeStackMapsSize());
+
+    // Set the Dex register location catalog.
+    code_info.SetNumberOfDexRegisterLocationCatalogEntries(
+        location_catalog_entries_.Size());
+    MemoryRegion dex_register_location_catalog_region = region.Subregion(
+        ComputeDexRegisterLocationCatalogStart(),
+        ComputeDexRegisterLocationCatalogSize());
+    DexRegisterLocationCatalog dex_register_location_catalog(dex_register_location_catalog_region);
+    // Offset in `dex_register_location_catalog` where to store the next
+    // register location.
+    size_t location_catalog_offset = DexRegisterLocationCatalog::kFixedSize;
+    for (size_t i = 0, e = location_catalog_entries_.Size(); i < e; ++i) {
+      DexRegisterLocation dex_register_location = location_catalog_entries_.Get(i);
+      dex_register_location_catalog.SetRegisterInfo(location_catalog_offset, dex_register_location);
+      location_catalog_offset += DexRegisterLocationCatalog::EntrySize(dex_register_location);
+    }
+    // Ensure we reached the end of the Dex registers location_catalog.
+    DCHECK_EQ(location_catalog_offset, dex_register_location_catalog_region.size());
 
     uintptr_t next_dex_register_map_offset = 0;
     uintptr_t next_inline_info_offset = 0;
@@ -234,25 +306,25 @@ class StackMapStream : public ValueObject {
           stack_map.SetDexRegisterMapOffset(
             code_info, register_region.start() - dex_register_locations_region.start());
 
-          // Offset in `dex_register_map` where to store the next register entry.
-          size_t offset = DexRegisterMap::kFixedSize;
-          dex_register_map.SetLiveBitMask(offset,
-                                          entry.num_dex_registers,
-                                          *entry.live_dex_registers_mask);
-          offset += DexRegisterMap::LiveBitMaskSize(entry.num_dex_registers);
+          // Set the live bit mask.
+          dex_register_map.SetLiveBitMask(entry.num_dex_registers, *entry.live_dex_registers_mask);
+
+          // Set the dex register location mapping data.
           for (size_t dex_register_number = 0, index_in_dex_register_locations = 0;
                dex_register_number < entry.num_dex_registers;
                ++dex_register_number) {
             if (entry.live_dex_registers_mask->IsBitSet(dex_register_number)) {
-              DexRegisterLocation dex_register_location = dex_register_locations_.Get(
-                  entry.dex_register_locations_start_index + index_in_dex_register_locations);
-              dex_register_map.SetRegisterInfo(offset, dex_register_location);
-              offset += DexRegisterMap::EntrySize(dex_register_location);
+              size_t location_catalog_entry_index =
+                  dex_register_locations_.Get(entry.dex_register_locations_start_index
+                                              + index_in_dex_register_locations);
+              dex_register_map.SetLocationCatalogEntryIndex(
+                  index_in_dex_register_locations,
+                  location_catalog_entry_index,
+                  entry.num_dex_registers,
+                  location_catalog_entries_.Size());
               ++index_in_dex_register_locations;
             }
           }
-          // Ensure we reached the end of the Dex registers region.
-          DCHECK_EQ(offset, register_region.size());
         }
       }
 
@@ -282,12 +354,31 @@ class StackMapStream : public ValueObject {
   }
 
   void AddDexRegisterEntry(uint16_t dex_register, DexRegisterLocation::Kind kind, int32_t value) {
+    StackMapEntry entry = stack_maps_.Get(stack_maps_.Size() - 1);
+    DCHECK_LT(dex_register, entry.num_dex_registers);
+
     if (kind != DexRegisterLocation::Kind::kNone) {
       // Ensure we only use non-compressed location kind at this stage.
       DCHECK(DexRegisterLocation::IsShortLocationKind(kind))
           << DexRegisterLocation::PrettyDescriptor(kind);
-      dex_register_locations_.Add(DexRegisterLocation(kind, value));
-      StackMapEntry entry = stack_maps_.Get(stack_maps_.Size() - 1);
+      DexRegisterLocation location(kind, value);
+
+      // Look for Dex register `location` in the location catalog (using the
+      // companion hash map of locations to indices).  Use its index if it
+      // is already in the location catalog.  If not, insert it (in the
+      // location catalog and the hash map) and use the newly created index.
+      auto it = location_catalog_entries_indices_.Find(location);
+      if (it != location_catalog_entries_indices_.end()) {
+        // Retrieve the index from the hash map.
+        dex_register_locations_.Add(it->second);
+      } else {
+        // Create a new entry in the location catalog and the hash map.
+        size_t index = location_catalog_entries_.Size();
+        location_catalog_entries_.Add(location);
+        dex_register_locations_.Add(index);
+        location_catalog_entries_indices_.Insert(std::make_pair(location, index));
+      }
+
       entry.live_dex_registers_mask->SetBit(dex_register);
       entry.dex_register_map_hash += (1 << dex_register);
       entry.dex_register_map_hash += static_cast<uint32_t>(value);
@@ -354,9 +445,9 @@ class StackMapStream : public ValueObject {
         return false;
       }
       if (a.live_dex_registers_mask->IsBitSet(i)) {
-        DexRegisterLocation a_loc = dex_register_locations_.Get(
+        size_t a_loc = dex_register_locations_.Get(
             a.dex_register_locations_start_index + index_in_dex_register_locations);
-        DexRegisterLocation b_loc = dex_register_locations_.Get(
+        size_t b_loc = dex_register_locations_.Get(
             b.dex_register_locations_start_index + index_in_dex_register_locations);
         if (a_loc != b_loc) {
           return false;
@@ -369,7 +460,18 @@ class StackMapStream : public ValueObject {
 
   ArenaAllocator* allocator_;
   GrowableArray<StackMapEntry> stack_maps_;
-  GrowableArray<DexRegisterLocation> dex_register_locations_;
+
+  // A catalog of unique [location_kind, register_value] pairs (per method).
+  GrowableArray<DexRegisterLocation> location_catalog_entries_;
+  // Map from Dex register location catalog entries to their indices in the
+  // location catalog.
+  typedef HashMap<DexRegisterLocation, size_t, LocationCatalogEntriesIndicesEmptyFn,
+                  DexRegisterLocationHashFn> LocationCatalogEntriesIndices;
+  LocationCatalogEntriesIndices location_catalog_entries_indices_;
+
+  // A set of concatenated maps of Dex register locations indices to
+  // `location_catalog_entries_`.
+  GrowableArray<size_t> dex_register_locations_;
   GrowableArray<InlineInfoEntry> inline_infos_;
   int stack_mask_max_;
   uint32_t dex_pc_max_;
@@ -380,10 +482,6 @@ class StackMapStream : public ValueObject {
 
   static constexpr uint32_t kNoSameDexMapFound = -1;
 
-  ART_FRIEND_TEST(StackMapTest, Test1);
-  ART_FRIEND_TEST(StackMapTest, Test2);
-  ART_FRIEND_TEST(StackMapTest, TestNonLiveDexRegisters);
-
   DISALLOW_COPY_AND_ASSIGN(StackMapStream);
 };