LLVM  15.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/SmallVector.h"
23 #include "llvm/IR/IRBuilder.h"
24 #include "llvm/IR/ValueHandle.h"
27 
28 namespace llvm {
29 extern cl::opt<unsigned> SCEVCheapExpansionBudget;
30 
31 /// Return true if the given expression is safe to expand in the sense that
32 /// all materialized values are safe to speculate anywhere their operands are
33 /// defined, and the expander is capable of expanding the expression.
34 /// CanonicalMode indicates whether the expander will be used in canonical mode.
35 bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE,
36  bool CanonicalMode = true);
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(), InstSimplifyFolder(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 SCEVComparePredicate.
295  Instruction *Loc);
296 
297  /// Generates code that evaluates if the \p AR expression will overflow.
299  bool Signed);
300 
301  /// A specialized variant of expandCodeForPredicate, handling the case when
302  /// we are expanding code for a SCEVWrapPredicate.
304 
305  /// A specialized variant of expandCodeForPredicate, handling the case when
306  /// we are expanding code for a SCEVUnionPredicate.
308 
309  /// Set the current IV increment loop and position.
310  void setIVIncInsertPos(const Loop *L, Instruction *Pos) {
311  assert(!CanonicalMode &&
312  "IV increment positions are not supported in CanonicalMode");
313  IVIncInsertLoop = L;
314  IVIncInsertPos = Pos;
315  }
316 
317  /// Enable post-inc expansion for addrecs referring to the given
318  /// loops. Post-inc expansion is only supported in non-canonical mode.
319  void setPostInc(const PostIncLoopSet &L) {
320  assert(!CanonicalMode &&
321  "Post-inc expansion is not supported in CanonicalMode");
322  PostIncLoops = L;
323  }
324 
325  /// Disable all post-inc expansion.
326  void clearPostInc() {
327  PostIncLoops.clear();
328 
329  // When we change the post-inc loop set, cached expansions may no
330  // longer be valid.
331  InsertedPostIncValues.clear();
332  }
333 
334  /// Disable the behavior of expanding expressions in canonical form rather
335  /// than in a more literal form. Non-canonical mode is useful for late
336  /// optimization passes.
337  void disableCanonicalMode() { CanonicalMode = false; }
338 
339  void enableLSRMode() { LSRMode = true; }
340 
341  /// Set the current insertion point. This is useful if multiple calls to
342  /// expandCodeFor() are going to be made with the same insert point and the
343  /// insert point may be moved during one of the expansions (e.g. if the
344  /// insert point is not a block terminator).
346  assert(IP);
347  Builder.SetInsertPoint(IP);
348  }
349 
350  /// Clear the current insertion point. This is useful if the instruction
351  /// that had been serving as the insertion point may have been deleted.
352  void clearInsertPoint() { Builder.ClearInsertionPoint(); }
353 
354  /// Set location information used by debugging information.
356  Builder.SetCurrentDebugLocation(std::move(L));
357  }
358 
359  /// Get location information used by debugging information.
361  return Builder.getCurrentDebugLocation();
362  }
363 
364  /// Return true if the specified instruction was inserted by the code
365  /// rewriter. If so, the client should not modify the instruction. Note that
366  /// this also includes instructions re-used during expansion.
368  return InsertedValues.count(I) || InsertedPostIncValues.count(I);
369  }
370 
371  void setChainedPhi(PHINode *PN) { ChainedPhis.insert(PN); }
372 
373  /// Try to find the ValueOffsetPair for S. The function is mainly used to
374  /// check whether S can be expanded cheaply. If this returns a non-None
375  /// value, we know we can codegen the `ValueOffsetPair` into a suitable
376  /// expansion identical with S so that S can be expanded cheaply.
377  ///
378  /// L is a hint which tells in which loop to look for the suitable value.
379  /// On success return value which is equivalent to the expanded S at point
380  /// At. Return nullptr if value was not found.
381  ///
382  /// Note that this function does not perform an exhaustive search. I.e if it
383  /// didn't find any value it does not mean that there is no such value.
384  ///
386  Loop *L);
387 
388  /// Returns a suitable insert point after \p I, that dominates \p
389  /// MustDominate. Skips instructions inserted by the expander.
391  Instruction *MustDominate) const;
392 
393 private:
394  LLVMContext &getContext() const { return SE.getContext(); }
395 
396  /// Insert code to directly compute the specified SCEV expression into the
397  /// program. The code is inserted into the SCEVExpander's current
398  /// insertion point. If a type is specified, the result will be expanded to
399  /// have that type, with a cast if necessary. If \p Root is true, this
400  /// indicates that \p SH is the top-level expression to expand passed from
401  /// an external client call.
402  Value *expandCodeForImpl(const SCEV *SH, Type *Ty, bool Root);
403 
404  /// Insert code to directly compute the specified SCEV expression into the
405  /// program. The code is inserted into the specified block. If \p
406  /// Root is true, this indicates that \p SH is the top-level expression to
407  /// expand passed from an external client call.
408  Value *expandCodeForImpl(const SCEV *SH, Type *Ty, Instruction *I, bool Root);
409 
410  /// Recursive helper function for isHighCostExpansion.
411  bool isHighCostExpansionHelper(const SCEVOperand &WorkItem, Loop *L,
412  const Instruction &At, InstructionCost &Cost,
413  unsigned Budget,
414  const TargetTransformInfo &TTI,
415  SmallPtrSetImpl<const SCEV *> &Processed,
416  SmallVectorImpl<SCEVOperand> &Worklist);
417 
418  /// Insert the specified binary operator, doing a small amount of work to
419  /// avoid inserting an obviously redundant operation, and hoisting to an
420  /// outer loop when the opportunity is there and it is safe.
421  Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
422  SCEV::NoWrapFlags Flags, bool IsSafeToHoist);
423 
424  /// We want to cast \p V. What would be the best place for such a cast?
425  BasicBlock::iterator GetOptimalInsertionPointForCastOf(Value *V) const;
426 
427  /// Arrange for there to be a cast of V to Ty at IP, reusing an existing
428  /// cast if a suitable one exists, moving an existing cast if a suitable one
429  /// exists but isn't in the right place, or creating a new one.
430  Value *ReuseOrCreateCast(Value *V, Type *Ty, Instruction::CastOps Op,
432 
433  /// Insert a cast of V to the specified type, which must be possible with a
434  /// noop cast, doing what we can to share the casts.
435  Value *InsertNoopCastOfTo(Value *V, Type *Ty);
436 
437  /// Expand a SCEVAddExpr with a pointer type into a GEP instead of using
438  /// ptrtoint+arithmetic+inttoptr.
439  Value *expandAddToGEP(const SCEV *const *op_begin, const SCEV *const *op_end,
440  PointerType *PTy, Type *Ty, Value *V);
441  Value *expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty, Value *V);
442 
443  /// Find a previous Value in ExprValueMap for expand.
444  Value *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 *expandMinMaxExpr(const SCEVNAryExpr *S, Intrinsic::ID IntrinID,
452  Twine Name, bool IsSequential = false);
453 
454  Value *visitConstant(const SCEVConstant *S) { return S->getValue(); }
455 
456  Value *visitPtrToIntExpr(const SCEVPtrToIntExpr *S);
457 
458  Value *visitTruncateExpr(const SCEVTruncateExpr *S);
459 
460  Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);
461 
462  Value *visitSignExtendExpr(const SCEVSignExtendExpr *S);
463 
464  Value *visitAddExpr(const SCEVAddExpr *S);
465 
466  Value *visitMulExpr(const SCEVMulExpr *S);
467 
468  Value *visitUDivExpr(const SCEVUDivExpr *S);
469 
470  Value *visitAddRecExpr(const SCEVAddRecExpr *S);
471 
472  Value *visitSMaxExpr(const SCEVSMaxExpr *S);
473 
474  Value *visitUMaxExpr(const SCEVUMaxExpr *S);
475 
476  Value *visitSMinExpr(const SCEVSMinExpr *S);
477 
478  Value *visitUMinExpr(const SCEVUMinExpr *S);
479 
480  Value *visitSequentialUMinExpr(const SCEVSequentialUMinExpr *S);
481 
482  Value *visitUnknown(const SCEVUnknown *S) { return S->getValue(); }
483 
484  void rememberInstruction(Value *I);
485 
486  bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
487 
488  bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
489 
490  Value *expandAddRecExprLiterally(const SCEVAddRecExpr *);
491  PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
492  const Loop *L, Type *ExpandTy, Type *IntTy,
493  Type *&TruncTy, bool &InvertStep);
494  Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L, Type *ExpandTy,
495  Type *IntTy, bool useSubtract);
496 
497  void fixupInsertPoints(Instruction *I);
498 
499  /// If required, create LCSSA PHIs for \p Users' operand \p OpIdx. If new
500  /// LCSSA PHIs have been created, return the LCSSA PHI available at \p User.
501  /// If no PHIs have been created, return the unchanged operand \p OpIdx.
502  Value *fixupLCSSAFormFor(Instruction *User, unsigned OpIdx);
503 };
504 
505 /// Helper to remove instructions inserted during SCEV expansion, unless they
506 /// are marked as used.
508  SCEVExpander &Expander;
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), 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:491
llvm::SCEVExpander::getSE
ScalarEvolution * getSE()
Definition: ScalarEvolutionExpander.h:208
PointerType
Definition: ItaniumDemangle.h:580
Signed
@ Signed
Definition: NVPTXISelLowering.cpp:4635
llvm::SCEVExpanderCleaner::cleanup
void cleanup()
Definition: ScalarEvolutionExpander.cpp:2645
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::isSafeToExpand
bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE, bool CanonicalMode=true)
Return true if the given expression is safe to expand in the sense that all materialized values are s...
Definition: ScalarEvolutionExpander.cpp:2617
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
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
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:1185
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:167
llvm::IRBuilder< InstSimplifyFolder, IRBuilderCallbackInserter >
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
llvm::SCEVExpander::getCurrentDebugLocation
DebugLoc getCurrentDebugLocation() const
Get location information used by debugging information.
Definition: ScalarEvolutionExpander.h:360
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
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
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1909
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::SCEVExpander::clearPostInc
void clearPostInc()
Disable all post-inc expansion.
Definition: ScalarEvolutionExpander.h:326
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:319
llvm::SCEVExpander::hoistIVInc
bool hoistIVInc(Instruction *IncV, Instruction *InsertPos)
Utility for hoisting an IV increment.
Definition: ScalarEvolutionExpander.cpp:1024
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::SCEVOperand
struct for holding enough information to help calculate the cost of the given SCEV when expanded into...
Definition: ScalarEvolutionExpander.h:46
llvm::SCEVPredicate
This class represents an assumption made using SCEV expressions which can be checked at run-time.
Definition: ScalarEvolution.h:215
llvm::SCEVOperand::OperandIdx
int OperandIdx
The use index of an expanded instruction.
Definition: ScalarEvolutionExpander.h:52
llvm::SCEVExpander::enableLSRMode
void enableLSRMode()
Definition: ScalarEvolutionExpander.h:339
llvm::SCEVExpanderCleaner::~SCEVExpanderCleaner
~SCEVExpanderCleaner()
Definition: ScalarEvolutionExpander.h:518
CommandLine.h
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::SCEVVisitor
This class defines a simple visitor class that may be used for various SCEV analysis purposes.
Definition: ScalarEvolutionExpressions.h:614
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:651
llvm::SCEVExpander::clearInsertPoint
void clearInsertPoint()
Clear the current insertion point.
Definition: ScalarEvolutionExpander.h:352
IP
Definition: NVPTXLowerArgs.cpp:167
DenseSet.h
false
Definition: StackSlotColoring.cpp:141
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction::CastOps
CastOps
Definition: Instruction.h:800
llvm::Instruction
Definition: Instruction.h:42
llvm::SCEVExpander::isInsertedInstruction
bool isInsertedInstruction(Instruction *I) const
Return true if the specified instruction was inserted by the code rewriter.
Definition: ScalarEvolutionExpander.h:367
llvm::SCEVExpander::setIVIncInsertPos
void setIVIncInsertPos(const Loop *L, Instruction *Pos)
Set the current IV increment loop and position.
Definition: ScalarEvolutionExpander.h:310
llvm::SCEVExpander::SetCurrentDebugLocation
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Definition: ScalarEvolutionExpander.h:355
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:2362
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:75
llvm::SCEVExpander::findInsertPointAfter
BasicBlock::iterator findInsertPointAfter(Instruction *I, Instruction *MustDominate) const
Returns a suitable insert point after I, that dominates MustDominate.
Definition: ScalarEvolutionExpander.cpp:98
expand
static Expected< BitVector > expand(StringRef S, StringRef Original)
Definition: GlobPattern.cpp:27
InstSimplifyFolder.h
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::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:2516
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::SCEVComparePredicate
This class represents an assumption that the expression LHS Pred RHS evaluates to true,...
Definition: ScalarEvolution.h:278
llvm::DenseMap
Definition: DenseMap.h:716
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::SCEVExpanderCleaner::SCEVExpanderCleaner
SCEVExpanderCleaner(SCEVExpander &Expander)
Definition: ScalarEvolutionExpander.h:515
llvm::SCEVExpander::disableCanonicalMode
void disableCanonicalMode()
Disable the behavior of expanding expressions in canonical form rather than in a more literal form.
Definition: ScalarEvolutionExpander.h:337
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:507
llvm::IRBuilderCallbackInserter
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
Definition: IRBuilder.h:75
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:95
this
Analysis the ScalarEvolution expression for r is this
Definition: README.txt:8
llvm::InstSimplifyFolder
InstSimplifyFolder - Use InstructionSimplify to fold operations to existing values.
Definition: InstSimplifyFolder.h:34
llvm::SCEVExpander::setInsertPoint
void setInsertPoint(Instruction *IP)
Set the current insertion point.
Definition: ScalarEvolutionExpander.h:345
llvm::IRBuilderBase
Common base class shared among various IRBuilders.
Definition: IRBuilder.h:93
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:130
llvm::SCEVExpander::getRelatedExistingExpansion
Value * getRelatedExistingExpansion(const SCEV *S, const Instruction *At, Loop *L)
Try to find the ValueOffsetPair for S.
Definition: ScalarEvolutionExpander.cpp:2052
name
static const char * name
Definition: SVEIntrinsicOpts.cpp:74
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:50
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:1911
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:338
llvm::SCEVUnionPredicate
This class represents a composition of other SCEV predicates, and is the class that most clients will...
Definition: ScalarEvolution.h:413
llvm::SCEVAddRecExpr
This node represents a polynomial recurrence on the trip count of the specified loop.
Definition: ScalarEvolutionExpressions.h:342
llvm::SCEVWrapPredicate
This class represents an assumption made on an AddRec expression.
Definition: ScalarEvolution.h:318
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::SCEVExpander::setChainedPhi
void setChainedPhi(PHINode *PN)
Definition: ScalarEvolutionExpander.h:371
llvm::SCEVOperand::ParentOpcode
unsigned ParentOpcode
LLVM instruction opcode that uses the operand.
Definition: ScalarEvolutionExpander.h:50
llvm::SCEVExpander::expandComparePredicate
Value * expandComparePredicate(const SCEVComparePredicate *Pred, Instruction *Loc)
A specialized variant of expandCodeForPredicate, handling the case when we are expanding code for a S...
Definition: ScalarEvolutionExpander.cpp:2349
ScalarEvolutionExpressions.h
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:786
llvm::IRBuilderBase::InsertPoint
InsertPoint - A saved insertion point.
Definition: IRBuilder.h:234
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:2623
SmallVector.h
llvm::SCEVExpander::expandCodeForPredicate
Value * expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc)
Generates a code sequence that evaluates this predicate.
Definition: ScalarEvolutionExpander.cpp:2333
llvm::AssertingVH
Value handle that asserts if the Value is deleted.
Definition: ValueHandle.h:260
TargetTransformInfo.h
llvm::PHINode
Definition: Instructions.h:2664
llvm::SCEVExpander::getIVIncOperand
Instruction * getIVIncOperand(Instruction *IncV, Instruction *InsertPos, bool allowScale)
Return the induction variable increment's IV operand.
Definition: ScalarEvolutionExpander.cpp:957
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
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:2491
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:262
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::SmallPtrSetImpl::contains
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:389
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:927
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37