Index: include/llvm/CodeGen/LivePhysRegs.h
===================================================================
--- include/llvm/CodeGen/LivePhysRegs.h
+++ include/llvm/CodeGen/LivePhysRegs.h
@@ -152,6 +152,10 @@
   /// \brief Adds live-in registers from basic block \p MBB, taking associated
   /// lane masks into consideration.
   void addBlockLiveIns(const MachineBasicBlock &MBB);
+
+  /// Adds pristine registers. Pristine registers are callee saved registers
+  /// that are unused in the function.
+  void addPristines(const MachineFunction &MF);
 };
 
 inline raw_ostream &operator<<(raw_ostream &OS, const LivePhysRegs& LR) {
Index: include/llvm/CodeGen/LiveRegUnits.h
===================================================================
--- include/llvm/CodeGen/LiveRegUnits.h
+++ include/llvm/CodeGen/LiveRegUnits.h
@@ -51,7 +51,7 @@
   void clear() { Units.reset(); }
 
   /// Returns true if the set is empty.
-  bool empty() const { return Units.empty(); }
+  bool empty() const { return Units.none(); }
 
   /// Adds register units covered by physical register \p Reg.
   void addReg(unsigned Reg) {
@@ -123,6 +123,11 @@
   const BitVector &getBitVector() const {
     return Units;
   }
+
+private:
+  /// Adds pristine registers. Pristine registers are callee saved registers
+  /// that are unused in the function.
+  void addPristines(const MachineFunction &MF);
 };
 
 } // end namespace llvm
Index: lib/CodeGen/LivePhysRegs.cpp
===================================================================
--- lib/CodeGen/LivePhysRegs.cpp
+++ lib/CodeGen/LivePhysRegs.cpp
@@ -166,17 +166,32 @@
     LiveRegs.addReg(*CSR);
 }
 
-/// Adds pristine registers to the given \p LiveRegs. Pristine registers are
-/// callee saved registers that are unused in the function.
-static void addPristines(LivePhysRegs &LiveRegs, const MachineFunction &MF) {
+void LivePhysRegs::addPristines(const MachineFunction &MF) {
   const MachineFrameInfo &MFI = MF.getFrameInfo();
   if (!MFI.isCalleeSavedInfoValid())
     return;
+  /// This function will usually be called on an empty object, handle this
+  /// as a special case.
+  if (empty()) {
+    /// Add all callee saved regs, then remove the ones that are saved and
+    /// restored.
+    addCalleeSavedRegs(*this, MF);
+    /// Remove the ones that are not saved/restored; they are pristine.
+    for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
+      removeReg(Info.getReg());
+    return;
+  }
+  /// If a callee-saved register that is not pristine is already present
+  /// in the set, we should make sure that it stays in it. Precompute the
+  /// set of pristine registers in a separate object.
   /// Add all callee saved regs, then remove the ones that are saved+restored.
-  addCalleeSavedRegs(LiveRegs, MF);
+  LivePhysRegs Pristine(*TRI);
+  addCalleeSavedRegs(Pristine, MF);
   /// Remove the ones that are not saved/restored; they are pristine.
   for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
-    LiveRegs.removeReg(Info.getReg());
+    Pristine.removeReg(Info.getReg());
+  for (MCPhysReg R : Pristine)
+    addReg(R);
 }
 
 void LivePhysRegs::addLiveOutsNoPristines(const MachineBasicBlock &MBB) {
@@ -201,7 +216,7 @@
 void LivePhysRegs::addLiveOuts(const MachineBasicBlock &MBB) {
   const MachineFunction &MF = *MBB.getParent();
   if (!MBB.succ_empty()) {
-    addPristines(*this, MF);
+    addPristines(MF);
     addLiveOutsNoPristines(MBB);
   } else if (MBB.isReturnBlock()) {
     // For the return block: Add all callee saved registers.
@@ -213,7 +228,7 @@
 
 void LivePhysRegs::addLiveIns(const MachineBasicBlock &MBB) {
   const MachineFunction &MF = *MBB.getParent();
-  addPristines(*this, MF);
+  addPristines(MF);
   addBlockLiveIns(MBB);
 }
 
Index: lib/CodeGen/LiveRegUnits.cpp
===================================================================
--- lib/CodeGen/LiveRegUnits.cpp
+++ lib/CodeGen/LiveRegUnits.cpp
@@ -97,23 +97,37 @@
     LiveUnits.addReg(*CSR);
 }
 
-/// Adds pristine registers to the given \p LiveUnits. Pristine registers are
-/// callee saved registers that are unused in the function.
-static void addPristines(LiveRegUnits &LiveUnits, const MachineFunction &MF) {
+void LiveRegUnits::addPristines(const MachineFunction &MF) {
   const MachineFrameInfo &MFI = MF.getFrameInfo();
   if (!MFI.isCalleeSavedInfoValid())
     return;
+  /// This function will usually be called on an empty object, handle this
+  /// as a special case.
+  if (empty()) {
+    /// Add all callee saved regs, then remove the ones that are saved and
+    /// restored.
+    addCalleeSavedRegs(*this, MF);
+    /// Remove the ones that are not saved/restored; they are pristine.
+    for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
+      removeReg(Info.getReg());
+    return;
+  }
+  /// If a callee-saved register that is not pristine is already present
+  /// in the set, we should make sure that it stays in it. Precompute the
+  /// set of pristine registers in a separate object.
   /// Add all callee saved regs, then remove the ones that are saved+restored.
-  addCalleeSavedRegs(LiveUnits, MF);
+  LiveRegUnits Pristine(*TRI);
+  addCalleeSavedRegs(Pristine, MF);
   /// Remove the ones that are not saved/restored; they are pristine.
   for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
-    LiveUnits.removeReg(Info.getReg());
+    Pristine.removeReg(Info.getReg());
+  addUnits(Pristine.getBitVector());
 }
 
 void LiveRegUnits::addLiveOuts(const MachineBasicBlock &MBB) {
   const MachineFunction &MF = *MBB.getParent();
   if (!MBB.succ_empty()) {
-    addPristines(*this, MF);
+    addPristines(MF);
     // To get the live-outs we simply merge the live-ins of all successors.
     for (const MachineBasicBlock *Succ : MBB.successors())
       addBlockLiveIns(*this, *Succ);
@@ -127,6 +141,6 @@
 
 void LiveRegUnits::addLiveIns(const MachineBasicBlock &MBB) {
   const MachineFunction &MF = *MBB.getParent();
-  addPristines(*this, MF);
+  addPristines(MF);
   addBlockLiveIns(*this, MBB);
 }
Index: test/CodeGen/Hexagon/livephysregs-add-pristines.mir
===================================================================
--- /dev/null
+++ test/CodeGen/Hexagon/livephysregs-add-pristines.mir
@@ -0,0 +1,37 @@
+# RUN: llc -march=hexagon -run-pass if-converter -o - %s -verify-machineinstrs | FileCheck %s
+
+# The register r23 is live on the path bb.0->bb.2->bb.3. Make sure we add
+# an implicit use of r23 to the predicated redefinition:
+# CHECK: %r23 = A2_tfrt %p0, killed %r1, implicit %r23
+
+# LivePhysRegs::addPristines could accidentally remove a callee-saved
+# register, if it determined that it wasn't pristine. Doing that caused
+# r23 in this testcase to be dropped from the Redefs set, and subsequently
+# the necessary implicit use was not added for it.
+
+---
+name: foo
+tracksRegLiveness: true
+fixedStack:
+  - { id: 0, offset: 0, size: 4, alignment: 4, callee-saved-register: '%r23' }
+body: |
+  bb.0:
+    successors: %bb.1, %bb.2
+    liveins: %r0, %r1, %r23
+      %p0 = C2_cmpgti killed %r0, 0
+      J2_jumpf killed %p0, %bb.2, implicit-def %pc
+
+  bb.1:
+    successors: %bb.3
+    liveins: %r1
+      %r23 = A2_tfr killed %r1
+      J2_jump %bb.3, implicit-def %pc
+
+  bb.2:
+    successors: %bb.3
+    liveins: %r1, %r23
+      %r0 = A2_tfr %r1
+
+  bb.3:
+    liveins: %r23
+...