LLVM  16.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  /// At is a parameter which specifies point in code where user is going to
223  /// expand this expression. Sometimes this knowledge can lead to
224  /// a less pessimistic cost estimation.
225  bool isHighCostExpansion(const SCEV *Expr, Loop *L, unsigned Budget,
226  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  Worklist.emplace_back(-1, -1, Expr);
237  while (!Worklist.empty()) {
238  const SCEVOperand WorkItem = Worklist.pop_back_val();
239  if (isHighCostExpansionHelper(WorkItem, L, *At, Cost, ScaledBudget, *TTI,
240  Processed, Worklist))
241  return true;
242  }
243  assert(Cost <= ScaledBudget && "Should have returned from inner loop.");
244  return false;
245  }
246 
247  /// Return the induction variable increment's IV operand.
249  bool allowScale);
250 
251  /// Utility for hoisting \p IncV (with all subexpressions requried for its
252  /// computation) before \p InsertPos. If \p RecomputePoisonFlags is set, drops
253  /// all poison-generating flags from instructions being hoisted and tries to
254  /// re-infer them in the new location. It should be used when we are going to
255  /// introduce a new use in the new position that didn't exist before, and may
256  /// trigger new UB in case of poison.
257  bool hoistIVInc(Instruction *IncV, Instruction *InsertPos,
258  bool RecomputePoisonFlags = false);
259 
260  /// replace congruent phis with their most canonical representative. Return
261  /// the number of phis eliminated.
262  unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT,
264  const TargetTransformInfo *TTI = nullptr);
265 
266  /// Return true if the given expression is safe to expand in the sense that
267  /// all materialized values are safe to speculate anywhere their operands are
268  /// defined, and the expander is capable of expanding the expression.
269  bool isSafeToExpand(const SCEV *S) const;
270 
271  /// Return true if the given expression is safe to expand in the sense that
272  /// all materialized values are defined and safe to speculate at the specified
273  /// location and their operands are defined at this location.
274  bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint) const;
275 
276  /// Insert code to directly compute the specified SCEV expression into the
277  /// program. The code is inserted into the specified block.
278  Value *expandCodeFor(const SCEV *SH, Type *Ty, Instruction *I) {
279  return expandCodeForImpl(SH, Ty, I);
280  }
281 
282  /// Insert code to directly compute the specified SCEV expression into the
283  /// program. The code is inserted into the SCEVExpander's current
284  /// insertion point. If a type is specified, the result will be expanded to
285  /// have that type, with a cast if necessary.
286  Value *expandCodeFor(const SCEV *SH, Type *Ty = nullptr) {
287  return expandCodeForImpl(SH, Ty);
288  }
289 
290  /// Generates a code sequence that evaluates this predicate. The inserted
291  /// instructions will be at position \p Loc. The result will be of type i1
292  /// and will have a value of 0 when the predicate is false and 1 otherwise.
294 
295  /// A specialized variant of expandCodeForPredicate, handling the case when
296  /// we are expanding code for a SCEVComparePredicate.
298  Instruction *Loc);
299 
300  /// Generates code that evaluates if the \p AR expression will overflow.
302  bool Signed);
303 
304  /// A specialized variant of expandCodeForPredicate, handling the case when
305  /// we are expanding code for a SCEVWrapPredicate.
307 
308  /// A specialized variant of expandCodeForPredicate, handling the case when
309  /// we are expanding code for a SCEVUnionPredicate.
311 
312  /// Set the current IV increment loop and position.
313  void setIVIncInsertPos(const Loop *L, Instruction *Pos) {
314  assert(!CanonicalMode &&
315  "IV increment positions are not supported in CanonicalMode");
316  IVIncInsertLoop = L;
317  IVIncInsertPos = Pos;
318  }
319 
320  /// Enable post-inc expansion for addrecs referring to the given
321  /// loops. Post-inc expansion is only supported in non-canonical mode.
322  void setPostInc(const PostIncLoopSet &L) {
323  assert(!CanonicalMode &&
324  "Post-inc expansion is not supported in CanonicalMode");
325  PostIncLoops = L;
326  }
327 
328  /// Disable all post-inc expansion.
329  void clearPostInc() {
330  PostIncLoops.clear();
331 
332  // When we change the post-inc loop set, cached expansions may no
333  // longer be valid.
334  InsertedPostIncValues.clear();
335  }
336 
337  /// Disable the behavior of expanding expressions in canonical form rather
338  /// than in a more literal form. Non-canonical mode is useful for late
339  /// optimization passes.
340  void disableCanonicalMode() { CanonicalMode = false; }
341 
342  void enableLSRMode() { LSRMode = true; }
343 
344  /// Set the current insertion point. This is useful if multiple calls to
345  /// expandCodeFor() are going to be made with the same insert point and the
346  /// insert point may be moved during one of the expansions (e.g. if the
347  /// insert point is not a block terminator).
349  assert(IP);
350  Builder.SetInsertPoint(IP);
351  }
352 
353  /// Clear the current insertion point. This is useful if the instruction
354  /// that had been serving as the insertion point may have been deleted.
355  void clearInsertPoint() { Builder.ClearInsertionPoint(); }
356 
357  /// Set location information used by debugging information.
359  Builder.SetCurrentDebugLocation(std::move(L));
360  }
361 
362  /// Get location information used by debugging information.
364  return Builder.getCurrentDebugLocation();
365  }
366 
367  /// Return true if the specified instruction was inserted by the code
368  /// rewriter. If so, the client should not modify the instruction. Note that
369  /// this also includes instructions re-used during expansion.
371  return InsertedValues.count(I) || InsertedPostIncValues.count(I);
372  }
373 
374  void setChainedPhi(PHINode *PN) { ChainedPhis.insert(PN); }
375 
376  /// Try to find the ValueOffsetPair for S. The function is mainly used to
377  /// check whether S can be expanded cheaply. If this returns a non-None
378  /// value, we know we can codegen the `ValueOffsetPair` into a suitable
379  /// expansion identical with S so that S can be expanded cheaply.
380  ///
381  /// L is a hint which tells in which loop to look for the suitable value.
382  /// On success return value which is equivalent to the expanded S at point
383  /// At. Return nullptr if value was not found.
384  ///
385  /// Note that this function does not perform an exhaustive search. I.e if it
386  /// didn't find any value it does not mean that there is no such value.
387  ///
389  Loop *L);
390 
391  /// Returns a suitable insert point after \p I, that dominates \p
392  /// MustDominate. Skips instructions inserted by the expander.
394  Instruction *MustDominate) const;
395 
396 private:
397  LLVMContext &getContext() const { return SE.getContext(); }
398 
399  /// Insert code to directly compute the specified SCEV expression into the
400  /// program. The code is inserted into the SCEVExpander's current
401  /// insertion point. If a type is specified, the result will be expanded to
402  /// have that type, with a cast if necessary. If \p Root is true, this
403  /// indicates that \p SH is the top-level expression to expand passed from
404  /// an external client call.
405  Value *expandCodeForImpl(const SCEV *SH, Type *Ty);
406 
407  /// Insert code to directly compute the specified SCEV expression into the
408  /// program. The code is inserted into the specified block. If \p
409  /// Root is true, this indicates that \p SH is the top-level expression to
410  /// expand passed from an external client call.
411  Value *expandCodeForImpl(const SCEV *SH, Type *Ty, Instruction *I);
412 
413  /// Recursive helper function for isHighCostExpansion.
414  bool isHighCostExpansionHelper(const SCEVOperand &WorkItem, Loop *L,
415  const Instruction &At, InstructionCost &Cost,
416  unsigned Budget,
417  const TargetTransformInfo &TTI,
418  SmallPtrSetImpl<const SCEV *> &Processed,
419  SmallVectorImpl<SCEVOperand> &Worklist);
420 
421  /// Insert the specified binary operator, doing a small amount of work to
422  /// avoid inserting an obviously redundant operation, and hoisting to an
423  /// outer loop when the opportunity is there and it is safe.
424  Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS,
425  SCEV::NoWrapFlags Flags, bool IsSafeToHoist);
426 
427  /// We want to cast \p V. What would be the best place for such a cast?
428  BasicBlock::iterator GetOptimalInsertionPointForCastOf(Value *V) const;
429 
430  /// Arrange for there to be a cast of V to Ty at IP, reusing an existing
431  /// cast if a suitable one exists, moving an existing cast if a suitable one
432  /// exists but isn't in the right place, or creating a new one.
433  Value *ReuseOrCreateCast(Value *V, Type *Ty, Instruction::CastOps Op,
435 
436  /// Insert a cast of V to the specified type, which must be possible with a
437  /// noop cast, doing what we can to share the casts.
438  Value *InsertNoopCastOfTo(Value *V, Type *Ty);
439 
440  /// Expand a SCEVAddExpr with a pointer type into a GEP instead of using
441  /// ptrtoint+arithmetic+inttoptr.
442  Value *expandAddToGEP(const SCEV *const *op_begin, const SCEV *const *op_end,
443  PointerType *PTy, Type *Ty, Value *V);
444  Value *expandAddToGEP(const SCEV *Op, PointerType *PTy, Type *Ty, Value *V);
445 
446  /// Find a previous Value in ExprValueMap for expand.
447  Value *FindValueInExprValueMap(const SCEV *S, const Instruction *InsertPt);
448 
449  Value *expand(const SCEV *S);
450 
451  /// Determine the most "relevant" loop for the given SCEV.
452  const Loop *getRelevantLoop(const SCEV *);
453 
454  Value *expandMinMaxExpr(const SCEVNAryExpr *S, Intrinsic::ID IntrinID,
455  Twine Name, bool IsSequential = false);
456 
457  Value *visitConstant(const SCEVConstant *S) { return S->getValue(); }
458 
459  Value *visitPtrToIntExpr(const SCEVPtrToIntExpr *S);
460 
461  Value *visitTruncateExpr(const SCEVTruncateExpr *S);
462 
463  Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);
464 
465  Value *visitSignExtendExpr(const SCEVSignExtendExpr *S);
466 
467  Value *visitAddExpr(const SCEVAddExpr *S);
468 
469  Value *visitMulExpr(const SCEVMulExpr *S);
470 
471  Value *visitUDivExpr(const SCEVUDivExpr *S);
472 
473  Value *visitAddRecExpr(const SCEVAddRecExpr *S);
474 
475  Value *visitSMaxExpr(const SCEVSMaxExpr *S);
476 
477  Value *visitUMaxExpr(const SCEVUMaxExpr *S);
478 
479  Value *visitSMinExpr(const SCEVSMinExpr *S);
480 
481  Value *visitUMinExpr(const SCEVUMinExpr *S);
482 
483  Value *visitSequentialUMinExpr(const SCEVSequentialUMinExpr *S);
484 
485  Value *visitUnknown(const SCEVUnknown *S) { return S->getValue(); }
486 
487  void rememberInstruction(Value *I);
488 
489  bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
490 
491  bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L);
492 
493  Value *expandAddRecExprLiterally(const SCEVAddRecExpr *);
494  PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
495  const Loop *L, Type *ExpandTy, Type *IntTy,
496  Type *&TruncTy, bool &InvertStep);
497  Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L, Type *ExpandTy,
498  Type *IntTy, bool useSubtract);
499 
500  void fixupInsertPoints(Instruction *I);
501 
502  /// If required, create LCSSA PHIs for \p Users' operand \p OpIdx. If new
503  /// LCSSA PHIs have been created, return the LCSSA PHI available at \p User.
504  /// If no PHIs have been created, return the unchanged operand \p OpIdx.
505  Value *fixupLCSSAFormFor(Instruction *User, unsigned OpIdx);
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:491
llvm::SCEVExpander::getSE
ScalarEvolution * getSE()
Definition: ScalarEvolutionExpander.h:195
PointerType
Definition: ItaniumDemangle.h:587
Signed
@ Signed
Definition: NVPTXISelLowering.cpp:4709
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:113
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:546
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
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1181
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:449
llvm::SCEVExpander::getCurrentDebugLocation
DebugLoc getCurrentDebugLocation() const
Get location information used by debugging information.
Definition: ScalarEvolutionExpander.h:363
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:278
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1835
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:329
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:322
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:2637
llvm::SCEVExpanderCleaner::cleanup
void cleanup()
Definition: ScalarEvolutionExpander.cpp:2659
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:39
llvm::SCEVExpander::enableLSRMode
void enableLSRMode()
Definition: ScalarEvolutionExpander.h:342
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: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:225
llvm::COFF::DebugType
DebugType
Definition: COFF.h:652
InlinePriorityMode::Cost
@ Cost
llvm::SCEVExpander::clearInsertPoint
void clearInsertPoint()
Clear the current insertion point.
Definition: ScalarEvolutionExpander.h:355
IP
Definition: NVPTXLowerArgs.cpp:168
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:787
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:370
llvm::SCEVExpander::setIVIncInsertPos
void setIVIncInsertPos(const Loop *L, Instruction *Pos)
Set the current IV increment loop and position.
Definition: ScalarEvolutionExpander.h:313
llvm::SCEVExpander::SetCurrentDebugLocation
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Definition: ScalarEvolutionExpander.h:358
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:2380
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:286
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:2534
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:278
llvm::DenseMap
Definition: DenseMap.h:714
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:340
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:2631
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: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: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
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:348
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:1027
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:2070
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:1927
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
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:374
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:2367
ScalarEvolutionExpressions.h
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:773
llvm::IRBuilderBase::InsertPoint
InsertPoint - A saved insertion point.
Definition: IRBuilder.h:242
SmallVector.h
llvm::SCEVExpander::expandCodeForPredicate
Value * expandCodeForPredicate(const SCEVPredicate *Pred, Instruction *Loc)
Generates a code sequence that evaluates this predicate.
Definition: ScalarEvolutionExpander.cpp:2351
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:659
TargetTransformInfo.h
llvm::PHINode
Definition: Instructions.h:2699
llvm::SCEVExpander::getIVIncOperand
Instruction * getIVIncOperand(Instruction *IncV, Instruction *InsertPos, bool allowScale)
Return the induction variable increment's IV operand.
Definition: ScalarEvolutionExpander.cpp:960
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:2509
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:923
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38