diff --git a/build/Android.common.mk b/build/Android.common.mk
index a8d313a..c5e45e3 100644
--- a/build/Android.common.mk
+++ b/build/Android.common.mk
@@ -260,7 +260,7 @@
 	src/utils.cc \
 	src/well_known_classes.cc \
 	src/zip_archive.cc \
-	src/verifier/gc_map.cc \
+	src/verifier/dex_gc_map.cc \
 	src/verifier/method_verifier.cc \
 	src/verifier/reg_type.cc \
 	src/verifier/reg_type_cache.cc \
diff --git a/src/class_linker.cc b/src/class_linker.cc
index 32e6c39..f9fbc58 100644
--- a/src/class_linker.cc
+++ b/src/class_linker.cc
@@ -1987,30 +1987,6 @@
   }
 }
 
-#if !defined(NDEBUG) && !defined(ART_USE_LLVM_COMPILER)
-static void CheckMethodsHaveGcMaps(Class* klass)
-    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
-  if (!Runtime::Current()->IsStarted()) {
-    return;
-  }
-  for (size_t i = 0; i < klass->NumDirectMethods(); i++) {
-    Method* method = klass->GetDirectMethod(i);
-    if (!method->IsNative() && !method->IsAbstract()) {
-      CHECK(method->GetGcMap() != NULL) << PrettyMethod(method);
-    }
-  }
-  for (size_t i = 0; i < klass->NumVirtualMethods(); i++) {
-    Method* method = klass->GetVirtualMethod(i);
-    if (!method->IsNative() && !method->IsAbstract()) {
-      CHECK(method->GetGcMap() != NULL) << PrettyMethod(method);
-    }
-  }
-}
-#else
-static void CheckMethodsHaveGcMaps(Class*) {
-}
-#endif
-
 void ClassLinker::VerifyClass(Class* klass) {
   // TODO: assert that the monitor on the Class is held
   ObjectLock lock(klass);
@@ -2106,8 +2082,6 @@
         klass->SetStatus(Class::kStatusVerified);
       }
     }
-    // Sanity check that a verified class has GC maps on all methods.
-    CheckMethodsHaveGcMaps(klass);
   } else {
     LOG(ERROR) << "Verification failed on class " << PrettyDescriptor(klass)
         << " in " << klass->GetDexCache()->GetLocation()->ToModifiedUtf8()
diff --git a/src/class_linker_test.cc b/src/class_linker_test.cc
index f249c6a..a0b4f1c 100644
--- a/src/class_linker_test.cc
+++ b/src/class_linker_test.cc
@@ -468,7 +468,7 @@
     offsets.push_back(CheckOffset(OFFSETOF_MEMBER(Method, core_spill_mask_),     "coreSpillMask"));
     offsets.push_back(CheckOffset(OFFSETOF_MEMBER(Method, fp_spill_mask_),       "fpSpillMask"));
     offsets.push_back(CheckOffset(OFFSETOF_MEMBER(Method, frame_size_in_bytes_), "frameSizeInBytes"));
-    offsets.push_back(CheckOffset(OFFSETOF_MEMBER(Method, gc_map_),              "gcMap"));
+    offsets.push_back(CheckOffset(OFFSETOF_MEMBER(Method, native_gc_map_),       "gcMap"));
     offsets.push_back(CheckOffset(OFFSETOF_MEMBER(Method, invoke_stub_),         "invokeStub"));
     offsets.push_back(CheckOffset(OFFSETOF_MEMBER(Method, mapping_table_),       "mappingTable"));
     offsets.push_back(CheckOffset(OFFSETOF_MEMBER(Method, method_dex_index_),    "methodDexIndex"));
diff --git a/src/compiled_method.cc b/src/compiled_method.cc
index b0285fd..4de2a3f 100644
--- a/src/compiled_method.cc
+++ b/src/compiled_method.cc
@@ -78,9 +78,11 @@
                                const uint32_t core_spill_mask,
                                const uint32_t fp_spill_mask,
                                const std::vector<uint32_t>& mapping_table,
-                               const std::vector<uint16_t>& vmap_table)
+                               const std::vector<uint16_t>& vmap_table,
+                               const std::vector<uint8_t>& native_gc_map)
     : CompiledCode(instruction_set), frame_size_in_bytes_(frame_size_in_bytes),
-      core_spill_mask_(core_spill_mask), fp_spill_mask_(fp_spill_mask)
+      core_spill_mask_(core_spill_mask), fp_spill_mask_(fp_spill_mask),
+      native_gc_map_(native_gc_map)
 {
   CHECK_NE(code.size(), 0U);
   DCHECK_EQ(vmap_table.size(),
@@ -113,17 +115,6 @@
   DCHECK_EQ(vmap_table_[0], static_cast<uint32_t>(__builtin_popcount(core_spill_mask) + __builtin_popcount(fp_spill_mask)));
 }
 
-void CompiledMethod::SetGcMap(const std::vector<uint8_t>& gc_map) {
-  CHECK_NE(gc_map.size(), 0U);
-
-#if !defined(ART_USE_LLVM_COMPILER) && !defined(ART_USE_GREENLAND_COMPILER)
-  // Should only be used with CompiledMethods created with the non-LLVM compilers.
-  CHECK_NE(mapping_table_.size(), 0U);
-#endif
-
-  gc_map_ = gc_map;
-}
-
 CompiledMethod::CompiledMethod(InstructionSet instruction_set,
                                const std::vector<uint8_t>& code,
                                const size_t frame_size_in_bytes,
@@ -134,32 +125,6 @@
       core_spill_mask_(core_spill_mask), fp_spill_mask_(fp_spill_mask) {
 }
 
-CompiledMethod::~CompiledMethod() {}
-
-size_t CompiledMethod::GetFrameSizeInBytes() const {
-  return frame_size_in_bytes_;
-}
-
-uint32_t CompiledMethod::GetCoreSpillMask() const {
-  return core_spill_mask_;
-}
-
-uint32_t CompiledMethod::GetFpSpillMask() const {
-  return fp_spill_mask_;
-}
-
-const std::vector<uint32_t>& CompiledMethod::GetMappingTable() const {
-  return mapping_table_;
-}
-
-const std::vector<uint16_t>& CompiledMethod::GetVmapTable() const {
-  return vmap_table_;
-}
-
-const std::vector<uint8_t>& CompiledMethod::GetGcMap() const {
-  return gc_map_;
-}
-
 CompiledInvokeStub::CompiledInvokeStub(InstructionSet instruction_set)
     : CompiledCode(instruction_set) {
 }
@@ -169,6 +134,4 @@
     : CompiledCode(instruction_set, code) {
 }
 
-CompiledInvokeStub::~CompiledInvokeStub() {}
-
 }  // namespace art
diff --git a/src/compiled_method.h b/src/compiled_method.h
index ca3a597..901ec64 100644
--- a/src/compiled_method.h
+++ b/src/compiled_method.h
@@ -87,10 +87,8 @@
                  const uint32_t core_spill_mask,
                  const uint32_t fp_spill_mask,
                  const std::vector<uint32_t>& mapping_table,
-                 const std::vector<uint16_t>& vmap_table);
-
-  // Sets the GC map for a CompiledMethod.
-  void SetGcMap(const std::vector<uint8_t>& gc_map);
+                 const std::vector<uint16_t>& vmap_table,
+                 const std::vector<uint8_t>& native_gc_map);
 
   // Constructs a CompiledMethod for the JniCompiler.
   CompiledMethod(InstructionSet instruction_set,
@@ -107,28 +105,39 @@
         fp_spill_mask_(0) {
   }
 
-  ~CompiledMethod();
+  ~CompiledMethod() {}
 
-  size_t GetFrameSizeInBytes() const;
-  uint32_t GetCoreSpillMask() const;
-  uint32_t GetFpSpillMask() const;
-  const std::vector<uint32_t>& GetMappingTable() const;
-  const std::vector<uint16_t>& GetVmapTable() const;
-  const std::vector<uint8_t>& GetGcMap() const;
-
-#if defined(ART_USE_LLVM_COMPILER)
-  void SetFrameSizeInBytes(size_t new_frame_size_in_bytes) {
-    frame_size_in_bytes_ = new_frame_size_in_bytes;
+  size_t GetFrameSizeInBytes() const {
+    return frame_size_in_bytes_;
   }
-#endif
+
+  uint32_t GetCoreSpillMask() const {
+    return core_spill_mask_;
+  }
+
+  uint32_t GetFpSpillMask() const {
+    return fp_spill_mask_;
+  }
+
+  const std::vector<uint32_t>& GetMappingTable() const {
+    return mapping_table_;
+  }
+
+  const std::vector<uint16_t>& GetVmapTable() const {
+    return vmap_table_;
+  }
+
+  const std::vector<uint8_t>& GetNativeGcMap() const {
+    return native_gc_map_;
+  }
 
  private:
-  size_t frame_size_in_bytes_;
+  const size_t frame_size_in_bytes_;
   const uint32_t core_spill_mask_;
   const uint32_t fp_spill_mask_;
   std::vector<uint32_t> mapping_table_;
   std::vector<uint16_t> vmap_table_;
-  std::vector<uint8_t> gc_map_;
+  std::vector<uint8_t> native_gc_map_;
 };
 
 class CompiledInvokeStub : public CompiledCode {
@@ -138,7 +147,7 @@
   explicit CompiledInvokeStub(InstructionSet instruction_set,
                               const std::vector<uint8_t>& code);
 
-  ~CompiledInvokeStub();
+  ~CompiledInvokeStub() {}
 };
 
 }  // namespace art
diff --git a/src/compiler.cc b/src/compiler.cc
index b80b6a6..abbb939 100644
--- a/src/compiler.cc
+++ b/src/compiler.cc
@@ -554,8 +554,7 @@
   timings.AddSplit("PreCompile.InitializeClassesWithoutClinit");
 }
 
-void Compiler::PostCompile(jobject class_loader, const std::vector<const DexFile*>& dex_files) {
-  SetGcMaps(class_loader, dex_files);
+void Compiler::PostCompile(jobject, const std::vector<const DexFile*>&) {
 }
 
 bool Compiler::IsImageClass(const std::string& descriptor) const {
@@ -1703,72 +1702,6 @@
   return it->second;
 }
 
-void Compiler::SetGcMaps(jobject class_loader, const std::vector<const DexFile*>& dex_files) {
-  for (size_t i = 0; i != dex_files.size(); ++i) {
-    const DexFile* dex_file = dex_files[i];
-    CHECK(dex_file != NULL);
-    SetGcMapsDexFile(class_loader, *dex_file);
-  }
-}
-
-void Compiler::SetGcMapsDexFile(jobject jni_class_loader, const DexFile& dex_file) {
-  ScopedObjectAccess soa(Thread::Current());
-  ClassLoader* class_loader = soa.Decode<ClassLoader*>(jni_class_loader);
-  ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
-  DexCache* dex_cache = class_linker->FindDexCache(dex_file);
-  for (size_t class_def_index = 0; class_def_index < dex_file.NumClassDefs(); class_def_index++) {
-    const DexFile::ClassDef& class_def = dex_file.GetClassDef(class_def_index);
-    const char* descriptor = dex_file.GetClassDescriptor(class_def);
-    Class* klass = class_linker->FindClass(descriptor, class_loader);
-    if (klass == NULL || !klass->IsVerified()) {
-      Thread::Current()->ClearException();
-      continue;
-    }
-    const byte* class_data = dex_file.GetClassData(class_def);
-    if (class_data == NULL) {
-      // empty class such as a marker interface
-      continue;
-    }
-    ClassDataItemIterator it(dex_file, class_data);
-    while (it.HasNextStaticField()) {
-      it.Next();
-    }
-    while (it.HasNextInstanceField()) {
-      it.Next();
-    }
-    while (it.HasNextDirectMethod()) {
-      Method* method = class_linker->ResolveMethod(dex_file, it.GetMemberIndex(), dex_cache,
-                                                   class_loader, NULL, it.GetMethodInvokeType(class_def));
-      SetGcMapsMethod(dex_file, method);
-      it.Next();
-    }
-    while (it.HasNextVirtualMethod()) {
-      Method* method = class_linker->ResolveMethod(dex_file, it.GetMemberIndex(), dex_cache,
-                                                   class_loader, NULL, it.GetMethodInvokeType(class_def));
-      SetGcMapsMethod(dex_file, method);
-      it.Next();
-    }
-  }
-}
-
-void Compiler::SetGcMapsMethod(const DexFile& dex_file, Method* method) {
-  if (method == NULL) {
-    Thread::Current()->ClearException();
-    return;
-  }
-  uint16_t method_idx = method->GetDexMethodIndex();
-  MethodReference ref(&dex_file, method_idx);
-  CompiledMethod* compiled_method = GetCompiledMethod(ref);
-  if (compiled_method == NULL) {
-    return;
-  }
-  const std::vector<uint8_t>* gc_map = verifier::MethodVerifier::GetGcMap(ref);
-  if (gc_map == NULL) {
-    return;
-  }
-  compiled_method->SetGcMap(*gc_map);
-}
-
 #if defined(ART_USE_LLVM_COMPILER) || defined(ART_USE_QUICK_COMPILER)
 void Compiler::SetBitcodeFileName(std::string const& filename) {
   typedef void (*SetBitcodeFileNameFn)(Compiler&, std::string const&);
diff --git a/src/compiler.h b/src/compiler.h
index 3376bc2..759fcd3 100644
--- a/src/compiler.h
+++ b/src/compiler.h
@@ -271,13 +271,6 @@
   static void CompileClass(const CompilationContext* context, size_t class_def_index)
       LOCKS_EXCLUDED(Locks::mutator_lock_);
 
-  void SetGcMaps(jobject class_loader, const std::vector<const DexFile*>& dex_files)
-      LOCKS_EXCLUDED(Locks::mutator_lock_);
-  void SetGcMapsDexFile(jobject class_loader, const DexFile& dex_file)
-      LOCKS_EXCLUDED(Locks::mutator_lock_);
-  void SetGcMapsMethod(const DexFile& dex_file, Method* method)
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
-
   void InsertInvokeStub(const std::string& key, const CompiledInvokeStub* compiled_invoke_stub)
       LOCKS_EXCLUDED(compiled_invoke_stubs_lock_);
 
diff --git a/src/compiler/CompilerIR.h b/src/compiler/CompilerIR.h
index f7b1bc6..c5bbae6 100644
--- a/src/compiler/CompilerIR.h
+++ b/src/compiler/CompilerIR.h
@@ -472,6 +472,7 @@
   std::vector<uint32_t> mappingTable;
   std::vector<uint32_t> coreVmapTable;
   std::vector<uint32_t> fpVmapTable;
+  std::vector<uint8_t> nativeGcMap;
   bool genDebugger;                   // Generate code for debugger
   bool printMe;
   bool hasClassLiterals;              // Contains class ptrs used as literals
diff --git a/src/compiler/Frontend.cc b/src/compiler/Frontend.cc
index ca6ccca..1a09427 100644
--- a/src/compiler/Frontend.cc
+++ b/src/compiler/Frontend.cc
@@ -1217,7 +1217,8 @@
   CompiledMethod* result =
       new CompiledMethod(cUnit->instructionSet, cUnit->codeBuffer,
                          cUnit->frameSize, cUnit->coreSpillMask,
-                         cUnit->fpSpillMask, cUnit->mappingTable, vmapTable);
+                         cUnit->fpSpillMask, cUnit->mappingTable, vmapTable,
+                         cUnit->nativeGcMap);
 
   VLOG(compiler) << "Compiled " << PrettyMethod(method_idx, dex_file)
      << " (" << (cUnit->codeBuffer.size() * sizeof(cUnit->codeBuffer[0]))
diff --git a/src/compiler/codegen/CodegenUtil.cc b/src/compiler/codegen/CodegenUtil.cc
index dff30be..ca0a933 100644
--- a/src/compiler/codegen/CodegenUtil.cc
+++ b/src/compiler/codegen/CodegenUtil.cc
@@ -14,6 +14,10 @@
  * limitations under the License.
  */
 
+#include "gc_map.h"
+#include "verifier/dex_gc_map.h"
+#include "verifier/method_verifier.h"
+
 namespace art {
 
 void setMemRefType(LIR* lir, bool isLoad, int memType)
@@ -768,6 +772,114 @@
   }
 }
 
+class NativePcToReferenceMapBuilder {
+ public:
+  NativePcToReferenceMapBuilder(std::vector<uint8_t>* table,
+                                size_t entries, uint32_t max_native_offset,
+                                size_t references_width) : entries_(entries),
+                                references_width_(references_width), in_use_(entries),
+                                table_(table) {
+    // Compute width in bytes needed to hold max_native_offset.
+    native_offset_width_ = 0;
+    while (max_native_offset != 0) {
+      native_offset_width_++;
+      max_native_offset >>= 8;
+    }
+    // Resize table and set up header.
+    table->resize((EntryWidth() * entries) + sizeof(uint32_t));
+    CHECK_LT(native_offset_width_, 1U << 8);
+    (*table)[0] = native_offset_width_;
+    CHECK_LT(references_width_, 1U << 8);
+    (*table)[1] = references_width_;
+    CHECK_LT(entries, 1U << 16);
+    (*table)[2] = entries & 0xFF;
+    (*table)[3] = (entries >> 8) & 0xFF;
+  }
+
+  void AddEntry(uint32_t native_offset, const uint8_t* references) {
+    size_t table_index = TableIndex(native_offset);
+    while (in_use_[table_index]) {
+      table_index = (table_index + 1) % entries_;
+    }
+    in_use_[table_index] = true;
+    SetNativeOffset(table_index, native_offset);
+    DCHECK_EQ(native_offset, GetNativeOffset(table_index));
+    SetReferences(table_index, references);
+  }
+
+ private:
+  size_t TableIndex(uint32_t native_offset) {
+    return NativePcOffsetToReferenceMap::Hash(native_offset) % entries_;
+  }
+
+  uint32_t GetNativeOffset(size_t table_index) {
+    uint32_t native_offset = 0;
+    size_t table_offset = (table_index * EntryWidth()) + sizeof(uint32_t);
+    for (size_t i = 0; i < native_offset_width_; i++) {
+      native_offset |= (*table_)[table_offset + i] << (i * 8);
+    }
+    return native_offset;
+  }
+
+  void SetNativeOffset(size_t table_index, uint32_t native_offset) {
+    size_t table_offset = (table_index * EntryWidth()) + sizeof(uint32_t);
+    for (size_t i = 0; i < native_offset_width_; i++) {
+      (*table_)[table_offset + i] = (native_offset >> (i * 8)) & 0xFF;
+    }
+  }
+
+  void SetReferences(size_t table_index, const uint8_t* references) {
+    size_t table_offset = (table_index * EntryWidth()) + sizeof(uint32_t);
+    memcpy(&(*table_)[table_offset + native_offset_width_], references, references_width_);
+  }
+
+  size_t EntryWidth() const {
+    return native_offset_width_ + references_width_;
+  }
+
+  // Number of entries in the table.
+  const size_t entries_;
+  // Number of bytes used to encode the reference bitmap.
+  const size_t references_width_;
+  // Number of bytes used to encode a native offset.
+  size_t native_offset_width_;
+  // Entries that are in use.
+  std::vector<bool> in_use_;
+  // The table we're building.
+  std::vector<uint8_t>* const table_;
+};
+
+static void createNativeGcMap(CompilationUnit* cUnit) {
+  const std::vector<uint32_t>& mapping_table = cUnit->mappingTable;
+  uint32_t max_native_offset = 0;
+  for (size_t i = 0; i < mapping_table.size(); i += 2) {
+    uint32_t native_offset = mapping_table[i + 0];
+    if (native_offset > max_native_offset) {
+      max_native_offset = native_offset;
+    }
+  }
+  Compiler::MethodReference method_ref(cUnit->dex_file, cUnit->method_idx);
+  const std::vector<uint8_t>* gc_map_raw = verifier::MethodVerifier::GetDexGcMap(method_ref);
+  verifier::DexPcToReferenceMap dex_gc_map(&(*gc_map_raw)[4], gc_map_raw->size() - 4);
+  // Compute native offset to references size.
+  NativePcToReferenceMapBuilder native_gc_map_builder(&cUnit->nativeGcMap,
+                                                      mapping_table.size() / 2, max_native_offset,
+                                                      dex_gc_map.RegWidth());
+
+  for (size_t i = 0; i < mapping_table.size(); i += 2) {
+    uint32_t native_offset = mapping_table[i + 0];
+    uint32_t dex_pc = mapping_table[i + 1];
+    const uint8_t* references = dex_gc_map.FindBitMap(dex_pc, false);
+    if (references != NULL) {
+      native_gc_map_builder.AddEntry(native_offset, references);
+    } else {
+      // TODO: there is a mapping table entry but no reference bitmap. This happens because of
+      //       catch block entries. We should check that the dex_pc corresponds with a catch block
+      //       here.
+    }
+  }
+}
+
 /* Determine the offset of each literal field */
 int assignLiteralOffset(CompilationUnit* cUnit, int offset)
 {
@@ -874,10 +986,10 @@
   // Install fill array data
   installFillArrayData(cUnit);
 
-  /*
-   * Create the mapping table
-   */
+  // Create the mapping table and native offset to reference map.
   createMappingTable(cUnit);
+
+  createNativeGcMap(cUnit);
 }
 
 /*
diff --git a/src/exception_test.cc b/src/exception_test.cc
index bd792f7..6a58210 100644
--- a/src/exception_test.cc
+++ b/src/exception_test.cc
@@ -136,7 +136,7 @@
   fake_stack.push_back(reinterpret_cast<uintptr_t>(method_g_));
   fake_stack.push_back(0);
   fake_stack.push_back(0);
-  fake_stack.push_back(method_f_->ToNativePC(dex_pc));  // return pc
+  fake_stack.push_back(method_f_->ToNativePc(dex_pc));  // return pc
 
   // Create/push fake 16byte stack frame for method f
   fake_stack.push_back(reinterpret_cast<uintptr_t>(method_f_));
@@ -153,7 +153,7 @@
   fake_stack.push_back(0);
 
   // Set up thread to appear as if we called out of method_g_ at pc dex 3
-  thread->SetTopOfStack(&fake_stack[0], method_g_->ToNativePC(dex_pc));  // return pc
+  thread->SetTopOfStack(&fake_stack[0], method_g_->ToNativePc(dex_pc));  // return pc
 #else
   // Create/push fake 20-byte shadow frame for method g
   fake_stack.push_back(0);
diff --git a/src/gc_map.h b/src/gc_map.h
new file mode 100644
index 0000000..50e63d6
--- /dev/null
+++ b/src/gc_map.h
@@ -0,0 +1,97 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_SRC_GC_MAP_H_
+#define ART_SRC_GC_MAP_H_
+
+#include "logging.h"
+#include "macros.h"
+#include <stdint.h>
+
+namespace art {
+
+// Lightweight wrapper for native PC offset to reference bit maps.
+class NativePcOffsetToReferenceMap {
+ public:
+  NativePcOffsetToReferenceMap(const uint8_t* data) : data_(data) {
+    CHECK(data_ != NULL);
+  }
+
+  // The number of entries in the table.
+  size_t NumEntries() const {
+    return data_[2] | (data_[3] << 8);
+  }
+
+  // Return address of bitmap encoding what are live references.
+  const uint8_t* GetBitMap(size_t index) const {
+    size_t entry_offset = index * EntryWidth();
+    return &Table()[entry_offset + NativeOffsetWidth()];
+  }
+
+  // Get the native PC encoded in the table at the given index.
+  uintptr_t GetNativePcOffset(size_t index) const {
+    size_t entry_offset = index * EntryWidth();
+    uintptr_t result = 0;
+    for (size_t i = 0; i < NativeOffsetWidth(); ++i) {
+      result |= Table()[entry_offset + i] << (i * 8);
+    }
+    return result;
+  }
+
+  // Finds the bitmap associated with the native pc offset.
+  const uint8_t* FindBitMap(uintptr_t native_pc_offset) {
+    size_t num_entries = NumEntries();
+    size_t index = Hash(native_pc_offset) % num_entries;
+    while (GetNativePcOffset(index) != native_pc_offset) {
+      index = (index + 1) % num_entries;
+    }
+    return GetBitMap(index);
+  }
+
+  static uint32_t Hash(uint32_t native_offset) {
+    uint32_t hash = native_offset;
+    hash ^= (hash >> 20) ^ (hash >> 12);
+    hash ^= (hash >> 7) ^ (hash >> 4);
+    return hash;
+  }
+
+  // The number of bytes used to encode registers.
+  size_t RegWidth() const {
+    return data_[1];
+  }
+
+ private:
+  // Skip the size information at the beginning of data.
+  const uint8_t* Table() const {
+    return data_ + 4;
+  }
+
+  // Number of bytes used to encode a native offset.
+  size_t NativeOffsetWidth() const {
+    return data_[0];
+  }
+
+  // The width of an entry in the table.
+  size_t EntryWidth() const {
+    return NativeOffsetWidth() + RegWidth();
+  }
+
+  const uint8_t* const data_;  // The header and table data
+};
+
+}  // namespace art
+
+#endif  // ART_SRC_GC_MAP_H_
diff --git a/src/image_writer.cc b/src/image_writer.cc
index d91fc59..4eec311 100644
--- a/src/image_writer.cc
+++ b/src/image_writer.cc
@@ -534,9 +534,9 @@
     const byte* vmap_table = GetOatAddress(vmap_table_offset);
     copy->vmap_table_ = reinterpret_cast<const uint16_t*>(vmap_table);
 
-    uint32_t gc_map_offset = orig->GetOatGcMapOffset();
-    const byte* gc_map = GetOatAddress(gc_map_offset);
-    copy->gc_map_ = reinterpret_cast<const uint8_t*>(gc_map);
+    uint32_t native_gc_map_offset = orig->GetOatNativeGcMapOffset();
+    const byte* native_gc_map = GetOatAddress(native_gc_map_offset);
+    copy->native_gc_map_ = reinterpret_cast<const uint8_t*>(native_gc_map);
   }
 }
 
diff --git a/src/oat/runtime/support_jni.cc b/src/oat/runtime/support_jni.cc
index 49365b5..2c6f766 100644
--- a/src/oat/runtime/support_jni.cc
+++ b/src/oat/runtime/support_jni.cc
@@ -179,7 +179,7 @@
     }
   }
   // Load expected destination, see Method::RegisterNative
-  const void* code = reinterpret_cast<const void*>(jni_method->GetGcMapRaw());
+  const void* code = reinterpret_cast<const void*>(jni_method->GetNativeGcMap());
   if (UNLIKELY(code == NULL)) {
     code = Runtime::Current()->GetJniDlsymLookupStub()->GetData();
     jni_method->RegisterNative(self, code);
diff --git a/src/oat/runtime/support_stubs.cc b/src/oat/runtime/support_stubs.cc
index 138f722..5df7da3 100644
--- a/src/oat/runtime/support_stubs.cc
+++ b/src/oat/runtime/support_stubs.cc
@@ -97,7 +97,7 @@
 #endif
   if (type == Runtime::kUnknownMethod) {
     DCHECK(called->IsRuntimeMethod());
-    uint32_t dex_pc = caller->ToDexPC(caller_pc);
+    uint32_t dex_pc = caller->ToDexPc(caller_pc);
     const DexFile::CodeItem* code = MethodHelper(caller).GetCodeItem();
     CHECK_LT(dex_pc, code->insns_size_in_code_units_);
     const Instruction* instr = Instruction::At(&code->insns_[dex_pc]);
diff --git a/src/oat_file.cc b/src/oat_file.cc
index 264405d..2a21baa 100644
--- a/src/oat_file.cc
+++ b/src/oat_file.cc
@@ -297,7 +297,7 @@
     fp_spill_mask_(fp_spill_mask),
     mapping_table_offset_(mapping_table_offset),
     vmap_table_offset_(vmap_table_offset),
-    gc_map_offset_(gc_map_offset),
+    native_gc_map_offset_(gc_map_offset),
     invoke_stub_offset_(invoke_stub_offset)
 #if defined(ART_USE_LLVM_COMPILER)
   , proxy_stub_offset_(proxy_stub_offset)
@@ -363,7 +363,7 @@
   method->SetFpSpillMask(fp_spill_mask_);
   method->SetMappingTable(GetMappingTable());
   method->SetVmapTable(GetVmapTable());
-  method->SetGcMap(GetGcMap());  // Note, used by native methods in work around JNI mode.
+  method->SetNativeGcMap(GetNativeGcMap());  // Note, used by native methods in work around JNI mode.
   method->SetInvokeStub(GetInvokeStub());
 }
 
@@ -375,7 +375,7 @@
   method->SetFpSpillMask(GetFpSpillMask());
   method->SetOatMappingTableOffset(GetMappingTableOffset());
   method->SetOatVmapTableOffset(GetVmapTableOffset());
-  method->SetOatGcMapOffset(GetGcMapOffset());
+  method->SetOatNativeGcMapOffset(GetNativeGcMapOffset());
   method->SetOatInvokeStubOffset(GetInvokeStubOffset());
 }
 
diff --git a/src/oat_file.h b/src/oat_file.h
index 24b6b40..91df927 100644
--- a/src/oat_file.h
+++ b/src/oat_file.h
@@ -88,8 +88,8 @@
     uint32_t GetVmapTableOffset() const {
       return vmap_table_offset_;
     }
-    uint32_t GetGcMapOffset() const {
-      return gc_map_offset_;
+    uint32_t GetNativeGcMapOffset() const {
+      return native_gc_map_offset_;
     }
     uint32_t GetInvokeStubOffset() const {
       return invoke_stub_offset_;
@@ -104,8 +104,8 @@
     const uint16_t* GetVmapTable() const {
       return GetOatPointer<const uint16_t*>(vmap_table_offset_);
     }
-    const uint8_t* GetGcMap() const {
-      return GetOatPointer<const uint8_t*>(gc_map_offset_);
+    const uint8_t* GetNativeGcMap() const {
+      return GetOatPointer<const uint8_t*>(native_gc_map_offset_);
     }
 
     Method::InvokeStub* GetInvokeStub() const;
@@ -149,7 +149,7 @@
     uint32_t fp_spill_mask_;
     uint32_t mapping_table_offset_;
     uint32_t vmap_table_offset_;
-    uint32_t gc_map_offset_;
+    uint32_t native_gc_map_offset_;
     uint32_t invoke_stub_offset_;
 
 #if defined(ART_USE_LLVM_COMPILER)
diff --git a/src/oat_writer.cc b/src/oat_writer.cc
index a7951f3..2eb80ec 100644
--- a/src/oat_writer.cc
+++ b/src/oat_writer.cc
@@ -297,7 +297,7 @@
       oat_header_->UpdateChecksum(&vmap_table[0], vmap_table_size);
     }
 
-    const std::vector<uint8_t>& gc_map = compiled_method->GetGcMap();
+    const std::vector<uint8_t>& gc_map = compiled_method->GetNativeGcMap();
     size_t gc_map_size = gc_map.size() * sizeof(gc_map[0]);
     gc_map_offset = (gc_map_size == 0) ? 0 : offset;
 
@@ -412,7 +412,7 @@
       method->SetCode(Runtime::Current()->GetResolutionStubArray(Runtime::kStaticMethod)->GetData());
     }
     method->SetOatVmapTableOffset(vmap_table_offset);
-    method->SetOatGcMapOffset(gc_map_offset);
+    method->SetOatNativeGcMapOffset(gc_map_offset);
     method->SetOatInvokeStubOffset(invoke_stub_offset);
   }
 
@@ -665,7 +665,7 @@
     }
     DCHECK_CODE_OFFSET();
 
-    const std::vector<uint8_t>& gc_map = compiled_method->GetGcMap();
+    const std::vector<uint8_t>& gc_map = compiled_method->GetNativeGcMap();
     size_t gc_map_size = gc_map.size() * sizeof(gc_map[0]);
 
     // Deduplicate GC maps
diff --git a/src/oatdump.cc b/src/oatdump.cc
index 54183bb..ee85782 100644
--- a/src/oatdump.cc
+++ b/src/oatdump.cc
@@ -35,7 +35,7 @@
 #include "scoped_thread_state_change.h"
 #include "space.h"
 #include "stringpiece.h"
-#include "verifier/gc_map.h"
+#include "gc_map.h"
 
 namespace art {
 
@@ -224,7 +224,7 @@
     offsets_.insert(code_offset);
     offsets_.insert(oat_method.GetMappingTableOffset());
     offsets_.insert(oat_method.GetVmapTableOffset());
-    offsets_.insert(oat_method.GetGcMapOffset());
+    offsets_.insert(oat_method.GetNativeGcMapOffset());
     offsets_.insert(oat_method.GetInvokeStubOffset());
   }
 
@@ -309,8 +309,8 @@
     DumpVmap(os, oat_method.GetVmapTable(), oat_method.GetCoreSpillMask(),
              oat_method.GetFpSpillMask());
     os << StringPrintf("\t\tgc_map: %p (offset=0x%08x)\n",
-                       oat_method.GetGcMap(), oat_method.GetGcMapOffset());
-    DumpGcMap(os, oat_method.GetGcMap());
+                       oat_method.GetNativeGcMap(), oat_method.GetNativeGcMapOffset());
+    DumpGcMap(os, oat_method.GetNativeGcMap());
     os << StringPrintf("\t\tCODE: %p (offset=0x%08x size=%d)%s\n",
                        oat_method.GetCode(),
                        oat_method.GetCodeOffset(),
@@ -392,11 +392,9 @@
     if (gc_map_raw == NULL) {
       return;
     }
-    uint32_t gc_map_length = (gc_map_raw[0] << 24) | (gc_map_raw[1] << 16) |
-                             (gc_map_raw[2] << 8) | (gc_map_raw[3] << 0);
-    verifier::DexPcToReferenceMap map(gc_map_raw + sizeof(uint32_t), gc_map_length);
+    NativePcOffsetToReferenceMap map(gc_map_raw);
     for (size_t entry = 0; entry < map.NumEntries(); entry++) {
-      os << StringPrintf("\t\t\t0x%04x", map.GetDexPc(entry));
+      os << StringPrintf("\t\t\t0x%04x", map.GetNativePcOffset(entry));
       size_t num_regs = map.RegWidth() * 8;
       const uint8_t* reg_bitmap = map.GetBitMap(entry);
       bool first = true;
@@ -770,8 +768,7 @@
     } else if (obj->IsMethod()) {
       Method* method = obj->AsMethod();
       if (method->IsNative()) {
-        DCHECK(method->GetGcMap() == NULL) << PrettyMethod(method);
-        DCHECK_EQ(0U, method->GetGcMapLength()) << PrettyMethod(method);
+        DCHECK(method->GetNativeGcMap() == NULL) << PrettyMethod(method);
         DCHECK(method->GetMappingTable() == NULL) << PrettyMethod(method);
         bool first_occurrence;
         size_t invoke_stub_size = state->ComputeOatSize(
@@ -790,13 +787,11 @@
         }
       } else if (method->IsAbstract() || method->IsCalleeSaveMethod() ||
           method->IsResolutionMethod()) {
-        DCHECK(method->GetGcMap() == NULL) << PrettyMethod(method);
-        DCHECK_EQ(0U, method->GetGcMapLength()) << PrettyMethod(method);
+        DCHECK(method->GetNativeGcMap() == NULL) << PrettyMethod(method);
         DCHECK(method->GetMappingTable() == NULL) << PrettyMethod(method);
       } else {
 #if !defined(ART_USE_LLVM_COMPILER)
-        DCHECK(method->GetGcMap() != NULL) << PrettyMethod(method);
-        DCHECK_NE(0U, method->GetGcMapLength()) << PrettyMethod(method);
+        DCHECK(method->GetNativeGcMap() != NULL) << PrettyMethod(method);
 #endif
 
         const DexFile::CodeItem* code_item = MethodHelper(method).GetCodeItem();
@@ -804,7 +799,7 @@
         state->stats_.dex_instruction_bytes += dex_instruction_bytes;
 
         bool first_occurrence;
-        size_t gc_map_bytes = state->ComputeOatSize(method->GetGcMapRaw(), &first_occurrence);
+        size_t gc_map_bytes = state->ComputeOatSize(method->GetNativeGcMap(), &first_occurrence);
         if (first_occurrence) {
           state->stats_.gc_map_bytes += gc_map_bytes;
         }
diff --git a/src/object.cc b/src/object.cc
index bac3ec1..f2043b1 100644
--- a/src/object.cc
+++ b/src/object.cc
@@ -450,8 +450,7 @@
   return result;
 }
 
-static const void* GetOatCode(const Method* m)
-    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+static const void* GetOatCode(const Method* m) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
   Runtime* runtime = Runtime::Current();
   const void* code = m->GetCode();
   // Peel off any method tracing trampoline.
@@ -465,7 +464,11 @@
   return code;
 }
 
-uint32_t Method::ToDexPC(const uintptr_t pc) const {
+uintptr_t Method::NativePcOffset(const uintptr_t pc) const {
+  return pc - reinterpret_cast<uintptr_t>(GetOatCode(this));
+}
+
+uint32_t Method::ToDexPc(const uintptr_t pc) const {
 #if !defined(ART_USE_LLVM_COMPILER)
   const uint32_t* mapping_table = GetMappingTable();
   if (mapping_table == NULL) {
@@ -488,7 +491,7 @@
 #endif
 }
 
-uintptr_t Method::ToNativePC(const uint32_t dex_pc) const {
+uintptr_t Method::ToNativePc(const uint32_t dex_pc) const {
   const uint32_t* mapping_table = GetMappingTable();
   if (mapping_table == NULL) {
     DCHECK_EQ(dex_pc, 0U);
@@ -600,7 +603,7 @@
 #else
     UNIMPLEMENTED(FATAL);
 #endif
-    SetFieldPtr<const uint8_t*>(OFFSET_OF_OBJECT_MEMBER(Method, gc_map_),
+    SetFieldPtr<const uint8_t*>(OFFSET_OF_OBJECT_MEMBER(Method, native_gc_map_),
         reinterpret_cast<const uint8_t*>(native_method), false);
   }
 #endif
diff --git a/src/object.h b/src/object.h
index 03aadda..5d19ffc 100644
--- a/src/object.h
+++ b/src/object.h
@@ -761,39 +761,22 @@
     SetVmapTable(reinterpret_cast<uint16_t*>(vmap_table_offset));
   }
 
-  const uint8_t* GetGcMap() const {
-    const uint8_t* gc_map_raw = GetGcMapRaw();
-    if (gc_map_raw == NULL) {
-      return gc_map_raw;
-    }
-    return gc_map_raw + sizeof(uint32_t);
+  const uint8_t* GetNativeGcMap() const {
+    return GetFieldPtr<uint8_t*>(OFFSET_OF_OBJECT_MEMBER(Method, native_gc_map_), false);
+  }
+  void SetNativeGcMap(const uint8_t* data) {
+    SetFieldPtr<const uint8_t*>(OFFSET_OF_OBJECT_MEMBER(Method, native_gc_map_), data, false);
   }
 
-  uint32_t GetGcMapLength() const {
-    const uint8_t* gc_map_raw = GetGcMapRaw();
-    if (gc_map_raw == NULL) {
-      return 0;
-    }
-    return static_cast<uint32_t>((gc_map_raw[0] << 24) |
-                                 (gc_map_raw[1] << 16) |
-                                 (gc_map_raw[2] << 8) |
-                                 (gc_map_raw[3] << 0));
-  }
-
-  const uint8_t* GetGcMapRaw() const {
-    return GetFieldPtr<uint8_t*>(OFFSET_OF_OBJECT_MEMBER(Method, gc_map_), false);
-  }
-  void SetGcMap(const uint8_t* data) {
-    SetFieldPtr<const uint8_t*>(OFFSET_OF_OBJECT_MEMBER(Method, gc_map_), data, false);
-  }
-
-  uint32_t GetOatGcMapOffset() const {
+  // When building the oat need a convenient place to stuff the offset of the native GC map.
+  void SetOatNativeGcMapOffset(uint32_t gc_map_offset) {
     DCHECK(!Runtime::Current()->IsStarted());
-    return reinterpret_cast<uint32_t>(GetGcMapRaw());
+    SetNativeGcMap(reinterpret_cast<uint8_t*>(gc_map_offset));
   }
-  void SetOatGcMapOffset(uint32_t gc_map_offset) {
+
+  uint32_t GetOatNativeGcMapOffset() const {
     DCHECK(!Runtime::Current()->IsStarted());
-    SetGcMap(reinterpret_cast<uint8_t*>(gc_map_offset));
+    return reinterpret_cast<uint32_t>(GetNativeGcMap());
   }
 
   size_t GetFrameSizeInBytes() const {
@@ -916,15 +899,13 @@
     return result;
   }
 
-  // Converts a native PC to a dex PC.  TODO: this is a no-op
-  // until we associate a PC mapping table with each method.
-  uint32_t ToDexPC(const uintptr_t pc) const
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  uintptr_t NativePcOffset(const uintptr_t pc) const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
-  // Converts a dex PC to a native PC.  TODO: this is a no-op
-  // until we associate a PC mapping table with each method.
-  uintptr_t ToNativePC(const uint32_t dex_pc) const
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  // Converts a native PC to a dex PC.
+  uint32_t ToDexPc(const uintptr_t pc) const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
+  // Converts a dex PC to a native PC.
+  uintptr_t ToNativePc(const uint32_t dex_pc) const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
   // Find the catch block for the given exception type and dex_pc
   uint32_t FindCatchBlock(Class* exception_type, uint32_t dex_pc) const
@@ -978,8 +959,8 @@
   // Total size in bytes of the frame
   size_t frame_size_in_bytes_;
 
-  // Garbage collection map
-  const uint8_t* gc_map_;
+  // Garbage collection map of native PC offsets to reference bitmaps.
+  const uint8_t* native_gc_map_;
 
   // Native invocation stub entry point for calling from native to managed code.
   InvokeStub* invoke_stub_;
diff --git a/src/stack.cc b/src/stack.cc
index 2b2530b..c13aaf4 100644
--- a/src/stack.cc
+++ b/src/stack.cc
@@ -68,12 +68,18 @@
   if (cur_shadow_frame_ != NULL) {
     return cur_shadow_frame_->GetDexPC();
   } else if (cur_quick_frame_ != NULL) {
-    return GetMethod()->ToDexPC(cur_quick_frame_pc_);
+    return GetMethod()->ToDexPc(cur_quick_frame_pc_);
   } else {
     return 0;
   }
 }
 
+size_t StackVisitor::GetNativePcOffset() const {
+  DCHECK(!IsShadowFrame());
+  return GetMethod()->NativePcOffset(cur_quick_frame_pc_);
+}
+
+
 uint32_t StackVisitor::GetVReg(Method* m, int vreg) const {
   if (cur_quick_frame_ != NULL) {
     DCHECK(context_ != NULL); // You can't reliably read registers without a context.
diff --git a/src/stack.h b/src/stack.h
index 91b0cf1..21b05c4 100644
--- a/src/stack.h
+++ b/src/stack.h
@@ -243,6 +243,10 @@
     return cur_shadow_frame_ != NULL;
   }
 
+  uint32_t GetDexPc() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
+  size_t GetNativePcOffset() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
   uintptr_t LoadCalleeSave(int num, size_t frame_size) const {
     // Callee saves are held at the top of the frame
     Method* method = GetMethod();
@@ -255,8 +259,6 @@
     return *reinterpret_cast<uintptr_t*>(save_addr);
   }
 
-  uint32_t GetDexPc() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
-
   // Returns the height of the stack in the managed stack frames, including transitions.
   size_t GetFrameHeight() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
     return GetNumFrames() - cur_depth_;
@@ -274,8 +276,7 @@
     return num_frames_;
   }
 
-  uint32_t GetVReg(Method* m, int vreg) const
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  uint32_t GetVReg(Method* m, int vreg) const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
   void SetVReg(Method* m, int vreg, uint32_t new_value)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
diff --git a/src/thread.cc b/src/thread.cc
index 935b05c..eaa6683 100644
--- a/src/thread.cc
+++ b/src/thread.cc
@@ -31,6 +31,7 @@
 #include "class_linker.h"
 #include "class_loader.h"
 #include "debugger.h"
+#include "gc_map.h"
 #include "heap.h"
 #include "jni_internal.h"
 #include "monitor.h"
@@ -47,7 +48,6 @@
 #include "stack_indirect_reference_table.h"
 #include "thread_list.h"
 #include "utils.h"
-#include "verifier/gc_map.h"
 #include "well_known_classes.h"
 
 namespace art {
@@ -1558,7 +1558,7 @@
         // Unwind stack when an exception occurs during method tracing
         if (UNLIKELY(method_tracing_active_ && IsTraceExitPc(GetCurrentQuickFramePc()))) {
           uintptr_t pc = TraceMethodUnwindFromCode(Thread::Current());
-          dex_pc = method->ToDexPC(pc);
+          dex_pc = method->ToDexPc(pc);
         } else {
           dex_pc = GetDexPc();
         }
@@ -1568,7 +1568,7 @@
       uint32_t found_dex_pc = method->FindCatchBlock(to_find_, dex_pc);
       if (found_dex_pc != DexFile::kDexNoIndex) {
         handler_dex_pc_ = found_dex_pc;
-        handler_quick_frame_pc_ = method->ToNativePC(found_dex_pc);
+        handler_quick_frame_pc_ = method->ToNativePc(found_dex_pc);
         handler_quick_frame_ = GetCurrentQuickFrame();
         return false;  // End stack walk.
       }
@@ -1712,49 +1712,50 @@
       Method* m = GetMethod();
       // Process register map (which native and runtime methods don't have)
       if (!m->IsNative() && !m->IsRuntimeMethod() && !m->IsProxyMethod()) {
-        const uint8_t* gc_map = m->GetGcMap();
-        CHECK(gc_map != NULL) << PrettyMethod(m);
-        uint32_t gc_map_length = m->GetGcMapLength();
-        CHECK_NE(0U, gc_map_length) << PrettyMethod(m);
-        verifier::DexPcToReferenceMap map(gc_map, gc_map_length);
-        const uint8_t* reg_bitmap = map.FindBitMap(GetDexPc());
-        CHECK(reg_bitmap != NULL);
-        const VmapTable vmap_table(m->GetVmapTableRaw());
-        const DexFile::CodeItem* code_item = MethodHelper(m).GetCodeItem();
+        const uint8_t* native_gc_map = m->GetNativeGcMap();
+        CHECK(native_gc_map != NULL) << PrettyMethod(m);
+        mh_.ChangeMethod(m);
+        const DexFile::CodeItem* code_item = mh_.GetCodeItem();
         DCHECK(code_item != NULL) << PrettyMethod(m); // Can't be NULL or how would we compile its instructions?
-        uint32_t core_spills = m->GetCoreSpillMask();
-        uint32_t fp_spills = m->GetFpSpillMask();
-        size_t frame_size = m->GetFrameSizeInBytes();
-        // For all dex registers in the bitmap
+        NativePcOffsetToReferenceMap map(native_gc_map);
         size_t num_regs = std::min(map.RegWidth() * 8,
                                    static_cast<size_t>(code_item->registers_size_));
-        Method** cur_quick_frame = GetCurrentQuickFrame();
-        DCHECK(cur_quick_frame != NULL);
-        for (size_t reg = 0; reg < num_regs; ++reg) {
-          // Does this register hold a reference?
-          if (TestBitmap(reg, reg_bitmap)) {
-            uint32_t vmap_offset;
-            Object* ref;
-            if (vmap_table.IsInContext(reg, vmap_offset)) {
-              // Compute the register we need to load from the context
-              uint32_t spill_mask = core_spills;
-              CHECK_LT(vmap_offset, static_cast<uint32_t>(__builtin_popcount(spill_mask)));
-              uint32_t matches = 0;
-              uint32_t spill_shifts = 0;
-              while (matches != (vmap_offset + 1)) {
-                DCHECK_NE(spill_mask, 0u);
-                matches += spill_mask & 1;  // Add 1 if the low bit is set
-                spill_mask >>= 1;
-                spill_shifts++;
+        if (num_regs > 0) {
+          const uint8_t* reg_bitmap = map.FindBitMap(GetNativePcOffset());
+          DCHECK(reg_bitmap != NULL);
+          const VmapTable vmap_table(m->GetVmapTableRaw());
+          uint32_t core_spills = m->GetCoreSpillMask();
+          uint32_t fp_spills = m->GetFpSpillMask();
+          size_t frame_size = m->GetFrameSizeInBytes();
+          // For all dex registers in the bitmap
+          Method** cur_quick_frame = GetCurrentQuickFrame();
+          DCHECK(cur_quick_frame != NULL);
+          for (size_t reg = 0; reg < num_regs; ++reg) {
+            // Does this register hold a reference?
+            if (TestBitmap(reg, reg_bitmap)) {
+              uint32_t vmap_offset;
+              Object* ref;
+              if (vmap_table.IsInContext(reg, vmap_offset)) {
+                // Compute the register we need to load from the context
+                uint32_t spill_mask = core_spills;
+                CHECK_LT(vmap_offset, static_cast<uint32_t>(__builtin_popcount(spill_mask)));
+                uint32_t matches = 0;
+                uint32_t spill_shifts = 0;
+                while (matches != (vmap_offset + 1)) {
+                  DCHECK_NE(spill_mask, 0u);
+                  matches += spill_mask & 1;  // Add 1 if the low bit is set
+                  spill_mask >>= 1;
+                  spill_shifts++;
+                }
+                spill_shifts--;  // wind back one as we want the last match
+                ref = reinterpret_cast<Object*>(GetGPR(spill_shifts));
+              } else {
+                ref = reinterpret_cast<Object*>(GetVReg(cur_quick_frame, code_item, core_spills,
+                                                        fp_spills, frame_size, reg));
               }
-              spill_shifts--;  // wind back one as we want the last match
-              ref = reinterpret_cast<Object*>(GetGPR(spill_shifts));
-            } else {
-              ref = reinterpret_cast<Object*>(GetVReg(cur_quick_frame, code_item, core_spills,
-                                                      fp_spills, frame_size, reg));
-            }
-            if (ref != NULL) {
-              root_visitor_(ref, arg_);
+              if (ref != NULL) {
+                root_visitor_(ref, arg_);
+              }
             }
           }
         }
@@ -1768,10 +1769,12 @@
     return ((reg_vector[reg / 8] >> (reg % 8)) & 0x01) != 0;
   }
 
-  // Call-back when we visit a root
+  // Call-back when we visit a root.
   Heap::RootVisitor* root_visitor_;
-  // Argument to call-back
+  // Argument to call-back.
   void* arg_;
+  // A method helper we keep around to avoid dex file/cache re-computations.
+  MethodHelper mh_;
 };
 
 void Thread::VisitRoots(Heap::RootVisitor* visitor, void* arg) {
diff --git a/src/verifier/gc_map.cc b/src/verifier/dex_gc_map.cc
similarity index 97%
rename from src/verifier/gc_map.cc
rename to src/verifier/dex_gc_map.cc
index 66cb6c7..c1c9a29 100644
--- a/src/verifier/gc_map.cc
+++ b/src/verifier/dex_gc_map.cc
@@ -14,7 +14,7 @@
  * limitations under the License.
  */
 
-#include "gc_map.h"
+#include "verifier/dex_gc_map.h"
 
 #include "logging.h"
 
diff --git a/src/verifier/gc_map.h b/src/verifier/dex_gc_map.h
similarity index 88%
rename from src/verifier/gc_map.h
rename to src/verifier/dex_gc_map.h
index d6a1c46..d588cfd 100644
--- a/src/verifier/gc_map.h
+++ b/src/verifier/dex_gc_map.h
@@ -14,8 +14,8 @@
  * limitations under the License.
  */
 
-#ifndef ART_SRC_VERIFIER_GC_MAP_H_
-#define ART_SRC_VERIFIER_GC_MAP_H_
+#ifndef ART_SRC_VERIFIER_DEX_GC_MAP_H_
+#define ART_SRC_VERIFIER_DEX_GC_MAP_H_
 
 #include "logging.h"
 #include "macros.h"
@@ -37,8 +37,7 @@
 // Lightweight wrapper for Dex PC to reference bit maps.
 class DexPcToReferenceMap {
  public:
-  DexPcToReferenceMap(const uint8_t* data, size_t data_length) {
-    data_ = data;
+  DexPcToReferenceMap(const uint8_t* data, size_t data_length) : data_(data) {
     CHECK(data_ != NULL);
     // Check the size of the table agrees with the number of entries
     size_t data_size = data_length - 4;
@@ -53,7 +52,7 @@
   // Get the Dex PC at the given index
   uint16_t GetDexPc(size_t index) const {
     size_t entry_offset = index * EntryWidth();
-    if (PcWidth() == 1) {
+    if (DexPcWidth() == 1) {
       return Table()[entry_offset];
     } else {
       return Table()[entry_offset] | (Table()[entry_offset + 1] << 8);
@@ -63,7 +62,7 @@
   // Return address of bitmap encoding what are live references
   const uint8_t* GetBitMap(size_t index) const {
     size_t entry_offset = index * EntryWidth();
-    return &Table()[entry_offset + PcWidth()];
+    return &Table()[entry_offset + DexPcWidth()];
   }
 
   // Find the bitmap associated with the given dex pc
@@ -86,7 +85,7 @@
   }
 
   // Number of bytes used to encode a dex pc
-  size_t PcWidth() const {
+  size_t DexPcWidth() const {
     RegisterMapFormat format = Format();
     switch (format) {
       case kRegMapFormatCompact8:
@@ -101,7 +100,7 @@
 
   // The width of an entry in the table
   size_t EntryWidth() const {
-    return PcWidth() + RegWidth();
+    return DexPcWidth() + RegWidth();
   }
 
   const uint8_t* GetData() const {
@@ -113,10 +112,10 @@
   static const int kRegMapFormatShift = 5;
   static const uint8_t kRegMapFormatMask = 0x7;
 
-  const uint8_t* data_;  // The header and table data
+  const uint8_t* const data_;  // The header and table data
 };
 
 }  // namespace verifier
 }  // namespace art
 
-#endif  // ART_SRC_VERIFIER_GC_MAP_H_
+#endif  // ART_SRC_VERIFIER_DEX_GC_MAP_H_
diff --git a/src/verifier/method_verifier.cc b/src/verifier/method_verifier.cc
index a01aa8d..73aee9c 100644
--- a/src/verifier/method_verifier.cc
+++ b/src/verifier/method_verifier.cc
@@ -24,7 +24,7 @@
 #include "dex_file.h"
 #include "dex_instruction.h"
 #include "dex_instruction_visitor.h"
-#include "gc_map.h"
+#include "verifier/dex_gc_map.h"
 #include "intern_table.h"
 #include "leb128.h"
 #include "logging.h"
@@ -549,8 +549,9 @@
 bool MethodVerifier::VerifyInstructions() {
   const Instruction* inst = Instruction::At(code_item_->insns_);
 
-  /* Flag the start of the method as a branch target. */
+  /* Flag the start of the method as a branch target, and a GC point due to stack overflow errors */
   insn_flags_[0].SetBranchTarget();
+  insn_flags_[0].SetGcPoint();
 
   uint32_t insns_size = code_item_->insns_size_in_code_units_;
   for (uint32_t dex_pc = 0; dex_pc < insns_size;) {
@@ -945,7 +946,7 @@
   return true;
 }
 
-const std::vector<uint8_t>* CreateLengthPrefixedGcMap(const std::vector<uint8_t>& gc_map) {
+static const std::vector<uint8_t>* CreateLengthPrefixedDexGcMap(const std::vector<uint8_t>& gc_map) {
   std::vector<uint8_t>* length_prefixed_gc_map = new std::vector<uint8_t>;
   length_prefixed_gc_map->push_back((gc_map.size() & 0xff000000) >> 24);
   length_prefixed_gc_map->push_back((gc_map.size() & 0x00ff0000) >> 16);
@@ -1004,12 +1005,8 @@
 #ifndef NDEBUG
   VerifyGcMap(*map);
 #endif
-  const std::vector<uint8_t>* gc_map = CreateLengthPrefixedGcMap(*(map.get()));
-  verifier::MethodVerifier::SetGcMap(ref, *gc_map);
-
-  if (foo_method_ != NULL) {
-    foo_method_->SetGcMap(&gc_map->at(0));
-  }
+  const std::vector<uint8_t>* dex_gc_map = CreateLengthPrefixedDexGcMap(*(map.get()));
+  verifier::MethodVerifier::SetDexGcMap(ref, *dex_gc_map);
 
 #else  // defined(ART_USE_LLVM_COMPILER) || defined(ART_USE_GREENLAND_COMPILER)
   /* Generate Inferred Register Category for LLVM-based Code Generator */
@@ -3212,31 +3209,31 @@
   }
 }
 
-void MethodVerifier::SetGcMap(Compiler::MethodReference ref, const std::vector<uint8_t>& gc_map) {
+void MethodVerifier::SetDexGcMap(Compiler::MethodReference ref, const std::vector<uint8_t>& gc_map) {
   {
-    MutexLock mu(*gc_maps_lock_);
-    GcMapTable::iterator it = gc_maps_->find(ref);
-    if (it != gc_maps_->end()) {
+    MutexLock mu(*dex_gc_maps_lock_);
+    DexGcMapTable::iterator it = dex_gc_maps_->find(ref);
+    if (it != dex_gc_maps_->end()) {
       delete it->second;
-      gc_maps_->erase(it);
+      dex_gc_maps_->erase(it);
     }
-    gc_maps_->Put(ref, &gc_map);
+    dex_gc_maps_->Put(ref, &gc_map);
   }
-  CHECK(GetGcMap(ref) != NULL);
+  CHECK(GetDexGcMap(ref) != NULL);
 }
 
-const std::vector<uint8_t>* MethodVerifier::GetGcMap(Compiler::MethodReference ref) {
-  MutexLock mu(*gc_maps_lock_);
-  GcMapTable::const_iterator it = gc_maps_->find(ref);
-  if (it == gc_maps_->end()) {
+const std::vector<uint8_t>* MethodVerifier::GetDexGcMap(Compiler::MethodReference ref) {
+  MutexLock mu(*dex_gc_maps_lock_);
+  DexGcMapTable::const_iterator it = dex_gc_maps_->find(ref);
+  if (it == dex_gc_maps_->end()) {
     return NULL;
   }
   CHECK(it->second != NULL);
   return it->second;
 }
 
-Mutex* MethodVerifier::gc_maps_lock_ = NULL;
-MethodVerifier::GcMapTable* MethodVerifier::gc_maps_ = NULL;
+Mutex* MethodVerifier::dex_gc_maps_lock_ = NULL;
+MethodVerifier::DexGcMapTable* MethodVerifier::dex_gc_maps_ = NULL;
 
 Mutex* MethodVerifier::rejected_classes_lock_ = NULL;
 MethodVerifier::RejectedClassesTable* MethodVerifier::rejected_classes_ = NULL;
@@ -3247,10 +3244,10 @@
 #endif
 
 void MethodVerifier::Init() {
-  gc_maps_lock_ = new Mutex("verifier GC maps lock");
+  dex_gc_maps_lock_ = new Mutex("verifier GC maps lock");
   {
-    MutexLock mu(*gc_maps_lock_);
-    gc_maps_ = new MethodVerifier::GcMapTable;
+    MutexLock mu(*dex_gc_maps_lock_);
+    dex_gc_maps_ = new MethodVerifier::DexGcMapTable;
   }
 
   rejected_classes_lock_ = new Mutex("verifier rejected classes lock");
@@ -3270,13 +3267,13 @@
 
 void MethodVerifier::Shutdown() {
   {
-    MutexLock mu(*gc_maps_lock_);
-    STLDeleteValues(gc_maps_);
-    delete gc_maps_;
-    gc_maps_ = NULL;
+    MutexLock mu(*dex_gc_maps_lock_);
+    STLDeleteValues(dex_gc_maps_);
+    delete dex_gc_maps_;
+    dex_gc_maps_ = NULL;
   }
-  delete gc_maps_lock_;
-  gc_maps_lock_ = NULL;
+  delete dex_gc_maps_lock_;
+  dex_gc_maps_lock_ = NULL;
 
   {
     MutexLock mu(*rejected_classes_lock_);
diff --git a/src/verifier/method_verifier.h b/src/verifier/method_verifier.h
index 92621ef..c1c2562 100644
--- a/src/verifier/method_verifier.h
+++ b/src/verifier/method_verifier.h
@@ -188,8 +188,8 @@
   // information
   void Dump(std::ostream& os) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
-  static const std::vector<uint8_t>* GetGcMap(Compiler::MethodReference ref)
-      LOCKS_EXCLUDED(gc_maps_lock_);
+  static const std::vector<uint8_t>* GetDexGcMap(Compiler::MethodReference ref)
+      LOCKS_EXCLUDED(dex_gc_maps_lock_);
 
   // Fills 'monitor_enter_dex_pcs' with the dex pcs of the monitor-enter instructions corresponding
   // to the locks held at 'dex_pc' in 'm'.
@@ -578,11 +578,11 @@
   InsnFlags* CurrentInsnFlags();
 
   // All the GC maps that the verifier has created
-  typedef SafeMap<const Compiler::MethodReference, const std::vector<uint8_t>*> GcMapTable;
-  static Mutex* gc_maps_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
-  static GcMapTable* gc_maps_ GUARDED_BY(gc_maps_lock_);
-  static void SetGcMap(Compiler::MethodReference ref, const std::vector<uint8_t>& gc_map)
-      LOCKS_EXCLUDED(gc_maps_lock_);
+  typedef SafeMap<const Compiler::MethodReference, const std::vector<uint8_t>*> DexGcMapTable;
+  static Mutex* dex_gc_maps_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
+  static DexGcMapTable* dex_gc_maps_ GUARDED_BY(dex_gc_maps_lock_);
+  static void SetDexGcMap(Compiler::MethodReference ref, const std::vector<uint8_t>& dex_gc_map)
+      LOCKS_EXCLUDED(dex_gc_maps_lock_);
 
   typedef std::set<Compiler::ClassReference> RejectedClassesTable;
   static Mutex* rejected_classes_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
diff --git a/test/ReferenceMap/stack_walk_refmap_jni.cc b/test/ReferenceMap/stack_walk_refmap_jni.cc
index 8cb1ed2..649e6ea 100644
--- a/test/ReferenceMap/stack_walk_refmap_jni.cc
+++ b/test/ReferenceMap/stack_walk_refmap_jni.cc
@@ -18,12 +18,12 @@
 
 #include "UniquePtr.h"
 #include "class_linker.h"
+#include "gc_map.h"
 #include "object.h"
 #include "object_utils.h"
 #include "scoped_thread_state_change.h"
 #include "thread.h"
 #include "jni.h"
-#include "verifier/gc_map.h"
 #include "verifier/method_verifier.h"
 
 namespace art {
@@ -55,7 +55,7 @@
     }
     LOG(INFO) << "At " << PrettyMethod(m, false);
 
-    verifier::DexPcToReferenceMap map(m->GetGcMap(), m->GetGcMapLength());
+    NativePcOffsetToReferenceMap map(m->GetNativeGcMap());
 
     if (m->IsCalleeSaveMethod()) {
       LOG(WARNING) << "no PC for " << PrettyMethod(m);
@@ -75,31 +75,31 @@
     // we know the Dex registers with live reference values. Assert that what we
     // find is what is expected.
     if (m_name.compare("f") == 0) {
-      ref_bitmap = map.FindBitMap(0x03U);
+      ref_bitmap = map.FindBitMap(m->NativePcOffset(m->ToNativePc(0x03U)));
       CHECK(ref_bitmap);
       CHECK_REGS_CONTAIN_REFS(8);  // v8: this
 
-      ref_bitmap = map.FindBitMap(0x06U);
+      ref_bitmap = map.FindBitMap(m->NativePcOffset(m->ToNativePc(0x06U)));
       CHECK(ref_bitmap);
       CHECK_REGS_CONTAIN_REFS(8, 1);  // v8: this, v1: x
 
-      ref_bitmap = map.FindBitMap(0x08U);
+      ref_bitmap = map.FindBitMap(m->NativePcOffset(m->ToNativePc(0x08U)));
       CHECK(ref_bitmap);
       CHECK_REGS_CONTAIN_REFS(8, 3, 1);  // v8: this, v3: y, v1: x
 
-      ref_bitmap = map.FindBitMap(0x0cU);
+      ref_bitmap = map.FindBitMap(m->NativePcOffset(m->ToNativePc(0x0cU)));
       CHECK(ref_bitmap);
       CHECK_REGS_CONTAIN_REFS(8, 3, 1);  // v8: this, v3: y, v1: x
 
-      ref_bitmap = map.FindBitMap(0x0eU);
+      ref_bitmap = map.FindBitMap(m->NativePcOffset(m->ToNativePc(0x0eU)));
       CHECK(ref_bitmap);
       CHECK_REGS_CONTAIN_REFS(8, 3, 1);  // v8: this, v3: y, v1: x
 
-      ref_bitmap = map.FindBitMap(0x10U);
+      ref_bitmap = map.FindBitMap(m->NativePcOffset(m->ToNativePc(0x10U)));
       CHECK(ref_bitmap);
       CHECK_REGS_CONTAIN_REFS(8, 3, 1);  // v8: this, v3: y, v1: x
 
-      ref_bitmap = map.FindBitMap(0x13U);
+      ref_bitmap = map.FindBitMap(m->NativePcOffset(m->ToNativePc(0x13U)));
       CHECK(ref_bitmap);
       // v2 is added because of the instruction at DexPC 0024. Object merges with 0 is Object. See:
       //   0024: move-object v3, v2
@@ -107,53 +107,49 @@
       // Detaled dex instructions for ReferenceMap.java are at the end of this function.
       CHECK_REGS_CONTAIN_REFS(8, 3, 2, 1);  // v8: this, v3: y, v2: y, v1: x
 
-      ref_bitmap = map.FindBitMap(0x15U);
+      ref_bitmap = map.FindBitMap(m->NativePcOffset(m->ToNativePc(0x18U)));
       CHECK(ref_bitmap);
       CHECK_REGS_CONTAIN_REFS(8, 2, 1, 0);  // v8: this, v2: y, v1: x, v0: ex
 
-      ref_bitmap = map.FindBitMap(0x18U);
-      CHECK(ref_bitmap);
-      CHECK_REGS_CONTAIN_REFS(8, 2, 1, 0);  // v8: this, v2: y, v1: x, v0: ex
-
-      ref_bitmap = map.FindBitMap(0x1aU);
+      ref_bitmap = map.FindBitMap(m->NativePcOffset(m->ToNativePc(0x1aU)));
       CHECK(ref_bitmap);
       CHECK_REGS_CONTAIN_REFS(8, 5, 2, 1, 0);  // v8: this, v5: x[1], v2: y, v1: x, v0: ex
 
-      ref_bitmap = map.FindBitMap(0x1dU);
+      ref_bitmap = map.FindBitMap(m->NativePcOffset(m->ToNativePc(0x1dU)));
       CHECK(ref_bitmap);
       CHECK_REGS_CONTAIN_REFS(8, 5, 2, 1, 0);  // v8: this, v5: x[1], v2: y, v1: x, v0: ex
 
-      ref_bitmap = map.FindBitMap(0x1fU);
+      ref_bitmap = map.FindBitMap(m->NativePcOffset(m->ToNativePc(0x1fU)));
       CHECK(ref_bitmap);
       // v5 is removed from the root set because there is a "merge" operation.
       // See 0015: if-nez v2, 001f.
       CHECK_REGS_CONTAIN_REFS(8, 2, 1, 0);  // v8: this, v2: y, v1: x, v0: ex
 
-      ref_bitmap = map.FindBitMap(0x21U);
+      ref_bitmap = map.FindBitMap(m->NativePcOffset(m->ToNativePc(0x21U)));
       CHECK(ref_bitmap);
       CHECK_REGS_CONTAIN_REFS(8, 2, 1, 0);  // v8: this, v2: y, v1: x, v0: ex
 
-      ref_bitmap = map.FindBitMap(0x25U);
+      ref_bitmap = map.FindBitMap(m->NativePcOffset(m->ToNativePc(0x25U)));
       CHECK(ref_bitmap);
       CHECK_REGS_CONTAIN_REFS(8, 3, 2, 1, 0);  // v8: this, v3: y, v2: y, v1: x, v0: ex
 
-      ref_bitmap = map.FindBitMap(0x27U);
+      ref_bitmap = map.FindBitMap(m->NativePcOffset(m->ToNativePc(0x27U)));
       CHECK(ref_bitmap);
       CHECK_REGS_CONTAIN_REFS(8, 4, 2, 1);  // v8: this, v4: ex, v2: y, v1: x
 
-      ref_bitmap = map.FindBitMap(0x29U);
+      ref_bitmap = map.FindBitMap(m->NativePcOffset(m->ToNativePc(0x29U)));
       CHECK(ref_bitmap);
       CHECK_REGS_CONTAIN_REFS(8, 4, 2, 1);  // v8: this, v4: ex, v2: y, v1: x
 
-      ref_bitmap = map.FindBitMap(0x2cU);
+      ref_bitmap = map.FindBitMap(m->NativePcOffset(m->ToNativePc(0x2cU)));
       CHECK(ref_bitmap);
       CHECK_REGS_CONTAIN_REFS(8, 4, 2, 1);  // v8: this, v4: ex, v2: y, v1: x
 
-      ref_bitmap = map.FindBitMap(0x2fU);
+      ref_bitmap = map.FindBitMap(m->NativePcOffset(m->ToNativePc(0x2fU)));
       CHECK(ref_bitmap);
       CHECK_REGS_CONTAIN_REFS(8, 4, 3, 2, 1);  // v8: this, v4: ex, v3: y, v2: y, v1: x
 
-      ref_bitmap = map.FindBitMap(0x32U);
+      ref_bitmap = map.FindBitMap(m->NativePcOffset(m->ToNativePc(0x32U)));
       CHECK(ref_bitmap);
       CHECK_REGS_CONTAIN_REFS(8, 3, 2, 1, 0);  // v8: this, v3: y, v2: y, v1: x, v0: ex
     }
diff --git a/test/StackWalk/stack_walk_jni.cc b/test/StackWalk/stack_walk_jni.cc
index 5fdb92f..3c37a98 100644
--- a/test/StackWalk/stack_walk_jni.cc
+++ b/test/StackWalk/stack_walk_jni.cc
@@ -18,11 +18,11 @@
 
 #include "UniquePtr.h"
 #include "class_linker.h"
+#include "gc_map.h"
 #include "object.h"
 #include "object_utils.h"
 #include "jni.h"
 #include "scoped_thread_state_change.h"
-#include "verifier/gc_map.h"
 
 namespace art {
 
@@ -58,8 +58,8 @@
     }
     const uint8_t* reg_bitmap = NULL;
     if (!IsShadowFrame()) {
-      verifier::DexPcToReferenceMap map(m->GetGcMap(), m->GetGcMapLength());
-      reg_bitmap = map.FindBitMap(GetDexPc());
+      NativePcOffsetToReferenceMap map(m->GetNativeGcMap());
+      reg_bitmap = map.FindBitMap(GetNativePcOffset());
     }
     MethodHelper mh(m);
     StringPiece m_name(mh.GetName());