[analysis] Add a FullLattice concept and Inverted lattice (#6038)

The FullLattice concept extends the base Lattice with `getTop` and `meet`
operations. The `Inverted` lattice uses these operations to reverse the order of
an arbitrary full lattice, for example to create a lattice of integers ordered
by `>` rather than by `<`.

4 files changed, 89 insertions, 4 deletions

diff --git a/src/analysis/lattice.h b/src/analysis/lattice.h
index ab75e0829..977bea0d5 100644
--- a/src/analysis/lattice.h
+++ b/src/analysis/lattice.h
@@ -59,9 +59,29 @@ concept Lattice = requires(const L& lattice,
   { lattice.join(elem, constElem) } noexcept -> std::same_as<bool>;
 };
 
+// The analysis framework only uses bottom elements and least upper bounds (i.e.
+// joins) directly, so lattices do not necessarily need to implement top
+// elements and greatest lower bounds (i.e. meets) to be useable, even though
+// they are required for mathematical lattices. Implementing top elements and
+// meets does have the benefit of making a lattice generically invertable,
+// though. See lattices/inverted.h.
+template<typename L>
+concept FullLattice =
+  Lattice<L> && requires(const L& lattice,
+                         const typename L::Element& constElem,
+                         typename L::Element& elem) {
+    // Get the top element of this lattice.
+    { lattice.getTop() } noexcept -> std::same_as<typename L::Element>;
+    // Modify `elem` in-place to be the meet (aka greatest lower bound) of
+    // `elem` and `constEleme`, returning true iff `elem` was modified, i.e. if
+    // it was not already a lower bound of `constElem`.
+    { lattice.meet(elem, constElem) } noexcept -> std::same_as<bool>;
+  };
+
 #else // __cplusplus >= 202002L
 
 #define Lattice typename
+#define FullLattice typename
 
 #endif // __cplusplus >= 202002L
 
diff --git a/src/analysis/lattices/bool.h b/src/analysis/lattices/bool.h
index 31094fb7d..c905d69f4 100644
--- a/src/analysis/lattices/bool.h
+++ b/src/analysis/lattices/bool.h
@@ -26,6 +26,7 @@ namespace wasm::analysis {
 struct Bool {
   using Element = bool;
   Element getBottom() const noexcept { return false; }
+  Element getTop() const noexcept { return true; }
   LatticeComparison compare(Element a, Element b) const noexcept {
     return a > b ? GREATER : a == b ? EQUAL : LESS;
   }
@@ -36,6 +37,13 @@ struct Bool {
     }
     return false;
   }
+  bool meet(Element& self, Element other) const noexcept {
+    if (self && !other) {
+      self = other;
+      return true;
+    }
+    return false;
+  }
 };
 
 #if __cplusplus >= 202002L
diff --git a/src/analysis/lattices/int.h b/src/analysis/lattices/int.h
index a2cd37c1e..682ac1063 100644
--- a/src/analysis/lattices/int.h
+++ b/src/analysis/lattices/int.h
@@ -34,6 +34,7 @@ template<typename T>
 struct Integer {
   using Element = T;
   Element getBottom() const noexcept { return std::numeric_limits<T>::min(); }
+  Element getTop() const noexcept { return std::numeric_limits<T>::max(); }
   LatticeComparison compare(Element a, Element b) const noexcept {
     return a > b ? GREATER : a == b ? EQUAL : LESS;
   }
@@ -44,6 +45,13 @@ struct Integer {
     }
     return false;
   }
+  bool meet(Element& self, Element other) const noexcept {
+    if (self > other) {
+      self = other;
+      return true;
+    }
+    return false;
+  }
 };
 
 using Int32 = Integer<int32_t>;
@@ -52,10 +60,10 @@ using Int64 = Integer<int64_t>;
 using UInt64 = Integer<uint64_t>;
 
 #if __cplusplus >= 202002L
-static_assert(Lattice<Int32>);
-static_assert(Lattice<Int64>);
-static_assert(Lattice<UInt32>);
-static_assert(Lattice<UInt64>);
+static_assert(FullLattice<Int32>);
+static_assert(FullLattice<Int64>);
+static_assert(FullLattice<UInt32>);
+static_assert(FullLattice<UInt64>);
 #endif // __cplusplus >= 202002L
 
 } // namespace wasm::analysis
diff --git a/src/analysis/lattices/inverted.h b/src/analysis/lattices/inverted.h
new file mode 100644
index 000000000..57f708421
--- /dev/null
+++ b/src/analysis/lattices/inverted.h
@@ -0,0 +1,49 @@
+/*
+ * 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_inverted_h
+#define wasm_analysis_lattices_inverted_h
+
+#include <utility>
+
+#include "../lattice.h"
+
+namespace wasm::analysis {
+
+// Reverses the order of an arbitrary full lattice. For example,
+// `Inverted<UInt32>` would order uint32_t values by > rather than by <.
+template<FullLattice L> struct Inverted {
+  using Element = typename L::Element;
+
+  L lattice;
+  Inverted(L&& lattice) : lattice(std::move(lattice)) {}
+
+  Element getBottom() const noexcept { return lattice.getTop(); }
+  Element getTop() const noexcept { return lattice.getBottom(); }
+  LatticeComparison compare(const Element& a, const Element& b) const noexcept {
+    return reverseComparison(lattice.compare(a, b));
+  }
+  bool join(Element& self, Element other) const noexcept {
+    return lattice.meet(self, other);
+  }
+  bool meet(Element& self, Element other) const noexcept {
+    return lattice.join(self, other);
+  }
+};
+
+} // namespace wasm::analysis
+
+#endif // wasm_analysis_lattices_inverted_h