LLVM  13.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/SmallVector.h"
24 #include "llvm/IR/IRBuilder.h"
25 #include "llvm/IR/ValueHandle.h"
28 
29 namespace llvm {
30 extern cl::opt<unsigned> SCEVCheapExpansionBudget;
31 
32 /// Return true if the given expression is safe to expand in the sense that
33 /// all materialized values are safe to speculate anywhere their operands are
34 /// defined.
35 bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE);
36 
37 /// Return true if the given expression is safe to expand in the sense that
38 /// all materialized values are defined and safe to speculate at the specified
39 /// location and their operands are defined at this location.
40 bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint,
41  ScalarEvolution &SE);
42 
43 /// struct for holding enough information to help calculate the cost of the
44 /// given SCEV when expanded into IR.
45 struct SCEVOperand {
46  explicit SCEVOperand(unsigned Opc, int Idx, const SCEV *S) :
47  ParentOpcode(Opc), OperandIdx(Idx), S(S) { }
48  /// LLVM instruction opcode that uses the operand.
49  unsigned ParentOpcode;
50  /// The use index of an expanded instruction.
52  /// The SCEV operand to be costed.
53  const SCEV* S;
54 };
55 
56 /// This class uses information about analyze scalars to rewrite expressions
57 /// in canonical form.
58 ///
59 /// Clients should create an instance of this class when rewriting is needed,
60 /// and destroy it when finished to allow the release of the associated
61 /// memory.
62 class SCEVExpander : public SCEVVisitor<SCEVExpander, Value *> {
63  ScalarEvolution &SE;
64  const DataLayout &DL;
65 
66  // New instructions receive a name to identify them with the current pass.
67  const char *IVName;
68 
69  /// Indicates whether LCSSA phis should be created for inserted values.
70  bool PreserveLCSSA;
71 
72  // InsertedExpressions caches Values for reuse, so must track RAUW.
74  InsertedExpressions;
75 
76  // InsertedValues only flags inserted instructions so needs no RAUW.
77  DenseSet<AssertingVH<Value>> InsertedValues;
78  DenseSet<AssertingVH<Value>> InsertedPostIncValues;
79 
80  /// Keep track of the existing IR values re-used during expansion.
81  /// FIXME: Ideally re-used instructions would not be added to
82  /// InsertedValues/InsertedPostIncValues.
83  SmallPtrSet<Value *, 16> ReusedValues;
84 
85  /// A memoization of the "relevant" loop for a given SCEV.
87 
88  /// Addrecs referring to any of the given loops are expanded in post-inc
89  /// mode. For example, expanding {1,+,1}<L> in post-inc mode returns the add
90  /// instruction that adds one to the phi for {0,+,1}<L>, as opposed to a new
91  /// phi starting at 1. This is only supported in non-canonical mode.
92  PostIncLoopSet PostIncLoops;
93 
94  /// When this is non-null, addrecs expanded in the loop it indicates should
95  /// be inserted with increments at IVIncInsertPos.
96  const Loop *IVIncInsertLoop;
97 
98  /// When expanding addrecs in the IVIncInsertLoop loop, insert the IV
99  /// increment at this position.
100  Instruction *IVIncInsertPos;
101 
102  /// Phis that complete an IV chain. Reuse
103  DenseSet<AssertingVH<PHINode>> ChainedPhis;
104 
105  /// When true, SCEVExpander tries to expand expressions in "canonical" form.
106  /// When false, expressions are expanded in a more literal form.
107  ///
108  /// In "canonical" form addrecs are expanded as arithmetic based on a
109  /// canonical induction variable. Note that CanonicalMode doesn't guarantee
110  /// that all expressions are expanded in "canonical" form. For some
111  /// expressions literal mode can be preferred.
112  bool CanonicalMode;
113 
114  /// When invoked from LSR, the expander is in "strength reduction" mode. The
115  /// only difference is that phi's are only reused if they are already in
116  /// "expanded" form.
117  bool LSRMode;
118 
120  BuilderType Builder;
121 
122  // RAII object that stores the current insertion point and restores it when
123  // the object is destroyed. This includes the debug location. Duplicated
124  // from InsertPointGuard to add SetInsertPoint() which is used to updated
125  // InsertPointGuards stack when insert points are moved during SCEV
126  // expansion.
127  class SCEVInsertPointGuard {
130  BasicBlock::iterator Point;
131  DebugLoc DbgLoc;
132  SCEVExpander *SE;
133 
134  SCEVInsertPointGuard(const SCEVInsertPointGuard &) = delete;
135  SCEVInsertPointGuard &operator=(const SCEVInsertPointGuard &) = delete;
136 
137  public:
138  SCEVInsertPointGuard(IRBuilderBase &B, SCEVExpander *SE)
139  : Builder(B), Block(B.GetInsertBlock()), Point(B.GetInsertPoint()),
140  DbgLoc(B.getCurrentDebugLocation()), SE(SE) {
141  SE->InsertPointGuards.push_back(this);
142  }
143 
144  ~SCEVInsertPointGuard() {
145  // These guards should always created/destroyed in FIFO order since they
146  // are used to guard lexically scoped blocks of code in
147  // ScalarEvolutionExpander.
148  assert(SE->InsertPointGuards.back() == this);
149  SE->InsertPointGuards.pop_back();
150  Builder.restoreIP(IRBuilderBase::InsertPoint(Block, Point));
151  Builder.SetCurrentDebugLocation(DbgLoc);
152  }
153 
154  BasicBlock::iterator GetInsertPoint() const { return Point; }
155  void SetInsertPoint(BasicBlock::iterator I) { Point = I; }
156  };
157 
158  /// Stack of pointers to saved insert points, used to keep insert points
159  /// consistent when instructions are moved.
160  SmallVector<SCEVInsertPointGuard *, 8> InsertPointGuards;
161 
162 #ifndef NDEBUG
163  const char *DebugType;
164 #endif
165 
166  friend struct SCEVVisitor<SCEVExpander, Value *>;
167 
168 public:
169  /// Construct a SCEVExpander in "canonical" mode.
171  const char *name, bool PreserveLCSSA = true)
172  : SE(se), DL(DL), IVName(name), PreserveLCSSA(PreserveLCSSA),
173  IVIncInsertLoop(nullptr), IVIncInsertPos(nullptr), CanonicalMode(true),
174  LSRMode(false),
175  Builder(se.getContext(), TargetFolder(DL),
177  [this](Instruction *I) { rememberInstruction(I); })) {
178 #ifndef NDEBUG
179  DebugType = "";
180 #endif
181  }
182 
184  // Make sure the insert point guard stack is consistent.
185  assert(InsertPointGuards.empty());
186  }
187 
188 #ifndef NDEBUG
189  void setDebugType(const char *s) { DebugType = s; }
190 #endif
191 
192  /// Erase the contents of the InsertedExpressions map so that users trying
193  /// to expand the same expression into multiple BasicBlocks or different
194  /// places within the same BasicBlock can do so.
195  void clear() {
196  InsertedExpressions.clear();
197  InsertedValues.clear();
198  InsertedPostIncValues.clear();
199  ReusedValues.clear();
200  ChainedPhis.clear();
201  }
202 
203  ScalarEvolution *getSE() { return &SE; }
204 
205  /// Return a vector containing all instructions inserted during expansion.
208  for (auto &VH : InsertedValues) {
209  Value *V = VH;
210  if (ReusedValues.contains(V))
211  continue;
212  if (auto *Inst = dyn_cast<Instruction>(V))
213  Result.push_back(Inst);
214  }
215  for (auto &VH : InsertedPostIncValues) {
216  Value *V = VH;
217  if (ReusedValues.contains(V))
218  continue;
219  if (auto *Inst = dyn_cast<Instruction>(V))
220  Result.push_back(Inst);
221  }
222 
223  return Result;
224  }
225 
226  /// Return true for expressions that can't be evaluated at runtime
227  /// within given \b Budget.
228  ///
229  /// At is a parameter which specifies point in code where user is going to
230  /// expand this expression. Sometimes this knowledge can lead to
231  /// a less pessimistic cost estimation.
232  bool isHighCostExpansion(const SCEV *Expr, Loop *L, unsigned Budget,
233  const TargetTransformInfo *TTI,
234  const Instruction *At) {
235  assert(TTI && "This function requires TTI to be provided.");
236  assert(At && "This function requires At instruction to be provided.");
237  if (!TTI) // In assert-less builds, avoid crashing
238  return true; // by always claiming to be high-cost.
241  InstructionCost Cost = 0;
242  unsigned ScaledBudget = Budget * TargetTransformInfo::TCC_Basic;
243  Worklist.emplace_back(-1, -1, Expr);
244  while (!Worklist.empty()) {
245  const SCEVOperand WorkItem = Worklist.pop_back_val();
246  if (isHighCostExpansionHelper(WorkItem, L, *At, Cost, ScaledBudget, *TTI,
247  Processed, Worklist))
248  return true;
249  }
250  assert(Cost <= ScaledBudget && "Should have returned from inner loop.");
251  return false;
252  }
253 
254  /// Return the induction variable increment's IV operand.
256  bool allowScale);
257 
258  /// Utility for hoisting an IV increment.
259  bool hoistIVInc(Instruction *IncV, Instruction *InsertPos);
260 
261  /// replace congruent phis with their most canonical representative. Return
262  /// the number of phis eliminated.
263  unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT,
265  const TargetTransformInfo *TTI = nullptr);
266 
267  /// Insert code to directly compute the specified SCEV expression into the
268  /// program. The code is inserted into the specified block.
269  Value *expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I) {
270  return expandCodeForImpl(SH, Ty, I, true);
271  }
272 
273  /// Insert code to directly compute the specified SCEV expression into the
274  /// program. The code is inserted into the SCEVExpander's current
275  /// insertion point. If a type is specified, the result will be expanded to
276  /// have that type, with a cast if necessary.
277  Value *expandCodeFor(const SCEV *SH, Type *Ty = nullptr) {
278  return expandCodeForImpl(SH, Ty, true);
279  }
280 
281  /// Generates a code sequence that evaluates this predicate. The inserted
282  /// instructions will be at position \p Loc. The result will be of type i1
283  /// and will have a value of 0 when the predicate is false and 1 otherwise.
285 
286  /// A specialized variant of expandCodeForPredicate, handling the case when
287  /// we are expanding code for a SCEVEqualPredicate.
289 
290  /// Generates code that evaluates if the \p AR expression will overflow.
292  bool Signed);
293 
294  /// A specialized variant of expandCodeForPredicate, handling the case when
295  /// we are expanding code for a SCEVWrapPredicate.
297 
298  /// A specialized variant of expandCodeForPredicate, handling the case when
299  /// we are expanding code for a SCEVUnionPredicate.
301 
302  /// Set the current IV increment loop and position.
303  void setIVIncInsertPos(const Loop *L, Instruction *Pos) {
304  assert(!CanonicalMode &&
305  "IV increment positions are not supported in CanonicalMode");
306  IVIncInsertLoop = L;
307  IVIncInsertPos = Pos;
308  }
309 
310  /// Enable post-inc expansion for addrecs referring to the given
311  /// loops. Post-inc expansion is only supported in non-canonical mode.
312  void setPostInc(const PostIncLoopSet &L) {
313  assert(!CanonicalMode &&
314  "Post-inc expansion is not supported in CanonicalMode");
315  PostIncLoops = L;
316  }
317 
318  /// Disable all post-inc expansion.
319  void clearPostInc() {
320  PostIncLoops.clear();
321 
322  // When we change the post-inc loop set, cached expansions may no
323  // longer be valid.
324  InsertedPostIncValues.clear();
325  }
326 
327  /// Disable the behavior of expanding expressions in canonical form rather
328  /// than in a more literal form. Non-canonical mode is useful for late
329  /// optimization passes.
330  void disableCanonicalMode() { CanonicalMode = false; }
331 
332  void enableLSRMode() { LSRMode = true; }
333 
334  /// Set the current insertion point. This is useful if multiple calls to
335  /// expandCodeFor() are going to be made with the same insert point and the
336  /// insert point may be moved during one of the expansions (e.g. if the
337  /// insert point is not a block terminator).
339  assert(IP);
340  Builder.SetInsertPoint(IP);
341  }
342 
343  /// Clear the current insertion point. This is useful if the instruction
344  /// that had been serving as the insertion point may have been deleted.
345  void clearInsertPoint() { Builder.ClearInsertionPoint(); }
346 
347  /// Set location information used by debugging information.
349  Builder.SetCurrentDebugLocation(std::move(L));
350  }
351 
352  /// Get location information used by debugging information.
354  return Builder.getCurrentDebugLocation();
355  }
356 
357  /// Return true if the specified instruction was inserted by the code
358  /// rewriter. If so, the client should not modify the instruction. Note that
359  /// this also includes instructions re-used during expansion.
361  return InsertedValues.count(I) || InsertedPostIncValues.count(I);
362  }
363 
364  void setChainedPhi(PHINode *PN) { ChainedPhis.insert(PN); }
365 
366  /// Try to find the ValueOffsetPair for S. The function is mainly used to
367  /// check whether S can be expanded cheaply. If this returns a non-None
368  /// value, we know we can codegen the `ValueOffsetPair` into a suitable
369  /// expansion identical with S so that S can be expanded cheaply.
370  ///
371  /// L is a hint which tells in which loop to look for the suitable value.
372  /// On success return value which is equivalent to the expanded S at point
373  /// At. Return nullptr if value was not found.
374  ///
375  /// Note that this function does not perform an exhaustive search. I.e if it
376  /// didn't find any value it does not mean that there is no such value.
377  ///
379  getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L);
380 
381  /// Returns a suitable insert point after \p I, that dominates \p
382  /// MustDominate. Skips instructions inserted by the expander.
384  Instruction *MustDominate);
385 
386 private:
387  LLVMContext &getContext() const { return SE.getContext(); }
388 
389  /// Insert code to directly compute the specified SCEV expression into the
390  /// program. The code is inserted into the SCEVExpander's current
391  /// insertion point. If a type is specified, the result will be expanded to
392  /// have that type, with a cast if necessary. If \p Root is true, this
393  /// indicates that \p SH is the top-level expression to expand passed from
394  /// an external client call.
395  Value *expandCodeForImpl(const SCEV *SH, Type *Ty, bool Root);
396 
397  /// Insert code to directly compute the specified SCEV expression into the
398  /// program. The code is inserted into the specified block. If \p
399  /// Root is true, this indicates that \p SH is the top-level expression to
400  /// expand passed from an external client call.
401  Value *expandCodeForImpl(const SCEV *SH, Type *Ty, Instruction *I, bool Root);
402 
403  /// Recursive helper function for isHighCostExpansion.
404  bool isHighCostExpansionHelper(const SCEVOperand &WorkItem, Loop *L,
405  const Instruction &At, InstructionCost &Cost,
406  unsigned Budget,
407  const TargetTransformInfo &TTI,
408  SmallPtrSetImpl<const SCEV *> &Processed,
409  SmallVectorImpl<SCEVOperand> &Worklist);
410 
411  /// Insert the specified binary operator, doing a small amount of work to
412  /// avoid inserting an obviously redundant operation, and hoisting to an
413  /// outer loop when the opportunity is there and it is safe.
414  Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
415  SCEV::NoWrapFlags Flags, bool IsSafeToHoist);
416 
417  /// Arrange for there to be a cast of V to Ty at IP, reusing an existing
418  /// cast if a suitable one exists, moving an existing cast if a suitable one
419  /// exists but isn't in the right place, or creating a new one.
420  Value *ReuseOrCreateCast(Value *V, Type *Ty, Instruction::CastOps Op,
422 
423  /// Insert a cast of V to the specified type, which must be possible with a
424  /// noop cast, doing what we can to share the casts.
425  Value *InsertNoopCastOfTo(Value *V, Type *Ty);
426 
427  /// Expand a SCEVAddExpr with a pointer type into a GEP instead of using
428  /// ptrtoint+arithmetic+inttoptr.
429  Value *expandAddToGEP(const SCEV *const *op_begin, const SCEV *const *op_end,
430  PointerType *PTy, Type *Ty, Value *V);
431  Value *expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty, Value *V);
432 
433  /// Find a previous Value in ExprValueMap for expand.
434  ScalarEvolution::ValueOffsetPair
435  FindValueInExprValueMap(const SCEV *S, const Instruction *InsertPt);
436 
437  Value *expand(const SCEV *S);
438 
439  /// Determine the most "relevant" loop for the given SCEV.
440  const Loop *getRelevantLoop(const SCEV *);
441 
442  Value *visitConstant(const SCEVConstant *S) { return S->getValue(); }
443 
444  Value *visitPtrToIntExpr(const SCEVPtrToIntExpr *S);
445 
446  Value *visitTruncateExpr(const SCEVTruncateExpr *S);
447 
448  Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);
449 
450  Value *visitSignExtendExpr(const SCEVSignExtendExpr *S);
451 
452  Value *visitAddExpr(const SCEVAddExpr *S);
453 
454  Value *visitMulExpr(const SCEVMulExpr *S);
455 
456  Value *visitUDivExpr(const SCEVUDivExpr *S);
457 
458  Value *visitAddRecExpr(const SCEVAddRecExpr *S);
459 
460  Value *visitSMaxExpr(const SCEVSMaxExpr *S);
461 
462  Value *visitUMaxExpr(const SCEVUMaxExpr *S);
463 
464  Value *visitSMinExpr(const SCEVSMinExpr *S);
465 
466  Value *visitUMinExpr(const SCEVUMinExpr *S);
467 
468  Value *visitUnknown(const SCEVUnknown *S) { return S->getValue(); }
469 
470  void rememberInstruction(Value *I);
471 
472  bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
473 
474  bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
475 
476  Value *expandAddRecExprLiterally(const SCEVAddRecExpr *);
477  PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
478  const Loop *L, Type *ExpandTy, Type *IntTy,
479  Type *&TruncTy, bool &InvertStep);
480  Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L, Type *ExpandTy,
481  Type *IntTy, bool useSubtract);
482 
483  void hoistBeforePos(DominatorTree *DT, Instruction *InstToHoist,
484  Instruction *Pos, PHINode *LoopPhi);
485 
486  void fixupInsertPoints(Instruction *I);
487 
488  /// If required, create LCSSA PHIs for \p Users' operand \p OpIdx. If new
489  /// LCSSA PHIs have been created, return the LCSSA PHI available at \p User.
490  /// If no PHIs have been created, return the unchanged operand \p OpIdx.
491  Value *fixupLCSSAFormFor(Instruction *User, unsigned OpIdx);
492 };
493 
494 /// Helper to remove instructions inserted during SCEV expansion, unless they
495 /// are marked as used.
497  SCEVExpander &Expander;
498 
499  DominatorTree &DT;
500 
501  /// Indicates whether the result of the expansion is used. If false, the
502  /// instructions added during expansion are removed.
503  bool ResultUsed;
504 
505 public:
507  : Expander(Expander), DT(DT), ResultUsed(false) {}
508 
510 
511  /// Indicate that the result of the expansion is used.
512  void markResultUsed() { ResultUsed = true; }
513 };
514 } // namespace llvm
515 
516 #endif
llvm::SCEVExpander::~SCEVExpander
~SCEVExpander()
Definition: ScalarEvolutionExpander.h:183
llvm::InstructionCost
Definition: InstructionCost.h:26
llvm::ScalarEvolution::getContext
LLVMContext & getContext() const
Definition: ScalarEvolution.h:481
llvm::SCEVExpander::getSE
ScalarEvolution * getSE()
Definition: ScalarEvolutionExpander.h:203
PointerType
Definition: ItaniumDemangle.h:474
Signed
@ Signed
Definition: NVPTXISelLowering.cpp:4550
llvm
This class represents lattice values for constants.
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:111
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:46
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:529
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:62
llvm::SmallVector< SCEVInsertPointGuard *, 8 >
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:167
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:506
llvm::SCEVExpander::getCurrentDebugLocation
DebugLoc getCurrentDebugLocation() const
Get location information used by debugging information.
Definition: ScalarEvolutionExpander.h:353
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:269
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
DenseMap.h
llvm::SCEVExpander::setDebugType
void setDebugType(const char *s)
Definition: ScalarEvolutionExpander.h:189
llvm::SCEVExpanderCleaner::markResultUsed
void markResultUsed()
Indicate that the result of the expansion is used.
Definition: ScalarEvolutionExpander.h:512
llvm::Optional
Definition: APInt.h:33
llvm::SCEVExpander::clearPostInc
void clearPostInc()
Disable all post-inc expansion.
Definition: ScalarEvolutionExpander.h:319
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:312
llvm::SCEVExpander::hoistIVInc
bool hoistIVInc(Instruction *IncV, Instruction *InsertPos)
Utility for hoisting an IV increment.
Definition: ScalarEvolutionExpander.cpp:1028
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:45
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:2145
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:51
llvm::SCEVExpander::enableLSRMode
void enableLSRMode()
Definition: ScalarEvolutionExpander.h:332
llvm::SCEVExpanderCleaner::~SCEVExpanderCleaner
~SCEVExpanderCleaner()
Definition: ScalarEvolutionExpander.cpp:2682
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:2654
CommandLine.h
llvm::SCEVVisitor
This class defines a simple visitor class that may be used for various SCEV analysis purposes.
Definition: ScalarEvolutionExpressions.h:568
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:232
llvm::COFF::DebugType
DebugType
Definition: COFF.h:651
llvm::SCEVExpander::clearInsertPoint
void clearInsertPoint()
Clear the current insertion point.
Definition: ScalarEvolutionExpander.h:345
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:775
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:360
llvm::SCEVExpander::setIVIncInsertPos
void setIVIncInsertPos(const Loop *L, Instruction *Pos)
Set the current IV increment loop and position.
Definition: ScalarEvolutionExpander.h:303
llvm::SCEVExpander::SetCurrentDebugLocation
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Definition: ScalarEvolutionExpander.h:348
llvm::SCEVOperand::S
const SCEV * S
The SCEV operand to be costed.
Definition: ScalarEvolutionExpander.h:53
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:2440
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
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:277
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:2562
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:330
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:162
llvm::SCEVExpanderCleaner
Helper to remove instructions inserted during SCEV expansion, unless they are marked as used.
Definition: ScalarEvolutionExpander.h:496
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:195
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:643
InstructionCost.h
llvm::SCEVExpander::getAllInsertedInstructions
SmallVector< Instruction *, 32 > getAllInsertedInstructions() const
Return a vector containing all instructions inserted during expansion.
Definition: ScalarEvolutionExpander.h:206
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:338
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:91
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:2007
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:302
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:364
llvm::SCEVOperand::ParentOpcode
unsigned ParentOpcode
LLVM instruction opcode that uses the operand.
Definition: ScalarEvolutionExpander.h:49
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:2428
ScalarEvolutionExpressions.h
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:761
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:2660
SmallVector.h
llvm::SCEVExpander::expandCodeForPredicate
Value * expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc)
Generates a code sequence that evaluates this predicate.
Definition: ScalarEvolutionExpander.cpp:2412
llvm::AssertingVH
Value handle that asserts if the Value is deleted.
Definition: ValueHandle.h:260
llvm::SCEVExpander::findInsertPointAfter
BasicBlock::iterator findInsertPointAfter(Instruction *I, Instruction *MustDominate)
Returns a suitable insert point after I, that dominates MustDominate.
Definition: ScalarEvolutionExpander.cpp:92
TargetTransformInfo.h
llvm::PHINode
Definition: Instructions.h:2582
llvm::SCEVExpander::getIVIncOperand
Instruction * getIVIncOperand(Instruction *IncV, Instruction *InsertPos, bool allowScale)
Return the induction variable increment's IV operand.
Definition: ScalarEvolutionExpander.cpp:961
llvm::SmallVectorImpl< WeakTrackingVH >
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:2537
llvm::SCEVExpander::SCEVExpander
SCEVExpander(ScalarEvolution &se, const DataLayout &DL, const char *name, bool PreserveLCSSA=true)
Construct a SCEVExpander in "canonical" mode.
Definition: ScalarEvolutionExpander.h:170
llvm::TargetTransformInfo::TCC_Basic
@ TCC_Basic
The cost of a typical 'add' instruction.
Definition: TargetTransformInfo.h:264
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:1833
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:908