sgatev created this revision.
sgatev added reviewers: ymandel, xazax.hun, gribozavr2.
Herald added subscribers: rnkovacs, mgorny.
sgatev requested review of this revision.
Herald added a project: clang.
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/D116368
Files:
clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h
clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
clang/include/clang/Analysis/FlowSensitive/StorageLocation.h
clang/include/clang/Analysis/FlowSensitive/Transfer.h
clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
clang/include/clang/Analysis/FlowSensitive/Value.h
clang/lib/Analysis/FlowSensitive/CMakeLists.txt
clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
clang/lib/Analysis/FlowSensitive/Transfer.cpp
clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
clang/unittests/Analysis/FlowSensitive/CMakeLists.txt
clang/unittests/Analysis/FlowSensitive/NoopAnalysis.h
clang/unittests/Analysis/FlowSensitive/TestingSupport.h
clang/unittests/Analysis/FlowSensitive/TestingSupportTest.cpp
clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
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
@@ -6,12 +6,14 @@
//
//===----------------------------------------------------------------------===//
+#include "NoopAnalysis.h"
#include "TestingSupport.h"
#include "clang/AST/Decl.h"
#include "clang/ASTMatchers/ASTMatchFinder.h"
#include "clang/ASTMatchers/ASTMatchers.h"
#include "clang/Analysis/CFG.h"
#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
+#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
#include "clang/Tooling/Tooling.h"
@@ -28,6 +30,8 @@
#include <utility>
#include <vector>
+namespace {
+
using namespace clang;
using namespace dataflow;
using ::testing::IsEmpty;
@@ -50,7 +54,8 @@
ControlFlowContext::build(nullptr, Body, Result.Context));
AnalysisT Analysis(*Result.Context);
- Environment Env;
+ DataflowAnalysisContext DACtx;
+ Environment Env(DACtx);
BlockStates = runDataflowAnalysis(CFCtx, Analysis, Env);
}
@@ -75,27 +80,6 @@
return Callback.BlockStates;
}
-class NoopLattice {
-public:
- bool operator==(const NoopLattice &) const { return true; }
-
- LatticeJoinEffect join(const NoopLattice &) {
- return LatticeJoinEffect::Unchanged;
- }
-};
-
-class NoopAnalysis : public DataflowAnalysis<NoopAnalysis, NoopLattice> {
-public:
- NoopAnalysis(ASTContext &Context)
- : DataflowAnalysis<NoopAnalysis, NoopLattice>(Context) {}
-
- static NoopLattice initialElement() { return {}; }
-
- NoopLattice transfer(const Stmt *S, const NoopLattice &E, Environment &Env) {
- return {};
- }
-};
-
TEST(DataflowAnalysisTest, NoopAnalysis) {
auto BlockStates = runAnalysis<NoopAnalysis>(R"(
void target() {}
@@ -314,3 +298,5 @@
UnorderedElementsAre("baz", "foo"))))));
// FIXME: Called functions at point `p` should contain only "foo".
}
+
+} // namespace
Index: clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
===================================================================
--- /dev/null
+++ clang/unittests/Analysis/FlowSensitive/TransferTest.cpp
@@ -0,0 +1,617 @@
+//===- unittests/Analysis/FlowSensitive/TransferTest.cpp ------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "NoopAnalysis.h"
+#include "TestingSupport.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/Decl.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "clang/Analysis/FlowSensitive/StorageLocation.h"
+#include "clang/Analysis/FlowSensitive/Value.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Casting.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include <cassert>
+#include <string>
+#include <utility>
+
+namespace {
+
+using namespace clang;
+using namespace dataflow;
+using ::testing::_;
+using ::testing::ElementsAre;
+using ::testing::IsNull;
+using ::testing::NotNull;
+using ::testing::Pair;
+
+class TransferTest : public ::testing::Test {
+protected:
+ template <typename Matcher>
+ void runDataflow(llvm::StringRef Code, Matcher Match) {
+ test::checkDataflow<NoopAnalysis>(
+ Code, "target",
+ [](ASTContext &C, Environment &) { return NoopAnalysis(C); },
+ [&Match](llvm::ArrayRef<
+ std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+ Results,
+ ASTContext &ASTCtx) { Match(Results, ASTCtx); },
+ {"-fsyntax-only", "-std=c++17"});
+ }
+};
+
+/// Returns the `ValueDecl` for the given identifier.
+///
+/// Requirements:
+///
+/// `Name` must be unique in `ASTCtx`.
+static const ValueDecl *findValueDecl(ASTContext &ASTCtx,
+ llvm::StringRef Name) {
+ auto TargetNodes = ast_matchers::match(
+ ast_matchers::valueDecl(ast_matchers::hasName(Name)).bind("v"), ASTCtx);
+ assert(TargetNodes.size() == 1 && "Name must be unique");
+ auto *const Result = ast_matchers::selectFirst<ValueDecl>("v", TargetNodes);
+ assert(Result != nullptr);
+ return Result;
+}
+
+TEST_F(TransferTest, IntVarDecl) {
+ std::string Code = R"(
+ void target() {
+ int foo;
+ // [[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 StorageLocation *FooLoc = Env.getStorageLocation(FooDecl);
+ ASSERT_TRUE(isa_and_nonnull<ScalarStorageLocation>(FooLoc));
+
+ const Value *FooVal = Env.getValue(FooLoc);
+ ASSERT_TRUE(isa_and_nonnull<IntegerValue>(FooVal));
+ });
+}
+
+TEST_F(TransferTest, FloatVarDecl) {
+ std::string Code = R"(
+ void target() {
+ float foo;
+ // [[p]]
+ }
+ )";
+ runDataflow(Code,
+ [](llvm::ArrayRef<
+ std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+ Results,
+ ASTContext &ASTCtx) {
+ ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+ const auto Env = Results[0].second.Env;
+
+ const ValueDecl *FooDecl = findValueDecl(ASTCtx, "foo");
+ ASSERT_THAT(FooDecl, NotNull());
+
+ const StorageLocation *FooLoc = Env.getStorageLocation(FooDecl);
+ ASSERT_TRUE(isa_and_nonnull<ScalarStorageLocation>(FooLoc));
+
+ const Value *FooVal = Env.getValue(FooLoc);
+ ASSERT_TRUE(isa_and_nonnull<FloatValue>(FooVal));
+ });
+}
+
+TEST_F(TransferTest, DoubleVarDecl) {
+ std::string Code = R"(
+ void target() {
+ double foo;
+ // [[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 StorageLocation *FooLoc = Env.getStorageLocation(FooDecl);
+ ASSERT_TRUE(isa_and_nonnull<ScalarStorageLocation>(FooLoc));
+
+ const Value *FooVal = Env.getValue(FooLoc);
+ ASSERT_TRUE(isa_and_nonnull<FloatValue>(FooVal));
+ });
+}
+
+TEST_F(TransferTest, StructVarDecl) {
+ std::string Code = R"(
+ struct Foo {
+ int Bar;
+ double Baz;
+ };
+
+ void target() {
+ Foo foo;
+ // [[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());
+
+ ASSERT_TRUE(FooDecl->getType()->isStructureType());
+ auto FooFields = FooDecl->getType()->getAsRecordDecl()->fields();
+
+ FieldDecl *BarDecl = nullptr;
+ FieldDecl *BazDecl = nullptr;
+ for (FieldDecl *Field : FooFields) {
+ if (Field->getNameAsString() == "Bar") {
+ BarDecl = Field;
+ } else if (Field->getNameAsString() == "Baz") {
+ BazDecl = Field;
+ }
+ }
+ ASSERT_THAT(BarDecl, NotNull());
+ ASSERT_THAT(BazDecl, NotNull());
+
+ const auto *FooLoc =
+ cast<AggregateStorageLocation>(Env.getStorageLocation(FooDecl));
+ const auto *BarLoc =
+ cast<ScalarStorageLocation>(FooLoc->getChild(BarDecl));
+ const auto *BazLoc =
+ cast<ScalarStorageLocation>(FooLoc->getChild(BazDecl));
+
+ const auto *FooVal = cast<StructValue>(Env.getValue(FooLoc));
+ const auto *BarVal = cast<IntegerValue>(FooVal->getChild(BarDecl));
+ const auto *BazVal = cast<FloatValue>(FooVal->getChild(BazDecl));
+
+ ASSERT_EQ(Env.getValue(BarLoc), BarVal);
+ ASSERT_EQ(Env.getValue(BazLoc), BazVal);
+ });
+}
+
+TEST_F(TransferTest, ClassVarDecl) {
+ std::string Code = R"(
+ class Foo {
+ int Bar;
+ double Baz;
+ };
+
+ void target() {
+ Foo foo;
+ // [[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());
+
+ ASSERT_TRUE(FooDecl->getType()->isClassType());
+ auto FooFields = FooDecl->getType()->getAsRecordDecl()->fields();
+
+ FieldDecl *BarDecl = nullptr;
+ FieldDecl *BazDecl = nullptr;
+ for (FieldDecl *Field : FooFields) {
+ if (Field->getNameAsString() == "Bar") {
+ BarDecl = Field;
+ } else if (Field->getNameAsString() == "Baz") {
+ BazDecl = Field;
+ } else {
+ FAIL() << "Unexpected field: " << Field->getNameAsString();
+ }
+ }
+ ASSERT_THAT(BarDecl, NotNull());
+ ASSERT_THAT(BazDecl, NotNull());
+
+ const auto *FooLoc =
+ cast<AggregateStorageLocation>(Env.getStorageLocation(FooDecl));
+ const auto *BarLoc =
+ cast<ScalarStorageLocation>(FooLoc->getChild(BarDecl));
+ const auto *BazLoc =
+ cast<ScalarStorageLocation>(FooLoc->getChild(BazDecl));
+
+ const auto *FooVal = cast<StructValue>(Env.getValue(FooLoc));
+ const auto *BarVal = cast<IntegerValue>(FooVal->getChild(BarDecl));
+ const auto *BazVal = cast<FloatValue>(FooVal->getChild(BazDecl));
+
+ ASSERT_EQ(Env.getValue(BarLoc), BarVal);
+ ASSERT_EQ(Env.getValue(BazLoc), BazVal);
+ });
+}
+
+TEST_F(TransferTest, ReferenceVarDecl) {
+ std::string Code = R"(
+ struct Foo {};
+
+ Foo& getFoo();
+
+ void target() {
+ Foo& foo = getFoo();
+ // [[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 StorageLocation *FooLoc = Env.getStorageLocation(FooDecl);
+ ASSERT_TRUE(isa_and_nonnull<ScalarStorageLocation>(FooLoc));
+
+ const ReferenceValue *FooVal =
+ cast<ReferenceValue>(Env.getValue(FooLoc));
+ const StorageLocation *FooPointeeLoc = FooVal->getLocation();
+ ASSERT_TRUE(isa_and_nonnull<AggregateStorageLocation>(FooPointeeLoc));
+
+ const Value *FooPointeeVal = Env.getValue(FooPointeeLoc);
+ ASSERT_TRUE(isa_and_nonnull<StructValue>(FooPointeeVal));
+ });
+}
+
+TEST_F(TransferTest, SelfReferentialReferenceVarDecl) {
+ std::string Code = R"(
+ struct Foo;
+
+ struct Baz {};
+
+ struct Bar {
+ Foo& FooRef;
+ Foo* FooPtr;
+ Baz& BazRef;
+ Baz* BazPtr;
+ };
+
+ struct Foo {
+ Bar& Bar;
+ };
+
+ Foo& getFoo();
+
+ void target() {
+ Foo& foo = getFoo();
+ // [[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());
+
+ ASSERT_TRUE(FooDecl->getType()->isReferenceType());
+ ASSERT_TRUE(FooDecl->getType().getNonReferenceType()->isStructureType());
+ const auto FooFields =
+ FooDecl->getType().getNonReferenceType()->getAsRecordDecl()->fields();
+
+ FieldDecl *BarDecl = nullptr;
+ for (FieldDecl *Field : FooFields) {
+ if (Field->getNameAsString() == "Bar") {
+ BarDecl = Field;
+ } else {
+ FAIL() << "Unexpected field: " << Field->getNameAsString();
+ }
+ }
+ ASSERT_THAT(BarDecl, NotNull());
+
+ ASSERT_TRUE(BarDecl->getType()->isReferenceType());
+ ASSERT_TRUE(BarDecl->getType().getNonReferenceType()->isStructureType());
+ const auto BarFields =
+ BarDecl->getType().getNonReferenceType()->getAsRecordDecl()->fields();
+
+ FieldDecl *FooRefDecl = nullptr;
+ FieldDecl *FooPtrDecl = nullptr;
+ FieldDecl *BazRefDecl = nullptr;
+ FieldDecl *BazPtrDecl = nullptr;
+ for (FieldDecl *Field : BarFields) {
+ if (Field->getNameAsString() == "FooRef") {
+ FooRefDecl = Field;
+ } else if (Field->getNameAsString() == "FooPtr") {
+ FooPtrDecl = Field;
+ } else if (Field->getNameAsString() == "BazRef") {
+ BazRefDecl = Field;
+ } else if (Field->getNameAsString() == "BazPtr") {
+ BazPtrDecl = Field;
+ } else {
+ FAIL() << "Unexpected field: " << Field->getNameAsString();
+ }
+ }
+ ASSERT_THAT(FooRefDecl, NotNull());
+ ASSERT_THAT(FooPtrDecl, NotNull());
+ ASSERT_THAT(BazRefDecl, NotNull());
+ ASSERT_THAT(BazPtrDecl, NotNull());
+
+ const auto *FooLoc =
+ cast<ScalarStorageLocation>(Env.getStorageLocation(FooDecl));
+ const auto *FooVal = cast<ReferenceValue>(Env.getValue(FooLoc));
+ const auto *FooPointeeVal =
+ cast<StructValue>(Env.getValue(FooVal->getLocation()));
+
+ const auto *BarVal = cast<ReferenceValue>(FooPointeeVal->getChild(BarDecl));
+ const auto *BarPointeeVal =
+ cast<StructValue>(Env.getValue(BarVal->getLocation()));
+
+ const auto *FooRefVal =
+ cast<ReferenceValue>(BarPointeeVal->getChild(FooRefDecl));
+ const StorageLocation *FooRefPointeeLoc = FooRefVal->getLocation();
+ ASSERT_THAT(FooRefPointeeLoc, NotNull());
+ ASSERT_THAT(Env.getValue(FooRefPointeeLoc), IsNull());
+
+ const auto *FooPtrVal =
+ cast<PointerValue>(BarPointeeVal->getChild(FooPtrDecl));
+ const StorageLocation *FooPtrPointeeLoc = FooPtrVal->getLocation();
+ ASSERT_THAT(FooPtrPointeeLoc, NotNull());
+ ASSERT_THAT(Env.getValue(FooPtrPointeeLoc), IsNull());
+
+ const auto *BazRefVal =
+ cast<ReferenceValue>(BarPointeeVal->getChild(BazRefDecl));
+ const StorageLocation *BazRefPointeeLoc = BazRefVal->getLocation();
+ ASSERT_THAT(BazRefPointeeLoc, NotNull());
+ ASSERT_THAT(Env.getValue(BazRefPointeeLoc), NotNull());
+
+ const auto *BazPtrVal =
+ cast<PointerValue>(BarPointeeVal->getChild(BazPtrDecl));
+ const StorageLocation *BazPtrPointeeLoc = BazPtrVal->getLocation();
+ ASSERT_THAT(BazPtrPointeeLoc, NotNull());
+ ASSERT_THAT(Env.getValue(BazPtrPointeeLoc), NotNull());
+ });
+}
+
+TEST_F(TransferTest, PointerVarDecl) {
+ std::string Code = R"(
+ struct Foo {};
+
+ Foo* getFoo();
+
+ void target() {
+ Foo* foo = getFoo();
+ // [[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 StorageLocation *FooLoc = Env.getStorageLocation(FooDecl);
+ ASSERT_TRUE(isa_and_nonnull<ScalarStorageLocation>(FooLoc));
+
+ const PointerValue *FooVal = cast<PointerValue>(Env.getValue(FooLoc));
+ const StorageLocation *FooPointeeLoc = FooVal->getLocation();
+ ASSERT_TRUE(isa_and_nonnull<AggregateStorageLocation>(FooPointeeLoc));
+
+ const Value *FooPointeeVal = Env.getValue(FooPointeeLoc);
+ ASSERT_TRUE(isa_and_nonnull<StructValue>(FooPointeeVal));
+ });
+}
+
+TEST_F(TransferTest, SelfReferentialPointerVarDecl) {
+ std::string Code = R"(
+ struct Foo;
+
+ struct Baz {};
+
+ struct Bar {
+ Foo& FooRef;
+ Foo* FooPtr;
+ Baz& BazRef;
+ Baz* BazPtr;
+ };
+
+ struct Foo {
+ Bar* Bar;
+ };
+
+ Foo* getFoo();
+
+ void target() {
+ Foo* foo = getFoo();
+ // [[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());
+
+ ASSERT_TRUE(FooDecl->getType()->isPointerType());
+ ASSERT_TRUE(FooDecl->getType()
+ ->getAs<PointerType>()
+ ->getPointeeType()
+ ->isStructureType());
+ const auto FooFields = FooDecl->getType()
+ ->getAs<PointerType>()
+ ->getPointeeType()
+ ->getAsRecordDecl()
+ ->fields();
+
+ FieldDecl *BarDecl = nullptr;
+ for (FieldDecl *Field : FooFields) {
+ if (Field->getNameAsString() == "Bar") {
+ BarDecl = Field;
+ } else {
+ FAIL() << "Unexpected field: " << Field->getNameAsString();
+ }
+ }
+ ASSERT_THAT(BarDecl, NotNull());
+
+ ASSERT_TRUE(BarDecl->getType()->isPointerType());
+ ASSERT_TRUE(BarDecl->getType()
+ ->getAs<PointerType>()
+ ->getPointeeType()
+ ->isStructureType());
+ const auto BarFields = BarDecl->getType()
+ ->getAs<PointerType>()
+ ->getPointeeType()
+ ->getAsRecordDecl()
+ ->fields();
+
+ FieldDecl *FooRefDecl = nullptr;
+ FieldDecl *FooPtrDecl = nullptr;
+ FieldDecl *BazRefDecl = nullptr;
+ FieldDecl *BazPtrDecl = nullptr;
+ for (FieldDecl *Field : BarFields) {
+ if (Field->getNameAsString() == "FooRef") {
+ FooRefDecl = Field;
+ } else if (Field->getNameAsString() == "FooPtr") {
+ FooPtrDecl = Field;
+ } else if (Field->getNameAsString() == "BazRef") {
+ BazRefDecl = Field;
+ } else if (Field->getNameAsString() == "BazPtr") {
+ BazPtrDecl = Field;
+ } else {
+ FAIL() << "Unexpected field: " << Field->getNameAsString();
+ }
+ }
+ ASSERT_THAT(FooRefDecl, NotNull());
+ ASSERT_THAT(FooPtrDecl, NotNull());
+ ASSERT_THAT(BazRefDecl, NotNull());
+ ASSERT_THAT(BazPtrDecl, NotNull());
+
+ const auto *FooLoc =
+ cast<ScalarStorageLocation>(Env.getStorageLocation(FooDecl));
+ const auto *FooVal = cast<PointerValue>(Env.getValue(FooLoc));
+ const auto *FooPointeeVal =
+ cast<StructValue>(Env.getValue(FooVal->getLocation()));
+
+ const auto *BarVal =
+ cast<PointerValue>(FooPointeeVal->getChild(BarDecl));
+ const auto *BarPointeeVal =
+ cast<StructValue>(Env.getValue(BarVal->getLocation()));
+
+ const auto *FooRefVal =
+ cast<ReferenceValue>(BarPointeeVal->getChild(FooRefDecl));
+ const StorageLocation *FooRefPointeeLoc = FooRefVal->getLocation();
+ ASSERT_THAT(FooRefPointeeLoc, NotNull());
+ ASSERT_THAT(Env.getValue(FooRefPointeeLoc), IsNull());
+
+ const auto *FooPtrVal =
+ cast<PointerValue>(BarPointeeVal->getChild(FooPtrDecl));
+ const StorageLocation *FooPtrPointeeLoc = FooPtrVal->getLocation();
+ ASSERT_THAT(FooPtrPointeeLoc, NotNull());
+ ASSERT_THAT(Env.getValue(FooPtrPointeeLoc), IsNull());
+
+ const auto *BazRefVal =
+ cast<ReferenceValue>(BarPointeeVal->getChild(BazRefDecl));
+ const StorageLocation *BazRefPointeeLoc = BazRefVal->getLocation();
+ ASSERT_THAT(BazRefPointeeLoc, NotNull());
+ ASSERT_THAT(Env.getValue(BazRefPointeeLoc), NotNull());
+
+ const auto *BazPtrVal =
+ cast<PointerValue>(BarPointeeVal->getChild(BazPtrDecl));
+ const StorageLocation *BazPtrPointeeLoc = BazPtrVal->getLocation();
+ ASSERT_THAT(BazPtrPointeeLoc, NotNull());
+ ASSERT_THAT(Env.getValue(BazPtrPointeeLoc), NotNull());
+ });
+}
+
+TEST_F(TransferTest, JoinVarDecl) {
+ std::string Code = R"(
+ void target(bool b) {
+ int foo;
+ // [[p1]]
+ if (b) {
+ int bar;
+ // [[p2]]
+ } else {
+ int baz;
+ // [[p3]]
+ }
+ (void)0;
+ // [[p4]]
+ }
+ )";
+ runDataflow(
+ Code, [](llvm::ArrayRef<
+ std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+ Results,
+ ASTContext &ASTCtx) {
+ ASSERT_THAT(Results, ElementsAre(Pair("p4", _), Pair("p3", _),
+ Pair("p2", _), Pair("p1", _)));
+ const ValueDecl *FooDecl = findValueDecl(ASTCtx, "foo");
+ ASSERT_THAT(FooDecl, NotNull());
+
+ const ValueDecl *BarDecl = findValueDecl(ASTCtx, "bar");
+ ASSERT_THAT(BarDecl, NotNull());
+
+ const ValueDecl *BazDecl = findValueDecl(ASTCtx, "baz");
+ ASSERT_THAT(BazDecl, NotNull());
+
+ const Environment &Env1 = Results[3].second.Env;
+ const StorageLocation *FooLoc = Env1.getStorageLocation(FooDecl);
+ ASSERT_THAT(FooLoc, NotNull());
+ ASSERT_THAT(Env1.getStorageLocation(BarDecl), IsNull());
+ ASSERT_THAT(Env1.getStorageLocation(BazDecl), IsNull());
+
+ const Environment &Env2 = Results[2].second.Env;
+ ASSERT_EQ(Env2.getStorageLocation(FooDecl), FooLoc);
+ ASSERT_THAT(Env2.getStorageLocation(BarDecl), NotNull());
+ ASSERT_THAT(Env2.getStorageLocation(BazDecl), IsNull());
+
+ const Environment &Env3 = Results[1].second.Env;
+ ASSERT_EQ(Env3.getStorageLocation(FooDecl), FooLoc);
+ ASSERT_THAT(Env3.getStorageLocation(BarDecl), IsNull());
+ ASSERT_THAT(Env3.getStorageLocation(BazDecl), NotNull());
+
+ const Environment &Env4 = Results[0].second.Env;
+ ASSERT_EQ(Env4.getStorageLocation(FooDecl), FooLoc);
+ ASSERT_THAT(Env4.getStorageLocation(BarDecl), IsNull());
+ ASSERT_THAT(Env4.getStorageLocation(BazDecl), IsNull());
+ });
+}
+
+} // namespace
Index: clang/unittests/Analysis/FlowSensitive/TestingSupportTest.cpp
===================================================================
--- clang/unittests/Analysis/FlowSensitive/TestingSupportTest.cpp
+++ clang/unittests/Analysis/FlowSensitive/TestingSupportTest.cpp
@@ -1,4 +1,5 @@
#include "TestingSupport.h"
+#include "NoopAnalysis.h"
#include "clang/AST/ASTContext.h"
#include "clang/ASTMatchers/ASTMatchFinder.h"
#include "clang/ASTMatchers/ASTMatchers.h"
@@ -19,32 +20,6 @@
using ::testing::Pair;
using ::testing::UnorderedElementsAre;
-class NoopLattice {
-public:
- bool operator==(const NoopLattice &) const { return true; }
-
- LatticeJoinEffect join(const NoopLattice &) {
- return LatticeJoinEffect::Unchanged;
- }
-};
-
-std::ostream &operator<<(std::ostream &OS, const NoopLattice &S) {
- OS << "noop";
- return OS;
-}
-
-class NoopAnalysis : public DataflowAnalysis<NoopAnalysis, NoopLattice> {
-public:
- NoopAnalysis(ASTContext &Context)
- : DataflowAnalysis<NoopAnalysis, NoopLattice>(Context) {}
-
- static NoopLattice initialElement() { return {}; }
-
- NoopLattice transfer(const Stmt *S, const NoopLattice &E, Environment &Env) {
- return {};
- }
-};
-
template <typename T>
const FunctionDecl *findTargetFunc(ASTContext &Context, T FunctionMatcher) {
auto TargetMatcher =
Index: clang/unittests/Analysis/FlowSensitive/TestingSupport.h
===================================================================
--- clang/unittests/Analysis/FlowSensitive/TestingSupport.h
+++ clang/unittests/Analysis/FlowSensitive/TestingSupport.h
@@ -98,7 +98,8 @@
auto CFCtx = ControlFlowContext::build(F, F->getBody(), &F->getASTContext());
ASSERT_TRUE((bool)CFCtx) << "Could not build ControlFlowContext.";
- Environment Env;
+ DataflowAnalysisContext DACtx;
+ Environment Env(DACtx);
auto Analysis = MakeAnalysis(Context, Env);
llvm::Expected<llvm::DenseMap<const clang::Stmt *, std::string>>
Index: clang/unittests/Analysis/FlowSensitive/NoopAnalysis.h
===================================================================
--- /dev/null
+++ clang/unittests/Analysis/FlowSensitive/NoopAnalysis.h
@@ -0,0 +1,55 @@
+//===-- NoopAnalysis.h ------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a NoopAnalysis class that is used by dataflow analysis
+// tests.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_UNITTESTS_ANALYSIS_FLOWSENSITIVE_NOOPANALYSIS_H
+#define LLVM_CLANG_UNITTESTS_ANALYSIS_FLOWSENSITIVE_NOOPANALYSIS_H
+
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/Stmt.h"
+#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
+#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
+#include <ostream>
+
+namespace clang {
+namespace dataflow {
+
+class NoopLattice {
+public:
+ bool operator==(const NoopLattice &) const { return true; }
+
+ LatticeJoinEffect join(const NoopLattice &) {
+ return LatticeJoinEffect::Unchanged;
+ }
+};
+
+inline std::ostream &operator<<(std::ostream &OS, const NoopLattice &) {
+ return OS << "noop";
+}
+
+class NoopAnalysis : public DataflowAnalysis<NoopAnalysis, NoopLattice> {
+public:
+ NoopAnalysis(ASTContext &Context)
+ : DataflowAnalysis<NoopAnalysis, NoopLattice>(Context) {}
+
+ static NoopLattice initialElement() { return {}; }
+
+ NoopLattice transfer(const Stmt *S, const NoopLattice &E, Environment &Env) {
+ return {};
+ }
+};
+
+} // namespace dataflow
+} // namespace clang
+
+#endif // LLVM_CLANG_UNITTESTS_ANALYSIS_FLOWSENSITIVE_NOOPANALYSIS_H
Index: clang/unittests/Analysis/FlowSensitive/CMakeLists.txt
===================================================================
--- clang/unittests/Analysis/FlowSensitive/CMakeLists.txt
+++ clang/unittests/Analysis/FlowSensitive/CMakeLists.txt
@@ -7,6 +7,7 @@
SingleVarConstantPropagationTest.cpp
TestingSupport.cpp
TestingSupportTest.cpp
+ TransferTest.cpp
TypeErasedDataflowAnalysisTest.cpp
)
Index: clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
===================================================================
--- clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
+++ clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
@@ -18,6 +18,7 @@
#include "clang/Analysis/CFG.h"
#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
#include "clang/Analysis/FlowSensitive/DataflowWorklist.h"
+#include "clang/Analysis/FlowSensitive/Transfer.h"
#include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
#include "llvm/ADT/None.h"
#include "llvm/ADT/Optional.h"
@@ -39,12 +40,6 @@
std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> &BlockStates,
const CFGBlock &Block, const Environment &InitEnv,
TypeErasedDataflowAnalysis &Analysis) {
- // FIXME: Consider passing `Block` to `Analysis.typeErasedInitialElement()`
- // to enable building analyses like computation of dominators that initialize
- // the state of each basic block differently.
- TypeErasedDataflowAnalysisState State = {Analysis.typeErasedInitialElement(),
- InitEnv};
-
llvm::DenseSet<const CFGBlock *> Preds;
Preds.insert(Block.pred_begin(), Block.pred_end());
if (Block.getTerminator().isTemporaryDtorsBranch()) {
@@ -77,6 +72,7 @@
}
}
+ llvm::Optional<TypeErasedDataflowAnalysisState> MaybeState;
for (const CFGBlock *Pred : Preds) {
// Skip if the `Block` is unreachable or control flow cannot get past it.
if (!Pred || Pred->hasNoReturnElement())
@@ -91,10 +87,20 @@
const TypeErasedDataflowAnalysisState &PredState =
MaybePredState.getValue();
- Analysis.joinTypeErased(State.Lattice, PredState.Lattice);
- State.Env.join(PredState.Env);
+ if (MaybeState.hasValue()) {
+ Analysis.joinTypeErased(MaybeState->Lattice, PredState.Lattice);
+ MaybeState->Env.join(PredState.Env);
+ } else {
+ MaybeState = PredState;
+ }
}
- return State;
+ if (!MaybeState.hasValue()) {
+ // FIXME: Consider passing `Block` to `Analysis.typeErasedInitialElement()`
+ // to enable building analyses like computation of dominators that
+ // initialize the state of each basic block differently.
+ MaybeState.emplace(Analysis.typeErasedInitialElement(), InitEnv);
+ }
+ return *MaybeState;
}
TypeErasedDataflowAnalysisState transferBlock(
@@ -109,16 +115,16 @@
computeBlockInputState(CFCtx, BlockStates, Block, InitEnv, Analysis);
for (const CFGElement &Element : Block) {
// FIXME: Evaluate other kinds of `CFGElement`.
- const llvm::Optional<CFGStmt> Stmt = Element.getAs<CFGStmt>();
- if (!Stmt.hasValue())
+ const llvm::Optional<CFGStmt> CfgStmt = Element.getAs<CFGStmt>();
+ if (!CfgStmt.hasValue())
continue;
- // FIXME: Evaluate the statement contained in `Stmt`.
+ const Stmt *S = CfgStmt.getValue().getStmt();
+ transfer(S, State.Env);
+ State.Lattice = Analysis.transferTypeErased(S, State.Lattice, State.Env);
- State.Lattice = Analysis.transferTypeErased(Stmt.getValue().getStmt(),
- State.Lattice, State.Env);
if (HandleTransferredStmt != nullptr)
- HandleTransferredStmt(Stmt.getValue(), State);
+ HandleTransferredStmt(CfgStmt.getValue(), State);
}
return State;
}
Index: clang/lib/Analysis/FlowSensitive/Transfer.cpp
===================================================================
--- /dev/null
+++ clang/lib/Analysis/FlowSensitive/Transfer.cpp
@@ -0,0 +1,47 @@
+//===-- Transfer.cpp --------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines transfer functions that evaluate program statements and
+// update an environment accordingly.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/FlowSensitive/Transfer.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/DeclBase.h"
+#include "clang/AST/Expr.h"
+#include "clang/AST/Stmt.h"
+#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "llvm/Support/Casting.h"
+#include <cassert>
+
+namespace clang {
+namespace dataflow {
+
+static void transferVarDecl(const VarDecl *D, Environment &Env) {
+ auto *Loc = Env.createStorageLocation(D);
+ Env.setStorageLocation(D, Loc);
+ Env.initValueInStorageLocation(Loc, D->getType());
+}
+
+static void transferDeclStmt(const DeclStmt *S, Environment &Env) {
+ if (const auto *D = dyn_cast<VarDecl>(S->getSingleDecl())) {
+ transferVarDecl(D, Env);
+ }
+}
+
+void transfer(const Stmt *S, Environment &Env) {
+ assert(!isa<ParenExpr>(S));
+
+ if (const auto *DS = dyn_cast<DeclStmt>(S)) {
+ transferDeclStmt(DS, Env);
+ }
+}
+
+} // namespace dataflow
+} // namespace clang
Index: clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
===================================================================
--- /dev/null
+++ clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
@@ -0,0 +1,216 @@
+//===-- DataflowEnvironment.cpp ---------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines an Environment class that is used by dataflow analyses
+// that run over Control-Flow Graphs (CFGs) to keep track of the state of the
+// program at given program points.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/Type.h"
+#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
+#include "clang/Analysis/FlowSensitive/StorageLocation.h"
+#include "clang/Analysis/FlowSensitive/Value.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include <memory>
+
+namespace clang {
+namespace dataflow {
+
+/// Returns true if and only if the given maps contain the same set of keys, and
+/// for each key the values stored in both maps are equal.
+template <typename K, typename V>
+bool denseMapsAreEqual(const llvm::DenseMap<K, V> &Map1,
+ const llvm::DenseMap<K, V> &Map2) {
+ if (Map1.size() != Map2.size()) {
+ return false;
+ }
+ for (auto &Entry : Map1) {
+ auto It = Map2.find(Entry.first);
+ if (It == Map2.end() || Entry.second != It->second) {
+ return false;
+ }
+ }
+ return true;
+}
+
+/// Returns a map consisting of key-value entries that are present in both maps.
+template <typename K, typename V>
+llvm::DenseMap<K, V> intersectDenseMaps(const llvm::DenseMap<K, V> &Map1,
+ const llvm::DenseMap<K, V> &Map2) {
+ llvm::DenseMap<K, V> Result;
+ for (auto &Entry : Map1) {
+ auto It = Map2.find(Entry.first);
+ if (It == Map2.end() || Entry.second != It->second) {
+ continue;
+ }
+ Result.insert({Entry.first, Entry.second});
+ }
+ return Result;
+}
+
+bool Environment::operator==(const Environment &Other) const {
+ assert(DACtx == Other.DACtx);
+ return denseMapsAreEqual(DeclToLoc, Other.DeclToLoc) &&
+ denseMapsAreEqual(LocToVal, Other.LocToVal);
+}
+
+LatticeJoinEffect Environment::join(const Environment &Other) {
+ assert(DACtx == Other.DACtx);
+
+ auto Effect = LatticeJoinEffect::Unchanged;
+
+ const unsigned DeclToLocSizeBefore = DeclToLoc.size();
+ DeclToLoc = intersectDenseMaps(DeclToLoc, Other.DeclToLoc);
+ if (DeclToLocSizeBefore != DeclToLoc.size())
+ Effect = LatticeJoinEffect::Changed;
+
+ const unsigned LocToValSizeBefore = LocToVal.size();
+ LocToVal = intersectDenseMaps(LocToVal, Other.LocToVal);
+ if (LocToValSizeBefore != LocToVal.size())
+ Effect = LatticeJoinEffect::Changed;
+
+ return Effect;
+}
+
+StorageLocation *Environment::createStorageLocation(QualType Type) {
+ if (Type->isStructureOrClassType()) {
+ llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
+ for (const FieldDecl *Field : Type->getAsRecordDecl()->fields()) {
+ FieldLocs.insert({Field, createStorageLocation(Field->getType())});
+ }
+ return DACtx->takeOwnership(
+ std::make_unique<AggregateStorageLocation>(Type, std::move(FieldLocs)));
+ }
+ return DACtx->takeOwnership(std::make_unique<ScalarStorageLocation>(Type));
+}
+
+StorageLocation *Environment::createStorageLocation(const VarDecl *D) {
+ assert(D != nullptr);
+ // Evaluated declarations are always assigned the same storage locations to
+ // ensure that the environment stabilizes across loop iterations. Storage
+ // locations for evaluated declarations are stored in the analysis context.
+ if (auto *Loc = DACtx->getStorageLocation(D))
+ return Loc;
+ auto *Loc = createStorageLocation(D->getType());
+ DACtx->setStorageLocation(D, Loc);
+ return Loc;
+}
+
+void Environment::setStorageLocation(const ValueDecl *D, StorageLocation *Loc) {
+ assert(D != nullptr);
+ assert(Loc != nullptr);
+ assert(DeclToLoc.find(D) == DeclToLoc.end());
+ DeclToLoc[D] = Loc;
+}
+
+StorageLocation *Environment::getStorageLocation(const ValueDecl *D) const {
+ assert(D != nullptr);
+ auto It = DeclToLoc.find(D);
+ return It == DeclToLoc.end() ? nullptr : It->second;
+}
+
+Value *Environment::initValueInStorageLocation(const StorageLocation *Loc,
+ QualType Type) {
+ llvm::DenseSet<QualType> Visited;
+ return initValueInStorageLocationUnlessSelfReferential(Loc, Type, Visited);
+}
+
+void Environment::setValue(const StorageLocation *Loc, Value *Value) {
+ assert(Loc != nullptr);
+ assert(Value != nullptr);
+ LocToVal[Loc] = Value;
+}
+
+Value *Environment::getValue(const StorageLocation *Loc) const {
+ assert(Loc != nullptr);
+ auto It = LocToVal.find(Loc);
+ return It == LocToVal.end() ? nullptr : It->second;
+}
+
+Value *Environment::initValueInStorageLocationUnlessSelfReferential(
+ const StorageLocation *Loc, QualType Type,
+ llvm::DenseSet<QualType> &Visited) {
+ assert(Loc != nullptr);
+
+ if (Type->isIntegerType()) {
+ auto *Value = DACtx->takeOwnership(std::make_unique<IntegerValue>());
+ setValue(Loc, Value);
+ return Value;
+ }
+
+ if (Type->isRealFloatingType()) {
+ auto *Value = DACtx->takeOwnership(std::make_unique<FloatValue>());
+ setValue(Loc, Value);
+ return Value;
+ }
+
+ if (Type->isReferenceType()) {
+ QualType PointeeType = Type->getAs<ReferenceType>()->getPointeeType();
+ auto *PointeeLoc = createStorageLocation(PointeeType);
+
+ if (!Visited.contains(PointeeType)) {
+ Visited.insert(PointeeType);
+ initValueInStorageLocationUnlessSelfReferential(PointeeLoc, PointeeType,
+ Visited);
+ Visited.erase(PointeeType);
+ }
+
+ auto *Value =
+ DACtx->takeOwnership(std::make_unique<ReferenceValue>(PointeeLoc));
+ setValue(Loc, Value);
+ return Value;
+ }
+
+ if (Type->isPointerType()) {
+ QualType PointeeType = Type->getAs<PointerType>()->getPointeeType();
+ auto *PointeeLoc = createStorageLocation(PointeeType);
+
+ if (!Visited.contains(PointeeType)) {
+ Visited.insert(PointeeType);
+ initValueInStorageLocationUnlessSelfReferential(PointeeLoc, PointeeType,
+ Visited);
+ Visited.erase(PointeeType);
+ }
+
+ auto *Value =
+ DACtx->takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
+ setValue(Loc, Value);
+ return Value;
+ }
+
+ if (Type->isStructureOrClassType()) {
+ auto *AggregateLoc = cast<AggregateStorageLocation>(Loc);
+
+ llvm::DenseMap<const ValueDecl *, Value *> FieldValues;
+ for (const FieldDecl *Field : Type->getAsRecordDecl()->fields()) {
+ QualType FieldType = Field->getType();
+ if (Visited.contains(FieldType))
+ continue;
+
+ Visited.insert(FieldType);
+ FieldValues.insert(
+ {Field, initValueInStorageLocationUnlessSelfReferential(
+ AggregateLoc->getChild(Field), FieldType, Visited)});
+ Visited.erase(FieldType);
+ }
+
+ auto *Value = DACtx->takeOwnership(
+ std::make_unique<StructValue>(std::move(FieldValues)));
+ setValue(Loc, Value);
+ return Value;
+ }
+
+ return nullptr;
+}
+
+} // namespace dataflow
+} // namespace clang
Index: clang/lib/Analysis/FlowSensitive/CMakeLists.txt
===================================================================
--- clang/lib/Analysis/FlowSensitive/CMakeLists.txt
+++ clang/lib/Analysis/FlowSensitive/CMakeLists.txt
@@ -1,5 +1,7 @@
add_clang_library(clangAnalysisFlowSensitive
ControlFlowContext.cpp
+ DataflowEnvironment.cpp
+ Transfer.cpp
TypeErasedDataflowAnalysis.cpp
LINK_LIBS
Index: clang/include/clang/Analysis/FlowSensitive/Value.h
===================================================================
--- /dev/null
+++ clang/include/clang/Analysis/FlowSensitive/Value.h
@@ -0,0 +1,142 @@
+//===-- Value.h -------------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines classes for values computed by abstract interpretation
+// during dataflow analysis.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H
+#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H
+
+#include "clang/AST/Decl.h"
+#include "clang/Analysis/FlowSensitive/StorageLocation.h"
+#include "llvm/ADT/DenseMap.h"
+#include <cassert>
+#include <utility>
+
+namespace clang {
+namespace dataflow {
+
+/// Base class for all values computed by abstract interpretation.
+class Value {
+public:
+ enum class Kind { Integer, Float, Reference, Pointer, Struct };
+
+ explicit Value(Kind ValKind) : ValKind(ValKind) {}
+
+ virtual ~Value() {}
+
+ Kind getKind() const { return ValKind; }
+
+private:
+ Kind ValKind;
+};
+
+/// Class that models an integer.
+class IntegerValue : public Value {
+public:
+ explicit IntegerValue() : Value(Kind::Integer) {}
+
+ static bool classof(const Value *Val) {
+ return Val->getKind() == Kind::Integer;
+ }
+};
+
+/// Class that models a float.
+class FloatValue : public Value {
+public:
+ explicit FloatValue() : Value(Kind::Float) {}
+
+ static bool classof(const Value *Val) {
+ return Val->getKind() == Kind::Float;
+ }
+};
+
+/// Base class for values that refer to storage locations.
+class IndirectionValue : public Value {
+public:
+ /// Constructs a value that refers to `Loc`.
+ ///
+ /// Requirements:
+ ///
+ /// `Loc` must not be null.
+ explicit IndirectionValue(Kind ValueKind, StorageLocation *Loc)
+ : Value(ValueKind), Loc(Loc) {
+ assert(Loc != nullptr);
+ }
+
+ static bool classof(const Value *Val) {
+ return Val->getKind() == Kind::Reference || Val->getKind() == Kind::Pointer;
+ }
+
+ StorageLocation *getLocation() const { return Loc; }
+
+private:
+ StorageLocation *Loc;
+};
+
+/// Class that models a dereferenced pointer. For example, a reference in C++ or
+/// an lvalue in C.
+class ReferenceValue final : public IndirectionValue {
+public:
+ explicit ReferenceValue(StorageLocation *Loc)
+ : IndirectionValue(Kind::Reference, Loc) {}
+
+ static bool classof(const Value *Val) {
+ return Val->getKind() == Kind::Reference;
+ }
+};
+
+/// Class that models a symbolic pointer. Specifically, any value of type `T*`.
+class PointerValue final : public IndirectionValue {
+public:
+ explicit PointerValue(StorageLocation *Loc)
+ : IndirectionValue(Kind::Pointer, Loc) {}
+
+ static bool classof(const Value *Val) {
+ return Val->getKind() == Kind::Pointer;
+ }
+};
+
+/// Class that models a value of `struct` or `class` type.
+class StructValue final : public Value {
+public:
+ StructValue() : StructValue(llvm::DenseMap<const ValueDecl *, Value *>()) {}
+
+ explicit StructValue(llvm::DenseMap<const ValueDecl *, Value *> Children)
+ : Value(Kind::Struct), Children(std::move(Children)) {}
+
+ static bool classof(const Value *Val) {
+ return Val->getKind() == Kind::Struct;
+ }
+
+ /// Returns the child value for `D`.
+ ///
+ /// Requirements:
+ ///
+ /// `D` must not be null.
+ Value *getChild(const ValueDecl *D) const {
+ assert(D != nullptr);
+ auto It = Children.find(D);
+ // FIXME: A missing child member means that the value was not created
+ // correctly. Change the following to assert(it != children_.end()) once all
+ // cases are modeled correctly.
+ if (It == Children.end())
+ return nullptr;
+ return It->second;
+ }
+
+private:
+ const llvm::DenseMap<const ValueDecl *, Value *> Children;
+};
+
+} // namespace dataflow
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H
Index: clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
===================================================================
--- clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
+++ clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h
@@ -14,6 +14,7 @@
#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H
#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H
+#include <utility>
#include <vector>
#include "clang/AST/ASTContext.h"
@@ -75,6 +76,9 @@
/// Model of the state of the program (store and heap).
Environment Env;
+
+ TypeErasedDataflowAnalysisState(TypeErasedLattice Lattice, Environment Env)
+ : Lattice(std::move(Lattice)), Env(std::move(Env)) {}
};
/// Transfers the state of a basic block by evaluating each of its statements in
Index: clang/include/clang/Analysis/FlowSensitive/Transfer.h
===================================================================
--- /dev/null
+++ clang/include/clang/Analysis/FlowSensitive/Transfer.h
@@ -0,0 +1,29 @@
+//===-- Transfer.h ----------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a transfer function that evaluates a program statement and
+// updates an environment accordingly.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TRANSFER_H
+#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TRANSFER_H
+
+#include "clang/AST/Stmt.h"
+#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+
+namespace clang {
+namespace dataflow {
+
+/// Evaluates `S` and updates `Env` accordingly.
+void transfer(const Stmt *S, Environment &Env);
+
+} // namespace dataflow
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TRANSFER_H
Index: clang/include/clang/Analysis/FlowSensitive/StorageLocation.h
===================================================================
--- /dev/null
+++ clang/include/clang/Analysis/FlowSensitive/StorageLocation.h
@@ -0,0 +1,98 @@
+//===-- StorageLocation.h ---------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines classes that represent elements of the local variable store
+// and of the heap during dataflow analysis.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H
+#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H
+
+#include "clang/AST/Decl.h"
+#include "clang/AST/Type.h"
+#include "llvm/ADT/DenseMap.h"
+
+namespace clang {
+namespace dataflow {
+
+/// Base class for elements of the local variable store and of the heap.
+///
+/// Each storage location holds a value. The mapping from storage locations to
+/// values is stored in the environment.
+class StorageLocation {
+public:
+ enum class Kind { Scalar, Aggregate };
+
+ StorageLocation(Kind LocKind, QualType Type) : LocKind(LocKind), Type(Type) {}
+
+ virtual ~StorageLocation() = default;
+
+ Kind getKind() const { return LocKind; }
+
+ QualType getType() const { return Type; }
+
+private:
+ Kind LocKind;
+ QualType Type;
+};
+
+/// A storage location that is not subdivided further for the purposes of
+/// abstract interpretation. For example: `int`, `int*`, `int&`.
+class ScalarStorageLocation final : public StorageLocation {
+public:
+ explicit ScalarStorageLocation(QualType Type)
+ : StorageLocation(Kind::Scalar, Type) {}
+
+ static bool classof(const StorageLocation *Loc) {
+ return Loc->getKind() == Kind::Scalar;
+ }
+};
+
+/// A storage location which is subdivided into smaller storage locations that
+/// can be traced independently by abstract interpretation. For example: a
+/// struct with public members.
+class AggregateStorageLocation final : public StorageLocation {
+public:
+ explicit AggregateStorageLocation(QualType Type)
+ : AggregateStorageLocation(
+ Type, llvm::DenseMap<const ValueDecl *, StorageLocation *>()) {}
+
+ AggregateStorageLocation(
+ QualType Type,
+ llvm::DenseMap<const ValueDecl *, StorageLocation *> Children)
+ : StorageLocation(Kind::Aggregate, Type), Children(std::move(Children)) {}
+
+ static bool classof(const StorageLocation *Loc) {
+ return Loc->getKind() == Kind::Aggregate;
+ }
+
+ /// Returns the child storage location for `D`.
+ ///
+ /// Requirements:
+ ///
+ /// `D` must not be null.
+ StorageLocation *getChild(const ValueDecl *D) const {
+ assert(D != nullptr);
+ auto It = Children.find(D);
+ // FIXME: A missing child member means that the sorage location was not
+ // created correctly. Change the following to assert(it != children_.end())
+ // once all cases are modeled correctly.
+ if (It == Children.end())
+ return nullptr;
+ return It->second;
+ }
+
+private:
+ llvm::DenseMap<const ValueDecl *, StorageLocation *> Children;
+};
+
+} // namespace dataflow
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H
Index: clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
===================================================================
--- clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
+++ clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
@@ -15,7 +15,15 @@
#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H
#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H
+#include "clang/AST/Decl.h"
+#include "clang/AST/Type.h"
+#include "clang/AST/TypeOrdering.h"
+#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
+#include "clang/Analysis/FlowSensitive/StorageLocation.h"
+#include "clang/Analysis/FlowSensitive/Value.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
namespace clang {
namespace dataflow {
@@ -23,11 +31,87 @@
/// Holds the state of the program (store and heap) at a given program point.
class Environment {
public:
- bool operator==(const Environment &) const { return true; }
+ Environment(DataflowAnalysisContext &DACtx) : DACtx(&DACtx) {}
- LatticeJoinEffect join(const Environment &) {
- return LatticeJoinEffect::Unchanged;
- }
+ bool operator==(const Environment &) const;
+
+ LatticeJoinEffect join(const Environment &);
+
+ /// Creates a storage location appropriate for `Type`. Does not assign a value
+ /// to the returned storage location in the environment. Never returns null.
+ StorageLocation *createStorageLocation(QualType Type);
+
+ /// Creates a storage location for `Decl`. Does not assign the returned
+ /// storage location to `Decl` in the environment. Does not assign a value
+ /// to the returned storage location in the environment. Never returns null.
+ ///
+ /// Requirements:
+ ///
+ /// `D` must not be null.
+ StorageLocation *createStorageLocation(const VarDecl *D);
+
+ /// Assigns `Loc` to `D` in the environment.
+ ///
+ /// Requirements:
+ ///
+ /// `D` must not be null.
+ ///
+ /// `Loc` must not be null.
+ ///
+ /// `D` must not be assigned a storage location in the environment.
+ void setStorageLocation(const ValueDecl *D, StorageLocation *Loc);
+
+ /// Returns the storage location assigned to `D` in the environment or null if
+ /// `D` isn't assigned a storage location in the environment.
+ ///
+ /// Requirements:
+ ///
+ /// `D` must not be null.
+ StorageLocation *getStorageLocation(const ValueDecl *D) const;
+
+ /// Creates a value appropriate for `Type` and assigns it to the given storage
+ /// location. If `Type` is a pointer or reference type, creates all the
+ /// necessary storage locations and values for indirections until it finds a
+ /// non-pointer/non-reference type.
+ ///
+ /// Requirements:
+ ///
+ /// `Loc` must not be null.
+ Value *initValueInStorageLocation(const StorageLocation *Loc, QualType Type);
+
+ /// Assigns `Val` to `Loc` in the environment.
+ ///
+ /// Requirements:
+ ///
+ /// `Loc` must not be null.
+ ///
+ /// `Val` must not be null.
+ void setValue(const StorageLocation *Loc, Value *Val);
+
+ /// Returns the value assigned to `Loc` in the environment or null if `Loc`
+ /// isn't assigned a value in the environment.
+ ///
+ /// Requirements:
+ ///
+ /// `Loc` must not be null.
+ Value *getValue(const StorageLocation *Loc) const;
+
+private:
+ /// Recursively initializes storage locations and values unless it sees a
+ /// self-referential pointer or reference type. `Visited` is used to track
+ /// which types appeared in the reference/pointer chain in order to avoid
+ /// creating a cyclic dependency with self-referential pointers/references.
+ ///
+ /// Requirements:
+ ///
+ /// `Loc` must not be null.
+ Value *initValueInStorageLocationUnlessSelfReferential(
+ const StorageLocation *Loc, QualType Type,
+ llvm::DenseSet<QualType> &Visited);
+
+ DataflowAnalysisContext *DACtx;
+ llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
+ llvm::DenseMap<const StorageLocation *, Value *> LocToVal;
};
} // namespace dataflow
Index: clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h
===================================================================
--- /dev/null
+++ clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h
@@ -0,0 +1,94 @@
+//===-- DataflowAnalysisContext.h -------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a DataflowAnalysisContext class that owns objects that
+// encompass the state of a program and stores context that is used during
+// dataflow analysis.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H
+#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H
+
+#include "clang/AST/Decl.h"
+#include "clang/Analysis/FlowSensitive/StorageLocation.h"
+#include "clang/Analysis/FlowSensitive/Value.h"
+#include "llvm/ADT/DenseMap.h"
+#include <cassert>
+#include <memory>
+#include <utility>
+#include <vector>
+
+namespace clang {
+namespace dataflow {
+
+/// Owns objects that encompass the state of a program and stores additional
+/// context that is used during dataflow analysis.
+class DataflowAnalysisContext {
+public:
+ /// Takes ownership of `Loc` and returns a pointer to it.
+ ///
+ /// Requirements:
+ ///
+ /// `Loc` must not be null.
+ StorageLocation *takeOwnership(std::unique_ptr<StorageLocation> Loc) {
+ assert(Loc != nullptr);
+ Locs.push_back(std::move(Loc));
+ return Locs.back().get();
+ }
+
+ /// Takes ownership of `Val` and returns a pointer to it.
+ ///
+ /// Requirements:
+ ///
+ /// `Val` must not be null.
+ Value *takeOwnership(std::unique_ptr<Value> Val) {
+ assert(Val != nullptr);
+ Values.push_back(std::move(Val));
+ return Values.back().get();
+ }
+
+ /// Assigns `Loc` to `D`.
+ ///
+ /// Requirements:
+ ///
+ /// `D` must not be null.
+ ///
+ /// `Loc` must not be null.
+ ///
+ /// `D` must not be assigned a storage location.
+ void setStorageLocation(const VarDecl *D, StorageLocation *Loc) {
+ assert(D != nullptr);
+ assert(Loc != nullptr);
+ assert(VarDeclToLoc.find(D) == VarDeclToLoc.end());
+ VarDeclToLoc[D] = Loc;
+ }
+
+ /// Returns the storage location assigned to `D` or null if `D` has no
+ /// assigned storage location.
+ ///
+ /// Requirements:
+ ///
+ /// `D` must not be null.
+ StorageLocation *getStorageLocation(const VarDecl *D) const {
+ assert(D != nullptr);
+ auto It = VarDeclToLoc.find(D);
+ return It == VarDeclToLoc.end() ? nullptr : It->second;
+ }
+
+private:
+ // Storage for the state of a program.
+ std::vector<std::unique_ptr<StorageLocation>> Locs;
+ std::vector<std::unique_ptr<Value>> Values;
+ llvm::DenseMap<const VarDecl *, StorageLocation *> VarDeclToLoc;
+};
+
+} // namespace dataflow
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
