LLVM  15.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.
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 
362  assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
363  assert((Mask & IncrementNoWrapMask) == Mask && "Invalid mask value!");
364 
366  }
367 
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.
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.
470  int Mask) {
471  return (SCEV::NoWrapFlags)(Flags & Mask);
472  }
474  SCEV::NoWrapFlags OnFlags) {
475  return (SCEV::NoWrapFlags)(Flags | OnFlags);
476  }
479  return (SCEV::NoWrapFlags)(Flags & ~OffFlags);
480  }
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)?
534  const SCEV *LHS, const SCEV *RHS);
535 
536  /// Parse NSW/NUW flags from add/sub/mul IR binary operation \p Op into
537  /// SCEV no-wrap flags, and deduce flag[s] that aren't known yet.
538  /// Does not mutate the original instruction.
539  std::pair<SCEV::NoWrapFlags, bool /*Deduced*/>
541 
542  /// Notify this ScalarEvolution that \p User directly uses SCEVs in \p Ops.
543  void registerUser(const SCEV *User, ArrayRef<const SCEV *> Ops);
544 
545  /// Return true if the SCEV expression contains an undef value.
546  bool containsUndefs(const SCEV *S) const;
547 
548  /// Return true if the SCEV expression contains a Value that has been
549  /// optimised out and is now a nullptr.
550  bool containsErasedValue(const SCEV *S) const;
551 
552  /// Return a SCEV expression for the full generality of the specified
553  /// expression.
554  const SCEV *getSCEV(Value *V);
555 
556  const SCEV *getConstant(ConstantInt *V);
557  const SCEV *getConstant(const APInt &Val);
558  const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false);
559  const SCEV *getLosslessPtrToIntExpr(const SCEV *Op, unsigned Depth = 0);
560  const SCEV *getPtrToIntExpr(const SCEV *Op, Type *Ty);
561  const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
562  const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
563  const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
564  const SCEV *getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty);
565  const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty);
568  unsigned Depth = 0);
569  const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS,
571  unsigned Depth = 0) {
573  return getAddExpr(Ops, Flags, Depth);
574  }
575  const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
577  unsigned Depth = 0) {
578  SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
579  return getAddExpr(Ops, Flags, Depth);
580  }
583  unsigned Depth = 0);
584  const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS,
586  unsigned Depth = 0) {
588  return getMulExpr(Ops, Flags, Depth);
589  }
590  const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
592  unsigned Depth = 0) {
593  SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
594  return getMulExpr(Ops, Flags, Depth);
595  }
596  const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS);
597  const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS);
598  const SCEV *getURemExpr(const SCEV *LHS, const SCEV *RHS);
599  const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L,
600  SCEV::NoWrapFlags Flags);
602  const Loop *L, SCEV::NoWrapFlags Flags);
604  const Loop *L, SCEV::NoWrapFlags Flags) {
605  SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end());
606  return getAddRecExpr(NewOp, L, Flags);
607  }
608 
609  /// Checks if \p SymbolicPHI can be rewritten as an AddRecExpr under some
610  /// Predicates. If successful return these <AddRecExpr, Predicates>;
611  /// The function is intended to be called from PSCEV (the caller will decide
612  /// whether to actually add the predicates and carry out the rewrites).
614  createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI);
615 
616  /// Returns an expression for a GEP
617  ///
618  /// \p GEP The GEP. The indices contained in the GEP itself are ignored,
619  /// instead we use IndexExprs.
620  /// \p IndexExprs The expressions for the indices.
621  const SCEV *getGEPExpr(GEPOperator *GEP,
622  const SmallVectorImpl<const SCEV *> &IndexExprs);
623  const SCEV *getAbsExpr(const SCEV *Op, bool IsNSW);
628  const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS);
630  const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS);
632  const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS);
634  const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS,
635  bool Sequential = false);
637  bool Sequential = false);
638  const SCEV *getUnknown(Value *V);
639  const SCEV *getCouldNotCompute();
640 
641  /// Return a SCEV for the constant 0 of a specific type.
642  const SCEV *getZero(Type *Ty) { return getConstant(Ty, 0); }
643 
644  /// Return a SCEV for the constant 1 of a specific type.
645  const SCEV *getOne(Type *Ty) { return getConstant(Ty, 1); }
646 
647  /// Return a SCEV for the constant -1 of a specific type.
648  const SCEV *getMinusOne(Type *Ty) {
649  return getConstant(Ty, -1, /*isSigned=*/true);
650  }
651 
652  /// Return an expression for sizeof ScalableTy that is type IntTy, where
653  /// ScalableTy is a scalable vector type.
654  const SCEV *getSizeOfScalableVectorExpr(Type *IntTy,
655  ScalableVectorType *ScalableTy);
656 
657  /// Return an expression for the alloc size of AllocTy that is type IntTy
658  const SCEV *getSizeOfExpr(Type *IntTy, Type *AllocTy);
659 
660  /// Return an expression for the store size of StoreTy that is type IntTy
661  const SCEV *getStoreSizeOfExpr(Type *IntTy, Type *StoreTy);
662 
663  /// Return an expression for offsetof on the given field with type IntTy
664  const SCEV *getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo);
665 
666  /// Return the SCEV object corresponding to -V.
667  const SCEV *getNegativeSCEV(const SCEV *V,
669 
670  /// Return the SCEV object corresponding to ~V.
671  const SCEV *getNotSCEV(const SCEV *V);
672 
673  /// Return LHS-RHS. Minus is represented in SCEV as A+B*-1.
674  ///
675  /// If the LHS and RHS are pointers which don't share a common base
676  /// (according to getPointerBase()), this returns a SCEVCouldNotCompute.
677  /// To compute the difference between two unrelated pointers, you can
678  /// explicitly convert the arguments using getPtrToIntExpr(), for pointer
679  /// types that support it.
680  const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
682  unsigned Depth = 0);
683 
684  /// Compute ceil(N / D). N and D are treated as unsigned values.
685  ///
686  /// Since SCEV doesn't have native ceiling division, this generates a
687  /// SCEV expression of the following form:
688  ///
689  /// umin(N, 1) + floor((N - umin(N, 1)) / D)
690  ///
691  /// A denominator of zero or poison is handled the same way as getUDivExpr().
692  const SCEV *getUDivCeilSCEV(const SCEV *N, const SCEV *D);
693 
694  /// Return a SCEV corresponding to a conversion of the input value to the
695  /// specified type. If the type must be extended, it is zero extended.
696  const SCEV *getTruncateOrZeroExtend(const SCEV *V, Type *Ty,
697  unsigned Depth = 0);
698 
699  /// Return a SCEV corresponding to a conversion of the input value to the
700  /// specified type. If the type must be extended, it is sign extended.
701  const SCEV *getTruncateOrSignExtend(const SCEV *V, Type *Ty,
702  unsigned Depth = 0);
703 
704  /// Return a SCEV corresponding to a conversion of the input value to the
705  /// specified type. If the type must be extended, it is zero extended. The
706  /// conversion must not be narrowing.
707  const SCEV *getNoopOrZeroExtend(const SCEV *V, Type *Ty);
708 
709  /// Return a SCEV corresponding to a conversion of the input value to the
710  /// specified type. If the type must be extended, it is sign extended. The
711  /// conversion must not be narrowing.
712  const SCEV *getNoopOrSignExtend(const SCEV *V, Type *Ty);
713 
714  /// Return a SCEV corresponding to a conversion of the input value to the
715  /// specified type. If the type must be extended, it is extended with
716  /// unspecified bits. The conversion must not be narrowing.
717  const SCEV *getNoopOrAnyExtend(const SCEV *V, Type *Ty);
718 
719  /// Return a SCEV corresponding to a conversion of the input value to the
720  /// specified type. The conversion must not be widening.
721  const SCEV *getTruncateOrNoop(const SCEV *V, Type *Ty);
722 
723  /// Promote the operands to the wider of the types using zero-extension, and
724  /// then perform a umax operation with them.
725  const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS);
726 
727  /// Promote the operands to the wider of the types using zero-extension, and
728  /// then perform a umin operation with them.
729  const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS,
730  bool Sequential = false);
731 
732  /// Promote the operands to the wider of the types using zero-extension, and
733  /// then perform a umin operation with them. N-ary function.
735  bool Sequential = false);
736 
737  /// Transitively follow the chain of pointer-type operands until reaching a
738  /// SCEV that does not have a single pointer operand. This returns a
739  /// SCEVUnknown pointer for well-formed pointer-type expressions, but corner
740  /// cases do exist.
741  const SCEV *getPointerBase(const SCEV *V);
742 
743  /// Compute an expression equivalent to S - getPointerBase(S).
744  const SCEV *removePointerBase(const SCEV *S);
745 
746  /// Return a SCEV expression for the specified value at the specified scope
747  /// in the program. The L value specifies a loop nest to evaluate the
748  /// expression at, where null is the top-level or a specified loop is
749  /// immediately inside of the loop.
750  ///
751  /// This method can be used to compute the exit value for a variable defined
752  /// in a loop by querying what the value will hold in the parent loop.
753  ///
754  /// In the case that a relevant loop exit value cannot be computed, the
755  /// original value V is returned.
756  const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L);
757 
758  /// This is a convenience function which does getSCEVAtScope(getSCEV(V), L).
759  const SCEV *getSCEVAtScope(Value *V, const Loop *L);
760 
761  /// Test whether entry to the loop is protected by a conditional between LHS
762  /// and RHS. This is used to help avoid max expressions in loop trip
763  /// counts, and to eliminate casts.
765  const SCEV *LHS, const SCEV *RHS);
766 
767  /// Test whether entry to the basic block is protected by a conditional
768  /// between LHS and RHS.
770  ICmpInst::Predicate Pred, const SCEV *LHS,
771  const SCEV *RHS);
772 
773  /// Test whether the backedge of the loop is protected by a conditional
774  /// between LHS and RHS. This is used to eliminate casts.
776  const SCEV *LHS, const SCEV *RHS);
777 
778  /// Convert from an "exit count" (i.e. "backedge taken count") to a "trip
779  /// count". A "trip count" is the number of times the header of the loop
780  /// will execute if an exit is taken after the specified number of backedges
781  /// have been taken. (e.g. TripCount = ExitCount + 1). Note that the
782  /// expression can overflow if ExitCount = UINT_MAX. \p Extend controls
783  /// how potential overflow is handled. If true, a wider result type is
784  /// returned. ex: EC = 255 (i8), TC = 256 (i9). If false, result unsigned
785  /// wraps with 2s-complement semantics. ex: EC = 255 (i8), TC = 0 (i8)
786  const SCEV *getTripCountFromExitCount(const SCEV *ExitCount,
787  bool Extend = true);
788 
789  /// Returns the exact trip count of the loop if we can compute it, and
790  /// the result is a small constant. '0' is used to represent an unknown
791  /// or non-constant trip count. Note that a trip count is simply one more
792  /// than the backedge taken count for the loop.
793  unsigned getSmallConstantTripCount(const Loop *L);
794 
795  /// Return the exact trip count for this loop if we exit through ExitingBlock.
796  /// '0' is used to represent an unknown or non-constant trip count. Note
797  /// that a trip count is simply one more than the backedge taken count for
798  /// the same exit.
799  /// This "trip count" assumes that control exits via ExitingBlock. More
800  /// precisely, it is the number of times that control will reach ExitingBlock
801  /// before taking the branch. For loops with multiple exits, it may not be
802  /// the number times that the loop header executes if the loop exits
803  /// prematurely via another branch.
804  unsigned getSmallConstantTripCount(const Loop *L,
805  const BasicBlock *ExitingBlock);
806 
807  /// Returns the upper bound of the loop trip count as a normal unsigned
808  /// value.
809  /// Returns 0 if the trip count is unknown or not constant.
810  unsigned getSmallConstantMaxTripCount(const Loop *L);
811 
812  /// Returns the upper bound of the loop trip count infered from array size.
813  /// Can not access bytes starting outside the statically allocated size
814  /// without being immediate UB.
815  /// Returns SCEVCouldNotCompute if the trip count could not inferred
816  /// from array accesses.
817  const SCEV *getConstantMaxTripCountFromArray(const Loop *L);
818 
819  /// Returns the largest constant divisor of the trip count as a normal
820  /// unsigned value, if possible. This means that the actual trip count is
821  /// always a multiple of the returned value. Returns 1 if the trip count is
822  /// unknown or not guaranteed to be the multiple of a constant., Will also
823  /// return 1 if the trip count is very large (>= 2^32).
824  /// Note that the argument is an exit count for loop L, NOT a trip count.
825  unsigned getSmallConstantTripMultiple(const Loop *L,
826  const SCEV *ExitCount);
827 
828  /// Returns the largest constant divisor of the trip count of the
829  /// loop. Will return 1 if no trip count could be computed, or if a
830  /// divisor could not be found.
831  unsigned getSmallConstantTripMultiple(const Loop *L);
832 
833  /// Returns the largest constant divisor of the trip count of this loop as a
834  /// normal unsigned value, if possible. This means that the actual trip
835  /// count is always a multiple of the returned value (don't forget the trip
836  /// count could very well be zero as well!). As explained in the comments
837  /// for getSmallConstantTripCount, this assumes that control exits the loop
838  /// via ExitingBlock.
839  unsigned getSmallConstantTripMultiple(const Loop *L,
840  const BasicBlock *ExitingBlock);
841 
842  /// The terms "backedge taken count" and "exit count" are used
843  /// interchangeably to refer to the number of times the backedge of a loop
844  /// has executed before the loop is exited.
846  /// An expression exactly describing the number of times the backedge has
847  /// executed when a loop is exited.
849  /// A constant which provides an upper bound on the exact trip count.
851  /// An expression which provides an upper bound on the exact trip count.
853  };
854 
855  /// Return the number of times the backedge executes before the given exit
856  /// would be taken; if not exactly computable, return SCEVCouldNotCompute.
857  /// For a single exit loop, this value is equivelent to the result of
858  /// getBackedgeTakenCount. The loop is guaranteed to exit (via *some* exit)
859  /// before the backedge is executed (ExitCount + 1) times. Note that there
860  /// is no guarantee about *which* exit is taken on the exiting iteration.
861  const SCEV *getExitCount(const Loop *L, const BasicBlock *ExitingBlock,
863 
864  /// If the specified loop has a predictable backedge-taken count, return it,
865  /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count is
866  /// the number of times the loop header will be branched to from within the
867  /// loop, assuming there are no abnormal exists like exception throws. This is
868  /// one less than the trip count of the loop, since it doesn't count the first
869  /// iteration, when the header is branched to from outside the loop.
870  ///
871  /// Note that it is not valid to call this method on a loop without a
872  /// loop-invariant backedge-taken count (see
873  /// hasLoopInvariantBackedgeTakenCount).
875 
876  /// Similar to getBackedgeTakenCount, except it will add a set of
877  /// SCEV predicates to Predicates that are required to be true in order for
878  /// the answer to be correct. Predicates can be checked with run-time
879  /// checks and can be used to perform loop versioning.
880  const SCEV *getPredicatedBackedgeTakenCount(const Loop *L,
882 
883  /// When successful, this returns a SCEVConstant that is greater than or equal
884  /// to (i.e. a "conservative over-approximation") of the value returend by
885  /// getBackedgeTakenCount. If such a value cannot be computed, it returns the
886  /// SCEVCouldNotCompute object.
889  }
890 
891  /// When successful, this returns a SCEV that is greater than or equal
892  /// to (i.e. a "conservative over-approximation") of the value returend by
893  /// getBackedgeTakenCount. If such a value cannot be computed, it returns the
894  /// SCEVCouldNotCompute object.
897  }
898 
899  /// Return true if the backedge taken count is either the value returned by
900  /// getConstantMaxBackedgeTakenCount or zero.
901  bool isBackedgeTakenCountMaxOrZero(const Loop *L);
902 
903  /// Return true if the specified loop has an analyzable loop-invariant
904  /// backedge-taken count.
906 
907  // This method should be called by the client when it made any change that
908  // would invalidate SCEV's answers, and the client wants to remove all loop
909  // information held internally by ScalarEvolution. This is intended to be used
910  // when the alternative to forget a loop is too expensive (i.e. large loop
911  // bodies).
912  void forgetAllLoops();
913 
914  /// This method should be called by the client when it has changed a loop in
915  /// a way that may effect ScalarEvolution's ability to compute a trip count,
916  /// or if the loop is deleted. This call is potentially expensive for large
917  /// loop bodies.
918  void forgetLoop(const Loop *L);
919 
920  // This method invokes forgetLoop for the outermost loop of the given loop
921  // \p L, making ScalarEvolution forget about all this subtree. This needs to
922  // be done whenever we make a transform that may affect the parameters of the
923  // outer loop, such as exit counts for branches.
924  void forgetTopmostLoop(const Loop *L);
925 
926  /// This method should be called by the client when it has changed a value
927  /// in a way that may effect its value, or which may disconnect it from a
928  /// def-use chain linking it to a loop.
929  void forgetValue(Value *V);
930 
931  /// Called when the client has changed the disposition of values in
932  /// this loop.
933  ///
934  /// We don't have a way to invalidate per-loop dispositions. Clear and
935  /// recompute is simpler.
936  void forgetLoopDispositions(const Loop *L);
937 
938  /// Determine the minimum number of zero bits that S is guaranteed to end in
939  /// (at every loop iteration). It is, at the same time, the minimum number
940  /// of times S is divisible by 2. For example, given {4,+,8} it returns 2.
941  /// If S is guaranteed to be 0, it returns the bitwidth of S.
943 
944  /// Determine the unsigned range for a particular SCEV.
945  /// NOTE: This returns a copy of the reference returned by getRangeRef.
947  return getRangeRef(S, HINT_RANGE_UNSIGNED);
948  }
949 
950  /// Determine the min of the unsigned range for a particular SCEV.
952  return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMin();
953  }
954 
955  /// Determine the max of the unsigned range for a particular SCEV.
957  return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMax();
958  }
959 
960  /// Determine the signed range for a particular SCEV.
961  /// NOTE: This returns a copy of the reference returned by getRangeRef.
963  return getRangeRef(S, HINT_RANGE_SIGNED);
964  }
965 
966  /// Determine the min of the signed range for a particular SCEV.
968  return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMin();
969  }
970 
971  /// Determine the max of the signed range for a particular SCEV.
973  return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMax();
974  }
975 
976  /// Test if the given expression is known to be negative.
977  bool isKnownNegative(const SCEV *S);
978 
979  /// Test if the given expression is known to be positive.
980  bool isKnownPositive(const SCEV *S);
981 
982  /// Test if the given expression is known to be non-negative.
983  bool isKnownNonNegative(const SCEV *S);
984 
985  /// Test if the given expression is known to be non-positive.
986  bool isKnownNonPositive(const SCEV *S);
987 
988  /// Test if the given expression is known to be non-zero.
989  bool isKnownNonZero(const SCEV *S);
990 
991  /// Splits SCEV expression \p S into two SCEVs. One of them is obtained from
992  /// \p S by substitution of all AddRec sub-expression related to loop \p L
993  /// with initial value of that SCEV. The second is obtained from \p S by
994  /// substitution of all AddRec sub-expressions related to loop \p L with post
995  /// increment of this AddRec in the loop \p L. In both cases all other AddRec
996  /// sub-expressions (not related to \p L) remain the same.
997  /// If the \p S contains non-invariant unknown SCEV the function returns
998  /// CouldNotCompute SCEV in both values of std::pair.
999  /// For example, for SCEV S={0, +, 1}<L1> + {0, +, 1}<L2> and loop L=L1
1000  /// the function returns pair:
1001  /// first = {0, +, 1}<L2>
1002  /// second = {1, +, 1}<L1> + {0, +, 1}<L2>
1003  /// We can see that for the first AddRec sub-expression it was replaced with
1004  /// 0 (initial value) for the first element and to {1, +, 1}<L1> (post
1005  /// increment value) for the second one. In both cases AddRec expression
1006  /// related to L2 remains the same.
1007  std::pair<const SCEV *, const SCEV *> SplitIntoInitAndPostInc(const Loop *L,
1008  const SCEV *S);
1009 
1010  /// We'd like to check the predicate on every iteration of the most dominated
1011  /// loop between loops used in LHS and RHS.
1012  /// To do this we use the following list of steps:
1013  /// 1. Collect set S all loops on which either LHS or RHS depend.
1014  /// 2. If S is non-empty
1015  /// a. Let PD be the element of S which is dominated by all other elements.
1016  /// b. Let E(LHS) be value of LHS on entry of PD.
1017  /// To get E(LHS), we should just take LHS and replace all AddRecs that are
1018  /// attached to PD on with their entry values.
1019  /// Define E(RHS) in the same way.
1020  /// c. Let B(LHS) be value of L on backedge of PD.
1021  /// To get B(LHS), we should just take LHS and replace all AddRecs that are
1022  /// attached to PD on with their backedge values.
1023  /// Define B(RHS) in the same way.
1024  /// d. Note that E(LHS) and E(RHS) are automatically available on entry of PD,
1025  /// so we can assert on that.
1026  /// e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) &&
1027  /// isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS))
1028  bool isKnownViaInduction(ICmpInst::Predicate Pred, const SCEV *LHS,
1029  const SCEV *RHS);
1030 
1031  /// Test if the given expression is known to satisfy the condition described
1032  /// by Pred, LHS, and RHS.
1033  bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS,
1034  const SCEV *RHS);
1035 
1036  /// Check whether the condition described by Pred, LHS, and RHS is true or
1037  /// false. If we know it, return the evaluation of this condition. If neither
1038  /// is proved, return None.
1040  const SCEV *RHS);
1041 
1042  /// Test if the given expression is known to satisfy the condition described
1043  /// by Pred, LHS, and RHS in the given Context.
1044  bool isKnownPredicateAt(ICmpInst::Predicate Pred, const SCEV *LHS,
1045  const SCEV *RHS, const Instruction *CtxI);
1046 
1047  /// Check whether the condition described by Pred, LHS, and RHS is true or
1048  /// false in the given \p Context. If we know it, return the evaluation of
1049  /// this condition. If neither is proved, return None.
1051  const SCEV *RHS, const Instruction *CtxI);
1052 
1053  /// Test if the condition described by Pred, LHS, RHS is known to be true on
1054  /// every iteration of the loop of the recurrency LHS.
1056  const SCEVAddRecExpr *LHS, const SCEV *RHS);
1057 
1058  /// A predicate is said to be monotonically increasing if may go from being
1059  /// false to being true as the loop iterates, but never the other way
1060  /// around. A predicate is said to be monotonically decreasing if may go
1061  /// from being true to being false as the loop iterates, but never the other
1062  /// way around.
1066  };
1067 
1068  /// If, for all loop invariant X, the predicate "LHS `Pred` X" is
1069  /// monotonically increasing or decreasing, returns
1070  /// Some(MonotonicallyIncreasing) and Some(MonotonicallyDecreasing)
1071  /// respectively. If we could not prove either of these facts, returns None.
1074  ICmpInst::Predicate Pred);
1075 
1078  const SCEV *LHS;
1079  const SCEV *RHS;
1080 
1082  const SCEV *RHS)
1083  : Pred(Pred), LHS(LHS), RHS(RHS) {}
1084  };
1085  /// If the result of the predicate LHS `Pred` RHS is loop invariant with
1086  /// respect to L, return a LoopInvariantPredicate with LHS and RHS being
1087  /// invariants, available at L's entry. Otherwise, return None.
1090  const SCEV *RHS, const Loop *L);
1091 
1092  /// If the result of the predicate LHS `Pred` RHS is loop invariant with
1093  /// respect to L at given Context during at least first MaxIter iterations,
1094  /// return a LoopInvariantPredicate with LHS and RHS being invariants,
1095  /// available at L's entry. Otherwise, return None. The predicate should be
1096  /// the loop's exit condition.
1099  const SCEV *LHS,
1100  const SCEV *RHS, const Loop *L,
1101  const Instruction *CtxI,
1102  const SCEV *MaxIter);
1103 
1104  /// Simplify LHS and RHS in a comparison with predicate Pred. Return true
1105  /// iff any changes were made. If the operands are provably equal or
1106  /// unequal, LHS and RHS are set to the same value and Pred is set to either
1107  /// ICMP_EQ or ICMP_NE. ControllingFiniteLoop is set if this comparison
1108  /// controls the exit of a loop known to have a finite number of iterations.
1109  bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS,
1110  const SCEV *&RHS, unsigned Depth = 0,
1111  bool ControllingFiniteLoop = false);
1112 
1113  /// Return the "disposition" of the given SCEV with respect to the given
1114  /// loop.
1115  LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L);
1116 
1117  /// Return true if the value of the given SCEV is unchanging in the
1118  /// specified loop.
1119  bool isLoopInvariant(const SCEV *S, const Loop *L);
1120 
1121  /// Determine if the SCEV can be evaluated at loop's entry. It is true if it
1122  /// doesn't depend on a SCEVUnknown of an instruction which is dominated by
1123  /// the header of loop L.
1124  bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L);
1125 
1126  /// Return true if the given SCEV changes value in a known way in the
1127  /// specified loop. This property being true implies that the value is
1128  /// variant in the loop AND that we can emit an expression to compute the
1129  /// value of the expression at any particular loop iteration.
1130  bool hasComputableLoopEvolution(const SCEV *S, const Loop *L);
1131 
1132  /// Return the "disposition" of the given SCEV with respect to the given
1133  /// block.
1135 
1136  /// Return true if elements that makes up the given SCEV dominate the
1137  /// specified basic block.
1138  bool dominates(const SCEV *S, const BasicBlock *BB);
1139 
1140  /// Return true if elements that makes up the given SCEV properly dominate
1141  /// the specified basic block.
1142  bool properlyDominates(const SCEV *S, const BasicBlock *BB);
1143 
1144  /// Test whether the given SCEV has Op as a direct or indirect operand.
1145  bool hasOperand(const SCEV *S, const SCEV *Op) const;
1146 
1147  /// Return the size of an element read or written by Inst.
1148  const SCEV *getElementSize(Instruction *Inst);
1149 
1150  void print(raw_ostream &OS) const;
1151  void verify() const;
1152  bool invalidate(Function &F, const PreservedAnalyses &PA,
1154 
1155  /// Return the DataLayout associated with the module this SCEV instance is
1156  /// operating on.
1157  const DataLayout &getDataLayout() const {
1158  return F.getParent()->getDataLayout();
1159  }
1160 
1161  const SCEVPredicate *getEqualPredicate(const SCEV *LHS, const SCEV *RHS);
1163  const SCEV *LHS, const SCEV *RHS);
1164 
1165  const SCEVPredicate *
1166  getWrapPredicate(const SCEVAddRecExpr *AR,
1168 
1169  /// Re-writes the SCEV according to the Predicates in \p A.
1170  const SCEV *rewriteUsingPredicate(const SCEV *S, const Loop *L,
1171  const SCEVPredicate &A);
1172  /// Tries to convert the \p S expression to an AddRec expression,
1173  /// adding additional predicates to \p Preds as required.
1175  const SCEV *S, const Loop *L,
1177 
1178  /// Compute \p LHS - \p RHS and returns the result as an APInt if it is a
1179  /// constant, and None if it isn't.
1180  ///
1181  /// This is intended to be a cheaper version of getMinusSCEV. We can be
1182  /// frugal here since we just bail out of actually constructing and
1183  /// canonicalizing an expression in the cases where the result isn't going
1184  /// to be a constant.
1186 
1187  /// Update no-wrap flags of an AddRec. This may drop the cached info about
1188  /// this AddRec (such as range info) in case if new flags may potentially
1189  /// sharpen it.
1190  void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags);
1191 
1192  /// Try to apply information from loop guards for \p L to \p Expr.
1193  const SCEV *applyLoopGuards(const SCEV *Expr, const Loop *L);
1194 
1195  /// Return true if the loop has no abnormal exits. That is, if the loop
1196  /// is not infinite, it must exit through an explicit edge in the CFG.
1197  /// (As opposed to either a) throwing out of the function or b) entering a
1198  /// well defined infinite loop in some callee.)
1199  bool loopHasNoAbnormalExits(const Loop *L) {
1200  return getLoopProperties(L).HasNoAbnormalExits;
1201  }
1202 
1203  /// Return true if this loop is finite by assumption. That is,
1204  /// to be infinite, it must also be undefined.
1205  bool loopIsFiniteByAssumption(const Loop *L);
1206 
1207 private:
1208  /// A CallbackVH to arrange for ScalarEvolution to be notified whenever a
1209  /// Value is deleted.
1210  class SCEVCallbackVH final : public CallbackVH {
1211  ScalarEvolution *SE;
1212 
1213  void deleted() override;
1214  void allUsesReplacedWith(Value *New) override;
1215 
1216  public:
1217  SCEVCallbackVH(Value *V, ScalarEvolution *SE = nullptr);
1218  };
1219 
1220  friend class SCEVCallbackVH;
1221  friend class SCEVExpander;
1222  friend class SCEVUnknown;
1223 
1224  /// The function we are analyzing.
1225  Function &F;
1226 
1227  /// Does the module have any calls to the llvm.experimental.guard intrinsic
1228  /// at all? If this is false, we avoid doing work that will only help if
1229  /// thare are guards present in the IR.
1230  bool HasGuards;
1231 
1232  /// The target library information for the target we are targeting.
1233  TargetLibraryInfo &TLI;
1234 
1235  /// The tracker for \@llvm.assume intrinsics in this function.
1236  AssumptionCache &AC;
1237 
1238  /// The dominator tree.
1239  DominatorTree &DT;
1240 
1241  /// The loop information for the function we are currently analyzing.
1242  LoopInfo &LI;
1243 
1244  /// This SCEV is used to represent unknown trip counts and things.
1245  std::unique_ptr<SCEVCouldNotCompute> CouldNotCompute;
1246 
1247  /// The type for HasRecMap.
1249 
1250  /// This is a cache to record whether a SCEV contains any scAddRecExpr.
1251  HasRecMapType HasRecMap;
1252 
1253  /// The type for ExprValueMap.
1256 
1257  /// ExprValueMap -- This map records the original values from which
1258  /// the SCEV expr is generated from.
1259  ExprValueMapType ExprValueMap;
1260 
1261  /// The type for ValueExprMap.
1262  using ValueExprMapType =
1264 
1265  /// This is a cache of the values we have analyzed so far.
1266  ValueExprMapType ValueExprMap;
1267 
1268  /// Mark predicate values currently being processed by isImpliedCond.
1269  SmallPtrSet<const Value *, 6> PendingLoopPredicates;
1270 
1271  /// Mark SCEVUnknown Phis currently being processed by getRangeRef.
1272  SmallPtrSet<const PHINode *, 6> PendingPhiRanges;
1273 
1274  // Mark SCEVUnknown Phis currently being processed by isImpliedViaMerge.
1275  SmallPtrSet<const PHINode *, 6> PendingMerges;
1276 
1277  /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of
1278  /// conditions dominating the backedge of a loop.
1279  bool WalkingBEDominatingConds = false;
1280 
1281  /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a
1282  /// predicate by splitting it into a set of independent predicates.
1283  bool ProvingSplitPredicate = false;
1284 
1285  /// Memoized values for the GetMinTrailingZeros
1286  DenseMap<const SCEV *, uint32_t> MinTrailingZerosCache;
1287 
1288  /// Return the Value set from which the SCEV expr is generated.
1289  ArrayRef<Value *> getSCEVValues(const SCEV *S);
1290 
1291  /// Private helper method for the GetMinTrailingZeros method
1292  uint32_t GetMinTrailingZerosImpl(const SCEV *S);
1293 
1294  /// Information about the number of loop iterations for which a loop exit's
1295  /// branch condition evaluates to the not-taken path. This is a temporary
1296  /// pair of exact and max expressions that are eventually summarized in
1297  /// ExitNotTakenInfo and BackedgeTakenInfo.
1298  struct ExitLimit {
1299  const SCEV *ExactNotTaken; // The exit is not taken exactly this many times
1300  const SCEV *MaxNotTaken; // The exit is not taken at most this many times
1301 
1302  // Not taken either exactly MaxNotTaken or zero times
1303  bool MaxOrZero = false;
1304 
1305  /// A set of predicate guards for this ExitLimit. The result is only valid
1306  /// if all of the predicates in \c Predicates evaluate to 'true' at
1307  /// run-time.
1309 
1310  void addPredicate(const SCEVPredicate *P) {
1311  assert(!isa<SCEVUnionPredicate>(P) && "Only add leaf predicates here!");
1312  Predicates.insert(P);
1313  }
1314 
1315  /// Construct either an exact exit limit from a constant, or an unknown
1316  /// one from a SCEVCouldNotCompute. No other types of SCEVs are allowed
1317  /// as arguments and asserts enforce that internally.
1318  /*implicit*/ ExitLimit(const SCEV *E);
1319 
1320  ExitLimit(
1321  const SCEV *E, const SCEV *M, bool MaxOrZero,
1322  ArrayRef<const SmallPtrSetImpl<const SCEVPredicate *> *> PredSetList);
1323 
1324  ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero,
1326 
1327  ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero);
1328 
1329  /// Test whether this ExitLimit contains any computed information, or
1330  /// whether it's all SCEVCouldNotCompute values.
1331  bool hasAnyInfo() const {
1332  return !isa<SCEVCouldNotCompute>(ExactNotTaken) ||
1333  !isa<SCEVCouldNotCompute>(MaxNotTaken);
1334  }
1335 
1336  /// Test whether this ExitLimit contains all information.
1337  bool hasFullInfo() const {
1338  return !isa<SCEVCouldNotCompute>(ExactNotTaken);
1339  }
1340  };
1341 
1342  /// Information about the number of times a particular loop exit may be
1343  /// reached before exiting the loop.
1344  struct ExitNotTakenInfo {
1345  PoisoningVH<BasicBlock> ExitingBlock;
1346  const SCEV *ExactNotTaken;
1347  const SCEV *MaxNotTaken;
1348  SmallPtrSet<const SCEVPredicate *, 4> Predicates;
1349 
1350  explicit ExitNotTakenInfo(PoisoningVH<BasicBlock> ExitingBlock,
1351  const SCEV *ExactNotTaken,
1352  const SCEV *MaxNotTaken,
1353  const SmallPtrSet<const SCEVPredicate *, 4> &Predicates)
1354  : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken),
1355  MaxNotTaken(ExactNotTaken), Predicates(Predicates) {}
1356 
1357  bool hasAlwaysTruePredicate() const {
1358  return Predicates.empty();
1359  }
1360  };
1361 
1362  /// Information about the backedge-taken count of a loop. This currently
1363  /// includes an exact count and a maximum count.
1364  ///
1365  class BackedgeTakenInfo {
1366  friend class ScalarEvolution;
1367 
1368  /// A list of computable exits and their not-taken counts. Loops almost
1369  /// never have more than one computable exit.
1370  SmallVector<ExitNotTakenInfo, 1> ExitNotTaken;
1371 
1372  /// Expression indicating the least constant maximum backedge-taken count of
1373  /// the loop that is known, or a SCEVCouldNotCompute. This expression is
1374  /// only valid if the redicates associated with all loop exits are true.
1375  const SCEV *ConstantMax;
1376 
1377  /// Indicating if \c ExitNotTaken has an element for every exiting block in
1378  /// the loop.
1379  bool IsComplete;
1380 
1381  /// Expression indicating the least maximum backedge-taken count of the loop
1382  /// that is known, or a SCEVCouldNotCompute. Lazily computed on first query.
1383  const SCEV *SymbolicMax = nullptr;
1384 
1385  /// True iff the backedge is taken either exactly Max or zero times.
1386  bool MaxOrZero = false;
1387 
1388  bool isComplete() const { return IsComplete; }
1389  const SCEV *getConstantMax() const { return ConstantMax; }
1390 
1391  public:
1392  BackedgeTakenInfo() : ConstantMax(nullptr), IsComplete(false) {}
1393  BackedgeTakenInfo(BackedgeTakenInfo &&) = default;
1394  BackedgeTakenInfo &operator=(BackedgeTakenInfo &&) = default;
1395 
1396  using EdgeExitInfo = std::pair<BasicBlock *, ExitLimit>;
1397 
1398  /// Initialize BackedgeTakenInfo from a list of exact exit counts.
1399  BackedgeTakenInfo(ArrayRef<EdgeExitInfo> ExitCounts, bool IsComplete,
1400  const SCEV *ConstantMax, bool MaxOrZero);
1401 
1402  /// Test whether this BackedgeTakenInfo contains any computed information,
1403  /// or whether it's all SCEVCouldNotCompute values.
1404  bool hasAnyInfo() const {
1405  return !ExitNotTaken.empty() ||
1406  !isa<SCEVCouldNotCompute>(getConstantMax());
1407  }
1408 
1409  /// Test whether this BackedgeTakenInfo contains complete information.
1410  bool hasFullInfo() const { return isComplete(); }
1411 
1412  /// Return an expression indicating the exact *backedge-taken*
1413  /// count of the loop if it is known or SCEVCouldNotCompute
1414  /// otherwise. If execution makes it to the backedge on every
1415  /// iteration (i.e. there are no abnormal exists like exception
1416  /// throws and thread exits) then this is the number of times the
1417  /// loop header will execute minus one.
1418  ///
1419  /// If the SCEV predicate associated with the answer can be different
1420  /// from AlwaysTrue, we must add a (non null) Predicates argument.
1421  /// The SCEV predicate associated with the answer will be added to
1422  /// Predicates. A run-time check needs to be emitted for the SCEV
1423  /// predicate in order for the answer to be valid.
1424  ///
1425  /// Note that we should always know if we need to pass a predicate
1426  /// argument or not from the way the ExitCounts vector was computed.
1427  /// If we allowed SCEV predicates to be generated when populating this
1428  /// vector, this information can contain them and therefore a
1429  /// SCEVPredicate argument should be added to getExact.
1430  const SCEV *getExact(const Loop *L, ScalarEvolution *SE,
1431  SmallVector<const SCEVPredicate *, 4> *Predicates = nullptr) const;
1432 
1433  /// Return the number of times this loop exit may fall through to the back
1434  /// edge, or SCEVCouldNotCompute. The loop is guaranteed not to exit via
1435  /// this block before this number of iterations, but may exit via another
1436  /// block.
1437  const SCEV *getExact(const BasicBlock *ExitingBlock,
1438  ScalarEvolution *SE) const;
1439 
1440  /// Get the constant max backedge taken count for the loop.
1441  const SCEV *getConstantMax(ScalarEvolution *SE) const;
1442 
1443  /// Get the constant max backedge taken count for the particular loop exit.
1444  const SCEV *getConstantMax(const BasicBlock *ExitingBlock,
1445  ScalarEvolution *SE) const;
1446 
1447  /// Get the symbolic max backedge taken count for the loop.
1448  const SCEV *getSymbolicMax(const Loop *L, ScalarEvolution *SE);
1449 
1450  /// Return true if the number of times this backedge is taken is either the
1451  /// value returned by getConstantMax or zero.
1452  bool isConstantMaxOrZero(ScalarEvolution *SE) const;
1453  };
1454 
1455  /// Cache the backedge-taken count of the loops for this function as they
1456  /// are computed.
1457  DenseMap<const Loop *, BackedgeTakenInfo> BackedgeTakenCounts;
1458 
1459  /// Cache the predicated backedge-taken count of the loops for this
1460  /// function as they are computed.
1461  DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts;
1462 
1463  /// Loops whose backedge taken counts directly use this non-constant SCEV.
1464  DenseMap<const SCEV *, SmallPtrSet<PointerIntPair<const Loop *, 1, bool>, 4>>
1465  BECountUsers;
1466 
1467  /// This map contains entries for all of the PHI instructions that we
1468  /// attempt to compute constant evolutions for. This allows us to avoid
1469  /// potentially expensive recomputation of these properties. An instruction
1470  /// maps to null if we are unable to compute its exit value.
1471  DenseMap<PHINode *, Constant *> ConstantEvolutionLoopExitValue;
1472 
1473  /// This map contains entries for all the expressions that we attempt to
1474  /// compute getSCEVAtScope information for, which can be expensive in
1475  /// extreme cases.
1476  DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1477  ValuesAtScopes;
1478 
1479  /// Reverse map for invalidation purposes: Stores of which SCEV and which
1480  /// loop this is the value-at-scope of.
1481  DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1482  ValuesAtScopesUsers;
1483 
1484  /// Memoized computeLoopDisposition results.
1485  DenseMap<const SCEV *,
1486  SmallVector<PointerIntPair<const Loop *, 2, LoopDisposition>, 2>>
1487  LoopDispositions;
1488 
1489  struct LoopProperties {
1490  /// Set to true if the loop contains no instruction that can abnormally exit
1491  /// the loop (i.e. via throwing an exception, by terminating the thread
1492  /// cleanly or by infinite looping in a called function). Strictly
1493  /// speaking, the last one is not leaving the loop, but is identical to
1494  /// leaving the loop for reasoning about undefined behavior.
1495  bool HasNoAbnormalExits;
1496 
1497  /// Set to true if the loop contains no instruction that can have side
1498  /// effects (i.e. via throwing an exception, volatile or atomic access).
1499  bool HasNoSideEffects;
1500  };
1501 
1502  /// Cache for \c getLoopProperties.
1503  DenseMap<const Loop *, LoopProperties> LoopPropertiesCache;
1504 
1505  /// Return a \c LoopProperties instance for \p L, creating one if necessary.
1506  LoopProperties getLoopProperties(const Loop *L);
1507 
1508  bool loopHasNoSideEffects(const Loop *L) {
1509  return getLoopProperties(L).HasNoSideEffects;
1510  }
1511 
1512  /// Compute a LoopDisposition value.
1513  LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L);
1514 
1515  /// Memoized computeBlockDisposition results.
1516  DenseMap<
1517  const SCEV *,
1518  SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>>
1519  BlockDispositions;
1520 
1521  /// Compute a BlockDisposition value.
1522  BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB);
1523 
1524  /// Stores all SCEV that use a given SCEV as its direct operand.
1525  DenseMap<const SCEV *, SmallPtrSet<const SCEV *, 8> > SCEVUsers;
1526 
1527  /// Memoized results from getRange
1528  DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
1529 
1530  /// Memoized results from getRange
1531  DenseMap<const SCEV *, ConstantRange> SignedRanges;
1532 
1533  /// Used to parameterize getRange
1534  enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED };
1535 
1536  /// Set the memoized range for the given SCEV.
1537  const ConstantRange &setRange(const SCEV *S, RangeSignHint Hint,
1538  ConstantRange CR) {
1539  DenseMap<const SCEV *, ConstantRange> &Cache =
1540  Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges;
1541 
1542  auto Pair = Cache.try_emplace(S, std::move(CR));
1543  if (!Pair.second)
1544  Pair.first->second = std::move(CR);
1545  return Pair.first->second;
1546  }
1547 
1548  /// Determine the range for a particular SCEV.
1549  /// NOTE: This returns a reference to an entry in a cache. It must be
1550  /// copied if its needed for longer.
1551  const ConstantRange &getRangeRef(const SCEV *S, RangeSignHint Hint);
1552 
1553  /// Determines the range for the affine SCEVAddRecExpr {\p Start,+,\p Step}.
1554  /// Helper for \c getRange.
1555  ConstantRange getRangeForAffineAR(const SCEV *Start, const SCEV *Step,
1556  const SCEV *MaxBECount, unsigned BitWidth);
1557 
1558  /// Determines the range for the affine non-self-wrapping SCEVAddRecExpr {\p
1559  /// Start,+,\p Step}<nw>.
1560  ConstantRange getRangeForAffineNoSelfWrappingAR(const SCEVAddRecExpr *AddRec,
1561  const SCEV *MaxBECount,
1562  unsigned BitWidth,
1563  RangeSignHint SignHint);
1564 
1565  /// Try to compute a range for the affine SCEVAddRecExpr {\p Start,+,\p
1566  /// Step} by "factoring out" a ternary expression from the add recurrence.
1567  /// Helper called by \c getRange.
1568  ConstantRange getRangeViaFactoring(const SCEV *Start, const SCEV *Step,
1569  const SCEV *MaxBECount, unsigned BitWidth);
1570 
1571  /// If the unknown expression U corresponds to a simple recurrence, return
1572  /// a constant range which represents the entire recurrence. Note that
1573  /// *add* recurrences with loop invariant steps aren't represented by
1574  /// SCEVUnknowns and thus don't use this mechanism.
1575  ConstantRange getRangeForUnknownRecurrence(const SCEVUnknown *U);
1576 
1577  /// We know that there is no SCEV for the specified value. Analyze the
1578  /// expression.
1579  const SCEV *createSCEV(Value *V);
1580 
1581  /// Provide the special handling we need to analyze PHI SCEVs.
1582  const SCEV *createNodeForPHI(PHINode *PN);
1583 
1584  /// Helper function called from createNodeForPHI.
1585  const SCEV *createAddRecFromPHI(PHINode *PN);
1586 
1587  /// A helper function for createAddRecFromPHI to handle simple cases.
1588  const SCEV *createSimpleAffineAddRec(PHINode *PN, Value *BEValueV,
1589  Value *StartValueV);
1590 
1591  /// Helper function called from createNodeForPHI.
1592  const SCEV *createNodeFromSelectLikePHI(PHINode *PN);
1593 
1594  /// Provide special handling for a select-like instruction (currently this
1595  /// is either a select instruction or a phi node). \p I is the instruction
1596  /// being processed, and it is assumed equivalent to "Cond ? TrueVal :
1597  /// FalseVal".
1598  const SCEV *createNodeForSelectOrPHIInstWithICmpInstCond(Instruction *I,
1599  ICmpInst *Cond,
1600  Value *TrueVal,
1601  Value *FalseVal);
1602 
1603  /// See if we can model this select-like instruction via umin_seq expression.
1604  const SCEV *createNodeForSelectOrPHIViaUMinSeq(Value *I, Value *Cond,
1605  Value *TrueVal,
1606  Value *FalseVal);
1607 
1608  /// Given a value \p V, which is a select-like instruction (currently this is
1609  /// either a select instruction or a phi node), which is assumed equivalent to
1610  /// Cond ? TrueVal : FalseVal
1611  /// see if we can model it as a SCEV expression.
1612  const SCEV *createNodeForSelectOrPHI(Value *V, Value *Cond, Value *TrueVal,
1613  Value *FalseVal);
1614 
1615  /// Provide the special handling we need to analyze GEP SCEVs.
1616  const SCEV *createNodeForGEP(GEPOperator *GEP);
1617 
1618  /// Implementation code for getSCEVAtScope; called at most once for each
1619  /// SCEV+Loop pair.
1620  const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L);
1621 
1622  /// Return the BackedgeTakenInfo for the given loop, lazily computing new
1623  /// values if the loop hasn't been analyzed yet. The returned result is
1624  /// guaranteed not to be predicated.
1625  BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L);
1626 
1627  /// Similar to getBackedgeTakenInfo, but will add predicates as required
1628  /// with the purpose of returning complete information.
1629  const BackedgeTakenInfo &getPredicatedBackedgeTakenInfo(const Loop *L);
1630 
1631  /// Compute the number of times the specified loop will iterate.
1632  /// If AllowPredicates is set, we will create new SCEV predicates as
1633  /// necessary in order to return an exact answer.
1634  BackedgeTakenInfo computeBackedgeTakenCount(const Loop *L,
1635  bool AllowPredicates = false);
1636 
1637  /// Compute the number of times the backedge of the specified loop will
1638  /// execute if it exits via the specified block. If AllowPredicates is set,
1639  /// this call will try to use a minimal set of SCEV predicates in order to
1640  /// return an exact answer.
1641  ExitLimit computeExitLimit(const Loop *L, BasicBlock *ExitingBlock,
1642  bool AllowPredicates = false);
1643 
1644  /// Compute the number of times the backedge of the specified loop will
1645  /// execute if its exit condition were a conditional branch of ExitCond.
1646  ///
1647  /// \p ControlsExit is true if ExitCond directly controls the exit
1648  /// branch. In this case, we can assume that the loop exits only if the
1649  /// condition is true and can infer that failing to meet the condition prior
1650  /// to integer wraparound results in undefined behavior.
1651  ///
1652  /// If \p AllowPredicates is set, this call will try to use a minimal set of
1653  /// SCEV predicates in order to return an exact answer.
1654  ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond,
1655  bool ExitIfTrue, bool ControlsExit,
1656  bool AllowPredicates = false);
1657 
1658  /// Return a symbolic upper bound for the backedge taken count of the loop.
1659  /// This is more general than getConstantMaxBackedgeTakenCount as it returns
1660  /// an arbitrary expression as opposed to only constants.
1661  const SCEV *computeSymbolicMaxBackedgeTakenCount(const Loop *L);
1662 
1663  // Helper functions for computeExitLimitFromCond to avoid exponential time
1664  // complexity.
1665 
1666  class ExitLimitCache {
1667  // It may look like we need key on the whole (L, ExitIfTrue, ControlsExit,
1668  // AllowPredicates) tuple, but recursive calls to
1669  // computeExitLimitFromCondCached from computeExitLimitFromCondImpl only
1670  // vary the in \c ExitCond and \c ControlsExit parameters. We remember the
1671  // initial values of the other values to assert our assumption.
1672  SmallDenseMap<PointerIntPair<Value *, 1>, ExitLimit> TripCountMap;
1673 
1674  const Loop *L;
1675  bool ExitIfTrue;
1676  bool AllowPredicates;
1677 
1678  public:
1679  ExitLimitCache(const Loop *L, bool ExitIfTrue, bool AllowPredicates)
1680  : L(L), ExitIfTrue(ExitIfTrue), AllowPredicates(AllowPredicates) {}
1681 
1682  Optional<ExitLimit> find(const Loop *L, Value *ExitCond, bool ExitIfTrue,
1683  bool ControlsExit, bool AllowPredicates);
1684 
1685  void insert(const Loop *L, Value *ExitCond, bool ExitIfTrue,
1686  bool ControlsExit, bool AllowPredicates, const ExitLimit &EL);
1687  };
1688 
1689  using ExitLimitCacheTy = ExitLimitCache;
1690 
1691  ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache,
1692  const Loop *L, Value *ExitCond,
1693  bool ExitIfTrue,
1694  bool ControlsExit,
1695  bool AllowPredicates);
1696  ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache, const Loop *L,
1697  Value *ExitCond, bool ExitIfTrue,
1698  bool ControlsExit,
1699  bool AllowPredicates);
1700  Optional<ScalarEvolution::ExitLimit>
1701  computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache, const Loop *L,
1702  Value *ExitCond, bool ExitIfTrue,
1703  bool ControlsExit, bool AllowPredicates);
1704 
1705  /// Compute the number of times the backedge of the specified loop will
1706  /// execute if its exit condition were a conditional branch of the ICmpInst
1707  /// ExitCond and ExitIfTrue. If AllowPredicates is set, this call will try
1708  /// to use a minimal set of SCEV predicates in order to return an exact
1709  /// answer.
1710  ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond,
1711  bool ExitIfTrue,
1712  bool IsSubExpr,
1713  bool AllowPredicates = false);
1714 
1715  /// Variant of previous which takes the components representing an ICmp
1716  /// as opposed to the ICmpInst itself. Note that the prior version can
1717  /// return more precise results in some cases and is preferred when caller
1718  /// has a materialized ICmp.
1719  ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst::Predicate Pred,
1720  const SCEV *LHS, const SCEV *RHS,
1721  bool IsSubExpr,
1722  bool AllowPredicates = false);
1723 
1724  /// Compute the number of times the backedge of the specified loop will
1725  /// execute if its exit condition were a switch with a single exiting case
1726  /// to ExitingBB.
1727  ExitLimit computeExitLimitFromSingleExitSwitch(const Loop *L,
1728  SwitchInst *Switch,
1729  BasicBlock *ExitingBB,
1730  bool IsSubExpr);
1731 
1732  /// Compute the exit limit of a loop that is controlled by a
1733  /// "(IV >> 1) != 0" type comparison. We cannot compute the exact trip
1734  /// count in these cases (since SCEV has no way of expressing them), but we
1735  /// can still sometimes compute an upper bound.
1736  ///
1737  /// Return an ExitLimit for a loop whose backedge is guarded by `LHS Pred
1738  /// RHS`.
1739  ExitLimit computeShiftCompareExitLimit(Value *LHS, Value *RHS, const Loop *L,
1740  ICmpInst::Predicate Pred);
1741 
1742  /// If the loop is known to execute a constant number of times (the
1743  /// condition evolves only from constants), try to evaluate a few iterations
1744  /// of the loop until we get the exit condition gets a value of ExitWhen
1745  /// (true or false). If we cannot evaluate the exit count of the loop,
1746  /// return CouldNotCompute.
1747  const SCEV *computeExitCountExhaustively(const Loop *L, Value *Cond,
1748  bool ExitWhen);
1749 
1750  /// Return the number of times an exit condition comparing the specified
1751  /// value to zero will execute. If not computable, return CouldNotCompute.
1752  /// If AllowPredicates is set, this call will try to use a minimal set of
1753  /// SCEV predicates in order to return an exact answer.
1754  ExitLimit howFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr,
1755  bool AllowPredicates = false);
1756 
1757  /// Return the number of times an exit condition checking the specified
1758  /// value for nonzero will execute. If not computable, return
1759  /// CouldNotCompute.
1760  ExitLimit howFarToNonZero(const SCEV *V, const Loop *L);
1761 
1762  /// Return the number of times an exit condition containing the specified
1763  /// less-than comparison will execute. If not computable, return
1764  /// CouldNotCompute.
1765  ///
1766  /// \p isSigned specifies whether the less-than is signed.
1767  ///
1768  /// \p ControlsExit is true when the LHS < RHS condition directly controls
1769  /// the branch (loops exits only if condition is true). In this case, we can
1770  /// use NoWrapFlags to skip overflow checks.
1771  ///
1772  /// If \p AllowPredicates is set, this call will try to use a minimal set of
1773  /// SCEV predicates in order to return an exact answer.
1774  ExitLimit howManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
1775  bool isSigned, bool ControlsExit,
1776  bool AllowPredicates = false);
1777 
1778  ExitLimit howManyGreaterThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
1779  bool isSigned, bool IsSubExpr,
1780  bool AllowPredicates = false);
1781 
1782  /// Return a predecessor of BB (which may not be an immediate predecessor)
1783  /// which has exactly one successor from which BB is reachable, or null if
1784  /// no such block is found.
1785  std::pair<const BasicBlock *, const BasicBlock *>
1786  getPredecessorWithUniqueSuccessorForBB(const BasicBlock *BB) const;
1787 
1788  /// Test whether the condition described by Pred, LHS, and RHS is true
1789  /// whenever the given FoundCondValue value evaluates to true in given
1790  /// Context. If Context is nullptr, then the found predicate is true
1791  /// everywhere. LHS and FoundLHS may have different type width.
1792  bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
1793  const Value *FoundCondValue, bool Inverse,
1794  const Instruction *Context = nullptr);
1795 
1796  /// Test whether the condition described by Pred, LHS, and RHS is true
1797  /// whenever the given FoundCondValue value evaluates to true in given
1798  /// Context. If Context is nullptr, then the found predicate is true
1799  /// everywhere. LHS and FoundLHS must have same type width.
1800  bool isImpliedCondBalancedTypes(ICmpInst::Predicate Pred, const SCEV *LHS,
1801  const SCEV *RHS,
1802  ICmpInst::Predicate FoundPred,
1803  const SCEV *FoundLHS, const SCEV *FoundRHS,
1804  const Instruction *CtxI);
1805 
1806  /// Test whether the condition described by Pred, LHS, and RHS is true
1807  /// whenever the condition described by FoundPred, FoundLHS, FoundRHS is
1808  /// true in given Context. If Context is nullptr, then the found predicate is
1809  /// true everywhere.
1810  bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
1811  ICmpInst::Predicate FoundPred, const SCEV *FoundLHS,
1812  const SCEV *FoundRHS,
1813  const Instruction *Context = nullptr);
1814 
1815  /// Test whether the condition described by Pred, LHS, and RHS is true
1816  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1817  /// true in given Context. If Context is nullptr, then the found predicate is
1818  /// true everywhere.
1819  bool isImpliedCondOperands(ICmpInst::Predicate Pred, const SCEV *LHS,
1820  const SCEV *RHS, const SCEV *FoundLHS,
1821  const SCEV *FoundRHS,
1822  const Instruction *Context = nullptr);
1823 
1824  /// Test whether the condition described by Pred, LHS, and RHS is true
1825  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1826  /// true. Here LHS is an operation that includes FoundLHS as one of its
1827  /// arguments.
1828  bool isImpliedViaOperations(ICmpInst::Predicate Pred,
1829  const SCEV *LHS, const SCEV *RHS,
1830  const SCEV *FoundLHS, const SCEV *FoundRHS,
1831  unsigned Depth = 0);
1832 
1833  /// Test whether the condition described by Pred, LHS, and RHS is true.
1834  /// Use only simple non-recursive types of checks, such as range analysis etc.
1835  bool isKnownViaNonRecursiveReasoning(ICmpInst::Predicate Pred,
1836  const SCEV *LHS, const SCEV *RHS);
1837 
1838  /// Test whether the condition described by Pred, LHS, and RHS is true
1839  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1840  /// true.
1841  bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, const SCEV *LHS,
1842  const SCEV *RHS, const SCEV *FoundLHS,
1843  const SCEV *FoundRHS);
1844 
1845  /// Test whether the condition described by Pred, LHS, and RHS is true
1846  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1847  /// true. Utility function used by isImpliedCondOperands. Tries to get
1848  /// cases like "X `sgt` 0 => X - 1 `sgt` -1".
1849  bool isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred, const SCEV *LHS,
1850  const SCEV *RHS, const SCEV *FoundLHS,
1851  const SCEV *FoundRHS);
1852 
1853  /// Return true if the condition denoted by \p LHS \p Pred \p RHS is implied
1854  /// by a call to @llvm.experimental.guard in \p BB.
1855  bool isImpliedViaGuard(const BasicBlock *BB, ICmpInst::Predicate Pred,
1856  const SCEV *LHS, const SCEV *RHS);
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.
1861  ///
1862  /// This routine tries to rule out certain kinds of integer overflow, and
1863  /// then tries to reason about arithmetic properties of the predicates.
1864  bool isImpliedCondOperandsViaNoOverflow(ICmpInst::Predicate Pred,
1865  const SCEV *LHS, const SCEV *RHS,
1866  const SCEV *FoundLHS,
1867  const SCEV *FoundRHS);
1868 
1869  /// Test whether the condition described by Pred, LHS, and RHS is true
1870  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1871  /// true.
1872  ///
1873  /// This routine tries to weaken the known condition basing on fact that
1874  /// FoundLHS is an AddRec.
1875  bool isImpliedCondOperandsViaAddRecStart(ICmpInst::Predicate Pred,
1876  const SCEV *LHS, const SCEV *RHS,
1877  const SCEV *FoundLHS,
1878  const SCEV *FoundRHS,
1879  const Instruction *CtxI);
1880 
1881  /// Test whether the condition described by Pred, LHS, and RHS is true
1882  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1883  /// true.
1884  ///
1885  /// This routine tries to figure out predicate for Phis which are SCEVUnknown
1886  /// if it is true for every possible incoming value from their respective
1887  /// basic blocks.
1888  bool isImpliedViaMerge(ICmpInst::Predicate Pred,
1889  const SCEV *LHS, const SCEV *RHS,
1890  const SCEV *FoundLHS, const SCEV *FoundRHS,
1891  unsigned Depth);
1892 
1893  /// Test whether the condition described by Pred, LHS, and RHS is true
1894  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1895  /// true.
1896  ///
1897  /// This routine tries to reason about shifts.
1898  bool isImpliedCondOperandsViaShift(ICmpInst::Predicate Pred, const SCEV *LHS,
1899  const SCEV *RHS, const SCEV *FoundLHS,
1900  const SCEV *FoundRHS);
1901 
1902  /// If we know that the specified Phi is in the header of its containing
1903  /// loop, we know the loop executes a constant number of times, and the PHI
1904  /// node is just a recurrence involving constants, fold it.
1905  Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt &BEs,
1906  const Loop *L);
1907 
1908  /// Test if the given expression is known to satisfy the condition described
1909  /// by Pred and the known constant ranges of LHS and RHS.
1910  bool isKnownPredicateViaConstantRanges(ICmpInst::Predicate Pred,
1911  const SCEV *LHS, const SCEV *RHS);
1912 
1913  /// Try to prove the condition described by "LHS Pred RHS" by ruling out
1914  /// integer overflow.
1915  ///
1916  /// For instance, this will return true for "A s< (A + C)<nsw>" if C is
1917  /// positive.
1918  bool isKnownPredicateViaNoOverflow(ICmpInst::Predicate Pred, const SCEV *LHS,
1919  const SCEV *RHS);
1920 
1921  /// Try to split Pred LHS RHS into logical conjunctions (and's) and try to
1922  /// prove them individually.
1923  bool isKnownPredicateViaSplitting(ICmpInst::Predicate Pred, const SCEV *LHS,
1924  const SCEV *RHS);
1925 
1926  /// Try to match the Expr as "(L + R)<Flags>".
1927  bool splitBinaryAdd(const SCEV *Expr, const SCEV *&L, const SCEV *&R,
1928  SCEV::NoWrapFlags &Flags);
1929 
1930  /// Forget predicated/non-predicated backedge taken counts for the given loop.
1931  void forgetBackedgeTakenCounts(const Loop *L, bool Predicated);
1932 
1933  /// Drop memoized information for all \p SCEVs.
1934  void forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs);
1935 
1936  /// Helper for forgetMemoizedResults.
1937  void forgetMemoizedResultsImpl(const SCEV *S);
1938 
1939  /// Return an existing SCEV for V if there is one, otherwise return nullptr.
1940  const SCEV *getExistingSCEV(Value *V);
1941 
1942  /// Erase Value from ValueExprMap and ExprValueMap.
1943  void eraseValueFromMap(Value *V);
1944 
1945  /// Insert V to S mapping into ValueExprMap and ExprValueMap.
1946  void insertValueToMap(Value *V, const SCEV *S);
1947 
1948  /// Return false iff given SCEV contains a SCEVUnknown with NULL value-
1949  /// pointer.
1950  bool checkValidity(const SCEV *S) const;
1951 
1952  /// Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be
1953  /// equal to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}. This is
1954  /// equivalent to proving no signed (resp. unsigned) wrap in
1955  /// {`Start`,+,`Step`} if `ExtendOpTy` is `SCEVSignExtendExpr`
1956  /// (resp. `SCEVZeroExtendExpr`).
1957  template <typename ExtendOpTy>
1958  bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step,
1959  const Loop *L);
1960 
1961  /// Try to prove NSW or NUW on \p AR relying on ConstantRange manipulation.
1962  SCEV::NoWrapFlags proveNoWrapViaConstantRanges(const SCEVAddRecExpr *AR);
1963 
1964  /// Try to prove NSW on \p AR by proving facts about conditions known on
1965  /// entry and backedge.
1966  SCEV::NoWrapFlags proveNoSignedWrapViaInduction(const SCEVAddRecExpr *AR);
1967 
1968  /// Try to prove NUW on \p AR by proving facts about conditions known on
1969  /// entry and backedge.
1970  SCEV::NoWrapFlags proveNoUnsignedWrapViaInduction(const SCEVAddRecExpr *AR);
1971 
1972  Optional<MonotonicPredicateType>
1973  getMonotonicPredicateTypeImpl(const SCEVAddRecExpr *LHS,
1974  ICmpInst::Predicate Pred);
1975 
1976  /// Return SCEV no-wrap flags that can be proven based on reasoning about
1977  /// how poison produced from no-wrap flags on this value (e.g. a nuw add)
1978  /// would trigger undefined behavior on overflow.
1979  SCEV::NoWrapFlags getNoWrapFlagsFromUB(const Value *V);
1980 
1981  /// Return a scope which provides an upper bound on the defining scope of
1982  /// 'S'. Specifically, return the first instruction in said bounding scope.
1983  /// Return nullptr if the scope is trivial (function entry).
1984  /// (See scope definition rules associated with flag discussion above)
1985  const Instruction *getNonTrivialDefiningScopeBound(const SCEV *S);
1986 
1987  /// Return a scope which provides an upper bound on the defining scope for
1988  /// a SCEV with the operands in Ops. The outparam Precise is set if the
1989  /// bound found is a precise bound (i.e. must be the defining scope.)
1990  const Instruction *getDefiningScopeBound(ArrayRef<const SCEV *> Ops,
1991  bool &Precise);
1992 
1993  /// Wrapper around the above for cases which don't care if the bound
1994  /// is precise.
1995  const Instruction *getDefiningScopeBound(ArrayRef<const SCEV *> Ops);
1996 
1997  /// Given two instructions in the same function, return true if we can
1998  /// prove B must execute given A executes.
1999  bool isGuaranteedToTransferExecutionTo(const Instruction *A,
2000  const Instruction *B);
2001 
2002  /// Return true if the SCEV corresponding to \p I is never poison. Proving
2003  /// this is more complex than proving that just \p I is never poison, since
2004  /// SCEV commons expressions across control flow, and you can have cases
2005  /// like:
2006  ///
2007  /// idx0 = a + b;
2008  /// ptr[idx0] = 100;
2009  /// if (<condition>) {
2010  /// idx1 = a +nsw b;
2011  /// ptr[idx1] = 200;
2012  /// }
2013  ///
2014  /// where the SCEV expression (+ a b) is guaranteed to not be poison (and
2015  /// hence not sign-overflow) only if "<condition>" is true. Since both
2016  /// `idx0` and `idx1` will be mapped to the same SCEV expression, (+ a b),
2017  /// it is not okay to annotate (+ a b) with <nsw> in the above example.
2018  bool isSCEVExprNeverPoison(const Instruction *I);
2019 
2020  /// This is like \c isSCEVExprNeverPoison but it specifically works for
2021  /// instructions that will get mapped to SCEV add recurrences. Return true
2022  /// if \p I will never generate poison under the assumption that \p I is an
2023  /// add recurrence on the loop \p L.
2024  bool isAddRecNeverPoison(const Instruction *I, const Loop *L);
2025 
2026  /// Similar to createAddRecFromPHI, but with the additional flexibility of
2027  /// suggesting runtime overflow checks in case casts are encountered.
2028  /// If successful, the analysis records that for this loop, \p SymbolicPHI,
2029  /// which is the UnknownSCEV currently representing the PHI, can be rewritten
2030  /// into an AddRec, assuming some predicates; The function then returns the
2031  /// AddRec and the predicates as a pair, and caches this pair in
2032  /// PredicatedSCEVRewrites.
2033  /// If the analysis is not successful, a mapping from the \p SymbolicPHI to
2034  /// itself (with no predicates) is recorded, and a nullptr with an empty
2035  /// predicates vector is returned as a pair.
2036  Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2037  createAddRecFromPHIWithCastsImpl(const SCEVUnknown *SymbolicPHI);
2038 
2039  /// Compute the maximum backedge count based on the range of values
2040  /// permitted by Start, End, and Stride. This is for loops of the form
2041  /// {Start, +, Stride} LT End.
2042  ///
2043  /// Preconditions:
2044  /// * the induction variable is known to be positive.
2045  /// * the induction variable is assumed not to overflow (i.e. either it
2046  /// actually doesn't, or we'd have to immediately execute UB)
2047  /// We *don't* assert these preconditions so please be careful.
2048  const SCEV *computeMaxBECountForLT(const SCEV *Start, const SCEV *Stride,
2049  const SCEV *End, unsigned BitWidth,
2050  bool IsSigned);
2051 
2052  /// Verify if an linear IV with positive stride can overflow when in a
2053  /// less-than comparison, knowing the invariant term of the comparison,
2054  /// the stride.
2055  bool canIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, bool IsSigned);
2056 
2057  /// Verify if an linear IV with negative stride can overflow when in a
2058  /// greater-than comparison, knowing the invariant term of the comparison,
2059  /// the stride.
2060  bool canIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, bool IsSigned);
2061 
2062  /// Get add expr already created or create a new one.
2063  const SCEV *getOrCreateAddExpr(ArrayRef<const SCEV *> Ops,
2064  SCEV::NoWrapFlags Flags);
2065 
2066  /// Get mul expr already created or create a new one.
2067  const SCEV *getOrCreateMulExpr(ArrayRef<const SCEV *> Ops,
2068  SCEV::NoWrapFlags Flags);
2069 
2070  // Get addrec expr already created or create a new one.
2071  const SCEV *getOrCreateAddRecExpr(ArrayRef<const SCEV *> Ops,
2072  const Loop *L, SCEV::NoWrapFlags Flags);
2073 
2074  /// Return x if \p Val is f(x) where f is a 1-1 function.
2075  const SCEV *stripInjectiveFunctions(const SCEV *Val) const;
2076 
2077  /// Find all of the loops transitively used in \p S, and fill \p LoopsUsed.
2078  /// A loop is considered "used" by an expression if it contains
2079  /// an add rec on said loop.
2080  void getUsedLoops(const SCEV *S, SmallPtrSetImpl<const Loop *> &LoopsUsed);
2081 
2082  /// Try to match the pattern generated by getURemExpr(A, B). If successful,
2083  /// Assign A and B to LHS and RHS, respectively.
2084  bool matchURem(const SCEV *Expr, const SCEV *&LHS, const SCEV *&RHS);
2085 
2086  /// Look for a SCEV expression with type `SCEVType` and operands `Ops` in
2087  /// `UniqueSCEVs`. Return if found, else nullptr.
2088  SCEV *findExistingSCEVInCache(SCEVTypes SCEVType, ArrayRef<const SCEV *> Ops);
2089 
2090  /// Get reachable blocks in this function, making limited use of SCEV
2091  /// reasoning about conditions.
2092  void getReachableBlocks(SmallPtrSetImpl<BasicBlock *> &Reachable,
2093  Function &F);
2094 
2095  FoldingSet<SCEV> UniqueSCEVs;
2096  FoldingSet<SCEVPredicate> UniquePreds;
2097  BumpPtrAllocator SCEVAllocator;
2098 
2099  /// This maps loops to a list of addrecs that directly use said loop.
2100  DenseMap<const Loop *, SmallVector<const SCEVAddRecExpr *, 4>> LoopUsers;
2101 
2102  /// Cache tentative mappings from UnknownSCEVs in a Loop, to a SCEV expression
2103  /// they can be rewritten into under certain predicates.
2104  DenseMap<std::pair<const SCEVUnknown *, const Loop *>,
2105  std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2106  PredicatedSCEVRewrites;
2107 
2108  /// The head of a linked list of all SCEVUnknown values that have been
2109  /// allocated. This is used by releaseMemory to locate them all and call
2110  /// their destructors.
2111  SCEVUnknown *FirstUnknown = nullptr;
2112 };
2113 
2114 /// Analysis pass that exposes the \c ScalarEvolution for a function.
2116  : public AnalysisInfoMixin<ScalarEvolutionAnalysis> {
2118 
2119  static AnalysisKey Key;
2120 
2121 public:
2123 
2125 };
2126 
2127 /// Verifier pass for the \c ScalarEvolutionAnalysis results.
2129  : public PassInfoMixin<ScalarEvolutionVerifierPass> {
2130 public:
2132 };
2133 
2134 /// Printer pass for the \c ScalarEvolutionAnalysis results.
2136  : public PassInfoMixin<ScalarEvolutionPrinterPass> {
2137  raw_ostream &OS;
2138 
2139 public:
2140  explicit ScalarEvolutionPrinterPass(raw_ostream &OS) : OS(OS) {}
2141 
2143 };
2144 
2146  std::unique_ptr<ScalarEvolution> SE;
2147 
2148 public:
2149  static char ID;
2150 
2152 
2153  ScalarEvolution &getSE() { return *SE; }
2154  const ScalarEvolution &getSE() const { return *SE; }
2155 
2156  bool runOnFunction(Function &F) override;
2157  void releaseMemory() override;
2158  void getAnalysisUsage(AnalysisUsage &AU) const override;
2159  void print(raw_ostream &OS, const Module * = nullptr) const override;
2160  void verifyAnalysis() const override;
2161 };
2162 
2163 /// An interface layer with SCEV used to manage how we see SCEV expressions
2164 /// for values in the context of existing predicates. We can add new
2165 /// predicates, but we cannot remove them.
2166 ///
2167 /// This layer has multiple purposes:
2168 /// - provides a simple interface for SCEV versioning.
2169 /// - guarantees that the order of transformations applied on a SCEV
2170 /// expression for a single Value is consistent across two different
2171 /// getSCEV calls. This means that, for example, once we've obtained
2172 /// an AddRec expression for a certain value through expression
2173 /// rewriting, we will continue to get an AddRec expression for that
2174 /// Value.
2175 /// - lowers the number of expression rewrites.
2177 public:
2179 
2180  const SCEVPredicate &getPredicate() const;
2181 
2182  /// Returns the SCEV expression of V, in the context of the current SCEV
2183  /// predicate. The order of transformations applied on the expression of V
2184  /// returned by ScalarEvolution is guaranteed to be preserved, even when
2185  /// adding new predicates.
2186  const SCEV *getSCEV(Value *V);
2187 
2188  /// Get the (predicated) backedge count for the analyzed loop.
2189  const SCEV *getBackedgeTakenCount();
2190 
2191  /// Adds a new predicate.
2192  void addPredicate(const SCEVPredicate &Pred);
2193 
2194  /// Attempts to produce an AddRecExpr for V by adding additional SCEV
2195  /// predicates. If we can't transform the expression into an AddRecExpr we
2196  /// return nullptr and not add additional SCEV predicates to the current
2197  /// context.
2198  const SCEVAddRecExpr *getAsAddRec(Value *V);
2199 
2200  /// Proves that V doesn't overflow by adding SCEV predicate.
2202 
2203  /// Returns true if we've proved that V doesn't wrap by means of a SCEV
2204  /// predicate.
2206 
2207  /// Returns the ScalarEvolution analysis used.
2208  ScalarEvolution *getSE() const { return &SE; }
2209 
2210  /// We need to explicitly define the copy constructor because of FlagsMap.
2212 
2213  /// Print the SCEV mappings done by the Predicated Scalar Evolution.
2214  /// The printed text is indented by \p Depth.
2215  void print(raw_ostream &OS, unsigned Depth) const;
2216 
2217  /// Check if \p AR1 and \p AR2 are equal, while taking into account
2218  /// Equal predicates in Preds.
2219  bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1,
2220  const SCEVAddRecExpr *AR2) const;
2221 
2222 private:
2223  /// Increments the version number of the predicate. This needs to be called
2224  /// every time the SCEV predicate changes.
2225  void updateGeneration();
2226 
2227  /// Holds a SCEV and the version number of the SCEV predicate used to
2228  /// perform the rewrite of the expression.
2229  using RewriteEntry = std::pair<unsigned, const SCEV *>;
2230 
2231  /// Maps a SCEV to the rewrite result of that SCEV at a certain version
2232  /// number. If this number doesn't match the current Generation, we will
2233  /// need to do a rewrite. To preserve the transformation order of previous
2234  /// rewrites, we will rewrite the previous result instead of the original
2235  /// SCEV.
2237 
2238  /// Records what NoWrap flags we've added to a Value *.
2240 
2241  /// The ScalarEvolution analysis.
2242  ScalarEvolution &SE;
2243 
2244  /// The analyzed Loop.
2245  const Loop &L;
2246 
2247  /// The SCEVPredicate that forms our context. We will rewrite all
2248  /// expressions assuming that this predicate true.
2249  std::unique_ptr<SCEVUnionPredicate> Preds;
2250 
2251  /// Marks the version of the SCEV predicate used. When rewriting a SCEV
2252  /// expression we mark it with the version of the predicate. We use this to
2253  /// figure out if the predicate has changed from the last rewrite of the
2254  /// SCEV. If so, we need to perform a new rewrite.
2255  unsigned Generation = 0;
2256 
2257  /// The backedge taken count.
2258  const SCEV *BackedgeCount = nullptr;
2259 };
2260 
2261 } // end namespace llvm
2262 
2263 #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:14083
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:10933
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:4635
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:12978
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:14125
Signed
@ Signed
Definition: NVPTXISelLowering.cpp:4637
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:2115
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:10125
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:11039
llvm::ScalarEvolution::getNegativeSCEV
const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
Definition: ScalarEvolution.cpp:4438
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::SCEVWrapPredicate::maskFlags
static LLVM_NODISCARD SCEVWrapPredicate::IncrementWrapFlags maskFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, int Mask)
Definition: ScalarEvolution.h:361
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:4599
Optional.h
llvm::ScalarEvolutionWrapperPass::getSE
const ScalarEvolution & getSE() const
Definition: ScalarEvolution.h:2154
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:4310
llvm::PredicatedScalarEvolution::getPredicate
const SCEVPredicate & getPredicate() const
Definition: ScalarEvolution.cpp:14175
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:14094
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:437
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::forgetLoopDispositions
void forgetLoopDispositions(const Loop *L)
Called when the client has changed the disposition of values in this loop.
Definition: ScalarEvolution.cpp:8126
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:7838
llvm::ScalarEvolution::getLosslessPtrToIntExpr
const SCEV * getLosslessPtrToIntExpr(const SCEV *Op, unsigned Depth=0)
Definition: ScalarEvolution.cpp:1070
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:7188
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
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:1079
Pass.h
llvm::SCEVExpander
This class uses information about analyze scalars to rewrite expressions in canonical form.
Definition: ScalarEvolutionExpander.h:63
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:2176
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:887
llvm::SCEVComparePredicate::implies
bool implies(const SCEVPredicate *N) const override
Implementation of the SCEVPredicate interface.
Definition: ScalarEvolution.cpp:14005
llvm::PredicatedScalarEvolution::PredicatedScalarEvolution
PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L)
Definition: ScalarEvolution.cpp:14118
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
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:10361
llvm::ScalarEvolution::isKnownNonZero
bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
Definition: ScalarEvolution.cpp:10345
llvm::PredicatedScalarEvolution::getBackedgeTakenCount
const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
Definition: ScalarEvolution.cpp:14154
llvm::ScalarEvolution::getSignedRangeMax
APInt getSignedRangeMax(const SCEV *S)
Determine the max of the signed range for a particular SCEV.
Definition: ScalarEvolution.h:972
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:3576
llvm::ScalarEvolutionPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: ScalarEvolution.cpp:13749
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:13257
llvm::ScalarEvolutionPrinterPass
Printer pass for the ScalarEvolutionAnalysis results.
Definition: ScalarEvolution.h:2135
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:13774
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:1204
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:4300
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:4623
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:14052
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:255
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
llvm::ScalarEvolutionVerifierPass
Verifier pass for the ScalarEvolutionAnalysis results.
Definition: ScalarEvolution.h:2128
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::maskFlags
static LLVM_NODISCARD 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::ConstantMaximum
@ ConstantMaximum
A constant which provides an upper bound on the exact trip count.
Definition: ScalarEvolution.h:850
llvm::ScalarEvolution::clearFlags
static LLVM_NODISCARD SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
Definition: ScalarEvolution.h:478
llvm::ScalarEvolution::LoopInvariantPredicate::Pred
ICmpInst::Predicate Pred
Definition: ScalarEvolution.h:1077
llvm::ScalarEvolution::setFlags
static LLVM_NODISCARD SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
Definition: ScalarEvolution.h:473
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:7704
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:372
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:14384
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::ScalarEvolution::hasFlags
static LLVM_NODISCARD bool hasFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags TestFlags)
Definition: ScalarEvolution.h:481
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:3522
llvm::ScalarEvolutionWrapperPass::getSE
ScalarEvolution & getSE()
Definition: ScalarEvolution.h:2153
llvm::ScalarEvolution::getWiderType
Type * getWiderType(Type *Ty1, Type *Ty2) const
Definition: ScalarEvolution.cpp:4321
llvm::tgtok::FalseVal
@ FalseVal
Definition: TGLexer.h:61
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:10427
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:13969
llvm::ScalarEvolution::getUnknown
const SCEV * getUnknown(Value *V)
Definition: ScalarEvolution.cpp:4263
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:10337
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:4586
llvm::ScalarEvolution::getStrengthenedNoWrapFlagsFromBinOp
std::pair< SCEV::NoWrapFlags, bool > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
Definition: ScalarEvolution.cpp:2324
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:7902
llvm::SCEVWrapPredicate::implies
bool implies(const SCEVPredicate *N) const override
Returns true if this predicate implies N.
Definition: ScalarEvolution.cpp:14036
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:4574
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:11373
llvm::ScalarEvolution::getUnsignedRangeMin
APInt getUnsignedRangeMin(const SCEV *S)
Determine the min of the unsigned range for a particular SCEV.
Definition: ScalarEvolution.h:951
llvm::PredicatedScalarEvolution::getAsAddRec
const SCEVAddRecExpr * getAsAddRec(Value *V)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
Definition: ScalarEvolution.cpp:14221
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:4692
llvm::ScalarEvolution::getURemExpr
const SCEV * getURemExpr(const SCEV *LHS, const SCEV *RHS)
Represents an unsigned remainder expression based on unsigned division.
Definition: ScalarEvolution.cpp:3317
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:4659
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:4235
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:3051
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:12833
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:13347
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:1063
llvm::ScalarEvolution::getTripCountFromExitCount
const SCEV * getTripCountFromExitCount(const SCEV *ExitCount, bool Extend=true)
Convert from an "exit count" (i.e.
Definition: ScalarEvolution.cpp:7651
llvm::ScalarEvolutionWrapperPass::ID
static char ID
Definition: ScalarEvolution.h:2149
llvm::ScalarEvolution::getOne
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
Definition: ScalarEvolution.h:645
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:10583
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:13252
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:12903
llvm::SCEVPredicate::~SCEVPredicate
~SCEVPredicate()=default
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:4192
llvm::ScalarEvolution::getSequentialMinMaxExpr
const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
Definition: ScalarEvolution.cpp:4074
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:261
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:3755
llvm::SCEV::getExpressionSize
unsigned short getExpressionSize() const
Definition: ScalarEvolution.h:170
llvm::ScalarEvolution::SCEVUnknown
friend class SCEVUnknown
Definition: ScalarEvolution.h:1222
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:3346
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:14205
false
Definition: StackSlotColoring.cpp:141
llvm::ScalarEvolution::containsUndefs
bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
Definition: ScalarEvolution.cpp:12824
llvm::ScalarEvolution::getMulExpr
const SCEV * getMulExpr(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Definition: ScalarEvolution.h:584
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::SCEVWrapPredicate::IncrementNSSW
@ IncrementNSSW
Definition: ScalarEvolution.h:345
llvm::Instruction
Definition: Instruction.h:42
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:10412
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:54
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:2145
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:13997
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:667
llvm::ScalarEvolution::getCastExpr
const SCEV * getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty)
Definition: ScalarEvolution.cpp:2134
llvm::ScalarEvolution::getEqualPredicate
const SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.cpp:13804
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:443
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:4407
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:10350
llvm::ScalarEvolutionPrinterPass::ScalarEvolutionPrinterPass
ScalarEvolutionPrinterPass(raw_ostream &OS)
Definition: ScalarEvolution.h:2140
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:13343
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:5542
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:7682
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:1078
llvm::ScalarEvolution::verify
void verify() const
Definition: ScalarEvolution.cpp:13499
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:956
llvm::FoldingSetTrait
FoldingSetTrait - This trait class is used to define behavior of how to "profile" (in the FoldingSet ...
Definition: FoldingSet.h:259
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:10462
llvm::ScalarEvolutionAnalysis::run
ScalarEvolution run(Function &F, FunctionAnalysisManager &AM)
Definition: ScalarEvolution.cpp:13734
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:4325
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:14189
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:577
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:1627
llvm::ScalarEvolution::getSMaxExpr
const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.cpp:4183
llvm::SCEVCouldNotCompute::classof
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition: ScalarEvolution.cpp:458
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::SCEVComparePredicate
This class represents an assumption that the expression LHS Pred RHS evaluates to true,...
Definition: ScalarEvolution.h:278
llvm::DenseMap
Definition: DenseMap.h:716
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:7698
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:12143
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:575
llvm::ScalarEvolution::Exact
@ Exact
An expression exactly describing the number of times the backedge has executed when a loop is exited.
Definition: ScalarEvolution.h:848
llvm::ScalarEvolution::getPtrToIntExpr
const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
Definition: ScalarEvolution.cpp:1194
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:5502
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:895
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:10824
llvm::SCEVComparePredicate::isAlwaysTrue
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
Definition: ScalarEvolution.cpp:14017
ArrayRef.h
llvm::ScalarEvolution::getUnsignedRange
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
Definition: ScalarEvolution.h:946
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:8099
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:10471
llvm::ScalarEvolution::MonotonicallyIncreasing
@ MonotonicallyIncreasing
Definition: ScalarEvolution.h:1064
llvm::SCEVWrapPredicate::clearFlags
static LLVM_NODISCARD SCEVWrapPredicate::IncrementWrapFlags clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OffFlags)
Convenient IncrementWrapFlags manipulation methods.
Definition: ScalarEvolution.h:352
llvm::SCEVWrapPredicate::getImpliedFlags
static LLVM_NODISCARD SCEVWrapPredicate::IncrementWrapFlags getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE)
Returns the set of SCEVWrapPredicate no wrap flags implied by a SCEVAddRecExpr.
Definition: ScalarEvolution.cpp:14062
llvm::ScalarEvolution::containsAddRecurrence
bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
Definition: ScalarEvolution.cpp:4353
llvm::ScalarEvolution::SCEVCallbackVH
friend class SCEVCallbackVH
Definition: ScalarEvolution.h:1220
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:14135
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:6258
llvm::ScalarEvolution::LoopInvariantPredicate::LoopInvariantPredicate
LoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.h:1081
llvm::ScalarEvolution::getAddExpr
const SCEV * getAddExpr(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Definition: ScalarEvolution.h:569
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::SCEVWrapPredicate::setFlags
static LLVM_NODISCARD SCEVWrapPredicate::IncrementWrapFlags setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OnFlags)
Definition: ScalarEvolution.h:369
llvm::ScalarEvolution::print
void print(raw_ostream &OS) const
Definition: ScalarEvolution.cpp:13057
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:10445
llvm::ScalarEvolution::forgetTopmostLoop
void forgetTopmostLoop(const Loop *L)
Definition: ScalarEvolution.cpp:8093
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
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:4224
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:4611
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:1157
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:13796
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:14089
llvm::ScalarEvolution::getAddRecExpr
const SCEV * getAddRecExpr(const SmallVectorImpl< const SCEV * > &Operands, const Loop *L, SCEV::NoWrapFlags Flags)
Definition: ScalarEvolution.h:603
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:4253
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:4646
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:1086
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:13351
llvm::ScalarEvolution::getSignExtendExpr
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
Definition: ScalarEvolution.cpp:1897
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:178
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:135
llvm::ScalarEvolution::getConstant
const SCEV * getConstant(ConstantInt *V)
Definition: ScalarEvolution.cpp:462
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:4244
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:12842
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:317
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:967
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:4211
llvm::ScalarEvolution::ExitCountKind
ExitCountKind
The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of ...
Definition: ScalarEvolution.h:845
llvm::SCEVWrapPredicate::IncrementAnyWrap
@ IncrementAnyWrap
Definition: ScalarEvolution.h:343
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:14019
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:13248
FoldingSet.h
llvm::SCEVCouldNotCompute::SCEVCouldNotCompute
SCEVCouldNotCompute()
Definition: ScalarEvolution.cpp:455
llvm::ScalarEvolution::isKnownPositive
bool isKnownPositive(const SCEV *S)
Test if the given expression is known to be positive.
Definition: ScalarEvolution.cpp:10333
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:13785
llvm::ScalarEvolution::isKnownNonPositive
bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
Definition: ScalarEvolution.cpp:10341
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:14029
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:8037
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:10437
llvm::ScalarEvolution::getGEPExpr
const SCEV * getGEPExpr(GEPOperator *GEP, const SmallVectorImpl< const SCEV * > &IndexExprs)
Returns an expression for a GEP.
Definition: ScalarEvolution.cpp:3671
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:4524
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:13974
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:341
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:1199
llvm::ScalarEvolution::invalidate
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Definition: ScalarEvolution.cpp:13720
llvm::ScalarEvolution::SymbolicMaximum
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
Definition: ScalarEvolution.h:852
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:230
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:7920
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:13810
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_NODISCARD
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h:155
llvm::ScalarEvolution::isSCEVable
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
Definition: ScalarEvolution.cpp:4293
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:431
llvm::ScalarEvolution::getCouldNotCompute
const SCEV * getCouldNotCompute()
Definition: ScalarEvolution.cpp:4340
llvm::PredicatedScalarEvolution::addPredicate
void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
Definition: ScalarEvolution.cpp:14164
llvm::ScalarEvolution::setNoWrapFlags
void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags)
Update no-wrap flags of an AddRec.
Definition: ScalarEvolution.cpp:6278
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:2449
llvm::SCEVWrapPredicate::isAlwaysTrue
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
Definition: ScalarEvolution.cpp:14042
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:287
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:590
llvm::ScalarEvolution::LoopInvariantPredicate
Definition: ScalarEvolution.h:1076
llvm::ScalarEvolution::MonotonicallyDecreasing
@ MonotonicallyDecreasing
Definition: ScalarEvolution.h:1065
llvm::ScalarEvolutionVerifierPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: ScalarEvolution.cpp:13743
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:786
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:2152
llvm::ScalarEvolution::getZeroExtendExpr
const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
Definition: ScalarEvolution.cpp:1595
llvm::ScalarEvolution::removePointerBase
const SCEV * removePointerBase(const SCEV *S)
Compute an expression equivalent to S - getPointerBase(S).
Definition: ScalarEvolution.cpp:4494
Instructions.h
llvm::SCEVWrapPredicate::getExpr
const SCEVAddRecExpr * getExpr() const
Implementation of the SCEVPredicate interface.
Definition: ScalarEvolution.cpp:14034
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:648
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:13789
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:13148
llvm::ScalarEvolution::forgetAllLoops
void forgetAllLoops()
Definition: ScalarEvolution.cpp:8013
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:962
llvm::ScalarEvolution::getLoopInvariantPredicate
Optional< LoopInvariantPredicate > getLoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L, return a LoopInvaria...
Definition: ScalarEvolution.cpp:10536
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:642
llvm::ScalarEvolutionWrapperPass::ScalarEvolutionWrapperPass
ScalarEvolutionWrapperPass()
Definition: ScalarEvolution.cpp:13770
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:14103
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:393
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:2454
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:172
llvm::ScalarEvolution::getMinMaxExpr
const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
Definition: ScalarEvolution.cpp:3760
llvm::ScalarEvolution::~ScalarEvolution
~ScalarEvolution()
Definition: ScalarEvolution.cpp:12955
llvm::ScalarEvolution::getWrapPredicate
const SCEVPredicate * getWrapPredicate(const SCEVAddRecExpr *AR, SCEVWrapPredicate::IncrementWrapFlags AddedFlags)
Definition: ScalarEvolution.cpp:13829
llvm::PredicatedScalarEvolution::print
void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
Definition: ScalarEvolution.cpp:14245
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:13783
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:7907
llvm::PredicatedScalarEvolution::getSE
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
Definition: ScalarEvolution.h:2208
llvm::tgtok::TrueVal
@ TrueVal
Definition: TGLexer.h:61
llvm::ScalarEvolution::getNotSCEV
const SCEV * getNotSCEV(const SCEV *V)
Return the SCEV object corresponding to ~V.
Definition: ScalarEvolution.cpp:4465
llvm::ScalarEvolution::isKnownNegative
bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
Definition: ScalarEvolution.cpp:10329
llvm::ScalarEvolution::getSMinExpr
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
Definition: ScalarEvolution.cpp:4201
llvm::SCEV::isZero
bool isZero() const
Return true if the expression is a constant zero.
Definition: ScalarEvolution.cpp:425
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:9245
llvm::ScalarEvolution::willNotOverflow
bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS)
Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?
Definition: ScalarEvolution.cpp:2288
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:7888
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