1 //===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // The ScalarEvolution class is an LLVM pass which can be used to analyze and
11 // categorize scalar expressions in loops. It specializes in recognizing
12 // general induction variables, representing them with the abstract and opaque
13 // SCEV class. Given this analysis, trip counts of loops and other important
14 // properties can be obtained.
16 // This analysis is primarily useful for induction variable substitution and
17 // strength reduction.
19 //===----------------------------------------------------------------------===//
21 #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
22 #define LLVM_ANALYSIS_SCALAREVOLUTION_H
24 #include "llvm/ADT/APInt.h"
25 #include "llvm/ADT/ArrayRef.h"
26 #include "llvm/ADT/DenseMap.h"
27 #include "llvm/ADT/DenseMapInfo.h"
28 #include "llvm/ADT/FoldingSet.h"
29 #include "llvm/ADT/Hashing.h"
30 #include "llvm/ADT/Optional.h"
31 #include "llvm/ADT/PointerIntPair.h"
32 #include "llvm/ADT/SetVector.h"
33 #include "llvm/ADT/SmallPtrSet.h"
34 #include "llvm/ADT/SmallVector.h"
35 #include "llvm/Analysis/LoopInfo.h"
36 #include "llvm/IR/ConstantRange.h"
37 #include "llvm/IR/Function.h"
38 #include "llvm/IR/InstrTypes.h"
39 #include "llvm/IR/Instructions.h"
40 #include "llvm/IR/Operator.h"
41 #include "llvm/IR/PassManager.h"
42 #include "llvm/IR/ValueHandle.h"
43 #include "llvm/IR/ValueMap.h"
44 #include "llvm/Pass.h"
45 #include "llvm/Support/Allocator.h"
46 #include "llvm/Support/Casting.h"
47 #include "llvm/Support/Compiler.h"
56 class AssumptionCache;
66 class ScalarEvolution;
70 class TargetLibraryInfo;
74 /// This class represents an analyzed expression in the program. These are
75 /// opaque objects that the client is not allowed to do much with directly.
77 class SCEV : public FoldingSetNode {
78 friend struct FoldingSetTrait<SCEV>;
80 /// A reference to an Interned FoldingSetNodeID for this node. The
81 /// ScalarEvolution's BumpPtrAllocator holds the data.
82 FoldingSetNodeIDRef FastID;
84 // The SCEV baseclass this node corresponds to
85 const unsigned short SCEVType;
88 /// This field is initialized to zero and may be used in subclasses to store
89 /// miscellaneous information.
90 unsigned short SubclassData = 0;
93 /// NoWrapFlags are bitfield indices into SubclassData.
95 /// Add and Mul expressions may have no-unsigned-wrap <NUW> or
96 /// no-signed-wrap <NSW> properties, which are derived from the IR
97 /// operator. NSW is a misnomer that we use to mean no signed overflow or
100 /// AddRec expressions may have a no-self-wraparound <NW> property if, in
101 /// the integer domain, abs(step) * max-iteration(loop) <=
102 /// unsigned-max(bitwidth). This means that the recurrence will never reach
103 /// its start value if the step is non-zero. Computing the same value on
104 /// each iteration is not considered wrapping, and recurrences with step = 0
105 /// are trivially <NW>. <NW> is independent of the sign of step and the
106 /// value the add recurrence starts with.
108 /// Note that NUW and NSW are also valid properties of a recurrence, and
109 /// either implies NW. For convenience, NW will be set for a recurrence
110 /// whenever either NUW or NSW are set.
112 FlagAnyWrap = 0, // No guarantee.
113 FlagNW = (1 << 0), // No self-wrap.
114 FlagNUW = (1 << 1), // No unsigned wrap.
115 FlagNSW = (1 << 2), // No signed wrap.
116 NoWrapMask = (1 << 3) - 1
119 explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy)
120 : FastID(ID), SCEVType(SCEVTy) {}
121 SCEV(const SCEV &) = delete;
122 SCEV &operator=(const SCEV &) = delete;
124 unsigned getSCEVType() const { return SCEVType; }
126 /// Return the LLVM type of this SCEV expression.
127 Type *getType() const;
129 /// Return true if the expression is a constant zero.
132 /// Return true if the expression is a constant one.
135 /// Return true if the expression is a constant all-ones value.
136 bool isAllOnesValue() const;
138 /// Return true if the specified scev is negated, but not a constant.
139 bool isNonConstantNegative() const;
141 /// Print out the internal representation of this scalar to the specified
142 /// stream. This should really only be used for debugging purposes.
143 void print(raw_ostream &OS) const;
145 /// This method is used for debugging.
149 // Specialize FoldingSetTrait for SCEV to avoid needing to compute
150 // temporary FoldingSetNodeID values.
151 template <> struct FoldingSetTrait<SCEV> : DefaultFoldingSetTrait<SCEV> {
152 static void Profile(const SCEV &X, FoldingSetNodeID &ID) { ID = X.FastID; }
154 static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, unsigned IDHash,
155 FoldingSetNodeID &TempID) {
156 return ID == X.FastID;
159 static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) {
160 return X.FastID.ComputeHash();
164 inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) {
169 /// An object of this class is returned by queries that could not be answered.
170 /// For example, if you ask for the number of iterations of a linked-list
171 /// traversal loop, you will get one of these. None of the standard SCEV
172 /// operations are valid on this class, it is just a marker.
173 struct SCEVCouldNotCompute : public SCEV {
174 SCEVCouldNotCompute();
176 /// Methods for support type inquiry through isa, cast, and dyn_cast:
177 static bool classof(const SCEV *S);
180 /// This class represents an assumption made using SCEV expressions which can
181 /// be checked at run-time.
182 class SCEVPredicate : public FoldingSetNode {
183 friend struct FoldingSetTrait<SCEVPredicate>;
185 /// A reference to an Interned FoldingSetNodeID for this node. The
186 /// ScalarEvolution's BumpPtrAllocator holds the data.
187 FoldingSetNodeIDRef FastID;
190 enum SCEVPredicateKind { P_Union, P_Equal, P_Wrap };
193 SCEVPredicateKind Kind;
194 ~SCEVPredicate() = default;
195 SCEVPredicate(const SCEVPredicate &) = default;
196 SCEVPredicate &operator=(const SCEVPredicate &) = default;
199 SCEVPredicate(const FoldingSetNodeIDRef ID, SCEVPredicateKind Kind);
201 SCEVPredicateKind getKind() const { return Kind; }
203 /// Returns the estimated complexity of this predicate. This is roughly
204 /// measured in the number of run-time checks required.
205 virtual unsigned getComplexity() const { return 1; }
207 /// Returns true if the predicate is always true. This means that no
208 /// assumptions were made and nothing needs to be checked at run-time.
209 virtual bool isAlwaysTrue() const = 0;
211 /// Returns true if this predicate implies \p N.
212 virtual bool implies(const SCEVPredicate *N) const = 0;
214 /// Prints a textual representation of this predicate with an indentation of
216 virtual void print(raw_ostream &OS, unsigned Depth = 0) const = 0;
218 /// Returns the SCEV to which this predicate applies, or nullptr if this is
219 /// a SCEVUnionPredicate.
220 virtual const SCEV *getExpr() const = 0;
223 inline raw_ostream &operator<<(raw_ostream &OS, const SCEVPredicate &P) {
228 // Specialize FoldingSetTrait for SCEVPredicate to avoid needing to compute
229 // temporary FoldingSetNodeID values.
231 struct FoldingSetTrait<SCEVPredicate> : DefaultFoldingSetTrait<SCEVPredicate> {
232 static void Profile(const SCEVPredicate &X, FoldingSetNodeID &ID) {
236 static bool Equals(const SCEVPredicate &X, const FoldingSetNodeID &ID,
237 unsigned IDHash, FoldingSetNodeID &TempID) {
238 return ID == X.FastID;
241 static unsigned ComputeHash(const SCEVPredicate &X,
242 FoldingSetNodeID &TempID) {
243 return X.FastID.ComputeHash();
247 /// This class represents an assumption that two SCEV expressions are equal,
248 /// and this can be checked at run-time.
249 class SCEVEqualPredicate final : public SCEVPredicate {
250 /// We assume that LHS == RHS.
255 SCEVEqualPredicate(const FoldingSetNodeIDRef ID, const SCEV *LHS,
258 /// Implementation of the SCEVPredicate interface
259 bool implies(const SCEVPredicate *N) const override;
260 void print(raw_ostream &OS, unsigned Depth = 0) const override;
261 bool isAlwaysTrue() const override;
262 const SCEV *getExpr() const override;
264 /// Returns the left hand side of the equality.
265 const SCEV *getLHS() const { return LHS; }
267 /// Returns the right hand side of the equality.
268 const SCEV *getRHS() const { return RHS; }
270 /// Methods for support type inquiry through isa, cast, and dyn_cast:
271 static bool classof(const SCEVPredicate *P) {
272 return P->getKind() == P_Equal;
276 /// This class represents an assumption made on an AddRec expression. Given an
277 /// affine AddRec expression {a,+,b}, we assume that it has the nssw or nusw
278 /// flags (defined below) in the first X iterations of the loop, where X is a
279 /// SCEV expression returned by getPredicatedBackedgeTakenCount).
281 /// Note that this does not imply that X is equal to the backedge taken
282 /// count. This means that if we have a nusw predicate for i32 {0,+,1} with a
283 /// predicated backedge taken count of X, we only guarantee that {0,+,1} has
284 /// nusw in the first X iterations. {0,+,1} may still wrap in the loop if we
285 /// have more than X iterations.
286 class SCEVWrapPredicate final : public SCEVPredicate {
288 /// Similar to SCEV::NoWrapFlags, but with slightly different semantics
289 /// for FlagNUSW. The increment is considered to be signed, and a + b
290 /// (where b is the increment) is considered to wrap if:
291 /// zext(a + b) != zext(a) + sext(b)
293 /// If Signed is a function that takes an n-bit tuple and maps to the
294 /// integer domain as the tuples value interpreted as twos complement,
295 /// and Unsigned a function that takes an n-bit tuple and maps to the
296 /// integer domain as as the base two value of input tuple, then a + b
297 /// has IncrementNUSW iff:
299 /// 0 <= Unsigned(a) + Signed(b) < 2^n
301 /// The IncrementNSSW flag has identical semantics with SCEV::FlagNSW.
303 /// Note that the IncrementNUSW flag is not commutative: if base + inc
304 /// has IncrementNUSW, then inc + base doesn't neccessarily have this
305 /// property. The reason for this is that this is used for sign/zero
306 /// extending affine AddRec SCEV expressions when a SCEVWrapPredicate is
307 /// assumed. A {base,+,inc} expression is already non-commutative with
308 /// regards to base and inc, since it is interpreted as:
309 /// (((base + inc) + inc) + inc) ...
310 enum IncrementWrapFlags {
311 IncrementAnyWrap = 0, // No guarantee.
312 IncrementNUSW = (1 << 0), // No unsigned with signed increment wrap.
313 IncrementNSSW = (1 << 1), // No signed with signed increment wrap
314 // (equivalent with SCEV::NSW)
315 IncrementNoWrapMask = (1 << 2) - 1
318 /// Convenient IncrementWrapFlags manipulation methods.
319 LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags
320 clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags,
321 SCEVWrapPredicate::IncrementWrapFlags OffFlags) {
322 assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
323 assert((OffFlags & IncrementNoWrapMask) == OffFlags &&
324 "Invalid flags value!");
325 return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & ~OffFlags);
328 LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags
329 maskFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, int Mask) {
330 assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
331 assert((Mask & IncrementNoWrapMask) == Mask && "Invalid mask value!");
333 return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & Mask);
336 LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags
337 setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags,
338 SCEVWrapPredicate::IncrementWrapFlags OnFlags) {
339 assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
340 assert((OnFlags & IncrementNoWrapMask) == OnFlags &&
341 "Invalid flags value!");
343 return (SCEVWrapPredicate::IncrementWrapFlags)(Flags | OnFlags);
346 /// Returns the set of SCEVWrapPredicate no wrap flags implied by a
348 LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags
349 getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE);
352 const SCEVAddRecExpr *AR;
353 IncrementWrapFlags Flags;
356 explicit SCEVWrapPredicate(const FoldingSetNodeIDRef ID,
357 const SCEVAddRecExpr *AR,
358 IncrementWrapFlags Flags);
360 /// Returns the set assumed no overflow flags.
361 IncrementWrapFlags getFlags() const { return Flags; }
363 /// Implementation of the SCEVPredicate interface
364 const SCEV *getExpr() const override;
365 bool implies(const SCEVPredicate *N) const override;
366 void print(raw_ostream &OS, unsigned Depth = 0) const override;
367 bool isAlwaysTrue() const override;
369 /// Methods for support type inquiry through isa, cast, and dyn_cast:
370 static bool classof(const SCEVPredicate *P) {
371 return P->getKind() == P_Wrap;
375 /// This class represents a composition of other SCEV predicates, and is the
376 /// class that most clients will interact with. This is equivalent to a
377 /// logical "AND" of all the predicates in the union.
379 /// NB! Unlike other SCEVPredicate sub-classes this class does not live in the
380 /// ScalarEvolution::Preds folding set. This is why the \c add function is sound.
381 class SCEVUnionPredicate final : public SCEVPredicate {
384 DenseMap<const SCEV *, SmallVector<const SCEVPredicate *, 4>>;
386 /// Vector with references to all predicates in this union.
387 SmallVector<const SCEVPredicate *, 16> Preds;
389 /// Maps SCEVs to predicates for quick look-ups.
390 PredicateMap SCEVToPreds;
393 SCEVUnionPredicate();
395 const SmallVectorImpl<const SCEVPredicate *> &getPredicates() const {
399 /// Adds a predicate to this union.
400 void add(const SCEVPredicate *N);
402 /// Returns a reference to a vector containing all predicates which apply to
404 ArrayRef<const SCEVPredicate *> getPredicatesForExpr(const SCEV *Expr);
406 /// Implementation of the SCEVPredicate interface
407 bool isAlwaysTrue() const override;
408 bool implies(const SCEVPredicate *N) const override;
409 void print(raw_ostream &OS, unsigned Depth) const override;
410 const SCEV *getExpr() const override;
412 /// We estimate the complexity of a union predicate as the size number of
413 /// predicates in the union.
414 unsigned getComplexity() const override { return Preds.size(); }
416 /// Methods for support type inquiry through isa, cast, and dyn_cast:
417 static bool classof(const SCEVPredicate *P) {
418 return P->getKind() == P_Union;
422 struct ExitLimitQuery {
423 ExitLimitQuery(const Loop *L, BasicBlock *ExitingBlock, bool AllowPredicates)
424 : L(L), ExitingBlock(ExitingBlock), AllowPredicates(AllowPredicates) {}
427 BasicBlock *ExitingBlock;
428 bool AllowPredicates;
431 template <> struct DenseMapInfo<ExitLimitQuery> {
432 static inline ExitLimitQuery getEmptyKey() {
433 return ExitLimitQuery(nullptr, nullptr, true);
436 static inline ExitLimitQuery getTombstoneKey() {
437 return ExitLimitQuery(nullptr, nullptr, false);
440 static unsigned getHashValue(ExitLimitQuery Val) {
441 return hash_combine(hash_combine(Val.L, Val.ExitingBlock),
442 Val.AllowPredicates);
445 static bool isEqual(ExitLimitQuery LHS, ExitLimitQuery RHS) {
446 return LHS.L == RHS.L && LHS.ExitingBlock == RHS.ExitingBlock &&
447 LHS.AllowPredicates == RHS.AllowPredicates;
451 /// The main scalar evolution driver. Because client code (intentionally)
452 /// can't do much with the SCEV objects directly, they must ask this class
454 class ScalarEvolution {
456 /// An enum describing the relationship between a SCEV and a loop.
457 enum LoopDisposition {
458 LoopVariant, ///< The SCEV is loop-variant (unknown).
459 LoopInvariant, ///< The SCEV is loop-invariant.
460 LoopComputable ///< The SCEV varies predictably with the loop.
463 /// An enum describing the relationship between a SCEV and a basic block.
464 enum BlockDisposition {
465 DoesNotDominateBlock, ///< The SCEV does not dominate the block.
466 DominatesBlock, ///< The SCEV dominates the block.
467 ProperlyDominatesBlock ///< The SCEV properly dominates the block.
470 /// Convenient NoWrapFlags manipulation that hides enum casts and is
471 /// visible in the ScalarEvolution name space.
472 LLVM_NODISCARD static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags,
474 return (SCEV::NoWrapFlags)(Flags & Mask);
476 LLVM_NODISCARD static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags,
477 SCEV::NoWrapFlags OnFlags) {
478 return (SCEV::NoWrapFlags)(Flags | OnFlags);
480 LLVM_NODISCARD static SCEV::NoWrapFlags
481 clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags) {
482 return (SCEV::NoWrapFlags)(Flags & ~OffFlags);
485 ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC,
486 DominatorTree &DT, LoopInfo &LI);
487 ScalarEvolution(ScalarEvolution &&Arg);
490 LLVMContext &getContext() const { return F.getContext(); }
492 /// Test if values of the given type are analyzable within the SCEV
493 /// framework. This primarily includes integer types, and it can optionally
494 /// include pointer types if the ScalarEvolution class has access to
495 /// target-specific information.
496 bool isSCEVable(Type *Ty) const;
498 /// Return the size in bits of the specified type, for which isSCEVable must
500 uint64_t getTypeSizeInBits(Type *Ty) const;
502 /// Return a type with the same bitwidth as the given type and which
503 /// represents how SCEV will treat the given type, for which isSCEVable must
504 /// return true. For pointer types, this is the pointer-sized integer type.
505 Type *getEffectiveSCEVType(Type *Ty) const;
507 // Returns a wider type among {Ty1, Ty2}.
508 Type *getWiderType(Type *Ty1, Type *Ty2) const;
510 /// Return true if the SCEV is a scAddRecExpr or it contains
511 /// scAddRecExpr. The result will be cached in HasRecMap.
512 bool containsAddRecurrence(const SCEV *S);
514 /// Erase Value from ValueExprMap and ExprValueMap.
515 void eraseValueFromMap(Value *V);
517 /// Return a SCEV expression for the full generality of the specified
519 const SCEV *getSCEV(Value *V);
521 const SCEV *getConstant(ConstantInt *V);
522 const SCEV *getConstant(const APInt &Val);
523 const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false);
524 const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty);
525 const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
526 const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
527 const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty);
528 const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
529 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
531 const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS,
532 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
533 unsigned Depth = 0) {
534 SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
535 return getAddExpr(Ops, Flags, Depth);
537 const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
538 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
539 unsigned Depth = 0) {
540 SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
541 return getAddExpr(Ops, Flags, Depth);
543 const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
544 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
546 const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS,
547 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
548 unsigned Depth = 0) {
549 SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
550 return getMulExpr(Ops, Flags, Depth);
552 const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
553 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
554 unsigned Depth = 0) {
555 SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
556 return getMulExpr(Ops, Flags, Depth);
558 const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS);
559 const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS);
560 const SCEV *getURemExpr(const SCEV *LHS, const SCEV *RHS);
561 const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L,
562 SCEV::NoWrapFlags Flags);
563 const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
564 const Loop *L, SCEV::NoWrapFlags Flags);
565 const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands,
566 const Loop *L, SCEV::NoWrapFlags Flags) {
567 SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end());
568 return getAddRecExpr(NewOp, L, Flags);
571 /// Checks if \p SymbolicPHI can be rewritten as an AddRecExpr under some
572 /// Predicates. If successful return these <AddRecExpr, Predicates>;
573 /// The function is intended to be called from PSCEV (the caller will decide
574 /// whether to actually add the predicates and carry out the rewrites).
575 Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
576 createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI);
578 /// Returns an expression for a GEP
580 /// \p GEP The GEP. The indices contained in the GEP itself are ignored,
581 /// instead we use IndexExprs.
582 /// \p IndexExprs The expressions for the indices.
583 const SCEV *getGEPExpr(GEPOperator *GEP,
584 const SmallVectorImpl<const SCEV *> &IndexExprs);
585 const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS);
586 const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
587 const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS);
588 const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
589 const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS);
590 const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS);
591 const SCEV *getUnknown(Value *V);
592 const SCEV *getCouldNotCompute();
594 /// Return a SCEV for the constant 0 of a specific type.
595 const SCEV *getZero(Type *Ty) { return getConstant(Ty, 0); }
597 /// Return a SCEV for the constant 1 of a specific type.
598 const SCEV *getOne(Type *Ty) { return getConstant(Ty, 1); }
600 /// Return an expression for sizeof AllocTy that is type IntTy
601 const SCEV *getSizeOfExpr(Type *IntTy, Type *AllocTy);
603 /// Return an expression for offsetof on the given field with type IntTy
604 const SCEV *getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo);
606 /// Return the SCEV object corresponding to -V.
607 const SCEV *getNegativeSCEV(const SCEV *V,
608 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap);
610 /// Return the SCEV object corresponding to ~V.
611 const SCEV *getNotSCEV(const SCEV *V);
613 /// Return LHS-RHS. Minus is represented in SCEV as A+B*-1.
614 const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
615 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
618 /// Return a SCEV corresponding to a conversion of the input value to the
619 /// specified type. If the type must be extended, it is zero extended.
620 const SCEV *getTruncateOrZeroExtend(const SCEV *V, Type *Ty);
622 /// Return a SCEV corresponding to a conversion of the input value to the
623 /// specified type. If the type must be extended, it is sign extended.
624 const SCEV *getTruncateOrSignExtend(const SCEV *V, Type *Ty);
626 /// Return a SCEV corresponding to a conversion of the input value to the
627 /// specified type. If the type must be extended, it is zero extended. The
628 /// conversion must not be narrowing.
629 const SCEV *getNoopOrZeroExtend(const SCEV *V, Type *Ty);
631 /// Return a SCEV corresponding to a conversion of the input value to the
632 /// specified type. If the type must be extended, it is sign extended. The
633 /// conversion must not be narrowing.
634 const SCEV *getNoopOrSignExtend(const SCEV *V, Type *Ty);
636 /// Return a SCEV corresponding to a conversion of the input value to the
637 /// specified type. If the type must be extended, it is extended with
638 /// unspecified bits. The conversion must not be narrowing.
639 const SCEV *getNoopOrAnyExtend(const SCEV *V, Type *Ty);
641 /// Return a SCEV corresponding to a conversion of the input value to the
642 /// specified type. The conversion must not be widening.
643 const SCEV *getTruncateOrNoop(const SCEV *V, Type *Ty);
645 /// Promote the operands to the wider of the types using zero-extension, and
646 /// then perform a umax operation with them.
647 const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS);
649 /// Promote the operands to the wider of the types using zero-extension, and
650 /// then perform a umin operation with them.
651 const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS);
653 /// Transitively follow the chain of pointer-type operands until reaching a
654 /// SCEV that does not have a single pointer operand. This returns a
655 /// SCEVUnknown pointer for well-formed pointer-type expressions, but corner
657 const SCEV *getPointerBase(const SCEV *V);
659 /// Return a SCEV expression for the specified value at the specified scope
660 /// in the program. The L value specifies a loop nest to evaluate the
661 /// expression at, where null is the top-level or a specified loop is
662 /// immediately inside of the loop.
664 /// This method can be used to compute the exit value for a variable defined
665 /// in a loop by querying what the value will hold in the parent loop.
667 /// In the case that a relevant loop exit value cannot be computed, the
668 /// original value V is returned.
669 const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L);
671 /// This is a convenience function which does getSCEVAtScope(getSCEV(V), L).
672 const SCEV *getSCEVAtScope(Value *V, const Loop *L);
674 /// Test whether entry to the loop is protected by a conditional between LHS
675 /// and RHS. This is used to help avoid max expressions in loop trip
676 /// counts, and to eliminate casts.
677 bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
678 const SCEV *LHS, const SCEV *RHS);
680 /// Test whether the backedge of the loop is protected by a conditional
681 /// between LHS and RHS. This is used to to eliminate casts.
682 bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
683 const SCEV *LHS, const SCEV *RHS);
685 /// Returns the maximum trip count of the loop if it is a single-exit
686 /// loop and we can compute a small maximum for that loop.
688 /// Implemented in terms of the \c getSmallConstantTripCount overload with
689 /// the single exiting block passed to it. See that routine for details.
690 unsigned getSmallConstantTripCount(const Loop *L);
692 /// Returns the maximum trip count of this loop as a normal unsigned
693 /// value. Returns 0 if the trip count is unknown or not constant. This
694 /// "trip count" assumes that control exits via ExitingBlock. More
695 /// precisely, it is the number of times that control may reach ExitingBlock
696 /// before taking the branch. For loops with multiple exits, it may not be
697 /// the number times that the loop header executes if the loop exits
698 /// prematurely via another branch.
699 unsigned getSmallConstantTripCount(const Loop *L, BasicBlock *ExitingBlock);
701 /// Returns the upper bound of the loop trip count as a normal unsigned
703 /// Returns 0 if the trip count is unknown or not constant.
704 unsigned getSmallConstantMaxTripCount(const Loop *L);
706 /// Returns the largest constant divisor of the trip count of the
707 /// loop if it is a single-exit loop and we can compute a small maximum for
710 /// Implemented in terms of the \c getSmallConstantTripMultiple overload with
711 /// the single exiting block passed to it. See that routine for details.
712 unsigned getSmallConstantTripMultiple(const Loop *L);
714 /// Returns the largest constant divisor of the trip count of this loop as a
715 /// normal unsigned value, if possible. This means that the actual trip
716 /// count is always a multiple of the returned value (don't forget the trip
717 /// count could very well be zero as well!). As explained in the comments
718 /// for getSmallConstantTripCount, this assumes that control exits the loop
719 /// via ExitingBlock.
720 unsigned getSmallConstantTripMultiple(const Loop *L,
721 BasicBlock *ExitingBlock);
723 /// Get the expression for the number of loop iterations for which this loop
724 /// is guaranteed not to exit via ExitingBlock. Otherwise return
725 /// SCEVCouldNotCompute.
726 const SCEV *getExitCount(const Loop *L, BasicBlock *ExitingBlock);
728 /// If the specified loop has a predictable backedge-taken count, return it,
729 /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count is
730 /// the number of times the loop header will be branched to from within the
731 /// loop, assuming there are no abnormal exists like exception throws. This is
732 /// one less than the trip count of the loop, since it doesn't count the first
733 /// iteration, when the header is branched to from outside the loop.
735 /// Note that it is not valid to call this method on a loop without a
736 /// loop-invariant backedge-taken count (see
737 /// hasLoopInvariantBackedgeTakenCount).
738 const SCEV *getBackedgeTakenCount(const Loop *L);
740 /// Similar to getBackedgeTakenCount, except it will add a set of
741 /// SCEV predicates to Predicates that are required to be true in order for
742 /// the answer to be correct. Predicates can be checked with run-time
743 /// checks and can be used to perform loop versioning.
744 const SCEV *getPredicatedBackedgeTakenCount(const Loop *L,
745 SCEVUnionPredicate &Predicates);
747 /// When successful, this returns a SCEVConstant that is greater than or equal
748 /// to (i.e. a "conservative over-approximation") of the value returend by
749 /// getBackedgeTakenCount. If such a value cannot be computed, it returns the
750 /// SCEVCouldNotCompute object.
751 const SCEV *getMaxBackedgeTakenCount(const Loop *L);
753 /// Return true if the backedge taken count is either the value returned by
754 /// getMaxBackedgeTakenCount or zero.
755 bool isBackedgeTakenCountMaxOrZero(const Loop *L);
757 /// Return true if the specified loop has an analyzable loop-invariant
758 /// backedge-taken count.
759 bool hasLoopInvariantBackedgeTakenCount(const Loop *L);
761 /// This method should be called by the client when it has changed a loop in
762 /// a way that may effect ScalarEvolution's ability to compute a trip count,
763 /// or if the loop is deleted. This call is potentially expensive for large
765 void forgetLoop(const Loop *L);
767 /// This method should be called by the client when it has changed a value
768 /// in a way that may effect its value, or which may disconnect it from a
769 /// def-use chain linking it to a loop.
770 void forgetValue(Value *V);
772 /// Called when the client has changed the disposition of values in
775 /// We don't have a way to invalidate per-loop dispositions. Clear and
776 /// recompute is simpler.
777 void forgetLoopDispositions(const Loop *L) { LoopDispositions.clear(); }
779 /// Determine the minimum number of zero bits that S is guaranteed to end in
780 /// (at every loop iteration). It is, at the same time, the minimum number
781 /// of times S is divisible by 2. For example, given {4,+,8} it returns 2.
782 /// If S is guaranteed to be 0, it returns the bitwidth of S.
783 uint32_t GetMinTrailingZeros(const SCEV *S);
785 /// Determine the unsigned range for a particular SCEV.
786 /// NOTE: This returns a copy of the reference returned by getRangeRef.
787 ConstantRange getUnsignedRange(const SCEV *S) {
788 return getRangeRef(S, HINT_RANGE_UNSIGNED);
791 /// Determine the min of the unsigned range for a particular SCEV.
792 APInt getUnsignedRangeMin(const SCEV *S) {
793 return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMin();
796 /// Determine the max of the unsigned range for a particular SCEV.
797 APInt getUnsignedRangeMax(const SCEV *S) {
798 return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMax();
801 /// Determine the signed range for a particular SCEV.
802 /// NOTE: This returns a copy of the reference returned by getRangeRef.
803 ConstantRange getSignedRange(const SCEV *S) {
804 return getRangeRef(S, HINT_RANGE_SIGNED);
807 /// Determine the min of the signed range for a particular SCEV.
808 APInt getSignedRangeMin(const SCEV *S) {
809 return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMin();
812 /// Determine the max of the signed range for a particular SCEV.
813 APInt getSignedRangeMax(const SCEV *S) {
814 return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMax();
817 /// Test if the given expression is known to be negative.
818 bool isKnownNegative(const SCEV *S);
820 /// Test if the given expression is known to be positive.
821 bool isKnownPositive(const SCEV *S);
823 /// Test if the given expression is known to be non-negative.
824 bool isKnownNonNegative(const SCEV *S);
826 /// Test if the given expression is known to be non-positive.
827 bool isKnownNonPositive(const SCEV *S);
829 /// Test if the given expression is known to be non-zero.
830 bool isKnownNonZero(const SCEV *S);
832 /// Test if the given expression is known to satisfy the condition described
833 /// by Pred, LHS, and RHS.
834 bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS,
837 /// Return true if, for all loop invariant X, the predicate "LHS `Pred` X"
838 /// is monotonically increasing or decreasing. In the former case set
839 /// `Increasing` to true and in the latter case set `Increasing` to false.
841 /// A predicate is said to be monotonically increasing if may go from being
842 /// false to being true as the loop iterates, but never the other way
843 /// around. A predicate is said to be monotonically decreasing if may go
844 /// from being true to being false as the loop iterates, but never the other
846 bool isMonotonicPredicate(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred,
849 /// Return true if the result of the predicate LHS `Pred` RHS is loop
850 /// invariant with respect to L. Set InvariantPred, InvariantLHS and
851 /// InvariantLHS so that InvariantLHS `InvariantPred` InvariantRHS is the
852 /// loop invariant form of LHS `Pred` RHS.
853 bool isLoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS,
854 const SCEV *RHS, const Loop *L,
855 ICmpInst::Predicate &InvariantPred,
856 const SCEV *&InvariantLHS,
857 const SCEV *&InvariantRHS);
859 /// Simplify LHS and RHS in a comparison with predicate Pred. Return true
860 /// iff any changes were made. If the operands are provably equal or
861 /// unequal, LHS and RHS are set to the same value and Pred is set to either
862 /// ICMP_EQ or ICMP_NE.
863 bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS,
864 const SCEV *&RHS, unsigned Depth = 0);
866 /// Return the "disposition" of the given SCEV with respect to the given
868 LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L);
870 /// Return true if the value of the given SCEV is unchanging in the
872 bool isLoopInvariant(const SCEV *S, const Loop *L);
874 /// Determine if the SCEV can be evaluated at loop's entry. It is true if it
875 /// doesn't depend on a SCEVUnknown of an instruction which is dominated by
876 /// the header of loop L.
877 bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L);
879 /// Return true if the given SCEV changes value in a known way in the
880 /// specified loop. This property being true implies that the value is
881 /// variant in the loop AND that we can emit an expression to compute the
882 /// value of the expression at any particular loop iteration.
883 bool hasComputableLoopEvolution(const SCEV *S, const Loop *L);
885 /// Return the "disposition" of the given SCEV with respect to the given
887 BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB);
889 /// Return true if elements that makes up the given SCEV dominate the
890 /// specified basic block.
891 bool dominates(const SCEV *S, const BasicBlock *BB);
893 /// Return true if elements that makes up the given SCEV properly dominate
894 /// the specified basic block.
895 bool properlyDominates(const SCEV *S, const BasicBlock *BB);
897 /// Test whether the given SCEV has Op as a direct or indirect operand.
898 bool hasOperand(const SCEV *S, const SCEV *Op) const;
900 /// Return the size of an element read or written by Inst.
901 const SCEV *getElementSize(Instruction *Inst);
903 /// Compute the array dimensions Sizes from the set of Terms extracted from
904 /// the memory access function of this SCEVAddRecExpr (second step of
905 /// delinearization).
906 void findArrayDimensions(SmallVectorImpl<const SCEV *> &Terms,
907 SmallVectorImpl<const SCEV *> &Sizes,
908 const SCEV *ElementSize);
910 void print(raw_ostream &OS) const;
912 bool invalidate(Function &F, const PreservedAnalyses &PA,
913 FunctionAnalysisManager::Invalidator &Inv);
915 /// Collect parametric terms occurring in step expressions (first step of
916 /// delinearization).
917 void collectParametricTerms(const SCEV *Expr,
918 SmallVectorImpl<const SCEV *> &Terms);
920 /// Return in Subscripts the access functions for each dimension in Sizes
921 /// (third step of delinearization).
922 void computeAccessFunctions(const SCEV *Expr,
923 SmallVectorImpl<const SCEV *> &Subscripts,
924 SmallVectorImpl<const SCEV *> &Sizes);
926 /// Split this SCEVAddRecExpr into two vectors of SCEVs representing the
927 /// subscripts and sizes of an array access.
929 /// The delinearization is a 3 step process: the first two steps compute the
930 /// sizes of each subscript and the third step computes the access functions
931 /// for the delinearized array:
933 /// 1. Find the terms in the step functions
934 /// 2. Compute the array size
935 /// 3. Compute the access function: divide the SCEV by the array size
936 /// starting with the innermost dimensions found in step 2. The Quotient
937 /// is the SCEV to be divided in the next step of the recursion. The
938 /// Remainder is the subscript of the innermost dimension. Loop over all
939 /// array dimensions computed in step 2.
941 /// To compute a uniform array size for several memory accesses to the same
942 /// object, one can collect in step 1 all the step terms for all the memory
943 /// accesses, and compute in step 2 a unique array shape. This guarantees
944 /// that the array shape will be the same across all memory accesses.
946 /// FIXME: We could derive the result of steps 1 and 2 from a description of
947 /// the array shape given in metadata.
958 /// The initial SCEV:
960 /// A[{{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k]
962 /// 1. Find the different terms in the step functions:
963 /// -> [2*m, 5, n*m, n*m]
965 /// 2. Compute the array size: sort and unique them
967 /// find the GCD of all the terms = 1
968 /// divide by the GCD and erase constant terms
971 /// divide by GCD -> [n, 2]
972 /// remove constant terms
974 /// size of the array is A[unknown][n][m]
976 /// 3. Compute the access function
977 /// a. Divide {{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k by the innermost size m
978 /// Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k
979 /// Remainder: {{{0,+,5}_i, +, 0}_j, +, 0}_k
980 /// The remainder is the subscript of the innermost array dimension: [5i].
982 /// b. Divide Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k by next outer size n
983 /// Quotient: {{{0,+,0}_i, +, 1}_j, +, 1}_k
984 /// Remainder: {{{0,+,2}_i, +, 0}_j, +, 0}_k
985 /// The Remainder is the subscript of the next array dimension: [2i].
987 /// The subscript of the outermost dimension is the Quotient: [j+k].
989 /// Overall, we have: A[][n][m], and the access function: A[j+k][2i][5i].
990 void delinearize(const SCEV *Expr, SmallVectorImpl<const SCEV *> &Subscripts,
991 SmallVectorImpl<const SCEV *> &Sizes,
992 const SCEV *ElementSize);
994 /// Return the DataLayout associated with the module this SCEV instance is
996 const DataLayout &getDataLayout() const {
997 return F.getParent()->getDataLayout();
1000 const SCEVPredicate *getEqualPredicate(const SCEV *LHS, const SCEV *RHS);
1002 const SCEVPredicate *
1003 getWrapPredicate(const SCEVAddRecExpr *AR,
1004 SCEVWrapPredicate::IncrementWrapFlags AddedFlags);
1006 /// Re-writes the SCEV according to the Predicates in \p A.
1007 const SCEV *rewriteUsingPredicate(const SCEV *S, const Loop *L,
1008 SCEVUnionPredicate &A);
1009 /// Tries to convert the \p S expression to an AddRec expression,
1010 /// adding additional predicates to \p Preds as required.
1011 const SCEVAddRecExpr *convertSCEVToAddRecWithPredicates(
1012 const SCEV *S, const Loop *L,
1013 SmallPtrSetImpl<const SCEVPredicate *> &Preds);
1016 /// A CallbackVH to arrange for ScalarEvolution to be notified whenever a
1017 /// Value is deleted.
1018 class SCEVCallbackVH final : public CallbackVH {
1019 ScalarEvolution *SE;
1021 void deleted() override;
1022 void allUsesReplacedWith(Value *New) override;
1025 SCEVCallbackVH(Value *V, ScalarEvolution *SE = nullptr);
1028 friend class SCEVCallbackVH;
1029 friend class SCEVExpander;
1030 friend class SCEVUnknown;
1032 /// The function we are analyzing.
1035 /// Does the module have any calls to the llvm.experimental.guard intrinsic
1036 /// at all? If this is false, we avoid doing work that will only help if
1037 /// thare are guards present in the IR.
1040 /// The target library information for the target we are targeting.
1041 TargetLibraryInfo &TLI;
1043 /// The tracker for @llvm.assume intrinsics in this function.
1044 AssumptionCache &AC;
1046 /// The dominator tree.
1049 /// The loop information for the function we are currently analyzing.
1052 /// This SCEV is used to represent unknown trip counts and things.
1053 std::unique_ptr<SCEVCouldNotCompute> CouldNotCompute;
1055 /// The type for HasRecMap.
1056 using HasRecMapType = DenseMap<const SCEV *, bool>;
1058 /// This is a cache to record whether a SCEV contains any scAddRecExpr.
1059 HasRecMapType HasRecMap;
1061 /// The type for ExprValueMap.
1062 using ValueOffsetPair = std::pair<Value *, ConstantInt *>;
1063 using ExprValueMapType = DenseMap<const SCEV *, SetVector<ValueOffsetPair>>;
1065 /// ExprValueMap -- This map records the original values from which
1066 /// the SCEV expr is generated from.
1068 /// We want to represent the mapping as SCEV -> ValueOffsetPair instead
1069 /// of SCEV -> Value:
1070 /// Suppose we know S1 expands to V1, and
1073 /// where C_a and C_b are different SCEVConstants. Then we'd like to
1074 /// expand S3 as V1 - C_a + C_b instead of expanding S2 literally.
1075 /// It is helpful when S2 is a complex SCEV expr.
1077 /// In order to do that, we represent ExprValueMap as a mapping from
1078 /// SCEV to ValueOffsetPair. We will save both S1->{V1, 0} and
1079 /// S2->{V1, C_a} into the map when we create SCEV for V1. When S3
1080 /// is expanded, it will first expand S2 to V1 - C_a because of
1081 /// S2->{V1, C_a} in the map, then expand S3 to V1 - C_a + C_b.
1083 /// Note: S->{V, Offset} in the ExprValueMap means S can be expanded
1085 ExprValueMapType ExprValueMap;
1087 /// The type for ValueExprMap.
1088 using ValueExprMapType =
1089 DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *>>;
1091 /// This is a cache of the values we have analyzed so far.
1092 ValueExprMapType ValueExprMap;
1094 /// Mark predicate values currently being processed by isImpliedCond.
1095 SmallPtrSet<Value *, 6> PendingLoopPredicates;
1097 /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of
1098 /// conditions dominating the backedge of a loop.
1099 bool WalkingBEDominatingConds = false;
1101 /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a
1102 /// predicate by splitting it into a set of independent predicates.
1103 bool ProvingSplitPredicate = false;
1105 /// Memoized values for the GetMinTrailingZeros
1106 DenseMap<const SCEV *, uint32_t> MinTrailingZerosCache;
1108 /// Return the Value set from which the SCEV expr is generated.
1109 SetVector<ValueOffsetPair> *getSCEVValues(const SCEV *S);
1111 /// Private helper method for the GetMinTrailingZeros method
1112 uint32_t GetMinTrailingZerosImpl(const SCEV *S);
1114 /// Information about the number of loop iterations for which a loop exit's
1115 /// branch condition evaluates to the not-taken path. This is a temporary
1116 /// pair of exact and max expressions that are eventually summarized in
1117 /// ExitNotTakenInfo and BackedgeTakenInfo.
1119 const SCEV *ExactNotTaken; // The exit is not taken exactly this many times
1120 const SCEV *MaxNotTaken; // The exit is not taken at most this many times
1122 // Not taken either exactly MaxNotTaken or zero times
1123 bool MaxOrZero = false;
1125 /// A set of predicate guards for this ExitLimit. The result is only valid
1126 /// if all of the predicates in \c Predicates evaluate to 'true' at
1128 SmallPtrSet<const SCEVPredicate *, 4> Predicates;
1130 void addPredicate(const SCEVPredicate *P) {
1131 assert(!isa<SCEVUnionPredicate>(P) && "Only add leaf predicates here!");
1132 Predicates.insert(P);
1135 /*implicit*/ ExitLimit(const SCEV *E);
1138 const SCEV *E, const SCEV *M, bool MaxOrZero,
1139 ArrayRef<const SmallPtrSetImpl<const SCEVPredicate *> *> PredSetList);
1141 ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero,
1142 const SmallPtrSetImpl<const SCEVPredicate *> &PredSet);
1144 ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero);
1146 /// Test whether this ExitLimit contains any computed information, or
1147 /// whether it's all SCEVCouldNotCompute values.
1148 bool hasAnyInfo() const {
1149 return !isa<SCEVCouldNotCompute>(ExactNotTaken) ||
1150 !isa<SCEVCouldNotCompute>(MaxNotTaken);
1153 bool hasOperand(const SCEV *S) const;
1155 /// Test whether this ExitLimit contains all information.
1156 bool hasFullInfo() const {
1157 return !isa<SCEVCouldNotCompute>(ExactNotTaken);
1161 /// Information about the number of times a particular loop exit may be
1162 /// reached before exiting the loop.
1163 struct ExitNotTakenInfo {
1164 PoisoningVH<BasicBlock> ExitingBlock;
1165 const SCEV *ExactNotTaken;
1166 std::unique_ptr<SCEVUnionPredicate> Predicate;
1168 explicit ExitNotTakenInfo(PoisoningVH<BasicBlock> ExitingBlock,
1169 const SCEV *ExactNotTaken,
1170 std::unique_ptr<SCEVUnionPredicate> Predicate)
1171 : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken),
1172 Predicate(std::move(Predicate)) {}
1174 bool hasAlwaysTruePredicate() const {
1175 return !Predicate || Predicate->isAlwaysTrue();
1179 /// Information about the backedge-taken count of a loop. This currently
1180 /// includes an exact count and a maximum count.
1182 class BackedgeTakenInfo {
1183 /// A list of computable exits and their not-taken counts. Loops almost
1184 /// never have more than one computable exit.
1185 SmallVector<ExitNotTakenInfo, 1> ExitNotTaken;
1187 /// The pointer part of \c MaxAndComplete is an expression indicating the
1188 /// least maximum backedge-taken count of the loop that is known, or a
1189 /// SCEVCouldNotCompute. This expression is only valid if the predicates
1190 /// associated with all loop exits are true.
1192 /// The integer part of \c MaxAndComplete is a boolean indicating if \c
1193 /// ExitNotTaken has an element for every exiting block in the loop.
1194 PointerIntPair<const SCEV *, 1> MaxAndComplete;
1196 /// True iff the backedge is taken either exactly Max or zero times.
1197 bool MaxOrZero = false;
1199 /// \name Helper projection functions on \c MaxAndComplete.
1201 bool isComplete() const { return MaxAndComplete.getInt(); }
1202 const SCEV *getMax() const { return MaxAndComplete.getPointer(); }
1206 BackedgeTakenInfo() : MaxAndComplete(nullptr, 0) {}
1207 BackedgeTakenInfo(BackedgeTakenInfo &&) = default;
1208 BackedgeTakenInfo &operator=(BackedgeTakenInfo &&) = default;
1210 using EdgeExitInfo = std::pair<BasicBlock *, ExitLimit>;
1212 /// Initialize BackedgeTakenInfo from a list of exact exit counts.
1213 BackedgeTakenInfo(SmallVectorImpl<EdgeExitInfo> &&ExitCounts, bool Complete,
1214 const SCEV *MaxCount, bool MaxOrZero);
1216 /// Test whether this BackedgeTakenInfo contains any computed information,
1217 /// or whether it's all SCEVCouldNotCompute values.
1218 bool hasAnyInfo() const {
1219 return !ExitNotTaken.empty() || !isa<SCEVCouldNotCompute>(getMax());
1222 /// Test whether this BackedgeTakenInfo contains complete information.
1223 bool hasFullInfo() const { return isComplete(); }
1225 /// Return an expression indicating the exact *backedge-taken*
1226 /// count of the loop if it is known or SCEVCouldNotCompute
1227 /// otherwise. If execution makes it to the backedge on every
1228 /// iteration (i.e. there are no abnormal exists like exception
1229 /// throws and thread exits) then this is the number of times the
1230 /// loop header will execute minus one.
1232 /// If the SCEV predicate associated with the answer can be different
1233 /// from AlwaysTrue, we must add a (non null) Predicates argument.
1234 /// The SCEV predicate associated with the answer will be added to
1235 /// Predicates. A run-time check needs to be emitted for the SCEV
1236 /// predicate in order for the answer to be valid.
1238 /// Note that we should always know if we need to pass a predicate
1239 /// argument or not from the way the ExitCounts vector was computed.
1240 /// If we allowed SCEV predicates to be generated when populating this
1241 /// vector, this information can contain them and therefore a
1242 /// SCEVPredicate argument should be added to getExact.
1243 const SCEV *getExact(ScalarEvolution *SE,
1244 SCEVUnionPredicate *Predicates = nullptr) const;
1246 /// Return the number of times this loop exit may fall through to the back
1247 /// edge, or SCEVCouldNotCompute. The loop is guaranteed not to exit via
1248 /// this block before this number of iterations, but may exit via another
1250 const SCEV *getExact(BasicBlock *ExitingBlock, ScalarEvolution *SE) const;
1252 /// Get the max backedge taken count for the loop.
1253 const SCEV *getMax(ScalarEvolution *SE) const;
1255 /// Return true if the number of times this backedge is taken is either the
1256 /// value returned by getMax or zero.
1257 bool isMaxOrZero(ScalarEvolution *SE) const;
1259 /// Return true if any backedge taken count expressions refer to the given
1261 bool hasOperand(const SCEV *S, ScalarEvolution *SE) const;
1263 /// Invalidate this result and free associated memory.
1267 /// Cache the backedge-taken count of the loops for this function as they
1269 DenseMap<const Loop *, BackedgeTakenInfo> BackedgeTakenCounts;
1271 /// Cache the predicated backedge-taken count of the loops for this
1272 /// function as they are computed.
1273 DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts;
1275 /// This map contains entries for all of the PHI instructions that we
1276 /// attempt to compute constant evolutions for. This allows us to avoid
1277 /// potentially expensive recomputation of these properties. An instruction
1278 /// maps to null if we are unable to compute its exit value.
1279 DenseMap<PHINode *, Constant *> ConstantEvolutionLoopExitValue;
1281 /// This map contains entries for all the expressions that we attempt to
1282 /// compute getSCEVAtScope information for, which can be expensive in
1284 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1287 /// Memoized computeLoopDisposition results.
1288 DenseMap<const SCEV *,
1289 SmallVector<PointerIntPair<const Loop *, 2, LoopDisposition>, 2>>
1292 struct LoopProperties {
1293 /// Set to true if the loop contains no instruction that can have side
1294 /// effects (i.e. via throwing an exception, volatile or atomic access).
1295 bool HasNoAbnormalExits;
1297 /// Set to true if the loop contains no instruction that can abnormally exit
1298 /// the loop (i.e. via throwing an exception, by terminating the thread
1299 /// cleanly or by infinite looping in a called function). Strictly
1300 /// speaking, the last one is not leaving the loop, but is identical to
1301 /// leaving the loop for reasoning about undefined behavior.
1302 bool HasNoSideEffects;
1305 /// Cache for \c getLoopProperties.
1306 DenseMap<const Loop *, LoopProperties> LoopPropertiesCache;
1308 /// Return a \c LoopProperties instance for \p L, creating one if necessary.
1309 LoopProperties getLoopProperties(const Loop *L);
1311 bool loopHasNoSideEffects(const Loop *L) {
1312 return getLoopProperties(L).HasNoSideEffects;
1315 bool loopHasNoAbnormalExits(const Loop *L) {
1316 return getLoopProperties(L).HasNoAbnormalExits;
1319 /// Compute a LoopDisposition value.
1320 LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L);
1322 /// Memoized computeBlockDisposition results.
1325 SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>>
1328 /// Compute a BlockDisposition value.
1329 BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB);
1331 /// Memoized results from getRange
1332 DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
1334 /// Memoized results from getRange
1335 DenseMap<const SCEV *, ConstantRange> SignedRanges;
1337 /// Used to parameterize getRange
1338 enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED };
1340 /// Set the memoized range for the given SCEV.
1341 const ConstantRange &setRange(const SCEV *S, RangeSignHint Hint,
1343 DenseMap<const SCEV *, ConstantRange> &Cache =
1344 Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges;
1346 auto Pair = Cache.try_emplace(S, std::move(CR));
1348 Pair.first->second = std::move(CR);
1349 return Pair.first->second;
1352 /// Determine the range for a particular SCEV.
1353 /// NOTE: This returns a reference to an entry in a cache. It must be
1354 /// copied if its needed for longer.
1355 const ConstantRange &getRangeRef(const SCEV *S, RangeSignHint Hint);
1357 /// Determines the range for the affine SCEVAddRecExpr {\p Start,+,\p Stop}.
1358 /// Helper for \c getRange.
1359 ConstantRange getRangeForAffineAR(const SCEV *Start, const SCEV *Stop,
1360 const SCEV *MaxBECount, unsigned BitWidth);
1362 /// Try to compute a range for the affine SCEVAddRecExpr {\p Start,+,\p
1363 /// Stop} by "factoring out" a ternary expression from the add recurrence.
1364 /// Helper called by \c getRange.
1365 ConstantRange getRangeViaFactoring(const SCEV *Start, const SCEV *Stop,
1366 const SCEV *MaxBECount, unsigned BitWidth);
1368 /// We know that there is no SCEV for the specified value. Analyze the
1370 const SCEV *createSCEV(Value *V);
1372 /// Provide the special handling we need to analyze PHI SCEVs.
1373 const SCEV *createNodeForPHI(PHINode *PN);
1375 /// Helper function called from createNodeForPHI.
1376 const SCEV *createAddRecFromPHI(PHINode *PN);
1378 /// A helper function for createAddRecFromPHI to handle simple cases.
1379 const SCEV *createSimpleAffineAddRec(PHINode *PN, Value *BEValueV,
1380 Value *StartValueV);
1382 /// Helper function called from createNodeForPHI.
1383 const SCEV *createNodeFromSelectLikePHI(PHINode *PN);
1385 /// Provide special handling for a select-like instruction (currently this
1386 /// is either a select instruction or a phi node). \p I is the instruction
1387 /// being processed, and it is assumed equivalent to "Cond ? TrueVal :
1389 const SCEV *createNodeForSelectOrPHI(Instruction *I, Value *Cond,
1390 Value *TrueVal, Value *FalseVal);
1392 /// Provide the special handling we need to analyze GEP SCEVs.
1393 const SCEV *createNodeForGEP(GEPOperator *GEP);
1395 /// Implementation code for getSCEVAtScope; called at most once for each
1397 const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L);
1399 /// This looks up computed SCEV values for all instructions that depend on
1400 /// the given instruction and removes them from the ValueExprMap map if they
1401 /// reference SymName. This is used during PHI resolution.
1402 void forgetSymbolicName(Instruction *I, const SCEV *SymName);
1404 /// Return the BackedgeTakenInfo for the given loop, lazily computing new
1405 /// values if the loop hasn't been analyzed yet. The returned result is
1406 /// guaranteed not to be predicated.
1407 const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L);
1409 /// Similar to getBackedgeTakenInfo, but will add predicates as required
1410 /// with the purpose of returning complete information.
1411 const BackedgeTakenInfo &getPredicatedBackedgeTakenInfo(const Loop *L);
1413 /// Compute the number of times the specified loop will iterate.
1414 /// If AllowPredicates is set, we will create new SCEV predicates as
1415 /// necessary in order to return an exact answer.
1416 BackedgeTakenInfo computeBackedgeTakenCount(const Loop *L,
1417 bool AllowPredicates = false);
1419 /// Compute the number of times the backedge of the specified loop will
1420 /// execute if it exits via the specified block. If AllowPredicates is set,
1421 /// this call will try to use a minimal set of SCEV predicates in order to
1422 /// return an exact answer.
1423 ExitLimit computeExitLimit(const Loop *L, BasicBlock *ExitingBlock,
1424 bool AllowPredicates = false);
1426 /// Compute the number of times the backedge of the specified loop will
1427 /// execute if its exit condition were a conditional branch of ExitCond,
1430 /// \p ControlsExit is true if ExitCond directly controls the exit
1431 /// branch. In this case, we can assume that the loop exits only if the
1432 /// condition is true and can infer that failing to meet the condition prior
1433 /// to integer wraparound results in undefined behavior.
1435 /// If \p AllowPredicates is set, this call will try to use a minimal set of
1436 /// SCEV predicates in order to return an exact answer.
1437 ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond,
1438 BasicBlock *TBB, BasicBlock *FBB,
1440 bool AllowPredicates = false);
1442 // Helper functions for computeExitLimitFromCond to avoid exponential time
1445 class ExitLimitCache {
1446 // It may look like we need key on the whole (L, TBB, FBB, ControlsExit,
1447 // AllowPredicates) tuple, but recursive calls to
1448 // computeExitLimitFromCondCached from computeExitLimitFromCondImpl only
1449 // vary the in \c ExitCond and \c ControlsExit parameters. We remember the
1450 // initial values of the other values to assert our assumption.
1451 SmallDenseMap<PointerIntPair<Value *, 1>, ExitLimit> TripCountMap;
1456 bool AllowPredicates;
1459 ExitLimitCache(const Loop *L, BasicBlock *TBB, BasicBlock *FBB,
1460 bool AllowPredicates)
1461 : L(L), TBB(TBB), FBB(FBB), AllowPredicates(AllowPredicates) {}
1463 Optional<ExitLimit> find(const Loop *L, Value *ExitCond, BasicBlock *TBB,
1464 BasicBlock *FBB, bool ControlsExit,
1465 bool AllowPredicates);
1467 void insert(const Loop *L, Value *ExitCond, BasicBlock *TBB,
1468 BasicBlock *FBB, bool ControlsExit, bool AllowPredicates,
1469 const ExitLimit &EL);
1472 using ExitLimitCacheTy = ExitLimitCache;
1474 ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache,
1475 const Loop *L, Value *ExitCond,
1476 BasicBlock *TBB, BasicBlock *FBB,
1478 bool AllowPredicates);
1479 ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache, const Loop *L,
1480 Value *ExitCond, BasicBlock *TBB,
1481 BasicBlock *FBB, bool ControlsExit,
1482 bool AllowPredicates);
1484 /// Compute the number of times the backedge of the specified loop will
1485 /// execute if its exit condition were a conditional branch of the ICmpInst
1486 /// ExitCond, TBB, and FBB. If AllowPredicates is set, this call will try
1487 /// to use a minimal set of SCEV predicates in order to return an exact
1489 ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond,
1490 BasicBlock *TBB, BasicBlock *FBB,
1492 bool AllowPredicates = false);
1494 /// Compute the number of times the backedge of the specified loop will
1495 /// execute if its exit condition were a switch with a single exiting case
1497 ExitLimit computeExitLimitFromSingleExitSwitch(const Loop *L,
1499 BasicBlock *ExitingBB,
1502 /// Given an exit condition of 'icmp op load X, cst', try to see if we can
1503 /// compute the backedge-taken count.
1504 ExitLimit computeLoadConstantCompareExitLimit(LoadInst *LI, Constant *RHS,
1506 ICmpInst::Predicate p);
1508 /// Compute the exit limit of a loop that is controlled by a
1509 /// "(IV >> 1) != 0" type comparison. We cannot compute the exact trip
1510 /// count in these cases (since SCEV has no way of expressing them), but we
1511 /// can still sometimes compute an upper bound.
1513 /// Return an ExitLimit for a loop whose backedge is guarded by `LHS Pred
1515 ExitLimit computeShiftCompareExitLimit(Value *LHS, Value *RHS, const Loop *L,
1516 ICmpInst::Predicate Pred);
1518 /// If the loop is known to execute a constant number of times (the
1519 /// condition evolves only from constants), try to evaluate a few iterations
1520 /// of the loop until we get the exit condition gets a value of ExitWhen
1521 /// (true or false). If we cannot evaluate the exit count of the loop,
1522 /// return CouldNotCompute.
1523 const SCEV *computeExitCountExhaustively(const Loop *L, Value *Cond,
1526 /// Return the number of times an exit condition comparing the specified
1527 /// value to zero will execute. If not computable, return CouldNotCompute.
1528 /// If AllowPredicates is set, this call will try to use a minimal set of
1529 /// SCEV predicates in order to return an exact answer.
1530 ExitLimit howFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr,
1531 bool AllowPredicates = false);
1533 /// Return the number of times an exit condition checking the specified
1534 /// value for nonzero will execute. If not computable, return
1535 /// CouldNotCompute.
1536 ExitLimit howFarToNonZero(const SCEV *V, const Loop *L);
1538 /// Return the number of times an exit condition containing the specified
1539 /// less-than comparison will execute. If not computable, return
1540 /// CouldNotCompute.
1542 /// \p isSigned specifies whether the less-than is signed.
1544 /// \p ControlsExit is true when the LHS < RHS condition directly controls
1545 /// the branch (loops exits only if condition is true). In this case, we can
1546 /// use NoWrapFlags to skip overflow checks.
1548 /// If \p AllowPredicates is set, this call will try to use a minimal set of
1549 /// SCEV predicates in order to return an exact answer.
1550 ExitLimit howManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
1551 bool isSigned, bool ControlsExit,
1552 bool AllowPredicates = false);
1554 ExitLimit howManyGreaterThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
1555 bool isSigned, bool IsSubExpr,
1556 bool AllowPredicates = false);
1558 /// Return a predecessor of BB (which may not be an immediate predecessor)
1559 /// which has exactly one successor from which BB is reachable, or null if
1560 /// no such block is found.
1561 std::pair<BasicBlock *, BasicBlock *>
1562 getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB);
1564 /// Test whether the condition described by Pred, LHS, and RHS is true
1565 /// whenever the given FoundCondValue value evaluates to true.
1566 bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
1567 Value *FoundCondValue, bool Inverse);
1569 /// Test whether the condition described by Pred, LHS, and RHS is true
1570 /// whenever the condition described by FoundPred, FoundLHS, FoundRHS is
1572 bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
1573 ICmpInst::Predicate FoundPred, const SCEV *FoundLHS,
1574 const SCEV *FoundRHS);
1576 /// Test whether the condition described by Pred, LHS, and RHS is true
1577 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1579 bool isImpliedCondOperands(ICmpInst::Predicate Pred, const SCEV *LHS,
1580 const SCEV *RHS, const SCEV *FoundLHS,
1581 const SCEV *FoundRHS);
1583 /// Test whether the condition described by Pred, LHS, and RHS is true
1584 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1585 /// true. Here LHS is an operation that includes FoundLHS as one of its
1587 bool isImpliedViaOperations(ICmpInst::Predicate Pred,
1588 const SCEV *LHS, const SCEV *RHS,
1589 const SCEV *FoundLHS, const SCEV *FoundRHS,
1590 unsigned Depth = 0);
1592 /// Test whether the condition described by Pred, LHS, and RHS is true.
1593 /// Use only simple non-recursive types of checks, such as range analysis etc.
1594 bool isKnownViaSimpleReasoning(ICmpInst::Predicate Pred,
1595 const SCEV *LHS, const SCEV *RHS);
1597 /// Test whether the condition described by Pred, LHS, and RHS is true
1598 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1600 bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, const SCEV *LHS,
1601 const SCEV *RHS, const SCEV *FoundLHS,
1602 const SCEV *FoundRHS);
1604 /// Test whether the condition described by Pred, LHS, and RHS is true
1605 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1606 /// true. Utility function used by isImpliedCondOperands. Tries to get
1607 /// cases like "X `sgt` 0 => X - 1 `sgt` -1".
1608 bool isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred, const SCEV *LHS,
1609 const SCEV *RHS, const SCEV *FoundLHS,
1610 const SCEV *FoundRHS);
1612 /// Return true if the condition denoted by \p LHS \p Pred \p RHS is implied
1613 /// by a call to \c @llvm.experimental.guard in \p BB.
1614 bool isImpliedViaGuard(BasicBlock *BB, ICmpInst::Predicate Pred,
1615 const SCEV *LHS, const SCEV *RHS);
1617 /// Test whether the condition described by Pred, LHS, and RHS is true
1618 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1621 /// This routine tries to rule out certain kinds of integer overflow, and
1622 /// then tries to reason about arithmetic properties of the predicates.
1623 bool isImpliedCondOperandsViaNoOverflow(ICmpInst::Predicate Pred,
1624 const SCEV *LHS, const SCEV *RHS,
1625 const SCEV *FoundLHS,
1626 const SCEV *FoundRHS);
1628 /// If we know that the specified Phi is in the header of its containing
1629 /// loop, we know the loop executes a constant number of times, and the PHI
1630 /// node is just a recurrence involving constants, fold it.
1631 Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt &BEs,
1634 /// Test if the given expression is known to satisfy the condition described
1635 /// by Pred and the known constant ranges of LHS and RHS.
1636 bool isKnownPredicateViaConstantRanges(ICmpInst::Predicate Pred,
1637 const SCEV *LHS, const SCEV *RHS);
1639 /// Try to prove the condition described by "LHS Pred RHS" by ruling out
1640 /// integer overflow.
1642 /// For instance, this will return true for "A s< (A + C)<nsw>" if C is
1644 bool isKnownPredicateViaNoOverflow(ICmpInst::Predicate Pred, const SCEV *LHS,
1647 /// Try to split Pred LHS RHS into logical conjunctions (and's) and try to
1648 /// prove them individually.
1649 bool isKnownPredicateViaSplitting(ICmpInst::Predicate Pred, const SCEV *LHS,
1652 /// Try to match the Expr as "(L + R)<Flags>".
1653 bool splitBinaryAdd(const SCEV *Expr, const SCEV *&L, const SCEV *&R,
1654 SCEV::NoWrapFlags &Flags);
1656 /// Compute \p LHS - \p RHS and returns the result as an APInt if it is a
1657 /// constant, and None if it isn't.
1659 /// This is intended to be a cheaper version of getMinusSCEV. We can be
1660 /// frugal here since we just bail out of actually constructing and
1661 /// canonicalizing an expression in the cases where the result isn't going
1662 /// to be a constant.
1663 Optional<APInt> computeConstantDifference(const SCEV *LHS, const SCEV *RHS);
1665 /// Drop memoized information computed for S.
1666 void forgetMemoizedResults(const SCEV *S);
1668 /// Return an existing SCEV for V if there is one, otherwise return nullptr.
1669 const SCEV *getExistingSCEV(Value *V);
1671 /// Return false iff given SCEV contains a SCEVUnknown with NULL value-
1673 bool checkValidity(const SCEV *S) const;
1675 /// Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be
1676 /// equal to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}. This is
1677 /// equivalent to proving no signed (resp. unsigned) wrap in
1678 /// {`Start`,+,`Step`} if `ExtendOpTy` is `SCEVSignExtendExpr`
1679 /// (resp. `SCEVZeroExtendExpr`).
1680 template <typename ExtendOpTy>
1681 bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step,
1684 /// Try to prove NSW or NUW on \p AR relying on ConstantRange manipulation.
1685 SCEV::NoWrapFlags proveNoWrapViaConstantRanges(const SCEVAddRecExpr *AR);
1687 bool isMonotonicPredicateImpl(const SCEVAddRecExpr *LHS,
1688 ICmpInst::Predicate Pred, bool &Increasing);
1690 /// Return SCEV no-wrap flags that can be proven based on reasoning about
1691 /// how poison produced from no-wrap flags on this value (e.g. a nuw add)
1692 /// would trigger undefined behavior on overflow.
1693 SCEV::NoWrapFlags getNoWrapFlagsFromUB(const Value *V);
1695 /// Return true if the SCEV corresponding to \p I is never poison. Proving
1696 /// this is more complex than proving that just \p I is never poison, since
1697 /// SCEV commons expressions across control flow, and you can have cases
1701 /// ptr[idx0] = 100;
1702 /// if (<condition>) {
1703 /// idx1 = a +nsw b;
1704 /// ptr[idx1] = 200;
1707 /// where the SCEV expression (+ a b) is guaranteed to not be poison (and
1708 /// hence not sign-overflow) only if "<condition>" is true. Since both
1709 /// `idx0` and `idx1` will be mapped to the same SCEV expression, (+ a b),
1710 /// it is not okay to annotate (+ a b) with <nsw> in the above example.
1711 bool isSCEVExprNeverPoison(const Instruction *I);
1713 /// This is like \c isSCEVExprNeverPoison but it specifically works for
1714 /// instructions that will get mapped to SCEV add recurrences. Return true
1715 /// if \p I will never generate poison under the assumption that \p I is an
1716 /// add recurrence on the loop \p L.
1717 bool isAddRecNeverPoison(const Instruction *I, const Loop *L);
1719 /// Similar to createAddRecFromPHI, but with the additional flexibility of
1720 /// suggesting runtime overflow checks in case casts are encountered.
1721 /// If successful, the analysis records that for this loop, \p SymbolicPHI,
1722 /// which is the UnknownSCEV currently representing the PHI, can be rewritten
1723 /// into an AddRec, assuming some predicates; The function then returns the
1724 /// AddRec and the predicates as a pair, and caches this pair in
1725 /// PredicatedSCEVRewrites.
1726 /// If the analysis is not successful, a mapping from the \p SymbolicPHI to
1727 /// itself (with no predicates) is recorded, and a nullptr with an empty
1728 /// predicates vector is returned as a pair.
1729 Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
1730 createAddRecFromPHIWithCastsImpl(const SCEVUnknown *SymbolicPHI);
1732 /// Compute the backedge taken count knowing the interval difference, the
1733 /// stride and presence of the equality in the comparison.
1734 const SCEV *computeBECount(const SCEV *Delta, const SCEV *Stride,
1737 /// Compute the maximum backedge count based on the range of values
1738 /// permitted by Start, End, and Stride. This is for loops of the form
1739 /// {Start, +, Stride} LT End.
1741 /// Precondition: the induction variable is known to be positive. We *don't*
1742 /// assert these preconditions so please be careful.
1743 const SCEV *computeMaxBECountForLT(const SCEV *Start, const SCEV *Stride,
1744 const SCEV *End, unsigned BitWidth,
1747 /// Verify if an linear IV with positive stride can overflow when in a
1748 /// less-than comparison, knowing the invariant term of the comparison,
1749 /// the stride and the knowledge of NSW/NUW flags on the recurrence.
1750 bool doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, bool IsSigned,
1753 /// Verify if an linear IV with negative stride can overflow when in a
1754 /// greater-than comparison, knowing the invariant term of the comparison,
1755 /// the stride and the knowledge of NSW/NUW flags on the recurrence.
1756 bool doesIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, bool IsSigned,
1759 /// Get add expr already created or create a new one.
1760 const SCEV *getOrCreateAddExpr(SmallVectorImpl<const SCEV *> &Ops,
1761 SCEV::NoWrapFlags Flags);
1763 /// Get mul expr already created or create a new one.
1764 const SCEV *getOrCreateMulExpr(SmallVectorImpl<const SCEV *> &Ops,
1765 SCEV::NoWrapFlags Flags);
1767 /// Find all of the loops transitively used in \p S, and update \c LoopUsers
1769 void addToLoopUseLists(const SCEV *S);
1771 FoldingSet<SCEV> UniqueSCEVs;
1772 FoldingSet<SCEVPredicate> UniquePreds;
1773 BumpPtrAllocator SCEVAllocator;
1775 /// This maps loops to a list of SCEV expressions that (transitively) use said
1777 DenseMap<const Loop *, SmallVector<const SCEV *, 4>> LoopUsers;
1779 /// Cache tentative mappings from UnknownSCEVs in a Loop, to a SCEV expression
1780 /// they can be rewritten into under certain predicates.
1781 DenseMap<std::pair<const SCEVUnknown *, const Loop *>,
1782 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
1783 PredicatedSCEVRewrites;
1785 /// The head of a linked list of all SCEVUnknown values that have been
1786 /// allocated. This is used by releaseMemory to locate them all and call
1787 /// their destructors.
1788 SCEVUnknown *FirstUnknown = nullptr;
1791 /// Analysis pass that exposes the \c ScalarEvolution for a function.
1792 class ScalarEvolutionAnalysis
1793 : public AnalysisInfoMixin<ScalarEvolutionAnalysis> {
1794 friend AnalysisInfoMixin<ScalarEvolutionAnalysis>;
1796 static AnalysisKey Key;
1799 using Result = ScalarEvolution;
1801 ScalarEvolution run(Function &F, FunctionAnalysisManager &AM);
1804 /// Printer pass for the \c ScalarEvolutionAnalysis results.
1805 class ScalarEvolutionPrinterPass
1806 : public PassInfoMixin<ScalarEvolutionPrinterPass> {
1810 explicit ScalarEvolutionPrinterPass(raw_ostream &OS) : OS(OS) {}
1812 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
1815 class ScalarEvolutionWrapperPass : public FunctionPass {
1816 std::unique_ptr<ScalarEvolution> SE;
1821 ScalarEvolutionWrapperPass();
1823 ScalarEvolution &getSE() { return *SE; }
1824 const ScalarEvolution &getSE() const { return *SE; }
1826 bool runOnFunction(Function &F) override;
1827 void releaseMemory() override;
1828 void getAnalysisUsage(AnalysisUsage &AU) const override;
1829 void print(raw_ostream &OS, const Module * = nullptr) const override;
1830 void verifyAnalysis() const override;
1833 /// An interface layer with SCEV used to manage how we see SCEV expressions
1834 /// for values in the context of existing predicates. We can add new
1835 /// predicates, but we cannot remove them.
1837 /// This layer has multiple purposes:
1838 /// - provides a simple interface for SCEV versioning.
1839 /// - guarantees that the order of transformations applied on a SCEV
1840 /// expression for a single Value is consistent across two different
1841 /// getSCEV calls. This means that, for example, once we've obtained
1842 /// an AddRec expression for a certain value through expression
1843 /// rewriting, we will continue to get an AddRec expression for that
1845 /// - lowers the number of expression rewrites.
1846 class PredicatedScalarEvolution {
1848 PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L);
1850 const SCEVUnionPredicate &getUnionPredicate() const;
1852 /// Returns the SCEV expression of V, in the context of the current SCEV
1853 /// predicate. The order of transformations applied on the expression of V
1854 /// returned by ScalarEvolution is guaranteed to be preserved, even when
1855 /// adding new predicates.
1856 const SCEV *getSCEV(Value *V);
1858 /// Get the (predicated) backedge count for the analyzed loop.
1859 const SCEV *getBackedgeTakenCount();
1861 /// Adds a new predicate.
1862 void addPredicate(const SCEVPredicate &Pred);
1864 /// Attempts to produce an AddRecExpr for V by adding additional SCEV
1865 /// predicates. If we can't transform the expression into an AddRecExpr we
1866 /// return nullptr and not add additional SCEV predicates to the current
1868 const SCEVAddRecExpr *getAsAddRec(Value *V);
1870 /// Proves that V doesn't overflow by adding SCEV predicate.
1871 void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags);
1873 /// Returns true if we've proved that V doesn't wrap by means of a SCEV
1875 bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags);
1877 /// Returns the ScalarEvolution analysis used.
1878 ScalarEvolution *getSE() const { return &SE; }
1880 /// We need to explicitly define the copy constructor because of FlagsMap.
1881 PredicatedScalarEvolution(const PredicatedScalarEvolution &);
1883 /// Print the SCEV mappings done by the Predicated Scalar Evolution.
1884 /// The printed text is indented by \p Depth.
1885 void print(raw_ostream &OS, unsigned Depth) const;
1887 /// Check if \p AR1 and \p AR2 are equal, while taking into account
1888 /// Equal predicates in Preds.
1889 bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1,
1890 const SCEVAddRecExpr *AR2) const;
1893 /// Increments the version number of the predicate. This needs to be called
1894 /// every time the SCEV predicate changes.
1895 void updateGeneration();
1897 /// Holds a SCEV and the version number of the SCEV predicate used to
1898 /// perform the rewrite of the expression.
1899 using RewriteEntry = std::pair<unsigned, const SCEV *>;
1901 /// Maps a SCEV to the rewrite result of that SCEV at a certain version
1902 /// number. If this number doesn't match the current Generation, we will
1903 /// need to do a rewrite. To preserve the transformation order of previous
1904 /// rewrites, we will rewrite the previous result instead of the original
1906 DenseMap<const SCEV *, RewriteEntry> RewriteMap;
1908 /// Records what NoWrap flags we've added to a Value *.
1909 ValueMap<Value *, SCEVWrapPredicate::IncrementWrapFlags> FlagsMap;
1911 /// The ScalarEvolution analysis.
1912 ScalarEvolution &SE;
1914 /// The analyzed Loop.
1917 /// The SCEVPredicate that forms our context. We will rewrite all
1918 /// expressions assuming that this predicate true.
1919 SCEVUnionPredicate Preds;
1921 /// Marks the version of the SCEV predicate used. When rewriting a SCEV
1922 /// expression we mark it with the version of the predicate. We use this to
1923 /// figure out if the predicate has changed from the last rewrite of the
1924 /// SCEV. If so, we need to perform a new rewrite.
1925 unsigned Generation = 0;
1927 /// The backedge taken count.
1928 const SCEV *BackedgeCount = nullptr;
1931 } // end namespace llvm
1933 #endif // LLVM_ANALYSIS_SCALAREVOLUTION_H