diff options
Diffstat (limited to 'llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp')
| -rw-r--r-- | llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp | 968 |
1 files changed, 736 insertions, 232 deletions
diff --git a/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp b/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp index e1c5a9c3e223..6717d4706aef 100644 --- a/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp +++ b/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp @@ -15,6 +15,26 @@ /// - t2LoopDec - placed within in the loop body. /// - t2LoopEnd - the loop latch terminator. /// +/// In addition to this, we also look for the presence of the VCTP instruction, +/// which determines whether we can generated the tail-predicated low-overhead +/// loop form. +/// +/// Assumptions and Dependencies: +/// Low-overhead loops are constructed and executed using a setup instruction: +/// DLS, WLS, DLSTP or WLSTP and an instruction that loops back: LE or LETP. +/// WLS(TP) and LE(TP) are branching instructions with a (large) limited range +/// but fixed polarity: WLS can only branch forwards and LE can only branch +/// backwards. These restrictions mean that this pass is dependent upon block +/// layout and block sizes, which is why it's the last pass to run. The same is +/// true for ConstantIslands, but this pass does not increase the size of the +/// basic blocks, nor does it change the CFG. Instructions are mainly removed +/// during the transform and pseudo instructions are replaced by real ones. In +/// some cases, when we have to revert to a 'normal' loop, we have to introduce +/// multiple instructions for a single pseudo (see RevertWhile and +/// RevertLoopEnd). To handle this situation, t2WhileLoopStart and t2LoopEnd +/// are defined to be as large as this maximum sequence of replacement +/// instructions. +/// //===----------------------------------------------------------------------===// #include "ARM.h" @@ -22,9 +42,16 @@ #include "ARMBaseRegisterInfo.h" #include "ARMBasicBlockInfo.h" #include "ARMSubtarget.h" +#include "Thumb2InstrInfo.h" +#include "llvm/ADT/SetOperations.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineLoopInfo.h" +#include "llvm/CodeGen/MachineLoopUtils.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/Passes.h" +#include "llvm/CodeGen/ReachingDefAnalysis.h" +#include "llvm/MC/MCInstrDesc.h" using namespace llvm; @@ -33,10 +60,154 @@ using namespace llvm; namespace { + struct PredicatedMI { + MachineInstr *MI = nullptr; + SetVector<MachineInstr*> Predicates; + + public: + PredicatedMI(MachineInstr *I, SetVector<MachineInstr*> &Preds) : + MI(I) { + Predicates.insert(Preds.begin(), Preds.end()); + } + }; + + // Represent a VPT block, a list of instructions that begins with a VPST and + // has a maximum of four proceeding instructions. All instructions within the + // block are predicated upon the vpr and we allow instructions to define the + // vpr within in the block too. + class VPTBlock { + std::unique_ptr<PredicatedMI> VPST; + PredicatedMI *Divergent = nullptr; + SmallVector<PredicatedMI, 4> Insts; + + public: + VPTBlock(MachineInstr *MI, SetVector<MachineInstr*> &Preds) { + VPST = std::make_unique<PredicatedMI>(MI, Preds); + } + + void addInst(MachineInstr *MI, SetVector<MachineInstr*> &Preds) { + LLVM_DEBUG(dbgs() << "ARM Loops: Adding predicated MI: " << *MI); + if (!Divergent && !set_difference(Preds, VPST->Predicates).empty()) { + Divergent = &Insts.back(); + LLVM_DEBUG(dbgs() << " - has divergent predicate: " << *Divergent->MI); + } + Insts.emplace_back(MI, Preds); + assert(Insts.size() <= 4 && "Too many instructions in VPT block!"); + } + + // Have we found an instruction within the block which defines the vpr? If + // so, not all the instructions in the block will have the same predicate. + bool HasNonUniformPredicate() const { + return Divergent != nullptr; + } + + // Is the given instruction part of the predicate set controlling the entry + // to the block. + bool IsPredicatedOn(MachineInstr *MI) const { + return VPST->Predicates.count(MI); + } + + // Is the given instruction the only predicate which controls the entry to + // the block. + bool IsOnlyPredicatedOn(MachineInstr *MI) const { + return IsPredicatedOn(MI) && VPST->Predicates.size() == 1; + } + + unsigned size() const { return Insts.size(); } + SmallVectorImpl<PredicatedMI> &getInsts() { return Insts; } + MachineInstr *getVPST() const { return VPST->MI; } + PredicatedMI *getDivergent() const { return Divergent; } + }; + + struct LowOverheadLoop { + + MachineLoop *ML = nullptr; + MachineFunction *MF = nullptr; + MachineInstr *InsertPt = nullptr; + MachineInstr *Start = nullptr; + MachineInstr *Dec = nullptr; + MachineInstr *End = nullptr; + MachineInstr *VCTP = nullptr; + VPTBlock *CurrentBlock = nullptr; + SetVector<MachineInstr*> CurrentPredicate; + SmallVector<VPTBlock, 4> VPTBlocks; + bool Revert = false; + bool CannotTailPredicate = false; + + LowOverheadLoop(MachineLoop *ML) : ML(ML) { + MF = ML->getHeader()->getParent(); + } + + // If this is an MVE instruction, check that we know how to use tail + // predication with it. Record VPT blocks and return whether the + // instruction is valid for tail predication. + bool ValidateMVEInst(MachineInstr *MI); + + void AnalyseMVEInst(MachineInstr *MI) { + CannotTailPredicate = !ValidateMVEInst(MI); + } + + bool IsTailPredicationLegal() const { + // For now, let's keep things really simple and only support a single + // block for tail predication. + return !Revert && FoundAllComponents() && VCTP && + !CannotTailPredicate && ML->getNumBlocks() == 1; + } + + bool ValidateTailPredicate(MachineInstr *StartInsertPt, + ReachingDefAnalysis *RDA, + MachineLoopInfo *MLI); + + // 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(ReachingDefAnalysis *RDA); + + // Check the branch targets are within range and we satisfy our + // restrictions. + void CheckLegality(ARMBasicBlockUtils *BBUtils, ReachingDefAnalysis *RDA, + MachineLoopInfo *MLI); + + bool FoundAllComponents() const { + return Start && Dec && End; + } + + SmallVectorImpl<VPTBlock> &getVPTBlocks() { return VPTBlocks; } + + // Return the loop iteration count, or the number of elements if we're tail + // predicating. + MachineOperand &getCount() { + return IsTailPredicationLegal() ? + VCTP->getOperand(1) : Start->getOperand(0); + } + + unsigned getStartOpcode() const { + bool IsDo = Start->getOpcode() == ARM::t2DoLoopStart; + if (!IsTailPredicationLegal()) + return IsDo ? ARM::t2DLS : ARM::t2WLS; + + return VCTPOpcodeToLSTP(VCTP->getOpcode(), IsDo); + } + + void dump() const { + if (Start) dbgs() << "ARM Loops: Found Loop Start: " << *Start; + if (Dec) dbgs() << "ARM Loops: Found Loop Dec: " << *Dec; + if (End) dbgs() << "ARM Loops: Found Loop End: " << *End; + if (VCTP) dbgs() << "ARM Loops: Found VCTP: " << *VCTP; + if (!FoundAllComponents()) + dbgs() << "ARM Loops: Not a low-overhead loop.\n"; + else if (!(Start && Dec && End)) + dbgs() << "ARM Loops: Failed to find all loop components.\n"; + } + }; + class ARMLowOverheadLoops : public MachineFunctionPass { MachineFunction *MF = nullptr; + MachineLoopInfo *MLI = nullptr; + ReachingDefAnalysis *RDA = nullptr; const ARMBaseInstrInfo *TII = nullptr; MachineRegisterInfo *MRI = nullptr; + const TargetRegisterInfo *TRI = nullptr; std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr; public: @@ -47,6 +218,7 @@ namespace { void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesCFG(); AU.addRequired<MachineLoopInfo>(); + AU.addRequired<ReachingDefAnalysis>(); MachineFunctionPass::getAnalysisUsage(AU); } @@ -54,7 +226,8 @@ namespace { MachineFunctionProperties getRequiredProperties() const override { return MachineFunctionProperties().set( - MachineFunctionProperties::Property::NoVRegs); + MachineFunctionProperties::Property::NoVRegs).set( + MachineFunctionProperties::Property::TracksLiveness); } StringRef getPassName() const override { @@ -64,8 +237,6 @@ namespace { private: bool ProcessLoop(MachineLoop *ML); - MachineInstr * IsSafeToDefineLR(MachineInstr *MI); - bool RevertNonLoops(); void RevertWhile(MachineInstr *MI) const; @@ -74,9 +245,13 @@ namespace { void RevertLoopEnd(MachineInstr *MI, bool SkipCmp = false) const; - void Expand(MachineLoop *ML, MachineInstr *Start, - MachineInstr *InsertPt, MachineInstr *Dec, - MachineInstr *End, bool Revert); + void RemoveLoopUpdate(LowOverheadLoop &LoLoop); + + void ConvertVPTBlocks(LowOverheadLoop &LoLoop); + + MachineInstr *ExpandLoopStart(LowOverheadLoop &LoLoop); + + void Expand(LowOverheadLoop &LoLoop); }; } @@ -86,128 +261,321 @@ char ARMLowOverheadLoops::ID = 0; INITIALIZE_PASS(ARMLowOverheadLoops, DEBUG_TYPE, ARM_LOW_OVERHEAD_LOOPS_NAME, false, false) -bool ARMLowOverheadLoops::runOnMachineFunction(MachineFunction &mf) { - const ARMSubtarget &ST = static_cast<const ARMSubtarget&>(mf.getSubtarget()); - if (!ST.hasLOB()) - return false; +MachineInstr *LowOverheadLoop::IsSafeToDefineLR(ReachingDefAnalysis *RDA) { + // We can define LR because LR already contains the same value. + if (Start->getOperand(0).getReg() == ARM::LR) + return Start; - MF = &mf; - LLVM_DEBUG(dbgs() << "ARM Loops on " << MF->getName() << " ------------- \n"); + unsigned CountReg = Start->getOperand(0).getReg(); + auto IsMoveLR = [&CountReg](MachineInstr *MI) { + return MI->getOpcode() == ARM::tMOVr && + MI->getOperand(0).getReg() == ARM::LR && + MI->getOperand(1).getReg() == CountReg && + MI->getOperand(2).getImm() == ARMCC::AL; + }; - auto &MLI = getAnalysis<MachineLoopInfo>(); - MF->getProperties().set(MachineFunctionProperties::Property::TracksLiveness); - MRI = &MF->getRegInfo(); - TII = static_cast<const ARMBaseInstrInfo*>(ST.getInstrInfo()); - BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(*MF)); - BBUtils->computeAllBlockSizes(); - BBUtils->adjustBBOffsetsAfter(&MF->front()); + MachineBasicBlock *MBB = Start->getParent(); - bool Changed = false; - for (auto ML : MLI) { - if (!ML->getParentLoop()) - Changed |= ProcessLoop(ML); - } - Changed |= RevertNonLoops(); - return Changed; + // 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 (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; + + // 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; } -static bool IsLoopStart(MachineInstr &MI) { - return MI.getOpcode() == ARM::t2DoLoopStart || - MI.getOpcode() == ARM::t2WhileLoopStart; +// 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; } -template<typename T> -static MachineInstr* SearchForDef(MachineInstr *Begin, T End, unsigned Reg) { - for(auto &MI : make_range(T(Begin), End)) { - for (auto &MO : MI.operands()) { - if (!MO.isReg() || !MO.isDef() || MO.getReg() != Reg) +bool LowOverheadLoop::ValidateTailPredicate(MachineInstr *StartInsertPt, + ReachingDefAnalysis *RDA, MachineLoopInfo *MLI) { + 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) { + if (Block.IsPredicatedOn(VCTP)) + continue; + if (!Block.HasNonUniformPredicate() || !isVCTP(Block.getDivergent()->MI)) { + LLVM_DEBUG(dbgs() << "ARM Loops: Found unsupported diverging predicate: " + << *Block.getDivergent()->MI); + return false; + } + SmallVectorImpl<PredicatedMI> &Insts = Block.getInsts(); + for (auto &PredMI : Insts) { + if (PredMI.Predicates.count(VCTP) || isVCTP(PredMI.MI)) continue; - return &MI; + LLVM_DEBUG(dbgs() << "ARM Loops: Can't convert: " << *PredMI.MI + << " - which is predicated on:\n"; + for (auto *MI : PredMI.Predicates) + dbgs() << " - " << *MI; + ); + return false; } } - return nullptr; -} -static MachineInstr* SearchForUse(MachineInstr *Begin, - MachineBasicBlock::iterator End, - unsigned Reg) { - for(auto &MI : make_range(MachineBasicBlock::iterator(Begin), End)) { - for (auto &MO : MI.operands()) { - if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg) - continue; - return &MI; + // For tail predication, we need to provide the number of elements, instead + // 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) { + 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 = InsertPt->getParent(); + if (!RDA->isReachingDefLiveOut(InsertPt, NumElements)) { + if (auto *ElemDef = RDA->getLocalLiveOutMIDef(InsertBB, NumElements)) { + if (IsSafeToMove<MachineBasicBlock::reverse_iterator>(ElemDef, InsertPt, RDA)) { + ElemDef->removeFromParent(); + InsertBB->insert(MachineBasicBlock::iterator(InsertPt), ElemDef); + LLVM_DEBUG(dbgs() << "ARM Loops: Moved element count def: " + << *ElemDef); + } else if (IsSafeToMove<MachineBasicBlock::iterator>(InsertPt, ElemDef, RDA)) { + InsertPt->removeFromParent(); + InsertBB->insertAfter(MachineBasicBlock::iterator(ElemDef), InsertPt); + 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; + } } } - return nullptr; + + // 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 = [&RDA](MachineBasicBlock *MBB, + Register NumElements) { + // NumElements is redefined in this block. + if (RDA->getReachingDef(&MBB->back(), NumElements) >= 0) + return true; + + // Don't continue searching up through multiple predecessors. + if (MBB->pred_size() > 1) + return true; + + return false; + }; + + // First, find the block that looks like the preheader. + MachineBasicBlock *MBB = MLI->findLoopPreheader(ML, true); + if (!MBB) { + LLVM_DEBUG(dbgs() << "ARM Loops: Didn't find preheader.\n"); + return false; + } + + // Then search backwards for a def, until we get to InsertBB. + while (MBB != InsertBB) { + if (CannotProvideElements(MBB, NumElements)) { + LLVM_DEBUG(dbgs() << "ARM Loops: Unable to provide element count.\n"); + return false; + } + MBB = *MBB->pred_begin(); + } + + LLVM_DEBUG(dbgs() << "ARM Loops: Will use tail predication.\n"); + return true; } -// Is it safe to define LR with DLS/WLS? -// LR can 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 *ARMLowOverheadLoops::IsSafeToDefineLR(MachineInstr *Start) { +void LowOverheadLoop::CheckLegality(ARMBasicBlockUtils *BBUtils, + ReachingDefAnalysis *RDA, + MachineLoopInfo *MLI) { + if (Revert) + return; - auto IsMoveLR = [](MachineInstr *MI, unsigned Reg) { - return MI->getOpcode() == ARM::tMOVr && - MI->getOperand(0).getReg() == ARM::LR && - MI->getOperand(1).getReg() == Reg && - MI->getOperand(2).getImm() == ARMCC::AL; - }; + if (!End->getOperand(1).isMBB()) + report_fatal_error("Expected LoopEnd to target basic block"); - MachineBasicBlock *MBB = Start->getParent(); - unsigned CountReg = Start->getOperand(0).getReg(); - // Walk forward and backward in the block to find the closest instructions - // that define LR. Then also filter them out if they're not a mov lr. - MachineInstr *PredLRDef = SearchForDef(Start, MBB->rend(), ARM::LR); - if (PredLRDef && !IsMoveLR(PredLRDef, CountReg)) - PredLRDef = nullptr; - - MachineInstr *SuccLRDef = SearchForDef(Start, MBB->end(), ARM::LR); - if (SuccLRDef && !IsMoveLR(SuccLRDef, CountReg)) - SuccLRDef = nullptr; - - // We've either found one, two or none mov lr instructions... Now figure out - // if they are performing the equilvant mov that the Start instruction will. - // Do this by scanning forward and backward to see if there's a def of the - // register holding the count value. If we find a suitable def, return it as - // the insert point. Later, if InsertPt != Start, then we can remove the - // redundant instruction. - if (SuccLRDef) { - MachineBasicBlock::iterator End(SuccLRDef); - if (!SearchForDef(Start, End, CountReg)) { - return SuccLRDef; - } else - SuccLRDef = nullptr; + // TODO Maybe there's cases where the target doesn't have to be the header, + // but for now be safe and revert. + if (End->getOperand(1).getMBB() != ML->getHeader()) { + LLVM_DEBUG(dbgs() << "ARM Loops: LoopEnd is not targetting header.\n"); + Revert = true; + return; } - if (PredLRDef) { - MachineBasicBlock::reverse_iterator End(PredLRDef); - if (!SearchForDef(Start, End, CountReg)) { - return PredLRDef; - } else - PredLRDef = nullptr; + + // The WLS and LE instructions have 12-bits for the label offset. WLS + // requires a positive offset, while LE uses negative. + if (BBUtils->getOffsetOf(End) < BBUtils->getOffsetOf(ML->getHeader()) || + !BBUtils->isBBInRange(End, ML->getHeader(), 4094)) { + LLVM_DEBUG(dbgs() << "ARM Loops: LE offset is out-of-range\n"); + Revert = true; + return; } - // We can define LR because LR already contains the same value. - if (Start->getOperand(0).getReg() == ARM::LR) - return Start; + 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; + } - // We've found no suitable LR def and Start doesn't use LR directly. Can we - // just define LR anyway? - const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo(); - LivePhysRegs LiveRegs(*TRI); - LiveRegs.addLiveOuts(*MBB); + InsertPt = Revert ? nullptr : IsSafeToDefineLR(RDA); + 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); - // Not if we've haven't found a suitable mov and LR is live out. - if (LiveRegs.contains(ARM::LR)) - return nullptr; + if (!IsTailPredicationLegal()) { + LLVM_DEBUG(if (!VCTP) + dbgs() << "ARM Loops: Didn't find a VCTP instruction.\n"; + dbgs() << "ARM Loops: Tail-predication is not valid.\n"); + return; + } - // If LR is not live out, we can insert the instruction if nothing else - // uses LR after it. - if (!SearchForUse(Start, MBB->end(), ARM::LR)) - return Start; + assert(ML->getBlocks().size() == 1 && + "Shouldn't be processing a loop with more than one block"); + CannotTailPredicate = !ValidateTailPredicate(InsertPt, RDA, MLI); + LLVM_DEBUG(if (CannotTailPredicate) + dbgs() << "ARM Loops: Couldn't validate tail predicate.\n"); +} - LLVM_DEBUG(dbgs() << "ARM Loops: Failed to find suitable insertion point for" - << " LR\n"); - return nullptr; +bool LowOverheadLoop::ValidateMVEInst(MachineInstr* MI) { + if (CannotTailPredicate) + return false; + + // Only support a single vctp. + if (isVCTP(MI) && VCTP) + return false; + + // Start a new vpt block when we discover a vpt. + if (MI->getOpcode() == ARM::MVE_VPST) { + VPTBlocks.emplace_back(MI, CurrentPredicate); + CurrentBlock = &VPTBlocks.back(); + return true; + } else if (isVCTP(MI)) + VCTP = MI; + else if (MI->getOpcode() == ARM::MVE_VPSEL || + MI->getOpcode() == ARM::MVE_VPNOT) + return false; + + // TODO: Allow VPSEL and VPNOT, we currently cannot because: + // 1) It will use the VPR as a predicate operand, but doesn't have to be + // instead a VPT block, which means we can assert while building up + // the VPT block because we don't find another VPST to being a new + // one. + // 2) VPSEL still requires a VPR operand even after tail predicating, + // which means we can't remove it unless there is another + // instruction, such as vcmp, that can provide the VPR def. + + bool IsUse = false; + bool IsDef = false; + const MCInstrDesc &MCID = MI->getDesc(); + for (int i = MI->getNumOperands() - 1; i >= 0; --i) { + const MachineOperand &MO = MI->getOperand(i); + if (!MO.isReg() || MO.getReg() != ARM::VPR) + continue; + + if (MO.isDef()) { + CurrentPredicate.insert(MI); + IsDef = true; + } else if (ARM::isVpred(MCID.OpInfo[i].OperandType)) { + CurrentBlock->addInst(MI, CurrentPredicate); + IsUse = true; + } else { + LLVM_DEBUG(dbgs() << "ARM Loops: Found instruction using vpr: " << *MI); + return false; + } + } + + // If we find a vpr def that is not already predicated on the vctp, we've + // got disjoint predicates that may not be equivalent when we do the + // conversion. + if (IsDef && !IsUse && VCTP && !isVCTP(MI)) { + LLVM_DEBUG(dbgs() << "ARM Loops: Found disjoint vpr def: " << *MI); + return false; + } + + uint64_t Flags = MCID.TSFlags; + if ((Flags & ARMII::DomainMask) != ARMII::DomainMVE) + return true; + + // If we find an instruction that has been marked as not valid for tail + // predication, only allow the instruction if it's contained within a valid + // VPT block. + if ((Flags & ARMII::ValidForTailPredication) == 0 && !IsUse) { + LLVM_DEBUG(dbgs() << "ARM Loops: Can't tail predicate: " << *MI); + return false; + } + + return true; +} + +bool ARMLowOverheadLoops::runOnMachineFunction(MachineFunction &mf) { + const ARMSubtarget &ST = static_cast<const ARMSubtarget&>(mf.getSubtarget()); + if (!ST.hasLOB()) + return false; + + MF = &mf; + LLVM_DEBUG(dbgs() << "ARM Loops on " << MF->getName() << " ------------- \n"); + + MLI = &getAnalysis<MachineLoopInfo>(); + RDA = &getAnalysis<ReachingDefAnalysis>(); + MF->getProperties().set(MachineFunctionProperties::Property::TracksLiveness); + MRI = &MF->getRegInfo(); + TII = static_cast<const ARMBaseInstrInfo*>(ST.getInstrInfo()); + TRI = ST.getRegisterInfo(); + BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(*MF)); + BBUtils->computeAllBlockSizes(); + BBUtils->adjustBBOffsetsAfter(&MF->front()); + + bool Changed = false; + for (auto ML : *MLI) { + if (!ML->getParentLoop()) + Changed |= ProcessLoop(ML); + } + Changed |= RevertNonLoops(); + return Changed; } bool ARMLowOverheadLoops::ProcessLoop(MachineLoop *ML) { @@ -218,14 +586,21 @@ bool ARMLowOverheadLoops::ProcessLoop(MachineLoop *ML) { for (auto I = ML->begin(), E = ML->end(); I != E; ++I) Changed |= ProcessLoop(*I); - LLVM_DEBUG(dbgs() << "ARM Loops: Processing " << *ML); + LLVM_DEBUG(dbgs() << "ARM Loops: Processing loop containing:\n"; + if (auto *Preheader = ML->getLoopPreheader()) + dbgs() << " - " << Preheader->getName() << "\n"; + else if (auto *Preheader = MLI->findLoopPreheader(ML)) + dbgs() << " - " << Preheader->getName() << "\n"; + for (auto *MBB : ML->getBlocks()) + dbgs() << " - " << MBB->getName() << "\n"; + ); // Search the given block for a loop start instruction. If one isn't found, // and there's only one predecessor block, search that one too. std::function<MachineInstr*(MachineBasicBlock*)> SearchForStart = [&SearchForStart](MachineBasicBlock *MBB) -> MachineInstr* { for (auto &MI : *MBB) { - if (IsLoopStart(MI)) + if (isLoopStart(MI)) return &MI; } if (MBB->pred_size() == 1) @@ -233,53 +608,43 @@ bool ARMLowOverheadLoops::ProcessLoop(MachineLoop *ML) { return nullptr; }; - MachineInstr *Start = nullptr; - MachineInstr *Dec = nullptr; - MachineInstr *End = nullptr; - bool Revert = false; - - // Search the preheader for the start intrinsic, or look through the - // predecessors of the header to find exactly one set.iterations intrinsic. + LowOverheadLoop LoLoop(ML); + // Search the preheader for the start intrinsic. // FIXME: I don't see why we shouldn't be supporting multiple predecessors // with potentially multiple set.loop.iterations, so we need to enable this. - if (auto *Preheader = ML->getLoopPreheader()) { - Start = SearchForStart(Preheader); - } else { - LLVM_DEBUG(dbgs() << "ARM Loops: Failed to find loop preheader!\n" - << " - Performing manual predecessor search.\n"); - MachineBasicBlock *Pred = nullptr; - for (auto *MBB : ML->getHeader()->predecessors()) { - if (!ML->contains(MBB)) { - if (Pred) { - LLVM_DEBUG(dbgs() << " - Found multiple out-of-loop preds.\n"); - Start = nullptr; - break; - } - Pred = MBB; - Start = SearchForStart(MBB); - } - } - } + if (auto *Preheader = ML->getLoopPreheader()) + LoLoop.Start = SearchForStart(Preheader); + else if (auto *Preheader = MLI->findLoopPreheader(ML, true)) + LoLoop.Start = SearchForStart(Preheader); + else + return false; // Find the low-overhead loop components and decide whether or not to fall - // back to a normal loop. + // back to a normal loop. Also look for a vctp instructions and decide + // whether we can convert that predicate using tail predication. for (auto *MBB : reverse(ML->getBlocks())) { for (auto &MI : *MBB) { if (MI.getOpcode() == ARM::t2LoopDec) - Dec = &MI; + LoLoop.Dec = &MI; else if (MI.getOpcode() == ARM::t2LoopEnd) - End = &MI; - else if (IsLoopStart(MI)) - Start = &MI; + LoLoop.End = &MI; + else if (isLoopStart(MI)) + LoLoop.Start = &MI; else if (MI.getDesc().isCall()) { // TODO: Though the call will require LE to execute again, does this // mean we should revert? Always executing LE hopefully should be // faster than performing a sub,cmp,br or even subs,br. - Revert = true; + LoLoop.Revert = true; LLVM_DEBUG(dbgs() << "ARM Loops: Found call.\n"); + } else { + // Record VPR defs and build up their corresponding vpt blocks. + // Check we know how to tail predicate any mve instructions. + LoLoop.AnalyseMVEInst(&MI); } - if (!Dec || End) + // We need to ensure that LR is not used or defined inbetween LoopDec and + // LoopEnd. + if (!LoLoop.Dec || LoLoop.End || LoLoop.Revert) continue; // If we find that LR has been written or read between LoopDec and @@ -294,61 +659,21 @@ bool ARMLowOverheadLoops::ProcessLoop(MachineLoop *ML) { if (MI.getOpcode() != ARM::t2LoopDec && MO.isReg() && MO.getReg() == ARM::LR) { LLVM_DEBUG(dbgs() << "ARM Loops: Found LR Use/Def: " << MI); - Revert = true; + LoLoop.Revert = true; break; } } } - - if (Dec && End && Revert) - break; } - LLVM_DEBUG(if (Start) dbgs() << "ARM Loops: Found Loop Start: " << *Start; - if (Dec) dbgs() << "ARM Loops: Found Loop Dec: " << *Dec; - if (End) dbgs() << "ARM Loops: Found Loop End: " << *End;); - - if (!Start && !Dec && !End) { - LLVM_DEBUG(dbgs() << "ARM Loops: Not a low-overhead loop.\n"); - return Changed; - } else if (!(Start && Dec && End)) { - LLVM_DEBUG(dbgs() << "ARM Loops: Failed to find all loop components.\n"); + LLVM_DEBUG(LoLoop.dump()); + if (!LoLoop.FoundAllComponents()) { + LLVM_DEBUG(dbgs() << "ARM Loops: Didn't find loop start, update, end\n"); return false; } - if (!End->getOperand(1).isMBB()) - report_fatal_error("Expected LoopEnd to target basic block"); - - // TODO Maybe there's cases where the target doesn't have to be the header, - // but for now be safe and revert. - if (End->getOperand(1).getMBB() != ML->getHeader()) { - LLVM_DEBUG(dbgs() << "ARM Loops: LoopEnd is not targetting header.\n"); - Revert = true; - } - - // The WLS and LE instructions have 12-bits for the label offset. WLS - // requires a positive offset, while LE uses negative. - if (BBUtils->getOffsetOf(End) < BBUtils->getOffsetOf(ML->getHeader()) || - !BBUtils->isBBInRange(End, ML->getHeader(), 4094)) { - LLVM_DEBUG(dbgs() << "ARM Loops: LE offset is out-of-range\n"); - Revert = true; - } - 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; - } - - MachineInstr *InsertPt = Revert ? nullptr : IsSafeToDefineLR(Start); - if (!InsertPt) { - LLVM_DEBUG(dbgs() << "ARM Loops: Unable to find safe insertion point.\n"); - Revert = true; - } else - LLVM_DEBUG(dbgs() << "ARM Loops: Start insertion point: " << *InsertPt); - - Expand(ML, Start, InsertPt, Dec, End, Revert); + LoLoop.CheckLegality(BBUtils.get(), RDA, MLI); + Expand(LoLoop); return true; } @@ -365,7 +690,7 @@ void ARMLowOverheadLoops::RevertWhile(MachineInstr *MI) const { MIB.addImm(0); MIB.addImm(ARMCC::AL); MIB.addReg(ARM::NoRegister); - + MachineBasicBlock *DestBB = MI->getOperand(1).getMBB(); unsigned BrOpc = BBUtils->isBBInRange(MI, DestBB, 254) ? ARM::tBcc : ARM::t2Bcc; @@ -378,19 +703,15 @@ void ARMLowOverheadLoops::RevertWhile(MachineInstr *MI) const { } bool ARMLowOverheadLoops::RevertLoopDec(MachineInstr *MI, - bool AllowFlags) const { + bool SetFlags) const { LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to sub: " << *MI); MachineBasicBlock *MBB = MI->getParent(); - // If nothing uses or defines CPSR between LoopDec and LoopEnd, use a t2SUBS. - bool SetFlags = false; - if (AllowFlags) { - if (auto *Def = SearchForDef(MI, MBB->end(), ARM::CPSR)) { - if (!SearchForUse(MI, MBB->end(), ARM::CPSR) && - Def->getOpcode() == ARM::t2LoopEnd) - SetFlags = true; - } - } + // 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; MachineInstrBuilder MIB = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(ARM::t2SUBri)); @@ -438,44 +759,223 @@ void ARMLowOverheadLoops::RevertLoopEnd(MachineInstr *MI, bool SkipCmp) const { MI->eraseFromParent(); } -void ARMLowOverheadLoops::Expand(MachineLoop *ML, MachineInstr *Start, - MachineInstr *InsertPt, - MachineInstr *Dec, MachineInstr *End, - bool Revert) { +MachineInstr* ARMLowOverheadLoops::ExpandLoopStart(LowOverheadLoop &LoLoop) { + MachineInstr *InsertPt = LoLoop.InsertPt; + MachineInstr *Start = LoLoop.Start; + MachineBasicBlock *MBB = InsertPt->getParent(); + bool IsDo = Start->getOpcode() == ARM::t2DoLoopStart; + unsigned Opc = LoLoop.getStartOpcode(); + MachineOperand &Count = LoLoop.getCount(); - auto ExpandLoopStart = [this](MachineLoop *ML, MachineInstr *Start, - MachineInstr *InsertPt) { - MachineBasicBlock *MBB = InsertPt->getParent(); - unsigned Opc = Start->getOpcode() == ARM::t2DoLoopStart ? - ARM::t2DLS : ARM::t2WLS; - MachineInstrBuilder MIB = - BuildMI(*MBB, InsertPt, InsertPt->getDebugLoc(), TII->get(Opc)); + MachineInstrBuilder MIB = + BuildMI(*MBB, InsertPt, InsertPt->getDebugLoc(), TII->get(Opc)); - MIB.addDef(ARM::LR); - MIB.add(Start->getOperand(0)); - if (Opc == ARM::t2WLS) - MIB.add(Start->getOperand(1)); - - if (InsertPt != Start) - InsertPt->eraseFromParent(); - Start->eraseFromParent(); - LLVM_DEBUG(dbgs() << "ARM Loops: Inserted start: " << *MIB); - return &*MIB; + MIB.addDef(ARM::LR); + MIB.add(Count); + if (!IsDo) + MIB.add(Start->getOperand(1)); + + // 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(Start, + Start->getOperand(0).getReg())) { + Killed.push_back(Def); + + while (!Killed.empty()) { + MachineInstr *Def = Killed.back(); + Killed.pop_back(); + Dead.push_back(Def); + for (auto &MO : Def->operands()) { + if (!MO.isReg() || !MO.isKill()) + continue; + + MachineInstr *Kill = RDA->getReachingMIDef(Def, MO.getReg()); + if (Kill && RDA->getNumUses(Kill, MO.getReg()) == 1) + Killed.push_back(Kill); + } + } + for (auto *MI : Dead) + MI->eraseFromParent(); + } + } + + // If we're inserting at a mov lr, then remove it as it's redundant. + if (InsertPt != Start) + InsertPt->eraseFromParent(); + Start->eraseFromParent(); + LLVM_DEBUG(dbgs() << "ARM Loops: Inserted start: " << *MIB); + return &*MIB; +} + +// Goal is to optimise and clean-up these loops: +// +// vector.body: +// renamable $vpr = MVE_VCTP32 renamable $r3, 0, $noreg +// renamable $r3, dead $cpsr = tSUBi8 killed renamable $r3(tied-def 0), 4 +// .. +// $lr = MVE_DLSTP_32 renamable $r3 +// +// The SUB is the old update of the loop iteration count expression, which +// is no longer needed. This sub is removed when the element count, which is in +// r3 in this example, is defined by an instruction in the loop, and it has +// no uses. +// +void ARMLowOverheadLoops::RemoveLoopUpdate(LowOverheadLoop &LoLoop) { + Register ElemCount = LoLoop.VCTP->getOperand(1).getReg(); + MachineInstr *LastInstrInBlock = &LoLoop.VCTP->getParent()->back(); + + LLVM_DEBUG(dbgs() << "ARM Loops: Trying to remove loop update stmt\n"); + + if (LoLoop.ML->getNumBlocks() != 1) { + LLVM_DEBUG(dbgs() << "ARM Loops: Single block loop expected\n"); + return; + } + + LLVM_DEBUG(dbgs() << "ARM Loops: Analyzing elemcount in operand: "; + LoLoop.VCTP->getOperand(1).dump()); + + // Find the definition we are interested in removing, if there is one. + MachineInstr *Def = RDA->getReachingMIDef(LastInstrInBlock, ElemCount); + if (!Def) { + LLVM_DEBUG(dbgs() << "ARM Loops: Can't find a def, nothing to do.\n"); + return; + } + + // Bail if we define CPSR and it is not dead + if (!Def->registerDefIsDead(ARM::CPSR, TRI)) { + LLVM_DEBUG(dbgs() << "ARM Loops: CPSR is not dead\n"); + return; + } + + // Bail if elemcount is used in exit blocks, i.e. if it is live-in. + if (isRegLiveInExitBlocks(LoLoop.ML, ElemCount)) { + LLVM_DEBUG(dbgs() << "ARM Loops: Elemcount is live-out, can't remove stmt\n"); + return; + } + + // Bail if there are uses after this Def in the block. + SmallVector<MachineInstr*, 4> Uses; + RDA->getReachingLocalUses(Def, ElemCount, Uses); + if (Uses.size()) { + LLVM_DEBUG(dbgs() << "ARM Loops: Local uses in block, can't remove stmt\n"); + return; + } + + Uses.clear(); + RDA->getAllInstWithUseBefore(Def, ElemCount, Uses); + + // Remove Def if there are no uses, or if the only use is the VCTP + // instruction. + if (!Uses.size() || (Uses.size() == 1 && Uses[0] == LoLoop.VCTP)) { + LLVM_DEBUG(dbgs() << "ARM Loops: Removing loop update instruction: "; + Def->dump()); + Def->eraseFromParent(); + return; + } + + LLVM_DEBUG(dbgs() << "ARM Loops: Can't remove loop update, it's used by:\n"; + for (auto U : Uses) U->dump()); +} + +void ARMLowOverheadLoops::ConvertVPTBlocks(LowOverheadLoop &LoLoop) { + auto RemovePredicate = [](MachineInstr *MI) { + LLVM_DEBUG(dbgs() << "ARM Loops: Removing predicate from: " << *MI); + if (int PIdx = llvm::findFirstVPTPredOperandIdx(*MI)) { + assert(MI->getOperand(PIdx).getImm() == ARMVCC::Then && + "Expected Then predicate!"); + MI->getOperand(PIdx).setImm(ARMVCC::None); + MI->getOperand(PIdx+1).setReg(0); + } else + llvm_unreachable("trying to unpredicate a non-predicated instruction"); }; + // There are a few scenarios which we have to fix up: + // 1) A VPT block with is only predicated by the vctp and has no internal vpr + // defs. + // 2) A VPT block which is only predicated by the vctp but has an internal + // vpr def. + // 3) A VPT block which is predicated upon the vctp as well as another vpr + // def. + // 4) A VPT block which is not predicated upon a vctp, but contains it and + // all instructions within the block are predicated upon in. + + for (auto &Block : LoLoop.getVPTBlocks()) { + SmallVectorImpl<PredicatedMI> &Insts = Block.getInsts(); + if (Block.HasNonUniformPredicate()) { + PredicatedMI *Divergent = Block.getDivergent(); + if (isVCTP(Divergent->MI)) { + // The vctp will be removed, so the size of the vpt block needs to be + // modified. + uint64_t Size = getARMVPTBlockMask(Block.size() - 1); + Block.getVPST()->getOperand(0).setImm(Size); + LLVM_DEBUG(dbgs() << "ARM Loops: Modified VPT block mask.\n"); + } else if (Block.IsOnlyPredicatedOn(LoLoop.VCTP)) { + // The VPT block has a non-uniform predicate but it's entry is guarded + // only by a vctp, which means we: + // - Need to remove the original vpst. + // - Then need to unpredicate any following instructions, until + // we come across the divergent vpr def. + // - Insert a new vpst to predicate the instruction(s) that following + // the divergent vpr def. + // TODO: We could be producing more VPT blocks than necessary and could + // fold the newly created one into a proceeding one. + for (auto I = ++MachineBasicBlock::iterator(Block.getVPST()), + E = ++MachineBasicBlock::iterator(Divergent->MI); I != E; ++I) + RemovePredicate(&*I); + + unsigned Size = 0; + auto E = MachineBasicBlock::reverse_iterator(Divergent->MI); + auto I = MachineBasicBlock::reverse_iterator(Insts.back().MI); + MachineInstr *InsertAt = nullptr; + while (I != E) { + InsertAt = &*I; + ++Size; + ++I; + } + MachineInstrBuilder MIB = BuildMI(*InsertAt->getParent(), InsertAt, + InsertAt->getDebugLoc(), + TII->get(ARM::MVE_VPST)); + MIB.addImm(getARMVPTBlockMask(Size)); + LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *Block.getVPST()); + LLVM_DEBUG(dbgs() << "ARM Loops: Created VPST: " << *MIB); + Block.getVPST()->eraseFromParent(); + } + } else if (Block.IsOnlyPredicatedOn(LoLoop.VCTP)) { + // A vpt block which is only predicated upon vctp and has no internal vpr + // defs: + // - Remove vpst. + // - Unpredicate the remaining instructions. + LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *Block.getVPST()); + Block.getVPST()->eraseFromParent(); + for (auto &PredMI : Insts) + RemovePredicate(PredMI.MI); + } + } + + LLVM_DEBUG(dbgs() << "ARM Loops: Removing VCTP: " << *LoLoop.VCTP); + LoLoop.VCTP->eraseFromParent(); +} + +void ARMLowOverheadLoops::Expand(LowOverheadLoop &LoLoop) { + // Combine the LoopDec and LoopEnd instructions into LE(TP). - auto ExpandLoopEnd = [this](MachineLoop *ML, MachineInstr *Dec, - MachineInstr *End) { + auto ExpandLoopEnd = [this](LowOverheadLoop &LoLoop) { + MachineInstr *End = LoLoop.End; MachineBasicBlock *MBB = End->getParent(); + unsigned Opc = LoLoop.IsTailPredicationLegal() ? + ARM::MVE_LETP : ARM::t2LEUpdate; MachineInstrBuilder MIB = BuildMI(*MBB, End, End->getDebugLoc(), - TII->get(ARM::t2LEUpdate)); + TII->get(Opc)); MIB.addDef(ARM::LR); MIB.add(End->getOperand(0)); MIB.add(End->getOperand(1)); LLVM_DEBUG(dbgs() << "ARM Loops: Inserted LE: " << *MIB); - End->eraseFromParent(); - Dec->eraseFromParent(); + LoLoop.End->eraseFromParent(); + LoLoop.Dec->eraseFromParent(); return &*MIB; }; @@ -496,18 +996,22 @@ void ARMLowOverheadLoops::Expand(MachineLoop *ML, MachineInstr *Start, } }; - if (Revert) { - if (Start->getOpcode() == ARM::t2WhileLoopStart) - RevertWhile(Start); + if (LoLoop.Revert) { + if (LoLoop.Start->getOpcode() == ARM::t2WhileLoopStart) + RevertWhile(LoLoop.Start); else - Start->eraseFromParent(); - bool FlagsAlreadySet = RevertLoopDec(Dec, true); - RevertLoopEnd(End, FlagsAlreadySet); + LoLoop.Start->eraseFromParent(); + bool FlagsAlreadySet = RevertLoopDec(LoLoop.Dec, true); + RevertLoopEnd(LoLoop.End, FlagsAlreadySet); } else { - Start = ExpandLoopStart(ML, Start, InsertPt); - RemoveDeadBranch(Start); - End = ExpandLoopEnd(ML, Dec, End); - RemoveDeadBranch(End); + LoLoop.Start = ExpandLoopStart(LoLoop); + RemoveDeadBranch(LoLoop.Start); + LoLoop.End = ExpandLoopEnd(LoLoop); + RemoveDeadBranch(LoLoop.End); + if (LoLoop.IsTailPredicationLegal()) { + RemoveLoopUpdate(LoLoop); + ConvertVPTBlocks(LoLoop); + } } } @@ -521,7 +1025,7 @@ bool ARMLowOverheadLoops::RevertNonLoops() { SmallVector<MachineInstr*, 4> Ends; for (auto &I : MBB) { - if (IsLoopStart(I)) + if (isLoopStart(I)) Starts.push_back(&I); else if (I.getOpcode() == ARM::t2LoopDec) Decs.push_back(&I); |