diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index 9754043..02e5dab 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -123,20 +123,21 @@
   }
 
   // If we removed at least one block, we need to recompute the full
-  // dominator tree.
+  // dominator tree and try block membership.
   if (removed_one_or_more_blocks) {
     graph_->ClearDominanceInformation();
     graph_->ComputeDominanceInformation();
+    graph_->ComputeTryBlockInformation();
   }
 
   // Connect successive blocks created by dead branches. Order does not matter.
   for (HReversePostOrderIterator it(*graph_); !it.Done();) {
     HBasicBlock* block  = it.Current();
-    if (block->IsEntryBlock() || block->GetSuccessors().size() != 1u) {
+    if (block->IsEntryBlock() || !block->GetLastInstruction()->IsGoto()) {
       it.Advance();
       continue;
     }
-    HBasicBlock* successor = block->GetSuccessors()[0];
+    HBasicBlock* successor = block->GetSingleSuccessor();
     if (successor->IsExitBlock() || successor->GetPredecessors().size() != 1u) {
       it.Advance();
       continue;
@@ -176,10 +177,7 @@
 }
 
 void HDeadCodeElimination::Run() {
-  if (!graph_->HasTryCatch()) {
-    // TODO: Update dead block elimination and enable for try/catch.
-    RemoveDeadBlocks();
-  }
+  RemoveDeadBlocks();
   SsaRedundantPhiElimination(graph_).Run();
   RemoveDeadInstructions();
 }
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 2d3dcf7..81daa7f 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -376,7 +376,11 @@
     HBasicBlock* first_predecessor = block->GetPredecessors()[0];
     DCHECK(!block->IsLoopHeader() || !block->GetLoopInformation()->IsBackEdge(*first_predecessor));
     const HTryBoundary* try_entry = first_predecessor->ComputeTryEntryOfSuccessors();
-    if (try_entry != nullptr) {
+    if (try_entry != nullptr &&
+        (block->GetTryCatchInformation() == nullptr ||
+         try_entry != &block->GetTryCatchInformation()->GetTryEntry())) {
+      // We are either setting try block membership for the first time or it
+      // has changed.
       block->SetTryCatchInformation(new (arena_) TryCatchInformation(*try_entry));
     }
   }
@@ -1394,7 +1398,7 @@
   // iteration.
   DCHECK(dominated_blocks_.empty());
 
-  // Remove the block from all loops it is included in.
+  // (1) Remove the block from all loops it is included in.
   for (HLoopInformationOutwardIterator it(*this); !it.Done(); it.Advance()) {
     HLoopInformation* loop_info = it.Current();
     loop_info->Remove(this);
@@ -1406,17 +1410,34 @@
     }
   }
 
-  // Disconnect the block from its predecessors and update their control-flow
-  // instructions.
+  // (2) Disconnect the block from its predecessors and update their
+  //     control-flow instructions.
   for (HBasicBlock* predecessor : predecessors_) {
     HInstruction* last_instruction = predecessor->GetLastInstruction();
+    if (last_instruction->IsTryBoundary() && !IsCatchBlock()) {
+      // This block is the only normal-flow successor of the TryBoundary which
+      // makes `predecessor` dead. Since DCE removes blocks in post order,
+      // exception handlers of this TryBoundary were already visited and any
+      // remaining handlers therefore must be live. We remove `predecessor` from
+      // their list of predecessors.
+      DCHECK_EQ(last_instruction->AsTryBoundary()->GetNormalFlowSuccessor(), this);
+      while (predecessor->GetSuccessors().size() > 1) {
+        HBasicBlock* handler = predecessor->GetSuccessors()[1];
+        DCHECK(handler->IsCatchBlock());
+        predecessor->RemoveSuccessor(handler);
+        handler->RemovePredecessor(predecessor);
+      }
+    }
+
     predecessor->RemoveSuccessor(this);
     uint32_t num_pred_successors = predecessor->GetSuccessors().size();
     if (num_pred_successors == 1u) {
       // If we have one successor after removing one, then we must have
-      // had an HIf or HPackedSwitch, as they have more than one successor.
-      // Replace those with a HGoto.
-      DCHECK(last_instruction->IsIf() || last_instruction->IsPackedSwitch());
+      // had an HIf, HPackedSwitch or HTryBoundary, as they have more than one
+      // successor. Replace those with a HGoto.
+      DCHECK(last_instruction->IsIf() ||
+             last_instruction->IsPackedSwitch() ||
+             (last_instruction->IsTryBoundary() && IsCatchBlock()));
       predecessor->RemoveInstruction(last_instruction);
       predecessor->AddInstruction(new (graph_->GetArena()) HGoto(last_instruction->GetDexPc()));
     } else if (num_pred_successors == 0u) {
@@ -1425,15 +1446,17 @@
       // SSAChecker fails unless it is not removed during the pass too.
       predecessor->RemoveInstruction(last_instruction);
     } else {
-      // There are multiple successors left.  This must come from a HPackedSwitch
-      // and we are in the middle of removing the HPackedSwitch. Like above, leave
-      // this alone, and the SSAChecker will fail if it is not removed as well.
-      DCHECK(last_instruction->IsPackedSwitch());
+      // There are multiple successors left. The removed block might be a successor
+      // of a PackedSwitch which will be completely removed (perhaps replaced with
+      // a Goto), or we are deleting a catch block from a TryBoundary. In either
+      // case, leave `last_instruction` as is for now.
+      DCHECK(last_instruction->IsPackedSwitch() ||
+             (last_instruction->IsTryBoundary() && IsCatchBlock()));
     }
   }
   predecessors_.clear();
 
-  // Disconnect the block from its successors and update their phis.
+  // (3) Disconnect the block from its successors and update their phis.
   for (HBasicBlock* successor : successors_) {
     // Delete this block from the list of predecessors.
     size_t this_index = successor->GetPredecessorIndexOf(this);
@@ -1443,30 +1466,57 @@
     // dominator of `successor` which violates the order DCHECKed at the top.
     DCHECK(!successor->predecessors_.empty());
 
-    // Remove this block's entries in the successor's phis.
-    if (successor->predecessors_.size() == 1u) {
-      // The successor has just one predecessor left. Replace phis with the only
-      // remaining input.
-      for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
-        HPhi* phi = phi_it.Current()->AsPhi();
-        phi->ReplaceWith(phi->InputAt(1 - this_index));
-        successor->RemovePhi(phi);
-      }
-    } else {
-      for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
-        phi_it.Current()->AsPhi()->RemoveInputAt(this_index);
+    // Remove this block's entries in the successor's phis. Skip exceptional
+    // successors because catch phi inputs do not correspond to predecessor
+    // blocks but throwing instructions. Their inputs will be updated in step (4).
+    if (!successor->IsCatchBlock()) {
+      if (successor->predecessors_.size() == 1u) {
+        // The successor has just one predecessor left. Replace phis with the only
+        // remaining input.
+        for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
+          HPhi* phi = phi_it.Current()->AsPhi();
+          phi->ReplaceWith(phi->InputAt(1 - this_index));
+          successor->RemovePhi(phi);
+        }
+      } else {
+        for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
+          phi_it.Current()->AsPhi()->RemoveInputAt(this_index);
+        }
       }
     }
   }
   successors_.clear();
 
+  // (4) Remove instructions and phis. Instructions should have no remaining uses
+  //     except in catch phis. If an instruction is used by a catch phi at `index`,
+  //     remove `index`-th input of all phis in the catch block since they are
+  //     guaranteed dead. Note that we may miss dead inputs this way but the
+  //     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);
+      }
+    }
+
+    RemoveInstruction(insn);
+  }
+  for (HInstructionIterator it(GetPhis()); !it.Done(); it.Advance()) {
+    RemovePhi(it.Current()->AsPhi());
+  }
+
   // Disconnect from the dominator.
   dominator_->RemoveDominatedBlock(this);
   SetDominator(nullptr);
 
-  // Delete from the graph. The function safely deletes remaining instructions
-  // and updates the reverse post order.
-  graph_->DeleteDeadBlock(this);
+  // Delete from the graph, update reverse post order.
+  graph_->DeleteDeadEmptyBlock(this);
   SetGraph(nullptr);
 }
 
@@ -1513,7 +1563,7 @@
   other->predecessors_.clear();
 
   // Delete `other` from the graph. The function updates reverse post order.
-  graph_->DeleteDeadBlock(other);
+  graph_->DeleteDeadEmptyBlock(other);
   other->SetGraph(nullptr);
 }
 
@@ -1577,19 +1627,14 @@
   std::copy_backward(blocks->begin() + after + 1u, blocks->begin() + old_size, blocks->end());
 }
 
-void HGraph::DeleteDeadBlock(HBasicBlock* block) {
+void HGraph::DeleteDeadEmptyBlock(HBasicBlock* block) {
   DCHECK_EQ(block->GetGraph(), this);
   DCHECK(block->GetSuccessors().empty());
   DCHECK(block->GetPredecessors().empty());
   DCHECK(block->GetDominatedBlocks().empty());
   DCHECK(block->GetDominator() == nullptr);
-
-  for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
-    block->RemoveInstruction(it.Current());
-  }
-  for (HBackwardInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
-    block->RemovePhi(it.Current()->AsPhi());
-  }
+  DCHECK(block->GetInstructions().IsEmpty());
+  DCHECK(block->GetPhis().IsEmpty());
 
   if (block->IsExitBlock()) {
     exit_block_ = nullptr;
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 4e81248..17b7094 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -240,8 +240,9 @@
   // put deoptimization instructions, etc.
   void TransformLoopHeaderForBCE(HBasicBlock* header);
 
-  // Removes `block` from the graph.
-  void DeleteDeadBlock(HBasicBlock* block);
+  // Removes `block` from the graph. Assumes `block` has been disconnected from
+  // other blocks and has no instructions or phis.
+  void DeleteDeadEmptyBlock(HBasicBlock* block);
 
   // Splits the edge between `block` and `successor` while preserving the
   // indices in the predecessor/successor lists. If there are multiple edges
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 7e3c5e6..9c19b98 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -531,6 +531,7 @@
   //       pipeline for all methods.
   if (graph->HasTryCatch()) {
     HOptimization* optimizations2[] = {
+      boolean_simplify,
       side_effects,
       gvn,
       dce2,
diff --git a/test/543-checker-dce-trycatch/expected.txt b/test/543-checker-dce-trycatch/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/543-checker-dce-trycatch/expected.txt
diff --git a/test/543-checker-dce-trycatch/info.txt b/test/543-checker-dce-trycatch/info.txt
new file mode 100644
index 0000000..e541938
--- /dev/null
+++ b/test/543-checker-dce-trycatch/info.txt
@@ -0,0 +1 @@
+Tests removal of try/catch blocks by DCE.
\ No newline at end of file
diff --git a/test/543-checker-dce-trycatch/smali/TestCase.smali b/test/543-checker-dce-trycatch/smali/TestCase.smali
new file mode 100644
index 0000000..44e907d
--- /dev/null
+++ b/test/543-checker-dce-trycatch/smali/TestCase.smali
@@ -0,0 +1,317 @@
+# 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.
+
+.class public LTestCase;
+.super Ljava/lang/Object;
+
+.method private static $inline$False()Z
+    .registers 1
+    const/4 v0, 0x0
+    return v0
+.end method
+
+# Test a case when one entering TryBoundary is dead but the rest of the try
+# block remains live.
+
+## CHECK-START: int TestCase.testDeadEntry(int, int, int, int) dead_code_elimination_final (before)
+## CHECK: Add
+
+## CHECK-START: int TestCase.testDeadEntry(int, int, int, int) dead_code_elimination_final (before)
+## CHECK:     TryBoundary kind:entry
+## CHECK:     TryBoundary kind:entry
+## CHECK-NOT: TryBoundary kind:entry
+
+## CHECK-START: int TestCase.testDeadEntry(int, int, int, int) dead_code_elimination_final (after)
+## CHECK-NOT: Add
+
+## CHECK-START: int TestCase.testDeadEntry(int, int, int, int) dead_code_elimination_final (after)
+## CHECK:     TryBoundary kind:entry
+## CHECK-NOT: TryBoundary kind:entry
+
+.method public static testDeadEntry(IIII)I
+    .registers 5
+
+    invoke-static {}, LTestCase;->$inline$False()Z
+    move-result v0
+
+    if-eqz v0, :else
+
+    add-int/2addr p0, p1
+
+    :try_start
+    div-int/2addr p0, p2
+
+    :else
+    div-int/2addr p0, p3
+    :try_end
+    .catchall {:try_start .. :try_end} :catch_all
+
+    :return
+    return p0
+
+    :catch_all
+    const/4 p0, -0x1
+    goto :return
+
+.end method
+
+# Test a case when one exiting TryBoundary is dead but the rest of the try
+# block remains live.
+
+## CHECK-START: int TestCase.testDeadExit(int, int, int, int) dead_code_elimination_final (before)
+## CHECK: Add
+
+## CHECK-START: int TestCase.testDeadExit(int, int, int, int) dead_code_elimination_final (before)
+## CHECK:     TryBoundary kind:exit
+## CHECK:     TryBoundary kind:exit
+## CHECK-NOT: TryBoundary kind:exit
+
+## CHECK-START: int TestCase.testDeadExit(int, int, int, int) dead_code_elimination_final (after)
+## CHECK-NOT: Add
+
+## CHECK-START: int TestCase.testDeadExit(int, int, int, int) dead_code_elimination_final (after)
+## CHECK:     TryBoundary kind:exit
+## CHECK-NOT: TryBoundary kind:exit
+
+.method public static testDeadExit(IIII)I
+    .registers 5
+
+    invoke-static {}, LTestCase;->$inline$False()Z
+    move-result v0
+
+    :try_start
+    div-int/2addr p0, p2
+
+    if-nez v0, :else
+
+    div-int/2addr p0, p3
+    goto :return
+    :try_end
+    .catchall {:try_start .. :try_end} :catch_all
+
+    :else
+    add-int/2addr p0, p1
+
+    :return
+    return p0
+
+    :catch_all
+    const/4 p0, -0x1
+    goto :return
+
+.end method
+
+# Test that a catch block remains live and consistent if some of try blocks
+# throwing into it are removed.
+
+## CHECK-START: int TestCase.testOneTryBlockDead(int, int, int, int) dead_code_elimination_final (before)
+## CHECK:     TryBoundary kind:entry
+## CHECK:     TryBoundary kind:entry
+## CHECK-NOT: TryBoundary kind:entry
+
+## CHECK-START: int TestCase.testOneTryBlockDead(int, int, int, int) dead_code_elimination_final (before)
+## CHECK:     TryBoundary kind:exit
+## CHECK:     TryBoundary kind:exit
+## CHECK-NOT: TryBoundary kind:exit
+
+## CHECK-START: int TestCase.testOneTryBlockDead(int, int, int, int) dead_code_elimination_final (after)
+## CHECK:     TryBoundary kind:entry
+## CHECK-NOT: TryBoundary kind:entry
+
+## CHECK-START: int TestCase.testOneTryBlockDead(int, int, int, int) dead_code_elimination_final (after)
+## CHECK:     TryBoundary kind:exit
+## CHECK-NOT: TryBoundary kind:exit
+
+.method public static testOneTryBlockDead(IIII)I
+    .registers 5
+
+    invoke-static {}, LTestCase;->$inline$False()Z
+    move-result v0
+
+    :try_start_1
+    div-int/2addr p0, p2
+    :try_end_1
+    .catchall {:try_start_1 .. :try_end_1} :catch_all
+
+    if-eqz v0, :return
+
+    :try_start_2
+    div-int/2addr p0, p3
+    :try_end_2
+    .catchall {:try_start_2 .. :try_end_2} :catch_all
+
+    :return
+    return p0
+
+    :catch_all
+    const/4 p0, -0x1
+    goto :return
+
+.end method
+
+# Test that try block membership is recomputed. In this test case, the try entry
+# stored with the merge block gets deleted and SSAChecker would fail if it was
+# not replaced with the try entry from the live branch.
+
+.method public static testRecomputeTryMembership(IIII)I
+    .registers 5
+
+    invoke-static {}, LTestCase;->$inline$False()Z
+    move-result v0
+
+    if-eqz v0, :else
+
+    # Dead branch
+    :try_start
+    div-int/2addr p0, p1
+    goto :merge
+
+    # Live branch
+    :else
+    div-int/2addr p0, p2
+
+    # Merge block. Make complex so it does not get merged with the live branch.
+    :merge
+    div-int/2addr p0, p3
+    if-eqz p0, :else2
+    div-int/2addr p0, p3
+    :else2
+    :try_end
+    .catchall {:try_start .. :try_end} :catch_all
+
+    :return
+    return p0
+
+    :catch_all
+    const/4 p0, -0x1
+    goto :return
+
+.end method
+
+# 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-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
+
+.method public static testCatchPhiInputs_DefinedInTryBlock(IIII)I
+    .registers 7
+
+    invoke-static {}, LTestCase;->$inline$False()Z
+    move-result v0
+
+    if-eqz v0, :else
+
+    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
+    div-int/2addr p0, v2
+
+    :else
+    const v1, 0xb           # live catch phi input
+    const v2, 0xc           # live catch phi input
+    div-int/2addr p0, p3
+
+    const v1, 0xd           # live catch phi input
+    const v2, 0xe           # live catch phi input
+    div-int/2addr p0, p1
+    :try_end
+    .catchall {:try_start .. :try_end} :catch_all
+
+    :return
+    return p0
+
+    :catch_all
+    sub-int p0, v1, v2      # use catch phi values
+    goto :return
+
+.end method
+
+# Test that DCE does not remove catch phi uses of instructions defined outside
+# 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
+## CHECK-DAG:     <<Const0xd:i\d+>> IntConstant 13
+## CHECK-DAG:     <<Const0xe:i\d+>> IntConstant 14
+## CHECK-DAG:     <<Const0xf:i\d+>> IntConstant 15
+## CHECK-DAG:                       Phi [<<Const0xa>>,<<Const0xb>>,<<Const0xd>>] reg:1 is_catch_phi:true
+## CHECK-DAG:                       Phi [<<Const0xf>>,<<Const0xc>>,<<Const0xe>>] reg:2 is_catch_phi:true
+
+## CHECK-START: int TestCase.testCatchPhiInputs_DefinedOutsideTryBlock(int, int, int, int) dead_code_elimination_final (after)
+## 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:                       Phi [<<Const0xa>>,<<Const0xb>>,<<Const0xd>>] reg:1 is_catch_phi:true
+## CHECK-DAG:                       Phi [<<Const0xf>>,<<Const0xc>>,<<Const0xe>>] reg:2 is_catch_phi:true
+
+.method public static testCatchPhiInputs_DefinedOutsideTryBlock(IIII)I
+    .registers 7
+
+    invoke-static {}, LTestCase;->$inline$False()Z
+    move-result v0
+
+    if-eqz v0, :else
+
+    shr-int/2addr p2, p3
+
+    :try_start
+    const v1, 0xa           # dead catch phi input, defined in entry block
+    const v2, 0xf           # dead catch phi input, defined in entry block
+    div-int/2addr p0, v2
+
+    :else
+    const v1, 0xb           # live catch phi input
+    const v2, 0xc           # live catch phi input
+    div-int/2addr p0, p3
+
+    const v1, 0xd           # live catch phi input
+    const v2, 0xe           # live catch phi input
+    div-int/2addr p0, p1
+    :try_end
+    .catchall {:try_start .. :try_end} :catch_all
+
+    :return
+    return p0
+
+    :catch_all
+    sub-int p0, v1, v2      # use catch phi values
+    goto :return
+
+.end method
diff --git a/test/543-checker-dce-trycatch/src/Main.java b/test/543-checker-dce-trycatch/src/Main.java
new file mode 100644
index 0000000..6e73d0d
--- /dev/null
+++ b/test/543-checker-dce-trycatch/src/Main.java
@@ -0,0 +1,66 @@
+/*
+ * 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 {
+
+  // Workaround for b/18051191.
+  class InnerClass {}
+
+  static boolean $inline$False() { return false; }
+
+  // DCE should only merge blocks where the first ends with a Goto.
+  // SSAChecker will fail if the following Throw->TryBoundary blocks are merged.
+  public static void doNotMergeThrow(String str) {
+    try {
+      throw new Exception(str);
+    } catch (Exception ex) {
+      return;
+    }
+  }
+
+  // Test deletion of all try/catch blocks. Multiple catch blocks test deletion
+  // where TryBoundary still has exception handler successors after having removed
+  // some already.
+
+  /// CHECK-START: void Main.testDeadTryCatch(boolean) dead_code_elimination_final (after)
+  /// CHECK-NOT: TryBoundary
+
+  /// CHECK-START: void Main.testDeadTryCatch(boolean) dead_code_elimination_final (after)
+  /// CHECK: begin_block
+  /// CHECK: begin_block
+  /// CHECK: begin_block
+  /// CHECK-NOT: begin_block
+
+  public static void testDeadTryCatch(boolean val) {
+    if ($inline$False()) {
+      try {
+        if (val) {
+          throw new ArithmeticException();
+        } else {
+          throw new ArrayIndexOutOfBoundsException();
+        }
+      } catch (ArithmeticException ex) {
+        System.out.println("Unexpected AE catch");
+      } catch (ArrayIndexOutOfBoundsException ex) {
+        System.out.println("Unexpected AIIOB catch");
+      }
+    }
+  }
+
+  public static void main(String[] args) {
+
+  }
+}
\ No newline at end of file