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 "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h" 20 #include "llvm/ADT/FoldingSet.h" 21 #include "llvm/ADT/ImmutableSet.h" 22 #include "llvm/Support/raw_ostream.h" 23 24 using namespace clang; 25 using namespace ento; 26 27 // This class can be extended with other tables which will help to reason 28 // about ranges more precisely. 29 class OperatorRelationsTable { 30 static_assert(BO_LT < BO_GT && BO_GT < BO_LE && BO_LE < BO_GE && 31 BO_GE < BO_EQ && BO_EQ < BO_NE, 32 "This class relies on operators order. Rework it otherwise."); 33 34 public: 35 enum TriStateKind { 36 False = 0, 37 True, 38 Unknown, 39 }; 40 41 private: 42 // CmpOpTable holds states which represent the corresponding range for 43 // branching an exploded graph. We can reason about the branch if there is 44 // a previously known fact of the existence of a comparison expression with 45 // operands used in the current expression. 46 // E.g. assuming (x < y) is true that means (x != y) is surely true. 47 // if (x previous_operation y) // < | != | > 48 // if (x operation y) // != | > | < 49 // tristate // True | Unknown | False 50 // 51 // CmpOpTable represents next: 52 // __|< |> |<=|>=|==|!=|UnknownX2| 53 // < |1 |0 |* |0 |0 |* |1 | 54 // > |0 |1 |0 |* |0 |* |1 | 55 // <=|1 |0 |1 |* |1 |* |0 | 56 // >=|0 |1 |* |1 |1 |* |0 | 57 // ==|0 |0 |* |* |1 |0 |1 | 58 // !=|1 |1 |* |* |0 |1 |0 | 59 // 60 // Columns stands for a previous operator. 61 // Rows stands for a current operator. 62 // Each row has exactly two `Unknown` cases. 63 // UnknownX2 means that both `Unknown` previous operators are met in code, 64 // and there is a special column for that, for example: 65 // if (x >= y) 66 // if (x != y) 67 // if (x <= y) 68 // False only 69 static constexpr size_t CmpOpCount = BO_NE - BO_LT + 1; 70 const TriStateKind CmpOpTable[CmpOpCount][CmpOpCount + 1] = { 71 // < > <= >= == != UnknownX2 72 {True, False, Unknown, False, False, Unknown, True}, // < 73 {False, True, False, Unknown, False, Unknown, True}, // > 74 {True, False, True, Unknown, True, Unknown, False}, // <= 75 {False, True, Unknown, True, True, Unknown, False}, // >= 76 {False, False, Unknown, Unknown, True, False, True}, // == 77 {True, True, Unknown, Unknown, False, True, False}, // != 78 }; 79 80 static size_t getIndexFromOp(BinaryOperatorKind OP) { 81 return static_cast<size_t>(OP - BO_LT); 82 } 83 84 public: 85 constexpr size_t getCmpOpCount() const { return CmpOpCount; } 86 87 static BinaryOperatorKind getOpFromIndex(size_t Index) { 88 return static_cast<BinaryOperatorKind>(Index + BO_LT); 89 } 90 91 TriStateKind getCmpOpState(BinaryOperatorKind CurrentOP, 92 BinaryOperatorKind QueriedOP) const { 93 return CmpOpTable[getIndexFromOp(CurrentOP)][getIndexFromOp(QueriedOP)]; 94 } 95 96 TriStateKind getCmpOpStateForUnknownX2(BinaryOperatorKind CurrentOP) const { 97 return CmpOpTable[getIndexFromOp(CurrentOP)][CmpOpCount]; 98 } 99 }; 100 //===----------------------------------------------------------------------===// 101 // RangeSet implementation 102 //===----------------------------------------------------------------------===// 103 104 void RangeSet::IntersectInRange(BasicValueFactory &BV, Factory &F, 105 const llvm::APSInt &Lower, 106 const llvm::APSInt &Upper, 107 PrimRangeSet &newRanges, 108 PrimRangeSet::iterator &i, 109 PrimRangeSet::iterator &e) const { 110 // There are six cases for each range R in the set: 111 // 1. R is entirely before the intersection range. 112 // 2. R is entirely after the intersection range. 113 // 3. R contains the entire intersection range. 114 // 4. R starts before the intersection range and ends in the middle. 115 // 5. R starts in the middle of the intersection range and ends after it. 116 // 6. R is entirely contained in the intersection range. 117 // These correspond to each of the conditions below. 118 for (/* i = begin(), e = end() */; i != e; ++i) { 119 if (i->To() < Lower) { 120 continue; 121 } 122 if (i->From() > Upper) { 123 break; 124 } 125 126 if (i->Includes(Lower)) { 127 if (i->Includes(Upper)) { 128 newRanges = 129 F.add(newRanges, Range(BV.getValue(Lower), BV.getValue(Upper))); 130 break; 131 } else 132 newRanges = F.add(newRanges, Range(BV.getValue(Lower), i->To())); 133 } else { 134 if (i->Includes(Upper)) { 135 newRanges = F.add(newRanges, Range(i->From(), BV.getValue(Upper))); 136 break; 137 } else 138 newRanges = F.add(newRanges, *i); 139 } 140 } 141 } 142 143 const llvm::APSInt &RangeSet::getMinValue() const { 144 assert(!isEmpty()); 145 return begin()->From(); 146 } 147 148 const llvm::APSInt &RangeSet::getMaxValue() const { 149 assert(!isEmpty()); 150 // NOTE: It's a shame that we can't implement 'getMaxValue' without scanning 151 // the whole tree to get to the last element. 152 // llvm::ImmutableSet should support decrement for 'end' iterators 153 // or reverse order iteration. 154 auto It = begin(); 155 for (auto End = end(); std::next(It) != End; ++It) { 156 } 157 return It->To(); 158 } 159 160 bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const { 161 if (isEmpty()) { 162 // This range is already infeasible. 163 return false; 164 } 165 166 // This function has nine cases, the cartesian product of range-testing 167 // both the upper and lower bounds against the symbol's type. 168 // Each case requires a different pinning operation. 169 // The function returns false if the described range is entirely outside 170 // the range of values for the associated symbol. 171 APSIntType Type(getMinValue()); 172 APSIntType::RangeTestResultKind LowerTest = Type.testInRange(Lower, true); 173 APSIntType::RangeTestResultKind UpperTest = Type.testInRange(Upper, true); 174 175 switch (LowerTest) { 176 case APSIntType::RTR_Below: 177 switch (UpperTest) { 178 case APSIntType::RTR_Below: 179 // The entire range is outside the symbol's set of possible values. 180 // If this is a conventionally-ordered range, the state is infeasible. 181 if (Lower <= Upper) 182 return false; 183 184 // However, if the range wraps around, it spans all possible values. 185 Lower = Type.getMinValue(); 186 Upper = Type.getMaxValue(); 187 break; 188 case APSIntType::RTR_Within: 189 // The range starts below what's possible but ends within it. Pin. 190 Lower = Type.getMinValue(); 191 Type.apply(Upper); 192 break; 193 case APSIntType::RTR_Above: 194 // The range spans all possible values for the symbol. Pin. 195 Lower = Type.getMinValue(); 196 Upper = Type.getMaxValue(); 197 break; 198 } 199 break; 200 case APSIntType::RTR_Within: 201 switch (UpperTest) { 202 case APSIntType::RTR_Below: 203 // The range wraps around, but all lower values are not possible. 204 Type.apply(Lower); 205 Upper = Type.getMaxValue(); 206 break; 207 case APSIntType::RTR_Within: 208 // The range may or may not wrap around, but both limits are valid. 209 Type.apply(Lower); 210 Type.apply(Upper); 211 break; 212 case APSIntType::RTR_Above: 213 // The range starts within what's possible but ends above it. Pin. 214 Type.apply(Lower); 215 Upper = Type.getMaxValue(); 216 break; 217 } 218 break; 219 case APSIntType::RTR_Above: 220 switch (UpperTest) { 221 case APSIntType::RTR_Below: 222 // The range wraps but is outside the symbol's set of possible values. 223 return false; 224 case APSIntType::RTR_Within: 225 // The range starts above what's possible but ends within it (wrap). 226 Lower = Type.getMinValue(); 227 Type.apply(Upper); 228 break; 229 case APSIntType::RTR_Above: 230 // The entire range is outside the symbol's set of possible values. 231 // If this is a conventionally-ordered range, the state is infeasible. 232 if (Lower <= Upper) 233 return false; 234 235 // However, if the range wraps around, it spans all possible values. 236 Lower = Type.getMinValue(); 237 Upper = Type.getMaxValue(); 238 break; 239 } 240 break; 241 } 242 243 return true; 244 } 245 246 // Returns a set containing the values in the receiving set, intersected with 247 // the closed range [Lower, Upper]. Unlike the Range type, this range uses 248 // modular arithmetic, corresponding to the common treatment of C integer 249 // overflow. Thus, if the Lower bound is greater than the Upper bound, the 250 // range is taken to wrap around. This is equivalent to taking the 251 // intersection with the two ranges [Min, Upper] and [Lower, Max], 252 // or, alternatively, /removing/ all integers between Upper and Lower. 253 RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F, 254 llvm::APSInt Lower, llvm::APSInt Upper) const { 255 PrimRangeSet newRanges = F.getEmptySet(); 256 257 if (isEmpty() || !pin(Lower, Upper)) 258 return newRanges; 259 260 PrimRangeSet::iterator i = begin(), e = end(); 261 if (Lower <= Upper) 262 IntersectInRange(BV, F, Lower, Upper, newRanges, i, e); 263 else { 264 // The order of the next two statements is important! 265 // IntersectInRange() does not reset the iteration state for i and e. 266 // Therefore, the lower range most be handled first. 267 IntersectInRange(BV, F, BV.getMinValue(Upper), Upper, newRanges, i, e); 268 IntersectInRange(BV, F, Lower, BV.getMaxValue(Lower), newRanges, i, e); 269 } 270 271 return newRanges; 272 } 273 274 // Returns a set containing the values in the receiving set, intersected with 275 // the range set passed as parameter. 276 RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F, 277 const RangeSet &Other) const { 278 PrimRangeSet newRanges = F.getEmptySet(); 279 280 for (iterator i = Other.begin(), e = Other.end(); i != e; ++i) { 281 RangeSet newPiece = Intersect(BV, F, i->From(), i->To()); 282 for (iterator j = newPiece.begin(), ee = newPiece.end(); j != ee; ++j) { 283 newRanges = F.add(newRanges, *j); 284 } 285 } 286 287 return newRanges; 288 } 289 290 // Turn all [A, B] ranges to [-B, -A], when "-" is a C-like unary minus 291 // operation under the values of the type. 292 // 293 // We also handle MIN because applying unary minus to MIN does not change it. 294 // Example 1: 295 // char x = -128; // -128 is a MIN value in a range of 'char' 296 // char y = -x; // y: -128 297 // Example 2: 298 // unsigned char x = 0; // 0 is a MIN value in a range of 'unsigned char' 299 // unsigned char y = -x; // y: 0 300 // 301 // And it makes us to separate the range 302 // like [MIN, N] to [MIN, MIN] U [-N,MAX]. 303 // For instance, whole range is {-128..127} and subrange is [-128,-126], 304 // thus [-128,-127,-126,.....] negates to [-128,.....,126,127]. 305 // 306 // Negate restores disrupted ranges on bounds, 307 // e.g. [MIN, B] => [MIN, MIN] U [-B, MAX] => [MIN, B]. 308 RangeSet RangeSet::Negate(BasicValueFactory &BV, Factory &F) const { 309 PrimRangeSet newRanges = F.getEmptySet(); 310 311 if (isEmpty()) 312 return newRanges; 313 314 const llvm::APSInt sampleValue = getMinValue(); 315 const llvm::APSInt &MIN = BV.getMinValue(sampleValue); 316 const llvm::APSInt &MAX = BV.getMaxValue(sampleValue); 317 318 // Handle a special case for MIN value. 319 iterator i = begin(); 320 const llvm::APSInt &from = i->From(); 321 const llvm::APSInt &to = i->To(); 322 if (from == MIN) { 323 // If [from, to] are [MIN, MAX], then just return the same [MIN, MAX]. 324 if (to == MAX) { 325 newRanges = ranges; 326 } else { 327 // Add separate range for the lowest value. 328 newRanges = F.add(newRanges, Range(MIN, MIN)); 329 // Skip adding the second range in case when [from, to] are [MIN, MIN]. 330 if (to != MIN) { 331 newRanges = F.add(newRanges, Range(BV.getValue(-to), MAX)); 332 } 333 } 334 // Skip the first range in the loop. 335 ++i; 336 } 337 338 // Negate all other ranges. 339 for (iterator e = end(); i != e; ++i) { 340 // Negate int values. 341 const llvm::APSInt &newFrom = BV.getValue(-i->To()); 342 const llvm::APSInt &newTo = BV.getValue(-i->From()); 343 // Add a negated range. 344 newRanges = F.add(newRanges, Range(newFrom, newTo)); 345 } 346 347 if (newRanges.isSingleton()) 348 return newRanges; 349 350 // Try to find and unite next ranges: 351 // [MIN, MIN] & [MIN + 1, N] => [MIN, N]. 352 iterator iter1 = newRanges.begin(); 353 iterator iter2 = std::next(iter1); 354 355 if (iter1->To() == MIN && (iter2->From() - 1) == MIN) { 356 const llvm::APSInt &to = iter2->To(); 357 // remove adjacent ranges 358 newRanges = F.remove(newRanges, *iter1); 359 newRanges = F.remove(newRanges, *newRanges.begin()); 360 // add united range 361 newRanges = F.add(newRanges, Range(MIN, to)); 362 } 363 364 return newRanges; 365 } 366 367 void RangeSet::print(raw_ostream &os) const { 368 bool isFirst = true; 369 os << "{ "; 370 for (iterator i = begin(), e = end(); i != e; ++i) { 371 if (isFirst) 372 isFirst = false; 373 else 374 os << ", "; 375 376 os << '[' << i->From().toString(10) << ", " << i->To().toString(10) 377 << ']'; 378 } 379 os << " }"; 380 } 381 382 namespace { 383 384 /// A little component aggregating all of the reasoning we have about 385 /// the ranges of symbolic expressions. 386 /// 387 /// Even when we don't know the exact values of the operands, we still 388 /// can get a pretty good estimate of the result's range. 389 class SymbolicRangeInferrer 390 : public SymExprVisitor<SymbolicRangeInferrer, RangeSet> { 391 public: 392 static RangeSet inferRange(BasicValueFactory &BV, RangeSet::Factory &F, 393 ProgramStateRef State, SymbolRef Sym) { 394 SymbolicRangeInferrer Inferrer(BV, F, State); 395 return Inferrer.infer(Sym); 396 } 397 398 RangeSet VisitSymExpr(SymbolRef Sym) { 399 // If we got to this function, the actual type of the symbolic 400 // expression is not supported for advanced inference. 401 // In this case, we simply backoff to the default "let's simply 402 // infer the range from the expression's type". 403 return infer(Sym->getType()); 404 } 405 406 RangeSet VisitSymIntExpr(const SymIntExpr *Sym) { 407 return VisitBinaryOperator(Sym); 408 } 409 410 RangeSet VisitIntSymExpr(const IntSymExpr *Sym) { 411 return VisitBinaryOperator(Sym); 412 } 413 414 RangeSet VisitSymSymExpr(const SymSymExpr *Sym) { 415 return VisitBinaryOperator(Sym); 416 } 417 418 private: 419 SymbolicRangeInferrer(BasicValueFactory &BV, RangeSet::Factory &F, 420 ProgramStateRef S) 421 : ValueFactory(BV), RangeFactory(F), State(S) {} 422 423 /// Infer range information from the given integer constant. 424 /// 425 /// It's not a real "inference", but is here for operating with 426 /// sub-expressions in a more polymorphic manner. 427 RangeSet inferAs(const llvm::APSInt &Val, QualType) { 428 return {RangeFactory, Val}; 429 } 430 431 /// Infer range information from symbol in the context of the given type. 432 RangeSet inferAs(SymbolRef Sym, QualType DestType) { 433 QualType ActualType = Sym->getType(); 434 // Check that we can reason about the symbol at all. 435 if (ActualType->isIntegralOrEnumerationType() || 436 Loc::isLocType(ActualType)) { 437 return infer(Sym); 438 } 439 // Otherwise, let's simply infer from the destination type. 440 // We couldn't figure out nothing else about that expression. 441 return infer(DestType); 442 } 443 444 RangeSet infer(SymbolRef Sym) { 445 const RangeSet *AssociatedRange = State->get<ConstraintRange>(Sym); 446 447 // If Sym is a difference of symbols A - B, then maybe we have range set 448 // stored for B - A. 449 const RangeSet *RangeAssociatedWithNegatedSym = 450 getRangeForMinusSymbol(State, Sym); 451 452 // If we have range set stored for both A - B and B - A then calculate the 453 // effective range set by intersecting the range set for A - B and the 454 // negated range set of B - A. 455 if (AssociatedRange && RangeAssociatedWithNegatedSym) 456 return AssociatedRange->Intersect( 457 ValueFactory, RangeFactory, 458 RangeAssociatedWithNegatedSym->Negate(ValueFactory, RangeFactory)); 459 460 if (AssociatedRange) 461 return *AssociatedRange; 462 463 if (RangeAssociatedWithNegatedSym) 464 return RangeAssociatedWithNegatedSym->Negate(ValueFactory, RangeFactory); 465 466 // If Sym is a comparison expression (except <=>), 467 // find any other comparisons with the same operands. 468 // See function description. 469 const RangeSet CmpRangeSet = getRangeForComparisonSymbol(State, Sym); 470 if (!CmpRangeSet.isEmpty()) 471 return CmpRangeSet; 472 473 return Visit(Sym); 474 } 475 476 /// Infer range information solely from the type. 477 RangeSet infer(QualType T) { 478 // Lazily generate a new RangeSet representing all possible values for the 479 // given symbol type. 480 RangeSet Result(RangeFactory, ValueFactory.getMinValue(T), 481 ValueFactory.getMaxValue(T)); 482 483 // References are known to be non-zero. 484 if (T->isReferenceType()) 485 return assumeNonZero(Result, T); 486 487 return Result; 488 } 489 490 template <class BinarySymExprTy> 491 RangeSet VisitBinaryOperator(const BinarySymExprTy *Sym) { 492 // TODO #1: VisitBinaryOperator implementation might not make a good 493 // use of the inferred ranges. In this case, we might be calculating 494 // everything for nothing. This being said, we should introduce some 495 // sort of laziness mechanism here. 496 // 497 // TODO #2: We didn't go into the nested expressions before, so it 498 // might cause us spending much more time doing the inference. 499 // This can be a problem for deeply nested expressions that are 500 // involved in conditions and get tested continuously. We definitely 501 // need to address this issue and introduce some sort of caching 502 // in here. 503 QualType ResultType = Sym->getType(); 504 return VisitBinaryOperator(inferAs(Sym->getLHS(), ResultType), 505 Sym->getOpcode(), 506 inferAs(Sym->getRHS(), ResultType), ResultType); 507 } 508 509 RangeSet VisitBinaryOperator(RangeSet LHS, BinaryOperator::Opcode Op, 510 RangeSet RHS, QualType T) { 511 switch (Op) { 512 case BO_Or: 513 return VisitBinaryOperator<BO_Or>(LHS, RHS, T); 514 case BO_And: 515 return VisitBinaryOperator<BO_And>(LHS, RHS, T); 516 case BO_Rem: 517 return VisitBinaryOperator<BO_Rem>(LHS, RHS, T); 518 default: 519 return infer(T); 520 } 521 } 522 523 //===----------------------------------------------------------------------===// 524 // Ranges and operators 525 //===----------------------------------------------------------------------===// 526 527 /// Return a rough approximation of the given range set. 528 /// 529 /// For the range set: 530 /// { [x_0, y_0], [x_1, y_1], ... , [x_N, y_N] } 531 /// it will return the range [x_0, y_N]. 532 static Range fillGaps(RangeSet Origin) { 533 assert(!Origin.isEmpty()); 534 return {Origin.getMinValue(), Origin.getMaxValue()}; 535 } 536 537 /// Try to convert given range into the given type. 538 /// 539 /// It will return llvm::None only when the trivial conversion is possible. 540 llvm::Optional<Range> convert(const Range &Origin, APSIntType To) { 541 if (To.testInRange(Origin.From(), false) != APSIntType::RTR_Within || 542 To.testInRange(Origin.To(), false) != APSIntType::RTR_Within) { 543 return llvm::None; 544 } 545 return Range(ValueFactory.Convert(To, Origin.From()), 546 ValueFactory.Convert(To, Origin.To())); 547 } 548 549 template <BinaryOperator::Opcode Op> 550 RangeSet VisitBinaryOperator(RangeSet LHS, RangeSet RHS, QualType T) { 551 // We should propagate information about unfeasbility of one of the 552 // operands to the resulting range. 553 if (LHS.isEmpty() || RHS.isEmpty()) { 554 return RangeFactory.getEmptySet(); 555 } 556 557 Range CoarseLHS = fillGaps(LHS); 558 Range CoarseRHS = fillGaps(RHS); 559 560 APSIntType ResultType = ValueFactory.getAPSIntType(T); 561 562 // We need to convert ranges to the resulting type, so we can compare values 563 // and combine them in a meaningful (in terms of the given operation) way. 564 auto ConvertedCoarseLHS = convert(CoarseLHS, ResultType); 565 auto ConvertedCoarseRHS = convert(CoarseRHS, ResultType); 566 567 // It is hard to reason about ranges when conversion changes 568 // borders of the ranges. 569 if (!ConvertedCoarseLHS || !ConvertedCoarseRHS) { 570 return infer(T); 571 } 572 573 return VisitBinaryOperator<Op>(*ConvertedCoarseLHS, *ConvertedCoarseRHS, T); 574 } 575 576 template <BinaryOperator::Opcode Op> 577 RangeSet VisitBinaryOperator(Range LHS, Range RHS, QualType T) { 578 return infer(T); 579 } 580 581 /// Return a symmetrical range for the given range and type. 582 /// 583 /// If T is signed, return the smallest range [-x..x] that covers the original 584 /// range, or [-min(T), max(T)] if the aforementioned symmetric range doesn't 585 /// exist due to original range covering min(T)). 586 /// 587 /// If T is unsigned, return the smallest range [0..x] that covers the 588 /// original range. 589 Range getSymmetricalRange(Range Origin, QualType T) { 590 APSIntType RangeType = ValueFactory.getAPSIntType(T); 591 592 if (RangeType.isUnsigned()) { 593 return Range(ValueFactory.getMinValue(RangeType), Origin.To()); 594 } 595 596 if (Origin.From().isMinSignedValue()) { 597 // If mini is a minimal signed value, absolute value of it is greater 598 // than the maximal signed value. In order to avoid these 599 // complications, we simply return the whole range. 600 return {ValueFactory.getMinValue(RangeType), 601 ValueFactory.getMaxValue(RangeType)}; 602 } 603 604 // At this point, we are sure that the type is signed and we can safely 605 // use unary - operator. 606 // 607 // While calculating absolute maximum, we can use the following formula 608 // because of these reasons: 609 // * If From >= 0 then To >= From and To >= -From. 610 // AbsMax == To == max(To, -From) 611 // * If To <= 0 then -From >= -To and -From >= From. 612 // AbsMax == -From == max(-From, To) 613 // * Otherwise, From <= 0, To >= 0, and 614 // AbsMax == max(abs(From), abs(To)) 615 llvm::APSInt AbsMax = std::max(-Origin.From(), Origin.To()); 616 617 // Intersection is guaranteed to be non-empty. 618 return {ValueFactory.getValue(-AbsMax), ValueFactory.getValue(AbsMax)}; 619 } 620 621 /// Return a range set subtracting zero from \p Domain. 622 RangeSet assumeNonZero(RangeSet Domain, QualType T) { 623 APSIntType IntType = ValueFactory.getAPSIntType(T); 624 return Domain.Intersect(ValueFactory, RangeFactory, 625 ++IntType.getZeroValue(), --IntType.getZeroValue()); 626 } 627 628 // FIXME: Once SValBuilder supports unary minus, we should use SValBuilder to 629 // obtain the negated symbolic expression instead of constructing the 630 // symbol manually. This will allow us to support finding ranges of not 631 // only negated SymSymExpr-type expressions, but also of other, simpler 632 // expressions which we currently do not know how to negate. 633 const RangeSet *getRangeForMinusSymbol(ProgramStateRef State, SymbolRef Sym) { 634 if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) { 635 if (SSE->getOpcode() == BO_Sub) { 636 QualType T = Sym->getType(); 637 SymbolManager &SymMgr = State->getSymbolManager(); 638 SymbolRef negSym = 639 SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, SSE->getLHS(), T); 640 641 if (const RangeSet *negV = State->get<ConstraintRange>(negSym)) { 642 // Unsigned range set cannot be negated, unless it is [0, 0]. 643 if (T->isUnsignedIntegerOrEnumerationType() || 644 T->isSignedIntegerOrEnumerationType()) 645 return negV; 646 } 647 } 648 } 649 return nullptr; 650 } 651 652 // Returns ranges only for binary comparison operators (except <=>) 653 // when left and right operands are symbolic values. 654 // Finds any other comparisons with the same operands. 655 // Then do logical calculations and refuse impossible branches. 656 // E.g. (x < y) and (x > y) at the same time are impossible. 657 // E.g. (x >= y) and (x != y) at the same time makes (x > y) true only. 658 // E.g. (x == y) and (y == x) are just reversed but the same. 659 // It covers all possible combinations (see CmpOpTable description). 660 // Note that `x` and `y` can also stand for subexpressions, 661 // not only for actual symbols. 662 RangeSet getRangeForComparisonSymbol(ProgramStateRef State, SymbolRef Sym) { 663 const RangeSet EmptyRangeSet = RangeFactory.getEmptySet(); 664 665 auto SSE = dyn_cast<SymSymExpr>(Sym); 666 if (!SSE) 667 return EmptyRangeSet; 668 669 BinaryOperatorKind CurrentOP = SSE->getOpcode(); 670 671 // We currently do not support <=> (C++20). 672 if (!BinaryOperator::isComparisonOp(CurrentOP) || (CurrentOP == BO_Cmp)) 673 return EmptyRangeSet; 674 675 static const OperatorRelationsTable CmpOpTable{}; 676 677 const SymExpr *LHS = SSE->getLHS(); 678 const SymExpr *RHS = SSE->getRHS(); 679 QualType T = SSE->getType(); 680 681 SymbolManager &SymMgr = State->getSymbolManager(); 682 const llvm::APSInt &Zero = ValueFactory.getValue(0, T); 683 const llvm::APSInt &One = ValueFactory.getValue(1, T); 684 const RangeSet TrueRangeSet(RangeFactory, One, One); 685 const RangeSet FalseRangeSet(RangeFactory, Zero, Zero); 686 687 int UnknownStates = 0; 688 689 // Loop goes through all of the columns exept the last one ('UnknownX2'). 690 // We treat `UnknownX2` column separately at the end of the loop body. 691 for (size_t i = 0; i < CmpOpTable.getCmpOpCount(); ++i) { 692 693 // Let's find an expression e.g. (x < y). 694 BinaryOperatorKind QueriedOP = OperatorRelationsTable::getOpFromIndex(i); 695 const SymSymExpr *SymSym = SymMgr.getSymSymExpr(LHS, QueriedOP, RHS, T); 696 const RangeSet *QueriedRangeSet = State->get<ConstraintRange>(SymSym); 697 698 // If ranges were not previously found, 699 // try to find a reversed expression (y > x). 700 if (!QueriedRangeSet) { 701 const BinaryOperatorKind ROP = 702 BinaryOperator::reverseComparisonOp(QueriedOP); 703 SymSym = SymMgr.getSymSymExpr(RHS, ROP, LHS, T); 704 QueriedRangeSet = State->get<ConstraintRange>(SymSym); 705 } 706 707 if (!QueriedRangeSet || QueriedRangeSet->isEmpty()) 708 continue; 709 710 const llvm::APSInt *ConcreteValue = QueriedRangeSet->getConcreteValue(); 711 const bool isInFalseBranch = 712 ConcreteValue ? (*ConcreteValue == 0) : false; 713 714 // If it is a false branch, we shall be guided by opposite operator, 715 // because the table is made assuming we are in the true branch. 716 // E.g. when (x <= y) is false, then (x > y) is true. 717 if (isInFalseBranch) 718 QueriedOP = BinaryOperator::negateComparisonOp(QueriedOP); 719 720 OperatorRelationsTable::TriStateKind BranchState = 721 CmpOpTable.getCmpOpState(CurrentOP, QueriedOP); 722 723 if (BranchState == OperatorRelationsTable::Unknown) { 724 if (++UnknownStates == 2) 725 // If we met both Unknown states. 726 // if (x <= y) // assume true 727 // if (x != y) // assume true 728 // if (x < y) // would be also true 729 // Get a state from `UnknownX2` column. 730 BranchState = CmpOpTable.getCmpOpStateForUnknownX2(CurrentOP); 731 else 732 continue; 733 } 734 735 return (BranchState == OperatorRelationsTable::True) ? TrueRangeSet 736 : FalseRangeSet; 737 } 738 739 return EmptyRangeSet; 740 } 741 742 BasicValueFactory &ValueFactory; 743 RangeSet::Factory &RangeFactory; 744 ProgramStateRef State; 745 }; 746 747 template <> 748 RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Or>(Range LHS, Range RHS, 749 QualType T) { 750 APSIntType ResultType = ValueFactory.getAPSIntType(T); 751 llvm::APSInt Zero = ResultType.getZeroValue(); 752 753 bool IsLHSPositiveOrZero = LHS.From() >= Zero; 754 bool IsRHSPositiveOrZero = RHS.From() >= Zero; 755 756 bool IsLHSNegative = LHS.To() < Zero; 757 bool IsRHSNegative = RHS.To() < Zero; 758 759 // Check if both ranges have the same sign. 760 if ((IsLHSPositiveOrZero && IsRHSPositiveOrZero) || 761 (IsLHSNegative && IsRHSNegative)) { 762 // The result is definitely greater or equal than any of the operands. 763 const llvm::APSInt &Min = std::max(LHS.From(), RHS.From()); 764 765 // We estimate maximal value for positives as the maximal value for the 766 // given type. For negatives, we estimate it with -1 (e.g. 0x11111111). 767 // 768 // TODO: We basically, limit the resulting range from below, but don't do 769 // anything with the upper bound. 770 // 771 // For positive operands, it can be done as follows: for the upper 772 // bound of LHS and RHS we calculate the most significant bit set. 773 // Let's call it the N-th bit. Then we can estimate the maximal 774 // number to be 2^(N+1)-1, i.e. the number with all the bits up to 775 // the N-th bit set. 776 const llvm::APSInt &Max = IsLHSNegative 777 ? ValueFactory.getValue(--Zero) 778 : ValueFactory.getMaxValue(ResultType); 779 780 return {RangeFactory, ValueFactory.getValue(Min), Max}; 781 } 782 783 // Otherwise, let's check if at least one of the operands is negative. 784 if (IsLHSNegative || IsRHSNegative) { 785 // This means that the result is definitely negative as well. 786 return {RangeFactory, ValueFactory.getMinValue(ResultType), 787 ValueFactory.getValue(--Zero)}; 788 } 789 790 RangeSet DefaultRange = infer(T); 791 792 // It is pretty hard to reason about operands with different signs 793 // (and especially with possibly different signs). We simply check if it 794 // can be zero. In order to conclude that the result could not be zero, 795 // at least one of the operands should be definitely not zero itself. 796 if (!LHS.Includes(Zero) || !RHS.Includes(Zero)) { 797 return assumeNonZero(DefaultRange, T); 798 } 799 800 // Nothing much else to do here. 801 return DefaultRange; 802 } 803 804 template <> 805 RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_And>(Range LHS, 806 Range RHS, 807 QualType T) { 808 APSIntType ResultType = ValueFactory.getAPSIntType(T); 809 llvm::APSInt Zero = ResultType.getZeroValue(); 810 811 bool IsLHSPositiveOrZero = LHS.From() >= Zero; 812 bool IsRHSPositiveOrZero = RHS.From() >= Zero; 813 814 bool IsLHSNegative = LHS.To() < Zero; 815 bool IsRHSNegative = RHS.To() < Zero; 816 817 // Check if both ranges have the same sign. 818 if ((IsLHSPositiveOrZero && IsRHSPositiveOrZero) || 819 (IsLHSNegative && IsRHSNegative)) { 820 // The result is definitely less or equal than any of the operands. 821 const llvm::APSInt &Max = std::min(LHS.To(), RHS.To()); 822 823 // We conservatively estimate lower bound to be the smallest positive 824 // or negative value corresponding to the sign of the operands. 825 const llvm::APSInt &Min = IsLHSNegative 826 ? ValueFactory.getMinValue(ResultType) 827 : ValueFactory.getValue(Zero); 828 829 return {RangeFactory, Min, Max}; 830 } 831 832 // Otherwise, let's check if at least one of the operands is positive. 833 if (IsLHSPositiveOrZero || IsRHSPositiveOrZero) { 834 // This makes result definitely positive. 835 // 836 // We can also reason about a maximal value by finding the maximal 837 // value of the positive operand. 838 const llvm::APSInt &Max = IsLHSPositiveOrZero ? LHS.To() : RHS.To(); 839 840 // The minimal value on the other hand is much harder to reason about. 841 // The only thing we know for sure is that the result is positive. 842 return {RangeFactory, ValueFactory.getValue(Zero), 843 ValueFactory.getValue(Max)}; 844 } 845 846 // Nothing much else to do here. 847 return infer(T); 848 } 849 850 template <> 851 RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Rem>(Range LHS, 852 Range RHS, 853 QualType T) { 854 llvm::APSInt Zero = ValueFactory.getAPSIntType(T).getZeroValue(); 855 856 Range ConservativeRange = getSymmetricalRange(RHS, T); 857 858 llvm::APSInt Max = ConservativeRange.To(); 859 llvm::APSInt Min = ConservativeRange.From(); 860 861 if (Max == Zero) { 862 // It's an undefined behaviour to divide by 0 and it seems like we know 863 // for sure that RHS is 0. Let's say that the resulting range is 864 // simply infeasible for that matter. 865 return RangeFactory.getEmptySet(); 866 } 867 868 // At this point, our conservative range is closed. The result, however, 869 // couldn't be greater than the RHS' maximal absolute value. Because of 870 // this reason, we turn the range into open (or half-open in case of 871 // unsigned integers). 872 // 873 // While we operate on integer values, an open interval (a, b) can be easily 874 // represented by the closed interval [a + 1, b - 1]. And this is exactly 875 // what we do next. 876 // 877 // If we are dealing with unsigned case, we shouldn't move the lower bound. 878 if (Min.isSigned()) { 879 ++Min; 880 } 881 --Max; 882 883 bool IsLHSPositiveOrZero = LHS.From() >= Zero; 884 bool IsRHSPositiveOrZero = RHS.From() >= Zero; 885 886 // Remainder operator results with negative operands is implementation 887 // defined. Positive cases are much easier to reason about though. 888 if (IsLHSPositiveOrZero && IsRHSPositiveOrZero) { 889 // If maximal value of LHS is less than maximal value of RHS, 890 // the result won't get greater than LHS.To(). 891 Max = std::min(LHS.To(), Max); 892 // We want to check if it is a situation similar to the following: 893 // 894 // <------------|---[ LHS ]--------[ RHS ]-----> 895 // -INF 0 +INF 896 // 897 // In this situation, we can conclude that (LHS / RHS) == 0 and 898 // (LHS % RHS) == LHS. 899 Min = LHS.To() < RHS.From() ? LHS.From() : Zero; 900 } 901 902 // Nevertheless, the symmetrical range for RHS is a conservative estimate 903 // for any sign of either LHS, or RHS. 904 return {RangeFactory, ValueFactory.getValue(Min), ValueFactory.getValue(Max)}; 905 } 906 907 class RangeConstraintManager : public RangedConstraintManager { 908 public: 909 RangeConstraintManager(ExprEngine *EE, SValBuilder &SVB) 910 : RangedConstraintManager(EE, SVB) {} 911 912 //===------------------------------------------------------------------===// 913 // Implementation for interface from ConstraintManager. 914 //===------------------------------------------------------------------===// 915 916 bool haveEqualConstraints(ProgramStateRef S1, 917 ProgramStateRef S2) const override { 918 return S1->get<ConstraintRange>() == S2->get<ConstraintRange>(); 919 } 920 921 bool canReasonAbout(SVal X) const override; 922 923 ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override; 924 925 const llvm::APSInt *getSymVal(ProgramStateRef State, 926 SymbolRef Sym) const override; 927 928 ProgramStateRef removeDeadBindings(ProgramStateRef State, 929 SymbolReaper &SymReaper) override; 930 931 void printJson(raw_ostream &Out, ProgramStateRef State, const char *NL = "\n", 932 unsigned int Space = 0, bool IsDot = false) const override; 933 934 //===------------------------------------------------------------------===// 935 // Implementation for interface from RangedConstraintManager. 936 //===------------------------------------------------------------------===// 937 938 ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym, 939 const llvm::APSInt &V, 940 const llvm::APSInt &Adjustment) override; 941 942 ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym, 943 const llvm::APSInt &V, 944 const llvm::APSInt &Adjustment) override; 945 946 ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym, 947 const llvm::APSInt &V, 948 const llvm::APSInt &Adjustment) override; 949 950 ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym, 951 const llvm::APSInt &V, 952 const llvm::APSInt &Adjustment) override; 953 954 ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym, 955 const llvm::APSInt &V, 956 const llvm::APSInt &Adjustment) override; 957 958 ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym, 959 const llvm::APSInt &V, 960 const llvm::APSInt &Adjustment) override; 961 962 ProgramStateRef assumeSymWithinInclusiveRange( 963 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 964 const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; 965 966 ProgramStateRef assumeSymOutsideInclusiveRange( 967 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 968 const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; 969 970 private: 971 RangeSet::Factory F; 972 973 RangeSet getRange(ProgramStateRef State, SymbolRef Sym); 974 975 RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym, 976 const llvm::APSInt &Int, 977 const llvm::APSInt &Adjustment); 978 RangeSet getSymGTRange(ProgramStateRef St, SymbolRef Sym, 979 const llvm::APSInt &Int, 980 const llvm::APSInt &Adjustment); 981 RangeSet getSymLERange(ProgramStateRef St, SymbolRef Sym, 982 const llvm::APSInt &Int, 983 const llvm::APSInt &Adjustment); 984 RangeSet getSymLERange(llvm::function_ref<RangeSet()> RS, 985 const llvm::APSInt &Int, 986 const llvm::APSInt &Adjustment); 987 RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym, 988 const llvm::APSInt &Int, 989 const llvm::APSInt &Adjustment); 990 }; 991 992 } // end anonymous namespace 993 994 std::unique_ptr<ConstraintManager> 995 ento::CreateRangeConstraintManager(ProgramStateManager &StMgr, 996 ExprEngine *Eng) { 997 return std::make_unique<RangeConstraintManager>(Eng, StMgr.getSValBuilder()); 998 } 999 1000 bool RangeConstraintManager::canReasonAbout(SVal X) const { 1001 Optional<nonloc::SymbolVal> SymVal = X.getAs<nonloc::SymbolVal>(); 1002 if (SymVal && SymVal->isExpression()) { 1003 const SymExpr *SE = SymVal->getSymbol(); 1004 1005 if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) { 1006 switch (SIE->getOpcode()) { 1007 // We don't reason yet about bitwise-constraints on symbolic values. 1008 case BO_And: 1009 case BO_Or: 1010 case BO_Xor: 1011 return false; 1012 // We don't reason yet about these arithmetic constraints on 1013 // symbolic values. 1014 case BO_Mul: 1015 case BO_Div: 1016 case BO_Rem: 1017 case BO_Shl: 1018 case BO_Shr: 1019 return false; 1020 // All other cases. 1021 default: 1022 return true; 1023 } 1024 } 1025 1026 if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) { 1027 // FIXME: Handle <=> here. 1028 if (BinaryOperator::isEqualityOp(SSE->getOpcode()) || 1029 BinaryOperator::isRelationalOp(SSE->getOpcode())) { 1030 // We handle Loc <> Loc comparisons, but not (yet) NonLoc <> NonLoc. 1031 // We've recently started producing Loc <> NonLoc comparisons (that 1032 // result from casts of one of the operands between eg. intptr_t and 1033 // void *), but we can't reason about them yet. 1034 if (Loc::isLocType(SSE->getLHS()->getType())) { 1035 return Loc::isLocType(SSE->getRHS()->getType()); 1036 } 1037 } 1038 } 1039 1040 return false; 1041 } 1042 1043 return true; 1044 } 1045 1046 ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State, 1047 SymbolRef Sym) { 1048 const RangeSet *Ranges = State->get<ConstraintRange>(Sym); 1049 1050 // If we don't have any information about this symbol, it's underconstrained. 1051 if (!Ranges) 1052 return ConditionTruthVal(); 1053 1054 // If we have a concrete value, see if it's zero. 1055 if (const llvm::APSInt *Value = Ranges->getConcreteValue()) 1056 return *Value == 0; 1057 1058 BasicValueFactory &BV = getBasicVals(); 1059 APSIntType IntType = BV.getAPSIntType(Sym->getType()); 1060 llvm::APSInt Zero = IntType.getZeroValue(); 1061 1062 // Check if zero is in the set of possible values. 1063 if (Ranges->Intersect(BV, F, Zero, Zero).isEmpty()) 1064 return false; 1065 1066 // Zero is a possible value, but it is not the /only/ possible value. 1067 return ConditionTruthVal(); 1068 } 1069 1070 const llvm::APSInt *RangeConstraintManager::getSymVal(ProgramStateRef St, 1071 SymbolRef Sym) const { 1072 const ConstraintRangeTy::data_type *T = St->get<ConstraintRange>(Sym); 1073 return T ? T->getConcreteValue() : nullptr; 1074 } 1075 1076 /// Scan all symbols referenced by the constraints. If the symbol is not alive 1077 /// as marked in LSymbols, mark it as dead in DSymbols. 1078 ProgramStateRef 1079 RangeConstraintManager::removeDeadBindings(ProgramStateRef State, 1080 SymbolReaper &SymReaper) { 1081 bool Changed = false; 1082 ConstraintRangeTy CR = State->get<ConstraintRange>(); 1083 ConstraintRangeTy::Factory &CRFactory = State->get_context<ConstraintRange>(); 1084 1085 for (ConstraintRangeTy::iterator I = CR.begin(), E = CR.end(); I != E; ++I) { 1086 SymbolRef Sym = I.getKey(); 1087 if (SymReaper.isDead(Sym)) { 1088 Changed = true; 1089 CR = CRFactory.remove(CR, Sym); 1090 } 1091 } 1092 1093 return Changed ? State->set<ConstraintRange>(CR) : State; 1094 } 1095 1096 RangeSet RangeConstraintManager::getRange(ProgramStateRef State, 1097 SymbolRef Sym) { 1098 return SymbolicRangeInferrer::inferRange(getBasicVals(), F, State, Sym); 1099 } 1100 1101 //===------------------------------------------------------------------------=== 1102 // assumeSymX methods: protected interface for RangeConstraintManager. 1103 //===------------------------------------------------------------------------===/ 1104 1105 // The syntax for ranges below is mathematical, using [x, y] for closed ranges 1106 // and (x, y) for open ranges. These ranges are modular, corresponding with 1107 // a common treatment of C integer overflow. This means that these methods 1108 // do not have to worry about overflow; RangeSet::Intersect can handle such a 1109 // "wraparound" range. 1110 // As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1, 1111 // UINT_MAX, 0, 1, and 2. 1112 1113 ProgramStateRef 1114 RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym, 1115 const llvm::APSInt &Int, 1116 const llvm::APSInt &Adjustment) { 1117 // Before we do any real work, see if the value can even show up. 1118 APSIntType AdjustmentType(Adjustment); 1119 if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within) 1120 return St; 1121 1122 llvm::APSInt Lower = AdjustmentType.convert(Int) - Adjustment; 1123 llvm::APSInt Upper = Lower; 1124 --Lower; 1125 ++Upper; 1126 1127 // [Int-Adjustment+1, Int-Adjustment-1] 1128 // Notice that the lower bound is greater than the upper bound. 1129 RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, Upper, Lower); 1130 return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); 1131 } 1132 1133 ProgramStateRef 1134 RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym, 1135 const llvm::APSInt &Int, 1136 const llvm::APSInt &Adjustment) { 1137 // Before we do any real work, see if the value can even show up. 1138 APSIntType AdjustmentType(Adjustment); 1139 if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within) 1140 return nullptr; 1141 1142 // [Int-Adjustment, Int-Adjustment] 1143 llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment; 1144 RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt); 1145 return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); 1146 } 1147 1148 RangeSet RangeConstraintManager::getSymLTRange(ProgramStateRef St, 1149 SymbolRef Sym, 1150 const llvm::APSInt &Int, 1151 const llvm::APSInt &Adjustment) { 1152 // Before we do any real work, see if the value can even show up. 1153 APSIntType AdjustmentType(Adjustment); 1154 switch (AdjustmentType.testInRange(Int, true)) { 1155 case APSIntType::RTR_Below: 1156 return F.getEmptySet(); 1157 case APSIntType::RTR_Within: 1158 break; 1159 case APSIntType::RTR_Above: 1160 return getRange(St, Sym); 1161 } 1162 1163 // Special case for Int == Min. This is always false. 1164 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); 1165 llvm::APSInt Min = AdjustmentType.getMinValue(); 1166 if (ComparisonVal == Min) 1167 return F.getEmptySet(); 1168 1169 llvm::APSInt Lower = Min - Adjustment; 1170 llvm::APSInt Upper = ComparisonVal - Adjustment; 1171 --Upper; 1172 1173 return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); 1174 } 1175 1176 ProgramStateRef 1177 RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym, 1178 const llvm::APSInt &Int, 1179 const llvm::APSInt &Adjustment) { 1180 RangeSet New = getSymLTRange(St, Sym, Int, Adjustment); 1181 return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); 1182 } 1183 1184 RangeSet RangeConstraintManager::getSymGTRange(ProgramStateRef St, 1185 SymbolRef Sym, 1186 const llvm::APSInt &Int, 1187 const llvm::APSInt &Adjustment) { 1188 // Before we do any real work, see if the value can even show up. 1189 APSIntType AdjustmentType(Adjustment); 1190 switch (AdjustmentType.testInRange(Int, true)) { 1191 case APSIntType::RTR_Below: 1192 return getRange(St, Sym); 1193 case APSIntType::RTR_Within: 1194 break; 1195 case APSIntType::RTR_Above: 1196 return F.getEmptySet(); 1197 } 1198 1199 // Special case for Int == Max. This is always false. 1200 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); 1201 llvm::APSInt Max = AdjustmentType.getMaxValue(); 1202 if (ComparisonVal == Max) 1203 return F.getEmptySet(); 1204 1205 llvm::APSInt Lower = ComparisonVal - Adjustment; 1206 llvm::APSInt Upper = Max - Adjustment; 1207 ++Lower; 1208 1209 return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); 1210 } 1211 1212 ProgramStateRef 1213 RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym, 1214 const llvm::APSInt &Int, 1215 const llvm::APSInt &Adjustment) { 1216 RangeSet New = getSymGTRange(St, Sym, Int, Adjustment); 1217 return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); 1218 } 1219 1220 RangeSet RangeConstraintManager::getSymGERange(ProgramStateRef St, 1221 SymbolRef Sym, 1222 const llvm::APSInt &Int, 1223 const llvm::APSInt &Adjustment) { 1224 // Before we do any real work, see if the value can even show up. 1225 APSIntType AdjustmentType(Adjustment); 1226 switch (AdjustmentType.testInRange(Int, true)) { 1227 case APSIntType::RTR_Below: 1228 return getRange(St, Sym); 1229 case APSIntType::RTR_Within: 1230 break; 1231 case APSIntType::RTR_Above: 1232 return F.getEmptySet(); 1233 } 1234 1235 // Special case for Int == Min. This is always feasible. 1236 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); 1237 llvm::APSInt Min = AdjustmentType.getMinValue(); 1238 if (ComparisonVal == Min) 1239 return getRange(St, Sym); 1240 1241 llvm::APSInt Max = AdjustmentType.getMaxValue(); 1242 llvm::APSInt Lower = ComparisonVal - Adjustment; 1243 llvm::APSInt Upper = Max - Adjustment; 1244 1245 return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); 1246 } 1247 1248 ProgramStateRef 1249 RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym, 1250 const llvm::APSInt &Int, 1251 const llvm::APSInt &Adjustment) { 1252 RangeSet New = getSymGERange(St, Sym, Int, Adjustment); 1253 return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); 1254 } 1255 1256 RangeSet RangeConstraintManager::getSymLERange( 1257 llvm::function_ref<RangeSet()> RS, 1258 const llvm::APSInt &Int, 1259 const llvm::APSInt &Adjustment) { 1260 // Before we do any real work, see if the value can even show up. 1261 APSIntType AdjustmentType(Adjustment); 1262 switch (AdjustmentType.testInRange(Int, true)) { 1263 case APSIntType::RTR_Below: 1264 return F.getEmptySet(); 1265 case APSIntType::RTR_Within: 1266 break; 1267 case APSIntType::RTR_Above: 1268 return RS(); 1269 } 1270 1271 // Special case for Int == Max. This is always feasible. 1272 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); 1273 llvm::APSInt Max = AdjustmentType.getMaxValue(); 1274 if (ComparisonVal == Max) 1275 return RS(); 1276 1277 llvm::APSInt Min = AdjustmentType.getMinValue(); 1278 llvm::APSInt Lower = Min - Adjustment; 1279 llvm::APSInt Upper = ComparisonVal - Adjustment; 1280 1281 return RS().Intersect(getBasicVals(), F, Lower, Upper); 1282 } 1283 1284 RangeSet RangeConstraintManager::getSymLERange(ProgramStateRef St, 1285 SymbolRef Sym, 1286 const llvm::APSInt &Int, 1287 const llvm::APSInt &Adjustment) { 1288 return getSymLERange([&] { return getRange(St, Sym); }, Int, Adjustment); 1289 } 1290 1291 ProgramStateRef 1292 RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym, 1293 const llvm::APSInt &Int, 1294 const llvm::APSInt &Adjustment) { 1295 RangeSet New = getSymLERange(St, Sym, Int, Adjustment); 1296 return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); 1297 } 1298 1299 ProgramStateRef RangeConstraintManager::assumeSymWithinInclusiveRange( 1300 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 1301 const llvm::APSInt &To, const llvm::APSInt &Adjustment) { 1302 RangeSet New = getSymGERange(State, Sym, From, Adjustment); 1303 if (New.isEmpty()) 1304 return nullptr; 1305 RangeSet Out = getSymLERange([&] { return New; }, To, Adjustment); 1306 return Out.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, Out); 1307 } 1308 1309 ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange( 1310 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 1311 const llvm::APSInt &To, const llvm::APSInt &Adjustment) { 1312 RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment); 1313 RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment); 1314 RangeSet New(RangeLT.addRange(F, RangeGT)); 1315 return New.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, New); 1316 } 1317 1318 //===----------------------------------------------------------------------===// 1319 // Pretty-printing. 1320 //===----------------------------------------------------------------------===// 1321 1322 void RangeConstraintManager::printJson(raw_ostream &Out, ProgramStateRef State, 1323 const char *NL, unsigned int Space, 1324 bool IsDot) const { 1325 ConstraintRangeTy Constraints = State->get<ConstraintRange>(); 1326 1327 Indent(Out, Space, IsDot) << "\"constraints\": "; 1328 if (Constraints.isEmpty()) { 1329 Out << "null," << NL; 1330 return; 1331 } 1332 1333 ++Space; 1334 Out << '[' << NL; 1335 for (ConstraintRangeTy::iterator I = Constraints.begin(); 1336 I != Constraints.end(); ++I) { 1337 Indent(Out, Space, IsDot) 1338 << "{ \"symbol\": \"" << I.getKey() << "\", \"range\": \""; 1339 I.getData().print(Out); 1340 Out << "\" }"; 1341 1342 if (std::next(I) != Constraints.end()) 1343 Out << ','; 1344 Out << NL; 1345 } 1346 1347 --Space; 1348 Indent(Out, Space, IsDot) << "]," << NL; 1349 } 1350