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),
1255 getRangeForComparisonSymbol(SSE),
1258 getRangeForEqualities(SSE),
1260 VisitBinaryOperator(SSE));
1265 : ValueFactory(F.getValueFactory()), RangeFactory(F), State(S) {}
1272 return {RangeFactory, Val};
1285 return infer(DestType);
1289 return intersect(RangeFactory,
1292 getConstraint(State, Sym),
1298 RangeSet infer(EquivalenceClass Class) {
1299 if (
const RangeSet *AssociatedConstraint = getConstraint(State, Class))
1300 return *AssociatedConstraint;
1302 return infer(
Class.getType());
1309 RangeSet Result(RangeFactory, ValueFactory.getMinValue(T),
1310 ValueFactory.getMaxValue(T));
1314 return assumeNonZero(Result, T);
1319 template <
class BinarySymExprTy>
1320 RangeSet VisitBinaryOperator(
const BinarySymExprTy *Sym) {
1332 QualType ResultType = Sym->getType();
1333 return VisitBinaryOperator(inferAs(Sym->getLHS(), ResultType),
1335 inferAs(Sym->getRHS(), ResultType), ResultType);
1361 return std::nullopt;
1363 return Range(ValueFactory.Convert(To, Origin.
From()),
1364 ValueFactory.Convert(To, Origin.
To()));
1367 template <BinaryOperator::Opcode Op>
1371 Range CoarseLHS = fillGaps(LHS);
1372 Range CoarseRHS = fillGaps(RHS);
1374 APSIntType ResultType = ValueFactory.getAPSIntType(T);
1378 auto ConvertedCoarseLHS = convert(CoarseLHS, ResultType);
1379 auto ConvertedCoarseRHS = convert(CoarseRHS, ResultType);
1383 if (!ConvertedCoarseLHS || !ConvertedCoarseRHS) {
1387 return VisitBinaryOperator<Op>(*ConvertedCoarseLHS, *ConvertedCoarseRHS, T);
1390 template <BinaryOperator::Opcode Op>
1404 APSIntType RangeType = ValueFactory.getAPSIntType(T);
1407 return Range(ValueFactory.getMinValue(RangeType), Origin.
To());
1410 if (Origin.
From().isMinSignedValue()) {
1414 return {ValueFactory.getMinValue(RangeType),
1415 ValueFactory.getMaxValue(RangeType)};
1429 llvm::APSInt AbsMax = std::max(-Origin.
From(), Origin.
To());
1432 return {ValueFactory.getValue(-AbsMax), ValueFactory.getValue(AbsMax)};
1437 APSIntType IntType = ValueFactory.getAPSIntType(T);
1441 template <
typename ProduceNegatedSymFunc>
1442 std::optional<RangeSet> getRangeForNegatedExpr(ProduceNegatedSymFunc F,
1447 return std::nullopt;
1450 if (
const RangeSet *NegatedRange = getConstraint(State, NegatedSym))
1451 return RangeFactory.negate(*NegatedRange);
1453 return std::nullopt;
1456 std::optional<RangeSet> getRangeForNegatedUnarySym(
const UnarySymExpr *USE) {
1459 return getRangeForNegatedExpr(
1468 std::optional<RangeSet> getRangeForNegatedSymSym(
const SymSymExpr *SSE) {
1469 return getRangeForNegatedExpr(
1470 [SSE, State = this->State]() ->
SymbolRef {
1472 return State->getSymbolManager().getSymSymExpr(
1479 std::optional<RangeSet> getRangeForNegatedSym(
SymbolRef Sym) {
1480 return getRangeForNegatedExpr(
1481 [Sym, State = this->State]() {
1482 return State->getSymbolManager().getUnarySymExpr(Sym, UO_Minus,
1498 std::optional<RangeSet> getRangeForComparisonSymbol(
const SymSymExpr *SSE) {
1503 return std::nullopt;
1522 for (
size_t i = 0; i < CmpOpTable.getCmpOpCount(); ++i) {
1527 const RangeSet *QueriedRangeSet = getConstraint(State, SymSym);
1531 if (!QueriedRangeSet) {
1535 QueriedRangeSet = getConstraint(State, SymSym);
1538 if (!QueriedRangeSet || QueriedRangeSet->
isEmpty())
1542 const bool isInFalseBranch =
1543 ConcreteValue ? (*ConcreteValue == 0) :
false;
1548 if (isInFalseBranch)
1552 CmpOpTable.getCmpOpState(CurrentOP, QueriedOP);
1555 if (LastQueriedOpToUnknown != CurrentOP &&
1556 LastQueriedOpToUnknown != QueriedOP) {
1562 BranchState = CmpOpTable.getCmpOpStateForUnknownX2(CurrentOP);
1564 LastQueriedOpToUnknown = QueriedOP;
1573 return std::nullopt;
1576 std::optional<RangeSet> getRangeForEqualities(
const SymSymExpr *Sym) {
1577 std::optional<bool>
Equality = meansEquality(Sym);
1580 return std::nullopt;
1582 if (std::optional<bool> AreEqual =
1583 EquivalenceClass::areEqual(State, Sym->
getLHS(), Sym->
getRHS())) {
1587 if (*AreEqual == *Equality) {
1588 return getTrueRange(Sym->
getType());
1591 return getFalseRange(Sym->
getType());
1594 return std::nullopt;
1599 return assumeNonZero(TypeRange, T);
1603 const llvm::APSInt &
Zero = ValueFactory.getValue(0, T);
1604 return RangeSet(RangeFactory, Zero);
1623 if (intersect(RangeFactory, LHS, RHS).isEmpty())
1624 return getTrueRange(T);
1643 return getTrueRange(T);
1648 return getTrueRange(T);
1656 RangeSet CastedLHS = RangeFactory.castTo(LHS, CastingType);
1657 RangeSet CastedRHS = RangeFactory.castTo(RHS, CastingType);
1659 if (intersect(RangeFactory, CastedLHS, CastedRHS).isEmpty())
1660 return getTrueRange(T);
1670 APSIntType ResultType = ValueFactory.getAPSIntType(T);
1673 bool IsLHSPositiveOrZero = LHS.
From() >=
Zero;
1674 bool IsRHSPositiveOrZero = RHS.
From() >=
Zero;
1676 bool IsLHSNegative = LHS.
To() <
Zero;
1677 bool IsRHSNegative = RHS.
To() <
Zero;
1680 if ((IsLHSPositiveOrZero && IsRHSPositiveOrZero) ||
1681 (IsLHSNegative && IsRHSNegative)) {
1683 const llvm::APSInt &
Min = std::max(LHS.
From(), RHS.
From());
1696 const llvm::APSInt &
Max = IsLHSNegative
1697 ? ValueFactory.getValue(--Zero)
1698 : ValueFactory.getMaxValue(ResultType);
1700 return {RangeFactory, ValueFactory.getValue(
Min),
Max};
1704 if (IsLHSNegative || IsRHSNegative) {
1706 return {RangeFactory, ValueFactory.getMinValue(ResultType),
1707 ValueFactory.getValue(--Zero)};
1717 return assumeNonZero(DefaultRange, T);
1721 return DefaultRange;
1725RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_And>(
Range LHS,
1728 APSIntType ResultType = ValueFactory.getAPSIntType(T);
1731 bool IsLHSPositiveOrZero = LHS.
From() >=
Zero;
1732 bool IsRHSPositiveOrZero = RHS.
From() >=
Zero;
1734 bool IsLHSNegative = LHS.
To() <
Zero;
1735 bool IsRHSNegative = RHS.
To() <
Zero;
1738 if ((IsLHSPositiveOrZero && IsRHSPositiveOrZero) ||
1739 (IsLHSNegative && IsRHSNegative)) {
1741 const llvm::APSInt &
Max = std::min(LHS.
To(), RHS.
To());
1745 const llvm::APSInt &
Min = IsLHSNegative
1746 ? ValueFactory.getMinValue(ResultType)
1747 : ValueFactory.getValue(Zero);
1749 return {RangeFactory,
Min,
Max};
1753 if (IsLHSPositiveOrZero || IsRHSPositiveOrZero) {
1758 const llvm::APSInt &
Max = IsLHSPositiveOrZero ? LHS.
To() : RHS.
To();
1762 return {RangeFactory, ValueFactory.getValue(Zero),
1763 ValueFactory.getValue(
Max)};
1771RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Rem>(
Range LHS,
1774 llvm::APSInt
Zero = ValueFactory.getAPSIntType(T).getZeroValue();
1776 Range ConservativeRange = getSymmetricalRange(RHS, T);
1778 llvm::APSInt
Max = ConservativeRange.
To();
1779 llvm::APSInt
Min = ConservativeRange.
From();
1785 return RangeFactory.getEmptySet();
1798 if (
Min.isSigned()) {
1803 bool IsLHSPositiveOrZero = LHS.
From() >=
Zero;
1804 bool IsRHSPositiveOrZero = RHS.
From() >=
Zero;
1808 if (IsLHSPositiveOrZero && IsRHSPositiveOrZero) {
1824 return {RangeFactory, ValueFactory.getValue(
Min), ValueFactory.getValue(
Max)};
1833 return RangeFactory.getEmptySet();
1838 return VisitBinaryOperator<BO_NE>(LHS, RHS, T);
1840 return VisitBinaryOperator<BO_Or>(LHS, RHS, T);
1842 return VisitBinaryOperator<BO_And>(LHS, RHS, T);
1844 return VisitBinaryOperator<BO_Rem>(LHS, RHS, T);
1868 return S1->get<ConstraintRange>() == S2->get<ConstraintRange>() &&
1869 S1->get<ClassMap>() == S2->get<ClassMap>();
1872 bool canReasonAbout(
SVal X)
const override;
1888 void printJson(raw_ostream &Out,
ProgramStateRef State,
const char *NL =
"\n",
1889 unsigned int Space = 0,
bool IsDot =
false)
const override;
1893 const char *NL =
"\n",
unsigned int Space = 0,
1894 bool IsDot =
false)
const;
1896 const char *NL =
"\n",
unsigned int Space = 0,
1897 bool IsDot =
false)
const;
1899 const char *NL =
"\n",
unsigned int Space = 0,
1900 bool IsDot =
false)
const;
1907 const llvm::APSInt &
V,
1908 const llvm::APSInt &Adjustment)
override;
1911 const llvm::APSInt &
V,
1912 const llvm::APSInt &Adjustment)
override;
1915 const llvm::APSInt &
V,
1916 const llvm::APSInt &Adjustment)
override;
1919 const llvm::APSInt &
V,
1920 const llvm::APSInt &Adjustment)
override;
1923 const llvm::APSInt &
V,
1924 const llvm::APSInt &Adjustment)
override;
1927 const llvm::APSInt &
V,
1928 const llvm::APSInt &Adjustment)
override;
1932 const llvm::APSInt &To,
const llvm::APSInt &Adjustment)
override;
1936 const llvm::APSInt &To,
const llvm::APSInt &Adjustment)
override;
1949 const llvm::APSInt &Int,
1950 const llvm::APSInt &Adjustment);
1952 const llvm::APSInt &Int,
1953 const llvm::APSInt &Adjustment);
1955 const llvm::APSInt &Int,
1956 const llvm::APSInt &Adjustment);
1958 const llvm::APSInt &Int,
1959 const llvm::APSInt &Adjustment);
1961 const llvm::APSInt &Int,
1962 const llvm::APSInt &Adjustment);
1983template <
class Derived>
class ConstraintAssignorBase {
1985 using Const =
const llvm::APSInt &;
1987#define DISPATCH(CLASS) return assign##CLASS##Impl(cast<CLASS>(Sym), Constraint)
1989#define ASSIGN(CLASS, TO, SYM, CONSTRAINT) \
1990 if (!static_cast<Derived *>(this)->assign##CLASS##To##TO(SYM, CONSTRAINT)) \
1994 assignImpl(Sym, Constraint);
1999#define SYMBOL(Id, Parent) \
2000 case SymExpr::Id##Kind: \
2002#include "clang/StaticAnalyzer/Core/PathSensitive/Symbols.def"
2004 llvm_unreachable(
"Unknown SymExpr kind!");
2007#define DEFAULT_ASSIGN(Id) \
2008 bool assign##Id##To##RangeSet(const Id *Sym, RangeSet Constraint) { \
2011 bool assign##Id##To##Range(const Id *Sym, Range Constraint) { return true; } \
2012 bool assign##Id##To##Const(const Id *Sym, Const Constraint) { return true; }
2018#define CONSTRAINT_DISPATCH(Id) \
2019 if (const llvm::APSInt *Const = Constraint.getConcreteValue()) { \
2020 ASSIGN(Id, Const, Sym, *Const); \
2022 if (Constraint.size() == 1) { \
2023 ASSIGN(Id, Range, Sym, *Constraint.begin()); \
2025 ASSIGN(Id, RangeSet, Sym, Constraint)
2030#define SYMBOL(Id, Parent) \
2031 bool assign##Id##Impl(const Id *Sym, RangeSet Constraint) { \
2032 CONSTRAINT_DISPATCH(Id); \
2036#define ABSTRACT_SYMBOL(Id, Parent) SYMBOL(Id, Parent)
2037#include "clang/StaticAnalyzer/Core/PathSensitive/Symbols.def"
2047#undef CONSTRAINT_DISPATCH
2048#undef DEFAULT_ASSIGN
2063class ConstraintAssignor :
public ConstraintAssignorBase<ConstraintAssignor> {
2065 template <
class ClassOrSymbol>
2068 ClassOrSymbol CoS,
RangeSet NewConstraint) {
2069 if (!State || NewConstraint.
isEmpty())
2072 ConstraintAssignor Assignor{State, Builder, F};
2073 return Assignor.assign(CoS, NewConstraint);
2077 template <
typename SymT>
2078 bool handleRemainderOp(
const SymT *Sym,
RangeSet Constraint) {
2079 if (Sym->getOpcode() != BO_Rem)
2083 SVal SymSVal = Builder.makeSymbolVal(Sym->getLHS());
2085 State = State->assume(*NonLocSymSVal,
true);
2093 inline bool assignSymExprToConst(
const SymExpr *Sym, Const Constraint);
2094 inline bool assignSymIntExprToRangeSet(
const SymIntExpr *Sym,
2096 return handleRemainderOp(Sym, Constraint);
2098 inline bool assignSymSymExprToRangeSet(
const SymSymExpr *Sym,
2104 : State(State), Builder(Builder), RangeFactory(F) {}
2105 using Base = ConstraintAssignorBase<ConstraintAssignor>;
2111 State = assign(EquivalenceClass::find(State, Sym), NewConstraint);
2117 Base::assign(Sym, NewConstraint);
2131 ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2132 ConstraintRangeTy::Factory &
CF = State->get_context<ConstraintRange>();
2135 Constraints =
CF.add(Constraints, Class, NewConstraint);
2137 for (EquivalenceClass DisequalClass :
Class.getDisequalClasses(State)) {
2138 RangeSet UpdatedConstraint = SymbolicRangeInferrer::inferRange(
2139 RangeFactory, State, DisequalClass);
2141 UpdatedConstraint = RangeFactory.deletePoint(UpdatedConstraint, *Point);
2145 if (UpdatedConstraint.
isEmpty())
2148 Constraints =
CF.add(Constraints, DisequalClass, UpdatedConstraint);
2150 assert(areFeasible(Constraints) &&
"Constraint manager shouldn't produce "
2151 "a state with infeasible constraints");
2153 return setConstraints(State, Constraints);
2156 return setConstraint(State, Class, NewConstraint);
2161 return EquivalenceClass::markDisequal(RangeFactory, State, LHS, RHS);
2166 return EquivalenceClass::merge(RangeFactory, State, LHS, RHS);
2169 [[nodiscard]] std::optional<bool> interpreteAsBool(
RangeSet Constraint) {
2170 assert(!Constraint.
isEmpty() &&
"Empty ranges shouldn't get here");
2178 return std::nullopt;
2186bool ConstraintAssignor::assignSymExprToConst(
const SymExpr *Sym,
2187 const llvm::APSInt &Constraint) {
2188 llvm::SmallSet<EquivalenceClass, 4> SimplifiedClasses;
2190 ClassMembersTy Members = State->get<ClassMembers>();
2191 for (std::pair<EquivalenceClass, SymbolSet> ClassToSymbolSet : Members) {
2192 EquivalenceClass
Class = ClassToSymbolSet.first;
2193 State = EquivalenceClass::simplify(Builder, RangeFactory, State, Class);
2196 SimplifiedClasses.insert(Class);
2202 ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2203 for (std::pair<EquivalenceClass, RangeSet> ClassConstraint : Constraints) {
2204 EquivalenceClass
Class = ClassConstraint.first;
2205 if (SimplifiedClasses.count(Class))
2207 State = EquivalenceClass::simplify(Builder, RangeFactory, State, Class);
2214 DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>();
2215 for (std::pair<EquivalenceClass, ClassSet> DisequalityEntry :
2217 EquivalenceClass
Class = DisequalityEntry.first;
2218 ClassSet DisequalClasses = DisequalityEntry.second;
2219 State = EquivalenceClass::simplify(Builder, RangeFactory, State, Class);
2227bool ConstraintAssignor::assignSymSymExprToRangeSet(
const SymSymExpr *Sym,
2229 if (!handleRemainderOp(Sym, Constraint))
2232 std::optional<bool> ConstraintAsBool = interpreteAsBool(Constraint);
2234 if (!ConstraintAsBool)
2237 if (std::optional<bool> Equality = meansEquality(Sym)) {
2243 if (*Equality == *ConstraintAsBool) {
2244 State = trackEquality(State, Sym->
getLHS(), Sym->
getRHS());
2247 State = trackDisequality(State, Sym->
getLHS(), Sym->
getRHS());
2259std::unique_ptr<ConstraintManager>
2262 return std::make_unique<RangeConstraintManager>(Eng, StMgr.
getSValBuilder());
2266 ConstraintMap::Factory &F = State->get_context<
ConstraintMap>();
2269 ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2270 for (std::pair<EquivalenceClass, RangeSet> ClassConstraint : Constraints) {
2271 EquivalenceClass
Class = ClassConstraint.first;
2273 assert(!ClassMembers.isEmpty() &&
2274 "Class must always have at least one member!");
2276 SymbolRef Representative = *ClassMembers.begin();
2277 Result = F.add(
Result, Representative, ClassConstraint.second);
2287LLVM_DUMP_METHOD
void EquivalenceClass::dumpToStream(
ProgramStateRef State,
2288 raw_ostream &os)
const {
2289 SymbolSet ClassMembers = getClassMembers(State);
2290 for (
const SymbolRef &MemberSym : ClassMembers) {
2298 assert(State &&
"State should not be null");
2299 assert(Sym &&
"Symbol should not be null");
2301 if (
const EquivalenceClass *NontrivialClass = State->get<ClassMap>(Sym))
2302 return *NontrivialClass;
2312 EquivalenceClass FirstClass = find(State,
First);
2313 EquivalenceClass SecondClass = find(State, Second);
2315 return FirstClass.merge(F, State, SecondClass);
2320 EquivalenceClass
Other) {
2336 if (getType() !=
Other.getType())
2339 SymbolSet Members = getClassMembers(State);
2345 if (Members.getHeight() >= OtherMembers.getHeight()) {
2346 return mergeImpl(F, State, Members,
Other, OtherMembers);
2348 return Other.mergeImpl(F, State, OtherMembers, *
this, Members);
2367 ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2368 ConstraintRangeTy::Factory &CRF = State->get_context<ConstraintRange>();
2375 if (std::optional<RangeSet> NewClassConstraint =
2376 intersect(RangeFactory, getConstraint(State, *
this),
2377 getConstraint(State,
Other))) {
2383 if (NewClassConstraint->isEmpty())
2388 Constraints = CRF.remove(Constraints,
Other);
2390 Constraints = CRF.add(Constraints, *
this, *NewClassConstraint);
2392 assert(areFeasible(Constraints) &&
"Constraint manager shouldn't produce "
2393 "a state with infeasible constraints");
2395 State = State->set<ConstraintRange>(Constraints);
2399 ClassMapTy Classes = State->get<ClassMap>();
2400 ClassMapTy::Factory &CMF = State->get_context<ClassMap>();
2402 ClassMembersTy Members = State->get<ClassMembers>();
2403 ClassMembersTy::Factory &MF = State->get_context<ClassMembers>();
2405 DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>();
2406 DisequalityMapTy::Factory &DF = State->get_context<DisequalityMap>();
2408 ClassSet::Factory &
CF = State->get_context<ClassSet>();
2409 SymbolSet::Factory &F = getMembersFactory(State);
2414 NewClassMembers = F.add(NewClassMembers, Sym);
2416 Classes = CMF.add(Classes, Sym, *
this);
2422 Members = MF.remove(Members,
Other);
2424 Members = MF.add(Members, *
this, NewClassMembers);
2427 ClassSet DisequalToOther =
Other.getDisequalClasses(DisequalityInfo,
CF);
2430 if (DisequalToOther.contains(*
this))
2433 if (!DisequalToOther.isEmpty()) {
2434 ClassSet DisequalToThis = getDisequalClasses(DisequalityInfo,
CF);
2435 DisequalityInfo = DF.remove(DisequalityInfo,
Other);
2437 for (EquivalenceClass DisequalClass : DisequalToOther) {
2438 DisequalToThis =
CF.add(DisequalToThis, DisequalClass);
2443 ClassSet OriginalSetLinkedToOther =
2444 *DisequalityInfo.lookup(DisequalClass);
2448 ClassSet NewSet =
CF.remove(OriginalSetLinkedToOther,
Other);
2449 NewSet =
CF.add(NewSet, *
this);
2451 DisequalityInfo = DF.add(DisequalityInfo, DisequalClass, NewSet);
2454 DisequalityInfo = DF.add(DisequalityInfo, *
this, DisequalToThis);
2455 State = State->set<DisequalityMap>(DisequalityInfo);
2459 State = State->set<ClassMap>(Classes);
2460 State = State->set<ClassMembers>(Members);
2465inline SymbolSet::Factory &
2471 if (
const SymbolSet *Members = State->get<ClassMembers>(*
this))
2476 SymbolSet::Factory &F = getMembersFactory(State);
2477 return F.add(F.getEmptySet(), getRepresentativeSymbol());
2481 return State->get<ClassMembers>(*this) ==
nullptr;
2493 return markDisequal(RF, State, find(State,
First), find(State, Second));
2498 EquivalenceClass
First,
2499 EquivalenceClass Second) {
2500 return First.markDisequal(RF, State, Second);
2505 EquivalenceClass
Other)
const {
2508 if (*
this ==
Other) {
2512 DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>();
2513 ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2517 if (!addToDisequalityInfo(DisequalityInfo, Constraints, RF, State, *
this,
2519 !addToDisequalityInfo(DisequalityInfo, Constraints, RF, State,
Other,
2523 assert(areFeasible(Constraints) &&
"Constraint manager shouldn't produce "
2524 "a state with infeasible constraints");
2526 State = State->set<DisequalityMap>(DisequalityInfo);
2527 State = State->set<ConstraintRange>(Constraints);
2532inline bool EquivalenceClass::addToDisequalityInfo(
2533 DisequalityMapTy &Info, ConstraintRangeTy &Constraints,
2535 EquivalenceClass Second) {
2538 DisequalityMapTy::Factory &F = State->get_context<DisequalityMap>();
2539 ClassSet::Factory &
CF = State->get_context<ClassSet>();
2540 ConstraintRangeTy::Factory &CRF = State->get_context<ConstraintRange>();
2543 const ClassSet *CurrentSet = Info.lookup(
First);
2544 ClassSet NewSet = CurrentSet ? *CurrentSet :
CF.getEmptySet();
2545 NewSet =
CF.add(NewSet, Second);
2547 Info = F.add(Info,
First, NewSet);
2554 if (
const RangeSet *SecondConstraint = Constraints.lookup(Second))
2555 if (
const llvm::APSInt *Point = SecondConstraint->getConcreteValue()) {
2557 RangeSet FirstConstraint = SymbolicRangeInferrer::inferRange(
2558 RF, State,
First.getRepresentativeSymbol());
2560 FirstConstraint = RF.
deletePoint(FirstConstraint, *Point);
2564 if (FirstConstraint.
isEmpty())
2567 Constraints = CRF.add(Constraints,
First, FirstConstraint);
2573inline std::optional<bool> EquivalenceClass::areEqual(
ProgramStateRef State,
2576 return EquivalenceClass::areEqual(State, find(State, FirstSym),
2577 find(State, SecondSym));
2580inline std::optional<bool> EquivalenceClass::areEqual(
ProgramStateRef State,
2581 EquivalenceClass
First,
2582 EquivalenceClass Second) {
2584 if (
First == Second)
2589 ClassSet DisequalToFirst =
First.getDisequalClasses(State);
2590 if (DisequalToFirst.contains(Second))
2594 return std::nullopt;
2600 SymbolSet ClsMembers = getClassMembers(State);
2601 assert(ClsMembers.contains(Old));
2604 SymbolSet::Factory &F = getMembersFactory(State);
2605 ClassMembersTy::Factory &EMFactory = State->get_context<ClassMembers>();
2606 ClsMembers = F.remove(ClsMembers, Old);
2609 assert(!ClsMembers.isEmpty() &&
2610 "Class should have had at least two members before member removal");
2612 ClassMembersTy ClassMembersMap = State->get<ClassMembers>();
2613 ClassMembersMap = EMFactory.add(ClassMembersMap, *
this, ClsMembers);
2614 State = State->set<ClassMembers>(ClassMembersMap);
2617 ClassMapTy Classes = State->get<ClassMap>();
2618 ClassMapTy::Factory &CMF = State->get_context<ClassMap>();
2619 Classes = CMF.remove(Classes, Old);
2620 State = State->set<ClassMap>(Classes);
2635 return State->assume(DefinedVal,
false);
2640 State = State->assume(DefinedVal,
true);
2647 return State->assumeInclusiveRange(DefinedVal, Constraint->
getMinValue(),
2660 for (
const SymbolRef &MemberSym : ClassMembers) {
2668 const llvm::APSInt &SV = CI->getValue();
2669 const RangeSet *ClassConstraint = getConstraint(State,
Class);
2671 if (ClassConstraint && !ClassConstraint->
contains(SV))
2675 if (SimplifiedMemberSym && MemberSym != SimplifiedMemberSym) {
2680 State = merge(F, State, MemberSym, SimplifiedMemberSym);
2684 if (OldState == State)
2700 State = find(State, MemberSym).removeMember(State, MemberSym);
2704 const RangeSet *ClassConstraint = getConstraint(State,
Class);
2725 State =
reAssume(State, ClassConstraint, SimplifiedMemberVal);
2733inline ClassSet EquivalenceClass::getDisequalClasses(
ProgramStateRef State,
2735 return find(State, Sym).getDisequalClasses(State);
2740 return getDisequalClasses(State->get<DisequalityMap>(),
2741 State->get_context<ClassSet>());
2745EquivalenceClass::getDisequalClasses(DisequalityMapTy Map,
2746 ClassSet::Factory &Factory)
const {
2747 if (
const ClassSet *DisequalClasses = Map.lookup(*
this))
2748 return *DisequalClasses;
2750 return Factory.getEmptySet();
2754 ClassMembersTy Members = State->get<ClassMembers>();
2756 for (std::pair<EquivalenceClass, SymbolSet> ClassMembersPair : Members) {
2759 if (find(State,
Member) == ClassMembersPair.first) {
2767 DisequalityMapTy Disequalities = State->get<DisequalityMap>();
2768 for (std::pair<EquivalenceClass, ClassSet> DisequalityInfo : Disequalities) {
2769 EquivalenceClass
Class = DisequalityInfo.first;
2770 ClassSet DisequalClasses = DisequalityInfo.second;
2773 if (DisequalClasses.isEmpty())
2778 for (EquivalenceClass DisequalClass : DisequalClasses) {
2779 const ClassSet *DisequalToDisequalClasses =
2780 Disequalities.lookup(DisequalClass);
2783 if (!DisequalToDisequalClasses ||
2784 !DisequalToDisequalClasses->contains(
Class))
2796bool RangeConstraintManager::canReasonAbout(
SVal X)
const {
2798 if (SymVal && SymVal->isExpression()) {
2799 const SymExpr *SE = SymVal->getSymbol();
2801 if (
const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) {
2802 switch (SIE->getOpcode()) {
2822 if (
const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) {
2844 const RangeSet *Ranges = getConstraint(State, Sym);
2866const llvm::APSInt *RangeConstraintManager::getSymVal(
ProgramStateRef St,
2868 const RangeSet *T = getConstraint(St, Sym);
2872const llvm::APSInt *RangeConstraintManager::getSymMinVal(
ProgramStateRef St,
2874 const RangeSet *T = getConstraint(St, Sym);
2880const llvm::APSInt *RangeConstraintManager::getSymMaxVal(
ProgramStateRef St,
2882 const RangeSet *T = getConstraint(St, Sym);
2897 ClassMembersTy ClassMembersMap = State->get<ClassMembers>();
2898 ClassMembersTy NewClassMembersMap = ClassMembersMap;
2899 ClassMembersTy::Factory &EMFactory = State->get_context<ClassMembers>();
2900 SymbolSet::Factory &SetFactory = State->get_context<
SymbolSet>();
2902 ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2903 ConstraintRangeTy NewConstraints = Constraints;
2904 ConstraintRangeTy::Factory &ConstraintFactory =
2905 State->get_context<ConstraintRange>();
2907 ClassMapTy Map = State->get<ClassMap>();
2908 ClassMapTy NewMap = Map;
2909 ClassMapTy::Factory &ClassFactory = State->get_context<ClassMap>();
2911 DisequalityMapTy Disequalities = State->get<DisequalityMap>();
2912 DisequalityMapTy::Factory &DisequalityFactory =
2913 State->get_context<DisequalityMap>();
2914 ClassSet::Factory &ClassSetFactory = State->get_context<ClassSet>();
2916 bool ClassMapChanged =
false;
2917 bool MembersMapChanged =
false;
2918 bool ConstraintMapChanged =
false;
2919 bool DisequalitiesChanged =
false;
2921 auto removeDeadClass = [&](EquivalenceClass
Class) {
2923 Constraints = ConstraintFactory.remove(Constraints,
Class);
2924 ConstraintMapChanged =
true;
2928 ClassSet DisequalClasses =
2929 Class.getDisequalClasses(Disequalities, ClassSetFactory);
2930 if (!DisequalClasses.isEmpty()) {
2931 for (EquivalenceClass DisequalClass : DisequalClasses) {
2932 ClassSet DisequalToDisequalSet =
2933 DisequalClass.getDisequalClasses(Disequalities, ClassSetFactory);
2936 assert(!DisequalToDisequalSet.isEmpty());
2937 ClassSet NewSet = ClassSetFactory.remove(DisequalToDisequalSet,
Class);
2940 if (NewSet.isEmpty()) {
2942 DisequalityFactory.remove(Disequalities, DisequalClass);
2945 DisequalityFactory.add(Disequalities, DisequalClass, NewSet);
2949 Disequalities = DisequalityFactory.remove(Disequalities,
Class);
2950 DisequalitiesChanged =
true;
2955 for (std::pair<EquivalenceClass, RangeSet> ClassConstraintPair :
2957 EquivalenceClass
Class = ClassConstraintPair.first;
2958 if (
Class.isTriviallyDead(State, SymReaper)) {
2960 removeDeadClass(
Class);
2965 for (std::pair<SymbolRef, EquivalenceClass> SymbolClassPair : Map) {
2968 if (SymReaper.
isDead(Sym)) {
2969 ClassMapChanged =
true;
2970 NewMap = ClassFactory.remove(NewMap, Sym);
2976 for (std::pair<EquivalenceClass, SymbolSet> ClassMembersPair :
2978 EquivalenceClass
Class = ClassMembersPair.first;
2979 SymbolSet LiveMembers = ClassMembersPair.second;
2980 bool MembersChanged =
false;
2984 MembersChanged =
true;
2985 LiveMembers = SetFactory.remove(LiveMembers,
Member);
2990 if (!MembersChanged)
2993 MembersMapChanged =
true;
2995 if (LiveMembers.isEmpty()) {
2997 NewClassMembersMap = EMFactory.remove(NewClassMembersMap,
Class);
3000 removeDeadClass(
Class);
3003 NewClassMembersMap =
3004 EMFactory.add(NewClassMembersMap,
Class, LiveMembers);
3011 if (ClassMapChanged)
3012 State = State->set<ClassMap>(NewMap);
3014 if (MembersMapChanged)
3015 State = State->set<ClassMembers>(NewClassMembersMap);
3017 if (ConstraintMapChanged)
3018 State = State->set<ConstraintRange>(Constraints);
3020 if (DisequalitiesChanged)
3021 State = State->set<DisequalityMap>(Disequalities);
3023 assert(EquivalenceClass::isClassDataConsistent(State));
3030 return SymbolicRangeInferrer::inferRange(F, State, Sym);
3036 return ConstraintAssignor::assign(State, getSValBuilder(), F, Sym,
Range);
3053 const llvm::APSInt &Int,
3054 const llvm::APSInt &Adjustment) {
3060 llvm::APSInt Point = AdjustmentType.convert(Int) - Adjustment;
3064 return setRange(St, Sym, New);
3069 const llvm::APSInt &Int,
3070 const llvm::APSInt &Adjustment) {
3077 llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment;
3081 return setRange(St, Sym, New);
3086 const llvm::APSInt &Int,
3087 const llvm::APSInt &Adjustment) {
3090 switch (AdjustmentType.testInRange(Int,
true)) {
3100 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
3101 llvm::APSInt
Min = AdjustmentType.getMinValue();
3102 if (ComparisonVal ==
Min)
3105 llvm::APSInt Lower =
Min - Adjustment;
3106 llvm::APSInt Upper = ComparisonVal - Adjustment;
3115 const llvm::APSInt &Int,
3116 const llvm::APSInt &Adjustment) {
3117 RangeSet New = getSymLTRange(St, Sym, Int, Adjustment);
3118 return setRange(St, Sym, New);
3123 const llvm::APSInt &Int,
3124 const llvm::APSInt &Adjustment) {
3127 switch (AdjustmentType.testInRange(Int,
true)) {
3137 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
3138 llvm::APSInt
Max = AdjustmentType.getMaxValue();
3139 if (ComparisonVal ==
Max)
3142 llvm::APSInt Lower = ComparisonVal - Adjustment;
3143 llvm::APSInt Upper =
Max - Adjustment;
3147 return F.
intersect(SymRange, Lower, Upper);
3152 const llvm::APSInt &Int,
3153 const llvm::APSInt &Adjustment) {
3154 RangeSet New = getSymGTRange(St, Sym, Int, Adjustment);
3155 return setRange(St, Sym, New);
3160 const llvm::APSInt &Int,
3161 const llvm::APSInt &Adjustment) {
3164 switch (AdjustmentType.testInRange(Int,
true)) {
3174 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
3175 llvm::APSInt
Min = AdjustmentType.getMinValue();
3176 if (ComparisonVal ==
Min)
3179 llvm::APSInt
Max = AdjustmentType.getMaxValue();
3180 llvm::APSInt Lower = ComparisonVal - Adjustment;
3181 llvm::APSInt Upper =
Max - Adjustment;
3184 return F.
intersect(SymRange, Lower, Upper);
3189 const llvm::APSInt &Int,
3190 const llvm::APSInt &Adjustment) {
3191 RangeSet New = getSymGERange(St, Sym, Int, Adjustment);
3192 return setRange(St, Sym, New);
3196RangeConstraintManager::getSymLERange(llvm::function_ref<
RangeSet()> RS,
3197 const llvm::APSInt &Int,
3198 const llvm::APSInt &Adjustment) {
3201 switch (AdjustmentType.testInRange(Int,
true)) {
3211 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
3212 llvm::APSInt
Max = AdjustmentType.getMaxValue();
3213 if (ComparisonVal ==
Max)
3216 llvm::APSInt
Min = AdjustmentType.getMinValue();
3217 llvm::APSInt Lower =
Min - Adjustment;
3218 llvm::APSInt Upper = ComparisonVal - Adjustment;
3226 const llvm::APSInt &Int,
3227 const llvm::APSInt &Adjustment) {
3228 return getSymLERange([&] {
return getRange(St, Sym); }, Int, Adjustment);
3233 const llvm::APSInt &Int,
3234 const llvm::APSInt &Adjustment) {
3235 RangeSet New = getSymLERange(St, Sym, Int, Adjustment);
3236 return setRange(St, Sym, New);
3241 const llvm::APSInt &To,
const llvm::APSInt &Adjustment) {
3242 RangeSet New = getSymGERange(State, Sym, From, Adjustment);
3245 RangeSet Out = getSymLERange([&] {
return New; }, To, Adjustment);
3246 return setRange(State, Sym, Out);
3249ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange(
3251 const llvm::APSInt &To,
const llvm::APSInt &Adjustment) {
3252 RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment);
3253 RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment);
3255 return setRange(State, Sym, New);
3262void RangeConstraintManager::printJson(raw_ostream &Out,
ProgramStateRef State,
3263 const char *NL,
unsigned int Space,
3265 printConstraints(Out, State, NL, Space, IsDot);
3266 printEquivalenceClasses(Out, State, NL, Space, IsDot);
3267 printDisequalities(Out, State, NL, Space, IsDot);
3270void RangeConstraintManager::printValue(raw_ostream &Out,
ProgramStateRef State,
3274 Out <<
"<empty rangeset>";
3283 llvm::raw_string_ostream O(S);
3288void RangeConstraintManager::printConstraints(raw_ostream &Out,
3293 ConstraintRangeTy Constraints = State->get<ConstraintRange>();
3295 Indent(Out, Space, IsDot) <<
"\"constraints\": ";
3296 if (Constraints.isEmpty()) {
3297 Out <<
"null," << NL;
3301 std::map<std::string, RangeSet> OrderedConstraints;
3302 for (std::pair<EquivalenceClass, RangeSet>
P : Constraints) {
3303 SymbolSet ClassMembers =
P.first.getClassMembers(State);
3304 for (
const SymbolRef &ClassMember : ClassMembers) {
3305 bool insertion_took_place;
3306 std::tie(std::ignore, insertion_took_place) =
3307 OrderedConstraints.insert({
toString(ClassMember),
P.second});
3308 assert(insertion_took_place &&
3309 "two symbols should not have the same dump");
3316 for (std::pair<std::string, RangeSet>
P : OrderedConstraints) {
3323 Indent(Out, Space, IsDot)
3324 <<
"{ \"symbol\": \"" <<
P.first <<
"\", \"range\": \"";
3331 Indent(Out, Space, IsDot) <<
"]," << NL;
3337 ClassMembers.end());
3338 llvm::sort(ClassMembersSorted,
3343 bool FirstMember =
true;
3346 llvm::raw_string_ostream Out(Str);
3348 for (
SymbolRef ClassMember : ClassMembersSorted) {
3350 FirstMember =
false;
3353 Out <<
"\"" << ClassMember <<
"\"";
3359void RangeConstraintManager::printEquivalenceClasses(raw_ostream &Out,
3364 ClassMembersTy Members = State->get<ClassMembers>();
3366 Indent(Out, Space, IsDot) <<
"\"equivalence_classes\": ";
3367 if (Members.isEmpty()) {
3368 Out <<
"null," << NL;
3372 std::set<std::string> MembersStr;
3373 for (std::pair<EquivalenceClass, SymbolSet> ClassToSymbolSet : Members)
3374 MembersStr.insert(
toString(State, ClassToSymbolSet.first));
3378 bool FirstClass =
true;
3379 for (
const std::string &Str : MembersStr) {
3386 Indent(Out, Space, IsDot);
3392 Indent(Out, Space, IsDot) <<
"]," << NL;
3395void RangeConstraintManager::printDisequalities(raw_ostream &Out,
3400 DisequalityMapTy Disequalities = State->get<DisequalityMap>();
3402 Indent(Out, Space, IsDot) <<
"\"disequality_info\": ";
3403 if (Disequalities.isEmpty()) {
3404 Out <<
"null," << NL;
3410 using EqClassesStrTy = std::set<std::string>;
3411 using DisequalityInfoStrTy = std::map<std::string, EqClassesStrTy>;
3412 DisequalityInfoStrTy DisequalityInfoStr;
3413 for (std::pair<EquivalenceClass, ClassSet> ClassToDisEqSet : Disequalities) {
3414 EquivalenceClass
Class = ClassToDisEqSet.first;
3415 ClassSet DisequalClasses = ClassToDisEqSet.second;
3416 EqClassesStrTy MembersStr;
3417 for (EquivalenceClass DisEqClass : DisequalClasses)
3418 MembersStr.insert(
toString(State, DisEqClass));
3419 DisequalityInfoStr.insert({
toString(State,
Class), MembersStr});
3424 bool FirstClass =
true;
3425 for (std::pair<std::string, EqClassesStrTy> ClassToDisEqSet :
3426 DisequalityInfoStr) {
3427 const std::string &
Class = ClassToDisEqSet.first;
3434 Indent(Out, Space, IsDot) <<
"{" << NL;
3435 unsigned int DisEqSpace = Space + 1;
3436 Indent(Out, DisEqSpace, IsDot) <<
"\"class\": ";
3438 const EqClassesStrTy &DisequalClasses = ClassToDisEqSet.second;
3439 if (!DisequalClasses.empty()) {
3441 Indent(Out, DisEqSpace, IsDot) <<
"\"disequal_to\": [" << NL;
3442 unsigned int DisEqClassSpace = DisEqSpace + 1;
3443 Indent(Out, DisEqClassSpace, IsDot);
3444 bool FirstDisEqClass =
true;
3445 for (
const std::string &DisEqClass : DisequalClasses) {
3446 if (FirstDisEqClass) {
3447 FirstDisEqClass =
false;
3450 Indent(Out, DisEqClassSpace, IsDot);
3456 Indent(Out, Space, IsDot) <<
"}";
3461 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)
ProgramStateRef reAssume(ProgramStateRef State, const RangeSet *Constraint, SVal TheValue)
#define DEFAULT_ASSIGN(Id)
void swapIterators(T &First, T &FirstEnd, T &Second, T &SecondEnd)
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 SymSymExpr * getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs, QualType t)
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)
@ 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...