diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 37c060c..aaf7a6d 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -397,6 +397,11 @@
     return strcmp(pass_name_, name) == 0;
   }
 
+  bool IsReferenceTypePropagationPass() {
+    return strstr(pass_name_, ReferenceTypePropagation::kReferenceTypePropagationPassName)
+        != nullptr;
+  }
+
   void PrintInstruction(HInstruction* instruction) {
     output_ << instruction->DebugName();
     if (instruction->InputCount() > 0) {
@@ -460,14 +465,13 @@
       } else {
         StartAttributeStream("loop") << "B" << info->GetHeader()->GetBlockId();
       }
-    } else if (IsPass(ReferenceTypePropagation::kReferenceTypePropagationPassName)
-               && is_after_pass_) {
+    } else if (IsReferenceTypePropagationPass() && is_after_pass_) {
       if (instruction->GetType() == Primitive::kPrimNot) {
         if (instruction->IsLoadClass()) {
           ReferenceTypeInfo info = instruction->AsLoadClass()->GetLoadedClassRTI();
           ScopedObjectAccess soa(Thread::Current());
           if (info.GetTypeHandle().GetReference() != nullptr) {
-            StartAttributeStream("klass") << PrettyClass(info.GetTypeHandle().Get());
+            StartAttributeStream("klass") << PrettyDescriptor(info.GetTypeHandle().Get());
           } else {
             StartAttributeStream("klass") << "unresolved";
           }
@@ -477,7 +481,7 @@
             StartAttributeStream("klass") << "java.lang.Object";
           } else {
             ScopedObjectAccess soa(Thread::Current());
-            StartAttributeStream("klass") << PrettyClass(info.GetTypeHandle().Get());
+            StartAttributeStream("klass") << PrettyDescriptor(info.GetTypeHandle().Get());
           }
           StartAttributeStream("exact") << std::boolalpha << info.IsExact() << std::noboolalpha;
         }
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 8546a10..57c7829 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -1488,6 +1488,7 @@
 
   // Does not apply for all instructions, but having this at top level greatly
   // simplifies the null check elimination.
+  // TODO: Consider merging can_be_null into ReferenceTypeInfo.
   virtual bool CanBeNull() const {
     DCHECK_EQ(GetType(), Primitive::kPrimNot) << "CanBeNull only applies to reference types";
     return true;
@@ -4070,27 +4071,39 @@
 
 class HBoundType : public HExpression<1> {
  public:
-  HBoundType(HInstruction* input, ReferenceTypeInfo bound_type)
+  HBoundType(HInstruction* input, ReferenceTypeInfo upper_bound, bool upper_can_be_null)
       : HExpression(Primitive::kPrimNot, SideEffects::None()),
-        bound_type_(bound_type) {
+        upper_bound_(upper_bound),
+        upper_can_be_null_(upper_can_be_null) {
     DCHECK_EQ(input->GetType(), Primitive::kPrimNot);
     SetRawInputAt(0, input);
   }
 
-  const ReferenceTypeInfo& GetBoundType() const { return bound_type_; }
+  // GetUpper* should only be used in reference type propagation.
+  const ReferenceTypeInfo& GetUpperBound() const { return upper_bound_; }
+  bool GetUpperCanBeNull() const { return upper_can_be_null_; }
 
-  bool CanBeNull() const OVERRIDE {
-    // `null instanceof ClassX` always return false so we can't be null.
-    return false;
+  void SetCanBeNull(bool can_be_null) {
+    DCHECK(upper_can_be_null_ || !can_be_null);
+    can_be_null_ = can_be_null;
   }
 
+  bool CanBeNull() const OVERRIDE { return can_be_null_; }
+
   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_;
+  // it is always the case that GetUpperBound().IsSupertypeOf(GetReferenceType()).
+  // It is used to bound the type in cases like:
+  //   if (x instanceof ClassX) {
+  //     // uper_bound_ will be ClassX
+  //   }
+  const ReferenceTypeInfo upper_bound_;
+  // Represents the top constraint that can_be_null_ cannot exceed (i.e. if this
+  // is false then can_be_null_ cannot be true).
+  const bool upper_can_be_null_;
+  bool can_be_null_;
 
   DISALLOW_COPY_AND_ASSIGN(HBoundType);
 };
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 4568a46..ae1958a 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -379,7 +379,8 @@
   InstructionSimplifier* simplify3 = new (arena) InstructionSimplifier(
       graph, stats, "instruction_simplifier_after_bce");
   ReferenceTypePropagation* type_propagation2 =
-      new (arena) ReferenceTypePropagation(graph, handles);
+      new (arena) ReferenceTypePropagation(
+          graph, handles, "reference_type_propagation_after_inlining");
   InstructionSimplifier* simplify4 = new (arena) InstructionSimplifier(
       graph, stats, "instruction_simplifier_before_codegen");
 
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
index 68316c2..84db62b 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -38,6 +38,7 @@
   void VisitStaticFieldGet(HStaticFieldGet* instr) OVERRIDE;
   void VisitInvoke(HInvoke* instr) OVERRIDE;
   void VisitArrayGet(HArrayGet* instr) OVERRIDE;
+  void VisitCheckCast(HCheckCast* instr) OVERRIDE;
   void UpdateReferenceTypeInfo(HInstruction* instr,
                                uint16_t type_idx,
                                const DexFile& dex_file,
@@ -78,6 +79,72 @@
   BoundTypeForIfInstanceOf(block);
 }
 
+// Create a bound type for the given object narrowing the type as much as possible.
+// The BoundType upper values for the super type and can_be_null will be taken from
+// load_class.GetLoadedClassRTI() and upper_can_be_null.
+static HBoundType* CreateBoundType(ArenaAllocator* arena,
+                                   HInstruction* obj,
+                                   HLoadClass* load_class,
+                                   bool upper_can_be_null)
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  ReferenceTypeInfo obj_rti = obj->GetReferenceTypeInfo();
+  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()) {
+    bound_type->SetReferenceTypeInfo(
+        ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ true));
+  } else if (!load_class->IsResolved() || class_rti.IsSupertypeOf(obj_rti)) {
+    bound_type->SetReferenceTypeInfo(obj_rti);
+  } else {
+    bound_type->SetReferenceTypeInfo(
+        ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ false));
+  }
+  return bound_type;
+}
+
+// Check if we should create a bound type for the given object at the specified
+// position. Because of inlining and the fact we run RTP more than once and we
+// might have a HBoundType already. If we do, we should not create a new one.
+// In this case we also assert that there are no other uses of the object (except
+// the bound type) dominated by the specified dominator_instr or dominator_block.
+static bool ShouldCreateBoundType(HInstruction* position,
+                                  HInstruction* obj,
+                                  ReferenceTypeInfo upper_bound,
+                                  HInstruction* dominator_instr,
+                                  HBasicBlock* dominator_block)
+    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+  // If the position where we should insert the bound type is not already a
+  // a bound type then we need to create one.
+  if (position == nullptr || !position->IsBoundType()) {
+    return true;
+  }
+
+  HBoundType* existing_bound_type = position->AsBoundType();
+  if (existing_bound_type->GetUpperBound().IsSupertypeOf(upper_bound)) {
+    if (kIsDebugBuild) {
+      // Check that the existing HBoundType dominates all the uses.
+      for (HUseIterator<HInstruction*> it(obj->GetUses()); !it.Done(); it.Advance()) {
+        HInstruction* user = it.Current()->GetUser();
+        if (dominator_instr != nullptr) {
+          DCHECK(!dominator_instr->StrictlyDominates(user)
+              || user == existing_bound_type
+              || existing_bound_type->StrictlyDominates(user));
+        } else if (dominator_block != nullptr) {
+          DCHECK(!dominator_block->Dominates(user->GetBlock())
+              || user == existing_bound_type
+              || existing_bound_type->StrictlyDominates(user));
+        }
+      }
+    }
+  } else {
+    // TODO: if the current bound type is a refinement we could update the
+    // existing_bound_type with the a new upper limit. However, we also need to
+    // update its users and have access to the work list.
+  }
+  return false;
+}
+
 void ReferenceTypePropagation::BoundTypeForIfNotNull(HBasicBlock* block) {
   HIf* ifInstruction = block->GetLastInstruction()->AsIf();
   if (ifInstruction == nullptr) {
@@ -116,8 +183,19 @@
     HInstruction* user = it.Current()->GetUser();
     if (notNullBlock->Dominates(user->GetBlock())) {
       if (bound_type == nullptr) {
-        bound_type = new (graph_->GetArena()) HBoundType(obj, ReferenceTypeInfo::CreateTop(false));
-        notNullBlock->InsertInstructionBefore(bound_type, notNullBlock->GetFirstInstruction());
+        ScopedObjectAccess soa(Thread::Current());
+        HInstruction* insert_point = notNullBlock->GetFirstInstruction();
+        ReferenceTypeInfo object_rti = ReferenceTypeInfo::CreateTop(false);
+        if (ShouldCreateBoundType(insert_point, obj, object_rti, nullptr, notNullBlock)) {
+          bound_type = new (graph_->GetArena()) HBoundType(
+              obj, object_rti, /* bound_can_be_null */ false);
+          notNullBlock->InsertInstructionBefore(bound_type, insert_point);
+        } else {
+          // We already have a bound type on the position we would need to insert
+          // the new one. The existing bound type should dominate all the users
+          // (dchecked) so there's no need to continue.
+          break;
+        }
       }
       user->ReplaceInput(bound_type, it.Current()->GetIndex());
     }
@@ -171,25 +249,23 @@
     HInstruction* user = it.Current()->GetUser();
     if (instanceOfTrueBlock->Dominates(user->GetBlock())) {
       if (bound_type == nullptr) {
+        ScopedObjectAccess soa(Thread::Current());
         HLoadClass* load_class = instanceOf->InputAt(1)->AsLoadClass();
-
-        ReferenceTypeInfo obj_rti = obj->GetReferenceTypeInfo();
         ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI();
-        bound_type = new (graph_->GetArena()) HBoundType(obj, class_rti);
-
-        // 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 {
-            bound_type->SetReferenceTypeInfo(
-                ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ false));
-          }
+        HInstruction* insert_point = instanceOfTrueBlock->GetFirstInstruction();
+        if (ShouldCreateBoundType(insert_point, obj, class_rti, nullptr, instanceOfTrueBlock)) {
+          bound_type = CreateBoundType(
+              graph_->GetArena(),
+              obj,
+              load_class,
+              false /* InstanceOf ensures the object is not null. */);
+          instanceOfTrueBlock->InsertInstructionBefore(bound_type, insert_point);
+        } else {
+          // We already have a bound type on the position we would need to insert
+          // the new one. The existing bound type should dominate all the users
+          // (dchecked) so there's no need to continue.
+          break;
         }
-
-        instanceOfTrueBlock->InsertInstructionBefore(
-            bound_type, instanceOfTrueBlock->GetFirstInstruction());
       }
       user->ReplaceInput(bound_type, it.Current()->GetIndex());
     }
@@ -266,6 +342,35 @@
   instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(class_handle, /* is_exact */ true));
 }
 
+void RTPVisitor::VisitCheckCast(HCheckCast* check_cast) {
+  HInstruction* obj = check_cast->InputAt(0);
+  HBoundType* bound_type = nullptr;
+  for (HUseIterator<HInstruction*> it(obj->GetUses()); !it.Done(); it.Advance()) {
+    HInstruction* user = it.Current()->GetUser();
+    if (check_cast->StrictlyDominates(user)) {
+      if (bound_type == nullptr) {
+        ScopedObjectAccess soa(Thread::Current());
+        HLoadClass* load_class = check_cast->InputAt(1)->AsLoadClass();
+        ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI();
+        if (ShouldCreateBoundType(check_cast->GetNext(), obj, class_rti, check_cast, nullptr)) {
+          bound_type = CreateBoundType(
+              GetGraph()->GetArena(),
+              obj,
+              load_class,
+              true /* CheckCast succeeds for nulls. */);
+          check_cast->GetBlock()->InsertInstructionAfter(bound_type, check_cast);
+        } else {
+          // We already have a bound type on the position we would need to insert
+          // the new one. The existing bound type should dominate all the users
+          // (dchecked) so there's no need to continue.
+          break;
+        }
+      }
+      user->ReplaceInput(bound_type, it.Current()->GetIndex());
+    }
+  }
+}
+
 void ReferenceTypePropagation::VisitPhi(HPhi* phi) {
   if (phi->GetType() != Primitive::kPrimNot) {
     return;
@@ -362,9 +467,9 @@
 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;
+  ReferenceTypeInfo upper_bound_rti = instr->GetUpperBound();
+  if (!upper_bound_rti.IsSupertypeOf(new_rti)) {
+    new_rti = upper_bound_rti;
   }
   instr->SetReferenceTypeInfo(new_rti);
 }
@@ -394,19 +499,22 @@
 bool ReferenceTypePropagation::UpdateNullability(HInstruction* instr) {
   DCHECK(instr->IsPhi() || instr->IsBoundType());
 
-  if (!instr->IsPhi()) {
-    return false;
+  bool existing_can_be_null = instr->CanBeNull();
+  if (instr->IsPhi()) {
+    HPhi* phi = instr->AsPhi();
+    bool new_can_be_null = false;
+    for (size_t i = 0; i < phi->InputCount(); i++) {
+      if (phi->InputAt(i)->CanBeNull()) {
+        new_can_be_null = true;
+        break;
+      }
+    }
+    phi->SetCanBeNull(new_can_be_null);
+  } else if (instr->IsBoundType()) {
+    HBoundType* bound_type = instr->AsBoundType();
+    bound_type->SetCanBeNull(instr->InputAt(0)->CanBeNull() && bound_type->GetUpperCanBeNull());
   }
-
-  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;
+  return existing_can_be_null != instr->CanBeNull();
 }
 
 void ReferenceTypePropagation::ProcessWorklist() {
diff --git a/compiler/optimizing/reference_type_propagation.h b/compiler/optimizing/reference_type_propagation.h
index 17cfed4..e8680ea 100644
--- a/compiler/optimizing/reference_type_propagation.h
+++ b/compiler/optimizing/reference_type_propagation.h
@@ -30,8 +30,10 @@
  */
 class ReferenceTypePropagation : public HOptimization {
  public:
-  ReferenceTypePropagation(HGraph* graph, StackHandleScopeCollection* handles)
-    : HOptimization(graph, kReferenceTypePropagationPassName),
+  ReferenceTypePropagation(HGraph* graph,
+                           StackHandleScopeCollection* handles,
+                           const char* name = kReferenceTypePropagationPassName)
+    : HOptimization(graph, name),
       handles_(handles),
       worklist_(graph->GetArena(), kDefaultWorklistSize) {}
 
diff --git a/test/450-checker-types/src/Main.java b/test/450-checker-types/src/Main.java
index 9070627..67060d9 100644
--- a/test/450-checker-types/src/Main.java
+++ b/test/450-checker-types/src/Main.java
@@ -14,7 +14,6 @@
 * limitations under the License.
 */
 
-
 interface Interface {
   void $noinline$f();
 }
@@ -52,6 +51,15 @@
   }
 }
 
+class Generic<A> {
+  private A a = null;
+  public A get() {
+    return a;
+  }
+}
+
+final class Final {}
+
 public class Main {
 
   /// CHECK-START: void Main.testSimpleRemove() instruction_simplifier_after_types (before)
@@ -395,6 +403,67 @@
     ((SubclassA)a[0]).$noinline$g();
   }
 
+  private Generic<SubclassC> genericC = new Generic<SubclassC>();
+  private Generic<Final> genericFinal = new Generic<Final>();
+
+  private SubclassC get() {
+    return genericC.get();
+  }
+
+  private Final getFinal() {
+    return genericFinal.get();
+  }
+
+  /// CHECK-START: SubclassC Main.inlineGenerics() reference_type_propagation (after)
+  /// CHECK:      <<Invoke:l\d+>>    InvokeStaticOrDirect klass:SubclassC
+  /// CHECK-NEXT:                    Return [<<Invoke>>]
+
+  /// CHECK-START: SubclassC Main.inlineGenerics() reference_type_propagation_after_inlining (after)
+  /// CHECK:      <<BoundType:l\d+>> BoundType klass:SubclassC
+  /// CHECK:                         Return [<<BoundType>>]
+  private SubclassC inlineGenerics() {
+    SubclassC c = get();
+    return c;
+  }
+
+  /// CHECK-START: Final Main.inlineGenericsFinal() reference_type_propagation (after)
+  /// CHECK:      <<Invoke:l\d+>>    InvokeStaticOrDirect klass:Final exact:true
+  /// CHECK-NEXT:                    Return [<<Invoke>>]
+
+  /// CHECK-START: Final Main.inlineGenericsFinal() reference_type_propagation_after_inlining (after)
+  /// CHECK:      <<BoundType:l\d+>> BoundType klass:Final exact:true
+  /// CHECK:                         Return [<<BoundType>>]
+  private Final inlineGenericsFinal() {
+    Final f = getFinal();
+    return f;
+  }
+
+  /// CHECK-START: void Main.boundOnlyOnceIfNotNull(java.lang.Object) reference_type_propagation_after_inlining (after)
+  /// CHECK:      BoundType
+  /// CHECK-NOT:  BoundType
+  private void boundOnlyOnceIfNotNull(Object o) {
+    if (o != null) {
+      o.toString();
+    }
+  }
+
+  /// CHECK-START: void Main.boundOnlyOnceIfInstanceOf(java.lang.Object) reference_type_propagation_after_inlining (after)
+  /// CHECK:      BoundType
+  /// CHECK-NOT:  BoundType
+  private void boundOnlyOnceIfInstanceOf(Object o) {
+    if (o instanceof Main) {
+      o.toString();
+    }
+  }
+
+  /// CHECK-START: Final Main.boundOnlyOnceCheckCast(Generic) reference_type_propagation_after_inlining (after)
+  /// CHECK:      BoundType
+  /// CHECK-NOT:  BoundType
+  private Final boundOnlyOnceCheckCast(Generic<Final> o) {
+    Final f = o.get();
+    return f;
+  }
+
   public static void main(String[] args) {
   }
 }