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() {
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);
315 "IV increment positions are not supported in CanonicalMode");
317 IVIncInsertPos = Pos;
324 "Post-inc expansion is not supported in CanonicalMode");
330 PostIncLoops.
clear();
334 InsertedPostIncValues.clear();
375 return InsertedValues.count(
I) || InsertedPostIncValues.count(
I);
399 bool isHighCostExpansionHelper(
const SCEVOperand &
WorkItem, Loop *L,
400 const Instruction &At, InstructionCost &
Cost,
402 const TargetTransformInfo &
TTI,
403 SmallPtrSetImpl<const SCEV *> &Processed,
404 SmallVectorImpl<SCEVOperand> &Worklist);
423 Value *InsertNoopCastOfTo(Value *V,
Type *Ty);
427 Value *expandAddToGEP(
const SCEV *
Op, Value *V);
432 Value *FindValueInExprValueMap(
433 const SCEV *S,
const Instruction *InsertPt,
434 SmallVectorImpl<Instruction *> &DropPoisonGeneratingInsts);
436 Value *
expand(
const SCEV *S);
447 const Loop *getRelevantLoop(
const SCEV *);
450 Twine
Name,
bool IsSequential =
false);
452 Value *visitConstant(
const SCEVConstant *S) {
return S->getValue(); }
454 Value *visitVScale(
const SCEVVScale *S);
456 Value *visitPtrToIntExpr(
const SCEVPtrToIntExpr *S);
458 Value *visitTruncateExpr(
const SCEVTruncateExpr *S);
460 Value *visitZeroExtendExpr(
const SCEVZeroExtendExpr *S);
462 Value *visitSignExtendExpr(
const SCEVSignExtendExpr *S);
464 Value *visitAddExpr(
const SCEVAddExpr *S);
466 Value *visitMulExpr(
const SCEVMulExpr *S);
468 Value *visitUDivExpr(
const SCEVUDivExpr *S);
470 Value *visitAddRecExpr(
const SCEVAddRecExpr *S);
472 Value *visitSMaxExpr(
const SCEVSMaxExpr *S);
474 Value *visitUMaxExpr(
const SCEVUMaxExpr *S);
476 Value *visitSMinExpr(
const SCEVSMinExpr *S);
478 Value *visitUMinExpr(
const SCEVUMinExpr *S);
480 Value *visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *S);
482 Value *visitUnknown(
const SCEVUnknown *S) {
return S->getValue(); }
484 void rememberInstruction(Value *
I);
486 bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV,
const Loop *L);
488 bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV,
const Loop *L);
490 Value *expandAddRecExprLiterally(
const SCEVAddRecExpr *);
491 PHINode *getAddRecExprPHILiterally(
const SCEVAddRecExpr *Normalized,
492 const Loop *L,
Type *&TruncTy,
494 Value *expandIVInc(PHINode *PN, Value *StepV,
const Loop *L,
497 void fixupInsertPoints(Instruction *
I);
501 Value *fixupLCSSAFormFor(Value *V);
515 : 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.
static constexpr uint32_t Opcode
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 restoreIP(InsertPoint IP)
Sets the current insert point to a previously-saved location.
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.
bool hasRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L)
Determine whether there is an existing expansion of S that can be reused.
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...
void setInsertPoint(BasicBlock::iterator IP)
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.
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
Value * expandCodeFor(const SCEV *SH, Type *Ty, BasicBlock::iterator I)
Insert code to directly compute the specified SCEV expression into the program.
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)
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
DWARFExpression::Operation Op
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.