1	//===- ConstantRangeTest.cpp - ConstantRange tests ------------------------===//
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	#include "llvm/IR/ConstantRange.h"
10	#include "llvm/ADT/BitVector.h"
11	#include "llvm/ADT/Sequence.h"
12	#include "llvm/ADT/SmallBitVector.h"
13	#include "llvm/IR/Instructions.h"
14	#include "llvm/IR/Operator.h"
15	#include "llvm/Support/KnownBits.h"
16	#include "gtest/gtest.h"
17
18	using namespace llvm;
19
20	namespace {
21
22	class ConstantRangeTest : public ::testing::Test {
23	protected:
24	static ConstantRange Full;
25	static ConstantRange Empty;
26	static ConstantRange One;
27	static ConstantRange Some;
28	static ConstantRange Wrap;
29	};
30
31	template<typename Fn>
32	static void EnumerateAPInts(unsigned Bits, Fn TestFn) {
33	APInt N(Bits, 0);
34	do {
35	TestFn(N);
36	} while (++N != 0);
37	}
38
39	template<typename Fn>
40	static void EnumerateConstantRanges(unsigned Bits, Fn TestFn) {
41	unsigned Max = 1 << Bits;
42	for (unsigned Lo = 0; Lo < Max; Lo++) {
43	for (unsigned Hi = 0; Hi < Max; Hi++) {
44	// Enforce ConstantRange invariant.
45	if (Lo == Hi && Lo != 0 && Lo != Max - 1)
46	continue;
47
48	ConstantRange CR(APInt(Bits, Lo), APInt(Bits, Hi));
49	TestFn(CR);
50	}
51	}
52	}
53
54	template <typename Fn>
55	static void EnumerateInterestingConstantRanges(Fn TestFn) {
56	// Check 1 bit ranges, because they may have special cases.
57	EnumerateConstantRanges(/* Bits */ 1, TestFn);
58	// Check 4 bit ranges to have decent coverage without being too slow.
59	EnumerateConstantRanges(/* Bits */ 4, TestFn);
60	}
61
62	template <typename Fn>
63	static void EnumerateTwoInterestingConstantRanges(Fn TestFn) {
64	for (unsigned Bits : {1, 4}) {
65	EnumerateConstantRanges(Bits, [&](const ConstantRange &CR1) {
66	EnumerateConstantRanges(
67	Bits, [&](const ConstantRange &CR2) { TestFn(CR1, CR2); });
68	});
69	}
70	}
71
72	template <typename Fn>
73	static void ForeachNumInConstantRange(const ConstantRange &CR, Fn TestFn) {
74	if (!CR.isEmptySet()) {
75	APInt N = CR.getLower();
76	do TestFn(N);
77	while (++N != CR.getUpper());
78	}
79	}
80
81	using PreferFn = llvm::function_ref<bool(const ConstantRange &,
82	const ConstantRange &)>;
83
84	bool PreferSmallest(const ConstantRange &CR1, const ConstantRange &CR2) {
85	return CR1.isSizeStrictlySmallerThan(CR: CR2);
86	}
87
88	bool PreferSmallestUnsigned(const ConstantRange &CR1,
89	const ConstantRange &CR2) {
90	if (CR1.isWrappedSet() != CR2.isWrappedSet())
91	return CR1.isWrappedSet() < CR2.isWrappedSet();
92	return PreferSmallest(CR1, CR2);
93	}
94
95	bool PreferSmallestSigned(const ConstantRange &CR1, const ConstantRange &CR2) {
96	if (CR1.isSignWrappedSet() != CR2.isSignWrappedSet())
97	return CR1.isSignWrappedSet() < CR2.isSignWrappedSet();
98	return PreferSmallest(CR1, CR2);
99	}
100
101	bool PreferSmallestNonFullUnsigned(const ConstantRange &CR1,
102	const ConstantRange &CR2) {
103	if (CR1.isFullSet() != CR2.isFullSet())
104	return CR1.isFullSet() < CR2.isFullSet();
105	return PreferSmallestUnsigned(CR1, CR2);
106	}
107
108	bool PreferSmallestNonFullSigned(const ConstantRange &CR1,
109	const ConstantRange &CR2) {
110	if (CR1.isFullSet() != CR2.isFullSet())
111	return CR1.isFullSet() < CR2.isFullSet();
112	return PreferSmallestSigned(CR1, CR2);
113	}
114
115	testing::AssertionResult rangeContains(const ConstantRange &CR, const APInt &N,
116	ArrayRef<ConstantRange> Inputs) {
117	if (CR.contains(Val: N))
118	return testing::AssertionSuccess();
119
120	testing::AssertionResult Result = testing::AssertionFailure();
121	Result << CR << " does not contain " << N << " for inputs: ";
122	for (const ConstantRange &Input : Inputs)
123	Result << Input << ", ";
124	return Result;
125	}
126
127	// Check whether constant range CR is an optimal approximation of the set
128	// Elems under the given PreferenceFn. The preference function should return
129	// true if the first range argument is strictly preferred to the second one.
130	static void TestRange(const ConstantRange &CR, const SmallBitVector &Elems,
131	PreferFn PreferenceFn, ArrayRef<ConstantRange> Inputs,
132	bool CheckOptimality = true) {
133	unsigned BitWidth = CR.getBitWidth();
134
135	// Check conservative correctness.
136	for (unsigned Elem : Elems.set_bits()) {
137	EXPECT_TRUE(rangeContains(CR, APInt(BitWidth, Elem), Inputs));
138	}
139
140	if (!CheckOptimality)
141	return;
142
143	// Make sure we have at least one element for the code below.
144	if (Elems.none()) {
145	EXPECT_TRUE(CR.isEmptySet());
146	return;
147	}
148
149	auto NotPreferred = [&](const ConstantRange &PossibleCR) {
150	if (!PreferenceFn(PossibleCR, CR))
151	return testing::AssertionSuccess();
152
153	testing::AssertionResult Result = testing::AssertionFailure();
154	Result << "Inputs = ";
155	for (const ConstantRange &Input : Inputs)
156	Result << Input << ", ";
157	Result << "CR = " << CR << ", BetterCR = " << PossibleCR;
158	return Result;
159	};
160
161	// Look at all pairs of adjacent elements and the slack-free ranges
162	// [Elem, PrevElem] they imply. Check that none of the ranges are strictly
163	// preferred over the computed range (they may have equal preference).
164	int FirstElem = Elems.find_first();
165	int PrevElem = FirstElem, Elem;
166	do {
167	Elem = Elems.find_next(Prev: PrevElem);
168	if (Elem < 0)
169	Elem = FirstElem; // Wrap around to first element.
170
171	ConstantRange PossibleCR =
172	ConstantRange::getNonEmpty(Lower: APInt(BitWidth, Elem),
173	Upper: APInt(BitWidth, PrevElem) + 1);
174	// We get a full range any time PrevElem and Elem are adjacent. Avoid
175	// repeated checks by skipping here, and explicitly checking below instead.
176	if (!PossibleCR.isFullSet()) {
177	EXPECT_TRUE(NotPreferred(PossibleCR));
178	}
179
180	PrevElem = Elem;
181	} while (Elem != FirstElem);
182
183	EXPECT_TRUE(NotPreferred(ConstantRange::getFull(BitWidth)));
184	}
185
186	using UnaryRangeFn = llvm::function_ref<ConstantRange(const ConstantRange &)>;
187	using UnaryIntFn = llvm::function_ref<std::optional<APInt>(const APInt &)>;
188
189	static void TestUnaryOpExhaustive(UnaryRangeFn RangeFn, UnaryIntFn IntFn,
190	PreferFn PreferenceFn = PreferSmallest) {
191	EnumerateInterestingConstantRanges(TestFn: [&](const ConstantRange &CR) {
192	SmallBitVector Elems(1 << CR.getBitWidth());
193	ForeachNumInConstantRange(CR, TestFn: [&](const APInt &N) {
194	if (std::optional<APInt> ResultN = IntFn(N))
195	Elems.set(ResultN->getZExtValue());
196	});
197	TestRange(CR: RangeFn(CR), Elems, PreferenceFn, Inputs: {CR});
198	});
199	}
200
201	using BinaryRangeFn = llvm::function_ref<ConstantRange(const ConstantRange &,
202	const ConstantRange &)>;
203	using BinaryIntFn =
204	llvm::function_ref<std::optional<APInt>(const APInt &, const APInt &)>;
205	using BinaryCheckFn = llvm::function_ref<bool(const ConstantRange &,
206	const ConstantRange &)>;
207
208	static bool CheckAll(const ConstantRange &, const ConstantRange &) {
209	return true;
210	}
211
212	static bool CheckSingleElementsOnly(const ConstantRange &CR1,
213	const ConstantRange &CR2) {
214	return CR1.isSingleElement() && CR2.isSingleElement();
215	}
216
217	static bool CheckNonWrappedOnly(const ConstantRange &CR1,
218	const ConstantRange &CR2) {
219	return !CR1.isWrappedSet() && !CR2.isWrappedSet();
220	}
221
222	static bool CheckNonSignWrappedOnly(const ConstantRange &CR1,
223	const ConstantRange &CR2) {
224	return !CR1.isSignWrappedSet() && !CR2.isSignWrappedSet();
225	}
226
227	static bool CheckNonWrappedOrSignWrappedOnly(const ConstantRange &CR1,
228	const ConstantRange &CR2) {
229	return !CR1.isWrappedSet() && !CR1.isSignWrappedSet() &&
230	!CR2.isWrappedSet() && !CR2.isSignWrappedSet();
231	}
232
233	// CheckFn determines whether optimality is checked for a given range pair.
234	// Correctness is always checked.
235	static void TestBinaryOpExhaustive(BinaryRangeFn RangeFn, BinaryIntFn IntFn,
236	PreferFn PreferenceFn = PreferSmallest,
237	BinaryCheckFn CheckFn = CheckAll) {
238	EnumerateTwoInterestingConstantRanges(
239	TestFn: [&](const ConstantRange &CR1, const ConstantRange &CR2) {
240	SmallBitVector Elems(1 << CR1.getBitWidth());
241	ForeachNumInConstantRange(CR: CR1, TestFn: [&](const APInt &N1) {
242	ForeachNumInConstantRange(CR: CR2, TestFn: [&](const APInt &N2) {
243	if (std::optional<APInt> ResultN = IntFn(N1, N2))
244	Elems.set(ResultN->getZExtValue());
245	});
246	});
247	TestRange(CR: RangeFn(CR1, CR2), Elems, PreferenceFn, Inputs: {CR1, CR2},
248	CheckOptimality: CheckFn(CR1, CR2));
249	});
250	}
251
252	ConstantRange ConstantRangeTest::Full(16, true);
253	ConstantRange ConstantRangeTest::Empty(16, false);
254	ConstantRange ConstantRangeTest::One(APInt(16, 0xa));
255	ConstantRange ConstantRangeTest::Some(APInt(16, 0xa), APInt(16, 0xaaa));
256	ConstantRange ConstantRangeTest::Wrap(APInt(16, 0xaaa), APInt(16, 0xa));
257
258	TEST_F(ConstantRangeTest, Basics) {
259	EXPECT_TRUE(Full.isFullSet());
260	EXPECT_FALSE(Full.isEmptySet());
261	EXPECT_TRUE(Full.inverse().isEmptySet());
262	EXPECT_FALSE(Full.isWrappedSet());
263	EXPECT_TRUE(Full.contains(APInt(16, 0x0)));
264	EXPECT_TRUE(Full.contains(APInt(16, 0x9)));
265	EXPECT_TRUE(Full.contains(APInt(16, 0xa)));
266	EXPECT_TRUE(Full.contains(APInt(16, 0xaa9)));
267	EXPECT_TRUE(Full.contains(APInt(16, 0xaaa)));
268
269	EXPECT_FALSE(Empty.isFullSet());
270	EXPECT_TRUE(Empty.isEmptySet());
271	EXPECT_TRUE(Empty.inverse().isFullSet());
272	EXPECT_FALSE(Empty.isWrappedSet());
273	EXPECT_FALSE(Empty.contains(APInt(16, 0x0)));
274	EXPECT_FALSE(Empty.contains(APInt(16, 0x9)));
275	EXPECT_FALSE(Empty.contains(APInt(16, 0xa)));
276	EXPECT_FALSE(Empty.contains(APInt(16, 0xaa9)));
277	EXPECT_FALSE(Empty.contains(APInt(16, 0xaaa)));
278
279	EXPECT_FALSE(One.isFullSet());
280	EXPECT_FALSE(One.isEmptySet());
281	EXPECT_FALSE(One.isWrappedSet());
282	EXPECT_FALSE(One.contains(APInt(16, 0x0)));
283	EXPECT_FALSE(One.contains(APInt(16, 0x9)));
284	EXPECT_TRUE(One.contains(APInt(16, 0xa)));
285	EXPECT_FALSE(One.contains(APInt(16, 0xaa9)));
286	EXPECT_FALSE(One.contains(APInt(16, 0xaaa)));
287	EXPECT_FALSE(One.inverse().contains(APInt(16, 0xa)));
288
289	EXPECT_FALSE(Some.isFullSet());
290	EXPECT_FALSE(Some.isEmptySet());
291	EXPECT_FALSE(Some.isWrappedSet());
292	EXPECT_FALSE(Some.contains(APInt(16, 0x0)));
293	EXPECT_FALSE(Some.contains(APInt(16, 0x9)));
294	EXPECT_TRUE(Some.contains(APInt(16, 0xa)));
295	EXPECT_TRUE(Some.contains(APInt(16, 0xaa9)));
296	EXPECT_FALSE(Some.contains(APInt(16, 0xaaa)));
297
298	EXPECT_FALSE(Wrap.isFullSet());
299	EXPECT_FALSE(Wrap.isEmptySet());
300	EXPECT_TRUE(Wrap.isWrappedSet());
301	EXPECT_TRUE(Wrap.contains(APInt(16, 0x0)));
302	EXPECT_TRUE(Wrap.contains(APInt(16, 0x9)));
303	EXPECT_FALSE(Wrap.contains(APInt(16, 0xa)));
304	EXPECT_FALSE(Wrap.contains(APInt(16, 0xaa9)));
305	EXPECT_TRUE(Wrap.contains(APInt(16, 0xaaa)));
306	}
307
308	TEST_F(ConstantRangeTest, Equality) {
309	EXPECT_EQ(Full, Full);
310	EXPECT_EQ(Empty, Empty);
311	EXPECT_EQ(One, One);
312	EXPECT_EQ(Some, Some);
313	EXPECT_EQ(Wrap, Wrap);
314	EXPECT_NE(Full, Empty);
315	EXPECT_NE(Full, One);
316	EXPECT_NE(Full, Some);
317	EXPECT_NE(Full, Wrap);
318	EXPECT_NE(Empty, One);
319	EXPECT_NE(Empty, Some);
320	EXPECT_NE(Empty, Wrap);
321	EXPECT_NE(One, Some);
322	EXPECT_NE(One, Wrap);
323	EXPECT_NE(Some, Wrap);
324	}
325
326	TEST_F(ConstantRangeTest, SingleElement) {
327	EXPECT_EQ(Full.getSingleElement(), static_cast<APInt *>(nullptr));
328	EXPECT_EQ(Empty.getSingleElement(), static_cast<APInt *>(nullptr));
329	EXPECT_EQ(Full.getSingleMissingElement(), static_cast<APInt *>(nullptr));
330	EXPECT_EQ(Empty.getSingleMissingElement(), static_cast<APInt *>(nullptr));
331
332	EXPECT_EQ(*One.getSingleElement(), APInt(16, 0xa));
333	EXPECT_EQ(Some.getSingleElement(), static_cast<APInt *>(nullptr));
334	EXPECT_EQ(Wrap.getSingleElement(), static_cast<APInt *>(nullptr));
335
336	EXPECT_EQ(One.getSingleMissingElement(), static_cast<APInt *>(nullptr));
337	EXPECT_EQ(Some.getSingleMissingElement(), static_cast<APInt *>(nullptr));
338
339	ConstantRange OneInverse = One.inverse();
340	EXPECT_EQ(*OneInverse.getSingleMissingElement(), *One.getSingleElement());
341
342	EXPECT_FALSE(Full.isSingleElement());
343	EXPECT_FALSE(Empty.isSingleElement());
344	EXPECT_TRUE(One.isSingleElement());
345	EXPECT_FALSE(Some.isSingleElement());
346	EXPECT_FALSE(Wrap.isSingleElement());
347	}
348
349	TEST_F(ConstantRangeTest, GetMinsAndMaxes) {
350	EXPECT_EQ(Full.getUnsignedMax(), APInt(16, UINT16_MAX));
351	EXPECT_EQ(One.getUnsignedMax(), APInt(16, 0xa));
352	EXPECT_EQ(Some.getUnsignedMax(), APInt(16, 0xaa9));
353	EXPECT_EQ(Wrap.getUnsignedMax(), APInt(16, UINT16_MAX));
354
355	EXPECT_EQ(Full.getUnsignedMin(), APInt(16, 0));
356	EXPECT_EQ(One.getUnsignedMin(), APInt(16, 0xa));
357	EXPECT_EQ(Some.getUnsignedMin(), APInt(16, 0xa));
358	EXPECT_EQ(Wrap.getUnsignedMin(), APInt(16, 0));
359
360	EXPECT_EQ(Full.getSignedMax(), APInt(16, INT16_MAX));
361	EXPECT_EQ(One.getSignedMax(), APInt(16, 0xa));
362	EXPECT_EQ(Some.getSignedMax(), APInt(16, 0xaa9));
363	EXPECT_EQ(Wrap.getSignedMax(), APInt(16, INT16_MAX));
364
365	EXPECT_EQ(Full.getSignedMin(), APInt(16, (uint64_t)INT16_MIN));
366	EXPECT_EQ(One.getSignedMin(), APInt(16, 0xa));
367	EXPECT_EQ(Some.getSignedMin(), APInt(16, 0xa));
368	EXPECT_EQ(Wrap.getSignedMin(), APInt(16, (uint64_t)INT16_MIN));
369
370	// Found by Klee
371	EXPECT_EQ(ConstantRange(APInt(4, 7), APInt(4, 0)).getSignedMax(),
372	APInt(4, 7));
373	}
374
375	TEST_F(ConstantRangeTest, SignWrapped) {
376	EXPECT_FALSE(Full.isSignWrappedSet());
377	EXPECT_FALSE(Empty.isSignWrappedSet());
378	EXPECT_FALSE(One.isSignWrappedSet());
379	EXPECT_FALSE(Some.isSignWrappedSet());
380	EXPECT_TRUE(Wrap.isSignWrappedSet());
381
382	EXPECT_FALSE(ConstantRange(APInt(8, 127), APInt(8, 128)).isSignWrappedSet());
383	EXPECT_TRUE(ConstantRange(APInt(8, 127), APInt(8, 129)).isSignWrappedSet());
384	EXPECT_FALSE(ConstantRange(APInt(8, 128), APInt(8, 129)).isSignWrappedSet());
385	EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 9)).isSignWrappedSet());
386	EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 250)).isSignWrappedSet());
387	EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 10)).isSignWrappedSet());
388	EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 251)).isSignWrappedSet());
389	}
390
391	TEST_F(ConstantRangeTest, UpperWrapped) {
392	// The behavior here is the same as for isWrappedSet() / isSignWrappedSet().
393	EXPECT_FALSE(Full.isUpperWrapped());
394	EXPECT_FALSE(Empty.isUpperWrapped());
395	EXPECT_FALSE(One.isUpperWrapped());
396	EXPECT_FALSE(Some.isUpperWrapped());
397	EXPECT_TRUE(Wrap.isUpperWrapped());
398	EXPECT_FALSE(Full.isUpperSignWrapped());
399	EXPECT_FALSE(Empty.isUpperSignWrapped());
400	EXPECT_FALSE(One.isUpperSignWrapped());
401	EXPECT_FALSE(Some.isUpperSignWrapped());
402	EXPECT_TRUE(Wrap.isUpperSignWrapped());
403
404	// The behavior differs if Upper is the Min/SignedMin value.
405	ConstantRange CR1(APInt(8, 42), APInt::getMinValue(numBits: 8));
406	EXPECT_FALSE(CR1.isWrappedSet());
407	EXPECT_TRUE(CR1.isUpperWrapped());
408
409	ConstantRange CR2(APInt(8, 42), APInt::getSignedMinValue(numBits: 8));
410	EXPECT_FALSE(CR2.isSignWrappedSet());
411	EXPECT_TRUE(CR2.isUpperSignWrapped());
412	}
413
414	TEST_F(ConstantRangeTest, Trunc) {
415	ConstantRange TFull = Full.truncate(BitWidth: 10);
416	ConstantRange TEmpty = Empty.truncate(BitWidth: 10);
417	ConstantRange TOne = One.truncate(BitWidth: 10);
418	ConstantRange TSome = Some.truncate(BitWidth: 10);
419	ConstantRange TWrap = Wrap.truncate(BitWidth: 10);
420	EXPECT_TRUE(TFull.isFullSet());
421	EXPECT_TRUE(TEmpty.isEmptySet());
422	EXPECT_EQ(TOne, ConstantRange(One.getLower().trunc(10),
423	One.getUpper().trunc(10)));
424	EXPECT_TRUE(TSome.isFullSet());
425	EXPECT_TRUE(TWrap.isFullSet());
426
427	// trunc([2, 5), 3->2) = [2, 1)
428	ConstantRange TwoFive(APInt(3, 2), APInt(3, 5));
429	EXPECT_EQ(TwoFive.truncate(2), ConstantRange(APInt(2, 2), APInt(2, 1)));
430
431	// trunc([2, 6), 3->2) = full
432	ConstantRange TwoSix(APInt(3, 2), APInt(3, 6));
433	EXPECT_TRUE(TwoSix.truncate(2).isFullSet());
434
435	// trunc([5, 7), 3->2) = [1, 3)
436	ConstantRange FiveSeven(APInt(3, 5), APInt(3, 7));
437	EXPECT_EQ(FiveSeven.truncate(2), ConstantRange(APInt(2, 1), APInt(2, 3)));
438
439	// trunc([7, 1), 3->2) = [3, 1)
440	ConstantRange SevenOne(APInt(3, 7), APInt(3, 1));
441	EXPECT_EQ(SevenOne.truncate(2), ConstantRange(APInt(2, 3), APInt(2, 1)));
442	}
443
444	TEST_F(ConstantRangeTest, ZExt) {
445	ConstantRange ZFull = Full.zeroExtend(BitWidth: 20);
446	ConstantRange ZEmpty = Empty.zeroExtend(BitWidth: 20);
447	ConstantRange ZOne = One.zeroExtend(BitWidth: 20);
448	ConstantRange ZSome = Some.zeroExtend(BitWidth: 20);
449	ConstantRange ZWrap = Wrap.zeroExtend(BitWidth: 20);
450	EXPECT_EQ(ZFull, ConstantRange(APInt(20, 0), APInt(20, 0x10000)));
451	EXPECT_TRUE(ZEmpty.isEmptySet());
452	EXPECT_EQ(ZOne, ConstantRange(One.getLower().zext(20),
453	One.getUpper().zext(20)));
454	EXPECT_EQ(ZSome, ConstantRange(Some.getLower().zext(20),
455	Some.getUpper().zext(20)));
456	EXPECT_EQ(ZWrap, ConstantRange(APInt(20, 0), APInt(20, 0x10000)));
457
458	// zext([5, 0), 3->7) = [5, 8)
459	ConstantRange FiveZero(APInt(3, 5), APInt(3, 0));
460	EXPECT_EQ(FiveZero.zeroExtend(7), ConstantRange(APInt(7, 5), APInt(7, 8)));
461	}
462
463	TEST_F(ConstantRangeTest, SExt) {
464	ConstantRange SFull = Full.signExtend(BitWidth: 20);
465	ConstantRange SEmpty = Empty.signExtend(BitWidth: 20);
466	ConstantRange SOne = One.signExtend(BitWidth: 20);
467	ConstantRange SSome = Some.signExtend(BitWidth: 20);
468	ConstantRange SWrap = Wrap.signExtend(BitWidth: 20);
469	EXPECT_EQ(SFull, ConstantRange(APInt(20, (uint64_t)INT16_MIN, true),
470	APInt(20, INT16_MAX + 1, true)));
471	EXPECT_TRUE(SEmpty.isEmptySet());
472	EXPECT_EQ(SOne, ConstantRange(One.getLower().sext(20),
473	One.getUpper().sext(20)));
474	EXPECT_EQ(SSome, ConstantRange(Some.getLower().sext(20),
475	Some.getUpper().sext(20)));
476	EXPECT_EQ(SWrap, ConstantRange(APInt(20, (uint64_t)INT16_MIN, true),
477	APInt(20, INT16_MAX + 1, true)));
478
479	EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, 140)).signExtend(16),
480	ConstantRange(APInt(16, -128), APInt(16, 128)));
481
482	EXPECT_EQ(ConstantRange(APInt(16, 0x0200), APInt(16, 0x8000)).signExtend(19),
483	ConstantRange(APInt(19, 0x0200), APInt(19, 0x8000)));
484	}
485
486	TEST_F(ConstantRangeTest, IntersectWith) {
487	EXPECT_EQ(Empty.intersectWith(Full), Empty);
488	EXPECT_EQ(Empty.intersectWith(Empty), Empty);
489	EXPECT_EQ(Empty.intersectWith(One), Empty);
490	EXPECT_EQ(Empty.intersectWith(Some), Empty);
491	EXPECT_EQ(Empty.intersectWith(Wrap), Empty);
492	EXPECT_EQ(Full.intersectWith(Full), Full);
493	EXPECT_EQ(Some.intersectWith(Some), Some);
494	EXPECT_EQ(Some.intersectWith(One), One);
495	EXPECT_EQ(Full.intersectWith(One), One);
496	EXPECT_EQ(Full.intersectWith(Some), Some);
497	EXPECT_EQ(Some.intersectWith(Wrap), Empty);
498	EXPECT_EQ(One.intersectWith(Wrap), Empty);
499	EXPECT_EQ(One.intersectWith(Wrap), Wrap.intersectWith(One));
500
501	// Klee generated testcase from PR4545.
502	// The intersection of i16 [4, 2) and [6, 5) is disjoint, looking like
503	// 01..4.6789ABCDEF where the dots represent values not in the intersection.
504	ConstantRange LHS(APInt(16, 4), APInt(16, 2));
505	ConstantRange RHS(APInt(16, 6), APInt(16, 5));
506	EXPECT_TRUE(LHS.intersectWith(RHS) == LHS);
507
508	// previous bug: intersection of [min, 3) and [2, max) should be 2
509	LHS = ConstantRange(APInt(32, -2147483646), APInt(32, 3));
510	RHS = ConstantRange(APInt(32, 2), APInt(32, 2147483646));
511	EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 2)));
512
513	// [2, 0) /\ [4, 3) = [2, 0)
514	LHS = ConstantRange(APInt(32, 2), APInt(32, 0));
515	RHS = ConstantRange(APInt(32, 4), APInt(32, 3));
516	EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 2), APInt(32, 0)));
517
518	// [2, 0) /\ [4, 2) = [4, 0)
519	LHS = ConstantRange(APInt(32, 2), APInt(32, 0));
520	RHS = ConstantRange(APInt(32, 4), APInt(32, 2));
521	EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 0)));
522
523	// [4, 2) /\ [5, 1) = [5, 1)
524	LHS = ConstantRange(APInt(32, 4), APInt(32, 2));
525	RHS = ConstantRange(APInt(32, 5), APInt(32, 1));
526	EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 5), APInt(32, 1)));
527
528	// [2, 0) /\ [7, 4) = [7, 4)
529	LHS = ConstantRange(APInt(32, 2), APInt(32, 0));
530	RHS = ConstantRange(APInt(32, 7), APInt(32, 4));
531	EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 7), APInt(32, 4)));
532
533	// [4, 2) /\ [1, 0) = [1, 0)
534	LHS = ConstantRange(APInt(32, 4), APInt(32, 2));
535	RHS = ConstantRange(APInt(32, 1), APInt(32, 0));
536	EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 2)));
537
538	// [15, 0) /\ [7, 6) = [15, 0)
539	LHS = ConstantRange(APInt(32, 15), APInt(32, 0));
540	RHS = ConstantRange(APInt(32, 7), APInt(32, 6));
541	EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 15), APInt(32, 0)));
542	}
543
544	template <typename Fn1, typename Fn2, typename Fn3>
545	void testBinarySetOperationExhaustive(Fn1 OpFn, Fn2 ExactOpFn, Fn3 InResultFn) {
546	EnumerateTwoInterestingConstantRanges(
547	[=](const ConstantRange &CR1, const ConstantRange &CR2) {
548	unsigned Bits = CR1.getBitWidth();
549	SmallBitVector Elems(1 << Bits);
550	APInt Num(Bits, 0);
551	for (unsigned I = 0, Limit = 1 << Bits; I < Limit; ++I, ++Num)
552	if (InResultFn(CR1, CR2, Num))
553	Elems.set(Num.getZExtValue());
554
555	ConstantRange SmallestCR = OpFn(CR1, CR2, ConstantRange::Smallest);
556	TestRange(CR: SmallestCR, Elems, PreferenceFn: PreferSmallest, Inputs: {CR1, CR2});
557
558	ConstantRange UnsignedCR = OpFn(CR1, CR2, ConstantRange::Unsigned);
559	TestRange(CR: UnsignedCR, Elems, PreferenceFn: PreferSmallestNonFullUnsigned, Inputs: {CR1, CR2});
560
561	ConstantRange SignedCR = OpFn(CR1, CR2, ConstantRange::Signed);
562	TestRange(CR: SignedCR, Elems, PreferenceFn: PreferSmallestNonFullSigned, Inputs: {CR1, CR2});
563
564	std::optional<ConstantRange> ExactCR = ExactOpFn(CR1, CR2);
565	if (SmallestCR.isSizeLargerThan(MaxSize: Elems.count())) {
566	EXPECT_TRUE(!ExactCR);
567	} else {
568	EXPECT_EQ(SmallestCR, *ExactCR);
569	}
570	});
571	}
572
573	TEST_F(ConstantRangeTest, IntersectWithExhaustive) {
574	testBinarySetOperationExhaustive(
575	OpFn: [](const ConstantRange &CR1, const ConstantRange &CR2,
576	ConstantRange::PreferredRangeType Type) {
577	return CR1.intersectWith(CR: CR2, Type);
578	},
579	ExactOpFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
580	return CR1.exactIntersectWith(CR: CR2);
581	},
582	InResultFn: [](const ConstantRange &CR1, const ConstantRange &CR2, const APInt &N) {
583	return CR1.contains(Val: N) && CR2.contains(Val: N);
584	});
585	}
586
587	TEST_F(ConstantRangeTest, UnionWithExhaustive) {
588	testBinarySetOperationExhaustive(
589	OpFn: [](const ConstantRange &CR1, const ConstantRange &CR2,
590	ConstantRange::PreferredRangeType Type) {
591	return CR1.unionWith(CR: CR2, Type);
592	},
593	ExactOpFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
594	return CR1.exactUnionWith(CR: CR2);
595	},
596	InResultFn: [](const ConstantRange &CR1, const ConstantRange &CR2, const APInt &N) {
597	return CR1.contains(Val: N) || CR2.contains(Val: N);
598	});
599	}
600
601	TEST_F(ConstantRangeTest, UnionWith) {
602	EXPECT_EQ(Wrap.unionWith(One),
603	ConstantRange(APInt(16, 0xaaa), APInt(16, 0xb)));
604	EXPECT_EQ(One.unionWith(Wrap), Wrap.unionWith(One));
605	EXPECT_EQ(Empty.unionWith(Empty), Empty);
606	EXPECT_EQ(Full.unionWith(Full), Full);
607	EXPECT_EQ(Some.unionWith(Wrap), Full);
608
609	// PR4545
610	EXPECT_EQ(ConstantRange(APInt(16, 14), APInt(16, 1)).unionWith(
611	ConstantRange(APInt(16, 0), APInt(16, 8))),
612	ConstantRange(APInt(16, 14), APInt(16, 8)));
613	EXPECT_EQ(ConstantRange(APInt(16, 6), APInt(16, 4)).unionWith(
614	ConstantRange(APInt(16, 4), APInt(16, 0))),
615	ConstantRange::getFull(16));
616	EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 0)).unionWith(
617	ConstantRange(APInt(16, 2), APInt(16, 1))),
618	ConstantRange::getFull(16));
619	}
620
621	TEST_F(ConstantRangeTest, SetDifference) {
622	EXPECT_EQ(Full.difference(Empty), Full);
623	EXPECT_EQ(Full.difference(Full), Empty);
624	EXPECT_EQ(Empty.difference(Empty), Empty);
625	EXPECT_EQ(Empty.difference(Full), Empty);
626
627	ConstantRange A(APInt(16, 3), APInt(16, 7));
628	ConstantRange B(APInt(16, 5), APInt(16, 9));
629	ConstantRange C(APInt(16, 3), APInt(16, 5));
630	ConstantRange D(APInt(16, 7), APInt(16, 9));
631	ConstantRange E(APInt(16, 5), APInt(16, 4));
632	ConstantRange F(APInt(16, 7), APInt(16, 3));
633	EXPECT_EQ(A.difference(B), C);
634	EXPECT_EQ(B.difference(A), D);
635	EXPECT_EQ(E.difference(A), F);
636	}
637
638	TEST_F(ConstantRangeTest, getActiveBits) {
639	EnumerateInterestingConstantRanges(TestFn: [&](const ConstantRange &CR) {
640	unsigned Exact = 0;
641	ForeachNumInConstantRange(CR, TestFn: [&](const APInt &N) {
642	Exact = std::max(a: Exact, b: N.getActiveBits());
643	});
644
645	unsigned ResultCR = CR.getActiveBits();
646	EXPECT_EQ(Exact, ResultCR);
647	});
648	}
649	TEST_F(ConstantRangeTest, losslessUnsignedTruncationZeroext) {
650	EnumerateInterestingConstantRanges(TestFn: [&](const ConstantRange &CR) {
651	unsigned Bits = CR.getBitWidth();
652	unsigned MinBitWidth = CR.getActiveBits();
653	if (MinBitWidth == 0) {
654	EXPECT_TRUE(CR.isEmptySet() ||
655	(CR.isSingleElement() && CR.getSingleElement()->isZero()));
656	return;
657	}
658	if (MinBitWidth == Bits)
659	return;
660	EXPECT_EQ(CR, CR.truncate(MinBitWidth).zeroExtend(Bits));
661	});
662	}
663
664	TEST_F(ConstantRangeTest, getMinSignedBits) {
665	EnumerateInterestingConstantRanges(TestFn: [&](const ConstantRange &CR) {
666	unsigned Exact = 0;
667	ForeachNumInConstantRange(CR, TestFn: [&](const APInt &N) {
668	Exact = std::max(a: Exact, b: N.getSignificantBits());
669	});
670
671	unsigned ResultCR = CR.getMinSignedBits();
672	EXPECT_EQ(Exact, ResultCR);
673	});
674	}
675	TEST_F(ConstantRangeTest, losslessSignedTruncationSignext) {
676	EnumerateInterestingConstantRanges(TestFn: [&](const ConstantRange &CR) {
677	unsigned Bits = CR.getBitWidth();
678	unsigned MinBitWidth = CR.getMinSignedBits();
679	if (MinBitWidth == 0) {
680	EXPECT_TRUE(CR.isEmptySet());
681	return;
682	}
683	if (MinBitWidth == Bits)
684	return;
685	EXPECT_EQ(CR, CR.truncate(MinBitWidth).signExtend(Bits));
686	});
687	}
688
689	TEST_F(ConstantRangeTest, SubtractAPInt) {
690	EXPECT_EQ(Full.subtract(APInt(16, 4)), Full);
691	EXPECT_EQ(Empty.subtract(APInt(16, 4)), Empty);
692	EXPECT_EQ(Some.subtract(APInt(16, 4)),
693	ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6)));
694	EXPECT_EQ(Wrap.subtract(APInt(16, 4)),
695	ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6)));
696	EXPECT_EQ(One.subtract(APInt(16, 4)),
697	ConstantRange(APInt(16, 0x6)));
698	}
699
700	TEST_F(ConstantRangeTest, Add) {
701	EXPECT_EQ(Full.add(APInt(16, 4)), Full);
702	EXPECT_EQ(Full.add(Full), Full);
703	EXPECT_EQ(Full.add(Empty), Empty);
704	EXPECT_EQ(Full.add(One), Full);
705	EXPECT_EQ(Full.add(Some), Full);
706	EXPECT_EQ(Full.add(Wrap), Full);
707	EXPECT_EQ(Empty.add(Empty), Empty);
708	EXPECT_EQ(Empty.add(One), Empty);
709	EXPECT_EQ(Empty.add(Some), Empty);
710	EXPECT_EQ(Empty.add(Wrap), Empty);
711	EXPECT_EQ(Empty.add(APInt(16, 4)), Empty);
712	EXPECT_EQ(Some.add(APInt(16, 4)),
713	ConstantRange(APInt(16, 0xe), APInt(16, 0xaae)));
714	EXPECT_EQ(Wrap.add(APInt(16, 4)),
715	ConstantRange(APInt(16, 0xaae), APInt(16, 0xe)));
716	EXPECT_EQ(One.add(APInt(16, 4)),
717	ConstantRange(APInt(16, 0xe)));
718
719	TestBinaryOpExhaustive(
720	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
721	return CR1.add(Other: CR2);
722	},
723	IntFn: [](const APInt &N1, const APInt &N2) {
724	return N1 + N2;
725	});
726	}
727
728	TEST_F(ConstantRangeTest, AddWithNoWrap) {
729	typedef OverflowingBinaryOperator OBO;
730	EXPECT_EQ(Empty.addWithNoWrap(Some, OBO::NoSignedWrap), Empty);
731	EXPECT_EQ(Some.addWithNoWrap(Empty, OBO::NoSignedWrap), Empty);
732	EXPECT_EQ(Full.addWithNoWrap(Full, OBO::NoSignedWrap), Full);
733	EXPECT_NE(Full.addWithNoWrap(Some, OBO::NoSignedWrap), Full);
734	EXPECT_NE(Some.addWithNoWrap(Full, OBO::NoSignedWrap), Full);
735	EXPECT_EQ(Full.addWithNoWrap(ConstantRange(APInt(16, 1), APInt(16, 2)),
736	OBO::NoSignedWrap),
737	ConstantRange(APInt(16, INT16_MIN + 1), APInt(16, INT16_MIN)));
738	EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 2))
739	.addWithNoWrap(Full, OBO::NoSignedWrap),
740	ConstantRange(APInt(16, INT16_MIN + 1), APInt(16, INT16_MIN)));
741	EXPECT_EQ(Full.addWithNoWrap(ConstantRange(APInt(16, -1), APInt(16, 0)),
742	OBO::NoSignedWrap),
743	ConstantRange(APInt(16, INT16_MIN), APInt(16, INT16_MAX)));
744	EXPECT_EQ(ConstantRange(APInt(8, 100), APInt(8, 120))
745	.addWithNoWrap(ConstantRange(APInt(8, 120), APInt(8, 123)),
746	OBO::NoSignedWrap),
747	ConstantRange(8, false));
748	EXPECT_EQ(ConstantRange(APInt(8, -120), APInt(8, -100))
749	.addWithNoWrap(ConstantRange(APInt(8, -110), APInt(8, -100)),
750	OBO::NoSignedWrap),
751	ConstantRange(8, false));
752	EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
753	.addWithNoWrap(ConstantRange(APInt(8, -128), APInt(8, 28)),
754	OBO::NoSignedWrap),
755	ConstantRange(8, true));
756	EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
757	.addWithNoWrap(ConstantRange(APInt(8, -120), APInt(8, 29)),
758	OBO::NoSignedWrap),
759	ConstantRange(APInt(8, -120), APInt(8, -128)));
760	EXPECT_EQ(ConstantRange(APInt(8, -50), APInt(8, 50))
761	.addWithNoWrap(ConstantRange(APInt(8, 10), APInt(8, 20)),
762	OBO::NoSignedWrap),
763	ConstantRange(APInt(8, -40), APInt(8, 69)));
764	EXPECT_EQ(ConstantRange(APInt(8, 10), APInt(8, 20))
765	.addWithNoWrap(ConstantRange(APInt(8, -50), APInt(8, 50)),
766	OBO::NoSignedWrap),
767	ConstantRange(APInt(8, -40), APInt(8, 69)));
768	EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -10))
769	.addWithNoWrap(ConstantRange(APInt(8, 5), APInt(8, 20)),
770	OBO::NoSignedWrap),
771	ConstantRange(APInt(8, 125), APInt(8, 9)));
772	EXPECT_EQ(ConstantRange(APInt(8, 5), APInt(8, 20))
773	.addWithNoWrap(ConstantRange(APInt(8, 120), APInt(8, -10)),
774	OBO::NoSignedWrap),
775	ConstantRange(APInt(8, 125), APInt(8, 9)));
776
777	TestBinaryOpExhaustive(
778	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
779	return CR1.addWithNoWrap(Other: CR2, NoWrapKind: OBO::NoSignedWrap);
780	},
781	IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
782	bool IsOverflow;
783	APInt Res = N1.sadd_ov(RHS: N2, Overflow&: IsOverflow);
784	if (IsOverflow)
785	return std::nullopt;
786	return Res;
787	},
788	PreferenceFn: PreferSmallest, CheckFn: CheckNonSignWrappedOnly);
789
790	EXPECT_EQ(Empty.addWithNoWrap(Some, OBO::NoUnsignedWrap), Empty);
791	EXPECT_EQ(Some.addWithNoWrap(Empty, OBO::NoUnsignedWrap), Empty);
792	EXPECT_EQ(Full.addWithNoWrap(Full, OBO::NoUnsignedWrap), Full);
793	EXPECT_NE(Full.addWithNoWrap(Some, OBO::NoUnsignedWrap), Full);
794	EXPECT_NE(Some.addWithNoWrap(Full, OBO::NoUnsignedWrap), Full);
795	EXPECT_EQ(Full.addWithNoWrap(ConstantRange(APInt(16, 1), APInt(16, 2)),
796	OBO::NoUnsignedWrap),
797	ConstantRange(APInt(16, 1), APInt(16, 0)));
798	EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 2))
799	.addWithNoWrap(Full, OBO::NoUnsignedWrap),
800	ConstantRange(APInt(16, 1), APInt(16, 0)));
801	EXPECT_EQ(ConstantRange(APInt(8, 200), APInt(8, 220))
802	.addWithNoWrap(ConstantRange(APInt(8, 100), APInt(8, 123)),
803	OBO::NoUnsignedWrap),
804	ConstantRange(8, false));
805	EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
806	.addWithNoWrap(ConstantRange(APInt(8, 0), APInt(8, 156)),
807	OBO::NoUnsignedWrap),
808	ConstantRange(8, true));
809	EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
810	.addWithNoWrap(ConstantRange(APInt(8, 10), APInt(8, 29)),
811	OBO::NoUnsignedWrap),
812	ConstantRange(APInt(8, 10), APInt(8, 129)));
813	EXPECT_EQ(ConstantRange(APInt(8, 20), APInt(8, 10))
814	.addWithNoWrap(ConstantRange(APInt(8, 50), APInt(8, 200)),
815	OBO::NoUnsignedWrap),
816	ConstantRange(APInt(8, 50), APInt(8, 0)));
817	EXPECT_EQ(ConstantRange(APInt(8, 10), APInt(8, 20))
818	.addWithNoWrap(ConstantRange(APInt(8, 50), APInt(8, 200)),
819	OBO::NoUnsignedWrap),
820	ConstantRange(APInt(8, 60), APInt(8, -37)));
821	EXPECT_EQ(ConstantRange(APInt(8, 20), APInt(8, -30))
822	.addWithNoWrap(ConstantRange(APInt(8, 5), APInt(8, 20)),
823	OBO::NoUnsignedWrap),
824	ConstantRange(APInt(8, 25), APInt(8, -11)));
825	EXPECT_EQ(ConstantRange(APInt(8, 5), APInt(8, 20))
826	.addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, -30)),
827	OBO::NoUnsignedWrap),
828	ConstantRange(APInt(8, 25), APInt(8, -11)));
829
830	TestBinaryOpExhaustive(
831	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
832	return CR1.addWithNoWrap(Other: CR2, NoWrapKind: OBO::NoUnsignedWrap);
833	},
834	IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
835	bool IsOverflow;
836	APInt Res = N1.uadd_ov(RHS: N2, Overflow&: IsOverflow);
837	if (IsOverflow)
838	return std::nullopt;
839	return Res;
840	},
841	PreferenceFn: PreferSmallest, CheckFn: CheckNonWrappedOnly);
842
843	EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100))
844	.addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)),
845	OBO::NoSignedWrap),
846	ConstantRange(APInt(8, 70), APInt(8, -128)));
847	EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100))
848	.addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)),
849	OBO::NoUnsignedWrap),
850	ConstantRange(APInt(8, 70), APInt(8, 169)));
851	EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100))
852	.addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)),
853	OBO::NoUnsignedWrap | OBO::NoSignedWrap),
854	ConstantRange(APInt(8, 70), APInt(8, -128)));
855
856	EXPECT_EQ(ConstantRange(APInt(8, -100), APInt(8, -50))
857	.addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)),
858	OBO::NoSignedWrap),
859	ConstantRange(APInt(8, -80), APInt(8, -21)));
860	EXPECT_EQ(ConstantRange(APInt(8, -100), APInt(8, -50))
861	.addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)),
862	OBO::NoUnsignedWrap),
863	ConstantRange(APInt(8, 176), APInt(8, 235)));
864	EXPECT_EQ(ConstantRange(APInt(8, -100), APInt(8, -50))
865	.addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)),
866	OBO::NoUnsignedWrap | OBO::NoSignedWrap),
867	ConstantRange(APInt(8, 176), APInt(8, 235)));
868
869	TestBinaryOpExhaustive(
870	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
871	return CR1.addWithNoWrap(Other: CR2, NoWrapKind: OBO::NoUnsignedWrap | OBO::NoSignedWrap);
872	},
873	IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
874	bool IsOverflow1, IsOverflow2;
875	APInt Res1 = N1.uadd_ov(RHS: N2, Overflow&: IsOverflow1);
876	APInt Res2 = N1.sadd_ov(RHS: N2, Overflow&: IsOverflow2);
877	if (IsOverflow1 || IsOverflow2)
878	return std::nullopt;
879	assert(Res1 == Res2 && "Addition results differ?");
880	return Res1;
881	},
882	PreferenceFn: PreferSmallest, CheckFn: CheckNonWrappedOrSignWrappedOnly);
883	}
884
885	TEST_F(ConstantRangeTest, Sub) {
886	EXPECT_EQ(Full.sub(APInt(16, 4)), Full);
887	EXPECT_EQ(Full.sub(Full), Full);
888	EXPECT_EQ(Full.sub(Empty), Empty);
889	EXPECT_EQ(Full.sub(One), Full);
890	EXPECT_EQ(Full.sub(Some), Full);
891	EXPECT_EQ(Full.sub(Wrap), Full);
892	EXPECT_EQ(Empty.sub(Empty), Empty);
893	EXPECT_EQ(Empty.sub(One), Empty);
894	EXPECT_EQ(Empty.sub(Some), Empty);
895	EXPECT_EQ(Empty.sub(Wrap), Empty);
896	EXPECT_EQ(Empty.sub(APInt(16, 4)), Empty);
897	EXPECT_EQ(Some.sub(APInt(16, 4)),
898	ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6)));
899	EXPECT_EQ(Some.sub(Some),
900	ConstantRange(APInt(16, 0xf561), APInt(16, 0xaa0)));
901	EXPECT_EQ(Wrap.sub(APInt(16, 4)),
902	ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6)));
903	EXPECT_EQ(One.sub(APInt(16, 4)),
904	ConstantRange(APInt(16, 0x6)));
905
906	TestBinaryOpExhaustive(
907	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
908	return CR1.sub(Other: CR2);
909	},
910	IntFn: [](const APInt &N1, const APInt &N2) {
911	return N1 - N2;
912	});
913	}
914
915	TEST_F(ConstantRangeTest, SubWithNoWrap) {
916	typedef OverflowingBinaryOperator OBO;
917	TestBinaryOpExhaustive(
918	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
919	return CR1.subWithNoWrap(Other: CR2, NoWrapKind: OBO::NoSignedWrap);
920	},
921	IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
922	bool IsOverflow;
923	APInt Res = N1.ssub_ov(RHS: N2, Overflow&: IsOverflow);
924	if (IsOverflow)
925	return std::nullopt;
926	return Res;
927	},
928	PreferenceFn: PreferSmallest, CheckFn: CheckNonSignWrappedOnly);
929	TestBinaryOpExhaustive(
930	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
931	return CR1.subWithNoWrap(Other: CR2, NoWrapKind: OBO::NoUnsignedWrap);
932	},
933	IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
934	bool IsOverflow;
935	APInt Res = N1.usub_ov(RHS: N2, Overflow&: IsOverflow);
936	if (IsOverflow)
937	return std::nullopt;
938	return Res;
939	},
940	PreferenceFn: PreferSmallest, CheckFn: CheckNonWrappedOnly);
941	TestBinaryOpExhaustive(
942	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
943	return CR1.subWithNoWrap(Other: CR2, NoWrapKind: OBO::NoUnsignedWrap | OBO::NoSignedWrap);
944	},
945	IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
946	bool IsOverflow1, IsOverflow2;
947	APInt Res1 = N1.usub_ov(RHS: N2, Overflow&: IsOverflow1);
948	APInt Res2 = N1.ssub_ov(RHS: N2, Overflow&: IsOverflow2);
949	if (IsOverflow1 || IsOverflow2)
950	return std::nullopt;
951	assert(Res1 == Res2 && "Subtraction results differ?");
952	return Res1;
953	},
954	PreferenceFn: PreferSmallest, CheckFn: CheckNonWrappedOrSignWrappedOnly);
955	}
956
957	TEST_F(ConstantRangeTest, Multiply) {
958	EXPECT_EQ(Full.multiply(Full), Full);
959	EXPECT_EQ(Full.multiply(Empty), Empty);
960	EXPECT_EQ(Full.multiply(One), Full);
961	EXPECT_EQ(Full.multiply(Some), Full);
962	EXPECT_EQ(Full.multiply(Wrap), Full);
963	EXPECT_EQ(Empty.multiply(Empty), Empty);
964	EXPECT_EQ(Empty.multiply(One), Empty);
965	EXPECT_EQ(Empty.multiply(Some), Empty);
966	EXPECT_EQ(Empty.multiply(Wrap), Empty);
967	EXPECT_EQ(One.multiply(One), ConstantRange(APInt(16, 0xa*0xa),
968	APInt(16, 0xa*0xa + 1)));
969	EXPECT_EQ(One.multiply(Some), ConstantRange(APInt(16, 0xa*0xa),
970	APInt(16, 0xa*0xaa9 + 1)));
971	EXPECT_EQ(One.multiply(Wrap), Full);
972	EXPECT_EQ(Some.multiply(Some), Full);
973	EXPECT_EQ(Some.multiply(Wrap), Full);
974	EXPECT_EQ(Wrap.multiply(Wrap), Full);
975
976	ConstantRange Zero(APInt(16, 0));
977	EXPECT_EQ(Zero.multiply(Full), Zero);
978	EXPECT_EQ(Zero.multiply(Some), Zero);
979	EXPECT_EQ(Zero.multiply(Wrap), Zero);
980	EXPECT_EQ(Full.multiply(Zero), Zero);
981	EXPECT_EQ(Some.multiply(Zero), Zero);
982	EXPECT_EQ(Wrap.multiply(Zero), Zero);
983
984	// http://llvm.org/PR4545
985	EXPECT_EQ(ConstantRange(APInt(4, 1), APInt(4, 6)).multiply(
986	ConstantRange(APInt(4, 6), APInt(4, 2))),
987	ConstantRange(4, /*isFullSet=*/true));
988
989	EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 0)).multiply(
990	ConstantRange(APInt(8, 252), APInt(8, 4))),
991	ConstantRange(APInt(8, 250), APInt(8, 9)));
992	EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 255)).multiply(
993	ConstantRange(APInt(8, 2), APInt(8, 4))),
994	ConstantRange(APInt(8, 250), APInt(8, 253)));
995
996	// TODO: This should be return [-2, 0]
997	EXPECT_EQ(ConstantRange(APInt(8, -2)).multiply(
998	ConstantRange(APInt(8, 0), APInt(8, 2))),
999	ConstantRange(APInt(8, -2), APInt(8, 1)));
1000
1001	// Multiplication by -1 should give precise results.
1002	EXPECT_EQ(ConstantRange(APInt(8, 3), APInt(8, -11))
1003	.multiply(ConstantRange(APInt(8, -1))),
1004	ConstantRange(APInt(8, 12), APInt(8, -2)));
1005	EXPECT_EQ(ConstantRange(APInt(8, -1))
1006	.multiply(ConstantRange(APInt(8, 3), APInt(8, -11))),
1007	ConstantRange(APInt(8, 12), APInt(8, -2)));
1008
1009	TestBinaryOpExhaustive(
1010	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
1011	return CR1.multiply(Other: CR2);
1012	},
1013	IntFn: [](const APInt &N1, const APInt &N2) {
1014	return N1 * N2;
1015	},
1016	PreferenceFn: PreferSmallest,
1017	CheckFn: [](const ConstantRange &, const ConstantRange &) {
1018	return false; // Check correctness only.
1019	});
1020	}
1021
1022	TEST_F(ConstantRangeTest, smul_fast) {
1023	TestBinaryOpExhaustive(
1024	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
1025	return CR1.smul_fast(Other: CR2);
1026	},
1027	IntFn: [](const APInt &N1, const APInt &N2) {
1028	return N1 * N2;
1029	},
1030	PreferenceFn: PreferSmallest,
1031	CheckFn: [](const ConstantRange &, const ConstantRange &) {
1032	return false; // Check correctness only.
1033	});
1034	}
1035
1036	TEST_F(ConstantRangeTest, UMax) {
1037	EXPECT_EQ(Full.umax(Full), Full);
1038	EXPECT_EQ(Full.umax(Empty), Empty);
1039	EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
1040	EXPECT_EQ(Full.umax(Wrap), Full);
1041	EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
1042	EXPECT_EQ(Empty.umax(Empty), Empty);
1043	EXPECT_EQ(Empty.umax(Some), Empty);
1044	EXPECT_EQ(Empty.umax(Wrap), Empty);
1045	EXPECT_EQ(Empty.umax(One), Empty);
1046	EXPECT_EQ(Some.umax(Some), Some);
1047	EXPECT_EQ(Some.umax(Wrap), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
1048	EXPECT_EQ(Some.umax(One), Some);
1049	EXPECT_EQ(Wrap.umax(Wrap), Wrap);
1050	EXPECT_EQ(Wrap.umax(One), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
1051	EXPECT_EQ(One.umax(One), One);
1052
1053	TestBinaryOpExhaustive(
1054	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
1055	return CR1.umax(Other: CR2);
1056	},
1057	IntFn: [](const APInt &N1, const APInt &N2) {
1058	return APIntOps::umax(A: N1, B: N2);
1059	},
1060	PreferenceFn: PreferSmallestNonFullUnsigned);
1061	}
1062
1063	TEST_F(ConstantRangeTest, SMax) {
1064	EXPECT_EQ(Full.smax(Full), Full);
1065	EXPECT_EQ(Full.smax(Empty), Empty);
1066	EXPECT_EQ(Full.smax(Some), ConstantRange(APInt(16, 0xa),
1067	APInt::getSignedMinValue(16)));
1068	EXPECT_EQ(Full.smax(Wrap), Full);
1069	EXPECT_EQ(Full.smax(One), ConstantRange(APInt(16, 0xa),
1070	APInt::getSignedMinValue(16)));
1071	EXPECT_EQ(Empty.smax(Empty), Empty);
1072	EXPECT_EQ(Empty.smax(Some), Empty);
1073	EXPECT_EQ(Empty.smax(Wrap), Empty);
1074	EXPECT_EQ(Empty.smax(One), Empty);
1075	EXPECT_EQ(Some.smax(Some), Some);
1076	EXPECT_EQ(Some.smax(Wrap), ConstantRange(APInt(16, 0xa),
1077	APInt(16, (uint64_t)INT16_MIN)));
1078	EXPECT_EQ(Some.smax(One), Some);
1079	EXPECT_EQ(Wrap.smax(One), ConstantRange(APInt(16, 0xa),
1080	APInt(16, (uint64_t)INT16_MIN)));
1081	EXPECT_EQ(One.smax(One), One);
1082
1083	TestBinaryOpExhaustive(
1084	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
1085	return CR1.smax(Other: CR2);
1086	},
1087	IntFn: [](const APInt &N1, const APInt &N2) {
1088	return APIntOps::smax(A: N1, B: N2);
1089	},
1090	PreferenceFn: PreferSmallestNonFullSigned);
1091	}
1092
1093	TEST_F(ConstantRangeTest, UMin) {
1094	EXPECT_EQ(Full.umin(Full), Full);
1095	EXPECT_EQ(Full.umin(Empty), Empty);
1096	EXPECT_EQ(Full.umin(Some), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1097	EXPECT_EQ(Full.umin(Wrap), Full);
1098	EXPECT_EQ(Empty.umin(Empty), Empty);
1099	EXPECT_EQ(Empty.umin(Some), Empty);
1100	EXPECT_EQ(Empty.umin(Wrap), Empty);
1101	EXPECT_EQ(Empty.umin(One), Empty);
1102	EXPECT_EQ(Some.umin(Some), Some);
1103	EXPECT_EQ(Some.umin(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1104	EXPECT_EQ(Some.umin(One), One);
1105	EXPECT_EQ(Wrap.umin(Wrap), Wrap);
1106	EXPECT_EQ(Wrap.umin(One), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
1107	EXPECT_EQ(One.umin(One), One);
1108
1109	TestBinaryOpExhaustive(
1110	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
1111	return CR1.umin(Other: CR2);
1112	},
1113	IntFn: [](const APInt &N1, const APInt &N2) {
1114	return APIntOps::umin(A: N1, B: N2);
1115	},
1116	PreferenceFn: PreferSmallestNonFullUnsigned);
1117	}
1118
1119	TEST_F(ConstantRangeTest, SMin) {
1120	EXPECT_EQ(Full.smin(Full), Full);
1121	EXPECT_EQ(Full.smin(Empty), Empty);
1122	EXPECT_EQ(Full.smin(Some), ConstantRange(APInt(16, (uint64_t)INT16_MIN),
1123	APInt(16, 0xaaa)));
1124	EXPECT_EQ(Full.smin(Wrap), Full);
1125	EXPECT_EQ(Empty.smin(Empty), Empty);
1126	EXPECT_EQ(Empty.smin(Some), Empty);
1127	EXPECT_EQ(Empty.smin(Wrap), Empty);
1128	EXPECT_EQ(Empty.smin(One), Empty);
1129	EXPECT_EQ(Some.smin(Some), Some);
1130	EXPECT_EQ(Some.smin(Wrap), ConstantRange(APInt(16, (uint64_t)INT16_MIN),
1131	APInt(16, 0xaaa)));
1132	EXPECT_EQ(Some.smin(One), One);
1133	EXPECT_EQ(Wrap.smin(Wrap), Wrap);
1134	EXPECT_EQ(Wrap.smin(One), ConstantRange(APInt(16, (uint64_t)INT16_MIN),
1135	APInt(16, 0xb)));
1136	EXPECT_EQ(One.smin(One), One);
1137
1138	TestBinaryOpExhaustive(
1139	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
1140	return CR1.smin(Other: CR2);
1141	},
1142	IntFn: [](const APInt &N1, const APInt &N2) {
1143	return APIntOps::smin(A: N1, B: N2);
1144	},
1145	PreferenceFn: PreferSmallestNonFullSigned);
1146	}
1147
1148	TEST_F(ConstantRangeTest, UDiv) {
1149	EXPECT_EQ(Full.udiv(Full), Full);
1150	EXPECT_EQ(Full.udiv(Empty), Empty);
1151	EXPECT_EQ(Full.udiv(One), ConstantRange(APInt(16, 0),
1152	APInt(16, 0xffff / 0xa + 1)));
1153	EXPECT_EQ(Full.udiv(Some), ConstantRange(APInt(16, 0),
1154	APInt(16, 0xffff / 0xa + 1)));
1155	EXPECT_EQ(Full.udiv(Wrap), Full);
1156	EXPECT_EQ(Empty.udiv(Empty), Empty);
1157	EXPECT_EQ(Empty.udiv(One), Empty);
1158	EXPECT_EQ(Empty.udiv(Some), Empty);
1159	EXPECT_EQ(Empty.udiv(Wrap), Empty);
1160	EXPECT_EQ(One.udiv(One), ConstantRange(APInt(16, 1)));
1161	EXPECT_EQ(One.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 2)));
1162	EXPECT_EQ(One.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
1163	EXPECT_EQ(Some.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 0x111)));
1164	EXPECT_EQ(Some.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1165	EXPECT_EQ(Wrap.udiv(Wrap), Full);
1166
1167
1168	ConstantRange Zero(APInt(16, 0));
1169	EXPECT_EQ(Zero.udiv(One), Zero);
1170	EXPECT_EQ(Zero.udiv(Full), Zero);
1171
1172	EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 99)).udiv(Full),
1173	ConstantRange(APInt(16, 0), APInt(16, 99)));
1174	EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 99)).udiv(Full),
1175	ConstantRange(APInt(16, 0), APInt(16, 99)));
1176	}
1177
1178	TEST_F(ConstantRangeTest, SDiv) {
1179	ConstantRange OneBit = ConstantRange::getFull(BitWidth: 1);
1180	EXPECT_EQ(OneBit.sdiv(OneBit), ConstantRange(APInt(1, 0)));
1181
1182	EnumerateTwoInterestingConstantRanges(TestFn: [&](const ConstantRange &CR1,
1183	const ConstantRange &CR2) {
1184	// Collect possible results in a bit vector. We store the signed value plus
1185	// a bias to make it unsigned.
1186	unsigned Bits = CR1.getBitWidth();
1187	int Bias = 1 << (Bits - 1);
1188	BitVector Results(1 << Bits);
1189	ForeachNumInConstantRange(CR: CR1, TestFn: [&](const APInt &N1) {
1190	ForeachNumInConstantRange(CR: CR2, TestFn: [&](const APInt &N2) {
1191	// Division by zero is UB.
1192	if (N2 == 0)
1193	return;
1194
1195	// SignedMin / -1 is UB.
1196	if (N1.isMinSignedValue() && N2.isAllOnes())
1197	return;
1198
1199	APInt N = N1.sdiv(RHS: N2);
1200	Results.set(N.getSExtValue() + Bias);
1201	});
1202	});
1203
1204	ConstantRange CR = CR1.sdiv(Other: CR2);
1205	if (Results.none()) {
1206	EXPECT_TRUE(CR.isEmptySet());
1207	return;
1208	}
1209
1210	// If there is a non-full signed envelope, that should be the result.
1211	APInt SMin(Bits, Results.find_first() - Bias);
1212	APInt SMax(Bits, Results.find_last() - Bias);
1213	ConstantRange Envelope = ConstantRange::getNonEmpty(Lower: SMin, Upper: SMax + 1);
1214	if (!Envelope.isFullSet()) {
1215	EXPECT_EQ(Envelope, CR);
1216	return;
1217	}
1218
1219	// If the signed envelope is a full set, try to find a smaller sign wrapped
1220	// set that is separated in negative and positive components (or one which
1221	// can also additionally contain zero).
1222	int LastNeg = Results.find_last_in(Begin: 0, End: Bias) - Bias;
1223	int LastPos = Results.find_next(Prev: Bias) - Bias;
1224	if (Results[Bias]) {
1225	if (LastNeg == -1)
1226	++LastNeg;
1227	else if (LastPos == 1)
1228	--LastPos;
1229	}
1230
1231	APInt WMax(Bits, LastNeg);
1232	APInt WMin(Bits, LastPos);
1233	ConstantRange Wrapped = ConstantRange::getNonEmpty(Lower: WMin, Upper: WMax + 1);
1234	EXPECT_EQ(Wrapped, CR);
1235	});
1236	}
1237
1238	TEST_F(ConstantRangeTest, URem) {
1239	EXPECT_EQ(Full.urem(Empty), Empty);
1240	EXPECT_EQ(Empty.urem(Full), Empty);
1241	// urem by zero is poison.
1242	EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0))), Empty);
1243	// urem by full range doesn't contain MaxValue.
1244	EXPECT_EQ(Full.urem(Full), ConstantRange(APInt(16, 0), APInt(16, 0xffff)));
1245	// urem is upper bounded by maximum RHS minus one.
1246	EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0), APInt(16, 123))),
1247	ConstantRange(APInt(16, 0), APInt(16, 122)));
1248	// urem is upper bounded by maximum LHS.
1249	EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 123)).urem(Full),
1250	ConstantRange(APInt(16, 0), APInt(16, 123)));
1251	// If the LHS is always lower than the RHS, the result is the LHS.
1252	EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20))
1253	.urem(ConstantRange(APInt(16, 20), APInt(16, 30))),
1254	ConstantRange(APInt(16, 10), APInt(16, 20)));
1255	// It has to be strictly lower, otherwise the top value may wrap to zero.
1256	EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20))
1257	.urem(ConstantRange(APInt(16, 19), APInt(16, 30))),
1258	ConstantRange(APInt(16, 0), APInt(16, 20)));
1259	// [12, 14] % 10 is [2, 4], but we conservatively compute [0, 9].
1260	EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))
1261	.urem(ConstantRange(APInt(16, 10))),
1262	ConstantRange(APInt(16, 0), APInt(16, 10)));
1263
1264	TestBinaryOpExhaustive(
1265	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
1266	return CR1.urem(Other: CR2);
1267	},
1268	IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
1269	if (N2.isZero())
1270	return std::nullopt;
1271	return N1.urem(RHS: N2);
1272	},
1273	PreferenceFn: PreferSmallest, CheckFn: CheckSingleElementsOnly);
1274	}
1275
1276	TEST_F(ConstantRangeTest, SRem) {
1277	EXPECT_EQ(Full.srem(Empty), Empty);
1278	EXPECT_EQ(Empty.srem(Full), Empty);
1279	// srem by zero is UB.
1280	EXPECT_EQ(Full.srem(ConstantRange(APInt(16, 0))), Empty);
1281	// srem by full range doesn't contain SignedMinValue.
1282	EXPECT_EQ(Full.srem(Full), ConstantRange(APInt::getSignedMinValue(16) + 1,
1283	APInt::getSignedMinValue(16)));
1284
1285	ConstantRange PosMod(APInt(16, 10), APInt(16, 21)); // [10, 20]
1286	ConstantRange NegMod(APInt(16, -20), APInt(16, -9)); // [-20, -10]
1287	ConstantRange IntMinMod(APInt::getSignedMinValue(numBits: 16));
1288
1289	ConstantRange Expected(16, true);
1290
1291	// srem is bounded by abs(RHS) minus one.
1292	ConstantRange PosLargeLHS(APInt(16, 0), APInt(16, 41));
1293	Expected = ConstantRange(APInt(16, 0), APInt(16, 20));
1294	EXPECT_EQ(PosLargeLHS.srem(PosMod), Expected);
1295	EXPECT_EQ(PosLargeLHS.srem(NegMod), Expected);
1296	ConstantRange NegLargeLHS(APInt(16, -40), APInt(16, 1));
1297	Expected = ConstantRange(APInt(16, -19), APInt(16, 1));
1298	EXPECT_EQ(NegLargeLHS.srem(PosMod), Expected);
1299	EXPECT_EQ(NegLargeLHS.srem(NegMod), Expected);
1300	ConstantRange PosNegLargeLHS(APInt(16, -32), APInt(16, 38));
1301	Expected = ConstantRange(APInt(16, -19), APInt(16, 20));
1302	EXPECT_EQ(PosNegLargeLHS.srem(PosMod), Expected);
1303	EXPECT_EQ(PosNegLargeLHS.srem(NegMod), Expected);
1304
1305	// srem is bounded by LHS.
1306	ConstantRange PosLHS(APInt(16, 0), APInt(16, 16));
1307	EXPECT_EQ(PosLHS.srem(PosMod), PosLHS);
1308	EXPECT_EQ(PosLHS.srem(NegMod), PosLHS);
1309	EXPECT_EQ(PosLHS.srem(IntMinMod), PosLHS);
1310	ConstantRange NegLHS(APInt(16, -15), APInt(16, 1));
1311	EXPECT_EQ(NegLHS.srem(PosMod), NegLHS);
1312	EXPECT_EQ(NegLHS.srem(NegMod), NegLHS);
1313	EXPECT_EQ(NegLHS.srem(IntMinMod), NegLHS);
1314	ConstantRange PosNegLHS(APInt(16, -12), APInt(16, 18));
1315	EXPECT_EQ(PosNegLHS.srem(PosMod), PosNegLHS);
1316	EXPECT_EQ(PosNegLHS.srem(NegMod), PosNegLHS);
1317	EXPECT_EQ(PosNegLHS.srem(IntMinMod), PosNegLHS);
1318
1319	// srem is LHS if it is smaller than RHS.
1320	ConstantRange PosSmallLHS(APInt(16, 3), APInt(16, 8));
1321	EXPECT_EQ(PosSmallLHS.srem(PosMod), PosSmallLHS);
1322	EXPECT_EQ(PosSmallLHS.srem(NegMod), PosSmallLHS);
1323	EXPECT_EQ(PosSmallLHS.srem(IntMinMod), PosSmallLHS);
1324	ConstantRange NegSmallLHS(APInt(16, -7), APInt(16, -2));
1325	EXPECT_EQ(NegSmallLHS.srem(PosMod), NegSmallLHS);
1326	EXPECT_EQ(NegSmallLHS.srem(NegMod), NegSmallLHS);
1327	EXPECT_EQ(NegSmallLHS.srem(IntMinMod), NegSmallLHS);
1328	ConstantRange PosNegSmallLHS(APInt(16, -3), APInt(16, 8));
1329	EXPECT_EQ(PosNegSmallLHS.srem(PosMod), PosNegSmallLHS);
1330	EXPECT_EQ(PosNegSmallLHS.srem(NegMod), PosNegSmallLHS);
1331	EXPECT_EQ(PosNegSmallLHS.srem(IntMinMod), PosNegSmallLHS);
1332
1333	// Example of a suboptimal result:
1334	// [12, 14] srem 10 is [2, 4], but we conservatively compute [0, 9].
1335	EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))
1336	.srem(ConstantRange(APInt(16, 10))),
1337	ConstantRange(APInt(16, 0), APInt(16, 10)));
1338
1339	TestBinaryOpExhaustive(
1340	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
1341	return CR1.srem(Other: CR2);
1342	},
1343	IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
1344	if (N2.isZero())
1345	return std::nullopt;
1346	return N1.srem(RHS: N2);
1347	},
1348	PreferenceFn: PreferSmallest, CheckFn: CheckSingleElementsOnly);
1349	}
1350
1351	TEST_F(ConstantRangeTest, Shl) {
1352	ConstantRange Some2(APInt(16, 0xfff), APInt(16, 0x8000));
1353	ConstantRange WrapNullMax(APInt(16, 0x1), APInt(16, 0x0));
1354	EXPECT_EQ(Full.shl(Full), Full);
1355	EXPECT_EQ(Full.shl(Empty), Empty);
1356	EXPECT_EQ(Full.shl(One), ConstantRange(APInt(16, 0),
1357	APInt(16, 0xfc00) + 1));
1358	EXPECT_EQ(Full.shl(Some), Full); // TODO: [0, (-1 << 0xa) + 1)
1359	EXPECT_EQ(Full.shl(Wrap), Full);
1360	EXPECT_EQ(Empty.shl(Empty), Empty);
1361	EXPECT_EQ(Empty.shl(One), Empty);
1362	EXPECT_EQ(Empty.shl(Some), Empty);
1363	EXPECT_EQ(Empty.shl(Wrap), Empty);
1364	EXPECT_EQ(One.shl(One), ConstantRange(APInt(16, 0xa << 0xa),
1365	APInt(16, (0xa << 0xa) + 1)));
1366	EXPECT_EQ(One.shl(Some), Full); // TODO: [0xa << 0xa, 0)
1367	EXPECT_EQ(One.shl(Wrap), Full); // TODO: [0xa, 0xa << 14 + 1)
1368	EXPECT_EQ(Some.shl(Some), Full); // TODO: [0xa << 0xa, 0xfc01)
1369	EXPECT_EQ(Some.shl(Wrap), Full); // TODO: [0xa, 0x7ff << 0x5 + 1)
1370	EXPECT_EQ(Wrap.shl(Wrap), Full);
1371	EXPECT_EQ(
1372	Some2.shl(ConstantRange(APInt(16, 0x1))),
1373	ConstantRange(APInt(16, 0xfff << 0x1), APInt(16, 0x7fff << 0x1) + 1));
1374	EXPECT_EQ(One.shl(WrapNullMax), Full);
1375
1376	ConstantRange NegOne(APInt(16, 0xffff));
1377	EXPECT_EQ(NegOne.shl(ConstantRange(APInt(16, 0), APInt(16, 5))),
1378	ConstantRange(APInt(16, 0xfff0), APInt(16, 0)));
1379	EXPECT_EQ(ConstantRange(APInt(16, 0xfffe), APInt(16, 0))
1380	.shl(ConstantRange(APInt(16, 0), APInt(16, 5))),
1381	ConstantRange(APInt(16, 0xffe0), APInt(16, 0)));
1382
1383	TestBinaryOpExhaustive(
1384	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
1385	return CR1.shl(Other: CR2);
1386	},
1387	IntFn: [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
1388	if (N2.uge(RHS: N2.getBitWidth()))
1389	return std::nullopt;
1390	return N1.shl(ShiftAmt: N2);
1391	},
1392	PreferenceFn: PreferSmallestUnsigned,
1393	CheckFn: [](const ConstantRange &, const ConstantRange &CR2) {
1394	// We currently only produce precise results for single element RHS.
1395	return CR2.isSingleElement();
1396	});
1397	}
1398
1399	TEST_F(ConstantRangeTest, Lshr) {
1400	EXPECT_EQ(Full.lshr(Full), Full);
1401	EXPECT_EQ(Full.lshr(Empty), Empty);
1402	EXPECT_EQ(Full.lshr(One), ConstantRange(APInt(16, 0),
1403	APInt(16, (0xffff >> 0xa) + 1)));
1404	EXPECT_EQ(Full.lshr(Some), ConstantRange(APInt(16, 0),
1405	APInt(16, (0xffff >> 0xa) + 1)));
1406	EXPECT_EQ(Full.lshr(Wrap), Full);
1407	EXPECT_EQ(Empty.lshr(Empty), Empty);
1408	EXPECT_EQ(Empty.lshr(One), Empty);
1409	EXPECT_EQ(Empty.lshr(Some), Empty);
1410	EXPECT_EQ(Empty.lshr(Wrap), Empty);
1411	EXPECT_EQ(One.lshr(One), ConstantRange(APInt(16, 0)));
1412	EXPECT_EQ(One.lshr(Some), ConstantRange(APInt(16, 0)));
1413	EXPECT_EQ(One.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
1414	EXPECT_EQ(Some.lshr(Some), ConstantRange(APInt(16, 0),
1415	APInt(16, (0xaaa >> 0xa) + 1)));
1416	EXPECT_EQ(Some.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1417	EXPECT_EQ(Wrap.lshr(Wrap), Full);
1418	}
1419
1420	TEST_F(ConstantRangeTest, Ashr) {
1421	EXPECT_EQ(Full.ashr(Full), Full);
1422	EXPECT_EQ(Full.ashr(Empty), Empty);
1423	EXPECT_EQ(Full.ashr(One), ConstantRange(APInt(16, 0xffe0),
1424	APInt(16, (0x7fff >> 0xa) + 1 )));
1425	ConstantRange Small(APInt(16, 0xa), APInt(16, 0xb));
1426	EXPECT_EQ(Full.ashr(Small), ConstantRange(APInt(16, 0xffe0),
1427	APInt(16, (0x7fff >> 0xa) + 1 )));
1428	EXPECT_EQ(Full.ashr(Some), ConstantRange(APInt(16, 0xffe0),
1429	APInt(16, (0x7fff >> 0xa) + 1 )));
1430	EXPECT_EQ(Full.ashr(Wrap), Full);
1431	EXPECT_EQ(Empty.ashr(Empty), Empty);
1432	EXPECT_EQ(Empty.ashr(One), Empty);
1433	EXPECT_EQ(Empty.ashr(Some), Empty);
1434	EXPECT_EQ(Empty.ashr(Wrap), Empty);
1435	EXPECT_EQ(One.ashr(One), ConstantRange(APInt(16, 0)));
1436	EXPECT_EQ(One.ashr(Some), ConstantRange(APInt(16, 0)));
1437	EXPECT_EQ(One.ashr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
1438	EXPECT_EQ(Some.ashr(Some), ConstantRange(APInt(16, 0),
1439	APInt(16, (0xaaa >> 0xa) + 1)));
1440	EXPECT_EQ(Some.ashr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1441	EXPECT_EQ(Wrap.ashr(Wrap), Full);
1442	ConstantRange Neg(APInt(16, 0xf3f0, true), APInt(16, 0xf7f8, true));
1443	EXPECT_EQ(Neg.ashr(Small), ConstantRange(APInt(16, 0xfffc, true),
1444	APInt(16, 0xfffe, true)));
1445	}
1446
1447	TEST(ConstantRange, MakeAllowedICmpRegion) {
1448	// PR8250
1449	ConstantRange SMax = ConstantRange(APInt::getSignedMaxValue(numBits: 32));
1450	EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_SGT, SMax)
1451	.isEmptySet());
1452	}
1453
1454	TEST(ConstantRange, MakeSatisfyingICmpRegion) {
1455	ConstantRange LowHalf(APInt(8, 0), APInt(8, 128));
1456	ConstantRange HighHalf(APInt(8, 128), APInt(8, 0));
1457	ConstantRange EmptySet(8, /* isFullSet = */ false);
1458
1459	EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, LowHalf),
1460	HighHalf);
1461
1462	EXPECT_EQ(
1463	ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, HighHalf),
1464	LowHalf);
1465
1466	EXPECT_TRUE(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_EQ,
1467	HighHalf).isEmptySet());
1468
1469	ConstantRange UnsignedSample(APInt(8, 5), APInt(8, 200));
1470
1471	EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULT,
1472	UnsignedSample),
1473	ConstantRange(APInt(8, 0), APInt(8, 5)));
1474
1475	EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULE,
1476	UnsignedSample),
1477	ConstantRange(APInt(8, 0), APInt(8, 6)));
1478
1479	EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGT,
1480	UnsignedSample),
1481	ConstantRange(APInt(8, 200), APInt(8, 0)));
1482
1483	EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGE,
1484	UnsignedSample),
1485	ConstantRange(APInt(8, 199), APInt(8, 0)));
1486
1487	ConstantRange SignedSample(APInt(8, -5), APInt(8, 5));
1488
1489	EXPECT_EQ(
1490	ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLT, SignedSample),
1491	ConstantRange(APInt(8, -128), APInt(8, -5)));
1492
1493	EXPECT_EQ(
1494	ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLE, SignedSample),
1495	ConstantRange(APInt(8, -128), APInt(8, -4)));
1496
1497	EXPECT_EQ(
1498	ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGT, SignedSample),
1499	ConstantRange(APInt(8, 5), APInt(8, -128)));
1500
1501	EXPECT_EQ(
1502	ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGE, SignedSample),
1503	ConstantRange(APInt(8, 4), APInt(8, -128)));
1504	}
1505
1506	void ICmpTestImpl(CmpInst::Predicate Pred) {
1507	EnumerateTwoInterestingConstantRanges(
1508	TestFn: [&](const ConstantRange &CR1, const ConstantRange &CR2) {
1509	bool Exhaustive = true;
1510	ForeachNumInConstantRange(CR: CR1, TestFn: [&](const APInt &N1) {
1511	ForeachNumInConstantRange(CR: CR2, TestFn: [&](const APInt &N2) {
1512	Exhaustive &= ICmpInst::compare(LHS: N1, RHS: N2, Pred);
1513	});
1514	});
1515	EXPECT_EQ(CR1.icmp(Pred, CR2), Exhaustive);
1516	});
1517	}
1518
1519	TEST(ConstantRange, ICmp) {
1520	for (auto Pred : ICmpInst::predicates())
1521	ICmpTestImpl(Pred);
1522	}
1523
1524	TEST(ConstantRange, MakeGuaranteedNoWrapRegion) {
1525	const int IntMin4Bits = 8;
1526	const int IntMax4Bits = 7;
1527	typedef OverflowingBinaryOperator OBO;
1528
1529	for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) {
1530	APInt C(4, Const, true /* = isSigned */);
1531
1532	auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1533	BinOp: Instruction::Add, Other: C, NoWrapKind: OBO::NoUnsignedWrap);
1534
1535	EXPECT_FALSE(NUWRegion.isEmptySet());
1536
1537	auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1538	BinOp: Instruction::Add, Other: C, NoWrapKind: OBO::NoSignedWrap);
1539
1540	EXPECT_FALSE(NSWRegion.isEmptySet());
1541
1542	for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E;
1543	++I) {
1544	bool Overflow = false;
1545	(void)I.uadd_ov(RHS: C, Overflow);
1546	EXPECT_FALSE(Overflow);
1547	}
1548
1549	for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E;
1550	++I) {
1551	bool Overflow = false;
1552	(void)I.sadd_ov(RHS: C, Overflow);
1553	EXPECT_FALSE(Overflow);
1554	}
1555	}
1556
1557	for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) {
1558	APInt C(4, Const, true /* = isSigned */);
1559
1560	auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1561	BinOp: Instruction::Sub, Other: C, NoWrapKind: OBO::NoUnsignedWrap);
1562
1563	EXPECT_FALSE(NUWRegion.isEmptySet());
1564
1565	auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1566	BinOp: Instruction::Sub, Other: C, NoWrapKind: OBO::NoSignedWrap);
1567
1568	EXPECT_FALSE(NSWRegion.isEmptySet());
1569
1570	for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E;
1571	++I) {
1572	bool Overflow = false;
1573	(void)I.usub_ov(RHS: C, Overflow);
1574	EXPECT_FALSE(Overflow);
1575	}
1576
1577	for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E;
1578	++I) {
1579	bool Overflow = false;
1580	(void)I.ssub_ov(RHS: C, Overflow);
1581	EXPECT_FALSE(Overflow);
1582	}
1583	}
1584
1585	auto NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
1586	BinOp: Instruction::Add, Other: ConstantRange(32, /* isFullSet = */ true),
1587	NoWrapKind: OBO::NoSignedWrap);
1588	EXPECT_TRUE(NSWForAllValues.isSingleElement() &&
1589	NSWForAllValues.getSingleElement()->isMinValue());
1590
1591	NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
1592	BinOp: Instruction::Sub, Other: ConstantRange(32, /* isFullSet = */ true),
1593	NoWrapKind: OBO::NoSignedWrap);
1594	EXPECT_TRUE(NSWForAllValues.isSingleElement() &&
1595	NSWForAllValues.getSingleElement()->isMaxValue());
1596
1597	auto NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
1598	BinOp: Instruction::Add, Other: ConstantRange(32, /* isFullSet = */ true),
1599	NoWrapKind: OBO::NoUnsignedWrap);
1600	EXPECT_TRUE(NUWForAllValues.isSingleElement() &&
1601	NUWForAllValues.getSingleElement()->isMinValue());
1602
1603	NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
1604	BinOp: Instruction::Sub, Other: ConstantRange(32, /* isFullSet = */ true),
1605	NoWrapKind: OBO::NoUnsignedWrap);
1606	EXPECT_TRUE(NUWForAllValues.isSingleElement() &&
1607	NUWForAllValues.getSingleElement()->isMaxValue());
1608
1609	EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1610	Instruction::Add, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet());
1611	EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1612	Instruction::Add, APInt(32, 0), OBO::NoSignedWrap).isFullSet());
1613	EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1614	Instruction::Sub, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet());
1615	EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1616	Instruction::Sub, APInt(32, 0), OBO::NoSignedWrap).isFullSet());
1617
1618	ConstantRange OneToFive(APInt(32, 1), APInt(32, 6));
1619	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1620	Instruction::Add, OneToFive, OBO::NoSignedWrap),
1621	ConstantRange(APInt::getSignedMinValue(32),
1622	APInt::getSignedMaxValue(32) - 4));
1623	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1624	Instruction::Add, OneToFive, OBO::NoUnsignedWrap),
1625	ConstantRange(APInt::getMinValue(32), APInt::getMinValue(32) - 5));
1626	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1627	Instruction::Sub, OneToFive, OBO::NoSignedWrap),
1628	ConstantRange(APInt::getSignedMinValue(32) + 5,
1629	APInt::getSignedMinValue(32)));
1630	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1631	Instruction::Sub, OneToFive, OBO::NoUnsignedWrap),
1632	ConstantRange(APInt::getMinValue(32) + 5, APInt::getMinValue(32)));
1633
1634	ConstantRange MinusFiveToMinusTwo(APInt(32, -5), APInt(32, -1));
1635	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1636	Instruction::Add, MinusFiveToMinusTwo, OBO::NoSignedWrap),
1637	ConstantRange(APInt::getSignedMinValue(32) + 5,
1638	APInt::getSignedMinValue(32)));
1639	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1640	Instruction::Add, MinusFiveToMinusTwo, OBO::NoUnsignedWrap),
1641	ConstantRange(APInt(32, 0), APInt(32, 2)));
1642	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1643	Instruction::Sub, MinusFiveToMinusTwo, OBO::NoSignedWrap),
1644	ConstantRange(APInt::getSignedMinValue(32),
1645	APInt::getSignedMaxValue(32) - 4));
1646	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1647	Instruction::Sub, MinusFiveToMinusTwo, OBO::NoUnsignedWrap),
1648	ConstantRange(APInt::getMaxValue(32) - 1,
1649	APInt::getMinValue(32)));
1650
1651	ConstantRange MinusOneToOne(APInt(32, -1), APInt(32, 2));
1652	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1653	Instruction::Add, MinusOneToOne, OBO::NoSignedWrap),
1654	ConstantRange(APInt::getSignedMinValue(32) + 1,
1655	APInt::getSignedMinValue(32) - 1));
1656	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1657	Instruction::Add, MinusOneToOne, OBO::NoUnsignedWrap),
1658	ConstantRange(APInt(32, 0), APInt(32, 1)));
1659	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1660	Instruction::Sub, MinusOneToOne, OBO::NoSignedWrap),
1661	ConstantRange(APInt::getSignedMinValue(32) + 1,
1662	APInt::getSignedMinValue(32) - 1));
1663	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1664	Instruction::Sub, MinusOneToOne, OBO::NoUnsignedWrap),
1665	ConstantRange(APInt::getMaxValue(32),
1666	APInt::getMinValue(32)));
1667
1668	ConstantRange One(APInt(32, 1), APInt(32, 2));
1669	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1670	Instruction::Add, One, OBO::NoSignedWrap),
1671	ConstantRange(APInt::getSignedMinValue(32),
1672	APInt::getSignedMaxValue(32)));
1673	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1674	Instruction::Add, One, OBO::NoUnsignedWrap),
1675	ConstantRange(APInt::getMinValue(32), APInt::getMaxValue(32)));
1676	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1677	Instruction::Sub, One, OBO::NoSignedWrap),
1678	ConstantRange(APInt::getSignedMinValue(32) + 1,
1679	APInt::getSignedMinValue(32)));
1680	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1681	Instruction::Sub, One, OBO::NoUnsignedWrap),
1682	ConstantRange(APInt::getMinValue(32) + 1, APInt::getMinValue(32)));
1683
1684	ConstantRange OneLessThanBitWidth(APInt(32, 0), APInt(32, 31) + 1);
1685	ConstantRange UpToBitWidth(APInt(32, 0), APInt(32, 32) + 1);
1686	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1687	Instruction::Shl, UpToBitWidth, OBO::NoUnsignedWrap),
1688	ConstantRange::makeGuaranteedNoWrapRegion(
1689	Instruction::Shl, OneLessThanBitWidth, OBO::NoUnsignedWrap));
1690	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1691	Instruction::Shl, UpToBitWidth, OBO::NoSignedWrap),
1692	ConstantRange::makeGuaranteedNoWrapRegion(
1693	Instruction::Shl, OneLessThanBitWidth, OBO::NoSignedWrap));
1694	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1695	Instruction::Shl, UpToBitWidth, OBO::NoUnsignedWrap),
1696	ConstantRange(APInt(32, 0), APInt(32, 1) + 1));
1697	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1698	Instruction::Shl, UpToBitWidth, OBO::NoSignedWrap),
1699	ConstantRange(APInt(32, -1), APInt(32, 0) + 1));
1700
1701	EXPECT_EQ(
1702	ConstantRange::makeGuaranteedNoWrapRegion(
1703	Instruction::Shl, ConstantRange::getFull(32), OBO::NoUnsignedWrap),
1704	ConstantRange::makeGuaranteedNoWrapRegion(
1705	Instruction::Shl, OneLessThanBitWidth, OBO::NoUnsignedWrap));
1706	EXPECT_EQ(
1707	ConstantRange::makeGuaranteedNoWrapRegion(
1708	Instruction::Shl, ConstantRange::getFull(32), OBO::NoSignedWrap),
1709	ConstantRange::makeGuaranteedNoWrapRegion(
1710	Instruction::Shl, OneLessThanBitWidth, OBO::NoSignedWrap));
1711
1712	ConstantRange IllegalShAmt(APInt(32, 32), APInt(32, 0) + 1);
1713	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1714	Instruction::Shl, IllegalShAmt, OBO::NoUnsignedWrap),
1715	ConstantRange::getFull(32));
1716	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1717	Instruction::Shl, IllegalShAmt, OBO::NoSignedWrap),
1718	ConstantRange::getFull(32));
1719
1720	EXPECT_EQ(
1721	ConstantRange::makeGuaranteedNoWrapRegion(
1722	Instruction::Shl, ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
1723	OBO::NoUnsignedWrap),
1724	ConstantRange::makeGuaranteedNoWrapRegion(
1725	Instruction::Shl, ConstantRange(APInt(32, 0), APInt(32, 16) + 1),
1726	OBO::NoUnsignedWrap));
1727	EXPECT_EQ(
1728	ConstantRange::makeGuaranteedNoWrapRegion(
1729	Instruction::Shl, ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
1730	OBO::NoSignedWrap),
1731	ConstantRange::makeGuaranteedNoWrapRegion(
1732	Instruction::Shl, ConstantRange(APInt(32, 0), APInt(32, 16) + 1),
1733	OBO::NoSignedWrap));
1734
1735	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1736	Instruction::Shl,
1737	ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
1738	OBO::NoUnsignedWrap),
1739	ConstantRange(APInt(32, 0), APInt(32, 65535) + 1));
1740	EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1741	Instruction::Shl,
1742	ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
1743	OBO::NoSignedWrap),
1744	ConstantRange(APInt(32, -32768), APInt(32, 32767) + 1));
1745	}
1746
1747	template<typename Fn>
1748	void TestNoWrapRegionExhaustive(Instruction::BinaryOps BinOp,
1749	unsigned NoWrapKind, Fn OverflowFn) {
1750	for (unsigned Bits : {1, 5}) {
1751	EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) {
1752	if (CR.isEmptySet())
1753	return;
1754	if (Instruction::isShift(Opcode: BinOp) && CR.getUnsignedMax().uge(RHS: Bits))
1755	return;
1756
1757	ConstantRange NoWrap =
1758	ConstantRange::makeGuaranteedNoWrapRegion(BinOp, Other: CR, NoWrapKind);
1759	EnumerateAPInts(Bits, [&](const APInt &N1) {
1760	bool NoOverflow = true;
1761	bool Overflow = true;
1762	ForeachNumInConstantRange(CR, [&](const APInt &N2) {
1763	if (OverflowFn(N1, N2))
1764	NoOverflow = false;
1765	else
1766	Overflow = false;
1767	});
1768	EXPECT_EQ(NoOverflow, NoWrap.contains(N1));
1769
1770	// The no-wrap range is exact for single-element ranges.
1771	if (CR.isSingleElement()) {
1772	EXPECT_EQ(Overflow, !NoWrap.contains(N1));
1773	}
1774	});
1775	});
1776	}
1777	}
1778
1779	// Show that makeGuaranteedNoWrapRegion() is maximal, and for single-element
1780	// ranges also exact.
1781	TEST(ConstantRange, NoWrapRegionExhaustive) {
1782	TestNoWrapRegionExhaustive(
1783	BinOp: Instruction::Add, NoWrapKind: OverflowingBinaryOperator::NoUnsignedWrap,
1784	OverflowFn: [](const APInt &N1, const APInt &N2) {
1785	bool Overflow;
1786	(void) N1.uadd_ov(RHS: N2, Overflow);
1787	return Overflow;
1788	});
1789	TestNoWrapRegionExhaustive(
1790	BinOp: Instruction::Add, NoWrapKind: OverflowingBinaryOperator::NoSignedWrap,
1791	OverflowFn: [](const APInt &N1, const APInt &N2) {
1792	bool Overflow;
1793	(void) N1.sadd_ov(RHS: N2, Overflow);
1794	return Overflow;
1795	});
1796	TestNoWrapRegionExhaustive(
1797	BinOp: Instruction::Sub, NoWrapKind: OverflowingBinaryOperator::NoUnsignedWrap,
1798	OverflowFn: [](const APInt &N1, const APInt &N2) {
1799	bool Overflow;
1800	(void) N1.usub_ov(RHS: N2, Overflow);
1801	return Overflow;
1802	});
1803	TestNoWrapRegionExhaustive(
1804	BinOp: Instruction::Sub, NoWrapKind: OverflowingBinaryOperator::NoSignedWrap,
1805	OverflowFn: [](const APInt &N1, const APInt &N2) {
1806	bool Overflow;
1807	(void) N1.ssub_ov(RHS: N2, Overflow);
1808	return Overflow;
1809	});
1810	TestNoWrapRegionExhaustive(
1811	BinOp: Instruction::Mul, NoWrapKind: OverflowingBinaryOperator::NoUnsignedWrap,
1812	OverflowFn: [](const APInt &N1, const APInt &N2) {
1813	bool Overflow;
1814	(void) N1.umul_ov(RHS: N2, Overflow);
1815	return Overflow;
1816	});
1817	TestNoWrapRegionExhaustive(
1818	BinOp: Instruction::Mul, NoWrapKind: OverflowingBinaryOperator::NoSignedWrap,
1819	OverflowFn: [](const APInt &N1, const APInt &N2) {
1820	bool Overflow;
1821	(void) N1.smul_ov(RHS: N2, Overflow);
1822	return Overflow;
1823	});
1824	TestNoWrapRegionExhaustive(BinOp: Instruction::Shl,
1825	NoWrapKind: OverflowingBinaryOperator::NoUnsignedWrap,
1826	OverflowFn: [](const APInt &N1, const APInt &N2) {
1827	bool Overflow;
1828	(void)N1.ushl_ov(Amt: N2, Overflow);
1829	return Overflow;
1830	});
1831	TestNoWrapRegionExhaustive(BinOp: Instruction::Shl,
1832	NoWrapKind: OverflowingBinaryOperator::NoSignedWrap,
1833	OverflowFn: [](const APInt &N1, const APInt &N2) {
1834	bool Overflow;
1835	(void)N1.sshl_ov(Amt: N2, Overflow);
1836	return Overflow;
1837	});
1838	}
1839
1840	TEST(ConstantRange, GetEquivalentICmp) {
1841	APInt RHS;
1842	CmpInst::Predicate Pred;
1843
1844	EXPECT_TRUE(ConstantRange(APInt::getMinValue(32), APInt(32, 100))
1845	.getEquivalentICmp(Pred, RHS));
1846	EXPECT_EQ(Pred, CmpInst::ICMP_ULT);
1847	EXPECT_EQ(RHS, APInt(32, 100));
1848
1849	EXPECT_TRUE(ConstantRange(APInt::getSignedMinValue(32), APInt(32, 100))
1850	.getEquivalentICmp(Pred, RHS));
1851	EXPECT_EQ(Pred, CmpInst::ICMP_SLT);
1852	EXPECT_EQ(RHS, APInt(32, 100));
1853
1854	EXPECT_TRUE(ConstantRange(APInt(32, 100), APInt::getMinValue(32))
1855	.getEquivalentICmp(Pred, RHS));
1856	EXPECT_EQ(Pred, CmpInst::ICMP_UGE);
1857	EXPECT_EQ(RHS, APInt(32, 100));
1858
1859	EXPECT_TRUE(ConstantRange(APInt(32, 100), APInt::getSignedMinValue(32))
1860	.getEquivalentICmp(Pred, RHS));
1861	EXPECT_EQ(Pred, CmpInst::ICMP_SGE);
1862	EXPECT_EQ(RHS, APInt(32, 100));
1863
1864	EXPECT_TRUE(
1865	ConstantRange(32, /*isFullSet=*/true).getEquivalentICmp(Pred, RHS));
1866	EXPECT_EQ(Pred, CmpInst::ICMP_UGE);
1867	EXPECT_EQ(RHS, APInt(32, 0));
1868
1869	EXPECT_TRUE(
1870	ConstantRange(32, /*isFullSet=*/false).getEquivalentICmp(Pred, RHS));
1871	EXPECT_EQ(Pred, CmpInst::ICMP_ULT);
1872	EXPECT_EQ(RHS, APInt(32, 0));
1873
1874	EXPECT_FALSE(ConstantRange(APInt(32, 100), APInt(32, 200))
1875	.getEquivalentICmp(Pred, RHS));
1876
1877	EXPECT_FALSE(ConstantRange(APInt::getSignedMinValue(32) - APInt(32, 100),
1878	APInt::getSignedMinValue(32) + APInt(32, 100))
1879	.getEquivalentICmp(Pred, RHS));
1880
1881	EXPECT_FALSE(ConstantRange(APInt::getMinValue(32) - APInt(32, 100),
1882	APInt::getMinValue(32) + APInt(32, 100))
1883	.getEquivalentICmp(Pred, RHS));
1884
1885	EXPECT_TRUE(ConstantRange(APInt(32, 100)).getEquivalentICmp(Pred, RHS));
1886	EXPECT_EQ(Pred, CmpInst::ICMP_EQ);
1887	EXPECT_EQ(RHS, APInt(32, 100));
1888
1889	EXPECT_TRUE(
1890	ConstantRange(APInt(32, 100)).inverse().getEquivalentICmp(Pred, RHS));
1891	EXPECT_EQ(Pred, CmpInst::ICMP_NE);
1892	EXPECT_EQ(RHS, APInt(32, 100));
1893
1894	EXPECT_TRUE(
1895	ConstantRange(APInt(512, 100)).inverse().getEquivalentICmp(Pred, RHS));
1896	EXPECT_EQ(Pred, CmpInst::ICMP_NE);
1897	EXPECT_EQ(RHS, APInt(512, 100));
1898
1899	// NB! It would be correct for the following four calls to getEquivalentICmp
1900	// to return ordered predicates like CmpInst::ICMP_ULT or CmpInst::ICMP_UGT.
1901	// However, that's not the case today.
1902
1903	EXPECT_TRUE(ConstantRange(APInt(32, 0)).getEquivalentICmp(Pred, RHS));
1904	EXPECT_EQ(Pred, CmpInst::ICMP_EQ);
1905	EXPECT_EQ(RHS, APInt(32, 0));
1906
1907	EXPECT_TRUE(
1908	ConstantRange(APInt(32, 0)).inverse().getEquivalentICmp(Pred, RHS));
1909	EXPECT_EQ(Pred, CmpInst::ICMP_NE);
1910	EXPECT_EQ(RHS, APInt(32, 0));
1911
1912	EXPECT_TRUE(ConstantRange(APInt(32, -1)).getEquivalentICmp(Pred, RHS));
1913	EXPECT_EQ(Pred, CmpInst::ICMP_EQ);
1914	EXPECT_EQ(RHS, APInt(32, -1));
1915
1916	EXPECT_TRUE(
1917	ConstantRange(APInt(32, -1)).inverse().getEquivalentICmp(Pred, RHS));
1918	EXPECT_EQ(Pred, CmpInst::ICMP_NE);
1919	EXPECT_EQ(RHS, APInt(32, -1));
1920
1921	EnumerateInterestingConstantRanges(TestFn: [](const ConstantRange &CR) {
1922	unsigned Bits = CR.getBitWidth();
1923	CmpInst::Predicate Pred;
1924	APInt RHS, Offset;
1925	CR.getEquivalentICmp(Pred, RHS, Offset);
1926	EnumerateAPInts(Bits, TestFn: [&](const APInt &N) {
1927	bool Result = ICmpInst::compare(LHS: N + Offset, RHS, Pred);
1928	EXPECT_EQ(CR.contains(N), Result);
1929	});
1930
1931	if (CR.getEquivalentICmp(Pred, RHS)) {
1932	EnumerateAPInts(Bits, TestFn: [&](const APInt &N) {
1933	bool Result = ICmpInst::compare(LHS: N, RHS, Pred);
1934	EXPECT_EQ(CR.contains(N), Result);
1935	});
1936	}
1937	});
1938	}
1939
1940	#define EXPECT_MAY_OVERFLOW(op) \
1941	EXPECT_EQ(ConstantRange::OverflowResult::MayOverflow, (op))
1942	#define EXPECT_ALWAYS_OVERFLOWS_LOW(op) \
1943	EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflowsLow, (op))
1944	#define EXPECT_ALWAYS_OVERFLOWS_HIGH(op) \
1945	EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflowsHigh, (op))
1946	#define EXPECT_NEVER_OVERFLOWS(op) \
1947	EXPECT_EQ(ConstantRange::OverflowResult::NeverOverflows, (op))
1948
1949	TEST_F(ConstantRangeTest, UnsignedAddOverflow) {
1950	// Ill-defined - may overflow is a conservative result.
1951	EXPECT_MAY_OVERFLOW(Some.unsignedAddMayOverflow(Empty));
1952	EXPECT_MAY_OVERFLOW(Empty.unsignedAddMayOverflow(Some));
1953
1954	// Never overflow despite one full/wrap set.
1955	ConstantRange Zero(APInt::getZero(numBits: 16));
1956	EXPECT_NEVER_OVERFLOWS(Full.unsignedAddMayOverflow(Zero));
1957	EXPECT_NEVER_OVERFLOWS(Wrap.unsignedAddMayOverflow(Zero));
1958	EXPECT_NEVER_OVERFLOWS(Zero.unsignedAddMayOverflow(Full));
1959	EXPECT_NEVER_OVERFLOWS(Zero.unsignedAddMayOverflow(Wrap));
1960
1961	// But usually full/wrap always may overflow.
1962	EXPECT_MAY_OVERFLOW(Full.unsignedAddMayOverflow(One));
1963	EXPECT_MAY_OVERFLOW(Wrap.unsignedAddMayOverflow(One));
1964	EXPECT_MAY_OVERFLOW(One.unsignedAddMayOverflow(Full));
1965	EXPECT_MAY_OVERFLOW(One.unsignedAddMayOverflow(Wrap));
1966
1967	ConstantRange A(APInt(16, 0xfd00), APInt(16, 0xfe00));
1968	ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
1969	ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
1970	EXPECT_NEVER_OVERFLOWS(A.unsignedAddMayOverflow(B1));
1971	EXPECT_MAY_OVERFLOW(A.unsignedAddMayOverflow(B2));
1972	EXPECT_NEVER_OVERFLOWS(B1.unsignedAddMayOverflow(A));
1973	EXPECT_MAY_OVERFLOW(B2.unsignedAddMayOverflow(A));
1974
1975	ConstantRange C1(APInt(16, 0x0299), APInt(16, 0x0400));
1976	ConstantRange C2(APInt(16, 0x0300), APInt(16, 0x0400));
1977	EXPECT_MAY_OVERFLOW(A.unsignedAddMayOverflow(C1));
1978	EXPECT_ALWAYS_OVERFLOWS_HIGH(A.unsignedAddMayOverflow(C2));
1979	EXPECT_MAY_OVERFLOW(C1.unsignedAddMayOverflow(A));
1980	EXPECT_ALWAYS_OVERFLOWS_HIGH(C2.unsignedAddMayOverflow(A));
1981	}
1982
1983	TEST_F(ConstantRangeTest, UnsignedSubOverflow) {
1984	// Ill-defined - may overflow is a conservative result.
1985	EXPECT_MAY_OVERFLOW(Some.unsignedSubMayOverflow(Empty));
1986	EXPECT_MAY_OVERFLOW(Empty.unsignedSubMayOverflow(Some));
1987
1988	// Never overflow despite one full/wrap set.
1989	ConstantRange Zero(APInt::getZero(numBits: 16));
1990	ConstantRange Max(APInt::getAllOnes(numBits: 16));
1991	EXPECT_NEVER_OVERFLOWS(Full.unsignedSubMayOverflow(Zero));
1992	EXPECT_NEVER_OVERFLOWS(Wrap.unsignedSubMayOverflow(Zero));
1993	EXPECT_NEVER_OVERFLOWS(Max.unsignedSubMayOverflow(Full));
1994	EXPECT_NEVER_OVERFLOWS(Max.unsignedSubMayOverflow(Wrap));
1995
1996	// But usually full/wrap always may overflow.
1997	EXPECT_MAY_OVERFLOW(Full.unsignedSubMayOverflow(One));
1998	EXPECT_MAY_OVERFLOW(Wrap.unsignedSubMayOverflow(One));
1999	EXPECT_MAY_OVERFLOW(One.unsignedSubMayOverflow(Full));
2000	EXPECT_MAY_OVERFLOW(One.unsignedSubMayOverflow(Wrap));
2001
2002	ConstantRange A(APInt(16, 0x0000), APInt(16, 0x0100));
2003	ConstantRange B(APInt(16, 0x0100), APInt(16, 0x0200));
2004	EXPECT_NEVER_OVERFLOWS(B.unsignedSubMayOverflow(A));
2005	EXPECT_ALWAYS_OVERFLOWS_LOW(A.unsignedSubMayOverflow(B));
2006
2007	ConstantRange A1(APInt(16, 0x0000), APInt(16, 0x0101));
2008	ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
2009	EXPECT_NEVER_OVERFLOWS(B1.unsignedSubMayOverflow(A1));
2010	EXPECT_MAY_OVERFLOW(A1.unsignedSubMayOverflow(B1));
2011
2012	ConstantRange A2(APInt(16, 0x0000), APInt(16, 0x0102));
2013	ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
2014	EXPECT_MAY_OVERFLOW(B2.unsignedSubMayOverflow(A2));
2015	EXPECT_MAY_OVERFLOW(A2.unsignedSubMayOverflow(B2));
2016	}
2017
2018	TEST_F(ConstantRangeTest, SignedAddOverflow) {
2019	// Ill-defined - may overflow is a conservative result.
2020	EXPECT_MAY_OVERFLOW(Some.signedAddMayOverflow(Empty));
2021	EXPECT_MAY_OVERFLOW(Empty.signedAddMayOverflow(Some));
2022
2023	// Never overflow despite one full/wrap set.
2024	ConstantRange Zero(APInt::getZero(numBits: 16));
2025	EXPECT_NEVER_OVERFLOWS(Full.signedAddMayOverflow(Zero));
2026	EXPECT_NEVER_OVERFLOWS(Wrap.signedAddMayOverflow(Zero));
2027	EXPECT_NEVER_OVERFLOWS(Zero.signedAddMayOverflow(Full));
2028	EXPECT_NEVER_OVERFLOWS(Zero.signedAddMayOverflow(Wrap));
2029
2030	// But usually full/wrap always may overflow.
2031	EXPECT_MAY_OVERFLOW(Full.signedAddMayOverflow(One));
2032	EXPECT_MAY_OVERFLOW(Wrap.signedAddMayOverflow(One));
2033	EXPECT_MAY_OVERFLOW(One.signedAddMayOverflow(Full));
2034	EXPECT_MAY_OVERFLOW(One.signedAddMayOverflow(Wrap));
2035
2036	ConstantRange A(APInt(16, 0x7d00), APInt(16, 0x7e00));
2037	ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
2038	ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
2039	EXPECT_NEVER_OVERFLOWS(A.signedAddMayOverflow(B1));
2040	EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B2));
2041	ConstantRange B3(APInt(16, 0x8000), APInt(16, 0x0201));
2042	ConstantRange B4(APInt(16, 0x8000), APInt(16, 0x0202));
2043	EXPECT_NEVER_OVERFLOWS(A.signedAddMayOverflow(B3));
2044	EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B4));
2045	ConstantRange B5(APInt(16, 0x0299), APInt(16, 0x0400));
2046	ConstantRange B6(APInt(16, 0x0300), APInt(16, 0x0400));
2047	EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B5));
2048	EXPECT_ALWAYS_OVERFLOWS_HIGH(A.signedAddMayOverflow(B6));
2049
2050	ConstantRange C(APInt(16, 0x8200), APInt(16, 0x8300));
2051	ConstantRange D1(APInt(16, 0xfe00), APInt(16, 0xff00));
2052	ConstantRange D2(APInt(16, 0xfd99), APInt(16, 0xff00));
2053	EXPECT_NEVER_OVERFLOWS(C.signedAddMayOverflow(D1));
2054	EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D2));
2055	ConstantRange D3(APInt(16, 0xfe00), APInt(16, 0x8000));
2056	ConstantRange D4(APInt(16, 0xfd99), APInt(16, 0x8000));
2057	EXPECT_NEVER_OVERFLOWS(C.signedAddMayOverflow(D3));
2058	EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D4));
2059	ConstantRange D5(APInt(16, 0xfc00), APInt(16, 0xfd02));
2060	ConstantRange D6(APInt(16, 0xfc00), APInt(16, 0xfd01));
2061	EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D5));
2062	EXPECT_ALWAYS_OVERFLOWS_LOW(C.signedAddMayOverflow(D6));
2063
2064	ConstantRange E(APInt(16, 0xff00), APInt(16, 0x0100));
2065	EXPECT_NEVER_OVERFLOWS(E.signedAddMayOverflow(E));
2066	ConstantRange F(APInt(16, 0xf000), APInt(16, 0x7000));
2067	EXPECT_MAY_OVERFLOW(F.signedAddMayOverflow(F));
2068	}
2069
2070	TEST_F(ConstantRangeTest, SignedSubOverflow) {
2071	// Ill-defined - may overflow is a conservative result.
2072	EXPECT_MAY_OVERFLOW(Some.signedSubMayOverflow(Empty));
2073	EXPECT_MAY_OVERFLOW(Empty.signedSubMayOverflow(Some));
2074
2075	// Never overflow despite one full/wrap set.
2076	ConstantRange Zero(APInt::getZero(numBits: 16));
2077	EXPECT_NEVER_OVERFLOWS(Full.signedSubMayOverflow(Zero));
2078	EXPECT_NEVER_OVERFLOWS(Wrap.signedSubMayOverflow(Zero));
2079
2080	// But usually full/wrap always may overflow.
2081	EXPECT_MAY_OVERFLOW(Full.signedSubMayOverflow(One));
2082	EXPECT_MAY_OVERFLOW(Wrap.signedSubMayOverflow(One));
2083	EXPECT_MAY_OVERFLOW(One.signedSubMayOverflow(Full));
2084	EXPECT_MAY_OVERFLOW(One.signedSubMayOverflow(Wrap));
2085
2086	ConstantRange A(APInt(16, 0x7d00), APInt(16, 0x7e00));
2087	ConstantRange B1(APInt(16, 0xfe00), APInt(16, 0xff00));
2088	ConstantRange B2(APInt(16, 0xfd99), APInt(16, 0xff00));
2089	EXPECT_NEVER_OVERFLOWS(A.signedSubMayOverflow(B1));
2090	EXPECT_MAY_OVERFLOW(A.signedSubMayOverflow(B2));
2091	ConstantRange B3(APInt(16, 0xfc00), APInt(16, 0xfd02));
2092	ConstantRange B4(APInt(16, 0xfc00), APInt(16, 0xfd01));
2093	EXPECT_MAY_OVERFLOW(A.signedSubMayOverflow(B3));
2094	EXPECT_ALWAYS_OVERFLOWS_HIGH(A.signedSubMayOverflow(B4));
2095
2096	ConstantRange C(APInt(16, 0x8200), APInt(16, 0x8300));
2097	ConstantRange D1(APInt(16, 0x0100), APInt(16, 0x0201));
2098	ConstantRange D2(APInt(16, 0x0100), APInt(16, 0x0202));
2099	EXPECT_NEVER_OVERFLOWS(C.signedSubMayOverflow(D1));
2100	EXPECT_MAY_OVERFLOW(C.signedSubMayOverflow(D2));
2101	ConstantRange D3(APInt(16, 0x0299), APInt(16, 0x0400));
2102	ConstantRange D4(APInt(16, 0x0300), APInt(16, 0x0400));
2103	EXPECT_MAY_OVERFLOW(C.signedSubMayOverflow(D3));
2104	EXPECT_ALWAYS_OVERFLOWS_LOW(C.signedSubMayOverflow(D4));
2105
2106	ConstantRange E(APInt(16, 0xff00), APInt(16, 0x0100));
2107	EXPECT_NEVER_OVERFLOWS(E.signedSubMayOverflow(E));
2108	ConstantRange F(APInt(16, 0xf000), APInt(16, 0x7001));
2109	EXPECT_MAY_OVERFLOW(F.signedSubMayOverflow(F));
2110	}
2111
2112	template <typename Fn1, typename Fn2>
2113	static void TestOverflowExhaustive(Fn1 OverflowFn, Fn2 MayOverflowFn) {
2114	// Constant range overflow checks are tested exhaustively on 4-bit numbers.
2115	EnumerateTwoInterestingConstantRanges([=](const ConstantRange &CR1,
2116	const ConstantRange &CR2) {
2117	// Loop over all N1 in CR1 and N2 in CR2 and check whether any of the
2118	// operations have overflow / have no overflow.
2119	bool RangeHasOverflowLow = false;
2120	bool RangeHasOverflowHigh = false;
2121	bool RangeHasNoOverflow = false;
2122	ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
2123	ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
2124	bool IsOverflowHigh;
2125	if (!OverflowFn(IsOverflowHigh, N1, N2)) {
2126	RangeHasNoOverflow = true;
2127	return;
2128	}
2129
2130	if (IsOverflowHigh)
2131	RangeHasOverflowHigh = true;
2132	else
2133	RangeHasOverflowLow = true;
2134	});
2135	});
2136
2137	ConstantRange::OverflowResult OR = MayOverflowFn(CR1, CR2);
2138	switch (OR) {
2139	case ConstantRange::OverflowResult::AlwaysOverflowsLow:
2140	EXPECT_TRUE(RangeHasOverflowLow);
2141	EXPECT_FALSE(RangeHasOverflowHigh);
2142	EXPECT_FALSE(RangeHasNoOverflow);
2143	break;
2144	case ConstantRange::OverflowResult::AlwaysOverflowsHigh:
2145	EXPECT_TRUE(RangeHasOverflowHigh);
2146	EXPECT_FALSE(RangeHasOverflowLow);
2147	EXPECT_FALSE(RangeHasNoOverflow);
2148	break;
2149	case ConstantRange::OverflowResult::NeverOverflows:
2150	EXPECT_FALSE(RangeHasOverflowLow);
2151	EXPECT_FALSE(RangeHasOverflowHigh);
2152	EXPECT_TRUE(RangeHasNoOverflow);
2153	break;
2154	case ConstantRange::OverflowResult::MayOverflow:
2155	// We return MayOverflow for empty sets as a conservative result,
2156	// but of course neither the RangeHasOverflow nor the
2157	// RangeHasNoOverflow flags will be set.
2158	if (CR1.isEmptySet() || CR2.isEmptySet())
2159	break;
2160
2161	EXPECT_TRUE(RangeHasOverflowLow || RangeHasOverflowHigh);
2162	EXPECT_TRUE(RangeHasNoOverflow);
2163	break;
2164	}
2165	});
2166	}
2167
2168	TEST_F(ConstantRangeTest, UnsignedAddOverflowExhaustive) {
2169	TestOverflowExhaustive(
2170	OverflowFn: [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
2171	bool Overflow;
2172	(void) N1.uadd_ov(RHS: N2, Overflow);
2173	IsOverflowHigh = true;
2174	return Overflow;
2175	},
2176	MayOverflowFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
2177	return CR1.unsignedAddMayOverflow(Other: CR2);
2178	});
2179	}
2180
2181	TEST_F(ConstantRangeTest, UnsignedSubOverflowExhaustive) {
2182	TestOverflowExhaustive(
2183	OverflowFn: [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
2184	bool Overflow;
2185	(void) N1.usub_ov(RHS: N2, Overflow);
2186	IsOverflowHigh = false;
2187	return Overflow;
2188	},
2189	MayOverflowFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
2190	return CR1.unsignedSubMayOverflow(Other: CR2);
2191	});
2192	}
2193
2194	TEST_F(ConstantRangeTest, UnsignedMulOverflowExhaustive) {
2195	TestOverflowExhaustive(
2196	OverflowFn: [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
2197	bool Overflow;
2198	(void) N1.umul_ov(RHS: N2, Overflow);
2199	IsOverflowHigh = true;
2200	return Overflow;
2201	},
2202	MayOverflowFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
2203	return CR1.unsignedMulMayOverflow(Other: CR2);
2204	});
2205	}
2206
2207	TEST_F(ConstantRangeTest, SignedAddOverflowExhaustive) {
2208	TestOverflowExhaustive(
2209	OverflowFn: [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
2210	bool Overflow;
2211	(void) N1.sadd_ov(RHS: N2, Overflow);
2212	IsOverflowHigh = N1.isNonNegative();
2213	return Overflow;
2214	},
2215	MayOverflowFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
2216	return CR1.signedAddMayOverflow(Other: CR2);
2217	});
2218	}
2219
2220	TEST_F(ConstantRangeTest, SignedSubOverflowExhaustive) {
2221	TestOverflowExhaustive(
2222	OverflowFn: [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
2223	bool Overflow;
2224	(void) N1.ssub_ov(RHS: N2, Overflow);
2225	IsOverflowHigh = N1.isNonNegative();
2226	return Overflow;
2227	},
2228	MayOverflowFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
2229	return CR1.signedSubMayOverflow(Other: CR2);
2230	});
2231	}
2232
2233	TEST_F(ConstantRangeTest, FromKnownBits) {
2234	KnownBits Unknown(16);
2235	EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/false));
2236	EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/true));
2237
2238	// .10..01. -> unsigned 01000010 (66) to 11011011 (219)
2239	// -> signed 11000010 (194) to 01011011 (91)
2240	KnownBits Known(8);
2241	Known.Zero = 36;
2242	Known.One = 66;
2243	ConstantRange Unsigned(APInt(8, 66), APInt(8, 219 + 1));
2244	ConstantRange Signed(APInt(8, 194), APInt(8, 91 + 1));
2245	EXPECT_EQ(Unsigned, ConstantRange::fromKnownBits(Known, /*signed*/false));
2246	EXPECT_EQ(Signed, ConstantRange::fromKnownBits(Known, /*signed*/true));
2247
2248	// 1.10.10. -> 10100100 (164) to 11101101 (237)
2249	Known.Zero = 18;
2250	Known.One = 164;
2251	ConstantRange CR1(APInt(8, 164), APInt(8, 237 + 1));
2252	EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/false));
2253	EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/true));
2254
2255	// 01.0.1.0 -> 01000100 (68) to 01101110 (110)
2256	Known.Zero = 145;
2257	Known.One = 68;
2258	ConstantRange CR2(APInt(8, 68), APInt(8, 110 + 1));
2259	EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/false));
2260	EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/true));
2261	}
2262
2263	TEST_F(ConstantRangeTest, FromKnownBitsExhaustive) {
2264	unsigned Bits = 4;
2265	unsigned Max = 1 << Bits;
2266	KnownBits Known(Bits);
2267	for (unsigned Zero = 0; Zero < Max; ++Zero) {
2268	for (unsigned One = 0; One < Max; ++One) {
2269	Known.Zero = Zero;
2270	Known.One = One;
2271	if (Known.hasConflict() || Known.isUnknown())
2272	continue;
2273
2274	SmallBitVector Elems(1 << Bits);
2275	for (unsigned N = 0; N < Max; ++N) {
2276	APInt Num(Bits, N);
2277	if ((Num & Known.Zero) != 0 || (~Num & Known.One) != 0)
2278	continue;
2279	Elems.set(Num.getZExtValue());
2280	}
2281
2282	TestRange(CR: ConstantRange::fromKnownBits(Known, IsSigned: false),
2283	Elems, PreferenceFn: PreferSmallestUnsigned, Inputs: {});
2284	TestRange(CR: ConstantRange::fromKnownBits(Known, IsSigned: true),
2285	Elems, PreferenceFn: PreferSmallestSigned, Inputs: {});
2286	}
2287	}
2288	}
2289
2290	TEST_F(ConstantRangeTest, ToKnownBits) {
2291	EnumerateInterestingConstantRanges(TestFn: [&](const ConstantRange &CR) {
2292	KnownBits Known = CR.toKnownBits();
2293	KnownBits ExpectedKnown(CR.getBitWidth());
2294	ExpectedKnown.Zero.setAllBits();
2295	ExpectedKnown.One.setAllBits();
2296	ForeachNumInConstantRange(CR, TestFn: [&](const APInt &N) {
2297	ExpectedKnown.One &= N;
2298	ExpectedKnown.Zero &= ~N;
2299	});
2300	// For an empty CR any result would be legal.
2301	if (!CR.isEmptySet()) {
2302	EXPECT_EQ(ExpectedKnown, Known);
2303	}
2304	});
2305	}
2306
2307	TEST_F(ConstantRangeTest, Negative) {
2308	// All elements in an empty set (of which there are none) are both negative
2309	// and non-negative. Empty & full sets checked explicitly for clarity, but
2310	// they are also covered by the exhaustive test below.
2311	EXPECT_TRUE(Empty.isAllNegative());
2312	EXPECT_TRUE(Empty.isAllNonNegative());
2313	EXPECT_FALSE(Full.isAllNegative());
2314	EXPECT_FALSE(Full.isAllNonNegative());
2315
2316	EnumerateInterestingConstantRanges(TestFn: [](const ConstantRange &CR) {
2317	bool AllNegative = true;
2318	bool AllNonNegative = true;
2319	ForeachNumInConstantRange(CR, TestFn: [&](const APInt &N) {
2320	if (!N.isNegative())
2321	AllNegative = false;
2322	if (!N.isNonNegative())
2323	AllNonNegative = false;
2324	});
2325	assert((CR.isEmptySet() || !AllNegative || !AllNonNegative) &&
2326	"Only empty set can be both all negative and all non-negative");
2327
2328	EXPECT_EQ(AllNegative, CR.isAllNegative());
2329	EXPECT_EQ(AllNonNegative, CR.isAllNonNegative());
2330	});
2331	}
2332
2333	TEST_F(ConstantRangeTest, UAddSat) {
2334	TestBinaryOpExhaustive(
2335	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
2336	return CR1.uadd_sat(Other: CR2);
2337	},
2338	IntFn: [](const APInt &N1, const APInt &N2) {
2339	return N1.uadd_sat(RHS: N2);
2340	},
2341	PreferenceFn: PreferSmallestUnsigned);
2342	}
2343
2344	TEST_F(ConstantRangeTest, USubSat) {
2345	TestBinaryOpExhaustive(
2346	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
2347	return CR1.usub_sat(Other: CR2);
2348	},
2349	IntFn: [](const APInt &N1, const APInt &N2) {
2350	return N1.usub_sat(RHS: N2);
2351	},
2352	PreferenceFn: PreferSmallestUnsigned);
2353	}
2354
2355	TEST_F(ConstantRangeTest, UMulSat) {
2356	TestBinaryOpExhaustive(
2357	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
2358	return CR1.umul_sat(Other: CR2);
2359	},
2360	IntFn: [](const APInt &N1, const APInt &N2) { return N1.umul_sat(RHS: N2); },
2361	PreferenceFn: PreferSmallestUnsigned);
2362	}
2363
2364	TEST_F(ConstantRangeTest, UShlSat) {
2365	TestBinaryOpExhaustive(
2366	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
2367	return CR1.ushl_sat(Other: CR2);
2368	},
2369	IntFn: [](const APInt &N1, const APInt &N2) { return N1.ushl_sat(RHS: N2); },
2370	PreferenceFn: PreferSmallestUnsigned);
2371	}
2372
2373	TEST_F(ConstantRangeTest, SAddSat) {
2374	TestBinaryOpExhaustive(
2375	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
2376	return CR1.sadd_sat(Other: CR2);
2377	},
2378	IntFn: [](const APInt &N1, const APInt &N2) {
2379	return N1.sadd_sat(RHS: N2);
2380	},
2381	PreferenceFn: PreferSmallestSigned);
2382	}
2383
2384	TEST_F(ConstantRangeTest, SSubSat) {
2385	TestBinaryOpExhaustive(
2386	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
2387	return CR1.ssub_sat(Other: CR2);
2388	},
2389	IntFn: [](const APInt &N1, const APInt &N2) {
2390	return N1.ssub_sat(RHS: N2);
2391	},
2392	PreferenceFn: PreferSmallestSigned);
2393	}
2394
2395	TEST_F(ConstantRangeTest, SMulSat) {
2396	TestBinaryOpExhaustive(
2397	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
2398	return CR1.smul_sat(Other: CR2);
2399	},
2400	IntFn: [](const APInt &N1, const APInt &N2) { return N1.smul_sat(RHS: N2); },
2401	PreferenceFn: PreferSmallestSigned);
2402	}
2403
2404	TEST_F(ConstantRangeTest, SShlSat) {
2405	TestBinaryOpExhaustive(
2406	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
2407	return CR1.sshl_sat(Other: CR2);
2408	},
2409	IntFn: [](const APInt &N1, const APInt &N2) { return N1.sshl_sat(RHS: N2); },
2410	PreferenceFn: PreferSmallestSigned);
2411	}
2412
2413	TEST_F(ConstantRangeTest, Abs) {
2414	TestUnaryOpExhaustive(
2415	RangeFn: [](const ConstantRange &CR) { return CR.abs(); },
2416	IntFn: [](const APInt &N) { return N.abs(); });
2417
2418	TestUnaryOpExhaustive(
2419	RangeFn: [](const ConstantRange &CR) { return CR.abs(/*IntMinIsPoison=*/true); },
2420	IntFn: [](const APInt &N) -> std::optional<APInt> {
2421	if (N.isMinSignedValue())
2422	return std::nullopt;
2423	return N.abs();
2424	});
2425	}
2426
2427	TEST_F(ConstantRangeTest, Ctlz) {
2428	TestUnaryOpExhaustive(
2429	RangeFn: [](const ConstantRange &CR) { return CR.ctlz(); },
2430	IntFn: [](const APInt &N) { return APInt(N.getBitWidth(), N.countl_zero()); });
2431
2432	TestUnaryOpExhaustive(
2433	RangeFn: [](const ConstantRange &CR) { return CR.ctlz(/*ZeroIsPoison=*/true); },
2434	IntFn: [](const APInt &N) -> std::optional<APInt> {
2435	if (N.isZero())
2436	return std::nullopt;
2437	return APInt(N.getBitWidth(), N.countl_zero());
2438	});
2439	}
2440
2441	TEST_F(ConstantRangeTest, Cttz) {
2442	TestUnaryOpExhaustive(
2443	RangeFn: [](const ConstantRange &CR) { return CR.cttz(); },
2444	IntFn: [](const APInt &N) { return APInt(N.getBitWidth(), N.countr_zero()); });
2445
2446	TestUnaryOpExhaustive(
2447	RangeFn: [](const ConstantRange &CR) { return CR.cttz(/*ZeroIsPoison=*/true); },
2448	IntFn: [](const APInt &N) -> std::optional<APInt> {
2449	if (N.isZero())
2450	return std::nullopt;
2451	return APInt(N.getBitWidth(), N.countr_zero());
2452	});
2453	}
2454
2455	TEST_F(ConstantRangeTest, Ctpop) {
2456	TestUnaryOpExhaustive(
2457	RangeFn: [](const ConstantRange &CR) { return CR.ctpop(); },
2458	IntFn: [](const APInt &N) { return APInt(N.getBitWidth(), N.popcount()); });
2459	}
2460
2461	TEST_F(ConstantRangeTest, castOps) {
2462	ConstantRange A(APInt(16, 66), APInt(16, 128));
2463	ConstantRange FpToI8 = A.castOp(CastOp: Instruction::FPToSI, BitWidth: 8);
2464	EXPECT_EQ(8u, FpToI8.getBitWidth());
2465	EXPECT_TRUE(FpToI8.isFullSet());
2466
2467	ConstantRange FpToI16 = A.castOp(CastOp: Instruction::FPToSI, BitWidth: 16);
2468	EXPECT_EQ(16u, FpToI16.getBitWidth());
2469	EXPECT_EQ(A, FpToI16);
2470
2471	ConstantRange FPExtToDouble = A.castOp(CastOp: Instruction::FPExt, BitWidth: 64);
2472	EXPECT_EQ(64u, FPExtToDouble.getBitWidth());
2473	EXPECT_TRUE(FPExtToDouble.isFullSet());
2474
2475	ConstantRange PtrToInt = A.castOp(CastOp: Instruction::PtrToInt, BitWidth: 64);
2476	EXPECT_EQ(64u, PtrToInt.getBitWidth());
2477	EXPECT_TRUE(PtrToInt.isFullSet());
2478
2479	ConstantRange IntToPtr = A.castOp(CastOp: Instruction::IntToPtr, BitWidth: 64);
2480	EXPECT_EQ(64u, IntToPtr.getBitWidth());
2481	EXPECT_TRUE(IntToPtr.isFullSet());
2482
2483	ConstantRange UIToFP = A.castOp(CastOp: Instruction::UIToFP, BitWidth: 16);
2484	EXPECT_EQ(16u, UIToFP.getBitWidth());
2485	EXPECT_TRUE(UIToFP.isFullSet());
2486
2487	ConstantRange UIToFP2 = A.castOp(CastOp: Instruction::UIToFP, BitWidth: 64);
2488	ConstantRange B(APInt(64, 0), APInt(64, 65536));
2489	EXPECT_EQ(64u, UIToFP2.getBitWidth());
2490	EXPECT_EQ(B, UIToFP2);
2491
2492	ConstantRange SIToFP = A.castOp(CastOp: Instruction::SIToFP, BitWidth: 16);
2493	EXPECT_EQ(16u, SIToFP.getBitWidth());
2494	EXPECT_TRUE(SIToFP.isFullSet());
2495
2496	ConstantRange SIToFP2 = A.castOp(CastOp: Instruction::SIToFP, BitWidth: 64);
2497	ConstantRange C(APInt(64, -32768), APInt(64, 32768));
2498	EXPECT_EQ(64u, SIToFP2.getBitWidth());
2499	EXPECT_EQ(C, SIToFP2);
2500	}
2501
2502	TEST_F(ConstantRangeTest, binaryAnd) {
2503	// Single element ranges.
2504	ConstantRange R16(APInt(8, 16));
2505	ConstantRange R20(APInt(8, 20));
2506	EXPECT_EQ(*R16.binaryAnd(R16).getSingleElement(), APInt(8, 16));
2507	EXPECT_EQ(*R16.binaryAnd(R20).getSingleElement(), APInt(8, 16 & 20));
2508
2509	ConstantRange R16_32(APInt(8, 16), APInt(8, 32));
2510	// 'And' with a high bits mask.
2511	ConstantRange R32(APInt(8, 32));
2512	EXPECT_TRUE(R16_32.binaryAnd(R32).getSingleElement()->isZero());
2513	EXPECT_TRUE(R32.binaryAnd(R16_32).getSingleElement()->isZero());
2514	// 'And' with a low bits mask. Handled conservatively for now.
2515	ConstantRange R4(APInt(8, 4));
2516	ConstantRange R0_5(APInt(8, 0), APInt(8, 5));
2517	EXPECT_EQ(R16_32.binaryAnd(R4), R0_5);
2518	EXPECT_EQ(R4.binaryAnd(R16_32), R0_5);
2519
2520	// Ranges with more than one element. Handled conservatively for now.
2521	ConstantRange R0_99(APInt(8, 0), APInt(8, 99));
2522	ConstantRange R0_32(APInt(8, 0), APInt(8, 32));
2523	EXPECT_EQ(R16_32.binaryAnd(R0_99), R0_32);
2524	EXPECT_EQ(R0_99.binaryAnd(R16_32), R0_32);
2525
2526	TestBinaryOpExhaustive(
2527	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
2528	return CR1.binaryAnd(Other: CR2);
2529	},
2530	IntFn: [](const APInt &N1, const APInt &N2) { return N1 & N2; }, PreferenceFn: PreferSmallest,
2531	CheckFn: CheckSingleElementsOnly);
2532	}
2533
2534	TEST_F(ConstantRangeTest, binaryOr) {
2535	// Single element ranges.
2536	ConstantRange R16(APInt(8, 16));
2537	ConstantRange R20(APInt(8, 20));
2538	EXPECT_EQ(*R16.binaryOr(R16).getSingleElement(), APInt(8, 16));
2539	EXPECT_EQ(*R16.binaryOr(R20).getSingleElement(), APInt(8, 16 | 20));
2540
2541	ConstantRange R16_32(APInt(8, 16), APInt(8, 32));
2542	// 'Or' with a high bits mask.
2543	// KnownBits estimate is important, otherwise the maximum included element
2544	// would be 2^8 - 1.
2545	ConstantRange R32(APInt(8, 32));
2546	ConstantRange R48_64(APInt(8, 48), APInt(8, 64));
2547	EXPECT_EQ(R16_32.binaryOr(R32), R48_64);
2548	EXPECT_EQ(R32.binaryOr(R16_32), R48_64);
2549	// 'Or' with a low bits mask.
2550	ConstantRange R4(APInt(8, 4));
2551	ConstantRange R0_16(APInt(8, 0), APInt(8, 16));
2552	ConstantRange R4_16(APInt(8, 4), APInt(8, 16));
2553	EXPECT_EQ(R0_16.binaryOr(R4), R4_16);
2554	EXPECT_EQ(R4.binaryOr(R0_16), R4_16);
2555
2556	// Ranges with more than one element. Handled conservatively for now.
2557	// UMaxUMin estimate is important, otherwise the lower bound would be zero.
2558	ConstantRange R0_64(APInt(8, 0), APInt(8, 64));
2559	ConstantRange R5_32(APInt(8, 5), APInt(8, 32));
2560	ConstantRange R5_64(APInt(8, 5), APInt(8, 64));
2561	EXPECT_EQ(R0_64.binaryOr(R5_32), R5_64);
2562	EXPECT_EQ(R5_32.binaryOr(R0_64), R5_64);
2563
2564	TestBinaryOpExhaustive(
2565	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
2566	return CR1.binaryOr(Other: CR2);
2567	},
2568	IntFn: [](const APInt &N1, const APInt &N2) { return N1 | N2; }, PreferenceFn: PreferSmallest,
2569	CheckFn: CheckSingleElementsOnly);
2570	}
2571
2572	TEST_F(ConstantRangeTest, binaryXor) {
2573	// Single element ranges.
2574	ConstantRange R16(APInt(8, 16));
2575	ConstantRange R20(APInt(8, 20));
2576	EXPECT_EQ(*R16.binaryXor(R16).getSingleElement(), APInt(8, 0));
2577	EXPECT_EQ(*R16.binaryXor(R20).getSingleElement(), APInt(8, 16 ^ 20));
2578
2579	// Ranges with more than a single element.
2580	ConstantRange R16_35(APInt(8, 16), APInt(8, 35));
2581	ConstantRange R0_99(APInt(8, 0), APInt(8, 99));
2582	EXPECT_EQ(R16_35.binaryXor(R16_35), ConstantRange(APInt(8, 0), APInt(8, 64)));
2583	EXPECT_EQ(R16_35.binaryXor(R0_99), ConstantRange(APInt(8, 0), APInt(8, 128)));
2584	EXPECT_EQ(R0_99.binaryXor(R16_35), ConstantRange(APInt(8, 0), APInt(8, 128)));
2585
2586	// Treat xor A, B as sub nsw nuw A, B
2587	ConstantRange R0_51(APInt(8, 0), APInt(8, 51));
2588	ConstantRange R63(APInt(8, 63));
2589	EXPECT_EQ(R0_51.binaryXor(R63), ConstantRange(APInt(8, 13), APInt(8, 64)));
2590	EXPECT_EQ(R63.binaryXor(R0_51), ConstantRange(APInt(8, 13), APInt(8, 64)));
2591
2592	TestBinaryOpExhaustive(
2593	RangeFn: [](const ConstantRange &CR1, const ConstantRange &CR2) {
2594	return CR1.binaryXor(Other: CR2);
2595	},
2596	IntFn: [](const APInt &N1, const APInt &N2) {
2597	return N1 ^ N2;
2598	},
2599	PreferenceFn: PreferSmallest,
2600	CheckFn: CheckSingleElementsOnly);
2601	}
2602
2603	TEST_F(ConstantRangeTest, binaryNot) {
2604	TestUnaryOpExhaustive(
2605	RangeFn: [](const ConstantRange &CR) { return CR.binaryNot(); },
2606	IntFn: [](const APInt &N) { return ~N; },
2607	PreferenceFn: PreferSmallest);
2608	TestUnaryOpExhaustive(
2609	RangeFn: [](const ConstantRange &CR) {
2610	return CR.binaryXor(Other: ConstantRange(APInt::getAllOnes(numBits: CR.getBitWidth())));
2611	},
2612	IntFn: [](const APInt &N) { return ~N; }, PreferenceFn: PreferSmallest);
2613	TestUnaryOpExhaustive(
2614	RangeFn: [](const ConstantRange &CR) {
2615	return ConstantRange(APInt::getAllOnes(numBits: CR.getBitWidth())).binaryXor(Other: CR);
2616	},
2617	IntFn: [](const APInt &N) { return ~N; }, PreferenceFn: PreferSmallest);
2618	}
2619
2620	template <typename T>
2621	void testConstantRangeICmpPredEquivalence(ICmpInst::Predicate SrcPred, T Func) {
2622	EnumerateTwoInterestingConstantRanges(
2623	[&](const ConstantRange &CR1, const ConstantRange &CR2) {
2624	ICmpInst::Predicate TgtPred;
2625	bool ExpectedEquivalent;
2626	std::tie(args&: TgtPred, args&: ExpectedEquivalent) = Func(CR1, CR2);
2627	if (TgtPred == CmpInst::Predicate::BAD_ICMP_PREDICATE)
2628	return;
2629	bool TrulyEquivalent = true;
2630	ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
2631	if (!TrulyEquivalent)
2632	return;
2633	ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
2634	if (!TrulyEquivalent)
2635	return;
2636	TrulyEquivalent &= ICmpInst::compare(LHS: N1, RHS: N2, Pred: SrcPred) ==
2637	ICmpInst::compare(LHS: N1, RHS: N2, Pred: TgtPred);
2638	});
2639	});
2640	ASSERT_EQ(TrulyEquivalent, ExpectedEquivalent);
2641	});
2642	}
2643
2644	TEST_F(ConstantRangeTest, areInsensitiveToSignednessOfICmpPredicate) {
2645	for (auto Pred : ICmpInst::predicates()) {
2646	if (ICmpInst::isEquality(P: Pred))
2647	continue;
2648	ICmpInst::Predicate FlippedSignednessPred =
2649	ICmpInst::getFlippedSignednessPredicate(pred: Pred);
2650	testConstantRangeICmpPredEquivalence(SrcPred: Pred, Func: [FlippedSignednessPred](
2651	const ConstantRange &CR1,
2652	const ConstantRange &CR2) {
2653	return std::make_pair(
2654	x: FlippedSignednessPred,
2655	y: ConstantRange::areInsensitiveToSignednessOfICmpPredicate(CR1, CR2));
2656	});
2657	}
2658	}
2659
2660	TEST_F(ConstantRangeTest, areInsensitiveToSignednessOfInvertedICmpPredicate) {
2661	for (auto Pred : ICmpInst::predicates()) {
2662	if (ICmpInst::isEquality(P: Pred))
2663	continue;
2664	ICmpInst::Predicate InvertedFlippedSignednessPred =
2665	ICmpInst::getInversePredicate(
2666	pred: ICmpInst::getFlippedSignednessPredicate(pred: Pred));
2667	testConstantRangeICmpPredEquivalence(
2668	SrcPred: Pred, Func: [InvertedFlippedSignednessPred](const ConstantRange &CR1,
2669	const ConstantRange &CR2) {
2670	return std::make_pair(
2671	x: InvertedFlippedSignednessPred,
2672	y: ConstantRange::areInsensitiveToSignednessOfInvertedICmpPredicate(
2673	CR1, CR2));
2674	});
2675	}
2676	}
2677
2678	TEST_F(ConstantRangeTest, getEquivalentPredWithFlippedSignedness) {
2679	for (auto Pred : ICmpInst::predicates()) {
2680	if (ICmpInst::isEquality(P: Pred))
2681	continue;
2682	testConstantRangeICmpPredEquivalence(
2683	SrcPred: Pred, Func: [Pred](const ConstantRange &CR1, const ConstantRange &CR2) {
2684	return std::make_pair(
2685	x: ConstantRange::getEquivalentPredWithFlippedSignedness(Pred, CR1,
2686	CR2),
2687	/*ExpectedEquivalent=*/y: true);
2688	});
2689	}
2690	}
2691
2692	TEST_F(ConstantRangeTest, isSizeLargerThan) {
2693	EXPECT_FALSE(Empty.isSizeLargerThan(0));
2694
2695	EXPECT_TRUE(Full.isSizeLargerThan(0));
2696	EXPECT_TRUE(Full.isSizeLargerThan(65535));
2697	EXPECT_FALSE(Full.isSizeLargerThan(65536));
2698
2699	EXPECT_TRUE(One.isSizeLargerThan(0));
2700	EXPECT_FALSE(One.isSizeLargerThan(1));
2701	}
2702
2703	} // anonymous namespace
2704