LLVM 19.0.0git
ScalarEvolutionExpander.h
Go to the documentation of this file.
1//===---- llvm/Analysis/ScalarEvolutionExpander.h - SCEV Exprs --*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines the classes used to generate code from scalar expressions.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H
14#define LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H
15
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/DenseSet.h"
23#include "llvm/IR/IRBuilder.h"
24#include "llvm/IR/ValueHandle.h"
27
28namespace llvm {
29extern cl::opt<unsigned> SCEVCheapExpansionBudget;
30
31/// struct for holding enough information to help calculate the cost of the
32/// given SCEV when expanded into IR.
34 explicit SCEVOperand(unsigned Opc, int Idx, const SCEV *S) :
35 ParentOpcode(Opc), OperandIdx(Idx), S(S) { }
36 /// LLVM instruction opcode that uses the operand.
37 unsigned ParentOpcode;
38 /// The use index of an expanded instruction.
40 /// The SCEV operand to be costed.
41 const SCEV* S;
42};
43
45 unsigned NUW : 1;
46 unsigned NSW : 1;
47 unsigned Exact : 1;
48 unsigned Disjoint : 1;
49 unsigned NNeg : 1;
50
52 void apply(Instruction *I);
53};
54
55/// This class uses information about analyze scalars to rewrite expressions
56/// in canonical form.
57///
58/// Clients should create an instance of this class when rewriting is needed,
59/// and destroy it when finished to allow the release of the associated
60/// memory.
61class SCEVExpander : public SCEVVisitor<SCEVExpander, Value *> {
62 friend class SCEVExpanderCleaner;
63
65 const DataLayout &DL;
66
67 // New instructions receive a name to identify them with the current pass.
68 const char *IVName;
69
70 /// Indicates whether LCSSA phis should be created for inserted values.
71 bool PreserveLCSSA;
72
73 // InsertedExpressions caches Values for reuse, so must track RAUW.
75 InsertedExpressions;
76
77 // InsertedValues only flags inserted instructions so needs no RAUW.
78 DenseSet<AssertingVH<Value>> InsertedValues;
79 DenseSet<AssertingVH<Value>> InsertedPostIncValues;
80
81 /// Keep track of the existing IR values re-used during expansion.
82 /// FIXME: Ideally re-used instructions would not be added to
83 /// InsertedValues/InsertedPostIncValues.
84 SmallPtrSet<Value *, 16> ReusedValues;
85
86 /// Original flags of instructions for which they were modified. Used
87 /// by SCEVExpanderCleaner to undo changes.
89
90 // The induction variables generated.
91 SmallVector<WeakVH, 2> InsertedIVs;
92
93 /// A memoization of the "relevant" loop for a given SCEV.
95
96 /// Addrecs referring to any of the given loops are expanded in post-inc
97 /// mode. For example, expanding {1,+,1}<L> in post-inc mode returns the add
98 /// instruction that adds one to the phi for {0,+,1}<L>, as opposed to a new
99 /// phi starting at 1. This is only supported in non-canonical mode.
100 PostIncLoopSet PostIncLoops;
101
102 /// When this is non-null, addrecs expanded in the loop it indicates should
103 /// be inserted with increments at IVIncInsertPos.
104 const Loop *IVIncInsertLoop;
105
106 /// When expanding addrecs in the IVIncInsertLoop loop, insert the IV
107 /// increment at this position.
108 Instruction *IVIncInsertPos;
109
110 /// Phis that complete an IV chain. Reuse
112
113 /// When true, SCEVExpander tries to expand expressions in "canonical" form.
114 /// When false, expressions are expanded in a more literal form.
115 ///
116 /// In "canonical" form addrecs are expanded as arithmetic based on a
117 /// canonical induction variable. Note that CanonicalMode doesn't guarantee
118 /// that all expressions are expanded in "canonical" form. For some
119 /// expressions literal mode can be preferred.
120 bool CanonicalMode;
121
122 /// When invoked from LSR, the expander is in "strength reduction" mode. The
123 /// only difference is that phi's are only reused if they are already in
124 /// "expanded" form.
125 bool LSRMode;
126
128 BuilderType Builder;
129
130 // RAII object that stores the current insertion point and restores it when
131 // the object is destroyed. This includes the debug location. Duplicated
132 // from InsertPointGuard to add SetInsertPoint() which is used to updated
133 // InsertPointGuards stack when insert points are moved during SCEV
134 // expansion.
135 class SCEVInsertPointGuard {
136 IRBuilderBase &Builder;
139 DebugLoc DbgLoc;
140 SCEVExpander *SE;
141
142 SCEVInsertPointGuard(const SCEVInsertPointGuard &) = delete;
143 SCEVInsertPointGuard &operator=(const SCEVInsertPointGuard &) = delete;
144
145 public:
146 SCEVInsertPointGuard(IRBuilderBase &B, SCEVExpander *SE)
147 : Builder(B), Block(B.GetInsertBlock()), Point(B.GetInsertPoint()),
148 DbgLoc(B.getCurrentDebugLocation()), SE(SE) {
149 SE->InsertPointGuards.push_back(this);
150 }
151
152 ~SCEVInsertPointGuard() {
153 // These guards should always created/destroyed in FIFO order since they
154 // are used to guard lexically scoped blocks of code in
155 // ScalarEvolutionExpander.
156 assert(SE->InsertPointGuards.back() == this);
157 SE->InsertPointGuards.pop_back();
158 Builder.restoreIP(IRBuilderBase::InsertPoint(Block, Point));
159 Builder.SetCurrentDebugLocation(DbgLoc);
160 }
161
162 BasicBlock::iterator GetInsertPoint() const { return Point; }
163 void SetInsertPoint(BasicBlock::iterator I) { Point = I; }
164 };
165
166 /// Stack of pointers to saved insert points, used to keep insert points
167 /// consistent when instructions are moved.
169
170#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
171 const char *DebugType;
172#endif
173
174 friend struct SCEVVisitor<SCEVExpander, Value *>;
175
176public:
177 /// Construct a SCEVExpander in "canonical" mode.
179 const char *name, bool PreserveLCSSA = true)
180 : SE(se), DL(DL), IVName(name), PreserveLCSSA(PreserveLCSSA),
181 IVIncInsertLoop(nullptr), IVIncInsertPos(nullptr), CanonicalMode(true),
182 LSRMode(false),
183 Builder(se.getContext(), InstSimplifyFolder(DL),
185 [this](Instruction *I) { rememberInstruction(I); })) {
186#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
187 DebugType = "";
188#endif
189 }
190
192 // Make sure the insert point guard stack is consistent.
193 assert(InsertPointGuards.empty());
194 }
195
196#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
197 void setDebugType(const char *s) { DebugType = s; }
198#endif
199
200 /// Erase the contents of the InsertedExpressions map so that users trying
201 /// to expand the same expression into multiple BasicBlocks or different
202 /// places within the same BasicBlock can do so.
203 void clear() {
204 InsertedExpressions.clear();
205 InsertedValues.clear();
206 InsertedPostIncValues.clear();
207 ReusedValues.clear();
208 OrigFlags.clear();
209 ChainedPhis.clear();
210 InsertedIVs.clear();
211 }
212
213 ScalarEvolution *getSE() { return &SE; }
214 const SmallVectorImpl<WeakVH> &getInsertedIVs() const { return InsertedIVs; }
215
216 /// Return a vector containing all instructions inserted during expansion.
219 for (const auto &VH : InsertedValues) {
220 Value *V = VH;
221 if (ReusedValues.contains(V))
222 continue;
223 if (auto *Inst = dyn_cast<Instruction>(V))
224 Result.push_back(Inst);
225 }
226 for (const auto &VH : InsertedPostIncValues) {
227 Value *V = VH;
228 if (ReusedValues.contains(V))
229 continue;
230 if (auto *Inst = dyn_cast<Instruction>(V))
231 Result.push_back(Inst);
232 }
233
234 return Result;
235 }
236
237 /// Return true for expressions that can't be evaluated at runtime
238 /// within given \b Budget.
239 ///
240 /// \p At is a parameter which specifies point in code where user is going to
241 /// expand these expressions. Sometimes this knowledge can lead to
242 /// a less pessimistic cost estimation.
244 unsigned Budget, const TargetTransformInfo *TTI,
245 const Instruction *At) {
246 assert(TTI && "This function requires TTI to be provided.");
247 assert(At && "This function requires At instruction to be provided.");
248 if (!TTI) // In assert-less builds, avoid crashing
249 return true; // by always claiming to be high-cost.
253 unsigned ScaledBudget = Budget * TargetTransformInfo::TCC_Basic;
254 for (auto *Expr : Exprs)
255 Worklist.emplace_back(-1, -1, Expr);
256 while (!Worklist.empty()) {
257 const SCEVOperand WorkItem = Worklist.pop_back_val();
258 if (isHighCostExpansionHelper(WorkItem, L, *At, Cost, ScaledBudget, *TTI,
259 Processed, Worklist))
260 return true;
261 }
262 assert(Cost <= ScaledBudget && "Should have returned from inner loop.");
263 return false;
264 }
265
266 /// Return the induction variable increment's IV operand.
268 bool allowScale);
269
270 /// Utility for hoisting \p IncV (with all subexpressions requried for its
271 /// computation) before \p InsertPos. If \p RecomputePoisonFlags is set, drops
272 /// all poison-generating flags from instructions being hoisted and tries to
273 /// re-infer them in the new location. It should be used when we are going to
274 /// introduce a new use in the new position that didn't exist before, and may
275 /// trigger new UB in case of poison.
276 bool hoistIVInc(Instruction *IncV, Instruction *InsertPos,
277 bool RecomputePoisonFlags = false);
278
279 /// Return true if both increments directly increment the corresponding IV PHI
280 /// nodes and have the same opcode. It is not safe to re-use the flags from
281 /// the original increment, if it is more complex and SCEV expansion may have
282 /// yielded a more simplified wider increment.
283 static bool canReuseFlagsFromOriginalIVInc(PHINode *OrigPhi, PHINode *WidePhi,
284 Instruction *OrigInc,
285 Instruction *WideInc);
286
287 /// replace congruent phis with their most canonical representative. Return
288 /// the number of phis eliminated.
289 unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT,
291 const TargetTransformInfo *TTI = nullptr);
292
293 /// Return true if the given expression is safe to expand in the sense that
294 /// all materialized values are safe to speculate anywhere their operands are
295 /// defined, and the expander is capable of expanding the expression.
296 bool isSafeToExpand(const SCEV *S) const;
297
298 /// Return true if the given expression is safe to expand in the sense that
299 /// all materialized values are defined and safe to speculate at the specified
300 /// location and their operands are defined at this location.
301 bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint) const;
302
303 /// Insert code to directly compute the specified SCEV expression into the
304 /// program. The code is inserted into the specified block.
307 return expandCodeFor(SH, Ty, I->getIterator());
308 }
309
310 /// Insert code to directly compute the specified SCEV expression into the
311 /// program. The code is inserted into the SCEVExpander's current
312 /// insertion point. If a type is specified, the result will be expanded to
313 /// have that type, with a cast if necessary.
314 Value *expandCodeFor(const SCEV *SH, Type *Ty = nullptr);
315
316 /// Generates a code sequence that evaluates this predicate. The inserted
317 /// instructions will be at position \p Loc. The result will be of type i1
318 /// and will have a value of 0 when the predicate is false and 1 otherwise.
320
321 /// A specialized variant of expandCodeForPredicate, handling the case when
322 /// we are expanding code for a SCEVComparePredicate.
324 Instruction *Loc);
325
326 /// Generates code that evaluates if the \p AR expression will overflow.
328 bool Signed);
329
330 /// A specialized variant of expandCodeForPredicate, handling the case when
331 /// we are expanding code for a SCEVWrapPredicate.
333
334 /// A specialized variant of expandCodeForPredicate, handling the case when
335 /// we are expanding code for a SCEVUnionPredicate.
337
338 /// Set the current IV increment loop and position.
339 void setIVIncInsertPos(const Loop *L, Instruction *Pos) {
340 assert(!CanonicalMode &&
341 "IV increment positions are not supported in CanonicalMode");
342 IVIncInsertLoop = L;
343 IVIncInsertPos = Pos;
344 }
345
346 /// Enable post-inc expansion for addrecs referring to the given
347 /// loops. Post-inc expansion is only supported in non-canonical mode.
348 void setPostInc(const PostIncLoopSet &L) {
349 assert(!CanonicalMode &&
350 "Post-inc expansion is not supported in CanonicalMode");
351 PostIncLoops = L;
352 }
353
354 /// Disable all post-inc expansion.
356 PostIncLoops.clear();
357
358 // When we change the post-inc loop set, cached expansions may no
359 // longer be valid.
360 InsertedPostIncValues.clear();
361 }
362
363 /// Disable the behavior of expanding expressions in canonical form rather
364 /// than in a more literal form. Non-canonical mode is useful for late
365 /// optimization passes.
366 void disableCanonicalMode() { CanonicalMode = false; }
367
368 void enableLSRMode() { LSRMode = true; }
369
370 /// Set the current insertion point. This is useful if multiple calls to
371 /// expandCodeFor() are going to be made with the same insert point and the
372 /// insert point may be moved during one of the expansions (e.g. if the
373 /// insert point is not a block terminator).
375 assert(IP);
376 Builder.SetInsertPoint(IP);
377 }
378
380 Builder.SetInsertPoint(IP->getParent(), IP);
381 }
382
383 /// Clear the current insertion point. This is useful if the instruction
384 /// that had been serving as the insertion point may have been deleted.
386
387 /// Set location information used by debugging information.
389 Builder.SetCurrentDebugLocation(std::move(L));
390 }
391
392 /// Get location information used by debugging information.
394 return Builder.getCurrentDebugLocation();
395 }
396
397 /// Return true if the specified instruction was inserted by the code
398 /// rewriter. If so, the client should not modify the instruction. Note that
399 /// this also includes instructions re-used during expansion.
401 return InsertedValues.count(I) || InsertedPostIncValues.count(I);
402 }
403
404 void setChainedPhi(PHINode *PN) { ChainedPhis.insert(PN); }
405
406 /// Determine whether there is an existing expansion of S that can be reused.
407 /// This is used to check whether S can be expanded cheaply.
408 ///
409 /// L is a hint which tells in which loop to look for the suitable value.
410 ///
411 /// Note that this function does not perform an exhaustive search. I.e if it
412 /// didn't find any value it does not mean that there is no such value.
413 bool hasRelatedExistingExpansion(const SCEV *S, const Instruction *At,
414 Loop *L);
415
416 /// Returns a suitable insert point after \p I, that dominates \p
417 /// MustDominate. Skips instructions inserted by the expander.
419 Instruction *MustDominate) const;
420
421private:
422 LLVMContext &getContext() const { return SE.getContext(); }
423
424 /// Recursive helper function for isHighCostExpansion.
425 bool isHighCostExpansionHelper(const SCEVOperand &WorkItem, Loop *L,
426 const Instruction &At, InstructionCost &Cost,
427 unsigned Budget,
428 const TargetTransformInfo &TTI,
429 SmallPtrSetImpl<const SCEV *> &Processed,
430 SmallVectorImpl<SCEVOperand> &Worklist);
431
432 /// Insert the specified binary operator, doing a small amount of work to
433 /// avoid inserting an obviously redundant operation, and hoisting to an
434 /// outer loop when the opportunity is there and it is safe.
435 Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
436 SCEV::NoWrapFlags Flags, bool IsSafeToHoist);
437
438 /// We want to cast \p V. What would be the best place for such a cast?
439 BasicBlock::iterator GetOptimalInsertionPointForCastOf(Value *V) const;
440
441 /// Arrange for there to be a cast of V to Ty at IP, reusing an existing
442 /// cast if a suitable one exists, moving an existing cast if a suitable one
443 /// exists but isn't in the right place, or creating a new one.
444 Value *ReuseOrCreateCast(Value *V, Type *Ty, Instruction::CastOps Op,
446
447 /// Insert a cast of V to the specified type, which must be possible with a
448 /// noop cast, doing what we can to share the casts.
449 Value *InsertNoopCastOfTo(Value *V, Type *Ty);
450
451 /// Expand a SCEVAddExpr with a pointer type into a GEP instead of using
452 /// ptrtoint+arithmetic+inttoptr.
453 Value *expandAddToGEP(const SCEV *Op, Value *V);
454
455 /// Find a previous Value in ExprValueMap for expand.
456 /// DropPoisonGeneratingInsts is populated with instructions for which
457 /// poison-generating flags must be dropped if the value is reused.
458 Value *FindValueInExprValueMap(
459 const SCEV *S, const Instruction *InsertPt,
460 SmallVectorImpl<Instruction *> &DropPoisonGeneratingInsts);
461
462 Value *expand(const SCEV *S);
463 Value *expand(const SCEV *S, BasicBlock::iterator I) {
465 return expand(S);
466 }
467 Value *expand(const SCEV *S, Instruction *I) {
469 return expand(S);
470 }
471
472 /// Determine the most "relevant" loop for the given SCEV.
473 const Loop *getRelevantLoop(const SCEV *);
474
475 Value *expandMinMaxExpr(const SCEVNAryExpr *S, Intrinsic::ID IntrinID,
476 Twine Name, bool IsSequential = false);
477
478 Value *visitConstant(const SCEVConstant *S) { return S->getValue(); }
479
480 Value *visitVScale(const SCEVVScale *S);
481
482 Value *visitPtrToIntExpr(const SCEVPtrToIntExpr *S);
483
484 Value *visitTruncateExpr(const SCEVTruncateExpr *S);
485
486 Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);
487
488 Value *visitSignExtendExpr(const SCEVSignExtendExpr *S);
489
490 Value *visitAddExpr(const SCEVAddExpr *S);
491
492 Value *visitMulExpr(const SCEVMulExpr *S);
493
494 Value *visitUDivExpr(const SCEVUDivExpr *S);
495
496 Value *visitAddRecExpr(const SCEVAddRecExpr *S);
497
498 Value *visitSMaxExpr(const SCEVSMaxExpr *S);
499
500 Value *visitUMaxExpr(const SCEVUMaxExpr *S);
501
502 Value *visitSMinExpr(const SCEVSMinExpr *S);
503
504 Value *visitUMinExpr(const SCEVUMinExpr *S);
505
506 Value *visitSequentialUMinExpr(const SCEVSequentialUMinExpr *S);
507
508 Value *visitUnknown(const SCEVUnknown *S) { return S->getValue(); }
509
510 void rememberInstruction(Value *I);
511
512 void rememberFlags(Instruction *I);
513
514 bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
515
516 bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
517
518 Value *expandAddRecExprLiterally(const SCEVAddRecExpr *);
519 PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
520 const Loop *L, Type *&TruncTy,
521 bool &InvertStep);
522 Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L,
523 bool useSubtract);
524
525 void fixupInsertPoints(Instruction *I);
526
527 /// Create LCSSA PHIs for \p V, if it is required for uses at the Builder's
528 /// current insertion point.
529 Value *fixupLCSSAFormFor(Value *V);
530
531 /// Replace congruent phi increments with their most canonical representative.
532 /// May swap \p Phi and \p OrigPhi, if \p Phi is more canonical, due to its
533 /// increment.
534 void replaceCongruentIVInc(PHINode *&Phi, PHINode *&OrigPhi, Loop *L,
535 const DominatorTree *DT,
536 SmallVectorImpl<WeakTrackingVH> &DeadInsts);
537};
538
539/// Helper to remove instructions inserted during SCEV expansion, unless they
540/// are marked as used.
542 SCEVExpander &Expander;
543
544 /// Indicates whether the result of the expansion is used. If false, the
545 /// instructions added during expansion are removed.
546 bool ResultUsed;
547
548public:
550 : Expander(Expander), ResultUsed(false) {}
551
553
554 /// Indicate that the result of the expansion is used.
555 void markResultUsed() { ResultUsed = true; }
556
557 void cleanup();
558};
559} // namespace llvm
560
561#endif
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
basic Basic Alias true
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
RelocType Type
Definition: COFFYAML.cpp:391
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.
std::string Name
static Expected< BitVector > expand(StringRef S, StringRef Original)
Definition: GlobPattern.cpp:21
This file defines an InstructionCost class that is used when calculating the cost of an instruction,...
#define I(x, y, z)
Definition: MD5.cpp:58
#define P(N)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static const char * name
Definition: SMEABIPass.cpp:49
This file defines the SmallVector class.
This pass exposes codegen information to IR-level passes.
Value * RHS
Value * LHS
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
Value handle that asserts if the Value is deleted.
Definition: ValueHandle.h:264
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:164
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
A debug info location.
Definition: DebugLoc.h:33
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
InsertPoint - A saved insertion point.
Definition: IRBuilder.h:251
Common base class shared among various IRBuilders.
Definition: IRBuilder.h:94
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Definition: IRBuilder.h:220
DebugLoc getCurrentDebugLocation() const
Get location information used by debugging information.
Definition: IRBuilder.cpp:63
void ClearInsertionPoint()
Clear the insertion point: created instructions will not be inserted into a block.
Definition: IRBuilder.h:169
void restoreIP(InsertPoint IP)
Sets the current insert point to a previously-saved location.
Definition: IRBuilder.h:283
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:180
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
Definition: IRBuilder.h:76
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2649
InstSimplifyFolder - Use InstructionSimplify to fold operations to existing values.
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
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
Definition: SmallPtrSet.h:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
bool empty() const
Definition: SmallVector.h:94
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:950
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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.
Definition: ValueHandle.h:331
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
LLVM Value Representation.
Definition: Value.h:74
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
cl::opt< unsigned > SCEVCheapExpansionBudget
TargetTransformInfo TTI
DWARFExpression::Operation Op
InstructionCost Cost
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.