LLVM 20.0.0git
|
#include "llvm/Transforms/Scalar/LoopUnrollPass.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/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/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 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. | |
#define DEBUG_TYPE "loop-unroll" |
Definition at line 74 of file LoopUnrollPass.cpp.
|
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).
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().
|
static |
Definition at line 784 of file LoopUnrollPass.cpp.
Referenced by shouldFullUnroll().
Definition at line 742 of file LoopUnrollPass.cpp.
References llvm::GetUnrollMetadata(), and Name.
Definition at line 760 of file LoopUnrollPass.cpp.
References getUnrollMetadataForLoop().
Referenced by llvm::computeUnrollCount().
Definition at line 755 of file LoopUnrollPass.cpp.
References getUnrollMetadataForLoop().
Referenced by llvm::computeUnrollCount().
Definition at line 749 of file LoopUnrollPass.cpp.
References getUnrollMetadataForLoop().
Referenced by llvm::computeUnrollCount().
|
static |
Definition at line 837 of file LoopUnrollPass.cpp.
References analyzeLoopUnrollCost(), assert(), llvm::TargetTransformInfo::UnrollingPreferences::FullUnrollMaxCount, getFullUnrollBoostingFactor(), llvm::UnrollCostEstimator::getUnrolledLoopSize(), llvm::TargetTransformInfo::UnrollingPreferences::MaxIterationsCountToAnalyze, llvm::TargetTransformInfo::UnrollingPreferences::MaxPercentThresholdBoost, and llvm::TargetTransformInfo::UnrollingPreferences::Threshold.
Referenced by llvm::computeUnrollCount().
|
static |
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().
|
static |
Definition at line 797 of file LoopUnrollPass.cpp.
References llvm::TargetTransformInfo::UnrollingPreferences::AllowRemainder, llvm::dbgs(), llvm::UnrollCostEstimator::getUnrolledLoopSize(), LLVM_DEBUG, llvm::TargetTransformInfo::UnrollingPreferences::MaxUpperBound, PragmaUnrollFullMaxIterations, llvm::TargetTransformInfo::UnrollingPreferences::Threshold, and UnrollCount.
Referenced by llvm::computeUnrollCount().
|
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().
Definition at line 766 of file LoopUnrollPass.cpp.
References assert(), llvm::MDNode::getNumOperands(), llvm::MDNode::getOperand(), and getUnrollMetadataForLoop().
Referenced by llvm::computeUnrollCount().
|
static |
Referenced by llvm::computeUnrollCount().
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 185 of file LoopUnrollPass.cpp.
Referenced by llvm::computeUnrollCount(), and shouldPartialUnroll().
|
static |
Referenced by shouldPragmaUnroll().
|
static |
Referenced by llvm::computeUnrollCount().
|
static |
Referenced by llvm::gatherUnrollingPreferences().
|
static |
Referenced by llvm::gatherUnrollingPreferences().
|
static |
Referenced by llvm::computeUnrollCount(), llvm::ARMTTIImpl::getUnrollingPreferences(), and shouldPragmaUnroll().
|
static |
Referenced by llvm::gatherUnrollingPreferences().
|
static |
Referenced by llvm::gatherUnrollingPreferences().
|
static |
Referenced by llvm::gatherUnrollingPreferences().
|
static |
Referenced by llvm::gatherUnrollingPreferences().
|
static |
Referenced by llvm::gatherUnrollingPreferences().
|
static |
Referenced by llvm::gatherUnrollingPreferences().
|
static |
Referenced by llvm::gatherUnrollingPreferences().
|
static |
Referenced by llvm::LoopFullUnrollPass::run().
|
static |
Referenced by llvm::gatherUnrollingPreferences().
|
static |
Referenced by llvm::gatherUnrollingPreferences().
|
static |
Referenced by llvm::gatherUnrollingPreferences().
|
static |
Referenced by llvm::gatherUnrollingPreferences().
|
static |
Referenced by llvm::gatherUnrollingPreferences().