diff --git a/llvm/lib/CodeGen/MachineOutliner.cpp b/llvm/lib/CodeGen/MachineOutliner.cpp
--- a/llvm/lib/CodeGen/MachineOutliner.cpp
+++ b/llvm/lib/CodeGen/MachineOutliner.cpp
@@ -669,7 +669,8 @@
     if (I->isCFIInstruction()) {
       unsigned CFIIndex = NewMI->getOperand(0).getCFIIndex();
       MCCFIInstruction CFI = Instrs[CFIIndex];
-      (void)MF.addFrameInst(CFI);
+      NewMI->removeOperand(0);
+      MachineInstrBuilder(MF, NewMI).addCFIIndex(MF.addFrameInst(CFI));
     }
     NewMI->dropMemRefs(MF);
 
diff --git a/llvm/lib/CodeGen/MachineVerifier.cpp b/llvm/lib/CodeGen/MachineVerifier.cpp
--- a/llvm/lib/CodeGen/MachineVerifier.cpp
+++ b/llvm/lib/CodeGen/MachineVerifier.cpp
@@ -64,6 +64,7 @@
 #include "llvm/InitializePasses.h"
 #include "llvm/MC/LaneBitmask.h"
 #include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCDwarf.h"
 #include "llvm/MC/MCInstrDesc.h"
 #include "llvm/MC/MCRegisterInfo.h"
 #include "llvm/MC/MCTargetOptions.h"
@@ -2212,6 +2213,11 @@
     }
     break;
 
+  case MachineOperand::MO_CFIIndex:
+    if (MO->getCFIIndex() >= MF->getFrameInstructions().size())
+      report("CFI instruction has invalid index", MO, MONum);
+    break;
+
   default:
     break;
   }
diff --git a/llvm/lib/Target/AArch64/AArch64InstrInfo.cpp b/llvm/lib/Target/AArch64/AArch64InstrInfo.cpp
--- a/llvm/lib/Target/AArch64/AArch64InstrInfo.cpp
+++ b/llvm/lib/Target/AArch64/AArch64InstrInfo.cpp
@@ -7014,12 +7014,10 @@
   // We check to see if CFI Instructions are present, and if they are
   // we find the number of CFI Instructions in the candidates.
   unsigned CFICount = 0;
-  MachineBasicBlock::iterator MBBI = RepeatedSequenceLocs[0].front();
-  for (unsigned Loc = RepeatedSequenceLocs[0].getStartIdx();
-       Loc < RepeatedSequenceLocs[0].getEndIdx() + 1; Loc++) {
-    if (MBBI->isCFIInstruction())
+  for (auto &I : make_range(RepeatedSequenceLocs[0].front(),
+                            std::next(RepeatedSequenceLocs[0].back()))) {
+    if (I.isCFIInstruction())
       CFICount++;
-    MBBI++;
   }
 
   // We compare the number of found CFI Instructions to  the number of CFI
@@ -7027,12 +7025,21 @@
   // since if we outline one of the CFI instructions in a function, we have to
   // outline them all for correctness. If we do not, the address offsets will be
   // incorrect between the two sections of the program.
-  for (outliner::Candidate &C : RepeatedSequenceLocs) {
-    std::vector<MCCFIInstruction> CFIInstructions =
-        C.getMF()->getFrameInstructions();
+  if (CFICount > 0) {
+    for (outliner::Candidate &C : RepeatedSequenceLocs) {
+      if (std::next(C.getMF()->begin()) != C.getMF()->end())
+        return outliner::OutlinedFunction();
 
-    if (CFICount > 0 && CFICount != CFIInstructions.size())
-      return outliner::OutlinedFunction();
+      unsigned FnCFICount = 0;
+      MachineBasicBlock *MBB = &*C.getMF()->begin();
+      for (auto &I : *MBB) {
+        if (I.isCFIInstruction())
+          FnCFICount++;
+      }
+
+      if (FnCFICount != CFICount)
+        return outliner::OutlinedFunction();
+    }
   }
 
   // Returns true if an instructions is safe to fix up, false otherwise.
diff --git a/llvm/lib/Target/X86/X86InstrInfo.cpp b/llvm/lib/Target/X86/X86InstrInfo.cpp
--- a/llvm/lib/Target/X86/X86InstrInfo.cpp
+++ b/llvm/lib/Target/X86/X86InstrInfo.cpp
@@ -9488,12 +9488,10 @@
   // We check to see if CFI Instructions are present, and if they are
   // we find the number of CFI Instructions in the candidates.
   unsigned CFICount = 0;
-  MachineBasicBlock::iterator MBBI = RepeatedSequenceLocs[0].front();
-  for (unsigned Loc = RepeatedSequenceLocs[0].getStartIdx();
-       Loc < RepeatedSequenceLocs[0].getEndIdx() + 1; Loc++) {
-    if (MBBI->isCFIInstruction())
+  for (auto &I : make_range(RepeatedSequenceLocs[0].front(),
+                            std::next(RepeatedSequenceLocs[0].back()))) {
+    if (I.isCFIInstruction())
       CFICount++;
-    MBBI++;
   }
 
   // We compare the number of found CFI Instructions to  the number of CFI
@@ -9501,12 +9499,21 @@
   // since if we outline one of the CFI instructions in a function, we have to
   // outline them all for correctness. If we do not, the address offsets will be
   // incorrect between the two sections of the program.
-  for (outliner::Candidate &C : RepeatedSequenceLocs) {
-    std::vector<MCCFIInstruction> CFIInstructions =
-        C.getMF()->getFrameInstructions();
+  if (CFICount > 0) {
+    for (outliner::Candidate &C : RepeatedSequenceLocs) {
+      if (std::next(C.getMF()->begin()) != C.getMF()->end())
+        return outliner::OutlinedFunction();
+
+      unsigned FnCFICount = 0;
+      MachineBasicBlock *MBB = &*C.getMF()->begin();
+      for (auto &I : *MBB) {
+        if (I.isCFIInstruction())
+          FnCFICount++;
+      }
 
-    if (CFICount > 0 && CFICount != CFIInstructions.size())
-      return outliner::OutlinedFunction();
+      if (FnCFICount != CFICount)
+        return outliner::OutlinedFunction();
+    }
   }
 
   // FIXME: Use real size in bytes for call and ret instructions.
diff --git a/llvm/test/CodeGen/AArch64/machine-outliner-cfi-tail.mir b/llvm/test/CodeGen/AArch64/machine-outliner-cfi-tail.mir
--- a/llvm/test/CodeGen/AArch64/machine-outliner-cfi-tail.mir
+++ b/llvm/test/CodeGen/AArch64/machine-outliner-cfi-tail.mir
@@ -1,9 +1,10 @@
 # NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
-# RUN: llc -mtriple=aarch64-apple-unknown -run-pass=machine-outliner -verify-machineinstrs %s -o - | FileCheck %s
+# RUN: llc -mtriple=aarch64-apple-unknown -run-pass=branch-folder,machine-outliner -verify-machineinstrs %s -o - | FileCheck %s
 
 # Outlining CFI instructions is unsafe if it is not tail called, but otherwise,
-# it requires fixups. Show that we include CFI instructions in tail call 
-# outlined sequences right now.
+# it requires fixups. Show that we include CFI instructions in tail call
+# outlined sequences right now. Show that we count CFI instructions correctly
+# in the presence of dead CFI instructions.
 
 --- |
   define void @foo() #0 { ret void }
@@ -15,11 +16,13 @@
 name:            foo
 tracksRegLiveness: true
 body:             |
+  ; CHECK-LABEL: name: foo
+  ; CHECK: bb.0:
+  ; CHECK-NEXT:   liveins: $lr
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   TCRETURNdi @OUTLINED_FUNCTION_0, 0, implicit $sp, implicit-def $w9, implicit-def $w10, implicit-def $w11, implicit-def $w12, implicit-def $w13, implicit-def $w14, implicit-def $w15, implicit $wzr, implicit $sp
   bb.0:
   liveins: $lr
-    ; CHECK-LABEL: name: foo
-    ; CHECK: liveins: $lr
-    ; CHECK: TCRETURNdi @OUTLINED_FUNCTION_0, 0, implicit $sp, implicit-def $w9, implicit-def $w10, implicit-def $w11, implicit-def $w12, implicit-def $w13, implicit-def $w14, implicit-def $w15, implicit $wzr, implicit $sp
     $w9 = ORRWri $wzr, 1
     $w10 = ORRWri $wzr, 2
     $w11 = ORRWri $wzr, 3
@@ -29,6 +32,9 @@
     $w14 = ORRWri $wzr, 3
     $w15 = ORRWri $wzr, 4
     RET undef $lr
+
+  bb.1:
+    frame-setup CFI_INSTRUCTION def_cfa $w29, 16
 ...
 ---
 name:            bar
@@ -38,7 +44,8 @@
   liveins: $lr
     ; CHECK-LABEL: name: bar
     ; CHECK: liveins: $lr
-    ; CHECK: TCRETURNdi @OUTLINED_FUNCTION_0, 0, implicit $sp, implicit-def $w9, implicit-def $w10, implicit-def $w11, implicit-def $w12, implicit-def $w13, implicit-def $w14, implicit-def $w15, implicit $wzr, implicit $sp
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: TCRETURNdi @OUTLINED_FUNCTION_0, 0, implicit $sp, implicit-def $w9, implicit-def $w10, implicit-def $w11, implicit-def $w12, implicit-def $w13, implicit-def $w14, implicit-def $w15, implicit $wzr, implicit $sp
     $w9 = ORRWri $wzr, 1
     $w10 = ORRWri $wzr, 2
     $w11 = ORRWri $wzr, 3
@@ -57,7 +64,8 @@
   liveins: $lr
     ; CHECK-LABEL: name: baz
     ; CHECK: liveins: $lr
-    ; CHECK: TCRETURNdi @OUTLINED_FUNCTION_0, 0, implicit $sp, implicit-def $w9, implicit-def $w10, implicit-def $w11, implicit-def $w12, implicit-def $w13, implicit-def $w14, implicit-def $w15, implicit $wzr, implicit $sp
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: TCRETURNdi @OUTLINED_FUNCTION_0, 0, implicit $sp, implicit-def $w9, implicit-def $w10, implicit-def $w11, implicit-def $w12, implicit-def $w13, implicit-def $w14, implicit-def $w15, implicit $wzr, implicit $sp
     $w9 = ORRWri $wzr, 1
     $w10 = ORRWri $wzr, 2
     $w11 = ORRWri $wzr, 3
diff --git a/llvm/test/CodeGen/AArch64/machine-outliner-cfi.mir b/llvm/test/CodeGen/AArch64/machine-outliner-cfi.mir
--- a/llvm/test/CodeGen/AArch64/machine-outliner-cfi.mir
+++ b/llvm/test/CodeGen/AArch64/machine-outliner-cfi.mir
@@ -1,15 +1,17 @@
 # NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
-# RUN: llc -mtriple=aarch64-apple-unknown -run-pass=machine-outliner -verify-machineinstrs %s -o - | FileCheck %s
+# RUN: llc -mtriple=aarch64-apple-unknown -run-pass=machine-outliner -verify-machineinstrs -enable-machine-outliner=always %s -o - | FileCheck %s
 
 # Outlining CFI instructions is unsafe if it is not tail called, but otherwise,
 # it requires fixups. Show that we don't include CFI instructions in non
-# tail call outlined sequences right now.
+# tail call outlined sequences right now. Show that we count CFI instructions
+# correctly in the presence of debug info.
 
 --- |
   define void @foo() #0 { ret void }
   define void @bar() #0 { ret void }
   define void @baz() #0 { ret void }
   attributes #0 = { noredzone }
+
 ...
 ---
 name:            foo
@@ -19,15 +21,28 @@
   liveins: $lr
     ; CHECK-LABEL: name: foo
     ; CHECK: liveins: $lr
-    ; CHECK: $w9 = ORRWri $wzr, 1
-    ; CHECK: $w10 = ORRWri $wzr, 2
-    ; CHECK: $w11 = ORRWri $wzr, 3
-    ; CHECK: frame-setup CFI_INSTRUCTION def_cfa $w29, 16
-    ; CHECK: $w20 = ORRWri $wzr, 1
-    ; CHECK: TCRETURNdi @OUTLINED_FUNCTION_0, 0, implicit $sp, implicit-def $w12, implicit-def $w13, implicit-def $w14, implicit-def $w15, implicit $wzr, implicit $sp
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: $w9 = ORRWri $wzr, 1
+    ; CHECK-NEXT: $w10 = ORRWri $wzr, 2
+    ; CHECK-NEXT: $w11 = ORRWri $wzr, 3
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: frame-setup CFI_INSTRUCTION def_cfa $w29, 16
+    ; CHECK-NEXT: $w20 = ORRWri $wzr, 1
+    ; CHECK-NEXT: TCRETURNdi @OUTLINED_FUNCTION_0, 0, implicit $sp, implicit-def $w12, implicit-def $w13, implicit-def $w14, implicit-def $w15, implicit $wzr, implicit $sp
     $w9 = ORRWri $wzr, 1
     $w10 = ORRWri $wzr, 2
     $w11 = ORRWri $wzr, 3
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
     frame-setup CFI_INSTRUCTION def_cfa $w29, 16
     $w20 = ORRWri $wzr, 1
     $w12 = ORRWri $wzr, 1
@@ -44,15 +59,28 @@
   liveins: $lr
     ; CHECK-LABEL: name: bar
     ; CHECK: liveins: $lr
-    ; CHECK: $w9 = ORRWri $wzr, 1
-    ; CHECK: $w10 = ORRWri $wzr, 2
-    ; CHECK: $w11 = ORRWri $wzr, 3
-    ; CHECK: frame-setup CFI_INSTRUCTION def_cfa $w29, 16
-    ; CHECK: $w21 = ORRWri $wzr, 1
-    ; CHECK: TCRETURNdi @OUTLINED_FUNCTION_0, 0, implicit $sp, implicit-def $w12, implicit-def $w13, implicit-def $w14, implicit-def $w15, implicit $wzr, implicit $sp
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: $w9 = ORRWri $wzr, 1
+    ; CHECK-NEXT: $w10 = ORRWri $wzr, 2
+    ; CHECK-NEXT: $w11 = ORRWri $wzr, 3
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: frame-setup CFI_INSTRUCTION def_cfa $w29, 16
+    ; CHECK-NEXT: $w21 = ORRWri $wzr, 1
+    ; CHECK-NEXT: TCRETURNdi @OUTLINED_FUNCTION_0, 0, implicit $sp, implicit-def $w12, implicit-def $w13, implicit-def $w14, implicit-def $w15, implicit $wzr, implicit $sp
     $w9 = ORRWri $wzr, 1
     $w10 = ORRWri $wzr, 2
     $w11 = ORRWri $wzr, 3
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
     frame-setup CFI_INSTRUCTION def_cfa $w29, 16
     $w21 = ORRWri $wzr, 1
     $w12 = ORRWri $wzr, 1
@@ -69,15 +97,28 @@
   liveins: $lr
     ; CHECK-LABEL: name: baz
     ; CHECK: liveins: $lr
-    ; CHECK: $w9 = ORRWri $wzr, 1
-    ; CHECK: $w10 = ORRWri $wzr, 2
-    ; CHECK: $w11 = ORRWri $wzr, 3
-    ; CHECK: frame-setup CFI_INSTRUCTION def_cfa $w29, 16
-    ; CHECK: $w22 = ORRWri $wzr, 1
-    ; CHECK: TCRETURNdi @OUTLINED_FUNCTION_0, 0, implicit $sp, implicit-def $w12, implicit-def $w13, implicit-def $w14, implicit-def $w15, implicit $wzr, implicit $sp
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: $w9 = ORRWri $wzr, 1
+    ; CHECK-NEXT: $w10 = ORRWri $wzr, 2
+    ; CHECK-NEXT: $w11 = ORRWri $wzr, 3
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: DBG_VALUE $w9, $noreg
+    ; CHECK-NEXT: frame-setup CFI_INSTRUCTION def_cfa $w29, 16
+    ; CHECK-NEXT: $w22 = ORRWri $wzr, 1
+    ; CHECK-NEXT: TCRETURNdi @OUTLINED_FUNCTION_0, 0, implicit $sp, implicit-def $w12, implicit-def $w13, implicit-def $w14, implicit-def $w15, implicit $wzr, implicit $sp
     $w9 = ORRWri $wzr, 1
     $w10 = ORRWri $wzr, 2
     $w11 = ORRWri $wzr, 3
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
+    DBG_VALUE $w9, $noreg
     frame-setup CFI_INSTRUCTION def_cfa $w29, 16
     $w22 = ORRWri $wzr, 1
     $w12 = ORRWri $wzr, 1