1218887Sdim//== RangeConstraintManager.cpp - Manage range constraints.------*- C++ -*--==// 2218887Sdim// 3218887Sdim// The LLVM Compiler Infrastructure 4218887Sdim// 5218887Sdim// This file is distributed under the University of Illinois Open Source 6218887Sdim// License. See LICENSE.TXT for details. 7218887Sdim// 8218887Sdim//===----------------------------------------------------------------------===// 9218887Sdim// 10218887Sdim// This file defines RangeConstraintManager, a class that tracks simple 11226633Sdim// equality and inequality constraints on symbolic values of ProgramState. 12218887Sdim// 13218887Sdim//===----------------------------------------------------------------------===// 14218887Sdim 15218887Sdim#include "SimpleConstraintManager.h" 16239462Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h" 17226633Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 18226633Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 19218887Sdim#include "llvm/ADT/FoldingSet.h" 20218887Sdim#include "llvm/ADT/ImmutableSet.h" 21249423Sdim#include "llvm/Support/Debug.h" 22218887Sdim#include "llvm/Support/raw_ostream.h" 23218887Sdim 24218887Sdimusing namespace clang; 25218887Sdimusing namespace ento; 26218887Sdim 27218887Sdim/// A Range represents the closed range [from, to]. The caller must 28218887Sdim/// guarantee that from <= to. Note that Range is immutable, so as not 29218887Sdim/// to subvert RangeSet's immutability. 30218887Sdimnamespace { 31218887Sdimclass Range : public std::pair<const llvm::APSInt*, 32218887Sdim const llvm::APSInt*> { 33218887Sdimpublic: 34218887Sdim Range(const llvm::APSInt &from, const llvm::APSInt &to) 35218887Sdim : std::pair<const llvm::APSInt*, const llvm::APSInt*>(&from, &to) { 36218887Sdim assert(from <= to); 37218887Sdim } 38218887Sdim bool Includes(const llvm::APSInt &v) const { 39218887Sdim return *first <= v && v <= *second; 40218887Sdim } 41218887Sdim const llvm::APSInt &From() const { 42218887Sdim return *first; 43218887Sdim } 44218887Sdim const llvm::APSInt &To() const { 45218887Sdim return *second; 46218887Sdim } 47218887Sdim const llvm::APSInt *getConcreteValue() const { 48276479Sdim return &From() == &To() ? &From() : nullptr; 49218887Sdim } 50218887Sdim 51218887Sdim void Profile(llvm::FoldingSetNodeID &ID) const { 52218887Sdim ID.AddPointer(&From()); 53218887Sdim ID.AddPointer(&To()); 54218887Sdim } 55218887Sdim}; 56218887Sdim 57218887Sdim 58218887Sdimclass RangeTrait : public llvm::ImutContainerInfo<Range> { 59218887Sdimpublic: 60218887Sdim // When comparing if one Range is less than another, we should compare 61218887Sdim // the actual APSInt values instead of their pointers. This keeps the order 62218887Sdim // consistent (instead of comparing by pointer values) and can potentially 63218887Sdim // be used to speed up some of the operations in RangeSet. 64218887Sdim static inline bool isLess(key_type_ref lhs, key_type_ref rhs) { 65218887Sdim return *lhs.first < *rhs.first || (!(*rhs.first < *lhs.first) && 66218887Sdim *lhs.second < *rhs.second); 67218887Sdim } 68218887Sdim}; 69218887Sdim 70218887Sdim/// RangeSet contains a set of ranges. If the set is empty, then 71218887Sdim/// there the value of a symbol is overly constrained and there are no 72218887Sdim/// possible values for that symbol. 73218887Sdimclass RangeSet { 74218887Sdim typedef llvm::ImmutableSet<Range, RangeTrait> PrimRangeSet; 75218887Sdim PrimRangeSet ranges; // no need to make const, since it is an 76218887Sdim // ImmutableSet - this allows default operator= 77218887Sdim // to work. 78218887Sdimpublic: 79218887Sdim typedef PrimRangeSet::Factory Factory; 80218887Sdim typedef PrimRangeSet::iterator iterator; 81218887Sdim 82218887Sdim RangeSet(PrimRangeSet RS) : ranges(RS) {} 83218887Sdim 84296417Sdim /// Create a new set with all ranges of this set and RS. 85296417Sdim /// Possible intersections are not checked here. 86296417Sdim RangeSet addRange(Factory &F, const RangeSet &RS) { 87296417Sdim PrimRangeSet Ranges(RS.ranges); 88296417Sdim for (const auto &range : ranges) 89296417Sdim Ranges = F.add(Ranges, range); 90296417Sdim return RangeSet(Ranges); 91296417Sdim } 92296417Sdim 93218887Sdim iterator begin() const { return ranges.begin(); } 94218887Sdim iterator end() const { return ranges.end(); } 95218887Sdim 96218887Sdim bool isEmpty() const { return ranges.isEmpty(); } 97218887Sdim 98218887Sdim /// Construct a new RangeSet representing '{ [from, to] }'. 99218887Sdim RangeSet(Factory &F, const llvm::APSInt &from, const llvm::APSInt &to) 100218887Sdim : ranges(F.add(F.getEmptySet(), Range(from, to))) {} 101218887Sdim 102218887Sdim /// Profile - Generates a hash profile of this RangeSet for use 103218887Sdim /// by FoldingSet. 104218887Sdim void Profile(llvm::FoldingSetNodeID &ID) const { ranges.Profile(ID); } 105218887Sdim 106218887Sdim /// getConcreteValue - If a symbol is contrained to equal a specific integer 107218887Sdim /// constant then this method returns that value. Otherwise, it returns 108218887Sdim /// NULL. 109218887Sdim const llvm::APSInt* getConcreteValue() const { 110276479Sdim return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : nullptr; 111218887Sdim } 112218887Sdim 113218887Sdimprivate: 114218887Sdim void IntersectInRange(BasicValueFactory &BV, Factory &F, 115218887Sdim const llvm::APSInt &Lower, 116218887Sdim const llvm::APSInt &Upper, 117218887Sdim PrimRangeSet &newRanges, 118218887Sdim PrimRangeSet::iterator &i, 119218887Sdim PrimRangeSet::iterator &e) const { 120218887Sdim // There are six cases for each range R in the set: 121218887Sdim // 1. R is entirely before the intersection range. 122218887Sdim // 2. R is entirely after the intersection range. 123218887Sdim // 3. R contains the entire intersection range. 124218887Sdim // 4. R starts before the intersection range and ends in the middle. 125218887Sdim // 5. R starts in the middle of the intersection range and ends after it. 126218887Sdim // 6. R is entirely contained in the intersection range. 127218887Sdim // These correspond to each of the conditions below. 128218887Sdim for (/* i = begin(), e = end() */; i != e; ++i) { 129218887Sdim if (i->To() < Lower) { 130218887Sdim continue; 131218887Sdim } 132218887Sdim if (i->From() > Upper) { 133218887Sdim break; 134218887Sdim } 135218887Sdim 136218887Sdim if (i->Includes(Lower)) { 137218887Sdim if (i->Includes(Upper)) { 138218887Sdim newRanges = F.add(newRanges, Range(BV.getValue(Lower), 139218887Sdim BV.getValue(Upper))); 140218887Sdim break; 141218887Sdim } else 142218887Sdim newRanges = F.add(newRanges, Range(BV.getValue(Lower), i->To())); 143218887Sdim } else { 144218887Sdim if (i->Includes(Upper)) { 145218887Sdim newRanges = F.add(newRanges, Range(i->From(), BV.getValue(Upper))); 146218887Sdim break; 147218887Sdim } else 148218887Sdim newRanges = F.add(newRanges, *i); 149218887Sdim } 150218887Sdim } 151218887Sdim } 152218887Sdim 153239462Sdim const llvm::APSInt &getMinValue() const { 154239462Sdim assert(!isEmpty()); 155239462Sdim return ranges.begin()->From(); 156239462Sdim } 157239462Sdim 158239462Sdim bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const { 159239462Sdim // This function has nine cases, the cartesian product of range-testing 160239462Sdim // both the upper and lower bounds against the symbol's type. 161239462Sdim // Each case requires a different pinning operation. 162239462Sdim // The function returns false if the described range is entirely outside 163239462Sdim // the range of values for the associated symbol. 164239462Sdim APSIntType Type(getMinValue()); 165249423Sdim APSIntType::RangeTestResultKind LowerTest = Type.testInRange(Lower, true); 166249423Sdim APSIntType::RangeTestResultKind UpperTest = Type.testInRange(Upper, true); 167239462Sdim 168239462Sdim switch (LowerTest) { 169239462Sdim case APSIntType::RTR_Below: 170239462Sdim switch (UpperTest) { 171239462Sdim case APSIntType::RTR_Below: 172239462Sdim // The entire range is outside the symbol's set of possible values. 173239462Sdim // If this is a conventionally-ordered range, the state is infeasible. 174296417Sdim if (Lower <= Upper) 175239462Sdim return false; 176239462Sdim 177239462Sdim // However, if the range wraps around, it spans all possible values. 178239462Sdim Lower = Type.getMinValue(); 179239462Sdim Upper = Type.getMaxValue(); 180239462Sdim break; 181239462Sdim case APSIntType::RTR_Within: 182239462Sdim // The range starts below what's possible but ends within it. Pin. 183239462Sdim Lower = Type.getMinValue(); 184239462Sdim Type.apply(Upper); 185239462Sdim break; 186239462Sdim case APSIntType::RTR_Above: 187239462Sdim // The range spans all possible values for the symbol. Pin. 188239462Sdim Lower = Type.getMinValue(); 189239462Sdim Upper = Type.getMaxValue(); 190239462Sdim break; 191239462Sdim } 192239462Sdim break; 193239462Sdim case APSIntType::RTR_Within: 194239462Sdim switch (UpperTest) { 195239462Sdim case APSIntType::RTR_Below: 196239462Sdim // The range wraps around, but all lower values are not possible. 197239462Sdim Type.apply(Lower); 198239462Sdim Upper = Type.getMaxValue(); 199239462Sdim break; 200239462Sdim case APSIntType::RTR_Within: 201239462Sdim // The range may or may not wrap around, but both limits are valid. 202239462Sdim Type.apply(Lower); 203239462Sdim Type.apply(Upper); 204239462Sdim break; 205239462Sdim case APSIntType::RTR_Above: 206239462Sdim // The range starts within what's possible but ends above it. Pin. 207239462Sdim Type.apply(Lower); 208239462Sdim Upper = Type.getMaxValue(); 209239462Sdim break; 210239462Sdim } 211239462Sdim break; 212239462Sdim case APSIntType::RTR_Above: 213239462Sdim switch (UpperTest) { 214239462Sdim case APSIntType::RTR_Below: 215239462Sdim // The range wraps but is outside the symbol's set of possible values. 216239462Sdim return false; 217239462Sdim case APSIntType::RTR_Within: 218239462Sdim // The range starts above what's possible but ends within it (wrap). 219239462Sdim Lower = Type.getMinValue(); 220239462Sdim Type.apply(Upper); 221239462Sdim break; 222239462Sdim case APSIntType::RTR_Above: 223239462Sdim // The entire range is outside the symbol's set of possible values. 224239462Sdim // If this is a conventionally-ordered range, the state is infeasible. 225296417Sdim if (Lower <= Upper) 226239462Sdim return false; 227239462Sdim 228239462Sdim // However, if the range wraps around, it spans all possible values. 229239462Sdim Lower = Type.getMinValue(); 230239462Sdim Upper = Type.getMaxValue(); 231239462Sdim break; 232239462Sdim } 233239462Sdim break; 234239462Sdim } 235239462Sdim 236239462Sdim return true; 237239462Sdim } 238239462Sdim 239218887Sdimpublic: 240218887Sdim // Returns a set containing the values in the receiving set, intersected with 241218887Sdim // the closed range [Lower, Upper]. Unlike the Range type, this range uses 242218887Sdim // modular arithmetic, corresponding to the common treatment of C integer 243218887Sdim // overflow. Thus, if the Lower bound is greater than the Upper bound, the 244218887Sdim // range is taken to wrap around. This is equivalent to taking the 245218887Sdim // intersection with the two ranges [Min, Upper] and [Lower, Max], 246218887Sdim // or, alternatively, /removing/ all integers between Upper and Lower. 247218887Sdim RangeSet Intersect(BasicValueFactory &BV, Factory &F, 248239462Sdim llvm::APSInt Lower, llvm::APSInt Upper) const { 249239462Sdim if (!pin(Lower, Upper)) 250239462Sdim return F.getEmptySet(); 251239462Sdim 252218887Sdim PrimRangeSet newRanges = F.getEmptySet(); 253218887Sdim 254218887Sdim PrimRangeSet::iterator i = begin(), e = end(); 255218887Sdim if (Lower <= Upper) 256218887Sdim IntersectInRange(BV, F, Lower, Upper, newRanges, i, e); 257218887Sdim else { 258218887Sdim // The order of the next two statements is important! 259218887Sdim // IntersectInRange() does not reset the iteration state for i and e. 260218887Sdim // Therefore, the lower range most be handled first. 261218887Sdim IntersectInRange(BV, F, BV.getMinValue(Upper), Upper, newRanges, i, e); 262218887Sdim IntersectInRange(BV, F, Lower, BV.getMaxValue(Lower), newRanges, i, e); 263218887Sdim } 264239462Sdim 265218887Sdim return newRanges; 266218887Sdim } 267218887Sdim 268226633Sdim void print(raw_ostream &os) const { 269218887Sdim bool isFirst = true; 270218887Sdim os << "{ "; 271218887Sdim for (iterator i = begin(), e = end(); i != e; ++i) { 272218887Sdim if (isFirst) 273218887Sdim isFirst = false; 274218887Sdim else 275218887Sdim os << ", "; 276218887Sdim 277218887Sdim os << '[' << i->From().toString(10) << ", " << i->To().toString(10) 278218887Sdim << ']'; 279218887Sdim } 280218887Sdim os << " }"; 281218887Sdim } 282218887Sdim 283218887Sdim bool operator==(const RangeSet &other) const { 284218887Sdim return ranges == other.ranges; 285218887Sdim } 286218887Sdim}; 287218887Sdim} // end anonymous namespace 288218887Sdim 289243830SdimREGISTER_TRAIT_WITH_PROGRAMSTATE(ConstraintRange, 290243830Sdim CLANG_ENTO_PROGRAMSTATE_MAP(SymbolRef, 291243830Sdim RangeSet)) 292218887Sdim 293218887Sdimnamespace { 294218887Sdimclass RangeConstraintManager : public SimpleConstraintManager{ 295234353Sdim RangeSet GetRange(ProgramStateRef state, SymbolRef sym); 296218887Sdimpublic: 297249423Sdim RangeConstraintManager(SubEngine *subengine, SValBuilder &SVB) 298249423Sdim : SimpleConstraintManager(subengine, SVB) {} 299218887Sdim 300234353Sdim ProgramStateRef assumeSymNE(ProgramStateRef state, SymbolRef sym, 301218887Sdim const llvm::APSInt& Int, 302276479Sdim const llvm::APSInt& Adjustment) override; 303218887Sdim 304234353Sdim ProgramStateRef assumeSymEQ(ProgramStateRef state, SymbolRef sym, 305218887Sdim const llvm::APSInt& Int, 306276479Sdim const llvm::APSInt& Adjustment) override; 307218887Sdim 308234353Sdim ProgramStateRef assumeSymLT(ProgramStateRef state, SymbolRef sym, 309218887Sdim const llvm::APSInt& Int, 310276479Sdim const llvm::APSInt& Adjustment) override; 311218887Sdim 312234353Sdim ProgramStateRef assumeSymGT(ProgramStateRef state, SymbolRef sym, 313218887Sdim const llvm::APSInt& Int, 314276479Sdim const llvm::APSInt& Adjustment) override; 315218887Sdim 316234353Sdim ProgramStateRef assumeSymGE(ProgramStateRef state, SymbolRef sym, 317218887Sdim const llvm::APSInt& Int, 318276479Sdim const llvm::APSInt& Adjustment) override; 319218887Sdim 320234353Sdim ProgramStateRef assumeSymLE(ProgramStateRef state, SymbolRef sym, 321218887Sdim const llvm::APSInt& Int, 322276479Sdim const llvm::APSInt& Adjustment) override; 323218887Sdim 324296417Sdim ProgramStateRef assumeSymbolWithinInclusiveRange( 325296417Sdim ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 326296417Sdim const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; 327296417Sdim 328296417Sdim ProgramStateRef assumeSymbolOutOfInclusiveRange( 329296417Sdim ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 330296417Sdim const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; 331296417Sdim 332276479Sdim const llvm::APSInt* getSymVal(ProgramStateRef St, 333276479Sdim SymbolRef sym) const override; 334276479Sdim ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override; 335218887Sdim 336276479Sdim ProgramStateRef removeDeadBindings(ProgramStateRef St, 337276479Sdim SymbolReaper& SymReaper) override; 338218887Sdim 339234353Sdim void print(ProgramStateRef St, raw_ostream &Out, 340276479Sdim const char* nl, const char *sep) override; 341218887Sdim 342218887Sdimprivate: 343218887Sdim RangeSet::Factory F; 344296417Sdim RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym, 345296417Sdim const llvm::APSInt &Int, 346296417Sdim const llvm::APSInt &Adjustment); 347296417Sdim RangeSet getSymGTRange(ProgramStateRef St, SymbolRef Sym, 348296417Sdim const llvm::APSInt &Int, 349296417Sdim const llvm::APSInt &Adjustment); 350296417Sdim RangeSet getSymLERange(ProgramStateRef St, SymbolRef Sym, 351296417Sdim const llvm::APSInt &Int, 352296417Sdim const llvm::APSInt &Adjustment); 353296417Sdim RangeSet getSymLERange(const RangeSet &RS, const llvm::APSInt &Int, 354296417Sdim const llvm::APSInt &Adjustment); 355296417Sdim RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym, 356296417Sdim const llvm::APSInt &Int, 357296417Sdim const llvm::APSInt &Adjustment); 358218887Sdim}; 359218887Sdim 360218887Sdim} // end anonymous namespace 361218887Sdim 362280031Sdimstd::unique_ptr<ConstraintManager> 363243830Sdimento::CreateRangeConstraintManager(ProgramStateManager &StMgr, SubEngine *Eng) { 364280031Sdim return llvm::make_unique<RangeConstraintManager>(Eng, StMgr.getSValBuilder()); 365218887Sdim} 366218887Sdim 367234353Sdimconst llvm::APSInt* RangeConstraintManager::getSymVal(ProgramStateRef St, 368218887Sdim SymbolRef sym) const { 369218887Sdim const ConstraintRangeTy::data_type *T = St->get<ConstraintRange>(sym); 370276479Sdim return T ? T->getConcreteValue() : nullptr; 371218887Sdim} 372218887Sdim 373243830SdimConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State, 374243830Sdim SymbolRef Sym) { 375243830Sdim const RangeSet *Ranges = State->get<ConstraintRange>(Sym); 376243830Sdim 377243830Sdim // If we don't have any information about this symbol, it's underconstrained. 378243830Sdim if (!Ranges) 379243830Sdim return ConditionTruthVal(); 380243830Sdim 381243830Sdim // If we have a concrete value, see if it's zero. 382243830Sdim if (const llvm::APSInt *Value = Ranges->getConcreteValue()) 383243830Sdim return *Value == 0; 384243830Sdim 385243830Sdim BasicValueFactory &BV = getBasicVals(); 386243830Sdim APSIntType IntType = BV.getAPSIntType(Sym->getType()); 387243830Sdim llvm::APSInt Zero = IntType.getZeroValue(); 388243830Sdim 389243830Sdim // Check if zero is in the set of possible values. 390243830Sdim if (Ranges->Intersect(BV, F, Zero, Zero).isEmpty()) 391243830Sdim return false; 392243830Sdim 393243830Sdim // Zero is a possible value, but it is not the /only/ possible value. 394243830Sdim return ConditionTruthVal(); 395243830Sdim} 396243830Sdim 397218887Sdim/// Scan all symbols referenced by the constraints. If the symbol is not alive 398218887Sdim/// as marked in LSymbols, mark it as dead in DSymbols. 399296417SdimProgramStateRef 400234353SdimRangeConstraintManager::removeDeadBindings(ProgramStateRef state, 401218887Sdim SymbolReaper& SymReaper) { 402218887Sdim 403218887Sdim ConstraintRangeTy CR = state->get<ConstraintRange>(); 404218887Sdim ConstraintRangeTy::Factory& CRFactory = state->get_context<ConstraintRange>(); 405218887Sdim 406218887Sdim for (ConstraintRangeTy::iterator I = CR.begin(), E = CR.end(); I != E; ++I) { 407218887Sdim SymbolRef sym = I.getKey(); 408218887Sdim if (SymReaper.maybeDead(sym)) 409218887Sdim CR = CRFactory.remove(CR, sym); 410218887Sdim } 411218887Sdim 412218887Sdim return state->set<ConstraintRange>(CR); 413218887Sdim} 414218887Sdim 415218887SdimRangeSet 416234353SdimRangeConstraintManager::GetRange(ProgramStateRef state, SymbolRef sym) { 417218887Sdim if (ConstraintRangeTy::data_type* V = state->get<ConstraintRange>(sym)) 418218887Sdim return *V; 419218887Sdim 420218887Sdim // Lazily generate a new RangeSet representing all possible values for the 421218887Sdim // given symbol type. 422239462Sdim BasicValueFactory &BV = getBasicVals(); 423243830Sdim QualType T = sym->getType(); 424243830Sdim 425243830Sdim RangeSet Result(F, BV.getMinValue(T), BV.getMaxValue(T)); 426243830Sdim 427243830Sdim // Special case: references are known to be non-zero. 428243830Sdim if (T->isReferenceType()) { 429243830Sdim APSIntType IntType = BV.getAPSIntType(T); 430243830Sdim Result = Result.Intersect(BV, F, ++IntType.getZeroValue(), 431243830Sdim --IntType.getZeroValue()); 432243830Sdim } 433243830Sdim 434243830Sdim return Result; 435218887Sdim} 436218887Sdim 437218887Sdim//===------------------------------------------------------------------------=== 438218887Sdim// assumeSymX methods: public interface for RangeConstraintManager. 439218887Sdim//===------------------------------------------------------------------------===/ 440218887Sdim 441218887Sdim// The syntax for ranges below is mathematical, using [x, y] for closed ranges 442218887Sdim// and (x, y) for open ranges. These ranges are modular, corresponding with 443218887Sdim// a common treatment of C integer overflow. This means that these methods 444218887Sdim// do not have to worry about overflow; RangeSet::Intersect can handle such a 445218887Sdim// "wraparound" range. 446218887Sdim// As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1, 447218887Sdim// UINT_MAX, 0, 1, and 2. 448218887Sdim 449296417SdimProgramStateRef 450239462SdimRangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym, 451239462Sdim const llvm::APSInt &Int, 452239462Sdim const llvm::APSInt &Adjustment) { 453239462Sdim // Before we do any real work, see if the value can even show up. 454239462Sdim APSIntType AdjustmentType(Adjustment); 455249423Sdim if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within) 456239462Sdim return St; 457218887Sdim 458239462Sdim llvm::APSInt Lower = AdjustmentType.convert(Int) - Adjustment; 459218887Sdim llvm::APSInt Upper = Lower; 460218887Sdim --Lower; 461218887Sdim ++Upper; 462218887Sdim 463218887Sdim // [Int-Adjustment+1, Int-Adjustment-1] 464218887Sdim // Notice that the lower bound is greater than the upper bound. 465239462Sdim RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Upper, Lower); 466276479Sdim return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); 467218887Sdim} 468218887Sdim 469296417SdimProgramStateRef 470239462SdimRangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym, 471239462Sdim const llvm::APSInt &Int, 472239462Sdim const llvm::APSInt &Adjustment) { 473239462Sdim // Before we do any real work, see if the value can even show up. 474239462Sdim APSIntType AdjustmentType(Adjustment); 475249423Sdim if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within) 476276479Sdim return nullptr; 477239462Sdim 478218887Sdim // [Int-Adjustment, Int-Adjustment] 479239462Sdim llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment; 480239462Sdim RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt); 481276479Sdim return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); 482218887Sdim} 483218887Sdim 484296417SdimRangeSet RangeConstraintManager::getSymLTRange(ProgramStateRef St, 485296417Sdim SymbolRef Sym, 486296417Sdim const llvm::APSInt &Int, 487296417Sdim const llvm::APSInt &Adjustment) { 488239462Sdim // Before we do any real work, see if the value can even show up. 489239462Sdim APSIntType AdjustmentType(Adjustment); 490249423Sdim switch (AdjustmentType.testInRange(Int, true)) { 491239462Sdim case APSIntType::RTR_Below: 492296417Sdim return F.getEmptySet(); 493239462Sdim case APSIntType::RTR_Within: 494239462Sdim break; 495239462Sdim case APSIntType::RTR_Above: 496296417Sdim return GetRange(St, Sym); 497239462Sdim } 498218887Sdim 499218887Sdim // Special case for Int == Min. This is always false. 500239462Sdim llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); 501239462Sdim llvm::APSInt Min = AdjustmentType.getMinValue(); 502239462Sdim if (ComparisonVal == Min) 503296417Sdim return F.getEmptySet(); 504218887Sdim 505296417Sdim llvm::APSInt Lower = Min - Adjustment; 506296417Sdim llvm::APSInt Upper = ComparisonVal - Adjustment; 507218887Sdim --Upper; 508218887Sdim 509296417Sdim return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); 510218887Sdim} 511218887Sdim 512296417SdimProgramStateRef 513296417SdimRangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym, 514239462Sdim const llvm::APSInt &Int, 515239462Sdim const llvm::APSInt &Adjustment) { 516296417Sdim RangeSet New = getSymLTRange(St, Sym, Int, Adjustment); 517296417Sdim return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); 518296417Sdim} 519296417Sdim 520296417SdimRangeSet 521296417SdimRangeConstraintManager::getSymGTRange(ProgramStateRef St, SymbolRef Sym, 522296417Sdim const llvm::APSInt &Int, 523296417Sdim const llvm::APSInt &Adjustment) { 524239462Sdim // Before we do any real work, see if the value can even show up. 525239462Sdim APSIntType AdjustmentType(Adjustment); 526249423Sdim switch (AdjustmentType.testInRange(Int, true)) { 527239462Sdim case APSIntType::RTR_Below: 528296417Sdim return GetRange(St, Sym); 529239462Sdim case APSIntType::RTR_Within: 530239462Sdim break; 531239462Sdim case APSIntType::RTR_Above: 532296417Sdim return F.getEmptySet(); 533239462Sdim } 534218887Sdim 535218887Sdim // Special case for Int == Max. This is always false. 536239462Sdim llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); 537239462Sdim llvm::APSInt Max = AdjustmentType.getMaxValue(); 538239462Sdim if (ComparisonVal == Max) 539296417Sdim return F.getEmptySet(); 540218887Sdim 541296417Sdim llvm::APSInt Lower = ComparisonVal - Adjustment; 542296417Sdim llvm::APSInt Upper = Max - Adjustment; 543218887Sdim ++Lower; 544218887Sdim 545296417Sdim return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); 546218887Sdim} 547218887Sdim 548296417SdimProgramStateRef 549296417SdimRangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym, 550239462Sdim const llvm::APSInt &Int, 551239462Sdim const llvm::APSInt &Adjustment) { 552296417Sdim RangeSet New = getSymGTRange(St, Sym, Int, Adjustment); 553296417Sdim return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); 554296417Sdim} 555296417Sdim 556296417SdimRangeSet 557296417SdimRangeConstraintManager::getSymGERange(ProgramStateRef St, SymbolRef Sym, 558296417Sdim const llvm::APSInt &Int, 559296417Sdim const llvm::APSInt &Adjustment) { 560239462Sdim // Before we do any real work, see if the value can even show up. 561239462Sdim APSIntType AdjustmentType(Adjustment); 562249423Sdim switch (AdjustmentType.testInRange(Int, true)) { 563239462Sdim case APSIntType::RTR_Below: 564296417Sdim return GetRange(St, Sym); 565239462Sdim case APSIntType::RTR_Within: 566239462Sdim break; 567239462Sdim case APSIntType::RTR_Above: 568296417Sdim return F.getEmptySet(); 569239462Sdim } 570218887Sdim 571218887Sdim // Special case for Int == Min. This is always feasible. 572239462Sdim llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); 573239462Sdim llvm::APSInt Min = AdjustmentType.getMinValue(); 574239462Sdim if (ComparisonVal == Min) 575296417Sdim return GetRange(St, Sym); 576218887Sdim 577239462Sdim llvm::APSInt Max = AdjustmentType.getMaxValue(); 578296417Sdim llvm::APSInt Lower = ComparisonVal - Adjustment; 579296417Sdim llvm::APSInt Upper = Max - Adjustment; 580218887Sdim 581296417Sdim return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); 582218887Sdim} 583218887Sdim 584296417SdimProgramStateRef 585296417SdimRangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym, 586239462Sdim const llvm::APSInt &Int, 587239462Sdim const llvm::APSInt &Adjustment) { 588296417Sdim RangeSet New = getSymGERange(St, Sym, Int, Adjustment); 589296417Sdim return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); 590296417Sdim} 591296417Sdim 592296417SdimRangeSet 593296417SdimRangeConstraintManager::getSymLERange(const RangeSet &RS, 594296417Sdim const llvm::APSInt &Int, 595296417Sdim const llvm::APSInt &Adjustment) { 596239462Sdim // Before we do any real work, see if the value can even show up. 597239462Sdim APSIntType AdjustmentType(Adjustment); 598249423Sdim switch (AdjustmentType.testInRange(Int, true)) { 599239462Sdim case APSIntType::RTR_Below: 600296417Sdim return F.getEmptySet(); 601239462Sdim case APSIntType::RTR_Within: 602239462Sdim break; 603239462Sdim case APSIntType::RTR_Above: 604296417Sdim return RS; 605239462Sdim } 606218887Sdim 607218887Sdim // Special case for Int == Max. This is always feasible. 608239462Sdim llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); 609239462Sdim llvm::APSInt Max = AdjustmentType.getMaxValue(); 610239462Sdim if (ComparisonVal == Max) 611296417Sdim return RS; 612218887Sdim 613239462Sdim llvm::APSInt Min = AdjustmentType.getMinValue(); 614296417Sdim llvm::APSInt Lower = Min - Adjustment; 615296417Sdim llvm::APSInt Upper = ComparisonVal - Adjustment; 616218887Sdim 617296417Sdim return RS.Intersect(getBasicVals(), F, Lower, Upper); 618296417Sdim} 619296417Sdim 620296417SdimRangeSet 621296417SdimRangeConstraintManager::getSymLERange(ProgramStateRef St, SymbolRef Sym, 622296417Sdim const llvm::APSInt &Int, 623296417Sdim const llvm::APSInt &Adjustment) { 624296417Sdim // Before we do any real work, see if the value can even show up. 625296417Sdim APSIntType AdjustmentType(Adjustment); 626296417Sdim switch (AdjustmentType.testInRange(Int, true)) { 627296417Sdim case APSIntType::RTR_Below: 628296417Sdim return F.getEmptySet(); 629296417Sdim case APSIntType::RTR_Within: 630296417Sdim break; 631296417Sdim case APSIntType::RTR_Above: 632296417Sdim return GetRange(St, Sym); 633296417Sdim } 634296417Sdim 635296417Sdim // Special case for Int == Max. This is always feasible. 636296417Sdim llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); 637296417Sdim llvm::APSInt Max = AdjustmentType.getMaxValue(); 638296417Sdim if (ComparisonVal == Max) 639296417Sdim return GetRange(St, Sym); 640296417Sdim 641296417Sdim llvm::APSInt Min = AdjustmentType.getMinValue(); 642296417Sdim llvm::APSInt Lower = Min - Adjustment; 643296417Sdim llvm::APSInt Upper = ComparisonVal - Adjustment; 644296417Sdim 645296417Sdim return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); 646296417Sdim} 647296417Sdim 648296417SdimProgramStateRef 649296417SdimRangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym, 650296417Sdim const llvm::APSInt &Int, 651296417Sdim const llvm::APSInt &Adjustment) { 652296417Sdim RangeSet New = getSymLERange(St, Sym, Int, Adjustment); 653276479Sdim return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); 654218887Sdim} 655218887Sdim 656296417SdimProgramStateRef 657296417SdimRangeConstraintManager::assumeSymbolWithinInclusiveRange( 658296417Sdim ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 659296417Sdim const llvm::APSInt &To, const llvm::APSInt &Adjustment) { 660296417Sdim RangeSet New = getSymGERange(State, Sym, From, Adjustment); 661296417Sdim if (New.isEmpty()) 662296417Sdim return nullptr; 663296417Sdim New = getSymLERange(New, To, Adjustment); 664296417Sdim return New.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, New); 665296417Sdim} 666296417Sdim 667296417SdimProgramStateRef 668296417SdimRangeConstraintManager::assumeSymbolOutOfInclusiveRange( 669296417Sdim ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 670296417Sdim const llvm::APSInt &To, const llvm::APSInt &Adjustment) { 671296417Sdim RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment); 672296417Sdim RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment); 673296417Sdim RangeSet New(RangeLT.addRange(F, RangeGT)); 674296417Sdim return New.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, New); 675296417Sdim} 676296417Sdim 677218887Sdim//===------------------------------------------------------------------------=== 678218887Sdim// Pretty-printing. 679218887Sdim//===------------------------------------------------------------------------===/ 680218887Sdim 681234353Sdimvoid RangeConstraintManager::print(ProgramStateRef St, raw_ostream &Out, 682218887Sdim const char* nl, const char *sep) { 683218887Sdim 684218887Sdim ConstraintRangeTy Ranges = St->get<ConstraintRange>(); 685218887Sdim 686234353Sdim if (Ranges.isEmpty()) { 687234353Sdim Out << nl << sep << "Ranges are empty." << nl; 688218887Sdim return; 689234353Sdim } 690218887Sdim 691234353Sdim Out << nl << sep << "Ranges of symbol values:"; 692218887Sdim for (ConstraintRangeTy::iterator I=Ranges.begin(), E=Ranges.end(); I!=E; ++I){ 693218887Sdim Out << nl << ' ' << I.getKey() << " : "; 694218887Sdim I.getData().print(Out); 695218887Sdim } 696234353Sdim Out << nl; 697218887Sdim} 698