LLVM: include/llvm/Transforms/Utils/ScalarEvolutionExpander.h Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13#ifndef LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H
14#define LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H
15
27
28namespace llvm {
30
31
32
36
38
40
42};
43
52
55};
56
57
58
59
60
61
62
65
68
69
70 const char *IVName;
71
72
73 bool PreserveLCSSA;
74
75
77 InsertedExpressions;
78
79
82
83
84
85
87
88
89
91
92
94
95
97
98
99
100
101
103
104
105
106 const Loop *IVIncInsertLoop;
107
108
109
111
112
114
115
116
117
118
119
120
121
122 bool CanonicalMode;
123
124
125
126
127 bool LSRMode;
128
129
130
131
132 bool SafeUDivMode = false;
133
136
137
138
139
140
141
142 class SCEVInsertPointGuard {
148
149 SCEVInsertPointGuard(const SCEVInsertPointGuard &) = delete;
150 SCEVInsertPointGuard &operator=(const SCEVInsertPointGuard &) = delete;
151
152 public:
154 : Builder(B), Block(B.GetInsertBlock()), Point(B.GetInsertPoint()),
156 SE->InsertPointGuards.push_back(this);
157 }
158
159 ~SCEVInsertPointGuard() {
160
161
162
163 assert(SE->InsertPointGuards.back() == this);
164 SE->InsertPointGuards.pop_back();
167 }
168
171 };
172
173
174
176
177#if LLVM_ENABLE_ABI_BREAKING_CHECKS
178 const char *DebugType;
179#endif
180
182
183public:
184
186 const char *name, bool PreserveLCSSA = true)
187 : SE(se), DL(DL), IVName(name), PreserveLCSSA(PreserveLCSSA),
188 IVIncInsertLoop(nullptr), IVIncInsertPos(nullptr), CanonicalMode(true),
192 [this](Instruction *I) { rememberInstruction(I); })) {
193#if LLVM_ENABLE_ABI_BREAKING_CHECKS
194 DebugType = "";
195#endif
196 }
197
199
201 }
202
203#if LLVM_ENABLE_ABI_BREAKING_CHECKS
204 void setDebugType(const char *s) { DebugType = s; }
205#endif
206
207
208
209
211 InsertedExpressions.clear();
212 InsertedValues.clear();
213 InsertedPostIncValues.clear();
214 ReusedValues.clear();
215 OrigFlags.clear();
216 ChainedPhis.clear();
217 InsertedIVs.clear();
218 }
219
222
223
226 for (const auto &VH : InsertedValues) {
228 if (ReusedValues.contains(V))
229 continue;
230 if (auto *Inst = dyn_cast(V))
231 Result.push_back(Inst);
232 }
233 for (const auto &VH : InsertedPostIncValues) {
235 if (ReusedValues.contains(V))
236 continue;
237 if (auto *Inst = dyn_cast(V))
238 Result.push_back(Inst);
239 }
240
241 return Result;
242 }
243
244
245
246
247
248
249
253 assert(TTI && "This function requires TTI to be provided.");
254 assert(At && "This function requires At instruction to be provided.");
255 if ()
256 return true;
261 for (auto *Expr : Exprs)
263 while (!Worklist.empty()) {
265 if (isHighCostExpansionHelper(WorkItem, L, *At, Cost, ScaledBudget, *TTI,
266 Processed, Worklist))
267 return true;
268 }
269 assert(Cost <= ScaledBudget && "Should have returned from inner loop.");
270 return false;
271 }
272
273
275 bool allowScale);
276
277
278
279
280
281
282
284 bool RecomputePoisonFlags = false);
285
286
287
288
289
293
294
295
299
300
301
302
304
305
306
307
309
310
311
315 }
316
317
318
319
320
322
323
324
325
327
328
329
332
333
336
337
338
340
341
342
344
345
347 assert(!CanonicalMode &&
348 "IV increment positions are not supported in CanonicalMode");
349 IVIncInsertLoop = L;
350 IVIncInsertPos = Pos;
351 }
352
353
354
356 assert(!CanonicalMode &&
357 "Post-inc expansion is not supported in CanonicalMode");
358 PostIncLoops = L;
359 }
360
361
363 PostIncLoops.clear();
364
365
366
367 InsertedPostIncValues.clear();
368 }
369
370
371
372
374
376
377
378
379
380
384 }
385
388 }
389
390
391
393
394
397 }
398
399
402 }
403
404
405
406
408 return InsertedValues.count(I) || InsertedPostIncValues.count(I);
409 }
410
412
413
414
415
416
417
418
419
422
423
424
427
428private:
429 LLVMContext &getContext() const { return SE.getContext(); }
430
431
432 bool isHighCostExpansionHelper(const SCEVOperand &WorkItem, Loop *L,
433 const Instruction &At, InstructionCost &Cost,
434 unsigned Budget,
435 const TargetTransformInfo &TTI,
436 SmallPtrSetImpl<const SCEV *> &Processed,
437 SmallVectorImpl &Worklist);
438
439
440
441
444
445
447
448
449
450
453
454
455
456 Value *InsertNoopCastOfTo(Value *V, Type *Ty);
457
458
459
460 Value *expandAddToGEP(const SCEV *Op, Value *V, SCEV::NoWrapFlags Flags);
461
462
463
464
465 Value *FindValueInExprValueMap(
466 const SCEV *S, const Instruction *InsertPt,
467 SmallVectorImpl<Instruction *> &DropPoisonGeneratingInsts);
468
469 Value *expand(const SCEV *S);
473 }
474 Value *expand(const SCEV *S, Instruction *I) {
477 }
478
479
480 const Loop *getRelevantLoop(const SCEV *);
481
482 Value *expandMinMaxExpr(const SCEVNAryExpr *S, Intrinsic::ID IntrinID,
483 Twine Name, bool IsSequential = false);
484
485 Value *visitConstant(const SCEVConstant *S) { return S->getValue(); }
486
487 Value *visitVScale(const SCEVVScale *S);
488
489 Value *visitPtrToIntExpr(const SCEVPtrToIntExpr *S);
490
491 Value *visitTruncateExpr(const SCEVTruncateExpr *S);
492
493 Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);
494
495 Value *visitSignExtendExpr(const SCEVSignExtendExpr *S);
496
497 Value *visitAddExpr(const SCEVAddExpr *S);
498
499 Value *visitMulExpr(const SCEVMulExpr *S);
500
501 Value *visitUDivExpr(const SCEVUDivExpr *S);
502
503 Value *visitAddRecExpr(const SCEVAddRecExpr *S);
504
505 Value *visitSMaxExpr(const SCEVSMaxExpr *S);
506
507 Value *visitUMaxExpr(const SCEVUMaxExpr *S);
508
509 Value *visitSMinExpr(const SCEVSMinExpr *S);
510
511 Value *visitUMinExpr(const SCEVUMinExpr *S);
512
513 Value *visitSequentialUMinExpr(const SCEVSequentialUMinExpr *S);
514
515 Value *visitUnknown(const SCEVUnknown *S) { return S->getValue(); }
516
517 void rememberInstruction(Value *I);
518
519 void rememberFlags(Instruction *I);
520
521 bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
522
523 bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
524
525 Value *expandAddRecExprLiterally(const SCEVAddRecExpr *);
526 PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
527 const Loop *L, Type *&TruncTy,
528 bool &InvertStep);
529 Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L,
530 bool useSubtract);
531
532 void fixupInsertPoints(Instruction *I);
533
534
535
536 Value *fixupLCSSAFormFor(Value *V);
537
538
539
540
541 void replaceCongruentIVInc(PHINode *&Phi, PHINode *&OrigPhi, Loop *L,
542 const DominatorTree *DT,
543 SmallVectorImpl &DeadInsts);
544};
545
546
547
550
551
552
553 bool ResultUsed;
554
555public:
557 : Expander(Expander), ResultUsed(false) {}
558
560
561
563
565};
566}
567
568#endif
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.
This pass exposes codegen information to IR-level passes.
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.
Represents flags for the getelementptr instruction/expression.
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.
static bool canReuseFlagsFromOriginalIVInc(PHINode *OrigPhi, PHINode *WidePhi, Instruction *OrigInc, Instruction *WideInc)
Return true if both increments directly increment the corresponding IV PHI nodes and have the same op...
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.
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.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
@ TCC_Basic
The cost of a typical 'add' instruction.
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.
std::pair< iterator, bool > insert(const ValueT &V)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
This is an optimization pass for GlobalISel generic memory operations.
cl::opt< unsigned > SCEVCheapExpansionBudget
DWARFExpression::Operation Op
void apply(Instruction *I)
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.