LLVM 19.0.0git
Macros | Functions | Variables
LoopStrengthReduce.cpp File Reference
#include "llvm/Transforms/Scalar/LoopStrengthReduce.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallBitVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/IVUsers.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ScalarEvolutionNormalization.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/BinaryFormat/Dwarf.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/GlobalValue.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <utility>

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "loop-reduce"
 

Functions

 STATISTIC (NumTermFold, "Number of terminating condition fold recognized and performed")
 
static void DoInitialMatch (const SCEV *S, Loop *L, SmallVectorImpl< const SCEV * > &Good, SmallVectorImpl< const SCEV * > &Bad, ScalarEvolution &SE)
 Recursion helper for initialMatch.
 
static bool containsAddRecDependentOnLoop (const SCEV *S, const Loop &L)
 
static bool isAddRecSExtable (const SCEVAddRecExpr *AR, ScalarEvolution &SE)
 Return true if the given addrec can be sign-extended without changing its value.
 
static bool isAddSExtable (const SCEVAddExpr *A, ScalarEvolution &SE)
 Return true if the given add can be sign-extended without changing its value.
 
static bool isMulSExtable (const SCEVMulExpr *M, ScalarEvolution &SE)
 Return true if the given mul can be sign-extended without changing its value.
 
static const SCEVgetExactSDiv (const SCEV *LHS, const SCEV *RHS, ScalarEvolution &SE, bool IgnoreSignificantBits=false)
 Return an expression for LHS /s RHS, if it can be determined and if the remainder is known to be zero, or null otherwise.
 
static int64_t ExtractImmediate (const SCEV *&S, ScalarEvolution &SE)
 If S involves the addition of a constant integer value, return that integer value, and mutate S to point to a new SCEV with that value excluded.
 
static GlobalValueExtractSymbol (const SCEV *&S, ScalarEvolution &SE)
 If S involves the addition of a GlobalValue address, return that symbol, and mutate S to point to a new SCEV with that value excluded.
 
static bool isAddressUse (const TargetTransformInfo &TTI, Instruction *Inst, Value *OperandVal)
 Returns true if the specified instruction is using the specified value as an address.
 
static MemAccessTy getAccessType (const TargetTransformInfo &TTI, Instruction *Inst, Value *OperandVal)
 Return the type of the memory being accessed.
 
static bool isExistingPhi (const SCEVAddRecExpr *AR, ScalarEvolution &SE)
 Return true if this AddRec is already a phi in its loop.
 
static bool isHighCostExpansion (const SCEV *S, SmallPtrSetImpl< const SCEV * > &Processed, ScalarEvolution &SE)
 Check if expanding this expression is likely to incur significant cost.
 
static bool isAMCompletelyFolded (const TargetTransformInfo &TTI, const LSRUse &LU, const Formula &F)
 Check if the addressing mode defined by F is completely folded in LU at isel time.
 
static InstructionCost getScalingFactorCost (const TargetTransformInfo &TTI, const LSRUse &LU, const Formula &F, const Loop &L)
 
static bool isAMCompletelyFolded (const TargetTransformInfo &TTI, LSRUse::KindType Kind, MemAccessTy AccessTy, GlobalValue *BaseGV, int64_t BaseOffset, bool HasBaseReg, int64_t Scale, Instruction *Fixup=nullptr)
 
static unsigned getSetupCost (const SCEV *Reg, unsigned Depth)
 
static bool isAMCompletelyFolded (const TargetTransformInfo &TTI, int64_t MinOffset, int64_t MaxOffset, LSRUse::KindType Kind, MemAccessTy AccessTy, GlobalValue *BaseGV, int64_t BaseOffset, bool HasBaseReg, int64_t Scale)
 
static bool isAMCompletelyFolded (const TargetTransformInfo &TTI, int64_t MinOffset, int64_t MaxOffset, LSRUse::KindType Kind, MemAccessTy AccessTy, const Formula &F, const Loop &L)
 
static bool isLegalUse (const TargetTransformInfo &TTI, int64_t MinOffset, int64_t MaxOffset, LSRUse::KindType Kind, MemAccessTy AccessTy, GlobalValue *BaseGV, int64_t BaseOffset, bool HasBaseReg, int64_t Scale)
 Test whether we know how to expand the current formula.
 
static bool isLegalUse (const TargetTransformInfo &TTI, int64_t MinOffset, int64_t MaxOffset, LSRUse::KindType Kind, MemAccessTy AccessTy, const Formula &F)
 
static bool isAlwaysFoldable (const TargetTransformInfo &TTI, LSRUse::KindType Kind, MemAccessTy AccessTy, GlobalValue *BaseGV, int64_t BaseOffset, bool HasBaseReg)
 
static bool isAlwaysFoldable (const TargetTransformInfo &TTI, ScalarEvolution &SE, int64_t MinOffset, int64_t MaxOffset, LSRUse::KindType Kind, MemAccessTy AccessTy, const SCEV *S, bool HasBaseReg)
 
static User::op_iterator findIVOperand (User::op_iterator OI, User::op_iterator OE, Loop *L, ScalarEvolution &SE)
 Helper for CollectChains that finds an IV operand (computed by an AddRec in this loop) within [OI,OE) or returns OE.
 
static ValuegetWideOperand (Value *Oper)
 IVChain logic must consistently peek base TruncInst operands, so wrap it in a convenient helper.
 
static const SCEVgetExprBase (const SCEV *S)
 Return an approximation of this SCEV expression's "base", or NULL for any constant.
 
static bool isProfitableChain (IVChain &Chain, SmallPtrSetImpl< Instruction * > &Users, ScalarEvolution &SE, const TargetTransformInfo &TTI)
 Return true if the number of registers needed for the chain is estimated to be less than the number required for the individual IV users.
 
static bool canFoldIVIncExpr (const SCEV *IncExpr, Instruction *UserInst, Value *Operand, const TargetTransformInfo &TTI)
 Return true if the IVInc can be folded into an addressing mode.
 
static const SCEVCollectSubexprs (const SCEV *S, const SCEVConstant *C, SmallVectorImpl< const SCEV * > &Ops, const Loop *L, ScalarEvolution &SE, unsigned Depth=0)
 Split S into subexpressions which can be pulled out into separate registers.
 
static bool mayUsePostIncMode (const TargetTransformInfo &TTI, LSRUse &LU, const SCEV *S, const Loop *L, ScalarEvolution &SE)
 Return true if the SCEV represents a value that may end up as a post-increment operation.
 
static const SCEVgetAnyExtendConsideringPostIncUses (ArrayRef< PostIncLoopSet > Loops, const SCEV *Expr, Type *ToTy, ScalarEvolution &SE)
 Extend/Truncate Expr to ToTy considering post-inc uses in Loops.
 
static bool IsSimplerBaseSCEVForTarget (const TargetTransformInfo &TTI, ScalarEvolution &SE, const SCEV *Best, const SCEV *Reg, MemAccessTy AccessType)
 
static bool canHoistIVInc (const TargetTransformInfo &TTI, const LSRFixup &Fixup, const LSRUse &LU, Instruction *IVIncInsertPos, Loop *L)
 
static unsigned numLLVMArgOps (SmallVectorImpl< uint64_t > &Expr)
 Returns the total number of DW_OP_llvm_arg operands in the expression.
 
template<typename T >
static void updateDVIWithLocation (T &DbgVal, Value *Location, SmallVectorImpl< uint64_t > &Ops)
 Overwrites DVI with the location and Ops as the DIExpression.
 
template<typename T >
static void updateDVIWithLocations (T &DbgVal, SmallVectorImpl< Value * > &Locations, SmallVectorImpl< uint64_t > &Ops)
 Overwrite DVI with locations placed into a DIArglist.
 
static void UpdateDbgValueInst (DVIRecoveryRec &DVIRec, SmallVectorImpl< Value * > &NewLocationOps, SmallVectorImpl< uint64_t > &NewExpr)
 Write the new expression and new location ops for the dbg.value.
 
static ValuegetValueOrPoison (WeakVH &VH, LLVMContext &C)
 Cached location ops may be erased during LSR, in which case a poison is required when restoring from the cache.
 
static void restorePreTransformState (DVIRecoveryRec &DVIRec)
 Restore the DVI's pre-LSR arguments. Substitute undef for any erased values.
 
static bool SalvageDVI (llvm::Loop *L, ScalarEvolution &SE, llvm::PHINode *LSRInductionVar, DVIRecoveryRec &DVIRec, const SCEV *SCEVInductionVar, SCEVDbgValueBuilder IterCountExpr)
 
static void DbgRewriteSalvageableDVIs (llvm::Loop *L, ScalarEvolution &SE, llvm::PHINode *LSRInductionVar, SmallVector< std::unique_ptr< DVIRecoveryRec >, 2 > &DVIToUpdate)
 Obtain an expression for the iteration count, then attempt to salvage the dbg.value intrinsics.
 
static void DbgGatherSalvagableDVI (Loop *L, ScalarEvolution &SE, SmallVector< std::unique_ptr< DVIRecoveryRec >, 2 > &SalvageableDVISCEVs, SmallSet< AssertingVH< DbgValueInst >, 2 > &DVIHandles)
 Identify and cache salvageable DVI locations and expressions along with the corresponding SCEV(s).
 
static llvm::PHINodeGetInductionVariable (const Loop &L, ScalarEvolution &SE, const LSRInstance &LSR)
 Ideally pick the PHI IV inserted by ScalarEvolutionExpander.
 
static std::optional< std::tuple< PHINode *, PHINode *, const SCEV *, bool > > canFoldTermCondOfLoop (Loop *L, ScalarEvolution &SE, DominatorTree &DT, const LoopInfo &LI, const TargetTransformInfo &TTI)
 
static bool ReduceLoopStrength (Loop *L, IVUsers &IU, ScalarEvolution &SE, DominatorTree &DT, LoopInfo &LI, const TargetTransformInfo &TTI, AssumptionCache &AC, TargetLibraryInfo &TLI, MemorySSA *MSSA)
 
 INITIALIZE_PASS_BEGIN (LoopStrengthReduce, "loop-reduce", "Loop Strength Reduction", false, false) INITIALIZE_PASS_END(LoopStrengthReduce
 

Variables

static const unsigned MaxIVUsers = 200
 MaxIVUsers is an arbitrary threshold that provides an early opportunity for bail out.
 
static const unsigned MaxSCEVSalvageExpressionSize = 64
 Limit the size of expression that SCEV-based salvaging will attempt to translate into a DIExpression.
 
static cl::opt< boolEnablePhiElim ("enable-lsr-phielim", cl::Hidden, cl::init(true), cl::desc("Enable LSR phi elimination"))
 
static cl::opt< boolInsnsCost ("lsr-insns-cost", cl::Hidden, cl::init(true), cl::desc("Add instruction count to a LSR cost model"))
 
static cl::opt< boolLSRExpNarrow ("lsr-exp-narrow", cl::Hidden, cl::init(false), cl::desc("Narrow LSR complex solution using" " expectation of registers number"))
 
static cl::opt< boolFilterSameScaledReg ("lsr-filter-same-scaled-reg", cl::Hidden, cl::init(true), cl::desc("Narrow LSR search space by filtering non-optimal formulae" " with the same ScaledReg and Scale"))
 
static cl::opt< TTI::AddressingModeKindPreferredAddresingMode ("lsr-preferred-addressing-mode", cl::Hidden, cl::init(TTI::AMK_None), cl::desc("A flag that overrides the target's preferred addressing mode."), cl::values(clEnumValN(TTI::AMK_None, "none", "Don't prefer any addressing mode"), clEnumValN(TTI::AMK_PreIndexed, "preindexed", "Prefer pre-indexed addressing mode"), clEnumValN(TTI::AMK_PostIndexed, "postindexed", "Prefer post-indexed addressing mode")))
 
static cl::opt< unsignedComplexityLimit ("lsr-complexity-limit", cl::Hidden, cl::init(std::numeric_limits< uint16_t >::max()), cl::desc("LSR search space complexity limit"))
 
static cl::opt< unsignedSetupCostDepthLimit ("lsr-setupcost-depth-limit", cl::Hidden, cl::init(7), cl::desc("The limit on recursion depth for LSRs setup cost"))
 
static cl::opt< cl::boolOrDefaultAllowTerminatingConditionFoldingAfterLSR ("lsr-term-fold", cl::Hidden, cl::desc("Attempt to replace primary IV with other IV."))
 
static cl::opt< boolAllowDropSolutionIfLessProfitable ("lsr-drop-solution", cl::Hidden, cl::init(false), cl::desc("Attempt to drop solution if it is less profitable"))
 
static cl::opt< boolStressIVChain ("stress-ivchain", cl::Hidden, cl::init(false), cl::desc("Stress test LSR IV chains"))
 
loop reduce
 
loop Loop Strength Reduction
 
loop Loop Strength false
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "loop-reduce"

Definition at line 133 of file LoopStrengthReduce.cpp.

Function Documentation

◆ canFoldIVIncExpr()

static bool canFoldIVIncExpr ( const SCEV IncExpr,
Instruction UserInst,
Value Operand,
const TargetTransformInfo TTI 
)
static

◆ canFoldTermCondOfLoop()

static std::optional< std::tuple< PHINode *, PHINode *, const SCEV *, bool > > canFoldTermCondOfLoop ( Loop L,
ScalarEvolution SE,
DominatorTree DT,
const LoopInfo LI,
const TargetTransformInfo TTI 
)
static

◆ canHoistIVInc()

static bool canHoistIVInc ( const TargetTransformInfo TTI,
const LSRFixup &  Fixup,
const LSRUse &  LU,
Instruction IVIncInsertPos,
Loop L 
)
static

◆ CollectSubexprs()

static const SCEV * CollectSubexprs ( const SCEV S,
const SCEVConstant C,
SmallVectorImpl< const SCEV * > &  Ops,
const Loop L,
ScalarEvolution SE,
unsigned  Depth = 0 
)
static

◆ containsAddRecDependentOnLoop()

static bool containsAddRecDependentOnLoop ( const SCEV S,
const Loop L 
)
static

Definition at line 494 of file LoopStrengthReduce.cpp.

References llvm::SCEVExprContains().

◆ DbgGatherSalvagableDVI()

static void DbgGatherSalvagableDVI ( Loop L,
ScalarEvolution SE,
SmallVector< std::unique_ptr< DVIRecoveryRec >, 2 > &  SalvageableDVISCEVs,
SmallSet< AssertingVH< DbgValueInst >, 2 > &  DVIHandles 
)
static

Identify and cache salvageable DVI locations and expressions along with the corresponding SCEV(s).

Also ensure that the DVI is not deleted between cacheing and salvaging.

Definition at line 6667 of file LoopStrengthReduce.cpp.

References B, llvm::ScalarEvolution::containsUndefs(), llvm::filterDbgVars(), llvm::ScalarEvolution::getSCEV(), I, and llvm::ScalarEvolution::isSCEVable().

Referenced by ReduceLoopStrength().

◆ DbgRewriteSalvageableDVIs()

static void DbgRewriteSalvageableDVIs ( llvm::Loop L,
ScalarEvolution SE,
llvm::PHINode LSRInductionVar,
SmallVector< std::unique_ptr< DVIRecoveryRec >, 2 > &  DVIToUpdate 
)
static

Obtain an expression for the iteration count, then attempt to salvage the dbg.value intrinsics.

Definition at line 6629 of file LoopStrengthReduce.cpp.

References assert(), llvm::dbgs(), llvm::ScalarEvolution::getSCEV(), LLVM_DEBUG, MaxSCEVSalvageExpressionSize, and SalvageDVI().

Referenced by ReduceLoopStrength().

◆ DoInitialMatch()

static void DoInitialMatch ( const SCEV S,
Loop L,
SmallVectorImpl< const SCEV * > &  Good,
SmallVectorImpl< const SCEV * > &  Bad,
ScalarEvolution SE 
)
static

◆ ExtractImmediate()

static int64_t ExtractImmediate ( const SCEV *&  S,
ScalarEvolution SE 
)
static

If S involves the addition of a constant integer value, return that integer value, and mutate S to point to a new SCEV with that value excluded.

Definition at line 801 of file LoopStrengthReduce.cpp.

References llvm::Add, llvm::CallingConv::C, ExtractImmediate(), llvm::SCEV::FlagAnyWrap, llvm::SmallVectorTemplateCommon< T, typename >::front(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getAddRecExpr(), and llvm::ScalarEvolution::getConstant().

Referenced by ExtractImmediate(), and isAlwaysFoldable().

◆ ExtractSymbol()

static GlobalValue * ExtractSymbol ( const SCEV *&  S,
ScalarEvolution SE 
)
static

If S involves the addition of a GlobalValue address, return that symbol, and mutate S to point to a new SCEV with that value excluded.

Definition at line 827 of file LoopStrengthReduce.cpp.

References llvm::Add, llvm::SmallVectorTemplateCommon< T, typename >::back(), ExtractSymbol(), llvm::SCEV::FlagAnyWrap, llvm::SmallVectorTemplateCommon< T, typename >::front(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getAddRecExpr(), and llvm::ScalarEvolution::getConstant().

Referenced by ExtractSymbol(), and isAlwaysFoldable().

◆ findIVOperand()

static User::op_iterator findIVOperand ( User::op_iterator  OI,
User::op_iterator  OE,
Loop L,
ScalarEvolution SE 
)
static

Helper for CollectChains that finds an IV operand (computed by an AddRec in this loop) within [OI,OE) or returns OE.

If IVUsers mapped Instructions to IVStrideUses, we could partially skip this.

Definition at line 2768 of file LoopStrengthReduce.cpp.

References llvm::SCEVAddRecExpr::getLoop(), llvm::ScalarEvolution::getSCEV(), and llvm::ScalarEvolution::isSCEVable().

◆ getAccessType()

static MemAccessTy getAccessType ( const TargetTransformInfo TTI,
Instruction Inst,
Value OperandVal 
)
static

◆ getAnyExtendConsideringPostIncUses()

static const SCEV * getAnyExtendConsideringPostIncUses ( ArrayRef< PostIncLoopSet Loops,
const SCEV Expr,
Type ToTy,
ScalarEvolution SE 
)
static

Extend/Truncate Expr to ToTy considering post-inc uses in Loops.

For all PostIncLoopSets in Loops, first de-normalize Expr, then perform the extension/truncate and normalize again, as the normalized form can result in folds that are not valid in the post-inc use contexts. The expressions for all PostIncLoopSets must match, otherwise return nullptr.

Definition at line 4148 of file LoopStrengthReduce.cpp.

References assert(), llvm::denormalizeForPostIncUse(), llvm::ScalarEvolution::getAnyExtendExpr(), Loops, and llvm::normalizeForPostIncUse().

◆ getExactSDiv()

static const SCEV * getExactSDiv ( const SCEV LHS,
const SCEV RHS,
ScalarEvolution SE,
bool  IgnoreSignificantBits = false 
)
static

Return an expression for LHS /s RHS, if it can be determined and if the remainder is known to be zero, or null otherwise.

If IgnoreSignificantBits is true, expressions like (X * Y) /s Y are simplified to X, ignoring that the multiplication may overflow, which is useful when the result will be used in a context where the most significant bits are ignored.

Definition at line 696 of file LoopStrengthReduce.cpp.

References llvm::Add, llvm::CallingConv::C, llvm::drop_begin(), llvm::SCEV::FlagAnyWrap, llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getAddRecExpr(), llvm::SCEVConstant::getAPInt(), llvm::ScalarEvolution::getConstant(), getExactSDiv(), llvm::ScalarEvolution::getMulExpr(), llvm::User::getOperand(), llvm::Value::getType(), isAddRecSExtable(), isAddSExtable(), isMulSExtable(), llvm::Type::isPointerTy(), LHS, Mul, llvm::User::operands(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), RA, RHS, llvm::APInt::sdiv(), and llvm::APInt::srem().

Referenced by getExactSDiv().

◆ getExprBase()

static const SCEV * getExprBase ( const SCEV S)
static

Return an approximation of this SCEV expression's "base", or NULL for any constant.

Returning the expression itself is conservative. Returning a deeper subexpression is more precise and valid as long as it isn't less complex than another subexpression. For expressions involving multiple unscaled values, we need to return the pointer-type SCEVUnknown. This avoids forming chains across objects, such as: PrevOper==a[i], IVOper==b[i], IVInc==b-a.

Since SCEVUnknown is the rightmost type, and pointers are the rightmost SCEVUnknown, we simply return the rightmost SCEV operand.

Definition at line 2803 of file LoopStrengthReduce.cpp.

References llvm::Add, getExprBase(), llvm::SCEV::getSCEVType(), llvm_unreachable, llvm::reverse(), llvm::scAddExpr, llvm::scAddRecExpr, llvm::scConstant, llvm::scMulExpr, llvm::scSignExtend, llvm::scTruncate, llvm::scVScale, and llvm::scZeroExtend.

Referenced by getExprBase().

◆ GetInductionVariable()

static llvm::PHINode * GetInductionVariable ( const Loop L,
ScalarEvolution SE,
const LSRInstance &  LSR 
)
static

Ideally pick the PHI IV inserted by ScalarEvolutionExpander.

As a fallback any PHi from the loop header is usable, but may have less chance of surviving subsequent transforms.

Definition at line 6730 of file LoopStrengthReduce.cpp.

References llvm::ScalarEvolution::containsUndefs(), llvm::ScalarEvolution::getSCEV(), llvm::ScalarEvolution::isSCEVable(), IV, and P.

Referenced by ReduceLoopStrength().

◆ getScalingFactorCost()

static InstructionCost getScalingFactorCost ( const TargetTransformInfo TTI,
const LSRUse &  LU,
const Formula &  F,
const Loop L 
)
static

◆ getSetupCost()

static unsigned getSetupCost ( const SCEV Reg,
unsigned  Depth 
)
static

Definition at line 1261 of file LoopStrengthReduce.cpp.

References llvm::Depth, getSetupCost(), and llvm::SCEV::operands().

Referenced by getSetupCost().

◆ getValueOrPoison()

static Value * getValueOrPoison ( WeakVH VH,
LLVMContext C 
)
static

Cached location ops may be erased during LSR, in which case a poison is required when restoring from the cache.

The type of that location is no longer available, so just use int8. The poison will be replaced by one or more locations later when a SCEVDbgValueBuilder selects alternative locations to use for the salvage.

Definition at line 6477 of file LoopStrengthReduce.cpp.

References llvm::CallingConv::C, llvm::PoisonValue::get(), and llvm::Type::getInt8Ty().

Referenced by restorePreTransformState().

◆ getWideOperand()

static Value * getWideOperand ( Value Oper)
static

IVChain logic must consistently peek base TruncInst operands, so wrap it in a convenient helper.

Definition at line 2787 of file LoopStrengthReduce.cpp.

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN ( LoopStrengthReduce  ,
"loop-reduce"  ,
"Loop Strength Reduction"  ,
false  ,
false   
)

◆ isAddRecSExtable()

static bool isAddRecSExtable ( const SCEVAddRecExpr AR,
ScalarEvolution SE 
)
static

Return true if the given addrec can be sign-extended without changing its value.

Definition at line 668 of file LoopStrengthReduce.cpp.

References llvm::IntegerType::get(), llvm::ScalarEvolution::getContext(), llvm::ScalarEvolution::getSignExtendExpr(), llvm::SCEVAddRecExpr::getType(), and llvm::ScalarEvolution::getTypeSizeInBits().

Referenced by getExactSDiv().

◆ isAddressUse()

static bool isAddressUse ( const TargetTransformInfo TTI,
Instruction Inst,
Value OperandVal 
)
static

Returns true if the specified instruction is using the specified value as an address.

Definition at line 853 of file LoopStrengthReduce.cpp.

References llvm::TargetTransformInfo::getTgtMemIntrinsic(), and llvm::MemIntrinsicInfo::PtrVal.

Referenced by canFoldIVIncExpr().

◆ isAddSExtable()

static bool isAddSExtable ( const SCEVAddExpr A,
ScalarEvolution SE 
)
static

Return true if the given add can be sign-extended without changing its value.

Definition at line 676 of file LoopStrengthReduce.cpp.

References A, llvm::IntegerType::get(), llvm::ScalarEvolution::getContext(), llvm::ScalarEvolution::getSignExtendExpr(), and llvm::ScalarEvolution::getTypeSizeInBits().

Referenced by getExactSDiv().

◆ isAlwaysFoldable() [1/2]

static bool isAlwaysFoldable ( const TargetTransformInfo TTI,
LSRUse::KindType  Kind,
MemAccessTy  AccessTy,
GlobalValue BaseGV,
int64_t  BaseOffset,
bool  HasBaseReg 
)
static

Definition at line 1841 of file LoopStrengthReduce.cpp.

References isAMCompletelyFolded().

Referenced by canFoldIVIncExpr().

◆ isAlwaysFoldable() [2/2]

static bool isAlwaysFoldable ( const TargetTransformInfo TTI,
ScalarEvolution SE,
int64_t  MinOffset,
int64_t  MaxOffset,
LSRUse::KindType  Kind,
MemAccessTy  AccessTy,
const SCEV S,
bool  HasBaseReg 
)
static

◆ isAMCompletelyFolded() [1/4]

static bool isAMCompletelyFolded ( const TargetTransformInfo TTI,
const LSRUse &  LU,
const Formula &  F 
)
static

Check if the addressing mode defined by F is completely folded in LU at isel time.

This includes address-mode folding and special icmp tricks. This function returns true if LU can accommodate what F defines and up to 1 base + 1 scaled + offset. In other words, if F has several base registers, this function may still return true. Therefore, users still need to account for additional base registers and/or unfolded offsets to derive an accurate cost model.

Definition at line 1787 of file LoopStrengthReduce.cpp.

References F, Fixup, isAMCompletelyFolded(), and llvm::TargetTransformInfo::LSRWithInstrQueries().

Referenced by getScalingFactorCost(), isAlwaysFoldable(), isAMCompletelyFolded(), and isLegalUse().

◆ isAMCompletelyFolded() [2/4]

static bool isAMCompletelyFolded ( const TargetTransformInfo TTI,
int64_t  MinOffset,
int64_t  MaxOffset,
LSRUse::KindType  Kind,
MemAccessTy  AccessTy,
const Formula &  F,
const Loop L 
)
static

Definition at line 1749 of file LoopStrengthReduce.cpp.

References assert(), F, and isAMCompletelyFolded().

◆ isAMCompletelyFolded() [3/4]

static bool isAMCompletelyFolded ( const TargetTransformInfo TTI,
int64_t  MinOffset,
int64_t  MaxOffset,
LSRUse::KindType  Kind,
MemAccessTy  AccessTy,
GlobalValue BaseGV,
int64_t  BaseOffset,
bool  HasBaseReg,
int64_t  Scale 
)
static

Definition at line 1728 of file LoopStrengthReduce.cpp.

References isAMCompletelyFolded().

◆ isAMCompletelyFolded() [4/4]

static bool isAMCompletelyFolded ( const TargetTransformInfo TTI,
LSRUse::KindType  Kind,
MemAccessTy  AccessTy,
GlobalValue BaseGV,
int64_t  BaseOffset,
bool  HasBaseReg,
int64_t  Scale,
Instruction Fixup = nullptr 
)
static

◆ isExistingPhi()

static bool isExistingPhi ( const SCEVAddRecExpr AR,
ScalarEvolution SE 
)
static

◆ isHighCostExpansion()

static bool isHighCostExpansion ( const SCEV S,
SmallPtrSetImpl< const SCEV * > &  Processed,
ScalarEvolution SE 
)
static

Check if expanding this expression is likely to incur significant cost.

This is tricky because SCEV doesn't track which expressions are actually computed by the current IR.

We currently allow expansion of IV increments that involve adds, multiplication by constants, and AddRecs from existing phis.

TODO: Allow UDivExpr if we can find an existing IV increment that is an obvious multiple of the UDivExpr.

Definition at line 971 of file LoopStrengthReduce.cpp.

References llvm::Add, llvm::User::getNumOperands(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::ScalarEvolution::getSCEV(), llvm::SCEV::getSCEVType(), llvm::Value::getType(), llvm::SmallPtrSetImpl< PtrType >::insert(), isExistingPhi(), isHighCostExpansion(), llvm::ScalarEvolution::isSCEVable(), Mul, llvm::scConstant, llvm::scSignExtend, llvm::scTruncate, llvm::scUnknown, llvm::scVScale, llvm::scZeroExtend, and llvm::Value::users().

Referenced by isHighCostExpansion().

◆ isLegalUse() [1/2]

static bool isLegalUse ( const TargetTransformInfo TTI,
int64_t  MinOffset,
int64_t  MaxOffset,
LSRUse::KindType  Kind,
MemAccessTy  AccessTy,
const Formula &  F 
)
static

Definition at line 1780 of file LoopStrengthReduce.cpp.

References F, and isLegalUse().

◆ isLegalUse() [2/2]

static bool isLegalUse ( const TargetTransformInfo TTI,
int64_t  MinOffset,
int64_t  MaxOffset,
LSRUse::KindType  Kind,
MemAccessTy  AccessTy,
GlobalValue BaseGV,
int64_t  BaseOffset,
bool  HasBaseReg,
int64_t  Scale 
)
static

Test whether we know how to expand the current formula.

Definition at line 1766 of file LoopStrengthReduce.cpp.

References isAMCompletelyFolded().

Referenced by isLegalUse().

◆ isMulSExtable()

static bool isMulSExtable ( const SCEVMulExpr M,
ScalarEvolution SE 
)
static

Return true if the given mul can be sign-extended without changing its value.

Definition at line 684 of file LoopStrengthReduce.cpp.

References llvm::IntegerType::get(), llvm::ScalarEvolution::getContext(), llvm::ScalarEvolution::getSignExtendExpr(), and llvm::ScalarEvolution::getTypeSizeInBits().

Referenced by getExactSDiv().

◆ isProfitableChain()

static bool isProfitableChain ( IVChain &  Chain,
SmallPtrSetImpl< Instruction * > &  Users,
ScalarEvolution SE,
const TargetTransformInfo TTI 
)
static

Return true if the number of registers needed for the chain is estimated to be less than the number required for the individual IV users.

First prohibit any IV users that keep the IV live across increments (the Users set should be empty). Next count the number and type of increments in the chain.

Chaining IVs can lead to considerable code bloat if ISEL doesn't effectively use postinc addressing modes. Only consider it profitable it the increments can be computed in fewer registers when chained.

TODO: Consider IVInc free if it's already used in another chains.

Definition at line 2870 of file LoopStrengthReduce.cpp.

References assert(), llvm::dbgs(), for(), llvm::ScalarEvolution::getSCEV(), llvm::TargetTransformInfo::isProfitableLSRChainElement(), LLVM_DEBUG, StressIVChain, and Users.

◆ IsSimplerBaseSCEVForTarget()

static bool IsSimplerBaseSCEVForTarget ( const TargetTransformInfo TTI,
ScalarEvolution SE,
const SCEV Best,
const SCEV Reg,
MemAccessTy  AccessType 
)
static

◆ mayUsePostIncMode()

static bool mayUsePostIncMode ( const TargetTransformInfo TTI,
LSRUse &  LU,
const SCEV S,
const Loop L,
ScalarEvolution SE 
)
static

◆ numLLVMArgOps()

static unsigned numLLVMArgOps ( SmallVectorImpl< uint64_t > &  Expr)
static

Returns the total number of DW_OP_llvm_arg operands in the expression.

This helps in determining if a DIArglist is necessary or can be omitted from the dbg.value.

Definition at line 6393 of file LoopStrengthReduce.cpp.

References llvm::dwarf::DW_OP_LLVM_arg.

Referenced by UpdateDbgValueInst(), updateDVIWithLocation(), and updateDVIWithLocations().

◆ ReduceLoopStrength()

static bool ReduceLoopStrength ( Loop L,
IVUsers IU,
ScalarEvolution SE,
DominatorTree DT,
LoopInfo LI,
const TargetTransformInfo TTI,
AssumptionCache AC,
TargetLibraryInfo TLI,
MemorySSA MSSA 
)
static

◆ restorePreTransformState()

static void restorePreTransformState ( DVIRecoveryRec &  DVIRec)
static

Restore the DVI's pre-LSR arguments. Substitute undef for any erased values.

Definition at line 6482 of file LoopStrengthReduce.cpp.

References assert(), llvm::dbgs(), llvm::DIArgList::get(), llvm::ValueAsMetadata::get(), getValueOrPoison(), LLVM_DEBUG, and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by SalvageDVI().

◆ SalvageDVI()

static bool SalvageDVI ( llvm::Loop L,
ScalarEvolution SE,
llvm::PHINode LSRInductionVar,
DVIRecoveryRec &  DVIRec,
const SCEV SCEVInductionVar,
SCEVDbgValueBuilder  IterCountExpr 
)
static

◆ STATISTIC()

STATISTIC ( NumTermFold  ,
"Number of terminating condition fold recognized and performed"   
)

◆ UpdateDbgValueInst()

static void UpdateDbgValueInst ( DVIRecoveryRec &  DVIRec,
SmallVectorImpl< Value * > &  NewLocationOps,
SmallVectorImpl< uint64_t > &  NewExpr 
)
static

Write the new expression and new location ops for the dbg.value.

If possible reduce the szie of the dbg.value intrinsic by omitting DIArglist. This can be omitted if:

  1. There is only a single location, refenced by a single DW_OP_llvm_arg.
  2. The DW_OP_LLVM_arg is the first operand in the expression.

Definition at line 6436 of file LoopStrengthReduce.cpp.

References llvm::DIExpression::append(), assert(), llvm::drop_begin(), llvm::dwarf::DW_OP_LLVM_arg, llvm::DIExpression::isComplex(), numLLVMArgOps(), updateDVIWithLocation(), and updateDVIWithLocations().

Referenced by SalvageDVI().

◆ updateDVIWithLocation()

template<typename T >
static void updateDVIWithLocation ( T DbgVal,
Value Location,
SmallVectorImpl< uint64_t > &  Ops 
)
static

Overwrites DVI with the location and Ops as the DIExpression.

This will create an invalid expression if Ops has any dwarf::DW_OP_llvm_arg operands, because a DIArglist is not created for the first argument of the dbg.value.

Definition at line 6406 of file LoopStrengthReduce.cpp.

References assert(), llvm::ValueAsMetadata::get(), and numLLVMArgOps().

Referenced by UpdateDbgValueInst().

◆ updateDVIWithLocations()

template<typename T >
static void updateDVIWithLocations ( T DbgVal,
SmallVectorImpl< Value * > &  Locations,
SmallVectorImpl< uint64_t > &  Ops 
)
static

Overwrite DVI with locations placed into a DIArglist.

Definition at line 6417 of file LoopStrengthReduce.cpp.

References assert(), llvm::DIArgList::get(), llvm::ValueAsMetadata::get(), numLLVMArgOps(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by UpdateDbgValueInst().

Variable Documentation

◆ AllowDropSolutionIfLessProfitable

cl::opt< bool > AllowDropSolutionIfLessProfitable("lsr-drop-solution", cl::Hidden, cl::init(false), cl::desc("Attempt to drop solution if it is less profitable")) ( "lsr-drop-solution"  ,
cl::Hidden  ,
cl::init(false)  ,
cl::desc("Attempt to drop solution if it is less profitable")   
)
static

◆ AllowTerminatingConditionFoldingAfterLSR

cl::opt< cl::boolOrDefault > AllowTerminatingConditionFoldingAfterLSR("lsr-term-fold", cl::Hidden, cl::desc("Attempt to replace primary IV with other IV.")) ( "lsr-term-fold"  ,
cl::Hidden  ,
cl::desc("Attempt to replace primary IV with other IV.")   
)
static

Referenced by ReduceLoopStrength().

◆ ComplexityLimit

cl::opt< unsigned > ComplexityLimit("lsr-complexity-limit", cl::Hidden, cl::init(std::numeric_limits< uint16_t >::max()), cl::desc("LSR search space complexity limit")) ( "lsr-complexity-limit"  ,
cl::Hidden  ,
cl::init(std::numeric_limits< uint16_t >::max())  ,
cl::desc("LSR search space complexity limit")   
)
static

◆ EnablePhiElim

cl::opt< bool > EnablePhiElim("enable-lsr-phielim", cl::Hidden, cl::init(true), cl::desc("Enable LSR phi elimination")) ( "enable-lsr-phielim"  ,
cl::Hidden  ,
cl::init(true ,
cl::desc("Enable LSR phi elimination")   
)
static

Referenced by ReduceLoopStrength().

◆ false

loop Loop Strength false

Definition at line 7144 of file LoopStrengthReduce.cpp.

◆ FilterSameScaledReg

cl::opt< bool > FilterSameScaledReg("lsr-filter-same-scaled-reg", cl::Hidden, cl::init(true), cl::desc("Narrow LSR search space by filtering non-optimal formulae" " with the same ScaledReg and Scale")) ( "lsr-filter-same-scaled-reg"  ,
cl::Hidden  ,
cl::init(true ,
cl::desc("Narrow LSR search space by filtering non-optimal formulae" " with the same ScaledReg and Scale")   
)
static

◆ InsnsCost

cl::opt< bool > InsnsCost("lsr-insns-cost", cl::Hidden, cl::init(true), cl::desc("Add instruction count to a LSR cost model")) ( "lsr-insns-cost"  ,
cl::Hidden  ,
cl::init(true ,
cl::desc("Add instruction count to a LSR cost model")   
)
static

◆ LSRExpNarrow

cl::opt< bool > LSRExpNarrow("lsr-exp-narrow", cl::Hidden, cl::init(false), cl::desc("Narrow LSR complex solution using" " expectation of registers number")) ( "lsr-exp-narrow"  ,
cl::Hidden  ,
cl::init(false)  ,
cl::desc("Narrow LSR complex solution using" " expectation of registers number")   
)
static

◆ MaxIVUsers

const unsigned MaxIVUsers = 200
static

MaxIVUsers is an arbitrary threshold that provides an early opportunity for bail out.

This threshold is far beyond the number of users that LSR can conceivably solve, so it should not affect generated code, but catches the worst cases before LSR burns too much compile time and stack space.

Definition at line 139 of file LoopStrengthReduce.cpp.

◆ MaxSCEVSalvageExpressionSize

const unsigned MaxSCEVSalvageExpressionSize = 64
static

Limit the size of expression that SCEV-based salvaging will attempt to translate into a DIExpression.

Choose a maximum size such that debuginfo is not excessively increased and the salvaging is not too expensive for the compiler.

Definition at line 145 of file LoopStrengthReduce.cpp.

Referenced by DbgRewriteSalvageableDVIs().

◆ PreferredAddresingMode

cl::opt< TTI::AddressingModeKind > PreferredAddresingMode("lsr-preferred-addressing-mode", cl::Hidden, cl::init(TTI::AMK_None), cl::desc("A flag that overrides the target's preferred addressing mode."), cl::values(clEnumValN(TTI::AMK_None, "none", "Don't prefer any addressing mode"), clEnumValN(TTI::AMK_PreIndexed, "preindexed", "Prefer pre-indexed addressing mode"), clEnumValN(TTI::AMK_PostIndexed, "postindexed", "Prefer post-indexed addressing mode"))) ( "lsr-preferred-addressing-mode"  ,
cl::Hidden  ,
cl::init(TTI::AMK_None)  ,
cl::desc("A flag that overrides the target's preferred addressing mode.")  ,
cl::values(clEnumValN(TTI::AMK_None, "none", "Don't prefer any addressing mode"), clEnumValN(TTI::AMK_PreIndexed, "preindexed", "Prefer pre-indexed addressing mode"), clEnumValN(TTI::AMK_PostIndexed, "postindexed", "Prefer post-indexed addressing mode"))   
)
static

◆ reduce

loop reduce

Definition at line 7143 of file LoopStrengthReduce.cpp.

◆ Reduction

loop Loop Strength Reduction

◆ SetupCostDepthLimit

cl::opt< unsigned > SetupCostDepthLimit("lsr-setupcost-depth-limit", cl::Hidden, cl::init(7), cl::desc("The limit on recursion depth for LSRs setup cost")) ( "lsr-setupcost-depth-limit"  ,
cl::Hidden  ,
cl::init(7)  ,
cl::desc("The limit on recursion depth for LSRs setup cost")   
)
static

◆ StressIVChain

cl::opt< bool > StressIVChain("stress-ivchain", cl::Hidden, cl::init(false), cl::desc("Stress test LSR IV chains")) ( "stress-ivchain"  ,
cl::Hidden  ,
cl::init(false)  ,
cl::desc("Stress test LSR IV chains")   
)
static

Referenced by isProfitableChain().