Go to the documentation of this file.
13 #ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
14 #define LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
82 return (
unsigned short)
Size.getZExtValue();
97 assert(
i == 0 &&
"Operand index out of range!");
194 const SCEV *
const *
O,
size_t N)
241 const SCEV *
const *
O,
size_t N)
265 return Op->getType()->isPointerTy();
268 Ty = (*FirstPointerTypedOp)->getType();
298 std::array<const SCEV *, 2>
Operands;
311 assert((
i == 0 ||
i == 1) &&
"Operand index out of range!");
430 const SCEV *
const *
O,
size_t N)
440 static bool classof(
const SCEV *
S) {
return isMinMaxType(
S->getSCEVType()); }
514 static bool isSequentialMinMaxType(
enum SCEVTypes T) {
524 const SCEV *
const *
O,
size_t N)
526 assert(isSequentialMinMaxType(
T));
535 assert(isSequentialMinMaxType(Ty));
549 return isSequentialMinMaxType(
S->getSCEVType());
588 void deleted()
override;
589 void allUsesReplacedWith(
Value *New)
override;
614 template <
typename SC,
typename RetVal =
void>
struct SCEVVisitor {
616 switch (
S->getSCEVType()) {
671 void push(
const SCEV *
S) {
672 if (Visited.
insert(
S).second && Visitor.follow(
S))
673 Worklist.push_back(
S);
681 while (!Worklist.empty() && !Visitor.isDone()) {
684 switch (
S->getSCEVType()) {
692 push(cast<SCEVCastExpr>(
S)->getOperand());
702 for (
const auto *
Op : cast<SCEVNAryExpr>(
S)->operands()) {
704 if (Visitor.isDone())
729 template <
typename PredTy>
735 FindClosure(PredTy Pred) : Pred(Pred) {}
737 bool follow(
const SCEV *
S) {
745 bool isDone()
const {
return Found; }
748 FindClosure
FC(Pred);
756 template <
typename SC>
776 assert(Result.second &&
"Should insert a new entry");
777 return Result.first->second;
812 bool Changed =
false;
822 bool Changed =
false;
839 bool Changed =
false;
844 return !Changed ? Expr
851 bool Changed =
false;
861 bool Changed =
false;
871 bool Changed =
false;
881 bool Changed =
false;
891 bool Changed =
false;
955 if (0 == Map.
count(L))
967 #endif // LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
void visitAll(const SCEV *Root)
This class represents a binary unsigned division operation.
This is an optimization pass for GlobalISel generic memory operations.
This class represents an unsigned minimum selection.
const SCEV * visitMulExpr(const SCEVMulExpr *Expr)
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a recurrence without clearing any previously set flags.
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
const SCEV * getStart() const
unsigned short computeExpressionSize(ArrayRef< const SCEV * > Args)
Represents a single loop in the control flow graph.
This class represents a signed maximum selection.
const SCEV * visitSMaxExpr(const SCEVSMaxExpr *Expr)
static const SCEV * rewrite(const SCEV *Scev, ScalarEvolution &SE, ValueToSCEVMapTy &Map)
const SCEV * visitCouldNotCompute(const SCEVCouldNotCompute *Expr)
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
const APInt & getValue() const
Return the constant as an APInt value reference.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
bool hasNoUnsignedWrap() const
This class represents a cast from a pointer to a pointer-sized integer value.
const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N)
const SCEV *const * Operands
const SCEV * getOperand() const
bool isAlignOf(Type *&AllocTy) const
The main scalar evolution driver.
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
bool isOffsetOf(Type *&STy, Constant *&FieldNo) const
const SCEV * visitUnknown(const SCEVUnknown *Expr)
The instances of the Type class are immutable: once they are created, they are never changed.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
const_iterator end(StringRef path)
Get end iterator over path.
SCEVTypes getEquivalentNonSequentialSCEVType() const
static LLVM_NODISCARD SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
Value * getValPtr() const
const SCEV * visitAddRecExpr(const SCEVAddRecExpr *Expr)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This node is the base class for sequential/in-order min/max selections.
SCEVTypes getSCEVType() const
This class represents a sign extension of a small integer value to a larger integer value.
LLVM_NODISCARD T pop_back_val()
ConstantInt * getValue() const
SCEVMinMaxExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N)
Note: Constructing subclasses via this constructor is allowed.
op_range operands() const
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This class represents a zero extension of a small integer value to a larger integer value.
const SCEV * visitPtrToIntExpr(const SCEVPtrToIntExpr *Expr)
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
Visit all nodes in the expression tree using worklist traversal.
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
This is the shared class of boolean and integer constants.
DenseMap< const SCEV *, const SCEV * > RewriteResults
This class defines a simple visitor class that may be used for various SCEV analysis purposes.
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the given expression tree.
Virtual Register Rewriter
@ SC
CHAIN = SC CHAIN, Imm128 - System call.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
SCEVNAryExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N)
const SCEV * getOperand(unsigned i) const
op_range operands() const
const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This class represents a truncation of an integer value to a smaller integer value.
const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
const SCEV * visitUnknown(const SCEVUnknown *Expr)
const SCEV * visitUDivExpr(const SCEVUDivExpr *Expr)
This requires reassociating to forms of expressions that are already something that reassoc doesn t think about yet These two functions should generate the same code on big endian int * l
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
SCEVParameterRewriter(ScalarEvolution &SE, ValueToSCEVMapTy &M)
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
This node represents multiplication of some number of SCEVs.
RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S)
This class represents an unsigned maximum selection.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
bool SCEVExprContains(const SCEV *Root, PredTy Pred)
Return true if any node in Root satisfies the predicate Pred.
static bool classof(const SCEV *S)
This node is a base class providing common functionality for n'ary operators.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
const SCEV * visitAddExpr(const SCEVAddExpr *Expr)
SCEVRewriteVisitor(ScalarEvolution &SE)
This node is the base class for n'ary commutative operators.
static SCEVTypes getEquivalentNonSequentialSCEVType(SCEVTypes Ty)
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
SCEVLoopAddRecRewriter(ScalarEvolution &SE, LoopToScevMapT &M)
mir Rename Register Operands
unsigned short SubclassData
This field is initialized to zero and may be used in subclasses to store miscellaneous information.
const SCEV * getOperand(unsigned i) const
This class represents an analyzed expression in the program.
This is an important base class in LLVM.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
op_iterator op_end() const
static const SCEV * rewrite(const SCEV *Scev, LoopToScevMapT &Map, ScalarEvolution &SE)
op_range operands() const
const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
bool hasNoSelfWrap() const
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
SCEVCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, const SCEV *op, Type *ty)
std::array< const SCEV *, 2 >::const_iterator op_iterator
const SCEV * getLHS() const
This visitor recursively visits a SCEV expression and re-writes it.
This class represents a constant integer value.
iterator find(const_arg_type_t< KeyT > Val)
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
static enum SCEVTypes negate(enum SCEVTypes T)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isQuadratic() const
Return true if this represents an expression A + B*x + C*x^2 where A, B and C are loop invariant valu...
An object of this class is returned by queries that could not be answered.
const SCEV * visitUMaxExpr(const SCEVUMaxExpr *Expr)
const SCEV * visit(const SCEV *S)
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
std::array< const SCEV *, 1 >::const_iterator op_iterator
Class for arbitrary precision integers.
const SCEV * visitUMinExpr(const SCEVUMinExpr *Expr)
std::array< const SCEV *, 1 > Operands
The SCEVParameterRewriter takes a scalar evolution expression and updates the SCEVUnknown components ...
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
size_t getNumOperands() const
This class represents a sequential/in-order unsigned minimum selection.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Type * getType() const
All values are typed, get the type of this value.
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
SCEVSequentialMinMaxExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N)
Note: Constructing subclasses via this constructor is allowed.
const SCEV * visitTruncateExpr(const SCEVTruncateExpr *Expr)
This node is the base class min/max selections.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
const SCEV * visitAddRecExpr(const SCEVAddRecExpr *Expr)
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
static bool classof(const SCEV *S)
const SCEV * visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr)
const Loop * getLoop() const
This class represents a signed minimum selection.
const SCEV * visitSMinExpr(const SCEVSMinExpr *Expr)
const SCEVAddRecExpr * getPostIncExpr(ScalarEvolution &SE) const
Return an expression representing the value of this expression one iteration of the loop ahead.
This is the base class for unary cast operator classes.
const SCEV * getNumIterationsInRange(const ConstantRange &Range, ScalarEvolution &SE) const
Return the number of iterations of this loop that produce values in the specified constant range.
op_iterator op_begin() const
This node represents a polynomial recurrence on the trip count of the specified loop.
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
const SCEV * getRHS() const
SCEVIntegralCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, const SCEV *op, Type *ty)
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a non-recurrence without clearing previously set flags.
RetVal visit(const SCEV *S)
const SCEV * visitSignExtendExpr(const SCEVSignExtendExpr *Expr)
Value handle with callbacks on RAUW and destruction.
This class represents a range of values.
const APInt & getAPInt() const
FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID,...
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
const SCEV * visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Expr)
const SCEV *const * op_iterator
This is the base class for unary integral cast operator classes.
const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
This node represents an addition of some number of SCEVs.
bool hasNoSignedWrap() const
const SCEV * visitConstant(const SCEVConstant *Constant)
A range adaptor for a pair of iterators.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Type * getType() const
Return the LLVM type of this SCEV expression.
const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
size_t getNumOperands() const
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
const SCEV * getOperand(unsigned i) const
size_t getNumOperands() const
The SCEVLoopAddRecRewriter takes a scalar evolution expression and applies the Map (Loop -> SCEV) to ...
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
LLVM Value Representation.
bool isSizeOf(Type *&AllocTy) const
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.