diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index dc3124b..8ea8f3c 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -170,7 +170,8 @@
     }
   }
 
-  // Ensure the uses of `instruction` are defined in a block of the graph.
+  // Ensure the uses of `instruction` are defined in a block of the graph,
+  // and the entry in the use list is consistent.
   for (HUseIterator<HInstruction*> use_it(instruction->GetUses());
        !use_it.Done(); use_it.Advance()) {
     HInstruction* use = use_it.Current()->GetUser();
@@ -184,6 +185,27 @@
                             use->GetId(),
                             instruction->GetId()));
     }
+    size_t use_index = use_it.Current()->GetIndex();
+    if ((use_index >= use->InputCount()) || (use->InputAt(use_index) != instruction)) {
+      AddError(StringPrintf("User %s:%d of instruction %d has a wrong "
+                            "UseListNode index.",
+                            use->DebugName(),
+                            use->GetId(),
+                            instruction->GetId()));
+    }
+  }
+
+  // Ensure the environment uses entries are consistent.
+  for (HUseIterator<HEnvironment*> use_it(instruction->GetEnvUses());
+       !use_it.Done(); use_it.Advance()) {
+    HEnvironment* use = use_it.Current()->GetUser();
+    size_t use_index = use_it.Current()->GetIndex();
+    if ((use_index >= use->Size()) || (use->GetInstructionAt(use_index) != instruction)) {
+      AddError(StringPrintf("Environment user of %s:%d has a wrong "
+                            "UseListNode index.",
+                            instruction->DebugName(),
+                            instruction->GetId()));
+    }
   }
 
   // Ensure 'instruction' has pointers to its inputs' use entries.
@@ -191,7 +213,11 @@
     HUserRecord<HInstruction*> input_record = instruction->InputRecordAt(i);
     HInstruction* input = input_record.GetInstruction();
     HUseListNode<HInstruction*>* use_node = input_record.GetUseNode();
-    if (use_node == nullptr || !input->GetUses().Contains(use_node)) {
+    size_t use_index = use_node->GetIndex();
+    if ((use_node == nullptr)
+        || !input->GetUses().Contains(use_node)
+        || (use_index >= e)
+        || (use_index != i)) {
       AddError(StringPrintf("Instruction %s:%d has an invalid pointer to use entry "
                             "at input %u (%s:%d).",
                             instruction->DebugName(),
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index f07f4c7..d3ee770 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -712,6 +712,9 @@
 void HPhi::RemoveInputAt(size_t index) {
   RemoveAsUserOfInput(index);
   inputs_.DeleteAt(index);
+  for (size_t i = index, e = InputCount(); i < e; ++i) {
+    InputRecordAt(i).GetUseNode()->SetIndex(i);
+  }
 }
 
 #define DEFINE_ACCEPT(name, super)                                             \
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 50eecff..63f3c95 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -850,13 +850,14 @@
   HUseListNode* GetNext() const { return next_; }
   T GetUser() const { return user_; }
   size_t GetIndex() const { return index_; }
+  void SetIndex(size_t index) { index_ = index; }
 
  private:
   HUseListNode(T user, size_t index)
       : user_(user), index_(index), prev_(nullptr), next_(nullptr) {}
 
   T const user_;
-  const size_t index_;
+  size_t index_;
   HUseListNode<T>* prev_;
   HUseListNode<T>* next_;
 
@@ -1090,7 +1091,7 @@
 
   GrowableArray<HUserRecord<HEnvironment*> > vregs_;
 
-  friend HInstruction;
+  friend class HInstruction;
 
   DISALLOW_COPY_AND_ASSIGN(HEnvironment);
 };
diff --git a/runtime/gc/collector/mark_sweep.cc b/runtime/gc/collector/mark_sweep.cc
index f0e8d14..c6d2861 100644
--- a/runtime/gc/collector/mark_sweep.cc
+++ b/runtime/gc/collector/mark_sweep.cc
@@ -381,8 +381,8 @@
     if (UNLIKELY(obj == nullptr || !IsAligned<kPageSize>(obj) ||
                  (kIsDebugBuild && large_object_space != nullptr &&
                      !large_object_space->Contains(obj)))) {
-      LOG(ERROR) << "Tried to mark " << obj << " not contained by any spaces";
-      LOG(ERROR) << "Attempting see if it's a bad root";
+      LOG(INTERNAL_FATAL) << "Tried to mark " << obj << " not contained by any spaces";
+      LOG(INTERNAL_FATAL) << "Attempting see if it's a bad root";
       mark_sweep_->VerifyRoots();
       LOG(FATAL) << "Can't mark invalid object";
     }
@@ -498,7 +498,7 @@
     if (heap->GetLiveBitmap()->GetContinuousSpaceBitmap(root) == nullptr) {
       space::LargeObjectSpace* large_object_space = heap->GetLargeObjectsSpace();
       if (large_object_space != nullptr && !large_object_space->Contains(root)) {
-        LOG(ERROR) << "Found invalid root: " << root << " " << info;
+        LOG(INTERNAL_FATAL) << "Found invalid root: " << root << " " << info;
       }
     }
   }
diff --git a/test/483-dce-block/expected.txt b/test/483-dce-block/expected.txt
new file mode 100644
index 0000000..ef48625
--- /dev/null
+++ b/test/483-dce-block/expected.txt
@@ -0,0 +1 @@
+class Main
diff --git a/test/483-dce-block/info.txt b/test/483-dce-block/info.txt
new file mode 100644
index 0000000..3db88ab
--- /dev/null
+++ b/test/483-dce-block/info.txt
@@ -0,0 +1,2 @@
+Regression test for optimizing that used to crash
+compiling the `foo` method.
diff --git a/test/483-dce-block/src/Main.java b/test/483-dce-block/src/Main.java
new file mode 100644
index 0000000..2f66a74
--- /dev/null
+++ b/test/483-dce-block/src/Main.java
@@ -0,0 +1,58 @@
+/*
+ * 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 foo(Object o, int a) {
+    Object result = null;
+    if (o instanceof Main) {
+      // The compiler optimizes the type of `o` by introducing
+      // a `HBoundType` in this block.
+      while (a != 3) {
+        if (a == 2) {
+          a++;
+          result = o;
+          continue;
+        } else if (willInline()) {
+          // This block will be detected as dead after inlining.
+          result = new Object();
+          continue;
+        }
+        result = new Object();
+      }
+      // The compiler produces a phi at the back edge for `result`.
+      // Before dead block elimination, the phi has three inputs:
+      // result = (new Object(), new Object(), HBoundType)
+      //
+      // After dead block elimination, the phi has now two inputs:
+      // result = (new Object(), HBoundType)
+      //
+      // Our internal data structure for linking users and inputs expect
+      // the input index stored in that data structure to be the index
+      // in the inputs array. So the index before dead block elimination
+      // of the `HBoundType` would be 2. Dead block elimination must update
+      // that index to be 1.
+    }
+    System.out.println(result.getClass());
+  }
+
+  public static boolean willInline() {
+    return false;
+  }
+
+  public static void main(String[] args) {
+    foo(new Main(), 2);
+  }
+}