[analysis] Add a "Shared" lattice to represent shared state (#6067)

The analysis framework stores a separate lattice element for each basic block
being analyzed to represent the program state at the beginning of the block.
However, in many analyses a significant portion of program state is not
flow-sensitive, so does not benefit from having a separate copy per block. For
example, an analysis might track constraints on the types of locals that do not
vary across blocks, so it really only needs a single copy of the constrains for
each local. It would be correct to simply duplicate the state across blocks
anyway, but it would not be efficient.

To make it possible to share a single copy of a lattice element across basic
blocks, introduce a `Shared<L>` lattice. Mathematically, this lattice represents
a single ascending chain in the underlying lattice and its elements are ordered
according to sequence numbers corresponding to positions in that chain.
Concretely, though, the `Shared<L>` lattice only ever materializes a single,
monotonically increasing element of `L` and all of its elements provide access
to that shared underlying element.

`Shared<L>` will let us get the benefits of having mutable shared state in the
concrete implementation of analyses without losing the benefits of keeping those
analyses expressible purely in terms of the monotone framework.

1 files changed, 108 insertions, 0 deletions

diff --git a/test/gtest/lattices.cpp b/test/gtest/lattices.cpp
index 81706e58e..49288fe85 100644
--- a/test/gtest/lattices.cpp
+++ b/test/gtest/lattices.cpp
@@ -20,6 +20,7 @@
 #include "analysis/lattices/int.h"
 #include "analysis/lattices/inverted.h"
 #include "analysis/lattices/lift.h"
+#include "analysis/lattices/shared.h"
 #include "analysis/lattices/tuple.h"
 #include "analysis/lattices/valtype.h"
 #include "analysis/lattices/vector.h"
@@ -546,3 +547,110 @@ TEST(ValTypeLattice, Meet) {
                   Type(HeapType::array, Nullable),
                   Type(HeapType::eq, Nullable));
 }
+
+TEST(SharedLattice, GetBottom) {
+  analysis::Shared<analysis::UInt32> shared{analysis::UInt32{}};
+  EXPECT_EQ(*shared.getBottom(), 0u);
+}
+
+TEST(SharedLattice, Compare) {
+  analysis::Shared<analysis::UInt32> shared{analysis::UInt32{}};
+
+  auto zero = shared.getBottom();
+
+  auto one = shared.getBottom();
+  shared.join(one, 1);
+
+  // This join will not change the value.
+  auto uno = one;
+  shared.join(uno, 1);
+
+  auto two = shared.getBottom();
+  shared.join(two, 2);
+
+  EXPECT_EQ(shared.compare(zero, zero), analysis::EQUAL);
+  EXPECT_EQ(shared.compare(zero, one), analysis::LESS);
+  EXPECT_EQ(shared.compare(zero, uno), analysis::LESS);
+  EXPECT_EQ(shared.compare(zero, two), analysis::LESS);
+
+  EXPECT_EQ(shared.compare(one, zero), analysis::GREATER);
+  EXPECT_EQ(shared.compare(one, one), analysis::EQUAL);
+  EXPECT_EQ(shared.compare(one, uno), analysis::EQUAL);
+  EXPECT_EQ(shared.compare(one, two), analysis::LESS);
+
+  EXPECT_EQ(shared.compare(two, zero), analysis::GREATER);
+  EXPECT_EQ(shared.compare(two, one), analysis::GREATER);
+  EXPECT_EQ(shared.compare(two, uno), analysis::GREATER);
+  EXPECT_EQ(shared.compare(two, two), analysis::EQUAL);
+
+  EXPECT_EQ(*zero, 2u);
+  EXPECT_EQ(*one, 2u);
+  EXPECT_EQ(*uno, 2u);
+  EXPECT_EQ(*two, 2u);
+}
+
+TEST(SharedLattice, Join) {
+  analysis::Shared<analysis::UInt32> shared{analysis::UInt32{}};
+
+  auto zero = shared.getBottom();
+
+  auto one = shared.getBottom();
+  shared.join(one, 1);
+
+  auto two = shared.getBottom();
+  shared.join(two, 2);
+
+  {
+    auto elem = zero;
+    EXPECT_FALSE(shared.join(elem, zero));
+    EXPECT_EQ(elem, zero);
+  }
+
+  {
+    auto elem = zero;
+    EXPECT_TRUE(shared.join(elem, one));
+    EXPECT_EQ(elem, one);
+  }
+
+  {
+    auto elem = zero;
+    EXPECT_TRUE(shared.join(elem, two));
+    EXPECT_EQ(elem, two);
+  }
+
+  {
+    auto elem = one;
+    EXPECT_FALSE(shared.join(elem, zero));
+    EXPECT_EQ(elem, one);
+  }
+
+  {
+    auto elem = one;
+    EXPECT_FALSE(shared.join(elem, one));
+    EXPECT_EQ(elem, one);
+  }
+
+  {
+    auto elem = one;
+    EXPECT_TRUE(shared.join(elem, two));
+    EXPECT_EQ(elem, two);
+  }
+
+  {
+    auto elem = two;
+    EXPECT_FALSE(shared.join(elem, zero));
+    EXPECT_EQ(elem, two);
+  }
+
+  {
+    auto elem = two;
+    EXPECT_FALSE(shared.join(elem, one));
+    EXPECT_EQ(elem, two);
+  }
+
+  {
+    auto elem = two;
+    EXPECT_FALSE(shared.join(elem, two));
+    EXPECT_EQ(elem, two);
+  }
+}