1 files changed, 106 insertions, 0 deletions
diff --git a/src/analysis/lattices/powerset-impl.h b/src/analysis/lattices/powerset-impl.h
new file mode 100644
index 000000000..3390934d3
--- /dev/null
+++ b/src/analysis/lattices/powerset-impl.h
@@ -0,0 +1,106 @@
+/*
+ * 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_powerset_impl_h
+#define wasm_analysis_lattices_powerset_impl_h
+
+#include <iostream>
+
+#include "powerset.h"
+
+namespace wasm::analysis {
+
+inline LatticeComparison FiniteIntPowersetLattice::compare(
+  const FiniteIntPowersetLattice::Element& left,
+  const FiniteIntPowersetLattice::Element& right) const noexcept {
+  // Both must be from the powerset lattice of the same set.
+  assert(left.bitvector.size() == right.bitvector.size());
+
+  // True in left, false in right.
+  bool leftNotRight = false;
+
+  // True in right, false in left.
+  bool rightNotLeft = false;
+
+  size_t size = left.bitvector.size();
+
+  for (size_t i = 0; i < size; ++i) {
+    leftNotRight |= (left.bitvector[i] && !right.bitvector[i]);
+    rightNotLeft |= (right.bitvector[i] && !left.bitvector[i]);
+
+    // We can end early if we know neither is a subset of the other.
+    if (leftNotRight && rightNotLeft) {
+      return NO_RELATION;
+    }
+  }
+
+  if (!leftNotRight) {
+    if (!rightNotLeft) {
+      return EQUAL;
+    }
+    return LESS;
+  } else if (!rightNotLeft) {
+    return GREATER;
+  }
+
+  return NO_RELATION;
+}
+
+inline FiniteIntPowersetLattice::Element
+FiniteIntPowersetLattice::getBottom() const noexcept {
+  FiniteIntPowersetLattice::Element result(setSize);
+  return result;
+}
+
+// We count the number of element members present in the element by counting the
+// trues in the bitvector.
+inline size_t FiniteIntPowersetLattice::Element::count() const {
+  size_t count = 0;
+  for (auto it : bitvector) {
+    count += it;
+  }
+  return count;
+}
+
+// Least upper bound is implemented as a logical OR between the bitvectors on
+// both sides. We return true if a bit is flipped in-place on the left so the
+// worklist algorithm will know if when to enqueue more work.
+inline bool FiniteIntPowersetLattice::Element::makeLeastUpperBound(
+  const FiniteIntPowersetLattice::Element& other) noexcept {
+  // Both must be from powerset lattice of the same set.
+  assert(other.bitvector.size() == bitvector.size());
+
+  bool modified = false;
+  for (size_t i = 0; i < bitvector.size(); ++i) {
+    // Bit is flipped on self only if self is false and other is true when self
+    // and other are OR'ed together.
+    modified |= (!bitvector[i] && other.bitvector[i]);
+    bitvector[i] = bitvector[i] || other.bitvector[i];
+  }
+
+  return modified;
+}
+
+inline void FiniteIntPowersetLattice::Element::print(std::ostream& os) {
+  // Element member 0 is on the left, element member N is on the right.
+  for (auto it : bitvector) {
+    os << it;
+  }
+}
+
+}; // namespace wasm::analysis
+
+#endif // wasm_analysis_lattices_powerset_impl_h