summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/analysis/lattices/tuple.h147
-rw-r--r--src/tools/wasm-fuzz-lattices.cpp78
2 files changed, 208 insertions, 17 deletions
diff --git a/src/analysis/lattices/tuple.h b/src/analysis/lattices/tuple.h
new file mode 100644
index 000000000..d63d81f47
--- /dev/null
+++ b/src/analysis/lattices/tuple.h
@@ -0,0 +1,147 @@
+/*
+ * 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_tuple_h
+#define wasm_analysis_lattices_tuple_h
+
+#include <tuple>
+#include <utility>
+
+#include "bool.h"
+#include "support/utilities.h"
+
+namespace wasm::analysis {
+
+template<Lattice... Ls> struct Tuple {
+ using Element = std::tuple<typename Ls::Element...>;
+
+ std::tuple<Ls...> lattices;
+
+ Tuple(Ls&&... lattices) : lattices({std::move(lattices)...}) {}
+
+private:
+ template<size_t... I>
+ Element getBottomImpl(std::index_sequence<I...>) const noexcept {
+ return {std::get<I>(lattices).getBottom()...};
+ }
+
+ template<size_t... I>
+ Element getTopImpl(std::index_sequence<I...>) const noexcept {
+ return {std::get<I>(lattices).getTop()...};
+ }
+
+ LatticeComparison compareImpl(const Element& a,
+ const Element& b,
+ LatticeComparison result,
+ std::index_sequence<>) const noexcept {
+ // Base case: there is nothing left to compare.
+ return result;
+ }
+
+ template<size_t I, size_t... Is>
+ LatticeComparison compareImpl(const Element& a,
+ const Element& b,
+ LatticeComparison result,
+ std::index_sequence<I, Is...>) const noexcept {
+ // Recursive case: compare the current elements, update `result`, and
+ // recurse to the next elements if necessary.
+ switch (std::get<I>(lattices).compare(std::get<I>(a), std::get<I>(b))) {
+ case EQUAL:
+ return compareImpl(a, b, result, std::index_sequence<Is...>{});
+ case LESS:
+ if (result == GREATER) {
+ // Cannot be both less and greater.
+ return NO_RELATION;
+ }
+ return compareImpl(a, b, LESS, std::index_sequence<Is...>{});
+ case GREATER:
+ if (result == LESS) {
+ // Cannot be both greater and less.
+ return NO_RELATION;
+ }
+ return compareImpl(a, b, GREATER, std::index_sequence<Is...>{});
+ case NO_RELATION:
+ return NO_RELATION;
+ }
+ WASM_UNREACHABLE("unexpected comparison");
+ }
+
+ int joinImpl(Element& joinee,
+ const Element& joiner,
+ std::index_sequence<>) const noexcept {
+ // Base case: there is nothing left to join.
+ return false;
+ }
+
+ template<size_t I, size_t... Is>
+ int joinImpl(Element& joinee,
+ const Element& joiner,
+ std::index_sequence<I, Is...>) const noexcept {
+ // Recursive case: join the current element and recurse to the next
+ // elements.
+ return std::get<I>(lattices).join(std::get<I>(joinee),
+ std::get<I>(joiner)) |
+ joinImpl(joinee, joiner, std::index_sequence<Is...>{});
+ }
+
+ int meetImpl(Element& meetee,
+ const Element& meeter,
+ std::index_sequence<>) const noexcept {
+ // Base case: there is nothing left to mee.
+ return false;
+ }
+
+ template<size_t I, size_t... Is>
+ int meetImpl(Element& meetee,
+ const Element& meeter,
+ std::index_sequence<I, Is...>) const noexcept {
+ // Recursive case: meet the current element and recurse to the next
+ // elements.
+ return (std::get<I>(lattices).meet(std::get<I>(meetee),
+ std::get<I>(meeter))) |
+ meetImpl(meetee, meeter, std::index_sequence<Is...>{});
+ }
+
+public:
+ Element getBottom() const noexcept {
+ return getBottomImpl(std::index_sequence_for<Ls...>());
+ }
+
+ Element getTop() const noexcept {
+ return getTopImpl(std::index_sequence_for<Ls...>());
+ }
+
+ LatticeComparison compare(const Element& a, const Element& b) const noexcept {
+ return compareImpl(a, b, EQUAL, std::index_sequence_for<Ls...>());
+ }
+
+ bool join(Element& joinee, const Element& joiner) const noexcept {
+ return joinImpl(joinee, joiner, std::index_sequence_for<Ls...>());
+ }
+
+ bool meet(Element& meetee, const Element& meeter) const noexcept {
+ return meetImpl(meetee, meeter, std::index_sequence_for<Ls...>());
+ }
+};
+
+#if __cplusplus >= 202002L
+static_assert(FullLattice<Tuple<>>);
+static_assert(FullLattice<Tuple<Bool>>);
+#endif
+
+} // namespace wasm::analysis
+
+#endif // wasm_analysis_lattices_tuple_h
diff --git a/src/tools/wasm-fuzz-lattices.cpp b/src/tools/wasm-fuzz-lattices.cpp
index f583103d6..7b7573798 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/tuple.h"
#include "analysis/lattices/vector.h"
#include "analysis/liveness-transfer-function.h"
#include "analysis/reaching-definitions-transfer-function.h"
@@ -152,38 +153,47 @@ static_assert(Lattice<RandomLattice>);
using ArrayFullLattice = analysis::Array<RandomFullLattice, 2>;
using ArrayLattice = analysis::Array<RandomLattice, 2>;
+using TupleFullLattice = analysis::Tuple<RandomFullLattice, RandomFullLattice>;
+using TupleLattice = analysis::Tuple<RandomLattice, RandomLattice>;
+
struct RandomFullLattice::L : std::variant<Bool,
UInt32,
Inverted<RandomFullLattice>,
ArrayFullLattice,
- Vector<RandomFullLattice>> {};
+ Vector<RandomFullLattice>,
+ TupleFullLattice> {};
struct RandomFullLattice::ElementImpl
: std::variant<typename Bool::Element,
typename UInt32::Element,
typename Inverted<RandomFullLattice>::Element,
typename ArrayFullLattice::Element,
- typename Vector<RandomFullLattice>::Element> {};
+ typename Vector<RandomFullLattice>::Element,
+ typename TupleFullLattice::Element> {};
struct RandomLattice::L : std::variant<RandomFullLattice,
Flat<uint32_t>,
Lift<RandomLattice>,
ArrayLattice,
- Vector<RandomLattice>> {};
+ Vector<RandomLattice>,
+ TupleLattice> {};
struct RandomLattice::ElementImpl
: std::variant<typename RandomFullLattice::Element,
typename Flat<uint32_t>::Element,
typename Lift<RandomLattice>::Element,
typename ArrayLattice::Element,
- typename Vector<RandomLattice>::Element> {};
+ typename Vector<RandomLattice>::Element,
+ typename TupleLattice::Element> {};
+
+constexpr int FullLatticePicks = 6;
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(5);
+ uint32_t pick = maybePick ? *maybePick : rand.upTo(FullLatticePicks);
switch (pick) {
case 0:
lattice = std::make_unique<L>(L{Bool{}});
@@ -203,35 +213,43 @@ RandomFullLattice::RandomFullLattice(Random& rand,
lattice = std::make_unique<L>(
L{Vector{RandomFullLattice{rand, depth + 1}, rand.upTo(4)}});
return;
+ case 5:
+ lattice = std::make_unique<L>(
+ L{TupleFullLattice{RandomFullLattice{rand, depth + 1},
+ RandomFullLattice{rand, depth + 1}}});
+ 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(9);
+ uint32_t pick = rand.upTo(FullLatticePicks + 5);
+
+ if (pick < FullLatticePicks) {
+ lattice = std::make_unique<L>(L{RandomFullLattice{rand, depth, pick}});
+ return;
+ }
+
switch (pick) {
- case 0:
- case 1:
- case 2:
- case 3:
- case 4:
- lattice = std::make_unique<L>(L{RandomFullLattice{rand, depth, pick}});
- return;
- case 5:
+ case FullLatticePicks + 0:
lattice = std::make_unique<L>(L{Flat<uint32_t>{}});
return;
- case 6:
+ case FullLatticePicks + 1:
lattice = std::make_unique<L>(L{Lift{RandomLattice{rand, depth + 1}}});
return;
- case 7:
+ case FullLatticePicks + 2:
lattice =
std::make_unique<L>(L{ArrayLattice{RandomLattice{rand, depth + 1}}});
return;
- case 8:
+ case FullLatticePicks + 3:
lattice = std::make_unique<L>(
L{Vector{RandomLattice{rand, depth + 1}, rand.upTo(4)}});
return;
+ case FullLatticePicks + 4:
+ lattice = std::make_unique<L>(L{TupleLattice{
+ RandomLattice{rand, depth + 1}, RandomLattice{rand, depth + 1}}});
+ return;
}
WASM_UNREACHABLE("unexpected pick");
}
@@ -258,6 +276,11 @@ RandomFullLattice::Element RandomFullLattice::makeElement() const noexcept {
}
return ElementImpl{std::move(elem)};
}
+ if (const auto* l = std::get_if<TupleFullLattice>(lattice.get())) {
+ return ElementImpl{typename TupleFullLattice::Element{
+ std::get<0>(l->lattices).makeElement(),
+ std::get<1>(l->lattices).makeElement()}};
+ }
WASM_UNREACHABLE("unexpected lattice");
}
@@ -292,6 +315,11 @@ RandomLattice::Element RandomLattice::makeElement() const noexcept {
}
return ElementImpl{std::move(elem)};
}
+ if (const auto* l = std::get_if<TupleLattice>(lattice.get())) {
+ return ElementImpl{
+ typename TupleLattice::Element{std::get<0>(l->lattices).makeElement(),
+ std::get<1>(l->lattices).makeElement()}};
+ }
WASM_UNREACHABLE("unexpected lattice");
}
@@ -333,6 +361,14 @@ void printFullElement(std::ostream& os,
}
indent(os, depth);
os << "]\n";
+ } else if (const auto* e =
+ std::get_if<typename TupleFullLattice::Element>(&*elem)) {
+ os << "Tuple(\n";
+ const auto& [first, second] = *e;
+ printFullElement(os, first, depth + 1);
+ printFullElement(os, second, depth + 1);
+ indent(os, depth);
+ os << ")\n";
} else {
WASM_UNREACHABLE("unexpected element");
}
@@ -382,6 +418,14 @@ void printElement(std::ostream& os,
}
indent(os, depth);
os << "]\n";
+ } else if (const auto* e =
+ std::get_if<typename TupleLattice::Element>(&*elem)) {
+ os << "Tuple(\n";
+ const auto& [first, second] = *e;
+ printElement(os, first, depth + 1);
+ printElement(os, second, 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 02:17:09 +0000