Go to the documentation of this file.
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) {
132 SE->InsertPointGuards.push_back(
this);
135 ~SCEVInsertPointGuard() {
139 assert(SE->InsertPointGuards.back() ==
this);
140 SE->InsertPointGuards.pop_back();
142 Builder.SetCurrentDebugLocation(DbgLoc);
153 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
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
176 assert(InsertPointGuards.empty());
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();
365 return Builder.getCurrentDebugLocation();
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);
443 Value *expandAddToGEP(
const SCEV *
const *op_begin,
const SCEV *
const *op_end,
448 Value *FindValueInExprValueMap(
const SCEV *
S,
const Instruction *InsertPt);
453 const Loop *getRelevantLoop(
const SCEV *);
456 Twine
Name,
bool IsSequential =
false);
458 Value *visitConstant(
const SCEVConstant *
S) {
return S->getValue(); }
460 Value *visitPtrToIntExpr(
const SCEVPtrToIntExpr *
S);
462 Value *visitTruncateExpr(
const SCEVTruncateExpr *
S);
464 Value *visitZeroExtendExpr(
const SCEVZeroExtendExpr *
S);
466 Value *visitSignExtendExpr(
const SCEVSignExtendExpr *
S);
468 Value *visitAddExpr(
const SCEVAddExpr *
S);
470 Value *visitMulExpr(
const SCEVMulExpr *
S);
472 Value *visitUDivExpr(
const SCEVUDivExpr *
S);
474 Value *visitAddRecExpr(
const SCEVAddRecExpr *
S);
476 Value *visitSMaxExpr(
const SCEVSMaxExpr *
S);
478 Value *visitUMaxExpr(
const SCEVUMaxExpr *
S);
480 Value *visitSMinExpr(
const SCEVSMinExpr *
S);
482 Value *visitUMinExpr(
const SCEVUMinExpr *
S);
484 Value *visitSequentialUMinExpr(
const SCEVSequentialUMinExpr *
S);
486 Value *visitUnknown(
const SCEVUnknown *
S) {
return S->getValue(); }
488 void rememberInstruction(
Value *
I);
490 bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV,
const Loop *L);
492 bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV,
const Loop *L);
494 Value *expandAddRecExprLiterally(
const SCEVAddRecExpr *);
495 PHINode *getAddRecExprPHILiterally(
const SCEVAddRecExpr *Normalized,
496 const Loop *L,
Type *ExpandTy,
Type *IntTy,
497 Type *&TruncTy,
bool &InvertStep);
498 Value *expandIVInc(PHINode *PN,
Value *StepV,
const Loop *L,
Type *ExpandTy,
499 Type *IntTy,
bool useSubtract);
501 void fixupInsertPoints(Instruction *
I);
519 : Expander(Expander), ResultUsed(
false) {}
const SmallVectorImpl< WeakVH > & getInsertedIVs() const
LLVMContext & getContext() const
ScalarEvolution * getSE()
This is an optimization pass for GlobalISel generic memory operations.
A parsed version of the target data layout string in and methods for querying it.
InstListType::iterator iterator
Instruction iterators...
SCEVOperand(unsigned Opc, int Idx, const SCEV *S)
Represents a single loop in the control flow graph.
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
This class uses information about analyze scalars to rewrite expressions in canonical form.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
The main scalar evolution driver.
DebugLoc getCurrentDebugLocation() const
Get location information used by debugging information.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
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.
The instances of the Type class are immutable: once they are created, they are never changed.
void markResultUsed()
Indicate that the result of the expansion is used.
void clearPostInc()
Disable all post-inc expansion.
void setPostInc(const PostIncLoopSet &L)
Enable post-inc expansion for addrecs referring to the given loops.
struct for holding enough information to help calculate the cost of the given SCEV when expanded into...
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...
This class represents an assumption made using SCEV expressions which can be checked at run-time.
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.
void clearInsertPoint()
Clear the current insertion point.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
bool isInsertedInstruction(Instruction *I) const
Return true if the specified instruction was inserted by the code rewriter.
void setIVIncInsertPos(const Loop *L, Instruction *Pos)
Set the current IV increment loop and position.
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
const SCEV * S
The SCEV operand to be costed.
Value * generateOverflowCheck(const SCEVAddRecExpr *AR, Instruction *Loc, bool Signed)
Generates code that evaluates if the AR expression will overflow.
Implements a dense probed hash-table based set.
This class represents an analyzed expression in the program.
BasicBlock::iterator findInsertPointAfter(Instruction *I, Instruction *MustDominate) const
Returns a suitable insert point after I, that dominates MustDominate.
static Expected< BitVector > expand(StringRef S, StringRef Original)
Value * expandCodeFor(const SCEV *SH, Type *Ty=nullptr)
Insert code to directly compute the specified SCEV expression into the program.
Value * expandUnionPredicate(const SCEVUnionPredicate *Pred, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
multiplies can be turned into SHL s
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
This is an important class for using LLVM in a threaded context.
This class represents an assumption that the expression LHS Pred RHS evaluates to true,...
SCEVExpanderCleaner(SCEVExpander &Expander)
void disableCanonicalMode()
Disable the behavior of expanding expressions in canonical form rather than in a more literal form.
cl::opt< unsigned > SCEVCheapExpansionBudget
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...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Helper to remove instructions inserted during SCEV expansion, unless they are marked as used.
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
void clear()
Erase the contents of the InsertedExpressions map so that users trying to expand the same expression ...
SmallVector< Instruction *, 32 > getAllInsertedInstructions() const
Return a vector containing all instructions inserted during expansion.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Analysis the ScalarEvolution expression for r is this
InstSimplifyFolder - Use InstructionSimplify to fold operations to existing values.
void setInsertPoint(Instruction *IP)
Set the current insertion point.
bool hoistIVInc(Instruction *IncV, Instruction *InsertPos, bool RecomputePoisonFlags=false)
Utility for hoisting IncV (with all subexpressions requried for its computation) before InsertPos.
Common base class shared among various IRBuilders.
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
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
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
Value * getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L)
Try to find the ValueOffsetPair for S.
unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT, SmallVectorImpl< WeakTrackingVH > &DeadInsts, const TargetTransformInfo *TTI=nullptr)
replace congruent phis with their most canonical representative.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
This node represents a polynomial recurrence on the trip count of the specified loop.
This class represents an assumption made on an AddRec expression.
void setChainedPhi(PHINode *PN)
unsigned ParentOpcode
LLVM instruction opcode that uses the operand.
Value * expandComparePredicate(const SCEVComparePredicate *Pred, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
InsertPoint - A saved insertion point.
Value * expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc)
Generates a code sequence that evaluates this predicate.
Value handle that asserts if the Value is deleted.
Instruction * getIVIncOperand(Instruction *IncV, Instruction *InsertPos, bool allowScale)
Return the induction variable increment's IV operand.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Value * expandWrapPredicate(const SCEVWrapPredicate *P, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
SCEVExpander(ScalarEvolution &se, const DataLayout &DL, const char *name, bool PreserveLCSSA=true)
Construct a SCEVExpander in "canonical" mode.
bool contains(ConstPtrType Ptr) const
LLVM Value Representation.
reference emplace_back(ArgTypes &&... Args)