Multi threaded hashed deduplication during compilation.

Moved deduplication to be in the compiler driver instead of oat
writer. This enables deduplication to be performed on multiple
threads. Also added a hash function to avoid excessive comparison
of byte arrays.

Improvements:
Before (alloats host):
real	1m6.967s
user	4m22.940s
sys	1m22.610s

Thinkfree.apk (target mako):
0m23.74s real     0m50.95s user     0m9.50s system
0m24.62s real     0m50.61s user     0m10.07s system
0m24.22s real     0m51.44s user     0m10.09s system
0m23.70s real     0m51.05s user     0m9.97s system
0m23.50s real     0m50.74s user     0m10.63s system

After (alloats host):
real	1m5.705s
user	4m44.030s
sys	1m29.990s

Thinkfree.apk (target mako):
0m23.32s real     0m51.38s user     0m10.00s system
0m23.49s real     0m51.20s user     0m9.80s system
0m23.18s real     0m50.80s user     0m9.77s system
0m23.52s real     0m51.22s user     0m10.02s system
0m23.50s real     0m51.55s user     0m9.46s system

Bug: 10552630

Change-Id: Ia6d06a747b86b0bfc4473b3cd68f8ce1a1c7eb22

16 files changed, 317 insertions, 86 deletions

diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index a150f06..4c658a2 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -23,6 +23,7 @@ TEST_COMMON_SRC_FILES := \
 	compiler/jni/jni_compiler_test.cc \
 	compiler/oat_test.cc \
 	compiler/output_stream_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 \
diff --git a/compiler/Android.mk b/compiler/Android.mk
index 8eb8db7..66ff461 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -19,6 +19,7 @@ LOCAL_PATH := $(call my-dir)
 include art/build/Android.common.mk
 
 LIBART_COMPILER_SRC_FILES := \
+	compiled_method.cc \
 	dex/local_value_numbering.cc \
 	dex/arena_allocator.cc \
 	dex/arena_bit_vector.cc \
diff --git a/runtime/compiled_method.cc b/compiler/compiled_method.cc
index 4631cb5..29ff390 100644
--- a/runtime/compiled_method.cc
+++ b/compiler/compiled_method.cc
@@ -15,26 +15,35 @@
  */
 
 #include "compiled_method.h"
+#include "driver/compiler_driver.h"
 
 namespace art {
 
-CompiledCode::CompiledCode(InstructionSet instruction_set, const std::vector<uint8_t>& code)
-    : instruction_set_(instruction_set), code_(code) {
-  CHECK_NE(code.size(), 0U);
+CompiledCode::CompiledCode(CompilerDriver* compiler_driver, InstructionSet instruction_set,
+                           const std::vector<uint8_t>& code)
+    : compiler_driver_(compiler_driver), instruction_set_(instruction_set), code_(nullptr) {
+  SetCode(code);
 }
 
-CompiledCode::CompiledCode(InstructionSet instruction_set,
-                           const std::string& elf_object,
-                           const std::string& symbol)
-    : instruction_set_(instruction_set), symbol_(symbol) {
+CompiledCode::CompiledCode(CompilerDriver* compiler_driver, InstructionSet instruction_set,
+                           const std::string& elf_object, const std::string& symbol)
+    : compiler_driver_(compiler_driver), instruction_set_(instruction_set), symbol_(symbol) {
   CHECK_NE(elf_object.size(), 0U);
   CHECK_NE(symbol.size(), 0U);
+  std::vector<uint8_t> temp_code(elf_object.size());
+  for (size_t i = 0; i < elf_object.size(); ++i) {
+    temp_code[i] = elf_object[i];
+  }
   // TODO: we shouldn't just shove ELF objects in as "code" but
   // change to have different kinds of compiled methods.  This is
   // being deferred until we work on hybrid execution or at least
   // until we work on batch compilation.
-  code_.resize(elf_object.size());
-  memcpy(&code_[0], &elf_object[0], elf_object.size());
+  SetCode(temp_code);
+}
+
+void CompiledCode::SetCode(const std::vector<uint8_t>& code) {
+  CHECK(!code.empty());
+  code_ = compiler_driver_->DeduplicateCode(code);
 }
 
 uint32_t CompiledCode::AlignCode(uint32_t offset) const {
@@ -107,7 +116,8 @@ void CompiledCode::AddOatdataOffsetToCompliledCodeOffset(uint32_t offset) {
 }
 #endif
 
-CompiledMethod::CompiledMethod(InstructionSet instruction_set,
+CompiledMethod::CompiledMethod(CompilerDriver& driver,
+                               InstructionSet instruction_set,
                                const std::vector<uint8_t>& code,
                                const size_t frame_size_in_bytes,
                                const uint32_t core_spill_mask,
@@ -115,19 +125,46 @@ CompiledMethod::CompiledMethod(InstructionSet instruction_set,
                                const std::vector<uint8_t>& mapping_table,
                                const std::vector<uint8_t>& vmap_table,
                                const std::vector<uint8_t>& native_gc_map)
-    : CompiledCode(instruction_set, code), frame_size_in_bytes_(frame_size_in_bytes),
+    : CompiledCode(&driver, instruction_set, code), frame_size_in_bytes_(frame_size_in_bytes),
       core_spill_mask_(core_spill_mask), fp_spill_mask_(fp_spill_mask),
-      mapping_table_(mapping_table), vmap_table_(vmap_table),
-      gc_map_(native_gc_map) {
+  mapping_table_(driver.DeduplicateMappingTable(mapping_table)),
+  vmap_table_(driver.DeduplicateVMapTable(vmap_table)),
+  gc_map_(driver.DeduplicateGCMap(native_gc_map)) {
 }
 
-CompiledMethod::CompiledMethod(InstructionSet instruction_set,
+CompiledMethod::CompiledMethod(CompilerDriver& driver,
+                               InstructionSet instruction_set,
                                const std::vector<uint8_t>& code,
                                const size_t frame_size_in_bytes,
                                const uint32_t core_spill_mask,
                                const uint32_t fp_spill_mask)
-    : CompiledCode(instruction_set, code),
+    : CompiledCode(&driver, instruction_set, code),
       frame_size_in_bytes_(frame_size_in_bytes),
-      core_spill_mask_(core_spill_mask), fp_spill_mask_(fp_spill_mask) {}
+      core_spill_mask_(core_spill_mask), fp_spill_mask_(fp_spill_mask) {
+  mapping_table_ = driver.DeduplicateMappingTable(std::vector<uint8_t>());
+  vmap_table_ = driver.DeduplicateVMapTable(std::vector<uint8_t>());
+  gc_map_ = driver.DeduplicateGCMap(std::vector<uint8_t>());
+}
+
+// Constructs a CompiledMethod for the Portable compiler.
+CompiledMethod::CompiledMethod(CompilerDriver& driver, InstructionSet instruction_set,
+                               const std::string& code, const std::vector<uint8_t>& gc_map,
+                               const std::string& symbol)
+    : CompiledCode(&driver, instruction_set, code, symbol),
+      frame_size_in_bytes_(kStackAlignment), core_spill_mask_(0),
+      fp_spill_mask_(0), gc_map_(driver.DeduplicateGCMap(gc_map)) {
+  mapping_table_ = driver.DeduplicateMappingTable(std::vector<uint8_t>());
+  vmap_table_ = driver.DeduplicateVMapTable(std::vector<uint8_t>());
+}
+
+CompiledMethod::CompiledMethod(CompilerDriver& driver, InstructionSet instruction_set,
+                               const std::string& code, const std::string& symbol)
+    : CompiledCode(&driver, instruction_set, code, symbol),
+      frame_size_in_bytes_(kStackAlignment), core_spill_mask_(0),
+      fp_spill_mask_(0) {
+  mapping_table_ = driver.DeduplicateMappingTable(std::vector<uint8_t>());
+  vmap_table_ = driver.DeduplicateVMapTable(std::vector<uint8_t>());
+  gc_map_ = driver.DeduplicateGCMap(std::vector<uint8_t>());
+}
 
 }  // namespace art
diff --git a/runtime/compiled_method.h b/compiler/compiled_method.h
index b3bb20f..e4fedf1 100644
--- a/runtime/compiled_method.h
+++ b/compiler/compiled_method.h
@@ -14,8 +14,8 @@
  * limitations under the License.
  */
 
-#ifndef ART_RUNTIME_COMPILED_METHOD_H_
-#define ART_RUNTIME_COMPILED_METHOD_H_
+#ifndef ART_COMPILER_COMPILED_METHOD_H_
+#define ART_COMPILER_COMPILED_METHOD_H_
 
 #include <string>
 #include <vector>
@@ -30,28 +30,27 @@ namespace llvm {
 
 namespace art {
 
+class CompilerDriver;
+
 class CompiledCode {
  public:
   // For Quick to supply an code blob
-  CompiledCode(InstructionSet instruction_set, const std::vector<uint8_t>& code);
+  CompiledCode(CompilerDriver* compiler_driver, InstructionSet instruction_set,
+               const std::vector<uint8_t>& code);
 
   // For Portable to supply an ELF object
-  CompiledCode(InstructionSet instruction_set,
-               const std::string& elf_object,
-               const std::string &symbol);
+  CompiledCode(CompilerDriver* compiler_driver, InstructionSet instruction_set,
+               const std::string& elf_object, const std::string &symbol);
 
   InstructionSet GetInstructionSet() const {
     return instruction_set_;
   }
 
   const std::vector<uint8_t>& GetCode() const {
-    return code_;
+    return *code_;
   }
 
-  void SetCode(const std::vector<uint8_t>& code) {
-    CHECK_NE(code.size(), 0U);
-    code_ = code;
-  }
+  void SetCode(const std::vector<uint8_t>& code);
 
   bool operator==(const CompiledCode& rhs) const {
     return (code_ == rhs.code_);
@@ -80,10 +79,12 @@ class CompiledCode {
 #endif
 
  private:
+  CompilerDriver* compiler_driver_;
+
   const InstructionSet instruction_set_;
 
   // Used to store the PIC code for Quick and an ELF image for portable.
-  std::vector<uint8_t> code_;
+  std::vector<uint8_t>* code_;
 
   // Used for the Portable ELF symbol name.
   const std::string symbol_;
@@ -98,7 +99,8 @@ class CompiledCode {
 class CompiledMethod : public CompiledCode {
  public:
   // Constructs a CompiledMethod for the non-LLVM compilers.
-  CompiledMethod(InstructionSet instruction_set,
+  CompiledMethod(CompilerDriver& driver,
+                 InstructionSet instruction_set,
                  const std::vector<uint8_t>& code,
                  const size_t frame_size_in_bytes,
                  const uint32_t core_spill_mask,
@@ -108,30 +110,20 @@ class CompiledMethod : public CompiledCode {
                  const std::vector<uint8_t>& native_gc_map);
 
   // Constructs a CompiledMethod for the JniCompiler.
-  CompiledMethod(InstructionSet instruction_set,
+  CompiledMethod(CompilerDriver& driver,
+                 InstructionSet instruction_set,
                  const std::vector<uint8_t>& code,
                  const size_t frame_size_in_bytes,
                  const uint32_t core_spill_mask,
                  const uint32_t fp_spill_mask);
 
   // Constructs a CompiledMethod for the Portable compiler.
-  CompiledMethod(InstructionSet instruction_set,
-                 const std::string& code,
-                 const std::vector<uint8_t>& gc_map,
-                 const std::string& symbol)
-      : CompiledCode(instruction_set, code, symbol),
-        frame_size_in_bytes_(kStackAlignment), core_spill_mask_(0),
-        fp_spill_mask_(0), gc_map_(gc_map) {
-  }
+  CompiledMethod(CompilerDriver& driver, InstructionSet instruction_set, const std::string& code,
+                 const std::vector<uint8_t>& gc_map, const std::string& symbol);
 
   // Constructs a CompiledMethod for the Portable JniCompiler.
-  CompiledMethod(InstructionSet instruction_set,
-                 const std::string& code,
-                 const std::string& symbol)
-      : CompiledCode(instruction_set, code, symbol),
-        frame_size_in_bytes_(kStackAlignment), core_spill_mask_(0),
-        fp_spill_mask_(0) {
-  }
+  CompiledMethod(CompilerDriver& driver, InstructionSet instruction_set, const std::string& code,
+                 const std::string& symbol);
 
   ~CompiledMethod() {}
 
@@ -148,15 +140,18 @@ class CompiledMethod : public CompiledCode {
   }
 
   const std::vector<uint8_t>& GetMappingTable() const {
-    return mapping_table_;
+    DCHECK(mapping_table_ != nullptr);
+    return *mapping_table_;
   }
 
   const std::vector<uint8_t>& GetVmapTable() const {
-    return vmap_table_;
+    DCHECK(vmap_table_ != nullptr);
+    return *vmap_table_;
   }
 
   const std::vector<uint8_t>& GetGcMap() const {
-    return gc_map_;
+    DCHECK(gc_map_ != nullptr);
+    return *gc_map_;
   }
 
  private:
@@ -168,14 +163,14 @@ class CompiledMethod : public CompiledCode {
   const uint32_t fp_spill_mask_;
   // For quick code, a uleb128 encoded map from native PC offset to dex PC aswell as dex PC to
   // native PC offset. Size prefixed.
-  std::vector<uint8_t> mapping_table_;
+  std::vector<uint8_t>* mapping_table_;
   // For quick code, a uleb128 encoded map from GPR/FPR register to dex register. Size prefixed.
-  std::vector<uint8_t> vmap_table_;
+  std::vector<uint8_t>* vmap_table_;
   // For quick code, a map keyed by native PC indices to bitmaps describing what dalvik registers
   // are live. For portable code, the key is a dalvik PC.
-  std::vector<uint8_t> gc_map_;
+  std::vector<uint8_t>* gc_map_;
 };
 
 }  // namespace art
 
-#endif  // ART_RUNTIME_COMPILED_METHOD_H_
+#endif  // ART_COMPILER_COMPILED_METHOD_H_
diff --git a/compiler/dex/quick/codegen_util.cc b/compiler/dex/quick/codegen_util.cc
index d89f1ed..e081c16 100644
--- a/compiler/dex/quick/codegen_util.cc
+++ b/compiler/dex/quick/codegen_util.cc
@@ -1004,7 +1004,7 @@ CompiledMethod* Mir2Lir::GetCompiledMethod() {
   std::vector<uint16_t> raw_vmap_table;
   // Core regs may have been inserted out of order - sort first
   std::sort(core_vmap_table_.begin(), core_vmap_table_.end());
-  for (size_t i = 0 ; i < core_vmap_table_.size(); i++) {
+  for (size_t i = 0 ; i < core_vmap_table_.size(); ++i) {
     // Copy, stripping out the phys register sort key
     raw_vmap_table.push_back(~(-1 << VREG_NUM_WIDTH) & core_vmap_table_[i]);
   }
@@ -1022,14 +1022,13 @@ CompiledMethod* Mir2Lir::GetCompiledMethod() {
   UnsignedLeb128EncodingVector vmap_encoder;
   // Prefix the encoded data with its size.
   vmap_encoder.PushBack(raw_vmap_table.size());
-  typedef std::vector<uint16_t>::const_iterator It;
-  for (It cur = raw_vmap_table.begin(), end = raw_vmap_table.end(); cur != end; ++cur) {
-    vmap_encoder.PushBack(*cur);
+  for (uint16_t cur : raw_vmap_table) {
+    vmap_encoder.PushBack(cur);
   }
   CompiledMethod* result =
-      new CompiledMethod(cu_->instruction_set, code_buffer_,
-                         frame_size_, core_spill_mask_, fp_spill_mask_,
-                         encoded_mapping_table_.GetData(), vmap_encoder.GetData(), native_gc_map_);
+      new CompiledMethod(*cu_->compiler_driver, cu_->instruction_set, code_buffer_, frame_size_,
+                         core_spill_mask_, fp_spill_mask_, encoded_mapping_table_.GetData(),
+                         vmap_encoder.GetData(), native_gc_map_);
   return result;
 }
 
diff --git a/compiler/driver/compiler_driver.cc b/compiler/driver/compiler_driver.cc
index b17df4e..cbd9020 100644
--- a/compiler/driver/compiler_driver.cc
+++ b/compiler/driver/compiler_driver.cc
@@ -394,6 +394,22 @@ CompilerDriver::CompilerDriver(CompilerBackend compiler_backend, InstructionSet
   }
 }
 
+std::vector<uint8_t>* CompilerDriver::DeduplicateCode(const std::vector<uint8_t>& code) {
+  return dedupe_code_.Add(Thread::Current(), code);
+}
+
+std::vector<uint8_t>* CompilerDriver::DeduplicateMappingTable(const std::vector<uint8_t>& code) {
+  return dedupe_mapping_table_.Add(Thread::Current(), code);
+}
+
+std::vector<uint8_t>* CompilerDriver::DeduplicateVMapTable(const std::vector<uint8_t>& code) {
+  return dedupe_vmap_table_.Add(Thread::Current(), code);
+}
+
+std::vector<uint8_t>* CompilerDriver::DeduplicateGCMap(const std::vector<uint8_t>& code) {
+  return dedupe_gc_map_.Add(Thread::Current(), code);
+}
+
 CompilerDriver::~CompilerDriver() {
   Thread* self = Thread::Current();
   {
diff --git a/compiler/driver/compiler_driver.h b/compiler/driver/compiler_driver.h
index fa1b8f9..cd6b5fa 100644
--- a/compiler/driver/compiler_driver.h
+++ b/compiler/driver/compiler_driver.h
@@ -34,6 +34,7 @@
 #include "runtime.h"
 #include "safe_map.h"
 #include "thread_pool.h"
+#include "utils/dedupe_set.h"
 
 namespace art {
 
@@ -303,6 +304,11 @@ class CompilerDriver {
   void RecordClassStatus(ClassReference ref, mirror::Class::Status status)
       LOCKS_EXCLUDED(compiled_classes_lock_);
 
+  std::vector<uint8_t>* DeduplicateCode(const std::vector<uint8_t>& code);
+  std::vector<uint8_t>* DeduplicateMappingTable(const std::vector<uint8_t>& code);
+  std::vector<uint8_t>* DeduplicateVMapTable(const std::vector<uint8_t>& code);
+  std::vector<uint8_t>* DeduplicateGCMap(const std::vector<uint8_t>& code);
+
  private:
   // Compute constant code and method pointers when possible
   void GetCodeAndMethodForDirectCall(InvokeType type, InvokeType sharp_type,
@@ -439,6 +445,32 @@ class CompilerDriver {
 
   bool support_boot_image_fixup_;
 
+  // DeDuplication data structures, these own the corresponding byte arrays.
+  class DedupeHashFunc {
+   public:
+    size_t operator()(const std::vector<uint8_t>& array) const {
+      // Take a random sample of bytes.
+      static const size_t kSmallArrayThreshold = 16;
+      static const size_t kRandomHashCount = 16;
+      size_t hash = 0;
+      if (array.size() < kSmallArrayThreshold) {
+        for (auto c : array) {
+          hash = hash * 54 + c;
+        }
+      } else {
+        for (size_t i = 0; i < kRandomHashCount; ++i) {
+          size_t r = i * 1103515245 + 12345;
+          hash = hash * 54 + array[r % array.size()];
+        }
+      }
+      return hash;
+    }
+  };
+  DedupeSet<std::vector<uint8_t>, size_t, DedupeHashFunc> dedupe_code_;
+  DedupeSet<std::vector<uint8_t>, size_t, DedupeHashFunc> dedupe_mapping_table_;
+  DedupeSet<std::vector<uint8_t>, size_t, DedupeHashFunc> dedupe_vmap_table_;
+  DedupeSet<std::vector<uint8_t>, size_t, DedupeHashFunc> dedupe_gc_map_;
+
   DISALLOW_COPY_AND_ASSIGN(CompilerDriver);
 };
 
diff --git a/compiler/jni/portable/jni_compiler.cc b/compiler/jni/portable/jni_compiler.cc
index fc2e4e2..43408a7 100644
--- a/compiler/jni/portable/jni_compiler.cc
+++ b/compiler/jni/portable/jni_compiler.cc
@@ -50,7 +50,7 @@ using ::art::llvm::runtime_support::JniMethodStartSynchronized;
 using ::art::llvm::runtime_support::RuntimeId;
 
 JniCompiler::JniCompiler(LlvmCompilationUnit* cunit,
-                         const CompilerDriver& driver,
+                         CompilerDriver& driver,
                          const DexCompilationUnit* dex_compilation_unit)
     : cunit_(cunit), driver_(&driver), module_(cunit_->GetModule()),
       context_(cunit_->GetLLVMContext()), irb_(*cunit_->GetIRBuilder()),
@@ -251,8 +251,7 @@ CompiledMethod* JniCompiler::Compile() {
 
   cunit_->Materialize();
 
-  return new CompiledMethod(cunit_->GetInstructionSet(),
-                            cunit_->GetElfObject(),
+  return new CompiledMethod(*driver_, cunit_->GetInstructionSet(), cunit_->GetElfObject(),
                             func_name);
 }
 
diff --git a/compiler/jni/portable/jni_compiler.h b/compiler/jni/portable/jni_compiler.h
index 49cc9f4..d20c63b 100644
--- a/compiler/jni/portable/jni_compiler.h
+++ b/compiler/jni/portable/jni_compiler.h
@@ -54,7 +54,7 @@ class IRBuilder;
 class JniCompiler {
  public:
   JniCompiler(LlvmCompilationUnit* cunit,
-              const CompilerDriver& driver,
+              CompilerDriver& driver,
               const DexCompilationUnit* dex_compilation_unit);
 
   CompiledMethod* Compile();
@@ -67,7 +67,7 @@ class JniCompiler {
 
  private:
   LlvmCompilationUnit* cunit_;
-  const CompilerDriver* const driver_;
+  CompilerDriver* driver_;
 
   ::llvm::Module* module_;
   ::llvm::LLVMContext* context_;
diff --git a/compiler/jni/quick/jni_compiler.cc b/compiler/jni/quick/jni_compiler.cc
index 069def6..1417fb9 100644
--- a/compiler/jni/quick/jni_compiler.cc
+++ b/compiler/jni/quick/jni_compiler.cc
@@ -370,7 +370,8 @@ CompiledMethod* ArtJniCompileMethodInternal(CompilerDriver& compiler,
     UniquePtr<Disassembler> disassembler(Disassembler::Create(instruction_set));
     disassembler->Dump(LOG(INFO), &managed_code[0], &managed_code[managed_code.size()]);
   }
-  return new CompiledMethod(instruction_set,
+  return new CompiledMethod(compiler,
+                            instruction_set,
                             managed_code,
                             frame_size,
                             main_jni_conv->CoreSpillMask(),
diff --git a/compiler/llvm/compiler_llvm.cc b/compiler/llvm/compiler_llvm.cc
index 6b19a37..fd440d5 100644
--- a/compiler/llvm/compiler_llvm.cc
+++ b/compiler/llvm/compiler_llvm.cc
@@ -153,9 +153,8 @@ CompileDexMethod(DexCompilationUnit* dex_compilation_unit, InvokeType invoke_typ
 
   MethodReference mref(dex_compilation_unit->GetDexFile(),
                        dex_compilation_unit->GetDexMethodIndex());
-  return new CompiledMethod(compiler_driver_->GetInstructionSet(),
-                            cunit->GetElfObject(),
-                            *verifier::MethodVerifier::GetDexGcMap(mref),
+  return new CompiledMethod(*compiler_driver_, compiler_driver_->GetInstructionSet(),
+                            cunit->GetElfObject(), *verifier::MethodVerifier::GetDexGcMap(mref),
                             cunit->GetDexCompilationUnit()->GetSymbol());
 }
 
diff --git a/compiler/oat_writer.h b/compiler/oat_writer.h
index 8111c9f..d5f7e21 100644
--- a/compiler/oat_writer.h
+++ b/compiler/oat_writer.h
@@ -217,18 +217,12 @@ class OatWriter {
   uint32_t size_oat_class_status_;
   uint32_t size_oat_class_method_offsets_;
 
-  template <class T> struct MapCompare {
-   public:
-    bool operator() (const T* const &a, const T* const &b) const {
-      return *a < *b;
-    }
-  };
-
-  // code mappings for deduplication
-  SafeMap<const std::vector<uint8_t>*, uint32_t, MapCompare<std::vector<uint8_t> > > code_offsets_;
-  SafeMap<const std::vector<uint8_t>*, uint32_t, MapCompare<std::vector<uint8_t> > > vmap_table_offsets_;
-  SafeMap<const std::vector<uint8_t>*, uint32_t, MapCompare<std::vector<uint8_t> > > mapping_table_offsets_;
-  SafeMap<const std::vector<uint8_t>*, uint32_t, MapCompare<std::vector<uint8_t> > > gc_map_offsets_;
+  // Code mappings for deduplication. Deduplication is already done on a pointer basis by the
+  // compiler driver, so we can simply compare the pointers to find out if things are duplicated.
+  SafeMap<const std::vector<uint8_t>*, uint32_t> code_offsets_;
+  SafeMap<const std::vector<uint8_t>*, uint32_t> vmap_table_offsets_;
+  SafeMap<const std::vector<uint8_t>*, uint32_t> mapping_table_offsets_;
+  SafeMap<const std::vector<uint8_t>*, uint32_t> gc_map_offsets_;
 
   DISALLOW_COPY_AND_ASSIGN(OatWriter);
 };
diff --git a/compiler/sea_ir/frontend.cc b/compiler/sea_ir/frontend.cc
index 6efc103..93f6f25 100644
--- a/compiler/sea_ir/frontend.cc
+++ b/compiler/sea_ir/frontend.cc
@@ -57,11 +57,9 @@ static CompiledMethod* CompileMethodWithSeaIr(CompilerDriver& compiler,
   dc.DumpSea(ir_graph, "/tmp/temp.dot", types);
   MethodReference mref(&dex_file, method_idx);
   std::string llvm_code = llvm_data->GetElf(compiler.GetInstructionSet());
-  CompiledMethod* compiled_method =  new CompiledMethod(
-                              compiler.GetInstructionSet(),
-                              llvm_code,
-                              *verifier::MethodVerifier::GetDexGcMap(mref),
-                              symbol);
+  CompiledMethod* compiled_method =
+      new CompiledMethod(compiler, compiler.GetInstructionSet(), llvm_code,
+                         *verifier::MethodVerifier::GetDexGcMap(mref), symbol);
   LOG(INFO) << "Compiled SEA IR method " << PrettyMethod(method_idx, dex_file) << ".";
   return compiled_method;
 }
diff --git a/compiler/utils/dedupe_set.h b/compiler/utils/dedupe_set.h
new file mode 100644
index 0000000..f3d35d7
--- /dev/null
+++ b/compiler/utils/dedupe_set.h
@@ -0,0 +1,82 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_COMPILER_UTILS_DEDUPE_SET_H_
+#define ART_COMPILER_UTILS_DEDUPE_SET_H_
+
+#include <set>
+
+#include "base/mutex.h"
+#include "base/stl_util.h"
+
+namespace art {
+
+// A simple data structure to handle hashed deduplication. Add is thread safe.
+template <typename Key, typename HashType, typename HashFunc>
+class DedupeSet {
+  typedef std::pair<HashType, Key*> HashedKey;
+
+  class Comparator {
+   public:
+    bool operator()(const HashedKey& a, const HashedKey& b) const {
+      if (a.first < b.first) return true;
+      if (a.first > b.first) return true;
+      return *a.second < *b.second;
+    }
+  };
+
+  typedef std::set<HashedKey, Comparator> Keys;
+
+ public:
+  typedef typename Keys::iterator iterator;
+  typedef typename Keys::const_iterator const_iterator;
+  typedef typename Keys::size_type size_type;
+  typedef typename Keys::value_type value_type;
+
+  iterator begin() { return keys_.begin(); }
+  const_iterator begin() const { return keys_.begin(); }
+  iterator end() { return keys_.end(); }
+  const_iterator end() const { return keys_.end(); }
+
+  Key* Add(Thread* self, const Key& key) {
+    HashType hash = HashFunc()(key);
+    HashedKey hashed_key(hash, const_cast<Key*>(&key));
+    MutexLock lock(self, lock_);
+    auto it = keys_.find(hashed_key);
+    if (it != keys_.end()) {
+      return it->second;
+    }
+    hashed_key.second = new Key(key);
+    keys_.insert(hashed_key);
+    return hashed_key.second;
+  }
+
+  DedupeSet() : lock_("dedupe lock") {
+  }
+
+  ~DedupeSet() {
+    STLDeleteValues(&keys_);
+  }
+
+ private:
+  Mutex lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
+  Keys keys_;
+  DISALLOW_COPY_AND_ASSIGN(DedupeSet);
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_UTILS_DEDUPE_SET_H_
diff --git a/compiler/utils/dedupe_set_test.cc b/compiler/utils/dedupe_set_test.cc
new file mode 100644
index 0000000..9f5e292
--- /dev/null
+++ b/compiler/utils/dedupe_set_test.cc
@@ -0,0 +1,78 @@
+/*
+ * Copyright (C) 2013 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.
+ */
+
+#include "common_test.h"
+#include "dedupe_set.h"
+
+namespace art {
+
+class DedupeSetTest : public testing::Test {
+ public:
+};
+
+class DedupeHashFunc {
+ public:
+  size_t operator()(const std::vector<uint8_t>& array) const {
+    size_t hash = 0;
+    for (uint8_t c : array) {
+      hash += c;
+      hash += hash << 10;
+      hash += hash >> 6;
+    }
+    return hash;
+  }
+};
+TEST_F(DedupeSetTest, Test) {
+  Thread* self = Thread::Current();
+  typedef std::vector<uint8_t> ByteArray;
+  DedupeSet<ByteArray, size_t, DedupeHashFunc> deduplicator;
+  ByteArray* array1;
+  {
+    ByteArray test1;
+    test1.push_back(10);
+    test1.push_back(20);
+    test1.push_back(30);
+    test1.push_back(45);
+    array1 = deduplicator.Add(self, test1);
+    ASSERT_EQ(test1, *array1);
+  }
+
+  ByteArray* array2;
+  {
+    ByteArray test1;
+    test1.push_back(10);
+    test1.push_back(20);
+    test1.push_back(30);
+    test1.push_back(45);
+    array2 = deduplicator.Add(self, test1);
+    ASSERT_EQ(array2, array1);
+    ASSERT_EQ(test1, *array2);
+  }
+
+  ByteArray* array3;
+  {
+    ByteArray test1;
+    test1.push_back(10);
+    test1.push_back(22);
+    test1.push_back(30);
+    test1.push_back(47);
+    array3 = deduplicator.Add(self, test1);
+    ASSERT_NE(array3, &test1);
+    ASSERT_EQ(test1, *array3);
+  }
+}
+
+}  // namespace art
diff --git a/runtime/Android.mk b/runtime/Android.mk
index 1ce7a30..a8d505e 100644
--- a/runtime/Android.mk
+++ b/runtime/Android.mk
@@ -34,7 +34,6 @@ LIBART_COMMON_SRC_FILES := \
 	check_jni.cc \
 	class_linker.cc \
 	common_throws.cc \
-	compiled_method.cc \
 	debugger.cc \
 	dex_file.cc \
 	dex_file_verifier.cc \