RangeConstraintManager.cpp revision 360784
1//== RangeConstraintManager.cpp - Manage range constraints.------*- C++ -*--==// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8// 9// This file defines RangeConstraintManager, a class that tracks simple 10// equality and inequality constraints on symbolic values of ProgramState. 11// 12//===----------------------------------------------------------------------===// 13 14#include "clang/Basic/JsonSupport.h" 15#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h" 16#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 17#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 18#include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h" 19#include "llvm/ADT/FoldingSet.h" 20#include "llvm/ADT/ImmutableSet.h" 21#include "llvm/Support/raw_ostream.h" 22 23using namespace clang; 24using namespace ento; 25 26void RangeSet::IntersectInRange(BasicValueFactory &BV, Factory &F, 27 const llvm::APSInt &Lower, const llvm::APSInt &Upper, 28 PrimRangeSet &newRanges, PrimRangeSet::iterator &i, 29 PrimRangeSet::iterator &e) const { 30 // There are six cases for each range R in the set: 31 // 1. R is entirely before the intersection range. 32 // 2. R is entirely after the intersection range. 33 // 3. R contains the entire intersection range. 34 // 4. R starts before the intersection range and ends in the middle. 35 // 5. R starts in the middle of the intersection range and ends after it. 36 // 6. R is entirely contained in the intersection range. 37 // These correspond to each of the conditions below. 38 for (/* i = begin(), e = end() */; i != e; ++i) { 39 if (i->To() < Lower) { 40 continue; 41 } 42 if (i->From() > Upper) { 43 break; 44 } 45 46 if (i->Includes(Lower)) { 47 if (i->Includes(Upper)) { 48 newRanges = 49 F.add(newRanges, Range(BV.getValue(Lower), BV.getValue(Upper))); 50 break; 51 } else 52 newRanges = F.add(newRanges, Range(BV.getValue(Lower), i->To())); 53 } else { 54 if (i->Includes(Upper)) { 55 newRanges = F.add(newRanges, Range(i->From(), BV.getValue(Upper))); 56 break; 57 } else 58 newRanges = F.add(newRanges, *i); 59 } 60 } 61} 62 63const llvm::APSInt &RangeSet::getMinValue() const { 64 assert(!isEmpty()); 65 return ranges.begin()->From(); 66} 67 68bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const { 69 // This function has nine cases, the cartesian product of range-testing 70 // both the upper and lower bounds against the symbol's type. 71 // Each case requires a different pinning operation. 72 // The function returns false if the described range is entirely outside 73 // the range of values for the associated symbol. 74 APSIntType Type(getMinValue()); 75 APSIntType::RangeTestResultKind LowerTest = Type.testInRange(Lower, true); 76 APSIntType::RangeTestResultKind UpperTest = Type.testInRange(Upper, true); 77 78 switch (LowerTest) { 79 case APSIntType::RTR_Below: 80 switch (UpperTest) { 81 case APSIntType::RTR_Below: 82 // The entire range is outside the symbol's set of possible values. 83 // If this is a conventionally-ordered range, the state is infeasible. 84 if (Lower <= Upper) 85 return false; 86 87 // However, if the range wraps around, it spans all possible values. 88 Lower = Type.getMinValue(); 89 Upper = Type.getMaxValue(); 90 break; 91 case APSIntType::RTR_Within: 92 // The range starts below what's possible but ends within it. Pin. 93 Lower = Type.getMinValue(); 94 Type.apply(Upper); 95 break; 96 case APSIntType::RTR_Above: 97 // The range spans all possible values for the symbol. Pin. 98 Lower = Type.getMinValue(); 99 Upper = Type.getMaxValue(); 100 break; 101 } 102 break; 103 case APSIntType::RTR_Within: 104 switch (UpperTest) { 105 case APSIntType::RTR_Below: 106 // The range wraps around, but all lower values are not possible. 107 Type.apply(Lower); 108 Upper = Type.getMaxValue(); 109 break; 110 case APSIntType::RTR_Within: 111 // The range may or may not wrap around, but both limits are valid. 112 Type.apply(Lower); 113 Type.apply(Upper); 114 break; 115 case APSIntType::RTR_Above: 116 // The range starts within what's possible but ends above it. Pin. 117 Type.apply(Lower); 118 Upper = Type.getMaxValue(); 119 break; 120 } 121 break; 122 case APSIntType::RTR_Above: 123 switch (UpperTest) { 124 case APSIntType::RTR_Below: 125 // The range wraps but is outside the symbol's set of possible values. 126 return false; 127 case APSIntType::RTR_Within: 128 // The range starts above what's possible but ends within it (wrap). 129 Lower = Type.getMinValue(); 130 Type.apply(Upper); 131 break; 132 case APSIntType::RTR_Above: 133 // The entire range is outside the symbol's set of possible values. 134 // If this is a conventionally-ordered range, the state is infeasible. 135 if (Lower <= Upper) 136 return false; 137 138 // However, if the range wraps around, it spans all possible values. 139 Lower = Type.getMinValue(); 140 Upper = Type.getMaxValue(); 141 break; 142 } 143 break; 144 } 145 146 return true; 147} 148 149// Returns a set containing the values in the receiving set, intersected with 150// the closed range [Lower, Upper]. Unlike the Range type, this range uses 151// modular arithmetic, corresponding to the common treatment of C integer 152// overflow. Thus, if the Lower bound is greater than the Upper bound, the 153// range is taken to wrap around. This is equivalent to taking the 154// intersection with the two ranges [Min, Upper] and [Lower, Max], 155// or, alternatively, /removing/ all integers between Upper and Lower. 156RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F, 157 llvm::APSInt Lower, llvm::APSInt Upper) const { 158 if (!pin(Lower, Upper)) 159 return F.getEmptySet(); 160 161 PrimRangeSet newRanges = F.getEmptySet(); 162 163 PrimRangeSet::iterator i = begin(), e = end(); 164 if (Lower <= Upper) 165 IntersectInRange(BV, F, Lower, Upper, newRanges, i, e); 166 else { 167 // The order of the next two statements is important! 168 // IntersectInRange() does not reset the iteration state for i and e. 169 // Therefore, the lower range most be handled first. 170 IntersectInRange(BV, F, BV.getMinValue(Upper), Upper, newRanges, i, e); 171 IntersectInRange(BV, F, Lower, BV.getMaxValue(Lower), newRanges, i, e); 172 } 173 174 return newRanges; 175} 176 177// Returns a set containing the values in the receiving set, intersected with 178// the range set passed as parameter. 179RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F, 180 const RangeSet &Other) const { 181 PrimRangeSet newRanges = F.getEmptySet(); 182 183 for (iterator i = Other.begin(), e = Other.end(); i != e; ++i) { 184 RangeSet newPiece = Intersect(BV, F, i->From(), i->To()); 185 for (iterator j = newPiece.begin(), ee = newPiece.end(); j != ee; ++j) { 186 newRanges = F.add(newRanges, *j); 187 } 188 } 189 190 return newRanges; 191} 192 193// Turn all [A, B] ranges to [-B, -A]. Ranges [MIN, B] are turned to range set 194// [MIN, MIN] U [-B, MAX], when MIN and MAX are the minimal and the maximal 195// signed values of the type. 196RangeSet RangeSet::Negate(BasicValueFactory &BV, Factory &F) const { 197 PrimRangeSet newRanges = F.getEmptySet(); 198 199 for (iterator i = begin(), e = end(); i != e; ++i) { 200 const llvm::APSInt &from = i->From(), &to = i->To(); 201 const llvm::APSInt &newTo = (from.isMinSignedValue() ? 202 BV.getMaxValue(from) : 203 BV.getValue(- from)); 204 if (to.isMaxSignedValue() && !newRanges.isEmpty() && 205 newRanges.begin()->From().isMinSignedValue()) { 206 assert(newRanges.begin()->To().isMinSignedValue() && 207 "Ranges should not overlap"); 208 assert(!from.isMinSignedValue() && "Ranges should not overlap"); 209 const llvm::APSInt &newFrom = newRanges.begin()->From(); 210 newRanges = 211 F.add(F.remove(newRanges, *newRanges.begin()), Range(newFrom, newTo)); 212 } else if (!to.isMinSignedValue()) { 213 const llvm::APSInt &newFrom = BV.getValue(- to); 214 newRanges = F.add(newRanges, Range(newFrom, newTo)); 215 } 216 if (from.isMinSignedValue()) { 217 newRanges = F.add(newRanges, Range(BV.getMinValue(from), 218 BV.getMinValue(from))); 219 } 220 } 221 222 return newRanges; 223} 224 225void RangeSet::print(raw_ostream &os) const { 226 bool isFirst = true; 227 os << "{ "; 228 for (iterator i = begin(), e = end(); i != e; ++i) { 229 if (isFirst) 230 isFirst = false; 231 else 232 os << ", "; 233 234 os << '[' << i->From().toString(10) << ", " << i->To().toString(10) 235 << ']'; 236 } 237 os << " }"; 238} 239 240namespace { 241class RangeConstraintManager : public RangedConstraintManager { 242public: 243 RangeConstraintManager(SubEngine *SE, SValBuilder &SVB) 244 : RangedConstraintManager(SE, SVB) {} 245 246 //===------------------------------------------------------------------===// 247 // Implementation for interface from ConstraintManager. 248 //===------------------------------------------------------------------===// 249 250 bool haveEqualConstraints(ProgramStateRef S1, 251 ProgramStateRef S2) const override { 252 return S1->get<ConstraintRange>() == S2->get<ConstraintRange>(); 253 } 254 255 bool canReasonAbout(SVal X) const override; 256 257 ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override; 258 259 const llvm::APSInt *getSymVal(ProgramStateRef State, 260 SymbolRef Sym) const override; 261 262 ProgramStateRef removeDeadBindings(ProgramStateRef State, 263 SymbolReaper &SymReaper) override; 264 265 void printJson(raw_ostream &Out, ProgramStateRef State, const char *NL = "\n", 266 unsigned int Space = 0, bool IsDot = false) const override; 267 268 //===------------------------------------------------------------------===// 269 // Implementation for interface from RangedConstraintManager. 270 //===------------------------------------------------------------------===// 271 272 ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym, 273 const llvm::APSInt &V, 274 const llvm::APSInt &Adjustment) override; 275 276 ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym, 277 const llvm::APSInt &V, 278 const llvm::APSInt &Adjustment) override; 279 280 ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym, 281 const llvm::APSInt &V, 282 const llvm::APSInt &Adjustment) override; 283 284 ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym, 285 const llvm::APSInt &V, 286 const llvm::APSInt &Adjustment) override; 287 288 ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym, 289 const llvm::APSInt &V, 290 const llvm::APSInt &Adjustment) override; 291 292 ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym, 293 const llvm::APSInt &V, 294 const llvm::APSInt &Adjustment) override; 295 296 ProgramStateRef assumeSymWithinInclusiveRange( 297 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 298 const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; 299 300 ProgramStateRef assumeSymOutsideInclusiveRange( 301 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 302 const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; 303 304private: 305 RangeSet::Factory F; 306 307 RangeSet getRange(ProgramStateRef State, SymbolRef Sym); 308 const RangeSet* getRangeForMinusSymbol(ProgramStateRef State, 309 SymbolRef Sym); 310 311 RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym, 312 const llvm::APSInt &Int, 313 const llvm::APSInt &Adjustment); 314 RangeSet getSymGTRange(ProgramStateRef St, SymbolRef Sym, 315 const llvm::APSInt &Int, 316 const llvm::APSInt &Adjustment); 317 RangeSet getSymLERange(ProgramStateRef St, SymbolRef Sym, 318 const llvm::APSInt &Int, 319 const llvm::APSInt &Adjustment); 320 RangeSet getSymLERange(llvm::function_ref<RangeSet()> RS, 321 const llvm::APSInt &Int, 322 const llvm::APSInt &Adjustment); 323 RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym, 324 const llvm::APSInt &Int, 325 const llvm::APSInt &Adjustment); 326 327}; 328 329} // end anonymous namespace 330 331std::unique_ptr<ConstraintManager> 332ento::CreateRangeConstraintManager(ProgramStateManager &StMgr, SubEngine *Eng) { 333 return std::make_unique<RangeConstraintManager>(Eng, StMgr.getSValBuilder()); 334} 335 336bool RangeConstraintManager::canReasonAbout(SVal X) const { 337 Optional<nonloc::SymbolVal> SymVal = X.getAs<nonloc::SymbolVal>(); 338 if (SymVal && SymVal->isExpression()) { 339 const SymExpr *SE = SymVal->getSymbol(); 340 341 if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) { 342 switch (SIE->getOpcode()) { 343 // We don't reason yet about bitwise-constraints on symbolic values. 344 case BO_And: 345 case BO_Or: 346 case BO_Xor: 347 return false; 348 // We don't reason yet about these arithmetic constraints on 349 // symbolic values. 350 case BO_Mul: 351 case BO_Div: 352 case BO_Rem: 353 case BO_Shl: 354 case BO_Shr: 355 return false; 356 // All other cases. 357 default: 358 return true; 359 } 360 } 361 362 if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) { 363 // FIXME: Handle <=> here. 364 if (BinaryOperator::isEqualityOp(SSE->getOpcode()) || 365 BinaryOperator::isRelationalOp(SSE->getOpcode())) { 366 // We handle Loc <> Loc comparisons, but not (yet) NonLoc <> NonLoc. 367 // We've recently started producing Loc <> NonLoc comparisons (that 368 // result from casts of one of the operands between eg. intptr_t and 369 // void *), but we can't reason about them yet. 370 if (Loc::isLocType(SSE->getLHS()->getType())) { 371 return Loc::isLocType(SSE->getRHS()->getType()); 372 } 373 } 374 } 375 376 return false; 377 } 378 379 return true; 380} 381 382ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State, 383 SymbolRef Sym) { 384 const RangeSet *Ranges = State->get<ConstraintRange>(Sym); 385 386 // If we don't have any information about this symbol, it's underconstrained. 387 if (!Ranges) 388 return ConditionTruthVal(); 389 390 // If we have a concrete value, see if it's zero. 391 if (const llvm::APSInt *Value = Ranges->getConcreteValue()) 392 return *Value == 0; 393 394 BasicValueFactory &BV = getBasicVals(); 395 APSIntType IntType = BV.getAPSIntType(Sym->getType()); 396 llvm::APSInt Zero = IntType.getZeroValue(); 397 398 // Check if zero is in the set of possible values. 399 if (Ranges->Intersect(BV, F, Zero, Zero).isEmpty()) 400 return false; 401 402 // Zero is a possible value, but it is not the /only/ possible value. 403 return ConditionTruthVal(); 404} 405 406const llvm::APSInt *RangeConstraintManager::getSymVal(ProgramStateRef St, 407 SymbolRef Sym) const { 408 const ConstraintRangeTy::data_type *T = St->get<ConstraintRange>(Sym); 409 return T ? T->getConcreteValue() : nullptr; 410} 411 412/// Scan all symbols referenced by the constraints. If the symbol is not alive 413/// as marked in LSymbols, mark it as dead in DSymbols. 414ProgramStateRef 415RangeConstraintManager::removeDeadBindings(ProgramStateRef State, 416 SymbolReaper &SymReaper) { 417 bool Changed = false; 418 ConstraintRangeTy CR = State->get<ConstraintRange>(); 419 ConstraintRangeTy::Factory &CRFactory = State->get_context<ConstraintRange>(); 420 421 for (ConstraintRangeTy::iterator I = CR.begin(), E = CR.end(); I != E; ++I) { 422 SymbolRef Sym = I.getKey(); 423 if (SymReaper.isDead(Sym)) { 424 Changed = true; 425 CR = CRFactory.remove(CR, Sym); 426 } 427 } 428 429 return Changed ? State->set<ConstraintRange>(CR) : State; 430} 431 432/// Return a range set subtracting zero from \p Domain. 433static RangeSet assumeNonZero( 434 BasicValueFactory &BV, 435 RangeSet::Factory &F, 436 SymbolRef Sym, 437 RangeSet Domain) { 438 APSIntType IntType = BV.getAPSIntType(Sym->getType()); 439 return Domain.Intersect(BV, F, ++IntType.getZeroValue(), 440 --IntType.getZeroValue()); 441} 442 443/// Apply implicit constraints for bitwise OR- and AND-. 444/// For unsigned types, bitwise OR with a constant always returns 445/// a value greater-or-equal than the constant, and bitwise AND 446/// returns a value less-or-equal then the constant. 447/// 448/// Pattern matches the expression \p Sym against those rule, 449/// and applies the required constraints. 450/// \p Input Previously established expression range set 451static RangeSet applyBitwiseConstraints( 452 BasicValueFactory &BV, 453 RangeSet::Factory &F, 454 RangeSet Input, 455 const SymIntExpr* SIE) { 456 QualType T = SIE->getType(); 457 bool IsUnsigned = T->isUnsignedIntegerType(); 458 const llvm::APSInt &RHS = SIE->getRHS(); 459 const llvm::APSInt &Zero = BV.getAPSIntType(T).getZeroValue(); 460 BinaryOperator::Opcode Operator = SIE->getOpcode(); 461 462 // For unsigned types, the output of bitwise-or is bigger-or-equal than RHS. 463 if (Operator == BO_Or && IsUnsigned) 464 return Input.Intersect(BV, F, RHS, BV.getMaxValue(T)); 465 466 // Bitwise-or with a non-zero constant is always non-zero. 467 if (Operator == BO_Or && RHS != Zero) 468 return assumeNonZero(BV, F, SIE, Input); 469 470 // For unsigned types, or positive RHS, 471 // bitwise-and output is always smaller-or-equal than RHS (assuming two's 472 // complement representation of signed types). 473 if (Operator == BO_And && (IsUnsigned || RHS >= Zero)) 474 return Input.Intersect(BV, F, BV.getMinValue(T), RHS); 475 476 return Input; 477} 478 479RangeSet RangeConstraintManager::getRange(ProgramStateRef State, 480 SymbolRef Sym) { 481 ConstraintRangeTy::data_type *V = State->get<ConstraintRange>(Sym); 482 483 // If Sym is a difference of symbols A - B, then maybe we have range set 484 // stored for B - A. 485 BasicValueFactory &BV = getBasicVals(); 486 const RangeSet *R = getRangeForMinusSymbol(State, Sym); 487 488 // If we have range set stored for both A - B and B - A then calculate the 489 // effective range set by intersecting the range set for A - B and the 490 // negated range set of B - A. 491 if (V && R) 492 return V->Intersect(BV, F, R->Negate(BV, F)); 493 if (V) 494 return *V; 495 if (R) 496 return R->Negate(BV, F); 497 498 // Lazily generate a new RangeSet representing all possible values for the 499 // given symbol type. 500 QualType T = Sym->getType(); 501 502 RangeSet Result(F, BV.getMinValue(T), BV.getMaxValue(T)); 503 504 // References are known to be non-zero. 505 if (T->isReferenceType()) 506 return assumeNonZero(BV, F, Sym, Result); 507 508 // Known constraints on ranges of bitwise expressions. 509 if (const SymIntExpr* SIE = dyn_cast<SymIntExpr>(Sym)) 510 return applyBitwiseConstraints(BV, F, Result, SIE); 511 512 return Result; 513} 514 515// FIXME: Once SValBuilder supports unary minus, we should use SValBuilder to 516// obtain the negated symbolic expression instead of constructing the 517// symbol manually. This will allow us to support finding ranges of not 518// only negated SymSymExpr-type expressions, but also of other, simpler 519// expressions which we currently do not know how to negate. 520const RangeSet* 521RangeConstraintManager::getRangeForMinusSymbol(ProgramStateRef State, 522 SymbolRef Sym) { 523 if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) { 524 if (SSE->getOpcode() == BO_Sub) { 525 QualType T = Sym->getType(); 526 SymbolManager &SymMgr = State->getSymbolManager(); 527 SymbolRef negSym = SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, 528 SSE->getLHS(), T); 529 if (const RangeSet *negV = State->get<ConstraintRange>(negSym)) { 530 // Unsigned range set cannot be negated, unless it is [0, 0]. 531 if ((negV->getConcreteValue() && 532 (*negV->getConcreteValue() == 0)) || 533 T->isSignedIntegerOrEnumerationType()) 534 return negV; 535 } 536 } 537 } 538 return nullptr; 539} 540 541//===------------------------------------------------------------------------=== 542// assumeSymX methods: protected interface for RangeConstraintManager. 543//===------------------------------------------------------------------------===/ 544 545// The syntax for ranges below is mathematical, using [x, y] for closed ranges 546// and (x, y) for open ranges. These ranges are modular, corresponding with 547// a common treatment of C integer overflow. This means that these methods 548// do not have to worry about overflow; RangeSet::Intersect can handle such a 549// "wraparound" range. 550// As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1, 551// UINT_MAX, 0, 1, and 2. 552 553ProgramStateRef 554RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym, 555 const llvm::APSInt &Int, 556 const llvm::APSInt &Adjustment) { 557 // Before we do any real work, see if the value can even show up. 558 APSIntType AdjustmentType(Adjustment); 559 if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within) 560 return St; 561 562 llvm::APSInt Lower = AdjustmentType.convert(Int) - Adjustment; 563 llvm::APSInt Upper = Lower; 564 --Lower; 565 ++Upper; 566 567 // [Int-Adjustment+1, Int-Adjustment-1] 568 // Notice that the lower bound is greater than the upper bound. 569 RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, Upper, Lower); 570 return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); 571} 572 573ProgramStateRef 574RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym, 575 const llvm::APSInt &Int, 576 const llvm::APSInt &Adjustment) { 577 // Before we do any real work, see if the value can even show up. 578 APSIntType AdjustmentType(Adjustment); 579 if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within) 580 return nullptr; 581 582 // [Int-Adjustment, Int-Adjustment] 583 llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment; 584 RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt); 585 return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); 586} 587 588RangeSet RangeConstraintManager::getSymLTRange(ProgramStateRef St, 589 SymbolRef Sym, 590 const llvm::APSInt &Int, 591 const llvm::APSInt &Adjustment) { 592 // Before we do any real work, see if the value can even show up. 593 APSIntType AdjustmentType(Adjustment); 594 switch (AdjustmentType.testInRange(Int, true)) { 595 case APSIntType::RTR_Below: 596 return F.getEmptySet(); 597 case APSIntType::RTR_Within: 598 break; 599 case APSIntType::RTR_Above: 600 return getRange(St, Sym); 601 } 602 603 // Special case for Int == Min. This is always false. 604 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); 605 llvm::APSInt Min = AdjustmentType.getMinValue(); 606 if (ComparisonVal == Min) 607 return F.getEmptySet(); 608 609 llvm::APSInt Lower = Min - Adjustment; 610 llvm::APSInt Upper = ComparisonVal - Adjustment; 611 --Upper; 612 613 return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); 614} 615 616ProgramStateRef 617RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym, 618 const llvm::APSInt &Int, 619 const llvm::APSInt &Adjustment) { 620 RangeSet New = getSymLTRange(St, Sym, Int, Adjustment); 621 return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); 622} 623 624RangeSet RangeConstraintManager::getSymGTRange(ProgramStateRef St, 625 SymbolRef Sym, 626 const llvm::APSInt &Int, 627 const llvm::APSInt &Adjustment) { 628 // Before we do any real work, see if the value can even show up. 629 APSIntType AdjustmentType(Adjustment); 630 switch (AdjustmentType.testInRange(Int, true)) { 631 case APSIntType::RTR_Below: 632 return getRange(St, Sym); 633 case APSIntType::RTR_Within: 634 break; 635 case APSIntType::RTR_Above: 636 return F.getEmptySet(); 637 } 638 639 // Special case for Int == Max. This is always false. 640 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); 641 llvm::APSInt Max = AdjustmentType.getMaxValue(); 642 if (ComparisonVal == Max) 643 return F.getEmptySet(); 644 645 llvm::APSInt Lower = ComparisonVal - Adjustment; 646 llvm::APSInt Upper = Max - Adjustment; 647 ++Lower; 648 649 return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); 650} 651 652ProgramStateRef 653RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym, 654 const llvm::APSInt &Int, 655 const llvm::APSInt &Adjustment) { 656 RangeSet New = getSymGTRange(St, Sym, Int, Adjustment); 657 return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); 658} 659 660RangeSet RangeConstraintManager::getSymGERange(ProgramStateRef St, 661 SymbolRef Sym, 662 const llvm::APSInt &Int, 663 const llvm::APSInt &Adjustment) { 664 // Before we do any real work, see if the value can even show up. 665 APSIntType AdjustmentType(Adjustment); 666 switch (AdjustmentType.testInRange(Int, true)) { 667 case APSIntType::RTR_Below: 668 return getRange(St, Sym); 669 case APSIntType::RTR_Within: 670 break; 671 case APSIntType::RTR_Above: 672 return F.getEmptySet(); 673 } 674 675 // Special case for Int == Min. This is always feasible. 676 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); 677 llvm::APSInt Min = AdjustmentType.getMinValue(); 678 if (ComparisonVal == Min) 679 return getRange(St, Sym); 680 681 llvm::APSInt Max = AdjustmentType.getMaxValue(); 682 llvm::APSInt Lower = ComparisonVal - Adjustment; 683 llvm::APSInt Upper = Max - Adjustment; 684 685 return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); 686} 687 688ProgramStateRef 689RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym, 690 const llvm::APSInt &Int, 691 const llvm::APSInt &Adjustment) { 692 RangeSet New = getSymGERange(St, Sym, Int, Adjustment); 693 return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); 694} 695 696RangeSet RangeConstraintManager::getSymLERange( 697 llvm::function_ref<RangeSet()> RS, 698 const llvm::APSInt &Int, 699 const llvm::APSInt &Adjustment) { 700 // Before we do any real work, see if the value can even show up. 701 APSIntType AdjustmentType(Adjustment); 702 switch (AdjustmentType.testInRange(Int, true)) { 703 case APSIntType::RTR_Below: 704 return F.getEmptySet(); 705 case APSIntType::RTR_Within: 706 break; 707 case APSIntType::RTR_Above: 708 return RS(); 709 } 710 711 // Special case for Int == Max. This is always feasible. 712 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); 713 llvm::APSInt Max = AdjustmentType.getMaxValue(); 714 if (ComparisonVal == Max) 715 return RS(); 716 717 llvm::APSInt Min = AdjustmentType.getMinValue(); 718 llvm::APSInt Lower = Min - Adjustment; 719 llvm::APSInt Upper = ComparisonVal - Adjustment; 720 721 return RS().Intersect(getBasicVals(), F, Lower, Upper); 722} 723 724RangeSet RangeConstraintManager::getSymLERange(ProgramStateRef St, 725 SymbolRef Sym, 726 const llvm::APSInt &Int, 727 const llvm::APSInt &Adjustment) { 728 return getSymLERange([&] { return getRange(St, Sym); }, Int, Adjustment); 729} 730 731ProgramStateRef 732RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym, 733 const llvm::APSInt &Int, 734 const llvm::APSInt &Adjustment) { 735 RangeSet New = getSymLERange(St, Sym, Int, Adjustment); 736 return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); 737} 738 739ProgramStateRef RangeConstraintManager::assumeSymWithinInclusiveRange( 740 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 741 const llvm::APSInt &To, const llvm::APSInt &Adjustment) { 742 RangeSet New = getSymGERange(State, Sym, From, Adjustment); 743 if (New.isEmpty()) 744 return nullptr; 745 RangeSet Out = getSymLERange([&] { return New; }, To, Adjustment); 746 return Out.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, Out); 747} 748 749ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange( 750 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 751 const llvm::APSInt &To, const llvm::APSInt &Adjustment) { 752 RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment); 753 RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment); 754 RangeSet New(RangeLT.addRange(F, RangeGT)); 755 return New.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, New); 756} 757 758//===----------------------------------------------------------------------===// 759// Pretty-printing. 760//===----------------------------------------------------------------------===// 761 762void RangeConstraintManager::printJson(raw_ostream &Out, ProgramStateRef State, 763 const char *NL, unsigned int Space, 764 bool IsDot) const { 765 ConstraintRangeTy Constraints = State->get<ConstraintRange>(); 766 767 Indent(Out, Space, IsDot) << "\"constraints\": "; 768 if (Constraints.isEmpty()) { 769 Out << "null," << NL; 770 return; 771 } 772 773 ++Space; 774 Out << '[' << NL; 775 for (ConstraintRangeTy::iterator I = Constraints.begin(); 776 I != Constraints.end(); ++I) { 777 Indent(Out, Space, IsDot) 778 << "{ \"symbol\": \"" << I.getKey() << "\", \"range\": \""; 779 I.getData().print(Out); 780 Out << "\" }"; 781 782 if (std::next(I) != Constraints.end()) 783 Out << ','; 784 Out << NL; 785 } 786 787 --Space; 788 Indent(Out, Space, IsDot) << "]," << NL; 789} 790