diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 22abba1..655c7dd 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -17,17 +17,18 @@
 LOCAL_PATH := art
 
 TEST_COMMON_SRC_FILES := \
+	compiler/dex/arena_allocator_test.cc \
 	compiler/driver/compiler_driver_test.cc \
 	compiler/elf_writer_test.cc \
 	compiler/image_test.cc \
 	compiler/jni/jni_compiler_test.cc \
 	compiler/oat_test.cc \
 	compiler/output_stream_test.cc \
-	compiler/utils/bit_vector_test.cc \
 	compiler/utils/dedupe_set_test.cc \
 	compiler/utils/arm/managed_register_arm_test.cc \
 	compiler/utils/x86/managed_register_x86_test.cc \
 	runtime/barrier_test.cc \
+	runtime/base/bit_vector_test.cc \
 	runtime/base/histogram_test.cc \
 	runtime/base/mutex_test.cc \
 	runtime/base/timing_logger_test.cc \
diff --git a/compiler/Android.mk b/compiler/Android.mk
index 0d3acbd..fc2f02b 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -79,8 +79,6 @@
 	utils/arm/assembler_arm.cc \
 	utils/arm/managed_register_arm.cc \
 	utils/assembler.cc \
-	utils/allocator.cc \
-	utils/bit_vector.cc \
 	utils/mips/assembler_mips.cc \
 	utils/mips/managed_register_mips.cc \
 	utils/x86/assembler_x86.cc \
diff --git a/compiler/utils/allocator.h b/compiler/dex/arena_allocator_test.cc
similarity index 60%
copy from compiler/utils/allocator.h
copy to compiler/dex/arena_allocator_test.cc
index 3482a79..63dc615 100644
--- a/compiler/utils/allocator.h
+++ b/compiler/dex/arena_allocator_test.cc
@@ -14,28 +14,20 @@
  * limitations under the License.
  */
 
-#ifndef ART_COMPILER_UTILS_ALLOCATOR_H_
-#define ART_COMPILER_UTILS_ALLOCATOR_H_
-
-#include "base/macros.h"
+#include "arena_allocator.h"
+#include "arena_bit_vector.h"
+#include "gtest/gtest.h"
 
 namespace art {
 
-class Allocator {
- public:
-  static Allocator* GetMallocAllocator();
-  static Allocator* GetNoopAllocator();
-
-  Allocator() {}
-  virtual ~Allocator() {}
-
-  virtual void* Alloc(size_t) = 0;
-  virtual void Free(void*) = 0;
-
- private:
-  DISALLOW_COPY_AND_ASSIGN(Allocator);
-};
+TEST(ArenaAllocator, Test) {
+  ArenaPool pool;
+  ArenaAllocator arena(&pool);
+  ArenaBitVector bv(&arena, 10, true);
+  bv.SetBit(5);
+  EXPECT_EQ(1U, bv.GetStorageSize());
+  bv.SetBit(35);
+  EXPECT_EQ(2U, bv.GetStorageSize());
+}
 
 }  // namespace art
-
-#endif  // ART_COMPILER_UTILS_ALLOCATOR_H_
diff --git a/compiler/dex/arena_bit_vector.h b/compiler/dex/arena_bit_vector.h
index 7d2f3ff..4b2193a 100644
--- a/compiler/dex/arena_bit_vector.h
+++ b/compiler/dex/arena_bit_vector.h
@@ -18,8 +18,8 @@
 #define ART_COMPILER_DEX_ARENA_BIT_VECTOR_H_
 
 #include "arena_allocator.h"
+#include "base/bit_vector.h"
 #include "compiler_enums.h"
-#include "utils/bit_vector.h"
 
 namespace art {
 
diff --git a/compiler/oat_test.cc b/compiler/oat_test.cc
index 634a160..af86743 100644
--- a/compiler/oat_test.cc
+++ b/compiler/oat_test.cc
@@ -28,6 +28,8 @@
 
 class OatTest : public CommonTest {
  protected:
+  static const bool kCompile = false;  // DISABLED_ due to the time to compile libcore
+
   void CheckMethod(mirror::ArtMethod* method,
                    const OatFile::OatMethod& oat_method,
                    const DexFile* dex_file)
@@ -40,7 +42,7 @@
       EXPECT_TRUE(oat_method.GetCode() == NULL) << PrettyMethod(method) << " "
                                                 << oat_method.GetCode();
 #if !defined(ART_USE_PORTABLE_COMPILER)
-      EXPECT_EQ(oat_method.GetFrameSizeInBytes(), static_cast<uint32_t>(kStackAlignment));
+      EXPECT_EQ(oat_method.GetFrameSizeInBytes(), kCompile ? kStackAlignment : 0);
       EXPECT_EQ(oat_method.GetCoreSpillMask(), 0U);
       EXPECT_EQ(oat_method.GetFpSpillMask(), 0U);
 #endif
@@ -65,7 +67,6 @@
 };
 
 TEST_F(OatTest, WriteRead) {
-  const bool compile = false;  // DISABLED_ due to the time to compile libcore
   ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
 
   // TODO: make selectable
@@ -77,7 +78,7 @@
   InstructionSet insn_set = kIsTargetBuild ? kThumb2 : kX86;
   compiler_driver_.reset(new CompilerDriver(compiler_backend, insn_set, false, NULL, 2, true));
   jobject class_loader = NULL;
-  if (compile) {
+  if (kCompile) {
     base::TimingLogger timings("OatTest::WriteRead", false, false);
     compiler_driver_->CompileAll(class_loader, class_linker->GetBootClassPath(), timings);
   }
@@ -96,7 +97,7 @@
                                             tmp.GetFile());
   ASSERT_TRUE(success);
 
-  if (compile) {  // OatWriter strips the code, regenerate to compare
+  if (kCompile) {  // OatWriter strips the code, regenerate to compare
     base::TimingLogger timings("CommonTest::WriteRead", false, false);
     compiler_driver_->CompileAll(class_loader, class_linker->GetBootClassPath(), timings);
   }
@@ -120,16 +121,18 @@
   for (size_t i = 0; i < dex_file->NumClassDefs(); i++) {
     const DexFile::ClassDef& class_def = dex_file->GetClassDef(i);
     const byte* class_data = dex_file->GetClassData(class_def);
-    size_t num_virtual_methods =0;
+    size_t num_virtual_methods = 0;
     if (class_data != NULL) {
       ClassDataItemIterator it(*dex_file, class_data);
       num_virtual_methods = it.NumVirtualMethods();
     }
     const char* descriptor = dex_file->GetClassDescriptor(class_def);
+    mirror::Class* klass = class_linker->FindClass(descriptor, NULL);
 
     UniquePtr<const OatFile::OatClass> oat_class(oat_dex_file->GetOatClass(i));
-
-    mirror::Class* klass = class_linker->FindClass(descriptor, NULL);
+    CHECK_EQ(mirror::Class::Status::kStatusNotReady, oat_class->GetStatus()) << descriptor;
+    CHECK_EQ(kCompile ? OatClassType::kOatClassAllCompiled : OatClassType::kOatClassNoneCompiled,
+             oat_class->GetType()) << descriptor;
 
     size_t method_index = 0;
     for (size_t i = 0; i < klass->NumDirectMethods(); i++, method_index++) {
diff --git a/compiler/oat_writer.cc b/compiler/oat_writer.cc
index f23b72b..f681d7d 100644
--- a/compiler/oat_writer.cc
+++ b/compiler/oat_writer.cc
@@ -18,6 +18,7 @@
 
 #include <zlib.h>
 
+#include "base/bit_vector.h"
 #include "base/stl_util.h"
 #include "base/unix_file/fd_file.h"
 #include "class_linker.h"
@@ -70,7 +71,9 @@
     size_oat_dex_file_location_checksum_(0),
     size_oat_dex_file_offset_(0),
     size_oat_dex_file_methods_offsets_(0),
+    size_oat_class_type_(0),
     size_oat_class_status_(0),
+    size_oat_class_method_bitmaps_(0),
     size_oat_class_method_offsets_(0) {
   size_t offset = InitOatHeader();
   offset = InitOatDexFiles(offset);
@@ -142,12 +145,48 @@
       oat_dex_files_[i]->methods_offsets_[class_def_index] = offset;
       const DexFile::ClassDef& class_def = dex_file->GetClassDef(class_def_index);
       const byte* class_data = dex_file->GetClassData(class_def);
-      uint32_t num_methods = 0;
+      uint32_t num_non_null_compiled_methods = 0;
+      UniquePtr<std::vector<CompiledMethod*> > compiled_methods(new std::vector<CompiledMethod*>());
       if (class_data != NULL) {  // ie not an empty class, such as a marker interface
         ClassDataItemIterator it(*dex_file, class_data);
         size_t num_direct_methods = it.NumDirectMethods();
         size_t num_virtual_methods = it.NumVirtualMethods();
-        num_methods = num_direct_methods + num_virtual_methods;
+        size_t num_methods = num_direct_methods + num_virtual_methods;
+
+        // Fill in the compiled_methods_ array for methods that have a
+        // CompiledMethod. We track the number of non-null entries in
+        // num_non_null_compiled_methods since we only want to allocate
+        // OatMethodOffsets for the compiled methods.
+        compiled_methods->reserve(num_methods);
+        while (it.HasNextStaticField()) {
+          it.Next();
+        }
+        while (it.HasNextInstanceField()) {
+          it.Next();
+        }
+        size_t class_def_method_index = 0;
+        while (it.HasNextDirectMethod()) {
+          uint32_t method_idx = it.GetMemberIndex();
+          CompiledMethod* compiled_method =
+              compiler_driver_->GetCompiledMethod(MethodReference(dex_file, method_idx));
+          compiled_methods->push_back(compiled_method);
+          if (compiled_method != NULL) {
+              num_non_null_compiled_methods++;
+          }
+          class_def_method_index++;
+          it.Next();
+        }
+        while (it.HasNextVirtualMethod()) {
+          uint32_t method_idx = it.GetMemberIndex();
+          CompiledMethod* compiled_method =
+              compiler_driver_->GetCompiledMethod(MethodReference(dex_file, method_idx));
+          compiled_methods->push_back(compiled_method);
+          if (compiled_method != NULL) {
+              num_non_null_compiled_methods++;
+          }
+          class_def_method_index++;
+          it.Next();
+        }
       }
 
       ClassReference class_ref(dex_file, class_def_index);
@@ -161,7 +200,8 @@
         status = mirror::Class::kStatusNotReady;
       }
 
-      OatClass* oat_class = new OatClass(offset, status, num_methods);
+      OatClass* oat_class = new OatClass(offset, compiled_methods.release(),
+                                         num_non_null_compiled_methods, status);
       oat_classes_.push_back(oat_class);
       offset += oat_class->SizeOf();
     }
@@ -212,20 +252,20 @@
   for (size_t i = 0; i != dex_files_->size(); ++i) {
     const DexFile* dex_file = (*dex_files_)[i];
     CHECK(dex_file != NULL);
-    offset = InitOatCodeDexFile(offset, oat_class_index, *dex_file);
+    offset = InitOatCodeDexFile(offset, &oat_class_index, *dex_file);
   }
   return offset;
 }
 
 size_t OatWriter::InitOatCodeDexFile(size_t offset,
-                                     size_t& oat_class_index,
+                                     size_t* oat_class_index,
                                      const DexFile& dex_file) {
   for (size_t class_def_index = 0;
        class_def_index < dex_file.NumClassDefs();
-       class_def_index++, oat_class_index++) {
+       class_def_index++, (*oat_class_index)++) {
     const DexFile::ClassDef& class_def = dex_file.GetClassDef(class_def_index);
-    offset = InitOatCodeClassDef(offset, oat_class_index, class_def_index, dex_file, class_def);
-    oat_classes_[oat_class_index]->UpdateChecksum(*oat_header_);
+    offset = InitOatCodeClassDef(offset, *oat_class_index, class_def_index, dex_file, class_def);
+    oat_classes_[*oat_class_index]->UpdateChecksum(*oat_header_);
   }
   return offset;
 }
@@ -240,7 +280,7 @@
     return offset;
   }
   ClassDataItemIterator it(dex_file, class_data);
-  CHECK_EQ(oat_classes_[oat_class_index]->method_offsets_.size(),
+  CHECK_LE(oat_classes_[oat_class_index]->method_offsets_.size(),
            it.NumDirectMethods() + it.NumVirtualMethods());
   // Skip fields
   while (it.HasNextStaticField()) {
@@ -251,32 +291,35 @@
   }
   // Process methods
   size_t class_def_method_index = 0;
+  size_t method_offsets_index = 0;
   while (it.HasNextDirectMethod()) {
     bool is_native = (it.GetMemberAccessFlags() & kAccNative) != 0;
     offset = InitOatCodeMethod(offset, oat_class_index, class_def_index, class_def_method_index,
-                               is_native, it.GetMethodInvokeType(class_def), it.GetMemberIndex(),
-                               &dex_file);
+                               &method_offsets_index, is_native,
+                               it.GetMethodInvokeType(class_def), it.GetMemberIndex(), dex_file);
     class_def_method_index++;
     it.Next();
   }
   while (it.HasNextVirtualMethod()) {
     bool is_native = (it.GetMemberAccessFlags() & kAccNative) != 0;
     offset = InitOatCodeMethod(offset, oat_class_index, class_def_index, class_def_method_index,
-                               is_native, it.GetMethodInvokeType(class_def), it.GetMemberIndex(),
-                               &dex_file);
+                               &method_offsets_index, is_native,
+                               it.GetMethodInvokeType(class_def), it.GetMemberIndex(), dex_file);
     class_def_method_index++;
     it.Next();
   }
   DCHECK(!it.HasNext());
+  CHECK_LE(method_offsets_index, class_def_method_index);
   return offset;
 }
 
 size_t OatWriter::InitOatCodeMethod(size_t offset, size_t oat_class_index,
                                     size_t __attribute__((unused)) class_def_index,
                                     size_t class_def_method_index,
+                                    size_t* method_offsets_index,
                                     bool __attribute__((unused)) is_native,
                                     InvokeType invoke_type,
-                                    uint32_t method_idx, const DexFile* dex_file) {
+                                    uint32_t method_idx, const DexFile& dex_file) {
   // derived from CompiledMethod if available
   uint32_t code_offset = 0;
   uint32_t frame_size_in_bytes = kStackAlignment;
@@ -292,8 +335,7 @@
       oat_class->GetOatMethodOffsetsOffsetFromOatHeader(class_def_method_index);
 #endif
 
-  CompiledMethod* compiled_method =
-      compiler_driver_->GetCompiledMethod(MethodReference(dex_file, method_idx));
+  CompiledMethod* compiled_method = oat_class->GetCompiledMethod(class_def_method_index);
   if (compiled_method != NULL) {
 #if defined(ART_USE_PORTABLE_COMPILER)
     compiled_method->AddOatdataOffsetToCompliledCodeOffset(
@@ -358,7 +400,7 @@
 
 #if !defined(NDEBUG)
     // We expect GC maps except when the class hasn't been verified or the method is native
-    ClassReference class_ref(dex_file, class_def_index);
+    ClassReference class_ref(&dex_file, class_def_index);
     CompiledClass* compiled_class = compiler_driver_->GetCompiledClass(class_ref);
     mirror::Class::Status status;
     if (compiled_class != NULL) {
@@ -371,7 +413,7 @@
     CHECK(gc_map_size != 0 || is_native || status < mirror::Class::kStatusVerified)
         << &gc_map << " " << gc_map_size << " " << (is_native ? "true" : "false") << " "
         << (status < mirror::Class::kStatusVerified) << " " << status << " "
-        << PrettyMethod(method_idx, *dex_file);
+        << PrettyMethod(method_idx, dex_file);
 #endif
 
     // Deduplicate GC maps
@@ -384,24 +426,26 @@
       offset += gc_map_size;
       oat_header_->UpdateChecksum(&gc_map[0], gc_map_size);
     }
+
+    oat_class->method_offsets_[*method_offsets_index] =
+        OatMethodOffsets(code_offset,
+                         frame_size_in_bytes,
+                         core_spill_mask,
+                         fp_spill_mask,
+                         mapping_table_offset,
+                         vmap_table_offset,
+                         gc_map_offset);
+    (*method_offsets_index)++;
   }
 
-  oat_class->method_offsets_[class_def_method_index] =
-      OatMethodOffsets(code_offset,
-                       frame_size_in_bytes,
-                       core_spill_mask,
-                       fp_spill_mask,
-                       mapping_table_offset,
-                       vmap_table_offset,
-                       gc_map_offset);
 
   if (compiler_driver_->IsImage()) {
     ClassLinker* linker = Runtime::Current()->GetClassLinker();
-    mirror::DexCache* dex_cache = linker->FindDexCache(*dex_file);
+    mirror::DexCache* dex_cache = linker->FindDexCache(dex_file);
     // Unchecked as we hold mutator_lock_ on entry.
     ScopedObjectAccessUnchecked soa(Thread::Current());
-    mirror::ArtMethod* method = linker->ResolveMethod(*dex_file, method_idx, dex_cache,
-                                                           NULL, NULL, invoke_type);
+    mirror::ArtMethod* method = linker->ResolveMethod(dex_file, method_idx, dex_cache,
+                                                      NULL, NULL, invoke_type);
     CHECK(method != NULL);
     method->SetFrameSizeInBytes(frame_size_in_bytes);
     method->SetCoreSpillMask(core_spill_mask);
@@ -491,7 +535,9 @@
     DO_STAT(size_oat_dex_file_location_checksum_);
     DO_STAT(size_oat_dex_file_offset_);
     DO_STAT(size_oat_dex_file_methods_offsets_);
+    DO_STAT(size_oat_class_type_);
     DO_STAT(size_oat_class_status_);
+    DO_STAT(size_oat_class_method_bitmaps_);
     DO_STAT(size_oat_class_method_offsets_);
     #undef DO_STAT
 
@@ -586,7 +632,7 @@
   for (size_t i = 0; i != oat_dex_files_.size(); ++i) {
     const DexFile* dex_file = (*dex_files_)[i];
     CHECK(dex_file != NULL);
-    relative_offset = WriteCodeDexFile(out, file_offset, relative_offset, oat_class_index,
+    relative_offset = WriteCodeDexFile(out, file_offset, relative_offset, &oat_class_index,
                                        *dex_file);
     if (relative_offset == 0) {
       return 0;
@@ -596,12 +642,12 @@
 }
 
 size_t OatWriter::WriteCodeDexFile(OutputStream& out, const size_t file_offset,
-                                   size_t relative_offset, size_t& oat_class_index,
+                                   size_t relative_offset, size_t* oat_class_index,
                                    const DexFile& dex_file) {
   for (size_t class_def_index = 0; class_def_index < dex_file.NumClassDefs();
-      class_def_index++, oat_class_index++) {
+      class_def_index++, (*oat_class_index)++) {
     const DexFile::ClassDef& class_def = dex_file.GetClassDef(class_def_index);
-    relative_offset = WriteCodeClassDef(out, file_offset, relative_offset, oat_class_index,
+    relative_offset = WriteCodeClassDef(out, file_offset, relative_offset, *oat_class_index,
                                         dex_file, class_def);
     if (relative_offset == 0) {
       return 0;
@@ -637,11 +683,12 @@
   }
   // Process methods
   size_t class_def_method_index = 0;
+  size_t method_offsets_index = 0;
   while (it.HasNextDirectMethod()) {
     bool is_static = (it.GetMemberAccessFlags() & kAccStatic) != 0;
     relative_offset = WriteCodeMethod(out, file_offset, relative_offset, oat_class_index,
-                                      class_def_method_index, is_static, it.GetMemberIndex(),
-                                      dex_file);
+                                      class_def_method_index, &method_offsets_index, is_static,
+                                      it.GetMemberIndex(), dex_file);
     if (relative_offset == 0) {
       return 0;
     }
@@ -650,28 +697,30 @@
   }
   while (it.HasNextVirtualMethod()) {
     relative_offset = WriteCodeMethod(out, file_offset, relative_offset, oat_class_index,
-                                      class_def_method_index, false, it.GetMemberIndex(), dex_file);
+                                      class_def_method_index, &method_offsets_index, false,
+                                      it.GetMemberIndex(), dex_file);
     if (relative_offset == 0) {
       return 0;
     }
     class_def_method_index++;
     it.Next();
   }
+  DCHECK(!it.HasNext());
+  CHECK_LE(method_offsets_index, class_def_method_index);
   return relative_offset;
 }
 
 size_t OatWriter::WriteCodeMethod(OutputStream& out, const size_t file_offset,
                                   size_t relative_offset, size_t oat_class_index,
-                                  size_t class_def_method_index, bool is_static,
-                                  uint32_t method_idx, const DexFile& dex_file) {
-  const CompiledMethod* compiled_method =
-      compiler_driver_->GetCompiledMethod(MethodReference(&dex_file, method_idx));
-
-  const OatMethodOffsets& method_offsets =
-      oat_classes_[oat_class_index]->method_offsets_[class_def_method_index];
-
+                                  size_t class_def_method_index, size_t* method_offsets_index,
+                                  bool is_static, uint32_t method_idx, const DexFile& dex_file) {
+  OatClass* oat_class = oat_classes_[oat_class_index];
+  const CompiledMethod* compiled_method = oat_class->GetCompiledMethod(class_def_method_index);
 
   if (compiled_method != NULL) {  // ie. not an abstract method
+    const OatMethodOffsets method_offsets = oat_class->method_offsets_[*method_offsets_index];
+    (*method_offsets_index)++;
+
 #if !defined(ART_USE_PORTABLE_COMPILER)
     uint32_t aligned_offset = compiled_method->AlignCode(relative_offset);
     uint32_t aligned_code_delta = aligned_offset - relative_offset;
@@ -854,29 +903,96 @@
   return true;
 }
 
-OatWriter::OatClass::OatClass(size_t offset, mirror::Class::Status status, uint32_t methods_count) {
+OatWriter::OatClass::OatClass(size_t offset,
+                              std::vector<CompiledMethod*>* compiled_methods,
+                              uint32_t num_non_null_compiled_methods,
+                              mirror::Class::Status status) {
+  CHECK(compiled_methods !=  NULL);
+  uint32_t num_methods = compiled_methods->size();
+  CHECK_LE(num_non_null_compiled_methods, num_methods);
+
   offset_ = offset;
+  compiled_methods_ = compiled_methods;
+  oat_method_offsets_offsets_from_oat_class_.resize(num_methods);
+
+  // Since both kOatClassNoneCompiled and kOatClassAllCompiled could
+  // apply when there are 0 methods, we just arbitrarily say that 0
+  // methods means kOatClassNoneCompiled and that we won't use
+  // kOatClassAllCompiled unless there is at least one compiled
+  // method. This means in an interpretter only system, we can assert
+  // that all classes are kOatClassNoneCompiled.
+  if (num_non_null_compiled_methods == 0) {
+    type_ = kOatClassNoneCompiled;
+  } else if (num_non_null_compiled_methods == num_methods) {
+    type_ = kOatClassAllCompiled;
+  } else {
+    type_ = kOatClassSomeCompiled;
+  }
+
   status_ = status;
-  method_offsets_.resize(methods_count);
+  method_offsets_.resize(num_non_null_compiled_methods);
+
+  uint32_t oat_method_offsets_offset_from_oat_class = sizeof(type_) + sizeof(status_);
+  if (type_ == kOatClassSomeCompiled) {
+    method_bitmap_ = new BitVector(num_methods, false, Allocator::GetMallocAllocator());
+    method_bitmap_size_ = method_bitmap_->GetSizeOf();
+    oat_method_offsets_offset_from_oat_class += sizeof(method_bitmap_size_);
+    oat_method_offsets_offset_from_oat_class += method_bitmap_size_;
+  } else {
+    method_bitmap_ = NULL;
+    method_bitmap_size_ = 0;
+  }
+
+  for (size_t i = 0; i < num_methods; i++) {
+    CompiledMethod* compiled_method = (*compiled_methods_)[i];
+    if (compiled_method == NULL) {
+      oat_method_offsets_offsets_from_oat_class_[i] = 0;
+    } else {
+      oat_method_offsets_offsets_from_oat_class_[i] = oat_method_offsets_offset_from_oat_class;
+      oat_method_offsets_offset_from_oat_class += sizeof(OatMethodOffsets);
+      if (type_ == kOatClassSomeCompiled) {
+        method_bitmap_->SetBit(i);
+      }
+    }
+  }
 }
 
+OatWriter::OatClass::~OatClass() {
+  delete compiled_methods_;
+}
+
+#if defined(ART_USE_PORTABLE_COMPILER)
 size_t OatWriter::OatClass::GetOatMethodOffsetsOffsetFromOatHeader(
     size_t class_def_method_index_) const {
-  return offset_ + GetOatMethodOffsetsOffsetFromOatClass(class_def_method_index_);
+  uint32_t method_offset = GetOatMethodOffsetsOffsetFromOatClass(class_def_method_index_);
+  if (method_offset == 0) {
+    return 0;
+  }
+  return offset_ + method_offset;
 }
 
 size_t OatWriter::OatClass::GetOatMethodOffsetsOffsetFromOatClass(
     size_t class_def_method_index_) const {
-  return sizeof(status_)
-          + (sizeof(method_offsets_[0]) * class_def_method_index_);
+  return oat_method_offsets_offsets_from_oat_class_[class_def_method_index_];
 }
+#endif
 
 size_t OatWriter::OatClass::SizeOf() const {
-  return GetOatMethodOffsetsOffsetFromOatClass(method_offsets_.size());
+  return sizeof(status_)
+          + sizeof(type_)
+          + ((method_bitmap_size_ == 0) ? 0 : sizeof(method_bitmap_size_))
+          + method_bitmap_size_
+          + (sizeof(method_offsets_[0]) * method_offsets_.size());
 }
 
 void OatWriter::OatClass::UpdateChecksum(OatHeader& oat_header) const {
   oat_header.UpdateChecksum(&status_, sizeof(status_));
+  oat_header.UpdateChecksum(&type_, sizeof(type_));
+  if (method_bitmap_size_ != 0) {
+    CHECK_EQ(kOatClassSomeCompiled, type_);
+    oat_header.UpdateChecksum(&method_bitmap_size_, sizeof(method_bitmap_size_));
+    oat_header.UpdateChecksum(method_bitmap_->GetRawStorage(), method_bitmap_size_);
+  }
   oat_header.UpdateChecksum(&method_offsets_[0],
                             sizeof(method_offsets_[0]) * method_offsets_.size());
 }
@@ -890,17 +1006,30 @@
     return false;
   }
   oat_writer->size_oat_class_status_ += sizeof(status_);
-  DCHECK_EQ(static_cast<off_t>(file_offset + GetOatMethodOffsetsOffsetFromOatHeader(0)),
-            out.Seek(0, kSeekCurrent));
+  if (!out.WriteFully(&type_, sizeof(type_))) {
+    PLOG(ERROR) << "Failed to write oat class type to " << out.GetLocation();
+    return false;
+  }
+  oat_writer->size_oat_class_type_ += sizeof(type_);
+  if (method_bitmap_size_ != 0) {
+    CHECK_EQ(kOatClassSomeCompiled, type_);
+    if (!out.WriteFully(&method_bitmap_size_, sizeof(method_bitmap_size_))) {
+      PLOG(ERROR) << "Failed to write method bitmap size to " << out.GetLocation();
+      return false;
+    }
+    oat_writer->size_oat_class_method_bitmaps_ += sizeof(method_bitmap_size_);
+    if (!out.WriteFully(method_bitmap_->GetRawStorage(), method_bitmap_size_)) {
+      PLOG(ERROR) << "Failed to write method bitmap to " << out.GetLocation();
+      return false;
+    }
+    oat_writer->size_oat_class_method_bitmaps_ += method_bitmap_size_;
+  }
   if (!out.WriteFully(&method_offsets_[0],
                       sizeof(method_offsets_[0]) * method_offsets_.size())) {
     PLOG(ERROR) << "Failed to write method offsets to " << out.GetLocation();
     return false;
   }
   oat_writer->size_oat_class_method_offsets_ += sizeof(method_offsets_[0]) * method_offsets_.size();
-  DCHECK_EQ(static_cast<off_t>(file_offset +
-                               GetOatMethodOffsetsOffsetFromOatHeader(method_offsets_.size())),
-            out.Seek(0, kSeekCurrent));
   return true;
 }
 
diff --git a/compiler/oat_writer.h b/compiler/oat_writer.h
index d5f7e21..e3cb0a8 100644
--- a/compiler/oat_writer.h
+++ b/compiler/oat_writer.h
@@ -30,6 +30,7 @@
 
 namespace art {
 
+class BitVector;
 class OutputStream;
 
 // OatHeader         variable length with count of D OatDexFiles
@@ -90,7 +91,7 @@
   size_t InitOatCodeDexFiles(size_t offset)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
   size_t InitOatCodeDexFile(size_t offset,
-                            size_t& oat_class_index,
+                            size_t* oat_class_index,
                             const DexFile& dex_file)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
   size_t InitOatCodeClassDef(size_t offset,
@@ -99,21 +100,22 @@
                              const DexFile::ClassDef& class_def)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
   size_t InitOatCodeMethod(size_t offset, size_t oat_class_index, size_t class_def_index,
-                           size_t class_def_method_index, bool is_native, InvokeType type,
-                           uint32_t method_idx, const DexFile*)
+                           size_t class_def_method_index, size_t* method_offsets_index,
+                           bool is_native, InvokeType type, uint32_t method_idx, const DexFile&)
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
   bool WriteTables(OutputStream& out, const size_t file_offset);
   size_t WriteCode(OutputStream& out, const size_t file_offset);
   size_t WriteCodeDexFiles(OutputStream& out, const size_t file_offset, size_t relative_offset);
   size_t WriteCodeDexFile(OutputStream& out, const size_t file_offset, size_t relative_offset,
-                          size_t& oat_class_index, const DexFile& dex_file);
+                          size_t* oat_class_index, const DexFile& dex_file);
   size_t WriteCodeClassDef(OutputStream& out, const size_t file_offset, size_t relative_offset,
                            size_t oat_class_index, const DexFile& dex_file,
                            const DexFile::ClassDef& class_def);
   size_t WriteCodeMethod(OutputStream& out, const size_t file_offset, size_t relative_offset,
-                         size_t oat_class_index, size_t class_def_method_index, bool is_static,
-                         uint32_t method_idx, const DexFile& dex_file);
+                         size_t oat_class_index, size_t class_def_method_index,
+                         size_t* method_offsets_index, bool is_static, uint32_t method_idx,
+                         const DexFile& dex_file);
 
   void ReportWriteFailure(const char* what, uint32_t method_idx, const DexFile& dex_file,
                           OutputStream& out) const;
@@ -142,13 +144,24 @@
 
   class OatClass {
    public:
-    explicit OatClass(size_t offset, mirror::Class::Status status, uint32_t methods_count);
+    explicit OatClass(size_t offset,
+                      std::vector<CompiledMethod*>* compiled_methods,
+                      uint32_t num_non_null_compiled_methods,
+                      mirror::Class::Status status);
+    ~OatClass();
+#if defined(ART_USE_PORTABLE_COMPILER)
     size_t GetOatMethodOffsetsOffsetFromOatHeader(size_t class_def_method_index_) const;
     size_t GetOatMethodOffsetsOffsetFromOatClass(size_t class_def_method_index_) const;
+#endif
     size_t SizeOf() const;
     void UpdateChecksum(OatHeader& oat_header) const;
     bool Write(OatWriter* oat_writer, OutputStream& out, const size_t file_offset) const;
 
+    CompiledMethod* GetCompiledMethod(size_t class_def_method_index) const {
+      DCHECK(compiled_methods_ != NULL);
+      return (*compiled_methods_)[class_def_method_index];
+    }
+
     // Offset of start of OatClass from beginning of OatHeader. It is
     // used to validate file position when writing. For Portable, it
     // is also used to calculate the position of the OatMethodOffsets
@@ -156,8 +169,37 @@
     // patched to point to code in the Portable .o ELF objects.
     size_t offset_;
 
+    // CompiledMethods for each class_def_method_index, or NULL if no method is available.
+    std::vector<CompiledMethod*>* compiled_methods_;
+
+    // Offset from OatClass::offset_ to the OatMethodOffsets for the
+    // class_def_method_index. If 0, it means the corresponding
+    // CompiledMethod entry in OatClass::compiled_methods_ should be
+    // NULL and that the OatClass::type_ should be kOatClassBitmap.
+    std::vector<uint32_t> oat_method_offsets_offsets_from_oat_class_;
+
     // data to write
-    mirror::Class::Status status_;
+
+    COMPILE_ASSERT(mirror::Class::Status::kStatusMax < (2 ^ 16), class_status_wont_fit_in_16bits);
+    int16_t status_;
+
+    COMPILE_ASSERT(OatClassType::kOatClassMax < (2 ^ 16), oat_class_type_wont_fit_in_16bits);
+    uint16_t type_;
+
+    uint32_t method_bitmap_size_;
+
+    // bit vector indexed by ClassDef method index. When
+    // OatClassType::type_ is kOatClassBitmap, a set bit indicates the
+    // method has an OatMethodOffsets in methods_offsets_, otherwise
+    // the entry was ommited to save space. If OatClassType::type_ is
+    // not is kOatClassBitmap, the bitmap will be NULL.
+    BitVector* method_bitmap_;
+
+    // OatMethodOffsets for each CompiledMethod present in the
+    // OatClass. Note that some may be missing if
+    // OatClass::compiled_methods_ contains NULL values (and
+    // oat_method_offsets_offsets_from_oat_class_ should contain 0
+    // values in this case).
     std::vector<OatMethodOffsets> method_offsets_;
 
    private:
@@ -214,7 +256,9 @@
   uint32_t size_oat_dex_file_location_checksum_;
   uint32_t size_oat_dex_file_offset_;
   uint32_t size_oat_dex_file_methods_offsets_;
+  uint32_t size_oat_class_type_;
   uint32_t size_oat_class_status_;
+  uint32_t size_oat_class_method_bitmaps_;
   uint32_t size_oat_class_method_offsets_;
 
   // Code mappings for deduplication. Deduplication is already done on a pointer basis by the
diff --git a/compiler/utils/dedupe_set.h b/compiler/utils/dedupe_set.h
index 53c1afa..638e0ec 100644
--- a/compiler/utils/dedupe_set.h
+++ b/compiler/utils/dedupe_set.h
@@ -22,6 +22,7 @@
 
 #include "base/mutex.h"
 #include "base/stl_util.h"
+#include "base/stringprintf.h"
 
 namespace art {
 
diff --git a/compiler/utils/dedupe_set_test.cc b/compiler/utils/dedupe_set_test.cc
index 2c6787b..8abe6de 100644
--- a/compiler/utils/dedupe_set_test.cc
+++ b/compiler/utils/dedupe_set_test.cc
@@ -14,8 +14,9 @@
  * limitations under the License.
  */
 
-#include "common_test.h"
 #include "dedupe_set.h"
+#include "gtest/gtest.h"
+#include "thread-inl.h"
 
 namespace art {
 
diff --git a/oatdump/oatdump.cc b/oatdump/oatdump.cc
index ea06b02..fdeeaec 100644
--- a/oatdump/oatdump.cc
+++ b/oatdump/oatdump.cc
@@ -263,8 +263,10 @@
       const char* descriptor = dex_file->GetClassDescriptor(class_def);
       UniquePtr<const OatFile::OatClass> oat_class(oat_dex_file.GetOatClass(class_def_index));
       CHECK(oat_class.get() != NULL);
-      os << StringPrintf("%zd: %s (type_idx=%d) (", class_def_index, descriptor, class_def.class_idx_)
-         << oat_class->GetStatus() << ")\n";
+      os << StringPrintf("%zd: %s (type_idx=%d)", class_def_index, descriptor, class_def.class_idx_)
+         << " (" << oat_class->GetStatus() << ")"
+         << " (" << oat_class->GetType() << ")\n";
+      // TODO: include bitmap here if type is kOatClassBitmap?
       Indenter indent_filter(os.rdbuf(), kIndentChar, kIndentBy1Count);
       std::ostream indented_os(&indent_filter);
       DumpOatClass(indented_os, *oat_class.get(), *(dex_file.get()), class_def);
diff --git a/runtime/Android.mk b/runtime/Android.mk
index 8579222..e4b7e47 100644
--- a/runtime/Android.mk
+++ b/runtime/Android.mk
@@ -21,6 +21,8 @@
 LIBART_COMMON_SRC_FILES := \
 	atomic.cc.arm \
 	barrier.cc \
+	base/allocator.cc \
+	base/bit_vector.cc \
 	base/logging.cc \
 	base/mutex.cc \
 	base/stringpiece.cc \
@@ -247,6 +249,7 @@
 	locks.h \
 	lock_word.h \
 	mirror/class.h \
+	oat.h \
 	thread.h \
 	thread_state.h \
 	verifier/method_verifier.h
diff --git a/compiler/utils/allocator.cc b/runtime/base/allocator.cc
similarity index 100%
rename from compiler/utils/allocator.cc
rename to runtime/base/allocator.cc
diff --git a/compiler/utils/allocator.h b/runtime/base/allocator.h
similarity index 88%
rename from compiler/utils/allocator.h
rename to runtime/base/allocator.h
index 3482a79..917bf0b 100644
--- a/compiler/utils/allocator.h
+++ b/runtime/base/allocator.h
@@ -14,8 +14,8 @@
  * limitations under the License.
  */
 
-#ifndef ART_COMPILER_UTILS_ALLOCATOR_H_
-#define ART_COMPILER_UTILS_ALLOCATOR_H_
+#ifndef ART_RUNTIME_BASE_ALLOCATOR_H_
+#define ART_RUNTIME_BASE_ALLOCATOR_H_
 
 #include "base/macros.h"
 
@@ -38,4 +38,4 @@
 
 }  // namespace art
 
-#endif  // ART_COMPILER_UTILS_ALLOCATOR_H_
+#endif  // ART_RUNTIME_BASE_ALLOCATOR_H_
diff --git a/compiler/utils/bit_vector.cc b/runtime/base/bit_vector.cc
similarity index 70%
rename from compiler/utils/bit_vector.cc
rename to runtime/base/bit_vector.cc
index 81a639a..3b82651 100644
--- a/compiler/utils/bit_vector.cc
+++ b/runtime/base/bit_vector.cc
@@ -28,14 +28,14 @@
   0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000,
   0x40000000, 0x80000000 };
 
-static inline uint32_t BitsToWords(unsigned int bits) {
+static inline uint32_t BitsToWords(uint32_t bits) {
   return (bits + 31) >> 5;
 }
 
 // TODO: replace excessive argument defaulting when we are at gcc 4.7
 // or later on host with delegating constructor support. Specifically,
 // starts_bits and storage_size/storage are mutually exclusive.
-BitVector::BitVector(unsigned int start_bits,
+BitVector::BitVector(uint32_t start_bits,
                      bool expandable,
                      Allocator* allocator,
                      uint32_t storage_size,
@@ -58,10 +58,10 @@
 /*
  * Determine whether or not the specified bit is set.
  */
-bool BitVector::IsBitSet(unsigned int num) {
+bool BitVector::IsBitSet(uint32_t num) const {
   DCHECK_LT(num, storage_size_ * sizeof(uint32_t) * 8);
 
-  unsigned int val = storage_[num >> 5] & check_masks[num & 0x1f];
+  uint32_t val = storage_[num >> 5] & check_masks[num & 0x1f];
   return (val != 0);
 }
 
@@ -75,12 +75,12 @@
  * TUNING: this could have pathologically bad growth/expand behavior.  Make sure we're
  * not using it badly or change resize mechanism.
  */
-void BitVector::SetBit(unsigned int num) {
+void BitVector::SetBit(uint32_t num) {
   if (num >= storage_size_ * sizeof(uint32_t) * 8) {
     DCHECK(expandable_) << "Attempted to expand a non-expandable bitmap to position " << num;
 
     /* Round up to word boundaries for "num+1" bits */
-    unsigned int new_size = BitsToWords(num + 1);
+    uint32_t new_size = BitsToWords(num + 1);
     DCHECK_GT(new_size, storage_size_);
     uint32_t *new_storage =
         static_cast<uint32_t*>(allocator_->Alloc(new_size * sizeof(uint32_t)));
@@ -96,7 +96,7 @@
 }
 
 // Mark the specified bit as "unset".
-void BitVector::ClearBit(unsigned int num) {
+void BitVector::ClearBit(uint32_t num) {
   DCHECK_LT(num, storage_size_ * sizeof(uint32_t) * 8);
   storage_[num >> 5] &= ~check_masks[num & 0x1f];
 }
@@ -105,7 +105,7 @@
 void BitVector::Intersect(const BitVector* src) {
   DCHECK_EQ(storage_size_, src->GetStorageSize());
   DCHECK_EQ(expandable_, src->IsExpandable());
-  for (unsigned int idx = 0; idx < storage_size_; idx++) {
+  for (uint32_t idx = 0; idx < storage_size_; idx++) {
     storage_[idx] &= src->GetRawStorageWord(idx);
   }
 }
@@ -116,22 +116,44 @@
 void BitVector::Union(const BitVector* src) {
   DCHECK_EQ(storage_size_, src->GetStorageSize());
   DCHECK_EQ(expandable_, src->IsExpandable());
-  for (unsigned int idx = 0; idx < storage_size_; idx++) {
+  for (uint32_t idx = 0; idx < storage_size_; idx++) {
     storage_[idx] |= src->GetRawStorageWord(idx);
   }
 }
 
 // Count the number of bits that are set.
-int BitVector::NumSetBits() {
-  unsigned int count = 0;
-
-  for (unsigned int word = 0; word < storage_size_; word++) {
+uint32_t BitVector::NumSetBits() const {
+  uint32_t count = 0;
+  for (uint32_t word = 0; word < storage_size_; word++) {
     count += __builtin_popcount(storage_[word]);
   }
   return count;
 }
 
-BitVector::Iterator* BitVector::GetIterator() {
+// Count the number of bits that are set up through and including num.
+uint32_t BitVector::NumSetBits(uint32_t num) const {
+  DCHECK_LT(num, storage_size_ * sizeof(uint32_t) * 8);
+  uint32_t last_word = num >> 5;
+  uint32_t partial_word_bits = num & 0x1f;
+
+  // partial_word_bits |  # |                         |                      | partial_word_mask
+  //             00000 |  0 | 0xffffffff >> (31 -  0) | (1 <<  (0 + 1)) - 1  | 0x00000001
+  //             00001 |  1 | 0xffffffff >> (31 -  1) | (1 <<  (1 + 1)) - 1  | 0x00000003
+  //             00010 |  2 | 0xffffffff >> (31 -  2) | (1 <<  (2 + 1)) - 1  | 0x00000007
+  //             ..... |
+  //             11110 | 30 | 0xffffffff >> (31 - 30) | (1 << (30 + 1)) - 1  | 0x7fffffff
+  //             11111 | 31 | 0xffffffff >> (31 - 31) | last_full_word++     | 0xffffffff
+  uint32_t partial_word_mask = 0xffffffff >> (0x1f - partial_word_bits);
+
+  uint32_t count = 0;
+  for (uint32_t word = 0; word < last_word; word++) {
+    count += __builtin_popcount(storage_[word]);
+  }
+  count += __builtin_popcount(storage_[last_word] & partial_word_mask);
+  return count;
+}
+
+BitVector::Iterator* BitVector::GetIterator() const {
   return new (allocator_) Iterator(this);
 }
 
@@ -140,13 +162,13 @@
  * since there might be unused bits - setting those to one will confuse the
  * iterator.
  */
-void BitVector::SetInitialBits(unsigned int num_bits) {
+void BitVector::SetInitialBits(uint32_t num_bits) {
   DCHECK_LE(BitsToWords(num_bits), storage_size_);
-  unsigned int idx;
+  uint32_t idx;
   for (idx = 0; idx < (num_bits >> 5); idx++) {
     storage_[idx] = -1;
   }
-  unsigned int rem_num_bits = num_bits & 0x1f;
+  uint32_t rem_num_bits = num_bits & 0x1f;
   if (rem_num_bits) {
     storage_[idx] = (1 << rem_num_bits) - 1;
   }
diff --git a/compiler/utils/bit_vector.h b/runtime/base/bit_vector.h
similarity index 89%
rename from compiler/utils/bit_vector.h
rename to runtime/base/bit_vector.h
index bf0f7c3..74bec08 100644
--- a/compiler/utils/bit_vector.h
+++ b/runtime/base/bit_vector.h
@@ -14,8 +14,8 @@
  * limitations under the License.
  */
 
-#ifndef ART_COMPILER_UTILS_BIT_VECTOR_H_
-#define ART_COMPILER_UTILS_BIT_VECTOR_H_
+#ifndef ART_RUNTIME_BASE_BIT_VECTOR_H_
+#define ART_RUNTIME_BASE_BIT_VECTOR_H_
 
 #include <stdint.h>
 #include <stddef.h>
@@ -34,7 +34,7 @@
   public:
     class Iterator {
       public:
-        explicit Iterator(BitVector* bit_vector)
+        explicit Iterator(const BitVector* bit_vector)
           : p_bits_(bit_vector),
             bit_storage_(bit_vector->GetRawStorage()),
             bit_index_(0),
@@ -77,8 +77,8 @@
         }
 
       private:
-        BitVector* const p_bits_;
-        uint32_t* const bit_storage_;
+        const BitVector* const p_bits_;
+        const uint32_t* const bit_storage_;
         uint32_t bit_index_;           // Current index (size in bits).
         const uint32_t bit_size_;      // Size of vector in bits.
 
@@ -95,9 +95,7 @@
 
     void SetBit(uint32_t num);
     void ClearBit(uint32_t num);
-    void MarkAllBits(bool set);
-    void DebugBitVector(char* msg, int length);
-    bool IsBitSet(uint32_t num);
+    bool IsBitSet(uint32_t num) const;
     void ClearAllBits();
     void SetInitialBits(uint32_t num_bits);
     void Copy(BitVector* src) {
@@ -111,15 +109,17 @@
         (expandable_ == src->IsExpandable()) &&
         (memcmp(storage_, src->GetRawStorage(), storage_size_ * sizeof(uint32_t)) == 0);
     }
-    int32_t NumSetBits();
+    uint32_t NumSetBits() const;
+    uint32_t NumSetBits(uint32_t num) const;
 
-    Iterator* GetIterator();
+    Iterator* GetIterator() const;
 
     uint32_t GetStorageSize() const { return storage_size_; }
     bool IsExpandable() const { return expandable_; }
     uint32_t GetRawStorageWord(size_t idx) const { return storage_[idx]; }
     uint32_t* GetRawStorage() { return storage_; }
     const uint32_t* GetRawStorage() const { return storage_; }
+    size_t GetSizeOf() const { return storage_size_ * sizeof(uint32_t); }
 
   private:
     Allocator* const allocator_;
@@ -131,4 +131,4 @@
 
 }  // namespace art
 
-#endif  // ART_COMPILER_UTILS_BIT_VECTOR_H_
+#endif  // ART_RUNTIME_BASE_BIT_VECTOR_H_
diff --git a/compiler/utils/bit_vector_test.cc b/runtime/base/bit_vector_test.cc
similarity index 68%
rename from compiler/utils/bit_vector_test.cc
rename to runtime/base/bit_vector_test.cc
index 5c18ec5..d99d059 100644
--- a/compiler/utils/bit_vector_test.cc
+++ b/runtime/base/bit_vector_test.cc
@@ -14,9 +14,9 @@
  * limitations under the License.
  */
 
-#include "common_test.h"
-#include "bit_vector.h"
 #include "UniquePtr.h"
+#include "bit_vector.h"
+#include "gtest/gtest.h"
 
 namespace art {
 
@@ -25,9 +25,12 @@
 
   BitVector bv(kBits, false, Allocator::GetMallocAllocator());
   EXPECT_EQ(1U, bv.GetStorageSize());
+  EXPECT_EQ(kWordSize, bv.GetSizeOf());
   EXPECT_FALSE(bv.IsExpandable());
 
-  EXPECT_EQ(0, bv.NumSetBits());
+  EXPECT_EQ(0U, bv.NumSetBits());
+  EXPECT_EQ(0U, bv.NumSetBits(0));
+  EXPECT_EQ(0U, bv.NumSetBits(kBits - 1));
   for (size_t i = 0; i < kBits; i++) {
     EXPECT_FALSE(bv.IsBitSet(i));
   }
@@ -42,7 +45,9 @@
 
   bv.SetBit(0);
   bv.SetBit(kBits - 1);
-  EXPECT_EQ(2, bv.NumSetBits());
+  EXPECT_EQ(2U, bv.NumSetBits());
+  EXPECT_EQ(1U, bv.NumSetBits(0));
+  EXPECT_EQ(2U, bv.NumSetBits(kBits - 1));
   EXPECT_TRUE(bv.IsBitSet(0));
   for (size_t i = 1; i < kBits - 1; i++) {
     EXPECT_FALSE(bv.IsBitSet(i));
@@ -65,32 +70,53 @@
 
   BitVector bv(0U, false, Allocator::GetNoopAllocator(), kWords, bits);
   EXPECT_EQ(kWords, bv.GetStorageSize());
+  EXPECT_EQ(kWords * kWordSize, bv.GetSizeOf());
   EXPECT_EQ(bits, bv.GetRawStorage());
-  EXPECT_EQ(0, bv.NumSetBits());
+  EXPECT_EQ(0U, bv.NumSetBits());
 
   bv.SetBit(8);
-  EXPECT_EQ(1, bv.NumSetBits());
+  EXPECT_EQ(1U, bv.NumSetBits());
   EXPECT_EQ(0x00000100U, bv.GetRawStorageWord(0));
   EXPECT_EQ(0x00000000U, bv.GetRawStorageWord(1));
-  EXPECT_EQ(1, bv.NumSetBits());
+  EXPECT_EQ(1U, bv.NumSetBits());
 
   bv.SetBit(16);
-  EXPECT_EQ(2, bv.NumSetBits());
+  EXPECT_EQ(2U, bv.NumSetBits());
   EXPECT_EQ(0x00010100U, bv.GetRawStorageWord(0));
   EXPECT_EQ(0x00000000U, bv.GetRawStorageWord(1));
-  EXPECT_EQ(2, bv.NumSetBits());
+  EXPECT_EQ(2U, bv.NumSetBits());
 
   bv.SetBit(32);
-  EXPECT_EQ(3, bv.NumSetBits());
+  EXPECT_EQ(3U, bv.NumSetBits());
   EXPECT_EQ(0x00010100U, bv.GetRawStorageWord(0));
   EXPECT_EQ(0x00000001U, bv.GetRawStorageWord(1));
-  EXPECT_EQ(3, bv.NumSetBits());
+  EXPECT_EQ(3U, bv.NumSetBits());
 
   bv.SetBit(48);
-  EXPECT_EQ(4, bv.NumSetBits());
+  EXPECT_EQ(4U, bv.NumSetBits());
   EXPECT_EQ(0x00010100U, bv.GetRawStorageWord(0));
   EXPECT_EQ(0x00010001U, bv.GetRawStorageWord(1));
-  EXPECT_EQ(4, bv.NumSetBits());
+  EXPECT_EQ(4U, bv.NumSetBits());
+
+  EXPECT_EQ(0U, bv.NumSetBits(0));
+
+  EXPECT_EQ(0U, bv.NumSetBits(7));
+  EXPECT_EQ(1U, bv.NumSetBits(8));
+  EXPECT_EQ(1U, bv.NumSetBits(9));
+
+  EXPECT_EQ(1U, bv.NumSetBits(15));
+  EXPECT_EQ(2U, bv.NumSetBits(16));
+  EXPECT_EQ(2U, bv.NumSetBits(17));
+
+  EXPECT_EQ(2U, bv.NumSetBits(31));
+  EXPECT_EQ(3U, bv.NumSetBits(32));
+  EXPECT_EQ(3U, bv.NumSetBits(33));
+
+  EXPECT_EQ(3U, bv.NumSetBits(47));
+  EXPECT_EQ(4U, bv.NumSetBits(48));
+  EXPECT_EQ(4U, bv.NumSetBits(49));
+
+  EXPECT_EQ(4U, bv.NumSetBits(63));
 }
 
 }  // namespace art
diff --git a/runtime/exception_test.cc b/runtime/exception_test.cc
index 2e6b0a8..a5f9997 100644
--- a/runtime/exception_test.cc
+++ b/runtime/exception_test.cc
@@ -146,7 +146,7 @@
   ScopedObjectAccess soa(env);
 
   std::vector<uintptr_t> fake_stack;
-  ASSERT_EQ(kStackAlignment, 16);
+  ASSERT_EQ(kStackAlignment, 16U);
   ASSERT_EQ(sizeof(uintptr_t), sizeof(uint32_t));
 
 #if !defined(ART_USE_PORTABLE_COMPILER)
diff --git a/runtime/globals.h b/runtime/globals.h
index c397494..31574ff 100644
--- a/runtime/globals.h
+++ b/runtime/globals.h
@@ -30,30 +30,30 @@
 const size_t MB = KB * KB;
 const size_t GB = KB * KB * KB;
 
-const int kWordSize = sizeof(word);
-const int kPointerSize = sizeof(void*);
+const size_t kWordSize = sizeof(word);
+const size_t kPointerSize = sizeof(void*);
 
-const int kBitsPerByte = 8;
-const int kBitsPerByteLog2 = 3;
+const size_t kBitsPerByte = 8;
+const size_t kBitsPerByteLog2 = 3;
 const int kBitsPerWord = kWordSize * kBitsPerByte;
-const int kWordHighBitMask = 1 << (kBitsPerWord - 1);
+const size_t kWordHighBitMask = 1 << (kBitsPerWord - 1);
 
 // Required stack alignment
-const int kStackAlignment = 16;
+const size_t kStackAlignment = 16;
 
 // Required object alignment
-const int kObjectAlignment = 8;
+const size_t kObjectAlignment = 8;
 
 // ARM instruction alignment. ARM processors require code to be 4-byte aligned,
 // but ARM ELF requires 8..
-const int kArmAlignment = 8;
+const size_t kArmAlignment = 8;
 
 // MIPS instruction alignment.  MIPS processors require code to be 4-byte aligned.
 // TODO: Can this be 4?
-const int kMipsAlignment = 8;
+const size_t kMipsAlignment = 8;
 
 // X86 instruction alignment. This is the recommended alignment for maximum performance.
-const int kX86Alignment = 16;
+const size_t kX86Alignment = 16;
 
 // System page size. We check this against sysconf(_SC_PAGE_SIZE) at runtime, but use a simple
 // compile-time constant so the compiler can generate better code.
diff --git a/runtime/mirror/class.h b/runtime/mirror/class.h
index dbc6f57..d15f337 100644
--- a/runtime/mirror/class.h
+++ b/runtime/mirror/class.h
@@ -122,6 +122,7 @@
     kStatusVerified = 7,  // Logically part of linking; done pre-init.
     kStatusInitializing = 8,  // Class init in progress.
     kStatusInitialized = 9,  // Ready to go.
+    kStatusMax = 10,
   };
 
   Status GetStatus() const {
diff --git a/runtime/oat.cc b/runtime/oat.cc
index c01f77c..6fe5d10 100644
--- a/runtime/oat.cc
+++ b/runtime/oat.cc
@@ -22,7 +22,7 @@
 namespace art {
 
 const uint8_t OatHeader::kOatMagic[] = { 'o', 'a', 't', '\n' };
-const uint8_t OatHeader::kOatVersion[] = { '0', '0', '7', '\0' };
+const uint8_t OatHeader::kOatVersion[] = { '0', '0', '8', '\0' };
 
 OatHeader::OatHeader() {
   memset(this, 0, sizeof(*this));
diff --git a/runtime/oat.h b/runtime/oat.h
index a653cf8..a9dc540 100644
--- a/runtime/oat.h
+++ b/runtime/oat.h
@@ -104,6 +104,19 @@
   DISALLOW_COPY_AND_ASSIGN(OatHeader);
 };
 
+// OatMethodOffsets are currently 7x32-bits=224-bits long, so if we can
+// save even one OatMethodOffsets struct, the more complicated encoding
+// using a bitmap pays for itself since few classes will have 224
+// methods.
+enum OatClassType {
+  kOatClassAllCompiled = 0,   // OatClass is followed by an OatMethodOffsets for each method.
+  kOatClassSomeCompiled = 1,  // A bitmap of which OatMethodOffsets are present follows the OatClass.
+  kOatClassNoneCompiled = 2,  // All methods are interpretted so no OatMethodOffsets are necessary.
+  kOatClassMax = 3,
+};
+
+std::ostream& operator<<(std::ostream& os, const OatClassType& rhs);
+
 class PACKED(4) OatMethodOffsets {
  public:
   OatMethodOffsets();
diff --git a/runtime/oat_file.cc b/runtime/oat_file.cc
index 7553dcc..fa2b485 100644
--- a/runtime/oat_file.cc
+++ b/runtime/oat_file.cc
@@ -18,6 +18,7 @@
 
 #include <dlfcn.h>
 
+#include "base/bit_vector.h"
 #include "base/stl_util.h"
 #include "base/unix_file/fd_file.h"
 #include "elf_file.h"
@@ -384,29 +385,92 @@
 
   const byte* oat_class_pointer = oat_file_->Begin() + oat_class_offset;
   CHECK_LT(oat_class_pointer, oat_file_->End()) << oat_file_->GetLocation();
-  mirror::Class::Status status = *reinterpret_cast<const mirror::Class::Status*>(oat_class_pointer);
 
-  const byte* methods_pointer = oat_class_pointer + sizeof(status);
+  const byte* status_pointer = oat_class_pointer;
+  CHECK_LT(status_pointer, oat_file_->End()) << oat_file_->GetLocation();
+  mirror::Class::Status status =
+      static_cast<mirror::Class::Status>(*reinterpret_cast<const int16_t*>(status_pointer));
+  CHECK_LT(status, mirror::Class::kStatusMax);
+
+  const byte* type_pointer = status_pointer + sizeof(uint16_t);
+  CHECK_LT(type_pointer, oat_file_->End()) << oat_file_->GetLocation();
+  OatClassType type = static_cast<OatClassType>(*reinterpret_cast<const uint16_t*>(type_pointer));
+  CHECK_LT(type, kOatClassMax);
+
+  const byte* bitmap_pointer = type_pointer + sizeof(int16_t);
+  CHECK_LT(bitmap_pointer, oat_file_->End()) << oat_file_->GetLocation();
+  uint32_t bitmap_size = 0;
+  if (type == kOatClassSomeCompiled) {
+    bitmap_size = static_cast<uint32_t>(*reinterpret_cast<const uint32_t*>(bitmap_pointer));
+    bitmap_pointer += sizeof(bitmap_size);
+    CHECK_LT(bitmap_pointer, oat_file_->End()) << oat_file_->GetLocation();
+  }
+
+  const byte* methods_pointer = bitmap_pointer + bitmap_size;
   CHECK_LT(methods_pointer, oat_file_->End()) << oat_file_->GetLocation();
 
   return new OatClass(oat_file_,
                       status,
+                      type,
+                      bitmap_size,
+                      reinterpret_cast<const uint32_t*>(bitmap_pointer),
                       reinterpret_cast<const OatMethodOffsets*>(methods_pointer));
 }
 
 OatFile::OatClass::OatClass(const OatFile* oat_file,
                             mirror::Class::Status status,
+                            OatClassType type,
+                            uint32_t bitmap_size,
+                            const uint32_t* bitmap_pointer,
                             const OatMethodOffsets* methods_pointer)
-    : oat_file_(oat_file), status_(status), methods_pointer_(methods_pointer) {}
+    : oat_file_(oat_file), status_(status), type_(type),
+      bitmap_(NULL), methods_pointer_(methods_pointer) {
+    switch (type_) {
+      case kOatClassAllCompiled: {
+        CHECK_EQ(0U, bitmap_size);
+        break;
+      }
+      case kOatClassSomeCompiled: {
+        CHECK_NE(0U, bitmap_size);
+        bitmap_ = new BitVector(0, false, Allocator::GetNoopAllocator(), bitmap_size,
+                                const_cast<uint32_t*>(bitmap_pointer));
+        break;
+      }
+      case kOatClassNoneCompiled: {
+        CHECK_EQ(0U, bitmap_size);
+        methods_pointer_ = NULL;
+        break;
+      }
+      case kOatClassMax: {
+        LOG(FATAL) << "Invalid OatClassType " << type_;
+        break;
+      }
+    }
+}
 
-OatFile::OatClass::~OatClass() {}
-
-mirror::Class::Status OatFile::OatClass::GetStatus() const {
-  return status_;
+OatFile::OatClass::~OatClass() {
+  delete bitmap_;
 }
 
 const OatFile::OatMethod OatFile::OatClass::GetOatMethod(uint32_t method_index) const {
-  const OatMethodOffsets& oat_method_offsets = methods_pointer_[method_index];
+  if (methods_pointer_ == NULL) {
+    CHECK_EQ(kOatClassNoneCompiled, type_);
+    return OatMethod(NULL, 0, 0, 0, 0, 0, 0, 0);
+  }
+  size_t methods_pointer_index;
+  if (bitmap_ == NULL) {
+    CHECK_EQ(kOatClassAllCompiled, type_);
+    methods_pointer_index = method_index;
+  } else {
+    CHECK_EQ(kOatClassSomeCompiled, type_);
+    if (!bitmap_->IsBitSet(method_index)) {
+      return OatMethod(NULL, 0, 0, 0, 0, 0, 0, 0);
+    }
+    size_t num_set_bits = bitmap_->NumSetBits(method_index);
+    CHECK_NE(0U, num_set_bits);
+    methods_pointer_index = num_set_bits - 1;
+  }
+  const OatMethodOffsets& oat_method_offsets = methods_pointer_[methods_pointer_index];
   return OatMethod(
       oat_file_->Begin(),
       oat_method_offsets.code_offset_,
diff --git a/runtime/oat_file.h b/runtime/oat_file.h
index af14760..887a9d1 100644
--- a/runtime/oat_file.h
+++ b/runtime/oat_file.h
@@ -29,6 +29,7 @@
 
 namespace art {
 
+class BitVector;
 class ElfFile;
 class MemMap;
 class OatMethodOffsets;
@@ -145,7 +146,13 @@
 
   class OatClass {
    public:
-    mirror::Class::Status GetStatus() const;
+    mirror::Class::Status GetStatus() const {
+      return status_;
+    }
+
+    OatClassType GetType() const {
+      return type_;
+    }
 
     // get the OatMethod entry based on its index into the class
     // defintion. direct methods come first, followed by virtual
@@ -157,10 +164,21 @@
    private:
     OatClass(const OatFile* oat_file,
              mirror::Class::Status status,
+             OatClassType type,
+             uint32_t bitmap_size,
+             const uint32_t* bitmap_pointer,
              const OatMethodOffsets* methods_pointer);
 
     const OatFile* oat_file_;
+
     const mirror::Class::Status status_;
+    COMPILE_ASSERT(mirror::Class::Status::kStatusMax < (2 ^ 16), class_status_wont_fit_in_16bits);
+
+    OatClassType type_;
+    COMPILE_ASSERT(OatClassType::kOatClassMax < (2 ^ 16), oat_class_type_wont_fit_in_16bits);
+
+    const BitVector* bitmap_;
+
     const OatMethodOffsets* methods_pointer_;
 
     friend class OatDexFile;