LLVM  16.0.0git
ScalarEvolution.h
Go to the documentation of this file.
1 //===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- 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 // The ScalarEvolution class is an LLVM pass which can be used to analyze and
10 // categorize scalar expressions in loops. It specializes in recognizing
11 // general induction variables, representing them with the abstract and opaque
12 // SCEV class. Given this analysis, trip counts of loops and other important
13 // properties can be obtained.
14 //
15 // This analysis is primarily useful for induction variable substitution and
16 // strength reduction.
17 //
18 //===----------------------------------------------------------------------===//
19 
20 #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
21 #define LLVM_ANALYSIS_SCALAREVOLUTION_H
22 
23 #include "llvm/ADT/APInt.h"
24 #include "llvm/ADT/ArrayRef.h"
25 #include "llvm/ADT/DenseMap.h"
26 #include "llvm/ADT/DenseMapInfo.h"
27 #include "llvm/ADT/FoldingSet.h"
28 #include "llvm/ADT/Optional.h"
30 #include "llvm/ADT/SetVector.h"
31 #include "llvm/ADT/SmallPtrSet.h"
32 #include "llvm/ADT/SmallVector.h"
33 #include "llvm/IR/ConstantRange.h"
34 #include "llvm/IR/InstrTypes.h"
35 #include "llvm/IR/Instructions.h"
36 #include "llvm/IR/PassManager.h"
37 #include "llvm/IR/ValueHandle.h"
38 #include "llvm/IR/ValueMap.h"
39 #include "llvm/Pass.h"
40 #include <cassert>
41 #include <cstdint>
42 #include <memory>
43 #include <utility>
44 
45 namespace llvm {
46 
47 class OverflowingBinaryOperator;
48 class AssumptionCache;
49 class BasicBlock;
50 class Constant;
51 class ConstantInt;
52 class DataLayout;
53 class DominatorTree;
54 class Function;
55 class GEPOperator;
56 class Instruction;
57 class LLVMContext;
58 class Loop;
59 class LoopInfo;
60 class raw_ostream;
61 class ScalarEvolution;
62 class SCEVAddRecExpr;
63 class SCEVUnknown;
64 class StructType;
65 class TargetLibraryInfo;
66 class Type;
67 class Value;
68 enum SCEVTypes : unsigned short;
69 
70 extern bool VerifySCEV;
71 
72 /// This class represents an analyzed expression in the program. These are
73 /// opaque objects that the client is not allowed to do much with directly.
74 ///
75 class SCEV : public FoldingSetNode {
76  friend struct FoldingSetTrait<SCEV>;
77 
78  /// A reference to an Interned FoldingSetNodeID for this node. The
79  /// ScalarEvolution's BumpPtrAllocator holds the data.
80  FoldingSetNodeIDRef FastID;
81 
82  // The SCEV baseclass this node corresponds to
83  const SCEVTypes SCEVType;
84 
85 protected:
86  // Estimated complexity of this node's expression tree size.
87  const unsigned short ExpressionSize;
88 
89  /// This field is initialized to zero and may be used in subclasses to store
90  /// miscellaneous information.
91  unsigned short SubclassData = 0;
92 
93 public:
94  /// NoWrapFlags are bitfield indices into SubclassData.
95  ///
96  /// Add and Mul expressions may have no-unsigned-wrap <NUW> or
97  /// no-signed-wrap <NSW> properties, which are derived from the IR
98  /// operator. NSW is a misnomer that we use to mean no signed overflow or
99  /// underflow.
100  ///
101  /// AddRec expressions may have a no-self-wraparound <NW> property if, in
102  /// the integer domain, abs(step) * max-iteration(loop) <=
103  /// unsigned-max(bitwidth). This means that the recurrence will never reach
104  /// its start value if the step is non-zero. Computing the same value on
105  /// each iteration is not considered wrapping, and recurrences with step = 0
106  /// are trivially <NW>. <NW> is independent of the sign of step and the
107  /// value the add recurrence starts with.
108  ///
109  /// Note that NUW and NSW are also valid properties of a recurrence, and
110  /// either implies NW. For convenience, NW will be set for a recurrence
111  /// whenever either NUW or NSW are set.
112  ///
113  /// We require that the flag on a SCEV apply to the entire scope in which
114  /// that SCEV is defined. A SCEV's scope is set of locations dominated by
115  /// a defining location, which is in turn described by the following rules:
116  /// * A SCEVUnknown is at the point of definition of the Value.
117  /// * A SCEVConstant is defined at all points.
118  /// * A SCEVAddRec is defined starting with the header of the associated
119  /// loop.
120  /// * All other SCEVs are defined at the earlest point all operands are
121  /// defined.
122  ///
123  /// The above rules describe a maximally hoisted form (without regards to
124  /// potential control dependence). A SCEV is defined anywhere a
125  /// corresponding instruction could be defined in said maximally hoisted
126  /// form. Note that SCEVUDivExpr (currently the only expression type which
127  /// can trap) can be defined per these rules in regions where it would trap
128  /// at runtime. A SCEV being defined does not require the existence of any
129  /// instruction within the defined scope.
130  enum NoWrapFlags {
131  FlagAnyWrap = 0, // No guarantee.
132  FlagNW = (1 << 0), // No self-wrap.
133  FlagNUW = (1 << 1), // No unsigned wrap.
134  FlagNSW = (1 << 2), // No signed wrap.
135  NoWrapMask = (1 << 3) - 1
136  };
137 
138  explicit SCEV(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy,
139  unsigned short ExpressionSize)
140  : FastID(ID), SCEVType(SCEVTy), ExpressionSize(ExpressionSize) {}
141  SCEV(const SCEV &) = delete;
142  SCEV &operator=(const SCEV &) = delete;
143 
144  SCEVTypes getSCEVType() const { return SCEVType; }
145 
146  /// Return the LLVM type of this SCEV expression.
147  Type *getType() const;
148 
149  /// Return true if the expression is a constant zero.
150  bool isZero() const;
151 
152  /// Return true if the expression is a constant one.
153  bool isOne() const;
154 
155  /// Return true if the expression is a constant all-ones value.
156  bool isAllOnesValue() const;
157 
158  /// Return true if the specified scev is negated, but not a constant.
159  bool isNonConstantNegative() const;
160 
161  // Returns estimated size of the mathematical expression represented by this
162  // SCEV. The rules of its calculation are following:
163  // 1) Size of a SCEV without operands (like constants and SCEVUnknown) is 1;
164  // 2) Size SCEV with operands Op1, Op2, ..., OpN is calculated by formula:
165  // (1 + Size(Op1) + ... + Size(OpN)).
166  // This value gives us an estimation of time we need to traverse through this
167  // SCEV and all its operands recursively. We may use it to avoid performing
168  // heavy transformations on SCEVs of excessive size for sake of saving the
169  // compilation time.
170  unsigned short getExpressionSize() const {
171  return ExpressionSize;
172  }
173 
174  /// Print out the internal representation of this scalar to the specified
175  /// stream. This should really only be used for debugging purposes.
176  void print(raw_ostream &OS) const;
177 
178  /// This method is used for debugging.
179  void dump() const;
180 };
181 
182 // Specialize FoldingSetTrait for SCEV to avoid needing to compute
183 // temporary FoldingSetNodeID values.
184 template <> struct FoldingSetTrait<SCEV> : DefaultFoldingSetTrait<SCEV> {
185  static void Profile(const SCEV &X, FoldingSetNodeID &ID) { ID = X.FastID; }
186 
187  static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, unsigned IDHash,
188  FoldingSetNodeID &TempID) {
189  return ID == X.FastID;
190  }
191 
192  static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) {
193  return X.FastID.ComputeHash();
194  }
195 };
196 
197 inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) {
198  S.print(OS);
199  return OS;
200 }
201 
202 /// An object of this class is returned by queries that could not be answered.
203 /// For example, if you ask for the number of iterations of a linked-list
204 /// traversal loop, you will get one of these. None of the standard SCEV
205 /// operations are valid on this class, it is just a marker.
206 struct SCEVCouldNotCompute : public SCEV {
208 
209  /// Methods for support type inquiry through isa, cast, and dyn_cast:
210  static bool classof(const SCEV *S);
211 };
212 
213 /// This class represents an assumption made using SCEV expressions which can
214 /// be checked at run-time.
217 
218  /// A reference to an Interned FoldingSetNodeID for this node. The
219  /// ScalarEvolution's BumpPtrAllocator holds the data.
220  FoldingSetNodeIDRef FastID;
221 
222 public:
224 
225 protected:
227  ~SCEVPredicate() = default;
228  SCEVPredicate(const SCEVPredicate &) = default;
229  SCEVPredicate &operator=(const SCEVPredicate &) = default;
230 
231 public:
233 
234  SCEVPredicateKind getKind() const { return Kind; }
235 
236  /// Returns the estimated complexity of this predicate. This is roughly
237  /// measured in the number of run-time checks required.
238  virtual unsigned getComplexity() const { return 1; }
239 
240  /// Returns true if the predicate is always true. This means that no
241  /// assumptions were made and nothing needs to be checked at run-time.
242  virtual bool isAlwaysTrue() const = 0;
243 
244  /// Returns true if this predicate implies \p N.
245  virtual bool implies(const SCEVPredicate *N) const = 0;
246 
247  /// Prints a textual representation of this predicate with an indentation of
248  /// \p Depth.
249  virtual void print(raw_ostream &OS, unsigned Depth = 0) const = 0;
250 };
251 
253  P.print(OS);
254  return OS;
255 }
256 
257 // Specialize FoldingSetTrait for SCEVPredicate to avoid needing to compute
258 // temporary FoldingSetNodeID values.
259 template <>
261  static void Profile(const SCEVPredicate &X, FoldingSetNodeID &ID) {
262  ID = X.FastID;
263  }
264 
265  static bool Equals(const SCEVPredicate &X, const FoldingSetNodeID &ID,
266  unsigned IDHash, FoldingSetNodeID &TempID) {
267  return ID == X.FastID;
268  }
269 
270  static unsigned ComputeHash(const SCEVPredicate &X,
271  FoldingSetNodeID &TempID) {
272  return X.FastID.ComputeHash();
273  }
274 };
275 
276 /// This class represents an assumption that the expression LHS Pred RHS
277 /// evaluates to true, and this can be checked at run-time.
278 class SCEVComparePredicate final : public SCEVPredicate {
279  /// We assume that LHS Pred RHS is true.
280  const ICmpInst::Predicate Pred;
281  const SCEV *LHS;
282  const SCEV *RHS;
283 
284 public:
286  const ICmpInst::Predicate Pred,
287  const SCEV *LHS, const SCEV *RHS);
288 
289  /// Implementation of the SCEVPredicate interface
290  bool implies(const SCEVPredicate *N) const override;
291  void print(raw_ostream &OS, unsigned Depth = 0) const override;
292  bool isAlwaysTrue() const override;
293 
294  ICmpInst::Predicate getPredicate() const { return Pred; }
295 
296  /// Returns the left hand side of the predicate.
297  const SCEV *getLHS() const { return LHS; }
298 
299  /// Returns the right hand side of the predicate.
300  const SCEV *getRHS() const { return RHS; }
301 
302  /// Methods for support type inquiry through isa, cast, and dyn_cast:
303  static bool classof(const SCEVPredicate *P) {
304  return P->getKind() == P_Compare;
305  }
306 };
307 
308 /// This class represents an assumption made on an AddRec expression. Given an
309 /// affine AddRec expression {a,+,b}, we assume that it has the nssw or nusw
310 /// flags (defined below) in the first X iterations of the loop, where X is a
311 /// SCEV expression returned by getPredicatedBackedgeTakenCount).
312 ///
313 /// Note that this does not imply that X is equal to the backedge taken
314 /// count. This means that if we have a nusw predicate for i32 {0,+,1} with a
315 /// predicated backedge taken count of X, we only guarantee that {0,+,1} has
316 /// nusw in the first X iterations. {0,+,1} may still wrap in the loop if we
317 /// have more than X iterations.
318 class SCEVWrapPredicate final : public SCEVPredicate {
319 public:
320  /// Similar to SCEV::NoWrapFlags, but with slightly different semantics
321  /// for FlagNUSW. The increment is considered to be signed, and a + b
322  /// (where b is the increment) is considered to wrap if:
323  /// zext(a + b) != zext(a) + sext(b)
324  ///
325  /// If Signed is a function that takes an n-bit tuple and maps to the
326  /// integer domain as the tuples value interpreted as twos complement,
327  /// and Unsigned a function that takes an n-bit tuple and maps to the
328  /// integer domain as as the base two value of input tuple, then a + b
329  /// has IncrementNUSW iff:
330  ///
331  /// 0 <= Unsigned(a) + Signed(b) < 2^n
332  ///
333  /// The IncrementNSSW flag has identical semantics with SCEV::FlagNSW.
334  ///
335  /// Note that the IncrementNUSW flag is not commutative: if base + inc
336  /// has IncrementNUSW, then inc + base doesn't neccessarily have this
337  /// property. The reason for this is that this is used for sign/zero
338  /// extending affine AddRec SCEV expressions when a SCEVWrapPredicate is
339  /// assumed. A {base,+,inc} expression is already non-commutative with
340  /// regards to base and inc, since it is interpreted as:
341  /// (((base + inc) + inc) + inc) ...
343  IncrementAnyWrap = 0, // No guarantee.
344  IncrementNUSW = (1 << 0), // No unsigned with signed increment wrap.
345  IncrementNSSW = (1 << 1), // No signed with signed increment wrap
346  // (equivalent with SCEV::NSW)
347  IncrementNoWrapMask = (1 << 2) - 1
348  };
349 
350  /// Convenient IncrementWrapFlags manipulation methods.
351  [[nodiscard]] static SCEVWrapPredicate::IncrementWrapFlags
354  assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
355  assert((OffFlags & IncrementNoWrapMask) == OffFlags &&
356  "Invalid flags value!");
357  return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & ~OffFlags);
358  }
359 
360  [[nodiscard]] static SCEVWrapPredicate::IncrementWrapFlags
362  assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
363  assert((Mask & IncrementNoWrapMask) == Mask && "Invalid mask value!");
364 
366  }
367 
368  [[nodiscard]] static SCEVWrapPredicate::IncrementWrapFlags
371  assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
372  assert((OnFlags & IncrementNoWrapMask) == OnFlags &&
373  "Invalid flags value!");
374 
375  return (SCEVWrapPredicate::IncrementWrapFlags)(Flags | OnFlags);
376  }
377 
378  /// Returns the set of SCEVWrapPredicate no wrap flags implied by a
379  /// SCEVAddRecExpr.
380  [[nodiscard]] static SCEVWrapPredicate::IncrementWrapFlags
382 
383 private:
384  const SCEVAddRecExpr *AR;
385  IncrementWrapFlags Flags;
386 
387 public:
389  const SCEVAddRecExpr *AR,
390  IncrementWrapFlags Flags);
391 
392  /// Returns the set assumed no overflow flags.
393  IncrementWrapFlags getFlags() const { return Flags; }
394 
395  /// Implementation of the SCEVPredicate interface
396  const SCEVAddRecExpr *getExpr() const;
397  bool implies(const SCEVPredicate *N) const override;
398  void print(raw_ostream &OS, unsigned Depth = 0) const override;
399  bool isAlwaysTrue() const override;
400 
401  /// Methods for support type inquiry through isa, cast, and dyn_cast:
402  static bool classof(const SCEVPredicate *P) {
403  return P->getKind() == P_Wrap;
404  }
405 };
406 
407 /// This class represents a composition of other SCEV predicates, and is the
408 /// class that most clients will interact with. This is equivalent to a
409 /// logical "AND" of all the predicates in the union.
410 ///
411 /// NB! Unlike other SCEVPredicate sub-classes this class does not live in the
412 /// ScalarEvolution::Preds folding set. This is why the \c add function is sound.
413 class SCEVUnionPredicate final : public SCEVPredicate {
414 private:
415  using PredicateMap =
417 
418  /// Vector with references to all predicates in this union.
420 
421  /// Adds a predicate to this union.
422  void add(const SCEVPredicate *N);
423 
424 public:
426 
428  return Preds;
429  }
430 
431  /// Implementation of the SCEVPredicate interface
432  bool isAlwaysTrue() const override;
433  bool implies(const SCEVPredicate *N) const override;
434  void print(raw_ostream &OS, unsigned Depth) const override;
435 
436  /// We estimate the complexity of a union predicate as the size number of
437  /// predicates in the union.
438  unsigned getComplexity() const override { return Preds.size(); }
439 
440  /// Methods for support type inquiry through isa, cast, and dyn_cast:
441  static bool classof(const SCEVPredicate *P) {
442  return P->getKind() == P_Union;
443  }
444 };
445 
446 /// The main scalar evolution driver. Because client code (intentionally)
447 /// can't do much with the SCEV objects directly, they must ask this class
448 /// for services.
450  friend class ScalarEvolutionsTest;
451 
452 public:
453  /// An enum describing the relationship between a SCEV and a loop.
455  LoopVariant, ///< The SCEV is loop-variant (unknown).
456  LoopInvariant, ///< The SCEV is loop-invariant.
457  LoopComputable ///< The SCEV varies predictably with the loop.
458  };
459 
460  /// An enum describing the relationship between a SCEV and a basic block.
462  DoesNotDominateBlock, ///< The SCEV does not dominate the block.
463  DominatesBlock, ///< The SCEV dominates the block.
464  ProperlyDominatesBlock ///< The SCEV properly dominates the block.
465  };
466 
467  /// Convenient NoWrapFlags manipulation that hides enum casts and is
468  /// visible in the ScalarEvolution name space.
469  [[nodiscard]] static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags,
470  int Mask) {
471  return (SCEV::NoWrapFlags)(Flags & Mask);
472  }
473  [[nodiscard]] static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags,
474  SCEV::NoWrapFlags OnFlags) {
475  return (SCEV::NoWrapFlags)(Flags | OnFlags);
476  }
477  [[nodiscard]] static SCEV::NoWrapFlags
479  return (SCEV::NoWrapFlags)(Flags & ~OffFlags);
480  }
481  [[nodiscard]] static bool hasFlags(SCEV::NoWrapFlags Flags,
482  SCEV::NoWrapFlags TestFlags) {
483  return TestFlags == maskFlags(Flags, TestFlags);
484  };
485 
487  DominatorTree &DT, LoopInfo &LI);
490 
491  LLVMContext &getContext() const { return F.getContext(); }
492 
493  /// Test if values of the given type are analyzable within the SCEV
494  /// framework. This primarily includes integer types, and it can optionally
495  /// include pointer types if the ScalarEvolution class has access to
496  /// target-specific information.
497  bool isSCEVable(Type *Ty) const;
498 
499  /// Return the size in bits of the specified type, for which isSCEVable must
500  /// return true.
501  uint64_t getTypeSizeInBits(Type *Ty) const;
502 
503  /// Return a type with the same bitwidth as the given type and which
504  /// represents how SCEV will treat the given type, for which isSCEVable must
505  /// return true. For pointer types, this is the pointer-sized integer type.
506  Type *getEffectiveSCEVType(Type *Ty) const;
507 
508  // Returns a wider type among {Ty1, Ty2}.
509  Type *getWiderType(Type *Ty1, Type *Ty2) const;
510 
511  /// Return true if there exists a point in the program at which both
512  /// A and B could be operands to the same instruction.
513  /// SCEV expressions are generally assumed to correspond to instructions
514  /// which could exists in IR. In general, this requires that there exists
515  /// a use point in the program where all operands dominate the use.
516  ///
517  /// Example:
518  /// loop {
519  /// if
520  /// loop { v1 = load @global1; }
521  /// else
522  /// loop { v2 = load @global2; }
523  /// }
524  /// No SCEV with operand V1, and v2 can exist in this program.
525  bool instructionCouldExistWitthOperands(const SCEV *A, const SCEV *B);
526 
527  /// Return true if the SCEV is a scAddRecExpr or it contains
528  /// scAddRecExpr. The result will be cached in HasRecMap.
529  bool containsAddRecurrence(const SCEV *S);
530 
531  /// Is operation \p BinOp between \p LHS and \p RHS provably does not have
532  /// a signed/unsigned overflow (\p Signed)? If \p CtxI is specified, the
533  /// no-overflow fact should be true in the context of this instruction.
535  const SCEV *LHS, const SCEV *RHS,
536  const Instruction *CtxI = nullptr);
537 
538  /// Parse NSW/NUW flags from add/sub/mul IR binary operation \p Op into
539  /// SCEV no-wrap flags, and deduce flag[s] that aren't known yet.
540  /// Does not mutate the original instruction. Returns None if it could not
541  /// deduce more precise flags than the instruction already has, otherwise
542  /// returns proven flags.
545 
546  /// Notify this ScalarEvolution that \p User directly uses SCEVs in \p Ops.
547  void registerUser(const SCEV *User, ArrayRef<const SCEV *> Ops);
548 
549  /// Return true if the SCEV expression contains an undef value.
550  bool containsUndefs(const SCEV *S) const;
551 
552  /// Return true if the SCEV expression contains a Value that has been
553  /// optimised out and is now a nullptr.
554  bool containsErasedValue(const SCEV *S) const;
555 
556  /// Return a SCEV expression for the full generality of the specified
557  /// expression.
558  const SCEV *getSCEV(Value *V);
559 
560  const SCEV *getConstant(ConstantInt *V);
561  const SCEV *getConstant(const APInt &Val);
562  const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false);
563  const SCEV *getLosslessPtrToIntExpr(const SCEV *Op, unsigned Depth = 0);
564  const SCEV *getPtrToIntExpr(const SCEV *Op, Type *Ty);
565  const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
566  const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
567  const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
568  const SCEV *getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty);
569  const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty);
572  unsigned Depth = 0);
573  const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS,
575  unsigned Depth = 0) {
577  return getAddExpr(Ops, Flags, Depth);
578  }
579  const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
581  unsigned Depth = 0) {
582  SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
583  return getAddExpr(Ops, Flags, Depth);
584  }
587  unsigned Depth = 0);
588  const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS,
590  unsigned Depth = 0) {
592  return getMulExpr(Ops, Flags, Depth);
593  }
594  const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
596  unsigned Depth = 0) {
597  SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
598  return getMulExpr(Ops, Flags, Depth);
599  }
600  const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS);
601  const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS);
602  const SCEV *getURemExpr(const SCEV *LHS, const SCEV *RHS);
603  const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L,
604  SCEV::NoWrapFlags Flags);
606  const Loop *L, SCEV::NoWrapFlags Flags);
608  const Loop *L, SCEV::NoWrapFlags Flags) {
609  SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end());
610  return getAddRecExpr(NewOp, L, Flags);
611  }
612 
613  /// Checks if \p SymbolicPHI can be rewritten as an AddRecExpr under some
614  /// Predicates. If successful return these <AddRecExpr, Predicates>;
615  /// The function is intended to be called from PSCEV (the caller will decide
616  /// whether to actually add the predicates and carry out the rewrites).
618  createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI);
619 
620  /// Returns an expression for a GEP
621  ///
622  /// \p GEP The GEP. The indices contained in the GEP itself are ignored,
623  /// instead we use IndexExprs.
624  /// \p IndexExprs The expressions for the indices.
625  const SCEV *getGEPExpr(GEPOperator *GEP,
626  const SmallVectorImpl<const SCEV *> &IndexExprs);
627  const SCEV *getAbsExpr(const SCEV *Op, bool IsNSW);
632  const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS);
634  const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS);
636  const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS);
638  const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS,
639  bool Sequential = false);
641  bool Sequential = false);
642  const SCEV *getUnknown(Value *V);
643  const SCEV *getCouldNotCompute();
644 
645  /// Return a SCEV for the constant 0 of a specific type.
646  const SCEV *getZero(Type *Ty) { return getConstant(Ty, 0); }
647 
648  /// Return a SCEV for the constant 1 of a specific type.
649  const SCEV *getOne(Type *Ty) { return getConstant(Ty, 1); }
650 
651  /// Return a SCEV for the constant -1 of a specific type.
652  const SCEV *getMinusOne(Type *Ty) {
653  return getConstant(Ty, -1, /*isSigned=*/true);
654  }
655 
656  /// Return an expression for sizeof ScalableTy that is type IntTy, where
657  /// ScalableTy is a scalable vector type.
658  const SCEV *getSizeOfScalableVectorExpr(Type *IntTy,
659  ScalableVectorType *ScalableTy);
660 
661  /// Return an expression for the alloc size of AllocTy that is type IntTy
662  const SCEV *getSizeOfExpr(Type *IntTy, Type *AllocTy);
663 
664  /// Return an expression for the store size of StoreTy that is type IntTy
665  const SCEV *getStoreSizeOfExpr(Type *IntTy, Type *StoreTy);
666 
667  /// Return an expression for offsetof on the given field with type IntTy
668  const SCEV *getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo);
669 
670  /// Return the SCEV object corresponding to -V.
671  const SCEV *getNegativeSCEV(const SCEV *V,
673 
674  /// Return the SCEV object corresponding to ~V.
675  const SCEV *getNotSCEV(const SCEV *V);
676 
677  /// Return LHS-RHS. Minus is represented in SCEV as A+B*-1.
678  ///
679  /// If the LHS and RHS are pointers which don't share a common base
680  /// (according to getPointerBase()), this returns a SCEVCouldNotCompute.
681  /// To compute the difference between two unrelated pointers, you can
682  /// explicitly convert the arguments using getPtrToIntExpr(), for pointer
683  /// types that support it.
684  const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
686  unsigned Depth = 0);
687 
688  /// Compute ceil(N / D). N and D are treated as unsigned values.
689  ///
690  /// Since SCEV doesn't have native ceiling division, this generates a
691  /// SCEV expression of the following form:
692  ///
693  /// umin(N, 1) + floor((N - umin(N, 1)) / D)
694  ///
695  /// A denominator of zero or poison is handled the same way as getUDivExpr().
696  const SCEV *getUDivCeilSCEV(const SCEV *N, const SCEV *D);
697 
698  /// Return a SCEV corresponding to a conversion of the input value to the
699  /// specified type. If the type must be extended, it is zero extended.
700  const SCEV *getTruncateOrZeroExtend(const SCEV *V, Type *Ty,
701  unsigned Depth = 0);
702 
703  /// Return a SCEV corresponding to a conversion of the input value to the
704  /// specified type. If the type must be extended, it is sign extended.
705  const SCEV *getTruncateOrSignExtend(const SCEV *V, Type *Ty,
706  unsigned Depth = 0);
707 
708  /// Return a SCEV corresponding to a conversion of the input value to the
709  /// specified type. If the type must be extended, it is zero extended. The
710  /// conversion must not be narrowing.
711  const SCEV *getNoopOrZeroExtend(const SCEV *V, Type *Ty);
712 
713  /// Return a SCEV corresponding to a conversion of the input value to the
714  /// specified type. If the type must be extended, it is sign extended. The
715  /// conversion must not be narrowing.
716  const SCEV *getNoopOrSignExtend(const SCEV *V, Type *Ty);
717 
718  /// Return a SCEV corresponding to a conversion of the input value to the
719  /// specified type. If the type must be extended, it is extended with
720  /// unspecified bits. The conversion must not be narrowing.
721  const SCEV *getNoopOrAnyExtend(const SCEV *V, Type *Ty);
722 
723  /// Return a SCEV corresponding to a conversion of the input value to the
724  /// specified type. The conversion must not be widening.
725  const SCEV *getTruncateOrNoop(const SCEV *V, Type *Ty);
726 
727  /// Promote the operands to the wider of the types using zero-extension, and
728  /// then perform a umax operation with them.
729  const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS);
730 
731  /// Promote the operands to the wider of the types using zero-extension, and
732  /// then perform a umin operation with them.
733  const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS,
734  bool Sequential = false);
735 
736  /// Promote the operands to the wider of the types using zero-extension, and
737  /// then perform a umin operation with them. N-ary function.
739  bool Sequential = false);
740 
741  /// Transitively follow the chain of pointer-type operands until reaching a
742  /// SCEV that does not have a single pointer operand. This returns a
743  /// SCEVUnknown pointer for well-formed pointer-type expressions, but corner
744  /// cases do exist.
745  const SCEV *getPointerBase(const SCEV *V);
746 
747  /// Compute an expression equivalent to S - getPointerBase(S).
748  const SCEV *removePointerBase(const SCEV *S);
749 
750  /// Return a SCEV expression for the specified value at the specified scope
751  /// in the program. The L value specifies a loop nest to evaluate the
752  /// expression at, where null is the top-level or a specified loop is
753  /// immediately inside of the loop.
754  ///
755  /// This method can be used to compute the exit value for a variable defined
756  /// in a loop by querying what the value will hold in the parent loop.
757  ///
758  /// In the case that a relevant loop exit value cannot be computed, the
759  /// original value V is returned.
760  const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L);
761 
762  /// This is a convenience function which does getSCEVAtScope(getSCEV(V), L).
763  const SCEV *getSCEVAtScope(Value *V, const Loop *L);
764 
765  /// Test whether entry to the loop is protected by a conditional between LHS
766  /// and RHS. This is used to help avoid max expressions in loop trip
767  /// counts, and to eliminate casts.
769  const SCEV *LHS, const SCEV *RHS);
770 
771  /// Test whether entry to the basic block is protected by a conditional
772  /// between LHS and RHS.
774  ICmpInst::Predicate Pred, const SCEV *LHS,
775  const SCEV *RHS);
776 
777  /// Test whether the backedge of the loop is protected by a conditional
778  /// between LHS and RHS. This is used to eliminate casts.
780  const SCEV *LHS, const SCEV *RHS);
781 
782  /// Convert from an "exit count" (i.e. "backedge taken count") to a "trip
783  /// count". A "trip count" is the number of times the header of the loop
784  /// will execute if an exit is taken after the specified number of backedges
785  /// have been taken. (e.g. TripCount = ExitCount + 1). Note that the
786  /// expression can overflow if ExitCount = UINT_MAX. \p Extend controls
787  /// how potential overflow is handled. If true, a wider result type is
788  /// returned. ex: EC = 255 (i8), TC = 256 (i9). If false, result unsigned
789  /// wraps with 2s-complement semantics. ex: EC = 255 (i8), TC = 0 (i8)
790  const SCEV *getTripCountFromExitCount(const SCEV *ExitCount,
791  bool Extend = true);
792 
793  /// Returns the exact trip count of the loop if we can compute it, and
794  /// the result is a small constant. '0' is used to represent an unknown
795  /// or non-constant trip count. Note that a trip count is simply one more
796  /// than the backedge taken count for the loop.
797  unsigned getSmallConstantTripCount(const Loop *L);
798 
799  /// Return the exact trip count for this loop if we exit through ExitingBlock.
800  /// '0' is used to represent an unknown or non-constant trip count. Note
801  /// that a trip count is simply one more than the backedge taken count for
802  /// the same exit.
803  /// This "trip count" assumes that control exits via ExitingBlock. More
804  /// precisely, it is the number of times that control will reach ExitingBlock
805  /// before taking the branch. For loops with multiple exits, it may not be
806  /// the number times that the loop header executes if the loop exits
807  /// prematurely via another branch.
808  unsigned getSmallConstantTripCount(const Loop *L,
809  const BasicBlock *ExitingBlock);
810 
811  /// Returns the upper bound of the loop trip count as a normal unsigned
812  /// value.
813  /// Returns 0 if the trip count is unknown or not constant.
814  unsigned getSmallConstantMaxTripCount(const Loop *L);
815 
816  /// Returns the upper bound of the loop trip count infered from array size.
817  /// Can not access bytes starting outside the statically allocated size
818  /// without being immediate UB.
819  /// Returns SCEVCouldNotCompute if the trip count could not inferred
820  /// from array accesses.
821  const SCEV *getConstantMaxTripCountFromArray(const Loop *L);
822 
823  /// Returns the largest constant divisor of the trip count as a normal
824  /// unsigned value, if possible. This means that the actual trip count is
825  /// always a multiple of the returned value. Returns 1 if the trip count is
826  /// unknown or not guaranteed to be the multiple of a constant., Will also
827  /// return 1 if the trip count is very large (>= 2^32).
828  /// Note that the argument is an exit count for loop L, NOT a trip count.
829  unsigned getSmallConstantTripMultiple(const Loop *L,
830  const SCEV *ExitCount);
831 
832  /// Returns the largest constant divisor of the trip count of the
833  /// loop. Will return 1 if no trip count could be computed, or if a
834  /// divisor could not be found.
835  unsigned getSmallConstantTripMultiple(const Loop *L);
836 
837  /// Returns the largest constant divisor of the trip count of this loop as a
838  /// normal unsigned value, if possible. This means that the actual trip
839  /// count is always a multiple of the returned value (don't forget the trip
840  /// count could very well be zero as well!). As explained in the comments
841  /// for getSmallConstantTripCount, this assumes that control exits the loop
842  /// via ExitingBlock.
843  unsigned getSmallConstantTripMultiple(const Loop *L,
844  const BasicBlock *ExitingBlock);
845 
846  /// The terms "backedge taken count" and "exit count" are used
847  /// interchangeably to refer to the number of times the backedge of a loop
848  /// has executed before the loop is exited.
850  /// An expression exactly describing the number of times the backedge has
851  /// executed when a loop is exited.
853  /// A constant which provides an upper bound on the exact trip count.
855  /// An expression which provides an upper bound on the exact trip count.
857  };
858 
859  /// Return the number of times the backedge executes before the given exit
860  /// would be taken; if not exactly computable, return SCEVCouldNotCompute.
861  /// For a single exit loop, this value is equivelent to the result of
862  /// getBackedgeTakenCount. The loop is guaranteed to exit (via *some* exit)
863  /// before the backedge is executed (ExitCount + 1) times. Note that there
864  /// is no guarantee about *which* exit is taken on the exiting iteration.
865  const SCEV *getExitCount(const Loop *L, const BasicBlock *ExitingBlock,
867 
868  /// If the specified loop has a predictable backedge-taken count, return it,
869  /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count is
870  /// the number of times the loop header will be branched to from within the
871  /// loop, assuming there are no abnormal exists like exception throws. This is
872  /// one less than the trip count of the loop, since it doesn't count the first
873  /// iteration, when the header is branched to from outside the loop.
874  ///
875  /// Note that it is not valid to call this method on a loop without a
876  /// loop-invariant backedge-taken count (see
877  /// hasLoopInvariantBackedgeTakenCount).
879 
880  /// Similar to getBackedgeTakenCount, except it will add a set of
881  /// SCEV predicates to Predicates that are required to be true in order for
882  /// the answer to be correct. Predicates can be checked with run-time
883  /// checks and can be used to perform loop versioning.
884  const SCEV *getPredicatedBackedgeTakenCount(const Loop *L,
886 
887  /// When successful, this returns a SCEVConstant that is greater than or equal
888  /// to (i.e. a "conservative over-approximation") of the value returend by
889  /// getBackedgeTakenCount. If such a value cannot be computed, it returns the
890  /// SCEVCouldNotCompute object.
893  }
894 
895  /// When successful, this returns a SCEV that is greater than or equal
896  /// to (i.e. a "conservative over-approximation") of the value returend by
897  /// getBackedgeTakenCount. If such a value cannot be computed, it returns the
898  /// SCEVCouldNotCompute object.
901  }
902 
903  /// Return true if the backedge taken count is either the value returned by
904  /// getConstantMaxBackedgeTakenCount or zero.
905  bool isBackedgeTakenCountMaxOrZero(const Loop *L);
906 
907  /// Return true if the specified loop has an analyzable loop-invariant
908  /// backedge-taken count.
910 
911  // This method should be called by the client when it made any change that
912  // would invalidate SCEV's answers, and the client wants to remove all loop
913  // information held internally by ScalarEvolution. This is intended to be used
914  // when the alternative to forget a loop is too expensive (i.e. large loop
915  // bodies).
916  void forgetAllLoops();
917 
918  /// This method should be called by the client when it has changed a loop in
919  /// a way that may effect ScalarEvolution's ability to compute a trip count,
920  /// or if the loop is deleted. This call is potentially expensive for large
921  /// loop bodies.
922  void forgetLoop(const Loop *L);
923 
924  // This method invokes forgetLoop for the outermost loop of the given loop
925  // \p L, making ScalarEvolution forget about all this subtree. This needs to
926  // be done whenever we make a transform that may affect the parameters of the
927  // outer loop, such as exit counts for branches.
928  void forgetTopmostLoop(const Loop *L);
929 
930  /// This method should be called by the client when it has changed a value
931  /// in a way that may effect its value, or which may disconnect it from a
932  /// def-use chain linking it to a loop.
933  void forgetValue(Value *V);
934 
935  /// Called when the client has changed the disposition of values in
936  /// this loop.
937  ///
938  /// We don't have a way to invalidate per-loop dispositions. Clear and
939  /// recompute is simpler.
940  void forgetLoopDispositions();
941 
942  /// Determine the minimum number of zero bits that S is guaranteed to end in
943  /// (at every loop iteration). It is, at the same time, the minimum number
944  /// of times S is divisible by 2. For example, given {4,+,8} it returns 2.
945  /// If S is guaranteed to be 0, it returns the bitwidth of S.
947 
948  /// Determine the unsigned range for a particular SCEV.
949  /// NOTE: This returns a copy of the reference returned by getRangeRef.
951  return getRangeRef(S, HINT_RANGE_UNSIGNED);
952  }
953 
954  /// Determine the min of the unsigned range for a particular SCEV.
956  return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMin();
957  }
958 
959  /// Determine the max of the unsigned range for a particular SCEV.
961  return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMax();
962  }
963 
964  /// Determine the signed range for a particular SCEV.
965  /// NOTE: This returns a copy of the reference returned by getRangeRef.
967  return getRangeRef(S, HINT_RANGE_SIGNED);
968  }
969 
970  /// Determine the min of the signed range for a particular SCEV.
972  return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMin();
973  }
974 
975  /// Determine the max of the signed range for a particular SCEV.
977  return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMax();
978  }
979 
980  /// Test if the given expression is known to be negative.
981  bool isKnownNegative(const SCEV *S);
982 
983  /// Test if the given expression is known to be positive.
984  bool isKnownPositive(const SCEV *S);
985 
986  /// Test if the given expression is known to be non-negative.
987  bool isKnownNonNegative(const SCEV *S);
988 
989  /// Test if the given expression is known to be non-positive.
990  bool isKnownNonPositive(const SCEV *S);
991 
992  /// Test if the given expression is known to be non-zero.
993  bool isKnownNonZero(const SCEV *S);
994 
995  /// Splits SCEV expression \p S into two SCEVs. One of them is obtained from
996  /// \p S by substitution of all AddRec sub-expression related to loop \p L
997  /// with initial value of that SCEV. The second is obtained from \p S by
998  /// substitution of all AddRec sub-expressions related to loop \p L with post
999  /// increment of this AddRec in the loop \p L. In both cases all other AddRec
1000  /// sub-expressions (not related to \p L) remain the same.
1001  /// If the \p S contains non-invariant unknown SCEV the function returns
1002  /// CouldNotCompute SCEV in both values of std::pair.
1003  /// For example, for SCEV S={0, +, 1}<L1> + {0, +, 1}<L2> and loop L=L1
1004  /// the function returns pair:
1005  /// first = {0, +, 1}<L2>
1006  /// second = {1, +, 1}<L1> + {0, +, 1}<L2>
1007  /// We can see that for the first AddRec sub-expression it was replaced with
1008  /// 0 (initial value) for the first element and to {1, +, 1}<L1> (post
1009  /// increment value) for the second one. In both cases AddRec expression
1010  /// related to L2 remains the same.
1011  std::pair<const SCEV *, const SCEV *> SplitIntoInitAndPostInc(const Loop *L,
1012  const SCEV *S);
1013 
1014  /// We'd like to check the predicate on every iteration of the most dominated
1015  /// loop between loops used in LHS and RHS.
1016  /// To do this we use the following list of steps:
1017  /// 1. Collect set S all loops on which either LHS or RHS depend.
1018  /// 2. If S is non-empty
1019  /// a. Let PD be the element of S which is dominated by all other elements.
1020  /// b. Let E(LHS) be value of LHS on entry of PD.
1021  /// To get E(LHS), we should just take LHS and replace all AddRecs that are
1022  /// attached to PD on with their entry values.
1023  /// Define E(RHS) in the same way.
1024  /// c. Let B(LHS) be value of L on backedge of PD.
1025  /// To get B(LHS), we should just take LHS and replace all AddRecs that are
1026  /// attached to PD on with their backedge values.
1027  /// Define B(RHS) in the same way.
1028  /// d. Note that E(LHS) and E(RHS) are automatically available on entry of PD,
1029  /// so we can assert on that.
1030  /// e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) &&
1031  /// isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS))
1032  bool isKnownViaInduction(ICmpInst::Predicate Pred, const SCEV *LHS,
1033  const SCEV *RHS);
1034 
1035  /// Test if the given expression is known to satisfy the condition described
1036  /// by Pred, LHS, and RHS.
1037  bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS,
1038  const SCEV *RHS);
1039 
1040  /// Check whether the condition described by Pred, LHS, and RHS is true or
1041  /// false. If we know it, return the evaluation of this condition. If neither
1042  /// is proved, return None.
1044  const SCEV *RHS);
1045 
1046  /// Test if the given expression is known to satisfy the condition described
1047  /// by Pred, LHS, and RHS in the given Context.
1048  bool isKnownPredicateAt(ICmpInst::Predicate Pred, const SCEV *LHS,
1049  const SCEV *RHS, const Instruction *CtxI);
1050 
1051  /// Check whether the condition described by Pred, LHS, and RHS is true or
1052  /// false in the given \p Context. If we know it, return the evaluation of
1053  /// this condition. If neither is proved, return None.
1055  const SCEV *RHS, const Instruction *CtxI);
1056 
1057  /// Test if the condition described by Pred, LHS, RHS is known to be true on
1058  /// every iteration of the loop of the recurrency LHS.
1060  const SCEVAddRecExpr *LHS, const SCEV *RHS);
1061 
1062  /// A predicate is said to be monotonically increasing if may go from being
1063  /// false to being true as the loop iterates, but never the other way
1064  /// around. A predicate is said to be monotonically decreasing if may go
1065  /// from being true to being false as the loop iterates, but never the other
1066  /// way around.
1070  };
1071 
1072  /// If, for all loop invariant X, the predicate "LHS `Pred` X" is
1073  /// monotonically increasing or decreasing, returns
1074  /// Some(MonotonicallyIncreasing) and Some(MonotonicallyDecreasing)
1075  /// respectively. If we could not prove either of these facts, returns None.
1078  ICmpInst::Predicate Pred);
1079 
1082  const SCEV *LHS;
1083  const SCEV *RHS;
1084 
1086  const SCEV *RHS)
1087  : Pred(Pred), LHS(LHS), RHS(RHS) {}
1088  };
1089  /// If the result of the predicate LHS `Pred` RHS is loop invariant with
1090  /// respect to L, return a LoopInvariantPredicate with LHS and RHS being
1091  /// invariants, available at L's entry. Otherwise, return None.
1094  const SCEV *RHS, const Loop *L,
1095  const Instruction *CtxI = nullptr);
1096 
1097  /// If the result of the predicate LHS `Pred` RHS is loop invariant with
1098  /// respect to L at given Context during at least first MaxIter iterations,
1099  /// return a LoopInvariantPredicate with LHS and RHS being invariants,
1100  /// available at L's entry. Otherwise, return None. The predicate should be
1101  /// the loop's exit condition.
1104  const SCEV *LHS,
1105  const SCEV *RHS, const Loop *L,
1106  const Instruction *CtxI,
1107  const SCEV *MaxIter);
1108 
1109  /// Simplify LHS and RHS in a comparison with predicate Pred. Return true
1110  /// iff any changes were made. If the operands are provably equal or
1111  /// unequal, LHS and RHS are set to the same value and Pred is set to either
1112  /// ICMP_EQ or ICMP_NE. ControllingFiniteLoop is set if this comparison
1113  /// controls the exit of a loop known to have a finite number of iterations.
1114  bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS,
1115  const SCEV *&RHS, unsigned Depth = 0,
1116  bool ControllingFiniteLoop = false);
1117 
1118  /// Return the "disposition" of the given SCEV with respect to the given
1119  /// loop.
1120  LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L);
1121 
1122  /// Return true if the value of the given SCEV is unchanging in the
1123  /// specified loop.
1124  bool isLoopInvariant(const SCEV *S, const Loop *L);
1125 
1126  /// Determine if the SCEV can be evaluated at loop's entry. It is true if it
1127  /// doesn't depend on a SCEVUnknown of an instruction which is dominated by
1128  /// the header of loop L.
1129  bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L);
1130 
1131  /// Return true if the given SCEV changes value in a known way in the
1132  /// specified loop. This property being true implies that the value is
1133  /// variant in the loop AND that we can emit an expression to compute the
1134  /// value of the expression at any particular loop iteration.
1135  bool hasComputableLoopEvolution(const SCEV *S, const Loop *L);
1136 
1137  /// Return the "disposition" of the given SCEV with respect to the given
1138  /// block.
1140 
1141  /// Return true if elements that makes up the given SCEV dominate the
1142  /// specified basic block.
1143  bool dominates(const SCEV *S, const BasicBlock *BB);
1144 
1145  /// Return true if elements that makes up the given SCEV properly dominate
1146  /// the specified basic block.
1147  bool properlyDominates(const SCEV *S, const BasicBlock *BB);
1148 
1149  /// Test whether the given SCEV has Op as a direct or indirect operand.
1150  bool hasOperand(const SCEV *S, const SCEV *Op) const;
1151 
1152  /// Return the size of an element read or written by Inst.
1153  const SCEV *getElementSize(Instruction *Inst);
1154 
1155  void print(raw_ostream &OS) const;
1156  void verify() const;
1157  bool invalidate(Function &F, const PreservedAnalyses &PA,
1159 
1160  /// Return the DataLayout associated with the module this SCEV instance is
1161  /// operating on.
1162  const DataLayout &getDataLayout() const {
1163  return F.getParent()->getDataLayout();
1164  }
1165 
1166  const SCEVPredicate *getEqualPredicate(const SCEV *LHS, const SCEV *RHS);
1168  const SCEV *LHS, const SCEV *RHS);
1169 
1170  const SCEVPredicate *
1171  getWrapPredicate(const SCEVAddRecExpr *AR,
1173 
1174  /// Re-writes the SCEV according to the Predicates in \p A.
1175  const SCEV *rewriteUsingPredicate(const SCEV *S, const Loop *L,
1176  const SCEVPredicate &A);
1177  /// Tries to convert the \p S expression to an AddRec expression,
1178  /// adding additional predicates to \p Preds as required.
1180  const SCEV *S, const Loop *L,
1182 
1183  /// Compute \p LHS - \p RHS and returns the result as an APInt if it is a
1184  /// constant, and None if it isn't.
1185  ///
1186  /// This is intended to be a cheaper version of getMinusSCEV. We can be
1187  /// frugal here since we just bail out of actually constructing and
1188  /// canonicalizing an expression in the cases where the result isn't going
1189  /// to be a constant.
1191 
1192  /// Update no-wrap flags of an AddRec. This may drop the cached info about
1193  /// this AddRec (such as range info) in case if new flags may potentially
1194  /// sharpen it.
1195  void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags);
1196 
1197  /// Try to apply information from loop guards for \p L to \p Expr.
1198  const SCEV *applyLoopGuards(const SCEV *Expr, const Loop *L);
1199 
1200  /// Return true if the loop has no abnormal exits. That is, if the loop
1201  /// is not infinite, it must exit through an explicit edge in the CFG.
1202  /// (As opposed to either a) throwing out of the function or b) entering a
1203  /// well defined infinite loop in some callee.)
1204  bool loopHasNoAbnormalExits(const Loop *L) {
1205  return getLoopProperties(L).HasNoAbnormalExits;
1206  }
1207 
1208  /// Return true if this loop is finite by assumption. That is,
1209  /// to be infinite, it must also be undefined.
1210  bool loopIsFiniteByAssumption(const Loop *L);
1211 
1212 private:
1213  /// A CallbackVH to arrange for ScalarEvolution to be notified whenever a
1214  /// Value is deleted.
1215  class SCEVCallbackVH final : public CallbackVH {
1216  ScalarEvolution *SE;
1217 
1218  void deleted() override;
1219  void allUsesReplacedWith(Value *New) override;
1220 
1221  public:
1222  SCEVCallbackVH(Value *V, ScalarEvolution *SE = nullptr);
1223  };
1224 
1225  friend class SCEVCallbackVH;
1226  friend class SCEVExpander;
1227  friend class SCEVUnknown;
1228 
1229  /// The function we are analyzing.
1230  Function &F;
1231 
1232  /// Does the module have any calls to the llvm.experimental.guard intrinsic
1233  /// at all? If this is false, we avoid doing work that will only help if
1234  /// thare are guards present in the IR.
1235  bool HasGuards;
1236 
1237  /// The target library information for the target we are targeting.
1238  TargetLibraryInfo &TLI;
1239 
1240  /// The tracker for \@llvm.assume intrinsics in this function.
1241  AssumptionCache &AC;
1242 
1243  /// The dominator tree.
1244  DominatorTree &DT;
1245 
1246  /// The loop information for the function we are currently analyzing.
1247  LoopInfo &LI;
1248 
1249  /// This SCEV is used to represent unknown trip counts and things.
1250  std::unique_ptr<SCEVCouldNotCompute> CouldNotCompute;
1251 
1252  /// The type for HasRecMap.
1254 
1255  /// This is a cache to record whether a SCEV contains any scAddRecExpr.
1256  HasRecMapType HasRecMap;
1257 
1258  /// The type for ExprValueMap.
1261 
1262  /// ExprValueMap -- This map records the original values from which
1263  /// the SCEV expr is generated from.
1264  ExprValueMapType ExprValueMap;
1265 
1266  /// The type for ValueExprMap.
1267  using ValueExprMapType =
1269 
1270  /// This is a cache of the values we have analyzed so far.
1271  ValueExprMapType ValueExprMap;
1272 
1273  /// Mark predicate values currently being processed by isImpliedCond.
1274  SmallPtrSet<const Value *, 6> PendingLoopPredicates;
1275 
1276  /// Mark SCEVUnknown Phis currently being processed by getRangeRef.
1277  SmallPtrSet<const PHINode *, 6> PendingPhiRanges;
1278 
1279  // Mark SCEVUnknown Phis currently being processed by isImpliedViaMerge.
1280  SmallPtrSet<const PHINode *, 6> PendingMerges;
1281 
1282  /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of
1283  /// conditions dominating the backedge of a loop.
1284  bool WalkingBEDominatingConds = false;
1285 
1286  /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a
1287  /// predicate by splitting it into a set of independent predicates.
1288  bool ProvingSplitPredicate = false;
1289 
1290  /// Memoized values for the GetMinTrailingZeros
1291  DenseMap<const SCEV *, uint32_t> MinTrailingZerosCache;
1292 
1293  /// Return the Value set from which the SCEV expr is generated.
1294  ArrayRef<Value *> getSCEVValues(const SCEV *S);
1295 
1296  /// Private helper method for the GetMinTrailingZeros method
1297  uint32_t GetMinTrailingZerosImpl(const SCEV *S);
1298 
1299  /// Information about the number of loop iterations for which a loop exit's
1300  /// branch condition evaluates to the not-taken path. This is a temporary
1301  /// pair of exact and max expressions that are eventually summarized in
1302  /// ExitNotTakenInfo and BackedgeTakenInfo.
1303  struct ExitLimit {
1304  const SCEV *ExactNotTaken; // The exit is not taken exactly this many times
1305  const SCEV *MaxNotTaken; // The exit is not taken at most this many times
1306 
1307  // Not taken either exactly MaxNotTaken or zero times
1308  bool MaxOrZero = false;
1309 
1310  /// A set of predicate guards for this ExitLimit. The result is only valid
1311  /// if all of the predicates in \c Predicates evaluate to 'true' at
1312  /// run-time.
1314 
1315  void addPredicate(const SCEVPredicate *P) {
1316  assert(!isa<SCEVUnionPredicate>(P) && "Only add leaf predicates here!");
1317  Predicates.insert(P);
1318  }
1319 
1320  /// Construct either an exact exit limit from a constant, or an unknown
1321  /// one from a SCEVCouldNotCompute. No other types of SCEVs are allowed
1322  /// as arguments and asserts enforce that internally.
1323  /*implicit*/ ExitLimit(const SCEV *E);
1324 
1325  ExitLimit(
1326  const SCEV *E, const SCEV *M, bool MaxOrZero,
1327  ArrayRef<const SmallPtrSetImpl<const SCEVPredicate *> *> PredSetList);
1328 
1329  ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero,
1331 
1332  ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero);
1333 
1334  /// Test whether this ExitLimit contains any computed information, or
1335  /// whether it's all SCEVCouldNotCompute values.
1336  bool hasAnyInfo() const {
1337  return !isa<SCEVCouldNotCompute>(ExactNotTaken) ||
1338  !isa<SCEVCouldNotCompute>(MaxNotTaken);
1339  }
1340 
1341  /// Test whether this ExitLimit contains all information.
1342  bool hasFullInfo() const {
1343  return !isa<SCEVCouldNotCompute>(ExactNotTaken);
1344  }
1345  };
1346 
1347  /// Information about the number of times a particular loop exit may be
1348  /// reached before exiting the loop.
1349  struct ExitNotTakenInfo {
1350  PoisoningVH<BasicBlock> ExitingBlock;
1351  const SCEV *ExactNotTaken;
1352  const SCEV *MaxNotTaken;
1353  SmallPtrSet<const SCEVPredicate *, 4> Predicates;
1354 
1355  explicit ExitNotTakenInfo(PoisoningVH<BasicBlock> ExitingBlock,
1356  const SCEV *ExactNotTaken,
1357  const SCEV *MaxNotTaken,
1358  const SmallPtrSet<const SCEVPredicate *, 4> &Predicates)
1359  : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken),
1360  MaxNotTaken(ExactNotTaken), Predicates(Predicates) {}
1361 
1362  bool hasAlwaysTruePredicate() const {
1363  return Predicates.empty();
1364  }
1365  };
1366 
1367  /// Information about the backedge-taken count of a loop. This currently
1368  /// includes an exact count and a maximum count.
1369  ///
1370  class BackedgeTakenInfo {
1371  friend class ScalarEvolution;
1372 
1373  /// A list of computable exits and their not-taken counts. Loops almost
1374  /// never have more than one computable exit.
1375  SmallVector<ExitNotTakenInfo, 1> ExitNotTaken;
1376 
1377  /// Expression indicating the least constant maximum backedge-taken count of
1378  /// the loop that is known, or a SCEVCouldNotCompute. This expression is
1379  /// only valid if the redicates associated with all loop exits are true.
1380  const SCEV *ConstantMax = nullptr;
1381 
1382  /// Indicating if \c ExitNotTaken has an element for every exiting block in
1383  /// the loop.
1384  bool IsComplete = false;
1385 
1386  /// Expression indicating the least maximum backedge-taken count of the loop
1387  /// that is known, or a SCEVCouldNotCompute. Lazily computed on first query.
1388  const SCEV *SymbolicMax = nullptr;
1389 
1390  /// True iff the backedge is taken either exactly Max or zero times.
1391  bool MaxOrZero = false;
1392 
1393  bool isComplete() const { return IsComplete; }
1394  const SCEV *getConstantMax() const { return ConstantMax; }
1395 
1396  public:
1397  BackedgeTakenInfo() = default;
1398  BackedgeTakenInfo(BackedgeTakenInfo &&) = default;
1399  BackedgeTakenInfo &operator=(BackedgeTakenInfo &&) = default;
1400 
1401  using EdgeExitInfo = std::pair<BasicBlock *, ExitLimit>;
1402 
1403  /// Initialize BackedgeTakenInfo from a list of exact exit counts.
1404  BackedgeTakenInfo(ArrayRef<EdgeExitInfo> ExitCounts, bool IsComplete,
1405  const SCEV *ConstantMax, bool MaxOrZero);
1406 
1407  /// Test whether this BackedgeTakenInfo contains any computed information,
1408  /// or whether it's all SCEVCouldNotCompute values.
1409  bool hasAnyInfo() const {
1410  return !ExitNotTaken.empty() ||
1411  !isa<SCEVCouldNotCompute>(getConstantMax());
1412  }
1413 
1414  /// Test whether this BackedgeTakenInfo contains complete information.
1415  bool hasFullInfo() const { return isComplete(); }
1416 
1417  /// Return an expression indicating the exact *backedge-taken*
1418  /// count of the loop if it is known or SCEVCouldNotCompute
1419  /// otherwise. If execution makes it to the backedge on every
1420  /// iteration (i.e. there are no abnormal exists like exception
1421  /// throws and thread exits) then this is the number of times the
1422  /// loop header will execute minus one.
1423  ///
1424  /// If the SCEV predicate associated with the answer can be different
1425  /// from AlwaysTrue, we must add a (non null) Predicates argument.
1426  /// The SCEV predicate associated with the answer will be added to
1427  /// Predicates. A run-time check needs to be emitted for the SCEV
1428  /// predicate in order for the answer to be valid.
1429  ///
1430  /// Note that we should always know if we need to pass a predicate
1431  /// argument or not from the way the ExitCounts vector was computed.
1432  /// If we allowed SCEV predicates to be generated when populating this
1433  /// vector, this information can contain them and therefore a
1434  /// SCEVPredicate argument should be added to getExact.
1435  const SCEV *getExact(const Loop *L, ScalarEvolution *SE,
1436  SmallVector<const SCEVPredicate *, 4> *Predicates = nullptr) const;
1437 
1438  /// Return the number of times this loop exit may fall through to the back
1439  /// edge, or SCEVCouldNotCompute. The loop is guaranteed not to exit via
1440  /// this block before this number of iterations, but may exit via another
1441  /// block.
1442  const SCEV *getExact(const BasicBlock *ExitingBlock,
1443  ScalarEvolution *SE) const;
1444 
1445  /// Get the constant max backedge taken count for the loop.
1446  const SCEV *getConstantMax(ScalarEvolution *SE) const;
1447 
1448  /// Get the constant max backedge taken count for the particular loop exit.
1449  const SCEV *getConstantMax(const BasicBlock *ExitingBlock,
1450  ScalarEvolution *SE) const;
1451 
1452  /// Get the symbolic max backedge taken count for the loop.
1453  const SCEV *getSymbolicMax(const Loop *L, ScalarEvolution *SE);
1454 
1455  /// Return true if the number of times this backedge is taken is either the
1456  /// value returned by getConstantMax or zero.
1457  bool isConstantMaxOrZero(ScalarEvolution *SE) const;
1458  };
1459 
1460  /// Cache the backedge-taken count of the loops for this function as they
1461  /// are computed.
1462  DenseMap<const Loop *, BackedgeTakenInfo> BackedgeTakenCounts;
1463 
1464  /// Cache the predicated backedge-taken count of the loops for this
1465  /// function as they are computed.
1466  DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts;
1467 
1468  /// Loops whose backedge taken counts directly use this non-constant SCEV.
1469  DenseMap<const SCEV *, SmallPtrSet<PointerIntPair<const Loop *, 1, bool>, 4>>
1470  BECountUsers;
1471 
1472  /// This map contains entries for all of the PHI instructions that we
1473  /// attempt to compute constant evolutions for. This allows us to avoid
1474  /// potentially expensive recomputation of these properties. An instruction
1475  /// maps to null if we are unable to compute its exit value.
1476  DenseMap<PHINode *, Constant *> ConstantEvolutionLoopExitValue;
1477 
1478  /// This map contains entries for all the expressions that we attempt to
1479  /// compute getSCEVAtScope information for, which can be expensive in
1480  /// extreme cases.
1481  DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1482  ValuesAtScopes;
1483 
1484  /// Reverse map for invalidation purposes: Stores of which SCEV and which
1485  /// loop this is the value-at-scope of.
1486  DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1487  ValuesAtScopesUsers;
1488 
1489  /// Memoized computeLoopDisposition results.
1490  DenseMap<const SCEV *,
1491  SmallVector<PointerIntPair<const Loop *, 2, LoopDisposition>, 2>>
1492  LoopDispositions;
1493 
1494  struct LoopProperties {
1495  /// Set to true if the loop contains no instruction that can abnormally exit
1496  /// the loop (i.e. via throwing an exception, by terminating the thread
1497  /// cleanly or by infinite looping in a called function). Strictly
1498  /// speaking, the last one is not leaving the loop, but is identical to
1499  /// leaving the loop for reasoning about undefined behavior.
1500  bool HasNoAbnormalExits;
1501 
1502  /// Set to true if the loop contains no instruction that can have side
1503  /// effects (i.e. via throwing an exception, volatile or atomic access).
1504  bool HasNoSideEffects;
1505  };
1506 
1507  /// Cache for \c getLoopProperties.
1508  DenseMap<const Loop *, LoopProperties> LoopPropertiesCache;
1509 
1510  /// Return a \c LoopProperties instance for \p L, creating one if necessary.
1511  LoopProperties getLoopProperties(const Loop *L);
1512 
1513  bool loopHasNoSideEffects(const Loop *L) {
1514  return getLoopProperties(L).HasNoSideEffects;
1515  }
1516 
1517  /// Compute a LoopDisposition value.
1518  LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L);
1519 
1520  /// Memoized computeBlockDisposition results.
1521  DenseMap<
1522  const SCEV *,
1523  SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>>
1524  BlockDispositions;
1525 
1526  /// Compute a BlockDisposition value.
1527  BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB);
1528 
1529  /// Stores all SCEV that use a given SCEV as its direct operand.
1530  DenseMap<const SCEV *, SmallPtrSet<const SCEV *, 8> > SCEVUsers;
1531 
1532  /// Memoized results from getRange
1533  DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
1534 
1535  /// Memoized results from getRange
1536  DenseMap<const SCEV *, ConstantRange> SignedRanges;
1537 
1538  /// Used to parameterize getRange
1539  enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED };
1540 
1541  /// Set the memoized range for the given SCEV.
1542  const ConstantRange &setRange(const SCEV *S, RangeSignHint Hint,
1543  ConstantRange CR) {
1544  DenseMap<const SCEV *, ConstantRange> &Cache =
1545  Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges;
1546 
1547  auto Pair = Cache.try_emplace(S, std::move(CR));
1548  if (!Pair.second)
1549  Pair.first->second = std::move(CR);
1550  return Pair.first->second;
1551  }
1552 
1553  /// Determine the range for a particular SCEV.
1554  /// NOTE: This returns a reference to an entry in a cache. It must be
1555  /// copied if its needed for longer.
1556  const ConstantRange &getRangeRef(const SCEV *S, RangeSignHint Hint);
1557 
1558  /// Determines the range for the affine SCEVAddRecExpr {\p Start,+,\p Step}.
1559  /// Helper for \c getRange.
1560  ConstantRange getRangeForAffineAR(const SCEV *Start, const SCEV *Step,
1561  const SCEV *MaxBECount, unsigned BitWidth);
1562 
1563  /// Determines the range for the affine non-self-wrapping SCEVAddRecExpr {\p
1564  /// Start,+,\p Step}<nw>.
1565  ConstantRange getRangeForAffineNoSelfWrappingAR(const SCEVAddRecExpr *AddRec,
1566  const SCEV *MaxBECount,
1567  unsigned BitWidth,
1568  RangeSignHint SignHint);
1569 
1570  /// Try to compute a range for the affine SCEVAddRecExpr {\p Start,+,\p
1571  /// Step} by "factoring out" a ternary expression from the add recurrence.
1572  /// Helper called by \c getRange.
1573  ConstantRange getRangeViaFactoring(const SCEV *Start, const SCEV *Step,
1574  const SCEV *MaxBECount, unsigned BitWidth);
1575 
1576  /// If the unknown expression U corresponds to a simple recurrence, return
1577  /// a constant range which represents the entire recurrence. Note that
1578  /// *add* recurrences with loop invariant steps aren't represented by
1579  /// SCEVUnknowns and thus don't use this mechanism.
1580  ConstantRange getRangeForUnknownRecurrence(const SCEVUnknown *U);
1581 
1582  /// We know that there is no SCEV for the specified value. Analyze the
1583  /// expression recursively.
1584  const SCEV *createSCEV(Value *V);
1585 
1586  /// We know that there is no SCEV for the specified value. Create a new SCEV
1587  /// for \p V iteratively.
1588  const SCEV *createSCEVIter(Value *V);
1589  /// Collect operands of \p V for which SCEV expressions should be constructed
1590  /// first. Returns a SCEV directly if it can be constructed trivially for \p
1591  /// V.
1592  const SCEV *getOperandsToCreate(Value *V, SmallVectorImpl<Value *> &Ops);
1593 
1594  /// Provide the special handling we need to analyze PHI SCEVs.
1595  const SCEV *createNodeForPHI(PHINode *PN);
1596 
1597  /// Helper function called from createNodeForPHI.
1598  const SCEV *createAddRecFromPHI(PHINode *PN);
1599 
1600  /// A helper function for createAddRecFromPHI to handle simple cases.
1601  const SCEV *createSimpleAffineAddRec(PHINode *PN, Value *BEValueV,
1602  Value *StartValueV);
1603 
1604  /// Helper function called from createNodeForPHI.
1605  const SCEV *createNodeFromSelectLikePHI(PHINode *PN);
1606 
1607  /// Provide special handling for a select-like instruction (currently this
1608  /// is either a select instruction or a phi node). \p I is the instruction
1609  /// being processed, and it is assumed equivalent to "Cond ? TrueVal :
1610  /// FalseVal".
1611  const SCEV *createNodeForSelectOrPHIInstWithICmpInstCond(Instruction *I,
1612  ICmpInst *Cond,
1613  Value *TrueVal,
1614  Value *FalseVal);
1615 
1616  /// See if we can model this select-like instruction via umin_seq expression.
1617  const SCEV *createNodeForSelectOrPHIViaUMinSeq(Value *I, Value *Cond,
1618  Value *TrueVal,
1619  Value *FalseVal);
1620 
1621  /// Given a value \p V, which is a select-like instruction (currently this is
1622  /// either a select instruction or a phi node), which is assumed equivalent to
1623  /// Cond ? TrueVal : FalseVal
1624  /// see if we can model it as a SCEV expression.
1625  const SCEV *createNodeForSelectOrPHI(Value *V, Value *Cond, Value *TrueVal,
1626  Value *FalseVal);
1627 
1628  /// Provide the special handling we need to analyze GEP SCEVs.
1629  const SCEV *createNodeForGEP(GEPOperator *GEP);
1630 
1631  /// Implementation code for getSCEVAtScope; called at most once for each
1632  /// SCEV+Loop pair.
1633  const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L);
1634 
1635  /// Return the BackedgeTakenInfo for the given loop, lazily computing new
1636  /// values if the loop hasn't been analyzed yet. The returned result is
1637  /// guaranteed not to be predicated.
1638  BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L);
1639 
1640  /// Similar to getBackedgeTakenInfo, but will add predicates as required
1641  /// with the purpose of returning complete information.
1642  const BackedgeTakenInfo &getPredicatedBackedgeTakenInfo(const Loop *L);
1643 
1644  /// Compute the number of times the specified loop will iterate.
1645  /// If AllowPredicates is set, we will create new SCEV predicates as
1646  /// necessary in order to return an exact answer.
1647  BackedgeTakenInfo computeBackedgeTakenCount(const Loop *L,
1648  bool AllowPredicates = false);
1649 
1650  /// Compute the number of times the backedge of the specified loop will
1651  /// execute if it exits via the specified block. If AllowPredicates is set,
1652  /// this call will try to use a minimal set of SCEV predicates in order to
1653  /// return an exact answer.
1654  ExitLimit computeExitLimit(const Loop *L, BasicBlock *ExitingBlock,
1655  bool AllowPredicates = false);
1656 
1657  /// Compute the number of times the backedge of the specified loop will
1658  /// execute if its exit condition were a conditional branch of ExitCond.
1659  ///
1660  /// \p ControlsExit is true if ExitCond directly controls the exit
1661  /// branch. In this case, we can assume that the loop exits only if the
1662  /// condition is true and can infer that failing to meet the condition prior
1663  /// to integer wraparound results in undefined behavior.
1664  ///
1665  /// If \p AllowPredicates is set, this call will try to use a minimal set of
1666  /// SCEV predicates in order to return an exact answer.
1667  ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond,
1668  bool ExitIfTrue, bool ControlsExit,
1669  bool AllowPredicates = false);
1670 
1671  /// Return a symbolic upper bound for the backedge taken count of the loop.
1672  /// This is more general than getConstantMaxBackedgeTakenCount as it returns
1673  /// an arbitrary expression as opposed to only constants.
1674  const SCEV *computeSymbolicMaxBackedgeTakenCount(const Loop *L);
1675 
1676  // Helper functions for computeExitLimitFromCond to avoid exponential time
1677  // complexity.
1678 
1679  class ExitLimitCache {
1680  // It may look like we need key on the whole (L, ExitIfTrue, ControlsExit,
1681  // AllowPredicates) tuple, but recursive calls to
1682  // computeExitLimitFromCondCached from computeExitLimitFromCondImpl only
1683  // vary the in \c ExitCond and \c ControlsExit parameters. We remember the
1684  // initial values of the other values to assert our assumption.
1685  SmallDenseMap<PointerIntPair<Value *, 1>, ExitLimit> TripCountMap;
1686 
1687  const Loop *L;
1688  bool ExitIfTrue;
1689  bool AllowPredicates;
1690 
1691  public:
1692  ExitLimitCache(const Loop *L, bool ExitIfTrue, bool AllowPredicates)
1693  : L(L), ExitIfTrue(ExitIfTrue), AllowPredicates(AllowPredicates) {}
1694 
1695  Optional<ExitLimit> find(const Loop *L, Value *ExitCond, bool ExitIfTrue,
1696  bool ControlsExit, bool AllowPredicates);
1697 
1698  void insert(const Loop *L, Value *ExitCond, bool ExitIfTrue,
1699  bool ControlsExit, bool AllowPredicates, const ExitLimit &EL);
1700  };
1701 
1702  using ExitLimitCacheTy = ExitLimitCache;
1703 
1704  ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache,
1705  const Loop *L, Value *ExitCond,
1706  bool ExitIfTrue,
1707  bool ControlsExit,
1708  bool AllowPredicates);
1709  ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache, const Loop *L,
1710  Value *ExitCond, bool ExitIfTrue,
1711  bool ControlsExit,
1712  bool AllowPredicates);
1713  Optional<ScalarEvolution::ExitLimit>
1714  computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache, const Loop *L,
1715  Value *ExitCond, bool ExitIfTrue,
1716  bool ControlsExit, bool AllowPredicates);
1717 
1718  /// Compute the number of times the backedge of the specified loop will
1719  /// execute if its exit condition were a conditional branch of the ICmpInst
1720  /// ExitCond and ExitIfTrue. If AllowPredicates is set, this call will try
1721  /// to use a minimal set of SCEV predicates in order to return an exact
1722  /// answer.
1723  ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond,
1724  bool ExitIfTrue,
1725  bool IsSubExpr,
1726  bool AllowPredicates = false);
1727 
1728  /// Variant of previous which takes the components representing an ICmp
1729  /// as opposed to the ICmpInst itself. Note that the prior version can
1730  /// return more precise results in some cases and is preferred when caller
1731  /// has a materialized ICmp.
1732  ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst::Predicate Pred,
1733  const SCEV *LHS, const SCEV *RHS,
1734  bool IsSubExpr,
1735  bool AllowPredicates = false);
1736 
1737  /// Compute the number of times the backedge of the specified loop will
1738  /// execute if its exit condition were a switch with a single exiting case
1739  /// to ExitingBB.
1740  ExitLimit computeExitLimitFromSingleExitSwitch(const Loop *L,
1741  SwitchInst *Switch,
1742  BasicBlock *ExitingBB,
1743  bool IsSubExpr);
1744 
1745  /// Compute the exit limit of a loop that is controlled by a
1746  /// "(IV >> 1) != 0" type comparison. We cannot compute the exact trip
1747  /// count in these cases (since SCEV has no way of expressing them), but we
1748  /// can still sometimes compute an upper bound.
1749  ///
1750  /// Return an ExitLimit for a loop whose backedge is guarded by `LHS Pred
1751  /// RHS`.
1752  ExitLimit computeShiftCompareExitLimit(Value *LHS, Value *RHS, const Loop *L,
1753  ICmpInst::Predicate Pred);
1754 
1755  /// If the loop is known to execute a constant number of times (the
1756  /// condition evolves only from constants), try to evaluate a few iterations
1757  /// of the loop until we get the exit condition gets a value of ExitWhen
1758  /// (true or false). If we cannot evaluate the exit count of the loop,
1759  /// return CouldNotCompute.
1760  const SCEV *computeExitCountExhaustively(const Loop *L, Value *Cond,
1761  bool ExitWhen);
1762 
1763  /// Return the number of times an exit condition comparing the specified
1764  /// value to zero will execute. If not computable, return CouldNotCompute.
1765  /// If AllowPredicates is set, this call will try to use a minimal set of
1766  /// SCEV predicates in order to return an exact answer.
1767  ExitLimit howFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr,
1768  bool AllowPredicates = false);
1769 
1770  /// Return the number of times an exit condition checking the specified
1771  /// value for nonzero will execute. If not computable, return
1772  /// CouldNotCompute.
1773  ExitLimit howFarToNonZero(const SCEV *V, const Loop *L);
1774 
1775  /// Return the number of times an exit condition containing the specified
1776  /// less-than comparison will execute. If not computable, return
1777  /// CouldNotCompute.
1778  ///
1779  /// \p isSigned specifies whether the less-than is signed.
1780  ///
1781  /// \p ControlsExit is true when the LHS < RHS condition directly controls
1782  /// the branch (loops exits only if condition is true). In this case, we can
1783  /// use NoWrapFlags to skip overflow checks.
1784  ///
1785  /// If \p AllowPredicates is set, this call will try to use a minimal set of
1786  /// SCEV predicates in order to return an exact answer.
1787  ExitLimit howManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
1788  bool isSigned, bool ControlsExit,
1789  bool AllowPredicates = false);
1790 
1791  ExitLimit howManyGreaterThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
1792  bool isSigned, bool IsSubExpr,
1793  bool AllowPredicates = false);
1794 
1795  /// Return a predecessor of BB (which may not be an immediate predecessor)
1796  /// which has exactly one successor from which BB is reachable, or null if
1797  /// no such block is found.
1798  std::pair<const BasicBlock *, const BasicBlock *>
1799  getPredecessorWithUniqueSuccessorForBB(const BasicBlock *BB) const;
1800 
1801  /// Test whether the condition described by Pred, LHS, and RHS is true
1802  /// whenever the given FoundCondValue value evaluates to true in given
1803  /// Context. If Context is nullptr, then the found predicate is true
1804  /// everywhere. LHS and FoundLHS may have different type width.
1805  bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
1806  const Value *FoundCondValue, bool Inverse,
1807  const Instruction *Context = nullptr);
1808 
1809  /// Test whether the condition described by Pred, LHS, and RHS is true
1810  /// whenever the given FoundCondValue value evaluates to true in given
1811  /// Context. If Context is nullptr, then the found predicate is true
1812  /// everywhere. LHS and FoundLHS must have same type width.
1813  bool isImpliedCondBalancedTypes(ICmpInst::Predicate Pred, const SCEV *LHS,
1814  const SCEV *RHS,
1815  ICmpInst::Predicate FoundPred,
1816  const SCEV *FoundLHS, const SCEV *FoundRHS,
1817  const Instruction *CtxI);
1818 
1819  /// Test whether the condition described by Pred, LHS, and RHS is true
1820  /// whenever the condition described by FoundPred, FoundLHS, FoundRHS is
1821  /// true in given Context. If Context is nullptr, then the found predicate is
1822  /// true everywhere.
1823  bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
1824  ICmpInst::Predicate FoundPred, const SCEV *FoundLHS,
1825  const SCEV *FoundRHS,
1826  const Instruction *Context = nullptr);
1827 
1828  /// Test whether the condition described by Pred, LHS, and RHS is true
1829  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1830  /// true in given Context. If Context is nullptr, then the found predicate is
1831  /// true everywhere.
1832  bool isImpliedCondOperands(ICmpInst::Predicate Pred, const SCEV *LHS,
1833  const SCEV *RHS, const SCEV *FoundLHS,
1834  const SCEV *FoundRHS,
1835  const Instruction *Context = nullptr);
1836 
1837  /// Test whether the condition described by Pred, LHS, and RHS is true
1838  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1839  /// true. Here LHS is an operation that includes FoundLHS as one of its
1840  /// arguments.
1841  bool isImpliedViaOperations(ICmpInst::Predicate Pred,
1842  const SCEV *LHS, const SCEV *RHS,
1843  const SCEV *FoundLHS, const SCEV *FoundRHS,
1844  unsigned Depth = 0);
1845 
1846  /// Test whether the condition described by Pred, LHS, and RHS is true.
1847  /// Use only simple non-recursive types of checks, such as range analysis etc.
1848  bool isKnownViaNonRecursiveReasoning(ICmpInst::Predicate Pred,
1849  const SCEV *LHS, const SCEV *RHS);
1850 
1851  /// Test whether the condition described by Pred, LHS, and RHS is true
1852  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1853  /// true.
1854  bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, const SCEV *LHS,
1855  const SCEV *RHS, const SCEV *FoundLHS,
1856  const SCEV *FoundRHS);
1857 
1858  /// Test whether the condition described by Pred, LHS, and RHS is true
1859  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1860  /// true. Utility function used by isImpliedCondOperands. Tries to get
1861  /// cases like "X `sgt` 0 => X - 1 `sgt` -1".
1862  bool isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred, const SCEV *LHS,
1863  const SCEV *RHS, const SCEV *FoundLHS,
1864  const SCEV *FoundRHS);
1865 
1866  /// Return true if the condition denoted by \p LHS \p Pred \p RHS is implied
1867  /// by a call to @llvm.experimental.guard in \p BB.
1868  bool isImpliedViaGuard(const BasicBlock *BB, ICmpInst::Predicate Pred,
1869  const SCEV *LHS, const SCEV *RHS);
1870 
1871  /// Test whether the condition described by Pred, LHS, and RHS is true
1872  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1873  /// true.
1874  ///
1875  /// This routine tries to rule out certain kinds of integer overflow, and
1876  /// then tries to reason about arithmetic properties of the predicates.
1877  bool isImpliedCondOperandsViaNoOverflow(ICmpInst::Predicate Pred,
1878  const SCEV *LHS, const SCEV *RHS,
1879  const SCEV *FoundLHS,
1880  const SCEV *FoundRHS);
1881 
1882  /// Test whether the condition described by Pred, LHS, and RHS is true
1883  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1884  /// true.
1885  ///
1886  /// This routine tries to weaken the known condition basing on fact that
1887  /// FoundLHS is an AddRec.
1888  bool isImpliedCondOperandsViaAddRecStart(ICmpInst::Predicate Pred,
1889  const SCEV *LHS, const SCEV *RHS,
1890  const SCEV *FoundLHS,
1891  const SCEV *FoundRHS,
1892  const Instruction *CtxI);
1893 
1894  /// Test whether the condition described by Pred, LHS, and RHS is true
1895  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1896  /// true.
1897  ///
1898  /// This routine tries to figure out predicate for Phis which are SCEVUnknown
1899  /// if it is true for every possible incoming value from their respective
1900  /// basic blocks.
1901  bool isImpliedViaMerge(ICmpInst::Predicate Pred,
1902  const SCEV *LHS, const SCEV *RHS,
1903  const SCEV *FoundLHS, const SCEV *FoundRHS,
1904  unsigned Depth);
1905 
1906  /// Test whether the condition described by Pred, LHS, and RHS is true
1907  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1908  /// true.
1909  ///
1910  /// This routine tries to reason about shifts.
1911  bool isImpliedCondOperandsViaShift(ICmpInst::Predicate Pred, const SCEV *LHS,
1912  const SCEV *RHS, const SCEV *FoundLHS,
1913  const SCEV *FoundRHS);
1914 
1915  /// If we know that the specified Phi is in the header of its containing
1916  /// loop, we know the loop executes a constant number of times, and the PHI
1917  /// node is just a recurrence involving constants, fold it.
1918  Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt &BEs,
1919  const Loop *L);
1920 
1921  /// Test if the given expression is known to satisfy the condition described
1922  /// by Pred and the known constant ranges of LHS and RHS.
1923  bool isKnownPredicateViaConstantRanges(ICmpInst::Predicate Pred,
1924  const SCEV *LHS, const SCEV *RHS);
1925 
1926  /// Try to prove the condition described by "LHS Pred RHS" by ruling out
1927  /// integer overflow.
1928  ///
1929  /// For instance, this will return true for "A s< (A + C)<nsw>" if C is
1930  /// positive.
1931  bool isKnownPredicateViaNoOverflow(ICmpInst::Predicate Pred, const SCEV *LHS,
1932  const SCEV *RHS);
1933 
1934  /// Try to split Pred LHS RHS into logical conjunctions (and's) and try to
1935  /// prove them individually.
1936  bool isKnownPredicateViaSplitting(ICmpInst::Predicate Pred, const SCEV *LHS,
1937  const SCEV *RHS);
1938 
1939  /// Try to match the Expr as "(L + R)<Flags>".
1940  bool splitBinaryAdd(const SCEV *Expr, const SCEV *&L, const SCEV *&R,
1941  SCEV::NoWrapFlags &Flags);
1942 
1943  /// Forget predicated/non-predicated backedge taken counts for the given loop.
1944  void forgetBackedgeTakenCounts(const Loop *L, bool Predicated);
1945 
1946  /// Drop memoized information for all \p SCEVs.
1947  void forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs);
1948 
1949  /// Helper for forgetMemoizedResults.
1950  void forgetMemoizedResultsImpl(const SCEV *S);
1951 
1952  /// Return an existing SCEV for V if there is one, otherwise return nullptr.
1953  const SCEV *getExistingSCEV(Value *V);
1954 
1955  /// Erase Value from ValueExprMap and ExprValueMap.
1956  void eraseValueFromMap(Value *V);
1957 
1958  /// Insert V to S mapping into ValueExprMap and ExprValueMap.
1959  void insertValueToMap(Value *V, const SCEV *S);
1960 
1961  /// Return false iff given SCEV contains a SCEVUnknown with NULL value-
1962  /// pointer.
1963  bool checkValidity(const SCEV *S) const;
1964 
1965  /// Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be
1966  /// equal to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}. This is
1967  /// equivalent to proving no signed (resp. unsigned) wrap in
1968  /// {`Start`,+,`Step`} if `ExtendOpTy` is `SCEVSignExtendExpr`
1969  /// (resp. `SCEVZeroExtendExpr`).
1970  template <typename ExtendOpTy>
1971  bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step,
1972  const Loop *L);
1973 
1974  /// Try to prove NSW or NUW on \p AR relying on ConstantRange manipulation.
1975  SCEV::NoWrapFlags proveNoWrapViaConstantRanges(const SCEVAddRecExpr *AR);
1976 
1977  /// Try to prove NSW on \p AR by proving facts about conditions known on
1978  /// entry and backedge.
1979  SCEV::NoWrapFlags proveNoSignedWrapViaInduction(const SCEVAddRecExpr *AR);
1980 
1981  /// Try to prove NUW on \p AR by proving facts about conditions known on
1982  /// entry and backedge.
1983  SCEV::NoWrapFlags proveNoUnsignedWrapViaInduction(const SCEVAddRecExpr *AR);
1984 
1985  Optional<MonotonicPredicateType>
1986  getMonotonicPredicateTypeImpl(const SCEVAddRecExpr *LHS,
1987  ICmpInst::Predicate Pred);
1988 
1989  /// Return SCEV no-wrap flags that can be proven based on reasoning about
1990  /// how poison produced from no-wrap flags on this value (e.g. a nuw add)
1991  /// would trigger undefined behavior on overflow.
1992  SCEV::NoWrapFlags getNoWrapFlagsFromUB(const Value *V);
1993 
1994  /// Return a scope which provides an upper bound on the defining scope of
1995  /// 'S'. Specifically, return the first instruction in said bounding scope.
1996  /// Return nullptr if the scope is trivial (function entry).
1997  /// (See scope definition rules associated with flag discussion above)
1998  const Instruction *getNonTrivialDefiningScopeBound(const SCEV *S);
1999 
2000  /// Return a scope which provides an upper bound on the defining scope for
2001  /// a SCEV with the operands in Ops. The outparam Precise is set if the
2002  /// bound found is a precise bound (i.e. must be the defining scope.)
2003  const Instruction *getDefiningScopeBound(ArrayRef<const SCEV *> Ops,
2004  bool &Precise);
2005 
2006  /// Wrapper around the above for cases which don't care if the bound
2007  /// is precise.
2008  const Instruction *getDefiningScopeBound(ArrayRef<const SCEV *> Ops);
2009 
2010  /// Given two instructions in the same function, return true if we can
2011  /// prove B must execute given A executes.
2012  bool isGuaranteedToTransferExecutionTo(const Instruction *A,
2013  const Instruction *B);
2014 
2015  /// Return true if the SCEV corresponding to \p I is never poison. Proving
2016  /// this is more complex than proving that just \p I is never poison, since
2017  /// SCEV commons expressions across control flow, and you can have cases
2018  /// like:
2019  ///
2020  /// idx0 = a + b;
2021  /// ptr[idx0] = 100;
2022  /// if (<condition>) {
2023  /// idx1 = a +nsw b;
2024  /// ptr[idx1] = 200;
2025  /// }
2026  ///
2027  /// where the SCEV expression (+ a b) is guaranteed to not be poison (and
2028  /// hence not sign-overflow) only if "<condition>" is true. Since both
2029  /// `idx0` and `idx1` will be mapped to the same SCEV expression, (+ a b),
2030  /// it is not okay to annotate (+ a b) with <nsw> in the above example.
2031  bool isSCEVExprNeverPoison(const Instruction *I);
2032 
2033  /// This is like \c isSCEVExprNeverPoison but it specifically works for
2034  /// instructions that will get mapped to SCEV add recurrences. Return true
2035  /// if \p I will never generate poison under the assumption that \p I is an
2036  /// add recurrence on the loop \p L.
2037  bool isAddRecNeverPoison(const Instruction *I, const Loop *L);
2038 
2039  /// Similar to createAddRecFromPHI, but with the additional flexibility of
2040  /// suggesting runtime overflow checks in case casts are encountered.
2041  /// If successful, the analysis records that for this loop, \p SymbolicPHI,
2042  /// which is the UnknownSCEV currently representing the PHI, can be rewritten
2043  /// into an AddRec, assuming some predicates; The function then returns the
2044  /// AddRec and the predicates as a pair, and caches this pair in
2045  /// PredicatedSCEVRewrites.
2046  /// If the analysis is not successful, a mapping from the \p SymbolicPHI to
2047  /// itself (with no predicates) is recorded, and a nullptr with an empty
2048  /// predicates vector is returned as a pair.
2049  Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2050  createAddRecFromPHIWithCastsImpl(const SCEVUnknown *SymbolicPHI);
2051 
2052  /// Compute the maximum backedge count based on the range of values
2053  /// permitted by Start, End, and Stride. This is for loops of the form
2054  /// {Start, +, Stride} LT End.
2055  ///
2056  /// Preconditions:
2057  /// * the induction variable is known to be positive.
2058  /// * the induction variable is assumed not to overflow (i.e. either it
2059  /// actually doesn't, or we'd have to immediately execute UB)
2060  /// We *don't* assert these preconditions so please be careful.
2061  const SCEV *computeMaxBECountForLT(const SCEV *Start, const SCEV *Stride,
2062  const SCEV *End, unsigned BitWidth,
2063  bool IsSigned);
2064 
2065  /// Verify if an linear IV with positive stride can overflow when in a
2066  /// less-than comparison, knowing the invariant term of the comparison,
2067  /// the stride.
2068  bool canIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, bool IsSigned);
2069 
2070  /// Verify if an linear IV with negative stride can overflow when in a
2071  /// greater-than comparison, knowing the invariant term of the comparison,
2072  /// the stride.
2073  bool canIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, bool IsSigned);
2074 
2075  /// Get add expr already created or create a new one.
2076  const SCEV *getOrCreateAddExpr(ArrayRef<const SCEV *> Ops,
2077  SCEV::NoWrapFlags Flags);
2078 
2079  /// Get mul expr already created or create a new one.
2080  const SCEV *getOrCreateMulExpr(ArrayRef<const SCEV *> Ops,
2081  SCEV::NoWrapFlags Flags);
2082 
2083  // Get addrec expr already created or create a new one.
2084  const SCEV *getOrCreateAddRecExpr(ArrayRef<const SCEV *> Ops,
2085  const Loop *L, SCEV::NoWrapFlags Flags);
2086 
2087  /// Return x if \p Val is f(x) where f is a 1-1 function.
2088  const SCEV *stripInjectiveFunctions(const SCEV *Val) const;
2089 
2090  /// Find all of the loops transitively used in \p S, and fill \p LoopsUsed.
2091  /// A loop is considered "used" by an expression if it contains
2092  /// an add rec on said loop.
2093  void getUsedLoops(const SCEV *S, SmallPtrSetImpl<const Loop *> &LoopsUsed);
2094 
2095  /// Try to match the pattern generated by getURemExpr(A, B). If successful,
2096  /// Assign A and B to LHS and RHS, respectively.
2097  bool matchURem(const SCEV *Expr, const SCEV *&LHS, const SCEV *&RHS);
2098 
2099  /// Look for a SCEV expression with type `SCEVType` and operands `Ops` in
2100  /// `UniqueSCEVs`. Return if found, else nullptr.
2101  SCEV *findExistingSCEVInCache(SCEVTypes SCEVType, ArrayRef<const SCEV *> Ops);
2102 
2103  /// Get reachable blocks in this function, making limited use of SCEV
2104  /// reasoning about conditions.
2105  void getReachableBlocks(SmallPtrSetImpl<BasicBlock *> &Reachable,
2106  Function &F);
2107 
2108  FoldingSet<SCEV> UniqueSCEVs;
2109  FoldingSet<SCEVPredicate> UniquePreds;
2110  BumpPtrAllocator SCEVAllocator;
2111 
2112  /// This maps loops to a list of addrecs that directly use said loop.
2113  DenseMap<const Loop *, SmallVector<const SCEVAddRecExpr *, 4>> LoopUsers;
2114 
2115  /// Cache tentative mappings from UnknownSCEVs in a Loop, to a SCEV expression
2116  /// they can be rewritten into under certain predicates.
2117  DenseMap<std::pair<const SCEVUnknown *, const Loop *>,
2118  std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2119  PredicatedSCEVRewrites;
2120 
2121  /// Set of AddRecs for which proving NUW via an induction has already been
2122  /// tried.
2123  SmallPtrSet<const SCEVAddRecExpr *, 16> UnsignedWrapViaInductionTried;
2124 
2125  /// Set of AddRecs for which proving NSW via an induction has already been
2126  /// tried.
2127  SmallPtrSet<const SCEVAddRecExpr *, 16> SignedWrapViaInductionTried;
2128 
2129  /// The head of a linked list of all SCEVUnknown values that have been
2130  /// allocated. This is used by releaseMemory to locate them all and call
2131  /// their destructors.
2132  SCEVUnknown *FirstUnknown = nullptr;
2133 };
2134 
2135 /// Analysis pass that exposes the \c ScalarEvolution for a function.
2137  : public AnalysisInfoMixin<ScalarEvolutionAnalysis> {
2139 
2140  static AnalysisKey Key;
2141 
2142 public:
2144 
2146 };
2147 
2148 /// Verifier pass for the \c ScalarEvolutionAnalysis results.
2150  : public PassInfoMixin<ScalarEvolutionVerifierPass> {
2151 public:
2153 };
2154 
2155 /// Printer pass for the \c ScalarEvolutionAnalysis results.
2157  : public PassInfoMixin<ScalarEvolutionPrinterPass> {
2158  raw_ostream &OS;
2159 
2160 public:
2161  explicit ScalarEvolutionPrinterPass(raw_ostream &OS) : OS(OS) {}
2162 
2164 };
2165 
2167  std::unique_ptr<ScalarEvolution> SE;
2168 
2169 public:
2170  static char ID;
2171 
2173 
2174  ScalarEvolution &getSE() { return *SE; }
2175  const ScalarEvolution &getSE() const { return *SE; }
2176 
2177  bool runOnFunction(Function &F) override;
2178  void releaseMemory() override;
2179  void getAnalysisUsage(AnalysisUsage &AU) const override;
2180  void print(raw_ostream &OS, const Module * = nullptr) const override;
2181  void verifyAnalysis() const override;
2182 };
2183 
2184 /// An interface layer with SCEV used to manage how we see SCEV expressions
2185 /// for values in the context of existing predicates. We can add new
2186 /// predicates, but we cannot remove them.
2187 ///
2188 /// This layer has multiple purposes:
2189 /// - provides a simple interface for SCEV versioning.
2190 /// - guarantees that the order of transformations applied on a SCEV
2191 /// expression for a single Value is consistent across two different
2192 /// getSCEV calls. This means that, for example, once we've obtained
2193 /// an AddRec expression for a certain value through expression
2194 /// rewriting, we will continue to get an AddRec expression for that
2195 /// Value.
2196 /// - lowers the number of expression rewrites.
2198 public:
2200 
2201  const SCEVPredicate &getPredicate() const;
2202 
2203  /// Returns the SCEV expression of V, in the context of the current SCEV
2204  /// predicate. The order of transformations applied on the expression of V
2205  /// returned by ScalarEvolution is guaranteed to be preserved, even when
2206  /// adding new predicates.
2207  const SCEV *getSCEV(Value *V);
2208 
2209  /// Get the (predicated) backedge count for the analyzed loop.
2210  const SCEV *getBackedgeTakenCount();
2211 
2212  /// Adds a new predicate.
2213  void addPredicate(const SCEVPredicate &Pred);
2214 
2215  /// Attempts to produce an AddRecExpr for V by adding additional SCEV
2216  /// predicates. If we can't transform the expression into an AddRecExpr we
2217  /// return nullptr and not add additional SCEV predicates to the current
2218  /// context.
2219  const SCEVAddRecExpr *getAsAddRec(Value *V);
2220 
2221  /// Proves that V doesn't overflow by adding SCEV predicate.
2223 
2224  /// Returns true if we've proved that V doesn't wrap by means of a SCEV
2225  /// predicate.
2227 
2228  /// Returns the ScalarEvolution analysis used.
2229  ScalarEvolution *getSE() const { return &SE; }
2230 
2231  /// We need to explicitly define the copy constructor because of FlagsMap.
2233 
2234  /// Print the SCEV mappings done by the Predicated Scalar Evolution.
2235  /// The printed text is indented by \p Depth.
2236  void print(raw_ostream &OS, unsigned Depth) const;
2237 
2238  /// Check if \p AR1 and \p AR2 are equal, while taking into account
2239  /// Equal predicates in Preds.
2240  bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1,
2241  const SCEVAddRecExpr *AR2) const;
2242 
2243 private:
2244  /// Increments the version number of the predicate. This needs to be called
2245  /// every time the SCEV predicate changes.
2246  void updateGeneration();
2247 
2248  /// Holds a SCEV and the version number of the SCEV predicate used to
2249  /// perform the rewrite of the expression.
2250  using RewriteEntry = std::pair<unsigned, const SCEV *>;
2251 
2252  /// Maps a SCEV to the rewrite result of that SCEV at a certain version
2253  /// number. If this number doesn't match the current Generation, we will
2254  /// need to do a rewrite. To preserve the transformation order of previous
2255  /// rewrites, we will rewrite the previous result instead of the original
2256  /// SCEV.
2258 
2259  /// Records what NoWrap flags we've added to a Value *.
2261 
2262  /// The ScalarEvolution analysis.
2263  ScalarEvolution &SE;
2264 
2265  /// The analyzed Loop.
2266  const Loop &L;
2267 
2268  /// The SCEVPredicate that forms our context. We will rewrite all
2269  /// expressions assuming that this predicate true.
2270  std::unique_ptr<SCEVUnionPredicate> Preds;
2271 
2272  /// Marks the version of the SCEV predicate used. When rewriting a SCEV
2273  /// expression we mark it with the version of the predicate. We use this to
2274  /// figure out if the predicate has changed from the last rewrite of the
2275  /// SCEV. If so, we need to perform a new rewrite.
2276  unsigned Generation = 0;
2277 
2278  /// The backedge taken count.
2279  const SCEV *BackedgeCount = nullptr;
2280 };
2281 
2282 } // end namespace llvm
2283 
2284 #endif // LLVM_ANALYSIS_SCALAREVOLUTION_H
llvm::SCEVUnionPredicate::SCEVUnionPredicate
SCEVUnionPredicate(ArrayRef< const SCEVPredicate * > Preds)
Union predicates don't get cached so create a dummy set ID for it.
Definition: ScalarEvolution.cpp:14357
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::ScalarEvolution::getContext
LLVMContext & getContext() const
Definition: ScalarEvolution.h:491
llvm::FoldingSetTrait< SCEVPredicate >::Profile
static void Profile(const SCEVPredicate &X, FoldingSetNodeID &ID)
Definition: ScalarEvolution.h:261
llvm::SCEVWrapPredicate::IncrementNoWrapMask
@ IncrementNoWrapMask
Definition: ScalarEvolution.h:347
llvm::ScalarEvolution::isBasicBlockEntryGuardedByCond
bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the basic block is protected by a conditional between LHS and RHS.
Definition: ScalarEvolution.cpp:11187
llvm::ScalarEvolution::getTruncateOrNoop
const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
Definition: ScalarEvolution.cpp:4655
llvm::ScalarEvolution::hasLoopInvariantBackedgeTakenCount
bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
Definition: ScalarEvolution.cpp:13226
llvm::ScalarEvolution::registerUser
void registerUser(const SCEV *User, ArrayRef< const SCEV * > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
Definition: ScalarEvolution.cpp:14399
Signed
@ Signed
Definition: NVPTXISelLowering.cpp:4709
llvm::ScalableVectorType
Class to represent scalable SIMD vectors.
Definition: DerivedTypes.h:572
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2136
llvm::SCEV::operator=
SCEV & operator=(const SCEV &)=delete
llvm::ScalarEvolution::SimplifyICmpOperands
bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS, const SCEV *&RHS, unsigned Depth=0, bool ControllingFiniteLoop=false)
Simplify LHS and RHS in a comparison with predicate Pred.
Definition: ScalarEvolution.cpp:10344
llvm::ScalarEvolution::isLoopEntryGuardedByCond
bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
Definition: ScalarEvolution.cpp:11287
llvm::ScalarEvolution::getNegativeSCEV
const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
Definition: ScalarEvolution.cpp:4458
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::ScalarEvolution::getNoopOrZeroExtend
const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
Definition: ScalarEvolution.cpp:4619
Optional.h
llvm::ScalarEvolutionWrapperPass::getSE
const ScalarEvolution & getSE() const
Definition: ScalarEvolution.h:2175
llvm::ScalarEvolution::getEffectiveSCEVType
Type * getEffectiveSCEVType(Type *Ty) const
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the g...
Definition: ScalarEvolution.cpp:4339
llvm::PredicatedScalarEvolution::getPredicate
const SCEVPredicate & getPredicate() const
Definition: ScalarEvolution.cpp:14449
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::SCEVComparePredicate::getLHS
const SCEV * getLHS() const
Returns the left hand side of the predicate.
Definition: ScalarEvolution.h:297
llvm::SCEVPredicate::operator=
SCEVPredicate & operator=(const SCEVPredicate &)=default
llvm::SCEVUnionPredicate::implies
bool implies(const SCEVPredicate *N) const override
Returns true if this predicate implies N.
Definition: ScalarEvolution.cpp:14368
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:719
llvm::SCEV::isAllOnesValue
bool isAllOnesValue() const
Return true if the expression is a constant all-ones value.
Definition: ScalarEvolution.cpp:441
llvm::SCEVComparePredicate::classof
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolution.h:303
llvm::SCEVPredicate::print
virtual void print(raw_ostream &OS, unsigned Depth=0) const =0
Prints a textual representation of this predicate with an indentation of Depth.
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
llvm::ScalarEvolution::getSmallConstantTripMultiple
unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
Definition: ScalarEvolution.cpp:8099
llvm::ScalarEvolution::getLosslessPtrToIntExpr
const SCEV * getLosslessPtrToIntExpr(const SCEV *Op, unsigned Depth=0)
Definition: ScalarEvolution.cpp:1074
llvm::Function
Definition: Function.h:60
llvm::ScalarEvolution::loopIsFiniteByAssumption
bool loopIsFiniteByAssumption(const Loop *L)
Return true if this loop is finite by assumption.
Definition: ScalarEvolution.cpp:7217
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::ScalarEvolution::LoopInvariantPredicate::RHS
const SCEV * RHS
Definition: ScalarEvolution.h:1083
Pass.h
llvm::SCEVExpander
This class uses information about analyze scalars to rewrite expressions in canonical form.
Definition: ScalarEvolutionExpander.h:50
llvm::SCEVPredicate::SCEVPredicateKind
SCEVPredicateKind
Definition: ScalarEvolution.h:223
llvm::PredicatedScalarEvolution
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
Definition: ScalarEvolution.h:2197
llvm::ScalarEvolution::getConstantMaxBackedgeTakenCount
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
Definition: ScalarEvolution.h:891
llvm::SCEVComparePredicate::implies
bool implies(const SCEVPredicate *N) const override
Implementation of the SCEVPredicate interface.
Definition: ScalarEvolution.cpp:14279
llvm::PredicatedScalarEvolution::PredicatedScalarEvolution
PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L)
Definition: ScalarEvolution.cpp:14392
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1182
llvm::ScalarEvolution::isKnownViaInduction
bool isKnownViaInduction(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
We'd like to check the predicate on every iteration of the most dominated loop between loops used in ...
Definition: ScalarEvolution.cpp:10580
llvm::ScalarEvolution::isKnownNonZero
bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
Definition: ScalarEvolution.cpp:10564
llvm::PredicatedScalarEvolution::getBackedgeTakenCount
const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
Definition: ScalarEvolution.cpp:14428
llvm::ScalarEvolution::getSignedRangeMax
APInt getSignedRangeMax(const SCEV *S)
Determine the max of the signed range for a particular SCEV.
Definition: ScalarEvolution.h:976
llvm::ScalarEvolution::getAddRecExpr
const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
Definition: ScalarEvolution.cpp:3605
llvm::ScalarEvolutionPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: ScalarEvolution.cpp:14023
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
llvm::ScalarEvolution::getBlockDisposition
BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB)
Return the "disposition" of the given SCEV with respect to the given block.
Definition: ScalarEvolution.cpp:13505
llvm::ScalarEvolutionPrinterPass
Printer pass for the ScalarEvolutionAnalysis results.
Definition: ScalarEvolution.h:2156
llvm::ScalarEvolutionWrapperPass::runOnFunction
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: ScalarEvolution.cpp:14048
llvm::SCEV::NoWrapMask
@ NoWrapMask
Definition: ScalarEvolution.h:135
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::SCEVTypes
SCEVTypes
Definition: ScalarEvolutionExpressions.h:38
llvm::ScalarEvolution::getTruncateExpr
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
Definition: ScalarEvolution.cpp:1208
llvm::ScalarEvolution::getTypeSizeInBits
uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
Definition: ScalarEvolution.cpp:4329
llvm::ScalarEvolution::getNoopOrAnyExtend
const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
Definition: ScalarEvolution.cpp:4643
llvm::SCEVWrapPredicate::print
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
Definition: ScalarEvolution.cpp:14326
llvm::SCEV::FlagNW
@ FlagNW
Definition: ScalarEvolution.h:132
APInt.h
llvm::SCEV::dump
void dump() const
This method is used for debugging.
Definition: ScalarEvolution.cpp:259
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
llvm::ScalarEvolutionVerifierPass
Verifier pass for the ScalarEvolutionAnalysis results.
Definition: ScalarEvolution.h:2149
llvm::ScalarEvolution::LoopInvariant
@ LoopInvariant
The SCEV is loop-invariant.
Definition: ScalarEvolution.h:456
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::ScalarEvolution::LoopComputable
@ LoopComputable
The SCEV varies predictably with the loop.
Definition: ScalarEvolution.h:457
llvm::ScalarEvolution::ConstantMaximum
@ ConstantMaximum
A constant which provides an upper bound on the exact trip count.
Definition: ScalarEvolution.h:854
llvm::ScalarEvolution::LoopInvariantPredicate::Pred
ICmpInst::Predicate Pred
Definition: ScalarEvolution.h:1081
llvm::ScalarEvolution::getConstantMaxTripCountFromArray
const SCEV * getConstantMaxTripCountFromArray(const Loop *L)
Returns the upper bound of the loop trip count infered from array size.
Definition: ScalarEvolution.cpp:7965
llvm::ScalarEvolution::LoopVariant
@ LoopVariant
The SCEV is loop-variant (unknown).
Definition: ScalarEvolution.h:455
llvm::Optional
Definition: APInt.h:33
llvm::BumpPtrAllocator
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition: Allocator.h:375
llvm::ScalarEvolution::applyLoopGuards
const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
Definition: ScalarEvolution.cpp:14658
llvm::ScalarEvolution::hasFlags
static bool hasFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags TestFlags)
Definition: ScalarEvolution.h:481
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::ScalarEvolution::getUDivExactExpr
const SCEV * getUDivExactExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
Definition: ScalarEvolution.cpp:3551
llvm::ScalarEvolutionWrapperPass::getSE
ScalarEvolution & getSE()
Definition: ScalarEvolution.h:2174
llvm::ScalarEvolution::getWiderType
Type * getWiderType(Type *Ty1, Type *Ty2) const
Definition: ScalarEvolution.cpp:4350
llvm::tgtok::FalseVal
@ FalseVal
Definition: TGLexer.h:62
llvm::ScalarEvolution::evaluatePredicate
Optional< bool > evaluatePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Check whether the condition described by Pred, LHS, and RHS is true or false.
Definition: ScalarEvolution.cpp:10646
llvm::ScalarEvolution::rewriteUsingPredicate
const SCEV * rewriteUsingPredicate(const SCEV *S, const Loop *L, const SCEVPredicate &A)
Re-writes the SCEV according to the Predicates in A.
Definition: ScalarEvolution.cpp:14243
llvm::ScalarEvolution::getUnknown
const SCEV * getUnknown(Value *V)
Definition: ScalarEvolution.cpp:4292
llvm::SCEV::getSCEVType
SCEVTypes getSCEVType() const
Definition: ScalarEvolution.h:144
llvm::ScalarEvolution::isKnownNonNegative
bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
Definition: ScalarEvolution.cpp:10556
llvm::ScalarEvolution::getTruncateOrSignExtend
const SCEV * getTruncateOrSignExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
Definition: ScalarEvolution.cpp:4606
llvm::ScalarEvolution::getPredicatedBackedgeTakenCount
const SCEV * getPredicatedBackedgeTakenCount(const Loop *L, SmallVector< const SCEVPredicate *, 4 > &Predicates)
Similar to getBackedgeTakenCount, except it will add a set of SCEV predicates to Predicates that are ...
Definition: ScalarEvolution.cpp:8163
llvm::SCEVWrapPredicate::implies
bool implies(const SCEVPredicate *N) const override
Returns true if this predicate implies N.
Definition: ScalarEvolution.cpp:14310
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::FoldingSetTrait< SCEV >::Profile
static void Profile(const SCEV &X, FoldingSetNodeID &ID)
Definition: ScalarEvolution.h:185
llvm::SCEVPredicate::P_Wrap
@ P_Wrap
Definition: ScalarEvolution.h:223
llvm::ScalarEvolution::getTruncateOrZeroExtend
const SCEV * getTruncateOrZeroExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
Definition: ScalarEvolution.cpp:4594
llvm::ScalarEvolution::computeConstantDifference
Optional< APInt > computeConstantDifference(const SCEV *LHS, const SCEV *RHS)
Compute LHS - RHS and returns the result as an APInt if it is a constant, and None if it isn't.
Definition: ScalarEvolution.cpp:11621
llvm::ScalarEvolution::getUnsignedRangeMin
APInt getUnsignedRangeMin(const SCEV *S)
Determine the min of the unsigned range for a particular SCEV.
Definition: ScalarEvolution.h:955
llvm::PredicatedScalarEvolution::getAsAddRec
const SCEVAddRecExpr * getAsAddRec(Value *V)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
Definition: ScalarEvolution.cpp:14495
llvm::ScalarEvolution::getPointerBase
const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
Definition: ScalarEvolution.cpp:4712
llvm::ScalarEvolution::getURemExpr
const SCEV * getURemExpr(const SCEV *LHS, const SCEV *RHS)
Represents an unsigned remainder expression based on unsigned division.
Definition: ScalarEvolution.cpp:3350
llvm::ScalarEvolution::getUMinFromMismatchedTypes
const SCEV * getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
Promote the operands to the wider of the types using zero-extension, and then perform a umin operatio...
Definition: ScalarEvolution.cpp:4679
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::SCEVPredicate
This class represents an assumption made using SCEV expressions which can be checked at run-time.
Definition: ScalarEvolution.h:215
llvm::SCEVPredicate::implies
virtual bool implies(const SCEVPredicate *N) const =0
Returns true if this predicate implies N.
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::ScalarEvolution::getSizeOfExpr
const SCEV * getSizeOfExpr(Type *IntTy, Type *AllocTy)
Return an expression for the alloc size of AllocTy that is type IntTy.
Definition: ScalarEvolution.cpp:4264
PointerIntPair.h
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
llvm::ScalarEvolution::getMulExpr
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
Definition: ScalarEvolution.cpp:3084
llvm::ScalarEvolution::containsErasedValue
bool containsErasedValue(const SCEV *S) const
Return true if the SCEV expression contains a Value that has been optimised out and is now a nullptr.
Definition: ScalarEvolution.cpp:13081
llvm::SCEVPredicate::Kind
SCEVPredicateKind Kind
Definition: ScalarEvolution.h:226
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:186
llvm::ScalarEvolution::properlyDominates
bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
Definition: ScalarEvolution.cpp:13595
llvm::BitmaskEnumDetail::Mask
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::ScalarEvolution::MonotonicPredicateType
MonotonicPredicateType
A predicate is said to be monotonically increasing if may go from being false to being true as the lo...
Definition: ScalarEvolution.h:1067
llvm::ScalarEvolution::getTripCountFromExitCount
const SCEV * getTripCountFromExitCount(const SCEV *ExitCount, bool Extend=true)
Convert from an "exit count" (i.e.
Definition: ScalarEvolution.cpp:7912
llvm::ScalarEvolutionWrapperPass::ID
static char ID
Definition: ScalarEvolution.h:2170
llvm::ScalarEvolution::getOne
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
Definition: ScalarEvolution.h:649
llvm::ScalarEvolution::getLoopInvariantExitCondDuringFirstIterations
Optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterations(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L at given Context duri...
Definition: ScalarEvolution.cpp:10841
llvm::ScalarEvolution::hasComputableLoopEvolution
bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
Definition: ScalarEvolution.cpp:13500
llvm::ISD::Constant
@ Constant
Definition: ISDOpcodes.h:76
llvm::ScalarEvolution::ScalarEvolution
ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI)
Definition: ScalarEvolution.cpp:13151
llvm::SCEVPredicate::~SCEVPredicate
~SCEVPredicate()=default
llvm::SCEVWrapPredicate::maskFlags
static SCEVWrapPredicate::IncrementWrapFlags maskFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, int Mask)
Definition: ScalarEvolution.h:361
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::User
Definition: User.h:44
llvm::ConstantRange::getUnsignedMin
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
Definition: ConstantRange.cpp:431
llvm::ScalarEvolution::getUMaxExpr
const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.cpp:4221
llvm::ScalarEvolution::getSequentialMinMaxExpr
const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
Definition: ScalarEvolution.cpp:4103
InstrTypes.h
llvm::SCEV::print
void print(raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
Definition: ScalarEvolution.cpp:265
llvm::SCEV::SCEV
SCEV(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, unsigned short ExpressionSize)
Definition: ScalarEvolution.h:138
llvm::ScalarEvolution::getAbsExpr
const SCEV * getAbsExpr(const SCEV *Op, bool IsNSW)
Definition: ScalarEvolution.cpp:3784
llvm::SCEV::getExpressionSize
unsigned short getExpressionSize() const
Definition: ScalarEvolution.h:170
llvm::ScalarEvolution::SCEVUnknown
friend class SCEVUnknown
Definition: ScalarEvolution.h:1227
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::ScalarEvolution::getUDivExpr
const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
Definition: ScalarEvolution.cpp:3379
llvm::PredicatedScalarEvolution::hasNoOverflow
bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've proved that V doesn't wrap by means of a SCEV predicate.
Definition: ScalarEvolution.cpp:14479
llvm::ScalarEvolution::containsUndefs
bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
Definition: ScalarEvolution.cpp:13072
llvm::ScalarEvolution::getMulExpr
const SCEV * getMulExpr(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Definition: ScalarEvolution.h:588
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::SCEVWrapPredicate::IncrementNSSW
@ IncrementNSSW
Definition: ScalarEvolution.h:345
llvm::ScalarEvolution::isKnownPredicate
bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
Definition: ScalarEvolution.cpp:10631
llvm::Instruction
Definition: Instruction.h:42
llvm::FoldingSetTrait< SCEV >::Equals
static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)
Definition: ScalarEvolution.h:187
llvm::ConstantRange::getUnsignedMax
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
Definition: ConstantRange.cpp:425
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::FoldingSetTrait< SCEVPredicate >::ComputeHash
static unsigned ComputeHash(const SCEVPredicate &X, FoldingSetNodeID &TempID)
Definition: ScalarEvolution.h:270
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2166
llvm::SCEVComparePredicate::getRHS
const SCEV * getRHS() const
Returns the right hand side of the predicate.
Definition: ScalarEvolution.h:300
SmallPtrSet.h
llvm::SCEVComparePredicate::SCEVComparePredicate
SCEVComparePredicate(const FoldingSetNodeIDRef ID, const ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.cpp:14271
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:661
llvm::ScalarEvolution::getCastExpr
const SCEV * getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty)
Definition: ScalarEvolution.cpp:2138
llvm::ScalarEvolution::getEqualPredicate
const SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.cpp:14078
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
Operands
mir Rename Register Operands
Definition: MIRNamerPass.cpp:74
llvm::SCEV::isNonConstantNegative
bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
Definition: ScalarEvolution.cpp:447
llvm::SCEV::SubclassData
unsigned short SubclassData
This field is initialized to zero and may be used in subclasses to store miscellaneous information.
Definition: ScalarEvolution.h:91
llvm::ScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
Definition: ScalarEvolution.cpp:4436
llvm::ScalarEvolution::willNotOverflow
bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI=nullptr)
Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?...
Definition: ScalarEvolution.cpp:2292
llvm::ScalarEvolution::SplitIntoInitAndPostInc
std::pair< const SCEV *, const SCEV * > SplitIntoInitAndPostInc(const Loop *L, const SCEV *S)
Splits SCEV expression S into two SCEVs.
Definition: ScalarEvolution.cpp:10569
llvm::ScalarEvolutionPrinterPass::ScalarEvolutionPrinterPass
ScalarEvolutionPrinterPass(raw_ostream &OS)
Definition: ScalarEvolution.h:2161
llvm::ScalarEvolution::dominates
bool dominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV dominate the specified basic block.
Definition: ScalarEvolution.cpp:13591
llvm::PredicatedScalarEvolution::areAddRecsEqualWithPreds
bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds.
Definition: ScalarEvolution.cpp:5570
llvm::ScalarEvolution::getSmallConstantTripCount
unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
Definition: ScalarEvolution.cpp:7943
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:75
llvm::SCEVUnionPredicate::getComplexity
unsigned getComplexity() const override
We estimate the complexity of a union predicate as the size number of predicates in the union.
Definition: ScalarEvolution.h:438
llvm::ScalarEvolution::LoopInvariantPredicate::LHS
const SCEV * LHS
Definition: ScalarEvolution.h:1082
llvm::ScalarEvolution::verify
void verify() const
Definition: ScalarEvolution.cpp:13752
llvm::SCEVWrapPredicate::classof
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolution.h:402
llvm::ScalarEvolution::getUnsignedRangeMax
APInt getUnsignedRangeMax(const SCEV *S)
Determine the max of the unsigned range for a particular SCEV.
Definition: ScalarEvolution.h:960
llvm::FoldingSetTrait
FoldingSetTrait - This trait class is used to define behavior of how to "profile" (in the FoldingSet ...
Definition: FoldingSet.h:261
uint64_t
llvm::ScalarEvolution::isKnownOnEveryIteration
bool isKnownOnEveryIteration(ICmpInst::Predicate Pred, const SCEVAddRecExpr *LHS, const SCEV *RHS)
Test if the condition described by Pred, LHS, RHS is known to be true on every iteration of the loop ...
Definition: ScalarEvolution.cpp:10681
llvm::ScalarEvolutionAnalysis::run
ScalarEvolution run(Function &F, FunctionAnalysisManager &AM)
Definition: ScalarEvolution.cpp:14008
llvm::ConstantRange::getSignedMin
APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
Definition: ConstantRange.cpp:443
llvm::ScalarEvolution::instructionCouldExistWitthOperands
bool instructionCouldExistWitthOperands(const SCEV *A, const SCEV *B)
Return true if there exists a point in the program at which both A and B could be operands to the sam...
Definition: ScalarEvolution.cpp:4354
llvm::SCEVPredicate::getKind
SCEVPredicateKind getKind() const
Definition: ScalarEvolution.h:234
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::PredicatedScalarEvolution::setNoOverflow
void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Proves that V doesn't overflow by adding SCEV predicate.
Definition: ScalarEvolution.cpp:14463
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:644
llvm::find
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1610
llvm::ScalarEvolution::getSMaxExpr
const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.cpp:4212
llvm::SCEVCouldNotCompute::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolution.cpp:462
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
llvm::SCEV::FlagNSW
@ FlagNSW
Definition: ScalarEvolution.h:134
llvm::ScalarEvolution::getSmallConstantMaxTripCount
unsigned getSmallConstantMaxTripCount(const Loop *L)
Returns the upper bound of the loop trip count as a normal unsigned value.
Definition: ScalarEvolution.cpp:7959
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
llvm::ScalarEvolution::getUDivCeilSCEV
const SCEV * getUDivCeilSCEV(const SCEV *N, const SCEV *D)
Compute ceil(N / D).
Definition: ScalarEvolution.cpp:12391
llvm::SCEV::FlagAnyWrap
@ FlagAnyWrap
Definition: ScalarEvolution.h:131
llvm::ScalarEvolution::getAddExpr
const SCEV * getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Definition: ScalarEvolution.h:579
llvm::ScalarEvolution::Exact
@ Exact
An expression exactly describing the number of times the backedge has executed when a loop is exited.
Definition: ScalarEvolution.h:852
llvm::ScalarEvolution::getPtrToIntExpr
const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
Definition: ScalarEvolution.cpp:1198
llvm::ScalarEvolution::LoopDisposition
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
Definition: ScalarEvolution.h:454
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::ScalarEvolution::createAddRecFromPHIWithCasts
Optional< std::pair< const SCEV *, SmallVector< const SCEVPredicate *, 3 > > > createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI)
Checks if SymbolicPHI can be rewritten as an AddRecExpr under some Predicates.
Definition: ScalarEvolution.cpp:5530
llvm::ScalarEvolution::getSymbolicMaxBackedgeTakenCount
const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEV that is greater than or equal to (i.e.
Definition: ScalarEvolution.h:899
llvm::ScalarEvolution::isLoopBackedgeGuardedByCond
bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether the backedge of the loop is protected by a conditional between LHS and RHS.
Definition: ScalarEvolution.cpp:11082
llvm::SCEVComparePredicate::isAlwaysTrue
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
Definition: ScalarEvolution.cpp:14291
ArrayRef.h
llvm::ScalarEvolution::getUnsignedRange
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
Definition: ScalarEvolution.h:950
llvm::FoldingSetTrait< SCEVPredicate >::Equals
static bool Equals(const SCEVPredicate &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)
Definition: ScalarEvolution.h:265
llvm::SCEVWrapPredicate::IncrementNUSW
@ IncrementNUSW
Definition: ScalarEvolution.h:344
llvm::ScalarEvolution::forgetValue
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
Definition: ScalarEvolution.cpp:8358
TemplateParamKind::Type
@ Type
llvm::ScalarEvolution::getMonotonicPredicateType
Optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
Definition: ScalarEvolution.cpp:10690
llvm::ScalarEvolution::MonotonicallyIncreasing
@ MonotonicallyIncreasing
Definition: ScalarEvolution.h:1068
llvm::SCEVWrapPredicate::getImpliedFlags
static SCEVWrapPredicate::IncrementWrapFlags getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE)
Returns the set of SCEVWrapPredicate no wrap flags implied by a SCEVAddRecExpr.
Definition: ScalarEvolution.cpp:14336
llvm::ScalarEvolution::containsAddRecurrence
bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
Definition: ScalarEvolution.cpp:4382
llvm::ScalarEvolution::SCEVCallbackVH
friend class SCEVCallbackVH
Definition: ScalarEvolution.h:1225
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::PredicatedScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
Definition: ScalarEvolution.cpp:14409
llvm::ScalarEvolution::GetMinTrailingZeros
uint32_t GetMinTrailingZeros(const SCEV *S)
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
Definition: ScalarEvolution.cpp:6280
llvm::ScalarEvolution::clearFlags
static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
Definition: ScalarEvolution.h:478
llvm::ScalarEvolution::LoopInvariantPredicate::LoopInvariantPredicate
LoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.h:1085
llvm::ScalarEvolution::getAddExpr
const SCEV * getAddExpr(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Definition: ScalarEvolution.h:573
llvm::SCEVWrapPredicate::setFlags
static SCEVWrapPredicate::IncrementWrapFlags setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OnFlags)
Definition: ScalarEvolution.h:369
llvm::SCEVPredicate::isAlwaysTrue
virtual bool isAlwaysTrue() const =0
Returns true if the predicate is always true.
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::SCEVCouldNotCompute
An object of this class is returned by queries that could not be answered.
Definition: ScalarEvolution.h:206
llvm::ScalarEvolution::print
void print(raw_ostream &OS) const
Definition: ScalarEvolution.cpp:13305
llvm::ScalarEvolution::evaluatePredicateAt
Optional< bool > evaluatePredicateAt(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Check whether the condition described by Pred, LHS, and RHS is true or false in the given Context.
Definition: ScalarEvolution.cpp:10664
llvm::ScalarEvolution::forgetTopmostLoop
void forgetTopmostLoop(const Loop *L)
Definition: ScalarEvolution.cpp:8354
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::ScalarEvolution::getStrengthenedNoWrapFlagsFromBinOp
Optional< SCEV::NoWrapFlags > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
Definition: ScalarEvolution.cpp:2352
llvm::ScalarEvolution::getSizeOfScalableVectorExpr
const SCEV * getSizeOfScalableVectorExpr(Type *IntTy, ScalableVectorType *ScalableTy)
Return an expression for sizeof ScalableTy that is type IntTy, where ScalableTy is a scalable vector ...
Definition: ScalarEvolution.cpp:4253
llvm::SCEVPredicate::P_Compare
@ P_Compare
Definition: ScalarEvolution.h:223
llvm::ScalarEvolution::getNoopOrSignExtend
const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
Definition: ScalarEvolution.cpp:4631
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
llvm::ScalarEvolution::getDataLayout
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
Definition: ScalarEvolution.h:1162
llvm::GEPOperator
Definition: Operator.h:375
llvm::ScalarEvolutionWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: ScalarEvolution.cpp:14070
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::ScalarEvolution::BlockDisposition
BlockDisposition
An enum describing the relationship between a SCEV and a basic block.
Definition: ScalarEvolution.h:461
llvm::SCEVUnionPredicate::isAlwaysTrue
bool isAlwaysTrue() const override
Implementation of the SCEVPredicate interface.
Definition: ScalarEvolution.cpp:14363
llvm::ScalarEvolution::forgetLoopDispositions
void forgetLoopDispositions()
Called when the client has changed the disposition of values in this loop.
Definition: ScalarEvolution.cpp:8385
llvm::ScalarEvolution::getAddRecExpr
const SCEV * getAddRecExpr(const SmallVectorImpl< const SCEV * > &Operands, const Loop *L, SCEV::NoWrapFlags Flags)
Definition: ScalarEvolution.h:607
llvm::ScalarEvolution::getOffsetOfExpr
const SCEV * getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo)
Return an expression for offsetof on the given field with type IntTy.
Definition: ScalarEvolution.cpp:4282
llvm::ScalarEvolution::getUMaxFromMismatchedTypes
const SCEV * getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS)
Promote the operands to the wider of the types using zero-extension, and then perform a umax operatio...
Definition: ScalarEvolution.cpp:4666
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::LoopInfo
Definition: LoopInfo.h:1105
llvm::ScalarEvolution::hasOperand
bool hasOperand(const SCEV *S, const SCEV *Op) const
Test whether the given SCEV has Op as a direct or indirect operand.
Definition: ScalarEvolution.cpp:13599
llvm::ScalarEvolution::getSignExtendExpr
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
Definition: ScalarEvolution.cpp:1901
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::SCEVPredicate::getComplexity
virtual unsigned getComplexity() const
Returns the estimated complexity of this predicate.
Definition: ScalarEvolution.h:238
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm::FoldingSetBase::Node
Node - This class is used to maintain the singly linked bucket list in a folding set.
Definition: FoldingSet.h:136
llvm::ScalarEvolution::getConstant
const SCEV * getConstant(ConstantInt *V)
Definition: ScalarEvolution.cpp:466
llvm::ScalarEvolution::getStoreSizeOfExpr
const SCEV * getStoreSizeOfExpr(Type *IntTy, Type *StoreTy)
Return an expression for the store size of StoreTy that is type IntTy.
Definition: ScalarEvolution.cpp:4273
A
* A
Definition: README_ALTIVEC.txt:89
llvm::ScalarEvolution::getElementSize
const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
Definition: ScalarEvolution.cpp:13090
uint32_t
llvm::SCEV::FlagNUW
@ FlagNUW
Definition: ScalarEvolution.h:133
ConstantRange.h
llvm::FoldingSetNodeID
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:318
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
llvm::ScalarEvolution::getSignedRangeMin
APInt getSignedRangeMin(const SCEV *S)
Determine the min of the signed range for a particular SCEV.
Definition: ScalarEvolution.h:971
llvm::ScalarEvolution::getLoopInvariantPredicate
Optional< LoopInvariantPredicate > getLoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI=nullptr)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L, return a LoopInvaria...
Definition: ScalarEvolution.cpp:10755
llvm::ScalarEvolution::ScalarEvolutionsTest
friend class ScalarEvolutionsTest
Definition: ScalarEvolution.h:450
llvm::OverflowingBinaryOperator
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
Definition: Operator.h:72
llvm::ScalarEvolution::getUMinExpr
const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
Definition: ScalarEvolution.cpp:4240
llvm::ScalarEvolution::ExitCountKind
ExitCountKind
The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of ...
Definition: ScalarEvolution.h:849
llvm::SCEVWrapPredicate::IncrementAnyWrap
@ IncrementAnyWrap
Definition: ScalarEvolution.h:343
llvm::SCEVWrapPredicate::clearFlags
static SCEVWrapPredicate::IncrementWrapFlags clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OffFlags)
Convenient IncrementWrapFlags manipulation methods.
Definition: ScalarEvolution.h:352
llvm::ValueMap
See the file comment.
Definition: ValueMap.h:85
ValueHandle.h
llvm::SCEVComparePredicate::print
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
Definition: ScalarEvolution.cpp:14293
ValueMap.h
llvm::ScalarEvolution::isLoopInvariant
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
Definition: ScalarEvolution.cpp:13496
FoldingSet.h
llvm::SCEVCouldNotCompute::SCEVCouldNotCompute
SCEVCouldNotCompute()
Definition: ScalarEvolution.cpp:459
llvm::ScalarEvolution::isKnownPositive
bool isKnownPositive(const SCEV *S)
Test if the given expression is known to be positive.
Definition: ScalarEvolution.cpp:10552
llvm::ScalarEvolution::DominatesBlock
@ DominatesBlock
The SCEV dominates the block.
Definition: ScalarEvolution.h:463
llvm::SCEV::NoWrapFlags
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
Definition: ScalarEvolution.h:130
llvm::ScalarEvolutionWrapperPass::print
void print(raw_ostream &OS, const Module *=nullptr) const override
print - Print out the internal state of the pass.
Definition: ScalarEvolution.cpp:14059
llvm::ScalarEvolution::isKnownNonPositive
bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
Definition: ScalarEvolution.cpp:10560
llvm::ConstantRange::getSignedMax
APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
Definition: ConstantRange.cpp:437
llvm::SCEVWrapPredicate::SCEVWrapPredicate
SCEVWrapPredicate(const FoldingSetNodeIDRef ID, const SCEVAddRecExpr *AR, IncrementWrapFlags Flags)
Definition: ScalarEvolution.cpp:14303
llvm::ScalarEvolution::maskFlags
static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask)
Convenient NoWrapFlags manipulation that hides enum casts and is visible in the ScalarEvolution name ...
Definition: ScalarEvolution.h:469
llvm::ScalarEvolution::forgetLoop
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
Definition: ScalarEvolution.cpp:8298
llvm::ScalarEvolution::isKnownPredicateAt
bool isKnownPredicateAt(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
Definition: ScalarEvolution.cpp:10656
llvm::ScalarEvolution::getGEPExpr
const SCEV * getGEPExpr(GEPOperator *GEP, const SmallVectorImpl< const SCEV * > &IndexExprs)
Returns an expression for a GEP.
Definition: ScalarEvolution.cpp:3700
llvm::ScalarEvolution::getMinusSCEV
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
Definition: ScalarEvolution.cpp:4544
llvm::SCEVWrapPredicate::getFlags
IncrementWrapFlags getFlags() const
Returns the set assumed no overflow flags.
Definition: ScalarEvolution.h:393
llvm::ScalarEvolution::convertSCEVToAddRecWithPredicates
const SCEVAddRecExpr * convertSCEVToAddRecWithPredicates(const SCEV *S, const Loop *L, SmallPtrSetImpl< const SCEVPredicate * > &Preds)
Tries to convert the S expression to an AddRec expression, adding additional predicates to Preds as r...
Definition: ScalarEvolution.cpp:14248
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::ScalarEvolution::loopHasNoAbnormalExits
bool loopHasNoAbnormalExits(const Loop *L)
Return true if the loop has no abnormal exits.
Definition: ScalarEvolution.h:1204
llvm::ScalarEvolution::invalidate
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Definition: ScalarEvolution.cpp:13994
llvm::ScalarEvolution::SymbolicMaximum
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
Definition: ScalarEvolution.h:856
llvm::ScalarEvolution::DoesNotDominateBlock
@ DoesNotDominateBlock
The SCEV does not dominate the block.
Definition: ScalarEvolution.h:462
llvm::DefaultFoldingSetTrait
DefaultFoldingSetTrait - This class provides default implementations for FoldingSetTrait implementati...
Definition: FoldingSet.h:231
llvm::ScalarEvolution::isBackedgeTakenCountMaxOrZero
bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
Definition: ScalarEvolution.cpp:8181
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::ScalarEvolution::getComparePredicate
const SCEVPredicate * getComparePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.cpp:14084
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::SCEVUnknown
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
Definition: ScalarEvolutionExpressions.h:571
llvm::ScalarEvolution::isSCEVable
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
Definition: ScalarEvolution.cpp:4322
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
PassManager.h
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:222
llvm::SCEV::isOne
bool isOne() const
Return true if the expression is a constant one.
Definition: ScalarEvolution.cpp:435
llvm::ScalarEvolution::getCouldNotCompute
const SCEV * getCouldNotCompute()
Definition: ScalarEvolution.cpp:4369
llvm::PredicatedScalarEvolution::addPredicate
void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
Definition: ScalarEvolution.cpp:14438
llvm::ScalarEvolution::setNoWrapFlags
void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags)
Update no-wrap flags of an AddRec.
Definition: ScalarEvolution.cpp:6300
llvm::ScalarEvolution::isAvailableAtLoopEntry
bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
Definition: ScalarEvolution.cpp:2482
llvm::SCEVWrapPredicate::isAlwaysTrue
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
Definition: ScalarEvolution.cpp:14316
llvm::CallbackVH
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:383
llvm::ConstantRange
This class represents a range of values.
Definition: ConstantRange.h:47
llvm::FoldingSetNodeIDRef
FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID,...
Definition: FoldingSet.h:288
llvm::ScalarEvolution::getMulExpr
const SCEV * getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Definition: ScalarEvolution.h:594
llvm::ScalarEvolution::LoopInvariantPredicate
Definition: ScalarEvolution.h:1080
llvm::ScalarEvolution::MonotonicallyDecreasing
@ MonotonicallyDecreasing
Definition: ScalarEvolution.h:1069
llvm::ScalarEvolutionVerifierPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: ScalarEvolution.cpp:14017
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:773
llvm::ScalarEvolution::setFlags
static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
Definition: ScalarEvolution.h:473
isSigned
static bool isSigned(unsigned int Opcode)
Definition: ExpandLargeDivRem.cpp:52
llvm::ScalarEvolution::getAnyExtendExpr
const SCEV * getAnyExtendExpr(const SCEV *Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
Definition: ScalarEvolution.cpp:2156
llvm::ScalarEvolution::getZeroExtendExpr
const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
Definition: ScalarEvolution.cpp:1599
llvm::ScalarEvolution::removePointerBase
const SCEV * removePointerBase(const SCEV *S)
Compute an expression equivalent to S - getPointerBase(S).
Definition: ScalarEvolution.cpp:4514
Instructions.h
llvm::SCEVWrapPredicate::getExpr
const SCEVAddRecExpr * getExpr() const
Implementation of the SCEVPredicate interface.
Definition: ScalarEvolution.cpp:14308
llvm::SCEVUnionPredicate::classof
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolution.h:441
llvm::ScalarEvolution::getMinusOne
const SCEV * getMinusOne(Type *Ty)
Return a SCEV for the constant -1 of a specific type.
Definition: ScalarEvolution.h:652
llvm::ScalarEvolutionWrapperPass::verifyAnalysis
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: ScalarEvolution.cpp:14063
SmallVector.h
llvm::FoldingSetTrait< SCEV >::ComputeHash
static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID)
Definition: ScalarEvolution.h:192
llvm::ScalarEvolution::getLoopDisposition
LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
Definition: ScalarEvolution.cpp:13396
llvm::ScalarEvolution::forgetAllLoops
void forgetAllLoops()
Definition: ScalarEvolution.cpp:8274
llvm::SCEVPredicate::P_Union
@ P_Union
Definition: ScalarEvolution.h:223
llvm::ScalarEvolution::getSignedRange
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
Definition: ScalarEvolution.h:966
N
#define N
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:164
llvm::ScalarEvolution::getZero
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
Definition: ScalarEvolution.h:646
llvm::ScalarEvolutionWrapperPass::ScalarEvolutionWrapperPass
ScalarEvolutionWrapperPass()
Definition: ScalarEvolution.cpp:14044
llvm::SCEVUnionPredicate::print
void print(raw_ostream &OS, unsigned Depth) const override
Prints a textual representation of this predicate with an indentation of Depth.
Definition: ScalarEvolution.cpp:14377
llvm::SCEVWrapPredicate::IncrementWrapFlags
IncrementWrapFlags
Similar to SCEV::NoWrapFlags, but with slightly different semantics for FlagNUSW.
Definition: ScalarEvolution.h:342
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
DenseMapInfo.h
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:398
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
llvm::SCEV::getType
Type * getType() const
Return the LLVM type of this SCEV expression.
Definition: ScalarEvolution.cpp:397
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::ScalarEvolution::getAddExpr
const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
Definition: ScalarEvolution.cpp:2487
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::SCEVUnionPredicate::getPredicates
const SmallVectorImpl< const SCEVPredicate * > & getPredicates() const
Definition: ScalarEvolution.h:427
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:171
llvm::ScalarEvolution::getMinMaxExpr
const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
Definition: ScalarEvolution.cpp:3789
llvm::ScalarEvolution::~ScalarEvolution
~ScalarEvolution()
Definition: ScalarEvolution.cpp:13203
llvm::ScalarEvolution::getWrapPredicate
const SCEVPredicate * getWrapPredicate(const SCEVAddRecExpr *AR, SCEVWrapPredicate::IncrementWrapFlags AddedFlags)
Definition: ScalarEvolution.cpp:14103
llvm::PredicatedScalarEvolution::print
void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
Definition: ScalarEvolution.cpp:14519
llvm::SCEVPredicate::SCEVPredicate
SCEVPredicate(const SCEVPredicate &)=default
llvm::ScalarEvolutionWrapperPass::releaseMemory
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: ScalarEvolution.cpp:14057
llvm::ScalarEvolution::getBackedgeTakenCount
const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
Definition: ScalarEvolution.cpp:8168
llvm::PredicatedScalarEvolution::getSE
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
Definition: ScalarEvolution.h:2229
llvm::tgtok::TrueVal
@ TrueVal
Definition: TGLexer.h:62
llvm::ScalarEvolution::getNotSCEV
const SCEV * getNotSCEV(const SCEV *V)
Return the SCEV object corresponding to ~V.
Definition: ScalarEvolution.cpp:4485
llvm::ScalarEvolution::isKnownNegative
bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
Definition: ScalarEvolution.cpp:10548
llvm::ScalarEvolution::getSMinExpr
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.cpp:4230
llvm::SCEV::isZero
bool isZero() const
Return true if the expression is a constant zero.
Definition: ScalarEvolution.cpp:429
llvm::ScalarEvolution::getSCEVAtScope
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
Definition: ScalarEvolution.cpp:9495
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::ScalarEvolution::getExitCount
const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
Definition: ScalarEvolution.cpp:8149
llvm::SCEV::ExpressionSize
const unsigned short ExpressionSize
Definition: ScalarEvolution.h:87
llvm::codeview::PublicSymFlags::Function
@ Function
SetVector.h
llvm::SCEVComparePredicate::getPredicate
ICmpInst::Predicate getPredicate() const
Definition: ScalarEvolution.h:294
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::ScalarEvolution::ProperlyDominatesBlock
@ ProperlyDominatesBlock
The SCEV properly dominates the block.
Definition: ScalarEvolution.h:464