Go to the documentation of this file.
13 #ifndef LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H
14 #define LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H
96 const Loop *IVIncInsertLoop;
127 class SCEVInsertPointGuard {
134 SCEVInsertPointGuard(
const SCEVInsertPointGuard &) =
delete;
135 SCEVInsertPointGuard &operator=(
const SCEVInsertPointGuard &) =
delete;
139 :
Builder(
B), Block(
B.GetInsertBlock()), Point(
B.GetInsertPoint()),
140 DbgLoc(
B.getCurrentDebugLocation()), SE(SE) {
141 SE->InsertPointGuards.push_back(
this);
144 ~SCEVInsertPointGuard() {
148 assert(SE->InsertPointGuards.back() ==
this);
149 SE->InsertPointGuards.pop_back();
151 Builder.SetCurrentDebugLocation(DbgLoc);
163 const char *DebugType;
171 const char *
name,
bool PreserveLCSSA =
true)
172 : SE(se),
DL(
DL), IVName(
name), PreserveLCSSA(PreserveLCSSA),
173 IVIncInsertLoop(nullptr), IVIncInsertPos(nullptr), CanonicalMode(
true),
185 assert(InsertPointGuards.empty());
196 InsertedExpressions.clear();
197 InsertedValues.clear();
198 InsertedPostIncValues.clear();
199 ReusedValues.
clear();
208 for (
auto &VH : InsertedValues) {
212 if (
auto *Inst = dyn_cast<Instruction>(V))
213 Result.push_back(Inst);
215 for (
auto &VH : InsertedPostIncValues) {
219 if (
auto *Inst = dyn_cast<Instruction>(V))
220 Result.push_back(Inst);
235 assert(
TTI &&
"This function requires TTI to be provided.");
236 assert(At &&
"This function requires At instruction to be provided.");
244 while (!Worklist.empty()) {
246 if (isHighCostExpansionHelper(WorkItem, L, *At, Cost, ScaledBudget, *
TTI,
247 Processed, Worklist))
250 assert(Cost <= ScaledBudget &&
"Should have returned from inner loop.");
270 return expandCodeForImpl(SH, Ty,
I,
true);
278 return expandCodeForImpl(SH, Ty,
true);
305 "IV increment positions are not supported in CanonicalMode");
307 IVIncInsertPos = Pos;
314 "Post-inc expansion is not supported in CanonicalMode");
320 PostIncLoops.
clear();
324 InsertedPostIncValues.clear();
354 return Builder.getCurrentDebugLocation();
361 return InsertedValues.count(
I) || InsertedPostIncValues.count(
I);
395 Value *expandCodeForImpl(
const SCEV *SH,
Type *Ty,
bool Root);
401 Value *expandCodeForImpl(
const SCEV *SH,
Type *Ty, Instruction *
I,
bool Root);
404 bool isHighCostExpansionHelper(
const SCEVOperand &WorkItem, Loop *L,
405 const Instruction &At, InstructionCost &Cost,
407 const TargetTransformInfo &
TTI,
408 SmallPtrSetImpl<const SCEV *> &Processed,
409 SmallVectorImpl<SCEVOperand> &Worklist);
429 Value *expandAddToGEP(
const SCEV *
const *op_begin,
const SCEV *
const *op_end,
434 ScalarEvolution::ValueOffsetPair
435 FindValueInExprValueMap(
const SCEV *
S,
const Instruction *InsertPt);
440 const Loop *getRelevantLoop(
const SCEV *);
442 Value *visitConstant(
const SCEVConstant *
S) {
return S->getValue(); }
444 Value *visitPtrToIntExpr(
const SCEVPtrToIntExpr *
S);
446 Value *visitTruncateExpr(
const SCEVTruncateExpr *
S);
448 Value *visitZeroExtendExpr(
const SCEVZeroExtendExpr *
S);
450 Value *visitSignExtendExpr(
const SCEVSignExtendExpr *
S);
452 Value *visitAddExpr(
const SCEVAddExpr *
S);
454 Value *visitMulExpr(
const SCEVMulExpr *
S);
456 Value *visitUDivExpr(
const SCEVUDivExpr *
S);
458 Value *visitAddRecExpr(
const SCEVAddRecExpr *
S);
460 Value *visitSMaxExpr(
const SCEVSMaxExpr *
S);
462 Value *visitUMaxExpr(
const SCEVUMaxExpr *
S);
464 Value *visitSMinExpr(
const SCEVSMinExpr *
S);
466 Value *visitUMinExpr(
const SCEVUMinExpr *
S);
468 Value *visitUnknown(
const SCEVUnknown *
S) {
return S->getValue(); }
470 void rememberInstruction(
Value *
I);
472 bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV,
const Loop *L);
474 bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV,
const Loop *L);
476 Value *expandAddRecExprLiterally(
const SCEVAddRecExpr *);
477 PHINode *getAddRecExprPHILiterally(
const SCEVAddRecExpr *Normalized,
478 const Loop *L,
Type *ExpandTy,
Type *IntTy,
479 Type *&TruncTy,
bool &InvertStep);
480 Value *expandIVInc(PHINode *PN,
Value *StepV,
const Loop *L,
Type *ExpandTy,
481 Type *IntTy,
bool useSubtract);
483 void hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist,
484 Instruction *Pos, PHINode *LoopPhi);
486 void fixupInsertPoints(Instruction *
I);
491 Value *fixupLCSSAFormFor(Instruction *User,
unsigned OpIdx);
507 : Expander(Expander), DT(DT), ResultUsed(
false) {}
LLVMContext & getContext() const
ScalarEvolution * getSE()
This class represents lattice values for constants.
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.
The main scalar evolution driver.
SCEVExpanderCleaner(SCEVExpander &Expander, DominatorTree &DT)
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 setDebugType(const char *s)
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...
Optional< ScalarEvolution::ValueOffsetPair > getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L)
Try to find the ValueOffsetPair for S.
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.
bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE)
Return true if the given expression is safe to expand in the sense that all materialized values are s...
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.
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.
This class represents an assumption that two SCEV expressions are equal, and this can be checked at r...
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.
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
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.
TargetFolder - Create constants with target dependent folding.
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 * expandEqualPredicate(const SCEVEqualPredicate *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.
BasicBlock::iterator findInsertPointAfter(Instruction *I, Instruction *MustDominate)
Returns a suitable insert point after I, that dominates MustDominate.
Instruction * getIVIncOperand(Instruction *IncV, Instruction *InsertPos, bool allowScale)
Return the induction variable increment's IV operand.
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)