diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 4fbb033..cb07d2e 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -183,6 +183,7 @@
 }
 
 void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) {
+  DCHECK(reverse_post_order_.empty()) << "We shouldn't have dominance information.";
   for (size_t i = 0; i < blocks_.size(); ++i) {
     if (!visited.IsBitSet(i)) {
       HBasicBlock* block = blocks_[i];
@@ -190,7 +191,7 @@
 
       // Disconnect from its sucessors, and remove all remaining uses.
       block->DisconnectFromSuccessors(&visited);
-      block->RemoveCatchPhiUses(/* remove_instruction = */ false);
+      block->RemoveCatchPhiUsesAndInstruction(/* building_dominator_tree = */ true);
 
       // Remove the block from the list of blocks, so that further analyses
       // never see it.
@@ -2435,7 +2436,7 @@
   //     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.
-  RemoveCatchPhiUses(/* remove_instruction = */ true);
+  RemoveCatchPhiUsesAndInstruction(/* building_dominator_tree = */ false);
 
   // (4) Disconnect the block from its predecessors and update their
   //     control-flow instructions.
@@ -2544,20 +2545,32 @@
   successors_.clear();
 }
 
-void HBasicBlock::RemoveCatchPhiUses(bool remove_instruction) {
+void HBasicBlock::RemoveCatchPhiUsesAndInstruction(bool building_dominator_tree) {
   for (HBackwardInstructionIterator it(GetInstructions()); !it.Done(); it.Advance()) {
     HInstruction* insn = it.Current();
     RemoveCatchPhiUsesOfDeadInstruction(insn);
-    if (remove_instruction) {
-      RemoveInstruction(insn);
+
+    // If we are building the dominator tree, we removed all input records previously.
+    // `RemoveInstruction` will try to remove them again but that's not something we support and we
+    // will crash. We check here since we won't be checking that in RemoveInstruction.
+    if (building_dominator_tree) {
+      DCHECK(insn->GetUses().empty());
+      DCHECK(insn->GetEnvUses().empty());
     }
+    RemoveInstruction(insn, /* ensure_safety= */ !building_dominator_tree);
   }
   for (HInstructionIterator it(GetPhis()); !it.Done(); it.Advance()) {
     HPhi* insn = it.Current()->AsPhi();
     RemoveCatchPhiUsesOfDeadInstruction(insn);
-    if (remove_instruction) {
-      RemovePhi(insn);
+
+    // If we are building the dominator tree, we removed all input records previously.
+    // `RemovePhi` will try to remove them again but that's not something we support and we
+    // will crash. We check here since we won't be checking that in RemovePhi.
+    if (building_dominator_tree) {
+      DCHECK(insn->GetUses().empty());
+      DCHECK(insn->GetEnvUses().empty());
     }
+    RemovePhi(insn, /* ensure_safety= */ !building_dominator_tree);
   }
 }