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

source code of llvm/include/llvm/Analysis/ScalarEvolution.h