diff --git a/src/class_linker_test.cc b/src/class_linker_test.cc
index 4b48892..f43e47c 100644
--- a/src/class_linker_test.cc
+++ b/src/class_linker_test.cc
@@ -545,6 +545,8 @@
     offsets.push_back(CheckOffset(OFFSETOF_MEMBER(Method, dex_cache_strings_),                    "shadow$_dex_cache_strings_"));
     offsets.push_back(CheckOffset(OFFSETOF_MEMBER(Method, invoke_stub_array_),                    "shadow$_invoke_stub_array_"));
     offsets.push_back(CheckOffset(OFFSETOF_MEMBER(Method, mapping_table_),                        "shadow$_mapping_table_"));
+    offsets.push_back(CheckOffset(OFFSETOF_MEMBER(Method, register_map_data_),                    "shadow$_register_map_data_"));
+    offsets.push_back(CheckOffset(OFFSETOF_MEMBER(Method, register_map_header_),                  "shadow$_register_map_header_"));
     offsets.push_back(CheckOffset(OFFSETOF_MEMBER(Method, shorty_),                               "shadow$_shorty_"));
     offsets.push_back(CheckOffset(OFFSETOF_MEMBER(Method, signature_),                            "shadow$_signature_"));
 
diff --git a/src/dex_verifier.cc b/src/dex_verifier.cc
index 5d622f9..b6739f8 100644
--- a/src/dex_verifier.cc
+++ b/src/dex_verifier.cc
@@ -351,13 +351,19 @@
 
   /* Generate a register map. */
   if (generate_register_map) {
-    RegisterMap* map = GenerateRegisterMapV(vdata);
+    UniquePtr<RegisterMap> map(GenerateRegisterMapV(vdata));
     /*
      * Tuck the map into the Method. It will either get used directly or, if
      * we're in dexopt, will be packed up and appended to the DEX file.
      */
-    // TODO: Put the map somewhere...
-    delete map;
+    ByteArray* header = ByteArray::Alloc(sizeof(RegisterMapHeader));
+    ByteArray* data = ByteArray::Alloc(ComputeRegisterMapSize(map.get()));
+
+    memcpy(header->GetData(), map.get()->header_, sizeof(RegisterMapHeader));
+    memcpy(data->GetData(), map.get()->data_, ComputeRegisterMapSize(map.get()));
+
+    method->SetRegisterMapHeader(header);
+    method->SetRegisterMapData(data);
   }
 
   return true;
@@ -5302,7 +5308,7 @@
       true, data_size);
 
   /* Populate it. */
-  uint8_t* map_data = map->data_.get();
+  uint8_t* map_data = map->data_;
   for (i = 0; i < (int) vdata->code_item_->insns_size_; i++) {
     if (InsnIsGcPoint(vdata->insn_flags_.get(), i)) {
       assert(vdata->register_lines_[i].reg_types_.get() != NULL);
@@ -5318,7 +5324,7 @@
     }
   }
 
-  assert((uint32_t) map_data - (uint32_t) map->data_.get() == data_size);
+  assert((uint32_t) map_data - (uint32_t) map->data_ == data_size);
 
   // TODO: Remove this check when it's really running...
 #if 1
@@ -5387,14 +5393,14 @@
 }
 
 bool DexVerifier::VerifyMap(VerifierData* vdata, const RegisterMap* map) {
-  const uint8_t* raw_map = map->data_.get();
-  uint8_t format = map->format_;
-  const int num_entries = map->num_entries_;
+  const uint8_t* raw_map = map->data_;
+  uint8_t format = map->header_->format_;
+  const int num_entries = map->header_->num_entries_;
   int ent;
 
-  if ((vdata->code_item_->registers_size_ + 7) / 8 != map->reg_width_) {
+  if ((vdata->code_item_->registers_size_ + 7) / 8 != map->header_->reg_width_) {
     LOG(ERROR) << "GLITCH: registersSize=" << vdata->code_item_->registers_size_
-               << ", reg_width=" << map->reg_width_;
+               << ", reg_width=" << map->header_->reg_width_;
     return false;
   }
 
@@ -5461,12 +5467,13 @@
     return false;
   }
 
-  if (map1->format_ != map2->format_ || map1->reg_width_ != map2->reg_width_ ||
-      map1->num_entries_ != map2->num_entries_ ||
-      map1->format_on_heap_ != map2->format_on_heap_) {
+  if (map1->header_->format_ != map2->header_->format_ ||
+      map1->header_->reg_width_ != map2->header_->reg_width_ ||
+      map1->header_->num_entries_ != map2->header_->num_entries_ ||
+      map1->header_->format_on_heap_ != map2->header_->format_on_heap_) {
     LOG(ERROR) << "CompareMaps: fields mismatch";
   }
-  if (memcmp(map1->data_.get(), map2->data_.get(), size1) != 0) {
+  if (memcmp(map1->data_, map2->data_, size1) != 0) {
     LOG(ERROR) << "CompareMaps: data mismatch";
     return false;
   }
@@ -5475,8 +5482,8 @@
 }
 
 size_t DexVerifier::ComputeRegisterMapSize(const RegisterMap* map) {
-  uint8_t format = map->format_;
-  uint16_t num_entries = map->num_entries_;
+  uint8_t format = map->header_->format_;
+  uint16_t num_entries = map->header_->num_entries_;
 
   assert(map != NULL);
 
@@ -5484,13 +5491,13 @@
     case kRegMapFormatNone:
       return 1;
     case kRegMapFormatCompact8:
-      return (1 + map->reg_width_) * num_entries;
+      return (1 + map->header_->reg_width_) * num_entries;
     case kRegMapFormatCompact16:
-      return (2 + map->reg_width_) * num_entries;
+      return (2 + map->header_->reg_width_) * num_entries;
     case kRegMapFormatDifferential:
       {
         /* Decoded ULEB128 length. */
-        const uint8_t* ptr = map->data_.get();
+        const uint8_t* ptr = map->data_;
         return DecodeUnsignedLeb128(&ptr);
       }
     default:
@@ -5554,7 +5561,7 @@
   uint8_t* tmp_ptr;
   int addr_width;
 
-  uint8_t format = map->format_;
+  uint8_t format = map->header_->format_;
   switch (format) {
     case kRegMapFormatCompact8:
       addr_width = 1;
@@ -5567,8 +5574,8 @@
       return NULL;
   }
 
-  int reg_width = map->reg_width_;
-  int num_entries = map->num_entries_;
+  int reg_width = map->header_->reg_width_;
+  int num_entries = map->header_->num_entries_;
 
   if (num_entries <= 1) {
     return NULL;
@@ -5595,7 +5602,7 @@
 
   tmp_ptr = tmp_buf.get();
 
-  const uint8_t* map_data = map->data_.get();
+  const uint8_t* map_data = map->data_;
   const uint8_t* prev_bits;
   uint16_t addr, prev_addr;
 
@@ -5714,7 +5721,7 @@
   RegisterMap* new_map = new RegisterMap(kRegMapFormatDifferential, reg_width,
       num_entries, true, new_map_size);
 
-  tmp_ptr = new_map->data_.get();
+  tmp_ptr = new_map->data_;
   tmp_ptr = WriteUnsignedLeb128(tmp_ptr, new_data_size);
   memcpy(tmp_ptr, tmp_buf.get(), new_data_size);
 
@@ -5723,7 +5730,7 @@
 
 DexVerifier::RegisterMap* DexVerifier::UncompressMapDifferential(
     const RegisterMap* map) {
-  uint8_t format = map->format_;
+  uint8_t format = map->header_->format_;
   RegisterMapFormat new_format;
   int reg_width, num_entries, new_addr_width, new_data_size;
 
@@ -5732,11 +5739,11 @@
     return NULL;
   }
 
-  reg_width = map->reg_width_;
-  num_entries = map->num_entries_;
+  reg_width = map->header_->reg_width_;
+  num_entries = map->header_->num_entries_;
 
   /* Get the data size; we can check this at the end. */
-  const uint8_t* src_ptr = map->data_.get();
+  const uint8_t* src_ptr = map->data_;
   int expected_src_len = DecodeUnsignedLeb128(&src_ptr);
   const uint8_t* src_start = src_ptr;
 
@@ -5757,7 +5764,7 @@
       true, new_data_size);
 
   /* Write the start address and initial bits to the new map. */
-  uint8_t* dst_ptr = new_map->data_.get();
+  uint8_t* dst_ptr = new_map->data_;
 
   *dst_ptr++ = addr & 0xff;
   if (new_addr_width > 1)
@@ -5823,8 +5830,8 @@
     dst_ptr += reg_width;
   }
 
-  if (dst_ptr - new_map->data_.get() != new_data_size) {
-    LOG(ERROR) << "ERROR: output " << dst_ptr - new_map->data_.get()
+  if (dst_ptr - new_map->data_ != new_data_size) {
+    LOG(ERROR) << "ERROR: output " << dst_ptr - new_map->data_
                << " bytes, expected " << new_data_size;
     free(new_map);
     return NULL;
diff --git a/src/dex_verifier.h b/src/dex_verifier.h
index 41223b2..404227d 100644
--- a/src/dex_verifier.h
+++ b/src/dex_verifier.h
@@ -34,10 +34,6 @@
 
 class DexVerifier {
  public:
-  /* Verify a class. Returns "true" on success. */
-  static bool VerifyClass(Class* klass);
-
- private:
   /*
    * RegType holds information about the type of data held in a register.
    * For most types it's a simple enum. For reference types it holds a
@@ -361,6 +357,20 @@
     }
   };
 
+  /* Header for RegisterMap */
+  struct RegisterMapHeader {
+    uint8_t format_;          /* enum RegisterMapFormat; MUST be first entry */
+    uint8_t reg_width_;       /* bytes per register line, 1+ */
+    uint16_t num_entries_;    /* number of entries */
+    bool    format_on_heap_;  /* indicates allocation on heap */
+
+    RegisterMapHeader(uint8_t format, uint8_t reg_width, uint16_t num_entries,
+        bool format_on_heap)
+        : format_(format), reg_width_(reg_width), num_entries_(num_entries),
+          format_on_heap_(format_on_heap) {
+    }
+  };
+
   /*
    * This is a single variable-size structure. It may be allocated on the
    * heap or mapped out of a (post-dexopt) DEX file.
@@ -374,19 +384,29 @@
    * Size of (format==FormatCompact16): 4 + (2 + reg_width) * num_entries
    */
   struct RegisterMap {
-    /* header */
-    uint8_t format_;          /* enum RegisterMapFormat; MUST be first entry */
-    uint8_t reg_width_;       /* bytes per register line, 1+ */
-    uint16_t num_entries_;    /* number of entries */
-    bool    format_on_heap_;  /* indicates allocation on heap */
+    RegisterMapHeader* header_;
+    uint8_t* data_;
+    bool needs_free_;
 
-    /* raw data starts here; need not be aligned */
-    UniquePtr<uint8_t[]> data_;
+    RegisterMap(ByteArray* header, ByteArray* data) {
+      header_ = (RegisterMapHeader*) header->GetData();
+      data_ = (uint8_t*) data->GetData();
+      needs_free_ = false;
+    }
 
     RegisterMap(uint8_t format, uint8_t reg_width, uint16_t num_entries,
-        bool format_on_heap, uint32_t data_size)
-        : format_(format), reg_width_(reg_width), num_entries_(num_entries),
-          format_on_heap_(format_on_heap), data_(new uint8_t[data_size]()) {
+        bool format_on_heap, uint32_t data_size) {
+      header_ = new RegisterMapHeader(format, reg_width, num_entries,
+          format_on_heap);
+      data_ = new uint8_t[data_size]();
+      needs_free_ = true;
+    }
+
+    ~RegisterMap() {
+      if (needs_free_) {
+        delete header_;
+        delete [] data_;
+      }
     }
   };
 
@@ -541,6 +561,10 @@
     return (uint32_t) (kRegTypeUninit | (uidx << kRegTypeUninitShift));
   }
 
+  /* Verify a class. Returns "true" on success. */
+  static bool VerifyClass(Class* klass);
+
+ private:
   /*
    * Perform verification on a single method.
    *
diff --git a/src/object.h b/src/object.h
index 5e09f2e..3e154e4 100644
--- a/src/object.h
+++ b/src/object.h
@@ -636,6 +636,14 @@
 
   void SetName(String* new_name);
 
+  ByteArray* GetRegisterMapData() const;
+
+  void SetRegisterMapData(ByteArray* new_data);
+
+  ByteArray* GetRegisterMapHeader() const;
+
+  void SetRegisterMapHeader(ByteArray* new_header);
+
   String* GetShorty() const;
 
   void SetShorty(String* new_shorty);
@@ -1012,6 +1020,10 @@
   // Storage for mapping_table_
   const ByteArray* mapping_table_;
 
+  // Byte arrays that hold data for the register maps
+  const ByteArray* register_map_data_;
+  const ByteArray* register_map_header_;
+
   // The short-form method descriptor string.
   String* shorty_;
 
@@ -2515,6 +2527,26 @@
 
 }
 
+inline ByteArray* Method::GetRegisterMapData() const {
+  return GetFieldObject<ByteArray*>(
+      OFFSET_OF_OBJECT_MEMBER(Method, register_map_data_), false);
+}
+
+inline void Method::SetRegisterMapData(ByteArray* new_data) {
+  SetFieldObject(OFFSET_OF_OBJECT_MEMBER(Method, register_map_data_),
+                 new_data, false);
+}
+
+inline ByteArray* Method::GetRegisterMapHeader() const {
+  return GetFieldObject<ByteArray*>(
+      OFFSET_OF_OBJECT_MEMBER(Method, register_map_header_), false);
+}
+
+inline void Method::SetRegisterMapHeader(ByteArray* new_header) {
+  SetFieldObject(OFFSET_OF_OBJECT_MEMBER(Method, register_map_header_),
+                 new_header, false);
+}
+
 inline String* Method::GetShorty() const {
   DCHECK(GetDeclaringClass()->IsLoaded());
   return GetFieldObject<String*>(