summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/analysis/lattices/array.h1
-rw-r--r--src/analysis/lattices/vector.h138
-rw-r--r--src/tools/wasm-fuzz-lattices.cpp74
3 files changed, 202 insertions, 11 deletions
diff --git a/src/analysis/lattices/array.h b/src/analysis/lattices/array.h
index 3426a3a77..7ac027302 100644
--- a/src/analysis/lattices/array.h
+++ b/src/analysis/lattices/array.h
@@ -27,6 +27,7 @@
namespace wasm::analysis {
// A lattice whose elements are N-tuples of elements of L. Also written as L^N.
+// N is supplied at compile time rather than run time like it is for Vector.
template<Lattice L, size_t N> struct Array {
using Element = std::array<typename L::Element, N>;
diff --git a/src/analysis/lattices/vector.h b/src/analysis/lattices/vector.h
new file mode 100644
index 000000000..d13380868
--- /dev/null
+++ b/src/analysis/lattices/vector.h
@@ -0,0 +1,138 @@
+/*
+ * 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_vector_h
+#define wasm_analysis_lattices_vector_h
+
+#include <vector>
+
+#include "../lattice.h"
+#include "bool.h"
+#include "flat.h"
+
+namespace wasm::analysis {
+
+// A lattice whose elements are N-tuples of elements of L. Also written as L^N.
+// N is supplied at run time rather than compile time like it is for Array.
+template<Lattice L> struct Vector {
+ using Element = std::vector<typename L::Element>;
+
+ L lattice;
+ const size_t size;
+
+ Vector(L&& lattice, size_t size) : lattice(std::move(lattice)), size(size) {}
+
+ Element getBottom() const noexcept {
+ return Element(size, lattice.getBottom());
+ }
+
+ Element getTop() const noexcept
+#if __cplusplus >= 202002L
+ requires FullLattice<L>
+#endif
+ {
+ return Element(size, lattice.getTop());
+ }
+
+ // `a` <= `b` if their elements are pairwise <=, etc. Unless we determine
+ // that there is no relation, we must check all the elements.
+ LatticeComparison compare(const Element& a, const Element& b) const noexcept {
+ assert(a.size() == size);
+ assert(b.size() == size);
+ auto result = EQUAL;
+ for (size_t i = 0; i < size; ++i) {
+ switch (lattice.compare(a[i], b[i])) {
+ case NO_RELATION:
+ return NO_RELATION;
+ case EQUAL:
+ continue;
+ case LESS:
+ if (result == GREATER) {
+ // Cannot be both less and greater.
+ return NO_RELATION;
+ }
+ result = LESS;
+ continue;
+ case GREATER:
+ if (result == LESS) {
+ // Cannot be both greater and less.
+ return NO_RELATION;
+ }
+ result = GREATER;
+ continue;
+ }
+ }
+ return result;
+ }
+
+ // Pairwise join on the elements.
+ bool join(Element& joinee, const Element& joiner) const noexcept {
+ assert(joinee.size() == size);
+ assert(joiner.size() == size);
+ bool result = false;
+ for (size_t i = 0; i < size; ++i) {
+ if constexpr (std::is_same_v<typename L::Element, bool>) {
+ // The vector<bool> specialization does not expose references to the
+ // individual bools because they might be in a bitmap, so we need a
+ // workaround.
+ bool e = joinee[i];
+ if (lattice.join(e, joiner[i])) {
+ joinee[i] = e;
+ result = true;
+ }
+ } else {
+ result |= lattice.join(joinee[i], joiner[i]);
+ }
+ }
+
+ return result;
+ }
+
+ // Pairwise meet on the elements.
+ bool meet(Element& meetee, const Element& meeter) const noexcept
+#if __cplusplus >= 202002L
+ requires FullLattice<L>
+#endif
+ {
+ assert(meetee.size() == size);
+ assert(meeter.size() == size);
+ bool result = false;
+ for (size_t i = 0; i < size; ++i) {
+ if constexpr (std::is_same_v<typename L::Element, bool>) {
+ // The vector<bool> specialization does not expose references to the
+ // individual bools because they might be in a bitmap, so we need a
+ // workaround.
+ bool e = meetee[i];
+ if (lattice.meet(e, meeter[i])) {
+ meetee[i] = e;
+ result = true;
+ }
+ } else {
+ result |= lattice.meet(meetee[i], meeter[i]);
+ }
+ }
+ return result;
+ }
+};
+
+#if __cplusplus >= 202002L
+static_assert(FullLattice<Vector<Bool>>);
+static_assert(Lattice<Vector<Flat<bool>>>);
+#endif
+
+} // namespace wasm::analysis
+
+#endif // wasm_analysis_lattices_vector_h
diff --git a/src/tools/wasm-fuzz-lattices.cpp b/src/tools/wasm-fuzz-lattices.cpp
index f073aa724..f583103d6 100644
--- a/src/tools/wasm-fuzz-lattices.cpp
+++ b/src/tools/wasm-fuzz-lattices.cpp
@@ -28,6 +28,7 @@
#include "analysis/lattices/inverted.h"
#include "analysis/lattices/lift.h"
#include "analysis/lattices/stack.h"
+#include "analysis/lattices/vector.h"
#include "analysis/liveness-transfer-function.h"
#include "analysis/reaching-definitions-transfer-function.h"
#include "analysis/transfer-function.h"
@@ -151,33 +152,38 @@ static_assert(Lattice<RandomLattice>);
using ArrayFullLattice = analysis::Array<RandomFullLattice, 2>;
using ArrayLattice = analysis::Array<RandomLattice, 2>;
-struct RandomFullLattice::L
- : std::variant<Bool, UInt32, Inverted<RandomFullLattice>, ArrayFullLattice> {
-};
+struct RandomFullLattice::L : std::variant<Bool,
+ UInt32,
+ Inverted<RandomFullLattice>,
+ ArrayFullLattice,
+ Vector<RandomFullLattice>> {};
struct RandomFullLattice::ElementImpl
: std::variant<typename Bool::Element,
typename UInt32::Element,
typename Inverted<RandomFullLattice>::Element,
- typename ArrayFullLattice::Element> {};
+ typename ArrayFullLattice::Element,
+ typename Vector<RandomFullLattice>::Element> {};
struct RandomLattice::L : std::variant<RandomFullLattice,
Flat<uint32_t>,
Lift<RandomLattice>,
- ArrayLattice> {};
+ ArrayLattice,
+ Vector<RandomLattice>> {};
struct RandomLattice::ElementImpl
: std::variant<typename RandomFullLattice::Element,
typename Flat<uint32_t>::Element,
typename Lift<RandomLattice>::Element,
- typename ArrayLattice::Element> {};
+ typename ArrayLattice::Element,
+ typename Vector<RandomLattice>::Element> {};
RandomFullLattice::RandomFullLattice(Random& rand,
size_t depth,
std::optional<uint32_t> maybePick)
: rand(rand) {
// TODO: Limit the depth once we get lattices with more fan-out.
- uint32_t pick = maybePick ? *maybePick : rand.upTo(4);
+ uint32_t pick = maybePick ? *maybePick : rand.upTo(5);
switch (pick) {
case 0:
lattice = std::make_unique<L>(L{Bool{}});
@@ -193,30 +199,39 @@ RandomFullLattice::RandomFullLattice(Random& rand,
lattice = std::make_unique<L>(
L{ArrayFullLattice{RandomFullLattice{rand, depth + 1}}});
return;
+ case 4:
+ lattice = std::make_unique<L>(
+ L{Vector{RandomFullLattice{rand, depth + 1}, rand.upTo(4)}});
+ return;
}
WASM_UNREACHABLE("unexpected pick");
}
RandomLattice::RandomLattice(Random& rand, size_t depth) : rand(rand) {
// TODO: Limit the depth once we get lattices with more fan-out.
- uint32_t pick = rand.upTo(7);
+ uint32_t pick = rand.upTo(9);
switch (pick) {
case 0:
case 1:
case 2:
case 3:
+ case 4:
lattice = std::make_unique<L>(L{RandomFullLattice{rand, depth, pick}});
return;
- case 4:
+ case 5:
lattice = std::make_unique<L>(L{Flat<uint32_t>{}});
return;
- case 5:
+ case 6:
lattice = std::make_unique<L>(L{Lift{RandomLattice{rand, depth + 1}}});
return;
- case 6:
+ case 7:
lattice =
std::make_unique<L>(L{ArrayLattice{RandomLattice{rand, depth + 1}}});
return;
+ case 8:
+ lattice = std::make_unique<L>(
+ L{Vector{RandomLattice{rand, depth + 1}, rand.upTo(4)}});
+ return;
}
WASM_UNREACHABLE("unexpected pick");
}
@@ -235,6 +250,14 @@ RandomFullLattice::Element RandomFullLattice::makeElement() const noexcept {
return ElementImpl{typename ArrayFullLattice::Element{
l->lattice.makeElement(), l->lattice.makeElement()}};
}
+ if (const auto* l = std::get_if<Vector<RandomFullLattice>>(lattice.get())) {
+ std::vector<typename RandomFullLattice::Element> elem;
+ elem.reserve(l->size);
+ for (size_t i = 0; i < l->size; ++i) {
+ elem.push_back(l->lattice.makeElement());
+ }
+ return ElementImpl{std::move(elem)};
+ }
WASM_UNREACHABLE("unexpected lattice");
}
@@ -261,6 +284,14 @@ RandomLattice::Element RandomLattice::makeElement() const noexcept {
return ElementImpl{typename ArrayLattice::Element{
l->lattice.makeElement(), l->lattice.makeElement()}};
}
+ if (const auto* l = std::get_if<Vector<RandomLattice>>(lattice.get())) {
+ std::vector<typename RandomLattice::Element> elem;
+ elem.reserve(l->size);
+ for (size_t i = 0; i < l->size; ++i) {
+ elem.push_back(l->lattice.makeElement());
+ }
+ return ElementImpl{std::move(elem)};
+ }
WASM_UNREACHABLE("unexpected lattice");
}
@@ -293,6 +324,17 @@ void printFullElement(std::ostream& os,
printFullElement(os, e->back(), depth + 1);
indent(os, depth);
os << "]\n";
+ } else if (const auto* vec =
+ std::get_if<typename Vector<RandomFullLattice>::Element>(
+ &*elem)) {
+ os << "Vector[\n";
+ for (const auto& e : *vec) {
+ printFullElement(os, e, depth + 1);
+ }
+ indent(os, depth);
+ os << "]\n";
+ } else {
+ WASM_UNREACHABLE("unexpected element");
}
}
@@ -332,6 +374,16 @@ void printElement(std::ostream& os,
printElement(os, e->back(), depth + 1);
indent(os, depth);
os << ")\n";
+ } else if (const auto* vec =
+ std::get_if<typename Vector<RandomLattice>::Element>(&*elem)) {
+ os << "Vector[\n";
+ for (const auto& e : *vec) {
+ printElement(os, e, depth + 1);
+ }
+ indent(os, depth);
+ os << "]\n";
+ } else {
+ WASM_UNREACHABLE("unexpected element");
}
}
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-06 17:49:30 +0000