20#include "llvm/ADT/FoldingSet.h"
21#include "llvm/ADT/ImmutableSet.h"
22#include "llvm/ADT/STLExtras.h"
23#include "llvm/ADT/SmallSet.h"
24#include "llvm/ADT/StringExtras.h"
25#include "llvm/Support/Compiler.h"
26#include "llvm/Support/raw_ostream.h"
37 static_assert(BO_LT < BO_GT && BO_GT < BO_LE && BO_LE < BO_GE &&
38 BO_GE < BO_EQ && BO_EQ < BO_NE,
39 "This class relies on operators order. Rework it otherwise.");
76 static constexpr size_t CmpOpCount = BO_NE - BO_LT + 1;
77 const TriStateKind CmpOpTable[CmpOpCount][CmpOpCount + 1] = {
88 return static_cast<size_t>(OP - BO_LT);
100 return CmpOpTable[getIndexFromOp(CurrentOP)][getIndexFromOp(QueriedOP)];
104 return CmpOpTable[getIndexFromOp(CurrentOP)][CmpOpCount];
112RangeSet::ContainerType RangeSet::Factory::EmptySet{};
118 std::back_inserter(
Result));
119 return makePersistent(std::move(
Result));
124 Result.reserve(Original.size() + 1);
128 Result.push_back(Element);
131 return makePersistent(std::move(
Result));
135 return add(Original,
Range(Point));
139 ContainerType
Result = unite(*LHS.Impl, *RHS.Impl);
140 return makePersistent(std::move(
Result));
147 return makePersistent(std::move(
Result));
151 return unite(Original,
Range(ValueFactory.getValue(Point)));
156 return unite(Original,
157 Range(ValueFactory.getValue(From), ValueFactory.getValue(To)));
162 std::swap(
First, Second);
163 std::swap(FirstEnd, SecondEnd);
167 const ContainerType &RHS) {
174 using iterator = ContainerType::const_iterator;
176 iterator
First = LHS.begin();
177 iterator FirstEnd = LHS.end();
178 iterator Second = RHS.begin();
179 iterator SecondEnd = RHS.end();
187 if (
Min ==
First->From() &&
Min == Second->From()) {
188 if (
First->To() > Second->To()) {
195 if (++Second == SecondEnd)
209 if (++
First == FirstEnd)
224 const auto AppendTheRest = [&
Result](iterator I, iterator
E) {
233 if (
First->From() > Second->From())
241 const llvm::APSInt &UnionStart =
First->From();
248 while (
First->To() >= Second->To()) {
250 if (++Second == SecondEnd) {
260 return AppendTheRest(++
First, FirstEnd);
269 if (
First->To() < Second->From() - One)
277 if (++
First == FirstEnd) {
283 Result.emplace_back(UnionStart, Second->To());
287 return AppendTheRest(++Second, SecondEnd);
308 if (++
First == FirstEnd)
312 return AppendTheRest(Second, SecondEnd);
315 llvm_unreachable(
"Normally, we should not reach here");
321 return makePersistent(std::move(
Result));
324RangeSet RangeSet::Factory::makePersistent(ContainerType &&From) {
325 llvm::FoldingSetNodeID ID;
329 ContainerType *
Result =
Cache.FindNodeOrInsertPos(ID, InsertPos);
335 Result = construct(std::move(From));
342RangeSet::ContainerType *RangeSet::Factory::construct(ContainerType &&From) {
343 void *Buffer = Arena.Allocate();
344 return new (Buffer) ContainerType(std::move(From));
349 return begin()->From();
354 return std::prev(
end())->To();
359 return begin()->From().isUnsigned();
364 return begin()->From().getBitWidth();
372bool RangeSet::containsImpl(llvm::APSInt &Point)
const {
381 return std::prev(It)->Includes(Point);
384bool RangeSet::pin(llvm::APSInt &Point)
const {
393bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper)
const {
413 Lower =
Type.getMinValue();
414 Upper =
Type.getMaxValue();
418 Lower =
Type.getMinValue();
423 Lower =
Type.getMinValue();
424 Upper =
Type.getMaxValue();
433 Upper =
Type.getMaxValue();
443 Upper =
Type.getMaxValue();
454 Lower =
Type.getMinValue();
464 Lower =
Type.getMinValue();
465 Upper =
Type.getMaxValue();
475 llvm::APSInt Upper) {
476 if (What.
isEmpty() || !What.pin(Lower, Upper))
477 return getEmptySet();
479 ContainerType DummyContainer;
481 if (Lower <= Upper) {
493 return getEmptySet();
495 DummyContainer.push_back(
496 Range(ValueFactory.getValue(Lower), ValueFactory.getValue(Upper)));
506 return getEmptySet();
508 DummyContainer.push_back(
509 Range(ValueFactory.getMinValue(Upper), ValueFactory.getValue(Upper)));
510 DummyContainer.push_back(
511 Range(ValueFactory.getValue(Lower), ValueFactory.getMaxValue(Lower)));
514 return intersect(*What.Impl, DummyContainer);
518 const RangeSet::ContainerType &RHS) {
520 Result.reserve(std::max(LHS.size(), RHS.size()));
523 FirstEnd = LHS.end(), SecondEnd = RHS.end();
528 while (
First != FirstEnd && Second != SecondEnd) {
533 if (Second->From() <
First->From())
544 if (Second->From() >
First->To()) {
560 const llvm::APSInt &IntersectionStart = Second->From();
565 if (Second->To() >
First->To()) {
582 Result.push_back(
Range(IntersectionStart, Second->To()));
586 }
while (Second != SecondEnd);
590 return getEmptySet();
592 return makePersistent(std::move(
Result));
599 return getEmptySet();
601 return intersect(*LHS.Impl, *RHS.Impl);
605 if (LHS.containsImpl(Point))
606 return getRangeSet(ValueFactory.getValue(Point));
608 return getEmptySet();
613 return getEmptySet();
615 const llvm::APSInt SampleValue = What.
getMinValue();
616 const llvm::APSInt &MIN = ValueFactory.getMinValue(SampleValue);
617 const llvm::APSInt &MAX = ValueFactory.getMaxValue(SampleValue);
620 Result.reserve(What.
size() + (SampleValue == MIN));
626 const llvm::APSInt &From = It->From();
627 const llvm::APSInt &To = It->To();
639 if (
Last->To() == MAX) {
643 Result.emplace_back(MIN, ValueFactory.getValue(-
Last->From()));
648 Result.emplace_back(MIN, MIN);
653 Result.emplace_back(ValueFactory.getValue(-To), MAX);
661 for (; It != End; ++It) {
663 const llvm::APSInt &NewFrom = ValueFactory.getValue(-It->To());
664 const llvm::APSInt &NewTo = ValueFactory.getValue(-It->From());
667 Result.emplace_back(NewFrom, NewTo);
671 return makePersistent(std::move(
Result));
686 return makePersistent(truncateTo(What, Ty));
700 if (IsConversion && (!IsPromotion || !What.
isUnsigned()))
701 return makePersistent(convertTo(What, Ty));
703 assert(IsPromotion &&
"Only promotion operation from unsigneds left.");
704 return makePersistent(promoteTo(What, Ty));
712RangeSet::ContainerType RangeSet::Factory::truncateTo(
RangeSet What,
725 uint64_t CastRangeSize = APInt::getMaxValue(Ty.
getBitWidth()).getZExtValue();
726 for (
const Range &R : What) {
728 APSInt FromInt = R.From();
732 uint64_t CurrentRangeSize = (ToInt - FromInt).getZExtValue();
736 if (CurrentRangeSize >= CastRangeSize) {
737 Dummy.emplace_back(ValueFactory.getMinValue(Ty),
738 ValueFactory.getMaxValue(Ty));
739 Result = std::move(Dummy);
745 const APSInt &PersistentFrom = ValueFactory.getValue(FromInt);
746 const APSInt &PersistentTo = ValueFactory.getValue(ToInt);
747 if (FromInt > ToInt) {
748 Dummy.emplace_back(ValueFactory.getMinValue(Ty), PersistentTo);
749 Dummy.emplace_back(PersistentFrom, ValueFactory.getMaxValue(Ty));
751 Dummy.emplace_back(PersistentFrom, PersistentTo);
778RangeSet::ContainerType RangeSet::Factory::convertTo(
RangeSet What,
782 using Bounds = std::pair<const APSInt &, const APSInt &>;
783 ContainerType AscendArray;
784 ContainerType DescendArray;
785 auto CastRange = [Ty, &VF = ValueFactory](
const Range &R) -> Bounds {
787 APSInt FromInt = R.From();
792 return {VF.getValue(FromInt), VF.getValue(ToInt)};
796 const auto *It = What.
begin();
797 const auto *
E = What.
end();
799 Bounds NewBounds = CastRange(*(It++));
801 if (NewBounds.first < LastConvertedInt) {
802 DescendArray.emplace_back(NewBounds.first, NewBounds.second);
809 if (NewBounds.first > NewBounds.second) {
810 DescendArray.emplace_back(ValueFactory.getMinValue(Ty), NewBounds.second);
811 AscendArray.emplace_back(NewBounds.first, ValueFactory.getMaxValue(Ty));
814 AscendArray.emplace_back(NewBounds.first, NewBounds.second);
815 LastConvertedInt = NewBounds.first;
819 Bounds NewBounds = CastRange(*(It++));
820 DescendArray.emplace_back(NewBounds.first, NewBounds.second);
823 return unite(AscendArray, DescendArray);
827RangeSet::ContainerType RangeSet::Factory::promoteTo(
RangeSet What,
836 for (
const Range &R : What) {
838 llvm::APSInt FromInt = R.From();
839 llvm::APSInt ToInt = R.To();
843 Result.emplace_back(ValueFactory.getValue(FromInt),
844 ValueFactory.getValue(ToInt));
850 const llvm::APSInt &Point) {
854 llvm::APSInt Upper = Point;
855 llvm::APSInt Lower = Point;
861 return intersect(From, Upper, Lower);
871 llvm::interleaveComma(*
this,
OS, [&
OS](
const Range &R) { R.
dump(
OS); });
879class EquivalenceClass;
914class EquivalenceClass :
public llvm::FoldingSetNode {
917 [[nodiscard]]
static inline EquivalenceClass find(
ProgramStateRef State,
954 EquivalenceClass
First, EquivalenceClass Second);
957 EquivalenceClass
Other)
const;
958 [[nodiscard]]
static inline ClassSet getDisequalClasses(
ProgramStateRef State,
960 [[nodiscard]]
inline ClassSet getDisequalClasses(
ProgramStateRef State)
const;
961 [[nodiscard]]
inline ClassSet
962 getDisequalClasses(DisequalityMapTy Map, ClassSet::Factory &Factory)
const;
964 [[nodiscard]]
static inline std::optional<bool>
966 EquivalenceClass Second);
967 [[nodiscard]]
static inline std::optional<bool>
978 EquivalenceClass Class);
982 dumpToStream(State, llvm::errs());
986 [[nodiscard]] LLVM_ATTRIBUTE_UNUSED
static bool
989 [[nodiscard]]
QualType getType()
const {
990 return getRepresentativeSymbol()->getType();
993 EquivalenceClass() =
delete;
994 EquivalenceClass(
const EquivalenceClass &) =
default;
995 EquivalenceClass &operator=(
const EquivalenceClass &) =
delete;
996 EquivalenceClass(EquivalenceClass &&) =
default;
997 EquivalenceClass &operator=(EquivalenceClass &&) =
delete;
1007 static void Profile(llvm::FoldingSetNodeID &
ID,
uintptr_t CID) {
1011 void Profile(llvm::FoldingSetNodeID &
ID)
const { Profile(
ID, this->ID); }
1022 SymbolRef getRepresentativeSymbol()
const {
1025 static inline SymbolSet::Factory &getMembersFactory(
ProgramStateRef State);
1032 addToDisequalityInfo(DisequalityMapTy &Info, ConstraintRangeTy &Constraints,
1034 EquivalenceClass
First, EquivalenceClass Second);
1044[[nodiscard]] LLVM_ATTRIBUTE_UNUSED
bool
1045areFeasible(ConstraintRangeTy Constraints) {
1046 return llvm::none_of(
1048 [](
const std::pair<EquivalenceClass, RangeSet> &ClassConstraint) {
1049 return ClassConstraint.second.isEmpty();
1054 EquivalenceClass Class) {
1055 return State->get<ConstraintRange>(
Class);
1060 return getConstraint(State, EquivalenceClass::find(State, Sym));
1064 EquivalenceClass Class,
1066 return State->set<ConstraintRange>(
Class, Constraint);
1070 ConstraintRangeTy Constraints) {
1071 return State->set<ConstraintRange>(Constraints);
1087std::optional<bool> meansEquality(
const SymSymExpr *Sym) {
1099 return std::nullopt;
1107template <
class SecondTy,
class... RestTy>
1109 SecondTy Second, RestTy... Tail);
1111template <
class... RangeTy>
struct IntersectionTraits;
1113template <
class... TailTy>
struct IntersectionTraits<
RangeSet, TailTy...> {
1118template <>
struct IntersectionTraits<> {
1121 using Type = std::optional<RangeSet>;
1124template <
class OptionalOrPointer,
class... TailTy>
1125struct IntersectionTraits<OptionalOrPointer, TailTy...> {
1127 using Type =
typename IntersectionTraits<TailTy...>
::Type;
1130template <
class EndTy>
1137[[nodiscard]] LLVM_ATTRIBUTE_UNUSED
inline std::optional<RangeSet>
1144 return std::nullopt;
1147template <
class... RestTy>
1152 return intersect(F, F.
intersect(Head, Second), Tail...);
1155template <
class SecondTy,
class... RestTy>
1157 SecondTy Second, RestTy... Tail) {
1160 return intersect(F, Head, *Second, Tail...);
1164 return intersect(F, Head, Tail...);
1188template <
class HeadTy,
class SecondTy,
class... RestTy>
1190 typename IntersectionTraits<HeadTy, SecondTy, RestTy...>
::Type
1194 return intersect(F, *Head, Second, Tail...);
1196 return intersect(F, Second, Tail...);
1208class SymbolicRangeInferrer
1211 template <
class SourceType>
1213 SourceType Origin) {
1214 SymbolicRangeInferrer Inferrer(F, State);
1215 return Inferrer.infer(Origin);
1219 if (std::optional<RangeSet> RS = getRangeForNegatedSym(Sym))
1229 if (std::optional<RangeSet> RS = getRangeForNegatedUnarySym(USE))
1235 return VisitBinaryOperator(Sym);
1239 return VisitBinaryOperator(Sym);
1251 getRangeForNegatedSymSym(SSE),
1253 getRangeCommutativeSymSym(SSE),
1257 getRangeForComparisonSymbol(SSE),
1260 getRangeForEqualities(SSE),
1262 VisitBinaryOperator(SSE));
1267 : ValueFactory(F.getValueFactory()), RangeFactory(F), State(S) {}
1274 return {RangeFactory, Val};
1287 return infer(DestType);
1291 return intersect(RangeFactory,
1294 getConstraint(State, Sym),
1300 RangeSet infer(EquivalenceClass Class) {
1301 if (
const RangeSet *AssociatedConstraint = getConstraint(State, Class))
1302 return *AssociatedConstraint;
1304 return infer(
Class.getType());
1311 RangeSet Result(RangeFactory, ValueFactory.getMinValue(
T),
1312 ValueFactory.getMaxValue(
T));
1316 return assumeNonZero(Result,
T);
1321 template <
class BinarySymExprTy>
1322 RangeSet VisitBinaryOperator(
const BinarySymExprTy *Sym) {
1334 QualType ResultType = Sym->getType();
1335 return VisitBinaryOperator(inferAs(Sym->getLHS(), ResultType),
1337 inferAs(Sym->getRHS(), ResultType), ResultType);
1363 return std::nullopt;
1365 return Range(ValueFactory.Convert(To, Origin.
From()),
1366 ValueFactory.Convert(To, Origin.
To()));
1369 template <BinaryOperator::Opcode Op>
1373 Range CoarseLHS = fillGaps(LHS);
1374 Range CoarseRHS = fillGaps(RHS);
1376 APSIntType ResultType = ValueFactory.getAPSIntType(
T);
1380 auto ConvertedCoarseLHS = convert(CoarseLHS, ResultType);
1381 auto ConvertedCoarseRHS = convert(CoarseRHS, ResultType);
1385 if (!ConvertedCoarseLHS || !ConvertedCoarseRHS) {
1389 return VisitBinaryOperator<Op>(*ConvertedCoarseLHS, *ConvertedCoarseRHS,
T);
1392 template <BinaryOperator::Opcode Op>
1406 APSIntType RangeType = ValueFactory.getAPSIntType(
T);
1409 return Range(ValueFactory.getMinValue(RangeType), Origin.
To());
1412 if (Origin.
From().isMinSignedValue()) {
1416 return {ValueFactory.getMinValue(RangeType),
1417 ValueFactory.getMaxValue(RangeType)};
1431 llvm::APSInt AbsMax = std::max(-Origin.
From(), Origin.
To());
1434 return {ValueFactory.getValue(-AbsMax), ValueFactory.getValue(AbsMax)};
1439 APSIntType IntType = ValueFactory.getAPSIntType(
T);
1443 template <
typename ProduceNegatedSymFunc>
1444 std::optional<RangeSet> getRangeForNegatedExpr(ProduceNegatedSymFunc F,
1449 return std::nullopt;
1452 if (
const RangeSet *NegatedRange = getConstraint(State, NegatedSym))
1453 return RangeFactory.negate(*NegatedRange);
1455 return std::nullopt;
1458 std::optional<RangeSet> getRangeForNegatedUnarySym(
const UnarySymExpr *USE) {
1461 return getRangeForNegatedExpr(
1470 std::optional<RangeSet> getRangeForNegatedSymSym(
const SymSymExpr *SSE) {
1471 return getRangeForNegatedExpr(
1472 [SSE, State = this->State]() ->
SymbolRef {
1474 return State->getSymbolManager().acquire<
SymSymExpr>(
1481 std::optional<RangeSet> getRangeForNegatedSym(
SymbolRef Sym) {
1482 return getRangeForNegatedExpr(
1483 [Sym, State = this->State]() {
1484 return State->getSymbolManager().acquire<UnarySymExpr>(
1485 Sym, UO_Minus, Sym->
getType());
1490 std::optional<RangeSet> getRangeCommutativeSymSym(
const SymSymExpr *SSE) {
1492 bool IsCommutative = llvm::is_contained(
1494 {BO_EQ, BO_NE, BO_Or, BO_And, BO_Add, BO_Mul, BO_Xor}, Op);
1496 return std::nullopt;
1502 return std::nullopt;
1515 std::optional<RangeSet> getRangeForComparisonSymbol(
const SymSymExpr *SSE) {
1520 return std::nullopt;
1539 for (
size_t i = 0; i < CmpOpTable.getCmpOpCount(); ++i) {
1545 const RangeSet *QueriedRangeSet = getConstraint(State, SymSym);
1549 if (!QueriedRangeSet) {
1553 QueriedRangeSet = getConstraint(State, SymSym);
1556 if (!QueriedRangeSet || QueriedRangeSet->isEmpty())
1559 const llvm::APSInt *ConcreteValue = QueriedRangeSet->getConcreteValue();
1560 const bool isInFalseBranch =
1561 ConcreteValue ? (*ConcreteValue == 0) :
false;
1566 if (isInFalseBranch)
1570 CmpOpTable.getCmpOpState(CurrentOP, QueriedOP);
1573 if (LastQueriedOpToUnknown != CurrentOP &&
1574 LastQueriedOpToUnknown != QueriedOP) {
1580 BranchState = CmpOpTable.getCmpOpStateForUnknownX2(CurrentOP);
1582 LastQueriedOpToUnknown = QueriedOP;
1591 return std::nullopt;
1594 std::optional<RangeSet> getRangeForEqualities(
const SymSymExpr *Sym) {
1595 std::optional<bool>
Equality = meansEquality(Sym);
1598 return std::nullopt;
1600 if (std::optional<bool> AreEqual =
1601 EquivalenceClass::areEqual(State, Sym->
getLHS(), Sym->
getRHS())) {
1605 if (*AreEqual == *Equality) {
1606 return getTrueRange(Sym->
getType());
1609 return getFalseRange(Sym->
getType());
1612 return std::nullopt;
1617 return assumeNonZero(TypeRange,
T);
1621 const llvm::APSInt &
Zero = ValueFactory.getValue(0,
T);
1622 return RangeSet(RangeFactory, Zero);
1641 if (intersect(RangeFactory, LHS, RHS).isEmpty())
1642 return getTrueRange(
T);
1661 return getTrueRange(
T);
1666 return getTrueRange(
T);
1674 RangeSet CastedLHS = RangeFactory.castTo(LHS, CastingType);
1675 RangeSet CastedRHS = RangeFactory.castTo(RHS, CastingType);
1677 if (intersect(RangeFactory, CastedLHS, CastedRHS).isEmpty())
1678 return getTrueRange(
T);
1688 APSIntType ResultType = ValueFactory.getAPSIntType(
T);
1691 bool IsLHSPositiveOrZero = LHS.
From() >=
Zero;
1692 bool IsRHSPositiveOrZero = RHS.
From() >=
Zero;
1694 bool IsLHSNegative = LHS.
To() <
Zero;
1695 bool IsRHSNegative = RHS.
To() <
Zero;
1698 if ((IsLHSPositiveOrZero && IsRHSPositiveOrZero) ||
1699 (IsLHSNegative && IsRHSNegative)) {
1701 const llvm::APSInt &
Min = std::max(LHS.
From(), RHS.
From());
1714 const llvm::APSInt &
Max = IsLHSNegative
1715 ? ValueFactory.getValue(--Zero)
1716 : ValueFactory.getMaxValue(ResultType);
1718 return {RangeFactory, ValueFactory.getValue(
Min),
Max};
1722 if (IsLHSNegative || IsRHSNegative) {
1724 return {RangeFactory, ValueFactory.getMinValue(ResultType),
1725 ValueFactory.getValue(--Zero)};
1735 return assumeNonZero(DefaultRange,
T);
1739 return DefaultRange;
1743RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_And>(
Range LHS,
1746 APSIntType ResultType = ValueFactory.getAPSIntType(
T);
1749 bool IsLHSPositiveOrZero = LHS.
From() >=
Zero;
1750 bool IsRHSPositiveOrZero = RHS.
From() >=
Zero;
1752 bool IsLHSNegative = LHS.
To() <
Zero;
1753 bool IsRHSNegative = RHS.
To() <
Zero;
1756 if ((IsLHSPositiveOrZero && IsRHSPositiveOrZero) ||
1757 (IsLHSNegative && IsRHSNegative)) {
1759 const llvm::APSInt &
Max = std::min(LHS.
To(), RHS.
To());
1763 const llvm::APSInt &
Min = IsLHSNegative
1764 ? ValueFactory.getMinValue(ResultType)
1765 : ValueFactory.getValue(Zero);
1767 return {RangeFactory,
Min,
Max};
1771 if (IsLHSPositiveOrZero || IsRHSPositiveOrZero) {
1776 const llvm::APSInt &
Max = IsLHSPositiveOrZero ? LHS.
To() : RHS.
To();
1780 return {RangeFactory, ValueFactory.getValue(Zero),
1781 ValueFactory.getValue(
Max)};
1789RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Rem>(
Range LHS,
1792 llvm::APSInt
Zero = ValueFactory.getAPSIntType(
T).getZeroValue();
1794 Range ConservativeRange = getSymmetricalRange(RHS,
T);
1796 llvm::APSInt
Max = ConservativeRange.
To();
1797 llvm::APSInt
Min = ConservativeRange.
From();
1803 return RangeFactory.getEmptySet();
1816 if (
Min.isSigned()) {
1821 bool IsLHSPositiveOrZero = LHS.
From() >=
Zero;
1822 bool IsRHSPositiveOrZero = RHS.
From() >=
Zero;
1826 if (IsLHSPositiveOrZero && IsRHSPositiveOrZero) {
1842 return {RangeFactory, ValueFactory.getValue(
Min), ValueFactory.getValue(
Max)};
1851 return RangeFactory.getEmptySet();
1856 return VisitBinaryOperator<BO_NE>(LHS, RHS,
T);
1858 return VisitBinaryOperator<BO_Or>(LHS, RHS,
T);
1860 return VisitBinaryOperator<BO_And>(LHS, RHS,
T);
1862 return VisitBinaryOperator<BO_Rem>(LHS, RHS,
T);
1886 return S1->get<ConstraintRange>() == S2->get<ConstraintRange>() &&
1887 S1->get<ClassMap>() == S2->get<ClassMap>();
1890 bool canReasonAbout(
SVal X)
const override;
1906 void printJson(raw_ostream &Out,
ProgramStateRef State,
const char *NL =
"\n",
1907 unsigned int Space = 0,
bool IsDot =
false)
const override;
1911 const char *NL =
"\n",
unsigned int Space = 0,
1912 bool IsDot =
false)
const;
1914 const char *NL =
"\n",
unsigned int Space = 0,
1915 bool IsDot =
false)
const;
1917 const char *NL =
"\n",
unsigned int Space = 0,
1918 bool IsDot =
false)
const;
1925 const llvm::APSInt &
V,
1926 const llvm::APSInt &Adjustment)
override;
1929 const llvm::APSInt &
V,
1930 const llvm::APSInt &Adjustment)
override;
1933 const llvm::APSInt &
V,
1934 const llvm::APSInt &Adjustment)
override;
1937 const llvm::APSInt &
V,
1938 const llvm::APSInt &Adjustment)
override;
1941 const llvm::APSInt &
V,
1942 const llvm::APSInt &Adjustment)
override;
1945 const llvm::APSInt &
V,
1946 const llvm::APSInt &Adjustment)
override;
1950 const llvm::APSInt &To,
const llvm::APSInt &Adjustment)
override;
1954 const llvm::APSInt &To,
const llvm::APSInt &Adjustment)
override;
1964 const llvm::APSInt &Int,
1965 const llvm::APSInt &Adjustment)
const;
1967 const llvm::APSInt &Int,
1968 const llvm::APSInt &Adjustment)
const;
1970 const llvm::APSInt &Int,
1971 const llvm::APSInt &Adjustment)
const;
1973 const llvm::APSInt &Int,
1974 const llvm::APSInt &Adjustment)
const;
1976 const llvm::APSInt &Int,
1977 const llvm::APSInt &Adjustment)
const;
1998template <
class Derived>
class ConstraintAssignorBase {
2000 using Const =
const llvm::APSInt &;
2002#define DISPATCH(CLASS) return assign##CLASS##Impl(cast<CLASS>(Sym), Constraint)
2004#define ASSIGN(CLASS, TO, SYM, CONSTRAINT) \
2005 if (!static_cast<Derived *>(this)->assign##CLASS##To##TO(SYM, CONSTRAINT)) \
2009 assignImpl(Sym, Constraint);
2014#define SYMBOL(Id, Parent) \
2015 case SymExpr::Id##Kind: \
2017#include "clang/StaticAnalyzer/Core/PathSensitive/Symbols.def"
2019 llvm_unreachable(
"Unknown SymExpr kind!");
2022#define DEFAULT_ASSIGN(Id) \
2023 bool assign##Id##To##RangeSet(const Id *Sym, RangeSet Constraint) { \
2026 bool assign##Id##To##Range(const Id *Sym, Range Constraint) { return true; } \
2027 bool assign##Id##To##Const(const Id *Sym, Const Constraint) { return true; }
2033#define CONSTRAINT_DISPATCH(Id) \
2034 if (const llvm::APSInt *Const = Constraint.getConcreteValue()) { \
2035 ASSIGN(Id, Const, Sym, *Const); \
2037 if (Constraint.size() == 1) { \
2038 ASSIGN(Id, Range, Sym, *Constraint.begin()); \
2040 ASSIGN(Id, RangeSet, Sym, Constraint)
2045#define SYMBOL(Id, Parent) \
2046 bool assign##Id##Impl(const Id *Sym, RangeSet Constraint) { \
2047 CONSTRAINT_DISPATCH(Id); \
2051#define ABSTRACT_SYMBOL(Id, Parent) SYMBOL(Id, Parent)
2052#include "clang/StaticAnalyzer/Core/PathSensitive/Symbols.def"
2062#undef CONSTRAINT_DISPATCH
2063#undef DEFAULT_ASSIGN
2078class ConstraintAssignor :
public ConstraintAssignorBase<ConstraintAssignor> {
2080 template <
class ClassOrSymbol>
2083 ClassOrSymbol CoS,
RangeSet NewConstraint) {
2084 if (!State || NewConstraint.
isEmpty())
2087 ConstraintAssignor Assignor{State, Builder, F};
2088 return Assignor.assign(CoS, NewConstraint);
2092 template <
typename SymT>
2093 bool handleRemainderOp(
const SymT *Sym,
RangeSet Constraint) {
2094 if (Sym->getOpcode() != BO_Rem)
2098 SVal SymSVal = Builder.makeSymbolVal(Sym->getLHS());
2100 State = State->assume(*NonLocSymSVal,
true);
2108 inline bool assignSymExprToConst(
const SymExpr *Sym, Const Constraint);
2109 inline bool assignSymIntExprToRangeSet(
const SymIntExpr *Sym,
2111 return handleRemainderOp(Sym, Constraint);
2113 inline bool assignSymSymExprToRangeSet(
const SymSymExpr *Sym,
2119 : State(State), Builder(Builder), RangeFactory(F) {}
2120 using Base = ConstraintAssignorBase<ConstraintAssignor>;
2126 State = assign(EquivalenceClass::find(State, Sym), NewConstraint);
2132 Base::assign(Sym, NewConstraint);
2146 ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2147 ConstraintRangeTy::Factory &
CF = State->get_context<ConstraintRange>();
2150 Constraints =
CF.add(Constraints, Class, NewConstraint);
2152 for (EquivalenceClass DisequalClass :
Class.getDisequalClasses(State)) {
2153 RangeSet UpdatedConstraint = SymbolicRangeInferrer::inferRange(
2154 RangeFactory, State, DisequalClass);
2156 UpdatedConstraint = RangeFactory.deletePoint(UpdatedConstraint, *Point);
2160 if (UpdatedConstraint.
isEmpty())
2163 Constraints =
CF.add(Constraints, DisequalClass, UpdatedConstraint);
2165 assert(areFeasible(Constraints) &&
"Constraint manager shouldn't produce "
2166 "a state with infeasible constraints");
2168 return setConstraints(State, Constraints);
2171 return setConstraint(State, Class, NewConstraint);
2176 return EquivalenceClass::markDisequal(RangeFactory, State, LHS, RHS);
2181 return EquivalenceClass::merge(RangeFactory, State, LHS, RHS);
2184 [[nodiscard]] std::optional<bool> interpreteAsBool(
RangeSet Constraint) {
2185 assert(!Constraint.
isEmpty() &&
"Empty ranges shouldn't get here");
2193 return std::nullopt;
2201bool ConstraintAssignor::assignSymExprToConst(
const SymExpr *Sym,
2202 const llvm::APSInt &Constraint) {
2203 llvm::SmallSet<EquivalenceClass, 4> SimplifiedClasses;
2205 ClassMembersTy Members = State->get<ClassMembers>();
2206 for (std::pair<EquivalenceClass, SymbolSet> ClassToSymbolSet : Members) {
2207 EquivalenceClass
Class = ClassToSymbolSet.first;
2208 State = EquivalenceClass::simplify(Builder, RangeFactory, State, Class);
2211 SimplifiedClasses.insert(Class);
2217 ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2218 for (std::pair<EquivalenceClass, RangeSet> ClassConstraint : Constraints) {
2219 EquivalenceClass
Class = ClassConstraint.first;
2220 if (SimplifiedClasses.count(Class))
2222 State = EquivalenceClass::simplify(Builder, RangeFactory, State, Class);
2229 DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>();
2230 for (std::pair<EquivalenceClass, ClassSet> DisequalityEntry :
2232 EquivalenceClass
Class = DisequalityEntry.first;
2233 ClassSet DisequalClasses = DisequalityEntry.second;
2234 State = EquivalenceClass::simplify(Builder, RangeFactory, State, Class);
2242bool ConstraintAssignor::assignSymSymExprToRangeSet(
const SymSymExpr *Sym,
2244 if (!handleRemainderOp(Sym, Constraint))
2247 std::optional<bool> ConstraintAsBool = interpreteAsBool(Constraint);
2249 if (!ConstraintAsBool)
2252 if (std::optional<bool> Equality = meansEquality(Sym)) {
2258 if (*Equality == *ConstraintAsBool) {
2259 State = trackEquality(State, Sym->
getLHS(), Sym->
getRHS());
2262 State = trackDisequality(State, Sym->
getLHS(), Sym->
getRHS());
2274std::unique_ptr<ConstraintManager>
2277 return std::make_unique<RangeConstraintManager>(Eng, StMgr.
getSValBuilder());
2281 ConstraintMap::Factory &F = State->get_context<
ConstraintMap>();
2284 ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2285 for (std::pair<EquivalenceClass, RangeSet> ClassConstraint : Constraints) {
2286 EquivalenceClass
Class = ClassConstraint.first;
2288 assert(!ClassMembers.isEmpty() &&
2289 "Class must always have at least one member!");
2291 SymbolRef Representative = *ClassMembers.begin();
2292 Result = F.add(
Result, Representative, ClassConstraint.second);
2302LLVM_DUMP_METHOD
void EquivalenceClass::dumpToStream(
ProgramStateRef State,
2303 raw_ostream &os)
const {
2304 SymbolSet ClassMembers = getClassMembers(State);
2305 for (
const SymbolRef &MemberSym : ClassMembers) {
2313 assert(State &&
"State should not be null");
2314 assert(Sym &&
"Symbol should not be null");
2316 if (
const EquivalenceClass *NontrivialClass = State->get<ClassMap>(Sym))
2317 return *NontrivialClass;
2327 EquivalenceClass FirstClass = find(State,
First);
2328 EquivalenceClass SecondClass = find(State, Second);
2330 return FirstClass.merge(F, State, SecondClass);
2335 EquivalenceClass
Other) {
2351 if (getType()->getCanonicalTypeUnqualified() !=
2352 Other.getType()->getCanonicalTypeUnqualified())
2355 SymbolSet Members = getClassMembers(State);
2361 if (Members.getHeight() >= OtherMembers.getHeight()) {
2362 return mergeImpl(F, State, Members,
Other, OtherMembers);
2364 return Other.mergeImpl(F, State, OtherMembers, *
this, Members);
2383 ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2384 ConstraintRangeTy::Factory &CRF = State->get_context<ConstraintRange>();
2391 if (std::optional<RangeSet> NewClassConstraint =
2392 intersect(RangeFactory, getConstraint(State, *
this),
2393 getConstraint(State,
Other))) {
2399 if (NewClassConstraint->isEmpty())
2404 Constraints = CRF.remove(Constraints,
Other);
2406 Constraints = CRF.add(Constraints, *
this, *NewClassConstraint);
2408 assert(areFeasible(Constraints) &&
"Constraint manager shouldn't produce "
2409 "a state with infeasible constraints");
2411 State = State->set<ConstraintRange>(Constraints);
2415 ClassMapTy Classes = State->get<ClassMap>();
2416 ClassMapTy::Factory &CMF = State->get_context<ClassMap>();
2418 ClassMembersTy Members = State->get<ClassMembers>();
2419 ClassMembersTy::Factory &MF = State->get_context<ClassMembers>();
2421 DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>();
2422 DisequalityMapTy::Factory &DF = State->get_context<DisequalityMap>();
2424 ClassSet::Factory &
CF = State->get_context<ClassSet>();
2425 SymbolSet::Factory &F = getMembersFactory(State);
2430 NewClassMembers = F.add(NewClassMembers, Sym);
2432 Classes = CMF.add(Classes, Sym, *
this);
2438 Members = MF.remove(Members,
Other);
2440 Members = MF.add(Members, *
this, NewClassMembers);
2443 ClassSet DisequalToOther =
Other.getDisequalClasses(DisequalityInfo,
CF);
2446 if (DisequalToOther.contains(*
this))
2449 if (!DisequalToOther.isEmpty()) {
2450 ClassSet DisequalToThis = getDisequalClasses(DisequalityInfo,
CF);
2451 DisequalityInfo = DF.remove(DisequalityInfo,
Other);
2453 for (EquivalenceClass DisequalClass : DisequalToOther) {
2454 DisequalToThis =
CF.add(DisequalToThis, DisequalClass);
2459 ClassSet OriginalSetLinkedToOther =
2460 *DisequalityInfo.lookup(DisequalClass);
2464 ClassSet NewSet =
CF.remove(OriginalSetLinkedToOther,
Other);
2465 NewSet =
CF.add(NewSet, *
this);
2467 DisequalityInfo = DF.add(DisequalityInfo, DisequalClass, NewSet);
2470 DisequalityInfo = DF.add(DisequalityInfo, *
this, DisequalToThis);
2471 State = State->set<DisequalityMap>(DisequalityInfo);
2475 State = State->set<ClassMap>(Classes);
2476 State = State->set<ClassMembers>(Members);
2481inline SymbolSet::Factory &
2487 if (
const SymbolSet *Members = State->get<ClassMembers>(*
this))
2492 SymbolSet::Factory &F = getMembersFactory(State);
2493 return F.add(F.getEmptySet(), getRepresentativeSymbol());
2497 return State->get<ClassMembers>(*this) ==
nullptr;
2509 return markDisequal(RF, State, find(State,
First), find(State, Second));
2514 EquivalenceClass
First,
2515 EquivalenceClass Second) {
2516 return First.markDisequal(RF, State, Second);
2521 EquivalenceClass
Other)
const {
2524 if (*
this ==
Other) {
2528 DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>();
2529 ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2533 if (!addToDisequalityInfo(DisequalityInfo, Constraints, RF, State, *
this,
2535 !addToDisequalityInfo(DisequalityInfo, Constraints, RF, State,
Other,
2539 assert(areFeasible(Constraints) &&
"Constraint manager shouldn't produce "
2540 "a state with infeasible constraints");
2542 State = State->set<DisequalityMap>(DisequalityInfo);
2543 State = State->set<ConstraintRange>(Constraints);
2548inline bool EquivalenceClass::addToDisequalityInfo(
2549 DisequalityMapTy &Info, ConstraintRangeTy &Constraints,
2551 EquivalenceClass Second) {
2554 DisequalityMapTy::Factory &F = State->get_context<DisequalityMap>();
2555 ClassSet::Factory &
CF = State->get_context<ClassSet>();
2556 ConstraintRangeTy::Factory &CRF = State->get_context<ConstraintRange>();
2559 const ClassSet *CurrentSet = Info.lookup(
First);
2560 ClassSet NewSet = CurrentSet ? *CurrentSet :
CF.getEmptySet();
2561 NewSet =
CF.add(NewSet, Second);
2563 Info = F.add(Info,
First, NewSet);
2570 if (
const RangeSet *SecondConstraint = Constraints.lookup(Second))
2571 if (
const llvm::APSInt *Point = SecondConstraint->getConcreteValue()) {
2573 RangeSet FirstConstraint = SymbolicRangeInferrer::inferRange(
2574 RF, State,
First.getRepresentativeSymbol());
2576 FirstConstraint = RF.
deletePoint(FirstConstraint, *Point);
2580 if (FirstConstraint.
isEmpty())
2583 Constraints = CRF.add(Constraints,
First, FirstConstraint);
2589inline std::optional<bool> EquivalenceClass::areEqual(
ProgramStateRef State,
2592 return EquivalenceClass::areEqual(State, find(State, FirstSym),
2593 find(State, SecondSym));
2596inline std::optional<bool> EquivalenceClass::areEqual(
ProgramStateRef State,
2597 EquivalenceClass
First,
2598 EquivalenceClass Second) {
2600 if (
First == Second)
2605 ClassSet DisequalToFirst =
First.getDisequalClasses(State);
2606 if (DisequalToFirst.contains(Second))
2610 return std::nullopt;
2616 SymbolSet ClsMembers = getClassMembers(State);
2617 assert(ClsMembers.contains(Old));
2620 SymbolSet::Factory &F = getMembersFactory(State);
2621 ClassMembersTy::Factory &EMFactory = State->get_context<ClassMembers>();
2622 ClsMembers = F.remove(ClsMembers, Old);
2625 assert(!ClsMembers.isEmpty() &&
2626 "Class should have had at least two members before member removal");
2628 ClassMembersTy ClassMembersMap = State->get<ClassMembers>();
2629 ClassMembersMap = EMFactory.add(ClassMembersMap, *
this, ClsMembers);
2630 State = State->set<ClassMembers>(ClassMembersMap);
2633 ClassMapTy Classes = State->get<ClassMap>();
2634 ClassMapTy::Factory &CMF = State->get_context<ClassMap>();
2635 Classes = CMF.remove(Classes, Old);
2636 State = State->set<ClassMap>(Classes);
2651 return State->assume(DefinedVal,
false);
2656 State = State->assume(DefinedVal,
true);
2663 return State->assumeInclusiveRange(DefinedVal, Constraint->
getMinValue(),
2676 for (
const SymbolRef &MemberSym : ClassMembers) {
2684 const llvm::APSInt &SV = CI->getValue();
2685 const RangeSet *ClassConstraint = getConstraint(State,
Class);
2687 if (ClassConstraint && !ClassConstraint->
contains(SV))
2691 if (SimplifiedMemberSym && MemberSym != SimplifiedMemberSym) {
2696 State = merge(F, State, MemberSym, SimplifiedMemberSym);
2700 if (OldState == State)
2716 State = find(State, MemberSym).removeMember(State, MemberSym);
2720 const RangeSet *ClassConstraint = getConstraint(State,
Class);
2741 State =
reAssume(State, ClassConstraint, SimplifiedMemberVal);
2749inline ClassSet EquivalenceClass::getDisequalClasses(
ProgramStateRef State,
2751 return find(State, Sym).getDisequalClasses(State);
2756 return getDisequalClasses(State->get<DisequalityMap>(),
2757 State->get_context<ClassSet>());
2761EquivalenceClass::getDisequalClasses(DisequalityMapTy Map,
2762 ClassSet::Factory &Factory)
const {
2763 if (
const ClassSet *DisequalClasses = Map.lookup(*
this))
2764 return *DisequalClasses;
2766 return Factory.getEmptySet();
2770 ClassMembersTy Members = State->get<ClassMembers>();
2772 for (std::pair<EquivalenceClass, SymbolSet> ClassMembersPair : Members) {
2775 if (find(State,
Member) == ClassMembersPair.first) {
2783 DisequalityMapTy Disequalities = State->get<DisequalityMap>();
2784 for (std::pair<EquivalenceClass, ClassSet> DisequalityInfo : Disequalities) {
2785 EquivalenceClass
Class = DisequalityInfo.first;
2786 ClassSet DisequalClasses = DisequalityInfo.second;
2789 if (DisequalClasses.isEmpty())
2794 for (EquivalenceClass DisequalClass : DisequalClasses) {
2795 const ClassSet *DisequalToDisequalClasses =
2796 Disequalities.lookup(DisequalClass);
2799 if (!DisequalToDisequalClasses ||
2800 !DisequalToDisequalClasses->contains(
Class))
2812bool RangeConstraintManager::canReasonAbout(
SVal X)
const {
2814 if (SymVal && SymVal->isExpression()) {
2815 const SymExpr *SE = SymVal->getSymbol();
2817 if (
const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) {
2818 switch (SIE->getOpcode()) {
2838 if (
const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) {
2860 const RangeSet *Ranges = getConstraint(State, Sym);
2882const llvm::APSInt *RangeConstraintManager::getSymVal(
ProgramStateRef St,
2884 return getRange(St, Sym).getConcreteValue();
2887const llvm::APSInt *RangeConstraintManager::getSymMinVal(
ProgramStateRef St,
2890 return Range.isEmpty() ? nullptr : &
Range.getMinValue();
2893const llvm::APSInt *RangeConstraintManager::getSymMaxVal(
ProgramStateRef St,
2896 return Range.isEmpty() ? nullptr : &
Range.getMaxValue();
2908 ClassMembersTy ClassMembersMap = State->get<ClassMembers>();
2909 ClassMembersTy NewClassMembersMap = ClassMembersMap;
2910 ClassMembersTy::Factory &EMFactory = State->get_context<ClassMembers>();
2911 SymbolSet::Factory &SetFactory = State->get_context<
SymbolSet>();
2913 ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2914 ConstraintRangeTy NewConstraints = Constraints;
2915 ConstraintRangeTy::Factory &ConstraintFactory =
2916 State->get_context<ConstraintRange>();
2918 ClassMapTy Map = State->get<ClassMap>();
2919 ClassMapTy NewMap = Map;
2920 ClassMapTy::Factory &ClassFactory = State->get_context<ClassMap>();
2922 DisequalityMapTy Disequalities = State->get<DisequalityMap>();
2923 DisequalityMapTy::Factory &DisequalityFactory =
2924 State->get_context<DisequalityMap>();
2925 ClassSet::Factory &ClassSetFactory = State->get_context<ClassSet>();
2927 bool ClassMapChanged =
false;
2928 bool MembersMapChanged =
false;
2929 bool ConstraintMapChanged =
false;
2930 bool DisequalitiesChanged =
false;
2932 auto removeDeadClass = [&](EquivalenceClass
Class) {
2934 Constraints = ConstraintFactory.remove(Constraints,
Class);
2935 ConstraintMapChanged =
true;
2939 ClassSet DisequalClasses =
2940 Class.getDisequalClasses(Disequalities, ClassSetFactory);
2941 if (!DisequalClasses.isEmpty()) {
2942 for (EquivalenceClass DisequalClass : DisequalClasses) {
2943 ClassSet DisequalToDisequalSet =
2944 DisequalClass.getDisequalClasses(Disequalities, ClassSetFactory);
2947 assert(!DisequalToDisequalSet.isEmpty());
2948 ClassSet NewSet = ClassSetFactory.remove(DisequalToDisequalSet,
Class);
2951 if (NewSet.isEmpty()) {
2953 DisequalityFactory.remove(Disequalities, DisequalClass);
2956 DisequalityFactory.add(Disequalities, DisequalClass, NewSet);
2960 Disequalities = DisequalityFactory.remove(Disequalities,
Class);
2961 DisequalitiesChanged =
true;
2966 for (std::pair<EquivalenceClass, RangeSet> ClassConstraintPair :
2968 EquivalenceClass
Class = ClassConstraintPair.first;
2969 if (
Class.isTriviallyDead(State, SymReaper)) {
2971 removeDeadClass(
Class);
2976 for (std::pair<SymbolRef, EquivalenceClass> SymbolClassPair : Map) {
2979 if (SymReaper.
isDead(Sym)) {
2980 ClassMapChanged =
true;
2981 NewMap = ClassFactory.remove(NewMap, Sym);
2987 for (std::pair<EquivalenceClass, SymbolSet> ClassMembersPair :
2989 EquivalenceClass
Class = ClassMembersPair.first;
2990 SymbolSet LiveMembers = ClassMembersPair.second;
2991 bool MembersChanged =
false;
2995 MembersChanged =
true;
2996 LiveMembers = SetFactory.remove(LiveMembers,
Member);
3001 if (!MembersChanged)
3004 MembersMapChanged =
true;
3006 if (LiveMembers.isEmpty()) {
3008 NewClassMembersMap = EMFactory.remove(NewClassMembersMap,
Class);
3011 removeDeadClass(
Class);
3014 NewClassMembersMap =
3015 EMFactory.add(NewClassMembersMap,
Class, LiveMembers);
3022 if (ClassMapChanged)
3023 State = State->set<ClassMap>(NewMap);
3025 if (MembersMapChanged)
3026 State = State->set<ClassMembers>(NewClassMembersMap);
3028 if (ConstraintMapChanged)
3029 State = State->set<ConstraintRange>(Constraints);
3031 if (DisequalitiesChanged)
3032 State = State->set<DisequalityMap>(Disequalities);
3034 assert(EquivalenceClass::isClassDataConsistent(State));
3041 return SymbolicRangeInferrer::inferRange(F, State, Sym);
3047 return ConstraintAssignor::assign(State, getSValBuilder(), F, Sym,
Range);
3064 const llvm::APSInt &Int,
3065 const llvm::APSInt &Adjustment) {
3071 llvm::APSInt Point = AdjustmentType.convert(Int) - Adjustment;
3075 return setRange(St, Sym, New);
3080 const llvm::APSInt &Int,
3081 const llvm::APSInt &Adjustment) {
3088 llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment;
3092 return setRange(St, Sym, New);
3097 const llvm::APSInt &Int,
3098 const llvm::APSInt &Adjustment)
const {
3101 switch (AdjustmentType.testInRange(Int,
true)) {
3111 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
3112 llvm::APSInt
Min = AdjustmentType.getMinValue();
3113 if (ComparisonVal ==
Min)
3116 llvm::APSInt Lower =
Min - Adjustment;
3117 llvm::APSInt Upper = ComparisonVal - Adjustment;
3126 const llvm::APSInt &Int,
3127 const llvm::APSInt &Adjustment) {
3128 RangeSet New = getSymLTRange(St, Sym, Int, Adjustment);
3129 return setRange(St, Sym, New);
3134 const llvm::APSInt &Int,
3135 const llvm::APSInt &Adjustment)
const {
3138 switch (AdjustmentType.testInRange(Int,
true)) {
3148 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
3149 llvm::APSInt
Max = AdjustmentType.getMaxValue();
3150 if (ComparisonVal ==
Max)
3153 llvm::APSInt Lower = ComparisonVal - Adjustment;
3154 llvm::APSInt Upper =
Max - Adjustment;
3158 return F.
intersect(SymRange, Lower, Upper);
3163 const llvm::APSInt &Int,
3164 const llvm::APSInt &Adjustment) {
3165 RangeSet New = getSymGTRange(St, Sym, Int, Adjustment);
3166 return setRange(St, Sym, New);
3171 const llvm::APSInt &Int,
3172 const llvm::APSInt &Adjustment)
const {
3175 switch (AdjustmentType.testInRange(Int,
true)) {
3185 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
3186 llvm::APSInt
Min = AdjustmentType.getMinValue();
3187 if (ComparisonVal ==
Min)
3190 llvm::APSInt
Max = AdjustmentType.getMaxValue();
3191 llvm::APSInt Lower = ComparisonVal - Adjustment;
3192 llvm::APSInt Upper =
Max - Adjustment;
3195 return F.
intersect(SymRange, Lower, Upper);
3200 const llvm::APSInt &Int,
3201 const llvm::APSInt &Adjustment) {
3202 RangeSet New = getSymGERange(St, Sym, Int, Adjustment);
3203 return setRange(St, Sym, New);
3207RangeConstraintManager::getSymLERange(llvm::function_ref<
RangeSet()> RS,
3208 const llvm::APSInt &Int,
3209 const llvm::APSInt &Adjustment)
const {
3212 switch (AdjustmentType.testInRange(Int,
true)) {
3222 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
3223 llvm::APSInt
Max = AdjustmentType.getMaxValue();
3224 if (ComparisonVal ==
Max)
3227 llvm::APSInt
Min = AdjustmentType.getMinValue();
3228 llvm::APSInt Lower =
Min - Adjustment;
3229 llvm::APSInt Upper = ComparisonVal - Adjustment;
3237 const llvm::APSInt &Int,
3238 const llvm::APSInt &Adjustment)
const {
3239 return getSymLERange([&] {
return getRange(St, Sym); },
Int, Adjustment);
3244 const llvm::APSInt &Int,
3245 const llvm::APSInt &Adjustment) {
3246 RangeSet New = getSymLERange(St, Sym, Int, Adjustment);
3247 return setRange(St, Sym, New);
3252 const llvm::APSInt &To,
const llvm::APSInt &Adjustment) {
3253 RangeSet New = getSymGERange(State, Sym, From, Adjustment);
3256 RangeSet Out = getSymLERange([&] {
return New; }, To, Adjustment);
3257 return setRange(State, Sym, Out);
3260ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange(
3262 const llvm::APSInt &To,
const llvm::APSInt &Adjustment) {
3263 RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment);
3264 RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment);
3266 return setRange(State, Sym, New);
3273void RangeConstraintManager::printJson(raw_ostream &Out,
ProgramStateRef State,
3274 const char *NL,
unsigned int Space,
3276 printConstraints(Out, State, NL, Space, IsDot);
3277 printEquivalenceClasses(Out, State, NL, Space, IsDot);
3278 printDisequalities(Out, State, NL, Space, IsDot);
3281void RangeConstraintManager::printValue(raw_ostream &Out,
ProgramStateRef State,
3285 Out <<
"<empty rangeset>";
3294 llvm::raw_string_ostream O(S);
3299void RangeConstraintManager::printConstraints(raw_ostream &Out,
3304 ConstraintRangeTy Constraints = State->get<ConstraintRange>();
3306 Indent(Out, Space, IsDot) <<
"\"constraints\": ";
3307 if (Constraints.isEmpty()) {
3308 Out <<
"null," << NL;
3312 std::map<std::string, RangeSet> OrderedConstraints;
3313 for (std::pair<EquivalenceClass, RangeSet>
P : Constraints) {
3314 SymbolSet ClassMembers =
P.first.getClassMembers(State);
3315 for (
const SymbolRef &ClassMember : ClassMembers) {
3316 bool insertion_took_place;
3317 std::tie(std::ignore, insertion_took_place) =
3318 OrderedConstraints.insert({
toString(ClassMember),
P.second});
3319 assert(insertion_took_place &&
3320 "two symbols should not have the same dump");
3327 for (std::pair<std::string, RangeSet>
P : OrderedConstraints) {
3334 Indent(Out, Space, IsDot)
3335 <<
"{ \"symbol\": \"" <<
P.first <<
"\", \"range\": \"";
3342 Indent(Out, Space, IsDot) <<
"]," << NL;
3348 ClassMembers.end());
3349 llvm::sort(ClassMembersSorted,
3354 bool FirstMember =
true;
3357 llvm::raw_string_ostream Out(Str);
3359 for (
SymbolRef ClassMember : ClassMembersSorted) {
3361 FirstMember =
false;
3364 Out <<
"\"" << ClassMember <<
"\"";
3370void RangeConstraintManager::printEquivalenceClasses(raw_ostream &Out,
3375 ClassMembersTy Members = State->get<ClassMembers>();
3377 Indent(Out, Space, IsDot) <<
"\"equivalence_classes\": ";
3378 if (Members.isEmpty()) {
3379 Out <<
"null," << NL;
3383 std::set<std::string> MembersStr;
3384 for (std::pair<EquivalenceClass, SymbolSet> ClassToSymbolSet : Members)
3385 MembersStr.insert(
toString(State, ClassToSymbolSet.first));
3389 bool FirstClass =
true;
3390 for (
const std::string &Str : MembersStr) {
3397 Indent(Out, Space, IsDot);
3403 Indent(Out, Space, IsDot) <<
"]," << NL;
3406void RangeConstraintManager::printDisequalities(raw_ostream &Out,
3411 DisequalityMapTy Disequalities = State->get<DisequalityMap>();
3413 Indent(Out, Space, IsDot) <<
"\"disequality_info\": ";
3414 if (Disequalities.isEmpty()) {
3415 Out <<
"null," << NL;
3421 using EqClassesStrTy = std::set<std::string>;
3422 using DisequalityInfoStrTy = std::map<std::string, EqClassesStrTy>;
3423 DisequalityInfoStrTy DisequalityInfoStr;
3424 for (std::pair<EquivalenceClass, ClassSet> ClassToDisEqSet : Disequalities) {
3425 EquivalenceClass
Class = ClassToDisEqSet.first;
3426 ClassSet DisequalClasses = ClassToDisEqSet.second;
3427 EqClassesStrTy MembersStr;
3428 for (EquivalenceClass DisEqClass : DisequalClasses)
3429 MembersStr.insert(
toString(State, DisEqClass));
3430 DisequalityInfoStr.insert({
toString(State,
Class), MembersStr});
3435 bool FirstClass =
true;
3436 for (std::pair<std::string, EqClassesStrTy> ClassToDisEqSet :
3437 DisequalityInfoStr) {
3438 const std::string &
Class = ClassToDisEqSet.first;
3445 Indent(Out, Space, IsDot) <<
"{" << NL;
3446 unsigned int DisEqSpace = Space + 1;
3447 Indent(Out, DisEqSpace, IsDot) <<
"\"class\": ";
3449 const EqClassesStrTy &DisequalClasses = ClassToDisEqSet.second;
3450 if (!DisequalClasses.empty()) {
3452 Indent(Out, DisEqSpace, IsDot) <<
"\"disequal_to\": [" << NL;
3453 unsigned int DisEqClassSpace = DisEqSpace + 1;
3454 Indent(Out, DisEqClassSpace, IsDot);
3455 bool FirstDisEqClass =
true;
3456 for (
const std::string &DisEqClass : DisequalClasses) {
3457 if (FirstDisEqClass) {
3458 FirstDisEqClass =
false;
3461 Indent(Out, DisEqClassSpace, IsDot);
3467 Indent(Out, Space, IsDot) <<
"}";
3472 Indent(Out, Space, IsDot) <<
"]," << NL;
static bool isTrivial(ASTContext &Ctx, const Expr *E)
Checks if the expression is constant or does not have non-trivial function calls.
static void dump(llvm::raw_ostream &OS, StringRef FunctionName, ArrayRef< CounterExpression > Expressions, ArrayRef< CounterMappingRegion > Regions)
llvm::MachO::SymbolSet SymbolSet
#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,...
#define CONSTRAINT_DISPATCH(Id)
static void swapIterators(T &First, T &FirstEnd, T &Second, T &SecondEnd)
static ProgramStateRef reAssume(ProgramStateRef State, const RangeSet *Constraint, SVal TheValue)
#define DEFAULT_ASSIGN(Id)
static std::string toString(const clang::SanitizerSet &Sanitizers)
Produce a string containing comma-separated names of sanitizers in Sanitizers set.
static CharSourceRange getRange(const CharSourceRange &EditRange, const SourceManager &SM, const LangOptions &LangOpts, bool IncludeMacroExpansion)
static BinaryOperatorKind getOpFromIndex(size_t Index)
constexpr size_t getCmpOpCount() const
TriStateKind getCmpOpState(BinaryOperatorKind CurrentOP, BinaryOperatorKind QueriedOP) const
TriStateKind getCmpOpStateForUnknownX2(BinaryOperatorKind CurrentOP) const
bool isComparisonOp() const
bool isRelationalOp() const
static Opcode negateComparisonOp(Opcode Opc)
static Opcode reverseComparisonOp(Opcode Opc)
bool isEqualityOp() const
A (possibly-)qualified type.
The base class of the type hierarchy.
bool isSignedIntegerOrEnumerationType() const
Determines whether this is an integer type that is signed or an enumeration types whose underlying ty...
bool isUnsignedIntegerOrEnumerationType() const
Determines whether this is an integer type that is unsigned or an enumeration types whose underlying ...
bool isReferenceType() const
bool isIntegralOrEnumerationType() const
Determine whether this type is an integral or enumeration type.
A record of the "type" of an APSInt, used for conversions.
llvm::APSInt getZeroValue() const LLVM_READONLY
Returns an all-zero value for this type.
RangeTestResultKind
Used to classify whether a value is representable using this type.
@ RTR_Within
Value is representable using this type.
@ RTR_Below
Value is less than the minimum representable value.
@ RTR_Above
Value is greater than the maximum representable value.
uint32_t getBitWidth() const
RangeTestResultKind testInRange(const llvm::APSInt &Val, bool AllowMixedSign) const LLVM_READONLY
Tests whether a given value is losslessly representable using this type.
void apply(llvm::APSInt &Value) const
Convert a given APSInt, in place, to match this type.
llvm::APSInt getMinValue() const LLVM_READONLY
Returns the minimum value for this type.
llvm::APSInt convert(const llvm::APSInt &Value) const LLVM_READONLY
Convert and return a new APSInt with the given value, but this type's bit width and signedness.
llvm::APSInt getValue(uint64_t RawValue) const LLVM_READONLY
APSIntType getAPSIntType(QualType T) const
Returns the type of the APSInt used to store values of the given QualType.
Template implementation for all binary symbolic expressions.
QualType getType() const override
BinaryOperator::Opcode getOpcode() const
static bool isLocType(QualType T)
SValBuilder & getSValBuilder()
RangeSet unite(RangeSet LHS, RangeSet RHS)
Create a new set which is a union of two given ranges.
RangeSet negate(RangeSet What)
Negate the given range set.
RangeSet intersect(RangeSet LHS, RangeSet RHS)
Intersect the given range sets.
RangeSet deletePoint(RangeSet From, const llvm::APSInt &Point)
Delete the given point from the range set.
RangeSet getRangeSet(Range Origin)
Create a new set with just one range.
RangeSet add(RangeSet LHS, RangeSet RHS)
Create a new set with all ranges from both LHS and RHS.
RangeSet castTo(RangeSet What, APSIntType Ty)
Performs promotions, truncations and conversions of the given set.
persistent set of non-overlapping ranges.
const_iterator end() const
APSIntType getAPSIntType() const
const llvm::APSInt & getMaxValue() const
Get the maximal value covered by the ranges in the set.
bool encodesTrueRange() const
Test if the range doesn't contain zero.
bool encodesFalseRange() const
Test if the range is the [0,0] range.
const_iterator begin() const
const llvm::APSInt & getMinValue() const
Get the minimal value covered by the ranges in the set.
ImplType::const_iterator const_iterator
bool contains(llvm::APSInt Point) const
Test whether the given point is contained by any of the ranges.
void dump(raw_ostream &OS) const
bool containsZero() const
uint32_t getBitWidth() const
const llvm::APSInt * getConcreteValue() const
getConcreteValue - If a symbol is constrained to equal a specific integer constant then this method r...
A Range represents the closed range [from, to].
const llvm::APSInt & From() const
void dump(raw_ostream &OS) const
bool Includes(const llvm::APSInt &Point) const
const llvm::APSInt & To() const
SVal - This represents a symbolic expression, which can be either an L-value or an R-value.
SymbolRef getAsSymbol(bool IncludeBaseRegions=false) const
If this SVal wraps a symbol return that SymbolRef.
std::optional< T > getAs() const
Convert to the specified SVal type, returning std::nullopt if this SVal is not of the desired type.
T castAs() const
Convert to the specified SVal type, asserting that this SVal is of the desired type.
SymExprVisitor - this class implements a simple visitor for SymExpr subclasses.
virtual void dumpToStream(raw_ostream &os) const
virtual QualType getType() const =0
const SymExprT * acquire(Args &&...args)
Create or retrieve a SymExpr of type SymExprT for the given arguments.
A class responsible for cleaning up unused symbols.
bool isDead(SymbolRef sym)
Returns whether or not a symbol has been confirmed dead.
Represents a symbolic expression involving a unary operator.
QualType getType() const override
UnaryOperator::Opcode getOpcode() const
const SymExpr * getOperand() const
Value representing integer constant.
Represents symbolic expression that isn't a location.
SVal simplifyToSVal(ProgramStateRef State, SymbolRef Sym)
Try to simplify a given symbolic expression's associated SVal based on the constraints in State.
llvm::ImmutableMap< SymbolRef, RangeSet > ConstraintMap
SymbolRef simplify(ProgramStateRef State, SymbolRef Sym)
Try to simplify a given symbolic expression based on the constraints in State.
@ OS
Indicates that the tracking object is a descendant of a referenced-counted OSObject,...
@ CF
Indicates that the tracked object is a CF object.
std::unique_ptr< ConstraintManager > CreateRangeConstraintManager(ProgramStateManager &statemgr, ExprEngine *exprengine)
ConstraintMap getConstraintMap(ProgramStateRef State)
bool Zero(InterpState &S, CodePtr OpPC)
bool Const(InterpState &S, CodePtr OpPC, const T &Arg)
The JSON file list parser is used to communicate input to InstallAPI.
bool operator==(const CallGraphNode::CallRecord &LHS, const CallGraphNode::CallRecord &RHS)
bool operator<(DeclarationName LHS, DeclarationName RHS)
Ordering on two declaration names.
@ Result
The result type of a method or function.
bool operator!=(CanQual< T > x, CanQual< U > y)
const FunctionProtoType * T
@ Class
The "class" keyword introduces the elaborated-type-specifier.
@ Other
Other implicit parameter.
__UINTPTR_TYPE__ uintptr_t
An unsigned integer type with the property that any valid pointer to void can be converted to this ty...