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