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