diff options
Diffstat (limited to 'clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp')
| -rw-r--r-- | clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp | 389 |
1 files changed, 271 insertions, 118 deletions
diff --git a/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp b/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp index 69554576bdb2..74403a160b8e 100644 --- a/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp +++ b/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp @@ -494,15 +494,17 @@ RangeSet RangeSet::Factory::deletePoint(RangeSet From, return intersect(From, Upper, Lower); } -void Range::dump(raw_ostream &OS) const { +LLVM_DUMP_METHOD void Range::dump(raw_ostream &OS) const { OS << '[' << toString(From(), 10) << ", " << toString(To(), 10) << ']'; } +LLVM_DUMP_METHOD void Range::dump() const { dump(llvm::errs()); } -void RangeSet::dump(raw_ostream &OS) const { +LLVM_DUMP_METHOD void RangeSet::dump(raw_ostream &OS) const { OS << "{ "; llvm::interleaveComma(*this, OS, [&OS](const Range &R) { R.dump(OS); }); OS << " }"; } +LLVM_DUMP_METHOD void RangeSet::dump() const { dump(llvm::errs()); } REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(SymbolSet, SymbolRef) @@ -599,6 +601,10 @@ public: LLVM_NODISCARD static inline Optional<bool> areEqual(ProgramStateRef State, SymbolRef First, SymbolRef Second); + /// Remove one member from the class. + LLVM_NODISCARD ProgramStateRef removeMember(ProgramStateRef State, + const SymbolRef Old); + /// Iterate over all symbols and try to simplify them. LLVM_NODISCARD static inline ProgramStateRef simplify(SValBuilder &SVB, RangeSet::Factory &F, @@ -655,6 +661,7 @@ private: inline ProgramStateRef mergeImpl(RangeSet::Factory &F, ProgramStateRef State, SymbolSet Members, EquivalenceClass Other, SymbolSet OtherMembers); + static inline bool addToDisequalityInfo(DisequalityMapTy &Info, ConstraintRangeTy &Constraints, RangeSet::Factory &F, ProgramStateRef State, @@ -1112,7 +1119,7 @@ private: if (!SSE) return llvm::None; - BinaryOperatorKind CurrentOP = SSE->getOpcode(); + const BinaryOperatorKind CurrentOP = SSE->getOpcode(); // We currently do not support <=> (C++20). if (!BinaryOperator::isComparisonOp(CurrentOP) || (CurrentOP == BO_Cmp)) @@ -1126,7 +1133,12 @@ private: SymbolManager &SymMgr = State->getSymbolManager(); - int UnknownStates = 0; + // We use this variable to store the last queried operator (`QueriedOP`) + // for which the `getCmpOpState` returned with `Unknown`. If there are two + // different OPs that returned `Unknown` then we have to query the special + // `UnknownX2` column. We assume that `getCmpOpState(CurrentOP, CurrentOP)` + // never returns `Unknown`, so `CurrentOP` is a good initial value. + BinaryOperatorKind LastQueriedOpToUnknown = CurrentOP; // Loop goes through all of the columns exept the last one ('UnknownX2'). // We treat `UnknownX2` column separately at the end of the loop body. @@ -1163,15 +1175,18 @@ private: CmpOpTable.getCmpOpState(CurrentOP, QueriedOP); if (BranchState == OperatorRelationsTable::Unknown) { - if (++UnknownStates == 2) - // If we met both Unknown states. + if (LastQueriedOpToUnknown != CurrentOP && + LastQueriedOpToUnknown != QueriedOP) { + // If we got the Unknown state for both different operators. // if (x <= y) // assume true // if (x != y) // assume true // if (x < y) // would be also true // Get a state from `UnknownX2` column. BranchState = CmpOpTable.getCmpOpStateForUnknownX2(CurrentOP); - else + } else { + LastQueriedOpToUnknown = QueriedOP; continue; + } } return (BranchState == OperatorRelationsTable::True) ? getTrueRange(T) @@ -1382,6 +1397,113 @@ RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Rem>(Range LHS, } //===----------------------------------------------------------------------===// +// Constraint manager implementation details +//===----------------------------------------------------------------------===// + +class RangeConstraintManager : public RangedConstraintManager { +public: + RangeConstraintManager(ExprEngine *EE, SValBuilder &SVB) + : RangedConstraintManager(EE, SVB), F(getBasicVals()) {} + + //===------------------------------------------------------------------===// + // Implementation for interface from ConstraintManager. + //===------------------------------------------------------------------===// + + bool haveEqualConstraints(ProgramStateRef S1, + ProgramStateRef S2) const override { + // NOTE: ClassMembers are as simple as back pointers for ClassMap, + // so comparing constraint ranges and class maps should be + // sufficient. + return S1->get<ConstraintRange>() == S2->get<ConstraintRange>() && + S1->get<ClassMap>() == S2->get<ClassMap>(); + } + + bool canReasonAbout(SVal X) const override; + + ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override; + + const llvm::APSInt *getSymVal(ProgramStateRef State, + SymbolRef Sym) const override; + + ProgramStateRef removeDeadBindings(ProgramStateRef State, + SymbolReaper &SymReaper) override; + + void printJson(raw_ostream &Out, ProgramStateRef State, const char *NL = "\n", + unsigned int Space = 0, bool IsDot = false) const override; + void printConstraints(raw_ostream &Out, ProgramStateRef State, + const char *NL = "\n", unsigned int Space = 0, + bool IsDot = false) const; + void printEquivalenceClasses(raw_ostream &Out, ProgramStateRef State, + const char *NL = "\n", unsigned int Space = 0, + bool IsDot = false) const; + void printDisequalities(raw_ostream &Out, ProgramStateRef State, + const char *NL = "\n", unsigned int Space = 0, + bool IsDot = false) const; + + //===------------------------------------------------------------------===// + // Implementation for interface from RangedConstraintManager. + //===------------------------------------------------------------------===// + + ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym, + const llvm::APSInt &V, + const llvm::APSInt &Adjustment) override; + + ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym, + const llvm::APSInt &V, + const llvm::APSInt &Adjustment) override; + + ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym, + const llvm::APSInt &V, + const llvm::APSInt &Adjustment) override; + + ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym, + const llvm::APSInt &V, + const llvm::APSInt &Adjustment) override; + + ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym, + const llvm::APSInt &V, + const llvm::APSInt &Adjustment) override; + + ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym, + const llvm::APSInt &V, + const llvm::APSInt &Adjustment) override; + + ProgramStateRef assumeSymWithinInclusiveRange( + ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, + const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; + + ProgramStateRef assumeSymOutsideInclusiveRange( + ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, + const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; + +private: + RangeSet::Factory F; + + RangeSet getRange(ProgramStateRef State, SymbolRef Sym); + RangeSet getRange(ProgramStateRef State, EquivalenceClass Class); + ProgramStateRef setRange(ProgramStateRef State, SymbolRef Sym, + RangeSet Range); + ProgramStateRef setRange(ProgramStateRef State, EquivalenceClass Class, + RangeSet Range); + + RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym, + const llvm::APSInt &Int, + const llvm::APSInt &Adjustment); + RangeSet getSymGTRange(ProgramStateRef St, SymbolRef Sym, + const llvm::APSInt &Int, + const llvm::APSInt &Adjustment); + RangeSet getSymLERange(ProgramStateRef St, SymbolRef Sym, + const llvm::APSInt &Int, + const llvm::APSInt &Adjustment); + RangeSet getSymLERange(llvm::function_ref<RangeSet()> RS, + const llvm::APSInt &Int, + const llvm::APSInt &Adjustment); + RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym, + const llvm::APSInt &Int, + const llvm::APSInt &Adjustment); +}; + +//===----------------------------------------------------------------------===// // Constraint assignment logic //===----------------------------------------------------------------------===// @@ -1492,7 +1614,28 @@ public: return Assignor.assign(CoS, NewConstraint); } + /// Handle expressions like: a % b != 0. + template <typename SymT> + bool handleRemainderOp(const SymT *Sym, RangeSet Constraint) { + if (Sym->getOpcode() != BO_Rem) + return true; + // a % b != 0 implies that a != 0. + if (!Constraint.containsZero()) { + SVal SymSVal = Builder.makeSymbolVal(Sym->getLHS()); + if (auto NonLocSymSVal = SymSVal.getAs<nonloc::SymbolVal>()) { + State = State->assume(*NonLocSymSVal, true); + if (!State) + return false; + } + } + return true; + } + inline bool assignSymExprToConst(const SymExpr *Sym, Const Constraint); + inline bool assignSymIntExprToRangeSet(const SymIntExpr *Sym, + RangeSet Constraint) { + return handleRemainderOp(Sym, Constraint); + } inline bool assignSymSymExprToRangeSet(const SymSymExpr *Sym, RangeSet Constraint); @@ -1568,11 +1711,9 @@ private: assert(!Constraint.isEmpty() && "Empty ranges shouldn't get here"); if (Constraint.getConcreteValue()) - return !Constraint.getConcreteValue()->isNullValue(); + return !Constraint.getConcreteValue()->isZero(); - APSIntType T{Constraint.getMinValue()}; - Const Zero = T.getZeroValue(); - if (!Constraint.contains(Zero)) + if (!Constraint.containsZero()) return true; return llvm::None; @@ -1583,112 +1724,6 @@ private: RangeSet::Factory &RangeFactory; }; -//===----------------------------------------------------------------------===// -// Constraint manager implementation details -//===----------------------------------------------------------------------===// - -class RangeConstraintManager : public RangedConstraintManager { -public: - RangeConstraintManager(ExprEngine *EE, SValBuilder &SVB) - : RangedConstraintManager(EE, SVB), F(getBasicVals()) {} - - //===------------------------------------------------------------------===// - // Implementation for interface from ConstraintManager. - //===------------------------------------------------------------------===// - - bool haveEqualConstraints(ProgramStateRef S1, - ProgramStateRef S2) const override { - // NOTE: ClassMembers are as simple as back pointers for ClassMap, - // so comparing constraint ranges and class maps should be - // sufficient. - return S1->get<ConstraintRange>() == S2->get<ConstraintRange>() && - S1->get<ClassMap>() == S2->get<ClassMap>(); - } - - bool canReasonAbout(SVal X) const override; - - ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override; - - const llvm::APSInt *getSymVal(ProgramStateRef State, - SymbolRef Sym) const override; - - ProgramStateRef removeDeadBindings(ProgramStateRef State, - SymbolReaper &SymReaper) override; - - void printJson(raw_ostream &Out, ProgramStateRef State, const char *NL = "\n", - unsigned int Space = 0, bool IsDot = false) const override; - void printConstraints(raw_ostream &Out, ProgramStateRef State, - const char *NL = "\n", unsigned int Space = 0, - bool IsDot = false) const; - void printEquivalenceClasses(raw_ostream &Out, ProgramStateRef State, - const char *NL = "\n", unsigned int Space = 0, - bool IsDot = false) const; - void printDisequalities(raw_ostream &Out, ProgramStateRef State, - const char *NL = "\n", unsigned int Space = 0, - bool IsDot = false) const; - - //===------------------------------------------------------------------===// - // Implementation for interface from RangedConstraintManager. - //===------------------------------------------------------------------===// - - ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym, - const llvm::APSInt &V, - const llvm::APSInt &Adjustment) override; - - ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym, - const llvm::APSInt &V, - const llvm::APSInt &Adjustment) override; - - ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym, - const llvm::APSInt &V, - const llvm::APSInt &Adjustment) override; - - ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym, - const llvm::APSInt &V, - const llvm::APSInt &Adjustment) override; - - ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym, - const llvm::APSInt &V, - const llvm::APSInt &Adjustment) override; - - ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym, - const llvm::APSInt &V, - const llvm::APSInt &Adjustment) override; - - ProgramStateRef assumeSymWithinInclusiveRange( - ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, - const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; - - ProgramStateRef assumeSymOutsideInclusiveRange( - ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, - const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; - -private: - RangeSet::Factory F; - - RangeSet getRange(ProgramStateRef State, SymbolRef Sym); - RangeSet getRange(ProgramStateRef State, EquivalenceClass Class); - ProgramStateRef setRange(ProgramStateRef State, SymbolRef Sym, - RangeSet Range); - ProgramStateRef setRange(ProgramStateRef State, EquivalenceClass Class, - RangeSet Range); - - RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym, - const llvm::APSInt &Int, - const llvm::APSInt &Adjustment); - RangeSet getSymGTRange(ProgramStateRef St, SymbolRef Sym, - const llvm::APSInt &Int, - const llvm::APSInt &Adjustment); - RangeSet getSymLERange(ProgramStateRef St, SymbolRef Sym, - const llvm::APSInt &Int, - const llvm::APSInt &Adjustment); - RangeSet getSymLERange(llvm::function_ref<RangeSet()> RS, - const llvm::APSInt &Int, - const llvm::APSInt &Adjustment); - RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym, - const llvm::APSInt &Int, - const llvm::APSInt &Adjustment); -}; bool ConstraintAssignor::assignSymExprToConst(const SymExpr *Sym, const llvm::APSInt &Constraint) { @@ -1716,11 +1751,26 @@ bool ConstraintAssignor::assignSymExprToConst(const SymExpr *Sym, return false; } + // We may have trivial equivalence classes in the disequality info as + // well, and we need to simplify them. + DisequalityMapTy DisequalityInfo = State->get<DisequalityMap>(); + for (std::pair<EquivalenceClass, ClassSet> DisequalityEntry : + DisequalityInfo) { + EquivalenceClass Class = DisequalityEntry.first; + ClassSet DisequalClasses = DisequalityEntry.second; + State = EquivalenceClass::simplify(Builder, RangeFactory, State, Class); + if (!State) + return false; + } + return true; } bool ConstraintAssignor::assignSymSymExprToRangeSet(const SymSymExpr *Sym, RangeSet Constraint) { + if (!handleRemainderOp(Sym, Constraint)) + return false; + Optional<bool> ConstraintAsBool = interpreteAsBool(Constraint); if (!ConstraintAsBool) @@ -2086,6 +2136,61 @@ inline Optional<bool> EquivalenceClass::areEqual(ProgramStateRef State, return llvm::None; } +LLVM_NODISCARD ProgramStateRef +EquivalenceClass::removeMember(ProgramStateRef State, const SymbolRef Old) { + + SymbolSet ClsMembers = getClassMembers(State); + assert(ClsMembers.contains(Old)); + + // We don't remove `Old`'s Sym->Class relation for two reasons: + // 1) This way constraints for the old symbol can still be found via it's + // equivalence class that it used to be the member of. + // 2) Performance and resource reasons. We can spare one removal and thus one + // additional tree in the forest of `ClassMap`. + + // Remove `Old`'s Class->Sym relation. + SymbolSet::Factory &F = getMembersFactory(State); + ClassMembersTy::Factory &EMFactory = State->get_context<ClassMembers>(); + ClsMembers = F.remove(ClsMembers, Old); + // Ensure another precondition of the removeMember function (we can check + // this only with isEmpty, thus we have to do the remove first). + assert(!ClsMembers.isEmpty() && + "Class should have had at least two members before member removal"); + // Overwrite the existing members assigned to this class. + ClassMembersTy ClassMembersMap = State->get<ClassMembers>(); + ClassMembersMap = EMFactory.add(ClassMembersMap, *this, ClsMembers); + State = State->set<ClassMembers>(ClassMembersMap); + + return State; +} + +// Re-evaluate an SVal with top-level `State->assume` logic. +LLVM_NODISCARD ProgramStateRef reAssume(ProgramStateRef State, + const RangeSet *Constraint, + SVal TheValue) { + if (!Constraint) + return State; + + const auto DefinedVal = TheValue.castAs<DefinedSVal>(); + + // If the SVal is 0, we can simply interpret that as `false`. + if (Constraint->encodesFalseRange()) + return State->assume(DefinedVal, false); + + // If the constraint does not encode 0 then we can interpret that as `true` + // AND as a Range(Set). + if (Constraint->encodesTrueRange()) { + State = State->assume(DefinedVal, true); + if (!State) + return nullptr; + // Fall through, re-assume based on the range values as well. + } + // Overestimate the individual Ranges with the RangeSet' lowest and + // highest values. + return State->assumeInclusiveRange(DefinedVal, Constraint->getMinValue(), + Constraint->getMaxValue(), true); +} + // Iterate over all symbols and try to simplify them. Once a symbol is // simplified then we check if we can merge the simplified symbol's equivalence // class to this class. This way, we simplify not just the symbols but the @@ -2096,14 +2201,62 @@ EquivalenceClass::simplify(SValBuilder &SVB, RangeSet::Factory &F, ProgramStateRef State, EquivalenceClass Class) { SymbolSet ClassMembers = Class.getClassMembers(State); for (const SymbolRef &MemberSym : ClassMembers) { - SymbolRef SimplifiedMemberSym = ento::simplify(State, MemberSym); + + const SVal SimplifiedMemberVal = simplifyToSVal(State, MemberSym); + const SymbolRef SimplifiedMemberSym = SimplifiedMemberVal.getAsSymbol(); + + // The symbol is collapsed to a constant, check if the current State is + // still feasible. + if (const auto CI = SimplifiedMemberVal.getAs<nonloc::ConcreteInt>()) { + const llvm::APSInt &SV = CI->getValue(); + const RangeSet *ClassConstraint = getConstraint(State, Class); + // We have found a contradiction. + if (ClassConstraint && !ClassConstraint->contains(SV)) + return nullptr; + } + if (SimplifiedMemberSym && MemberSym != SimplifiedMemberSym) { // The simplified symbol should be the member of the original Class, // however, it might be in another existing class at the moment. We // have to merge these classes. + ProgramStateRef OldState = State; State = merge(F, State, MemberSym, SimplifiedMemberSym); if (!State) return nullptr; + // No state change, no merge happened actually. + if (OldState == State) + continue; + + assert(find(State, MemberSym) == find(State, SimplifiedMemberSym)); + // Remove the old and more complex symbol. + State = find(State, MemberSym).removeMember(State, MemberSym); + + // Query the class constraint again b/c that may have changed during the + // merge above. + const RangeSet *ClassConstraint = getConstraint(State, Class); + + // Re-evaluate an SVal with top-level `State->assume`, this ignites + // a RECURSIVE algorithm that will reach a FIXPOINT. + // + // About performance and complexity: Let us assume that in a State we + // have N non-trivial equivalence classes and that all constraints and + // disequality info is related to non-trivial classes. In the worst case, + // we can simplify only one symbol of one class in each iteration. The + // number of symbols in one class cannot grow b/c we replace the old + // symbol with the simplified one. Also, the number of the equivalence + // classes can decrease only, b/c the algorithm does a merge operation + // optionally. We need N iterations in this case to reach the fixpoint. + // Thus, the steps needed to be done in the worst case is proportional to + // N*N. + // + // This worst case scenario can be extended to that case when we have + // trivial classes in the constraints and in the disequality map. This + // case can be reduced to the case with a State where there are only + // non-trivial classes. This is because a merge operation on two trivial + // classes results in one non-trivial class. + State = reAssume(State, ClassConstraint, SimplifiedMemberVal); + if (!State) + return nullptr; } } return State; |