Supporting de-virtualization for precise types.

Sharpening invoke-virtual and invoke-interface calls to invoke-direct for cases
where the type of "this" pointer in the invoke- params is precisely known.

Instructions that have an invoke opcode are marked as interesting, for each invoke-virtual/interface
we come across with a precise type for "this" we mark the location as a candidate for sharpening,
resolve the concrete method and save its method reference <DexFile, DexMethodIndex> to be sharpened
in CompilerDriver::ComputeInvokeInfo().

Added a new entry to AOT statistics showing the percentage of sharpened calls that were based on
type analysis.

Fix a minor bug in type creation for GetSuperClass(). Previously super class of a precise reference
had precise types created which is not necessarily the case.

Fixed DCHECK in Class::FindVirtualMethodForVirtual to handle cases for Miranda methods.

Sharpening only takes place for cases where no soft failures happen at verification time.

Change-Id: Ic027d0226d6f95260c1918014cb6313f2e0ca455

13 files changed, 251 insertions, 46 deletions

diff --git a/src/compiler/dex/mir_dataflow.cc b/src/compiler/dex/mir_dataflow.cc
index 23bf248896..444874dce5 100644
--- a/src/compiler/dex/mir_dataflow.cc
+++ b/src/compiler/dex/mir_dataflow.cc
@@ -1249,11 +1249,13 @@ bool MIRGraph::InvokeUsesMethodStar(MIR* mir)
   int vtable_idx;
   uintptr_t direct_code;
   uintptr_t direct_method;
+  uint32_t current_offset = static_cast<uint32_t>(current_offset_);
   bool fast_path =
-      cu_->compiler_driver->ComputeInvokeInfo(dex_method_idx, &m_unit, type,
-                                             vtable_idx, direct_code,
-                                             direct_method) &&
-                                             !(cu_->enable_debug & (1 << kDebugSlowInvokePath));
+      cu_->compiler_driver->ComputeInvokeInfo(dex_method_idx, current_offset,
+                                              &m_unit, type,
+                                              vtable_idx, direct_code,
+                                              direct_method) &&
+                                              !(cu_->enable_debug & (1 << kDebugSlowInvokePath));
   return (((type == kDirect) || (type == kStatic)) &&
           fast_path && ((direct_code == 0) || (direct_method == 0)));
 }
diff --git a/src/compiler/dex/quick/gen_invoke.cc b/src/compiler/dex/quick/gen_invoke.cc
index 2eab673e2c..efacff0ab2 100644
--- a/src/compiler/dex/quick/gen_invoke.cc
+++ b/src/compiler/dex/quick/gen_invoke.cc
@@ -1329,7 +1329,7 @@ void Mir2Lir::GenInvoke(CallInfo* info)
   uintptr_t direct_method;
   bool skip_this;
   bool fast_path = cu_->compiler_driver->ComputeInvokeInfo(
-      dex_method_idx, mir_graph_->GetCurrentDexCompilationUnit(), info->type, vtable_idx,
+      dex_method_idx, current_dalvik_offset_, mir_graph_->GetCurrentDexCompilationUnit(), info->type, vtable_idx,
       direct_code, direct_method) && !SLOW_INVOKE_PATH;
   if (info->type == kInterface) {
     if (fast_path) {
diff --git a/src/compiler/driver/compiler_driver.cc b/src/compiler/driver/compiler_driver.cc
index bc34073020..3e1e7436aa 100644
--- a/src/compiler/driver/compiler_driver.cc
+++ b/src/compiler/driver/compiler_driver.cc
@@ -71,7 +71,8 @@ class AOTCompilationStats {
         strings_in_dex_cache_(0), strings_not_in_dex_cache_(0),
         resolved_types_(0), unresolved_types_(0),
         resolved_instance_fields_(0), unresolved_instance_fields_(0),
-        resolved_local_static_fields_(0), resolved_static_fields_(0), unresolved_static_fields_(0) {
+        resolved_local_static_fields_(0), resolved_static_fields_(0), unresolved_static_fields_(0),
+        type_based_devirtualization_(0) {
     for (size_t i = 0; i <= kMaxInvokeType; i++) {
       resolved_methods_[i] = 0;
       unresolved_methods_[i] = 0;
@@ -90,6 +91,8 @@ class AOTCompilationStats {
              "static fields resolved");
     DumpStat(resolved_local_static_fields_, resolved_static_fields_ + unresolved_static_fields_,
              "static fields local to a class");
+    DumpStat(type_based_devirtualization_,virtual_made_direct_[kInterface] + virtual_made_direct_[kVirtual]
+             - type_based_devirtualization_, "sharpened calls based on type information");
 
     for (size_t i = 0; i <= kMaxInvokeType; i++) {
       std::ostringstream oss;
@@ -181,6 +184,10 @@ class AOTCompilationStats {
     unresolved_static_fields_++;
   }
 
+  void PreciseTypeDevirtualization() {
+    STATS_LOCK();
+    type_based_devirtualization_++;
+  }
   void ResolvedMethod(InvokeType type) {
     DCHECK_LE(type, kMaxInvokeType);
     STATS_LOCK();
@@ -229,6 +236,8 @@ class AOTCompilationStats {
   size_t resolved_local_static_fields_;
   size_t resolved_static_fields_;
   size_t unresolved_static_fields_;
+  // Type based devirtualization for invoke interface and virtual.
+  size_t type_based_devirtualization_;
 
   size_t resolved_methods_[kMaxInvokeType + 1];
   size_t unresolved_methods_[kMaxInvokeType + 1];
@@ -804,10 +813,16 @@ void CompilerDriver::GetCodeAndMethodForDirectCall(InvokeType type, InvokeType s
   }
 }
 
-bool CompilerDriver::ComputeInvokeInfo(uint32_t method_idx, const DexCompilationUnit* mUnit,
-                                       InvokeType& type, int& vtable_idx, uintptr_t& direct_code,
+bool CompilerDriver::ComputeInvokeInfo(uint32_t method_idx,const uint32_t dex_pc,
+                                       const DexCompilationUnit* mUnit, InvokeType& type,
+                                       int& vtable_idx, uintptr_t& direct_code,
                                        uintptr_t& direct_method) {
   ScopedObjectAccess soa(Thread::Current());
+
+  const bool kEnableVerifierBasedSharpening = true;
+  const CompilerDriver::MethodReference ref_caller(mUnit->GetDexFile(), mUnit->GetDexMethodIndex());
+  const CompilerDriver::MethodReference* ref_sharpen = verifier::MethodVerifier::GetDevirtMap(ref_caller, dex_pc);
+  bool can_devirtualize = (dex_pc != art::kDexPCNotReady) && (ref_sharpen != NULL);
   vtable_idx = -1;
   direct_code = 0;
   direct_method = 0;
@@ -845,6 +860,7 @@ bool CompilerDriver::ComputeInvokeInfo(uint32_t method_idx, const DexCompilation
             referrer_class->IsSubClass(methods_class) &&
             vtable_idx < methods_class->GetVTable()->GetLength() &&
             methods_class->GetVTable()->Get(vtable_idx) == resolved_method);
+
         if (kEnableSharpening && can_sharpen) {
           stats_->ResolvedMethod(type);
           // Sharpen a virtual call into a direct call. The method_idx is into referrer's
@@ -856,7 +872,26 @@ bool CompilerDriver::ComputeInvokeInfo(uint32_t method_idx, const DexCompilation
                                         direct_code, direct_method);
           type = kDirect;
           return true;
-        } else if (type == kSuper) {
+        } else if(can_devirtualize && kEnableSharpening && kEnableVerifierBasedSharpening) {
+            // If traditional sharpening fails, try the sharpening based on type information (Devirtualization)
+            mirror::DexCache* dex_cache = mUnit->GetClassLinker()->FindDexCache(*ref_sharpen->first);
+            mirror::ClassLoader* class_loader = soa.Decode<mirror::ClassLoader*>(mUnit->GetClassLoader());
+            mirror::AbstractMethod* concrete_method = mUnit->GetClassLinker()->ResolveMethod(
+                *ref_sharpen->first, ref_sharpen->second, dex_cache, class_loader, NULL, kVirtual);
+            CHECK(concrete_method != NULL);
+            CHECK(!concrete_method->IsAbstract());
+            // TODO: fix breakage in image patching to be able to devirtualize cases with different
+            // resolved and concrete methods.
+            if(resolved_method == concrete_method) {
+              GetCodeAndMethodForDirectCall(type, kDirect, referrer_class, concrete_method, direct_code, direct_method);
+              stats_->VirtualMadeDirect(type);
+              type = kDirect;
+              stats_->PreciseTypeDevirtualization();
+            }
+            stats_->ResolvedMethod(type);
+            return true;
+        }
+        else if (type == kSuper) {
           // Unsharpened super calls are suspicious so go slow-path.
         } else {
           stats_->ResolvedMethod(type);
diff --git a/src/compiler/driver/compiler_driver.h b/src/compiler/driver/compiler_driver.h
index 7c37c6a083..75d276d5b1 100644
--- a/src/compiler/driver/compiler_driver.h
+++ b/src/compiler/driver/compiler_driver.h
@@ -39,6 +39,7 @@ class ParallelCompilationManager;
 class DexCompilationUnit;
 class TimingLogger;
 
+const uint32_t kDexPCNotReady = 0xFFFFFF;
 enum CompilerBackend {
   kQuick,
   kPortable,
@@ -145,8 +146,9 @@ class CompilerDriver {
 
   // Can we fastpath a interface, super class or virtual method call? Computes method's vtable
   // index.
-  bool ComputeInvokeInfo(uint32_t method_idx, const DexCompilationUnit* mUnit, InvokeType& type,
-                         int& vtable_idx, uintptr_t& direct_code, uintptr_t& direct_method)
+  bool ComputeInvokeInfo(uint32_t method_idx, uint32_t dex_pc,
+                         const DexCompilationUnit* mUnit, InvokeType& type, int& vtable_idx,
+                         uintptr_t& direct_code, uintptr_t& direct_method)
       LOCKS_EXCLUDED(Locks::mutator_lock_);
 
   // Record patch information for later fix up.
diff --git a/src/compiler/llvm/gbc_expander.cc b/src/compiler/llvm/gbc_expander.cc
index 94eb741039..c1e35a69a7 100644
--- a/src/compiler/llvm/gbc_expander.cc
+++ b/src/compiler/llvm/gbc_expander.cc
@@ -785,8 +785,10 @@ llvm::Value* GBCExpanderPass::EmitInvoke(llvm::CallInst& call_inst) {
   int vtable_idx = -1;
   uintptr_t direct_code = 0;
   uintptr_t direct_method = 0;
+  // TODO: pass actual value of dex PC (instead of kDexPCNotready) needed by verifier based
+  // sharpening after LLVM re-factoring is finished.
   bool is_fast_path = driver_->
-      ComputeInvokeInfo(callee_method_idx, dex_compilation_unit_,
+      ComputeInvokeInfo(callee_method_idx, art::kDexPCNotReady, dex_compilation_unit_,
                         invoke_type, vtable_idx, direct_code, direct_method);
 
   // Load the method object
diff --git a/src/mirror/class-inl.h b/src/mirror/class-inl.h
index d7afed6cd5..62740bed2e 100644
--- a/src/mirror/class-inl.h
+++ b/src/mirror/class-inl.h
@@ -225,7 +225,7 @@ inline AbstractMethod* Class::FindVirtualMethodForInterface(AbstractMethod* meth
 
 inline AbstractMethod* Class::FindVirtualMethodForVirtual(AbstractMethod* method) const
     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
-  DCHECK(!method->GetDeclaringClass()->IsInterface());
+  DCHECK(!method->GetDeclaringClass()->IsInterface() || method->IsMiranda());
   // The argument method may from a super class.
   // Use the index to a potentially overridden one for this instance's class.
   return GetVTable()->Get(method->GetMethodIndex());
diff --git a/src/mirror/class.h b/src/mirror/class.h
index afab3141fe..dfbe815631 100644
--- a/src/mirror/class.h
+++ b/src/mirror/class.h
@@ -346,7 +346,7 @@ class MANAGED Class : public StaticStorageBase {
     return !IsPrimitive() && GetSuperClass() == NULL;
   }
   bool IsInstantiable() const {
-    return !IsPrimitive() && !IsInterface() && !IsAbstract();
+    return (!IsPrimitive() && !IsInterface() && !IsAbstract()) || ((IsAbstract()) && IsArrayClass());
   }
 
   bool IsObjectArrayClass() const {
diff --git a/src/verifier/instruction_flags.cc b/src/verifier/instruction_flags.cc
index 823edde9f0..358791ddf6 100644
--- a/src/verifier/instruction_flags.cc
+++ b/src/verifier/instruction_flags.cc
@@ -29,7 +29,7 @@ std::string InstructionFlags::ToString() const {
     strncpy(encoding, "-----", sizeof(encoding));
     if (IsInTry())        encoding[kInTry] = 'T';
     if (IsBranchTarget()) encoding[kBranchTarget] = 'B';
-    if (IsGcPoint())      encoding[kGcPoint] = 'G';
+    if (IsCompileTimeInfoPoint())  encoding[kCompileTimeInfoPoint] = 'G';
     if (IsVisited())      encoding[kVisited] = 'V';
     if (IsChanged())      encoding[kChanged] = 'C';
   }
diff --git a/src/verifier/instruction_flags.h b/src/verifier/instruction_flags.h
index 7f0d24041b..9dc3ea7a7c 100644
--- a/src/verifier/instruction_flags.h
+++ b/src/verifier/instruction_flags.h
@@ -59,15 +59,14 @@ class InstructionFlags {
   bool IsBranchTarget() const {
     return (flags_ & (1 << kBranchTarget)) != 0;
   }
-
-  void SetGcPoint() {
-    flags_ |= 1 << kGcPoint;
+  void SetCompileTimeInfoPoint() {
+    flags_ |= 1 << kCompileTimeInfoPoint;
   }
-  void ClearGcPoint() {
-    flags_ &= ~(1 << kGcPoint);
+  void ClearCompileTimeInfoPoint() {
+    flags_ &= ~(1 << kCompileTimeInfoPoint);
   }
-  bool IsGcPoint() const {
-    return (flags_ & (1 << kGcPoint)) != 0;
+  bool IsCompileTimeInfoPoint() const {
+    return (flags_ & (1 << kCompileTimeInfoPoint)) != 0;
   }
 
   void SetVisited() {
@@ -100,7 +99,8 @@ class InstructionFlags {
   enum {
     kInTry,
     kBranchTarget,
-    kGcPoint,
+    kCompileTimeInfoPoint,  // Location of interest to the compiler for GC maps and
+                            // verifier based method sharpening.
     kVisited,
     kChanged,
   };
diff --git a/src/verifier/method_verifier.cc b/src/verifier/method_verifier.cc
index 2b70e265d4..2eb0c203ea 100644
--- a/src/verifier/method_verifier.cc
+++ b/src/verifier/method_verifier.cc
@@ -56,8 +56,8 @@ void PcToRegisterLineTable::Init(RegisterTrackingMode mode, InstructionFlags* fl
       case kTrackRegsAll:
         interesting = flags[i].IsOpcode();
         break;
-      case kTrackRegsGcPoints:
-        interesting = flags[i].IsGcPoint() || flags[i].IsBranchTarget();
+      case kTrackCompilerInterestPoints:
+        interesting = flags[i].IsCompileTimeInfoPoint() || flags[i].IsBranchTarget() ;
         break;
       case kTrackRegsBranches:
         interesting = flags[i].IsBranchTarget();
@@ -496,7 +496,7 @@ bool MethodVerifier::VerifyInstructions() {
 
   /* Flag the start of the method as a branch target, and a GC point due to stack overflow errors */
   insn_flags_[0].SetBranchTarget();
-  insn_flags_[0].SetGcPoint();
+  insn_flags_[0].SetCompileTimeInfoPoint();
 
   uint32_t insns_size = code_item_->insns_size_in_code_units_;
   for (uint32_t dex_pc = 0; dex_pc < insns_size;) {
@@ -505,8 +505,10 @@ bool MethodVerifier::VerifyInstructions() {
       return false;
     }
     /* Flag instructions that are garbage collection points */
+    // All invoke points are marked as "Throw" points already.
+    // We are relying on this to also count all the invokes as interesting.
     if (inst->IsBranch() || inst->IsSwitch() || inst->IsThrow() || inst->IsReturn()) {
-      insn_flags_[dex_pc].SetGcPoint();
+      insn_flags_[dex_pc].SetCompileTimeInfoPoint();
     }
     dex_pc += inst->SizeInCodeUnits();
     inst = inst->Next();
@@ -918,7 +920,8 @@ bool MethodVerifier::VerifyCodeFlow() {
                  << " insns_size=" << insns_size << ")";
   }
   /* Create and initialize table holding register status */
-  reg_table_.Init(kTrackRegsGcPoints, insn_flags_.get(), insns_size, registers_size, this);
+  reg_table_.Init(kTrackCompilerInterestPoints, insn_flags_.get(), insns_size, registers_size, this);
+
 
   work_line_.reset(new RegisterLine(registers_size, this));
   saved_line_.reset(new RegisterLine(registers_size, this));
@@ -952,6 +955,10 @@ bool MethodVerifier::VerifyCodeFlow() {
   const std::vector<uint8_t>* dex_gc_map = CreateLengthPrefixedDexGcMap(*(map.get()));
   verifier::MethodVerifier::SetDexGcMap(ref, *dex_gc_map);
 
+  MethodVerifier::PcToConreteMethod* pc_to_conrete_method = GenerateDevirtMap();
+  if(pc_to_conrete_method != NULL ) {
+    SetDevirtMap(ref, pc_to_conrete_method);
+  }
   return true;
 }
 
@@ -3137,7 +3144,7 @@ void MethodVerifier::ComputeGcMapSizes(size_t* gc_points, size_t* ref_bitmap_bit
   size_t max_insn = 0;
   size_t max_ref_reg = -1;
   for (size_t i = 0; i < code_item_->insns_size_in_code_units_; i++) {
-    if (insn_flags_[i].IsGcPoint()) {
+    if (insn_flags_[i].IsCompileTimeInfoPoint()) {
       local_gc_points++;
       max_insn = i;
       RegisterLine* line = reg_table_.GetLine(i);
@@ -3153,6 +3160,84 @@ void MethodVerifier::ComputeGcMapSizes(size_t* gc_points, size_t* ref_bitmap_bit
   *log2_max_gc_pc = i;
 }
 
+MethodVerifier::PcToConreteMethod* MethodVerifier::GenerateDevirtMap() {
+
+  // It is risky to rely on reg_types for sharpening in cases of soft
+  // verification, we might end up sharpening to a wrong implementation. Just abort.
+  if (!failure_messages_.empty()) {
+    return NULL;
+  }
+
+  PcToConreteMethod* pc_to_concrete_method = new PcToConreteMethod();
+  uint32_t dex_pc = 0;
+  const uint16_t* insns = code_item_->insns_ ;
+  const Instruction* inst = Instruction::At(insns);
+
+  for (; dex_pc < code_item_->insns_size_in_code_units_;
+         dex_pc += insn_flags_[dex_pc].GetLengthInCodeUnits(), inst = inst->Next()) {
+
+    bool is_virtual   = (inst->Opcode() == Instruction::INVOKE_VIRTUAL) ||
+        (inst->Opcode() ==  Instruction::INVOKE_VIRTUAL_RANGE);
+    bool is_interface = (inst->Opcode() == Instruction::INVOKE_INTERFACE) ||
+        (inst->Opcode() == Instruction::INVOKE_INTERFACE_RANGE);
+
+   if(!(is_interface || is_virtual))
+     continue;
+
+    // Check if vC ("this" pointer in the instruction) has a precise type.
+    RegisterLine* line = reg_table_.GetLine(dex_pc);
+    DecodedInstruction dec_insn(inst);
+    const RegType& reg_type(line->GetRegisterType(dec_insn.vC));
+
+    if (!reg_type.IsPreciseReference()) {
+       continue;
+    }
+
+    CHECK(!(reg_type.GetClass()->IsInterface()));
+    // If the class is an array class, it can be both Abstract and final and so
+    // the reg_type will be created as precise.
+    CHECK(!(reg_type.GetClass()->IsAbstract()) || reg_type.GetClass()->IsArrayClass());
+    // Find the abstract method.
+    // vB has the method index.
+    mirror::AbstractMethod* abstract_method =  NULL ;
+    abstract_method =  dex_cache_->GetResolvedMethod(dec_insn.vB);
+    if(abstract_method == NULL) {
+      // If the method is not found in the cache this means that it was never found
+      // by ResolveMethodAndCheckAccess() called when verifying invoke_*.
+      continue;
+    }
+    // Find the concrete method.
+    mirror::AbstractMethod* concrete_method = NULL;
+    if (is_interface) {
+      concrete_method = reg_type.GetClass()->FindVirtualMethodForInterface(abstract_method);
+    }
+    if (is_virtual) {
+      concrete_method = reg_type.GetClass()->FindVirtualMethodForVirtual(abstract_method);
+    }
+
+    if(concrete_method == NULL) {
+      // In cases where concrete_method is not found continue to the next invoke instead
+      // of crashing.
+      continue;
+    }
+
+    CHECK(!concrete_method->IsAbstract()) << PrettyMethod(concrete_method);
+    // Build method reference.
+    CompilerDriver::MethodReference concrete_ref(
+        concrete_method->GetDeclaringClass()->GetDexCache()->GetDexFile(),
+        concrete_method->GetDexMethodIndex());
+    // Now Save the current PC and the concrete method reference to be used
+    // in compiler driver.
+    pc_to_concrete_method->Put(dex_pc, concrete_ref );
+    }
+
+  if (pc_to_concrete_method->size() == 0) {
+    delete pc_to_concrete_method;
+    return NULL ;
+  }
+  return pc_to_concrete_method;
+}
+
 const std::vector<uint8_t>* MethodVerifier::GenerateGcMap() {
   size_t num_entries, ref_bitmap_bits, pc_bits;
   ComputeGcMapSizes(&num_entries, &ref_bitmap_bits, &pc_bits);
@@ -3199,7 +3284,7 @@ const std::vector<uint8_t>* MethodVerifier::GenerateGcMap() {
   table->push_back((num_entries >> 8) & 0xFF);
   // Write table data
   for (size_t i = 0; i < code_item_->insns_size_in_code_units_; i++) {
-    if (insn_flags_[i].IsGcPoint()) {
+    if (insn_flags_[i].IsCompileTimeInfoPoint()) {
       table->push_back(i & 0xFF);
       if (pc_bytes == 2) {
         table->push_back((i >> 8) & 0xFF);
@@ -3219,7 +3304,7 @@ void MethodVerifier::VerifyGcMap(const std::vector<uint8_t>& data) {
   size_t map_index = 0;
   for (size_t i = 0; i < code_item_->insns_size_in_code_units_; i++) {
     const uint8_t* reg_bitmap = map.FindBitMap(i, false);
-    if (insn_flags_[i].IsGcPoint()) {
+    if (insn_flags_[i].IsCompileTimeInfoPoint()) {
       CHECK_LT(map_index, map.NumEntries());
       CHECK_EQ(map.GetDexPc(map_index), i);
       CHECK_EQ(map.GetBitMap(map_index), reg_bitmap);
@@ -3254,6 +3339,19 @@ void MethodVerifier::SetDexGcMap(CompilerDriver::MethodReference ref, const std:
   CHECK(GetDexGcMap(ref) != NULL);
 }
 
+void  MethodVerifier::SetDevirtMap(CompilerDriver::MethodReference ref, const PcToConreteMethod* devirt_map) {
+
+  MutexLock mu(Thread::Current(), *devirt_maps_lock_);
+  DevirtualizationMapTable::iterator it = devirt_maps_->find(ref);
+  if (it != devirt_maps_->end()) {
+    delete it->second;
+    devirt_maps_->erase(it);
+  }
+
+  devirt_maps_->Put(ref, devirt_map);
+  CHECK(devirt_maps_->find(ref) != devirt_maps_->end());
+}
+
 const std::vector<uint8_t>* MethodVerifier::GetDexGcMap(CompilerDriver::MethodReference ref) {
   MutexLock mu(Thread::Current(), *dex_gc_maps_lock_);
   DexGcMapTable::const_iterator it = dex_gc_maps_->find(ref);
@@ -3265,6 +3363,22 @@ const std::vector<uint8_t>* MethodVerifier::GetDexGcMap(CompilerDriver::MethodRe
   return it->second;
 }
 
+const CompilerDriver::MethodReference* MethodVerifier::GetDevirtMap(CompilerDriver::MethodReference ref, uint32_t pc) {
+  MutexLock mu(Thread::Current(), *devirt_maps_lock_);
+  DevirtualizationMapTable::const_iterator it = devirt_maps_->find(ref);
+  if (it == devirt_maps_->end()) {
+    return NULL;
+  }
+
+  // Look up the PC in the map, get the concrete method to execute and return its reference.
+  MethodVerifier::PcToConreteMethod::const_iterator pc_to_concrete_method = it->second->find(pc);
+  if(pc_to_concrete_method != it->second->end()) {
+    return &(pc_to_concrete_method->second);
+  } else {
+    return NULL;
+  }
+}
+
 std::vector<int32_t> MethodVerifier::DescribeVRegs(uint32_t dex_pc) {
   RegisterLine* line = reg_table_.GetLine(dex_pc);
   std::vector<int32_t> result;
@@ -3312,6 +3426,9 @@ std::vector<int32_t> MethodVerifier::DescribeVRegs(uint32_t dex_pc) {
 Mutex* MethodVerifier::dex_gc_maps_lock_ = NULL;
 MethodVerifier::DexGcMapTable* MethodVerifier::dex_gc_maps_ = NULL;
 
+Mutex* MethodVerifier::devirt_maps_lock_ = NULL;
+MethodVerifier::DevirtualizationMapTable* MethodVerifier::devirt_maps_ = NULL;
+
 Mutex* MethodVerifier::rejected_classes_lock_ = NULL;
 MethodVerifier::RejectedClassesTable* MethodVerifier::rejected_classes_ = NULL;
 
@@ -3323,6 +3440,12 @@ void MethodVerifier::Init() {
     dex_gc_maps_ = new MethodVerifier::DexGcMapTable;
   }
 
+  devirt_maps_lock_ = new Mutex("verifier Devirtualization lock");
+  {
+    MutexLock mu(self, *devirt_maps_lock_);
+    devirt_maps_ = new MethodVerifier::DevirtualizationMapTable();
+  }
+
   rejected_classes_lock_ = new Mutex("verifier rejected classes lock");
   {
     MutexLock mu(self, *rejected_classes_lock_);
@@ -3343,6 +3466,15 @@ void MethodVerifier::Shutdown() {
   dex_gc_maps_lock_ = NULL;
 
   {
+    MutexLock mu(self, *devirt_maps_lock_);
+    STLDeleteValues(devirt_maps_);
+    delete devirt_maps_;
+    devirt_maps_ = NULL;
+  }
+  delete devirt_maps_lock_;
+  devirt_maps_lock_ = NULL;
+
+  {
     MutexLock mu(self, *rejected_classes_lock_);
     delete rejected_classes_;
     rejected_classes_ = NULL;
diff --git a/src/verifier/method_verifier.h b/src/verifier/method_verifier.h
index 7570b50dbe..b7e1cf2257 100644
--- a/src/verifier/method_verifier.h
+++ b/src/verifier/method_verifier.h
@@ -101,7 +101,7 @@ const int kVerifyErrorRefTypeShift = 6;
 // type-precise register analysis).
 enum RegisterTrackingMode {
   kTrackRegsBranches,
-  kTrackRegsGcPoints,
+  kTrackCompilerInterestPoints,
   kTrackRegsAll,
 };
 
@@ -187,6 +187,9 @@ class MethodVerifier {
   static const std::vector<uint8_t>* GetDexGcMap(CompilerDriver::MethodReference ref)
       LOCKS_EXCLUDED(dex_gc_maps_lock_);
 
+  static const CompilerDriver::MethodReference* GetDevirtMap(CompilerDriver::MethodReference ref, uint32_t pc)
+      LOCKS_EXCLUDED(devirt_maps_lock_);
+
   // Fills 'monitor_enter_dex_pcs' with the dex pcs of the monitor-enter instructions corresponding
   // to the locks held at 'dex_pc' in 'm'.
   static void FindLocksAtDexPc(mirror::AbstractMethod* m, uint32_t dex_pc,
@@ -577,6 +580,16 @@ class MethodVerifier {
   static void SetDexGcMap(CompilerDriver::MethodReference ref, const std::vector<uint8_t>& dex_gc_map)
       LOCKS_EXCLUDED(dex_gc_maps_lock_);
 
+
+  // Devirtualization map.
+  typedef SafeMap<const uint32_t, CompilerDriver::MethodReference> PcToConreteMethod;
+  typedef SafeMap<const CompilerDriver::MethodReference, const PcToConreteMethod*> DevirtualizationMapTable;
+  MethodVerifier::PcToConreteMethod* GenerateDevirtMap();
+
+  static Mutex* devirt_maps_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
+  static DevirtualizationMapTable* devirt_maps_ GUARDED_BY(devirt_maps_lock_);
+  static void SetDevirtMap(CompilerDriver::MethodReference ref, const PcToConreteMethod* pc_method_map);
+        LOCKS_EXCLUDED(devirt_maps_lock_);
   typedef std::set<CompilerDriver::ClassReference> RejectedClassesTable;
   static Mutex* rejected_classes_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
   static RejectedClassesTable* rejected_classes_;
diff --git a/src/verifier/reg_type.cc b/src/verifier/reg_type.cc
index 774c2b29eb..32679f6100 100644
--- a/src/verifier/reg_type.cc
+++ b/src/verifier/reg_type.cc
@@ -494,6 +494,7 @@ ReferenceType::ReferenceType(mirror::Class* klass, std::string& descriptor, uint
 PreciseReferenceType::PreciseReferenceType(mirror::Class* klass, std::string& descriptor,
                                            uint16_t cache_id)
     : RegType(klass, descriptor, cache_id) {
+  DCHECK(klass->IsInstantiable());
 }
 
 UnresolvedUninitialisedThisRefType::UnresolvedUninitialisedThisRefType(std::string& descriptor,
@@ -609,7 +610,9 @@ const RegType& RegType::GetSuperClass(RegTypeCache* cache) const {
   if (!IsUnresolvedTypes()) {
     mirror::Class* super_klass = GetClass()->GetSuperClass();
     if (super_klass != NULL) {
-      return cache->FromClass(super_klass, IsPreciseReference());
+      // A super class of a precise type isn't precise as a precise type indicates the register
+      // holds exactly that type.
+      return cache->FromClass(super_klass, false);
     } else {
       return cache->Zero();
     }
diff --git a/src/verifier/reg_type_cache.cc b/src/verifier/reg_type_cache.cc
index 8e23b743f0..7153768ec7 100644
--- a/src/verifier/reg_type_cache.cc
+++ b/src/verifier/reg_type_cache.cc
@@ -179,7 +179,7 @@ const RegType& RegTypeCache::From(mirror::ClassLoader* loader, std::string descr
 
     //To pass the verification, the type should be imprecise,
     // instantiable or an interface with the precise type set to false.
-    CHECK(!precise || klass->IsInstantiable());
+    DCHECK(!precise || klass->IsInstantiable());
 
     // Create a precise type if:
     // 1- Class is final and NOT an interface. a precise interface
@@ -189,10 +189,9 @@ const RegType& RegTypeCache::From(mirror::ClassLoader* loader, std::string descr
     RegType* entry;
     // Create an imprecise type if we can't tell for a fact that it is precise.
     if ((klass->IsFinal()) || precise) {
-      CHECK(!(klass->IsAbstract()) || klass->IsArrayClass());
-      CHECK(!klass->IsInterface());
+      DCHECK(!(klass->IsAbstract()) || klass->IsArrayClass());
+      DCHECK(!klass->IsInterface());
       entry = new PreciseReferenceType(klass, descriptor, entries_.size());
-
     } else {
       entry = new ReferenceType(klass, descriptor, entries_.size());
     }
@@ -372,7 +371,7 @@ const RegType& RegTypeCache::Uninitialized(const RegType& type, uint32_t allocat
         return *cur_entry;
       }
     }
-    std::string descriptor = "";
+    std::string descriptor("");
     entry = new UninitialisedReferenceType(klass, descriptor, allocation_pc, entries_.size());
   }
   entries_.push_back(entry);
@@ -401,17 +400,34 @@ const RegType& RegTypeCache::FromUninitialized(const RegType& uninit_type) {
           return *cur_entry;
         }
       }
-      std::string descriptor = "";
+      std::string descriptor("");
       entry = new ReferenceType(klass, descriptor, entries_.size());
     } else {
-      for (size_t i = primitive_count_; i < entries_.size(); i++) {
-        RegType* cur_entry = entries_[i];
-        if (cur_entry->IsPreciseReference() && cur_entry->GetClass() == klass) {
-          return *cur_entry;
+        std::string descriptor;
+        if (klass->IsFinal()) {
+          if (klass->IsInstantiable()) {
+            for (size_t i = primitive_count_; i < entries_.size(); i++) {
+              RegType* cur_entry = entries_[i];
+              if (cur_entry->IsPreciseReference() && cur_entry->GetClass() == klass) {
+                return *cur_entry;
+              }
+            }
+            // Precise type was not found , create one !
+            entry = new PreciseReferenceType(klass, descriptor, entries_.size());
+          } else {
+            return Conflict();
+          }
+      } else {
+        // Not a final class, create an imprecise reference. Look up if we have it in the cache first.
+        for (size_t i = primitive_count_; i < entries_.size(); i++) {
+          RegType* cur_entry = entries_[i];
+          if (cur_entry->IsReference() && !(cur_entry->IsPrecise()) &&
+              cur_entry->GetClass() == klass) {
+            return *cur_entry;
+          }
         }
+        entry = new ReferenceType(klass, descriptor, entries_.size());
       }
-      std::string descriptor = "";
-      entry = new PreciseReferenceType(klass, descriptor, entries_.size());
     }
  }
   entries_.push_back(entry);
@@ -447,7 +463,7 @@ const RegType& RegTypeCache::UninitializedThisArgument(const RegType& type) {
         return *cur_entry;
       }
     }
-    std::string descriptor = "";
+    std::string descriptor("");
     entry = new UninitialisedThisReferenceType(klass, descriptor, entries_.size());
   }
   entries_.push_back(entry);