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