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