LLVM 17.0.0git
|
This class uses information about analyze scalars to rewrite expressions in canonical form. More...
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
Public Member Functions | |
SCEVExpander (ScalarEvolution &se, const DataLayout &DL, const char *name, bool PreserveLCSSA=true) | |
Construct a SCEVExpander in "canonical" mode. | |
~SCEVExpander () | |
void | clear () |
Erase the contents of the InsertedExpressions map so that users trying to expand the same expression into multiple BasicBlocks or different places within the same BasicBlock can do so. | |
ScalarEvolution * | getSE () |
const SmallVectorImpl< WeakVH > & | getInsertedIVs () const |
SmallVector< Instruction *, 32 > | getAllInsertedInstructions () const |
Return a vector containing all instructions inserted during expansion. | |
bool | isHighCostExpansion (ArrayRef< const SCEV * > Exprs, Loop *L, unsigned Budget, const TargetTransformInfo *TTI, const Instruction *At) |
Return true for expressions that can't be evaluated at runtime within given Budget. | |
Instruction * | getIVIncOperand (Instruction *IncV, Instruction *InsertPos, bool allowScale) |
Return the induction variable increment's IV operand. | |
bool | hoistIVInc (Instruction *IncV, Instruction *InsertPos, bool RecomputePoisonFlags=false) |
Utility for hoisting IncV (with all subexpressions requried for its computation) before InsertPos . | |
unsigned | replaceCongruentIVs (Loop *L, const DominatorTree *DT, SmallVectorImpl< WeakTrackingVH > &DeadInsts, const TargetTransformInfo *TTI=nullptr) |
replace congruent phis with their most canonical representative. | |
bool | isSafeToExpand (const SCEV *S) const |
Return true if the given expression is safe to expand in the sense that all materialized values are safe to speculate anywhere their operands are defined, and the expander is capable of expanding the expression. | |
bool | isSafeToExpandAt (const SCEV *S, const Instruction *InsertionPoint) const |
Return true if the given expression is safe to expand in the sense that all materialized values are defined and safe to speculate at the specified location and their operands are defined at this location. | |
Value * | expandCodeFor (const SCEV *SH, Type *Ty, Instruction *I) |
Insert code to directly compute the specified SCEV expression into the program. | |
Value * | expandCodeFor (const SCEV *SH, Type *Ty=nullptr) |
Insert code to directly compute the specified SCEV expression into the program. | |
Value * | expandCodeForPredicate (const SCEVPredicate *Pred, Instruction *Loc) |
Generates a code sequence that evaluates this predicate. | |
Value * | expandComparePredicate (const SCEVComparePredicate *Pred, Instruction *Loc) |
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a SCEVComparePredicate. | |
Value * | generateOverflowCheck (const SCEVAddRecExpr *AR, Instruction *Loc, bool Signed) |
Generates code that evaluates if the AR expression will overflow. | |
Value * | expandWrapPredicate (const SCEVWrapPredicate *P, Instruction *Loc) |
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a SCEVWrapPredicate. | |
Value * | expandUnionPredicate (const SCEVUnionPredicate *Pred, Instruction *Loc) |
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a SCEVUnionPredicate. | |
void | setIVIncInsertPos (const Loop *L, Instruction *Pos) |
Set the current IV increment loop and position. | |
void | setPostInc (const PostIncLoopSet &L) |
Enable post-inc expansion for addrecs referring to the given loops. | |
void | clearPostInc () |
Disable all post-inc expansion. | |
void | disableCanonicalMode () |
Disable the behavior of expanding expressions in canonical form rather than in a more literal form. | |
void | enableLSRMode () |
void | setInsertPoint (Instruction *IP) |
Set the current insertion point. | |
void | clearInsertPoint () |
Clear the current insertion point. | |
void | SetCurrentDebugLocation (DebugLoc L) |
Set location information used by debugging information. | |
DebugLoc | getCurrentDebugLocation () const |
Get location information used by debugging information. | |
bool | isInsertedInstruction (Instruction *I) const |
Return true if the specified instruction was inserted by the code rewriter. | |
void | setChainedPhi (PHINode *PN) |
Value * | getRelatedExistingExpansion (const SCEV *S, const Instruction *At, Loop *L) |
Try to find the ValueOffsetPair for S. | |
BasicBlock::iterator | findInsertPointAfter (Instruction *I, Instruction *MustDominate) const |
Returns a suitable insert point after I , that dominates MustDominate . | |
![]() | |
Value * | visit (const SCEV *S) |
Value * | visitCouldNotCompute (const SCEVCouldNotCompute *S) |
Friends | |
struct | SCEVVisitor< SCEVExpander, Value * > |
This class uses information about analyze scalars to rewrite expressions in canonical form.
Clients should create an instance of this class when rewriting is needed, and destroy it when finished to allow the release of the associated memory.
Definition at line 50 of file ScalarEvolutionExpander.h.
|
inlineexplicit |
Construct a SCEVExpander in "canonical" mode.
Definition at line 161 of file ScalarEvolutionExpander.h.
|
inline |
Definition at line 174 of file ScalarEvolutionExpander.h.
References assert(), and llvm::SmallVectorBase< Size_T >::empty().
|
inline |
Erase the contents of the InsertedExpressions map so that users trying to expand the same expression into multiple BasicBlocks or different places within the same BasicBlock can do so.
Definition at line 186 of file ScalarEvolutionExpander.h.
References llvm::SmallPtrSetImplBase::clear().
Referenced by llvm::SCEVExpanderCleaner::cleanup().
|
inline |
Clear the current insertion point.
This is useful if the instruction that had been serving as the insertion point may have been deleted.
Definition at line 356 of file ScalarEvolutionExpander.h.
References llvm::IRBuilderBase::ClearInsertionPoint().
|
inline |
Disable all post-inc expansion.
Definition at line 330 of file ScalarEvolutionExpander.h.
References llvm::SmallPtrSetImplBase::clear().
|
inline |
Disable the behavior of expanding expressions in canonical form rather than in a more literal form.
Non-canonical mode is useful for late optimization passes.
Definition at line 341 of file ScalarEvolutionExpander.h.
|
inline |
Definition at line 343 of file ScalarEvolutionExpander.h.
|
inline |
Insert code to directly compute the specified SCEV expression into the program.
The code is inserted into the specified block.
Definition at line 279 of file ScalarEvolutionExpander.h.
References I.
Referenced by llvm::addDiffRuntimeChecks(), ReduceLoopStrength(), llvm::splitLoopBound(), and llvm::UnrollRuntimeLoopRemainder().
Insert code to directly compute the specified SCEV expression into the program.
The code is inserted into the SCEVExpander's current insertion point. If a type is specified, the result will be expanded to have that type, with a cast if necessary.
Definition at line 287 of file ScalarEvolutionExpander.h.
Value * SCEVExpander::expandCodeForPredicate | ( | const SCEVPredicate * | Pred, |
Instruction * | Loc | ||
) |
Generates a code sequence that evaluates this predicate.
The inserted instructions will be at position Loc
. The result will be of type i1 and will have a value of 0 when the predicate is false and 1 otherwise.
Definition at line 2336 of file ScalarEvolutionExpander.cpp.
References assert(), expandComparePredicate(), expandUnionPredicate(), expandWrapPredicate(), llvm::SCEVPredicate::getKind(), llvm_unreachable, llvm::SCEVPredicate::P_Compare, llvm::SCEVPredicate::P_Union, and llvm::SCEVPredicate::P_Wrap.
Referenced by expandUnionPredicate().
Value * SCEVExpander::expandComparePredicate | ( | const SCEVComparePredicate * | Pred, |
Instruction * | Loc | ||
) |
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a SCEVComparePredicate.
Definition at line 2352 of file ScalarEvolutionExpander.cpp.
References llvm::IRBuilderBase::CreateICmp(), llvm::CmpInst::getInversePredicate(), llvm::SCEVComparePredicate::getLHS(), llvm::SCEVComparePredicate::getPredicate(), llvm::SCEVComparePredicate::getRHS(), llvm::SCEV::getType(), I, and llvm::IRBuilderBase::SetInsertPoint().
Referenced by expandCodeForPredicate().
Value * SCEVExpander::expandUnionPredicate | ( | const SCEVUnionPredicate * | Pred, |
Instruction * | Loc | ||
) |
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a SCEVUnionPredicate.
Definition at line 2519 of file ScalarEvolutionExpander.cpp.
References llvm::IRBuilderBase::CreateOr(), llvm::SmallVectorBase< Size_T >::empty(), expandCodeForPredicate(), llvm::Value::getContext(), llvm::ConstantInt::getFalse(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::IRBuilderBase::SetInsertPoint().
Referenced by expandCodeForPredicate().
Value * SCEVExpander::expandWrapPredicate | ( | const SCEVWrapPredicate * | P, |
Instruction * | Loc | ||
) |
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a SCEVWrapPredicate.
Definition at line 2494 of file ScalarEvolutionExpander.cpp.
References A, llvm::IRBuilderBase::CreateOr(), generateOverflowCheck(), llvm::Value::getContext(), llvm::SCEVWrapPredicate::getExpr(), llvm::ConstantInt::getFalse(), llvm::SCEVWrapPredicate::getFlags(), llvm::SCEVWrapPredicate::IncrementNSSW, and llvm::SCEVWrapPredicate::IncrementNUSW.
Referenced by expandCodeForPredicate().
BasicBlock::iterator SCEVExpander::findInsertPointAfter | ( | Instruction * | I, |
Instruction * | MustDominate | ||
) | const |
Returns a suitable insert point after I
, that dominates MustDominate
.
Skips instructions inserted by the expander.
Definition at line 99 of file ScalarEvolutionExpander.cpp.
References assert(), llvm::BasicBlock::getFirstInsertionPt(), llvm::Instruction::getParent(), I, and isInsertedInstruction().
Value * SCEVExpander::generateOverflowCheck | ( | const SCEVAddRecExpr * | AR, |
Instruction * | Loc, | ||
bool | Signed | ||
) |
Generates code that evaluates if the AR
expression will overflow.
Definition at line 2365 of file ScalarEvolutionExpander.cpp.
References llvm::Add, assert(), llvm::IRBuilderBase::CreateAdd(), llvm::IRBuilderBase::CreateAnd(), llvm::IRBuilderBase::CreateCall(), llvm::IRBuilderBase::CreateExtractValue(), llvm::IRBuilderBase::CreateGEP(), llvm::IRBuilderBase::CreateICmp(), llvm::IRBuilderBase::CreateNeg(), llvm::IRBuilderBase::CreateOr(), llvm::IRBuilderBase::CreateSelect(), llvm::IRBuilderBase::CreateSub(), llvm::IRBuilderBase::CreateZExtOrTrunc(), llvm::IntegerType::get(), llvm::ConstantInt::get(), llvm::Value::getContext(), llvm::Intrinsic::getDeclaration(), llvm::ConstantInt::getFalse(), llvm::IRBuilderBase::getInt8PtrTy(), llvm::IRBuilderBase::getInt8Ty(), llvm::SCEVAddRecExpr::getLoop(), llvm::APInt::getMaxValue(), llvm::Instruction::getModule(), llvm::ScalarEvolution::getNegativeSCEV(), llvm::ScalarEvolution::getPredicatedBackedgeTakenCount(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::SCEV::getType(), llvm::SCEVAddRecExpr::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), llvm::APInt::getZero(), llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLT, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULT, llvm::SCEVAddRecExpr::isAffine(), llvm::ScalarEvolution::isKnownNegative(), llvm::ScalarEvolution::isKnownPositive(), llvm::SCEV::isOne(), llvm::Mul, llvm::IRBuilderBase::SetInsertPoint(), Signed, and llvm::APInt::zext().
Referenced by expandWrapPredicate().
|
inline |
Return a vector containing all instructions inserted during expansion.
Definition at line 199 of file ScalarEvolutionExpander.h.
References llvm::SmallPtrSetImpl< PtrType >::contains().
Referenced by llvm::SCEVExpanderCleaner::cleanup().
|
inline |
Get location information used by debugging information.
Definition at line 364 of file ScalarEvolutionExpander.h.
References llvm::IRBuilderBase::getCurrentDebugLocation().
|
inline |
Definition at line 196 of file ScalarEvolutionExpander.h.
Instruction * SCEVExpander::getIVIncOperand | ( | Instruction * | IncV, |
Instruction * | InsertPos, | ||
bool | allowScale | ||
) |
Return the induction variable increment's IV operand.
getIVIncOperand returns an induction variable increment's induction variable operand.
If allowScale is set, any type of GEP is allowed as long as the nonIV operands dominate InsertPos.
If allowScale is not set, ensure that a GEP increment conforms to one of the simple patterns generated by getAddRecExprPHILiterally and expandAddtoGEP. If the pattern isn't recognized, return NULL.
Definition at line 971 of file ScalarEvolutionExpander.cpp.
References llvm::DominatorTree::dominates(), llvm::drop_begin(), llvm::ScalarEvolution::getContext(), llvm::Type::getInt1PtrTy(), llvm::Type::getInt8PtrTy(), llvm::User::getNumOperands(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), and llvm::User::operands().
Referenced by hoistIVInc().
Value * SCEVExpander::getRelatedExistingExpansion | ( | const SCEV * | S, |
const Instruction * | At, | ||
Loop * | L | ||
) |
Try to find the ValueOffsetPair for S.
The function is mainly used to check whether S can be expanded cheaply. If this returns a non-None value, we know we can codegen the ValueOffsetPair
into a suitable expansion identical with S so that S can be expanded cheaply.
L is a hint which tells in which loop to look for the suitable value. On success return value which is equivalent to the expanded S at point At. Return nullptr if value was not found.
Note that this function does not perform an exhaustive search. I.e if it didn't find any value it does not mean that there is no such value.
Definition at line 2053 of file ScalarEvolutionExpander.cpp.
References llvm::DominatorTree::dominates(), llvm::ScalarEvolution::getSCEV(), LHS, llvm::PatternMatch::m_BasicBlock(), llvm::PatternMatch::m_Br(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Instruction(), llvm::PatternMatch::match(), and RHS.
|
inline |
Definition at line 195 of file ScalarEvolutionExpander.h.
bool SCEVExpander::hoistIVInc | ( | Instruction * | IncV, |
Instruction * | InsertPos, | ||
bool | RecomputePoisonFlags = false |
||
) |
Utility for hoisting IncV
(with all subexpressions requried for its computation) before InsertPos
.
hoistStep - Attempt to hoist a simple IV increment above InsertPos to make it available to other uses in this loop.
If RecomputePoisonFlags
is set, drops all poison-generating flags from instructions being hoisted and tries to re-infer them in the new location. It should be used when we are going to introduce a new use in the new position that didn't exist before, and may trigger new UB in case of poison.
Recursively hoist any operands, until we reach a value that dominates InsertPos.
Definition at line 1038 of file ScalarEvolutionExpander.cpp.
References llvm::DominatorTree::dominates(), llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, Flags, getIVIncOperand(), llvm::Instruction::getParent(), llvm::ScalarEvolution::getStrengthenedNoWrapFlagsFromBinOp(), I, llvm::ScalarEvolution::maskFlags(), llvm::LoopInfo::movementPreservesLCSSAForm(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::reverse(), llvm::Instruction::setHasNoSignedWrap(), and llvm::Instruction::setHasNoUnsignedWrap().
Referenced by replaceCongruentIVs().
|
inline |
Return true for expressions that can't be evaluated at runtime within given Budget.
At
is a parameter which specifies point in code where user is going to expand these expressions. Sometimes this knowledge can lead to a less pessimistic cost estimation.
Definition at line 225 of file ScalarEvolutionExpander.h.
References assert(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::TargetTransformInfo::TCC_Basic.
Referenced by llvm::UnrollRuntimeLoopRemainder().
|
inline |
Return true if the specified instruction was inserted by the code rewriter.
If so, the client should not modify the instruction. Note that this also includes instructions re-used during expansion.
Definition at line 371 of file ScalarEvolutionExpander.h.
References I.
Referenced by findInsertPointAfter().
Return true if the given expression is safe to expand in the sense that all materialized values are safe to speculate anywhere their operands are defined, and the expander is capable of expanding the expression.
Definition at line 2635 of file ScalarEvolutionExpander.cpp.
References llvm::visitAll().
Referenced by canFoldTermCondOfLoop(), isSafeToExpandAt(), and ReduceLoopStrength().
bool SCEVExpander::isSafeToExpandAt | ( | const SCEV * | S, |
const Instruction * | InsertionPoint | ||
) | const |
Return true if the given expression is safe to expand in the sense that all materialized values are defined and safe to speculate at the specified location and their operands are defined at this location.
Definition at line 2641 of file ScalarEvolutionExpander.cpp.
References llvm::ScalarEvolution::dominates(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), llvm::is_contained(), isSafeToExpand(), llvm::User::operand_values(), and llvm::ScalarEvolution::properlyDominates().
unsigned SCEVExpander::replaceCongruentIVs | ( | Loop * | L, |
const DominatorTree * | DT, | ||
SmallVectorImpl< WeakTrackingVH > & | DeadInsts, | ||
const TargetTransformInfo * | TTI = nullptr |
||
) |
replace congruent phis with their most canonical representative.
replaceCongruentIVs - Check for congruent phis in this loop header and replace them with their most canonical representative.
Return the number of phis eliminated.
Return the number of phis eliminated.
This does not depend on any SCEVExpander state but should be used in the same context that SCEVExpander is used.
Definition at line 1909 of file ScalarEvolutionExpander.cpp.
References llvm::SmallVectorTemplateCommon< T, typename >::back(), Builder, llvm::dbgs(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::ScalarEvolution::forgetValue(), llvm::Instruction::getDebugLoc(), llvm::BasicBlock::getFirstInsertionPt(), llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::getFixedValue(), llvm::PHINode::getIncomingValueForBlock(), llvm::ilist_node_with_parent< NodeTy, ParentTy, Options >::getNextNode(), llvm::Instruction::getParent(), llvm::Type::getPrimitiveSizeInBits(), llvm::ScalarEvolution::getSCEV(), llvm::ScalarEvolution::getTruncateExpr(), llvm::ScalarEvolution::getTruncateOrNoop(), llvm::Value::getType(), hoistIVInc(), llvm::Type::isIntegerTy(), llvm::Type::isPointerTy(), llvm::ScalarEvolution::isSCEVable(), llvm::TargetTransformInfo::isTruncateFree(), LHS, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::Value::replaceAllUsesWith(), llvm::LoopInfo::replacementPreservesLCSSAForm(), RHS, SCEV_DEBUG_WITH_TYPE, llvm::simplifyInstruction(), llvm::stable_sort(), and std::swap().
|
inline |
Definition at line 375 of file ScalarEvolutionExpander.h.
|
inline |
Set location information used by debugging information.
Definition at line 359 of file ScalarEvolutionExpander.h.
References llvm::IRBuilderBase::SetCurrentDebugLocation().
|
inline |
Set the current insertion point.
This is useful if multiple calls to expandCodeFor() are going to be made with the same insert point and the insert point may be moved during one of the expansions (e.g. if the insert point is not a block terminator).
Definition at line 349 of file ScalarEvolutionExpander.h.
References assert(), and llvm::IRBuilderBase::SetInsertPoint().
|
inline |
Set the current IV increment loop and position.
Definition at line 314 of file ScalarEvolutionExpander.h.
References assert().
|
inline |
Enable post-inc expansion for addrecs referring to the given loops.
Post-inc expansion is only supported in non-canonical mode.
Definition at line 323 of file ScalarEvolutionExpander.h.
References assert().
|
friend |
Definition at line 151 of file ScalarEvolutionExpander.h.