ConstantRange.cpp revision 9babd0e0f2f380dcb84561c1d9f9ebc773c588f2
1645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner//===-- ConstantRange.cpp - ConstantRange implementation ------------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// 10645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// Represent a range of possible values that may occur when the program is run 11645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// for an integral value. This keeps track of a lower and upper bound for the 12645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// constant, which MAY wrap around the end of the numeric range. To do this, it 13645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// keeps track of a [lower, upper) bound, which specifies an interval just like 14645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// STL iterators. When used with boolean values, the following are important 15645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// ranges (other integral ranges use min/max values for special range values): 16645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// 17645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// [F, F) = {} = Empty set 18645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// [T, F) = {T} 19645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// [F, T) = {F} 20645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// [T, T) = {F, T} = Full set 21645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// 22645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner//===----------------------------------------------------------------------===// 23645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 24645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner#include "llvm/Support/ConstantRange.h" 256f81b510217bd87f265cca054c5d9885250d8525Bill Wendling#include "llvm/Support/Streams.h" 266f81b510217bd87f265cca054c5d9885250d8525Bill Wendling#include <ostream> 272cdd21c2e4d855500dfb53f77aa74da53ccf9de6Chris Lattnerusing namespace llvm; 28d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 29645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// Initialize a full (the default) or empty set for the specified type. 30645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 31bb626a6751db9a63d159d32522bdf88cedf46eebReid SpencerConstantRange::ConstantRange(uint32_t BitWidth, bool Full) : 32bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer Lower(BitWidth, 0), Upper(BitWidth, 0) { 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/// 41dc5c1597014fa5c47c94db2b9fd424d2266053dbReid SpencerConstantRange::ConstantRange(const APInt & V) : Lower(V), Upper(V + 1) { } 42645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 43663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid SpencerConstantRange::ConstantRange(const APInt &L, const APInt &U) : 44663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer Lower(L), Upper(U) { 45663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer assert(L.getBitWidth() == U.getBitWidth() && 46663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer "ConstantRange with unequal bit widths"); 47663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer uint32_t BitWidth = L.getBitWidth(); 48663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer assert((L != U || (L == APInt::getMaxValue(BitWidth) || 49663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer L == APInt::getMinValue(BitWidth))) && 50663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer "Lower == Upper, but they aren't min or max value!"); 51663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer} 52663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer 53645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// isFullSet - Return true if this set contains all of the elements possible 54645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// for this data-type 55645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattnerbool ConstantRange::isFullSet() const { 56bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer return Lower == Upper && Lower == APInt::getMaxValue(getBitWidth()); 57645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 58fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 59645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// isEmptySet - Return true if this set contains no members. 60645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 61645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattnerbool ConstantRange::isEmptySet() const { 62bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer return Lower == Upper && Lower == APInt::getMinValue(getBitWidth()); 63645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 64645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 65645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// isWrappedSet - Return true if this set wraps around the top of the range, 66645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// for example: [100, 8) 67645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 68a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencerbool ConstantRange::isWrappedSet() const { 69663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return Lower.ugt(Upper); 70645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 71645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 72645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// getSetSize - Return the number of elements in this set. 73645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 74663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid SpencerAPInt ConstantRange::getSetSize() const { 75663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer if (isEmptySet()) 76bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer return APInt(getBitWidth(), 0); 77bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer if (getBitWidth() == 1) { 78645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner if (Lower != Upper) // One of T or F in the set... 79bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer return APInt(2, 1); 80bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer return APInt(2, 2); // Must be full set... 81645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner } 82fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 83645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // Simply subtract the bounds... 84663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return Upper - Lower; 85645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 86645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 873400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getUnsignedMax - Return the largest unsigned value contained in the 883400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 893400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 903400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getUnsignedMax() const { 913400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (isFullSet() || isWrappedSet()) 923400e6af6b10acea219c02ac262637220f84218fNick Lewycky return APInt::getMaxValue(getBitWidth()); 933400e6af6b10acea219c02ac262637220f84218fNick Lewycky else 943400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getUpper() - 1; 953400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 963400e6af6b10acea219c02ac262637220f84218fNick Lewycky 973400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getUnsignedMin - Return the smallest unsigned value contained in the 983400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 993400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1003400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getUnsignedMin() const { 1013400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (isFullSet() || (isWrappedSet() && getUpper() != 0)) 1023400e6af6b10acea219c02ac262637220f84218fNick Lewycky return APInt::getMinValue(getBitWidth()); 1033400e6af6b10acea219c02ac262637220f84218fNick Lewycky else 1043400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getLower(); 1053400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 1063400e6af6b10acea219c02ac262637220f84218fNick Lewycky 1073400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getSignedMax - Return the largest signed value contained in the 1083400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 1093400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1103400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getSignedMax() const { 1113400e6af6b10acea219c02ac262637220f84218fNick Lewycky APInt SignedMax = APInt::getSignedMaxValue(getBitWidth()); 1123400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (!isWrappedSet()) { 1133400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (getLower().slt(getUpper() - 1)) 1143400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getUpper() - 1; 1153400e6af6b10acea219c02ac262637220f84218fNick Lewycky else 1163400e6af6b10acea219c02ac262637220f84218fNick Lewycky return SignedMax; 1173400e6af6b10acea219c02ac262637220f84218fNick Lewycky } else { 1183400e6af6b10acea219c02ac262637220f84218fNick Lewycky if ((getUpper() - 1).slt(getLower())) { 1193400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (getLower() != SignedMax) 1203400e6af6b10acea219c02ac262637220f84218fNick Lewycky return SignedMax; 1213400e6af6b10acea219c02ac262637220f84218fNick Lewycky else 1223400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getUpper() - 1; 1233400e6af6b10acea219c02ac262637220f84218fNick Lewycky } else { 1243400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getUpper() - 1; 1253400e6af6b10acea219c02ac262637220f84218fNick Lewycky } 1263400e6af6b10acea219c02ac262637220f84218fNick Lewycky } 1273400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 1283400e6af6b10acea219c02ac262637220f84218fNick Lewycky 1293400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// getSignedMin - Return the smallest signed value contained in the 1303400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// ConstantRange. 1313400e6af6b10acea219c02ac262637220f84218fNick Lewycky/// 1323400e6af6b10acea219c02ac262637220f84218fNick LewyckyAPInt ConstantRange::getSignedMin() const { 1333400e6af6b10acea219c02ac262637220f84218fNick Lewycky APInt SignedMin = APInt::getSignedMinValue(getBitWidth()); 1343400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (!isWrappedSet()) { 1353400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (getLower().slt(getUpper() - 1)) 1363400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getLower(); 1373400e6af6b10acea219c02ac262637220f84218fNick Lewycky else 1383400e6af6b10acea219c02ac262637220f84218fNick Lewycky return SignedMin; 1393400e6af6b10acea219c02ac262637220f84218fNick Lewycky } else { 1403400e6af6b10acea219c02ac262637220f84218fNick Lewycky if ((getUpper() - 1).slt(getLower())) { 1413400e6af6b10acea219c02ac262637220f84218fNick Lewycky if (getUpper() != SignedMin) 1423400e6af6b10acea219c02ac262637220f84218fNick Lewycky return SignedMin; 1433400e6af6b10acea219c02ac262637220f84218fNick Lewycky else 1443400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getLower(); 1453400e6af6b10acea219c02ac262637220f84218fNick Lewycky } else { 1463400e6af6b10acea219c02ac262637220f84218fNick Lewycky return getLower(); 1473400e6af6b10acea219c02ac262637220f84218fNick Lewycky } 1483400e6af6b10acea219c02ac262637220f84218fNick Lewycky } 1493400e6af6b10acea219c02ac262637220f84218fNick Lewycky} 1503400e6af6b10acea219c02ac262637220f84218fNick Lewycky 151fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// contains - Return true if the specified value is in the set. 152fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// 153a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencerbool ConstantRange::contains(const APInt &V) const { 154a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer if (Lower == Upper) 155a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer return isFullSet(); 156fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 157a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer if (!isWrappedSet()) 158a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer return Lower.ule(V) && V.ult(Upper); 159663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer else 160663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return Lower.ule(V) || V.ult(Upper); 161fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 162645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 163fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// subtract - Subtract the specified constant from the endpoints of this 164fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// constant range. 165581b0d453a63f7f657248f80317976995262be11Reid SpencerConstantRange ConstantRange::subtract(const APInt &Val) const { 166bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width"); 167fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner // If the set is empty or full, don't modify the endpoints. 168663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer if (Lower == Upper) 169663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return *this; 170663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return ConstantRange(Lower - Val, Upper - Val); 171fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 172fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 173fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 174645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// intersect1Wrapped - This helper function is used to intersect two ranges when 175645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// it is known that LHS is wrapped and RHS isn't. 176645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner// 177663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid SpencerConstantRange 178663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid SpencerConstantRange::intersect1Wrapped(const ConstantRange &LHS, 179a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer const ConstantRange &RHS) { 180a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer assert(LHS.isWrappedSet() && !RHS.isWrappedSet()); 181645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 182645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // Check to see if we overlap on the Left side of RHS... 183645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // 184a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer if (RHS.Lower.ult(LHS.Upper)) { 185645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // We do overlap on the left side of RHS, see if we overlap on the right of 186645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // RHS... 187a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer if (RHS.Upper.ugt(LHS.Lower)) { 188645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // Ok, the result overlaps on both the left and right sides. See if the 189645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // resultant interval will be smaller if we wrap or not... 190645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // 191663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer if (LHS.getSetSize().ult(RHS.getSetSize())) 192645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner return LHS; 193645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner else 194645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner return RHS; 195645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 196645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner } else { 197645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // No overlap on the right, just on the left. 198dc5c1597014fa5c47c94db2b9fd424d2266053dbReid Spencer return ConstantRange(RHS.Lower, LHS.Upper); 199645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner } 200645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner } else { 201645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // We don't overlap on the left side of RHS, see if we overlap on the right 202645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // of RHS... 203a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer if (RHS.Upper.ugt(LHS.Lower)) { 204645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // Simple overlap... 205dc5c1597014fa5c47c94db2b9fd424d2266053dbReid Spencer return ConstantRange(LHS.Lower, RHS.Upper); 206645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner } else { 207645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // No overlap... 208bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer return ConstantRange(LHS.getBitWidth(), false); 209645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner } 210645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner } 211645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 212645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 2133e051647c079fe29db049646b39611fc0135327dNick Lewycky/// intersectWith - Return the range that results from the intersection of this 214645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// range with another range. 215645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 216a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid SpencerConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const { 217bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer assert(getBitWidth() == CR.getBitWidth() && 218bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer "ConstantRange types don't agree!"); 219d122f4b648571867c0f8f72290b6c1a0aac02ebbChris Lattner // Handle common special cases 220663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer if (isEmptySet() || CR.isFullSet()) 221663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return *this; 222663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer if (isFullSet() || CR.isEmptySet()) 223663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return CR; 224645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 225a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer if (!isWrappedSet()) { 226a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer if (!CR.isWrappedSet()) { 227663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer using namespace APIntOps; 228a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer APInt L = umax(Lower, CR.Lower); 229a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer APInt U = umin(Upper, CR.Upper); 230645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 231a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer if (L.ult(U)) // If range isn't empty... 232d122f4b648571867c0f8f72290b6c1a0aac02ebbChris Lattner return ConstantRange(L, U); 233645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner else 234bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer return ConstantRange(getBitWidth(), false);// Otherwise, empty set 235645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner } else 236a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer return intersect1Wrapped(CR, *this); 237645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner } else { // We know "this" is wrapped... 238a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer if (!CR.isWrappedSet()) 239a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer return intersect1Wrapped(*this, CR); 240645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner else { 241645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner // Both ranges are wrapped... 242663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer using namespace APIntOps; 243a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer APInt L = umax(Lower, CR.Lower); 244a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid Spencer APInt U = umin(Upper, CR.Upper); 245d122f4b648571867c0f8f72290b6c1a0aac02ebbChris Lattner return ConstantRange(L, U); 246645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner } 247645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner } 248645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner return *this; 249645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 250645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 2513e051647c079fe29db049646b39611fc0135327dNick Lewycky/// unionWith - Return the range that results from the union of this range with 252645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// another range. The resultant range is guaranteed to include the elements of 2539babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky/// both sets, but may contain more. For example, [3, 9) union [12,15) is 2549babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky/// [3, 15), which includes 9, 10, and 11, which were not included in either 2559babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky/// set before. 256645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner/// 257a6e8a955d6ab82911a1909fac7a9f4256a4d090eReid SpencerConstantRange ConstantRange::unionWith(const ConstantRange &CR) const { 258bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer assert(getBitWidth() == CR.getBitWidth() && 259bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer "ConstantRange types don't agree!"); 260645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 261c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky if ( isFullSet() || CR.isEmptySet()) return *this; 262c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky if (CR.isFullSet() || isEmptySet()) return CR; 263645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner 2649babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this); 2659babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 266c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky APInt L = Lower, U = Upper; 267c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky 2689babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (!isWrappedSet() && !CR.isWrappedSet()) { 2699babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (CR.Lower.ult(L)) 2709babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky L = CR.Lower; 2719babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 2729babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (CR.Upper.ugt(U)) 2739babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky U = CR.Upper; 2749babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 2759babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 2769babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (isWrappedSet() && !CR.isWrappedSet()) { 2779babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if ((CR.Lower.ult(Upper) && CR.Upper.ult(Upper)) || 2789babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky (CR.Lower.ugt(Lower) && CR.Upper.ugt(Lower))) { 2799babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky return *this; 2809babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 2819babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 2829babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) { 2839babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky return ConstantRange(getBitWidth()); 2849babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 2859babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 2869babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (CR.Lower.ule(Upper) && CR.Upper.ule(Lower)) { 2879babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky APInt d1 = CR.Upper - Upper, d2 = Lower - CR.Upper; 2889babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (d1.ult(d2)) { 2899babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky U = CR.Upper; 2909babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } else { 2919babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky L = CR.Upper; 2929babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 2939babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 2949babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 2959babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (Upper.ult(CR.Lower) && CR.Upper.ult(Lower)) { 2969babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; 2979babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (d1.ult(d2)) { 2989babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky U = CR.Lower + 1; 2999babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } else { 3009babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky L = CR.Upper - 1; 3019babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 3029babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 303c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky 3049babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper)) { 3059babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Lower; 3069babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3079babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (d1.ult(d2)) { 3089babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky U = CR.Lower + 1; 3099babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } else { 3109babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky L = CR.Lower; 3119babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 3129babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 3139babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 3149babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3159babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (isWrappedSet() && CR.isWrappedSet()) { 3169babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (Lower.ult(CR.Upper) || CR.Lower.ult(Upper)) 3179babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky return ConstantRange(getBitWidth()); 3189babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3199babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (CR.Upper.ugt(U)) { 3209babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky U = CR.Upper; 3219babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 3229babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3239babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (CR.Lower.ult(L)) { 3249babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky L = CR.Lower; 3259babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 3269babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky 3279babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky if (L == U) return ConstantRange(getBitWidth()); 3289babd0e0f2f380dcb84561c1d9f9ebc773c588f2Nick Lewycky } 329c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky 330c6a28fcf5db2b6e81607e45cd5210e3e07834eedNick Lewycky return ConstantRange(L, U); 331645e00d1497dec37da92b59b47d76c4f922e6abcChris Lattner} 33296f9d7232c72867ee09641832d2db99f9166d6f0Chris Lattner 333fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// zeroExtend - Return a new range in the specified integer type, which must 334fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// be strictly larger than the current type. The returned range will 335e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer/// correspond to the possible range of values as if the source range had been 336fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// zero extended. 337bb626a6751db9a63d159d32522bdf88cedf46eebReid SpencerConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const { 338bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer unsigned SrcTySize = getBitWidth(); 339663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer assert(SrcTySize < DstTySize && "Not a value extension"); 340dc5c1597014fa5c47c94db2b9fd424d2266053dbReid Spencer if (isFullSet()) 341fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner // Change a source full set into [0, 1 << 8*numbytes) 342dc5c1597014fa5c47c94db2b9fd424d2266053dbReid Spencer return ConstantRange(APInt(DstTySize,0), APInt(DstTySize,1).shl(SrcTySize)); 343fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 344663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer APInt L = Lower; L.zext(DstTySize); 345663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer APInt U = Upper; U.zext(DstTySize); 346663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return ConstantRange(L, U); 347fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 348fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 349fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// truncate - Return a new range in the specified integer type, which must be 350fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// strictly smaller than the current type. The returned range will 351e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer/// correspond to the possible range of values as if the source range had been 352fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner/// truncated to the specified type. 353bb626a6751db9a63d159d32522bdf88cedf46eebReid SpencerConstantRange ConstantRange::truncate(uint32_t DstTySize) const { 354bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer unsigned SrcTySize = getBitWidth(); 355663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer assert(SrcTySize > DstTySize && "Not a value truncation"); 356663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer APInt Size = APInt::getMaxValue(DstTySize).zext(SrcTySize); 357663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer if (isFullSet() || getSetSize().ugt(Size)) 358bb626a6751db9a63d159d32522bdf88cedf46eebReid Spencer return ConstantRange(DstTySize); 359fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 360663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer APInt L = Lower; L.trunc(DstTySize); 361663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer APInt U = Upper; U.trunc(DstTySize); 362663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer return ConstantRange(L, U); 363fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner} 364fc33d30446843009b0eadf63c0bfca35ae2baac6Chris Lattner 36596f9d7232c72867ee09641832d2db99f9166d6f0Chris Lattner/// print - Print out the bounds to a stream... 36696f9d7232c72867ee09641832d2db99f9166d6f0Chris Lattner/// 36796f9d7232c72867ee09641832d2db99f9166d6f0Chris Lattnervoid ConstantRange::print(std::ostream &OS) const { 368663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer OS << "[" << Lower.toStringSigned(10) << "," 369663e711dc235cae94eb50abb1c0571fd0b3a6a35Reid Spencer << Upper.toStringSigned(10) << " )"; 37096f9d7232c72867ee09641832d2db99f9166d6f0Chris Lattner} 37196f9d7232c72867ee09641832d2db99f9166d6f0Chris Lattner 37296f9d7232c72867ee09641832d2db99f9166d6f0Chris Lattner/// dump - Allow printing from a debugger easily... 37396f9d7232c72867ee09641832d2db99f9166d6f0Chris Lattner/// 37496f9d7232c72867ee09641832d2db99f9166d6f0Chris Lattnervoid ConstantRange::dump() const { 375e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling print(cerr); 37696f9d7232c72867ee09641832d2db99f9166d6f0Chris Lattner} 377