From 2c3860b8f6e9ba3e0878ecadfdef409da0f471b7 Mon Sep 17 00:00:00 2001
From: Thomas Lively <tlively@google.com>
Date: Thu, 2 Nov 2023 19:32:32 +0100
Subject: [analysis] Allow joining a single vector element efficiently (#6071)

Previously, modifying a single vector element of a `Shared<Vector>` element
required materializing a full vector to do the join. When there is just a single
element to update, materializing all the other elements with bottom value is
useless work. Add a `Vector<L>::SingletonElement` utility that represents but
does not materialize a vector with a single non-bottom element and allow it to
be passed to `Vector<L>::join`. Also update `Shared` and `Inverted` so that
`SingletonElement` joins still work on vectors wrapped in those other lattices.
---
 test/gtest/lattices.cpp | 43 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 43 insertions(+)

(limited to 'test')

diff --git a/test/gtest/lattices.cpp b/test/gtest/lattices.cpp
index ed4f48e38..905f03420 100644
--- a/test/gtest/lattices.cpp
+++ b/test/gtest/lattices.cpp
@@ -478,6 +478,30 @@ TEST(VectorLattice, Meet) {
     vector, {false, false}, {false, true}, {true, false}, {true, true});
 }
 
+TEST(VectorLattice, JoinSingleton) {
+  using Vec = analysis::Vector<analysis::Bool>;
+  Vec vector{analysis::Bool{}, 2};
+  auto elem = vector.getBottom();
+
+  EXPECT_FALSE(vector.join(elem, Vec::SingletonElement(0, false)));
+  EXPECT_EQ(elem, (std::vector{false, false}));
+
+  EXPECT_TRUE(vector.join(elem, Vec::SingletonElement(1, true)));
+  EXPECT_EQ(elem, (std::vector{false, true}));
+}
+
+TEST(VectorLattice, MeetSingleton) {
+  using Vec = analysis::Vector<analysis::Bool>;
+  Vec vector{analysis::Bool{}, 2};
+  auto elem = vector.getTop();
+
+  EXPECT_FALSE(vector.meet(elem, Vec::SingletonElement(1, true)));
+  EXPECT_EQ(elem, (std::vector{true, true}));
+
+  EXPECT_TRUE(vector.meet(elem, Vec::SingletonElement(0, false)));
+  EXPECT_EQ(elem, (std::vector{false, true}));
+}
+
 TEST(TupleLattice, GetBottom) {
   analysis::Tuple<analysis::Bool, analysis::UInt32> tuple{analysis::Bool{},
                                                           analysis::UInt32{}};
@@ -656,6 +680,25 @@ TEST(SharedLattice, Join) {
   }
 }
 
+TEST(SharedLattice, JoinVecSingleton) {
+  using Vec = analysis::Vector<analysis::Bool>;
+  analysis::Shared<Vec> shared{analysis::Vector{analysis::Bool{}, 2}};
+
+  auto elem = shared.getBottom();
+  EXPECT_TRUE(shared.join(elem, Vec::SingletonElement(1, true)));
+  EXPECT_EQ(*elem, (std::vector{false, true}));
+}
+
+TEST(SharedLattice, JoinInvertedVecSingleton) {
+  using Vec = analysis::Vector<analysis::Bool>;
+  analysis::Shared<analysis::Inverted<Vec>> shared{
+    analysis::Inverted{analysis::Vector{analysis::Bool{}, 2}}};
+
+  auto elem = shared.getBottom();
+  EXPECT_TRUE(shared.join(elem, Vec::SingletonElement(1, false)));
+  EXPECT_EQ(*elem, (std::vector{true, false}));
+}
+
 TEST(StackLattice, GetBottom) {
   analysis::Stack stack{analysis::Flat<uint32_t>{}};
   EXPECT_EQ(stack.getBottom().size(), 0u);
-- 
cgit v1.2.3