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
200inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) {
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
368 return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & Mask);
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
378 return (SCEVWrapPredicate::IncrementWrapFlags)(Flags | OnFlags);
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.
396 IncrementWrapFlags getFlags() const { return 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 }
476 [[nodiscard]] static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags,
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 *getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
570 const SCEV *getZeroExtendExprImpl(const SCEV *Op, Type *Ty,
571 unsigned Depth = 0);
572 const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
573 const SCEV *getSignExtendExprImpl(const SCEV *Op, Type *Ty,
574 unsigned Depth = 0);
575 const SCEV *getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty);
576 const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty);
579 unsigned Depth = 0);
580 const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS,
582 unsigned Depth = 0) {
584 return getAddExpr(Ops, Flags, Depth);
585 }
586 const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
588 unsigned Depth = 0) {
589 SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
590 return getAddExpr(Ops, Flags, Depth);
591 }
594 unsigned Depth = 0);
595 const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS,
597 unsigned Depth = 0) {
599 return getMulExpr(Ops, Flags, Depth);
600 }
601 const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
603 unsigned Depth = 0) {
604 SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
605 return getMulExpr(Ops, Flags, Depth);
606 }
607 const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS);
608 const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS);
609 const SCEV *getURemExpr(const SCEV *LHS, const SCEV *RHS);
610 const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L,
611 SCEV::NoWrapFlags Flags);
613 const Loop *L, SCEV::NoWrapFlags Flags);
615 const Loop *L, SCEV::NoWrapFlags Flags) {
616 SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end());
617 return getAddRecExpr(NewOp, L, Flags);
618 }
619
620 /// Checks if \p SymbolicPHI can be rewritten as an AddRecExpr under some
621 /// Predicates. If successful return these <AddRecExpr, Predicates>;
622 /// The function is intended to be called from PSCEV (the caller will decide
623 /// whether to actually add the predicates and carry out the rewrites).
624 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
625 createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI);
626
627 /// Returns an expression for a GEP
628 ///
629 /// \p GEP The GEP. The indices contained in the GEP itself are ignored,
630 /// instead we use IndexExprs.
631 /// \p IndexExprs The expressions for the indices.
633 const SmallVectorImpl<const SCEV *> &IndexExprs);
634 const SCEV *getAbsExpr(const SCEV *Op, bool IsNSW);
635 const SCEV *getMinMaxExpr(SCEVTypes Kind,
639 const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS);
641 const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS);
643 const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS);
645 const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS,
646 bool Sequential = false);
648 bool Sequential = false);
649 const SCEV *getUnknown(Value *V);
650 const SCEV *getCouldNotCompute();
651
652 /// Return a SCEV for the constant 0 of a specific type.
653 const SCEV *getZero(Type *Ty) { return getConstant(Ty, 0); }
654
655 /// Return a SCEV for the constant 1 of a specific type.
656 const SCEV *getOne(Type *Ty) { return getConstant(Ty, 1); }
657
658 /// Return a SCEV for the constant -1 of a specific type.
659 const SCEV *getMinusOne(Type *Ty) {
660 return getConstant(Ty, -1, /*isSigned=*/true);
661 }
662
663 /// Return an expression for sizeof ScalableTy that is type IntTy, where
664 /// ScalableTy is a scalable vector type.
666 ScalableVectorType *ScalableTy);
667
668 /// Return an expression for the alloc size of AllocTy that is type IntTy
669 const SCEV *getSizeOfExpr(Type *IntTy, Type *AllocTy);
670
671 /// Return an expression for the store size of StoreTy that is type IntTy
672 const SCEV *getStoreSizeOfExpr(Type *IntTy, Type *StoreTy);
673
674 /// Return an expression for offsetof on the given field with type IntTy
675 const SCEV *getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo);
676
677 /// Return the SCEV object corresponding to -V.
678 const SCEV *getNegativeSCEV(const SCEV *V,
680
681 /// Return the SCEV object corresponding to ~V.
682 const SCEV *getNotSCEV(const SCEV *V);
683
684 /// Return LHS-RHS. Minus is represented in SCEV as A+B*-1.
685 ///
686 /// If the LHS and RHS are pointers which don't share a common base
687 /// (according to getPointerBase()), this returns a SCEVCouldNotCompute.
688 /// To compute the difference between two unrelated pointers, you can
689 /// explicitly convert the arguments using getPtrToIntExpr(), for pointer
690 /// types that support it.
691 const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
693 unsigned Depth = 0);
694
695 /// Compute ceil(N / D). N and D are treated as unsigned values.
696 ///
697 /// Since SCEV doesn't have native ceiling division, this generates a
698 /// SCEV expression of the following form:
699 ///
700 /// umin(N, 1) + floor((N - umin(N, 1)) / D)
701 ///
702 /// A denominator of zero or poison is handled the same way as getUDivExpr().
703 const SCEV *getUDivCeilSCEV(const SCEV *N, const SCEV *D);
704
705 /// Return a SCEV corresponding to a conversion of the input value to the
706 /// specified type. If the type must be extended, it is zero extended.
707 const SCEV *getTruncateOrZeroExtend(const SCEV *V, Type *Ty,
708 unsigned Depth = 0);
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 sign extended.
712 const SCEV *getTruncateOrSignExtend(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 zero extended. The
717 /// conversion must not be narrowing.
718 const SCEV *getNoopOrZeroExtend(const SCEV *V, Type *Ty);
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 sign extended. The
722 /// conversion must not be narrowing.
723 const SCEV *getNoopOrSignExtend(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 extended with
727 /// unspecified bits. The conversion must not be narrowing.
728 const SCEV *getNoopOrAnyExtend(const SCEV *V, Type *Ty);
729
730 /// Return a SCEV corresponding to a conversion of the input value to the
731 /// specified type. The conversion must not be widening.
732 const SCEV *getTruncateOrNoop(const SCEV *V, Type *Ty);
733
734 /// Promote the operands to the wider of the types using zero-extension, and
735 /// then perform a umax operation with them.
736 const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS);
737
738 /// Promote the operands to the wider of the types using zero-extension, and
739 /// then perform a umin operation with them.
740 const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS,
741 bool Sequential = false);
742
743 /// Promote the operands to the wider of the types using zero-extension, and
744 /// then perform a umin operation with them. N-ary function.
746 bool Sequential = false);
747
748 /// Transitively follow the chain of pointer-type operands until reaching a
749 /// SCEV that does not have a single pointer operand. This returns a
750 /// SCEVUnknown pointer for well-formed pointer-type expressions, but corner
751 /// cases do exist.
752 const SCEV *getPointerBase(const SCEV *V);
753
754 /// Compute an expression equivalent to S - getPointerBase(S).
755 const SCEV *removePointerBase(const SCEV *S);
756
757 /// Return a SCEV expression for the specified value at the specified scope
758 /// in the program. The L value specifies a loop nest to evaluate the
759 /// expression at, where null is the top-level or a specified loop is
760 /// immediately inside of the loop.
761 ///
762 /// This method can be used to compute the exit value for a variable defined
763 /// in a loop by querying what the value will hold in the parent loop.
764 ///
765 /// In the case that a relevant loop exit value cannot be computed, the
766 /// original value V is returned.
767 const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L);
768
769 /// This is a convenience function which does getSCEVAtScope(getSCEV(V), L).
770 const SCEV *getSCEVAtScope(Value *V, const Loop *L);
771
772 /// Test whether entry to the loop is protected by a conditional between LHS
773 /// and RHS. This is used to help avoid max expressions in loop trip
774 /// counts, and to eliminate casts.
776 const SCEV *LHS, const SCEV *RHS);
777
778 /// Test whether entry to the basic block is protected by a conditional
779 /// between LHS and RHS.
781 ICmpInst::Predicate Pred, const SCEV *LHS,
782 const SCEV *RHS);
783
784 /// Test whether the backedge of the loop is protected by a conditional
785 /// between LHS and RHS. This is used to eliminate casts.
787 const SCEV *LHS, const SCEV *RHS);
788
789 /// Convert from an "exit count" (i.e. "backedge taken count") to a "trip
790 /// count". A "trip count" is the number of times the header of the loop
791 /// will execute if an exit is taken after the specified number of backedges
792 /// have been taken. (e.g. TripCount = ExitCount + 1). Note that the
793 /// expression can overflow if ExitCount = UINT_MAX. \p Extend controls
794 /// how potential overflow is handled. If true, a wider result type is
795 /// returned. ex: EC = 255 (i8), TC = 256 (i9). If false, result unsigned
796 /// wraps with 2s-complement semantics. ex: EC = 255 (i8), TC = 0 (i8)
797 const SCEV *getTripCountFromExitCount(const SCEV *ExitCount,
798 bool Extend = true);
799
800 /// Returns the exact trip count of the loop if we can compute it, and
801 /// the result is a small constant. '0' is used to represent an unknown
802 /// or non-constant trip count. Note that a trip count is simply one more
803 /// than the backedge taken count for the loop.
804 unsigned getSmallConstantTripCount(const Loop *L);
805
806 /// Return the exact trip count for this loop if we exit through ExitingBlock.
807 /// '0' is used to represent an unknown or non-constant trip count. Note
808 /// that a trip count is simply one more than the backedge taken count for
809 /// the same exit.
810 /// This "trip count" assumes that control exits via ExitingBlock. More
811 /// precisely, it is the number of times that control will reach ExitingBlock
812 /// before taking the branch. For loops with multiple exits, it may not be
813 /// the number times that the loop header executes if the loop exits
814 /// prematurely via another branch.
815 unsigned getSmallConstantTripCount(const Loop *L,
816 const BasicBlock *ExitingBlock);
817
818 /// Returns the upper bound of the loop trip count as a normal unsigned
819 /// value.
820 /// Returns 0 if the trip count is unknown or not constant.
821 unsigned getSmallConstantMaxTripCount(const Loop *L);
822
823 /// Returns the upper bound of the loop trip count infered from array size.
824 /// Can not access bytes starting outside the statically allocated size
825 /// without being immediate UB.
826 /// Returns SCEVCouldNotCompute if the trip count could not inferred
827 /// from array accesses.
829
830 /// Returns the largest constant divisor of the trip count as a normal
831 /// unsigned value, if possible. This means that the actual trip count is
832 /// always a multiple of the returned value. Returns 1 if the trip count is
833 /// unknown or not guaranteed to be the multiple of a constant., Will also
834 /// return 1 if the trip count is very large (>= 2^32).
835 /// Note that the argument is an exit count for loop L, NOT a trip count.
836 unsigned getSmallConstantTripMultiple(const Loop *L,
837 const SCEV *ExitCount);
838
839 /// Returns the largest constant divisor of the trip count of the
840 /// loop. Will return 1 if no trip count could be computed, or if a
841 /// divisor could not be found.
842 unsigned getSmallConstantTripMultiple(const Loop *L);
843
844 /// Returns the largest constant divisor of the trip count of this loop as a
845 /// normal unsigned value, if possible. This means that the actual trip
846 /// count is always a multiple of the returned value (don't forget the trip
847 /// count could very well be zero as well!). As explained in the comments
848 /// for getSmallConstantTripCount, this assumes that control exits the loop
849 /// via ExitingBlock.
850 unsigned getSmallConstantTripMultiple(const Loop *L,
851 const BasicBlock *ExitingBlock);
852
853 /// The terms "backedge taken count" and "exit count" are used
854 /// interchangeably to refer to the number of times the backedge of a loop
855 /// has executed before the loop is exited.
857 /// An expression exactly describing the number of times the backedge has
858 /// executed when a loop is exited.
860 /// A constant which provides an upper bound on the exact trip count.
862 /// An expression which provides an upper bound on the exact trip count.
864 };
865
866 /// Return the number of times the backedge executes before the given exit
867 /// would be taken; if not exactly computable, return SCEVCouldNotCompute.
868 /// For a single exit loop, this value is equivelent to the result of
869 /// getBackedgeTakenCount. The loop is guaranteed to exit (via *some* exit)
870 /// before the backedge is executed (ExitCount + 1) times. Note that there
871 /// is no guarantee about *which* exit is taken on the exiting iteration.
872 const SCEV *getExitCount(const Loop *L, const BasicBlock *ExitingBlock,
873 ExitCountKind Kind = Exact);
874
875 /// If the specified loop has a predictable backedge-taken count, return it,
876 /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count is
877 /// the number of times the loop header will be branched to from within the
878 /// loop, assuming there are no abnormal exists like exception throws. This is
879 /// one less than the trip count of the loop, since it doesn't count the first
880 /// iteration, when the header is branched to from outside the loop.
881 ///
882 /// Note that it is not valid to call this method on a loop without a
883 /// loop-invariant backedge-taken count (see
884 /// hasLoopInvariantBackedgeTakenCount).
885 const SCEV *getBackedgeTakenCount(const Loop *L, ExitCountKind Kind = Exact);
886
887 /// Similar to getBackedgeTakenCount, except it will add a set of
888 /// SCEV predicates to Predicates that are required to be true in order for
889 /// the answer to be correct. Predicates can be checked with run-time
890 /// checks and can be used to perform loop versioning.
893
894 /// When successful, this returns a SCEVConstant that is greater than or equal
895 /// to (i.e. a "conservative over-approximation") of the value returend by
896 /// getBackedgeTakenCount. If such a value cannot be computed, it returns the
897 /// SCEVCouldNotCompute object.
900 }
901
902 /// When successful, this returns a SCEV 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 /// Return true if the backedge taken count is either the value returned by
911 /// getConstantMaxBackedgeTakenCount or zero.
912 bool isBackedgeTakenCountMaxOrZero(const Loop *L);
913
914 /// Return true if the specified loop has an analyzable loop-invariant
915 /// backedge-taken count.
917
918 // This method should be called by the client when it made any change that
919 // would invalidate SCEV's answers, and the client wants to remove all loop
920 // information held internally by ScalarEvolution. This is intended to be used
921 // when the alternative to forget a loop is too expensive (i.e. large loop
922 // bodies).
923 void forgetAllLoops();
924
925 /// This method should be called by the client when it has changed a loop in
926 /// a way that may effect ScalarEvolution's ability to compute a trip count,
927 /// or if the loop is deleted. This call is potentially expensive for large
928 /// loop bodies.
929 void forgetLoop(const Loop *L);
930
931 // This method invokes forgetLoop for the outermost loop of the given loop
932 // \p L, making ScalarEvolution forget about all this subtree. This needs to
933 // be done whenever we make a transform that may affect the parameters of the
934 // outer loop, such as exit counts for branches.
935 void forgetTopmostLoop(const Loop *L);
936
937 /// This method should be called by the client when it has changed a value
938 /// in a way that may effect its value, or which may disconnect it from a
939 /// def-use chain linking it to a loop.
940 void forgetValue(Value *V);
941
942 /// Called when the client has changed the disposition of values in
943 /// this loop.
944 ///
945 /// We don't have a way to invalidate per-loop dispositions. Clear and
946 /// recompute is simpler.
948
949 /// Called when the client has changed the disposition of values in
950 /// a loop or block.
951 ///
952 /// We don't have a way to invalidate per-loop/per-block dispositions. Clear
953 /// and recompute is simpler.
954 void forgetBlockAndLoopDispositions(Value *V = nullptr);
955
956 /// Determine the minimum number of zero bits that S is guaranteed to end in
957 /// (at every loop iteration). It is, at the same time, the minimum number
958 /// of times S is divisible by 2. For example, given {4,+,8} it returns 2.
959 /// If S is guaranteed to be 0, it returns the bitwidth of S.
961
962 /// Determine the unsigned range for a particular SCEV.
963 /// NOTE: This returns a copy of the reference returned by getRangeRef.
965 return getRangeRef(S, HINT_RANGE_UNSIGNED);
966 }
967
968 /// Determine the min of the unsigned range for a particular SCEV.
970 return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMin();
971 }
972
973 /// Determine the max of the unsigned range for a particular SCEV.
975 return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMax();
976 }
977
978 /// Determine the signed range for a particular SCEV.
979 /// NOTE: This returns a copy of the reference returned by getRangeRef.
981 return getRangeRef(S, HINT_RANGE_SIGNED);
982 }
983
984 /// Determine the min of the signed range for a particular SCEV.
986 return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMin();
987 }
988
989 /// Determine the max of the signed range for a particular SCEV.
991 return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMax();
992 }
993
994 /// Test if the given expression is known to be negative.
995 bool isKnownNegative(const SCEV *S);
996
997 /// Test if the given expression is known to be positive.
998 bool isKnownPositive(const SCEV *S);
999
1000 /// Test if the given expression is known to be non-negative.
1001 bool isKnownNonNegative(const SCEV *S);
1002
1003 /// Test if the given expression is known to be non-positive.
1004 bool isKnownNonPositive(const SCEV *S);
1005
1006 /// Test if the given expression is known to be non-zero.
1007 bool isKnownNonZero(const SCEV *S);
1008
1009 /// Splits SCEV expression \p S into two SCEVs. One of them is obtained from
1010 /// \p S by substitution of all AddRec sub-expression related to loop \p L
1011 /// with initial value of that SCEV. The second is obtained from \p S by
1012 /// substitution of all AddRec sub-expressions related to loop \p L with post
1013 /// increment of this AddRec in the loop \p L. In both cases all other AddRec
1014 /// sub-expressions (not related to \p L) remain the same.
1015 /// If the \p S contains non-invariant unknown SCEV the function returns
1016 /// CouldNotCompute SCEV in both values of std::pair.
1017 /// For example, for SCEV S={0, +, 1}<L1> + {0, +, 1}<L2> and loop L=L1
1018 /// the function returns pair:
1019 /// first = {0, +, 1}<L2>
1020 /// second = {1, +, 1}<L1> + {0, +, 1}<L2>
1021 /// We can see that for the first AddRec sub-expression it was replaced with
1022 /// 0 (initial value) for the first element and to {1, +, 1}<L1> (post
1023 /// increment value) for the second one. In both cases AddRec expression
1024 /// related to L2 remains the same.
1025 std::pair<const SCEV *, const SCEV *> SplitIntoInitAndPostInc(const Loop *L,
1026 const SCEV *S);
1027
1028 /// We'd like to check the predicate on every iteration of the most dominated
1029 /// loop between loops used in LHS and RHS.
1030 /// To do this we use the following list of steps:
1031 /// 1. Collect set S all loops on which either LHS or RHS depend.
1032 /// 2. If S is non-empty
1033 /// a. Let PD be the element of S which is dominated by all other elements.
1034 /// b. Let E(LHS) be value of LHS on entry of PD.
1035 /// To get E(LHS), we should just take LHS and replace all AddRecs that are
1036 /// attached to PD on with their entry values.
1037 /// Define E(RHS) in the same way.
1038 /// c. Let B(LHS) be value of L on backedge of PD.
1039 /// To get B(LHS), we should just take LHS and replace all AddRecs that are
1040 /// attached to PD on with their backedge values.
1041 /// Define B(RHS) in the same way.
1042 /// d. Note that E(LHS) and E(RHS) are automatically available on entry of PD,
1043 /// so we can assert on that.
1044 /// e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) &&
1045 /// isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS))
1047 const SCEV *RHS);
1048
1049 /// Test if the given expression is known to satisfy the condition described
1050 /// by Pred, LHS, and RHS.
1051 bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS,
1052 const SCEV *RHS);
1053
1054 /// Check whether the condition described by Pred, LHS, and RHS is true or
1055 /// false. If we know it, return the evaluation of this condition. If neither
1056 /// is proved, return std::nullopt.
1057 std::optional<bool> evaluatePredicate(ICmpInst::Predicate Pred,
1058 const SCEV *LHS, const SCEV *RHS);
1059
1060 /// Test if the given expression is known to satisfy the condition described
1061 /// by Pred, LHS, and RHS in the given Context.
1063 const SCEV *RHS, const Instruction *CtxI);
1064
1065 /// Check whether the condition described by Pred, LHS, and RHS is true or
1066 /// false in the given \p Context. If we know it, return the evaluation of
1067 /// this condition. If neither is proved, return std::nullopt.
1068 std::optional<bool> evaluatePredicateAt(ICmpInst::Predicate Pred,
1069 const SCEV *LHS, const SCEV *RHS,
1070 const Instruction *CtxI);
1071
1072 /// Test if the condition described by Pred, LHS, RHS is known to be true on
1073 /// every iteration of the loop of the recurrency LHS.
1075 const SCEVAddRecExpr *LHS, const SCEV *RHS);
1076
1077 /// Information about the number of loop iterations for which a loop exit's
1078 /// branch condition evaluates to the not-taken path. This is a temporary
1079 /// pair of exact and max expressions that are eventually summarized in
1080 /// ExitNotTakenInfo and BackedgeTakenInfo.
1081 struct ExitLimit {
1082 const SCEV *ExactNotTaken; // The exit is not taken exactly this many times
1083 const SCEV *ConstantMaxNotTaken; // The exit is not taken at most this many
1084 // times
1086
1087 // Not taken either exactly ConstantMaxNotTaken or zero times
1088 bool MaxOrZero = false;
1089
1090 /// A set of predicate guards for this ExitLimit. The result is only valid
1091 /// if all of the predicates in \c Predicates evaluate to 'true' at
1092 /// run-time.
1094
1096 assert(!isa<SCEVUnionPredicate>(P) && "Only add leaf predicates here!");
1097 Predicates.insert(P);
1098 }
1099
1100 /// Construct either an exact exit limit from a constant, or an unknown
1101 /// one from a SCEVCouldNotCompute. No other types of SCEVs are allowed
1102 /// as arguments and asserts enforce that internally.
1103 /*implicit*/ ExitLimit(const SCEV *E);
1104
1105 ExitLimit(
1106 const SCEV *E, const SCEV *ConstantMaxNotTaken,
1107 const SCEV *SymbolicMaxNotTaken, bool MaxOrZero,
1109 std::nullopt);
1110
1111 ExitLimit(const SCEV *E, const SCEV *ConstantMaxNotTaken,
1112 const SCEV *SymbolicMaxNotTaken, bool MaxOrZero,
1114
1115 /// Test whether this ExitLimit contains any computed information, or
1116 /// whether it's all SCEVCouldNotCompute values.
1117 bool hasAnyInfo() const {
1118 return !isa<SCEVCouldNotCompute>(ExactNotTaken) ||
1119 !isa<SCEVCouldNotCompute>(ConstantMaxNotTaken);
1120 }
1121
1122 /// Test whether this ExitLimit contains all information.
1123 bool hasFullInfo() const {
1124 return !isa<SCEVCouldNotCompute>(ExactNotTaken);
1125 }
1126 };
1127
1128 /// Compute the number of times the backedge of the specified loop will
1129 /// execute if its exit condition were a conditional branch of ExitCond.
1130 ///
1131 /// \p ControlsExit is true if ExitCond directly controls the exit
1132 /// branch. In this case, we can assume that the loop exits only if the
1133 /// condition is true and can infer that failing to meet the condition prior
1134 /// to integer wraparound results in undefined behavior.
1135 ///
1136 /// If \p AllowPredicates is set, this call will try to use a minimal set of
1137 /// SCEV predicates in order to return an exact answer.
1138 ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond,
1139 bool ExitIfTrue, bool ControlsExit,
1140 bool AllowPredicates = false);
1141
1142 /// A predicate is said to be monotonically increasing if may go from being
1143 /// false to being true as the loop iterates, but never the other way
1144 /// around. A predicate is said to be monotonically decreasing if may go
1145 /// from being true to being false as the loop iterates, but never the other
1146 /// way around.
1151
1152 /// If, for all loop invariant X, the predicate "LHS `Pred` X" is
1153 /// monotonically increasing or decreasing, returns
1154 /// Some(MonotonicallyIncreasing) and Some(MonotonicallyDecreasing)
1155 /// respectively. If we could not prove either of these facts, returns
1156 /// std::nullopt.
1157 std::optional<MonotonicPredicateType>
1159 ICmpInst::Predicate Pred);
1160
1163 const SCEV *LHS;
1164 const SCEV *RHS;
1165
1167 const SCEV *RHS)
1168 : Pred(Pred), LHS(LHS), RHS(RHS) {}
1169 };
1170 /// If the result of the predicate LHS `Pred` RHS is loop invariant with
1171 /// respect to L, return a LoopInvariantPredicate with LHS and RHS being
1172 /// invariants, available at L's entry. Otherwise, return std::nullopt.
1173 std::optional<LoopInvariantPredicate>
1175 const SCEV *RHS, const Loop *L,
1176 const Instruction *CtxI = nullptr);
1177
1178 /// If the result of the predicate LHS `Pred` RHS is loop invariant with
1179 /// respect to L at given Context during at least first MaxIter iterations,
1180 /// return a LoopInvariantPredicate with LHS and RHS being invariants,
1181 /// available at L's entry. Otherwise, return std::nullopt. The predicate
1182 /// should be the loop's exit condition.
1183 std::optional<LoopInvariantPredicate>
1185 const SCEV *LHS,
1186 const SCEV *RHS, const Loop *L,
1187 const Instruction *CtxI,
1188 const SCEV *MaxIter);
1189
1190 std::optional<LoopInvariantPredicate>
1192 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L,
1193 const Instruction *CtxI, const SCEV *MaxIter);
1194
1195 /// Simplify LHS and RHS in a comparison with predicate Pred. Return true
1196 /// iff any changes were made. If the operands are provably equal or
1197 /// unequal, LHS and RHS are set to the same value and Pred is set to either
1198 /// ICMP_EQ or ICMP_NE. ControllingFiniteLoop is set if this comparison
1199 /// controls the exit of a loop known to have a finite number of iterations.
1201 const SCEV *&RHS, unsigned Depth = 0,
1202 bool ControllingFiniteLoop = false);
1203
1204 /// Return the "disposition" of the given SCEV with respect to the given
1205 /// loop.
1206 LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L);
1207
1208 /// Return true if the value of the given SCEV is unchanging in the
1209 /// specified loop.
1210 bool isLoopInvariant(const SCEV *S, const Loop *L);
1211
1212 /// Determine if the SCEV can be evaluated at loop's entry. It is true if it
1213 /// doesn't depend on a SCEVUnknown of an instruction which is dominated by
1214 /// the header of loop L.
1215 bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L);
1216
1217 /// Return true if the given SCEV changes value in a known way in the
1218 /// specified loop. This property being true implies that the value is
1219 /// variant in the loop AND that we can emit an expression to compute the
1220 /// value of the expression at any particular loop iteration.
1221 bool hasComputableLoopEvolution(const SCEV *S, const Loop *L);
1222
1223 /// Return the "disposition" of the given SCEV with respect to the given
1224 /// block.
1226
1227 /// Return true if elements that makes up the given SCEV dominate the
1228 /// specified basic block.
1229 bool dominates(const SCEV *S, const BasicBlock *BB);
1230
1231 /// Return true if elements that makes up the given SCEV properly dominate
1232 /// the specified basic block.
1233 bool properlyDominates(const SCEV *S, const BasicBlock *BB);
1234
1235 /// Test whether the given SCEV has Op as a direct or indirect operand.
1236 bool hasOperand(const SCEV *S, const SCEV *Op) const;
1237
1238 /// Return the size of an element read or written by Inst.
1239 const SCEV *getElementSize(Instruction *Inst);
1240
1241 void print(raw_ostream &OS) const;
1242 void verify() const;
1243 bool invalidate(Function &F, const PreservedAnalyses &PA,
1245
1246 /// Return the DataLayout associated with the module this SCEV instance is
1247 /// operating on.
1248 const DataLayout &getDataLayout() const {
1249 return F.getParent()->getDataLayout();
1250 }
1251
1252 const SCEVPredicate *getEqualPredicate(const SCEV *LHS, const SCEV *RHS);
1254 const SCEV *LHS, const SCEV *RHS);
1255
1256 const SCEVPredicate *
1259
1260 /// Re-writes the SCEV according to the Predicates in \p A.
1261 const SCEV *rewriteUsingPredicate(const SCEV *S, const Loop *L,
1262 const SCEVPredicate &A);
1263 /// Tries to convert the \p S expression to an AddRec expression,
1264 /// adding additional predicates to \p Preds as required.
1266 const SCEV *S, const Loop *L,
1268
1269 /// Compute \p LHS - \p RHS and returns the result as an APInt if it is a
1270 /// constant, and std::nullopt if it isn't.
1271 ///
1272 /// This is intended to be a cheaper version of getMinusSCEV. We can be
1273 /// frugal here since we just bail out of actually constructing and
1274 /// canonicalizing an expression in the cases where the result isn't going
1275 /// to be a constant.
1276 std::optional<APInt> computeConstantDifference(const SCEV *LHS,
1277 const SCEV *RHS);
1278
1279 /// Update no-wrap flags of an AddRec. This may drop the cached info about
1280 /// this AddRec (such as range info) in case if new flags may potentially
1281 /// sharpen it.
1282 void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags);
1283
1284 /// Try to apply information from loop guards for \p L to \p Expr.
1285 const SCEV *applyLoopGuards(const SCEV *Expr, const Loop *L);
1286
1287 /// Return true if the loop has no abnormal exits. That is, if the loop
1288 /// is not infinite, it must exit through an explicit edge in the CFG.
1289 /// (As opposed to either a) throwing out of the function or b) entering a
1290 /// well defined infinite loop in some callee.)
1292 return getLoopProperties(L).HasNoAbnormalExits;
1293 }
1294
1295 /// Return true if this loop is finite by assumption. That is,
1296 /// to be infinite, it must also be undefined.
1297 bool loopIsFiniteByAssumption(const Loop *L);
1298
1299 class FoldID {
1301
1302 public:
1303 void addInteger(unsigned long I) { Bits.push_back(I); }
1304 void addInteger(unsigned I) { Bits.push_back(I); }
1305 void addInteger(int I) { Bits.push_back(I); }
1306
1307 void addInteger(unsigned long long I) {
1308 addInteger(unsigned(I));
1309 addInteger(unsigned(I >> 32));
1310 }
1311
1312 void addPointer(const void *Ptr) {
1313 // Note: this adds pointers to the hash using sizes and endianness that
1314 // depend on the host. It doesn't matter, however, because hashing on
1315 // pointer values is inherently unstable. Nothing should depend on the
1316 // ordering of nodes in the folding set.
1317 static_assert(sizeof(uintptr_t) <= sizeof(unsigned long long),
1318 "unexpected pointer size");
1319 addInteger(reinterpret_cast<uintptr_t>(Ptr));
1320 }
1321
1322 unsigned computeHash() const {
1323 unsigned Hash = Bits.size();
1324 for (unsigned I = 0; I != Bits.size(); ++I)
1325 Hash = detail::combineHashValue(Hash, Bits[I]);
1326 return Hash;
1327 }
1328 bool operator==(const FoldID &RHS) const {
1329 if (Bits.size() != RHS.Bits.size())
1330 return false;
1331 for (unsigned I = 0; I != Bits.size(); ++I)
1332 if (Bits[I] != RHS.Bits[I])
1333 return false;
1334 return true;
1335 }
1336 };
1337
1338private:
1339 /// A CallbackVH to arrange for ScalarEvolution to be notified whenever a
1340 /// Value is deleted.
1341 class SCEVCallbackVH final : public CallbackVH {
1342 ScalarEvolution *SE;
1343
1344 void deleted() override;
1345 void allUsesReplacedWith(Value *New) override;
1346
1347 public:
1348 SCEVCallbackVH(Value *V, ScalarEvolution *SE = nullptr);
1349 };
1350
1351 friend class SCEVCallbackVH;
1352 friend class SCEVExpander;
1353 friend class SCEVUnknown;
1354
1355 /// The function we are analyzing.
1356 Function &F;
1357
1358 /// Does the module have any calls to the llvm.experimental.guard intrinsic
1359 /// at all? If this is false, we avoid doing work that will only help if
1360 /// thare are guards present in the IR.
1361 bool HasGuards;
1362
1363 /// The target library information for the target we are targeting.
1364 TargetLibraryInfo &TLI;
1365
1366 /// The tracker for \@llvm.assume intrinsics in this function.
1367 AssumptionCache &AC;
1368
1369 /// The dominator tree.
1370 DominatorTree &DT;
1371
1372 /// The loop information for the function we are currently analyzing.
1373 LoopInfo &LI;
1374
1375 /// This SCEV is used to represent unknown trip counts and things.
1376 std::unique_ptr<SCEVCouldNotCompute> CouldNotCompute;
1377
1378 /// The type for HasRecMap.
1380
1381 /// This is a cache to record whether a SCEV contains any scAddRecExpr.
1382 HasRecMapType HasRecMap;
1383
1384 /// The type for ExprValueMap.
1387
1388 /// ExprValueMap -- This map records the original values from which
1389 /// the SCEV expr is generated from.
1390 ExprValueMapType ExprValueMap;
1391
1392 /// The type for ValueExprMap.
1393 using ValueExprMapType =
1395
1396 /// This is a cache of the values we have analyzed so far.
1397 ValueExprMapType ValueExprMap;
1398
1399 /// This is a cache for expressions that got folded to a different existing
1400 /// SCEV.
1403
1404 /// Mark predicate values currently being processed by isImpliedCond.
1405 SmallPtrSet<const Value *, 6> PendingLoopPredicates;
1406
1407 /// Mark SCEVUnknown Phis currently being processed by getRangeRef.
1408 SmallPtrSet<const PHINode *, 6> PendingPhiRanges;
1409
1410 /// Mark SCEVUnknown Phis currently being processed by getRangeRefIter.
1411 SmallPtrSet<const PHINode *, 6> PendingPhiRangesIter;
1412
1413 // Mark SCEVUnknown Phis currently being processed by isImpliedViaMerge.
1414 SmallPtrSet<const PHINode *, 6> PendingMerges;
1415
1416 /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of
1417 /// conditions dominating the backedge of a loop.
1418 bool WalkingBEDominatingConds = false;
1419
1420 /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a
1421 /// predicate by splitting it into a set of independent predicates.
1422 bool ProvingSplitPredicate = false;
1423
1424 /// Memoized values for the GetMinTrailingZeros
1425 DenseMap<const SCEV *, uint32_t> MinTrailingZerosCache;
1426
1427 /// Return the Value set from which the SCEV expr is generated.
1428 ArrayRef<Value *> getSCEVValues(const SCEV *S);
1429
1430 /// Private helper method for the GetMinTrailingZeros method
1431 uint32_t GetMinTrailingZerosImpl(const SCEV *S);
1432
1433 /// Information about the number of times a particular loop exit may be
1434 /// reached before exiting the loop.
1435 struct ExitNotTakenInfo {
1436 PoisoningVH<BasicBlock> ExitingBlock;
1437 const SCEV *ExactNotTaken;
1438 const SCEV *ConstantMaxNotTaken;
1439 const SCEV *SymbolicMaxNotTaken;
1441
1442 explicit ExitNotTakenInfo(
1443 PoisoningVH<BasicBlock> ExitingBlock, const SCEV *ExactNotTaken,
1444 const SCEV *ConstantMaxNotTaken, const SCEV *SymbolicMaxNotTaken,
1445 const SmallPtrSet<const SCEVPredicate *, 4> &Predicates)
1446 : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken),
1447 ConstantMaxNotTaken(ConstantMaxNotTaken),
1448 SymbolicMaxNotTaken(SymbolicMaxNotTaken), Predicates(Predicates) {}
1449
1450 bool hasAlwaysTruePredicate() const {
1451 return Predicates.empty();
1452 }
1453 };
1454
1455 /// Information about the backedge-taken count of a loop. This currently
1456 /// includes an exact count and a maximum count.
1457 ///
1458 class BackedgeTakenInfo {
1459 friend class ScalarEvolution;
1460
1461 /// A list of computable exits and their not-taken counts. Loops almost
1462 /// never have more than one computable exit.
1463 SmallVector<ExitNotTakenInfo, 1> ExitNotTaken;
1464
1465 /// Expression indicating the least constant maximum backedge-taken count of
1466 /// the loop that is known, or a SCEVCouldNotCompute. This expression is
1467 /// only valid if the redicates associated with all loop exits are true.
1468 const SCEV *ConstantMax = nullptr;
1469
1470 /// Indicating if \c ExitNotTaken has an element for every exiting block in
1471 /// the loop.
1472 bool IsComplete = false;
1473
1474 /// Expression indicating the least maximum backedge-taken count of the loop
1475 /// that is known, or a SCEVCouldNotCompute. Lazily computed on first query.
1476 const SCEV *SymbolicMax = nullptr;
1477
1478 /// True iff the backedge is taken either exactly Max or zero times.
1479 bool MaxOrZero = false;
1480
1481 bool isComplete() const { return IsComplete; }
1482 const SCEV *getConstantMax() const { return ConstantMax; }
1483
1484 public:
1485 BackedgeTakenInfo() = default;
1486 BackedgeTakenInfo(BackedgeTakenInfo &&) = default;
1487 BackedgeTakenInfo &operator=(BackedgeTakenInfo &&) = default;
1488
1489 using EdgeExitInfo = std::pair<BasicBlock *, ExitLimit>;
1490
1491 /// Initialize BackedgeTakenInfo from a list of exact exit counts.
1492 BackedgeTakenInfo(ArrayRef<EdgeExitInfo> ExitCounts, bool IsComplete,
1493 const SCEV *ConstantMax, bool MaxOrZero);
1494
1495 /// Test whether this BackedgeTakenInfo contains any computed information,
1496 /// or whether it's all SCEVCouldNotCompute values.
1497 bool hasAnyInfo() const {
1498 return !ExitNotTaken.empty() ||
1499 !isa<SCEVCouldNotCompute>(getConstantMax());
1500 }
1501
1502 /// Test whether this BackedgeTakenInfo contains complete information.
1503 bool hasFullInfo() const { return isComplete(); }
1504
1505 /// Return an expression indicating the exact *backedge-taken*
1506 /// count of the loop if it is known or SCEVCouldNotCompute
1507 /// otherwise. If execution makes it to the backedge on every
1508 /// iteration (i.e. there are no abnormal exists like exception
1509 /// throws and thread exits) then this is the number of times the
1510 /// loop header will execute minus one.
1511 ///
1512 /// If the SCEV predicate associated with the answer can be different
1513 /// from AlwaysTrue, we must add a (non null) Predicates argument.
1514 /// The SCEV predicate associated with the answer will be added to
1515 /// Predicates. A run-time check needs to be emitted for the SCEV
1516 /// predicate in order for the answer to be valid.
1517 ///
1518 /// Note that we should always know if we need to pass a predicate
1519 /// argument or not from the way the ExitCounts vector was computed.
1520 /// If we allowed SCEV predicates to be generated when populating this
1521 /// vector, this information can contain them and therefore a
1522 /// SCEVPredicate argument should be added to getExact.
1523 const SCEV *getExact(const Loop *L, ScalarEvolution *SE,
1524 SmallVector<const SCEVPredicate *, 4> *Predicates = nullptr) const;
1525
1526 /// Return the number of times this loop exit may fall through to the back
1527 /// edge, or SCEVCouldNotCompute. The loop is guaranteed not to exit via
1528 /// this block before this number of iterations, but may exit via another
1529 /// block.
1530 const SCEV *getExact(const BasicBlock *ExitingBlock,
1531 ScalarEvolution *SE) const;
1532
1533 /// Get the constant max backedge taken count for the loop.
1534 const SCEV *getConstantMax(ScalarEvolution *SE) const;
1535
1536 /// Get the constant max backedge taken count for the particular loop exit.
1537 const SCEV *getConstantMax(const BasicBlock *ExitingBlock,
1538 ScalarEvolution *SE) const;
1539
1540 /// Get the symbolic max backedge taken count for the loop.
1541 const SCEV *getSymbolicMax(const Loop *L, ScalarEvolution *SE);
1542
1543 /// Get the symbolic max backedge taken count for the particular loop exit.
1544 const SCEV *getSymbolicMax(const BasicBlock *ExitingBlock,
1545 ScalarEvolution *SE) const;
1546
1547 /// Return true if the number of times this backedge is taken is either the
1548 /// value returned by getConstantMax or zero.
1549 bool isConstantMaxOrZero(ScalarEvolution *SE) const;
1550 };
1551
1552 /// Cache the backedge-taken count of the loops for this function as they
1553 /// are computed.
1554 DenseMap<const Loop *, BackedgeTakenInfo> BackedgeTakenCounts;
1555
1556 /// Cache the predicated backedge-taken count of the loops for this
1557 /// function as they are computed.
1558 DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts;
1559
1560 /// Loops whose backedge taken counts directly use this non-constant SCEV.
1561 DenseMap<const SCEV *, SmallPtrSet<PointerIntPair<const Loop *, 1, bool>, 4>>
1562 BECountUsers;
1563
1564 /// This map contains entries for all of the PHI instructions that we
1565 /// attempt to compute constant evolutions for. This allows us to avoid
1566 /// potentially expensive recomputation of these properties. An instruction
1567 /// maps to null if we are unable to compute its exit value.
1568 DenseMap<PHINode *, Constant *> ConstantEvolutionLoopExitValue;
1569
1570 /// This map contains entries for all the expressions that we attempt to
1571 /// compute getSCEVAtScope information for, which can be expensive in
1572 /// extreme cases.
1573 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1574 ValuesAtScopes;
1575
1576 /// Reverse map for invalidation purposes: Stores of which SCEV and which
1577 /// loop this is the value-at-scope of.
1578 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1579 ValuesAtScopesUsers;
1580
1581 /// Memoized computeLoopDisposition results.
1582 DenseMap<const SCEV *,
1583 SmallVector<PointerIntPair<const Loop *, 2, LoopDisposition>, 2>>
1584 LoopDispositions;
1585
1586 struct LoopProperties {
1587 /// Set to true if the loop contains no instruction that can abnormally exit
1588 /// the loop (i.e. via throwing an exception, by terminating the thread
1589 /// cleanly or by infinite looping in a called function). Strictly
1590 /// speaking, the last one is not leaving the loop, but is identical to
1591 /// leaving the loop for reasoning about undefined behavior.
1592 bool HasNoAbnormalExits;
1593
1594 /// Set to true if the loop contains no instruction that can have side
1595 /// effects (i.e. via throwing an exception, volatile or atomic access).
1596 bool HasNoSideEffects;
1597 };
1598
1599 /// Cache for \c getLoopProperties.
1600 DenseMap<const Loop *, LoopProperties> LoopPropertiesCache;
1601
1602 /// Return a \c LoopProperties instance for \p L, creating one if necessary.
1603 LoopProperties getLoopProperties(const Loop *L);
1604
1605 bool loopHasNoSideEffects(const Loop *L) {
1606 return getLoopProperties(L).HasNoSideEffects;
1607 }
1608
1609 /// Compute a LoopDisposition value.
1610 LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L);
1611
1612 /// Memoized computeBlockDisposition results.
1613 DenseMap<
1614 const SCEV *,
1615 SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>>
1616 BlockDispositions;
1617
1618 /// Compute a BlockDisposition value.
1619 BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB);
1620
1621 /// Stores all SCEV that use a given SCEV as its direct operand.
1622 DenseMap<const SCEV *, SmallPtrSet<const SCEV *, 8> > SCEVUsers;
1623
1624 /// Memoized results from getRange
1625 DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
1626
1627 /// Memoized results from getRange
1628 DenseMap<const SCEV *, ConstantRange> SignedRanges;
1629
1630 /// Used to parameterize getRange
1631 enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED };
1632
1633 /// Set the memoized range for the given SCEV.
1634 const ConstantRange &setRange(const SCEV *S, RangeSignHint Hint,
1635 ConstantRange CR) {
1636 DenseMap<const SCEV *, ConstantRange> &Cache =
1637 Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges;
1638
1639 auto Pair = Cache.try_emplace(S, std::move(CR));
1640 if (!Pair.second)
1641 Pair.first->second = std::move(CR);
1642 return Pair.first->second;
1643 }
1644
1645 /// Determine the range for a particular SCEV.
1646 /// NOTE: This returns a reference to an entry in a cache. It must be
1647 /// copied if its needed for longer.
1648 const ConstantRange &getRangeRef(const SCEV *S, RangeSignHint Hint,
1649 unsigned Depth = 0);
1650
1651 /// Determine the range for a particular SCEV, but evaluates ranges for
1652 /// operands iteratively first.
1653 const ConstantRange &getRangeRefIter(const SCEV *S, RangeSignHint Hint);
1654
1655 /// Determines the range for the affine SCEVAddRecExpr {\p Start,+,\p Step}.
1656 /// Helper for \c getRange.
1657 ConstantRange getRangeForAffineAR(const SCEV *Start, const SCEV *Step,
1658 const SCEV *MaxBECount, unsigned BitWidth);
1659
1660 /// Determines the range for the affine non-self-wrapping SCEVAddRecExpr {\p
1661 /// Start,+,\p Step}<nw>.
1662 ConstantRange getRangeForAffineNoSelfWrappingAR(const SCEVAddRecExpr *AddRec,
1663 const SCEV *MaxBECount,
1664 unsigned BitWidth,
1665 RangeSignHint SignHint);
1666
1667 /// Try to compute a range for the affine SCEVAddRecExpr {\p Start,+,\p
1668 /// Step} by "factoring out" a ternary expression from the add recurrence.
1669 /// Helper called by \c getRange.
1670 ConstantRange getRangeViaFactoring(const SCEV *Start, const SCEV *Step,
1671 const SCEV *MaxBECount, unsigned BitWidth);
1672
1673 /// If the unknown expression U corresponds to a simple recurrence, return
1674 /// a constant range which represents the entire recurrence. Note that
1675 /// *add* recurrences with loop invariant steps aren't represented by
1676 /// SCEVUnknowns and thus don't use this mechanism.
1677 ConstantRange getRangeForUnknownRecurrence(const SCEVUnknown *U);
1678
1679 /// We know that there is no SCEV for the specified value. Analyze the
1680 /// expression recursively.
1681 const SCEV *createSCEV(Value *V);
1682
1683 /// We know that there is no SCEV for the specified value. Create a new SCEV
1684 /// for \p V iteratively.
1685 const SCEV *createSCEVIter(Value *V);
1686 /// Collect operands of \p V for which SCEV expressions should be constructed
1687 /// first. Returns a SCEV directly if it can be constructed trivially for \p
1688 /// V.
1689 const SCEV *getOperandsToCreate(Value *V, SmallVectorImpl<Value *> &Ops);
1690
1691 /// Provide the special handling we need to analyze PHI SCEVs.
1692 const SCEV *createNodeForPHI(PHINode *PN);
1693
1694 /// Helper function called from createNodeForPHI.
1695 const SCEV *createAddRecFromPHI(PHINode *PN);
1696
1697 /// A helper function for createAddRecFromPHI to handle simple cases.
1698 const SCEV *createSimpleAffineAddRec(PHINode *PN, Value *BEValueV,
1699 Value *StartValueV);
1700
1701 /// Helper function called from createNodeForPHI.
1702 const SCEV *createNodeFromSelectLikePHI(PHINode *PN);
1703
1704 /// Provide special handling for a select-like instruction (currently this
1705 /// is either a select instruction or a phi node). \p Ty is the type of the
1706 /// instruction being processed, that is assumed equivalent to
1707 /// "Cond ? TrueVal : FalseVal".
1708 std::optional<const SCEV *>
1709 createNodeForSelectOrPHIInstWithICmpInstCond(Type *Ty, ICmpInst *Cond,
1710 Value *TrueVal, Value *FalseVal);
1711
1712 /// See if we can model this select-like instruction via umin_seq expression.
1713 const SCEV *createNodeForSelectOrPHIViaUMinSeq(Value *I, Value *Cond,
1714 Value *TrueVal,
1715 Value *FalseVal);
1716
1717 /// Given a value \p V, which is a select-like instruction (currently this is
1718 /// either a select instruction or a phi node), which is assumed equivalent to
1719 /// Cond ? TrueVal : FalseVal
1720 /// see if we can model it as a SCEV expression.
1721 const SCEV *createNodeForSelectOrPHI(Value *V, Value *Cond, Value *TrueVal,
1722 Value *FalseVal);
1723
1724 /// Provide the special handling we need to analyze GEP SCEVs.
1725 const SCEV *createNodeForGEP(GEPOperator *GEP);
1726
1727 /// Implementation code for getSCEVAtScope; called at most once for each
1728 /// SCEV+Loop pair.
1729 const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L);
1730
1731 /// Return the BackedgeTakenInfo for the given loop, lazily computing new
1732 /// values if the loop hasn't been analyzed yet. The returned result is
1733 /// guaranteed not to be predicated.
1734 BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L);
1735
1736 /// Similar to getBackedgeTakenInfo, but will add predicates as required
1737 /// with the purpose of returning complete information.
1738 const BackedgeTakenInfo &getPredicatedBackedgeTakenInfo(const Loop *L);
1739
1740 /// Compute the number of times the specified loop will iterate.
1741 /// If AllowPredicates is set, we will create new SCEV predicates as
1742 /// necessary in order to return an exact answer.
1743 BackedgeTakenInfo computeBackedgeTakenCount(const Loop *L,
1744 bool AllowPredicates = false);
1745
1746 /// Compute the number of times the backedge of the specified loop will
1747 /// execute if it exits via the specified block. If AllowPredicates is set,
1748 /// this call will try to use a minimal set of SCEV predicates in order to
1749 /// return an exact answer.
1750 ExitLimit computeExitLimit(const Loop *L, BasicBlock *ExitingBlock,
1751 bool AllowPredicates = false);
1752
1753 /// Return a symbolic upper bound for the backedge taken count of the loop.
1754 /// This is more general than getConstantMaxBackedgeTakenCount as it returns
1755 /// an arbitrary expression as opposed to only constants.
1756 const SCEV *computeSymbolicMaxBackedgeTakenCount(const Loop *L);
1757
1758 // Helper functions for computeExitLimitFromCond to avoid exponential time
1759 // complexity.
1760
1761 class ExitLimitCache {
1762 // It may look like we need key on the whole (L, ExitIfTrue, ControlsExit,
1763 // AllowPredicates) tuple, but recursive calls to
1764 // computeExitLimitFromCondCached from computeExitLimitFromCondImpl only
1765 // vary the in \c ExitCond and \c ControlsExit parameters. We remember the
1766 // initial values of the other values to assert our assumption.
1767 SmallDenseMap<PointerIntPair<Value *, 1>, ExitLimit> TripCountMap;
1768
1769 const Loop *L;
1770 bool ExitIfTrue;
1771 bool AllowPredicates;
1772
1773 public:
1774 ExitLimitCache(const Loop *L, bool ExitIfTrue, bool AllowPredicates)
1775 : L(L), ExitIfTrue(ExitIfTrue), AllowPredicates(AllowPredicates) {}
1776
1777 std::optional<ExitLimit> find(const Loop *L, Value *ExitCond,
1778 bool ExitIfTrue, bool ControlsExit,
1779 bool AllowPredicates);
1780
1781 void insert(const Loop *L, Value *ExitCond, bool ExitIfTrue,
1782 bool ControlsExit, bool AllowPredicates, const ExitLimit &EL);
1783 };
1784
1785 using ExitLimitCacheTy = ExitLimitCache;
1786
1787 ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache,
1788 const Loop *L, Value *ExitCond,
1789 bool ExitIfTrue,
1790 bool ControlsExit,
1791 bool AllowPredicates);
1792 ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache, const Loop *L,
1793 Value *ExitCond, bool ExitIfTrue,
1794 bool ControlsExit,
1795 bool AllowPredicates);
1796 std::optional<ScalarEvolution::ExitLimit>
1797 computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache, const Loop *L,
1798 Value *ExitCond, bool ExitIfTrue,
1799 bool ControlsExit, bool AllowPredicates);
1800
1801 /// Compute the number of times the backedge of the specified loop will
1802 /// execute if its exit condition were a conditional branch of the ICmpInst
1803 /// ExitCond and ExitIfTrue. If AllowPredicates is set, this call will try
1804 /// to use a minimal set of SCEV predicates in order to return an exact
1805 /// answer.
1806 ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond,
1807 bool ExitIfTrue,
1808 bool IsSubExpr,
1809 bool AllowPredicates = false);
1810
1811 /// Variant of previous which takes the components representing an ICmp
1812 /// as opposed to the ICmpInst itself. Note that the prior version can
1813 /// return more precise results in some cases and is preferred when caller
1814 /// has a materialized ICmp.
1815 ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst::Predicate Pred,
1816 const SCEV *LHS, const SCEV *RHS,
1817 bool IsSubExpr,
1818 bool AllowPredicates = false);
1819
1820 /// Compute the number of times the backedge of the specified loop will
1821 /// execute if its exit condition were a switch with a single exiting case
1822 /// to ExitingBB.
1823 ExitLimit computeExitLimitFromSingleExitSwitch(const Loop *L,
1824 SwitchInst *Switch,
1825 BasicBlock *ExitingBB,
1826 bool IsSubExpr);
1827
1828 /// Compute the exit limit of a loop that is controlled by a
1829 /// "(IV >> 1) != 0" type comparison. We cannot compute the exact trip
1830 /// count in these cases (since SCEV has no way of expressing them), but we
1831 /// can still sometimes compute an upper bound.
1832 ///
1833 /// Return an ExitLimit for a loop whose backedge is guarded by `LHS Pred
1834 /// RHS`.
1835 ExitLimit computeShiftCompareExitLimit(Value *LHS, Value *RHS, const Loop *L,
1836 ICmpInst::Predicate Pred);
1837
1838 /// If the loop is known to execute a constant number of times (the
1839 /// condition evolves only from constants), try to evaluate a few iterations
1840 /// of the loop until we get the exit condition gets a value of ExitWhen
1841 /// (true or false). If we cannot evaluate the exit count of the loop,
1842 /// return CouldNotCompute.
1843 const SCEV *computeExitCountExhaustively(const Loop *L, Value *Cond,
1844 bool ExitWhen);
1845
1846 /// Return the number of times an exit condition comparing the specified
1847 /// value to zero will execute. If not computable, return CouldNotCompute.
1848 /// If AllowPredicates is set, this call will try to use a minimal set of
1849 /// SCEV predicates in order to return an exact answer.
1850 ExitLimit howFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr,
1851 bool AllowPredicates = false);
1852
1853 /// Return the number of times an exit condition checking the specified
1854 /// value for nonzero will execute. If not computable, return
1855 /// CouldNotCompute.
1856 ExitLimit howFarToNonZero(const SCEV *V, const Loop *L);
1857
1858 /// Return the number of times an exit condition containing the specified
1859 /// less-than comparison will execute. If not computable, return
1860 /// CouldNotCompute.
1861 ///
1862 /// \p isSigned specifies whether the less-than is signed.
1863 ///
1864 /// \p ControlsExit is true when the LHS < RHS condition directly controls
1865 /// the branch (loops exits only if condition is true). In this case, we can
1866 /// use NoWrapFlags to skip overflow checks.
1867 ///
1868 /// If \p AllowPredicates is set, this call will try to use a minimal set of
1869 /// SCEV predicates in order to return an exact answer.
1870 ExitLimit howManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
1871 bool isSigned, bool ControlsExit,
1872 bool AllowPredicates = false);
1873
1874 ExitLimit howManyGreaterThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
1875 bool isSigned, bool IsSubExpr,
1876 bool AllowPredicates = false);
1877
1878 /// Return a predecessor of BB (which may not be an immediate predecessor)
1879 /// which has exactly one successor from which BB is reachable, or null if
1880 /// no such block is found.
1881 std::pair<const BasicBlock *, const BasicBlock *>
1882 getPredecessorWithUniqueSuccessorForBB(const BasicBlock *BB) const;
1883
1884 /// Test whether the condition described by Pred, LHS, and RHS is true
1885 /// whenever the given FoundCondValue value evaluates to true in given
1886 /// Context. If Context is nullptr, then the found predicate is true
1887 /// everywhere. LHS and FoundLHS may have different type width.
1888 bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
1889 const Value *FoundCondValue, bool Inverse,
1890 const Instruction *Context = nullptr);
1891
1892 /// Test whether the condition described by Pred, LHS, and RHS is true
1893 /// whenever the given FoundCondValue value evaluates to true in given
1894 /// Context. If Context is nullptr, then the found predicate is true
1895 /// everywhere. LHS and FoundLHS must have same type width.
1896 bool isImpliedCondBalancedTypes(ICmpInst::Predicate Pred, const SCEV *LHS,
1897 const SCEV *RHS,
1898 ICmpInst::Predicate FoundPred,
1899 const SCEV *FoundLHS, const SCEV *FoundRHS,
1900 const Instruction *CtxI);
1901
1902 /// Test whether the condition described by Pred, LHS, and RHS is true
1903 /// whenever the condition described by FoundPred, FoundLHS, FoundRHS is
1904 /// true in given Context. If Context is nullptr, then the found predicate is
1905 /// true everywhere.
1906 bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
1907 ICmpInst::Predicate FoundPred, const SCEV *FoundLHS,
1908 const SCEV *FoundRHS,
1909 const Instruction *Context = nullptr);
1910
1911 /// Test whether the condition described by Pred, LHS, and RHS is true
1912 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1913 /// true in given Context. If Context is nullptr, then the found predicate is
1914 /// true everywhere.
1915 bool isImpliedCondOperands(ICmpInst::Predicate Pred, const SCEV *LHS,
1916 const SCEV *RHS, const SCEV *FoundLHS,
1917 const SCEV *FoundRHS,
1918 const Instruction *Context = nullptr);
1919
1920 /// Test whether the condition described by Pred, LHS, and RHS is true
1921 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1922 /// true. Here LHS is an operation that includes FoundLHS as one of its
1923 /// arguments.
1924 bool isImpliedViaOperations(ICmpInst::Predicate Pred,
1925 const SCEV *LHS, const SCEV *RHS,
1926 const SCEV *FoundLHS, const SCEV *FoundRHS,
1927 unsigned Depth = 0);
1928
1929 /// Test whether the condition described by Pred, LHS, and RHS is true.
1930 /// Use only simple non-recursive types of checks, such as range analysis etc.
1931 bool isKnownViaNonRecursiveReasoning(ICmpInst::Predicate Pred,
1932 const SCEV *LHS, const SCEV *RHS);
1933
1934 /// Test whether the condition described by Pred, LHS, and RHS is true
1935 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1936 /// true.
1937 bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, const SCEV *LHS,
1938 const SCEV *RHS, const SCEV *FoundLHS,
1939 const SCEV *FoundRHS);
1940
1941 /// Test whether the condition described by Pred, LHS, and RHS is true
1942 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1943 /// true. Utility function used by isImpliedCondOperands. Tries to get
1944 /// cases like "X `sgt` 0 => X - 1 `sgt` -1".
1945 bool isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred, const SCEV *LHS,
1946 const SCEV *RHS, const SCEV *FoundLHS,
1947 const SCEV *FoundRHS);
1948
1949 /// Return true if the condition denoted by \p LHS \p Pred \p RHS is implied
1950 /// by a call to @llvm.experimental.guard in \p BB.
1951 bool isImpliedViaGuard(const BasicBlock *BB, ICmpInst::Predicate Pred,
1952 const SCEV *LHS, const SCEV *RHS);
1953
1954 /// Test whether the condition described by Pred, LHS, and RHS is true
1955 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1956 /// true.
1957 ///
1958 /// This routine tries to rule out certain kinds of integer overflow, and
1959 /// then tries to reason about arithmetic properties of the predicates.
1960 bool isImpliedCondOperandsViaNoOverflow(ICmpInst::Predicate Pred,
1961 const SCEV *LHS, const SCEV *RHS,
1962 const SCEV *FoundLHS,
1963 const SCEV *FoundRHS);
1964
1965 /// Test whether the condition described by Pred, LHS, and RHS is true
1966 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1967 /// true.
1968 ///
1969 /// This routine tries to weaken the known condition basing on fact that
1970 /// FoundLHS is an AddRec.
1971 bool isImpliedCondOperandsViaAddRecStart(ICmpInst::Predicate Pred,
1972 const SCEV *LHS, const SCEV *RHS,
1973 const SCEV *FoundLHS,
1974 const SCEV *FoundRHS,
1975 const Instruction *CtxI);
1976
1977 /// Test whether the condition described by Pred, LHS, and RHS is true
1978 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1979 /// true.
1980 ///
1981 /// This routine tries to figure out predicate for Phis which are SCEVUnknown
1982 /// if it is true for every possible incoming value from their respective
1983 /// basic blocks.
1984 bool isImpliedViaMerge(ICmpInst::Predicate Pred,
1985 const SCEV *LHS, const SCEV *RHS,
1986 const SCEV *FoundLHS, const SCEV *FoundRHS,
1987 unsigned Depth);
1988
1989 /// Test whether the condition described by Pred, LHS, and RHS is true
1990 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1991 /// true.
1992 ///
1993 /// This routine tries to reason about shifts.
1994 bool isImpliedCondOperandsViaShift(ICmpInst::Predicate Pred, const SCEV *LHS,
1995 const SCEV *RHS, const SCEV *FoundLHS,
1996 const SCEV *FoundRHS);
1997
1998 /// If we know that the specified Phi is in the header of its containing
1999 /// loop, we know the loop executes a constant number of times, and the PHI
2000 /// node is just a recurrence involving constants, fold it.
2001 Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt &BEs,
2002 const Loop *L);
2003
2004 /// Test if the given expression is known to satisfy the condition described
2005 /// by Pred and the known constant ranges of LHS and RHS.
2006 bool isKnownPredicateViaConstantRanges(ICmpInst::Predicate Pred,
2007 const SCEV *LHS, const SCEV *RHS);
2008
2009 /// Try to prove the condition described by "LHS Pred RHS" by ruling out
2010 /// integer overflow.
2011 ///
2012 /// For instance, this will return true for "A s< (A + C)<nsw>" if C is
2013 /// positive.
2014 bool isKnownPredicateViaNoOverflow(ICmpInst::Predicate Pred, const SCEV *LHS,
2015 const SCEV *RHS);
2016
2017 /// Try to split Pred LHS RHS into logical conjunctions (and's) and try to
2018 /// prove them individually.
2019 bool isKnownPredicateViaSplitting(ICmpInst::Predicate Pred, const SCEV *LHS,
2020 const SCEV *RHS);
2021
2022 /// Try to match the Expr as "(L + R)<Flags>".
2023 bool splitBinaryAdd(const SCEV *Expr, const SCEV *&L, const SCEV *&R,
2024 SCEV::NoWrapFlags &Flags);
2025
2026 /// Forget predicated/non-predicated backedge taken counts for the given loop.
2027 void forgetBackedgeTakenCounts(const Loop *L, bool Predicated);
2028
2029 /// Drop memoized information for all \p SCEVs.
2030 void forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs);
2031
2032 /// Helper for forgetMemoizedResults.
2033 void forgetMemoizedResultsImpl(const SCEV *S);
2034
2035 /// Return an existing SCEV for V if there is one, otherwise return nullptr.
2036 const SCEV *getExistingSCEV(Value *V);
2037
2038 /// Erase Value from ValueExprMap and ExprValueMap.
2039 void eraseValueFromMap(Value *V);
2040
2041 /// Insert V to S mapping into ValueExprMap and ExprValueMap.
2042 void insertValueToMap(Value *V, const SCEV *S);
2043
2044 /// Return false iff given SCEV contains a SCEVUnknown with NULL value-
2045 /// pointer.
2046 bool checkValidity(const SCEV *S) const;
2047
2048 /// Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be
2049 /// equal to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}. This is
2050 /// equivalent to proving no signed (resp. unsigned) wrap in
2051 /// {`Start`,+,`Step`} if `ExtendOpTy` is `SCEVSignExtendExpr`
2052 /// (resp. `SCEVZeroExtendExpr`).
2053 template <typename ExtendOpTy>
2054 bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step,
2055 const Loop *L);
2056
2057 /// Try to prove NSW or NUW on \p AR relying on ConstantRange manipulation.
2058 SCEV::NoWrapFlags proveNoWrapViaConstantRanges(const SCEVAddRecExpr *AR);
2059
2060 /// Try to prove NSW on \p AR by proving facts about conditions known on
2061 /// entry and backedge.
2062 SCEV::NoWrapFlags proveNoSignedWrapViaInduction(const SCEVAddRecExpr *AR);
2063
2064 /// Try to prove NUW on \p AR by proving facts about conditions known on
2065 /// entry and backedge.
2066 SCEV::NoWrapFlags proveNoUnsignedWrapViaInduction(const SCEVAddRecExpr *AR);
2067
2068 std::optional<MonotonicPredicateType>
2069 getMonotonicPredicateTypeImpl(const SCEVAddRecExpr *LHS,
2070 ICmpInst::Predicate Pred);
2071
2072 /// Return SCEV no-wrap flags that can be proven based on reasoning about
2073 /// how poison produced from no-wrap flags on this value (e.g. a nuw add)
2074 /// would trigger undefined behavior on overflow.
2075 SCEV::NoWrapFlags getNoWrapFlagsFromUB(const Value *V);
2076
2077 /// Return a scope which provides an upper bound on the defining scope of
2078 /// 'S'. Specifically, return the first instruction in said bounding scope.
2079 /// Return nullptr if the scope is trivial (function entry).
2080 /// (See scope definition rules associated with flag discussion above)
2081 const Instruction *getNonTrivialDefiningScopeBound(const SCEV *S);
2082
2083 /// Return a scope which provides an upper bound on the defining scope for
2084 /// a SCEV with the operands in Ops. The outparam Precise is set if the
2085 /// bound found is a precise bound (i.e. must be the defining scope.)
2086 const Instruction *getDefiningScopeBound(ArrayRef<const SCEV *> Ops,
2087 bool &Precise);
2088
2089 /// Wrapper around the above for cases which don't care if the bound
2090 /// is precise.
2091 const Instruction *getDefiningScopeBound(ArrayRef<const SCEV *> Ops);
2092
2093 /// Given two instructions in the same function, return true if we can
2094 /// prove B must execute given A executes.
2095 bool isGuaranteedToTransferExecutionTo(const Instruction *A,
2096 const Instruction *B);
2097
2098 /// Return true if the SCEV corresponding to \p I is never poison. Proving
2099 /// this is more complex than proving that just \p I is never poison, since
2100 /// SCEV commons expressions across control flow, and you can have cases
2101 /// like:
2102 ///
2103 /// idx0 = a + b;
2104 /// ptr[idx0] = 100;
2105 /// if (<condition>) {
2106 /// idx1 = a +nsw b;
2107 /// ptr[idx1] = 200;
2108 /// }
2109 ///
2110 /// where the SCEV expression (+ a b) is guaranteed to not be poison (and
2111 /// hence not sign-overflow) only if "<condition>" is true. Since both
2112 /// `idx0` and `idx1` will be mapped to the same SCEV expression, (+ a b),
2113 /// it is not okay to annotate (+ a b) with <nsw> in the above example.
2114 bool isSCEVExprNeverPoison(const Instruction *I);
2115
2116 /// This is like \c isSCEVExprNeverPoison but it specifically works for
2117 /// instructions that will get mapped to SCEV add recurrences. Return true
2118 /// if \p I will never generate poison under the assumption that \p I is an
2119 /// add recurrence on the loop \p L.
2120 bool isAddRecNeverPoison(const Instruction *I, const Loop *L);
2121
2122 /// Similar to createAddRecFromPHI, but with the additional flexibility of
2123 /// suggesting runtime overflow checks in case casts are encountered.
2124 /// If successful, the analysis records that for this loop, \p SymbolicPHI,
2125 /// which is the UnknownSCEV currently representing the PHI, can be rewritten
2126 /// into an AddRec, assuming some predicates; The function then returns the
2127 /// AddRec and the predicates as a pair, and caches this pair in
2128 /// PredicatedSCEVRewrites.
2129 /// If the analysis is not successful, a mapping from the \p SymbolicPHI to
2130 /// itself (with no predicates) is recorded, and a nullptr with an empty
2131 /// predicates vector is returned as a pair.
2132 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2133 createAddRecFromPHIWithCastsImpl(const SCEVUnknown *SymbolicPHI);
2134
2135 /// Compute the maximum backedge count based on the range of values
2136 /// permitted by Start, End, and Stride. This is for loops of the form
2137 /// {Start, +, Stride} LT End.
2138 ///
2139 /// Preconditions:
2140 /// * the induction variable is known to be positive.
2141 /// * the induction variable is assumed not to overflow (i.e. either it
2142 /// actually doesn't, or we'd have to immediately execute UB)
2143 /// We *don't* assert these preconditions so please be careful.
2144 const SCEV *computeMaxBECountForLT(const SCEV *Start, const SCEV *Stride,
2145 const SCEV *End, unsigned BitWidth,
2146 bool IsSigned);
2147
2148 /// Verify if an linear IV with positive stride can overflow when in a
2149 /// less-than comparison, knowing the invariant term of the comparison,
2150 /// the stride.
2151 bool canIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, bool IsSigned);
2152
2153 /// Verify if an linear IV with negative stride can overflow when in a
2154 /// greater-than comparison, knowing the invariant term of the comparison,
2155 /// the stride.
2156 bool canIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, bool IsSigned);
2157
2158 /// Get add expr already created or create a new one.
2159 const SCEV *getOrCreateAddExpr(ArrayRef<const SCEV *> Ops,
2160 SCEV::NoWrapFlags Flags);
2161
2162 /// Get mul expr already created or create a new one.
2163 const SCEV *getOrCreateMulExpr(ArrayRef<const SCEV *> Ops,
2164 SCEV::NoWrapFlags Flags);
2165
2166 // Get addrec expr already created or create a new one.
2167 const SCEV *getOrCreateAddRecExpr(ArrayRef<const SCEV *> Ops,
2168 const Loop *L, SCEV::NoWrapFlags Flags);
2169
2170 /// Return x if \p Val is f(x) where f is a 1-1 function.
2171 const SCEV *stripInjectiveFunctions(const SCEV *Val) const;
2172
2173 /// Find all of the loops transitively used in \p S, and fill \p LoopsUsed.
2174 /// A loop is considered "used" by an expression if it contains
2175 /// an add rec on said loop.
2176 void getUsedLoops(const SCEV *S, SmallPtrSetImpl<const Loop *> &LoopsUsed);
2177
2178 /// Try to match the pattern generated by getURemExpr(A, B). If successful,
2179 /// Assign A and B to LHS and RHS, respectively.
2180 bool matchURem(const SCEV *Expr, const SCEV *&LHS, const SCEV *&RHS);
2181
2182 /// Look for a SCEV expression with type `SCEVType` and operands `Ops` in
2183 /// `UniqueSCEVs`. Return if found, else nullptr.
2184 SCEV *findExistingSCEVInCache(SCEVTypes SCEVType, ArrayRef<const SCEV *> Ops);
2185
2186 /// Get reachable blocks in this function, making limited use of SCEV
2187 /// reasoning about conditions.
2188 void getReachableBlocks(SmallPtrSetImpl<BasicBlock *> &Reachable,
2189 Function &F);
2190
2191 FoldingSet<SCEV> UniqueSCEVs;
2192 FoldingSet<SCEVPredicate> UniquePreds;
2193 BumpPtrAllocator SCEVAllocator;
2194
2195 /// This maps loops to a list of addrecs that directly use said loop.
2196 DenseMap<const Loop *, SmallVector<const SCEVAddRecExpr *, 4>> LoopUsers;
2197
2198 /// Cache tentative mappings from UnknownSCEVs in a Loop, to a SCEV expression
2199 /// they can be rewritten into under certain predicates.
2200 DenseMap<std::pair<const SCEVUnknown *, const Loop *>,
2201 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2202 PredicatedSCEVRewrites;
2203
2204 /// Set of AddRecs for which proving NUW via an induction has already been
2205 /// tried.
2206 SmallPtrSet<const SCEVAddRecExpr *, 16> UnsignedWrapViaInductionTried;
2207
2208 /// Set of AddRecs for which proving NSW via an induction has already been
2209 /// tried.
2210 SmallPtrSet<const SCEVAddRecExpr *, 16> SignedWrapViaInductionTried;
2211
2212 /// The head of a linked list of all SCEVUnknown values that have been
2213 /// allocated. This is used by releaseMemory to locate them all and call
2214 /// their destructors.
2215 SCEVUnknown *FirstUnknown = nullptr;
2216};
2217
2218/// Analysis pass that exposes the \c ScalarEvolution for a function.
2220 : public AnalysisInfoMixin<ScalarEvolutionAnalysis> {
2222
2223 static AnalysisKey Key;
2224
2225public:
2227
2229};
2230
2231/// Verifier pass for the \c ScalarEvolutionAnalysis results.
2233 : public PassInfoMixin<ScalarEvolutionVerifierPass> {
2234public:
2236};
2237
2238/// Printer pass for the \c ScalarEvolutionAnalysis results.
2240 : public PassInfoMixin<ScalarEvolutionPrinterPass> {
2241 raw_ostream &OS;
2242
2243public:
2244 explicit ScalarEvolutionPrinterPass(raw_ostream &OS) : OS(OS) {}
2245
2247};
2248
2250 std::unique_ptr<ScalarEvolution> SE;
2251
2252public:
2253 static char ID;
2254
2256
2257 ScalarEvolution &getSE() { return *SE; }
2258 const ScalarEvolution &getSE() const { return *SE; }
2259
2260 bool runOnFunction(Function &F) override;
2261 void releaseMemory() override;
2262 void getAnalysisUsage(AnalysisUsage &AU) const override;
2263 void print(raw_ostream &OS, const Module * = nullptr) const override;
2264 void verifyAnalysis() const override;
2265};
2266
2267/// An interface layer with SCEV used to manage how we see SCEV expressions
2268/// for values in the context of existing predicates. We can add new
2269/// predicates, but we cannot remove them.
2270///
2271/// This layer has multiple purposes:
2272/// - provides a simple interface for SCEV versioning.
2273/// - guarantees that the order of transformations applied on a SCEV
2274/// expression for a single Value is consistent across two different
2275/// getSCEV calls. This means that, for example, once we've obtained
2276/// an AddRec expression for a certain value through expression
2277/// rewriting, we will continue to get an AddRec expression for that
2278/// Value.
2279/// - lowers the number of expression rewrites.
2281public:
2283
2284 const SCEVPredicate &getPredicate() const;
2285
2286 /// Returns the SCEV expression of V, in the context of the current SCEV
2287 /// predicate. The order of transformations applied on the expression of V
2288 /// returned by ScalarEvolution is guaranteed to be preserved, even when
2289 /// adding new predicates.
2290 const SCEV *getSCEV(Value *V);
2291
2292 /// Get the (predicated) backedge count for the analyzed loop.
2293 const SCEV *getBackedgeTakenCount();
2294
2295 /// Adds a new predicate.
2296 void addPredicate(const SCEVPredicate &Pred);
2297
2298 /// Attempts to produce an AddRecExpr for V by adding additional SCEV
2299 /// predicates. If we can't transform the expression into an AddRecExpr we
2300 /// return nullptr and not add additional SCEV predicates to the current
2301 /// context.
2302 const SCEVAddRecExpr *getAsAddRec(Value *V);
2303
2304 /// Proves that V doesn't overflow by adding SCEV predicate.
2306
2307 /// Returns true if we've proved that V doesn't wrap by means of a SCEV
2308 /// predicate.
2310
2311 /// Returns the ScalarEvolution analysis used.
2312 ScalarEvolution *getSE() const { return &SE; }
2313
2314 /// We need to explicitly define the copy constructor because of FlagsMap.
2316
2317 /// Print the SCEV mappings done by the Predicated Scalar Evolution.
2318 /// The printed text is indented by \p Depth.
2319 void print(raw_ostream &OS, unsigned Depth) const;
2320
2321 /// Check if \p AR1 and \p AR2 are equal, while taking into account
2322 /// Equal predicates in Preds.
2324 const SCEVAddRecExpr *AR2) const;
2325
2326private:
2327 /// Increments the version number of the predicate. This needs to be called
2328 /// every time the SCEV predicate changes.
2329 void updateGeneration();
2330
2331 /// Holds a SCEV and the version number of the SCEV predicate used to
2332 /// perform the rewrite of the expression.
2333 using RewriteEntry = std::pair<unsigned, const SCEV *>;
2334
2335 /// Maps a SCEV to the rewrite result of that SCEV at a certain version
2336 /// number. If this number doesn't match the current Generation, we will
2337 /// need to do a rewrite. To preserve the transformation order of previous
2338 /// rewrites, we will rewrite the previous result instead of the original
2339 /// SCEV.
2341
2342 /// Records what NoWrap flags we've added to a Value *.
2344
2345 /// The ScalarEvolution analysis.
2346 ScalarEvolution &SE;
2347
2348 /// The analyzed Loop.
2349 const Loop &L;
2350
2351 /// The SCEVPredicate that forms our context. We will rewrite all
2352 /// expressions assuming that this predicate true.
2353 std::unique_ptr<SCEVUnionPredicate> Preds;
2354
2355 /// Marks the version of the SCEV predicate used. When rewriting a SCEV
2356 /// expression we mark it with the version of the predicate. We use this to
2357 /// figure out if the predicate has changed from the last rewrite of the
2358 /// SCEV. If so, we need to perform a new rewrite.
2359 unsigned Generation = 0;
2360
2361 /// The backedge taken count.
2362 const SCEV *BackedgeCount = nullptr;
2363};
2364
2365template <> struct DenseMapInfo<ScalarEvolution::FoldID> {
2368 ID.addInteger(~0ULL);
2369 return ID;
2370 }
2373 ID.addInteger(~0ULL - 1ULL);
2374 return ID;
2375 }
2376
2377 static unsigned getHashValue(const ScalarEvolution::FoldID &Val) {
2378 return Val.computeHash();
2379 }
2380
2383 return LHS == RHS;
2384 }
2385};
2386
2387} // end namespace llvm
2388
2389#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:390
This file defines DenseMapInfo traits for DenseMap.
This file defines the DenseMap class.
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())
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition: APInt.h:75
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:718
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:114
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:308
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:547
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.
Class to represent scalable SIMD vectors.
Definition: DerivedTypes.h:572
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 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)?...
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 * 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.
const SCEV * getSizeOfExpr(Type *IntTy, Type *AllocTy)
Return an expression for the alloc size of AllocTy that is type IntTy.
const SCEV * getTripCountFromExitCount(const SCEV *ExitCount, bool Extend=true)
Convert from an "exit count" (i.e.
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.
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.
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.
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 * 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.
ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, bool ExitIfTrue, bool ControlsExit, bool AllowPredicates=false)
Compute the number of times the backedge of the specified loop will execute if its exit condition wer...
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.
bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS, const SCEV *&RHS, unsigned Depth=0, bool ControllingFiniteLoop=false)
Simplify LHS and RHS in a comparison with predicate Pred.
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 * 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 * getSizeOfScalableVectorExpr(Type *IntTy, ScalableVectorType *ScalableTy)
Return an expression for sizeof ScalableTy that is type IntTy, where ScalableTy is a scalable vector ...
const SCEV * getUDivExactExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
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 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:301
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
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:1755
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:147
#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)