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 RangeSet RangeSet::Delete(BasicValueFactory &BV, Factory &F, 368 const llvm::APSInt &Point) const { 369 llvm::APSInt Upper = Point; 370 llvm::APSInt Lower = Point; 371 372 ++Upper; 373 --Lower; 374 375 // Notice that the lower bound is greater than the upper bound. 376 return Intersect(BV, F, Upper, Lower); 377 } 378 379 void RangeSet::print(raw_ostream &os) const { 380 bool isFirst = true; 381 os << "{ "; 382 for (iterator i = begin(), e = end(); i != e; ++i) { 383 if (isFirst) 384 isFirst = false; 385 else 386 os << ", "; 387 388 os << '[' << i->From().toString(10) << ", " << i->To().toString(10) 389 << ']'; 390 } 391 os << " }"; 392 } 393 394 REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(SymbolSet, SymbolRef) 395 396 namespace { 397 class EquivalenceClass; 398 } // end anonymous namespace 399 400 REGISTER_MAP_WITH_PROGRAMSTATE(ClassMap, SymbolRef, EquivalenceClass) 401 REGISTER_MAP_WITH_PROGRAMSTATE(ClassMembers, EquivalenceClass, SymbolSet) 402 REGISTER_MAP_WITH_PROGRAMSTATE(ConstraintRange, EquivalenceClass, RangeSet) 403 404 REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(ClassSet, EquivalenceClass) 405 REGISTER_MAP_WITH_PROGRAMSTATE(DisequalityMap, EquivalenceClass, ClassSet) 406 407 namespace { 408 /// This class encapsulates a set of symbols equal to each other. 409 /// 410 /// The main idea of the approach requiring such classes is in narrowing 411 /// and sharing constraints between symbols within the class. Also we can 412 /// conclude that there is no practical need in storing constraints for 413 /// every member of the class separately. 414 /// 415 /// Main terminology: 416 /// 417 /// * "Equivalence class" is an object of this class, which can be efficiently 418 /// compared to other classes. It represents the whole class without 419 /// storing the actual in it. The members of the class however can be 420 /// retrieved from the state. 421 /// 422 /// * "Class members" are the symbols corresponding to the class. This means 423 /// that A == B for every member symbols A and B from the class. Members of 424 /// each class are stored in the state. 425 /// 426 /// * "Trivial class" is a class that has and ever had only one same symbol. 427 /// 428 /// * "Merge operation" merges two classes into one. It is the main operation 429 /// to produce non-trivial classes. 430 /// If, at some point, we can assume that two symbols from two distinct 431 /// classes are equal, we can merge these classes. 432 class EquivalenceClass : public llvm::FoldingSetNode { 433 public: 434 /// Find equivalence class for the given symbol in the given state. 435 LLVM_NODISCARD static inline EquivalenceClass find(ProgramStateRef State, 436 SymbolRef Sym); 437 438 /// Merge classes for the given symbols and return a new state. 439 LLVM_NODISCARD static inline ProgramStateRef 440 merge(BasicValueFactory &BV, RangeSet::Factory &F, ProgramStateRef State, 441 SymbolRef First, SymbolRef Second); 442 // Merge this class with the given class and return a new state. 443 LLVM_NODISCARD inline ProgramStateRef merge(BasicValueFactory &BV, 444 RangeSet::Factory &F, 445 ProgramStateRef State, 446 EquivalenceClass Other); 447 448 /// Return a set of class members for the given state. 449 LLVM_NODISCARD inline SymbolSet getClassMembers(ProgramStateRef State); 450 /// Return true if the current class is trivial in the given state. 451 LLVM_NODISCARD inline bool isTrivial(ProgramStateRef State); 452 /// Return true if the current class is trivial and its only member is dead. 453 LLVM_NODISCARD inline bool isTriviallyDead(ProgramStateRef State, 454 SymbolReaper &Reaper); 455 456 LLVM_NODISCARD static inline ProgramStateRef 457 markDisequal(BasicValueFactory &BV, RangeSet::Factory &F, 458 ProgramStateRef State, SymbolRef First, SymbolRef Second); 459 LLVM_NODISCARD static inline ProgramStateRef 460 markDisequal(BasicValueFactory &BV, RangeSet::Factory &F, 461 ProgramStateRef State, EquivalenceClass First, 462 EquivalenceClass Second); 463 LLVM_NODISCARD inline ProgramStateRef 464 markDisequal(BasicValueFactory &BV, RangeSet::Factory &F, 465 ProgramStateRef State, EquivalenceClass Other) const; 466 LLVM_NODISCARD static inline ClassSet 467 getDisequalClasses(ProgramStateRef State, SymbolRef Sym); 468 LLVM_NODISCARD inline ClassSet 469 getDisequalClasses(ProgramStateRef State) const; 470 LLVM_NODISCARD inline ClassSet 471 getDisequalClasses(DisequalityMapTy Map, ClassSet::Factory &Factory) const; 472 473 LLVM_NODISCARD static inline Optional<bool> 474 areEqual(ProgramStateRef State, SymbolRef First, SymbolRef Second); 475 476 /// Check equivalence data for consistency. 477 LLVM_NODISCARD LLVM_ATTRIBUTE_UNUSED static bool 478 isClassDataConsistent(ProgramStateRef State); 479 480 LLVM_NODISCARD QualType getType() const { 481 return getRepresentativeSymbol()->getType(); 482 } 483 484 EquivalenceClass() = delete; 485 EquivalenceClass(const EquivalenceClass &) = default; 486 EquivalenceClass &operator=(const EquivalenceClass &) = delete; 487 EquivalenceClass(EquivalenceClass &&) = default; 488 EquivalenceClass &operator=(EquivalenceClass &&) = delete; 489 490 bool operator==(const EquivalenceClass &Other) const { 491 return ID == Other.ID; 492 } 493 bool operator<(const EquivalenceClass &Other) const { return ID < Other.ID; } 494 bool operator!=(const EquivalenceClass &Other) const { 495 return !operator==(Other); 496 } 497 498 static void Profile(llvm::FoldingSetNodeID &ID, uintptr_t CID) { 499 ID.AddInteger(CID); 500 } 501 502 void Profile(llvm::FoldingSetNodeID &ID) const { Profile(ID, this->ID); } 503 504 private: 505 /* implicit */ EquivalenceClass(SymbolRef Sym) 506 : ID(reinterpret_cast<uintptr_t>(Sym)) {} 507 508 /// This function is intended to be used ONLY within the class. 509 /// The fact that ID is a pointer to a symbol is an implementation detail 510 /// and should stay that way. 511 /// In the current implementation, we use it to retrieve the only member 512 /// of the trivial class. 513 SymbolRef getRepresentativeSymbol() const { 514 return reinterpret_cast<SymbolRef>(ID); 515 } 516 static inline SymbolSet::Factory &getMembersFactory(ProgramStateRef State); 517 518 inline ProgramStateRef mergeImpl(BasicValueFactory &BV, RangeSet::Factory &F, 519 ProgramStateRef State, SymbolSet Members, 520 EquivalenceClass Other, 521 SymbolSet OtherMembers); 522 static inline void 523 addToDisequalityInfo(DisequalityMapTy &Info, ConstraintRangeTy &Constraints, 524 BasicValueFactory &BV, RangeSet::Factory &F, 525 ProgramStateRef State, EquivalenceClass First, 526 EquivalenceClass Second); 527 528 /// This is a unique identifier of the class. 529 uintptr_t ID; 530 }; 531 532 //===----------------------------------------------------------------------===// 533 // Constraint functions 534 //===----------------------------------------------------------------------===// 535 536 LLVM_NODISCARD inline const RangeSet *getConstraint(ProgramStateRef State, 537 EquivalenceClass Class) { 538 return State->get<ConstraintRange>(Class); 539 } 540 541 LLVM_NODISCARD inline const RangeSet *getConstraint(ProgramStateRef State, 542 SymbolRef Sym) { 543 return getConstraint(State, EquivalenceClass::find(State, Sym)); 544 } 545 546 //===----------------------------------------------------------------------===// 547 // Equality/diseqiality abstraction 548 //===----------------------------------------------------------------------===// 549 550 /// A small helper structure representing symbolic equality. 551 /// 552 /// Equality check can have different forms (like a == b or a - b) and this 553 /// class encapsulates those away if the only thing the user wants to check - 554 /// whether it's equality/diseqiality or not and have an easy access to the 555 /// compared symbols. 556 struct EqualityInfo { 557 public: 558 SymbolRef Left, Right; 559 // true for equality and false for disequality. 560 bool IsEquality = true; 561 562 void invert() { IsEquality = !IsEquality; } 563 /// Extract equality information from the given symbol and the constants. 564 /// 565 /// This function assumes the following expression Sym + Adjustment != Int. 566 /// It is a default because the most widespread case of the equality check 567 /// is (A == B) + 0 != 0. 568 static Optional<EqualityInfo> extract(SymbolRef Sym, const llvm::APSInt &Int, 569 const llvm::APSInt &Adjustment) { 570 // As of now, the only equality form supported is Sym + 0 != 0. 571 if (!Int.isNullValue() || !Adjustment.isNullValue()) 572 return llvm::None; 573 574 return extract(Sym); 575 } 576 /// Extract equality information from the given symbol. 577 static Optional<EqualityInfo> extract(SymbolRef Sym) { 578 return EqualityExtractor().Visit(Sym); 579 } 580 581 private: 582 class EqualityExtractor 583 : public SymExprVisitor<EqualityExtractor, Optional<EqualityInfo>> { 584 public: 585 Optional<EqualityInfo> VisitSymSymExpr(const SymSymExpr *Sym) const { 586 switch (Sym->getOpcode()) { 587 case BO_Sub: 588 // This case is: A - B != 0 -> disequality check. 589 return EqualityInfo{Sym->getLHS(), Sym->getRHS(), false}; 590 case BO_EQ: 591 // This case is: A == B != 0 -> equality check. 592 return EqualityInfo{Sym->getLHS(), Sym->getRHS(), true}; 593 case BO_NE: 594 // This case is: A != B != 0 -> diseqiality check. 595 return EqualityInfo{Sym->getLHS(), Sym->getRHS(), false}; 596 default: 597 return llvm::None; 598 } 599 } 600 }; 601 }; 602 603 //===----------------------------------------------------------------------===// 604 // Intersection functions 605 //===----------------------------------------------------------------------===// 606 607 template <class SecondTy, class... RestTy> 608 LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory &BV, 609 RangeSet::Factory &F, RangeSet Head, 610 SecondTy Second, RestTy... Tail); 611 612 template <class... RangeTy> struct IntersectionTraits; 613 614 template <class... TailTy> struct IntersectionTraits<RangeSet, TailTy...> { 615 // Found RangeSet, no need to check any further 616 using Type = RangeSet; 617 }; 618 619 template <> struct IntersectionTraits<> { 620 // We ran out of types, and we didn't find any RangeSet, so the result should 621 // be optional. 622 using Type = Optional<RangeSet>; 623 }; 624 625 template <class OptionalOrPointer, class... TailTy> 626 struct IntersectionTraits<OptionalOrPointer, TailTy...> { 627 // If current type is Optional or a raw pointer, we should keep looking. 628 using Type = typename IntersectionTraits<TailTy...>::Type; 629 }; 630 631 template <class EndTy> 632 LLVM_NODISCARD inline EndTy intersect(BasicValueFactory &BV, 633 RangeSet::Factory &F, EndTy End) { 634 // If the list contains only RangeSet or Optional<RangeSet>, simply return 635 // that range set. 636 return End; 637 } 638 639 LLVM_NODISCARD LLVM_ATTRIBUTE_UNUSED inline Optional<RangeSet> 640 intersect(BasicValueFactory &BV, RangeSet::Factory &F, const RangeSet *End) { 641 // This is an extraneous conversion from a raw pointer into Optional<RangeSet> 642 if (End) { 643 return *End; 644 } 645 return llvm::None; 646 } 647 648 template <class... RestTy> 649 LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory &BV, 650 RangeSet::Factory &F, RangeSet Head, 651 RangeSet Second, RestTy... Tail) { 652 // Here we call either the <RangeSet,RangeSet,...> or <RangeSet,...> version 653 // of the function and can be sure that the result is RangeSet. 654 return intersect(BV, F, Head.Intersect(BV, F, Second), Tail...); 655 } 656 657 template <class SecondTy, class... RestTy> 658 LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory &BV, 659 RangeSet::Factory &F, RangeSet Head, 660 SecondTy Second, RestTy... Tail) { 661 if (Second) { 662 // Here we call the <RangeSet,RangeSet,...> version of the function... 663 return intersect(BV, F, Head, *Second, Tail...); 664 } 665 // ...and here it is either <RangeSet,RangeSet,...> or <RangeSet,...>, which 666 // means that the result is definitely RangeSet. 667 return intersect(BV, F, Head, Tail...); 668 } 669 670 /// Main generic intersect function. 671 /// It intersects all of the given range sets. If some of the given arguments 672 /// don't hold a range set (nullptr or llvm::None), the function will skip them. 673 /// 674 /// Available representations for the arguments are: 675 /// * RangeSet 676 /// * Optional<RangeSet> 677 /// * RangeSet * 678 /// Pointer to a RangeSet is automatically assumed to be nullable and will get 679 /// checked as well as the optional version. If this behaviour is undesired, 680 /// please dereference the pointer in the call. 681 /// 682 /// Return type depends on the arguments' types. If we can be sure in compile 683 /// time that there will be a range set as a result, the returning type is 684 /// simply RangeSet, in other cases we have to back off to Optional<RangeSet>. 685 /// 686 /// Please, prefer optional range sets to raw pointers. If the last argument is 687 /// a raw pointer and all previous arguments are None, it will cost one 688 /// additional check to convert RangeSet * into Optional<RangeSet>. 689 template <class HeadTy, class SecondTy, class... RestTy> 690 LLVM_NODISCARD inline 691 typename IntersectionTraits<HeadTy, SecondTy, RestTy...>::Type 692 intersect(BasicValueFactory &BV, RangeSet::Factory &F, HeadTy Head, 693 SecondTy Second, RestTy... Tail) { 694 if (Head) { 695 return intersect(BV, F, *Head, Second, Tail...); 696 } 697 return intersect(BV, F, Second, Tail...); 698 } 699 700 //===----------------------------------------------------------------------===// 701 // Symbolic reasoning logic 702 //===----------------------------------------------------------------------===// 703 704 /// A little component aggregating all of the reasoning we have about 705 /// the ranges of symbolic expressions. 706 /// 707 /// Even when we don't know the exact values of the operands, we still 708 /// can get a pretty good estimate of the result's range. 709 class SymbolicRangeInferrer 710 : public SymExprVisitor<SymbolicRangeInferrer, RangeSet> { 711 public: 712 template <class SourceType> 713 static RangeSet inferRange(BasicValueFactory &BV, RangeSet::Factory &F, 714 ProgramStateRef State, SourceType Origin) { 715 SymbolicRangeInferrer Inferrer(BV, F, State); 716 return Inferrer.infer(Origin); 717 } 718 719 RangeSet VisitSymExpr(SymbolRef Sym) { 720 // If we got to this function, the actual type of the symbolic 721 // expression is not supported for advanced inference. 722 // In this case, we simply backoff to the default "let's simply 723 // infer the range from the expression's type". 724 return infer(Sym->getType()); 725 } 726 727 RangeSet VisitSymIntExpr(const SymIntExpr *Sym) { 728 return VisitBinaryOperator(Sym); 729 } 730 731 RangeSet VisitIntSymExpr(const IntSymExpr *Sym) { 732 return VisitBinaryOperator(Sym); 733 } 734 735 RangeSet VisitSymSymExpr(const SymSymExpr *Sym) { 736 return VisitBinaryOperator(Sym); 737 } 738 739 private: 740 SymbolicRangeInferrer(BasicValueFactory &BV, RangeSet::Factory &F, 741 ProgramStateRef S) 742 : ValueFactory(BV), RangeFactory(F), State(S) {} 743 744 /// Infer range information from the given integer constant. 745 /// 746 /// It's not a real "inference", but is here for operating with 747 /// sub-expressions in a more polymorphic manner. 748 RangeSet inferAs(const llvm::APSInt &Val, QualType) { 749 return {RangeFactory, Val}; 750 } 751 752 /// Infer range information from symbol in the context of the given type. 753 RangeSet inferAs(SymbolRef Sym, QualType DestType) { 754 QualType ActualType = Sym->getType(); 755 // Check that we can reason about the symbol at all. 756 if (ActualType->isIntegralOrEnumerationType() || 757 Loc::isLocType(ActualType)) { 758 return infer(Sym); 759 } 760 // Otherwise, let's simply infer from the destination type. 761 // We couldn't figure out nothing else about that expression. 762 return infer(DestType); 763 } 764 765 RangeSet infer(SymbolRef Sym) { 766 if (Optional<RangeSet> ConstraintBasedRange = intersect( 767 ValueFactory, RangeFactory, getConstraint(State, Sym), 768 // If Sym is a difference of symbols A - B, then maybe we have range 769 // set stored for B - A. 770 // 771 // If we have range set stored for both A - B and B - A then 772 // calculate the effective range set by intersecting the range set 773 // for A - B and the negated range set of B - A. 774 getRangeForNegatedSub(Sym), getRangeForEqualities(Sym))) { 775 return *ConstraintBasedRange; 776 } 777 778 // If Sym is a comparison expression (except <=>), 779 // find any other comparisons with the same operands. 780 // See function description. 781 if (Optional<RangeSet> CmpRangeSet = getRangeForComparisonSymbol(Sym)) { 782 return *CmpRangeSet; 783 } 784 785 return Visit(Sym); 786 } 787 788 RangeSet infer(EquivalenceClass Class) { 789 if (const RangeSet *AssociatedConstraint = getConstraint(State, Class)) 790 return *AssociatedConstraint; 791 792 return infer(Class.getType()); 793 } 794 795 /// Infer range information solely from the type. 796 RangeSet infer(QualType T) { 797 // Lazily generate a new RangeSet representing all possible values for the 798 // given symbol type. 799 RangeSet Result(RangeFactory, ValueFactory.getMinValue(T), 800 ValueFactory.getMaxValue(T)); 801 802 // References are known to be non-zero. 803 if (T->isReferenceType()) 804 return assumeNonZero(Result, T); 805 806 return Result; 807 } 808 809 template <class BinarySymExprTy> 810 RangeSet VisitBinaryOperator(const BinarySymExprTy *Sym) { 811 // TODO #1: VisitBinaryOperator implementation might not make a good 812 // use of the inferred ranges. In this case, we might be calculating 813 // everything for nothing. This being said, we should introduce some 814 // sort of laziness mechanism here. 815 // 816 // TODO #2: We didn't go into the nested expressions before, so it 817 // might cause us spending much more time doing the inference. 818 // This can be a problem for deeply nested expressions that are 819 // involved in conditions and get tested continuously. We definitely 820 // need to address this issue and introduce some sort of caching 821 // in here. 822 QualType ResultType = Sym->getType(); 823 return VisitBinaryOperator(inferAs(Sym->getLHS(), ResultType), 824 Sym->getOpcode(), 825 inferAs(Sym->getRHS(), ResultType), ResultType); 826 } 827 828 RangeSet VisitBinaryOperator(RangeSet LHS, BinaryOperator::Opcode Op, 829 RangeSet RHS, QualType T) { 830 switch (Op) { 831 case BO_Or: 832 return VisitBinaryOperator<BO_Or>(LHS, RHS, T); 833 case BO_And: 834 return VisitBinaryOperator<BO_And>(LHS, RHS, T); 835 case BO_Rem: 836 return VisitBinaryOperator<BO_Rem>(LHS, RHS, T); 837 default: 838 return infer(T); 839 } 840 } 841 842 //===----------------------------------------------------------------------===// 843 // Ranges and operators 844 //===----------------------------------------------------------------------===// 845 846 /// Return a rough approximation of the given range set. 847 /// 848 /// For the range set: 849 /// { [x_0, y_0], [x_1, y_1], ... , [x_N, y_N] } 850 /// it will return the range [x_0, y_N]. 851 static Range fillGaps(RangeSet Origin) { 852 assert(!Origin.isEmpty()); 853 return {Origin.getMinValue(), Origin.getMaxValue()}; 854 } 855 856 /// Try to convert given range into the given type. 857 /// 858 /// It will return llvm::None only when the trivial conversion is possible. 859 llvm::Optional<Range> convert(const Range &Origin, APSIntType To) { 860 if (To.testInRange(Origin.From(), false) != APSIntType::RTR_Within || 861 To.testInRange(Origin.To(), false) != APSIntType::RTR_Within) { 862 return llvm::None; 863 } 864 return Range(ValueFactory.Convert(To, Origin.From()), 865 ValueFactory.Convert(To, Origin.To())); 866 } 867 868 template <BinaryOperator::Opcode Op> 869 RangeSet VisitBinaryOperator(RangeSet LHS, RangeSet RHS, QualType T) { 870 // We should propagate information about unfeasbility of one of the 871 // operands to the resulting range. 872 if (LHS.isEmpty() || RHS.isEmpty()) { 873 return RangeFactory.getEmptySet(); 874 } 875 876 Range CoarseLHS = fillGaps(LHS); 877 Range CoarseRHS = fillGaps(RHS); 878 879 APSIntType ResultType = ValueFactory.getAPSIntType(T); 880 881 // We need to convert ranges to the resulting type, so we can compare values 882 // and combine them in a meaningful (in terms of the given operation) way. 883 auto ConvertedCoarseLHS = convert(CoarseLHS, ResultType); 884 auto ConvertedCoarseRHS = convert(CoarseRHS, ResultType); 885 886 // It is hard to reason about ranges when conversion changes 887 // borders of the ranges. 888 if (!ConvertedCoarseLHS || !ConvertedCoarseRHS) { 889 return infer(T); 890 } 891 892 return VisitBinaryOperator<Op>(*ConvertedCoarseLHS, *ConvertedCoarseRHS, T); 893 } 894 895 template <BinaryOperator::Opcode Op> 896 RangeSet VisitBinaryOperator(Range LHS, Range RHS, QualType T) { 897 return infer(T); 898 } 899 900 /// Return a symmetrical range for the given range and type. 901 /// 902 /// If T is signed, return the smallest range [-x..x] that covers the original 903 /// range, or [-min(T), max(T)] if the aforementioned symmetric range doesn't 904 /// exist due to original range covering min(T)). 905 /// 906 /// If T is unsigned, return the smallest range [0..x] that covers the 907 /// original range. 908 Range getSymmetricalRange(Range Origin, QualType T) { 909 APSIntType RangeType = ValueFactory.getAPSIntType(T); 910 911 if (RangeType.isUnsigned()) { 912 return Range(ValueFactory.getMinValue(RangeType), Origin.To()); 913 } 914 915 if (Origin.From().isMinSignedValue()) { 916 // If mini is a minimal signed value, absolute value of it is greater 917 // than the maximal signed value. In order to avoid these 918 // complications, we simply return the whole range. 919 return {ValueFactory.getMinValue(RangeType), 920 ValueFactory.getMaxValue(RangeType)}; 921 } 922 923 // At this point, we are sure that the type is signed and we can safely 924 // use unary - operator. 925 // 926 // While calculating absolute maximum, we can use the following formula 927 // because of these reasons: 928 // * If From >= 0 then To >= From and To >= -From. 929 // AbsMax == To == max(To, -From) 930 // * If To <= 0 then -From >= -To and -From >= From. 931 // AbsMax == -From == max(-From, To) 932 // * Otherwise, From <= 0, To >= 0, and 933 // AbsMax == max(abs(From), abs(To)) 934 llvm::APSInt AbsMax = std::max(-Origin.From(), Origin.To()); 935 936 // Intersection is guaranteed to be non-empty. 937 return {ValueFactory.getValue(-AbsMax), ValueFactory.getValue(AbsMax)}; 938 } 939 940 /// Return a range set subtracting zero from \p Domain. 941 RangeSet assumeNonZero(RangeSet Domain, QualType T) { 942 APSIntType IntType = ValueFactory.getAPSIntType(T); 943 return Domain.Delete(ValueFactory, RangeFactory, IntType.getZeroValue()); 944 } 945 946 // FIXME: Once SValBuilder supports unary minus, we should use SValBuilder to 947 // obtain the negated symbolic expression instead of constructing the 948 // symbol manually. This will allow us to support finding ranges of not 949 // only negated SymSymExpr-type expressions, but also of other, simpler 950 // expressions which we currently do not know how to negate. 951 Optional<RangeSet> getRangeForNegatedSub(SymbolRef Sym) { 952 if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) { 953 if (SSE->getOpcode() == BO_Sub) { 954 QualType T = Sym->getType(); 955 956 // Do not negate unsigned ranges 957 if (!T->isUnsignedIntegerOrEnumerationType() && 958 !T->isSignedIntegerOrEnumerationType()) 959 return llvm::None; 960 961 SymbolManager &SymMgr = State->getSymbolManager(); 962 SymbolRef NegatedSym = 963 SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, SSE->getLHS(), T); 964 965 if (const RangeSet *NegatedRange = getConstraint(State, NegatedSym)) { 966 return NegatedRange->Negate(ValueFactory, RangeFactory); 967 } 968 } 969 } 970 return llvm::None; 971 } 972 973 // Returns ranges only for binary comparison operators (except <=>) 974 // when left and right operands are symbolic values. 975 // Finds any other comparisons with the same operands. 976 // Then do logical calculations and refuse impossible branches. 977 // E.g. (x < y) and (x > y) at the same time are impossible. 978 // E.g. (x >= y) and (x != y) at the same time makes (x > y) true only. 979 // E.g. (x == y) and (y == x) are just reversed but the same. 980 // It covers all possible combinations (see CmpOpTable description). 981 // Note that `x` and `y` can also stand for subexpressions, 982 // not only for actual symbols. 983 Optional<RangeSet> getRangeForComparisonSymbol(SymbolRef Sym) { 984 const auto *SSE = dyn_cast<SymSymExpr>(Sym); 985 if (!SSE) 986 return llvm::None; 987 988 BinaryOperatorKind CurrentOP = SSE->getOpcode(); 989 990 // We currently do not support <=> (C++20). 991 if (!BinaryOperator::isComparisonOp(CurrentOP) || (CurrentOP == BO_Cmp)) 992 return llvm::None; 993 994 static const OperatorRelationsTable CmpOpTable{}; 995 996 const SymExpr *LHS = SSE->getLHS(); 997 const SymExpr *RHS = SSE->getRHS(); 998 QualType T = SSE->getType(); 999 1000 SymbolManager &SymMgr = State->getSymbolManager(); 1001 1002 int UnknownStates = 0; 1003 1004 // Loop goes through all of the columns exept the last one ('UnknownX2'). 1005 // We treat `UnknownX2` column separately at the end of the loop body. 1006 for (size_t i = 0; i < CmpOpTable.getCmpOpCount(); ++i) { 1007 1008 // Let's find an expression e.g. (x < y). 1009 BinaryOperatorKind QueriedOP = OperatorRelationsTable::getOpFromIndex(i); 1010 const SymSymExpr *SymSym = SymMgr.getSymSymExpr(LHS, QueriedOP, RHS, T); 1011 const RangeSet *QueriedRangeSet = getConstraint(State, SymSym); 1012 1013 // If ranges were not previously found, 1014 // try to find a reversed expression (y > x). 1015 if (!QueriedRangeSet) { 1016 const BinaryOperatorKind ROP = 1017 BinaryOperator::reverseComparisonOp(QueriedOP); 1018 SymSym = SymMgr.getSymSymExpr(RHS, ROP, LHS, T); 1019 QueriedRangeSet = getConstraint(State, SymSym); 1020 } 1021 1022 if (!QueriedRangeSet || QueriedRangeSet->isEmpty()) 1023 continue; 1024 1025 const llvm::APSInt *ConcreteValue = QueriedRangeSet->getConcreteValue(); 1026 const bool isInFalseBranch = 1027 ConcreteValue ? (*ConcreteValue == 0) : false; 1028 1029 // If it is a false branch, we shall be guided by opposite operator, 1030 // because the table is made assuming we are in the true branch. 1031 // E.g. when (x <= y) is false, then (x > y) is true. 1032 if (isInFalseBranch) 1033 QueriedOP = BinaryOperator::negateComparisonOp(QueriedOP); 1034 1035 OperatorRelationsTable::TriStateKind BranchState = 1036 CmpOpTable.getCmpOpState(CurrentOP, QueriedOP); 1037 1038 if (BranchState == OperatorRelationsTable::Unknown) { 1039 if (++UnknownStates == 2) 1040 // If we met both Unknown states. 1041 // if (x <= y) // assume true 1042 // if (x != y) // assume true 1043 // if (x < y) // would be also true 1044 // Get a state from `UnknownX2` column. 1045 BranchState = CmpOpTable.getCmpOpStateForUnknownX2(CurrentOP); 1046 else 1047 continue; 1048 } 1049 1050 return (BranchState == OperatorRelationsTable::True) ? getTrueRange(T) 1051 : getFalseRange(T); 1052 } 1053 1054 return llvm::None; 1055 } 1056 1057 Optional<RangeSet> getRangeForEqualities(SymbolRef Sym) { 1058 Optional<EqualityInfo> Equality = EqualityInfo::extract(Sym); 1059 1060 if (!Equality) 1061 return llvm::None; 1062 1063 if (Optional<bool> AreEqual = EquivalenceClass::areEqual( 1064 State, Equality->Left, Equality->Right)) { 1065 if (*AreEqual == Equality->IsEquality) { 1066 return getTrueRange(Sym->getType()); 1067 } 1068 return getFalseRange(Sym->getType()); 1069 } 1070 1071 return llvm::None; 1072 } 1073 1074 RangeSet getTrueRange(QualType T) { 1075 RangeSet TypeRange = infer(T); 1076 return assumeNonZero(TypeRange, T); 1077 } 1078 1079 RangeSet getFalseRange(QualType T) { 1080 const llvm::APSInt &Zero = ValueFactory.getValue(0, T); 1081 return RangeSet(RangeFactory, Zero); 1082 } 1083 1084 BasicValueFactory &ValueFactory; 1085 RangeSet::Factory &RangeFactory; 1086 ProgramStateRef State; 1087 }; 1088 1089 //===----------------------------------------------------------------------===// 1090 // Range-based reasoning about symbolic operations 1091 //===----------------------------------------------------------------------===// 1092 1093 template <> 1094 RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Or>(Range LHS, Range RHS, 1095 QualType T) { 1096 APSIntType ResultType = ValueFactory.getAPSIntType(T); 1097 llvm::APSInt Zero = ResultType.getZeroValue(); 1098 1099 bool IsLHSPositiveOrZero = LHS.From() >= Zero; 1100 bool IsRHSPositiveOrZero = RHS.From() >= Zero; 1101 1102 bool IsLHSNegative = LHS.To() < Zero; 1103 bool IsRHSNegative = RHS.To() < Zero; 1104 1105 // Check if both ranges have the same sign. 1106 if ((IsLHSPositiveOrZero && IsRHSPositiveOrZero) || 1107 (IsLHSNegative && IsRHSNegative)) { 1108 // The result is definitely greater or equal than any of the operands. 1109 const llvm::APSInt &Min = std::max(LHS.From(), RHS.From()); 1110 1111 // We estimate maximal value for positives as the maximal value for the 1112 // given type. For negatives, we estimate it with -1 (e.g. 0x11111111). 1113 // 1114 // TODO: We basically, limit the resulting range from below, but don't do 1115 // anything with the upper bound. 1116 // 1117 // For positive operands, it can be done as follows: for the upper 1118 // bound of LHS and RHS we calculate the most significant bit set. 1119 // Let's call it the N-th bit. Then we can estimate the maximal 1120 // number to be 2^(N+1)-1, i.e. the number with all the bits up to 1121 // the N-th bit set. 1122 const llvm::APSInt &Max = IsLHSNegative 1123 ? ValueFactory.getValue(--Zero) 1124 : ValueFactory.getMaxValue(ResultType); 1125 1126 return {RangeFactory, ValueFactory.getValue(Min), Max}; 1127 } 1128 1129 // Otherwise, let's check if at least one of the operands is negative. 1130 if (IsLHSNegative || IsRHSNegative) { 1131 // This means that the result is definitely negative as well. 1132 return {RangeFactory, ValueFactory.getMinValue(ResultType), 1133 ValueFactory.getValue(--Zero)}; 1134 } 1135 1136 RangeSet DefaultRange = infer(T); 1137 1138 // It is pretty hard to reason about operands with different signs 1139 // (and especially with possibly different signs). We simply check if it 1140 // can be zero. In order to conclude that the result could not be zero, 1141 // at least one of the operands should be definitely not zero itself. 1142 if (!LHS.Includes(Zero) || !RHS.Includes(Zero)) { 1143 return assumeNonZero(DefaultRange, T); 1144 } 1145 1146 // Nothing much else to do here. 1147 return DefaultRange; 1148 } 1149 1150 template <> 1151 RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_And>(Range LHS, 1152 Range RHS, 1153 QualType T) { 1154 APSIntType ResultType = ValueFactory.getAPSIntType(T); 1155 llvm::APSInt Zero = ResultType.getZeroValue(); 1156 1157 bool IsLHSPositiveOrZero = LHS.From() >= Zero; 1158 bool IsRHSPositiveOrZero = RHS.From() >= Zero; 1159 1160 bool IsLHSNegative = LHS.To() < Zero; 1161 bool IsRHSNegative = RHS.To() < Zero; 1162 1163 // Check if both ranges have the same sign. 1164 if ((IsLHSPositiveOrZero && IsRHSPositiveOrZero) || 1165 (IsLHSNegative && IsRHSNegative)) { 1166 // The result is definitely less or equal than any of the operands. 1167 const llvm::APSInt &Max = std::min(LHS.To(), RHS.To()); 1168 1169 // We conservatively estimate lower bound to be the smallest positive 1170 // or negative value corresponding to the sign of the operands. 1171 const llvm::APSInt &Min = IsLHSNegative 1172 ? ValueFactory.getMinValue(ResultType) 1173 : ValueFactory.getValue(Zero); 1174 1175 return {RangeFactory, Min, Max}; 1176 } 1177 1178 // Otherwise, let's check if at least one of the operands is positive. 1179 if (IsLHSPositiveOrZero || IsRHSPositiveOrZero) { 1180 // This makes result definitely positive. 1181 // 1182 // We can also reason about a maximal value by finding the maximal 1183 // value of the positive operand. 1184 const llvm::APSInt &Max = IsLHSPositiveOrZero ? LHS.To() : RHS.To(); 1185 1186 // The minimal value on the other hand is much harder to reason about. 1187 // The only thing we know for sure is that the result is positive. 1188 return {RangeFactory, ValueFactory.getValue(Zero), 1189 ValueFactory.getValue(Max)}; 1190 } 1191 1192 // Nothing much else to do here. 1193 return infer(T); 1194 } 1195 1196 template <> 1197 RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Rem>(Range LHS, 1198 Range RHS, 1199 QualType T) { 1200 llvm::APSInt Zero = ValueFactory.getAPSIntType(T).getZeroValue(); 1201 1202 Range ConservativeRange = getSymmetricalRange(RHS, T); 1203 1204 llvm::APSInt Max = ConservativeRange.To(); 1205 llvm::APSInt Min = ConservativeRange.From(); 1206 1207 if (Max == Zero) { 1208 // It's an undefined behaviour to divide by 0 and it seems like we know 1209 // for sure that RHS is 0. Let's say that the resulting range is 1210 // simply infeasible for that matter. 1211 return RangeFactory.getEmptySet(); 1212 } 1213 1214 // At this point, our conservative range is closed. The result, however, 1215 // couldn't be greater than the RHS' maximal absolute value. Because of 1216 // this reason, we turn the range into open (or half-open in case of 1217 // unsigned integers). 1218 // 1219 // While we operate on integer values, an open interval (a, b) can be easily 1220 // represented by the closed interval [a + 1, b - 1]. And this is exactly 1221 // what we do next. 1222 // 1223 // If we are dealing with unsigned case, we shouldn't move the lower bound. 1224 if (Min.isSigned()) { 1225 ++Min; 1226 } 1227 --Max; 1228 1229 bool IsLHSPositiveOrZero = LHS.From() >= Zero; 1230 bool IsRHSPositiveOrZero = RHS.From() >= Zero; 1231 1232 // Remainder operator results with negative operands is implementation 1233 // defined. Positive cases are much easier to reason about though. 1234 if (IsLHSPositiveOrZero && IsRHSPositiveOrZero) { 1235 // If maximal value of LHS is less than maximal value of RHS, 1236 // the result won't get greater than LHS.To(). 1237 Max = std::min(LHS.To(), Max); 1238 // We want to check if it is a situation similar to the following: 1239 // 1240 // <------------|---[ LHS ]--------[ RHS ]-----> 1241 // -INF 0 +INF 1242 // 1243 // In this situation, we can conclude that (LHS / RHS) == 0 and 1244 // (LHS % RHS) == LHS. 1245 Min = LHS.To() < RHS.From() ? LHS.From() : Zero; 1246 } 1247 1248 // Nevertheless, the symmetrical range for RHS is a conservative estimate 1249 // for any sign of either LHS, or RHS. 1250 return {RangeFactory, ValueFactory.getValue(Min), ValueFactory.getValue(Max)}; 1251 } 1252 1253 //===----------------------------------------------------------------------===// 1254 // Constraint manager implementation details 1255 //===----------------------------------------------------------------------===// 1256 1257 class RangeConstraintManager : public RangedConstraintManager { 1258 public: 1259 RangeConstraintManager(ExprEngine *EE, SValBuilder &SVB) 1260 : RangedConstraintManager(EE, SVB) {} 1261 1262 //===------------------------------------------------------------------===// 1263 // Implementation for interface from ConstraintManager. 1264 //===------------------------------------------------------------------===// 1265 1266 bool haveEqualConstraints(ProgramStateRef S1, 1267 ProgramStateRef S2) const override { 1268 // NOTE: ClassMembers are as simple as back pointers for ClassMap, 1269 // so comparing constraint ranges and class maps should be 1270 // sufficient. 1271 return S1->get<ConstraintRange>() == S2->get<ConstraintRange>() && 1272 S1->get<ClassMap>() == S2->get<ClassMap>(); 1273 } 1274 1275 bool canReasonAbout(SVal X) const override; 1276 1277 ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override; 1278 1279 const llvm::APSInt *getSymVal(ProgramStateRef State, 1280 SymbolRef Sym) const override; 1281 1282 ProgramStateRef removeDeadBindings(ProgramStateRef State, 1283 SymbolReaper &SymReaper) override; 1284 1285 void printJson(raw_ostream &Out, ProgramStateRef State, const char *NL = "\n", 1286 unsigned int Space = 0, bool IsDot = false) const override; 1287 1288 //===------------------------------------------------------------------===// 1289 // Implementation for interface from RangedConstraintManager. 1290 //===------------------------------------------------------------------===// 1291 1292 ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym, 1293 const llvm::APSInt &V, 1294 const llvm::APSInt &Adjustment) override; 1295 1296 ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym, 1297 const llvm::APSInt &V, 1298 const llvm::APSInt &Adjustment) override; 1299 1300 ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym, 1301 const llvm::APSInt &V, 1302 const llvm::APSInt &Adjustment) override; 1303 1304 ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym, 1305 const llvm::APSInt &V, 1306 const llvm::APSInt &Adjustment) override; 1307 1308 ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym, 1309 const llvm::APSInt &V, 1310 const llvm::APSInt &Adjustment) override; 1311 1312 ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym, 1313 const llvm::APSInt &V, 1314 const llvm::APSInt &Adjustment) override; 1315 1316 ProgramStateRef assumeSymWithinInclusiveRange( 1317 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 1318 const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; 1319 1320 ProgramStateRef assumeSymOutsideInclusiveRange( 1321 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 1322 const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; 1323 1324 private: 1325 RangeSet::Factory F; 1326 1327 RangeSet getRange(ProgramStateRef State, SymbolRef Sym); 1328 RangeSet getRange(ProgramStateRef State, EquivalenceClass Class); 1329 1330 RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym, 1331 const llvm::APSInt &Int, 1332 const llvm::APSInt &Adjustment); 1333 RangeSet getSymGTRange(ProgramStateRef St, SymbolRef Sym, 1334 const llvm::APSInt &Int, 1335 const llvm::APSInt &Adjustment); 1336 RangeSet getSymLERange(ProgramStateRef St, SymbolRef Sym, 1337 const llvm::APSInt &Int, 1338 const llvm::APSInt &Adjustment); 1339 RangeSet getSymLERange(llvm::function_ref<RangeSet()> RS, 1340 const llvm::APSInt &Int, 1341 const llvm::APSInt &Adjustment); 1342 RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym, 1343 const llvm::APSInt &Int, 1344 const llvm::APSInt &Adjustment); 1345 1346 //===------------------------------------------------------------------===// 1347 // Equality tracking implementation 1348 //===------------------------------------------------------------------===// 1349 1350 ProgramStateRef trackEQ(RangeSet NewConstraint, ProgramStateRef State, 1351 SymbolRef Sym, const llvm::APSInt &Int, 1352 const llvm::APSInt &Adjustment) { 1353 return track<true>(NewConstraint, State, Sym, Int, Adjustment); 1354 } 1355 1356 ProgramStateRef trackNE(RangeSet NewConstraint, ProgramStateRef State, 1357 SymbolRef Sym, const llvm::APSInt &Int, 1358 const llvm::APSInt &Adjustment) { 1359 return track<false>(NewConstraint, State, Sym, Int, Adjustment); 1360 } 1361 1362 template <bool EQ> 1363 ProgramStateRef track(RangeSet NewConstraint, ProgramStateRef State, 1364 SymbolRef Sym, const llvm::APSInt &Int, 1365 const llvm::APSInt &Adjustment) { 1366 if (NewConstraint.isEmpty()) 1367 // This is an infeasible assumption. 1368 return nullptr; 1369 1370 ProgramStateRef NewState = setConstraint(State, Sym, NewConstraint); 1371 if (auto Equality = EqualityInfo::extract(Sym, Int, Adjustment)) { 1372 // If the original assumption is not Sym + Adjustment !=/</> Int, 1373 // we should invert IsEquality flag. 1374 Equality->IsEquality = Equality->IsEquality != EQ; 1375 return track(NewState, *Equality); 1376 } 1377 1378 return NewState; 1379 } 1380 1381 ProgramStateRef track(ProgramStateRef State, EqualityInfo ToTrack) { 1382 if (ToTrack.IsEquality) { 1383 return trackEquality(State, ToTrack.Left, ToTrack.Right); 1384 } 1385 return trackDisequality(State, ToTrack.Left, ToTrack.Right); 1386 } 1387 1388 ProgramStateRef trackDisequality(ProgramStateRef State, SymbolRef LHS, 1389 SymbolRef RHS) { 1390 return EquivalenceClass::markDisequal(getBasicVals(), F, State, LHS, RHS); 1391 } 1392 1393 ProgramStateRef trackEquality(ProgramStateRef State, SymbolRef LHS, 1394 SymbolRef RHS) { 1395 return EquivalenceClass::merge(getBasicVals(), F, State, LHS, RHS); 1396 } 1397 1398 LLVM_NODISCARD inline ProgramStateRef setConstraint(ProgramStateRef State, 1399 EquivalenceClass Class, 1400 RangeSet Constraint) { 1401 ConstraintRangeTy Constraints = State->get<ConstraintRange>(); 1402 ConstraintRangeTy::Factory &CF = State->get_context<ConstraintRange>(); 1403 1404 // Add new constraint. 1405 Constraints = CF.add(Constraints, Class, Constraint); 1406 1407 // There is a chance that we might need to update constraints for the 1408 // classes that are known to be disequal to Class. 1409 // 1410 // In order for this to be even possible, the new constraint should 1411 // be simply a constant because we can't reason about range disequalities. 1412 if (const llvm::APSInt *Point = Constraint.getConcreteValue()) 1413 for (EquivalenceClass DisequalClass : Class.getDisequalClasses(State)) { 1414 RangeSet UpdatedConstraint = 1415 getRange(State, DisequalClass).Delete(getBasicVals(), F, *Point); 1416 Constraints = CF.add(Constraints, DisequalClass, UpdatedConstraint); 1417 } 1418 1419 return State->set<ConstraintRange>(Constraints); 1420 } 1421 1422 LLVM_NODISCARD inline ProgramStateRef 1423 setConstraint(ProgramStateRef State, SymbolRef Sym, RangeSet Constraint) { 1424 return setConstraint(State, EquivalenceClass::find(State, Sym), Constraint); 1425 } 1426 }; 1427 1428 } // end anonymous namespace 1429 1430 std::unique_ptr<ConstraintManager> 1431 ento::CreateRangeConstraintManager(ProgramStateManager &StMgr, 1432 ExprEngine *Eng) { 1433 return std::make_unique<RangeConstraintManager>(Eng, StMgr.getSValBuilder()); 1434 } 1435 1436 ConstraintMap ento::getConstraintMap(ProgramStateRef State) { 1437 ConstraintMap::Factory &F = State->get_context<ConstraintMap>(); 1438 ConstraintMap Result = F.getEmptyMap(); 1439 1440 ConstraintRangeTy Constraints = State->get<ConstraintRange>(); 1441 for (std::pair<EquivalenceClass, RangeSet> ClassConstraint : Constraints) { 1442 EquivalenceClass Class = ClassConstraint.first; 1443 SymbolSet ClassMembers = Class.getClassMembers(State); 1444 assert(!ClassMembers.isEmpty() && 1445 "Class must always have at least one member!"); 1446 1447 SymbolRef Representative = *ClassMembers.begin(); 1448 Result = F.add(Result, Representative, ClassConstraint.second); 1449 } 1450 1451 return Result; 1452 } 1453 1454 //===----------------------------------------------------------------------===// 1455 // EqualityClass implementation details 1456 //===----------------------------------------------------------------------===// 1457 1458 inline EquivalenceClass EquivalenceClass::find(ProgramStateRef State, 1459 SymbolRef Sym) { 1460 // We store far from all Symbol -> Class mappings 1461 if (const EquivalenceClass *NontrivialClass = State->get<ClassMap>(Sym)) 1462 return *NontrivialClass; 1463 1464 // This is a trivial class of Sym. 1465 return Sym; 1466 } 1467 1468 inline ProgramStateRef EquivalenceClass::merge(BasicValueFactory &BV, 1469 RangeSet::Factory &F, 1470 ProgramStateRef State, 1471 SymbolRef First, 1472 SymbolRef Second) { 1473 EquivalenceClass FirstClass = find(State, First); 1474 EquivalenceClass SecondClass = find(State, Second); 1475 1476 return FirstClass.merge(BV, F, State, SecondClass); 1477 } 1478 1479 inline ProgramStateRef EquivalenceClass::merge(BasicValueFactory &BV, 1480 RangeSet::Factory &F, 1481 ProgramStateRef State, 1482 EquivalenceClass Other) { 1483 // It is already the same class. 1484 if (*this == Other) 1485 return State; 1486 1487 // FIXME: As of now, we support only equivalence classes of the same type. 1488 // This limitation is connected to the lack of explicit casts in 1489 // our symbolic expression model. 1490 // 1491 // That means that for `int x` and `char y` we don't distinguish 1492 // between these two very different cases: 1493 // * `x == y` 1494 // * `(char)x == y` 1495 // 1496 // The moment we introduce symbolic casts, this restriction can be 1497 // lifted. 1498 if (getType() != Other.getType()) 1499 return State; 1500 1501 SymbolSet Members = getClassMembers(State); 1502 SymbolSet OtherMembers = Other.getClassMembers(State); 1503 1504 // We estimate the size of the class by the height of tree containing 1505 // its members. Merging is not a trivial operation, so it's easier to 1506 // merge the smaller class into the bigger one. 1507 if (Members.getHeight() >= OtherMembers.getHeight()) { 1508 return mergeImpl(BV, F, State, Members, Other, OtherMembers); 1509 } else { 1510 return Other.mergeImpl(BV, F, State, OtherMembers, *this, Members); 1511 } 1512 } 1513 1514 inline ProgramStateRef 1515 EquivalenceClass::mergeImpl(BasicValueFactory &ValueFactory, 1516 RangeSet::Factory &RangeFactory, 1517 ProgramStateRef State, SymbolSet MyMembers, 1518 EquivalenceClass Other, SymbolSet OtherMembers) { 1519 // Essentially what we try to recreate here is some kind of union-find 1520 // data structure. It does have certain limitations due to persistence 1521 // and the need to remove elements from classes. 1522 // 1523 // In this setting, EquialityClass object is the representative of the class 1524 // or the parent element. ClassMap is a mapping of class members to their 1525 // parent. Unlike the union-find structure, they all point directly to the 1526 // class representative because we don't have an opportunity to actually do 1527 // path compression when dealing with immutability. This means that we 1528 // compress paths every time we do merges. It also means that we lose 1529 // the main amortized complexity benefit from the original data structure. 1530 ConstraintRangeTy Constraints = State->get<ConstraintRange>(); 1531 ConstraintRangeTy::Factory &CRF = State->get_context<ConstraintRange>(); 1532 1533 // 1. If the merged classes have any constraints associated with them, we 1534 // need to transfer them to the class we have left. 1535 // 1536 // Intersection here makes perfect sense because both of these constraints 1537 // must hold for the whole new class. 1538 if (Optional<RangeSet> NewClassConstraint = 1539 intersect(ValueFactory, RangeFactory, getConstraint(State, *this), 1540 getConstraint(State, Other))) { 1541 // NOTE: Essentially, NewClassConstraint should NEVER be infeasible because 1542 // range inferrer shouldn't generate ranges incompatible with 1543 // equivalence classes. However, at the moment, due to imperfections 1544 // in the solver, it is possible and the merge function can also 1545 // return infeasible states aka null states. 1546 if (NewClassConstraint->isEmpty()) 1547 // Infeasible state 1548 return nullptr; 1549 1550 // No need in tracking constraints of a now-dissolved class. 1551 Constraints = CRF.remove(Constraints, Other); 1552 // Assign new constraints for this class. 1553 Constraints = CRF.add(Constraints, *this, *NewClassConstraint); 1554 1555 State = State->set<ConstraintRange>(Constraints); 1556 } 1557 1558 // 2. Get ALL equivalence-related maps 1559 ClassMapTy Classes = State->get<ClassMap>(); 1560 ClassMapTy::Factory &CMF = State->get_context<ClassMap>(); 1561 1562 ClassMembersTy Members = State->get<ClassMembers>(); 1563 ClassMembersTy::Factory &MF = State->get_context<ClassMembers>(); 1564 1565 DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>(); 1566 DisequalityMapTy::Factory &DF = State->get_context<DisequalityMap>(); 1567 1568 ClassSet::Factory &CF = State->get_context<ClassSet>(); 1569 SymbolSet::Factory &F = getMembersFactory(State); 1570 1571 // 2. Merge members of the Other class into the current class. 1572 SymbolSet NewClassMembers = MyMembers; 1573 for (SymbolRef Sym : OtherMembers) { 1574 NewClassMembers = F.add(NewClassMembers, Sym); 1575 // *this is now the class for all these new symbols. 1576 Classes = CMF.add(Classes, Sym, *this); 1577 } 1578 1579 // 3. Adjust member mapping. 1580 // 1581 // No need in tracking members of a now-dissolved class. 1582 Members = MF.remove(Members, Other); 1583 // Now only the current class is mapped to all the symbols. 1584 Members = MF.add(Members, *this, NewClassMembers); 1585 1586 // 4. Update disequality relations 1587 ClassSet DisequalToOther = Other.getDisequalClasses(DisequalityInfo, CF); 1588 if (!DisequalToOther.isEmpty()) { 1589 ClassSet DisequalToThis = getDisequalClasses(DisequalityInfo, CF); 1590 DisequalityInfo = DF.remove(DisequalityInfo, Other); 1591 1592 for (EquivalenceClass DisequalClass : DisequalToOther) { 1593 DisequalToThis = CF.add(DisequalToThis, DisequalClass); 1594 1595 // Disequality is a symmetric relation meaning that if 1596 // DisequalToOther not null then the set for DisequalClass is not 1597 // empty and has at least Other. 1598 ClassSet OriginalSetLinkedToOther = 1599 *DisequalityInfo.lookup(DisequalClass); 1600 1601 // Other will be eliminated and we should replace it with the bigger 1602 // united class. 1603 ClassSet NewSet = CF.remove(OriginalSetLinkedToOther, Other); 1604 NewSet = CF.add(NewSet, *this); 1605 1606 DisequalityInfo = DF.add(DisequalityInfo, DisequalClass, NewSet); 1607 } 1608 1609 DisequalityInfo = DF.add(DisequalityInfo, *this, DisequalToThis); 1610 State = State->set<DisequalityMap>(DisequalityInfo); 1611 } 1612 1613 // 5. Update the state 1614 State = State->set<ClassMap>(Classes); 1615 State = State->set<ClassMembers>(Members); 1616 1617 return State; 1618 } 1619 1620 inline SymbolSet::Factory & 1621 EquivalenceClass::getMembersFactory(ProgramStateRef State) { 1622 return State->get_context<SymbolSet>(); 1623 } 1624 1625 SymbolSet EquivalenceClass::getClassMembers(ProgramStateRef State) { 1626 if (const SymbolSet *Members = State->get<ClassMembers>(*this)) 1627 return *Members; 1628 1629 // This class is trivial, so we need to construct a set 1630 // with just that one symbol from the class. 1631 SymbolSet::Factory &F = getMembersFactory(State); 1632 return F.add(F.getEmptySet(), getRepresentativeSymbol()); 1633 } 1634 1635 bool EquivalenceClass::isTrivial(ProgramStateRef State) { 1636 return State->get<ClassMembers>(*this) == nullptr; 1637 } 1638 1639 bool EquivalenceClass::isTriviallyDead(ProgramStateRef State, 1640 SymbolReaper &Reaper) { 1641 return isTrivial(State) && Reaper.isDead(getRepresentativeSymbol()); 1642 } 1643 1644 inline ProgramStateRef EquivalenceClass::markDisequal(BasicValueFactory &VF, 1645 RangeSet::Factory &RF, 1646 ProgramStateRef State, 1647 SymbolRef First, 1648 SymbolRef Second) { 1649 return markDisequal(VF, RF, State, find(State, First), find(State, Second)); 1650 } 1651 1652 inline ProgramStateRef EquivalenceClass::markDisequal(BasicValueFactory &VF, 1653 RangeSet::Factory &RF, 1654 ProgramStateRef State, 1655 EquivalenceClass First, 1656 EquivalenceClass Second) { 1657 return First.markDisequal(VF, RF, State, Second); 1658 } 1659 1660 inline ProgramStateRef 1661 EquivalenceClass::markDisequal(BasicValueFactory &VF, RangeSet::Factory &RF, 1662 ProgramStateRef State, 1663 EquivalenceClass Other) const { 1664 // If we know that two classes are equal, we can only produce an infeasible 1665 // state. 1666 if (*this == Other) { 1667 return nullptr; 1668 } 1669 1670 DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>(); 1671 ConstraintRangeTy Constraints = State->get<ConstraintRange>(); 1672 1673 // Disequality is a symmetric relation, so if we mark A as disequal to B, 1674 // we should also mark B as disequalt to A. 1675 addToDisequalityInfo(DisequalityInfo, Constraints, VF, RF, State, *this, 1676 Other); 1677 addToDisequalityInfo(DisequalityInfo, Constraints, VF, RF, State, Other, 1678 *this); 1679 1680 State = State->set<DisequalityMap>(DisequalityInfo); 1681 State = State->set<ConstraintRange>(Constraints); 1682 1683 return State; 1684 } 1685 1686 inline void EquivalenceClass::addToDisequalityInfo( 1687 DisequalityMapTy &Info, ConstraintRangeTy &Constraints, 1688 BasicValueFactory &VF, RangeSet::Factory &RF, ProgramStateRef State, 1689 EquivalenceClass First, EquivalenceClass Second) { 1690 1691 // 1. Get all of the required factories. 1692 DisequalityMapTy::Factory &F = State->get_context<DisequalityMap>(); 1693 ClassSet::Factory &CF = State->get_context<ClassSet>(); 1694 ConstraintRangeTy::Factory &CRF = State->get_context<ConstraintRange>(); 1695 1696 // 2. Add Second to the set of classes disequal to First. 1697 const ClassSet *CurrentSet = Info.lookup(First); 1698 ClassSet NewSet = CurrentSet ? *CurrentSet : CF.getEmptySet(); 1699 NewSet = CF.add(NewSet, Second); 1700 1701 Info = F.add(Info, First, NewSet); 1702 1703 // 3. If Second is known to be a constant, we can delete this point 1704 // from the constraint asociated with First. 1705 // 1706 // So, if Second == 10, it means that First != 10. 1707 // At the same time, the same logic does not apply to ranges. 1708 if (const RangeSet *SecondConstraint = Constraints.lookup(Second)) 1709 if (const llvm::APSInt *Point = SecondConstraint->getConcreteValue()) { 1710 1711 RangeSet FirstConstraint = SymbolicRangeInferrer::inferRange( 1712 VF, RF, State, First.getRepresentativeSymbol()); 1713 1714 FirstConstraint = FirstConstraint.Delete(VF, RF, *Point); 1715 Constraints = CRF.add(Constraints, First, FirstConstraint); 1716 } 1717 } 1718 1719 inline Optional<bool> EquivalenceClass::areEqual(ProgramStateRef State, 1720 SymbolRef FirstSym, 1721 SymbolRef SecondSym) { 1722 EquivalenceClass First = find(State, FirstSym); 1723 EquivalenceClass Second = find(State, SecondSym); 1724 1725 // The same equivalence class => symbols are equal. 1726 if (First == Second) 1727 return true; 1728 1729 // Let's check if we know anything about these two classes being not equal to 1730 // each other. 1731 ClassSet DisequalToFirst = First.getDisequalClasses(State); 1732 if (DisequalToFirst.contains(Second)) 1733 return false; 1734 1735 // It is not clear. 1736 return llvm::None; 1737 } 1738 1739 inline ClassSet EquivalenceClass::getDisequalClasses(ProgramStateRef State, 1740 SymbolRef Sym) { 1741 return find(State, Sym).getDisequalClasses(State); 1742 } 1743 1744 inline ClassSet 1745 EquivalenceClass::getDisequalClasses(ProgramStateRef State) const { 1746 return getDisequalClasses(State->get<DisequalityMap>(), 1747 State->get_context<ClassSet>()); 1748 } 1749 1750 inline ClassSet 1751 EquivalenceClass::getDisequalClasses(DisequalityMapTy Map, 1752 ClassSet::Factory &Factory) const { 1753 if (const ClassSet *DisequalClasses = Map.lookup(*this)) 1754 return *DisequalClasses; 1755 1756 return Factory.getEmptySet(); 1757 } 1758 1759 bool EquivalenceClass::isClassDataConsistent(ProgramStateRef State) { 1760 ClassMembersTy Members = State->get<ClassMembers>(); 1761 1762 for (std::pair<EquivalenceClass, SymbolSet> ClassMembersPair : Members) { 1763 for (SymbolRef Member : ClassMembersPair.second) { 1764 // Every member of the class should have a mapping back to the class. 1765 if (find(State, Member) == ClassMembersPair.first) { 1766 continue; 1767 } 1768 1769 return false; 1770 } 1771 } 1772 1773 DisequalityMapTy Disequalities = State->get<DisequalityMap>(); 1774 for (std::pair<EquivalenceClass, ClassSet> DisequalityInfo : Disequalities) { 1775 EquivalenceClass Class = DisequalityInfo.first; 1776 ClassSet DisequalClasses = DisequalityInfo.second; 1777 1778 // There is no use in keeping empty sets in the map. 1779 if (DisequalClasses.isEmpty()) 1780 return false; 1781 1782 // Disequality is symmetrical, i.e. for every Class A and B that A != B, 1783 // B != A should also be true. 1784 for (EquivalenceClass DisequalClass : DisequalClasses) { 1785 const ClassSet *DisequalToDisequalClasses = 1786 Disequalities.lookup(DisequalClass); 1787 1788 // It should be a set of at least one element: Class 1789 if (!DisequalToDisequalClasses || 1790 !DisequalToDisequalClasses->contains(Class)) 1791 return false; 1792 } 1793 } 1794 1795 return true; 1796 } 1797 1798 //===----------------------------------------------------------------------===// 1799 // RangeConstraintManager implementation 1800 //===----------------------------------------------------------------------===// 1801 1802 bool RangeConstraintManager::canReasonAbout(SVal X) const { 1803 Optional<nonloc::SymbolVal> SymVal = X.getAs<nonloc::SymbolVal>(); 1804 if (SymVal && SymVal->isExpression()) { 1805 const SymExpr *SE = SymVal->getSymbol(); 1806 1807 if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) { 1808 switch (SIE->getOpcode()) { 1809 // We don't reason yet about bitwise-constraints on symbolic values. 1810 case BO_And: 1811 case BO_Or: 1812 case BO_Xor: 1813 return false; 1814 // We don't reason yet about these arithmetic constraints on 1815 // symbolic values. 1816 case BO_Mul: 1817 case BO_Div: 1818 case BO_Rem: 1819 case BO_Shl: 1820 case BO_Shr: 1821 return false; 1822 // All other cases. 1823 default: 1824 return true; 1825 } 1826 } 1827 1828 if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) { 1829 // FIXME: Handle <=> here. 1830 if (BinaryOperator::isEqualityOp(SSE->getOpcode()) || 1831 BinaryOperator::isRelationalOp(SSE->getOpcode())) { 1832 // We handle Loc <> Loc comparisons, but not (yet) NonLoc <> NonLoc. 1833 // We've recently started producing Loc <> NonLoc comparisons (that 1834 // result from casts of one of the operands between eg. intptr_t and 1835 // void *), but we can't reason about them yet. 1836 if (Loc::isLocType(SSE->getLHS()->getType())) { 1837 return Loc::isLocType(SSE->getRHS()->getType()); 1838 } 1839 } 1840 } 1841 1842 return false; 1843 } 1844 1845 return true; 1846 } 1847 1848 ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State, 1849 SymbolRef Sym) { 1850 const RangeSet *Ranges = getConstraint(State, Sym); 1851 1852 // If we don't have any information about this symbol, it's underconstrained. 1853 if (!Ranges) 1854 return ConditionTruthVal(); 1855 1856 // If we have a concrete value, see if it's zero. 1857 if (const llvm::APSInt *Value = Ranges->getConcreteValue()) 1858 return *Value == 0; 1859 1860 BasicValueFactory &BV = getBasicVals(); 1861 APSIntType IntType = BV.getAPSIntType(Sym->getType()); 1862 llvm::APSInt Zero = IntType.getZeroValue(); 1863 1864 // Check if zero is in the set of possible values. 1865 if (Ranges->Intersect(BV, F, Zero, Zero).isEmpty()) 1866 return false; 1867 1868 // Zero is a possible value, but it is not the /only/ possible value. 1869 return ConditionTruthVal(); 1870 } 1871 1872 const llvm::APSInt *RangeConstraintManager::getSymVal(ProgramStateRef St, 1873 SymbolRef Sym) const { 1874 const RangeSet *T = getConstraint(St, Sym); 1875 return T ? T->getConcreteValue() : nullptr; 1876 } 1877 1878 //===----------------------------------------------------------------------===// 1879 // Remove dead symbols from existing constraints 1880 //===----------------------------------------------------------------------===// 1881 1882 /// Scan all symbols referenced by the constraints. If the symbol is not alive 1883 /// as marked in LSymbols, mark it as dead in DSymbols. 1884 ProgramStateRef 1885 RangeConstraintManager::removeDeadBindings(ProgramStateRef State, 1886 SymbolReaper &SymReaper) { 1887 ClassMembersTy ClassMembersMap = State->get<ClassMembers>(); 1888 ClassMembersTy NewClassMembersMap = ClassMembersMap; 1889 ClassMembersTy::Factory &EMFactory = State->get_context<ClassMembers>(); 1890 SymbolSet::Factory &SetFactory = State->get_context<SymbolSet>(); 1891 1892 ConstraintRangeTy Constraints = State->get<ConstraintRange>(); 1893 ConstraintRangeTy NewConstraints = Constraints; 1894 ConstraintRangeTy::Factory &ConstraintFactory = 1895 State->get_context<ConstraintRange>(); 1896 1897 ClassMapTy Map = State->get<ClassMap>(); 1898 ClassMapTy NewMap = Map; 1899 ClassMapTy::Factory &ClassFactory = State->get_context<ClassMap>(); 1900 1901 DisequalityMapTy Disequalities = State->get<DisequalityMap>(); 1902 DisequalityMapTy::Factory &DisequalityFactory = 1903 State->get_context<DisequalityMap>(); 1904 ClassSet::Factory &ClassSetFactory = State->get_context<ClassSet>(); 1905 1906 bool ClassMapChanged = false; 1907 bool MembersMapChanged = false; 1908 bool ConstraintMapChanged = false; 1909 bool DisequalitiesChanged = false; 1910 1911 auto removeDeadClass = [&](EquivalenceClass Class) { 1912 // Remove associated constraint ranges. 1913 Constraints = ConstraintFactory.remove(Constraints, Class); 1914 ConstraintMapChanged = true; 1915 1916 // Update disequality information to not hold any information on the 1917 // removed class. 1918 ClassSet DisequalClasses = 1919 Class.getDisequalClasses(Disequalities, ClassSetFactory); 1920 if (!DisequalClasses.isEmpty()) { 1921 for (EquivalenceClass DisequalClass : DisequalClasses) { 1922 ClassSet DisequalToDisequalSet = 1923 DisequalClass.getDisequalClasses(Disequalities, ClassSetFactory); 1924 // DisequalToDisequalSet is guaranteed to be non-empty for consistent 1925 // disequality info. 1926 assert(!DisequalToDisequalSet.isEmpty()); 1927 ClassSet NewSet = ClassSetFactory.remove(DisequalToDisequalSet, Class); 1928 1929 // No need in keeping an empty set. 1930 if (NewSet.isEmpty()) { 1931 Disequalities = 1932 DisequalityFactory.remove(Disequalities, DisequalClass); 1933 } else { 1934 Disequalities = 1935 DisequalityFactory.add(Disequalities, DisequalClass, NewSet); 1936 } 1937 } 1938 // Remove the data for the class 1939 Disequalities = DisequalityFactory.remove(Disequalities, Class); 1940 DisequalitiesChanged = true; 1941 } 1942 }; 1943 1944 // 1. Let's see if dead symbols are trivial and have associated constraints. 1945 for (std::pair<EquivalenceClass, RangeSet> ClassConstraintPair : 1946 Constraints) { 1947 EquivalenceClass Class = ClassConstraintPair.first; 1948 if (Class.isTriviallyDead(State, SymReaper)) { 1949 // If this class is trivial, we can remove its constraints right away. 1950 removeDeadClass(Class); 1951 } 1952 } 1953 1954 // 2. We don't need to track classes for dead symbols. 1955 for (std::pair<SymbolRef, EquivalenceClass> SymbolClassPair : Map) { 1956 SymbolRef Sym = SymbolClassPair.first; 1957 1958 if (SymReaper.isDead(Sym)) { 1959 ClassMapChanged = true; 1960 NewMap = ClassFactory.remove(NewMap, Sym); 1961 } 1962 } 1963 1964 // 3. Remove dead members from classes and remove dead non-trivial classes 1965 // and their constraints. 1966 for (std::pair<EquivalenceClass, SymbolSet> ClassMembersPair : 1967 ClassMembersMap) { 1968 EquivalenceClass Class = ClassMembersPair.first; 1969 SymbolSet LiveMembers = ClassMembersPair.second; 1970 bool MembersChanged = false; 1971 1972 for (SymbolRef Member : ClassMembersPair.second) { 1973 if (SymReaper.isDead(Member)) { 1974 MembersChanged = true; 1975 LiveMembers = SetFactory.remove(LiveMembers, Member); 1976 } 1977 } 1978 1979 // Check if the class changed. 1980 if (!MembersChanged) 1981 continue; 1982 1983 MembersMapChanged = true; 1984 1985 if (LiveMembers.isEmpty()) { 1986 // The class is dead now, we need to wipe it out of the members map... 1987 NewClassMembersMap = EMFactory.remove(NewClassMembersMap, Class); 1988 1989 // ...and remove all of its constraints. 1990 removeDeadClass(Class); 1991 } else { 1992 // We need to change the members associated with the class. 1993 NewClassMembersMap = 1994 EMFactory.add(NewClassMembersMap, Class, LiveMembers); 1995 } 1996 } 1997 1998 // 4. Update the state with new maps. 1999 // 2000 // Here we try to be humble and update a map only if it really changed. 2001 if (ClassMapChanged) 2002 State = State->set<ClassMap>(NewMap); 2003 2004 if (MembersMapChanged) 2005 State = State->set<ClassMembers>(NewClassMembersMap); 2006 2007 if (ConstraintMapChanged) 2008 State = State->set<ConstraintRange>(Constraints); 2009 2010 if (DisequalitiesChanged) 2011 State = State->set<DisequalityMap>(Disequalities); 2012 2013 assert(EquivalenceClass::isClassDataConsistent(State)); 2014 2015 return State; 2016 } 2017 2018 RangeSet RangeConstraintManager::getRange(ProgramStateRef State, 2019 SymbolRef Sym) { 2020 return SymbolicRangeInferrer::inferRange(getBasicVals(), F, State, Sym); 2021 } 2022 2023 RangeSet RangeConstraintManager::getRange(ProgramStateRef State, 2024 EquivalenceClass Class) { 2025 return SymbolicRangeInferrer::inferRange(getBasicVals(), F, State, Class); 2026 } 2027 2028 //===------------------------------------------------------------------------=== 2029 // assumeSymX methods: protected interface for RangeConstraintManager. 2030 //===------------------------------------------------------------------------===/ 2031 2032 // The syntax for ranges below is mathematical, using [x, y] for closed ranges 2033 // and (x, y) for open ranges. These ranges are modular, corresponding with 2034 // a common treatment of C integer overflow. This means that these methods 2035 // do not have to worry about overflow; RangeSet::Intersect can handle such a 2036 // "wraparound" range. 2037 // As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1, 2038 // UINT_MAX, 0, 1, and 2. 2039 2040 ProgramStateRef 2041 RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym, 2042 const llvm::APSInt &Int, 2043 const llvm::APSInt &Adjustment) { 2044 // Before we do any real work, see if the value can even show up. 2045 APSIntType AdjustmentType(Adjustment); 2046 if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within) 2047 return St; 2048 2049 llvm::APSInt Point = AdjustmentType.convert(Int) - Adjustment; 2050 2051 RangeSet New = getRange(St, Sym).Delete(getBasicVals(), F, Point); 2052 2053 return trackNE(New, St, Sym, Int, Adjustment); 2054 } 2055 2056 ProgramStateRef 2057 RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym, 2058 const llvm::APSInt &Int, 2059 const llvm::APSInt &Adjustment) { 2060 // Before we do any real work, see if the value can even show up. 2061 APSIntType AdjustmentType(Adjustment); 2062 if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within) 2063 return nullptr; 2064 2065 // [Int-Adjustment, Int-Adjustment] 2066 llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment; 2067 RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt); 2068 2069 return trackEQ(New, St, Sym, Int, Adjustment); 2070 } 2071 2072 RangeSet RangeConstraintManager::getSymLTRange(ProgramStateRef St, 2073 SymbolRef Sym, 2074 const llvm::APSInt &Int, 2075 const llvm::APSInt &Adjustment) { 2076 // Before we do any real work, see if the value can even show up. 2077 APSIntType AdjustmentType(Adjustment); 2078 switch (AdjustmentType.testInRange(Int, true)) { 2079 case APSIntType::RTR_Below: 2080 return F.getEmptySet(); 2081 case APSIntType::RTR_Within: 2082 break; 2083 case APSIntType::RTR_Above: 2084 return getRange(St, Sym); 2085 } 2086 2087 // Special case for Int == Min. This is always false. 2088 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); 2089 llvm::APSInt Min = AdjustmentType.getMinValue(); 2090 if (ComparisonVal == Min) 2091 return F.getEmptySet(); 2092 2093 llvm::APSInt Lower = Min - Adjustment; 2094 llvm::APSInt Upper = ComparisonVal - Adjustment; 2095 --Upper; 2096 2097 return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); 2098 } 2099 2100 ProgramStateRef 2101 RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym, 2102 const llvm::APSInt &Int, 2103 const llvm::APSInt &Adjustment) { 2104 RangeSet New = getSymLTRange(St, Sym, Int, Adjustment); 2105 return trackNE(New, St, Sym, Int, Adjustment); 2106 } 2107 2108 RangeSet RangeConstraintManager::getSymGTRange(ProgramStateRef St, 2109 SymbolRef Sym, 2110 const llvm::APSInt &Int, 2111 const llvm::APSInt &Adjustment) { 2112 // Before we do any real work, see if the value can even show up. 2113 APSIntType AdjustmentType(Adjustment); 2114 switch (AdjustmentType.testInRange(Int, true)) { 2115 case APSIntType::RTR_Below: 2116 return getRange(St, Sym); 2117 case APSIntType::RTR_Within: 2118 break; 2119 case APSIntType::RTR_Above: 2120 return F.getEmptySet(); 2121 } 2122 2123 // Special case for Int == Max. This is always false. 2124 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); 2125 llvm::APSInt Max = AdjustmentType.getMaxValue(); 2126 if (ComparisonVal == Max) 2127 return F.getEmptySet(); 2128 2129 llvm::APSInt Lower = ComparisonVal - Adjustment; 2130 llvm::APSInt Upper = Max - Adjustment; 2131 ++Lower; 2132 2133 return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); 2134 } 2135 2136 ProgramStateRef 2137 RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym, 2138 const llvm::APSInt &Int, 2139 const llvm::APSInt &Adjustment) { 2140 RangeSet New = getSymGTRange(St, Sym, Int, Adjustment); 2141 return trackNE(New, St, Sym, Int, Adjustment); 2142 } 2143 2144 RangeSet RangeConstraintManager::getSymGERange(ProgramStateRef St, 2145 SymbolRef Sym, 2146 const llvm::APSInt &Int, 2147 const llvm::APSInt &Adjustment) { 2148 // Before we do any real work, see if the value can even show up. 2149 APSIntType AdjustmentType(Adjustment); 2150 switch (AdjustmentType.testInRange(Int, true)) { 2151 case APSIntType::RTR_Below: 2152 return getRange(St, Sym); 2153 case APSIntType::RTR_Within: 2154 break; 2155 case APSIntType::RTR_Above: 2156 return F.getEmptySet(); 2157 } 2158 2159 // Special case for Int == Min. This is always feasible. 2160 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); 2161 llvm::APSInt Min = AdjustmentType.getMinValue(); 2162 if (ComparisonVal == Min) 2163 return getRange(St, Sym); 2164 2165 llvm::APSInt Max = AdjustmentType.getMaxValue(); 2166 llvm::APSInt Lower = ComparisonVal - Adjustment; 2167 llvm::APSInt Upper = Max - Adjustment; 2168 2169 return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); 2170 } 2171 2172 ProgramStateRef 2173 RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym, 2174 const llvm::APSInt &Int, 2175 const llvm::APSInt &Adjustment) { 2176 RangeSet New = getSymGERange(St, Sym, Int, Adjustment); 2177 return New.isEmpty() ? nullptr : setConstraint(St, Sym, New); 2178 } 2179 2180 RangeSet 2181 RangeConstraintManager::getSymLERange(llvm::function_ref<RangeSet()> RS, 2182 const llvm::APSInt &Int, 2183 const llvm::APSInt &Adjustment) { 2184 // Before we do any real work, see if the value can even show up. 2185 APSIntType AdjustmentType(Adjustment); 2186 switch (AdjustmentType.testInRange(Int, true)) { 2187 case APSIntType::RTR_Below: 2188 return F.getEmptySet(); 2189 case APSIntType::RTR_Within: 2190 break; 2191 case APSIntType::RTR_Above: 2192 return RS(); 2193 } 2194 2195 // Special case for Int == Max. This is always feasible. 2196 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); 2197 llvm::APSInt Max = AdjustmentType.getMaxValue(); 2198 if (ComparisonVal == Max) 2199 return RS(); 2200 2201 llvm::APSInt Min = AdjustmentType.getMinValue(); 2202 llvm::APSInt Lower = Min - Adjustment; 2203 llvm::APSInt Upper = ComparisonVal - Adjustment; 2204 2205 return RS().Intersect(getBasicVals(), F, Lower, Upper); 2206 } 2207 2208 RangeSet RangeConstraintManager::getSymLERange(ProgramStateRef St, 2209 SymbolRef Sym, 2210 const llvm::APSInt &Int, 2211 const llvm::APSInt &Adjustment) { 2212 return getSymLERange([&] { return getRange(St, Sym); }, Int, Adjustment); 2213 } 2214 2215 ProgramStateRef 2216 RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym, 2217 const llvm::APSInt &Int, 2218 const llvm::APSInt &Adjustment) { 2219 RangeSet New = getSymLERange(St, Sym, Int, Adjustment); 2220 return New.isEmpty() ? nullptr : setConstraint(St, Sym, New); 2221 } 2222 2223 ProgramStateRef RangeConstraintManager::assumeSymWithinInclusiveRange( 2224 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 2225 const llvm::APSInt &To, const llvm::APSInt &Adjustment) { 2226 RangeSet New = getSymGERange(State, Sym, From, Adjustment); 2227 if (New.isEmpty()) 2228 return nullptr; 2229 RangeSet Out = getSymLERange([&] { return New; }, To, Adjustment); 2230 return Out.isEmpty() ? nullptr : setConstraint(State, Sym, Out); 2231 } 2232 2233 ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange( 2234 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 2235 const llvm::APSInt &To, const llvm::APSInt &Adjustment) { 2236 RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment); 2237 RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment); 2238 RangeSet New(RangeLT.addRange(F, RangeGT)); 2239 return New.isEmpty() ? nullptr : setConstraint(State, Sym, New); 2240 } 2241 2242 //===----------------------------------------------------------------------===// 2243 // Pretty-printing. 2244 //===----------------------------------------------------------------------===// 2245 2246 void RangeConstraintManager::printJson(raw_ostream &Out, ProgramStateRef State, 2247 const char *NL, unsigned int Space, 2248 bool IsDot) const { 2249 ConstraintRangeTy Constraints = State->get<ConstraintRange>(); 2250 2251 Indent(Out, Space, IsDot) << "\"constraints\": "; 2252 if (Constraints.isEmpty()) { 2253 Out << "null," << NL; 2254 return; 2255 } 2256 2257 ++Space; 2258 Out << '[' << NL; 2259 bool First = true; 2260 for (std::pair<EquivalenceClass, RangeSet> P : Constraints) { 2261 SymbolSet ClassMembers = P.first.getClassMembers(State); 2262 2263 // We can print the same constraint for every class member. 2264 for (SymbolRef ClassMember : ClassMembers) { 2265 if (First) { 2266 First = false; 2267 } else { 2268 Out << ','; 2269 Out << NL; 2270 } 2271 Indent(Out, Space, IsDot) 2272 << "{ \"symbol\": \"" << ClassMember << "\", \"range\": \""; 2273 P.second.print(Out); 2274 Out << "\" }"; 2275 } 2276 } 2277 Out << NL; 2278 2279 --Space; 2280 Indent(Out, Space, IsDot) << "]," << NL; 2281 } 2282