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