diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 07ff611..4f63099 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -27,6 +27,8 @@
   AllFields \
   ExceptionHandle \
   GetMethodSignature \
+  ImageLayoutA \
+  ImageLayoutB \
   Instrumentation \
   Interfaces \
   Lookup \
@@ -84,6 +86,7 @@
 ART_GTEST_dex_file_test_DEX_DEPS := GetMethodSignature Main Nested
 ART_GTEST_dex2oat_test_DEX_DEPS := $(ART_GTEST_dex2oat_environment_tests_DEX_DEPS) Statics
 ART_GTEST_exception_test_DEX_DEPS := ExceptionHandle
+ART_GTEST_image_test_DEX_DEPS := ImageLayoutA ImageLayoutB
 ART_GTEST_instrumentation_test_DEX_DEPS := Instrumentation
 ART_GTEST_jni_compiler_test_DEX_DEPS := MyClassNatives
 ART_GTEST_jni_internal_test_DEX_DEPS := AllFields StaticLeafMethods
diff --git a/compiler/common_compiler_test.cc b/compiler/common_compiler_test.cc
index 06a39b2..2af4d72 100644
--- a/compiler/common_compiler_test.cc
+++ b/compiler/common_compiler_test.cc
@@ -226,6 +226,7 @@
   method_inliner_map_.reset();
   verification_results_.reset();
   compiler_options_.reset();
+  image_reservation_.reset();
 
   CommonRuntimeTest::TearDown();
 }
diff --git a/compiler/image_test.cc b/compiler/image_test.cc
index 421a1d5..ea4b7ee 100644
--- a/compiler/image_test.cc
+++ b/compiler/image_test.cc
@@ -39,42 +39,104 @@
 
 namespace art {
 
+static const uintptr_t kRequestedImageBase = ART_BASE_ADDRESS;
+
+struct CompilationHelper {
+  std::vector<std::string> dex_file_locations;
+  std::vector<ScratchFile> image_locations;
+  std::vector<std::unique_ptr<const DexFile>> extra_dex_files;
+  std::vector<ScratchFile> image_files;
+  std::vector<ScratchFile> oat_files;
+  std::vector<ScratchFile> vdex_files;
+  std::string image_dir;
+
+  void Compile(CompilerDriver* driver,
+               ImageHeader::StorageMode storage_mode);
+
+  std::vector<size_t> GetImageObjectSectionSizes();
+
+  ~CompilationHelper();
+};
+
 class ImageTest : public CommonCompilerTest {
  protected:
   virtual void SetUp() {
     ReserveImageSpace();
     CommonCompilerTest::SetUp();
   }
+
   void TestWriteRead(ImageHeader::StorageMode storage_mode);
+
+  void Compile(ImageHeader::StorageMode storage_mode,
+               CompilationHelper& out_helper,
+               const std::string& extra_dex = "",
+               const std::string& image_class = "");
+
+  std::unordered_set<std::string>* GetImageClasses() OVERRIDE {
+    return new std::unordered_set<std::string>(image_classes_);
+  }
+
+ private:
+  std::unordered_set<std::string> image_classes_;
 };
 
-void ImageTest::TestWriteRead(ImageHeader::StorageMode storage_mode) {
-  CreateCompilerDriver(Compiler::kOptimizing, kRuntimeISA, kIsTargetBuild ? 2U : 16U);
+CompilationHelper::~CompilationHelper() {
+  for (ScratchFile& image_file : image_files) {
+    image_file.Unlink();
+  }
+  for (ScratchFile& oat_file : oat_files) {
+    oat_file.Unlink();
+  }
+  for (ScratchFile& vdex_file : vdex_files) {
+    vdex_file.Unlink();
+  }
+  const int rmdir_result = rmdir(image_dir.c_str());
+  CHECK_EQ(0, rmdir_result);
+}
 
-  // Set inline filter values.
-  compiler_options_->SetInlineDepthLimit(CompilerOptions::kDefaultInlineDepthLimit);
-  compiler_options_->SetInlineMaxCodeUnits(CompilerOptions::kDefaultInlineMaxCodeUnits);
+std::vector<size_t> CompilationHelper::GetImageObjectSectionSizes() {
+  std::vector<size_t> ret;
+  for (ScratchFile& image_file : image_files) {
+    std::unique_ptr<File> file(OS::OpenFileForReading(image_file.GetFilename().c_str()));
+    CHECK(file.get() != nullptr);
+    ImageHeader image_header;
+    CHECK_EQ(file->ReadFully(&image_header, sizeof(image_header)), true);
+    CHECK(image_header.IsValid());
+    ret.push_back(image_header.GetImageSize());
+  }
+  return ret;
+}
 
+void CompilationHelper::Compile(CompilerDriver* driver,
+                                ImageHeader::StorageMode storage_mode) {
   ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
-  const std::vector<const DexFile*>& boot_class_path = class_linker->GetBootClassPath();
-  const size_t num_images = boot_class_path.size();
+  std::vector<const DexFile*> class_path = class_linker->GetBootClassPath();
+
+  for (const std::unique_ptr<const DexFile>& dex_file : extra_dex_files) {
+    {
+      ScopedObjectAccess soa(Thread::Current());
+      // Inject in boot class path so that the compiler driver can see it.
+      class_linker->AppendToBootClassPath(soa.Self(), *dex_file.get());
+    }
+    class_path.push_back(dex_file.get());
+  }
 
   // Enable write for dex2dex.
-  for (const DexFile* dex_file : boot_class_path) {
-    dex_file->EnableWrite();
+  for (const DexFile* dex_file : class_path) {
+    dex_file_locations.push_back(dex_file->GetLocation());
+    if (dex_file->IsReadOnly()) {
+      dex_file->EnableWrite();
+    }
   }
-  // Create a generic location tmp file, to be the base of the .art and .oat temporary files.
-  std::vector<ScratchFile> image_locations;
   {
+    // Create a generic tmp file, to be the base of the .art and .oat temporary files.
     ScratchFile location;
-    for (int i = 0; i < static_cast<int>(num_images); ++i) {
+    for (int i = 0; i < static_cast<int>(class_path.size()); ++i) {
       std::string cur_location(StringPrintf("%s-%d.art", location.GetFilename().c_str(), i));
       image_locations.push_back(ScratchFile(cur_location));
     }
   }
   std::vector<std::string> image_filenames;
-  std::vector<ScratchFile> image_files;
-  std::string image_dir;
   for (ScratchFile& file : image_locations) {
     std::string image_filename(GetSystemImageFilename(file.GetFilename().c_str(), kRuntimeISA));
     image_filenames.push_back(image_filename);
@@ -89,9 +151,7 @@
   }
 
   std::vector<std::string> oat_filenames;
-  std::vector<ScratchFile> oat_files;
   std::vector<std::string> vdex_filenames;
-  std::vector<ScratchFile> vdex_files;
   for (const std::string& image_filename : image_filenames) {
     std::string oat_filename = ReplaceFileExtension(image_filename, "oat");
     oat_files.push_back(ScratchFile(OS::CreateEmptyFile(oat_filename.c_str())));
@@ -101,7 +161,6 @@
     vdex_filenames.push_back(vdex_filename);
   }
 
-  const uintptr_t requested_image_base = ART_BASE_ADDRESS;
   std::unordered_map<const DexFile*, size_t> dex_file_to_oat_index_map;
   std::vector<const char*> oat_filename_vector;
   for (const std::string& file : oat_filenames) {
@@ -112,13 +171,13 @@
     image_filename_vector.push_back(file.c_str());
   }
   size_t image_idx = 0;
-  for (const DexFile* dex_file : boot_class_path) {
+  for (const DexFile* dex_file : class_path) {
     dex_file_to_oat_index_map.emplace(dex_file, image_idx);
     ++image_idx;
   }
   // TODO: compile_pic should be a test argument.
-  std::unique_ptr<ImageWriter> writer(new ImageWriter(*compiler_driver_,
-                                                      requested_image_base,
+  std::unique_ptr<ImageWriter> writer(new ImageWriter(*driver,
+                                                      kRequestedImageBase,
                                                       /*compile_pic*/false,
                                                       /*compile_app_image*/false,
                                                       storage_mode,
@@ -129,13 +188,13 @@
       jobject class_loader = nullptr;
       TimingLogger timings("ImageTest::WriteRead", false, false);
       TimingLogger::ScopedTiming t("CompileAll", &timings);
-      compiler_driver_->SetDexFilesForOatFile(class_linker->GetBootClassPath());
-      compiler_driver_->CompileAll(class_loader, class_linker->GetBootClassPath(), &timings);
+      driver->SetDexFilesForOatFile(class_path);
+      driver->CompileAll(class_loader, class_path, &timings);
 
       t.NewTiming("WriteElf");
       SafeMap<std::string, std::string> key_value_store;
       std::vector<const char*> dex_filename_vector;
-      for (size_t i = 0; i < boot_class_path.size(); ++i) {
+      for (size_t i = 0; i < class_path.size(); ++i) {
         dex_filename_vector.push_back("");
       }
       key_value_store.Put(OatHeader::kBootClassPathKey,
@@ -144,14 +203,13 @@
                               oat_filename_vector,
                               image_filename_vector));
 
-      const std::vector<const DexFile*>& dex_files = class_linker->GetBootClassPath();
       std::vector<std::unique_ptr<ElfWriter>> elf_writers;
       std::vector<std::unique_ptr<OatWriter>> oat_writers;
       for (ScratchFile& oat_file : oat_files) {
-        elf_writers.emplace_back(CreateElfWriterQuick(compiler_driver_->GetInstructionSet(),
-                                                       compiler_driver_->GetInstructionSetFeatures(),
-                                                       &compiler_driver_->GetCompilerOptions(),
-                                                       oat_file.GetFile()));
+        elf_writers.emplace_back(CreateElfWriterQuick(driver->GetInstructionSet(),
+                                                      driver->GetInstructionSetFeatures(),
+                                                      &driver->GetCompilerOptions(),
+                                                      oat_file.GetFile()));
         elf_writers.back()->Start();
         oat_writers.emplace_back(new OatWriter(/*compiling_boot_image*/true, &timings));
       }
@@ -161,7 +219,7 @@
       std::vector<std::unique_ptr<const DexFile>> opened_dex_files;
       // Now that we have finalized key_value_store_, start writing the oat file.
       for (size_t i = 0, size = oat_writers.size(); i != size; ++i) {
-        const DexFile* dex_file = dex_files[i];
+        const DexFile* dex_file = class_path[i];
         rodata.push_back(elf_writers[i]->StartRoData());
         ArrayRef<const uint8_t> raw_dex_file(
             reinterpret_cast<const uint8_t*>(&dex_file->GetHeader()),
@@ -175,8 +233,8 @@
         bool dex_files_ok = oat_writers[i]->WriteAndOpenDexFiles(
             kIsVdexEnabled ? vdex_files[i].GetFile() : oat_files[i].GetFile(),
             rodata.back(),
-            compiler_driver_->GetInstructionSet(),
-            compiler_driver_->GetInstructionSetFeatures(),
+            driver->GetInstructionSet(),
+            driver->GetInstructionSetFeatures(),
             &key_value_store,
             /* verify */ false,           // Dex files may be dex-to-dex-ed, don't verify.
             &cur_opened_dex_files_map,
@@ -197,12 +255,12 @@
       ASSERT_TRUE(image_space_ok);
 
       for (size_t i = 0, size = oat_files.size(); i != size; ++i) {
-        linker::MultiOatRelativePatcher patcher(compiler_driver_->GetInstructionSet(),
-                                                instruction_set_features_.get());
+        linker::MultiOatRelativePatcher patcher(driver->GetInstructionSet(),
+                                                driver->GetInstructionSetFeatures());
         OatWriter* const oat_writer = oat_writers[i].get();
         ElfWriter* const elf_writer = elf_writers[i].get();
-        std::vector<const DexFile*> cur_dex_files(1u, dex_files[i]);
-        oat_writer->PrepareLayout(compiler_driver_.get(), writer.get(), cur_dex_files, &patcher);
+        std::vector<const DexFile*> cur_dex_files(1u, class_path[i]);
+        oat_writer->PrepareLayout(driver, writer.get(), cur_dex_files, &patcher);
         size_t rodata_size = oat_writer->GetOatHeader().GetExecutableOffset();
         size_t text_size = oat_writer->GetOatSize() - rodata_size;
         elf_writer->SetLoadedSectionSizes(rodata_size, text_size, oat_writer->GetBssSize());
@@ -234,9 +292,7 @@
         ASSERT_TRUE(success);
       }
     }
-  }
 
-  {
     bool success_image = writer->Write(kInvalidFd,
                                        image_filename_vector,
                                        oat_filename_vector);
@@ -253,9 +309,39 @@
                                                   << oat_filename;
     }
   }
+}
 
+void ImageTest::Compile(ImageHeader::StorageMode storage_mode,
+                        CompilationHelper& helper,
+                        const std::string& extra_dex,
+                        const std::string& image_class) {
+  if (!image_class.empty()) {
+    image_classes_.insert(image_class);
+  }
+  CreateCompilerDriver(Compiler::kOptimizing, kRuntimeISA, kIsTargetBuild ? 2U : 16U);
+  // Set inline filter values.
+  compiler_options_->SetInlineDepthLimit(CompilerOptions::kDefaultInlineDepthLimit);
+  compiler_options_->SetInlineMaxCodeUnits(CompilerOptions::kDefaultInlineMaxCodeUnits);
+  image_classes_.clear();
+  if (!extra_dex.empty()) {
+    helper.extra_dex_files = OpenTestDexFiles(extra_dex.c_str());
+  }
+  helper.Compile(compiler_driver_.get(), storage_mode);
+  if (!image_class.empty()) {
+    // Make sure the class got initialized.
+    ScopedObjectAccess soa(Thread::Current());
+    ClassLinker* const class_linker = Runtime::Current()->GetClassLinker();
+    mirror::Class* klass = class_linker->FindSystemClass(Thread::Current(), image_class.c_str());
+    EXPECT_TRUE(klass != nullptr);
+    EXPECT_TRUE(klass->IsInitialized());
+  }
+}
+
+void ImageTest::TestWriteRead(ImageHeader::StorageMode storage_mode) {
+  CompilationHelper helper;
+  Compile(storage_mode, /*out*/ helper);
   std::vector<uint64_t> image_file_sizes;
-  for (ScratchFile& image_file : image_files) {
+  for (ScratchFile& image_file : helper.image_files) {
     std::unique_ptr<File> file(OS::OpenFileForReading(image_file.GetFilename().c_str()));
     ASSERT_TRUE(file.get() != nullptr);
     ImageHeader image_header;
@@ -285,8 +371,8 @@
   // Remove the reservation of the memory for use to load the image.
   // Need to do this before we reset the runtime.
   UnreserveImageSpace();
-  writer.reset(nullptr);
 
+  helper.extra_dex_files.clear();
   runtime_.reset();
   java_lang_dex_file_ = nullptr;
 
@@ -294,7 +380,7 @@
 
   RuntimeOptions options;
   std::string image("-Ximage:");
-  image.append(image_locations[0].GetFilename());
+  image.append(helper.image_locations[0].GetFilename());
   options.push_back(std::make_pair(image.c_str(), static_cast<void*>(nullptr)));
   // By default the compiler this creates will not include patch information.
   options.push_back(std::make_pair("-Xnorelocate", nullptr));
@@ -317,17 +403,18 @@
 
   // We loaded the runtime with an explicit image, so it must exist.
   ASSERT_EQ(heap->GetBootImageSpaces().size(), image_file_sizes.size());
-  for (size_t i = 0; i < image_file_sizes.size(); ++i) {
+  for (size_t i = 0; i < helper.dex_file_locations.size(); ++i) {
     std::unique_ptr<const DexFile> dex(
-        LoadExpectSingleDexFile(GetLibCoreDexFileNames()[i].c_str()));
+        LoadExpectSingleDexFile(helper.dex_file_locations[i].c_str()));
+    ASSERT_TRUE(dex != nullptr);
     uint64_t image_file_size = image_file_sizes[i];
     gc::space::ImageSpace* image_space = heap->GetBootImageSpaces()[i];
     ASSERT_TRUE(image_space != nullptr);
     if (storage_mode == ImageHeader::kStorageModeUncompressed) {
       // Uncompressed, image should be smaller than file.
       ASSERT_LE(image_space->GetImageHeader().GetImageSize(), image_file_size);
-    } else {
-      // Compressed, file should be smaller than image.
+    } else if (image_file_size > 16 * KB) {
+      // Compressed, file should be smaller than image. Not really valid for small images.
       ASSERT_LE(image_file_size, image_space->GetImageHeader().GetImageSize());
     }
 
@@ -336,7 +423,7 @@
     uint8_t* image_end = image_space->End();
     if (i == 0) {
       // This check is only valid for image 0.
-      CHECK_EQ(requested_image_base, reinterpret_cast<uintptr_t>(image_begin));
+      CHECK_EQ(kRequestedImageBase, reinterpret_cast<uintptr_t>(image_begin));
     }
     for (size_t j = 0; j < dex->NumClassDefs(); ++j) {
       const DexFile::ClassDef& class_def = dex->GetClassDef(j);
@@ -354,18 +441,6 @@
       EXPECT_TRUE(Monitor::IsValidLockWord(klass->GetLockWord(false)));
     }
   }
-
-  for (ScratchFile& image_file : image_files) {
-    image_file.Unlink();
-  }
-  for (ScratchFile& oat_file : oat_files) {
-    oat_file.Unlink();
-  }
-  for (ScratchFile& vdex_file : vdex_files) {
-    vdex_file.Unlink();
-  }
-  int rmdir_result = rmdir(image_dir.c_str());
-  CHECK_EQ(0, rmdir_result);
 }
 
 TEST_F(ImageTest, WriteReadUncompressed) {
@@ -380,6 +455,35 @@
   TestWriteRead(ImageHeader::kStorageModeLZ4HC);
 }
 
+TEST_F(ImageTest, TestImageLayout) {
+  std::vector<size_t> image_sizes;
+  std::vector<size_t> image_sizes_extra;
+  // Compile multi-image with ImageLayoutA being the last image.
+  {
+    CompilationHelper helper;
+    Compile(ImageHeader::kStorageModeUncompressed, helper, "ImageLayoutA", "LMyClass;");
+    image_sizes = helper.GetImageObjectSectionSizes();
+  }
+  TearDown();
+  runtime_.reset();
+  SetUp();
+  // Compile multi-image with ImageLayoutB being the last image.
+  {
+    CompilationHelper helper;
+    Compile(ImageHeader::kStorageModeUncompressed, helper, "ImageLayoutB", "LMyClass;");
+    image_sizes_extra = helper.GetImageObjectSectionSizes();
+  }
+  // Make sure that the new stuff in the clinit in ImageLayoutB is in the last image and not in the
+  // first two images.
+  ASSERT_EQ(image_sizes.size(), image_sizes.size());
+  // Sizes of the images should be the same. These sizes are for the whole image unrounded.
+  for (size_t i = 0; i < image_sizes.size() - 1; ++i) {
+    EXPECT_EQ(image_sizes[i], image_sizes_extra[i]);
+  }
+  // Last image should be larger since it has a hash map and a string.
+  EXPECT_LT(image_sizes.back(), image_sizes_extra.back());
+}
+
 TEST_F(ImageTest, ImageHeaderIsValid) {
     uint32_t image_begin = ART_BASE_ADDRESS;
     uint32_t image_size_ = 16 * KB;
diff --git a/compiler/image_writer.cc b/compiler/image_writer.cc
index cdb57a9..ad881b7 100644
--- a/compiler/image_writer.cc
+++ b/compiler/image_writer.cc
@@ -389,7 +389,6 @@
   DCHECK(!IsImageBinSlotAssigned(object));
 
   // Before we stomp over the lock word, save the hash code for later.
-  Monitor::Deflate(Thread::Current(), object);;
   LockWord lw(object->GetLockWord(false));
   switch (lw.GetState()) {
     case LockWord::kFatLocked: {
@@ -490,7 +489,7 @@
   pointer_arrays_.emplace(arr, kBinArtMethodClean);
 }
 
-void ImageWriter::AssignImageBinSlot(mirror::Object* object) {
+void ImageWriter::AssignImageBinSlot(mirror::Object* object, size_t oat_index) {
   DCHECK(object != nullptr);
   size_t object_size = object->SizeOf();
 
@@ -593,7 +592,10 @@
     // else bin = kBinRegular
   }
 
-  size_t oat_index = GetOatIndex(object);
+  // Assign the oat index too.
+  DCHECK(oat_index_map_.find(object) == oat_index_map_.end());
+  oat_index_map_.emplace(object, oat_index);
+
   ImageInfo& image_info = GetImageInfo(oat_index);
 
   size_t offset_delta = RoundUp(object_size, kObjectAlignment);  // 64-bit alignment
@@ -974,39 +976,6 @@
   return nullptr;
 }
 
-void ImageWriter::CalculateObjectBinSlots(Object* obj) {
-  DCHECK(obj != nullptr);
-  // if it is a string, we want to intern it if its not interned.
-  if (obj->GetClass()->IsStringClass()) {
-    size_t oat_index = GetOatIndex(obj);
-    ImageInfo& image_info = GetImageInfo(oat_index);
-
-    // we must be an interned string that was forward referenced and already assigned
-    if (IsImageBinSlotAssigned(obj)) {
-      DCHECK_EQ(obj, FindInternedString(obj->AsString()));
-      return;
-    }
-    // Need to check if the string is already interned in another image info so that we don't have
-    // the intern tables of two different images contain the same string.
-    mirror::String* interned = FindInternedString(obj->AsString());
-    if (interned == nullptr) {
-      // Not in another image space, insert to our table.
-      interned = image_info.intern_table_->InternStrongImageString(obj->AsString());
-    }
-    if (obj != interned) {
-      if (!IsImageBinSlotAssigned(interned)) {
-        // interned obj is after us, allocate its location early
-        AssignImageBinSlot(interned);
-      }
-      // point those looking for this object to the interned version.
-      SetImageBinSlot(obj, GetImageBinSlot(interned));
-      return;
-    }
-    // else (obj == interned), nothing to do but fall through to the normal case
-  }
-
-  AssignImageBinSlot(obj);
-}
 
 ObjectArray<Object>* ImageWriter::CreateImageRoots(size_t oat_index) const {
   Runtime* runtime = Runtime::Current();
@@ -1092,61 +1061,33 @@
   return image_roots.Get();
 }
 
-// Walk instance fields of the given Class. Separate function to allow recursion on the super
-// class.
-void ImageWriter::WalkInstanceFields(mirror::Object* obj, mirror::Class* klass) {
-  // Visit fields of parent classes first.
-  StackHandleScope<1> hs(Thread::Current());
-  Handle<mirror::Class> h_class(hs.NewHandle(klass));
-  mirror::Class* super = h_class->GetSuperClass();
-  if (super != nullptr) {
-    WalkInstanceFields(obj, super);
+mirror::Object* ImageWriter::TryAssignBinSlot(WorkStack& work_stack,
+                                              mirror::Object* obj,
+                                              size_t oat_index) {
+  if (obj == nullptr || IsInBootImage(obj)) {
+    // Object is null or already in the image, there is no work to do.
+    return obj;
   }
-  //
-  size_t num_reference_fields = h_class->NumReferenceInstanceFields();
-  MemberOffset field_offset = h_class->GetFirstReferenceInstanceFieldOffset();
-  for (size_t i = 0; i < num_reference_fields; ++i) {
-    mirror::Object* value = obj->GetFieldObject<mirror::Object>(field_offset);
-    if (value != nullptr) {
-      WalkFieldsInOrder(value);
-    }
-    field_offset = MemberOffset(field_offset.Uint32Value() +
-                                sizeof(mirror::HeapReference<mirror::Object>));
-  }
-}
-
-// For an unvisited object, visit it then all its children found via fields.
-void ImageWriter::WalkFieldsInOrder(mirror::Object* obj) {
-  if (IsInBootImage(obj)) {
-    // Object is in the image, don't need to fix it up.
-    return;
-  }
-  // Use our own visitor routine (instead of GC visitor) to get better locality between
-  // an object and its fields
   if (!IsImageBinSlotAssigned(obj)) {
-    // Walk instance fields of all objects
-    StackHandleScope<2> hs(Thread::Current());
-    Handle<mirror::Object> h_obj(hs.NewHandle(obj));
-    Handle<mirror::Class> klass(hs.NewHandle(obj->GetClass()));
-    // visit the object itself.
-    CalculateObjectBinSlots(h_obj.Get());
-    WalkInstanceFields(h_obj.Get(), klass.Get());
-    // Walk static fields of a Class.
-    if (h_obj->IsClass()) {
-      size_t num_reference_static_fields = klass->NumReferenceStaticFields();
-      MemberOffset field_offset = klass->GetFirstReferenceStaticFieldOffset(target_ptr_size_);
-      for (size_t i = 0; i < num_reference_static_fields; ++i) {
-        mirror::Object* value = h_obj->GetFieldObject<mirror::Object>(field_offset);
-        if (value != nullptr) {
-          WalkFieldsInOrder(value);
-        }
-        field_offset = MemberOffset(field_offset.Uint32Value() +
-                                    sizeof(mirror::HeapReference<mirror::Object>));
+    // We want to intern all strings but also assign offsets for the source string. Since the
+    // pruning phase has already happened, if we intern a string to one in the image we still
+    // end up copying an unreachable string.
+    if (obj->IsString()) {
+      // Need to check if the string is already interned in another image info so that we don't have
+      // the intern tables of two different images contain the same string.
+      mirror::String* interned = FindInternedString(obj->AsString());
+      if (interned == nullptr) {
+        // Not in another image space, insert to our table.
+        interned = GetImageInfo(oat_index).intern_table_->InternStrongImageString(obj->AsString());
+        DCHECK_EQ(interned, obj);
       }
+    } else if (obj->IsDexCache()) {
+      oat_index = GetOatIndexForDexCache(obj->AsDexCache());
+    } else if (obj->IsClass()) {
       // Visit and assign offsets for fields and field arrays.
-      auto* as_klass = h_obj->AsClass();
+      mirror::Class* as_klass = obj->AsClass();
       mirror::DexCache* dex_cache = as_klass->GetDexCache();
-      DCHECK_NE(klass->GetStatus(), mirror::Class::kStatusError);
+      DCHECK_NE(as_klass->GetStatus(), mirror::Class::kStatusError);
       if (compile_app_image_) {
         // Extra sanity, no boot loader classes should be left!
         CHECK(!IsBootClassLoaderClass(as_klass)) << PrettyClass(as_klass);
@@ -1154,14 +1095,14 @@
       LengthPrefixedArray<ArtField>* fields[] = {
           as_klass->GetSFieldsPtr(), as_klass->GetIFieldsPtr(),
       };
-      size_t oat_index = GetOatIndexForDexCache(dex_cache);
+      // Overwrite the oat index value since the class' dex cache is more accurate of where it
+      // belongs.
+      oat_index = GetOatIndexForDexCache(dex_cache);
       ImageInfo& image_info = GetImageInfo(oat_index);
       {
-        // Note: This table is only accessed from the image writer, so the lock is technically
-        // unnecessary.
-        WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
-        // Insert in the class table for this iamge.
-        image_info.class_table_->Insert(as_klass);
+        // Note: This table is only accessed from the image writer, avoid locking to prevent lock
+        // order violations from root visiting.
+        image_info.class_table_->InsertWithoutLocks(as_klass);
       }
       for (LengthPrefixedArray<ArtField>* cur_fields : fields) {
         // Total array length including header.
@@ -1251,26 +1192,26 @@
         ImTable* imt = as_klass->GetImt(target_ptr_size_);
         TryAssignImTableOffset(imt, oat_index);
       }
-    } else if (h_obj->IsObjectArray()) {
-      // Walk elements of an object array.
-      int32_t length = h_obj->AsObjectArray<mirror::Object>()->GetLength();
-      for (int32_t i = 0; i < length; i++) {
-        mirror::ObjectArray<mirror::Object>* obj_array = h_obj->AsObjectArray<mirror::Object>();
-        mirror::Object* value = obj_array->Get(i);
-        if (value != nullptr) {
-          WalkFieldsInOrder(value);
-        }
-      }
-    } else if (h_obj->IsClassLoader()) {
+    } else if (obj->IsClassLoader()) {
       // Register the class loader if it has a class table.
       // The fake boot class loader should not get registered and we should end up with only one
       // class loader.
-      mirror::ClassLoader* class_loader = h_obj->AsClassLoader();
+      mirror::ClassLoader* class_loader = obj->AsClassLoader();
       if (class_loader->GetClassTable() != nullptr) {
         class_loaders_.insert(class_loader);
       }
     }
+    AssignImageBinSlot(obj, oat_index);
+    work_stack.emplace(obj, oat_index);
   }
+  if (obj->IsString()) {
+    // Always return the interned string if there exists one.
+    mirror::String* interned = FindInternedString(obj->AsString());
+    if (interned != nullptr) {
+      return interned;
+    }
+  }
+  return obj;
 }
 
 bool ImageWriter::NativeRelocationAssigned(void* ptr) const {
@@ -1327,10 +1268,16 @@
   offset += ArtMethod::Size(target_ptr_size_);
 }
 
-void ImageWriter::WalkFieldsCallback(mirror::Object* obj, void* arg) {
+void ImageWriter::EnsureBinSlotAssignedCallback(mirror::Object* obj, void* arg) {
   ImageWriter* writer = reinterpret_cast<ImageWriter*>(arg);
   DCHECK(writer != nullptr);
-  writer->WalkFieldsInOrder(obj);
+  if (!Runtime::Current()->GetHeap()->ObjectIsInBootImageSpace(obj)) {
+    CHECK(writer->IsImageBinSlotAssigned(obj)) << PrettyTypeOf(obj) << " " << obj;
+  }
+}
+
+void ImageWriter::DeflateMonitorCallback(mirror::Object* obj, void* arg ATTRIBUTE_UNUSED) {
+  Monitor::Deflate(Thread::Current(), obj);
 }
 
 void ImageWriter::UnbinObjectsIntoOffsetCallback(mirror::Object* obj, void* arg) {
@@ -1354,6 +1301,88 @@
   AssignImageOffset(obj, bin_slot);
 }
 
+class ImageWriter::VisitReferencesVisitor {
+ public:
+  VisitReferencesVisitor(ImageWriter* image_writer, WorkStack* work_stack, size_t oat_index)
+      : image_writer_(image_writer), work_stack_(work_stack), oat_index_(oat_index) {}
+
+  // Fix up separately since we also need to fix up method entrypoints.
+  ALWAYS_INLINE void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    if (!root->IsNull()) {
+      VisitRoot(root);
+    }
+  }
+
+  ALWAYS_INLINE void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    root->Assign(VisitReference(root->AsMirrorPtr()));
+  }
+
+  ALWAYS_INLINE void operator() (mirror::Object* obj,
+                                 MemberOffset offset,
+                                 bool is_static ATTRIBUTE_UNUSED) const
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    mirror::Object* ref =
+        obj->GetFieldObject<mirror::Object, kVerifyNone, kWithoutReadBarrier>(offset);
+    obj->SetFieldObject</*kTransactionActive*/false>(offset, VisitReference(ref));
+  }
+
+  ALWAYS_INLINE void operator() (mirror::Class* klass ATTRIBUTE_UNUSED,
+                                 mirror::Reference* ref) const
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    ref->SetReferent</*kTransactionActive*/false>(
+        VisitReference(ref->GetReferent<kWithoutReadBarrier>()));
+  }
+
+ private:
+  mirror::Object* VisitReference(mirror::Object* ref) const REQUIRES_SHARED(Locks::mutator_lock_) {
+    return image_writer_->TryAssignBinSlot(*work_stack_, ref, oat_index_);
+  }
+
+  ImageWriter* const image_writer_;
+  WorkStack* const work_stack_;
+  const size_t oat_index_;
+};
+
+class ImageWriter::GetRootsVisitor : public RootVisitor  {
+ public:
+  explicit GetRootsVisitor(std::vector<mirror::Object*>* roots) : roots_(roots) {}
+
+  void VisitRoots(mirror::Object*** roots,
+                  size_t count,
+                  const RootInfo& info ATTRIBUTE_UNUSED) OVERRIDE
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    for (size_t i = 0; i < count; ++i) {
+      roots_->push_back(*roots[i]);
+    }
+  }
+
+  void VisitRoots(mirror::CompressedReference<mirror::Object>** roots,
+                  size_t count,
+                  const RootInfo& info ATTRIBUTE_UNUSED) OVERRIDE
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    for (size_t i = 0; i < count; ++i) {
+      roots_->push_back(roots[i]->AsMirrorPtr());
+    }
+  }
+
+ private:
+  std::vector<mirror::Object*>* const roots_;
+};
+
+void ImageWriter::ProcessWorkStack(WorkStack* work_stack) {
+  while (!work_stack->empty()) {
+    std::pair<mirror::Object*, size_t> pair(work_stack->top());
+    work_stack->pop();
+    VisitReferencesVisitor visitor(this, work_stack, /*oat_index*/ pair.second);
+    // Walk references and assign bin slots for them.
+    pair.first->VisitReferences</*kVisitNativeRoots*/true, kVerifyNone, kWithoutReadBarrier>(
+        visitor,
+        visitor);
+  }
+}
+
 void ImageWriter::CalculateNewObjectOffsets() {
   Thread* const self = Thread::Current();
   StackHandleScopeCollection handles(self);
@@ -1362,8 +1391,8 @@
     image_roots.push_back(handles.NewHandle(CreateImageRoots(i)));
   }
 
-  auto* runtime = Runtime::Current();
-  auto* heap = runtime->GetHeap();
+  Runtime* const runtime = Runtime::Current();
+  gc::Heap* const heap = runtime->GetHeap();
 
   // Leave space for the header, but do not write it yet, we need to
   // know where image_roots is going to end up
@@ -1392,8 +1421,64 @@
     }
   }
 
-  // Clear any pre-existing monitors which may have been in the monitor words, assign bin slots.
-  heap->VisitObjects(WalkFieldsCallback, this);
+  // Deflate monitors before we visit roots since deflating acquires the monitor lock. Acquiring
+  // this lock while holding other locks may cause lock order violations.
+  heap->VisitObjects(DeflateMonitorCallback, this);
+
+  // Work list of <object, oat_index> for objects. Everything on the stack must already be
+  // assigned a bin slot.
+  WorkStack work_stack;
+
+  // Special case interned strings to put them in the image they are likely to be resolved from.
+  for (const DexFile* dex_file : compiler_driver_.GetDexFilesForOatFile()) {
+    auto it = dex_file_oat_index_map_.find(dex_file);
+    DCHECK(it != dex_file_oat_index_map_.end()) << dex_file->GetLocation();
+    const size_t oat_index = it->second;
+    InternTable* const intern_table = runtime->GetInternTable();
+    for (size_t i = 0, count = dex_file->NumStringIds(); i < count; ++i) {
+      uint32_t utf16_length;
+      const char* utf8_data = dex_file->StringDataAndUtf16LengthByIdx(i, &utf16_length);
+      mirror::String* string = intern_table->LookupStrong(self, utf16_length, utf8_data);
+      TryAssignBinSlot(work_stack, string, oat_index);
+    }
+  }
+
+  // Get the GC roots and then visit them separately to avoid lock violations since the root visitor
+  // visits roots while holding various locks.
+  {
+    std::vector<mirror::Object*> roots;
+    GetRootsVisitor root_visitor(&roots);
+    runtime->VisitRoots(&root_visitor);
+    for (mirror::Object* obj : roots) {
+      TryAssignBinSlot(work_stack, obj, GetDefaultOatIndex());
+    }
+  }
+  ProcessWorkStack(&work_stack);
+
+  // For app images, there may be objects that are only held live by the by the boot image. One
+  // example is finalizer references. Forward these objects so that EnsureBinSlotAssignedCallback
+  // does not fail any checks. TODO: We should probably avoid copying these objects.
+  if (compile_app_image_) {
+    for (gc::space::ImageSpace* space : heap->GetBootImageSpaces()) {
+      DCHECK(space->IsImageSpace());
+      gc::accounting::ContinuousSpaceBitmap* live_bitmap = space->GetLiveBitmap();
+      live_bitmap->VisitMarkedRange(reinterpret_cast<uintptr_t>(space->Begin()),
+                                    reinterpret_cast<uintptr_t>(space->Limit()),
+                                    [this, &work_stack](mirror::Object* obj)
+          REQUIRES_SHARED(Locks::mutator_lock_) {
+        VisitReferencesVisitor visitor(this, &work_stack, GetDefaultOatIndex());
+        // Visit all references and try to assign bin slots for them (calls TryAssignBinSlot).
+        obj->VisitReferences</*kVisitNativeRoots*/true, kVerifyNone, kWithoutReadBarrier>(
+            visitor,
+            visitor);
+      });
+    }
+    // Process the work stack in case anything was added by TryAssignBinSlot.
+    ProcessWorkStack(&work_stack);
+  }
+
+  // Verify that all objects have assigned image bin slots.
+  heap->VisitObjects(EnsureBinSlotAssignedCallback, this);
 
   // Calculate size of the dex cache arrays slot and prepare offsets.
   PrepareDexCacheArraySlots();
@@ -2281,25 +2366,21 @@
 }
 
 size_t ImageWriter::GetOatIndex(mirror::Object* obj) const {
-  if (compile_app_image_) {
+  if (!IsMultiImage()) {
     return GetDefaultOatIndex();
-  } else {
-    mirror::DexCache* dex_cache =
-        obj->IsDexCache() ? obj->AsDexCache()
-                          : obj->IsClass() ? obj->AsClass()->GetDexCache()
-                                           : obj->GetClass()->GetDexCache();
-    return GetOatIndexForDexCache(dex_cache);
   }
+  auto it = oat_index_map_.find(obj);
+  DCHECK(it != oat_index_map_.end());
+  return it->second;
 }
 
 size_t ImageWriter::GetOatIndexForDexFile(const DexFile* dex_file) const {
-  if (compile_app_image_) {
+  if (!IsMultiImage()) {
     return GetDefaultOatIndex();
-  } else {
-    auto it = dex_file_oat_index_map_.find(dex_file);
-    DCHECK(it != dex_file_oat_index_map_.end()) << dex_file->GetLocation();
-    return it->second;
   }
+  auto it = dex_file_oat_index_map_.find(dex_file);
+  DCHECK(it != dex_file_oat_index_map_.end()) << dex_file->GetLocation();
+  return it->second;
 }
 
 size_t ImageWriter::GetOatIndexForDexCache(mirror::DexCache* dex_cache) const {
diff --git a/compiler/image_writer.h b/compiler/image_writer.h
index 76749cf..acd1681 100644
--- a/compiler/image_writer.h
+++ b/compiler/image_writer.h
@@ -23,6 +23,7 @@
 #include <cstddef>
 #include <memory>
 #include <set>
+#include <stack>
 #include <string>
 #include <ostream>
 
@@ -144,6 +145,8 @@
   void UpdateOatFileHeader(size_t oat_index, const OatHeader& oat_header);
 
  private:
+  using WorkStack = std::stack<std::pair<mirror::Object*, size_t>>;
+
   bool AllocMemory();
 
   // Mark the objects defined in this space in the given live bitmap.
@@ -321,7 +324,10 @@
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   void PrepareDexCacheArraySlots() REQUIRES_SHARED(Locks::mutator_lock_);
-  void AssignImageBinSlot(mirror::Object* object) REQUIRES_SHARED(Locks::mutator_lock_);
+  void AssignImageBinSlot(mirror::Object* object, size_t oat_index)
+      REQUIRES_SHARED(Locks::mutator_lock_);
+  mirror::Object* TryAssignBinSlot(WorkStack& work_stack, mirror::Object* obj, size_t oat_index)
+      REQUIRES_SHARED(Locks::mutator_lock_);
   void SetImageBinSlot(mirror::Object* object, BinSlot bin_slot)
       REQUIRES_SHARED(Locks::mutator_lock_);
   bool IsImageBinSlotAssigned(mirror::Object* object) const
@@ -378,6 +384,8 @@
   // Lays out where the image objects will be at runtime.
   void CalculateNewObjectOffsets()
       REQUIRES_SHARED(Locks::mutator_lock_);
+  void ProcessWorkStack(WorkStack* work_stack)
+      REQUIRES_SHARED(Locks::mutator_lock_);
   void CreateHeader(size_t oat_index)
       REQUIRES_SHARED(Locks::mutator_lock_);
   mirror::ObjectArray<mirror::Object>* CreateImageRoots(size_t oat_index) const
@@ -387,11 +395,9 @@
   void UnbinObjectsIntoOffset(mirror::Object* obj)
       REQUIRES_SHARED(Locks::mutator_lock_);
 
-  void WalkInstanceFields(mirror::Object* obj, mirror::Class* klass)
+  static void EnsureBinSlotAssignedCallback(mirror::Object* obj, void* arg)
       REQUIRES_SHARED(Locks::mutator_lock_);
-  void WalkFieldsInOrder(mirror::Object* obj)
-      REQUIRES_SHARED(Locks::mutator_lock_);
-  static void WalkFieldsCallback(mirror::Object* obj, void* arg)
+  static void DeflateMonitorCallback(mirror::Object* obj, void* arg)
       REQUIRES_SHARED(Locks::mutator_lock_);
   static void UnbinObjectsIntoOffsetCallback(mirror::Object* obj, void* arg)
       REQUIRES_SHARED(Locks::mutator_lock_);
@@ -461,6 +467,10 @@
                                   std::unordered_set<mirror::Class*>* visited)
       REQUIRES_SHARED(Locks::mutator_lock_);
 
+  bool IsMultiImage() const {
+    return image_infos_.size() > 1;
+  }
+
   static Bin BinTypeForNativeRelocationType(NativeObjectRelocationType type);
 
   uintptr_t NativeOffsetInImage(void* obj) REQUIRES_SHARED(Locks::mutator_lock_);
@@ -519,6 +529,9 @@
   // forwarding addresses as well as copying over hash codes.
   std::unordered_map<mirror::Object*, uint32_t> saved_hashcode_map_;
 
+  // Oat index map for objects.
+  std::unordered_map<mirror::Object*, uint32_t> oat_index_map_;
+
   // Boolean flags.
   const bool compile_pic_;
   const bool compile_app_image_;
@@ -573,8 +586,10 @@
   friend class FixupClassVisitor;
   friend class FixupRootVisitor;
   friend class FixupVisitor;
+  class GetRootsVisitor;
   friend class NativeLocationVisitor;
   friend class NonImageClassesVisitor;
+  class VisitReferencesVisitor;
   DISALLOW_COPY_AND_ASSIGN(ImageWriter);
 };
 
diff --git a/runtime/class_linker.h b/runtime/class_linker.h
index 0a46e2e..954af76 100644
--- a/runtime/class_linker.h
+++ b/runtime/class_linker.h
@@ -1172,6 +1172,7 @@
   PointerSize image_pointer_size_;
 
   class FindVirtualMethodHolderVisitor;
+  friend struct CompilationHelper;  // For Compile in ImageTest.
   friend class ImageDumper;  // for DexLock
   friend class ImageWriter;  // for GetClassRoots
   friend class JniCompilerTest;  // for GetRuntimeQuickGenericJniStub
diff --git a/runtime/class_table.cc b/runtime/class_table.cc
index 55ff73d..0600876 100644
--- a/runtime/class_table.cc
+++ b/runtime/class_table.cc
@@ -113,6 +113,10 @@
   classes_.back().Insert(GcRoot<mirror::Class>(klass));
 }
 
+void ClassTable::InsertWithoutLocks(mirror::Class* klass) {
+  classes_.back().Insert(GcRoot<mirror::Class>(klass));
+}
+
 void ClassTable::InsertWithHash(mirror::Class* klass, size_t hash) {
   WriterMutexLock mu(Thread::Current(), lock_);
   classes_.back().InsertWithHash(GcRoot<mirror::Class>(klass), hash);
diff --git a/runtime/class_table.h b/runtime/class_table.h
index 66c241f..8c91806 100644
--- a/runtime/class_table.h
+++ b/runtime/class_table.h
@@ -163,6 +163,8 @@
   }
 
  private:
+  void InsertWithoutLocks(mirror::Class* klass) NO_THREAD_SAFETY_ANALYSIS;
+
   // Lock to guard inserting and removing.
   mutable ReaderWriterMutex lock_;
   // We have a vector to help prevent dirty pages after the zygote forks by calling FreezeSnapshot.
@@ -171,6 +173,8 @@
   // loader which may not be owned by the class loader must be held strongly live. Also dex caches
   // are held live to prevent them being unloading once they have classes in them.
   std::vector<GcRoot<mirror::Object>> strong_roots_ GUARDED_BY(lock_);
+
+  friend class ImageWriter;  // for InsertWithoutLocks.
 };
 
 }  // namespace art
diff --git a/runtime/common_runtime_test.h b/runtime/common_runtime_test.h
index 2376e6a..a7948e4 100644
--- a/runtime/common_runtime_test.h
+++ b/runtime/common_runtime_test.h
@@ -119,8 +119,7 @@
 
   std::string GetTestDexFileName(const char* name) const;
 
-  std::vector<std::unique_ptr<const DexFile>> OpenTestDexFiles(const char* name)
-      REQUIRES_SHARED(Locks::mutator_lock_);
+  std::vector<std::unique_ptr<const DexFile>> OpenTestDexFiles(const char* name);
 
   std::unique_ptr<const DexFile> OpenTestDexFile(const char* name)
       REQUIRES_SHARED(Locks::mutator_lock_);
diff --git a/test/ImageLayoutA/ImageLayoutA.java b/test/ImageLayoutA/ImageLayoutA.java
new file mode 100644
index 0000000..0784ec2
--- /dev/null
+++ b/test/ImageLayoutA/ImageLayoutA.java
@@ -0,0 +1,21 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+import java.util.HashMap;
+
+class MyClass {
+    static int i = 123;
+}
diff --git a/test/ImageLayoutB/ImageLayoutB.java b/test/ImageLayoutB/ImageLayoutB.java
new file mode 100644
index 0000000..a21c5e2
--- /dev/null
+++ b/test/ImageLayoutB/ImageLayoutB.java
@@ -0,0 +1,25 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+import java.util.HashMap;
+
+class MyClass {
+    public static String string = "ASDF_UNIQUE_STRING";
+    public static HashMap<String, String> map = new HashMap<String, String>();
+    static {
+        map.put("KEY_FOR_HASH_MAP", "VALUE_FOR_HASH_MAP");
+    }
+}