LLVM 20.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,constDataLayout &DL,constchar *name,bool PreserveLCSSA=true) | |
Construct aSCEVExpander 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 sameBasicBlock can do so. | |
ScalarEvolution * | getSE () |
constSmallVectorImpl<WeakVH > & | getInsertedIVs ()const |
SmallVector<Instruction *, 32 > | getAllInsertedInstructions ()const |
Return a vector containing all instructions inserted during expansion. | |
bool | isHighCostExpansion (ArrayRef<constSCEV * > Exprs,Loop *L,unsigned Budget,constTargetTransformInfo *TTI,constInstruction *At) |
Return true for expressions that can't be evaluated at runtime within givenBudget. | |
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 hoistingIncV (with all subexpressions requried for its computation) beforeInsertPos . | |
unsigned | replaceCongruentIVs (Loop *L,constDominatorTree *DT,SmallVectorImpl<WeakTrackingVH > &DeadInsts,constTargetTransformInfo *TTI=nullptr) |
replace congruent phis with their most canonical representative. | |
bool | isSafeToExpand (constSCEV *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 (constSCEV *S,constInstruction *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 (constSCEV *SH,Type *Ty,BasicBlock::iteratorI) |
Insert code to directly compute the specifiedSCEV expression into the program. | |
Value * | expandCodeFor (constSCEV *SH,Type *Ty,Instruction *I) |
Value * | expandCodeFor (constSCEV *SH,Type *Ty=nullptr) |
Insert code to directly compute the specifiedSCEV expression into the program. | |
Value * | expandCodeForPredicate (constSCEVPredicate *Pred,Instruction *Loc) |
Generates a code sequence that evaluates this predicate. | |
Value * | expandComparePredicate (constSCEVComparePredicate *Pred,Instruction *Loc) |
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for aSCEVComparePredicate. | |
Value * | generateOverflowCheck (constSCEVAddRecExpr *AR,Instruction *Loc,boolSigned) |
Generates code that evaluates if theAR expression will overflow. | |
Value * | expandWrapPredicate (constSCEVWrapPredicate *P,Instruction *Loc) |
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for aSCEVWrapPredicate. | |
Value * | expandUnionPredicate (constSCEVUnionPredicate *Pred,Instruction *Loc) |
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for aSCEVUnionPredicate. | |
void | setIVIncInsertPos (constLoop *L,Instruction *Pos) |
Set the current IV increment loop and position. | |
void | setPostInc (constPostIncLoopSet &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 | setInsertPoint (BasicBlock::iterator IP) |
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) |
bool | hasRelatedExistingExpansion (constSCEV *S,constInstruction *At,Loop *L) |
Determine whether there is an existing expansion of S that can be reused. | |
BasicBlock::iterator | findInsertPointAfter (Instruction *I,Instruction *MustDominate)const |
Returns a suitable insert point afterI , that dominatesMustDominate . | |
![]() | |
Value * | visit (constSCEV *S) |
Value * | visitCouldNotCompute (constSCEVCouldNotCompute *S) |
Static Public Member Functions | |
staticbool | canReuseFlagsFromOriginalIVInc (PHINode *OrigPhi,PHINode *WidePhi,Instruction *OrigInc,Instruction *WideInc) |
Return true if both increments directly increment the corresponding IV PHI nodes and have the same opcode. | |
Friends | |
class | SCEVExpanderCleaner |
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 line63 of fileScalarEvolutionExpander.h.
| inlineexplicit |
Construct aSCEVExpander in "canonical" mode.
Definition at line185 of fileScalarEvolutionExpander.h.
ReferencesI.
| inline |
Definition at line198 of fileScalarEvolutionExpander.h.
Referencesassert(), andllvm::SmallVectorBase< Size_T >::empty().
| static |
Return true if both increments directly increment the corresponding IV PHI nodes and have the same opcode.
It is not safe to re-use the flags from the original increment, if it is more complex andSCEV expansion may have yielded a more simplified wider increment.
Definition at line855 of fileScalarEvolutionExpander.cpp.
Referencesllvm::Instruction::getOpcode(),llvm::PatternMatch::m_c_BinOp(),llvm::PatternMatch::m_Specific(),llvm::PatternMatch::m_Value(), andllvm::PatternMatch::match().
| 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 sameBasicBlock can do so.
Definition at line210 of fileScalarEvolutionExpander.h.
Referencesllvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::clear(),llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::clear(),llvm::SmallPtrSetImplBase::clear(), andllvm::SmallVectorImpl< T >::clear().
Referenced byllvm::SCEVExpanderCleaner::cleanup(), andRunTermFold().
| 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 line392 of fileScalarEvolutionExpander.h.
Referencesllvm::IRBuilderBase::ClearInsertionPoint().
| inline |
Disable all post-inc expansion.
Definition at line362 of fileScalarEvolutionExpander.h.
Referencesllvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::clear(), andllvm::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 line373 of fileScalarEvolutionExpander.h.
| inline |
Definition at line375 of fileScalarEvolutionExpander.h.
Value * SCEVExpander::expandCodeFor | ( | constSCEV * | SH, |
Type * | Ty, | ||
BasicBlock::iterator | I | ||
) |
Insert code to directly compute the specifiedSCEV expression into the program.
The code is inserted into the specified block.
Definition at line1443 of fileScalarEvolutionExpander.cpp.
ReferencesexpandCodeFor(), andsetInsertPoint().
Referenced byllvm::addDiffRuntimeChecks(),calculateRtStride(),expandCodeFor(),llvm::LoopStructure::parseLoopStructure(),llvm::LoopConstrainer::run(),RunTermFold(),llvm::splitLoopBound(), andllvm::UnrollRuntimeLoopRemainder().
| inline |
Definition at line313 of fileScalarEvolutionExpander.h.
ReferencesexpandCodeFor(), andI.
Insert code to directly compute the specifiedSCEV expression into the program.
The code is inserted into theSCEVExpander'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 line1450 of fileScalarEvolutionExpander.cpp.
Referencesassert(),llvm::SCEV::getType(), andllvm::ScalarEvolution::getTypeSizeInBits().
Value * SCEVExpander::expandCodeForPredicate | ( | constSCEVPredicate * | Pred, |
Instruction * | Loc | ||
) |
Generates a code sequence that evaluates this predicate.
The inserted instructions will be at positionLoc
. The result will be of type i1 and will have a value of 0 when the predicate is false and 1 otherwise.
Definition at line2067 of fileScalarEvolutionExpander.cpp.
Referencesassert(),expandComparePredicate(),expandUnionPredicate(),expandWrapPredicate(),llvm::SCEVPredicate::getKind(),llvm_unreachable,llvm::SCEVPredicate::P_Compare,llvm::SCEVPredicate::P_Union, andllvm::SCEVPredicate::P_Wrap.
Referenced byexpandUnionPredicate().
Value * SCEVExpander::expandComparePredicate | ( | constSCEVComparePredicate * | Pred, |
Instruction * | Loc | ||
) |
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for aSCEVComparePredicate.
Definition at line2083 of fileScalarEvolutionExpander.cpp.
Referencesllvm::IRBuilderBase::CreateICmp(),llvm::CmpInst::getInversePredicate(),llvm::SCEVComparePredicate::getLHS(),llvm::SCEVComparePredicate::getPredicate(),llvm::SCEVComparePredicate::getRHS(),I, andllvm::IRBuilderBase::SetInsertPoint().
Referenced byexpandCodeForPredicate().
Value * SCEVExpander::expandUnionPredicate | ( | constSCEVUnionPredicate * | Pred, |
Instruction * | Loc | ||
) |
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for aSCEVUnionPredicate.
Definition at line2243 of fileScalarEvolutionExpander.cpp.
Referencesllvm::IRBuilderBase::CreateOr(),llvm::SmallVectorBase< Size_T >::empty(),expandCodeForPredicate(),llvm::Value::getContext(),llvm::ConstantInt::getFalse(),llvm::SmallVectorTemplateBase< T, bool >::push_back(), andllvm::IRBuilderBase::SetInsertPoint().
Referenced byexpandCodeForPredicate().
Value * SCEVExpander::expandWrapPredicate | ( | constSCEVWrapPredicate * | P, |
Instruction * | Loc | ||
) |
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for aSCEVWrapPredicate.
Definition at line2218 of fileScalarEvolutionExpander.cpp.
ReferencesA,llvm::IRBuilderBase::CreateOr(),generateOverflowCheck(),llvm::Value::getContext(),llvm::SCEVWrapPredicate::getExpr(),llvm::ConstantInt::getFalse(),llvm::SCEVWrapPredicate::getFlags(),llvm::SCEVWrapPredicate::IncrementNSSW, andllvm::SCEVWrapPredicate::IncrementNUSW.
Referenced byexpandCodeForPredicate().
BasicBlock::iterator SCEVExpander::findInsertPointAfter | ( | Instruction * | I, |
Instruction * | MustDominate | ||
) | const |
Returns a suitable insert point afterI
, that dominatesMustDominate
.
Skips instructions inserted by the expander.
Definition at line148 of fileScalarEvolutionExpander.cpp.
Referencesassert(),llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(),I,II, andisInsertedInstruction().
Value * SCEVExpander::generateOverflowCheck | ( | constSCEVAddRecExpr * | AR, |
Instruction * | Loc, | ||
bool | Signed | ||
) |
Generates code that evaluates if theAR
expression will overflow.
Definition at line2094 of fileScalarEvolutionExpander.cpp.
Referencesllvm::Add,assert(),llvm::IRBuilderBase::CreateAdd(),llvm::IRBuilderBase::CreateAnd(),llvm::IRBuilderBase::CreateExtractValue(),llvm::IRBuilderBase::CreateICmp(),llvm::IRBuilderBase::CreateIntrinsic(),llvm::IRBuilderBase::CreateNeg(),llvm::IRBuilderBase::CreateOr(),llvm::IRBuilderBase::CreatePtrAdd(),llvm::IRBuilderBase::CreateSelect(),llvm::IRBuilderBase::CreateSub(),llvm::IRBuilderBase::CreateZExtOrTrunc(),llvm::IntegerType::get(),llvm::Value::getContext(),llvm::ConstantInt::getFalse(),llvm::SCEVAddRecExpr::getLoop(),llvm::APInt::getMaxValue(),llvm::ScalarEvolution::getNegativeSCEV(),llvm::ScalarEvolution::getPredicatedSymbolicMaxBackedgeTakenCount(),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, andllvm::APInt::zext().
Referenced byexpandWrapPredicate().
| inline |
Return a vector containing all instructions inserted during expansion.
Definition at line224 of fileScalarEvolutionExpander.h.
Referencesllvm::SmallPtrSetImpl< PtrType >::contains().
Referenced byllvm::SCEVExpanderCleaner::cleanup().
| inline |
Get location information used by debugging information.
Definition at line400 of fileScalarEvolutionExpander.h.
| inline |
Definition at line221 of fileScalarEvolutionExpander.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 line742 of fileScalarEvolutionExpander.cpp.
Referencesllvm::DominatorTree::dominates(),llvm::drop_begin(),llvm::Instruction::getOpcode(),llvm::User::getOperand(), andllvm::User::operands().
Referenced byhoistIVInc().
| inline |
Definition at line220 of fileScalarEvolutionExpander.h.
Referenced byllvm::addDiffRuntimeChecks().
Determine whether there is an existing expansion of S that can be reused.
This is used to check whether S can be expanded cheaply.
L is a hint which tells in which loop to look for the suitable value.
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 line1809 of fileScalarEvolutionExpander.cpp.
Referencesllvm::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(), andRHS.
bool SCEVExpander::hoistIVInc | ( | Instruction * | IncV, |
Instruction * | InsertPos, | ||
bool | RecomputePoisonFlags =false | ||
) |
Utility for hoistingIncV
(with all subexpressions requried for its computation) beforeInsertPos
.
hoistStep - Attempt to hoist a simple IV increment above InsertPos to make it available to other uses in this loop.
IfRecomputePoisonFlags
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 line802 of fileScalarEvolutionExpander.cpp.
Referencesllvm::DominatorTree::dominates(),llvm::SCEV::FlagNSW,llvm::SCEV::FlagNUW,llvm::ilist_node_impl< OptionsT >::getIterator(),getIVIncOperand(),llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(),llvm::ScalarEvolution::getStrengthenedNoWrapFlagsFromBinOp(),I,llvm::ScalarEvolution::maskFlags(),llvm::LoopInfo::movementPreservesLCSSAForm(),llvm::SmallVectorTemplateBase< T, bool >::push_back(),llvm::reverse(),llvm::Instruction::setHasNoSignedWrap(), andllvm::Instruction::setHasNoUnsignedWrap().
| inline |
Return true for expressions that can't be evaluated at runtime within givenBudget.
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 line250 of fileScalarEvolutionExpander.h.
Referencesassert(),llvm::SmallVectorImpl< T >::emplace_back(),llvm::SmallVectorBase< Size_T >::empty(),llvm::SmallVectorImpl< T >::pop_back_val(), andllvm::TargetTransformInfo::TCC_Basic.
Referenced bycanFoldTermCondOfLoop(), andllvm::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 line407 of fileScalarEvolutionExpander.h.
Referencesllvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::count(), andI.
Referenced byfindInsertPointAfter().
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 line2353 of fileScalarEvolutionExpander.cpp.
Referencesllvm::visitAll().
Referenced bycanFoldTermCondOfLoop(),isSafeToExpandAt(), andRunTermFold().
bool SCEVExpander::isSafeToExpandAt | ( | constSCEV * | S, |
constInstruction * | 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 line2359 of fileScalarEvolutionExpander.cpp.
Referencesllvm::ScalarEvolution::dominates(),llvm::is_contained(),isSafeToExpand(), andllvm::ScalarEvolution::properlyDominates().
Referenced byllvm::LoopConstrainer::run().
unsigned SCEVExpander::replaceCongruentIVs | ( | Loop * | L, |
constDominatorTree * | DT, | ||
SmallVectorImpl<WeakTrackingVH > & | DeadInsts, | ||
constTargetTransformInfo * | 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 anySCEVExpander state but should be used in the same context thatSCEVExpander is used.
Definition at line1711 of fileScalarEvolutionExpander.cpp.
Referencesllvm::SmallVectorTemplateCommon< T, typename >::back(),llvm::IRBuilderBase::CreateTruncOrBitCast(),llvm::dbgs(),llvm::SmallVectorImpl< T >::emplace_back(),llvm::ScalarEvolution::forgetValue(),llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::getFixedValue(),llvm::Type::getPrimitiveSizeInBits(),llvm::ScalarEvolution::getSCEV(),llvm::ScalarEvolution::getTruncateExpr(),llvm::Value::getType(),llvm::Type::isIntegerTy(),llvm::Type::isPointerTy(),llvm::ScalarEvolution::isSCEVable(),llvm::TargetTransformInfo::isTruncateFree(),LHS,llvm::SmallVectorTemplateBase< T, bool >::push_back(),RHS,SCEV_DEBUG_WITH_TYPE,llvm::IRBuilderBase::SetCurrentDebugLocation(),llvm::simplifyInstruction(), andllvm::stable_sort().
| inline |
Definition at line411 of fileScalarEvolutionExpander.h.
Referencesllvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert().
| inline |
Set location information used by debugging information.
Definition at line395 of fileScalarEvolutionExpander.h.
| inline |
Definition at line386 of fileScalarEvolutionExpander.h.
Referencesllvm::IRBuilderBase::SetInsertPoint().
| inline |
Set the current insertion point.
This is useful if multiple calls toexpandCodeFor() 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 line381 of fileScalarEvolutionExpander.h.
Referencesassert(), andllvm::IRBuilderBase::SetInsertPoint().
Referenced byexpandCodeFor().
| inline |
Set the current IV increment loop and position.
Definition at line346 of fileScalarEvolutionExpander.h.
Referencesassert().
| inline |
Enable post-inc expansion for addrecs referring to the given loops.
Post-inc expansion is only supported in non-canonical mode.
Definition at line355 of fileScalarEvolutionExpander.h.
Referencesassert().
| friend |
Definition at line64 of fileScalarEvolutionExpander.h.
| friend |
Definition at line175 of fileScalarEvolutionExpander.h.