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 240b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/InstrTypes.h" 25645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner#include "llvm/Support/ConstantRange.h" 267fd5fb4b4755c3df86da5a0ebedf0d328fafbc81David Greene#include "llvm/Support/Debug.h" 27944fac71e082cc2664cc71b4d3f6c72bab7143fbChris Lattner#include "llvm/Support/raw_ostream.h" 282cdd21c2e4d855500dfb53f77aa74da53ccf9de6Chris Lattnerusing namespace llvm; 29d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 30645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// Initialize a full (the default) or empty set for the specified type. 31645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 3238b06447615440f935008a2141bd0a1fe078d437Dan GohmanConstantRange::ConstantRange(uint32_t BitWidth, bool Full) { 33645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner if (Full) 34663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer Lower = Upper = APInt::getMaxValue(BitWidth); 35645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner else 36663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer Lower = Upper = APInt::getMinValue(BitWidth); 37645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 38645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 39fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// Initialize a range to hold the single specified value. 40fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// 41318b7cc7f10d41370929ff93274de29c11f87b81Benjamin KramerConstantRange::ConstantRange(APIntMoveTy V) 42318b7cc7f10d41370929ff93274de29c11f87b81Benjamin Kramer : Lower(llvm_move(V)), Upper(Lower + 1) {} 43645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 44318b7cc7f10d41370929ff93274de29c11f87b81Benjamin KramerConstantRange::ConstantRange(APIntMoveTy L, APIntMoveTy U) 45318b7cc7f10d41370929ff93274de29c11f87b81Benjamin Kramer : Lower(llvm_move(L)), Upper(llvm_move(U)) { 46318b7cc7f10d41370929ff93274de29c11f87b81Benjamin Kramer assert(Lower.getBitWidth() == Upper.getBitWidth() && 4738b06447615440f935008a2141bd0a1fe078d437Dan Gohman "ConstantRange with unequal bit widths"); 48318b7cc7f10d41370929ff93274de29c11f87b81Benjamin Kramer assert((Lower != Upper || (Lower.isMaxValue() || Lower.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) { 54f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky if (CR.isEmptySet()) 55f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky return CR; 56f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky 57bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky uint32_t W = CR.getBitWidth(); 58bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky switch (Pred) { 59858143816d43e58b17bfd11cb1b57afbd7f0f893Craig Topper default: llvm_unreachable("Invalid ICmp predicate to makeICmpRegion()"); 60a09d514b291151ad9c92c9bf8776583de231ded4Frits van Bommel case CmpInst::ICMP_EQ: 61f067a233562d3cfeb29d0092d1069bb8d25cad31Nick Lewycky return CR; 62a09d514b291151ad9c92c9bf8776583de231ded4Frits van Bommel case CmpInst::ICMP_NE: 63bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (CR.isSingleElement()) 64bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(CR.getUpper(), CR.getLower()); 65bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(W); 66a09d514b291151ad9c92c9bf8776583de231ded4Frits van Bommel case CmpInst::ICMP_ULT: { 67f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky APInt UMax(CR.getUnsignedMax()); 68f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky if (UMax.isMinValue()) 69f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky return ConstantRange(W, /* empty */ false); 70f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky return ConstantRange(APInt::getMinValue(W), UMax); 71f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky } 72a09d514b291151ad9c92c9bf8776583de231ded4Frits van Bommel case CmpInst::ICMP_SLT: { 73f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky APInt SMax(CR.getSignedMax()); 74f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky if (SMax.isMinSignedValue()) 75f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky return ConstantRange(W, /* empty */ false); 76f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky return ConstantRange(APInt::getSignedMinValue(W), SMax); 77f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky } 78a09d514b291151ad9c92c9bf8776583de231ded4Frits van Bommel case CmpInst::ICMP_ULE: { 79bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky APInt UMax(CR.getUnsignedMax()); 80bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (UMax.isMaxValue()) 81bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(W); 82bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(APInt::getMinValue(W), UMax + 1); 83bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 84a09d514b291151ad9c92c9bf8776583de231ded4Frits van Bommel case CmpInst::ICMP_SLE: { 85bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky APInt SMax(CR.getSignedMax()); 86f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky if (SMax.isMaxSignedValue()) 87bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(W); 88bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(APInt::getSignedMinValue(W), SMax + 1); 89bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 90a09d514b291151ad9c92c9bf8776583de231ded4Frits van Bommel case CmpInst::ICMP_UGT: { 91f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky APInt UMin(CR.getUnsignedMin()); 92f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky if (UMin.isMaxValue()) 93f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky return ConstantRange(W, /* empty */ false); 94f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky return ConstantRange(UMin + 1, APInt::getNullValue(W)); 95f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky } 96a09d514b291151ad9c92c9bf8776583de231ded4Frits van Bommel case CmpInst::ICMP_SGT: { 97f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky APInt SMin(CR.getSignedMin()); 98f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky if (SMin.isMaxSignedValue()) 99f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky return ConstantRange(W, /* empty */ false); 100f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky return ConstantRange(SMin + 1, APInt::getSignedMinValue(W)); 101f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky } 102a09d514b291151ad9c92c9bf8776583de231ded4Frits van Bommel case CmpInst::ICMP_UGE: { 103bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky APInt UMin(CR.getUnsignedMin()); 104bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (UMin.isMinValue()) 105bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(W); 106bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(UMin, APInt::getNullValue(W)); 107bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 108a09d514b291151ad9c92c9bf8776583de231ded4Frits van Bommel case CmpInst::ICMP_SGE: { 109bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky APInt SMin(CR.getSignedMin()); 110bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (SMin.isMinSignedValue()) 111bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(W); 112bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(SMin, APInt::getSignedMinValue(W)); 113bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 114bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 115bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky} 116bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 117645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// isFullSet - Return true if this set contains all of the elements possible 118645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// for this data-type 119645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattnerbool ConstantRange::isFullSet() const { 120c125c00e68138b8ae7861b589277a491ee217893Zhou Sheng return Lower == Upper && Lower.isMaxValue(); 121645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 122fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 123645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// isEmptySet - Return true if this set contains no members. 124645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 125645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattnerbool ConstantRange::isEmptySet() const { 126c125c00e68138b8ae7861b589277a491ee217893Zhou Sheng return Lower == Upper && Lower.isMinValue(); 127645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 128645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 129645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// isWrappedSet - Return true if this set wraps around the top of the range, 130645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// for example: [100, 8) 131645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 132a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencerbool ConstantRange::isWrappedSet() const { 133663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return Lower.ugt(Upper); 134645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 135645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 13632cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky/// isSignWrappedSet - Return true if this set wraps around the INT_MIN of 13732cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky/// its bitwidth, for example: i8 [120, 140). 13832cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky/// 13932cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewyckybool ConstantRange::isSignWrappedSet() const { 14032cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky return contains(APInt::getSignedMaxValue(getBitWidth())) && 14132cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky contains(APInt::getSignedMinValue(getBitWidth())); 14232cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky} 14332cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky 144645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// getSetSize - Return the number of elements in this set. 145645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 146663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid SpencerAPInt ConstantRange::getSetSize() const { 147367308f798338e162b4ab76efa785caa847487c0Nuno Lopes if (isEmptySet()) 148367308f798338e162b4ab76efa785caa847487c0Nuno Lopes return APInt(getBitWidth()+1, 0); 149367308f798338e162b4ab76efa785caa847487c0Nuno Lopes 1505d2fada44ce77c6db15173a8107bf253c2293170Nuno Lopes if (isFullSet()) { 1515d2fada44ce77c6db15173a8107bf253c2293170Nuno Lopes APInt Size(getBitWidth()+1, 0); 1525d2fada44ce77c6db15173a8107bf253c2293170Nuno Lopes Size.setBit(getBitWidth()); 1535d2fada44ce77c6db15173a8107bf253c2293170Nuno Lopes return Size; 154645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner } 155fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1565d2fada44ce77c6db15173a8107bf253c2293170Nuno Lopes // This is also correct for wrapped sets. 157367308f798338e162b4ab76efa785caa847487c0Nuno Lopes return (Upper - Lower).zext(getBitWidth()+1); 158645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 159645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 1603400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getUnsignedMax - Return the largest unsigned value contained in the 1613400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 1623400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1633400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getUnsignedMax() const { 1643400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (isFullSet() || isWrappedSet()) 1653400e6af6b10acea219c02ac262637220f84218fNick Lewycky return APInt::getMaxValue(getBitWidth()); 16648a09aec60c5daf67430811e24256d501a576766Nick Lewycky return getUpper() - 1; 1673400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 1683400e6af6b10acea219c02ac262637220f84218fNick Lewycky 1693400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getUnsignedMin - Return the smallest unsigned value contained in the 1703400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 1713400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1723400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getUnsignedMin() const { 1733400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (isFullSet() || (isWrappedSet() && getUpper() != 0)) 1743400e6af6b10acea219c02ac262637220f84218fNick Lewycky return APInt::getMinValue(getBitWidth()); 17548a09aec60c5daf67430811e24256d501a576766Nick Lewycky return getLower(); 1763400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 1773400e6af6b10acea219c02ac262637220f84218fNick Lewycky 1783400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getSignedMax - Return the largest signed value contained in the 1793400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 1803400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1813400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getSignedMax() const { 182daacf22537e0d140c379a39a11a83d3321395d4dZhou Sheng APInt SignedMax(APInt::getSignedMaxValue(getBitWidth())); 1833400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (!isWrappedSet()) { 184ae5eb7accf65ee94e22b3d235d466d71268f1e83Nick Lewycky if (getLower().sle(getUpper() - 1)) 1853400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getUpper() - 1; 18648a09aec60c5daf67430811e24256d501a576766Nick Lewycky return SignedMax; 1873400e6af6b10acea219c02ac262637220f84218fNick Lewycky } 18848a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (getLower().isNegative() == getUpper().isNegative()) 18948a09aec60c5daf67430811e24256d501a576766Nick Lewycky return SignedMax; 19048a09aec60c5daf67430811e24256d501a576766Nick Lewycky return getUpper() - 1; 1913400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 1923400e6af6b10acea219c02ac262637220f84218fNick Lewycky 1933400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getSignedMin - Return the smallest signed value contained in the 1943400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 1953400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1963400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getSignedMin() const { 197daacf22537e0d140c379a39a11a83d3321395d4dZhou Sheng APInt SignedMin(APInt::getSignedMinValue(getBitWidth())); 1983400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (!isWrappedSet()) { 199ae5eb7accf65ee94e22b3d235d466d71268f1e83Nick Lewycky if (getLower().sle(getUpper() - 1)) 2003400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getLower(); 20148a09aec60c5daf67430811e24256d501a576766Nick Lewycky return SignedMin; 20248a09aec60c5daf67430811e24256d501a576766Nick Lewycky } 20348a09aec60c5daf67430811e24256d501a576766Nick Lewycky if ((getUpper() - 1).slt(getLower())) { 20448a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (getUpper() != SignedMin) 2053400e6af6b10acea219c02ac262637220f84218fNick Lewycky return SignedMin; 2063400e6af6b10acea219c02ac262637220f84218fNick Lewycky } 20748a09aec60c5daf67430811e24256d501a576766Nick Lewycky return getLower(); 2083400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 2093400e6af6b10acea219c02ac262637220f84218fNick Lewycky 210fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// contains - Return true if the specified value is in the set. 211fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// 212a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencerbool ConstantRange::contains(const APInt &V) const { 213a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer if (Lower == Upper) 214a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer return isFullSet(); 215fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 216a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer if (!isWrappedSet()) 217a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer return Lower.ule(V) && V.ult(Upper); 21848a09aec60c5daf67430811e24256d501a576766Nick Lewycky return Lower.ule(V) || V.ult(Upper); 219fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 220645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 221bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky/// contains - Return true if the argument is a subset of this range. 2227f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky/// Two equal sets contain each other. The empty set contained by all other 2237f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky/// sets. 224bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky/// 225bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewyckybool ConstantRange::contains(const ConstantRange &Other) const { 2267f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isFullSet() || Other.isEmptySet()) return true; 2277f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isEmptySet() || Other.isFullSet()) return false; 228bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 229bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (!isWrappedSet()) { 230bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (Other.isWrappedSet()) 231bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return false; 232bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 233bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper); 234bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 235bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 236bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (!Other.isWrappedSet()) 237bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return Other.getUpper().ule(Upper) || 238bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky Lower.ule(Other.getLower()); 239bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 240bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower()); 241bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky} 242bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 243fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// subtract - Subtract the specified constant from the endpoints of this 244fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// constant range. 245581b0d453a63f7f657248f80317976995262be11Reid SpencerConstantRange ConstantRange::subtract(const APInt &Val) const { 246bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width"); 247fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner // If the set is empty or full, don't modify the endpoints. 248663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer if (Lower == Upper) 249663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return *this; 250663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return ConstantRange(Lower - Val, Upper - Val); 251fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 252fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 25362d7afad8faf7a1fbbf3402f8e23ce4ece9ab108Nuno Lopes/// \brief Subtract the specified range from this range (aka relative complement 25462d7afad8faf7a1fbbf3402f8e23ce4ece9ab108Nuno Lopes/// of the sets). 25562d7afad8faf7a1fbbf3402f8e23ce4ece9ab108Nuno LopesConstantRange ConstantRange::difference(const ConstantRange &CR) const { 25662d7afad8faf7a1fbbf3402f8e23ce4ece9ab108Nuno Lopes return intersectWith(CR.inverse()); 25762d7afad8faf7a1fbbf3402f8e23ce4ece9ab108Nuno Lopes} 25862d7afad8faf7a1fbbf3402f8e23ce4ece9ab108Nuno Lopes 2593e051647c079fe29db049646b39611fc0135327dNick Lewycky/// intersectWith - Return the range that results from the intersection of this 2603a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky/// range with another range. The resultant range is guaranteed to include all 2613a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky/// elements contained in both input ranges, and to have the smallest possible 2623a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky/// set size that does so. Because there may be two intersections with the 2633a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky/// same set size, A.intersectWith(B) might not be equal to B.intersectWith(A). 264a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid SpencerConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const { 265bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer assert(getBitWidth() == CR.getBitWidth() && 266bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer "ConstantRange types don't agree!"); 267377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 268377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky // Handle common cases. 269377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if ( isEmptySet() || CR.isFullSet()) return *this; 270377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.isEmptySet() || isFullSet()) return CR; 271377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 272377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (!isWrappedSet() && CR.isWrappedSet()) 2733a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky return CR.intersectWith(*this); 274377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 275377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (!isWrappedSet() && !CR.isWrappedSet()) { 276377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (Lower.ult(CR.Lower)) { 277377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (Upper.ule(CR.Lower)) 278377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(getBitWidth(), false); 279377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 280377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (Upper.ult(CR.Upper)) 281377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(CR.Lower, Upper); 282377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 283377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 28448a09aec60c5daf67430811e24256d501a576766Nick Lewycky } 28548a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (Upper.ult(CR.Upper)) 28648a09aec60c5daf67430811e24256d501a576766Nick Lewycky return *this; 287377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 28848a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (Lower.ult(CR.Upper)) 28948a09aec60c5daf67430811e24256d501a576766Nick Lewycky return ConstantRange(Lower, CR.Upper); 290377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 29148a09aec60c5daf67430811e24256d501a576766Nick Lewycky return ConstantRange(getBitWidth(), false); 292377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 293377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 294377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (isWrappedSet() && !CR.isWrappedSet()) { 295377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Lower.ult(Upper)) { 296377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Upper.ult(Upper)) 297377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 298377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 299fbb7a73631e3c23510abb3904e8ad38c87ff2a24Nuno Lopes if (CR.Upper.ule(Lower)) 300377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(CR.Lower, Upper); 301377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 302377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (getSetSize().ult(CR.getSetSize())) 303377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return *this; 30448a09aec60c5daf67430811e24256d501a576766Nick Lewycky return CR; 30548a09aec60c5daf67430811e24256d501a576766Nick Lewycky } 30648a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (CR.Lower.ult(Lower)) { 307377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Upper.ule(Lower)) 308377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(getBitWidth(), false); 309377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 310377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(Lower, CR.Upper); 311377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 312377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 313377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 314377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 315377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Upper.ult(Upper)) { 316377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Lower.ult(Upper)) { 317377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (getSetSize().ult(CR.getSetSize())) 318377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return *this; 31948a09aec60c5daf67430811e24256d501a576766Nick Lewycky return CR; 320377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 321377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 322377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Lower.ult(Lower)) 323377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(Lower, CR.Upper); 324377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 325377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 32648a09aec60c5daf67430811e24256d501a576766Nick Lewycky } 327532516a87bc57f21e6d99f49548e4c2adf835551Nuno Lopes if (CR.Upper.ule(Lower)) { 328377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Lower.ult(Lower)) 329377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return *this; 330377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 331377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(CR.Lower, Upper); 332377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 333377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (getSetSize().ult(CR.getSetSize())) 334377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return *this; 33548a09aec60c5daf67430811e24256d501a576766Nick Lewycky return CR; 336377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky} 337377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 338377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 3393e051647c079fe29db049646b39611fc0135327dNick Lewycky/// unionWith - Return the range that results from the union of this range with 340645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// another range. The resultant range is guaranteed to include the elements of 3419babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky/// both sets, but may contain more. For example, [3, 9) union [12,15) is 3429babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky/// [3, 15), which includes 9, 10, and 11, which were not included in either 3439babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky/// set before. 344645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 345a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid SpencerConstantRange ConstantRange::unionWith(const ConstantRange &CR) const { 346bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer assert(getBitWidth() == CR.getBitWidth() && 347bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer "ConstantRange types don't agree!"); 348645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 349c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky if ( isFullSet() || CR.isEmptySet()) return *this; 350c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky if (CR.isFullSet() || isEmptySet()) return CR; 351645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 3529babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this); 3539babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3549babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (!isWrappedSet() && !CR.isWrappedSet()) { 3557e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) { 3567e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // If the two ranges are disjoint, find the smaller gap and bridge it. 3577e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; 3587e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (d1.ult(d2)) 3597e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(Lower, CR.Upper); 36048a09aec60c5daf67430811e24256d501a576766Nick Lewycky return ConstantRange(CR.Lower, Upper); 3617e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky } 3627e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky 3637e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky APInt L = Lower, U = Upper; 3649babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (CR.Lower.ult(L)) 3659babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky L = CR.Lower; 3667e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if ((CR.Upper - 1).ugt(U - 1)) 3679babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky U = CR.Upper; 3687e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky 3697e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (L == 0 && U == 0) 3707e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(getBitWidth()); 3717e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky 3727e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(L, U); 3739babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 3749babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3757e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (!CR.isWrappedSet()) { 3767e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ------U L----- and ------U L----- : this 3777e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L--U L--U : CR 3787e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower)) 3799babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky return *this; 3809babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3817e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ------U L----- : this 3827e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L---------U : CR 3837e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) 3849babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky return ConstantRange(getBitWidth()); 3859babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3867e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ----U L---- : this 3877e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L---U : CR 3887e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // <d1> <d2> 3897e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) { 3909babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; 3917e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (d1.ult(d2)) 3927e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(Lower, CR.Upper); 39348a09aec60c5daf67430811e24256d501a576766Nick Lewycky return ConstantRange(CR.Lower, Upper); 3949babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 395c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky 3967e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ----U L----- : this 3977e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L----U : CR 3987e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper)) 3997e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(CR.Lower, Upper); 4009babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 4017e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ------U L---- : this 4027e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L-----U : CR 40348a09aec60c5daf67430811e24256d501a576766Nick Lewycky assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) && 40448a09aec60c5daf67430811e24256d501a576766Nick Lewycky "ConstantRange::unionWith missed a case with one range wrapped"); 40548a09aec60c5daf67430811e24256d501a576766Nick Lewycky return ConstantRange(Lower, CR.Upper); 4069babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 4079babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 4087e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ------U L---- and ------U L---- : this 4097e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // -U L----------- and ------------U L : CR 4107e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper)) 4117e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(getBitWidth()); 4129babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 4137e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky APInt L = Lower, U = Upper; 4147e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Upper.ugt(U)) 4157e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky U = CR.Upper; 4167e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Lower.ult(L)) 4177e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky L = CR.Lower; 418c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky 419c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky return ConstantRange(L, U); 420645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 42196f9d7232c72867ee09641832d2db99f9166d6f0Chris Lattner 422fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// zeroExtend - Return a new range in the specified integer type, which must 423fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// be strictly larger than the current type. The returned range will 424e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer/// correspond to the possible range of values as if the source range had been 425fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// zero extended. 426bb626a6751db9a63d159d32522bdf88cedf46eebReid SpencerConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const { 42732cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false); 42832cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky 429bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer unsigned SrcTySize = getBitWidth(); 430663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer assert(SrcTySize < DstTySize && "Not a value extension"); 431b42729b53a061e2a3def61eb10e2a648cecd60aeNuno Lopes if (isFullSet() || isWrappedSet()) { 43232cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky // Change into [0, 1 << src bit width) 433b42729b53a061e2a3def61eb10e2a648cecd60aeNuno Lopes APInt LowerExt(DstTySize, 0); 434b42729b53a061e2a3def61eb10e2a648cecd60aeNuno Lopes if (!Upper) // special case: [X, 0) -- not really wrapping around 435b42729b53a061e2a3def61eb10e2a648cecd60aeNuno Lopes LowerExt = Lower.zext(DstTySize); 4360a230e0d985625a3909cb78fd867a3abaf434565Benjamin Kramer return ConstantRange(LowerExt, APInt::getOneBitSet(DstTySize, SrcTySize)); 437b42729b53a061e2a3def61eb10e2a648cecd60aeNuno Lopes } 438fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 43940f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize)); 440e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky} 441e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky 442e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky/// signExtend - Return a new range in the specified integer type, which must 443e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky/// be strictly larger than the current type. The returned range will 444e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky/// correspond to the possible range of values as if the source range had been 445e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky/// sign extended. 446e32157c6098ee7536315e9793eed98d21bf71fd0Nick LewyckyConstantRange ConstantRange::signExtend(uint32_t DstTySize) const { 44732cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false); 44832cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky 449e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky unsigned SrcTySize = getBitWidth(); 450e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky assert(SrcTySize < DstTySize && "Not a value extension"); 45132cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky if (isFullSet() || isSignWrappedSet()) { 452e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1), 453ff84de767a9baded740abd1e846938477a4b285aNick Lewycky APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1); 454e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky } 455e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky 45640f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize)); 457fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 458fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 459fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// truncate - Return a new range in the specified integer type, which must be 460fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// strictly smaller than the current type. The returned range will 461e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer/// correspond to the possible range of values as if the source range had been 462fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// truncated to the specified type. 463bb626a6751db9a63d159d32522bdf88cedf46eebReid SpencerConstantRange ConstantRange::truncate(uint32_t DstTySize) const { 464b3ff49e923225d0f7242ef5ac554bdef34c1b216Benjamin Kramer assert(getBitWidth() > DstTySize && "Not a value truncation"); 46555c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes if (isEmptySet()) 46655c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes return ConstantRange(DstTySize, /*isFullSet=*/false); 46755c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes if (isFullSet()) 4687f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(DstTySize, /*isFullSet=*/true); 469fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 47055c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes APInt MaxValue = APInt::getMaxValue(DstTySize).zext(getBitWidth()); 47155c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes APInt MaxBitValue(getBitWidth(), 0); 47255c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes MaxBitValue.setBit(DstTySize); 47355c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes 47455c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes APInt LowerDiv(Lower), UpperDiv(Upper); 47555c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes ConstantRange Union(DstTySize, /*isFullSet=*/false); 47655c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes 47755c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue] 47855c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and 47955c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes // then we do the union with [MaxValue, Upper) 48055c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes if (isWrappedSet()) { 48155c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes // if Upper is greater than Max Value, it covers the whole truncated range. 48255c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes if (Upper.uge(MaxValue)) 48355c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes return ConstantRange(DstTySize, /*isFullSet=*/true); 48455c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes 48555c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize)); 48655c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes UpperDiv = APInt::getMaxValue(getBitWidth()); 48755c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes 48855c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes // Union covers the MaxValue case, so return if the remaining range is just 48955c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes // MaxValue. 49055c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes if (LowerDiv == UpperDiv) 49155c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes return Union; 49255c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes } 49355c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes 49455c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes // Chop off the most significant bits that are past the destination bitwidth. 49555c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes if (LowerDiv.uge(MaxValue)) { 49655c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes APInt Div(getBitWidth(), 0); 49755c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes APInt::udivrem(LowerDiv, MaxBitValue, Div, LowerDiv); 49855c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes UpperDiv = UpperDiv - MaxBitValue * Div; 49955c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes } 50055c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes 50155c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes if (UpperDiv.ule(MaxValue)) 50255c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes return ConstantRange(LowerDiv.trunc(DstTySize), 50355c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes UpperDiv.trunc(DstTySize)).unionWith(Union); 50455c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes 50555c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes // The truncated value wrapps around. Check if we can do better than fullset. 50655c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes APInt UpperModulo = UpperDiv - MaxBitValue; 50755c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes if (UpperModulo.ult(LowerDiv)) 50855c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes return ConstantRange(LowerDiv.trunc(DstTySize), 50955c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes UpperModulo.trunc(DstTySize)).unionWith(Union); 51055c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes 51155c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes return ConstantRange(DstTySize, /*isFullSet=*/true); 512fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 513fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 51495a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes/// zextOrTrunc - make this range have the bit width given by \p DstTySize. The 51595a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes/// value is zero extended, truncated, or left alone to make it that width. 51695a3be0ba44e96308c65c28ee859acc36149ddd8Nuno LopesConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const { 51795a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes unsigned SrcTySize = getBitWidth(); 51895a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes if (SrcTySize > DstTySize) 51995a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return truncate(DstTySize); 52048a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (SrcTySize < DstTySize) 52195a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return zeroExtend(DstTySize); 52248a09aec60c5daf67430811e24256d501a576766Nick Lewycky return *this; 52395a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes} 52495a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes 52595a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes/// sextOrTrunc - make this range have the bit width given by \p DstTySize. The 52695a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes/// value is sign extended, truncated, or left alone to make it that width. 52795a3be0ba44e96308c65c28ee859acc36149ddd8Nuno LopesConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const { 52895a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes unsigned SrcTySize = getBitWidth(); 52995a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes if (SrcTySize > DstTySize) 53095a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return truncate(DstTySize); 53148a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (SrcTySize < DstTySize) 53295a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return signExtend(DstTySize); 53348a09aec60c5daf67430811e24256d501a576766Nick Lewycky return *this; 53495a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes} 53595a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes 536a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 537a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange::add(const ConstantRange &Other) const { 538a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (isEmptySet() || Other.isEmptySet()) 539a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/false); 540cf9e07dea8aad32c5e7e2631d135566b20e1763cNick Lewycky if (isFullSet() || Other.isFullSet()) 541cf9e07dea8aad32c5e7e2631d135566b20e1763cNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 542a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 543a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize(); 544a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt NewLower = getLower() + Other.getLower(); 545a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt NewUpper = getUpper() + Other.getUpper() - 1; 546a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (NewLower == NewUpper) 547a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/true); 548a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 549a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman ConstantRange X = ConstantRange(NewLower, NewUpper); 550a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y)) 551a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman // We've wrapped, therefore, full set. 552a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/true); 553a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 554a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return X; 555a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 556a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 557a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 5587f9ef4bb514d5a28637789d8f397dadd4344dc1bNick LewyckyConstantRange::sub(const ConstantRange &Other) const { 5597f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isEmptySet() || Other.isEmptySet()) 5607f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 5617f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isFullSet() || Other.isFullSet()) 5627f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 5637f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky 5647f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize(); 565e6240e8b83e9bd60e622650e9e801ebc957172b4Nick Lewycky APInt NewLower = getLower() - Other.getUpper() + 1; 566e6240e8b83e9bd60e622650e9e801ebc957172b4Nick Lewycky APInt NewUpper = getUpper() - Other.getLower(); 5677f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (NewLower == NewUpper) 5687f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 5697f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky 5707f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky ConstantRange X = ConstantRange(NewLower, NewUpper); 5717f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y)) 5727f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky // We've wrapped, therefore, full set. 5737f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 5747f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky 5757f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return X; 5767f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky} 5777f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky 5787f9ef4bb514d5a28637789d8f397dadd4344dc1bNick LewyckyConstantRange 579a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange::multiply(const ConstantRange &Other) const { 5808dcc58e6b44fbaab39a24b1f75e67f05275084dcDan Gohman // TODO: If either operand is a single element and the multiply is known to 5818dcc58e6b44fbaab39a24b1f75e67f05275084dcDan Gohman // be non-wrapping, round the result min and max value to the appropriate 5828dcc58e6b44fbaab39a24b1f75e67f05275084dcDan Gohman // multiple of that element. If wrapping is possible, at least adjust the 5838dcc58e6b44fbaab39a24b1f75e67f05275084dcDan Gohman // range according to the greatest power-of-two factor of the single element. 584153f1ebeb8fd394e5b11b27edde9472de0cbb57fDan Gohman 5852ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky if (isEmptySet() || Other.isEmptySet()) 5862ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 5877e733eab2f11fceb24d6b4f25c27d7ba7d92d97eNuno Lopes 588f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky APInt this_min = getUnsignedMin().zext(getBitWidth() * 2); 589f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky APInt this_max = getUnsignedMax().zext(getBitWidth() * 2); 590f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2); 591f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2); 5922ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky 593f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky ConstantRange Result_zext = ConstantRange(this_min * Other_min, 594f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky this_max * Other_max + 1); 5952ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky return Result_zext.truncate(getBitWidth()); 596a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 597a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 598a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 599a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange::smax(const ConstantRange &Other) const { 60038b06447615440f935008a2141bd0a1fe078d437Dan Gohman // X smax Y is: range(smax(X_smin, Y_smin), 60138b06447615440f935008a2141bd0a1fe078d437Dan Gohman // smax(X_smax, Y_smax)) 60238b06447615440f935008a2141bd0a1fe078d437Dan Gohman if (isEmptySet() || Other.isEmptySet()) 60338b06447615440f935008a2141bd0a1fe078d437Dan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/false); 60438b06447615440f935008a2141bd0a1fe078d437Dan Gohman APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin()); 60538b06447615440f935008a2141bd0a1fe078d437Dan Gohman APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1; 60638b06447615440f935008a2141bd0a1fe078d437Dan Gohman if (NewU == NewL) 60738b06447615440f935008a2141bd0a1fe078d437Dan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/true); 60838b06447615440f935008a2141bd0a1fe078d437Dan Gohman return ConstantRange(NewL, NewU); 609a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 610a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 611a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 612a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange::umax(const ConstantRange &Other) const { 613a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman // X umax Y is: range(umax(X_umin, Y_umin), 614a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman // umax(X_umax, Y_umax)) 615a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (isEmptySet() || Other.isEmptySet()) 616a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/false); 617a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); 618a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1; 619a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (NewU == NewL) 620a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/true); 621a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(NewL, NewU); 622a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 623a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 624a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 625956daf0f7f7fa473cf92c8193905a8a441932b69Nick LewyckyConstantRange::udiv(const ConstantRange &RHS) const { 626956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0) 627956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 628956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (RHS.isFullSet()) 629956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 630956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 631956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax()); 632956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 633956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky APInt RHS_umin = RHS.getUnsignedMin(); 634956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (RHS_umin == 0) { 635956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky // We want the lowest value in RHS excluding zero. Usually that would be 1 636956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky // except for a range in the form of [X, 1) in which case it would be X. 637956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (RHS.getUpper() == 1) 638956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky RHS_umin = RHS.getLower(); 639956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky else 640956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky RHS_umin = APInt(getBitWidth(), 1); 641956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky } 642956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 643956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1; 644956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 645956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky // If the LHS is Full and the RHS is a wrapped interval containing 1 then 646956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky // this could occur. 647956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (Lower == Upper) 648956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 649956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 650956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky return ConstantRange(Lower, Upper); 651a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 652a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 65334e992da381bf8b1a9cbcc1bde0b117207809649Nuno LopesConstantRange 654198381e542320265e1c5fed18e938db3563a45bfNick LewyckyConstantRange::binaryAnd(const ConstantRange &Other) const { 655198381e542320265e1c5fed18e938db3563a45bfNick Lewycky if (isEmptySet() || Other.isEmptySet()) 656198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 657198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 658198381e542320265e1c5fed18e938db3563a45bfNick Lewycky // TODO: replace this with something less conservative 659198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 660198381e542320265e1c5fed18e938db3563a45bfNick Lewycky APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax()); 661198381e542320265e1c5fed18e938db3563a45bfNick Lewycky if (umin.isAllOnesValue()) 662198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 663198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(APInt::getNullValue(getBitWidth()), umin + 1); 664198381e542320265e1c5fed18e938db3563a45bfNick Lewycky} 665198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 666198381e542320265e1c5fed18e938db3563a45bfNick LewyckyConstantRange 667198381e542320265e1c5fed18e938db3563a45bfNick LewyckyConstantRange::binaryOr(const ConstantRange &Other) const { 668198381e542320265e1c5fed18e938db3563a45bfNick Lewycky if (isEmptySet() || Other.isEmptySet()) 669198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 670198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 671198381e542320265e1c5fed18e938db3563a45bfNick Lewycky // TODO: replace this with something less conservative 672198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 673198381e542320265e1c5fed18e938db3563a45bfNick Lewycky APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); 674198381e542320265e1c5fed18e938db3563a45bfNick Lewycky if (umax.isMinValue()) 675198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 676198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(umax, APInt::getNullValue(getBitWidth())); 677198381e542320265e1c5fed18e938db3563a45bfNick Lewycky} 678198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 679198381e542320265e1c5fed18e938db3563a45bfNick LewyckyConstantRange 6807f9ef4bb514d5a28637789d8f397dadd4344dc1bNick LewyckyConstantRange::shl(const ConstantRange &Other) const { 6817f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isEmptySet() || Other.isEmptySet()) 6827f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 68334e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 6847f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky APInt min = getUnsignedMin().shl(Other.getUnsignedMin()); 6857f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky APInt max = getUnsignedMax().shl(Other.getUnsignedMax()); 68634e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 68734e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes // there's no overflow! 6884459145c2ccb5d063841a5d8c76b8b8ac9adaf2fNuno Lopes APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros()); 6897f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (Zeros.ugt(Other.getUnsignedMax())) 6907f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(min, max + 1); 69134e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 69234e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes // FIXME: implement the other tricky cases 6937f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 69434e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes} 69534e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 69634e992da381bf8b1a9cbcc1bde0b117207809649Nuno LopesConstantRange 6977f9ef4bb514d5a28637789d8f397dadd4344dc1bNick LewyckyConstantRange::lshr(const ConstantRange &Other) const { 6987f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isEmptySet() || Other.isEmptySet()) 6997f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 70034e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 7017f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()); 7027f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky APInt min = getUnsignedMin().lshr(Other.getUnsignedMax()); 7037f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (min == max + 1) 7047f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 7057f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky 7067f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(min, max + 1); 70734e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes} 70834e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 7099773e45a1e97f5098905bac26b8b8b7c844473f0Owen AndersonConstantRange ConstantRange::inverse() const { 71048a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (isFullSet()) 7117f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 71248a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (isEmptySet()) 7137f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 7149773e45a1e97f5098905bac26b8b8b7c844473f0Owen Anderson return ConstantRange(Upper, Lower); 7159773e45a1e97f5098905bac26b8b8b7c844473f0Owen Anderson} 7169773e45a1e97f5098905bac26b8b8b7c844473f0Owen Anderson 71738b06447615440f935008a2141bd0a1fe078d437Dan Gohman/// print - Print out the bounds to a stream... 718a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman/// 71938b06447615440f935008a2141bd0a1fe078d437Dan Gohmanvoid ConstantRange::print(raw_ostream &OS) const { 720df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman if (isFullSet()) 721df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman OS << "full-set"; 722df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman else if (isEmptySet()) 723df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman OS << "empty-set"; 724df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman else 725df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman OS << "[" << Lower << "," << Upper << ")"; 726a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 727a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 72838b06447615440f935008a2141bd0a1fe078d437Dan Gohman/// dump - Allow printing from a debugger easily... 729a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman/// 73038b06447615440f935008a2141bd0a1fe078d437Dan Gohmanvoid ConstantRange::dump() const { 7317fd5fb4b4755c3df86da5a0ebedf0d328fafbc81David Greene print(dbgs()); 732a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 733