LLVM  9.0.0svn
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_ANALYSIS_SCALAREVOLUTIONEXPANDER_H
14 #define LLVM_ANALYSIS_SCALAREVOLUTIONEXPANDER_H
15 
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/DenseSet.h"
18 #include "llvm/ADT/Optional.h"
22 #include "llvm/IR/IRBuilder.h"
23 #include "llvm/IR/ValueHandle.h"
24 
25 namespace llvm {
26  class TargetTransformInfo;
27 
28  /// Return true if the given expression is safe to expand in the sense that
29  /// all materialized values are safe to speculate anywhere their operands are
30  /// defined.
31  bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE);
32 
33  /// Return true if the given expression is safe to expand in the sense that
34  /// all materialized values are defined and safe to speculate at the specified
35  /// location and their operands are defined at this location.
36  bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint,
37  ScalarEvolution &SE);
38 
39  /// This class uses information about analyze scalars to rewrite expressions
40  /// in canonical form.
41  ///
42  /// Clients should create an instance of this class when rewriting is needed,
43  /// and destroy it when finished to allow the release of the associated
44  /// memory.
45  class SCEVExpander : public SCEVVisitor<SCEVExpander, Value*> {
46  ScalarEvolution &SE;
47  const DataLayout &DL;
48 
49  // New instructions receive a name to identify them with the current pass.
50  const char* IVName;
51 
52  // InsertedExpressions caches Values for reuse, so must track RAUW.
54  InsertedExpressions;
55 
56  // InsertedValues only flags inserted instructions so needs no RAUW.
57  DenseSet<AssertingVH<Value>> InsertedValues;
58  DenseSet<AssertingVH<Value>> InsertedPostIncValues;
59 
60  /// A memoization of the "relevant" loop for a given SCEV.
62 
63  /// Addrecs referring to any of the given loops are expanded in post-inc
64  /// mode. For example, expanding {1,+,1}<L> in post-inc mode returns the add
65  /// instruction that adds one to the phi for {0,+,1}<L>, as opposed to a new
66  /// phi starting at 1. This is only supported in non-canonical mode.
67  PostIncLoopSet PostIncLoops;
68 
69  /// When this is non-null, addrecs expanded in the loop it indicates should
70  /// be inserted with increments at IVIncInsertPos.
71  const Loop *IVIncInsertLoop;
72 
73  /// When expanding addrecs in the IVIncInsertLoop loop, insert the IV
74  /// increment at this position.
75  Instruction *IVIncInsertPos;
76 
77  /// Phis that complete an IV chain. Reuse
78  DenseSet<AssertingVH<PHINode>> ChainedPhis;
79 
80  /// When true, expressions are expanded in "canonical" form. In particular,
81  /// addrecs are expanded as arithmetic based on a canonical induction
82  /// variable. When false, expression are expanded in a more literal form.
83  bool CanonicalMode;
84 
85  /// When invoked from LSR, the expander is in "strength reduction" mode. The
86  /// only difference is that phi's are only reused if they are already in
87  /// "expanded" form.
88  bool LSRMode;
89 
91  BuilderType Builder;
92 
93  // RAII object that stores the current insertion point and restores it when
94  // the object is destroyed. This includes the debug location. Duplicated
95  // from InsertPointGuard to add SetInsertPoint() which is used to updated
96  // InsertPointGuards stack when insert points are moved during SCEV
97  // expansion.
98  class SCEVInsertPointGuard {
99  IRBuilderBase &Builder;
101  BasicBlock::iterator Point;
102  DebugLoc DbgLoc;
103  SCEVExpander *SE;
104 
105  SCEVInsertPointGuard(const SCEVInsertPointGuard &) = delete;
106  SCEVInsertPointGuard &operator=(const SCEVInsertPointGuard &) = delete;
107 
108  public:
109  SCEVInsertPointGuard(IRBuilderBase &B, SCEVExpander *SE)
110  : Builder(B), Block(B.GetInsertBlock()), Point(B.GetInsertPoint()),
111  DbgLoc(B.getCurrentDebugLocation()), SE(SE) {
112  SE->InsertPointGuards.push_back(this);
113  }
114 
115  ~SCEVInsertPointGuard() {
116  // These guards should always created/destroyed in FIFO order since they
117  // are used to guard lexically scoped blocks of code in
118  // ScalarEvolutionExpander.
119  assert(SE->InsertPointGuards.back() == this);
120  SE->InsertPointGuards.pop_back();
121  Builder.restoreIP(IRBuilderBase::InsertPoint(Block, Point));
122  Builder.SetCurrentDebugLocation(DbgLoc);
123  }
124 
125  BasicBlock::iterator GetInsertPoint() const { return Point; }
126  void SetInsertPoint(BasicBlock::iterator I) { Point = I; }
127  };
128 
129  /// Stack of pointers to saved insert points, used to keep insert points
130  /// consistent when instructions are moved.
131  SmallVector<SCEVInsertPointGuard *, 8> InsertPointGuards;
132 
133 #ifndef NDEBUG
134  const char *DebugType;
135 #endif
136 
137  friend struct SCEVVisitor<SCEVExpander, Value*>;
138 
139  public:
140  /// Construct a SCEVExpander in "canonical" mode.
141  explicit SCEVExpander(ScalarEvolution &se, const DataLayout &DL,
142  const char *name)
143  : SE(se), DL(DL), IVName(name), IVIncInsertLoop(nullptr),
144  IVIncInsertPos(nullptr), CanonicalMode(true), LSRMode(false),
145  Builder(se.getContext(), TargetFolder(DL)) {
146 #ifndef NDEBUG
147  DebugType = "";
148 #endif
149  }
150 
152  // Make sure the insert point guard stack is consistent.
153  assert(InsertPointGuards.empty());
154  }
155 
156 #ifndef NDEBUG
157  void setDebugType(const char* s) { DebugType = s; }
158 #endif
159 
160  /// Erase the contents of the InsertedExpressions map so that users trying
161  /// to expand the same expression into multiple BasicBlocks or different
162  /// places within the same BasicBlock can do so.
163  void clear() {
164  InsertedExpressions.clear();
165  InsertedValues.clear();
166  InsertedPostIncValues.clear();
167  ChainedPhis.clear();
168  }
169 
170  /// Return true for expressions that may incur non-trivial cost to evaluate
171  /// at runtime.
172  ///
173  /// At is an optional parameter which specifies point in code where user is
174  /// going to expand this expression. Sometimes this knowledge can lead to a
175  /// more accurate cost estimation.
176  bool isHighCostExpansion(const SCEV *Expr, Loop *L,
177  const Instruction *At = nullptr) {
179  return isHighCostExpansionHelper(Expr, L, At, Processed);
180  }
181 
182  /// This method returns the canonical induction variable of the specified
183  /// type for the specified loop (inserting one if there is none). A
184  /// canonical induction variable starts at zero and steps by one on each
185  /// iteration.
187 
188  /// Return the induction variable increment's IV operand.
190  bool allowScale);
191 
192  /// Utility for hoisting an IV increment.
193  bool hoistIVInc(Instruction *IncV, Instruction *InsertPos);
194 
195  /// replace congruent phis with their most canonical representative. Return
196  /// the number of phis eliminated.
197  unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT,
199  const TargetTransformInfo *TTI = nullptr);
200 
201  /// Insert code to directly compute the specified SCEV expression into the
202  /// program. The inserted code is inserted into the specified block.
203  Value *expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I);
204 
205  /// Insert code to directly compute the specified SCEV expression into the
206  /// program. The inserted code is inserted into the SCEVExpander's current
207  /// insertion point. If a type is specified, the result will be expanded to
208  /// have that type, with a cast if necessary.
209  Value *expandCodeFor(const SCEV *SH, Type *Ty = nullptr);
210 
211 
212  /// Generates a code sequence that evaluates this predicate. The inserted
213  /// instructions will be at position \p Loc. The result will be of type i1
214  /// and will have a value of 0 when the predicate is false and 1 otherwise.
216 
217  /// A specialized variant of expandCodeForPredicate, handling the case when
218  /// we are expanding code for a SCEVEqualPredicate.
220  Instruction *Loc);
221 
222  /// Generates code that evaluates if the \p AR expression will overflow.
224  bool Signed);
225 
226  /// A specialized variant of expandCodeForPredicate, handling the case when
227  /// we are expanding code for a SCEVWrapPredicate.
229 
230  /// A specialized variant of expandCodeForPredicate, handling the case when
231  /// we are expanding code for a SCEVUnionPredicate.
233  Instruction *Loc);
234 
235  /// Set the current IV increment loop and position.
236  void setIVIncInsertPos(const Loop *L, Instruction *Pos) {
237  assert(!CanonicalMode &&
238  "IV increment positions are not supported in CanonicalMode");
239  IVIncInsertLoop = L;
240  IVIncInsertPos = Pos;
241  }
242 
243  /// Enable post-inc expansion for addrecs referring to the given
244  /// loops. Post-inc expansion is only supported in non-canonical mode.
245  void setPostInc(const PostIncLoopSet &L) {
246  assert(!CanonicalMode &&
247  "Post-inc expansion is not supported in CanonicalMode");
248  PostIncLoops = L;
249  }
250 
251  /// Disable all post-inc expansion.
252  void clearPostInc() {
253  PostIncLoops.clear();
254 
255  // When we change the post-inc loop set, cached expansions may no
256  // longer be valid.
257  InsertedPostIncValues.clear();
258  }
259 
260  /// Disable the behavior of expanding expressions in canonical form rather
261  /// than in a more literal form. Non-canonical mode is useful for late
262  /// optimization passes.
263  void disableCanonicalMode() { CanonicalMode = false; }
264 
265  void enableLSRMode() { LSRMode = true; }
266 
267  /// Set the current insertion point. This is useful if multiple calls to
268  /// expandCodeFor() are going to be made with the same insert point and the
269  /// insert point may be moved during one of the expansions (e.g. if the
270  /// insert point is not a block terminator).
272  assert(IP);
273  Builder.SetInsertPoint(IP);
274  }
275 
276  /// Clear the current insertion point. This is useful if the instruction
277  /// that had been serving as the insertion point may have been deleted.
279  Builder.ClearInsertionPoint();
280  }
281 
282  /// Return true if the specified instruction was inserted by the code
283  /// rewriter. If so, the client should not modify the instruction.
285  return InsertedValues.count(I) || InsertedPostIncValues.count(I);
286  }
287 
288  void setChainedPhi(PHINode *PN) { ChainedPhis.insert(PN); }
289 
290  /// Try to find existing LLVM IR value for S available at the point At.
291  Value *getExactExistingExpansion(const SCEV *S, const Instruction *At,
292  Loop *L);
293 
294  /// Try to find the ValueOffsetPair for S. The function is mainly used to
295  /// check whether S can be expanded cheaply. If this returns a non-None
296  /// value, we know we can codegen the `ValueOffsetPair` into a suitable
297  /// expansion identical with S so that S can be expanded cheaply.
298  ///
299  /// L is a hint which tells in which loop to look for the suitable value.
300  /// On success return value which is equivalent to the expanded S at point
301  /// At. Return nullptr if value was not found.
302  ///
303  /// Note that this function does not perform an exhaustive search. I.e if it
304  /// didn't find any value it does not mean that there is no such value.
305  ///
307  getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L);
308 
309  private:
310  LLVMContext &getContext() const { return SE.getContext(); }
311 
312  /// Recursive helper function for isHighCostExpansion.
313  bool isHighCostExpansionHelper(const SCEV *S, Loop *L,
314  const Instruction *At,
315  SmallPtrSetImpl<const SCEV *> &Processed);
316 
317  /// Insert the specified binary operator, doing a small amount of work to
318  /// avoid inserting an obviously redundant operation.
319  Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS);
320 
321  /// Arrange for there to be a cast of V to Ty at IP, reusing an existing
322  /// cast if a suitable one exists, moving an existing cast if a suitable one
323  /// exists but isn't in the right place, or creating a new one.
324  Value *ReuseOrCreateCast(Value *V, Type *Ty,
327 
328  /// Insert a cast of V to the specified type, which must be possible with a
329  /// noop cast, doing what we can to share the casts.
330  Value *InsertNoopCastOfTo(Value *V, Type *Ty);
331 
332  /// Expand a SCEVAddExpr with a pointer type into a GEP instead of using
333  /// ptrtoint+arithmetic+inttoptr.
334  Value *expandAddToGEP(const SCEV *const *op_begin,
335  const SCEV *const *op_end,
336  PointerType *PTy, Type *Ty, Value *V);
337  Value *expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty, Value *V);
338 
339  /// Find a previous Value in ExprValueMap for expand.
340  ScalarEvolution::ValueOffsetPair
341  FindValueInExprValueMap(const SCEV *S, const Instruction *InsertPt);
342 
343  Value *expand(const SCEV *S);
344 
345  /// Determine the most "relevant" loop for the given SCEV.
346  const Loop *getRelevantLoop(const SCEV *);
347 
348  Value *visitConstant(const SCEVConstant *S) {
349  return S->getValue();
350  }
351 
352  Value *visitTruncateExpr(const SCEVTruncateExpr *S);
353 
354  Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);
355 
356  Value *visitSignExtendExpr(const SCEVSignExtendExpr *S);
357 
358  Value *visitAddExpr(const SCEVAddExpr *S);
359 
360  Value *visitMulExpr(const SCEVMulExpr *S);
361 
362  Value *visitUDivExpr(const SCEVUDivExpr *S);
363 
364  Value *visitAddRecExpr(const SCEVAddRecExpr *S);
365 
366  Value *visitSMaxExpr(const SCEVSMaxExpr *S);
367 
368  Value *visitUMaxExpr(const SCEVUMaxExpr *S);
369 
370  Value *visitUnknown(const SCEVUnknown *S) {
371  return S->getValue();
372  }
373 
374  void rememberInstruction(Value *I);
375 
376  bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
377 
378  bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
379 
380  Value *expandAddRecExprLiterally(const SCEVAddRecExpr *);
381  PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
382  const Loop *L,
383  Type *ExpandTy,
384  Type *IntTy,
385  Type *&TruncTy,
386  bool &InvertStep);
387  Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L,
388  Type *ExpandTy, Type *IntTy, bool useSubtract);
389 
390  void hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist,
391  Instruction *Pos, PHINode *LoopPhi);
392 
393  void fixupInsertPoints(Instruction *I);
394  };
395 }
396 
397 #endif
Common base class shared among various IRBuilders.
Definition: IRBuilder.h:88
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
bool hoistIVInc(Instruction *IncV, Instruction *InsertPos)
Utility for hoisting an IV increment.
Value * getExactExistingExpansion(const SCEV *S, const Instruction *At, Loop *L)
Try to find existing LLVM IR value for S available at the point At.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint, ScalarEvolution &SE)
Return true if the given expression is safe to expand in the sense that all materialized values are d...
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
void push_back(const T &Elt)
Definition: SmallVector.h:211
The main scalar evolution driver.
bool isHighCostExpansion(const SCEV *Expr, Loop *L, const Instruction *At=nullptr)
Return true for expressions that may incur non-trivial cost to evaluate at runtime.
Optional< ScalarEvolution::ValueOffsetPair > getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L)
Try to find the ValueOffsetPair for S.
This class represents a truncation of an integer value to a smaller integer value.
void setDebugType(const char *s)
Value * expandWrapPredicate(const SCEVWrapPredicate *P, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
A debug info location.
Definition: DebugLoc.h:33
block Block Frequency true
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
Value * expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc)
Generates a code sequence that evaluates this predicate.
void clearPostInc()
Disable all post-inc expansion.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
LLVMContext & getContext() const
const DebugLoc & getCurrentDebugLocation() const
Get location information used by debugging information.
Definition: IRBuilder.h:153
This node represents multiplication of some number of SCEVs.
Value * generateOverflowCheck(const SCEVAddRecExpr *AR, Instruction *Loc, bool Signed)
Generates code that evaluates if the AR expression will overflow.
ConstantInt * getValue() const
This node represents a polynomial recurrence on the trip count of the specified loop.
BasicBlock * GetInsertBlock() const
Definition: IRBuilder.h:120
void ClearInsertionPoint()
Clear the insertion point: created instructions will not be inserted into a block.
Definition: IRBuilder.h:115
TargetFolder - Create constants with target dependent folding.
Definition: TargetFolder.h:31
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Definition: IRBuilder.h:150
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block...
Definition: IRBuilder.h:126
Class to represent pointers.
Definition: DerivedTypes.h:498
void clearInsertPoint()
Clear the current insertion point.
void clear()
Erase the contents of the InsertedExpressions map so that users trying to expand the same expression ...
#define P(N)
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
void restoreIP(InsertPoint IP)
Sets the current insert point to a previously-saved location.
Definition: IRBuilder.h:199
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This class defines a simple visitor class that may be used for various SCEV analysis purposes...
This class represents a binary unsigned division operation.
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:64
void setInsertPoint(Instruction *IP)
Set the current insertion point.
Value handle that tracks a Value across RAUW.
Definition: ValueHandle.h:327
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
static Expected< BitVector > expand(StringRef S, StringRef Original)
Definition: GlobPattern.cpp:27
SCEVExpander(ScalarEvolution &se, const DataLayout &DL, const char *name)
Construct a SCEVExpander in "canonical" mode.
This class represents an assumption made using SCEV expressions which can be checked at run-time...
void setChainedPhi(PHINode *PN)
InsertPoint - A saved insertion point.
Definition: IRBuilder.h:167
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
PHINode * getOrInsertCanonicalInductionVariable(const Loop *L, Type *Ty)
This method returns the canonical induction variable of the specified type for the specified loop (in...
void setIVIncInsertPos(const Loop *L, Instruction *Pos)
Set the current IV increment loop and position.
Value handle that asserts if the Value is deleted.
Definition: ValueHandle.h:237
bool isInsertedInstruction(Instruction *I) const
Return true if the specified instruction was inserted by the code rewriter.
This node represents an addition of some number of SCEVs.
This class represents a signed maximum selection.
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:89
Value * expandUnionPredicate(const SCEVUnionPredicate *Pred, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
This class uses information about analyze scalars to rewrite expressions in canonical form...
This class represents a zero extension of a small integer value to a larger integer value...
This class represents an analyzed expression in the program.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:464
#define I(x, y, z)
Definition: MD5.cpp:58
This class represents a sign extension of a small integer value to a larger integer value...
This class represents an unsigned maximum selection.
Instruction * getIVIncOperand(Instruction *IncV, Instruction *InsertPos, bool allowScale)
Return the induction variable increment&#39;s IV operand.
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:91
unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT, SmallVectorImpl< WeakTrackingVH > &DeadInsts, const TargetTransformInfo *TTI=nullptr)
replace congruent phis with their most canonical representative.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This class represents a composition of other SCEV predicates, and is the class that most clients will...
Value * expandEqualPredicate(const SCEVEqualPredicate *Pred, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
LLVM Value Representation.
Definition: Value.h:72
static const char * name
BasicBlock::iterator GetInsertPoint() const
Definition: IRBuilder.h:121
void disableCanonicalMode()
Disable the behavior of expanding expressions in canonical form rather than in a more literal form...
This class represents an assumption made on an AddRec expression.
void setPostInc(const PostIncLoopSet &L)
Enable post-inc expansion for addrecs referring to the given loops.
bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE)
Return true if the given expression is safe to expand in the sense that all materialized values are s...
This class represents an assumption that two SCEV expressions are equal, and this can be checked at r...
This class represents a constant integer value.