ConstantRange.cpp revision 4459145c2ccb5d063841a5d8c76b8b8ac9adaf2f
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 24645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner#include "llvm/Support/ConstantRange.h" 25944fac71e082cc2664cc71b4d3f6c72bab7143fbChris Lattner#include "llvm/Support/raw_ostream.h" 26bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky#include "llvm/Instructions.h" 272cdd21c2e4d855500dfb53f77aa74da53ccf9de6Chris Lattnerusing namespace llvm; 28d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 29645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// Initialize a full (the default) or empty set for the specified type. 30645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 3138b06447615440f935008a2141bd0a1fe078d437Dan GohmanConstantRange::ConstantRange(uint32_t BitWidth, bool Full) { 32645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner if (Full) 33663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer Lower = Upper = APInt::getMaxValue(BitWidth); 34645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner else 35663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer Lower = Upper = APInt::getMinValue(BitWidth); 36645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 37645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 38fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// Initialize a range to hold the single specified value. 39fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// 4038b06447615440f935008a2141bd0a1fe078d437Dan GohmanConstantRange::ConstantRange(const APInt & V) : Lower(V), Upper(V + 1) {} 41645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 4238b06447615440f935008a2141bd0a1fe078d437Dan GohmanConstantRange::ConstantRange(const APInt &L, const APInt &U) : 4338b06447615440f935008a2141bd0a1fe078d437Dan Gohman Lower(L), Upper(U) { 4438b06447615440f935008a2141bd0a1fe078d437Dan Gohman assert(L.getBitWidth() == U.getBitWidth() && 4538b06447615440f935008a2141bd0a1fe078d437Dan Gohman "ConstantRange with unequal bit widths"); 46c125c00e68138b8ae7861b589277a491ee217893Zhou Sheng assert((L != U || (L.isMaxValue() || L.isMinValue())) && 47663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer "Lower == Upper, but they aren't min or max value!"); 48663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer} 49663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer 50bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick LewyckyConstantRange ConstantRange::makeICmpRegion(unsigned Pred, 51bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky const ConstantRange &CR) { 52bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky uint32_t W = CR.getBitWidth(); 53bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky switch (Pred) { 54bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky default: assert(!"Invalid ICmp predicate to makeICmpRegion()"); 55bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky case ICmpInst::ICMP_EQ: 56f067a233562d3cfeb29d0092d1069bb8d25cad31Nick Lewycky return CR; 57bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky case ICmpInst::ICMP_NE: 58bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (CR.isSingleElement()) 59bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(CR.getUpper(), CR.getLower()); 60bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(W); 61bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky case ICmpInst::ICMP_ULT: 62bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(APInt::getMinValue(W), CR.getUnsignedMax()); 63bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky case ICmpInst::ICMP_SLT: 64bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(APInt::getSignedMinValue(W), CR.getSignedMax()); 65bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky case ICmpInst::ICMP_ULE: { 66bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky APInt UMax(CR.getUnsignedMax()); 67bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (UMax.isMaxValue()) 68bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(W); 69bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(APInt::getMinValue(W), UMax + 1); 70bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 71bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky case ICmpInst::ICMP_SLE: { 72bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky APInt SMax(CR.getSignedMax()); 73bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (SMax.isMaxSignedValue() || (SMax+1).isMaxSignedValue()) 74bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(W); 75bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(APInt::getSignedMinValue(W), SMax + 1); 76bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 77bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky case ICmpInst::ICMP_UGT: 78bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(CR.getUnsignedMin() + 1, APInt::getNullValue(W)); 79bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky case ICmpInst::ICMP_SGT: 80bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(CR.getSignedMin() + 1, 81bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky APInt::getSignedMinValue(W)); 82bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky case ICmpInst::ICMP_UGE: { 83bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky APInt UMin(CR.getUnsignedMin()); 84bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (UMin.isMinValue()) 85bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(W); 86bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(UMin, APInt::getNullValue(W)); 87bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 88bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky case ICmpInst::ICMP_SGE: { 89bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky APInt SMin(CR.getSignedMin()); 90bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (SMin.isMinSignedValue()) 91bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(W); 92bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(SMin, APInt::getSignedMinValue(W)); 93bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 94bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 95bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky} 96bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 97645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// isFullSet - Return true if this set contains all of the elements possible 98645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// for this data-type 99645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattnerbool ConstantRange::isFullSet() const { 100c125c00e68138b8ae7861b589277a491ee217893Zhou Sheng return Lower == Upper && Lower.isMaxValue(); 101645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 102fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 103645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// isEmptySet - Return true if this set contains no members. 104645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 105645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattnerbool ConstantRange::isEmptySet() const { 106c125c00e68138b8ae7861b589277a491ee217893Zhou Sheng return Lower == Upper && Lower.isMinValue(); 107645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 108645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 109645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// isWrappedSet - Return true if this set wraps around the top of the range, 110645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// for example: [100, 8) 111645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 112a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencerbool ConstantRange::isWrappedSet() const { 113663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return Lower.ugt(Upper); 114645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 115645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 116645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// getSetSize - Return the number of elements in this set. 117645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 118663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid SpencerAPInt ConstantRange::getSetSize() const { 119663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer if (isEmptySet()) 120bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer return APInt(getBitWidth(), 0); 121bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer if (getBitWidth() == 1) { 122645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner if (Lower != Upper) // One of T or F in the set... 123bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer return APInt(2, 1); 124bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer return APInt(2, 2); // Must be full set... 125645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner } 126fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 127645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // Simply subtract the bounds... 128663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return Upper - Lower; 129645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 130645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 1313400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getUnsignedMax - Return the largest unsigned value contained in the 1323400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 1333400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1343400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getUnsignedMax() const { 1353400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (isFullSet() || isWrappedSet()) 1363400e6af6b10acea219c02ac262637220f84218fNick Lewycky return APInt::getMaxValue(getBitWidth()); 1373400e6af6b10acea219c02ac262637220f84218fNick Lewycky else 1383400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getUpper() - 1; 1393400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 1403400e6af6b10acea219c02ac262637220f84218fNick Lewycky 1413400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getUnsignedMin - Return the smallest unsigned value contained in the 1423400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 1433400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1443400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getUnsignedMin() const { 1453400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (isFullSet() || (isWrappedSet() && getUpper() != 0)) 1463400e6af6b10acea219c02ac262637220f84218fNick Lewycky return APInt::getMinValue(getBitWidth()); 1473400e6af6b10acea219c02ac262637220f84218fNick Lewycky else 1483400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getLower(); 1493400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 1503400e6af6b10acea219c02ac262637220f84218fNick Lewycky 1513400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getSignedMax - Return the largest signed value contained in the 1523400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 1533400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1543400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getSignedMax() const { 155daacf22537e0d140c379a39a11a83d3321395d4dZhou Sheng APInt SignedMax(APInt::getSignedMaxValue(getBitWidth())); 1563400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (!isWrappedSet()) { 157ae5eb7accf65ee94e22b3d235d466d71268f1e83Nick Lewycky if (getLower().sle(getUpper() - 1)) 1583400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getUpper() - 1; 1593400e6af6b10acea219c02ac262637220f84218fNick Lewycky else 1603400e6af6b10acea219c02ac262637220f84218fNick Lewycky return SignedMax; 1613400e6af6b10acea219c02ac262637220f84218fNick Lewycky } else { 162780905e9f9f29419de56b47253f6db84bc659f42Nick Lewycky if (getLower().isNegative() == getUpper().isNegative()) 163780905e9f9f29419de56b47253f6db84bc659f42Nick Lewycky return SignedMax; 164780905e9f9f29419de56b47253f6db84bc659f42Nick Lewycky else 1653400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getUpper() - 1; 1663400e6af6b10acea219c02ac262637220f84218fNick Lewycky } 1673400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 1683400e6af6b10acea219c02ac262637220f84218fNick Lewycky 1693400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getSignedMin - Return the smallest signed value contained in the 1703400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 1713400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1723400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getSignedMin() const { 173daacf22537e0d140c379a39a11a83d3321395d4dZhou Sheng APInt SignedMin(APInt::getSignedMinValue(getBitWidth())); 1743400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (!isWrappedSet()) { 175ae5eb7accf65ee94e22b3d235d466d71268f1e83Nick Lewycky if (getLower().sle(getUpper() - 1)) 1763400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getLower(); 1773400e6af6b10acea219c02ac262637220f84218fNick Lewycky else 1783400e6af6b10acea219c02ac262637220f84218fNick Lewycky return SignedMin; 1793400e6af6b10acea219c02ac262637220f84218fNick Lewycky } else { 1803400e6af6b10acea219c02ac262637220f84218fNick Lewycky if ((getUpper() - 1).slt(getLower())) { 1813400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (getUpper() != SignedMin) 1823400e6af6b10acea219c02ac262637220f84218fNick Lewycky return SignedMin; 1833400e6af6b10acea219c02ac262637220f84218fNick Lewycky else 1843400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getLower(); 1853400e6af6b10acea219c02ac262637220f84218fNick Lewycky } else { 1863400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getLower(); 1873400e6af6b10acea219c02ac262637220f84218fNick Lewycky } 1883400e6af6b10acea219c02ac262637220f84218fNick Lewycky } 1893400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 1903400e6af6b10acea219c02ac262637220f84218fNick Lewycky 191fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// contains - Return true if the specified value is in the set. 192fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// 193a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencerbool ConstantRange::contains(const APInt &V) const { 194a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer if (Lower == Upper) 195a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer return isFullSet(); 196fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 197a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer if (!isWrappedSet()) 198a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer return Lower.ule(V) && V.ult(Upper); 199663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer else 200663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return Lower.ule(V) || V.ult(Upper); 201fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 202645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 203bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky/// contains - Return true if the argument is a subset of this range. 204bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky/// Two equal set contain each other. The empty set is considered to be 205bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky/// contained by all other sets. 206bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky/// 207bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewyckybool ConstantRange::contains(const ConstantRange &Other) const { 208bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (isFullSet()) return true; 209bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (Other.isFullSet()) return false; 210bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (Other.isEmptySet()) return true; 211bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (isEmptySet()) return false; 212bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 213bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (!isWrappedSet()) { 214bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (Other.isWrappedSet()) 215bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return false; 216bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 217bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper); 218bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 219bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 220bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (!Other.isWrappedSet()) 221bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return Other.getUpper().ule(Upper) || 222bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky Lower.ule(Other.getLower()); 223bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 224bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower()); 225bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky} 226bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 227fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// subtract - Subtract the specified constant from the endpoints of this 228fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// constant range. 229581b0d453a63f7f657248f80317976995262be11Reid SpencerConstantRange ConstantRange::subtract(const APInt &Val) const { 230bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width"); 231fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner // If the set is empty or full, don't modify the endpoints. 232663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer if (Lower == Upper) 233663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return *this; 234663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return ConstantRange(Lower - Val, Upper - Val); 235fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 236fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 237fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 238645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// intersect1Wrapped - This helper function is used to intersect two ranges when 239645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// it is known that LHS is wrapped and RHS isn't. 240645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// 241663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid SpencerConstantRange 242663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid SpencerConstantRange::intersect1Wrapped(const ConstantRange &LHS, 243a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer const ConstantRange &RHS) { 244a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer assert(LHS.isWrappedSet() && !RHS.isWrappedSet()); 245645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 246645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // Check to see if we overlap on the Left side of RHS... 247645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // 248a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer if (RHS.Lower.ult(LHS.Upper)) { 249645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // We do overlap on the left side of RHS, see if we overlap on the right of 250645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // RHS... 251a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer if (RHS.Upper.ugt(LHS.Lower)) { 252645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // Ok, the result overlaps on both the left and right sides. See if the 253645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // resultant interval will be smaller if we wrap or not... 254645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // 255663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer if (LHS.getSetSize().ult(RHS.getSetSize())) 256645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner return LHS; 257645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner else 258645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner return RHS; 259645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 260645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner } else { 261645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // No overlap on the right, just on the left. 262dc5c1597014fa5c47c94db2b9fd424d2266053dbReid Spencer return ConstantRange(RHS.Lower, LHS.Upper); 263645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner } 264645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner } else { 265645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // We don't overlap on the left side of RHS, see if we overlap on the right 266645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // of RHS... 267a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer if (RHS.Upper.ugt(LHS.Lower)) { 268645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // Simple overlap... 269dc5c1597014fa5c47c94db2b9fd424d2266053dbReid Spencer return ConstantRange(LHS.Lower, RHS.Upper); 270645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner } else { 271645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // No overlap... 272bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer return ConstantRange(LHS.getBitWidth(), false); 273645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner } 274645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner } 275645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 276645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 2773e051647c079fe29db049646b39611fc0135327dNick Lewycky/// intersectWith - Return the range that results from the intersection of this 2783a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky/// range with another range. The resultant range is guaranteed to include all 2793a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky/// elements contained in both input ranges, and to have the smallest possible 2803a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky/// set size that does so. Because there may be two intersections with the 2813a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky/// same set size, A.intersectWith(B) might not be equal to B.intersectWith(A). 282a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid SpencerConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const { 283bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer assert(getBitWidth() == CR.getBitWidth() && 284bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer "ConstantRange types don't agree!"); 285377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 286377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky // Handle common cases. 287377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if ( isEmptySet() || CR.isFullSet()) return *this; 288377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.isEmptySet() || isFullSet()) return CR; 289377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 290377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (!isWrappedSet() && CR.isWrappedSet()) 2913a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky return CR.intersectWith(*this); 292377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 293377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (!isWrappedSet() && !CR.isWrappedSet()) { 294377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (Lower.ult(CR.Lower)) { 295377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (Upper.ule(CR.Lower)) 296377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(getBitWidth(), false); 297377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 298377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (Upper.ult(CR.Upper)) 299377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(CR.Lower, Upper); 300377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 301377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 302377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } else { 303377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (Upper.ult(CR.Upper)) 304377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return *this; 305377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 306377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (Lower.ult(CR.Upper)) 307377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(Lower, CR.Upper); 308377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 309377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(getBitWidth(), false); 310377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 311377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 312377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 313377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (isWrappedSet() && !CR.isWrappedSet()) { 314377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Lower.ult(Upper)) { 315377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Upper.ult(Upper)) 316377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 317377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 318377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Upper.ult(Lower)) 319377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(CR.Lower, Upper); 320377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 321377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (getSetSize().ult(CR.getSetSize())) 322377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return *this; 323377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky else 324377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 325377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } else if (CR.Lower.ult(Lower)) { 326377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Upper.ule(Lower)) 327377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(getBitWidth(), false); 328377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 329377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(Lower, CR.Upper); 330377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 331377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 332377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 333377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 334377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Upper.ult(Upper)) { 335377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Lower.ult(Upper)) { 336377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (getSetSize().ult(CR.getSetSize())) 337377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return *this; 338377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky else 339377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 340377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 341377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 342377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Lower.ult(Lower)) 343377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(Lower, CR.Upper); 344377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 345377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 346377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } else if (CR.Upper.ult(Lower)) { 347377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Lower.ult(Lower)) 348377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return *this; 349377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 350377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(CR.Lower, Upper); 351377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 352377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (getSetSize().ult(CR.getSetSize())) 353377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return *this; 354377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky else 355377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 356377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky} 357377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 358377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 3593e051647c079fe29db049646b39611fc0135327dNick Lewycky/// unionWith - Return the range that results from the union of this range with 360645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// another range. The resultant range is guaranteed to include the elements of 3619babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky/// both sets, but may contain more. For example, [3, 9) union [12,15) is 3629babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky/// [3, 15), which includes 9, 10, and 11, which were not included in either 3639babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky/// set before. 364645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 365a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid SpencerConstantRange ConstantRange::unionWith(const ConstantRange &CR) const { 366bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer assert(getBitWidth() == CR.getBitWidth() && 367bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer "ConstantRange types don't agree!"); 368645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 369c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky if ( isFullSet() || CR.isEmptySet()) return *this; 370c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky if (CR.isFullSet() || isEmptySet()) return CR; 371645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 3729babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this); 3739babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3749babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (!isWrappedSet() && !CR.isWrappedSet()) { 3757e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) { 3767e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // If the two ranges are disjoint, find the smaller gap and bridge it. 3777e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; 3787e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (d1.ult(d2)) 3797e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(Lower, CR.Upper); 3807e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky else 3817e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(CR.Lower, Upper); 3827e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky } 3837e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky 3847e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky APInt L = Lower, U = Upper; 3859babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (CR.Lower.ult(L)) 3869babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky L = CR.Lower; 3877e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if ((CR.Upper - 1).ugt(U - 1)) 3889babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky U = CR.Upper; 3897e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky 3907e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (L == 0 && U == 0) 3917e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(getBitWidth()); 3927e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky 3937e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(L, U); 3949babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 3959babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3967e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (!CR.isWrappedSet()) { 3977e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ------U L----- and ------U L----- : this 3987e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L--U L--U : CR 3997e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower)) 4009babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky return *this; 4019babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 4027e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ------U L----- : this 4037e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L---------U : CR 4047e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) 4059babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky return ConstantRange(getBitWidth()); 4069babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 4077e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ----U L---- : this 4087e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L---U : CR 4097e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // <d1> <d2> 4107e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) { 4119babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; 4127e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (d1.ult(d2)) 4137e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(Lower, CR.Upper); 4147e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky else 4157e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(CR.Lower, Upper); 4169babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 417c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky 4187e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ----U L----- : this 4197e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L----U : CR 4207e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper)) 4217e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(CR.Lower, Upper); 4229babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 4237e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ------U L---- : this 4247e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L-----U : CR 4257e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Lower.ult(Upper) && CR.Upper.ult(Lower)) 4267e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(Lower, CR.Upper); 4279babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 4289babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 4297e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky assert(isWrappedSet() && CR.isWrappedSet() && 4307e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky "ConstantRange::unionWith missed wrapped union unwrapped case"); 4319babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 4327e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ------U L---- and ------U L---- : this 4337e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // -U L----------- and ------------U L : CR 4347e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper)) 4357e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(getBitWidth()); 4369babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 4377e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky APInt L = Lower, U = Upper; 4387e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Upper.ugt(U)) 4397e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky U = CR.Upper; 4407e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Lower.ult(L)) 4417e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky L = CR.Lower; 442c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky 443c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky return ConstantRange(L, U); 444645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 44596f9d7232c72867ee09641832d2db99f9166d6f0Chris Lattner 446fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// zeroExtend - Return a new range in the specified integer type, which must 447fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// be strictly larger than the current type. The returned range will 448e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer/// correspond to the possible range of values as if the source range had been 449fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// zero extended. 450bb626a6751db9a63d159d32522bdf88cedf46eebReid SpencerConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const { 451bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer unsigned SrcTySize = getBitWidth(); 452663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer assert(SrcTySize < DstTySize && "Not a value extension"); 453dc5c1597014fa5c47c94db2b9fd424d2266053dbReid Spencer if (isFullSet()) 454fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner // Change a source full set into [0, 1 << 8*numbytes) 455dc5c1597014fa5c47c94db2b9fd424d2266053dbReid Spencer return ConstantRange(APInt(DstTySize,0), APInt(DstTySize,1).shl(SrcTySize)); 456fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 457663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer APInt L = Lower; L.zext(DstTySize); 458663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer APInt U = Upper; U.zext(DstTySize); 459663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return ConstantRange(L, U); 460e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky} 461e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky 462e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky/// signExtend - Return a new range in the specified integer type, which must 463e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky/// be strictly larger than the current type. The returned range will 464e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky/// correspond to the possible range of values as if the source range had been 465e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky/// sign extended. 466e32157c6098ee7536315e9793eed98d21bf71fd0Nick LewyckyConstantRange ConstantRange::signExtend(uint32_t DstTySize) const { 467e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky unsigned SrcTySize = getBitWidth(); 468e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky assert(SrcTySize < DstTySize && "Not a value extension"); 469e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky if (isFullSet()) { 470e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1), 471ff84de767a9baded740abd1e846938477a4b285aNick Lewycky APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1); 472e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky } 473e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky 474e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky APInt L = Lower; L.sext(DstTySize); 475e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky APInt U = Upper; U.sext(DstTySize); 476e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky return ConstantRange(L, U); 477fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 478fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 479fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// truncate - Return a new range in the specified integer type, which must be 480fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// strictly smaller than the current type. The returned range will 481e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer/// correspond to the possible range of values as if the source range had been 482fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// truncated to the specified type. 483bb626a6751db9a63d159d32522bdf88cedf46eebReid SpencerConstantRange ConstantRange::truncate(uint32_t DstTySize) const { 484bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer unsigned SrcTySize = getBitWidth(); 485663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer assert(SrcTySize > DstTySize && "Not a value truncation"); 486daacf22537e0d140c379a39a11a83d3321395d4dZhou Sheng APInt Size(APInt::getLowBitsSet(SrcTySize, DstTySize)); 487663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer if (isFullSet() || getSetSize().ugt(Size)) 488bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer return ConstantRange(DstTySize); 489fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 490663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer APInt L = Lower; L.trunc(DstTySize); 491663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer APInt U = Upper; U.trunc(DstTySize); 492663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return ConstantRange(L, U); 493fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 494fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 49595a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes/// zextOrTrunc - make this range have the bit width given by \p DstTySize. The 49695a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes/// value is zero extended, truncated, or left alone to make it that width. 49795a3be0ba44e96308c65c28ee859acc36149ddd8Nuno LopesConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const { 49895a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes unsigned SrcTySize = getBitWidth(); 49995a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes if (SrcTySize > DstTySize) 50095a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return truncate(DstTySize); 50195a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes else if (SrcTySize < DstTySize) 50295a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return zeroExtend(DstTySize); 50395a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes else 50495a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return *this; 50595a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes} 50695a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes 50795a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes/// sextOrTrunc - make this range have the bit width given by \p DstTySize. The 50895a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes/// value is sign extended, truncated, or left alone to make it that width. 50995a3be0ba44e96308c65c28ee859acc36149ddd8Nuno LopesConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const { 51095a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes unsigned SrcTySize = getBitWidth(); 51195a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes if (SrcTySize > DstTySize) 51295a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return truncate(DstTySize); 51395a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes else if (SrcTySize < DstTySize) 51495a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return signExtend(DstTySize); 51595a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes else 51695a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return *this; 51795a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes} 51895a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes 519a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 520a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange::add(const ConstantRange &Other) const { 521a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (isEmptySet() || Other.isEmptySet()) 522a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/false); 523cf9e07dea8aad32c5e7e2631d135566b20e1763cNick Lewycky if (isFullSet() || Other.isFullSet()) 524cf9e07dea8aad32c5e7e2631d135566b20e1763cNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 525a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 526a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize(); 527a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt NewLower = getLower() + Other.getLower(); 528a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt NewUpper = getUpper() + Other.getUpper() - 1; 529a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (NewLower == NewUpper) 530a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/true); 531a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 532a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman ConstantRange X = ConstantRange(NewLower, NewUpper); 533a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y)) 534a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman // We've wrapped, therefore, full set. 535a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/true); 536a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 537a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return X; 538a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 539a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 540a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 541a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange::multiply(const ConstantRange &Other) const { 5422ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky if (isEmptySet() || Other.isEmptySet()) 5432ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 5442ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky if (isFullSet() || Other.isFullSet()) 5452ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 5462ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky 547f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky APInt this_min = getUnsignedMin().zext(getBitWidth() * 2); 548f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky APInt this_max = getUnsignedMax().zext(getBitWidth() * 2); 549f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2); 550f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2); 5512ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky 552f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky ConstantRange Result_zext = ConstantRange(this_min * Other_min, 553f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky this_max * Other_max + 1); 5542ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky return Result_zext.truncate(getBitWidth()); 555a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 556a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 557a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 558a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange::smax(const ConstantRange &Other) const { 55938b06447615440f935008a2141bd0a1fe078d437Dan Gohman // X smax Y is: range(smax(X_smin, Y_smin), 56038b06447615440f935008a2141bd0a1fe078d437Dan Gohman // smax(X_smax, Y_smax)) 56138b06447615440f935008a2141bd0a1fe078d437Dan Gohman if (isEmptySet() || Other.isEmptySet()) 56238b06447615440f935008a2141bd0a1fe078d437Dan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/false); 56338b06447615440f935008a2141bd0a1fe078d437Dan Gohman APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin()); 56438b06447615440f935008a2141bd0a1fe078d437Dan Gohman APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1; 56538b06447615440f935008a2141bd0a1fe078d437Dan Gohman if (NewU == NewL) 56638b06447615440f935008a2141bd0a1fe078d437Dan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/true); 56738b06447615440f935008a2141bd0a1fe078d437Dan Gohman return ConstantRange(NewL, NewU); 568a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 569a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 570a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 571a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange::umax(const ConstantRange &Other) const { 572a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman // X umax Y is: range(umax(X_umin, Y_umin), 573a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman // umax(X_umax, Y_umax)) 574a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (isEmptySet() || Other.isEmptySet()) 575a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/false); 576a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); 577a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1; 578a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (NewU == NewL) 579a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/true); 580a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(NewL, NewU); 581a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 582a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 583a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 584956daf0f7f7fa473cf92c8193905a8a441932b69Nick LewyckyConstantRange::udiv(const ConstantRange &RHS) const { 585956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0) 586956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 587956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (RHS.isFullSet()) 588956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 589956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 590956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax()); 591956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 592956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky APInt RHS_umin = RHS.getUnsignedMin(); 593956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (RHS_umin == 0) { 594956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky // We want the lowest value in RHS excluding zero. Usually that would be 1 595956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky // except for a range in the form of [X, 1) in which case it would be X. 596956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (RHS.getUpper() == 1) 597956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky RHS_umin = RHS.getLower(); 598956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky else 599956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky RHS_umin = APInt(getBitWidth(), 1); 600956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky } 601956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 602956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1; 603956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 604956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky // If the LHS is Full and the RHS is a wrapped interval containing 1 then 605956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky // this could occur. 606956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (Lower == Upper) 607956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 608956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 609956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky return ConstantRange(Lower, Upper); 610a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 611a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 61234e992da381bf8b1a9cbcc1bde0b117207809649Nuno LopesConstantRange 61334e992da381bf8b1a9cbcc1bde0b117207809649Nuno LopesConstantRange::shl(const ConstantRange &Amount) const { 61434e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes if (isEmptySet()) 61534e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes return *this; 61634e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 61734e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes APInt min = getUnsignedMin() << Amount.getUnsignedMin(); 61834e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes APInt max = getUnsignedMax() << Amount.getUnsignedMax(); 61934e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 62034e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes // there's no overflow! 6214459145c2ccb5d063841a5d8c76b8b8ac9adaf2fNuno Lopes APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros()); 62234e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes if (Zeros.uge(Amount.getUnsignedMax())) 62334e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes return ConstantRange(min, max); 62434e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 62534e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes // FIXME: implement the other tricky cases 62634e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes return ConstantRange(getBitWidth()); 62734e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes} 62834e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 62934e992da381bf8b1a9cbcc1bde0b117207809649Nuno LopesConstantRange 63034e992da381bf8b1a9cbcc1bde0b117207809649Nuno LopesConstantRange::ashr(const ConstantRange &Amount) const { 63134e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes if (isEmptySet()) 63234e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes return *this; 63334e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 63434e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes APInt min = getUnsignedMax().ashr(Amount.getUnsignedMin()); 63534e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes APInt max = getUnsignedMin().ashr(Amount.getUnsignedMax()); 63634e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes return ConstantRange(min, max); 63734e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes} 63834e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 63934e992da381bf8b1a9cbcc1bde0b117207809649Nuno LopesConstantRange 64034e992da381bf8b1a9cbcc1bde0b117207809649Nuno LopesConstantRange::lshr(const ConstantRange &Amount) const { 64134e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes if (isEmptySet()) 64234e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes return *this; 64334e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 64434e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes APInt min = getUnsignedMax().lshr(Amount.getUnsignedMin()); 64534e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes APInt max = getUnsignedMin().lshr(Amount.getUnsignedMax()); 64634e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes return ConstantRange(min, max); 64734e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes} 64834e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 64938b06447615440f935008a2141bd0a1fe078d437Dan Gohman/// print - Print out the bounds to a stream... 650a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman/// 65138b06447615440f935008a2141bd0a1fe078d437Dan Gohmanvoid ConstantRange::print(raw_ostream &OS) const { 65238b06447615440f935008a2141bd0a1fe078d437Dan Gohman OS << "[" << Lower << "," << Upper << ")"; 653a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 654a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 65538b06447615440f935008a2141bd0a1fe078d437Dan Gohman/// dump - Allow printing from a debugger easily... 656a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman/// 65738b06447615440f935008a2141bd0a1fe078d437Dan Gohmanvoid ConstantRange::dump() const { 65838b06447615440f935008a2141bd0a1fe078d437Dan Gohman print(errs()); 659a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 660a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 66145cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattner 662