diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index d7e6bd8..9679d0a 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -257,6 +257,7 @@
 }
 
 void GraphChecker::VisitReturn(HReturn* ret) {
+  VisitInstruction(ret);
   if (!ret->GetBlock()->GetSingleSuccessor()->IsExitBlock()) {
     AddError(StringPrintf("%s:%d does not jump to the exit block.",
                           ret->DebugName(),
@@ -265,6 +266,7 @@
 }
 
 void GraphChecker::VisitReturnVoid(HReturnVoid* ret) {
+  VisitInstruction(ret);
   if (!ret->GetBlock()->GetSingleSuccessor()->IsExitBlock()) {
     AddError(StringPrintf("%s:%d does not jump to the exit block.",
                           ret->DebugName(),
@@ -272,6 +274,30 @@
   }
 }
 
+void GraphChecker::VisitCheckCast(HCheckCast* check) {
+  VisitInstruction(check);
+  HInstruction* input = check->InputAt(1);
+  if (!input->IsLoadClass()) {
+    AddError(StringPrintf("%s:%d expects a HLoadClass as second input, not %s:%d.",
+                          check->DebugName(),
+                          check->GetId(),
+                          input->DebugName(),
+                          input->GetId()));
+  }
+}
+
+void GraphChecker::VisitInstanceOf(HInstanceOf* instruction) {
+  VisitInstruction(instruction);
+  HInstruction* input = instruction->InputAt(1);
+  if (!input->IsLoadClass()) {
+    AddError(StringPrintf("%s:%d expects a HLoadClass as second input, not %s:%d.",
+                          instruction->DebugName(),
+                          instruction->GetId(),
+                          input->DebugName(),
+                          input->GetId()));
+  }
+}
+
 void SSAChecker::VisitBasicBlock(HBasicBlock* block) {
   super_type::VisitBasicBlock(block);
 
diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h
index bafa69d..7c72e23 100644
--- a/compiler/optimizing/graph_checker.h
+++ b/compiler/optimizing/graph_checker.h
@@ -48,6 +48,10 @@
   // Check that the HasBoundsChecks() flag is set for bounds checks.
   void VisitBoundsCheck(HBoundsCheck* check) OVERRIDE;
 
+  // Check that HCheckCast and HInstanceOf have HLoadClass as second input.
+  void VisitCheckCast(HCheckCast* check) OVERRIDE;
+  void VisitInstanceOf(HInstanceOf* check) OVERRIDE;
+
   // Check that the Return and ReturnVoid jump to the exit block.
   void VisitReturn(HReturn* ret) OVERRIDE;
   void VisitReturnVoid(HReturnVoid* ret) OVERRIDE;
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 30d61ef..c41574c 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -462,7 +462,7 @@
           ReferenceTypeInfo info = instruction->AsLoadClass()->GetLoadedClassRTI();
           ScopedObjectAccess soa(Thread::Current());
           if (info.GetTypeHandle().GetReference() != nullptr) {
-            StartAttributeStream("klass") << info.GetTypeHandle().Get();
+            StartAttributeStream("klass") << PrettyClass(info.GetTypeHandle().Get());
           } else {
             StartAttributeStream("klass") << "unresolved";
           }
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
index 6784098..3d6606b 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -151,6 +151,15 @@
   HBoundType* bound_type = nullptr;
 
   HInstruction* obj = instanceOf->InputAt(0);
+  if (obj->GetReferenceTypeInfo().IsExact() && !obj->IsPhi()) {
+    // This method is being called while doing a fixed-point calculation
+    // over phis. Non-phis instruction whose type is already known do
+    // not need to be bound to another type.
+    // Not that this also prevents replacing `HLoadClass` with a `HBoundType`.
+    // `HCheckCast` and `HInstanceOf` expect a `HLoadClass` as a second
+    // input.
+    return;
+  }
   for (HUseIterator<HInstruction*> it(obj->GetUses()); !it.Done(); it.Advance()) {
     HInstruction* user = it.Current()->GetUser();
     if (instanceOfTrueBlock->Dominates(user->GetBlock())) {
diff --git a/test/519-bound-load-class/expected.txt b/test/519-bound-load-class/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/519-bound-load-class/expected.txt
diff --git a/test/519-bound-load-class/info.txt b/test/519-bound-load-class/info.txt
new file mode 100644
index 0000000..5763962
--- /dev/null
+++ b/test/519-bound-load-class/info.txt
@@ -0,0 +1,3 @@
+Regression test for the optimizing compiler that
+used to crash when a `HCheckCast` did not have a `HLoadClass`
+as second input.
diff --git a/test/519-bound-load-class/src/Main.java b/test/519-bound-load-class/src/Main.java
new file mode 100644
index 0000000..41bb951
--- /dev/null
+++ b/test/519-bound-load-class/src/Main.java
@@ -0,0 +1,24 @@
+/*
+ * 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.
+ */
+
+public class Main {
+  public static void main(String[] args) {
+    Object o = Main.class;
+    if (o instanceof Main) {
+      System.out.println((Main)o);
+    }
+  }
+}