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
{
471 friend class ScalarEvolutionsTest
;
474 /// An enum describing the relationship between a SCEV and a loop.
475 enum LoopDisposition
{
476 LoopVariant
, ///< The SCEV is loop-variant (unknown).
477 LoopInvariant
, ///< The SCEV is loop-invariant.
478 LoopComputable
///< The SCEV varies predictably with the loop.
481 /// An enum describing the relationship between a SCEV and a basic block.
482 enum BlockDisposition
{
483 DoesNotDominateBlock
, ///< The SCEV does not dominate the block.
484 DominatesBlock
, ///< The SCEV dominates the block.
485 ProperlyDominatesBlock
///< The SCEV properly dominates the block.
488 /// Convenient NoWrapFlags manipulation that hides enum casts and is
489 /// visible in the ScalarEvolution name space.
490 LLVM_NODISCARD
static SCEV::NoWrapFlags
maskFlags(SCEV::NoWrapFlags Flags
,
492 return (SCEV::NoWrapFlags
)(Flags
& Mask
);
494 LLVM_NODISCARD
static SCEV::NoWrapFlags
setFlags(SCEV::NoWrapFlags Flags
,
495 SCEV::NoWrapFlags OnFlags
) {
496 return (SCEV::NoWrapFlags
)(Flags
| OnFlags
);
498 LLVM_NODISCARD
static SCEV::NoWrapFlags
499 clearFlags(SCEV::NoWrapFlags Flags
, SCEV::NoWrapFlags OffFlags
) {
500 return (SCEV::NoWrapFlags
)(Flags
& ~OffFlags
);
503 ScalarEvolution(Function
&F
, TargetLibraryInfo
&TLI
, AssumptionCache
&AC
,
504 DominatorTree
&DT
, LoopInfo
&LI
);
505 ScalarEvolution(ScalarEvolution
&&Arg
);
508 LLVMContext
&getContext() const { return F
.getContext(); }
510 /// Test if values of the given type are analyzable within the SCEV
511 /// framework. This primarily includes integer types, and it can optionally
512 /// include pointer types if the ScalarEvolution class has access to
513 /// target-specific information.
514 bool isSCEVable(Type
*Ty
) const;
516 /// Return the size in bits of the specified type, for which isSCEVable must
518 uint64_t getTypeSizeInBits(Type
*Ty
) const;
520 /// Return a type with the same bitwidth as the given type and which
521 /// represents how SCEV will treat the given type, for which isSCEVable must
522 /// return true. For pointer types, this is the pointer-sized integer type.
523 Type
*getEffectiveSCEVType(Type
*Ty
) const;
525 // Returns a wider type among {Ty1, Ty2}.
526 Type
*getWiderType(Type
*Ty1
, Type
*Ty2
) const;
528 /// Return true if the SCEV is a scAddRecExpr or it contains
529 /// scAddRecExpr. The result will be cached in HasRecMap.
530 bool containsAddRecurrence(const SCEV
*S
);
532 /// Erase Value from ValueExprMap and ExprValueMap.
533 void eraseValueFromMap(Value
*V
);
535 /// Return a SCEV expression for the full generality of the specified
537 const SCEV
*getSCEV(Value
*V
);
539 const SCEV
*getConstant(ConstantInt
*V
);
540 const SCEV
*getConstant(const APInt
&Val
);
541 const SCEV
*getConstant(Type
*Ty
, uint64_t V
, bool isSigned
= false);
542 const SCEV
*getTruncateExpr(const SCEV
*Op
, Type
*Ty
, unsigned Depth
= 0);
543 const SCEV
*getZeroExtendExpr(const SCEV
*Op
, Type
*Ty
, unsigned Depth
= 0);
544 const SCEV
*getSignExtendExpr(const SCEV
*Op
, Type
*Ty
, unsigned Depth
= 0);
545 const SCEV
*getAnyExtendExpr(const SCEV
*Op
, Type
*Ty
);
546 const SCEV
*getAddExpr(SmallVectorImpl
<const SCEV
*> &Ops
,
547 SCEV::NoWrapFlags Flags
= SCEV::FlagAnyWrap
,
549 const SCEV
*getAddExpr(const SCEV
*LHS
, const SCEV
*RHS
,
550 SCEV::NoWrapFlags Flags
= SCEV::FlagAnyWrap
,
551 unsigned Depth
= 0) {
552 SmallVector
<const SCEV
*, 2> Ops
= {LHS
, RHS
};
553 return getAddExpr(Ops
, Flags
, Depth
);
555 const SCEV
*getAddExpr(const SCEV
*Op0
, const SCEV
*Op1
, const SCEV
*Op2
,
556 SCEV::NoWrapFlags Flags
= SCEV::FlagAnyWrap
,
557 unsigned Depth
= 0) {
558 SmallVector
<const SCEV
*, 3> Ops
= {Op0
, Op1
, Op2
};
559 return getAddExpr(Ops
, Flags
, Depth
);
561 const SCEV
*getMulExpr(SmallVectorImpl
<const SCEV
*> &Ops
,
562 SCEV::NoWrapFlags Flags
= SCEV::FlagAnyWrap
,
564 const SCEV
*getMulExpr(const SCEV
*LHS
, const SCEV
*RHS
,
565 SCEV::NoWrapFlags Flags
= SCEV::FlagAnyWrap
,
566 unsigned Depth
= 0) {
567 SmallVector
<const SCEV
*, 2> Ops
= {LHS
, RHS
};
568 return getMulExpr(Ops
, Flags
, Depth
);
570 const SCEV
*getMulExpr(const SCEV
*Op0
, const SCEV
*Op1
, const SCEV
*Op2
,
571 SCEV::NoWrapFlags Flags
= SCEV::FlagAnyWrap
,
572 unsigned Depth
= 0) {
573 SmallVector
<const SCEV
*, 3> Ops
= {Op0
, Op1
, Op2
};
574 return getMulExpr(Ops
, Flags
, Depth
);
576 const SCEV
*getUDivExpr(const SCEV
*LHS
, const SCEV
*RHS
);
577 const SCEV
*getUDivExactExpr(const SCEV
*LHS
, const SCEV
*RHS
);
578 const SCEV
*getURemExpr(const SCEV
*LHS
, const SCEV
*RHS
);
579 const SCEV
*getAddRecExpr(const SCEV
*Start
, const SCEV
*Step
, const Loop
*L
,
580 SCEV::NoWrapFlags Flags
);
581 const SCEV
*getAddRecExpr(SmallVectorImpl
<const SCEV
*> &Operands
,
582 const Loop
*L
, SCEV::NoWrapFlags Flags
);
583 const SCEV
*getAddRecExpr(const SmallVectorImpl
<const SCEV
*> &Operands
,
584 const Loop
*L
, SCEV::NoWrapFlags Flags
) {
585 SmallVector
<const SCEV
*, 4> NewOp(Operands
.begin(), Operands
.end());
586 return getAddRecExpr(NewOp
, L
, Flags
);
589 /// Checks if \p SymbolicPHI can be rewritten as an AddRecExpr under some
590 /// Predicates. If successful return these <AddRecExpr, Predicates>;
591 /// The function is intended to be called from PSCEV (the caller will decide
592 /// whether to actually add the predicates and carry out the rewrites).
593 Optional
<std::pair
<const SCEV
*, SmallVector
<const SCEVPredicate
*, 3>>>
594 createAddRecFromPHIWithCasts(const SCEVUnknown
*SymbolicPHI
);
596 /// Returns an expression for a GEP
598 /// \p GEP The GEP. The indices contained in the GEP itself are ignored,
599 /// instead we use IndexExprs.
600 /// \p IndexExprs The expressions for the indices.
601 const SCEV
*getGEPExpr(GEPOperator
*GEP
,
602 const SmallVectorImpl
<const SCEV
*> &IndexExprs
);
603 const SCEV
*getMinMaxExpr(unsigned Kind
,
604 SmallVectorImpl
<const SCEV
*> &Operands
);
605 const SCEV
*getSMaxExpr(const SCEV
*LHS
, const SCEV
*RHS
);
606 const SCEV
*getSMaxExpr(SmallVectorImpl
<const SCEV
*> &Operands
);
607 const SCEV
*getUMaxExpr(const SCEV
*LHS
, const SCEV
*RHS
);
608 const SCEV
*getUMaxExpr(SmallVectorImpl
<const SCEV
*> &Operands
);
609 const SCEV
*getSMinExpr(const SCEV
*LHS
, const SCEV
*RHS
);
610 const SCEV
*getSMinExpr(SmallVectorImpl
<const SCEV
*> &Operands
);
611 const SCEV
*getUMinExpr(const SCEV
*LHS
, const SCEV
*RHS
);
612 const SCEV
*getUMinExpr(SmallVectorImpl
<const SCEV
*> &Operands
);
613 const SCEV
*getUnknown(Value
*V
);
614 const SCEV
*getCouldNotCompute();
616 /// Return a SCEV for the constant 0 of a specific type.
617 const SCEV
*getZero(Type
*Ty
) { return getConstant(Ty
, 0); }
619 /// Return a SCEV for the constant 1 of a specific type.
620 const SCEV
*getOne(Type
*Ty
) { return getConstant(Ty
, 1); }
622 /// Return an expression for sizeof AllocTy that is type IntTy
623 const SCEV
*getSizeOfExpr(Type
*IntTy
, Type
*AllocTy
);
625 /// Return an expression for offsetof on the given field with type IntTy
626 const SCEV
*getOffsetOfExpr(Type
*IntTy
, StructType
*STy
, unsigned FieldNo
);
628 /// Return the SCEV object corresponding to -V.
629 const SCEV
*getNegativeSCEV(const SCEV
*V
,
630 SCEV::NoWrapFlags Flags
= SCEV::FlagAnyWrap
);
632 /// Return the SCEV object corresponding to ~V.
633 const SCEV
*getNotSCEV(const SCEV
*V
);
635 /// Return LHS-RHS. Minus is represented in SCEV as A+B*-1.
636 const SCEV
*getMinusSCEV(const SCEV
*LHS
, const SCEV
*RHS
,
637 SCEV::NoWrapFlags Flags
= SCEV::FlagAnyWrap
,
640 /// Return a SCEV corresponding to a conversion of the input value to the
641 /// specified type. If the type must be extended, it is zero extended.
642 const SCEV
*getTruncateOrZeroExtend(const SCEV
*V
, Type
*Ty
,
645 /// Return a SCEV corresponding to a conversion of the input value to the
646 /// specified type. If the type must be extended, it is sign extended.
647 const SCEV
*getTruncateOrSignExtend(const SCEV
*V
, Type
*Ty
,
650 /// Return a SCEV corresponding to a conversion of the input value to the
651 /// specified type. If the type must be extended, it is zero extended. The
652 /// conversion must not be narrowing.
653 const SCEV
*getNoopOrZeroExtend(const SCEV
*V
, Type
*Ty
);
655 /// Return a SCEV corresponding to a conversion of the input value to the
656 /// specified type. If the type must be extended, it is sign extended. The
657 /// conversion must not be narrowing.
658 const SCEV
*getNoopOrSignExtend(const SCEV
*V
, Type
*Ty
);
660 /// Return a SCEV corresponding to a conversion of the input value to the
661 /// specified type. If the type must be extended, it is extended with
662 /// unspecified bits. The conversion must not be narrowing.
663 const SCEV
*getNoopOrAnyExtend(const SCEV
*V
, Type
*Ty
);
665 /// Return a SCEV corresponding to a conversion of the input value to the
666 /// specified type. The conversion must not be widening.
667 const SCEV
*getTruncateOrNoop(const SCEV
*V
, Type
*Ty
);
669 /// Promote the operands to the wider of the types using zero-extension, and
670 /// then perform a umax operation with them.
671 const SCEV
*getUMaxFromMismatchedTypes(const SCEV
*LHS
, const SCEV
*RHS
);
673 /// Promote the operands to the wider of the types using zero-extension, and
674 /// then perform a umin operation with them.
675 const SCEV
*getUMinFromMismatchedTypes(const SCEV
*LHS
, const SCEV
*RHS
);
677 /// Promote the operands to the wider of the types using zero-extension, and
678 /// then perform a umin operation with them. N-ary function.
679 const SCEV
*getUMinFromMismatchedTypes(SmallVectorImpl
<const SCEV
*> &Ops
);
681 /// Transitively follow the chain of pointer-type operands until reaching a
682 /// SCEV that does not have a single pointer operand. This returns a
683 /// SCEVUnknown pointer for well-formed pointer-type expressions, but corner
685 const SCEV
*getPointerBase(const SCEV
*V
);
687 /// Return a SCEV expression for the specified value at the specified scope
688 /// in the program. The L value specifies a loop nest to evaluate the
689 /// expression at, where null is the top-level or a specified loop is
690 /// immediately inside of the loop.
692 /// This method can be used to compute the exit value for a variable defined
693 /// in a loop by querying what the value will hold in the parent loop.
695 /// In the case that a relevant loop exit value cannot be computed, the
696 /// original value V is returned.
697 const SCEV
*getSCEVAtScope(const SCEV
*S
, const Loop
*L
);
699 /// This is a convenience function which does getSCEVAtScope(getSCEV(V), L).
700 const SCEV
*getSCEVAtScope(Value
*V
, const Loop
*L
);
702 /// Test whether entry to the loop is protected by a conditional between LHS
703 /// and RHS. This is used to help avoid max expressions in loop trip
704 /// counts, and to eliminate casts.
705 bool isLoopEntryGuardedByCond(const Loop
*L
, ICmpInst::Predicate Pred
,
706 const SCEV
*LHS
, const SCEV
*RHS
);
708 /// Test whether the backedge of the loop is protected by a conditional
709 /// between LHS and RHS. This is used to eliminate casts.
710 bool isLoopBackedgeGuardedByCond(const Loop
*L
, ICmpInst::Predicate Pred
,
711 const SCEV
*LHS
, const SCEV
*RHS
);
713 /// Returns the maximum trip count of the loop if it is a single-exit
714 /// loop and we can compute a small maximum for that loop.
716 /// Implemented in terms of the \c getSmallConstantTripCount overload with
717 /// the single exiting block passed to it. See that routine for details.
718 unsigned getSmallConstantTripCount(const Loop
*L
);
720 /// Returns the maximum trip count of this loop as a normal unsigned
721 /// value. Returns 0 if the trip count is unknown or not constant. This
722 /// "trip count" assumes that control exits via ExitingBlock. More
723 /// precisely, it is the number of times that control may reach ExitingBlock
724 /// before taking the branch. For loops with multiple exits, it may not be
725 /// the number times that the loop header executes if the loop exits
726 /// prematurely via another branch.
727 unsigned getSmallConstantTripCount(const Loop
*L
, BasicBlock
*ExitingBlock
);
729 /// Returns the upper bound of the loop trip count as a normal unsigned
731 /// Returns 0 if the trip count is unknown or not constant.
732 unsigned getSmallConstantMaxTripCount(const Loop
*L
);
734 /// Returns the largest constant divisor of the trip count of the
735 /// loop if it is a single-exit loop and we can compute a small maximum for
738 /// Implemented in terms of the \c getSmallConstantTripMultiple overload with
739 /// the single exiting block passed to it. See that routine for details.
740 unsigned getSmallConstantTripMultiple(const Loop
*L
);
742 /// Returns the largest constant divisor of the trip count of this loop as a
743 /// normal unsigned value, if possible. This means that the actual trip
744 /// count is always a multiple of the returned value (don't forget the trip
745 /// count could very well be zero as well!). As explained in the comments
746 /// for getSmallConstantTripCount, this assumes that control exits the loop
747 /// via ExitingBlock.
748 unsigned getSmallConstantTripMultiple(const Loop
*L
,
749 BasicBlock
*ExitingBlock
);
751 /// Return the number of times the backedge executes before the given exit
752 /// would be taken; if not exactly computable, return SCEVCouldNotCompute.
753 /// For a single exit loop, this value is equivelent to the result of
754 /// getBackedgeTakenCount. The loop is guaranteed to exit (via *some* exit)
755 /// before the backedge is executed (ExitCount + 1) times. Note that there
756 /// is no guarantee about *which* exit is taken on the exiting iteration.
757 const SCEV
*getExitCount(const Loop
*L
, BasicBlock
*ExitingBlock
);
759 /// If the specified loop has a predictable backedge-taken count, return it,
760 /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count is
761 /// the number of times the loop header will be branched to from within the
762 /// loop, assuming there are no abnormal exists like exception throws. This is
763 /// one less than the trip count of the loop, since it doesn't count the first
764 /// iteration, when the header is branched to from outside the loop.
766 /// Note that it is not valid to call this method on a loop without a
767 /// loop-invariant backedge-taken count (see
768 /// hasLoopInvariantBackedgeTakenCount).
769 const SCEV
*getBackedgeTakenCount(const Loop
*L
);
771 /// Similar to getBackedgeTakenCount, except it will add a set of
772 /// SCEV predicates to Predicates that are required to be true in order for
773 /// the answer to be correct. Predicates can be checked with run-time
774 /// checks and can be used to perform loop versioning.
775 const SCEV
*getPredicatedBackedgeTakenCount(const Loop
*L
,
776 SCEVUnionPredicate
&Predicates
);
778 /// When successful, this returns a SCEVConstant that is greater than or equal
779 /// to (i.e. a "conservative over-approximation") of the value returend by
780 /// getBackedgeTakenCount. If such a value cannot be computed, it returns the
781 /// SCEVCouldNotCompute object.
782 const SCEV
*getConstantMaxBackedgeTakenCount(const Loop
*L
);
784 /// Return true if the backedge taken count is either the value returned by
785 /// getConstantMaxBackedgeTakenCount or zero.
786 bool isBackedgeTakenCountMaxOrZero(const Loop
*L
);
788 /// Return true if the specified loop has an analyzable loop-invariant
789 /// backedge-taken count.
790 bool hasLoopInvariantBackedgeTakenCount(const Loop
*L
);
792 // This method should be called by the client when it made any change that
793 // would invalidate SCEV's answers, and the client wants to remove all loop
794 // information held internally by ScalarEvolution. This is intended to be used
795 // when the alternative to forget a loop is too expensive (i.e. large loop
797 void forgetAllLoops();
799 /// This method should be called by the client when it has changed a loop in
800 /// a way that may effect ScalarEvolution's ability to compute a trip count,
801 /// or if the loop is deleted. This call is potentially expensive for large
803 void forgetLoop(const Loop
*L
);
805 // This method invokes forgetLoop for the outermost loop of the given loop
806 // \p L, making ScalarEvolution forget about all this subtree. This needs to
807 // be done whenever we make a transform that may affect the parameters of the
808 // outer loop, such as exit counts for branches.
809 void forgetTopmostLoop(const Loop
*L
);
811 /// This method should be called by the client when it has changed a value
812 /// in a way that may effect its value, or which may disconnect it from a
813 /// def-use chain linking it to a loop.
814 void forgetValue(Value
*V
);
816 /// Called when the client has changed the disposition of values in
819 /// We don't have a way to invalidate per-loop dispositions. Clear and
820 /// recompute is simpler.
821 void forgetLoopDispositions(const Loop
*L
) { LoopDispositions
.clear(); }
823 /// Determine the minimum number of zero bits that S is guaranteed to end in
824 /// (at every loop iteration). It is, at the same time, the minimum number
825 /// of times S is divisible by 2. For example, given {4,+,8} it returns 2.
826 /// If S is guaranteed to be 0, it returns the bitwidth of S.
827 uint32_t GetMinTrailingZeros(const SCEV
*S
);
829 /// Determine the unsigned range for a particular SCEV.
830 /// NOTE: This returns a copy of the reference returned by getRangeRef.
831 ConstantRange
getUnsignedRange(const SCEV
*S
) {
832 return getRangeRef(S
, HINT_RANGE_UNSIGNED
);
835 /// Determine the min of the unsigned range for a particular SCEV.
836 APInt
getUnsignedRangeMin(const SCEV
*S
) {
837 return getRangeRef(S
, HINT_RANGE_UNSIGNED
).getUnsignedMin();
840 /// Determine the max of the unsigned range for a particular SCEV.
841 APInt
getUnsignedRangeMax(const SCEV
*S
) {
842 return getRangeRef(S
, HINT_RANGE_UNSIGNED
).getUnsignedMax();
845 /// Determine the signed range for a particular SCEV.
846 /// NOTE: This returns a copy of the reference returned by getRangeRef.
847 ConstantRange
getSignedRange(const SCEV
*S
) {
848 return getRangeRef(S
, HINT_RANGE_SIGNED
);
851 /// Determine the min of the signed range for a particular SCEV.
852 APInt
getSignedRangeMin(const SCEV
*S
) {
853 return getRangeRef(S
, HINT_RANGE_SIGNED
).getSignedMin();
856 /// Determine the max of the signed range for a particular SCEV.
857 APInt
getSignedRangeMax(const SCEV
*S
) {
858 return getRangeRef(S
, HINT_RANGE_SIGNED
).getSignedMax();
861 /// Test if the given expression is known to be negative.
862 bool isKnownNegative(const SCEV
*S
);
864 /// Test if the given expression is known to be positive.
865 bool isKnownPositive(const SCEV
*S
);
867 /// Test if the given expression is known to be non-negative.
868 bool isKnownNonNegative(const SCEV
*S
);
870 /// Test if the given expression is known to be non-positive.
871 bool isKnownNonPositive(const SCEV
*S
);
873 /// Test if the given expression is known to be non-zero.
874 bool isKnownNonZero(const SCEV
*S
);
876 /// Splits SCEV expression \p S into two SCEVs. One of them is obtained from
877 /// \p S by substitution of all AddRec sub-expression related to loop \p L
878 /// with initial value of that SCEV. The second is obtained from \p S by
879 /// substitution of all AddRec sub-expressions related to loop \p L with post
880 /// increment of this AddRec in the loop \p L. In both cases all other AddRec
881 /// sub-expressions (not related to \p L) remain the same.
882 /// If the \p S contains non-invariant unknown SCEV the function returns
883 /// CouldNotCompute SCEV in both values of std::pair.
884 /// For example, for SCEV S={0, +, 1}<L1> + {0, +, 1}<L2> and loop L=L1
885 /// the function returns pair:
886 /// first = {0, +, 1}<L2>
887 /// second = {1, +, 1}<L1> + {0, +, 1}<L2>
888 /// We can see that for the first AddRec sub-expression it was replaced with
889 /// 0 (initial value) for the first element and to {1, +, 1}<L1> (post
890 /// increment value) for the second one. In both cases AddRec expression
891 /// related to L2 remains the same.
892 std::pair
<const SCEV
*, const SCEV
*> SplitIntoInitAndPostInc(const Loop
*L
,
895 /// We'd like to check the predicate on every iteration of the most dominated
896 /// loop between loops used in LHS and RHS.
897 /// To do this we use the following list of steps:
898 /// 1. Collect set S all loops on which either LHS or RHS depend.
899 /// 2. If S is non-empty
900 /// a. Let PD be the element of S which is dominated by all other elements.
901 /// b. Let E(LHS) be value of LHS on entry of PD.
902 /// To get E(LHS), we should just take LHS and replace all AddRecs that are
903 /// attached to PD on with their entry values.
904 /// Define E(RHS) in the same way.
905 /// c. Let B(LHS) be value of L on backedge of PD.
906 /// To get B(LHS), we should just take LHS and replace all AddRecs that are
907 /// attached to PD on with their backedge values.
908 /// Define B(RHS) in the same way.
909 /// d. Note that E(LHS) and E(RHS) are automatically available on entry of PD,
910 /// so we can assert on that.
911 /// e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) &&
912 /// isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS))
913 bool isKnownViaInduction(ICmpInst::Predicate Pred
, const SCEV
*LHS
,
916 /// Test if the given expression is known to satisfy the condition described
917 /// by Pred, LHS, and RHS.
918 bool isKnownPredicate(ICmpInst::Predicate Pred
, const SCEV
*LHS
,
921 /// Test if the condition described by Pred, LHS, RHS is known to be true on
922 /// every iteration of the loop of the recurrency LHS.
923 bool isKnownOnEveryIteration(ICmpInst::Predicate Pred
,
924 const SCEVAddRecExpr
*LHS
, const SCEV
*RHS
);
926 /// Return true if, for all loop invariant X, the predicate "LHS `Pred` X"
927 /// is monotonically increasing or decreasing. In the former case set
928 /// `Increasing` to true and in the latter case set `Increasing` to false.
930 /// A predicate is said to be monotonically increasing if may go from being
931 /// false to being true as the loop iterates, but never the other way
932 /// around. A predicate is said to be monotonically decreasing if may go
933 /// from being true to being false as the loop iterates, but never the other
935 bool isMonotonicPredicate(const SCEVAddRecExpr
*LHS
, ICmpInst::Predicate Pred
,
938 /// Return true if the result of the predicate LHS `Pred` RHS is loop
939 /// invariant with respect to L. Set InvariantPred, InvariantLHS and
940 /// InvariantLHS so that InvariantLHS `InvariantPred` InvariantRHS is the
941 /// loop invariant form of LHS `Pred` RHS.
942 bool isLoopInvariantPredicate(ICmpInst::Predicate Pred
, const SCEV
*LHS
,
943 const SCEV
*RHS
, const Loop
*L
,
944 ICmpInst::Predicate
&InvariantPred
,
945 const SCEV
*&InvariantLHS
,
946 const SCEV
*&InvariantRHS
);
948 /// Simplify LHS and RHS in a comparison with predicate Pred. Return true
949 /// iff any changes were made. If the operands are provably equal or
950 /// unequal, LHS and RHS are set to the same value and Pred is set to either
951 /// ICMP_EQ or ICMP_NE.
952 bool SimplifyICmpOperands(ICmpInst::Predicate
&Pred
, const SCEV
*&LHS
,
953 const SCEV
*&RHS
, unsigned Depth
= 0);
955 /// Return the "disposition" of the given SCEV with respect to the given
957 LoopDisposition
getLoopDisposition(const SCEV
*S
, const Loop
*L
);
959 /// Return true if the value of the given SCEV is unchanging in the
961 bool isLoopInvariant(const SCEV
*S
, const Loop
*L
);
963 /// Determine if the SCEV can be evaluated at loop's entry. It is true if it
964 /// doesn't depend on a SCEVUnknown of an instruction which is dominated by
965 /// the header of loop L.
966 bool isAvailableAtLoopEntry(const SCEV
*S
, const Loop
*L
);
968 /// Return true if the given SCEV changes value in a known way in the
969 /// specified loop. This property being true implies that the value is
970 /// variant in the loop AND that we can emit an expression to compute the
971 /// value of the expression at any particular loop iteration.
972 bool hasComputableLoopEvolution(const SCEV
*S
, const Loop
*L
);
974 /// Return the "disposition" of the given SCEV with respect to the given
976 BlockDisposition
getBlockDisposition(const SCEV
*S
, const BasicBlock
*BB
);
978 /// Return true if elements that makes up the given SCEV dominate the
979 /// specified basic block.
980 bool dominates(const SCEV
*S
, const BasicBlock
*BB
);
982 /// Return true if elements that makes up the given SCEV properly dominate
983 /// the specified basic block.
984 bool properlyDominates(const SCEV
*S
, const BasicBlock
*BB
);
986 /// Test whether the given SCEV has Op as a direct or indirect operand.
987 bool hasOperand(const SCEV
*S
, const SCEV
*Op
) const;
989 /// Return the size of an element read or written by Inst.
990 const SCEV
*getElementSize(Instruction
*Inst
);
992 /// Compute the array dimensions Sizes from the set of Terms extracted from
993 /// the memory access function of this SCEVAddRecExpr (second step of
994 /// delinearization).
995 void findArrayDimensions(SmallVectorImpl
<const SCEV
*> &Terms
,
996 SmallVectorImpl
<const SCEV
*> &Sizes
,
997 const SCEV
*ElementSize
);
999 void print(raw_ostream
&OS
) const;
1000 void verify() const;
1001 bool invalidate(Function
&F
, const PreservedAnalyses
&PA
,
1002 FunctionAnalysisManager::Invalidator
&Inv
);
1004 /// Collect parametric terms occurring in step expressions (first step of
1005 /// delinearization).
1006 void collectParametricTerms(const SCEV
*Expr
,
1007 SmallVectorImpl
<const SCEV
*> &Terms
);
1009 /// Return in Subscripts the access functions for each dimension in Sizes
1010 /// (third step of delinearization).
1011 void computeAccessFunctions(const SCEV
*Expr
,
1012 SmallVectorImpl
<const SCEV
*> &Subscripts
,
1013 SmallVectorImpl
<const SCEV
*> &Sizes
);
1015 /// Split this SCEVAddRecExpr into two vectors of SCEVs representing the
1016 /// subscripts and sizes of an array access.
1018 /// The delinearization is a 3 step process: the first two steps compute the
1019 /// sizes of each subscript and the third step computes the access functions
1020 /// for the delinearized array:
1022 /// 1. Find the terms in the step functions
1023 /// 2. Compute the array size
1024 /// 3. Compute the access function: divide the SCEV by the array size
1025 /// starting with the innermost dimensions found in step 2. The Quotient
1026 /// is the SCEV to be divided in the next step of the recursion. The
1027 /// Remainder is the subscript of the innermost dimension. Loop over all
1028 /// array dimensions computed in step 2.
1030 /// To compute a uniform array size for several memory accesses to the same
1031 /// object, one can collect in step 1 all the step terms for all the memory
1032 /// accesses, and compute in step 2 a unique array shape. This guarantees
1033 /// that the array shape will be the same across all memory accesses.
1035 /// FIXME: We could derive the result of steps 1 and 2 from a description of
1036 /// the array shape given in metadata.
1045 /// A[j+k][2i][5i] =
1047 /// The initial SCEV:
1049 /// A[{{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k]
1051 /// 1. Find the different terms in the step functions:
1052 /// -> [2*m, 5, n*m, n*m]
1054 /// 2. Compute the array size: sort and unique them
1055 /// -> [n*m, 2*m, 5]
1056 /// find the GCD of all the terms = 1
1057 /// divide by the GCD and erase constant terms
1060 /// divide by GCD -> [n, 2]
1061 /// remove constant terms
1063 /// size of the array is A[unknown][n][m]
1065 /// 3. Compute the access function
1066 /// a. Divide {{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k by the innermost size m
1067 /// Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k
1068 /// Remainder: {{{0,+,5}_i, +, 0}_j, +, 0}_k
1069 /// The remainder is the subscript of the innermost array dimension: [5i].
1071 /// b. Divide Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k by next outer size n
1072 /// Quotient: {{{0,+,0}_i, +, 1}_j, +, 1}_k
1073 /// Remainder: {{{0,+,2}_i, +, 0}_j, +, 0}_k
1074 /// The Remainder is the subscript of the next array dimension: [2i].
1076 /// The subscript of the outermost dimension is the Quotient: [j+k].
1078 /// Overall, we have: A[][n][m], and the access function: A[j+k][2i][5i].
1079 void delinearize(const SCEV
*Expr
, SmallVectorImpl
<const SCEV
*> &Subscripts
,
1080 SmallVectorImpl
<const SCEV
*> &Sizes
,
1081 const SCEV
*ElementSize
);
1083 /// Return the DataLayout associated with the module this SCEV instance is
1085 const DataLayout
&getDataLayout() const {
1086 return F
.getParent()->getDataLayout();
1089 const SCEVPredicate
*getEqualPredicate(const SCEV
*LHS
, const SCEV
*RHS
);
1091 const SCEVPredicate
*
1092 getWrapPredicate(const SCEVAddRecExpr
*AR
,
1093 SCEVWrapPredicate::IncrementWrapFlags AddedFlags
);
1095 /// Re-writes the SCEV according to the Predicates in \p A.
1096 const SCEV
*rewriteUsingPredicate(const SCEV
*S
, const Loop
*L
,
1097 SCEVUnionPredicate
&A
);
1098 /// Tries to convert the \p S expression to an AddRec expression,
1099 /// adding additional predicates to \p Preds as required.
1100 const SCEVAddRecExpr
*convertSCEVToAddRecWithPredicates(
1101 const SCEV
*S
, const Loop
*L
,
1102 SmallPtrSetImpl
<const SCEVPredicate
*> &Preds
);
1105 /// A CallbackVH to arrange for ScalarEvolution to be notified whenever a
1106 /// Value is deleted.
1107 class SCEVCallbackVH final
: public CallbackVH
{
1108 ScalarEvolution
*SE
;
1110 void deleted() override
;
1111 void allUsesReplacedWith(Value
*New
) override
;
1114 SCEVCallbackVH(Value
*V
, ScalarEvolution
*SE
= nullptr);
1117 friend class SCEVCallbackVH
;
1118 friend class SCEVExpander
;
1119 friend class SCEVUnknown
;
1121 /// The function we are analyzing.
1124 /// Does the module have any calls to the llvm.experimental.guard intrinsic
1125 /// at all? If this is false, we avoid doing work that will only help if
1126 /// thare are guards present in the IR.
1129 /// The target library information for the target we are targeting.
1130 TargetLibraryInfo
&TLI
;
1132 /// The tracker for \@llvm.assume intrinsics in this function.
1133 AssumptionCache
&AC
;
1135 /// The dominator tree.
1138 /// The loop information for the function we are currently analyzing.
1141 /// This SCEV is used to represent unknown trip counts and things.
1142 std::unique_ptr
<SCEVCouldNotCompute
> CouldNotCompute
;
1144 /// The type for HasRecMap.
1145 using HasRecMapType
= DenseMap
<const SCEV
*, bool>;
1147 /// This is a cache to record whether a SCEV contains any scAddRecExpr.
1148 HasRecMapType HasRecMap
;
1150 /// The type for ExprValueMap.
1151 using ValueOffsetPair
= std::pair
<Value
*, ConstantInt
*>;
1152 using ExprValueMapType
= DenseMap
<const SCEV
*, SetVector
<ValueOffsetPair
>>;
1154 /// ExprValueMap -- This map records the original values from which
1155 /// the SCEV expr is generated from.
1157 /// We want to represent the mapping as SCEV -> ValueOffsetPair instead
1158 /// of SCEV -> Value:
1159 /// Suppose we know S1 expands to V1, and
1162 /// where C_a and C_b are different SCEVConstants. Then we'd like to
1163 /// expand S3 as V1 - C_a + C_b instead of expanding S2 literally.
1164 /// It is helpful when S2 is a complex SCEV expr.
1166 /// In order to do that, we represent ExprValueMap as a mapping from
1167 /// SCEV to ValueOffsetPair. We will save both S1->{V1, 0} and
1168 /// S2->{V1, C_a} into the map when we create SCEV for V1. When S3
1169 /// is expanded, it will first expand S2 to V1 - C_a because of
1170 /// S2->{V1, C_a} in the map, then expand S3 to V1 - C_a + C_b.
1172 /// Note: S->{V, Offset} in the ExprValueMap means S can be expanded
1174 ExprValueMapType ExprValueMap
;
1176 /// The type for ValueExprMap.
1177 using ValueExprMapType
=
1178 DenseMap
<SCEVCallbackVH
, const SCEV
*, DenseMapInfo
<Value
*>>;
1180 /// This is a cache of the values we have analyzed so far.
1181 ValueExprMapType ValueExprMap
;
1183 /// Mark predicate values currently being processed by isImpliedCond.
1184 SmallPtrSet
<Value
*, 6> PendingLoopPredicates
;
1186 /// Mark SCEVUnknown Phis currently being processed by getRangeRef.
1187 SmallPtrSet
<const PHINode
*, 6> PendingPhiRanges
;
1189 // Mark SCEVUnknown Phis currently being processed by isImpliedViaMerge.
1190 SmallPtrSet
<const PHINode
*, 6> PendingMerges
;
1192 /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of
1193 /// conditions dominating the backedge of a loop.
1194 bool WalkingBEDominatingConds
= false;
1196 /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a
1197 /// predicate by splitting it into a set of independent predicates.
1198 bool ProvingSplitPredicate
= false;
1200 /// Memoized values for the GetMinTrailingZeros
1201 DenseMap
<const SCEV
*, uint32_t> MinTrailingZerosCache
;
1203 /// Return the Value set from which the SCEV expr is generated.
1204 SetVector
<ValueOffsetPair
> *getSCEVValues(const SCEV
*S
);
1206 /// Private helper method for the GetMinTrailingZeros method
1207 uint32_t GetMinTrailingZerosImpl(const SCEV
*S
);
1209 /// Information about the number of loop iterations for which a loop exit's
1210 /// branch condition evaluates to the not-taken path. This is a temporary
1211 /// pair of exact and max expressions that are eventually summarized in
1212 /// ExitNotTakenInfo and BackedgeTakenInfo.
1214 const SCEV
*ExactNotTaken
; // The exit is not taken exactly this many times
1215 const SCEV
*MaxNotTaken
; // The exit is not taken at most this many times
1217 // Not taken either exactly MaxNotTaken or zero times
1218 bool MaxOrZero
= false;
1220 /// A set of predicate guards for this ExitLimit. The result is only valid
1221 /// if all of the predicates in \c Predicates evaluate to 'true' at
1223 SmallPtrSet
<const SCEVPredicate
*, 4> Predicates
;
1225 void addPredicate(const SCEVPredicate
*P
) {
1226 assert(!isa
<SCEVUnionPredicate
>(P
) && "Only add leaf predicates here!");
1227 Predicates
.insert(P
);
1230 /*implicit*/ ExitLimit(const SCEV
*E
);
1233 const SCEV
*E
, const SCEV
*M
, bool MaxOrZero
,
1234 ArrayRef
<const SmallPtrSetImpl
<const SCEVPredicate
*> *> PredSetList
);
1236 ExitLimit(const SCEV
*E
, const SCEV
*M
, bool MaxOrZero
,
1237 const SmallPtrSetImpl
<const SCEVPredicate
*> &PredSet
);
1239 ExitLimit(const SCEV
*E
, const SCEV
*M
, bool MaxOrZero
);
1241 /// Test whether this ExitLimit contains any computed information, or
1242 /// whether it's all SCEVCouldNotCompute values.
1243 bool hasAnyInfo() const {
1244 return !isa
<SCEVCouldNotCompute
>(ExactNotTaken
) ||
1245 !isa
<SCEVCouldNotCompute
>(MaxNotTaken
);
1248 bool hasOperand(const SCEV
*S
) const;
1250 /// Test whether this ExitLimit contains all information.
1251 bool hasFullInfo() const {
1252 return !isa
<SCEVCouldNotCompute
>(ExactNotTaken
);
1256 /// Information about the number of times a particular loop exit may be
1257 /// reached before exiting the loop.
1258 struct ExitNotTakenInfo
{
1259 PoisoningVH
<BasicBlock
> ExitingBlock
;
1260 const SCEV
*ExactNotTaken
;
1261 std::unique_ptr
<SCEVUnionPredicate
> Predicate
;
1263 explicit ExitNotTakenInfo(PoisoningVH
<BasicBlock
> ExitingBlock
,
1264 const SCEV
*ExactNotTaken
,
1265 std::unique_ptr
<SCEVUnionPredicate
> Predicate
)
1266 : ExitingBlock(ExitingBlock
), ExactNotTaken(ExactNotTaken
),
1267 Predicate(std::move(Predicate
)) {}
1269 bool hasAlwaysTruePredicate() const {
1270 return !Predicate
|| Predicate
->isAlwaysTrue();
1274 /// Information about the backedge-taken count of a loop. This currently
1275 /// includes an exact count and a maximum count.
1277 class BackedgeTakenInfo
{
1278 /// A list of computable exits and their not-taken counts. Loops almost
1279 /// never have more than one computable exit.
1280 SmallVector
<ExitNotTakenInfo
, 1> ExitNotTaken
;
1282 /// The pointer part of \c MaxAndComplete is an expression indicating the
1283 /// least maximum backedge-taken count of the loop that is known, or a
1284 /// SCEVCouldNotCompute. This expression is only valid if the predicates
1285 /// associated with all loop exits are true.
1287 /// The integer part of \c MaxAndComplete is a boolean indicating if \c
1288 /// ExitNotTaken has an element for every exiting block in the loop.
1289 PointerIntPair
<const SCEV
*, 1> MaxAndComplete
;
1291 /// True iff the backedge is taken either exactly Max or zero times.
1292 bool MaxOrZero
= false;
1294 /// \name Helper projection functions on \c MaxAndComplete.
1296 bool isComplete() const { return MaxAndComplete
.getInt(); }
1297 const SCEV
*getMax() const { return MaxAndComplete
.getPointer(); }
1301 BackedgeTakenInfo() : MaxAndComplete(nullptr, 0) {}
1302 BackedgeTakenInfo(BackedgeTakenInfo
&&) = default;
1303 BackedgeTakenInfo
&operator=(BackedgeTakenInfo
&&) = default;
1305 using EdgeExitInfo
= std::pair
<BasicBlock
*, ExitLimit
>;
1307 /// Initialize BackedgeTakenInfo from a list of exact exit counts.
1308 BackedgeTakenInfo(ArrayRef
<EdgeExitInfo
> ExitCounts
, bool Complete
,
1309 const SCEV
*MaxCount
, bool MaxOrZero
);
1311 /// Test whether this BackedgeTakenInfo contains any computed information,
1312 /// or whether it's all SCEVCouldNotCompute values.
1313 bool hasAnyInfo() const {
1314 return !ExitNotTaken
.empty() || !isa
<SCEVCouldNotCompute
>(getMax());
1317 /// Test whether this BackedgeTakenInfo contains complete information.
1318 bool hasFullInfo() const { return isComplete(); }
1320 /// Return an expression indicating the exact *backedge-taken*
1321 /// count of the loop if it is known or SCEVCouldNotCompute
1322 /// otherwise. If execution makes it to the backedge on every
1323 /// iteration (i.e. there are no abnormal exists like exception
1324 /// throws and thread exits) then this is the number of times the
1325 /// loop header will execute minus one.
1327 /// If the SCEV predicate associated with the answer can be different
1328 /// from AlwaysTrue, we must add a (non null) Predicates argument.
1329 /// The SCEV predicate associated with the answer will be added to
1330 /// Predicates. A run-time check needs to be emitted for the SCEV
1331 /// predicate in order for the answer to be valid.
1333 /// Note that we should always know if we need to pass a predicate
1334 /// argument or not from the way the ExitCounts vector was computed.
1335 /// If we allowed SCEV predicates to be generated when populating this
1336 /// vector, this information can contain them and therefore a
1337 /// SCEVPredicate argument should be added to getExact.
1338 const SCEV
*getExact(const Loop
*L
, ScalarEvolution
*SE
,
1339 SCEVUnionPredicate
*Predicates
= nullptr) const;
1341 /// Return the number of times this loop exit may fall through to the back
1342 /// edge, or SCEVCouldNotCompute. The loop is guaranteed not to exit via
1343 /// this block before this number of iterations, but may exit via another
1345 const SCEV
*getExact(BasicBlock
*ExitingBlock
, ScalarEvolution
*SE
) const;
1347 /// Get the max backedge taken count for the loop.
1348 const SCEV
*getMax(ScalarEvolution
*SE
) const;
1350 /// Return true if the number of times this backedge is taken is either the
1351 /// value returned by getMax or zero.
1352 bool isMaxOrZero(ScalarEvolution
*SE
) const;
1354 /// Return true if any backedge taken count expressions refer to the given
1356 bool hasOperand(const SCEV
*S
, ScalarEvolution
*SE
) const;
1358 /// Invalidate this result and free associated memory.
1362 /// Cache the backedge-taken count of the loops for this function as they
1364 DenseMap
<const Loop
*, BackedgeTakenInfo
> BackedgeTakenCounts
;
1366 /// Cache the predicated backedge-taken count of the loops for this
1367 /// function as they are computed.
1368 DenseMap
<const Loop
*, BackedgeTakenInfo
> PredicatedBackedgeTakenCounts
;
1370 /// This map contains entries for all of the PHI instructions that we
1371 /// attempt to compute constant evolutions for. This allows us to avoid
1372 /// potentially expensive recomputation of these properties. An instruction
1373 /// maps to null if we are unable to compute its exit value.
1374 DenseMap
<PHINode
*, Constant
*> ConstantEvolutionLoopExitValue
;
1376 /// This map contains entries for all the expressions that we attempt to
1377 /// compute getSCEVAtScope information for, which can be expensive in
1379 DenseMap
<const SCEV
*, SmallVector
<std::pair
<const Loop
*, const SCEV
*>, 2>>
1382 /// Memoized computeLoopDisposition results.
1383 DenseMap
<const SCEV
*,
1384 SmallVector
<PointerIntPair
<const Loop
*, 2, LoopDisposition
>, 2>>
1387 struct LoopProperties
{
1388 /// Set to true if the loop contains no instruction that can have side
1389 /// effects (i.e. via throwing an exception, volatile or atomic access).
1390 bool HasNoAbnormalExits
;
1392 /// Set to true if the loop contains no instruction that can abnormally exit
1393 /// the loop (i.e. via throwing an exception, by terminating the thread
1394 /// cleanly or by infinite looping in a called function). Strictly
1395 /// speaking, the last one is not leaving the loop, but is identical to
1396 /// leaving the loop for reasoning about undefined behavior.
1397 bool HasNoSideEffects
;
1400 /// Cache for \c getLoopProperties.
1401 DenseMap
<const Loop
*, LoopProperties
> LoopPropertiesCache
;
1403 /// Return a \c LoopProperties instance for \p L, creating one if necessary.
1404 LoopProperties
getLoopProperties(const Loop
*L
);
1406 bool loopHasNoSideEffects(const Loop
*L
) {
1407 return getLoopProperties(L
).HasNoSideEffects
;
1410 bool loopHasNoAbnormalExits(const Loop
*L
) {
1411 return getLoopProperties(L
).HasNoAbnormalExits
;
1414 /// Compute a LoopDisposition value.
1415 LoopDisposition
computeLoopDisposition(const SCEV
*S
, const Loop
*L
);
1417 /// Memoized computeBlockDisposition results.
1420 SmallVector
<PointerIntPair
<const BasicBlock
*, 2, BlockDisposition
>, 2>>
1423 /// Compute a BlockDisposition value.
1424 BlockDisposition
computeBlockDisposition(const SCEV
*S
, const BasicBlock
*BB
);
1426 /// Memoized results from getRange
1427 DenseMap
<const SCEV
*, ConstantRange
> UnsignedRanges
;
1429 /// Memoized results from getRange
1430 DenseMap
<const SCEV
*, ConstantRange
> SignedRanges
;
1432 /// Used to parameterize getRange
1433 enum RangeSignHint
{ HINT_RANGE_UNSIGNED
, HINT_RANGE_SIGNED
};
1435 /// Set the memoized range for the given SCEV.
1436 const ConstantRange
&setRange(const SCEV
*S
, RangeSignHint Hint
,
1438 DenseMap
<const SCEV
*, ConstantRange
> &Cache
=
1439 Hint
== HINT_RANGE_UNSIGNED
? UnsignedRanges
: SignedRanges
;
1441 auto Pair
= Cache
.try_emplace(S
, std::move(CR
));
1443 Pair
.first
->second
= std::move(CR
);
1444 return Pair
.first
->second
;
1447 /// Determine the range for a particular SCEV.
1448 /// NOTE: This returns a reference to an entry in a cache. It must be
1449 /// copied if its needed for longer.
1450 const ConstantRange
&getRangeRef(const SCEV
*S
, RangeSignHint Hint
);
1452 /// Determines the range for the affine SCEVAddRecExpr {\p Start,+,\p Stop}.
1453 /// Helper for \c getRange.
1454 ConstantRange
getRangeForAffineAR(const SCEV
*Start
, const SCEV
*Stop
,
1455 const SCEV
*MaxBECount
, unsigned BitWidth
);
1457 /// Try to compute a range for the affine SCEVAddRecExpr {\p Start,+,\p
1458 /// Stop} by "factoring out" a ternary expression from the add recurrence.
1459 /// Helper called by \c getRange.
1460 ConstantRange
getRangeViaFactoring(const SCEV
*Start
, const SCEV
*Stop
,
1461 const SCEV
*MaxBECount
, unsigned BitWidth
);
1463 /// We know that there is no SCEV for the specified value. Analyze the
1465 const SCEV
*createSCEV(Value
*V
);
1467 /// Provide the special handling we need to analyze PHI SCEVs.
1468 const SCEV
*createNodeForPHI(PHINode
*PN
);
1470 /// Helper function called from createNodeForPHI.
1471 const SCEV
*createAddRecFromPHI(PHINode
*PN
);
1473 /// A helper function for createAddRecFromPHI to handle simple cases.
1474 const SCEV
*createSimpleAffineAddRec(PHINode
*PN
, Value
*BEValueV
,
1475 Value
*StartValueV
);
1477 /// Helper function called from createNodeForPHI.
1478 const SCEV
*createNodeFromSelectLikePHI(PHINode
*PN
);
1480 /// Provide special handling for a select-like instruction (currently this
1481 /// is either a select instruction or a phi node). \p I is the instruction
1482 /// being processed, and it is assumed equivalent to "Cond ? TrueVal :
1484 const SCEV
*createNodeForSelectOrPHI(Instruction
*I
, Value
*Cond
,
1485 Value
*TrueVal
, Value
*FalseVal
);
1487 /// Provide the special handling we need to analyze GEP SCEVs.
1488 const SCEV
*createNodeForGEP(GEPOperator
*GEP
);
1490 /// Implementation code for getSCEVAtScope; called at most once for each
1492 const SCEV
*computeSCEVAtScope(const SCEV
*S
, const Loop
*L
);
1494 /// This looks up computed SCEV values for all instructions that depend on
1495 /// the given instruction and removes them from the ValueExprMap map if they
1496 /// reference SymName. This is used during PHI resolution.
1497 void forgetSymbolicName(Instruction
*I
, const SCEV
*SymName
);
1499 /// Return the BackedgeTakenInfo for the given loop, lazily computing new
1500 /// values if the loop hasn't been analyzed yet. The returned result is
1501 /// guaranteed not to be predicated.
1502 const BackedgeTakenInfo
&getBackedgeTakenInfo(const Loop
*L
);
1504 /// Similar to getBackedgeTakenInfo, but will add predicates as required
1505 /// with the purpose of returning complete information.
1506 const BackedgeTakenInfo
&getPredicatedBackedgeTakenInfo(const Loop
*L
);
1508 /// Compute the number of times the specified loop will iterate.
1509 /// If AllowPredicates is set, we will create new SCEV predicates as
1510 /// necessary in order to return an exact answer.
1511 BackedgeTakenInfo
computeBackedgeTakenCount(const Loop
*L
,
1512 bool AllowPredicates
= false);
1514 /// Compute the number of times the backedge of the specified loop will
1515 /// execute if it exits via the specified block. If AllowPredicates is set,
1516 /// this call will try to use a minimal set of SCEV predicates in order to
1517 /// return an exact answer.
1518 ExitLimit
computeExitLimit(const Loop
*L
, BasicBlock
*ExitingBlock
,
1519 bool AllowPredicates
= false);
1521 /// Compute the number of times the backedge of the specified loop will
1522 /// execute if its exit condition were a conditional branch of ExitCond.
1524 /// \p ControlsExit is true if ExitCond directly controls the exit
1525 /// branch. In this case, we can assume that the loop exits only if the
1526 /// condition is true and can infer that failing to meet the condition prior
1527 /// to integer wraparound results in undefined behavior.
1529 /// If \p AllowPredicates is set, this call will try to use a minimal set of
1530 /// SCEV predicates in order to return an exact answer.
1531 ExitLimit
computeExitLimitFromCond(const Loop
*L
, Value
*ExitCond
,
1532 bool ExitIfTrue
, bool ControlsExit
,
1533 bool AllowPredicates
= false);
1535 // Helper functions for computeExitLimitFromCond to avoid exponential time
1538 class ExitLimitCache
{
1539 // It may look like we need key on the whole (L, ExitIfTrue, ControlsExit,
1540 // AllowPredicates) tuple, but recursive calls to
1541 // computeExitLimitFromCondCached from computeExitLimitFromCondImpl only
1542 // vary the in \c ExitCond and \c ControlsExit parameters. We remember the
1543 // initial values of the other values to assert our assumption.
1544 SmallDenseMap
<PointerIntPair
<Value
*, 1>, ExitLimit
> TripCountMap
;
1548 bool AllowPredicates
;
1551 ExitLimitCache(const Loop
*L
, bool ExitIfTrue
, bool AllowPredicates
)
1552 : L(L
), ExitIfTrue(ExitIfTrue
), AllowPredicates(AllowPredicates
) {}
1554 Optional
<ExitLimit
> find(const Loop
*L
, Value
*ExitCond
, bool ExitIfTrue
,
1555 bool ControlsExit
, bool AllowPredicates
);
1557 void insert(const Loop
*L
, Value
*ExitCond
, bool ExitIfTrue
,
1558 bool ControlsExit
, bool AllowPredicates
, const ExitLimit
&EL
);
1561 using ExitLimitCacheTy
= ExitLimitCache
;
1563 ExitLimit
computeExitLimitFromCondCached(ExitLimitCacheTy
&Cache
,
1564 const Loop
*L
, Value
*ExitCond
,
1567 bool AllowPredicates
);
1568 ExitLimit
computeExitLimitFromCondImpl(ExitLimitCacheTy
&Cache
, const Loop
*L
,
1569 Value
*ExitCond
, bool ExitIfTrue
,
1571 bool AllowPredicates
);
1573 /// Compute the number of times the backedge of the specified loop will
1574 /// execute if its exit condition were a conditional branch of the ICmpInst
1575 /// ExitCond and ExitIfTrue. If AllowPredicates is set, this call will try
1576 /// to use a minimal set of SCEV predicates in order to return an exact
1578 ExitLimit
computeExitLimitFromICmp(const Loop
*L
, ICmpInst
*ExitCond
,
1581 bool AllowPredicates
= false);
1583 /// Compute the number of times the backedge of the specified loop will
1584 /// execute if its exit condition were a switch with a single exiting case
1586 ExitLimit
computeExitLimitFromSingleExitSwitch(const Loop
*L
,
1588 BasicBlock
*ExitingBB
,
1591 /// Given an exit condition of 'icmp op load X, cst', try to see if we can
1592 /// compute the backedge-taken count.
1593 ExitLimit
computeLoadConstantCompareExitLimit(LoadInst
*LI
, Constant
*RHS
,
1595 ICmpInst::Predicate p
);
1597 /// Compute the exit limit of a loop that is controlled by a
1598 /// "(IV >> 1) != 0" type comparison. We cannot compute the exact trip
1599 /// count in these cases (since SCEV has no way of expressing them), but we
1600 /// can still sometimes compute an upper bound.
1602 /// Return an ExitLimit for a loop whose backedge is guarded by `LHS Pred
1604 ExitLimit
computeShiftCompareExitLimit(Value
*LHS
, Value
*RHS
, const Loop
*L
,
1605 ICmpInst::Predicate Pred
);
1607 /// If the loop is known to execute a constant number of times (the
1608 /// condition evolves only from constants), try to evaluate a few iterations
1609 /// of the loop until we get the exit condition gets a value of ExitWhen
1610 /// (true or false). If we cannot evaluate the exit count of the loop,
1611 /// return CouldNotCompute.
1612 const SCEV
*computeExitCountExhaustively(const Loop
*L
, Value
*Cond
,
1615 /// Return the number of times an exit condition comparing the specified
1616 /// value to zero will execute. If not computable, return CouldNotCompute.
1617 /// If AllowPredicates is set, this call will try to use a minimal set of
1618 /// SCEV predicates in order to return an exact answer.
1619 ExitLimit
howFarToZero(const SCEV
*V
, const Loop
*L
, bool IsSubExpr
,
1620 bool AllowPredicates
= false);
1622 /// Return the number of times an exit condition checking the specified
1623 /// value for nonzero will execute. If not computable, return
1624 /// CouldNotCompute.
1625 ExitLimit
howFarToNonZero(const SCEV
*V
, const Loop
*L
);
1627 /// Return the number of times an exit condition containing the specified
1628 /// less-than comparison will execute. If not computable, return
1629 /// CouldNotCompute.
1631 /// \p isSigned specifies whether the less-than is signed.
1633 /// \p ControlsExit is true when the LHS < RHS condition directly controls
1634 /// the branch (loops exits only if condition is true). In this case, we can
1635 /// use NoWrapFlags to skip overflow checks.
1637 /// If \p AllowPredicates is set, this call will try to use a minimal set of
1638 /// SCEV predicates in order to return an exact answer.
1639 ExitLimit
howManyLessThans(const SCEV
*LHS
, const SCEV
*RHS
, const Loop
*L
,
1640 bool isSigned
, bool ControlsExit
,
1641 bool AllowPredicates
= false);
1643 ExitLimit
howManyGreaterThans(const SCEV
*LHS
, const SCEV
*RHS
, const Loop
*L
,
1644 bool isSigned
, bool IsSubExpr
,
1645 bool AllowPredicates
= false);
1647 /// Return a predecessor of BB (which may not be an immediate predecessor)
1648 /// which has exactly one successor from which BB is reachable, or null if
1649 /// no such block is found.
1650 std::pair
<BasicBlock
*, BasicBlock
*>
1651 getPredecessorWithUniqueSuccessorForBB(BasicBlock
*BB
);
1653 /// Test whether the condition described by Pred, LHS, and RHS is true
1654 /// whenever the given FoundCondValue value evaluates to true.
1655 bool isImpliedCond(ICmpInst::Predicate Pred
, const SCEV
*LHS
, const SCEV
*RHS
,
1656 Value
*FoundCondValue
, bool Inverse
);
1658 /// Test whether the condition described by Pred, LHS, and RHS is true
1659 /// whenever the condition described by FoundPred, FoundLHS, FoundRHS is
1661 bool isImpliedCond(ICmpInst::Predicate Pred
, const SCEV
*LHS
, const SCEV
*RHS
,
1662 ICmpInst::Predicate FoundPred
, const SCEV
*FoundLHS
,
1663 const SCEV
*FoundRHS
);
1665 /// Test whether the condition described by Pred, LHS, and RHS is true
1666 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1668 bool isImpliedCondOperands(ICmpInst::Predicate Pred
, const SCEV
*LHS
,
1669 const SCEV
*RHS
, const SCEV
*FoundLHS
,
1670 const SCEV
*FoundRHS
);
1672 /// Test whether the condition described by Pred, LHS, and RHS is true
1673 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1674 /// true. Here LHS is an operation that includes FoundLHS as one of its
1676 bool isImpliedViaOperations(ICmpInst::Predicate Pred
,
1677 const SCEV
*LHS
, const SCEV
*RHS
,
1678 const SCEV
*FoundLHS
, const SCEV
*FoundRHS
,
1679 unsigned Depth
= 0);
1681 /// Test whether the condition described by Pred, LHS, and RHS is true.
1682 /// Use only simple non-recursive types of checks, such as range analysis etc.
1683 bool isKnownViaNonRecursiveReasoning(ICmpInst::Predicate Pred
,
1684 const SCEV
*LHS
, const SCEV
*RHS
);
1686 /// Test whether the condition described by Pred, LHS, and RHS is true
1687 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1689 bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred
, const SCEV
*LHS
,
1690 const SCEV
*RHS
, const SCEV
*FoundLHS
,
1691 const SCEV
*FoundRHS
);
1693 /// Test whether the condition described by Pred, LHS, and RHS is true
1694 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1695 /// true. Utility function used by isImpliedCondOperands. Tries to get
1696 /// cases like "X `sgt` 0 => X - 1 `sgt` -1".
1697 bool isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred
, const SCEV
*LHS
,
1698 const SCEV
*RHS
, const SCEV
*FoundLHS
,
1699 const SCEV
*FoundRHS
);
1701 /// Return true if the condition denoted by \p LHS \p Pred \p RHS is implied
1702 /// by a call to \c @llvm.experimental.guard in \p BB.
1703 bool isImpliedViaGuard(BasicBlock
*BB
, ICmpInst::Predicate Pred
,
1704 const SCEV
*LHS
, const SCEV
*RHS
);
1706 /// Test whether the condition described by Pred, LHS, and RHS is true
1707 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1710 /// This routine tries to rule out certain kinds of integer overflow, and
1711 /// then tries to reason about arithmetic properties of the predicates.
1712 bool isImpliedCondOperandsViaNoOverflow(ICmpInst::Predicate Pred
,
1713 const SCEV
*LHS
, const SCEV
*RHS
,
1714 const SCEV
*FoundLHS
,
1715 const SCEV
*FoundRHS
);
1717 /// Test whether the condition described by Pred, LHS, and RHS is true
1718 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1721 /// This routine tries to figure out predicate for Phis which are SCEVUnknown
1722 /// if it is true for every possible incoming value from their respective
1724 bool isImpliedViaMerge(ICmpInst::Predicate Pred
,
1725 const SCEV
*LHS
, const SCEV
*RHS
,
1726 const SCEV
*FoundLHS
, const SCEV
*FoundRHS
,
1729 /// If we know that the specified Phi is in the header of its containing
1730 /// loop, we know the loop executes a constant number of times, and the PHI
1731 /// node is just a recurrence involving constants, fold it.
1732 Constant
*getConstantEvolutionLoopExitValue(PHINode
*PN
, const APInt
&BEs
,
1735 /// Test if the given expression is known to satisfy the condition described
1736 /// by Pred and the known constant ranges of LHS and RHS.
1737 bool isKnownPredicateViaConstantRanges(ICmpInst::Predicate Pred
,
1738 const SCEV
*LHS
, const SCEV
*RHS
);
1740 /// Try to prove the condition described by "LHS Pred RHS" by ruling out
1741 /// integer overflow.
1743 /// For instance, this will return true for "A s< (A + C)<nsw>" if C is
1745 bool isKnownPredicateViaNoOverflow(ICmpInst::Predicate Pred
, const SCEV
*LHS
,
1748 /// Try to split Pred LHS RHS into logical conjunctions (and's) and try to
1749 /// prove them individually.
1750 bool isKnownPredicateViaSplitting(ICmpInst::Predicate Pred
, const SCEV
*LHS
,
1753 /// Try to match the Expr as "(L + R)<Flags>".
1754 bool splitBinaryAdd(const SCEV
*Expr
, const SCEV
*&L
, const SCEV
*&R
,
1755 SCEV::NoWrapFlags
&Flags
);
1757 /// Compute \p LHS - \p RHS and returns the result as an APInt if it is a
1758 /// constant, and None if it isn't.
1760 /// This is intended to be a cheaper version of getMinusSCEV. We can be
1761 /// frugal here since we just bail out of actually constructing and
1762 /// canonicalizing an expression in the cases where the result isn't going
1763 /// to be a constant.
1764 Optional
<APInt
> computeConstantDifference(const SCEV
*LHS
, const SCEV
*RHS
);
1766 /// Drop memoized information computed for S.
1767 void forgetMemoizedResults(const SCEV
*S
);
1769 /// Return an existing SCEV for V if there is one, otherwise return nullptr.
1770 const SCEV
*getExistingSCEV(Value
*V
);
1772 /// Return false iff given SCEV contains a SCEVUnknown with NULL value-
1774 bool checkValidity(const SCEV
*S
) const;
1776 /// Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be
1777 /// equal to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}. This is
1778 /// equivalent to proving no signed (resp. unsigned) wrap in
1779 /// {`Start`,+,`Step`} if `ExtendOpTy` is `SCEVSignExtendExpr`
1780 /// (resp. `SCEVZeroExtendExpr`).
1781 template <typename ExtendOpTy
>
1782 bool proveNoWrapByVaryingStart(const SCEV
*Start
, const SCEV
*Step
,
1785 /// Try to prove NSW or NUW on \p AR relying on ConstantRange manipulation.
1786 SCEV::NoWrapFlags
proveNoWrapViaConstantRanges(const SCEVAddRecExpr
*AR
);
1788 bool isMonotonicPredicateImpl(const SCEVAddRecExpr
*LHS
,
1789 ICmpInst::Predicate Pred
, bool &Increasing
);
1791 /// Return SCEV no-wrap flags that can be proven based on reasoning about
1792 /// how poison produced from no-wrap flags on this value (e.g. a nuw add)
1793 /// would trigger undefined behavior on overflow.
1794 SCEV::NoWrapFlags
getNoWrapFlagsFromUB(const Value
*V
);
1796 /// Return true if the SCEV corresponding to \p I is never poison. Proving
1797 /// this is more complex than proving that just \p I is never poison, since
1798 /// SCEV commons expressions across control flow, and you can have cases
1802 /// ptr[idx0] = 100;
1803 /// if (<condition>) {
1804 /// idx1 = a +nsw b;
1805 /// ptr[idx1] = 200;
1808 /// where the SCEV expression (+ a b) is guaranteed to not be poison (and
1809 /// hence not sign-overflow) only if "<condition>" is true. Since both
1810 /// `idx0` and `idx1` will be mapped to the same SCEV expression, (+ a b),
1811 /// it is not okay to annotate (+ a b) with <nsw> in the above example.
1812 bool isSCEVExprNeverPoison(const Instruction
*I
);
1814 /// This is like \c isSCEVExprNeverPoison but it specifically works for
1815 /// instructions that will get mapped to SCEV add recurrences. Return true
1816 /// if \p I will never generate poison under the assumption that \p I is an
1817 /// add recurrence on the loop \p L.
1818 bool isAddRecNeverPoison(const Instruction
*I
, const Loop
*L
);
1820 /// Similar to createAddRecFromPHI, but with the additional flexibility of
1821 /// suggesting runtime overflow checks in case casts are encountered.
1822 /// If successful, the analysis records that for this loop, \p SymbolicPHI,
1823 /// which is the UnknownSCEV currently representing the PHI, can be rewritten
1824 /// into an AddRec, assuming some predicates; The function then returns the
1825 /// AddRec and the predicates as a pair, and caches this pair in
1826 /// PredicatedSCEVRewrites.
1827 /// If the analysis is not successful, a mapping from the \p SymbolicPHI to
1828 /// itself (with no predicates) is recorded, and a nullptr with an empty
1829 /// predicates vector is returned as a pair.
1830 Optional
<std::pair
<const SCEV
*, SmallVector
<const SCEVPredicate
*, 3>>>
1831 createAddRecFromPHIWithCastsImpl(const SCEVUnknown
*SymbolicPHI
);
1833 /// Compute the backedge taken count knowing the interval difference, the
1834 /// stride and presence of the equality in the comparison.
1835 const SCEV
*computeBECount(const SCEV
*Delta
, const SCEV
*Stride
,
1838 /// Compute the maximum backedge count based on the range of values
1839 /// permitted by Start, End, and Stride. This is for loops of the form
1840 /// {Start, +, Stride} LT End.
1842 /// Precondition: the induction variable is known to be positive. We *don't*
1843 /// assert these preconditions so please be careful.
1844 const SCEV
*computeMaxBECountForLT(const SCEV
*Start
, const SCEV
*Stride
,
1845 const SCEV
*End
, unsigned BitWidth
,
1848 /// Verify if an linear IV with positive stride can overflow when in a
1849 /// less-than comparison, knowing the invariant term of the comparison,
1850 /// the stride and the knowledge of NSW/NUW flags on the recurrence.
1851 bool doesIVOverflowOnLT(const SCEV
*RHS
, const SCEV
*Stride
, bool IsSigned
,
1854 /// Verify if an linear IV with negative stride can overflow when in a
1855 /// greater-than comparison, knowing the invariant term of the comparison,
1856 /// the stride and the knowledge of NSW/NUW flags on the recurrence.
1857 bool doesIVOverflowOnGT(const SCEV
*RHS
, const SCEV
*Stride
, bool IsSigned
,
1860 /// Get add expr already created or create a new one.
1861 const SCEV
*getOrCreateAddExpr(ArrayRef
<const SCEV
*> Ops
,
1862 SCEV::NoWrapFlags Flags
);
1864 /// Get mul expr already created or create a new one.
1865 const SCEV
*getOrCreateMulExpr(ArrayRef
<const SCEV
*> Ops
,
1866 SCEV::NoWrapFlags Flags
);
1868 // Get addrec expr already created or create a new one.
1869 const SCEV
*getOrCreateAddRecExpr(ArrayRef
<const SCEV
*> Ops
,
1870 const Loop
*L
, SCEV::NoWrapFlags Flags
);
1872 /// Return x if \p Val is f(x) where f is a 1-1 function.
1873 const SCEV
*stripInjectiveFunctions(const SCEV
*Val
) const;
1875 /// Find all of the loops transitively used in \p S, and fill \p LoopsUsed.
1876 /// A loop is considered "used" by an expression if it contains
1877 /// an add rec on said loop.
1878 void getUsedLoops(const SCEV
*S
, SmallPtrSetImpl
<const Loop
*> &LoopsUsed
);
1880 /// Find all of the loops transitively used in \p S, and update \c LoopUsers
1882 void addToLoopUseLists(const SCEV
*S
);
1884 /// Try to match the pattern generated by getURemExpr(A, B). If successful,
1885 /// Assign A and B to LHS and RHS, respectively.
1886 bool matchURem(const SCEV
*Expr
, const SCEV
*&LHS
, const SCEV
*&RHS
);
1888 /// Look for a SCEV expression with type `SCEVType` and operands `Ops` in
1891 /// The first component of the returned tuple is the SCEV if found and null
1892 /// otherwise. The second component is the `FoldingSetNodeID` that was
1893 /// constructed to look up the SCEV and the third component is the insertion
1895 std::tuple
<const SCEV
*, FoldingSetNodeID
, void *>
1896 findExistingSCEVInCache(int SCEVType
, ArrayRef
<const SCEV
*> Ops
);
1898 FoldingSet
<SCEV
> UniqueSCEVs
;
1899 FoldingSet
<SCEVPredicate
> UniquePreds
;
1900 BumpPtrAllocator SCEVAllocator
;
1902 /// This maps loops to a list of SCEV expressions that (transitively) use said
1904 DenseMap
<const Loop
*, SmallVector
<const SCEV
*, 4>> LoopUsers
;
1906 /// Cache tentative mappings from UnknownSCEVs in a Loop, to a SCEV expression
1907 /// they can be rewritten into under certain predicates.
1908 DenseMap
<std::pair
<const SCEVUnknown
*, const Loop
*>,
1909 std::pair
<const SCEV
*, SmallVector
<const SCEVPredicate
*, 3>>>
1910 PredicatedSCEVRewrites
;
1912 /// The head of a linked list of all SCEVUnknown values that have been
1913 /// allocated. This is used by releaseMemory to locate them all and call
1914 /// their destructors.
1915 SCEVUnknown
*FirstUnknown
= nullptr;
1918 /// Analysis pass that exposes the \c ScalarEvolution for a function.
1919 class ScalarEvolutionAnalysis
1920 : public AnalysisInfoMixin
<ScalarEvolutionAnalysis
> {
1921 friend AnalysisInfoMixin
<ScalarEvolutionAnalysis
>;
1923 static AnalysisKey Key
;
1926 using Result
= ScalarEvolution
;
1928 ScalarEvolution
run(Function
&F
, FunctionAnalysisManager
&AM
);
1931 /// Printer pass for the \c ScalarEvolutionAnalysis results.
1932 class ScalarEvolutionPrinterPass
1933 : public PassInfoMixin
<ScalarEvolutionPrinterPass
> {
1937 explicit ScalarEvolutionPrinterPass(raw_ostream
&OS
) : OS(OS
) {}
1939 PreservedAnalyses
run(Function
&F
, FunctionAnalysisManager
&AM
);
1942 class ScalarEvolutionWrapperPass
: public FunctionPass
{
1943 std::unique_ptr
<ScalarEvolution
> SE
;
1948 ScalarEvolutionWrapperPass();
1950 ScalarEvolution
&getSE() { return *SE
; }
1951 const ScalarEvolution
&getSE() const { return *SE
; }
1953 bool runOnFunction(Function
&F
) override
;
1954 void releaseMemory() override
;
1955 void getAnalysisUsage(AnalysisUsage
&AU
) const override
;
1956 void print(raw_ostream
&OS
, const Module
* = nullptr) const override
;
1957 void verifyAnalysis() const override
;
1960 /// An interface layer with SCEV used to manage how we see SCEV expressions
1961 /// for values in the context of existing predicates. We can add new
1962 /// predicates, but we cannot remove them.
1964 /// This layer has multiple purposes:
1965 /// - provides a simple interface for SCEV versioning.
1966 /// - guarantees that the order of transformations applied on a SCEV
1967 /// expression for a single Value is consistent across two different
1968 /// getSCEV calls. This means that, for example, once we've obtained
1969 /// an AddRec expression for a certain value through expression
1970 /// rewriting, we will continue to get an AddRec expression for that
1972 /// - lowers the number of expression rewrites.
1973 class PredicatedScalarEvolution
{
1975 PredicatedScalarEvolution(ScalarEvolution
&SE
, Loop
&L
);
1977 const SCEVUnionPredicate
&getUnionPredicate() const;
1979 /// Returns the SCEV expression of V, in the context of the current SCEV
1980 /// predicate. The order of transformations applied on the expression of V
1981 /// returned by ScalarEvolution is guaranteed to be preserved, even when
1982 /// adding new predicates.
1983 const SCEV
*getSCEV(Value
*V
);
1985 /// Get the (predicated) backedge count for the analyzed loop.
1986 const SCEV
*getBackedgeTakenCount();
1988 /// Adds a new predicate.
1989 void addPredicate(const SCEVPredicate
&Pred
);
1991 /// Attempts to produce an AddRecExpr for V by adding additional SCEV
1992 /// predicates. If we can't transform the expression into an AddRecExpr we
1993 /// return nullptr and not add additional SCEV predicates to the current
1995 const SCEVAddRecExpr
*getAsAddRec(Value
*V
);
1997 /// Proves that V doesn't overflow by adding SCEV predicate.
1998 void setNoOverflow(Value
*V
, SCEVWrapPredicate::IncrementWrapFlags Flags
);
2000 /// Returns true if we've proved that V doesn't wrap by means of a SCEV
2002 bool hasNoOverflow(Value
*V
, SCEVWrapPredicate::IncrementWrapFlags Flags
);
2004 /// Returns the ScalarEvolution analysis used.
2005 ScalarEvolution
*getSE() const { return &SE
; }
2007 /// We need to explicitly define the copy constructor because of FlagsMap.
2008 PredicatedScalarEvolution(const PredicatedScalarEvolution
&);
2010 /// Print the SCEV mappings done by the Predicated Scalar Evolution.
2011 /// The printed text is indented by \p Depth.
2012 void print(raw_ostream
&OS
, unsigned Depth
) const;
2014 /// Check if \p AR1 and \p AR2 are equal, while taking into account
2015 /// Equal predicates in Preds.
2016 bool areAddRecsEqualWithPreds(const SCEVAddRecExpr
*AR1
,
2017 const SCEVAddRecExpr
*AR2
) const;
2020 /// Increments the version number of the predicate. This needs to be called
2021 /// every time the SCEV predicate changes.
2022 void updateGeneration();
2024 /// Holds a SCEV and the version number of the SCEV predicate used to
2025 /// perform the rewrite of the expression.
2026 using RewriteEntry
= std::pair
<unsigned, const SCEV
*>;
2028 /// Maps a SCEV to the rewrite result of that SCEV at a certain version
2029 /// number. If this number doesn't match the current Generation, we will
2030 /// need to do a rewrite. To preserve the transformation order of previous
2031 /// rewrites, we will rewrite the previous result instead of the original
2033 DenseMap
<const SCEV
*, RewriteEntry
> RewriteMap
;
2035 /// Records what NoWrap flags we've added to a Value *.
2036 ValueMap
<Value
*, SCEVWrapPredicate::IncrementWrapFlags
> FlagsMap
;
2038 /// The ScalarEvolution analysis.
2039 ScalarEvolution
&SE
;
2041 /// The analyzed Loop.
2044 /// The SCEVPredicate that forms our context. We will rewrite all
2045 /// expressions assuming that this predicate true.
2046 SCEVUnionPredicate Preds
;
2048 /// Marks the version of the SCEV predicate used. When rewriting a SCEV
2049 /// expression we mark it with the version of the predicate. We use this to
2050 /// figure out if the predicate has changed from the last rewrite of the
2051 /// SCEV. If so, we need to perform a new rewrite.
2052 unsigned Generation
= 0;
2054 /// The backedge taken count.
2055 const SCEV
*BackedgeCount
= nullptr;
2058 } // end namespace llvm
2060 #endif // LLVM_ANALYSIS_SCALAREVOLUTION_H