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,19 +51,36 @@ /// Holds the state of the program (store and heap) at a given program point. class Environment { public: - /// Supplements `Environment` with non-standard join operations. - class Merger { + /// Supplements `Environment` with non-standard comparison and join + /// operations. + class ValueModel { public: - virtual ~Merger() = default; + virtual ~ValueModel() = 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`. + /// Returns true if and only if `Val1` is equivalent to `Val2`. /// /// Requirements: /// /// `Val1` and `Val2` must be distinct. + /// + /// `Val1` and `Val2` must model values of type `Type`. + virtual bool compareEquivalent(QualType Type, const Value &Val1, + const Value &Val2) { + // FIXME: Consider adding QualType to StructValue and removing the Type + // argument here. + return false; + } + + /// 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: + /// + /// `Val1` and `Val2` must be distinct. + /// + /// `Val1`, `Val2`, and `MergedVal` must model values of type `Type`. virtual bool merge(QualType Type, const Value &Val1, const Value &Val2, Value &MergedVal, Environment &Env) { return false; @@ -84,9 +101,29 @@ /// with a symbolic representation of the `this` pointee. Environment(DataflowAnalysisContext &DACtx, const DeclContext &DeclCtx); - bool operator==(const Environment &) const; - - LatticeJoinEffect join(const Environment &, Environment::Merger &); + /// 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 `Model`) values assigned to + /// the same storage locations. + /// + /// Requirements: + /// + /// `Other` and `this` must use the same `DataflowAnalysisContext`. + bool equivalentTo(const Environment &Other, + Environment::ValueModel &Model) const; + + /// Joins the environment with `Other` 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 the environment and `Other` are + /// merged using `Model`. + /// + /// Requirements: + /// + /// `Other` and `this` must use the same `DataflowAnalysisContext`. + LatticeJoinEffect join(const Environment &Other, + Environment::ValueModel &Model); // 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,7 @@ }; /// Type-erased base class for dataflow analyses built on a single lattice type. -class TypeErasedDataflowAnalysis : public Environment::Merger { +class TypeErasedDataflowAnalysis : public Environment::ValueModel { /// 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 +116,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 @@ -41,6 +41,21 @@ return Result; } +/// Returns true if and only if `Val1` is equivalent to `Val2`. +static bool equivalentValues(QualType Type, Value *Val1, Value *Val2, + Environment::ValueModel &Model) { + if (Val1 == Val2) + return true; + + if (auto *IndVal1 = dyn_cast(Val1)) { + auto *IndVal2 = cast(Val2); + assert(IndVal1->getKind() == IndVal2->getKind()); + return &IndVal1->getPointeeLoc() == &IndVal2->getPointeeLoc(); + } + + return Model.compareEquivalent(Type, *Val1, *Val2); +} + Environment::Environment(DataflowAnalysisContext &DACtx, const DeclContext &DeclCtx) : Environment(DACtx) { @@ -68,13 +83,40 @@ } } -bool Environment::operator==(const Environment &Other) const { +bool Environment::equivalentTo(const Environment &Other, + Environment::ValueModel &Model) 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 (!equivalentValues(Loc->getType(), Val, It->second, Model)) + return false; + } + + return true; } LatticeJoinEffect Environment::join(const Environment &Other, - Environment::Merger &Merger) { + Environment::ValueModel &Model) { assert(DACtx == Other.DACtx); auto Effect = LatticeJoinEffect::Unchanged; @@ -89,7 +131,7 @@ if (ExprToLocSizeBefore != ExprToLoc.size()) Effect = LatticeJoinEffect::Changed; - // Move `LocToVal` so that `Environment::Merger::merge` can safely assign + // Move `LocToVal` so that `Environment::ValueModel::merge` can safely assign // values to storage locations while this code iterates over the current // assignments. llvm::DenseMap OldLocToVal = @@ -106,23 +148,16 @@ continue; assert(It->second != nullptr); - if (It->second == Val) { + if (equivalentValues(Loc->getType(), Val, It->second, Model)) { LocToVal.insert({Loc, Val}); continue; } - if (auto *FirstVal = dyn_cast(Val)) { - auto *SecondVal = cast(It->second); - if (&FirstVal->getPointeeLoc() == &SecondVal->getPointeeLoc()) { - LocToVal.insert({Loc, FirstVal}); - continue; - } - } - - // FIXME: Consider destroying `MergedValue` immediately if `Merger::merge` - // returns false to avoid storing unneeded values in `DACtx`. + // FIXME: Consider destroying `MergedValue` immediately if + // `ValueModel::merge` returns false to avoid storing unneeded values in + // `DACtx`. if (Value *MergedVal = createValue(Loc->getType())) - if (Merger.merge(Loc->getType(), *Val, *It->second, *MergedVal, *this)) + if (Model.merge(Loc->getType(), *Val, *It->second, *MergedVal, *this)) LocToVal.insert({Loc, MergedVal}); } if (OldLocToVal.size() != LocToVal.size()) 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); - return Callback.BlockStates; + auto CFCtx = llvm::cantFail( + ControlFlowContext::build(nullptr, Body, &AST->getASTContext())); + + 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 { @@ -317,8 +297,9 @@ class OptionalIntAnalysis : public DataflowAnalysis { public: - explicit OptionalIntAnalysis(ASTContext &Context) - : DataflowAnalysis(Context) {} + explicit OptionalIntAnalysis(ASTContext &Context, BoolValue &HasValueTop) + : DataflowAnalysis(Context), + HasValueTop(HasValueTop) {} static NoopLattice initialElement() { return {}; } @@ -353,8 +334,20 @@ } } + bool compareEquivalent(QualType Type, const Value &Val1, + const Value &Val2) final { + // Nothing to say about a value that does not model an `OptionalInt`. + if (!Type->isRecordType() || + Type->getAsCXXRecordDecl()->getQualifiedNameAsString() != "OptionalInt") + return false; + + 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 { + // Nothing to say about a value that does not model an `OptionalInt`. if (!Type->isRecordType() || Type->getAsCXXRecordDecl()->getQualifiedNameAsString() != "OptionalInt") return false; @@ -369,12 +362,12 @@ if (HasValue2 == nullptr) return false; - if (HasValue1 != HasValue2) - return false; - - cast(&MergedVal)->setProperty("has_value", *HasValue1); + assert(HasValue1 != HasValue2); + cast(&MergedVal)->setProperty("has_value", HasValueTop); return true; } + + BoolValue &HasValueTop; }; class WideningTest : public Test { @@ -392,8 +385,10 @@ ASSERT_THAT_ERROR( test::checkDataflow( Code, "target", - [](ASTContext &Context, Environment &Env) { - return OptionalIntAnalysis(Context); + [this](ASTContext &Context, Environment &Env) { + assert(HasValueTop == nullptr); + HasValueTop = &Env.takeOwnership(std::make_unique()); + return OptionalIntAnalysis(Context, *HasValueTop); }, [&Match]( llvm::ArrayRef< @@ -403,6 +398,8 @@ {"-fsyntax-only", "-std=c++17"}, FilesContents), llvm::Succeeded()); } + + BoolValue *HasValueTop = nullptr; }; TEST_F(WideningTest, JoinDistinctValuesWithDistinctProperties) { @@ -421,10 +418,11 @@ } )"; runDataflow( - Code, [](llvm::ArrayRef< - std::pair>> - Results, - ASTContext &ASTCtx) { + Code, + [this](llvm::ArrayRef< + std::pair>> + Results, + ASTContext &ASTCtx) { ASSERT_THAT(Results, ElementsAre(Pair("p3", _), Pair("p2", _), Pair("p1", _))); const Environment &Env1 = Results[2].second.Env; @@ -442,7 +440,7 @@ &Env1.getBoolLiteralValue(false)); EXPECT_EQ(GetFooValue(Env2)->getProperty("has_value"), &Env2.getBoolLiteralValue(true)); - EXPECT_THAT(Env3.getValue(*FooDecl, SkipPast::None), IsNull()); + EXPECT_EQ(GetFooValue(Env3)->getProperty("has_value"), HasValueTop); }); } @@ -494,7 +492,7 @@ }); } -TEST_F(WideningTest, DistinctPointersToTheSameLocation) { +TEST_F(WideningTest, DistinctPointersToTheSameLocationAreEquivalent) { std::string Code = R"( void target(int Foo, bool Cond) { int *Bar = &Foo; @@ -527,4 +525,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