[RDA][ARM] Move functionality into RDA

[samparker]

Summary

Add several helpers to RDA:

• hasLocalDefBefore
• isRegDefinedAfter
• isSafeToDefRegAt

And move two bits of logic from ARMLowOverheadLoops into RDA:

• isSafeToMove
• isSafeToRemove

Both of these have some wrappers too to make them more convenient to use. This is an NFC for LowOverheadLoops.

[samparker]

Rebased.

[SjoerdMeijer]

Looks like a good and useful reshuffle to me

llvm/include/llvm/CodeGen/ReachingDefAnalysis.h

120

nit: missing comment/description

188

nit: if this is only a helper for isSafeToMoveForwards/Backwards, should this be a private function?

llvm/lib/CodeGen/ReachingDefAnalysis.cpp

376

nit: From's?

[samparker]

llvm/include/llvm/CodeGen/ReachingDefAnalysis.h

120

I'll add it before committing.

188

It is!

llvm/include/llvm/CodeGen/ReachingDefAnalysis.h

public:
   /// block.
   bool isReachingDefLiveOut(MachineInstr *MI, int PhysReg) const;
 
   /// Return the local MI that produces the live out value for PhysReg, or
   /// nullptr for a non-live out or non-local def.
   MachineInstr *getLocalLiveOutMIDef(MachineBasicBlock *MBB,
                                      int PhysReg) const;
 
+  bool hasLocalDefBefore(MachineInstr *MI, int PhysReg) const;
+
   /// Return whether the given register is used after MI, whether it's a local
   /// use or a live out.
   bool isRegUsedAfter(MachineInstr *MI, int PhysReg) const;
 
+  /// Return whether the given register is defined after MI.
+  bool isRegDefinedAfter(MachineInstr *MI, int PhysReg) const;
+
   /// Provides the clearance - the number of instructions since the closest
   /// reaching def instuction of PhysReg that reaches MI.
   int getClearance(MachineInstr *MI, MCPhysReg PhysReg) const;
 
   /// Provides the uses, in the same block as MI, of register that MI defines.
   /// This does not consider live-outs.
   void getReachingLocalUses(MachineInstr *MI, int PhysReg,
                             InstSet &Uses) const;
 
   /// For the given block, collect the instructions that use the live-in
   /// value of the provided register. Return whether the value is still
   /// live on exit.
   bool getLiveInUses(MachineBasicBlock *MBB, int PhysReg,
                      InstSet &Uses) const;
 
   /// Collect the users of the value stored in PhysReg, which is defined
   /// by MI.
   void getGlobalUses(MachineInstr *MI, int PhysReg,
                      InstSet &Uses) const;
 
+  /// Return whether From can be moved forwards to just before To.
+  bool isSafeToMoveForwards(MachineInstr *From, MachineInstr *To) const;
+
+  /// Return whether From can be moved backwards to just after To.
+  bool isSafeToMoveBackwards(MachineInstr *From, MachineInstr *To) const;
+
+  /// Return whether removing this instruction will have no effect on the
+  /// program, returning the redundant use-def chain.
+  bool isSafeToRemove(MachineInstr *MI, InstSet &ToRemove) const;
+
+  /// Return whether removing this instruction will have no effect on the
+  /// program, ignoring the possible effects on some instructions, returning
+  /// the redundant use-def chain.
+  bool isSafeToRemove(MachineInstr *MI, InstSet &ToRemove,
+                      InstSet &Ignore) const;
+
+  /// Return whether a MachineInstr could be inserted at MI and safely define
+  /// the given register without affecting the program.
+  bool isSafeToDefRegAt(MachineInstr *MI, int PhysReg) const;
+
+  /// Return whether a MachineInstr could be inserted at MI and safely define
+  /// the given register without affecting the program, ignoring any effects
+  /// on the provided instructions.
+  bool isSafeToDefRegAt(MachineInstr *MI, int PhysReg, InstSet &Ignore) const;
+
 private:
   /// Set up LiveRegs by merging predecessor live-out values.
   void enterBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
 
   /// Update live-out values.
   void leaveBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
 
   /// Process he given basic block.
   void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
 
   /// Update def-ages for registers defined by MI.
   /// Also break dependencies on partial defs and undef uses.
   void processDefs(MachineInstr *);
+
+  /// Utility function for isSafeToMoveForwards/Backwards.
+  template<typename Iterator>
+  bool isSafeToMove(MachineInstr *From, MachineInstr *To) const;
+
+  /// Return whether removing this instruction will have no effect on the
+  /// program, ignoring the possible effects on some instructions, returning
+  /// the redundant use-def chain.
+  bool isSafeToRemove(MachineInstr *MI, InstSet &Visited,
+                      InstSet &ToRemove, InstSet &Ignore) const;
 };
 
 } // namespace llvm
 
 #endif // LLVM_CODEGEN_REACHINGDEFSANALYSIS_H

llvm/lib/CodeGen/ReachingDefAnalysis.cpp

 //===---- ReachingDefAnalysis.cpp - Reaching Def Analysis ---*- C++ -*-----===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/CodeGen/LivePhysRegs.h"
 #include "llvm/CodeGen/ReachingDefAnalysis.h"
 #include "llvm/CodeGen/TargetRegisterInfo.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/Support/Debug.h"
 
 using namespace llvm;
 

 }
 
 int
 ReachingDefAnalysis::getClearance(MachineInstr *MI, MCPhysReg PhysReg) const {
   assert(InstIds.count(MI) && "Unexpected machine instuction.");
   return InstIds.lookup(MI) - getReachingDef(MI, PhysReg);
 }
 
+bool
+ReachingDefAnalysis::hasLocalDefBefore(MachineInstr *MI, int PhysReg) const {
+  return getReachingDef(MI, PhysReg) >= 0;
+}
+
 void ReachingDefAnalysis::getReachingLocalUses(MachineInstr *Def, int PhysReg,
                                                InstSet &Uses) const {
   MachineBasicBlock *MBB = Def->getParent();
   MachineBasicBlock::iterator MI = MachineBasicBlock::iterator(Def);
   while (++MI != MBB->end()) {
     if (MI->isDebugInstr())
       continue;
 
bool ReachingDefAnalysis::isRegUsedAfter(MachineInstr *MI, int PhysReg) const {
   for (auto Last = MBB->rbegin(), End = MBB->rend(); Last != End; ++Last) {
     LiveRegs.stepBackward(*Last);
     if (LiveRegs.contains(PhysReg))
       return InstIds.lookup(&*Last) > InstIds.lookup(MI);
   }
   return false;
 }
 
+bool ReachingDefAnalysis::isRegDefinedAfter(MachineInstr *MI,
+                                            int PhysReg) const {
+  MachineBasicBlock *MBB = MI->getParent();
+  if (getReachingDef(MI, PhysReg) != getReachingDef(&MBB->back(), PhysReg))
+    return true;
+
+  if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg))
+    return Def == getReachingMIDef(MI, PhysReg);
+
+  return false;
+}
+
 bool
 ReachingDefAnalysis::isReachingDefLiveOut(MachineInstr *MI, int PhysReg) const {
   MachineBasicBlock *MBB = MI->getParent();
   LivePhysRegs LiveRegs(*TRI);
   LiveRegs.addLiveOuts(*MBB);
   if (!LiveRegs.contains(PhysReg))
     return false;
 
MachineInstr* ReachingDefAnalysis::getLocalLiveOutMIDef(MachineBasicBlock *MBB,
   MachineInstr *Last = &MBB->back();
   int Def = getReachingDef(Last, PhysReg);
   for (auto &MO : Last->operands())
     if (MO.isReg() && MO.isDef() && MO.getReg() == PhysReg)
       return Last;
 
   return Def < 0 ? nullptr : getInstFromId(MBB, Def);
 }
+
+// Can we safely move 'From' to just before 'To'? To satisfy this, 'From' must
+// not define a register that is used by any instructions, after and including,
+// 'To'. These instructions also must not redefine any of Froms operands.
+template<typename Iterator>
+bool ReachingDefAnalysis::isSafeToMove(MachineInstr *From,
+                                       MachineInstr *To) const {
+  if (From->getParent() != To->getParent())
+    return false;
+
+  SmallSet<int, 2> Defs;
+  // First check that From would compute the same value if moved.
+  for (auto &MO : From->operands()) {
+    if (!MO.isReg() || MO.isUndef() || !MO.getReg())
+      continue;
+    if (MO.isDef())
+      Defs.insert(MO.getReg());
+    else if (!hasSameReachingDef(From, To, MO.getReg()))
+      return false;
+  }
+
+  // Now walk checking that the rest of the instructions will compute the same
+  // value.
+  for (auto I = ++Iterator(From), E = Iterator(To); I != E; ++I) {
+    for (auto &MO : I->operands())
+      if (MO.isReg() && MO.getReg() && MO.isUse() && Defs.count(MO.getReg()))
+        return false;
+  }
+  return true;
+}
+
+bool ReachingDefAnalysis::isSafeToMoveForwards(MachineInstr *From,
+                                               MachineInstr *To) const {
+  return isSafeToMove<MachineBasicBlock::reverse_iterator>(From, To);
+}
+
+bool ReachingDefAnalysis::isSafeToMoveBackwards(MachineInstr *From,
+                                                MachineInstr *To) const {
+  return isSafeToMove<MachineBasicBlock::iterator>(From, To);
+}
+
+bool ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI,
+                                         InstSet &ToRemove) const {
+  SmallPtrSet<MachineInstr*, 1> Ignore;
+  SmallPtrSet<MachineInstr*, 2> Visited;
+  return isSafeToRemove(MI, Visited, ToRemove, Ignore);
+}
+
+bool
+ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI, InstSet &ToRemove,
+                                    InstSet &Ignore) const {
+  SmallPtrSet<MachineInstr*, 2> Visited;
+  return isSafeToRemove(MI, Visited, ToRemove, Ignore);
+}
+
+bool
+ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI, InstSet &Visited,
+                                    InstSet &ToRemove, InstSet &Ignore) const {
+  if (Visited.count(MI) || Ignore.count(MI))
+    return true;
+  else if (MI->mayLoadOrStore() || MI->hasUnmodeledSideEffects() ||
+           MI->isBranch() || MI->isTerminator() || MI->isReturn()) {
+    // Unless told to ignore the instruction, don't remove anything which has
+    // side effects.
+    return false;
+  }
+
+  Visited.insert(MI);
+  for (auto &MO : MI->operands()) {
+    if (!MO.isReg() || MO.isUse() || MO.getReg() == 0)
+      continue;
+
+    SmallPtrSet<MachineInstr*, 4> Uses;
+    getGlobalUses(MI, MO.getReg(), Uses);
+
+    for (auto I : Uses) {
+      if (Ignore.count(I) || ToRemove.count(I))
+        continue;
+      if (!isSafeToRemove(I, Visited, ToRemove, Ignore))
+        return false;
+    }
+  }
+  ToRemove.insert(MI);
+  return true;
+}
+
+bool ReachingDefAnalysis::isSafeToDefRegAt(MachineInstr *MI,
+                                           int PhysReg) const {
+  SmallPtrSet<MachineInstr*, 1> Ignore;
+  return isSafeToDefRegAt(MI, PhysReg, Ignore);
+}
+
+bool ReachingDefAnalysis::isSafeToDefRegAt(MachineInstr *MI, int PhysReg,
+                                           InstSet &Ignore) const {
+  // Check for any uses of the register after MI.
+  if (isRegUsedAfter(MI, PhysReg)) {
+    if (auto *Def = getReachingMIDef(MI, PhysReg)) {
+      SmallPtrSet<MachineInstr*, 2> Uses;
+      getReachingLocalUses(Def, PhysReg, Uses);
+      for (auto *Use : Uses)
+        if (!Ignore.count(Use))
+          return false;
+    } else
+      return false;
+  }
+
+  MachineBasicBlock *MBB = MI->getParent();
+  // Check for any defs after MI.
+  if (isRegDefinedAfter(MI, PhysReg)) {
+    auto I = MachineBasicBlock::iterator(MI);
+    for (auto E = MBB->end(); I != E; ++I) {
+      if (Ignore.count(&*I))
+        continue;
+      for (auto &MO : I->operands())
+        if (MO.isReg() && MO.isDef() && MO.getReg() == PhysReg)
+          return false;
+    }
+  }
+  return true;
+}

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

bool IsTailPredicationLegal() const {
              !CannotTailPredicate && ML->getNumBlocks() == 1;
     }
 
     bool ValidateTailPredicate(MachineInstr *StartInsertPt);
 
     // Is it safe to define LR with DLS/WLS?
     // LR can be defined if it is the operand to start, because it's the same
     // value, or if it's going to be equivalent to the operand to Start.
-    MachineInstr *IsSafeToDefineLR();
+    MachineInstr *isSafeToDefineLR();
 
     // Check the branch targets are within range and we satisfy our
     // restrictions.
     void CheckLegality(ARMBasicBlockUtils *BBUtils);
 
     bool FoundAllComponents() const {
       return Start && Dec && End;
     }
namespace {
 
   private:
     bool ProcessLoop(MachineLoop *ML);
 
     bool RevertNonLoops();
 
     void RevertWhile(MachineInstr *MI) const;
 
-    bool RevertLoopDec(MachineInstr *MI, bool AllowFlags = false) const;
+    bool RevertLoopDec(MachineInstr *MI) const;
 
     void RevertLoopEnd(MachineInstr *MI, bool SkipCmp = false) const;
 
     void ConvertVPTBlocks(LowOverheadLoop &LoLoop);
 
     MachineInstr *ExpandLoopStart(LowOverheadLoop &LoLoop);
 
     void Expand(LowOverheadLoop &LoLoop);
 
   };
 }
 
 char ARMLowOverheadLoops::ID = 0;
 
 INITIALIZE_PASS(ARMLowOverheadLoops, DEBUG_TYPE, ARM_LOW_OVERHEAD_LOOPS_NAME,
                 false, false)
 
-MachineInstr *LowOverheadLoop::IsSafeToDefineLR() {
+MachineInstr *LowOverheadLoop::isSafeToDefineLR() {
   // We can define LR because LR already contains the same value.
   if (Start->getOperand(0).getReg() == ARM::LR)
     return Start;
 
   unsigned CountReg = Start->getOperand(0).getReg();
   auto IsMoveLR = [&CountReg](MachineInstr *MI) {
     return MI->getOpcode() == ARM::tMOVr &&
            MI->getOperand(0).getReg() == ARM::LR &&
MachineInstr *LowOverheadLoop::isSafeToDefineLR() {
   // - Is there a (mov lr, Count) after Start? If so, and nothing else writes
   //   to Count after Start, we can insert at that mov.
   if (auto *LRDef = RDA->getLocalLiveOutMIDef(MBB, ARM::LR))
     if (IsMoveLR(LRDef) && RDA->hasSameReachingDef(Start, LRDef, CountReg))
       return LRDef;
 
   // We've found no suitable LR def and Start doesn't use LR directly. Can we
   // just define LR anyway?
-  if (!RDA->isRegUsedAfter(Start, ARM::LR))
-    return Start;
-
-  return nullptr;
-}
-
-// Can we safely move 'From' to just before 'To'? To satisfy this, 'From' must
-// not define a register that is used by any instructions, after and including,
-// 'To'. These instructions also must not redefine any of Froms operands.
-template<typename Iterator>
-static bool IsSafeToMove(MachineInstr *From, MachineInstr *To, ReachingDefAnalysis *RDA) {
-  SmallSet<int, 2> Defs;
-  // First check that From would compute the same value if moved.
-  for (auto &MO : From->operands()) {
-    if (!MO.isReg() || MO.isUndef() || !MO.getReg())
-      continue;
-    if (MO.isDef())
-      Defs.insert(MO.getReg());
-    else if (!RDA->hasSameReachingDef(From, To, MO.getReg()))
-      return false;
-  }
-
-  // Now walk checking that the rest of the instructions will compute the same
-  // value.
-  for (auto I = ++Iterator(From), E = Iterator(To); I != E; ++I) {
-    for (auto &MO : I->operands())
-      if (MO.isReg() && MO.getReg() && MO.isUse() && Defs.count(MO.getReg()))
-        return false;
-  }
-  return true;
-}
-
-static bool IsSafeToRemove(MachineInstr *MI, ReachingDefAnalysis *RDA,
-                           SmallPtrSetImpl<MachineInstr*> &Visited,
-                           SmallPtrSetImpl<MachineInstr*> &ToRemove,
-                           SmallPtrSetImpl<MachineInstr*> &Ignore) {
-  if (Visited.count(MI) || Ignore.count(MI))
-    return true;
-  else if (MI->mayLoadOrStore() || MI->hasUnmodeledSideEffects() ||
-           MI->isBranch() || MI->isTerminator() || MI->isReturn()) {
-    // Unless told to ignore the instruction, don't remove anything which has
-    // side effects.
-    LLVM_DEBUG(dbgs() << "ARM Loops: Has side effects: " << *MI);
-    return false;
-  }
-
-  Visited.insert(MI);
-  for (auto &MO : MI->operands()) {
-    if (!MO.isReg() || MO.isUse() || MO.getReg() == 0)
-      continue;
-
-    SmallPtrSet<MachineInstr*, 4> Uses;
-    RDA->getGlobalUses(MI, MO.getReg(), Uses);
-
-    for (auto I : Uses) {
-      if (Ignore.count(I) || ToRemove.count(I))
-        continue;
-      if (!IsSafeToRemove(I, RDA, Visited, ToRemove, Ignore)) {
-        LLVM_DEBUG(dbgs() << "ARM Loops: Unable to remove " << *I);
-        return false;
-      }
-    }
-  }
-  ToRemove.insert(MI);
-  LLVM_DEBUG(dbgs() << "ARM Loops: Can remove: " << *MI);
-  return true;
+  return RDA->isSafeToDefRegAt(Start, ARM::LR) ? Start : nullptr;
 }
 
 bool LowOverheadLoop::ValidateTailPredicate(MachineInstr *StartInsertPt) {
   assert(VCTP && "VCTP instruction expected but is not set");
   // All predication within the loop should be based on vctp. If the block
   // isn't predicated on entry, check whether the vctp is within the block
   // and that all other instructions are then predicated on it.
   for (auto &Block : VPTBlocks) {
bool LowOverheadLoop::ValidateTailPredicate(MachineInstr *StartInsertPt) {
   // of the iteration count, to the loop start instruction. The number of
   // elements is provided to the vctp instruction, so we need to check that
   // we can use this register at InsertPt.
   Register NumElements = VCTP->getOperand(1).getReg();
 
   // If the register is defined within loop, then we can't perform TP.
   // TODO: Check whether this is just a mov of a register that would be
   // available.
-  if (RDA->getReachingDef(VCTP, NumElements) >= 0) {
+  if (RDA->hasLocalDefBefore(VCTP, NumElements)) {
     LLVM_DEBUG(dbgs() << "ARM Loops: VCTP operand is defined in the loop.\n");
     return false;
   }
 
   // The element count register maybe defined after InsertPt, in which case we
   // need to try to move either InsertPt or the def so that the [w|d]lstp can
   // use the value.
   MachineBasicBlock *InsertBB = StartInsertPt->getParent();
   if (!RDA->isReachingDefLiveOut(StartInsertPt, NumElements)) {
     if (auto *ElemDef = RDA->getLocalLiveOutMIDef(InsertBB, NumElements)) {
-      if (IsSafeToMove<MachineBasicBlock::reverse_iterator>(
-          ElemDef, StartInsertPt, RDA)) {
+      if (RDA->isSafeToMoveForwards(ElemDef, StartInsertPt)) {
         ElemDef->removeFromParent();
         InsertBB->insert(MachineBasicBlock::iterator(StartInsertPt), ElemDef);
         LLVM_DEBUG(dbgs() << "ARM Loops: Moved element count def: "
                    << *ElemDef);
-      } else if (IsSafeToMove<MachineBasicBlock::iterator>(
-          StartInsertPt, ElemDef, RDA)) {
+      } else if (RDA->isSafeToMoveBackwards(StartInsertPt, ElemDef)) {
         StartInsertPt->removeFromParent();
         InsertBB->insertAfter(MachineBasicBlock::iterator(ElemDef),
                               StartInsertPt);
         LLVM_DEBUG(dbgs() << "ARM Loops: Moved start past: " << *ElemDef);
       } else {
         LLVM_DEBUG(dbgs() << "ARM Loops: Unable to move element count to loop "
                    << "start instruction.\n");
         return false;
       }
     }
   }
 
   // Especially in the case of while loops, InsertBB may not be the
   // preheader, so we need to check that the register isn't redefined
   // before entering the loop.
   auto CannotProvideElements = [this](MachineBasicBlock *MBB,
                                       Register NumElements) {
     // NumElements is redefined in this block.
-    if (RDA->getReachingDef(&MBB->back(), NumElements) >= 0)
+    if (RDA->hasLocalDefBefore(&MBB->back(), NumElements))
       return true;
 
     // Don't continue searching up through multiple predecessors.
     if (MBB->pred_size() > 1)
       return true;
 
     return false;
   };
case ARM::t2SUBri12:
       ImmOpIdx = 2;
       break;
     }
     return MI->getOperand(ImmOpIdx).getImm() == ExpectedVecWidth;
   };
 
   MBB = VCTP->getParent();
   if (MachineInstr *Def = RDA->getReachingMIDef(&MBB->back(), NumElements)) {
-    SmallPtrSet<MachineInstr*, 2> Visited;
     SmallPtrSet<MachineInstr*, 2> ElementChain;
     SmallPtrSet<MachineInstr*, 2> Ignore = { VCTP };
     unsigned ExpectedVectorWidth = getTailPredVectorWidth(VCTP->getOpcode());
 
-    if (IsSafeToRemove(Def, RDA, Visited, ElementChain, Ignore)) {
+    if (RDA->isSafeToRemove(Def, ElementChain, Ignore)) {
       bool FoundSub = false;
 
       for (auto *MI : ElementChain) {
         if (isMovRegOpcode(MI->getOpcode()))
           continue;
 
         if (isSubImmOpcode(MI->getOpcode())) {
           if (FoundSub || !IsValidSub(MI, ExpectedVectorWidth))
if (Start->getOpcode() == ARM::t2WhileLoopStart &&
       (BBUtils->getOffsetOf(Start) >
        BBUtils->getOffsetOf(Start->getOperand(1).getMBB()) ||
        !BBUtils->isBBInRange(Start, Start->getOperand(1).getMBB(), 4094))) {
     LLVM_DEBUG(dbgs() << "ARM Loops: WLS offset is out-of-range!\n");
     Revert = true;
     return;
   }
 
-  InsertPt = Revert ? nullptr : IsSafeToDefineLR();
+  InsertPt = Revert ? nullptr : isSafeToDefineLR();
   if (!InsertPt) {
     LLVM_DEBUG(dbgs() << "ARM Loops: Unable to find safe insertion point.\n");
     Revert = true;
     return;
   } else
     LLVM_DEBUG(dbgs() << "ARM Loops: Start insertion point: " << *InsertPt);
 
   if (!IsTailPredicationLegal()) {
bool ARMLowOverheadLoops::ProcessLoop(MachineLoop *ML) {
   }
 
   LLVM_DEBUG(LoLoop.dump());
   if (!LoLoop.FoundAllComponents()) {
     LLVM_DEBUG(dbgs() << "ARM Loops: Didn't find loop start, update, end\n");
     return false;
   }
 
-  SmallPtrSet<MachineInstr*, 2> Visited;
   SmallPtrSet<MachineInstr*, 2> Ignore = { LoLoop.End };
   SmallPtrSet<MachineInstr*, 4> Remove;
-  if (!IsSafeToRemove(LoLoop.Dec, RDA, Visited, Remove, Ignore)) {
+  if (!RDA->isSafeToRemove(LoLoop.Dec, Remove, Ignore)) {
     LLVM_DEBUG(dbgs() << "ARM Loops: Unable to remove loop count chain.\n");
     LoLoop.Revert = true;
   } else {
     LLVM_DEBUG(dbgs() << "ARM Loops: Will need to remove:\n";
                for (auto *I : Remove)
                  dbgs() << " - " << *I);
     LoLoop.ToRemove.insert(Remove.begin(), Remove.end());
   }
void ARMLowOverheadLoops::RevertWhile(MachineInstr *MI) const {
 
   MIB = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(BrOpc));
   MIB.add(MI->getOperand(1));   // branch target
   MIB.addImm(ARMCC::EQ);        // condition code
   MIB.addReg(ARM::CPSR);
   MI->eraseFromParent();
 }
 
-bool ARMLowOverheadLoops::RevertLoopDec(MachineInstr *MI,
-                                        bool SetFlags) const {
+bool ARMLowOverheadLoops::RevertLoopDec(MachineInstr *MI) const {
   LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to sub: " << *MI);
   MachineBasicBlock *MBB = MI->getParent();
+  MachineInstr *Last = &MBB->back();
+  SmallPtrSet<MachineInstr*, 1> Ignore;
+  if (Last->getOpcode() == ARM::t2LoopEnd)
+    Ignore.insert(Last);
 
   // If nothing defines CPSR between LoopDec and LoopEnd, use a t2SUBS.
-  if (SetFlags &&
-      (RDA->isRegUsedAfter(MI, ARM::CPSR) ||
-       !RDA->hasSameReachingDef(MI, &MBB->back(), ARM::CPSR)))
-      SetFlags = false;
+  bool SetFlags = RDA->isSafeToDefRegAt(MI, ARM::CPSR, Ignore);
 
   MachineInstrBuilder MIB = BuildMI(*MBB, MI, MI->getDebugLoc(),
                                     TII->get(ARM::t2SUBri));
   MIB.addDef(ARM::LR);
   MIB.add(MI->getOperand(1));
   MIB.add(MI->getOperand(2));
   MIB.addImm(ARMCC::AL);
   MIB.addReg(0);
MachineInstr* ARMLowOverheadLoops::ExpandLoopStart(LowOverheadLoop &LoLoop) {
   LLVM_DEBUG(dbgs() << "ARM Loops: Expanding LoopStart.\n");
   // When using tail-predication, try to delete the dead code that was used to
   // calculate the number of loop iterations.
   if (LoLoop.IsTailPredicationLegal()) {
     SmallVector<MachineInstr*, 4> Killed;
     SmallVector<MachineInstr*, 4> Dead;
     if (auto *Def = RDA->getReachingMIDef(LoLoop.Start,
                                       LoLoop.Start->getOperand(0).getReg())) {
-      SmallPtrSet<MachineInstr*, 4> Visited;
       SmallPtrSet<MachineInstr*, 4> Remove;
       SmallPtrSet<MachineInstr*, 4> Ignore = { LoLoop.Start, LoLoop.Dec,
                                                LoLoop.End, LoLoop.InsertPt };
       SmallVector<MachineInstr*, 4> Chain = { Def };
       while (!Chain.empty()) {
         MachineInstr *MI = Chain.back();
         Chain.pop_back();
-        if (IsSafeToRemove(MI, RDA, Visited, Remove, Ignore)) {
+        if (RDA->isSafeToRemove(MI, Remove, Ignore)) {
           for (auto &MO : MI->operands()) {
             if (!MO.isReg() || !MO.isUse() || MO.getReg() == 0)
               continue;
             if (auto *Op = RDA->getReachingMIDef(MI, MO.getReg()))
               Chain.push_back(Op);
           }
           Ignore.insert(MI);
         }
auto RemoveDeadBranch = [](MachineInstr *I) {
     }
   };
 
   if (LoLoop.Revert) {
     if (LoLoop.Start->getOpcode() == ARM::t2WhileLoopStart)
       RevertWhile(LoLoop.Start);
     else
       LoLoop.Start->eraseFromParent();
-    bool FlagsAlreadySet = RevertLoopDec(LoLoop.Dec, true);
+    bool FlagsAlreadySet = RevertLoopDec(LoLoop.Dec);
     RevertLoopEnd(LoLoop.End, FlagsAlreadySet);
   } else {
     LoLoop.Start = ExpandLoopStart(LoLoop);
     RemoveDeadBranch(LoLoop.Start);
     LoLoop.End = ExpandLoopEnd(LoLoop);
     RemoveDeadBranch(LoLoop.End);
     if (LoLoop.IsTailPredicationLegal())
       ConvertVPTBlocks(LoLoop);