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