Line data Source code
1 : //===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // The ScalarEvolution class is an LLVM pass which can be used to analyze and
11 : // categorize scalar expressions in loops. It specializes in recognizing
12 : // general induction variables, representing them with the abstract and opaque
13 : // SCEV class. Given this analysis, trip counts of loops and other important
14 : // properties can be obtained.
15 : //
16 : // This analysis is primarily useful for induction variable substitution and
17 : // strength reduction.
18 : //
19 : //===----------------------------------------------------------------------===//
20 :
21 : #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
22 : #define LLVM_ANALYSIS_SCALAREVOLUTION_H
23 :
24 : #include "llvm/ADT/APInt.h"
25 : #include "llvm/ADT/ArrayRef.h"
26 : #include "llvm/ADT/DenseMap.h"
27 : #include "llvm/ADT/DenseMapInfo.h"
28 : #include "llvm/ADT/FoldingSet.h"
29 : #include "llvm/ADT/Hashing.h"
30 : #include "llvm/ADT/Optional.h"
31 : #include "llvm/ADT/PointerIntPair.h"
32 : #include "llvm/ADT/SetVector.h"
33 : #include "llvm/ADT/SmallPtrSet.h"
34 : #include "llvm/ADT/SmallVector.h"
35 : #include "llvm/Analysis/LoopInfo.h"
36 : #include "llvm/IR/ConstantRange.h"
37 : #include "llvm/IR/Function.h"
38 : #include "llvm/IR/InstrTypes.h"
39 : #include "llvm/IR/Instructions.h"
40 : #include "llvm/IR/Operator.h"
41 : #include "llvm/IR/PassManager.h"
42 : #include "llvm/IR/ValueHandle.h"
43 : #include "llvm/IR/ValueMap.h"
44 : #include "llvm/Pass.h"
45 : #include "llvm/Support/Allocator.h"
46 : #include "llvm/Support/Casting.h"
47 : #include "llvm/Support/Compiler.h"
48 : #include <algorithm>
49 : #include <cassert>
50 : #include <cstdint>
51 : #include <memory>
52 : #include <utility>
53 :
54 : namespace llvm {
55 :
56 : class AssumptionCache;
57 : class BasicBlock;
58 : class Constant;
59 : class ConstantInt;
60 : class DataLayout;
61 : class DominatorTree;
62 : class GEPOperator;
63 : class Instruction;
64 : class LLVMContext;
65 : class raw_ostream;
66 : class ScalarEvolution;
67 : class SCEVAddRecExpr;
68 : class SCEVUnknown;
69 : class StructType;
70 : class TargetLibraryInfo;
71 : class Type;
72 : class Value;
73 :
74 : /// This class represents an analyzed expression in the program. These are
75 : /// opaque objects that the client is not allowed to do much with directly.
76 : ///
77 : class SCEV : public FoldingSetNode {
78 : friend struct FoldingSetTrait<SCEV>;
79 :
80 : /// A reference to an Interned FoldingSetNodeID for this node. The
81 : /// ScalarEvolution's BumpPtrAllocator holds the data.
82 : FoldingSetNodeIDRef FastID;
83 :
84 : // The SCEV baseclass this node corresponds to
85 : const unsigned short SCEVType;
86 :
87 : protected:
88 : /// This field is initialized to zero and may be used in subclasses to store
89 : /// miscellaneous information.
90 : unsigned short SubclassData = 0;
91 :
92 : public:
93 : /// NoWrapFlags are bitfield indices into SubclassData.
94 : ///
95 : /// Add and Mul expressions may have no-unsigned-wrap <NUW> or
96 : /// no-signed-wrap <NSW> properties, which are derived from the IR
97 : /// operator. NSW is a misnomer that we use to mean no signed overflow or
98 : /// underflow.
99 : ///
100 : /// AddRec expressions may have a no-self-wraparound <NW> property if, in
101 : /// the integer domain, abs(step) * max-iteration(loop) <=
102 : /// unsigned-max(bitwidth). This means that the recurrence will never reach
103 : /// its start value if the step is non-zero. Computing the same value on
104 : /// each iteration is not considered wrapping, and recurrences with step = 0
105 : /// are trivially <NW>. <NW> is independent of the sign of step and the
106 : /// value the add recurrence starts with.
107 : ///
108 : /// Note that NUW and NSW are also valid properties of a recurrence, and
109 : /// either implies NW. For convenience, NW will be set for a recurrence
110 : /// whenever either NUW or NSW are set.
111 : enum NoWrapFlags {
112 : FlagAnyWrap = 0, // No guarantee.
113 : FlagNW = (1 << 0), // No self-wrap.
114 : FlagNUW = (1 << 1), // No unsigned wrap.
115 : FlagNSW = (1 << 2), // No signed wrap.
116 : NoWrapMask = (1 << 3) - 1
117 : };
118 :
119 : explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy)
120 2520522 : : FastID(ID), SCEVType(SCEVTy) {}
121 : SCEV(const SCEV &) = delete;
122 : SCEV &operator=(const SCEV &) = delete;
123 :
124 23612763 : unsigned getSCEVType() const { return SCEVType; }
125 :
126 : /// Return the LLVM type of this SCEV expression.
127 : Type *getType() const;
128 :
129 : /// Return true if the expression is a constant zero.
130 : bool isZero() const;
131 :
132 : /// Return true if the expression is a constant one.
133 : bool isOne() const;
134 :
135 : /// Return true if the expression is a constant all-ones value.
136 : bool isAllOnesValue() const;
137 :
138 : /// Return true if the specified scev is negated, but not a constant.
139 : bool isNonConstantNegative() const;
140 :
141 : /// Print out the internal representation of this scalar to the specified
142 : /// stream. This should really only be used for debugging purposes.
143 : void print(raw_ostream &OS) const;
144 :
145 : /// This method is used for debugging.
146 : void dump() const;
147 : };
148 :
149 : // Specialize FoldingSetTrait for SCEV to avoid needing to compute
150 : // temporary FoldingSetNodeID values.
151 : template <> struct FoldingSetTrait<SCEV> : DefaultFoldingSetTrait<SCEV> {
152 0 : static void Profile(const SCEV &X, FoldingSetNodeID &ID) { ID = X.FastID; }
153 :
154 0 : static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, unsigned IDHash,
155 : FoldingSetNodeID &TempID) {
156 11435895 : return ID == X.FastID;
157 : }
158 :
159 0 : static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) {
160 444925 : return X.FastID.ComputeHash();
161 : }
162 : };
163 :
164 53181 : inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) {
165 57895 : S.print(OS);
166 53181 : return OS;
167 : }
168 :
169 : /// An object of this class is returned by queries that could not be answered.
170 : /// For example, if you ask for the number of iterations of a linked-list
171 : /// traversal loop, you will get one of these. None of the standard SCEV
172 : /// operations are valid on this class, it is just a marker.
173 : struct SCEVCouldNotCompute : public SCEV {
174 : SCEVCouldNotCompute();
175 :
176 : /// Methods for support type inquiry through isa, cast, and dyn_cast:
177 : static bool classof(const SCEV *S);
178 : };
179 :
180 : /// This class represents an assumption made using SCEV expressions which can
181 : /// be checked at run-time.
182 : class SCEVPredicate : public FoldingSetNode {
183 : friend struct FoldingSetTrait<SCEVPredicate>;
184 :
185 : /// A reference to an Interned FoldingSetNodeID for this node. The
186 : /// ScalarEvolution's BumpPtrAllocator holds the data.
187 : FoldingSetNodeIDRef FastID;
188 :
189 : public:
190 : enum SCEVPredicateKind { P_Union, P_Equal, P_Wrap };
191 :
192 : protected:
193 : SCEVPredicateKind Kind;
194 : ~SCEVPredicate() = default;
195 : SCEVPredicate(const SCEVPredicate &) = default;
196 : SCEVPredicate &operator=(const SCEVPredicate &) = default;
197 :
198 : public:
199 : SCEVPredicate(const FoldingSetNodeIDRef ID, SCEVPredicateKind Kind);
200 :
201 0 : SCEVPredicateKind getKind() const { return Kind; }
202 :
203 : /// Returns the estimated complexity of this predicate. This is roughly
204 : /// measured in the number of run-time checks required.
205 0 : virtual unsigned getComplexity() const { return 1; }
206 :
207 : /// Returns true if the predicate is always true. This means that no
208 : /// assumptions were made and nothing needs to be checked at run-time.
209 : virtual bool isAlwaysTrue() const = 0;
210 :
211 : /// Returns true if this predicate implies \p N.
212 : virtual bool implies(const SCEVPredicate *N) const = 0;
213 :
214 : /// Prints a textual representation of this predicate with an indentation of
215 : /// \p Depth.
216 : virtual void print(raw_ostream &OS, unsigned Depth = 0) const = 0;
217 :
218 : /// Returns the SCEV to which this predicate applies, or nullptr if this is
219 : /// a SCEVUnionPredicate.
220 : virtual const SCEV *getExpr() const = 0;
221 : };
222 :
223 : inline raw_ostream &operator<<(raw_ostream &OS, const SCEVPredicate &P) {
224 : P.print(OS);
225 : return OS;
226 : }
227 :
228 : // Specialize FoldingSetTrait for SCEVPredicate to avoid needing to compute
229 : // temporary FoldingSetNodeID values.
230 : template <>
231 : struct FoldingSetTrait<SCEVPredicate> : DefaultFoldingSetTrait<SCEVPredicate> {
232 0 : static void Profile(const SCEVPredicate &X, FoldingSetNodeID &ID) {
233 0 : ID = X.FastID;
234 0 : }
235 :
236 0 : static bool Equals(const SCEVPredicate &X, const FoldingSetNodeID &ID,
237 : unsigned IDHash, FoldingSetNodeID &TempID) {
238 186 : return ID == X.FastID;
239 : }
240 :
241 0 : static unsigned ComputeHash(const SCEVPredicate &X,
242 : FoldingSetNodeID &TempID) {
243 0 : return X.FastID.ComputeHash();
244 : }
245 : };
246 :
247 : /// This class represents an assumption that two SCEV expressions are equal,
248 : /// and this can be checked at run-time.
249 : class SCEVEqualPredicate final : public SCEVPredicate {
250 : /// We assume that LHS == RHS.
251 : const SCEV *LHS;
252 : const SCEV *RHS;
253 :
254 : public:
255 : SCEVEqualPredicate(const FoldingSetNodeIDRef ID, const SCEV *LHS,
256 : const SCEV *RHS);
257 :
258 : /// Implementation of the SCEVPredicate interface
259 : bool implies(const SCEVPredicate *N) const override;
260 : void print(raw_ostream &OS, unsigned Depth = 0) const override;
261 : bool isAlwaysTrue() const override;
262 : const SCEV *getExpr() const override;
263 :
264 : /// Returns the left hand side of the equality.
265 0 : const SCEV *getLHS() const { return LHS; }
266 :
267 : /// Returns the right hand side of the equality.
268 0 : const SCEV *getRHS() const { return RHS; }
269 :
270 : /// Methods for support type inquiry through isa, cast, and dyn_cast:
271 : static bool classof(const SCEVPredicate *P) {
272 91 : return P->getKind() == P_Equal;
273 : }
274 : };
275 :
276 : /// This class represents an assumption made on an AddRec expression. Given an
277 : /// affine AddRec expression {a,+,b}, we assume that it has the nssw or nusw
278 : /// flags (defined below) in the first X iterations of the loop, where X is a
279 : /// SCEV expression returned by getPredicatedBackedgeTakenCount).
280 : ///
281 : /// Note that this does not imply that X is equal to the backedge taken
282 : /// count. This means that if we have a nusw predicate for i32 {0,+,1} with a
283 : /// predicated backedge taken count of X, we only guarantee that {0,+,1} has
284 : /// nusw in the first X iterations. {0,+,1} may still wrap in the loop if we
285 : /// have more than X iterations.
286 : class SCEVWrapPredicate final : public SCEVPredicate {
287 : public:
288 : /// Similar to SCEV::NoWrapFlags, but with slightly different semantics
289 : /// for FlagNUSW. The increment is considered to be signed, and a + b
290 : /// (where b is the increment) is considered to wrap if:
291 : /// zext(a + b) != zext(a) + sext(b)
292 : ///
293 : /// If Signed is a function that takes an n-bit tuple and maps to the
294 : /// integer domain as the tuples value interpreted as twos complement,
295 : /// and Unsigned a function that takes an n-bit tuple and maps to the
296 : /// integer domain as as the base two value of input tuple, then a + b
297 : /// has IncrementNUSW iff:
298 : ///
299 : /// 0 <= Unsigned(a) + Signed(b) < 2^n
300 : ///
301 : /// The IncrementNSSW flag has identical semantics with SCEV::FlagNSW.
302 : ///
303 : /// Note that the IncrementNUSW flag is not commutative: if base + inc
304 : /// has IncrementNUSW, then inc + base doesn't neccessarily have this
305 : /// property. The reason for this is that this is used for sign/zero
306 : /// extending affine AddRec SCEV expressions when a SCEVWrapPredicate is
307 : /// assumed. A {base,+,inc} expression is already non-commutative with
308 : /// regards to base and inc, since it is interpreted as:
309 : /// (((base + inc) + inc) + inc) ...
310 : enum IncrementWrapFlags {
311 : IncrementAnyWrap = 0, // No guarantee.
312 : IncrementNUSW = (1 << 0), // No unsigned with signed increment wrap.
313 : IncrementNSSW = (1 << 1), // No signed with signed increment wrap
314 : // (equivalent with SCEV::NSW)
315 : IncrementNoWrapMask = (1 << 2) - 1
316 : };
317 :
318 : /// Convenient IncrementWrapFlags manipulation methods.
319 : LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags
320 : clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags,
321 : SCEVWrapPredicate::IncrementWrapFlags OffFlags) {
322 : assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
323 : assert((OffFlags & IncrementNoWrapMask) == OffFlags &&
324 : "Invalid flags value!");
325 1676 : return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & ~OffFlags);
326 : }
327 :
328 : LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags
329 : maskFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, int Mask) {
330 : assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
331 : assert((Mask & IncrementNoWrapMask) == Mask && "Invalid mask value!");
332 :
333 : return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & Mask);
334 : }
335 :
336 : LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags
337 : setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags,
338 : SCEVWrapPredicate::IncrementWrapFlags OnFlags) {
339 : assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");
340 : assert((OnFlags & IncrementNoWrapMask) == OnFlags &&
341 : "Invalid flags value!");
342 :
343 211 : return (SCEVWrapPredicate::IncrementWrapFlags)(Flags | OnFlags);
344 : }
345 :
346 : /// Returns the set of SCEVWrapPredicate no wrap flags implied by a
347 : /// SCEVAddRecExpr.
348 : LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags
349 : getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE);
350 :
351 : private:
352 : const SCEVAddRecExpr *AR;
353 : IncrementWrapFlags Flags;
354 :
355 : public:
356 : explicit SCEVWrapPredicate(const FoldingSetNodeIDRef ID,
357 : const SCEVAddRecExpr *AR,
358 : IncrementWrapFlags Flags);
359 :
360 : /// Returns the set assumed no overflow flags.
361 0 : IncrementWrapFlags getFlags() const { return Flags; }
362 :
363 : /// Implementation of the SCEVPredicate interface
364 : const SCEV *getExpr() const override;
365 : bool implies(const SCEVPredicate *N) const override;
366 : void print(raw_ostream &OS, unsigned Depth = 0) const override;
367 : bool isAlwaysTrue() const override;
368 :
369 : /// Methods for support type inquiry through isa, cast, and dyn_cast:
370 : static bool classof(const SCEVPredicate *P) {
371 198 : return P->getKind() == P_Wrap;
372 : }
373 : };
374 :
375 : /// This class represents a composition of other SCEV predicates, and is the
376 : /// class that most clients will interact with. This is equivalent to a
377 : /// logical "AND" of all the predicates in the union.
378 : ///
379 : /// NB! Unlike other SCEVPredicate sub-classes this class does not live in the
380 : /// ScalarEvolution::Preds folding set. This is why the \c add function is sound.
381 : class SCEVUnionPredicate final : public SCEVPredicate {
382 : private:
383 : using PredicateMap =
384 : DenseMap<const SCEV *, SmallVector<const SCEVPredicate *, 4>>;
385 :
386 : /// Vector with references to all predicates in this union.
387 : SmallVector<const SCEVPredicate *, 16> Preds;
388 :
389 : /// Maps SCEVs to predicates for quick look-ups.
390 : PredicateMap SCEVToPreds;
391 :
392 : public:
393 : SCEVUnionPredicate();
394 :
395 : const SmallVectorImpl<const SCEVPredicate *> &getPredicates() const {
396 : return Preds;
397 : }
398 :
399 : /// Adds a predicate to this union.
400 : void add(const SCEVPredicate *N);
401 :
402 : /// Returns a reference to a vector containing all predicates which apply to
403 : /// \p Expr.
404 : ArrayRef<const SCEVPredicate *> getPredicatesForExpr(const SCEV *Expr);
405 :
406 : /// Implementation of the SCEVPredicate interface
407 : bool isAlwaysTrue() const override;
408 : bool implies(const SCEVPredicate *N) const override;
409 : void print(raw_ostream &OS, unsigned Depth) const override;
410 : const SCEV *getExpr() const override;
411 :
412 : /// We estimate the complexity of a union predicate as the size number of
413 : /// predicates in the union.
414 1061 : unsigned getComplexity() const override { return Preds.size(); }
415 :
416 : /// Methods for support type inquiry through isa, cast, and dyn_cast:
417 : static bool classof(const SCEVPredicate *P) {
418 6186 : return P->getKind() == P_Union;
419 : }
420 : };
421 :
422 : struct ExitLimitQuery {
423 : ExitLimitQuery(const Loop *L, BasicBlock *ExitingBlock, bool AllowPredicates)
424 : : L(L), ExitingBlock(ExitingBlock), AllowPredicates(AllowPredicates) {}
425 :
426 : const Loop *L;
427 : BasicBlock *ExitingBlock;
428 : bool AllowPredicates;
429 : };
430 :
431 : template <> struct DenseMapInfo<ExitLimitQuery> {
432 : static inline ExitLimitQuery getEmptyKey() {
433 : return ExitLimitQuery(nullptr, nullptr, true);
434 : }
435 :
436 : static inline ExitLimitQuery getTombstoneKey() {
437 : return ExitLimitQuery(nullptr, nullptr, false);
438 : }
439 :
440 : static unsigned getHashValue(ExitLimitQuery Val) {
441 : return hash_combine(hash_combine(Val.L, Val.ExitingBlock),
442 : Val.AllowPredicates);
443 : }
444 :
445 : static bool isEqual(ExitLimitQuery LHS, ExitLimitQuery RHS) {
446 : return LHS.L == RHS.L && LHS.ExitingBlock == RHS.ExitingBlock &&
447 : LHS.AllowPredicates == RHS.AllowPredicates;
448 : }
449 : };
450 :
451 : /// The main scalar evolution driver. Because client code (intentionally)
452 : /// can't do much with the SCEV objects directly, they must ask this class
453 : /// for services.
454 : class ScalarEvolution {
455 : public:
456 : /// An enum describing the relationship between a SCEV and a loop.
457 : enum LoopDisposition {
458 : LoopVariant, ///< The SCEV is loop-variant (unknown).
459 : LoopInvariant, ///< The SCEV is loop-invariant.
460 : LoopComputable ///< The SCEV varies predictably with the loop.
461 : };
462 :
463 : /// An enum describing the relationship between a SCEV and a basic block.
464 : enum BlockDisposition {
465 : DoesNotDominateBlock, ///< The SCEV does not dominate the block.
466 : DominatesBlock, ///< The SCEV dominates the block.
467 : ProperlyDominatesBlock ///< The SCEV properly dominates the block.
468 : };
469 :
470 : /// Convenient NoWrapFlags manipulation that hides enum casts and is
471 : /// visible in the ScalarEvolution name space.
472 : LLVM_NODISCARD static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags,
473 : int Mask) {
474 6750791 : return (SCEV::NoWrapFlags)(Flags & Mask);
475 : }
476 : LLVM_NODISCARD static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags,
477 : SCEV::NoWrapFlags OnFlags) {
478 4089666 : return (SCEV::NoWrapFlags)(Flags | OnFlags);
479 : }
480 : LLVM_NODISCARD static SCEV::NoWrapFlags
481 : clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags) {
482 31446 : return (SCEV::NoWrapFlags)(Flags & ~OffFlags);
483 : }
484 :
485 : ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC,
486 : DominatorTree &DT, LoopInfo &LI);
487 : ScalarEvolution(ScalarEvolution &&Arg);
488 : ~ScalarEvolution();
489 :
490 3252784 : LLVMContext &getContext() const { return F.getContext(); }
491 :
492 : /// Test if values of the given type are analyzable within the SCEV
493 : /// framework. This primarily includes integer types, and it can optionally
494 : /// include pointer types if the ScalarEvolution class has access to
495 : /// target-specific information.
496 : bool isSCEVable(Type *Ty) const;
497 :
498 : /// Return the size in bits of the specified type, for which isSCEVable must
499 : /// return true.
500 : uint64_t getTypeSizeInBits(Type *Ty) const;
501 :
502 : /// Return a type with the same bitwidth as the given type and which
503 : /// represents how SCEV will treat the given type, for which isSCEVable must
504 : /// return true. For pointer types, this is the pointer-sized integer type.
505 : Type *getEffectiveSCEVType(Type *Ty) const;
506 :
507 : // Returns a wider type among {Ty1, Ty2}.
508 : Type *getWiderType(Type *Ty1, Type *Ty2) const;
509 :
510 : /// Return true if the SCEV is a scAddRecExpr or it contains
511 : /// scAddRecExpr. The result will be cached in HasRecMap.
512 : bool containsAddRecurrence(const SCEV *S);
513 :
514 : /// Erase Value from ValueExprMap and ExprValueMap.
515 : void eraseValueFromMap(Value *V);
516 :
517 : /// Return a SCEV expression for the full generality of the specified
518 : /// expression.
519 : const SCEV *getSCEV(Value *V);
520 :
521 : const SCEV *getConstant(ConstantInt *V);
522 : const SCEV *getConstant(const APInt &Val);
523 : const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false);
524 : const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty);
525 : const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
526 : const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
527 : const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty);
528 : const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
529 : SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
530 : unsigned Depth = 0);
531 1881245 : const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS,
532 : SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
533 : unsigned Depth = 0) {
534 1881245 : SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
535 1881245 : return getAddExpr(Ops, Flags, Depth);
536 : }
537 : const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
538 : SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
539 : unsigned Depth = 0) {
540 : SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
541 : return getAddExpr(Ops, Flags, Depth);
542 : }
543 : const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
544 : SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
545 : unsigned Depth = 0);
546 1375347 : const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS,
547 : SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
548 : unsigned Depth = 0) {
549 1375347 : SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
550 1375347 : return getMulExpr(Ops, Flags, Depth);
551 : }
552 5150 : const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
553 : SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
554 : unsigned Depth = 0) {
555 5150 : SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
556 5150 : return getMulExpr(Ops, Flags, Depth);
557 : }
558 : const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS);
559 : const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS);
560 : const SCEV *getURemExpr(const SCEV *LHS, const SCEV *RHS);
561 : const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L,
562 : SCEV::NoWrapFlags Flags);
563 : const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
564 : const Loop *L, SCEV::NoWrapFlags Flags);
565 142 : const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands,
566 : const Loop *L, SCEV::NoWrapFlags Flags) {
567 : SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end());
568 142 : return getAddRecExpr(NewOp, L, Flags);
569 : }
570 :
571 : /// Checks if \p SymbolicPHI can be rewritten as an AddRecExpr under some
572 : /// Predicates. If successful return these <AddRecExpr, Predicates>;
573 : /// The function is intended to be called from PSCEV (the caller will decide
574 : /// whether to actually add the predicates and carry out the rewrites).
575 : Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
576 : createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI);
577 :
578 : /// Returns an expression for a GEP
579 : ///
580 : /// \p GEP The GEP. The indices contained in the GEP itself are ignored,
581 : /// instead we use IndexExprs.
582 : /// \p IndexExprs The expressions for the indices.
583 : const SCEV *getGEPExpr(GEPOperator *GEP,
584 : const SmallVectorImpl<const SCEV *> &IndexExprs);
585 : const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS);
586 : const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
587 : const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS);
588 : const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
589 : const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS);
590 : const SCEV *getSMinExpr(SmallVectorImpl<const SCEV *> &Operands);
591 : const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS);
592 : const SCEV *getUMinExpr(SmallVectorImpl<const SCEV *> &Operands);
593 : const SCEV *getUnknown(Value *V);
594 : const SCEV *getCouldNotCompute();
595 :
596 : /// Return a SCEV for the constant 0 of a specific type.
597 467364 : const SCEV *getZero(Type *Ty) { return getConstant(Ty, 0); }
598 :
599 : /// Return a SCEV for the constant 1 of a specific type.
600 82221 : const SCEV *getOne(Type *Ty) { return getConstant(Ty, 1); }
601 :
602 : /// Return an expression for sizeof AllocTy that is type IntTy
603 : const SCEV *getSizeOfExpr(Type *IntTy, Type *AllocTy);
604 :
605 : /// Return an expression for offsetof on the given field with type IntTy
606 : const SCEV *getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo);
607 :
608 : /// Return the SCEV object corresponding to -V.
609 : const SCEV *getNegativeSCEV(const SCEV *V,
610 : SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap);
611 :
612 : /// Return the SCEV object corresponding to ~V.
613 : const SCEV *getNotSCEV(const SCEV *V);
614 :
615 : /// Return LHS-RHS. Minus is represented in SCEV as A+B*-1.
616 : const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
617 : SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
618 : unsigned Depth = 0);
619 :
620 : /// Return a SCEV corresponding to a conversion of the input value to the
621 : /// specified type. If the type must be extended, it is zero extended.
622 : const SCEV *getTruncateOrZeroExtend(const SCEV *V, Type *Ty);
623 :
624 : /// Return a SCEV corresponding to a conversion of the input value to the
625 : /// specified type. If the type must be extended, it is sign extended.
626 : const SCEV *getTruncateOrSignExtend(const SCEV *V, Type *Ty);
627 :
628 : /// Return a SCEV corresponding to a conversion of the input value to the
629 : /// specified type. If the type must be extended, it is zero extended. The
630 : /// conversion must not be narrowing.
631 : const SCEV *getNoopOrZeroExtend(const SCEV *V, Type *Ty);
632 :
633 : /// Return a SCEV corresponding to a conversion of the input value to the
634 : /// specified type. If the type must be extended, it is sign extended. The
635 : /// conversion must not be narrowing.
636 : const SCEV *getNoopOrSignExtend(const SCEV *V, Type *Ty);
637 :
638 : /// Return a SCEV corresponding to a conversion of the input value to the
639 : /// specified type. If the type must be extended, it is extended with
640 : /// unspecified bits. The conversion must not be narrowing.
641 : const SCEV *getNoopOrAnyExtend(const SCEV *V, Type *Ty);
642 :
643 : /// Return a SCEV corresponding to a conversion of the input value to the
644 : /// specified type. The conversion must not be widening.
645 : const SCEV *getTruncateOrNoop(const SCEV *V, Type *Ty);
646 :
647 : /// Promote the operands to the wider of the types using zero-extension, and
648 : /// then perform a umax operation with them.
649 : const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS);
650 :
651 : /// Promote the operands to the wider of the types using zero-extension, and
652 : /// then perform a umin operation with them.
653 : const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS);
654 :
655 : /// Promote the operands to the wider of the types using zero-extension, and
656 : /// then perform a umin operation with them. N-ary function.
657 : const SCEV *getUMinFromMismatchedTypes(SmallVectorImpl<const SCEV *> &Ops);
658 :
659 : /// Transitively follow the chain of pointer-type operands until reaching a
660 : /// SCEV that does not have a single pointer operand. This returns a
661 : /// SCEVUnknown pointer for well-formed pointer-type expressions, but corner
662 : /// cases do exist.
663 : const SCEV *getPointerBase(const SCEV *V);
664 :
665 : /// Return a SCEV expression for the specified value at the specified scope
666 : /// in the program. The L value specifies a loop nest to evaluate the
667 : /// expression at, where null is the top-level or a specified loop is
668 : /// immediately inside of the loop.
669 : ///
670 : /// This method can be used to compute the exit value for a variable defined
671 : /// in a loop by querying what the value will hold in the parent loop.
672 : ///
673 : /// In the case that a relevant loop exit value cannot be computed, the
674 : /// original value V is returned.
675 : const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L);
676 :
677 : /// This is a convenience function which does getSCEVAtScope(getSCEV(V), L).
678 : const SCEV *getSCEVAtScope(Value *V, const Loop *L);
679 :
680 : /// Test whether entry to the loop is protected by a conditional between LHS
681 : /// and RHS. This is used to help avoid max expressions in loop trip
682 : /// counts, and to eliminate casts.
683 : bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
684 : const SCEV *LHS, const SCEV *RHS);
685 :
686 : /// Test whether the backedge of the loop is protected by a conditional
687 : /// between LHS and RHS. This is used to eliminate casts.
688 : bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
689 : const SCEV *LHS, const SCEV *RHS);
690 :
691 : /// Returns the maximum trip count of the loop if it is a single-exit
692 : /// loop and we can compute a small maximum for that loop.
693 : ///
694 : /// Implemented in terms of the \c getSmallConstantTripCount overload with
695 : /// the single exiting block passed to it. See that routine for details.
696 : unsigned getSmallConstantTripCount(const Loop *L);
697 :
698 : /// Returns the maximum trip count of this loop as a normal unsigned
699 : /// value. Returns 0 if the trip count is unknown or not constant. This
700 : /// "trip count" assumes that control exits via ExitingBlock. More
701 : /// precisely, it is the number of times that control may reach ExitingBlock
702 : /// before taking the branch. For loops with multiple exits, it may not be
703 : /// the number times that the loop header executes if the loop exits
704 : /// prematurely via another branch.
705 : unsigned getSmallConstantTripCount(const Loop *L, BasicBlock *ExitingBlock);
706 :
707 : /// Returns the upper bound of the loop trip count as a normal unsigned
708 : /// value.
709 : /// Returns 0 if the trip count is unknown or not constant.
710 : unsigned getSmallConstantMaxTripCount(const Loop *L);
711 :
712 : /// Returns the largest constant divisor of the trip count of the
713 : /// loop if it is a single-exit loop and we can compute a small maximum for
714 : /// that loop.
715 : ///
716 : /// Implemented in terms of the \c getSmallConstantTripMultiple overload with
717 : /// the single exiting block passed to it. See that routine for details.
718 : unsigned getSmallConstantTripMultiple(const Loop *L);
719 :
720 : /// Returns the largest constant divisor of the trip count of this loop as a
721 : /// normal unsigned value, if possible. This means that the actual trip
722 : /// count is always a multiple of the returned value (don't forget the trip
723 : /// count could very well be zero as well!). As explained in the comments
724 : /// for getSmallConstantTripCount, this assumes that control exits the loop
725 : /// via ExitingBlock.
726 : unsigned getSmallConstantTripMultiple(const Loop *L,
727 : BasicBlock *ExitingBlock);
728 :
729 : /// Get the expression for the number of loop iterations for which this loop
730 : /// is guaranteed not to exit via ExitingBlock. Otherwise return
731 : /// SCEVCouldNotCompute.
732 : const SCEV *getExitCount(const Loop *L, BasicBlock *ExitingBlock);
733 :
734 : /// If the specified loop has a predictable backedge-taken count, return it,
735 : /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count is
736 : /// the number of times the loop header will be branched to from within the
737 : /// loop, assuming there are no abnormal exists like exception throws. This is
738 : /// one less than the trip count of the loop, since it doesn't count the first
739 : /// iteration, when the header is branched to from outside the loop.
740 : ///
741 : /// Note that it is not valid to call this method on a loop without a
742 : /// loop-invariant backedge-taken count (see
743 : /// hasLoopInvariantBackedgeTakenCount).
744 : const SCEV *getBackedgeTakenCount(const Loop *L);
745 :
746 : /// Similar to getBackedgeTakenCount, except it will add a set of
747 : /// SCEV predicates to Predicates that are required to be true in order for
748 : /// the answer to be correct. Predicates can be checked with run-time
749 : /// checks and can be used to perform loop versioning.
750 : const SCEV *getPredicatedBackedgeTakenCount(const Loop *L,
751 : SCEVUnionPredicate &Predicates);
752 :
753 : /// When successful, this returns a SCEVConstant that is greater than or equal
754 : /// to (i.e. a "conservative over-approximation") of the value returend by
755 : /// getBackedgeTakenCount. If such a value cannot be computed, it returns the
756 : /// SCEVCouldNotCompute object.
757 : const SCEV *getMaxBackedgeTakenCount(const Loop *L);
758 :
759 : /// Return true if the backedge taken count is either the value returned by
760 : /// getMaxBackedgeTakenCount or zero.
761 : bool isBackedgeTakenCountMaxOrZero(const Loop *L);
762 :
763 : /// Return true if the specified loop has an analyzable loop-invariant
764 : /// backedge-taken count.
765 : bool hasLoopInvariantBackedgeTakenCount(const Loop *L);
766 :
767 : /// This method should be called by the client when it has changed a loop in
768 : /// a way that may effect ScalarEvolution's ability to compute a trip count,
769 : /// or if the loop is deleted. This call is potentially expensive for large
770 : /// loop bodies.
771 : void forgetLoop(const Loop *L);
772 :
773 : // This method invokes forgetLoop for the outermost loop of the given loop
774 : // \p L, making ScalarEvolution forget about all this subtree. This needs to
775 : // be done whenever we make a transform that may affect the parameters of the
776 : // outer loop, such as exit counts for branches.
777 : void forgetTopmostLoop(const Loop *L);
778 :
779 : /// This method should be called by the client when it has changed a value
780 : /// in a way that may effect its value, or which may disconnect it from a
781 : /// def-use chain linking it to a loop.
782 : void forgetValue(Value *V);
783 :
784 : /// Called when the client has changed the disposition of values in
785 : /// this loop.
786 : ///
787 : /// We don't have a way to invalidate per-loop dispositions. Clear and
788 : /// recompute is simpler.
789 2853 : void forgetLoopDispositions(const Loop *L) { LoopDispositions.clear(); }
790 :
791 : /// Determine the minimum number of zero bits that S is guaranteed to end in
792 : /// (at every loop iteration). It is, at the same time, the minimum number
793 : /// of times S is divisible by 2. For example, given {4,+,8} it returns 2.
794 : /// If S is guaranteed to be 0, it returns the bitwidth of S.
795 : uint32_t GetMinTrailingZeros(const SCEV *S);
796 :
797 : /// Determine the unsigned range for a particular SCEV.
798 : /// NOTE: This returns a copy of the reference returned by getRangeRef.
799 2527 : ConstantRange getUnsignedRange(const SCEV *S) {
800 3339101 : return getRangeRef(S, HINT_RANGE_UNSIGNED);
801 : }
802 :
803 : /// Determine the min of the unsigned range for a particular SCEV.
804 : APInt getUnsignedRangeMin(const SCEV *S) {
805 15211 : return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMin();
806 : }
807 :
808 : /// Determine the max of the unsigned range for a particular SCEV.
809 3474 : APInt getUnsignedRangeMax(const SCEV *S) {
810 362350 : return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMax();
811 : }
812 :
813 : /// Determine the signed range for a particular SCEV.
814 : /// NOTE: This returns a copy of the reference returned by getRangeRef.
815 426 : ConstantRange getSignedRange(const SCEV *S) {
816 2930869 : return getRangeRef(S, HINT_RANGE_SIGNED);
817 : }
818 :
819 : /// Determine the min of the signed range for a particular SCEV.
820 12936 : APInt getSignedRangeMin(const SCEV *S) {
821 2511553 : return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMin();
822 : }
823 :
824 : /// Determine the max of the signed range for a particular SCEV.
825 : APInt getSignedRangeMax(const SCEV *S) {
826 198457 : return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMax();
827 : }
828 :
829 : /// Test if the given expression is known to be negative.
830 : bool isKnownNegative(const SCEV *S);
831 :
832 : /// Test if the given expression is known to be positive.
833 : bool isKnownPositive(const SCEV *S);
834 :
835 : /// Test if the given expression is known to be non-negative.
836 : bool isKnownNonNegative(const SCEV *S);
837 :
838 : /// Test if the given expression is known to be non-positive.
839 : bool isKnownNonPositive(const SCEV *S);
840 :
841 : /// Test if the given expression is known to be non-zero.
842 : bool isKnownNonZero(const SCEV *S);
843 :
844 : /// Splits SCEV expression \p S into two SCEVs. One of them is obtained from
845 : /// \p S by substitution of all AddRec sub-expression related to loop \p L
846 : /// with initial value of that SCEV. The second is obtained from \p S by
847 : /// substitution of all AddRec sub-expressions related to loop \p L with post
848 : /// increment of this AddRec in the loop \p L. In both cases all other AddRec
849 : /// sub-expressions (not related to \p L) remain the same.
850 : /// If the \p S contains non-invariant unknown SCEV the function returns
851 : /// CouldNotCompute SCEV in both values of std::pair.
852 : /// For example, for SCEV S={0, +, 1}<L1> + {0, +, 1}<L2> and loop L=L1
853 : /// the function returns pair:
854 : /// first = {0, +, 1}<L2>
855 : /// second = {1, +, 1}<L1> + {0, +, 1}<L2>
856 : /// We can see that for the first AddRec sub-expression it was replaced with
857 : /// 0 (initial value) for the first element and to {1, +, 1}<L1> (post
858 : /// increment value) for the second one. In both cases AddRec expression
859 : /// related to L2 remains the same.
860 : std::pair<const SCEV *, const SCEV *> SplitIntoInitAndPostInc(const Loop *L,
861 : const SCEV *S);
862 :
863 : /// We'd like to check the predicate on every iteration of the most dominated
864 : /// loop between loops used in LHS and RHS.
865 : /// To do this we use the following list of steps:
866 : /// 1. Collect set S all loops on which either LHS or RHS depend.
867 : /// 2. If S is non-empty
868 : /// a. Let PD be the element of S which is dominated by all other elements.
869 : /// b. Let E(LHS) be value of LHS on entry of PD.
870 : /// To get E(LHS), we should just take LHS and replace all AddRecs that are
871 : /// attached to PD on with their entry values.
872 : /// Define E(RHS) in the same way.
873 : /// c. Let B(LHS) be value of L on backedge of PD.
874 : /// To get B(LHS), we should just take LHS and replace all AddRecs that are
875 : /// attached to PD on with their backedge values.
876 : /// Define B(RHS) in the same way.
877 : /// d. Note that E(LHS) and E(RHS) are automatically available on entry of PD,
878 : /// so we can assert on that.
879 : /// e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) &&
880 : /// isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS))
881 : bool isKnownViaInduction(ICmpInst::Predicate Pred, const SCEV *LHS,
882 : const SCEV *RHS);
883 :
884 : /// Test if the given expression is known to satisfy the condition described
885 : /// by Pred, LHS, and RHS.
886 : bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS,
887 : const SCEV *RHS);
888 :
889 : /// Test if the condition described by Pred, LHS, RHS is known to be true on
890 : /// every iteration of the loop of the recurrency LHS.
891 : bool isKnownOnEveryIteration(ICmpInst::Predicate Pred,
892 : const SCEVAddRecExpr *LHS, const SCEV *RHS);
893 :
894 : /// Return true if, for all loop invariant X, the predicate "LHS `Pred` X"
895 : /// is monotonically increasing or decreasing. In the former case set
896 : /// `Increasing` to true and in the latter case set `Increasing` to false.
897 : ///
898 : /// A predicate is said to be monotonically increasing if may go from being
899 : /// false to being true as the loop iterates, but never the other way
900 : /// around. A predicate is said to be monotonically decreasing if may go
901 : /// from being true to being false as the loop iterates, but never the other
902 : /// way around.
903 : bool isMonotonicPredicate(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred,
904 : bool &Increasing);
905 :
906 : /// Return true if the result of the predicate LHS `Pred` RHS is loop
907 : /// invariant with respect to L. Set InvariantPred, InvariantLHS and
908 : /// InvariantLHS so that InvariantLHS `InvariantPred` InvariantRHS is the
909 : /// loop invariant form of LHS `Pred` RHS.
910 : bool isLoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS,
911 : const SCEV *RHS, const Loop *L,
912 : ICmpInst::Predicate &InvariantPred,
913 : const SCEV *&InvariantLHS,
914 : const SCEV *&InvariantRHS);
915 :
916 : /// Simplify LHS and RHS in a comparison with predicate Pred. Return true
917 : /// iff any changes were made. If the operands are provably equal or
918 : /// unequal, LHS and RHS are set to the same value and Pred is set to either
919 : /// ICMP_EQ or ICMP_NE.
920 : bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS,
921 : const SCEV *&RHS, unsigned Depth = 0);
922 :
923 : /// Return the "disposition" of the given SCEV with respect to the given
924 : /// loop.
925 : LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L);
926 :
927 : /// Return true if the value of the given SCEV is unchanging in the
928 : /// specified loop.
929 : bool isLoopInvariant(const SCEV *S, const Loop *L);
930 :
931 : /// Determine if the SCEV can be evaluated at loop's entry. It is true if it
932 : /// doesn't depend on a SCEVUnknown of an instruction which is dominated by
933 : /// the header of loop L.
934 : bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L);
935 :
936 : /// Return true if the given SCEV changes value in a known way in the
937 : /// specified loop. This property being true implies that the value is
938 : /// variant in the loop AND that we can emit an expression to compute the
939 : /// value of the expression at any particular loop iteration.
940 : bool hasComputableLoopEvolution(const SCEV *S, const Loop *L);
941 :
942 : /// Return the "disposition" of the given SCEV with respect to the given
943 : /// block.
944 : BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB);
945 :
946 : /// Return true if elements that makes up the given SCEV dominate the
947 : /// specified basic block.
948 : bool dominates(const SCEV *S, const BasicBlock *BB);
949 :
950 : /// Return true if elements that makes up the given SCEV properly dominate
951 : /// the specified basic block.
952 : bool properlyDominates(const SCEV *S, const BasicBlock *BB);
953 :
954 : /// Test whether the given SCEV has Op as a direct or indirect operand.
955 : bool hasOperand(const SCEV *S, const SCEV *Op) const;
956 :
957 : /// Return the size of an element read or written by Inst.
958 : const SCEV *getElementSize(Instruction *Inst);
959 :
960 : /// Compute the array dimensions Sizes from the set of Terms extracted from
961 : /// the memory access function of this SCEVAddRecExpr (second step of
962 : /// delinearization).
963 : void findArrayDimensions(SmallVectorImpl<const SCEV *> &Terms,
964 : SmallVectorImpl<const SCEV *> &Sizes,
965 : const SCEV *ElementSize);
966 :
967 : void print(raw_ostream &OS) const;
968 : void verify() const;
969 : bool invalidate(Function &F, const PreservedAnalyses &PA,
970 : FunctionAnalysisManager::Invalidator &Inv);
971 :
972 : /// Collect parametric terms occurring in step expressions (first step of
973 : /// delinearization).
974 : void collectParametricTerms(const SCEV *Expr,
975 : SmallVectorImpl<const SCEV *> &Terms);
976 :
977 : /// Return in Subscripts the access functions for each dimension in Sizes
978 : /// (third step of delinearization).
979 : void computeAccessFunctions(const SCEV *Expr,
980 : SmallVectorImpl<const SCEV *> &Subscripts,
981 : SmallVectorImpl<const SCEV *> &Sizes);
982 :
983 : /// Split this SCEVAddRecExpr into two vectors of SCEVs representing the
984 : /// subscripts and sizes of an array access.
985 : ///
986 : /// The delinearization is a 3 step process: the first two steps compute the
987 : /// sizes of each subscript and the third step computes the access functions
988 : /// for the delinearized array:
989 : ///
990 : /// 1. Find the terms in the step functions
991 : /// 2. Compute the array size
992 : /// 3. Compute the access function: divide the SCEV by the array size
993 : /// starting with the innermost dimensions found in step 2. The Quotient
994 : /// is the SCEV to be divided in the next step of the recursion. The
995 : /// Remainder is the subscript of the innermost dimension. Loop over all
996 : /// array dimensions computed in step 2.
997 : ///
998 : /// To compute a uniform array size for several memory accesses to the same
999 : /// object, one can collect in step 1 all the step terms for all the memory
1000 : /// accesses, and compute in step 2 a unique array shape. This guarantees
1001 : /// that the array shape will be the same across all memory accesses.
1002 : ///
1003 : /// FIXME: We could derive the result of steps 1 and 2 from a description of
1004 : /// the array shape given in metadata.
1005 : ///
1006 : /// Example:
1007 : ///
1008 : /// A[][n][m]
1009 : ///
1010 : /// for i
1011 : /// for j
1012 : /// for k
1013 : /// A[j+k][2i][5i] =
1014 : ///
1015 : /// The initial SCEV:
1016 : ///
1017 : /// A[{{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k]
1018 : ///
1019 : /// 1. Find the different terms in the step functions:
1020 : /// -> [2*m, 5, n*m, n*m]
1021 : ///
1022 : /// 2. Compute the array size: sort and unique them
1023 : /// -> [n*m, 2*m, 5]
1024 : /// find the GCD of all the terms = 1
1025 : /// divide by the GCD and erase constant terms
1026 : /// -> [n*m, 2*m]
1027 : /// GCD = m
1028 : /// divide by GCD -> [n, 2]
1029 : /// remove constant terms
1030 : /// -> [n]
1031 : /// size of the array is A[unknown][n][m]
1032 : ///
1033 : /// 3. Compute the access function
1034 : /// a. Divide {{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k by the innermost size m
1035 : /// Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k
1036 : /// Remainder: {{{0,+,5}_i, +, 0}_j, +, 0}_k
1037 : /// The remainder is the subscript of the innermost array dimension: [5i].
1038 : ///
1039 : /// b. Divide Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k by next outer size n
1040 : /// Quotient: {{{0,+,0}_i, +, 1}_j, +, 1}_k
1041 : /// Remainder: {{{0,+,2}_i, +, 0}_j, +, 0}_k
1042 : /// The Remainder is the subscript of the next array dimension: [2i].
1043 : ///
1044 : /// The subscript of the outermost dimension is the Quotient: [j+k].
1045 : ///
1046 : /// Overall, we have: A[][n][m], and the access function: A[j+k][2i][5i].
1047 : void delinearize(const SCEV *Expr, SmallVectorImpl<const SCEV *> &Subscripts,
1048 : SmallVectorImpl<const SCEV *> &Sizes,
1049 : const SCEV *ElementSize);
1050 :
1051 : /// Return the DataLayout associated with the module this SCEV instance is
1052 : /// operating on.
1053 0 : const DataLayout &getDataLayout() const {
1054 5394161 : return F.getParent()->getDataLayout();
1055 : }
1056 :
1057 : const SCEVPredicate *getEqualPredicate(const SCEV *LHS, const SCEV *RHS);
1058 :
1059 : const SCEVPredicate *
1060 : getWrapPredicate(const SCEVAddRecExpr *AR,
1061 : SCEVWrapPredicate::IncrementWrapFlags AddedFlags);
1062 :
1063 : /// Re-writes the SCEV according to the Predicates in \p A.
1064 : const SCEV *rewriteUsingPredicate(const SCEV *S, const Loop *L,
1065 : SCEVUnionPredicate &A);
1066 : /// Tries to convert the \p S expression to an AddRec expression,
1067 : /// adding additional predicates to \p Preds as required.
1068 : const SCEVAddRecExpr *convertSCEVToAddRecWithPredicates(
1069 : const SCEV *S, const Loop *L,
1070 : SmallPtrSetImpl<const SCEVPredicate *> &Preds);
1071 :
1072 : private:
1073 : /// A CallbackVH to arrange for ScalarEvolution to be notified whenever a
1074 : /// Value is deleted.
1075 12414056 : class SCEVCallbackVH final : public CallbackVH {
1076 : ScalarEvolution *SE;
1077 :
1078 : void deleted() override;
1079 : void allUsesReplacedWith(Value *New) override;
1080 :
1081 : public:
1082 : SCEVCallbackVH(Value *V, ScalarEvolution *SE = nullptr);
1083 : };
1084 :
1085 : friend class SCEVCallbackVH;
1086 : friend class SCEVExpander;
1087 : friend class SCEVUnknown;
1088 :
1089 : /// The function we are analyzing.
1090 : Function &F;
1091 :
1092 : /// Does the module have any calls to the llvm.experimental.guard intrinsic
1093 : /// at all? If this is false, we avoid doing work that will only help if
1094 : /// thare are guards present in the IR.
1095 : bool HasGuards;
1096 :
1097 : /// The target library information for the target we are targeting.
1098 : TargetLibraryInfo &TLI;
1099 :
1100 : /// The tracker for \@llvm.assume intrinsics in this function.
1101 : AssumptionCache &AC;
1102 :
1103 : /// The dominator tree.
1104 : DominatorTree &DT;
1105 :
1106 : /// The loop information for the function we are currently analyzing.
1107 : LoopInfo &LI;
1108 :
1109 : /// This SCEV is used to represent unknown trip counts and things.
1110 : std::unique_ptr<SCEVCouldNotCompute> CouldNotCompute;
1111 :
1112 : /// The type for HasRecMap.
1113 : using HasRecMapType = DenseMap<const SCEV *, bool>;
1114 :
1115 : /// This is a cache to record whether a SCEV contains any scAddRecExpr.
1116 : HasRecMapType HasRecMap;
1117 :
1118 : /// The type for ExprValueMap.
1119 : using ValueOffsetPair = std::pair<Value *, ConstantInt *>;
1120 : using ExprValueMapType = DenseMap<const SCEV *, SetVector<ValueOffsetPair>>;
1121 :
1122 : /// ExprValueMap -- This map records the original values from which
1123 : /// the SCEV expr is generated from.
1124 : ///
1125 : /// We want to represent the mapping as SCEV -> ValueOffsetPair instead
1126 : /// of SCEV -> Value:
1127 : /// Suppose we know S1 expands to V1, and
1128 : /// S1 = S2 + C_a
1129 : /// S3 = S2 + C_b
1130 : /// where C_a and C_b are different SCEVConstants. Then we'd like to
1131 : /// expand S3 as V1 - C_a + C_b instead of expanding S2 literally.
1132 : /// It is helpful when S2 is a complex SCEV expr.
1133 : ///
1134 : /// In order to do that, we represent ExprValueMap as a mapping from
1135 : /// SCEV to ValueOffsetPair. We will save both S1->{V1, 0} and
1136 : /// S2->{V1, C_a} into the map when we create SCEV for V1. When S3
1137 : /// is expanded, it will first expand S2 to V1 - C_a because of
1138 : /// S2->{V1, C_a} in the map, then expand S3 to V1 - C_a + C_b.
1139 : ///
1140 : /// Note: S->{V, Offset} in the ExprValueMap means S can be expanded
1141 : /// to V - Offset.
1142 : ExprValueMapType ExprValueMap;
1143 :
1144 : /// The type for ValueExprMap.
1145 : using ValueExprMapType =
1146 : DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *>>;
1147 :
1148 : /// This is a cache of the values we have analyzed so far.
1149 : ValueExprMapType ValueExprMap;
1150 :
1151 : /// Mark predicate values currently being processed by isImpliedCond.
1152 : SmallPtrSet<Value *, 6> PendingLoopPredicates;
1153 :
1154 : /// Mark SCEVUnknown Phis currently being processed by getRangeRef.
1155 : SmallPtrSet<const PHINode *, 6> PendingPhiRanges;
1156 :
1157 : // Mark SCEVUnknown Phis currently being processed by isImpliedViaMerge.
1158 : SmallPtrSet<const PHINode *, 6> PendingMerges;
1159 :
1160 : /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of
1161 : /// conditions dominating the backedge of a loop.
1162 : bool WalkingBEDominatingConds = false;
1163 :
1164 : /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a
1165 : /// predicate by splitting it into a set of independent predicates.
1166 : bool ProvingSplitPredicate = false;
1167 :
1168 : /// Memoized values for the GetMinTrailingZeros
1169 : DenseMap<const SCEV *, uint32_t> MinTrailingZerosCache;
1170 :
1171 : /// Return the Value set from which the SCEV expr is generated.
1172 : SetVector<ValueOffsetPair> *getSCEVValues(const SCEV *S);
1173 :
1174 : /// Private helper method for the GetMinTrailingZeros method
1175 : uint32_t GetMinTrailingZerosImpl(const SCEV *S);
1176 :
1177 : /// Information about the number of loop iterations for which a loop exit's
1178 : /// branch condition evaluates to the not-taken path. This is a temporary
1179 : /// pair of exact and max expressions that are eventually summarized in
1180 : /// ExitNotTakenInfo and BackedgeTakenInfo.
1181 187856 : struct ExitLimit {
1182 : const SCEV *ExactNotTaken; // The exit is not taken exactly this many times
1183 : const SCEV *MaxNotTaken; // The exit is not taken at most this many times
1184 :
1185 : // Not taken either exactly MaxNotTaken or zero times
1186 : bool MaxOrZero = false;
1187 :
1188 : /// A set of predicate guards for this ExitLimit. The result is only valid
1189 : /// if all of the predicates in \c Predicates evaluate to 'true' at
1190 : /// run-time.
1191 : SmallPtrSet<const SCEVPredicate *, 4> Predicates;
1192 :
1193 : void addPredicate(const SCEVPredicate *P) {
1194 : assert(!isa<SCEVUnionPredicate>(P) && "Only add leaf predicates here!");
1195 13 : Predicates.insert(P);
1196 : }
1197 :
1198 : /*implicit*/ ExitLimit(const SCEV *E);
1199 :
1200 : ExitLimit(
1201 : const SCEV *E, const SCEV *M, bool MaxOrZero,
1202 : ArrayRef<const SmallPtrSetImpl<const SCEVPredicate *> *> PredSetList);
1203 :
1204 : ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero,
1205 : const SmallPtrSetImpl<const SCEVPredicate *> &PredSet);
1206 :
1207 : ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero);
1208 :
1209 : /// Test whether this ExitLimit contains any computed information, or
1210 : /// whether it's all SCEVCouldNotCompute values.
1211 24406 : bool hasAnyInfo() const {
1212 39507 : return !isa<SCEVCouldNotCompute>(ExactNotTaken) ||
1213 15101 : !isa<SCEVCouldNotCompute>(MaxNotTaken);
1214 : }
1215 :
1216 : bool hasOperand(const SCEV *S) const;
1217 :
1218 : /// Test whether this ExitLimit contains all information.
1219 : bool hasFullInfo() const {
1220 29897 : return !isa<SCEVCouldNotCompute>(ExactNotTaken);
1221 : }
1222 : };
1223 :
1224 : /// Information about the number of times a particular loop exit may be
1225 : /// reached before exiting the loop.
1226 51961 : struct ExitNotTakenInfo {
1227 : PoisoningVH<BasicBlock> ExitingBlock;
1228 : const SCEV *ExactNotTaken;
1229 : std::unique_ptr<SCEVUnionPredicate> Predicate;
1230 :
1231 : explicit ExitNotTakenInfo(PoisoningVH<BasicBlock> ExitingBlock,
1232 : const SCEV *ExactNotTaken,
1233 : std::unique_ptr<SCEVUnionPredicate> Predicate)
1234 : : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken),
1235 : Predicate(std::move(Predicate)) {}
1236 :
1237 : bool hasAlwaysTruePredicate() const {
1238 31659 : return !Predicate || Predicate->isAlwaysTrue();
1239 : }
1240 : };
1241 :
1242 : /// Information about the backedge-taken count of a loop. This currently
1243 : /// includes an exact count and a maximum count.
1244 : ///
1245 476210 : class BackedgeTakenInfo {
1246 : /// A list of computable exits and their not-taken counts. Loops almost
1247 : /// never have more than one computable exit.
1248 : SmallVector<ExitNotTakenInfo, 1> ExitNotTaken;
1249 :
1250 : /// The pointer part of \c MaxAndComplete is an expression indicating the
1251 : /// least maximum backedge-taken count of the loop that is known, or a
1252 : /// SCEVCouldNotCompute. This expression is only valid if the predicates
1253 : /// associated with all loop exits are true.
1254 : ///
1255 : /// The integer part of \c MaxAndComplete is a boolean indicating if \c
1256 : /// ExitNotTaken has an element for every exiting block in the loop.
1257 : PointerIntPair<const SCEV *, 1> MaxAndComplete;
1258 :
1259 : /// True iff the backedge is taken either exactly Max or zero times.
1260 : bool MaxOrZero = false;
1261 :
1262 : /// \name Helper projection functions on \c MaxAndComplete.
1263 : /// @{
1264 54946 : bool isComplete() const { return MaxAndComplete.getInt(); }
1265 600565 : const SCEV *getMax() const { return MaxAndComplete.getPointer(); }
1266 : /// @}
1267 :
1268 : public:
1269 797706 : BackedgeTakenInfo() : MaxAndComplete(nullptr, 0) {}
1270 824396 : BackedgeTakenInfo(BackedgeTakenInfo &&) = default;
1271 : BackedgeTakenInfo &operator=(BackedgeTakenInfo &&) = default;
1272 :
1273 : using EdgeExitInfo = std::pair<BasicBlock *, ExitLimit>;
1274 :
1275 : /// Initialize BackedgeTakenInfo from a list of exact exit counts.
1276 : BackedgeTakenInfo(SmallVectorImpl<EdgeExitInfo> &&ExitCounts, bool Complete,
1277 : const SCEV *MaxCount, bool MaxOrZero);
1278 :
1279 : /// Test whether this BackedgeTakenInfo contains any computed information,
1280 : /// or whether it's all SCEVCouldNotCompute values.
1281 : bool hasAnyInfo() const {
1282 33496 : return !ExitNotTaken.empty() || !isa<SCEVCouldNotCompute>(getMax());
1283 : }
1284 :
1285 : /// Test whether this BackedgeTakenInfo contains complete information.
1286 : bool hasFullInfo() const { return isComplete(); }
1287 :
1288 : /// Return an expression indicating the exact *backedge-taken*
1289 : /// count of the loop if it is known or SCEVCouldNotCompute
1290 : /// otherwise. If execution makes it to the backedge on every
1291 : /// iteration (i.e. there are no abnormal exists like exception
1292 : /// throws and thread exits) then this is the number of times the
1293 : /// loop header will execute minus one.
1294 : ///
1295 : /// If the SCEV predicate associated with the answer can be different
1296 : /// from AlwaysTrue, we must add a (non null) Predicates argument.
1297 : /// The SCEV predicate associated with the answer will be added to
1298 : /// Predicates. A run-time check needs to be emitted for the SCEV
1299 : /// predicate in order for the answer to be valid.
1300 : ///
1301 : /// Note that we should always know if we need to pass a predicate
1302 : /// argument or not from the way the ExitCounts vector was computed.
1303 : /// If we allowed SCEV predicates to be generated when populating this
1304 : /// vector, this information can contain them and therefore a
1305 : /// SCEVPredicate argument should be added to getExact.
1306 : const SCEV *getExact(const Loop *L, ScalarEvolution *SE,
1307 : SCEVUnionPredicate *Predicates = nullptr) const;
1308 :
1309 : /// Return the number of times this loop exit may fall through to the back
1310 : /// edge, or SCEVCouldNotCompute. The loop is guaranteed not to exit via
1311 : /// this block before this number of iterations, but may exit via another
1312 : /// block.
1313 : const SCEV *getExact(BasicBlock *ExitingBlock, ScalarEvolution *SE) const;
1314 :
1315 : /// Get the max backedge taken count for the loop.
1316 : const SCEV *getMax(ScalarEvolution *SE) const;
1317 :
1318 : /// Return true if the number of times this backedge is taken is either the
1319 : /// value returned by getMax or zero.
1320 : bool isMaxOrZero(ScalarEvolution *SE) const;
1321 :
1322 : /// Return true if any backedge taken count expressions refer to the given
1323 : /// subexpression.
1324 : bool hasOperand(const SCEV *S, ScalarEvolution *SE) const;
1325 :
1326 : /// Invalidate this result and free associated memory.
1327 : void clear();
1328 : };
1329 :
1330 : /// Cache the backedge-taken count of the loops for this function as they
1331 : /// are computed.
1332 : DenseMap<const Loop *, BackedgeTakenInfo> BackedgeTakenCounts;
1333 :
1334 : /// Cache the predicated backedge-taken count of the loops for this
1335 : /// function as they are computed.
1336 : DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts;
1337 :
1338 : /// This map contains entries for all of the PHI instructions that we
1339 : /// attempt to compute constant evolutions for. This allows us to avoid
1340 : /// potentially expensive recomputation of these properties. An instruction
1341 : /// maps to null if we are unable to compute its exit value.
1342 : DenseMap<PHINode *, Constant *> ConstantEvolutionLoopExitValue;
1343 :
1344 : /// This map contains entries for all the expressions that we attempt to
1345 : /// compute getSCEVAtScope information for, which can be expensive in
1346 : /// extreme cases.
1347 : DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1348 : ValuesAtScopes;
1349 :
1350 : /// Memoized computeLoopDisposition results.
1351 : DenseMap<const SCEV *,
1352 : SmallVector<PointerIntPair<const Loop *, 2, LoopDisposition>, 2>>
1353 : LoopDispositions;
1354 :
1355 : struct LoopProperties {
1356 : /// Set to true if the loop contains no instruction that can have side
1357 : /// effects (i.e. via throwing an exception, volatile or atomic access).
1358 : bool HasNoAbnormalExits;
1359 :
1360 : /// Set to true if the loop contains no instruction that can abnormally exit
1361 : /// the loop (i.e. via throwing an exception, by terminating the thread
1362 : /// cleanly or by infinite looping in a called function). Strictly
1363 : /// speaking, the last one is not leaving the loop, but is identical to
1364 : /// leaving the loop for reasoning about undefined behavior.
1365 : bool HasNoSideEffects;
1366 : };
1367 :
1368 : /// Cache for \c getLoopProperties.
1369 : DenseMap<const Loop *, LoopProperties> LoopPropertiesCache;
1370 :
1371 : /// Return a \c LoopProperties instance for \p L, creating one if necessary.
1372 : LoopProperties getLoopProperties(const Loop *L);
1373 :
1374 : bool loopHasNoSideEffects(const Loop *L) {
1375 7 : return getLoopProperties(L).HasNoSideEffects;
1376 : }
1377 :
1378 : bool loopHasNoAbnormalExits(const Loop *L) {
1379 24384 : return getLoopProperties(L).HasNoAbnormalExits;
1380 : }
1381 :
1382 : /// Compute a LoopDisposition value.
1383 : LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L);
1384 :
1385 : /// Memoized computeBlockDisposition results.
1386 : DenseMap<
1387 : const SCEV *,
1388 : SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>>
1389 : BlockDispositions;
1390 :
1391 : /// Compute a BlockDisposition value.
1392 : BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB);
1393 :
1394 : /// Memoized results from getRange
1395 : DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
1396 :
1397 : /// Memoized results from getRange
1398 : DenseMap<const SCEV *, ConstantRange> SignedRanges;
1399 :
1400 : /// Used to parameterize getRange
1401 : enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED };
1402 :
1403 : /// Set the memoized range for the given SCEV.
1404 1462913 : const ConstantRange &setRange(const SCEV *S, RangeSignHint Hint,
1405 : ConstantRange CR) {
1406 1462913 : DenseMap<const SCEV *, ConstantRange> &Cache =
1407 : Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges;
1408 :
1409 1462913 : auto Pair = Cache.try_emplace(S, std::move(CR));
1410 1462913 : if (!Pair.second)
1411 11211 : Pair.first->second = std::move(CR);
1412 1462913 : return Pair.first->second;
1413 : }
1414 :
1415 : /// Determine the range for a particular SCEV.
1416 : /// NOTE: This returns a reference to an entry in a cache. It must be
1417 : /// copied if its needed for longer.
1418 : const ConstantRange &getRangeRef(const SCEV *S, RangeSignHint Hint);
1419 :
1420 : /// Determines the range for the affine SCEVAddRecExpr {\p Start,+,\p Stop}.
1421 : /// Helper for \c getRange.
1422 : ConstantRange getRangeForAffineAR(const SCEV *Start, const SCEV *Stop,
1423 : const SCEV *MaxBECount, unsigned BitWidth);
1424 :
1425 : /// Try to compute a range for the affine SCEVAddRecExpr {\p Start,+,\p
1426 : /// Stop} by "factoring out" a ternary expression from the add recurrence.
1427 : /// Helper called by \c getRange.
1428 : ConstantRange getRangeViaFactoring(const SCEV *Start, const SCEV *Stop,
1429 : const SCEV *MaxBECount, unsigned BitWidth);
1430 :
1431 : /// We know that there is no SCEV for the specified value. Analyze the
1432 : /// expression.
1433 : const SCEV *createSCEV(Value *V);
1434 :
1435 : /// Provide the special handling we need to analyze PHI SCEVs.
1436 : const SCEV *createNodeForPHI(PHINode *PN);
1437 :
1438 : /// Helper function called from createNodeForPHI.
1439 : const SCEV *createAddRecFromPHI(PHINode *PN);
1440 :
1441 : /// A helper function for createAddRecFromPHI to handle simple cases.
1442 : const SCEV *createSimpleAffineAddRec(PHINode *PN, Value *BEValueV,
1443 : Value *StartValueV);
1444 :
1445 : /// Helper function called from createNodeForPHI.
1446 : const SCEV *createNodeFromSelectLikePHI(PHINode *PN);
1447 :
1448 : /// Provide special handling for a select-like instruction (currently this
1449 : /// is either a select instruction or a phi node). \p I is the instruction
1450 : /// being processed, and it is assumed equivalent to "Cond ? TrueVal :
1451 : /// FalseVal".
1452 : const SCEV *createNodeForSelectOrPHI(Instruction *I, Value *Cond,
1453 : Value *TrueVal, Value *FalseVal);
1454 :
1455 : /// Provide the special handling we need to analyze GEP SCEVs.
1456 : const SCEV *createNodeForGEP(GEPOperator *GEP);
1457 :
1458 : /// Implementation code for getSCEVAtScope; called at most once for each
1459 : /// SCEV+Loop pair.
1460 : const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L);
1461 :
1462 : /// This looks up computed SCEV values for all instructions that depend on
1463 : /// the given instruction and removes them from the ValueExprMap map if they
1464 : /// reference SymName. This is used during PHI resolution.
1465 : void forgetSymbolicName(Instruction *I, const SCEV *SymName);
1466 :
1467 : /// Return the BackedgeTakenInfo for the given loop, lazily computing new
1468 : /// values if the loop hasn't been analyzed yet. The returned result is
1469 : /// guaranteed not to be predicated.
1470 : const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L);
1471 :
1472 : /// Similar to getBackedgeTakenInfo, but will add predicates as required
1473 : /// with the purpose of returning complete information.
1474 : const BackedgeTakenInfo &getPredicatedBackedgeTakenInfo(const Loop *L);
1475 :
1476 : /// Compute the number of times the specified loop will iterate.
1477 : /// If AllowPredicates is set, we will create new SCEV predicates as
1478 : /// necessary in order to return an exact answer.
1479 : BackedgeTakenInfo computeBackedgeTakenCount(const Loop *L,
1480 : bool AllowPredicates = false);
1481 :
1482 : /// Compute the number of times the backedge of the specified loop will
1483 : /// execute if it exits via the specified block. If AllowPredicates is set,
1484 : /// this call will try to use a minimal set of SCEV predicates in order to
1485 : /// return an exact answer.
1486 : ExitLimit computeExitLimit(const Loop *L, BasicBlock *ExitingBlock,
1487 : bool AllowPredicates = false);
1488 :
1489 : /// Compute the number of times the backedge of the specified loop will
1490 : /// execute if its exit condition were a conditional branch of ExitCond.
1491 : ///
1492 : /// \p ControlsExit is true if ExitCond directly controls the exit
1493 : /// branch. In this case, we can assume that the loop exits only if the
1494 : /// condition is true and can infer that failing to meet the condition prior
1495 : /// to integer wraparound results in undefined behavior.
1496 : ///
1497 : /// If \p AllowPredicates is set, this call will try to use a minimal set of
1498 : /// SCEV predicates in order to return an exact answer.
1499 : ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond,
1500 : bool ExitIfTrue, bool ControlsExit,
1501 : bool AllowPredicates = false);
1502 :
1503 : // Helper functions for computeExitLimitFromCond to avoid exponential time
1504 : // complexity.
1505 :
1506 31158 : class ExitLimitCache {
1507 : // It may look like we need key on the whole (L, ExitIfTrue, ControlsExit,
1508 : // AllowPredicates) tuple, but recursive calls to
1509 : // computeExitLimitFromCondCached from computeExitLimitFromCondImpl only
1510 : // vary the in \c ExitCond and \c ControlsExit parameters. We remember the
1511 : // initial values of the other values to assert our assumption.
1512 : SmallDenseMap<PointerIntPair<Value *, 1>, ExitLimit> TripCountMap;
1513 :
1514 : const Loop *L;
1515 : bool ExitIfTrue;
1516 : bool AllowPredicates;
1517 :
1518 : public:
1519 : ExitLimitCache(const Loop *L, bool ExitIfTrue, bool AllowPredicates)
1520 31158 : : L(L), ExitIfTrue(ExitIfTrue), AllowPredicates(AllowPredicates) {}
1521 :
1522 : Optional<ExitLimit> find(const Loop *L, Value *ExitCond, bool ExitIfTrue,
1523 : bool ControlsExit, bool AllowPredicates);
1524 :
1525 : void insert(const Loop *L, Value *ExitCond, bool ExitIfTrue,
1526 : bool ControlsExit, bool AllowPredicates, const ExitLimit &EL);
1527 : };
1528 :
1529 : using ExitLimitCacheTy = ExitLimitCache;
1530 :
1531 : ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache,
1532 : const Loop *L, Value *ExitCond,
1533 : bool ExitIfTrue,
1534 : bool ControlsExit,
1535 : bool AllowPredicates);
1536 : ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache, const Loop *L,
1537 : Value *ExitCond, bool ExitIfTrue,
1538 : bool ControlsExit,
1539 : bool AllowPredicates);
1540 :
1541 : /// Compute the number of times the backedge of the specified loop will
1542 : /// execute if its exit condition were a conditional branch of the ICmpInst
1543 : /// ExitCond and ExitIfTrue. If AllowPredicates is set, this call will try
1544 : /// to use a minimal set of SCEV predicates in order to return an exact
1545 : /// answer.
1546 : ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond,
1547 : bool ExitIfTrue,
1548 : bool IsSubExpr,
1549 : bool AllowPredicates = false);
1550 :
1551 : /// Compute the number of times the backedge of the specified loop will
1552 : /// execute if its exit condition were a switch with a single exiting case
1553 : /// to ExitingBB.
1554 : ExitLimit computeExitLimitFromSingleExitSwitch(const Loop *L,
1555 : SwitchInst *Switch,
1556 : BasicBlock *ExitingBB,
1557 : bool IsSubExpr);
1558 :
1559 : /// Given an exit condition of 'icmp op load X, cst', try to see if we can
1560 : /// compute the backedge-taken count.
1561 : ExitLimit computeLoadConstantCompareExitLimit(LoadInst *LI, Constant *RHS,
1562 : const Loop *L,
1563 : ICmpInst::Predicate p);
1564 :
1565 : /// Compute the exit limit of a loop that is controlled by a
1566 : /// "(IV >> 1) != 0" type comparison. We cannot compute the exact trip
1567 : /// count in these cases (since SCEV has no way of expressing them), but we
1568 : /// can still sometimes compute an upper bound.
1569 : ///
1570 : /// Return an ExitLimit for a loop whose backedge is guarded by `LHS Pred
1571 : /// RHS`.
1572 : ExitLimit computeShiftCompareExitLimit(Value *LHS, Value *RHS, const Loop *L,
1573 : ICmpInst::Predicate Pred);
1574 :
1575 : /// If the loop is known to execute a constant number of times (the
1576 : /// condition evolves only from constants), try to evaluate a few iterations
1577 : /// of the loop until we get the exit condition gets a value of ExitWhen
1578 : /// (true or false). If we cannot evaluate the exit count of the loop,
1579 : /// return CouldNotCompute.
1580 : const SCEV *computeExitCountExhaustively(const Loop *L, Value *Cond,
1581 : bool ExitWhen);
1582 :
1583 : /// Return the number of times an exit condition comparing the specified
1584 : /// value to zero will execute. If not computable, return CouldNotCompute.
1585 : /// If AllowPredicates is set, this call will try to use a minimal set of
1586 : /// SCEV predicates in order to return an exact answer.
1587 : ExitLimit howFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr,
1588 : bool AllowPredicates = false);
1589 :
1590 : /// Return the number of times an exit condition checking the specified
1591 : /// value for nonzero will execute. If not computable, return
1592 : /// CouldNotCompute.
1593 : ExitLimit howFarToNonZero(const SCEV *V, const Loop *L);
1594 :
1595 : /// Return the number of times an exit condition containing the specified
1596 : /// less-than comparison will execute. If not computable, return
1597 : /// CouldNotCompute.
1598 : ///
1599 : /// \p isSigned specifies whether the less-than is signed.
1600 : ///
1601 : /// \p ControlsExit is true when the LHS < RHS condition directly controls
1602 : /// the branch (loops exits only if condition is true). In this case, we can
1603 : /// use NoWrapFlags to skip overflow checks.
1604 : ///
1605 : /// If \p AllowPredicates is set, this call will try to use a minimal set of
1606 : /// SCEV predicates in order to return an exact answer.
1607 : ExitLimit howManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
1608 : bool isSigned, bool ControlsExit,
1609 : bool AllowPredicates = false);
1610 :
1611 : ExitLimit howManyGreaterThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
1612 : bool isSigned, bool IsSubExpr,
1613 : bool AllowPredicates = false);
1614 :
1615 : /// Return a predecessor of BB (which may not be an immediate predecessor)
1616 : /// which has exactly one successor from which BB is reachable, or null if
1617 : /// no such block is found.
1618 : std::pair<BasicBlock *, BasicBlock *>
1619 : getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB);
1620 :
1621 : /// Test whether the condition described by Pred, LHS, and RHS is true
1622 : /// whenever the given FoundCondValue value evaluates to true.
1623 : bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
1624 : Value *FoundCondValue, bool Inverse);
1625 :
1626 : /// Test whether the condition described by Pred, LHS, and RHS is true
1627 : /// whenever the condition described by FoundPred, FoundLHS, FoundRHS is
1628 : /// true.
1629 : bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
1630 : ICmpInst::Predicate FoundPred, const SCEV *FoundLHS,
1631 : const SCEV *FoundRHS);
1632 :
1633 : /// Test whether the condition described by Pred, LHS, and RHS is true
1634 : /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1635 : /// true.
1636 : bool isImpliedCondOperands(ICmpInst::Predicate Pred, const SCEV *LHS,
1637 : const SCEV *RHS, const SCEV *FoundLHS,
1638 : const SCEV *FoundRHS);
1639 :
1640 : /// Test whether the condition described by Pred, LHS, and RHS is true
1641 : /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1642 : /// true. Here LHS is an operation that includes FoundLHS as one of its
1643 : /// arguments.
1644 : bool isImpliedViaOperations(ICmpInst::Predicate Pred,
1645 : const SCEV *LHS, const SCEV *RHS,
1646 : const SCEV *FoundLHS, const SCEV *FoundRHS,
1647 : unsigned Depth = 0);
1648 :
1649 : /// Test whether the condition described by Pred, LHS, and RHS is true.
1650 : /// Use only simple non-recursive types of checks, such as range analysis etc.
1651 : bool isKnownViaNonRecursiveReasoning(ICmpInst::Predicate Pred,
1652 : const SCEV *LHS, const SCEV *RHS);
1653 :
1654 : /// Test whether the condition described by Pred, LHS, and RHS is true
1655 : /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1656 : /// true.
1657 : bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, const SCEV *LHS,
1658 : const SCEV *RHS, const SCEV *FoundLHS,
1659 : const SCEV *FoundRHS);
1660 :
1661 : /// Test whether the condition described by Pred, LHS, and RHS is true
1662 : /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1663 : /// true. Utility function used by isImpliedCondOperands. Tries to get
1664 : /// cases like "X `sgt` 0 => X - 1 `sgt` -1".
1665 : bool isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred, const SCEV *LHS,
1666 : const SCEV *RHS, const SCEV *FoundLHS,
1667 : const SCEV *FoundRHS);
1668 :
1669 : /// Return true if the condition denoted by \p LHS \p Pred \p RHS is implied
1670 : /// by a call to \c @llvm.experimental.guard in \p BB.
1671 : bool isImpliedViaGuard(BasicBlock *BB, ICmpInst::Predicate Pred,
1672 : const SCEV *LHS, const SCEV *RHS);
1673 :
1674 : /// Test whether the condition described by Pred, LHS, and RHS is true
1675 : /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1676 : /// true.
1677 : ///
1678 : /// This routine tries to rule out certain kinds of integer overflow, and
1679 : /// then tries to reason about arithmetic properties of the predicates.
1680 : bool isImpliedCondOperandsViaNoOverflow(ICmpInst::Predicate Pred,
1681 : const SCEV *LHS, const SCEV *RHS,
1682 : const SCEV *FoundLHS,
1683 : const SCEV *FoundRHS);
1684 :
1685 : /// Test whether the condition described by Pred, LHS, and RHS is true
1686 : /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
1687 : /// true.
1688 : ///
1689 : /// This routine tries to figure out predicate for Phis which are SCEVUnknown
1690 : /// if it is true for every possible incoming value from their respective
1691 : /// basic blocks.
1692 : bool isImpliedViaMerge(ICmpInst::Predicate Pred,
1693 : const SCEV *LHS, const SCEV *RHS,
1694 : const SCEV *FoundLHS, const SCEV *FoundRHS,
1695 : unsigned Depth);
1696 :
1697 : /// If we know that the specified Phi is in the header of its containing
1698 : /// loop, we know the loop executes a constant number of times, and the PHI
1699 : /// node is just a recurrence involving constants, fold it.
1700 : Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt &BEs,
1701 : const Loop *L);
1702 :
1703 : /// Test if the given expression is known to satisfy the condition described
1704 : /// by Pred and the known constant ranges of LHS and RHS.
1705 : bool isKnownPredicateViaConstantRanges(ICmpInst::Predicate Pred,
1706 : const SCEV *LHS, const SCEV *RHS);
1707 :
1708 : /// Try to prove the condition described by "LHS Pred RHS" by ruling out
1709 : /// integer overflow.
1710 : ///
1711 : /// For instance, this will return true for "A s< (A + C)<nsw>" if C is
1712 : /// positive.
1713 : bool isKnownPredicateViaNoOverflow(ICmpInst::Predicate Pred, const SCEV *LHS,
1714 : const SCEV *RHS);
1715 :
1716 : /// Try to split Pred LHS RHS into logical conjunctions (and's) and try to
1717 : /// prove them individually.
1718 : bool isKnownPredicateViaSplitting(ICmpInst::Predicate Pred, const SCEV *LHS,
1719 : const SCEV *RHS);
1720 :
1721 : /// Try to match the Expr as "(L + R)<Flags>".
1722 : bool splitBinaryAdd(const SCEV *Expr, const SCEV *&L, const SCEV *&R,
1723 : SCEV::NoWrapFlags &Flags);
1724 :
1725 : /// Compute \p LHS - \p RHS and returns the result as an APInt if it is a
1726 : /// constant, and None if it isn't.
1727 : ///
1728 : /// This is intended to be a cheaper version of getMinusSCEV. We can be
1729 : /// frugal here since we just bail out of actually constructing and
1730 : /// canonicalizing an expression in the cases where the result isn't going
1731 : /// to be a constant.
1732 : Optional<APInt> computeConstantDifference(const SCEV *LHS, const SCEV *RHS);
1733 :
1734 : /// Drop memoized information computed for S.
1735 : void forgetMemoizedResults(const SCEV *S);
1736 :
1737 : /// Return an existing SCEV for V if there is one, otherwise return nullptr.
1738 : const SCEV *getExistingSCEV(Value *V);
1739 :
1740 : /// Return false iff given SCEV contains a SCEVUnknown with NULL value-
1741 : /// pointer.
1742 : bool checkValidity(const SCEV *S) const;
1743 :
1744 : /// Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be
1745 : /// equal to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}. This is
1746 : /// equivalent to proving no signed (resp. unsigned) wrap in
1747 : /// {`Start`,+,`Step`} if `ExtendOpTy` is `SCEVSignExtendExpr`
1748 : /// (resp. `SCEVZeroExtendExpr`).
1749 : template <typename ExtendOpTy>
1750 : bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step,
1751 : const Loop *L);
1752 :
1753 : /// Try to prove NSW or NUW on \p AR relying on ConstantRange manipulation.
1754 : SCEV::NoWrapFlags proveNoWrapViaConstantRanges(const SCEVAddRecExpr *AR);
1755 :
1756 : bool isMonotonicPredicateImpl(const SCEVAddRecExpr *LHS,
1757 : ICmpInst::Predicate Pred, bool &Increasing);
1758 :
1759 : /// Return SCEV no-wrap flags that can be proven based on reasoning about
1760 : /// how poison produced from no-wrap flags on this value (e.g. a nuw add)
1761 : /// would trigger undefined behavior on overflow.
1762 : SCEV::NoWrapFlags getNoWrapFlagsFromUB(const Value *V);
1763 :
1764 : /// Return true if the SCEV corresponding to \p I is never poison. Proving
1765 : /// this is more complex than proving that just \p I is never poison, since
1766 : /// SCEV commons expressions across control flow, and you can have cases
1767 : /// like:
1768 : ///
1769 : /// idx0 = a + b;
1770 : /// ptr[idx0] = 100;
1771 : /// if (<condition>) {
1772 : /// idx1 = a +nsw b;
1773 : /// ptr[idx1] = 200;
1774 : /// }
1775 : ///
1776 : /// where the SCEV expression (+ a b) is guaranteed to not be poison (and
1777 : /// hence not sign-overflow) only if "<condition>" is true. Since both
1778 : /// `idx0` and `idx1` will be mapped to the same SCEV expression, (+ a b),
1779 : /// it is not okay to annotate (+ a b) with <nsw> in the above example.
1780 : bool isSCEVExprNeverPoison(const Instruction *I);
1781 :
1782 : /// This is like \c isSCEVExprNeverPoison but it specifically works for
1783 : /// instructions that will get mapped to SCEV add recurrences. Return true
1784 : /// if \p I will never generate poison under the assumption that \p I is an
1785 : /// add recurrence on the loop \p L.
1786 : bool isAddRecNeverPoison(const Instruction *I, const Loop *L);
1787 :
1788 : /// Similar to createAddRecFromPHI, but with the additional flexibility of
1789 : /// suggesting runtime overflow checks in case casts are encountered.
1790 : /// If successful, the analysis records that for this loop, \p SymbolicPHI,
1791 : /// which is the UnknownSCEV currently representing the PHI, can be rewritten
1792 : /// into an AddRec, assuming some predicates; The function then returns the
1793 : /// AddRec and the predicates as a pair, and caches this pair in
1794 : /// PredicatedSCEVRewrites.
1795 : /// If the analysis is not successful, a mapping from the \p SymbolicPHI to
1796 : /// itself (with no predicates) is recorded, and a nullptr with an empty
1797 : /// predicates vector is returned as a pair.
1798 : Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
1799 : createAddRecFromPHIWithCastsImpl(const SCEVUnknown *SymbolicPHI);
1800 :
1801 : /// Compute the backedge taken count knowing the interval difference, the
1802 : /// stride and presence of the equality in the comparison.
1803 : const SCEV *computeBECount(const SCEV *Delta, const SCEV *Stride,
1804 : bool Equality);
1805 :
1806 : /// Compute the maximum backedge count based on the range of values
1807 : /// permitted by Start, End, and Stride. This is for loops of the form
1808 : /// {Start, +, Stride} LT End.
1809 : ///
1810 : /// Precondition: the induction variable is known to be positive. We *don't*
1811 : /// assert these preconditions so please be careful.
1812 : const SCEV *computeMaxBECountForLT(const SCEV *Start, const SCEV *Stride,
1813 : const SCEV *End, unsigned BitWidth,
1814 : bool IsSigned);
1815 :
1816 : /// Verify if an linear IV with positive stride can overflow when in a
1817 : /// less-than comparison, knowing the invariant term of the comparison,
1818 : /// the stride and the knowledge of NSW/NUW flags on the recurrence.
1819 : bool doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, bool IsSigned,
1820 : bool NoWrap);
1821 :
1822 : /// Verify if an linear IV with negative stride can overflow when in a
1823 : /// greater-than comparison, knowing the invariant term of the comparison,
1824 : /// the stride and the knowledge of NSW/NUW flags on the recurrence.
1825 : bool doesIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, bool IsSigned,
1826 : bool NoWrap);
1827 :
1828 : /// Get add expr already created or create a new one.
1829 : const SCEV *getOrCreateAddExpr(SmallVectorImpl<const SCEV *> &Ops,
1830 : SCEV::NoWrapFlags Flags);
1831 :
1832 : /// Get mul expr already created or create a new one.
1833 : const SCEV *getOrCreateMulExpr(SmallVectorImpl<const SCEV *> &Ops,
1834 : SCEV::NoWrapFlags Flags);
1835 :
1836 : // Get addrec expr already created or create a new one.
1837 : const SCEV *getOrCreateAddRecExpr(SmallVectorImpl<const SCEV *> &Ops,
1838 : const Loop *L, SCEV::NoWrapFlags Flags);
1839 :
1840 : /// Return x if \p Val is f(x) where f is a 1-1 function.
1841 : const SCEV *stripInjectiveFunctions(const SCEV *Val) const;
1842 :
1843 : /// Find all of the loops transitively used in \p S, and fill \p LoopsUsed.
1844 : /// A loop is considered "used" by an expression if it contains
1845 : /// an add rec on said loop.
1846 : void getUsedLoops(const SCEV *S, SmallPtrSetImpl<const Loop *> &LoopsUsed);
1847 :
1848 : /// Find all of the loops transitively used in \p S, and update \c LoopUsers
1849 : /// accordingly.
1850 : void addToLoopUseLists(const SCEV *S);
1851 :
1852 : /// Try to match the pattern generated by getURemExpr(A, B). If successful,
1853 : /// Assign A and B to LHS and RHS, respectively.
1854 : bool matchURem(const SCEV *Expr, const SCEV *&LHS, const SCEV *&RHS);
1855 :
1856 : FoldingSet<SCEV> UniqueSCEVs;
1857 : FoldingSet<SCEVPredicate> UniquePreds;
1858 : BumpPtrAllocator SCEVAllocator;
1859 :
1860 : /// This maps loops to a list of SCEV expressions that (transitively) use said
1861 : /// loop.
1862 : DenseMap<const Loop *, SmallVector<const SCEV *, 4>> LoopUsers;
1863 :
1864 : /// Cache tentative mappings from UnknownSCEVs in a Loop, to a SCEV expression
1865 : /// they can be rewritten into under certain predicates.
1866 : DenseMap<std::pair<const SCEVUnknown *, const Loop *>,
1867 : std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
1868 : PredicatedSCEVRewrites;
1869 :
1870 : /// The head of a linked list of all SCEVUnknown values that have been
1871 : /// allocated. This is used by releaseMemory to locate them all and call
1872 : /// their destructors.
1873 : SCEVUnknown *FirstUnknown = nullptr;
1874 : };
1875 :
1876 : /// Analysis pass that exposes the \c ScalarEvolution for a function.
1877 : class ScalarEvolutionAnalysis
1878 : : public AnalysisInfoMixin<ScalarEvolutionAnalysis> {
1879 : friend AnalysisInfoMixin<ScalarEvolutionAnalysis>;
1880 :
1881 : static AnalysisKey Key;
1882 :
1883 : public:
1884 : using Result = ScalarEvolution;
1885 :
1886 : ScalarEvolution run(Function &F, FunctionAnalysisManager &AM);
1887 : };
1888 :
1889 : /// Printer pass for the \c ScalarEvolutionAnalysis results.
1890 : class ScalarEvolutionPrinterPass
1891 : : public PassInfoMixin<ScalarEvolutionPrinterPass> {
1892 : raw_ostream &OS;
1893 :
1894 : public:
1895 6 : explicit ScalarEvolutionPrinterPass(raw_ostream &OS) : OS(OS) {}
1896 :
1897 : PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
1898 : };
1899 :
1900 : class ScalarEvolutionWrapperPass : public FunctionPass {
1901 : std::unique_ptr<ScalarEvolution> SE;
1902 :
1903 : public:
1904 : static char ID;
1905 :
1906 : ScalarEvolutionWrapperPass();
1907 :
1908 : ScalarEvolution &getSE() { return *SE; }
1909 : const ScalarEvolution &getSE() const { return *SE; }
1910 :
1911 : bool runOnFunction(Function &F) override;
1912 : void releaseMemory() override;
1913 : void getAnalysisUsage(AnalysisUsage &AU) const override;
1914 : void print(raw_ostream &OS, const Module * = nullptr) const override;
1915 : void verifyAnalysis() const override;
1916 : };
1917 :
1918 : /// An interface layer with SCEV used to manage how we see SCEV expressions
1919 : /// for values in the context of existing predicates. We can add new
1920 : /// predicates, but we cannot remove them.
1921 : ///
1922 : /// This layer has multiple purposes:
1923 : /// - provides a simple interface for SCEV versioning.
1924 : /// - guarantees that the order of transformations applied on a SCEV
1925 : /// expression for a single Value is consistent across two different
1926 : /// getSCEV calls. This means that, for example, once we've obtained
1927 : /// an AddRec expression for a certain value through expression
1928 : /// rewriting, we will continue to get an AddRec expression for that
1929 : /// Value.
1930 : /// - lowers the number of expression rewrites.
1931 : class PredicatedScalarEvolution {
1932 : public:
1933 : PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L);
1934 :
1935 : const SCEVUnionPredicate &getUnionPredicate() const;
1936 :
1937 : /// Returns the SCEV expression of V, in the context of the current SCEV
1938 : /// predicate. The order of transformations applied on the expression of V
1939 : /// returned by ScalarEvolution is guaranteed to be preserved, even when
1940 : /// adding new predicates.
1941 : const SCEV *getSCEV(Value *V);
1942 :
1943 : /// Get the (predicated) backedge count for the analyzed loop.
1944 : const SCEV *getBackedgeTakenCount();
1945 :
1946 : /// Adds a new predicate.
1947 : void addPredicate(const SCEVPredicate &Pred);
1948 :
1949 : /// Attempts to produce an AddRecExpr for V by adding additional SCEV
1950 : /// predicates. If we can't transform the expression into an AddRecExpr we
1951 : /// return nullptr and not add additional SCEV predicates to the current
1952 : /// context.
1953 : const SCEVAddRecExpr *getAsAddRec(Value *V);
1954 :
1955 : /// Proves that V doesn't overflow by adding SCEV predicate.
1956 : void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags);
1957 :
1958 : /// Returns true if we've proved that V doesn't wrap by means of a SCEV
1959 : /// predicate.
1960 : bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags);
1961 :
1962 : /// Returns the ScalarEvolution analysis used.
1963 0 : ScalarEvolution *getSE() const { return &SE; }
1964 :
1965 : /// We need to explicitly define the copy constructor because of FlagsMap.
1966 : PredicatedScalarEvolution(const PredicatedScalarEvolution &);
1967 :
1968 : /// Print the SCEV mappings done by the Predicated Scalar Evolution.
1969 : /// The printed text is indented by \p Depth.
1970 : void print(raw_ostream &OS, unsigned Depth) const;
1971 :
1972 : /// Check if \p AR1 and \p AR2 are equal, while taking into account
1973 : /// Equal predicates in Preds.
1974 : bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1,
1975 : const SCEVAddRecExpr *AR2) const;
1976 :
1977 : private:
1978 : /// Increments the version number of the predicate. This needs to be called
1979 : /// every time the SCEV predicate changes.
1980 : void updateGeneration();
1981 :
1982 : /// Holds a SCEV and the version number of the SCEV predicate used to
1983 : /// perform the rewrite of the expression.
1984 : using RewriteEntry = std::pair<unsigned, const SCEV *>;
1985 :
1986 : /// Maps a SCEV to the rewrite result of that SCEV at a certain version
1987 : /// number. If this number doesn't match the current Generation, we will
1988 : /// need to do a rewrite. To preserve the transformation order of previous
1989 : /// rewrites, we will rewrite the previous result instead of the original
1990 : /// SCEV.
1991 : DenseMap<const SCEV *, RewriteEntry> RewriteMap;
1992 :
1993 : /// Records what NoWrap flags we've added to a Value *.
1994 : ValueMap<Value *, SCEVWrapPredicate::IncrementWrapFlags> FlagsMap;
1995 :
1996 : /// The ScalarEvolution analysis.
1997 : ScalarEvolution &SE;
1998 :
1999 : /// The analyzed Loop.
2000 : const Loop &L;
2001 :
2002 : /// The SCEVPredicate that forms our context. We will rewrite all
2003 : /// expressions assuming that this predicate true.
2004 : SCEVUnionPredicate Preds;
2005 :
2006 : /// Marks the version of the SCEV predicate used. When rewriting a SCEV
2007 : /// expression we mark it with the version of the predicate. We use this to
2008 : /// figure out if the predicate has changed from the last rewrite of the
2009 : /// SCEV. If so, we need to perform a new rewrite.
2010 : unsigned Generation = 0;
2011 :
2012 : /// The backedge taken count.
2013 : const SCEV *BackedgeCount = nullptr;
2014 : };
2015 :
2016 : } // end namespace llvm
2017 :
2018 : #endif // LLVM_ANALYSIS_SCALAREVOLUTION_H
|
