1	//===- ConstantRange.cpp - ConstantRange implementation -------------------===//
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	// Represent a range of possible values that may occur when the program is run
10	// for an integral value. This keeps track of a lower and upper bound for the
11	// constant, which MAY wrap around the end of the numeric range. To do this, it
12	// keeps track of a [lower, upper) bound, which specifies an interval just like
13	// STL iterators. When used with boolean values, the following are important
14	// ranges (other integral ranges use min/max values for special range values):
15	//
16	// [F, F) = {} = Empty set
17	// [T, F) = {T}
18	// [F, T) = {F}
19	// [T, T) = {F, T} = Full set
20	//
21	//===----------------------------------------------------------------------===//
22
23	#include "llvm/ADT/APInt.h"
24	#include "llvm/Config/llvm-config.h"
25	#include "llvm/IR/ConstantRange.h"
26	#include "llvm/IR/Constants.h"
27	#include "llvm/IR/InstrTypes.h"
28	#include "llvm/IR/Instruction.h"
29	#include "llvm/IR/Intrinsics.h"
30	#include "llvm/IR/Metadata.h"
31	#include "llvm/IR/Operator.h"
32	#include "llvm/Support/Compiler.h"
33	#include "llvm/Support/Debug.h"
34	#include "llvm/Support/ErrorHandling.h"
35	#include "llvm/Support/KnownBits.h"
36	#include "llvm/Support/raw_ostream.h"
37	#include <algorithm>
38	#include <cassert>
39	#include <cstdint>
40	#include <optional>
41
42	using namespace llvm;
43
44	ConstantRange::ConstantRange(uint32_t BitWidth, bool Full)
45	: Lower(Full ? APInt::getMaxValue(numBits: BitWidth) : APInt::getMinValue(numBits: BitWidth)),
46	Upper(Lower) {}
47
48	ConstantRange::ConstantRange(APInt V)
49	: Lower(std::move(V)), Upper(Lower + 1) {}
50
51	ConstantRange::ConstantRange(APInt L, APInt U)
52	: Lower(std::move(L)), Upper(std::move(U)) {
53	assert(Lower.getBitWidth() == Upper.getBitWidth() &&
54	"ConstantRange with unequal bit widths");
55	assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) &&
56	"Lower == Upper, but they aren't min or max value!");
57	}
58
59	ConstantRange ConstantRange::fromKnownBits(const KnownBits &Known,
60	bool IsSigned) {
61	assert(!Known.hasConflict() && "Expected valid KnownBits");
62
63	if (Known.isUnknown())
64	return getFull(BitWidth: Known.getBitWidth());
65
66	// For unsigned ranges, or signed ranges with known sign bit, create a simple
67	// range between the smallest and largest possible value.
68	if (!IsSigned || Known.isNegative() || Known.isNonNegative())
69	return ConstantRange(Known.getMinValue(), Known.getMaxValue() + 1);
70
71	// If we don't know the sign bit, pick the lower bound as a negative number
72	// and the upper bound as a non-negative one.
73	APInt Lower = Known.getMinValue(), Upper = Known.getMaxValue();
74	Lower.setSignBit();
75	Upper.clearSignBit();
76	return ConstantRange(Lower, Upper + 1);
77	}
78
79	KnownBits ConstantRange::toKnownBits() const {
80	// TODO: We could return conflicting known bits here, but consumers are
81	// likely not prepared for that.
82	if (isEmptySet())
83	return KnownBits(getBitWidth());
84
85	// We can only retain the top bits that are the same between min and max.
86	APInt Min = getUnsignedMin();
87	APInt Max = getUnsignedMax();
88	KnownBits Known = KnownBits::makeConstant(C: Min);
89	if (std::optional<unsigned> DifferentBit =
90	APIntOps::GetMostSignificantDifferentBit(A: Min, B: Max)) {
91	Known.Zero.clearLowBits(loBits: *DifferentBit + 1);
92	Known.One.clearLowBits(loBits: *DifferentBit + 1);
93	}
94	return Known;
95	}
96
97	ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,
98	const ConstantRange &CR) {
99	if (CR.isEmptySet())
100	return CR;
101
102	uint32_t W = CR.getBitWidth();
103	switch (Pred) {
104	default:
105	llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
106	case CmpInst::ICMP_EQ:
107	return CR;
108	case CmpInst::ICMP_NE:
109	if (CR.isSingleElement())
110	return ConstantRange(CR.getUpper(), CR.getLower());
111	return getFull(BitWidth: W);
112	case CmpInst::ICMP_ULT: {
113	APInt UMax(CR.getUnsignedMax());
114	if (UMax.isMinValue())
115	return getEmpty(BitWidth: W);
116	return ConstantRange(APInt::getMinValue(numBits: W), std::move(UMax));
117	}
118	case CmpInst::ICMP_SLT: {
119	APInt SMax(CR.getSignedMax());
120	if (SMax.isMinSignedValue())
121	return getEmpty(BitWidth: W);
122	return ConstantRange(APInt::getSignedMinValue(numBits: W), std::move(SMax));
123	}
124	case CmpInst::ICMP_ULE:
125	return getNonEmpty(Lower: APInt::getMinValue(numBits: W), Upper: CR.getUnsignedMax() + 1);
126	case CmpInst::ICMP_SLE:
127	return getNonEmpty(Lower: APInt::getSignedMinValue(numBits: W), Upper: CR.getSignedMax() + 1);
128	case CmpInst::ICMP_UGT: {
129	APInt UMin(CR.getUnsignedMin());
130	if (UMin.isMaxValue())
131	return getEmpty(BitWidth: W);
132	return ConstantRange(std::move(UMin) + 1, APInt::getZero(numBits: W));
133	}
134	case CmpInst::ICMP_SGT: {
135	APInt SMin(CR.getSignedMin());
136	if (SMin.isMaxSignedValue())
137	return getEmpty(BitWidth: W);
138	return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(numBits: W));
139	}
140	case CmpInst::ICMP_UGE:
141	return getNonEmpty(Lower: CR.getUnsignedMin(), Upper: APInt::getZero(numBits: W));
142	case CmpInst::ICMP_SGE:
143	return getNonEmpty(Lower: CR.getSignedMin(), Upper: APInt::getSignedMinValue(numBits: W));
144	}
145	}
146
147	ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred,
148	const ConstantRange &CR) {
149	// Follows from De-Morgan's laws:
150	//
151	// ~(~A union ~B) == A intersect B.
152	//
153	return makeAllowedICmpRegion(Pred: CmpInst::getInversePredicate(pred: Pred), CR)
154	.inverse();
155	}
156
157	ConstantRange ConstantRange::makeExactICmpRegion(CmpInst::Predicate Pred,
158	const APInt &C) {
159	// Computes the exact range that is equal to both the constant ranges returned
160	// by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true
161	// when RHS is a singleton such as an APInt and so the assert is valid.
162	// However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion
163	// returns [0,4) but makeSatisfyICmpRegion returns [0,2).
164	//
165	assert(makeAllowedICmpRegion(Pred, C) == makeSatisfyingICmpRegion(Pred, C));
166	return makeAllowedICmpRegion(Pred, CR: C);
167	}
168
169	bool ConstantRange::areInsensitiveToSignednessOfICmpPredicate(
170	const ConstantRange &CR1, const ConstantRange &CR2) {
171	if (CR1.isEmptySet() || CR2.isEmptySet())
172	return true;
173
174	return (CR1.isAllNonNegative() && CR2.isAllNonNegative()) ||
175	(CR1.isAllNegative() && CR2.isAllNegative());
176	}
177
178	bool ConstantRange::areInsensitiveToSignednessOfInvertedICmpPredicate(
179	const ConstantRange &CR1, const ConstantRange &CR2) {
180	if (CR1.isEmptySet() || CR2.isEmptySet())
181	return true;
182
183	return (CR1.isAllNonNegative() && CR2.isAllNegative()) ||
184	(CR1.isAllNegative() && CR2.isAllNonNegative());
185	}
186
187	CmpInst::Predicate ConstantRange::getEquivalentPredWithFlippedSignedness(
188	CmpInst::Predicate Pred, const ConstantRange &CR1,
189	const ConstantRange &CR2) {
190	assert(CmpInst::isIntPredicate(Pred) && CmpInst::isRelational(Pred) &&
191	"Only for relational integer predicates!");
192
193	CmpInst::Predicate FlippedSignednessPred =
194	CmpInst::getFlippedSignednessPredicate(pred: Pred);
195
196	if (areInsensitiveToSignednessOfICmpPredicate(CR1, CR2))
197	return FlippedSignednessPred;
198
199	if (areInsensitiveToSignednessOfInvertedICmpPredicate(CR1, CR2))
200	return CmpInst::getInversePredicate(pred: FlippedSignednessPred);
201
202	return CmpInst::Predicate::BAD_ICMP_PREDICATE;
203	}
204
205	void ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,
206	APInt &RHS, APInt &Offset) const {
207	Offset = APInt(getBitWidth(), 0);
208	if (isFullSet() || isEmptySet()) {
209	Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE;
210	RHS = APInt(getBitWidth(), 0);
211	} else if (auto *OnlyElt = getSingleElement()) {
212	Pred = CmpInst::ICMP_EQ;
213	RHS = *OnlyElt;
214	} else if (auto *OnlyMissingElt = getSingleMissingElement()) {
215	Pred = CmpInst::ICMP_NE;
216	RHS = *OnlyMissingElt;
217	} else if (getLower().isMinSignedValue() || getLower().isMinValue()) {
218	Pred =
219	getLower().isMinSignedValue() ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
220	RHS = getUpper();
221	} else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {
222	Pred =
223	getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE;
224	RHS = getLower();
225	} else {
226	Pred = CmpInst::ICMP_ULT;
227	RHS = getUpper() - getLower();
228	Offset = -getLower();
229	}
230
231	assert(ConstantRange::makeExactICmpRegion(Pred, RHS) == add(Offset) &&
232	"Bad result!");
233	}
234
235	bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,
236	APInt &RHS) const {
237	APInt Offset;
238	getEquivalentICmp(Pred, RHS, Offset);
239	return Offset.isZero();
240	}
241
242	bool ConstantRange::icmp(CmpInst::Predicate Pred,
243	const ConstantRange &Other) const {
244	return makeSatisfyingICmpRegion(Pred, CR: Other).contains(CR: *this);
245	}
246
247	/// Exact mul nuw region for single element RHS.
248	static ConstantRange makeExactMulNUWRegion(const APInt &V) {
249	unsigned BitWidth = V.getBitWidth();
250	if (V == 0)
251	return ConstantRange::getFull(BitWidth: V.getBitWidth());
252
253	return ConstantRange::getNonEmpty(
254	Lower: APIntOps::RoundingUDiv(A: APInt::getMinValue(numBits: BitWidth), B: V,
255	RM: APInt::Rounding::UP),
256	Upper: APIntOps::RoundingUDiv(A: APInt::getMaxValue(numBits: BitWidth), B: V,
257	RM: APInt::Rounding::DOWN) + 1);
258	}
259
260	/// Exact mul nsw region for single element RHS.
261	static ConstantRange makeExactMulNSWRegion(const APInt &V) {
262	// Handle 0 and -1 separately to avoid division by zero or overflow.
263	unsigned BitWidth = V.getBitWidth();
264	if (V == 0)
265	return ConstantRange::getFull(BitWidth);
266
267	APInt MinValue = APInt::getSignedMinValue(numBits: BitWidth);
268	APInt MaxValue = APInt::getSignedMaxValue(numBits: BitWidth);
269	// e.g. Returning [-127, 127], represented as [-127, -128).
270	if (V.isAllOnes())
271	return ConstantRange(-MaxValue, MinValue);
272
273	APInt Lower, Upper;
274	if (V.isNegative()) {
275	Lower = APIntOps::RoundingSDiv(A: MaxValue, B: V, RM: APInt::Rounding::UP);
276	Upper = APIntOps::RoundingSDiv(A: MinValue, B: V, RM: APInt::Rounding::DOWN);
277	} else {
278	Lower = APIntOps::RoundingSDiv(A: MinValue, B: V, RM: APInt::Rounding::UP);
279	Upper = APIntOps::RoundingSDiv(A: MaxValue, B: V, RM: APInt::Rounding::DOWN);
280	}
281	return ConstantRange::getNonEmpty(Lower, Upper: Upper + 1);
282	}
283
284	ConstantRange
285	ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,
286	const ConstantRange &Other,
287	unsigned NoWrapKind) {
288	using OBO = OverflowingBinaryOperator;
289
290	assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
291
292	assert((NoWrapKind == OBO::NoSignedWrap ||
293	NoWrapKind == OBO::NoUnsignedWrap) &&
294	"NoWrapKind invalid!");
295
296	bool Unsigned = NoWrapKind == OBO::NoUnsignedWrap;
297	unsigned BitWidth = Other.getBitWidth();
298
299	switch (BinOp) {
300	default:
301	llvm_unreachable("Unsupported binary op");
302
303	case Instruction::Add: {
304	if (Unsigned)
305	return getNonEmpty(Lower: APInt::getZero(numBits: BitWidth), Upper: -Other.getUnsignedMax());
306
307	APInt SignedMinVal = APInt::getSignedMinValue(numBits: BitWidth);
308	APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax();
309	return getNonEmpty(
310	Lower: SMin.isNegative() ? SignedMinVal - SMin : SignedMinVal,
311	Upper: SMax.isStrictlyPositive() ? SignedMinVal - SMax : SignedMinVal);
312	}
313
314	case Instruction::Sub: {
315	if (Unsigned)
316	return getNonEmpty(Lower: Other.getUnsignedMax(), Upper: APInt::getMinValue(numBits: BitWidth));
317
318	APInt SignedMinVal = APInt::getSignedMinValue(numBits: BitWidth);
319	APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax();
320	return getNonEmpty(
321	Lower: SMax.isStrictlyPositive() ? SignedMinVal + SMax : SignedMinVal,
322	Upper: SMin.isNegative() ? SignedMinVal + SMin : SignedMinVal);
323	}
324
325	case Instruction::Mul:
326	if (Unsigned)
327	return makeExactMulNUWRegion(V: Other.getUnsignedMax());
328
329	// Avoid one makeExactMulNSWRegion() call for the common case of constants.
330	if (const APInt *C = Other.getSingleElement())
331	return makeExactMulNSWRegion(V: *C);
332
333	return makeExactMulNSWRegion(V: Other.getSignedMin())
334	.intersectWith(CR: makeExactMulNSWRegion(V: Other.getSignedMax()));
335
336	case Instruction::Shl: {
337	// For given range of shift amounts, if we ignore all illegal shift amounts
338	// (that always produce poison), what shift amount range is left?
339	ConstantRange ShAmt = Other.intersectWith(
340	CR: ConstantRange(APInt(BitWidth, 0), APInt(BitWidth, (BitWidth - 1) + 1)));
341	if (ShAmt.isEmptySet()) {
342	// If the entire range of shift amounts is already poison-producing,
343	// then we can freely add more poison-producing flags ontop of that.
344	return getFull(BitWidth);
345	}
346	// There are some legal shift amounts, we can compute conservatively-correct
347	// range of no-wrap inputs. Note that by now we have clamped the ShAmtUMax
348	// to be at most bitwidth-1, which results in most conservative range.
349	APInt ShAmtUMax = ShAmt.getUnsignedMax();
350	if (Unsigned)
351	return getNonEmpty(Lower: APInt::getZero(numBits: BitWidth),
352	Upper: APInt::getMaxValue(numBits: BitWidth).lshr(ShiftAmt: ShAmtUMax) + 1);
353	return getNonEmpty(Lower: APInt::getSignedMinValue(numBits: BitWidth).ashr(ShiftAmt: ShAmtUMax),
354	Upper: APInt::getSignedMaxValue(numBits: BitWidth).ashr(ShiftAmt: ShAmtUMax) + 1);
355	}
356	}
357	}
358
359	ConstantRange ConstantRange::makeExactNoWrapRegion(Instruction::BinaryOps BinOp,
360	const APInt &Other,
361	unsigned NoWrapKind) {
362	// makeGuaranteedNoWrapRegion() is exact for single-element ranges, as
363	// "for all" and "for any" coincide in this case.
364	return makeGuaranteedNoWrapRegion(BinOp, Other: ConstantRange(Other), NoWrapKind);
365	}
366
367	bool ConstantRange::isFullSet() const {
368	return Lower == Upper && Lower.isMaxValue();
369	}
370
371	bool ConstantRange::isEmptySet() const {
372	return Lower == Upper && Lower.isMinValue();
373	}
374
375	bool ConstantRange::isWrappedSet() const {
376	return Lower.ugt(RHS: Upper) && !Upper.isZero();
377	}
378
379	bool ConstantRange::isUpperWrapped() const {
380	return Lower.ugt(RHS: Upper);
381	}
382
383	bool ConstantRange::isSignWrappedSet() const {
384	return Lower.sgt(RHS: Upper) && !Upper.isMinSignedValue();
385	}
386
387	bool ConstantRange::isUpperSignWrapped() const {
388	return Lower.sgt(RHS: Upper);
389	}
390
391	bool
392	ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const {
393	assert(getBitWidth() == Other.getBitWidth());
394	if (isFullSet())
395	return false;
396	if (Other.isFullSet())
397	return true;
398	return (Upper - Lower).ult(RHS: Other.Upper - Other.Lower);
399	}
400
401	bool
402	ConstantRange::isSizeLargerThan(uint64_t MaxSize) const {
403	// If this a full set, we need special handling to avoid needing an extra bit
404	// to represent the size.
405	if (isFullSet())
406	return MaxSize == 0 || APInt::getMaxValue(numBits: getBitWidth()).ugt(RHS: MaxSize - 1);
407
408	return (Upper - Lower).ugt(RHS: MaxSize);
409	}
410
411	bool ConstantRange::isAllNegative() const {
412	// Empty set is all negative, full set is not.
413	if (isEmptySet())
414	return true;
415	if (isFullSet())
416	return false;
417
418	return !isUpperSignWrapped() && !Upper.isStrictlyPositive();
419	}
420
421	bool ConstantRange::isAllNonNegative() const {
422	// Empty and full set are automatically treated correctly.
423	return !isSignWrappedSet() && Lower.isNonNegative();
424	}
425
426	APInt ConstantRange::getUnsignedMax() const {
427	if (isFullSet() || isUpperWrapped())
428	return APInt::getMaxValue(numBits: getBitWidth());
429	return getUpper() - 1;
430	}
431
432	APInt ConstantRange::getUnsignedMin() const {
433	if (isFullSet() || isWrappedSet())
434	return APInt::getMinValue(numBits: getBitWidth());
435	return getLower();
436	}
437
438	APInt ConstantRange::getSignedMax() const {
439	if (isFullSet() || isUpperSignWrapped())
440	return APInt::getSignedMaxValue(numBits: getBitWidth());
441	return getUpper() - 1;
442	}
443
444	APInt ConstantRange::getSignedMin() const {
445	if (isFullSet() || isSignWrappedSet())
446	return APInt::getSignedMinValue(numBits: getBitWidth());
447	return getLower();
448	}
449
450	bool ConstantRange::contains(const APInt &V) const {
451	if (Lower == Upper)
452	return isFullSet();
453
454	if (!isUpperWrapped())
455	return Lower.ule(RHS: V) && V.ult(RHS: Upper);
456	return Lower.ule(RHS: V) || V.ult(RHS: Upper);
457	}
458
459	bool ConstantRange::contains(const ConstantRange &Other) const {
460	if (isFullSet() || Other.isEmptySet()) return true;
461	if (isEmptySet() || Other.isFullSet()) return false;
462
463	if (!isUpperWrapped()) {
464	if (Other.isUpperWrapped())
465	return false;
466
467	return Lower.ule(RHS: Other.getLower()) && Other.getUpper().ule(RHS: Upper);
468	}
469
470	if (!Other.isUpperWrapped())
471	return Other.getUpper().ule(RHS: Upper) ||
472	Lower.ule(RHS: Other.getLower());
473
474	return Other.getUpper().ule(RHS: Upper) && Lower.ule(RHS: Other.getLower());
475	}
476
477	unsigned ConstantRange::getActiveBits() const {
478	if (isEmptySet())
479	return 0;
480
481	return getUnsignedMax().getActiveBits();
482	}
483
484	unsigned ConstantRange::getMinSignedBits() const {
485	if (isEmptySet())
486	return 0;
487
488	return std::max(a: getSignedMin().getSignificantBits(),
489	b: getSignedMax().getSignificantBits());
490	}
491
492	ConstantRange ConstantRange::subtract(const APInt &Val) const {
493	assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
494	// If the set is empty or full, don't modify the endpoints.
495	if (Lower == Upper)
496	return *this;
497	return ConstantRange(Lower - Val, Upper - Val);
498	}
499
500	ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
501	return intersectWith(CR: CR.inverse());
502	}
503
504	static ConstantRange getPreferredRange(
505	const ConstantRange &CR1, const ConstantRange &CR2,
506	ConstantRange::PreferredRangeType Type) {
507	if (Type == ConstantRange::Unsigned) {
508	if (!CR1.isWrappedSet() && CR2.isWrappedSet())
509	return CR1;
510	if (CR1.isWrappedSet() && !CR2.isWrappedSet())
511	return CR2;
512	} else if (Type == ConstantRange::Signed) {
513	if (!CR1.isSignWrappedSet() && CR2.isSignWrappedSet())
514	return CR1;
515	if (CR1.isSignWrappedSet() && !CR2.isSignWrappedSet())
516	return CR2;
517	}
518
519	if (CR1.isSizeStrictlySmallerThan(Other: CR2))
520	return CR1;
521	return CR2;
522	}
523
524	ConstantRange ConstantRange::intersectWith(const ConstantRange &CR,
525	PreferredRangeType Type) const {
526	assert(getBitWidth() == CR.getBitWidth() &&
527	"ConstantRange types don't agree!");
528
529	// Handle common cases.
530	if ( isEmptySet() || CR.isFullSet()) return *this;
531	if (CR.isEmptySet() || isFullSet()) return CR;
532
533	if (!isUpperWrapped() && CR.isUpperWrapped())
534	return CR.intersectWith(CR: *this, Type);
535
536	if (!isUpperWrapped() && !CR.isUpperWrapped()) {
537	if (Lower.ult(RHS: CR.Lower)) {
538	// L---U : this
539	// L---U : CR
540	if (Upper.ule(RHS: CR.Lower))
541	return getEmpty();
542
543	// L---U : this
544	// L---U : CR
545	if (Upper.ult(RHS: CR.Upper))
546	return ConstantRange(CR.Lower, Upper);
547
548	// L-------U : this
549	// L---U : CR
550	return CR;
551	}
552	// L---U : this
553	// L-------U : CR
554	if (Upper.ult(RHS: CR.Upper))
555	return *this;
556
557	// L-----U : this
558	// L-----U : CR
559	if (Lower.ult(RHS: CR.Upper))
560	return ConstantRange(Lower, CR.Upper);
561
562	// L---U : this
563	// L---U : CR
564	return getEmpty();
565	}
566
567	if (isUpperWrapped() && !CR.isUpperWrapped()) {
568	if (CR.Lower.ult(RHS: Upper)) {
569	// ------U L--- : this
570	// L--U : CR
571	if (CR.Upper.ult(RHS: Upper))
572	return CR;
573
574	// ------U L--- : this
575	// L------U : CR
576	if (CR.Upper.ule(RHS: Lower))
577	return ConstantRange(CR.Lower, Upper);
578
579	// ------U L--- : this
580	// L----------U : CR
581	return getPreferredRange(CR1: *this, CR2: CR, Type);
582	}
583	if (CR.Lower.ult(RHS: Lower)) {
584	// --U L---- : this
585	// L--U : CR
586	if (CR.Upper.ule(RHS: Lower))
587	return getEmpty();
588
589	// --U L---- : this
590	// L------U : CR
591	return ConstantRange(Lower, CR.Upper);
592	}
593
594	// --U L------ : this
595	// L--U : CR
596	return CR;
597	}
598
599	if (CR.Upper.ult(RHS: Upper)) {
600	// ------U L-- : this
601	// --U L------ : CR
602	if (CR.Lower.ult(RHS: Upper))
603	return getPreferredRange(CR1: *this, CR2: CR, Type);
604
605	// ----U L-- : this
606	// --U L---- : CR
607	if (CR.Lower.ult(RHS: Lower))
608	return ConstantRange(Lower, CR.Upper);
609
610	// ----U L---- : this
611	// --U L-- : CR
612	return CR;
613	}
614	if (CR.Upper.ule(RHS: Lower)) {
615	// --U L-- : this
616	// ----U L---- : CR
617	if (CR.Lower.ult(RHS: Lower))
618	return *this;
619
620	// --U L---- : this
621	// ----U L-- : CR
622	return ConstantRange(CR.Lower, Upper);
623	}
624
625	// --U L------ : this
626	// ------U L-- : CR
627	return getPreferredRange(CR1: *this, CR2: CR, Type);
628	}
629
630	ConstantRange ConstantRange::unionWith(const ConstantRange &CR,
631	PreferredRangeType Type) const {
632	assert(getBitWidth() == CR.getBitWidth() &&
633	"ConstantRange types don't agree!");
634
635	if ( isFullSet() || CR.isEmptySet()) return *this;
636	if (CR.isFullSet() || isEmptySet()) return CR;
637
638	if (!isUpperWrapped() && CR.isUpperWrapped())
639	return CR.unionWith(CR: *this, Type);
640
641	if (!isUpperWrapped() && !CR.isUpperWrapped()) {
642	// L---U and L---U : this
643	// L---U L---U : CR
644	// result in one of
645	// L---------U
646	// -----U L-----
647	if (CR.Upper.ult(RHS: Lower) || Upper.ult(RHS: CR.Lower))
648	return getPreferredRange(
649	CR1: ConstantRange(Lower, CR.Upper), CR2: ConstantRange(CR.Lower, Upper), Type);
650
651	APInt L = CR.Lower.ult(RHS: Lower) ? CR.Lower : Lower;
652	APInt U = (CR.Upper - 1).ugt(RHS: Upper - 1) ? CR.Upper : Upper;
653
654	if (L.isZero() && U.isZero())
655	return getFull();
656
657	return ConstantRange(std::move(L), std::move(U));
658	}
659
660	if (!CR.isUpperWrapped()) {
661	// ------U L----- and ------U L----- : this
662	// L--U L--U : CR
663	if (CR.Upper.ule(RHS: Upper) || CR.Lower.uge(RHS: Lower))
664	return *this;
665
666	// ------U L----- : this
667	// L---------U : CR
668	if (CR.Lower.ule(RHS: Upper) && Lower.ule(RHS: CR.Upper))
669	return getFull();
670
671	// ----U L---- : this
672	// L---U : CR
673	// results in one of
674	// ----------U L----
675	// ----U L----------
676	if (Upper.ult(RHS: CR.Lower) && CR.Upper.ult(RHS: Lower))
677	return getPreferredRange(
678	CR1: ConstantRange(Lower, CR.Upper), CR2: ConstantRange(CR.Lower, Upper), Type);
679
680	// ----U L----- : this
681	// L----U : CR
682	if (Upper.ult(RHS: CR.Lower) && Lower.ule(RHS: CR.Upper))
683	return ConstantRange(CR.Lower, Upper);
684
685	// ------U L---- : this
686	// L-----U : CR
687	assert(CR.Lower.ule(Upper) && CR.Upper.ult(Lower) &&
688	"ConstantRange::unionWith missed a case with one range wrapped");
689	return ConstantRange(Lower, CR.Upper);
690	}
691
692	// ------U L---- and ------U L---- : this
693	// -U L----------- and ------------U L : CR
694	if (CR.Lower.ule(RHS: Upper) || Lower.ule(RHS: CR.Upper))
695	return getFull();
696
697	APInt L = CR.Lower.ult(RHS: Lower) ? CR.Lower : Lower;
698	APInt U = CR.Upper.ugt(RHS: Upper) ? CR.Upper : Upper;
699
700	return ConstantRange(std::move(L), std::move(U));
701	}
702
703	std::optional<ConstantRange>
704	ConstantRange::exactIntersectWith(const ConstantRange &CR) const {
705	// TODO: This can be implemented more efficiently.
706	ConstantRange Result = intersectWith(CR);
707	if (Result == inverse().unionWith(CR: CR.inverse()).inverse())
708	return Result;
709	return std::nullopt;
710	}
711
712	std::optional<ConstantRange>
713	ConstantRange::exactUnionWith(const ConstantRange &CR) const {
714	// TODO: This can be implemented more efficiently.
715	ConstantRange Result = unionWith(CR);
716	if (Result == inverse().intersectWith(CR: CR.inverse()).inverse())
717	return Result;
718	return std::nullopt;
719	}
720
721	ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp,
722	uint32_t ResultBitWidth) const {
723	switch (CastOp) {
724	default:
725	llvm_unreachable("unsupported cast type");
726	case Instruction::Trunc:
727	return truncate(BitWidth: ResultBitWidth);
728	case Instruction::SExt:
729	return signExtend(BitWidth: ResultBitWidth);
730	case Instruction::ZExt:
731	return zeroExtend(BitWidth: ResultBitWidth);
732	case Instruction::BitCast:
733	return *this;
734	case Instruction::FPToUI:
735	case Instruction::FPToSI:
736	if (getBitWidth() == ResultBitWidth)
737	return *this;
738	else
739	return getFull(BitWidth: ResultBitWidth);
740	case Instruction::UIToFP: {
741	// TODO: use input range if available
742	auto BW = getBitWidth();
743	APInt Min = APInt::getMinValue(numBits: BW);
744	APInt Max = APInt::getMaxValue(numBits: BW);
745	if (ResultBitWidth > BW) {
746	Min = Min.zext(width: ResultBitWidth);
747	Max = Max.zext(width: ResultBitWidth);
748	}
749	return getNonEmpty(Lower: std::move(Min), Upper: std::move(Max) + 1);
750	}
751	case Instruction::SIToFP: {
752	// TODO: use input range if available
753	auto BW = getBitWidth();
754	APInt SMin = APInt::getSignedMinValue(numBits: BW);
755	APInt SMax = APInt::getSignedMaxValue(numBits: BW);
756	if (ResultBitWidth > BW) {
757	SMin = SMin.sext(width: ResultBitWidth);
758	SMax = SMax.sext(width: ResultBitWidth);
759	}
760	return getNonEmpty(Lower: std::move(SMin), Upper: std::move(SMax) + 1);
761	}
762	case Instruction::FPTrunc:
763	case Instruction::FPExt:
764	case Instruction::IntToPtr:
765	case Instruction::PtrToInt:
766	case Instruction::AddrSpaceCast:
767	// Conservatively return getFull set.
768	return getFull(BitWidth: ResultBitWidth);
769	};
770	}
771
772	ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
773	if (isEmptySet()) return getEmpty(BitWidth: DstTySize);
774
775	unsigned SrcTySize = getBitWidth();
776	assert(SrcTySize < DstTySize && "Not a value extension");
777	if (isFullSet() || isUpperWrapped()) {
778	// Change into [0, 1 << src bit width)
779	APInt LowerExt(DstTySize, 0);
780	if (!Upper) // special case: [X, 0) -- not really wrapping around
781	LowerExt = Lower.zext(width: DstTySize);
782	return ConstantRange(std::move(LowerExt),
783	APInt::getOneBitSet(numBits: DstTySize, BitNo: SrcTySize));
784	}
785
786	return ConstantRange(Lower.zext(width: DstTySize), Upper.zext(width: DstTySize));
787	}
788
789	ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
790	if (isEmptySet()) return getEmpty(BitWidth: DstTySize);
791
792	unsigned SrcTySize = getBitWidth();
793	assert(SrcTySize < DstTySize && "Not a value extension");
794
795	// special case: [X, INT_MIN) -- not really wrapping around
796	if (Upper.isMinSignedValue())
797	return ConstantRange(Lower.sext(width: DstTySize), Upper.zext(width: DstTySize));
798
799	if (isFullSet() || isSignWrappedSet()) {
800	return ConstantRange(APInt::getHighBitsSet(numBits: DstTySize,hiBitsSet: DstTySize-SrcTySize+1),
801	APInt::getLowBitsSet(numBits: DstTySize, loBitsSet: SrcTySize-1) + 1);
802	}
803
804	return ConstantRange(Lower.sext(width: DstTySize), Upper.sext(width: DstTySize));
805	}
806
807	ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
808	assert(getBitWidth() > DstTySize && "Not a value truncation");
809	if (isEmptySet())
810	return getEmpty(BitWidth: DstTySize);
811	if (isFullSet())
812	return getFull(BitWidth: DstTySize);
813
814	APInt LowerDiv(Lower), UpperDiv(Upper);
815	ConstantRange Union(DstTySize, /*isFullSet=*/false);
816
817	// Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
818	// We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
819	// then we do the union with [MaxValue, Upper)
820	if (isUpperWrapped()) {
821	// If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
822	// truncated range.
823	if (Upper.getActiveBits() > DstTySize || Upper.countr_one() == DstTySize)
824	return getFull(BitWidth: DstTySize);
825
826	Union = ConstantRange(APInt::getMaxValue(numBits: DstTySize),Upper.trunc(width: DstTySize));
827	UpperDiv.setAllBits();
828
829	// Union covers the MaxValue case, so return if the remaining range is just
830	// MaxValue(DstTy).
831	if (LowerDiv == UpperDiv)
832	return Union;
833	}
834
835	// Chop off the most significant bits that are past the destination bitwidth.
836	if (LowerDiv.getActiveBits() > DstTySize) {
837	// Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
838	APInt Adjust = LowerDiv & APInt::getBitsSetFrom(numBits: getBitWidth(), loBit: DstTySize);
839	LowerDiv -= Adjust;
840	UpperDiv -= Adjust;
841	}
842
843	unsigned UpperDivWidth = UpperDiv.getActiveBits();
844	if (UpperDivWidth <= DstTySize)
845	return ConstantRange(LowerDiv.trunc(width: DstTySize),
846	UpperDiv.trunc(width: DstTySize)).unionWith(CR: Union);
847
848	// The truncated value wraps around. Check if we can do better than fullset.
849	if (UpperDivWidth == DstTySize + 1) {
850	// Clear the MSB so that UpperDiv wraps around.
851	UpperDiv.clearBit(BitPosition: DstTySize);
852	if (UpperDiv.ult(RHS: LowerDiv))
853	return ConstantRange(LowerDiv.trunc(width: DstTySize),
854	UpperDiv.trunc(width: DstTySize)).unionWith(CR: Union);
855	}
856
857	return getFull(BitWidth: DstTySize);
858	}
859
860	ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
861	unsigned SrcTySize = getBitWidth();
862	if (SrcTySize > DstTySize)
863	return truncate(DstTySize);
864	if (SrcTySize < DstTySize)
865	return zeroExtend(DstTySize);
866	return *this;
867	}
868
869	ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
870	unsigned SrcTySize = getBitWidth();
871	if (SrcTySize > DstTySize)
872	return truncate(DstTySize);
873	if (SrcTySize < DstTySize)
874	return signExtend(DstTySize);
875	return *this;
876	}
877
878	ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
879	const ConstantRange &Other) const {
880	assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
881
882	switch (BinOp) {
883	case Instruction::Add:
884	return add(Other);
885	case Instruction::Sub:
886	return sub(Other);
887	case Instruction::Mul:
888	return multiply(Other);
889	case Instruction::UDiv:
890	return udiv(Other);
891	case Instruction::SDiv:
892	return sdiv(Other);
893	case Instruction::URem:
894	return urem(Other);
895	case Instruction::SRem:
896	return srem(Other);
897	case Instruction::Shl:
898	return shl(Other);
899	case Instruction::LShr:
900	return lshr(Other);
901	case Instruction::AShr:
902	return ashr(Other);
903	case Instruction::And:
904	return binaryAnd(Other);
905	case Instruction::Or:
906	return binaryOr(Other);
907	case Instruction::Xor:
908	return binaryXor(Other);
909	// Note: floating point operations applied to abstract ranges are just
910	// ideal integer operations with a lossy representation
911	case Instruction::FAdd:
912	return add(Other);
913	case Instruction::FSub:
914	return sub(Other);
915	case Instruction::FMul:
916	return multiply(Other);
917	default:
918	// Conservatively return getFull set.
919	return getFull();
920	}
921	}
922
923	ConstantRange ConstantRange::overflowingBinaryOp(Instruction::BinaryOps BinOp,
924	const ConstantRange &Other,
925	unsigned NoWrapKind) const {
926	assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
927
928	switch (BinOp) {
929	case Instruction::Add:
930	return addWithNoWrap(Other, NoWrapKind);
931	case Instruction::Sub:
932	return subWithNoWrap(Other, NoWrapKind);
933	default:
934	// Don't know about this Overflowing Binary Operation.
935	// Conservatively fallback to plain binop handling.
936	return binaryOp(BinOp, Other);
937	}
938	}
939
940	bool ConstantRange::isIntrinsicSupported(Intrinsic::ID IntrinsicID) {
941	switch (IntrinsicID) {
942	case Intrinsic::uadd_sat:
943	case Intrinsic::usub_sat:
944	case Intrinsic::sadd_sat:
945	case Intrinsic::ssub_sat:
946	case Intrinsic::umin:
947	case Intrinsic::umax:
948	case Intrinsic::smin:
949	case Intrinsic::smax:
950	case Intrinsic::abs:
951	case Intrinsic::ctlz:
952	case Intrinsic::cttz:
953	case Intrinsic::ctpop:
954	return true;
955	default:
956	return false;
957	}
958	}
959
960	ConstantRange ConstantRange::intrinsic(Intrinsic::ID IntrinsicID,
961	ArrayRef<ConstantRange> Ops) {
962	switch (IntrinsicID) {
963	case Intrinsic::uadd_sat:
964	return Ops[0].uadd_sat(Other: Ops[1]);
965	case Intrinsic::usub_sat:
966	return Ops[0].usub_sat(Other: Ops[1]);
967	case Intrinsic::sadd_sat:
968	return Ops[0].sadd_sat(Other: Ops[1]);
969	case Intrinsic::ssub_sat:
970	return Ops[0].ssub_sat(Other: Ops[1]);
971	case Intrinsic::umin:
972	return Ops[0].umin(Other: Ops[1]);
973	case Intrinsic::umax:
974	return Ops[0].umax(Other: Ops[1]);
975	case Intrinsic::smin:
976	return Ops[0].smin(Other: Ops[1]);
977	case Intrinsic::smax:
978	return Ops[0].smax(Other: Ops[1]);
979	case Intrinsic::abs: {
980	const APInt *IntMinIsPoison = Ops[1].getSingleElement();
981	assert(IntMinIsPoison && "Must be known (immarg)");
982	assert(IntMinIsPoison->getBitWidth() == 1 && "Must be boolean");
983	return Ops[0].abs(IntMinIsPoison: IntMinIsPoison->getBoolValue());
984	}
985	case Intrinsic::ctlz: {
986	const APInt *ZeroIsPoison = Ops[1].getSingleElement();
987	assert(ZeroIsPoison && "Must be known (immarg)");
988	assert(ZeroIsPoison->getBitWidth() == 1 && "Must be boolean");
989	return Ops[0].ctlz(ZeroIsPoison: ZeroIsPoison->getBoolValue());
990	}
991	case Intrinsic::cttz: {
992	const APInt *ZeroIsPoison = Ops[1].getSingleElement();
993	assert(ZeroIsPoison && "Must be known (immarg)");
994	assert(ZeroIsPoison->getBitWidth() == 1 && "Must be boolean");
995	return Ops[0].cttz(ZeroIsPoison: ZeroIsPoison->getBoolValue());
996	}
997	case Intrinsic::ctpop:
998	return Ops[0].ctpop();
999	default:
1000	assert(!isIntrinsicSupported(IntrinsicID) && "Shouldn't be supported");
1001	llvm_unreachable("Unsupported intrinsic");
1002	}
1003	}
1004
1005	ConstantRange
1006	ConstantRange::add(const ConstantRange &Other) const {
1007	if (isEmptySet() || Other.isEmptySet())
1008	return getEmpty();
1009	if (isFullSet() || Other.isFullSet())
1010	return getFull();
1011
1012	APInt NewLower = getLower() + Other.getLower();
1013	APInt NewUpper = getUpper() + Other.getUpper() - 1;
1014	if (NewLower == NewUpper)
1015	return getFull();
1016
1017	ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
1018	if (X.isSizeStrictlySmallerThan(Other: *this) ||
1019	X.isSizeStrictlySmallerThan(Other))
1020	// We've wrapped, therefore, full set.
1021	return getFull();
1022	return X;
1023	}
1024
1025	ConstantRange ConstantRange::addWithNoWrap(const ConstantRange &Other,
1026	unsigned NoWrapKind,
1027	PreferredRangeType RangeType) const {
1028	// Calculate the range for "X + Y" which is guaranteed not to wrap(overflow).
1029	// (X is from this, and Y is from Other)
1030	if (isEmptySet() || Other.isEmptySet())
1031	return getEmpty();
1032	if (isFullSet() && Other.isFullSet())
1033	return getFull();
1034
1035	using OBO = OverflowingBinaryOperator;
1036	ConstantRange Result = add(Other);
1037
1038	// If an overflow happens for every value pair in these two constant ranges,
1039	// we must return Empty set. In this case, we get that for free, because we
1040	// get lucky that intersection of add() with uadd_sat()/sadd_sat() results
1041	// in an empty set.
1042
1043	if (NoWrapKind & OBO::NoSignedWrap)
1044	Result = Result.intersectWith(CR: sadd_sat(Other), Type: RangeType);
1045
1046	if (NoWrapKind & OBO::NoUnsignedWrap)
1047	Result = Result.intersectWith(CR: uadd_sat(Other), Type: RangeType);
1048
1049	return Result;
1050	}
1051
1052	ConstantRange
1053	ConstantRange::sub(const ConstantRange &Other) const {
1054	if (isEmptySet() || Other.isEmptySet())
1055	return getEmpty();
1056	if (isFullSet() || Other.isFullSet())
1057	return getFull();
1058
1059	APInt NewLower = getLower() - Other.getUpper() + 1;
1060	APInt NewUpper = getUpper() - Other.getLower();
1061	if (NewLower == NewUpper)
1062	return getFull();
1063
1064	ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
1065	if (X.isSizeStrictlySmallerThan(Other: *this) ||
1066	X.isSizeStrictlySmallerThan(Other))
1067	// We've wrapped, therefore, full set.
1068	return getFull();
1069	return X;
1070	}
1071
1072	ConstantRange ConstantRange::subWithNoWrap(const ConstantRange &Other,
1073	unsigned NoWrapKind,
1074	PreferredRangeType RangeType) const {
1075	// Calculate the range for "X - Y" which is guaranteed not to wrap(overflow).
1076	// (X is from this, and Y is from Other)
1077	if (isEmptySet() || Other.isEmptySet())
1078	return getEmpty();
1079	if (isFullSet() && Other.isFullSet())
1080	return getFull();
1081
1082	using OBO = OverflowingBinaryOperator;
1083	ConstantRange Result = sub(Other);
1084
1085	// If an overflow happens for every value pair in these two constant ranges,
1086	// we must return Empty set. In signed case, we get that for free, because we
1087	// get lucky that intersection of sub() with ssub_sat() results in an
1088	// empty set. But for unsigned we must perform the overflow check manually.
1089
1090	if (NoWrapKind & OBO::NoSignedWrap)
1091	Result = Result.intersectWith(CR: ssub_sat(Other), Type: RangeType);
1092
1093	if (NoWrapKind & OBO::NoUnsignedWrap) {
1094	if (getUnsignedMax().ult(RHS: Other.getUnsignedMin()))
1095	return getEmpty(); // Always overflows.
1096	Result = Result.intersectWith(CR: usub_sat(Other), Type: RangeType);
1097	}
1098
1099	return Result;
1100	}
1101
1102	ConstantRange
1103	ConstantRange::multiply(const ConstantRange &Other) const {
1104	// TODO: If either operand is a single element and the multiply is known to
1105	// be non-wrapping, round the result min and max value to the appropriate
1106	// multiple of that element. If wrapping is possible, at least adjust the
1107	// range according to the greatest power-of-two factor of the single element.
1108
1109	if (isEmptySet() || Other.isEmptySet())
1110	return getEmpty();
1111
1112	if (const APInt *C = getSingleElement()) {
1113	if (C->isOne())
1114	return Other;
1115	if (C->isAllOnes())
1116	return ConstantRange(APInt::getZero(numBits: getBitWidth())).sub(Other);
1117	}
1118
1119	if (const APInt *C = Other.getSingleElement()) {
1120	if (C->isOne())
1121	return *this;
1122	if (C->isAllOnes())
1123	return ConstantRange(APInt::getZero(numBits: getBitWidth())).sub(Other: *this);
1124	}
1125
1126	// Multiplication is signedness-independent. However different ranges can be
1127	// obtained depending on how the input ranges are treated. These different
1128	// ranges are all conservatively correct, but one might be better than the
1129	// other. We calculate two ranges; one treating the inputs as unsigned
1130	// and the other signed, then return the smallest of these ranges.
1131
1132	// Unsigned range first.
1133	APInt this_min = getUnsignedMin().zext(width: getBitWidth() * 2);
1134	APInt this_max = getUnsignedMax().zext(width: getBitWidth() * 2);
1135	APInt Other_min = Other.getUnsignedMin().zext(width: getBitWidth() * 2);
1136	APInt Other_max = Other.getUnsignedMax().zext(width: getBitWidth() * 2);
1137
1138	ConstantRange Result_zext = ConstantRange(this_min * Other_min,
1139	this_max * Other_max + 1);
1140	ConstantRange UR = Result_zext.truncate(DstTySize: getBitWidth());
1141
1142	// If the unsigned range doesn't wrap, and isn't negative then it's a range
1143	// from one positive number to another which is as good as we can generate.
1144	// In this case, skip the extra work of generating signed ranges which aren't
1145	// going to be better than this range.
1146	if (!UR.isUpperWrapped() &&
1147	(UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))
1148	return UR;
1149
1150	// Now the signed range. Because we could be dealing with negative numbers
1151	// here, the lower bound is the smallest of the cartesian product of the
1152	// lower and upper ranges; for example:
1153	// [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
1154	// Similarly for the upper bound, swapping min for max.
1155
1156	this_min = getSignedMin().sext(width: getBitWidth() * 2);
1157	this_max = getSignedMax().sext(width: getBitWidth() * 2);
1158	Other_min = Other.getSignedMin().sext(width: getBitWidth() * 2);
1159	Other_max = Other.getSignedMax().sext(width: getBitWidth() * 2);
1160
1161	auto L = {this_min * Other_min, this_min * Other_max,
1162	this_max * Other_min, this_max * Other_max};
1163	auto Compare = [](const APInt &A, const APInt &B) { return A.slt(RHS: B); };
1164	ConstantRange Result_sext(std::min(l: L, comp: Compare), std::max(l: L, comp: Compare) + 1);
1165	ConstantRange SR = Result_sext.truncate(DstTySize: getBitWidth());
1166
1167	return UR.isSizeStrictlySmallerThan(Other: SR) ? UR : SR;
1168	}
1169
1170	ConstantRange ConstantRange::smul_fast(const ConstantRange &Other) const {
1171	if (isEmptySet() || Other.isEmptySet())
1172	return getEmpty();
1173
1174	APInt Min = getSignedMin();
1175	APInt Max = getSignedMax();
1176	APInt OtherMin = Other.getSignedMin();
1177	APInt OtherMax = Other.getSignedMax();
1178
1179	bool O1, O2, O3, O4;
1180	auto Muls = {Min.smul_ov(RHS: OtherMin, Overflow&: O1), Min.smul_ov(RHS: OtherMax, Overflow&: O2),
1181	Max.smul_ov(RHS: OtherMin, Overflow&: O3), Max.smul_ov(RHS: OtherMax, Overflow&: O4)};
1182	if (O1 || O2 || O3 || O4)
1183	return getFull();
1184
1185	auto Compare = [](const APInt &A, const APInt &B) { return A.slt(RHS: B); };
1186	return getNonEmpty(Lower: std::min(l: Muls, comp: Compare), Upper: std::max(l: Muls, comp: Compare) + 1);
1187	}
1188
1189	ConstantRange
1190	ConstantRange::smax(const ConstantRange &Other) const {
1191	// X smax Y is: range(smax(X_smin, Y_smin),
1192	// smax(X_smax, Y_smax))
1193	if (isEmptySet() || Other.isEmptySet())
1194	return getEmpty();
1195	APInt NewL = APIntOps::smax(A: getSignedMin(), B: Other.getSignedMin());
1196	APInt NewU = APIntOps::smax(A: getSignedMax(), B: Other.getSignedMax()) + 1;
1197	ConstantRange Res = getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1198	if (isSignWrappedSet() || Other.isSignWrappedSet())
1199	return Res.intersectWith(CR: unionWith(CR: Other, Type: Signed), Type: Signed);
1200	return Res;
1201	}
1202
1203	ConstantRange
1204	ConstantRange::umax(const ConstantRange &Other) const {
1205	// X umax Y is: range(umax(X_umin, Y_umin),
1206	// umax(X_umax, Y_umax))
1207	if (isEmptySet() || Other.isEmptySet())
1208	return getEmpty();
1209	APInt NewL = APIntOps::umax(A: getUnsignedMin(), B: Other.getUnsignedMin());
1210	APInt NewU = APIntOps::umax(A: getUnsignedMax(), B: Other.getUnsignedMax()) + 1;
1211	ConstantRange Res = getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1212	if (isWrappedSet() || Other.isWrappedSet())
1213	return Res.intersectWith(CR: unionWith(CR: Other, Type: Unsigned), Type: Unsigned);
1214	return Res;
1215	}
1216
1217	ConstantRange
1218	ConstantRange::smin(const ConstantRange &Other) const {
1219	// X smin Y is: range(smin(X_smin, Y_smin),
1220	// smin(X_smax, Y_smax))
1221	if (isEmptySet() || Other.isEmptySet())
1222	return getEmpty();
1223	APInt NewL = APIntOps::smin(A: getSignedMin(), B: Other.getSignedMin());
1224	APInt NewU = APIntOps::smin(A: getSignedMax(), B: Other.getSignedMax()) + 1;
1225	ConstantRange Res = getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1226	if (isSignWrappedSet() || Other.isSignWrappedSet())
1227	return Res.intersectWith(CR: unionWith(CR: Other, Type: Signed), Type: Signed);
1228	return Res;
1229	}
1230
1231	ConstantRange
1232	ConstantRange::umin(const ConstantRange &Other) const {
1233	// X umin Y is: range(umin(X_umin, Y_umin),
1234	// umin(X_umax, Y_umax))
1235	if (isEmptySet() || Other.isEmptySet())
1236	return getEmpty();
1237	APInt NewL = APIntOps::umin(A: getUnsignedMin(), B: Other.getUnsignedMin());
1238	APInt NewU = APIntOps::umin(A: getUnsignedMax(), B: Other.getUnsignedMax()) + 1;
1239	ConstantRange Res = getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1240	if (isWrappedSet() || Other.isWrappedSet())
1241	return Res.intersectWith(CR: unionWith(CR: Other, Type: Unsigned), Type: Unsigned);
1242	return Res;
1243	}
1244
1245	ConstantRange
1246	ConstantRange::udiv(const ConstantRange &RHS) const {
1247	if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isZero())
1248	return getEmpty();
1249
1250	APInt Lower = getUnsignedMin().udiv(RHS: RHS.getUnsignedMax());
1251
1252	APInt RHS_umin = RHS.getUnsignedMin();
1253	if (RHS_umin.isZero()) {
1254	// We want the lowest value in RHS excluding zero. Usually that would be 1
1255	// except for a range in the form of [X, 1) in which case it would be X.
1256	if (RHS.getUpper() == 1)
1257	RHS_umin = RHS.getLower();
1258	else
1259	RHS_umin = 1;
1260	}
1261
1262	APInt Upper = getUnsignedMax().udiv(RHS: RHS_umin) + 1;
1263	return getNonEmpty(Lower: std::move(Lower), Upper: std::move(Upper));
1264	}
1265
1266	ConstantRange ConstantRange::sdiv(const ConstantRange &RHS) const {
1267	// We split up the LHS and RHS into positive and negative components
1268	// and then also compute the positive and negative components of the result
1269	// separately by combining division results with the appropriate signs.
1270	APInt Zero = APInt::getZero(numBits: getBitWidth());
1271	APInt SignedMin = APInt::getSignedMinValue(numBits: getBitWidth());
1272	// There are no positive 1-bit values. The 1 would get interpreted as -1.
1273	ConstantRange PosFilter =
1274	getBitWidth() == 1 ? getEmpty()
1275	: ConstantRange(APInt(getBitWidth(), 1), SignedMin);
1276	ConstantRange NegFilter(SignedMin, Zero);
1277	ConstantRange PosL = intersectWith(CR: PosFilter);
1278	ConstantRange NegL = intersectWith(CR: NegFilter);
1279	ConstantRange PosR = RHS.intersectWith(CR: PosFilter);
1280	ConstantRange NegR = RHS.intersectWith(CR: NegFilter);
1281
1282	ConstantRange PosRes = getEmpty();
1283	if (!PosL.isEmptySet() && !PosR.isEmptySet())
1284	// pos / pos = pos.
1285	PosRes = ConstantRange(PosL.Lower.sdiv(RHS: PosR.Upper - 1),
1286	(PosL.Upper - 1).sdiv(RHS: PosR.Lower) + 1);
1287
1288	if (!NegL.isEmptySet() && !NegR.isEmptySet()) {
1289	// neg / neg = pos.
1290	//
1291	// We need to deal with one tricky case here: SignedMin / -1 is UB on the
1292	// IR level, so we'll want to exclude this case when calculating bounds.
1293	// (For APInts the operation is well-defined and yields SignedMin.) We
1294	// handle this by dropping either SignedMin from the LHS or -1 from the RHS.
1295	APInt Lo = (NegL.Upper - 1).sdiv(RHS: NegR.Lower);
1296	if (NegL.Lower.isMinSignedValue() && NegR.Upper.isZero()) {
1297	// Remove -1 from the LHS. Skip if it's the only element, as this would
1298	// leave us with an empty set.
1299	if (!NegR.Lower.isAllOnes()) {
1300	APInt AdjNegRUpper;
1301	if (RHS.Lower.isAllOnes())
1302	// Negative part of [-1, X] without -1 is [SignedMin, X].
1303	AdjNegRUpper = RHS.Upper;
1304	else
1305	// [X, -1] without -1 is [X, -2].
1306	AdjNegRUpper = NegR.Upper - 1;
1307
1308	PosRes = PosRes.unionWith(
1309	CR: ConstantRange(Lo, NegL.Lower.sdiv(RHS: AdjNegRUpper - 1) + 1));
1310	}
1311
1312	// Remove SignedMin from the RHS. Skip if it's the only element, as this
1313	// would leave us with an empty set.
1314	if (NegL.Upper != SignedMin + 1) {
1315	APInt AdjNegLLower;
1316	if (Upper == SignedMin + 1)
1317	// Negative part of [X, SignedMin] without SignedMin is [X, -1].
1318	AdjNegLLower = Lower;
1319	else
1320	// [SignedMin, X] without SignedMin is [SignedMin + 1, X].
1321	AdjNegLLower = NegL.Lower + 1;
1322
1323	PosRes = PosRes.unionWith(
1324	CR: ConstantRange(std::move(Lo),
1325	AdjNegLLower.sdiv(RHS: NegR.Upper - 1) + 1));
1326	}
1327	} else {
1328	PosRes = PosRes.unionWith(
1329	CR: ConstantRange(std::move(Lo), NegL.Lower.sdiv(RHS: NegR.Upper - 1) + 1));
1330	}
1331	}
1332
1333	ConstantRange NegRes = getEmpty();
1334	if (!PosL.isEmptySet() && !NegR.isEmptySet())
1335	// pos / neg = neg.
1336	NegRes = ConstantRange((PosL.Upper - 1).sdiv(RHS: NegR.Upper - 1),
1337	PosL.Lower.sdiv(RHS: NegR.Lower) + 1);
1338
1339	if (!NegL.isEmptySet() && !PosR.isEmptySet())
1340	// neg / pos = neg.
1341	NegRes = NegRes.unionWith(
1342	CR: ConstantRange(NegL.Lower.sdiv(RHS: PosR.Lower),
1343	(NegL.Upper - 1).sdiv(RHS: PosR.Upper - 1) + 1));
1344
1345	// Prefer a non-wrapping signed range here.
1346	ConstantRange Res = NegRes.unionWith(CR: PosRes, Type: PreferredRangeType::Signed);
1347
1348	// Preserve the zero that we dropped when splitting the LHS by sign.
1349	if (contains(V: Zero) && (!PosR.isEmptySet() || !NegR.isEmptySet()))
1350	Res = Res.unionWith(CR: ConstantRange(Zero));
1351	return Res;
1352	}
1353
1354	ConstantRange ConstantRange::urem(const ConstantRange &RHS) const {
1355	if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isZero())
1356	return getEmpty();
1357
1358	if (const APInt *RHSInt = RHS.getSingleElement()) {
1359	// UREM by null is UB.
1360	if (RHSInt->isZero())
1361	return getEmpty();
1362	// Use APInt's implementation of UREM for single element ranges.
1363	if (const APInt *LHSInt = getSingleElement())
1364	return {LHSInt->urem(RHS: *RHSInt)};
1365	}
1366
1367	// L % R for L < R is L.
1368	if (getUnsignedMax().ult(RHS: RHS.getUnsignedMin()))
1369	return *this;
1370
1371	// L % R is <= L and < R.
1372	APInt Upper = APIntOps::umin(A: getUnsignedMax(), B: RHS.getUnsignedMax() - 1) + 1;
1373	return getNonEmpty(Lower: APInt::getZero(numBits: getBitWidth()), Upper: std::move(Upper));
1374	}
1375
1376	ConstantRange ConstantRange::srem(const ConstantRange &RHS) const {
1377	if (isEmptySet() || RHS.isEmptySet())
1378	return getEmpty();
1379
1380	if (const APInt *RHSInt = RHS.getSingleElement()) {
1381	// SREM by null is UB.
1382	if (RHSInt->isZero())
1383	return getEmpty();
1384	// Use APInt's implementation of SREM for single element ranges.
1385	if (const APInt *LHSInt = getSingleElement())
1386	return {LHSInt->srem(RHS: *RHSInt)};
1387	}
1388
1389	ConstantRange AbsRHS = RHS.abs();
1390	APInt MinAbsRHS = AbsRHS.getUnsignedMin();
1391	APInt MaxAbsRHS = AbsRHS.getUnsignedMax();
1392
1393	// Modulus by zero is UB.
1394	if (MaxAbsRHS.isZero())
1395	return getEmpty();
1396
1397	if (MinAbsRHS.isZero())
1398	++MinAbsRHS;
1399
1400	APInt MinLHS = getSignedMin(), MaxLHS = getSignedMax();
1401
1402	if (MinLHS.isNonNegative()) {
1403	// L % R for L < R is L.
1404	if (MaxLHS.ult(RHS: MinAbsRHS))
1405	return *this;
1406
1407	// L % R is <= L and < R.
1408	APInt Upper = APIntOps::umin(A: MaxLHS, B: MaxAbsRHS - 1) + 1;
1409	return ConstantRange(APInt::getZero(numBits: getBitWidth()), std::move(Upper));
1410	}
1411
1412	// Same basic logic as above, but the result is negative.
1413	if (MaxLHS.isNegative()) {
1414	if (MinLHS.ugt(RHS: -MinAbsRHS))
1415	return *this;
1416
1417	APInt Lower = APIntOps::umax(A: MinLHS, B: -MaxAbsRHS + 1);
1418	return ConstantRange(std::move(Lower), APInt(getBitWidth(), 1));
1419	}
1420
1421	// LHS range crosses zero.
1422	APInt Lower = APIntOps::umax(A: MinLHS, B: -MaxAbsRHS + 1);
1423	APInt Upper = APIntOps::umin(A: MaxLHS, B: MaxAbsRHS - 1) + 1;
1424	return ConstantRange(std::move(Lower), std::move(Upper));
1425	}
1426
1427	ConstantRange ConstantRange::binaryNot() const {
1428	return ConstantRange(APInt::getAllOnes(numBits: getBitWidth())).sub(Other: *this);
1429	}
1430
1431	ConstantRange ConstantRange::binaryAnd(const ConstantRange &Other) const {
1432	if (isEmptySet() || Other.isEmptySet())
1433	return getEmpty();
1434
1435	ConstantRange KnownBitsRange =
1436	fromKnownBits(Known: toKnownBits() & Other.toKnownBits(), IsSigned: false);
1437	ConstantRange UMinUMaxRange =
1438	getNonEmpty(Lower: APInt::getZero(numBits: getBitWidth()),
1439	Upper: APIntOps::umin(A: Other.getUnsignedMax(), B: getUnsignedMax()) + 1);
1440	return KnownBitsRange.intersectWith(CR: UMinUMaxRange);
1441	}
1442
1443	ConstantRange ConstantRange::binaryOr(const ConstantRange &Other) const {
1444	if (isEmptySet() || Other.isEmptySet())
1445	return getEmpty();
1446
1447	ConstantRange KnownBitsRange =
1448	fromKnownBits(Known: toKnownBits() | Other.toKnownBits(), IsSigned: false);
1449	// Upper wrapped range.
1450	ConstantRange UMaxUMinRange =
1451	getNonEmpty(Lower: APIntOps::umax(A: getUnsignedMin(), B: Other.getUnsignedMin()),
1452	Upper: APInt::getZero(numBits: getBitWidth()));
1453	return KnownBitsRange.intersectWith(CR: UMaxUMinRange);
1454	}
1455
1456	ConstantRange ConstantRange::binaryXor(const ConstantRange &Other) const {
1457	if (isEmptySet() || Other.isEmptySet())
1458	return getEmpty();
1459
1460	// Use APInt's implementation of XOR for single element ranges.
1461	if (isSingleElement() && Other.isSingleElement())
1462	return {*getSingleElement() ^ *Other.getSingleElement()};
1463
1464	// Special-case binary complement, since we can give a precise answer.
1465	if (Other.isSingleElement() && Other.getSingleElement()->isAllOnes())
1466	return binaryNot();
1467	if (isSingleElement() && getSingleElement()->isAllOnes())
1468	return Other.binaryNot();
1469
1470	KnownBits LHSKnown = toKnownBits();
1471	KnownBits RHSKnown = Other.toKnownBits();
1472	KnownBits Known = LHSKnown ^ RHSKnown;
1473	ConstantRange CR = fromKnownBits(Known, /*IsSigned*/ false);
1474	// Typically the following code doesn't improve the result if BW = 1.
1475	if (getBitWidth() == 1)
1476	return CR;
1477
1478	// If LHS is known to be the subset of RHS, treat LHS ^ RHS as RHS -nuw/nsw
1479	// LHS. If RHS is known to be the subset of LHS, treat LHS ^ RHS as LHS
1480	// -nuw/nsw RHS.
1481	if ((~LHSKnown.Zero).isSubsetOf(RHS: RHSKnown.One))
1482	CR = CR.intersectWith(CR: Other.sub(Other: *this), Type: PreferredRangeType::Unsigned);
1483	else if ((~RHSKnown.Zero).isSubsetOf(RHS: LHSKnown.One))
1484	CR = CR.intersectWith(CR: this->sub(Other), Type: PreferredRangeType::Unsigned);
1485	return CR;
1486	}
1487
1488	ConstantRange
1489	ConstantRange::shl(const ConstantRange &Other) const {
1490	if (isEmptySet() || Other.isEmptySet())
1491	return getEmpty();
1492
1493	APInt Min = getUnsignedMin();
1494	APInt Max = getUnsignedMax();
1495	if (const APInt *RHS = Other.getSingleElement()) {
1496	unsigned BW = getBitWidth();
1497	if (RHS->uge(RHS: BW))
1498	return getEmpty();
1499
1500	unsigned EqualLeadingBits = (Min ^ Max).countl_zero();
1501	if (RHS->ule(RHS: EqualLeadingBits))
1502	return getNonEmpty(Lower: Min << *RHS, Upper: (Max << *RHS) + 1);
1503
1504	return getNonEmpty(Lower: APInt::getZero(numBits: BW),
1505	Upper: APInt::getBitsSetFrom(numBits: BW, loBit: RHS->getZExtValue()) + 1);
1506	}
1507
1508	APInt OtherMax = Other.getUnsignedMax();
1509	if (isAllNegative() && OtherMax.ule(RHS: Min.countl_one())) {
1510	// For negative numbers, if the shift does not overflow in a signed sense,
1511	// a larger shift will make the number smaller.
1512	Max <<= Other.getUnsignedMin();
1513	Min <<= OtherMax;
1514	return ConstantRange::getNonEmpty(Lower: std::move(Min), Upper: std::move(Max) + 1);
1515	}
1516
1517	// There's overflow!
1518	if (OtherMax.ugt(RHS: Max.countl_zero()))
1519	return getFull();
1520
1521	// FIXME: implement the other tricky cases
1522
1523	Min <<= Other.getUnsignedMin();
1524	Max <<= OtherMax;
1525
1526	return ConstantRange::getNonEmpty(Lower: std::move(Min), Upper: std::move(Max) + 1);
1527	}
1528
1529	ConstantRange
1530	ConstantRange::lshr(const ConstantRange &Other) const {
1531	if (isEmptySet() || Other.isEmptySet())
1532	return getEmpty();
1533
1534	APInt max = getUnsignedMax().lshr(ShiftAmt: Other.getUnsignedMin()) + 1;
1535	APInt min = getUnsignedMin().lshr(ShiftAmt: Other.getUnsignedMax());
1536	return getNonEmpty(Lower: std::move(min), Upper: std::move(max));
1537	}
1538
1539	ConstantRange
1540	ConstantRange::ashr(const ConstantRange &Other) const {
1541	if (isEmptySet() || Other.isEmptySet())
1542	return getEmpty();
1543
1544	// May straddle zero, so handle both positive and negative cases.
1545	// 'PosMax' is the upper bound of the result of the ashr
1546	// operation, when Upper of the LHS of ashr is a non-negative.
1547	// number. Since ashr of a non-negative number will result in a
1548	// smaller number, the Upper value of LHS is shifted right with
1549	// the minimum value of 'Other' instead of the maximum value.
1550	APInt PosMax = getSignedMax().ashr(ShiftAmt: Other.getUnsignedMin()) + 1;
1551
1552	// 'PosMin' is the lower bound of the result of the ashr
1553	// operation, when Lower of the LHS is a non-negative number.
1554	// Since ashr of a non-negative number will result in a smaller
1555	// number, the Lower value of LHS is shifted right with the
1556	// maximum value of 'Other'.
1557	APInt PosMin = getSignedMin().ashr(ShiftAmt: Other.getUnsignedMax());
1558
1559	// 'NegMax' is the upper bound of the result of the ashr
1560	// operation, when Upper of the LHS of ashr is a negative number.
1561	// Since 'ashr' of a negative number will result in a bigger
1562	// number, the Upper value of LHS is shifted right with the
1563	// maximum value of 'Other'.
1564	APInt NegMax = getSignedMax().ashr(ShiftAmt: Other.getUnsignedMax()) + 1;
1565
1566	// 'NegMin' is the lower bound of the result of the ashr
1567	// operation, when Lower of the LHS of ashr is a negative number.
1568	// Since 'ashr' of a negative number will result in a bigger
1569	// number, the Lower value of LHS is shifted right with the
1570	// minimum value of 'Other'.
1571	APInt NegMin = getSignedMin().ashr(ShiftAmt: Other.getUnsignedMin());
1572
1573	APInt max, min;
1574	if (getSignedMin().isNonNegative()) {
1575	// Upper and Lower of LHS are non-negative.
1576	min = PosMin;
1577	max = PosMax;
1578	} else if (getSignedMax().isNegative()) {
1579	// Upper and Lower of LHS are negative.
1580	min = NegMin;
1581	max = NegMax;
1582	} else {
1583	// Upper is non-negative and Lower is negative.
1584	min = NegMin;
1585	max = PosMax;
1586	}
1587	return getNonEmpty(Lower: std::move(min), Upper: std::move(max));
1588	}
1589
1590	ConstantRange ConstantRange::uadd_sat(const ConstantRange &Other) const {
1591	if (isEmptySet() || Other.isEmptySet())
1592	return getEmpty();
1593
1594	APInt NewL = getUnsignedMin().uadd_sat(RHS: Other.getUnsignedMin());
1595	APInt NewU = getUnsignedMax().uadd_sat(RHS: Other.getUnsignedMax()) + 1;
1596	return getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1597	}
1598
1599	ConstantRange ConstantRange::sadd_sat(const ConstantRange &Other) const {
1600	if (isEmptySet() || Other.isEmptySet())
1601	return getEmpty();
1602
1603	APInt NewL = getSignedMin().sadd_sat(RHS: Other.getSignedMin());
1604	APInt NewU = getSignedMax().sadd_sat(RHS: Other.getSignedMax()) + 1;
1605	return getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1606	}
1607
1608	ConstantRange ConstantRange::usub_sat(const ConstantRange &Other) const {
1609	if (isEmptySet() || Other.isEmptySet())
1610	return getEmpty();
1611
1612	APInt NewL = getUnsignedMin().usub_sat(RHS: Other.getUnsignedMax());
1613	APInt NewU = getUnsignedMax().usub_sat(RHS: Other.getUnsignedMin()) + 1;
1614	return getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1615	}
1616
1617	ConstantRange ConstantRange::ssub_sat(const ConstantRange &Other) const {
1618	if (isEmptySet() || Other.isEmptySet())
1619	return getEmpty();
1620
1621	APInt NewL = getSignedMin().ssub_sat(RHS: Other.getSignedMax());
1622	APInt NewU = getSignedMax().ssub_sat(RHS: Other.getSignedMin()) + 1;
1623	return getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1624	}
1625
1626	ConstantRange ConstantRange::umul_sat(const ConstantRange &Other) const {
1627	if (isEmptySet() || Other.isEmptySet())
1628	return getEmpty();
1629
1630	APInt NewL = getUnsignedMin().umul_sat(RHS: Other.getUnsignedMin());
1631	APInt NewU = getUnsignedMax().umul_sat(RHS: Other.getUnsignedMax()) + 1;
1632	return getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1633	}
1634
1635	ConstantRange ConstantRange::smul_sat(const ConstantRange &Other) const {
1636	if (isEmptySet() || Other.isEmptySet())
1637	return getEmpty();
1638
1639	// Because we could be dealing with negative numbers here, the lower bound is
1640	// the smallest of the cartesian product of the lower and upper ranges;
1641	// for example:
1642	// [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
1643	// Similarly for the upper bound, swapping min for max.
1644
1645	APInt Min = getSignedMin();
1646	APInt Max = getSignedMax();
1647	APInt OtherMin = Other.getSignedMin();
1648	APInt OtherMax = Other.getSignedMax();
1649
1650	auto L = {Min.smul_sat(RHS: OtherMin), Min.smul_sat(RHS: OtherMax),
1651	Max.smul_sat(RHS: OtherMin), Max.smul_sat(RHS: OtherMax)};
1652	auto Compare = [](const APInt &A, const APInt &B) { return A.slt(RHS: B); };
1653	return getNonEmpty(Lower: std::min(l: L, comp: Compare), Upper: std::max(l: L, comp: Compare) + 1);
1654	}
1655
1656	ConstantRange ConstantRange::ushl_sat(const ConstantRange &Other) const {
1657	if (isEmptySet() || Other.isEmptySet())
1658	return getEmpty();
1659
1660	APInt NewL = getUnsignedMin().ushl_sat(RHS: Other.getUnsignedMin());
1661	APInt NewU = getUnsignedMax().ushl_sat(RHS: Other.getUnsignedMax()) + 1;
1662	return getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1663	}
1664
1665	ConstantRange ConstantRange::sshl_sat(const ConstantRange &Other) const {
1666	if (isEmptySet() || Other.isEmptySet())
1667	return getEmpty();
1668
1669	APInt Min = getSignedMin(), Max = getSignedMax();
1670	APInt ShAmtMin = Other.getUnsignedMin(), ShAmtMax = Other.getUnsignedMax();
1671	APInt NewL = Min.sshl_sat(RHS: Min.isNonNegative() ? ShAmtMin : ShAmtMax);
1672	APInt NewU = Max.sshl_sat(RHS: Max.isNegative() ? ShAmtMin : ShAmtMax) + 1;
1673	return getNonEmpty(Lower: std::move(NewL), Upper: std::move(NewU));
1674	}
1675
1676	ConstantRange ConstantRange::inverse() const {
1677	if (isFullSet())
1678	return getEmpty();
1679	if (isEmptySet())
1680	return getFull();
1681	return ConstantRange(Upper, Lower);
1682	}
1683
1684	ConstantRange ConstantRange::abs(bool IntMinIsPoison) const {
1685	if (isEmptySet())
1686	return getEmpty();
1687
1688	if (isSignWrappedSet()) {
1689	APInt Lo;
1690	// Check whether the range crosses zero.
1691	if (Upper.isStrictlyPositive() || !Lower.isStrictlyPositive())
1692	Lo = APInt::getZero(numBits: getBitWidth());
1693	else
1694	Lo = APIntOps::umin(A: Lower, B: -Upper + 1);
1695
1696	// If SignedMin is not poison, then it is included in the result range.
1697	if (IntMinIsPoison)
1698	return ConstantRange(Lo, APInt::getSignedMinValue(numBits: getBitWidth()));
1699	else
1700	return ConstantRange(Lo, APInt::getSignedMinValue(numBits: getBitWidth()) + 1);
1701	}
1702
1703	APInt SMin = getSignedMin(), SMax = getSignedMax();
1704
1705	// Skip SignedMin if it is poison.
1706	if (IntMinIsPoison && SMin.isMinSignedValue()) {
1707	// The range may become empty if it *only* contains SignedMin.
1708	if (SMax.isMinSignedValue())
1709	return getEmpty();
1710	++SMin;
1711	}
1712
1713	// All non-negative.
1714	if (SMin.isNonNegative())
1715	return ConstantRange(SMin, SMax + 1);
1716
1717	// All negative.
1718	if (SMax.isNegative())
1719	return ConstantRange(-SMax, -SMin + 1);
1720
1721	// Range crosses zero.
1722	return ConstantRange::getNonEmpty(Lower: APInt::getZero(numBits: getBitWidth()),
1723	Upper: APIntOps::umax(A: -SMin, B: SMax) + 1);
1724	}
1725
1726	ConstantRange ConstantRange::ctlz(bool ZeroIsPoison) const {
1727	if (isEmptySet())
1728	return getEmpty();
1729
1730	APInt Zero = APInt::getZero(numBits: getBitWidth());
1731	if (ZeroIsPoison && contains(V: Zero)) {
1732	// ZeroIsPoison is set, and zero is contained. We discern three cases, in
1733	// which a zero can appear:
1734	// 1) Lower is zero, handling cases of kind [0, 1), [0, 2), etc.
1735	// 2) Upper is zero, wrapped set, handling cases of kind [3, 0], etc.
1736	// 3) Zero contained in a wrapped set, e.g., [3, 2), [3, 1), etc.
1737
1738	if (getLower().isZero()) {
1739	if ((getUpper() - 1).isZero()) {
1740	// We have in input interval of kind [0, 1). In this case we cannot
1741	// really help but return empty-set.
1742	return getEmpty();
1743	}
1744
1745	// Compute the resulting range by excluding zero from Lower.
1746	return ConstantRange(
1747	APInt(getBitWidth(), (getUpper() - 1).countl_zero()),
1748	APInt(getBitWidth(), (getLower() + 1).countl_zero() + 1));
1749	} else if ((getUpper() - 1).isZero()) {
1750	// Compute the resulting range by excluding zero from Upper.
1751	return ConstantRange(Zero,
1752	APInt(getBitWidth(), getLower().countl_zero() + 1));
1753	} else {
1754	return ConstantRange(Zero, APInt(getBitWidth(), getBitWidth()));
1755	}
1756	}
1757
1758	// Zero is either safe or not in the range. The output range is composed by
1759	// the result of countLeadingZero of the two extremes.
1760	return getNonEmpty(Lower: APInt(getBitWidth(), getUnsignedMax().countl_zero()),
1761	Upper: APInt(getBitWidth(), getUnsignedMin().countl_zero() + 1));
1762	}
1763
1764	static ConstantRange getUnsignedCountTrailingZerosRange(const APInt &Lower,
1765	const APInt &Upper) {
1766	assert(!ConstantRange(Lower, Upper).isWrappedSet() &&
1767	"Unexpected wrapped set.");
1768	assert(Lower != Upper && "Unexpected empty set.");
1769	unsigned BitWidth = Lower.getBitWidth();
1770	if (Lower + 1 == Upper)
1771	return ConstantRange(APInt(BitWidth, Lower.countr_zero()));
1772	if (Lower.isZero())
1773	return ConstantRange(APInt::getZero(numBits: BitWidth),
1774	APInt(BitWidth, BitWidth + 1));
1775
1776	// Calculate longest common prefix.
1777	unsigned LCPLength = (Lower ^ (Upper - 1)).countl_zero();
1778	// If Lower is {LCP, 000...}, the maximum is Lower.countr_zero().
1779	// Otherwise, the maximum is BitWidth - LCPLength - 1 ({LCP, 100...}).
1780	return ConstantRange(
1781	APInt::getZero(numBits: BitWidth),
1782	APInt(BitWidth,
1783	std::max(a: BitWidth - LCPLength - 1, b: Lower.countr_zero()) + 1));
1784	}
1785
1786	ConstantRange ConstantRange::cttz(bool ZeroIsPoison) const {
1787	if (isEmptySet())
1788	return getEmpty();
1789
1790	unsigned BitWidth = getBitWidth();
1791	APInt Zero = APInt::getZero(numBits: BitWidth);
1792	if (ZeroIsPoison && contains(V: Zero)) {
1793	// ZeroIsPoison is set, and zero is contained. We discern three cases, in
1794	// which a zero can appear:
1795	// 1) Lower is zero, handling cases of kind [0, 1), [0, 2), etc.
1796	// 2) Upper is zero, wrapped set, handling cases of kind [3, 0], etc.
1797	// 3) Zero contained in a wrapped set, e.g., [3, 2), [3, 1), etc.
1798
1799	if (Lower.isZero()) {
1800	if (Upper == 1) {
1801	// We have in input interval of kind [0, 1). In this case we cannot
1802	// really help but return empty-set.
1803	return getEmpty();
1804	}
1805
1806	// Compute the resulting range by excluding zero from Lower.
1807	return getUnsignedCountTrailingZerosRange(Lower: APInt(BitWidth, 1), Upper);
1808	} else if (Upper == 1) {
1809	// Compute the resulting range by excluding zero from Upper.
1810	return getUnsignedCountTrailingZerosRange(Lower, Upper: Zero);
1811	} else {
1812	ConstantRange CR1 = getUnsignedCountTrailingZerosRange(Lower, Upper: Zero);
1813	ConstantRange CR2 =
1814	getUnsignedCountTrailingZerosRange(Lower: APInt(BitWidth, 1), Upper);
1815	return CR1.unionWith(CR: CR2);
1816	}
1817	}
1818
1819	if (isFullSet())
1820	return getNonEmpty(Lower: Zero, Upper: APInt(BitWidth, BitWidth + 1));
1821	if (!isWrappedSet())
1822	return getUnsignedCountTrailingZerosRange(Lower, Upper);
1823	// The range is wrapped. We decompose it into two ranges, [0, Upper) and
1824	// [Lower, 0).
1825	// Handle [Lower, 0)
1826	ConstantRange CR1 = getUnsignedCountTrailingZerosRange(Lower, Upper: Zero);
1827	// Handle [0, Upper)
1828	ConstantRange CR2 = getUnsignedCountTrailingZerosRange(Lower: Zero, Upper);
1829	return CR1.unionWith(CR: CR2);
1830	}
1831
1832	static ConstantRange getUnsignedPopCountRange(const APInt &Lower,
1833	const APInt &Upper) {
1834	assert(!ConstantRange(Lower, Upper).isWrappedSet() &&
1835	"Unexpected wrapped set.");
1836	assert(Lower != Upper && "Unexpected empty set.");
1837	unsigned BitWidth = Lower.getBitWidth();
1838	if (Lower + 1 == Upper)
1839	return ConstantRange(APInt(BitWidth, Lower.popcount()));
1840
1841	APInt Max = Upper - 1;
1842	// Calculate longest common prefix.
1843	unsigned LCPLength = (Lower ^ Max).countl_zero();
1844	unsigned LCPPopCount = Lower.getHiBits(numBits: LCPLength).popcount();
1845	// If Lower is {LCP, 000...}, the minimum is the popcount of LCP.
1846	// Otherwise, the minimum is the popcount of LCP + 1.
1847	unsigned MinBits =
1848	LCPPopCount + (Lower.countr_zero() < BitWidth - LCPLength ? 1 : 0);
1849	// If Max is {LCP, 111...}, the maximum is the popcount of LCP + (BitWidth -
1850	// length of LCP).
1851	// Otherwise, the minimum is the popcount of LCP + (BitWidth -
1852	// length of LCP - 1).
1853	unsigned MaxBits = LCPPopCount + (BitWidth - LCPLength) -
1854	(Max.countr_one() < BitWidth - LCPLength ? 1 : 0);
1855	return ConstantRange(APInt(BitWidth, MinBits), APInt(BitWidth, MaxBits + 1));
1856	}
1857
1858	ConstantRange ConstantRange::ctpop() const {
1859	if (isEmptySet())
1860	return getEmpty();
1861
1862	unsigned BitWidth = getBitWidth();
1863	APInt Zero = APInt::getZero(numBits: BitWidth);
1864	if (isFullSet())
1865	return getNonEmpty(Lower: Zero, Upper: APInt(BitWidth, BitWidth + 1));
1866	if (!isWrappedSet())
1867	return getUnsignedPopCountRange(Lower, Upper);
1868	// The range is wrapped. We decompose it into two ranges, [0, Upper) and
1869	// [Lower, 0).
1870	// Handle [Lower, 0) == [Lower, Max]
1871	ConstantRange CR1 = ConstantRange(APInt(BitWidth, Lower.countl_one()),
1872	APInt(BitWidth, BitWidth + 1));
1873	// Handle [0, Upper)
1874	ConstantRange CR2 = getUnsignedPopCountRange(Lower: Zero, Upper);
1875	return CR1.unionWith(CR: CR2);
1876	}
1877
1878	ConstantRange::OverflowResult ConstantRange::unsignedAddMayOverflow(
1879	const ConstantRange &Other) const {
1880	if (isEmptySet() || Other.isEmptySet())
1881	return OverflowResult::MayOverflow;
1882
1883	APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1884	APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1885
1886	// a u+ b overflows high iff a u> ~b.
1887	if (Min.ugt(RHS: ~OtherMin))
1888	return OverflowResult::AlwaysOverflowsHigh;
1889	if (Max.ugt(RHS: ~OtherMax))
1890	return OverflowResult::MayOverflow;
1891	return OverflowResult::NeverOverflows;
1892	}
1893
1894	ConstantRange::OverflowResult ConstantRange::signedAddMayOverflow(
1895	const ConstantRange &Other) const {
1896	if (isEmptySet() || Other.isEmptySet())
1897	return OverflowResult::MayOverflow;
1898
1899	APInt Min = getSignedMin(), Max = getSignedMax();
1900	APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
1901
1902	APInt SignedMin = APInt::getSignedMinValue(numBits: getBitWidth());
1903	APInt SignedMax = APInt::getSignedMaxValue(numBits: getBitWidth());
1904
1905	// a s+ b overflows high iff a s>=0 && b s>= 0 && a s> smax - b.
1906	// a s+ b overflows low iff a s< 0 && b s< 0 && a s< smin - b.
1907	if (Min.isNonNegative() && OtherMin.isNonNegative() &&
1908	Min.sgt(RHS: SignedMax - OtherMin))
1909	return OverflowResult::AlwaysOverflowsHigh;
1910	if (Max.isNegative() && OtherMax.isNegative() &&
1911	Max.slt(RHS: SignedMin - OtherMax))
1912	return OverflowResult::AlwaysOverflowsLow;
1913
1914	if (Max.isNonNegative() && OtherMax.isNonNegative() &&
1915	Max.sgt(RHS: SignedMax - OtherMax))
1916	return OverflowResult::MayOverflow;
1917	if (Min.isNegative() && OtherMin.isNegative() &&
1918	Min.slt(RHS: SignedMin - OtherMin))
1919	return OverflowResult::MayOverflow;
1920
1921	return OverflowResult::NeverOverflows;
1922	}
1923
1924	ConstantRange::OverflowResult ConstantRange::unsignedSubMayOverflow(
1925	const ConstantRange &Other) const {
1926	if (isEmptySet() || Other.isEmptySet())
1927	return OverflowResult::MayOverflow;
1928
1929	APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1930	APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1931
1932	// a u- b overflows low iff a u< b.
1933	if (Max.ult(RHS: OtherMin))
1934	return OverflowResult::AlwaysOverflowsLow;
1935	if (Min.ult(RHS: OtherMax))
1936	return OverflowResult::MayOverflow;
1937	return OverflowResult::NeverOverflows;
1938	}
1939
1940	ConstantRange::OverflowResult ConstantRange::signedSubMayOverflow(
1941	const ConstantRange &Other) const {
1942	if (isEmptySet() || Other.isEmptySet())
1943	return OverflowResult::MayOverflow;
1944
1945	APInt Min = getSignedMin(), Max = getSignedMax();
1946	APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
1947
1948	APInt SignedMin = APInt::getSignedMinValue(numBits: getBitWidth());
1949	APInt SignedMax = APInt::getSignedMaxValue(numBits: getBitWidth());
1950
1951	// a s- b overflows high iff a s>=0 && b s< 0 && a s> smax + b.
1952	// a s- b overflows low iff a s< 0 && b s>= 0 && a s< smin + b.
1953	if (Min.isNonNegative() && OtherMax.isNegative() &&
1954	Min.sgt(RHS: SignedMax + OtherMax))
1955	return OverflowResult::AlwaysOverflowsHigh;
1956	if (Max.isNegative() && OtherMin.isNonNegative() &&
1957	Max.slt(RHS: SignedMin + OtherMin))
1958	return OverflowResult::AlwaysOverflowsLow;
1959
1960	if (Max.isNonNegative() && OtherMin.isNegative() &&
1961	Max.sgt(RHS: SignedMax + OtherMin))
1962	return OverflowResult::MayOverflow;
1963	if (Min.isNegative() && OtherMax.isNonNegative() &&
1964	Min.slt(RHS: SignedMin + OtherMax))
1965	return OverflowResult::MayOverflow;
1966
1967	return OverflowResult::NeverOverflows;
1968	}
1969
1970	ConstantRange::OverflowResult ConstantRange::unsignedMulMayOverflow(
1971	const ConstantRange &Other) const {
1972	if (isEmptySet() || Other.isEmptySet())
1973	return OverflowResult::MayOverflow;
1974
1975	APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1976	APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1977	bool Overflow;
1978
1979	(void) Min.umul_ov(RHS: OtherMin, Overflow);
1980	if (Overflow)
1981	return OverflowResult::AlwaysOverflowsHigh;
1982
1983	(void) Max.umul_ov(RHS: OtherMax, Overflow);
1984	if (Overflow)
1985	return OverflowResult::MayOverflow;
1986
1987	return OverflowResult::NeverOverflows;
1988	}
1989
1990	void ConstantRange::print(raw_ostream &OS) const {
1991	if (isFullSet())
1992	OS << "full-set";
1993	else if (isEmptySet())
1994	OS << "empty-set";
1995	else
1996	OS << "[" << Lower << "," << Upper << ")";
1997	}
1998
1999	#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2000	LLVM_DUMP_METHOD void ConstantRange::dump() const {
2001	print(OS&: dbgs());
2002	}
2003	#endif
2004
2005	ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) {
2006	const unsigned NumRanges = Ranges.getNumOperands() / 2;
2007	assert(NumRanges >= 1 && "Must have at least one range!");
2008	assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
2009
2010	auto *FirstLow = mdconst::extract<ConstantInt>(MD: Ranges.getOperand(I: 0));
2011	auto *FirstHigh = mdconst::extract<ConstantInt>(MD: Ranges.getOperand(I: 1));
2012
2013	ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
2014
2015	for (unsigned i = 1; i < NumRanges; ++i) {
2016	auto *Low = mdconst::extract<ConstantInt>(MD: Ranges.getOperand(I: 2 * i + 0));
2017	auto *High = mdconst::extract<ConstantInt>(MD: Ranges.getOperand(I: 2 * i + 1));
2018
2019	// Note: unionWith will potentially create a range that contains values not
2020	// contained in any of the original N ranges.
2021	CR = CR.unionWith(CR: ConstantRange(Low->getValue(), High->getValue()));
2022	}
2023
2024	return CR;
2025	}
2026