diff --git a/llvm/lib/CodeGen/MachineLateInstrsCleanup.cpp b/llvm/lib/CodeGen/MachineLateInstrsCleanup.cpp
--- a/llvm/lib/CodeGen/MachineLateInstrsCleanup.cpp
+++ b/llvm/lib/CodeGen/MachineLateInstrsCleanup.cpp
@@ -43,13 +43,22 @@
   const TargetInstrInfo *TII;
 
   // Data structures to map regs to their definitions per MBB.
-  using Reg2DefMap = std::map<Register, MachineInstr*>;
-  std::vector<Reg2DefMap> RegDefs;
+  struct RegInfo {
+    MachineInstr *DefMI = nullptr;
+    MachineInstr *KillMI = nullptr;
+  };
+  using Reg2MIMap = SmallDenseMap<Register, RegInfo>;
+  std::vector<Reg2MIMap> BBRegInfo;
 
   // Walk through the instructions in MBB and remove any redundant
   // instructions.
   bool processBlock(MachineBasicBlock *MBB);
 
+  void removeRedundantDef(MachineInstr *MI, const TargetRegisterInfo *TRI);
+  void clearKillsForDef(Register Reg, MachineBasicBlock *MBB,
+                        MachineBasicBlock::iterator I, BitVector &VisitedPreds,
+                        const TargetRegisterInfo *TRI);
+
 public:
   static char ID; // Pass identification, replacement for typeid
 
@@ -86,8 +95,9 @@
   TRI = MF.getSubtarget().getRegisterInfo();
   TII = MF.getSubtarget().getInstrInfo();
 
-  RegDefs.clear();
-  RegDefs.resize(MF.getNumBlockIDs());
+  for (auto &RI : BBRegInfo)
+    RI.clear();
+  BBRegInfo.resize(MF.getNumBlockIDs());
 
   // Visit all MBBs in an order that maximises the reuse from predecessors.
   bool Changed = false;
@@ -102,24 +112,23 @@
 // in MBB and if needed continue in predecessors until a use/def of Reg is
 // encountered. This seems to be faster in practice than tracking kill flags
 // in a map.
-static void clearKillsForDef(Register Reg, MachineBasicBlock *MBB,
-                             MachineBasicBlock::iterator I,
-                             BitVector &VisitedPreds,
-                             const TargetRegisterInfo *TRI) {
+void MachineLateInstrsCleanup::clearKillsForDef(Register Reg,
+                                                MachineBasicBlock *MBB,
+                                                MachineBasicBlock::iterator I,
+                                                BitVector &VisitedPreds,
+                                                const TargetRegisterInfo *TRI) {
   VisitedPreds.set(MBB->getNumber());
-  while (I != MBB->begin()) {
-    --I;
-    bool Found = false;
-    for (auto &MO : I->operands())
-      if (MO.isReg() && TRI->regsOverlap(MO.getReg(), Reg)) {
-        if (MO.isDef())
-          return;
-        if (MO.readsReg()) {
-          MO.setIsKill(false);
-          Found = true; // Keep going for an implicit kill of the super-reg.
-        }
-      }
-    if (Found)
+
+  auto &Map = BBRegInfo[MBB->getNumber()];
+  auto RI = Map.find(Reg);
+  if (RI != Map.end()) {
+    if (RI->second.KillMI) {
+      // Kill flag in MBB
+      RI->second.KillMI->clearRegisterKills(Reg, TRI);
+      return;
+    }
+    // Def in MBB (missing kill flag)
+    if (RI->second.DefMI->getParent() == MBB)
       return;
   }
 
@@ -132,8 +141,8 @@
       clearKillsForDef(Reg, Pred, Pred->end(), VisitedPreds, TRI);
 }
 
-static void removeRedundantDef(MachineInstr *MI,
-                               const TargetRegisterInfo *TRI) {
+void MachineLateInstrsCleanup::removeRedundantDef(
+    MachineInstr *MI, const TargetRegisterInfo *TRI) {
   Register Reg = MI->getOperand(0).getReg();
   BitVector VisitedPreds(MI->getMF()->getNumBlockIDs());
   clearKillsForDef(Reg, MI->getParent(), MI->getIterator(), VisitedPreds, TRI);
@@ -172,23 +181,28 @@
 
 bool MachineLateInstrsCleanup::processBlock(MachineBasicBlock *MBB) {
   bool Changed = false;
-  Reg2DefMap &MBBDefs = RegDefs[MBB->getNumber()];
+  auto &MBBRegInfo = BBRegInfo[MBB->getNumber()];
 
   // Find reusable definitions in the predecessor(s).
   if (!MBB->pred_empty() && !MBB->isEHPad()) {
     MachineBasicBlock *FirstPred = *MBB->pred_begin();
-    for (auto [Reg, DefMI] : RegDefs[FirstPred->getNumber()])
-      if (llvm::all_of(
-              drop_begin(MBB->predecessors()),
-              [&, &Reg = Reg, &DefMI = DefMI](const MachineBasicBlock *Pred) {
-                auto PredDefI = RegDefs[Pred->getNumber()].find(Reg);
-                return PredDefI != RegDefs[Pred->getNumber()].end() &&
-                       DefMI->isIdenticalTo(*PredDefI->second);
-              })) {
-        MBBDefs[Reg] = DefMI;
+    for (auto &[Reg, RI] : BBRegInfo[FirstPred->getNumber()]) {
+      if (!RI.DefMI)
+        continue;
+      if (llvm::all_of(drop_begin(MBB->predecessors()),
+                       [&, &Reg = Reg,
+                        &DefMI = RI.DefMI](const MachineBasicBlock *Pred) {
+                         auto &PredMap = BBRegInfo[Pred->getNumber()];
+                         auto PredDefI = PredMap.find(Reg);
+                         return PredDefI != PredMap.end() &&
+                                PredDefI->second.DefMI &&
+                                DefMI->isIdenticalTo(*PredDefI->second.DefMI);
+                       })) {
+        MBBRegInfo[Reg].DefMI = RI.DefMI;
         LLVM_DEBUG(dbgs() << "Reusable instruction from pred(s): in "
-                          << printMBBReference(*MBB) << ":  " << *DefMI;);
+                          << printMBBReference(*MBB) << ":  " << *RI.DefMI;);
       }
+    }
   }
 
   // Process MBB.
@@ -199,7 +213,13 @@
     // If FrameReg is modified, no previous load-address instructions (using
     // it) are valid.
     if (MI.modifiesRegister(FrameReg, TRI)) {
-      MBBDefs.clear();
+      for (auto I = MBBRegInfo.begin(); I != MBBRegInfo.end();) {
+        auto ThisI = I++;
+        if (!ThisI->second.KillMI)
+          MBBRegInfo.erase(ThisI);
+        else
+          ThisI->second.DefMI = nullptr;
+      }
       continue;
     }
 
@@ -208,8 +228,9 @@
 
     // Check for an earlier identical and reusable instruction.
     if (IsCandidate) {
-      auto DefI = MBBDefs.find(DefedReg);
-      if (DefI != MBBDefs.end() && MI.isIdenticalTo(*DefI->second)) {
+      auto I = MBBRegInfo.find(DefedReg);
+      if (I != MBBRegInfo.end() && I->second.DefMI &&
+          MI.isIdenticalTo(*I->second.DefMI)) {
         LLVM_DEBUG(dbgs() << "Removing redundant instruction in "
                           << printMBBReference(*MBB) << ":  " << MI;);
         removeRedundantDef(&MI, TRI);
@@ -219,19 +240,24 @@
     }
 
     // Clear any entries in map that MI clobbers.
-    for (auto DefI = MBBDefs.begin(); DefI != MBBDefs.end();) {
-      Register Reg = DefI->first;
-      if (MI.modifiesRegister(Reg, TRI))
-        DefI = MBBDefs.erase(DefI);
-      else
-        ++DefI;
+    for (auto I = MBBRegInfo.begin(); I != MBBRegInfo.end();) {
+      auto ThisI = I++;
+      if (!ThisI->second.DefMI)
+        continue;
+      Register Reg = ThisI->first;
+      if (MI.modifiesRegister(Reg, TRI)) {
+        MBBRegInfo.erase(ThisI);
+        continue;
+      }
+      if (MI.findRegisterUseOperandIdx(Reg, false /*isKill*/, TRI) != -1)
+        ThisI->second.KillMI = &MI;
     }
 
     // Record this MI for potential later reuse.
     if (IsCandidate) {
       LLVM_DEBUG(dbgs() << "Found interesting instruction in "
                         << printMBBReference(*MBB) << ":  " << MI;);
-      MBBDefs[DefedReg] = &MI;
+      MBBRegInfo[DefedReg].DefMI = &MI;
     }
   }