Go to the documentation of this file.
13 #ifndef LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H
14 #define LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H
36 bool CanonicalMode =
true);
100 const Loop *IVIncInsertLoop;
131 class SCEVInsertPointGuard {
138 SCEVInsertPointGuard(
const SCEVInsertPointGuard &) =
delete;
139 SCEVInsertPointGuard &operator=(
const SCEVInsertPointGuard &) =
delete;
143 :
Builder(
B), Block(
B.GetInsertBlock()), Point(
B.GetInsertPoint()),
144 DbgLoc(
B.getCurrentDebugLocation()), SE(SE) {
145 SE->InsertPointGuards.push_back(
this);
148 ~SCEVInsertPointGuard() {
152 assert(SE->InsertPointGuards.back() ==
this);
153 SE->InsertPointGuards.pop_back();
155 Builder.SetCurrentDebugLocation(DbgLoc);
166 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
175 const char *
name,
bool PreserveLCSSA =
true)
176 : SE(se),
DL(
DL), IVName(
name), PreserveLCSSA(PreserveLCSSA),
177 IVIncInsertLoop(nullptr), IVIncInsertPos(nullptr), CanonicalMode(
true),
182 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
189 assert(InsertPointGuards.empty());
192 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
193 void setDebugType(
const char *
s) {
DebugType =
s; }
200 InsertedExpressions.clear();
201 InsertedValues.clear();
202 InsertedPostIncValues.clear();
203 ReusedValues.
clear();
214 for (
auto &VH : InsertedValues) {
218 if (
auto *Inst = dyn_cast<Instruction>(V))
219 Result.push_back(Inst);
221 for (
auto &VH : InsertedPostIncValues) {
225 if (
auto *Inst = dyn_cast<Instruction>(V))
226 Result.push_back(Inst);
241 assert(
TTI &&
"This function requires TTI to be provided.");
242 assert(At &&
"This function requires At instruction to be provided.");
250 while (!Worklist.empty()) {
252 if (isHighCostExpansionHelper(WorkItem, L, *At, Cost, ScaledBudget, *
TTI,
253 Processed, Worklist))
256 assert(Cost <= ScaledBudget &&
"Should have returned from inner loop.");
276 return expandCodeForImpl(SH, Ty,
I,
true);
284 return expandCodeForImpl(SH, Ty,
true);
312 "IV increment positions are not supported in CanonicalMode");
314 IVIncInsertPos = Pos;
321 "Post-inc expansion is not supported in CanonicalMode");
327 PostIncLoops.
clear();
331 InsertedPostIncValues.clear();
361 return Builder.getCurrentDebugLocation();
368 return InsertedValues.count(
I) || InsertedPostIncValues.count(
I);
402 Value *expandCodeForImpl(
const SCEV *SH,
Type *Ty,
bool Root);
408 Value *expandCodeForImpl(
const SCEV *SH,
Type *Ty, Instruction *
I,
bool Root);
411 bool isHighCostExpansionHelper(
const SCEVOperand &WorkItem, Loop *L,
412 const Instruction &At, InstructionCost &Cost,
414 const TargetTransformInfo &
TTI,
415 SmallPtrSetImpl<const SCEV *> &Processed,
416 SmallVectorImpl<SCEVOperand> &Worklist);
439 Value *expandAddToGEP(
const SCEV *
const *op_begin,
const SCEV *
const *op_end,
444 Value *FindValueInExprValueMap(
const SCEV *
S,
const Instruction *InsertPt);
449 const Loop *getRelevantLoop(
const SCEV *);
452 Twine
Name,
bool IsSequential =
false);
454 Value *visitConstant(
const SCEVConstant *
S) {
return S->getValue(); }
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 *ExpandTy,
Type *IntTy,
493 Type *&TruncTy,
bool &InvertStep);
494 Value *expandIVInc(PHINode *PN,
Value *StepV,
const Loop *L,
Type *ExpandTy,
495 Type *IntTy,
bool useSubtract);
497 void fixupInsertPoints(Instruction *
I);
502 Value *fixupLCSSAFormFor(Instruction *User,
unsigned OpIdx);
516 : 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.
bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE, bool CanonicalMode=true)
Return true if the given expression is safe to expand in the sense that all materialized values are s...
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.
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.
bool hoistIVInc(Instruction *IncV, Instruction *InsertPos)
Utility for hoisting an IV increment.
LLVM_NODISCARD T pop_back_val()
struct for holding enough information to help calculate the cost of the given SCEV when expanded into...
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.
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.
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
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.
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.
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.
bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint, ScalarEvolution &SE)
Return true if the given expression is safe to expand in the sense that all materialized values are d...
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)