diff --git a/compiler/optimizing/boolean_simplifier.cc b/compiler/optimizing/boolean_simplifier.cc
index 30c89f2..9a92151 100644
--- a/compiler/optimizing/boolean_simplifier.cc
+++ b/compiler/optimizing/boolean_simplifier.cc
@@ -128,7 +128,7 @@
 
     // Remove the original condition if it is now unused.
     if (!if_condition->HasUses()) {
-      if_condition->GetBlock()->RemoveInstruction(if_condition);
+      if_condition->GetBlock()->RemoveInstructionOrPhi(if_condition);
     }
   }
 }
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index ca470f4..df3b1fc 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -481,6 +481,7 @@
 }
 
 void HBasicBlock::RemoveInstruction(HInstruction* instruction, bool ensure_safety) {
+  DCHECK(!instruction->IsPhi());
   Remove(&instructions_, this, instruction, ensure_safety);
 }
 
@@ -488,6 +489,14 @@
   Remove(&phis_, this, phi, ensure_safety);
 }
 
+void HBasicBlock::RemoveInstructionOrPhi(HInstruction* instruction, bool ensure_safety) {
+  if (instruction->IsPhi()) {
+    RemovePhi(instruction->AsPhi(), ensure_safety);
+  } else {
+    RemoveInstruction(instruction, ensure_safety);
+  }
+}
+
 void HEnvironment::CopyFrom(HEnvironment* env) {
   for (size_t i = 0; i < env->Size(); i++) {
     HInstruction* instruction = env->GetInstructionAt(i);
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index d970e38..753c95b 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -589,6 +589,7 @@
   // instruction is not in use and removes it from the use lists of its inputs.
   void RemoveInstruction(HInstruction* instruction, bool ensure_safety = true);
   void RemovePhi(HPhi* phi, bool ensure_safety = true);
+  void RemoveInstructionOrPhi(HInstruction* instruction, bool ensure_safety = true);
 
   bool IsLoopHeader() const {
     return (loop_information_ != nullptr) && (loop_information_->GetHeader() == this);
diff --git a/test/481-regression-phi-cond/expected.txt b/test/481-regression-phi-cond/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/481-regression-phi-cond/expected.txt
diff --git a/test/481-regression-phi-cond/info.txt b/test/481-regression-phi-cond/info.txt
new file mode 100644
index 0000000..7ac3bb6
--- /dev/null
+++ b/test/481-regression-phi-cond/info.txt
@@ -0,0 +1,2 @@
+Tests a regression in which simplification of a boolean selection could attempt
+to remove a Phi from the wrong instruction list.
diff --git a/test/481-regression-phi-cond/src/Main.java b/test/481-regression-phi-cond/src/Main.java
new file mode 100644
index 0000000..bad9669
--- /dev/null
+++ b/test/481-regression-phi-cond/src/Main.java
@@ -0,0 +1,51 @@
+/*
+* 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 assertBooleanEquals(boolean expected, boolean result) {
+    if (expected != result) {
+      throw new Error("Expected: " + expected + ", found: " + result);
+    }
+  }
+
+  public static boolean inlinePhi(boolean x, boolean y, boolean z) {
+    boolean phi;
+    if (z) {
+      phi = x;
+    } else {
+      phi = y;
+    }
+    return phi;
+  }
+
+  public static boolean dontUseParam(boolean x) {
+    return false;
+  }
+
+  public static boolean testCase(boolean x, boolean y, boolean z) {
+    // First create a Phi(x, y).
+    boolean phi = inlinePhi(x, y, z);
+    // Now use the phi as a condition which the boolean simplifier will try to
+    // optimize out. If the result is not used, the algorithm will try to remove
+    // the original condition (phi) and crash.
+    return dontUseParam(phi == false ? false : true);
+  }
+
+  public static void main(String[] args) {
+    assertBooleanEquals(false, testCase(true, true, true));
+  }
+}