Index: llvm/trunk/include/llvm/Analysis/TargetTransformInfo.h =================================================================== --- llvm/trunk/include/llvm/Analysis/TargetTransformInfo.h +++ llvm/trunk/include/llvm/Analysis/TargetTransformInfo.h @@ -27,6 +27,9 @@ #include "llvm/Pass.h" #include "llvm/Support/AtomicOrdering.h" #include "llvm/Support/DataTypes.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/IR/Dominators.h" #include namespace llvm { @@ -75,6 +78,26 @@ } }; +/// Attributes of a target dependent hardware loop. +struct HardwareLoopInfo { + HardwareLoopInfo() = delete; + HardwareLoopInfo(Loop *L) : L(L) {} + Loop *L = nullptr; + BasicBlock *ExitBlock = nullptr; + BranchInst *ExitBranch = nullptr; + const SCEV *ExitCount = nullptr; + IntegerType *CountType = nullptr; + Value *LoopDecrement = nullptr; // Decrement the loop counter by this + // value in every iteration. + bool IsNestingLegal = false; // Can a hardware loop be a parent to + // another hardware loop? + bool CounterInReg = false; // Should loop counter be updated in + // the loop via a phi? + bool isHardwareLoopCandidate(ScalarEvolution &SE, LoopInfo &LI, + DominatorTree &DT, bool ForceNestedLoop = false, + bool ForceHardwareLoopPHI = false); +}; + /// This pass provides access to the codegen interfaces that are needed /// for IR-level transformations. class TargetTransformInfo { @@ -448,23 +471,6 @@ void getUnrollingPreferences(Loop *L, ScalarEvolution &, UnrollingPreferences &UP) const; - /// Attributes of a target dependent hardware loop. - struct HardwareLoopInfo { - HardwareLoopInfo() = delete; - HardwareLoopInfo(Loop *L) : L(L) { } - Loop *L = nullptr; - BasicBlock *ExitBlock = nullptr; - BranchInst *ExitBranch = nullptr; - const SCEV *ExitCount = nullptr; - IntegerType *CountType = nullptr; - Value *LoopDecrement = nullptr; // Decrement the loop counter by this - // value in every iteration. - bool IsNestingLegal = false; // Can a hardware loop be a parent to - // another hardware loop? - bool CounterInReg = false; // Should loop counter be updated in - // the loop via a phi? - }; - /// Query the target whether it would be profitable to convert the given loop /// into a hardware loop. bool isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE, Index: llvm/trunk/include/llvm/Analysis/TargetTransformInfoImpl.h =================================================================== --- llvm/trunk/include/llvm/Analysis/TargetTransformInfoImpl.h +++ llvm/trunk/include/llvm/Analysis/TargetTransformInfoImpl.h @@ -193,7 +193,7 @@ bool isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE, AssumptionCache &AC, TargetLibraryInfo *LibInfo, - TTI::HardwareLoopInfo &HWLoopInfo) { + HardwareLoopInfo &HWLoopInfo) { return false; } Index: llvm/trunk/include/llvm/CodeGen/BasicTTIImpl.h =================================================================== --- llvm/trunk/include/llvm/CodeGen/BasicTTIImpl.h +++ llvm/trunk/include/llvm/CodeGen/BasicTTIImpl.h @@ -495,7 +495,7 @@ bool isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE, AssumptionCache &AC, TargetLibraryInfo *LibInfo, - TTI::HardwareLoopInfo &HWLoopInfo) { + HardwareLoopInfo &HWLoopInfo) { return BaseT::isHardwareLoopProfitable(L, SE, AC, LibInfo, HWLoopInfo); } Index: llvm/trunk/lib/Analysis/TargetTransformInfo.cpp =================================================================== --- llvm/trunk/lib/Analysis/TargetTransformInfo.cpp +++ llvm/trunk/lib/Analysis/TargetTransformInfo.cpp @@ -40,6 +40,91 @@ }; } +bool HardwareLoopInfo::isHardwareLoopCandidate(ScalarEvolution &SE, + LoopInfo &LI, DominatorTree &DT, + bool ForceNestedLoop, + bool ForceHardwareLoopPHI) { + SmallVector ExitingBlocks; + L->getExitingBlocks(ExitingBlocks); + + for (SmallVectorImpl::iterator I = ExitingBlocks.begin(), + IE = ExitingBlocks.end(); + I != IE; ++I) { + BasicBlock *BB = *I; + + // If we pass the updated counter back through a phi, we need to know + // which latch the updated value will be coming from. + if (!L->isLoopLatch(BB)) { + if (ForceHardwareLoopPHI || CounterInReg) + continue; + } + + const SCEV *EC = SE.getExitCount(L, BB); + if (isa(EC)) + continue; + if (const SCEVConstant *ConstEC = dyn_cast(EC)) { + if (ConstEC->getValue()->isZero()) + continue; + } else if (!SE.isLoopInvariant(EC, L)) + continue; + + if (SE.getTypeSizeInBits(EC->getType()) > CountType->getBitWidth()) + continue; + + // If this exiting block is contained in a nested loop, it is not eligible + // for insertion of the branch-and-decrement since the inner loop would + // end up messing up the value in the CTR. + if (!IsNestingLegal && LI.getLoopFor(BB) != L && !ForceNestedLoop) + continue; + + // We now have a loop-invariant count of loop iterations (which is not the + // constant zero) for which we know that this loop will not exit via this + // existing block. + + // We need to make sure that this block will run on every loop iteration. + // For this to be true, we must dominate all blocks with backedges. Such + // blocks are in-loop predecessors to the header block. + bool NotAlways = false; + for (pred_iterator PI = pred_begin(L->getHeader()), + PIE = pred_end(L->getHeader()); + PI != PIE; ++PI) { + if (!L->contains(*PI)) + continue; + + if (!DT.dominates(*I, *PI)) { + NotAlways = true; + break; + } + } + + if (NotAlways) + continue; + + // Make sure this blocks ends with a conditional branch. + Instruction *TI = BB->getTerminator(); + if (!TI) + continue; + + if (BranchInst *BI = dyn_cast(TI)) { + if (!BI->isConditional()) + continue; + + ExitBranch = BI; + } else + continue; + + // Note that this block may not be the loop latch block, even if the loop + // has a latch block. + ExitBlock = *I; + ExitCount = EC; + break; + } + + if (!ExitBlock) + return false; + return true; +} + TargetTransformInfo::TargetTransformInfo(const DataLayout &DL) : TTIImpl(new Model(NoTTIImpl(DL))) {} Index: llvm/trunk/lib/CodeGen/HardwareLoops.cpp =================================================================== --- llvm/trunk/lib/CodeGen/HardwareLoops.cpp +++ llvm/trunk/lib/CodeGen/HardwareLoops.cpp @@ -101,7 +101,7 @@ // Given that the target believes the loop to be profitable, try to // convert it. - bool TryConvertLoop(TTI::HardwareLoopInfo &HWLoopInfo); + bool TryConvertLoop(HardwareLoopInfo &HWLoopInfo); private: ScalarEvolution *SE = nullptr; @@ -139,7 +139,7 @@ void UpdateBranch(Value *EltsRem); public: - HardwareLoop(TTI::HardwareLoopInfo &Info, ScalarEvolution &SE, + HardwareLoop(HardwareLoopInfo &Info, ScalarEvolution &SE, const DataLayout &DL) : SE(SE), DL(DL), L(Info.L), M(L->getHeader()->getModule()), ExitCount(Info.ExitCount), @@ -205,7 +205,7 @@ if (containsIrreducibleCFG(RPOT, *LI)) return false; - TTI::HardwareLoopInfo HWLoopInfo(L); + HardwareLoopInfo HWLoopInfo(L); if (TTI->isHardwareLoopProfitable(L, *SE, *AC, LibInfo, HWLoopInfo) || ForceHardwareLoops) { @@ -225,91 +225,19 @@ return false; } -bool HardwareLoops::TryConvertLoop(TTI::HardwareLoopInfo &HWLoopInfo) { +bool HardwareLoops::TryConvertLoop(HardwareLoopInfo &HWLoopInfo) { Loop *L = HWLoopInfo.L; LLVM_DEBUG(dbgs() << "HWLoops: Try to convert profitable loop: " << *L); - SmallVector ExitingBlocks; - L->getExitingBlocks(ExitingBlocks); - - for (SmallVectorImpl::iterator I = ExitingBlocks.begin(), - IE = ExitingBlocks.end(); I != IE; ++I) { - BasicBlock *BB = *I; - - // If we pass the updated counter back through a phi, we need to know - // which latch the updated value will be coming from. - if (!L->isLoopLatch(BB)) { - if ((ForceHardwareLoopPHI.getNumOccurrences() && ForceHardwareLoopPHI) || - HWLoopInfo.CounterInReg) - continue; - } - - const SCEV *EC = SE->getExitCount(L, BB); - if (isa(EC)) - continue; - if (const SCEVConstant *ConstEC = dyn_cast(EC)) { - if (ConstEC->getValue()->isZero()) - continue; - } else if (!SE->isLoopInvariant(EC, L)) - continue; - - if (SE->getTypeSizeInBits(EC->getType()) > - HWLoopInfo.CountType->getBitWidth()) - continue; - - // If this exiting block is contained in a nested loop, it is not eligible - // for insertion of the branch-and-decrement since the inner loop would - // end up messing up the value in the CTR. - if (!HWLoopInfo.IsNestingLegal && LI->getLoopFor(BB) != L && - !ForceNestedLoop) - continue; - - // We now have a loop-invariant count of loop iterations (which is not the - // constant zero) for which we know that this loop will not exit via this - // existing block. - - // We need to make sure that this block will run on every loop iteration. - // For this to be true, we must dominate all blocks with backedges. Such - // blocks are in-loop predecessors to the header block. - bool NotAlways = false; - for (pred_iterator PI = pred_begin(L->getHeader()), - PIE = pred_end(L->getHeader()); PI != PIE; ++PI) { - if (!L->contains(*PI)) - continue; - - if (!DT->dominates(*I, *PI)) { - NotAlways = true; - break; - } - } - - if (NotAlways) - continue; - - // Make sure this blocks ends with a conditional branch. - Instruction *TI = BB->getTerminator(); - if (!TI) - continue; - - if (BranchInst *BI = dyn_cast(TI)) { - if (!BI->isConditional()) - continue; - - HWLoopInfo.ExitBranch = BI; - } else - continue; - - // Note that this block may not be the loop latch block, even if the loop - // has a latch block. - HWLoopInfo.ExitBlock = *I; - HWLoopInfo.ExitCount = EC; - break; - } - - if (!HWLoopInfo.ExitBlock) + if (!HWLoopInfo.isHardwareLoopCandidate(*SE, *LI, *DT, ForceNestedLoop, + ForceHardwareLoopPHI)) return false; + assert( + (HWLoopInfo.ExitBlock && HWLoopInfo.ExitBranch && HWLoopInfo.ExitCount) && + "Hardware Loop must have set exit info."); + BasicBlock *Preheader = L->getLoopPreheader(); // If we don't have a preheader, then insert one. Index: llvm/trunk/lib/Target/ARM/ARMTargetTransformInfo.h =================================================================== --- llvm/trunk/lib/Target/ARM/ARMTargetTransformInfo.h +++ llvm/trunk/lib/Target/ARM/ARMTargetTransformInfo.h @@ -184,7 +184,7 @@ bool isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE, AssumptionCache &AC, TargetLibraryInfo *LibInfo, - TTI::HardwareLoopInfo &HWLoopInfo); + HardwareLoopInfo &HWLoopInfo); void getUnrollingPreferences(Loop *L, ScalarEvolution &SE, TTI::UnrollingPreferences &UP); Index: llvm/trunk/lib/Target/ARM/ARMTargetTransformInfo.cpp =================================================================== --- llvm/trunk/lib/Target/ARM/ARMTargetTransformInfo.cpp +++ llvm/trunk/lib/Target/ARM/ARMTargetTransformInfo.cpp @@ -696,7 +696,7 @@ bool ARMTTIImpl::isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE, AssumptionCache &AC, TargetLibraryInfo *LibInfo, - TTI::HardwareLoopInfo &HWLoopInfo) { + HardwareLoopInfo &HWLoopInfo) { // Low-overhead branches are only supported in the 'low-overhead branch' // extension of v8.1-m. if (!ST->hasLOB() || DisableLowOverheadLoops) Index: llvm/trunk/lib/Target/PowerPC/PPCTargetTransformInfo.h =================================================================== --- llvm/trunk/lib/Target/PowerPC/PPCTargetTransformInfo.h +++ llvm/trunk/lib/Target/PowerPC/PPCTargetTransformInfo.h @@ -56,7 +56,7 @@ bool isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE, AssumptionCache &AC, TargetLibraryInfo *LibInfo, - TTI::HardwareLoopInfo &HWLoopInfo); + HardwareLoopInfo &HWLoopInfo); void getUnrollingPreferences(Loop *L, ScalarEvolution &SE, TTI::UnrollingPreferences &UP); Index: llvm/trunk/lib/Target/PowerPC/PPCTargetTransformInfo.cpp =================================================================== --- llvm/trunk/lib/Target/PowerPC/PPCTargetTransformInfo.cpp +++ llvm/trunk/lib/Target/PowerPC/PPCTargetTransformInfo.cpp @@ -492,7 +492,7 @@ bool PPCTTIImpl::isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE, AssumptionCache &AC, TargetLibraryInfo *LibInfo, - TTI::HardwareLoopInfo &HWLoopInfo) { + HardwareLoopInfo &HWLoopInfo) { const PPCTargetMachine &TM = ST->getTargetMachine(); TargetSchedModel SchedModel; SchedModel.init(ST);