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