diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 461be25..926bc15 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -1460,6 +1460,24 @@
   }
 }
 
+// Should be called on instructions in a dead block in post order. This method
+// assumes `insn` has been removed from all users with the exception of catch
+// phis because of missing exceptional edges in the graph. It removes the
+// instruction from catch phi uses, together with inputs of other catch phis in
+// the catch block at the same index, as these must be dead too.
+static void RemoveUsesOfDeadInstruction(HInstruction* insn) {
+  DCHECK(!insn->HasEnvironmentUses());
+  while (insn->HasNonEnvironmentUses()) {
+    HUseListNode<HInstruction*>* use = insn->GetUses().GetFirst();
+    size_t use_index = use->GetIndex();
+    HBasicBlock* user_block =  use->GetUser()->GetBlock();
+    DCHECK(use->GetUser()->IsPhi() && user_block->IsCatchBlock());
+    for (HInstructionIterator phi_it(user_block->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
+      phi_it.Current()->AsPhi()->RemoveInputAt(use_index);
+    }
+  }
+}
+
 void HBasicBlock::DisconnectAndDelete() {
   // Dominators must be removed after all the blocks they dominate. This way
   // a loop header is removed last, a requirement for correct loop information
@@ -1562,21 +1580,13 @@
   //     graph will always remain consistent.
   for (HBackwardInstructionIterator it(GetInstructions()); !it.Done(); it.Advance()) {
     HInstruction* insn = it.Current();
-    while (insn->HasUses()) {
-      DCHECK(IsTryBlock());
-      HUseListNode<HInstruction*>* use = insn->GetUses().GetFirst();
-      size_t use_index = use->GetIndex();
-      HBasicBlock* user_block =  use->GetUser()->GetBlock();
-      DCHECK(use->GetUser()->IsPhi() && user_block->IsCatchBlock());
-      for (HInstructionIterator phi_it(user_block->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
-        phi_it.Current()->AsPhi()->RemoveInputAt(use_index);
-      }
-    }
-
+    RemoveUsesOfDeadInstruction(insn);
     RemoveInstruction(insn);
   }
   for (HInstructionIterator it(GetPhis()); !it.Done(); it.Advance()) {
-    RemovePhi(it.Current()->AsPhi());
+    HPhi* insn = it.Current()->AsPhi();
+    RemoveUsesOfDeadInstruction(insn);
+    RemovePhi(insn);
   }
 
   // Disconnect from the dominator.
diff --git a/test/543-checker-dce-trycatch/smali/TestCase.smali b/test/543-checker-dce-trycatch/smali/TestCase.smali
index 44e907d..1756fa4 100644
--- a/test/543-checker-dce-trycatch/smali/TestCase.smali
+++ b/test/543-checker-dce-trycatch/smali/TestCase.smali
@@ -202,27 +202,35 @@
 # Test that DCE removes catch phi uses of instructions defined in dead try blocks.
 
 ## CHECK-START: int TestCase.testCatchPhiInputs_DefinedInTryBlock(int, int, int, int) dead_code_elimination_final (before)
-## CHECK-DAG:     <<Arg0:i\d+>>     ParameterValue
-## CHECK-DAG:     <<Arg1:i\d+>>     ParameterValue
-## CHECK-DAG:     <<Const0xa:i\d+>> IntConstant 10
-## CHECK-DAG:     <<Const0xb:i\d+>> IntConstant 11
-## CHECK-DAG:     <<Const0xc:i\d+>> IntConstant 12
-## CHECK-DAG:     <<Const0xd:i\d+>> IntConstant 13
-## CHECK-DAG:     <<Const0xe:i\d+>> IntConstant 14
-## CHECK-DAG:     <<Add:i\d+>>      Add [<<Arg0>>,<<Arg1>>]
-## CHECK-DAG:                       Phi [<<Const0xa>>,<<Const0xb>>,<<Const0xd>>] reg:1 is_catch_phi:true
-## CHECK-DAG:                       Phi [<<Add>>,<<Const0xc>>,<<Const0xe>>] reg:2 is_catch_phi:true
+## CHECK-DAG:     <<Arg0:i\d+>>      ParameterValue
+## CHECK-DAG:     <<Arg1:i\d+>>      ParameterValue
+## CHECK-DAG:     <<Const0xa:i\d+>>  IntConstant 10
+## CHECK-DAG:     <<Const0xb:i\d+>>  IntConstant 11
+## CHECK-DAG:     <<Const0xc:i\d+>>  IntConstant 12
+## CHECK-DAG:     <<Const0xd:i\d+>>  IntConstant 13
+## CHECK-DAG:     <<Const0xe:i\d+>>  IntConstant 14
+## CHECK-DAG:     <<Const0xf:i\d+>>  IntConstant 15
+## CHECK-DAG:     <<Const0x10:i\d+>> IntConstant 16
+## CHECK-DAG:     <<Const0x11:i\d+>> IntConstant 17
+## CHECK-DAG:     <<Add:i\d+>>       Add [<<Arg0>>,<<Arg1>>]
+## CHECK-DAG:     <<Phi:i\d+>>       Phi [<<Add>>,<<Const0xf>>] reg:3 is_catch_phi:false
+## CHECK-DAG:                        Phi [<<Const0xa>>,<<Const0xb>>,<<Const0xd>>] reg:1 is_catch_phi:true
+## CHECK-DAG:                        Phi [<<Add>>,<<Const0xc>>,<<Const0xe>>] reg:2 is_catch_phi:true
+## CHECK-DAG:                        Phi [<<Phi>>,<<Const0x10>>,<<Const0x11>>] reg:3 is_catch_phi:true
 
 ## CHECK-START: int TestCase.testCatchPhiInputs_DefinedInTryBlock(int, int, int, int) dead_code_elimination_final (after)
-## CHECK-DAG:     <<Const0xb:i\d+>> IntConstant 11
-## CHECK-DAG:     <<Const0xc:i\d+>> IntConstant 12
-## CHECK-DAG:     <<Const0xd:i\d+>> IntConstant 13
-## CHECK-DAG:     <<Const0xe:i\d+>> IntConstant 14
-## CHECK-DAG:                       Phi [<<Const0xb>>,<<Const0xd>>] reg:1 is_catch_phi:true
-## CHECK-DAG:                       Phi [<<Const0xc>>,<<Const0xe>>] reg:2 is_catch_phi:true
+## CHECK-DAG:     <<Const0xb:i\d+>>  IntConstant 11
+## CHECK-DAG:     <<Const0xc:i\d+>>  IntConstant 12
+## CHECK-DAG:     <<Const0xd:i\d+>>  IntConstant 13
+## CHECK-DAG:     <<Const0xe:i\d+>>  IntConstant 14
+## CHECK-DAG:     <<Const0x10:i\d+>> IntConstant 16
+## CHECK-DAG:     <<Const0x11:i\d+>> IntConstant 17
+## CHECK-DAG:                        Phi [<<Const0xb>>,<<Const0xd>>] reg:1 is_catch_phi:true
+## CHECK-DAG:                        Phi [<<Const0xc>>,<<Const0xe>>] reg:2 is_catch_phi:true
+## CHECK-DAG:                        Phi [<<Const0x10>>,<<Const0x11>>] reg:3 is_catch_phi:true
 
 .method public static testCatchPhiInputs_DefinedInTryBlock(IIII)I
-    .registers 7
+    .registers 8
 
     invoke-static {}, LTestCase;->$inline$False()Z
     move-result v0
@@ -232,17 +240,24 @@
     shr-int/2addr p2, p3
 
     :try_start
-    const v1, 0xa           # dead catch phi input, defined in entry block
-    add-int v2, p0, p1      # dead catch phi input, defined in the dead block
+    const v1, 0xa           # dead catch phi input, defined in entry block (HInstruction)
+    add-int v2, p0, p1      # dead catch phi input, defined in the dead block (HInstruction)
+    move v3, v2
+    if-eqz v3, :define_phi
+    const v3, 0xf
+    :define_phi
+    # v3 = Phi [Add, 0xf]   # dead catch phi input, defined in the dead block (HPhi)
     div-int/2addr p0, v2
 
     :else
     const v1, 0xb           # live catch phi input
     const v2, 0xc           # live catch phi input
+    const v3, 0x10          # live catch phi input
     div-int/2addr p0, p3
 
     const v1, 0xd           # live catch phi input
     const v2, 0xe           # live catch phi input
+    const v3, 0x11          # live catch phi input
     div-int/2addr p0, p1
     :try_end
     .catchall {:try_start .. :try_end} :catch_all
@@ -252,6 +267,7 @@
 
     :catch_all
     sub-int p0, v1, v2      # use catch phi values
+    sub-int p0, p0, v3      # use catch phi values
     goto :return
 
 .end method
@@ -260,8 +276,6 @@
 # dead try blocks.
 
 ## CHECK-START: int TestCase.testCatchPhiInputs_DefinedOutsideTryBlock(int, int, int, int) dead_code_elimination_final (before)
-## CHECK-DAG:     <<Arg0:i\d+>>     ParameterValue
-## CHECK-DAG:     <<Arg1:i\d+>>     ParameterValue
 ## CHECK-DAG:     <<Const0xa:i\d+>> IntConstant 10
 ## CHECK-DAG:     <<Const0xb:i\d+>> IntConstant 11
 ## CHECK-DAG:     <<Const0xc:i\d+>> IntConstant 12