diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h @@ -126,6 +126,8 @@ RangeSet Intersect(BasicValueFactory &BV, Factory &F, const RangeSet &Other) const; RangeSet Negate(BasicValueFactory &BV, Factory &F) const; + RangeSet Delete(BasicValueFactory &BV, Factory &F, + const llvm::APSInt &Point) const; void print(raw_ostream &os) const; @@ -139,11 +141,10 @@ template <> struct ProgramStateTrait - : public ProgramStatePartialTrait { + : public ProgramStatePartialTrait { static void *GDMIndex(); }; - class RangedConstraintManager : public SimpleConstraintManager { public: RangedConstraintManager(ExprEngine *EE, SValBuilder &SB) @@ -169,8 +170,8 @@ protected: /// Assume a constraint between a symbolic expression and a concrete integer. virtual ProgramStateRef assumeSymRel(ProgramStateRef State, SymbolRef Sym, - BinaryOperator::Opcode op, - const llvm::APSInt &Int); + BinaryOperator::Opcode op, + const llvm::APSInt &Int); //===------------------------------------------------------------------===// // Interface that subclasses must implement. @@ -218,8 +219,7 @@ static void computeAdjustment(SymbolRef &Sym, llvm::APSInt &Adjustment); }; -} // end GR namespace - -} // end clang namespace +} // namespace ento +} // namespace clang #endif diff --git a/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp b/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp --- a/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp +++ b/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp @@ -89,7 +89,7 @@ } TriStateKind getCmpOpState(BinaryOperatorKind CurrentOP, - BinaryOperatorKind QueriedOP) const { + BinaryOperatorKind QueriedOP) const { return CmpOpTable[getIndexFromOp(CurrentOP)][getIndexFromOp(QueriedOP)]; } @@ -364,6 +364,18 @@ return newRanges; } +RangeSet RangeSet::Delete(BasicValueFactory &BV, Factory &F, + const llvm::APSInt &Point) const { + llvm::APSInt Upper = Point; + llvm::APSInt Lower = Point; + + ++Upper; + --Lower; + + // Notice that the lower bound is greater than the upper bound. + return Intersect(BV, F, Upper, Lower); +} + void RangeSet::print(raw_ostream &os) const { bool isFirst = true; os << "{ "; @@ -381,6 +393,107 @@ namespace { +//===----------------------------------------------------------------------===// +// Intersection functions +//===----------------------------------------------------------------------===// + +template +LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory &BV, + RangeSet::Factory &F, RangeSet Head, + SecondTy Second, RestTy... Tail); + +template struct IntersectionTraits; + +template struct IntersectionTraits { + // Found RangeSet, no need to check any further + using Type = RangeSet; +}; + +template <> struct IntersectionTraits<> { + // We ran out of types, and we didn't find any RangeSet, so the result should + // be optional. + using Type = Optional; +}; + +template +struct IntersectionTraits { + // If current type is Optional or a raw pointer, we should keep looking. + using Type = typename IntersectionTraits::Type; +}; + +template +LLVM_NODISCARD inline EndTy intersect(BasicValueFactory &BV, + RangeSet::Factory &F, EndTy End) { + // If the list contains only RangeSet or Optional, simply return + // that range set. + return End; +} + +LLVM_NODISCARD LLVM_ATTRIBUTE_UNUSED inline Optional +intersect(BasicValueFactory &BV, RangeSet::Factory &F, const RangeSet *End) { + // This is an extraneous conversion from a raw pointer into Optional + if (End) { + return *End; + } + return llvm::None; +} + +template +LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory &BV, + RangeSet::Factory &F, RangeSet Head, + RangeSet Second, RestTy... Tail) { + // Here we call either the or version + // of the function and can be sure that the result is RangeSet. + return intersect(BV, F, Head.Intersect(BV, F, Second), Tail...); +} + +template +LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory &BV, + RangeSet::Factory &F, RangeSet Head, + SecondTy Second, RestTy... Tail) { + if (Second) { + // Here we call the version of the function... + return intersect(BV, F, Head, *Second, Tail...); + } + // ...and here it is either or , which + // means that the result is definitely RangeSet. + return intersect(BV, F, Head, Tail...); +} + +/// Main generic intersect function. +/// It intersects all of the given range sets. If some of the given arguments +/// don't hold a range set (nullptr or llvm::None), the function will skip them. +/// +/// Available representations for the arguments are: +/// * RangeSet +/// * Optional +/// * RangeSet * +/// Pointer to a RangeSet is automatically assumed to be nullable and will get +/// checked as well as the optional version. If this behaviour is undesired, +/// please dereference the pointer in the call. +/// +/// Return type depends on the arguments' types. If we can be sure in compile +/// time that there will be a range set as a result, the returning type is +/// simply RangeSet, in other cases we have to back off to Optional. +/// +/// Please, prefer optional range sets to raw pointers. If the last argument is +/// a raw pointer and all previous arguments are None, it will cost one +/// additional check to convert RangeSet * into Optional. +template +LLVM_NODISCARD inline + typename IntersectionTraits::Type + intersect(BasicValueFactory &BV, RangeSet::Factory &F, HeadTy Head, + SecondTy Second, RestTy... Tail) { + if (Head) { + return intersect(BV, F, *Head, Second, Tail...); + } + return intersect(BV, F, Second, Tail...); +} + +//===----------------------------------------------------------------------===// +// Symbolic reasoning logic +//===----------------------------------------------------------------------===// + /// A little component aggregating all of the reasoning we have about /// the ranges of symbolic expressions. /// @@ -442,33 +555,22 @@ } RangeSet infer(SymbolRef Sym) { - const RangeSet *AssociatedRange = State->get(Sym); - - // If Sym is a difference of symbols A - B, then maybe we have range set - // stored for B - A. - const RangeSet *RangeAssociatedWithNegatedSym = - getRangeForMinusSymbol(State, Sym); - - // If we have range set stored for both A - B and B - A then calculate the - // effective range set by intersecting the range set for A - B and the - // negated range set of B - A. - if (AssociatedRange && RangeAssociatedWithNegatedSym) - return AssociatedRange->Intersect( - ValueFactory, RangeFactory, - RangeAssociatedWithNegatedSym->Negate(ValueFactory, RangeFactory)); - - if (AssociatedRange) - return *AssociatedRange; - - if (RangeAssociatedWithNegatedSym) - return RangeAssociatedWithNegatedSym->Negate(ValueFactory, RangeFactory); + if (Optional ConstraintBasedRange = intersect( + ValueFactory, RangeFactory, State->get(Sym), + // If Sym is a difference of symbols A - B, then maybe we have range + // set stored for B - A. + // + // If we have range set stored for both A - B and B - A then + // calculate the effective range set by intersecting the range set + // for A - B and the negated range set of B - A. + getRangeForNegatedSub(Sym))) + return *ConstraintBasedRange; // If Sym is a comparison expression (except <=>), // find any other comparisons with the same operands. // See function description. - const RangeSet CmpRangeSet = getRangeForComparisonSymbol(State, Sym); - if (!CmpRangeSet.isEmpty()) - return CmpRangeSet; + if (Optional CmpRangeSet = getRangeForComparisonSymbol(Sym)) + return *CmpRangeSet; return Visit(Sym); } @@ -621,8 +723,7 @@ /// Return a range set subtracting zero from \p Domain. RangeSet assumeNonZero(RangeSet Domain, QualType T) { APSIntType IntType = ValueFactory.getAPSIntType(T); - return Domain.Intersect(ValueFactory, RangeFactory, - ++IntType.getZeroValue(), --IntType.getZeroValue()); + return Domain.Delete(ValueFactory, RangeFactory, IntType.getZeroValue()); } // FIXME: Once SValBuilder supports unary minus, we should use SValBuilder to @@ -630,23 +731,27 @@ // symbol manually. This will allow us to support finding ranges of not // only negated SymSymExpr-type expressions, but also of other, simpler // expressions which we currently do not know how to negate. - const RangeSet *getRangeForMinusSymbol(ProgramStateRef State, SymbolRef Sym) { + Optional getRangeForNegatedSub(SymbolRef Sym) { if (const SymSymExpr *SSE = dyn_cast(Sym)) { if (SSE->getOpcode() == BO_Sub) { QualType T = Sym->getType(); + + // Do not negate unsigned ranges + if (!T->isUnsignedIntegerOrEnumerationType() && + !T->isSignedIntegerOrEnumerationType()) + return llvm::None; + SymbolManager &SymMgr = State->getSymbolManager(); - SymbolRef negSym = + SymbolRef NegatedSym = SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, SSE->getLHS(), T); - if (const RangeSet *negV = State->get(negSym)) { - // Unsigned range set cannot be negated, unless it is [0, 0]. - if (T->isUnsignedIntegerOrEnumerationType() || - T->isSignedIntegerOrEnumerationType()) - return negV; + if (const RangeSet *NegatedRange = + State->get(NegatedSym)) { + return NegatedRange->Negate(ValueFactory, RangeFactory); } } } - return nullptr; + return llvm::None; } // Returns ranges only for binary comparison operators (except <=>) @@ -659,18 +764,16 @@ // It covers all possible combinations (see CmpOpTable description). // Note that `x` and `y` can also stand for subexpressions, // not only for actual symbols. - RangeSet getRangeForComparisonSymbol(ProgramStateRef State, SymbolRef Sym) { - const RangeSet EmptyRangeSet = RangeFactory.getEmptySet(); - - auto SSE = dyn_cast(Sym); + Optional getRangeForComparisonSymbol(SymbolRef Sym) { + const auto *SSE = dyn_cast(Sym); if (!SSE) - return EmptyRangeSet; + return llvm::None; BinaryOperatorKind CurrentOP = SSE->getOpcode(); // We currently do not support <=> (C++20). if (!BinaryOperator::isComparisonOp(CurrentOP) || (CurrentOP == BO_Cmp)) - return EmptyRangeSet; + return llvm::None; static const OperatorRelationsTable CmpOpTable{}; @@ -679,10 +782,6 @@ QualType T = SSE->getType(); SymbolManager &SymMgr = State->getSymbolManager(); - const llvm::APSInt &Zero = ValueFactory.getValue(0, T); - const llvm::APSInt &One = ValueFactory.getValue(1, T); - const RangeSet TrueRangeSet(RangeFactory, One, One); - const RangeSet FalseRangeSet(RangeFactory, Zero, Zero); int UnknownStates = 0; @@ -732,11 +831,21 @@ continue; } - return (BranchState == OperatorRelationsTable::True) ? TrueRangeSet - : FalseRangeSet; + return (BranchState == OperatorRelationsTable::True) ? getTrueRange(T) + : getFalseRange(T); } - return EmptyRangeSet; + return llvm::None; + } + + RangeSet getTrueRange(QualType T) { + RangeSet TypeRange = infer(T); + return assumeNonZero(TypeRange, T); + } + + RangeSet getFalseRange(QualType T) { + const llvm::APSInt &Zero = ValueFactory.getValue(0, T); + return RangeSet(RangeFactory, Zero); } BasicValueFactory &ValueFactory; @@ -744,6 +853,10 @@ ProgramStateRef State; }; +//===----------------------------------------------------------------------===// +// Range-based reasoning about symbolic operations +//===----------------------------------------------------------------------===// + template <> RangeSet SymbolicRangeInferrer::VisitBinaryOperator(Range LHS, Range RHS, QualType T) { @@ -904,6 +1017,10 @@ return {RangeFactory, ValueFactory.getValue(Min), ValueFactory.getValue(Max)}; } +//===----------------------------------------------------------------------===// +// Constraint manager implementation details +//===----------------------------------------------------------------------===// + class RangeConstraintManager : public RangedConstraintManager { public: RangeConstraintManager(ExprEngine *EE, SValBuilder &SVB) @@ -997,6 +1114,10 @@ return std::make_unique(Eng, StMgr.getSValBuilder()); } +//===----------------------------------------------------------------------===// +// RangeConstraintManager implementation +//===----------------------------------------------------------------------===// + bool RangeConstraintManager::canReasonAbout(SVal X) const { Optional SymVal = X.getAs(); if (SymVal && SymVal->isExpression()) { @@ -1073,6 +1194,10 @@ return T ? T->getConcreteValue() : nullptr; } +//===----------------------------------------------------------------------===// +// Remove dead symbols from existing constraints +//===----------------------------------------------------------------------===// + /// Scan all symbols referenced by the constraints. If the symbol is not alive /// as marked in LSymbols, mark it as dead in DSymbols. ProgramStateRef @@ -1119,14 +1244,9 @@ if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within) return St; - llvm::APSInt Lower = AdjustmentType.convert(Int) - Adjustment; - llvm::APSInt Upper = Lower; - --Lower; - ++Upper; + llvm::APSInt Point = AdjustmentType.convert(Int) - Adjustment; - // [Int-Adjustment+1, Int-Adjustment-1] - // Notice that the lower bound is greater than the upper bound. - RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, Upper, Lower); + RangeSet New = getRange(St, Sym).Delete(getBasicVals(), F, Point); return New.isEmpty() ? nullptr : St->set(Sym, New); }