LLVM 23.0.0git
ScalarEvolution.h
Go to the documentation of this file.
1//===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// The ScalarEvolution class is an LLVM pass which can be used to analyze and
10// categorize scalar expressions in loops. It specializes in recognizing
11// general induction variables, representing them with the abstract and opaque
12// SCEV class. Given this analysis, trip counts of loops and other important
13// properties can be obtained.
14//
15// This analysis is primarily useful for induction variable substitution and
16// strength reduction.
17//
18//===----------------------------------------------------------------------===//
19
20#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
21#define LLVM_ANALYSIS_SCALAREVOLUTION_H
22
23#include "llvm/ADT/APInt.h"
24#include "llvm/ADT/ArrayRef.h"
26#include "llvm/ADT/DenseMap.h"
28#include "llvm/ADT/FoldingSet.h"
30#include "llvm/ADT/SetVector.h"
35#include "llvm/IR/PassManager.h"
36#include "llvm/IR/ValueHandle.h"
37#include "llvm/IR/ValueMap.h"
38#include "llvm/Pass.h"
40#include <cassert>
41#include <cstdint>
42#include <memory>
43#include <optional>
44#include <utility>
45
46namespace llvm {
47
49class AssumptionCache;
50class BasicBlock;
51class Constant;
52class ConstantInt;
53class DataLayout;
54class DominatorTree;
55class GEPOperator;
56class LLVMContext;
57class Loop;
58class LoopInfo;
59class raw_ostream;
60class ScalarEvolution;
61class SCEVAddRecExpr;
62class SCEVUnknown;
63class StructType;
65class Type;
66class VPSCEVExpander;
67enum SCEVTypes : unsigned short;
68
69LLVM_ABI extern bool VerifySCEV;
70
71/// NoWrapFlags are bitfield indices into SCEV's SubclassData.
72///
73/// Add and Mul expressions may have no-unsigned-wrap <NUW> or
74/// no-signed-wrap <NSW> properties, which are derived from the IR
75/// operator. NSW is a misnomer that we use to mean no signed overflow or
76/// underflow. NUW and NSW must hold for all subsets and orders of
77/// Add/Mul operands. That is, in `(a + b + c)<nsw>`, all of `a + b`,
78/// `b + c`, `a + c` must be nsw as well.
79///
80/// AddRec expressions may have a no-self-wraparound <NW> property if, in
81/// the integer domain, abs(step) * max-iteration(loop) <=
82/// unsigned-max(bitwidth). This means that the recurrence will never reach
83/// its start value if the step is non-zero. Computing the same value on
84/// each iteration is not considered wrapping, and recurrences with step = 0
85/// are trivially <NW>. <NW> is independent of the sign of step and the
86/// value the add recurrence starts with.
87///
88/// Note that NUW and NSW are also valid properties of a recurrence, and
89/// either implies NW. For convenience, NW will be set for a recurrence
90/// whenever either NUW or NSW are set.
91///
92/// We require that the flag on a SCEV apply to the entire scope in which
93/// that SCEV is defined. A SCEV's scope is set of locations dominated by
94/// a defining location, which is in turn described by the following rules:
95/// * A SCEVUnknown is at the point of definition of the Value.
96/// * A SCEVConstant is defined at all points.
97/// * A SCEVAddRec is defined starting with the header of the associated
98/// loop.
99/// * All other SCEVs are defined at the earlest point all operands are
100/// defined.
101///
102/// The above rules describe a maximally hoisted form (without regards to
103/// potential control dependence). A SCEV is defined anywhere a
104/// corresponding instruction could be defined in said maximally hoisted
105/// form. Note that SCEVUDivExpr (currently the only expression type which
106/// can trap) can be defined per these rules in regions where it would trap
107/// at runtime. A SCEV being defined does not require the existence of any
108/// instruction within the defined scope.
109enum class SCEVNoWrapFlags {
110 FlagAnyWrap = 0, // No guarantee.
111 FlagNW = (1 << 0), // No self-wrap.
112 FlagNUW = (1 << 1), // No unsigned wrap.
113 FlagNSW = (1 << 2), // No signed wrap.
114 NoWrapMask = (1 << 3) - 1,
115 LLVM_MARK_AS_BITMASK_ENUM(/*LargestValue=*/NoWrapMask)
116};
117
118class SCEV;
119
120template <typename SCEVPtrT = const SCEV *>
121struct SCEVUseT : private PointerIntPair<SCEVPtrT, 2> {
124 using Base::getPointer;
125
126 SCEVUseT() : Base(nullptr, 0) {}
127 SCEVUseT(SCEVPtrT S) : Base(S, 0) {}
128 /// Construct with NoWrapFlags; only NUW/NSW are encoded, NW is dropped.
129 SCEVUseT(SCEVPtrT S, SCEVNoWrapFlags Flags)
130 : Base(S, static_cast<unsigned>(Flags) >> 1) {}
131 template <typename OtherPtrT, typename = std::enable_if_t<
132 std::is_convertible_v<OtherPtrT, SCEVPtrT>>>
135
136 operator SCEVPtrT() const { return getPointer(); }
137 SCEVPtrT operator->() const { return getPointer(); }
138
139 /// Returns true if the SCEVUse is canonical, i.e. no SCEVUse flags set in any
140 /// operands.
141 bool isCanonical() const { return getCanonical() == getOpaqueValue(); }
142
143 /// Return the canonical SCEV for this SCEVUse.
144 const SCEV *getCanonical() const;
145
146 /// Return the no-wrap flags for this SCEVUse, which is the union of the
147 /// use-specific flags and the underlying SCEV's flags, masked by \p Mask.
150
151 /// Return only the use-specific no-wrap flags (NUW/NSW) without the
152 /// underlying SCEV's flags.
154 SCEVNoWrapFlags UseFlags =
155 static_cast<SCEVNoWrapFlags>(Base::getInt() << 1);
157 UseFlags |= SCEVNoWrapFlags::FlagNW;
158 return UseFlags;
159 }
160
161 bool operator==(const SCEVUseT &RHS) const {
162 return getOpaqueValue() == RHS.getOpaqueValue();
163 }
164
165 bool operator!=(const SCEVUseT &RHS) const { return !(*this == RHS); }
166
167 bool operator>(const SCEVUseT &RHS) const { return Base::operator>(RHS); }
168
169 bool operator==(const SCEV *RHS) const { return getOpaqueValue() == RHS; }
170 bool operator!=(const SCEV *RHS) const { return getOpaqueValue() != RHS; }
171
172 /// Print out the internal representation of this scalar to the specified
173 /// stream. This should really only be used for debugging purposes.
174 void print(raw_ostream &OS) const;
175
176 /// This method is used for debugging.
177 void dump() const;
178
179private:
181 friend struct PointerLikeTypeTraits<SCEVUseT>;
182};
183
184/// Deduction guide for various SCEV subclass pointers.
185template <typename SCEVPtrT> SCEVUseT(SCEVPtrT) -> SCEVUseT<SCEVPtrT>;
186
188
189/// Provide PointerLikeTypeTraits for SCEVUse, so it can be used with
190/// SmallPtrSet, among others.
191template <> struct PointerLikeTypeTraits<SCEVUse> {
192 static inline void *getAsVoidPointer(SCEVUse U) { return U.getOpaqueValue(); }
193 static inline SCEVUse getFromVoidPointer(void *P) {
194 SCEVUse U;
195 U.setFromOpaqueValue(P);
196 return U;
197 }
198
199 /// The Low bits are used by the PointerIntPair.
200 static constexpr int NumLowBitsAvailable = 0;
201};
202
203template <> struct DenseMapInfo<SCEVUse> {
204 static unsigned getHashValue(SCEVUse U) {
205 return hash_value(U.getOpaqueValue());
206 }
207
208 static bool isEqual(const SCEVUse LHS, const SCEVUse RHS) {
209 return LHS.getOpaqueValue() == RHS.getOpaqueValue();
210 }
211};
212
213template <> struct simplify_type<SCEVUse> {
214 using SimpleType = const SCEV *;
215
217 return Val.getPointer();
218 }
219};
220
221/// Provide CastInfo for SCEVUseT so that cast<SCEVUseT<const To *>>(use)
222/// returns SCEVUseT<const To *> with flags preserved.
223template <typename ToSCEVPtrT>
224struct CastInfo<SCEVUseT<ToSCEVPtrT>, SCEVUse,
225 std::enable_if_t<!is_simple_type<SCEVUse>::value>> {
226 using To = std::remove_cv_t<std::remove_pointer_t<ToSCEVPtrT>>;
228
229 static bool isPossible(const SCEVUse &U) { return isa<To>(U.getPointer()); }
230 static CastReturnType doCast(const SCEVUse &U) {
231 return CastReturnType(cast<To>(U.getPointer()), U.getUseNoWrapFlags());
232 }
233 static CastReturnType castFailed() { return CastReturnType(nullptr); }
235 if (!isPossible(U))
236 return castFailed();
237 return doCast(U);
238 }
239};
240
241template <typename ToSCEVPtrT>
242struct CastInfo<SCEVUseT<ToSCEVPtrT>, const SCEVUse,
243 std::enable_if_t<!is_simple_type<const SCEVUse>::value>>
244 : CastInfo<SCEVUseT<ToSCEVPtrT>, SCEVUse> {};
245
246/// This class represents an analyzed expression in the program. These are
247/// opaque objects that the client is not allowed to do much with directly.
248///
249class SCEV : public FoldingSetNode {
250 friend struct FoldingSetTrait<SCEV>;
251
252 /// A reference to an Interned FoldingSetNodeID for this node. The
253 /// ScalarEvolution's BumpPtrAllocator holds the data.
254 FoldingSetNodeIDRef FastID;
255
256 // The SCEV baseclass this node corresponds to
257 const SCEVTypes SCEVType;
258
259protected:
260 // Estimated complexity of this node's expression tree size.
261 const unsigned short ExpressionSize;
262
263 /// This field is initialized to zero and may be used in subclasses to store
264 /// miscellaneous information.
265 unsigned short SubclassData = 0;
266
267 /// Pointer to the canonical version of the SCEV, i.e. one where all operands
268 /// have no SCEVUse flags.
269 const SCEV *CanonicalSCEV = nullptr;
270
271public:
274 static constexpr auto FlagNW = SCEVNoWrapFlags::FlagNW;
275 static constexpr auto FlagNUW = SCEVNoWrapFlags::FlagNUW;
276 static constexpr auto FlagNSW = SCEVNoWrapFlags::FlagNSW;
278
279 explicit SCEV(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy,
280 unsigned short ExpressionSize)
281 : FastID(ID), SCEVType(SCEVTy), ExpressionSize(ExpressionSize) {}
282 SCEV(const SCEV &) = delete;
283 SCEV &operator=(const SCEV &) = delete;
284
285 SCEVTypes getSCEVType() const { return SCEVType; }
286
287 /// Return the LLVM type of this SCEV expression.
288 LLVM_ABI Type *getType() const;
289
290 /// Return operands of this SCEV expression.
292
293 /// Return true if the expression is a constant zero.
294 LLVM_ABI bool isZero() const;
295
296 /// Return true if the expression is a constant one.
297 LLVM_ABI bool isOne() const;
298
299 /// Return true if the expression is a constant all-ones value.
300 LLVM_ABI bool isAllOnesValue() const;
301
302 /// Return true if the specified scev is negated, but not a constant.
303 LLVM_ABI bool isNonConstantNegative() const;
304
305 // Returns estimated size of the mathematical expression represented by this
306 // SCEV. The rules of its calculation are following:
307 // 1) Size of a SCEV without operands (like constants and SCEVUnknown) is 1;
308 // 2) Size SCEV with operands Op1, Op2, ..., OpN is calculated by formula:
309 // (1 + Size(Op1) + ... + Size(OpN)).
310 // This value gives us an estimation of time we need to traverse through this
311 // SCEV and all its operands recursively. We may use it to avoid performing
312 // heavy transformations on SCEVs of excessive size for sake of saving the
313 // compilation time.
314 unsigned short getExpressionSize() const {
315 return ExpressionSize;
316 }
317
318 /// Print out the internal representation of this scalar to the specified
319 /// stream. This should really only be used for debugging purposes.
320 LLVM_ABI void print(raw_ostream &OS) const;
321
322 /// This method is used for debugging.
323 LLVM_ABI void dump() const;
324
325 /// Compute and set the canonical SCEV, by constructing a SCEV with the same
326 /// operands, but all SCEVUse flags dropped.
328
329 /// Return the canonical SCEV.
330 const SCEV *getCanonical() const {
331 assert(CanonicalSCEV && "canonical SCEV not yet computed");
332 return CanonicalSCEV;
333 }
334};
335
336// Specialize FoldingSetTrait for SCEV to avoid needing to compute
337// temporary FoldingSetNodeID values.
338template <> struct FoldingSetTrait<SCEV> : DefaultFoldingSetTrait<SCEV> {
339 static void Profile(const SCEV &X, FoldingSetNodeID &ID) { ID = X.FastID; }
340
341 static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, unsigned IDHash,
342 FoldingSetNodeID &TempID) {
343 return ID == X.FastID;
344 }
345
346 static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) {
347 return X.FastID.ComputeHash();
348 }
349};
350
351inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) {
352 S.print(OS);
353 return OS;
354}
355
357 U.print(OS);
358 return OS;
359}
360
361/// An object of this class is returned by queries that could not be answered.
362/// For example, if you ask for the number of iterations of a linked-list
363/// traversal loop, you will get one of these. None of the standard SCEV
364/// operations are valid on this class, it is just a marker.
365struct SCEVCouldNotCompute : public SCEV {
367
368 /// Methods for support type inquiry through isa, cast, and dyn_cast:
369 LLVM_ABI static bool classof(const SCEV *S);
370};
371
372/// This class represents an assumption made using SCEV expressions which can
373/// be checked at run-time.
375 friend struct FoldingSetTrait<SCEVPredicate>;
376
377 /// A reference to an Interned FoldingSetNodeID for this node. The
378 /// ScalarEvolution's BumpPtrAllocator holds the data.
379 FoldingSetNodeIDRef FastID;
380
381public:
383
384protected:
386 ~SCEVPredicate() = default;
387 SCEVPredicate(const SCEVPredicate &) = default;
389
390public:
392
393 SCEVPredicateKind getKind() const { return Kind; }
394
395 /// Returns the estimated complexity of this predicate. This is roughly
396 /// measured in the number of run-time checks required.
397 virtual unsigned getComplexity() const { return 1; }
398
399 /// Returns true if the predicate is always true. This means that no
400 /// assumptions were made and nothing needs to be checked at run-time.
401 virtual bool isAlwaysTrue() const = 0;
402
403 /// Returns true if this predicate implies \p N.
404 virtual bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const = 0;
405
406 /// Prints a textual representation of this predicate with an indentation of
407 /// \p Depth.
408 virtual void print(raw_ostream &OS, unsigned Depth = 0) const = 0;
409};
410
412 P.print(OS);
413 return OS;
414}
415
416// Specialize FoldingSetTrait for SCEVPredicate to avoid needing to compute
417// temporary FoldingSetNodeID values.
418template <>
420 static void Profile(const SCEVPredicate &X, FoldingSetNodeID &ID) {
421 ID = X.FastID;
422 }
423
424 static bool Equals(const SCEVPredicate &X, const FoldingSetNodeID &ID,
425 unsigned IDHash, FoldingSetNodeID &TempID) {
426 return ID == X.FastID;
427 }
428
429 static unsigned ComputeHash(const SCEVPredicate &X,
430 FoldingSetNodeID &TempID) {
431 return X.FastID.ComputeHash();
432 }
433};
434
435/// This class represents an assumption that the expression LHS Pred RHS
436/// evaluates to true, and this can be checked at run-time.
438 /// We assume that LHS Pred RHS is true.
439 const ICmpInst::Predicate Pred;
440 const SCEV *LHS;
441 const SCEV *RHS;
442
443public:
445 const ICmpInst::Predicate Pred,
446 const SCEV *LHS, const SCEV *RHS);
447
448 /// Implementation of the SCEVPredicate interface
449 bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override;
450 void print(raw_ostream &OS, unsigned Depth = 0) const override;
451 bool isAlwaysTrue() const override;
452
453 ICmpInst::Predicate getPredicate() const { return Pred; }
454
455 /// Returns the left hand side of the predicate.
456 const SCEV *getLHS() const { return LHS; }
457
458 /// Returns the right hand side of the predicate.
459 const SCEV *getRHS() const { return RHS; }
460
461 /// Methods for support type inquiry through isa, cast, and dyn_cast:
462 static bool classof(const SCEVPredicate *P) {
463 return P->getKind() == P_Compare;
464 }
465};
466
467/// This class represents an assumption made on an AddRec expression. Given an
468/// affine AddRec expression {a,+,b}, we assume that it has the nssw or nusw
469/// flags (defined below) in the first X iterations of the loop, where X is a
470/// SCEV expression returned by getPredicatedBackedgeTakenCount).
471///
472/// Note that this does not imply that X is equal to the backedge taken
473/// count. This means that if we have a nusw predicate for i32 {0,+,1} with a
474/// predicated backedge taken count of X, we only guarantee that {0,+,1} has
475/// nusw in the first X iterations. {0,+,1} may still wrap in the loop if we
476/// have more than X iterations.
478public:
479 /// Similar to SCEV::NoWrapFlags, but with slightly different semantics
480 /// for FlagNUSW. The increment is considered to be signed, and a + b
481 /// (where b is the increment) is considered to wrap if:
482 /// zext(a + b) != zext(a) + sext(b)
483 ///
484 /// If Signed is a function that takes an n-bit tuple and maps to the
485 /// integer domain as the tuples value interpreted as twos complement,
486 /// and Unsigned a function that takes an n-bit tuple and maps to the
487 /// integer domain as the base two value of input tuple, then a + b
488 /// has IncrementNUSW iff:
489 ///
490 /// 0 <= Unsigned(a) + Signed(b) < 2^n
491 ///
492 /// The IncrementNSSW flag has identical semantics with SCEV::FlagNSW.
493 ///
494 /// Note that the IncrementNUSW flag is not commutative: if base + inc
495 /// has IncrementNUSW, then inc + base doesn't neccessarily have this
496 /// property. The reason for this is that this is used for sign/zero
497 /// extending affine AddRec SCEV expressions when a SCEVWrapPredicate is
498 /// assumed. A {base,+,inc} expression is already non-commutative with
499 /// regards to base and inc, since it is interpreted as:
500 /// (((base + inc) + inc) + inc) ...
502 IncrementAnyWrap = 0, // No guarantee.
503 IncrementNUSW = (1 << 0), // No unsigned with signed increment wrap.
504 IncrementNSSW = (1 << 1), // No signed with signed increment wrap
505 // (equivalent with SCEV::NSW)
506 IncrementNoWrapMask = (1 << 2) - 1
507 };
508
509 /// Convenient IncrementWrapFlags manipulation methods.
510 [[nodiscard]] static SCEVWrapPredicate::IncrementWrapFlags
513 assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
514 assert((OffFlags & IncrementNoWrapMask) == OffFlags &&
515 "Invalid flags value!");
516 return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & ~OffFlags);
517 }
518
519 [[nodiscard]] static SCEVWrapPredicate::IncrementWrapFlags
521 assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
522 assert((Mask & IncrementNoWrapMask) == Mask && "Invalid mask value!");
523
524 return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & Mask);
525 }
526
527 [[nodiscard]] static SCEVWrapPredicate::IncrementWrapFlags
530 assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
531 assert((OnFlags & IncrementNoWrapMask) == OnFlags &&
532 "Invalid flags value!");
533
534 return (SCEVWrapPredicate::IncrementWrapFlags)(Flags | OnFlags);
535 }
536
537 /// Returns the set of SCEVWrapPredicate no wrap flags implied by a
538 /// SCEVAddRecExpr.
539 [[nodiscard]] static SCEVWrapPredicate::IncrementWrapFlags
540 getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE);
541
542private:
543 const SCEVAddRecExpr *AR;
544 IncrementWrapFlags Flags;
545
546public:
548 const SCEVAddRecExpr *AR,
549 IncrementWrapFlags Flags);
550
551 /// Returns the set assumed no overflow flags.
552 IncrementWrapFlags getFlags() const { return Flags; }
553
554 /// Implementation of the SCEVPredicate interface
555 const SCEVAddRecExpr *getExpr() const;
556 bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override;
557 void print(raw_ostream &OS, unsigned Depth = 0) const override;
558 bool isAlwaysTrue() const override;
559
560 /// Methods for support type inquiry through isa, cast, and dyn_cast:
561 static bool classof(const SCEVPredicate *P) {
562 return P->getKind() == P_Wrap;
563 }
564};
565
566/// This class represents a composition of other SCEV predicates, and is the
567/// class that most clients will interact with. This is equivalent to a
568/// logical "AND" of all the predicates in the union.
569///
570/// NB! Unlike other SCEVPredicate sub-classes this class does not live in the
571/// ScalarEvolution::Preds folding set. This is why the \c add function is sound.
573private:
574 using PredicateMap =
576
577 /// Vector with references to all predicates in this union.
579
580 /// Adds a predicate to this union.
581 void add(const SCEVPredicate *N, ScalarEvolution &SE);
582
583public:
585 ScalarEvolution &SE);
586
588
589 /// Returns a new SCEVUnionPredicate that is the union of this predicate
590 /// and the given predicate \p N.
592 ScalarEvolution &SE) const {
593 SCEVUnionPredicate Result(Preds, SE);
594 Result.add(N, SE);
595 return Result;
596 }
597
598 /// Implementation of the SCEVPredicate interface
599 bool isAlwaysTrue() const override;
600 bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override;
601 void print(raw_ostream &OS, unsigned Depth) const override;
602
603 /// We estimate the complexity of a union predicate as the size number of
604 /// predicates in the union.
605 unsigned getComplexity() const override { return Preds.size(); }
606
607 /// Methods for support type inquiry through isa, cast, and dyn_cast:
608 static bool classof(const SCEVPredicate *P) {
609 return P->getKind() == P_Union;
610 }
611};
612
613/// The main scalar evolution driver. Because client code (intentionally)
614/// can't do much with the SCEV objects directly, they must ask this class
615/// for services.
618
619public:
620 /// An enum describing the relationship between a SCEV and a loop.
622 LoopVariant, ///< The SCEV is loop-variant (unknown).
623 LoopInvariant, ///< The SCEV is loop-invariant.
624 LoopUniform, ///< The SCEV is loop-uniform.
625 LoopComputable ///< The SCEV varies predictably with the loop.
626 };
627
628 /// An enum describing the relationship between a SCEV and a basic block.
630 DoesNotDominateBlock, ///< The SCEV does not dominate the block.
631 DominatesBlock, ///< The SCEV dominates the block.
632 ProperlyDominatesBlock ///< The SCEV properly dominates the block.
633 };
634
635 /// Convenient NoWrapFlags manipulation. TODO: Replace with & operator of
636 /// enum class.
638 SCEV::NoWrapFlags Mask) {
639 return Flags & Mask;
640 }
641 [[nodiscard]] static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags,
642 SCEV::NoWrapFlags OnFlags) {
643 return Flags | OnFlags;
644 }
645 [[nodiscard]] static SCEV::NoWrapFlags
647 return Flags & ~OffFlags;
648 }
649 [[nodiscard]] static bool hasFlags(SCEV::NoWrapFlags Flags,
650 SCEV::NoWrapFlags TestFlags) {
651 return TestFlags == maskFlags(Flags, TestFlags);
652 };
653
656 LoopInfo &LI);
659
660 LLVMContext &getContext() const { return F.getContext(); }
661
662 /// Test if values of the given type are analyzable within the SCEV
663 /// framework. This primarily includes integer types, and it can optionally
664 /// include pointer types if the ScalarEvolution class has access to
665 /// target-specific information.
666 LLVM_ABI bool isSCEVable(Type *Ty) const;
667
668 /// Return the size in bits of the specified type, for which isSCEVable must
669 /// return true.
671
672 /// Return a type with the same bitwidth as the given type and which
673 /// represents how SCEV will treat the given type, for which isSCEVable must
674 /// return true. For pointer types, this is the pointer-sized integer type.
676
677 // Returns a wider type among {Ty1, Ty2}.
678 LLVM_ABI Type *getWiderType(Type *Ty1, Type *Ty2) const;
679
680 /// Return true if there exists a point in the program at which both
681 /// A and B could be operands to the same instruction.
682 /// SCEV expressions are generally assumed to correspond to instructions
683 /// which could exists in IR. In general, this requires that there exists
684 /// a use point in the program where all operands dominate the use.
685 ///
686 /// Example:
687 /// loop {
688 /// if
689 /// loop { v1 = load @global1; }
690 /// else
691 /// loop { v2 = load @global2; }
692 /// }
693 /// No SCEV with operand V1, and v2 can exist in this program.
695
696 /// Return true if the SCEV is a scAddRecExpr or it contains
697 /// scAddRecExpr. The result will be cached in HasRecMap.
698 LLVM_ABI bool containsAddRecurrence(const SCEV *S);
699
700 /// Is operation \p BinOp between \p LHS and \p RHS provably does not have
701 /// a signed/unsigned overflow (\p Signed)? If \p CtxI is specified, the
702 /// no-overflow fact should be true in the context of this instruction.
704 const SCEV *LHS, const SCEV *RHS,
705 const Instruction *CtxI = nullptr);
706
707 /// Parse NSW/NUW flags from add/sub/mul IR binary operation \p Op into
708 /// SCEV no-wrap flags, and deduce flag[s] that aren't known yet.
709 /// Does not mutate the original instruction. Returns std::nullopt if it could
710 /// not deduce more precise flags than the instruction already has, otherwise
711 /// returns proven flags.
712 LLVM_ABI std::optional<SCEV::NoWrapFlags>
714
715 /// Notify this ScalarEvolution that \p User directly uses SCEVs in \p Ops.
718
719 /// Return true if the SCEV expression contains an undef value.
720 LLVM_ABI bool containsUndefs(const SCEV *S) const;
721
722 /// Return true if the SCEV expression contains a Value that has been
723 /// optimised out and is now a nullptr.
724 LLVM_ABI bool containsErasedValue(const SCEV *S) const;
725
726 /// Return a SCEV expression for the full generality of the specified
727 /// expression.
728 LLVM_ABI const SCEV *getSCEV(Value *V);
729
730 /// Return an existing SCEV for V if there is one, otherwise return nullptr.
732
734 LLVM_ABI const SCEV *getConstant(const APInt &Val);
735 LLVM_ABI const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false);
737
738 LLVM_ABI const SCEV *getPtrToAddrExpr(const SCEV *Op);
739 LLVM_ABI const SCEV *getPtrToIntExpr(const SCEV *Op, Type *Ty);
740 LLVM_ABI const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty,
741 unsigned Depth = 0);
742 LLVM_ABI const SCEV *getVScale(Type *Ty);
743 LLVM_ABI const SCEV *
746 LLVM_ABI const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty,
747 unsigned Depth = 0);
748 LLVM_ABI const SCEV *getZeroExtendExprImpl(const SCEV *Op, Type *Ty,
749 unsigned Depth = 0);
750 LLVM_ABI const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty,
751 unsigned Depth = 0);
752 LLVM_ABI const SCEV *getSignExtendExprImpl(const SCEV *Op, Type *Ty,
753 unsigned Depth = 0);
754 LLVM_ABI const SCEV *getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty);
755 LLVM_ABI const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty);
756
759 unsigned Depth = 0);
762 unsigned Depth = 0) {
764 return getAddExpr(Ops, Flags, Depth);
765 }
766 const SCEV *getAddExpr(SCEVUse Op0, SCEVUse Op1, SCEVUse Op2,
768 unsigned Depth = 0) {
769 SmallVector<SCEVUse, 3> Ops = {Op0, Op1, Op2};
770 return getAddExpr(Ops, Flags, Depth);
771 }
774 unsigned Depth = 0);
777 unsigned Depth = 0) {
779 return getMulExpr(Ops, Flags, Depth);
780 }
781 const SCEV *getMulExpr(SCEVUse Op0, SCEVUse Op1, SCEVUse Op2,
783 unsigned Depth = 0) {
784 SmallVector<SCEVUse, 3> Ops = {Op0, Op1, Op2};
785 return getMulExpr(Ops, Flags, Depth);
786 }
790 LLVM_ABI const SCEV *getAddRecExpr(SCEVUse Start, SCEVUse Step, const Loop *L,
791 SCEV::NoWrapFlags Flags);
793 const Loop *L, SCEV::NoWrapFlags Flags);
795 const Loop *L, SCEV::NoWrapFlags Flags) {
796 SmallVector<SCEVUse, 4> NewOp(Operands.begin(), Operands.end());
797 return getAddRecExpr(NewOp, L, Flags);
798 }
799
800 /// Checks if \p SymbolicPHI can be rewritten as an AddRecExpr under some
801 /// Predicates. If successful return these <AddRecExpr, Predicates>;
802 /// The function is intended to be called from PSCEV (the caller will decide
803 /// whether to actually add the predicates and carry out the rewrites).
804 LLVM_ABI std::optional<
805 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
806 createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI);
807
808 /// Returns an expression for a GEP
809 ///
810 /// \p GEP The GEP. The indices contained in the GEP itself are ignored,
811 /// instead we use IndexExprs.
812 /// \p IndexExprs The expressions for the indices.
814 ArrayRef<SCEVUse> IndexExprs);
815 LLVM_ABI const SCEV *getGEPExpr(SCEVUse BaseExpr,
816 ArrayRef<SCEVUse> IndexExprs,
817 Type *SrcElementTy,
819 LLVM_ABI const SCEV *getAbsExpr(const SCEV *Op, bool IsNSW);
821 SmallVectorImpl<SCEVUse> &Operands);
822 LLVM_ABI const SCEV *
831 bool Sequential = false);
833 bool Sequential = false);
834 LLVM_ABI const SCEV *getUnknown(Value *V);
836
837 /// Return a SCEV for the constant 0 of a specific type.
838 const SCEV *getZero(Type *Ty) { return getConstant(Ty, 0); }
839
840 /// Return a SCEV for the constant 1 of a specific type.
841 const SCEV *getOne(Type *Ty) { return getConstant(Ty, 1); }
842
843 /// Return a SCEV for the constant \p Power of two.
844 const SCEV *getPowerOfTwo(Type *Ty, unsigned Power) {
845 assert(Power < getTypeSizeInBits(Ty) && "Power out of range");
847 }
848
849 /// Return a SCEV for the constant -1 of a specific type.
850 const SCEV *getMinusOne(Type *Ty) {
851 return getConstant(Ty, -1, /*isSigned=*/true);
852 }
853
854 /// Return an expression for a TypeSize.
856
857 /// Return an expression for the alloc size of AllocTy that is type IntTy
858 LLVM_ABI const SCEV *getSizeOfExpr(Type *IntTy, Type *AllocTy);
859
860 /// Return an expression for the store size of StoreTy that is type IntTy
861 LLVM_ABI const SCEV *getStoreSizeOfExpr(Type *IntTy, Type *StoreTy);
862
863 /// Return an expression for offsetof on the given field with type IntTy
864 LLVM_ABI const SCEV *getOffsetOfExpr(Type *IntTy, StructType *STy,
865 unsigned FieldNo);
866
867 /// Return the SCEV object corresponding to -V.
868 LLVM_ABI const SCEV *
870
871 /// Return the SCEV object corresponding to ~V.
872 LLVM_ABI const SCEV *getNotSCEV(const SCEV *V);
873
874 /// Return LHS-RHS. Minus is represented in SCEV as A+B*-1.
875 ///
876 /// If the LHS and RHS are pointers which don't share a common base
877 /// (according to getPointerBase()), this returns a SCEVCouldNotCompute.
878 /// To compute the difference between two unrelated pointers, you can
879 /// explicitly convert the arguments using getPtrToIntExpr(), for pointer
880 /// types that support it.
883 unsigned Depth = 0);
884
885 /// Compute ceil(N / D). N and D are treated as unsigned values.
886 ///
887 /// Since SCEV doesn't have native ceiling division, this generates a
888 /// SCEV expression of the following form:
889 ///
890 /// umin(N, 1) + floor((N - umin(N, 1)) / D)
891 ///
892 /// A denominator of zero or poison is handled the same way as getUDivExpr().
893 LLVM_ABI const SCEV *getUDivCeilSCEV(const SCEV *N, const SCEV *D);
894
895 /// Return a SCEV corresponding to a conversion of the input value to the
896 /// specified type. If the type must be extended, it is zero extended.
897 LLVM_ABI const SCEV *getTruncateOrZeroExtend(const SCEV *V, Type *Ty,
898 unsigned Depth = 0);
899
900 /// Return a SCEV corresponding to a conversion of the input value to the
901 /// specified type. If the type must be extended, it is sign extended.
902 LLVM_ABI const SCEV *getTruncateOrSignExtend(const SCEV *V, Type *Ty,
903 unsigned Depth = 0);
904
905 /// Return a SCEV corresponding to a conversion of the input value to the
906 /// specified type. If the type must be extended, it is zero extended. The
907 /// conversion must not be narrowing.
908 LLVM_ABI const SCEV *getNoopOrZeroExtend(const SCEV *V, Type *Ty);
909
910 /// Return a SCEV corresponding to a conversion of the input value to the
911 /// specified type. If the type must be extended, it is sign extended. The
912 /// conversion must not be narrowing.
913 LLVM_ABI const SCEV *getNoopOrSignExtend(const SCEV *V, Type *Ty);
914
915 /// Return a SCEV corresponding to a conversion of the input value to the
916 /// specified type. If the type must be extended, it is extended with
917 /// unspecified bits. The conversion must not be narrowing.
918 LLVM_ABI const SCEV *getNoopOrAnyExtend(const SCEV *V, Type *Ty);
919
920 /// Return a SCEV corresponding to a conversion of the input value to the
921 /// specified type. The conversion must not be widening.
922 LLVM_ABI const SCEV *getTruncateOrNoop(const SCEV *V, Type *Ty);
923
924 /// Promote the operands to the wider of the types using zero-extension, and
925 /// then perform a umax operation with them.
927 const SCEV *RHS);
928
929 /// Promote the operands to the wider of the types using zero-extension, and
930 /// then perform a umin operation with them.
932 const SCEV *RHS,
933 bool Sequential = false);
934
935 /// Promote the operands to the wider of the types using zero-extension, and
936 /// then perform a umin operation with them. N-ary function.
938 bool Sequential = false);
939
940 /// Transitively follow the chain of pointer-type operands until reaching a
941 /// SCEV that does not have a single pointer operand. This returns a
942 /// SCEVUnknown pointer for well-formed pointer-type expressions, but corner
943 /// cases do exist.
944 LLVM_ABI const SCEV *getPointerBase(const SCEV *V);
945
946 /// Compute an expression equivalent to S - getPointerBase(S).
947 LLVM_ABI const SCEV *removePointerBase(const SCEV *S);
948
949 /// Return a SCEV expression for the specified value at the specified scope
950 /// in the program. The L value specifies a loop nest to evaluate the
951 /// expression at, where null is the top-level or a specified loop is
952 /// immediately inside of the loop.
953 ///
954 /// This method can be used to compute the exit value for a variable defined
955 /// in a loop by querying what the value will hold in the parent loop.
956 ///
957 /// In the case that a relevant loop exit value cannot be computed, the
958 /// original value V is returned.
959 LLVM_ABI const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L);
960
961 /// This is a convenience function which does getSCEVAtScope(getSCEV(V), L).
962 LLVM_ABI const SCEV *getSCEVAtScope(Value *V, const Loop *L);
963
964 /// Test whether entry to the loop is protected by a conditional between LHS
965 /// and RHS. This is used to help avoid max expressions in loop trip
966 /// counts, and to eliminate casts.
968 const SCEV *LHS, const SCEV *RHS);
969
970 /// Test whether entry to the basic block is protected by a conditional
971 /// between LHS and RHS.
973 CmpPredicate Pred,
974 const SCEV *LHS,
975 const SCEV *RHS);
976
977 /// Test whether the backedge of the loop is protected by a conditional
978 /// between LHS and RHS. This is used to eliminate casts.
980 const SCEV *LHS, const SCEV *RHS);
981
982 /// A version of getTripCountFromExitCount below which always picks an
983 /// evaluation type which can not result in overflow.
984 LLVM_ABI const SCEV *getTripCountFromExitCount(const SCEV *ExitCount);
985
986 /// Convert from an "exit count" (i.e. "backedge taken count") to a "trip
987 /// count". A "trip count" is the number of times the header of the loop
988 /// will execute if an exit is taken after the specified number of backedges
989 /// have been taken. (e.g. TripCount = ExitCount + 1). Note that the
990 /// expression can overflow if ExitCount = UINT_MAX. If EvalTy is not wide
991 /// enough to hold the result without overflow, result unsigned wraps with
992 /// 2s-complement semantics. ex: EC = 255 (i8), TC = 0 (i8)
993 LLVM_ABI const SCEV *getTripCountFromExitCount(const SCEV *ExitCount,
994 Type *EvalTy, const Loop *L);
995
996 /// Returns the exact trip count of the loop if we can compute it, and
997 /// the result is a small constant. '0' is used to represent an unknown
998 /// or non-constant trip count. Note that a trip count is simply one more
999 /// than the backedge taken count for the loop.
1000 LLVM_ABI unsigned getSmallConstantTripCount(const Loop *L);
1001
1002 /// Return the exact trip count for this loop if we exit through ExitingBlock.
1003 /// '0' is used to represent an unknown or non-constant trip count. Note
1004 /// that a trip count is simply one more than the backedge taken count for
1005 /// the same exit.
1006 /// This "trip count" assumes that control exits via ExitingBlock. More
1007 /// precisely, it is the number of times that control will reach ExitingBlock
1008 /// before taking the branch. For loops with multiple exits, it may not be
1009 /// the number times that the loop header executes if the loop exits
1010 /// prematurely via another branch.
1011 LLVM_ABI unsigned getSmallConstantTripCount(const Loop *L,
1012 const BasicBlock *ExitingBlock);
1013
1014 /// Returns the upper bound of the loop trip count as a normal unsigned
1015 /// value.
1016 /// Returns 0 if the trip count is unknown, not constant or requires
1017 /// SCEV predicates and \p Predicates is nullptr.
1019 const Loop *L,
1020 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr);
1021
1022 /// Returns the largest constant divisor of the trip count as a normal
1023 /// unsigned value, if possible. This means that the actual trip count is
1024 /// always a multiple of the returned value. Returns 1 if the trip count is
1025 /// unknown or not guaranteed to be the multiple of a constant., Will also
1026 /// return 1 if the trip count is very large (>= 2^32).
1027 /// Note that the argument is an exit count for loop L, NOT a trip count.
1028 LLVM_ABI unsigned getSmallConstantTripMultiple(const Loop *L,
1029 const SCEV *ExitCount);
1030
1031 /// Returns the largest constant divisor of the trip count of the
1032 /// loop. Will return 1 if no trip count could be computed, or if a
1033 /// divisor could not be found.
1034 LLVM_ABI unsigned getSmallConstantTripMultiple(const Loop *L);
1035
1036 /// Returns the largest constant divisor of the trip count of this loop as a
1037 /// normal unsigned value, if possible. This means that the actual trip
1038 /// count is always a multiple of the returned value (don't forget the trip
1039 /// count could very well be zero as well!). As explained in the comments
1040 /// for getSmallConstantTripCount, this assumes that control exits the loop
1041 /// via ExitingBlock.
1042 LLVM_ABI unsigned
1043 getSmallConstantTripMultiple(const Loop *L, const BasicBlock *ExitingBlock);
1044
1045 /// The terms "backedge taken count" and "exit count" are used
1046 /// interchangeably to refer to the number of times the backedge of a loop
1047 /// has executed before the loop is exited.
1049 /// An expression exactly describing the number of times the backedge has
1050 /// executed when a loop is exited.
1052 /// A constant which provides an upper bound on the exact trip count.
1054 /// An expression which provides an upper bound on the exact trip count.
1056 };
1057
1058 /// Return the number of times the backedge executes before the given exit
1059 /// would be taken; if not exactly computable, return SCEVCouldNotCompute.
1060 /// For a single exit loop, this value is equivelent to the result of
1061 /// getBackedgeTakenCount. The loop is guaranteed to exit (via *some* exit)
1062 /// before the backedge is executed (ExitCount + 1) times. Note that there
1063 /// is no guarantee about *which* exit is taken on the exiting iteration.
1064 LLVM_ABI const SCEV *getExitCount(const Loop *L,
1065 const BasicBlock *ExitingBlock,
1066 ExitCountKind Kind = Exact);
1067
1068 /// Same as above except this uses the predicated backedge taken info and
1069 /// may require predicates.
1070 LLVM_ABI const SCEV *
1071 getPredicatedExitCount(const Loop *L, const BasicBlock *ExitingBlock,
1073 ExitCountKind Kind = Exact);
1074
1075 /// If the specified loop has a predictable backedge-taken count, return it,
1076 /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count is
1077 /// the number of times the loop header will be branched to from within the
1078 /// loop, assuming there are no abnormal exists like exception throws. This is
1079 /// one less than the trip count of the loop, since it doesn't count the first
1080 /// iteration, when the header is branched to from outside the loop.
1081 ///
1082 /// Note that it is not valid to call this method on a loop without a
1083 /// loop-invariant backedge-taken count (see
1084 /// hasLoopInvariantBackedgeTakenCount).
1085 LLVM_ABI const SCEV *getBackedgeTakenCount(const Loop *L,
1086 ExitCountKind Kind = Exact);
1087
1088 /// Similar to getBackedgeTakenCount, except it will add a set of
1089 /// SCEV predicates to Predicates that are required to be true in order for
1090 /// the answer to be correct. Predicates can be checked with run-time
1091 /// checks and can be used to perform loop versioning.
1093 const Loop *L, SmallVectorImpl<const SCEVPredicate *> &Predicates);
1094
1095 /// When successful, this returns a SCEVConstant that is greater than or equal
1096 /// to (i.e. a "conservative over-approximation") of the value returend by
1097 /// getBackedgeTakenCount. If such a value cannot be computed, it returns the
1098 /// SCEVCouldNotCompute object.
1102
1103 /// Similar to getConstantMaxBackedgeTakenCount, except it will add a set of
1104 /// SCEV predicates to Predicates that are required to be true in order for
1105 /// the answer to be correct. Predicates can be checked with run-time
1106 /// checks and can be used to perform loop versioning.
1108 const Loop *L, SmallVectorImpl<const SCEVPredicate *> &Predicates);
1109
1110 /// When successful, this returns a SCEV that is greater than or equal
1111 /// to (i.e. a "conservative over-approximation") of the value returend by
1112 /// getBackedgeTakenCount. If such a value cannot be computed, it returns the
1113 /// SCEVCouldNotCompute object.
1117
1118 /// Similar to getSymbolicMaxBackedgeTakenCount, except it will add a set of
1119 /// SCEV predicates to Predicates that are required to be true in order for
1120 /// the answer to be correct. Predicates can be checked with run-time
1121 /// checks and can be used to perform loop versioning.
1123 const Loop *L, SmallVectorImpl<const SCEVPredicate *> &Predicates);
1124
1125 /// Return true if the backedge taken count is either the value returned by
1126 /// getConstantMaxBackedgeTakenCount or zero.
1128
1129 /// Return true if the specified loop has an analyzable loop-invariant
1130 /// backedge-taken count.
1132
1133 // This method should be called by the client when it made any change that
1134 // would invalidate SCEV's answers, and the client wants to remove all loop
1135 // information held internally by ScalarEvolution. This is intended to be used
1136 // when the alternative to forget a loop is too expensive (i.e. large loop
1137 // bodies).
1138 LLVM_ABI void forgetAllLoops();
1139
1140 /// This method should be called by the client when it has changed a loop in
1141 /// a way that may effect ScalarEvolution's ability to compute a trip count,
1142 /// or if the loop is deleted. This call is potentially expensive for large
1143 /// loop bodies.
1144 LLVM_ABI void forgetLoop(const Loop *L);
1145
1146 // This method invokes forgetLoop for the outermost loop of the given loop
1147 // \p L, making ScalarEvolution forget about all this subtree. This needs to
1148 // be done whenever we make a transform that may affect the parameters of the
1149 // outer loop, such as exit counts for branches.
1150 LLVM_ABI void forgetTopmostLoop(const Loop *L);
1151
1152 /// This method should be called by the client when it has changed a value
1153 /// in a way that may effect its value, or which may disconnect it from a
1154 /// def-use chain linking it to a loop.
1155 LLVM_ABI void forgetValue(Value *V);
1156
1157 /// Forget LCSSA phi node V of loop L to which a new predecessor was added,
1158 /// such that it may no longer be trivial.
1160
1161 /// Called when the client has changed the disposition of values in
1162 /// this loop.
1163 ///
1164 /// We don't have a way to invalidate per-loop dispositions. Clear and
1165 /// recompute is simpler.
1167
1168 /// Called when the client has changed the disposition of values in
1169 /// a loop or block.
1170 ///
1171 /// We don't have a way to invalidate per-loop/per-block dispositions. Clear
1172 /// and recompute is simpler.
1174
1175 /// Determine the minimum number of zero bits that S is guaranteed to end in
1176 /// (at every loop iteration). It is, at the same time, the minimum number
1177 /// of times S is divisible by 2. For example, given {4,+,8} it returns 2.
1178 /// If S is guaranteed to be 0, it returns the bitwidth of S.
1179 /// If \p CtxI is not nullptr, return a constant multiple valid at \p CtxI.
1181 const Instruction *CtxI = nullptr);
1182
1183 /// Returns the max constant multiple of S. If \p CtxI is not nullptr, return
1184 /// a constant multiple valid at \p CtxI.
1186 const Instruction *CtxI = nullptr);
1187
1188 // Returns the max constant multiple of S. If S is exactly 0, return 1.
1190
1191 /// Determine the unsigned range for a particular SCEV.
1192 /// NOTE: This returns a copy of the reference returned by getRangeRef.
1194 return getRangeRef(S, HINT_RANGE_UNSIGNED);
1195 }
1196
1197 /// Determine the min of the unsigned range for a particular SCEV.
1199 return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMin();
1200 }
1201
1202 /// Determine the max of the unsigned range for a particular SCEV.
1204 return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMax();
1205 }
1206
1207 /// Determine the signed range for a particular SCEV.
1208 /// NOTE: This returns a copy of the reference returned by getRangeRef.
1210 return getRangeRef(S, HINT_RANGE_SIGNED);
1211 }
1212
1213 /// Determine the min of the signed range for a particular SCEV.
1215 return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMin();
1216 }
1217
1218 /// Determine the max of the signed range for a particular SCEV.
1220 return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMax();
1221 }
1222
1223 /// Test if the given expression is known to be negative.
1224 LLVM_ABI bool isKnownNegative(const SCEV *S);
1225
1226 /// Test if the given expression is known to be positive.
1227 LLVM_ABI bool isKnownPositive(const SCEV *S);
1228
1229 /// Test if the given expression is known to be non-negative.
1230 LLVM_ABI bool isKnownNonNegative(const SCEV *S);
1231
1232 /// Test if the given expression is known to be non-positive.
1233 LLVM_ABI bool isKnownNonPositive(const SCEV *S);
1234
1235 /// Test if the given expression is known to be non-zero.
1236 LLVM_ABI bool isKnownNonZero(const SCEV *S);
1237
1238 /// Test if the given expression is known to be a power of 2. OrNegative
1239 /// allows matching negative power of 2s, and OrZero allows matching 0.
1240 LLVM_ABI bool isKnownToBeAPowerOfTwo(const SCEV *S, bool OrZero = false,
1241 bool OrNegative = false);
1242
1243 /// Check that \p S is a multiple of \p M. When \p S is an AddRecExpr, \p S is
1244 /// a multiple of \p M if \p S starts with a multiple of \p M and at every
1245 /// iteration step \p S only adds multiples of \p M. \p Assumptions records
1246 /// the runtime predicates under which \p S is a multiple of \p M.
1247 LLVM_ABI bool
1248 isKnownMultipleOf(const SCEV *S, uint64_t M,
1250
1251 /// Return true if we know that S1 and S2 must have the same sign.
1252 LLVM_ABI bool haveSameSign(const SCEV *S1, const SCEV *S2);
1253
1254 /// Splits SCEV expression \p S into two SCEVs. One of them is obtained from
1255 /// \p S by substitution of all AddRec sub-expression related to loop \p L
1256 /// with initial value of that SCEV. The second is obtained from \p S by
1257 /// substitution of all AddRec sub-expressions related to loop \p L with post
1258 /// increment of this AddRec in the loop \p L. In both cases all other AddRec
1259 /// sub-expressions (not related to \p L) remain the same.
1260 /// If the \p S contains non-invariant unknown SCEV the function returns
1261 /// CouldNotCompute SCEV in both values of std::pair.
1262 /// For example, for SCEV S={0, +, 1}<L1> + {0, +, 1}<L2> and loop L=L1
1263 /// the function returns pair:
1264 /// first = {0, +, 1}<L2>
1265 /// second = {1, +, 1}<L1> + {0, +, 1}<L2>
1266 /// We can see that for the first AddRec sub-expression it was replaced with
1267 /// 0 (initial value) for the first element and to {1, +, 1}<L1> (post
1268 /// increment value) for the second one. In both cases AddRec expression
1269 /// related to L2 remains the same.
1270 LLVM_ABI std::pair<const SCEV *, const SCEV *>
1271 SplitIntoInitAndPostInc(const Loop *L, const SCEV *S);
1272
1273 /// We'd like to check the predicate on every iteration of the most dominated
1274 /// loop between loops used in LHS and RHS.
1275 /// To do this we use the following list of steps:
1276 /// 1. Collect set S all loops on which either LHS or RHS depend.
1277 /// 2. If S is non-empty
1278 /// a. Let PD be the element of S which is dominated by all other elements.
1279 /// b. Let E(LHS) be value of LHS on entry of PD.
1280 /// To get E(LHS), we should just take LHS and replace all AddRecs that are
1281 /// attached to PD on with their entry values.
1282 /// Define E(RHS) in the same way.
1283 /// c. Let B(LHS) be value of L on backedge of PD.
1284 /// To get B(LHS), we should just take LHS and replace all AddRecs that are
1285 /// attached to PD on with their backedge values.
1286 /// Define B(RHS) in the same way.
1287 /// d. Note that E(LHS) and E(RHS) are automatically available on entry of PD,
1288 /// so we can assert on that.
1289 /// e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) &&
1290 /// isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS))
1292 SCEVUse RHS);
1293
1294 /// Test if the given expression is known to satisfy the condition described
1295 /// by Pred, LHS, and RHS.
1297
1298 /// Check whether the condition described by Pred, LHS, and RHS is true or
1299 /// false. If we know it, return the evaluation of this condition. If neither
1300 /// is proved, return std::nullopt.
1301 LLVM_ABI std::optional<bool>
1302 evaluatePredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS);
1303
1304 /// Test if the given expression is known to satisfy the condition described
1305 /// by Pred, LHS, and RHS in the given Context.
1307 const SCEV *RHS, const Instruction *CtxI);
1308
1309 /// Check whether the condition described by Pred, LHS, and RHS is true or
1310 /// false in the given \p Context. If we know it, return the evaluation of
1311 /// this condition. If neither is proved, return std::nullopt.
1312 LLVM_ABI std::optional<bool> evaluatePredicateAt(CmpPredicate Pred,
1313 const SCEV *LHS,
1314 const SCEV *RHS,
1315 const Instruction *CtxI);
1316
1317 /// Test if the condition described by Pred, LHS, RHS is known to be true on
1318 /// every iteration of the loop of the recurrency LHS.
1320 const SCEVAddRecExpr *LHS,
1321 const SCEV *RHS);
1322
1323 /// Information about the number of loop iterations for which a loop exit's
1324 /// branch condition evaluates to the not-taken path. This is a temporary
1325 /// pair of exact and max expressions that are eventually summarized in
1326 /// ExitNotTakenInfo and BackedgeTakenInfo.
1327 struct ExitLimit {
1328 const SCEV *ExactNotTaken; // The exit is not taken exactly this many times
1329 const SCEV *ConstantMaxNotTaken; // The exit is not taken at most this many
1330 // times
1332
1333 // Not taken either exactly ConstantMaxNotTaken or zero times
1334 bool MaxOrZero = false;
1335
1336 /// A vector of predicate guards for this ExitLimit. The result is only
1337 /// valid if all of the predicates in \c Predicates evaluate to 'true' at
1338 /// run-time.
1340
1341 /// Construct either an exact exit limit from a constant, or an unknown
1342 /// one from a SCEVCouldNotCompute. No other types of SCEVs are allowed
1343 /// as arguments and asserts enforce that internally.
1344 /*implicit*/ LLVM_ABI ExitLimit(const SCEV *E);
1345 /*implicit*/ ExitLimit(SCEVUse E) : ExitLimit((const SCEV *)E) {}
1346
1347 LLVM_ABI
1348 ExitLimit(const SCEV *E, const SCEV *ConstantMaxNotTaken,
1349 const SCEV *SymbolicMaxNotTaken, bool MaxOrZero,
1351
1353 const SCEV *SymbolicMaxNotTaken, bool MaxOrZero,
1355
1356 /// Test whether this ExitLimit contains any computed information, or
1357 /// whether it's all SCEVCouldNotCompute values.
1362
1363 /// Test whether this ExitLimit contains all information.
1364 bool hasFullInfo() const {
1366 }
1367 };
1368
1369 /// Compute the number of times the backedge of the specified loop will
1370 /// execute if its exit condition were a conditional branch of ExitCond.
1371 ///
1372 /// \p ControlsOnlyExit is true if ExitCond directly controls the only exit
1373 /// branch. In this case, we can assume that the loop exits only if the
1374 /// condition is true and can infer that failing to meet the condition prior
1375 /// to integer wraparound results in undefined behavior.
1376 ///
1377 /// If \p AllowPredicates is set, this call will try to use a minimal set of
1378 /// SCEV predicates in order to return an exact answer.
1379 LLVM_ABI ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond,
1380 bool ExitIfTrue,
1381 bool ControlsOnlyExit,
1382 bool AllowPredicates = false);
1383
1384 /// A predicate is said to be monotonically increasing if may go from being
1385 /// false to being true as the loop iterates, but never the other way
1386 /// around. A predicate is said to be monotonically decreasing if may go
1387 /// from being true to being false as the loop iterates, but never the other
1388 /// way around.
1393
1394 /// If, for all loop invariant X, the predicate "LHS `Pred` X" is
1395 /// monotonically increasing or decreasing, returns
1396 /// Some(MonotonicallyIncreasing) and Some(MonotonicallyDecreasing)
1397 /// respectively. If we could not prove either of these facts, returns
1398 /// std::nullopt.
1399 LLVM_ABI std::optional<MonotonicPredicateType>
1401 ICmpInst::Predicate Pred);
1402
1411 /// If the result of the predicate LHS `Pred` RHS is loop invariant with
1412 /// respect to L, return a LoopInvariantPredicate with LHS and RHS being
1413 /// invariants, available at L's entry. Otherwise, return std::nullopt.
1414 LLVM_ABI std::optional<LoopInvariantPredicate>
1416 const Loop *L, const Instruction *CtxI = nullptr);
1417
1418 /// If the result of the predicate LHS `Pred` RHS is loop invariant with
1419 /// respect to L at given Context during at least first MaxIter iterations,
1420 /// return a LoopInvariantPredicate with LHS and RHS being invariants,
1421 /// available at L's entry. Otherwise, return std::nullopt. The predicate
1422 /// should be the loop's exit condition.
1423 LLVM_ABI std::optional<LoopInvariantPredicate>
1425 const SCEV *LHS,
1426 const SCEV *RHS, const Loop *L,
1427 const Instruction *CtxI,
1428 const SCEV *MaxIter);
1429
1430 LLVM_ABI std::optional<LoopInvariantPredicate>
1432 CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L,
1433 const Instruction *CtxI, const SCEV *MaxIter);
1434
1435 /// Simplify LHS and RHS in a comparison with predicate Pred. Return true
1436 /// iff any changes were made. If the operands are provably equal or
1437 /// unequal, LHS and RHS are set to the same value and Pred is set to either
1438 /// ICMP_EQ or ICMP_NE.
1440 SCEVUse &RHS, unsigned Depth = 0);
1441
1442 /// Return the "disposition" of the given SCEV with respect to the given
1443 /// loop.
1445
1446 /// Returns true if the given SCEV is loop-uniform with respect to the
1447 /// specified loop L.
1448 ///
1449 /// A SCEV is considered loop-uniform if its value is invariant across all
1450 /// iterations of L, meaning it does not depend on any induction variables
1451 /// or values that vary within L.
1452 ///
1453 /// This notion is particularly useful in nested loops, where a value may vary
1454 /// in an inner loop but remain invariant in an outer loop.
1455 ///
1456 /// Example:
1457 /// \code
1458 /// for (i)
1459 /// for (j)
1460 /// dep(j);
1461 /// dep(i, j);
1462 /// \endcode
1463 /// isLoopUniform(SCEV(dep(j)), loop_i) returns true, as `j` is independent of
1464 /// `i`.
1465 /// isLoopUniform(SCEV(dep(i, j)), loop_i) returns false, as the expression
1466 /// depends on `i`, which varies in loop_i.
1467 LLVM_ABI bool isLoopUniform(const SCEV *S, const Loop *L);
1468
1469 /// Return true if the value of the given SCEV is unchanging in the
1470 /// specified loop.
1471 LLVM_ABI bool isLoopInvariant(const SCEV *S, const Loop *L);
1472
1473 /// Determine if the SCEV can be evaluated at loop's entry. It is true if it
1474 /// doesn't depend on a SCEVUnknown of an instruction which is dominated by
1475 /// the header of loop L.
1476 LLVM_ABI bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L);
1477
1478 /// Return true if the given SCEV changes value in a known way in the
1479 /// specified loop. This property being true implies that the value is
1480 /// variant in the loop AND that we can emit an expression to compute the
1481 /// value of the expression at any particular loop iteration.
1482 LLVM_ABI bool hasComputableLoopEvolution(const SCEV *S, const Loop *L);
1483
1484 /// Return the "disposition" of the given SCEV with respect to the given
1485 /// block.
1487 const BasicBlock *BB);
1488
1489 /// Return true if elements that makes up the given SCEV dominate the
1490 /// specified basic block.
1491 LLVM_ABI bool dominates(const SCEV *S, const BasicBlock *BB);
1492
1493 /// Return true if elements that makes up the given SCEV properly dominate
1494 /// the specified basic block.
1495 LLVM_ABI bool properlyDominates(const SCEV *S, const BasicBlock *BB);
1496
1497 /// Test whether the given SCEV has Op as a direct or indirect operand.
1498 LLVM_ABI bool hasOperand(const SCEV *S, const SCEV *Op) const;
1499
1500 /// Return the size of an element read or written by Inst.
1502
1503 LLVM_ABI void print(raw_ostream &OS) const;
1504 LLVM_ABI void verify() const;
1506 FunctionAnalysisManager::Invalidator &Inv);
1507
1508 /// Return the DataLayout associated with the module this SCEV instance is
1509 /// operating on.
1510 const DataLayout &getDataLayout() const { return DL; }
1511
1513 const SCEV *RHS);
1515 const SCEV *LHS,
1516 const SCEV *RHS);
1517
1518 LLVM_ABI const SCEVPredicate *
1521
1522 /// Re-writes the SCEV according to the Predicates in \p A.
1523 LLVM_ABI const SCEV *rewriteUsingPredicate(const SCEV *S, const Loop *L,
1524 const SCEVPredicate &A);
1525 /// Tries to convert the \p S expression to an AddRec expression,
1526 /// adding additional predicates to \p Preds as required.
1528 const SCEV *S, const Loop *L,
1530
1531 /// Compute \p LHS - \p RHS and returns the result as an APInt if it is a
1532 /// constant, and std::nullopt if it isn't.
1533 ///
1534 /// This is intended to be a cheaper version of getMinusSCEV. We can be
1535 /// frugal here since we just bail out of actually constructing and
1536 /// canonicalizing an expression in the cases where the result isn't going
1537 /// to be a constant.
1538 LLVM_ABI std::optional<APInt> computeConstantDifference(const SCEV *LHS,
1539 const SCEV *RHS);
1540
1541 /// Update no-wrap flags of an AddRec. This may drop the cached info about
1542 /// this AddRec (such as range info) in case if new flags may potentially
1543 /// sharpen it.
1545
1546 class LoopGuards {
1549 bool PreserveNUW = false;
1550 bool PreserveNSW = false;
1551 ScalarEvolution &SE;
1552
1553 LoopGuards(ScalarEvolution &SE) : SE(SE) {}
1554
1555 /// Recursively collect loop guards in \p Guards, starting from
1556 /// block \p Block with predecessor \p Pred. The intended starting point
1557 /// is to collect from a loop header and its predecessor.
1558 static void
1559 collectFromBlock(ScalarEvolution &SE, ScalarEvolution::LoopGuards &Guards,
1560 const BasicBlock *Block, const BasicBlock *Pred,
1562 unsigned Depth = 0);
1563
1564 /// Collect loop guards in \p Guards, starting from PHINode \p
1565 /// Phi, by calling \p collectFromBlock on the incoming blocks of
1566 /// \Phi and trying to merge the found constraints into a single
1567 /// combined one for \p Phi.
1568 static void collectFromPHI(
1572 unsigned Depth);
1573
1574 public:
1575 /// Collect rewrite map for loop guards for loop \p L, together with flags
1576 /// indicating if NUW and NSW can be preserved during rewriting.
1577 LLVM_ABI static LoopGuards collect(const Loop *L, ScalarEvolution &SE);
1578
1579 /// Try to apply the collected loop guards to \p Expr.
1580 LLVM_ABI const SCEV *rewrite(const SCEV *Expr) const;
1581 };
1582
1583 /// Try to apply information from loop guards for \p L to \p Expr.
1584 LLVM_ABI const SCEV *applyLoopGuards(const SCEV *Expr, const Loop *L);
1585 LLVM_ABI const SCEV *applyLoopGuards(const SCEV *Expr,
1586 const LoopGuards &Guards);
1587
1588 /// Return true if the loop has no abnormal exits. That is, if the loop
1589 /// is not infinite, it must exit through an explicit edge in the CFG.
1590 /// (As opposed to either a) throwing out of the function or b) entering a
1591 /// well defined infinite loop in some callee.)
1593 return getLoopProperties(L).HasNoAbnormalExits;
1594 }
1595
1596 /// Return true if this loop is finite by assumption. That is,
1597 /// to be infinite, it must also be undefined.
1598 LLVM_ABI bool loopIsFiniteByAssumption(const Loop *L);
1599
1600 /// Return the set of Values that, if poison, will definitively result in S
1601 /// being poison as well. The returned set may be incomplete, i.e. there can
1602 /// be additional Values that also result in S being poison.
1603 LLVM_ABI void
1605 const SCEV *S);
1606
1607 /// Check whether it is poison-safe to represent the expression S using the
1608 /// instruction I. If such a replacement is performed, the poison flags of
1609 /// instructions in DropPoisonGeneratingInsts must be dropped.
1611 const SCEV *S, Instruction *I,
1612 SmallVectorImpl<Instruction *> &DropPoisonGeneratingInsts);
1613
1614 class FoldID {
1615 const SCEV *Op = nullptr;
1616 const Type *Ty = nullptr;
1617 unsigned short C;
1618
1619 public:
1620 FoldID(SCEVTypes C, const SCEV *Op, const Type *Ty) : Op(Op), Ty(Ty), C(C) {
1621 assert(Op);
1622 assert(Ty);
1623 }
1624
1625 FoldID(unsigned short C) : C(C) {}
1626
1627 unsigned computeHash() const {
1629 C, detail::combineHashValue(reinterpret_cast<uintptr_t>(Op),
1630 reinterpret_cast<uintptr_t>(Ty)));
1631 }
1632
1633 bool operator==(const FoldID &RHS) const {
1634 return std::tie(Op, Ty, C) == std::tie(RHS.Op, RHS.Ty, RHS.C);
1635 }
1636 };
1637
1638private:
1639 /// A CallbackVH to arrange for ScalarEvolution to be notified whenever a
1640 /// Value is deleted.
1641 class LLVM_ABI SCEVCallbackVH final : public CallbackVH {
1642 ScalarEvolution *SE;
1643
1644 void deleted() override;
1645 void allUsesReplacedWith(Value *New) override;
1646
1647 public:
1648 SCEVCallbackVH(Value *V, ScalarEvolution *SE = nullptr);
1649 };
1650
1651 friend class SCEVCallbackVH;
1652 friend class SCEVExpander;
1653 friend class SCEVUnknown;
1654 friend class VPSCEVExpander;
1655
1656 /// The function we are analyzing.
1657 Function &F;
1658
1659 /// Data layout of the module.
1660 const DataLayout &DL;
1661
1662 /// Does the module have any calls to the llvm.experimental.guard intrinsic
1663 /// at all? If this is false, we avoid doing work that will only help if
1664 /// thare are guards present in the IR.
1665 bool HasGuards;
1666
1667 /// The target library information for the target we are targeting.
1668 TargetLibraryInfo &TLI;
1669
1670 /// The tracker for \@llvm.assume intrinsics in this function.
1671 AssumptionCache &AC;
1672
1673 /// The dominator tree.
1674 DominatorTree &DT;
1675
1676 /// The loop information for the function we are currently analyzing.
1677 LoopInfo &LI;
1678
1679 /// This SCEV is used to represent unknown trip counts and things.
1680 std::unique_ptr<SCEVCouldNotCompute> CouldNotCompute;
1681
1682 /// The type for HasRecMap.
1683 using HasRecMapType = DenseMap<const SCEV *, bool>;
1684
1685 /// This is a cache to record whether a SCEV contains any scAddRecExpr.
1686 HasRecMapType HasRecMap;
1687
1688 /// The type for ExprValueMap.
1689 using ValueSetVector = SmallSetVector<Value *, 4>;
1690 using ExprValueMapType = DenseMap<const SCEV *, ValueSetVector>;
1691
1692 /// ExprValueMap -- This map records the original values from which
1693 /// the SCEV expr is generated from.
1694 ExprValueMapType ExprValueMap;
1695
1696 /// The type for ValueExprMap.
1697 using ValueExprMapType =
1699
1700 /// This is a cache of the values we have analyzed so far.
1701 ValueExprMapType ValueExprMap;
1702
1703 /// This is a cache for expressions that got folded to a different existing
1704 /// SCEV.
1707
1708 /// Mark predicate values currently being processed by isImpliedCond.
1709 SmallPtrSet<const Value *, 6> PendingLoopPredicates;
1710
1711 // Mark SCEVUnknown Phis currently being processed by isImpliedViaMerge.
1712 SmallPtrSet<const PHINode *, 6> PendingMerges;
1713
1714 /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of
1715 /// conditions dominating the backedge of a loop.
1716 bool WalkingBEDominatingConds = false;
1717
1718 /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a
1719 /// predicate by splitting it into a set of independent predicates.
1720 bool ProvingSplitPredicate = false;
1721
1722 /// Memoized values for the getConstantMultiple
1723 DenseMap<const SCEV *, APInt> ConstantMultipleCache;
1724
1725 /// Return the Value set from which the SCEV expr is generated.
1726 ArrayRef<Value *> getSCEVValues(const SCEV *S);
1727
1728 /// Private helper method for the getConstantMultiple method. If \p CtxI is
1729 /// not nullptr, return a constant multiple valid at \p CtxI.
1730 APInt getConstantMultipleImpl(const SCEV *S,
1731 const Instruction *Ctx = nullptr);
1732
1733 /// Information about the number of times a particular loop exit may be
1734 /// reached before exiting the loop.
1735 struct ExitNotTakenInfo {
1736 PoisoningVH<BasicBlock> ExitingBlock;
1737 const SCEV *ExactNotTaken;
1738 const SCEV *ConstantMaxNotTaken;
1739 const SCEV *SymbolicMaxNotTaken;
1741
1742 explicit ExitNotTakenInfo(PoisoningVH<BasicBlock> ExitingBlock,
1743 const SCEV *ExactNotTaken,
1744 const SCEV *ConstantMaxNotTaken,
1745 const SCEV *SymbolicMaxNotTaken,
1747 : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken),
1748 ConstantMaxNotTaken(ConstantMaxNotTaken),
1749 SymbolicMaxNotTaken(SymbolicMaxNotTaken), Predicates(Predicates) {}
1750
1751 bool hasAlwaysTruePredicate() const {
1752 return Predicates.empty();
1753 }
1754 };
1755
1756 /// Information about the backedge-taken count of a loop. This currently
1757 /// includes an exact count and a maximum count.
1758 ///
1759 class BackedgeTakenInfo {
1760 friend class ScalarEvolution;
1761
1762 /// A list of computable exits and their not-taken counts. Loops almost
1763 /// never have more than one computable exit.
1764 SmallVector<ExitNotTakenInfo, 1> ExitNotTaken;
1765
1766 /// Expression indicating the least constant maximum backedge-taken count of
1767 /// the loop that is known, or a SCEVCouldNotCompute. This expression is
1768 /// only valid if the predicates associated with all loop exits are true.
1769 const SCEV *ConstantMax = nullptr;
1770
1771 /// Indicating if \c ExitNotTaken has an element for every exiting block in
1772 /// the loop.
1773 bool IsComplete = false;
1774
1775 /// Expression indicating the least maximum backedge-taken count of the loop
1776 /// that is known, or a SCEVCouldNotCompute. Lazily computed on first query.
1777 const SCEV *SymbolicMax = nullptr;
1778
1779 /// True iff the backedge is taken either exactly Max or zero times.
1780 bool MaxOrZero = false;
1781
1782 bool isComplete() const { return IsComplete; }
1783 const SCEV *getConstantMax() const { return ConstantMax; }
1784
1785 LLVM_ABI const ExitNotTakenInfo *getExitNotTaken(
1786 const BasicBlock *ExitingBlock,
1787 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr) const;
1788
1789 public:
1790 BackedgeTakenInfo() = default;
1791 BackedgeTakenInfo(BackedgeTakenInfo &&) = default;
1792 BackedgeTakenInfo &operator=(BackedgeTakenInfo &&) = default;
1793
1794 using EdgeExitInfo = std::pair<BasicBlock *, ExitLimit>;
1795
1796 /// Initialize BackedgeTakenInfo from a list of exact exit counts.
1797 LLVM_ABI BackedgeTakenInfo(ArrayRef<EdgeExitInfo> ExitCounts,
1798 bool IsComplete, const SCEV *ConstantMax,
1799 bool MaxOrZero);
1800
1801 /// Test whether this BackedgeTakenInfo contains any computed information,
1802 /// or whether it's all SCEVCouldNotCompute values.
1803 bool hasAnyInfo() const {
1804 return !ExitNotTaken.empty() ||
1805 !isa<SCEVCouldNotCompute>(getConstantMax());
1806 }
1807
1808 /// Test whether this BackedgeTakenInfo contains complete information.
1809 bool hasFullInfo() const { return isComplete(); }
1810
1811 /// Return an expression indicating the exact *backedge-taken*
1812 /// count of the loop if it is known or SCEVCouldNotCompute
1813 /// otherwise. If execution makes it to the backedge on every
1814 /// iteration (i.e. there are no abnormal exists like exception
1815 /// throws and thread exits) then this is the number of times the
1816 /// loop header will execute minus one.
1817 ///
1818 /// If the SCEV predicate associated with the answer can be different
1819 /// from AlwaysTrue, we must add a (non null) Predicates argument.
1820 /// The SCEV predicate associated with the answer will be added to
1821 /// Predicates. A run-time check needs to be emitted for the SCEV
1822 /// predicate in order for the answer to be valid.
1823 ///
1824 /// Note that we should always know if we need to pass a predicate
1825 /// argument or not from the way the ExitCounts vector was computed.
1826 /// If we allowed SCEV predicates to be generated when populating this
1827 /// vector, this information can contain them and therefore a
1828 /// SCEVPredicate argument should be added to getExact.
1829 LLVM_ABI const SCEV *getExact(
1830 const Loop *L, ScalarEvolution *SE,
1831 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr) const;
1832
1833 /// Return the number of times this loop exit may fall through to the back
1834 /// edge, or SCEVCouldNotCompute. The loop is guaranteed not to exit via
1835 /// this block before this number of iterations, but may exit via another
1836 /// block. If \p Predicates is null the function returns CouldNotCompute if
1837 /// predicates are required, otherwise it fills in the required predicates.
1838 const SCEV *getExact(
1839 const BasicBlock *ExitingBlock, ScalarEvolution *SE,
1840 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr) const {
1841 if (auto *ENT = getExitNotTaken(ExitingBlock, Predicates))
1842 return ENT->ExactNotTaken;
1843 else
1844 return SE->getCouldNotCompute();
1845 }
1846
1847 /// Get the constant max backedge taken count for the loop.
1848 LLVM_ABI const SCEV *getConstantMax(
1849 ScalarEvolution *SE,
1850 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr) const;
1851
1852 /// Get the constant max backedge taken count for the particular loop exit.
1853 const SCEV *getConstantMax(
1854 const BasicBlock *ExitingBlock, ScalarEvolution *SE,
1855 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr) const {
1856 if (auto *ENT = getExitNotTaken(ExitingBlock, Predicates))
1857 return ENT->ConstantMaxNotTaken;
1858 else
1859 return SE->getCouldNotCompute();
1860 }
1861
1862 /// Get the symbolic max backedge taken count for the loop.
1863 LLVM_ABI const SCEV *getSymbolicMax(
1864 const Loop *L, ScalarEvolution *SE,
1865 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr);
1866
1867 /// Get the symbolic max backedge taken count for the particular loop exit.
1868 const SCEV *getSymbolicMax(
1869 const BasicBlock *ExitingBlock, ScalarEvolution *SE,
1870 SmallVectorImpl<const SCEVPredicate *> *Predicates = nullptr) const {
1871 if (auto *ENT = getExitNotTaken(ExitingBlock, Predicates))
1872 return ENT->SymbolicMaxNotTaken;
1873 else
1874 return SE->getCouldNotCompute();
1875 }
1876
1877 /// Return true if the number of times this backedge is taken is either the
1878 /// value returned by getConstantMax or zero.
1879 LLVM_ABI bool isConstantMaxOrZero(ScalarEvolution *SE) const;
1880 };
1881
1882 /// Cache the backedge-taken count of the loops for this function as they
1883 /// are computed.
1884 DenseMap<const Loop *, BackedgeTakenInfo> BackedgeTakenCounts;
1885
1886 /// Cache the predicated backedge-taken count of the loops for this
1887 /// function as they are computed.
1888 DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts;
1889
1890 /// Loops whose backedge taken counts directly use this non-constant SCEV.
1891 DenseMap<const SCEV *, SmallPtrSet<PointerIntPair<const Loop *, 1, bool>, 4>>
1892 BECountUsers;
1893
1894 /// This map contains entries for all of the PHI instructions that we
1895 /// attempt to compute constant evolutions for. This allows us to avoid
1896 /// potentially expensive recomputation of these properties. An instruction
1897 /// maps to null if we are unable to compute its exit value.
1898 DenseMap<PHINode *, Constant *> ConstantEvolutionLoopExitValue;
1899
1900 /// This map contains entries for all the expressions that we attempt to
1901 /// compute getSCEVAtScope information for, which can be expensive in
1902 /// extreme cases.
1903 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1904 ValuesAtScopes;
1905
1906 /// Reverse map for invalidation purposes: Stores of which SCEV and which
1907 /// loop this is the value-at-scope of.
1908 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1909 ValuesAtScopesUsers;
1910
1911 /// Memoized computeLoopDisposition results.
1912 DenseMap<const SCEV *,
1914 LoopDispositions;
1915
1916 struct LoopProperties {
1917 /// Set to true if the loop contains no instruction that can abnormally exit
1918 /// the loop (i.e. via throwing an exception, by terminating the thread
1919 /// cleanly or by infinite looping in a called function). Strictly
1920 /// speaking, the last one is not leaving the loop, but is identical to
1921 /// leaving the loop for reasoning about undefined behavior.
1922 bool HasNoAbnormalExits;
1923
1924 /// Set to true if the loop contains no instruction that can have side
1925 /// effects (i.e. via throwing an exception, volatile or atomic access).
1926 bool HasNoSideEffects;
1927 };
1928
1929 /// Cache for \c getLoopProperties.
1930 DenseMap<const Loop *, LoopProperties> LoopPropertiesCache;
1931
1932 /// Return a \c LoopProperties instance for \p L, creating one if necessary.
1933 LLVM_ABI LoopProperties getLoopProperties(const Loop *L);
1934
1935 bool loopHasNoSideEffects(const Loop *L) {
1936 return getLoopProperties(L).HasNoSideEffects;
1937 }
1938
1939 /// Compute a LoopDisposition value.
1940 LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L);
1941
1942 /// Memoized computeBlockDisposition results.
1943 DenseMap<
1944 const SCEV *,
1946 BlockDispositions;
1947
1948 /// Compute a BlockDisposition value.
1949 BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB);
1950
1951 /// Stores all SCEV that use a given SCEV as its direct operand.
1952 DenseMap<const SCEV *, SmallPtrSet<const SCEV *, 8> > SCEVUsers;
1953
1954 /// Memoized results from getRange
1955 DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
1956
1957 /// Memoized results from getRange
1958 DenseMap<const SCEV *, ConstantRange> SignedRanges;
1959
1960 /// Used to parameterize getRange
1961 enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED };
1962
1963 /// Set the memoized range for the given SCEV.
1964 const ConstantRange &setRange(const SCEV *S, RangeSignHint Hint,
1965 ConstantRange CR) {
1966 DenseMap<const SCEV *, ConstantRange> &Cache =
1967 Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges;
1968
1969 auto Pair = Cache.insert_or_assign(S, std::move(CR));
1970 return Pair.first->second;
1971 }
1972
1973 /// Determine the range for a particular SCEV.
1974 /// NOTE: This returns a reference to an entry in a cache. It must be
1975 /// copied if its needed for longer.
1976 LLVM_ABI const ConstantRange &getRangeRef(const SCEV *S, RangeSignHint Hint,
1977 unsigned Depth = 0);
1978
1979 /// Determine the range for a particular SCEV, but evaluates ranges for
1980 /// operands iteratively first.
1981 const ConstantRange &getRangeRefIter(const SCEV *S, RangeSignHint Hint);
1982
1983 /// Determines the range for the affine SCEVAddRecExpr {\p Start,+,\p Step}.
1984 /// Helper for \c getRange.
1985 ConstantRange getRangeForAffineAR(const SCEV *Start, const SCEV *Step,
1986 const APInt &MaxBECount);
1987
1988 /// Determines the range for the affine non-self-wrapping SCEVAddRecExpr {\p
1989 /// Start,+,\p Step}<nw>.
1990 ConstantRange getRangeForAffineNoSelfWrappingAR(const SCEVAddRecExpr *AddRec,
1991 const SCEV *MaxBECount,
1992 unsigned BitWidth,
1993 RangeSignHint SignHint);
1994
1995 /// Try to compute a range for the affine SCEVAddRecExpr {\p Start,+,\p
1996 /// Step} by "factoring out" a ternary expression from the add recurrence.
1997 /// Helper called by \c getRange.
1998 ConstantRange getRangeViaFactoring(const SCEV *Start, const SCEV *Step,
1999 const APInt &MaxBECount);
2000
2001 /// If the unknown expression U corresponds to a simple recurrence, return
2002 /// a constant range which represents the entire recurrence. Note that
2003 /// *add* recurrences with loop invariant steps aren't represented by
2004 /// SCEVUnknowns and thus don't use this mechanism.
2005 ConstantRange getRangeForUnknownRecurrence(const SCEVUnknown *U);
2006
2007 /// We know that there is no SCEV for the specified value. Analyze the
2008 /// expression recursively.
2009 const SCEV *createSCEV(Value *V);
2010
2011 /// We know that there is no SCEV for the specified value. Create a new SCEV
2012 /// for \p V iteratively.
2013 const SCEV *createSCEVIter(Value *V);
2014 /// Collect operands of \p V for which SCEV expressions should be constructed
2015 /// first. Returns a SCEV directly if it can be constructed trivially for \p
2016 /// V.
2017 const SCEV *getOperandsToCreate(Value *V, SmallVectorImpl<Value *> &Ops);
2018
2019 /// Returns SCEV for the first operand of a phi if all phi operands have
2020 /// identical opcodes and operands.
2021 const SCEV *createNodeForPHIWithIdenticalOperands(PHINode *PN);
2022
2023 /// Provide the special handling we need to analyze PHI SCEVs.
2024 const SCEV *createNodeForPHI(PHINode *PN);
2025
2026 /// Helper function called from createNodeForPHI.
2027 const SCEV *createAddRecFromPHI(PHINode *PN);
2028
2029 /// A helper function for createAddRecFromPHI to handle simple cases.
2030 const SCEV *createSimpleAffineAddRec(PHINode *PN, Value *BEValueV,
2031 Value *StartValueV);
2032
2033 /// Helper function called from createNodeForPHI.
2034 const SCEV *createNodeFromSelectLikePHI(PHINode *PN);
2035
2036 /// Provide special handling for a select-like instruction (currently this
2037 /// is either a select instruction or a phi node). \p Ty is the type of the
2038 /// instruction being processed, that is assumed equivalent to
2039 /// "Cond ? TrueVal : FalseVal".
2040 std::optional<const SCEV *>
2041 createNodeForSelectOrPHIInstWithICmpInstCond(Type *Ty, ICmpInst *Cond,
2042 Value *TrueVal, Value *FalseVal);
2043
2044 /// See if we can model this select-like instruction via umin_seq expression.
2045 const SCEV *createNodeForSelectOrPHIViaUMinSeq(Value *I, Value *Cond,
2046 Value *TrueVal,
2047 Value *FalseVal);
2048
2049 /// Given a value \p V, which is a select-like instruction (currently this is
2050 /// either a select instruction or a phi node), which is assumed equivalent to
2051 /// Cond ? TrueVal : FalseVal
2052 /// see if we can model it as a SCEV expression.
2053 const SCEV *createNodeForSelectOrPHI(Value *V, Value *Cond, Value *TrueVal,
2054 Value *FalseVal);
2055
2056 /// Provide the special handling we need to analyze GEP SCEVs.
2057 const SCEV *createNodeForGEP(GEPOperator *GEP);
2058
2059 /// Implementation code for getSCEVAtScope; called at most once for each
2060 /// SCEV+Loop pair.
2061 const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L);
2062
2063 /// Return the BackedgeTakenInfo for the given loop, lazily computing new
2064 /// values if the loop hasn't been analyzed yet. The returned result is
2065 /// guaranteed not to be predicated.
2066 BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L);
2067
2068 /// Similar to getBackedgeTakenInfo, but will add predicates as required
2069 /// with the purpose of returning complete information.
2070 BackedgeTakenInfo &getPredicatedBackedgeTakenInfo(const Loop *L);
2071
2072 /// Compute the number of times the specified loop will iterate.
2073 /// If AllowPredicates is set, we will create new SCEV predicates as
2074 /// necessary in order to return an exact answer.
2075 BackedgeTakenInfo computeBackedgeTakenCount(const Loop *L,
2076 bool AllowPredicates = false);
2077
2078 /// Compute the number of times the backedge of the specified loop will
2079 /// execute if it exits via the specified block. If AllowPredicates is set,
2080 /// this call will try to use a minimal set of SCEV predicates in order to
2081 /// return an exact answer.
2082 ExitLimit computeExitLimit(const Loop *L, BasicBlock *ExitingBlock,
2083 bool IsOnlyExit, bool AllowPredicates = false);
2084
2085 // Helper functions for computeExitLimitFromCond to avoid exponential time
2086 // complexity.
2087
2088 class ExitLimitCache {
2089 // It may look like we need key on the whole (L, ExitIfTrue,
2090 // ControlsOnlyExit, AllowPredicates) tuple, but recursive calls to
2091 // computeExitLimitFromCondCached from computeExitLimitFromCondImpl only
2092 // vary the in \c ExitCond and \c ControlsOnlyExit parameters. We remember
2093 // the initial values of the other values to assert our assumption.
2094 SmallDenseMap<PointerIntPair<Value *, 1>, ExitLimit> TripCountMap;
2095
2096 const Loop *L;
2097 bool ExitIfTrue;
2098 bool AllowPredicates;
2099
2100 public:
2101 ExitLimitCache(const Loop *L, bool ExitIfTrue, bool AllowPredicates)
2102 : L(L), ExitIfTrue(ExitIfTrue), AllowPredicates(AllowPredicates) {}
2103
2104 LLVM_ABI std::optional<ExitLimit> find(const Loop *L, Value *ExitCond,
2105 bool ExitIfTrue,
2106 bool ControlsOnlyExit,
2107 bool AllowPredicates);
2108
2109 LLVM_ABI void insert(const Loop *L, Value *ExitCond, bool ExitIfTrue,
2110 bool ControlsOnlyExit, bool AllowPredicates,
2111 const ExitLimit &EL);
2112 };
2113
2114 using ExitLimitCacheTy = ExitLimitCache;
2115
2116 ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache,
2117 const Loop *L, Value *ExitCond,
2118 bool ExitIfTrue,
2119 bool ControlsOnlyExit,
2120 bool AllowPredicates);
2121 ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache, const Loop *L,
2122 Value *ExitCond, bool ExitIfTrue,
2123 bool ControlsOnlyExit,
2124 bool AllowPredicates);
2125 std::optional<ScalarEvolution::ExitLimit>
2126 computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache, const Loop *L,
2127 Value *ExitCond, bool ExitIfTrue,
2128 bool AllowPredicates);
2129
2130 /// Compute the number of times the backedge of the specified loop will
2131 /// execute if its exit condition were a conditional branch of the ICmpInst
2132 /// ExitCond and ExitIfTrue. If AllowPredicates is set, this call will try
2133 /// to use a minimal set of SCEV predicates in order to return an exact
2134 /// answer.
2135 ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond,
2136 bool ExitIfTrue,
2137 bool IsSubExpr,
2138 bool AllowPredicates = false);
2139
2140 /// Variant of previous which takes the components representing an ICmp
2141 /// as opposed to the ICmpInst itself. Note that the prior version can
2142 /// return more precise results in some cases and is preferred when caller
2143 /// has a materialized ICmp.
2144 ExitLimit computeExitLimitFromICmp(const Loop *L, CmpPredicate Pred,
2145 SCEVUse LHS, SCEVUse RHS, bool IsSubExpr,
2146 bool AllowPredicates = false);
2147
2148 /// Compute the number of times the backedge of the specified loop will
2149 /// execute if its exit condition were a switch with a single exiting case
2150 /// to ExitingBB.
2151 ExitLimit computeExitLimitFromSingleExitSwitch(const Loop *L,
2152 SwitchInst *Switch,
2153 BasicBlock *ExitingBB,
2154 bool IsSubExpr);
2155
2156 /// Compute the exit limit of a loop that is controlled by a
2157 /// "(IV >> 1) != 0" type comparison. We cannot compute the exact trip
2158 /// count in these cases (since SCEV has no way of expressing them), but we
2159 /// can still sometimes compute an upper bound.
2160 ///
2161 /// Return an ExitLimit for a loop whose backedge is guarded by `LHS Pred
2162 /// RHS`.
2163 ExitLimit computeShiftCompareExitLimit(Value *LHS, Value *RHS, const Loop *L,
2164 ICmpInst::Predicate Pred);
2165
2166 /// If the loop is known to execute a constant number of times (the
2167 /// condition evolves only from constants), try to evaluate a few iterations
2168 /// of the loop until we get the exit condition gets a value of ExitWhen
2169 /// (true or false). If we cannot evaluate the exit count of the loop,
2170 /// return CouldNotCompute.
2171 const SCEV *computeExitCountExhaustively(const Loop *L, Value *Cond,
2172 bool ExitWhen);
2173
2174 /// Return the number of times an exit condition comparing the specified
2175 /// value to zero will execute. If not computable, return CouldNotCompute.
2176 /// If AllowPredicates is set, this call will try to use a minimal set of
2177 /// SCEV predicates in order to return an exact answer.
2178 ExitLimit howFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr,
2179 bool AllowPredicates = false);
2180
2181 /// Return the number of times an exit condition checking the specified
2182 /// value for nonzero will execute. If not computable, return
2183 /// CouldNotCompute.
2184 ExitLimit howFarToNonZero(const SCEV *V, const Loop *L);
2185
2186 /// Return the number of times an exit condition containing the specified
2187 /// less-than comparison will execute. If not computable, return
2188 /// CouldNotCompute.
2189 ///
2190 /// \p isSigned specifies whether the less-than is signed.
2191 ///
2192 /// \p ControlsOnlyExit is true when the LHS < RHS condition directly controls
2193 /// the branch (loops exits only if condition is true). In this case, we can
2194 /// use NoWrapFlags to skip overflow checks.
2195 ///
2196 /// If \p AllowPredicates is set, this call will try to use a minimal set of
2197 /// SCEV predicates in order to return an exact answer.
2198 ExitLimit howManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
2199 bool isSigned, bool ControlsOnlyExit,
2200 bool AllowPredicates = false);
2201
2202 ExitLimit howManyGreaterThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
2203 bool isSigned, bool IsSubExpr,
2204 bool AllowPredicates = false);
2205
2206 /// Return a predecessor of BB (which may not be an immediate predecessor)
2207 /// which has exactly one successor from which BB is reachable, or null if
2208 /// no such block is found.
2209 std::pair<const BasicBlock *, const BasicBlock *>
2210 getPredecessorWithUniqueSuccessorForBB(const BasicBlock *BB) const;
2211
2212 /// Test whether the condition described by Pred, LHS, and RHS is true
2213 /// whenever the given FoundCondValue value evaluates to true in given
2214 /// Context. If Context is nullptr, then the found predicate is true
2215 /// everywhere. LHS and FoundLHS may have different type width.
2216 LLVM_ABI bool isImpliedCond(CmpPredicate Pred, const SCEV *LHS,
2217 const SCEV *RHS, const Value *FoundCondValue,
2218 bool Inverse,
2219 const Instruction *Context = nullptr);
2220
2221 /// Test whether the condition described by Pred, LHS, and RHS is true
2222 /// whenever the given FoundCondValue value evaluates to true in given
2223 /// Context. If Context is nullptr, then the found predicate is true
2224 /// everywhere. LHS and FoundLHS must have same type width.
2225 LLVM_ABI bool isImpliedCondBalancedTypes(CmpPredicate Pred, SCEVUse LHS,
2226 SCEVUse RHS, CmpPredicate FoundPred,
2227 SCEVUse FoundLHS, SCEVUse FoundRHS,
2228 const Instruction *CtxI);
2229
2230 /// Test whether the condition described by Pred, LHS, and RHS is true
2231 /// whenever the condition described by FoundPred, FoundLHS, FoundRHS is
2232 /// true in given Context. If Context is nullptr, then the found predicate is
2233 /// true everywhere.
2234 LLVM_ABI bool isImpliedCond(CmpPredicate Pred, const SCEV *LHS,
2235 const SCEV *RHS, CmpPredicate FoundPred,
2236 const SCEV *FoundLHS, const SCEV *FoundRHS,
2237 const Instruction *Context = nullptr);
2238
2239 /// Test whether the condition described by Pred, LHS, and RHS is true
2240 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
2241 /// true in given Context. If Context is nullptr, then the found predicate is
2242 /// true everywhere.
2243 bool isImpliedCondOperands(CmpPredicate Pred, const SCEV *LHS,
2244 const SCEV *RHS, const SCEV *FoundLHS,
2245 const SCEV *FoundRHS,
2246 const Instruction *Context = nullptr);
2247
2248 /// Test whether the condition described by Pred, LHS, and RHS is true
2249 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
2250 /// true. Here LHS is an operation that includes FoundLHS as one of its
2251 /// arguments.
2252 bool isImpliedViaOperations(CmpPredicate Pred, const SCEV *LHS,
2253 const SCEV *RHS, const SCEV *FoundLHS,
2254 const SCEV *FoundRHS, unsigned Depth = 0);
2255
2256 /// Test whether the condition described by Pred, LHS, and RHS is true.
2257 /// Use only simple non-recursive types of checks, such as range analysis etc.
2258 bool isKnownViaNonRecursiveReasoning(CmpPredicate Pred, SCEVUse LHS,
2259 SCEVUse RHS);
2260
2261 /// Test whether the condition described by Pred, LHS, and RHS is true
2262 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
2263 /// true.
2264 bool isImpliedCondOperandsHelper(CmpPredicate Pred, const SCEV *LHS,
2265 const SCEV *RHS, const SCEV *FoundLHS,
2266 const SCEV *FoundRHS);
2267
2268 /// Test whether the condition described by Pred, LHS, and RHS is true
2269 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
2270 /// true. Utility function used by isImpliedCondOperands. Tries to get
2271 /// cases like "X `sgt` 0 => X - 1 `sgt` -1".
2272 bool isImpliedCondOperandsViaRanges(CmpPredicate Pred, const SCEV *LHS,
2273 const SCEV *RHS, CmpPredicate FoundPred,
2274 const SCEV *FoundLHS,
2275 const SCEV *FoundRHS);
2276
2277 /// Return true if the condition denoted by \p LHS \p Pred \p RHS is implied
2278 /// by a call to @llvm.experimental.guard in \p BB.
2279 bool isImpliedViaGuard(const BasicBlock *BB, CmpPredicate Pred,
2280 const SCEV *LHS, const SCEV *RHS);
2281
2282 /// Test whether the condition described by Pred, LHS, and RHS is true
2283 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
2284 /// true.
2285 ///
2286 /// This routine tries to rule out certain kinds of integer overflow, and
2287 /// then tries to reason about arithmetic properties of the predicates.
2288 bool isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred, const SCEV *LHS,
2289 const SCEV *RHS, const SCEV *FoundLHS,
2290 const SCEV *FoundRHS);
2291
2292 /// Test whether the condition described by Pred, LHS, and RHS is true
2293 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
2294 /// true.
2295 ///
2296 /// This routine tries to weaken the known condition basing on fact that
2297 /// FoundLHS is an AddRec.
2298 bool isImpliedCondOperandsViaAddRecStart(CmpPredicate Pred, const SCEV *LHS,
2299 const SCEV *RHS,
2300 const SCEV *FoundLHS,
2301 const SCEV *FoundRHS,
2302 const Instruction *CtxI);
2303
2304 /// Test whether the condition described by Pred, LHS, and RHS is true
2305 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
2306 /// true.
2307 ///
2308 /// This routine tries to figure out predicate for Phis which are SCEVUnknown
2309 /// if it is true for every possible incoming value from their respective
2310 /// basic blocks.
2311 bool isImpliedViaMerge(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS,
2312 const SCEV *FoundLHS, const SCEV *FoundRHS,
2313 unsigned Depth);
2314
2315 /// Test whether the condition described by Pred, LHS, and RHS is true
2316 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
2317 /// true.
2318 ///
2319 /// This routine tries to reason about shifts.
2320 bool isImpliedCondOperandsViaShift(CmpPredicate Pred, const SCEV *LHS,
2321 const SCEV *RHS, const SCEV *FoundLHS,
2322 const SCEV *FoundRHS);
2323
2324 /// If we know that the specified Phi is in the header of its containing
2325 /// loop, we know the loop executes a constant number of times, and the PHI
2326 /// node is just a recurrence involving constants, fold it.
2327 Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt &BEs,
2328 const Loop *L);
2329
2330 /// Test if the given expression is known to satisfy the condition described
2331 /// by Pred and the known constant ranges of LHS and RHS.
2332 bool isKnownPredicateViaConstantRanges(CmpPredicate Pred, SCEVUse LHS,
2333 SCEVUse RHS);
2334
2335 /// Try to prove the condition described by "LHS Pred RHS" by ruling out
2336 /// integer overflow.
2337 ///
2338 /// For instance, this will return true for "A s< (A + C)<nsw>" if C is
2339 /// positive.
2340 bool isKnownPredicateViaNoOverflow(CmpPredicate Pred, SCEVUse LHS,
2341 SCEVUse RHS);
2342
2343 /// Try to split Pred LHS RHS into logical conjunctions (and's) and try to
2344 /// prove them individually.
2345 bool isKnownPredicateViaSplitting(CmpPredicate Pred, SCEVUse LHS,
2346 SCEVUse RHS);
2347
2348 /// Try to match the Expr as "(L + R)<Flags>".
2349 bool splitBinaryAdd(SCEVUse Expr, SCEVUse &L, SCEVUse &R,
2350 SCEV::NoWrapFlags &Flags);
2351
2352 /// Forget predicated/non-predicated backedge taken counts for the given loop.
2353 void forgetBackedgeTakenCounts(const Loop *L, bool Predicated);
2354
2355 /// Drop memoized information for all \p SCEVs.
2356 void forgetMemoizedResults(ArrayRef<SCEVUse> SCEVs);
2357
2358 /// Helper for forgetMemoizedResults.
2359 void forgetMemoizedResultsImpl(const SCEV *S);
2360
2361 /// Iterate over instructions in \p Worklist and their users. Erase entries
2362 /// from ValueExprMap and collect SCEV expressions in \p ToForget
2363 void visitAndClearUsers(SmallVectorImpl<Instruction *> &Worklist,
2364 SmallPtrSetImpl<Instruction *> &Visited,
2365 SmallVectorImpl<SCEVUse> &ToForget);
2366
2367 /// Erase Value from ValueExprMap and ExprValueMap.
2368 void eraseValueFromMap(Value *V);
2369
2370 /// Insert V to S mapping into ValueExprMap and ExprValueMap.
2371 void insertValueToMap(Value *V, const SCEV *S);
2372
2373 /// Return false iff given SCEV contains a SCEVUnknown with NULL value-
2374 /// pointer.
2375 bool checkValidity(const SCEV *S) const;
2376
2377 /// Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be
2378 /// equal to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}. This is
2379 /// equivalent to proving no signed (resp. unsigned) wrap in
2380 /// {`Start`,+,`Step`} if `ExtendOpTy` is `SCEVSignExtendExpr`
2381 /// (resp. `SCEVZeroExtendExpr`).
2382 template <typename ExtendOpTy>
2383 bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step,
2384 const Loop *L);
2385
2386 /// Try to prove NSW or NUW on \p AR relying on ConstantRange manipulation.
2387 SCEV::NoWrapFlags proveNoWrapViaConstantRanges(const SCEVAddRecExpr *AR);
2388
2389 /// Try to prove NSW on \p AR by proving facts about conditions known on
2390 /// entry and backedge.
2391 SCEV::NoWrapFlags proveNoSignedWrapViaInduction(const SCEVAddRecExpr *AR);
2392
2393 /// Try to prove NUW on \p AR by proving facts about conditions known on
2394 /// entry and backedge.
2395 SCEV::NoWrapFlags proveNoUnsignedWrapViaInduction(const SCEVAddRecExpr *AR);
2396
2397 std::optional<MonotonicPredicateType>
2398 getMonotonicPredicateTypeImpl(const SCEVAddRecExpr *LHS,
2399 ICmpInst::Predicate Pred);
2400
2401 /// Return SCEV no-wrap flags that can be proven based on reasoning about
2402 /// how poison produced from no-wrap flags on this value (e.g. a nuw add)
2403 /// would trigger undefined behavior on overflow.
2404 SCEV::NoWrapFlags getNoWrapFlagsFromUB(const Value *V);
2405
2406 /// Return a scope which provides an upper bound on the defining scope of
2407 /// 'S'. Specifically, return the first instruction in said bounding scope.
2408 /// Return nullptr if the scope is trivial (function entry).
2409 /// (See scope definition rules associated with flag discussion above)
2410 const Instruction *getNonTrivialDefiningScopeBound(const SCEV *S);
2411
2412 /// Return a scope which provides an upper bound on the defining scope for
2413 /// a SCEV with the operands in Ops. The outparam Precise is set if the
2414 /// bound found is a precise bound (i.e. must be the defining scope.)
2415 const Instruction *getDefiningScopeBound(ArrayRef<SCEVUse> Ops,
2416 bool &Precise);
2417
2418 /// Wrapper around the above for cases which don't care if the bound
2419 /// is precise.
2420 const Instruction *getDefiningScopeBound(ArrayRef<SCEVUse> Ops);
2421
2422 /// Given two instructions in the same function, return true if we can
2423 /// prove B must execute given A executes.
2424 bool isGuaranteedToTransferExecutionTo(const Instruction *A,
2425 const Instruction *B);
2426
2427 /// Returns true if \p Op is guaranteed not to cause immediate UB.
2428 bool isGuaranteedNotToCauseUB(const SCEV *Op);
2429
2430 /// Returns true if \p Op is guaranteed to not be poison.
2431 static bool isGuaranteedNotToBePoison(const SCEV *Op);
2432
2433 /// Return true if the SCEV corresponding to \p I is never poison. Proving
2434 /// this is more complex than proving that just \p I is never poison, since
2435 /// SCEV commons expressions across control flow, and you can have cases
2436 /// like:
2437 ///
2438 /// idx0 = a + b;
2439 /// ptr[idx0] = 100;
2440 /// if (<condition>) {
2441 /// idx1 = a +nsw b;
2442 /// ptr[idx1] = 200;
2443 /// }
2444 ///
2445 /// where the SCEV expression (+ a b) is guaranteed to not be poison (and
2446 /// hence not sign-overflow) only if "<condition>" is true. Since both
2447 /// `idx0` and `idx1` will be mapped to the same SCEV expression, (+ a b),
2448 /// it is not okay to annotate (+ a b) with <nsw> in the above example.
2449 bool isSCEVExprNeverPoison(const Instruction *I);
2450
2451 /// This is like \c isSCEVExprNeverPoison but it specifically works for
2452 /// instructions that will get mapped to SCEV add recurrences. Return true
2453 /// if \p I will never generate poison under the assumption that \p I is an
2454 /// add recurrence on the loop \p L.
2455 bool isAddRecNeverPoison(const Instruction *I, const Loop *L);
2456
2457 /// Similar to createAddRecFromPHI, but with the additional flexibility of
2458 /// suggesting runtime overflow checks in case casts are encountered.
2459 /// If successful, the analysis records that for this loop, \p SymbolicPHI,
2460 /// which is the UnknownSCEV currently representing the PHI, can be rewritten
2461 /// into an AddRec, assuming some predicates; The function then returns the
2462 /// AddRec and the predicates as a pair, and caches this pair in
2463 /// PredicatedSCEVRewrites.
2464 /// If the analysis is not successful, a mapping from the \p SymbolicPHI to
2465 /// itself (with no predicates) is recorded, and a nullptr with an empty
2466 /// predicates vector is returned as a pair.
2467 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2468 createAddRecFromPHIWithCastsImpl(const SCEVUnknown *SymbolicPHI);
2469
2470 /// Compute the maximum backedge count based on the range of values
2471 /// permitted by Start, End, and Stride. This is for loops of the form
2472 /// {Start, +, Stride} LT End.
2473 ///
2474 /// Preconditions:
2475 /// * the induction variable is known to be positive.
2476 /// * the induction variable is assumed not to overflow (i.e. either it
2477 /// actually doesn't, or we'd have to immediately execute UB)
2478 /// We *don't* assert these preconditions so please be careful.
2479 const SCEV *computeMaxBECountForLT(const SCEV *Start, const SCEV *Stride,
2480 const SCEV *End, unsigned BitWidth,
2481 bool IsSigned);
2482
2483 /// Verify if an linear IV with positive stride can overflow when in a
2484 /// less-than comparison, knowing the invariant term of the comparison,
2485 /// the stride.
2486 bool canIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, bool IsSigned);
2487
2488 /// Verify if an linear IV with negative stride can overflow when in a
2489 /// greater-than comparison, knowing the invariant term of the comparison,
2490 /// the stride.
2491 bool canIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, bool IsSigned);
2492
2493 /// Get add expr already created or create a new one.
2494 const SCEV *getOrCreateAddExpr(ArrayRef<SCEVUse> Ops,
2495 SCEV::NoWrapFlags Flags);
2496
2497 /// Get mul expr already created or create a new one.
2498 const SCEV *getOrCreateMulExpr(ArrayRef<SCEVUse> Ops,
2499 SCEV::NoWrapFlags Flags);
2500
2501 // Get addrec expr already created or create a new one.
2502 const SCEV *getOrCreateAddRecExpr(ArrayRef<SCEVUse> Ops, const Loop *L,
2503 SCEV::NoWrapFlags Flags);
2504
2505 /// Return x if \p Val is f(x) where f is a 1-1 function.
2506 const SCEV *stripInjectiveFunctions(const SCEV *Val) const;
2507
2508 /// Find all of the loops transitively used in \p S, and fill \p LoopsUsed.
2509 /// A loop is considered "used" by an expression if it contains
2510 /// an add rec on said loop.
2511 void getUsedLoops(const SCEV *S, SmallPtrSetImpl<const Loop *> &LoopsUsed);
2512
2513 /// Look for a SCEV expression with type `SCEVType` and operands `Ops` in
2514 /// `UniqueSCEVs`. Return if found, else nullptr.
2515 SCEV *findExistingSCEVInCache(SCEVTypes SCEVType, ArrayRef<const SCEV *> Ops);
2516 SCEV *findExistingSCEVInCache(SCEVTypes SCEVType, ArrayRef<SCEVUse> Ops);
2517
2518 /// Get reachable blocks in this function, making limited use of SCEV
2519 /// reasoning about conditions.
2520 void getReachableBlocks(SmallPtrSetImpl<BasicBlock *> &Reachable,
2521 Function &F);
2522
2523 /// Return the given SCEV expression with a new set of operands.
2524 /// This preserves the origial nowrap flags.
2525 const SCEV *getWithOperands(const SCEV *S, SmallVectorImpl<SCEVUse> &NewOps);
2526
2527 FoldingSet<SCEV> UniqueSCEVs;
2528 FoldingSet<SCEVPredicate> UniquePreds;
2529 BumpPtrAllocator SCEVAllocator;
2530
2531 /// This maps loops to a list of addrecs that directly use said loop.
2532 DenseMap<const Loop *, SmallVector<const SCEVAddRecExpr *, 4>> LoopUsers;
2533
2534 /// Cache tentative mappings from UnknownSCEVs in a Loop, to a SCEV expression
2535 /// they can be rewritten into under certain predicates.
2536 DenseMap<std::pair<const SCEVUnknown *, const Loop *>,
2537 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2538 PredicatedSCEVRewrites;
2539
2540 /// Set of AddRecs for which proving NUW via an induction has already been
2541 /// tried.
2542 SmallPtrSet<const SCEVAddRecExpr *, 16> UnsignedWrapViaInductionTried;
2543
2544 /// Set of AddRecs for which proving NSW via an induction has already been
2545 /// tried.
2546 SmallPtrSet<const SCEVAddRecExpr *, 16> SignedWrapViaInductionTried;
2547
2548 /// The head of a linked list of all SCEVUnknown values that have been
2549 /// allocated. This is used by releaseMemory to locate them all and call
2550 /// their destructors.
2551 SCEVUnknown *FirstUnknown = nullptr;
2552};
2553
2554/// Analysis pass that exposes the \c ScalarEvolution for a function.
2556 : public AnalysisInfoMixin<ScalarEvolutionAnalysis> {
2558
2559 LLVM_ABI static AnalysisKey Key;
2560
2561public:
2563
2565};
2566
2567/// Verifier pass for the \c ScalarEvolutionAnalysis results.
2569 : public RequiredPassInfoMixin<ScalarEvolutionVerifierPass> {
2570public:
2572};
2573
2574/// Printer pass for the \c ScalarEvolutionAnalysis results.
2576 : public RequiredPassInfoMixin<ScalarEvolutionPrinterPass> {
2577 raw_ostream &OS;
2578
2579public:
2580 explicit ScalarEvolutionPrinterPass(raw_ostream &OS) : OS(OS) {}
2581
2583};
2584
2586 std::unique_ptr<ScalarEvolution> SE;
2587
2588public:
2589 static char ID;
2590
2592
2593 ScalarEvolution &getSE() { return *SE; }
2594 const ScalarEvolution &getSE() const { return *SE; }
2595
2596 bool runOnFunction(Function &F) override;
2597 void releaseMemory() override;
2598 void getAnalysisUsage(AnalysisUsage &AU) const override;
2599 void print(raw_ostream &OS, const Module * = nullptr) const override;
2600 void verifyAnalysis() const override;
2601};
2602
2603/// An interface layer with SCEV used to manage how we see SCEV expressions
2604/// for values in the context of existing predicates. We can add new
2605/// predicates, but we cannot remove them.
2606///
2607/// This layer has multiple purposes:
2608/// - provides a simple interface for SCEV versioning.
2609/// - guarantees that the order of transformations applied on a SCEV
2610/// expression for a single Value is consistent across two different
2611/// getSCEV calls. This means that, for example, once we've obtained
2612/// an AddRec expression for a certain value through expression
2613/// rewriting, we will continue to get an AddRec expression for that
2614/// Value.
2615/// - lowers the number of expression rewrites.
2617public:
2619
2620 LLVM_ABI const SCEVPredicate &getPredicate() const;
2621
2622 /// Returns the SCEV expression of V, in the context of the current SCEV
2623 /// predicate. The order of transformations applied on the expression of V
2624 /// returned by ScalarEvolution is guaranteed to be preserved, even when
2625 /// adding new predicates.
2626 LLVM_ABI const SCEV *getSCEV(Value *V);
2627
2628 /// Returns the rewritten SCEV for \p Expr in the context of the current SCEV
2629 /// predicate. The order of transformations applied on the expression of \p
2630 /// Expr returned by ScalarEvolution is guaranteed to be preserved, even when
2631 /// adding new predicates.
2632 LLVM_ABI const SCEV *getPredicatedSCEV(const SCEV *Expr);
2633
2634 /// Get the (predicated) backedge count for the analyzed loop.
2636
2637 /// Get the (predicated) symbolic max backedge count for the analyzed loop.
2639
2640 /// Returns the upper bound of the loop trip count as a normal unsigned
2641 /// value, or 0 if the trip count is unknown.
2643
2644 /// Adds a new predicate.
2645 LLVM_ABI void addPredicate(const SCEVPredicate &Pred);
2646
2647 /// Attempts to produce an AddRecExpr for V by adding additional SCEV
2648 /// predicates. If we can't transform the expression into an AddRecExpr we
2649 /// return nullptr and not add additional SCEV predicates to the current
2650 /// context. If \p WrapPredsAdded is non-null, the required predicates are
2651 /// collected there instead of being added to this context.
2652 LLVM_ABI const SCEVAddRecExpr *
2653 getAsAddRec(Value *V,
2654 SmallVectorImpl<const SCEVPredicate *> *WrapPredsAdded = nullptr);
2655
2656 /// Proves that V doesn't overflow by adding SCEV predicate.
2659
2660 /// Returns true if we've proved that V doesn't wrap by means of a SCEV
2661 /// predicate.
2664
2665 /// Returns the ScalarEvolution analysis used.
2666 ScalarEvolution *getSE() const { return &SE; }
2667
2668 /// We need to explicitly define the copy constructor because of FlagsMap.
2670
2671 /// Print the SCEV mappings done by the Predicated Scalar Evolution.
2672 /// The printed text is indented by \p Depth.
2673 LLVM_ABI void print(raw_ostream &OS, unsigned Depth) const;
2674
2675 /// Check if \p AR1 and \p AR2 are equal, while taking into account
2676 /// Equal predicates in Preds and \p ExtraPreds.
2678 const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2,
2679 ArrayRef<const SCEVPredicate *> ExtraPreds = {}) const;
2680
2681private:
2682 /// Increments the version number of the predicate. This needs to be called
2683 /// every time the SCEV predicate changes.
2684 void updateGeneration();
2685
2686 /// Holds a SCEV and the version number of the SCEV predicate used to
2687 /// perform the rewrite of the expression.
2688 using RewriteEntry = std::pair<unsigned, const SCEV *>;
2689
2690 /// Maps a SCEV to the rewrite result of that SCEV at a certain version
2691 /// number. If this number doesn't match the current Generation, we will
2692 /// need to do a rewrite. To preserve the transformation order of previous
2693 /// rewrites, we will rewrite the previous result instead of the original
2694 /// SCEV.
2695 DenseMap<const SCEV *, RewriteEntry> RewriteMap;
2696
2697 /// Records what NoWrap flags we've added to a Value *.
2698 ValueMap<Value *, SCEVWrapPredicate::IncrementWrapFlags> FlagsMap;
2699
2700 /// The ScalarEvolution analysis.
2701 ScalarEvolution &SE;
2702
2703 /// The analyzed Loop.
2704 const Loop &L;
2705
2706 /// The SCEVPredicate that forms our context. We will rewrite all
2707 /// expressions assuming that this predicate true.
2708 std::unique_ptr<SCEVUnionPredicate> Preds;
2709
2710 /// Marks the version of the SCEV predicate used. When rewriting a SCEV
2711 /// expression we mark it with the version of the predicate. We use this to
2712 /// figure out if the predicate has changed from the last rewrite of the
2713 /// SCEV. If so, we need to perform a new rewrite.
2714 unsigned Generation = 0;
2715
2716 /// The backedge taken count.
2717 const SCEV *BackedgeCount = nullptr;
2718
2719 /// The symbolic backedge taken count.
2720 const SCEV *SymbolicMaxBackedgeCount = nullptr;
2721
2722 /// The constant max trip count for the loop.
2723 std::optional<unsigned> SmallConstantMaxTripCount;
2724};
2725
2726template <> struct DenseMapInfo<ScalarEvolution::FoldID> {
2727 static unsigned getHashValue(const ScalarEvolution::FoldID &Val) {
2728 return Val.computeHash();
2729 }
2730
2733 return LHS == RHS;
2734 }
2735};
2736
2737template <> inline const SCEV *SCEVUseT<const SCEV *>::getCanonical() const {
2738 return getPointer()->getCanonical();
2739}
2740
2741template <typename SCEVPtrT>
2743 getPointer()->print(OS);
2745 if (any(Flags & SCEV::FlagNUW))
2746 OS << "(u nuw)";
2747 if (any(Flags & SCEV::FlagNSW))
2748 OS << "(u nsw)";
2749}
2750
2751#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2752template <typename SCEVPtrT>
2754 print(dbgs());
2755 dbgs() << '\n';
2756}
2757#endif
2758
2759} // end namespace llvm
2760
2761#endif // LLVM_ANALYSIS_SCALAREVOLUTION_H
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
aarch64 promote const
constexpr LLT S1
This file implements a class to represent arbitrary precision integral constant values and operations...
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
#define X(NUM, ENUM, NAME)
Definition ELF.h:853
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_ABI
Definition Compiler.h:213
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition Compiler.h:661
SmallPtrSet< const BasicBlock *, 8 > VisitedBlocks
This file defines DenseMapInfo traits for DenseMap.
This file defines the DenseMap class.
static bool runOnFunction(Function &F, bool PostInlining)
static bool isSigned(unsigned Opcode)
This file defines a hash set that can be used to remove duplication of nodes in a graph.
Hexagon Common GEP
Value * getPointer(Value *Ptr)
This header defines various interfaces for pass management in LLVM.
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
#define F(x, y, z)
Definition MD5.cpp:54
#define I(x, y, z)
Definition MD5.cpp:57
#define P(N)
This file defines the PointerIntPair class.
const SmallVectorImpl< MachineOperand > & Cond
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition APInt.h:78
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition APInt.h:240
Represent the analysis usage information of a pass.
Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:40
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition BasicBlock.h:62
Value handle with callbacks on RAUW and destruction.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition InstrTypes.h:740
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
This is the shared class of boolean and integer constants.
Definition Constants.h:87
This class represents a range of values.
This is an important base class in LLVM.
Definition Constant.h:43
A parsed version of the target data layout string in and methods for querying it.
Definition DataLayout.h:64
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition Dominators.h:151
This class describes a reference to an interned FoldingSetNodeID, which can be a useful to store node...
Definition FoldingSet.h:171
This class is used to gather all the unique data bits of a node.
Definition FoldingSet.h:208
FunctionPass(char &pid)
Definition Pass.h:316
Represents flags for the getelementptr instruction/expression.
static GEPNoWrapFlags none()
This is an important class for using LLVM in a threaded context.
Definition LLVMContext.h:68
Represents a single loop in the control flow graph.
Definition LoopInfo.h:40
A Module instance is used to store all the information related to an LLVM module.
Definition Module.h:67
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
Definition Operator.h:78
bool operator>(const PointerIntPair &RHS) const
Value handle that poisons itself if the Value is deleted.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
LLVM_ABI void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
LLVM_ABI const SCEVPredicate & getPredicate() const
LLVM_ABI const SCEV * getPredicatedSCEV(const SCEV *Expr)
Returns the rewritten SCEV for Expr in the context of the current SCEV predicate.
LLVM_ABI bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2, ArrayRef< const SCEVPredicate * > ExtraPreds={}) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds and ExtraPreds.
LLVM_ABI bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've proved that V doesn't wrap by means of a SCEV predicate.
LLVM_ABI void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Proves that V doesn't overflow by adding SCEV predicate.
LLVM_ABI const SCEVAddRecExpr * getAsAddRec(Value *V, SmallVectorImpl< const SCEVPredicate * > *WrapPredsAdded=nullptr)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
LLVM_ABI void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
LLVM_ABI PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L)
LLVM_ABI unsigned getSmallConstantMaxTripCount()
Returns the upper bound of the loop trip count as a normal unsigned value, or 0 if the trip count is ...
LLVM_ABI const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSymbolicMaxBackedgeTakenCount()
Get the (predicated) symbolic max backedge count for the analyzed loop.
LLVM_ABI const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
This node represents a polynomial recurrence on the trip count of the specified loop.
SCEVComparePredicate(const FoldingSetNodeIDRef ID, const ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
const SCEV * getRHS() const
Returns the right hand side of the predicate.
ICmpInst::Predicate getPredicate() const
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
const SCEV * getLHS() const
Returns the left hand side of the predicate.
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Implementation of the SCEVPredicate interface.
This class represents an assumption made using SCEV expressions which can be checked at run-time.
SCEVPredicateKind getKind() const
virtual unsigned getComplexity() const
Returns the estimated complexity of this predicate.
SCEVPredicate & operator=(const SCEVPredicate &)=default
SCEVPredicate(const SCEVPredicate &)=default
virtual bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const =0
Returns true if this predicate implies N.
virtual void print(raw_ostream &OS, unsigned Depth=0) const =0
Prints a textual representation of this predicate with an indentation of Depth.
~SCEVPredicate()=default
virtual bool isAlwaysTrue() const =0
Returns true if the predicate is always true.
SCEVPredicateKind Kind
unsigned getComplexity() const override
We estimate the complexity of a union predicate as the size number of predicates in the union.
SCEVUnionPredicate(ArrayRef< const SCEVPredicate * > Preds, ScalarEvolution &SE)
Union predicates don't get cached so create a dummy set ID for it.
SCEVUnionPredicate getUnionWith(const SCEVPredicate *N, ScalarEvolution &SE) const
Returns a new SCEVUnionPredicate that is the union of this predicate and the given predicate N.
ArrayRef< const SCEVPredicate * > getPredicates() const
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents an assumption made on an AddRec expression.
IncrementWrapFlags
Similar to SCEV::NoWrapFlags, but with slightly different semantics for FlagNUSW.
SCEVWrapPredicate(const FoldingSetNodeIDRef ID, const SCEVAddRecExpr *AR, IncrementWrapFlags Flags)
static SCEVWrapPredicate::IncrementWrapFlags setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OnFlags)
static SCEVWrapPredicate::IncrementWrapFlags clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OffFlags)
Convenient IncrementWrapFlags manipulation methods.
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
IncrementWrapFlags getFlags() const
Returns the set assumed no overflow flags.
static SCEVWrapPredicate::IncrementWrapFlags maskFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, int Mask)
This class represents an analyzed expression in the program.
static constexpr auto NoWrapMask
unsigned short getExpressionSize() const
SCEV & operator=(const SCEV &)=delete
SCEVNoWrapFlags NoWrapFlags
LLVM_ABI bool isOne() const
Return true if the expression is a constant one.
static constexpr auto FlagNUW
LLVM_ABI void computeAndSetCanonical(ScalarEvolution &SE)
Compute and set the canonical SCEV, by constructing a SCEV with the same operands,...
LLVM_ABI bool isZero() const
Return true if the expression is a constant zero.
const SCEV * getCanonical() const
Return the canonical SCEV.
SCEV(const SCEV &)=delete
const SCEV * CanonicalSCEV
Pointer to the canonical version of the SCEV, i.e.
static constexpr auto FlagAnyWrap
LLVM_ABI void dump() const
This method is used for debugging.
LLVM_ABI bool isAllOnesValue() const
Return true if the expression is a constant all-ones value.
LLVM_ABI bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
static constexpr auto FlagNSW
LLVM_ABI ArrayRef< SCEVUse > operands() const
Return operands of this SCEV expression.
const unsigned short ExpressionSize
LLVM_ABI void print(raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
SCEV(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, unsigned short ExpressionSize)
SCEVTypes getSCEVType() const
unsigned short SubclassData
This field is initialized to zero and may be used in subclasses to store miscellaneous information.
static constexpr auto FlagNW
LLVM_ABI Type * getType() const
Return the LLVM type of this SCEV expression.
Analysis pass that exposes the ScalarEvolution for a function.
LLVM_ABI ScalarEvolution run(Function &F, FunctionAnalysisManager &AM)
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Verifier pass for the ScalarEvolutionAnalysis results.
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
const ScalarEvolution & getSE() const
bool operator==(const FoldID &RHS) const
FoldID(SCEVTypes C, const SCEV *Op, const Type *Ty)
static LLVM_ABI LoopGuards collect(const Loop *L, ScalarEvolution &SE)
Collect rewrite map for loop guards for loop L, together with flags indicating if NUW and NSW can be ...
LLVM_ABI const SCEV * rewrite(const SCEV *Expr) const
Try to apply the collected loop guards to Expr.
The main scalar evolution driver.
LLVM_ABI const SCEV * getUDivExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
static bool hasFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags TestFlags)
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
LLVM_ABI bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
LLVM_ABI bool isKnownOnEveryIteration(CmpPredicate Pred, const SCEVAddRecExpr *LHS, const SCEV *RHS)
Test if the condition described by Pred, LHS, RHS is known to be true on every iteration of the loop ...
LLVM_ABI const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterationsImpl(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
LLVM_ABI const SCEV * getUDivCeilSCEV(const SCEV *N, const SCEV *D)
Compute ceil(N / D).
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterations(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L at given Context duri...
LLVM_ABI Type * getWiderType(Type *Ty1, Type *Ty2) const
LLVM_ABI const SCEV * getAbsExpr(const SCEV *Op, bool IsNSW)
LLVM_ABI bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
LLVM_ABI bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
LLVM_ABI const SCEV * getPredicatedConstantMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getConstantMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI const SCEV * removePointerBase(const SCEV *S)
Compute an expression equivalent to S - getPointerBase(S).
LLVM_ABI bool isLoopEntryGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
LLVM_ABI bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
LLVM_ABI const SCEV * getURemExpr(SCEVUse LHS, SCEVUse RHS)
Represents an unsigned remainder expression based on unsigned division.
LLVM_ABI const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
LLVM_ABI const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
LLVM_ABI const SCEV * getSMinExpr(SCEVUse LHS, SCEVUse RHS)
LLVM_ABI void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags)
Update no-wrap flags of an AddRec.
LLVM_ABI const SCEV * getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS)
Promote the operands to the wider of the types using zero-extension, and then perform a umax operatio...
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
LLVM_ABI bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI=nullptr)
Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?
LLVM_ABI ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, bool ExitIfTrue, bool ControlsOnlyExit, bool AllowPredicates=false)
Compute the number of times the backedge of the specified loop will execute if its exit condition wer...
LLVM_ABI const SCEV * getZeroExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< SCEVUse > &Operands)
LLVM_ABI const SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
LLVM_ABI unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
LLVM_ABI uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
LLVM_ABI const SCEV * getConstant(ConstantInt *V)
LLVM_ABI const SCEV * getPredicatedBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getBackedgeTakenCount, except it will add a set of SCEV predicates to Predicates that are ...
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
LLVM_ABI const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
LLVM_ABI const SCEV * getAddRecExpr(SCEVUse Start, SCEVUse Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
LLVM_ABI const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
bool loopHasNoAbnormalExits(const Loop *L)
Return true if the loop has no abnormal exits.
LLVM_ABI const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)
A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...
LLVM_ABI ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI)
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
LLVM_ABI const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI const SCEV * getLosslessPtrToIntExpr(const SCEV *Op)
const SCEV * getMulExpr(SCEVUse Op0, SCEVUse Op1, SCEVUse Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
LLVM_ABI const SCEV * getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty)
LLVM_ABI const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< SCEVUse > &Operands)
LLVM_ABI std::optional< bool > evaluatePredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Check whether the condition described by Pred, LHS, and RHS is true or false in the given Context.
LLVM_ABI unsigned getSmallConstantMaxTripCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Returns the upper bound of the loop trip count as a normal unsigned value.
LLVM_ABI const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
LLVM_ABI bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
LLVM_ABI void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
LLVM_ABI bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
LLVM_ABI bool isKnownPositive(const SCEV *S)
Test if the given expression is known to be positive.
LLVM_ABI bool SimplifyICmpOperands(CmpPredicate &Pred, SCEVUse &LHS, SCEVUse &RHS, unsigned Depth=0)
Simplify LHS and RHS in a comparison with predicate Pred.
APInt getUnsignedRangeMin(const SCEV *S)
Determine the min of the unsigned range for a particular SCEV.
LLVM_ABI const SCEV * getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo)
Return an expression for offsetof on the given field with type IntTy.
LLVM_ABI LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
LLVM_ABI bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
LLVM_ABI const SCEV * getSignExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI bool hasOperand(const SCEV *S, const SCEV *Op) const
Test whether the given SCEV has Op as a direct or indirect operand.
LLVM_ABI const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
LLVM_ABI Type * getEffectiveSCEVType(Type *Ty) const
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the g...
LLVM_ABI const SCEVPredicate * getComparePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
LLVM_ABI bool haveSameSign(const SCEV *S1, const SCEV *S2)
Return true if we know that S1 and S2 must have the same sign.
LLVM_ABI const SCEV * getNotSCEV(const SCEV *V)
Return the SCEV object corresponding to ~V.
LLVM_ABI const SCEV * getElementCount(Type *Ty, ElementCount EC, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
LLVM_ABI bool instructionCouldExistWithOperands(const SCEV *A, const SCEV *B)
Return true if there exists a point in the program at which both A and B could be operands to the sam...
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
LLVM_ABI void print(raw_ostream &OS) const
LLVM_ABI const SCEV * getPredicatedExitCount(const Loop *L, const BasicBlock *ExitingBlock, SmallVectorImpl< const SCEVPredicate * > *Predicates, ExitCountKind Kind=Exact)
Same as above except this uses the predicated backedge taken info and may require predicates.
static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
LLVM_ABI void forgetTopmostLoop(const Loop *L)
friend class ScalarEvolutionsTest
LLVM_ABI void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
APInt getSignedRangeMin(const SCEV *S)
Determine the min of the signed range for a particular SCEV.
LLVM_ABI bool isLoopUniform(const SCEV *S, const Loop *L)
Returns true if the given SCEV is loop-uniform with respect to the specified loop L.
LLVM_ABI const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
LLVM_ABI const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI const SCEV * getUMaxExpr(SCEVUse LHS, SCEVUse RHS)
static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags Mask)
Convenient NoWrapFlags manipulation.
MonotonicPredicateType
A predicate is said to be monotonically increasing if may go from being false to being true as the lo...
LLVM_ABI std::optional< LoopInvariantPredicate > getLoopInvariantPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI=nullptr)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L, return a LoopInvaria...
LLVM_ABI const SCEV * getStoreSizeOfExpr(Type *IntTy, Type *StoreTy)
Return an expression for the store size of StoreTy that is type IntTy.
LLVM_ABI const SCEVPredicate * getWrapPredicate(const SCEVAddRecExpr *AR, SCEVWrapPredicate::IncrementWrapFlags AddedFlags)
LLVM_ABI bool isLoopBackedgeGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether the backedge of the loop is protected by a conditional between LHS and RHS.
LLVM_ABI APInt getNonZeroConstantMultiple(const SCEV *S)
const SCEV * getMinusOne(Type *Ty)
Return a SCEV for the constant -1 of a specific type.
static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
LLVM_ABI bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
LLVM_ABI BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB)
Return the "disposition" of the given SCEV with respect to the given block.
LLVM_ABI const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
LLVM_ABI const SCEV * getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
Promote the operands to the wider of the types using zero-extension, and then perform a umin operatio...
LLVM_ABI bool loopIsFiniteByAssumption(const Loop *L)
Return true if this loop is finite by assumption.
LLVM_ABI const SCEV * getExistingSCEV(Value *V)
Return an existing SCEV for V if there is one, otherwise return nullptr.
LLVM_ABI APInt getConstantMultiple(const SCEV *S, const Instruction *CtxI=nullptr)
Returns the max constant multiple of S.
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
@ LoopComputable
The SCEV varies predictably with the loop.
@ LoopVariant
The SCEV is loop-variant (unknown).
@ LoopInvariant
The SCEV is loop-invariant.
@ LoopUniform
The SCEV is loop-uniform.
LLVM_ABI bool isKnownMultipleOf(const SCEV *S, uint64_t M, SmallVectorImpl< const SCEVPredicate * > &Assumptions)
Check that S is a multiple of M.
LLVM_ABI const SCEV * getAnyExtendExpr(const SCEV *Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
const SCEV * getAddRecExpr(const SmallVectorImpl< SCEVUse > &Operands, const Loop *L, SCEV::NoWrapFlags Flags)
LLVM_ABI bool isKnownToBeAPowerOfTwo(const SCEV *S, bool OrZero=false, bool OrNegative=false)
Test if the given expression is known to be a power of 2.
LLVM_ABI std::optional< SCEV::NoWrapFlags > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
LLVM_ABI void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)
Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...
LLVM_ABI bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
LLVM_ABI std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
LLVM_ABI const SCEV * getCouldNotCompute()
LLVM_ABI const SCEV * getMulExpr(SmallVectorImpl< SCEVUse > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
LLVM_ABI bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
LLVM_ABI uint32_t getMinTrailingZeros(const SCEV *S, const Instruction *CtxI=nullptr)
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
BlockDisposition
An enum describing the relationship between a SCEV and a basic block.
@ DominatesBlock
The SCEV dominates the block.
@ ProperlyDominatesBlock
The SCEV properly dominates the block.
@ DoesNotDominateBlock
The SCEV does not dominate the block.
LLVM_ABI const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
LLVM_ABI const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
LLVM_ABI void getPoisonGeneratingValues(SmallPtrSetImpl< const Value * > &Result, const SCEV *S)
Return the set of Values that, if poison, will definitively result in S being poison as well.
LLVM_ABI void forgetLoopDispositions()
Called when the client has changed the disposition of values in this loop.
LLVM_ABI const SCEV * getVScale(Type *Ty)
LLVM_ABI unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
LLVM_ABI bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
LLVM_ABI const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
const SCEV * getPowerOfTwo(Type *Ty, unsigned Power)
Return a SCEV for the constant Power of two.
LLVM_ABI void forgetAllLoops()
LLVM_ABI bool dominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV dominate the specified basic block.
const SCEV * getAddExpr(SCEVUse Op0, SCEVUse Op1, SCEVUse Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
APInt getUnsignedRangeMax(const SCEV *S)
Determine the max of the unsigned range for a particular SCEV.
LLVM_ABI const SCEV * getAddExpr(SmallVectorImpl< SCEVUse > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
ExitCountKind
The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of ...
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
@ ConstantMaximum
A constant which provides an upper bound on the exact trip count.
@ Exact
An expression exactly describing the number of times the backedge has executed when a loop is exited.
LLVM_ABI bool isKnownPredicate(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
LLVM_ABI const SCEV * getPtrToAddrExpr(const SCEV *Op)
LLVM_ABI const SCEVAddRecExpr * convertSCEVToAddRecWithPredicates(const SCEV *S, const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Preds)
Tries to convert the S expression to an AddRec expression, adding additional predicates to Preds as r...
LLVM_ABI const SCEV * getSMaxExpr(SCEVUse LHS, SCEVUse RHS)
LLVM_ABI const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
LLVM_ABI const SCEV * getSizeOfExpr(Type *IntTy, TypeSize Size)
Return an expression for a TypeSize.
LLVM_ABI std::optional< bool > evaluatePredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Check whether the condition described by Pred, LHS, and RHS is true or false.
LLVM_ABI const SCEV * getUnknown(Value *V)
const SCEV * getAddExpr(SCEVUse LHS, SCEVUse RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
LLVM_ABI std::optional< std::pair< const SCEV *, SmallVector< const SCEVPredicate *, 3 > > > createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI)
Checks if SymbolicPHI can be rewritten as an AddRecExpr under some Predicates.
LLVM_ABI const SCEV * getTruncateOrZeroExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool isKnownViaInduction(CmpPredicate Pred, SCEVUse LHS, SCEVUse RHS)
We'd like to check the predicate on every iteration of the most dominated loop between loops used in ...
LLVM_ABI std::optional< APInt > computeConstantDifference(const SCEV *LHS, const SCEV *RHS)
Compute LHS - RHS and returns the result as an APInt if it is a constant, and std::nullopt if it isn'...
LLVM_ABI bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
LLVM_ABI const SCEV * getUDivExactExpr(SCEVUse LHS, SCEVUse RHS)
Get a canonical unsigned division expression, or something simpler if possible.
LLVM_ABI const SCEV * rewriteUsingPredicate(const SCEV *S, const Loop *L, const SCEVPredicate &A)
Re-writes the SCEV according to the Predicates in A.
LLVM_ABI std::pair< const SCEV *, const SCEV * > SplitIntoInitAndPostInc(const Loop *L, const SCEV *S)
Splits SCEV expression S into two SCEVs.
LLVM_ABI bool canReuseInstruction(const SCEV *S, Instruction *I, SmallVectorImpl< Instruction * > &DropPoisonGeneratingInsts)
Check whether it is poison-safe to represent the expression S using the instruction I.
LLVM_ABI bool isKnownPredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
LLVM_ABI const SCEV * getPredicatedSymbolicMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getSymbolicMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
LLVM_ABI const SCEV * getGEPExpr(GEPOperator *GEP, ArrayRef< SCEVUse > IndexExprs)
Returns an expression for a GEP.
LLVM_ABI const SCEV * getUMinExpr(SCEVUse LHS, SCEVUse RHS, bool Sequential=false)
LLVM_ABI void registerUser(const SCEV *User, ArrayRef< const SCEV * > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
LLVM_ABI bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the basic block is protected by a conditional between LHS and RHS.
LLVM_ABI const SCEV * getTruncateOrSignExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
LLVM_ABI bool containsErasedValue(const SCEV *S) const
Return true if the SCEV expression contains a Value that has been optimised out and is now a nullptr.
const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEV that is greater than or equal to (i.e.
const SCEV * getMulExpr(SCEVUse LHS, SCEVUse RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
APInt getSignedRangeMax(const SCEV *S)
Determine the max of the signed range for a particular SCEV.
LLVM_ABI void verify() const
LLVMContext & getContext() const
Implements a dense probed hash-table based set with some number of buckets stored inline.
Definition DenseSet.h:301
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
Definition SetVector.h:339
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Class to represent struct types.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition Type.h:46
Lightweight SCEV-to-VPlan expander.
Definition VPlanUtils.h:189
LLVM Value Representation.
Definition Value.h:75
LLVM_ABI void print(raw_ostream &O, bool IsForDebug=false) const
Implement operator<< on Value.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition CallingConv.h:24
unsigned combineHashValue(unsigned a, unsigned b)
Simplistic combination of 32-bit hash values into 32-bit hash values.
friend class Instruction
Iterator for Instructions in a `BasicBlock.
Definition BasicBlock.h:73
This is an optimization pass for GlobalISel generic memory operations.
FunctionAddr VTableAddr Value
Definition InstrProf.h:137
hash_code hash_value(const FixedPointSemantics &Val)
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)
FoldingSetBase::Node FoldingSetNode
Definition FoldingSet.h:404
LLVM_ABI bool VerifySCEV
SCEVUseT(SCEVPtrT) -> SCEVUseT< SCEVPtrT >
Deduction guide for various SCEV subclass pointers.
SCEVNoWrapFlags
NoWrapFlags are bitfield indices into SCEV's SubclassData.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
@ Other
Any other memory.
Definition ModRef.h:68
DWARFExpression::Operation Op
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
ArrayRef(const T &OneElt) -> ArrayRef< T >
constexpr unsigned BitWidth
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
BumpPtrAllocatorImpl<> BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition Allocator.h:383
SCEVUseT< const SCEV * > SCEVUse
Implement std::hash so that hash_code can be used in STL containers.
Definition BitVector.h:860
#define N
A CRTP mix-in that provides informational APIs needed for analysis passes.
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition Analysis.h:29
This struct provides a method for customizing the way a cast is performed.
Definition Casting.h:476
static CastReturnType castFailed()
Definition Casting.h:490
static CastReturnType doCast(const From &f)
Definition Casting.h:481
typename cast_retty< To, From >::ret_type CastReturnType
Definition Casting.h:479
static bool isPossible(const From &f)
Definition Casting.h:254
This class provides default implementations for FoldingSetTrait implementations.
Definition FoldingSet.h:116
static bool isEqual(const SCEVUse LHS, const SCEVUse RHS)
static unsigned getHashValue(SCEVUse U)
static unsigned getHashValue(const ScalarEvolution::FoldID &Val)
static bool isEqual(const ScalarEvolution::FoldID &LHS, const ScalarEvolution::FoldID &RHS)
An information struct used to provide DenseMap with the various necessary components for a given valu...
static void Profile(const SCEVPredicate &X, FoldingSetNodeID &ID)
static bool Equals(const SCEVPredicate &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)
static unsigned ComputeHash(const SCEVPredicate &X, FoldingSetNodeID &TempID)
static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)
static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID)
static void Profile(const SCEV &X, FoldingSetNodeID &ID)
This trait class is used to define behavior of how to "profile" (in the FoldingSet parlance) an objec...
Definition FoldingSet.h:146
static constexpr int NumLowBitsAvailable
The Low bits are used by the PointerIntPair.
static void * getAsVoidPointer(SCEVUse U)
static SCEVUse getFromVoidPointer(void *P)
A traits type that is used to handle pointer types and things that are just wrappers for pointers as ...
A CRTP mix-in for passes that should not be skipped.
static LLVM_ABI bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
bool operator==(const SCEVUseT &RHS) const
const SCEV * getCanonical() const
Return the canonical SCEV for this SCEVUse.
bool operator!=(const SCEVUseT &RHS) const
SCEVPtrT operator->() const
SCEVUseT(const SCEVUseT< OtherPtrT > &Other)
void * getOpaqueValue() const
bool isCanonical() const
Returns true if the SCEVUse is canonical, i.e.
SCEVNoWrapFlags getUseNoWrapFlags() const
const SCEV * getPointer() const
bool operator==(const SCEV *RHS) const
void dump() const
This method is used for debugging.
SCEVUseT(SCEVPtrT S, SCEVNoWrapFlags Flags)
Construct with NoWrapFlags; only NUW/NSW are encoded, NW is dropped.
SCEVNoWrapFlags getNoWrapFlags(SCEVNoWrapFlags Mask=SCEVNoWrapFlags::NoWrapMask) const
Return the no-wrap flags for this SCEVUse, which is the union of the use-specific flags and the under...
bool operator>(const SCEVUseT &RHS) const
PointerIntPair< SCEVPtrT, 2 > Base
bool operator!=(const SCEV *RHS) const
void print(raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
SCEVUseT(SCEVPtrT S)
Information about the number of loop iterations for which a loop exit's branch condition evaluates to...
LLVM_ABI ExitLimit(const SCEV *E)
Construct either an exact exit limit from a constant, or an unknown one from a SCEVCouldNotCompute.
bool hasAnyInfo() const
Test whether this ExitLimit contains any computed information, or whether it's all SCEVCouldNotComput...
SmallVector< const SCEVPredicate *, 4 > Predicates
A vector of predicate guards for this ExitLimit.
bool hasFullInfo() const
Test whether this ExitLimit contains all information.
LoopInvariantPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
static SimpleType getSimplifiedValue(SCEVUse &Val)
Define a template that can be specialized by smart pointers to reflect the fact that they are automat...
Definition Casting.h:34