1 //===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
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.
15 // This analysis is primarily useful for induction variable substitution and
16 // strength reduction.
18 //===----------------------------------------------------------------------===//
20 #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
21 #define LLVM_ANALYSIS_SCALAREVOLUTION_H
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"
30 #include "llvm/ADT/PointerIntPair.h"
31 #include "llvm/ADT/SetVector.h"
32 #include "llvm/ADT/SmallPtrSet.h"
33 #include "llvm/ADT/SmallVector.h"
34 #include "llvm/Analysis/LoopInfo.h"
35 #include "llvm/IR/ConstantRange.h"
36 #include "llvm/IR/Function.h"
37 #include "llvm/IR/InstrTypes.h"
38 #include "llvm/IR/Instructions.h"
39 #include "llvm/IR/Operator.h"
40 #include "llvm/IR/PassManager.h"
41 #include "llvm/IR/ValueHandle.h"
42 #include "llvm/IR/ValueMap.h"
43 #include "llvm/Pass.h"
44 #include "llvm/Support/Allocator.h"
45 #include "llvm/Support/Casting.h"
46 #include "llvm/Support/Compiler.h"
55 class AssumptionCache;
65 class ScalarEvolution;
69 class TargetLibraryInfo;
73 /// This class represents an analyzed expression in the program. These are
74 /// opaque objects that the client is not allowed to do much with directly.
76 class SCEV : public FoldingSetNode {
77 friend struct FoldingSetTrait<SCEV>;
79 /// A reference to an Interned FoldingSetNodeID for this node. The
80 /// ScalarEvolution's BumpPtrAllocator holds the data.
81 FoldingSetNodeIDRef FastID;
83 // The SCEV baseclass this node corresponds to
84 const unsigned short SCEVType;
87 // Estimated complexity of this node's expression tree size.
88 const unsigned short ExpressionSize;
90 /// This field is initialized to zero and may be used in subclasses to store
91 /// miscellaneous information.
92 unsigned short SubclassData = 0;
95 /// NoWrapFlags are bitfield indices into SubclassData.
97 /// Add and Mul expressions may have no-unsigned-wrap <NUW> or
98 /// no-signed-wrap <NSW> properties, which are derived from the IR
99 /// operator. NSW is a misnomer that we use to mean no signed overflow or
102 /// AddRec expressions may have a no-self-wraparound <NW> property if, in
103 /// the integer domain, abs(step) * max-iteration(loop) <=
104 /// unsigned-max(bitwidth). This means that the recurrence will never reach
105 /// its start value if the step is non-zero. Computing the same value on
106 /// each iteration is not considered wrapping, and recurrences with step = 0
107 /// are trivially <NW>. <NW> is independent of the sign of step and the
108 /// value the add recurrence starts with.
110 /// Note that NUW and NSW are also valid properties of a recurrence, and
111 /// either implies NW. For convenience, NW will be set for a recurrence
112 /// whenever either NUW or NSW are set.
114 FlagAnyWrap = 0, // No guarantee.
115 FlagNW = (1 << 0), // No self-wrap.
116 FlagNUW = (1 << 1), // No unsigned wrap.
117 FlagNSW = (1 << 2), // No signed wrap.
118 NoWrapMask = (1 << 3) - 1
121 explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy,
122 unsigned short ExpressionSize)
123 : FastID(ID), SCEVType(SCEVTy), ExpressionSize(ExpressionSize) {}
124 SCEV(const SCEV &) = delete;
125 SCEV &operator=(const SCEV &) = delete;
127 unsigned getSCEVType() const { return SCEVType; }
129 /// Return the LLVM type of this SCEV expression.
130 Type *getType() const;
132 /// Return true if the expression is a constant zero.
135 /// Return true if the expression is a constant one.
138 /// Return true if the expression is a constant all-ones value.
139 bool isAllOnesValue() const;
141 /// Return true if the specified scev is negated, but not a constant.
142 bool isNonConstantNegative() const;
144 // Returns estimated size of the mathematical expression represented by this
145 // SCEV. The rules of its calculation are following:
146 // 1) Size of a SCEV without operands (like constants and SCEVUnknown) is 1;
147 // 2) Size SCEV with operands Op1, Op2, ..., OpN is calculated by formula:
148 // (1 + Size(Op1) + ... + Size(OpN)).
149 // This value gives us an estimation of time we need to traverse through this
150 // SCEV and all its operands recursively. We may use it to avoid performing
151 // heavy transformations on SCEVs of excessive size for sake of saving the
153 unsigned short getExpressionSize() const {
154 return ExpressionSize;
157 /// Print out the internal representation of this scalar to the specified
158 /// stream. This should really only be used for debugging purposes.
159 void print(raw_ostream &OS) const;
161 /// This method is used for debugging.
165 // Specialize FoldingSetTrait for SCEV to avoid needing to compute
166 // temporary FoldingSetNodeID values.
167 template <> struct FoldingSetTrait<SCEV> : DefaultFoldingSetTrait<SCEV> {
168 static void Profile(const SCEV &X, FoldingSetNodeID &ID) { ID = X.FastID; }
170 static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, unsigned IDHash,
171 FoldingSetNodeID &TempID) {
172 return ID == X.FastID;
175 static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) {
176 return X.FastID.ComputeHash();
180 inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) {
185 /// An object of this class is returned by queries that could not be answered.
186 /// For example, if you ask for the number of iterations of a linked-list
187 /// traversal loop, you will get one of these. None of the standard SCEV
188 /// operations are valid on this class, it is just a marker.
189 struct SCEVCouldNotCompute : public SCEV {
190 SCEVCouldNotCompute();
192 /// Methods for support type inquiry through isa, cast, and dyn_cast:
193 static bool classof(const SCEV *S);
196 /// This class represents an assumption made using SCEV expressions which can
197 /// be checked at run-time.
198 class SCEVPredicate : public FoldingSetNode {
199 friend struct FoldingSetTrait<SCEVPredicate>;
201 /// A reference to an Interned FoldingSetNodeID for this node. The
202 /// ScalarEvolution's BumpPtrAllocator holds the data.
203 FoldingSetNodeIDRef FastID;
206 enum SCEVPredicateKind { P_Union, P_Equal, P_Wrap };
209 SCEVPredicateKind Kind;
210 ~SCEVPredicate() = default;
211 SCEVPredicate(const SCEVPredicate &) = default;
212 SCEVPredicate &operator=(const SCEVPredicate &) = default;
215 SCEVPredicate(const FoldingSetNodeIDRef ID, SCEVPredicateKind Kind);
217 SCEVPredicateKind getKind() const { return Kind; }
219 /// Returns the estimated complexity of this predicate. This is roughly
220 /// measured in the number of run-time checks required.
221 virtual unsigned getComplexity() const { return 1; }
223 /// Returns true if the predicate is always true. This means that no
224 /// assumptions were made and nothing needs to be checked at run-time.
225 virtual bool isAlwaysTrue() const = 0;
227 /// Returns true if this predicate implies \p N.
228 virtual bool implies(const SCEVPredicate *N) const = 0;
230 /// Prints a textual representation of this predicate with an indentation of
232 virtual void print(raw_ostream &OS, unsigned Depth = 0) const = 0;
234 /// Returns the SCEV to which this predicate applies, or nullptr if this is
235 /// a SCEVUnionPredicate.
236 virtual const SCEV *getExpr() const = 0;
239 inline raw_ostream &operator<<(raw_ostream &OS, const SCEVPredicate &P) {
244 // Specialize FoldingSetTrait for SCEVPredicate to avoid needing to compute
245 // temporary FoldingSetNodeID values.
247 struct FoldingSetTrait<SCEVPredicate> : DefaultFoldingSetTrait<SCEVPredicate> {
248 static void Profile(const SCEVPredicate &X, FoldingSetNodeID &ID) {
252 static bool Equals(const SCEVPredicate &X, const FoldingSetNodeID &ID,
253 unsigned IDHash, FoldingSetNodeID &TempID) {
254 return ID == X.FastID;
257 static unsigned ComputeHash(const SCEVPredicate &X,
258 FoldingSetNodeID &TempID) {
259 return X.FastID.ComputeHash();
263 /// This class represents an assumption that two SCEV expressions are equal,
264 /// and this can be checked at run-time.
265 class SCEVEqualPredicate final : public SCEVPredicate {
266 /// We assume that LHS == RHS.
271 SCEVEqualPredicate(const FoldingSetNodeIDRef ID, const SCEV *LHS,
274 /// Implementation of the SCEVPredicate interface
275 bool implies(const SCEVPredicate *N) const override;
276 void print(raw_ostream &OS, unsigned Depth = 0) const override;
277 bool isAlwaysTrue() const override;
278 const SCEV *getExpr() const override;
280 /// Returns the left hand side of the equality.
281 const SCEV *getLHS() const { return LHS; }
283 /// Returns the right hand side of the equality.
284 const SCEV *getRHS() const { return RHS; }
286 /// Methods for support type inquiry through isa, cast, and dyn_cast:
287 static bool classof(const SCEVPredicate *P) {
288 return P->getKind() == P_Equal;
292 /// This class represents an assumption made on an AddRec expression. Given an
293 /// affine AddRec expression {a,+,b}, we assume that it has the nssw or nusw
294 /// flags (defined below) in the first X iterations of the loop, where X is a
295 /// SCEV expression returned by getPredicatedBackedgeTakenCount).
297 /// Note that this does not imply that X is equal to the backedge taken
298 /// count. This means that if we have a nusw predicate for i32 {0,+,1} with a
299 /// predicated backedge taken count of X, we only guarantee that {0,+,1} has
300 /// nusw in the first X iterations. {0,+,1} may still wrap in the loop if we
301 /// have more than X iterations.
302 class SCEVWrapPredicate final : public SCEVPredicate {
304 /// Similar to SCEV::NoWrapFlags, but with slightly different semantics
305 /// for FlagNUSW. The increment is considered to be signed, and a + b
306 /// (where b is the increment) is considered to wrap if:
307 /// zext(a + b) != zext(a) + sext(b)
309 /// If Signed is a function that takes an n-bit tuple and maps to the
310 /// integer domain as the tuples value interpreted as twos complement,
311 /// and Unsigned a function that takes an n-bit tuple and maps to the
312 /// integer domain as as the base two value of input tuple, then a + b
313 /// has IncrementNUSW iff:
315 /// 0 <= Unsigned(a) + Signed(b) < 2^n
317 /// The IncrementNSSW flag has identical semantics with SCEV::FlagNSW.
319 /// Note that the IncrementNUSW flag is not commutative: if base + inc
320 /// has IncrementNUSW, then inc + base doesn't neccessarily have this
321 /// property. The reason for this is that this is used for sign/zero
322 /// extending affine AddRec SCEV expressions when a SCEVWrapPredicate is
323 /// assumed. A {base,+,inc} expression is already non-commutative with
324 /// regards to base and inc, since it is interpreted as:
325 /// (((base + inc) + inc) + inc) ...
326 enum IncrementWrapFlags {
327 IncrementAnyWrap = 0, // No guarantee.
328 IncrementNUSW = (1 << 0), // No unsigned with signed increment wrap.
329 IncrementNSSW = (1 << 1), // No signed with signed increment wrap
330 // (equivalent with SCEV::NSW)
331 IncrementNoWrapMask = (1 << 2) - 1
334 /// Convenient IncrementWrapFlags manipulation methods.
335 LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags
336 clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags,
337 SCEVWrapPredicate::IncrementWrapFlags OffFlags) {
338 assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
339 assert((OffFlags & IncrementNoWrapMask) == OffFlags &&
340 "Invalid flags value!");
341 return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & ~OffFlags);
344 LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags
345 maskFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, int Mask) {
346 assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
347 assert((Mask & IncrementNoWrapMask) == Mask && "Invalid mask value!");
349 return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & Mask);
352 LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags
353 setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags,
354 SCEVWrapPredicate::IncrementWrapFlags OnFlags) {
355 assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
356 assert((OnFlags & IncrementNoWrapMask) == OnFlags &&
357 "Invalid flags value!");
359 return (SCEVWrapPredicate::IncrementWrapFlags)(Flags | OnFlags);
362 /// Returns the set of SCEVWrapPredicate no wrap flags implied by a
364 LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags
365 getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE);
368 const SCEVAddRecExpr *AR;
369 IncrementWrapFlags Flags;
372 explicit SCEVWrapPredicate(const FoldingSetNodeIDRef ID,
373 const SCEVAddRecExpr *AR,
374 IncrementWrapFlags Flags);
376 /// Returns the set assumed no overflow flags.
377 IncrementWrapFlags getFlags() const { return Flags; }
379 /// Implementation of the SCEVPredicate interface
380 const SCEV *getExpr() const override;
381 bool implies(const SCEVPredicate *N) const override;
382 void print(raw_ostream &OS, unsigned Depth = 0) const override;
383 bool isAlwaysTrue() const override;
385 /// Methods for support type inquiry through isa, cast, and dyn_cast:
386 static bool classof(const SCEVPredicate *P) {
387 return P->getKind() == P_Wrap;
391 /// This class represents a composition of other SCEV predicates, and is the
392 /// class that most clients will interact with. This is equivalent to a
393 /// logical "AND" of all the predicates in the union.
395 /// NB! Unlike other SCEVPredicate sub-classes this class does not live in the
396 /// ScalarEvolution::Preds folding set. This is why the \c add function is sound.
397 class SCEVUnionPredicate final : public SCEVPredicate {
400 DenseMap<const SCEV *, SmallVector<const SCEVPredicate *, 4>>;
402 /// Vector with references to all predicates in this union.
403 SmallVector<const SCEVPredicate *, 16> Preds;
405 /// Maps SCEVs to predicates for quick look-ups.
406 PredicateMap SCEVToPreds;
409 SCEVUnionPredicate();
411 const SmallVectorImpl<const SCEVPredicate *> &getPredicates() const {
415 /// Adds a predicate to this union.
416 void add(const SCEVPredicate *N);
418 /// Returns a reference to a vector containing all predicates which apply to
420 ArrayRef<const SCEVPredicate *> getPredicatesForExpr(const SCEV *Expr);
422 /// Implementation of the SCEVPredicate interface
423 bool isAlwaysTrue() const override;
424 bool implies(const SCEVPredicate *N) const override;
425 void print(raw_ostream &OS, unsigned Depth) const override;
426 const SCEV *getExpr() const override;
428 /// We estimate the complexity of a union predicate as the size number of
429 /// predicates in the union.
430 unsigned getComplexity() const override { return Preds.size(); }
432 /// Methods for support type inquiry through isa, cast, and dyn_cast:
433 static bool classof(const SCEVPredicate *P) {
434 return P->getKind() == P_Union;
438 struct ExitLimitQuery {
439 ExitLimitQuery(const Loop *L, BasicBlock *ExitingBlock, bool AllowPredicates)
440 : L(L), ExitingBlock(ExitingBlock), AllowPredicates(AllowPredicates) {}
443 BasicBlock *ExitingBlock;
444 bool AllowPredicates;
447 template <> struct DenseMapInfo<ExitLimitQuery> {
448 static inline ExitLimitQuery getEmptyKey() {
449 return ExitLimitQuery(nullptr, nullptr, true);
452 static inline ExitLimitQuery getTombstoneKey() {
453 return ExitLimitQuery(nullptr, nullptr, false);
456 static unsigned getHashValue(ExitLimitQuery Val) {
457 return hash_combine(hash_combine(Val.L, Val.ExitingBlock),
458 Val.AllowPredicates);
461 static bool isEqual(ExitLimitQuery LHS, ExitLimitQuery RHS) {
462 return LHS.L == RHS.L && LHS.ExitingBlock == RHS.ExitingBlock &&
463 LHS.AllowPredicates == RHS.AllowPredicates;
467 /// The main scalar evolution driver. Because client code (intentionally)
468 /// can't do much with the SCEV objects directly, they must ask this class
470 class ScalarEvolution {
472 /// An enum describing the relationship between a SCEV and a loop.
473 enum LoopDisposition {
474 LoopVariant, ///< The SCEV is loop-variant (unknown).
475 LoopInvariant, ///< The SCEV is loop-invariant.
476 LoopComputable ///< The SCEV varies predictably with the loop.
479 /// An enum describing the relationship between a SCEV and a basic block.
480 enum BlockDisposition {
481 DoesNotDominateBlock, ///< The SCEV does not dominate the block.
482 DominatesBlock, ///< The SCEV dominates the block.
483 ProperlyDominatesBlock ///< The SCEV properly dominates the block.
486 /// Convenient NoWrapFlags manipulation that hides enum casts and is
487 /// visible in the ScalarEvolution name space.
488 LLVM_NODISCARD static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags,
490 return (SCEV::NoWrapFlags)(Flags & Mask);
492 LLVM_NODISCARD static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags,
493 SCEV::NoWrapFlags OnFlags) {
494 return (SCEV::NoWrapFlags)(Flags | OnFlags);
496 LLVM_NODISCARD static SCEV::NoWrapFlags
497 clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags) {
498 return (SCEV::NoWrapFlags)(Flags & ~OffFlags);
501 ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC,
502 DominatorTree &DT, LoopInfo &LI);
503 ScalarEvolution(ScalarEvolution &&Arg);
506 LLVMContext &getContext() const { return F.getContext(); }
508 /// Test if values of the given type are analyzable within the SCEV
509 /// framework. This primarily includes integer types, and it can optionally
510 /// include pointer types if the ScalarEvolution class has access to
511 /// target-specific information.
512 bool isSCEVable(Type *Ty) const;
514 /// Return the size in bits of the specified type, for which isSCEVable must
516 uint64_t getTypeSizeInBits(Type *Ty) const;
518 /// Return a type with the same bitwidth as the given type and which
519 /// represents how SCEV will treat the given type, for which isSCEVable must
520 /// return true. For pointer types, this is the pointer-sized integer type.
521 Type *getEffectiveSCEVType(Type *Ty) const;
523 // Returns a wider type among {Ty1, Ty2}.
524 Type *getWiderType(Type *Ty1, Type *Ty2) const;
526 /// Return true if the SCEV is a scAddRecExpr or it contains
527 /// scAddRecExpr. The result will be cached in HasRecMap.
528 bool containsAddRecurrence(const SCEV *S);
530 /// Erase Value from ValueExprMap and ExprValueMap.
531 void eraseValueFromMap(Value *V);
533 /// Return a SCEV expression for the full generality of the specified
535 const SCEV *getSCEV(Value *V);
537 const SCEV *getConstant(ConstantInt *V);
538 const SCEV *getConstant(const APInt &Val);
539 const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false);
540 const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
541 const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
542 const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
543 const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty);
544 const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
545 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
547 const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS,
548 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
549 unsigned Depth = 0) {
550 SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
551 return getAddExpr(Ops, Flags, Depth);
553 const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
554 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
555 unsigned Depth = 0) {
556 SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
557 return getAddExpr(Ops, Flags, Depth);
559 const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
560 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
562 const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS,
563 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
564 unsigned Depth = 0) {
565 SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
566 return getMulExpr(Ops, Flags, Depth);
568 const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
569 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
570 unsigned Depth = 0) {
571 SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
572 return getMulExpr(Ops, Flags, Depth);
574 const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS);
575 const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS);
576 const SCEV *getURemExpr(const SCEV *LHS, const SCEV *RHS);
577 const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L,
578 SCEV::NoWrapFlags Flags);
579 const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
580 const Loop *L, SCEV::NoWrapFlags Flags);
581 const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands,
582 const Loop *L, SCEV::NoWrapFlags Flags) {
583 SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end());
584 return getAddRecExpr(NewOp, L, Flags);
587 /// Checks if \p SymbolicPHI can be rewritten as an AddRecExpr under some
588 /// Predicates. If successful return these <AddRecExpr, Predicates>;
589 /// The function is intended to be called from PSCEV (the caller will decide
590 /// whether to actually add the predicates and carry out the rewrites).
591 Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
592 createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI);
594 /// Returns an expression for a GEP
596 /// \p GEP The GEP. The indices contained in the GEP itself are ignored,
597 /// instead we use IndexExprs.
598 /// \p IndexExprs The expressions for the indices.
599 const SCEV *getGEPExpr(GEPOperator *GEP,
600 const SmallVectorImpl<const SCEV *> &IndexExprs);
601 const SCEV *getMinMaxExpr(unsigned Kind,
602 SmallVectorImpl<const SCEV *> &Operands);
603 const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS);
604 const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
605 const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS);
606 const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
607 const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS);
608 const SCEV *getSMinExpr(SmallVectorImpl<const SCEV *> &Operands);
609 const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS);
610 const SCEV *getUMinExpr(SmallVectorImpl<const SCEV *> &Operands);
611 const SCEV *getUnknown(Value *V);
612 const SCEV *getCouldNotCompute();
614 /// Return a SCEV for the constant 0 of a specific type.
615 const SCEV *getZero(Type *Ty) { return getConstant(Ty, 0); }
617 /// Return a SCEV for the constant 1 of a specific type.
618 const SCEV *getOne(Type *Ty) { return getConstant(Ty, 1); }
620 /// Return an expression for sizeof AllocTy that is type IntTy
621 const SCEV *getSizeOfExpr(Type *IntTy, Type *AllocTy);
623 /// Return an expression for offsetof on the given field with type IntTy
624 const SCEV *getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo);
626 /// Return the SCEV object corresponding to -V.
627 const SCEV *getNegativeSCEV(const SCEV *V,
628 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap);
630 /// Return the SCEV object corresponding to ~V.
631 const SCEV *getNotSCEV(const SCEV *V);
633 /// Return LHS-RHS. Minus is represented in SCEV as A+B*-1.
634 const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
635 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
638 /// Return a SCEV corresponding to a conversion of the input value to the
639 /// specified type. If the type must be extended, it is zero extended.
640 const SCEV *getTruncateOrZeroExtend(const SCEV *V, Type *Ty,
643 /// Return a SCEV corresponding to a conversion of the input value to the
644 /// specified type. If the type must be extended, it is sign extended.
645 const SCEV *getTruncateOrSignExtend(const SCEV *V, Type *Ty,
648 /// Return a SCEV corresponding to a conversion of the input value to the
649 /// specified type. If the type must be extended, it is zero extended. The
650 /// conversion must not be narrowing.
651 const SCEV *getNoopOrZeroExtend(const SCEV *V, Type *Ty);
653 /// Return a SCEV corresponding to a conversion of the input value to the
654 /// specified type. If the type must be extended, it is sign extended. The
655 /// conversion must not be narrowing.
656 const SCEV *getNoopOrSignExtend(const SCEV *V, Type *Ty);
658 /// Return a SCEV corresponding to a conversion of the input value to the
659 /// specified type. If the type must be extended, it is extended with
660 /// unspecified bits. The conversion must not be narrowing.
661 const SCEV *getNoopOrAnyExtend(const SCEV *V, Type *Ty);
663 /// Return a SCEV corresponding to a conversion of the input value to the
664 /// specified type. The conversion must not be widening.
665 const SCEV *getTruncateOrNoop(const SCEV *V, Type *Ty);
667 /// Promote the operands to the wider of the types using zero-extension, and
668 /// then perform a umax operation with them.
669 const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS);
671 /// Promote the operands to the wider of the types using zero-extension, and
672 /// then perform a umin operation with them.
673 const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS);
675 /// Promote the operands to the wider of the types using zero-extension, and
676 /// then perform a umin operation with them. N-ary function.
677 const SCEV *getUMinFromMismatchedTypes(SmallVectorImpl<const SCEV *> &Ops);
679 /// Transitively follow the chain of pointer-type operands until reaching a
680 /// SCEV that does not have a single pointer operand. This returns a
681 /// SCEVUnknown pointer for well-formed pointer-type expressions, but corner
683 const SCEV *getPointerBase(const SCEV *V);
685 /// Return a SCEV expression for the specified value at the specified scope
686 /// in the program. The L value specifies a loop nest to evaluate the
687 /// expression at, where null is the top-level or a specified loop is
688 /// immediately inside of the loop.
690 /// This method can be used to compute the exit value for a variable defined
691 /// in a loop by querying what the value will hold in the parent loop.
693 /// In the case that a relevant loop exit value cannot be computed, the
694 /// original value V is returned.
695 const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L);
697 /// This is a convenience function which does getSCEVAtScope(getSCEV(V), L).
698 const SCEV *getSCEVAtScope(Value *V, const Loop *L);
700 /// Test whether entry to the loop is protected by a conditional between LHS
701 /// and RHS. This is used to help avoid max expressions in loop trip
702 /// counts, and to eliminate casts.
703 bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
704 const SCEV *LHS, const SCEV *RHS);
706 /// Test whether the backedge of the loop is protected by a conditional
707 /// between LHS and RHS. This is used to eliminate casts.
708 bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
709 const SCEV *LHS, const SCEV *RHS);
711 /// Returns the maximum trip count of the loop if it is a single-exit
712 /// loop and we can compute a small maximum for that loop.
714 /// Implemented in terms of the \c getSmallConstantTripCount overload with
715 /// the single exiting block passed to it. See that routine for details.
716 unsigned getSmallConstantTripCount(const Loop *L);
718 /// Returns the maximum trip count of this loop as a normal unsigned
719 /// value. Returns 0 if the trip count is unknown or not constant. This
720 /// "trip count" assumes that control exits via ExitingBlock. More
721 /// precisely, it is the number of times that control may reach ExitingBlock
722 /// before taking the branch. For loops with multiple exits, it may not be
723 /// the number times that the loop header executes if the loop exits
724 /// prematurely via another branch.
725 unsigned getSmallConstantTripCount(const Loop *L, BasicBlock *ExitingBlock);
727 /// Returns the upper bound of the loop trip count as a normal unsigned
729 /// Returns 0 if the trip count is unknown or not constant.
730 unsigned getSmallConstantMaxTripCount(const Loop *L);
732 /// Returns the largest constant divisor of the trip count of the
733 /// loop if it is a single-exit loop and we can compute a small maximum for
736 /// Implemented in terms of the \c getSmallConstantTripMultiple overload with
737 /// the single exiting block passed to it. See that routine for details.
738 unsigned getSmallConstantTripMultiple(const Loop *L);
740 /// Returns the largest constant divisor of the trip count of this loop as a
741 /// normal unsigned value, if possible. This means that the actual trip
742 /// count is always a multiple of the returned value (don't forget the trip
743 /// count could very well be zero as well!). As explained in the comments
744 /// for getSmallConstantTripCount, this assumes that control exits the loop
745 /// via ExitingBlock.
746 unsigned getSmallConstantTripMultiple(const Loop *L,
747 BasicBlock *ExitingBlock);
749 /// Return the number of times the backedge executes before the given exit
750 /// would be taken; if not exactly computable, return SCEVCouldNotCompute.
751 /// For a single exit loop, this value is equivelent to the result of
752 /// getBackedgeTakenCount. The loop is guaranteed to exit (via *some* exit)
753 /// before the backedge is executed (ExitCount + 1) times. Note that there
754 /// is no guarantee about *which* exit is taken on the exiting iteration.
755 const SCEV *getExitCount(const Loop *L, BasicBlock *ExitingBlock);
757 /// If the specified loop has a predictable backedge-taken count, return it,
758 /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count is
759 /// the number of times the loop header will be branched to from within the
760 /// loop, assuming there are no abnormal exists like exception throws. This is
761 /// one less than the trip count of the loop, since it doesn't count the first
762 /// iteration, when the header is branched to from outside the loop.
764 /// Note that it is not valid to call this method on a loop without a
765 /// loop-invariant backedge-taken count (see
766 /// hasLoopInvariantBackedgeTakenCount).
767 const SCEV *getBackedgeTakenCount(const Loop *L);
769 /// Similar to getBackedgeTakenCount, except it will add a set of
770 /// SCEV predicates to Predicates that are required to be true in order for
771 /// the answer to be correct. Predicates can be checked with run-time
772 /// checks and can be used to perform loop versioning.
773 const SCEV *getPredicatedBackedgeTakenCount(const Loop *L,
774 SCEVUnionPredicate &Predicates);
776 /// When successful, this returns a SCEVConstant that is greater than or equal
777 /// to (i.e. a "conservative over-approximation") of the value returend by
778 /// getBackedgeTakenCount. If such a value cannot be computed, it returns the
779 /// SCEVCouldNotCompute object.
780 const SCEV *getMaxBackedgeTakenCount(const Loop *L);
782 /// Return true if the backedge taken count is either the value returned by
783 /// getMaxBackedgeTakenCount or zero.
784 bool isBackedgeTakenCountMaxOrZero(const Loop *L);
786 /// Return true if the specified loop has an analyzable loop-invariant
787 /// backedge-taken count.
788 bool hasLoopInvariantBackedgeTakenCount(const Loop *L);
790 // This method should be called by the client when it made any change that
791 // would invalidate SCEV's answers, and the client wants to remove all loop
792 // information held internally by ScalarEvolution. This is intended to be used
793 // when the alternative to forget a loop is too expensive (i.e. large loop
795 void forgetAllLoops();
797 /// This method should be called by the client when it has changed a loop in
798 /// a way that may effect ScalarEvolution's ability to compute a trip count,
799 /// or if the loop is deleted. This call is potentially expensive for large
801 void forgetLoop(const Loop *L);
803 // This method invokes forgetLoop for the outermost loop of the given loop
804 // \p L, making ScalarEvolution forget about all this subtree. This needs to
805 // be done whenever we make a transform that may affect the parameters of the
806 // outer loop, such as exit counts for branches.
807 void forgetTopmostLoop(const Loop *L);
809 /// This method should be called by the client when it has changed a value
810 /// in a way that may effect its value, or which may disconnect it from a
811 /// def-use chain linking it to a loop.
812 void forgetValue(Value *V);
814 /// Called when the client has changed the disposition of values in
817 /// We don't have a way to invalidate per-loop dispositions. Clear and
818 /// recompute is simpler.
819 void forgetLoopDispositions(const Loop *L) { LoopDispositions.clear(); }
821 /// Determine the minimum number of zero bits that S is guaranteed to end in
822 /// (at every loop iteration). It is, at the same time, the minimum number
823 /// of times S is divisible by 2. For example, given {4,+,8} it returns 2.
824 /// If S is guaranteed to be 0, it returns the bitwidth of S.
825 uint32_t GetMinTrailingZeros(const SCEV *S);
827 /// Determine the unsigned range for a particular SCEV.
828 /// NOTE: This returns a copy of the reference returned by getRangeRef.
829 ConstantRange getUnsignedRange(const SCEV *S) {
830 return getRangeRef(S, HINT_RANGE_UNSIGNED);
833 /// Determine the min of the unsigned range for a particular SCEV.
834 APInt getUnsignedRangeMin(const SCEV *S) {
835 return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMin();
838 /// Determine the max of the unsigned range for a particular SCEV.
839 APInt getUnsignedRangeMax(const SCEV *S) {
840 return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMax();
843 /// Determine the signed range for a particular SCEV.
844 /// NOTE: This returns a copy of the reference returned by getRangeRef.
845 ConstantRange getSignedRange(const SCEV *S) {
846 return getRangeRef(S, HINT_RANGE_SIGNED);
849 /// Determine the min of the signed range for a particular SCEV.
850 APInt getSignedRangeMin(const SCEV *S) {
851 return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMin();
854 /// Determine the max of the signed range for a particular SCEV.
855 APInt getSignedRangeMax(const SCEV *S) {
856 return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMax();
859 /// Test if the given expression is known to be negative.
860 bool isKnownNegative(const SCEV *S);
862 /// Test if the given expression is known to be positive.
863 bool isKnownPositive(const SCEV *S);
865 /// Test if the given expression is known to be non-negative.
866 bool isKnownNonNegative(const SCEV *S);
868 /// Test if the given expression is known to be non-positive.
869 bool isKnownNonPositive(const SCEV *S);
871 /// Test if the given expression is known to be non-zero.
872 bool isKnownNonZero(const SCEV *S);
874 /// Splits SCEV expression \p S into two SCEVs. One of them is obtained from
875 /// \p S by substitution of all AddRec sub-expression related to loop \p L
876 /// with initial value of that SCEV. The second is obtained from \p S by
877 /// substitution of all AddRec sub-expressions related to loop \p L with post
878 /// increment of this AddRec in the loop \p L. In both cases all other AddRec
879 /// sub-expressions (not related to \p L) remain the same.
880 /// If the \p S contains non-invariant unknown SCEV the function returns
881 /// CouldNotCompute SCEV in both values of std::pair.
882 /// For example, for SCEV S={0, +, 1}<L1> + {0, +, 1}<L2> and loop L=L1
883 /// the function returns pair:
884 /// first = {0, +, 1}<L2>
885 /// second = {1, +, 1}<L1> + {0, +, 1}<L2>
886 /// We can see that for the first AddRec sub-expression it was replaced with
887 /// 0 (initial value) for the first element and to {1, +, 1}<L1> (post
888 /// increment value) for the second one. In both cases AddRec expression
889 /// related to L2 remains the same.
890 std::pair<const SCEV *, const SCEV *> SplitIntoInitAndPostInc(const Loop *L,
893 /// We'd like to check the predicate on every iteration of the most dominated
894 /// loop between loops used in LHS and RHS.
895 /// To do this we use the following list of steps:
896 /// 1. Collect set S all loops on which either LHS or RHS depend.
897 /// 2. If S is non-empty
898 /// a. Let PD be the element of S which is dominated by all other elements.
899 /// b. Let E(LHS) be value of LHS on entry of PD.
900 /// To get E(LHS), we should just take LHS and replace all AddRecs that are
901 /// attached to PD on with their entry values.
902 /// Define E(RHS) in the same way.
903 /// c. Let B(LHS) be value of L on backedge of PD.
904 /// To get B(LHS), we should just take LHS and replace all AddRecs that are
905 /// attached to PD on with their backedge values.
906 /// Define B(RHS) in the same way.
907 /// d. Note that E(LHS) and E(RHS) are automatically available on entry of PD,
908 /// so we can assert on that.
909 /// e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) &&
910 /// isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS))
911 bool isKnownViaInduction(ICmpInst::Predicate Pred, const SCEV *LHS,
914 /// Test if the given expression is known to satisfy the condition described
915 /// by Pred, LHS, and RHS.
916 bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS,
919 /// Test if the condition described by Pred, LHS, RHS is known to be true on
920 /// every iteration of the loop of the recurrency LHS.
921 bool isKnownOnEveryIteration(ICmpInst::Predicate Pred,
922 const SCEVAddRecExpr *LHS, const SCEV *RHS);
924 /// Return true if, for all loop invariant X, the predicate "LHS `Pred` X"
925 /// is monotonically increasing or decreasing. In the former case set
926 /// `Increasing` to true and in the latter case set `Increasing` to false.
928 /// A predicate is said to be monotonically increasing if may go from being
929 /// false to being true as the loop iterates, but never the other way
930 /// around. A predicate is said to be monotonically decreasing if may go
931 /// from being true to being false as the loop iterates, but never the other
933 bool isMonotonicPredicate(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred,
936 /// Return true if the result of the predicate LHS `Pred` RHS is loop
937 /// invariant with respect to L. Set InvariantPred, InvariantLHS and
938 /// InvariantLHS so that InvariantLHS `InvariantPred` InvariantRHS is the
939 /// loop invariant form of LHS `Pred` RHS.
940 bool isLoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS,
941 const SCEV *RHS, const Loop *L,
942 ICmpInst::Predicate &InvariantPred,
943 const SCEV *&InvariantLHS,
944 const SCEV *&InvariantRHS);
946 /// Simplify LHS and RHS in a comparison with predicate Pred. Return true
947 /// iff any changes were made. If the operands are provably equal or
948 /// unequal, LHS and RHS are set to the same value and Pred is set to either
949 /// ICMP_EQ or ICMP_NE.
950 bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS,
951 const SCEV *&RHS, unsigned Depth = 0);
953 /// Return the "disposition" of the given SCEV with respect to the given
955 LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L);
957 /// Return true if the value of the given SCEV is unchanging in the
959 bool isLoopInvariant(const SCEV *S, const Loop *L);
961 /// Determine if the SCEV can be evaluated at loop's entry. It is true if it
962 /// doesn't depend on a SCEVUnknown of an instruction which is dominated by
963 /// the header of loop L.
964 bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L);
966 /// Return true if the given SCEV changes value in a known way in the
967 /// specified loop. This property being true implies that the value is
968 /// variant in the loop AND that we can emit an expression to compute the
969 /// value of the expression at any particular loop iteration.
970 bool hasComputableLoopEvolution(const SCEV *S, const Loop *L);
972 /// Return the "disposition" of the given SCEV with respect to the given
974 BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB);
976 /// Return true if elements that makes up the given SCEV dominate the
977 /// specified basic block.
978 bool dominates(const SCEV *S, const BasicBlock *BB);
980 /// Return true if elements that makes up the given SCEV properly dominate
981 /// the specified basic block.
982 bool properlyDominates(const SCEV *S, const BasicBlock *BB);
984 /// Test whether the given SCEV has Op as a direct or indirect operand.
985 bool hasOperand(const SCEV *S, const SCEV *Op) const;
987 /// Return the size of an element read or written by Inst.
988 const SCEV *getElementSize(Instruction *Inst);
990 /// Compute the array dimensions Sizes from the set of Terms extracted from
991 /// the memory access function of this SCEVAddRecExpr (second step of
992 /// delinearization).
993 void findArrayDimensions(SmallVectorImpl<const SCEV *> &Terms,
994 SmallVectorImpl<const SCEV *> &Sizes,
995 const SCEV *ElementSize);
997 void print(raw_ostream &OS) const;
999 bool invalidate(Function &F, const PreservedAnalyses &PA,
1000 FunctionAnalysisManager::Invalidator &Inv);
1002 /// Collect parametric terms occurring in step expressions (first step of
1003 /// delinearization).
1004 void collectParametricTerms(const SCEV *Expr,
1005 SmallVectorImpl<const SCEV *> &Terms);
1007 /// Return in Subscripts the access functions for each dimension in Sizes
1008 /// (third step of delinearization).
1009 void computeAccessFunctions(const SCEV *Expr,
1010 SmallVectorImpl<const SCEV *> &Subscripts,
1011 SmallVectorImpl<const SCEV *> &Sizes);
1013 /// Split this SCEVAddRecExpr into two vectors of SCEVs representing the
1014 /// subscripts and sizes of an array access.
1016 /// The delinearization is a 3 step process: the first two steps compute the
1017 /// sizes of each subscript and the third step computes the access functions
1018 /// for the delinearized array:
1020 /// 1. Find the terms in the step functions
1021 /// 2. Compute the array size
1022 /// 3. Compute the access function: divide the SCEV by the array size
1023 /// starting with the innermost dimensions found in step 2. The Quotient
1024 /// is the SCEV to be divided in the next step of the recursion. The
1025 /// Remainder is the subscript of the innermost dimension. Loop over all
1026 /// array dimensions computed in step 2.
1028 /// To compute a uniform array size for several memory accesses to the same
1029 /// object, one can collect in step 1 all the step terms for all the memory
1030 /// accesses, and compute in step 2 a unique array shape. This guarantees
1031 /// that the array shape will be the same across all memory accesses.
1033 /// FIXME: We could derive the result of steps 1 and 2 from a description of
1034 /// the array shape given in metadata.
1043 /// A[j+k][2i][5i] =
1045 /// The initial SCEV:
1047 /// A[{{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k]
1049 /// 1. Find the different terms in the step functions:
1050 /// -> [2*m, 5, n*m, n*m]
1052 /// 2. Compute the array size: sort and unique them
1053 /// -> [n*m, 2*m, 5]
1054 /// find the GCD of all the terms = 1
1055 /// divide by the GCD and erase constant terms
1058 /// divide by GCD -> [n, 2]
1059 /// remove constant terms
1061 /// size of the array is A[unknown][n][m]
1063 /// 3. Compute the access function
1064 /// a. Divide {{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k by the innermost size m
1065 /// Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k
1066 /// Remainder: {{{0,+,5}_i, +, 0}_j, +, 0}_k
1067 /// The remainder is the subscript of the innermost array dimension: [5i].
1069 /// b. Divide Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k by next outer size n
1070 /// Quotient: {{{0,+,0}_i, +, 1}_j, +, 1}_k
1071 /// Remainder: {{{0,+,2}_i, +, 0}_j, +, 0}_k
1072 /// The Remainder is the subscript of the next array dimension: [2i].
1074 /// The subscript of the outermost dimension is the Quotient: [j+k].
1076 /// Overall, we have: A[][n][m], and the access function: A[j+k][2i][5i].
1077 void delinearize(const SCEV *Expr, SmallVectorImpl<const SCEV *> &Subscripts,
1078 SmallVectorImpl<const SCEV *> &Sizes,
1079 const SCEV *ElementSize);
1081 /// Return the DataLayout associated with the module this SCEV instance is
1083 const DataLayout &getDataLayout() const {
1084 return F.getParent()->getDataLayout();
1087 const SCEVPredicate *getEqualPredicate(const SCEV *LHS, const SCEV *RHS);
1089 const SCEVPredicate *
1090 getWrapPredicate(const SCEVAddRecExpr *AR,
1091 SCEVWrapPredicate::IncrementWrapFlags AddedFlags);
1093 /// Re-writes the SCEV according to the Predicates in \p A.
1094 const SCEV *rewriteUsingPredicate(const SCEV *S, const Loop *L,
1095 SCEVUnionPredicate &A);
1096 /// Tries to convert the \p S expression to an AddRec expression,
1097 /// adding additional predicates to \p Preds as required.
1098 const SCEVAddRecExpr *convertSCEVToAddRecWithPredicates(
1099 const SCEV *S, const Loop *L,
1100 SmallPtrSetImpl<const SCEVPredicate *> &Preds);
1103 /// A CallbackVH to arrange for ScalarEvolution to be notified whenever a
1104 /// Value is deleted.
1105 class SCEVCallbackVH final : public CallbackVH {
1106 ScalarEvolution *SE;
1108 void deleted() override;
1109 void allUsesReplacedWith(Value *New) override;
1112 SCEVCallbackVH(Value *V, ScalarEvolution *SE = nullptr);
1115 friend class SCEVCallbackVH;
1116 friend class SCEVExpander;
1117 friend class SCEVUnknown;
1119 /// The function we are analyzing.
1122 /// Does the module have any calls to the llvm.experimental.guard intrinsic
1123 /// at all? If this is false, we avoid doing work that will only help if
1124 /// thare are guards present in the IR.
1127 /// The target library information for the target we are targeting.
1128 TargetLibraryInfo &TLI;
1130 /// The tracker for \@llvm.assume intrinsics in this function.
1131 AssumptionCache &AC;
1133 /// The dominator tree.
1136 /// The loop information for the function we are currently analyzing.
1139 /// This SCEV is used to represent unknown trip counts and things.
1140 std::unique_ptr<SCEVCouldNotCompute> CouldNotCompute;
1142 /// The type for HasRecMap.
1143 using HasRecMapType = DenseMap<const SCEV *, bool>;
1145 /// This is a cache to record whether a SCEV contains any scAddRecExpr.
1146 HasRecMapType HasRecMap;
1148 /// The type for ExprValueMap.
1149 using ValueOffsetPair = std::pair<Value *, ConstantInt *>;
1150 using ExprValueMapType = DenseMap<const SCEV *, SetVector<ValueOffsetPair>>;
1152 /// ExprValueMap -- This map records the original values from which
1153 /// the SCEV expr is generated from.
1155 /// We want to represent the mapping as SCEV -> ValueOffsetPair instead
1156 /// of SCEV -> Value:
1157 /// Suppose we know S1 expands to V1, and
1160 /// where C_a and C_b are different SCEVConstants. Then we'd like to
1161 /// expand S3 as V1 - C_a + C_b instead of expanding S2 literally.
1162 /// It is helpful when S2 is a complex SCEV expr.
1164 /// In order to do that, we represent ExprValueMap as a mapping from
1165 /// SCEV to ValueOffsetPair. We will save both S1->{V1, 0} and
1166 /// S2->{V1, C_a} into the map when we create SCEV for V1. When S3
1167 /// is expanded, it will first expand S2 to V1 - C_a because of
1168 /// S2->{V1, C_a} in the map, then expand S3 to V1 - C_a + C_b.
1170 /// Note: S->{V, Offset} in the ExprValueMap means S can be expanded
1172 ExprValueMapType ExprValueMap;
1174 /// The type for ValueExprMap.
1175 using ValueExprMapType =
1176 DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *>>;
1178 /// This is a cache of the values we have analyzed so far.
1179 ValueExprMapType ValueExprMap;
1181 /// Mark predicate values currently being processed by isImpliedCond.
1182 SmallPtrSet<Value *, 6> PendingLoopPredicates;
1184 /// Mark SCEVUnknown Phis currently being processed by getRangeRef.
1185 SmallPtrSet<const PHINode *, 6> PendingPhiRanges;
1187 // Mark SCEVUnknown Phis currently being processed by isImpliedViaMerge.
1188 SmallPtrSet<const PHINode *, 6> PendingMerges;
1190 /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of
1191 /// conditions dominating the backedge of a loop.
1192 bool WalkingBEDominatingConds = false;
1194 /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a
1195 /// predicate by splitting it into a set of independent predicates.
1196 bool ProvingSplitPredicate = false;
1198 /// Memoized values for the GetMinTrailingZeros
1199 DenseMap<const SCEV *, uint32_t> MinTrailingZerosCache;
1201 /// Return the Value set from which the SCEV expr is generated.
1202 SetVector<ValueOffsetPair> *getSCEVValues(const SCEV *S);
1204 /// Private helper method for the GetMinTrailingZeros method
1205 uint32_t GetMinTrailingZerosImpl(const SCEV *S);
1207 /// Information about the number of loop iterations for which a loop exit's
1208 /// branch condition evaluates to the not-taken path. This is a temporary
1209 /// pair of exact and max expressions that are eventually summarized in
1210 /// ExitNotTakenInfo and BackedgeTakenInfo.
1212 const SCEV *ExactNotTaken; // The exit is not taken exactly this many times
1213 const SCEV *MaxNotTaken; // The exit is not taken at most this many times
1215 // Not taken either exactly MaxNotTaken or zero times
1216 bool MaxOrZero = false;
1218 /// A set of predicate guards for this ExitLimit. The result is only valid
1219 /// if all of the predicates in \c Predicates evaluate to 'true' at
1221 SmallPtrSet<const SCEVPredicate *, 4> Predicates;
1223 void addPredicate(const SCEVPredicate *P) {
1224 assert(!isa<SCEVUnionPredicate>(P) && "Only add leaf predicates here!");
1225 Predicates.insert(P);
1228 /*implicit*/ ExitLimit(const SCEV *E);
1231 const SCEV *E, const SCEV *M, bool MaxOrZero,
1232 ArrayRef<const SmallPtrSetImpl<const SCEVPredicate *> *> PredSetList);
1234 ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero,
1235 const SmallPtrSetImpl<const SCEVPredicate *> &PredSet);
1237 ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero);
1239 /// Test whether this ExitLimit contains any computed information, or
1240 /// whether it's all SCEVCouldNotCompute values.
1241 bool hasAnyInfo() const {
1242 return !isa<SCEVCouldNotCompute>(ExactNotTaken) ||
1243 !isa<SCEVCouldNotCompute>(MaxNotTaken);
1246 bool hasOperand(const SCEV *S) const;
1248 /// Test whether this ExitLimit contains all information.
1249 bool hasFullInfo() const {
1250 return !isa<SCEVCouldNotCompute>(ExactNotTaken);
1254 /// Information about the number of times a particular loop exit may be
1255 /// reached before exiting the loop.
1256 struct ExitNotTakenInfo {
1257 PoisoningVH<BasicBlock> ExitingBlock;
1258 const SCEV *ExactNotTaken;
1259 std::unique_ptr<SCEVUnionPredicate> Predicate;
1261 explicit ExitNotTakenInfo(PoisoningVH<BasicBlock> ExitingBlock,
1262 const SCEV *ExactNotTaken,
1263 std::unique_ptr<SCEVUnionPredicate> Predicate)
1264 : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken),
1265 Predicate(std::move(Predicate)) {}
1267 bool hasAlwaysTruePredicate() const {
1268 return !Predicate || Predicate->isAlwaysTrue();
1272 /// Information about the backedge-taken count of a loop. This currently
1273 /// includes an exact count and a maximum count.
1275 class BackedgeTakenInfo {
1276 /// A list of computable exits and their not-taken counts. Loops almost
1277 /// never have more than one computable exit.
1278 SmallVector<ExitNotTakenInfo, 1> ExitNotTaken;
1280 /// The pointer part of \c MaxAndComplete is an expression indicating the
1281 /// least maximum backedge-taken count of the loop that is known, or a
1282 /// SCEVCouldNotCompute. This expression is only valid if the predicates
1283 /// associated with all loop exits are true.
1285 /// The integer part of \c MaxAndComplete is a boolean indicating if \c
1286 /// ExitNotTaken has an element for every exiting block in the loop.
1287 PointerIntPair<const SCEV *, 1> MaxAndComplete;
1289 /// True iff the backedge is taken either exactly Max or zero times.
1290 bool MaxOrZero = false;
1292 /// \name Helper projection functions on \c MaxAndComplete.
1294 bool isComplete() const { return MaxAndComplete.getInt(); }
1295 const SCEV *getMax() const { return MaxAndComplete.getPointer(); }
1299 BackedgeTakenInfo() : MaxAndComplete(nullptr, 0) {}
1300 BackedgeTakenInfo(BackedgeTakenInfo &&) = default;
1301 BackedgeTakenInfo &operator=(BackedgeTakenInfo &&) = default;
1303 using EdgeExitInfo = std::pair<BasicBlock *, ExitLimit>;
1305 /// Initialize BackedgeTakenInfo from a list of exact exit counts.
1306 BackedgeTakenInfo(ArrayRef<EdgeExitInfo> ExitCounts, bool Complete,
1307 const SCEV *MaxCount, bool MaxOrZero);
1309 /// Test whether this BackedgeTakenInfo contains any computed information,
1310 /// or whether it's all SCEVCouldNotCompute values.
1311 bool hasAnyInfo() const {
1312 return !ExitNotTaken.empty() || !isa<SCEVCouldNotCompute>(getMax());
1315 /// Test whether this BackedgeTakenInfo contains complete information.
1316 bool hasFullInfo() const { return isComplete(); }
1318 /// Return an expression indicating the exact *backedge-taken*
1319 /// count of the loop if it is known or SCEVCouldNotCompute
1320 /// otherwise. If execution makes it to the backedge on every
1321 /// iteration (i.e. there are no abnormal exists like exception
1322 /// throws and thread exits) then this is the number of times the
1323 /// loop header will execute minus one.
1325 /// If the SCEV predicate associated with the answer can be different
1326 /// from AlwaysTrue, we must add a (non null) Predicates argument.
1327 /// The SCEV predicate associated with the answer will be added to
1328 /// Predicates. A run-time check needs to be emitted for the SCEV
1329 /// predicate in order for the answer to be valid.
1331 /// Note that we should always know if we need to pass a predicate
1332 /// argument or not from the way the ExitCounts vector was computed.
1333 /// If we allowed SCEV predicates to be generated when populating this
1334 /// vector, this information can contain them and therefore a
1335 /// SCEVPredicate argument should be added to getExact.
1336 const SCEV *getExact(const Loop *L, ScalarEvolution *SE,
1337 SCEVUnionPredicate *Predicates = nullptr) const;
1339 /// Return the number of times this loop exit may fall through to the back
1340 /// edge, or SCEVCouldNotCompute. The loop is guaranteed not to exit via
1341 /// this block before this number of iterations, but may exit via another
1343 const SCEV *getExact(BasicBlock *ExitingBlock, ScalarEvolution *SE) const;
1345 /// Get the max backedge taken count for the loop.
1346 const SCEV *getMax(ScalarEvolution *SE) const;
1348 /// Return true if the number of times this backedge is taken is either the
1349 /// value returned by getMax or zero.
1350 bool isMaxOrZero(ScalarEvolution *SE) const;
1352 /// Return true if any backedge taken count expressions refer to the given
1354 bool hasOperand(const SCEV *S, ScalarEvolution *SE) const;
1356 /// Invalidate this result and free associated memory.
1360 /// Cache the backedge-taken count of the loops for this function as they
1362 DenseMap<const Loop *, BackedgeTakenInfo> BackedgeTakenCounts;
1364 /// Cache the predicated backedge-taken count of the loops for this
1365 /// function as they are computed.
1366 DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts;
1368 /// This map contains entries for all of the PHI instructions that we
1369 /// attempt to compute constant evolutions for. This allows us to avoid
1370 /// potentially expensive recomputation of these properties. An instruction
1371 /// maps to null if we are unable to compute its exit value.
1372 DenseMap<PHINode *, Constant *> ConstantEvolutionLoopExitValue;
1374 /// This map contains entries for all the expressions that we attempt to
1375 /// compute getSCEVAtScope information for, which can be expensive in
1377 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1380 /// Memoized computeLoopDisposition results.
1381 DenseMap<const SCEV *,
1382 SmallVector<PointerIntPair<const Loop *, 2, LoopDisposition>, 2>>
1385 struct LoopProperties {
1386 /// Set to true if the loop contains no instruction that can have side
1387 /// effects (i.e. via throwing an exception, volatile or atomic access).
1388 bool HasNoAbnormalExits;
1390 /// Set to true if the loop contains no instruction that can abnormally exit
1391 /// the loop (i.e. via throwing an exception, by terminating the thread
1392 /// cleanly or by infinite looping in a called function). Strictly
1393 /// speaking, the last one is not leaving the loop, but is identical to
1394 /// leaving the loop for reasoning about undefined behavior.
1395 bool HasNoSideEffects;
1398 /// Cache for \c getLoopProperties.
1399 DenseMap<const Loop *, LoopProperties> LoopPropertiesCache;
1401 /// Return a \c LoopProperties instance for \p L, creating one if necessary.
1402 LoopProperties getLoopProperties(const Loop *L);
1404 bool loopHasNoSideEffects(const Loop *L) {
1405 return getLoopProperties(L).HasNoSideEffects;
1408 bool loopHasNoAbnormalExits(const Loop *L) {
1409 return getLoopProperties(L).HasNoAbnormalExits;
1412 /// Compute a LoopDisposition value.
1413 LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L);
1415 /// Memoized computeBlockDisposition results.
1418 SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>>
1421 /// Compute a BlockDisposition value.
1422 BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB);
1424 /// Memoized results from getRange
1425 DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
1427 /// Memoized results from getRange
1428 DenseMap<const SCEV *, ConstantRange> SignedRanges;
1430 /// Used to parameterize getRange
1431 enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED };
1433 /// Set the memoized range for the given SCEV.
1434 const ConstantRange &setRange(const SCEV *S, RangeSignHint Hint,
1436 DenseMap<const SCEV *, ConstantRange> &Cache =
1437 Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges;
1439 auto Pair = Cache.try_emplace(S, std::move(CR));
1441 Pair.first->second = std::move(CR);
1442 return Pair.first->second;
1445 /// Determine the range for a particular SCEV.
1446 /// NOTE: This returns a reference to an entry in a cache. It must be
1447 /// copied if its needed for longer.
1448 const ConstantRange &getRangeRef(const SCEV *S, RangeSignHint Hint);
1450 /// Determines the range for the affine SCEVAddRecExpr {\p Start,+,\p Stop}.
1451 /// Helper for \c getRange.
1452 ConstantRange getRangeForAffineAR(const SCEV *Start, const SCEV *Stop,
1453 const SCEV *MaxBECount, unsigned BitWidth);
1455 /// Try to compute a range for the affine SCEVAddRecExpr {\p Start,+,\p
1456 /// Stop} by "factoring out" a ternary expression from the add recurrence.
1457 /// Helper called by \c getRange.
1458 ConstantRange getRangeViaFactoring(const SCEV *Start, const SCEV *Stop,
1459 const SCEV *MaxBECount, unsigned BitWidth);
1461 /// We know that there is no SCEV for the specified value. Analyze the
1463 const SCEV *createSCEV(Value *V);
1465 /// Provide the special handling we need to analyze PHI SCEVs.
1466 const SCEV *createNodeForPHI(PHINode *PN);
1468 /// Helper function called from createNodeForPHI.
1469 const SCEV *createAddRecFromPHI(PHINode *PN);
1471 /// A helper function for createAddRecFromPHI to handle simple cases.
1472 const SCEV *createSimpleAffineAddRec(PHINode *PN, Value *BEValueV,
1473 Value *StartValueV);
1475 /// Helper function called from createNodeForPHI.
1476 const SCEV *createNodeFromSelectLikePHI(PHINode *PN);
1478 /// Provide special handling for a select-like instruction (currently this
1479 /// is either a select instruction or a phi node). \p I is the instruction
1480 /// being processed, and it is assumed equivalent to "Cond ? TrueVal :
1482 const SCEV *createNodeForSelectOrPHI(Instruction *I, Value *Cond,
1483 Value *TrueVal, Value *FalseVal);
1485 /// Provide the special handling we need to analyze GEP SCEVs.
1486 const SCEV *createNodeForGEP(GEPOperator *GEP);
1488 /// Implementation code for getSCEVAtScope; called at most once for each
1490 const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L);
1492 /// This looks up computed SCEV values for all instructions that depend on
1493 /// the given instruction and removes them from the ValueExprMap map if they
1494 /// reference SymName. This is used during PHI resolution.
1495 void forgetSymbolicName(Instruction *I, const SCEV *SymName);
1497 /// Return the BackedgeTakenInfo for the given loop, lazily computing new
1498 /// values if the loop hasn't been analyzed yet. The returned result is
1499 /// guaranteed not to be predicated.
1500 const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L);
1502 /// Similar to getBackedgeTakenInfo, but will add predicates as required
1503 /// with the purpose of returning complete information.
1504 const BackedgeTakenInfo &getPredicatedBackedgeTakenInfo(const Loop *L);
1506 /// Compute the number of times the specified loop will iterate.
1507 /// If AllowPredicates is set, we will create new SCEV predicates as
1508 /// necessary in order to return an exact answer.
1509 BackedgeTakenInfo computeBackedgeTakenCount(const Loop *L,
1510 bool AllowPredicates = false);
1512 /// Compute the number of times the backedge of the specified loop will
1513 /// execute if it exits via the specified block. If AllowPredicates is set,
1514 /// this call will try to use a minimal set of SCEV predicates in order to
1515 /// return an exact answer.
1516 ExitLimit computeExitLimit(const Loop *L, BasicBlock *ExitingBlock,
1517 bool AllowPredicates = false);
1519 /// Compute the number of times the backedge of the specified loop will
1520 /// execute if its exit condition were a conditional branch of ExitCond.
1522 /// \p ControlsExit is true if ExitCond directly controls the exit
1523 /// branch. In this case, we can assume that the loop exits only if the
1524 /// condition is true and can infer that failing to meet the condition prior
1525 /// to integer wraparound results in undefined behavior.
1527 /// If \p AllowPredicates is set, this call will try to use a minimal set of
1528 /// SCEV predicates in order to return an exact answer.
1529 ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond,
1530 bool ExitIfTrue, bool ControlsExit,
1531 bool AllowPredicates = false);
1533 // Helper functions for computeExitLimitFromCond to avoid exponential time
1536 class ExitLimitCache {
1537 // It may look like we need key on the whole (L, ExitIfTrue, ControlsExit,
1538 // AllowPredicates) tuple, but recursive calls to
1539 // computeExitLimitFromCondCached from computeExitLimitFromCondImpl only
1540 // vary the in \c ExitCond and \c ControlsExit parameters. We remember the
1541 // initial values of the other values to assert our assumption.
1542 SmallDenseMap<PointerIntPair<Value *, 1>, ExitLimit> TripCountMap;
1546 bool AllowPredicates;
1549 ExitLimitCache(const Loop *L, bool ExitIfTrue, bool AllowPredicates)
1550 : L(L), ExitIfTrue(ExitIfTrue), AllowPredicates(AllowPredicates) {}
1552 Optional<ExitLimit> find(const Loop *L, Value *ExitCond, bool ExitIfTrue,
1553 bool ControlsExit, bool AllowPredicates);
1555 void insert(const Loop *L, Value *ExitCond, bool ExitIfTrue,
1556 bool ControlsExit, bool AllowPredicates, const ExitLimit &EL);
1559 using ExitLimitCacheTy = ExitLimitCache;
1561 ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache,
1562 const Loop *L, Value *ExitCond,
1565 bool AllowPredicates);
1566 ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache, const Loop *L,
1567 Value *ExitCond, bool ExitIfTrue,
1569 bool AllowPredicates);
1571 /// Compute the number of times the backedge of the specified loop will
1572 /// execute if its exit condition were a conditional branch of the ICmpInst
1573 /// ExitCond and ExitIfTrue. If AllowPredicates is set, this call will try
1574 /// to use a minimal set of SCEV predicates in order to return an exact
1576 ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond,
1579 bool AllowPredicates = false);
1581 /// Compute the number of times the backedge of the specified loop will
1582 /// execute if its exit condition were a switch with a single exiting case
1584 ExitLimit computeExitLimitFromSingleExitSwitch(const Loop *L,
1586 BasicBlock *ExitingBB,
1589 /// Given an exit condition of 'icmp op load X, cst', try to see if we can
1590 /// compute the backedge-taken count.
1591 ExitLimit computeLoadConstantCompareExitLimit(LoadInst *LI, Constant *RHS,
1593 ICmpInst::Predicate p);
1595 /// Compute the exit limit of a loop that is controlled by a
1596 /// "(IV >> 1) != 0" type comparison. We cannot compute the exact trip
1597 /// count in these cases (since SCEV has no way of expressing them), but we
1598 /// can still sometimes compute an upper bound.
1600 /// Return an ExitLimit for a loop whose backedge is guarded by `LHS Pred
1602 ExitLimit computeShiftCompareExitLimit(Value *LHS, Value *RHS, const Loop *L,
1603 ICmpInst::Predicate Pred);
1605 /// If the loop is known to execute a constant number of times (the
1606 /// condition evolves only from constants), try to evaluate a few iterations
1607 /// of the loop until we get the exit condition gets a value of ExitWhen
1608 /// (true or false). If we cannot evaluate the exit count of the loop,
1609 /// return CouldNotCompute.
1610 const SCEV *computeExitCountExhaustively(const Loop *L, Value *Cond,
1613 /// Return the number of times an exit condition comparing the specified
1614 /// value to zero will execute. If not computable, return CouldNotCompute.
1615 /// If AllowPredicates is set, this call will try to use a minimal set of
1616 /// SCEV predicates in order to return an exact answer.
1617 ExitLimit howFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr,
1618 bool AllowPredicates = false);
1620 /// Return the number of times an exit condition checking the specified
1621 /// value for nonzero will execute. If not computable, return
1622 /// CouldNotCompute.
1623 ExitLimit howFarToNonZero(const SCEV *V, const Loop *L);
1625 /// Return the number of times an exit condition containing the specified
1626 /// less-than comparison will execute. If not computable, return
1627 /// CouldNotCompute.
1629 /// \p isSigned specifies whether the less-than is signed.
1631 /// \p ControlsExit is true when the LHS < RHS condition directly controls
1632 /// the branch (loops exits only if condition is true). In this case, we can
1633 /// use NoWrapFlags to skip overflow checks.
1635 /// If \p AllowPredicates is set, this call will try to use a minimal set of
1636 /// SCEV predicates in order to return an exact answer.
1637 ExitLimit howManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
1638 bool isSigned, bool ControlsExit,
1639 bool AllowPredicates = false);
1641 ExitLimit howManyGreaterThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
1642 bool isSigned, bool IsSubExpr,
1643 bool AllowPredicates = false);
1645 /// Return a predecessor of BB (which may not be an immediate predecessor)
1646 /// which has exactly one successor from which BB is reachable, or null if
1647 /// no such block is found.
1648 std::pair<BasicBlock *, BasicBlock *>
1649 getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB);
1651 /// Test whether the condition described by Pred, LHS, and RHS is true
1652 /// whenever the given FoundCondValue value evaluates to true.
1653 bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
1654 Value *FoundCondValue, bool Inverse);
1656 /// Test whether the condition described by Pred, LHS, and RHS is true
1657 /// whenever the condition described by FoundPred, FoundLHS, FoundRHS is
1659 bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
1660 ICmpInst::Predicate FoundPred, const SCEV *FoundLHS,
1661 const SCEV *FoundRHS);
1663 /// Test whether the condition described by Pred, LHS, and RHS is true
1664 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1666 bool isImpliedCondOperands(ICmpInst::Predicate Pred, const SCEV *LHS,
1667 const SCEV *RHS, const SCEV *FoundLHS,
1668 const SCEV *FoundRHS);
1670 /// Test whether the condition described by Pred, LHS, and RHS is true
1671 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1672 /// true. Here LHS is an operation that includes FoundLHS as one of its
1674 bool isImpliedViaOperations(ICmpInst::Predicate Pred,
1675 const SCEV *LHS, const SCEV *RHS,
1676 const SCEV *FoundLHS, const SCEV *FoundRHS,
1677 unsigned Depth = 0);
1679 /// Test whether the condition described by Pred, LHS, and RHS is true.
1680 /// Use only simple non-recursive types of checks, such as range analysis etc.
1681 bool isKnownViaNonRecursiveReasoning(ICmpInst::Predicate Pred,
1682 const SCEV *LHS, const SCEV *RHS);
1684 /// Test whether the condition described by Pred, LHS, and RHS is true
1685 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1687 bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, const SCEV *LHS,
1688 const SCEV *RHS, const SCEV *FoundLHS,
1689 const SCEV *FoundRHS);
1691 /// Test whether the condition described by Pred, LHS, and RHS is true
1692 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1693 /// true. Utility function used by isImpliedCondOperands. Tries to get
1694 /// cases like "X `sgt` 0 => X - 1 `sgt` -1".
1695 bool isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred, const SCEV *LHS,
1696 const SCEV *RHS, const SCEV *FoundLHS,
1697 const SCEV *FoundRHS);
1699 /// Return true if the condition denoted by \p LHS \p Pred \p RHS is implied
1700 /// by a call to \c @llvm.experimental.guard in \p BB.
1701 bool isImpliedViaGuard(BasicBlock *BB, ICmpInst::Predicate Pred,
1702 const SCEV *LHS, const SCEV *RHS);
1704 /// Test whether the condition described by Pred, LHS, and RHS is true
1705 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1708 /// This routine tries to rule out certain kinds of integer overflow, and
1709 /// then tries to reason about arithmetic properties of the predicates.
1710 bool isImpliedCondOperandsViaNoOverflow(ICmpInst::Predicate Pred,
1711 const SCEV *LHS, const SCEV *RHS,
1712 const SCEV *FoundLHS,
1713 const SCEV *FoundRHS);
1715 /// Test whether the condition described by Pred, LHS, and RHS is true
1716 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1719 /// This routine tries to figure out predicate for Phis which are SCEVUnknown
1720 /// if it is true for every possible incoming value from their respective
1722 bool isImpliedViaMerge(ICmpInst::Predicate Pred,
1723 const SCEV *LHS, const SCEV *RHS,
1724 const SCEV *FoundLHS, const SCEV *FoundRHS,
1727 /// If we know that the specified Phi is in the header of its containing
1728 /// loop, we know the loop executes a constant number of times, and the PHI
1729 /// node is just a recurrence involving constants, fold it.
1730 Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt &BEs,
1733 /// Test if the given expression is known to satisfy the condition described
1734 /// by Pred and the known constant ranges of LHS and RHS.
1735 bool isKnownPredicateViaConstantRanges(ICmpInst::Predicate Pred,
1736 const SCEV *LHS, const SCEV *RHS);
1738 /// Try to prove the condition described by "LHS Pred RHS" by ruling out
1739 /// integer overflow.
1741 /// For instance, this will return true for "A s< (A + C)<nsw>" if C is
1743 bool isKnownPredicateViaNoOverflow(ICmpInst::Predicate Pred, const SCEV *LHS,
1746 /// Try to split Pred LHS RHS into logical conjunctions (and's) and try to
1747 /// prove them individually.
1748 bool isKnownPredicateViaSplitting(ICmpInst::Predicate Pred, const SCEV *LHS,
1751 /// Try to match the Expr as "(L + R)<Flags>".
1752 bool splitBinaryAdd(const SCEV *Expr, const SCEV *&L, const SCEV *&R,
1753 SCEV::NoWrapFlags &Flags);
1755 /// Compute \p LHS - \p RHS and returns the result as an APInt if it is a
1756 /// constant, and None if it isn't.
1758 /// This is intended to be a cheaper version of getMinusSCEV. We can be
1759 /// frugal here since we just bail out of actually constructing and
1760 /// canonicalizing an expression in the cases where the result isn't going
1761 /// to be a constant.
1762 Optional<APInt> computeConstantDifference(const SCEV *LHS, const SCEV *RHS);
1764 /// Drop memoized information computed for S.
1765 void forgetMemoizedResults(const SCEV *S);
1767 /// Return an existing SCEV for V if there is one, otherwise return nullptr.
1768 const SCEV *getExistingSCEV(Value *V);
1770 /// Return false iff given SCEV contains a SCEVUnknown with NULL value-
1772 bool checkValidity(const SCEV *S) const;
1774 /// Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be
1775 /// equal to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}. This is
1776 /// equivalent to proving no signed (resp. unsigned) wrap in
1777 /// {`Start`,+,`Step`} if `ExtendOpTy` is `SCEVSignExtendExpr`
1778 /// (resp. `SCEVZeroExtendExpr`).
1779 template <typename ExtendOpTy>
1780 bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step,
1783 /// Try to prove NSW or NUW on \p AR relying on ConstantRange manipulation.
1784 SCEV::NoWrapFlags proveNoWrapViaConstantRanges(const SCEVAddRecExpr *AR);
1786 bool isMonotonicPredicateImpl(const SCEVAddRecExpr *LHS,
1787 ICmpInst::Predicate Pred, bool &Increasing);
1789 /// Return SCEV no-wrap flags that can be proven based on reasoning about
1790 /// how poison produced from no-wrap flags on this value (e.g. a nuw add)
1791 /// would trigger undefined behavior on overflow.
1792 SCEV::NoWrapFlags getNoWrapFlagsFromUB(const Value *V);
1794 /// Return true if the SCEV corresponding to \p I is never poison. Proving
1795 /// this is more complex than proving that just \p I is never poison, since
1796 /// SCEV commons expressions across control flow, and you can have cases
1800 /// ptr[idx0] = 100;
1801 /// if (<condition>) {
1802 /// idx1 = a +nsw b;
1803 /// ptr[idx1] = 200;
1806 /// where the SCEV expression (+ a b) is guaranteed to not be poison (and
1807 /// hence not sign-overflow) only if "<condition>" is true. Since both
1808 /// `idx0` and `idx1` will be mapped to the same SCEV expression, (+ a b),
1809 /// it is not okay to annotate (+ a b) with <nsw> in the above example.
1810 bool isSCEVExprNeverPoison(const Instruction *I);
1812 /// This is like \c isSCEVExprNeverPoison but it specifically works for
1813 /// instructions that will get mapped to SCEV add recurrences. Return true
1814 /// if \p I will never generate poison under the assumption that \p I is an
1815 /// add recurrence on the loop \p L.
1816 bool isAddRecNeverPoison(const Instruction *I, const Loop *L);
1818 /// Similar to createAddRecFromPHI, but with the additional flexibility of
1819 /// suggesting runtime overflow checks in case casts are encountered.
1820 /// If successful, the analysis records that for this loop, \p SymbolicPHI,
1821 /// which is the UnknownSCEV currently representing the PHI, can be rewritten
1822 /// into an AddRec, assuming some predicates; The function then returns the
1823 /// AddRec and the predicates as a pair, and caches this pair in
1824 /// PredicatedSCEVRewrites.
1825 /// If the analysis is not successful, a mapping from the \p SymbolicPHI to
1826 /// itself (with no predicates) is recorded, and a nullptr with an empty
1827 /// predicates vector is returned as a pair.
1828 Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
1829 createAddRecFromPHIWithCastsImpl(const SCEVUnknown *SymbolicPHI);
1831 /// Compute the backedge taken count knowing the interval difference, the
1832 /// stride and presence of the equality in the comparison.
1833 const SCEV *computeBECount(const SCEV *Delta, const SCEV *Stride,
1836 /// Compute the maximum backedge count based on the range of values
1837 /// permitted by Start, End, and Stride. This is for loops of the form
1838 /// {Start, +, Stride} LT End.
1840 /// Precondition: the induction variable is known to be positive. We *don't*
1841 /// assert these preconditions so please be careful.
1842 const SCEV *computeMaxBECountForLT(const SCEV *Start, const SCEV *Stride,
1843 const SCEV *End, unsigned BitWidth,
1846 /// Verify if an linear IV with positive stride can overflow when in a
1847 /// less-than comparison, knowing the invariant term of the comparison,
1848 /// the stride and the knowledge of NSW/NUW flags on the recurrence.
1849 bool doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, bool IsSigned,
1852 /// Verify if an linear IV with negative stride can overflow when in a
1853 /// greater-than comparison, knowing the invariant term of the comparison,
1854 /// the stride and the knowledge of NSW/NUW flags on the recurrence.
1855 bool doesIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, bool IsSigned,
1858 /// Get add expr already created or create a new one.
1859 const SCEV *getOrCreateAddExpr(ArrayRef<const SCEV *> Ops,
1860 SCEV::NoWrapFlags Flags);
1862 /// Get mul expr already created or create a new one.
1863 const SCEV *getOrCreateMulExpr(ArrayRef<const SCEV *> Ops,
1864 SCEV::NoWrapFlags Flags);
1866 // Get addrec expr already created or create a new one.
1867 const SCEV *getOrCreateAddRecExpr(ArrayRef<const SCEV *> Ops,
1868 const Loop *L, SCEV::NoWrapFlags Flags);
1870 /// Return x if \p Val is f(x) where f is a 1-1 function.
1871 const SCEV *stripInjectiveFunctions(const SCEV *Val) const;
1873 /// Find all of the loops transitively used in \p S, and fill \p LoopsUsed.
1874 /// A loop is considered "used" by an expression if it contains
1875 /// an add rec on said loop.
1876 void getUsedLoops(const SCEV *S, SmallPtrSetImpl<const Loop *> &LoopsUsed);
1878 /// Find all of the loops transitively used in \p S, and update \c LoopUsers
1880 void addToLoopUseLists(const SCEV *S);
1882 /// Try to match the pattern generated by getURemExpr(A, B). If successful,
1883 /// Assign A and B to LHS and RHS, respectively.
1884 bool matchURem(const SCEV *Expr, const SCEV *&LHS, const SCEV *&RHS);
1886 /// Look for a SCEV expression with type `SCEVType` and operands `Ops` in
1889 /// The first component of the returned tuple is the SCEV if found and null
1890 /// otherwise. The second component is the `FoldingSetNodeID` that was
1891 /// constructed to look up the SCEV and the third component is the insertion
1893 std::tuple<const SCEV *, FoldingSetNodeID, void *>
1894 findExistingSCEVInCache(int SCEVType, ArrayRef<const SCEV *> Ops);
1896 FoldingSet<SCEV> UniqueSCEVs;
1897 FoldingSet<SCEVPredicate> UniquePreds;
1898 BumpPtrAllocator SCEVAllocator;
1900 /// This maps loops to a list of SCEV expressions that (transitively) use said
1902 DenseMap<const Loop *, SmallVector<const SCEV *, 4>> LoopUsers;
1904 /// Cache tentative mappings from UnknownSCEVs in a Loop, to a SCEV expression
1905 /// they can be rewritten into under certain predicates.
1906 DenseMap<std::pair<const SCEVUnknown *, const Loop *>,
1907 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
1908 PredicatedSCEVRewrites;
1910 /// The head of a linked list of all SCEVUnknown values that have been
1911 /// allocated. This is used by releaseMemory to locate them all and call
1912 /// their destructors.
1913 SCEVUnknown *FirstUnknown = nullptr;
1916 /// Analysis pass that exposes the \c ScalarEvolution for a function.
1917 class ScalarEvolutionAnalysis
1918 : public AnalysisInfoMixin<ScalarEvolutionAnalysis> {
1919 friend AnalysisInfoMixin<ScalarEvolutionAnalysis>;
1921 static AnalysisKey Key;
1924 using Result = ScalarEvolution;
1926 ScalarEvolution run(Function &F, FunctionAnalysisManager &AM);
1929 /// Printer pass for the \c ScalarEvolutionAnalysis results.
1930 class ScalarEvolutionPrinterPass
1931 : public PassInfoMixin<ScalarEvolutionPrinterPass> {
1935 explicit ScalarEvolutionPrinterPass(raw_ostream &OS) : OS(OS) {}
1937 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
1940 class ScalarEvolutionWrapperPass : public FunctionPass {
1941 std::unique_ptr<ScalarEvolution> SE;
1946 ScalarEvolutionWrapperPass();
1948 ScalarEvolution &getSE() { return *SE; }
1949 const ScalarEvolution &getSE() const { return *SE; }
1951 bool runOnFunction(Function &F) override;
1952 void releaseMemory() override;
1953 void getAnalysisUsage(AnalysisUsage &AU) const override;
1954 void print(raw_ostream &OS, const Module * = nullptr) const override;
1955 void verifyAnalysis() const override;
1958 /// An interface layer with SCEV used to manage how we see SCEV expressions
1959 /// for values in the context of existing predicates. We can add new
1960 /// predicates, but we cannot remove them.
1962 /// This layer has multiple purposes:
1963 /// - provides a simple interface for SCEV versioning.
1964 /// - guarantees that the order of transformations applied on a SCEV
1965 /// expression for a single Value is consistent across two different
1966 /// getSCEV calls. This means that, for example, once we've obtained
1967 /// an AddRec expression for a certain value through expression
1968 /// rewriting, we will continue to get an AddRec expression for that
1970 /// - lowers the number of expression rewrites.
1971 class PredicatedScalarEvolution {
1973 PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L);
1975 const SCEVUnionPredicate &getUnionPredicate() const;
1977 /// Returns the SCEV expression of V, in the context of the current SCEV
1978 /// predicate. The order of transformations applied on the expression of V
1979 /// returned by ScalarEvolution is guaranteed to be preserved, even when
1980 /// adding new predicates.
1981 const SCEV *getSCEV(Value *V);
1983 /// Get the (predicated) backedge count for the analyzed loop.
1984 const SCEV *getBackedgeTakenCount();
1986 /// Adds a new predicate.
1987 void addPredicate(const SCEVPredicate &Pred);
1989 /// Attempts to produce an AddRecExpr for V by adding additional SCEV
1990 /// predicates. If we can't transform the expression into an AddRecExpr we
1991 /// return nullptr and not add additional SCEV predicates to the current
1993 const SCEVAddRecExpr *getAsAddRec(Value *V);
1995 /// Proves that V doesn't overflow by adding SCEV predicate.
1996 void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags);
1998 /// Returns true if we've proved that V doesn't wrap by means of a SCEV
2000 bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags);
2002 /// Returns the ScalarEvolution analysis used.
2003 ScalarEvolution *getSE() const { return &SE; }
2005 /// We need to explicitly define the copy constructor because of FlagsMap.
2006 PredicatedScalarEvolution(const PredicatedScalarEvolution &);
2008 /// Print the SCEV mappings done by the Predicated Scalar Evolution.
2009 /// The printed text is indented by \p Depth.
2010 void print(raw_ostream &OS, unsigned Depth) const;
2012 /// Check if \p AR1 and \p AR2 are equal, while taking into account
2013 /// Equal predicates in Preds.
2014 bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1,
2015 const SCEVAddRecExpr *AR2) const;
2018 /// Increments the version number of the predicate. This needs to be called
2019 /// every time the SCEV predicate changes.
2020 void updateGeneration();
2022 /// Holds a SCEV and the version number of the SCEV predicate used to
2023 /// perform the rewrite of the expression.
2024 using RewriteEntry = std::pair<unsigned, const SCEV *>;
2026 /// Maps a SCEV to the rewrite result of that SCEV at a certain version
2027 /// number. If this number doesn't match the current Generation, we will
2028 /// need to do a rewrite. To preserve the transformation order of previous
2029 /// rewrites, we will rewrite the previous result instead of the original
2031 DenseMap<const SCEV *, RewriteEntry> RewriteMap;
2033 /// Records what NoWrap flags we've added to a Value *.
2034 ValueMap<Value *, SCEVWrapPredicate::IncrementWrapFlags> FlagsMap;
2036 /// The ScalarEvolution analysis.
2037 ScalarEvolution &SE;
2039 /// The analyzed Loop.
2042 /// The SCEVPredicate that forms our context. We will rewrite all
2043 /// expressions assuming that this predicate true.
2044 SCEVUnionPredicate Preds;
2046 /// Marks the version of the SCEV predicate used. When rewriting a SCEV
2047 /// expression we mark it with the version of the predicate. We use this to
2048 /// figure out if the predicate has changed from the last rewrite of the
2049 /// SCEV. If so, we need to perform a new rewrite.
2050 unsigned Generation = 0;
2052 /// The backedge taken count.
2053 const SCEV *BackedgeCount = nullptr;
2056 } // end namespace llvm
2058 #endif // LLVM_ANALYSIS_SCALAREVOLUTION_H