diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/analysis/lattices/shared.h | 126 | ||||
| -rw-r--r-- | src/tools/wasm-fuzz-lattices.cpp | 23 |
2 files changed, 146 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"); } |