[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 `<`.

1 files changed, 12 insertions, 4 deletions

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