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,21 @@
   const TargetInstrInfo *TII;
 
   // Data structures to map regs to their definitions per MBB.
-  using Reg2DefMap = std::map<Register, MachineInstr*>;
-  std::vector<Reg2DefMap> RegDefs;
+  using Reg2MIMap = std::map<Register, MachineInstr *>;
+  std::vector<Reg2MIMap> RegDefs;
+
+  // Map regs to kills per MBB.
+  std::vector<Reg2MIMap> RegKills;
 
   // 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
 
@@ -88,6 +96,8 @@
 
   RegDefs.clear();
   RegDefs.resize(MF.getNumBlockIDs());
+  RegKills.clear();
+  RegKills.resize(MF.getNumBlockIDs());
 
   // Visit all MBBs in an order that maximises the reuse from predecessors.
   bool Changed = false;
@@ -102,27 +112,26 @@
 // 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)
-      return;
+
+  // Kill flag in MBB
+  auto KillI = RegKills[MBB->getNumber()].find(Reg);
+  if (KillI != RegKills[MBB->getNumber()].end()) {
+    KillI->second->clearRegisterKills(Reg, TRI);
+    return;
   }
 
+  // Def in MBB (missing kill flag)
+  auto DefI = RegDefs[MBB->getNumber()].find(Reg);
+  if (DefI != RegDefs[MBB->getNumber()].end() &&
+      DefI->second->getParent() == MBB)
+    return;
+
   // If an earlier def is not in MBB, continue in predecessors.
   if (!MBB->isLiveIn(Reg))
     MBB->addLiveIn(Reg);
@@ -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,7 +181,8 @@
 
 bool MachineLateInstrsCleanup::processBlock(MachineBasicBlock *MBB) {
   bool Changed = false;
-  Reg2DefMap &MBBDefs = RegDefs[MBB->getNumber()];
+  Reg2MIMap &MBBDefs = RegDefs[MBB->getNumber()];
+  Reg2MIMap &MBBKills = RegKills[MBB->getNumber()];
 
   // Find reusable definitions in the predecessor(s).
   if (!MBB->pred_empty() && !MBB->isEHPad()) {
@@ -221,10 +231,14 @@
     // 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))
+      if (MI.modifiesRegister(Reg, TRI)) {
         DefI = MBBDefs.erase(DefI);
-      else
-        ++DefI;
+        MBBKills.erase(Reg);
+        continue;
+      }
+      if (MI.findRegisterUseOperandIdx(Reg, false /*isKill*/, TRI) != -1)
+        MBBKills[Reg] = &MI;
+      ++DefI;
     }
 
     // Record this MI for potential later reuse.
@@ -232,6 +246,7 @@
       LLVM_DEBUG(dbgs() << "Found interesting instruction in "
                         << printMBBReference(*MBB) << ":  " << MI;);
       MBBDefs[DefedReg] = &MI;
+      MBBKills.erase(DefedReg);
     }
   }