ConstantRange.cpp revision 858143816d43e58b17bfd11cb1b57afbd7f0f893
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 24a09d514b291151ad9c92c9bf8776583de231ded4Frits van Bommel#include "llvm/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/// 417f9ef4bb514d5a28637789d8f397dadd4344dc1bNick LewyckyConstantRange::ConstantRange(const APInt &V) : Lower(V), Upper(V + 1) {} 42645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 4338b06447615440f935008a2141bd0a1fe078d437Dan GohmanConstantRange::ConstantRange(const APInt &L, const APInt &U) : 4438b06447615440f935008a2141bd0a1fe078d437Dan Gohman Lower(L), Upper(U) { 4538b06447615440f935008a2141bd0a1fe078d437Dan Gohman assert(L.getBitWidth() == U.getBitWidth() && 4638b06447615440f935008a2141bd0a1fe078d437Dan Gohman "ConstantRange with unequal bit widths"); 47c125c00e68138b8ae7861b589277a491ee217893Zhou Sheng assert((L != U || (L.isMaxValue() || L.isMinValue())) && 48663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer "Lower == Upper, but they aren't min or max value!"); 49663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer} 50663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer 51bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick LewyckyConstantRange ConstantRange::makeICmpRegion(unsigned Pred, 52bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky const ConstantRange &CR) { 53f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky if (CR.isEmptySet()) 54f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky return CR; 55f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky 56bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky uint32_t W = CR.getBitWidth(); 57bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky switch (Pred) { 58858143816d43e58b17bfd11cb1b57afbd7f0f893Craig Topper default: llvm_unreachable("Invalid ICmp predicate to makeICmpRegion()"); 59a09d514b291151ad9c92c9bf8776583de231ded4Frits van Bommel case CmpInst::ICMP_EQ: 60f067a233562d3cfeb29d0092d1069bb8d25cad31Nick Lewycky return CR; 61a09d514b291151ad9c92c9bf8776583de231ded4Frits van Bommel case CmpInst::ICMP_NE: 62bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (CR.isSingleElement()) 63bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(CR.getUpper(), CR.getLower()); 64bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(W); 65a09d514b291151ad9c92c9bf8776583de231ded4Frits van Bommel case CmpInst::ICMP_ULT: { 66f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky APInt UMax(CR.getUnsignedMax()); 67f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky if (UMax.isMinValue()) 68f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky return ConstantRange(W, /* empty */ false); 69f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky return ConstantRange(APInt::getMinValue(W), UMax); 70f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky } 71a09d514b291151ad9c92c9bf8776583de231ded4Frits van Bommel case CmpInst::ICMP_SLT: { 72f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky APInt SMax(CR.getSignedMax()); 73f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky if (SMax.isMinSignedValue()) 74f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky return ConstantRange(W, /* empty */ false); 75f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky return ConstantRange(APInt::getSignedMinValue(W), SMax); 76f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky } 77a09d514b291151ad9c92c9bf8776583de231ded4Frits van Bommel case CmpInst::ICMP_ULE: { 78bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky APInt UMax(CR.getUnsignedMax()); 79bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (UMax.isMaxValue()) 80bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(W); 81bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(APInt::getMinValue(W), UMax + 1); 82bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 83a09d514b291151ad9c92c9bf8776583de231ded4Frits van Bommel case CmpInst::ICMP_SLE: { 84bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky APInt SMax(CR.getSignedMax()); 85f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky if (SMax.isMaxSignedValue()) 86bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(W); 87bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(APInt::getSignedMinValue(W), SMax + 1); 88bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 89a09d514b291151ad9c92c9bf8776583de231ded4Frits van Bommel case CmpInst::ICMP_UGT: { 90f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky APInt UMin(CR.getUnsignedMin()); 91f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky if (UMin.isMaxValue()) 92f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky return ConstantRange(W, /* empty */ false); 93f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky return ConstantRange(UMin + 1, APInt::getNullValue(W)); 94f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky } 95a09d514b291151ad9c92c9bf8776583de231ded4Frits van Bommel case CmpInst::ICMP_SGT: { 96f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky APInt SMin(CR.getSignedMin()); 97f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky if (SMin.isMaxSignedValue()) 98f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky return ConstantRange(W, /* empty */ false); 99f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky return ConstantRange(SMin + 1, APInt::getSignedMinValue(W)); 100f2d7b7c879548090beae51b21c4b363da7dbbaadNick Lewycky } 101a09d514b291151ad9c92c9bf8776583de231ded4Frits van Bommel case CmpInst::ICMP_UGE: { 102bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky APInt UMin(CR.getUnsignedMin()); 103bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (UMin.isMinValue()) 104bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(W); 105bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(UMin, APInt::getNullValue(W)); 106bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 107a09d514b291151ad9c92c9bf8776583de231ded4Frits van Bommel case CmpInst::ICMP_SGE: { 108bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky APInt SMin(CR.getSignedMin()); 109bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (SMin.isMinSignedValue()) 110bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(W); 111bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return ConstantRange(SMin, APInt::getSignedMinValue(W)); 112bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 113bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 114bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky} 115bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 116645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// isFullSet - Return true if this set contains all of the elements possible 117645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// for this data-type 118645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattnerbool ConstantRange::isFullSet() const { 119c125c00e68138b8ae7861b589277a491ee217893Zhou Sheng return Lower == Upper && Lower.isMaxValue(); 120645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 121fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 122645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// isEmptySet - Return true if this set contains no members. 123645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 124645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattnerbool ConstantRange::isEmptySet() const { 125c125c00e68138b8ae7861b589277a491ee217893Zhou Sheng return Lower == Upper && Lower.isMinValue(); 126645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 127645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 128645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// isWrappedSet - Return true if this set wraps around the top of the range, 129645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// for example: [100, 8) 130645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 131a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencerbool ConstantRange::isWrappedSet() const { 132663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return Lower.ugt(Upper); 133645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 134645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 13532cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky/// isSignWrappedSet - Return true if this set wraps around the INT_MIN of 13632cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky/// its bitwidth, for example: i8 [120, 140). 13732cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky/// 13832cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewyckybool ConstantRange::isSignWrappedSet() const { 13932cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky return contains(APInt::getSignedMaxValue(getBitWidth())) && 14032cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky contains(APInt::getSignedMinValue(getBitWidth())); 14132cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky} 14232cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky 143645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// getSetSize - Return the number of elements in this set. 144645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 145663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid SpencerAPInt ConstantRange::getSetSize() const { 146663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer if (isEmptySet()) 147bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer return APInt(getBitWidth(), 0); 148bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer if (getBitWidth() == 1) { 149645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner if (Lower != Upper) // One of T or F in the set... 150bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer return APInt(2, 1); 151bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer return APInt(2, 2); // Must be full set... 152645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner } 153fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 154645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // Simply subtract the bounds... 155663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return Upper - Lower; 156645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 157645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 1583400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getUnsignedMax - Return the largest unsigned value contained in the 1593400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 1603400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1613400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getUnsignedMax() const { 1623400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (isFullSet() || isWrappedSet()) 1633400e6af6b10acea219c02ac262637220f84218fNick Lewycky return APInt::getMaxValue(getBitWidth()); 16448a09aec60c5daf67430811e24256d501a576766Nick Lewycky return getUpper() - 1; 1653400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 1663400e6af6b10acea219c02ac262637220f84218fNick Lewycky 1673400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getUnsignedMin - Return the smallest unsigned value contained in the 1683400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 1693400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1703400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getUnsignedMin() const { 1713400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (isFullSet() || (isWrappedSet() && getUpper() != 0)) 1723400e6af6b10acea219c02ac262637220f84218fNick Lewycky return APInt::getMinValue(getBitWidth()); 17348a09aec60c5daf67430811e24256d501a576766Nick Lewycky return getLower(); 1743400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 1753400e6af6b10acea219c02ac262637220f84218fNick Lewycky 1763400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getSignedMax - Return the largest signed value contained in the 1773400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 1783400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1793400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getSignedMax() const { 180daacf22537e0d140c379a39a11a83d3321395d4dZhou Sheng APInt SignedMax(APInt::getSignedMaxValue(getBitWidth())); 1813400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (!isWrappedSet()) { 182ae5eb7accf65ee94e22b3d235d466d71268f1e83Nick Lewycky if (getLower().sle(getUpper() - 1)) 1833400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getUpper() - 1; 18448a09aec60c5daf67430811e24256d501a576766Nick Lewycky return SignedMax; 1853400e6af6b10acea219c02ac262637220f84218fNick Lewycky } 18648a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (getLower().isNegative() == getUpper().isNegative()) 18748a09aec60c5daf67430811e24256d501a576766Nick Lewycky return SignedMax; 18848a09aec60c5daf67430811e24256d501a576766Nick Lewycky return getUpper() - 1; 1893400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 1903400e6af6b10acea219c02ac262637220f84218fNick Lewycky 1913400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getSignedMin - Return the smallest signed value contained in the 1923400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 1933400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1943400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getSignedMin() const { 195daacf22537e0d140c379a39a11a83d3321395d4dZhou Sheng APInt SignedMin(APInt::getSignedMinValue(getBitWidth())); 1963400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (!isWrappedSet()) { 197ae5eb7accf65ee94e22b3d235d466d71268f1e83Nick Lewycky if (getLower().sle(getUpper() - 1)) 1983400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getLower(); 19948a09aec60c5daf67430811e24256d501a576766Nick Lewycky return SignedMin; 20048a09aec60c5daf67430811e24256d501a576766Nick Lewycky } 20148a09aec60c5daf67430811e24256d501a576766Nick Lewycky if ((getUpper() - 1).slt(getLower())) { 20248a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (getUpper() != SignedMin) 2033400e6af6b10acea219c02ac262637220f84218fNick Lewycky return SignedMin; 2043400e6af6b10acea219c02ac262637220f84218fNick Lewycky } 20548a09aec60c5daf67430811e24256d501a576766Nick Lewycky return getLower(); 2063400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 2073400e6af6b10acea219c02ac262637220f84218fNick Lewycky 208fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// contains - Return true if the specified value is in the set. 209fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// 210a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencerbool ConstantRange::contains(const APInt &V) const { 211a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer if (Lower == Upper) 212a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer return isFullSet(); 213fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 214a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer if (!isWrappedSet()) 215a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer return Lower.ule(V) && V.ult(Upper); 21648a09aec60c5daf67430811e24256d501a576766Nick Lewycky return Lower.ule(V) || V.ult(Upper); 217fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 218645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 219bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky/// contains - Return true if the argument is a subset of this range. 2207f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky/// Two equal sets contain each other. The empty set contained by all other 2217f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky/// sets. 222bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky/// 223bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewyckybool ConstantRange::contains(const ConstantRange &Other) const { 2247f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isFullSet() || Other.isEmptySet()) return true; 2257f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isEmptySet() || Other.isFullSet()) return false; 226bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 227bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (!isWrappedSet()) { 228bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (Other.isWrappedSet()) 229bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return false; 230bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 231bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper); 232bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 233bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 234bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (!Other.isWrappedSet()) 235bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return Other.getUpper().ule(Upper) || 236bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky Lower.ule(Other.getLower()); 237bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 238bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower()); 239bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky} 240bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 241fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// subtract - Subtract the specified constant from the endpoints of this 242fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// constant range. 243581b0d453a63f7f657248f80317976995262be11Reid SpencerConstantRange ConstantRange::subtract(const APInt &Val) const { 244bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width"); 245fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner // If the set is empty or full, don't modify the endpoints. 246663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer if (Lower == Upper) 247663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return *this; 248663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return ConstantRange(Lower - Val, Upper - Val); 249fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 250fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 2513e051647c079fe29db049646b39611fc0135327dNick Lewycky/// intersectWith - Return the range that results from the intersection of this 2523a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky/// range with another range. The resultant range is guaranteed to include all 2533a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky/// elements contained in both input ranges, and to have the smallest possible 2543a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky/// set size that does so. Because there may be two intersections with the 2553a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky/// same set size, A.intersectWith(B) might not be equal to B.intersectWith(A). 256a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid SpencerConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const { 257bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer assert(getBitWidth() == CR.getBitWidth() && 258bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer "ConstantRange types don't agree!"); 259377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 260377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky // Handle common cases. 261377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if ( isEmptySet() || CR.isFullSet()) return *this; 262377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.isEmptySet() || isFullSet()) return CR; 263377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 264377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (!isWrappedSet() && CR.isWrappedSet()) 2653a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky return CR.intersectWith(*this); 266377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 267377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (!isWrappedSet() && !CR.isWrappedSet()) { 268377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (Lower.ult(CR.Lower)) { 269377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (Upper.ule(CR.Lower)) 270377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(getBitWidth(), false); 271377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 272377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (Upper.ult(CR.Upper)) 273377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(CR.Lower, Upper); 274377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 275377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 27648a09aec60c5daf67430811e24256d501a576766Nick Lewycky } 27748a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (Upper.ult(CR.Upper)) 27848a09aec60c5daf67430811e24256d501a576766Nick Lewycky return *this; 279377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 28048a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (Lower.ult(CR.Upper)) 28148a09aec60c5daf67430811e24256d501a576766Nick Lewycky return ConstantRange(Lower, CR.Upper); 282377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 28348a09aec60c5daf67430811e24256d501a576766Nick Lewycky return ConstantRange(getBitWidth(), false); 284377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 285377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 286377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (isWrappedSet() && !CR.isWrappedSet()) { 287377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Lower.ult(Upper)) { 288377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Upper.ult(Upper)) 289377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 290377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 291377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Upper.ult(Lower)) 292377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(CR.Lower, Upper); 293377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 294377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (getSetSize().ult(CR.getSetSize())) 295377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return *this; 29648a09aec60c5daf67430811e24256d501a576766Nick Lewycky return CR; 29748a09aec60c5daf67430811e24256d501a576766Nick Lewycky } 29848a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (CR.Lower.ult(Lower)) { 299377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Upper.ule(Lower)) 300377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(getBitWidth(), false); 301377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 302377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(Lower, CR.Upper); 303377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 304377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 305377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 306377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 307377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Upper.ult(Upper)) { 308377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Lower.ult(Upper)) { 309377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (getSetSize().ult(CR.getSetSize())) 310377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return *this; 31148a09aec60c5daf67430811e24256d501a576766Nick Lewycky return CR; 312377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 313377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 314377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Lower.ult(Lower)) 315377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(Lower, CR.Upper); 316377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 317377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 31848a09aec60c5daf67430811e24256d501a576766Nick Lewycky } 31948a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (CR.Upper.ult(Lower)) { 320377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Lower.ult(Lower)) 321377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return *this; 322377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 323377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(CR.Lower, Upper); 324377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 325377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (getSetSize().ult(CR.getSetSize())) 326377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return *this; 32748a09aec60c5daf67430811e24256d501a576766Nick Lewycky return CR; 328377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky} 329377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 330377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 3313e051647c079fe29db049646b39611fc0135327dNick Lewycky/// unionWith - Return the range that results from the union of this range with 332645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// another range. The resultant range is guaranteed to include the elements of 3339babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky/// both sets, but may contain more. For example, [3, 9) union [12,15) is 3349babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky/// [3, 15), which includes 9, 10, and 11, which were not included in either 3359babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky/// set before. 336645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 337a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid SpencerConstantRange ConstantRange::unionWith(const ConstantRange &CR) const { 338bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer assert(getBitWidth() == CR.getBitWidth() && 339bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer "ConstantRange types don't agree!"); 340645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 341c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky if ( isFullSet() || CR.isEmptySet()) return *this; 342c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky if (CR.isFullSet() || isEmptySet()) return CR; 343645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 3449babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this); 3459babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3469babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (!isWrappedSet() && !CR.isWrappedSet()) { 3477e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) { 3487e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // If the two ranges are disjoint, find the smaller gap and bridge it. 3497e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; 3507e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (d1.ult(d2)) 3517e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(Lower, CR.Upper); 35248a09aec60c5daf67430811e24256d501a576766Nick Lewycky return ConstantRange(CR.Lower, Upper); 3537e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky } 3547e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky 3557e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky APInt L = Lower, U = Upper; 3569babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (CR.Lower.ult(L)) 3579babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky L = CR.Lower; 3587e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if ((CR.Upper - 1).ugt(U - 1)) 3599babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky U = CR.Upper; 3607e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky 3617e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (L == 0 && U == 0) 3627e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(getBitWidth()); 3637e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky 3647e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(L, U); 3659babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 3669babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3677e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (!CR.isWrappedSet()) { 3687e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ------U L----- and ------U L----- : this 3697e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L--U L--U : CR 3707e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower)) 3719babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky return *this; 3729babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3737e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ------U L----- : this 3747e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L---------U : CR 3757e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) 3769babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky return ConstantRange(getBitWidth()); 3779babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3787e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ----U L---- : this 3797e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L---U : CR 3807e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // <d1> <d2> 3817e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) { 3829babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; 3837e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (d1.ult(d2)) 3847e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(Lower, CR.Upper); 38548a09aec60c5daf67430811e24256d501a576766Nick Lewycky return ConstantRange(CR.Lower, Upper); 3869babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 387c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky 3887e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ----U L----- : this 3897e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L----U : CR 3907e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper)) 3917e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(CR.Lower, Upper); 3929babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3937e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ------U L---- : this 3947e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L-----U : CR 39548a09aec60c5daf67430811e24256d501a576766Nick Lewycky assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) && 39648a09aec60c5daf67430811e24256d501a576766Nick Lewycky "ConstantRange::unionWith missed a case with one range wrapped"); 39748a09aec60c5daf67430811e24256d501a576766Nick Lewycky return ConstantRange(Lower, CR.Upper); 3989babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 3999babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 4007e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ------U L---- and ------U L---- : this 4017e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // -U L----------- and ------------U L : CR 4027e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper)) 4037e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(getBitWidth()); 4049babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 4057e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky APInt L = Lower, U = Upper; 4067e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Upper.ugt(U)) 4077e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky U = CR.Upper; 4087e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Lower.ult(L)) 4097e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky L = CR.Lower; 410c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky 411c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky return ConstantRange(L, U); 412645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 41396f9d7232c72867ee09641832d2db99f9166d6f0Chris Lattner 414fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// zeroExtend - Return a new range in the specified integer type, which must 415fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// be strictly larger than the current type. The returned range will 416e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer/// correspond to the possible range of values as if the source range had been 417fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// zero extended. 418bb626a6751db9a63d159d32522bdf88cedf46eebReid SpencerConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const { 41932cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false); 42032cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky 421bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer unsigned SrcTySize = getBitWidth(); 422663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer assert(SrcTySize < DstTySize && "Not a value extension"); 42332cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky if (isFullSet() || isWrappedSet()) 42432cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky // Change into [0, 1 << src bit width) 425dc5c1597014fa5c47c94db2b9fd424d2266053dbReid Spencer return ConstantRange(APInt(DstTySize,0), APInt(DstTySize,1).shl(SrcTySize)); 426fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 42740f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize)); 428e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky} 429e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky 430e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky/// signExtend - Return a new range in the specified integer type, which must 431e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky/// be strictly larger than the current type. The returned range will 432e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky/// correspond to the possible range of values as if the source range had been 433e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky/// sign extended. 434e32157c6098ee7536315e9793eed98d21bf71fd0Nick LewyckyConstantRange ConstantRange::signExtend(uint32_t DstTySize) const { 43532cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false); 43632cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky 437e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky unsigned SrcTySize = getBitWidth(); 438e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky assert(SrcTySize < DstTySize && "Not a value extension"); 43932cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky if (isFullSet() || isSignWrappedSet()) { 440e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1), 441ff84de767a9baded740abd1e846938477a4b285aNick Lewycky APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1); 442e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky } 443e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky 44440f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize)); 445fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 446fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 447fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// truncate - Return a new range in the specified integer type, which must be 448fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// strictly smaller than the current type. The returned range will 449e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer/// correspond to the possible range of values as if the source range had been 450fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// truncated to the specified type. 451bb626a6751db9a63d159d32522bdf88cedf46eebReid SpencerConstantRange ConstantRange::truncate(uint32_t DstTySize) const { 452b3ff49e923225d0f7242ef5ac554bdef34c1b216Benjamin Kramer assert(getBitWidth() > DstTySize && "Not a value truncation"); 453b3ff49e923225d0f7242ef5ac554bdef34c1b216Benjamin Kramer if (isFullSet() || getSetSize().getActiveBits() > DstTySize) 4547f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(DstTySize, /*isFullSet=*/true); 455fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 45640f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad return ConstantRange(Lower.trunc(DstTySize), Upper.trunc(DstTySize)); 457fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 458fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 45995a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes/// zextOrTrunc - make this range have the bit width given by \p DstTySize. The 46095a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes/// value is zero extended, truncated, or left alone to make it that width. 46195a3be0ba44e96308c65c28ee859acc36149ddd8Nuno LopesConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const { 46295a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes unsigned SrcTySize = getBitWidth(); 46395a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes if (SrcTySize > DstTySize) 46495a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return truncate(DstTySize); 46548a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (SrcTySize < DstTySize) 46695a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return zeroExtend(DstTySize); 46748a09aec60c5daf67430811e24256d501a576766Nick Lewycky return *this; 46895a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes} 46995a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes 47095a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes/// sextOrTrunc - make this range have the bit width given by \p DstTySize. The 47195a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes/// value is sign extended, truncated, or left alone to make it that width. 47295a3be0ba44e96308c65c28ee859acc36149ddd8Nuno LopesConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const { 47395a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes unsigned SrcTySize = getBitWidth(); 47495a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes if (SrcTySize > DstTySize) 47595a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return truncate(DstTySize); 47648a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (SrcTySize < DstTySize) 47795a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return signExtend(DstTySize); 47848a09aec60c5daf67430811e24256d501a576766Nick Lewycky return *this; 47995a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes} 48095a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes 481a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 482a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange::add(const ConstantRange &Other) const { 483a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (isEmptySet() || Other.isEmptySet()) 484a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/false); 485cf9e07dea8aad32c5e7e2631d135566b20e1763cNick Lewycky if (isFullSet() || Other.isFullSet()) 486cf9e07dea8aad32c5e7e2631d135566b20e1763cNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 487a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 488a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize(); 489a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt NewLower = getLower() + Other.getLower(); 490a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt NewUpper = getUpper() + Other.getUpper() - 1; 491a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (NewLower == NewUpper) 492a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/true); 493a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 494a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman ConstantRange X = ConstantRange(NewLower, NewUpper); 495a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y)) 496a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman // We've wrapped, therefore, full set. 497a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/true); 498a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 499a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return X; 500a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 501a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 502a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 5037f9ef4bb514d5a28637789d8f397dadd4344dc1bNick LewyckyConstantRange::sub(const ConstantRange &Other) const { 5047f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isEmptySet() || Other.isEmptySet()) 5057f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 5067f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isFullSet() || Other.isFullSet()) 5077f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 5087f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky 5097f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize(); 510e6240e8b83e9bd60e622650e9e801ebc957172b4Nick Lewycky APInt NewLower = getLower() - Other.getUpper() + 1; 511e6240e8b83e9bd60e622650e9e801ebc957172b4Nick Lewycky APInt NewUpper = getUpper() - Other.getLower(); 5127f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (NewLower == NewUpper) 5137f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 5147f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky 5157f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky ConstantRange X = ConstantRange(NewLower, NewUpper); 5167f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y)) 5177f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky // We've wrapped, therefore, full set. 5187f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 5197f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky 5207f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return X; 5217f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky} 5227f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky 5237f9ef4bb514d5a28637789d8f397dadd4344dc1bNick LewyckyConstantRange 524a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange::multiply(const ConstantRange &Other) const { 5258dcc58e6b44fbaab39a24b1f75e67f05275084dcDan Gohman // TODO: If either operand is a single element and the multiply is known to 5268dcc58e6b44fbaab39a24b1f75e67f05275084dcDan Gohman // be non-wrapping, round the result min and max value to the appropriate 5278dcc58e6b44fbaab39a24b1f75e67f05275084dcDan Gohman // multiple of that element. If wrapping is possible, at least adjust the 5288dcc58e6b44fbaab39a24b1f75e67f05275084dcDan Gohman // range according to the greatest power-of-two factor of the single element. 529153f1ebeb8fd394e5b11b27edde9472de0cbb57fDan Gohman 5302ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky if (isEmptySet() || Other.isEmptySet()) 5312ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 5322ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky if (isFullSet() || Other.isFullSet()) 5332ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 5342ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky 535f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky APInt this_min = getUnsignedMin().zext(getBitWidth() * 2); 536f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky APInt this_max = getUnsignedMax().zext(getBitWidth() * 2); 537f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2); 538f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2); 5392ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky 540f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky ConstantRange Result_zext = ConstantRange(this_min * Other_min, 541f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky this_max * Other_max + 1); 5422ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky return Result_zext.truncate(getBitWidth()); 543a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 544a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 545a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 546a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange::smax(const ConstantRange &Other) const { 54738b06447615440f935008a2141bd0a1fe078d437Dan Gohman // X smax Y is: range(smax(X_smin, Y_smin), 54838b06447615440f935008a2141bd0a1fe078d437Dan Gohman // smax(X_smax, Y_smax)) 54938b06447615440f935008a2141bd0a1fe078d437Dan Gohman if (isEmptySet() || Other.isEmptySet()) 55038b06447615440f935008a2141bd0a1fe078d437Dan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/false); 55138b06447615440f935008a2141bd0a1fe078d437Dan Gohman APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin()); 55238b06447615440f935008a2141bd0a1fe078d437Dan Gohman APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1; 55338b06447615440f935008a2141bd0a1fe078d437Dan Gohman if (NewU == NewL) 55438b06447615440f935008a2141bd0a1fe078d437Dan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/true); 55538b06447615440f935008a2141bd0a1fe078d437Dan Gohman return ConstantRange(NewL, NewU); 556a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 557a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 558a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 559a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange::umax(const ConstantRange &Other) const { 560a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman // X umax Y is: range(umax(X_umin, Y_umin), 561a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman // umax(X_umax, Y_umax)) 562a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (isEmptySet() || Other.isEmptySet()) 563a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/false); 564a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); 565a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1; 566a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (NewU == NewL) 567a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/true); 568a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(NewL, NewU); 569a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 570a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 571a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 572956daf0f7f7fa473cf92c8193905a8a441932b69Nick LewyckyConstantRange::udiv(const ConstantRange &RHS) const { 573956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0) 574956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 575956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (RHS.isFullSet()) 576956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 577956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 578956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax()); 579956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 580956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky APInt RHS_umin = RHS.getUnsignedMin(); 581956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (RHS_umin == 0) { 582956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky // We want the lowest value in RHS excluding zero. Usually that would be 1 583956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky // except for a range in the form of [X, 1) in which case it would be X. 584956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (RHS.getUpper() == 1) 585956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky RHS_umin = RHS.getLower(); 586956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky else 587956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky RHS_umin = APInt(getBitWidth(), 1); 588956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky } 589956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 590956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1; 591956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 592956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky // If the LHS is Full and the RHS is a wrapped interval containing 1 then 593956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky // this could occur. 594956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (Lower == Upper) 595956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 596956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 597956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky return ConstantRange(Lower, Upper); 598a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 599a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 60034e992da381bf8b1a9cbcc1bde0b117207809649Nuno LopesConstantRange 601198381e542320265e1c5fed18e938db3563a45bfNick LewyckyConstantRange::binaryAnd(const ConstantRange &Other) const { 602198381e542320265e1c5fed18e938db3563a45bfNick Lewycky if (isEmptySet() || Other.isEmptySet()) 603198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 604198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 605198381e542320265e1c5fed18e938db3563a45bfNick Lewycky // TODO: replace this with something less conservative 606198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 607198381e542320265e1c5fed18e938db3563a45bfNick Lewycky APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax()); 608198381e542320265e1c5fed18e938db3563a45bfNick Lewycky if (umin.isAllOnesValue()) 609198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 610198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(APInt::getNullValue(getBitWidth()), umin + 1); 611198381e542320265e1c5fed18e938db3563a45bfNick Lewycky} 612198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 613198381e542320265e1c5fed18e938db3563a45bfNick LewyckyConstantRange 614198381e542320265e1c5fed18e938db3563a45bfNick LewyckyConstantRange::binaryOr(const ConstantRange &Other) const { 615198381e542320265e1c5fed18e938db3563a45bfNick Lewycky if (isEmptySet() || Other.isEmptySet()) 616198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 617198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 618198381e542320265e1c5fed18e938db3563a45bfNick Lewycky // TODO: replace this with something less conservative 619198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 620198381e542320265e1c5fed18e938db3563a45bfNick Lewycky APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); 621198381e542320265e1c5fed18e938db3563a45bfNick Lewycky if (umax.isMinValue()) 622198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 623198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(umax, APInt::getNullValue(getBitWidth())); 624198381e542320265e1c5fed18e938db3563a45bfNick Lewycky} 625198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 626198381e542320265e1c5fed18e938db3563a45bfNick LewyckyConstantRange 6277f9ef4bb514d5a28637789d8f397dadd4344dc1bNick LewyckyConstantRange::shl(const ConstantRange &Other) const { 6287f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isEmptySet() || Other.isEmptySet()) 6297f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 63034e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 6317f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky APInt min = getUnsignedMin().shl(Other.getUnsignedMin()); 6327f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky APInt max = getUnsignedMax().shl(Other.getUnsignedMax()); 63334e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 63434e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes // there's no overflow! 6354459145c2ccb5d063841a5d8c76b8b8ac9adaf2fNuno Lopes APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros()); 6367f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (Zeros.ugt(Other.getUnsignedMax())) 6377f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(min, max + 1); 63834e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 63934e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes // FIXME: implement the other tricky cases 6407f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 64134e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes} 64234e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 64334e992da381bf8b1a9cbcc1bde0b117207809649Nuno LopesConstantRange 6447f9ef4bb514d5a28637789d8f397dadd4344dc1bNick LewyckyConstantRange::lshr(const ConstantRange &Other) const { 6457f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isEmptySet() || Other.isEmptySet()) 6467f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 64734e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 6487f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()); 6497f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky APInt min = getUnsignedMin().lshr(Other.getUnsignedMax()); 6507f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (min == max + 1) 6517f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 6527f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky 6537f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(min, max + 1); 65434e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes} 65534e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 6569773e45a1e97f5098905bac26b8b8b7c844473f0Owen AndersonConstantRange ConstantRange::inverse() const { 65748a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (isFullSet()) 6587f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 65948a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (isEmptySet()) 6607f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 6619773e45a1e97f5098905bac26b8b8b7c844473f0Owen Anderson return ConstantRange(Upper, Lower); 6629773e45a1e97f5098905bac26b8b8b7c844473f0Owen Anderson} 6639773e45a1e97f5098905bac26b8b8b7c844473f0Owen Anderson 66438b06447615440f935008a2141bd0a1fe078d437Dan Gohman/// print - Print out the bounds to a stream... 665a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman/// 66638b06447615440f935008a2141bd0a1fe078d437Dan Gohmanvoid ConstantRange::print(raw_ostream &OS) const { 667df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman if (isFullSet()) 668df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman OS << "full-set"; 669df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman else if (isEmptySet()) 670df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman OS << "empty-set"; 671df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman else 672df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman OS << "[" << Lower << "," << Upper << ")"; 673a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 674a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 67538b06447615440f935008a2141bd0a1fe078d437Dan Gohman/// dump - Allow printing from a debugger easily... 676a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman/// 67738b06447615440f935008a2141bd0a1fe078d437Dan Gohmanvoid ConstantRange::dump() const { 6787fd5fb4b4755c3df86da5a0ebedf0d328fafbc81David Greene print(dbgs()); 679a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 680