ConstantRange.cpp revision 203954
1100894Srwatson//===-- ConstantRange.cpp - ConstantRange implementation ------------------===// 2126097Srwatson// 3100894Srwatson// The LLVM Compiler Infrastructure 4145160Srwatson// 5147983Srwatson// This file is distributed under the University of Illinois Open Source 6100894Srwatson// License. See LICENSE.TXT for details. 7100894Srwatson// 8100894Srwatson//===----------------------------------------------------------------------===// 9100894Srwatson// 10100894Srwatson// Represent a range of possible values that may occur when the program is run 11106392Srwatson// for an integral value. This keeps track of a lower and upper bound for the 12106392Srwatson// constant, which MAY wrap around the end of the numeric range. To do this, it 13106392Srwatson// keeps track of a [lower, upper) bound, which specifies an interval just like 14106392Srwatson// STL iterators. When used with boolean values, the following are important 15100894Srwatson// ranges (other integral ranges use min/max values for special range values): 16147983Srwatson// 17147983Srwatson// [F, F) = {} = Empty set 18147983Srwatson// [T, F) = {T} 19100894Srwatson// [F, T) = {F} 20100894Srwatson// [T, T) = {F, T} = Full set 21100894Srwatson// 22100894Srwatson//===----------------------------------------------------------------------===// 23100894Srwatson 24100894Srwatson#include "llvm/Support/ConstantRange.h" 25100894Srwatson#include "llvm/Support/Debug.h" 26100894Srwatson#include "llvm/Support/raw_ostream.h" 27100894Srwatson#include "llvm/Instructions.h" 28100894Srwatsonusing namespace llvm; 29100894Srwatson 30100894Srwatson/// Initialize a full (the default) or empty set for the specified type. 31100894Srwatson/// 32100894SrwatsonConstantRange::ConstantRange(uint32_t BitWidth, bool Full) { 33100894Srwatson if (Full) 34100894Srwatson Lower = Upper = APInt::getMaxValue(BitWidth); 35100894Srwatson else 36100894Srwatson Lower = Upper = APInt::getMinValue(BitWidth); 37100894Srwatson} 38100894Srwatson 39100894Srwatson/// Initialize a range to hold the single specified value. 40116182Sobrien/// 41122454SrwatsonConstantRange::ConstantRange(const APInt & V) : Lower(V), Upper(V + 1) {} 42122454Srwatson 43122454SrwatsonConstantRange::ConstantRange(const APInt &L, const APInt &U) : 44122454Srwatson Lower(L), Upper(U) { 45145414Strhodes assert(L.getBitWidth() == U.getBitWidth() && 46145414Strhodes "ConstantRange with unequal bit widths"); 47100894Srwatson assert((L != U || (L.isMaxValue() || L.isMinValue())) && 48100894Srwatson "Lower == Upper, but they aren't min or max value!"); 49116182Sobrien} 50116182Sobrien 51116182SobrienConstantRange ConstantRange::makeICmpRegion(unsigned Pred, 52100894Srwatson const ConstantRange &CR) { 53104300Sphk uint32_t W = CR.getBitWidth(); 54101173Srwatson switch (Pred) { 55100894Srwatson default: assert(!"Invalid ICmp predicate to makeICmpRegion()"); 56106856Srwatson case ICmpInst::ICMP_EQ: 57100979Srwatson return CR; 58106468Srwatson case ICmpInst::ICMP_NE: 59100979Srwatson if (CR.isSingleElement()) 60100979Srwatson return ConstantRange(CR.getUpper(), CR.getLower()); 61102949Sbde return ConstantRange(W); 62100979Srwatson case ICmpInst::ICMP_ULT: 63100979Srwatson return ConstantRange(APInt::getMinValue(W), CR.getUnsignedMax()); 64101712Srwatson case ICmpInst::ICMP_SLT: 65100979Srwatson return ConstantRange(APInt::getSignedMinValue(W), CR.getSignedMax()); 66116701Srwatson case ICmpInst::ICMP_ULE: { 67100979Srwatson APInt UMax(CR.getUnsignedMax()); 68100894Srwatson if (UMax.isMaxValue()) 69100894Srwatson return ConstantRange(W); 70100979Srwatson return ConstantRange(APInt::getMinValue(W), UMax + 1); 71100979Srwatson } 72100979Srwatson case ICmpInst::ICMP_SLE: { 73100979Srwatson APInt SMax(CR.getSignedMax()); 74100979Srwatson if (SMax.isMaxSignedValue() || (SMax+1).isMaxSignedValue()) 75100979Srwatson return ConstantRange(W); 76100979Srwatson return ConstantRange(APInt::getSignedMinValue(W), SMax + 1); 77100979Srwatson } 78100894Srwatson case ICmpInst::ICMP_UGT: 79100979Srwatson return ConstantRange(CR.getUnsignedMin() + 1, APInt::getNullValue(W)); 80100979Srwatson case ICmpInst::ICMP_SGT: 81100979Srwatson return ConstantRange(CR.getSignedMin() + 1, 82100979Srwatson APInt::getSignedMinValue(W)); 83100979Srwatson case ICmpInst::ICMP_UGE: { 84100979Srwatson APInt UMin(CR.getUnsignedMin()); 85100979Srwatson if (UMin.isMinValue()) 86100979Srwatson return ConstantRange(W); 87100979Srwatson return ConstantRange(UMin, APInt::getNullValue(W)); 88100979Srwatson } 89100979Srwatson case ICmpInst::ICMP_SGE: { 90100979Srwatson APInt SMin(CR.getSignedMin()); 91100979Srwatson if (SMin.isMinSignedValue()) 92100979Srwatson return ConstantRange(W); 93100979Srwatson return ConstantRange(SMin, APInt::getSignedMinValue(W)); 94100979Srwatson } 95121374Srwatson } 96121374Srwatson} 97100979Srwatson 98100979Srwatson/// isFullSet - Return true if this set contains all of the elements possible 99101712Srwatson/// for this data-type 100101712Srwatsonbool ConstantRange::isFullSet() const { 101101712Srwatson return Lower == Upper && Lower.isMaxValue(); 102101712Srwatson} 103101712Srwatson 104147983Srwatson/// isEmptySet - Return true if this set contains no members. 105101712Srwatson/// 106100979Srwatsonbool ConstantRange::isEmptySet() const { 107100979Srwatson return Lower == Upper && Lower.isMinValue(); 108104517Srwatson} 109114846Srwatson 110114846Srwatson/// isWrappedSet - Return true if this set wraps around the top of the range, 111100979Srwatson/// for example: [100, 8) 112105497Srwatson/// 113114846Srwatsonbool ConstantRange::isWrappedSet() const { 114114846Srwatson return Lower.ugt(Upper); 115114846Srwatson} 116114846Srwatson 117100979Srwatson/// getSetSize - Return the number of elements in this set. 118105959Srwatson/// 119105959SrwatsonAPInt ConstantRange::getSetSize() const { 120105959Srwatson if (isEmptySet()) 121105959Srwatson return APInt(getBitWidth(), 0); 122105959Srwatson if (getBitWidth() == 1) { 123121372Srwatson if (Lower != Upper) // One of T or F in the set... 124100979Srwatson return APInt(2, 1); 125105988Srwatson return APInt(2, 2); // Must be full set... 126113487Srwatson } 127113487Srwatson 128113487Srwatson // Simply subtract the bounds... 129113487Srwatson return Upper - Lower; 130113487Srwatson} 131113487Srwatson 132113487Srwatson/// getUnsignedMax - Return the largest unsigned value contained in the 133113487Srwatson/// ConstantRange. 134113487Srwatson/// 135113487SrwatsonAPInt ConstantRange::getUnsignedMax() const { 136118308Srwatson if (isFullSet() || isWrappedSet()) 137121372Srwatson return APInt::getMaxValue(getBitWidth()); 138113487Srwatson else 139113487Srwatson return getUpper() - 1; 140101988Srwatson} 141104268Srwatson 142104268Srwatson/// getUnsignedMin - Return the smallest unsigned value contained in the 143104517Srwatson/// ConstantRange. 144104517Srwatson/// 145104517SrwatsonAPInt ConstantRange::getUnsignedMin() const { 146121374Srwatson if (isFullSet() || (isWrappedSet() && getUpper() != 0)) 147104517Srwatson return APInt::getMinValue(getBitWidth()); 148100979Srwatson else 149101988Srwatson return getLower(); 150100979Srwatson} 151100979Srwatson 152100979Srwatson/// getSignedMax - Return the largest signed value contained in the 153100979Srwatson/// ConstantRange. 154105694Srwatson/// 155100979SrwatsonAPInt ConstantRange::getSignedMax() const { 156100979Srwatson APInt SignedMax(APInt::getSignedMaxValue(getBitWidth())); 157114806Srwatson if (!isWrappedSet()) { 158114806Srwatson if (getLower().sle(getUpper() - 1)) 159114806Srwatson return getUpper() - 1; 160114806Srwatson else 161114806Srwatson return SignedMax; 162106856Srwatson } else { 163114806Srwatson if (getLower().isNegative() == getUpper().isNegative()) 164106856Srwatson return SignedMax; 165106856Srwatson else 166106856Srwatson return getUpper() - 1; 167106856Srwatson } 168106856Srwatson} 169114806Srwatson 170114806Srwatson/// getSignedMin - Return the smallest signed value contained in the 171114806Srwatson/// ConstantRange. 172114806Srwatson/// 173100979SrwatsonAPInt ConstantRange::getSignedMin() const { 174128885Srwatson APInt SignedMin(APInt::getSignedMinValue(getBitWidth())); 175114806Srwatson if (!isWrappedSet()) { 176114806Srwatson if (getLower().sle(getUpper() - 1)) 177114806Srwatson return getLower(); 178128885Srwatson else 179121372Srwatson return SignedMin; 180121372Srwatson } else { 181100979Srwatson if ((getUpper() - 1).slt(getLower())) { 182106856Srwatson if (getUpper() != SignedMin) 183111883Sjhb return SignedMin; 184106856Srwatson else 185106856Srwatson return getLower(); 186106856Srwatson } else { 187106856Srwatson return getLower(); 188106856Srwatson } 189106856Srwatson } 190106856Srwatson} 191121372Srwatson 192114806Srwatson/// contains - Return true if the specified value is in the set. 193114806Srwatson/// 194122454Srwatsonbool ConstantRange::contains(const APInt &V) const { 195128885Srwatson if (Lower == Upper) 196137072Srwatson return isFullSet(); 197137072Srwatson 198137072Srwatson if (!isWrappedSet()) 199114806Srwatson return Lower.ule(V) && V.ult(Upper); 200114806Srwatson else 201114806Srwatson return Lower.ule(V) || V.ult(Upper); 202114806Srwatson} 203114806Srwatson 204128885Srwatson/// contains - Return true if the argument is a subset of this range. 205114806Srwatson/// Two equal set contain each other. The empty set is considered to be 206106856Srwatson/// contained by all other sets. 207121372Srwatson/// 208114806Srwatsonbool ConstantRange::contains(const ConstantRange &Other) const { 209114806Srwatson if (isFullSet()) return true; 210122454Srwatson if (Other.isFullSet()) return false; 211128885Srwatson if (Other.isEmptySet()) return true; 212137072Srwatson if (isEmptySet()) return false; 213137072Srwatson 214137072Srwatson if (!isWrappedSet()) { 215114806Srwatson if (Other.isWrappedSet()) 216114806Srwatson return false; 217114806Srwatson 218128885Srwatson return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper); 219114806Srwatson } 220113487Srwatson 221121372Srwatson if (!Other.isWrappedSet()) 222114806Srwatson return Other.getUpper().ule(Upper) || 223114806Srwatson Lower.ule(Other.getLower()); 224100979Srwatson 225128885Srwatson return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower()); 226137072Srwatson} 227137072Srwatson 228137072Srwatson/// subtract - Subtract the specified constant from the endpoints of this 229114806Srwatson/// constant range. 230114806SrwatsonConstantRange ConstantRange::subtract(const APInt &Val) const { 231114806Srwatson assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width"); 232114806Srwatson // If the set is empty or full, don't modify the endpoints. 233128885Srwatson if (Lower == Upper) 234114806Srwatson return *this; 235100979Srwatson return ConstantRange(Lower - Val, Upper - Val); 236121372Srwatson} 237114806Srwatson 238114806Srwatson 239122454Srwatson// intersect1Wrapped - This helper function is used to intersect two ranges when 240128885Srwatson// it is known that LHS is wrapped and RHS isn't. 241137072Srwatson// 242137072SrwatsonConstantRange 243137072SrwatsonConstantRange::intersect1Wrapped(const ConstantRange &LHS, 244114806Srwatson const ConstantRange &RHS) { 245114806Srwatson assert(LHS.isWrappedSet() && !RHS.isWrappedSet()); 246114806Srwatson 247128885Srwatson // Check to see if we overlap on the Left side of RHS... 248114806Srwatson // 249114806Srwatson if (RHS.Lower.ult(LHS.Upper)) { 250121372Srwatson // We do overlap on the left side of RHS, see if we overlap on the right of 251114806Srwatson // RHS... 252114806Srwatson if (RHS.Upper.ugt(LHS.Lower)) { 253128885Srwatson // Ok, the result overlaps on both the left and right sides. See if the 254114806Srwatson // resultant interval will be smaller if we wrap or not... 255114806Srwatson // 256137072Srwatson if (LHS.getSetSize().ult(RHS.getSetSize())) 257137072Srwatson return LHS; 258137072Srwatson else 259114806Srwatson return RHS; 260114806Srwatson 261114806Srwatson } else { 262114806Srwatson // No overlap on the right, just on the left. 263114806Srwatson return ConstantRange(RHS.Lower, LHS.Upper); 264114806Srwatson } 265114806Srwatson } else { 266114806Srwatson // We don't overlap on the left side of RHS, see if we overlap on the right 267128885Srwatson // of RHS... 268137072Srwatson if (RHS.Upper.ugt(LHS.Lower)) { 269137072Srwatson // Simple overlap... 270137072Srwatson return ConstantRange(LHS.Lower, RHS.Upper); 271128885Srwatson } else { 272128885Srwatson // No overlap... 273114806Srwatson return ConstantRange(LHS.getBitWidth(), false); 274114806Srwatson } 275121372Srwatson } 276114806Srwatson} 277114806Srwatson 278122454Srwatson/// intersectWith - Return the range that results from the intersection of this 279128885Srwatson/// range with another range. The resultant range is guaranteed to include all 280137072Srwatson/// elements contained in both input ranges, and to have the smallest possible 281137072Srwatson/// set size that does so. Because there may be two intersections with the 282137072Srwatson/// same set size, A.intersectWith(B) might not be equal to B.intersectWith(A). 283114806SrwatsonConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const { 284114806Srwatson assert(getBitWidth() == CR.getBitWidth() && 285114806Srwatson "ConstantRange types don't agree!"); 286114806Srwatson 287114806Srwatson // Handle common cases. 288114806Srwatson if ( isEmptySet() || CR.isFullSet()) return *this; 289128885Srwatson if (CR.isEmptySet() || isFullSet()) return CR; 290114806Srwatson 291114806Srwatson if (!isWrappedSet() && CR.isWrappedSet()) 292100979Srwatson return CR.intersectWith(*this); 293100979Srwatson 294100979Srwatson if (!isWrappedSet() && !CR.isWrappedSet()) { 295100979Srwatson if (Lower.ult(CR.Lower)) { 296100979Srwatson if (Upper.ule(CR.Lower)) 297100979Srwatson return ConstantRange(getBitWidth(), false); 298100979Srwatson 299114806Srwatson if (Upper.ult(CR.Upper)) 300100979Srwatson return ConstantRange(CR.Lower, Upper); 301122524Srwatson 302114806Srwatson return CR; 303128885Srwatson } else { 304114806Srwatson if (Upper.ult(CR.Upper)) 305114806Srwatson return *this; 306128885Srwatson 307100979Srwatson if (Lower.ult(CR.Upper)) 308100979Srwatson return ConstantRange(Lower, CR.Upper); 309100979Srwatson 310100979Srwatson return ConstantRange(getBitWidth(), false); 311100979Srwatson } 312100979Srwatson } 313100979Srwatson 314100979Srwatson if (isWrappedSet() && !CR.isWrappedSet()) { 315100979Srwatson if (CR.Lower.ult(Upper)) { 316100979Srwatson if (CR.Upper.ult(Upper)) 317100979Srwatson return CR; 318100979Srwatson 319100979Srwatson if (CR.Upper.ult(Lower)) 320100979Srwatson return ConstantRange(CR.Lower, Upper); 321100979Srwatson 322113487Srwatson if (getSetSize().ult(CR.getSetSize())) 323118308Srwatson return *this; 324118308Srwatson else 325118308Srwatson return CR; 326113487Srwatson } else if (CR.Lower.ult(Lower)) { 327113487Srwatson if (CR.Upper.ule(Lower)) 328113487Srwatson return ConstantRange(getBitWidth(), false); 329113487Srwatson 330118308Srwatson return ConstantRange(Lower, CR.Upper); 331113487Srwatson } 332113487Srwatson return CR; 333113487Srwatson } 334114806Srwatson 335113487Srwatson if (CR.Upper.ult(Upper)) { 336113487Srwatson if (CR.Lower.ult(Upper)) { 337114806Srwatson if (getSetSize().ult(CR.getSetSize())) 338114806Srwatson return *this; 339114806Srwatson else 340114806Srwatson return CR; 341113487Srwatson } 342113487Srwatson 343113487Srwatson if (CR.Lower.ult(Lower)) 344113487Srwatson return ConstantRange(Lower, CR.Upper); 345113487Srwatson 346113487Srwatson return CR; 347113487Srwatson } else if (CR.Upper.ult(Lower)) { 348113487Srwatson if (CR.Lower.ult(Lower)) 349113487Srwatson return *this; 350100979Srwatson 351100979Srwatson return ConstantRange(CR.Lower, Upper); 352100894Srwatson } 353100979Srwatson if (getSetSize().ult(CR.getSetSize())) 354100979Srwatson return *this; 355100979Srwatson else 356100979Srwatson return CR; 357100979Srwatson} 358100979Srwatson 359100979Srwatson 360100979Srwatson/// unionWith - Return the range that results from the union of this range with 361128885Srwatson/// another range. The resultant range is guaranteed to include the elements of 362128885Srwatson/// both sets, but may contain more. For example, [3, 9) union [12,15) is 363128885Srwatson/// [3, 15), which includes 9, 10, and 11, which were not included in either 364128885Srwatson/// set before. 365128885Srwatson/// 366128885SrwatsonConstantRange ConstantRange::unionWith(const ConstantRange &CR) const { 367128885Srwatson assert(getBitWidth() == CR.getBitWidth() && 368100979Srwatson "ConstantRange types don't agree!"); 369100979Srwatson 370100979Srwatson if ( isFullSet() || CR.isEmptySet()) return *this; 371100979Srwatson if (CR.isFullSet() || isEmptySet()) return CR; 372100979Srwatson 373100979Srwatson if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this); 374100979Srwatson 375100979Srwatson if (!isWrappedSet() && !CR.isWrappedSet()) { 376100979Srwatson if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) { 377100979Srwatson // If the two ranges are disjoint, find the smaller gap and bridge it. 378100979Srwatson APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; 379100979Srwatson if (d1.ult(d2)) 380100979Srwatson return ConstantRange(Lower, CR.Upper); 381100979Srwatson else 382100979Srwatson return ConstantRange(CR.Lower, Upper); 383100979Srwatson } 384100979Srwatson 385100979Srwatson APInt L = Lower, U = Upper; 386100979Srwatson if (CR.Lower.ult(L)) 387100979Srwatson L = CR.Lower; 388132199Sphk if ((CR.Upper - 1).ugt(U - 1)) 389100979Srwatson U = CR.Upper; 390100979Srwatson 391100979Srwatson if (L == 0 && U == 0) 392100979Srwatson return ConstantRange(getBitWidth()); 393100979Srwatson 394100979Srwatson return ConstantRange(L, U); 395100979Srwatson } 396100979Srwatson 397100979Srwatson if (!CR.isWrappedSet()) { 398100979Srwatson // ------U L----- and ------U L----- : this 399114806Srwatson // L--U L--U : CR 400100979Srwatson if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower)) 401114806Srwatson return *this; 402114806Srwatson 403114806Srwatson // ------U L----- : this 404114806Srwatson // L---------U : CR 405114806Srwatson if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) 406114806Srwatson return ConstantRange(getBitWidth()); 407114806Srwatson 408114806Srwatson // ----U L---- : this 409114806Srwatson // L---U : CR 410114806Srwatson // <d1> <d2> 411114806Srwatson if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) { 412114806Srwatson APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; 413114806Srwatson if (d1.ult(d2)) 414114806Srwatson return ConstantRange(Lower, CR.Upper); 415114806Srwatson else 416114806Srwatson return ConstantRange(CR.Lower, Upper); 417114806Srwatson } 418114806Srwatson 419114806Srwatson // ----U L----- : this 420114806Srwatson // L----U : CR 421114806Srwatson if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper)) 422114806Srwatson return ConstantRange(CR.Lower, Upper); 423114806Srwatson 424100979Srwatson // ------U L---- : this 425114806Srwatson // L-----U : CR 426114806Srwatson if (CR.Lower.ult(Upper) && CR.Upper.ult(Lower)) 427114806Srwatson return ConstantRange(Lower, CR.Upper); 428114806Srwatson } 429114806Srwatson 430114806Srwatson assert(isWrappedSet() && CR.isWrappedSet() && 431114806Srwatson "ConstantRange::unionWith missed wrapped union unwrapped case"); 432100979Srwatson 433100979Srwatson // ------U L---- and ------U L---- : this 434114846Srwatson // -U L----------- and ------------U L : CR 435100979Srwatson if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper)) 436114806Srwatson return ConstantRange(getBitWidth()); 437114806Srwatson 438100979Srwatson APInt L = Lower, U = Upper; 439100979Srwatson if (CR.Upper.ugt(U)) 440114846Srwatson U = CR.Upper; 441100979Srwatson if (CR.Lower.ult(L)) 442100979Srwatson L = CR.Lower; 443100979Srwatson 444100979Srwatson return ConstantRange(L, U); 445114806Srwatson} 446114806Srwatson 447114806Srwatson/// zeroExtend - Return a new range in the specified integer type, which must 448114806Srwatson/// be strictly larger than the current type. The returned range will 449114806Srwatson/// correspond to the possible range of values as if the source range had been 450114806Srwatson/// zero extended. 451114806SrwatsonConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const { 452114806Srwatson unsigned SrcTySize = getBitWidth(); 453114806Srwatson assert(SrcTySize < DstTySize && "Not a value extension"); 454114806Srwatson if (isFullSet()) 455114806Srwatson // Change a source full set into [0, 1 << 8*numbytes) 456114806Srwatson return ConstantRange(APInt(DstTySize,0), APInt(DstTySize,1).shl(SrcTySize)); 457100979Srwatson 458100979Srwatson APInt L = Lower; L.zext(DstTySize); 459100979Srwatson APInt U = Upper; U.zext(DstTySize); 460113487Srwatson return ConstantRange(L, U); 461100979Srwatson} 462100979Srwatson 463100979Srwatson/// signExtend - Return a new range in the specified integer type, which must 464100979Srwatson/// be strictly larger than the current type. The returned range will 465114806Srwatson/// correspond to the possible range of values as if the source range had been 466114806Srwatson/// sign extended. 467114806SrwatsonConstantRange ConstantRange::signExtend(uint32_t DstTySize) const { 468100979Srwatson unsigned SrcTySize = getBitWidth(); 469100979Srwatson assert(SrcTySize < DstTySize && "Not a value extension"); 470100979Srwatson if (isFullSet()) { 471100979Srwatson return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1), 472100979Srwatson APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1); 473100979Srwatson } 474104520Srwatson 475104520Srwatson APInt L = Lower; L.sext(DstTySize); 476104520Srwatson APInt U = Upper; U.sext(DstTySize); 477104520Srwatson return ConstantRange(L, U); 478104520Srwatson} 479114806Srwatson 480104520Srwatson/// truncate - Return a new range in the specified integer type, which must be 481114806Srwatson/// strictly smaller than the current type. The returned range will 482104520Srwatson/// correspond to the possible range of values as if the source range had been 483104520Srwatson/// truncated to the specified type. 484100979SrwatsonConstantRange ConstantRange::truncate(uint32_t DstTySize) const { 485100979Srwatson unsigned SrcTySize = getBitWidth(); 486100979Srwatson assert(SrcTySize > DstTySize && "Not a value truncation"); 487100979Srwatson APInt Size(APInt::getLowBitsSet(SrcTySize, DstTySize)); 488104520Srwatson if (isFullSet() || getSetSize().ugt(Size)) 489104520Srwatson return ConstantRange(DstTySize); 490100979Srwatson 491104520Srwatson APInt L = Lower; L.trunc(DstTySize); 492100979Srwatson APInt U = Upper; U.trunc(DstTySize); 493104520Srwatson return ConstantRange(L, U); 494104520Srwatson} 495104520Srwatson 496104520Srwatson/// zextOrTrunc - make this range have the bit width given by \p DstTySize. The 497104520Srwatson/// value is zero extended, truncated, or left alone to make it that width. 498114806SrwatsonConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const { 499100979Srwatson unsigned SrcTySize = getBitWidth(); 500104520Srwatson if (SrcTySize > DstTySize) 501100979Srwatson return truncate(DstTySize); 502100979Srwatson else if (SrcTySize < DstTySize) 503100979Srwatson return zeroExtend(DstTySize); 504100979Srwatson else 505106856Srwatson return *this; 506113487Srwatson} 507100979Srwatson 508114806Srwatson/// sextOrTrunc - make this range have the bit width given by \p DstTySize. The 509114806Srwatson/// value is sign extended, truncated, or left alone to make it that width. 510100979SrwatsonConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const { 511100979Srwatson unsigned SrcTySize = getBitWidth(); 512100979Srwatson if (SrcTySize > DstTySize) 513100979Srwatson return truncate(DstTySize); 514100979Srwatson else if (SrcTySize < DstTySize) 515100979Srwatson return signExtend(DstTySize); 516100979Srwatson else 517100979Srwatson return *this; 518100979Srwatson} 519100979Srwatson 520121371SrwatsonConstantRange 521121371SrwatsonConstantRange::add(const ConstantRange &Other) const { 522100979Srwatson if (isEmptySet() || Other.isEmptySet()) 523100979Srwatson return ConstantRange(getBitWidth(), /*isFullSet=*/false); 524100979Srwatson if (isFullSet() || Other.isFullSet()) 525100979Srwatson return ConstantRange(getBitWidth(), /*isFullSet=*/true); 526100979Srwatson 527100979Srwatson APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize(); 528100979Srwatson APInt NewLower = getLower() + Other.getLower(); 529100979Srwatson APInt NewUpper = getUpper() + Other.getUpper() - 1; 530100979Srwatson if (NewLower == NewUpper) 531100979Srwatson return ConstantRange(getBitWidth(), /*isFullSet=*/true); 532100979Srwatson 533100979Srwatson ConstantRange X = ConstantRange(NewLower, NewUpper); 534100979Srwatson if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y)) 535100979Srwatson // We've wrapped, therefore, full set. 536100979Srwatson return ConstantRange(getBitWidth(), /*isFullSet=*/true); 537100979Srwatson 538100979Srwatson return X; 539100979Srwatson} 540100979Srwatson 541100979SrwatsonConstantRange 542100979SrwatsonConstantRange::multiply(const ConstantRange &Other) const { 543100979Srwatson // TODO: If either operand is a single element and the multiply is known to 544100979Srwatson // be non-wrapping, round the result min and max value to the appropriate 545100979Srwatson // multiple of that element. If wrapping is possible, at least adjust the 546100979Srwatson // range according to the greatest power-of-two factor of the single element. 547100979Srwatson 548100979Srwatson if (isEmptySet() || Other.isEmptySet()) 549100979Srwatson return ConstantRange(getBitWidth(), /*isFullSet=*/false); 550100979Srwatson if (isFullSet() || Other.isFullSet()) 551100979Srwatson return ConstantRange(getBitWidth(), /*isFullSet=*/true); 552100979Srwatson 553121374Srwatson APInt this_min = getUnsignedMin().zext(getBitWidth() * 2); 554104521Srwatson APInt this_max = getUnsignedMax().zext(getBitWidth() * 2); 555104521Srwatson APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2); 556104521Srwatson APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2); 557104521Srwatson 558104521Srwatson ConstantRange Result_zext = ConstantRange(this_min * Other_min, 559104521Srwatson this_max * Other_max + 1); 560104521Srwatson return Result_zext.truncate(getBitWidth()); 561121374Srwatson} 562104521Srwatson 563104521SrwatsonConstantRange 564104521SrwatsonConstantRange::smax(const ConstantRange &Other) const { 565104521Srwatson // X smax Y is: range(smax(X_smin, Y_smin), 566104521Srwatson // smax(X_smax, Y_smax)) 567104521Srwatson if (isEmptySet() || Other.isEmptySet()) 568104521Srwatson return ConstantRange(getBitWidth(), /*isFullSet=*/false); 569104521Srwatson APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin()); 570104521Srwatson APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1; 571104521Srwatson if (NewU == NewL) 572112675Srwatson return ConstantRange(getBitWidth(), /*isFullSet=*/true); 573105694Srwatson return ConstantRange(NewL, NewU); 574104522Srwatson} 575105694Srwatson 576120582SrwatsonConstantRange 577120582SrwatsonConstantRange::umax(const ConstantRange &Other) const { 578105694Srwatson // X umax Y is: range(umax(X_umin, Y_umin), 579105694Srwatson // umax(X_umax, Y_umax)) 580105694Srwatson if (isEmptySet() || Other.isEmptySet()) 581105694Srwatson return ConstantRange(getBitWidth(), /*isFullSet=*/false); 582105694Srwatson APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); 583122584Srwatson APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1; 584122584Srwatson if (NewU == NewL) 585122584Srwatson return ConstantRange(getBitWidth(), /*isFullSet=*/true); 586105988Srwatson return ConstantRange(NewL, NewU); 587105694Srwatson} 588105694Srwatson 589105694SrwatsonConstantRange 590105694SrwatsonConstantRange::udiv(const ConstantRange &RHS) const { 591105694Srwatson if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0) 592105694Srwatson return ConstantRange(getBitWidth(), /*isFullSet=*/false); 593105694Srwatson if (RHS.isFullSet()) 594105694Srwatson return ConstantRange(getBitWidth(), /*isFullSet=*/true); 595107849Salfred 596105694Srwatson APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax()); 597105694Srwatson 598105694Srwatson APInt RHS_umin = RHS.getUnsignedMin(); 599105694Srwatson if (RHS_umin == 0) { 600105694Srwatson // We want the lowest value in RHS excluding zero. Usually that would be 1 601105694Srwatson // except for a range in the form of [X, 1) in which case it would be X. 602105694Srwatson if (RHS.getUpper() == 1) 603105694Srwatson RHS_umin = RHS.getLower(); 604105694Srwatson else 605105694Srwatson RHS_umin = APInt(getBitWidth(), 1); 606105694Srwatson } 607105694Srwatson 608105694Srwatson APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1; 609105694Srwatson 610105694Srwatson // If the LHS is Full and the RHS is a wrapped interval containing 1 then 611105694Srwatson // this could occur. 612105694Srwatson if (Lower == Upper) 613105694Srwatson return ConstantRange(getBitWidth(), /*isFullSet=*/true); 614105694Srwatson 615111119Simp return ConstantRange(Lower, Upper); 616105694Srwatson} 617105694Srwatson 618105694SrwatsonConstantRange 619105694SrwatsonConstantRange::shl(const ConstantRange &Amount) const { 620105694Srwatson if (isEmptySet()) 621105694Srwatson return *this; 622105694Srwatson 623111119Simp APInt min = getUnsignedMin() << Amount.getUnsignedMin(); 624122524Srwatson APInt max = getUnsignedMax() << Amount.getUnsignedMax(); 625122159Srwatson 626105694Srwatson // there's no overflow! 627105694Srwatson APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros()); 628105694Srwatson if (Zeros.uge(Amount.getUnsignedMax())) 629105694Srwatson return ConstantRange(min, max); 630105694Srwatson 631105694Srwatson // FIXME: implement the other tricky cases 632105694Srwatson return ConstantRange(getBitWidth()); 633105694Srwatson} 634105694Srwatson 635100979SrwatsonConstantRange 636100979SrwatsonConstantRange::ashr(const ConstantRange &Amount) const { 637100979Srwatson if (isEmptySet()) 638100979Srwatson return *this; 639100894Srwatson 640100894Srwatson APInt min = getUnsignedMax().ashr(Amount.getUnsignedMin()); 641105694Srwatson APInt max = getUnsignedMin().ashr(Amount.getUnsignedMax()); 642105694Srwatson return ConstantRange(min, max); 643100979Srwatson} 644100894Srwatson 645105694SrwatsonConstantRange 646105694SrwatsonConstantRange::lshr(const ConstantRange &Amount) const { 647105694Srwatson if (isEmptySet()) 648105694Srwatson return *this; 649105694Srwatson 650105694Srwatson APInt min = getUnsignedMax().lshr(Amount.getUnsignedMin()); 651105694Srwatson APInt max = getUnsignedMin().lshr(Amount.getUnsignedMax()); 652105694Srwatson return ConstantRange(min, max); 653111119Simp} 654105694Srwatson 655105694Srwatson/// print - Print out the bounds to a stream... 656105694Srwatson/// 657105694Srwatsonvoid ConstantRange::print(raw_ostream &OS) const { 658105694Srwatson if (isFullSet()) 659105694Srwatson OS << "full-set"; 660111119Simp else if (isEmptySet()) 661122524Srwatson OS << "empty-set"; 662122159Srwatson else 663100979Srwatson OS << "[" << Lower << "," << Upper << ")"; 664105694Srwatson} 665100979Srwatson 666105694Srwatson/// dump - Allow printing from a debugger easily... 667105694Srwatson/// 668100979Srwatsonvoid ConstantRange::dump() const { 669100979Srwatson print(dbgs()); 670100979Srwatson} 671100979Srwatson 672100979Srwatson 673100979Srwatson