[ARM][RDA] add getUniqueReachingMIDef

[samparker]

Summary

Add getUniqueReachingMIDef to RDA which performs a global search for a machine instruction that produces a unique definition of a given register at a given point. Also add two helper functions (getMIOperand) that wrap around this functionality to get the incoming definition uses of a given instruction. These now replaces the uses of getReachingMIDef in ARMLowOverheadLoops. getReachingMIDef has been renamed to getReachingLocalMIDef and has been made private along with getInstFromId.

[samparker]

• Rebased after committing some changes under an NFC.
• Added two getMIOperand methods.

[samparker]

Ping.

[SjoerdMeijer]

llvm/include/llvm/CodeGen/ReachingDefAnalysis.h

155

Incoming -> Defs?

226

This function already exists. Why this change?

llvm/lib/CodeGen/ReachingDefAnalysis.cpp

337

nit: use shorter notation?

if (InstIds[LocalDef] < InstIds[MI])

[samparker]

llvm/include/llvm/CodeGen/ReachingDefAnalysis.h

226

Just making it private.

llvm/lib/CodeGen/ReachingDefAnalysis.cpp

337

Can't use that notation in a const method.

[SjoerdMeijer]

LGTM

llvm/include/llvm/CodeGen/ReachingDefAnalysis.h

226

Ah, okay, thanks, missed that.

llvm/lib/CodeGen/ReachingDefAnalysis.cpp

337

Cheers, missed that too

llvm/include/llvm/CodeGen/ReachingDefAnalysis.h

private:
   /// All reaching defs of all reg units for a all MBBs
   using MBBReachingDefsInfo = SmallVector<MBBDefsInfo, 4>;
   MBBReachingDefsInfo MBBReachingDefs;
 
   /// Default values are 'nothing happened a long time ago'.
   const int ReachingDefDefaultVal = -(1 << 20);
 
   using InstSet = SmallPtrSetImpl<MachineInstr*>;
+  using BlockSet = SmallPtrSetImpl<MachineBasicBlock*>;
 
 public:
   static char ID; // Pass identification, replacement for typeid
 
   ReachingDefAnalysis() : MachineFunctionPass(ID) {
     initializeReachingDefAnalysisPass(*PassRegistry::getPassRegistry());
   }
   void releaseMemory() override;
public:
 
   /// Traverse the machine function, mapping definitions.
   void traverse();
 
   /// Provides the instruction id of the closest reaching def instruction of
   /// PhysReg that reaches MI, relative to the begining of MI's basic block.
   int getReachingDef(MachineInstr *MI, int PhysReg) const;
 
-  /// Provides the instruction of the closest reaching def instruction of
-  /// PhysReg that reaches MI, relative to the begining of MI's basic block.
-  MachineInstr *getReachingMIDef(MachineInstr *MI, int PhysReg) const;
-
-  /// Provides the MI, from the given block, corresponding to the Id or a
-  /// nullptr if the id does not refer to the block.
-  MachineInstr *getInstFromId(MachineBasicBlock *MBB, int InstId) const;
-
   /// Return whether A and B use the same def of PhysReg.
   bool hasSameReachingDef(MachineInstr *A, MachineInstr *B, int PhysReg) const;
 
   /// Return whether the reaching def for MI also is live out of its parent
   /// 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;
 
+  /// If a single MachineInstr creates the reaching definition, then return it.
+  /// Otherwise return null.
+  MachineInstr *getUniqueReachingMIDef(MachineInstr *MI, int PhysReg) const;
+
+  /// If a single MachineInstr creates the reaching definition, for MIs operand
+  /// at Idx, then return it. Otherwise return null.
+  MachineInstr *getMIOperand(MachineInstr *MI, unsigned Idx) const;
+
+  /// If a single MachineInstr creates the reaching definition, for MIs MO,
+  /// then return it. Otherwise return null.
+  MachineInstr *getMIOperand(MachineInstr *MI, MachineOperand &MO) const;
+
   /// Provide whether the register has been defined in the same basic block as,
   /// and before, MI.
   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;
 
+  /// Search MBB for a definition of PhysReg and insert it into Defs. If no
+  /// definition is found, recursively search the predecessor blocks for them.
+  void getLiveOuts(MachineBasicBlock *MBB, int PhysReg, InstSet &Defs,
+                   BlockSet &VisitedBBs) 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.
private:
   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;
+
+  /// Provides the MI, from the given block, corresponding to the Id or a
+  /// nullptr if the id does not refer to the block.
+  MachineInstr *getInstFromId(MachineBasicBlock *MBB, int InstId) const;
+
+  /// Provides the instruction of the closest reaching def instruction of
+  /// PhysReg that reaches MI, relative to the begining of MI's basic block.
+  MachineInstr *getReachingLocalMIDef(MachineInstr *MI, int PhysReg) const;
 };
 
 } // namespace llvm
 
 #endif // LLVM_CODEGEN_REACHINGDEFSANALYSIS_H

llvm/lib/CodeGen/ReachingDefAnalysis.cpp

for (int Def : MBBReachingDefs[MBBNumber][*Unit]) {
         break;
       DefRes = Def;
     }
     LatestDef = std::max(LatestDef, DefRes);
   }
   return LatestDef;
 }
 
-MachineInstr* ReachingDefAnalysis::getReachingMIDef(MachineInstr *MI,
+MachineInstr* ReachingDefAnalysis::getReachingLocalMIDef(MachineInstr *MI,
                                                     int PhysReg) const {
   return getInstFromId(MI->getParent(), getReachingDef(MI, PhysReg));
 }
 
 bool ReachingDefAnalysis::hasSameReachingDef(MachineInstr *A, MachineInstr *B,
                                              int PhysReg) const {
   MachineBasicBlock *ParentA = A->getParent();
   MachineBasicBlock *ParentB = B->getParent();
void ReachingDefAnalysis::getReachingLocalUses(MachineInstr *Def, int PhysReg,
   MachineBasicBlock *MBB = Def->getParent();
   MachineBasicBlock::iterator MI = MachineBasicBlock::iterator(Def);
   while (++MI != MBB->end()) {
     if (MI->isDebugInstr())
       continue;
 
     // If/when we find a new reaching def, we know that there's no more uses
     // of 'Def'.
-    if (getReachingMIDef(&*MI, PhysReg) != Def)
+    if (getReachingLocalMIDef(&*MI, PhysReg) != Def)
       return;
 
     for (auto &MO : MI->operands()) {
       if (!MO.isReg() || !MO.isUse() || MO.getReg() != PhysReg)
         continue;
 
       Uses.insert(&*MI);
       if (MO.isKill())
while (!ToVisit.empty()) {
       if (getLiveInUses(MBB, PhysReg, Uses))
         ToVisit.insert(ToVisit.end(), MBB->successors().begin(),
                        MBB->successors().end());
       Visited.insert(MBB);
     }
   }
 }
 
+void
+ReachingDefAnalysis::getLiveOuts(MachineBasicBlock *MBB, int PhysReg,
+                                 InstSet &Defs, BlockSet &VisitedBBs) const {
+  if (VisitedBBs.count(MBB))
+    return;
+
+  VisitedBBs.insert(MBB);
+  LivePhysRegs LiveRegs(*TRI);
+  LiveRegs.addLiveOuts(*MBB);
+  if (!LiveRegs.contains(PhysReg))
+    return;
+
+  if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg))
+    Defs.insert(Def);
+  else
+    for (auto *Pred : MBB->predecessors())
+      getLiveOuts(Pred, PhysReg, Defs, VisitedBBs);
+}
+
+MachineInstr *ReachingDefAnalysis::getUniqueReachingMIDef(MachineInstr *MI,
+                                                          int PhysReg) const {
+  // If there's a local def before MI, return it.
+  MachineInstr *LocalDef = getReachingLocalMIDef(MI, PhysReg);
+  if (InstIds.lookup(LocalDef) < InstIds.lookup(MI))
+    return LocalDef;
+
+  SmallPtrSet<MachineBasicBlock*, 4> VisitedBBs;
+  SmallPtrSet<MachineInstr*, 2> Incoming;
+  for (auto *Pred : MI->getParent()->predecessors())
+    getLiveOuts(Pred, PhysReg, Incoming, VisitedBBs);
+
+  // If we have a local def and an incoming instruction, then there's not a
+  // unique instruction def.
+  if (!Incoming.empty() && LocalDef)
+    return nullptr;
+  else if (Incoming.size() == 1)
+    return *Incoming.begin();
+  else
+    return LocalDef;
+}
+
+MachineInstr *ReachingDefAnalysis::getMIOperand(MachineInstr *MI,
+                                                unsigned Idx) const {
+  assert(MI->getOperand(Idx).isReg() && "Expected register operand");
+  return getUniqueReachingMIDef(MI, MI->getOperand(Idx).getReg());
+}
+
+MachineInstr *ReachingDefAnalysis::getMIOperand(MachineInstr *MI,
+                                                MachineOperand &MO) const {
+  assert(MO.isReg() && "Expected register operand");
+  return getUniqueReachingMIDef(MI, MO.getReg());
+}
+
 bool ReachingDefAnalysis::isRegUsedAfter(MachineInstr *MI, int PhysReg) const {
   MachineBasicBlock *MBB = MI->getParent();
   LivePhysRegs LiveRegs(*TRI);
   LiveRegs.addLiveOuts(*MBB);
 
   // Yes if the register is live out of the basic block.
   if (LiveRegs.contains(PhysReg))
     return true;

 
 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 Def == getReachingLocalMIDef(MI, PhysReg);
 
   return false;
 }
 
 bool
 ReachingDefAnalysis::isReachingDefLiveOut(MachineInstr *MI, int PhysReg) const {
   MachineBasicBlock *MBB = MI->getParent();
   LivePhysRegs LiveRegs(*TRI);
auto IsDead = [this](MachineInstr *Def, int PhysReg) {
     SmallPtrSet<MachineInstr*, 4> Uses;
     getGlobalUses(Def, PhysReg, Uses);
     return Uses.size() == 1;
   };
 
   for (auto &MO : MI->uses()) {
     if (!MO.isReg() || MO.getReg() == 0 || !MO.isKill())
       continue;
-    if (MachineInstr *Def = getReachingMIDef(MI, MO.getReg()))
+    if (MachineInstr *Def = getReachingLocalMIDef(MI, MO.getReg()))
       if (IsDead(Def, MO.getReg()))
         collectLocalKilledOperands(Def, Dead);
   }
 }
 
 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)) {
+    if (auto *Def = getReachingLocalMIDef(MI, PhysReg)) {
       SmallPtrSet<MachineInstr*, 2> Uses;
       getReachingLocalUses(Def, PhysReg, Uses);
       for (auto *Use : Uses)
         if (!Ignore.count(Use))
           return false;
     } else
       return false;
   }

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

return MI->getOpcode() == ARM::tMOVr &&
            MI->getOperand(2).getImm() == ARMCC::AL;
    };
 
   MachineBasicBlock *MBB = Start->getParent();
 
   // Find an insertion point:
   // - Is there a (mov lr, Count) before Start? If so, and nothing else writes
   //   to Count before Start, we can insert at that mov.
-  if (auto *LRDef = RDA.getReachingMIDef(Start, ARM::LR))
+  if (auto *LRDef = RDA.getUniqueReachingMIDef(Start, ARM::LR))
     if (IsMoveLR(LRDef) && RDA.hasSameReachingDef(Start, LRDef, CountReg))
       return LRDef;
 
   // - 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;
auto IsValidSub = [](MachineInstr *MI, unsigned ExpectedVecWidth) {
     case ARM::t2SUBri12:
       ImmOpIdx = 2;
       break;
     }
     return MI->getOperand(ImmOpIdx).getImm() == ExpectedVecWidth;
   };
 
   MBB = VCTP->getParent();
-  if (MachineInstr *Def = RDA.getReachingMIDef(&MBB->back(), NumElements)) {
+  if (auto *Def = RDA.getUniqueReachingMIDef(&MBB->back(), NumElements)) {
     SmallPtrSet<MachineInstr*, 2> ElementChain;
     SmallPtrSet<MachineInstr*, 2> Ignore = { VCTP };
     unsigned ExpectedVectorWidth = getTailPredVectorWidth(VCTP->getOpcode());
 
     if (RDA.isSafeToRemove(Def, ElementChain, Ignore)) {
       bool FoundSub = false;
 
       for (auto *MI : ElementChain) {

 // Thus, $r3 which defines the number of elements, is written to $lr,
 // and then we want to delete the whole chain that used to define $lr,
 // see the comment below how this chain could look like.
 //
 void ARMLowOverheadLoops::IterationCountDCE(LowOverheadLoop &LoLoop) {
   if (!LoLoop.IsTailPredicationLegal())
     return;
 
-  auto *Def = RDA->getReachingMIDef(LoLoop.Start,
-                                    LoLoop.Start->getOperand(0).getReg());
+  MachineInstr *Def = RDA->getMIOperand(LoLoop.Start, 0);
   if (!Def)
     return;
 
   // Collect IT blocks.
   std::map<MachineInstr *, SmallPtrSet<MachineInstr *, 2>> ITBlocks;
   std::map<MachineInstr *, MachineInstr *> Predicates;
   MachineInstr *IT = nullptr;
   for (auto &MI : *Def->getParent()) {
for (auto *MBB : PostOrder) {
     recomputeLiveIns(*MBB);
     // FIXME: For some reason, the live-in print order is non-deterministic for
     // our tests and I can't out why... So just sort them.
     MBB->sortUniqueLiveIns();
   }
 
   for (auto *MBB : reverse(PostOrder))
     recomputeLivenessFlags(*MBB);
+
+  // We've moved, removed and inserted new instructions, so update RDA.
+  RDA->reset();
 }
 
 bool ARMLowOverheadLoops::RevertNonLoops() {
   LLVM_DEBUG(dbgs() << "ARM Loops: Reverting any remaining pseudos...\n");
   bool Changed = false;
 
   for (auto &MBB : *MF) {
     SmallVector<MachineInstr*, 4> Starts;