13#ifndef LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H
14#define LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H
87 const Loop *IVIncInsertLoop;
118 class SCEVInsertPointGuard {
125 SCEVInsertPointGuard(
const SCEVInsertPointGuard &) =
delete;
126 SCEVInsertPointGuard &operator=(
const SCEVInsertPointGuard &) =
delete;
130 :
Builder(
B), Block(
B.GetInsertBlock()), Point(
B.GetInsertPoint()),
131 DbgLoc(
B.getCurrentDebugLocation()), SE(SE) {
135 ~SCEVInsertPointGuard() {
142 Builder.SetCurrentDebugLocation(DbgLoc);
153#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
154 const char *DebugType;
162 const char *
name,
bool PreserveLCSSA =
true)
163 : SE(se),
DL(
DL), IVName(
name), PreserveLCSSA(PreserveLCSSA),
164 IVIncInsertLoop(nullptr), IVIncInsertPos(nullptr), CanonicalMode(
true),
169#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
179#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
180 void setDebugType(
const char *s) { DebugType = s; }
187 InsertedExpressions.clear();
188 InsertedValues.clear();
189 InsertedPostIncValues.clear();
190 ReusedValues.
clear();
201 for (
const auto &VH : InsertedValues) {
205 if (
auto *Inst = dyn_cast<Instruction>(V))
206 Result.push_back(Inst);
208 for (
const auto &VH : InsertedPostIncValues) {
212 if (
auto *Inst = dyn_cast<Instruction>(V))
213 Result.push_back(Inst);
228 assert(
TTI &&
"This function requires TTI to be provided.");
229 assert(At &&
"This function requires At instruction to be provided.");
236 for (
auto *Expr : Exprs)
238 while (!Worklist.
empty()) {
240 if (isHighCostExpansionHelper(
WorkItem, L, *At,
Cost, ScaledBudget, *
TTI,
241 Processed, Worklist))
244 assert(
Cost <= ScaledBudget &&
"Should have returned from inner loop.");
259 bool RecomputePoisonFlags =
false);
280 return expandCodeForImpl(SH, Ty,
I);
288 return expandCodeForImpl(SH, Ty);
316 "IV increment positions are not supported in CanonicalMode");
318 IVIncInsertPos = Pos;
325 "Post-inc expansion is not supported in CanonicalMode");
331 PostIncLoops.
clear();
335 InsertedPostIncValues.clear();
372 return InsertedValues.count(
I) || InsertedPostIncValues.count(
I);
406 Value *expandCodeForImpl(
const SCEV *SH,
Type *Ty);
412 Value *expandCodeForImpl(
const SCEV *SH,
Type *Ty, Instruction *
I);
415 bool isHighCostExpansionHelper(
const SCEVOperand &
WorkItem, Loop *L,
416 const Instruction &At, InstructionCost &
Cost,
418 const TargetTransformInfo &
TTI,
419 SmallPtrSetImpl<const SCEV *> &Processed,
420 SmallVectorImpl<SCEVOperand> &Worklist);
439 Value *InsertNoopCastOfTo(Value *V,
Type *Ty);
443 Value *expandAddToGEP(
const SCEV *
const *op_begin,
const SCEV *
const *op_end,
445 Value *expandAddToGEP(
const SCEV *Op,
PointerType *PTy,
Type *Ty, Value *V);
448 Value *FindValueInExprValueMap(
const SCEV *S,
const Instruction *InsertPt);
450 Value *
expand(
const SCEV *S);
453 const Loop *getRelevantLoop(
const SCEV *);
455 Value *expandMinMaxExpr(
const SCEVNAryExpr *S,
Intrinsic::ID IntrinID,
456 Twine
Name,
bool IsSequential =
false);
458 Value *visitConstant(
const SCEVConstant *S) {
return S->getValue(); }
460 Value *visitVScale(
const SCEVVScale *S);
462 Value *visitPtrToIntExpr(
const SCEVPtrToIntExpr *S);
464 Value *visitTruncateExpr(
const SCEVTruncateExpr *S);
466 Value *visitZeroExtendExpr(
const SCEVZeroExtendExpr *S);
468 Value *visitSignExtendExpr(
const SCEVSignExtendExpr *S);
470 Value *visitAddExpr(
const SCEVAddExpr *S);
472 Value *visitMulExpr(
const SCEVMulExpr *S);
474 Value *visitUDivExpr(
const SCEVUDivExpr *S);
476 Value *visitAddRecExpr(
const SCEVAddRecExpr *S);
478 Value *visitSMaxExpr(
const SCEVSMaxExpr *S);
480 Value *visitUMaxExpr(
const SCEVUMaxExpr *S);
482 Value *visitSMinExpr(
const SCEVSMinExpr *S);
484 Value *visitUMinExpr(
const SCEVUMinExpr *S);
486 Value *visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *S);
488 Value *visitUnknown(
const SCEVUnknown *S) {
return S->getValue(); }
490 void rememberInstruction(Value *
I);
492 bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV,
const Loop *L);
494 bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV,
const Loop *L);
496 Value *expandAddRecExprLiterally(
const SCEVAddRecExpr *);
497 PHINode *getAddRecExprPHILiterally(
const SCEVAddRecExpr *Normalized,
498 const Loop *L,
Type *ExpandTy,
Type *IntTy,
499 Type *&TruncTy,
bool &InvertStep);
500 Value *expandIVInc(PHINode *PN, Value *StepV,
const Loop *L,
Type *ExpandTy,
501 Type *IntTy,
bool useSubtract);
503 void fixupInsertPoints(Instruction *
I);
507 Value *fixupLCSSAFormFor(Value *V);
521 : Expander(Expander), ResultUsed(
false) {}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
static Expected< BitVector > expand(StringRef S, StringRef Original)
This file defines an InstructionCost class that is used when calculating the cost of an instruction,...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Value handle that asserts if the Value is deleted.
InstListType::iterator iterator
Instruction iterators...
A parsed version of the target data layout string in and methods for querying it.
Implements a dense probed hash-table based set.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
InsertPoint - A saved insertion point.
Common base class shared among various IRBuilders.
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
DebugLoc getCurrentDebugLocation() const
Get location information used by debugging information.
void ClearInsertionPoint()
Clear the insertion point: created instructions will not be inserted into a block.
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
InstSimplifyFolder - Use InstructionSimplify to fold operations to existing values.
This is an important class for using LLVM in a threaded context.
Represents a single loop in the control flow graph.
This node represents a polynomial recurrence on the trip count of the specified loop.
This class represents an assumption that the expression LHS Pred RHS evaluates to true,...
Helper to remove instructions inserted during SCEV expansion, unless they are marked as used.
SCEVExpanderCleaner(SCEVExpander &Expander)
void markResultUsed()
Indicate that the result of the expansion is used.
This class uses information about analyze scalars to rewrite expressions in canonical form.
Value * generateOverflowCheck(const SCEVAddRecExpr *AR, Instruction *Loc, bool Signed)
Generates code that evaluates if the AR expression will overflow.
SmallVector< Instruction *, 32 > getAllInsertedInstructions() const
Return a vector containing all instructions inserted during expansion.
void setChainedPhi(PHINode *PN)
bool isSafeToExpand(const SCEV *S) const
Return true if the given expression is safe to expand in the sense that all materialized values are s...
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.
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 d...
ScalarEvolution * getSE()
unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT, SmallVectorImpl< WeakTrackingVH > &DeadInsts, const TargetTransformInfo *TTI=nullptr)
replace congruent phis with their most canonical representative.
void clearInsertPoint()
Clear the current insertion point.
Value * expandCodeFor(const SCEV *SH, Type *Ty=nullptr)
Insert code to directly compute the specified SCEV expression into the program.
Value * getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L)
Try to find the ValueOffsetPair for S.
void clearPostInc()
Disable all post-inc expansion.
SCEVExpander(ScalarEvolution &se, const DataLayout &DL, const char *name, bool PreserveLCSSA=true)
Construct a SCEVExpander in "canonical" mode.
Value * expandUnionPredicate(const SCEVUnionPredicate *Pred, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
bool hoistIVInc(Instruction *IncV, Instruction *InsertPos, bool RecomputePoisonFlags=false)
Utility for hoisting IncV (with all subexpressions requried for its computation) before InsertPos.
void clear()
Erase the contents of the InsertedExpressions map so that users trying to expand the same expression ...
bool isInsertedInstruction(Instruction *I) const
Return true if the specified instruction was inserted by the code rewriter.
Value * expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc)
Generates a code sequence that evaluates this predicate.
void setPostInc(const PostIncLoopSet &L)
Enable post-inc expansion for addrecs referring to the given loops.
DebugLoc getCurrentDebugLocation() const
Get location information used by debugging information.
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Value * expandComparePredicate(const SCEVComparePredicate *Pred, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
void setIVIncInsertPos(const Loop *L, Instruction *Pos)
Set the current IV increment loop and position.
const SmallVectorImpl< WeakVH > & getInsertedIVs() const
void disableCanonicalMode()
Disable the behavior of expanding expressions in canonical form rather than in a more literal form.
Value * expandWrapPredicate(const SCEVWrapPredicate *P, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
Instruction * getIVIncOperand(Instruction *IncV, Instruction *InsertPos, bool allowScale)
Return the induction variable increment's IV operand.
BasicBlock::iterator findInsertPointAfter(Instruction *I, Instruction *MustDominate) const
Returns a suitable insert point after I, that dominates MustDominate.
void setInsertPoint(Instruction *IP)
Set the current insertion point.
This class represents an assumption made using SCEV expressions which can be checked at run-time.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
This class represents an assumption made on an AddRec expression.
This class represents an analyzed expression in the program.
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
The main scalar evolution driver.
LLVMContext & getContext() const
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Value handle that tracks a Value across RAUW.
The instances of the Type class are immutable: once they are created, they are never changed.
LLVM Value Representation.
This is an optimization pass for GlobalISel generic memory operations.
cl::opt< unsigned > SCEVCheapExpansionBudget
struct for holding enough information to help calculate the cost of the given SCEV when expanded into...
const SCEV * S
The SCEV operand to be costed.
unsigned ParentOpcode
LLVM instruction opcode that uses the operand.
SCEVOperand(unsigned Opc, int Idx, const SCEV *S)
int OperandIdx
The use index of an expanded instruction.
This class defines a simple visitor class that may be used for various SCEV analysis purposes.