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