[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, 126 insertions, 0 deletions

diff --git a/src/analysis/lattices/shared.h b/src/analysis/lattices/shared.h
new file mode 100644
index 000000000..489ed0003
--- /dev/null
+++ b/src/analysis/lattices/shared.h
@@ -0,0 +1,126 @@
+/*
+ * Copyright 2023 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef wasm_analysis_lattices_shared_h
+#define wasm_analysis_lattices_shared_h
+
+#include <cstdint>
+#include <utility>
+
+#include "../lattice.h"
+#include "bool.h"
+
+namespace wasm::analysis {
+
+// A lattice whose elements are a single ascending chain in lattice `L`.
+// Internally, there is only ever a single monotonically increasing element of L
+// materialized. Dereferencing any element of the Shared lattice will produce
+// the current value of that single element of L, which is generally safe
+// because the current value always overapproximates (i.e. is higher in the
+// lattice than) the value at the time of the Shared element's construction.
+//
+// Each element of this lattice maintains a sequence number that corresponds to
+// a value the shared underlying element has had at some point in time. Higher
+// sequence numbers correspond to greater values of the underlying element.
+// Elements of this lattice are compared and joined using these sequence
+// numbers, so blocks will correctly be re-analyzed if the value has increased
+// since the last time they were analyzed.
+template<Lattice L> struct Shared {
+  // If we ever have extremely long-running analyses, this may need to be
+  // changed to uint64_t.
+  using Seq = uint32_t;
+
+  class Element {
+    const typename L::Element* val;
+    Seq seq = 0;
+
+    Element(const typename L::Element* val) : val(val) {}
+
+  public:
+    Element() = default;
+    Element(const Element&) = default;
+    Element(Element&&) = default;
+    Element& operator=(const Element&) = default;
+    Element& operator=(Element&&) = default;
+
+    // Only provide const references to the value to force all updates to go
+    // through our API.
+    const typename L::Element& operator*() const noexcept { return *val; }
+    const typename L::Element* operator->() const noexcept { return val; }
+
+    bool operator==(const Element& other) const noexcept {
+      assert(val == other.val);
+      return seq == other.seq;
+    }
+
+    bool operator!=(const Element& other) const noexcept {
+      return !(*this == other);
+    }
+
+    friend Shared;
+  };
+
+  L lattice;
+
+  // The current value that all elements point to and the current maximum
+  // sequence number. The sequence numbers monotonically increase along with
+  // `val` and serve to provide ordering between elements of this lattice. These
+  // are mutable because they are logically not part of the lattice itself, but
+  // rather of its elements. They are only stored inside the lattice because it
+  // is simpler and more efficient than using shared pointers.
+  mutable typename L::Element val;
+  mutable Seq seq = 0;
+
+  Shared(L&& l) : lattice(std::move(l)), val(lattice.getBottom()) {}
+
+  // TODO: Delete the move constructor and the move assignment operator. This
+  // requires fixing the lattice fuzzer first, since it depends on lattices
+  // being moveable.
+
+  Element getBottom() const noexcept { return Element{&val}; }
+
+  LatticeComparison compare(const Element& a, const Element& b) const noexcept {
+    assert(a.val == b.val);
+    return a.seq < b.seq ? LESS : a.seq == b.seq ? EQUAL : GREATER;
+  }
+
+  bool join(Element& joinee, const Element& joiner) const noexcept {
+    assert(joinee.val == joiner.val);
+    if (joinee.seq < joiner.seq) {
+      joinee.seq = joiner.seq;
+      return true;
+    }
+    return false;
+  }
+
+  bool join(Element& joinee, const typename L::Element& joiner) const noexcept {
+    if (lattice.join(val, joiner)) {
+      // We have moved to the next value in our ascending chain. Assign it a new
+      // sequence number and update joinee with that sequence number.
+      joinee.seq = ++seq;
+      return true;
+    }
+    return false;
+  }
+};
+
+#if __cplusplus >= 202002L
+static_assert(Lattice<Shared<Bool>>);
+#endif // __cplusplus >= 202002L
+
+} // namespace wasm::analysis
+
+#endif // wasm_analysis_lattices_shared_h