sgatev created this revision.
sgatev added reviewers: ymandel, xazax.hun, gribozavr2.
Herald added subscribers: tschuett, steakhal, rnkovacs.
sgatev requested review of this revision.
Herald added a project: clang.
Make specializations of `DataflowAnalysis` extendable with domain-specific
logic for comparing distinct values when comparing environments.
This is part of the implementation of the dataflow analysis framework.
See "[RFC] A dataflow analysis framework for Clang AST" on cfe-dev.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D118596
Files:
clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h
clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
clang/unittests/Analysis/FlowSensitive/TestingSupport.h
clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
Index: clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
===================================================================
--- clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
+++ 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 <typename AnalysisT>
-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<FunctionDecl>("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<DataflowAnalysisState<typename AnalysisT::Lattice>>>
- BlockStates;
-};
-
-template <typename AnalysisT>
-std::vector<llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
+llvm::Expected<std::vector<
+ llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>>
runAnalysis(llvm::StringRef Code, AnalysisT (*MakeAnalysis)(ASTContext &)) {
std::unique_ptr<ASTUnit> AST =
tooling::buildASTFromCodeWithArgs(Code, {"-std=c++11"});
- AnalysisCallback<AnalysisT> 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<FunctionDecl>(
+ "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<NoopAnalysis>(
- "void target() {}", [](ASTContext &C) { return NoopAnalysis(C, false); });
+ auto BlockStates = llvm::cantFail(
+ runAnalysis<NoopAnalysis>("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<NonConvergingAnalysis>(
- 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<NonConvergingAnalysis>(
+ 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<StructValue>(&Val1)->getProperty("has_value") ==
+ cast<StructValue>(&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<std::string, DataflowAnalysisState<NoopLattice>>>
+ 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<StructValue>(Env.getValue(*FooDecl, SkipPast::None));
+ EXPECT_EQ(FooVal->getProperty("has_value"),
+ &Env.getBoolLiteralValue(true));
+ });
+}
+
} // namespace
Index: clang/unittests/Analysis/FlowSensitive/TestingSupport.h
===================================================================
--- clang/unittests/Analysis/FlowSensitive/TestingSupport.h
+++ clang/unittests/Analysis/FlowSensitive/TestingSupport.h
@@ -112,11 +112,13 @@
StmtToAnnotations = buildStatementToAnnotationMapping(F, AnnotatedCode);
if (!StmtToAnnotations)
return StmtToAnnotations.takeError();
-
auto &Annotations = *StmtToAnnotations;
- std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> BlockStates =
- runTypeErasedDataflowAnalysis(*CFCtx, Analysis, Env);
+ llvm::Expected<std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>>
+ MaybeBlockStates = runTypeErasedDataflowAnalysis(*CFCtx, Analysis, Env);
+ if (!MaybeBlockStates)
+ return MaybeBlockStates.takeError();
+ auto &BlockStates = *MaybeBlockStates;
if (BlockStates.empty()) {
Expectations({}, Context);
Index: clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
===================================================================
--- clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
+++ clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
@@ -12,6 +12,7 @@
//===----------------------------------------------------------------------===//
#include <memory>
+#include <system_error>
#include <utility>
#include <vector>
@@ -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::Optional<TypeErasedDataflowAnalysisState>>
+llvm::Expected<std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>>
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<TypeErasedDataflowAnalysisState> &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;
Index: clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
===================================================================
--- clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
+++ 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<IndirectionValue>(Val)) {
+ auto *Val2 = cast<IndirectionValue>(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<PointerValue>(Val)) {
- auto *SecondVal = cast<PointerValue>(It->second);
- if (&FirstVal->getPointeeLoc() == &SecondVal->getPointeeLoc()) {
- LocToVal.insert({Loc, FirstVal});
+ if (auto *Val1 = dyn_cast<PointerValue>(Val)) {
+ auto *Val2 = cast<PointerValue>(It->second);
+ if (&Val1->getPointeeLoc() == &Val2->getPointeeLoc()) {
+ LocToVal.insert({Loc, Val1});
continue;
}
}
Index: clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
===================================================================
--- clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
+++ 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<llvm::Optional<TypeErasedDataflowAnalysisState>>
+/// of the returned vector correspond to basic block IDs. Returns an error if
+/// the dataflow analysis cannot be performed successfully.
+llvm::Expected<std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>>
runTypeErasedDataflowAnalysis(const ControlFlowContext &CFCtx,
TypeErasedDataflowAnalysis &Analysis,
const Environment &InitEnv);
Index: clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
===================================================================
--- clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
+++ 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.
Index: clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h
===================================================================
--- clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h
+++ 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 <typename AnalysisT>
-std::vector<llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
+llvm::Expected<std::vector<
+ llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>>
runDataflowAnalysis(const ControlFlowContext &CFCtx, AnalysisT &Analysis,
const Environment &InitEnv) {
auto TypeErasedBlockStates =
runTypeErasedDataflowAnalysis(CFCtx, Analysis, InitEnv);
+ if (!TypeErasedBlockStates)
+ return TypeErasedBlockStates.takeError();
+
std::vector<
llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
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<typename AnalysisT::Lattice>{
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
