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/CodeMetrics.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/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 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 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, bool PreserveLCSSA, int OptLevel, bool OnlyWhenForced, 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< unsigned >	UnrollThreshold ("unroll-threshold", cl::Hidden, cl::desc("The cost threshold for loop unrolling"))
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< unsigned >	UnrollPeelCount ("unroll-peel-count", cl::Hidden, cl::desc("Set the unroll peeling count, 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::ZeroOrMore, 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 >	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 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 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 70 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 314 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 >::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

Definition at line 1315 of file LoopUnrollPass.cpp.

References llvm::SmallVectorImpl< T >::append(), assert(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::LoopBase< BlockT, LoopT >::begin(), llvm::SmallVectorImpl< T >::clear(), llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::LoopBase< BlockT, LoopT >::end(), Loops, llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T >::push_back().

Referenced by llvm::LoopUnrollPass::run().

getFullUnrollBoostingFactor()

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

static

Definition at line 689 of file LoopUnrollPass.cpp.

References llvm::max().

Referenced by llvm::computeUnrollCount().

getUnrolledLoopSize()

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

static

Definition at line 702 of file LoopUnrollPass.cpp.

References assert(), llvm::TargetTransformInfo::UnrollingPreferences::BEInsns, and llvm::TargetTransformInfo::UnrollingPreferences::Count.

Referenced by llvm::computeUnrollCount().

GetUnrollMetadataForLoop()

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

static

Definition at line 647 of file LoopUnrollPass.cpp.

References llvm::Loop::getLoopID(), and llvm::GetUnrollMetadata().

Referenced by HasRuntimeUnrollDisablePragma(), HasUnrollEnablePragma(), HasUnrollFullPragma(), and UnrollCountPragmaValue().

HasRuntimeUnrollDisablePragma()

static bool HasRuntimeUnrollDisablePragma ( const Loop *  L )

static

Definition at line 665 of file LoopUnrollPass.cpp.

References GetUnrollMetadataForLoop().

Referenced by llvm::computeUnrollCount().

HasUnrollEnablePragma()

static bool HasUnrollEnablePragma ( const Loop *  L )

static

Definition at line 660 of file LoopUnrollPass.cpp.

References GetUnrollMetadataForLoop().

Referenced by llvm::computeUnrollCount().

HasUnrollFullPragma()

static bool HasUnrollFullPragma ( const Loop *  L )

static

Definition at line 654 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, bool  PreserveLCSSA, int  OptLevel, bool  OnlyWhenForced, Optional< unsigned >  ProvidedCount, Optional< unsigned >  ProvidedThreshold, Optional< bool >  ProvidedAllowPartial, Optional< bool >  ProvidedRuntime, Optional< bool >  ProvidedUpperBound, Optional< bool >  ProvidedAllowPeeling  )

static

Definition at line 964 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::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::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

Definition at line 671 of file LoopUnrollPass.cpp.

References assert(), llvm::MDNode::getNumOperands(), llvm::MDNode::getOperand(), and GetUnrollMetadataForLoop().

Referenced by llvm::computeUnrollCount().

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

Referenced by llvm::computeUnrollCount().

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 164 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

Referenced by llvm::computeUnrollCount().

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

Referenced by llvm::gatherUnrollingPreferences().

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

Referenced by llvm::gatherUnrollingPreferences().

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

Referenced by llvm::gatherUnrollingPreferences().

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

Referenced by llvm::computeUnrollCount().

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

Referenced by llvm::gatherUnrollingPreferences().

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

Referenced by llvm::gatherUnrollingPreferences().

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

Referenced by llvm::gatherUnrollingPreferences().

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

Referenced by llvm::gatherUnrollingPreferences(), and tryToUnrollLoop().

UnrollPartialThreshold

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

static

Referenced by llvm::gatherUnrollingPreferences().

UnrollPeelCount

cl::opt<unsigned> UnrollPeelCount("unroll-peel-count", cl::Hidden, cl::desc("Set the unroll peeling count, for testing purposes"))

static

Referenced by llvm::gatherUnrollingPreferences().

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

Referenced by llvm::LoopFullUnrollPass::run().

UnrollRuntime

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

static

Referenced by llvm::gatherUnrollingPreferences().

UnrollThreshold

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

static

Referenced by llvm::gatherUnrollingPreferences().

UnrollUnrollRemainder

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

static

Referenced by llvm::gatherUnrollingPreferences().