LLVM  17.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 /// struct for holding enough information to help calculate the cost of the
32 /// given SCEV when expanded into IR.
33 struct SCEVOperand {
34  explicit SCEVOperand(unsigned Opc, int Idx, const SCEV *S) :
35  ParentOpcode(Opc), OperandIdx(Idx), S(S) { }
36  /// LLVM instruction opcode that uses the operand.
37  unsigned ParentOpcode;
38  /// The use index of an expanded instruction.
40  /// The SCEV operand to be costed.
41  const SCEV* S;
42 };
43 
44 /// This class uses information about analyze scalars to rewrite expressions
45 /// in canonical form.
46 ///
47 /// Clients should create an instance of this class when rewriting is needed,
48 /// and destroy it when finished to allow the release of the associated
49 /// memory.
50 class SCEVExpander : public SCEVVisitor<SCEVExpander, Value *> {
51  ScalarEvolution &SE;
52  const DataLayout &DL;
53 
54  // New instructions receive a name to identify them with the current pass.
55  const char *IVName;
56 
57  /// Indicates whether LCSSA phis should be created for inserted values.
58  bool PreserveLCSSA;
59 
60  // InsertedExpressions caches Values for reuse, so must track RAUW.
62  InsertedExpressions;
63 
64  // InsertedValues only flags inserted instructions so needs no RAUW.
65  DenseSet<AssertingVH<Value>> InsertedValues;
66  DenseSet<AssertingVH<Value>> InsertedPostIncValues;
67 
68  /// Keep track of the existing IR values re-used during expansion.
69  /// FIXME: Ideally re-used instructions would not be added to
70  /// InsertedValues/InsertedPostIncValues.
71  SmallPtrSet<Value *, 16> ReusedValues;
72 
73  // The induction variables generated.
74  SmallVector<WeakVH, 2> InsertedIVs;
75 
76  /// A memoization of the "relevant" loop for a given SCEV.
78 
79  /// Addrecs referring to any of the given loops are expanded in post-inc
80  /// mode. For example, expanding {1,+,1}<L> in post-inc mode returns the add
81  /// instruction that adds one to the phi for {0,+,1}<L>, as opposed to a new
82  /// phi starting at 1. This is only supported in non-canonical mode.
83  PostIncLoopSet PostIncLoops;
84 
85  /// When this is non-null, addrecs expanded in the loop it indicates should
86  /// be inserted with increments at IVIncInsertPos.
87  const Loop *IVIncInsertLoop;
88 
89  /// When expanding addrecs in the IVIncInsertLoop loop, insert the IV
90  /// increment at this position.
91  Instruction *IVIncInsertPos;
92 
93  /// Phis that complete an IV chain. Reuse
94  DenseSet<AssertingVH<PHINode>> ChainedPhis;
95 
96  /// When true, SCEVExpander tries to expand expressions in "canonical" form.
97  /// When false, expressions are expanded in a more literal form.
98  ///
99  /// In "canonical" form addrecs are expanded as arithmetic based on a
100  /// canonical induction variable. Note that CanonicalMode doesn't guarantee
101  /// that all expressions are expanded in "canonical" form. For some
102  /// expressions literal mode can be preferred.
103  bool CanonicalMode;
104 
105  /// When invoked from LSR, the expander is in "strength reduction" mode. The
106  /// only difference is that phi's are only reused if they are already in
107  /// "expanded" form.
108  bool LSRMode;
109 
111  BuilderType Builder;
112 
113  // RAII object that stores the current insertion point and restores it when
114  // the object is destroyed. This includes the debug location. Duplicated
115  // from InsertPointGuard to add SetInsertPoint() which is used to updated
116  // InsertPointGuards stack when insert points are moved during SCEV
117  // expansion.
118  class SCEVInsertPointGuard {
121  BasicBlock::iterator Point;
122  DebugLoc DbgLoc;
123  SCEVExpander *SE;
124 
125  SCEVInsertPointGuard(const SCEVInsertPointGuard &) = delete;
126  SCEVInsertPointGuard &operator=(const SCEVInsertPointGuard &) = delete;
127 
128  public:
129  SCEVInsertPointGuard(IRBuilderBase &B, SCEVExpander *SE)
130  : Builder(B), Block(B.GetInsertBlock()), Point(B.GetInsertPoint()),
131  DbgLoc(B.getCurrentDebugLocation()), SE(SE) {
132  SE->InsertPointGuards.push_back(this);
133  }
134 
135  ~SCEVInsertPointGuard() {
136  // These guards should always created/destroyed in FIFO order since they
137  // are used to guard lexically scoped blocks of code in
138  // ScalarEvolutionExpander.
139  assert(SE->InsertPointGuards.back() == this);
140  SE->InsertPointGuards.pop_back();
141  Builder.restoreIP(IRBuilderBase::InsertPoint(Block, Point));
142  Builder.SetCurrentDebugLocation(DbgLoc);
143  }
144 
145  BasicBlock::iterator GetInsertPoint() const { return Point; }
146  void SetInsertPoint(BasicBlock::iterator I) { Point = I; }
147  };
148 
149  /// Stack of pointers to saved insert points, used to keep insert points
150  /// consistent when instructions are moved.
151  SmallVector<SCEVInsertPointGuard *, 8> InsertPointGuards;
152 
153 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
154  const char *DebugType;
155 #endif
156 
157  friend struct SCEVVisitor<SCEVExpander, Value *>;
158 
159 public:
160  /// Construct a SCEVExpander in "canonical" mode.
162  const char *name, bool PreserveLCSSA = true)
163  : SE(se), DL(DL), IVName(name), PreserveLCSSA(PreserveLCSSA),
164  IVIncInsertLoop(nullptr), IVIncInsertPos(nullptr), CanonicalMode(true),
165  LSRMode(false),
166  Builder(se.getContext(), InstSimplifyFolder(DL),
168  [this](Instruction *I) { rememberInstruction(I); })) {
169 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
170  DebugType = "";
171 #endif
172  }
173 
175  // Make sure the insert point guard stack is consistent.
176  assert(InsertPointGuards.empty());
177  }
178 
179 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
180  void setDebugType(const char *s) { DebugType = s; }
181 #endif
182 
183  /// Erase the contents of the InsertedExpressions map so that users trying
184  /// to expand the same expression into multiple BasicBlocks or different
185  /// places within the same BasicBlock can do so.
186  void clear() {
187  InsertedExpressions.clear();
188  InsertedValues.clear();
189  InsertedPostIncValues.clear();
190  ReusedValues.clear();
191  ChainedPhis.clear();
192  InsertedIVs.clear();
193  }
194 
195  ScalarEvolution *getSE() { return &SE; }
196  const SmallVectorImpl<WeakVH> &getInsertedIVs() const { return InsertedIVs; }
197 
198  /// Return a vector containing all instructions inserted during expansion.
201  for (const auto &VH : InsertedValues) {
202  Value *V = VH;
203  if (ReusedValues.contains(V))
204  continue;
205  if (auto *Inst = dyn_cast<Instruction>(V))
206  Result.push_back(Inst);
207  }
208  for (const auto &VH : InsertedPostIncValues) {
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 
216  return Result;
217  }
218 
219  /// Return true for expressions that can't be evaluated at runtime
220  /// within given \b Budget.
221  ///
222  /// \p At is a parameter which specifies point in code where user is going to
223  /// expand these expressions. Sometimes this knowledge can lead to
224  /// a less pessimistic cost estimation.
226  unsigned Budget, const TargetTransformInfo *TTI,
227  const Instruction *At) {
228  assert(TTI && "This function requires TTI to be provided.");
229  assert(At && "This function requires At instruction to be provided.");
230  if (!TTI) // In assert-less builds, avoid crashing
231  return true; // by always claiming to be high-cost.
234  InstructionCost Cost = 0;
235  unsigned ScaledBudget = Budget * TargetTransformInfo::TCC_Basic;
236  for (auto *Expr : Exprs)
237  Worklist.emplace_back(-1, -1, Expr);
238  while (!Worklist.empty()) {
239  const SCEVOperand WorkItem = Worklist.pop_back_val();
240  if (isHighCostExpansionHelper(WorkItem, L, *At, Cost, ScaledBudget, *TTI,
241  Processed, Worklist))
242  return true;
243  }
244  assert(Cost <= ScaledBudget && "Should have returned from inner loop.");
245  return false;
246  }
247 
248  /// Return the induction variable increment's IV operand.
250  bool allowScale);
251 
252  /// Utility for hoisting \p IncV (with all subexpressions requried for its
253  /// computation) before \p InsertPos. If \p RecomputePoisonFlags is set, drops
254  /// all poison-generating flags from instructions being hoisted and tries to
255  /// re-infer them in the new location. It should be used when we are going to
256  /// introduce a new use in the new position that didn't exist before, and may
257  /// trigger new UB in case of poison.
258  bool hoistIVInc(Instruction *IncV, Instruction *InsertPos,
259  bool RecomputePoisonFlags = false);
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  /// Return true if the given expression is safe to expand in the sense that
268  /// all materialized values are safe to speculate anywhere their operands are
269  /// defined, and the expander is capable of expanding the expression.
270  bool isSafeToExpand(const SCEV *S) const;
271 
272  /// Return true if the given expression is safe to expand in the sense that
273  /// all materialized values are defined and safe to speculate at the specified
274  /// location and their operands are defined at this location.
275  bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint) const;
276 
277  /// Insert code to directly compute the specified SCEV expression into the
278  /// program. The code is inserted into the specified block.
279  Value *expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I) {
280  return expandCodeForImpl(SH, Ty, I);
281  }
282 
283  /// Insert code to directly compute the specified SCEV expression into the
284  /// program. The code is inserted into the SCEVExpander's current
285  /// insertion point. If a type is specified, the result will be expanded to
286  /// have that type, with a cast if necessary.
287  Value *expandCodeFor(const SCEV *SH, Type *Ty = nullptr) {
288  return expandCodeForImpl(SH, Ty);
289  }
290 
291  /// Generates a code sequence that evaluates this predicate. The inserted
292  /// instructions will be at position \p Loc. The result will be of type i1
293  /// and will have a value of 0 when the predicate is false and 1 otherwise.
295 
296  /// A specialized variant of expandCodeForPredicate, handling the case when
297  /// we are expanding code for a SCEVComparePredicate.
299  Instruction *Loc);
300 
301  /// Generates code that evaluates if the \p AR expression will overflow.
303  bool Signed);
304 
305  /// A specialized variant of expandCodeForPredicate, handling the case when
306  /// we are expanding code for a SCEVWrapPredicate.
308 
309  /// A specialized variant of expandCodeForPredicate, handling the case when
310  /// we are expanding code for a SCEVUnionPredicate.
312 
313  /// Set the current IV increment loop and position.
314  void setIVIncInsertPos(const Loop *L, Instruction *Pos) {
315  assert(!CanonicalMode &&
316  "IV increment positions are not supported in CanonicalMode");
317  IVIncInsertLoop = L;
318  IVIncInsertPos = Pos;
319  }
320 
321  /// Enable post-inc expansion for addrecs referring to the given
322  /// loops. Post-inc expansion is only supported in non-canonical mode.
323  void setPostInc(const PostIncLoopSet &L) {
324  assert(!CanonicalMode &&
325  "Post-inc expansion is not supported in CanonicalMode");
326  PostIncLoops = L;
327  }
328 
329  /// Disable all post-inc expansion.
330  void clearPostInc() {
331  PostIncLoops.clear();
332 
333  // When we change the post-inc loop set, cached expansions may no
334  // longer be valid.
335  InsertedPostIncValues.clear();
336  }
337 
338  /// Disable the behavior of expanding expressions in canonical form rather
339  /// than in a more literal form. Non-canonical mode is useful for late
340  /// optimization passes.
341  void disableCanonicalMode() { CanonicalMode = false; }
342 
343  void enableLSRMode() { LSRMode = true; }
344 
345  /// Set the current insertion point. This is useful if multiple calls to
346  /// expandCodeFor() are going to be made with the same insert point and the
347  /// insert point may be moved during one of the expansions (e.g. if the
348  /// insert point is not a block terminator).
350  assert(IP);
351  Builder.SetInsertPoint(IP);
352  }
353 
354  /// Clear the current insertion point. This is useful if the instruction
355  /// that had been serving as the insertion point may have been deleted.
356  void clearInsertPoint() { Builder.ClearInsertionPoint(); }
357 
358  /// Set location information used by debugging information.
360  Builder.SetCurrentDebugLocation(std::move(L));
361  }
362 
363  /// Get location information used by debugging information.
365  return Builder.getCurrentDebugLocation();
366  }
367 
368  /// Return true if the specified instruction was inserted by the code
369  /// rewriter. If so, the client should not modify the instruction. Note that
370  /// this also includes instructions re-used during expansion.
372  return InsertedValues.count(I) || InsertedPostIncValues.count(I);
373  }
374 
375  void setChainedPhi(PHINode *PN) { ChainedPhis.insert(PN); }
376 
377  /// Try to find the ValueOffsetPair for S. The function is mainly used to
378  /// check whether S can be expanded cheaply. If this returns a non-None
379  /// value, we know we can codegen the `ValueOffsetPair` into a suitable
380  /// expansion identical with S so that S can be expanded cheaply.
381  ///
382  /// L is a hint which tells in which loop to look for the suitable value.
383  /// On success return value which is equivalent to the expanded S at point
384  /// At. Return nullptr if value was not found.
385  ///
386  /// Note that this function does not perform an exhaustive search. I.e if it
387  /// didn't find any value it does not mean that there is no such value.
388  ///
390  Loop *L);
391 
392  /// Returns a suitable insert point after \p I, that dominates \p
393  /// MustDominate. Skips instructions inserted by the expander.
395  Instruction *MustDominate) const;
396 
397 private:
398  LLVMContext &getContext() const { return SE.getContext(); }
399 
400  /// Insert code to directly compute the specified SCEV expression into the
401  /// program. The code is inserted into the SCEVExpander's current
402  /// insertion point. If a type is specified, the result will be expanded to
403  /// have that type, with a cast if necessary. If \p Root is true, this
404  /// indicates that \p SH is the top-level expression to expand passed from
405  /// an external client call.
406  Value *expandCodeForImpl(const SCEV *SH, Type *Ty);
407 
408  /// Insert code to directly compute the specified SCEV expression into the
409  /// program. The code is inserted into the specified block. If \p
410  /// Root is true, this indicates that \p SH is the top-level expression to
411  /// expand passed from an external client call.
412  Value *expandCodeForImpl(const SCEV *SH, Type *Ty, Instruction *I);
413 
414  /// Recursive helper function for isHighCostExpansion.
415  bool isHighCostExpansionHelper(const SCEVOperand &WorkItem, Loop *L,
416  const Instruction &At, InstructionCost &Cost,
417  unsigned Budget,
418  const TargetTransformInfo &TTI,
419  SmallPtrSetImpl<const SCEV *> &Processed,
420  SmallVectorImpl<SCEVOperand> &Worklist);
421 
422  /// Insert the specified binary operator, doing a small amount of work to
423  /// avoid inserting an obviously redundant operation, and hoisting to an
424  /// outer loop when the opportunity is there and it is safe.
425  Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
426  SCEV::NoWrapFlags Flags, bool IsSafeToHoist);
427 
428  /// We want to cast \p V. What would be the best place for such a cast?
429  BasicBlock::iterator GetOptimalInsertionPointForCastOf(Value *V) const;
430 
431  /// Arrange for there to be a cast of V to Ty at IP, reusing an existing
432  /// cast if a suitable one exists, moving an existing cast if a suitable one
433  /// exists but isn't in the right place, or creating a new one.
434  Value *ReuseOrCreateCast(Value *V, Type *Ty, Instruction::CastOps Op,
436 
437  /// Insert a cast of V to the specified type, which must be possible with a
438  /// noop cast, doing what we can to share the casts.
439  Value *InsertNoopCastOfTo(Value *V, Type *Ty);
440 
441  /// Expand a SCEVAddExpr with a pointer type into a GEP instead of using
442  /// ptrtoint+arithmetic+inttoptr.
443  Value *expandAddToGEP(const SCEV *const *op_begin, const SCEV *const *op_end,
444  PointerType *PTy, Type *Ty, Value *V);
445  Value *expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty, Value *V);
446 
447  /// Find a previous Value in ExprValueMap for expand.
448  Value *FindValueInExprValueMap(const SCEV *S, const Instruction *InsertPt);
449 
450  Value *expand(const SCEV *S);
451 
452  /// Determine the most "relevant" loop for the given SCEV.
453  const Loop *getRelevantLoop(const SCEV *);
454 
455  Value *expandMinMaxExpr(const SCEVNAryExpr *S, Intrinsic::ID IntrinID,
456  Twine Name, bool IsSequential = false);
457 
458  Value *visitConstant(const SCEVConstant *S) { return S->getValue(); }
459 
460  Value *visitPtrToIntExpr(const SCEVPtrToIntExpr *S);
461 
462  Value *visitTruncateExpr(const SCEVTruncateExpr *S);
463 
464  Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);
465 
466  Value *visitSignExtendExpr(const SCEVSignExtendExpr *S);
467 
468  Value *visitAddExpr(const SCEVAddExpr *S);
469 
470  Value *visitMulExpr(const SCEVMulExpr *S);
471 
472  Value *visitUDivExpr(const SCEVUDivExpr *S);
473 
474  Value *visitAddRecExpr(const SCEVAddRecExpr *S);
475 
476  Value *visitSMaxExpr(const SCEVSMaxExpr *S);
477 
478  Value *visitUMaxExpr(const SCEVUMaxExpr *S);
479 
480  Value *visitSMinExpr(const SCEVSMinExpr *S);
481 
482  Value *visitUMinExpr(const SCEVUMinExpr *S);
483 
484  Value *visitSequentialUMinExpr(const SCEVSequentialUMinExpr *S);
485 
486  Value *visitUnknown(const SCEVUnknown *S) { return S->getValue(); }
487 
488  void rememberInstruction(Value *I);
489 
490  bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
491 
492  bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
493 
494  Value *expandAddRecExprLiterally(const SCEVAddRecExpr *);
495  PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
496  const Loop *L, Type *ExpandTy, Type *IntTy,
497  Type *&TruncTy, bool &InvertStep);
498  Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L, Type *ExpandTy,
499  Type *IntTy, bool useSubtract);
500 
501  void fixupInsertPoints(Instruction *I);
502 
503  /// Create LCSSA PHIs for \p V, if it is required for uses at the Builder's
504  /// current insertion point.
505  Value *fixupLCSSAFormFor(Value *V);
506 };
507 
508 /// Helper to remove instructions inserted during SCEV expansion, unless they
509 /// are marked as used.
511  SCEVExpander &Expander;
512 
513  /// Indicates whether the result of the expansion is used. If false, the
514  /// instructions added during expansion are removed.
515  bool ResultUsed;
516 
517 public:
519  : Expander(Expander), ResultUsed(false) {}
520 
522 
523  /// Indicate that the result of the expansion is used.
524  void markResultUsed() { ResultUsed = true; }
525 
526  void cleanup();
527 };
528 } // namespace llvm
529 
530 #endif
llvm::SCEVExpander::getInsertedIVs
const SmallVectorImpl< WeakVH > & getInsertedIVs() const
Definition: ScalarEvolutionExpander.h:196
llvm::SCEVExpander::~SCEVExpander
~SCEVExpander()
Definition: ScalarEvolutionExpander.h:174
llvm::InstructionCost
Definition: InstructionCost.h:29
llvm::ScalarEvolution::getContext
LLVMContext & getContext() const
Definition: ScalarEvolution.h:494
llvm::SCEVExpander::getSE
ScalarEvolution * getSE()
Definition: ScalarEvolutionExpander.h:195
PointerType
Definition: ItaniumDemangle.h:588
Signed
@ Signed
Definition: NVPTXISelLowering.cpp:4884
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:114
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:34
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
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:50
name
static const char * name
Definition: SMEABIPass.cpp:49
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:172
llvm::IRBuilder< InstSimplifyFolder, IRBuilderCallbackInserter >
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:452
llvm::SCEVExpander::getCurrentDebugLocation
DebugLoc getCurrentDebugLocation() const
Get location information used by debugging information.
Definition: ScalarEvolutionExpander.h:364
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:279
llvm::SCEVExpander::isHighCostExpansion
bool isHighCostExpansion(ArrayRef< const SCEV * > Exprs, 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:225
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:524
llvm::SCEVExpander::clearPostInc
void clearPostInc()
Disable all post-inc expansion.
Definition: ScalarEvolutionExpander.h:330
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:323
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:33
llvm::SCEVExpander::isSafeToExpandAt
bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint) const
Return true if the given expression is safe to expand in the sense that all materialized values are d...
Definition: ScalarEvolutionExpander.cpp:2627
llvm::SCEVExpanderCleaner::cleanup
void cleanup()
Definition: ScalarEvolutionExpander.cpp:2649
llvm::SCEVPredicate
This class represents an assumption made using SCEV expressions which can be checked at run-time.
Definition: ScalarEvolution.h:218
llvm::SCEVOperand::OperandIdx
int OperandIdx
The use index of an expanded instruction.
Definition: ScalarEvolutionExpander.h:39
llvm::SCEVExpander::enableLSRMode
void enableLSRMode()
Definition: ScalarEvolutionExpander.h:343
llvm::SCEVExpanderCleaner::~SCEVExpanderCleaner
~SCEVExpanderCleaner()
Definition: ScalarEvolutionExpander.h:521
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:602
llvm::COFF::DebugType
DebugType
Definition: COFF.h:652
InlinePriorityMode::Cost
@ Cost
llvm::SCEVExpander::clearInsertPoint
void clearInsertPoint()
Clear the current insertion point.
Definition: ScalarEvolutionExpander.h:356
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:823
llvm::Instruction
Definition: Instruction.h:41
llvm::SCEVExpander::isInsertedInstruction
bool isInsertedInstruction(Instruction *I) const
Return true if the specified instruction was inserted by the code rewriter.
Definition: ScalarEvolutionExpander.h:371
llvm::SCEVExpander::setIVIncInsertPos
void setIVIncInsertPos(const Loop *L, Instruction *Pos)
Set the current IV increment loop and position.
Definition: ScalarEvolutionExpander.h:314
llvm::SCEVExpander::SetCurrentDebugLocation
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Definition: ScalarEvolutionExpander.h:359
llvm::SCEVOperand::S
const SCEV * S
The SCEV operand to be costed.
Definition: ScalarEvolutionExpander.h:41
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:2355
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:99
expand
static Expected< BitVector > expand(StringRef S, StringRef Original)
Definition: GlobPattern.cpp:26
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:287
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:2509
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:67
llvm::SCEVComparePredicate
This class represents an assumption that the expression LHS Pred RHS evaluates to true,...
Definition: ScalarEvolution.h:281
llvm::DenseMap
Definition: DenseMap.h:714
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1804
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::SCEVExpanderCleaner::SCEVExpanderCleaner
SCEVExpanderCleaner(SCEVExpander &Expander)
Definition: ScalarEvolutionExpander.h:518
llvm::SCEVExpander::disableCanonicalMode
void disableCanonicalMode()
Disable the behavior of expanding expressions in canonical form rather than in a more literal form.
Definition: ScalarEvolutionExpander.h:341
llvm::SCEVCheapExpansionBudget
cl::opt< unsigned > SCEVCheapExpansionBudget
TemplateParamKind::Type
@ Type
llvm::TrackingVH< Value >
llvm::SCEVExpander::isSafeToExpand
bool isSafeToExpand(const SCEV *S) const
Return true if the given expression is safe to expand in the sense that all materialized values are s...
Definition: ScalarEvolutionExpander.cpp:2621
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::TTI
TargetTransformInfo TTI
Definition: TargetTransformInfo.h:167
llvm::SCEVExpanderCleaner
Helper to remove instructions inserted during SCEV expansion, unless they are marked as used.
Definition: ScalarEvolutionExpander.h:510
llvm::IRBuilderCallbackInserter
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
Definition: IRBuilder.h:76
llvm::SCEVExpander::clear
void clear()
Erase the contents of the InsertedExpressions map so that users trying to expand the same expression ...
Definition: ScalarEvolutionExpander.h:186
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:199
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:95
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:33
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:349
llvm::SCEVExpander::hoistIVInc
bool hoistIVInc(Instruction *IncV, Instruction *InsertPos, bool RecomputePoisonFlags=false)
Utility for hoisting IncV (with all subexpressions requried for its computation) before InsertPos.
Definition: ScalarEvolutionExpander.cpp:1034
llvm::IRBuilderBase
Common base class shared among various IRBuilders.
Definition: IRBuilder.h:94
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:2045
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:1901
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:354
llvm::SCEVUnionPredicate
This class represents a composition of other SCEV predicates, and is the class that most clients will...
Definition: ScalarEvolution.h:416
llvm::SCEVAddRecExpr
This node represents a polynomial recurrence on the trip count of the specified loop.
Definition: ScalarEvolutionExpressions.h:330
llvm::SCEVWrapPredicate
This class represents an assumption made on an AddRec expression.
Definition: ScalarEvolution.h:321
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::SCEVExpander::setChainedPhi
void setChainedPhi(PHINode *PN)
Definition: ScalarEvolutionExpander.h:375
llvm::SCEVOperand::ParentOpcode
unsigned ParentOpcode
LLVM instruction opcode that uses the operand.
Definition: ScalarEvolutionExpander.h:37
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:2342
ScalarEvolutionExpressions.h
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:809
llvm::IRBuilderBase::InsertPoint
InsertPoint - A saved insertion point.
Definition: IRBuilder.h:243
SmallVector.h
llvm::SCEVExpander::expandCodeForPredicate
Value * expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc)
Generates a code sequence that evaluates this predicate.
Definition: ScalarEvolutionExpander.cpp:2326
llvm::AssertingVH
Value handle that asserts if the Value is deleted.
Definition: ValueHandle.h:260
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
TargetTransformInfo.h
llvm::PHINode
Definition: Instructions.h:2708
llvm::SCEVExpander::getIVIncOperand
Instruction * getIVIncOperand(Instruction *IncV, Instruction *InsertPos, bool allowScale)
Return the induction variable increment's IV operand.
Definition: ScalarEvolutionExpander.cpp:967
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:2484
llvm::SCEVExpander::SCEVExpander
SCEVExpander(ScalarEvolution &se, const DataLayout &DL, const char *name, bool PreserveLCSSA=true)
Construct a SCEVExpander in "canonical" mode.
Definition: ScalarEvolutionExpander.h:161
llvm::TargetTransformInfo::TCC_Basic
@ TCC_Basic
The cost of a typical 'add' instruction.
Definition: TargetTransformInfo.h:244
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:941
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:39