LLVM 17.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 {
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.
280 return expandCodeForImpl(SH, Ty, I);
281 }
282
283 /// Insert code to directly compute the specified SCEV expression into the
284 /// program. The code is inserted into the SCEVExpander's current
285 /// insertion point. If a type is specified, the result will be expanded to
286 /// have that type, with a cast if necessary.
287 Value *expandCodeFor(const SCEV *SH, Type *Ty = nullptr) {
288 return expandCodeForImpl(SH, Ty);
289 }
290
291 /// Generates a code sequence that evaluates this predicate. The inserted
292 /// instructions will be at position \p Loc. The result will be of type i1
293 /// and will have a value of 0 when the predicate is false and 1 otherwise.
295
296 /// A specialized variant of expandCodeForPredicate, handling the case when
297 /// we are expanding code for a SCEVComparePredicate.
299 Instruction *Loc);
300
301 /// Generates code that evaluates if the \p AR expression will overflow.
303 bool Signed);
304
305 /// A specialized variant of expandCodeForPredicate, handling the case when
306 /// we are expanding code for a SCEVWrapPredicate.
308
309 /// A specialized variant of expandCodeForPredicate, handling the case when
310 /// we are expanding code for a SCEVUnionPredicate.
312
313 /// Set the current IV increment loop and position.
314 void setIVIncInsertPos(const Loop *L, Instruction *Pos) {
315 assert(!CanonicalMode &&
316 "IV increment positions are not supported in CanonicalMode");
317 IVIncInsertLoop = L;
318 IVIncInsertPos = Pos;
319 }
320
321 /// Enable post-inc expansion for addrecs referring to the given
322 /// loops. Post-inc expansion is only supported in non-canonical mode.
323 void setPostInc(const PostIncLoopSet &L) {
324 assert(!CanonicalMode &&
325 "Post-inc expansion is not supported in CanonicalMode");
326 PostIncLoops = L;
327 }
328
329 /// Disable all post-inc expansion.
331 PostIncLoops.clear();
332
333 // When we change the post-inc loop set, cached expansions may no
334 // longer be valid.
335 InsertedPostIncValues.clear();
336 }
337
338 /// Disable the behavior of expanding expressions in canonical form rather
339 /// than in a more literal form. Non-canonical mode is useful for late
340 /// optimization passes.
341 void disableCanonicalMode() { CanonicalMode = false; }
342
343 void enableLSRMode() { LSRMode = true; }
344
345 /// Set the current insertion point. This is useful if multiple calls to
346 /// expandCodeFor() are going to be made with the same insert point and the
347 /// insert point may be moved during one of the expansions (e.g. if the
348 /// insert point is not a block terminator).
350 assert(IP);
351 Builder.SetInsertPoint(IP);
352 }
353
354 /// Clear the current insertion point. This is useful if the instruction
355 /// that had been serving as the insertion point may have been deleted.
357
358 /// Set location information used by debugging information.
360 Builder.SetCurrentDebugLocation(std::move(L));
361 }
362
363 /// Get location information used by debugging information.
365 return Builder.getCurrentDebugLocation();
366 }
367
368 /// Return true if the specified instruction was inserted by the code
369 /// rewriter. If so, the client should not modify the instruction. Note that
370 /// this also includes instructions re-used during expansion.
372 return InsertedValues.count(I) || InsertedPostIncValues.count(I);
373 }
374
375 void setChainedPhi(PHINode *PN) { ChainedPhis.insert(PN); }
376
377 /// Try to find the ValueOffsetPair for S. The function is mainly used to
378 /// check whether S can be expanded cheaply. If this returns a non-None
379 /// value, we know we can codegen the `ValueOffsetPair` into a suitable
380 /// expansion identical with S so that S can be expanded cheaply.
381 ///
382 /// L is a hint which tells in which loop to look for the suitable value.
383 /// On success return value which is equivalent to the expanded S at point
384 /// At. Return nullptr if value was not found.
385 ///
386 /// Note that this function does not perform an exhaustive search. I.e if it
387 /// didn't find any value it does not mean that there is no such value.
388 ///
390 Loop *L);
391
392 /// Returns a suitable insert point after \p I, that dominates \p
393 /// MustDominate. Skips instructions inserted by the expander.
395 Instruction *MustDominate) const;
396
397private:
398 LLVMContext &getContext() const { return SE.getContext(); }
399
400 /// Insert code to directly compute the specified SCEV expression into the
401 /// program. The code is inserted into the SCEVExpander's current
402 /// insertion point. If a type is specified, the result will be expanded to
403 /// have that type, with a cast if necessary. If \p Root is true, this
404 /// indicates that \p SH is the top-level expression to expand passed from
405 /// an external client call.
406 Value *expandCodeForImpl(const SCEV *SH, Type *Ty);
407
408 /// Insert code to directly compute the specified SCEV expression into the
409 /// program. The code is inserted into the specified block. If \p
410 /// Root is true, this indicates that \p SH is the top-level expression to
411 /// expand passed from an external client call.
412 Value *expandCodeForImpl(const SCEV *SH, Type *Ty, Instruction *I);
413
414 /// Recursive helper function for isHighCostExpansion.
415 bool isHighCostExpansionHelper(const SCEVOperand &WorkItem, Loop *L,
416 const Instruction &At, InstructionCost &Cost,
417 unsigned Budget,
418 const TargetTransformInfo &TTI,
419 SmallPtrSetImpl<const SCEV *> &Processed,
420 SmallVectorImpl<SCEVOperand> &Worklist);
421
422 /// Insert the specified binary operator, doing a small amount of work to
423 /// avoid inserting an obviously redundant operation, and hoisting to an
424 /// outer loop when the opportunity is there and it is safe.
425 Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
426 SCEV::NoWrapFlags Flags, bool IsSafeToHoist);
427
428 /// We want to cast \p V. What would be the best place for such a cast?
429 BasicBlock::iterator GetOptimalInsertionPointForCastOf(Value *V) const;
430
431 /// Arrange for there to be a cast of V to Ty at IP, reusing an existing
432 /// cast if a suitable one exists, moving an existing cast if a suitable one
433 /// exists but isn't in the right place, or creating a new one.
434 Value *ReuseOrCreateCast(Value *V, Type *Ty, Instruction::CastOps Op,
436
437 /// Insert a cast of V to the specified type, which must be possible with a
438 /// noop cast, doing what we can to share the casts.
439 Value *InsertNoopCastOfTo(Value *V, Type *Ty);
440
441 /// Expand a SCEVAddExpr with a pointer type into a GEP instead of using
442 /// ptrtoint+arithmetic+inttoptr.
443 Value *expandAddToGEP(const SCEV *const *op_begin, const SCEV *const *op_end,
444 PointerType *PTy, Type *Ty, Value *V);
445 Value *expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty, Value *V);
446
447 /// Find a previous Value in ExprValueMap for expand.
448 Value *FindValueInExprValueMap(const SCEV *S, const Instruction *InsertPt);
449
450 Value *expand(const SCEV *S);
451
452 /// Determine the most "relevant" loop for the given SCEV.
453 const Loop *getRelevantLoop(const SCEV *);
454
455 Value *expandMinMaxExpr(const SCEVNAryExpr *S, Intrinsic::ID IntrinID,
456 Twine Name, bool IsSequential = false);
457
458 Value *visitConstant(const SCEVConstant *S) { return S->getValue(); }
459
460 Value *visitPtrToIntExpr(const SCEVPtrToIntExpr *S);
461
462 Value *visitTruncateExpr(const SCEVTruncateExpr *S);
463
464 Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);
465
466 Value *visitSignExtendExpr(const SCEVSignExtendExpr *S);
467
468 Value *visitAddExpr(const SCEVAddExpr *S);
469
470 Value *visitMulExpr(const SCEVMulExpr *S);
471
472 Value *visitUDivExpr(const SCEVUDivExpr *S);
473
474 Value *visitAddRecExpr(const SCEVAddRecExpr *S);
475
476 Value *visitSMaxExpr(const SCEVSMaxExpr *S);
477
478 Value *visitUMaxExpr(const SCEVUMaxExpr *S);
479
480 Value *visitSMinExpr(const SCEVSMinExpr *S);
481
482 Value *visitUMinExpr(const SCEVUMinExpr *S);
483
484 Value *visitSequentialUMinExpr(const SCEVSequentialUMinExpr *S);
485
486 Value *visitUnknown(const SCEVUnknown *S) { return S->getValue(); }
487
488 void rememberInstruction(Value *I);
489
490 bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
491
492 bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
493
494 Value *expandAddRecExprLiterally(const SCEVAddRecExpr *);
495 PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
496 const Loop *L, Type *ExpandTy, Type *IntTy,
497 Type *&TruncTy, bool &InvertStep);
498 Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L, Type *ExpandTy,
499 Type *IntTy, bool useSubtract);
500
501 void fixupInsertPoints(Instruction *I);
502
503 /// Create LCSSA PHIs for \p V, if it is required for uses at the Builder's
504 /// current insertion point.
505 Value *fixupLCSSAFormFor(Value *V);
506};
507
508/// Helper to remove instructions inserted during SCEV expansion, unless they
509/// are marked as used.
511 SCEVExpander &Expander;
512
513 /// Indicates whether the result of the expansion is used. If false, the
514 /// instructions added during expansion are removed.
515 bool ResultUsed;
516
517public:
519 : Expander(Expander), ResultUsed(false) {}
520
522
523 /// Indicate that the result of the expansion is used.
524 void markResultUsed() { ResultUsed = true; }
525
526 void cleanup();
527};
528} // namespace llvm
529
530#endif
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
assume Assume Builder
basic Basic Alias true
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
RelocType Type
Definition: COFFYAML.cpp:390
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:26
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:87
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:114
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:166
InsertPoint - A saved insertion point.
Definition: IRBuilder.h:243
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:212
DebugLoc getCurrentDebugLocation() const
Get location information used by debugging information.
Definition: IRBuilder.cpp:72
void ClearInsertionPoint()
Clear the insertion point: created instructions will not be inserted into a block.
Definition: IRBuilder.h:169
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:2550
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:547
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.
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...
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.
Value * expandCodeFor(const SCEV *SH, Type *Ty=nullptr)
Insert code to directly compute the specified SCEV expression into the program.
Value * getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L)
Try to find the ValueOffsetPair for S.
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
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)
Insert code to directly compute the specified SCEV expression into the program.
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:389
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
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:577
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
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
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.