Index: llvm/test/tools/llvm-reduce/mir/remove-frame-destroy.mir
===================================================================
--- /dev/null
+++ llvm/test/tools/llvm-reduce/mir/remove-frame-destroy.mir
@@ -0,0 +1,24 @@
+# REQUIRES: amdgpu-registered-target
+# RUN: llvm-reduce --delta-passes=instructions -mtriple=amdgcn-amd-amdhsa --test FileCheck --test-arg --check-prefix=CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t 2> %t.log
+# RUN: FileCheck --check-prefix=RESULT %s < %t
+
+# CHECK-INTERESTINGNESS: S_NOP 0
+
+# RESULT: ADJCALLSTACKUP
+# RESULT-NEXT: ADJCALLSTACKDOWN
+# RESULT-NEXT: S_ENDPGM 0
+
+---
+name: frame_setup_destroy
+tracksRegLiveness: true
+machineFunctionInfo:
+  stackPtrOffsetReg: '$sgpr32'
+body:             |
+  bb.0:
+    S_NOP 0
+    ADJCALLSTACKUP 0, 0, implicit-def dead $scc, implicit-def $sgpr32, implicit $sgpr32
+    S_NOP 0
+    ADJCALLSTACKDOWN 0, 0, implicit-def dead $scc, implicit-def $sgpr32, implicit $sgpr32
+    S_ENDPGM 0
+
+...
Index: llvm/tools/llvm-reduce/deltas/ReduceInstructionsMIR.cpp
===================================================================
--- llvm/tools/llvm-reduce/deltas/ReduceInstructionsMIR.cpp
+++ llvm/tools/llvm-reduce/deltas/ReduceInstructionsMIR.cpp
@@ -46,6 +46,21 @@
   return 0;
 }
 
+static bool shouldNotRemoveInstruction(const TargetInstrInfo &TII,
+                                       const MachineInstr &MI) {
+  if (MI.isTerminator())
+    return true;
+
+  // The MIR is almost certainly going to be invalid if frame instructions are
+  // deleted individually since they need to come in balanced pairs, so don't
+  // try to delete them.
+  if (MI.getOpcode() == TII.getCallFrameSetupOpcode() ||
+      MI.getOpcode() == TII.getCallFrameDestroyOpcode())
+    return true;
+
+  return false;
+}
+
 static void extractInstrFromFunction(Oracle &O, MachineFunction &MF) {
   MachineDominatorTree MDT;
   MDT.runOnMachineFunction(MF);
@@ -62,7 +77,7 @@
   // Mark MIs for deletion according to some criteria.
   for (auto &MBB : MF) {
     for (auto &MI : MBB) {
-      if (MI.isTerminator())
+      if (shouldNotRemoveInstruction(*TII, MI))
         continue;
       if (!O.shouldKeep())
         ToDelete.insert(&MI);