diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 46d821e..edc271a 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -469,19 +469,14 @@
         if (instruction->IsLoadClass()) {
           ReferenceTypeInfo info = instruction->AsLoadClass()->GetLoadedClassRTI();
           ScopedObjectAccess soa(Thread::Current());
-          if (info.GetTypeHandle().GetReference() != nullptr) {
-            StartAttributeStream("klass") << PrettyDescriptor(info.GetTypeHandle().Get());
-          } else {
-            StartAttributeStream("klass") << "unresolved";
-          }
+          DCHECK(info.IsValid()) << "Invalid RTI for " << instruction->DebugName();
+          StartAttributeStream("klass") << PrettyDescriptor(info.GetTypeHandle().Get());
+          StartAttributeStream("exact") << std::boolalpha << info.IsExact() << std::noboolalpha;
         } else {
           ReferenceTypeInfo info = instruction->GetReferenceTypeInfo();
-          if (info.IsTop()) {
-            StartAttributeStream("klass") << "java.lang.Object";
-          } else {
-            ScopedObjectAccess soa(Thread::Current());
-            StartAttributeStream("klass") << PrettyDescriptor(info.GetTypeHandle().Get());
-          }
+          ScopedObjectAccess soa(Thread::Current());
+          DCHECK(info.IsValid()) << "Invalid RTI for " << instruction->DebugName();
+          StartAttributeStream("klass") << PrettyDescriptor(info.GetTypeHandle().Get());
           StartAttributeStream("can_be_null")
               << std::boolalpha << instruction->CanBeNull() << std::noboolalpha;
           StartAttributeStream("exact") << std::boolalpha << info.IsExact() << std::noboolalpha;
diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc
index c185b58..644f45c 100644
--- a/compiler/optimizing/inliner.cc
+++ b/compiler/optimizing/inliner.cc
@@ -109,10 +109,8 @@
     receiver = receiver->InputAt(0);
   }
   ReferenceTypeInfo info = receiver->GetReferenceTypeInfo();
-  if (info.IsTop()) {
-    // We have no information on the receiver.
-    return nullptr;
-  } else if (!info.IsExact()) {
+  DCHECK(info.IsValid()) << "Invalid RTI for " << receiver->DebugName();
+  if (!info.IsExact()) {
     // We currently only support inlining with known receivers.
     // TODO: Remove this check, we should be able to inline final methods
     // on unknown receivers.
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index b30b6c7..1089812 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -195,16 +195,16 @@
 // Returns whether doing a type test between the class of `object` against `klass` has
 // a statically known outcome. The result of the test is stored in `outcome`.
 static bool TypeCheckHasKnownOutcome(HLoadClass* klass, HInstruction* object, bool* outcome) {
-  if (!klass->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.
+  ReferenceTypeInfo obj_rti = object->GetReferenceTypeInfo();
+  ScopedObjectAccess soa(Thread::Current());
+  if (!obj_rti.IsValid()) {
+    // We run the simplifier before the reference type propagation so type info might not be
+    // available.
     return false;
   }
 
-  ReferenceTypeInfo obj_rti = object->GetReferenceTypeInfo();
   ReferenceTypeInfo class_rti = klass->GetLoadedClassRTI();
-  ScopedObjectAccess soa(Thread::Current());
+  DCHECK(class_rti.IsValid() && class_rti.IsExact());
   if (class_rti.IsSupertypeOf(obj_rti)) {
     *outcome = true;
     return true;
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 519fa00..296c1b0 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -1757,11 +1757,39 @@
   }
 }
 
+void HInstruction::SetReferenceTypeInfo(ReferenceTypeInfo rti) {
+  if (kIsDebugBuild) {
+    DCHECK_EQ(GetType(), Primitive::kPrimNot);
+    ScopedObjectAccess soa(Thread::Current());
+    DCHECK(rti.IsValid()) << "Invalid RTI for " << DebugName();
+    if (IsBoundType()) {
+      // Having the test here spares us from making the method virtual just for
+      // the sake of a DCHECK.
+      ReferenceTypeInfo upper_bound_rti = AsBoundType()->GetUpperBound();
+      DCHECK(upper_bound_rti.IsSupertypeOf(rti))
+          << " upper_bound_rti: " << upper_bound_rti
+          << " rti: " << rti;
+      DCHECK(!upper_bound_rti.GetTypeHandle()->IsFinal() || rti.IsExact());
+    }
+  }
+  reference_type_info_ = rti;
+}
+
+ReferenceTypeInfo::ReferenceTypeInfo() : type_handle_(TypeHandle()), is_exact_(false) {}
+
+ReferenceTypeInfo::ReferenceTypeInfo(TypeHandle type_handle, bool is_exact)
+    : type_handle_(type_handle), is_exact_(is_exact) {
+  if (kIsDebugBuild) {
+    ScopedObjectAccess soa(Thread::Current());
+    DCHECK(IsValidHandle(type_handle));
+  }
+}
+
 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_valid=" << rhs.IsValid()
+     << " type=" << (!rhs.IsValid() ? "?" : PrettyClass(rhs.GetTypeHandle().Get()))
      << " is_exact=" << rhs.IsExact()
      << " ]";
   return os;
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 5c5cecc..151da7f 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -1460,79 +1460,64 @@
  public:
   typedef Handle<mirror::Class> TypeHandle;
 
-  static ReferenceTypeInfo Create(TypeHandle type_handle, bool is_exact)
-      SHARED_REQUIRES(Locks::mutator_lock_) {
-    if (type_handle->IsObjectClass()) {
-      // 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.
-      return ReferenceTypeInfo(TypeHandle(), is_exact, true);
-    } else {
-      return ReferenceTypeInfo(type_handle, is_exact, false);
-    }
+  static ReferenceTypeInfo Create(TypeHandle type_handle, bool is_exact) {
+    // The constructor will check that the type_handle is valid.
+    return ReferenceTypeInfo(type_handle, is_exact);
   }
 
-  static ReferenceTypeInfo CreateTop(bool is_exact) {
-    return ReferenceTypeInfo(TypeHandle(), is_exact, true);
+  static ReferenceTypeInfo CreateInvalid() { return ReferenceTypeInfo(); }
+
+  static bool IsValidHandle(TypeHandle handle) SHARED_REQUIRES(Locks::mutator_lock_) {
+    return handle.GetReference() != nullptr;
   }
 
+  bool IsValid() const SHARED_REQUIRES(Locks::mutator_lock_) {
+    return IsValidHandle(type_handle_);
+  }
   bool IsExact() const { return is_exact_; }
-  bool IsTop() const { return is_top_; }
+
+  bool IsObjectClass() const SHARED_REQUIRES(Locks::mutator_lock_) {
+    DCHECK(IsValid());
+    return GetTypeHandle()->IsObjectClass();
+  }
   bool IsInterface() const SHARED_REQUIRES(Locks::mutator_lock_) {
-    return !IsTop() && GetTypeHandle()->IsInterface();
+    DCHECK(IsValid());
+    return GetTypeHandle()->IsInterface();
   }
 
   Handle<mirror::Class> GetTypeHandle() const { return type_handle_; }
 
   bool IsSupertypeOf(ReferenceTypeInfo rti) const SHARED_REQUIRES(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;
-    }
+    DCHECK(IsValid());
+    DCHECK(rti.IsValid());
     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).
+  // (because the type can be the result of a merge).
   bool IsEqual(ReferenceTypeInfo rti) SHARED_REQUIRES(Locks::mutator_lock_) {
-    if (IsExact() != rti.IsExact()) {
-      return false;
-    }
-    if (IsTop() && rti.IsTop()) {
-      // `Top` means java.lang.Object, so the types are equivalent.
+    if (!IsValid() && !rti.IsValid()) {
+      // Invalid types are equal.
       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.
+    if (!IsValid() || !rti.IsValid()) {
+      // One is valid, the other not.
       return false;
     }
-
-    // Finally check the types.
-    return GetTypeHandle().Get() == rti.GetTypeHandle().Get();
+    return IsExact() == rti.IsExact()
+        && GetTypeHandle().Get() == rti.GetTypeHandle().Get();
   }
 
  private:
-  ReferenceTypeInfo() : ReferenceTypeInfo(TypeHandle(), false, true) {}
-  ReferenceTypeInfo(TypeHandle type_handle, bool is_exact, bool is_top)
-      : type_handle_(type_handle), is_exact_(is_exact), is_top_(is_top) {}
+  ReferenceTypeInfo();
+  ReferenceTypeInfo(TypeHandle type_handle, bool is_exact);
 
   // The class of the object.
   TypeHandle type_handle_;
   // Whether or not the type is exact or a superclass of the actual type.
   // Whether or not we have any information about this 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);
@@ -1550,7 +1535,7 @@
         live_interval_(nullptr),
         lifetime_position_(kNoLifetime),
         side_effects_(side_effects),
-        reference_type_info_(ReferenceTypeInfo::CreateTop(/* is_exact */ false)) {}
+        reference_type_info_(ReferenceTypeInfo::CreateInvalid()) {}
 
   virtual ~HInstruction() {}
 
@@ -1607,10 +1592,7 @@
     return false;
   }
 
-  void SetReferenceTypeInfo(ReferenceTypeInfo reference_type_info) {
-    DCHECK_EQ(GetType(), Primitive::kPrimNot);
-    reference_type_info_ = reference_type_info;
-  }
+  void SetReferenceTypeInfo(ReferenceTypeInfo rti);
 
   ReferenceTypeInfo GetReferenceTypeInfo() const {
     DCHECK_EQ(GetType(), Primitive::kPrimNot);
@@ -3905,7 +3887,7 @@
         is_referrers_class_(is_referrers_class),
         dex_pc_(dex_pc),
         generate_clinit_check_(false),
-        loaded_class_rti_(ReferenceTypeInfo::CreateTop(/* is_exact */ false)) {
+        loaded_class_rti_(ReferenceTypeInfo::CreateInvalid()) {
     SetRawInputAt(0, current_method);
   }
 
@@ -3956,10 +3938,6 @@
     loaded_class_rti_ = rti;
   }
 
-  bool IsResolved() {
-    return loaded_class_rti_.IsExact();
-  }
-
   const DexFile& GetDexFile() { return dex_file_; }
 
   bool NeedsDexCache() const OVERRIDE { return !is_referrers_class_; }
@@ -4202,6 +4180,8 @@
 
 class HBoundType : public HExpression<1> {
  public:
+  // Constructs an HBoundType with the given upper_bound.
+  // Ensures that the upper_bound is valid.
   HBoundType(HInstruction* input, ReferenceTypeInfo upper_bound, bool upper_can_be_null)
       : HExpression(Primitive::kPrimNot, SideEffects::None()),
         upper_bound_(upper_bound),
@@ -4209,6 +4189,7 @@
         can_be_null_(upper_can_be_null) {
     DCHECK_EQ(input->GetType(), Primitive::kPrimNot);
     SetRawInputAt(0, input);
+    SetReferenceTypeInfo(upper_bound_);
   }
 
   // GetUpper* should only be used in reference type propagation.
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
index 9d0d412..da3d5e9 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -25,13 +25,26 @@
 
 class RTPVisitor : public HGraphDelegateVisitor {
  public:
-  RTPVisitor(HGraph* graph, StackHandleScopeCollection* handles)
+  RTPVisitor(HGraph* graph,
+             StackHandleScopeCollection* handles,
+             GrowableArray<HInstruction*>* worklist,
+             ReferenceTypeInfo::TypeHandle object_class_handle,
+             ReferenceTypeInfo::TypeHandle class_class_handle,
+             ReferenceTypeInfo::TypeHandle string_class_handle)
     : HGraphDelegateVisitor(graph),
-      handles_(handles) {}
+      handles_(handles),
+      object_class_handle_(object_class_handle),
+      class_class_handle_(class_class_handle),
+      string_class_handle_(string_class_handle),
+      worklist_(worklist) {}
 
+  void VisitNullConstant(HNullConstant* null_constant) OVERRIDE;
   void VisitNewInstance(HNewInstance* new_instance) OVERRIDE;
   void VisitLoadClass(HLoadClass* load_class) OVERRIDE;
+  void VisitClinitCheck(HClinitCheck* clinit_check) OVERRIDE;
+  void VisitLoadString(HLoadString* instr) OVERRIDE;
   void VisitNewArray(HNewArray* instr) OVERRIDE;
+  void VisitParameterValue(HParameterValue* instr) OVERRIDE;
   void UpdateFieldAccessTypeInfo(HInstruction* instr, const FieldInfo& info);
   void SetClassAsTypeInfo(HInstruction* instr, mirror::Class* klass, bool is_exact);
   void VisitInstanceFieldGet(HInstanceFieldGet* instr) OVERRIDE;
@@ -39,6 +52,8 @@
   void VisitInvoke(HInvoke* instr) OVERRIDE;
   void VisitArrayGet(HArrayGet* instr) OVERRIDE;
   void VisitCheckCast(HCheckCast* instr) OVERRIDE;
+  void VisitNullCheck(HNullCheck* instr) OVERRIDE;
+  void VisitFakeString(HFakeString* instr) OVERRIDE;
   void UpdateReferenceTypeInfo(HInstruction* instr,
                                uint16_t type_idx,
                                const DexFile& dex_file,
@@ -46,8 +61,33 @@
 
  private:
   StackHandleScopeCollection* handles_;
+  ReferenceTypeInfo::TypeHandle object_class_handle_;
+  ReferenceTypeInfo::TypeHandle class_class_handle_;
+  ReferenceTypeInfo::TypeHandle string_class_handle_;
+  GrowableArray<HInstruction*>* worklist_;
+
+  static constexpr size_t kDefaultWorklistSize = 8;
 };
 
+ReferenceTypePropagation::ReferenceTypePropagation(HGraph* graph,
+                                                   StackHandleScopeCollection* handles,
+                                                   const char* name)
+    : HOptimization(graph, name),
+      handles_(handles),
+      worklist_(graph->GetArena(), kDefaultWorklistSize) {
+  ClassLinker* linker = Runtime::Current()->GetClassLinker();
+  object_class_handle_ = handles_->NewHandle(linker->GetClassRoot(ClassLinker::kJavaLangObject));
+  string_class_handle_ = handles_->NewHandle(linker->GetClassRoot(ClassLinker::kJavaLangString));
+  class_class_handle_ = handles_->NewHandle(linker->GetClassRoot(ClassLinker::kJavaLangClass));
+
+  if (kIsDebugBuild) {
+    ScopedObjectAccess soa(Thread::Current());
+    DCHECK(ReferenceTypeInfo::IsValidHandle(object_class_handle_));
+    DCHECK(ReferenceTypeInfo::IsValidHandle(class_class_handle_));
+    DCHECK(ReferenceTypeInfo::IsValidHandle(string_class_handle_));
+  }
+}
+
 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.
@@ -56,24 +96,51 @@
     VisitBasicBlock(it.Current());
   }
   ProcessWorklist();
+
+  if (kIsDebugBuild) {
+    // TODO: move this to the graph checker.
+    ScopedObjectAccess soa(Thread::Current());
+    for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+      HBasicBlock* block = it.Current();
+      for (HInstructionIterator iti(block->GetInstructions()); !iti.Done(); iti.Advance()) {
+        HInstruction* instr = iti.Current();
+        if (instr->GetType() == Primitive::kPrimNot) {
+          DCHECK(instr->GetReferenceTypeInfo().IsValid())
+              << "Invalid RTI for instruction: " << instr->DebugName();
+          if (instr->IsBoundType()) {
+            DCHECK(instr->AsBoundType()->GetUpperBound().IsValid());
+          } else if (instr->IsLoadClass()) {
+            DCHECK(instr->AsLoadClass()->GetReferenceTypeInfo().IsExact());
+            DCHECK(instr->AsLoadClass()->GetLoadedClassRTI().IsValid());
+          } else if (instr->IsNullCheck()) {
+            DCHECK(instr->GetReferenceTypeInfo().IsEqual(instr->InputAt(0)->GetReferenceTypeInfo()))
+                << "NullCheck " << instr->GetReferenceTypeInfo()
+                << "Input(0) " << instr->InputAt(0)->GetReferenceTypeInfo();
+          }
+        }
+      }
+    }
+  }
 }
 
 void ReferenceTypePropagation::VisitBasicBlock(HBasicBlock* block) {
-  // TODO: handle other instructions that give type info
-  // (array accesses)
+  RTPVisitor visitor(graph_,
+                     handles_,
+                     &worklist_,
+                     object_class_handle_,
+                     class_class_handle_,
+                     string_class_handle_);
+  // Handle Phis first as there might be instructions in the same block who depend on them.
+  for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
+    VisitPhi(it.Current()->AsPhi());
+  }
 
-  RTPVisitor visitor(graph_, handles_);
-  // Initialize exact types first for faster convergence.
+  // Handle instructions.
   for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
     HInstruction* instr = it.Current();
     instr->Accept(&visitor);
   }
 
-  // Handle Phis.
-  for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
-    VisitPhi(it.Current()->AsPhi());
-  }
-
   // Add extra nodes to bound types.
   BoundTypeForIfNotNull(block);
   BoundTypeForIfInstanceOf(block);
@@ -91,10 +158,10 @@
   ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI();
   HBoundType* bound_type = new (arena) HBoundType(obj, class_rti, upper_can_be_null);
   // Narrow the type as much as possible.
-  if (load_class->IsResolved() && class_rti.GetTypeHandle()->IsFinal()) {
+  if (class_rti.GetTypeHandle()->IsFinal()) {
     bound_type->SetReferenceTypeInfo(
         ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ true));
-  } else if (!load_class->IsResolved() || class_rti.IsSupertypeOf(obj_rti)) {
+  } else if (obj_rti.IsValid() && class_rti.IsSupertypeOf(obj_rti)) {
     bound_type->SetReferenceTypeInfo(obj_rti);
   } else {
     bound_type->SetReferenceTypeInfo(
@@ -185,10 +252,14 @@
       if (bound_type == nullptr) {
         ScopedObjectAccess soa(Thread::Current());
         HInstruction* insert_point = notNullBlock->GetFirstInstruction();
-        ReferenceTypeInfo object_rti = ReferenceTypeInfo::CreateTop(false);
+        ReferenceTypeInfo object_rti = ReferenceTypeInfo::Create(
+            object_class_handle_, /* is_exact */ true);
         if (ShouldCreateBoundType(insert_point, obj, object_rti, nullptr, notNullBlock)) {
           bound_type = new (graph_->GetArena()) HBoundType(
               obj, object_rti, /* bound_can_be_null */ false);
+          if (obj->GetReferenceTypeInfo().IsValid()) {
+            bound_type->SetReferenceTypeInfo(obj->GetReferenceTypeInfo());
+          }
           notNullBlock->InsertInstructionBefore(bound_type, insert_point);
         } else {
           // We already have a bound type on the position we would need to insert
@@ -275,11 +346,32 @@
 void RTPVisitor::SetClassAsTypeInfo(HInstruction* instr,
                                     mirror::Class* klass,
                                     bool is_exact) {
-  if (klass != nullptr) {
+  if (instr->IsInvokeStaticOrDirect() && instr->AsInvokeStaticOrDirect()->IsStringInit()) {
+    // Calls to String.<init> are replaced with a StringFactory.
+    if (kIsDebugBuild) {
+      ScopedObjectAccess soa(Thread::Current());
+      ClassLinker* cl = Runtime::Current()->GetClassLinker();
+      mirror::DexCache* dex_cache = cl->FindDexCache(instr->AsInvoke()->GetDexFile());
+      ArtMethod* method = dex_cache->GetResolvedMethod(
+          instr->AsInvoke()->GetDexMethodIndex(), cl->GetImagePointerSize());
+      DCHECK(method != nullptr);
+      mirror::Class* declaring_class = method->GetDeclaringClass();
+      DCHECK(declaring_class != nullptr);
+      DCHECK(declaring_class->IsStringClass())
+          << "Expected String class: " << PrettyDescriptor(declaring_class);
+      DCHECK(method->IsConstructor())
+          << "Expected String.<init>: " << PrettyMethod(method);
+    }
+    instr->SetReferenceTypeInfo(
+        ReferenceTypeInfo::Create(string_class_handle_, /* is_exact */ true));
+  } else if (klass != nullptr) {
     ScopedObjectAccess soa(Thread::Current());
-    MutableHandle<mirror::Class> handle = handles_->NewHandle(klass);
+    ReferenceTypeInfo::TypeHandle handle = handles_->NewHandle(klass);
     is_exact = is_exact || klass->IsFinal();
     instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(handle, is_exact));
+  } else {
+    instr->SetReferenceTypeInfo(
+        ReferenceTypeInfo::Create(object_class_handle_, /* is_exact */ false));
   }
 }
 
@@ -295,6 +387,11 @@
   SetClassAsTypeInfo(instr, dex_cache->GetResolvedType(type_idx), is_exact);
 }
 
+void RTPVisitor::VisitNullConstant(HNullConstant* instr) {
+  instr->SetReferenceTypeInfo(
+      ReferenceTypeInfo::Create(object_class_handle_, /* is_exact */ false));
+}
+
 void RTPVisitor::VisitNewInstance(HNewInstance* instr) {
   UpdateReferenceTypeInfo(instr, instr->GetTypeIndex(), instr->GetDexFile(), /* is_exact */ true);
 }
@@ -303,6 +400,13 @@
   UpdateReferenceTypeInfo(instr, instr->GetTypeIndex(), instr->GetDexFile(), /* is_exact */ true);
 }
 
+void RTPVisitor::VisitParameterValue(HParameterValue* instr) {
+  if (instr->GetType() == Primitive::kPrimNot) {
+    // TODO: parse the signature and add precise types for the parameters.
+    SetClassAsTypeInfo(instr, nullptr, /* is_exact */ false);
+  }
+}
+
 void RTPVisitor::UpdateFieldAccessTypeInfo(HInstruction* instr,
                                            const FieldInfo& info) {
   // The field index is unknown only during tests.
@@ -314,10 +418,10 @@
   ClassLinker* cl = Runtime::Current()->GetClassLinker();
   mirror::DexCache* dex_cache = cl->FindDexCache(info.GetDexFile());
   ArtField* field = cl->GetResolvedField(info.GetFieldIndex(), dex_cache);
-  if (field != nullptr) {
-    mirror::Class* klass = field->GetType<false>();
-    SetClassAsTypeInfo(instr, klass, /* is_exact */ false);
-  }
+  // TODO: There are certain cases where we can't resolve the field.
+  // b/21914925 is open to keep track of a repro case for this issue.
+  mirror::Class* klass = (field == nullptr) ? nullptr : field->GetType<false>();
+  SetClassAsTypeInfo(instr, klass, /* is_exact */ false);
 }
 
 void RTPVisitor::VisitInstanceFieldGet(HInstanceFieldGet* instr) {
@@ -334,12 +438,29 @@
       Runtime::Current()->GetClassLinker()->FindDexCache(instr->GetDexFile());
   // 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::Create(handle, /* is_exact */ true));
-  }
-  Handle<mirror::Class> class_handle = handles_->NewHandle(mirror::Class::GetJavaLangClass());
-  instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(class_handle, /* is_exact */ true));
+  DCHECK(resolved_class != nullptr);
+  ReferenceTypeInfo::TypeHandle handle = handles_->NewHandle(resolved_class);
+  instr->SetLoadedClassRTI(ReferenceTypeInfo::Create(handle, /* is_exact */ true));
+  instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(class_class_handle_, /* is_exact */ true));
+}
+
+void RTPVisitor::VisitClinitCheck(HClinitCheck* instr) {
+  instr->SetReferenceTypeInfo(instr->InputAt(0)->GetReferenceTypeInfo());
+}
+
+void RTPVisitor::VisitLoadString(HLoadString* instr) {
+  instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(string_class_handle_, /* is_exact */ true));
+}
+
+void RTPVisitor::VisitNullCheck(HNullCheck* instr) {
+  ScopedObjectAccess soa(Thread::Current());
+  ReferenceTypeInfo parent_rti = instr->InputAt(0)->GetReferenceTypeInfo();
+  DCHECK(parent_rti.IsValid());
+  instr->SetReferenceTypeInfo(parent_rti);
+}
+
+void RTPVisitor::VisitFakeString(HFakeString* instr) {
+  instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(string_class_handle_, /* is_exact */ true));
 }
 
 void RTPVisitor::VisitCheckCast(HCheckCast* check_cast) {
@@ -395,29 +516,54 @@
 
 ReferenceTypeInfo ReferenceTypePropagation::MergeTypes(const ReferenceTypeInfo& a,
                                                        const ReferenceTypeInfo& b) {
-  bool is_exact = a.IsExact() && b.IsExact();
-  bool is_top = a.IsTop() || b.IsTop();
-  Handle<mirror::Class> type_handle;
-
-  if (!is_top) {
-    if (a.GetTypeHandle().Get() == b.GetTypeHandle().Get()) {
-      type_handle = a.GetTypeHandle();
-    } else if (a.IsSupertypeOf(b)) {
-      type_handle = a.GetTypeHandle();
-      is_exact = false;
-    } else if (b.IsSupertypeOf(a)) {
-      type_handle = b.GetTypeHandle();
-      is_exact = false;
-    } else {
-      // TODO: Find a common super class.
-      is_top = true;
-      is_exact = false;
-    }
+  if (!b.IsValid()) {
+    return a;
+  }
+  if (!a.IsValid()) {
+    return b;
   }
 
-  return is_top
-      ? ReferenceTypeInfo::CreateTop(is_exact)
-      : ReferenceTypeInfo::Create(type_handle, is_exact);
+  bool is_exact = a.IsExact() && b.IsExact();
+  Handle<mirror::Class> type_handle;
+
+  if (a.GetTypeHandle().Get() == b.GetTypeHandle().Get()) {
+    type_handle = a.GetTypeHandle();
+  } else if (a.IsSupertypeOf(b)) {
+    type_handle = a.GetTypeHandle();
+    is_exact = false;
+  } else if (b.IsSupertypeOf(a)) {
+    type_handle = b.GetTypeHandle();
+    is_exact = false;
+  } else {
+    // TODO: Find the first common super class.
+    type_handle = object_class_handle_;
+    is_exact = false;
+  }
+
+  return ReferenceTypeInfo::Create(type_handle, is_exact);
+}
+
+static void UpdateArrayGet(HArrayGet* instr,
+                           StackHandleScopeCollection* handles,
+                           ReferenceTypeInfo::TypeHandle object_class_handle)
+    SHARED_REQUIRES(Locks::mutator_lock_) {
+  DCHECK_EQ(Primitive::kPrimNot, instr->GetType());
+
+  ReferenceTypeInfo parent_rti = instr->InputAt(0)->GetReferenceTypeInfo();
+  DCHECK(parent_rti.IsValid());
+
+  Handle<mirror::Class> handle = parent_rti.GetTypeHandle();
+  if (handle->IsObjectArrayClass()) {
+    ReferenceTypeInfo::TypeHandle component_handle = handles->NewHandle(handle->GetComponentType());
+    instr->SetReferenceTypeInfo(
+        ReferenceTypeInfo::Create(component_handle, /* is_exact */ false));
+  } else {
+    // We don't know what the parent actually is, so we fallback to object.
+    instr->SetReferenceTypeInfo(
+        ReferenceTypeInfo::Create(object_class_handle, /* is_exact */ false));
+  }
+
+  return;
 }
 
 bool ReferenceTypePropagation::UpdateReferenceTypeInfo(HInstruction* instr) {
@@ -428,6 +574,15 @@
     UpdateBoundType(instr->AsBoundType());
   } else if (instr->IsPhi()) {
     UpdatePhi(instr->AsPhi());
+  } else if (instr->IsNullCheck()) {
+    ReferenceTypeInfo parent_rti = instr->InputAt(0)->GetReferenceTypeInfo();
+    if (parent_rti.IsValid()) {
+      instr->SetReferenceTypeInfo(parent_rti);
+    }
+  } else if (instr->IsArrayGet()) {
+    // TODO: consider if it's worth "looking back" and bounding the input object
+    // to an array type.
+    UpdateArrayGet(instr->AsArrayGet(), handles_, object_class_handle_);
   } else {
     LOG(FATAL) << "Invalid instruction (should not get here)";
   }
@@ -445,28 +600,28 @@
   mirror::DexCache* dex_cache = cl->FindDexCache(instr->GetDexFile());
   ArtMethod* method = dex_cache->GetResolvedMethod(
       instr->GetDexMethodIndex(), cl->GetImagePointerSize());
-  if (method != nullptr) {
-    mirror::Class* klass = method->GetReturnType(false);
-    SetClassAsTypeInfo(instr, klass, /* is_exact */ false);
-  }
+  mirror::Class* klass = (method == nullptr) ? nullptr : method->GetReturnType(false);
+  SetClassAsTypeInfo(instr, klass, /* is_exact */ false);
 }
 
 void RTPVisitor::VisitArrayGet(HArrayGet* instr) {
   if (instr->GetType() != Primitive::kPrimNot) {
     return;
   }
-
-  HInstruction* parent = instr->InputAt(0);
   ScopedObjectAccess soa(Thread::Current());
-  Handle<mirror::Class> handle = parent->GetReferenceTypeInfo().GetTypeHandle();
-  if (handle.GetReference() != nullptr && handle->IsObjectArrayClass()) {
-    SetClassAsTypeInfo(instr, handle->GetComponentType(), /* is_exact */ false);
+  UpdateArrayGet(instr, handles_, object_class_handle_);
+  if (!instr->GetReferenceTypeInfo().IsValid()) {
+    worklist_->Add(instr);
   }
 }
 
 void ReferenceTypePropagation::UpdateBoundType(HBoundType* instr) {
   ReferenceTypeInfo new_rti = instr->InputAt(0)->GetReferenceTypeInfo();
-  // Be sure that we don't go over the bounded type.
+  if (!new_rti.IsValid()) {
+    return;  // No new info yet.
+  }
+
+  // Make sure that we don't go over the bounded type.
   ReferenceTypeInfo upper_bound_rti = instr->GetUpperBound();
   if (!upper_bound_rti.IsSupertypeOf(new_rti)) {
     new_rti = upper_bound_rti;
@@ -476,14 +631,14 @@
 
 void ReferenceTypePropagation::UpdatePhi(HPhi* instr) {
   ReferenceTypeInfo new_rti = instr->InputAt(0)->GetReferenceTypeInfo();
-  if (new_rti.IsTop() && !new_rti.IsExact()) {
-    // Early return if we are Top and inexact.
+  if (new_rti.IsValid() && new_rti.IsObjectClass() && !new_rti.IsExact()) {
+    // Early return if we are Object and inexact.
     instr->SetReferenceTypeInfo(new_rti);
     return;
   }
   for (size_t i = 1; i < instr->InputCount(); i++) {
     new_rti = MergeTypes(new_rti, instr->InputAt(i)->GetReferenceTypeInfo());
-    if (new_rti.IsTop()) {
+    if (new_rti.IsValid() && new_rti.IsObjectClass()) {
       if (!new_rti.IsExact()) {
         break;
       } else {
@@ -497,7 +652,14 @@
 // Re-computes and updates the nullability of the instruction. Returns whether or
 // not the nullability was changed.
 bool ReferenceTypePropagation::UpdateNullability(HInstruction* instr) {
-  DCHECK(instr->IsPhi() || instr->IsBoundType());
+  DCHECK(instr->IsPhi()
+      || instr->IsBoundType()
+      || instr->IsNullCheck()
+      || instr->IsArrayGet());
+
+  if (!instr->IsPhi() && !instr->IsBoundType()) {
+    return false;
+  }
 
   bool existing_can_be_null = instr->CanBeNull();
   if (instr->IsPhi()) {
@@ -527,14 +689,18 @@
 }
 
 void ReferenceTypePropagation::AddToWorklist(HInstruction* instruction) {
-  DCHECK_EQ(instruction->GetType(), Primitive::kPrimNot) << instruction->GetType();
+  DCHECK_EQ(instruction->GetType(), Primitive::kPrimNot)
+      << instruction->DebugName() << ":" << instruction->GetType();
   worklist_.Add(instruction);
 }
 
 void ReferenceTypePropagation::AddDependentInstructionsToWorklist(HInstruction* instruction) {
   for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
     HInstruction* user = it.Current()->GetUser();
-    if (user->IsPhi() || user->IsBoundType()) {
+    if (user->IsPhi()
+       || user->IsBoundType()
+       || user->IsNullCheck()
+       || (user->IsArrayGet() && (user->GetType() == Primitive::kPrimNot))) {
       AddToWorklist(user);
     }
   }
diff --git a/compiler/optimizing/reference_type_propagation.h b/compiler/optimizing/reference_type_propagation.h
index 32f5e09..14d4a82 100644
--- a/compiler/optimizing/reference_type_propagation.h
+++ b/compiler/optimizing/reference_type_propagation.h
@@ -32,10 +32,7 @@
  public:
   ReferenceTypePropagation(HGraph* graph,
                            StackHandleScopeCollection* handles,
-                           const char* name = kReferenceTypePropagationPassName)
-    : HOptimization(graph, name),
-      handles_(handles),
-      worklist_(graph->GetArena(), kDefaultWorklistSize) {}
+                           const char* name = kReferenceTypePropagationPassName);
 
   void Run() OVERRIDE;
 
@@ -62,6 +59,10 @@
 
   GrowableArray<HInstruction*> worklist_;
 
+  ReferenceTypeInfo::TypeHandle object_class_handle_;
+  ReferenceTypeInfo::TypeHandle class_class_handle_;
+  ReferenceTypeInfo::TypeHandle string_class_handle_;
+
   static constexpr size_t kDefaultWorklistSize = 8;
 
   DISALLOW_COPY_AND_ASSIGN(ReferenceTypePropagation);
diff --git a/runtime/mirror/class-inl.h b/runtime/mirror/class-inl.h
index fc27315..73a194d 100644
--- a/runtime/mirror/class-inl.h
+++ b/runtime/mirror/class-inl.h
@@ -909,6 +909,33 @@
   DCHECK_EQ(pointer_size, Runtime::Current()->GetClassLinker()->GetImagePointerSize());
 }
 
+template<VerifyObjectFlags kVerifyFlags, ReadBarrierOption kReadBarrierOption>
+inline Class* Class::GetComponentType() {
+  return GetFieldObject<Class, kVerifyFlags, kReadBarrierOption>(ComponentTypeOffset());
+}
+
+template<VerifyObjectFlags kVerifyFlags, ReadBarrierOption kReadBarrierOption>
+inline bool Class::IsArrayClass() {
+  return GetComponentType<kVerifyFlags, kReadBarrierOption>() != nullptr;
+}
+
+inline bool Class::IsAssignableFrom(Class* src) {
+  DCHECK(src != nullptr);
+  if (this == src) {
+    // Can always assign to things of the same type.
+    return true;
+  } else if (IsObjectClass()) {
+    // Can assign any reference to java.lang.Object.
+    return !src->IsPrimitive();
+  } else if (IsInterface()) {
+    return src->Implements(this);
+  } else if (src->IsArrayClass()) {
+    return IsAssignableFromArray(src);
+  } else {
+    return !src->IsInterface() && src->IsSubClass(this);
+  }
+}
+
 }  // namespace mirror
 }  // namespace art
 
diff --git a/runtime/mirror/class.h b/runtime/mirror/class.h
index f1eb9be..086137d 100644
--- a/runtime/mirror/class.h
+++ b/runtime/mirror/class.h
@@ -403,9 +403,8 @@
 
   template<VerifyObjectFlags kVerifyFlags = kDefaultVerifyFlags,
            ReadBarrierOption kReadBarrierOption = kWithReadBarrier>
-  bool IsArrayClass() SHARED_REQUIRES(Locks::mutator_lock_) {
-    return GetComponentType<kVerifyFlags, kReadBarrierOption>() != nullptr;
-  }
+
+  bool IsArrayClass() SHARED_REQUIRES(Locks::mutator_lock_);
 
   template<VerifyObjectFlags kVerifyFlags = kDefaultVerifyFlags,
            ReadBarrierOption kReadBarrierOption = kWithReadBarrier>
@@ -422,9 +421,7 @@
 
   template<VerifyObjectFlags kVerifyFlags = kDefaultVerifyFlags,
            ReadBarrierOption kReadBarrierOption = kWithReadBarrier>
-  Class* GetComponentType() SHARED_REQUIRES(Locks::mutator_lock_) {
-    return GetFieldObject<Class, kVerifyFlags, kReadBarrierOption>(ComponentTypeOffset());
-  }
+  Class* GetComponentType() SHARED_REQUIRES(Locks::mutator_lock_);
 
   void SetComponentType(Class* new_component_type) SHARED_REQUIRES(Locks::mutator_lock_) {
     DCHECK(GetComponentType() == nullptr);
@@ -616,22 +613,7 @@
   // downcast would be necessary. Similarly for interfaces, a class that implements (or an interface
   // that extends) another can be assigned to its parent, but not vice-versa. All Classes may assign
   // to themselves. Classes for primitive types may not assign to each other.
-  ALWAYS_INLINE bool IsAssignableFrom(Class* src) SHARED_REQUIRES(Locks::mutator_lock_) {
-    DCHECK(src != nullptr);
-    if (this == src) {
-      // Can always assign to things of the same type.
-      return true;
-    } else if (IsObjectClass()) {
-      // Can assign any reference to java.lang.Object.
-      return !src->IsPrimitive();
-    } else if (IsInterface()) {
-      return src->Implements(this);
-    } else if (src->IsArrayClass()) {
-      return IsAssignableFromArray(src);
-    } else {
-      return !src->IsInterface() && src->IsSubClass(this);
-    }
-  }
+  ALWAYS_INLINE bool IsAssignableFrom(Class* src) SHARED_REQUIRES(Locks::mutator_lock_);
 
   ALWAYS_INLINE Class* GetSuperClass() SHARED_REQUIRES(Locks::mutator_lock_);
 
diff --git a/test/450-checker-types/src/Main.java b/test/450-checker-types/src/Main.java
index 5755205..b320e38 100644
--- a/test/450-checker-types/src/Main.java
+++ b/test/450-checker-types/src/Main.java
@@ -415,11 +415,11 @@
   }
 
   /// CHECK-START: SubclassC Main.inlineGenerics() reference_type_propagation (after)
-  /// CHECK:      <<Invoke:l\d+>>    InvokeStaticOrDirect klass:SubclassC
+  /// CHECK:      <<Invoke:l\d+>>    InvokeStaticOrDirect klass:SubclassC exact:false
   /// CHECK-NEXT:                    Return [<<Invoke>>]
 
   /// CHECK-START: SubclassC Main.inlineGenerics() reference_type_propagation_after_inlining (after)
-  /// CHECK:      <<BoundType:l\d+>> BoundType klass:SubclassC
+  /// CHECK:      <<BoundType:l\d+>> BoundType klass:SubclassC exact:false
   /// CHECK:                         Return [<<BoundType>>]
   private SubclassC inlineGenerics() {
     SubclassC c = get();
@@ -464,6 +464,25 @@
     return f;
   }
 
+  private Super getSuper() {
+    return new SubclassA();
+  }
+
+  /// CHECK-START: void Main.updateNodesInTheSameBlockAsPhi(boolean) reference_type_propagation (after)
+  /// CHECK:      <<Phi:l\d+>> Phi klass:Super
+  /// CHECK:                   NullCheck [<<Phi>>] klass:Super
+
+  /// CHECK-START: void Main.updateNodesInTheSameBlockAsPhi(boolean) reference_type_propagation_after_inlining (after)
+  /// CHECK:      <<Phi:l\d+>> Phi klass:SubclassA
+  /// CHECK:                   NullCheck [<<Phi>>] klass:SubclassA
+  private void updateNodesInTheSameBlockAsPhi(boolean cond) {
+    Super s = getSuper();
+    if (cond) {
+      s = new SubclassA();
+    }
+    s.$noinline$f();
+  }
+
   /// CHECK-START: java.lang.String Main.checkcastPreserveNullCheck(java.lang.Object) reference_type_propagation_after_inlining (after)
   /// CHECK:      <<This:l\d+>>     ParameterValue
   /// CHECK:      <<Param:l\d+>>    ParameterValue