LLVM  14.0.0git
ScalarEvolutionExpander.h
Go to the documentation of this file.
1 //===---- llvm/Analysis/ScalarEvolutionExpander.h - SCEV Exprs --*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the classes used to generate code from scalar expressions.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H
14 #define LLVM_TRANSFORMS_UTILS_SCALAREVOLUTIONEXPANDER_H
15 
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/DenseSet.h"
18 #include "llvm/ADT/Optional.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/SmallVector.h"
25 #include "llvm/IR/IRBuilder.h"
26 #include "llvm/IR/ValueHandle.h"
29 
30 namespace llvm {
31 extern cl::opt<unsigned> SCEVCheapExpansionBudget;
32 
33 /// Return true if the given expression is safe to expand in the sense that
34 /// all materialized values are safe to speculate anywhere their operands are
35 /// defined.
36 bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE);
37 
38 /// Return true if the given expression is safe to expand in the sense that
39 /// all materialized values are defined and safe to speculate at the specified
40 /// location and their operands are defined at this location.
41 bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint,
42  ScalarEvolution &SE);
43 
44 /// struct for holding enough information to help calculate the cost of the
45 /// given SCEV when expanded into IR.
46 struct SCEVOperand {
47  explicit SCEVOperand(unsigned Opc, int Idx, const SCEV *S) :
48  ParentOpcode(Opc), OperandIdx(Idx), S(S) { }
49  /// LLVM instruction opcode that uses the operand.
50  unsigned ParentOpcode;
51  /// The use index of an expanded instruction.
53  /// The SCEV operand to be costed.
54  const SCEV* S;
55 };
56 
57 /// This class uses information about analyze scalars to rewrite expressions
58 /// in canonical form.
59 ///
60 /// Clients should create an instance of this class when rewriting is needed,
61 /// and destroy it when finished to allow the release of the associated
62 /// memory.
63 class SCEVExpander : public SCEVVisitor<SCEVExpander, Value *> {
64  ScalarEvolution &SE;
65  const DataLayout &DL;
66 
67  // New instructions receive a name to identify them with the current pass.
68  const char *IVName;
69 
70  /// Indicates whether LCSSA phis should be created for inserted values.
71  bool PreserveLCSSA;
72 
73  // InsertedExpressions caches Values for reuse, so must track RAUW.
75  InsertedExpressions;
76 
77  // InsertedValues only flags inserted instructions so needs no RAUW.
78  DenseSet<AssertingVH<Value>> InsertedValues;
79  DenseSet<AssertingVH<Value>> InsertedPostIncValues;
80 
81  /// Keep track of the existing IR values re-used during expansion.
82  /// FIXME: Ideally re-used instructions would not be added to
83  /// InsertedValues/InsertedPostIncValues.
84  SmallPtrSet<Value *, 16> ReusedValues;
85 
86  // The induction variables generated.
87  SmallVector<WeakVH, 2> InsertedIVs;
88 
89  /// A memoization of the "relevant" loop for a given SCEV.
91 
92  /// Addrecs referring to any of the given loops are expanded in post-inc
93  /// mode. For example, expanding {1,+,1}<L> in post-inc mode returns the add
94  /// instruction that adds one to the phi for {0,+,1}<L>, as opposed to a new
95  /// phi starting at 1. This is only supported in non-canonical mode.
96  PostIncLoopSet PostIncLoops;
97 
98  /// When this is non-null, addrecs expanded in the loop it indicates should
99  /// be inserted with increments at IVIncInsertPos.
100  const Loop *IVIncInsertLoop;
101 
102  /// When expanding addrecs in the IVIncInsertLoop loop, insert the IV
103  /// increment at this position.
104  Instruction *IVIncInsertPos;
105 
106  /// Phis that complete an IV chain. Reuse
107  DenseSet<AssertingVH<PHINode>> ChainedPhis;
108 
109  /// When true, SCEVExpander tries to expand expressions in "canonical" form.
110  /// When false, expressions are expanded in a more literal form.
111  ///
112  /// In "canonical" form addrecs are expanded as arithmetic based on a
113  /// canonical induction variable. Note that CanonicalMode doesn't guarantee
114  /// that all expressions are expanded in "canonical" form. For some
115  /// expressions literal mode can be preferred.
116  bool CanonicalMode;
117 
118  /// When invoked from LSR, the expander is in "strength reduction" mode. The
119  /// only difference is that phi's are only reused if they are already in
120  /// "expanded" form.
121  bool LSRMode;
122 
124  BuilderType Builder;
125 
126  // RAII object that stores the current insertion point and restores it when
127  // the object is destroyed. This includes the debug location. Duplicated
128  // from InsertPointGuard to add SetInsertPoint() which is used to updated
129  // InsertPointGuards stack when insert points are moved during SCEV
130  // expansion.
131  class SCEVInsertPointGuard {
134  BasicBlock::iterator Point;
135  DebugLoc DbgLoc;
136  SCEVExpander *SE;
137 
138  SCEVInsertPointGuard(const SCEVInsertPointGuard &) = delete;
139  SCEVInsertPointGuard &operator=(const SCEVInsertPointGuard &) = delete;
140 
141  public:
142  SCEVInsertPointGuard(IRBuilderBase &B, SCEVExpander *SE)
143  : Builder(B), Block(B.GetInsertBlock()), Point(B.GetInsertPoint()),
144  DbgLoc(B.getCurrentDebugLocation()), SE(SE) {
145  SE->InsertPointGuards.push_back(this);
146  }
147 
148  ~SCEVInsertPointGuard() {
149  // These guards should always created/destroyed in FIFO order since they
150  // are used to guard lexically scoped blocks of code in
151  // ScalarEvolutionExpander.
152  assert(SE->InsertPointGuards.back() == this);
153  SE->InsertPointGuards.pop_back();
154  Builder.restoreIP(IRBuilderBase::InsertPoint(Block, Point));
155  Builder.SetCurrentDebugLocation(DbgLoc);
156  }
157 
158  BasicBlock::iterator GetInsertPoint() const { return Point; }
159  void SetInsertPoint(BasicBlock::iterator I) { Point = I; }
160  };
161 
162  /// Stack of pointers to saved insert points, used to keep insert points
163  /// consistent when instructions are moved.
164  SmallVector<SCEVInsertPointGuard *, 8> InsertPointGuards;
165 
166 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
167  const char *DebugType;
168 #endif
169 
170  friend struct SCEVVisitor<SCEVExpander, Value *>;
171 
172 public:
173  /// Construct a SCEVExpander in "canonical" mode.
175  const char *name, bool PreserveLCSSA = true)
176  : SE(se), DL(DL), IVName(name), PreserveLCSSA(PreserveLCSSA),
177  IVIncInsertLoop(nullptr), IVIncInsertPos(nullptr), CanonicalMode(true),
178  LSRMode(false),
179  Builder(se.getContext(), TargetFolder(DL),
181  [this](Instruction *I) { rememberInstruction(I); })) {
182 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
183  DebugType = "";
184 #endif
185  }
186 
188  // Make sure the insert point guard stack is consistent.
189  assert(InsertPointGuards.empty());
190  }
191 
192 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
193  void setDebugType(const char *s) { DebugType = s; }
194 #endif
195 
196  /// Erase the contents of the InsertedExpressions map so that users trying
197  /// to expand the same expression into multiple BasicBlocks or different
198  /// places within the same BasicBlock can do so.
199  void clear() {
200  InsertedExpressions.clear();
201  InsertedValues.clear();
202  InsertedPostIncValues.clear();
203  ReusedValues.clear();
204  ChainedPhis.clear();
205  InsertedIVs.clear();
206  }
207 
208  ScalarEvolution *getSE() { return &SE; }
209  const SmallVectorImpl<WeakVH> &getInsertedIVs() const { return InsertedIVs; }
210 
211  /// Return a vector containing all instructions inserted during expansion.
214  for (auto &VH : InsertedValues) {
215  Value *V = VH;
216  if (ReusedValues.contains(V))
217  continue;
218  if (auto *Inst = dyn_cast<Instruction>(V))
219  Result.push_back(Inst);
220  }
221  for (auto &VH : InsertedPostIncValues) {
222  Value *V = VH;
223  if (ReusedValues.contains(V))
224  continue;
225  if (auto *Inst = dyn_cast<Instruction>(V))
226  Result.push_back(Inst);
227  }
228 
229  return Result;
230  }
231 
232  /// Return true for expressions that can't be evaluated at runtime
233  /// within given \b Budget.
234  ///
235  /// At is a parameter which specifies point in code where user is going to
236  /// expand this expression. Sometimes this knowledge can lead to
237  /// a less pessimistic cost estimation.
238  bool isHighCostExpansion(const SCEV *Expr, Loop *L, unsigned Budget,
239  const TargetTransformInfo *TTI,
240  const Instruction *At) {
241  assert(TTI && "This function requires TTI to be provided.");
242  assert(At && "This function requires At instruction to be provided.");
243  if (!TTI) // In assert-less builds, avoid crashing
244  return true; // by always claiming to be high-cost.
247  InstructionCost Cost = 0;
248  unsigned ScaledBudget = Budget * TargetTransformInfo::TCC_Basic;
249  Worklist.emplace_back(-1, -1, Expr);
250  while (!Worklist.empty()) {
251  const SCEVOperand WorkItem = Worklist.pop_back_val();
252  if (isHighCostExpansionHelper(WorkItem, L, *At, Cost, ScaledBudget, *TTI,
253  Processed, Worklist))
254  return true;
255  }
256  assert(Cost <= ScaledBudget && "Should have returned from inner loop.");
257  return false;
258  }
259 
260  /// Return the induction variable increment's IV operand.
262  bool allowScale);
263 
264  /// Utility for hoisting an IV increment.
265  bool hoistIVInc(Instruction *IncV, Instruction *InsertPos);
266 
267  /// replace congruent phis with their most canonical representative. Return
268  /// the number of phis eliminated.
269  unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT,
271  const TargetTransformInfo *TTI = nullptr);
272 
273  /// Insert code to directly compute the specified SCEV expression into the
274  /// program. The code is inserted into the specified block.
275  Value *expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I) {
276  return expandCodeForImpl(SH, Ty, I, true);
277  }
278 
279  /// Insert code to directly compute the specified SCEV expression into the
280  /// program. The code is inserted into the SCEVExpander's current
281  /// insertion point. If a type is specified, the result will be expanded to
282  /// have that type, with a cast if necessary.
283  Value *expandCodeFor(const SCEV *SH, Type *Ty = nullptr) {
284  return expandCodeForImpl(SH, Ty, true);
285  }
286 
287  /// Generates a code sequence that evaluates this predicate. The inserted
288  /// instructions will be at position \p Loc. The result will be of type i1
289  /// and will have a value of 0 when the predicate is false and 1 otherwise.
291 
292  /// A specialized variant of expandCodeForPredicate, handling the case when
293  /// we are expanding code for a SCEVEqualPredicate.
295 
296  /// Generates code that evaluates if the \p AR expression will overflow.
298  bool Signed);
299 
300  /// A specialized variant of expandCodeForPredicate, handling the case when
301  /// we are expanding code for a SCEVWrapPredicate.
303 
304  /// A specialized variant of expandCodeForPredicate, handling the case when
305  /// we are expanding code for a SCEVUnionPredicate.
307 
308  /// Set the current IV increment loop and position.
309  void setIVIncInsertPos(const Loop *L, Instruction *Pos) {
310  assert(!CanonicalMode &&
311  "IV increment positions are not supported in CanonicalMode");
312  IVIncInsertLoop = L;
313  IVIncInsertPos = Pos;
314  }
315 
316  /// Enable post-inc expansion for addrecs referring to the given
317  /// loops. Post-inc expansion is only supported in non-canonical mode.
318  void setPostInc(const PostIncLoopSet &L) {
319  assert(!CanonicalMode &&
320  "Post-inc expansion is not supported in CanonicalMode");
321  PostIncLoops = L;
322  }
323 
324  /// Disable all post-inc expansion.
325  void clearPostInc() {
326  PostIncLoops.clear();
327 
328  // When we change the post-inc loop set, cached expansions may no
329  // longer be valid.
330  InsertedPostIncValues.clear();
331  }
332 
333  /// Disable the behavior of expanding expressions in canonical form rather
334  /// than in a more literal form. Non-canonical mode is useful for late
335  /// optimization passes.
336  void disableCanonicalMode() { CanonicalMode = false; }
337 
338  void enableLSRMode() { LSRMode = true; }
339 
340  /// Set the current insertion point. This is useful if multiple calls to
341  /// expandCodeFor() are going to be made with the same insert point and the
342  /// insert point may be moved during one of the expansions (e.g. if the
343  /// insert point is not a block terminator).
345  assert(IP);
346  Builder.SetInsertPoint(IP);
347  }
348 
349  /// Clear the current insertion point. This is useful if the instruction
350  /// that had been serving as the insertion point may have been deleted.
351  void clearInsertPoint() { Builder.ClearInsertionPoint(); }
352 
353  /// Set location information used by debugging information.
355  Builder.SetCurrentDebugLocation(std::move(L));
356  }
357 
358  /// Get location information used by debugging information.
360  return Builder.getCurrentDebugLocation();
361  }
362 
363  /// Return true if the specified instruction was inserted by the code
364  /// rewriter. If so, the client should not modify the instruction. Note that
365  /// this also includes instructions re-used during expansion.
367  return InsertedValues.count(I) || InsertedPostIncValues.count(I);
368  }
369 
370  void setChainedPhi(PHINode *PN) { ChainedPhis.insert(PN); }
371 
372  /// Try to find the ValueOffsetPair for S. The function is mainly used to
373  /// check whether S can be expanded cheaply. If this returns a non-None
374  /// value, we know we can codegen the `ValueOffsetPair` into a suitable
375  /// expansion identical with S so that S can be expanded cheaply.
376  ///
377  /// L is a hint which tells in which loop to look for the suitable value.
378  /// On success return value which is equivalent to the expanded S at point
379  /// At. Return nullptr if value was not found.
380  ///
381  /// Note that this function does not perform an exhaustive search. I.e if it
382  /// didn't find any value it does not mean that there is no such value.
383  ///
385  getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L);
386 
387  /// Returns a suitable insert point after \p I, that dominates \p
388  /// MustDominate. Skips instructions inserted by the expander.
390  Instruction *MustDominate) const;
391 
392 private:
393  LLVMContext &getContext() const { return SE.getContext(); }
394 
395  /// Insert code to directly compute the specified SCEV expression into the
396  /// program. The code is inserted into the SCEVExpander's current
397  /// insertion point. If a type is specified, the result will be expanded to
398  /// have that type, with a cast if necessary. If \p Root is true, this
399  /// indicates that \p SH is the top-level expression to expand passed from
400  /// an external client call.
401  Value *expandCodeForImpl(const SCEV *SH, Type *Ty, bool Root);
402 
403  /// Insert code to directly compute the specified SCEV expression into the
404  /// program. The code is inserted into the specified block. If \p
405  /// Root is true, this indicates that \p SH is the top-level expression to
406  /// expand passed from an external client call.
407  Value *expandCodeForImpl(const SCEV *SH, Type *Ty, Instruction *I, bool Root);
408 
409  /// Recursive helper function for isHighCostExpansion.
410  bool isHighCostExpansionHelper(const SCEVOperand &WorkItem, Loop *L,
411  const Instruction &At, InstructionCost &Cost,
412  unsigned Budget,
413  const TargetTransformInfo &TTI,
414  SmallPtrSetImpl<const SCEV *> &Processed,
415  SmallVectorImpl<SCEVOperand> &Worklist);
416 
417  /// Insert the specified binary operator, doing a small amount of work to
418  /// avoid inserting an obviously redundant operation, and hoisting to an
419  /// outer loop when the opportunity is there and it is safe.
420  Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
421  SCEV::NoWrapFlags Flags, bool IsSafeToHoist);
422 
423  /// We want to cast \p V. What would be the best place for such a cast?
424  BasicBlock::iterator GetOptimalInsertionPointForCastOf(Value *V) const;
425 
426  /// Arrange for there to be a cast of V to Ty at IP, reusing an existing
427  /// cast if a suitable one exists, moving an existing cast if a suitable one
428  /// exists but isn't in the right place, or creating a new one.
429  Value *ReuseOrCreateCast(Value *V, Type *Ty, Instruction::CastOps Op,
431 
432  /// Insert a cast of V to the specified type, which must be possible with a
433  /// noop cast, doing what we can to share the casts.
434  Value *InsertNoopCastOfTo(Value *V, Type *Ty);
435 
436  /// Expand a SCEVAddExpr with a pointer type into a GEP instead of using
437  /// ptrtoint+arithmetic+inttoptr.
438  Value *expandAddToGEP(const SCEV *const *op_begin, const SCEV *const *op_end,
439  PointerType *PTy, Type *Ty, Value *V);
440  Value *expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty, Value *V);
441 
442  /// Find a previous Value in ExprValueMap for expand.
443  ScalarEvolution::ValueOffsetPair
444  FindValueInExprValueMap(const SCEV *S, const Instruction *InsertPt);
445 
446  Value *expand(const SCEV *S);
447 
448  /// Determine the most "relevant" loop for the given SCEV.
449  const Loop *getRelevantLoop(const SCEV *);
450 
451  Value *visitConstant(const SCEVConstant *S) { return S->getValue(); }
452 
453  Value *visitPtrToIntExpr(const SCEVPtrToIntExpr *S);
454 
455  Value *visitTruncateExpr(const SCEVTruncateExpr *S);
456 
457  Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);
458 
459  Value *visitSignExtendExpr(const SCEVSignExtendExpr *S);
460 
461  Value *visitAddExpr(const SCEVAddExpr *S);
462 
463  Value *visitMulExpr(const SCEVMulExpr *S);
464 
465  Value *visitUDivExpr(const SCEVUDivExpr *S);
466 
467  Value *visitAddRecExpr(const SCEVAddRecExpr *S);
468 
469  Value *visitSMaxExpr(const SCEVSMaxExpr *S);
470 
471  Value *visitUMaxExpr(const SCEVUMaxExpr *S);
472 
473  Value *visitSMinExpr(const SCEVSMinExpr *S);
474 
475  Value *visitUMinExpr(const SCEVUMinExpr *S);
476 
477  Value *visitUnknown(const SCEVUnknown *S) { return S->getValue(); }
478 
479  void rememberInstruction(Value *I);
480 
481  bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
482 
483  bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
484 
485  Value *expandAddRecExprLiterally(const SCEVAddRecExpr *);
486  PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
487  const Loop *L, Type *ExpandTy, Type *IntTy,
488  Type *&TruncTy, bool &InvertStep);
489  Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L, Type *ExpandTy,
490  Type *IntTy, bool useSubtract);
491 
492  void hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist,
493  Instruction *Pos, PHINode *LoopPhi);
494 
495  void fixupInsertPoints(Instruction *I);
496 
497  /// If required, create LCSSA PHIs for \p Users' operand \p OpIdx. If new
498  /// LCSSA PHIs have been created, return the LCSSA PHI available at \p User.
499  /// If no PHIs have been created, return the unchanged operand \p OpIdx.
500  Value *fixupLCSSAFormFor(Instruction *User, unsigned OpIdx);
501 };
502 
503 /// Helper to remove instructions inserted during SCEV expansion, unless they
504 /// are marked as used.
506  SCEVExpander &Expander;
507 
508  DominatorTree &DT;
509 
510  /// Indicates whether the result of the expansion is used. If false, the
511  /// instructions added during expansion are removed.
512  bool ResultUsed;
513 
514 public:
516  : Expander(Expander), DT(DT), ResultUsed(false) {}
517 
519 
520  /// Indicate that the result of the expansion is used.
521  void markResultUsed() { ResultUsed = true; }
522 
523  void cleanup();
524 };
525 } // namespace llvm
526 
527 #endif
llvm::SCEVExpander::getInsertedIVs
const SmallVectorImpl< WeakVH > & getInsertedIVs() const
Definition: ScalarEvolutionExpander.h:209
llvm::SCEVExpander::~SCEVExpander
~SCEVExpander()
Definition: ScalarEvolutionExpander.h:187
llvm::InstructionCost
Definition: InstructionCost.h:29
llvm::ScalarEvolution::getContext
LLVMContext & getContext() const
Definition: ScalarEvolution.h:481
llvm::SCEVExpander::getSE
ScalarEvolution * getSE()
Definition: ScalarEvolutionExpander.h:208
PointerType
Definition: ItaniumDemangle.h:477
Signed
@ Signed
Definition: NVPTXISelLowering.cpp:4630
llvm::SCEVExpanderCleaner::cleanup
void cleanup()
Definition: ScalarEvolutionExpander.cpp:2743
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
Optional.h
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
ScalarEvolutionNormalization.h
llvm::SCEVOperand::SCEVOperand
SCEVOperand(unsigned Opc, int Idx, const SCEV *S)
Definition: ScalarEvolutionExpander.h:47
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
TargetFolder.h
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::SCEVExpander
This class uses information about analyze scalars to rewrite expressions in canonical form.
Definition: ScalarEvolutionExpander.h:63
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
llvm::IRBuilder< TargetFolder, IRBuilderCallbackInserter >
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:443
llvm::SCEVExpanderCleaner::SCEVExpanderCleaner
SCEVExpanderCleaner(SCEVExpander &Expander, DominatorTree &DT)
Definition: ScalarEvolutionExpander.h:515
llvm::SCEVExpander::getCurrentDebugLocation
DebugLoc getCurrentDebugLocation() const
Get location information used by debugging information.
Definition: ScalarEvolutionExpander.h:359
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::SCEVExpander::expandCodeFor
Value * expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I)
Insert code to directly compute the specified SCEV expression into the program.
Definition: ScalarEvolutionExpander.h:275
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
DenseMap.h
llvm::SCEVExpanderCleaner::markResultUsed
void markResultUsed()
Indicate that the result of the expansion is used.
Definition: ScalarEvolutionExpander.h:521
llvm::Optional
Definition: APInt.h:33
llvm::SCEVExpander::clearPostInc
void clearPostInc()
Disable all post-inc expansion.
Definition: ScalarEvolutionExpander.h:325
llvm::SmallPtrSet< Value *, 16 >
llvm::SCEVExpander::setPostInc
void setPostInc(const PostIncLoopSet &L)
Enable post-inc expansion for addrecs referring to the given loops.
Definition: ScalarEvolutionExpander.h:318
llvm::SCEVExpander::hoistIVInc
bool hoistIVInc(Instruction *IncV, Instruction *InsertPos)
Utility for hoisting an IV increment.
Definition: ScalarEvolutionExpander.cpp:1054
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::SCEVOperand
struct for holding enough information to help calculate the cost of the given SCEV when expanded into...
Definition: ScalarEvolutionExpander.h:46
llvm::SCEVExpander::getRelatedExistingExpansion
Optional< ScalarEvolution::ValueOffsetPair > getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L)
Try to find the ValueOffsetPair for S.
Definition: ScalarEvolutionExpander.cpp:2202
llvm::SCEVPredicate
This class represents an assumption made using SCEV expressions which can be checked at run-time.
Definition: ScalarEvolution.h:200
llvm::SCEVOperand::OperandIdx
int OperandIdx
The use index of an expanded instruction.
Definition: ScalarEvolutionExpander.h:52
llvm::SCEVExpander::enableLSRMode
void enableLSRMode()
Definition: ScalarEvolutionExpander.h:338
llvm::SCEVExpanderCleaner::~SCEVExpanderCleaner
~SCEVExpanderCleaner()
Definition: ScalarEvolutionExpander.h:518
llvm::isSafeToExpand
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...
Definition: ScalarEvolutionExpander.cpp:2715
CommandLine.h
llvm::SCEVVisitor
This class defines a simple visitor class that may be used for various SCEV analysis purposes.
Definition: ScalarEvolutionExpressions.h:576
llvm::SCEVExpander::isHighCostExpansion
bool isHighCostExpansion(const SCEV *Expr, Loop *L, unsigned Budget, const TargetTransformInfo *TTI, const Instruction *At)
Return true for expressions that can't be evaluated at runtime within given Budget.
Definition: ScalarEvolutionExpander.h:238
llvm::COFF::DebugType
DebugType
Definition: COFF.h:652
llvm::SCEVExpander::clearInsertPoint
void clearInsertPoint()
Clear the current insertion point.
Definition: ScalarEvolutionExpander.h:351
IP
Definition: NVPTXLowerArgs.cpp:166
DenseSet.h
false
Definition: StackSlotColoring.cpp:142
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction::CastOps
CastOps
Definition: Instruction.h:801
llvm::Instruction
Definition: Instruction.h:45
llvm::SCEVExpander::isInsertedInstruction
bool isInsertedInstruction(Instruction *I) const
Return true if the specified instruction was inserted by the code rewriter.
Definition: ScalarEvolutionExpander.h:366
llvm::SCEVExpander::setIVIncInsertPos
void setIVIncInsertPos(const Loop *L, Instruction *Pos)
Set the current IV increment loop and position.
Definition: ScalarEvolutionExpander.h:309
llvm::SCEVExpander::SetCurrentDebugLocation
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Definition: ScalarEvolutionExpander.h:354
llvm::SCEVOperand::S
const SCEV * S
The SCEV operand to be costed.
Definition: ScalarEvolutionExpander.h:54
llvm::SCEVExpander::generateOverflowCheck
Value * generateOverflowCheck(const SCEVAddRecExpr *AR, Instruction *Loc, bool Signed)
Generates code that evaluates if the AR expression will overflow.
Definition: ScalarEvolutionExpander.cpp:2498
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:78
llvm::SCEVExpander::findInsertPointAfter
BasicBlock::iterator findInsertPointAfter(Instruction *I, Instruction *MustDominate) const
Returns a suitable insert point after I, that dominates MustDominate.
Definition: ScalarEvolutionExpander.cpp:100
expand
static Expected< BitVector > expand(StringRef S, StringRef Original)
Definition: GlobPattern.cpp:27
llvm::SCEVExpander::expandCodeFor
Value * expandCodeFor(const SCEV *SH, Type *Ty=nullptr)
Insert code to directly compute the specified SCEV expression into the program.
Definition: ScalarEvolutionExpander.h:283
llvm::SCEVEqualPredicate
This class represents an assumption that two SCEV expressions are equal, and this can be checked at r...
Definition: ScalarEvolution.h:267
llvm::SCEVExpander::expandUnionPredicate
Value * expandUnionPredicate(const SCEVUnionPredicate *Pred, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
Definition: ScalarEvolutionExpander.cpp:2623
s
multiplies can be turned into SHL s
Definition: README.txt:370
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::SCEVExpander::disableCanonicalMode
void disableCanonicalMode()
Disable the behavior of expanding expressions in canonical form rather than in a more literal form.
Definition: ScalarEvolutionExpander.h:336
llvm::SCEVCheapExpansionBudget
cl::opt< unsigned > SCEVCheapExpansionBudget
TemplateParamKind::Type
@ Type
llvm::TrackingVH< Value >
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::TTI
TargetTransformInfo TTI
Definition: TargetTransformInfo.h:163
llvm::SCEVExpanderCleaner
Helper to remove instructions inserted during SCEV expansion, unless they are marked as used.
Definition: ScalarEvolutionExpander.h:505
llvm::IRBuilderCallbackInserter
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
Definition: IRBuilder.h:77
llvm::SCEVExpander::clear
void clear()
Erase the contents of the InsertedExpressions map so that users trying to expand the same expression ...
Definition: ScalarEvolutionExpander.h:199
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
InstructionCost.h
llvm::SCEVExpander::getAllInsertedInstructions
SmallVector< Instruction *, 32 > getAllInsertedInstructions() const
Return a vector containing all instructions inserted during expansion.
Definition: ScalarEvolutionExpander.h:212
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:94
this
Analysis the ScalarEvolution expression for r is this
Definition: README.txt:8
llvm::SCEVExpander::setInsertPoint
void setInsertPoint(Instruction *IP)
Set the current insertion point.
Definition: ScalarEvolutionExpander.h:344
llvm::IRBuilderBase
Common base class shared among various IRBuilders.
Definition: IRBuilder.h:95
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
ValueHandle.h
llvm::SCEV::NoWrapFlags
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
Definition: ScalarEvolution.h:115
name
static const char * name
Definition: SVEIntrinsicOpts.cpp:79
llvm::TargetFolder
TargetFolder - Create constants with target dependent folding.
Definition: TargetFolder.h:32
llvm::SCEVExpander::replaceCongruentIVs
unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT, SmallVectorImpl< WeakTrackingVH > &DeadInsts, const TargetTransformInfo *TTI=nullptr)
replace congruent phis with their most canonical representative.
Definition: ScalarEvolutionExpander.cpp:2062
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
llvm::SCEVUnionPredicate
This class represents a composition of other SCEV predicates, and is the class that most clients will...
Definition: ScalarEvolution.h:399
llvm::SCEVAddRecExpr
This node represents a polynomial recurrence on the trip count of the specified loop.
Definition: ScalarEvolutionExpressions.h:352
llvm::SCEVWrapPredicate
This class represents an assumption made on an AddRec expression.
Definition: ScalarEvolution.h:304
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::SCEVExpander::setChainedPhi
void setChainedPhi(PHINode *PN)
Definition: ScalarEvolutionExpander.h:370
llvm::SCEVOperand::ParentOpcode
unsigned ParentOpcode
LLVM instruction opcode that uses the operand.
Definition: ScalarEvolutionExpander.h:50
llvm::SCEVExpander::expandEqualPredicate
Value * expandEqualPredicate(const SCEVEqualPredicate *Pred, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
Definition: ScalarEvolutionExpander.cpp:2486
ScalarEvolutionExpressions.h
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:787
llvm::IRBuilderBase::InsertPoint
InsertPoint - A saved insertion point.
Definition: IRBuilder.h:251
llvm::isSafeToExpandAt
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...
Definition: ScalarEvolutionExpander.cpp:2721
SmallVector.h
llvm::SCEVExpander::expandCodeForPredicate
Value * expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc)
Generates a code sequence that evaluates this predicate.
Definition: ScalarEvolutionExpander.cpp:2470
llvm::AssertingVH
Value handle that asserts if the Value is deleted.
Definition: ValueHandle.h:260
TargetTransformInfo.h
llvm::PHINode
Definition: Instructions.h:2627
llvm::SCEVExpander::getIVIncOperand
Instruction * getIVIncOperand(Instruction *IncV, Instruction *InsertPos, bool allowScale)
Return the induction variable increment's IV operand.
Definition: ScalarEvolutionExpander.cpp:987
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::SCEVExpander::expandWrapPredicate
Value * expandWrapPredicate(const SCEVWrapPredicate *P, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
Definition: ScalarEvolutionExpander.cpp:2598
llvm::SCEVExpander::SCEVExpander
SCEVExpander(ScalarEvolution &se, const DataLayout &DL, const char *name, bool PreserveLCSSA=true)
Construct a SCEVExpander in "canonical" mode.
Definition: ScalarEvolutionExpander.h:174
llvm::TargetTransformInfo::TCC_Basic
@ TCC_Basic
The cost of a typical 'add' instruction.
Definition: TargetTransformInfo.h:263
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::SmallPtrSetImpl::contains
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:388
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1815
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
SetVector.h
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:908