ConstantRange.cpp revision 198381e542320265e1c5fed18e938db3563a45bf
1645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner//===-- ConstantRange.cpp - ConstantRange implementation ------------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// 10645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// Represent a range of possible values that may occur when the program is run 11645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// for an integral value. This keeps track of a lower and upper bound for the 12645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// constant, which MAY wrap around the end of the numeric range. To do this, it 13645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// keeps track of a [lower, upper) bound, which specifies an interval just like 14645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// STL iterators. When used with boolean values, the following are important 15645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// ranges (other integral ranges use min/max values for special range values): 16645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// 17645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// [F, F) = {} = Empty set 18645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// [T, F) = {T} 19645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// [F, T) = {F} 20645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// [T, T) = {F, T} = Full set 21645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// 22645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner//===----------------------------------------------------------------------===// 23645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 24634bab148cacc8cc8647172056c26c8bc3f60a65Owen Anderson#include "llvm/Constants.h" 25645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner#include "llvm/Support/ConstantRange.h" 267fd5fb4b4755c3df86da5a0ebedf0d328fafbc81David Greene#include "llvm/Support/Debug.h" 27944fac71e082cc2664cc71b4d3f6c72bab7143fbChris Lattner#include "llvm/Support/raw_ostream.h" 28bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky#include "llvm/Instructions.h" 292cdd21c2e4d855500dfb53f77aa74da53ccf9de6Chris Lattnerusing namespace llvm; 30d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 31645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// Initialize a full (the default) or empty set for the specified type. 32645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 3338b06447615440f935008a2141bd0a1fe078d437Dan GohmanConstantRange::ConstantRange(uint32_t BitWidth, bool Full) { 34645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner if (Full) 35663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer Lower = Upper = APInt::getMaxValue(BitWidth); 36645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner else 37663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer Lower = Upper = APInt::getMinValue(BitWidth); 38645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 39645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 40fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// Initialize a range to hold the single specified value. 41fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// 427f9ef4bb514d5a28637789d8f397dadd4344dc1bNick LewyckyConstantRange::ConstantRange(const APInt &V) : Lower(V), Upper(V + 1) {} 43645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 4438b06447615440f935008a2141bd0a1fe078d437Dan GohmanConstantRange::ConstantRange(const APInt &L, const APInt &U) : 4538b06447615440f935008a2141bd0a1fe078d437Dan Gohman Lower(L), Upper(U) { 4638b06447615440f935008a2141bd0a1fe078d437Dan Gohman assert(L.getBitWidth() == U.getBitWidth() && 4738b06447615440f935008a2141bd0a1fe078d437Dan Gohman "ConstantRange with unequal bit widths"); 48c125c00e68138b8ae7861b589277a491ee217893Zhou Sheng assert((L != U || (L.isMaxValue() || L.isMinValue())) && 49663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer "Lower == Upper, but they aren't min or max value!"); 50663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer} 51663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer 52bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick LewyckyConstantRange ConstantRange::makeICmpRegion(unsigned Pred, 53bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky const ConstantRange &CR) { 54bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky uint32_t W = CR.getBitWidth(); 55bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky switch (Pred) { 56bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky default: assert(!"Invalid ICmp predicate to makeICmpRegion()"); 57bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky case ICmpInst::ICMP_EQ: 58f067a233562d3cfeb29d0092d1069bb8d25cad31Nick Lewycky return CR; 59bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky case ICmpInst::ICMP_NE: 60bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (CR.isSingleElement()) 61bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(CR.getUpper(), CR.getLower()); 62bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(W); 63bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky case ICmpInst::ICMP_ULT: 64bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(APInt::getMinValue(W), CR.getUnsignedMax()); 65bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky case ICmpInst::ICMP_SLT: 66bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(APInt::getSignedMinValue(W), CR.getSignedMax()); 67bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky case ICmpInst::ICMP_ULE: { 68bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky APInt UMax(CR.getUnsignedMax()); 69bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (UMax.isMaxValue()) 70bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(W); 71bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(APInt::getMinValue(W), UMax + 1); 72bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 73bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky case ICmpInst::ICMP_SLE: { 74bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky APInt SMax(CR.getSignedMax()); 75bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (SMax.isMaxSignedValue() || (SMax+1).isMaxSignedValue()) 76bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(W); 77bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(APInt::getSignedMinValue(W), SMax + 1); 78bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 79bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky case ICmpInst::ICMP_UGT: 80bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(CR.getUnsignedMin() + 1, APInt::getNullValue(W)); 81bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky case ICmpInst::ICMP_SGT: 82bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(CR.getSignedMin() + 1, 83bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky APInt::getSignedMinValue(W)); 84bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky case ICmpInst::ICMP_UGE: { 85bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky APInt UMin(CR.getUnsignedMin()); 86bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (UMin.isMinValue()) 87bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(W); 88bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(UMin, APInt::getNullValue(W)); 89bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 90bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky case ICmpInst::ICMP_SGE: { 91bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky APInt SMin(CR.getSignedMin()); 92bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (SMin.isMinSignedValue()) 93bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(W); 94bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(SMin, APInt::getSignedMinValue(W)); 95bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 96bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 97bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky} 98bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 99645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// isFullSet - Return true if this set contains all of the elements possible 100645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// for this data-type 101645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattnerbool ConstantRange::isFullSet() const { 102c125c00e68138b8ae7861b589277a491ee217893Zhou Sheng return Lower == Upper && Lower.isMaxValue(); 103645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 104fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 105645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// isEmptySet - Return true if this set contains no members. 106645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 107645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattnerbool ConstantRange::isEmptySet() const { 108c125c00e68138b8ae7861b589277a491ee217893Zhou Sheng return Lower == Upper && Lower.isMinValue(); 109645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 110645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 111645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// isWrappedSet - Return true if this set wraps around the top of the range, 112645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// for example: [100, 8) 113645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 114a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencerbool ConstantRange::isWrappedSet() const { 115663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return Lower.ugt(Upper); 116645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 117645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 11832cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky/// isSignWrappedSet - Return true if this set wraps around the INT_MIN of 11932cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky/// its bitwidth, for example: i8 [120, 140). 12032cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky/// 12132cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewyckybool ConstantRange::isSignWrappedSet() const { 12232cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky return contains(APInt::getSignedMaxValue(getBitWidth())) && 12332cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky contains(APInt::getSignedMinValue(getBitWidth())); 12432cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky} 12532cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky 126645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// getSetSize - Return the number of elements in this set. 127645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 128663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid SpencerAPInt ConstantRange::getSetSize() const { 129663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer if (isEmptySet()) 130bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer return APInt(getBitWidth(), 0); 131bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer if (getBitWidth() == 1) { 132645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner if (Lower != Upper) // One of T or F in the set... 133bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer return APInt(2, 1); 134bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer return APInt(2, 2); // Must be full set... 135645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner } 136fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 137645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // Simply subtract the bounds... 138663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return Upper - Lower; 139645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 140645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 1413400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getUnsignedMax - Return the largest unsigned value contained in the 1423400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 1433400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1443400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getUnsignedMax() const { 1453400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (isFullSet() || isWrappedSet()) 1463400e6af6b10acea219c02ac262637220f84218fNick Lewycky return APInt::getMaxValue(getBitWidth()); 1473400e6af6b10acea219c02ac262637220f84218fNick Lewycky else 1483400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getUpper() - 1; 1493400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 1503400e6af6b10acea219c02ac262637220f84218fNick Lewycky 1513400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getUnsignedMin - Return the smallest unsigned value contained in the 1523400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 1533400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1543400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getUnsignedMin() const { 1553400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (isFullSet() || (isWrappedSet() && getUpper() != 0)) 1563400e6af6b10acea219c02ac262637220f84218fNick Lewycky return APInt::getMinValue(getBitWidth()); 1573400e6af6b10acea219c02ac262637220f84218fNick Lewycky else 1583400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getLower(); 1593400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 1603400e6af6b10acea219c02ac262637220f84218fNick Lewycky 1613400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getSignedMax - Return the largest signed value contained in the 1623400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 1633400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1643400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getSignedMax() const { 165daacf22537e0d140c379a39a11a83d3321395d4dZhou Sheng APInt SignedMax(APInt::getSignedMaxValue(getBitWidth())); 1663400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (!isWrappedSet()) { 167ae5eb7accf65ee94e22b3d235d466d71268f1e83Nick Lewycky if (getLower().sle(getUpper() - 1)) 1683400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getUpper() - 1; 1693400e6af6b10acea219c02ac262637220f84218fNick Lewycky else 1703400e6af6b10acea219c02ac262637220f84218fNick Lewycky return SignedMax; 1713400e6af6b10acea219c02ac262637220f84218fNick Lewycky } else { 172780905e9f9f29419de56b47253f6db84bc659f42Nick Lewycky if (getLower().isNegative() == getUpper().isNegative()) 173780905e9f9f29419de56b47253f6db84bc659f42Nick Lewycky return SignedMax; 174780905e9f9f29419de56b47253f6db84bc659f42Nick Lewycky else 1753400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getUpper() - 1; 1763400e6af6b10acea219c02ac262637220f84218fNick Lewycky } 1773400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 1783400e6af6b10acea219c02ac262637220f84218fNick Lewycky 1793400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getSignedMin - Return the smallest signed value contained in the 1803400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 1813400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1823400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getSignedMin() const { 183daacf22537e0d140c379a39a11a83d3321395d4dZhou Sheng APInt SignedMin(APInt::getSignedMinValue(getBitWidth())); 1843400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (!isWrappedSet()) { 185ae5eb7accf65ee94e22b3d235d466d71268f1e83Nick Lewycky if (getLower().sle(getUpper() - 1)) 1863400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getLower(); 1873400e6af6b10acea219c02ac262637220f84218fNick Lewycky else 1883400e6af6b10acea219c02ac262637220f84218fNick Lewycky return SignedMin; 1893400e6af6b10acea219c02ac262637220f84218fNick Lewycky } else { 1903400e6af6b10acea219c02ac262637220f84218fNick Lewycky if ((getUpper() - 1).slt(getLower())) { 1913400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (getUpper() != SignedMin) 1923400e6af6b10acea219c02ac262637220f84218fNick Lewycky return SignedMin; 1933400e6af6b10acea219c02ac262637220f84218fNick Lewycky else 1943400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getLower(); 1953400e6af6b10acea219c02ac262637220f84218fNick Lewycky } else { 1963400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getLower(); 1973400e6af6b10acea219c02ac262637220f84218fNick Lewycky } 1983400e6af6b10acea219c02ac262637220f84218fNick Lewycky } 1993400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 2003400e6af6b10acea219c02ac262637220f84218fNick Lewycky 201fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// contains - Return true if the specified value is in the set. 202fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// 203a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencerbool ConstantRange::contains(const APInt &V) const { 204a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer if (Lower == Upper) 205a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer return isFullSet(); 206fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 207a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer if (!isWrappedSet()) 208a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer return Lower.ule(V) && V.ult(Upper); 209663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer else 210663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return Lower.ule(V) || V.ult(Upper); 211fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 212645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 213bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky/// contains - Return true if the argument is a subset of this range. 2147f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky/// Two equal sets contain each other. The empty set contained by all other 2157f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky/// sets. 216bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky/// 217bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewyckybool ConstantRange::contains(const ConstantRange &Other) const { 2187f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isFullSet() || Other.isEmptySet()) return true; 2197f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isEmptySet() || Other.isFullSet()) return false; 220bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 221bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (!isWrappedSet()) { 222bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (Other.isWrappedSet()) 223bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return false; 224bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 225bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper); 226bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 227bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 228bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (!Other.isWrappedSet()) 229bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return Other.getUpper().ule(Upper) || 230bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky Lower.ule(Other.getLower()); 231bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 232bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower()); 233bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky} 234bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 235fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// subtract - Subtract the specified constant from the endpoints of this 236fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// constant range. 237581b0d453a63f7f657248f80317976995262be11Reid SpencerConstantRange ConstantRange::subtract(const APInt &Val) const { 238bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width"); 239fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner // If the set is empty or full, don't modify the endpoints. 240663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer if (Lower == Upper) 241663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return *this; 242663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return ConstantRange(Lower - Val, Upper - Val); 243fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 244fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 2453e051647c079fe29db049646b39611fc0135327dNick Lewycky/// intersectWith - Return the range that results from the intersection of this 2463a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky/// range with another range. The resultant range is guaranteed to include all 2473a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky/// elements contained in both input ranges, and to have the smallest possible 2483a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky/// set size that does so. Because there may be two intersections with the 2493a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky/// same set size, A.intersectWith(B) might not be equal to B.intersectWith(A). 250a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid SpencerConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const { 251bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer assert(getBitWidth() == CR.getBitWidth() && 252bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer "ConstantRange types don't agree!"); 253377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 254377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky // Handle common cases. 255377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if ( isEmptySet() || CR.isFullSet()) return *this; 256377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.isEmptySet() || isFullSet()) return CR; 257377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 258377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (!isWrappedSet() && CR.isWrappedSet()) 2593a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky return CR.intersectWith(*this); 260377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 261377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (!isWrappedSet() && !CR.isWrappedSet()) { 262377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (Lower.ult(CR.Lower)) { 263377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (Upper.ule(CR.Lower)) 264377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(getBitWidth(), false); 265377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 266377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (Upper.ult(CR.Upper)) 267377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(CR.Lower, Upper); 268377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 269377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 270377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } else { 271377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (Upper.ult(CR.Upper)) 272377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return *this; 273377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 274377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (Lower.ult(CR.Upper)) 275377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(Lower, CR.Upper); 276377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 277377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(getBitWidth(), false); 278377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 279377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 280377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 281377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (isWrappedSet() && !CR.isWrappedSet()) { 282377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Lower.ult(Upper)) { 283377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Upper.ult(Upper)) 284377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 285377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 286377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Upper.ult(Lower)) 287377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(CR.Lower, Upper); 288377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 289377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (getSetSize().ult(CR.getSetSize())) 290377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return *this; 291377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky else 292377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 293377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } else if (CR.Lower.ult(Lower)) { 294377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Upper.ule(Lower)) 295377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(getBitWidth(), false); 296377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 297377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(Lower, CR.Upper); 298377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 299377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 300377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 301377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 302377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Upper.ult(Upper)) { 303377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Lower.ult(Upper)) { 304377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (getSetSize().ult(CR.getSetSize())) 305377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return *this; 306377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky else 307377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 308377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 309377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 310377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Lower.ult(Lower)) 311377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(Lower, CR.Upper); 312377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 313377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 314377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } else if (CR.Upper.ult(Lower)) { 315377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Lower.ult(Lower)) 316377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return *this; 317377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 318377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(CR.Lower, Upper); 319377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 320377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (getSetSize().ult(CR.getSetSize())) 321377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return *this; 322377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky else 323377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 324377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky} 325377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 326377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 3273e051647c079fe29db049646b39611fc0135327dNick Lewycky/// unionWith - Return the range that results from the union of this range with 328645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// another range. The resultant range is guaranteed to include the elements of 3299babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky/// both sets, but may contain more. For example, [3, 9) union [12,15) is 3309babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky/// [3, 15), which includes 9, 10, and 11, which were not included in either 3319babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky/// set before. 332645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 333a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid SpencerConstantRange ConstantRange::unionWith(const ConstantRange &CR) const { 334bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer assert(getBitWidth() == CR.getBitWidth() && 335bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer "ConstantRange types don't agree!"); 336645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 337c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky if ( isFullSet() || CR.isEmptySet()) return *this; 338c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky if (CR.isFullSet() || isEmptySet()) return CR; 339645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 3409babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this); 3419babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3429babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (!isWrappedSet() && !CR.isWrappedSet()) { 3437e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) { 3447e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // If the two ranges are disjoint, find the smaller gap and bridge it. 3457e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; 3467e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (d1.ult(d2)) 3477e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(Lower, CR.Upper); 3487e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky else 3497e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(CR.Lower, Upper); 3507e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky } 3517e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky 3527e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky APInt L = Lower, U = Upper; 3539babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (CR.Lower.ult(L)) 3549babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky L = CR.Lower; 3557e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if ((CR.Upper - 1).ugt(U - 1)) 3569babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky U = CR.Upper; 3577e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky 3587e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (L == 0 && U == 0) 3597e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(getBitWidth()); 3607e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky 3617e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(L, U); 3629babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 3639babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3647e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (!CR.isWrappedSet()) { 3657e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ------U L----- and ------U L----- : this 3667e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L--U L--U : CR 3677e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower)) 3689babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky return *this; 3699babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3707e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ------U L----- : this 3717e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L---------U : CR 3727e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) 3739babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky return ConstantRange(getBitWidth()); 3749babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3757e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ----U L---- : this 3767e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L---U : CR 3777e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // <d1> <d2> 3787e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) { 3799babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; 3807e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (d1.ult(d2)) 3817e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(Lower, CR.Upper); 3827e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky else 3837e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(CR.Lower, Upper); 3849babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 385c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky 3867e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ----U L----- : this 3877e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L----U : CR 3887e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper)) 3897e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(CR.Lower, Upper); 3909babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3917e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ------U L---- : this 3927e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L-----U : CR 3937e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Lower.ult(Upper) && CR.Upper.ult(Lower)) 3947e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(Lower, CR.Upper); 3959babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 3969babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3977e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky assert(isWrappedSet() && CR.isWrappedSet() && 3987e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky "ConstantRange::unionWith missed wrapped union unwrapped case"); 3999babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 4007e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ------U L---- and ------U L---- : this 4017e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // -U L----------- and ------------U L : CR 4027e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper)) 4037e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(getBitWidth()); 4049babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 4057e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky APInt L = Lower, U = Upper; 4067e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Upper.ugt(U)) 4077e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky U = CR.Upper; 4087e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Lower.ult(L)) 4097e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky L = CR.Lower; 410c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky 411c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky return ConstantRange(L, U); 412645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 41396f9d7232c72867ee09641832d2db99f9166d6f0Chris Lattner 414fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// zeroExtend - Return a new range in the specified integer type, which must 415fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// be strictly larger than the current type. The returned range will 416e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer/// correspond to the possible range of values as if the source range had been 417fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// zero extended. 418bb626a6751db9a63d159d32522bdf88cedf46eebReid SpencerConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const { 41932cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false); 42032cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky 421bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer unsigned SrcTySize = getBitWidth(); 422663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer assert(SrcTySize < DstTySize && "Not a value extension"); 42332cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky if (isFullSet() || isWrappedSet()) 42432cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky // Change into [0, 1 << src bit width) 425dc5c1597014fa5c47c94db2b9fd424d2266053dbReid Spencer return ConstantRange(APInt(DstTySize,0), APInt(DstTySize,1).shl(SrcTySize)); 426fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 427663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer APInt L = Lower; L.zext(DstTySize); 428663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer APInt U = Upper; U.zext(DstTySize); 429663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return ConstantRange(L, U); 430e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky} 431e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky 432e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky/// signExtend - Return a new range in the specified integer type, which must 433e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky/// be strictly larger than the current type. The returned range will 434e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky/// correspond to the possible range of values as if the source range had been 435e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky/// sign extended. 436e32157c6098ee7536315e9793eed98d21bf71fd0Nick LewyckyConstantRange ConstantRange::signExtend(uint32_t DstTySize) const { 43732cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false); 43832cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky 439e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky unsigned SrcTySize = getBitWidth(); 440e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky assert(SrcTySize < DstTySize && "Not a value extension"); 44132cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky if (isFullSet() || isSignWrappedSet()) { 442e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1), 443ff84de767a9baded740abd1e846938477a4b285aNick Lewycky APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1); 444e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky } 445e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky 446e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky APInt L = Lower; L.sext(DstTySize); 447e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky APInt U = Upper; U.sext(DstTySize); 448e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky return ConstantRange(L, U); 449fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 450fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 451fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// truncate - Return a new range in the specified integer type, which must be 452fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// strictly smaller than the current type. The returned range will 453e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer/// correspond to the possible range of values as if the source range had been 454fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// truncated to the specified type. 455bb626a6751db9a63d159d32522bdf88cedf46eebReid SpencerConstantRange ConstantRange::truncate(uint32_t DstTySize) const { 456bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer unsigned SrcTySize = getBitWidth(); 457663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer assert(SrcTySize > DstTySize && "Not a value truncation"); 458daacf22537e0d140c379a39a11a83d3321395d4dZhou Sheng APInt Size(APInt::getLowBitsSet(SrcTySize, DstTySize)); 459663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer if (isFullSet() || getSetSize().ugt(Size)) 4607f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(DstTySize, /*isFullSet=*/true); 461fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 462663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer APInt L = Lower; L.trunc(DstTySize); 463663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer APInt U = Upper; U.trunc(DstTySize); 464663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return ConstantRange(L, U); 465fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 466fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 46795a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes/// zextOrTrunc - make this range have the bit width given by \p DstTySize. The 46895a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes/// value is zero extended, truncated, or left alone to make it that width. 46995a3be0ba44e96308c65c28ee859acc36149ddd8Nuno LopesConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const { 47095a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes unsigned SrcTySize = getBitWidth(); 47195a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes if (SrcTySize > DstTySize) 47295a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return truncate(DstTySize); 47395a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes else if (SrcTySize < DstTySize) 47495a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return zeroExtend(DstTySize); 47595a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes else 47695a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return *this; 47795a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes} 47895a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes 47995a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes/// sextOrTrunc - make this range have the bit width given by \p DstTySize. The 48095a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes/// value is sign extended, truncated, or left alone to make it that width. 48195a3be0ba44e96308c65c28ee859acc36149ddd8Nuno LopesConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const { 48295a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes unsigned SrcTySize = getBitWidth(); 48395a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes if (SrcTySize > DstTySize) 48495a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return truncate(DstTySize); 48595a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes else if (SrcTySize < DstTySize) 48695a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return signExtend(DstTySize); 48795a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes else 48895a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return *this; 48995a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes} 49095a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes 491a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 492a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange::add(const ConstantRange &Other) const { 493a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (isEmptySet() || Other.isEmptySet()) 494a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/false); 495cf9e07dea8aad32c5e7e2631d135566b20e1763cNick Lewycky if (isFullSet() || Other.isFullSet()) 496cf9e07dea8aad32c5e7e2631d135566b20e1763cNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 497a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 498a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize(); 499a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt NewLower = getLower() + Other.getLower(); 500a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt NewUpper = getUpper() + Other.getUpper() - 1; 501a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (NewLower == NewUpper) 502a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/true); 503a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 504a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman ConstantRange X = ConstantRange(NewLower, NewUpper); 505a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y)) 506a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman // We've wrapped, therefore, full set. 507a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/true); 508a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 509a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return X; 510a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 511a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 512a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 5137f9ef4bb514d5a28637789d8f397dadd4344dc1bNick LewyckyConstantRange::sub(const ConstantRange &Other) const { 5147f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isEmptySet() || Other.isEmptySet()) 5157f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 5167f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isFullSet() || Other.isFullSet()) 5177f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 5187f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky 5197f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize(); 5207f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky APInt NewLower = getLower() - Other.getLower(); 5217f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky APInt NewUpper = getUpper() - Other.getUpper() + 1; 5227f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (NewLower == NewUpper) 5237f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 5247f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky 5257f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky ConstantRange X = ConstantRange(NewLower, NewUpper); 5267f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y)) 5277f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky // We've wrapped, therefore, full set. 5287f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 5297f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky 5307f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return X; 5317f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky} 5327f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky 5337f9ef4bb514d5a28637789d8f397dadd4344dc1bNick LewyckyConstantRange 534a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange::multiply(const ConstantRange &Other) const { 5358dcc58e6b44fbaab39a24b1f75e67f05275084dcDan Gohman // TODO: If either operand is a single element and the multiply is known to 5368dcc58e6b44fbaab39a24b1f75e67f05275084dcDan Gohman // be non-wrapping, round the result min and max value to the appropriate 5378dcc58e6b44fbaab39a24b1f75e67f05275084dcDan Gohman // multiple of that element. If wrapping is possible, at least adjust the 5388dcc58e6b44fbaab39a24b1f75e67f05275084dcDan Gohman // range according to the greatest power-of-two factor of the single element. 539153f1ebeb8fd394e5b11b27edde9472de0cbb57fDan Gohman 5402ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky if (isEmptySet() || Other.isEmptySet()) 5412ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 5422ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky if (isFullSet() || Other.isFullSet()) 5432ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 5442ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky 545f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky APInt this_min = getUnsignedMin().zext(getBitWidth() * 2); 546f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky APInt this_max = getUnsignedMax().zext(getBitWidth() * 2); 547f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2); 548f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2); 5492ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky 550f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky ConstantRange Result_zext = ConstantRange(this_min * Other_min, 551f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky this_max * Other_max + 1); 5522ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky return Result_zext.truncate(getBitWidth()); 553a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 554a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 555a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 556a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange::smax(const ConstantRange &Other) const { 55738b06447615440f935008a2141bd0a1fe078d437Dan Gohman // X smax Y is: range(smax(X_smin, Y_smin), 55838b06447615440f935008a2141bd0a1fe078d437Dan Gohman // smax(X_smax, Y_smax)) 55938b06447615440f935008a2141bd0a1fe078d437Dan Gohman if (isEmptySet() || Other.isEmptySet()) 56038b06447615440f935008a2141bd0a1fe078d437Dan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/false); 56138b06447615440f935008a2141bd0a1fe078d437Dan Gohman APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin()); 56238b06447615440f935008a2141bd0a1fe078d437Dan Gohman APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1; 56338b06447615440f935008a2141bd0a1fe078d437Dan Gohman if (NewU == NewL) 56438b06447615440f935008a2141bd0a1fe078d437Dan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/true); 56538b06447615440f935008a2141bd0a1fe078d437Dan Gohman return ConstantRange(NewL, NewU); 566a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 567a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 568a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 569a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange::umax(const ConstantRange &Other) const { 570a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman // X umax Y is: range(umax(X_umin, Y_umin), 571a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman // umax(X_umax, Y_umax)) 572a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (isEmptySet() || Other.isEmptySet()) 573a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/false); 574a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); 575a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1; 576a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (NewU == NewL) 577a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/true); 578a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(NewL, NewU); 579a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 580a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 581a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 582956daf0f7f7fa473cf92c8193905a8a441932b69Nick LewyckyConstantRange::udiv(const ConstantRange &RHS) const { 583956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0) 584956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 585956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (RHS.isFullSet()) 586956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 587956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 588956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax()); 589956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 590956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky APInt RHS_umin = RHS.getUnsignedMin(); 591956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (RHS_umin == 0) { 592956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky // We want the lowest value in RHS excluding zero. Usually that would be 1 593956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky // except for a range in the form of [X, 1) in which case it would be X. 594956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (RHS.getUpper() == 1) 595956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky RHS_umin = RHS.getLower(); 596956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky else 597956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky RHS_umin = APInt(getBitWidth(), 1); 598956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky } 599956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 600956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1; 601956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 602956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky // If the LHS is Full and the RHS is a wrapped interval containing 1 then 603956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky // this could occur. 604956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (Lower == Upper) 605956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 606956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 607956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky return ConstantRange(Lower, Upper); 608a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 609a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 61034e992da381bf8b1a9cbcc1bde0b117207809649Nuno LopesConstantRange 611198381e542320265e1c5fed18e938db3563a45bfNick LewyckyConstantRange::binaryAnd(const ConstantRange &Other) const { 612198381e542320265e1c5fed18e938db3563a45bfNick Lewycky if (isEmptySet() || Other.isEmptySet()) 613198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 614198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 615198381e542320265e1c5fed18e938db3563a45bfNick Lewycky // TODO: replace this with something less conservative 616198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 617198381e542320265e1c5fed18e938db3563a45bfNick Lewycky APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax()); 618198381e542320265e1c5fed18e938db3563a45bfNick Lewycky if (umin.isAllOnesValue()) 619198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 620198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(APInt::getNullValue(getBitWidth()), umin + 1); 621198381e542320265e1c5fed18e938db3563a45bfNick Lewycky} 622198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 623198381e542320265e1c5fed18e938db3563a45bfNick LewyckyConstantRange 624198381e542320265e1c5fed18e938db3563a45bfNick LewyckyConstantRange::binaryOr(const ConstantRange &Other) const { 625198381e542320265e1c5fed18e938db3563a45bfNick Lewycky if (isEmptySet() || Other.isEmptySet()) 626198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 627198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 628198381e542320265e1c5fed18e938db3563a45bfNick Lewycky // TODO: replace this with something less conservative 629198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 630198381e542320265e1c5fed18e938db3563a45bfNick Lewycky APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); 631198381e542320265e1c5fed18e938db3563a45bfNick Lewycky if (umax.isMinValue()) 632198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 633198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(umax, APInt::getNullValue(getBitWidth())); 634198381e542320265e1c5fed18e938db3563a45bfNick Lewycky} 635198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 636198381e542320265e1c5fed18e938db3563a45bfNick LewyckyConstantRange 6377f9ef4bb514d5a28637789d8f397dadd4344dc1bNick LewyckyConstantRange::shl(const ConstantRange &Other) const { 6387f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isEmptySet() || Other.isEmptySet()) 6397f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 64034e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 6417f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky APInt min = getUnsignedMin().shl(Other.getUnsignedMin()); 6427f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky APInt max = getUnsignedMax().shl(Other.getUnsignedMax()); 64334e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 64434e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes // there's no overflow! 6454459145c2ccb5d063841a5d8c76b8b8ac9adaf2fNuno Lopes APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros()); 6467f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (Zeros.ugt(Other.getUnsignedMax())) 6477f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(min, max + 1); 64834e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 64934e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes // FIXME: implement the other tricky cases 6507f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 65134e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes} 65234e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 65334e992da381bf8b1a9cbcc1bde0b117207809649Nuno LopesConstantRange 6547f9ef4bb514d5a28637789d8f397dadd4344dc1bNick LewyckyConstantRange::lshr(const ConstantRange &Other) const { 6557f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isEmptySet() || Other.isEmptySet()) 6567f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 65734e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 6587f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()); 6597f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky APInt min = getUnsignedMin().lshr(Other.getUnsignedMax()); 6607f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (min == max + 1) 6617f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 6627f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky 6637f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(min, max + 1); 66434e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes} 66534e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 6669773e45a1e97f5098905bac26b8b8b7c844473f0Owen AndersonConstantRange ConstantRange::inverse() const { 6679773e45a1e97f5098905bac26b8b8b7c844473f0Owen Anderson if (isFullSet()) { 6687f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 6699773e45a1e97f5098905bac26b8b8b7c844473f0Owen Anderson } else if (isEmptySet()) { 6707f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 6719773e45a1e97f5098905bac26b8b8b7c844473f0Owen Anderson } 6729773e45a1e97f5098905bac26b8b8b7c844473f0Owen Anderson return ConstantRange(Upper, Lower); 6739773e45a1e97f5098905bac26b8b8b7c844473f0Owen Anderson} 6749773e45a1e97f5098905bac26b8b8b7c844473f0Owen Anderson 67538b06447615440f935008a2141bd0a1fe078d437Dan Gohman/// print - Print out the bounds to a stream... 676a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman/// 67738b06447615440f935008a2141bd0a1fe078d437Dan Gohmanvoid ConstantRange::print(raw_ostream &OS) const { 678df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman if (isFullSet()) 679df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman OS << "full-set"; 680df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman else if (isEmptySet()) 681df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman OS << "empty-set"; 682df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman else 683df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman OS << "[" << Lower << "," << Upper << ")"; 684a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 685a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 68638b06447615440f935008a2141bd0a1fe078d437Dan Gohman/// dump - Allow printing from a debugger easily... 687a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman/// 68838b06447615440f935008a2141bd0a1fe078d437Dan Gohmanvoid ConstantRange::dump() const { 6897fd5fb4b4755c3df86da5a0ebedf0d328fafbc81David Greene print(dbgs()); 690a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 691