LoopUnrollPass.cpp File Reference

#include "llvm/Transforms/Scalar/LoopUnrollPass.h"
#include "ScalarOptions.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/DenseSet.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/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/LoopUnrollAnalyzer.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ProfileSummaryInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/UniformityAnalysis.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/Metadata.h"
#include "llvm/IR/PassManager.h"
#include "llvm/InitializePasses.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/LoopPeel.h"
#include "llvm/Transforms/Utils/LoopSimplify.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
#include "llvm/Transforms/Utils/SizeOpts.h"
#include "llvm/Transforms/Utils/UnrollLoop.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <optional>
#include <string>
#include <tuple>
#include <utility>

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "loop-unroll"

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 bool	hasUnrollFullPragma (const Loop *L)
static bool	hasUnrollEnablePragma (const Loop *L)
static bool	hasRuntimeUnrollDisablePragma (const Loop *L)
static bool	isSCEVUniform (const SCEV *S, UniformityInfo &UI)
	Returns true if the SCEV expression is uniform, i.e., all threads in a convergent execution agree on its value.
static unsigned	unrollCountPragmaValue (const Loop *L)
static unsigned	getFullUnrollBoostingFactor (const EstimatedUnrollCost &Cost, unsigned MaxPercentThresholdBoost)
static std::optional< unsigned >	shouldPragmaUnroll (const ScalarOptions &Opts, Loop *L, const UnrollPragmaInfo &PInfo, const unsigned TripMultiple, const unsigned TripCount, unsigned MaxTripCount, const UnrollCostEstimator UCE, const TargetTransformInfo::UnrollingPreferences &UP, OptimizationRemarkEmitter *ORE)
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, bool PrepareForLTO, 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, UniformityInfo *UI=nullptr, AAResults *AA=nullptr)

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

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "loop-unroll"

Definition at line 75 of file LoopUnrollPass.cpp.

Function Documentation

analyzeLoopUnrollCost()

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 )

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

Definition at line 233 of file LoopUnrollPass.cpp.

References llvm::SmallVectorImpl< T >::append(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::DenseMapBase< StorageT, KeyT, ValueT, KeyInfoT, BucketT >::clear(), llvm::SetVector< T, Vector, Set, N >::clear(), llvm::SmallVectorImpl< T >::clear(), CostKind, llvm::DenseMapBase< StorageT, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::dyn_cast(), llvm::SetVector< T, Vector, Set, N >::empty(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::detail::DenseSetImpl< ValueT, MapTy >::end(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::detail::DenseSetImpl< ValueT, MapTy >::find(), llvm::Instruction::getFunction(), llvm::BasicBlock::getTerminator(), llvm::InstructionCost::getValue(), llvm::Function::hasMinSize(), I, llvm::raw_ostream::indent(), llvm::DenseMapBase< StorageT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::detail::DenseSetImpl< ValueT, MapTy >::insert(), llvm::SetVector< T, Vector, Set, N >::insert(), llvm::isa(), llvm::InstructionCost::isValid(), LLVM_DEBUG, llvm::DenseMapBase< StorageT, 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, llvm::transform(), and llvm::UnrolledInstAnalyzer::visit().

Referenced by shouldFullUnroll().

getFullUnrollBoostingFactor()

unsigned getFullUnrollBoostingFactor ( const EstimatedUnrollCost & Cost, unsigned MaxPercentThresholdBoost )

static

Definition at line 700 of file LoopUnrollPass.cpp.

Referenced by shouldFullUnroll().

hasRuntimeUnrollDisablePragma()

bool hasRuntimeUnrollDisablePragma ( const Loop * L )

static

Definition at line 650 of file LoopUnrollPass.cpp.

References llvm::getUnrollMetadataForLoop().

Referenced by llvm::UnrollPragmaInfo::UnrollPragmaInfo().

hasUnrollEnablePragma()

bool hasUnrollEnablePragma ( const Loop * L )

static

Definition at line 645 of file LoopUnrollPass.cpp.

References llvm::getUnrollMetadataForLoop().

Referenced by llvm::UnrollPragmaInfo::UnrollPragmaInfo().

hasUnrollFullPragma()

bool hasUnrollFullPragma ( const Loop * L )

static

Definition at line 639 of file LoopUnrollPass.cpp.

References llvm::getUnrollMetadataForLoop().

Referenced by llvm::UnrollPragmaInfo::UnrollPragmaInfo().

isSCEVUniform()

bool isSCEVUniform ( const SCEV * S, UniformityInfo & UI )

static

Returns true if the SCEV expression is uniform, i.e., all threads in a convergent execution agree on its value.

Recursively checks operands. Returns false if the SCEV could not be computed.

Definition at line 657 of file LoopUnrollPass.cpp.

References llvm::dyn_cast(), llvm::isa(), isSCEVUniform(), llvm::GenericUniformityInfo< ContextT >::isUniformAtDef(), and llvm::SCEV::operands().

Referenced by isSCEVUniform(), and tryToUnrollLoop().

shouldFullUnroll()

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

Definition at line 802 of file LoopUnrollPass.cpp.

References analyzeLoopUnrollCost(), assert(), llvm::dbgs(), llvm::TargetTransformInfo::UnrollingPreferences::FullUnrollMaxCount, getFullUnrollBoostingFactor(), llvm::UnrollCostEstimator::getUnrolledLoopSize(), LLVM_DEBUG, llvm::TargetTransformInfo::UnrollingPreferences::MaxIterationsCountToAnalyze, llvm::TargetTransformInfo::UnrollingPreferences::MaxPercentThresholdBoost, llvm::TargetTransformInfo::UnrollingPreferences::Threshold, and uint64_t.

Referenced by llvm::computeUnrollCount().

shouldPartialUnroll()

std::optional< unsigned > shouldPartialUnroll ( const unsigned LoopSize, const unsigned TripCount, const UnrollCostEstimator UCE, const TargetTransformInfo::UnrollingPreferences & UP )

static

Definition at line 852 of file LoopUnrollPass.cpp.

References llvm::TargetTransformInfo::UnrollingPreferences::AllowRemainder, llvm::TargetTransformInfo::UnrollingPreferences::BEInsns, llvm::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()

std::optional< unsigned > shouldPragmaUnroll ( const ScalarOptions & Opts, Loop * L, const UnrollPragmaInfo & PInfo, const unsigned TripMultiple, const unsigned TripCount, unsigned MaxTripCount, const UnrollCostEstimator UCE, const TargetTransformInfo::UnrollingPreferences & UP, OptimizationRemarkEmitter * ORE )

static

Definition at line 713 of file LoopUnrollPass.cpp.

References llvm::TargetTransformInfo::UnrollingPreferences::AllowRemainder, llvm::dbgs(), DEBUG_TYPE, llvm::OptimizationRemarkEmitter::emit(), llvm::UnrollCostEstimator::getUnrolledLoopSize(), LLVM_DEBUG, llvm::TargetTransformInfo::UnrollingPreferences::MaxUpperBound, llvm::UnrollPragmaInfo::PragmaCount, llvm::UnrollPragmaInfo::PragmaEnableUnroll, llvm::UnrollPragmaInfo::PragmaFullUnroll, llvm::TargetTransformInfo::UnrollingPreferences::Threshold, and llvm::UnrollPragmaInfo::UserUnrollCount.

Referenced by llvm::computeUnrollCount().

tryToUnrollLoop()

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, bool PrepareForLTO, 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, UniformityInfo * UI = nullptr, AAResults * AA = nullptr )

static

Definition at line 1114 of file LoopUnrollPass.cpp.

References llvm::TargetTransformInfo::UnrollingPreferences::AddAdditionalAccumulators, llvm::UnrollLoopOptions::AddAdditionalAccumulators, 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::Count, llvm::UnrollLoopOptions::Count, llvm::dbgs(), DEBUG_TYPE, llvm::OptimizationRemarkEmitter::emit(), llvm::UnrollPragmaInfo::ExplicitUnroll, llvm::TargetTransformInfo::UnrollingPreferences::Force, llvm::UnrollLoopOptions::Force, llvm::UnrollLoopOptions::ForgetAllSCEV, llvm::FullyUnrolled, llvm::gatherPeelingPreferences(), llvm::gatherUnrollingPreferences(), llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::getLoopConvergenceHeart(), llvm::UnrollCostEstimator::getRolledLoopSize(), llvm::ScalarEvolution::getSmallConstantMaxTripCount(), llvm::ScalarEvolution::getSmallConstantTripCount(), llvm::ScalarEvolution::getSmallConstantTripMultiple(), llvm::hasUnrollAndJamTransformation(), llvm::hasUnrollTransformation(), llvm::UnrollLoopOptions::Heart, llvm::ScalarEvolution::isBackedgeTakenCountMaxOrZero(), isSCEVUniform(), 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::TargetTransformInfo::PeelingPreferences::PeelLast, llvm::peelLoop(), llvm::TargetTransformInfo::PeelingPreferences::PeelProfiledIterations, llvm::UnrollPragmaInfo::PragmaCount, llvm::UnrollPragmaInfo::PragmaFullUnroll, llvm::TargetTransformInfo::UnrollingPreferences::Runtime, llvm::UnrollLoopOptions::Runtime, llvm::TargetTransformInfo::UnrollingPreferences::RuntimeUnrollMultiExit, llvm::UnrollLoopOptions::RuntimeUnrollMultiExit, 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::LoopFullUnrollPass::run(), and llvm::LoopUnrollPass::run().

unrollCountPragmaValue()

unsigned unrollCountPragmaValue ( const Loop * L )

static

Definition at line 673 of file LoopUnrollPass.cpp.

References assert(), llvm::Count, llvm::mdconst::extract(), llvm::MDNode::getNumOperands(), llvm::MDNode::getOperand(), and llvm::getUnrollMetadataForLoop().

Referenced by llvm::UnrollPragmaInfo::UnrollPragmaInfo().

Variable Documentation

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 84 of file LoopUnrollPass.cpp.

Referenced by shouldPartialUnroll().