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