diff --git a/compiler/optimizing/stack_map_stream.h b/compiler/optimizing/stack_map_stream.h
index 5818a37..b77e604 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 @@
   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 @@
 
   size_t ComputeNeededSize() {
     size_t size = CodeInfo::kFixedSize
+        + ComputeDexRegisterLocationCatalogSize()
         + ComputeStackMapsSize()
         + ComputeDexRegisterMapsSize()
         + ComputeInlineInfoSize();
@@ -131,21 +159,39 @@
         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 @@
       + (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 @@
         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 @@
           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 @@
   }
 
   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 @@
         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 @@
 
   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 @@
 
   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);
 };
 
diff --git a/compiler/optimizing/stack_map_test.cc b/compiler/optimizing/stack_map_test.cc
index e5a9790..b9bf016 100644
--- a/compiler/optimizing/stack_map_test.cc
+++ b/compiler/optimizing/stack_map_test.cc
@@ -31,6 +31,8 @@
   return true;
 }
 
+using Kind = DexRegisterLocation::Kind;
+
 TEST(StackMapTest, Test1) {
   ArenaPool pool;
   ArenaAllocator arena(&pool);
@@ -39,8 +41,8 @@
   ArenaBitVector sp_mask(&arena, 0, false);
   size_t number_of_dex_registers = 2;
   stream.AddStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0);
-  stream.AddDexRegisterEntry(0, DexRegisterLocation::Kind::kInStack, 0);
-  stream.AddDexRegisterEntry(1, DexRegisterLocation::Kind::kConstant, -2);
+  stream.AddDexRegisterEntry(0, Kind::kInStack, 0);         // Short location.
+  stream.AddDexRegisterEntry(1, Kind::kConstant, -2);       // Short location.
 
   size_t size = stream.ComputeNeededSize();
   void* memory = arena.Alloc(size, kArenaAllocMisc);
@@ -51,6 +53,16 @@
   ASSERT_EQ(0u, code_info.GetStackMaskSize());
   ASSERT_EQ(1u, code_info.GetNumberOfStackMaps());
 
+  uint32_t number_of_location_catalog_entries =
+      code_info.GetNumberOfDexRegisterLocationCatalogEntries();
+  ASSERT_EQ(2u, number_of_location_catalog_entries);
+  DexRegisterLocationCatalog location_catalog = code_info.GetDexRegisterLocationCatalog();
+  // The Dex register location catalog contains:
+  // - one 1-byte short Dex register location, and
+  // - one 5-byte large Dex register location.
+  size_t expected_location_catalog_size = 1u + 5u;
+  ASSERT_EQ(expected_location_catalog_size, location_catalog.Size());
+
   StackMap stack_map = code_info.GetStackMapAt(0);
   ASSERT_TRUE(stack_map.Equals(code_info.GetStackMapForDexPc(0)));
   ASSERT_TRUE(stack_map.Equals(code_info.GetStackMapForNativePcOffset(64)));
@@ -62,14 +74,40 @@
   ASSERT_TRUE(SameBits(stack_mask, sp_mask));
 
   ASSERT_TRUE(stack_map.HasDexRegisterMap(code_info));
-  DexRegisterMap dex_registers = code_info.GetDexRegisterMapOf(stack_map, number_of_dex_registers);
-  ASSERT_EQ(7u, dex_registers.Size());
-  DexRegisterLocation location0 = dex_registers.GetLocationKindAndValue(0, number_of_dex_registers);
-  DexRegisterLocation location1 = dex_registers.GetLocationKindAndValue(1, number_of_dex_registers);
-  ASSERT_EQ(DexRegisterLocation::Kind::kInStack, location0.GetKind());
-  ASSERT_EQ(DexRegisterLocation::Kind::kConstant, location1.GetKind());
-  ASSERT_EQ(DexRegisterLocation::Kind::kInStack, location0.GetInternalKind());
-  ASSERT_EQ(DexRegisterLocation::Kind::kConstantLargeValue, location1.GetInternalKind());
+  DexRegisterMap dex_register_map =
+      code_info.GetDexRegisterMapOf(stack_map, number_of_dex_registers);
+  ASSERT_TRUE(dex_register_map.IsDexRegisterLive(0));
+  ASSERT_TRUE(dex_register_map.IsDexRegisterLive(1));
+  ASSERT_EQ(2u, dex_register_map.GetNumberOfLiveDexRegisters(number_of_dex_registers));
+  // The Dex register map contains:
+  // - one 1-byte live bit mask, and
+  // - one 1-byte set of location catalog entry indices composed of two 2-bit values.
+  size_t expected_dex_register_map_size = 1u + 1u;
+  ASSERT_EQ(expected_dex_register_map_size, dex_register_map.Size());
+
+  ASSERT_EQ(Kind::kInStack,
+            dex_register_map.GetLocationKind(0, number_of_dex_registers, code_info));
+  ASSERT_EQ(Kind::kConstant,
+            dex_register_map.GetLocationKind(1, number_of_dex_registers, code_info));
+  ASSERT_EQ(Kind::kInStack,
+            dex_register_map.GetLocationInternalKind(0, number_of_dex_registers, code_info));
+  ASSERT_EQ(Kind::kConstantLargeValue,
+            dex_register_map.GetLocationInternalKind(1, number_of_dex_registers, code_info));
+  ASSERT_EQ(0, dex_register_map.GetStackOffsetInBytes(0, number_of_dex_registers, code_info));
+  ASSERT_EQ(-2, dex_register_map.GetConstant(1, number_of_dex_registers, code_info));
+
+  size_t index0 = dex_register_map.GetLocationCatalogEntryIndex(
+      0, number_of_dex_registers, number_of_location_catalog_entries);
+  size_t index1 = dex_register_map.GetLocationCatalogEntryIndex(
+      1, number_of_dex_registers, number_of_location_catalog_entries);
+  ASSERT_EQ(0u, index0);
+  ASSERT_EQ(1u, index1);
+  DexRegisterLocation location0 = location_catalog.GetDexRegisterLocation(index0);
+  DexRegisterLocation location1 = location_catalog.GetDexRegisterLocation(index1);
+  ASSERT_EQ(Kind::kInStack, location0.GetKind());
+  ASSERT_EQ(Kind::kConstant, location1.GetKind());
+  ASSERT_EQ(Kind::kInStack, location0.GetInternalKind());
+  ASSERT_EQ(Kind::kConstantLargeValue, location1.GetInternalKind());
   ASSERT_EQ(0, location0.GetValue());
   ASSERT_EQ(-2, location1.GetValue());
 
@@ -86,8 +124,8 @@
   sp_mask1.SetBit(4);
   size_t number_of_dex_registers = 2;
   stream.AddStackMapEntry(0, 64, 0x3, &sp_mask1, number_of_dex_registers, 2);
-  stream.AddDexRegisterEntry(0, DexRegisterLocation::Kind::kInStack, 0);
-  stream.AddDexRegisterEntry(1, DexRegisterLocation::Kind::kConstant, -2);
+  stream.AddDexRegisterEntry(0, Kind::kInStack, 0);         // Short location.
+  stream.AddDexRegisterEntry(1, Kind::kConstant, -2);       // Large location.
   stream.AddInlineInfoEntry(42);
   stream.AddInlineInfoEntry(82);
 
@@ -95,8 +133,8 @@
   sp_mask2.SetBit(3);
   sp_mask1.SetBit(8);
   stream.AddStackMapEntry(1, 128, 0xFF, &sp_mask2, number_of_dex_registers, 0);
-  stream.AddDexRegisterEntry(0, DexRegisterLocation::Kind::kInRegister, 18);
-  stream.AddDexRegisterEntry(1, DexRegisterLocation::Kind::kInFpuRegister, 3);
+  stream.AddDexRegisterEntry(0, Kind::kInRegister, 18);     // Short location.
+  stream.AddDexRegisterEntry(1, Kind::kInFpuRegister, 3);   // Short location.
 
   size_t size = stream.ComputeNeededSize();
   void* memory = arena.Alloc(size, kArenaAllocMisc);
@@ -107,6 +145,16 @@
   ASSERT_EQ(1u, code_info.GetStackMaskSize());
   ASSERT_EQ(2u, code_info.GetNumberOfStackMaps());
 
+  uint32_t number_of_location_catalog_entries =
+      code_info.GetNumberOfDexRegisterLocationCatalogEntries();
+  ASSERT_EQ(4u, number_of_location_catalog_entries);
+  DexRegisterLocationCatalog location_catalog = code_info.GetDexRegisterLocationCatalog();
+  // The Dex register location catalog contains:
+  // - three 1-byte short Dex register locations, and
+  // - one 5-byte large Dex register location.
+  size_t expected_location_catalog_size = 3u * 1u + 5u;
+  ASSERT_EQ(expected_location_catalog_size, location_catalog.Size());
+
   // First stack map.
   {
     StackMap stack_map = code_info.GetStackMapAt(0);
@@ -120,17 +168,40 @@
     ASSERT_TRUE(SameBits(stack_mask, sp_mask1));
 
     ASSERT_TRUE(stack_map.HasDexRegisterMap(code_info));
-    DexRegisterMap dex_registers =
+    DexRegisterMap dex_register_map =
         code_info.GetDexRegisterMapOf(stack_map, number_of_dex_registers);
-    ASSERT_EQ(7u, dex_registers.Size());
-    DexRegisterLocation location0 =
-        dex_registers.GetLocationKindAndValue(0, number_of_dex_registers);
-    DexRegisterLocation location1 =
-        dex_registers.GetLocationKindAndValue(1, number_of_dex_registers);
-    ASSERT_EQ(DexRegisterLocation::Kind::kInStack, location0.GetKind());
-    ASSERT_EQ(DexRegisterLocation::Kind::kConstant, location1.GetKind());
-    ASSERT_EQ(DexRegisterLocation::Kind::kInStack, location0.GetInternalKind());
-    ASSERT_EQ(DexRegisterLocation::Kind::kConstantLargeValue, location1.GetInternalKind());
+    ASSERT_TRUE(dex_register_map.IsDexRegisterLive(0));
+    ASSERT_TRUE(dex_register_map.IsDexRegisterLive(1));
+    ASSERT_EQ(2u, dex_register_map.GetNumberOfLiveDexRegisters(number_of_dex_registers));
+    // The Dex register map contains:
+    // - one 1-byte live bit mask, and
+    // - one 1-byte set of location catalog entry indices composed of two 2-bit values.
+    size_t expected_dex_register_map_size = 1u + 1u;
+    ASSERT_EQ(expected_dex_register_map_size, dex_register_map.Size());
+
+    ASSERT_EQ(Kind::kInStack,
+              dex_register_map.GetLocationKind(0, number_of_dex_registers, code_info));
+    ASSERT_EQ(Kind::kConstant,
+              dex_register_map.GetLocationKind(1, number_of_dex_registers, code_info));
+    ASSERT_EQ(Kind::kInStack,
+              dex_register_map.GetLocationInternalKind(0, number_of_dex_registers, code_info));
+    ASSERT_EQ(Kind::kConstantLargeValue,
+              dex_register_map.GetLocationInternalKind(1, number_of_dex_registers, code_info));
+    ASSERT_EQ(0, dex_register_map.GetStackOffsetInBytes(0, number_of_dex_registers, code_info));
+    ASSERT_EQ(-2, dex_register_map.GetConstant(1, number_of_dex_registers, code_info));
+
+    size_t index0 = dex_register_map.GetLocationCatalogEntryIndex(
+        0, number_of_dex_registers, number_of_location_catalog_entries);
+    size_t index1 = dex_register_map.GetLocationCatalogEntryIndex(
+        1, number_of_dex_registers, number_of_location_catalog_entries);
+    ASSERT_EQ(0u, index0);
+    ASSERT_EQ(1u, index1);
+    DexRegisterLocation location0 = location_catalog.GetDexRegisterLocation(index0);
+    DexRegisterLocation location1 = location_catalog.GetDexRegisterLocation(index1);
+    ASSERT_EQ(Kind::kInStack, location0.GetKind());
+    ASSERT_EQ(Kind::kConstant, location1.GetKind());
+    ASSERT_EQ(Kind::kInStack, location0.GetInternalKind());
+    ASSERT_EQ(Kind::kConstantLargeValue, location1.GetInternalKind());
     ASSERT_EQ(0, location0.GetValue());
     ASSERT_EQ(-2, location1.GetValue());
 
@@ -154,17 +225,40 @@
     ASSERT_TRUE(SameBits(stack_mask, sp_mask2));
 
     ASSERT_TRUE(stack_map.HasDexRegisterMap(code_info));
-    DexRegisterMap dex_registers =
+    DexRegisterMap dex_register_map =
         code_info.GetDexRegisterMapOf(stack_map, number_of_dex_registers);
-    ASSERT_EQ(3u, dex_registers.Size());
-    DexRegisterLocation location0 =
-        dex_registers.GetLocationKindAndValue(0, number_of_dex_registers);
-    DexRegisterLocation location1 =
-        dex_registers.GetLocationKindAndValue(1, number_of_dex_registers);
-    ASSERT_EQ(DexRegisterLocation::Kind::kInRegister, location0.GetKind());
-    ASSERT_EQ(DexRegisterLocation::Kind::kInFpuRegister, location1.GetKind());
-    ASSERT_EQ(DexRegisterLocation::Kind::kInRegister, location0.GetInternalKind());
-    ASSERT_EQ(DexRegisterLocation::Kind::kInFpuRegister, location1.GetInternalKind());
+    ASSERT_TRUE(dex_register_map.IsDexRegisterLive(0));
+    ASSERT_TRUE(dex_register_map.IsDexRegisterLive(1));
+    ASSERT_EQ(2u, dex_register_map.GetNumberOfLiveDexRegisters(number_of_dex_registers));
+    // The Dex register map contains:
+    // - one 1-byte live bit mask, and
+    // - one 1-byte set of location catalog entry indices composed of two 2-bit values.
+    size_t expected_dex_register_map_size = 1u + 1u;
+    ASSERT_EQ(expected_dex_register_map_size, dex_register_map.Size());
+
+    ASSERT_EQ(Kind::kInRegister,
+              dex_register_map.GetLocationKind(0, number_of_dex_registers, code_info));
+    ASSERT_EQ(Kind::kInFpuRegister,
+              dex_register_map.GetLocationKind(1, number_of_dex_registers, code_info));
+    ASSERT_EQ(Kind::kInRegister,
+              dex_register_map.GetLocationInternalKind(0, number_of_dex_registers, code_info));
+    ASSERT_EQ(Kind::kInFpuRegister,
+              dex_register_map.GetLocationInternalKind(1, number_of_dex_registers, code_info));
+    ASSERT_EQ(18, dex_register_map.GetMachineRegister(0, number_of_dex_registers, code_info));
+    ASSERT_EQ(3, dex_register_map.GetMachineRegister(1, number_of_dex_registers, code_info));
+
+    size_t index0 = dex_register_map.GetLocationCatalogEntryIndex(
+        0, number_of_dex_registers, number_of_location_catalog_entries);
+    size_t index1 = dex_register_map.GetLocationCatalogEntryIndex(
+        1, number_of_dex_registers, number_of_location_catalog_entries);
+    ASSERT_EQ(2u, index0);
+    ASSERT_EQ(3u, index1);
+    DexRegisterLocation location0 = location_catalog.GetDexRegisterLocation(index0);
+    DexRegisterLocation location1 = location_catalog.GetDexRegisterLocation(index1);
+    ASSERT_EQ(Kind::kInRegister, location0.GetKind());
+    ASSERT_EQ(Kind::kInFpuRegister, location1.GetKind());
+    ASSERT_EQ(Kind::kInRegister, location0.GetInternalKind());
+    ASSERT_EQ(Kind::kInFpuRegister, location1.GetInternalKind());
     ASSERT_EQ(18, location0.GetValue());
     ASSERT_EQ(3, location1.GetValue());
 
@@ -180,8 +274,8 @@
   ArenaBitVector sp_mask(&arena, 0, false);
   uint32_t number_of_dex_registers = 2;
   stream.AddStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0);
-  stream.AddDexRegisterEntry(0, DexRegisterLocation::Kind::kNone, 0);
-  stream.AddDexRegisterEntry(1, DexRegisterLocation::Kind::kConstant, -2);
+  stream.AddDexRegisterEntry(0, Kind::kNone, 0);            // No location.
+  stream.AddDexRegisterEntry(1, Kind::kConstant, -2);       // Large location.
 
   size_t size = stream.ComputeNeededSize();
   void* memory = arena.Alloc(size, kArenaAllocMisc);
@@ -189,14 +283,62 @@
   stream.FillIn(region);
 
   CodeInfo code_info(region);
+  ASSERT_EQ(0u, code_info.GetStackMaskSize());
+  ASSERT_EQ(1u, code_info.GetNumberOfStackMaps());
+
+  uint32_t number_of_location_catalog_entries =
+      code_info.GetNumberOfDexRegisterLocationCatalogEntries();
+  ASSERT_EQ(1u, number_of_location_catalog_entries);
+  DexRegisterLocationCatalog location_catalog = code_info.GetDexRegisterLocationCatalog();
+  // The Dex register location catalog contains:
+  // - one 5-byte large Dex register location.
+  size_t expected_location_catalog_size = 5u;
+  ASSERT_EQ(expected_location_catalog_size, location_catalog.Size());
+
   StackMap stack_map = code_info.GetStackMapAt(0);
+  ASSERT_TRUE(stack_map.Equals(code_info.GetStackMapForDexPc(0)));
+  ASSERT_TRUE(stack_map.Equals(code_info.GetStackMapForNativePcOffset(64)));
+  ASSERT_EQ(0u, stack_map.GetDexPc(code_info));
+  ASSERT_EQ(64u, stack_map.GetNativePcOffset(code_info));
+  ASSERT_EQ(0x3u, stack_map.GetRegisterMask(code_info));
+
   ASSERT_TRUE(stack_map.HasDexRegisterMap(code_info));
-  DexRegisterMap dex_registers = code_info.GetDexRegisterMapOf(stack_map, 2);
-  ASSERT_EQ(DexRegisterLocation::Kind::kNone,
-            dex_registers.GetLocationKind(0, number_of_dex_registers));
-  ASSERT_EQ(DexRegisterLocation::Kind::kConstant,
-            dex_registers.GetLocationKind(1, number_of_dex_registers));
-  ASSERT_EQ(-2, dex_registers.GetConstant(1, number_of_dex_registers));
+  DexRegisterMap dex_register_map =
+      code_info.GetDexRegisterMapOf(stack_map, number_of_dex_registers);
+  ASSERT_FALSE(dex_register_map.IsDexRegisterLive(0));
+  ASSERT_TRUE(dex_register_map.IsDexRegisterLive(1));
+  ASSERT_EQ(1u, dex_register_map.GetNumberOfLiveDexRegisters(number_of_dex_registers));
+  // The Dex register map contains:
+  // - one 1-byte live bit mask.
+  // No space is allocated for the sole location catalog entry index, as it is useless.
+  size_t expected_dex_register_map_size = 1u + 0u;
+  ASSERT_EQ(expected_dex_register_map_size, dex_register_map.Size());
+
+  ASSERT_EQ(Kind::kNone,
+            dex_register_map.GetLocationKind(0, number_of_dex_registers, code_info));
+  ASSERT_EQ(Kind::kConstant,
+            dex_register_map.GetLocationKind(1, number_of_dex_registers, code_info));
+  ASSERT_EQ(Kind::kNone,
+            dex_register_map.GetLocationInternalKind(0, number_of_dex_registers, code_info));
+  ASSERT_EQ(Kind::kConstantLargeValue,
+            dex_register_map.GetLocationInternalKind(1, number_of_dex_registers, code_info));
+  ASSERT_EQ(-2, dex_register_map.GetConstant(1, number_of_dex_registers, code_info));
+
+  size_t index0 = dex_register_map.GetLocationCatalogEntryIndex(
+      0, number_of_dex_registers, number_of_location_catalog_entries);
+  size_t index1 =  dex_register_map.GetLocationCatalogEntryIndex(
+      1, number_of_dex_registers, number_of_location_catalog_entries);
+  ASSERT_EQ(DexRegisterLocationCatalog::kNoLocationEntryIndex, index0);
+  ASSERT_EQ(0u, index1);
+  DexRegisterLocation location0 = location_catalog.GetDexRegisterLocation(index0);
+  DexRegisterLocation location1 = location_catalog.GetDexRegisterLocation(index1);
+  ASSERT_EQ(Kind::kNone, location0.GetKind());
+  ASSERT_EQ(Kind::kConstant, location1.GetKind());
+  ASSERT_EQ(Kind::kNone, location0.GetInternalKind());
+  ASSERT_EQ(Kind::kConstantLargeValue, location1.GetInternalKind());
+  ASSERT_EQ(0, location0.GetValue());
+  ASSERT_EQ(-2, location1.GetValue());
+
   ASSERT_FALSE(stack_map.HasInlineInfo(code_info));
 }
 
@@ -209,14 +351,21 @@
   StackMapStream stream(&arena);
 
   ArenaBitVector sp_mask(&arena, 0, false);
-  uint32_t number_of_dex_registers = 0xEA;
+  uint32_t number_of_dex_registers = 1024;
+  // Create the first stack map (and its Dex register map).
   stream.AddStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0);
-  for (uint32_t i = 0; i < number_of_dex_registers - 9; ++i) {
-    stream.AddDexRegisterEntry(i, DexRegisterLocation::Kind::kConstant, 0);
+  uint32_t number_of_dex_live_registers_in_dex_register_map_0 = number_of_dex_registers - 8;
+  for (uint32_t i = 0; i < number_of_dex_live_registers_in_dex_register_map_0; ++i) {
+    // Use two different Dex register locations to populate this map,
+    // as using a single value (in the whole CodeInfo object) would
+    // make this Dex register mapping data empty (see
+    // art::DexRegisterMap::SingleEntrySizeInBits).
+    stream.AddDexRegisterEntry(i, Kind::kConstant, i % 2);  // Short location.
   }
+  // Create the second stack map (and its Dex register map).
   stream.AddStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0);
   for (uint32_t i = 0; i < number_of_dex_registers; ++i) {
-    stream.AddDexRegisterEntry(i, DexRegisterLocation::Kind::kConstant, 0);
+    stream.AddDexRegisterEntry(i, Kind::kConstant, 0);  // Short location.
   }
 
   size_t size = stream.ComputeNeededSize();
@@ -225,10 +374,36 @@
   stream.FillIn(region);
 
   CodeInfo code_info(region);
-  StackMap stack_map = code_info.GetStackMapAt(1);
-  ASSERT_TRUE(stack_map.HasDexRegisterMap(code_info));
-  ASSERT_NE(stack_map.GetDexRegisterMapOffset(code_info), StackMap::kNoDexRegisterMap);
-  ASSERT_EQ(stack_map.GetDexRegisterMapOffset(code_info), StackMap::kNoDexRegisterMapSmallEncoding);
+  // The location catalog contains two entries (DexRegisterLocation(kConstant, 0)
+  // and DexRegisterLocation(kConstant, 1)), therefore the location catalog index
+  // has a size of 1 bit.
+  uint32_t number_of_location_catalog_entries =
+      code_info.GetNumberOfDexRegisterLocationCatalogEntries();
+  ASSERT_EQ(2u, number_of_location_catalog_entries);
+  ASSERT_EQ(1u, DexRegisterMap::SingleEntrySizeInBits(number_of_location_catalog_entries));
+
+  // The first Dex register map contains:
+  // - a live register bit mask for 1024 registers (that is, 128 bytes of
+  //   data); and
+  // - Dex register mapping information for 1016 1-bit Dex (live) register
+  //   locations (that is, 127 bytes of data).
+  // Hence it has a size of 255 bytes, and therefore...
+  ASSERT_EQ(128u, DexRegisterMap::GetLiveBitMaskSize(number_of_dex_registers));
+  StackMap stack_map0 = code_info.GetStackMapAt(0);
+  DexRegisterMap dex_register_map0 =
+      code_info.GetDexRegisterMapOf(stack_map0, number_of_dex_registers);
+  ASSERT_EQ(127u, dex_register_map0.GetLocationMappingDataSize(number_of_dex_registers,
+                                                               number_of_location_catalog_entries));
+  ASSERT_EQ(255u, dex_register_map0.Size());
+
+  StackMap stack_map1 = code_info.GetStackMapAt(1);
+  ASSERT_TRUE(stack_map1.HasDexRegisterMap(code_info));
+  // ...the offset of the second Dex register map (relative to the
+  // beginning of the Dex register maps region) is 255 (i.e.,
+  // kNoDexRegisterMapSmallEncoding).
+  ASSERT_NE(StackMap::kNoDexRegisterMap, stack_map1.GetDexRegisterMapOffset(code_info));
+  ASSERT_EQ(StackMap::kNoDexRegisterMapSmallEncoding,
+            stack_map1.GetDexRegisterMapOffset(code_info));
 }
 
 TEST(StackMapTest, TestShareDexRegisterMap) {
@@ -240,16 +415,16 @@
   uint32_t number_of_dex_registers = 2;
   // First stack map.
   stream.AddStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0);
-  stream.AddDexRegisterEntry(0, DexRegisterLocation::Kind::kInRegister, 0);
-  stream.AddDexRegisterEntry(1, DexRegisterLocation::Kind::kConstant, -2);
+  stream.AddDexRegisterEntry(0, Kind::kInRegister, 0);  // Short location.
+  stream.AddDexRegisterEntry(1, Kind::kConstant, -2);   // Large location.
   // Second stack map, which should share the same dex register map.
   stream.AddStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0);
-  stream.AddDexRegisterEntry(0, DexRegisterLocation::Kind::kInRegister, 0);
-  stream.AddDexRegisterEntry(1, DexRegisterLocation::Kind::kConstant, -2);
+  stream.AddDexRegisterEntry(0, Kind::kInRegister, 0);  // Short location.
+  stream.AddDexRegisterEntry(1, Kind::kConstant, -2);   // Large location.
   // Third stack map (doesn't share the dex register map).
   stream.AddStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0);
-  stream.AddDexRegisterEntry(0, DexRegisterLocation::Kind::kInRegister, 2);
-  stream.AddDexRegisterEntry(1, DexRegisterLocation::Kind::kConstant, -2);
+  stream.AddDexRegisterEntry(0, Kind::kInRegister, 2);  // Short location.
+  stream.AddDexRegisterEntry(1, Kind::kConstant, -2);   // Large location.
 
   size_t size = stream.ComputeNeededSize();
   void* memory = arena.Alloc(size, kArenaAllocMisc);
@@ -260,20 +435,20 @@
   // Verify first stack map.
   StackMap sm0 = ci.GetStackMapAt(0);
   DexRegisterMap dex_registers0 = ci.GetDexRegisterMapOf(sm0, number_of_dex_registers);
-  ASSERT_EQ(0, dex_registers0.GetMachineRegister(0, number_of_dex_registers));
-  ASSERT_EQ(-2, dex_registers0.GetConstant(1, number_of_dex_registers));
+  ASSERT_EQ(0, dex_registers0.GetMachineRegister(0, number_of_dex_registers, ci));
+  ASSERT_EQ(-2, dex_registers0.GetConstant(1, number_of_dex_registers, ci));
 
   // Verify second stack map.
   StackMap sm1 = ci.GetStackMapAt(1);
   DexRegisterMap dex_registers1 = ci.GetDexRegisterMapOf(sm1, number_of_dex_registers);
-  ASSERT_EQ(0, dex_registers1.GetMachineRegister(0, number_of_dex_registers));
-  ASSERT_EQ(-2, dex_registers1.GetConstant(1, number_of_dex_registers));
+  ASSERT_EQ(0, dex_registers1.GetMachineRegister(0, number_of_dex_registers, ci));
+  ASSERT_EQ(-2, dex_registers1.GetConstant(1, number_of_dex_registers, ci));
 
   // Verify third stack map.
   StackMap sm2 = ci.GetStackMapAt(2);
   DexRegisterMap dex_registers2 = ci.GetDexRegisterMapOf(sm2, number_of_dex_registers);
-  ASSERT_EQ(2, dex_registers2.GetMachineRegister(0, number_of_dex_registers));
-  ASSERT_EQ(-2, dex_registers2.GetConstant(1, number_of_dex_registers));
+  ASSERT_EQ(2, dex_registers2.GetMachineRegister(0, number_of_dex_registers, ci));
+  ASSERT_EQ(-2, dex_registers2.GetConstant(1, number_of_dex_registers, ci));
 
   // Verify dex register map offsets.
   ASSERT_EQ(sm0.GetDexRegisterMapOffset(ci), sm1.GetDexRegisterMapOffset(ci));
@@ -281,4 +456,39 @@
   ASSERT_NE(sm1.GetDexRegisterMapOffset(ci), sm2.GetDexRegisterMapOffset(ci));
 }
 
+TEST(StackMapTest, TestNoDexRegisterMap) {
+  ArenaPool pool;
+  ArenaAllocator arena(&pool);
+  StackMapStream stream(&arena);
+
+  ArenaBitVector sp_mask(&arena, 0, false);
+  uint32_t number_of_dex_registers = 0;
+  stream.AddStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0);
+
+  size_t size = stream.ComputeNeededSize();
+  void* memory = arena.Alloc(size, kArenaAllocMisc);
+  MemoryRegion region(memory, size);
+  stream.FillIn(region);
+
+  CodeInfo code_info(region);
+  ASSERT_EQ(0u, code_info.GetStackMaskSize());
+  ASSERT_EQ(1u, code_info.GetNumberOfStackMaps());
+
+  uint32_t number_of_location_catalog_entries =
+      code_info.GetNumberOfDexRegisterLocationCatalogEntries();
+  ASSERT_EQ(0u, number_of_location_catalog_entries);
+  DexRegisterLocationCatalog location_catalog = code_info.GetDexRegisterLocationCatalog();
+  ASSERT_EQ(0u, location_catalog.Size());
+
+  StackMap stack_map = code_info.GetStackMapAt(0);
+  ASSERT_TRUE(stack_map.Equals(code_info.GetStackMapForDexPc(0)));
+  ASSERT_TRUE(stack_map.Equals(code_info.GetStackMapForNativePcOffset(64)));
+  ASSERT_EQ(0u, stack_map.GetDexPc(code_info));
+  ASSERT_EQ(64u, stack_map.GetNativePcOffset(code_info));
+  ASSERT_EQ(0x3u, stack_map.GetRegisterMask(code_info));
+
+  ASSERT_FALSE(stack_map.HasDexRegisterMap(code_info));
+  ASSERT_FALSE(stack_map.HasInlineInfo(code_info));
+}
+
 }  // namespace art
diff --git a/runtime/base/hash_map.h b/runtime/base/hash_map.h
index c0f903f..eab80ff 100644
--- a/runtime/base/hash_map.h
+++ b/runtime/base/hash_map.h
@@ -48,7 +48,7 @@
   Fn fn_;
 };
 
-template <class Key, class Value, class EmptyFn = DefaultEmptyFn<Key>,
+template <class Key, class Value, class EmptyFn,
     class HashFn = std::hash<Key>, class Pred = std::equal_to<Key>,
     class Alloc = std::allocator<std::pair<Key, Value>>>
 class HashMap : public HashSet<std::pair<Key, Value>, EmptyFn, HashMapWrapper<HashFn>,
diff --git a/runtime/check_reference_map_visitor.h b/runtime/check_reference_map_visitor.h
index 204546d..5d9cd35 100644
--- a/runtime/check_reference_map_visitor.h
+++ b/runtime/check_reference_map_visitor.h
@@ -75,7 +75,7 @@
       int reg = registers[i];
       CHECK(reg < m->GetCodeItem()->registers_size_);
       DexRegisterLocation location =
-          dex_register_map.GetLocationKindAndValue(reg, number_of_dex_registers);
+          dex_register_map.GetDexRegisterLocation(reg, number_of_dex_registers, code_info);
       switch (location.GetKind()) {
         case DexRegisterLocation::Kind::kNone:
           // Not set, should not be a reference.
diff --git a/runtime/memory_region.h b/runtime/memory_region.h
index 3dcb0dd..e275f0f 100644
--- a/runtime/memory_region.h
+++ b/runtime/memory_region.h
@@ -113,6 +113,31 @@
     }
   }
 
+  // Load `length` bits from the region starting at bit offset `bit_offset`.
+  // The bit at the smallest offset is the least significant bit in the
+  // loaded value.  `length` must not be larger than the number of bits
+  // contained in the return value (32).
+  uint32_t LoadBits(uintptr_t bit_offset, size_t length) const {
+    CHECK_LE(length, sizeof(uint32_t) * kBitsPerByte);
+    uint32_t value = 0u;
+    for (size_t i = 0; i < length; ++i) {
+      value |= LoadBit(bit_offset + i) << i;
+    }
+    return value;
+  }
+
+  // Store `value` on `length` bits in the region starting at bit offset
+  // `bit_offset`.  The bit at the smallest offset is the least significant
+  // bit of the stored `value`.  `value` must not be larger than `length`
+  // bits.
+  void StoreBits(uintptr_t bit_offset, uint32_t value, size_t length) {
+    CHECK_LT(value, 2u << length);
+    for (size_t i = 0; i < length; ++i) {
+      bool ith_bit = value & (1 << i);
+      StoreBit(bit_offset + i, ith_bit);
+    }
+  }
+
   void CopyFrom(size_t offset, const MemoryRegion& from) const;
 
   // Compute a sub memory region based on an existing one.
diff --git a/runtime/stack.cc b/runtime/stack.cc
index 2d688ee..4ae49dd 100644
--- a/runtime/stack.cc
+++ b/runtime/stack.cc
@@ -206,21 +206,22 @@
   DexRegisterMap dex_register_map =
       code_info.GetDexRegisterMapOf(stack_map, number_of_dex_registers);
   DexRegisterLocation::Kind location_kind =
-      dex_register_map.GetLocationKind(vreg, number_of_dex_registers);
+      dex_register_map.GetLocationKind(vreg, number_of_dex_registers, code_info);
   switch (location_kind) {
     case DexRegisterLocation::Kind::kInStack: {
-      const int32_t offset = dex_register_map.GetStackOffsetInBytes(vreg, number_of_dex_registers);
+      const int32_t offset =
+          dex_register_map.GetStackOffsetInBytes(vreg, number_of_dex_registers, code_info);
       const uint8_t* addr = reinterpret_cast<const uint8_t*>(cur_quick_frame_) + offset;
       *val = *reinterpret_cast<const uint32_t*>(addr);
       return true;
     }
     case DexRegisterLocation::Kind::kInRegister:
     case DexRegisterLocation::Kind::kInFpuRegister: {
-      uint32_t reg = dex_register_map.GetMachineRegister(vreg, number_of_dex_registers);
+      uint32_t reg = dex_register_map.GetMachineRegister(vreg, number_of_dex_registers, code_info);
       return GetRegisterIfAccessible(reg, kind, val);
     }
     case DexRegisterLocation::Kind::kConstant:
-      *val = dex_register_map.GetConstant(vreg, number_of_dex_registers);
+      *val = dex_register_map.GetConstant(vreg, number_of_dex_registers, code_info);
       return true;
     case DexRegisterLocation::Kind::kNone:
       return false;
@@ -228,7 +229,7 @@
       LOG(FATAL)
           << "Unexpected location kind"
           << DexRegisterLocation::PrettyDescriptor(
-                dex_register_map.GetLocationInternalKind(vreg, number_of_dex_registers));
+                dex_register_map.GetLocationInternalKind(vreg, number_of_dex_registers, code_info));
       UNREACHABLE();
   }
 }
@@ -396,18 +397,19 @@
   DexRegisterMap dex_register_map =
       code_info.GetDexRegisterMapOf(stack_map, number_of_dex_registers);
   DexRegisterLocation::Kind location_kind =
-      dex_register_map.GetLocationKind(vreg, number_of_dex_registers);
+      dex_register_map.GetLocationKind(vreg, number_of_dex_registers, code_info);
   uint32_t dex_pc = m->ToDexPc(cur_quick_frame_pc_, false);
   switch (location_kind) {
     case DexRegisterLocation::Kind::kInStack: {
-      const int32_t offset = dex_register_map.GetStackOffsetInBytes(vreg, number_of_dex_registers);
+      const int32_t offset =
+          dex_register_map.GetStackOffsetInBytes(vreg, number_of_dex_registers, code_info);
       uint8_t* addr = reinterpret_cast<uint8_t*>(cur_quick_frame_) + offset;
       *reinterpret_cast<uint32_t*>(addr) = new_value;
       return true;
     }
     case DexRegisterLocation::Kind::kInRegister:
     case DexRegisterLocation::Kind::kInFpuRegister: {
-      uint32_t reg = dex_register_map.GetMachineRegister(vreg, number_of_dex_registers);
+      uint32_t reg = dex_register_map.GetMachineRegister(vreg, number_of_dex_registers, code_info);
       return SetRegisterIfAccessible(reg, new_value, kind);
     }
     case DexRegisterLocation::Kind::kConstant:
diff --git a/runtime/stack_map.cc b/runtime/stack_map.cc
index 020a6e6..28f42c1 100644
--- a/runtime/stack_map.cc
+++ b/runtime/stack_map.cc
@@ -18,11 +18,37 @@
 
 namespace art {
 
+constexpr size_t DexRegisterLocationCatalog::kNoLocationEntryIndex;
+
 constexpr uint32_t StackMap::kNoDexRegisterMapSmallEncoding;
 constexpr uint32_t StackMap::kNoInlineInfoSmallEncoding;
 constexpr uint32_t StackMap::kNoDexRegisterMap;
 constexpr uint32_t StackMap::kNoInlineInfo;
 
+DexRegisterLocation::Kind DexRegisterMap::GetLocationInternalKind(uint16_t dex_register_number,
+                                                                  uint16_t number_of_dex_registers,
+                                                                  const CodeInfo& code_info) const {
+  DexRegisterLocationCatalog dex_register_location_catalog =
+      code_info.GetDexRegisterLocationCatalog();
+  size_t location_catalog_entry_index = GetLocationCatalogEntryIndex(
+      dex_register_number,
+      number_of_dex_registers,
+      code_info.GetNumberOfDexRegisterLocationCatalogEntries());
+  return dex_register_location_catalog.GetLocationInternalKind(location_catalog_entry_index);
+}
+
+DexRegisterLocation DexRegisterMap::GetDexRegisterLocation(uint16_t dex_register_number,
+                                                           uint16_t number_of_dex_registers,
+                                                           const CodeInfo& code_info) const {
+  DexRegisterLocationCatalog dex_register_location_catalog =
+      code_info.GetDexRegisterLocationCatalog();
+  size_t location_catalog_entry_index = GetLocationCatalogEntryIndex(
+      dex_register_number,
+      number_of_dex_registers,
+      code_info.GetNumberOfDexRegisterLocationCatalogEntries());
+  return dex_register_location_catalog.GetDexRegisterLocation(location_catalog_entry_index);
+}
+
 uint32_t StackMap::GetDexPc(const CodeInfo& info) const {
   return info.HasSmallDexPc()
       ? region_.LoadUnaligned<kSmallEncoding>(info.ComputeStackMapDexPcOffset())
@@ -143,6 +169,16 @@
   return region_.Subregion(info.ComputeStackMapStackMaskOffset(), info.GetStackMaskSize());
 }
 
+static void DumpRegisterMapping(std::ostream& os,
+                                size_t dex_register_num,
+                                DexRegisterLocation location,
+                                const std::string& prefix = "v",
+                                const std::string& suffix = "") {
+  os << "      " << prefix << dex_register_num << ": "
+     << DexRegisterLocation::PrettyDescriptor(location.GetInternalKind())
+     << " (" << location.GetValue() << ")" << suffix << '\n';
+}
+
 void CodeInfo::DumpStackMapHeader(std::ostream& os, size_t stack_map_num) const {
   StackMap stack_map = GetStackMapAt(stack_map_num);
   os << "    StackMap " << stack_map_num
@@ -174,7 +210,18 @@
      << ", has_small_native_pc=" << HasSmallNativePc()
      << ")\n";
 
-  // Display stack maps along with Dex register maps.
+  // Display the Dex register location catalog.
+  size_t number_of_location_catalog_entries = GetNumberOfDexRegisterLocationCatalogEntries();
+  size_t location_catalog_size_in_bytes = GetDexRegisterLocationCatalogSize();
+  os << "  DexRegisterLocationCatalog (number_of_entries=" << number_of_location_catalog_entries
+     << ", size_in_bytes=" << location_catalog_size_in_bytes << ")\n";
+  DexRegisterLocationCatalog dex_register_location_catalog = GetDexRegisterLocationCatalog();
+  for (size_t i = 0; i < number_of_location_catalog_entries; ++i) {
+    DexRegisterLocation location = dex_register_location_catalog.GetDexRegisterLocation(i);
+    DumpRegisterMapping(os, i, location, "entry ");
+  }
+
+  // Display stack maps along with (live) Dex register maps.
   for (size_t i = 0; i < number_of_stack_maps; ++i) {
     StackMap stack_map = GetStackMapAt(i);
     DumpStackMapHeader(os, i);
@@ -183,11 +230,13 @@
       // TODO: Display the bit mask of live Dex registers.
       for (size_t j = 0; j < number_of_dex_registers; ++j) {
         if (dex_register_map.IsDexRegisterLive(j)) {
+          size_t location_catalog_entry_index = dex_register_map.GetLocationCatalogEntryIndex(
+              j, number_of_dex_registers, number_of_location_catalog_entries);
           DexRegisterLocation location =
-              dex_register_map.GetLocationKindAndValue(j, number_of_dex_registers);
-           os << "      " << "v" << j << ": "
-              << DexRegisterLocation::PrettyDescriptor(location.GetInternalKind())
-              << " (" << location.GetValue() << ")" << '\n';
+              dex_register_map.GetDexRegisterLocation(j, number_of_dex_registers, *this);
+          DumpRegisterMapping(
+              os, j, location, "v",
+              "\t[entry " + std::to_string(static_cast<int>(location_catalog_entry_index)) + "]");
         }
       }
     }
diff --git a/runtime/stack_map.h b/runtime/stack_map.h
index 2c6240a..ab7f926 100644
--- a/runtime/stack_map.h
+++ b/runtime/stack_map.h
@@ -26,10 +26,10 @@
 // Size of a frame slot, in bytes.  This constant is a signed value,
 // to please the compiler in arithmetic operations involving int32_t
 // (signed) values.
-static ssize_t constexpr kFrameSlotSize = 4;
+static constexpr ssize_t kFrameSlotSize = 4;
 
 // Size of Dex virtual registers.
-static size_t constexpr kVRegSize = 4;
+static constexpr size_t kVRegSize = 4;
 
 class CodeInfo;
 
@@ -94,9 +94,9 @@
    *
    * In addition, DexRegisterMap also uses these values:
    * - kInStackLargeOffset: value holds a "large" stack offset (greater than
-   *   128 bytes);
-   * - kConstantLargeValue: value holds a "large" constant (lower than or
-   *   equal to -16, or greater than 16).
+   *   or equal to 128 bytes);
+   * - kConstantLargeValue: value holds a "large" constant (lower than 0, or
+   *   or greater than or equal to 32).
    */
   enum class Kind : uint8_t {
     // Short location kinds, for entries fitting on one byte (3 bits
@@ -117,8 +117,7 @@
     kInStackLargeOffset = 5,  // 0b101
 
     // Large constant, that cannot fit on a 5-bit signed integer (i.e.,
-    // lower than -2^(5-1) = -16, or greater than or equal to
-    // 2^(5-1) - 1 = 15).
+    // lower than 0, or greater than or equal to 2^5 = 32).
     kConstantLargeValue = 6,  // 0b110
 
     kLastLocationKind = kConstantLargeValue
@@ -190,8 +189,10 @@
     }
   }
 
-  DexRegisterLocation(Kind kind, int32_t value)
-      : kind_(kind), value_(value) {}
+  // Required by art::StackMapStream::LocationCatalogEntriesIndices.
+  DexRegisterLocation() : kind_(Kind::kNone), value_(0) {}
+
+  DexRegisterLocation(Kind kind, int32_t value) : kind_(kind), value_(value) {}
 
   static DexRegisterLocation None() {
     return DexRegisterLocation(Kind::kNone, 0);
@@ -220,33 +221,23 @@
  private:
   Kind kind_;
   int32_t value_;
+
+  friend class DexRegisterLocationHashFn;
 };
 
 /**
- * Information on dex register values for a specific PC. The information is
- * of the form:
- * [live_bit_mask, DexRegisterLocation+].
+ * Store information on unique Dex register locations used in a method.
+ * The information is of the form:
+ * [DexRegisterLocation+].
  * DexRegisterLocations are either 1- or 5-byte wide (see art::DexRegisterLocation::Kind).
  */
-class DexRegisterMap {
+class DexRegisterLocationCatalog {
  public:
-  explicit DexRegisterMap(MemoryRegion region) : region_(region) {}
+  explicit DexRegisterLocationCatalog(MemoryRegion region) : region_(region) {}
 
   // Short (compressed) location, fitting on one byte.
   typedef uint8_t ShortLocation;
 
-  static size_t LiveBitMaskSize(uint16_t number_of_dex_registers) {
-    return RoundUp(number_of_dex_registers, kBitsPerByte) / kBitsPerByte;
-  }
-
-  void SetLiveBitMask(size_t offset,
-                      uint16_t number_of_dex_registers,
-                      const BitVector& live_dex_registers_mask) {
-    for (uint16_t i = 0; i < number_of_dex_registers; i++) {
-      region_.StoreBit(offset + i, live_dex_registers_mask.IsBitSet(i));
-    }
-  }
-
   void SetRegisterInfo(size_t offset, const DexRegisterLocation& dex_register_location) {
     DexRegisterLocation::Kind kind = ComputeCompressedKind(dex_register_location);
     int32_t value = dex_register_location.GetValue();
@@ -262,12 +253,12 @@
         DCHECK_EQ(value % kFrameSlotSize, 0);
         value /= kFrameSlotSize;
       }
-      DCHECK(IsUint<kValueBits>(value)) << value;
+      DCHECK(IsShortValue(value)) << value;
       region_.StoreUnaligned<ShortLocation>(offset, MakeShortLocation(kind, value));
     } else {
       // Large location.  Write the location on one byte and the value
       // on 4 bytes.
-      DCHECK(!IsUint<kValueBits>(value)) << value;
+      DCHECK(!IsShortValue(value)) << value;
       if (kind == DexRegisterLocation::Kind::kInStackLargeOffset) {
         // Also divide large stack offsets by 4 for the sake of consistency.
         DCHECK_EQ(value % kFrameSlotSize, 0);
@@ -282,63 +273,39 @@
     }
   }
 
-  bool IsDexRegisterLive(uint16_t dex_register_index) const {
+  // Find the offset of the location catalog entry number `location_catalog_entry_index`.
+  size_t FindLocationOffset(size_t location_catalog_entry_index) const {
     size_t offset = kFixedSize;
-    return region_.LoadBit(offset + dex_register_index);
-  }
-
-  static constexpr size_t kNoDexRegisterLocationOffset = -1;
-
-  static size_t GetDexRegisterMapLocationsOffset(uint16_t number_of_dex_registers) {
-    return kLiveBitMaskOffset + LiveBitMaskSize(number_of_dex_registers);
-  }
-
-  // Find the offset of the Dex register location number `dex_register_index`.
-  size_t FindLocationOffset(uint16_t dex_register_index, uint16_t number_of_dex_registers) const {
-    if (!IsDexRegisterLive(dex_register_index)) return kNoDexRegisterLocationOffset;
-    size_t offset = GetDexRegisterMapLocationsOffset(number_of_dex_registers);
-    // Skip the first `dex_register_index - 1` entries.
-    for (uint16_t i = 0; i < dex_register_index; ++i) {
-      if (IsDexRegisterLive(i)) {
-        // Read the first next byte and inspect its first 3 bits to decide
-        // whether it is a short or a large location.
-        DexRegisterLocation::Kind kind = ExtractKindAtOffset(offset);
-        if (DexRegisterLocation::IsShortLocationKind(kind)) {
-          // Short location.  Skip the current byte.
-          offset += SingleShortEntrySize();
-        } else {
-          // Large location.  Skip the 5 next bytes.
-          offset += SingleLargeEntrySize();
-        }
+    // Skip the first `location_catalog_entry_index - 1` entries.
+    for (uint16_t i = 0; i < location_catalog_entry_index; ++i) {
+      // Read the first next byte and inspect its first 3 bits to decide
+      // whether it is a short or a large location.
+      DexRegisterLocation::Kind kind = ExtractKindAtOffset(offset);
+      if (DexRegisterLocation::IsShortLocationKind(kind)) {
+        // Short location.  Skip the current byte.
+        offset += SingleShortEntrySize();
+      } else {
+        // Large location.  Skip the 5 next bytes.
+        offset += SingleLargeEntrySize();
       }
     }
     return offset;
   }
 
-  // Get the surface kind.
-  DexRegisterLocation::Kind GetLocationKind(uint16_t dex_register_index,
-                                            uint16_t number_of_dex_registers) const {
-    return IsDexRegisterLive(dex_register_index)
-        ? DexRegisterLocation::ConvertToSurfaceKind(
-              GetLocationInternalKind(dex_register_index, number_of_dex_registers))
-        : DexRegisterLocation::Kind::kNone;
+  // Get the internal kind of entry at `location_catalog_entry_index`.
+  DexRegisterLocation::Kind GetLocationInternalKind(size_t location_catalog_entry_index) const {
+    if (location_catalog_entry_index == kNoLocationEntryIndex) {
+      return DexRegisterLocation::Kind::kNone;
+    }
+    return ExtractKindAtOffset(FindLocationOffset(location_catalog_entry_index));
   }
 
-  // Get the internal kind.
-  DexRegisterLocation::Kind GetLocationInternalKind(uint16_t dex_register_index,
-                                                    uint16_t number_of_dex_registers) const {
-    return IsDexRegisterLive(dex_register_index)
-        ? ExtractKindAtOffset(FindLocationOffset(dex_register_index, number_of_dex_registers))
-        : DexRegisterLocation::Kind::kNone;
-  }
-
-  // TODO: Rename as GetDexRegisterLocation?
-  DexRegisterLocation GetLocationKindAndValue(uint16_t dex_register_index,
-                                              uint16_t number_of_dex_registers) const {
-    if (!IsDexRegisterLive(dex_register_index)) {
+  // Get the (surface) kind and value of entry at `location_catalog_entry_index`.
+  DexRegisterLocation GetDexRegisterLocation(size_t location_catalog_entry_index) const {
+    if (location_catalog_entry_index == kNoLocationEntryIndex) {
       return DexRegisterLocation::None();
     }
-    size_t offset = FindLocationOffset(dex_register_index, number_of_dex_registers);
+    size_t offset = FindLocationOffset(location_catalog_entry_index);
     // Read the first byte and inspect its first 3 bits to get the location.
     ShortLocation first_byte = region_.LoadUnaligned<ShortLocation>(offset);
     DexRegisterLocation::Kind kind = ExtractKindFromShortLocation(first_byte);
@@ -361,31 +328,6 @@
     }
   }
 
-  int32_t GetStackOffsetInBytes(uint16_t dex_register_index,
-                                uint16_t number_of_dex_registers) const {
-    DexRegisterLocation location =
-        GetLocationKindAndValue(dex_register_index, number_of_dex_registers);
-    DCHECK(location.GetKind() == DexRegisterLocation::Kind::kInStack);
-    // GetLocationKindAndValue returns the offset in bytes.
-    return location.GetValue();
-  }
-
-  int32_t GetConstant(uint16_t dex_register_index, uint16_t number_of_dex_registers) const {
-    DexRegisterLocation location =
-        GetLocationKindAndValue(dex_register_index, number_of_dex_registers);
-    DCHECK(location.GetKind() == DexRegisterLocation::Kind::kConstant);
-    return location.GetValue();
-  }
-
-  int32_t GetMachineRegister(uint16_t dex_register_index, uint16_t number_of_dex_registers) const {
-    DexRegisterLocation location =
-        GetLocationKindAndValue(dex_register_index, number_of_dex_registers);
-    DCHECK(location.GetInternalKind() == DexRegisterLocation::Kind::kInRegister
-           || location.GetInternalKind() == DexRegisterLocation::Kind::kInFpuRegister)
-        << DexRegisterLocation::PrettyDescriptor(location.GetInternalKind());
-    return location.GetValue();
-  }
-
   // Compute the compressed kind of `location`.
   static DexRegisterLocation::Kind ComputeCompressedKind(const DexRegisterLocation& location) {
     switch (location.GetInternalKind()) {
@@ -395,22 +337,21 @@
 
       case DexRegisterLocation::Kind::kInRegister:
         DCHECK_GE(location.GetValue(), 0);
-        DCHECK_LT(location.GetValue(), 1 << DexRegisterMap::kValueBits);
+        DCHECK_LT(location.GetValue(), 1 << kValueBits);
         return DexRegisterLocation::Kind::kInRegister;
 
       case DexRegisterLocation::Kind::kInFpuRegister:
         DCHECK_GE(location.GetValue(), 0);
-        DCHECK_LT(location.GetValue(), 1 << DexRegisterMap::kValueBits);
+        DCHECK_LT(location.GetValue(), 1 << kValueBits);
         return DexRegisterLocation::Kind::kInFpuRegister;
 
       case DexRegisterLocation::Kind::kInStack:
-        DCHECK_EQ(location.GetValue() % kFrameSlotSize, 0);
-        return IsUint<DexRegisterMap::kValueBits>(location.GetValue() / kFrameSlotSize)
+        return IsShortStackOffsetValue(location.GetValue())
             ? DexRegisterLocation::Kind::kInStack
             : DexRegisterLocation::Kind::kInStackLargeOffset;
 
       case DexRegisterLocation::Kind::kConstant:
-        return IsUint<DexRegisterMap::kValueBits>(location.GetValue())
+        return IsShortConstantValue(location.GetValue())
             ? DexRegisterLocation::Kind::kConstant
             : DexRegisterLocation::Kind::kConstantLargeValue;
 
@@ -430,11 +371,10 @@
         return true;
 
       case DexRegisterLocation::Kind::kInStack:
-        DCHECK_EQ(location.GetValue() % kFrameSlotSize, 0);
-        return IsUint<kValueBits>(location.GetValue() / kFrameSlotSize);
+        return IsShortStackOffsetValue(location.GetValue());
 
       case DexRegisterLocation::Kind::kConstant:
-        return IsUint<kValueBits>(location.GetValue());
+        return IsShortConstantValue(location.GetValue());
 
       default:
         UNREACHABLE();
@@ -442,9 +382,7 @@
   }
 
   static size_t EntrySize(const DexRegisterLocation& location) {
-    return CanBeEncodedAsShortLocation(location)
-        ? DexRegisterMap::SingleShortEntrySize()
-        : DexRegisterMap::SingleLargeEntrySize();
+    return CanBeEncodedAsShortLocation(location) ? SingleShortEntrySize() : SingleLargeEntrySize();
   }
 
   static size_t SingleShortEntrySize() {
@@ -459,10 +397,14 @@
     return region_.size();
   }
 
-  static constexpr int kLiveBitMaskOffset = 0;
-  static constexpr int kFixedSize = kLiveBitMaskOffset;
+  // Special (invalid) Dex register location catalog entry index meaning
+  // that there is no location for a given Dex register (i.e., it is
+  // mapped to a DexRegisterLocation::Kind::kNone location).
+  static constexpr size_t kNoLocationEntryIndex = -1;
 
  private:
+  static constexpr int kFixedSize = 0;
+
   // Width of the kind "field" in a short location, in bits.
   static constexpr size_t kKindBits = 3;
   // Width of the value "field" in a short location, in bits.
@@ -473,10 +415,24 @@
   static constexpr size_t kKindOffset = 0;
   static constexpr size_t kValueOffset = kKindBits;
 
+  static bool IsShortStackOffsetValue(int32_t value) {
+    DCHECK_EQ(value % kFrameSlotSize, 0);
+    return IsShortValue(value / kFrameSlotSize);
+  }
+
+  static bool IsShortConstantValue(int32_t value) {
+    return IsShortValue(value);
+  }
+
+  static bool IsShortValue(int32_t value) {
+    return IsUint<kValueBits>(value);
+  }
+
   static ShortLocation MakeShortLocation(DexRegisterLocation::Kind kind, int32_t value) {
-    DCHECK(IsUint<kKindBits>(static_cast<uint8_t>(kind))) << static_cast<uint8_t>(kind);
-    DCHECK(IsUint<kValueBits>(value)) << value;
-    return (static_cast<uint8_t>(kind) & kKindMask) << kKindOffset
+    uint8_t kind_integer_value = static_cast<uint8_t>(kind);
+    DCHECK(IsUint<kKindBits>(kind_integer_value)) << kind_integer_value;
+    DCHECK(IsShortValue(value)) << value;
+    return (kind_integer_value & kKindMask) << kKindOffset
         | (value & kValueMask) << kValueOffset;
   }
 
@@ -504,6 +460,210 @@
   friend class StackMapStream;
 };
 
+/* Information on Dex register locations for a specific PC, mapping a
+ * stack map's Dex register to a location entry in a DexRegisterLocationCatalog.
+ * The information is of the form:
+ * [live_bit_mask, entries*]
+ * where entries are concatenated unsigned integer values encoded on a number
+ * of bits (fixed per DexRegisterMap instances of a CodeInfo object) depending
+ * on the number of entries in the Dex register location catalog
+ * (see DexRegisterMap::SingleEntrySizeInBits).  The map is 1-byte aligned.
+ */
+class DexRegisterMap {
+ public:
+  explicit DexRegisterMap(MemoryRegion region) : region_(region) {}
+
+  // Get the surface kind of Dex register `dex_register_number`.
+  DexRegisterLocation::Kind GetLocationKind(uint16_t dex_register_number,
+                                            uint16_t number_of_dex_registers,
+                                            const CodeInfo& code_info) const {
+    return DexRegisterLocation::ConvertToSurfaceKind(
+        GetLocationInternalKind(dex_register_number, number_of_dex_registers, code_info));
+  }
+
+  // Get the internal kind of Dex register `dex_register_number`.
+  DexRegisterLocation::Kind GetLocationInternalKind(uint16_t dex_register_number,
+                                                    uint16_t number_of_dex_registers,
+                                                    const CodeInfo& code_info) const;
+
+  // Get the Dex register location `dex_register_number`.
+  DexRegisterLocation GetDexRegisterLocation(uint16_t dex_register_number,
+                                             uint16_t number_of_dex_registers,
+                                             const CodeInfo& code_info) const;
+
+  int32_t GetStackOffsetInBytes(uint16_t dex_register_number,
+                                uint16_t number_of_dex_registers,
+                                const CodeInfo& code_info) const {
+    DexRegisterLocation location =
+        GetDexRegisterLocation(dex_register_number, number_of_dex_registers, code_info);
+    DCHECK(location.GetKind() == DexRegisterLocation::Kind::kInStack);
+    // GetDexRegisterLocation returns the offset in bytes.
+    return location.GetValue();
+  }
+
+  int32_t GetConstant(uint16_t dex_register_number,
+                      uint16_t number_of_dex_registers,
+                      const CodeInfo& code_info) const {
+    DexRegisterLocation location =
+        GetDexRegisterLocation(dex_register_number, number_of_dex_registers, code_info);
+    DCHECK(location.GetKind() == DexRegisterLocation::Kind::kConstant);
+    return location.GetValue();
+  }
+
+  int32_t GetMachineRegister(uint16_t dex_register_number,
+                             uint16_t number_of_dex_registers,
+                             const CodeInfo& code_info) const {
+    DexRegisterLocation location =
+        GetDexRegisterLocation(dex_register_number, number_of_dex_registers, code_info);
+    DCHECK(location.GetInternalKind() == DexRegisterLocation::Kind::kInRegister
+           || location.GetInternalKind() == DexRegisterLocation::Kind::kInFpuRegister)
+        << DexRegisterLocation::PrettyDescriptor(location.GetInternalKind());
+    return location.GetValue();
+  }
+
+  // Get the index of the entry in the Dex register location catalog
+  // corresponding to `dex_register_number`.
+  size_t GetLocationCatalogEntryIndex(uint16_t dex_register_number,
+                                      uint16_t number_of_dex_registers,
+                                      size_t number_of_location_catalog_entries) const {
+    if (!IsDexRegisterLive(dex_register_number)) {
+      return DexRegisterLocationCatalog::kNoLocationEntryIndex;
+    }
+
+    if (number_of_location_catalog_entries == 1) {
+      // We do not allocate space for location maps in the case of a
+      // single-entry location catalog, as it is useless.  The only valid
+      // entry index is 0;
+      return 0;
+    }
+
+    // The bit offset of the beginning of the map locations.
+    size_t map_locations_offset_in_bits =
+        GetLocationMappingDataOffset(number_of_dex_registers) * kBitsPerByte;
+    size_t index_in_dex_register_map = GetIndexInDexRegisterMap(dex_register_number);
+    DCHECK_LT(index_in_dex_register_map, GetNumberOfLiveDexRegisters(number_of_dex_registers));
+    // The bit size of an entry.
+    size_t map_entry_size_in_bits = SingleEntrySizeInBits(number_of_location_catalog_entries);
+    // The bit offset where `index_in_dex_register_map` is located.
+    size_t entry_offset_in_bits =
+        map_locations_offset_in_bits + index_in_dex_register_map * map_entry_size_in_bits;
+    size_t location_catalog_entry_index =
+        region_.LoadBits(entry_offset_in_bits, map_entry_size_in_bits);
+    DCHECK_LT(location_catalog_entry_index, number_of_location_catalog_entries);
+    return location_catalog_entry_index;
+  }
+
+  // Map entry at `index_in_dex_register_map` to `location_catalog_entry_index`.
+  void SetLocationCatalogEntryIndex(size_t index_in_dex_register_map,
+                                    size_t location_catalog_entry_index,
+                                    uint16_t number_of_dex_registers,
+                                    size_t number_of_location_catalog_entries) {
+    DCHECK_LT(index_in_dex_register_map, GetNumberOfLiveDexRegisters(number_of_dex_registers));
+    DCHECK_LT(location_catalog_entry_index, number_of_location_catalog_entries);
+
+    if (number_of_location_catalog_entries == 1) {
+      // We do not allocate space for location maps in the case of a
+      // single-entry location catalog, as it is useless.
+      return;
+    }
+
+    // The bit offset of the beginning of the map locations.
+    size_t map_locations_offset_in_bits =
+        GetLocationMappingDataOffset(number_of_dex_registers) * kBitsPerByte;
+    // The bit size of an entry.
+    size_t map_entry_size_in_bits = SingleEntrySizeInBits(number_of_location_catalog_entries);
+    // The bit offset where `index_in_dex_register_map` is located.
+    size_t entry_offset_in_bits =
+        map_locations_offset_in_bits + index_in_dex_register_map * map_entry_size_in_bits;
+    region_.StoreBits(entry_offset_in_bits, location_catalog_entry_index, map_entry_size_in_bits);
+  }
+
+  void SetLiveBitMask(uint16_t number_of_dex_registers,
+                      const BitVector& live_dex_registers_mask) {
+    size_t live_bit_mask_offset_in_bits = GetLiveBitMaskOffset() * kBitsPerByte;
+    for (uint16_t i = 0; i < number_of_dex_registers; ++i) {
+      region_.StoreBit(live_bit_mask_offset_in_bits + i, live_dex_registers_mask.IsBitSet(i));
+    }
+  }
+
+  bool IsDexRegisterLive(uint16_t dex_register_number) const {
+    size_t live_bit_mask_offset_in_bits = GetLiveBitMaskOffset() * kBitsPerByte;
+    return region_.LoadBit(live_bit_mask_offset_in_bits + dex_register_number);
+  }
+
+  size_t GetNumberOfLiveDexRegisters(uint16_t number_of_dex_registers) const {
+    size_t number_of_live_dex_registers = 0;
+    for (size_t i = 0; i < number_of_dex_registers; ++i) {
+      if (IsDexRegisterLive(i)) {
+        ++number_of_live_dex_registers;
+      }
+    }
+    return number_of_live_dex_registers;
+  }
+
+  static size_t GetLiveBitMaskOffset() {
+    return kFixedSize;
+  }
+
+  // Compute the size of the live register bit mask (in bytes), for a
+  // method having `number_of_dex_registers` Dex registers.
+  static size_t GetLiveBitMaskSize(uint16_t number_of_dex_registers) {
+    return RoundUp(number_of_dex_registers, kBitsPerByte) / kBitsPerByte;
+  }
+
+  static size_t GetLocationMappingDataOffset(uint16_t number_of_dex_registers) {
+    return GetLiveBitMaskOffset() + GetLiveBitMaskSize(number_of_dex_registers);
+  }
+
+  size_t GetLocationMappingDataSize(uint16_t number_of_dex_registers,
+                                    size_t number_of_location_catalog_entries) const {
+    size_t location_mapping_data_size_in_bits =
+        GetNumberOfLiveDexRegisters(number_of_dex_registers)
+        * SingleEntrySizeInBits(number_of_location_catalog_entries);
+    return RoundUp(location_mapping_data_size_in_bits, kBitsPerByte) / kBitsPerByte;
+  }
+
+  // Return the size of a map entry in bits.  Note that if
+  // `number_of_location_catalog_entries` equals 1, this function returns 0,
+  // which is fine, as there is no need to allocate a map for a
+  // single-entry location catalog; the only valid location catalog entry index
+  // for a live register in this case is 0 and there is no need to
+  // store it.
+  static size_t SingleEntrySizeInBits(size_t number_of_location_catalog_entries) {
+    // Handle the case of 0, as we cannot pass 0 to art::WhichPowerOf2.
+    return number_of_location_catalog_entries == 0
+        ? 0u
+        : WhichPowerOf2(RoundUpToPowerOfTwo(number_of_location_catalog_entries));
+  }
+
+  // Return the size of the DexRegisterMap object, in bytes.
+  size_t Size() const {
+    return region_.size();
+  }
+
+ private:
+  // Return the index in the Dex register map corresponding to the Dex
+  // register number `dex_register_number`.
+  size_t GetIndexInDexRegisterMap(uint16_t dex_register_number) const {
+    if (!IsDexRegisterLive(dex_register_number)) {
+      return kInvalidIndexInDexRegisterMap;
+    }
+    return GetNumberOfLiveDexRegisters(dex_register_number);
+  }
+
+  // Special (invalid) Dex register map entry index meaning that there
+  // is no index in the map for a given Dex register (i.e., it must
+  // have been mapped to a DexRegisterLocation::Kind::kNone location).
+  static constexpr size_t kInvalidIndexInDexRegisterMap = -1;
+
+  static constexpr int kFixedSize = 0;
+
+  MemoryRegion region_;
+
+  friend class CodeInfo;
+  friend class StackMapStream;
+};
+
 /**
  * A Stack Map holds compilation information for a specific PC necessary for:
  * - Mapping it to a dex PC,
@@ -513,7 +673,8 @@
  * - Knowing the values of dex registers.
  *
  * The information is of the form:
- * [dex_pc, native_pc_offset, dex_register_map_offset, inlining_info_offset, register_mask, stack_mask].
+ * [dex_pc, native_pc_offset, dex_register_map_offset, inlining_info_offset, register_mask,
+ * stack_mask].
  *
  * Note that register_mask is fixed size, but stack_mask is variable size, depending on the
  * stack size of a method.
@@ -619,7 +780,8 @@
 /**
  * Wrapper around all compiler information collected for a method.
  * The information is of the form:
- * [overall_size, number_of_stack_maps, stack_mask_size, StackMap+, DexRegisterInfo+, InlineInfo*].
+ * [overall_size, number_of_location_catalog_entries, number_of_stack_maps, stack_mask_size,
+ * DexRegisterLocationCatalog+, StackMap+, DexRegisterMap+, InlineInfo*].
  */
 class CodeInfo {
  public:
@@ -704,6 +866,16 @@
         + (HasSmallDexRegisterMap() ? sizeof(uint8_t) : sizeof(uint32_t));
   }
 
+  uint32_t GetDexRegisterLocationCatalogOffset() const {
+    return kFixedSize;
+  }
+
+  DexRegisterLocationCatalog GetDexRegisterLocationCatalog() const {
+    return DexRegisterLocationCatalog(region_.Subregion(
+        GetDexRegisterLocationCatalogOffset(),
+        GetDexRegisterLocationCatalogSize()));
+  }
+
   StackMap GetStackMapAt(size_t i) const {
     size_t size = StackMapSize();
     return StackMap(GetStackMaps().Subregion(i * size, size));
@@ -717,6 +889,19 @@
     region_.StoreUnaligned<uint32_t>(kOverallSizeOffset, size);
   }
 
+  uint32_t GetNumberOfDexRegisterLocationCatalogEntries() const {
+    return region_.LoadUnaligned<uint32_t>(kNumberOfDexRegisterLocationCatalogEntriesOffset);
+  }
+
+  void SetNumberOfDexRegisterLocationCatalogEntries(uint32_t num_entries) {
+    region_.StoreUnaligned<uint32_t>(kNumberOfDexRegisterLocationCatalogEntriesOffset, num_entries);
+  }
+
+  uint32_t GetDexRegisterLocationCatalogSize() const {
+    return ComputeDexRegisterLocationCatalogSize(GetDexRegisterLocationCatalogOffset(),
+                                                 GetNumberOfDexRegisterLocationCatalogEntries());
+  }
+
   uint32_t GetStackMaskSize() const {
     return region_.LoadUnaligned<uint32_t>(kStackMaskSizeOffset);
   }
@@ -745,22 +930,22 @@
   }
 
   // Get the size all the stack maps of this CodeInfo object, in bytes.
-  size_t StackMapsSize() const {
+  size_t GetStackMapsSize() const {
     return StackMapSize() * GetNumberOfStackMaps();
   }
 
   size_t GetDexRegisterMapsOffset() const {
-    return CodeInfo::kFixedSize + StackMapsSize();
+    return GetStackMapsOffset() + GetStackMapsSize();
   }
 
   uint32_t GetStackMapsOffset() const {
-    return kFixedSize;
+    return GetDexRegisterLocationCatalogOffset() + GetDexRegisterLocationCatalogSize();
   }
 
   DexRegisterMap GetDexRegisterMapOf(StackMap stack_map, uint32_t number_of_dex_registers) const {
     DCHECK(stack_map.HasDexRegisterMap(*this));
-    uint32_t offset = stack_map.GetDexRegisterMapOffset(*this) + GetDexRegisterMapsOffset();
-    size_t size = ComputeDexRegisterMapSize(offset, number_of_dex_registers);
+    uint32_t offset = GetDexRegisterMapsOffset() + stack_map.GetDexRegisterMapOffset(*this);
+    size_t size = ComputeDexRegisterMapSizeOf(offset, number_of_dex_registers);
     return DexRegisterMap(region_.Subregion(offset, size));
   }
 
@@ -803,7 +988,10 @@
   // typedefs (and document the memory layout of CodeInfo).
   static constexpr int kOverallSizeOffset = 0;
   static constexpr int kEncodingInfoOffset = kOverallSizeOffset + sizeof(uint32_t);
-  static constexpr int kNumberOfStackMapsOffset = kEncodingInfoOffset + sizeof(uint8_t);
+  static constexpr int kNumberOfDexRegisterLocationCatalogEntriesOffset =
+      kEncodingInfoOffset + sizeof(uint8_t);
+  static constexpr int kNumberOfStackMapsOffset =
+      kNumberOfDexRegisterLocationCatalogEntriesOffset + sizeof(uint32_t);
   static constexpr int kStackMaskSizeOffset = kNumberOfStackMapsOffset + sizeof(uint32_t);
   static constexpr int kFixedSize = kStackMaskSizeOffset + sizeof(uint32_t);
 
@@ -816,37 +1004,56 @@
   MemoryRegion GetStackMaps() const {
     return region_.size() == 0
         ? MemoryRegion()
-        : region_.Subregion(kFixedSize, StackMapsSize());
+        : region_.Subregion(GetStackMapsOffset(), GetStackMapsSize());
   }
 
-  // Compute the size of a Dex register map starting at offset `origin` in
-  // `region_` and containing `number_of_dex_registers` locations.
-  size_t ComputeDexRegisterMapSize(uint32_t origin, uint32_t number_of_dex_registers) const {
-    // TODO: Ideally, we would like to use art::DexRegisterMap::Size or
-    // art::DexRegisterMap::FindLocationOffset, but the DexRegisterMap is not
-    // yet built.  Try to factor common code.
-    size_t offset =
-        origin + DexRegisterMap::GetDexRegisterMapLocationsOffset(number_of_dex_registers);
+  // Compute the size of the Dex register map associated to the stack map at
+  // `dex_register_map_offset_in_code_info`.
+  size_t ComputeDexRegisterMapSizeOf(uint32_t dex_register_map_offset_in_code_info,
+                                     uint16_t number_of_dex_registers) const {
+    // Offset where the actual mapping data starts within art::DexRegisterMap.
+    size_t location_mapping_data_offset_in_dex_register_map =
+        DexRegisterMap::GetLocationMappingDataOffset(number_of_dex_registers);
+    // Create a temporary art::DexRegisterMap to be able to call
+    // art::DexRegisterMap::GetNumberOfLiveDexRegisters and
+    DexRegisterMap dex_register_map_without_locations(
+        MemoryRegion(region_.Subregion(dex_register_map_offset_in_code_info,
+                                       location_mapping_data_offset_in_dex_register_map)));
+    size_t number_of_live_dex_registers =
+        dex_register_map_without_locations.GetNumberOfLiveDexRegisters(number_of_dex_registers);
+    size_t location_mapping_data_size_in_bits =
+        DexRegisterMap::SingleEntrySizeInBits(GetNumberOfDexRegisterLocationCatalogEntries())
+        * number_of_live_dex_registers;
+    size_t location_mapping_data_size_in_bytes =
+        RoundUp(location_mapping_data_size_in_bits, kBitsPerByte) / kBitsPerByte;
+    size_t dex_register_map_size =
+        location_mapping_data_offset_in_dex_register_map + location_mapping_data_size_in_bytes;
+    return dex_register_map_size;
+  }
 
-    // Create a temporary DexRegisterMap to be able to call DexRegisterMap.IsDexRegisterLive.
-    DexRegisterMap only_live_mask(MemoryRegion(region_.Subregion(origin, offset - origin)));
+  // Compute the size of a Dex register location catalog starting at offset `origin`
+  // in `region_` and containing `number_of_dex_locations` entries.
+  size_t ComputeDexRegisterLocationCatalogSize(uint32_t origin,
+                                               uint32_t number_of_dex_locations) const {
+    // TODO: Ideally, we would like to use art::DexRegisterLocationCatalog::Size or
+    // art::DexRegisterLocationCatalog::FindLocationOffset, but the
+    // DexRegisterLocationCatalog is not yet built.  Try to factor common code.
+    size_t offset = origin + DexRegisterLocationCatalog::kFixedSize;
 
-    // Skip the first `number_of_dex_registers - 1` entries.
-    for (uint16_t i = 0; i < number_of_dex_registers; ++i) {
-      if (only_live_mask.IsDexRegisterLive(i)) {
-        // Read the first next byte and inspect its first 3 bits to decide
-        // whether it is a short or a large location.
-        DexRegisterMap::ShortLocation first_byte =
-            region_.LoadUnaligned<DexRegisterMap::ShortLocation>(offset);
-        DexRegisterLocation::Kind kind =
-            DexRegisterMap::ExtractKindFromShortLocation(first_byte);
-        if (DexRegisterLocation::IsShortLocationKind(kind)) {
-          // Short location.  Skip the current byte.
-          offset += DexRegisterMap::SingleShortEntrySize();
-        } else {
-          // Large location.  Skip the 5 next bytes.
-          offset += DexRegisterMap::SingleLargeEntrySize();
-        }
+    // Skip the first `number_of_dex_locations - 1` entries.
+    for (uint16_t i = 0; i < number_of_dex_locations; ++i) {
+      // Read the first next byte and inspect its first 3 bits to decide
+      // whether it is a short or a large location.
+      DexRegisterLocationCatalog::ShortLocation first_byte =
+          region_.LoadUnaligned<DexRegisterLocationCatalog::ShortLocation>(offset);
+      DexRegisterLocation::Kind kind =
+          DexRegisterLocationCatalog::ExtractKindFromShortLocation(first_byte);
+      if (DexRegisterLocation::IsShortLocationKind(kind)) {
+        // Short location.  Skip the current byte.
+        offset += DexRegisterLocationCatalog::SingleShortEntrySize();
+      } else {
+        // Large location.  Skip the 5 next bytes.
+        offset += DexRegisterLocationCatalog::SingleLargeEntrySize();
       }
     }
     size_t size = offset - origin;