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 /// Forget LCSSA phi node V of loop L to which a new predecessor was added,
947 /// such that it may no longer be trivial.
949
950 /// Called when the client has changed the disposition of values in
951 /// this loop.
952 ///
953 /// We don't have a way to invalidate per-loop dispositions. Clear and
954 /// recompute is simpler.
956
957 /// Called when the client has changed the disposition of values in
958 /// a loop or block.
959 ///
960 /// We don't have a way to invalidate per-loop/per-block dispositions. Clear
961 /// and recompute is simpler.
962 void forgetBlockAndLoopDispositions(Value *V = nullptr);
963
964 /// Determine the minimum number of zero bits that S is guaranteed to end in
965 /// (at every loop iteration). It is, at the same time, the minimum number
966 /// of times S is divisible by 2. For example, given {4,+,8} it returns 2.
967 /// If S is guaranteed to be 0, it returns the bitwidth of S.
969
970 /// Returns the max constant multiple of S.
972
973 // Returns the max constant multiple of S. If S is exactly 0, return 1.
975
976 /// Determine the unsigned range for a particular SCEV.
977 /// NOTE: This returns a copy of the reference returned by getRangeRef.
979 return getRangeRef(S, HINT_RANGE_UNSIGNED);
980 }
981
982 /// Determine the min of the unsigned range for a particular SCEV.
984 return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMin();
985 }
986
987 /// Determine the max of the unsigned range for a particular SCEV.
989 return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMax();
990 }
991
992 /// Determine the signed range for a particular SCEV.
993 /// NOTE: This returns a copy of the reference returned by getRangeRef.
995 return getRangeRef(S, HINT_RANGE_SIGNED);
996 }
997
998 /// Determine the min of the signed range for a particular SCEV.
1000 return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMin();
1001 }
1002
1003 /// Determine the max of the signed range for a particular SCEV.
1005 return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMax();
1006 }
1007
1008 /// Test if the given expression is known to be negative.
1009 bool isKnownNegative(const SCEV *S);
1010
1011 /// Test if the given expression is known to be positive.
1012 bool isKnownPositive(const SCEV *S);
1013
1014 /// Test if the given expression is known to be non-negative.
1015 bool isKnownNonNegative(const SCEV *S);
1016
1017 /// Test if the given expression is known to be non-positive.
1018 bool isKnownNonPositive(const SCEV *S);
1019
1020 /// Test if the given expression is known to be non-zero.
1021 bool isKnownNonZero(const SCEV *S);
1022
1023 /// Splits SCEV expression \p S into two SCEVs. One of them is obtained from
1024 /// \p S by substitution of all AddRec sub-expression related to loop \p L
1025 /// with initial value of that SCEV. The second is obtained from \p S by
1026 /// substitution of all AddRec sub-expressions related to loop \p L with post
1027 /// increment of this AddRec in the loop \p L. In both cases all other AddRec
1028 /// sub-expressions (not related to \p L) remain the same.
1029 /// If the \p S contains non-invariant unknown SCEV the function returns
1030 /// CouldNotCompute SCEV in both values of std::pair.
1031 /// For example, for SCEV S={0, +, 1}<L1> + {0, +, 1}<L2> and loop L=L1
1032 /// the function returns pair:
1033 /// first = {0, +, 1}<L2>
1034 /// second = {1, +, 1}<L1> + {0, +, 1}<L2>
1035 /// We can see that for the first AddRec sub-expression it was replaced with
1036 /// 0 (initial value) for the first element and to {1, +, 1}<L1> (post
1037 /// increment value) for the second one. In both cases AddRec expression
1038 /// related to L2 remains the same.
1039 std::pair<const SCEV *, const SCEV *> SplitIntoInitAndPostInc(const Loop *L,
1040 const SCEV *S);
1041
1042 /// We'd like to check the predicate on every iteration of the most dominated
1043 /// loop between loops used in LHS and RHS.
1044 /// To do this we use the following list of steps:
1045 /// 1. Collect set S all loops on which either LHS or RHS depend.
1046 /// 2. If S is non-empty
1047 /// a. Let PD be the element of S which is dominated by all other elements.
1048 /// b. Let E(LHS) be value of LHS on entry of PD.
1049 /// To get E(LHS), we should just take LHS and replace all AddRecs that are
1050 /// attached to PD on with their entry values.
1051 /// Define E(RHS) in the same way.
1052 /// c. Let B(LHS) be value of L on backedge of PD.
1053 /// To get B(LHS), we should just take LHS and replace all AddRecs that are
1054 /// attached to PD on with their backedge values.
1055 /// Define B(RHS) in the same way.
1056 /// d. Note that E(LHS) and E(RHS) are automatically available on entry of PD,
1057 /// so we can assert on that.
1058 /// e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) &&
1059 /// isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS))
1061 const SCEV *RHS);
1062
1063 /// Test if the given expression is known to satisfy the condition described
1064 /// by Pred, LHS, and RHS.
1065 bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS,
1066 const SCEV *RHS);
1067
1068 /// Check whether the condition described by Pred, LHS, and RHS is true or
1069 /// false. If we know it, return the evaluation of this condition. If neither
1070 /// is proved, return std::nullopt.
1071 std::optional<bool> evaluatePredicate(ICmpInst::Predicate Pred,
1072 const SCEV *LHS, const SCEV *RHS);
1073
1074 /// Test if the given expression is known to satisfy the condition described
1075 /// by Pred, LHS, and RHS in the given Context.
1077 const SCEV *RHS, const Instruction *CtxI);
1078
1079 /// Check whether the condition described by Pred, LHS, and RHS is true or
1080 /// false in the given \p Context. If we know it, return the evaluation of
1081 /// this condition. If neither is proved, return std::nullopt.
1082 std::optional<bool> evaluatePredicateAt(ICmpInst::Predicate Pred,
1083 const SCEV *LHS, const SCEV *RHS,
1084 const Instruction *CtxI);
1085
1086 /// Test if the condition described by Pred, LHS, RHS is known to be true on
1087 /// every iteration of the loop of the recurrency LHS.
1089 const SCEVAddRecExpr *LHS, const SCEV *RHS);
1090
1091 /// Information about the number of loop iterations for which a loop exit's
1092 /// branch condition evaluates to the not-taken path. This is a temporary
1093 /// pair of exact and max expressions that are eventually summarized in
1094 /// ExitNotTakenInfo and BackedgeTakenInfo.
1095 struct ExitLimit {
1096 const SCEV *ExactNotTaken; // The exit is not taken exactly this many times
1097 const SCEV *ConstantMaxNotTaken; // The exit is not taken at most this many
1098 // times
1100
1101 // Not taken either exactly ConstantMaxNotTaken or zero times
1102 bool MaxOrZero = false;
1103
1104 /// A set of predicate guards for this ExitLimit. The result is only valid
1105 /// if all of the predicates in \c Predicates evaluate to 'true' at
1106 /// run-time.
1108
1110 assert(!isa<SCEVUnionPredicate>(P) && "Only add leaf predicates here!");
1111 Predicates.insert(P);
1112 }
1113
1114 /// Construct either an exact exit limit from a constant, or an unknown
1115 /// one from a SCEVCouldNotCompute. No other types of SCEVs are allowed
1116 /// as arguments and asserts enforce that internally.
1117 /*implicit*/ ExitLimit(const SCEV *E);
1118
1119 ExitLimit(
1120 const SCEV *E, const SCEV *ConstantMaxNotTaken,
1121 const SCEV *SymbolicMaxNotTaken, bool MaxOrZero,
1123 std::nullopt);
1124
1125 ExitLimit(const SCEV *E, const SCEV *ConstantMaxNotTaken,
1126 const SCEV *SymbolicMaxNotTaken, bool MaxOrZero,
1128
1129 /// Test whether this ExitLimit contains any computed information, or
1130 /// whether it's all SCEVCouldNotCompute values.
1131 bool hasAnyInfo() const {
1132 return !isa<SCEVCouldNotCompute>(ExactNotTaken) ||
1133 !isa<SCEVCouldNotCompute>(ConstantMaxNotTaken);
1134 }
1135
1136 /// Test whether this ExitLimit contains all information.
1137 bool hasFullInfo() const {
1138 return !isa<SCEVCouldNotCompute>(ExactNotTaken);
1139 }
1140 };
1141
1142 /// Compute the number of times the backedge of the specified loop will
1143 /// execute if its exit condition were a conditional branch of ExitCond.
1144 ///
1145 /// \p ControlsOnlyExit is true if ExitCond directly controls the only exit
1146 /// branch. In this case, we can assume that the loop exits only if the
1147 /// condition is true and can infer that failing to meet the condition prior
1148 /// to integer wraparound results in undefined behavior.
1149 ///
1150 /// If \p AllowPredicates is set, this call will try to use a minimal set of
1151 /// SCEV predicates in order to return an exact answer.
1152 ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond,
1153 bool ExitIfTrue, bool ControlsOnlyExit,
1154 bool AllowPredicates = false);
1155
1156 /// A predicate is said to be monotonically increasing if may go from being
1157 /// false to being true as the loop iterates, but never the other way
1158 /// around. A predicate is said to be monotonically decreasing if may go
1159 /// from being true to being false as the loop iterates, but never the other
1160 /// way around.
1165
1166 /// If, for all loop invariant X, the predicate "LHS `Pred` X" is
1167 /// monotonically increasing or decreasing, returns
1168 /// Some(MonotonicallyIncreasing) and Some(MonotonicallyDecreasing)
1169 /// respectively. If we could not prove either of these facts, returns
1170 /// std::nullopt.
1171 std::optional<MonotonicPredicateType>
1173 ICmpInst::Predicate Pred);
1174
1177 const SCEV *LHS;
1178 const SCEV *RHS;
1179
1181 const SCEV *RHS)
1182 : Pred(Pred), LHS(LHS), RHS(RHS) {}
1183 };
1184 /// If the result of the predicate LHS `Pred` RHS is loop invariant with
1185 /// respect to L, return a LoopInvariantPredicate with LHS and RHS being
1186 /// invariants, available at L's entry. Otherwise, return std::nullopt.
1187 std::optional<LoopInvariantPredicate>
1189 const SCEV *RHS, const Loop *L,
1190 const Instruction *CtxI = nullptr);
1191
1192 /// If the result of the predicate LHS `Pred` RHS is loop invariant with
1193 /// respect to L at given Context during at least first MaxIter iterations,
1194 /// return a LoopInvariantPredicate with LHS and RHS being invariants,
1195 /// available at L's entry. Otherwise, return std::nullopt. The predicate
1196 /// should be the loop's exit condition.
1197 std::optional<LoopInvariantPredicate>
1199 const SCEV *LHS,
1200 const SCEV *RHS, const Loop *L,
1201 const Instruction *CtxI,
1202 const SCEV *MaxIter);
1203
1204 std::optional<LoopInvariantPredicate>
1206 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L,
1207 const Instruction *CtxI, const SCEV *MaxIter);
1208
1209 /// Simplify LHS and RHS in a comparison with predicate Pred. Return true
1210 /// iff any changes were made. If the operands are provably equal or
1211 /// unequal, LHS and RHS are set to the same value and Pred is set to either
1212 /// ICMP_EQ or ICMP_NE.
1214 const SCEV *&RHS, unsigned Depth = 0);
1215
1216 /// Return the "disposition" of the given SCEV with respect to the given
1217 /// loop.
1218 LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L);
1219
1220 /// Return true if the value of the given SCEV is unchanging in the
1221 /// specified loop.
1222 bool isLoopInvariant(const SCEV *S, const Loop *L);
1223
1224 /// Determine if the SCEV can be evaluated at loop's entry. It is true if it
1225 /// doesn't depend on a SCEVUnknown of an instruction which is dominated by
1226 /// the header of loop L.
1227 bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L);
1228
1229 /// Return true if the given SCEV changes value in a known way in the
1230 /// specified loop. This property being true implies that the value is
1231 /// variant in the loop AND that we can emit an expression to compute the
1232 /// value of the expression at any particular loop iteration.
1233 bool hasComputableLoopEvolution(const SCEV *S, const Loop *L);
1234
1235 /// Return the "disposition" of the given SCEV with respect to the given
1236 /// block.
1238
1239 /// Return true if elements that makes up the given SCEV dominate the
1240 /// specified basic block.
1241 bool dominates(const SCEV *S, const BasicBlock *BB);
1242
1243 /// Return true if elements that makes up the given SCEV properly dominate
1244 /// the specified basic block.
1245 bool properlyDominates(const SCEV *S, const BasicBlock *BB);
1246
1247 /// Test whether the given SCEV has Op as a direct or indirect operand.
1248 bool hasOperand(const SCEV *S, const SCEV *Op) const;
1249
1250 /// Return the size of an element read or written by Inst.
1251 const SCEV *getElementSize(Instruction *Inst);
1252
1253 void print(raw_ostream &OS) const;
1254 void verify() const;
1255 bool invalidate(Function &F, const PreservedAnalyses &PA,
1257
1258 /// Return the DataLayout associated with the module this SCEV instance is
1259 /// operating on.
1260 const DataLayout &getDataLayout() const {
1261 return F.getParent()->getDataLayout();
1262 }
1263
1264 const SCEVPredicate *getEqualPredicate(const SCEV *LHS, const SCEV *RHS);
1266 const SCEV *LHS, const SCEV *RHS);
1267
1268 const SCEVPredicate *
1271
1272 /// Re-writes the SCEV according to the Predicates in \p A.
1273 const SCEV *rewriteUsingPredicate(const SCEV *S, const Loop *L,
1274 const SCEVPredicate &A);
1275 /// Tries to convert the \p S expression to an AddRec expression,
1276 /// adding additional predicates to \p Preds as required.
1278 const SCEV *S, const Loop *L,
1280
1281 /// Compute \p LHS - \p RHS and returns the result as an APInt if it is a
1282 /// constant, and std::nullopt if it isn't.
1283 ///
1284 /// This is intended to be a cheaper version of getMinusSCEV. We can be
1285 /// frugal here since we just bail out of actually constructing and
1286 /// canonicalizing an expression in the cases where the result isn't going
1287 /// to be a constant.
1288 std::optional<APInt> computeConstantDifference(const SCEV *LHS,
1289 const SCEV *RHS);
1290
1291 /// Update no-wrap flags of an AddRec. This may drop the cached info about
1292 /// this AddRec (such as range info) in case if new flags may potentially
1293 /// sharpen it.
1294 void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags);
1295
1296 /// Try to apply information from loop guards for \p L to \p Expr.
1297 const SCEV *applyLoopGuards(const SCEV *Expr, const Loop *L);
1298
1299 /// Return true if the loop has no abnormal exits. That is, if the loop
1300 /// is not infinite, it must exit through an explicit edge in the CFG.
1301 /// (As opposed to either a) throwing out of the function or b) entering a
1302 /// well defined infinite loop in some callee.)
1304 return getLoopProperties(L).HasNoAbnormalExits;
1305 }
1306
1307 /// Return true if this loop is finite by assumption. That is,
1308 /// to be infinite, it must also be undefined.
1309 bool loopIsFiniteByAssumption(const Loop *L);
1310
1311 /// Return the set of Values that, if poison, will definitively result in S
1312 /// being poison as well. The returned set may be incomplete, i.e. there can
1313 /// be additional Values that also result in S being poison.
1315 const SCEV *S);
1316
1317 class FoldID {
1318 const SCEV *Op = nullptr;
1319 const Type *Ty = nullptr;
1320 unsigned short C;
1321
1322 public:
1323 FoldID(SCEVTypes C, const SCEV *Op, const Type *Ty) : Op(Op), Ty(Ty), C(C) {
1324 assert(Op);
1325 assert(Ty);
1326 }
1327
1328 FoldID(unsigned short C) : C(C) {}
1329
1330 unsigned computeHash() const {
1332 C, detail::combineHashValue(reinterpret_cast<uintptr_t>(Op),
1333 reinterpret_cast<uintptr_t>(Ty)));
1334 }
1335
1336 bool operator==(const FoldID &RHS) const {
1337 return std::tie(Op, Ty, C) == std::tie(RHS.Op, RHS.Ty, RHS.C);
1338 }
1339 };
1340
1341private:
1342 /// A CallbackVH to arrange for ScalarEvolution to be notified whenever a
1343 /// Value is deleted.
1344 class SCEVCallbackVH final : public CallbackVH {
1345 ScalarEvolution *SE;
1346
1347 void deleted() override;
1348 void allUsesReplacedWith(Value *New) override;
1349
1350 public:
1351 SCEVCallbackVH(Value *V, ScalarEvolution *SE = nullptr);
1352 };
1353
1354 friend class SCEVCallbackVH;
1355 friend class SCEVExpander;
1356 friend class SCEVUnknown;
1357
1358 /// The function we are analyzing.
1359 Function &F;
1360
1361 /// Does the module have any calls to the llvm.experimental.guard intrinsic
1362 /// at all? If this is false, we avoid doing work that will only help if
1363 /// thare are guards present in the IR.
1364 bool HasGuards;
1365
1366 /// The target library information for the target we are targeting.
1367 TargetLibraryInfo &TLI;
1368
1369 /// The tracker for \@llvm.assume intrinsics in this function.
1370 AssumptionCache &AC;
1371
1372 /// The dominator tree.
1373 DominatorTree &DT;
1374
1375 /// The loop information for the function we are currently analyzing.
1376 LoopInfo &LI;
1377
1378 /// This SCEV is used to represent unknown trip counts and things.
1379 std::unique_ptr<SCEVCouldNotCompute> CouldNotCompute;
1380
1381 /// The type for HasRecMap.
1383
1384 /// This is a cache to record whether a SCEV contains any scAddRecExpr.
1385 HasRecMapType HasRecMap;
1386
1387 /// The type for ExprValueMap.
1390
1391 /// ExprValueMap -- This map records the original values from which
1392 /// the SCEV expr is generated from.
1393 ExprValueMapType ExprValueMap;
1394
1395 /// The type for ValueExprMap.
1396 using ValueExprMapType =
1398
1399 /// This is a cache of the values we have analyzed so far.
1400 ValueExprMapType ValueExprMap;
1401
1402 /// This is a cache for expressions that got folded to a different existing
1403 /// SCEV.
1406
1407 /// Mark predicate values currently being processed by isImpliedCond.
1408 SmallPtrSet<const Value *, 6> PendingLoopPredicates;
1409
1410 /// Mark SCEVUnknown Phis currently being processed by getRangeRef.
1411 SmallPtrSet<const PHINode *, 6> PendingPhiRanges;
1412
1413 /// Mark SCEVUnknown Phis currently being processed by getRangeRefIter.
1414 SmallPtrSet<const PHINode *, 6> PendingPhiRangesIter;
1415
1416 // Mark SCEVUnknown Phis currently being processed by isImpliedViaMerge.
1417 SmallPtrSet<const PHINode *, 6> PendingMerges;
1418
1419 /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of
1420 /// conditions dominating the backedge of a loop.
1421 bool WalkingBEDominatingConds = false;
1422
1423 /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a
1424 /// predicate by splitting it into a set of independent predicates.
1425 bool ProvingSplitPredicate = false;
1426
1427 /// Memoized values for the getConstantMultiple
1428 DenseMap<const SCEV *, APInt> ConstantMultipleCache;
1429
1430 /// Return the Value set from which the SCEV expr is generated.
1431 ArrayRef<Value *> getSCEVValues(const SCEV *S);
1432
1433 /// Private helper method for the getConstantMultiple method.
1434 APInt getConstantMultipleImpl(const SCEV *S);
1435
1436 /// Information about the number of times a particular loop exit may be
1437 /// reached before exiting the loop.
1438 struct ExitNotTakenInfo {
1439 PoisoningVH<BasicBlock> ExitingBlock;
1440 const SCEV *ExactNotTaken;
1441 const SCEV *ConstantMaxNotTaken;
1442 const SCEV *SymbolicMaxNotTaken;
1444
1445 explicit ExitNotTakenInfo(
1446 PoisoningVH<BasicBlock> ExitingBlock, const SCEV *ExactNotTaken,
1447 const SCEV *ConstantMaxNotTaken, const SCEV *SymbolicMaxNotTaken,
1448 const SmallPtrSet<const SCEVPredicate *, 4> &Predicates)
1449 : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken),
1450 ConstantMaxNotTaken(ConstantMaxNotTaken),
1451 SymbolicMaxNotTaken(SymbolicMaxNotTaken), Predicates(Predicates) {}
1452
1453 bool hasAlwaysTruePredicate() const {
1454 return Predicates.empty();
1455 }
1456 };
1457
1458 /// Information about the backedge-taken count of a loop. This currently
1459 /// includes an exact count and a maximum count.
1460 ///
1461 class BackedgeTakenInfo {
1462 friend class ScalarEvolution;
1463
1464 /// A list of computable exits and their not-taken counts. Loops almost
1465 /// never have more than one computable exit.
1466 SmallVector<ExitNotTakenInfo, 1> ExitNotTaken;
1467
1468 /// Expression indicating the least constant maximum backedge-taken count of
1469 /// the loop that is known, or a SCEVCouldNotCompute. This expression is
1470 /// only valid if the redicates associated with all loop exits are true.
1471 const SCEV *ConstantMax = nullptr;
1472
1473 /// Indicating if \c ExitNotTaken has an element for every exiting block in
1474 /// the loop.
1475 bool IsComplete = false;
1476
1477 /// Expression indicating the least maximum backedge-taken count of the loop
1478 /// that is known, or a SCEVCouldNotCompute. Lazily computed on first query.
1479 const SCEV *SymbolicMax = nullptr;
1480
1481 /// True iff the backedge is taken either exactly Max or zero times.
1482 bool MaxOrZero = false;
1483
1484 bool isComplete() const { return IsComplete; }
1485 const SCEV *getConstantMax() const { return ConstantMax; }
1486
1487 public:
1488 BackedgeTakenInfo() = default;
1489 BackedgeTakenInfo(BackedgeTakenInfo &&) = default;
1490 BackedgeTakenInfo &operator=(BackedgeTakenInfo &&) = default;
1491
1492 using EdgeExitInfo = std::pair<BasicBlock *, ExitLimit>;
1493
1494 /// Initialize BackedgeTakenInfo from a list of exact exit counts.
1495 BackedgeTakenInfo(ArrayRef<EdgeExitInfo> ExitCounts, bool IsComplete,
1496 const SCEV *ConstantMax, bool MaxOrZero);
1497
1498 /// Test whether this BackedgeTakenInfo contains any computed information,
1499 /// or whether it's all SCEVCouldNotCompute values.
1500 bool hasAnyInfo() const {
1501 return !ExitNotTaken.empty() ||
1502 !isa<SCEVCouldNotCompute>(getConstantMax());
1503 }
1504
1505 /// Test whether this BackedgeTakenInfo contains complete information.
1506 bool hasFullInfo() const { return isComplete(); }
1507
1508 /// Return an expression indicating the exact *backedge-taken*
1509 /// count of the loop if it is known or SCEVCouldNotCompute
1510 /// otherwise. If execution makes it to the backedge on every
1511 /// iteration (i.e. there are no abnormal exists like exception
1512 /// throws and thread exits) then this is the number of times the
1513 /// loop header will execute minus one.
1514 ///
1515 /// If the SCEV predicate associated with the answer can be different
1516 /// from AlwaysTrue, we must add a (non null) Predicates argument.
1517 /// The SCEV predicate associated with the answer will be added to
1518 /// Predicates. A run-time check needs to be emitted for the SCEV
1519 /// predicate in order for the answer to be valid.
1520 ///
1521 /// Note that we should always know if we need to pass a predicate
1522 /// argument or not from the way the ExitCounts vector was computed.
1523 /// If we allowed SCEV predicates to be generated when populating this
1524 /// vector, this information can contain them and therefore a
1525 /// SCEVPredicate argument should be added to getExact.
1526 const SCEV *getExact(const Loop *L, ScalarEvolution *SE,
1527 SmallVector<const SCEVPredicate *, 4> *Predicates = nullptr) const;
1528
1529 /// Return the number of times this loop exit may fall through to the back
1530 /// edge, or SCEVCouldNotCompute. The loop is guaranteed not to exit via
1531 /// this block before this number of iterations, but may exit via another
1532 /// block.
1533 const SCEV *getExact(const BasicBlock *ExitingBlock,
1534 ScalarEvolution *SE) const;
1535
1536 /// Get the constant max backedge taken count for the loop.
1537 const SCEV *getConstantMax(ScalarEvolution *SE) const;
1538
1539 /// Get the constant max backedge taken count for the particular loop exit.
1540 const SCEV *getConstantMax(const BasicBlock *ExitingBlock,
1541 ScalarEvolution *SE) const;
1542
1543 /// Get the symbolic max backedge taken count for the loop.
1544 const SCEV *getSymbolicMax(const Loop *L, ScalarEvolution *SE);
1545
1546 /// Get the symbolic max backedge taken count for the particular loop exit.
1547 const SCEV *getSymbolicMax(const BasicBlock *ExitingBlock,
1548 ScalarEvolution *SE) const;
1549
1550 /// Return true if the number of times this backedge is taken is either the
1551 /// value returned by getConstantMax or zero.
1552 bool isConstantMaxOrZero(ScalarEvolution *SE) const;
1553 };
1554
1555 /// Cache the backedge-taken count of the loops for this function as they
1556 /// are computed.
1557 DenseMap<const Loop *, BackedgeTakenInfo> BackedgeTakenCounts;
1558
1559 /// Cache the predicated backedge-taken count of the loops for this
1560 /// function as they are computed.
1561 DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts;
1562
1563 /// Loops whose backedge taken counts directly use this non-constant SCEV.
1564 DenseMap<const SCEV *, SmallPtrSet<PointerIntPair<const Loop *, 1, bool>, 4>>
1565 BECountUsers;
1566
1567 /// This map contains entries for all of the PHI instructions that we
1568 /// attempt to compute constant evolutions for. This allows us to avoid
1569 /// potentially expensive recomputation of these properties. An instruction
1570 /// maps to null if we are unable to compute its exit value.
1571 DenseMap<PHINode *, Constant *> ConstantEvolutionLoopExitValue;
1572
1573 /// This map contains entries for all the expressions that we attempt to
1574 /// compute getSCEVAtScope information for, which can be expensive in
1575 /// extreme cases.
1576 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1577 ValuesAtScopes;
1578
1579 /// Reverse map for invalidation purposes: Stores of which SCEV and which
1580 /// loop this is the value-at-scope of.
1581 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1582 ValuesAtScopesUsers;
1583
1584 /// Memoized computeLoopDisposition results.
1585 DenseMap<const SCEV *,
1586 SmallVector<PointerIntPair<const Loop *, 2, LoopDisposition>, 2>>
1587 LoopDispositions;
1588
1589 struct LoopProperties {
1590 /// Set to true if the loop contains no instruction that can abnormally exit
1591 /// the loop (i.e. via throwing an exception, by terminating the thread
1592 /// cleanly or by infinite looping in a called function). Strictly
1593 /// speaking, the last one is not leaving the loop, but is identical to
1594 /// leaving the loop for reasoning about undefined behavior.
1595 bool HasNoAbnormalExits;
1596
1597 /// Set to true if the loop contains no instruction that can have side
1598 /// effects (i.e. via throwing an exception, volatile or atomic access).
1599 bool HasNoSideEffects;
1600 };
1601
1602 /// Cache for \c getLoopProperties.
1603 DenseMap<const Loop *, LoopProperties> LoopPropertiesCache;
1604
1605 /// Return a \c LoopProperties instance for \p L, creating one if necessary.
1606 LoopProperties getLoopProperties(const Loop *L);
1607
1608 bool loopHasNoSideEffects(const Loop *L) {
1609 return getLoopProperties(L).HasNoSideEffects;
1610 }
1611
1612 /// Compute a LoopDisposition value.
1613 LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L);
1614
1615 /// Memoized computeBlockDisposition results.
1616 DenseMap<
1617 const SCEV *,
1618 SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>>
1619 BlockDispositions;
1620
1621 /// Compute a BlockDisposition value.
1622 BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB);
1623
1624 /// Stores all SCEV that use a given SCEV as its direct operand.
1625 DenseMap<const SCEV *, SmallPtrSet<const SCEV *, 8> > SCEVUsers;
1626
1627 /// Memoized results from getRange
1628 DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
1629
1630 /// Memoized results from getRange
1631 DenseMap<const SCEV *, ConstantRange> SignedRanges;
1632
1633 /// Used to parameterize getRange
1634 enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED };
1635
1636 /// Set the memoized range for the given SCEV.
1637 const ConstantRange &setRange(const SCEV *S, RangeSignHint Hint,
1638 ConstantRange CR) {
1639 DenseMap<const SCEV *, ConstantRange> &Cache =
1640 Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges;
1641
1642 auto Pair = Cache.try_emplace(S, std::move(CR));
1643 if (!Pair.second)
1644 Pair.first->second = std::move(CR);
1645 return Pair.first->second;
1646 }
1647
1648 /// Determine the range for a particular SCEV.
1649 /// NOTE: This returns a reference to an entry in a cache. It must be
1650 /// copied if its needed for longer.
1651 const ConstantRange &getRangeRef(const SCEV *S, RangeSignHint Hint,
1652 unsigned Depth = 0);
1653
1654 /// Determine the range for a particular SCEV, but evaluates ranges for
1655 /// operands iteratively first.
1656 const ConstantRange &getRangeRefIter(const SCEV *S, RangeSignHint Hint);
1657
1658 /// Determines the range for the affine SCEVAddRecExpr {\p Start,+,\p Step}.
1659 /// Helper for \c getRange.
1660 ConstantRange getRangeForAffineAR(const SCEV *Start, const SCEV *Step,
1661 const APInt &MaxBECount);
1662
1663 /// Determines the range for the affine non-self-wrapping SCEVAddRecExpr {\p
1664 /// Start,+,\p Step}<nw>.
1665 ConstantRange getRangeForAffineNoSelfWrappingAR(const SCEVAddRecExpr *AddRec,
1666 const SCEV *MaxBECount,
1667 unsigned BitWidth,
1668 RangeSignHint SignHint);
1669
1670 /// Try to compute a range for the affine SCEVAddRecExpr {\p Start,+,\p
1671 /// Step} by "factoring out" a ternary expression from the add recurrence.
1672 /// Helper called by \c getRange.
1673 ConstantRange getRangeViaFactoring(const SCEV *Start, const SCEV *Step,
1674 const APInt &MaxBECount);
1675
1676 /// If the unknown expression U corresponds to a simple recurrence, return
1677 /// a constant range which represents the entire recurrence. Note that
1678 /// *add* recurrences with loop invariant steps aren't represented by
1679 /// SCEVUnknowns and thus don't use this mechanism.
1680 ConstantRange getRangeForUnknownRecurrence(const SCEVUnknown *U);
1681
1682 /// We know that there is no SCEV for the specified value. Analyze the
1683 /// expression recursively.
1684 const SCEV *createSCEV(Value *V);
1685
1686 /// We know that there is no SCEV for the specified value. Create a new SCEV
1687 /// for \p V iteratively.
1688 const SCEV *createSCEVIter(Value *V);
1689 /// Collect operands of \p V for which SCEV expressions should be constructed
1690 /// first. Returns a SCEV directly if it can be constructed trivially for \p
1691 /// V.
1692 const SCEV *getOperandsToCreate(Value *V, SmallVectorImpl<Value *> &Ops);
1693
1694 /// Provide the special handling we need to analyze PHI SCEVs.
1695 const SCEV *createNodeForPHI(PHINode *PN);
1696
1697 /// Helper function called from createNodeForPHI.
1698 const SCEV *createAddRecFromPHI(PHINode *PN);
1699
1700 /// A helper function for createAddRecFromPHI to handle simple cases.
1701 const SCEV *createSimpleAffineAddRec(PHINode *PN, Value *BEValueV,
1702 Value *StartValueV);
1703
1704 /// Helper function called from createNodeForPHI.
1705 const SCEV *createNodeFromSelectLikePHI(PHINode *PN);
1706
1707 /// Provide special handling for a select-like instruction (currently this
1708 /// is either a select instruction or a phi node). \p Ty is the type of the
1709 /// instruction being processed, that is assumed equivalent to
1710 /// "Cond ? TrueVal : FalseVal".
1711 std::optional<const SCEV *>
1712 createNodeForSelectOrPHIInstWithICmpInstCond(Type *Ty, ICmpInst *Cond,
1713 Value *TrueVal, Value *FalseVal);
1714
1715 /// See if we can model this select-like instruction via umin_seq expression.
1716 const SCEV *createNodeForSelectOrPHIViaUMinSeq(Value *I, Value *Cond,
1717 Value *TrueVal,
1718 Value *FalseVal);
1719
1720 /// Given a value \p V, which is a select-like instruction (currently this is
1721 /// either a select instruction or a phi node), which is assumed equivalent to
1722 /// Cond ? TrueVal : FalseVal
1723 /// see if we can model it as a SCEV expression.
1724 const SCEV *createNodeForSelectOrPHI(Value *V, Value *Cond, Value *TrueVal,
1725 Value *FalseVal);
1726
1727 /// Provide the special handling we need to analyze GEP SCEVs.
1728 const SCEV *createNodeForGEP(GEPOperator *GEP);
1729
1730 /// Implementation code for getSCEVAtScope; called at most once for each
1731 /// SCEV+Loop pair.
1732 const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L);
1733
1734 /// Return the BackedgeTakenInfo for the given loop, lazily computing new
1735 /// values if the loop hasn't been analyzed yet. The returned result is
1736 /// guaranteed not to be predicated.
1737 BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L);
1738
1739 /// Similar to getBackedgeTakenInfo, but will add predicates as required
1740 /// with the purpose of returning complete information.
1741 const BackedgeTakenInfo &getPredicatedBackedgeTakenInfo(const Loop *L);
1742
1743 /// Compute the number of times the specified loop will iterate.
1744 /// If AllowPredicates is set, we will create new SCEV predicates as
1745 /// necessary in order to return an exact answer.
1746 BackedgeTakenInfo computeBackedgeTakenCount(const Loop *L,
1747 bool AllowPredicates = false);
1748
1749 /// Compute the number of times the backedge of the specified loop will
1750 /// execute if it exits via the specified block. If AllowPredicates is set,
1751 /// this call will try to use a minimal set of SCEV predicates in order to
1752 /// return an exact answer.
1753 ExitLimit computeExitLimit(const Loop *L, BasicBlock *ExitingBlock,
1754 bool AllowPredicates = false);
1755
1756 /// Return a symbolic upper bound for the backedge taken count of the loop.
1757 /// This is more general than getConstantMaxBackedgeTakenCount as it returns
1758 /// an arbitrary expression as opposed to only constants.
1759 const SCEV *computeSymbolicMaxBackedgeTakenCount(const Loop *L);
1760
1761 // Helper functions for computeExitLimitFromCond to avoid exponential time
1762 // complexity.
1763
1764 class ExitLimitCache {
1765 // It may look like we need key on the whole (L, ExitIfTrue,
1766 // ControlsOnlyExit, AllowPredicates) tuple, but recursive calls to
1767 // computeExitLimitFromCondCached from computeExitLimitFromCondImpl only
1768 // vary the in \c ExitCond and \c ControlsOnlyExit parameters. We remember
1769 // the initial values of the other values to assert our assumption.
1770 SmallDenseMap<PointerIntPair<Value *, 1>, ExitLimit> TripCountMap;
1771
1772 const Loop *L;
1773 bool ExitIfTrue;
1774 bool AllowPredicates;
1775
1776 public:
1777 ExitLimitCache(const Loop *L, bool ExitIfTrue, bool AllowPredicates)
1778 : L(L), ExitIfTrue(ExitIfTrue), AllowPredicates(AllowPredicates) {}
1779
1780 std::optional<ExitLimit> find(const Loop *L, Value *ExitCond,
1781 bool ExitIfTrue, bool ControlsOnlyExit,
1782 bool AllowPredicates);
1783
1784 void insert(const Loop *L, Value *ExitCond, bool ExitIfTrue,
1785 bool ControlsOnlyExit, bool AllowPredicates,
1786 const ExitLimit &EL);
1787 };
1788
1789 using ExitLimitCacheTy = ExitLimitCache;
1790
1791 ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache,
1792 const Loop *L, Value *ExitCond,
1793 bool ExitIfTrue,
1794 bool ControlsOnlyExit,
1795 bool AllowPredicates);
1796 ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache, const Loop *L,
1797 Value *ExitCond, bool ExitIfTrue,
1798 bool ControlsOnlyExit,
1799 bool AllowPredicates);
1800 std::optional<ScalarEvolution::ExitLimit> computeExitLimitFromCondFromBinOp(
1801 ExitLimitCacheTy &Cache, const Loop *L, Value *ExitCond, bool ExitIfTrue,
1802 bool ControlsOnlyExit, bool AllowPredicates);
1803
1804 /// Compute the number of times the backedge of the specified loop will
1805 /// execute if its exit condition were a conditional branch of the ICmpInst
1806 /// ExitCond and ExitIfTrue. If AllowPredicates is set, this call will try
1807 /// to use a minimal set of SCEV predicates in order to return an exact
1808 /// answer.
1809 ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond,
1810 bool ExitIfTrue,
1811 bool IsSubExpr,
1812 bool AllowPredicates = false);
1813
1814 /// Variant of previous which takes the components representing an ICmp
1815 /// as opposed to the ICmpInst itself. Note that the prior version can
1816 /// return more precise results in some cases and is preferred when caller
1817 /// has a materialized ICmp.
1818 ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst::Predicate Pred,
1819 const SCEV *LHS, const SCEV *RHS,
1820 bool IsSubExpr,
1821 bool AllowPredicates = false);
1822
1823 /// Compute the number of times the backedge of the specified loop will
1824 /// execute if its exit condition were a switch with a single exiting case
1825 /// to ExitingBB.
1826 ExitLimit computeExitLimitFromSingleExitSwitch(const Loop *L,
1827 SwitchInst *Switch,
1828 BasicBlock *ExitingBB,
1829 bool IsSubExpr);
1830
1831 /// Compute the exit limit of a loop that is controlled by a
1832 /// "(IV >> 1) != 0" type comparison. We cannot compute the exact trip
1833 /// count in these cases (since SCEV has no way of expressing them), but we
1834 /// can still sometimes compute an upper bound.
1835 ///
1836 /// Return an ExitLimit for a loop whose backedge is guarded by `LHS Pred
1837 /// RHS`.
1838 ExitLimit computeShiftCompareExitLimit(Value *LHS, Value *RHS, const Loop *L,
1839 ICmpInst::Predicate Pred);
1840
1841 /// If the loop is known to execute a constant number of times (the
1842 /// condition evolves only from constants), try to evaluate a few iterations
1843 /// of the loop until we get the exit condition gets a value of ExitWhen
1844 /// (true or false). If we cannot evaluate the exit count of the loop,
1845 /// return CouldNotCompute.
1846 const SCEV *computeExitCountExhaustively(const Loop *L, Value *Cond,
1847 bool ExitWhen);
1848
1849 /// Return the number of times an exit condition comparing the specified
1850 /// value to zero will execute. If not computable, return CouldNotCompute.
1851 /// If AllowPredicates is set, this call will try to use a minimal set of
1852 /// SCEV predicates in order to return an exact answer.
1853 ExitLimit howFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr,
1854 bool AllowPredicates = false);
1855
1856 /// Return the number of times an exit condition checking the specified
1857 /// value for nonzero will execute. If not computable, return
1858 /// CouldNotCompute.
1859 ExitLimit howFarToNonZero(const SCEV *V, const Loop *L);
1860
1861 /// Return the number of times an exit condition containing the specified
1862 /// less-than comparison will execute. If not computable, return
1863 /// CouldNotCompute.
1864 ///
1865 /// \p isSigned specifies whether the less-than is signed.
1866 ///
1867 /// \p ControlsOnlyExit is true when the LHS < RHS condition directly controls
1868 /// the branch (loops exits only if condition is true). In this case, we can
1869 /// use NoWrapFlags to skip overflow checks.
1870 ///
1871 /// If \p AllowPredicates is set, this call will try to use a minimal set of
1872 /// SCEV predicates in order to return an exact answer.
1873 ExitLimit howManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
1874 bool isSigned, bool ControlsOnlyExit,
1875 bool AllowPredicates = false);
1876
1877 ExitLimit howManyGreaterThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
1878 bool isSigned, bool IsSubExpr,
1879 bool AllowPredicates = false);
1880
1881 /// Return a predecessor of BB (which may not be an immediate predecessor)
1882 /// which has exactly one successor from which BB is reachable, or null if
1883 /// no such block is found.
1884 std::pair<const BasicBlock *, const BasicBlock *>
1885 getPredecessorWithUniqueSuccessorForBB(const BasicBlock *BB) const;
1886
1887 /// Test whether the condition described by Pred, LHS, and RHS is true
1888 /// whenever the given FoundCondValue value evaluates to true in given
1889 /// Context. If Context is nullptr, then the found predicate is true
1890 /// everywhere. LHS and FoundLHS may have different type width.
1891 bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
1892 const Value *FoundCondValue, bool Inverse,
1893 const Instruction *Context = nullptr);
1894
1895 /// Test whether the condition described by Pred, LHS, and RHS is true
1896 /// whenever the given FoundCondValue value evaluates to true in given
1897 /// Context. If Context is nullptr, then the found predicate is true
1898 /// everywhere. LHS and FoundLHS must have same type width.
1899 bool isImpliedCondBalancedTypes(ICmpInst::Predicate Pred, const SCEV *LHS,
1900 const SCEV *RHS,
1901 ICmpInst::Predicate FoundPred,
1902 const SCEV *FoundLHS, const SCEV *FoundRHS,
1903 const Instruction *CtxI);
1904
1905 /// Test whether the condition described by Pred, LHS, and RHS is true
1906 /// whenever the condition described by FoundPred, FoundLHS, FoundRHS is
1907 /// true in given Context. If Context is nullptr, then the found predicate is
1908 /// true everywhere.
1909 bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
1910 ICmpInst::Predicate FoundPred, const SCEV *FoundLHS,
1911 const SCEV *FoundRHS,
1912 const Instruction *Context = nullptr);
1913
1914 /// Test whether the condition described by Pred, LHS, and RHS is true
1915 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1916 /// true in given Context. If Context is nullptr, then the found predicate is
1917 /// true everywhere.
1918 bool isImpliedCondOperands(ICmpInst::Predicate Pred, const SCEV *LHS,
1919 const SCEV *RHS, const SCEV *FoundLHS,
1920 const SCEV *FoundRHS,
1921 const Instruction *Context = nullptr);
1922
1923 /// Test whether the condition described by Pred, LHS, and RHS is true
1924 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1925 /// true. Here LHS is an operation that includes FoundLHS as one of its
1926 /// arguments.
1927 bool isImpliedViaOperations(ICmpInst::Predicate Pred,
1928 const SCEV *LHS, const SCEV *RHS,
1929 const SCEV *FoundLHS, const SCEV *FoundRHS,
1930 unsigned Depth = 0);
1931
1932 /// Test whether the condition described by Pred, LHS, and RHS is true.
1933 /// Use only simple non-recursive types of checks, such as range analysis etc.
1934 bool isKnownViaNonRecursiveReasoning(ICmpInst::Predicate Pred,
1935 const SCEV *LHS, const SCEV *RHS);
1936
1937 /// Test whether the condition described by Pred, LHS, and RHS is true
1938 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1939 /// true.
1940 bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, const SCEV *LHS,
1941 const SCEV *RHS, const SCEV *FoundLHS,
1942 const SCEV *FoundRHS);
1943
1944 /// Test whether the condition described by Pred, LHS, and RHS is true
1945 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1946 /// true. Utility function used by isImpliedCondOperands. Tries to get
1947 /// cases like "X `sgt` 0 => X - 1 `sgt` -1".
1948 bool isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred, const SCEV *LHS,
1949 const SCEV *RHS,
1950 ICmpInst::Predicate FoundPred,
1951 const SCEV *FoundLHS,
1952 const SCEV *FoundRHS);
1953
1954 /// Return true if the condition denoted by \p LHS \p Pred \p RHS is implied
1955 /// by a call to @llvm.experimental.guard in \p BB.
1956 bool isImpliedViaGuard(const BasicBlock *BB, ICmpInst::Predicate Pred,
1957 const SCEV *LHS, const SCEV *RHS);
1958
1959 /// Test whether the condition described by Pred, LHS, and RHS is true
1960 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1961 /// true.
1962 ///
1963 /// This routine tries to rule out certain kinds of integer overflow, and
1964 /// then tries to reason about arithmetic properties of the predicates.
1965 bool isImpliedCondOperandsViaNoOverflow(ICmpInst::Predicate Pred,
1966 const SCEV *LHS, const SCEV *RHS,
1967 const SCEV *FoundLHS,
1968 const SCEV *FoundRHS);
1969
1970 /// Test whether the condition described by Pred, LHS, and RHS is true
1971 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1972 /// true.
1973 ///
1974 /// This routine tries to weaken the known condition basing on fact that
1975 /// FoundLHS is an AddRec.
1976 bool isImpliedCondOperandsViaAddRecStart(ICmpInst::Predicate Pred,
1977 const SCEV *LHS, const SCEV *RHS,
1978 const SCEV *FoundLHS,
1979 const SCEV *FoundRHS,
1980 const Instruction *CtxI);
1981
1982 /// Test whether the condition described by Pred, LHS, and RHS is true
1983 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1984 /// true.
1985 ///
1986 /// This routine tries to figure out predicate for Phis which are SCEVUnknown
1987 /// if it is true for every possible incoming value from their respective
1988 /// basic blocks.
1989 bool isImpliedViaMerge(ICmpInst::Predicate Pred,
1990 const SCEV *LHS, const SCEV *RHS,
1991 const SCEV *FoundLHS, const SCEV *FoundRHS,
1992 unsigned Depth);
1993
1994 /// Test whether the condition described by Pred, LHS, and RHS is true
1995 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1996 /// true.
1997 ///
1998 /// This routine tries to reason about shifts.
1999 bool isImpliedCondOperandsViaShift(ICmpInst::Predicate Pred, const SCEV *LHS,
2000 const SCEV *RHS, const SCEV *FoundLHS,
2001 const SCEV *FoundRHS);
2002
2003 /// If we know that the specified Phi is in the header of its containing
2004 /// loop, we know the loop executes a constant number of times, and the PHI
2005 /// node is just a recurrence involving constants, fold it.
2006 Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt &BEs,
2007 const Loop *L);
2008
2009 /// Test if the given expression is known to satisfy the condition described
2010 /// by Pred and the known constant ranges of LHS and RHS.
2011 bool isKnownPredicateViaConstantRanges(ICmpInst::Predicate Pred,
2012 const SCEV *LHS, const SCEV *RHS);
2013
2014 /// Try to prove the condition described by "LHS Pred RHS" by ruling out
2015 /// integer overflow.
2016 ///
2017 /// For instance, this will return true for "A s< (A + C)<nsw>" if C is
2018 /// positive.
2019 bool isKnownPredicateViaNoOverflow(ICmpInst::Predicate Pred, const SCEV *LHS,
2020 const SCEV *RHS);
2021
2022 /// Try to split Pred LHS RHS into logical conjunctions (and's) and try to
2023 /// prove them individually.
2024 bool isKnownPredicateViaSplitting(ICmpInst::Predicate Pred, const SCEV *LHS,
2025 const SCEV *RHS);
2026
2027 /// Try to match the Expr as "(L + R)<Flags>".
2028 bool splitBinaryAdd(const SCEV *Expr, const SCEV *&L, const SCEV *&R,
2029 SCEV::NoWrapFlags &Flags);
2030
2031 /// Forget predicated/non-predicated backedge taken counts for the given loop.
2032 void forgetBackedgeTakenCounts(const Loop *L, bool Predicated);
2033
2034 /// Drop memoized information for all \p SCEVs.
2035 void forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs);
2036
2037 /// Helper for forgetMemoizedResults.
2038 void forgetMemoizedResultsImpl(const SCEV *S);
2039
2040 /// Iterate over instructions in \p Worklist and their users. Erase entries
2041 /// from ValueExprMap and collect SCEV expressions in \p ToForget
2042 void visitAndClearUsers(SmallVectorImpl<Instruction *> &Worklist,
2043 SmallPtrSetImpl<Instruction *> &Visited,
2044 SmallVectorImpl<const SCEV *> &ToForget);
2045
2046 /// Erase Value from ValueExprMap and ExprValueMap.
2047 void eraseValueFromMap(Value *V);
2048
2049 /// Insert V to S mapping into ValueExprMap and ExprValueMap.
2050 void insertValueToMap(Value *V, const SCEV *S);
2051
2052 /// Return false iff given SCEV contains a SCEVUnknown with NULL value-
2053 /// pointer.
2054 bool checkValidity(const SCEV *S) const;
2055
2056 /// Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be
2057 /// equal to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}. This is
2058 /// equivalent to proving no signed (resp. unsigned) wrap in
2059 /// {`Start`,+,`Step`} if `ExtendOpTy` is `SCEVSignExtendExpr`
2060 /// (resp. `SCEVZeroExtendExpr`).
2061 template <typename ExtendOpTy>
2062 bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step,
2063 const Loop *L);
2064
2065 /// Try to prove NSW or NUW on \p AR relying on ConstantRange manipulation.
2066 SCEV::NoWrapFlags proveNoWrapViaConstantRanges(const SCEVAddRecExpr *AR);
2067
2068 /// Try to prove NSW on \p AR by proving facts about conditions known on
2069 /// entry and backedge.
2070 SCEV::NoWrapFlags proveNoSignedWrapViaInduction(const SCEVAddRecExpr *AR);
2071
2072 /// Try to prove NUW on \p AR by proving facts about conditions known on
2073 /// entry and backedge.
2074 SCEV::NoWrapFlags proveNoUnsignedWrapViaInduction(const SCEVAddRecExpr *AR);
2075
2076 std::optional<MonotonicPredicateType>
2077 getMonotonicPredicateTypeImpl(const SCEVAddRecExpr *LHS,
2078 ICmpInst::Predicate Pred);
2079
2080 /// Return SCEV no-wrap flags that can be proven based on reasoning about
2081 /// how poison produced from no-wrap flags on this value (e.g. a nuw add)
2082 /// would trigger undefined behavior on overflow.
2083 SCEV::NoWrapFlags getNoWrapFlagsFromUB(const Value *V);
2084
2085 /// Return a scope which provides an upper bound on the defining scope of
2086 /// 'S'. Specifically, return the first instruction in said bounding scope.
2087 /// Return nullptr if the scope is trivial (function entry).
2088 /// (See scope definition rules associated with flag discussion above)
2089 const Instruction *getNonTrivialDefiningScopeBound(const SCEV *S);
2090
2091 /// Return a scope which provides an upper bound on the defining scope for
2092 /// a SCEV with the operands in Ops. The outparam Precise is set if the
2093 /// bound found is a precise bound (i.e. must be the defining scope.)
2094 const Instruction *getDefiningScopeBound(ArrayRef<const SCEV *> Ops,
2095 bool &Precise);
2096
2097 /// Wrapper around the above for cases which don't care if the bound
2098 /// is precise.
2099 const Instruction *getDefiningScopeBound(ArrayRef<const SCEV *> Ops);
2100
2101 /// Given two instructions in the same function, return true if we can
2102 /// prove B must execute given A executes.
2103 bool isGuaranteedToTransferExecutionTo(const Instruction *A,
2104 const Instruction *B);
2105
2106 /// Return true if the SCEV corresponding to \p I is never poison. Proving
2107 /// this is more complex than proving that just \p I is never poison, since
2108 /// SCEV commons expressions across control flow, and you can have cases
2109 /// like:
2110 ///
2111 /// idx0 = a + b;
2112 /// ptr[idx0] = 100;
2113 /// if (<condition>) {
2114 /// idx1 = a +nsw b;
2115 /// ptr[idx1] = 200;
2116 /// }
2117 ///
2118 /// where the SCEV expression (+ a b) is guaranteed to not be poison (and
2119 /// hence not sign-overflow) only if "<condition>" is true. Since both
2120 /// `idx0` and `idx1` will be mapped to the same SCEV expression, (+ a b),
2121 /// it is not okay to annotate (+ a b) with <nsw> in the above example.
2122 bool isSCEVExprNeverPoison(const Instruction *I);
2123
2124 /// This is like \c isSCEVExprNeverPoison but it specifically works for
2125 /// instructions that will get mapped to SCEV add recurrences. Return true
2126 /// if \p I will never generate poison under the assumption that \p I is an
2127 /// add recurrence on the loop \p L.
2128 bool isAddRecNeverPoison(const Instruction *I, const Loop *L);
2129
2130 /// Similar to createAddRecFromPHI, but with the additional flexibility of
2131 /// suggesting runtime overflow checks in case casts are encountered.
2132 /// If successful, the analysis records that for this loop, \p SymbolicPHI,
2133 /// which is the UnknownSCEV currently representing the PHI, can be rewritten
2134 /// into an AddRec, assuming some predicates; The function then returns the
2135 /// AddRec and the predicates as a pair, and caches this pair in
2136 /// PredicatedSCEVRewrites.
2137 /// If the analysis is not successful, a mapping from the \p SymbolicPHI to
2138 /// itself (with no predicates) is recorded, and a nullptr with an empty
2139 /// predicates vector is returned as a pair.
2140 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2141 createAddRecFromPHIWithCastsImpl(const SCEVUnknown *SymbolicPHI);
2142
2143 /// Compute the maximum backedge count based on the range of values
2144 /// permitted by Start, End, and Stride. This is for loops of the form
2145 /// {Start, +, Stride} LT End.
2146 ///
2147 /// Preconditions:
2148 /// * the induction variable is known to be positive.
2149 /// * the induction variable is assumed not to overflow (i.e. either it
2150 /// actually doesn't, or we'd have to immediately execute UB)
2151 /// We *don't* assert these preconditions so please be careful.
2152 const SCEV *computeMaxBECountForLT(const SCEV *Start, const SCEV *Stride,
2153 const SCEV *End, unsigned BitWidth,
2154 bool IsSigned);
2155
2156 /// Verify if an linear IV with positive stride can overflow when in a
2157 /// less-than comparison, knowing the invariant term of the comparison,
2158 /// the stride.
2159 bool canIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, bool IsSigned);
2160
2161 /// Verify if an linear IV with negative stride can overflow when in a
2162 /// greater-than comparison, knowing the invariant term of the comparison,
2163 /// the stride.
2164 bool canIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, bool IsSigned);
2165
2166 /// Get add expr already created or create a new one.
2167 const SCEV *getOrCreateAddExpr(ArrayRef<const SCEV *> Ops,
2168 SCEV::NoWrapFlags Flags);
2169
2170 /// Get mul expr already created or create a new one.
2171 const SCEV *getOrCreateMulExpr(ArrayRef<const SCEV *> Ops,
2172 SCEV::NoWrapFlags Flags);
2173
2174 // Get addrec expr already created or create a new one.
2175 const SCEV *getOrCreateAddRecExpr(ArrayRef<const SCEV *> Ops,
2176 const Loop *L, SCEV::NoWrapFlags Flags);
2177
2178 /// Return x if \p Val is f(x) where f is a 1-1 function.
2179 const SCEV *stripInjectiveFunctions(const SCEV *Val) const;
2180
2181 /// Find all of the loops transitively used in \p S, and fill \p LoopsUsed.
2182 /// A loop is considered "used" by an expression if it contains
2183 /// an add rec on said loop.
2184 void getUsedLoops(const SCEV *S, SmallPtrSetImpl<const Loop *> &LoopsUsed);
2185
2186 /// Try to match the pattern generated by getURemExpr(A, B). If successful,
2187 /// Assign A and B to LHS and RHS, respectively.
2188 bool matchURem(const SCEV *Expr, const SCEV *&LHS, const SCEV *&RHS);
2189
2190 /// Look for a SCEV expression with type `SCEVType` and operands `Ops` in
2191 /// `UniqueSCEVs`. Return if found, else nullptr.
2192 SCEV *findExistingSCEVInCache(SCEVTypes SCEVType, ArrayRef<const SCEV *> Ops);
2193
2194 /// Get reachable blocks in this function, making limited use of SCEV
2195 /// reasoning about conditions.
2196 void getReachableBlocks(SmallPtrSetImpl<BasicBlock *> &Reachable,
2197 Function &F);
2198
2199 /// Return the given SCEV expression with a new set of operands.
2200 /// This preserves the origial nowrap flags.
2201 const SCEV *getWithOperands(const SCEV *S,
2202 SmallVectorImpl<const SCEV *> &NewOps);
2203
2204 FoldingSet<SCEV> UniqueSCEVs;
2205 FoldingSet<SCEVPredicate> UniquePreds;
2206 BumpPtrAllocator SCEVAllocator;
2207
2208 /// This maps loops to a list of addrecs that directly use said loop.
2209 DenseMap<const Loop *, SmallVector<const SCEVAddRecExpr *, 4>> LoopUsers;
2210
2211 /// Cache tentative mappings from UnknownSCEVs in a Loop, to a SCEV expression
2212 /// they can be rewritten into under certain predicates.
2213 DenseMap<std::pair<const SCEVUnknown *, const Loop *>,
2214 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2215 PredicatedSCEVRewrites;
2216
2217 /// Set of AddRecs for which proving NUW via an induction has already been
2218 /// tried.
2219 SmallPtrSet<const SCEVAddRecExpr *, 16> UnsignedWrapViaInductionTried;
2220
2221 /// Set of AddRecs for which proving NSW via an induction has already been
2222 /// tried.
2223 SmallPtrSet<const SCEVAddRecExpr *, 16> SignedWrapViaInductionTried;
2224
2225 /// The head of a linked list of all SCEVUnknown values that have been
2226 /// allocated. This is used by releaseMemory to locate them all and call
2227 /// their destructors.
2228 SCEVUnknown *FirstUnknown = nullptr;
2229};
2230
2231/// Analysis pass that exposes the \c ScalarEvolution for a function.
2233 : public AnalysisInfoMixin<ScalarEvolutionAnalysis> {
2235
2236 static AnalysisKey Key;
2237
2238public:
2240
2242};
2243
2244/// Verifier pass for the \c ScalarEvolutionAnalysis results.
2246 : public PassInfoMixin<ScalarEvolutionVerifierPass> {
2247public:
2249};
2250
2251/// Printer pass for the \c ScalarEvolutionAnalysis results.
2253 : public PassInfoMixin<ScalarEvolutionPrinterPass> {
2254 raw_ostream &OS;
2255
2256public:
2258
2260};
2261
2263 std::unique_ptr<ScalarEvolution> SE;
2264
2265public:
2266 static char ID;
2267
2269
2270 ScalarEvolution &getSE() { return *SE; }
2271 const ScalarEvolution &getSE() const { return *SE; }
2272
2273 bool runOnFunction(Function &F) override;
2274 void releaseMemory() override;
2275 void getAnalysisUsage(AnalysisUsage &AU) const override;
2276 void print(raw_ostream &OS, const Module * = nullptr) const override;
2277 void verifyAnalysis() const override;
2278};
2279
2280/// An interface layer with SCEV used to manage how we see SCEV expressions
2281/// for values in the context of existing predicates. We can add new
2282/// predicates, but we cannot remove them.
2283///
2284/// This layer has multiple purposes:
2285/// - provides a simple interface for SCEV versioning.
2286/// - guarantees that the order of transformations applied on a SCEV
2287/// expression for a single Value is consistent across two different
2288/// getSCEV calls. This means that, for example, once we've obtained
2289/// an AddRec expression for a certain value through expression
2290/// rewriting, we will continue to get an AddRec expression for that
2291/// Value.
2292/// - lowers the number of expression rewrites.
2294public:
2296
2297 const SCEVPredicate &getPredicate() const;
2298
2299 /// Returns the SCEV expression of V, in the context of the current SCEV
2300 /// predicate. The order of transformations applied on the expression of V
2301 /// returned by ScalarEvolution is guaranteed to be preserved, even when
2302 /// adding new predicates.
2303 const SCEV *getSCEV(Value *V);
2304
2305 /// Get the (predicated) backedge count for the analyzed loop.
2306 const SCEV *getBackedgeTakenCount();
2307
2308 /// Adds a new predicate.
2309 void addPredicate(const SCEVPredicate &Pred);
2310
2311 /// Attempts to produce an AddRecExpr for V by adding additional SCEV
2312 /// predicates. If we can't transform the expression into an AddRecExpr we
2313 /// return nullptr and not add additional SCEV predicates to the current
2314 /// context.
2315 const SCEVAddRecExpr *getAsAddRec(Value *V);
2316
2317 /// Proves that V doesn't overflow by adding SCEV predicate.
2319
2320 /// Returns true if we've proved that V doesn't wrap by means of a SCEV
2321 /// predicate.
2323
2324 /// Returns the ScalarEvolution analysis used.
2325 ScalarEvolution *getSE() const { return &SE; }
2326
2327 /// We need to explicitly define the copy constructor because of FlagsMap.
2329
2330 /// Print the SCEV mappings done by the Predicated Scalar Evolution.
2331 /// The printed text is indented by \p Depth.
2332 void print(raw_ostream &OS, unsigned Depth) const;
2333
2334 /// Check if \p AR1 and \p AR2 are equal, while taking into account
2335 /// Equal predicates in Preds.
2337 const SCEVAddRecExpr *AR2) const;
2338
2339private:
2340 /// Increments the version number of the predicate. This needs to be called
2341 /// every time the SCEV predicate changes.
2342 void updateGeneration();
2343
2344 /// Holds a SCEV and the version number of the SCEV predicate used to
2345 /// perform the rewrite of the expression.
2346 using RewriteEntry = std::pair<unsigned, const SCEV *>;
2347
2348 /// Maps a SCEV to the rewrite result of that SCEV at a certain version
2349 /// number. If this number doesn't match the current Generation, we will
2350 /// need to do a rewrite. To preserve the transformation order of previous
2351 /// rewrites, we will rewrite the previous result instead of the original
2352 /// SCEV.
2354
2355 /// Records what NoWrap flags we've added to a Value *.
2357
2358 /// The ScalarEvolution analysis.
2359 ScalarEvolution &SE;
2360
2361 /// The analyzed Loop.
2362 const Loop &L;
2363
2364 /// The SCEVPredicate that forms our context. We will rewrite all
2365 /// expressions assuming that this predicate true.
2366 std::unique_ptr<SCEVUnionPredicate> Preds;
2367
2368 /// Marks the version of the SCEV predicate used. When rewriting a SCEV
2369 /// expression we mark it with the version of the predicate. We use this to
2370 /// figure out if the predicate has changed from the last rewrite of the
2371 /// SCEV. If so, we need to perform a new rewrite.
2372 unsigned Generation = 0;
2373
2374 /// The backedge taken count.
2375 const SCEV *BackedgeCount = nullptr;
2376};
2377
2378template <> struct DenseMapInfo<ScalarEvolution::FoldID> {
2381 return ID;
2382 }
2385 return ID;
2386 }
2387
2388 static unsigned getHashValue(const ScalarEvolution::FoldID &Val) {
2389 return Val.computeHash();
2390 }
2391
2394 return LHS == RHS;
2395 }
2396};
2397
2398} // end namespace llvm
2399
2400#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:478
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:690
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:649
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:60
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:780
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
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:164
Node - This class is used to maintain the singly linked bucket list in a folding set.
Definition: FoldingSet.h:137
FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID,...
Definition: FoldingSet.h:289
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:319
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:44
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:275
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:172
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,...
void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)
Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...
bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
const SCEV * getCouldNotCompute()
bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
BlockDisposition
An enum describing the relationship between a SCEV and a basic block.
@ DominatesBlock
The SCEV dominates the block.
@ ProperlyDominatesBlock
The SCEV properly dominates the block.
@ DoesNotDominateBlock
The SCEV does not dominate the block.
std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterationsImpl(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
void getPoisonGeneratingValues(SmallPtrSetImpl< const Value * > &Result, const SCEV *S)
Return the set of Values that, if poison, will definitively result in S being poison as well.
void forgetLoopDispositions()
Called when the client has changed the disposition of values in this loop.
const SCEV * getVScale(Type *Ty)
unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
const SCEV * getPowerOfTwo(Type *Ty, unsigned Power)
Return a SCEV for the constant Power of two.
const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
bool dominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV dominate the specified basic block.
APInt getUnsignedRangeMax(const SCEV *S)
Determine the max of the unsigned range for a particular SCEV.
ExitCountKind
The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of ...
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
@ ConstantMaximum
A constant which provides an upper bound on the exact trip count.
@ Exact
An expression exactly describing the number of times the backedge has executed when a loop is exited.
std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterations(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L at given Context duri...
const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
const SCEV * getSizeOfExpr(Type *IntTy, TypeSize Size)
Return an expression for a TypeSize.
const SCEV * getUnknown(Value *V)
std::optional< std::pair< const SCEV *, SmallVector< const SCEVPredicate *, 3 > > > createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI)
Checks if SymbolicPHI can be rewritten as an AddRecExpr under some Predicates.
const SCEV * getTruncateOrZeroExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
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:216
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
See the file comment.
Definition: ValueMap.h:84
LLVM Value Representation.
Definition: Value.h:74
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
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:1746
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:191
#define N
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:414
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:89
DefaultFoldingSetTrait - This class provides default implementations for FoldingSetTrait implementati...
Definition: FoldingSet.h:232
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:262
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:391
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)