LLVM: lib/Transforms/Scalar/LoopUnrollPass.cpp File Reference (original) (raw)

Go to the source code of this file.

Functions
static std::optional< EstimatedUnrollCost > analyzeLoopUnrollCost (const Loop *L, unsigned TripCount, DominatorTree &DT, ScalarEvolution &SE, const SmallPtrSetImpl< const Value * > &EphValues, const TargetTransformInfo &TTI, unsigned MaxUnrolledLoopSize, unsigned MaxIterationsCountToAnalyze)
Figure out if the loop is worth full unrolling.
static MDNode * getUnrollMetadataForLoop (const Loop *L, StringRef Name)
static bool hasUnrollFullPragma (const Loop *L)
static bool hasUnrollEnablePragma (const Loop *L)
static bool hasRuntimeUnrollDisablePragma (const Loop *L)
static unsigned unrollCountPragmaValue (const Loop *L)
static unsigned getFullUnrollBoostingFactor (const EstimatedUnrollCost &Cost, unsigned MaxPercentThresholdBoost)
static std::optional< unsigned > shouldPragmaUnroll (Loop *L, const PragmaInfo &PInfo, const unsigned TripMultiple, const unsigned TripCount, unsigned MaxTripCount, const UnrollCostEstimator UCE, const TargetTransformInfo::UnrollingPreferences &UP)
static std::optional< unsigned > shouldFullUnroll (Loop *L, const TargetTransformInfo &TTI, DominatorTree &DT, ScalarEvolution &SE, const SmallPtrSetImpl< const Value * > &EphValues, const unsigned FullUnrollTripCount, const UnrollCostEstimator UCE, const TargetTransformInfo::UnrollingPreferences &UP)
static std::optional< unsigned > shouldPartialUnroll (const unsigned LoopSize, const unsigned TripCount, const UnrollCostEstimator UCE, const TargetTransformInfo::UnrollingPreferences &UP)
static LoopUnrollResult tryToUnrollLoop (Loop *L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE, const TargetTransformInfo &TTI, AssumptionCache &AC, OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, bool PreserveLCSSA, int OptLevel, bool OnlyFullUnroll, bool OnlyWhenForced, bool ForgetAllSCEV, std::optional< unsigned > ProvidedCount, std::optional< unsigned > ProvidedThreshold, std::optional< bool > ProvidedAllowPartial, std::optional< bool > ProvidedRuntime, std::optional< bool > ProvidedUpperBound, std::optional< bool > ProvidedAllowPeeling, std::optional< bool > ProvidedAllowProfileBasedPeeling, std::optional< unsigned > ProvidedFullUnrollMaxCount, AAResults *AA=nullptr)
Variables
static cl::opt< unsigned > UnrollThreshold ("unroll-threshold", cl::Hidden, cl::desc("The cost threshold for loop unrolling"))
static cl::opt< unsigned > UnrollOptSizeThreshold ("unroll-optsize-threshold", cl::init(0), cl::Hidden, cl::desc("The cost threshold for loop unrolling when optimizing for " "size"))
static cl::opt< unsigned > UnrollPartialThreshold ("unroll-partial-threshold", cl::Hidden, cl::desc("The cost threshold for partial loop unrolling"))
static cl::opt< unsigned > UnrollMaxPercentThresholdBoost ("unroll-max-percent-threshold-boost", cl::init(400), cl::Hidden, cl::desc("The maximum 'boost' (represented as a percentage >= 100) applied " "to the threshold when aggressively unrolling a loop due to the " "dynamic cost savings. If completely unrolling a loop will reduce " "the total runtime from X to Y, we boost the loop unroll " "threshold to DefaultThreshold*std::min(MaxPercentThresholdBoost, " "X/Y). This limit avoids excessive code bloat."))
static cl::opt< unsigned > UnrollMaxIterationsCountToAnalyze ("unroll-max-iteration-count-to-analyze", cl::init(10), cl::Hidden, cl::desc("Don't allow loop unrolling to simulate more than this number of " "iterations when checking full unroll profitability"))
static cl::opt< unsigned > 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< unsigned > UnrollMaxCount ("unroll-max-count", cl::Hidden, cl::desc("Set the max unroll count for partial and runtime unrolling, for" "testing purposes"))
static cl::opt< unsigned > UnrollFullMaxCount ("unroll-full-max-count", cl::Hidden, cl::desc("Set the max unroll count for full unrolling, for testing purposes"))
static cl::opt< bool > 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 > UnrollAllowRemainder ("unroll-allow-remainder", cl::Hidden, cl::desc("Allow generation of a loop remainder (extra iterations) " "when unrolling a loop."))
static cl::opt< bool > UnrollRuntime ("unroll-runtime", cl::Hidden, cl::desc("Unroll loops with run-time trip counts"))
static cl::opt< unsigned > UnrollMaxUpperBound ("unroll-max-upperbound", cl::init(8), cl::Hidden, cl::desc("The max of trip count upper bound that is considered in unrolling"))
static cl::opt< unsigned > 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."))
static cl::opt< unsigned > FlatLoopTripCountThreshold ("flat-loop-tripcount-threshold", cl::init(5), cl::Hidden, cl::desc("If the runtime tripcount for the loop is lower than the " "threshold, the loop is considered as flat and will be less " "aggressively unrolled."))
static cl::opt< bool > UnrollUnrollRemainder ("unroll-remainder", cl::Hidden, cl::desc("Allow the loop remainder to be unrolled."))
static cl::opt< bool > UnrollRevisitChildLoops ("unroll-revisit-child-loops", cl::Hidden, cl::desc("Enqueue and re-visit child loops in the loop PM after unrolling. " "This shouldn't typically be needed as child loops (or their " "clones) were already visited."))
static cl::opt< unsigned > UnrollThresholdAggressive ("unroll-threshold-aggressive", cl::init(300), cl::Hidden, cl::desc("Threshold (max size of unrolled loop) to use in aggressive (O3) " "optimizations"))
static cl::opt< unsigned > UnrollThresholdDefault ("unroll-threshold-default", cl::init(150), cl::Hidden, cl::desc("Default threshold (max size of unrolled " "loop), used in all but O3 optimizations"))
static cl::opt< unsigned > PragmaUnrollFullMaxIterations ("pragma-unroll-full-max-iterations", cl::init(1 '000 '000), cl::Hidden, cl::desc("Maximum allowed iterations to unroll under pragma unroll full."))
static const unsigned NoThreshold = std::numeric_limits<unsigned>::max()
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.

DEBUG_TYPE

#define DEBUG_TYPE "loop-unroll"

analyzeLoopUnrollCost()

Figure out if the loop is worth full unrolling.

Complete loop unrolling can make some loads constant, and we need to know if that would expose any further optimization opportunities. This routine estimates this optimization. It computes cost of unrolled loop (UnrolledCost) and dynamic cost of the original loop (RolledDynamicCost). By dynamic cost we mean that we won't count costs of blocks that are known not to be executed (i.e. if we have a branch in the loop and we know that at the given iteration its condition would be resolved to true, we won't add up the cost of the 'false'-block).

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 std::nullopt.

Definition at line 356 of file LoopUnrollPass.cpp.

References llvm::SmallVectorImpl< T >::append(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::clear(), llvm::SetVector< T, Vector, Set, N >::clear(), llvm::SmallVectorImpl< T >::clear(), CostKind, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::SetVector< T, Vector, Set, N >::empty(), llvm::SmallVectorBase< Size_T >::empty(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::end(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::find(), llvm::Instruction::getFunction(), llvm::TargetTransformInfo::getInstructionCost(), llvm::BasicBlock::getTerminator(), llvm::InstructionCost::getValue(), llvm::Function::hasMinSize(), I, Idx, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::SetVector< T, Vector, Set, N >::insert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::TargetTransformInfo::isLoweredToCall(), llvm::InstructionCost::isValid(), LLVM_DEBUG, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), Operands, PHI, llvm::SetVector< T, Vector, Set, N >::pop_back_val(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SetVector< T, Vector, Set, N >::size(), llvm::successors(), llvm::TargetTransformInfo::TCK_CodeSize, llvm::TargetTransformInfo::TCK_SizeAndLatency, and llvm::transform().

Referenced by shouldFullUnroll().

getFullUnrollBoostingFactor()

static unsigned getFullUnrollBoostingFactor ( const EstimatedUnrollCost & Cost, unsigned MaxPercentThresholdBoost ) static

getUnrollMetadataForLoop()

hasRuntimeUnrollDisablePragma()

static bool hasRuntimeUnrollDisablePragma ( const Loop * L) static

hasUnrollEnablePragma()

hasUnrollFullPragma()

shouldFullUnroll()

shouldPartialUnroll()

Definition at line 868 of file LoopUnrollPass.cpp.

References llvm::TargetTransformInfo::UnrollingPreferences::AllowRemainder, llvm::TargetTransformInfo::UnrollingPreferences::BEInsns, llvm::count(), llvm::TargetTransformInfo::UnrollingPreferences::Count, llvm::dbgs(), llvm::TargetTransformInfo::UnrollingPreferences::DefaultUnrollRuntimeCount, llvm::UnrollCostEstimator::getUnrolledLoopSize(), LLVM_DEBUG, llvm::TargetTransformInfo::UnrollingPreferences::MaxCount, NoThreshold, llvm::TargetTransformInfo::UnrollingPreferences::Partial, and llvm::TargetTransformInfo::UnrollingPreferences::PartialThreshold.

Referenced by llvm::computeUnrollCount().

shouldPragmaUnroll()

tryToUnrollLoop()

static LoopUnrollResult tryToUnrollLoop ( Loop * L, DominatorTree & DT, LoopInfo * LI, ScalarEvolution & SE, const TargetTransformInfo & TTI, AssumptionCache & AC, OptimizationRemarkEmitter & ORE, BlockFrequencyInfo * BFI, ProfileSummaryInfo * PSI, bool PreserveLCSSA, int OptLevel, bool OnlyFullUnroll, bool OnlyWhenForced, bool ForgetAllSCEV, std::optional< unsigned > ProvidedCount, std::optional< unsigned > ProvidedThreshold, std::optional< bool > ProvidedAllowPartial, std::optional< bool > ProvidedRuntime, std::optional< bool > ProvidedUpperBound, std::optional< bool > ProvidedAllowPeeling, std::optional< bool > ProvidedAllowProfileBasedPeeling, std::optional< unsigned > ProvidedFullUnrollMaxCount, AAResults * AA = nullptr ) static

Definition at line 1157 of file LoopUnrollPass.cpp.

References llvm::TargetTransformInfo::UnrollingPreferences::AllowExpensiveTripCount, llvm::UnrollLoopOptions::AllowExpensiveTripCount, llvm::TargetTransformInfo::UnrollingPreferences::AllowRemainder, assert(), llvm::TargetTransformInfo::UnrollingPreferences::BEInsns, llvm::UnrollCostEstimator::canUnroll(), llvm::CodeMetrics::collectEphemeralValues(), llvm::computeUnrollCount(), llvm::UnrollCostEstimator::ConvergenceAllowsRuntime, llvm::TargetTransformInfo::UnrollingPreferences::Count, llvm::UnrollLoopOptions::Count, llvm::dbgs(), DEBUG_TYPE, llvm::OptimizationRemarkEmitter::emit(), llvm::TargetTransformInfo::UnrollingPreferences::Force, llvm::UnrollLoopOptions::Force, llvm::UnrollLoopOptions::ForgetAllSCEV, llvm::FullyUnrolled, llvm::gatherPeelingPreferences(), llvm::gatherUnrollingPreferences(), llvm::getLoopConvergenceHeart(), llvm::UnrollCostEstimator::getRolledLoopSize(), llvm::ScalarEvolution::getSmallConstantMaxTripCount(), llvm::ScalarEvolution::getSmallConstantTripCount(), llvm::ScalarEvolution::getSmallConstantTripMultiple(), llvm::hasUnrollAndJamTransformation(), llvm::hasUnrollTransformation(), llvm::UnrollLoopOptions::Heart, llvm::ScalarEvolution::isBackedgeTakenCountMaxOrZero(), LLVM_DEBUG, llvm::LLVMLoopUnrollFollowupAll, llvm::LLVMLoopUnrollFollowupRemainder, llvm::LLVMLoopUnrollFollowupUnrolled, llvm::makeFollowupLoopID(), llvm::UnrollCostEstimator::NumInlineCandidates, llvm::TargetTransformInfo::UnrollingPreferences::Partial, llvm::PartiallyUnrolled, llvm::TargetTransformInfo::UnrollingPreferences::PartialThreshold, llvm::TargetTransformInfo::PeelingPreferences::PeelCount, llvm::peelLoop(), llvm::TargetTransformInfo::PeelingPreferences::PeelProfiledIterations, llvm::TargetTransformInfo::UnrollingPreferences::Runtime, llvm::UnrollLoopOptions::Runtime, llvm::TargetTransformInfo::UnrollingPreferences::SCEVExpansionBudget, llvm::UnrollLoopOptions::SCEVExpansionBudget, llvm::Loop::setLoopID(), llvm::simplifyLoopAfterUnroll(), llvm::TargetTransformInfo::UnrollingPreferences::Threshold, llvm::TM_Disable, llvm::TM_Enable, llvm::TM_ForcedByUser, llvm::Unmodified, llvm::UnrollLoop(), llvm::TargetTransformInfo::UnrollingPreferences::UnrollRemainder, and llvm::UnrollLoopOptions::UnrollRemainder.

Referenced by llvm::LoopUnrollPass::run(), and llvm::LoopFullUnrollPass::run().

unrollCountPragmaValue()

FlatLoopTripCountThreshold

cl::opt< unsigned > FlatLoopTripCountThreshold("flat-loop-tripcount-threshold", cl::init(5), cl::Hidden, cl::desc("If the runtime tripcount for the loop is lower than the " "threshold, the loop is considered as flat and will be less " "aggressively unrolled.")) ( "flat-loop-tripcount-threshold" , cl::init(5) , cl::Hidden , cl::desc("If the runtime tripcount for the loop is lower than the " "threshold, the loop is considered as flat and will be less " "aggressively unrolled.") ) static

NoThreshold

PragmaUnrollFullMaxIterations

cl::opt< unsigned > PragmaUnrollFullMaxIterations("pragma-unroll-full-max-iterations", cl::init(1 '000 '000), cl::Hidden, cl::desc("Maximum allowed iterations to unroll under pragma unroll full.")) ( "pragma-unroll-full-max-iterations" , cl::init(1 '000 '000) , cl::Hidden , cl::desc("Maximum allowed iterations to unroll under pragma unroll full.") ) static

PragmaUnrollThreshold

cl::opt< unsigned > 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.")) ( "pragma-unroll-threshold" , cl::init(16 *1024) , cl::Hidden , cl::desc("Unrolled size limit for loops with an unroll(full) or " "unroll_count pragma.") ) static

UnrollAllowPartial

cl::opt< bool > UnrollAllowPartial("unroll-allow-partial", cl::Hidden, cl::desc("Allows loops to be partially unrolled until " "-unroll-threshold loop size is reached.")) ( "unroll-allow-partial" , cl::Hidden , cl::desc("Allows loops to be partially unrolled until " "-unroll-threshold loop size is reached.") ) static

UnrollAllowRemainder

cl::opt< bool > UnrollAllowRemainder("unroll-allow-remainder", cl::Hidden, cl::desc("Allow generation of a loop remainder (extra iterations) " "when unrolling a loop.")) ( "unroll-allow-remainder" , cl::Hidden , cl::desc("Allow generation of a loop remainder (extra iterations) " "when unrolling a loop.") ) static

UnrollCount

cl::opt< unsigned > UnrollCount("unroll-count", cl::Hidden, cl::desc("Use this unroll count for all loops including those with " "unroll_count pragma values, for testing purposes")) ( "unroll-count" , cl::Hidden , cl::desc("Use this unroll count for all loops including those with " "unroll_count pragma values, for testing purposes") ) static

UnrollFullMaxCount

cl::opt< unsigned > UnrollFullMaxCount("unroll-full-max-count", cl::Hidden, cl::desc( "Set the max unroll count for full unrolling, for testing purposes")) ( "unroll-full-max-count" , cl::Hidden , cl::desc( "Set the max unroll count for full unrolling, for testing purposes") ) static

UnrollMaxCount

cl::opt< unsigned > UnrollMaxCount("unroll-max-count", cl::Hidden, cl::desc("Set the max unroll count for partial and runtime unrolling, for" "testing purposes")) ( "unroll-max-count" , cl::Hidden , cl::desc("Set the max unroll count for partial and runtime unrolling, for" "testing purposes") ) static

UnrollMaxIterationsCountToAnalyze

cl::opt< unsigned > UnrollMaxIterationsCountToAnalyze("unroll-max-iteration-count-to-analyze", cl::init(10), cl::Hidden, cl::desc("Don't allow loop unrolling to simulate more than this number of " "iterations when checking full unroll profitability")) ( "unroll-max-iteration-count-to-analyze" , cl::init(10) , cl::Hidden , cl::desc("Don't allow loop unrolling to simulate more than this number of " "iterations when checking full unroll profitability") ) static

UnrollMaxPercentThresholdBoost

cl::opt< unsigned > UnrollMaxPercentThresholdBoost("unroll-max-percent-threshold-boost", cl::init(400), cl::Hidden, cl::desc("The maximum 'boost' (represented as a percentage >= 100) applied " "to the threshold when aggressively unrolling a loop due to the " "dynamic cost savings. If completely unrolling a loop will reduce " "the total runtime from X to Y, we boost the loop unroll " "threshold to DefaultThreshold*std::min(MaxPercentThresholdBoost, " "X/Y). This limit avoids excessive code bloat.")) ( "unroll-max-percent-threshold-boost" , cl::init(400) , cl::Hidden , cl::desc("The maximum 'boost' (represented as a percentage >= 100) applied " "to the threshold when aggressively unrolling a loop due to the " "dynamic cost savings. If completely unrolling a loop will reduce " "the total runtime from X to Y, we boost the loop unroll " "threshold to DefaultThreshold*std::min(MaxPercentThresholdBoost, " "X/Y). This limit avoids excessive code bloat.") ) static

UnrollMaxUpperBound

cl::opt< unsigned > UnrollMaxUpperBound("unroll-max-upperbound", cl::init(8), cl::Hidden, cl::desc( "The max of trip count upper bound that is considered in unrolling")) ( "unroll-max-upperbound" , cl::init(8) , cl::Hidden , cl::desc( "The max of trip count upper bound that is considered in unrolling") ) static

UnrollOptSizeThreshold

cl::opt< unsigned > UnrollOptSizeThreshold("unroll-optsize-threshold", cl::init(0), cl::Hidden, cl::desc("The cost threshold for loop unrolling when optimizing for " "size")) ( "unroll-optsize-threshold" , cl::init(0) , cl::Hidden , cl::desc("The cost threshold for loop unrolling when optimizing for " "size") ) static

UnrollPartialThreshold

cl::opt< unsigned > UnrollPartialThreshold("unroll-partial-threshold", cl::Hidden, cl::desc("The cost threshold for partial loop unrolling")) ( "unroll-partial-threshold" , cl::Hidden , cl::desc("The cost threshold for partial loop unrolling") ) static

UnrollRevisitChildLoops

cl::opt< bool > UnrollRevisitChildLoops("unroll-revisit-child-loops", cl::Hidden, cl::desc("Enqueue and re-visit child loops in the loop PM after unrolling. " "This shouldn't typically be needed as child loops (or their " "clones) were already visited.")) ( "unroll-revisit-child-loops" , cl::Hidden , cl::desc("Enqueue and re-visit child loops in the loop PM after unrolling. " "This shouldn't typically be needed as child loops (or their " "clones) were already visited.") ) static

UnrollRuntime

cl::opt< bool > UnrollRuntime("unroll-runtime", cl::Hidden, cl::desc("Unroll loops with run-time trip counts")) ( "unroll-runtime" , cl::Hidden , cl::desc("Unroll loops with run-time trip counts") ) static

UnrollThreshold

cl::opt< unsigned > UnrollThreshold("unroll-threshold", cl::Hidden, cl::desc("The cost threshold for loop unrolling")) ( "unroll-threshold" , cl::Hidden , cl::desc("The cost threshold for loop unrolling") ) static

UnrollThresholdAggressive

cl::opt< unsigned > UnrollThresholdAggressive("unroll-threshold-aggressive", cl::init(300), cl::Hidden, cl::desc("Threshold (max size of unrolled loop) to use in aggressive (O3) " "optimizations")) ( "unroll-threshold-aggressive" , cl::init(300) , cl::Hidden , cl::desc("Threshold (max size of unrolled loop) to use in aggressive (O3) " "optimizations") ) static

UnrollThresholdDefault

cl::opt< unsigned > UnrollThresholdDefault("unroll-threshold-default", cl::init(150), cl::Hidden, cl::desc("Default threshold (max size of unrolled " "loop), used in all but O3 optimizations")) ( "unroll-threshold-default" , cl::init(150) , cl::Hidden , cl::desc("Default threshold (max size of unrolled " "loop), used in all but O3 optimizations") ) static

UnrollUnrollRemainder

cl::opt< bool > UnrollUnrollRemainder("unroll-remainder", cl::Hidden, cl::desc("Allow the loop remainder to be unrolled.")) ( "unroll-remainder" , cl::Hidden , cl::desc("Allow the loop remainder to be unrolled.") ) static