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