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" 2536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/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) 4236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines : Lower(std::move(V)), Upper(Lower + 1) {} 43645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 44318b7cc7f10d41370929ff93274de29c11f87b81Benjamin KramerConstantRange::ConstantRange(APIntMoveTy L, APIntMoveTy U) 4536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines : Lower(std::move(L)), Upper(std::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 { 1475d2fada44ce77c6db15173a8107bf253c2293170Nuno Lopes if (isFullSet()) { 1485d2fada44ce77c6db15173a8107bf253c2293170Nuno Lopes APInt Size(getBitWidth()+1, 0); 1495d2fada44ce77c6db15173a8107bf253c2293170Nuno Lopes Size.setBit(getBitWidth()); 1505d2fada44ce77c6db15173a8107bf253c2293170Nuno Lopes return Size; 151645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner } 152fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1535d2fada44ce77c6db15173a8107bf253c2293170Nuno Lopes // This is also correct for wrapped sets. 154367308f798338e162b4ab76efa785caa847487c0Nuno Lopes return (Upper - Lower).zext(getBitWidth()+1); 155645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 156645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 1573400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getUnsignedMax - Return the largest unsigned value contained in the 1583400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 1593400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1603400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getUnsignedMax() const { 1613400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (isFullSet() || isWrappedSet()) 1623400e6af6b10acea219c02ac262637220f84218fNick Lewycky return APInt::getMaxValue(getBitWidth()); 16348a09aec60c5daf67430811e24256d501a576766Nick Lewycky return getUpper() - 1; 1643400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 1653400e6af6b10acea219c02ac262637220f84218fNick Lewycky 1663400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getUnsignedMin - Return the smallest unsigned value contained in the 1673400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 1683400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1693400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getUnsignedMin() const { 1703400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (isFullSet() || (isWrappedSet() && getUpper() != 0)) 1713400e6af6b10acea219c02ac262637220f84218fNick Lewycky return APInt::getMinValue(getBitWidth()); 17248a09aec60c5daf67430811e24256d501a576766Nick Lewycky return getLower(); 1733400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 1743400e6af6b10acea219c02ac262637220f84218fNick Lewycky 1753400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getSignedMax - Return the largest signed value contained in the 1763400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 1773400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1783400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getSignedMax() const { 179daacf22537e0d140c379a39a11a83d3321395d4dZhou Sheng APInt SignedMax(APInt::getSignedMaxValue(getBitWidth())); 1803400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (!isWrappedSet()) { 181ae5eb7accf65ee94e22b3d235d466d71268f1e83Nick Lewycky if (getLower().sle(getUpper() - 1)) 1823400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getUpper() - 1; 18348a09aec60c5daf67430811e24256d501a576766Nick Lewycky return SignedMax; 1843400e6af6b10acea219c02ac262637220f84218fNick Lewycky } 18548a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (getLower().isNegative() == getUpper().isNegative()) 18648a09aec60c5daf67430811e24256d501a576766Nick Lewycky return SignedMax; 18748a09aec60c5daf67430811e24256d501a576766Nick Lewycky return getUpper() - 1; 1883400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 1893400e6af6b10acea219c02ac262637220f84218fNick Lewycky 1903400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getSignedMin - Return the smallest signed value contained in the 1913400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 1923400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1933400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getSignedMin() const { 194daacf22537e0d140c379a39a11a83d3321395d4dZhou Sheng APInt SignedMin(APInt::getSignedMinValue(getBitWidth())); 1953400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (!isWrappedSet()) { 196ae5eb7accf65ee94e22b3d235d466d71268f1e83Nick Lewycky if (getLower().sle(getUpper() - 1)) 1973400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getLower(); 19848a09aec60c5daf67430811e24256d501a576766Nick Lewycky return SignedMin; 19948a09aec60c5daf67430811e24256d501a576766Nick Lewycky } 20048a09aec60c5daf67430811e24256d501a576766Nick Lewycky if ((getUpper() - 1).slt(getLower())) { 20148a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (getUpper() != SignedMin) 2023400e6af6b10acea219c02ac262637220f84218fNick Lewycky return SignedMin; 2033400e6af6b10acea219c02ac262637220f84218fNick Lewycky } 20448a09aec60c5daf67430811e24256d501a576766Nick Lewycky return getLower(); 2053400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 2063400e6af6b10acea219c02ac262637220f84218fNick Lewycky 207fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// contains - Return true if the specified value is in the set. 208fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// 209a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencerbool ConstantRange::contains(const APInt &V) const { 210a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer if (Lower == Upper) 211a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer return isFullSet(); 212fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 213a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer if (!isWrappedSet()) 214a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer return Lower.ule(V) && V.ult(Upper); 21548a09aec60c5daf67430811e24256d501a576766Nick Lewycky return Lower.ule(V) || V.ult(Upper); 216fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 217645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 218bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky/// contains - Return true if the argument is a subset of this range. 2197f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky/// Two equal sets contain each other. The empty set contained by all other 2207f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky/// sets. 221bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky/// 222bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewyckybool ConstantRange::contains(const ConstantRange &Other) const { 2237f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isFullSet() || Other.isEmptySet()) return true; 2247f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isEmptySet() || Other.isFullSet()) return false; 225bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 226bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (!isWrappedSet()) { 227bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (Other.isWrappedSet()) 228bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return false; 229bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 230bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper); 231bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky } 232bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 233bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky if (!Other.isWrappedSet()) 234bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return Other.getUpper().ule(Upper) || 235bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky Lower.ule(Other.getLower()); 236bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 237bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower()); 238bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky} 239bf8c7f0adf90c8271c790be9922a2f97d19d4c01Nick Lewycky 240fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// subtract - Subtract the specified constant from the endpoints of this 241fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// constant range. 242581b0d453a63f7f657248f80317976995262be11Reid SpencerConstantRange ConstantRange::subtract(const APInt &Val) const { 243bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width"); 244fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner // If the set is empty or full, don't modify the endpoints. 245663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer if (Lower == Upper) 246663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return *this; 247663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return ConstantRange(Lower - Val, Upper - Val); 248fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 249fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 25062d7afad8faf7a1fbbf3402f8e23ce4ece9ab108Nuno Lopes/// \brief Subtract the specified range from this range (aka relative complement 25162d7afad8faf7a1fbbf3402f8e23ce4ece9ab108Nuno Lopes/// of the sets). 25262d7afad8faf7a1fbbf3402f8e23ce4ece9ab108Nuno LopesConstantRange ConstantRange::difference(const ConstantRange &CR) const { 25362d7afad8faf7a1fbbf3402f8e23ce4ece9ab108Nuno Lopes return intersectWith(CR.inverse()); 25462d7afad8faf7a1fbbf3402f8e23ce4ece9ab108Nuno Lopes} 25562d7afad8faf7a1fbbf3402f8e23ce4ece9ab108Nuno Lopes 2563e051647c079fe29db049646b39611fc0135327dNick Lewycky/// intersectWith - Return the range that results from the intersection of this 2573a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky/// range with another range. The resultant range is guaranteed to include all 2583a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky/// elements contained in both input ranges, and to have the smallest possible 2593a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky/// set size that does so. Because there may be two intersections with the 2603a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky/// same set size, A.intersectWith(B) might not be equal to B.intersectWith(A). 261a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid SpencerConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const { 262bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer assert(getBitWidth() == CR.getBitWidth() && 263bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer "ConstantRange types don't agree!"); 264377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 265377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky // Handle common cases. 266377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if ( isEmptySet() || CR.isFullSet()) return *this; 267377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.isEmptySet() || isFullSet()) return CR; 268377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 269377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (!isWrappedSet() && CR.isWrappedSet()) 2703a4a884c1618d94202ee714ea5c899cd80d1c536Nick Lewycky return CR.intersectWith(*this); 271377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 272377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (!isWrappedSet() && !CR.isWrappedSet()) { 273377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (Lower.ult(CR.Lower)) { 274377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (Upper.ule(CR.Lower)) 275377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(getBitWidth(), false); 276377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 277377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (Upper.ult(CR.Upper)) 278377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(CR.Lower, Upper); 279377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 280377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 28148a09aec60c5daf67430811e24256d501a576766Nick Lewycky } 28248a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (Upper.ult(CR.Upper)) 28348a09aec60c5daf67430811e24256d501a576766Nick Lewycky return *this; 284377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 28548a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (Lower.ult(CR.Upper)) 28648a09aec60c5daf67430811e24256d501a576766Nick Lewycky return ConstantRange(Lower, CR.Upper); 287377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 28848a09aec60c5daf67430811e24256d501a576766Nick Lewycky return ConstantRange(getBitWidth(), false); 289377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 290377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 291377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (isWrappedSet() && !CR.isWrappedSet()) { 292377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Lower.ult(Upper)) { 293377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Upper.ult(Upper)) 294377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 295377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 296fbb7a73631e3c23510abb3904e8ad38c87ff2a24Nuno Lopes if (CR.Upper.ule(Lower)) 297377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(CR.Lower, Upper); 298377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 299377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (getSetSize().ult(CR.getSetSize())) 300377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return *this; 30148a09aec60c5daf67430811e24256d501a576766Nick Lewycky return CR; 30248a09aec60c5daf67430811e24256d501a576766Nick Lewycky } 30348a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (CR.Lower.ult(Lower)) { 304377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Upper.ule(Lower)) 305377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(getBitWidth(), false); 306377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 307377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(Lower, CR.Upper); 308377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 309377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 310377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 311377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 312377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Upper.ult(Upper)) { 313377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Lower.ult(Upper)) { 314377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (getSetSize().ult(CR.getSetSize())) 315377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return *this; 31648a09aec60c5daf67430811e24256d501a576766Nick Lewycky return CR; 317377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 318377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 319377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Lower.ult(Lower)) 320377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(Lower, CR.Upper); 321377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 322377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return CR; 32348a09aec60c5daf67430811e24256d501a576766Nick Lewycky } 324532516a87bc57f21e6d99f49548e4c2adf835551Nuno Lopes if (CR.Upper.ule(Lower)) { 325377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (CR.Lower.ult(Lower)) 326377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return *this; 327377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 328377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return ConstantRange(CR.Lower, Upper); 329377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky } 330377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky if (getSetSize().ult(CR.getSetSize())) 331377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky return *this; 33248a09aec60c5daf67430811e24256d501a576766Nick Lewycky return CR; 333377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky} 334377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 335377b1190cbcf99e9298300d890c4b744dd2ed2c7Nick Lewycky 3363e051647c079fe29db049646b39611fc0135327dNick Lewycky/// unionWith - Return the range that results from the union of this range with 337645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// another range. The resultant range is guaranteed to include the elements of 3389babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky/// both sets, but may contain more. For example, [3, 9) union [12,15) is 3399babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky/// [3, 15), which includes 9, 10, and 11, which were not included in either 3409babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky/// set before. 341645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 342a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid SpencerConstantRange ConstantRange::unionWith(const ConstantRange &CR) const { 343bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer assert(getBitWidth() == CR.getBitWidth() && 344bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer "ConstantRange types don't agree!"); 345645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 346c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky if ( isFullSet() || CR.isEmptySet()) return *this; 347c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky if (CR.isFullSet() || isEmptySet()) return CR; 348645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 3499babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this); 3509babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3519babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (!isWrappedSet() && !CR.isWrappedSet()) { 3527e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) { 3537e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // If the two ranges are disjoint, find the smaller gap and bridge it. 3547e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; 3557e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (d1.ult(d2)) 3567e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(Lower, CR.Upper); 35748a09aec60c5daf67430811e24256d501a576766Nick Lewycky return ConstantRange(CR.Lower, Upper); 3587e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky } 3597e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky 3607e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky APInt L = Lower, U = Upper; 3619babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (CR.Lower.ult(L)) 3629babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky L = CR.Lower; 3637e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if ((CR.Upper - 1).ugt(U - 1)) 3649babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky U = CR.Upper; 3657e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky 3667e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (L == 0 && U == 0) 3677e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(getBitWidth()); 3687e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky 3697e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(L, U); 3709babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 3719babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3727e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (!CR.isWrappedSet()) { 3737e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ------U L----- and ------U L----- : this 3747e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L--U L--U : CR 3757e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower)) 3769babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky return *this; 3779babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3787e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ------U L----- : this 3797e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L---------U : CR 3807e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) 3819babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky return ConstantRange(getBitWidth()); 3829babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3837e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ----U L---- : this 3847e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L---U : CR 3857e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // <d1> <d2> 3867e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) { 3879babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; 3887e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (d1.ult(d2)) 3897e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(Lower, CR.Upper); 39048a09aec60c5daf67430811e24256d501a576766Nick Lewycky return ConstantRange(CR.Lower, Upper); 3919babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 392c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky 3937e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ----U L----- : this 3947e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L----U : CR 3957e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper)) 3967e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(CR.Lower, Upper); 3979babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3987e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ------U L---- : this 3997e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // L-----U : CR 40048a09aec60c5daf67430811e24256d501a576766Nick Lewycky assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) && 40148a09aec60c5daf67430811e24256d501a576766Nick Lewycky "ConstantRange::unionWith missed a case with one range wrapped"); 40248a09aec60c5daf67430811e24256d501a576766Nick Lewycky return ConstantRange(Lower, CR.Upper); 4039babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 4049babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 4057e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // ------U L---- and ------U L---- : this 4067e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky // -U L----------- and ------------U L : CR 4077e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper)) 4087e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky return ConstantRange(getBitWidth()); 4099babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 4107e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky APInt L = Lower, U = Upper; 4117e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Upper.ugt(U)) 4127e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky U = CR.Upper; 4137e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky if (CR.Lower.ult(L)) 4147e7dc45eb15d3739564f2a63ab1c468c57d94ff8Nick Lewycky L = CR.Lower; 415c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky 416c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky return ConstantRange(L, U); 417645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 41896f9d7232c72867ee09641832d2db99f9166d6f0Chris Lattner 419fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// zeroExtend - Return a new range in the specified integer type, which must 420fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// be strictly larger than the current type. The returned range will 421e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer/// correspond to the possible range of values as if the source range had been 422fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// zero extended. 423bb626a6751db9a63d159d32522bdf88cedf46eebReid SpencerConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const { 42432cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false); 42532cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky 426bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer unsigned SrcTySize = getBitWidth(); 427663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer assert(SrcTySize < DstTySize && "Not a value extension"); 428b42729b53a061e2a3def61eb10e2a648cecd60aeNuno Lopes if (isFullSet() || isWrappedSet()) { 42932cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky // Change into [0, 1 << src bit width) 430b42729b53a061e2a3def61eb10e2a648cecd60aeNuno Lopes APInt LowerExt(DstTySize, 0); 431b42729b53a061e2a3def61eb10e2a648cecd60aeNuno Lopes if (!Upper) // special case: [X, 0) -- not really wrapping around 432b42729b53a061e2a3def61eb10e2a648cecd60aeNuno Lopes LowerExt = Lower.zext(DstTySize); 4330a230e0d985625a3909cb78fd867a3abaf434565Benjamin Kramer return ConstantRange(LowerExt, APInt::getOneBitSet(DstTySize, SrcTySize)); 434b42729b53a061e2a3def61eb10e2a648cecd60aeNuno Lopes } 435fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 43640f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize)); 437e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky} 438e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky 439e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky/// signExtend - Return a new range in the specified integer type, which must 440e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky/// be strictly larger than the current type. The returned range will 441e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky/// correspond to the possible range of values as if the source range had been 442e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky/// sign extended. 443e32157c6098ee7536315e9793eed98d21bf71fd0Nick LewyckyConstantRange ConstantRange::signExtend(uint32_t DstTySize) const { 44432cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false); 44532cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky 446e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky unsigned SrcTySize = getBitWidth(); 447e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky assert(SrcTySize < DstTySize && "Not a value extension"); 448d3b64efcb33415e980035371b3e8de1e501a6f12Nuno Lopes 449d3b64efcb33415e980035371b3e8de1e501a6f12Nuno Lopes // special case: [X, INT_MIN) -- not really wrapping around 4507de1b3bd458c33949b9b3f7eb1b9e0c07cfdf65aNuno Lopes if (Upper.isMinSignedValue()) 451d3b64efcb33415e980035371b3e8de1e501a6f12Nuno Lopes return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize)); 452d3b64efcb33415e980035371b3e8de1e501a6f12Nuno Lopes 45332cda119ef63ae1f1ee4b60e1d9e4a5ea8e00604Nick Lewycky if (isFullSet() || isSignWrappedSet()) { 454e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1), 455ff84de767a9baded740abd1e846938477a4b285aNick Lewycky APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1); 456e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky } 457e32157c6098ee7536315e9793eed98d21bf71fd0Nick Lewycky 45840f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize)); 459fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 460fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 461fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// truncate - Return a new range in the specified integer type, which must be 462fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// strictly smaller than the current type. The returned range will 463e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer/// correspond to the possible range of values as if the source range had been 464fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// truncated to the specified type. 465bb626a6751db9a63d159d32522bdf88cedf46eebReid SpencerConstantRange ConstantRange::truncate(uint32_t DstTySize) const { 466b3ff49e923225d0f7242ef5ac554bdef34c1b216Benjamin Kramer assert(getBitWidth() > DstTySize && "Not a value truncation"); 46755c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes if (isEmptySet()) 46855c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes return ConstantRange(DstTySize, /*isFullSet=*/false); 46955c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes if (isFullSet()) 4707f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(DstTySize, /*isFullSet=*/true); 471fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 47255c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes APInt MaxValue = APInt::getMaxValue(DstTySize).zext(getBitWidth()); 47355c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes APInt MaxBitValue(getBitWidth(), 0); 47455c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes MaxBitValue.setBit(DstTySize); 47555c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes 47655c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes APInt LowerDiv(Lower), UpperDiv(Upper); 47755c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes ConstantRange Union(DstTySize, /*isFullSet=*/false); 47855c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes 47955c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue] 48055c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and 48155c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes // then we do the union with [MaxValue, Upper) 48255c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes if (isWrappedSet()) { 48355c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes // if Upper is greater than Max Value, it covers the whole truncated range. 48455c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes if (Upper.uge(MaxValue)) 48555c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes return ConstantRange(DstTySize, /*isFullSet=*/true); 48655c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes 48755c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize)); 48855c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes UpperDiv = APInt::getMaxValue(getBitWidth()); 48955c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes 49055c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes // Union covers the MaxValue case, so return if the remaining range is just 49155c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes // MaxValue. 49255c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes if (LowerDiv == UpperDiv) 49355c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes return Union; 49455c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes } 49555c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes 49655c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes // Chop off the most significant bits that are past the destination bitwidth. 49755c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes if (LowerDiv.uge(MaxValue)) { 49855c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes APInt Div(getBitWidth(), 0); 49955c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes APInt::udivrem(LowerDiv, MaxBitValue, Div, LowerDiv); 50055c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes UpperDiv = UpperDiv - MaxBitValue * Div; 50155c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes } 50255c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes 50355c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes if (UpperDiv.ule(MaxValue)) 50455c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes return ConstantRange(LowerDiv.trunc(DstTySize), 50555c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes UpperDiv.trunc(DstTySize)).unionWith(Union); 50655c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes 50755c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes // The truncated value wrapps around. Check if we can do better than fullset. 50855c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes APInt UpperModulo = UpperDiv - MaxBitValue; 50955c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes if (UpperModulo.ult(LowerDiv)) 51055c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes return ConstantRange(LowerDiv.trunc(DstTySize), 51155c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes UpperModulo.trunc(DstTySize)).unionWith(Union); 51255c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes 51355c9ecba47953aa8a4a1baffef81461aee660e9aNuno Lopes return ConstantRange(DstTySize, /*isFullSet=*/true); 514fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 515fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 51695a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes/// zextOrTrunc - make this range have the bit width given by \p DstTySize. The 51795a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes/// value is zero extended, truncated, or left alone to make it that width. 51895a3be0ba44e96308c65c28ee859acc36149ddd8Nuno LopesConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const { 51995a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes unsigned SrcTySize = getBitWidth(); 52095a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes if (SrcTySize > DstTySize) 52195a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return truncate(DstTySize); 52248a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (SrcTySize < DstTySize) 52395a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return zeroExtend(DstTySize); 52448a09aec60c5daf67430811e24256d501a576766Nick Lewycky return *this; 52595a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes} 52695a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes 52795a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes/// sextOrTrunc - make this range have the bit width given by \p DstTySize. The 52895a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes/// value is sign extended, truncated, or left alone to make it that width. 52995a3be0ba44e96308c65c28ee859acc36149ddd8Nuno LopesConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const { 53095a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes unsigned SrcTySize = getBitWidth(); 53195a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes if (SrcTySize > DstTySize) 53295a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return truncate(DstTySize); 53348a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (SrcTySize < DstTySize) 53495a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes return signExtend(DstTySize); 53548a09aec60c5daf67430811e24256d501a576766Nick Lewycky return *this; 53695a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes} 53795a3be0ba44e96308c65c28ee859acc36149ddd8Nuno Lopes 538a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 539a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange::add(const ConstantRange &Other) const { 540a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (isEmptySet() || Other.isEmptySet()) 541a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/false); 542cf9e07dea8aad32c5e7e2631d135566b20e1763cNick Lewycky if (isFullSet() || Other.isFullSet()) 543cf9e07dea8aad32c5e7e2631d135566b20e1763cNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 544a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 545a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize(); 546a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt NewLower = getLower() + Other.getLower(); 547a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt NewUpper = getUpper() + Other.getUpper() - 1; 548a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (NewLower == NewUpper) 549a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/true); 550a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 551a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman ConstantRange X = ConstantRange(NewLower, NewUpper); 552a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y)) 553a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman // We've wrapped, therefore, full set. 554a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/true); 555a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 556a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return X; 557a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 558a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 559a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 5607f9ef4bb514d5a28637789d8f397dadd4344dc1bNick LewyckyConstantRange::sub(const ConstantRange &Other) const { 5617f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isEmptySet() || Other.isEmptySet()) 5627f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 5637f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isFullSet() || Other.isFullSet()) 5647f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 5657f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky 5667f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize(); 567e6240e8b83e9bd60e622650e9e801ebc957172b4Nick Lewycky APInt NewLower = getLower() - Other.getUpper() + 1; 568e6240e8b83e9bd60e622650e9e801ebc957172b4Nick Lewycky APInt NewUpper = getUpper() - Other.getLower(); 5697f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (NewLower == NewUpper) 5707f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 5717f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky 5727f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky ConstantRange X = ConstantRange(NewLower, NewUpper); 5737f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y)) 5747f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky // We've wrapped, therefore, full set. 5757f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 5767f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky 5777f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return X; 5787f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky} 5797f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky 5807f9ef4bb514d5a28637789d8f397dadd4344dc1bNick LewyckyConstantRange 581a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange::multiply(const ConstantRange &Other) const { 5828dcc58e6b44fbaab39a24b1f75e67f05275084dcDan Gohman // TODO: If either operand is a single element and the multiply is known to 5838dcc58e6b44fbaab39a24b1f75e67f05275084dcDan Gohman // be non-wrapping, round the result min and max value to the appropriate 5848dcc58e6b44fbaab39a24b1f75e67f05275084dcDan Gohman // multiple of that element. If wrapping is possible, at least adjust the 5858dcc58e6b44fbaab39a24b1f75e67f05275084dcDan Gohman // range according to the greatest power-of-two factor of the single element. 586153f1ebeb8fd394e5b11b27edde9472de0cbb57fDan Gohman 5872ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky if (isEmptySet() || Other.isEmptySet()) 5882ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 5897e733eab2f11fceb24d6b4f25c27d7ba7d92d97eNuno Lopes 590f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky APInt this_min = getUnsignedMin().zext(getBitWidth() * 2); 591f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky APInt this_max = getUnsignedMax().zext(getBitWidth() * 2); 592f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2); 593f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2); 5942ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky 595f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky ConstantRange Result_zext = ConstantRange(this_min * Other_min, 596f1db120d0494ec55d9265cea7dab22e80dcae10cNick Lewycky this_max * Other_max + 1); 5972ff893f48698005f87163c8029224c718cf4cba9Nick Lewycky return Result_zext.truncate(getBitWidth()); 598a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 599a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 600a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 601a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange::smax(const ConstantRange &Other) const { 60238b06447615440f935008a2141bd0a1fe078d437Dan Gohman // X smax Y is: range(smax(X_smin, Y_smin), 60338b06447615440f935008a2141bd0a1fe078d437Dan Gohman // smax(X_smax, Y_smax)) 60438b06447615440f935008a2141bd0a1fe078d437Dan Gohman if (isEmptySet() || Other.isEmptySet()) 60538b06447615440f935008a2141bd0a1fe078d437Dan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/false); 60638b06447615440f935008a2141bd0a1fe078d437Dan Gohman APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin()); 60738b06447615440f935008a2141bd0a1fe078d437Dan Gohman APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1; 60838b06447615440f935008a2141bd0a1fe078d437Dan Gohman if (NewU == NewL) 60938b06447615440f935008a2141bd0a1fe078d437Dan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/true); 61038b06447615440f935008a2141bd0a1fe078d437Dan Gohman return ConstantRange(NewL, NewU); 611a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 612a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 613a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 614a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange::umax(const ConstantRange &Other) const { 615a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman // X umax Y is: range(umax(X_umin, Y_umin), 616a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman // umax(X_umax, Y_umax)) 617a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (isEmptySet() || Other.isEmptySet()) 618a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/false); 619a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); 620a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1; 621a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman if (NewU == NewL) 622a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(getBitWidth(), /*isFullSet=*/true); 623a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman return ConstantRange(NewL, NewU); 624a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 625a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 626a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan GohmanConstantRange 627956daf0f7f7fa473cf92c8193905a8a441932b69Nick LewyckyConstantRange::udiv(const ConstantRange &RHS) const { 628956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0) 629956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 630956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (RHS.isFullSet()) 631956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 632956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 633956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax()); 634956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 635956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky APInt RHS_umin = RHS.getUnsignedMin(); 636956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (RHS_umin == 0) { 637956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky // We want the lowest value in RHS excluding zero. Usually that would be 1 638956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky // except for a range in the form of [X, 1) in which case it would be X. 639956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (RHS.getUpper() == 1) 640956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky RHS_umin = RHS.getLower(); 641956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky else 642956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky RHS_umin = APInt(getBitWidth(), 1); 643956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky } 644956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 645956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1; 646956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 647956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky // If the LHS is Full and the RHS is a wrapped interval containing 1 then 648956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky // this could occur. 649956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky if (Lower == Upper) 650956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 651956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky 652956daf0f7f7fa473cf92c8193905a8a441932b69Nick Lewycky return ConstantRange(Lower, Upper); 653a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 654a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 65534e992da381bf8b1a9cbcc1bde0b117207809649Nuno LopesConstantRange 656198381e542320265e1c5fed18e938db3563a45bfNick LewyckyConstantRange::binaryAnd(const ConstantRange &Other) const { 657198381e542320265e1c5fed18e938db3563a45bfNick Lewycky if (isEmptySet() || Other.isEmptySet()) 658198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 659198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 660198381e542320265e1c5fed18e938db3563a45bfNick Lewycky // TODO: replace this with something less conservative 661198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 662198381e542320265e1c5fed18e938db3563a45bfNick Lewycky APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax()); 663198381e542320265e1c5fed18e938db3563a45bfNick Lewycky if (umin.isAllOnesValue()) 664198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 665198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(APInt::getNullValue(getBitWidth()), umin + 1); 666198381e542320265e1c5fed18e938db3563a45bfNick Lewycky} 667198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 668198381e542320265e1c5fed18e938db3563a45bfNick LewyckyConstantRange 669198381e542320265e1c5fed18e938db3563a45bfNick LewyckyConstantRange::binaryOr(const ConstantRange &Other) const { 670198381e542320265e1c5fed18e938db3563a45bfNick Lewycky if (isEmptySet() || Other.isEmptySet()) 671198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 672198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 673198381e542320265e1c5fed18e938db3563a45bfNick Lewycky // TODO: replace this with something less conservative 674198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 675198381e542320265e1c5fed18e938db3563a45bfNick Lewycky APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); 676198381e542320265e1c5fed18e938db3563a45bfNick Lewycky if (umax.isMinValue()) 677198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 678198381e542320265e1c5fed18e938db3563a45bfNick Lewycky return ConstantRange(umax, APInt::getNullValue(getBitWidth())); 679198381e542320265e1c5fed18e938db3563a45bfNick Lewycky} 680198381e542320265e1c5fed18e938db3563a45bfNick Lewycky 681198381e542320265e1c5fed18e938db3563a45bfNick LewyckyConstantRange 6827f9ef4bb514d5a28637789d8f397dadd4344dc1bNick LewyckyConstantRange::shl(const ConstantRange &Other) const { 6837f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isEmptySet() || Other.isEmptySet()) 6847f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 68534e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 6867f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky APInt min = getUnsignedMin().shl(Other.getUnsignedMin()); 6877f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky APInt max = getUnsignedMax().shl(Other.getUnsignedMax()); 68834e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 68934e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes // there's no overflow! 6904459145c2ccb5d063841a5d8c76b8b8ac9adaf2fNuno Lopes APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros()); 6917f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (Zeros.ugt(Other.getUnsignedMax())) 6927f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(min, max + 1); 69334e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 69434e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes // FIXME: implement the other tricky cases 6957f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 69634e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes} 69734e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 69834e992da381bf8b1a9cbcc1bde0b117207809649Nuno LopesConstantRange 6997f9ef4bb514d5a28637789d8f397dadd4344dc1bNick LewyckyConstantRange::lshr(const ConstantRange &Other) const { 7007f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (isEmptySet() || Other.isEmptySet()) 7017f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 70234e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 7037f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()); 7047f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky APInt min = getUnsignedMin().lshr(Other.getUnsignedMax()); 7057f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky if (min == max + 1) 7067f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 7077f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky 7087f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(min, max + 1); 70934e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes} 71034e992da381bf8b1a9cbcc1bde0b117207809649Nuno Lopes 7119773e45a1e97f5098905bac26b8b8b7c844473f0Owen AndersonConstantRange ConstantRange::inverse() const { 71248a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (isFullSet()) 7137f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 71448a09aec60c5daf67430811e24256d501a576766Nick Lewycky if (isEmptySet()) 7157f9ef4bb514d5a28637789d8f397dadd4344dc1bNick Lewycky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 7169773e45a1e97f5098905bac26b8b8b7c844473f0Owen Anderson return ConstantRange(Upper, Lower); 7179773e45a1e97f5098905bac26b8b8b7c844473f0Owen Anderson} 7189773e45a1e97f5098905bac26b8b8b7c844473f0Owen Anderson 71938b06447615440f935008a2141bd0a1fe078d437Dan Gohman/// print - Print out the bounds to a stream... 720a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman/// 72138b06447615440f935008a2141bd0a1fe078d437Dan Gohmanvoid ConstantRange::print(raw_ostream &OS) const { 722df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman if (isFullSet()) 723df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman OS << "full-set"; 724df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman else if (isEmptySet()) 725df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman OS << "empty-set"; 726df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman else 727df6d5e03940c8a2a560b74a69061aff4ae1badf3Dan Gohman OS << "[" << Lower << "," << Upper << ")"; 728a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 729a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman 73038b06447615440f935008a2141bd0a1fe078d437Dan Gohman/// dump - Allow printing from a debugger easily... 731a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman/// 73238b06447615440f935008a2141bd0a1fe078d437Dan Gohmanvoid ConstantRange::dump() const { 7337fd5fb4b4755c3df86da5a0ebedf0d328fafbc81David Greene print(dbgs()); 734a3755d8d366fdd7a2415b93ac0253f8e677c9dfdDan Gohman} 735