[clang][dataflow] Add parameterized map lattice.

[ymandel]

Summary

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.

[sgatev]

It seems unnecessary to deal with AST elements in the tests for MapLattice. I think testing it with integer or string keys would be simpler. Given that VarMapLattice is just an alias, I don't think it's necessary to add dedicated tests for it. What do you think?

clang/include/clang/Analysis/FlowSensitive/MapLattice.h

2

The comment needs to be updated.

16

Remove the last underscore for consistency.

34

Please document the relation, the join operation, and the bottom element for this lattice.

51

Is (void) necessary? Is it a convention?

clang/unittests/Analysis/FlowSensitive/MapLatticeTest.cpp

13–14

using namespace clang;
using namespace dataflow;

23

#include "llvm/ADT/Twine.h"

[ymandel]

addressed comments

[ymandel]

update comments

[ymandel]

In D116369#3212532, @sgatev wrote:

It seems unnecessary to deal with AST elements in the tests for MapLattice. I think testing it with integer or string keys would be simpler. Given that VarMapLattice is just an alias, I don't think it's necessary to add dedicated tests for it. What do you think?

Yes, excellent point. I've stripped all of that out and think its much cleaner this way. Thanks!

clang/include/clang/Analysis/FlowSensitive/MapLattice.h

34

I wasn't sure which relation you had in mind, so documented the equality operation.

51

not necessary -- I'll sometimes do it when I'm ignoring a result. But, no need -- i dropped it.

[xazax.hun]

clang/include/clang/Analysis/FlowSensitive/MapLattice.h

93

It looks like apart from the join operation the rest of the methods are simply forwarding to DenseMap. I was wondering if it would make more sense to make the framework support join as a free function (possibly using some custom type traits?) to avoid forcing the user to write wrappers like this.

[ymandel]

clang/include/clang/Analysis/FlowSensitive/MapLattice.h

93

Good point, but I think that these concerns are separable -- that is, how much forwarding we do and whether we should enable join an arbitrary types.

For the first issue, an alternative design here would be to simply expose the container as a public field and drop all the methods except for join. I intentionally left some abstraction in place, though, because I think that DenseMap is not the right container, its just "good enough" to get started. I think ultimately we'll want functional data structures, because the current setup forces an absurd amount of copying.

For the second issue, I'm open to the idea -- it would be like Haskell's type classes in some sense, but I prefer the design where the lattice's operations are grouped together as a unit. I think that we could fit it into the current design with some form of SFINAE-based discrimination on the lattice type parameter of DataflowAnalysis.

Given that, what do you think of just renaming this to DenseMapLattice and exposing the container field publicly? When we're ready with a better map lattice, we can add that alongside this one with a different name.

[xazax.hun]

clang/include/clang/Analysis/FlowSensitive/MapLattice.h

93

Alternatively, I was wondering if deriving from llvm::DenseMap<Key, ElementLattice> would reduce the amount of boilerplate this needs.

I'm a big fan of the typeclass approach, so I'd be really happy if the framework supported something like that but it is definitely out of scope for the PR.

I think ultimately we'll want functional data structures, because the current setup forces an absurd amount of copying.

+1.

Given that, what do you think of just renaming this to DenseMapLattice and exposing the container field publicly? When we're ready with a better map lattice, we can add that alongside this one with a different name.

Since we do not consider this to be the final/definitive solution, I'm fine with either approach or leaving this as is.

[ymandel]

clang/include/clang/Analysis/FlowSensitive/MapLattice.h

93

Thanks! I'll stick with what I have for now, but ImmutableMap definitely seems like a strict improvement, so I'll look into that next.

Regarding the representation -- I think I'd prefer subclassing over typeclasses, but this sounds like a good discussion to have. It would probably benefit us all to have a issue component to track ideas like this. I'll look into the status of LLVM's move to github for issue tracking to see if there's a way to set this up.

clang/include/clang/Analysis/FlowSensitive/MapLattice.h

+//===------------------------ MapLattice.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. When instantiated
+/// with an `ElementLattice` that is a bounded semi-lattice, `MapLattice` is
+/// itself a bounded semi-lattice, so long as the user limits themselves to a
+/// finite number of keys. In that case, `top` is (implicitly), the map
+/// containing all valid keys mapped to `top` of `ElementLattice`.
+///
+/// Requirements on `ElementLattice`:
+/// * Provides standard declarations of a bounded semi-lattice.
+template <typename Key, typename ElementLattice> class MapLattice {
+  using Container = llvm::DenseMap<Key, ElementLattice>;
+  Container C;
+
+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); }
+
+  // The `bottom` element is the empty map.
+  static MapLattice bottom() { return MapLattice(); }
+
+  void insert(const std::pair<const key_type, mapped_type> &P) { C.insert(P); }
+
+  void insert(std::pair<const key_type, mapped_type> &&P) {
+    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(); }
+
+  // Equality is direct equality of underlying map entries. One implication of
+  // this definition is that a map with (only) keys that map to bottom is not
+  // equal to the empty map.
+  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(); }
+
+  iterator find(const key_type &K) { return C.find(K); }
+  const_iterator find(const key_type &K) const { return C.find(K); }
+
+  mapped_type &operator[](const key_type &K) { return C[K]; }
+
+  /// If an entry exists in one map but not the other, the missing entry is
+  /// treated as implicitly mapping to `bottom`. So, the joined map contains the
+  /// entry as it was in the source map.
+  LatticeJoinEffect join(const MapLattice &Other) {
+    LatticeJoinEffect Effect = LatticeJoinEffect::Unchanged;
+    for (const auto &O : Other.C) {
+      auto It = C.find(O.first);
+      if (It == C.end()) {
+        C.insert(O);
+        Effect = LatticeJoinEffect::Changed;
+      } else if (It->second.join(O.second) == LatticeJoinEffect::Changed)
+        Effect = LatticeJoinEffect::Changed;
+    }
+    return Effect;
+  }
+};
+
+/// 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 Key, typename ElementLattice>
+std::ostream &
+operator<<(std::ostream &Os,
+           const clang::dataflow::MapLattice<Key, ElementLattice> &M) {
+  std::string Separator = "";
+  Os << "{";
+  for (const auto &E : M) {
+    Os << std::exchange(Separator, ", ") << E.first << " => " << E.second;
+  }
+  Os << "}";
+  return Os;
+}
+
+template <typename ElementLattice>
+std::ostream &
+operator<<(std::ostream &Os,
+           const clang::dataflow::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

clang/unittests/Analysis/FlowSensitive/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   FrontendOpenMP
   Support
   )
 
 add_clang_unittest(ClangAnalysisFlowSensitiveTests
+  MapLatticeTest.cpp
   SingleVarConstantPropagationTest.cpp
   TestingSupport.cpp
   TestingSupportTest.cpp
   TransferTest.cpp
   TypeErasedDataflowAnalysisTest.cpp
   )
 
 clang_target_link_libraries(ClangAnalysisFlowSensitiveTests

clang/unittests/Analysis/FlowSensitive/MapLatticeTest.cpp

+#include "clang/Analysis/FlowSensitive/MapLattice.h"
+#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
+#include "llvm/Support/Error.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include <ostream>
+
+using namespace clang;
+using namespace dataflow;
+
+namespace {
+// 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;
+};
+} // namespace
+
+static constexpr int Key1 = 0;
+static constexpr int Key2 = 1;
+
+namespace {
+using ::testing::Pair;
+using ::testing::UnorderedElementsAre;
+
+TEST(MapLatticeTest, InsertWorks) {
+  MapLattice<int, BooleanLattice> Lattice;
+  Lattice.insert({Key1, BooleanLattice(false)});
+  Lattice.insert({Key2, BooleanLattice(false)});
+
+  EXPECT_THAT(Lattice, UnorderedElementsAre(Pair(Key1, BooleanLattice(false)),
+                                            Pair(Key2, BooleanLattice(false))));
+}
+
+TEST(MapLatticeTest, ComparisonWorks) {
+  MapLattice<int, BooleanLattice> Lattice1;
+  Lattice1.insert({Key1, BooleanLattice(true)});
+  Lattice1.insert({Key2, BooleanLattice(false)});
+  MapLattice<int, BooleanLattice> Lattice2 = Lattice1;
+  EXPECT_EQ(Lattice1, Lattice2);
+
+  Lattice2.find(Key2)->second = BooleanLattice(true);
+  EXPECT_NE(Lattice1, Lattice2);
+}
+
+TEST(MapLatticeTest, JoinChange) {
+  MapLattice<int, BooleanLattice> Lattice1;
+  Lattice1.insert({Key1, BooleanLattice(false)});
+  Lattice1.insert({Key2, BooleanLattice(false)});
+
+  MapLattice<int, BooleanLattice> Lattice2;
+  Lattice2.insert({Key1, BooleanLattice(true)});
+  Lattice2.insert({Key2, BooleanLattice(true)});
+
+  ASSERT_THAT(Lattice1,
+              UnorderedElementsAre(Pair(Key1, BooleanLattice(false)),
+                                   Pair(Key2, BooleanLattice(false))));
+
+  ASSERT_EQ(Lattice1.join(Lattice2), LatticeJoinEffect::Changed);
+  EXPECT_THAT(Lattice1, UnorderedElementsAre(Pair(Key1, BooleanLattice(true)),
+                                             Pair(Key2, BooleanLattice(true))));
+}
+
+TEST(MapLatticeTest, JoinEqNoChange) {
+  MapLattice<int, BooleanLattice> Lattice;
+  Lattice.insert({Key1, BooleanLattice(false)});
+  Lattice.insert({Key2, BooleanLattice(false)});
+
+  ASSERT_EQ(Lattice.join(Lattice), LatticeJoinEffect::Unchanged);
+  EXPECT_THAT(Lattice, UnorderedElementsAre(Pair(Key1, BooleanLattice(false)),
+                                            Pair(Key2, BooleanLattice(false))));
+}
+
+TEST(MapLatticeTest, JoinLtNoChange) {
+  MapLattice<int, BooleanLattice> Lattice1;
+  Lattice1.insert({Key1, BooleanLattice(false)});
+  Lattice1.insert({Key2, BooleanLattice(false)});
+
+  MapLattice<int, BooleanLattice> Lattice2;
+  Lattice2.insert({Key1, BooleanLattice(true)});
+  Lattice2.insert({Key2, BooleanLattice(true)});
+
+  ASSERT_THAT(Lattice1,
+              UnorderedElementsAre(Pair(Key1, BooleanLattice(false)),
+                                   Pair(Key2, BooleanLattice(false))));
+
+  ASSERT_THAT(Lattice2, UnorderedElementsAre(Pair(Key1, BooleanLattice(true)),
+                                             Pair(Key2, BooleanLattice(true))));
+
+  ASSERT_EQ(Lattice2.join(Lattice1), LatticeJoinEffect::Unchanged);
+  EXPECT_THAT(Lattice2, UnorderedElementsAre(Pair(Key1, BooleanLattice(true)),
+                                             Pair(Key2, BooleanLattice(true))));
+}
+
+TEST(MapLatticeTest, JoinDifferentDomainsProducesUnion) {
+  MapLattice<int, BooleanLattice> Lattice1;
+  Lattice1.insert({Key1, BooleanLattice(true)});
+  MapLattice<int, BooleanLattice> Lattice2;
+  Lattice2.insert({Key2, BooleanLattice(true)});
+
+  ASSERT_EQ(Lattice1.join(Lattice2), LatticeJoinEffect::Changed);
+  EXPECT_THAT(Lattice1, UnorderedElementsAre(Pair(Key1, BooleanLattice(true)),
+                                             Pair(Key2, BooleanLattice(true))));
+}
+
+TEST(MapLatticeTest, FindWorks) {
+  MapLattice<int, BooleanLattice> Lattice;
+  Lattice.insert({Key1, BooleanLattice(true)});
+  Lattice.insert({Key2, BooleanLattice(false)});
+
+  auto It = Lattice.find(Key1);
+  ASSERT_NE(It, Lattice.end());
+  EXPECT_EQ(It->second, BooleanLattice(true));
+
+  It = Lattice.find(Key2);
+  ASSERT_NE(It, Lattice.end());
+  EXPECT_EQ(It->second, BooleanLattice(false));
+}
+
+TEST(MapLatticeTest, ContainsWorks) {
+  MapLattice<int, BooleanLattice> Lattice;
+  Lattice.insert({Key1, BooleanLattice(true)});
+  EXPECT_TRUE(Lattice.contains(Key1));
+  EXPECT_FALSE(Lattice.contains(Key2));
+}
+} // namespace