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