diff --git a/llvm/include/llvm/CodeGen/ReachingDefAnalysis.h b/llvm/include/llvm/CodeGen/ReachingDefAnalysis.h --- a/llvm/include/llvm/CodeGen/ReachingDefAnalysis.h +++ b/llvm/include/llvm/CodeGen/ReachingDefAnalysis.h @@ -117,10 +117,17 @@ MachineInstr *getLocalLiveOutMIDef(MachineBasicBlock *MBB, int PhysReg) 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; @@ -141,6 +148,31 @@ 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); @@ -154,6 +186,16 @@ /// 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 + 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 diff --git a/llvm/lib/CodeGen/ReachingDefAnalysis.cpp b/llvm/lib/CodeGen/ReachingDefAnalysis.cpp --- a/llvm/lib/CodeGen/ReachingDefAnalysis.cpp +++ b/llvm/lib/CodeGen/ReachingDefAnalysis.cpp @@ -6,6 +6,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/ADT/SmallSet.h" #include "llvm/CodeGen/LivePhysRegs.h" #include "llvm/CodeGen/ReachingDefAnalysis.h" #include "llvm/CodeGen/TargetRegisterInfo.h" @@ -226,6 +227,11 @@ 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(); @@ -316,6 +322,18 @@ 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(); @@ -352,3 +370,123 @@ 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 +bool ReachingDefAnalysis::isSafeToMove(MachineInstr *From, + MachineInstr *To) const { + if (From->getParent() != To->getParent()) + return false; + + SmallSet 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(From, To); +} + +bool ReachingDefAnalysis::isSafeToMoveBackwards(MachineInstr *From, + MachineInstr *To) const { + return isSafeToMove(From, To); +} + +bool ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI, + InstSet &ToRemove) const { + SmallPtrSet Ignore; + SmallPtrSet Visited; + return isSafeToRemove(MI, Visited, ToRemove, Ignore); +} + +bool +ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI, InstSet &ToRemove, + InstSet &Ignore) const { + SmallPtrSet 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 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 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 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; +} diff --git a/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp b/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp --- a/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp +++ b/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp @@ -217,7 +217,7 @@ // 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. @@ -296,7 +296,7 @@ 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; @@ -314,7 +314,7 @@ 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; @@ -344,72 +344,7 @@ // 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 -static bool IsSafeToMove(MachineInstr *From, MachineInstr *To, ReachingDefAnalysis *RDA) { - SmallSet 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 &Visited, - SmallPtrSetImpl &ToRemove, - SmallPtrSetImpl &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 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) { @@ -446,7 +381,7 @@ // 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; } @@ -457,14 +392,12 @@ MachineBasicBlock *InsertBB = StartInsertPt->getParent(); if (!RDA->isReachingDefLiveOut(StartInsertPt, NumElements)) { if (auto *ElemDef = RDA->getLocalLiveOutMIDef(InsertBB, NumElements)) { - if (IsSafeToMove( - 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( - StartInsertPt, ElemDef, RDA)) { + } else if (RDA->isSafeToMoveBackwards(StartInsertPt, ElemDef)) { StartInsertPt->removeFromParent(); InsertBB->insertAfter(MachineBasicBlock::iterator(ElemDef), StartInsertPt); @@ -483,7 +416,7 @@ 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. @@ -532,12 +465,11 @@ MBB = VCTP->getParent(); if (MachineInstr *Def = RDA->getReachingMIDef(&MBB->back(), NumElements)) { - SmallPtrSet Visited; SmallPtrSet ElementChain; SmallPtrSet 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) { @@ -594,7 +526,7 @@ 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; @@ -788,10 +720,9 @@ return false; } - SmallPtrSet Visited; SmallPtrSet Ignore = { LoLoop.End }; SmallPtrSet 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 { @@ -831,16 +762,16 @@ 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 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)); @@ -897,7 +828,6 @@ SmallVector Dead; if (auto *Def = RDA->getReachingMIDef(LoLoop.Start, LoLoop.Start->getOperand(0).getReg())) { - SmallPtrSet Visited; SmallPtrSet Remove; SmallPtrSet Ignore = { LoLoop.Start, LoLoop.Dec, LoLoop.End, LoLoop.InsertPt }; @@ -905,7 +835,7 @@ 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; @@ -1060,7 +990,7 @@ 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);