LLVM  6.0.0svn
ScalarEvolutionExpander.h
Go to the documentation of this file.
1 //===---- llvm/Analysis/ScalarEvolutionExpander.h - SCEV Exprs --*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines the classes used to generate code from scalar expressions.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPANDER_H
15 #define LLVM_ANALYSIS_SCALAREVOLUTIONEXPANDER_H
16 
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/DenseSet.h"
19 #include "llvm/ADT/Optional.h"
23 #include "llvm/IR/IRBuilder.h"
24 #include "llvm/IR/ValueHandle.h"
25 
26 namespace llvm {
27  class TargetTransformInfo;
28 
29  /// Return true if the given expression is safe to expand in the sense that
30  /// all materialized values are safe to speculate anywhere their operands are
31  /// defined.
32  bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE);
33 
34  /// Return true if the given expression is safe to expand in the sense that
35  /// all materialized values are defined and safe to speculate at the specified
36  /// location and their operands are defined at this location.
37  bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint,
38  ScalarEvolution &SE);
39 
40  /// This class uses information about analyze scalars to rewrite expressions
41  /// in canonical form.
42  ///
43  /// Clients should create an instance of this class when rewriting is needed,
44  /// and destroy it when finished to allow the release of the associated
45  /// memory.
46  class SCEVExpander : public SCEVVisitor<SCEVExpander, Value*> {
47  ScalarEvolution &SE;
48  const DataLayout &DL;
49 
50  // New instructions receive a name to identifies them with the current pass.
51  const char* IVName;
52 
53  // InsertedExpressions caches Values for reuse, so must track RAUW.
55  InsertedExpressions;
56 
57  // InsertedValues only flags inserted instructions so needs no RAUW.
58  DenseSet<AssertingVH<Value>> InsertedValues;
59  DenseSet<AssertingVH<Value>> InsertedPostIncValues;
60 
61  /// A memoization of the "relevant" loop for a given SCEV.
63 
64  /// Addrecs referring to any of the given loops are expanded in post-inc
65  /// mode. For example, expanding {1,+,1}<L> in post-inc mode returns the add
66  /// instruction that adds one to the phi for {0,+,1}<L>, as opposed to a new
67  /// phi starting at 1. This is only supported in non-canonical mode.
68  PostIncLoopSet PostIncLoops;
69 
70  /// When this is non-null, addrecs expanded in the loop it indicates should
71  /// be inserted with increments at IVIncInsertPos.
72  const Loop *IVIncInsertLoop;
73 
74  /// When expanding addrecs in the IVIncInsertLoop loop, insert the IV
75  /// increment at this position.
76  Instruction *IVIncInsertPos;
77 
78  /// Phis that complete an IV chain. Reuse
79  DenseSet<AssertingVH<PHINode>> ChainedPhis;
80 
81  /// When true, expressions are expanded in "canonical" form. In particular,
82  /// addrecs are expanded as arithmetic based on a canonical induction
83  /// variable. When false, expression are expanded in a more literal form.
84  bool CanonicalMode;
85 
86  /// When invoked from LSR, the expander is in "strength reduction" mode. The
87  /// only difference is that phi's are only reused if they are already in
88  /// "expanded" form.
89  bool LSRMode;
90 
92  BuilderType Builder;
93 
94  // RAII object that stores the current insertion point and restores it when
95  // the object is destroyed. This includes the debug location. Duplicated
96  // from InsertPointGuard to add SetInsertPoint() which is used to updated
97  // InsertPointGuards stack when insert points are moved during SCEV
98  // expansion.
99  class SCEVInsertPointGuard {
100  IRBuilderBase &Builder;
102  BasicBlock::iterator Point;
103  DebugLoc DbgLoc;
104  SCEVExpander *SE;
105 
106  SCEVInsertPointGuard(const SCEVInsertPointGuard &) = delete;
107  SCEVInsertPointGuard &operator=(const SCEVInsertPointGuard &) = delete;
108 
109  public:
110  SCEVInsertPointGuard(IRBuilderBase &B, SCEVExpander *SE)
111  : Builder(B), Block(B.GetInsertBlock()), Point(B.GetInsertPoint()),
112  DbgLoc(B.getCurrentDebugLocation()), SE(SE) {
113  SE->InsertPointGuards.push_back(this);
114  }
115 
116  ~SCEVInsertPointGuard() {
117  // These guards should always created/destroyed in FIFO order since they
118  // are used to guard lexically scoped blocks of code in
119  // ScalarEvolutionExpander.
120  assert(SE->InsertPointGuards.back() == this);
121  SE->InsertPointGuards.pop_back();
122  Builder.restoreIP(IRBuilderBase::InsertPoint(Block, Point));
123  Builder.SetCurrentDebugLocation(DbgLoc);
124  }
125 
126  BasicBlock::iterator GetInsertPoint() const { return Point; }
127  void SetInsertPoint(BasicBlock::iterator I) { Point = I; }
128  };
129 
130  /// Stack of pointers to saved insert points, used to keep insert points
131  /// consistent when instructions are moved.
132  SmallVector<SCEVInsertPointGuard *, 8> InsertPointGuards;
133 
134 #ifndef NDEBUG
135  const char *DebugType;
136 #endif
137 
138  friend struct SCEVVisitor<SCEVExpander, Value*>;
139 
140  public:
141  /// Construct a SCEVExpander in "canonical" mode.
142  explicit SCEVExpander(ScalarEvolution &se, const DataLayout &DL,
143  const char *name)
144  : SE(se), DL(DL), IVName(name), IVIncInsertLoop(nullptr),
145  IVIncInsertPos(nullptr), CanonicalMode(true), LSRMode(false),
146  Builder(se.getContext(), TargetFolder(DL)) {
147 #ifndef NDEBUG
148  DebugType = "";
149 #endif
150  }
151 
153  // Make sure the insert point guard stack is consistent.
154  assert(InsertPointGuards.empty());
155  }
156 
157 #ifndef NDEBUG
158  void setDebugType(const char* s) { DebugType = s; }
159 #endif
160 
161  /// Erase the contents of the InsertedExpressions map so that users trying
162  /// to expand the same expression into multiple BasicBlocks or different
163  /// places within the same BasicBlock can do so.
164  void clear() {
165  InsertedExpressions.clear();
166  InsertedValues.clear();
167  InsertedPostIncValues.clear();
168  ChainedPhis.clear();
169  }
170 
171  /// Return true for expressions that may incur non-trivial cost to evaluate
172  /// at runtime.
173  ///
174  /// At is an optional parameter which specifies point in code where user is
175  /// going to expand this expression. Sometimes this knowledge can lead to a
176  /// more accurate cost estimation.
177  bool isHighCostExpansion(const SCEV *Expr, Loop *L,
178  const Instruction *At = nullptr) {
180  return isHighCostExpansionHelper(Expr, L, At, Processed);
181  }
182 
183  /// This method returns the canonical induction variable of the specified
184  /// type for the specified loop (inserting one if there is none). A
185  /// canonical induction variable starts at zero and steps by one on each
186  /// iteration.
188 
189  /// Return the induction variable increment's IV operand.
191  bool allowScale);
192 
193  /// Utility for hoisting an IV increment.
194  bool hoistIVInc(Instruction *IncV, Instruction *InsertPos);
195 
196  /// replace congruent phis with their most canonical representative. Return
197  /// the number of phis eliminated.
198  unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT,
200  const TargetTransformInfo *TTI = nullptr);
201 
202  /// Insert code to directly compute the specified SCEV expression into the
203  /// program. The inserted code is inserted into the specified block.
204  Value *expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I);
205 
206  /// Insert code to directly compute the specified SCEV expression into the
207  /// program. The inserted code is inserted into the SCEVExpander's current
208  /// insertion point. If a type is specified, the result will be expanded to
209  /// have that type, with a cast if necessary.
210  Value *expandCodeFor(const SCEV *SH, Type *Ty = nullptr);
211 
212 
213  /// Generates a code sequence that evaluates this predicate. The inserted
214  /// instructions will be at position \p Loc. The result will be of type i1
215  /// and will have a value of 0 when the predicate is false and 1 otherwise.
217 
218  /// A specialized variant of expandCodeForPredicate, handling the case when
219  /// we are expanding code for a SCEVEqualPredicate.
221  Instruction *Loc);
222 
223  /// Generates code that evaluates if the \p AR expression will overflow.
225  bool Signed);
226 
227  /// A specialized variant of expandCodeForPredicate, handling the case when
228  /// we are expanding code for a SCEVWrapPredicate.
230 
231  /// A specialized variant of expandCodeForPredicate, handling the case when
232  /// we are expanding code for a SCEVUnionPredicate.
234  Instruction *Loc);
235 
236  /// Set the current IV increment loop and position.
237  void setIVIncInsertPos(const Loop *L, Instruction *Pos) {
238  assert(!CanonicalMode &&
239  "IV increment positions are not supported in CanonicalMode");
240  IVIncInsertLoop = L;
241  IVIncInsertPos = Pos;
242  }
243 
244  /// Enable post-inc expansion for addrecs referring to the given
245  /// loops. Post-inc expansion is only supported in non-canonical mode.
246  void setPostInc(const PostIncLoopSet &L) {
247  assert(!CanonicalMode &&
248  "Post-inc expansion is not supported in CanonicalMode");
249  PostIncLoops = L;
250  }
251 
252  /// Disable all post-inc expansion.
253  void clearPostInc() {
254  PostIncLoops.clear();
255 
256  // When we change the post-inc loop set, cached expansions may no
257  // longer be valid.
258  InsertedPostIncValues.clear();
259  }
260 
261  /// Disable the behavior of expanding expressions in canonical form rather
262  /// than in a more literal form. Non-canonical mode is useful for late
263  /// optimization passes.
264  void disableCanonicalMode() { CanonicalMode = false; }
265 
266  void enableLSRMode() { LSRMode = true; }
267 
268  /// Set the current insertion point. This is useful if multiple calls to
269  /// expandCodeFor() are going to be made with the same insert point and the
270  /// insert point may be moved during one of the expansions (e.g. if the
271  /// insert point is not a block terminator).
273  assert(IP);
274  Builder.SetInsertPoint(IP);
275  }
276 
277  /// Clear the current insertion point. This is useful if the instruction
278  /// that had been serving as the insertion point may have been deleted.
280  Builder.ClearInsertionPoint();
281  }
282 
283  /// Return true if the specified instruction was inserted by the code
284  /// rewriter. If so, the client should not modify the instruction.
286  return InsertedValues.count(I) || InsertedPostIncValues.count(I);
287  }
288 
289  void setChainedPhi(PHINode *PN) { ChainedPhis.insert(PN); }
290 
291  /// Try to find existing LLVM IR value for S available at the point At.
292  Value *getExactExistingExpansion(const SCEV *S, const Instruction *At,
293  Loop *L);
294 
295  /// Try to find the ValueOffsetPair for S. The function is mainly used to
296  /// check whether S can be expanded cheaply. If this returns a non-None
297  /// value, we know we can codegen the `ValueOffsetPair` into a suitable
298  /// expansion identical with S so that S can be expanded cheaply.
299  ///
300  /// L is a hint which tells in which loop to look for the suitable value.
301  /// On success return value which is equivalent to the expanded S at point
302  /// At. Return nullptr if value was not found.
303  ///
304  /// Note that this function does not perform an exhaustive search. I.e if it
305  /// didn't find any value it does not mean that there is no such value.
306  ///
308  getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L);
309 
310  private:
311  LLVMContext &getContext() const { return SE.getContext(); }
312 
313  /// Recursive helper function for isHighCostExpansion.
314  bool isHighCostExpansionHelper(const SCEV *S, Loop *L,
315  const Instruction *At,
316  SmallPtrSetImpl<const SCEV *> &Processed);
317 
318  /// Insert the specified binary operator, doing a small amount of work to
319  /// avoid inserting an obviously redundant operation.
320  Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS);
321 
322  /// Arrange for there to be a cast of V to Ty at IP, reusing an existing
323  /// cast if a suitable one exists, moving an existing cast if a suitable one
324  /// exists but isn't in the right place, or or creating a new one.
325  Value *ReuseOrCreateCast(Value *V, Type *Ty,
328 
329  /// Insert a cast of V to the specified type, which must be possible with a
330  /// noop cast, doing what we can to share the casts.
331  Value *InsertNoopCastOfTo(Value *V, Type *Ty);
332 
333  /// Expand a SCEVAddExpr with a pointer type into a GEP instead of using
334  /// ptrtoint+arithmetic+inttoptr.
335  Value *expandAddToGEP(const SCEV *const *op_begin,
336  const SCEV *const *op_end,
337  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:90
void push_back(const T &Elt)
Definition: SmallVector.h:212
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
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.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
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:221
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:34
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
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:42
LLVMContext & getContext() const
const DebugLoc & getCurrentDebugLocation() const
Get location information used by debugging information.
Definition: IRBuilder.h:155
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:122
void ClearInsertionPoint()
Clear the insertion point: created instructions will not be inserted into a block.
Definition: IRBuilder.h:117
TargetFolder - Create constants with target dependent folding.
Definition: TargetFolder.h:32
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Definition: IRBuilder.h:152
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block...
Definition: IRBuilder.h:128
Class to represent pointers.
Definition: DerivedTypes.h:467
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:201
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:69
void setInsertPoint(Instruction *IP)
Set the current insertion point.
Value handle that tracks a Value across RAUW.
Definition: ValueHandle.h:337
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:28
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:169
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:238
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:91
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...
Basic Alias true
This class represents an analyzed expression in the program.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:439
#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:73
static const char * name
BasicBlock::iterator GetInsertPoint() const
Definition: IRBuilder.h:123
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.