diff options
Diffstat (limited to 'contrib/llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp')
| -rw-r--r-- | contrib/llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp | 702 |
1 files changed, 405 insertions, 297 deletions
diff --git a/contrib/llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp b/contrib/llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp index d78db6c..ecef6db 100644 --- a/contrib/llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp +++ b/contrib/llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp @@ -14,6 +14,7 @@ #include "llvm/Transforms/Scalar.h" #include "llvm/ADT/SetVector.h" +#include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/CodeMetrics.h" #include "llvm/Analysis/InstructionSimplify.h" @@ -38,16 +39,16 @@ using namespace llvm; #define DEBUG_TYPE "loop-unroll" static cl::opt<unsigned> - UnrollThreshold("unroll-threshold", cl::init(150), cl::Hidden, + UnrollThreshold("unroll-threshold", cl::Hidden, cl::desc("The baseline cost threshold for loop unrolling")); static cl::opt<unsigned> UnrollPercentDynamicCostSavedThreshold( - "unroll-percent-dynamic-cost-saved-threshold", cl::init(20), cl::Hidden, + "unroll-percent-dynamic-cost-saved-threshold", cl::Hidden, cl::desc("The percentage of estimated dynamic cost which must be saved by " "unrolling to allow unrolling up to the max threshold.")); static cl::opt<unsigned> UnrollDynamicCostSavingsDiscount( - "unroll-dynamic-cost-savings-discount", cl::init(2000), cl::Hidden, + "unroll-dynamic-cost-savings-discount", cl::Hidden, cl::desc("This is the amount discounted from the total unroll cost when " "the unrolled form has a high dynamic cost savings (triggered by " "the '-unroll-perecent-dynamic-cost-saved-threshold' flag).")); @@ -58,17 +59,17 @@ static cl::opt<unsigned> UnrollMaxIterationsCountToAnalyze( "iterations when checking full unroll profitability")); static cl::opt<unsigned> -UnrollCount("unroll-count", cl::init(0), cl::Hidden, +UnrollCount("unroll-count", cl::Hidden, cl::desc("Use this unroll count for all loops including those with " "unroll_count pragma values, for testing purposes")); static cl::opt<bool> -UnrollAllowPartial("unroll-allow-partial", cl::init(false), cl::Hidden, +UnrollAllowPartial("unroll-allow-partial", cl::Hidden, cl::desc("Allows loops to be partially unrolled until " "-unroll-threshold loop size is reached.")); static cl::opt<bool> -UnrollRuntime("unroll-runtime", cl::ZeroOrMore, cl::init(false), cl::Hidden, +UnrollRuntime("unroll-runtime", cl::ZeroOrMore, cl::Hidden, cl::desc("Unroll loops with run-time trip counts")); static cl::opt<unsigned> @@ -76,178 +77,95 @@ PragmaUnrollThreshold("pragma-unroll-threshold", cl::init(16 * 1024), cl::Hidden cl::desc("Unrolled size limit for loops with an unroll(full) or " "unroll_count pragma.")); -namespace { - class LoopUnroll : public LoopPass { - public: - static char ID; // Pass ID, replacement for typeid - LoopUnroll(int T = -1, int C = -1, int P = -1, int R = -1) : LoopPass(ID) { - CurrentThreshold = (T == -1) ? UnrollThreshold : unsigned(T); - CurrentPercentDynamicCostSavedThreshold = - UnrollPercentDynamicCostSavedThreshold; - CurrentDynamicCostSavingsDiscount = UnrollDynamicCostSavingsDiscount; - CurrentCount = (C == -1) ? UnrollCount : unsigned(C); - CurrentAllowPartial = (P == -1) ? UnrollAllowPartial : (bool)P; - CurrentRuntime = (R == -1) ? UnrollRuntime : (bool)R; - - UserThreshold = (T != -1) || (UnrollThreshold.getNumOccurrences() > 0); - UserPercentDynamicCostSavedThreshold = - (UnrollPercentDynamicCostSavedThreshold.getNumOccurrences() > 0); - UserDynamicCostSavingsDiscount = - (UnrollDynamicCostSavingsDiscount.getNumOccurrences() > 0); - UserAllowPartial = (P != -1) || - (UnrollAllowPartial.getNumOccurrences() > 0); - UserRuntime = (R != -1) || (UnrollRuntime.getNumOccurrences() > 0); - UserCount = (C != -1) || (UnrollCount.getNumOccurrences() > 0); - - initializeLoopUnrollPass(*PassRegistry::getPassRegistry()); - } - /// A magic value for use with the Threshold parameter to indicate - /// that the loop unroll should be performed regardless of how much - /// code expansion would result. - static const unsigned NoThreshold = UINT_MAX; - - // Threshold to use when optsize is specified (and there is no - // explicit -unroll-threshold). - static const unsigned OptSizeUnrollThreshold = 50; - - // Default unroll count for loops with run-time trip count if - // -unroll-count is not set - static const unsigned UnrollRuntimeCount = 8; - - unsigned CurrentCount; - unsigned CurrentThreshold; - unsigned CurrentPercentDynamicCostSavedThreshold; - unsigned CurrentDynamicCostSavingsDiscount; - bool CurrentAllowPartial; - bool CurrentRuntime; - - // Flags for whether the 'current' settings are user-specified. - bool UserCount; - bool UserThreshold; - bool UserPercentDynamicCostSavedThreshold; - bool UserDynamicCostSavingsDiscount; - bool UserAllowPartial; - bool UserRuntime; - - bool runOnLoop(Loop *L, LPPassManager &LPM) override; - - /// This transformation requires natural loop information & requires that - /// loop preheaders be inserted into the CFG... - /// - void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.addRequired<AssumptionCacheTracker>(); - AU.addRequired<LoopInfoWrapperPass>(); - AU.addPreserved<LoopInfoWrapperPass>(); - AU.addRequiredID(LoopSimplifyID); - AU.addPreservedID(LoopSimplifyID); - AU.addRequiredID(LCSSAID); - AU.addPreservedID(LCSSAID); - AU.addRequired<ScalarEvolution>(); - AU.addPreserved<ScalarEvolution>(); - AU.addRequired<TargetTransformInfoWrapperPass>(); - // FIXME: Loop unroll requires LCSSA. And LCSSA requires dom info. - // If loop unroll does not preserve dom info then LCSSA pass on next - // loop will receive invalid dom info. - // For now, recreate dom info, if loop is unrolled. - AU.addPreserved<DominatorTreeWrapperPass>(); - } +/// A magic value for use with the Threshold parameter to indicate +/// that the loop unroll should be performed regardless of how much +/// code expansion would result. +static const unsigned NoThreshold = UINT_MAX; - // Fill in the UnrollingPreferences parameter with values from the - // TargetTransformationInfo. - void getUnrollingPreferences(Loop *L, const TargetTransformInfo &TTI, - TargetTransformInfo::UnrollingPreferences &UP) { - UP.Threshold = CurrentThreshold; - UP.PercentDynamicCostSavedThreshold = - CurrentPercentDynamicCostSavedThreshold; - UP.DynamicCostSavingsDiscount = CurrentDynamicCostSavingsDiscount; - UP.OptSizeThreshold = OptSizeUnrollThreshold; - UP.PartialThreshold = CurrentThreshold; - UP.PartialOptSizeThreshold = OptSizeUnrollThreshold; - UP.Count = CurrentCount; - UP.MaxCount = UINT_MAX; - UP.Partial = CurrentAllowPartial; - UP.Runtime = CurrentRuntime; - UP.AllowExpensiveTripCount = false; - TTI.getUnrollingPreferences(L, UP); - } +/// Default unroll count for loops with run-time trip count if +/// -unroll-count is not set +static const unsigned DefaultUnrollRuntimeCount = 8; - // Select and return an unroll count based on parameters from - // user, unroll preferences, unroll pragmas, or a heuristic. - // SetExplicitly is set to true if the unroll count is is set by - // the user or a pragma rather than selected heuristically. - unsigned - selectUnrollCount(const Loop *L, unsigned TripCount, bool PragmaFullUnroll, - unsigned PragmaCount, - const TargetTransformInfo::UnrollingPreferences &UP, - bool &SetExplicitly); - - // Select threshold values used to limit unrolling based on a - // total unrolled size. Parameters Threshold and PartialThreshold - // are set to the maximum unrolled size for fully and partially - // unrolled loops respectively. - void selectThresholds(const Loop *L, bool HasPragma, - const TargetTransformInfo::UnrollingPreferences &UP, - unsigned &Threshold, unsigned &PartialThreshold, - unsigned &PercentDynamicCostSavedThreshold, - unsigned &DynamicCostSavingsDiscount) { - // Determine the current unrolling threshold. While this is - // normally set from UnrollThreshold, it is overridden to a - // smaller value if the current function is marked as - // optimize-for-size, and the unroll threshold was not user - // specified. - Threshold = UserThreshold ? CurrentThreshold : UP.Threshold; - PartialThreshold = UserThreshold ? CurrentThreshold : UP.PartialThreshold; - PercentDynamicCostSavedThreshold = - UserPercentDynamicCostSavedThreshold - ? CurrentPercentDynamicCostSavedThreshold - : UP.PercentDynamicCostSavedThreshold; - DynamicCostSavingsDiscount = UserDynamicCostSavingsDiscount - ? CurrentDynamicCostSavingsDiscount - : UP.DynamicCostSavingsDiscount; - - if (!UserThreshold && - L->getHeader()->getParent()->hasFnAttribute( - Attribute::OptimizeForSize)) { - Threshold = UP.OptSizeThreshold; - PartialThreshold = UP.PartialOptSizeThreshold; - } - if (HasPragma) { - // If the loop has an unrolling pragma, we want to be more - // aggressive with unrolling limits. Set thresholds to at - // least the PragmaTheshold value which is larger than the - // default limits. - if (Threshold != NoThreshold) - Threshold = std::max<unsigned>(Threshold, PragmaUnrollThreshold); - if (PartialThreshold != NoThreshold) - PartialThreshold = - std::max<unsigned>(PartialThreshold, PragmaUnrollThreshold); - } - } - bool canUnrollCompletely(Loop *L, unsigned Threshold, - unsigned PercentDynamicCostSavedThreshold, - unsigned DynamicCostSavingsDiscount, - uint64_t UnrolledCost, uint64_t RolledDynamicCost); - }; -} +/// Gather the various unrolling parameters based on the defaults, compiler +/// flags, TTI overrides, pragmas, and user specified parameters. +static TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences( + Loop *L, const TargetTransformInfo &TTI, Optional<unsigned> UserThreshold, + Optional<unsigned> UserCount, Optional<bool> UserAllowPartial, + Optional<bool> UserRuntime, unsigned PragmaCount, bool PragmaFullUnroll, + bool PragmaEnableUnroll, unsigned TripCount) { + TargetTransformInfo::UnrollingPreferences UP; -char LoopUnroll::ID = 0; -INITIALIZE_PASS_BEGIN(LoopUnroll, "loop-unroll", "Unroll loops", false, false) -INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) -INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) -INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) -INITIALIZE_PASS_DEPENDENCY(LoopSimplify) -INITIALIZE_PASS_DEPENDENCY(LCSSA) -INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) -INITIALIZE_PASS_END(LoopUnroll, "loop-unroll", "Unroll loops", false, false) + // Set up the defaults + UP.Threshold = 150; + UP.PercentDynamicCostSavedThreshold = 20; + UP.DynamicCostSavingsDiscount = 2000; + UP.OptSizeThreshold = 50; + UP.PartialThreshold = UP.Threshold; + UP.PartialOptSizeThreshold = UP.OptSizeThreshold; + UP.Count = 0; + UP.MaxCount = UINT_MAX; + UP.Partial = false; + UP.Runtime = false; + UP.AllowExpensiveTripCount = false; + + // Override with any target specific settings + TTI.getUnrollingPreferences(L, UP); + + // Apply size attributes + if (L->getHeader()->getParent()->optForSize()) { + UP.Threshold = UP.OptSizeThreshold; + UP.PartialThreshold = UP.PartialOptSizeThreshold; + } -Pass *llvm::createLoopUnrollPass(int Threshold, int Count, int AllowPartial, - int Runtime) { - return new LoopUnroll(Threshold, Count, AllowPartial, Runtime); -} + // Apply unroll count pragmas + if (PragmaCount) + UP.Count = PragmaCount; + else if (PragmaFullUnroll) + UP.Count = TripCount; -Pass *llvm::createSimpleLoopUnrollPass() { - return llvm::createLoopUnrollPass(-1, -1, 0, 0); + // Apply any user values specified by cl::opt + if (UnrollThreshold.getNumOccurrences() > 0) { + UP.Threshold = UnrollThreshold; + UP.PartialThreshold = UnrollThreshold; + } + if (UnrollPercentDynamicCostSavedThreshold.getNumOccurrences() > 0) + UP.PercentDynamicCostSavedThreshold = + UnrollPercentDynamicCostSavedThreshold; + if (UnrollDynamicCostSavingsDiscount.getNumOccurrences() > 0) + UP.DynamicCostSavingsDiscount = UnrollDynamicCostSavingsDiscount; + if (UnrollCount.getNumOccurrences() > 0) + UP.Count = UnrollCount; + if (UnrollAllowPartial.getNumOccurrences() > 0) + UP.Partial = UnrollAllowPartial; + if (UnrollRuntime.getNumOccurrences() > 0) + UP.Runtime = UnrollRuntime; + + // Apply user values provided by argument + if (UserThreshold.hasValue()) { + UP.Threshold = *UserThreshold; + UP.PartialThreshold = *UserThreshold; + } + if (UserCount.hasValue()) + UP.Count = *UserCount; + if (UserAllowPartial.hasValue()) + UP.Partial = *UserAllowPartial; + if (UserRuntime.hasValue()) + UP.Runtime = *UserRuntime; + + if (PragmaCount > 0 || + ((PragmaFullUnroll || PragmaEnableUnroll) && TripCount != 0)) { + // If the loop has an unrolling pragma, we want to be more aggressive with + // unrolling limits. Set thresholds to at least the PragmaTheshold value + // which is larger than the default limits. + if (UP.Threshold != NoThreshold) + UP.Threshold = std::max<unsigned>(UP.Threshold, PragmaUnrollThreshold); + if (UP.PartialThreshold != NoThreshold) + UP.PartialThreshold = + std::max<unsigned>(UP.PartialThreshold, PragmaUnrollThreshold); + } + + return UP; } namespace { @@ -278,8 +196,8 @@ class UnrolledInstAnalyzer : private InstVisitor<UnrolledInstAnalyzer, bool> { public: UnrolledInstAnalyzer(unsigned Iteration, DenseMap<Value *, Constant *> &SimplifiedValues, - const Loop *L, ScalarEvolution &SE) - : Iteration(Iteration), SimplifiedValues(SimplifiedValues), L(L), SE(SE) { + ScalarEvolution &SE) + : SimplifiedValues(SimplifiedValues), SE(SE) { IterationNumber = SE.getConstant(APInt(64, Iteration)); } @@ -295,13 +213,6 @@ private: /// results saved. DenseMap<Value *, SimplifiedAddress> SimplifiedAddresses; - /// \brief Number of currently simulated iteration. - /// - /// If an expression is ConstAddress+Constant, then the Constant is - /// Start + Iteration*Step, where Start and Step could be obtained from - /// SCEVGEPCache. - unsigned Iteration; - /// \brief SCEV expression corresponding to number of currently simulated /// iteration. const SCEV *IterationNumber; @@ -316,7 +227,6 @@ private: /// post-unrolling. DenseMap<Value *, Constant *> &SimplifiedValues; - const Loop *L; ScalarEvolution &SE; /// \brief Try to simplify instruction \param I using its SCEV expression. @@ -368,11 +278,9 @@ private: return simplifyInstWithSCEV(&I); } - /// TODO: Add visitors for other instruction types, e.g. ZExt, SExt. - /// Try to simplify binary operator I. /// - /// TODO: Probaly it's worth to hoist the code for estimating the + /// TODO: Probably it's worth to hoist the code for estimating the /// simplifications effects to a separate class, since we have a very similar /// code in InlineCost already. bool visitBinaryOperator(BinaryOperator &I) { @@ -412,7 +320,7 @@ private: auto *GV = dyn_cast<GlobalVariable>(AddressIt->second.Base); // We're only interested in loads that can be completely folded to a // constant. - if (!GV || !GV->hasInitializer()) + if (!GV || !GV->hasDefinitiveInitializer() || !GV->isConstant()) return false; ConstantDataSequential *CDS = @@ -420,6 +328,12 @@ private: if (!CDS) return false; + // We might have a vector load from an array. FIXME: for now we just bail + // out in this case, but we should be able to resolve and simplify such + // loads. + if(!CDS->isElementTypeCompatible(I.getType())) + return false; + int ElemSize = CDS->getElementType()->getPrimitiveSizeInBits() / 8U; assert(SimplifiedAddrOp->getValue().getActiveBits() < 64 && "Unexpectedly large index value."); @@ -436,6 +350,59 @@ private: return true; } + + bool visitCastInst(CastInst &I) { + // Propagate constants through casts. + Constant *COp = dyn_cast<Constant>(I.getOperand(0)); + if (!COp) + COp = SimplifiedValues.lookup(I.getOperand(0)); + if (COp) + if (Constant *C = + ConstantExpr::getCast(I.getOpcode(), COp, I.getType())) { + SimplifiedValues[&I] = C; + return true; + } + + return Base::visitCastInst(I); + } + + bool visitCmpInst(CmpInst &I) { + Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); + + // First try to handle simplified comparisons. + if (!isa<Constant>(LHS)) + if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS)) + LHS = SimpleLHS; + if (!isa<Constant>(RHS)) + if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS)) + RHS = SimpleRHS; + + if (!isa<Constant>(LHS) && !isa<Constant>(RHS)) { + auto SimplifiedLHS = SimplifiedAddresses.find(LHS); + if (SimplifiedLHS != SimplifiedAddresses.end()) { + auto SimplifiedRHS = SimplifiedAddresses.find(RHS); + if (SimplifiedRHS != SimplifiedAddresses.end()) { + SimplifiedAddress &LHSAddr = SimplifiedLHS->second; + SimplifiedAddress &RHSAddr = SimplifiedRHS->second; + if (LHSAddr.Base == RHSAddr.Base) { + LHS = LHSAddr.Offset; + RHS = RHSAddr.Offset; + } + } + } + } + + if (Constant *CLHS = dyn_cast<Constant>(LHS)) { + if (Constant *CRHS = dyn_cast<Constant>(RHS)) { + if (Constant *C = ConstantExpr::getCompare(I.getPredicate(), CLHS, CRHS)) { + SimplifiedValues[&I] = C; + return true; + } + } + } + + return Base::visitCmpInst(I); + } }; } // namespace @@ -443,11 +410,11 @@ private: namespace { struct EstimatedUnrollCost { /// \brief The estimated cost after unrolling. - unsigned UnrolledCost; + int UnrolledCost; /// \brief The estimated dynamic cost of executing the instructions in the /// rolled form. - unsigned RolledDynamicCost; + int RolledDynamicCost; }; } @@ -464,10 +431,10 @@ struct EstimatedUnrollCost { /// \returns Optional value, holding the RolledDynamicCost and UnrolledCost. If /// the analysis failed (no benefits expected from the unrolling, or the loop is /// too big to analyze), the returned value is None. -Optional<EstimatedUnrollCost> -analyzeLoopUnrollCost(const Loop *L, unsigned TripCount, ScalarEvolution &SE, - const TargetTransformInfo &TTI, - unsigned MaxUnrolledLoopSize) { +static Optional<EstimatedUnrollCost> +analyzeLoopUnrollCost(const Loop *L, unsigned TripCount, DominatorTree &DT, + ScalarEvolution &SE, const TargetTransformInfo &TTI, + int MaxUnrolledLoopSize) { // We want to be able to scale offsets by the trip count and add more offsets // to them without checking for overflows, and we already don't want to // analyze *massive* trip counts, so we force the max to be reasonably small. @@ -481,24 +448,61 @@ analyzeLoopUnrollCost(const Loop *L, unsigned TripCount, ScalarEvolution &SE, SmallSetVector<BasicBlock *, 16> BBWorklist; DenseMap<Value *, Constant *> SimplifiedValues; + SmallVector<std::pair<Value *, Constant *>, 4> SimplifiedInputValues; // The estimated cost of the unrolled form of the loop. We try to estimate // this by simplifying as much as we can while computing the estimate. - unsigned UnrolledCost = 0; + int UnrolledCost = 0; // We also track the estimated dynamic (that is, actually executed) cost in // the rolled form. This helps identify cases when the savings from unrolling // aren't just exposing dead control flows, but actual reduced dynamic // instructions due to the simplifications which we expect to occur after // unrolling. - unsigned RolledDynamicCost = 0; + int RolledDynamicCost = 0; + + // Ensure that we don't violate the loop structure invariants relied on by + // this analysis. + assert(L->isLoopSimplifyForm() && "Must put loop into normal form first."); + assert(L->isLCSSAForm(DT) && + "Must have loops in LCSSA form to track live-out values."); + + DEBUG(dbgs() << "Starting LoopUnroll profitability analysis...\n"); // Simulate execution of each iteration of the loop counting instructions, // which would be simplified. // Since the same load will take different values on different iterations, // we literally have to go through all loop's iterations. for (unsigned Iteration = 0; Iteration < TripCount; ++Iteration) { + DEBUG(dbgs() << " Analyzing iteration " << Iteration << "\n"); + + // Prepare for the iteration by collecting any simplified entry or backedge + // inputs. + for (Instruction &I : *L->getHeader()) { + auto *PHI = dyn_cast<PHINode>(&I); + if (!PHI) + break; + + // The loop header PHI nodes must have exactly two input: one from the + // loop preheader and one from the loop latch. + assert( + PHI->getNumIncomingValues() == 2 && + "Must have an incoming value only for the preheader and the latch."); + + Value *V = PHI->getIncomingValueForBlock( + Iteration == 0 ? L->getLoopPreheader() : L->getLoopLatch()); + Constant *C = dyn_cast<Constant>(V); + if (Iteration != 0 && !C) + C = SimplifiedValues.lookup(V); + if (C) + SimplifiedInputValues.push_back({PHI, C}); + } + + // Now clear and re-populate the map for the next iteration. SimplifiedValues.clear(); - UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, L, SE); + while (!SimplifiedInputValues.empty()) + SimplifiedValues.insert(SimplifiedInputValues.pop_back_val()); + + UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, SE); BBWorklist.clear(); BBWorklist.insert(L->getHeader()); @@ -510,21 +514,67 @@ analyzeLoopUnrollCost(const Loop *L, unsigned TripCount, ScalarEvolution &SE, // it. We don't change the actual IR, just count optimization // opportunities. for (Instruction &I : *BB) { - unsigned InstCost = TTI.getUserCost(&I); + int InstCost = TTI.getUserCost(&I); // Visit the instruction to analyze its loop cost after unrolling, // and if the visitor returns false, include this instruction in the // unrolled cost. if (!Analyzer.visit(I)) UnrolledCost += InstCost; + else { + DEBUG(dbgs() << " " << I + << " would be simplified if loop is unrolled.\n"); + (void)0; + } // Also track this instructions expected cost when executing the rolled // loop form. RolledDynamicCost += InstCost; // If unrolled body turns out to be too big, bail out. - if (UnrolledCost > MaxUnrolledLoopSize) + if (UnrolledCost > MaxUnrolledLoopSize) { + DEBUG(dbgs() << " Exceeded threshold.. exiting.\n" + << " UnrolledCost: " << UnrolledCost + << ", MaxUnrolledLoopSize: " << MaxUnrolledLoopSize + << "\n"); return None; + } + } + + TerminatorInst *TI = BB->getTerminator(); + + // Add in the live successors by first checking whether we have terminator + // that may be simplified based on the values simplified by this call. + if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { + if (BI->isConditional()) { + if (Constant *SimpleCond = + SimplifiedValues.lookup(BI->getCondition())) { + BasicBlock *Succ = nullptr; + // Just take the first successor if condition is undef + if (isa<UndefValue>(SimpleCond)) + Succ = BI->getSuccessor(0); + else + Succ = BI->getSuccessor( + cast<ConstantInt>(SimpleCond)->isZero() ? 1 : 0); + if (L->contains(Succ)) + BBWorklist.insert(Succ); + continue; + } + } + } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { + if (Constant *SimpleCond = + SimplifiedValues.lookup(SI->getCondition())) { + BasicBlock *Succ = nullptr; + // Just take the first successor if condition is undef + if (isa<UndefValue>(SimpleCond)) + Succ = SI->getSuccessor(0); + else + Succ = SI->findCaseValue(cast<ConstantInt>(SimpleCond)) + .getCaseSuccessor(); + if (L->contains(Succ)) + BBWorklist.insert(Succ); + continue; + } } // Add BB's successors to the worklist. @@ -535,9 +585,15 @@ analyzeLoopUnrollCost(const Loop *L, unsigned TripCount, ScalarEvolution &SE, // If we found no optimization opportunities on the first iteration, we // won't find them on later ones too. - if (UnrolledCost == RolledDynamicCost) + if (UnrolledCost == RolledDynamicCost) { + DEBUG(dbgs() << " No opportunities found.. exiting.\n" + << " UnrolledCost: " << UnrolledCost << "\n"); return None; + } } + DEBUG(dbgs() << "Analysis finished:\n" + << "UnrolledCost: " << UnrolledCost << ", " + << "RolledDynamicCost: " << RolledDynamicCost << "\n"); return {{UnrolledCost, RolledDynamicCost}}; } @@ -583,6 +639,12 @@ static bool HasUnrollFullPragma(const Loop *L) { return GetUnrollMetadataForLoop(L, "llvm.loop.unroll.full"); } +// Returns true if the loop has an unroll(enable) pragma. This metadata is used +// for both "#pragma unroll" and "#pragma clang loop unroll(enable)" directives. +static bool HasUnrollEnablePragma(const Loop *L) { + return GetUnrollMetadataForLoop(L, "llvm.loop.unroll.enable"); +} + // Returns true if the loop has an unroll(disable) pragma. static bool HasUnrollDisablePragma(const Loop *L) { return GetUnrollMetadataForLoop(L, "llvm.loop.unroll.disable"); @@ -644,12 +706,11 @@ static void SetLoopAlreadyUnrolled(Loop *L) { L->setLoopID(NewLoopID); } -bool LoopUnroll::canUnrollCompletely(Loop *L, unsigned Threshold, - unsigned PercentDynamicCostSavedThreshold, - unsigned DynamicCostSavingsDiscount, - uint64_t UnrolledCost, - uint64_t RolledDynamicCost) { - +static bool canUnrollCompletely(Loop *L, unsigned Threshold, + unsigned PercentDynamicCostSavedThreshold, + unsigned DynamicCostSavingsDiscount, + uint64_t UnrolledCost, + uint64_t RolledDynamicCost) { if (Threshold == NoThreshold) { DEBUG(dbgs() << " Can fully unroll, because no threshold is set.\n"); return true; @@ -697,58 +758,13 @@ bool LoopUnroll::canUnrollCompletely(Loop *L, unsigned Threshold, return false; } -unsigned LoopUnroll::selectUnrollCount( - const Loop *L, unsigned TripCount, bool PragmaFullUnroll, - unsigned PragmaCount, const TargetTransformInfo::UnrollingPreferences &UP, - bool &SetExplicitly) { - SetExplicitly = true; - - // User-specified count (either as a command-line option or - // constructor parameter) has highest precedence. - unsigned Count = UserCount ? CurrentCount : 0; - - // If there is no user-specified count, unroll pragmas have the next - // highest precendence. - if (Count == 0) { - if (PragmaCount) { - Count = PragmaCount; - } else if (PragmaFullUnroll) { - Count = TripCount; - } - } - - if (Count == 0) - Count = UP.Count; - - if (Count == 0) { - SetExplicitly = false; - if (TripCount == 0) - // Runtime trip count. - Count = UnrollRuntimeCount; - else - // Conservative heuristic: if we know the trip count, see if we can - // completely unroll (subject to the threshold, checked below); otherwise - // try to find greatest modulo of the trip count which is still under - // threshold value. - Count = TripCount; - } - if (TripCount && Count > TripCount) - return TripCount; - return Count; -} - -bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) { - if (skipOptnoneFunction(L)) - return false; - - Function &F = *L->getHeader()->getParent(); - - LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); - ScalarEvolution *SE = &getAnalysis<ScalarEvolution>(); - const TargetTransformInfo &TTI = - getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); - auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); - +static bool tryToUnrollLoop(Loop *L, DominatorTree &DT, LoopInfo *LI, + ScalarEvolution *SE, const TargetTransformInfo &TTI, + AssumptionCache &AC, bool PreserveLCSSA, + Optional<unsigned> ProvidedCount, + Optional<unsigned> ProvidedThreshold, + Optional<bool> ProvidedAllowPartial, + Optional<bool> ProvidedRuntime) { BasicBlock *Header = L->getHeader(); DEBUG(dbgs() << "Loop Unroll: F[" << Header->getParent()->getName() << "] Loop %" << Header->getName() << "\n"); @@ -757,11 +773,9 @@ bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) { return false; } bool PragmaFullUnroll = HasUnrollFullPragma(L); + bool PragmaEnableUnroll = HasUnrollEnablePragma(L); unsigned PragmaCount = UnrollCountPragmaValue(L); - bool HasPragma = PragmaFullUnroll || PragmaCount > 0; - - TargetTransformInfo::UnrollingPreferences UP; - getUnrollingPreferences(L, TTI, UP); + bool HasPragma = PragmaFullUnroll || PragmaEnableUnroll || PragmaCount > 0; // Find trip count and trip multiple if count is not available unsigned TripCount = 0; @@ -777,11 +791,18 @@ bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) { TripMultiple = SE->getSmallConstantTripMultiple(L, ExitingBlock); } - // Select an initial unroll count. This may be reduced later based - // on size thresholds. - bool CountSetExplicitly; - unsigned Count = selectUnrollCount(L, TripCount, PragmaFullUnroll, - PragmaCount, UP, CountSetExplicitly); + TargetTransformInfo::UnrollingPreferences UP = gatherUnrollingPreferences( + L, TTI, ProvidedThreshold, ProvidedCount, ProvidedAllowPartial, + ProvidedRuntime, PragmaCount, PragmaFullUnroll, PragmaEnableUnroll, + TripCount); + + unsigned Count = UP.Count; + bool CountSetExplicitly = Count != 0; + // Use a heuristic count if we didn't set anything explicitly. + if (!CountSetExplicitly) + Count = TripCount == 0 ? DefaultUnrollRuntimeCount : TripCount; + if (TripCount && Count > TripCount) + Count = TripCount; unsigned NumInlineCandidates; bool notDuplicatable; @@ -803,13 +824,6 @@ bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) { return false; } - unsigned Threshold, PartialThreshold; - unsigned PercentDynamicCostSavedThreshold; - unsigned DynamicCostSavingsDiscount; - selectThresholds(L, HasPragma, UP, Threshold, PartialThreshold, - PercentDynamicCostSavedThreshold, - DynamicCostSavingsDiscount); - // Given Count, TripCount and thresholds determine the type of // unrolling which is to be performed. enum { Full = 0, Partial = 1, Runtime = 2 }; @@ -817,7 +831,7 @@ bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) { if (TripCount && Count == TripCount) { Unrolling = Partial; // If the loop is really small, we don't need to run an expensive analysis. - if (canUnrollCompletely(L, Threshold, 100, DynamicCostSavingsDiscount, + if (canUnrollCompletely(L, UP.Threshold, 100, UP.DynamicCostSavingsDiscount, UnrolledSize, UnrolledSize)) { Unrolling = Full; } else { @@ -825,10 +839,12 @@ bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) { // helps to remove a significant number of instructions. // To check that, run additional analysis on the loop. if (Optional<EstimatedUnrollCost> Cost = analyzeLoopUnrollCost( - L, TripCount, *SE, TTI, Threshold + DynamicCostSavingsDiscount)) - if (canUnrollCompletely(L, Threshold, PercentDynamicCostSavedThreshold, - DynamicCostSavingsDiscount, Cost->UnrolledCost, - Cost->RolledDynamicCost)) { + L, TripCount, DT, *SE, TTI, + UP.Threshold + UP.DynamicCostSavingsDiscount)) + if (canUnrollCompletely(L, UP.Threshold, + UP.PercentDynamicCostSavedThreshold, + UP.DynamicCostSavingsDiscount, + Cost->UnrolledCost, Cost->RolledDynamicCost)) { Unrolling = Full; } } @@ -840,22 +856,22 @@ bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) { // Reduce count based on the type of unrolling and the threshold values. unsigned OriginalCount = Count; - bool AllowRuntime = - (PragmaCount > 0) || (UserRuntime ? CurrentRuntime : UP.Runtime); + bool AllowRuntime = PragmaEnableUnroll || (PragmaCount > 0) || UP.Runtime; // Don't unroll a runtime trip count loop with unroll full pragma. if (HasRuntimeUnrollDisablePragma(L) || PragmaFullUnroll) { AllowRuntime = false; } if (Unrolling == Partial) { - bool AllowPartial = UserAllowPartial ? CurrentAllowPartial : UP.Partial; + bool AllowPartial = PragmaEnableUnroll || UP.Partial; if (!AllowPartial && !CountSetExplicitly) { DEBUG(dbgs() << " will not try to unroll partially because " << "-unroll-allow-partial not given\n"); return false; } - if (PartialThreshold != NoThreshold && UnrolledSize > PartialThreshold) { + if (UP.PartialThreshold != NoThreshold && + UnrolledSize > UP.PartialThreshold) { // Reduce unroll count to be modulo of TripCount for partial unrolling. - Count = (std::max(PartialThreshold, 3u)-2) / (LoopSize-2); + Count = (std::max(UP.PartialThreshold, 3u) - 2) / (LoopSize - 2); while (Count != 0 && TripCount % Count != 0) Count--; } @@ -867,7 +883,7 @@ bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) { } // Reduce unroll count to be the largest power-of-two factor of // the original count which satisfies the threshold limit. - while (Count != 0 && UnrolledSize > PartialThreshold) { + while (Count != 0 && UnrolledSize > UP.PartialThreshold) { Count >>= 1; UnrolledSize = (LoopSize-2) * Count + 2; } @@ -887,23 +903,27 @@ bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) { DebugLoc LoopLoc = L->getStartLoc(); Function *F = Header->getParent(); LLVMContext &Ctx = F->getContext(); - if (PragmaFullUnroll && PragmaCount == 0) { - if (TripCount && Count != TripCount) { - emitOptimizationRemarkMissed( - Ctx, DEBUG_TYPE, *F, LoopLoc, - "Unable to fully unroll loop as directed by unroll(full) pragma " - "because unrolled size is too large."); - } else if (!TripCount) { - emitOptimizationRemarkMissed( - Ctx, DEBUG_TYPE, *F, LoopLoc, - "Unable to fully unroll loop as directed by unroll(full) pragma " - "because loop has a runtime trip count."); - } - } else if (PragmaCount > 0 && Count != OriginalCount) { + if ((PragmaCount > 0) && Count != OriginalCount) { emitOptimizationRemarkMissed( Ctx, DEBUG_TYPE, *F, LoopLoc, "Unable to unroll loop the number of times directed by " "unroll_count pragma because unrolled size is too large."); + } else if (PragmaFullUnroll && !TripCount) { + emitOptimizationRemarkMissed( + Ctx, DEBUG_TYPE, *F, LoopLoc, + "Unable to fully unroll loop as directed by unroll(full) pragma " + "because loop has a runtime trip count."); + } else if (PragmaEnableUnroll && Count != TripCount && Count < 2) { + emitOptimizationRemarkMissed( + Ctx, DEBUG_TYPE, *F, LoopLoc, + "Unable to unroll loop as directed by unroll(enable) pragma because " + "unrolled size is too large."); + } else if ((PragmaFullUnroll || PragmaEnableUnroll) && TripCount && + Count != TripCount) { + emitOptimizationRemarkMissed( + Ctx, DEBUG_TYPE, *F, LoopLoc, + "Unable to fully unroll loop as directed by unroll pragma because " + "unrolled size is too large."); } } @@ -915,8 +935,96 @@ bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) { // Unroll the loop. if (!UnrollLoop(L, Count, TripCount, AllowRuntime, UP.AllowExpensiveTripCount, - TripMultiple, LI, this, &LPM, &AC)) + TripMultiple, LI, SE, &DT, &AC, PreserveLCSSA)) return false; return true; } + +namespace { +class LoopUnroll : public LoopPass { +public: + static char ID; // Pass ID, replacement for typeid + LoopUnroll(Optional<unsigned> Threshold = None, + Optional<unsigned> Count = None, + Optional<bool> AllowPartial = None, Optional<bool> Runtime = None) + : LoopPass(ID), ProvidedCount(Count), ProvidedThreshold(Threshold), + ProvidedAllowPartial(AllowPartial), ProvidedRuntime(Runtime) { + initializeLoopUnrollPass(*PassRegistry::getPassRegistry()); + } + + Optional<unsigned> ProvidedCount; + Optional<unsigned> ProvidedThreshold; + Optional<bool> ProvidedAllowPartial; + Optional<bool> ProvidedRuntime; + + bool runOnLoop(Loop *L, LPPassManager &) override { + if (skipOptnoneFunction(L)) + return false; + + Function &F = *L->getHeader()->getParent(); + + auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); + LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); + ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); + const TargetTransformInfo &TTI = + getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); + auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); + bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID); + + return tryToUnrollLoop(L, DT, LI, SE, TTI, AC, PreserveLCSSA, ProvidedCount, + ProvidedThreshold, ProvidedAllowPartial, + ProvidedRuntime); + } + + /// This transformation requires natural loop information & requires that + /// loop preheaders be inserted into the CFG... + /// + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired<AssumptionCacheTracker>(); + AU.addRequired<DominatorTreeWrapperPass>(); + AU.addRequired<LoopInfoWrapperPass>(); + AU.addPreserved<LoopInfoWrapperPass>(); + AU.addRequiredID(LoopSimplifyID); + AU.addPreservedID(LoopSimplifyID); + AU.addRequiredID(LCSSAID); + AU.addPreservedID(LCSSAID); + AU.addRequired<ScalarEvolutionWrapperPass>(); + AU.addPreserved<ScalarEvolutionWrapperPass>(); + AU.addRequired<TargetTransformInfoWrapperPass>(); + // FIXME: Loop unroll requires LCSSA. And LCSSA requires dom info. + // If loop unroll does not preserve dom info then LCSSA pass on next + // loop will receive invalid dom info. + // For now, recreate dom info, if loop is unrolled. + AU.addPreserved<DominatorTreeWrapperPass>(); + AU.addPreserved<GlobalsAAWrapperPass>(); + } +}; +} + +char LoopUnroll::ID = 0; +INITIALIZE_PASS_BEGIN(LoopUnroll, "loop-unroll", "Unroll loops", false, false) +INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(LoopSimplify) +INITIALIZE_PASS_DEPENDENCY(LCSSA) +INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) +INITIALIZE_PASS_END(LoopUnroll, "loop-unroll", "Unroll loops", false, false) + +Pass *llvm::createLoopUnrollPass(int Threshold, int Count, int AllowPartial, + int Runtime) { + // TODO: It would make more sense for this function to take the optionals + // directly, but that's dangerous since it would silently break out of tree + // callers. + return new LoopUnroll(Threshold == -1 ? None : Optional<unsigned>(Threshold), + Count == -1 ? None : Optional<unsigned>(Count), + AllowPartial == -1 ? None + : Optional<bool>(AllowPartial), + Runtime == -1 ? None : Optional<bool>(Runtime)); +} + +Pass *llvm::createSimpleLoopUnrollPass() { + return llvm::createLoopUnrollPass(-1, -1, 0, 0); +} |
