clang  12.0.0git
RangeConstraintManager.cpp
Go to the documentation of this file.
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 
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.
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,
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 
92  BinaryOperatorKind QueriedOP) const {
93  return CmpOpTable[getIndexFromOp(CurrentOP)][getIndexFromOp(QueriedOP)];
94  }
95 
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 
144  assert(!isEmpty());
145  return begin()->From();
146 }
147 
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) {
177  switch (UpperTest) {
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;
189  // The range starts below what's possible but ends within it. Pin.
190  Lower = Type.getMinValue();
191  Type.apply(Upper);
192  break;
194  // The range spans all possible values for the symbol. Pin.
195  Lower = Type.getMinValue();
196  Upper = Type.getMaxValue();
197  break;
198  }
199  break;
201  switch (UpperTest) {
203  // The range wraps around, but all lower values are not possible.
204  Type.apply(Lower);
205  Upper = Type.getMaxValue();
206  break;
208  // The range may or may not wrap around, but both limits are valid.
209  Type.apply(Lower);
210  Type.apply(Upper);
211  break;
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;
220  switch (UpperTest) {
222  // The range wraps but is outside the symbol's set of possible values.
223  return false;
225  // The range starts above what's possible but ends within it (wrap).
226  Lower = Type.getMinValue();
227  Type.apply(Upper);
228  break;
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.
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.
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].
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 
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 
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,
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
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).
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 =
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 
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;
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 
1293  const llvm::APSInt &V,
1294  const llvm::APSInt &Adjustment) override;
1295 
1297  const llvm::APSInt &V,
1298  const llvm::APSInt &Adjustment) override;
1299 
1301  const llvm::APSInt &V,
1302  const llvm::APSInt &Adjustment) override;
1303 
1305  const llvm::APSInt &V,
1306  const llvm::APSInt &Adjustment) override;
1307 
1309  const llvm::APSInt &V,
1310  const llvm::APSInt &Adjustment) override;
1311 
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:
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>
1432  ExprEngine *Eng) {
1433  return std::make_unique<RangeConstraintManager>(Eng, StMgr.getSValBuilder());
1434 }
1435 
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,
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,
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 
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,
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,
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,
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.
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 
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 
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();
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 
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);
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 
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);
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 
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();
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 
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 }
Indicates that the tracked object is a CF object.
A (possibly-)qualified type.
Definition: Type.h:661
Value is less than the minimum representable value.
Definition: APSIntType.h:77
bool isUnsignedIntegerOrEnumerationType() const
Determines whether this is an integer type that is unsigned or an enumeration types whose underlying ...
Definition: Type.cpp:2069
__DEVICE__ int max(int __a, int __b)
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
static void add(Kind k)
Definition: DeclBase.cpp:193
StringRef P
RangeSet Delete(BasicValueFactory &BV, Factory &F, const llvm::APSInt &Point) const
ConstraintMap getConstraintMap(ProgramStateRef State)
The base class of the type hierarchy.
Definition: Type.h:1478
std::unique_ptr< ConstraintManager > CreateRangeConstraintManager(ProgramStateManager &statemgr, ExprEngine *exprengine)
A Range represents the closed range [from, to].
RangeSet contains a set of ranges.
bool isEqualityOp() const
Definition: Expr.h:3824
llvm::ImmutableMap< SymbolRef, RangeSet > ConstraintMap
Symbolic value.
Definition: SymExpr.h:29
const SymExpr * SymbolRef
Definition: SymExpr.h:110
static Opcode reverseComparisonOp(Opcode Opc)
Definition: Expr.h:3845
LineState State
BinarySymExprImpl< const SymExpr *, const SymExpr *, SymExpr::Kind::SymSymExprKind > SymSymExpr
Represents a symbolic expression like 'x' + 'y'.
bool Zero(InterpState &S, CodePtr OpPC)
Definition: Interp.h:812
bool isReferenceType() const
Definition: Type.h:6652
bool isIntegralOrEnumerationType() const
Determine whether this type is an integral or enumeration type.
Definition: Type.h:7022
RangeSet Negate(BasicValueFactory &BV, Factory &F) const
static bool isLocType(QualType T)
Definition: SVals.h:323
BinaryOperatorKind
PrimRangeSet::Factory Factory
bool operator==(const CallGraphNode::CallRecord &LHS, const CallGraphNode::CallRecord &RHS)
Definition: CallGraph.h:207
static BinaryOperatorKind getOpFromIndex(size_t Index)
Value is representable using this type.
Definition: APSIntType.h:78
bool isRelationalOp() const
Definition: Expr.h:3821
static Opcode negateComparisonOp(Opcode Opc)
Definition: Expr.h:3832
void print(raw_ostream &os) const
BinarySymExprImpl< const llvm::APSInt &, const SymExpr *, SymExpr::Kind::IntSymExprKind > IntSymExpr
Represents a symbolic expression like 3 - 'x'.
SourceLocation End
#define V(N, I)
Definition: ASTContext.h:2983
__UINTPTR_TYPE__ uintptr_t
An unsigned integer type with the property that any valid pointer to void can be converted to this ty...
Definition: opencl-c-base.h:62
TriStateKind getCmpOpStateForUnknownX2(BinaryOperatorKind CurrentOP) const
bool isComparisonOp() const
Definition: Expr.h:3827
constexpr size_t getCmpOpCount() const
llvm::APSInt APSInt
#define REGISTER_MAP_WITH_PROGRAMSTATE(Name, Key, Value)
Declares an immutable map of type NameTy, suitable for placement into the ProgramState.
#define REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(Name, Elem)
Declares an immutable set type Name and registers the factory for such sets in the program state,...
bool isSignedIntegerOrEnumerationType() const
Determines whether this is an integer type that is signed or an enumeration types whose underlying ty...
Definition: Type.cpp:2022
Value is greater than the maximum representable value.
Definition: APSIntType.h:79
bool operator<(DeclarationName LHS, DeclarationName RHS)
Ordering on two declaration names.
RangeTestResultKind
Used to classify whether a value is representable using this type.
Definition: APSIntType.h:76
Dataflow Directional Tag Classes.
TriStateKind getCmpOpState(BinaryOperatorKind CurrentOP, BinaryOperatorKind QueriedOP) const
const llvm::APSInt & getMaxValue() const
Get a maximal value covered by the ranges in the set.
BinarySymExprImpl< const SymExpr *, const llvm::APSInt &, SymExpr::Kind::SymIntExprKind > SymIntExpr
Represents a symbolic expression like 'x' + 3.
const llvm::APSInt & getMinValue(const llvm::APSInt &v)
RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower, llvm::APSInt Upper) const
PrimRangeSet::iterator iterator
X
Add a minimal nested name specifier fixit hint to allow lookup of a tag name from an outer enclosing ...
Definition: SemaDecl.cpp:15282
static bool isTrivial(ASTContext &Ctx, const Expr *E)
Checks if the expression is constant or does not have non-trivial function calls.
bool operator!=(CanQual< T > x, CanQual< U > y)
__DEVICE__ int min(int __a, int __b)
const llvm::APSInt & getMaxValue(const llvm::APSInt &v)
raw_ostream & Indent(raw_ostream &Out, const unsigned int Space, bool IsDot)
Definition: JsonSupport.h:20
const llvm::APSInt & getMinValue() const
Get a minimal value covered by the ranges in the set.
bool EQ(InterpState &S, CodePtr OpPC)
Definition: Interp.h:216