LLVM  7.0.0svn
ScalarEvolution.h
Go to the documentation of this file.
1 //===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // The ScalarEvolution class is an LLVM pass which can be used to analyze and
11 // categorize scalar expressions in loops. It specializes in recognizing
12 // general induction variables, representing them with the abstract and opaque
13 // SCEV class. Given this analysis, trip counts of loops and other important
14 // properties can be obtained.
15 //
16 // This analysis is primarily useful for induction variable substitution and
17 // strength reduction.
18 //
19 //===----------------------------------------------------------------------===//
20 
21 #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
22 #define LLVM_ANALYSIS_SCALAREVOLUTION_H
23 
24 #include "llvm/ADT/APInt.h"
25 #include "llvm/ADT/ArrayRef.h"
26 #include "llvm/ADT/DenseMap.h"
27 #include "llvm/ADT/DenseMapInfo.h"
28 #include "llvm/ADT/FoldingSet.h"
29 #include "llvm/ADT/Hashing.h"
30 #include "llvm/ADT/Optional.h"
32 #include "llvm/ADT/SetVector.h"
33 #include "llvm/ADT/SmallPtrSet.h"
34 #include "llvm/ADT/SmallVector.h"
35 #include "llvm/Analysis/LoopInfo.h"
36 #include "llvm/IR/ConstantRange.h"
37 #include "llvm/IR/Function.h"
38 #include "llvm/IR/InstrTypes.h"
39 #include "llvm/IR/Instructions.h"
40 #include "llvm/IR/Operator.h"
41 #include "llvm/IR/PassManager.h"
42 #include "llvm/IR/ValueHandle.h"
43 #include "llvm/IR/ValueMap.h"
44 #include "llvm/Pass.h"
45 #include "llvm/Support/Allocator.h"
46 #include "llvm/Support/Casting.h"
47 #include "llvm/Support/Compiler.h"
48 #include <algorithm>
49 #include <cassert>
50 #include <cstdint>
51 #include <memory>
52 #include <utility>
53 
54 namespace llvm {
55 
56 class AssumptionCache;
57 class BasicBlock;
58 class Constant;
59 class ConstantInt;
60 class DataLayout;
61 class DominatorTree;
62 class GEPOperator;
63 class Instruction;
64 class LLVMContext;
65 class raw_ostream;
66 class ScalarEvolution;
67 class SCEVAddRecExpr;
68 class SCEVUnknown;
69 class StructType;
70 class TargetLibraryInfo;
71 class Type;
72 class Value;
73 
74 /// This class represents an analyzed expression in the program. These are
75 /// opaque objects that the client is not allowed to do much with directly.
76 ///
77 class SCEV : public FoldingSetNode {
78  friend struct FoldingSetTrait<SCEV>;
79 
80  /// A reference to an Interned FoldingSetNodeID for this node. The
81  /// ScalarEvolution's BumpPtrAllocator holds the data.
82  FoldingSetNodeIDRef FastID;
83 
84  // The SCEV baseclass this node corresponds to
85  const unsigned short SCEVType;
86 
87 protected:
88  /// This field is initialized to zero and may be used in subclasses to store
89  /// miscellaneous information.
90  unsigned short SubclassData = 0;
91 
92 public:
93  /// NoWrapFlags are bitfield indices into SubclassData.
94  ///
95  /// Add and Mul expressions may have no-unsigned-wrap <NUW> or
96  /// no-signed-wrap <NSW> properties, which are derived from the IR
97  /// operator. NSW is a misnomer that we use to mean no signed overflow or
98  /// underflow.
99  ///
100  /// AddRec expressions may have a no-self-wraparound <NW> property if, in
101  /// the integer domain, abs(step) * max-iteration(loop) <=
102  /// unsigned-max(bitwidth). This means that the recurrence will never reach
103  /// its start value if the step is non-zero. Computing the same value on
104  /// each iteration is not considered wrapping, and recurrences with step = 0
105  /// are trivially <NW>. <NW> is independent of the sign of step and the
106  /// value the add recurrence starts with.
107  ///
108  /// Note that NUW and NSW are also valid properties of a recurrence, and
109  /// either implies NW. For convenience, NW will be set for a recurrence
110  /// whenever either NUW or NSW are set.
111  enum NoWrapFlags {
112  FlagAnyWrap = 0, // No guarantee.
113  FlagNW = (1 << 0), // No self-wrap.
114  FlagNUW = (1 << 1), // No unsigned wrap.
115  FlagNSW = (1 << 2), // No signed wrap.
116  NoWrapMask = (1 << 3) - 1
117  };
118 
119  explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy)
120  : FastID(ID), SCEVType(SCEVTy) {}
121  SCEV(const SCEV &) = delete;
122  SCEV &operator=(const SCEV &) = delete;
123 
124  unsigned getSCEVType() const { return SCEVType; }
125 
126  /// Return the LLVM type of this SCEV expression.
127  Type *getType() const;
128 
129  /// Return true if the expression is a constant zero.
130  bool isZero() const;
131 
132  /// Return true if the expression is a constant one.
133  bool isOne() const;
134 
135  /// Return true if the expression is a constant all-ones value.
136  bool isAllOnesValue() const;
137 
138  /// Return true if the specified scev is negated, but not a constant.
139  bool isNonConstantNegative() const;
140 
141  /// Print out the internal representation of this scalar to the specified
142  /// stream. This should really only be used for debugging purposes.
143  void print(raw_ostream &OS) const;
144 
145  /// This method is used for debugging.
146  void dump() const;
147 };
148 
149 // Specialize FoldingSetTrait for SCEV to avoid needing to compute
150 // temporary FoldingSetNodeID values.
151 template <> struct FoldingSetTrait<SCEV> : DefaultFoldingSetTrait<SCEV> {
152  static void Profile(const SCEV &X, FoldingSetNodeID &ID) { ID = X.FastID; }
153 
154  static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, unsigned IDHash,
155  FoldingSetNodeID &TempID) {
156  return ID == X.FastID;
157  }
158 
159  static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) {
160  return X.FastID.ComputeHash();
161  }
162 };
163 
164 inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) {
165  S.print(OS);
166  return OS;
167 }
168 
169 /// An object of this class is returned by queries that could not be answered.
170 /// For example, if you ask for the number of iterations of a linked-list
171 /// traversal loop, you will get one of these. None of the standard SCEV
172 /// operations are valid on this class, it is just a marker.
173 struct SCEVCouldNotCompute : public SCEV {
175 
176  /// Methods for support type inquiry through isa, cast, and dyn_cast:
177  static bool classof(const SCEV *S);
178 };
179 
180 /// This class represents an assumption made using SCEV expressions which can
181 /// be checked at run-time.
184 
185  /// A reference to an Interned FoldingSetNodeID for this node. The
186  /// ScalarEvolution's BumpPtrAllocator holds the data.
187  FoldingSetNodeIDRef FastID;
188 
189 public:
190  enum SCEVPredicateKind { P_Union, P_Equal, P_Wrap };
191 
192 protected:
194  ~SCEVPredicate() = default;
195  SCEVPredicate(const SCEVPredicate &) = default;
196  SCEVPredicate &operator=(const SCEVPredicate &) = default;
197 
198 public:
200 
201  SCEVPredicateKind getKind() const { return Kind; }
202 
203  /// Returns the estimated complexity of this predicate. This is roughly
204  /// measured in the number of run-time checks required.
205  virtual unsigned getComplexity() const { return 1; }
206 
207  /// Returns true if the predicate is always true. This means that no
208  /// assumptions were made and nothing needs to be checked at run-time.
209  virtual bool isAlwaysTrue() const = 0;
210 
211  /// Returns true if this predicate implies \p N.
212  virtual bool implies(const SCEVPredicate *N) const = 0;
213 
214  /// Prints a textual representation of this predicate with an indentation of
215  /// \p Depth.
216  virtual void print(raw_ostream &OS, unsigned Depth = 0) const = 0;
217 
218  /// Returns the SCEV to which this predicate applies, or nullptr if this is
219  /// a SCEVUnionPredicate.
220  virtual const SCEV *getExpr() const = 0;
221 };
222 
224  P.print(OS);
225  return OS;
226 }
227 
228 // Specialize FoldingSetTrait for SCEVPredicate to avoid needing to compute
229 // temporary FoldingSetNodeID values.
230 template <>
232  static void Profile(const SCEVPredicate &X, FoldingSetNodeID &ID) {
233  ID = X.FastID;
234  }
235 
236  static bool Equals(const SCEVPredicate &X, const FoldingSetNodeID &ID,
237  unsigned IDHash, FoldingSetNodeID &TempID) {
238  return ID == X.FastID;
239  }
240 
241  static unsigned ComputeHash(const SCEVPredicate &X,
242  FoldingSetNodeID &TempID) {
243  return X.FastID.ComputeHash();
244  }
245 };
246 
247 /// This class represents an assumption that two SCEV expressions are equal,
248 /// and this can be checked at run-time.
249 class SCEVEqualPredicate final : public SCEVPredicate {
250  /// We assume that LHS == RHS.
251  const SCEV *LHS;
252  const SCEV *RHS;
253 
254 public:
255  SCEVEqualPredicate(const FoldingSetNodeIDRef ID, const SCEV *LHS,
256  const SCEV *RHS);
257 
258  /// Implementation of the SCEVPredicate interface
259  bool implies(const SCEVPredicate *N) const override;
260  void print(raw_ostream &OS, unsigned Depth = 0) const override;
261  bool isAlwaysTrue() const override;
262  const SCEV *getExpr() const override;
263 
264  /// Returns the left hand side of the equality.
265  const SCEV *getLHS() const { return LHS; }
266 
267  /// Returns the right hand side of the equality.
268  const SCEV *getRHS() const { return RHS; }
269 
270  /// Methods for support type inquiry through isa, cast, and dyn_cast:
271  static bool classof(const SCEVPredicate *P) {
272  return P->getKind() == P_Equal;
273  }
274 };
275 
276 /// This class represents an assumption made on an AddRec expression. Given an
277 /// affine AddRec expression {a,+,b}, we assume that it has the nssw or nusw
278 /// flags (defined below) in the first X iterations of the loop, where X is a
279 /// SCEV expression returned by getPredicatedBackedgeTakenCount).
280 ///
281 /// Note that this does not imply that X is equal to the backedge taken
282 /// count. This means that if we have a nusw predicate for i32 {0,+,1} with a
283 /// predicated backedge taken count of X, we only guarantee that {0,+,1} has
284 /// nusw in the first X iterations. {0,+,1} may still wrap in the loop if we
285 /// have more than X iterations.
286 class SCEVWrapPredicate final : public SCEVPredicate {
287 public:
288  /// Similar to SCEV::NoWrapFlags, but with slightly different semantics
289  /// for FlagNUSW. The increment is considered to be signed, and a + b
290  /// (where b is the increment) is considered to wrap if:
291  /// zext(a + b) != zext(a) + sext(b)
292  ///
293  /// If Signed is a function that takes an n-bit tuple and maps to the
294  /// integer domain as the tuples value interpreted as twos complement,
295  /// and Unsigned a function that takes an n-bit tuple and maps to the
296  /// integer domain as as the base two value of input tuple, then a + b
297  /// has IncrementNUSW iff:
298  ///
299  /// 0 <= Unsigned(a) + Signed(b) < 2^n
300  ///
301  /// The IncrementNSSW flag has identical semantics with SCEV::FlagNSW.
302  ///
303  /// Note that the IncrementNUSW flag is not commutative: if base + inc
304  /// has IncrementNUSW, then inc + base doesn't neccessarily have this
305  /// property. The reason for this is that this is used for sign/zero
306  /// extending affine AddRec SCEV expressions when a SCEVWrapPredicate is
307  /// assumed. A {base,+,inc} expression is already non-commutative with
308  /// regards to base and inc, since it is interpreted as:
309  /// (((base + inc) + inc) + inc) ...
311  IncrementAnyWrap = 0, // No guarantee.
312  IncrementNUSW = (1 << 0), // No unsigned with signed increment wrap.
313  IncrementNSSW = (1 << 1), // No signed with signed increment wrap
314  // (equivalent with SCEV::NSW)
315  IncrementNoWrapMask = (1 << 2) - 1
316  };
317 
318  /// Convenient IncrementWrapFlags manipulation methods.
322  assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
323  assert((OffFlags & IncrementNoWrapMask) == OffFlags &&
324  "Invalid flags value!");
325  return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & ~OffFlags);
326  }
327 
330  assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
331  assert((Mask & IncrementNoWrapMask) == Mask && "Invalid mask value!");
332 
334  }
335 
339  assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
340  assert((OnFlags & IncrementNoWrapMask) == OnFlags &&
341  "Invalid flags value!");
342 
343  return (SCEVWrapPredicate::IncrementWrapFlags)(Flags | OnFlags);
344  }
345 
346  /// Returns the set of SCEVWrapPredicate no wrap flags implied by a
347  /// SCEVAddRecExpr.
349  getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE);
350 
351 private:
352  const SCEVAddRecExpr *AR;
353  IncrementWrapFlags Flags;
354 
355 public:
357  const SCEVAddRecExpr *AR,
358  IncrementWrapFlags Flags);
359 
360  /// Returns the set assumed no overflow flags.
361  IncrementWrapFlags getFlags() const { return Flags; }
362 
363  /// Implementation of the SCEVPredicate interface
364  const SCEV *getExpr() const override;
365  bool implies(const SCEVPredicate *N) const override;
366  void print(raw_ostream &OS, unsigned Depth = 0) const override;
367  bool isAlwaysTrue() const override;
368 
369  /// Methods for support type inquiry through isa, cast, and dyn_cast:
370  static bool classof(const SCEVPredicate *P) {
371  return P->getKind() == P_Wrap;
372  }
373 };
374 
375 /// This class represents a composition of other SCEV predicates, and is the
376 /// class that most clients will interact with. This is equivalent to a
377 /// logical "AND" of all the predicates in the union.
378 ///
379 /// NB! Unlike other SCEVPredicate sub-classes this class does not live in the
380 /// ScalarEvolution::Preds folding set. This is why the \c add function is sound.
381 class SCEVUnionPredicate final : public SCEVPredicate {
382 private:
383  using PredicateMap =
385 
386  /// Vector with references to all predicates in this union.
388 
389  /// Maps SCEVs to predicates for quick look-ups.
390  PredicateMap SCEVToPreds;
391 
392 public:
394 
396  return Preds;
397  }
398 
399  /// Adds a predicate to this union.
400  void add(const SCEVPredicate *N);
401 
402  /// Returns a reference to a vector containing all predicates which apply to
403  /// \p Expr.
404  ArrayRef<const SCEVPredicate *> getPredicatesForExpr(const SCEV *Expr);
405 
406  /// Implementation of the SCEVPredicate interface
407  bool isAlwaysTrue() const override;
408  bool implies(const SCEVPredicate *N) const override;
409  void print(raw_ostream &OS, unsigned Depth) const override;
410  const SCEV *getExpr() const override;
411 
412  /// We estimate the complexity of a union predicate as the size number of
413  /// predicates in the union.
414  unsigned getComplexity() const override { return Preds.size(); }
415 
416  /// Methods for support type inquiry through isa, cast, and dyn_cast:
417  static bool classof(const SCEVPredicate *P) {
418  return P->getKind() == P_Union;
419  }
420 };
421 
423  ExitLimitQuery(const Loop *L, BasicBlock *ExitingBlock, bool AllowPredicates)
424  : L(L), ExitingBlock(ExitingBlock), AllowPredicates(AllowPredicates) {}
425 
426  const Loop *L;
429 };
430 
431 template <> struct DenseMapInfo<ExitLimitQuery> {
432  static inline ExitLimitQuery getEmptyKey() {
433  return ExitLimitQuery(nullptr, nullptr, true);
434  }
435 
436  static inline ExitLimitQuery getTombstoneKey() {
437  return ExitLimitQuery(nullptr, nullptr, false);
438  }
439 
440  static unsigned getHashValue(ExitLimitQuery Val) {
441  return hash_combine(hash_combine(Val.L, Val.ExitingBlock),
442  Val.AllowPredicates);
443  }
444 
445  static bool isEqual(ExitLimitQuery LHS, ExitLimitQuery RHS) {
446  return LHS.L == RHS.L && LHS.ExitingBlock == RHS.ExitingBlock &&
447  LHS.AllowPredicates == RHS.AllowPredicates;
448  }
449 };
450 
451 /// The main scalar evolution driver. Because client code (intentionally)
452 /// can't do much with the SCEV objects directly, they must ask this class
453 /// for services.
455 public:
456  /// An enum describing the relationship between a SCEV and a loop.
458  LoopVariant, ///< The SCEV is loop-variant (unknown).
459  LoopInvariant, ///< The SCEV is loop-invariant.
460  LoopComputable ///< The SCEV varies predictably with the loop.
461  };
462 
463  /// An enum describing the relationship between a SCEV and a basic block.
465  DoesNotDominateBlock, ///< The SCEV does not dominate the block.
466  DominatesBlock, ///< The SCEV dominates the block.
467  ProperlyDominatesBlock ///< The SCEV properly dominates the block.
468  };
469 
470  /// Convenient NoWrapFlags manipulation that hides enum casts and is
471  /// visible in the ScalarEvolution name space.
473  int Mask) {
474  return (SCEV::NoWrapFlags)(Flags & Mask);
475  }
477  SCEV::NoWrapFlags OnFlags) {
478  return (SCEV::NoWrapFlags)(Flags | OnFlags);
479  }
482  return (SCEV::NoWrapFlags)(Flags & ~OffFlags);
483  }
484 
486  DominatorTree &DT, LoopInfo &LI);
488  ~ScalarEvolution();
489 
490  LLVMContext &getContext() const { return F.getContext(); }
491 
492  /// Test if values of the given type are analyzable within the SCEV
493  /// framework. This primarily includes integer types, and it can optionally
494  /// include pointer types if the ScalarEvolution class has access to
495  /// target-specific information.
496  bool isSCEVable(Type *Ty) const;
497 
498  /// Return the size in bits of the specified type, for which isSCEVable must
499  /// return true.
500  uint64_t getTypeSizeInBits(Type *Ty) const;
501 
502  /// Return a type with the same bitwidth as the given type and which
503  /// represents how SCEV will treat the given type, for which isSCEVable must
504  /// return true. For pointer types, this is the pointer-sized integer type.
505  Type *getEffectiveSCEVType(Type *Ty) const;
506 
507  // Returns a wider type among {Ty1, Ty2}.
508  Type *getWiderType(Type *Ty1, Type *Ty2) const;
509 
510  /// Return true if the SCEV is a scAddRecExpr or it contains
511  /// scAddRecExpr. The result will be cached in HasRecMap.
512  bool containsAddRecurrence(const SCEV *S);
513 
514  /// Erase Value from ValueExprMap and ExprValueMap.
515  void eraseValueFromMap(Value *V);
516 
517  /// Return a SCEV expression for the full generality of the specified
518  /// expression.
519  const SCEV *getSCEV(Value *V);
520 
521  const SCEV *getConstant(ConstantInt *V);
522  const SCEV *getConstant(const APInt &Val);
523  const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false);
524  const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty);
525  const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
526  const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
527  const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty);
528  const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
530  unsigned Depth = 0);
531  const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS,
533  unsigned Depth = 0) {
534  SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
535  return getAddExpr(Ops, Flags, Depth);
536  }
537  const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
539  unsigned Depth = 0) {
540  SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
541  return getAddExpr(Ops, Flags, Depth);
542  }
543  const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
545  unsigned Depth = 0);
546  const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS,
548  unsigned Depth = 0) {
549  SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
550  return getMulExpr(Ops, Flags, Depth);
551  }
552  const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
554  unsigned Depth = 0) {
555  SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
556  return getMulExpr(Ops, Flags, Depth);
557  }
558  const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS);
559  const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS);
560  const SCEV *getURemExpr(const SCEV *LHS, const SCEV *RHS);
561  const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L,
562  SCEV::NoWrapFlags Flags);
563  const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
564  const Loop *L, SCEV::NoWrapFlags Flags);
566  const Loop *L, SCEV::NoWrapFlags Flags) {
567  SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end());
568  return getAddRecExpr(NewOp, L, Flags);
569  }
570 
571  /// Checks if \p SymbolicPHI can be rewritten as an AddRecExpr under some
572  /// Predicates. If successful return these <AddRecExpr, Predicates>;
573  /// The function is intended to be called from PSCEV (the caller will decide
574  /// whether to actually add the predicates and carry out the rewrites).
576  createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI);
577 
578  /// Returns an expression for a GEP
579  ///
580  /// \p GEP The GEP. The indices contained in the GEP itself are ignored,
581  /// instead we use IndexExprs.
582  /// \p IndexExprs The expressions for the indices.
583  const SCEV *getGEPExpr(GEPOperator *GEP,
584  const SmallVectorImpl<const SCEV *> &IndexExprs);
585  const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS);
586  const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
587  const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS);
588  const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
589  const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS);
590  const SCEV *getSMinExpr(SmallVectorImpl<const SCEV *> &Operands);
591  const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS);
592  const SCEV *getUMinExpr(SmallVectorImpl<const SCEV *> &Operands);
593  const SCEV *getUnknown(Value *V);
594  const SCEV *getCouldNotCompute();
595 
596  /// Return a SCEV for the constant 0 of a specific type.
597  const SCEV *getZero(Type *Ty) { return getConstant(Ty, 0); }
598 
599  /// Return a SCEV for the constant 1 of a specific type.
600  const SCEV *getOne(Type *Ty) { return getConstant(Ty, 1); }
601 
602  /// Return an expression for sizeof AllocTy that is type IntTy
603  const SCEV *getSizeOfExpr(Type *IntTy, Type *AllocTy);
604 
605  /// Return an expression for offsetof on the given field with type IntTy
606  const SCEV *getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo);
607 
608  /// Return the SCEV object corresponding to -V.
609  const SCEV *getNegativeSCEV(const SCEV *V,
611 
612  /// Return the SCEV object corresponding to ~V.
613  const SCEV *getNotSCEV(const SCEV *V);
614 
615  /// Return LHS-RHS. Minus is represented in SCEV as A+B*-1.
616  const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
618  unsigned Depth = 0);
619 
620  /// Return a SCEV corresponding to a conversion of the input value to the
621  /// specified type. If the type must be extended, it is zero extended.
622  const SCEV *getTruncateOrZeroExtend(const SCEV *V, Type *Ty);
623 
624  /// Return a SCEV corresponding to a conversion of the input value to the
625  /// specified type. If the type must be extended, it is sign extended.
626  const SCEV *getTruncateOrSignExtend(const SCEV *V, Type *Ty);
627 
628  /// Return a SCEV corresponding to a conversion of the input value to the
629  /// specified type. If the type must be extended, it is zero extended. The
630  /// conversion must not be narrowing.
631  const SCEV *getNoopOrZeroExtend(const SCEV *V, Type *Ty);
632 
633  /// Return a SCEV corresponding to a conversion of the input value to the
634  /// specified type. If the type must be extended, it is sign extended. The
635  /// conversion must not be narrowing.
636  const SCEV *getNoopOrSignExtend(const SCEV *V, Type *Ty);
637 
638  /// Return a SCEV corresponding to a conversion of the input value to the
639  /// specified type. If the type must be extended, it is extended with
640  /// unspecified bits. The conversion must not be narrowing.
641  const SCEV *getNoopOrAnyExtend(const SCEV *V, Type *Ty);
642 
643  /// Return a SCEV corresponding to a conversion of the input value to the
644  /// specified type. The conversion must not be widening.
645  const SCEV *getTruncateOrNoop(const SCEV *V, Type *Ty);
646 
647  /// Promote the operands to the wider of the types using zero-extension, and
648  /// then perform a umax operation with them.
649  const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS);
650 
651  /// Promote the operands to the wider of the types using zero-extension, and
652  /// then perform a umin operation with them.
653  const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS);
654 
655  /// Promote the operands to the wider of the types using zero-extension, and
656  /// then perform a umin operation with them. N-ary function.
657  const SCEV *getUMinFromMismatchedTypes(SmallVectorImpl<const SCEV *> &Ops);
658 
659  /// Transitively follow the chain of pointer-type operands until reaching a
660  /// SCEV that does not have a single pointer operand. This returns a
661  /// SCEVUnknown pointer for well-formed pointer-type expressions, but corner
662  /// cases do exist.
663  const SCEV *getPointerBase(const SCEV *V);
664 
665  /// Return a SCEV expression for the specified value at the specified scope
666  /// in the program. The L value specifies a loop nest to evaluate the
667  /// expression at, where null is the top-level or a specified loop is
668  /// immediately inside of the loop.
669  ///
670  /// This method can be used to compute the exit value for a variable defined
671  /// in a loop by querying what the value will hold in the parent loop.
672  ///
673  /// In the case that a relevant loop exit value cannot be computed, the
674  /// original value V is returned.
675  const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L);
676 
677  /// This is a convenience function which does getSCEVAtScope(getSCEV(V), L).
678  const SCEV *getSCEVAtScope(Value *V, const Loop *L);
679 
680  /// Test whether entry to the loop is protected by a conditional between LHS
681  /// and RHS. This is used to help avoid max expressions in loop trip
682  /// counts, and to eliminate casts.
683  bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
684  const SCEV *LHS, const SCEV *RHS);
685 
686  /// Test whether the backedge of the loop is protected by a conditional
687  /// between LHS and RHS. This is used to eliminate casts.
688  bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
689  const SCEV *LHS, const SCEV *RHS);
690 
691  /// Returns the maximum trip count of the loop if it is a single-exit
692  /// loop and we can compute a small maximum for that loop.
693  ///
694  /// Implemented in terms of the \c getSmallConstantTripCount overload with
695  /// the single exiting block passed to it. See that routine for details.
696  unsigned getSmallConstantTripCount(const Loop *L);
697 
698  /// Returns the maximum trip count of this loop as a normal unsigned
699  /// value. Returns 0 if the trip count is unknown or not constant. This
700  /// "trip count" assumes that control exits via ExitingBlock. More
701  /// precisely, it is the number of times that control may reach ExitingBlock
702  /// before taking the branch. For loops with multiple exits, it may not be
703  /// the number times that the loop header executes if the loop exits
704  /// prematurely via another branch.
705  unsigned getSmallConstantTripCount(const Loop *L, BasicBlock *ExitingBlock);
706 
707  /// Returns the upper bound of the loop trip count as a normal unsigned
708  /// value.
709  /// Returns 0 if the trip count is unknown or not constant.
710  unsigned getSmallConstantMaxTripCount(const Loop *L);
711 
712  /// Returns the largest constant divisor of the trip count of the
713  /// loop if it is a single-exit loop and we can compute a small maximum for
714  /// that loop.
715  ///
716  /// Implemented in terms of the \c getSmallConstantTripMultiple overload with
717  /// the single exiting block passed to it. See that routine for details.
718  unsigned getSmallConstantTripMultiple(const Loop *L);
719 
720  /// Returns the largest constant divisor of the trip count of this loop as a
721  /// normal unsigned value, if possible. This means that the actual trip
722  /// count is always a multiple of the returned value (don't forget the trip
723  /// count could very well be zero as well!). As explained in the comments
724  /// for getSmallConstantTripCount, this assumes that control exits the loop
725  /// via ExitingBlock.
726  unsigned getSmallConstantTripMultiple(const Loop *L,
727  BasicBlock *ExitingBlock);
728 
729  /// Get the expression for the number of loop iterations for which this loop
730  /// is guaranteed not to exit via ExitingBlock. Otherwise return
731  /// SCEVCouldNotCompute.
732  const SCEV *getExitCount(const Loop *L, BasicBlock *ExitingBlock);
733 
734  /// If the specified loop has a predictable backedge-taken count, return it,
735  /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count is
736  /// the number of times the loop header will be branched to from within the
737  /// loop, assuming there are no abnormal exists like exception throws. This is
738  /// one less than the trip count of the loop, since it doesn't count the first
739  /// iteration, when the header is branched to from outside the loop.
740  ///
741  /// Note that it is not valid to call this method on a loop without a
742  /// loop-invariant backedge-taken count (see
743  /// hasLoopInvariantBackedgeTakenCount).
744  const SCEV *getBackedgeTakenCount(const Loop *L);
745 
746  /// Similar to getBackedgeTakenCount, except it will add a set of
747  /// SCEV predicates to Predicates that are required to be true in order for
748  /// the answer to be correct. Predicates can be checked with run-time
749  /// checks and can be used to perform loop versioning.
750  const SCEV *getPredicatedBackedgeTakenCount(const Loop *L,
751  SCEVUnionPredicate &Predicates);
752 
753  /// When successful, this returns a SCEVConstant that is greater than or equal
754  /// to (i.e. a "conservative over-approximation") of the value returend by
755  /// getBackedgeTakenCount. If such a value cannot be computed, it returns the
756  /// SCEVCouldNotCompute object.
757  const SCEV *getMaxBackedgeTakenCount(const Loop *L);
758 
759  /// Return true if the backedge taken count is either the value returned by
760  /// getMaxBackedgeTakenCount or zero.
761  bool isBackedgeTakenCountMaxOrZero(const Loop *L);
762 
763  /// Return true if the specified loop has an analyzable loop-invariant
764  /// backedge-taken count.
765  bool hasLoopInvariantBackedgeTakenCount(const Loop *L);
766 
767  /// This method should be called by the client when it has changed a loop in
768  /// a way that may effect ScalarEvolution's ability to compute a trip count,
769  /// or if the loop is deleted. This call is potentially expensive for large
770  /// loop bodies.
771  void forgetLoop(const Loop *L);
772 
773  // This method invokes forgetLoop for the outermost loop of the given loop
774  // \p L, making ScalarEvolution forget about all this subtree. This needs to
775  // be done whenever we make a transform that may affect the parameters of the
776  // outer loop, such as exit counts for branches.
777  void forgetTopmostLoop(const Loop *L);
778 
779  /// This method should be called by the client when it has changed a value
780  /// in a way that may effect its value, or which may disconnect it from a
781  /// def-use chain linking it to a loop.
782  void forgetValue(Value *V);
783 
784  /// Called when the client has changed the disposition of values in
785  /// this loop.
786  ///
787  /// We don't have a way to invalidate per-loop dispositions. Clear and
788  /// recompute is simpler.
789  void forgetLoopDispositions(const Loop *L) { LoopDispositions.clear(); }
790 
791  /// Determine the minimum number of zero bits that S is guaranteed to end in
792  /// (at every loop iteration). It is, at the same time, the minimum number
793  /// of times S is divisible by 2. For example, given {4,+,8} it returns 2.
794  /// If S is guaranteed to be 0, it returns the bitwidth of S.
795  uint32_t GetMinTrailingZeros(const SCEV *S);
796 
797  /// Determine the unsigned range for a particular SCEV.
798  /// NOTE: This returns a copy of the reference returned by getRangeRef.
800  return getRangeRef(S, HINT_RANGE_UNSIGNED);
801  }
802 
803  /// Determine the min of the unsigned range for a particular SCEV.
805  return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMin();
806  }
807 
808  /// Determine the max of the unsigned range for a particular SCEV.
810  return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMax();
811  }
812 
813  /// Determine the signed range for a particular SCEV.
814  /// NOTE: This returns a copy of the reference returned by getRangeRef.
816  return getRangeRef(S, HINT_RANGE_SIGNED);
817  }
818 
819  /// Determine the min of the signed range for a particular SCEV.
821  return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMin();
822  }
823 
824  /// Determine the max of the signed range for a particular SCEV.
826  return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMax();
827  }
828 
829  /// Test if the given expression is known to be negative.
830  bool isKnownNegative(const SCEV *S);
831 
832  /// Test if the given expression is known to be positive.
833  bool isKnownPositive(const SCEV *S);
834 
835  /// Test if the given expression is known to be non-negative.
836  bool isKnownNonNegative(const SCEV *S);
837 
838  /// Test if the given expression is known to be non-positive.
839  bool isKnownNonPositive(const SCEV *S);
840 
841  /// Test if the given expression is known to be non-zero.
842  bool isKnownNonZero(const SCEV *S);
843 
844  /// Splits SCEV expression \p S into two SCEVs. One of them is obtained from
845  /// \p S by substitution of all AddRec sub-expression related to loop \p L
846  /// with initial value of that SCEV. The second is obtained from \p S by
847  /// substitution of all AddRec sub-expressions related to loop \p L with post
848  /// increment of this AddRec in the loop \p L. In both cases all other AddRec
849  /// sub-expressions (not related to \p L) remain the same.
850  /// If the \p S contains non-invariant unknown SCEV the function returns
851  /// CouldNotCompute SCEV in both values of std::pair.
852  /// For example, for SCEV S={0, +, 1}<L1> + {0, +, 1}<L2> and loop L=L1
853  /// the function returns pair:
854  /// first = {0, +, 1}<L2>
855  /// second = {1, +, 1}<L1> + {0, +, 1}<L2>
856  /// We can see that for the first AddRec sub-expression it was replaced with
857  /// 0 (initial value) for the first element and to {1, +, 1}<L1> (post
858  /// increment value) for the second one. In both cases AddRec expression
859  /// related to L2 remains the same.
860  std::pair<const SCEV *, const SCEV *> SplitIntoInitAndPostInc(const Loop *L,
861  const SCEV *S);
862 
863  /// We'd like to check the predicate on every iteration of the most dominated
864  /// loop between loops used in LHS and RHS.
865  /// To do this we use the following list of steps:
866  /// 1. Collect set S all loops on which either LHS or RHS depend.
867  /// 2. If S is non-empty
868  /// a. Let PD be the element of S which is dominated by all other elements.
869  /// b. Let E(LHS) be value of LHS on entry of PD.
870  /// To get E(LHS), we should just take LHS and replace all AddRecs that are
871  /// attached to PD on with their entry values.
872  /// Define E(RHS) in the same way.
873  /// c. Let B(LHS) be value of L on backedge of PD.
874  /// To get B(LHS), we should just take LHS and replace all AddRecs that are
875  /// attached to PD on with their backedge values.
876  /// Define B(RHS) in the same way.
877  /// d. Note that E(LHS) and E(RHS) are automatically available on entry of PD,
878  /// so we can assert on that.
879  /// e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) &&
880  /// isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS))
881  bool isKnownViaInduction(ICmpInst::Predicate Pred, const SCEV *LHS,
882  const SCEV *RHS);
883 
884  /// Test if the given expression is known to satisfy the condition described
885  /// by Pred, LHS, and RHS.
886  bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS,
887  const SCEV *RHS);
888 
889  /// Test if the condition described by Pred, LHS, RHS is known to be true on
890  /// every iteration of the loop of the recurrency LHS.
891  bool isKnownOnEveryIteration(ICmpInst::Predicate Pred,
892  const SCEVAddRecExpr *LHS, const SCEV *RHS);
893 
894  /// Return true if, for all loop invariant X, the predicate "LHS `Pred` X"
895  /// is monotonically increasing or decreasing. In the former case set
896  /// `Increasing` to true and in the latter case set `Increasing` to false.
897  ///
898  /// A predicate is said to be monotonically increasing if may go from being
899  /// false to being true as the loop iterates, but never the other way
900  /// around. A predicate is said to be monotonically decreasing if may go
901  /// from being true to being false as the loop iterates, but never the other
902  /// way around.
903  bool isMonotonicPredicate(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred,
904  bool &Increasing);
905 
906  /// Return true if the result of the predicate LHS `Pred` RHS is loop
907  /// invariant with respect to L. Set InvariantPred, InvariantLHS and
908  /// InvariantLHS so that InvariantLHS `InvariantPred` InvariantRHS is the
909  /// loop invariant form of LHS `Pred` RHS.
910  bool isLoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS,
911  const SCEV *RHS, const Loop *L,
912  ICmpInst::Predicate &InvariantPred,
913  const SCEV *&InvariantLHS,
914  const SCEV *&InvariantRHS);
915 
916  /// Simplify LHS and RHS in a comparison with predicate Pred. Return true
917  /// iff any changes were made. If the operands are provably equal or
918  /// unequal, LHS and RHS are set to the same value and Pred is set to either
919  /// ICMP_EQ or ICMP_NE.
920  bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS,
921  const SCEV *&RHS, unsigned Depth = 0);
922 
923  /// Return the "disposition" of the given SCEV with respect to the given
924  /// loop.
925  LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L);
926 
927  /// Return true if the value of the given SCEV is unchanging in the
928  /// specified loop.
929  bool isLoopInvariant(const SCEV *S, const Loop *L);
930 
931  /// Determine if the SCEV can be evaluated at loop's entry. It is true if it
932  /// doesn't depend on a SCEVUnknown of an instruction which is dominated by
933  /// the header of loop L.
934  bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L);
935 
936  /// Return true if the given SCEV changes value in a known way in the
937  /// specified loop. This property being true implies that the value is
938  /// variant in the loop AND that we can emit an expression to compute the
939  /// value of the expression at any particular loop iteration.
940  bool hasComputableLoopEvolution(const SCEV *S, const Loop *L);
941 
942  /// Return the "disposition" of the given SCEV with respect to the given
943  /// block.
944  BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB);
945 
946  /// Return true if elements that makes up the given SCEV dominate the
947  /// specified basic block.
948  bool dominates(const SCEV *S, const BasicBlock *BB);
949 
950  /// Return true if elements that makes up the given SCEV properly dominate
951  /// the specified basic block.
952  bool properlyDominates(const SCEV *S, const BasicBlock *BB);
953 
954  /// Test whether the given SCEV has Op as a direct or indirect operand.
955  bool hasOperand(const SCEV *S, const SCEV *Op) const;
956 
957  /// Return the size of an element read or written by Inst.
958  const SCEV *getElementSize(Instruction *Inst);
959 
960  /// Compute the array dimensions Sizes from the set of Terms extracted from
961  /// the memory access function of this SCEVAddRecExpr (second step of
962  /// delinearization).
963  void findArrayDimensions(SmallVectorImpl<const SCEV *> &Terms,
965  const SCEV *ElementSize);
966 
967  void print(raw_ostream &OS) const;
968  void verify() const;
969  bool invalidate(Function &F, const PreservedAnalyses &PA,
971 
972  /// Collect parametric terms occurring in step expressions (first step of
973  /// delinearization).
974  void collectParametricTerms(const SCEV *Expr,
976 
977  /// Return in Subscripts the access functions for each dimension in Sizes
978  /// (third step of delinearization).
979  void computeAccessFunctions(const SCEV *Expr,
980  SmallVectorImpl<const SCEV *> &Subscripts,
982 
983  /// Split this SCEVAddRecExpr into two vectors of SCEVs representing the
984  /// subscripts and sizes of an array access.
985  ///
986  /// The delinearization is a 3 step process: the first two steps compute the
987  /// sizes of each subscript and the third step computes the access functions
988  /// for the delinearized array:
989  ///
990  /// 1. Find the terms in the step functions
991  /// 2. Compute the array size
992  /// 3. Compute the access function: divide the SCEV by the array size
993  /// starting with the innermost dimensions found in step 2. The Quotient
994  /// is the SCEV to be divided in the next step of the recursion. The
995  /// Remainder is the subscript of the innermost dimension. Loop over all
996  /// array dimensions computed in step 2.
997  ///
998  /// To compute a uniform array size for several memory accesses to the same
999  /// object, one can collect in step 1 all the step terms for all the memory
1000  /// accesses, and compute in step 2 a unique array shape. This guarantees
1001  /// that the array shape will be the same across all memory accesses.
1002  ///
1003  /// FIXME: We could derive the result of steps 1 and 2 from a description of
1004  /// the array shape given in metadata.
1005  ///
1006  /// Example:
1007  ///
1008  /// A[][n][m]
1009  ///
1010  /// for i
1011  /// for j
1012  /// for k
1013  /// A[j+k][2i][5i] =
1014  ///
1015  /// The initial SCEV:
1016  ///
1017  /// A[{{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k]
1018  ///
1019  /// 1. Find the different terms in the step functions:
1020  /// -> [2*m, 5, n*m, n*m]
1021  ///
1022  /// 2. Compute the array size: sort and unique them
1023  /// -> [n*m, 2*m, 5]
1024  /// find the GCD of all the terms = 1
1025  /// divide by the GCD and erase constant terms
1026  /// -> [n*m, 2*m]
1027  /// GCD = m
1028  /// divide by GCD -> [n, 2]
1029  /// remove constant terms
1030  /// -> [n]
1031  /// size of the array is A[unknown][n][m]
1032  ///
1033  /// 3. Compute the access function
1034  /// a. Divide {{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k by the innermost size m
1035  /// Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k
1036  /// Remainder: {{{0,+,5}_i, +, 0}_j, +, 0}_k
1037  /// The remainder is the subscript of the innermost array dimension: [5i].
1038  ///
1039  /// b. Divide Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k by next outer size n
1040  /// Quotient: {{{0,+,0}_i, +, 1}_j, +, 1}_k
1041  /// Remainder: {{{0,+,2}_i, +, 0}_j, +, 0}_k
1042  /// The Remainder is the subscript of the next array dimension: [2i].
1043  ///
1044  /// The subscript of the outermost dimension is the Quotient: [j+k].
1045  ///
1046  /// Overall, we have: A[][n][m], and the access function: A[j+k][2i][5i].
1047  void delinearize(const SCEV *Expr, SmallVectorImpl<const SCEV *> &Subscripts,
1049  const SCEV *ElementSize);
1050 
1051  /// Return the DataLayout associated with the module this SCEV instance is
1052  /// operating on.
1053  const DataLayout &getDataLayout() const {
1054  return F.getParent()->getDataLayout();
1055  }
1056 
1057  const SCEVPredicate *getEqualPredicate(const SCEV *LHS, const SCEV *RHS);
1058 
1059  const SCEVPredicate *
1060  getWrapPredicate(const SCEVAddRecExpr *AR,
1062 
1063  /// Re-writes the SCEV according to the Predicates in \p A.
1064  const SCEV *rewriteUsingPredicate(const SCEV *S, const Loop *L,
1065  SCEVUnionPredicate &A);
1066  /// Tries to convert the \p S expression to an AddRec expression,
1067  /// adding additional predicates to \p Preds as required.
1068  const SCEVAddRecExpr *convertSCEVToAddRecWithPredicates(
1069  const SCEV *S, const Loop *L,
1071 
1072 private:
1073  /// A CallbackVH to arrange for ScalarEvolution to be notified whenever a
1074  /// Value is deleted.
1075  class SCEVCallbackVH final : public CallbackVH {
1076  ScalarEvolution *SE;
1077 
1078  void deleted() override;
1079  void allUsesReplacedWith(Value *New) override;
1080 
1081  public:
1082  SCEVCallbackVH(Value *V, ScalarEvolution *SE = nullptr);
1083  };
1084 
1085  friend class SCEVCallbackVH;
1086  friend class SCEVExpander;
1087  friend class SCEVUnknown;
1088 
1089  /// The function we are analyzing.
1090  Function &F;
1091 
1092  /// Does the module have any calls to the llvm.experimental.guard intrinsic
1093  /// at all? If this is false, we avoid doing work that will only help if
1094  /// thare are guards present in the IR.
1095  bool HasGuards;
1096 
1097  /// The target library information for the target we are targeting.
1098  TargetLibraryInfo &TLI;
1099 
1100  /// The tracker for \@llvm.assume intrinsics in this function.
1101  AssumptionCache &AC;
1102 
1103  /// The dominator tree.
1104  DominatorTree &DT;
1105 
1106  /// The loop information for the function we are currently analyzing.
1107  LoopInfo &LI;
1108 
1109  /// This SCEV is used to represent unknown trip counts and things.
1110  std::unique_ptr<SCEVCouldNotCompute> CouldNotCompute;
1111 
1112  /// The type for HasRecMap.
1114 
1115  /// This is a cache to record whether a SCEV contains any scAddRecExpr.
1116  HasRecMapType HasRecMap;
1117 
1118  /// The type for ExprValueMap.
1119  using ValueOffsetPair = std::pair<Value *, ConstantInt *>;
1121 
1122  /// ExprValueMap -- This map records the original values from which
1123  /// the SCEV expr is generated from.
1124  ///
1125  /// We want to represent the mapping as SCEV -> ValueOffsetPair instead
1126  /// of SCEV -> Value:
1127  /// Suppose we know S1 expands to V1, and
1128  /// S1 = S2 + C_a
1129  /// S3 = S2 + C_b
1130  /// where C_a and C_b are different SCEVConstants. Then we'd like to
1131  /// expand S3 as V1 - C_a + C_b instead of expanding S2 literally.
1132  /// It is helpful when S2 is a complex SCEV expr.
1133  ///
1134  /// In order to do that, we represent ExprValueMap as a mapping from
1135  /// SCEV to ValueOffsetPair. We will save both S1->{V1, 0} and
1136  /// S2->{V1, C_a} into the map when we create SCEV for V1. When S3
1137  /// is expanded, it will first expand S2 to V1 - C_a because of
1138  /// S2->{V1, C_a} in the map, then expand S3 to V1 - C_a + C_b.
1139  ///
1140  /// Note: S->{V, Offset} in the ExprValueMap means S can be expanded
1141  /// to V - Offset.
1142  ExprValueMapType ExprValueMap;
1143 
1144  /// The type for ValueExprMap.
1145  using ValueExprMapType =
1147 
1148  /// This is a cache of the values we have analyzed so far.
1149  ValueExprMapType ValueExprMap;
1150 
1151  /// Mark predicate values currently being processed by isImpliedCond.
1152  SmallPtrSet<Value *, 6> PendingLoopPredicates;
1153 
1154  /// Mark SCEVUnknown Phis currently being processed by getRangeRef.
1155  SmallPtrSet<const PHINode *, 6> PendingPhiRanges;
1156 
1157  // Mark SCEVUnknown Phis currently being processed by isImpliedViaMerge.
1158  SmallPtrSet<const PHINode *, 6> PendingMerges;
1159 
1160  /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of
1161  /// conditions dominating the backedge of a loop.
1162  bool WalkingBEDominatingConds = false;
1163 
1164  /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a
1165  /// predicate by splitting it into a set of independent predicates.
1166  bool ProvingSplitPredicate = false;
1167 
1168  /// Memoized values for the GetMinTrailingZeros
1169  DenseMap<const SCEV *, uint32_t> MinTrailingZerosCache;
1170 
1171  /// Return the Value set from which the SCEV expr is generated.
1172  SetVector<ValueOffsetPair> *getSCEVValues(const SCEV *S);
1173 
1174  /// Private helper method for the GetMinTrailingZeros method
1175  uint32_t GetMinTrailingZerosImpl(const SCEV *S);
1176 
1177  /// Information about the number of loop iterations for which a loop exit's
1178  /// branch condition evaluates to the not-taken path. This is a temporary
1179  /// pair of exact and max expressions that are eventually summarized in
1180  /// ExitNotTakenInfo and BackedgeTakenInfo.
1181  struct ExitLimit {
1182  const SCEV *ExactNotTaken; // The exit is not taken exactly this many times
1183  const SCEV *MaxNotTaken; // The exit is not taken at most this many times
1184 
1185  // Not taken either exactly MaxNotTaken or zero times
1186  bool MaxOrZero = false;
1187 
1188  /// A set of predicate guards for this ExitLimit. The result is only valid
1189  /// if all of the predicates in \c Predicates evaluate to 'true' at
1190  /// run-time.
1192 
1193  void addPredicate(const SCEVPredicate *P) {
1194  assert(!isa<SCEVUnionPredicate>(P) && "Only add leaf predicates here!");
1195  Predicates.insert(P);
1196  }
1197 
1198  /*implicit*/ ExitLimit(const SCEV *E);
1199 
1200  ExitLimit(
1201  const SCEV *E, const SCEV *M, bool MaxOrZero,
1202  ArrayRef<const SmallPtrSetImpl<const SCEVPredicate *> *> PredSetList);
1203 
1204  ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero,
1206 
1207  ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero);
1208 
1209  /// Test whether this ExitLimit contains any computed information, or
1210  /// whether it's all SCEVCouldNotCompute values.
1211  bool hasAnyInfo() const {
1212  return !isa<SCEVCouldNotCompute>(ExactNotTaken) ||
1213  !isa<SCEVCouldNotCompute>(MaxNotTaken);
1214  }
1215 
1216  bool hasOperand(const SCEV *S) const;
1217 
1218  /// Test whether this ExitLimit contains all information.
1219  bool hasFullInfo() const {
1220  return !isa<SCEVCouldNotCompute>(ExactNotTaken);
1221  }
1222  };
1223 
1224  /// Information about the number of times a particular loop exit may be
1225  /// reached before exiting the loop.
1226  struct ExitNotTakenInfo {
1227  PoisoningVH<BasicBlock> ExitingBlock;
1228  const SCEV *ExactNotTaken;
1229  std::unique_ptr<SCEVUnionPredicate> Predicate;
1230 
1231  explicit ExitNotTakenInfo(PoisoningVH<BasicBlock> ExitingBlock,
1232  const SCEV *ExactNotTaken,
1233  std::unique_ptr<SCEVUnionPredicate> Predicate)
1234  : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken),
1235  Predicate(std::move(Predicate)) {}
1236 
1237  bool hasAlwaysTruePredicate() const {
1238  return !Predicate || Predicate->isAlwaysTrue();
1239  }
1240  };
1241 
1242  /// Information about the backedge-taken count of a loop. This currently
1243  /// includes an exact count and a maximum count.
1244  ///
1245  class BackedgeTakenInfo {
1246  /// A list of computable exits and their not-taken counts. Loops almost
1247  /// never have more than one computable exit.
1248  SmallVector<ExitNotTakenInfo, 1> ExitNotTaken;
1249 
1250  /// The pointer part of \c MaxAndComplete is an expression indicating the
1251  /// least maximum backedge-taken count of the loop that is known, or a
1252  /// SCEVCouldNotCompute. This expression is only valid if the predicates
1253  /// associated with all loop exits are true.
1254  ///
1255  /// The integer part of \c MaxAndComplete is a boolean indicating if \c
1256  /// ExitNotTaken has an element for every exiting block in the loop.
1257  PointerIntPair<const SCEV *, 1> MaxAndComplete;
1258 
1259  /// True iff the backedge is taken either exactly Max or zero times.
1260  bool MaxOrZero = false;
1261 
1262  /// \name Helper projection functions on \c MaxAndComplete.
1263  /// @{
1264  bool isComplete() const { return MaxAndComplete.getInt(); }
1265  const SCEV *getMax() const { return MaxAndComplete.getPointer(); }
1266  /// @}
1267 
1268  public:
1269  BackedgeTakenInfo() : MaxAndComplete(nullptr, 0) {}
1270  BackedgeTakenInfo(BackedgeTakenInfo &&) = default;
1271  BackedgeTakenInfo &operator=(BackedgeTakenInfo &&) = default;
1272 
1273  using EdgeExitInfo = std::pair<BasicBlock *, ExitLimit>;
1274 
1275  /// Initialize BackedgeTakenInfo from a list of exact exit counts.
1276  BackedgeTakenInfo(SmallVectorImpl<EdgeExitInfo> &&ExitCounts, bool Complete,
1277  const SCEV *MaxCount, bool MaxOrZero);
1278 
1279  /// Test whether this BackedgeTakenInfo contains any computed information,
1280  /// or whether it's all SCEVCouldNotCompute values.
1281  bool hasAnyInfo() const {
1282  return !ExitNotTaken.empty() || !isa<SCEVCouldNotCompute>(getMax());
1283  }
1284 
1285  /// Test whether this BackedgeTakenInfo contains complete information.
1286  bool hasFullInfo() const { return isComplete(); }
1287 
1288  /// Return an expression indicating the exact *backedge-taken*
1289  /// count of the loop if it is known or SCEVCouldNotCompute
1290  /// otherwise. If execution makes it to the backedge on every
1291  /// iteration (i.e. there are no abnormal exists like exception
1292  /// throws and thread exits) then this is the number of times the
1293  /// loop header will execute minus one.
1294  ///
1295  /// If the SCEV predicate associated with the answer can be different
1296  /// from AlwaysTrue, we must add a (non null) Predicates argument.
1297  /// The SCEV predicate associated with the answer will be added to
1298  /// Predicates. A run-time check needs to be emitted for the SCEV
1299  /// predicate in order for the answer to be valid.
1300  ///
1301  /// Note that we should always know if we need to pass a predicate
1302  /// argument or not from the way the ExitCounts vector was computed.
1303  /// If we allowed SCEV predicates to be generated when populating this
1304  /// vector, this information can contain them and therefore a
1305  /// SCEVPredicate argument should be added to getExact.
1306  const SCEV *getExact(const Loop *L, ScalarEvolution *SE,
1307  SCEVUnionPredicate *Predicates = nullptr) const;
1308 
1309  /// Return the number of times this loop exit may fall through to the back
1310  /// edge, or SCEVCouldNotCompute. The loop is guaranteed not to exit via
1311  /// this block before this number of iterations, but may exit via another
1312  /// block.
1313  const SCEV *getExact(BasicBlock *ExitingBlock, ScalarEvolution *SE) const;
1314 
1315  /// Get the max backedge taken count for the loop.
1316  const SCEV *getMax(ScalarEvolution *SE) const;
1317 
1318  /// Return true if the number of times this backedge is taken is either the
1319  /// value returned by getMax or zero.
1320  bool isMaxOrZero(ScalarEvolution *SE) const;
1321 
1322  /// Return true if any backedge taken count expressions refer to the given
1323  /// subexpression.
1324  bool hasOperand(const SCEV *S, ScalarEvolution *SE) const;
1325 
1326  /// Invalidate this result and free associated memory.
1327  void clear();
1328  };
1329 
1330  /// Cache the backedge-taken count of the loops for this function as they
1331  /// are computed.
1332  DenseMap<const Loop *, BackedgeTakenInfo> BackedgeTakenCounts;
1333 
1334  /// Cache the predicated backedge-taken count of the loops for this
1335  /// function as they are computed.
1336  DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts;
1337 
1338  /// This map contains entries for all of the PHI instructions that we
1339  /// attempt to compute constant evolutions for. This allows us to avoid
1340  /// potentially expensive recomputation of these properties. An instruction
1341  /// maps to null if we are unable to compute its exit value.
1342  DenseMap<PHINode *, Constant *> ConstantEvolutionLoopExitValue;
1343 
1344  /// This map contains entries for all the expressions that we attempt to
1345  /// compute getSCEVAtScope information for, which can be expensive in
1346  /// extreme cases.
1348  ValuesAtScopes;
1349 
1350  /// Memoized computeLoopDisposition results.
1351  DenseMap<const SCEV *,
1353  LoopDispositions;
1354 
1355  struct LoopProperties {
1356  /// Set to true if the loop contains no instruction that can have side
1357  /// effects (i.e. via throwing an exception, volatile or atomic access).
1358  bool HasNoAbnormalExits;
1359 
1360  /// Set to true if the loop contains no instruction that can abnormally exit
1361  /// the loop (i.e. via throwing an exception, by terminating the thread
1362  /// cleanly or by infinite looping in a called function). Strictly
1363  /// speaking, the last one is not leaving the loop, but is identical to
1364  /// leaving the loop for reasoning about undefined behavior.
1365  bool HasNoSideEffects;
1366  };
1367 
1368  /// Cache for \c getLoopProperties.
1369  DenseMap<const Loop *, LoopProperties> LoopPropertiesCache;
1370 
1371  /// Return a \c LoopProperties instance for \p L, creating one if necessary.
1372  LoopProperties getLoopProperties(const Loop *L);
1373 
1374  bool loopHasNoSideEffects(const Loop *L) {
1375  return getLoopProperties(L).HasNoSideEffects;
1376  }
1377 
1378  bool loopHasNoAbnormalExits(const Loop *L) {
1379  return getLoopProperties(L).HasNoAbnormalExits;
1380  }
1381 
1382  /// Compute a LoopDisposition value.
1383  LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L);
1384 
1385  /// Memoized computeBlockDisposition results.
1386  DenseMap<
1387  const SCEV *,
1389  BlockDispositions;
1390 
1391  /// Compute a BlockDisposition value.
1392  BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB);
1393 
1394  /// Memoized results from getRange
1396 
1397  /// Memoized results from getRange
1399 
1400  /// Used to parameterize getRange
1401  enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED };
1402 
1403  /// Set the memoized range for the given SCEV.
1404  const ConstantRange &setRange(const SCEV *S, RangeSignHint Hint,
1405  ConstantRange CR) {
1407  Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges;
1408 
1409  auto Pair = Cache.try_emplace(S, std::move(CR));
1410  if (!Pair.second)
1411  Pair.first->second = std::move(CR);
1412  return Pair.first->second;
1413  }
1414 
1415  /// Determine the range for a particular SCEV.
1416  /// NOTE: This returns a reference to an entry in a cache. It must be
1417  /// copied if its needed for longer.
1418  const ConstantRange &getRangeRef(const SCEV *S, RangeSignHint Hint);
1419 
1420  /// Determines the range for the affine SCEVAddRecExpr {\p Start,+,\p Stop}.
1421  /// Helper for \c getRange.
1422  ConstantRange getRangeForAffineAR(const SCEV *Start, const SCEV *Stop,
1423  const SCEV *MaxBECount, unsigned BitWidth);
1424 
1425  /// Try to compute a range for the affine SCEVAddRecExpr {\p Start,+,\p
1426  /// Stop} by "factoring out" a ternary expression from the add recurrence.
1427  /// Helper called by \c getRange.
1428  ConstantRange getRangeViaFactoring(const SCEV *Start, const SCEV *Stop,
1429  const SCEV *MaxBECount, unsigned BitWidth);
1430 
1431  /// We know that there is no SCEV for the specified value. Analyze the
1432  /// expression.
1433  const SCEV *createSCEV(Value *V);
1434 
1435  /// Provide the special handling we need to analyze PHI SCEVs.
1436  const SCEV *createNodeForPHI(PHINode *PN);
1437 
1438  /// Helper function called from createNodeForPHI.
1439  const SCEV *createAddRecFromPHI(PHINode *PN);
1440 
1441  /// A helper function for createAddRecFromPHI to handle simple cases.
1442  const SCEV *createSimpleAffineAddRec(PHINode *PN, Value *BEValueV,
1443  Value *StartValueV);
1444 
1445  /// Helper function called from createNodeForPHI.
1446  const SCEV *createNodeFromSelectLikePHI(PHINode *PN);
1447 
1448  /// Provide special handling for a select-like instruction (currently this
1449  /// is either a select instruction or a phi node). \p I is the instruction
1450  /// being processed, and it is assumed equivalent to "Cond ? TrueVal :
1451  /// FalseVal".
1452  const SCEV *createNodeForSelectOrPHI(Instruction *I, Value *Cond,
1453  Value *TrueVal, Value *FalseVal);
1454 
1455  /// Provide the special handling we need to analyze GEP SCEVs.
1456  const SCEV *createNodeForGEP(GEPOperator *GEP);
1457 
1458  /// Implementation code for getSCEVAtScope; called at most once for each
1459  /// SCEV+Loop pair.
1460  const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L);
1461 
1462  /// This looks up computed SCEV values for all instructions that depend on
1463  /// the given instruction and removes them from the ValueExprMap map if they
1464  /// reference SymName. This is used during PHI resolution.
1465  void forgetSymbolicName(Instruction *I, const SCEV *SymName);
1466 
1467  /// Return the BackedgeTakenInfo for the given loop, lazily computing new
1468  /// values if the loop hasn't been analyzed yet. The returned result is
1469  /// guaranteed not to be predicated.
1470  const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L);
1471 
1472  /// Similar to getBackedgeTakenInfo, but will add predicates as required
1473  /// with the purpose of returning complete information.
1474  const BackedgeTakenInfo &getPredicatedBackedgeTakenInfo(const Loop *L);
1475 
1476  /// Compute the number of times the specified loop will iterate.
1477  /// If AllowPredicates is set, we will create new SCEV predicates as
1478  /// necessary in order to return an exact answer.
1479  BackedgeTakenInfo computeBackedgeTakenCount(const Loop *L,
1480  bool AllowPredicates = false);
1481 
1482  /// Compute the number of times the backedge of the specified loop will
1483  /// execute if it exits via the specified block. If AllowPredicates is set,
1484  /// this call will try to use a minimal set of SCEV predicates in order to
1485  /// return an exact answer.
1486  ExitLimit computeExitLimit(const Loop *L, BasicBlock *ExitingBlock,
1487  bool AllowPredicates = false);
1488 
1489  /// Compute the number of times the backedge of the specified loop will
1490  /// execute if its exit condition were a conditional branch of ExitCond.
1491  ///
1492  /// \p ControlsExit is true if ExitCond directly controls the exit
1493  /// branch. In this case, we can assume that the loop exits only if the
1494  /// condition is true and can infer that failing to meet the condition prior
1495  /// to integer wraparound results in undefined behavior.
1496  ///
1497  /// If \p AllowPredicates is set, this call will try to use a minimal set of
1498  /// SCEV predicates in order to return an exact answer.
1499  ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond,
1500  bool ExitIfTrue, bool ControlsExit,
1501  bool AllowPredicates = false);
1502 
1503  // Helper functions for computeExitLimitFromCond to avoid exponential time
1504  // complexity.
1505 
1506  class ExitLimitCache {
1507  // It may look like we need key on the whole (L, ExitIfTrue, ControlsExit,
1508  // AllowPredicates) tuple, but recursive calls to
1509  // computeExitLimitFromCondCached from computeExitLimitFromCondImpl only
1510  // vary the in \c ExitCond and \c ControlsExit parameters. We remember the
1511  // initial values of the other values to assert our assumption.
1512  SmallDenseMap<PointerIntPair<Value *, 1>, ExitLimit> TripCountMap;
1513 
1514  const Loop *L;
1515  bool ExitIfTrue;
1516  bool AllowPredicates;
1517 
1518  public:
1519  ExitLimitCache(const Loop *L, bool ExitIfTrue, bool AllowPredicates)
1520  : L(L), ExitIfTrue(ExitIfTrue), AllowPredicates(AllowPredicates) {}
1521 
1522  Optional<ExitLimit> find(const Loop *L, Value *ExitCond, bool ExitIfTrue,
1523  bool ControlsExit, bool AllowPredicates);
1524 
1525  void insert(const Loop *L, Value *ExitCond, bool ExitIfTrue,
1526  bool ControlsExit, bool AllowPredicates, const ExitLimit &EL);
1527  };
1528 
1529  using ExitLimitCacheTy = ExitLimitCache;
1530 
1531  ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache,
1532  const Loop *L, Value *ExitCond,
1533  bool ExitIfTrue,
1534  bool ControlsExit,
1535  bool AllowPredicates);
1536  ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache, const Loop *L,
1537  Value *ExitCond, bool ExitIfTrue,
1538  bool ControlsExit,
1539  bool AllowPredicates);
1540 
1541  /// Compute the number of times the backedge of the specified loop will
1542  /// execute if its exit condition were a conditional branch of the ICmpInst
1543  /// ExitCond and ExitIfTrue. If AllowPredicates is set, this call will try
1544  /// to use a minimal set of SCEV predicates in order to return an exact
1545  /// answer.
1546  ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond,
1547  bool ExitIfTrue,
1548  bool IsSubExpr,
1549  bool AllowPredicates = false);
1550 
1551  /// Compute the number of times the backedge of the specified loop will
1552  /// execute if its exit condition were a switch with a single exiting case
1553  /// to ExitingBB.
1554  ExitLimit computeExitLimitFromSingleExitSwitch(const Loop *L,
1555  SwitchInst *Switch,
1556  BasicBlock *ExitingBB,
1557  bool IsSubExpr);
1558 
1559  /// Given an exit condition of 'icmp op load X, cst', try to see if we can
1560  /// compute the backedge-taken count.
1561  ExitLimit computeLoadConstantCompareExitLimit(LoadInst *LI, Constant *RHS,
1562  const Loop *L,
1564 
1565  /// Compute the exit limit of a loop that is controlled by a
1566  /// "(IV >> 1) != 0" type comparison. We cannot compute the exact trip
1567  /// count in these cases (since SCEV has no way of expressing them), but we
1568  /// can still sometimes compute an upper bound.
1569  ///
1570  /// Return an ExitLimit for a loop whose backedge is guarded by `LHS Pred
1571  /// RHS`.
1572  ExitLimit computeShiftCompareExitLimit(Value *LHS, Value *RHS, const Loop *L,
1573  ICmpInst::Predicate Pred);
1574 
1575  /// If the loop is known to execute a constant number of times (the
1576  /// condition evolves only from constants), try to evaluate a few iterations
1577  /// of the loop until we get the exit condition gets a value of ExitWhen
1578  /// (true or false). If we cannot evaluate the exit count of the loop,
1579  /// return CouldNotCompute.
1580  const SCEV *computeExitCountExhaustively(const Loop *L, Value *Cond,
1581  bool ExitWhen);
1582 
1583  /// Return the number of times an exit condition comparing the specified
1584  /// value to zero will execute. If not computable, return CouldNotCompute.
1585  /// If AllowPredicates is set, this call will try to use a minimal set of
1586  /// SCEV predicates in order to return an exact answer.
1587  ExitLimit howFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr,
1588  bool AllowPredicates = false);
1589 
1590  /// Return the number of times an exit condition checking the specified
1591  /// value for nonzero will execute. If not computable, return
1592  /// CouldNotCompute.
1593  ExitLimit howFarToNonZero(const SCEV *V, const Loop *L);
1594 
1595  /// Return the number of times an exit condition containing the specified
1596  /// less-than comparison will execute. If not computable, return
1597  /// CouldNotCompute.
1598  ///
1599  /// \p isSigned specifies whether the less-than is signed.
1600  ///
1601  /// \p ControlsExit is true when the LHS < RHS condition directly controls
1602  /// the branch (loops exits only if condition is true). In this case, we can
1603  /// use NoWrapFlags to skip overflow checks.
1604  ///
1605  /// If \p AllowPredicates is set, this call will try to use a minimal set of
1606  /// SCEV predicates in order to return an exact answer.
1607  ExitLimit howManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
1608  bool isSigned, bool ControlsExit,
1609  bool AllowPredicates = false);
1610 
1611  ExitLimit howManyGreaterThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
1612  bool isSigned, bool IsSubExpr,
1613  bool AllowPredicates = false);
1614 
1615  /// Return a predecessor of BB (which may not be an immediate predecessor)
1616  /// which has exactly one successor from which BB is reachable, or null if
1617  /// no such block is found.
1618  std::pair<BasicBlock *, BasicBlock *>
1619  getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB);
1620 
1621  /// Test whether the condition described by Pred, LHS, and RHS is true
1622  /// whenever the given FoundCondValue value evaluates to true.
1623  bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
1624  Value *FoundCondValue, bool Inverse);
1625 
1626  /// Test whether the condition described by Pred, LHS, and RHS is true
1627  /// whenever the condition described by FoundPred, FoundLHS, FoundRHS is
1628  /// true.
1629  bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
1630  ICmpInst::Predicate FoundPred, const SCEV *FoundLHS,
1631  const SCEV *FoundRHS);
1632 
1633  /// Test whether the condition described by Pred, LHS, and RHS is true
1634  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1635  /// true.
1636  bool isImpliedCondOperands(ICmpInst::Predicate Pred, const SCEV *LHS,
1637  const SCEV *RHS, const SCEV *FoundLHS,
1638  const SCEV *FoundRHS);
1639 
1640  /// Test whether the condition described by Pred, LHS, and RHS is true
1641  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1642  /// true. Here LHS is an operation that includes FoundLHS as one of its
1643  /// arguments.
1644  bool isImpliedViaOperations(ICmpInst::Predicate Pred,
1645  const SCEV *LHS, const SCEV *RHS,
1646  const SCEV *FoundLHS, const SCEV *FoundRHS,
1647  unsigned Depth = 0);
1648 
1649  /// Test whether the condition described by Pred, LHS, and RHS is true.
1650  /// Use only simple non-recursive types of checks, such as range analysis etc.
1651  bool isKnownViaNonRecursiveReasoning(ICmpInst::Predicate Pred,
1652  const SCEV *LHS, const SCEV *RHS);
1653 
1654  /// Test whether the condition described by Pred, LHS, and RHS is true
1655  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1656  /// true.
1657  bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, const SCEV *LHS,
1658  const SCEV *RHS, const SCEV *FoundLHS,
1659  const SCEV *FoundRHS);
1660 
1661  /// Test whether the condition described by Pred, LHS, and RHS is true
1662  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1663  /// true. Utility function used by isImpliedCondOperands. Tries to get
1664  /// cases like "X `sgt` 0 => X - 1 `sgt` -1".
1665  bool isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred, const SCEV *LHS,
1666  const SCEV *RHS, const SCEV *FoundLHS,
1667  const SCEV *FoundRHS);
1668 
1669  /// Return true if the condition denoted by \p LHS \p Pred \p RHS is implied
1670  /// by a call to \c @llvm.experimental.guard in \p BB.
1671  bool isImpliedViaGuard(BasicBlock *BB, ICmpInst::Predicate Pred,
1672  const SCEV *LHS, const SCEV *RHS);
1673 
1674  /// Test whether the condition described by Pred, LHS, and RHS is true
1675  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1676  /// true.
1677  ///
1678  /// This routine tries to rule out certain kinds of integer overflow, and
1679  /// then tries to reason about arithmetic properties of the predicates.
1680  bool isImpliedCondOperandsViaNoOverflow(ICmpInst::Predicate Pred,
1681  const SCEV *LHS, const SCEV *RHS,
1682  const SCEV *FoundLHS,
1683  const SCEV *FoundRHS);
1684 
1685  /// Test whether the condition described by Pred, LHS, and RHS is true
1686  /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1687  /// true.
1688  ///
1689  /// This routine tries to figure out predicate for Phis which are SCEVUnknown
1690  /// if it is true for every possible incoming value from their respective
1691  /// basic blocks.
1692  bool isImpliedViaMerge(ICmpInst::Predicate Pred,
1693  const SCEV *LHS, const SCEV *RHS,
1694  const SCEV *FoundLHS, const SCEV *FoundRHS,
1695  unsigned Depth);
1696 
1697  /// If we know that the specified Phi is in the header of its containing
1698  /// loop, we know the loop executes a constant number of times, and the PHI
1699  /// node is just a recurrence involving constants, fold it.
1700  Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt &BEs,
1701  const Loop *L);
1702 
1703  /// Test if the given expression is known to satisfy the condition described
1704  /// by Pred and the known constant ranges of LHS and RHS.
1705  bool isKnownPredicateViaConstantRanges(ICmpInst::Predicate Pred,
1706  const SCEV *LHS, const SCEV *RHS);
1707 
1708  /// Try to prove the condition described by "LHS Pred RHS" by ruling out
1709  /// integer overflow.
1710  ///
1711  /// For instance, this will return true for "A s< (A + C)<nsw>" if C is
1712  /// positive.
1713  bool isKnownPredicateViaNoOverflow(ICmpInst::Predicate Pred, const SCEV *LHS,
1714  const SCEV *RHS);
1715 
1716  /// Try to split Pred LHS RHS into logical conjunctions (and's) and try to
1717  /// prove them individually.
1718  bool isKnownPredicateViaSplitting(ICmpInst::Predicate Pred, const SCEV *LHS,
1719  const SCEV *RHS);
1720 
1721  /// Try to match the Expr as "(L + R)<Flags>".
1722  bool splitBinaryAdd(const SCEV *Expr, const SCEV *&L, const SCEV *&R,
1723  SCEV::NoWrapFlags &Flags);
1724 
1725  /// Compute \p LHS - \p RHS and returns the result as an APInt if it is a
1726  /// constant, and None if it isn't.
1727  ///
1728  /// This is intended to be a cheaper version of getMinusSCEV. We can be
1729  /// frugal here since we just bail out of actually constructing and
1730  /// canonicalizing an expression in the cases where the result isn't going
1731  /// to be a constant.
1732  Optional<APInt> computeConstantDifference(const SCEV *LHS, const SCEV *RHS);
1733 
1734  /// Drop memoized information computed for S.
1735  void forgetMemoizedResults(const SCEV *S);
1736 
1737  /// Return an existing SCEV for V if there is one, otherwise return nullptr.
1738  const SCEV *getExistingSCEV(Value *V);
1739 
1740  /// Return false iff given SCEV contains a SCEVUnknown with NULL value-
1741  /// pointer.
1742  bool checkValidity(const SCEV *S) const;
1743 
1744  /// Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be
1745  /// equal to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}. This is
1746  /// equivalent to proving no signed (resp. unsigned) wrap in
1747  /// {`Start`,+,`Step`} if `ExtendOpTy` is `SCEVSignExtendExpr`
1748  /// (resp. `SCEVZeroExtendExpr`).
1749  template <typename ExtendOpTy>
1750  bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step,
1751  const Loop *L);
1752 
1753  /// Try to prove NSW or NUW on \p AR relying on ConstantRange manipulation.
1754  SCEV::NoWrapFlags proveNoWrapViaConstantRanges(const SCEVAddRecExpr *AR);
1755 
1756  bool isMonotonicPredicateImpl(const SCEVAddRecExpr *LHS,
1757  ICmpInst::Predicate Pred, bool &Increasing);
1758 
1759  /// Return SCEV no-wrap flags that can be proven based on reasoning about
1760  /// how poison produced from no-wrap flags on this value (e.g. a nuw add)
1761  /// would trigger undefined behavior on overflow.
1762  SCEV::NoWrapFlags getNoWrapFlagsFromUB(const Value *V);
1763 
1764  /// Return true if the SCEV corresponding to \p I is never poison. Proving
1765  /// this is more complex than proving that just \p I is never poison, since
1766  /// SCEV commons expressions across control flow, and you can have cases
1767  /// like:
1768  ///
1769  /// idx0 = a + b;
1770  /// ptr[idx0] = 100;
1771  /// if (<condition>) {
1772  /// idx1 = a +nsw b;
1773  /// ptr[idx1] = 200;
1774  /// }
1775  ///
1776  /// where the SCEV expression (+ a b) is guaranteed to not be poison (and
1777  /// hence not sign-overflow) only if "<condition>" is true. Since both
1778  /// `idx0` and `idx1` will be mapped to the same SCEV expression, (+ a b),
1779  /// it is not okay to annotate (+ a b) with <nsw> in the above example.
1780  bool isSCEVExprNeverPoison(const Instruction *I);
1781 
1782  /// This is like \c isSCEVExprNeverPoison but it specifically works for
1783  /// instructions that will get mapped to SCEV add recurrences. Return true
1784  /// if \p I will never generate poison under the assumption that \p I is an
1785  /// add recurrence on the loop \p L.
1786  bool isAddRecNeverPoison(const Instruction *I, const Loop *L);
1787 
1788  /// Similar to createAddRecFromPHI, but with the additional flexibility of
1789  /// suggesting runtime overflow checks in case casts are encountered.
1790  /// If successful, the analysis records that for this loop, \p SymbolicPHI,
1791  /// which is the UnknownSCEV currently representing the PHI, can be rewritten
1792  /// into an AddRec, assuming some predicates; The function then returns the
1793  /// AddRec and the predicates as a pair, and caches this pair in
1794  /// PredicatedSCEVRewrites.
1795  /// If the analysis is not successful, a mapping from the \p SymbolicPHI to
1796  /// itself (with no predicates) is recorded, and a nullptr with an empty
1797  /// predicates vector is returned as a pair.
1799  createAddRecFromPHIWithCastsImpl(const SCEVUnknown *SymbolicPHI);
1800 
1801  /// Compute the backedge taken count knowing the interval difference, the
1802  /// stride and presence of the equality in the comparison.
1803  const SCEV *computeBECount(const SCEV *Delta, const SCEV *Stride,
1804  bool Equality);
1805 
1806  /// Compute the maximum backedge count based on the range of values
1807  /// permitted by Start, End, and Stride. This is for loops of the form
1808  /// {Start, +, Stride} LT End.
1809  ///
1810  /// Precondition: the induction variable is known to be positive. We *don't*
1811  /// assert these preconditions so please be careful.
1812  const SCEV *computeMaxBECountForLT(const SCEV *Start, const SCEV *Stride,
1813  const SCEV *End, unsigned BitWidth,
1814  bool IsSigned);
1815 
1816  /// Verify if an linear IV with positive stride can overflow when in a
1817  /// less-than comparison, knowing the invariant term of the comparison,
1818  /// the stride and the knowledge of NSW/NUW flags on the recurrence.
1819  bool doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, bool IsSigned,
1820  bool NoWrap);
1821 
1822  /// Verify if an linear IV with negative stride can overflow when in a
1823  /// greater-than comparison, knowing the invariant term of the comparison,
1824  /// the stride and the knowledge of NSW/NUW flags on the recurrence.
1825  bool doesIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, bool IsSigned,
1826  bool NoWrap);
1827 
1828  /// Get add expr already created or create a new one.
1829  const SCEV *getOrCreateAddExpr(SmallVectorImpl<const SCEV *> &Ops,
1830  SCEV::NoWrapFlags Flags);
1831 
1832  /// Get mul expr already created or create a new one.
1833  const SCEV *getOrCreateMulExpr(SmallVectorImpl<const SCEV *> &Ops,
1834  SCEV::NoWrapFlags Flags);
1835 
1836  /// Return x if \p Val is f(x) where f is a 1-1 function.
1837  const SCEV *stripInjectiveFunctions(const SCEV *Val) const;
1838 
1839  /// Find all of the loops transitively used in \p S, and fill \p LoopsUsed.
1840  /// A loop is considered "used" by an expression if it contains
1841  /// an add rec on said loop.
1842  void getUsedLoops(const SCEV *S, SmallPtrSetImpl<const Loop *> &LoopsUsed);
1843 
1844  /// Find all of the loops transitively used in \p S, and update \c LoopUsers
1845  /// accordingly.
1846  void addToLoopUseLists(const SCEV *S);
1847 
1848  /// Try to match the pattern generated by getURemExpr(A, B). If successful,
1849  /// Assign A and B to LHS and RHS, respectively.
1850  bool matchURem(const SCEV *Expr, const SCEV *&LHS, const SCEV *&RHS);
1851 
1852  FoldingSet<SCEV> UniqueSCEVs;
1853  FoldingSet<SCEVPredicate> UniquePreds;
1854  BumpPtrAllocator SCEVAllocator;
1855 
1856  /// This maps loops to a list of SCEV expressions that (transitively) use said
1857  /// loop.
1859 
1860  /// Cache tentative mappings from UnknownSCEVs in a Loop, to a SCEV expression
1861  /// they can be rewritten into under certain predicates.
1863  std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
1864  PredicatedSCEVRewrites;
1865 
1866  /// The head of a linked list of all SCEVUnknown values that have been
1867  /// allocated. This is used by releaseMemory to locate them all and call
1868  /// their destructors.
1869  SCEVUnknown *FirstUnknown = nullptr;
1870 };
1871 
1872 /// Analysis pass that exposes the \c ScalarEvolution for a function.
1874  : public AnalysisInfoMixin<ScalarEvolutionAnalysis> {
1876 
1877  static AnalysisKey Key;
1878 
1879 public:
1881 
1883 };
1884 
1885 /// Printer pass for the \c ScalarEvolutionAnalysis results.
1887  : public PassInfoMixin<ScalarEvolutionPrinterPass> {
1888  raw_ostream &OS;
1889 
1890 public:
1891  explicit ScalarEvolutionPrinterPass(raw_ostream &OS) : OS(OS) {}
1892 
1894 };
1895 
1897  std::unique_ptr<ScalarEvolution> SE;
1898 
1899 public:
1900  static char ID;
1901 
1903 
1904  ScalarEvolution &getSE() { return *SE; }
1905  const ScalarEvolution &getSE() const { return *SE; }
1906 
1907  bool runOnFunction(Function &F) override;
1908  void releaseMemory() override;
1909  void getAnalysisUsage(AnalysisUsage &AU) const override;
1910  void print(raw_ostream &OS, const Module * = nullptr) const override;
1911  void verifyAnalysis() const override;
1912 };
1913 
1914 /// An interface layer with SCEV used to manage how we see SCEV expressions
1915 /// for values in the context of existing predicates. We can add new
1916 /// predicates, but we cannot remove them.
1917 ///
1918 /// This layer has multiple purposes:
1919 /// - provides a simple interface for SCEV versioning.
1920 /// - guarantees that the order of transformations applied on a SCEV
1921 /// expression for a single Value is consistent across two different
1922 /// getSCEV calls. This means that, for example, once we've obtained
1923 /// an AddRec expression for a certain value through expression
1924 /// rewriting, we will continue to get an AddRec expression for that
1925 /// Value.
1926 /// - lowers the number of expression rewrites.
1928 public:
1930 
1931  const SCEVUnionPredicate &getUnionPredicate() const;
1932 
1933  /// Returns the SCEV expression of V, in the context of the current SCEV
1934  /// predicate. The order of transformations applied on the expression of V
1935  /// returned by ScalarEvolution is guaranteed to be preserved, even when
1936  /// adding new predicates.
1937  const SCEV *getSCEV(Value *V);
1938 
1939  /// Get the (predicated) backedge count for the analyzed loop.
1940  const SCEV *getBackedgeTakenCount();
1941 
1942  /// Adds a new predicate.
1943  void addPredicate(const SCEVPredicate &Pred);
1944 
1945  /// Attempts to produce an AddRecExpr for V by adding additional SCEV
1946  /// predicates. If we can't transform the expression into an AddRecExpr we
1947  /// return nullptr and not add additional SCEV predicates to the current
1948  /// context.
1949  const SCEVAddRecExpr *getAsAddRec(Value *V);
1950 
1951  /// Proves that V doesn't overflow by adding SCEV predicate.
1952  void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags);
1953 
1954  /// Returns true if we've proved that V doesn't wrap by means of a SCEV
1955  /// predicate.
1956  bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags);
1957 
1958  /// Returns the ScalarEvolution analysis used.
1959  ScalarEvolution *getSE() const { return &SE; }
1960 
1961  /// We need to explicitly define the copy constructor because of FlagsMap.
1963 
1964  /// Print the SCEV mappings done by the Predicated Scalar Evolution.
1965  /// The printed text is indented by \p Depth.
1966  void print(raw_ostream &OS, unsigned Depth) const;
1967 
1968  /// Check if \p AR1 and \p AR2 are equal, while taking into account
1969  /// Equal predicates in Preds.
1970  bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1,
1971  const SCEVAddRecExpr *AR2) const;
1972 
1973 private:
1974  /// Increments the version number of the predicate. This needs to be called
1975  /// every time the SCEV predicate changes.
1976  void updateGeneration();
1977 
1978  /// Holds a SCEV and the version number of the SCEV predicate used to
1979  /// perform the rewrite of the expression.
1980  using RewriteEntry = std::pair<unsigned, const SCEV *>;
1981 
1982  /// Maps a SCEV to the rewrite result of that SCEV at a certain version
1983  /// number. If this number doesn't match the current Generation, we will
1984  /// need to do a rewrite. To preserve the transformation order of previous
1985  /// rewrites, we will rewrite the previous result instead of the original
1986  /// SCEV.
1988 
1989  /// Records what NoWrap flags we've added to a Value *.
1991 
1992  /// The ScalarEvolution analysis.
1993  ScalarEvolution &SE;
1994 
1995  /// The analyzed Loop.
1996  const Loop &L;
1997 
1998  /// The SCEVPredicate that forms our context. We will rewrite all
1999  /// expressions assuming that this predicate true.
2000  SCEVUnionPredicate Preds;
2001 
2002  /// Marks the version of the SCEV predicate used. When rewriting a SCEV
2003  /// expression we mark it with the version of the predicate. We use this to
2004  /// figure out if the predicate has changed from the last rewrite of the
2005  /// SCEV. If so, we need to perform a new rewrite.
2006  unsigned Generation = 0;
2007 
2008  /// The backedge taken count.
2009  const SCEV *BackedgeCount = nullptr;
2010 };
2011 
2012 } // end namespace llvm
2013 
2014 #endif // LLVM_ANALYSIS_SCALAREVOLUTION_H
ExitLimitQuery(const Loop *L, BasicBlock *ExitingBlock, bool AllowPredicates)
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
const ScalarEvolution & getSE() const
static Type * getWiderType(const DataLayout &DL, Type *Ty0, Type *Ty1)
static bool isLoopInvariant(Value *V, const Loop *L, const DominatorTree *DT)
Perform a quick domtree based check for loop invariance assuming that V is used within the loop...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
SCEV & operator=(const SCEV &)=delete
PointerTy getPointer() const
Various leaf nodes.
Definition: ISDOpcodes.h:60
static unsigned ComputeHash(const SCEVPredicate &X, FoldingSetNodeID &TempID)
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:137
void dump() const
This method is used for debugging.
The main scalar evolution driver.
bool isZero() const
Return true if the expression is a constant zero.
const SCEV * getAddRecExpr(const SmallVectorImpl< const SCEV *> &Operands, const Loop *L, SCEV::NoWrapFlags Flags)
IncrementWrapFlags
Similar to SCEV::NoWrapFlags, but with slightly different semantics for FlagNUSW. ...
static LLVM_NODISCARD SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
static bool Equals(const SCEVPredicate &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)
A cache of @llvm.assume calls within a function.
APInt getSignedRangeMin(const SCEV *S)
Determine the min of the signed range for a particular SCEV.
F(f)
An instruction for reading from memory.
Definition: Instructions.h:168
Hexagon Common GEP
An object of this class is returned by queries that could not be answered.
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
APInt getSignedRangeMax(const SCEV *S)
Determine the max of the signed range for a particular SCEV.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
The SCEV is loop-invariant.
static LLVM_NODISCARD SCEVWrapPredicate::IncrementWrapFlags setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OnFlags)
Definition: BitVector.h:921
const SCEV * getAddExpr(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
Class to represent struct types.
Definition: DerivedTypes.h:201
APInt getUnsignedRangeMax(const SCEV *S)
Determine the max of the unsigned range for a particular SCEV.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
unsigned short SubclassData
This field is initialized to zero and may be used in subclasses to store miscellaneous information...
LLVMContext & getContext() const
BasicBlock * ExitingBlock
This file implements a class to represent arbitrary precision integral constant values and operations...
static int64_t getConstant(const MachineInstr *MI)
Key
PAL metadata keys.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
This node represents a polynomial recurrence on the trip count of the specified loop.
IntType getInt() const
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:365
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:142
void forgetLoopDispositions(const Loop *L)
Called when the client has changed the disposition of values in this loop.
Value handle that poisons itself if the Value is deleted.
Definition: ValueHandle.h:450
unsigned ComputeHash() const
ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef, used to lookup the node in th...
Definition: FoldingSet.cpp:30
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:306
Printer pass for the ScalarEvolutionAnalysis results.
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
APInt getUnsignedRangeMin(const SCEV *S)
Determine the min of the unsigned range for a particular SCEV.
FoldingSetTrait - This trait class is used to define behavior of how to "profile" (in the FoldingSet ...
Definition: FoldingSet.h:250
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)
SCEVPredicateKind getKind() const
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
PointerIntPair - This class implements a pair of a pointer and small integer.
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:140
bool isKnownNonNegative(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Returns true if the give value is known to be non-negative.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:117
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:371
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:382
ScalarEvolutionPrinterPass(raw_ostream &OS)
Represent the analysis usage information of a pass.
This instruction compares its operands according to the predicate given to the constructor.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:885
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
static LLVM_NODISCARD SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
const SCEV * getLHS() const
Returns the left hand side of the equality.
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:194
const SCEV * getRHS() const
Returns the right hand side of the equality.
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:929
FoldingSet - This template class is used to instantiate a specialized implementation of the folding s...
Definition: FoldingSet.h:474
bool verify(const TargetRegisterInfo &TRI) const
Check that information hold by this instance make sense for the given TRI.
static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID)
static ExitLimitQuery getEmptyKey()
The SCEV is loop-variant (unknown).
This class represents an assumption made using SCEV expressions which can be checked at run-time...
void print(raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
unsigned getSCEVType() const
bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
See the file comment.
Definition: ValueMap.h:86
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
bool isAllOnesValue() const
Return true if the expression is a constant all-ones value.
Type * getType() const
Return the LLVM type of this SCEV expression.
static LLVM_NODISCARD SCEVWrapPredicate::IncrementWrapFlags clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OffFlags)
Convenient IncrementWrapFlags manipulation methods.
static bool isEqual(ExitLimitQuery LHS, ExitLimitQuery RHS)
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:861
Provides information about what library functions are available for the current target.
The SCEV dominates the block.
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:27
This class represents a range of values.
Definition: ConstantRange.h:47
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
static LLVM_NODISCARD SCEVWrapPredicate::IncrementWrapFlags maskFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, int Mask)
static void Profile(const SCEV &X, FoldingSetNodeID &ID)
static void Profile(const SCEVPredicate &X, FoldingSetNodeID &ID)
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
Class for arbitrary precision integers.
Definition: APInt.h:69
virtual void print(raw_ostream &OS, unsigned Depth=0) const =0
Prints a textual representation of this predicate with an indentation of Depth.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:602
This class uses information about analyze scalars to rewrite expressions in canonical form...
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:211
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
amdgpu Simplify well known AMD library false Value Value * Arg
Analysis pass that exposes the ScalarEvolution for a function.
bool isKnownNegative(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Returns true if the given value is known be negative (i.e.
unsigned getComplexity() const override
We estimate the complexity of a union predicate as the size number of predicates in the union...
static ExitLimitQuery getTombstoneKey()
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:121
The SCEV does not dominate the block.
FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID, which can be a useful to store node id data rather than using plain FoldingSetNodeIDs, since the 32-element SmallVector is often much larger than necessary, and the possibility of heap allocation means it requires a non-trivial destructor call.
Definition: FoldingSet.h:278
MCExpr const & getExpr(MCExpr const &Expr)
Node - This class is used to maintain the singly linked bucket list in a folding set.
Definition: FoldingSet.h:136
This class represents an analyzed expression in the program.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:62
const SCEV * getMulExpr(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy)
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
BlockDisposition
An enum describing the relationship between a SCEV and a basic block.
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 ...
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2032
virtual unsigned getComplexity() const
Returns the estimated complexity of this predicate.
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h:129
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:559
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
const unsigned Kind
const SmallVectorImpl< const SCEVPredicate * > & getPredicates() const
Multiway switch.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This class represents a composition of other SCEV predicates, and is the class that most clients will...
bool isOne() const
Return true if the expression is a constant one.
const SCEV * getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:565
LLVM Value Representation.
Definition: Value.h:73
A vector that has set insertion semantics.
Definition: SetVector.h:41
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:81
bool isKnownPositive(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Returns true if the given value is known be positive (i.e.
DefaultFoldingSetTrait - This class provides default implementations for FoldingSetTrait implementati...
Definition: FoldingSet.h:221
SCEVPredicateKind Kind
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
static unsigned getHashValue(ExitLimitQuery Val)
bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Return true if the given value is known to be non-zero when defined.
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:389
A container for analyses that lazily runs them and caches their results.
static Optional< bool > isImpliedCondOperands(CmpInst::Predicate Pred, const Value *ALHS, const Value *ARHS, const Value *BLHS, const Value *BRHS, const DataLayout &DL, unsigned Depth)
Return true if "icmp Pred BLHS BRHS" is true whenever "icmp Pred ALHS ARHS" is true.
This header defines various interfaces for pass management in LLVM.
const SCEV * getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
This class represents an assumption made on an AddRec expression.
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
This class represents an assumption that two SCEV expressions are equal, and this can be checked at r...
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
IncrementWrapFlags getFlags() const
Returns the set assumed no overflow flags.