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