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));
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,
930 [[nodiscard]]
inline SymbolSet getClassMembers(
ProgramStateRef State)
const;
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;
999 bool operator==(
const EquivalenceClass &Other)
const {
1002 bool operator<(
const EquivalenceClass &Other)
const {
return ID <
Other.ID; }
1003 bool operator!=(
const EquivalenceClass &Other)
const {
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);
1028 SymbolSet Members, EquivalenceClass Other,
1029 SymbolSet OtherMembers);
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) {
1811 Max = std::min(LHS.
To(), Max);
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;
1882 void printJson(raw_ostream &Out,
ProgramStateRef State,
const char *NL =
"\n",
1883 unsigned int Space = 0,
bool IsDot =
false)
const override;
1887 const char *NL =
"\n",
unsigned int Space = 0,
1888 bool IsDot =
false)
const;
1890 const char *NL =
"\n",
unsigned int Space = 0,
1891 bool IsDot =
false)
const;
1893 const char *NL =
"\n",
unsigned int Space = 0,
1894 bool IsDot =
false)
const;
1901 const llvm::APSInt &
V,
1902 const llvm::APSInt &Adjustment)
override;
1905 const llvm::APSInt &
V,
1906 const llvm::APSInt &Adjustment)
override;
1909 const llvm::APSInt &
V,
1910 const llvm::APSInt &Adjustment)
override;
1913 const llvm::APSInt &
V,
1914 const llvm::APSInt &Adjustment)
override;
1917 const llvm::APSInt &
V,
1918 const llvm::APSInt &Adjustment)
override;
1921 const llvm::APSInt &
V,
1922 const llvm::APSInt &Adjustment)
override;
1926 const llvm::APSInt &To,
const llvm::APSInt &Adjustment)
override;
1930 const llvm::APSInt &To,
const llvm::APSInt &Adjustment)
override;
1943 const llvm::APSInt &Int,
1944 const llvm::APSInt &Adjustment);
1946 const llvm::APSInt &Int,
1947 const llvm::APSInt &Adjustment);
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);
1977template <
class Derived>
class ConstraintAssignorBase {
1979 using Const =
const llvm::APSInt &;
1981#define DISPATCH(CLASS) return assign##CLASS##Impl(cast<CLASS>(Sym), Constraint)
1983#define ASSIGN(CLASS, TO, SYM, CONSTRAINT) \
1984 if (!static_cast<Derived *>(this)->assign##CLASS##To##TO(SYM, CONSTRAINT)) \
1988 assignImpl(Sym, Constraint);
1993#define SYMBOL(Id, Parent) \
1994 case SymExpr::Id##Kind: \
1996#include "clang/StaticAnalyzer/Core/PathSensitive/Symbols.def"
1998 llvm_unreachable(
"Unknown SymExpr kind!");
2001#define DEFAULT_ASSIGN(Id) \
2002 bool assign##Id##To##RangeSet(const Id *Sym, RangeSet Constraint) { \
2005 bool assign##Id##To##Range(const Id *Sym, Range Constraint) { return true; } \
2006 bool assign##Id##To##Const(const Id *Sym, Const Constraint) { return true; }
2012#define CONSTRAINT_DISPATCH(Id) \
2013 if (const llvm::APSInt *Const = Constraint.getConcreteValue()) { \
2014 ASSIGN(Id, Const, Sym, *Const); \
2016 if (Constraint.size() == 1) { \
2017 ASSIGN(Id, Range, Sym, *Constraint.begin()); \
2019 ASSIGN(Id, RangeSet, Sym, Constraint)
2024#define SYMBOL(Id, Parent) \
2025 bool assign##Id##Impl(const Id *Sym, RangeSet Constraint) { \
2026 CONSTRAINT_DISPATCH(Id); \
2030#define ABSTRACT_SYMBOL(Id, Parent) SYMBOL(Id, Parent)
2031#include "clang/StaticAnalyzer/Core/PathSensitive/Symbols.def"
2041#undef CONSTRAINT_DISPATCH
2042#undef DEFAULT_ASSIGN
2057class ConstraintAssignor :
public ConstraintAssignorBase<ConstraintAssignor> {
2059 template <
class ClassOrSymbol>
2062 ClassOrSymbol CoS,
RangeSet NewConstraint) {
2063 if (!State || NewConstraint.
isEmpty())
2066 ConstraintAssignor Assignor{State, Builder, F};
2067 return Assignor.assign(CoS, NewConstraint);
2071 template <
typename SymT>
2072 bool handleRemainderOp(
const SymT *Sym,
RangeSet Constraint) {
2073 if (Sym->getOpcode() != BO_Rem)
2077 SVal SymSVal = Builder.makeSymbolVal(Sym->getLHS());
2079 State = State->assume(*NonLocSymSVal,
true);
2087 inline bool assignSymExprToConst(
const SymExpr *Sym, Const Constraint);
2088 inline bool assignSymIntExprToRangeSet(
const SymIntExpr *Sym,
2090 return handleRemainderOp(Sym, Constraint);
2092 inline bool assignSymSymExprToRangeSet(
const SymSymExpr *Sym,
2098 : State(State), Builder(Builder), RangeFactory(F) {}
2099 using Base = ConstraintAssignorBase<ConstraintAssignor>;
2105 State = assign(EquivalenceClass::find(State, Sym), NewConstraint);
2111 Base::assign(Sym, NewConstraint);
2125 ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2126 ConstraintRangeTy::Factory &
CF = State->get_context<ConstraintRange>();
2129 Constraints =
CF.add(Constraints, Class, NewConstraint);
2131 for (EquivalenceClass DisequalClass :
Class.getDisequalClasses(State)) {
2132 RangeSet UpdatedConstraint = SymbolicRangeInferrer::inferRange(
2133 RangeFactory, State, DisequalClass);
2135 UpdatedConstraint = RangeFactory.deletePoint(UpdatedConstraint, *Point);
2139 if (UpdatedConstraint.
isEmpty())
2142 Constraints =
CF.add(Constraints, DisequalClass, UpdatedConstraint);
2144 assert(areFeasible(Constraints) &&
"Constraint manager shouldn't produce "
2145 "a state with infeasible constraints");
2147 return setConstraints(State, Constraints);
2150 return setConstraint(State, Class, NewConstraint);
2155 return EquivalenceClass::markDisequal(RangeFactory, State, LHS, RHS);
2160 return EquivalenceClass::merge(RangeFactory, State, LHS, RHS);
2163 [[nodiscard]] std::optional<bool> interpreteAsBool(
RangeSet Constraint) {
2164 assert(!Constraint.
isEmpty() &&
"Empty ranges shouldn't get here");
2172 return std::nullopt;
2180bool ConstraintAssignor::assignSymExprToConst(
const SymExpr *Sym,
2181 const llvm::APSInt &Constraint) {
2182 llvm::SmallSet<EquivalenceClass, 4> SimplifiedClasses;
2184 ClassMembersTy Members = State->get<ClassMembers>();
2185 for (std::pair<EquivalenceClass, SymbolSet> ClassToSymbolSet : Members) {
2186 EquivalenceClass
Class = ClassToSymbolSet.first;
2187 State = EquivalenceClass::simplify(Builder, RangeFactory, State, Class);
2190 SimplifiedClasses.insert(Class);
2196 ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2197 for (std::pair<EquivalenceClass, RangeSet> ClassConstraint : Constraints) {
2198 EquivalenceClass
Class = ClassConstraint.first;
2199 if (SimplifiedClasses.count(Class))
2201 State = EquivalenceClass::simplify(Builder, RangeFactory, State, Class);
2208 DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>();
2209 for (std::pair<EquivalenceClass, ClassSet> DisequalityEntry :
2211 EquivalenceClass
Class = DisequalityEntry.first;
2212 ClassSet DisequalClasses = DisequalityEntry.second;
2213 State = EquivalenceClass::simplify(Builder, RangeFactory, State, Class);
2221bool ConstraintAssignor::assignSymSymExprToRangeSet(
const SymSymExpr *Sym,
2223 if (!handleRemainderOp(Sym, Constraint))
2226 std::optional<bool> ConstraintAsBool = interpreteAsBool(Constraint);
2228 if (!ConstraintAsBool)
2231 if (std::optional<bool> Equality = meansEquality(Sym)) {
2237 if (*Equality == *ConstraintAsBool) {
2238 State = trackEquality(State, Sym->
getLHS(), Sym->
getRHS());
2241 State = trackDisequality(State, Sym->
getLHS(), Sym->
getRHS());
2253std::unique_ptr<ConstraintManager>
2256 return std::make_unique<RangeConstraintManager>(Eng, StMgr.
getSValBuilder());
2260 ConstraintMap::Factory &F = State->get_context<
ConstraintMap>();
2263 ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2264 for (std::pair<EquivalenceClass, RangeSet> ClassConstraint : Constraints) {
2265 EquivalenceClass Class = ClassConstraint.first;
2266 SymbolSet ClassMembers = Class.getClassMembers(State);
2267 assert(!ClassMembers.isEmpty() &&
2268 "Class must always have at least one member!");
2270 SymbolRef Representative = *ClassMembers.begin();
2271 Result = F.add(
Result, Representative, ClassConstraint.second);
2281LLVM_DUMP_METHOD
void EquivalenceClass::dumpToStream(
ProgramStateRef State,
2282 raw_ostream &os)
const {
2283 SymbolSet ClassMembers = getClassMembers(State);
2284 for (
const SymbolRef &MemberSym : ClassMembers) {
2292 assert(State &&
"State should not be null");
2293 assert(Sym &&
"Symbol should not be null");
2295 if (
const EquivalenceClass *NontrivialClass = State->get<ClassMap>(Sym))
2296 return *NontrivialClass;
2306 EquivalenceClass FirstClass = find(State,
First);
2307 EquivalenceClass SecondClass = find(State, Second);
2309 return FirstClass.merge(F, State, SecondClass);
2314 EquivalenceClass Other) {
2330 if (getType() !=
Other.getType())
2333 SymbolSet Members = getClassMembers(State);
2334 SymbolSet OtherMembers =
Other.getClassMembers(State);
2339 if (Members.getHeight() >= OtherMembers.getHeight()) {
2340 return mergeImpl(F, State, Members, Other, OtherMembers);
2342 return Other.mergeImpl(F, State, OtherMembers, *
this, Members);
2349 EquivalenceClass Other, SymbolSet OtherMembers) {
2361 ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2362 ConstraintRangeTy::Factory &CRF = State->get_context<ConstraintRange>();
2369 if (std::optional<RangeSet> NewClassConstraint =
2370 intersect(RangeFactory, getConstraint(State, *
this),
2371 getConstraint(State, Other))) {
2377 if (NewClassConstraint->isEmpty())
2382 Constraints = CRF.remove(Constraints, Other);
2384 Constraints = CRF.add(Constraints, *
this, *NewClassConstraint);
2386 assert(areFeasible(Constraints) &&
"Constraint manager shouldn't produce "
2387 "a state with infeasible constraints");
2389 State = State->set<ConstraintRange>(Constraints);
2393 ClassMapTy Classes = State->get<ClassMap>();
2394 ClassMapTy::Factory &CMF = State->get_context<ClassMap>();
2396 ClassMembersTy Members = State->get<ClassMembers>();
2397 ClassMembersTy::Factory &MF = State->get_context<ClassMembers>();
2399 DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>();
2400 DisequalityMapTy::Factory &DF = State->get_context<DisequalityMap>();
2402 ClassSet::Factory &
CF = State->get_context<ClassSet>();
2403 SymbolSet::Factory &F = getMembersFactory(State);
2406 SymbolSet NewClassMembers = MyMembers;
2408 NewClassMembers = F.add(NewClassMembers, Sym);
2410 Classes = CMF.add(Classes, Sym, *
this);
2416 Members = MF.remove(Members, Other);
2418 Members = MF.add(Members, *
this, NewClassMembers);
2421 ClassSet DisequalToOther =
Other.getDisequalClasses(DisequalityInfo,
CF);
2424 if (DisequalToOther.contains(*
this))
2427 if (!DisequalToOther.isEmpty()) {
2428 ClassSet DisequalToThis = getDisequalClasses(DisequalityInfo,
CF);
2429 DisequalityInfo = DF.remove(DisequalityInfo, Other);
2431 for (EquivalenceClass DisequalClass : DisequalToOther) {
2432 DisequalToThis =
CF.add(DisequalToThis, DisequalClass);
2437 ClassSet OriginalSetLinkedToOther =
2438 *DisequalityInfo.lookup(DisequalClass);
2442 ClassSet NewSet =
CF.remove(OriginalSetLinkedToOther, Other);
2443 NewSet =
CF.add(NewSet, *
this);
2445 DisequalityInfo = DF.add(DisequalityInfo, DisequalClass, NewSet);
2448 DisequalityInfo = DF.add(DisequalityInfo, *
this, DisequalToThis);
2449 State = State->set<DisequalityMap>(DisequalityInfo);
2453 State = State->set<ClassMap>(Classes);
2454 State = State->set<ClassMembers>(Members);
2459inline SymbolSet::Factory &
2461 return State->get_context<SymbolSet>();
2464SymbolSet EquivalenceClass::getClassMembers(
ProgramStateRef State)
const {
2465 if (
const SymbolSet *Members = State->get<ClassMembers>(*
this))
2470 SymbolSet::Factory &F = getMembersFactory(State);
2471 return F.add(F.getEmptySet(), getRepresentativeSymbol());
2475 return State->get<ClassMembers>(*this) ==
nullptr;
2487 return markDisequal(RF, State, find(State,
First), find(State, Second));
2492 EquivalenceClass
First,
2493 EquivalenceClass Second) {
2494 return First.markDisequal(RF, State, Second);
2499 EquivalenceClass Other)
const {
2502 if (*
this == Other) {
2506 DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>();
2507 ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2511 if (!addToDisequalityInfo(DisequalityInfo, Constraints, RF, State, *
this,
2513 !addToDisequalityInfo(DisequalityInfo, Constraints, RF, State, Other,
2517 assert(areFeasible(Constraints) &&
"Constraint manager shouldn't produce "
2518 "a state with infeasible constraints");
2520 State = State->set<DisequalityMap>(DisequalityInfo);
2521 State = State->set<ConstraintRange>(Constraints);
2526inline bool EquivalenceClass::addToDisequalityInfo(
2527 DisequalityMapTy &Info, ConstraintRangeTy &Constraints,
2529 EquivalenceClass Second) {
2532 DisequalityMapTy::Factory &F = State->get_context<DisequalityMap>();
2533 ClassSet::Factory &
CF = State->get_context<ClassSet>();
2534 ConstraintRangeTy::Factory &CRF = State->get_context<ConstraintRange>();
2537 const ClassSet *CurrentSet = Info.lookup(
First);
2538 ClassSet NewSet = CurrentSet ? *CurrentSet :
CF.getEmptySet();
2539 NewSet =
CF.add(NewSet, Second);
2541 Info = F.add(Info,
First, NewSet);
2548 if (
const RangeSet *SecondConstraint = Constraints.lookup(Second))
2549 if (
const llvm::APSInt *Point = SecondConstraint->getConcreteValue()) {
2551 RangeSet FirstConstraint = SymbolicRangeInferrer::inferRange(
2552 RF, State,
First.getRepresentativeSymbol());
2554 FirstConstraint = RF.
deletePoint(FirstConstraint, *Point);
2558 if (FirstConstraint.
isEmpty())
2561 Constraints = CRF.add(Constraints,
First, FirstConstraint);
2567inline std::optional<bool> EquivalenceClass::areEqual(
ProgramStateRef State,
2570 return EquivalenceClass::areEqual(State, find(State, FirstSym),
2571 find(State, SecondSym));
2574inline std::optional<bool> EquivalenceClass::areEqual(
ProgramStateRef State,
2575 EquivalenceClass
First,
2576 EquivalenceClass Second) {
2578 if (
First == Second)
2583 ClassSet DisequalToFirst =
First.getDisequalClasses(State);
2584 if (DisequalToFirst.contains(Second))
2588 return std::nullopt;
2594 SymbolSet ClsMembers = getClassMembers(State);
2595 assert(ClsMembers.contains(Old));
2598 SymbolSet::Factory &F = getMembersFactory(State);
2599 ClassMembersTy::Factory &EMFactory = State->get_context<ClassMembers>();
2600 ClsMembers = F.remove(ClsMembers, Old);
2603 assert(!ClsMembers.isEmpty() &&
2604 "Class should have had at least two members before member removal");
2606 ClassMembersTy ClassMembersMap = State->get<ClassMembers>();
2607 ClassMembersMap = EMFactory.add(ClassMembersMap, *
this, ClsMembers);
2608 State = State->set<ClassMembers>(ClassMembersMap);
2611 ClassMapTy Classes = State->get<ClassMap>();
2612 ClassMapTy::Factory &CMF = State->get_context<ClassMap>();
2613 Classes = CMF.remove(Classes, Old);
2614 State = State->set<ClassMap>(Classes);
2629 return State->assume(DefinedVal,
false);
2634 State = State->assume(DefinedVal,
true);
2641 return State->assumeInclusiveRange(DefinedVal, Constraint->
getMinValue(),
2653 SymbolSet ClassMembers =
Class.getClassMembers(State);
2654 for (
const SymbolRef &MemberSym : ClassMembers) {
2662 const llvm::APSInt &SV = CI->getValue();
2663 const RangeSet *ClassConstraint = getConstraint(State, Class);
2665 if (ClassConstraint && !ClassConstraint->
contains(SV))
2669 if (SimplifiedMemberSym && MemberSym != SimplifiedMemberSym) {
2674 State = merge(F, State, MemberSym, SimplifiedMemberSym);
2678 if (OldState == State)
2694 State = find(State, MemberSym).removeMember(State, MemberSym);
2698 const RangeSet *ClassConstraint = getConstraint(State, Class);
2719 State =
reAssume(State, ClassConstraint, SimplifiedMemberVal);
2727inline ClassSet EquivalenceClass::getDisequalClasses(
ProgramStateRef State,
2729 return find(State, Sym).getDisequalClasses(State);
2734 return getDisequalClasses(State->get<DisequalityMap>(),
2735 State->get_context<ClassSet>());
2739EquivalenceClass::getDisequalClasses(DisequalityMapTy Map,
2740 ClassSet::Factory &Factory)
const {
2741 if (
const ClassSet *DisequalClasses = Map.lookup(*
this))
2742 return *DisequalClasses;
2744 return Factory.getEmptySet();
2748 ClassMembersTy Members = State->get<ClassMembers>();
2750 for (std::pair<EquivalenceClass, SymbolSet> ClassMembersPair : Members) {
2753 if (find(State,
Member) == ClassMembersPair.first) {
2761 DisequalityMapTy Disequalities = State->get<DisequalityMap>();
2762 for (std::pair<EquivalenceClass, ClassSet> DisequalityInfo : Disequalities) {
2763 EquivalenceClass
Class = DisequalityInfo.first;
2764 ClassSet DisequalClasses = DisequalityInfo.second;
2767 if (DisequalClasses.isEmpty())
2772 for (EquivalenceClass DisequalClass : DisequalClasses) {
2773 const ClassSet *DisequalToDisequalClasses =
2774 Disequalities.lookup(DisequalClass);
2777 if (!DisequalToDisequalClasses ||
2778 !DisequalToDisequalClasses->contains(Class))
2790bool RangeConstraintManager::canReasonAbout(
SVal X)
const {
2792 if (SymVal && SymVal->isExpression()) {
2793 const SymExpr *SE = SymVal->getSymbol();
2795 if (
const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) {
2796 switch (SIE->getOpcode()) {
2816 if (
const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) {
2838 const RangeSet *Ranges = getConstraint(State, Sym);
2860const llvm::APSInt *RangeConstraintManager::getSymVal(
ProgramStateRef St,
2862 const RangeSet *T = getConstraint(St, Sym);
2875 ClassMembersTy ClassMembersMap = State->get<ClassMembers>();
2876 ClassMembersTy NewClassMembersMap = ClassMembersMap;
2877 ClassMembersTy::Factory &EMFactory = State->get_context<ClassMembers>();
2878 SymbolSet::Factory &SetFactory = State->get_context<SymbolSet>();
2880 ConstraintRangeTy Constraints = State->get<ConstraintRange>();
2881 ConstraintRangeTy NewConstraints = Constraints;
2882 ConstraintRangeTy::Factory &ConstraintFactory =
2883 State->get_context<ConstraintRange>();
2885 ClassMapTy Map = State->get<ClassMap>();
2886 ClassMapTy NewMap = Map;
2887 ClassMapTy::Factory &ClassFactory = State->get_context<ClassMap>();
2889 DisequalityMapTy Disequalities = State->get<DisequalityMap>();
2890 DisequalityMapTy::Factory &DisequalityFactory =
2891 State->get_context<DisequalityMap>();
2892 ClassSet::Factory &ClassSetFactory = State->get_context<ClassSet>();
2894 bool ClassMapChanged =
false;
2895 bool MembersMapChanged =
false;
2896 bool ConstraintMapChanged =
false;
2897 bool DisequalitiesChanged =
false;
2899 auto removeDeadClass = [&](EquivalenceClass
Class) {
2901 Constraints = ConstraintFactory.remove(Constraints, Class);
2902 ConstraintMapChanged =
true;
2906 ClassSet DisequalClasses =
2907 Class.getDisequalClasses(Disequalities, ClassSetFactory);
2908 if (!DisequalClasses.isEmpty()) {
2909 for (EquivalenceClass DisequalClass : DisequalClasses) {
2910 ClassSet DisequalToDisequalSet =
2911 DisequalClass.getDisequalClasses(Disequalities, ClassSetFactory);
2914 assert(!DisequalToDisequalSet.isEmpty());
2915 ClassSet NewSet = ClassSetFactory.remove(DisequalToDisequalSet, Class);
2918 if (NewSet.isEmpty()) {
2920 DisequalityFactory.remove(Disequalities, DisequalClass);
2923 DisequalityFactory.add(Disequalities, DisequalClass, NewSet);
2927 Disequalities = DisequalityFactory.remove(Disequalities, Class);
2928 DisequalitiesChanged =
true;
2933 for (std::pair<EquivalenceClass, RangeSet> ClassConstraintPair :
2935 EquivalenceClass
Class = ClassConstraintPair.first;
2936 if (
Class.isTriviallyDead(State, SymReaper)) {
2938 removeDeadClass(Class);
2943 for (std::pair<SymbolRef, EquivalenceClass> SymbolClassPair : Map) {
2946 if (SymReaper.
isDead(Sym)) {
2947 ClassMapChanged =
true;
2948 NewMap = ClassFactory.remove(NewMap, Sym);
2954 for (std::pair<EquivalenceClass, SymbolSet> ClassMembersPair :
2956 EquivalenceClass
Class = ClassMembersPair.first;
2957 SymbolSet LiveMembers = ClassMembersPair.second;
2958 bool MembersChanged =
false;
2962 MembersChanged =
true;
2963 LiveMembers = SetFactory.remove(LiveMembers,
Member);
2968 if (!MembersChanged)
2971 MembersMapChanged =
true;
2973 if (LiveMembers.isEmpty()) {
2975 NewClassMembersMap = EMFactory.remove(NewClassMembersMap, Class);
2978 removeDeadClass(Class);
2981 NewClassMembersMap =
2982 EMFactory.add(NewClassMembersMap, Class, LiveMembers);
2989 if (ClassMapChanged)
2990 State = State->set<ClassMap>(NewMap);
2992 if (MembersMapChanged)
2993 State = State->set<ClassMembers>(NewClassMembersMap);
2995 if (ConstraintMapChanged)
2996 State = State->set<ConstraintRange>(Constraints);
2998 if (DisequalitiesChanged)
2999 State = State->set<DisequalityMap>(Disequalities);
3001 assert(EquivalenceClass::isClassDataConsistent(State));
3008 return SymbolicRangeInferrer::inferRange(F, State, Sym);
3014 return ConstraintAssignor::assign(State, getSValBuilder(), F, Sym,
Range);
3031 const llvm::APSInt &Int,
3032 const llvm::APSInt &Adjustment) {
3038 llvm::APSInt Point = AdjustmentType.convert(Int) - Adjustment;
3042 return setRange(St, Sym, New);
3047 const llvm::APSInt &Int,
3048 const llvm::APSInt &Adjustment) {
3055 llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment;
3059 return setRange(St, Sym, New);
3064 const llvm::APSInt &Int,
3065 const llvm::APSInt &Adjustment) {
3068 switch (AdjustmentType.testInRange(Int,
true)) {
3078 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
3079 llvm::APSInt Min = AdjustmentType.getMinValue();
3080 if (ComparisonVal == Min)
3083 llvm::APSInt Lower = Min - Adjustment;
3084 llvm::APSInt Upper = ComparisonVal - Adjustment;
3093 const llvm::APSInt &Int,
3094 const llvm::APSInt &Adjustment) {
3095 RangeSet New = getSymLTRange(St, Sym, Int, Adjustment);
3096 return setRange(St, Sym, New);
3101 const llvm::APSInt &Int,
3102 const llvm::APSInt &Adjustment) {
3105 switch (AdjustmentType.testInRange(Int,
true)) {
3115 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
3117 if (ComparisonVal == Max)
3120 llvm::APSInt Lower = ComparisonVal - Adjustment;
3121 llvm::APSInt Upper = Max - Adjustment;
3125 return F.
intersect(SymRange, Lower, Upper);
3130 const llvm::APSInt &Int,
3131 const llvm::APSInt &Adjustment) {
3132 RangeSet New = getSymGTRange(St, Sym, Int, Adjustment);
3133 return setRange(St, Sym, New);
3138 const llvm::APSInt &Int,
3139 const llvm::APSInt &Adjustment) {
3142 switch (AdjustmentType.testInRange(Int,
true)) {
3152 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
3154 if (ComparisonVal == Min)
3157 llvm::APSInt Max = AdjustmentType.getMaxValue();
3158 llvm::APSInt Lower = ComparisonVal - Adjustment;
3159 llvm::APSInt Upper = Max - Adjustment;
3162 return F.
intersect(SymRange, Lower, Upper);
3167 const llvm::APSInt &Int,
3168 const llvm::APSInt &Adjustment) {
3169 RangeSet New = getSymGERange(St, Sym, Int, Adjustment);
3170 return setRange(St, Sym, New);
3174RangeConstraintManager::getSymLERange(llvm::function_ref<
RangeSet()> RS,
3175 const llvm::APSInt &Int,
3176 const llvm::APSInt &Adjustment) {
3179 switch (AdjustmentType.testInRange(Int,
true)) {
3189 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
3190 llvm::APSInt Max = AdjustmentType.getMaxValue();
3191 if (ComparisonVal == Max)
3194 llvm::APSInt Min = AdjustmentType.getMinValue();
3195 llvm::APSInt Lower = Min - Adjustment;
3196 llvm::APSInt Upper = ComparisonVal - Adjustment;
3204 const llvm::APSInt &Int,
3205 const llvm::APSInt &Adjustment) {
3206 return getSymLERange([&] {
return getRange(St, Sym); }, Int, Adjustment);
3211 const llvm::APSInt &Int,
3212 const llvm::APSInt &Adjustment) {
3213 RangeSet New = getSymLERange(St, Sym, Int, Adjustment);
3214 return setRange(St, Sym, New);
3219 const llvm::APSInt &To,
const llvm::APSInt &Adjustment) {
3220 RangeSet New = getSymGERange(State, Sym, From, Adjustment);
3223 RangeSet Out = getSymLERange([&] {
return New; }, To, Adjustment);
3224 return setRange(State, Sym, Out);
3227ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange(
3229 const llvm::APSInt &To,
const llvm::APSInt &Adjustment) {
3230 RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment);
3231 RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment);
3233 return setRange(State, Sym, New);
3240void RangeConstraintManager::printJson(raw_ostream &Out,
ProgramStateRef State,
3241 const char *NL,
unsigned int Space,
3243 printConstraints(Out, State, NL, Space, IsDot);
3244 printEquivalenceClasses(Out, State, NL, Space, IsDot);
3245 printDisequalities(Out, State, NL, Space, IsDot);
3248void RangeConstraintManager::printValue(raw_ostream &Out,
ProgramStateRef State,
3257 llvm::raw_string_ostream O(S);
3262void RangeConstraintManager::printConstraints(raw_ostream &Out,
3267 ConstraintRangeTy Constraints = State->get<ConstraintRange>();
3269 Indent(Out, Space, IsDot) <<
"\"constraints\": ";
3270 if (Constraints.isEmpty()) {
3271 Out <<
"null," << NL;
3275 std::map<std::string, RangeSet> OrderedConstraints;
3276 for (std::pair<EquivalenceClass, RangeSet>
P : Constraints) {
3277 SymbolSet ClassMembers =
P.first.getClassMembers(State);
3278 for (
const SymbolRef &ClassMember : ClassMembers) {
3279 bool insertion_took_place;
3280 std::tie(std::ignore, insertion_took_place) =
3281 OrderedConstraints.insert({
toString(ClassMember),
P.second});
3282 assert(insertion_took_place &&
3283 "two symbols should not have the same dump");
3290 for (std::pair<std::string, RangeSet>
P : OrderedConstraints) {
3297 Indent(Out, Space, IsDot)
3298 <<
"{ \"symbol\": \"" <<
P.first <<
"\", \"range\": \"";
3305 Indent(Out, Space, IsDot) <<
"]," << NL;
3309 SymbolSet ClassMembers = Class.getClassMembers(State);
3311 ClassMembers.end());
3312 llvm::sort(ClassMembersSorted,
3317 bool FirstMember =
true;
3320 llvm::raw_string_ostream Out(Str);
3322 for (
SymbolRef ClassMember : ClassMembersSorted) {
3324 FirstMember =
false;
3327 Out <<
"\"" << ClassMember <<
"\"";
3333void RangeConstraintManager::printEquivalenceClasses(raw_ostream &Out,
3338 ClassMembersTy Members = State->get<ClassMembers>();
3340 Indent(Out, Space, IsDot) <<
"\"equivalence_classes\": ";
3341 if (Members.isEmpty()) {
3342 Out <<
"null," << NL;
3346 std::set<std::string> MembersStr;
3347 for (std::pair<EquivalenceClass, SymbolSet> ClassToSymbolSet : Members)
3348 MembersStr.insert(
toString(State, ClassToSymbolSet.first));
3352 bool FirstClass =
true;
3353 for (
const std::string &Str : MembersStr) {
3360 Indent(Out, Space, IsDot);
3366 Indent(Out, Space, IsDot) <<
"]," << NL;
3369void RangeConstraintManager::printDisequalities(raw_ostream &Out,
3374 DisequalityMapTy Disequalities = State->get<DisequalityMap>();
3376 Indent(Out, Space, IsDot) <<
"\"disequality_info\": ";
3377 if (Disequalities.isEmpty()) {
3378 Out <<
"null," << NL;
3384 using EqClassesStrTy = std::set<std::string>;
3385 using DisequalityInfoStrTy = std::map<std::string, EqClassesStrTy>;
3386 DisequalityInfoStrTy DisequalityInfoStr;
3387 for (std::pair<EquivalenceClass, ClassSet> ClassToDisEqSet : Disequalities) {
3388 EquivalenceClass
Class = ClassToDisEqSet.first;
3389 ClassSet DisequalClasses = ClassToDisEqSet.second;
3390 EqClassesStrTy MembersStr;
3391 for (EquivalenceClass DisEqClass : DisequalClasses)
3392 MembersStr.insert(
toString(State, DisEqClass));
3393 DisequalityInfoStr.insert({
toString(State, Class), MembersStr});
3398 bool FirstClass =
true;
3399 for (std::pair<std::string, EqClassesStrTy> ClassToDisEqSet :
3400 DisequalityInfoStr) {
3401 const std::string &
Class = ClassToDisEqSet.first;
3408 Indent(Out, Space, IsDot) <<
"{" << NL;
3409 unsigned int DisEqSpace = Space + 1;
3410 Indent(Out, DisEqSpace, IsDot) <<
"\"class\": ";
3412 const EqClassesStrTy &DisequalClasses = ClassToDisEqSet.second;
3413 if (!DisequalClasses.empty()) {
3415 Indent(Out, DisEqSpace, IsDot) <<
"\"disequal_to\": [" << NL;
3416 unsigned int DisEqClassSpace = DisEqSpace + 1;
3417 Indent(Out, DisEqClassSpace, IsDot);
3418 bool FirstDisEqClass =
true;
3419 for (
const std::string &DisEqClass : DisequalClasses) {
3420 if (FirstDisEqClass) {
3421 FirstDisEqClass =
false;
3424 Indent(Out, DisEqClassSpace, IsDot);
3430 Indent(Out, Space, IsDot) <<
"}";
3435 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)
#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)
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)
__UINTPTR_TYPE__ uintptr_t
An unsigned integer type with the property that any valid pointer to void can be converted to this ty...