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