diff options
| author | Dimitry Andric <dim@FreeBSD.org> | 2022-07-03 14:10:23 +0000 |
|---|---|---|
| committer | Dimitry Andric <dim@FreeBSD.org> | 2022-07-03 14:10:23 +0000 |
| commit | 145449b1e420787bb99721a429341fa6be3adfb6 (patch) | |
| tree | 1d56ae694a6de602e348dd80165cf881a36600ed /clang/lib/StaticAnalyzer/Core | |
| parent | ecbca9f5fb7d7613d2b94982c4825eb0d33d6842 (diff) | |
Diffstat (limited to 'clang/lib/StaticAnalyzer/Core')
30 files changed, 1175 insertions, 542 deletions
diff --git a/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp b/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp index 8cd7f75e4e38..79d19a3b99f2 100644 --- a/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp +++ b/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp @@ -77,7 +77,18 @@ AnalyzerOptions::getExplorationStrategy() const { .Case("bfs_block_dfs_contents", ExplorationStrategyKind::BFSBlockDFSContents) .Default(None); - assert(K.hasValue() && "User mode is invalid."); + assert(K && "User mode is invalid."); + return K.getValue(); +} + +CTUPhase1InliningKind AnalyzerOptions::getCTUPhase1Inlining() const { + auto K = llvm::StringSwitch<llvm::Optional<CTUPhase1InliningKind>>( + CTUPhase1InliningMode) + .Case("none", CTUPhase1InliningKind::None) + .Case("small", CTUPhase1InliningKind::Small) + .Case("all", CTUPhase1InliningKind::All) + .Default(None); + assert(K && "CTU inlining mode is invalid."); return K.getValue(); } @@ -89,7 +100,7 @@ IPAKind AnalyzerOptions::getIPAMode() const { .Case("dynamic", IPAK_DynamicDispatch) .Case("dynamic-bifurcate", IPAK_DynamicDispatchBifurcate) .Default(None); - assert(K.hasValue() && "IPA Mode is invalid."); + assert(K && "IPA Mode is invalid."); return K.getValue(); } @@ -109,7 +120,7 @@ AnalyzerOptions::mayInlineCXXMemberFunction( .Case("none", CIMK_None) .Default(None); - assert(K.hasValue() && "Invalid c++ member function inlining mode."); + assert(K && "Invalid c++ member function inlining mode."); return *K >= Param; } diff --git a/clang/lib/StaticAnalyzer/Core/BugReporter.cpp b/clang/lib/StaticAnalyzer/Core/BugReporter.cpp index 771ed2578f6d..a2efe14f1045 100644 --- a/clang/lib/StaticAnalyzer/Core/BugReporter.cpp +++ b/clang/lib/StaticAnalyzer/Core/BugReporter.cpp @@ -1883,7 +1883,7 @@ static bool optimizeEdges(const PathDiagnosticConstruct &C, PathPieces &path, lexicalContains(PM, s1Start, s1End)) { SourceRange EdgeRange(PieceI->getEndLocation().asLocation(), PieceI->getStartLocation().asLocation()); - if (!getLengthOnSingleLine(SM, EdgeRange).hasValue()) + if (!getLengthOnSingleLine(SM, EdgeRange)) removeEdge = true; } } diff --git a/clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp b/clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp index e13387fb1fc8..5b72c91ccd74 100644 --- a/clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp +++ b/clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp @@ -82,6 +82,10 @@ static const Expr *peelOffPointerArithmetic(const BinaryOperator *B) { return nullptr; } +/// \return A subexpression of @c Ex which represents the +/// expression-of-interest. +static const Expr *peelOffOuterExpr(const Expr *Ex, const ExplodedNode *N); + /// Given that expression S represents a pointer that would be dereferenced, /// try to find a sub-expression from which the pointer came from. /// This is used for tracking down origins of a null or undefined value: @@ -254,7 +258,7 @@ static bool isVarAnInterestingCondition(const Expr *CondVarExpr, static bool isInterestingExpr(const Expr *E, const ExplodedNode *N, const PathSensitiveBugReport *B) { if (Optional<SVal> V = getSValForVar(E, N)) - return B->getInterestingnessKind(*V).hasValue(); + return B->getInterestingnessKind(*V).has_value(); return false; } @@ -523,11 +527,6 @@ public: ID.AddPointer(RegionOfInterest); } - void *getTag() const { - static int Tag = 0; - return static_cast<void *>(&Tag); - } - private: /// \return Whether \c RegionOfInterest was modified at \p CurrN compared to /// the value it holds in \p CallExitBeginN. @@ -915,7 +914,7 @@ public: const SVal V) { AnalyzerOptions &Options = N->getState()->getAnalysisManager().options; if (EnableNullFPSuppression && Options.ShouldSuppressNullReturnPaths && - V.getAs<Loc>()) + isa<Loc>(V)) BR.addVisitor<MacroNullReturnSuppressionVisitor>(R->getAs<SubRegion>(), V); } @@ -1031,14 +1030,13 @@ public: if (RetE->isGLValue()) { if ((LValue = V.getAs<Loc>())) { SVal RValue = State->getRawSVal(*LValue, RetE->getType()); - if (RValue.getAs<DefinedSVal>()) + if (isa<DefinedSVal>(RValue)) V = RValue; } } // Ignore aggregate rvalues. - if (V.getAs<nonloc::LazyCompoundVal>() || - V.getAs<nonloc::CompoundVal>()) + if (isa<nonloc::LazyCompoundVal, nonloc::CompoundVal>(V)) return nullptr; RetE = RetE->IgnoreParenCasts(); @@ -1053,7 +1051,7 @@ public: bool WouldEventBeMeaningless = false; if (State->isNull(V).isConstrainedTrue()) { - if (V.getAs<Loc>()) { + if (isa<Loc>(V)) { // If we have counter-suppression enabled, make sure we keep visiting // future nodes. We want to emit a path note as well, in case @@ -1083,10 +1081,7 @@ public: if (N->getCFG().size() == 3) WouldEventBeMeaningless = true; - if (V.getAs<Loc>()) - Out << "Returning pointer"; - else - Out << "Returning value"; + Out << (isa<Loc>(V) ? "Returning pointer" : "Returning value"); } } @@ -1309,7 +1304,7 @@ static void showBRDiagnostics(llvm::raw_svector_ostream &OS, StoreInfo SI) { llvm_unreachable("Unexpected store kind"); } - if (SI.Value.getAs<loc::ConcreteInt>()) { + if (isa<loc::ConcreteInt>(SI.Value)) { OS << Action << (isObjCPointer(SI.Dest) ? "nil" : "a null pointer value"); } else if (auto CVal = SI.Value.getAs<nonloc::ConcreteInt>()) { @@ -1352,7 +1347,7 @@ static void showBRParamDiagnostics(llvm::raw_svector_ostream &OS, OS << "Passing "; - if (SI.Value.getAs<loc::ConcreteInt>()) { + if (isa<loc::ConcreteInt>(SI.Value)) { OS << (isObjCPointer(Param) ? "nil object reference" : "null pointer value"); @@ -1383,7 +1378,7 @@ static void showBRDefaultDiagnostics(llvm::raw_svector_ostream &OS, StoreInfo SI) { const bool HasSuffix = SI.Dest->canPrintPretty(); - if (SI.Value.getAs<loc::ConcreteInt>()) { + if (isa<loc::ConcreteInt>(SI.Value)) { OS << (isObjCPointer(SI.Dest) ? "nil object reference stored" : (HasSuffix ? "Null pointer value stored" : "Storing null pointer value")); @@ -1681,7 +1676,7 @@ PathDiagnosticPieceRef TrackConstraintBRVisitor::VisitNode( SmallString<64> sbuf; llvm::raw_svector_ostream os(sbuf); - if (Constraint.getAs<Loc>()) { + if (isa<Loc>(Constraint)) { os << "Assuming pointer value is "; os << (Assumption ? "non-null" : "null"); } @@ -1691,6 +1686,13 @@ PathDiagnosticPieceRef TrackConstraintBRVisitor::VisitNode( // Construct a new PathDiagnosticPiece. ProgramPoint P = N->getLocation(); + + // If this node already have a specialized note, it's probably better + // than our generic note. + // FIXME: This only looks for note tags, not for other ways to add a note. + if (isa_and_nonnull<NoteTag>(P.getTag())) + return nullptr; + PathDiagnosticLocation L = PathDiagnosticLocation::create(P, BRC.getSourceManager()); if (!L.isValid()) @@ -1919,11 +1921,33 @@ TrackControlDependencyCondBRVisitor::VisitNode(const ExplodedNode *N, return nullptr; if (const Expr *Condition = NB->getLastCondition()) { + + // If we can't retrieve a sensible condition, just bail out. + const Expr *InnerExpr = peelOffOuterExpr(Condition, N); + if (!InnerExpr) + return nullptr; + + // If the condition was a function call, we likely won't gain much from + // tracking it either. Evidence suggests that it will mostly trigger in + // scenarios like this: + // + // void f(int *x) { + // x = nullptr; + // if (alwaysTrue()) // We don't need a whole lot of explanation + // // here, the function name is good enough. + // *x = 5; + // } + // + // Its easy to create a counterexample where this heuristic would make us + // lose valuable information, but we've never really seen one in practice. + if (isa<CallExpr>(InnerExpr)) + return nullptr; + // Keeping track of the already tracked conditions on a visitor level // isn't sufficient, because a new visitor is created for each tracked // expression, hence the BugReport level set. if (BR.addTrackedCondition(N)) { - getParentTracker().track(Condition, N, + getParentTracker().track(InnerExpr, N, {bugreporter::TrackingKind::Condition, /*EnableNullFPSuppression=*/false}); return constructDebugPieceForTrackedCondition(Condition, N, BRC); @@ -1938,10 +1962,8 @@ TrackControlDependencyCondBRVisitor::VisitNode(const ExplodedNode *N, // Implementation of trackExpressionValue. //===----------------------------------------------------------------------===// -/// \return A subexpression of @c Ex which represents the -/// expression-of-interest. -static const Expr *peelOffOuterExpr(const Expr *Ex, - const ExplodedNode *N) { +static const Expr *peelOffOuterExpr(const Expr *Ex, const ExplodedNode *N) { + Ex = Ex->IgnoreParenCasts(); if (const auto *FE = dyn_cast<FullExpr>(Ex)) return peelOffOuterExpr(FE->getSubExpr(), N); @@ -2333,7 +2355,7 @@ public: // well. Try to use the correct type when looking up the value. SVal RVal; if (ExplodedGraph::isInterestingLValueExpr(Inner)) - RVal = LVState->getRawSVal(L.getValue(), Inner->getType()); + RVal = LVState->getRawSVal(*L, Inner->getType()); else if (CanDereference) RVal = LVState->getSVal(L->getRegion()); @@ -2927,7 +2949,7 @@ PathDiagnosticPieceRef ConditionBRVisitor::VisitTrueTest( PathDiagnosticLocation Loc(Cond, SM, LCtx); auto event = std::make_shared<PathDiagnosticEventPiece>(Loc, Message); - if (shouldPrune.hasValue()) + if (shouldPrune) event->setPrunable(shouldPrune.getValue()); return event; } @@ -3055,7 +3077,7 @@ bool ConditionBRVisitor::printValue(const Expr *CondVarExpr, raw_ostream &Out, if (!IsAssuming) IntValue = getConcreteIntegerValue(CondVarExpr, N); - if (IsAssuming || !IntValue.hasValue()) { + if (IsAssuming || !IntValue) { if (Ty->isBooleanType()) Out << (TookTrue ? "true" : "false"); else @@ -3257,7 +3279,7 @@ void FalsePositiveRefutationBRVisitor::finalizeVisitor( // And check for satisfiability Optional<bool> IsSAT = RefutationSolver->check(); - if (!IsSAT.hasValue()) + if (!IsSAT) return; if (!IsSAT.getValue()) diff --git a/clang/lib/StaticAnalyzer/Core/CallDescription.cpp b/clang/lib/StaticAnalyzer/Core/CallDescription.cpp index 810fe365d021..bb8b7492e248 100644 --- a/clang/lib/StaticAnalyzer/Core/CallDescription.cpp +++ b/clang/lib/StaticAnalyzer/Core/CallDescription.cpp @@ -13,6 +13,7 @@ //===----------------------------------------------------------------------===// #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h" +#include "clang/AST/Decl.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" #include "llvm/ADT/ArrayRef.h" @@ -61,22 +62,39 @@ bool ento::CallDescription::matches(const CallEvent &Call) const { if (!FD) return false; + return matchesImpl(FD, Call.getNumArgs(), Call.parameters().size()); +} + +bool ento::CallDescription::matchesAsWritten(const CallExpr &CE) const { + const auto *FD = dyn_cast_or_null<FunctionDecl>(CE.getCalleeDecl()); + if (!FD) + return false; + + return matchesImpl(FD, CE.getNumArgs(), FD->param_size()); +} + +bool ento::CallDescription::matchesImpl(const FunctionDecl *Callee, + size_t ArgCount, + size_t ParamCount) const { + const auto *FD = Callee; + if (!FD) + return false; + if (Flags & CDF_MaybeBuiltin) { return CheckerContext::isCLibraryFunction(FD, getFunctionName()) && - (!RequiredArgs || *RequiredArgs <= Call.getNumArgs()) && - (!RequiredParams || *RequiredParams <= Call.parameters().size()); + (!RequiredArgs || *RequiredArgs <= ArgCount) && + (!RequiredParams || *RequiredParams <= ParamCount); } - if (!II.hasValue()) { - II = &Call.getState()->getStateManager().getContext().Idents.get( - getFunctionName()); + if (!II) { + II = &FD->getASTContext().Idents.get(getFunctionName()); } const auto MatchNameOnly = [](const CallDescription &CD, const NamedDecl *ND) -> bool { DeclarationName Name = ND->getDeclName(); if (const auto *II = Name.getAsIdentifierInfo()) - return II == CD.II.getValue(); // Fast case. + return II == *CD.II; // Fast case. // Fallback to the slow stringification and comparison for: // C++ overloaded operators, constructors, destructors, etc. @@ -86,11 +104,11 @@ bool ento::CallDescription::matches(const CallEvent &Call) const { }; const auto ExactMatchArgAndParamCounts = - [](const CallEvent &Call, const CallDescription &CD) -> bool { - const bool ArgsMatch = - !CD.RequiredArgs || *CD.RequiredArgs == Call.getNumArgs(); + [](size_t ArgCount, size_t ParamCount, + const CallDescription &CD) -> bool { + const bool ArgsMatch = !CD.RequiredArgs || *CD.RequiredArgs == ArgCount; const bool ParamsMatch = - !CD.RequiredParams || *CD.RequiredParams == Call.parameters().size(); + !CD.RequiredParams || *CD.RequiredParams == ParamCount; return ArgsMatch && ParamsMatch; }; @@ -122,7 +140,7 @@ bool ento::CallDescription::matches(const CallEvent &Call) const { }; // Let's start matching... - if (!ExactMatchArgAndParamCounts(Call, *this)) + if (!ExactMatchArgAndParamCounts(ArgCount, ParamCount, *this)) return false; if (!MatchNameOnly(*this, FD)) @@ -144,3 +162,7 @@ ento::CallDescriptionSet::CallDescriptionSet( bool ento::CallDescriptionSet::contains(const CallEvent &Call) const { return static_cast<bool>(Impl.lookup(Call)); } + +bool ento::CallDescriptionSet::containsAsWritten(const CallExpr &CE) const { + return static_cast<bool>(Impl.lookupAsWritten(CE)); +} diff --git a/clang/lib/StaticAnalyzer/Core/CallEvent.cpp b/clang/lib/StaticAnalyzer/Core/CallEvent.cpp index ae46709340d3..3a8d69df7a64 100644 --- a/clang/lib/StaticAnalyzer/Core/CallEvent.cpp +++ b/clang/lib/StaticAnalyzer/Core/CallEvent.cpp @@ -515,20 +515,28 @@ RuntimeDefinition AnyFunctionCall::getRuntimeDefinition() const { llvm::dbgs() << "Using autosynthesized body for " << FD->getName() << "\n"; }); - if (Body) { - const Decl* Decl = AD->getDecl(); - return RuntimeDefinition(Decl); - } ExprEngine &Engine = getState()->getStateManager().getOwningEngine(); + cross_tu::CrossTranslationUnitContext &CTUCtx = + *Engine.getCrossTranslationUnitContext(); + AnalyzerOptions &Opts = Engine.getAnalysisManager().options; + if (Body) { + const Decl* Decl = AD->getDecl(); + if (Opts.IsNaiveCTUEnabled && CTUCtx.isImportedAsNew(Decl)) { + // A newly created definition, but we had error(s) during the import. + if (CTUCtx.hasError(Decl)) + return {}; + return RuntimeDefinition(Decl, /*Foreign=*/true); + } + return RuntimeDefinition(Decl, /*Foreign=*/false); + } + // Try to get CTU definition only if CTUDir is provided. if (!Opts.IsNaiveCTUEnabled) return {}; - cross_tu::CrossTranslationUnitContext &CTUCtx = - *Engine.getCrossTranslationUnitContext(); llvm::Expected<const FunctionDecl *> CTUDeclOrError = CTUCtx.getCrossTUDefinition(FD, Opts.CTUDir, Opts.CTUIndexName, Opts.DisplayCTUProgress); @@ -541,7 +549,7 @@ RuntimeDefinition AnyFunctionCall::getRuntimeDefinition() const { return {}; } - return RuntimeDefinition(*CTUDeclOrError); + return RuntimeDefinition(*CTUDeclOrError, /*Foreign=*/true); } void AnyFunctionCall::getInitialStackFrameContents( @@ -672,7 +680,7 @@ SVal CXXInstanceCall::getCXXThisVal() const { return UnknownVal(); SVal ThisVal = getSVal(Base); - assert(ThisVal.isUnknownOrUndef() || ThisVal.getAs<Loc>()); + assert(ThisVal.isUnknownOrUndef() || isa<Loc>(ThisVal)); return ThisVal; } @@ -764,7 +772,7 @@ void CXXInstanceCall::getInitialStackFrameContents( // FIXME: CallEvent maybe shouldn't be directly accessing StoreManager. Optional<SVal> V = StateMgr.getStoreManager().evalBaseToDerived(ThisVal, Ty); - if (!V.hasValue()) { + if (!V) { // We might have suffered some sort of placement new earlier, so // we're constructing in a completely unexpected storage. // Fall back to a generic pointer cast for this-value. @@ -1184,7 +1192,7 @@ lookupRuntimeDefinition(const ObjCInterfaceDecl *Interface, PMC[{Interface, LookupSelector, InstanceMethod}]; // Query lookupPrivateMethod() if the cache does not hit. - if (!Val.hasValue()) { + if (!Val) { Val = Interface->lookupPrivateMethod(LookupSelector, InstanceMethod); if (!*Val) { @@ -1193,7 +1201,7 @@ lookupRuntimeDefinition(const ObjCInterfaceDecl *Interface, } } - return Val.getValue(); + return *Val; } RuntimeDefinition ObjCMethodCall::getRuntimeDefinition() const { @@ -1398,7 +1406,7 @@ CallEventManager::getCaller(const StackFrameContext *CalleeCtx, Trigger = Dtor->getBody(); return getCXXDestructorCall(Dtor, Trigger, ThisVal.getAsRegion(), - E.getAs<CFGBaseDtor>().hasValue(), State, + E.getAs<CFGBaseDtor>().has_value(), State, CallerCtx); } @@ -1408,6 +1416,8 @@ CallEventRef<> CallEventManager::getCall(const Stmt *S, ProgramStateRef State, return getSimpleCall(CE, State, LC); } else if (const auto *NE = dyn_cast<CXXNewExpr>(S)) { return getCXXAllocatorCall(NE, State, LC); + } else if (const auto *DE = dyn_cast<CXXDeleteExpr>(S)) { + return getCXXDeallocatorCall(DE, State, LC); } else if (const auto *ME = dyn_cast<ObjCMessageExpr>(S)) { return getObjCMethodCall(ME, State, LC); } else { diff --git a/clang/lib/StaticAnalyzer/Core/CheckerContext.cpp b/clang/lib/StaticAnalyzer/Core/CheckerContext.cpp index 4c684c3ffd9b..1e2532d27633 100644 --- a/clang/lib/StaticAnalyzer/Core/CheckerContext.cpp +++ b/clang/lib/StaticAnalyzer/Core/CheckerContext.cpp @@ -55,8 +55,29 @@ bool CheckerContext::isCLibraryFunction(const FunctionDecl *FD, if (Name.empty()) return true; StringRef BName = FD->getASTContext().BuiltinInfo.getName(BId); - if (BName.contains(Name)) - return true; + size_t start = BName.find(Name); + if (start != StringRef::npos) { + // Accept exact match. + if (BName.size() == Name.size()) + return true; + + // v-- match starts here + // ...xxxxx... + // _xxxxx_ + // ^ ^ lookbehind and lookahead characters + + const auto MatchPredecessor = [=]() -> bool { + return start <= 0 || !llvm::isAlpha(BName[start - 1]); + }; + const auto MatchSuccessor = [=]() -> bool { + std::size_t LookbehindPlace = start + Name.size(); + return LookbehindPlace >= BName.size() || + !llvm::isAlpha(BName[LookbehindPlace]); + }; + + if (MatchPredecessor() && MatchSuccessor()) + return true; + } } const IdentifierInfo *II = FD->getIdentifier(); @@ -106,10 +127,10 @@ static bool evalComparison(SVal LHSVal, BinaryOperatorKind ComparisonOp, if (LHSVal.isUnknownOrUndef()) return false; ProgramStateManager &Mgr = State->getStateManager(); - if (!LHSVal.getAs<NonLoc>()) { + if (!isa<NonLoc>(LHSVal)) { LHSVal = Mgr.getStoreManager().getBinding(State->getStore(), LHSVal.castAs<Loc>()); - if (LHSVal.isUnknownOrUndef() || !LHSVal.getAs<NonLoc>()) + if (LHSVal.isUnknownOrUndef() || !isa<NonLoc>(LHSVal)) return false; } diff --git a/clang/lib/StaticAnalyzer/Core/ConstraintManager.cpp b/clang/lib/StaticAnalyzer/Core/ConstraintManager.cpp index d642c3530268..9ef3455a110a 100644 --- a/clang/lib/StaticAnalyzer/Core/ConstraintManager.cpp +++ b/clang/lib/StaticAnalyzer/Core/ConstraintManager.cpp @@ -16,6 +16,7 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" +#include "llvm/ADT/ScopeExit.h" using namespace clang; using namespace ento; @@ -41,3 +42,82 @@ ConditionTruthVal ConstraintManager::checkNull(ProgramStateRef State, return ConditionTruthVal(true); return {}; } + +template <typename AssumeFunction> +ConstraintManager::ProgramStatePair +ConstraintManager::assumeDualImpl(ProgramStateRef &State, + AssumeFunction &Assume) { + if (LLVM_UNLIKELY(State->isPosteriorlyOverconstrained())) + return {State, State}; + + // Assume functions might recurse (see `reAssume` or `tryRearrange`). During + // the recursion the State might not change anymore, that means we reached a + // fixpoint. + // We avoid infinite recursion of assume calls by checking already visited + // States on the stack of assume function calls. + const ProgramState *RawSt = State.get(); + if (LLVM_UNLIKELY(AssumeStack.contains(RawSt))) + return {State, State}; + AssumeStack.push(RawSt); + auto AssumeStackBuilder = + llvm::make_scope_exit([this]() { AssumeStack.pop(); }); + + ProgramStateRef StTrue = Assume(true); + + if (!StTrue) { + ProgramStateRef StFalse = Assume(false); + if (LLVM_UNLIKELY(!StFalse)) { // both infeasible + ProgramStateRef StInfeasible = State->cloneAsPosteriorlyOverconstrained(); + assert(StInfeasible->isPosteriorlyOverconstrained()); + // Checkers might rely on the API contract that both returned states + // cannot be null. Thus, we return StInfeasible for both branches because + // it might happen that a Checker uncoditionally uses one of them if the + // other is a nullptr. This may also happen with the non-dual and + // adjacent `assume(true)` and `assume(false)` calls. By implementing + // assume in therms of assumeDual, we can keep our API contract there as + // well. + return ProgramStatePair(StInfeasible, StInfeasible); + } + return ProgramStatePair(nullptr, StFalse); + } + + ProgramStateRef StFalse = Assume(false); + if (!StFalse) { + return ProgramStatePair(StTrue, nullptr); + } + + return ProgramStatePair(StTrue, StFalse); +} + +ConstraintManager::ProgramStatePair +ConstraintManager::assumeDual(ProgramStateRef State, DefinedSVal Cond) { + auto AssumeFun = [&](bool Assumption) { + return assumeInternal(State, Cond, Assumption); + }; + return assumeDualImpl(State, AssumeFun); +} + +ConstraintManager::ProgramStatePair +ConstraintManager::assumeInclusiveRangeDual(ProgramStateRef State, NonLoc Value, + const llvm::APSInt &From, + const llvm::APSInt &To) { + auto AssumeFun = [&](bool Assumption) { + return assumeInclusiveRangeInternal(State, Value, From, To, Assumption); + }; + return assumeDualImpl(State, AssumeFun); +} + +ProgramStateRef ConstraintManager::assume(ProgramStateRef State, + DefinedSVal Cond, bool Assumption) { + ConstraintManager::ProgramStatePair R = assumeDual(State, Cond); + return Assumption ? R.first : R.second; +} + +ProgramStateRef +ConstraintManager::assumeInclusiveRange(ProgramStateRef State, NonLoc Value, + const llvm::APSInt &From, + const llvm::APSInt &To, bool InBound) { + ConstraintManager::ProgramStatePair R = + assumeInclusiveRangeDual(State, Value, From, To); + return InBound ? R.first : R.second; +} diff --git a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp index d57bab154b61..de90f4a71be0 100644 --- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -43,6 +43,8 @@ using namespace ento; STATISTIC(NumSteps, "The # of steps executed."); +STATISTIC(NumSTUSteps, "The # of STU steps executed."); +STATISTIC(NumCTUSteps, "The # of CTU steps executed."); STATISTIC(NumReachedMaxSteps, "The # of times we reached the max number of steps."); STATISTIC(NumPathsExplored, @@ -73,11 +75,18 @@ static std::unique_ptr<WorkList> generateWorkList(AnalyzerOptions &Opts) { CoreEngine::CoreEngine(ExprEngine &exprengine, FunctionSummariesTy *FS, AnalyzerOptions &Opts) : ExprEng(exprengine), WList(generateWorkList(Opts)), + CTUWList(Opts.IsNaiveCTUEnabled ? generateWorkList(Opts) : nullptr), BCounterFactory(G.getAllocator()), FunctionSummaries(FS) {} +void CoreEngine::setBlockCounter(BlockCounter C) { + WList->setBlockCounter(C); + if (CTUWList) + CTUWList->setBlockCounter(C); +} + /// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps. -bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps, - ProgramStateRef InitState) { +bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned MaxSteps, + ProgramStateRef InitState) { if (G.num_roots() == 0) { // Initialize the analysis by constructing // the root if none exists. @@ -100,7 +109,7 @@ bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps, BlockEdge StartLoc(Entry, Succ, L); // Set the current block counter to being empty. - WList->setBlockCounter(BCounterFactory.GetEmptyCounter()); + setBlockCounter(BCounterFactory.GetEmptyCounter()); if (!InitState) InitState = ExprEng.getInitialState(L); @@ -118,34 +127,54 @@ bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps, } // Check if we have a steps limit - bool UnlimitedSteps = Steps == 0; + bool UnlimitedSteps = MaxSteps == 0; + // Cap our pre-reservation in the event that the user specifies // a very large number of maximum steps. const unsigned PreReservationCap = 4000000; if(!UnlimitedSteps) - G.reserve(std::min(Steps,PreReservationCap)); + G.reserve(std::min(MaxSteps, PreReservationCap)); - while (WList->hasWork()) { - if (!UnlimitedSteps) { - if (Steps == 0) { - NumReachedMaxSteps++; - break; + auto ProcessWList = [this, UnlimitedSteps](unsigned MaxSteps) { + unsigned Steps = MaxSteps; + while (WList->hasWork()) { + if (!UnlimitedSteps) { + if (Steps == 0) { + NumReachedMaxSteps++; + break; + } + --Steps; } - --Steps; - } - NumSteps++; + NumSteps++; + + const WorkListUnit &WU = WList->dequeue(); - const WorkListUnit& WU = WList->dequeue(); + // Set the current block counter. + setBlockCounter(WU.getBlockCounter()); - // Set the current block counter. - WList->setBlockCounter(WU.getBlockCounter()); + // Retrieve the node. + ExplodedNode *Node = WU.getNode(); - // Retrieve the node. - ExplodedNode *Node = WU.getNode(); + dispatchWorkItem(Node, Node->getLocation(), WU); + } + return MaxSteps - Steps; + }; + const unsigned STUSteps = ProcessWList(MaxSteps); - dispatchWorkItem(Node, Node->getLocation(), WU); + if (CTUWList) { + NumSTUSteps += STUSteps; + const unsigned MinCTUSteps = + this->ExprEng.getAnalysisManager().options.CTUMaxNodesMin; + const unsigned Pct = + this->ExprEng.getAnalysisManager().options.CTUMaxNodesPercentage; + unsigned MaxCTUSteps = std::max(STUSteps * Pct / 100, MinCTUSteps); + + WList = std::move(CTUWList); + const unsigned CTUSteps = ProcessWList(MaxCTUSteps); + NumCTUSteps += CTUSteps; } + ExprEng.processEndWorklist(); return WList->hasWork(); } @@ -282,7 +311,7 @@ void CoreEngine::HandleBlockEntrance(const BlockEntrance &L, BlockCounter Counter = WList->getBlockCounter(); Counter = BCounterFactory.IncrementCount(Counter, LC->getStackFrame(), BlockId); - WList->setBlockCounter(Counter); + setBlockCounter(Counter); // Process the entrance of the block. if (Optional<CFGElement> E = L.getFirstElement()) { diff --git a/clang/lib/StaticAnalyzer/Core/DynamicType.cpp b/clang/lib/StaticAnalyzer/Core/DynamicType.cpp index 9ed915aafcab..06052cb99fd1 100644 --- a/clang/lib/StaticAnalyzer/Core/DynamicType.cpp +++ b/clang/lib/StaticAnalyzer/Core/DynamicType.cpp @@ -209,7 +209,7 @@ static raw_ostream &printJson(const DynamicTypeInfo &DTI, raw_ostream &Out, if (ToPrint->isAnyPointerType()) ToPrint = ToPrint->getPointeeType(); - Out << '\"' << ToPrint.getAsString() << "\", \"sub_classable\": " + Out << '\"' << ToPrint << "\", \"sub_classable\": " << (DTI.canBeASubClass() ? "true" : "false"); } return Out; @@ -217,9 +217,9 @@ static raw_ostream &printJson(const DynamicTypeInfo &DTI, raw_ostream &Out, static raw_ostream &printJson(const DynamicCastInfo &DCI, raw_ostream &Out, const char *NL, unsigned int Space, bool IsDot) { - return Out << "\"from\": \"" << DCI.from().getAsString() << "\", \"to\": \"" - << DCI.to().getAsString() << "\", \"kind\": \"" - << (DCI.succeeds() ? "success" : "fail") << "\""; + return Out << "\"from\": \"" << DCI.from() << "\", \"to\": \"" << DCI.to() + << "\", \"kind\": \"" << (DCI.succeeds() ? "success" : "fail") + << "\""; } template <class T, class U> diff --git a/clang/lib/StaticAnalyzer/Core/Environment.cpp b/clang/lib/StaticAnalyzer/Core/Environment.cpp index 64e915a09ceb..719793fa224c 100644 --- a/clang/lib/StaticAnalyzer/Core/Environment.cpp +++ b/clang/lib/StaticAnalyzer/Core/Environment.cpp @@ -118,7 +118,7 @@ SVal Environment::getSVal(const EnvironmentEntry &Entry, case Stmt::SizeOfPackExprClass: case Stmt::PredefinedExprClass: // Known constants; defer to SValBuilder. - return svalBuilder.getConstantVal(cast<Expr>(S)).getValue(); + return *svalBuilder.getConstantVal(cast<Expr>(S)); case Stmt::ReturnStmtClass: { const auto *RS = cast<ReturnStmt>(S); diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index a170ef3885b2..45af22de50ae 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -7,7 +7,7 @@ //===----------------------------------------------------------------------===// // // This file defines a meta-engine for path-sensitive dataflow analysis that -// is built on GREngine, but provides the boilerplate to execute transfer +// is built on CoreEngine, but provides the boilerplate to execute transfer // functions and build the ExplodedGraph at the expression level. // //===----------------------------------------------------------------------===// @@ -118,18 +118,10 @@ namespace { /// the construction context was present and contained references to these /// AST nodes. class ConstructedObjectKey { - typedef std::pair<ConstructionContextItem, const LocationContext *> - ConstructedObjectKeyImpl; - + using ConstructedObjectKeyImpl = + std::pair<ConstructionContextItem, const LocationContext *>; const ConstructedObjectKeyImpl Impl; - const void *getAnyASTNodePtr() const { - if (const Stmt *S = getItem().getStmtOrNull()) - return S; - else - return getItem().getCXXCtorInitializer(); - } - public: explicit ConstructedObjectKey(const ConstructionContextItem &Item, const LocationContext *LC) @@ -200,24 +192,17 @@ REGISTER_TRAIT_WITH_PROGRAMSTATE(ObjectsUnderConstruction, static const char* TagProviderName = "ExprEngine"; ExprEngine::ExprEngine(cross_tu::CrossTranslationUnitContext &CTU, - AnalysisManager &mgr, - SetOfConstDecls *VisitedCalleesIn, - FunctionSummariesTy *FS, - InliningModes HowToInlineIn) - : CTU(CTU), AMgr(mgr), - AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()), + AnalysisManager &mgr, SetOfConstDecls *VisitedCalleesIn, + FunctionSummariesTy *FS, InliningModes HowToInlineIn) + : CTU(CTU), IsCTUEnabled(mgr.getAnalyzerOptions().IsNaiveCTUEnabled), + AMgr(mgr), AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()), Engine(*this, FS, mgr.getAnalyzerOptions()), G(Engine.getGraph()), StateMgr(getContext(), mgr.getStoreManagerCreator(), - mgr.getConstraintManagerCreator(), G.getAllocator(), - this), - SymMgr(StateMgr.getSymbolManager()), - MRMgr(StateMgr.getRegionManager()), - svalBuilder(StateMgr.getSValBuilder()), - ObjCNoRet(mgr.getASTContext()), - BR(mgr, *this), - VisitedCallees(VisitedCalleesIn), - HowToInline(HowToInlineIn) - { + mgr.getConstraintManagerCreator(), G.getAllocator(), this), + SymMgr(StateMgr.getSymbolManager()), MRMgr(StateMgr.getRegionManager()), + svalBuilder(StateMgr.getSValBuilder()), ObjCNoRet(mgr.getASTContext()), + BR(mgr, *this), VisitedCallees(VisitedCalleesIn), + HowToInline(HowToInlineIn) { unsigned TrimInterval = mgr.options.GraphTrimInterval; if (TrimInterval != 0) { // Enable eager node reclamation when constructing the ExplodedGraph. @@ -319,7 +304,7 @@ ProgramStateRef ExprEngine::createTemporaryRegionIfNeeded( if (!Result) { // If we don't have an explicit result expression, we're in "if needed" // mode. Only create a region if the current value is a NonLoc. - if (!InitValWithAdjustments.getAs<NonLoc>()) { + if (!isa<NonLoc>(InitValWithAdjustments)) { if (OutRegionWithAdjustments) *OutRegionWithAdjustments = nullptr; return State; @@ -328,7 +313,7 @@ ProgramStateRef ExprEngine::createTemporaryRegionIfNeeded( } else { // We need to create a region no matter what. Make sure we don't try to // stuff a Loc into a non-pointer temporary region. - assert(!InitValWithAdjustments.getAs<Loc>() || + assert(!isa<Loc>(InitValWithAdjustments) || Loc::isLocType(Result->getType()) || Result->getType()->isMemberPointerType()); } @@ -620,6 +605,8 @@ void ExprEngine::printJson(raw_ostream &Out, ProgramStateRef State, } void ExprEngine::processEndWorklist() { + // This prints the name of the top-level function if we crash. + PrettyStackTraceLocationContext CrashInfo(getRootLocationContext()); getCheckerManager().runCheckersForEndAnalysis(G, BR, *this); } @@ -1251,6 +1238,7 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, case Stmt::OMPParallelForSimdDirectiveClass: case Stmt::OMPParallelSectionsDirectiveClass: case Stmt::OMPParallelMasterDirectiveClass: + case Stmt::OMPParallelMaskedDirectiveClass: case Stmt::OMPTaskDirectiveClass: case Stmt::OMPTaskyieldDirectiveClass: case Stmt::OMPBarrierDirectiveClass: @@ -1274,9 +1262,13 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, case Stmt::OMPTaskLoopDirectiveClass: case Stmt::OMPTaskLoopSimdDirectiveClass: case Stmt::OMPMasterTaskLoopDirectiveClass: + case Stmt::OMPMaskedTaskLoopDirectiveClass: case Stmt::OMPMasterTaskLoopSimdDirectiveClass: + case Stmt::OMPMaskedTaskLoopSimdDirectiveClass: case Stmt::OMPParallelMasterTaskLoopDirectiveClass: + case Stmt::OMPParallelMaskedTaskLoopDirectiveClass: case Stmt::OMPParallelMasterTaskLoopSimdDirectiveClass: + case Stmt::OMPParallelMaskedTaskLoopSimdDirectiveClass: case Stmt::OMPDistributeDirectiveClass: case Stmt::OMPDistributeParallelForDirectiveClass: case Stmt::OMPDistributeParallelForSimdDirectiveClass: @@ -1297,6 +1289,10 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, case Stmt::OMPDispatchDirectiveClass: case Stmt::OMPMaskedDirectiveClass: case Stmt::OMPGenericLoopDirectiveClass: + case Stmt::OMPTeamsGenericLoopDirectiveClass: + case Stmt::OMPTargetTeamsGenericLoopDirectiveClass: + case Stmt::OMPParallelGenericLoopDirectiveClass: + case Stmt::OMPTargetParallelGenericLoopDirectiveClass: case Stmt::CapturedStmtClass: case Stmt::OMPUnrollDirectiveClass: case Stmt::OMPMetaDirectiveClass: { @@ -1342,8 +1338,9 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, case Stmt::GNUNullExprClass: { // GNU __null is a pointer-width integer, not an actual pointer. ProgramStateRef state = Pred->getState(); - state = state->BindExpr(S, Pred->getLocationContext(), - svalBuilder.makeIntValWithPtrWidth(0, false)); + state = state->BindExpr( + S, Pred->getLocationContext(), + svalBuilder.makeIntValWithWidth(getContext().VoidPtrTy, 0)); Bldr.generateNode(S, Pred, state); break; } @@ -1370,10 +1367,14 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred, break; } + case Stmt::ArrayInitLoopExprClass: + Bldr.takeNodes(Pred); + VisitArrayInitLoopExpr(cast<ArrayInitLoopExpr>(S), Pred, Dst); + Bldr.addNodes(Dst); + break; // Cases not handled yet; but will handle some day. case Stmt::DesignatedInitExprClass: case Stmt::DesignatedInitUpdateExprClass: - case Stmt::ArrayInitLoopExprClass: case Stmt::ArrayInitIndexExprClass: case Stmt::ExtVectorElementExprClass: case Stmt::ImaginaryLiteralClass: @@ -2343,7 +2344,7 @@ void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) { llvm_unreachable("No block with label."); } - if (V.getAs<loc::ConcreteInt>() || V.getAs<UndefinedVal>()) { + if (isa<UndefinedVal, loc::ConcreteInt>(V)) { // Dispatch to the first target and mark it as a sink. //ExplodedNode* N = builder.generateNode(builder.begin(), state, true); // FIXME: add checker visit. @@ -2598,15 +2599,144 @@ void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D, // operator&. return; } - if (isa<BindingDecl>(D)) { - // FIXME: proper support for bound declarations. - // For now, let's just prevent crashing. + if (const auto *BD = dyn_cast<BindingDecl>(D)) { + const auto *DD = cast<DecompositionDecl>(BD->getDecomposedDecl()); + + SVal Base = state->getLValue(DD, LCtx); + if (DD->getType()->isReferenceType()) { + Base = state->getSVal(Base.getAsRegion()); + } + + SVal V = UnknownVal(); + + // Handle binding to data members + if (const auto *ME = dyn_cast<MemberExpr>(BD->getBinding())) { + const auto *Field = cast<FieldDecl>(ME->getMemberDecl()); + V = state->getLValue(Field, Base); + } + // Handle binding to arrays + else if (const auto *ASE = dyn_cast<ArraySubscriptExpr>(BD->getBinding())) { + SVal Idx = state->getSVal(ASE->getIdx(), LCtx); + + // Note: the index of an element in a structured binding is automatically + // created and it is a unique identifier of the specific element. Thus it + // cannot be a value that varies at runtime. + assert(Idx.isConstant() && "BindingDecl array index is not a constant!"); + + V = state->getLValue(BD->getType(), Idx, Base); + } + // Handle binding to tuple-like strcutures + else if (BD->getHoldingVar()) { + // FIXME: handle tuples + return; + } else + llvm_unreachable("An unknown case of structured binding encountered!"); + + if (BD->getType()->isReferenceType()) + V = state->getSVal(V.getAsRegion()); + + Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr, + ProgramPoint::PostLValueKind); + return; } llvm_unreachable("Support for this Decl not implemented."); } +/// VisitArrayInitLoopExpr - Transfer function for array init loop. +void ExprEngine::VisitArrayInitLoopExpr(const ArrayInitLoopExpr *Ex, + ExplodedNode *Pred, + ExplodedNodeSet &Dst) { + ExplodedNodeSet CheckerPreStmt; + getCheckerManager().runCheckersForPreStmt(CheckerPreStmt, Pred, Ex, *this); + + ExplodedNodeSet EvalSet; + StmtNodeBuilder Bldr(CheckerPreStmt, EvalSet, *currBldrCtx); + + const Expr *Arr = Ex->getCommonExpr()->getSourceExpr(); + + for (auto *Node : CheckerPreStmt) { + const LocationContext *LCtx = Node->getLocationContext(); + ProgramStateRef state = Node->getState(); + + SVal Base = UnknownVal(); + + // As in case of this expression the sub-expressions are not visited by any + // other transfer functions, they are handled by matching their AST. + + // Case of implicit copy or move ctor of object with array member + // + // Note: ExprEngine::VisitMemberExpr is not able to bind the array to the + // environment. + // + // struct S { + // int arr[2]; + // }; + // + // + // S a; + // S b = a; + // + // The AST in case of a *copy constructor* looks like this: + // ArrayInitLoopExpr + // |-OpaqueValueExpr + // | `-MemberExpr <-- match this + // | `-DeclRefExpr + // ` ... + // + // + // S c; + // S d = std::move(d); + // + // In case of a *move constructor* the resulting AST looks like: + // ArrayInitLoopExpr + // |-OpaqueValueExpr + // | `-MemberExpr <-- match this first + // | `-CXXStaticCastExpr <-- match this after + // | `-DeclRefExpr + // ` ... + if (const auto *ME = dyn_cast<MemberExpr>(Arr)) { + Expr *MEBase = ME->getBase(); + + // Move ctor + if (auto CXXSCE = dyn_cast<CXXStaticCastExpr>(MEBase)) { + MEBase = CXXSCE->getSubExpr(); + } + + auto ObjDeclExpr = cast<DeclRefExpr>(MEBase); + SVal Obj = state->getLValue(cast<VarDecl>(ObjDeclExpr->getDecl()), LCtx); + + Base = state->getLValue(cast<FieldDecl>(ME->getMemberDecl()), Obj); + } + + // Case of lambda capture and decomposition declaration + // + // int arr[2]; + // + // [arr]{ int a = arr[0]; }(); + // auto[a, b] = arr; + // + // In both of these cases the AST looks like the following: + // ArrayInitLoopExpr + // |-OpaqueValueExpr + // | `-DeclRefExpr <-- match this + // ` ... + if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Arr)) + Base = state->getLValue(cast<VarDecl>(DRE->getDecl()), LCtx); + + // Create a lazy compound value to the original array + if (const MemRegion *R = Base.getAsRegion()) + Base = state->getSVal(R); + else + Base = UnknownVal(); + + Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, Base)); + } + + getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, Ex, *this); +} + /// VisitArraySubscriptExpr - Transfer function for array accesses void ExprEngine::VisitArraySubscriptExpr(const ArraySubscriptExpr *A, ExplodedNode *Pred, @@ -2894,7 +3024,7 @@ void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE, // If the location is not a 'Loc', it will already be handled by // the checkers. There is nothing left to do. - if (!location.getAs<Loc>()) { + if (!isa<Loc>(location)) { const ProgramPoint L = PostStore(StoreE, LC, /*Loc*/nullptr, /*tag*/nullptr); ProgramStateRef state = Pred->getState(); @@ -2964,7 +3094,7 @@ void ExprEngine::evalLoad(ExplodedNodeSet &Dst, SVal location, const ProgramPointTag *tag, QualType LoadTy) { - assert(!location.getAs<NonLoc>() && "location cannot be a NonLoc."); + assert(!isa<NonLoc>(location) && "location cannot be a NonLoc."); assert(NodeEx); assert(BoundEx); // Evaluate the location (checks for bad dereferences). @@ -3095,7 +3225,7 @@ void ExprEngine::VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred, for (const Expr *O : A->outputs()) { SVal X = state->getSVal(O, Pred->getLocationContext()); - assert(!X.getAs<NonLoc>()); // Should be an Lval, or unknown, undef. + assert(!isa<NonLoc>(X)); // Should be an Lval, or unknown, undef. if (Optional<Loc> LV = X.getAs<Loc>()) state = state->bindLoc(*LV, UnknownVal(), Pred->getLocationContext()); @@ -3114,7 +3244,6 @@ void ExprEngine::VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred, // Visualization. //===----------------------------------------------------------------------===// -#ifndef NDEBUG namespace llvm { template<> @@ -3212,29 +3341,18 @@ struct DOTGraphTraits<ExplodedGraph*> : public DefaultDOTGraphTraits { }; } // namespace llvm -#endif void ExprEngine::ViewGraph(bool trim) { -#ifndef NDEBUG std::string Filename = DumpGraph(trim); llvm::DisplayGraph(Filename, false, llvm::GraphProgram::DOT); -#else - llvm::errs() << "Warning: viewing graph requires assertions" << "\n"; -#endif } - -void ExprEngine::ViewGraph(ArrayRef<const ExplodedNode*> Nodes) { -#ifndef NDEBUG +void ExprEngine::ViewGraph(ArrayRef<const ExplodedNode *> Nodes) { std::string Filename = DumpGraph(Nodes); llvm::DisplayGraph(Filename, false, llvm::GraphProgram::DOT); -#else - llvm::errs() << "Warning: viewing graph requires assertions" << "\n"; -#endif } std::string ExprEngine::DumpGraph(bool trim, StringRef Filename) { -#ifndef NDEBUG if (trim) { std::vector<const ExplodedNode *> Src; @@ -3249,35 +3367,26 @@ std::string ExprEngine::DumpGraph(bool trim, StringRef Filename) { Src.push_back(N); } return DumpGraph(Src, Filename); - } else { - return llvm::WriteGraph(&G, "ExprEngine", /*ShortNames=*/false, - /*Title=*/"Exploded Graph", - /*Filename=*/std::string(Filename)); } -#else - llvm::errs() << "Warning: dumping graph requires assertions" << "\n"; - return ""; -#endif + + return llvm::WriteGraph(&G, "ExprEngine", /*ShortNames=*/false, + /*Title=*/"Exploded Graph", + /*Filename=*/std::string(Filename)); } -std::string ExprEngine::DumpGraph(ArrayRef<const ExplodedNode*> Nodes, +std::string ExprEngine::DumpGraph(ArrayRef<const ExplodedNode *> Nodes, StringRef Filename) { -#ifndef NDEBUG std::unique_ptr<ExplodedGraph> TrimmedG(G.trim(Nodes)); if (!TrimmedG.get()) { llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n"; return ""; - } else { - return llvm::WriteGraph(TrimmedG.get(), "TrimmedExprEngine", - /*ShortNames=*/false, - /*Title=*/"Trimmed Exploded Graph", - /*Filename=*/std::string(Filename)); } -#else - llvm::errs() << "Warning: dumping graph requires assertions" << "\n"; - return ""; -#endif + + return llvm::WriteGraph(TrimmedG.get(), "TrimmedExprEngine", + /*ShortNames=*/false, + /*Title=*/"Trimmed Exploded Graph", + /*Filename=*/std::string(Filename)); } void *ProgramStateTrait<ReplayWithoutInlining>::GDMIndex() { diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngineC.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngineC.cpp index 302a971a15f2..43e298f3de08 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngineC.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngineC.cpp @@ -29,8 +29,7 @@ static SVal conjureOffsetSymbolOnLocation( SVal Symbol, SVal Other, Expr* Expression, SValBuilder &svalBuilder, unsigned Count, const LocationContext *LCtx) { QualType Ty = Expression->getType(); - if (Other.getAs<Loc>() && - Ty->isIntegralOrEnumerationType() && + if (isa<Loc>(Other) && Ty->isIntegralOrEnumerationType() && Symbol.isUnknown()) { return svalBuilder.conjureSymbolVal(Expression, LCtx, Ty, Count); } @@ -271,8 +270,9 @@ ProgramStateRef ExprEngine::handleLValueBitCast( SVal OrigV = state->getSVal(Ex, LCtx); SVal V = svalBuilder.evalCast(OrigV, T, ExTy); // Negate the result if we're treating the boolean as a signed i1 - if (CastE->getCastKind() == CK_BooleanToSignedIntegral) - V = evalMinus(V); + if (CastE->getCastKind() == CK_BooleanToSignedIntegral && V.isValid()) + V = svalBuilder.evalMinus(V.castAs<NonLoc>()); + state = state->BindExpr(CastE, LCtx, V); if (V.isUnknown() && !OrigV.isUnknown()) { state = escapeValues(state, OrigV, PSK_EscapeOther); @@ -371,7 +371,7 @@ void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex, case CK_IntegralToPointer: case CK_PointerToIntegral: { SVal V = state->getSVal(Ex, LCtx); - if (V.getAs<nonloc::PointerToMember>()) { + if (isa<nonloc::PointerToMember>(V)) { state = state->BindExpr(CastE, LCtx, UnknownVal()); Bldr.generateNode(CastE, Pred, state); continue; @@ -460,7 +460,8 @@ void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex, continue; } else { // If the cast fails on a pointer, bind to 0. - state = state->BindExpr(CastE, LCtx, svalBuilder.makeNull()); + state = state->BindExpr(CastE, LCtx, + svalBuilder.makeNullWithType(resultType)); } } else { // If we don't know if the cast succeeded, conjure a new symbol. @@ -498,7 +499,7 @@ void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex, continue; } case CK_NullToPointer: { - SVal V = svalBuilder.makeNull(); + SVal V = svalBuilder.makeNullWithType(CastE->getType()); state = state->BindExpr(CastE, LCtx, V); Bldr.generateNode(CastE, Pred, state); continue; @@ -1028,11 +1029,13 @@ void ExprEngine::VisitUnaryOperator(const UnaryOperator* U, ExplodedNode *Pred, llvm_unreachable("Invalid Opcode."); case UO_Not: // FIXME: Do we need to handle promotions? - state = state->BindExpr(U, LCtx, evalComplement(V.castAs<NonLoc>())); + state = state->BindExpr( + U, LCtx, svalBuilder.evalComplement(V.castAs<NonLoc>())); break; case UO_Minus: // FIXME: Do we need to handle promotions? - state = state->BindExpr(U, LCtx, evalMinus(V.castAs<NonLoc>())); + state = state->BindExpr(U, LCtx, + svalBuilder.evalMinus(V.castAs<NonLoc>())); break; case UO_LNot: // C99 6.5.3.3: "The expression !E is equivalent to (0==E)." diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp index ba105f34a915..6d979da2755f 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp @@ -883,13 +883,10 @@ void ExprEngine::VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred, // where new can return NULL. If we end up supporting that option, we can // consider adding a check for it here. // C++11 [basic.stc.dynamic.allocation]p3. - if (FD) { - QualType Ty = FD->getType(); - if (const auto *ProtoType = Ty->getAs<FunctionProtoType>()) - if (!ProtoType->isNothrow()) - if (auto dSymVal = symVal.getAs<DefinedOrUnknownSVal>()) - State = State->assume(*dSymVal, true); - } + if (const auto *ProtoType = FD->getType()->getAs<FunctionProtoType>()) + if (!ProtoType->isNothrow()) + if (auto dSymVal = symVal.getAs<DefinedOrUnknownSVal>()) + State = State->assume(*dSymVal, true); } StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx); @@ -914,7 +911,7 @@ void ExprEngine::VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred, // CXXNewExpr, we need to make sure that the constructed object is not // immediately invalidated here. (The placement call should happen before // the constructor call anyway.) - if (FD && FD->isReservedGlobalPlacementOperator()) { + if (FD->isReservedGlobalPlacementOperator()) { // Non-array placement new should always return the placement location. SVal PlacementLoc = State->getSVal(CNE->getPlacementArg(0), LCtx); Result = svalBuilder.evalCast(PlacementLoc, CNE->getType(), @@ -948,8 +945,17 @@ void ExprEngine::VisitCXXDeleteExpr(const CXXDeleteExpr *CDE, ExplodedNodeSet DstPreCall; getCheckerManager().runCheckersForPreCall(DstPreCall, Pred, *Call, *this); + ExplodedNodeSet DstPostCall; - getCheckerManager().runCheckersForPostCall(Dst, DstPreCall, *Call, *this); + if (AMgr.getAnalyzerOptions().MayInlineCXXAllocator) { + StmtNodeBuilder Bldr(DstPreCall, DstPostCall, *currBldrCtx); + for (ExplodedNode *I : DstPreCall) { + defaultEvalCall(Bldr, I, *Call); + } + } else { + DstPostCall = DstPreCall; + } + getCheckerManager().runCheckersForPostCall(Dst, DstPostCall, *Call, *this); } void ExprEngine::VisitCXXCatchStmt(const CXXCatchStmt *CS, ExplodedNode *Pred, diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp index e6918e071a4f..5f8a84591b2a 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp @@ -129,7 +129,7 @@ static std::pair<const Stmt*, static SVal adjustReturnValue(SVal V, QualType ExpectedTy, QualType ActualTy, StoreManager &StoreMgr) { // For now, the only adjustments we handle apply only to locations. - if (!V.getAs<Loc>()) + if (!isa<Loc>(V)) return V; // If the types already match, don't do any unnecessary work. @@ -427,10 +427,39 @@ namespace { REGISTER_MAP_WITH_PROGRAMSTATE(DynamicDispatchBifurcationMap, const MemRegion *, unsigned) +REGISTER_TRAIT_WITH_PROGRAMSTATE(CTUDispatchBifurcation, bool) -bool ExprEngine::inlineCall(const CallEvent &Call, const Decl *D, - NodeBuilder &Bldr, ExplodedNode *Pred, - ProgramStateRef State) { +void ExprEngine::ctuBifurcate(const CallEvent &Call, const Decl *D, + NodeBuilder &Bldr, ExplodedNode *Pred, + ProgramStateRef State) { + ProgramStateRef ConservativeEvalState = nullptr; + if (Call.isForeign() && !isSecondPhaseCTU()) { + const auto IK = AMgr.options.getCTUPhase1Inlining(); + const bool DoInline = IK == CTUPhase1InliningKind::All || + (IK == CTUPhase1InliningKind::Small && + isSmall(AMgr.getAnalysisDeclContext(D))); + if (DoInline) { + inlineCall(Engine.getWorkList(), Call, D, Bldr, Pred, State); + return; + } + const bool BState = State->get<CTUDispatchBifurcation>(); + if (!BState) { // This is the first time we see this foreign function. + // Enqueue it to be analyzed in the second (ctu) phase. + inlineCall(Engine.getCTUWorkList(), Call, D, Bldr, Pred, State); + // Conservatively evaluate in the first phase. + ConservativeEvalState = State->set<CTUDispatchBifurcation>(true); + conservativeEvalCall(Call, Bldr, Pred, ConservativeEvalState); + } else { + conservativeEvalCall(Call, Bldr, Pred, State); + } + return; + } + inlineCall(Engine.getWorkList(), Call, D, Bldr, Pred, State); +} + +void ExprEngine::inlineCall(WorkList *WList, const CallEvent &Call, + const Decl *D, NodeBuilder &Bldr, + ExplodedNode *Pred, ProgramStateRef State) { assert(D); const LocationContext *CurLC = Pred->getLocationContext(); @@ -465,7 +494,7 @@ bool ExprEngine::inlineCall(const CallEvent &Call, const Decl *D, if (ExplodedNode *N = G.getNode(Loc, State, false, &isNew)) { N->addPredecessor(Pred, G); if (isNew) - Engine.getWorkList()->enqueue(N); + WList->enqueue(N); } // If we decided to inline the call, the successor has been manually @@ -475,11 +504,17 @@ bool ExprEngine::inlineCall(const CallEvent &Call, const Decl *D, NumInlinedCalls++; Engine.FunctionSummaries->bumpNumTimesInlined(D); - // Mark the decl as visited. - if (VisitedCallees) - VisitedCallees->insert(D); - - return true; + // Do not mark as visited in the 2nd run (CTUWList), so the function will + // be visited as top-level, this way we won't loose reports in non-ctu + // mode. Considering the case when a function in a foreign TU calls back + // into the main TU. + // Note, during the 1st run, it doesn't matter if we mark the foreign + // functions as visited (or not) because they can never appear as a top level + // function in the main TU. + if (!isSecondPhaseCTU()) + // Mark the decl as visited. + if (VisitedCallees) + VisitedCallees->insert(D); } static ProgramStateRef getInlineFailedState(ProgramStateRef State, @@ -697,7 +732,7 @@ ProgramStateRef ExprEngine::bindReturnValue(const CallEvent &Call, // Store the extent of the allocated object(s). SVal ElementCount; - if (const Expr *SizeExpr = CNE->getArraySize().getValueOr(nullptr)) { + if (const Expr *SizeExpr = CNE->getArraySize().value_or(nullptr)) { ElementCount = State->getSVal(SizeExpr, LCtx); } else { ElementCount = svalBuilder.makeIntVal(1, /*IsUnsigned=*/true); @@ -980,7 +1015,7 @@ bool ExprEngine::shouldInlineCall(const CallEvent &Call, const Decl *D, // Check if this function has been marked as non-inlinable. Optional<bool> MayInline = Engine.FunctionSummaries->mayInline(D); - if (MayInline.hasValue()) { + if (MayInline) { if (!MayInline.getValue()) return false; @@ -1002,7 +1037,7 @@ bool ExprEngine::shouldInlineCall(const CallEvent &Call, const Decl *D, CallInlinePolicy CIP = mayInlineCallKind(Call, Pred, Opts, CallOpts); if (CIP != CIP_Allowed) { if (CIP == CIP_DisallowedAlways) { - assert(!MayInline.hasValue() || MayInline.getValue()); + assert(!MayInline || *MayInline); Engine.FunctionSummaries->markShouldNotInline(D); } return false; @@ -1068,6 +1103,7 @@ void ExprEngine::defaultEvalCall(NodeBuilder &Bldr, ExplodedNode *Pred, State = InlinedFailedState; } else { RuntimeDefinition RD = Call->getRuntimeDefinition(); + Call->setForeign(RD.isForeign()); const Decl *D = RD.getDecl(); if (shouldInlineCall(*Call, D, Pred, CallOpts)) { if (RD.mayHaveOtherDefinitions()) { @@ -1085,10 +1121,8 @@ void ExprEngine::defaultEvalCall(NodeBuilder &Bldr, ExplodedNode *Pred, return; } } - - // We are not bifurcating and we do have a Decl, so just inline. - if (inlineCall(*Call, D, Bldr, Pred, State)) - return; + ctuBifurcate(*Call, D, Bldr, Pred, State); + return; } } @@ -1110,8 +1144,7 @@ void ExprEngine::BifurcateCall(const MemRegion *BifurReg, if (BState) { // If we are on "inline path", keep inlining if possible. if (*BState == DynamicDispatchModeInlined) - if (inlineCall(Call, D, Bldr, Pred, State)) - return; + ctuBifurcate(Call, D, Bldr, Pred, State); // If inline failed, or we are on the path where we assume we // don't have enough info about the receiver to inline, conjure the // return value and invalidate the regions. @@ -1124,7 +1157,7 @@ void ExprEngine::BifurcateCall(const MemRegion *BifurReg, ProgramStateRef IState = State->set<DynamicDispatchBifurcationMap>(BifurReg, DynamicDispatchModeInlined); - inlineCall(Call, D, Bldr, Pred, IState); + ctuBifurcate(Call, D, Bldr, Pred, IState); ProgramStateRef NoIState = State->set<DynamicDispatchBifurcationMap>(BifurReg, diff --git a/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp b/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp index 8bf6fc085c6a..506d61d94d5f 100644 --- a/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp +++ b/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp @@ -264,8 +264,8 @@ bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx, Matches[0].getNodeAs<IntegerLiteral>("initNum")->getValue(); auto CondOp = Matches[0].getNodeAs<BinaryOperator>("conditionOperator"); if (InitNum.getBitWidth() != BoundNum.getBitWidth()) { - InitNum = InitNum.zextOrSelf(BoundNum.getBitWidth()); - BoundNum = BoundNum.zextOrSelf(InitNum.getBitWidth()); + InitNum = InitNum.zext(BoundNum.getBitWidth()); + BoundNum = BoundNum.zext(InitNum.getBitWidth()); } if (CondOp->getOpcode() == BO_GE || CondOp->getOpcode() == BO_LE) diff --git a/clang/lib/StaticAnalyzer/Core/MemRegion.cpp b/clang/lib/StaticAnalyzer/Core/MemRegion.cpp index 58bea12f8783..f0cda835e07c 100644 --- a/clang/lib/StaticAnalyzer/Core/MemRegion.cpp +++ b/clang/lib/StaticAnalyzer/Core/MemRegion.cpp @@ -162,7 +162,9 @@ const StackFrameContext *VarRegion::getStackFrame() const { } ObjCIvarRegion::ObjCIvarRegion(const ObjCIvarDecl *ivd, const SubRegion *sReg) - : DeclRegion(sReg, ObjCIvarRegionKind), IVD(ivd) {} + : DeclRegion(sReg, ObjCIvarRegionKind), IVD(ivd) { + assert(IVD); +} const ObjCIvarDecl *ObjCIvarRegion::getDecl() const { return IVD; } @@ -480,7 +482,7 @@ void CompoundLiteralRegion::dumpToStream(raw_ostream &os) const { } void CXXTempObjectRegion::dumpToStream(raw_ostream &os) const { - os << "temp_object{" << getValueType().getAsString() << ", " + os << "temp_object{" << getValueType() << ", " << "S" << Ex->getID(getContext()) << '}'; } @@ -497,8 +499,8 @@ void CXXThisRegion::dumpToStream(raw_ostream &os) const { } void ElementRegion::dumpToStream(raw_ostream &os) const { - os << "Element{" << superRegion << ',' - << Index << ',' << getElementType().getAsString() << '}'; + os << "Element{" << superRegion << ',' << Index << ',' << getElementType() + << '}'; } void FieldRegion::dumpToStream(raw_ostream &os) const { @@ -971,26 +973,14 @@ const VarRegion *MemRegionManager::getVarRegion(const VarDecl *D, const MemRegion *sReg = nullptr; if (D->hasGlobalStorage() && !D->isStaticLocal()) { - - // First handle the globals defined in system headers. - if (Ctx.getSourceManager().isInSystemHeader(D->getLocation())) { - // Allow the system globals which often DO GET modified, assume the - // rest are immutable. - if (D->getName().contains("errno")) - sReg = getGlobalsRegion(MemRegion::GlobalSystemSpaceRegionKind); - else - sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind); - - // Treat other globals as GlobalInternal unless they are constants. + QualType Ty = D->getType(); + assert(!Ty.isNull()); + if (Ty.isConstQualified()) { + sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind); + } else if (Ctx.getSourceManager().isInSystemHeader(D->getLocation())) { + sReg = getGlobalsRegion(MemRegion::GlobalSystemSpaceRegionKind); } else { - QualType GQT = D->getType(); - const Type *GT = GQT.getTypePtrOrNull(); - // TODO: We could walk the complex types here and see if everything is - // constified. - if (GT && GQT.isConstQualified() && GT->isArithmeticType()) - sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind); - else - sReg = getGlobalsRegion(); + sReg = getGlobalsRegion(MemRegion::GlobalInternalSpaceRegionKind); } // Finally handle static locals. @@ -1033,8 +1023,10 @@ const VarRegion *MemRegionManager::getVarRegion(const VarDecl *D, T = TSI->getType(); if (T.isNull()) T = getContext().VoidTy; - if (!T->getAs<FunctionType>()) - T = getContext().getFunctionNoProtoType(T); + if (!T->getAs<FunctionType>()) { + FunctionProtoType::ExtProtoInfo Ext; + T = getContext().getFunctionType(T, None, Ext); + } T = getContext().getBlockPointerType(T); const BlockCodeRegion *BTR = @@ -1153,9 +1145,12 @@ MemRegionManager::getBlockCodeRegion(const BlockDecl *BD, CanQualType locTy, return getSubRegion<BlockCodeRegion>(BD, locTy, AC, getCodeRegion()); } -/// getSymbolicRegion - Retrieve or create a "symbolic" memory region. -const SymbolicRegion *MemRegionManager::getSymbolicRegion(SymbolRef sym) { - return getSubRegion<SymbolicRegion>(sym, getUnknownRegion()); +const SymbolicRegion * +MemRegionManager::getSymbolicRegion(SymbolRef sym, + const MemSpaceRegion *MemSpace) { + if (MemSpace == nullptr) + MemSpace = getUnknownRegion(); + return getSubRegion<SymbolicRegion>(sym, MemSpace); } const SymbolicRegion *MemRegionManager::getSymbolicHeapRegion(SymbolRef Sym) { diff --git a/clang/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp b/clang/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp index 92104d628711..93c19a688b9a 100644 --- a/clang/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp +++ b/clang/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp @@ -389,7 +389,7 @@ void PlistPrinter::ReportMacroExpansions(raw_ostream &o, unsigned indent) { const Optional<StringRef> ExpansionText = getExpandedMacro(MacroExpansionLoc, CTU, MacroExpansions, SM); - if (!MacroName.hasValue() || !ExpansionText.hasValue()) + if (!MacroName || !ExpansionText) continue; Indent(o, indent) << "<dict>\n"; diff --git a/clang/lib/StaticAnalyzer/Core/ProgramState.cpp b/clang/lib/StaticAnalyzer/Core/ProgramState.cpp index 8d4e0bbb7dec..a6d0e242924b 100644 --- a/clang/lib/StaticAnalyzer/Core/ProgramState.cpp +++ b/clang/lib/StaticAnalyzer/Core/ProgramState.cpp @@ -55,7 +55,7 @@ ProgramState::ProgramState(ProgramStateManager *mgr, const Environment& env, ProgramState::ProgramState(const ProgramState &RHS) : stateMgr(RHS.stateMgr), Env(RHS.Env), store(RHS.store), GDM(RHS.GDM), - refCount(0) { + PosteriorlyOverconstrained(RHS.PosteriorlyOverconstrained), refCount(0) { stateMgr->getStoreManager().incrementReferenceCount(store); } @@ -216,7 +216,7 @@ ProgramState::invalidateRegionsImpl(ValueList Values, } ProgramStateRef ProgramState::killBinding(Loc LV) const { - assert(!LV.getAs<loc::MemRegionVal>() && "Use invalidateRegion instead."); + assert(!isa<loc::MemRegionVal>(LV) && "Use invalidateRegion instead."); Store OldStore = getStore(); const StoreRef &newStore = @@ -314,12 +314,12 @@ ProgramStateRef ProgramState::BindExpr(const Stmt *S, return getStateManager().getPersistentState(NewSt); } -ProgramStateRef ProgramState::assumeInBound(DefinedOrUnknownSVal Idx, - DefinedOrUnknownSVal UpperBound, - bool Assumption, - QualType indexTy) const { +LLVM_NODISCARD std::pair<ProgramStateRef, ProgramStateRef> +ProgramState::assumeInBoundDual(DefinedOrUnknownSVal Idx, + DefinedOrUnknownSVal UpperBound, + QualType indexTy) const { if (Idx.isUnknown() || UpperBound.isUnknown()) - return this; + return {this, this}; // Build an expression for 0 <= Idx < UpperBound. // This is the same as Idx + MIN < UpperBound + MIN, if overflow is allowed. @@ -338,7 +338,7 @@ ProgramStateRef ProgramState::assumeInBound(DefinedOrUnknownSVal Idx, SVal newIdx = svalBuilder.evalBinOpNN(this, BO_Add, Idx.castAs<NonLoc>(), Min, indexTy); if (newIdx.isUnknownOrUndef()) - return this; + return {this, this}; // Adjust the upper bound. SVal newBound = @@ -346,17 +346,26 @@ ProgramStateRef ProgramState::assumeInBound(DefinedOrUnknownSVal Idx, Min, indexTy); if (newBound.isUnknownOrUndef()) - return this; + return {this, this}; // Build the actual comparison. SVal inBound = svalBuilder.evalBinOpNN(this, BO_LT, newIdx.castAs<NonLoc>(), newBound.castAs<NonLoc>(), Ctx.IntTy); if (inBound.isUnknownOrUndef()) - return this; + return {this, this}; // Finally, let the constraint manager take care of it. ConstraintManager &CM = SM.getConstraintManager(); - return CM.assume(this, inBound.castAs<DefinedSVal>(), Assumption); + return CM.assumeDual(this, inBound.castAs<DefinedSVal>()); +} + +ProgramStateRef ProgramState::assumeInBound(DefinedOrUnknownSVal Idx, + DefinedOrUnknownSVal UpperBound, + bool Assumption, + QualType indexTy) const { + std::pair<ProgramStateRef, ProgramStateRef> R = + assumeInBoundDual(Idx, UpperBound, indexTy); + return Assumption ? R.first : R.second; } ConditionTruthVal ProgramState::isNonNull(SVal V) const { @@ -429,6 +438,12 @@ ProgramStateRef ProgramState::makeWithStore(const StoreRef &store) const { return getStateManager().getPersistentState(NewSt); } +ProgramStateRef ProgramState::cloneAsPosteriorlyOverconstrained() const { + ProgramState NewSt(*this); + NewSt.PosteriorlyOverconstrained = true; + return getStateManager().getPersistentState(NewSt); +} + void ProgramState::setStore(const StoreRef &newStore) { Store newStoreStore = newStore.getStore(); if (newStoreStore) diff --git a/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp b/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp index 4b0d4942e528..e788a7a60830 100644 --- a/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp +++ b/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp @@ -20,8 +20,8 @@ #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/ImmutableSet.h" #include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/StringExtras.h" #include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/StringExtras.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/raw_ostream.h" #include <algorithm> @@ -353,6 +353,21 @@ const llvm::APSInt &RangeSet::getMaxValue() const { return std::prev(end())->To(); } +bool clang::ento::RangeSet::isUnsigned() const { + assert(!isEmpty()); + return begin()->From().isUnsigned(); +} + +uint32_t clang::ento::RangeSet::getBitWidth() const { + assert(!isEmpty()); + return begin()->From().getBitWidth(); +} + +APSIntType clang::ento::RangeSet::getAPSIntType() const { + assert(!isEmpty()); + return APSIntType(begin()->From()); +} + bool RangeSet::containsImpl(llvm::APSInt &Point) const { if (isEmpty() || !pin(Point)) return false; @@ -655,6 +670,181 @@ RangeSet RangeSet::Factory::negate(RangeSet What) { return makePersistent(std::move(Result)); } +// Convert range set to the given integral type using truncation and promotion. +// This works similar to APSIntType::apply function but for the range set. +RangeSet RangeSet::Factory::castTo(RangeSet What, APSIntType Ty) { + // Set is empty or NOOP (aka cast to the same type). + if (What.isEmpty() || What.getAPSIntType() == Ty) + return What; + + const bool IsConversion = What.isUnsigned() != Ty.isUnsigned(); + const bool IsTruncation = What.getBitWidth() > Ty.getBitWidth(); + const bool IsPromotion = What.getBitWidth() < Ty.getBitWidth(); + + if (IsTruncation) + return makePersistent(truncateTo(What, Ty)); + + // Here we handle 2 cases: + // - IsConversion && !IsPromotion. + // In this case we handle changing a sign with same bitwidth: char -> uchar, + // uint -> int. Here we convert negatives to positives and positives which + // is out of range to negatives. We use convertTo function for that. + // - IsConversion && IsPromotion && !What.isUnsigned(). + // In this case we handle changing a sign from signeds to unsigneds with + // higher bitwidth: char -> uint, int-> uint64. The point is that we also + // need convert negatives to positives and use convertTo function as well. + // For example, we don't need such a convertion when converting unsigned to + // signed with higher bitwidth, because all the values of unsigned is valid + // for the such signed. + if (IsConversion && (!IsPromotion || !What.isUnsigned())) + return makePersistent(convertTo(What, Ty)); + + assert(IsPromotion && "Only promotion operation from unsigneds left."); + return makePersistent(promoteTo(What, Ty)); +} + +RangeSet RangeSet::Factory::castTo(RangeSet What, QualType T) { + assert(T->isIntegralOrEnumerationType() && "T shall be an integral type."); + return castTo(What, ValueFactory.getAPSIntType(T)); +} + +RangeSet::ContainerType RangeSet::Factory::truncateTo(RangeSet What, + APSIntType Ty) { + using llvm::APInt; + using llvm::APSInt; + ContainerType Result; + ContainerType Dummy; + // CastRangeSize is an amount of all possible values of cast type. + // Example: `char` has 256 values; `short` has 65536 values. + // But in fact we use `amount of values` - 1, because + // we can't keep `amount of values of UINT64` inside uint64_t. + // E.g. 256 is an amount of all possible values of `char` and we can't keep + // it inside `char`. + // And it's OK, it's enough to do correct calculations. + uint64_t CastRangeSize = APInt::getMaxValue(Ty.getBitWidth()).getZExtValue(); + for (const Range &R : What) { + // Get bounds of the given range. + APSInt FromInt = R.From(); + APSInt ToInt = R.To(); + // CurrentRangeSize is an amount of all possible values of the current + // range minus one. + uint64_t CurrentRangeSize = (ToInt - FromInt).getZExtValue(); + // This is an optimization for a specific case when this Range covers + // the whole range of the target type. + Dummy.clear(); + if (CurrentRangeSize >= CastRangeSize) { + Dummy.emplace_back(ValueFactory.getMinValue(Ty), + ValueFactory.getMaxValue(Ty)); + Result = std::move(Dummy); + break; + } + // Cast the bounds. + Ty.apply(FromInt); + Ty.apply(ToInt); + const APSInt &PersistentFrom = ValueFactory.getValue(FromInt); + const APSInt &PersistentTo = ValueFactory.getValue(ToInt); + if (FromInt > ToInt) { + Dummy.emplace_back(ValueFactory.getMinValue(Ty), PersistentTo); + Dummy.emplace_back(PersistentFrom, ValueFactory.getMaxValue(Ty)); + } else + Dummy.emplace_back(PersistentFrom, PersistentTo); + // Every range retrieved after truncation potentialy has garbage values. + // So, we have to unite every next range with the previouses. + Result = unite(Result, Dummy); + } + + return Result; +} + +// Divide the convertion into two phases (presented as loops here). +// First phase(loop) works when casted values go in ascending order. +// E.g. char{1,3,5,127} -> uint{1,3,5,127} +// Interrupt the first phase and go to second one when casted values start +// go in descending order. That means that we crossed over the middle of +// the type value set (aka 0 for signeds and MAX/2+1 for unsigneds). +// For instance: +// 1: uchar{1,3,5,128,255} -> char{1,3,5,-128,-1} +// Here we put {1,3,5} to one array and {-128, -1} to another +// 2: char{-128,-127,-1,0,1,2} -> uchar{128,129,255,0,1,3} +// Here we put {128,129,255} to one array and {0,1,3} to another. +// After that we unite both arrays. +// NOTE: We don't just concatenate the arrays, because they may have +// adjacent ranges, e.g.: +// 1: char(-128, 127) -> uchar -> arr1(128, 255), arr2(0, 127) -> +// unite -> uchar(0, 255) +// 2: uchar(0, 1)U(254, 255) -> char -> arr1(0, 1), arr2(-2, -1) -> +// unite -> uchar(-2, 1) +RangeSet::ContainerType RangeSet::Factory::convertTo(RangeSet What, + APSIntType Ty) { + using llvm::APInt; + using llvm::APSInt; + using Bounds = std::pair<const APSInt &, const APSInt &>; + ContainerType AscendArray; + ContainerType DescendArray; + auto CastRange = [Ty, &VF = ValueFactory](const Range &R) -> Bounds { + // Get bounds of the given range. + APSInt FromInt = R.From(); + APSInt ToInt = R.To(); + // Cast the bounds. + Ty.apply(FromInt); + Ty.apply(ToInt); + return {VF.getValue(FromInt), VF.getValue(ToInt)}; + }; + // Phase 1. Fill the first array. + APSInt LastConvertedInt = Ty.getMinValue(); + const auto *It = What.begin(); + const auto *E = What.end(); + while (It != E) { + Bounds NewBounds = CastRange(*(It++)); + // If values stop going acsending order, go to the second phase(loop). + if (NewBounds.first < LastConvertedInt) { + DescendArray.emplace_back(NewBounds.first, NewBounds.second); + break; + } + // If the range contains a midpoint, then split the range. + // E.g. char(-5, 5) -> uchar(251, 5) + // Here we shall add a range (251, 255) to the first array and (0, 5) to the + // second one. + if (NewBounds.first > NewBounds.second) { + DescendArray.emplace_back(ValueFactory.getMinValue(Ty), NewBounds.second); + AscendArray.emplace_back(NewBounds.first, ValueFactory.getMaxValue(Ty)); + } else + // Values are going acsending order. + AscendArray.emplace_back(NewBounds.first, NewBounds.second); + LastConvertedInt = NewBounds.first; + } + // Phase 2. Fill the second array. + while (It != E) { + Bounds NewBounds = CastRange(*(It++)); + DescendArray.emplace_back(NewBounds.first, NewBounds.second); + } + // Unite both arrays. + return unite(AscendArray, DescendArray); +} + +/// Promotion from unsigneds to signeds/unsigneds left. +RangeSet::ContainerType RangeSet::Factory::promoteTo(RangeSet What, + APSIntType Ty) { + ContainerType Result; + // We definitely know the size of the result set. + Result.reserve(What.size()); + + // Each unsigned value fits every larger type without any changes, + // whether the larger type is signed or unsigned. So just promote and push + // back each range one by one. + for (const Range &R : What) { + // Get bounds of the given range. + llvm::APSInt FromInt = R.From(); + llvm::APSInt ToInt = R.To(); + // Cast the bounds. + Ty.apply(FromInt); + Ty.apply(ToInt); + Result.emplace_back(ValueFactory.getValue(FromInt), + ValueFactory.getValue(ToInt)); + } + return Result; +} + RangeSet RangeSet::Factory::deletePoint(RangeSet From, const llvm::APSInt &Point) { if (!From.contains(Point)) @@ -1253,30 +1443,35 @@ private: return RangeFactory.deletePoint(Domain, IntType.getZeroValue()); } - // FIXME: Once SValBuilder supports unary minus, we should use SValBuilder to - // obtain the negated symbolic expression instead of constructing the - // 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. Optional<RangeSet> getRangeForNegatedSub(SymbolRef Sym) { - if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) { + // Do not negate if the type cannot be meaningfully negated. + if (!Sym->getType()->isUnsignedIntegerOrEnumerationType() && + !Sym->getType()->isSignedIntegerOrEnumerationType()) + return llvm::None; + + const RangeSet *NegatedRange = nullptr; + SymbolManager &SymMgr = State->getSymbolManager(); + if (const auto *USE = dyn_cast<UnarySymExpr>(Sym)) { + if (USE->getOpcode() == UO_Minus) { + // Just get the operand when we negate a symbol that is already negated. + // -(-a) == a + NegatedRange = getConstraint(State, USE->getOperand()); + } + } else if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(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 NegatedSym = SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, SSE->getLHS(), T); - - if (const RangeSet *NegatedRange = getConstraint(State, NegatedSym)) { - return RangeFactory.negate(*NegatedRange); - } + NegatedRange = getConstraint(State, NegatedSym); } + } else { + SymbolRef NegatedSym = + SymMgr.getUnarySymExpr(Sym, UO_Minus, Sym->getType()); + NegatedRange = getConstraint(State, NegatedSym); } + + if (NegatedRange) + return RangeFactory.negate(*NegatedRange); return llvm::None; } @@ -2318,12 +2513,6 @@ 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>(); @@ -2337,6 +2526,12 @@ EquivalenceClass::removeMember(ProgramStateRef State, const SymbolRef Old) { ClassMembersMap = EMFactory.add(ClassMembersMap, *this, ClsMembers); State = State->set<ClassMembers>(ClassMembersMap); + // Remove `Old`'s Sym->Class relation. + ClassMapTy Classes = State->get<ClassMap>(); + ClassMapTy::Factory &CMF = State->get_context<ClassMap>(); + Classes = CMF.remove(Classes, Old); + State = State->set<ClassMap>(Classes); + return State; } diff --git a/clang/lib/StaticAnalyzer/Core/RangedConstraintManager.cpp b/clang/lib/StaticAnalyzer/Core/RangedConstraintManager.cpp index 892d64ea4e4e..4bbe933be212 100644 --- a/clang/lib/StaticAnalyzer/Core/RangedConstraintManager.cpp +++ b/clang/lib/StaticAnalyzer/Core/RangedConstraintManager.cpp @@ -48,47 +48,48 @@ ProgramStateRef RangedConstraintManager::assumeSym(ProgramStateRef State, if (const auto *SSE = dyn_cast<SymSymExpr>(Sym)) { BinaryOperator::Opcode Op = SSE->getOpcode(); - assert(BinaryOperator::isComparisonOp(Op)); + if (BinaryOperator::isComparisonOp(Op)) { - // We convert equality operations for pointers only. - if (Loc::isLocType(SSE->getLHS()->getType()) && - Loc::isLocType(SSE->getRHS()->getType())) { - // Translate "a != b" to "(b - a) != 0". - // We invert the order of the operands as a heuristic for how loop - // conditions are usually written ("begin != end") as compared to length - // calculations ("end - begin"). The more correct thing to do would be to - // canonicalize "a - b" and "b - a", which would allow us to treat - // "a != b" and "b != a" the same. + // We convert equality operations for pointers only. + if (Loc::isLocType(SSE->getLHS()->getType()) && + Loc::isLocType(SSE->getRHS()->getType())) { + // Translate "a != b" to "(b - a) != 0". + // We invert the order of the operands as a heuristic for how loop + // conditions are usually written ("begin != end") as compared to length + // calculations ("end - begin"). The more correct thing to do would be + // to canonicalize "a - b" and "b - a", which would allow us to treat + // "a != b" and "b != a" the same. - SymbolManager &SymMgr = getSymbolManager(); - QualType DiffTy = SymMgr.getContext().getPointerDiffType(); - SymbolRef Subtraction = - SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, SSE->getLHS(), DiffTy); + SymbolManager &SymMgr = getSymbolManager(); + QualType DiffTy = SymMgr.getContext().getPointerDiffType(); + SymbolRef Subtraction = + SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, SSE->getLHS(), DiffTy); - const llvm::APSInt &Zero = getBasicVals().getValue(0, DiffTy); - Op = BinaryOperator::reverseComparisonOp(Op); - if (!Assumption) - Op = BinaryOperator::negateComparisonOp(Op); - return assumeSymRel(State, Subtraction, Op, Zero); - } + const llvm::APSInt &Zero = getBasicVals().getValue(0, DiffTy); + Op = BinaryOperator::reverseComparisonOp(Op); + if (!Assumption) + Op = BinaryOperator::negateComparisonOp(Op); + return assumeSymRel(State, Subtraction, Op, Zero); + } - if (BinaryOperator::isEqualityOp(Op)) { - SymbolManager &SymMgr = getSymbolManager(); + if (BinaryOperator::isEqualityOp(Op)) { + SymbolManager &SymMgr = getSymbolManager(); - QualType ExprType = SSE->getType(); - SymbolRef CanonicalEquality = - SymMgr.getSymSymExpr(SSE->getLHS(), BO_EQ, SSE->getRHS(), ExprType); + QualType ExprType = SSE->getType(); + SymbolRef CanonicalEquality = + SymMgr.getSymSymExpr(SSE->getLHS(), BO_EQ, SSE->getRHS(), ExprType); - bool WasEqual = SSE->getOpcode() == BO_EQ; - bool IsExpectedEqual = WasEqual == Assumption; + bool WasEqual = SSE->getOpcode() == BO_EQ; + bool IsExpectedEqual = WasEqual == Assumption; - const llvm::APSInt &Zero = getBasicVals().getValue(0, ExprType); + const llvm::APSInt &Zero = getBasicVals().getValue(0, ExprType); - if (IsExpectedEqual) { - return assumeSymNE(State, CanonicalEquality, Zero, Zero); - } + if (IsExpectedEqual) { + return assumeSymNE(State, CanonicalEquality, Zero, Zero); + } - return assumeSymEQ(State, CanonicalEquality, Zero, Zero); + return assumeSymEQ(State, CanonicalEquality, Zero, Zero); + } } } diff --git a/clang/lib/StaticAnalyzer/Core/RegionStore.cpp b/clang/lib/StaticAnalyzer/Core/RegionStore.cpp index 135130b35ba7..5e946483a93d 100644 --- a/clang/lib/StaticAnalyzer/Core/RegionStore.cpp +++ b/clang/lib/StaticAnalyzer/Core/RegionStore.cpp @@ -318,29 +318,6 @@ RegionBindingsRef RegionBindingsRef::removeBinding(const MemRegion *R, } //===----------------------------------------------------------------------===// -// Fine-grained control of RegionStoreManager. -//===----------------------------------------------------------------------===// - -namespace { -struct minimal_features_tag {}; -struct maximal_features_tag {}; - -class RegionStoreFeatures { - bool SupportsFields; -public: - RegionStoreFeatures(minimal_features_tag) : - SupportsFields(false) {} - - RegionStoreFeatures(maximal_features_tag) : - SupportsFields(true) {} - - void enableFields(bool t) { SupportsFields = t; } - - bool supportsFields() const { return SupportsFields; } -}; -} - -//===----------------------------------------------------------------------===// // Main RegionStore logic. //===----------------------------------------------------------------------===// @@ -349,8 +326,6 @@ class InvalidateRegionsWorker; class RegionStoreManager : public StoreManager { public: - const RegionStoreFeatures Features; - RegionBindings::Factory RBFactory; mutable ClusterBindings::Factory CBFactory; @@ -370,6 +345,16 @@ private: /// To disable all small-struct-dependent behavior, set the option to "0". unsigned SmallStructLimit; + /// The largest number of element an array can have and still be + /// considered "small". + /// + /// This is currently used to decide whether or not it is worth "forcing" a + /// LazyCompoundVal on bind. + /// + /// This is controlled by 'region-store-small-struct-limit' option. + /// To disable all small-struct-dependent behavior, set the option to "0". + unsigned SmallArrayLimit; + /// A helper used to populate the work list with the given set of /// regions. void populateWorkList(InvalidateRegionsWorker &W, @@ -377,16 +362,15 @@ private: InvalidatedRegions *TopLevelRegions); public: - RegionStoreManager(ProgramStateManager& mgr, const RegionStoreFeatures &f) - : StoreManager(mgr), Features(f), - RBFactory(mgr.getAllocator()), CBFactory(mgr.getAllocator()), - SmallStructLimit(0) { + RegionStoreManager(ProgramStateManager &mgr) + : StoreManager(mgr), RBFactory(mgr.getAllocator()), + CBFactory(mgr.getAllocator()), SmallStructLimit(0), SmallArrayLimit(0) { ExprEngine &Eng = StateMgr.getOwningEngine(); AnalyzerOptions &Options = Eng.getAnalysisManager().options; SmallStructLimit = Options.RegionStoreSmallStructLimit; + SmallArrayLimit = Options.RegionStoreSmallArrayLimit; } - /// setImplicitDefaultValue - Set the default binding for the provided /// MemRegion to the value implicitly defined for compound literals when /// the value is not specified. @@ -514,6 +498,11 @@ public: // Part of public interface to class. RegionBindingsRef bindVector(RegionBindingsConstRef B, const TypedValueRegion* R, SVal V); + Optional<RegionBindingsRef> tryBindSmallArray(RegionBindingsConstRef B, + const TypedValueRegion *R, + const ArrayType *AT, + nonloc::LazyCompoundVal LCV); + RegionBindingsRef bindArray(RegionBindingsConstRef B, const TypedValueRegion* R, SVal V); @@ -674,18 +663,9 @@ public: // Part of public interface to class. std::unique_ptr<StoreManager> ento::CreateRegionStoreManager(ProgramStateManager &StMgr) { - RegionStoreFeatures F = maximal_features_tag(); - return std::make_unique<RegionStoreManager>(StMgr, F); + return std::make_unique<RegionStoreManager>(StMgr); } -std::unique_ptr<StoreManager> -ento::CreateFieldsOnlyRegionStoreManager(ProgramStateManager &StMgr) { - RegionStoreFeatures F = minimal_features_tag(); - F.enableFields(true); - return std::make_unique<RegionStoreManager>(StMgr, F); -} - - //===----------------------------------------------------------------------===// // Region Cluster analysis. //===----------------------------------------------------------------------===// @@ -1397,10 +1377,10 @@ RegionStoreManager::invalidateRegions(Store store, /// the array). This is called by ExprEngine when evaluating casts /// from arrays to pointers. SVal RegionStoreManager::ArrayToPointer(Loc Array, QualType T) { - if (Array.getAs<loc::ConcreteInt>()) + if (isa<loc::ConcreteInt>(Array)) return Array; - if (!Array.getAs<loc::MemRegionVal>()) + if (!isa<loc::MemRegionVal>(Array)) return UnknownVal(); const SubRegion *R = @@ -1414,8 +1394,8 @@ SVal RegionStoreManager::ArrayToPointer(Loc Array, QualType T) { //===----------------------------------------------------------------------===// SVal RegionStoreManager::getBinding(RegionBindingsConstRef B, Loc L, QualType T) { - assert(!L.getAs<UnknownVal>() && "location unknown"); - assert(!L.getAs<UndefinedVal>() && "location undefined"); + assert(!isa<UnknownVal>(L) && "location unknown"); + assert(!isa<UndefinedVal>(L) && "location undefined"); // For access to concrete addresses, return UnknownVal. Checks // for null dereferences (and similar errors) are done by checkers, not @@ -1789,7 +1769,7 @@ Optional<SVal> RegionStoreManager::getConstantValFromConstArrayInitializer( SmallVector<uint64_t, 2> Extents = getConstantArrayExtents(CAT); // The number of offsets should equal to the numbers of extents, - // otherwise wrong type punning occured. For instance: + // otherwise wrong type punning occurred. For instance: // int arr[1][2][3]; // auto ptr = (int(*)[42])arr; // auto x = ptr[4][2]; // UB @@ -1983,15 +1963,9 @@ SVal RegionStoreManager::getBindingForField(RegionBindingsConstRef B, if (const Optional<SVal> &V = B.getDirectBinding(R)) return *V; - // Is the field declared constant and has an in-class initializer? + // If the containing record was initialized, try to get its constant value. const FieldDecl *FD = R->getDecl(); QualType Ty = FD->getType(); - if (Ty.isConstQualified()) - if (const Expr *Init = FD->getInClassInitializer()) - if (Optional<SVal> V = svalBuilder.getConstantVal(Init)) - return *V; - - // If the containing record was initialized, try to get its constant value. const MemRegion* superR = R->getSuperRegion(); if (const auto *VR = dyn_cast<VarRegion>(superR)) { const VarDecl *VD = VR->getDecl(); @@ -2024,7 +1998,7 @@ RegionStoreManager::getBindingForDerivedDefaultValue(RegionBindingsConstRef B, QualType Ty) { if (const Optional<SVal> &D = B.getDefaultBinding(superR)) { - const SVal &val = D.getValue(); + const SVal &val = *D; if (SymbolRef parentSym = val.getAsSymbol()) return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R); @@ -2036,8 +2010,7 @@ RegionStoreManager::getBindingForDerivedDefaultValue(RegionBindingsConstRef B, // Lazy bindings are usually handled through getExistingLazyBinding(). // We should unify these two code paths at some point. - if (val.getAs<nonloc::LazyCompoundVal>() || - val.getAs<nonloc::CompoundVal>()) + if (isa<nonloc::LazyCompoundVal, nonloc::CompoundVal>(val)) return val; llvm_unreachable("Unknown default value"); @@ -2153,8 +2126,13 @@ RegionStoreManager::getBindingForFieldOrElementCommon(RegionBindingsConstRef B, return UnknownVal(); // Additionally allow introspection of a block's internal layout. - if (!hasPartialLazyBinding && !isa<BlockDataRegion>(R->getBaseRegion())) + // Try to get direct binding if all other attempts failed thus far. + // Else, return UndefinedVal() + if (!hasPartialLazyBinding && !isa<BlockDataRegion>(R->getBaseRegion())) { + if (const Optional<SVal> &V = B.getDefaultBinding(R)) + return *V; return UndefinedVal(); + } } // All other values are symbolic. @@ -2235,7 +2213,7 @@ SVal RegionStoreManager::getBindingForVar(RegionBindingsConstRef B, if (Optional<SVal> V = getBindingForDerivedDefaultValue(B, MS, R, T)) { assert(!V->getAs<nonloc::LazyCompoundVal>()); - return V.getValue(); + return *V; } return svalBuilder.getRegionValueSymbolVal(R); @@ -2410,7 +2388,7 @@ RegionStoreManager::setImplicitDefaultValue(RegionBindingsConstRef B, SVal V; if (Loc::isLocType(T)) - V = svalBuilder.makeNull(); + V = svalBuilder.makeNullWithType(T); else if (T->isIntegralOrEnumerationType()) V = svalBuilder.makeZeroVal(T); else if (T->isStructureOrClassType() || T->isArrayType()) { @@ -2430,6 +2408,40 @@ RegionStoreManager::setImplicitDefaultValue(RegionBindingsConstRef B, return B.addBinding(R, BindingKey::Default, V); } +Optional<RegionBindingsRef> RegionStoreManager::tryBindSmallArray( + RegionBindingsConstRef B, const TypedValueRegion *R, const ArrayType *AT, + nonloc::LazyCompoundVal LCV) { + + auto CAT = dyn_cast<ConstantArrayType>(AT); + + // If we don't know the size, create a lazyCompoundVal instead. + if (!CAT) + return None; + + QualType Ty = CAT->getElementType(); + if (!(Ty->isScalarType() || Ty->isReferenceType())) + return None; + + // If the array is too big, create a LCV instead. + uint64_t ArrSize = CAT->getSize().getLimitedValue(); + if (ArrSize > SmallArrayLimit) + return None; + + RegionBindingsRef NewB = B; + + for (uint64_t i = 0; i < ArrSize; ++i) { + auto Idx = svalBuilder.makeArrayIndex(i); + const ElementRegion *SrcER = + MRMgr.getElementRegion(Ty, Idx, LCV.getRegion(), Ctx); + SVal V = getBindingForElement(getRegionBindings(LCV.getStore()), SrcER); + + const ElementRegion *DstER = MRMgr.getElementRegion(Ty, Idx, R, Ctx); + NewB = bind(NewB, loc::MemRegionVal(DstER), V); + } + + return NewB; +} + RegionBindingsRef RegionStoreManager::bindArray(RegionBindingsConstRef B, const TypedValueRegion* R, @@ -2451,8 +2463,13 @@ RegionStoreManager::bindArray(RegionBindingsConstRef B, } // Handle lazy compound values. - if (Init.getAs<nonloc::LazyCompoundVal>()) + if (Optional<nonloc::LazyCompoundVal> LCV = + Init.getAs<nonloc::LazyCompoundVal>()) { + if (Optional<RegionBindingsRef> NewB = tryBindSmallArray(B, R, AT, *LCV)) + return *NewB; + return bindAggregate(B, R, Init); + } if (Init.isUnknown()) return bindAggregate(B, R, UnknownVal()); @@ -2464,7 +2481,7 @@ RegionStoreManager::bindArray(RegionBindingsConstRef B, RegionBindingsRef NewB(B); - for (; Size.hasValue() ? i < Size.getValue() : true ; ++i, ++VI) { + for (; Size ? i < *Size : true; ++i, ++VI) { // The init list might be shorter than the array length. if (VI == VE) break; @@ -2483,7 +2500,7 @@ RegionStoreManager::bindArray(RegionBindingsConstRef B, // If the init list is shorter than the array length (or the array has // variable length), set the array default value. Values that are already set // are not overwritten. - if (!Size.hasValue() || i < Size.getValue()) + if (!Size || i < *Size) NewB = setImplicitDefaultValue(NewB, R, ElementTy); return NewB; @@ -2496,13 +2513,13 @@ RegionBindingsRef RegionStoreManager::bindVector(RegionBindingsConstRef B, const VectorType *VT = T->castAs<VectorType>(); // Use castAs for typedefs. // Handle lazy compound values and symbolic values. - if (V.getAs<nonloc::LazyCompoundVal>() || V.getAs<nonloc::SymbolVal>()) + if (isa<nonloc::LazyCompoundVal, nonloc::SymbolVal>(V)) return bindAggregate(B, R, V); // We may get non-CompoundVal accidentally due to imprecise cast logic or // that we are binding symbolic struct value. Kill the field values, and if // the value is symbolic go and bind it as a "default" binding. - if (!V.getAs<nonloc::CompoundVal>()) { + if (!isa<nonloc::CompoundVal>(V)) { return bindAggregate(B, R, UnknownVal()); } @@ -2570,11 +2587,8 @@ RegionStoreManager::tryBindSmallStruct(RegionBindingsConstRef B, } RegionBindingsRef RegionStoreManager::bindStruct(RegionBindingsConstRef B, - const TypedValueRegion* R, + const TypedValueRegion *R, SVal V) { - if (!Features.supportsFields()) - return B; - QualType T = R->getValueType(); assert(T->isStructureOrClassType()); @@ -2591,13 +2605,13 @@ RegionBindingsRef RegionStoreManager::bindStruct(RegionBindingsConstRef B, return *NewB; return bindAggregate(B, R, V); } - if (V.getAs<nonloc::SymbolVal>()) + if (isa<nonloc::SymbolVal>(V)) return bindAggregate(B, R, V); // We may get non-CompoundVal accidentally due to imprecise cast logic or // that we are binding symbolic struct value. Kill the field values, and if // the value is symbolic go and bind it as a "default" binding. - if (V.isUnknown() || !V.getAs<nonloc::CompoundVal>()) + if (V.isUnknown() || !isa<nonloc::CompoundVal>(V)) return bindAggregate(B, R, UnknownVal()); // The raw CompoundVal is essentially a symbolic InitListExpr: an (immutable) diff --git a/clang/lib/StaticAnalyzer/Core/SValBuilder.cpp b/clang/lib/StaticAnalyzer/Core/SValBuilder.cpp index bb3261bae3bf..13fac37899cd 100644 --- a/clang/lib/StaticAnalyzer/Core/SValBuilder.cpp +++ b/clang/lib/StaticAnalyzer/Core/SValBuilder.cpp @@ -61,7 +61,7 @@ SValBuilder::SValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context, DefinedOrUnknownSVal SValBuilder::makeZeroVal(QualType type) { if (Loc::isLocType(type)) - return makeNull(); + return makeNullWithType(type); if (type->isIntegralOrEnumerationType()) return makeIntVal(0, type); @@ -74,8 +74,10 @@ DefinedOrUnknownSVal SValBuilder::makeZeroVal(QualType type) { return UnknownVal(); } -NonLoc SValBuilder::makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, - const llvm::APSInt& rhs, QualType type) { +nonloc::SymbolVal SValBuilder::makeNonLoc(const SymExpr *lhs, + BinaryOperator::Opcode op, + const llvm::APSInt &rhs, + QualType type) { // The Environment ensures we always get a persistent APSInt in // BasicValueFactory, so we don't need to get the APSInt from // BasicValueFactory again. @@ -84,23 +86,31 @@ NonLoc SValBuilder::makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, return nonloc::SymbolVal(SymMgr.getSymIntExpr(lhs, op, rhs, type)); } -NonLoc SValBuilder::makeNonLoc(const llvm::APSInt& lhs, - BinaryOperator::Opcode op, const SymExpr *rhs, - QualType type) { +nonloc::SymbolVal SValBuilder::makeNonLoc(const llvm::APSInt &lhs, + BinaryOperator::Opcode op, + const SymExpr *rhs, QualType type) { assert(rhs); assert(!Loc::isLocType(type)); return nonloc::SymbolVal(SymMgr.getIntSymExpr(lhs, op, rhs, type)); } -NonLoc SValBuilder::makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, - const SymExpr *rhs, QualType type) { +nonloc::SymbolVal SValBuilder::makeNonLoc(const SymExpr *lhs, + BinaryOperator::Opcode op, + const SymExpr *rhs, QualType type) { assert(lhs && rhs); assert(!Loc::isLocType(type)); return nonloc::SymbolVal(SymMgr.getSymSymExpr(lhs, op, rhs, type)); } -NonLoc SValBuilder::makeNonLoc(const SymExpr *operand, - QualType fromTy, QualType toTy) { +NonLoc SValBuilder::makeNonLoc(const SymExpr *operand, UnaryOperator::Opcode op, + QualType type) { + assert(operand); + assert(!Loc::isLocType(type)); + return nonloc::SymbolVal(SymMgr.getUnarySymExpr(operand, op, type)); +} + +nonloc::SymbolVal SValBuilder::makeNonLoc(const SymExpr *operand, + QualType fromTy, QualType toTy) { assert(operand); assert(!Loc::isLocType(toTy)); return nonloc::SymbolVal(SymMgr.getCastSymbol(operand, fromTy, toTy)); @@ -359,7 +369,7 @@ Optional<SVal> SValBuilder::getConstantVal(const Expr *E) { return makeBoolVal(cast<ObjCBoolLiteralExpr>(E)); case Stmt::CXXNullPtrLiteralExprClass: - return makeNull(); + return makeNullWithType(E->getType()); case Stmt::CStyleCastExprClass: case Stmt::CXXFunctionalCastExprClass: @@ -399,7 +409,7 @@ Optional<SVal> SValBuilder::getConstantVal(const Expr *E) { if (Loc::isLocType(E->getType())) if (E->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNotNull)) - return makeNull(); + return makeNullWithType(E->getType()); return None; } @@ -431,6 +441,43 @@ SVal SValBuilder::makeSymExprValNN(BinaryOperator::Opcode Op, return UnknownVal(); } +SVal SValBuilder::evalMinus(NonLoc X) { + switch (X.getSubKind()) { + case nonloc::ConcreteIntKind: + return makeIntVal(-X.castAs<nonloc::ConcreteInt>().getValue()); + case nonloc::SymbolValKind: + return makeNonLoc(X.castAs<nonloc::SymbolVal>().getSymbol(), UO_Minus, + X.getType(Context)); + default: + return UnknownVal(); + } +} + +SVal SValBuilder::evalComplement(NonLoc X) { + switch (X.getSubKind()) { + case nonloc::ConcreteIntKind: + return makeIntVal(~X.castAs<nonloc::ConcreteInt>().getValue()); + case nonloc::SymbolValKind: + return makeNonLoc(X.castAs<nonloc::SymbolVal>().getSymbol(), UO_Not, + X.getType(Context)); + default: + return UnknownVal(); + } +} + +SVal SValBuilder::evalUnaryOp(ProgramStateRef state, UnaryOperator::Opcode opc, + SVal operand, QualType type) { + auto OpN = operand.getAs<NonLoc>(); + if (!OpN) + return UnknownVal(); + + if (opc == UO_Minus) + return evalMinus(*OpN); + if (opc == UO_Not) + return evalComplement(*OpN); + llvm_unreachable("Unexpected unary operator"); +} + SVal SValBuilder::evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op, SVal lhs, SVal rhs, QualType type) { if (lhs.isUndef() || rhs.isUndef()) @@ -439,8 +486,7 @@ SVal SValBuilder::evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op, if (lhs.isUnknown() || rhs.isUnknown()) return UnknownVal(); - if (lhs.getAs<nonloc::LazyCompoundVal>() || - rhs.getAs<nonloc::LazyCompoundVal>()) { + if (isa<nonloc::LazyCompoundVal>(lhs) || isa<nonloc::LazyCompoundVal>(rhs)) { return UnknownVal(); } @@ -563,8 +609,7 @@ SVal SValBuilder::evalIntegralCast(ProgramStateRef state, SVal val, std::tie(IsNotTruncated, IsTruncated) = state->assume(CompVal); if (!IsNotTruncated && IsTruncated) { // Symbol is truncated so we evaluate it as a cast. - NonLoc CastVal = makeNonLoc(se, originalTy, castTy); - return CastVal; + return makeNonLoc(se, originalTy, castTy); } return evalCast(val, castTy, originalTy); } @@ -682,8 +727,11 @@ SVal SValBuilder::evalCastSubKind(loc::ConcreteInt V, QualType CastTy, } // Pointer to any pointer. - if (Loc::isLocType(CastTy)) - return V; + if (Loc::isLocType(CastTy)) { + llvm::APSInt Value = V.getValue(); + BasicVals.getAPSIntType(CastTy).apply(Value); + return loc::ConcreteInt(BasicVals.getValue(Value)); + } // Pointer to whatever else. return UnknownVal(); @@ -742,9 +790,6 @@ SVal SValBuilder::evalCastSubKind(loc::MemRegionVal V, QualType CastTy, // This change is needed for architectures with varying // pointer widths. See the amdgcn opencl reproducer with // this change as an example: solver-sym-simplification-ptr-bool.cl - // FIXME: Cleanup remainder of `getZeroWithPtrWidth ()` - // and `getIntWithPtrWidth()` functions to prevent future - // confusion if (!Ty->isReferenceType()) return makeNonLoc(Sym, BO_NE, BasicVals.getZeroWithTypeSize(Ty), CastTy); @@ -983,8 +1028,8 @@ SVal SValBuilder::evalCastSubKind(nonloc::SymbolVal V, QualType CastTy, // Produce SymbolCast if CastTy and T are different integers. // NOTE: In the end the type of SymbolCast shall be equal to CastTy. - if (T->isIntegralOrEnumerationType() && - CastTy->isIntegralOrEnumerationType()) { + if (T->isIntegralOrUnscopedEnumerationType() && + CastTy->isIntegralOrUnscopedEnumerationType()) { AnalyzerOptions &Opts = StateMgr.getOwningEngine().getAnalysisManager().getAnalyzerOptions(); // If appropriate option is disabled, ignore the cast. @@ -1009,7 +1054,7 @@ SVal SValBuilder::evalCastSubKind(nonloc::PointerToMember V, QualType CastTy, return V; } -SVal clang::ento::SValBuilder::simplifySymbolCast(nonloc::SymbolVal V, +nonloc::SymbolVal SValBuilder::simplifySymbolCast(nonloc::SymbolVal V, QualType CastTy) { // We use seven conditions to recognize a simplification case. // For the clarity let `CastTy` be `C`, SE->getType() - `T`, root type - `R`, diff --git a/clang/lib/StaticAnalyzer/Core/SVals.cpp b/clang/lib/StaticAnalyzer/Core/SVals.cpp index 117546e43b1a..67913a55b3dc 100644 --- a/clang/lib/StaticAnalyzer/Core/SVals.cpp +++ b/clang/lib/StaticAnalyzer/Core/SVals.cpp @@ -43,25 +43,6 @@ using namespace ento; // Utility methods. //===----------------------------------------------------------------------===// -bool SVal::hasConjuredSymbol() const { - if (Optional<nonloc::SymbolVal> SV = getAs<nonloc::SymbolVal>()) { - SymbolRef sym = SV->getSymbol(); - if (isa<SymbolConjured>(sym)) - return true; - } - - if (Optional<loc::MemRegionVal> RV = getAs<loc::MemRegionVal>()) { - const MemRegion *R = RV->getRegion(); - if (const auto *SR = dyn_cast<SymbolicRegion>(R)) { - SymbolRef sym = SR->getSymbol(); - if (isa<SymbolConjured>(sym)) - return true; - } - } - - return false; -} - const FunctionDecl *SVal::getAsFunctionDecl() const { if (Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>()) { const MemRegion* R = X->getRegion(); @@ -196,8 +177,7 @@ QualType SVal::getType(const ASTContext &Context) const { } const MemRegion *loc::MemRegionVal::stripCasts(bool StripBaseCasts) const { - const MemRegion *R = getRegion(); - return R ? R->StripCasts(StripBaseCasts) : nullptr; + return getRegion()->StripCasts(StripBaseCasts); } const void *nonloc::LazyCompoundVal::getStore() const { @@ -273,49 +253,6 @@ bool SVal::isZeroConstant() const { } //===----------------------------------------------------------------------===// -// Transfer function dispatch for Non-Locs. -//===----------------------------------------------------------------------===// - -SVal nonloc::ConcreteInt::evalBinOp(SValBuilder &svalBuilder, - BinaryOperator::Opcode Op, - const nonloc::ConcreteInt& R) const { - const llvm::APSInt* X = - svalBuilder.getBasicValueFactory().evalAPSInt(Op, getValue(), R.getValue()); - - if (X) - return nonloc::ConcreteInt(*X); - else - return UndefinedVal(); -} - -nonloc::ConcreteInt -nonloc::ConcreteInt::evalComplement(SValBuilder &svalBuilder) const { - return svalBuilder.makeIntVal(~getValue()); -} - -nonloc::ConcreteInt -nonloc::ConcreteInt::evalMinus(SValBuilder &svalBuilder) const { - return svalBuilder.makeIntVal(-getValue()); -} - -//===----------------------------------------------------------------------===// -// Transfer function dispatch for Locs. -//===----------------------------------------------------------------------===// - -SVal loc::ConcreteInt::evalBinOp(BasicValueFactory& BasicVals, - BinaryOperator::Opcode Op, - const loc::ConcreteInt& R) const { - assert(BinaryOperator::isComparisonOp(Op) || Op == BO_Sub); - - const llvm::APSInt *X = BasicVals.evalAPSInt(Op, getValue(), R.getValue()); - - if (X) - return nonloc::ConcreteInt(*X); - else - return UndefinedVal(); -} - -//===----------------------------------------------------------------------===// // Pretty-Printing. //===----------------------------------------------------------------------===// @@ -401,7 +338,7 @@ void NonLoc::dumpToStream(raw_ostream &os) const { else os << ", "; - os << (*I).getType().getAsString(); + os << I->getType(); } os << '}'; diff --git a/clang/lib/StaticAnalyzer/Core/SarifDiagnostics.cpp b/clang/lib/StaticAnalyzer/Core/SarifDiagnostics.cpp index e1319a4c2e41..ad3110792592 100644 --- a/clang/lib/StaticAnalyzer/Core/SarifDiagnostics.cpp +++ b/clang/lib/StaticAnalyzer/Core/SarifDiagnostics.cpp @@ -97,12 +97,12 @@ static std::string fileNameToURI(StringRef Filename) { assert(Iter != End && "Expected there to be a non-root path component."); // Add the rest of the path components, encoding any reserved characters; // we skip past the first path component, as it was handled it above. - std::for_each(++Iter, End, [&Ret](StringRef Component) { + for (StringRef Component : llvm::make_range(++Iter, End)) { // For reasons unknown to me, we may get a backslash with Windows native // paths for the initial backslash following the drive component, which // we need to ignore as a URI path part. if (Component == "\\") - return; + continue; // Add the separator between the previous path part and the one being // currently processed. @@ -112,7 +112,7 @@ static std::string fileNameToURI(StringRef Filename) { for (char C : Component) { Ret += percentEncodeURICharacter(C); } - }); + } return std::string(Ret); } @@ -341,14 +341,14 @@ static json::Array createRules(std::vector<const PathDiagnostic *> &Diags, json::Array Rules; llvm::StringSet<> Seen; - llvm::for_each(Diags, [&](const PathDiagnostic *D) { + for (const PathDiagnostic *D : Diags) { StringRef RuleID = D->getCheckerName(); std::pair<llvm::StringSet<>::iterator, bool> P = Seen.insert(RuleID); if (P.second) { RuleMapping[RuleID] = Rules.size(); // Maps RuleID to an Array Index. Rules.push_back(createRule(*D)); } - }); + } return Rules; } @@ -368,10 +368,9 @@ static json::Object createRun(const LangOptions &LO, json::Array Results, Artifacts; StringMap<unsigned> RuleMapping; json::Object Tool = createTool(Diags, RuleMapping); - - llvm::for_each(Diags, [&](const PathDiagnostic *D) { + + for (const PathDiagnostic *D : Diags) Results.push_back(createResult(LO, *D, Artifacts, RuleMapping)); - }); return json::Object{{"tool", std::move(Tool)}, {"results", std::move(Results)}, diff --git a/clang/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp b/clang/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp index f96974f97dcc..dcb6043e9df3 100644 --- a/clang/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp +++ b/clang/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp @@ -22,9 +22,9 @@ namespace ento { SimpleConstraintManager::~SimpleConstraintManager() {} -ProgramStateRef SimpleConstraintManager::assume(ProgramStateRef State, - DefinedSVal Cond, - bool Assumption) { +ProgramStateRef SimpleConstraintManager::assumeInternal(ProgramStateRef State, + DefinedSVal Cond, + bool Assumption) { // If we have a Loc value, cast it to a bool NonLoc first. if (Optional<Loc> LV = Cond.getAs<Loc>()) { SValBuilder &SVB = State->getStateManager().getSValBuilder(); @@ -44,7 +44,7 @@ ProgramStateRef SimpleConstraintManager::assume(ProgramStateRef State, ProgramStateRef SimpleConstraintManager::assume(ProgramStateRef State, NonLoc Cond, bool Assumption) { State = assumeAux(State, Cond, Assumption); - if (NotifyAssumeClients && EE) + if (EE) return EE->processAssume(State, Cond, Assumption); return State; } @@ -86,12 +86,12 @@ ProgramStateRef SimpleConstraintManager::assumeAux(ProgramStateRef State, } case nonloc::LocAsIntegerKind: - return assume(State, Cond.castAs<nonloc::LocAsInteger>().getLoc(), - Assumption); + return assumeInternal(State, Cond.castAs<nonloc::LocAsInteger>().getLoc(), + Assumption); } // end switch } -ProgramStateRef SimpleConstraintManager::assumeInclusiveRange( +ProgramStateRef SimpleConstraintManager::assumeInclusiveRangeInternal( ProgramStateRef State, NonLoc Value, const llvm::APSInt &From, const llvm::APSInt &To, bool InRange) { diff --git a/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp b/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp index 0bd47ced15a5..762ecc18ecea 100644 --- a/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp +++ b/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp @@ -22,6 +22,13 @@ using namespace ento; namespace { class SimpleSValBuilder : public SValBuilder { + // Query the constraint manager whether the SVal has only one possible + // (integer) value. If that is the case, the value is returned. Otherwise, + // returns NULL. + // This is an implementation detail. Checkers should use `getKnownValue()` + // instead. + const llvm::APSInt *getConstValue(ProgramStateRef state, SVal V); + // With one `simplifySValOnce` call, a compound symbols might collapse to // simpler symbol tree that is still possible to further simplify. Thus, we // do the simplification on a new symbol tree until we reach the simplest @@ -45,7 +52,7 @@ class SimpleSValBuilder : public SValBuilder { SVal simplifyUntilFixpoint(ProgramStateRef State, SVal Val); // Recursively descends into symbolic expressions and replaces symbols - // with their known values (in the sense of the getKnownValue() method). + // with their known values (in the sense of the getConstValue() method). // We traverse the symbol tree and query the constraint values for the // sub-trees and if a value is a constant we do the constant folding. SVal simplifySValOnce(ProgramStateRef State, SVal V); @@ -56,8 +63,6 @@ public: : SValBuilder(alloc, context, stateMgr) {} ~SimpleSValBuilder() override {} - SVal evalMinus(NonLoc val) override; - SVal evalComplement(NonLoc val) override; SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op, NonLoc lhs, NonLoc rhs, QualType resultTy) override; SVal evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op, @@ -65,8 +70,9 @@ public: SVal evalBinOpLN(ProgramStateRef state, BinaryOperator::Opcode op, Loc lhs, NonLoc rhs, QualType resultTy) override; - /// getKnownValue - evaluates a given SVal. If the SVal has only one possible - /// (integer) value, that value is returned. Otherwise, returns NULL. + /// Evaluates a given SVal by recursively evaluating and + /// simplifying the children SVals. If the SVal has only one possible + /// (integer) value, that value is returned. Otherwise, returns NULL. const llvm::APSInt *getKnownValue(ProgramStateRef state, SVal V) override; SVal simplifySVal(ProgramStateRef State, SVal V) override; @@ -82,26 +88,21 @@ SValBuilder *ento::createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc, return new SimpleSValBuilder(alloc, context, stateMgr); } -//===----------------------------------------------------------------------===// -// Transfer function for unary operators. -//===----------------------------------------------------------------------===// - -SVal SimpleSValBuilder::evalMinus(NonLoc val) { - switch (val.getSubKind()) { - case nonloc::ConcreteIntKind: - return val.castAs<nonloc::ConcreteInt>().evalMinus(*this); - default: - return UnknownVal(); +// Checks if the negation the value and flipping sign preserve +// the semantics on the operation in the resultType +static bool isNegationValuePreserving(const llvm::APSInt &Value, + APSIntType ResultType) { + const unsigned ValueBits = Value.getSignificantBits(); + if (ValueBits == ResultType.getBitWidth()) { + // The value is the lowest negative value that is representable + // in signed integer with bitWith of result type. The + // negation is representable if resultType is unsigned. + return ResultType.isUnsigned(); } -} -SVal SimpleSValBuilder::evalComplement(NonLoc X) { - switch (X.getSubKind()) { - case nonloc::ConcreteIntKind: - return X.castAs<nonloc::ConcreteInt>().evalComplement(*this); - default: - return UnknownVal(); - } + // If resultType bitWith is higher that number of bits required + // to represent RHS, the sign flip produce same value. + return ValueBits < ResultType.getBitWidth(); } //===----------------------------------------------------------------------===// @@ -197,6 +198,17 @@ SVal SimpleSValBuilder::MakeSymIntVal(const SymExpr *LHS, if (RHS.isSigned() && !SymbolType->isSignedIntegerOrEnumerationType()) ConvertedRHS = &BasicVals.Convert(SymbolType, RHS); } + } else if (BinaryOperator::isAdditiveOp(op) && RHS.isNegative()) { + // Change a+(-N) into a-N, and a-(-N) into a+N + // Adjust addition/subtraction of negative value, to + // subtraction/addition of the negated value. + APSIntType resultIntTy = BasicVals.getAPSIntType(resultTy); + if (isNegationValuePreserving(RHS, resultIntTy)) { + ConvertedRHS = &BasicVals.getValue(-resultIntTy.convert(RHS)); + op = (op == BO_Add) ? BO_Sub : BO_Add; + } else { + ConvertedRHS = &BasicVals.Convert(resultTy, RHS); + } } else ConvertedRHS = &BasicVals.Convert(resultTy, RHS); @@ -286,7 +298,6 @@ static NonLoc doRearrangeUnchecked(ProgramStateRef State, else llvm_unreachable("Operation not suitable for unchecked rearrangement!"); - // FIXME: Can we use assume() without getting into an infinite recursion? if (LSym == RSym) return SVB.evalBinOpNN(State, Op, nonloc::ConcreteInt(LInt), nonloc::ConcreteInt(RInt), ResultTy) @@ -499,7 +510,7 @@ SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state, llvm::APSInt LHSValue = lhs.castAs<nonloc::ConcreteInt>().getValue(); // If we're dealing with two known constants, just perform the operation. - if (const llvm::APSInt *KnownRHSValue = getKnownValue(state, rhs)) { + if (const llvm::APSInt *KnownRHSValue = getConstValue(state, rhs)) { llvm::APSInt RHSValue = *KnownRHSValue; if (BinaryOperator::isComparisonOp(op)) { // We're looking for a type big enough to compare the two values. @@ -619,7 +630,7 @@ SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state, } // For now, only handle expressions whose RHS is a constant. - if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs)) { + if (const llvm::APSInt *RHSValue = getConstValue(state, rhs)) { // If both the LHS and the current expression are additive, // fold their constants and try again. if (BinaryOperator::isAdditiveOp(op)) { @@ -636,16 +647,26 @@ SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state, const llvm::APSInt &first = IntType.convert(symIntExpr->getRHS()); const llvm::APSInt &second = IntType.convert(*RHSValue); + // If the op and lop agrees, then we just need to + // sum the constants. Otherwise, we change to operation + // type if substraction would produce negative value + // (and cause overflow for unsigned integers), + // as consequence x+1U-10 produces x-9U, instead + // of x+4294967287U, that would be produced without this + // additional check. const llvm::APSInt *newRHS; - if (lop == op) + if (lop == op) { newRHS = BasicVals.evalAPSInt(BO_Add, first, second); - else + } else if (first >= second) { newRHS = BasicVals.evalAPSInt(BO_Sub, first, second); + op = lop; + } else { + newRHS = BasicVals.evalAPSInt(BO_Sub, second, first); + } assert(newRHS && "Invalid operation despite common type!"); rhs = nonloc::ConcreteInt(*newRHS); lhs = nonloc::SymbolVal(symIntExpr->getLHS()); - op = lop; continue; } } @@ -656,7 +677,7 @@ SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state, } // Is the RHS a constant? - if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs)) + if (const llvm::APSInt *RHSValue = getConstValue(state, rhs)) return MakeSymIntVal(Sym, op, *RHSValue, resultTy); if (Optional<NonLoc> V = tryRearrange(state, op, lhs, rhs, resultTy)) @@ -715,11 +736,41 @@ static SVal evalBinOpFieldRegionFieldRegion(const FieldRegion *LeftFR, llvm_unreachable("Fields not found in parent record's definition"); } +// This is used in debug builds only for now because some downstream users +// may hit this assert in their subsequent merges. +// There are still places in the analyzer where equal bitwidth Locs +// are compared, and need to be found and corrected. Recent previous fixes have +// addressed the known problems of making NULLs with specific bitwidths +// for Loc comparisons along with deprecation of APIs for the same purpose. +// +static void assertEqualBitWidths(ProgramStateRef State, Loc RhsLoc, + Loc LhsLoc) { + // Implements a "best effort" check for RhsLoc and LhsLoc bit widths + ASTContext &Ctx = State->getStateManager().getContext(); + uint64_t RhsBitwidth = + RhsLoc.getType(Ctx).isNull() ? 0 : Ctx.getTypeSize(RhsLoc.getType(Ctx)); + uint64_t LhsBitwidth = + LhsLoc.getType(Ctx).isNull() ? 0 : Ctx.getTypeSize(LhsLoc.getType(Ctx)); + if (RhsBitwidth && LhsBitwidth && + (LhsLoc.getSubKind() == RhsLoc.getSubKind())) { + assert(RhsBitwidth == LhsBitwidth && + "RhsLoc and LhsLoc bitwidth must be same!"); + } +} + // FIXME: all this logic will change if/when we have MemRegion::getLocation(). SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op, Loc lhs, Loc rhs, QualType resultTy) { + + // Assert that bitwidth of lhs and rhs are the same. + // This can happen if two different address spaces are used, + // and the bitwidths of the address spaces are different. + // See LIT case clang/test/Analysis/cstring-checker-addressspace.c + // FIXME: See comment above in the function assertEqualBitWidths + assertEqualBitWidths(state, rhs, lhs); + // Only comparisons and subtractions are valid operations on two pointers. // See [C99 6.5.5 through 6.5.14] or [C++0x 5.6 through 5.15]. // However, if a pointer is casted to an integer, evalBinOpNN may end up @@ -777,6 +828,8 @@ SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state, return UnknownVal(); case loc::ConcreteIntKind: { + auto L = lhs.castAs<loc::ConcreteInt>(); + // If one of the operands is a symbol and the other is a constant, // build an expression for use by the constraint manager. if (SymbolRef rSym = rhs.getAsLocSymbol()) { @@ -785,19 +838,17 @@ SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state, if (!BinaryOperator::isComparisonOp(op) || op == BO_Cmp) return UnknownVal(); - const llvm::APSInt &lVal = lhs.castAs<loc::ConcreteInt>().getValue(); op = BinaryOperator::reverseComparisonOp(op); - return makeNonLoc(rSym, op, lVal, resultTy); + return makeNonLoc(rSym, op, L.getValue(), resultTy); } // If both operands are constants, just perform the operation. if (Optional<loc::ConcreteInt> rInt = rhs.getAs<loc::ConcreteInt>()) { - SVal ResultVal = - lhs.castAs<loc::ConcreteInt>().evalBinOp(BasicVals, op, *rInt); - if (Optional<NonLoc> Result = ResultVal.getAs<NonLoc>()) - return evalCast(*Result, resultTy, QualType{}); + assert(BinaryOperator::isComparisonOp(op) || op == BO_Sub); - assert(!ResultVal.getAs<Loc>() && "Loc-Loc ops should not produce Locs"); + if (const auto *ResultInt = + BasicVals.evalAPSInt(op, L.getValue(), rInt->getValue())) + return evalCast(nonloc::ConcreteInt(*ResultInt), resultTy, QualType{}); return UnknownVal(); } @@ -805,7 +856,7 @@ SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state, // This must come after the test if the RHS is a symbol, which is used to // build constraints. The address of any non-symbolic region is guaranteed // to be non-NULL, as is any label. - assert(rhs.getAs<loc::MemRegionVal>() || rhs.getAs<loc::GotoLabel>()); + assert((isa<loc::MemRegionVal, loc::GotoLabel>(rhs))); if (lhs.isZeroConstant()) { switch (op) { default: @@ -1114,9 +1165,8 @@ SVal SimpleSValBuilder::evalBinOpLN(ProgramStateRef state, return UnknownVal(); } -const llvm::APSInt *SimpleSValBuilder::getKnownValue(ProgramStateRef state, - SVal V) { - V = simplifySVal(state, V); +const llvm::APSInt *SimpleSValBuilder::getConstValue(ProgramStateRef state, + SVal V) { if (V.isUnknownOrUndef()) return nullptr; @@ -1132,6 +1182,11 @@ const llvm::APSInt *SimpleSValBuilder::getKnownValue(ProgramStateRef state, return nullptr; } +const llvm::APSInt *SimpleSValBuilder::getKnownValue(ProgramStateRef state, + SVal V) { + return getConstValue(state, simplifySVal(state, V)); +} + SVal SimpleSValBuilder::simplifyUntilFixpoint(ProgramStateRef State, SVal Val) { SVal SimplifiedVal = simplifySValOnce(State, Val); while (SimplifiedVal != Val) { @@ -1198,14 +1253,12 @@ SVal SimpleSValBuilder::simplifySValOnce(ProgramStateRef State, SVal V) { SVal VisitSymbolData(const SymbolData *S) { // No cache here. if (const llvm::APSInt *I = - SVB.getKnownValue(State, SVB.makeSymbolVal(S))) + State->getConstraintManager().getSymVal(State, S)) return Loc::isLocType(S->getType()) ? (SVal)SVB.makeIntLocVal(*I) : (SVal)SVB.makeIntVal(*I); return SVB.makeSymbolVal(S); } - // TODO: Support SymbolCast. - SVal VisitSymIntExpr(const SymIntExpr *S) { auto I = Cached.find(S); if (I != Cached.end()) @@ -1275,6 +1328,30 @@ SVal SimpleSValBuilder::simplifySValOnce(ProgramStateRef State, SVal V) { S, SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType())); } + SVal VisitSymbolCast(const SymbolCast *S) { + auto I = Cached.find(S); + if (I != Cached.end()) + return I->second; + const SymExpr *OpSym = S->getOperand(); + SVal OpVal = getConstOrVisit(OpSym); + if (isUnchanged(OpSym, OpVal)) + return skip(S); + + return cache(S, SVB.evalCast(OpVal, S->getType(), OpSym->getType())); + } + + SVal VisitUnarySymExpr(const UnarySymExpr *S) { + auto I = Cached.find(S); + if (I != Cached.end()) + return I->second; + SVal Op = getConstOrVisit(S->getOperand()); + if (isUnchanged(S->getOperand(), Op)) + return skip(S); + + return cache( + S, SVB.evalUnaryOp(State, S->getOpcode(), Op, S->getType())); + } + SVal VisitSymExpr(SymbolRef S) { return nonloc::SymbolVal(S); } SVal VisitMemRegion(const MemRegion *R) { return loc::MemRegionVal(R); } @@ -1288,14 +1365,6 @@ SVal SimpleSValBuilder::simplifySValOnce(ProgramStateRef State, SVal V) { SVal VisitSVal(SVal V) { return V; } }; - // A crude way of preventing this function from calling itself from evalBinOp. - static bool isReentering = false; - if (isReentering) - return V; - - isReentering = true; SVal SimplifiedV = Simplifier(State).Visit(V); - isReentering = false; - return SimplifiedV; } diff --git a/clang/lib/StaticAnalyzer/Core/Store.cpp b/clang/lib/StaticAnalyzer/Core/Store.cpp index 2bcdb0faf5da..96e8878da616 100644 --- a/clang/lib/StaticAnalyzer/Core/Store.cpp +++ b/clang/lib/StaticAnalyzer/Core/Store.cpp @@ -459,10 +459,10 @@ SVal StoreManager::getLValueElement(QualType elementType, NonLoc Offset, // FIXME: For absolute pointer addresses, we just return that value back as // well, although in reality we should return the offset added to that // value. See also the similar FIXME in getLValueFieldOrIvar(). - if (Base.isUnknownOrUndef() || Base.getAs<loc::ConcreteInt>()) + if (Base.isUnknownOrUndef() || isa<loc::ConcreteInt>(Base)) return Base; - if (Base.getAs<loc::GotoLabel>()) + if (isa<loc::GotoLabel>(Base)) return UnknownVal(); const SubRegion *BaseRegion = @@ -488,7 +488,7 @@ SVal StoreManager::getLValueElement(QualType elementType, NonLoc Offset, SVal BaseIdx = ElemR->getIndex(); - if (!BaseIdx.getAs<nonloc::ConcreteInt>()) + if (!isa<nonloc::ConcreteInt>(BaseIdx)) return UnknownVal(); const llvm::APSInt &BaseIdxI = @@ -497,7 +497,7 @@ SVal StoreManager::getLValueElement(QualType elementType, NonLoc Offset, // Only allow non-integer offsets if the base region has no offset itself. // FIXME: This is a somewhat arbitrary restriction. We should be using // SValBuilder here to add the two offsets without checking their types. - if (!Offset.getAs<nonloc::ConcreteInt>()) { + if (!isa<nonloc::ConcreteInt>(Offset)) { if (isa<ElementRegion>(BaseRegion->StripCasts())) return UnknownVal(); diff --git a/clang/lib/StaticAnalyzer/Core/SymbolManager.cpp b/clang/lib/StaticAnalyzer/Core/SymbolManager.cpp index 1ae1f97efd2e..2227bd324adc 100644 --- a/clang/lib/StaticAnalyzer/Core/SymbolManager.cpp +++ b/clang/lib/StaticAnalyzer/Core/SymbolManager.cpp @@ -65,14 +65,23 @@ void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS, } void SymbolCast::dumpToStream(raw_ostream &os) const { - os << '(' << ToTy.getAsString() << ") ("; + os << '(' << ToTy << ") ("; Operand->dumpToStream(os); os << ')'; } +void UnarySymExpr::dumpToStream(raw_ostream &os) const { + os << UnaryOperator::getOpcodeStr(Op); + bool Binary = isa<BinarySymExpr>(Operand); + if (Binary) + os << '('; + Operand->dumpToStream(os); + if (Binary) + os << ')'; +} + void SymbolConjured::dumpToStream(raw_ostream &os) const { - os << getKindStr() << getSymbolID() << '{' << T.getAsString() << ", LC" - << LCtx->getID(); + os << getKindStr() << getSymbolID() << '{' << T << ", LC" << LCtx->getID(); if (S) os << ", S" << S->getID(LCtx->getDecl()->getASTContext()); else @@ -90,15 +99,13 @@ void SymbolExtent::dumpToStream(raw_ostream &os) const { } void SymbolMetadata::dumpToStream(raw_ostream &os) const { - os << getKindStr() << getSymbolID() << '{' << getRegion() << ',' - << T.getAsString() << '}'; + os << getKindStr() << getSymbolID() << '{' << getRegion() << ',' << T << '}'; } void SymbolData::anchor() {} void SymbolRegionValue::dumpToStream(raw_ostream &os) const { - os << getKindStr() << getSymbolID() << '<' << getType().getAsString() << ' ' - << R << '>'; + os << getKindStr() << getSymbolID() << '<' << getType() << ' ' << R << '>'; } bool SymExpr::symbol_iterator::operator==(const symbol_iterator &X) const { @@ -137,6 +144,9 @@ void SymExpr::symbol_iterator::expand() { case SymExpr::SymbolCastKind: itr.push_back(cast<SymbolCast>(SE)->getOperand()); return; + case SymExpr::UnarySymExprKind: + itr.push_back(cast<UnarySymExpr>(SE)->getOperand()); + return; case SymExpr::SymIntExprKind: itr.push_back(cast<SymIntExpr>(SE)->getLHS()); return; @@ -309,6 +319,22 @@ const SymSymExpr *SymbolManager::getSymSymExpr(const SymExpr *lhs, return cast<SymSymExpr>(data); } +const UnarySymExpr *SymbolManager::getUnarySymExpr(const SymExpr *Operand, + UnaryOperator::Opcode Opc, + QualType T) { + llvm::FoldingSetNodeID ID; + UnarySymExpr::Profile(ID, Operand, Opc, T); + void *InsertPos; + SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); + if (!data) { + data = (UnarySymExpr *)BPAlloc.Allocate<UnarySymExpr>(); + new (data) UnarySymExpr(Operand, Opc, T); + DataSet.InsertNode(data, InsertPos); + } + + return cast<UnarySymExpr>(data); +} + QualType SymbolConjured::getType() const { return T; } @@ -468,6 +494,9 @@ bool SymbolReaper::isLive(SymbolRef sym) { case SymExpr::SymbolCastKind: KnownLive = isLive(cast<SymbolCast>(sym)->getOperand()); break; + case SymExpr::UnarySymExprKind: + KnownLive = isLive(cast<UnarySymExpr>(sym)->getOperand()); + break; } if (KnownLive) diff --git a/clang/lib/StaticAnalyzer/Core/TextDiagnostics.cpp b/clang/lib/StaticAnalyzer/Core/TextDiagnostics.cpp index 4f3be7cae331..48c82cfb82b2 100644 --- a/clang/lib/StaticAnalyzer/Core/TextDiagnostics.cpp +++ b/clang/lib/StaticAnalyzer/Core/TextDiagnostics.cpp @@ -129,7 +129,7 @@ public: Rewriter Rewrite(SM, LO); if (!applyAllReplacements(Repls, Rewrite)) { - llvm::errs() << "An error occured during applying fix-it.\n"; + llvm::errs() << "An error occurred during applying fix-it.\n"; } Rewrite.overwriteChangedFiles(); diff --git a/clang/lib/StaticAnalyzer/Core/WorkList.cpp b/clang/lib/StaticAnalyzer/Core/WorkList.cpp index 348552ba73a9..7042a9020837 100644 --- a/clang/lib/StaticAnalyzer/Core/WorkList.cpp +++ b/clang/lib/StaticAnalyzer/Core/WorkList.cpp @@ -205,12 +205,6 @@ class UnexploredFirstPriorityQueue : public WorkList { using QueuePriority = std::pair<int, unsigned long>; using QueueItem = std::pair<WorkListUnit, QueuePriority>; - struct ExplorationComparator { - bool operator() (const QueueItem &LHS, const QueueItem &RHS) { - return LHS.second < RHS.second; - } - }; - // Number of inserted nodes, used to emulate DFS ordering in the priority // queue when insertions are equal. unsigned long Counter = 0; @@ -219,7 +213,7 @@ class UnexploredFirstPriorityQueue : public WorkList { VisitedTimesMap NumReached; // The top item is the largest one. - llvm::PriorityQueue<QueueItem, std::vector<QueueItem>, ExplorationComparator> + llvm::PriorityQueue<QueueItem, std::vector<QueueItem>, llvm::less_second> queue; public: @@ -267,12 +261,6 @@ class UnexploredFirstPriorityLocationQueue : public WorkList { using QueuePriority = std::pair<int, unsigned long>; using QueueItem = std::pair<WorkListUnit, QueuePriority>; - struct ExplorationComparator { - bool operator() (const QueueItem &LHS, const QueueItem &RHS) { - return LHS.second < RHS.second; - } - }; - // Number of inserted nodes, used to emulate DFS ordering in the priority // queue when insertions are equal. unsigned long Counter = 0; @@ -281,7 +269,7 @@ class UnexploredFirstPriorityLocationQueue : public WorkList { VisitedTimesMap NumReached; // The top item is the largest one. - llvm::PriorityQueue<QueueItem, std::vector<QueueItem>, ExplorationComparator> + llvm::PriorityQueue<QueueItem, std::vector<QueueItem>, llvm::less_second> queue; public: |