summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorThomas Lively <tlively@google.com>2023-11-01 18:15:44 +0100
committerGitHub <noreply@github.com>2023-11-01 18:15:44 +0100
commit74237bf7825cb9a2f0a83d73e239ed7a66a174a3 (patch)
treeb7d6a16940430e0f7a5b4ac437e4105438659f71 /src
parentc82627e698c67fc67e301fc9d130be6458c6e718 (diff)
downloadbinaryen-74237bf7825cb9a2f0a83d73e239ed7a66a174a3.tar.gz
binaryen-74237bf7825cb9a2f0a83d73e239ed7a66a174a3.tar.bz2
binaryen-74237bf7825cb9a2f0a83d73e239ed7a66a174a3.zip
[analysis] Add a lattice for value types (#6064)
Add a lattice that is a thin wrapper around `wasm::Type` giving it the interface of a lattice. As usual, `Type::unreachable` is the bottom element, but unlike in the underlying API, we uniformly treat `Type::none` as the top type so that we have a proper lattice.
Diffstat (limited to 'src')
-rw-r--r--src/analysis/lattices/valtype.h82
-rw-r--r--src/tools/wasm-fuzz-lattices.cpp59
2 files changed, 135 insertions, 6 deletions
diff --git a/src/analysis/lattices/valtype.h b/src/analysis/lattices/valtype.h
new file mode 100644
index 000000000..d63432ac6
--- /dev/null
+++ b/src/analysis/lattices/valtype.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_valtype_h
+#define wasm_analysis_lattices_valtype_h
+
+#include "../lattice.h"
+#include "wasm-type.h"
+
+namespace wasm::analysis {
+
+// Thin wrapper around `wasm::Type` giving it the interface of a lattice. As
+// usual, `Type::unreachable` is the bottom element, but unlike in the
+// underlying API, we uniformly treat `Type::none` as the top type so that we
+// have a proper lattice.
+struct ValType {
+ using Element = Type;
+
+ Element getBottom() const noexcept { return Type::unreachable; }
+
+ Element getTop() const noexcept { return Type::none; }
+
+ LatticeComparison compare(Element a, Element b) const noexcept {
+ if (a == b) {
+ return EQUAL;
+ }
+ if (b == Type::none || Type::isSubType(a, b)) {
+ return LESS;
+ }
+ if (a == Type::none || Type::isSubType(b, a)) {
+ return GREATER;
+ }
+ return NO_RELATION;
+ }
+
+ bool join(Element& joinee, Element joiner) const noexcept {
+ // `getLeastUpperBound` already treats `Type::none` as top.
+ auto lub = Type::getLeastUpperBound(joinee, joiner);
+ if (lub != joinee) {
+ joinee = lub;
+ return true;
+ }
+ return false;
+ }
+
+ bool meet(Element& meetee, Element meeter) const noexcept {
+ if (meetee == meeter || meeter == Type::none) {
+ return false;
+ }
+ if (meetee == Type::none) {
+ meetee = meeter;
+ return true;
+ }
+ auto glb = Type::getGreatestLowerBound(meetee, meeter);
+ if (glb != meetee) {
+ meetee = glb;
+ return true;
+ }
+ return false;
+ }
+};
+
+#if __cplusplus >= 202002L
+static_assert(FullLattice<ValType>);
+#endif
+
+} // namespace wasm::analysis
+
+#endif // wasm_analysis_lattices_valtype_h
diff --git a/src/tools/wasm-fuzz-lattices.cpp b/src/tools/wasm-fuzz-lattices.cpp
index 7b7573798..f380f3541 100644
--- a/src/tools/wasm-fuzz-lattices.cpp
+++ b/src/tools/wasm-fuzz-lattices.cpp
@@ -29,6 +29,7 @@
#include "analysis/lattices/lift.h"
#include "analysis/lattices/stack.h"
#include "analysis/lattices/tuple.h"
+#include "analysis/lattices/valtype.h"
#include "analysis/lattices/vector.h"
#include "analysis/liveness-transfer-function.h"
#include "analysis/reaching-definitions-transfer-function.h"
@@ -158,6 +159,7 @@ using TupleLattice = analysis::Tuple<RandomLattice, RandomLattice>;
struct RandomFullLattice::L : std::variant<Bool,
UInt32,
+ ValType,
Inverted<RandomFullLattice>,
ArrayFullLattice,
Vector<RandomFullLattice>,
@@ -166,6 +168,7 @@ struct RandomFullLattice::L : std::variant<Bool,
struct RandomFullLattice::ElementImpl
: std::variant<typename Bool::Element,
typename UInt32::Element,
+ typename ValType::Element,
typename Inverted<RandomFullLattice>::Element,
typename ArrayFullLattice::Element,
typename Vector<RandomFullLattice>::Element,
@@ -186,7 +189,7 @@ struct RandomLattice::ElementImpl
typename Vector<RandomLattice>::Element,
typename TupleLattice::Element> {};
-constexpr int FullLatticePicks = 6;
+constexpr int FullLatticePicks = 7;
RandomFullLattice::RandomFullLattice(Random& rand,
size_t depth,
@@ -202,18 +205,21 @@ RandomFullLattice::RandomFullLattice(Random& rand,
lattice = std::make_unique<L>(L{UInt32{}});
return;
case 2:
+ lattice = std::make_unique<L>(L{ValType{}});
+ return;
+ case 3:
lattice =
std::make_unique<L>(L{Inverted{RandomFullLattice{rand, depth + 1}}});
return;
- case 3:
+ case 4:
lattice = std::make_unique<L>(
L{ArrayFullLattice{RandomFullLattice{rand, depth + 1}}});
return;
- case 4:
+ case 5:
lattice = std::make_unique<L>(
L{Vector{RandomFullLattice{rand, depth + 1}, rand.upTo(4)}});
return;
- case 5:
+ case 6:
lattice = std::make_unique<L>(
L{TupleFullLattice{RandomFullLattice{rand, depth + 1},
RandomFullLattice{rand, depth + 1}}});
@@ -261,6 +267,38 @@ RandomFullLattice::Element RandomFullLattice::makeElement() const noexcept {
if (std::get_if<UInt32>(lattice.get())) {
return ElementImpl{rand.upToSquared(33)};
}
+ if (std::get_if<ValType>(lattice.get())) {
+ Type type;
+ // Choose a random type. No need to make all possible types available as
+ // long as we cover all the kinds of relationships between types.
+ switch (rand.upTo(8)) {
+ case 0:
+ type = Type::unreachable;
+ break;
+ case 1:
+ type = Type::none;
+ break;
+ case 2:
+ type = Type::i32;
+ break;
+ case 3:
+ type = Type::f32;
+ break;
+ case 4:
+ type = Type(HeapType::any, rand.oneIn(2) ? Nullable : NonNullable);
+ break;
+ case 5:
+ type = Type(HeapType::none, rand.oneIn(2) ? Nullable : NonNullable);
+ break;
+ case 6:
+ type = Type(HeapType::struct_, rand.oneIn(2) ? Nullable : NonNullable);
+ break;
+ case 7:
+ type = Type(HeapType::array, rand.oneIn(2) ? Nullable : NonNullable);
+ break;
+ }
+ return ElementImpl{type};
+ }
if (const auto* l = std::get_if<Inverted<RandomFullLattice>>(lattice.get())) {
return ElementImpl{l->lattice.makeElement()};
}
@@ -338,6 +376,8 @@ void printFullElement(std::ostream& os,
os << (*e ? "true" : "false") << "\n";
} else if (const auto* e = std::get_if<typename UInt32::Element>(&*elem)) {
os << *e << "\n";
+ } else if (const auto* e = std::get_if<typename ValType::Element>(&*elem)) {
+ os << *e << "\n";
} else if (const auto* e =
std::get_if<typename Inverted<RandomFullLattice>::Element>(
&*elem)) {
@@ -439,13 +479,20 @@ std::ostream& operator<<(std::ostream& os,
// Check that random lattices have the correct mathematical properties by
// checking the relationships between random elements.
-void checkLatticeProperties(Random& rand) {
+void checkLatticeProperties(Random& rand, bool verbose) {
RandomLattice lattice(rand);
// Generate the lattice elements we will perform checks on.
typename RandomLattice::Element elems[3] = {
lattice.makeElement(), lattice.makeElement(), lattice.makeElement()};
+ if (verbose) {
+ std::cout << "Random lattice elements:\n"
+ << elems[0] << "\n"
+ << elems[1] << "\n"
+ << elems[2];
+ }
+
// Calculate the relations between the generated elements.
LatticeComparison relation[3][3];
for (int i = 0; i < 3; ++i) {
@@ -920,7 +967,7 @@ struct Fuzzer {
}
Random rand(std::move(funcBytes));
- checkLatticeProperties(rand);
+ checkLatticeProperties(rand, verbose);
CFG cfg = CFG::fromFunction(func);
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-06 09:07:35 +0000