diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index 7b0231b..e864ae1 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -3865,5 +3865,17 @@
   DCHECK(!IsLeafMethod());
 }
 
+void LocationsBuilderARM::VisitBoundType(HBoundType* instruction) {
+  // Nothing to do, this should be removed during prepare for register allocator.
+  UNUSED(instruction);
+  LOG(FATAL) << "Unreachable";
+}
+
+void InstructionCodeGeneratorARM::VisitBoundType(HBoundType* instruction) {
+  // Nothing to do, this should be removed during prepare for register allocator.
+  UNUSED(instruction);
+  LOG(FATAL) << "Unreachable";
+}
+
 }  // namespace arm
 }  // namespace art
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index 8220207..6da1e61 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -2582,6 +2582,18 @@
   HandleBinaryOp(instruction);
 }
 
+void LocationsBuilderARM64::VisitBoundType(HBoundType* instruction) {
+  // Nothing to do, this should be removed during prepare for register allocator.
+  UNUSED(instruction);
+  LOG(FATAL) << "Unreachable";
+}
+
+void InstructionCodeGeneratorARM64::VisitBoundType(HBoundType* instruction) {
+  // Nothing to do, this should be removed during prepare for register allocator.
+  UNUSED(instruction);
+  LOG(FATAL) << "Unreachable";
+}
+
 #undef __
 #undef QUICK_ENTRY_POINT
 
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 8a73eb4..e151c6b 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -3914,5 +3914,17 @@
   }
 }
 
+void LocationsBuilderX86::VisitBoundType(HBoundType* instruction) {
+  // Nothing to do, this should be removed during prepare for register allocator.
+  UNUSED(instruction);
+  LOG(FATAL) << "Unreachable";
+}
+
+void InstructionCodeGeneratorX86::VisitBoundType(HBoundType* instruction) {
+  // Nothing to do, this should be removed during prepare for register allocator.
+  UNUSED(instruction);
+  LOG(FATAL) << "Unreachable";
+}
+
 }  // namespace x86
 }  // namespace art
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index f7ec67f..41a19e1 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -3711,5 +3711,17 @@
   }
 }
 
+void LocationsBuilderX86_64::VisitBoundType(HBoundType* instruction) {
+  // Nothing to do, this should be removed during prepare for register allocator.
+  UNUSED(instruction);
+  LOG(FATAL) << "Unreachable";
+}
+
+void InstructionCodeGeneratorX86_64::VisitBoundType(HBoundType* instruction) {
+  // Nothing to do, this should be removed during prepare for register allocator.
+  UNUSED(instruction);
+  LOG(FATAL) << "Unreachable";
+}
+
 }  // namespace x86_64
 }  // namespace art
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index c7b8343..4baea66 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -583,6 +583,7 @@
   M(ArrayLength, Instruction)                                           \
   M(ArraySet, Instruction)                                              \
   M(BoundsCheck, Instruction)                                           \
+  M(BoundType, Instruction)                                             \
   M(CheckCast, Instruction)                                             \
   M(ClinitCheck, Instruction)                                           \
   M(Compare, BinaryOperation)                                           \
@@ -876,9 +877,22 @@
 
 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);
+  typedef Handle<mirror::Class> TypeHandle;
+
+  static ReferenceTypeInfo Create(TypeHandle type_handle, bool is_exact)
+      SHARED_LOCKS_REQUIRED(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 CreateTop(bool is_exact) {
+    return ReferenceTypeInfo(TypeHandle(), is_exact, true);
   }
 
   bool IsExact() const { return is_exact_; }
@@ -886,29 +900,7 @@
 
   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_) {
+  bool IsSupertypeOf(ReferenceTypeInfo rti) const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
     if (IsTop()) {
       // Top (equivalent for java.lang.Object) is supertype of anything.
       return true;
@@ -943,9 +935,14 @@
   }
 
  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) {}
+
   // The class of the object.
-  Handle<mirror::Class> type_handle_;
+  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
@@ -968,7 +965,8 @@
         locations_(nullptr),
         live_interval_(nullptr),
         lifetime_position_(kNoLifetime),
-        side_effects_(side_effects) {}
+        side_effects_(side_effects),
+        reference_type_info_(ReferenceTypeInfo::CreateTop(/* is_exact */ false)) {}
 
   virtual ~HInstruction() {}
 
@@ -2740,7 +2738,8 @@
         type_index_(type_index),
         is_referrers_class_(is_referrers_class),
         dex_pc_(dex_pc),
-        generate_clinit_check_(false) {}
+        generate_clinit_check_(false),
+        loaded_class_rti_(ReferenceTypeInfo::CreateTop(/* is_exact */ false)) {}
 
   bool CanBeMoved() const OVERRIDE { return true; }
 
@@ -3006,6 +3005,32 @@
   DISALLOW_COPY_AND_ASSIGN(HInstanceOf);
 };
 
+class HBoundType : public HExpression<1> {
+ public:
+  HBoundType(HInstruction* input, ReferenceTypeInfo bound_type)
+      : HExpression(Primitive::kPrimNot, SideEffects::None()),
+        bound_type_(bound_type) {
+    SetRawInputAt(0, input);
+  }
+
+  const ReferenceTypeInfo& GetBoundType() const { return bound_type_; }
+
+  bool CanBeNull() const OVERRIDE {
+    // `null instanceof ClassX` always return false so we can't be null.
+    return false;
+  }
+
+  DECLARE_INSTRUCTION(BoundType);
+
+ private:
+  // Encodes the most upper class that this instruction can have. In other words
+  // it is always the case that GetBoundType().IsSupertypeOf(GetReferenceType()).
+  // It is used to bound the type in cases like `if (x instanceof ClassX) {}`
+  const ReferenceTypeInfo bound_type_;
+
+  DISALLOW_COPY_AND_ASSIGN(HBoundType);
+};
+
 class HCheckCast : public HTemplateInstruction<2> {
  public:
   HCheckCast(HInstruction* object,
diff --git a/compiler/optimizing/prepare_for_register_allocation.cc b/compiler/optimizing/prepare_for_register_allocation.cc
index 12acd08..2d9a2bf 100644
--- a/compiler/optimizing/prepare_for_register_allocation.cc
+++ b/compiler/optimizing/prepare_for_register_allocation.cc
@@ -42,6 +42,11 @@
   check->ReplaceWith(check->InputAt(0));
 }
 
+void PrepareForRegisterAllocation::VisitBoundType(HBoundType* bound_type) {
+  bound_type->ReplaceWith(bound_type->InputAt(0));
+  bound_type->GetBlock()->RemoveInstruction(bound_type);
+}
+
 void PrepareForRegisterAllocation::VisitClinitCheck(HClinitCheck* check) {
   HLoadClass* cls = check->GetLoadClass();
   check->ReplaceWith(cls);
diff --git a/compiler/optimizing/prepare_for_register_allocation.h b/compiler/optimizing/prepare_for_register_allocation.h
index 0fdb65f..0f697fb 100644
--- a/compiler/optimizing/prepare_for_register_allocation.h
+++ b/compiler/optimizing/prepare_for_register_allocation.h
@@ -36,6 +36,7 @@
   virtual void VisitNullCheck(HNullCheck* check) OVERRIDE;
   virtual void VisitDivZeroCheck(HDivZeroCheck* check) OVERRIDE;
   virtual void VisitBoundsCheck(HBoundsCheck* check) OVERRIDE;
+  virtual void VisitBoundType(HBoundType* bound_type) OVERRIDE;
   virtual void VisitClinitCheck(HClinitCheck* check) OVERRIDE;
   virtual void VisitCondition(HCondition* condition) OVERRIDE;
 
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
index 18c0564..76b8d7e 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -23,24 +23,7 @@
 
 namespace art {
 
-// 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.
-
-// 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();
-//  }
+// TODO: handle: a !=/== null.
 
 void ReferenceTypePropagation::Run() {
   // To properly propagate type info we need to visit in the dominator-based order.
@@ -52,65 +35,80 @@
   ProcessWorklist();
 }
 
-// Re-computes and updates the nullability of the instruction. Returns whether or
-// not the nullability was changed.
-bool ReferenceTypePropagation::UpdateNullability(HPhi* phi) {
-  bool existing_can_be_null = phi->CanBeNull();
-  bool new_can_be_null = false;
-  for (size_t i = 0; i < phi->InputCount(); i++) {
-    new_can_be_null |= phi->InputAt(i)->CanBeNull();
-  }
-  phi->SetCanBeNull(new_can_be_null);
+void ReferenceTypePropagation::VisitBasicBlock(HBasicBlock* block) {
+  // TODO: handle other instructions that give type info
+  // (NewArray/Call/Field accesses/array accesses)
 
-  return existing_can_be_null != new_can_be_null;
+  // Initialize exact types first for faster convergence.
+  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());
+    }
+  }
+
+  // Handle Phis.
+  for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
+    VisitPhi(it.Current()->AsPhi());
+  }
+
+  // Add extra nodes to bound types.
+  BoundTypeForIfInstanceOf(block);
 }
 
-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);;
+// Detects if `block` is the True block for the pattern
+// `if (x instanceof ClassX) { }`
+// If that's the case insert an HBoundType instruction to bound the type of `x`
+// to `ClassX` in the scope of the dominated blocks.
+void ReferenceTypePropagation::BoundTypeForIfInstanceOf(HBasicBlock* block) {
+  HInstruction* lastInstruction = block->GetLastInstruction();
+  if (!lastInstruction->IsIf()) {
+    return;
+  }
+  HInstruction* ifInput = lastInstruction->InputAt(0);
+  // TODO: Handle more patterns here: HIf(bool) HIf(HNotEqual).
+  if (!ifInput->IsEqual()) {
+    return;
+  }
+  HInstruction* instanceOf = ifInput->InputAt(0);
+  HInstruction* comp_value = ifInput->InputAt(1);
+  if (!instanceOf->IsInstanceOf() || !comp_value->IsIntConstant()) {
+    return;
   }
 
-  for (size_t i = 1; i < phi->InputCount(); i++) {
-    ReferenceTypeInfo input_rti = phi->InputAt(i)->GetReferenceTypeInfo();
+  HInstruction* obj = instanceOf->InputAt(0);
+  HLoadClass* load_class = instanceOf->InputAt(1)->AsLoadClass();
 
-    if (!input_rti.IsExact()) {
-      new_rti.SetInexact();
-    }
+  ReferenceTypeInfo obj_rti = obj->GetReferenceTypeInfo();
+  ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI();
+  HBoundType* bound_type = new (graph_->GetArena()) HBoundType(obj, class_rti);
 
-    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();
+  // Narrow the type as much as possible.
+  {
+    ScopedObjectAccess soa(Thread::Current());
+    if (!load_class->IsResolved() || class_rti.IsSupertypeOf(obj_rti)) {
+      bound_type->SetReferenceTypeInfo(obj_rti);
     } else {
-      // TODO: Find common parent.
-      new_rti.SetTop();
-      new_rti.SetInexact();
+      bound_type->SetReferenceTypeInfo(
+          ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ false));
     }
   }
 
-  phi->SetReferenceTypeInfo(new_rti);
-  return !new_rti.IsEqual(existing_rti);
+  block->InsertInstructionBefore(bound_type, lastInstruction);
+  // Pick the right successor based on the value we compare against.
+  HIntConstant* comp_value_int = comp_value->AsIntConstant();
+  HBasicBlock* instanceOfTrueBlock = comp_value_int->GetValue() == 0
+      ? lastInstruction->AsIf()->IfFalseSuccessor()
+      : lastInstruction->AsIf()->IfTrueSuccessor();
+
+  for (HUseIterator<HInstruction*> it(obj->GetUses()); !it.Done(); it.Advance()) {
+    HInstruction* user = it.Current()->GetUser();
+    if (instanceOfTrueBlock->Dominates(user->GetBlock())) {
+      user->ReplaceInput(bound_type, it.Current()->GetIndex());
+    }
+  }
 }
 
 void ReferenceTypePropagation::VisitNewInstance(HNewInstance* instr) {
@@ -120,7 +118,7 @@
   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));
+    instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(handle, true));
   }
 }
 
@@ -131,71 +129,146 @@
   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));
+    instr->SetLoadedClassRTI(ReferenceTypeInfo::Create(handle, /* is_exact */ true));
   }
   Handle<mirror::Class> class_handle = handles_->NewHandle(mirror::Class::GetJavaLangClass());
-  instr->SetReferenceTypeInfo(ReferenceTypeInfo(class_handle, true));
+  instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(class_handle, /* is_exact */ 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());
-    }
+void ReferenceTypePropagation::VisitPhi(HPhi* phi) {
+  if (phi->GetType() != Primitive::kPrimNot) {
+    return;
   }
-  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
-      // a fixed point faster.
-      HPhi* phi = it.Current()->AsPhi();
-      if (phi->GetType() == Primitive::kPrimNot) {
-        AddToWorklist(phi);
-        phi->SetCanBeNull(phi->InputAt(0)->CanBeNull());
-        phi->SetReferenceTypeInfo(phi->InputAt(0)->GetReferenceTypeInfo());
-      }
-    }
+
+  if (phi->GetBlock()->IsLoopHeader()) {
+    // Set the initial type for the phi. Use the non back edge input for reaching
+    // a fixed point faster.
+    AddToWorklist(phi);
+    phi->SetCanBeNull(phi->InputAt(0)->CanBeNull());
+    phi->SetReferenceTypeInfo(phi->InputAt(0)->GetReferenceTypeInfo());
   } else {
-    for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
-      // Eagerly compute the type of the phi, for quicker convergence. Note
-      // that we don't need to add users to the worklist because we are
-      // doing a reverse post-order visit, therefore either the phi users are
-      // non-loop phi and will be visited later in the visit, or are loop-phis,
-      // and they are already in the work list.
-      HPhi* phi = it.Current()->AsPhi();
-      if (phi->GetType() == Primitive::kPrimNot) {
-        UpdateNullability(phi);
-        UpdateReferenceTypeInfo(phi);
+    // Eagerly compute the type of the phi, for quicker convergence. Note
+    // that we don't need to add users to the worklist because we are
+    // doing a reverse post-order visit, therefore either the phi users are
+    // non-loop phi and will be visited later in the visit, or are loop-phis,
+    // and they are already in the work list.
+    UpdateNullability(phi);
+    UpdateReferenceTypeInfo(phi);
+  }
+}
+
+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;
+    }
+  }
+
+  return is_top
+      ? ReferenceTypeInfo::CreateTop(is_exact)
+      : ReferenceTypeInfo::Create(type_handle, is_exact);
+}
+
+bool ReferenceTypePropagation::UpdateReferenceTypeInfo(HInstruction* instr) {
+  ScopedObjectAccess soa(Thread::Current());
+
+  ReferenceTypeInfo previous_rti = instr->GetReferenceTypeInfo();
+  if (instr->IsBoundType()) {
+    UpdateBoundType(instr->AsBoundType());
+  } else if (instr->IsPhi()) {
+    UpdatePhi(instr->AsPhi());
+  } else {
+    LOG(FATAL) << "Invalid instruction (should not get here)";
+  }
+
+  return !previous_rti.IsEqual(instr->GetReferenceTypeInfo());
+}
+
+void ReferenceTypePropagation::UpdateBoundType(HBoundType* instr) {
+  ReferenceTypeInfo new_rti = instr->InputAt(0)->GetReferenceTypeInfo();
+  // Be sure that we don't go over the bounded type.
+  ReferenceTypeInfo bound_rti = instr->GetBoundType();
+  if (!bound_rti.IsSupertypeOf(new_rti)) {
+    new_rti = bound_rti;
+  }
+  instr->SetReferenceTypeInfo(new_rti);
+}
+
+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.
+    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.IsExact()) {
+        break;
+      } else {
+        continue;
       }
     }
   }
+  instr->SetReferenceTypeInfo(new_rti);
+}
+
+// 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());
+
+  if (!instr->IsPhi()) {
+    return false;
+  }
+
+  HPhi* phi = instr->AsPhi();
+  bool existing_can_be_null = phi->CanBeNull();
+  bool new_can_be_null = false;
+  for (size_t i = 0; i < phi->InputCount(); i++) {
+    new_can_be_null |= phi->InputAt(i)->CanBeNull();
+  }
+  phi->SetCanBeNull(new_can_be_null);
+
+  return existing_can_be_null != new_can_be_null;
 }
 
 void ReferenceTypePropagation::ProcessWorklist() {
   while (!worklist_.IsEmpty()) {
-    HPhi* instruction = worklist_.Pop();
+    HInstruction* instruction = worklist_.Pop();
     if (UpdateNullability(instruction) || UpdateReferenceTypeInfo(instruction)) {
       AddDependentInstructionsToWorklist(instruction);
     }
   }
 }
 
-void ReferenceTypePropagation::AddToWorklist(HPhi* instruction) {
-  DCHECK_EQ(instruction->GetType(), Primitive::kPrimNot);
+void ReferenceTypePropagation::AddToWorklist(HInstruction* instruction) {
+  DCHECK_EQ(instruction->GetType(), Primitive::kPrimNot) << instruction->GetType();
   worklist_.Add(instruction);
 }
 
-void ReferenceTypePropagation::AddDependentInstructionsToWorklist(HPhi* instruction) {
+void ReferenceTypePropagation::AddDependentInstructionsToWorklist(HInstruction* instruction) {
   for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
-    HPhi* phi = it.Current()->GetUser()->AsPhi();
-    if (phi != nullptr) {
-      AddToWorklist(phi);
+    HInstruction* user = it.Current()->GetUser();
+    if (user->IsPhi() || user->IsBoundType()) {
+      AddToWorklist(user);
     }
   }
 }
-
 }  // namespace art
diff --git a/compiler/optimizing/reference_type_propagation.h b/compiler/optimizing/reference_type_propagation.h
index 1ec5df3..e346dbf 100644
--- a/compiler/optimizing/reference_type_propagation.h
+++ b/compiler/optimizing/reference_type_propagation.h
@@ -21,6 +21,7 @@
 #include "handle_scope-inl.h"
 #include "nodes.h"
 #include "optimization.h"
+#include "optimizing_compiler_stats.h"
 
 namespace art {
 
@@ -44,18 +45,29 @@
  private:
   void VisitNewInstance(HNewInstance* new_instance);
   void VisitLoadClass(HLoadClass* load_class);
+  void VisitPhi(HPhi* phi);
   void VisitBasicBlock(HBasicBlock* block);
+
+  void UpdateBoundType(HBoundType* bound_type) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  void UpdatePhi(HPhi* phi) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+
+  void BoundTypeForIfInstanceOf(HBasicBlock* block);
+
   void ProcessWorklist();
-  void AddToWorklist(HPhi* phi);
-  void AddDependentInstructionsToWorklist(HPhi* phi);
-  bool UpdateNullability(HPhi* phi);
-  bool UpdateReferenceTypeInfo(HPhi* phi);
+  void AddToWorklist(HInstruction* instr);
+  void AddDependentInstructionsToWorklist(HInstruction* instr);
+
+  bool UpdateNullability(HInstruction* instr);
+  bool UpdateReferenceTypeInfo(HInstruction* instr);
+
+  ReferenceTypeInfo MergeTypes(const ReferenceTypeInfo& a, const ReferenceTypeInfo& b)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
   const DexFile& dex_file_;
   const DexCompilationUnit& dex_compilation_unit_;
   StackHandleScopeCollection* handles_;
 
-  GrowableArray<HPhi*> worklist_;
+  GrowableArray<HInstruction*> worklist_;
 
   static constexpr size_t kDefaultWorklistSize = 8;
 
diff --git a/test/450-checker-types/src/Main.java b/test/450-checker-types/src/Main.java
index a0d8ed5..640aeb8 100644
--- a/test/450-checker-types/src/Main.java
+++ b/test/450-checker-types/src/Main.java
@@ -168,6 +168,170 @@
     ((SubclassC)x).g();
   }
 
+  // CHECK-START: void Main.testInstanceOf(java.lang.Object) instruction_simplifier_after_types (before)
+  // CHECK:         CheckCast
+  // CHECK:         CheckCast
+
+  // CHECK-START: void Main.testInstanceOf(java.lang.Object) instruction_simplifier_after_types (after)
+  // CHECK-NOT:     CheckCast
+  public void testInstanceOf(Object o) {
+    if (o instanceof SubclassC) {
+      ((SubclassC)o).g();
+    }
+    if (o instanceof SubclassB) {
+      ((SubclassB)o).g();
+    }
+  }
+
+  // CHECK-START: void Main.testInstanceOfKeep(java.lang.Object) instruction_simplifier_after_types (before)
+  // CHECK:         CheckCast
+  // CHECK:         CheckCast
+
+  // CHECK-START: void Main.testInstanceOfKeep(java.lang.Object) instruction_simplifier_after_types (after)
+  // CHECK:         CheckCast
+  // CHECK:         CheckCast
+  public void testInstanceOfKeep(Object o) {
+    if (o instanceof SubclassC) {
+      ((SubclassB)o).g();
+    }
+    if (o instanceof SubclassB) {
+      ((SubclassA)o).g();
+    }
+  }
+
+  // CHECK-START: void Main.testInstanceOfNested(java.lang.Object) instruction_simplifier_after_types (before)
+  // CHECK:         CheckCast
+  // CHECK:         CheckCast
+
+  // CHECK-START: void Main.testInstanceOfNested(java.lang.Object) instruction_simplifier_after_types (after)
+  // CHECK-NOT:     CheckCast
+  public void testInstanceOfNested(Object o) {
+    if (o instanceof SubclassC) {
+      if (o instanceof SubclassB) {
+        ((SubclassB)o).g();
+      } else {
+        ((SubclassC)o).g();
+      }
+    }
+  }
+
+  // CHECK-START: void Main.testInstanceOfWithPhi(int) instruction_simplifier_after_types (before)
+  // CHECK:         CheckCast
+
+  // CHECK-START: void Main.testInstanceOfWithPhi(int) instruction_simplifier_after_types (after)
+  // CHECK-NOT:     CheckCast
+  public void testInstanceOfWithPhi(int i) {
+    Object o;
+    if (i == 0) {
+      o = new SubclassA();
+    } else {
+      o = new SubclassB();
+    }
+
+    if (o instanceof SubclassB) {
+      ((SubclassB)o).g();
+    }
+  }
+
+  // CHECK-START: void Main.testInstanceOfInFor(int) instruction_simplifier_after_types (before)
+  // CHECK:         CheckCast
+
+  // CHECK-START: void Main.testInstanceOfInFor(int) instruction_simplifier_after_types (after)
+  // CHECK-NOT:     CheckCast
+  public void testInstanceOfInFor(int n) {
+    Object o = new SubclassA();
+    for (int i = 0; i < n; i++) {
+      if (i / 2 == 0) {
+        o = new SubclassB();
+      }
+      if (o instanceof SubclassB) {
+        ((SubclassB)o).g();
+      }
+    }
+  }
+
+  // CHECK-START: void Main.testInstanceOfSubclass() instruction_simplifier_after_types (before)
+  // CHECK:         CheckCast
+
+  // CHECK-START: void Main.testInstanceOfSubclass() instruction_simplifier_after_types (after)
+  // CHECK-NOT:     CheckCast
+  public void testInstanceOfSubclass() {
+    Object o = new SubclassA();
+    if (o instanceof Super) {
+      ((SubclassA)o).g();
+    }
+  }
+
+  // CHECK-START: void Main.testInstanceOfWithPhiSubclass(int) instruction_simplifier_after_types (before)
+  // CHECK:         CheckCast
+
+  // CHECK-START: void Main.testInstanceOfWithPhiSubclass(int) instruction_simplifier_after_types (after)
+  // CHECK-NOT:     CheckCast
+  public void testInstanceOfWithPhiSubclass(int i) {
+    Object o;
+    if (i == 0) {
+      o = new SubclassA();
+    } else {
+      o = new SubclassC();
+    }
+
+    if (o instanceof Super) {
+      ((SubclassA)o).g();
+    }
+  }
+
+  // CHECK-START: void Main.testInstanceOfWithPhiTop(int) instruction_simplifier_after_types (before)
+  // CHECK:         CheckCast
+
+  // CHECK-START: void Main.testInstanceOfWithPhiTop(int) instruction_simplifier_after_types (after)
+  // CHECK-NOT:     CheckCast
+  public void testInstanceOfWithPhiTop(int i) {
+    Object o;
+    if (i == 0) {
+      o = new Object();
+    } else {
+      o = new SubclassC();
+    }
+
+    if (o instanceof Super) {
+      ((Super)o).f();
+    }
+  }
+
+  // CHECK-START: void Main.testInstanceOfSubclassInFor(int) instruction_simplifier_after_types (before)
+  // CHECK:         CheckCast
+
+  // CHECK-START: void Main.testInstanceOfSubclassInFor(int) instruction_simplifier_after_types (after)
+  // CHECK-NOT:     CheckCast
+  public void testInstanceOfSubclassInFor(int n) {
+    Object o = new SubclassA();
+    for (int i = 0; i < n; i++) {
+      if (o instanceof Super) {
+        ((SubclassA)o).g();
+      }
+      if (i / 2 == 0) {
+        o = new SubclassC();
+      }
+    }
+  }
+
+  // CHECK-START: void Main.testInstanceOfTopInFor(int) instruction_simplifier_after_types (before)
+  // CHECK:         CheckCast
+
+  // CHECK-START: void Main.testInstanceOfTopInFor(int) instruction_simplifier_after_types (after)
+  // CHECK-NOT:     CheckCast
+  public void testInstanceOfTopInFor(int n) {
+    Object o = new SubclassA();
+    for (int i = 0; i < n; i++) {
+      if (o instanceof Super) {
+        ((Super)o).f();
+      }
+      if (i / 2 == 0) {
+        o = new Object();
+      }
+    }
+  }
+
   public Object newObject() {
     try {
       return Object.class.newInstance();