LLVM  9.0.0svn
Macros | Functions | Variables
LoopUnrollPass.cpp File Reference
#include "llvm/Transforms/Scalar/LoopUnrollPass.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/None.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/BlockFrequencyInfo.h"
#include "llvm/Analysis/CodeMetrics.h"
#include "llvm/Analysis/LazyBlockFrequencyInfo.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/LoopUnrollAnalyzer.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ProfileSummaryInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/PassManager.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Scalar/LoopPassManager.h"
#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Utils/LoopSimplify.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/SizeOpts.h"
#include "llvm/Transforms/Utils/UnrollLoop.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <string>
#include <tuple>
#include <utility>

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "loop-unroll"
 

Functions

static Optional< EstimatedUnrollCost > analyzeLoopUnrollCost (const Loop *L, unsigned TripCount, DominatorTree &DT, ScalarEvolution &SE, const SmallPtrSetImpl< const Value *> &EphValues, const TargetTransformInfo &TTI, unsigned MaxUnrolledLoopSize)
 Figure out if the loop is worth full unrolling. More...
 
static MDNodeGetUnrollMetadataForLoop (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 uint64_t getUnrolledLoopSize (unsigned LoopSize, 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 OnlyWhenForced, bool ForgetAllSCEV, Optional< unsigned > ProvidedCount, Optional< unsigned > ProvidedThreshold, Optional< bool > ProvidedAllowPartial, Optional< bool > ProvidedRuntime, Optional< bool > ProvidedUpperBound, Optional< bool > ProvidedAllowPeeling)
 
template<typename RangeT >
static SmallVector< Loop *, 8 > appendLoopsToWorklist (RangeT &&Loops)
 

Variables

static cl::opt< unsignedUnrollThreshold ("unroll-threshold", cl::Hidden, cl::desc("The cost threshold for loop unrolling"))
 
static cl::opt< unsignedUnrollPartialThreshold ("unroll-partial-threshold", cl::Hidden, cl::desc("The cost threshold for partial loop unrolling"))
 
static cl::opt< unsignedUnrollMaxPercentThresholdBoost ("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< unsignedUnrollMaxIterationsCountToAnalyze ("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< unsignedUnrollCount ("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< unsignedUnrollMaxCount ("unroll-max-count", cl::Hidden, cl::desc("Set the max unroll count for partial and runtime unrolling, for" "testing purposes"))
 
static cl::opt< unsignedUnrollFullMaxCount ("unroll-full-max-count", cl::Hidden, cl::desc("Set the max unroll count for full unrolling, for testing purposes"))
 
static cl::opt< unsignedUnrollPeelCount ("unroll-peel-count", cl::Hidden, cl::desc("Set the unroll peeling count, for testing purposes"))
 
static cl::opt< boolUnrollAllowPartial ("unroll-allow-partial", cl::Hidden, cl::desc("Allows loops to be partially unrolled until " "-unroll-threshold loop size is reached."))
 
static cl::opt< boolUnrollAllowRemainder ("unroll-allow-remainder", cl::Hidden, cl::desc("Allow generation of a loop remainder (extra iterations) " "when unrolling a loop."))
 
static cl::opt< boolUnrollRuntime ("unroll-runtime", cl::ZeroOrMore, cl::Hidden, cl::desc("Unroll loops with run-time trip counts"))
 
static cl::opt< unsignedUnrollMaxUpperBound ("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< unsignedPragmaUnrollThreshold ("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< unsignedFlatLoopTripCountThreshold ("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< boolUnrollAllowPeeling ("unroll-allow-peeling", cl::init(true), cl::Hidden, cl::desc("Allows loops to be peeled when the dynamic " "trip count is known to be low."))
 
static cl::opt< boolUnrollUnrollRemainder ("unroll-remainder", cl::Hidden, cl::desc("Allow the loop remainder to be unrolled."))
 
static cl::opt< boolUnrollRevisitChildLoops ("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 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. More...
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "loop-unroll"

Definition at line 72 of file LoopUnrollPass.cpp.

Referenced by llvm::computeUnrollCount().

Function Documentation

◆ analyzeLoopUnrollCost()

static Optional<EstimatedUnrollCost> analyzeLoopUnrollCost ( const Loop L,
unsigned  TripCount,
DominatorTree DT,
ScalarEvolution SE,
const SmallPtrSetImpl< const Value *> &  EphValues,
const TargetTransformInfo TTI,
unsigned  MaxUnrolledLoopSize 
)
static

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 None.

Definition at line 320 of file LoopUnrollPass.cpp.

References llvm::SmallVectorImpl< T >::append(), assert(), llvm::SmallVectorTemplateCommon< T >::begin(), C, Callee, llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::clear(), llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::clear(), llvm::SmallVectorImpl< T >::clear(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::Value::dump(), llvm::dyn_cast(), llvm::SmallVectorBase::empty(), llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::empty(), llvm::LoopBase< BlockT, LoopT >::empty(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, ValueInfoT, detail::DenseSetPair< ValueT > >, ValueInfoT >::end(), llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, ValueInfoT, detail::DenseSetPair< ValueT > >, ValueInfoT >::find(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::TargetTransformInfo::getUserCost(), I, llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert(), llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, ValueInfoT, detail::DenseSetPair< ValueT > >, ValueInfoT >::insert(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::Loop::isLCSSAForm(), llvm::Loop::isLoopSimplifyForm(), llvm::TargetTransformInfo::isLoweredToCall(), LLVM_DEBUG, llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), llvm::max(), llvm::None, llvm::User::operands(), llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::pop_back_val(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorTemplateBase< T >::push_back(), second, SI, llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::size(), llvm::successors(), UnrollMaxIterationsCountToAnalyze, and llvm::InstVisitor< SubClass, RetTy >::visit().

Referenced by llvm::computeUnrollCount().

◆ appendLoopsToWorklist()

template<typename RangeT >
static SmallVector<Loop *, 8> appendLoopsToWorklist ( RangeT &&  Loops)
static

◆ getFullUnrollBoostingFactor()

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

Definition at line 695 of file LoopUnrollPass.cpp.

References llvm::max().

Referenced by llvm::computeUnrollCount().

◆ getUnrolledLoopSize()

static uint64_t getUnrolledLoopSize ( unsigned  LoopSize,
TargetTransformInfo::UnrollingPreferences UP 
)
static

◆ GetUnrollMetadataForLoop()

static MDNode* GetUnrollMetadataForLoop ( const Loop L,
StringRef  Name 
)
static

◆ HasRuntimeUnrollDisablePragma()

static bool HasRuntimeUnrollDisablePragma ( const Loop L)
static

Definition at line 671 of file LoopUnrollPass.cpp.

References GetUnrollMetadataForLoop().

Referenced by llvm::computeUnrollCount().

◆ HasUnrollEnablePragma()

static bool HasUnrollEnablePragma ( const Loop L)
static

Definition at line 666 of file LoopUnrollPass.cpp.

References GetUnrollMetadataForLoop().

Referenced by llvm::computeUnrollCount().

◆ HasUnrollFullPragma()

static bool HasUnrollFullPragma ( const Loop L)
static

Definition at line 660 of file LoopUnrollPass.cpp.

References GetUnrollMetadataForLoop().

Referenced by llvm::computeUnrollCount().

◆ 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  OnlyWhenForced,
bool  ForgetAllSCEV,
Optional< unsigned ProvidedCount,
Optional< unsigned ProvidedThreshold,
Optional< bool ProvidedAllowPartial,
Optional< bool ProvidedRuntime,
Optional< bool ProvidedUpperBound,
Optional< bool ProvidedAllowPeeling 
)
static

Definition at line 970 of file LoopUnrollPass.cpp.

References llvm::AnalysisUsage::addRequired(), llvm::TargetTransformInfo::UnrollingPreferences::AllowExpensiveTripCount, llvm::TargetTransformInfo::UnrollingPreferences::AllowRemainder, llvm::ApproximateLoopSize(), llvm::TargetTransformInfo::UnrollingPreferences::BEInsns, llvm::CodeMetrics::collectEphemeralValues(), llvm::computeUnrollCount(), llvm::MCID::Convergent, llvm::TargetTransformInfo::UnrollingPreferences::Count, llvm::dbgs(), F(), llvm::TargetTransformInfo::UnrollingPreferences::Force, llvm::FullyUnrolled, llvm::gatherUnrollingPreferences(), llvm::LoopBase< BlockT, LoopT >::getExitingBlock(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::getLoopAnalysisUsage(), llvm::Loop::getLoopID(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Value::getName(), llvm::BasicBlock::getParent(), llvm::PassRegistry::getPassRegistry(), llvm::ScalarEvolution::getSmallConstantMaxTripCount(), llvm::ScalarEvolution::getSmallConstantTripCount(), llvm::ScalarEvolution::getSmallConstantTripMultiple(), llvm::Optional< T >::getValue(), llvm::Function::hasOptSize(), llvm::hasUnrollTransformation(), llvm::Optional< T >::hasValue(), INITIALIZE_PASS_BEGIN, INITIALIZE_PASS_DEPENDENCY, INITIALIZE_PASS_END(), llvm::initializeLoopUnrollPass(), llvm::ScalarEvolution::isBackedgeTakenCountMaxOrZero(), llvm::LoopBase< BlockT, LoopT >::isLoopExiting(), llvm::Loop::isLoopSimplifyForm(), llvm::LCSSAID, LLVM_DEBUG, llvm::LLVMLoopUnrollFollowupAll, llvm::LLVMLoopUnrollFollowupRemainder, llvm::LLVMLoopUnrollFollowupUnrolled, llvm::makeFollowupLoopID(), llvm::LPPassManager::markLoopAsDeleted(), llvm::max(), llvm::None, llvm::TargetTransformInfo::UnrollingPreferences::Partial, llvm::TargetTransformInfo::UnrollingPreferences::PartialThreshold, llvm::TargetTransformInfo::UnrollingPreferences::PeelCount, llvm::TargetTransformInfo::UnrollingPreferences::Runtime, llvm::Loop::setLoopAlreadyUnrolled(), llvm::Loop::setLoopID(), Threshold, llvm::TargetTransformInfo::UnrollingPreferences::Threshold, llvm::SystemZISD::TM, llvm::TM_Disable, llvm::TM_Enable, llvm::Unmodified, llvm::UnrollLoop(), UnrollMaxUpperBound, llvm::TargetTransformInfo::UnrollingPreferences::UnrollRemainder, and llvm::TargetTransformInfo::UnrollingPreferences::UpperBound.

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

◆ UnrollCountPragmaValue()

static unsigned UnrollCountPragmaValue ( const Loop L)
static

Variable Documentation

◆ 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."))
static

◆ NoThreshold

const unsigned NoThreshold = std::numeric_limits<unsigned>::max()
static

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.

Definition at line 166 of file LoopUnrollPass.cpp.

◆ 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."))
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."))
static

◆ UnrollAllowPeeling

cl::opt<bool> UnrollAllowPeeling("unroll-allow-peeling", cl::init(true), cl::Hidden, cl::desc("Allows loops to be peeled when the dynamic " "trip count is known to be low."))
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."))
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"))
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"))
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"))
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"))
static

Referenced by analyzeLoopUnrollCost().

◆ 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."))
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"))
static

◆ UnrollPartialThreshold

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

◆ UnrollPeelCount

cl::opt<unsigned> UnrollPeelCount("unroll-peel-count", cl::Hidden, cl::desc("Set the unroll peeling count, for testing purposes"))
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."))
static

◆ UnrollRuntime

cl::opt<bool> UnrollRuntime("unroll-runtime", cl::ZeroOrMore, 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"))
static

◆ UnrollUnrollRemainder

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