Smarter image layout

Put strings in the dex file that resolves them.

Depth first traversal with overrides for class and dex cache. The
work list keeps track of what oat_index with each pushed item. This
means the static fields of a class will usually be in the same image.

Added layout test to image_test to make sure things are somewhat
reasonably attributed.

Bug: 28640955

Test: test-art-host

(cherry picked from commit 4e9c4e746617bad6a012d799d2f5cf9e01d24ea2)

Change-Id: I67a536c33aeed603b252d8e0f75622c9efbf2559
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);
 };