diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h --- a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h @@ -27,6 +27,7 @@ #include "llvm/ADT/Any.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/Support/Error.h" namespace clang { namespace dataflow { @@ -106,18 +107,24 @@ /// Performs dataflow analysis and returns a mapping from basic block IDs to /// dataflow analysis states that model the respective basic blocks. Indices -/// of the returned vector correspond to basic block IDs. +/// of the returned vector correspond to basic block IDs. Returns an error if +/// the dataflow analysis cannot be performed successfully. template -std::vector>> +llvm::Expected>>> runDataflowAnalysis(const ControlFlowContext &CFCtx, AnalysisT &Analysis, const Environment &InitEnv) { auto TypeErasedBlockStates = runTypeErasedDataflowAnalysis(CFCtx, Analysis, InitEnv); + if (!TypeErasedBlockStates) + return TypeErasedBlockStates.takeError(); + std::vector< llvm::Optional>> BlockStates; - BlockStates.reserve(TypeErasedBlockStates.size()); - llvm::transform(std::move(TypeErasedBlockStates), + BlockStates.reserve(TypeErasedBlockStates->size()); + + llvm::transform(std::move(*TypeErasedBlockStates), std::back_inserter(BlockStates), [](auto &OptState) { return std::move(OptState).map([](auto &&State) { return DataflowAnalysisState{ diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h --- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h @@ -51,15 +51,36 @@ /// Holds the state of the program (store and heap) at a given program point. class Environment { public: + /// Supplements `Environment` with non-standard comparison operations. + class Comparator { + public: + virtual ~Comparator() = default; + + /// Returns true if and only if `Val1` is equivalent to `Val2`. + /// + /// Requirements: + /// + /// `Val1` must be assigned to a storage location of type `Type` in `Env1`. + /// + /// `Val2` must be assigned to a storage location of type `Type` in `Env2`. + /// + /// `Val1` and `Val2` must be distinct. + virtual bool compareEquivalent(QualType Type, const Value &Val1, + const Environment &Env1, const Value &Val2, + const Environment &Env2) { + return false; + } + }; + /// Supplements `Environment` with non-standard join operations. class Merger { public: virtual ~Merger() = default; - /// Given distinct `Val1` and `Val2`, modifies `MergedVal` to approximate - /// both `Val1` and `Val2`. This could be a strict lattice join or a more - /// general widening operation. If this function returns true, `MergedVal` - /// will be assigned to a storage location of type `Type` in `Env`. + /// Modifies `MergedVal` to approximate both `Val1` and `Val2`. This could + /// be a strict lattice join or a more general widening operation. If this + /// function returns true, `MergedVal` will be assigned to a storage + /// location of type `Type` in `Env`. /// /// Requirements: /// @@ -84,9 +105,27 @@ /// with a symbolic representation of the `this` pointee. Environment(DataflowAnalysisContext &DACtx, const DeclContext &DeclCtx); - bool operator==(const Environment &) const; + /// Returns true if and only if the environment is equivalent to `Other`, i.e + /// the two environments: + /// - have the same mappings from declarations to storage locations, + /// - have the same mappings from expressions to storage locations, + /// - have the same or equivalent (according to `Comparator`) values assigned + /// to the same storage locations. + /// + /// Requirements: + /// + /// `Other` and `this` must use the same `DataflowAnalysisContext`. + bool equivalentTo(const Environment &Other, + Environment::Comparator &Comparator) const; - LatticeJoinEffect join(const Environment &, Environment::Merger &); + /// Joins `Env1` and `Env2` by taking the intersection of storage locations + /// and values that are stored in them. Distinct values that are assigned to + /// the same storage locations in `Env1` and `Env2` are merged using `Merger`. + /// + /// Requirements: + /// + /// `Other` and `this` must use the same `DataflowAnalysisContext`. + LatticeJoinEffect join(const Environment &Other, Environment::Merger &Merger); // FIXME: Rename `createOrGetStorageLocation` to `getOrCreateStorageLocation`, // `getStableStorageLocation`, or something more appropriate. diff --git a/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h b/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h --- a/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h +++ b/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h @@ -25,6 +25,7 @@ #include "clang/Analysis/FlowSensitive/DataflowLattice.h" #include "llvm/ADT/Any.h" #include "llvm/ADT/Optional.h" +#include "llvm/Support/Error.h" namespace clang { namespace dataflow { @@ -40,7 +41,8 @@ }; /// Type-erased base class for dataflow analyses built on a single lattice type. -class TypeErasedDataflowAnalysis : public Environment::Merger { +class TypeErasedDataflowAnalysis : public Environment::Comparator, + public Environment::Merger { /// Determines whether to apply the built-in transfer functions. // FIXME: Remove this option once the framework supports composing analyses // (at which point the built-in transfer functions can be simply a standalone @@ -115,8 +117,9 @@ /// Performs dataflow analysis and returns a mapping from basic block IDs to /// dataflow analysis states that model the respective basic blocks. Indices -/// of the returned vector correspond to basic block IDs. -std::vector> +/// of the returned vector correspond to basic block IDs. Returns an error if +/// the dataflow analysis cannot be performed successfully. +llvm::Expected>> runTypeErasedDataflowAnalysis(const ControlFlowContext &CFCtx, TypeErasedDataflowAnalysis &Analysis, const Environment &InitEnv); diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp --- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -68,9 +68,46 @@ } } -bool Environment::operator==(const Environment &Other) const { +bool Environment::equivalentTo(const Environment &Other, + Environment::Comparator &Comparator) const { assert(DACtx == Other.DACtx); - return DeclToLoc == Other.DeclToLoc && LocToVal == Other.LocToVal; + + if (DeclToLoc != Other.DeclToLoc) + return false; + + if (ExprToLoc != Other.ExprToLoc) + return false; + + if (LocToVal.size() != Other.LocToVal.size()) + return false; + + for (auto &Entry : LocToVal) { + const StorageLocation *Loc = Entry.first; + assert(Loc != nullptr); + + Value *Val = Entry.second; + assert(Val != nullptr); + + auto It = Other.LocToVal.find(Loc); + if (It == Other.LocToVal.end()) + return false; + assert(It->second != nullptr); + + if (It->second == Val) + continue; + + if (auto *Val1 = dyn_cast(Val)) { + auto *Val2 = cast(It->second); + if (&Val1->getPointeeLoc() == &Val2->getPointeeLoc()) + continue; + } + + if (!Comparator.compareEquivalent(Loc->getType(), *Val, *this, *It->second, + Other)) + return false; + } + + return true; } LatticeJoinEffect Environment::join(const Environment &Other, @@ -111,10 +148,10 @@ continue; } - if (auto *FirstVal = dyn_cast(Val)) { - auto *SecondVal = cast(It->second); - if (&FirstVal->getPointeeLoc() == &SecondVal->getPointeeLoc()) { - LocToVal.insert({Loc, FirstVal}); + if (auto *Val1 = dyn_cast(Val)) { + auto *Val2 = cast(It->second); + if (&Val1->getPointeeLoc() == &Val2->getPointeeLoc()) { + LocToVal.insert({Loc, Val1}); continue; } } diff --git a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp --- a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp +++ b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp @@ -12,6 +12,7 @@ //===----------------------------------------------------------------------===// #include +#include #include #include @@ -26,7 +27,7 @@ #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/None.h" #include "llvm/ADT/Optional.h" -#include "llvm/Support/raw_ostream.h" +#include "llvm/Support/Error.h" namespace clang { namespace dataflow { @@ -190,7 +191,7 @@ return State; } -std::vector> +llvm::Expected>> runTypeErasedDataflowAnalysis(const ControlFlowContext &CFCtx, TypeErasedDataflowAnalysis &Analysis, const Environment &InitEnv) { @@ -216,8 +217,8 @@ static constexpr uint32_t MaxIterations = 1 << 16; while (const CFGBlock *Block = Worklist.dequeue()) { if (++Iterations > MaxIterations) { - llvm::errs() << "Maximum number of iterations reached, giving up.\n"; - break; + return llvm::createStringError(std::errc::timed_out, + "maximum number of iterations reached"); } const llvm::Optional &OldBlockState = @@ -228,7 +229,7 @@ if (OldBlockState.hasValue() && Analysis.isEqualTypeErased(OldBlockState.getValue().Lattice, NewBlockState.Lattice) && - OldBlockState->Env == NewBlockState.Env) { + OldBlockState->Env.equivalentTo(NewBlockState.Env, Analysis)) { // The state of `Block` didn't change after transfer so there's no need to // revisit its successors. continue; diff --git a/clang/unittests/Analysis/FlowSensitive/TestingSupport.h b/clang/unittests/Analysis/FlowSensitive/TestingSupport.h --- a/clang/unittests/Analysis/FlowSensitive/TestingSupport.h +++ b/clang/unittests/Analysis/FlowSensitive/TestingSupport.h @@ -112,11 +112,13 @@ StmtToAnnotations = buildStatementToAnnotationMapping(F, AnnotatedCode); if (!StmtToAnnotations) return StmtToAnnotations.takeError(); - auto &Annotations = *StmtToAnnotations; - std::vector> BlockStates = - runTypeErasedDataflowAnalysis(*CFCtx, Analysis, Env); + llvm::Expected>> + MaybeBlockStates = runTypeErasedDataflowAnalysis(*CFCtx, Analysis, Env); + if (!MaybeBlockStates) + return MaybeBlockStates.takeError(); + auto &BlockStates = *MaybeBlockStates; if (BlockStates.empty()) { Expectations({}, Context); diff --git a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp --- a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp +++ b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp @@ -19,6 +19,7 @@ #include "clang/Analysis/FlowSensitive/DataflowLattice.h" #include "clang/Analysis/FlowSensitive/Value.h" #include "clang/Tooling/Tooling.h" +#include "llvm/ADT/Optional.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/StringRef.h" @@ -49,53 +50,35 @@ using ::testing::UnorderedElementsAre; template -class AnalysisCallback : public ast_matchers::MatchFinder::MatchCallback { -public: - AnalysisCallback(AnalysisT (*MakeAnalysis)(ASTContext &)) - : MakeAnalysis(MakeAnalysis) {} - void run(const ast_matchers::MatchFinder::MatchResult &Result) override { - assert(BlockStates.empty()); - - const auto *Func = Result.Nodes.getNodeAs("func"); - assert(Func != nullptr); - - Stmt *Body = Func->getBody(); - assert(Body != nullptr); - - auto CFCtx = llvm::cantFail( - ControlFlowContext::build(nullptr, Body, Result.Context)); - - AnalysisT Analysis = MakeAnalysis(*Result.Context); - DataflowAnalysisContext DACtx; - Environment Env(DACtx); - BlockStates = runDataflowAnalysis(CFCtx, Analysis, Env); - } - - AnalysisT (*MakeAnalysis)(ASTContext &); - std::vector< - llvm::Optional>> - BlockStates; -}; - -template -std::vector>> +llvm::Expected>>> runAnalysis(llvm::StringRef Code, AnalysisT (*MakeAnalysis)(ASTContext &)) { std::unique_ptr AST = tooling::buildASTFromCodeWithArgs(Code, {"-std=c++11"}); - AnalysisCallback Callback(MakeAnalysis); - ast_matchers::MatchFinder Finder; - Finder.addMatcher( - ast_matchers::functionDecl(ast_matchers::hasName("target")).bind("func"), - &Callback); - Finder.matchAST(AST->getASTContext()); + auto *Func = selectFirst( + "func", match(functionDecl(ast_matchers::hasName("target")).bind("func"), + AST->getASTContext())); + assert(Func != nullptr); + + Stmt *Body = Func->getBody(); + assert(Body != nullptr); + + auto CFCtx = llvm::cantFail( + ControlFlowContext::build(nullptr, Body, &AST->getASTContext())); - return Callback.BlockStates; + AnalysisT Analysis = MakeAnalysis(AST->getASTContext()); + DataflowAnalysisContext DACtx; + Environment Env(DACtx); + + return runDataflowAnalysis(CFCtx, Analysis, Env); } TEST(DataflowAnalysisTest, NoopAnalysis) { - auto BlockStates = runAnalysis( - "void target() {}", [](ASTContext &C) { return NoopAnalysis(C, false); }); + auto BlockStates = llvm::cantFail( + runAnalysis("void target() {}", [](ASTContext &C) { + return NoopAnalysis(C, false); + })); EXPECT_EQ(BlockStates.size(), 2u); EXPECT_TRUE(BlockStates[0].hasValue()); EXPECT_TRUE(BlockStates[1].hasValue()); @@ -132,18 +115,15 @@ }; TEST(DataflowAnalysisTest, NonConvergingAnalysis) { - auto BlockStates = runAnalysis( - R"( + std::string Code = R"( void target() { while(true) {} } - )", - [](ASTContext &C) { return NonConvergingAnalysis(C); }); - EXPECT_EQ(BlockStates.size(), 4u); - EXPECT_TRUE(BlockStates[0].hasValue()); - EXPECT_TRUE(BlockStates[1].hasValue()); - EXPECT_TRUE(BlockStates[2].hasValue()); - EXPECT_TRUE(BlockStates[3].hasValue()); + )"; + auto Res = runAnalysis( + Code, [](ASTContext &C) { return NonConvergingAnalysis(C); }); + EXPECT_EQ(llvm::toString(Res.takeError()), + "maximum number of iterations reached"); } struct FunctionCallLattice { @@ -353,6 +333,18 @@ } } + bool compareEquivalent(QualType Type, const Value &Val1, + const Environment &Env1, const Value &Val2, + const Environment &Env2) final { + // Nothing to say about a value that does not model an `OptionalInt`. + if (!Type->isRecordType() || + Type->getAsCXXRecordDecl()->getQualifiedNameAsString() != "OptionalInt") + return true; + + return cast(&Val1)->getProperty("has_value") == + cast(&Val2)->getProperty("has_value"); + } + bool merge(QualType Type, const Value &Val1, const Value &Val2, Value &MergedVal, Environment &Env) final { if (!Type->isRecordType() || @@ -527,4 +519,36 @@ }); } +TEST_F(WideningTest, DistinctValuesWithSamePropertiesAreEquivalent) { + std::string Code = R"( + #include "widening_test_defs.h" + + void target(bool Cond) { + OptionalInt Foo; + Foo = 1; + while (Cond) { + Foo = 2; + } + (void)0; + /*[[p]]*/ + } + )"; + runDataflow( + Code, [](llvm::ArrayRef< + std::pair>> + Results, + ASTContext &ASTCtx) { + ASSERT_THAT(Results, ElementsAre(Pair("p", _))); + const Environment &Env = Results[0].second.Env; + + const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo"); + ASSERT_THAT(FooDecl, NotNull()); + + const auto *FooVal = + cast(Env.getValue(*FooDecl, SkipPast::None)); + EXPECT_EQ(FooVal->getProperty("has_value"), + &Env.getBoolLiteralValue(true)); + }); +} + } // namespace