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