summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/analysis/lattices/shared.h126
-rw-r--r--src/tools/wasm-fuzz-lattices.cpp23
-rw-r--r--test/gtest/lattices.cpp108
3 files changed, 254 insertions, 3 deletions
diff --git a/src/analysis/lattices/shared.h b/src/analysis/lattices/shared.h
new file mode 100644
index 000000000..489ed0003
--- /dev/null
+++ b/src/analysis/lattices/shared.h
@@ -0,0 +1,126 @@
+/*
+ * 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_shared_h
+#define wasm_analysis_lattices_shared_h
+
+#include <cstdint>
+#include <utility>
+
+#include "../lattice.h"
+#include "bool.h"
+
+namespace wasm::analysis {
+
+// A lattice whose elements are a single ascending chain in lattice `L`.
+// Internally, there is only ever a single monotonically increasing element of L
+// materialized. Dereferencing any element of the Shared lattice will produce
+// the current value of that single element of L, which is generally safe
+// because the current value always overapproximates (i.e. is higher in the
+// lattice than) the value at the time of the Shared element's construction.
+//
+// Each element of this lattice maintains a sequence number that corresponds to
+// a value the shared underlying element has had at some point in time. Higher
+// sequence numbers correspond to greater values of the underlying element.
+// Elements of this lattice are compared and joined using these sequence
+// numbers, so blocks will correctly be re-analyzed if the value has increased
+// since the last time they were analyzed.
+template<Lattice L> struct Shared {
+ // If we ever have extremely long-running analyses, this may need to be
+ // changed to uint64_t.
+ using Seq = uint32_t;
+
+ class Element {
+ const typename L::Element* val;
+ Seq seq = 0;
+
+ Element(const typename L::Element* val) : val(val) {}
+
+ public:
+ Element() = default;
+ Element(const Element&) = default;
+ Element(Element&&) = default;
+ Element& operator=(const Element&) = default;
+ Element& operator=(Element&&) = default;
+
+ // Only provide const references to the value to force all updates to go
+ // through our API.
+ const typename L::Element& operator*() const noexcept { return *val; }
+ const typename L::Element* operator->() const noexcept { return val; }
+
+ bool operator==(const Element& other) const noexcept {
+ assert(val == other.val);
+ return seq == other.seq;
+ }
+
+ bool operator!=(const Element& other) const noexcept {
+ return !(*this == other);
+ }
+
+ friend Shared;
+ };
+
+ L lattice;
+
+ // The current value that all elements point to and the current maximum
+ // sequence number. The sequence numbers monotonically increase along with
+ // `val` and serve to provide ordering between elements of this lattice. These
+ // are mutable because they are logically not part of the lattice itself, but
+ // rather of its elements. They are only stored inside the lattice because it
+ // is simpler and more efficient than using shared pointers.
+ mutable typename L::Element val;
+ mutable Seq seq = 0;
+
+ Shared(L&& l) : lattice(std::move(l)), val(lattice.getBottom()) {}
+
+ // TODO: Delete the move constructor and the move assignment operator. This
+ // requires fixing the lattice fuzzer first, since it depends on lattices
+ // being moveable.
+
+ Element getBottom() const noexcept { return Element{&val}; }
+
+ LatticeComparison compare(const Element& a, const Element& b) const noexcept {
+ assert(a.val == b.val);
+ return a.seq < b.seq ? LESS : a.seq == b.seq ? EQUAL : GREATER;
+ }
+
+ bool join(Element& joinee, const Element& joiner) const noexcept {
+ assert(joinee.val == joiner.val);
+ if (joinee.seq < joiner.seq) {
+ joinee.seq = joiner.seq;
+ return true;
+ }
+ return false;
+ }
+
+ bool join(Element& joinee, const typename L::Element& joiner) const noexcept {
+ if (lattice.join(val, joiner)) {
+ // We have moved to the next value in our ascending chain. Assign it a new
+ // sequence number and update joinee with that sequence number.
+ joinee.seq = ++seq;
+ return true;
+ }
+ return false;
+ }
+};
+
+#if __cplusplus >= 202002L
+static_assert(Lattice<Shared<Bool>>);
+#endif // __cplusplus >= 202002L
+
+} // namespace wasm::analysis
+
+#endif // wasm_analysis_lattices_shared_h
diff --git a/src/tools/wasm-fuzz-lattices.cpp b/src/tools/wasm-fuzz-lattices.cpp
index f380f3541..b0a0a97af 100644
--- a/src/tools/wasm-fuzz-lattices.cpp
+++ b/src/tools/wasm-fuzz-lattices.cpp
@@ -27,6 +27,7 @@
#include "analysis/lattices/int.h"
#include "analysis/lattices/inverted.h"
#include "analysis/lattices/lift.h"
+#include "analysis/lattices/shared.h"
#include "analysis/lattices/stack.h"
#include "analysis/lattices/tuple.h"
#include "analysis/lattices/valtype.h"
@@ -179,7 +180,8 @@ struct RandomLattice::L : std::variant<RandomFullLattice,
Lift<RandomLattice>,
ArrayLattice,
Vector<RandomLattice>,
- TupleLattice> {};
+ TupleLattice,
+ Shared<RandomLattice>> {};
struct RandomLattice::ElementImpl
: std::variant<typename RandomFullLattice::Element,
@@ -187,7 +189,8 @@ struct RandomLattice::ElementImpl
typename Lift<RandomLattice>::Element,
typename ArrayLattice::Element,
typename Vector<RandomLattice>::Element,
- typename TupleLattice::Element> {};
+ typename TupleLattice::Element,
+ typename Shared<RandomLattice>::Element> {};
constexpr int FullLatticePicks = 7;
@@ -230,7 +233,7 @@ RandomFullLattice::RandomFullLattice(Random& rand,
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(FullLatticePicks + 5);
+ uint32_t pick = rand.upTo(FullLatticePicks + 6);
if (pick < FullLatticePicks) {
lattice = std::make_unique<L>(L{RandomFullLattice{rand, depth, pick}});
@@ -256,6 +259,9 @@ RandomLattice::RandomLattice(Random& rand, size_t depth) : rand(rand) {
lattice = std::make_unique<L>(L{TupleLattice{
RandomLattice{rand, depth + 1}, RandomLattice{rand, depth + 1}}});
return;
+ case FullLatticePicks + 5:
+ lattice = std::make_unique<L>(L{Shared{RandomLattice{rand, depth + 1}}});
+ return;
}
WASM_UNREACHABLE("unexpected pick");
}
@@ -358,6 +364,11 @@ RandomLattice::Element RandomLattice::makeElement() const noexcept {
typename TupleLattice::Element{std::get<0>(l->lattices).makeElement(),
std::get<1>(l->lattices).makeElement()}};
}
+ if (const auto* l = std::get_if<Shared<RandomLattice>>(lattice.get())) {
+ auto elem = l->getBottom();
+ l->join(elem, l->lattice.makeElement());
+ return ElementImpl{elem};
+ }
WASM_UNREACHABLE("unexpected lattice");
}
@@ -466,6 +477,12 @@ void printElement(std::ostream& os,
printElement(os, second, depth + 1);
indent(os, depth);
os << ")\n";
+ } else if (const auto* e =
+ std::get_if<typename Shared<RandomLattice>::Element>(&*elem)) {
+ os << "Shared(\n";
+ printElement(os, **e, depth + 1);
+ indent(os, depth);
+ os << ")\n";
} else {
WASM_UNREACHABLE("unexpected element");
}
diff --git a/test/gtest/lattices.cpp b/test/gtest/lattices.cpp
index 81706e58e..49288fe85 100644
--- a/test/gtest/lattices.cpp
+++ b/test/gtest/lattices.cpp
@@ -20,6 +20,7 @@
#include "analysis/lattices/int.h"
#include "analysis/lattices/inverted.h"
#include "analysis/lattices/lift.h"
+#include "analysis/lattices/shared.h"
#include "analysis/lattices/tuple.h"
#include "analysis/lattices/valtype.h"
#include "analysis/lattices/vector.h"
@@ -546,3 +547,110 @@ TEST(ValTypeLattice, Meet) {
Type(HeapType::array, Nullable),
Type(HeapType::eq, Nullable));
}
+
+TEST(SharedLattice, GetBottom) {
+ analysis::Shared<analysis::UInt32> shared{analysis::UInt32{}};
+ EXPECT_EQ(*shared.getBottom(), 0u);
+}
+
+TEST(SharedLattice, Compare) {
+ analysis::Shared<analysis::UInt32> shared{analysis::UInt32{}};
+
+ auto zero = shared.getBottom();
+
+ auto one = shared.getBottom();
+ shared.join(one, 1);
+
+ // This join will not change the value.
+ auto uno = one;
+ shared.join(uno, 1);
+
+ auto two = shared.getBottom();
+ shared.join(two, 2);
+
+ EXPECT_EQ(shared.compare(zero, zero), analysis::EQUAL);
+ EXPECT_EQ(shared.compare(zero, one), analysis::LESS);
+ EXPECT_EQ(shared.compare(zero, uno), analysis::LESS);
+ EXPECT_EQ(shared.compare(zero, two), analysis::LESS);
+
+ EXPECT_EQ(shared.compare(one, zero), analysis::GREATER);
+ EXPECT_EQ(shared.compare(one, one), analysis::EQUAL);
+ EXPECT_EQ(shared.compare(one, uno), analysis::EQUAL);
+ EXPECT_EQ(shared.compare(one, two), analysis::LESS);
+
+ EXPECT_EQ(shared.compare(two, zero), analysis::GREATER);
+ EXPECT_EQ(shared.compare(two, one), analysis::GREATER);
+ EXPECT_EQ(shared.compare(two, uno), analysis::GREATER);
+ EXPECT_EQ(shared.compare(two, two), analysis::EQUAL);
+
+ EXPECT_EQ(*zero, 2u);
+ EXPECT_EQ(*one, 2u);
+ EXPECT_EQ(*uno, 2u);
+ EXPECT_EQ(*two, 2u);
+}
+
+TEST(SharedLattice, Join) {
+ analysis::Shared<analysis::UInt32> shared{analysis::UInt32{}};
+
+ auto zero = shared.getBottom();
+
+ auto one = shared.getBottom();
+ shared.join(one, 1);
+
+ auto two = shared.getBottom();
+ shared.join(two, 2);
+
+ {
+ auto elem = zero;
+ EXPECT_FALSE(shared.join(elem, zero));
+ EXPECT_EQ(elem, zero);
+ }
+
+ {
+ auto elem = zero;
+ EXPECT_TRUE(shared.join(elem, one));
+ EXPECT_EQ(elem, one);
+ }
+
+ {
+ auto elem = zero;
+ EXPECT_TRUE(shared.join(elem, two));
+ EXPECT_EQ(elem, two);
+ }
+
+ {
+ auto elem = one;
+ EXPECT_FALSE(shared.join(elem, zero));
+ EXPECT_EQ(elem, one);
+ }
+
+ {
+ auto elem = one;
+ EXPECT_FALSE(shared.join(elem, one));
+ EXPECT_EQ(elem, one);
+ }
+
+ {
+ auto elem = one;
+ EXPECT_TRUE(shared.join(elem, two));
+ EXPECT_EQ(elem, two);
+ }
+
+ {
+ auto elem = two;
+ EXPECT_FALSE(shared.join(elem, zero));
+ EXPECT_EQ(elem, two);
+ }
+
+ {
+ auto elem = two;
+ EXPECT_FALSE(shared.join(elem, one));
+ EXPECT_EQ(elem, two);
+ }
+
+ {
+ auto elem = two;
+ EXPECT_FALSE(shared.join(elem, two));
+ EXPECT_EQ(elem, two);
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-05 22:40:46 +0000