[analysis] Implement a Lift lattice (#6040)

This lattice "lifts" another lattice by inserting a new bottom element
underneath it.

3 files changed, 88 insertions, 0 deletions

diff --git a/src/analysis/lattices/flat.h b/src/analysis/lattices/flat.h
index c34f8fc7c..b3cfe3809 100644
--- a/src/analysis/lattices/flat.h
+++ b/src/analysis/lattices/flat.h
@@ -68,6 +68,7 @@ public:
       return EQUAL;
     }
   }
+
   bool join(Element& self, const Element& other) const noexcept {
     switch (compare(self, other)) {
       case LESS:
diff --git a/src/analysis/lattices/inverted.h b/src/analysis/lattices/inverted.h
index 57f708421..92b965323 100644
--- a/src/analysis/lattices/inverted.h
+++ b/src/analysis/lattices/inverted.h
@@ -20,6 +20,7 @@
 #include <utility>
 
 #include "../lattice.h"
+#include "bool.h"
 
 namespace wasm::analysis {
 
@@ -44,6 +45,10 @@ template<FullLattice L> struct Inverted {
   }
 };
 
+#if __cplusplus >= 202002L
+static_assert(Lattice<Inverted<Bool>>);
+#endif
+
 } // namespace wasm::analysis
 
 #endif // wasm_analysis_lattices_inverted_h
diff --git a/src/analysis/lattices/lift.h b/src/analysis/lattices/lift.h
new file mode 100644
index 000000000..a458fd6b6
--- /dev/null
+++ b/src/analysis/lattices/lift.h
@@ -0,0 +1,82 @@
+/*
+ * 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_lift_h
+#define wasm_analysis_lattices_lift_h
+
+#include <optional>
+#include <utility>
+
+#include "../lattice.h"
+#include "bool.h"
+
+namespace wasm::analysis {
+
+// A lattice created by "lifting" another lattice by inserting a new bottom
+// element that is less than all elements in the lifted lattice.
+template<Lattice L> struct Lift {
+  // Represent the bottom element as an empty optional and any element of the
+  // lifted lattice as a non-empty optional. This representation is
+  // intentionally part of the public API.
+  struct Element : std::optional<typename L::Element> {
+    bool isBottom() const noexcept { return !this->has_value(); }
+    bool operator==(const Element& other) const noexcept {
+      return (isBottom() && other.isBottom()) ||
+             (!isBottom() && !other.isBottom() && **this == *other);
+    }
+  };
+
+  L lattice;
+  Lift(L&& lattice) : lattice(std::move(lattice)) {}
+
+  Element getBottom() const noexcept { return {std::nullopt}; }
+  Element get(typename L::Element&& val) const noexcept {
+    return Element{std::move(val)};
+  }
+
+  LatticeComparison compare(const Element& a, const Element& b) const noexcept {
+    if (a.isBottom() && b.isBottom()) {
+      return EQUAL;
+    } else if (a.isBottom()) {
+      return LESS;
+    } else if (b.isBottom()) {
+      return GREATER;
+    } else {
+      return lattice.compare(*a, *b);
+    }
+  }
+
+  bool join(Element& self, const Element& other) const noexcept {
+    if (self.isBottom() && other.isBottom()) {
+      return false;
+    } else if (self.isBottom()) {
+      self = other;
+      return true;
+    } else if (other.isBottom()) {
+      return false;
+    } else {
+      return lattice.join(*self, *other);
+    }
+  }
+};
+
+#if __cplusplus >= 202002L
+static_assert(Lattice<Lift<Bool>>);
+#endif
+
+} // namespace wasm::analysis
+
+#endif // wasm_analysis_lattices_lift_h