LLVM  10.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, SCEVExpander tries to expand expressions in "canonical" form.
81  /// When false, expressions are expanded in a more literal form.
82  ///
83  /// In "canonical" form addrecs are expanded as arithmetic based on a
84  /// canonical induction variable. Note that CanonicalMode doesn't guarantee
85  /// that all expressions are expanded in "canonical" form. For some
86  /// expressions literal mode can be preferred.
87  bool CanonicalMode;
88 
89  /// When invoked from LSR, the expander is in "strength reduction" mode. The
90  /// only difference is that phi's are only reused if they are already in
91  /// "expanded" form.
92  bool LSRMode;
93 
95  BuilderType Builder;
96 
97  // RAII object that stores the current insertion point and restores it when
98  // the object is destroyed. This includes the debug location. Duplicated
99  // from InsertPointGuard to add SetInsertPoint() which is used to updated
100  // InsertPointGuards stack when insert points are moved during SCEV
101  // expansion.
102  class SCEVInsertPointGuard {
103  IRBuilderBase &Builder;
105  BasicBlock::iterator Point;
106  DebugLoc DbgLoc;
107  SCEVExpander *SE;
108 
109  SCEVInsertPointGuard(const SCEVInsertPointGuard &) = delete;
110  SCEVInsertPointGuard &operator=(const SCEVInsertPointGuard &) = delete;
111 
112  public:
113  SCEVInsertPointGuard(IRBuilderBase &B, SCEVExpander *SE)
114  : Builder(B), Block(B.GetInsertBlock()), Point(B.GetInsertPoint()),
115  DbgLoc(B.getCurrentDebugLocation()), SE(SE) {
116  SE->InsertPointGuards.push_back(this);
117  }
118 
119  ~SCEVInsertPointGuard() {
120  // These guards should always created/destroyed in FIFO order since they
121  // are used to guard lexically scoped blocks of code in
122  // ScalarEvolutionExpander.
123  assert(SE->InsertPointGuards.back() == this);
124  SE->InsertPointGuards.pop_back();
125  Builder.restoreIP(IRBuilderBase::InsertPoint(Block, Point));
126  Builder.SetCurrentDebugLocation(DbgLoc);
127  }
128 
129  BasicBlock::iterator GetInsertPoint() const { return Point; }
130  void SetInsertPoint(BasicBlock::iterator I) { Point = I; }
131  };
132 
133  /// Stack of pointers to saved insert points, used to keep insert points
134  /// consistent when instructions are moved.
135  SmallVector<SCEVInsertPointGuard *, 8> InsertPointGuards;
136 
137 #ifndef NDEBUG
138  const char *DebugType;
139 #endif
140 
141  friend struct SCEVVisitor<SCEVExpander, Value*>;
142 
143  public:
144  /// Construct a SCEVExpander in "canonical" mode.
145  explicit SCEVExpander(ScalarEvolution &se, const DataLayout &DL,
146  const char *name)
147  : SE(se), DL(DL), IVName(name), IVIncInsertLoop(nullptr),
148  IVIncInsertPos(nullptr), CanonicalMode(true), LSRMode(false),
149  Builder(se.getContext(), TargetFolder(DL)) {
150 #ifndef NDEBUG
151  DebugType = "";
152 #endif
153  }
154 
156  // Make sure the insert point guard stack is consistent.
157  assert(InsertPointGuards.empty());
158  }
159 
160 #ifndef NDEBUG
161  void setDebugType(const char* s) { DebugType = s; }
162 #endif
163 
164  /// Erase the contents of the InsertedExpressions map so that users trying
165  /// to expand the same expression into multiple BasicBlocks or different
166  /// places within the same BasicBlock can do so.
167  void clear() {
168  InsertedExpressions.clear();
169  InsertedValues.clear();
170  InsertedPostIncValues.clear();
171  ChainedPhis.clear();
172  }
173 
174  /// Return true for expressions that may incur non-trivial cost to evaluate
175  /// at runtime.
176  ///
177  /// At is an optional parameter which specifies point in code where user is
178  /// going to expand this expression. Sometimes this knowledge can lead to a
179  /// more accurate cost estimation.
180  bool isHighCostExpansion(const SCEV *Expr, Loop *L,
181  const Instruction *At = nullptr) {
183  return isHighCostExpansionHelper(Expr, L, At, Processed);
184  }
185 
186  /// This method returns the canonical induction variable of the specified
187  /// type for the specified loop (inserting one if there is none). A
188  /// canonical induction variable starts at zero and steps by one on each
189  /// iteration.
191 
192  /// Return the induction variable increment's IV operand.
194  bool allowScale);
195 
196  /// Utility for hoisting an IV increment.
197  bool hoistIVInc(Instruction *IncV, Instruction *InsertPos);
198 
199  /// replace congruent phis with their most canonical representative. Return
200  /// the number of phis eliminated.
201  unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT,
203  const TargetTransformInfo *TTI = nullptr);
204 
205  /// Insert code to directly compute the specified SCEV expression into the
206  /// program. The inserted code is inserted into the specified block.
207  Value *expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I);
208 
209  /// Insert code to directly compute the specified SCEV expression into the
210  /// program. The inserted code is inserted into the SCEVExpander's current
211  /// insertion point. If a type is specified, the result will be expanded to
212  /// have that type, with a cast if necessary.
213  Value *expandCodeFor(const SCEV *SH, Type *Ty = nullptr);
214 
215 
216  /// Generates a code sequence that evaluates this predicate. The inserted
217  /// instructions will be at position \p Loc. The result will be of type i1
218  /// and will have a value of 0 when the predicate is false and 1 otherwise.
220 
221  /// A specialized variant of expandCodeForPredicate, handling the case when
222  /// we are expanding code for a SCEVEqualPredicate.
224  Instruction *Loc);
225 
226  /// Generates code that evaluates if the \p AR expression will overflow.
228  bool Signed);
229 
230  /// A specialized variant of expandCodeForPredicate, handling the case when
231  /// we are expanding code for a SCEVWrapPredicate.
233 
234  /// A specialized variant of expandCodeForPredicate, handling the case when
235  /// we are expanding code for a SCEVUnionPredicate.
237  Instruction *Loc);
238 
239  /// Set the current IV increment loop and position.
240  void setIVIncInsertPos(const Loop *L, Instruction *Pos) {
241  assert(!CanonicalMode &&
242  "IV increment positions are not supported in CanonicalMode");
243  IVIncInsertLoop = L;
244  IVIncInsertPos = Pos;
245  }
246 
247  /// Enable post-inc expansion for addrecs referring to the given
248  /// loops. Post-inc expansion is only supported in non-canonical mode.
249  void setPostInc(const PostIncLoopSet &L) {
250  assert(!CanonicalMode &&
251  "Post-inc expansion is not supported in CanonicalMode");
252  PostIncLoops = L;
253  }
254 
255  /// Disable all post-inc expansion.
256  void clearPostInc() {
257  PostIncLoops.clear();
258 
259  // When we change the post-inc loop set, cached expansions may no
260  // longer be valid.
261  InsertedPostIncValues.clear();
262  }
263 
264  /// Disable the behavior of expanding expressions in canonical form rather
265  /// than in a more literal form. Non-canonical mode is useful for late
266  /// optimization passes.
267  void disableCanonicalMode() { CanonicalMode = false; }
268 
269  void enableLSRMode() { LSRMode = true; }
270 
271  /// Set the current insertion point. This is useful if multiple calls to
272  /// expandCodeFor() are going to be made with the same insert point and the
273  /// insert point may be moved during one of the expansions (e.g. if the
274  /// insert point is not a block terminator).
276  assert(IP);
277  Builder.SetInsertPoint(IP);
278  }
279 
280  /// Clear the current insertion point. This is useful if the instruction
281  /// that had been serving as the insertion point may have been deleted.
282  void clearInsertPoint() { Builder.ClearInsertionPoint(); }
283 
284  /// Set location information used by debugging information.
286  Builder.SetCurrentDebugLocation(std::move(L));
287  }
288 
289  /// Get location information used by debugging information.
291  return Builder.getCurrentDebugLocation();
292  }
293 
294  /// Return true if the specified instruction was inserted by the code
295  /// rewriter. If so, the client should not modify the instruction.
297  return InsertedValues.count(I) || InsertedPostIncValues.count(I);
298  }
299 
300  void setChainedPhi(PHINode *PN) { ChainedPhis.insert(PN); }
301 
302  /// Try to find existing LLVM IR value for S available at the point At.
303  Value *getExactExistingExpansion(const SCEV *S, const Instruction *At,
304  Loop *L);
305 
306  /// Try to find the ValueOffsetPair for S. The function is mainly used to
307  /// check whether S can be expanded cheaply. If this returns a non-None
308  /// value, we know we can codegen the `ValueOffsetPair` into a suitable
309  /// expansion identical with S so that S can be expanded cheaply.
310  ///
311  /// L is a hint which tells in which loop to look for the suitable value.
312  /// On success return value which is equivalent to the expanded S at point
313  /// At. Return nullptr if value was not found.
314  ///
315  /// Note that this function does not perform an exhaustive search. I.e if it
316  /// didn't find any value it does not mean that there is no such value.
317  ///
319  getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L);
320 
321  private:
322  LLVMContext &getContext() const { return SE.getContext(); }
323 
324  /// Recursive helper function for isHighCostExpansion.
325  bool isHighCostExpansionHelper(const SCEV *S, Loop *L,
326  const Instruction *At,
327  SmallPtrSetImpl<const SCEV *> &Processed);
328 
329  /// Insert the specified binary operator, doing a small amount of work to
330  /// avoid inserting an obviously redundant operation, and hoisting to an
331  /// outer loop when the opportunity is there and it is safe.
332  Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
333  SCEV::NoWrapFlags Flags, bool IsSafeToHoist);
334 
335  /// Arrange for there to be a cast of V to Ty at IP, reusing an existing
336  /// cast if a suitable one exists, moving an existing cast if a suitable one
337  /// exists but isn't in the right place, or creating a new one.
338  Value *ReuseOrCreateCast(Value *V, Type *Ty,
341 
342  /// Insert a cast of V to the specified type, which must be possible with a
343  /// noop cast, doing what we can to share the casts.
344  Value *InsertNoopCastOfTo(Value *V, Type *Ty);
345 
346  /// Expand a SCEVAddExpr with a pointer type into a GEP instead of using
347  /// ptrtoint+arithmetic+inttoptr.
348  Value *expandAddToGEP(const SCEV *const *op_begin,
349  const SCEV *const *op_end,
350  PointerType *PTy, Type *Ty, Value *V);
351  Value *expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty, Value *V);
352 
353  /// Find a previous Value in ExprValueMap for expand.
354  ScalarEvolution::ValueOffsetPair
355  FindValueInExprValueMap(const SCEV *S, const Instruction *InsertPt);
356 
357  Value *expand(const SCEV *S);
358 
359  /// Determine the most "relevant" loop for the given SCEV.
360  const Loop *getRelevantLoop(const SCEV *);
361 
362  Value *visitConstant(const SCEVConstant *S) {
363  return S->getValue();
364  }
365 
366  Value *visitTruncateExpr(const SCEVTruncateExpr *S);
367 
368  Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);
369 
370  Value *visitSignExtendExpr(const SCEVSignExtendExpr *S);
371 
372  Value *visitAddExpr(const SCEVAddExpr *S);
373 
374  Value *visitMulExpr(const SCEVMulExpr *S);
375 
376  Value *visitUDivExpr(const SCEVUDivExpr *S);
377 
378  Value *visitAddRecExpr(const SCEVAddRecExpr *S);
379 
380  Value *visitSMaxExpr(const SCEVSMaxExpr *S);
381 
382  Value *visitUMaxExpr(const SCEVUMaxExpr *S);
383 
384  Value *visitSMinExpr(const SCEVSMinExpr *S);
385 
386  Value *visitUMinExpr(const SCEVUMinExpr *S);
387 
388  Value *visitUnknown(const SCEVUnknown *S) {
389  return S->getValue();
390  }
391 
392  void rememberInstruction(Value *I);
393 
394  bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
395 
396  bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
397 
398  Value *expandAddRecExprLiterally(const SCEVAddRecExpr *);
399  PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
400  const Loop *L,
401  Type *ExpandTy,
402  Type *IntTy,
403  Type *&TruncTy,
404  bool &InvertStep);
405  Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L,
406  Type *ExpandTy, Type *IntTy, bool useSubtract);
407 
408  void hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist,
409  Instruction *Pos, PHINode *LoopPhi);
410 
411  void fixupInsertPoints(Instruction *I);
412  };
413 }
414 
415 #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:112
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
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
const DebugLoc & getCurrentDebugLocation() const
Get location information used by debugging information.
Definition: IRBuilder.h:159
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:126
void ClearInsertionPoint()
Clear the insertion point: created instructions will not be inserted into a block.
Definition: IRBuilder.h:121
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:156
This class represents a signed minimum selection.
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:132
Class to represent pointers.
Definition: DerivedTypes.h:575
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:205
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:46
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
This class represents an unsigned minimum selection.
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:173
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...
const DebugLoc & getCurrentDebugLocation() const
Get location information used by debugging information.
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:509
#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:74
static const char * name
BasicBlock::iterator GetInsertPoint() const
Definition: IRBuilder.h:127
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.
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
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.