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