LLVM  13.0.0git
Classes | Public Member Functions | Friends | List of all members
llvm::SCEVExpander Class Reference

This class uses information about analyze scalars to rewrite expressions in canonical form. More...

#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"

Inheritance diagram for llvm::SCEVExpander:
Inheritance graph
[legend]
Collaboration diagram for llvm::SCEVExpander:
Collaboration graph
[legend]

Public Member Functions

 SCEVExpander (ScalarEvolution &se, const DataLayout &DL, const char *name, bool PreserveLCSSA=true)
 Construct a SCEVExpander in "canonical" mode. More...
 
 ~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. More...
 
ScalarEvolutiongetSE ()
 
SmallVector< Instruction *, 32 > getAllInsertedInstructions () const
 Return a vector containing all instructions inserted during expansion. More...
 
bool isHighCostExpansion (const SCEV *Expr, Loop *L, unsigned Budget, const TargetTransformInfo *TTI, const Instruction *At)
 Return true for expressions that can't be evaluated at runtime within given Budget. More...
 
InstructiongetIVIncOperand (Instruction *IncV, Instruction *InsertPos, bool allowScale)
 Return the induction variable increment's IV operand. More...
 
bool hoistIVInc (Instruction *IncV, Instruction *InsertPos)
 Utility for hoisting an IV increment. More...
 
unsigned replaceCongruentIVs (Loop *L, const DominatorTree *DT, SmallVectorImpl< WeakTrackingVH > &DeadInsts, const TargetTransformInfo *TTI=nullptr)
 replace congruent phis with their most canonical representative. More...
 
ValueexpandCodeFor (const SCEV *SH, Type *Ty, Instruction *I)
 Insert code to directly compute the specified SCEV expression into the program. More...
 
ValueexpandCodeFor (const SCEV *SH, Type *Ty=nullptr)
 Insert code to directly compute the specified SCEV expression into the program. More...
 
ValueexpandCodeForPredicate (const SCEVPredicate *Pred, Instruction *Loc)
 Generates a code sequence that evaluates this predicate. More...
 
ValueexpandEqualPredicate (const SCEVEqualPredicate *Pred, Instruction *Loc)
 A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a SCEVEqualPredicate. More...
 
ValuegenerateOverflowCheck (const SCEVAddRecExpr *AR, Instruction *Loc, bool Signed)
 Generates code that evaluates if the AR expression will overflow. More...
 
ValueexpandWrapPredicate (const SCEVWrapPredicate *P, Instruction *Loc)
 A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a SCEVWrapPredicate. More...
 
ValueexpandUnionPredicate (const SCEVUnionPredicate *Pred, Instruction *Loc)
 A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a SCEVUnionPredicate. More...
 
void setIVIncInsertPos (const Loop *L, Instruction *Pos)
 Set the current IV increment loop and position. More...
 
void setPostInc (const PostIncLoopSet &L)
 Enable post-inc expansion for addrecs referring to the given loops. More...
 
void clearPostInc ()
 Disable all post-inc expansion. More...
 
void disableCanonicalMode ()
 Disable the behavior of expanding expressions in canonical form rather than in a more literal form. More...
 
void enableLSRMode ()
 
void setInsertPoint (Instruction *IP)
 Set the current insertion point. More...
 
void clearInsertPoint ()
 Clear the current insertion point. More...
 
void SetCurrentDebugLocation (DebugLoc L)
 Set location information used by debugging information. More...
 
DebugLoc getCurrentDebugLocation () const
 Get location information used by debugging information. More...
 
bool isInsertedInstruction (Instruction *I) const
 Return true if the specified instruction was inserted by the code rewriter. More...
 
void setChainedPhi (PHINode *PN)
 
Optional< ScalarEvolution::ValueOffsetPair > getRelatedExistingExpansion (const SCEV *S, const Instruction *At, Loop *L)
 Try to find the ValueOffsetPair for S. More...
 
BasicBlock::iterator findInsertPointAfter (Instruction *I, Instruction *MustDominate) const
 Returns a suitable insert point after I, that dominates MustDominate. More...
 
- Public Member Functions inherited from llvm::SCEVVisitor< SCEVExpander, Value * >
Valuevisit (const SCEV *S)
 
ValuevisitCouldNotCompute (const SCEVCouldNotCompute *S)
 

Friends

struct SCEVVisitor< SCEVExpander, Value * >
 

Detailed Description

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 63 of file ScalarEvolutionExpander.h.

Constructor & Destructor Documentation

◆ SCEVExpander()

llvm::SCEVExpander::SCEVExpander ( ScalarEvolution se,
const DataLayout DL,
const char *  name,
bool  PreserveLCSSA = true 
)
inlineexplicit

Construct a SCEVExpander in "canonical" mode.

Definition at line 171 of file ScalarEvolutionExpander.h.

References I.

◆ ~SCEVExpander()

llvm::SCEVExpander::~SCEVExpander ( )
inline

Definition at line 184 of file ScalarEvolutionExpander.h.

References assert().

Member Function Documentation

◆ clear()

void llvm::SCEVExpander::clear ( )
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 196 of file ScalarEvolutionExpander.h.

References llvm::SmallPtrSetImplBase::clear().

◆ clearInsertPoint()

void llvm::SCEVExpander::clearInsertPoint ( )
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 346 of file ScalarEvolutionExpander.h.

References Builder.

◆ clearPostInc()

void llvm::SCEVExpander::clearPostInc ( )
inline

Disable all post-inc expansion.

Definition at line 320 of file ScalarEvolutionExpander.h.

References llvm::SmallPtrSetImplBase::clear().

◆ disableCanonicalMode()

void llvm::SCEVExpander::disableCanonicalMode ( )
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 331 of file ScalarEvolutionExpander.h.

◆ enableLSRMode()

void llvm::SCEVExpander::enableLSRMode ( )
inline

Definition at line 333 of file ScalarEvolutionExpander.h.

◆ expandCodeFor() [1/2]

Value* llvm::SCEVExpander::expandCodeFor ( const SCEV SH,
Type Ty,
Instruction I 
)
inline

Insert code to directly compute the specified SCEV expression into the program.

The code is inserted into the specified block.

Definition at line 270 of file ScalarEvolutionExpander.h.

References I.

Referenced by llvm::splitLoopBound(), and llvm::UnrollRuntimeLoopRemainder().

◆ expandCodeFor() [2/2]

Value* llvm::SCEVExpander::expandCodeFor ( const SCEV SH,
Type Ty = nullptr 
)
inline

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 278 of file ScalarEvolutionExpander.h.

◆ expandCodeForPredicate()

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 2469 of file ScalarEvolutionExpander.cpp.

References assert(), llvm::SCEVPredicate::getKind(), llvm_unreachable, llvm::SCEVPredicate::P_Equal, llvm::SCEVPredicate::P_Union, and llvm::SCEVPredicate::P_Wrap.

Referenced by GeneratedRTChecks::Create().

◆ expandEqualPredicate()

Value * SCEVExpander::expandEqualPredicate ( const SCEVEqualPredicate Pred,
Instruction Loc 
)

A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a SCEVEqualPredicate.

Definition at line 2485 of file ScalarEvolutionExpander.cpp.

References Builder, llvm::SCEVEqualPredicate::getLHS(), llvm::SCEVEqualPredicate::getRHS(), llvm::SCEV::getType(), and I.

◆ expandUnionPredicate()

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 2622 of file ScalarEvolutionExpander.cpp.

References Builder, Check(), llvm::IntegerType::get(), and llvm::Constant::getNullValue().

◆ expandWrapPredicate()

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 2597 of file ScalarEvolutionExpander.cpp.

References Builder, llvm::SCEVWrapPredicate::getExpr(), llvm::ConstantInt::getFalse(), llvm::SCEVWrapPredicate::getFlags(), llvm::SCEVWrapPredicate::IncrementNSSW, and llvm::SCEVWrapPredicate::IncrementNUSW.

◆ findInsertPointAfter()

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 100 of file ScalarEvolutionExpander.cpp.

References assert(), llvm::BasicBlock::getFirstInsertionPt(), llvm::Instruction::getParent(), and I.

◆ generateOverflowCheck()

Value * SCEVExpander::generateOverflowCheck ( const SCEVAddRecExpr AR,
Instruction Loc,
bool  Signed 
)

Generates code that evaluates if the AR expression will overflow.

Definition at line 2497 of file ScalarEvolutionExpander.cpp.

References assert(), llvm::SCEVAddRecExpr::getLoop(), llvm::SCEVAddRecExpr::getStepRecurrence(), and llvm::SCEVAddRecExpr::isAffine().

◆ getAllInsertedInstructions()

SmallVector<Instruction *, 32> llvm::SCEVExpander::getAllInsertedInstructions ( ) const
inline

Return a vector containing all instructions inserted during expansion.

Definition at line 207 of file ScalarEvolutionExpander.h.

References llvm::SmallPtrSetImpl< PtrType >::contains().

◆ getCurrentDebugLocation()

DebugLoc llvm::SCEVExpander::getCurrentDebugLocation ( ) const
inline

Get location information used by debugging information.

Definition at line 354 of file ScalarEvolutionExpander.h.

References Builder.

◆ getIVIncOperand()

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 987 of file ScalarEvolutionExpander.cpp.

References llvm::MCID::Add, llvm::drop_begin(), llvm::Type::getInt1PtrTy(), llvm::Type::getInt8PtrTy(), llvm::User::getNumOperands(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), and llvm::User::operands().

◆ getRelatedExistingExpansion()

Optional< ScalarEvolution::ValueOffsetPair > 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 2201 of file ScalarEvolutionExpander.cpp.

References BB, llvm::LoopBase< BlockT, LoopT >::getExitingBlocks(), llvm::PatternMatch::m_BasicBlock(), llvm::PatternMatch::m_Br(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Instruction(), llvm::PatternMatch::match(), llvm::None, and S.

◆ getSE()

ScalarEvolution* llvm::SCEVExpander::getSE ( )
inline

Definition at line 204 of file ScalarEvolutionExpander.h.

Referenced by GeneratedRTChecks::~GeneratedRTChecks().

◆ hoistIVInc()

bool SCEVExpander::hoistIVInc ( Instruction IncV,
Instruction InsertPos 
)

Utility for hoisting an IV increment.

hoistStep - Attempt to hoist a simple IV increment above InsertPos to make it available to other uses in this loop.

Recursively hoist any operands, until we reach a value that dominates InsertPos.

Definition at line 1054 of file ScalarEvolutionExpander.cpp.

References E, llvm::Instruction::getParent(), and I.

◆ isHighCostExpansion()

bool llvm::SCEVExpander::isHighCostExpansion ( const SCEV Expr,
Loop L,
unsigned  Budget,
const TargetTransformInfo TTI,
const Instruction At 
)
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 this expression. Sometimes this knowledge can lead to a less pessimistic cost estimation.

Definition at line 233 of file ScalarEvolutionExpander.h.

References assert(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::TargetTransformInfo::TCC_Basic.

Referenced by llvm::UnrollRuntimeLoopRemainder().

◆ isInsertedInstruction()

bool llvm::SCEVExpander::isInsertedInstruction ( Instruction I) const
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 361 of file ScalarEvolutionExpander.h.

References I.

Referenced by GeneratedRTChecks::~GeneratedRTChecks().

◆ replaceCongruentIVs()

unsigned SCEVExpander::replaceCongruentIVs ( Loop L,
const DominatorTree DT,
SmallVectorImpl< WeakTrackingVH > &  DeadInsts,
const TargetTransformInfo TTI = nullptr 
)

◆ setChainedPhi()

void llvm::SCEVExpander::setChainedPhi ( PHINode PN)
inline

Definition at line 365 of file ScalarEvolutionExpander.h.

◆ SetCurrentDebugLocation()

void llvm::SCEVExpander::SetCurrentDebugLocation ( DebugLoc  L)
inline

Set location information used by debugging information.

Definition at line 349 of file ScalarEvolutionExpander.h.

References Builder, and move.

◆ setInsertPoint()

void llvm::SCEVExpander::setInsertPoint ( Instruction IP)
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 339 of file ScalarEvolutionExpander.h.

References assert(), and Builder.

◆ setIVIncInsertPos()

void llvm::SCEVExpander::setIVIncInsertPos ( const Loop L,
Instruction Pos 
)
inline

Set the current IV increment loop and position.

Definition at line 304 of file ScalarEvolutionExpander.h.

References assert().

◆ setPostInc()

void llvm::SCEVExpander::setPostInc ( const PostIncLoopSet L)
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 313 of file ScalarEvolutionExpander.h.

References assert().

Friends And Related Function Documentation

◆ SCEVVisitor< SCEVExpander, Value * >

friend struct SCEVVisitor< SCEVExpander, Value * >
friend

Definition at line 167 of file ScalarEvolutionExpander.h.


The documentation for this class was generated from the following files: