Merge "Reference type propagation"

16 files changed, 548 insertions, 23 deletions

diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc
index 32f6972c84..d55a3ca00b 100644
--- a/compiler/optimizing/inliner.cc
+++ b/compiler/optimizing/inliner.cc
@@ -159,7 +159,7 @@ bool HInliner::TryInline(HInvoke* invoke_instruction,
   SsaDeadPhiElimination dead_phi(callee_graph);
   HDeadCodeElimination dce(callee_graph);
   HConstantFolding fold(callee_graph);
-  InstructionSimplifier simplify(callee_graph);
+  InstructionSimplifier simplify(callee_graph, stats_);
 
   HOptimization* optimizations[] = {
     &redundant_phi,
@@ -176,7 +176,7 @@ bool HInliner::TryInline(HInvoke* invoke_instruction,
 
   if (depth_ + 1 < kDepthLimit) {
     HInliner inliner(
-        callee_graph, outer_compilation_unit_, compiler_driver_, outer_stats_, depth_ + 1);
+        callee_graph, outer_compilation_unit_, compiler_driver_, stats_, depth_ + 1);
     inliner.Run();
   }
 
@@ -221,7 +221,7 @@ bool HInliner::TryInline(HInvoke* invoke_instruction,
   // after optimizations get a unique id.
   graph_->SetCurrentInstructionId(callee_graph->GetNextInstructionId());
   VLOG(compiler) << "Successfully inlined " << PrettyMethod(method_index, outer_dex_file);
-  outer_stats_->RecordStat(kInlinedInvoke);
+  MaybeRecordStat(kInlinedInvoke);
   return true;
 }
 
diff --git a/compiler/optimizing/inliner.h b/compiler/optimizing/inliner.h
index 07d893e7c9..8e9cf837df 100644
--- a/compiler/optimizing/inliner.h
+++ b/compiler/optimizing/inliner.h
@@ -35,10 +35,9 @@ class HInliner : public HOptimization {
            CompilerDriver* compiler_driver,
            OptimizingCompilerStats* stats,
            size_t depth = 0)
-      : HOptimization(outer_graph, true, "inliner"),
+      : HOptimization(outer_graph, true, "inliner", stats),
         outer_compilation_unit_(outer_compilation_unit),
         compiler_driver_(compiler_driver),
-        outer_stats_(stats),
         depth_(depth) {}
 
   void Run() OVERRIDE;
@@ -48,7 +47,6 @@ class HInliner : public HOptimization {
 
   const DexCompilationUnit& outer_compilation_unit_;
   CompilerDriver* const compiler_driver_;
-  OptimizingCompilerStats* const outer_stats_;
   const size_t depth_;
 
   DISALLOW_COPY_AND_ASSIGN(HInliner);
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index 44dbb9d106..fd99070780 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -16,11 +16,15 @@
 
 #include "instruction_simplifier.h"
 
+#include "mirror/class-inl.h"
+#include "scoped_thread_state_change.h"
+
 namespace art {
 
 class InstructionSimplifierVisitor : public HGraphVisitor {
  public:
-  explicit InstructionSimplifierVisitor(HGraph* graph) : HGraphVisitor(graph) {}
+  InstructionSimplifierVisitor(HGraph* graph, OptimizingCompilerStats* stats)
+      : HGraphVisitor(graph), stats_(stats) {}
 
  private:
   void VisitSuspendCheck(HSuspendCheck* check) OVERRIDE;
@@ -29,10 +33,13 @@ class InstructionSimplifierVisitor : public HGraphVisitor {
   void VisitTypeConversion(HTypeConversion* instruction) OVERRIDE;
   void VisitNullCheck(HNullCheck* instruction) OVERRIDE;
   void VisitArrayLength(HArrayLength* instruction) OVERRIDE;
+  void VisitCheckCast(HCheckCast* instruction) OVERRIDE;
+
+  OptimizingCompilerStats* stats_;
 };
 
 void InstructionSimplifier::Run() {
-  InstructionSimplifierVisitor visitor(graph_);
+  InstructionSimplifierVisitor visitor(graph_, stats_);
   visitor.VisitInsertionOrder();
 }
 
@@ -41,6 +48,28 @@ void InstructionSimplifierVisitor::VisitNullCheck(HNullCheck* null_check) {
   if (!obj->CanBeNull()) {
     null_check->ReplaceWith(obj);
     null_check->GetBlock()->RemoveInstruction(null_check);
+    if (stats_ != nullptr) {
+      stats_->RecordStat(MethodCompilationStat::kRemovedNullCheck);
+    }
+  }
+}
+
+void InstructionSimplifierVisitor::VisitCheckCast(HCheckCast* check_cast) {
+  HLoadClass* load_class = check_cast->InputAt(1)->AsLoadClass();
+  if (!load_class->IsResolved()) {
+    // If the class couldn't be resolve it's not safe to compare against it. It's
+    // default type would be Top which might be wider that the actual class type
+    // and thus producing wrong results.
+    return;
+  }
+  ReferenceTypeInfo obj_rti = check_cast->InputAt(0)->GetReferenceTypeInfo();
+  ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI();
+  ScopedObjectAccess soa(Thread::Current());
+  if (class_rti.IsSupertypeOf(obj_rti)) {
+    check_cast->GetBlock()->RemoveInstruction(check_cast);
+    if (stats_ != nullptr) {
+      stats_->RecordStat(MethodCompilationStat::kRemovedCheckedCast);
+    }
   }
 }
 
diff --git a/compiler/optimizing/instruction_simplifier.h b/compiler/optimizing/instruction_simplifier.h
index bca6697d05..a7ff755aed 100644
--- a/compiler/optimizing/instruction_simplifier.h
+++ b/compiler/optimizing/instruction_simplifier.h
@@ -19,6 +19,7 @@
 
 #include "nodes.h"
 #include "optimization.h"
+#include "optimizing_compiler_stats.h"
 
 namespace art {
 
@@ -27,8 +28,10 @@ namespace art {
  */
 class InstructionSimplifier : public HOptimization {
  public:
-  explicit InstructionSimplifier(HGraph* graph, const char* name = "instruction_simplifier")
-    : HOptimization(graph, true, name) {}
+  InstructionSimplifier(HGraph* graph,
+                        OptimizingCompilerStats* stats = nullptr,
+                        const char* name = "instruction_simplifier")
+    : HOptimization(graph, true, name, stats) {}
 
   void Run() OVERRIDE;
 };
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 4a574b0754..7a75d260fd 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -18,6 +18,7 @@
 
 #include "ssa_builder.h"
 #include "utils/growable_array.h"
+#include "scoped_thread_state_change.h"
 
 namespace art {
 
@@ -999,4 +1000,14 @@ void HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) {
   invoke->GetBlock()->RemoveInstruction(invoke);
 }
 
+std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs) {
+  ScopedObjectAccess soa(Thread::Current());
+  os << "["
+     << " is_top=" << rhs.IsTop()
+     << " type=" << (rhs.IsTop() ? "?" : PrettyClass(rhs.GetTypeHandle().Get()))
+     << " is_exact=" << rhs.IsExact()
+     << " ]";
+  return os;
+}
+
 }  // namespace art
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index c221404f32..e87e439b47 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -19,8 +19,11 @@
 
 #include "base/arena_object.h"
 #include "entrypoints/quick/quick_entrypoints_enum.h"
+#include "handle.h"
+#include "handle_scope.h"
 #include "invoke_type.h"
 #include "locations.h"
+#include "mirror/class.h"
 #include "offsets.h"
 #include "primitive.h"
 #include "utils/arena_bit_vector.h"
@@ -871,6 +874,88 @@ class HEnvironment : public ArenaObject<kArenaAllocMisc> {
   DISALLOW_COPY_AND_ASSIGN(HEnvironment);
 };
 
+class ReferenceTypeInfo : ValueObject {
+ public:
+  ReferenceTypeInfo() : is_exact_(false), is_top_(true) {}
+  ReferenceTypeInfo(Handle<mirror::Class> type_handle, bool is_exact) {
+    SetTypeHandle(type_handle, is_exact);
+  }
+
+  bool IsExact() const { return is_exact_; }
+  bool IsTop() const { return is_top_; }
+
+  Handle<mirror::Class> GetTypeHandle() const { return type_handle_; }
+
+  void SetTop() {
+    is_top_ = true;
+    type_handle_ = Handle<mirror::Class>();
+  }
+
+  void SetInexact() { is_exact_ = false; }
+
+  void SetTypeHandle(Handle<mirror::Class> type_handle, bool is_exact)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    is_exact_ =  is_exact;
+    if (type_handle->IsObjectClass()) {
+      is_top_ = true;
+      // Override the type handle to be consistent with the case when we get to
+      // Top but don't have the Object class available. It avoids having to guess
+      // what value the type_handle has when it's Top.
+      type_handle_ = Handle<mirror::Class>();
+    } else {
+      is_top_ = false;
+      type_handle_ = type_handle;
+    }
+  }
+
+  bool IsSupertypeOf(ReferenceTypeInfo rti) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    if (IsTop()) {
+      // Top (equivalent for java.lang.Object) is supertype of anything.
+      return true;
+    }
+    if (rti.IsTop()) {
+      // If we get here `this` is not Top() so it can't be a supertype.
+      return false;
+    }
+    return GetTypeHandle()->IsAssignableFrom(rti.GetTypeHandle().Get());
+  }
+
+  // Returns true if the type information provide the same amount of details.
+  // Note that it does not mean that the instructions have the same actual type
+  // (e.g. tops are equal but they can be the result of a merge).
+  bool IsEqual(ReferenceTypeInfo rti) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    if (IsExact() != rti.IsExact()) {
+      return false;
+    }
+    if (IsTop() && rti.IsTop()) {
+      // `Top` means java.lang.Object, so the types are equivalent.
+      return true;
+    }
+    if (IsTop() || rti.IsTop()) {
+      // If only one is top or object than they are not equivalent.
+      // NB: We need this extra check because the type_handle of `Top` is invalid
+      // and we cannot inspect its reference.
+      return false;
+    }
+
+    // Finally check the types.
+    return GetTypeHandle().Get() == rti.GetTypeHandle().Get();
+  }
+
+ private:
+  // The class of the object.
+  Handle<mirror::Class> type_handle_;
+  // Whether or not the type is exact or a superclass of the actual type.
+  bool is_exact_;
+  // A true value here means that the object type should be java.lang.Object.
+  // We don't have access to the corresponding mirror object every time so this
+  // flag acts as a substitute. When true, the TypeHandle refers to a null
+  // pointer and should not be used.
+  bool is_top_;
+};
+
+std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs);
+
 class HInstruction : public ArenaObject<kArenaAllocMisc> {
  public:
   explicit HInstruction(SideEffects side_effects)
@@ -928,6 +1013,12 @@ class HInstruction : public ArenaObject<kArenaAllocMisc> {
 
   virtual bool CanDoImplicitNullCheck() const { return false; }
 
+  void SetReferenceTypeInfo(ReferenceTypeInfo reference_type_info) {
+    reference_type_info_ = reference_type_info;
+  }
+
+  ReferenceTypeInfo GetReferenceTypeInfo() const { return reference_type_info_; }
+
   void AddUseAt(HInstruction* user, size_t index) {
     uses_.AddUse(user, index, GetBlock()->GetGraph()->GetArena());
   }
@@ -1072,6 +1163,9 @@ class HInstruction : public ArenaObject<kArenaAllocMisc> {
 
   const SideEffects side_effects_;
 
+  // TODO: for primitive types this should be marked as invalid.
+  ReferenceTypeInfo reference_type_info_;
+
   friend class HBasicBlock;
   friend class HGraph;
   friend class HInstructionList;
@@ -2684,6 +2778,20 @@ class HLoadClass : public HExpression<0> {
     return !is_referrers_class_;
   }
 
+  ReferenceTypeInfo GetLoadedClassRTI() {
+    return loaded_class_rti_;
+  }
+
+  void SetLoadedClassRTI(ReferenceTypeInfo rti) {
+    // Make sure we only set exact types (the loaded class should never be merged).
+    DCHECK(rti.IsExact());
+    loaded_class_rti_ = rti;
+  }
+
+  bool IsResolved() {
+    return loaded_class_rti_.IsExact();
+  }
+
   DECLARE_INSTRUCTION(LoadClass);
 
  private:
@@ -2694,6 +2802,8 @@ class HLoadClass : public HExpression<0> {
   // Used for code generation.
   bool generate_clinit_check_;
 
+  ReferenceTypeInfo loaded_class_rti_;
+
   DISALLOW_COPY_AND_ASSIGN(HLoadClass);
 };
 
diff --git a/compiler/optimizing/optimization.cc b/compiler/optimizing/optimization.cc
index b99f6784f7..b13e07eb22 100644
--- a/compiler/optimizing/optimization.cc
+++ b/compiler/optimizing/optimization.cc
@@ -21,6 +21,12 @@
 
 namespace art {
 
+void HOptimization::MaybeRecordStat(MethodCompilationStat compilation_stat) const {
+  if (stats_ != nullptr) {
+    stats_->RecordStat(compilation_stat);
+  }
+}
+
 void HOptimization::Check() {
   if (kIsDebugBuild) {
     if (is_in_ssa_form_) {
diff --git a/compiler/optimizing/optimization.h b/compiler/optimizing/optimization.h
index d9e082a7f3..af39e092c7 100644
--- a/compiler/optimizing/optimization.h
+++ b/compiler/optimizing/optimization.h
@@ -18,6 +18,7 @@
 #define ART_COMPILER_OPTIMIZING_OPTIMIZATION_H_
 
 #include "nodes.h"
+#include "optimizing_compiler_stats.h"
 
 namespace art {
 
@@ -34,8 +35,10 @@ class HOptimization : public ValueObject {
  public:
   HOptimization(HGraph* graph,
                 bool is_in_ssa_form,
-                const char* pass_name)
+                const char* pass_name,
+                OptimizingCompilerStats* stats = nullptr)
       : graph_(graph),
+        stats_(stats),
         is_in_ssa_form_(is_in_ssa_form),
         pass_name_(pass_name) {}
 
@@ -51,7 +54,11 @@ class HOptimization : public ValueObject {
   void Check();
 
  protected:
+  void MaybeRecordStat(MethodCompilationStat compilation_stat) const;
+
   HGraph* const graph_;
+  // Used to record stats about the optimization.
+  OptimizingCompilerStats* const stats_;
 
  private:
   // Does the analyzed graph use the SSA form?
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 080d6e01af..2fef8c7b3a 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -201,6 +201,7 @@ class OptimizingCompiler FINAL : public Compiler {
   CompiledMethod* CompileOptimized(HGraph* graph,
                                    CodeGenerator* codegen,
                                    CompilerDriver* driver,
+                                   const DexFile& dex_file,
                                    const DexCompilationUnit& dex_compilation_unit,
                                    PassInfoPrinter* pass_info) const;
 
@@ -293,13 +294,15 @@ static void RunOptimizations(HOptimization* optimizations[],
 static void RunOptimizations(HGraph* graph,
                              CompilerDriver* driver,
                              OptimizingCompilerStats* stats,
+                             const DexFile& dex_file,
                              const DexCompilationUnit& dex_compilation_unit,
-                             PassInfoPrinter* pass_info_printer) {
+                             PassInfoPrinter* pass_info_printer,
+                             StackHandleScopeCollection* handles) {
   SsaRedundantPhiElimination redundant_phi(graph);
   SsaDeadPhiElimination dead_phi(graph);
   HDeadCodeElimination dce(graph);
   HConstantFolding fold1(graph);
-  InstructionSimplifier simplify1(graph);
+  InstructionSimplifier simplify1(graph, stats);
 
   HInliner inliner(graph, dex_compilation_unit, driver, stats);
 
@@ -308,8 +311,8 @@ static void RunOptimizations(HGraph* graph,
   GVNOptimization gvn(graph, side_effects);
   LICM licm(graph, side_effects);
   BoundsCheckElimination bce(graph);
-  ReferenceTypePropagation type_propagation(graph);
-  InstructionSimplifier simplify2(graph, "instruction_simplifier_after_types");
+  ReferenceTypePropagation type_propagation(graph, dex_file, dex_compilation_unit, handles);
+  InstructionSimplifier simplify2(graph, stats, "instruction_simplifier_after_types");
 
   IntrinsicsRecognizer intrinsics(graph, dex_compilation_unit.GetDexFile(), driver);
 
@@ -348,10 +351,12 @@ static ArrayRef<const uint8_t> AlignVectorSize(std::vector<uint8_t>& vector) {
 CompiledMethod* OptimizingCompiler::CompileOptimized(HGraph* graph,
                                                      CodeGenerator* codegen,
                                                      CompilerDriver* compiler_driver,
+                                                     const DexFile& dex_file,
                                                      const DexCompilationUnit& dex_compilation_unit,
                                                      PassInfoPrinter* pass_info_printer) const {
-  RunOptimizations(
-      graph, compiler_driver, &compilation_stats_, dex_compilation_unit, pass_info_printer);
+  StackHandleScopeCollection handles(Thread::Current());
+  RunOptimizations(graph, compiler_driver, &compilation_stats_,
+                   dex_file, dex_compilation_unit, pass_info_printer, &handles);
 
   PrepareForRegisterAllocation(graph).Run();
   SsaLivenessAnalysis liveness(*graph, codegen);
@@ -515,6 +520,7 @@ CompiledMethod* OptimizingCompiler::Compile(const DexFile::CodeItem* code_item,
     return CompileOptimized(graph,
                             codegen.get(),
                             compiler_driver,
+                            dex_file,
                             dex_compilation_unit,
                             &pass_info_printer);
   } else if (shouldOptimize && RegisterAllocator::Supports(instruction_set)) {
diff --git a/compiler/optimizing/optimizing_compiler_stats.h b/compiler/optimizing/optimizing_compiler_stats.h
index cc2723df99..3ebf0f8cd2 100644
--- a/compiler/optimizing/optimizing_compiler_stats.h
+++ b/compiler/optimizing/optimizing_compiler_stats.h
@@ -43,6 +43,8 @@ enum MethodCompilationStat {
   kNotCompiledCantAccesType,
   kNotOptimizedRegisterAllocator,
   kNotCompiledUnhandledInstruction,
+  kRemovedCheckedCast,
+  kRemovedNullCheck,
   kLastStat
 };
 
@@ -96,6 +98,8 @@ class OptimizingCompilerStats {
       case kNotCompiledCantAccesType : return "kNotCompiledCantAccesType";
       case kNotOptimizedRegisterAllocator : return "kNotOptimizedRegisterAllocator";
       case kNotCompiledUnhandledInstruction : return "kNotCompiledUnhandledInstruction";
+      case kRemovedCheckedCast: return "kRemovedCheckedCast";
+      case kRemovedNullCheck: return "kRemovedNullCheck";
       default: LOG(FATAL) << "invalid stat";
     }
     return "";
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
index 4f17b6fc3b..18c0564b18 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -16,12 +16,34 @@
 
 #include "reference_type_propagation.h"
 
+#include "class_linker.h"
+#include "mirror/class-inl.h"
+#include "mirror/dex_cache.h"
+#include "scoped_thread_state_change.h"
+
 namespace art {
 
-void ReferenceTypePropagation::Run() {
-  // Compute null status for instructions.
+// TODO: Only do the analysis on reference types. We currently have to handle
+// the `null` constant, that is represented as a `HIntConstant` and therefore
+// has the Primitive::kPrimInt type.
 
-  // To properly propagate not-null info we need to visit in the dominator-based order.
+// TODO: handle:
+//  public Main ifNullTest(int count, Main a) {
+//    Main m = new Main();
+//    if (a == null) {
+//      a = m;
+//    }
+//    return a.g();
+//  }
+//  public Main ifNotNullTest(Main a) {
+//    if (a != null) {
+//      return a.g();
+//    }
+//    return new Main();
+//  }
+
+void ReferenceTypePropagation::Run() {
+  // To properly propagate type info we need to visit in the dominator-based order.
   // Reverse post order guarantees a node's dominators are visited first.
   // We take advantage of this order in `VisitBasicBlock`.
   for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
@@ -43,8 +65,89 @@ bool ReferenceTypePropagation::UpdateNullability(HPhi* phi) {
   return existing_can_be_null != new_can_be_null;
 }
 
+bool ReferenceTypePropagation::UpdateReferenceTypeInfo(HPhi* phi) {
+  ScopedObjectAccess soa(Thread::Current());
+
+  ReferenceTypeInfo existing_rti = phi->GetReferenceTypeInfo();
+  ReferenceTypeInfo new_rti = phi->InputAt(0)->GetReferenceTypeInfo();
+
+  if (new_rti.IsTop() && !new_rti.IsExact()) {
+    // Early return if we are Top and inexact.
+    phi->SetReferenceTypeInfo(new_rti);
+    return !new_rti.IsEqual(existing_rti);;
+  }
+
+  for (size_t i = 1; i < phi->InputCount(); i++) {
+    ReferenceTypeInfo input_rti = phi->InputAt(i)->GetReferenceTypeInfo();
+
+    if (!input_rti.IsExact()) {
+      new_rti.SetInexact();
+    }
+
+    if (input_rti.IsTop()) {
+      new_rti.SetTop();
+    }
+
+    if (new_rti.IsTop()) {
+      if (!new_rti.IsExact()) {
+        break;
+      } else {
+        continue;
+      }
+    }
+
+    if (new_rti.GetTypeHandle().Get() == input_rti.GetTypeHandle().Get()) {
+      // nothing to do if we have the same type
+    } else if (input_rti.IsSupertypeOf(new_rti)) {
+      new_rti.SetTypeHandle(input_rti.GetTypeHandle(), false);
+    } else if (new_rti.IsSupertypeOf(input_rti)) {
+      new_rti.SetInexact();
+    } else {
+      // TODO: Find common parent.
+      new_rti.SetTop();
+      new_rti.SetInexact();
+    }
+  }
+
+  phi->SetReferenceTypeInfo(new_rti);
+  return !new_rti.IsEqual(existing_rti);
+}
+
+void ReferenceTypePropagation::VisitNewInstance(HNewInstance* instr) {
+  ScopedObjectAccess soa(Thread::Current());
+  mirror::DexCache* dex_cache = dex_compilation_unit_.GetClassLinker()->FindDexCache(dex_file_);
+  // Get type from dex cache assuming it was populated by the verifier.
+  mirror::Class* resolved_class = dex_cache->GetResolvedType(instr->GetTypeIndex());
+  if (resolved_class != nullptr) {
+    MutableHandle<mirror::Class> handle = handles_->NewHandle(resolved_class);
+    instr->SetReferenceTypeInfo(ReferenceTypeInfo(handle, true));
+  }
+}
+
+void ReferenceTypePropagation::VisitLoadClass(HLoadClass* instr) {
+  ScopedObjectAccess soa(Thread::Current());
+  mirror::DexCache* dex_cache = dex_compilation_unit_.GetClassLinker()->FindDexCache(dex_file_);
+  // Get type from dex cache assuming it was populated by the verifier.
+  mirror::Class* resolved_class = dex_cache->GetResolvedType(instr->GetTypeIndex());
+  if (resolved_class != nullptr) {
+    Handle<mirror::Class> handle = handles_->NewHandle(resolved_class);
+    instr->SetLoadedClassRTI(ReferenceTypeInfo(handle, true));
+  }
+  Handle<mirror::Class> class_handle = handles_->NewHandle(mirror::Class::GetJavaLangClass());
+  instr->SetReferenceTypeInfo(ReferenceTypeInfo(class_handle, true));
+}
 
 void ReferenceTypePropagation::VisitBasicBlock(HBasicBlock* block) {
+  // TODO: handle other instructions that give type info
+  // (NewArray/Call/Field accesses/array accesses)
+  for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
+    HInstruction* instr = it.Current();
+    if (instr->IsNewInstance()) {
+      VisitNewInstance(instr->AsNewInstance());
+    } else if (instr->IsLoadClass()) {
+      VisitLoadClass(instr->AsLoadClass());
+    }
+  }
   if (block->IsLoopHeader()) {
     for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
       // Set the initial type for the phi. Use the non back edge input for reaching
@@ -53,6 +156,7 @@ void ReferenceTypePropagation::VisitBasicBlock(HBasicBlock* block) {
       if (phi->GetType() == Primitive::kPrimNot) {
         AddToWorklist(phi);
         phi->SetCanBeNull(phi->InputAt(0)->CanBeNull());
+        phi->SetReferenceTypeInfo(phi->InputAt(0)->GetReferenceTypeInfo());
       }
     }
   } else {
@@ -65,6 +169,7 @@ void ReferenceTypePropagation::VisitBasicBlock(HBasicBlock* block) {
       HPhi* phi = it.Current()->AsPhi();
       if (phi->GetType() == Primitive::kPrimNot) {
         UpdateNullability(phi);
+        UpdateReferenceTypeInfo(phi);
       }
     }
   }
@@ -73,7 +178,7 @@ void ReferenceTypePropagation::VisitBasicBlock(HBasicBlock* block) {
 void ReferenceTypePropagation::ProcessWorklist() {
   while (!worklist_.IsEmpty()) {
     HPhi* instruction = worklist_.Pop();
-    if (UpdateNullability(instruction)) {
+    if (UpdateNullability(instruction) || UpdateReferenceTypeInfo(instruction)) {
       AddDependentInstructionsToWorklist(instruction);
     }
   }
diff --git a/compiler/optimizing/reference_type_propagation.h b/compiler/optimizing/reference_type_propagation.h
index a74319d0c5..1ec5df345b 100644
--- a/compiler/optimizing/reference_type_propagation.h
+++ b/compiler/optimizing/reference_type_propagation.h
@@ -17,6 +17,8 @@
 #ifndef ART_COMPILER_OPTIMIZING_REFERENCE_TYPE_PROPAGATION_H_
 #define ART_COMPILER_OPTIMIZING_REFERENCE_TYPE_PROPAGATION_H_
 
+#include "driver/dex_compilation_unit.h"
+#include "handle_scope-inl.h"
 #include "nodes.h"
 #include "optimization.h"
 
@@ -24,22 +26,34 @@ namespace art {
 
 /**
  * Propagates reference types to instructions.
- * TODO: Currently only nullability is computed.
  */
 class ReferenceTypePropagation : public HOptimization {
  public:
-  explicit ReferenceTypePropagation(HGraph* graph)
+  ReferenceTypePropagation(HGraph* graph,
+                           const DexFile& dex_file,
+                           const DexCompilationUnit& dex_compilation_unit,
+                           StackHandleScopeCollection* handles)
     : HOptimization(graph, true, "reference_type_propagation"),
+      dex_file_(dex_file),
+      dex_compilation_unit_(dex_compilation_unit),
+      handles_(handles),
       worklist_(graph->GetArena(), kDefaultWorklistSize) {}
 
   void Run() OVERRIDE;
 
  private:
+  void VisitNewInstance(HNewInstance* new_instance);
+  void VisitLoadClass(HLoadClass* load_class);
   void VisitBasicBlock(HBasicBlock* block);
   void ProcessWorklist();
   void AddToWorklist(HPhi* phi);
   void AddDependentInstructionsToWorklist(HPhi* phi);
   bool UpdateNullability(HPhi* phi);
+  bool UpdateReferenceTypeInfo(HPhi* phi);
+
+  const DexFile& dex_file_;
+  const DexCompilationUnit& dex_compilation_unit_;
+  StackHandleScopeCollection* handles_;
 
   GrowableArray<HPhi*> worklist_;
 
diff --git a/runtime/handle_scope.h b/runtime/handle_scope.h
index 782bbeaabc..a8365782a1 100644
--- a/runtime/handle_scope.h
+++ b/runtime/handle_scope.h
@@ -17,6 +17,8 @@
 #ifndef ART_RUNTIME_HANDLE_SCOPE_H_
 #define ART_RUNTIME_HANDLE_SCOPE_H_
 
+#include <stack>
+
 #include "base/logging.h"
 #include "base/macros.h"
 #include "handle.h"
@@ -176,6 +178,54 @@ class PACKED(4) StackHandleScope FINAL : public HandleScope {
   template<size_t kNumRefs> friend class StackHandleScope;
 };
 
+// Utility class to manage a collection (stack) of StackHandleScope. All the managed
+// scope handle have the same fixed sized.
+// Calls to NewHandle will create a new handle inside the top StackHandleScope.
+// When the handle scope becomes full a new one is created and push on top of the
+// previous.
+//
+// NB:
+// - it is not safe to use the *same* StackHandleScopeCollection intermix with
+// other StackHandleScopes.
+// - this is a an easy way around implementing a full ZoneHandleScope to manage an
+// arbitrary number of handles.
+class StackHandleScopeCollection {
+ public:
+  explicit StackHandleScopeCollection(Thread* const self) :
+      self_(self),
+      current_scope_num_refs_(0) {
+  }
+
+  ~StackHandleScopeCollection() {
+    while (!scopes_.empty()) {
+      delete scopes_.top();
+      scopes_.pop();
+    }
+  }
+
+  template<class T>
+  MutableHandle<T> NewHandle(T* object) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    if (scopes_.empty() || current_scope_num_refs_ >= kNumReferencesPerScope) {
+      StackHandleScope<kNumReferencesPerScope>* scope =
+          new StackHandleScope<kNumReferencesPerScope>(self_);
+      scopes_.push(scope);
+      current_scope_num_refs_ = 0;
+    }
+    current_scope_num_refs_++;
+    return scopes_.top()->NewHandle(object);
+  }
+
+ private:
+  static constexpr size_t kNumReferencesPerScope = 4;
+
+  Thread* const self_;
+
+  std::stack<StackHandleScope<kNumReferencesPerScope>*> scopes_;
+  size_t current_scope_num_refs_;
+
+  DISALLOW_COPY_AND_ASSIGN(StackHandleScopeCollection);
+};
+
 }  // namespace art
 
 #endif  // ART_RUNTIME_HANDLE_SCOPE_H_
diff --git a/test/450-checker-types/expected.txt b/test/450-checker-types/expected.txt
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/test/450-checker-types/expected.txt
diff --git a/test/450-checker-types/info.txt b/test/450-checker-types/info.txt
new file mode 100644
index 0000000000..3dc3ccb6a1
--- /dev/null
+++ b/test/450-checker-types/info.txt
@@ -0,0 +1 @@
+Checker test for testing checked cast elimination.
diff --git a/test/450-checker-types/src/Main.java b/test/450-checker-types/src/Main.java
new file mode 100644
index 0000000000..a0d8ed5576
--- /dev/null
+++ b/test/450-checker-types/src/Main.java
@@ -0,0 +1,181 @@
+/*
+* Copyright (C) 2015 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.
+*/
+
+
+interface Interface {
+  void f();
+}
+
+class Super implements Interface {
+  public void f() {
+    throw new RuntimeException();
+  }
+}
+
+class SubclassA extends Super {
+  public void f() {
+    throw new RuntimeException();
+  }
+
+  public String h() {
+    throw new RuntimeException();
+  }
+
+  void g() {
+    throw new RuntimeException();
+  }
+}
+
+class SubclassC extends SubclassA {
+}
+
+class SubclassB extends Super {
+  public void f() {
+    throw new RuntimeException();
+  }
+
+  void g() {
+    throw new RuntimeException();
+  }
+}
+
+public class Main {
+
+  // CHECK-START: void Main.testSimpleRemove() instruction_simplifier_after_types (before)
+  // CHECK:         CheckCast
+
+  // CHECK-START: void Main.testSimpleRemove() instruction_simplifier_after_types (after)
+  // CHECK-NOT:     CheckCast
+  public void testSimpleRemove() {
+    Super s = new SubclassA();
+    ((SubclassA)s).g();
+  }
+
+  // CHECK-START: void Main.testSimpleKeep(Super) instruction_simplifier_after_types (before)
+  // CHECK:         CheckCast
+
+  // CHECK-START: void Main.testSimpleKeep(Super) instruction_simplifier_after_types (after)
+  // CHECK:         CheckCast
+  public void testSimpleKeep(Super s) {
+    ((SubclassA)s).f();
+  }
+
+  // CHECK-START: java.lang.String Main.testClassRemove() instruction_simplifier_after_types (before)
+  // CHECK:         CheckCast
+
+  // CHECK-START: java.lang.String Main.testClassRemove() instruction_simplifier_after_types (after)
+  // CHECK-NOT:     CheckCast
+  public String testClassRemove() {
+    Object s = SubclassA.class;
+    return ((Class)s).getName();
+  }
+
+  // CHECK-START: java.lang.String Main.testClassKeep() instruction_simplifier_after_types (before)
+  // CHECK:         CheckCast
+
+  // CHECK-START: java.lang.String Main.testClassKeep() instruction_simplifier_after_types (after)
+  // CHECK:         CheckCast
+  public String testClassKeep() {
+    Object s = SubclassA.class;
+    return ((SubclassA)s).h();
+  }
+
+  // CHECK-START: void Main.testIfRemove(int) instruction_simplifier_after_types (before)
+  // CHECK:         CheckCast
+
+  // CHECK-START: void Main.testIfRemove(int) instruction_simplifier_after_types (after)
+  // CHECK-NOT:     CheckCast
+  public void testIfRemove(int x) {
+    Super s;
+    if (x % 2 == 0) {
+      s = new SubclassA();
+    } else {
+      s = new SubclassC();
+    }
+    ((SubclassA)s).g();
+  }
+
+  // CHECK-START: void Main.testIfKeep(int) instruction_simplifier_after_types (before)
+  // CHECK:         CheckCast
+
+  // CHECK-START: void Main.testIfKeep(int) instruction_simplifier_after_types (after)
+  // CHECK:         CheckCast
+  public void testIfKeep(int x) {
+    Super s;
+    if (x % 2 == 0) {
+      s = new SubclassA();
+    } else {
+      s = new SubclassB();
+    }
+    ((SubclassA)s).g();
+  }
+
+  // CHECK-START: void Main.testForRemove(int) instruction_simplifier_after_types (before)
+  // CHECK:         CheckCast
+
+  // CHECK-START: void Main.testForRemove(int) instruction_simplifier_after_types (after)
+  // CHECK-NOT:     CheckCast
+  public void testForRemove(int x) {
+    Super s = new SubclassA();
+    for (int i = 0 ; i < x; i++) {
+      if (x % 2 == 0) {
+        s = new SubclassC();
+      }
+    }
+    ((SubclassA)s).g();
+  }
+
+  // CHECK-START: void Main.testForKeep(int) instruction_simplifier_after_types (before)
+  // CHECK:         CheckCast
+
+  // CHECK-START: void Main.testForKeep(int) instruction_simplifier_after_types (after)
+  // CHECK:         CheckCast
+  public void testForKeep(int x) {
+    Super s = new SubclassA();
+    for (int i = 0 ; i < x; i++) {
+      if (x % 2 == 0) {
+        s = new SubclassC();
+      }
+    }
+    ((SubclassC)s).g();
+  }
+
+  // CHECK-START: void Main.testPhiFromCall(int) instruction_simplifier_after_types (before)
+  // CHECK:         CheckCast
+
+  // CHECK-START: void Main.testPhiFromCall(int) instruction_simplifier_after_types (after)
+  // CHECK:         CheckCast
+  public void testPhiFromCall(int i) {
+    Object x;
+    if (i % 2 == 0) {
+      x = new SubclassC();
+    } else {
+      x = newObject();  // this one will have an unknown type.
+    }
+    ((SubclassC)x).g();
+  }
+
+  public Object newObject() {
+    try {
+      return Object.class.newInstance();
+    } catch (Exception e) {
+      return null;
+    }
+  }
+
+  public static void main(String[] args) {
+  }
+}