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