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
44/// This class uses information about analyze scalars to rewrite expressions
45/// in canonical form.
46///
47/// Clients should create an instance of this class when rewriting is needed,
48/// and destroy it when finished to allow the release of the associated
49/// memory.
50class SCEVExpander : public SCEVVisitor<SCEVExpander, Value *> {
52 const DataLayout &DL;
53
54 // New instructions receive a name to identify them with the current pass.
55 const char *IVName;
56
57 /// Indicates whether LCSSA phis should be created for inserted values.
58 bool PreserveLCSSA;
59
60 // InsertedExpressions caches Values for reuse, so must track RAUW.
62 InsertedExpressions;
63
64 // InsertedValues only flags inserted instructions so needs no RAUW.
65 DenseSet<AssertingVH<Value>> InsertedValues;
66 DenseSet<AssertingVH<Value>> InsertedPostIncValues;
67
68 /// Keep track of the existing IR values re-used during expansion.
69 /// FIXME: Ideally re-used instructions would not be added to
70 /// InsertedValues/InsertedPostIncValues.
71 SmallPtrSet<Value *, 16> ReusedValues;
72
73 // The induction variables generated.
74 SmallVector<WeakVH, 2> InsertedIVs;
75
76 /// A memoization of the "relevant" loop for a given SCEV.
78
79 /// Addrecs referring to any of the given loops are expanded in post-inc
80 /// mode. For example, expanding {1,+,1}<L> in post-inc mode returns the add
81 /// instruction that adds one to the phi for {0,+,1}<L>, as opposed to a new
82 /// phi starting at 1. This is only supported in non-canonical mode.
83 PostIncLoopSet PostIncLoops;
84
85 /// When this is non-null, addrecs expanded in the loop it indicates should
86 /// be inserted with increments at IVIncInsertPos.
87 const Loop *IVIncInsertLoop;
88
89 /// When expanding addrecs in the IVIncInsertLoop loop, insert the IV
90 /// increment at this position.
91 Instruction *IVIncInsertPos;
92
93 /// Phis that complete an IV chain. Reuse
95
96 /// When true, SCEVExpander tries to expand expressions in "canonical" form.
97 /// When false, expressions are expanded in a more literal form.
98 ///
99 /// In "canonical" form addrecs are expanded as arithmetic based on a
100 /// canonical induction variable. Note that CanonicalMode doesn't guarantee
101 /// that all expressions are expanded in "canonical" form. For some
102 /// expressions literal mode can be preferred.
103 bool CanonicalMode;
104
105 /// When invoked from LSR, the expander is in "strength reduction" mode. The
106 /// only difference is that phi's are only reused if they are already in
107 /// "expanded" form.
108 bool LSRMode;
109
111 BuilderType Builder;
112
113 // RAII object that stores the current insertion point and restores it when
114 // the object is destroyed. This includes the debug location. Duplicated
115 // from InsertPointGuard to add SetInsertPoint() which is used to updated
116 // InsertPointGuards stack when insert points are moved during SCEV
117 // expansion.
118 class SCEVInsertPointGuard {
119 IRBuilderBase &Builder;
122 DebugLoc DbgLoc;
123 SCEVExpander *SE;
124
125 SCEVInsertPointGuard(const SCEVInsertPointGuard &) = delete;
126 SCEVInsertPointGuard &operator=(const SCEVInsertPointGuard &) = delete;
127
128 public:
129 SCEVInsertPointGuard(IRBuilderBase &B, SCEVExpander *SE)
130 : Builder(B), Block(B.GetInsertBlock()), Point(B.GetInsertPoint()),
131 DbgLoc(B.getCurrentDebugLocation()), SE(SE) {
132 SE->InsertPointGuards.push_back(this);
133 }
134
135 ~SCEVInsertPointGuard() {
136 // These guards should always created/destroyed in FIFO order since they
137 // are used to guard lexically scoped blocks of code in
138 // ScalarEvolutionExpander.
139 assert(SE->InsertPointGuards.back() == this);
140 SE->InsertPointGuards.pop_back();
141 Builder.restoreIP(IRBuilderBase::InsertPoint(Block, Point));
142 Builder.SetCurrentDebugLocation(DbgLoc);
143 }
144
145 BasicBlock::iterator GetInsertPoint() const { return Point; }
146 void SetInsertPoint(BasicBlock::iterator I) { Point = I; }
147 };
148
149 /// Stack of pointers to saved insert points, used to keep insert points
150 /// consistent when instructions are moved.
152
153#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
154 const char *DebugType;
155#endif
156
157 friend struct SCEVVisitor<SCEVExpander, Value *>;
158
159public:
160 /// Construct a SCEVExpander in "canonical" mode.
162 const char *name, bool PreserveLCSSA = true)
163 : SE(se), DL(DL), IVName(name), PreserveLCSSA(PreserveLCSSA),
164 IVIncInsertLoop(nullptr), IVIncInsertPos(nullptr), CanonicalMode(true),
165 LSRMode(false),
166 Builder(se.getContext(), InstSimplifyFolder(DL),
168 [this](Instruction *I) { rememberInstruction(I); })) {
169#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
170 DebugType = "";
171#endif
172 }
173
175 // Make sure the insert point guard stack is consistent.
176 assert(InsertPointGuards.empty());
177 }
178
179#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
180 void setDebugType(const char *s) { DebugType = s; }
181#endif
182
183 /// Erase the contents of the InsertedExpressions map so that users trying
184 /// to expand the same expression into multiple BasicBlocks or different
185 /// places within the same BasicBlock can do so.
186 void clear() {
187 InsertedExpressions.clear();
188 InsertedValues.clear();
189 InsertedPostIncValues.clear();
190 ReusedValues.clear();
191 ChainedPhis.clear();
192 InsertedIVs.clear();
193 }
194
195 ScalarEvolution *getSE() { return &SE; }
196 const SmallVectorImpl<WeakVH> &getInsertedIVs() const { return InsertedIVs; }
197
198 /// Return a vector containing all instructions inserted during expansion.
201 for (const auto &VH : InsertedValues) {
202 Value *V = VH;
203 if (ReusedValues.contains(V))
204 continue;
205 if (auto *Inst = dyn_cast<Instruction>(V))
206 Result.push_back(Inst);
207 }
208 for (const auto &VH : InsertedPostIncValues) {
209 Value *V = VH;
210 if (ReusedValues.contains(V))
211 continue;
212 if (auto *Inst = dyn_cast<Instruction>(V))
213 Result.push_back(Inst);
214 }
215
216 return Result;
217 }
218
219 /// Return true for expressions that can't be evaluated at runtime
220 /// within given \b Budget.
221 ///
222 /// \p At is a parameter which specifies point in code where user is going to
223 /// expand these expressions. Sometimes this knowledge can lead to
224 /// a less pessimistic cost estimation.
226 unsigned Budget, const TargetTransformInfo *TTI,
227 const Instruction *At) {
228 assert(TTI && "This function requires TTI to be provided.");
229 assert(At && "This function requires At instruction to be provided.");
230 if (!TTI) // In assert-less builds, avoid crashing
231 return true; // by always claiming to be high-cost.
235 unsigned ScaledBudget = Budget * TargetTransformInfo::TCC_Basic;
236 for (auto *Expr : Exprs)
237 Worklist.emplace_back(-1, -1, Expr);
238 while (!Worklist.empty()) {
239 const SCEVOperand WorkItem = Worklist.pop_back_val();
240 if (isHighCostExpansionHelper(WorkItem, L, *At, Cost, ScaledBudget, *TTI,
241 Processed, Worklist))
242 return true;
243 }
244 assert(Cost <= ScaledBudget && "Should have returned from inner loop.");
245 return false;
246 }
247
248 /// Return the induction variable increment's IV operand.
250 bool allowScale);
251
252 /// Utility for hoisting \p IncV (with all subexpressions requried for its
253 /// computation) before \p InsertPos. If \p RecomputePoisonFlags is set, drops
254 /// all poison-generating flags from instructions being hoisted and tries to
255 /// re-infer them in the new location. It should be used when we are going to
256 /// introduce a new use in the new position that didn't exist before, and may
257 /// trigger new UB in case of poison.
258 bool hoistIVInc(Instruction *IncV, Instruction *InsertPos,
259 bool RecomputePoisonFlags = false);
260
261 /// replace congruent phis with their most canonical representative. Return
262 /// the number of phis eliminated.
263 unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT,
265 const TargetTransformInfo *TTI = nullptr);
266
267 /// Return true if the given expression is safe to expand in the sense that
268 /// all materialized values are safe to speculate anywhere their operands are
269 /// defined, and the expander is capable of expanding the expression.
270 bool isSafeToExpand(const SCEV *S) const;
271
272 /// Return true if the given expression is safe to expand in the sense that
273 /// all materialized values are defined and safe to speculate at the specified
274 /// location and their operands are defined at this location.
275 bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint) const;
276
277 /// Insert code to directly compute the specified SCEV expression into the
278 /// program. The code is inserted into the specified block.
281 return expandCodeFor(SH, Ty, I->getIterator());
282 }
283
284 /// Insert code to directly compute the specified SCEV expression into the
285 /// program. The code is inserted into the SCEVExpander's current
286 /// insertion point. If a type is specified, the result will be expanded to
287 /// have that type, with a cast if necessary.
288 Value *expandCodeFor(const SCEV *SH, Type *Ty = nullptr);
289
290 /// Generates a code sequence that evaluates this predicate. The inserted
291 /// instructions will be at position \p Loc. The result will be of type i1
292 /// and will have a value of 0 when the predicate is false and 1 otherwise.
294
295 /// A specialized variant of expandCodeForPredicate, handling the case when
296 /// we are expanding code for a SCEVComparePredicate.
298 Instruction *Loc);
299
300 /// Generates code that evaluates if the \p AR expression will overflow.
302 bool Signed);
303
304 /// A specialized variant of expandCodeForPredicate, handling the case when
305 /// we are expanding code for a SCEVWrapPredicate.
307
308 /// A specialized variant of expandCodeForPredicate, handling the case when
309 /// we are expanding code for a SCEVUnionPredicate.
311
312 /// Set the current IV increment loop and position.
313 void setIVIncInsertPos(const Loop *L, Instruction *Pos) {
314 assert(!CanonicalMode &&
315 "IV increment positions are not supported in CanonicalMode");
316 IVIncInsertLoop = L;
317 IVIncInsertPos = Pos;
318 }
319
320 /// Enable post-inc expansion for addrecs referring to the given
321 /// loops. Post-inc expansion is only supported in non-canonical mode.
322 void setPostInc(const PostIncLoopSet &L) {
323 assert(!CanonicalMode &&
324 "Post-inc expansion is not supported in CanonicalMode");
325 PostIncLoops = L;
326 }
327
328 /// Disable all post-inc expansion.
330 PostIncLoops.clear();
331
332 // When we change the post-inc loop set, cached expansions may no
333 // longer be valid.
334 InsertedPostIncValues.clear();
335 }
336
337 /// Disable the behavior of expanding expressions in canonical form rather
338 /// than in a more literal form. Non-canonical mode is useful for late
339 /// optimization passes.
340 void disableCanonicalMode() { CanonicalMode = false; }
341
342 void enableLSRMode() { LSRMode = true; }
343
344 /// Set the current insertion point. This is useful if multiple calls to
345 /// expandCodeFor() are going to be made with the same insert point and the
346 /// insert point may be moved during one of the expansions (e.g. if the
347 /// insert point is not a block terminator).
349 assert(IP);
350 Builder.SetInsertPoint(IP);
351 }
352
354 Builder.SetInsertPoint(IP->getParent(), IP);
355 }
356
357 /// Clear the current insertion point. This is useful if the instruction
358 /// that had been serving as the insertion point may have been deleted.
360
361 /// Set location information used by debugging information.
363 Builder.SetCurrentDebugLocation(std::move(L));
364 }
365
366 /// Get location information used by debugging information.
368 return Builder.getCurrentDebugLocation();
369 }
370
371 /// Return true if the specified instruction was inserted by the code
372 /// rewriter. If so, the client should not modify the instruction. Note that
373 /// this also includes instructions re-used during expansion.
375 return InsertedValues.count(I) || InsertedPostIncValues.count(I);
376 }
377
378 void setChainedPhi(PHINode *PN) { ChainedPhis.insert(PN); }
379
380 /// Determine whether there is an existing expansion of S that can be reused.
381 /// This is used to check whether S can be expanded cheaply.
382 ///
383 /// L is a hint which tells in which loop to look for the suitable value.
384 ///
385 /// Note that this function does not perform an exhaustive search. I.e if it
386 /// didn't find any value it does not mean that there is no such value.
387 bool hasRelatedExistingExpansion(const SCEV *S, const Instruction *At,
388 Loop *L);
389
390 /// Returns a suitable insert point after \p I, that dominates \p
391 /// MustDominate. Skips instructions inserted by the expander.
393 Instruction *MustDominate) const;
394
395private:
396 LLVMContext &getContext() const { return SE.getContext(); }
397
398 /// Recursive helper function for isHighCostExpansion.
399 bool isHighCostExpansionHelper(const SCEVOperand &WorkItem, Loop *L,
400 const Instruction &At, InstructionCost &Cost,
401 unsigned Budget,
402 const TargetTransformInfo &TTI,
403 SmallPtrSetImpl<const SCEV *> &Processed,
404 SmallVectorImpl<SCEVOperand> &Worklist);
405
406 /// Insert the specified binary operator, doing a small amount of work to
407 /// avoid inserting an obviously redundant operation, and hoisting to an
408 /// outer loop when the opportunity is there and it is safe.
409 Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
410 SCEV::NoWrapFlags Flags, bool IsSafeToHoist);
411
412 /// We want to cast \p V. What would be the best place for such a cast?
413 BasicBlock::iterator GetOptimalInsertionPointForCastOf(Value *V) const;
414
415 /// Arrange for there to be a cast of V to Ty at IP, reusing an existing
416 /// cast if a suitable one exists, moving an existing cast if a suitable one
417 /// exists but isn't in the right place, or creating a new one.
418 Value *ReuseOrCreateCast(Value *V, Type *Ty, Instruction::CastOps Op,
420
421 /// Insert a cast of V to the specified type, which must be possible with a
422 /// noop cast, doing what we can to share the casts.
423 Value *InsertNoopCastOfTo(Value *V, Type *Ty);
424
425 /// Expand a SCEVAddExpr with a pointer type into a GEP instead of using
426 /// ptrtoint+arithmetic+inttoptr.
427 Value *expandAddToGEP(const SCEV *Op, Value *V);
428
429 /// Find a previous Value in ExprValueMap for expand.
430 /// DropPoisonGeneratingInsts is populated with instructions for which
431 /// poison-generating flags must be dropped if the value is reused.
432 Value *FindValueInExprValueMap(
433 const SCEV *S, const Instruction *InsertPt,
434 SmallVectorImpl<Instruction *> &DropPoisonGeneratingInsts);
435
436 Value *expand(const SCEV *S);
437 Value *expand(const SCEV *S, BasicBlock::iterator I) {
439 return expand(S);
440 }
441 Value *expand(const SCEV *S, Instruction *I) {
443 return expand(S);
444 }
445
446 /// Determine the most "relevant" loop for the given SCEV.
447 const Loop *getRelevantLoop(const SCEV *);
448
449 Value *expandMinMaxExpr(const SCEVNAryExpr *S, Intrinsic::ID IntrinID,
450 Twine Name, bool IsSequential = false);
451
452 Value *visitConstant(const SCEVConstant *S) { return S->getValue(); }
453
454 Value *visitVScale(const SCEVVScale *S);
455
456 Value *visitPtrToIntExpr(const SCEVPtrToIntExpr *S);
457
458 Value *visitTruncateExpr(const SCEVTruncateExpr *S);
459
460 Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);
461
462 Value *visitSignExtendExpr(const SCEVSignExtendExpr *S);
463
464 Value *visitAddExpr(const SCEVAddExpr *S);
465
466 Value *visitMulExpr(const SCEVMulExpr *S);
467
468 Value *visitUDivExpr(const SCEVUDivExpr *S);
469
470 Value *visitAddRecExpr(const SCEVAddRecExpr *S);
471
472 Value *visitSMaxExpr(const SCEVSMaxExpr *S);
473
474 Value *visitUMaxExpr(const SCEVUMaxExpr *S);
475
476 Value *visitSMinExpr(const SCEVSMinExpr *S);
477
478 Value *visitUMinExpr(const SCEVUMinExpr *S);
479
480 Value *visitSequentialUMinExpr(const SCEVSequentialUMinExpr *S);
481
482 Value *visitUnknown(const SCEVUnknown *S) { return S->getValue(); }
483
484 void rememberInstruction(Value *I);
485
486 bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
487
488 bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
489
490 Value *expandAddRecExprLiterally(const SCEVAddRecExpr *);
491 PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
492 const Loop *L, Type *&TruncTy,
493 bool &InvertStep);
494 Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L,
495 bool useSubtract);
496
497 void fixupInsertPoints(Instruction *I);
498
499 /// Create LCSSA PHIs for \p V, if it is required for uses at the Builder's
500 /// current insertion point.
501 Value *fixupLCSSAFormFor(Value *V);
502
503 /// Replace congruent phi increments with their most canonical representative.
504 /// May swap \p Phi and \p OrigPhi, if \p Phi is more canonical, due to its
505 /// increment.
506 void replaceCongruentIVInc(PHINode *&Phi, PHINode *&OrigPhi, Loop *L,
507 const DominatorTree *DT,
508 SmallVectorImpl<WeakTrackingVH> &DeadInsts);
509};
510
511/// Helper to remove instructions inserted during SCEV expansion, unless they
512/// are marked as used.
514 SCEVExpander &Expander;
515
516 /// Indicates whether the result of the expansion is used. If false, the
517 /// instructions added during expansion are removed.
518 bool ResultUsed;
519
520public:
522 : Expander(Expander), ResultUsed(false) {}
523
525
526 /// Indicate that the result of the expansion is used.
527 void markResultUsed() { ResultUsed = true; }
528
529 void cleanup();
530};
531} // namespace llvm
532
533#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:173
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.
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.
LLVMContext & getContext() const
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
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
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.