ymandel created this revision.
ymandel added reviewers: xazax.hun, gribozavr2, sgatev.
Herald added subscribers: rnkovacs, mgorny.
ymandel requested review of this revision.
Herald added a project: clang.
This patchs adds a `MapLattice` template for lifting a lattice to a keyed map. A
typical use is for modeling variables in a scope with a partcular lattice.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D116369
Files:
clang/include/clang/Analysis/FlowSensitive/MapLattice.h
clang/unittests/Analysis/FlowSensitive/CMakeLists.txt
clang/unittests/Analysis/FlowSensitive/MapLatticeTest.cpp
Index: clang/unittests/Analysis/FlowSensitive/MapLatticeTest.cpp
===================================================================
--- /dev/null
+++ clang/unittests/Analysis/FlowSensitive/MapLatticeTest.cpp
@@ -0,0 +1,224 @@
+#include "clang/Analysis/FlowSensitive/MapLattice.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
+#include "clang/Frontend/ASTUnit.h"
+#include "clang/Tooling/Tooling.h"
+#include "llvm/Support/Error.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include <ostream>
+
+namespace clang {
+namespace dataflow {
+namespace {
+
+using ::testing::Pair;
+using ::testing::UnorderedElementsAre;
+
+using namespace ast_matchers;
+
+MATCHER_P(Var, name,
+ (llvm::Twine(negation ? "isn't" : "is") + " a variable named `" +
+ name + "`")
+ .str()) {
+ return arg->getName() == name;
+}
+
+// A simple lattice for basic tests.
+class BooleanLattice {
+public:
+ BooleanLattice() : Value(false) {}
+ explicit BooleanLattice(bool B) : Value(B) {}
+
+ static BooleanLattice bottom() { return BooleanLattice(false); }
+
+ static BooleanLattice top() { return BooleanLattice(true); }
+
+ LatticeJoinEffect join(BooleanLattice Other) {
+ auto Prev = Value;
+ Value = Value || Other.Value;
+ return Prev == Value ? LatticeJoinEffect::Unchanged
+ : LatticeJoinEffect::Changed;
+ }
+
+ friend bool operator==(BooleanLattice LHS, BooleanLattice RHS) {
+ return LHS.Value == RHS.Value;
+ }
+
+ friend bool operator!=(BooleanLattice LHS, BooleanLattice RHS) {
+ return LHS.Value != RHS.Value;
+ }
+
+ friend std::ostream &operator<<(std::ostream &Os, const BooleanLattice &B) {
+ Os << B.Value;
+ return Os;
+ }
+
+ bool value() const { return Value; }
+
+private:
+ bool Value;
+};
+
+// Two `VarDecls` and the AST they are taken from.
+struct ValidVarDecls {
+ // The AST from which the var-decls are drawn. Needs to be kept in the struct
+ // so that `var1`, `var2` will be valid.
+ std::unique_ptr<ASTUnit> Unit;
+ const VarDecl *Var1;
+ const VarDecl *Var2;
+};
+
+// Generates two valid `VarDecl`s named "test_var_1" and "test_var_2".
+ValidVarDecls getVarDecls() {
+ std::string Code = R"cc(
+ void fun() {
+ int test_var_1;
+ int test_var_2;
+ }
+ )cc";
+
+ ValidVarDecls Result;
+ Result.Unit = tooling::buildASTFromCodeWithArgs(Code, {"-Wno-unused-value"});
+ assert(Result.Unit != nullptr && "AST construction failed");
+
+ ASTContext &Context = Result.Unit->getASTContext();
+ auto Matches = match(
+ functionDecl(hasBody(compoundStmt(
+ hasAnySubstatement(declStmt(
+ hasSingleDecl(varDecl(hasName("test_var_1")).bind("var1")))),
+ hasAnySubstatement(declStmt(
+ hasSingleDecl(varDecl(hasName("test_var_2")).bind("var2"))))))),
+ Context);
+ assert(Matches.size() == 1);
+
+ Result.Var1 = Matches[0].getNodeAs<clang::VarDecl>("var1");
+ Result.Var2 = Matches[0].getNodeAs<clang::VarDecl>("var2");
+ assert(Result.Var1 != nullptr);
+ assert(Result.Var2 != nullptr);
+
+ return Result;
+}
+
+TEST(VarMapLatticeTest, InsertWorks) {
+ auto Decls = getVarDecls();
+
+ VarMapLattice<BooleanLattice> Lattice;
+ Lattice.insert({Decls.Var1, BooleanLattice(false)});
+ Lattice.insert({Decls.Var2, BooleanLattice(false)});
+
+ EXPECT_THAT(Lattice, UnorderedElementsAre(
+ Pair(Var("test_var_1"), BooleanLattice(false)),
+ Pair(Var("test_var_2"), BooleanLattice(false))));
+}
+
+TEST(VarMapLatticeTest, ComparisonWorks) {
+ auto Decls = getVarDecls();
+
+ VarMapLattice<BooleanLattice> Lattice1;
+ Lattice1.insert({Decls.Var1, BooleanLattice(true)});
+ Lattice1.insert({Decls.Var2, BooleanLattice(false)});
+ VarMapLattice<BooleanLattice> Lattice2 = Lattice1;
+
+ EXPECT_EQ(Lattice1, Lattice2);
+ Lattice2[Decls.Var2] = BooleanLattice(true);
+ EXPECT_NE(Lattice1, Lattice2);
+}
+
+TEST(VarMapLatticeTest, JoinChange) {
+ auto Decls = getVarDecls();
+
+ VarMapLattice<BooleanLattice> Lattice1;
+ Lattice1.insert({Decls.Var1, BooleanLattice(false)});
+ Lattice1.insert({Decls.Var2, BooleanLattice(false)});
+
+ VarMapLattice<BooleanLattice> Lattice2;
+ Lattice2.insert({Decls.Var1, BooleanLattice(true)});
+ Lattice2.insert({Decls.Var2, BooleanLattice(true)});
+
+ ASSERT_THAT(Lattice1, UnorderedElementsAre(
+ Pair(Var("test_var_1"), BooleanLattice(false)),
+ Pair(Var("test_var_2"), BooleanLattice(false))));
+
+ ASSERT_EQ(Lattice1.join(Lattice2), LatticeJoinEffect::Changed);
+ EXPECT_THAT(Lattice1, UnorderedElementsAre(
+ Pair(Var("test_var_1"), BooleanLattice(true)),
+ Pair(Var("test_var_2"), BooleanLattice(true))));
+}
+
+TEST(VarMapLatticeTest, JoinEqNoChange) {
+ auto Decls = getVarDecls();
+
+ VarMapLattice<BooleanLattice> Lattice;
+ Lattice.insert({Decls.Var1, BooleanLattice(false)});
+ Lattice.insert({Decls.Var2, BooleanLattice(false)});
+
+ ASSERT_EQ(Lattice.join(Lattice), LatticeJoinEffect::Unchanged);
+ EXPECT_THAT(Lattice, UnorderedElementsAre(
+ Pair(Var("test_var_1"), BooleanLattice(false)),
+ Pair(Var("test_var_2"), BooleanLattice(false))));
+}
+
+TEST(VarMapLatticeTest, JoinLtNoChange) {
+ auto Decls = getVarDecls();
+
+ VarMapLattice<BooleanLattice> Lattice1;
+ Lattice1.insert({Decls.Var1, BooleanLattice(false)});
+ Lattice1.insert({Decls.Var2, BooleanLattice(false)});
+
+ VarMapLattice<BooleanLattice> Lattice2;
+ Lattice2.insert({Decls.Var1, BooleanLattice(true)});
+ Lattice2.insert({Decls.Var2, BooleanLattice(true)});
+
+ ASSERT_THAT(Lattice1, UnorderedElementsAre(
+ Pair(Var("test_var_1"), BooleanLattice(false)),
+ Pair(Var("test_var_2"), BooleanLattice(false))));
+
+ ASSERT_THAT(Lattice2, UnorderedElementsAre(
+ Pair(Var("test_var_1"), BooleanLattice(true)),
+ Pair(Var("test_var_2"), BooleanLattice(true))));
+
+ ASSERT_EQ(Lattice2.join(Lattice1), LatticeJoinEffect::Unchanged);
+ EXPECT_THAT(Lattice2, UnorderedElementsAre(
+ Pair(Var("test_var_1"), BooleanLattice(true)),
+ Pair(Var("test_var_2"), BooleanLattice(true))));
+}
+
+TEST(VarMapLatticeTest, JoinDifferentDomainsProducesUnion) {
+ auto Decls = getVarDecls();
+
+ VarMapLattice<BooleanLattice> Lattice1;
+ Lattice1.insert({Decls.Var1, BooleanLattice(true)});
+ VarMapLattice<BooleanLattice> Lattice2;
+ Lattice2.insert({Decls.Var2, BooleanLattice(true)});
+
+ ASSERT_EQ(Lattice1.join(Lattice2), LatticeJoinEffect::Changed);
+ EXPECT_THAT(Lattice1, UnorderedElementsAre(
+ Pair(Var("test_var_1"), BooleanLattice(true)),
+ Pair(Var("test_var_2"), BooleanLattice(true))));
+}
+
+TEST(VarMapLatticeTest, LookupWorks) {
+ auto Decls = getVarDecls();
+
+ VarMapLattice<BooleanLattice> Lattice;
+ Lattice.insert({Decls.Var1, BooleanLattice(true)});
+ Lattice.insert({Decls.Var2, BooleanLattice(false)});
+
+ EXPECT_EQ(Lattice[Decls.Var1], BooleanLattice(true));
+ EXPECT_EQ(Lattice[Decls.Var2], BooleanLattice(false));
+}
+
+TEST(VarMapLatticeTest, ContainsWorks) {
+ auto Decls = getVarDecls();
+
+ VarMapLattice<BooleanLattice> Lattice;
+ Lattice.insert({Decls.Var1, BooleanLattice(true)});
+ EXPECT_TRUE(Lattice.contains(Decls.Var1));
+ EXPECT_FALSE(Lattice.contains(Decls.Var2));
+}
+
+} // namespace
+} // namespace dataflow
+} // namespace clang
Index: clang/unittests/Analysis/FlowSensitive/CMakeLists.txt
===================================================================
--- clang/unittests/Analysis/FlowSensitive/CMakeLists.txt
+++ clang/unittests/Analysis/FlowSensitive/CMakeLists.txt
@@ -4,6 +4,7 @@
)
add_clang_unittest(ClangAnalysisFlowSensitiveTests
+ MapLatticeTest.cpp
SingleVarConstantPropagationTest.cpp
TestingSupport.cpp
TestingSupportTest.cpp
Index: clang/include/clang/Analysis/FlowSensitive/MapLattice.h
===================================================================
--- /dev/null
+++ clang/include/clang/Analysis/FlowSensitive/MapLattice.h
@@ -0,0 +1,110 @@
+//===- DataflowAnalysis.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 parameterized lattice that maps keys to individual
+// lattice elements (of the parameter lattice type). A typical usage is lifting
+// a particular lattice to all variables in a lexical scope.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H_
+#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H_
+
+#include <ostream>
+#include <string>
+#include <utility>
+
+#include "DataflowAnalysis.h"
+#include "clang/AST/Decl.h"
+#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/StringRef.h"
+
+namespace clang {
+namespace dataflow {
+
+/// A lattice that maps keys to individual lattice elements. The default
+/// constructor of `ElementLattice` should produce the bottom element.
+template <typename Key, typename ElementLattice> class MapLattice {
+ using Container = llvm::DenseMap<Key, ElementLattice>;
+
+public:
+ using key_type = Key;
+ using mapped_type = ElementLattice;
+ using value_type = typename Container::value_type;
+ using iterator = typename Container::iterator;
+ using const_iterator = typename Container::const_iterator;
+
+ MapLattice() = default;
+
+ explicit MapLattice(Container C) { C = std::move(C); }
+
+ static MapLattice bottom() { return MapLattice(); }
+
+ void insert(const std::pair<const key_type, mapped_type> &P) {
+ (void)C.insert(P);
+ }
+
+ void insert(std::pair<const key_type, mapped_type> &&P) {
+ (void)C.insert(std::move(P));
+ }
+
+ unsigned size() const { return C.size(); }
+ bool empty() const { return C.empty(); }
+
+ iterator begin() { return C.begin(); }
+ iterator end() { return C.end(); }
+ const_iterator begin() const { return C.begin(); }
+ const_iterator end() const { return C.end(); }
+
+ mapped_type &operator[](const key_type &K) { return C[K]; }
+
+ friend bool operator==(const MapLattice &LHS, const MapLattice &RHS) {
+ return LHS.C == RHS.C;
+ }
+
+ friend bool operator!=(const MapLattice &LHS, const MapLattice &RHS) {
+ return !(LHS == RHS);
+ }
+
+ bool contains(const key_type &K) const { return C.find(K) != C.end(); }
+
+ LatticeJoinEffect join(const MapLattice &Other) {
+ LatticeJoinEffect Effect = LatticeJoinEffect::Unchanged;
+ for (const auto &E : Other.C)
+ if (C[E.first].join(E.second) == LatticeJoinEffect::Changed)
+ Effect = LatticeJoinEffect::Changed;
+ return Effect;
+ }
+
+private:
+ Container C;
+};
+
+/// Convenience alias that captures the common use of map lattices to model
+/// in-scope variables.
+template <typename ElementLattice>
+using VarMapLattice = MapLattice<const clang::VarDecl *, ElementLattice>;
+
+template <typename ElementLattice>
+std::ostream &operator<<(std::ostream &Os,
+ const VarMapLattice<ElementLattice> &M) {
+ std::string Separator = "";
+ Os << "{";
+ for (const auto &E : M) {
+ Os << std::exchange(Separator, ", ") << E.first->getName().str() << " => "
+ << E.second;
+ }
+ Os << "}";
+ return Os;
+}
+
+} // namespace dataflow
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H_
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
