From 2c3860b8f6e9ba3e0878ecadfdef409da0f471b7 Mon Sep 17 00:00:00 2001 From: Thomas Lively Date: Thu, 2 Nov 2023 19:32:32 +0100 Subject: [analysis] Allow joining a single vector element efficiently (#6071) Previously, modifying a single vector element of a `Shared` element required materializing a full vector to do the join. When there is just a single element to update, materializing all the other elements with bottom value is useless work. Add a `Vector::SingletonElement` utility that represents but does not materialize a vector with a single non-bottom element and allow it to be passed to `Vector::join`. Also update `Shared` and `Inverted` so that `SingletonElement` joins still work on vectors wrapped in those other lattices. --- src/analysis/lattices/inverted.h | 8 +++- src/analysis/lattices/shared.h | 3 +- src/analysis/lattices/vector.h | 97 +++++++++++++++++++++++++--------------- 3 files changed, 68 insertions(+), 40 deletions(-) (limited to 'src') diff --git a/src/analysis/lattices/inverted.h b/src/analysis/lattices/inverted.h index b232d89aa..22e326742 100644 --- a/src/analysis/lattices/inverted.h +++ b/src/analysis/lattices/inverted.h @@ -37,10 +37,14 @@ template struct Inverted { LatticeComparison compare(const Element& a, const Element& b) const noexcept { return lattice.compare(b, a); } - bool join(Element& joinee, Element joiner) const noexcept { + + template + bool join(Element& joinee, const Elem& joiner) const noexcept { return lattice.meet(joinee, joiner); } - bool meet(Element& meetee, Element meeter) const noexcept { + + template + bool meet(Element& meetee, const Elem& meeter) const noexcept { return lattice.join(meetee, meeter); } }; diff --git a/src/analysis/lattices/shared.h b/src/analysis/lattices/shared.h index 489ed0003..e75b895ea 100644 --- a/src/analysis/lattices/shared.h +++ b/src/analysis/lattices/shared.h @@ -106,7 +106,8 @@ template struct Shared { return false; } - bool join(Element& joinee, const typename L::Element& joiner) const noexcept { + template + bool join(Element& joinee, const Elem& 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. diff --git a/src/analysis/lattices/vector.h b/src/analysis/lattices/vector.h index d13380868..175ec5e3c 100644 --- a/src/analysis/lattices/vector.h +++ b/src/analysis/lattices/vector.h @@ -30,6 +30,13 @@ namespace wasm::analysis { template struct Vector { using Element = std::vector; + // Represent a vector in which all but one of the elements are bottom without + // materializing the full vector. + struct SingletonElement : std::pair { + SingletonElement(size_t i, typename L::Element&& elem) + : std::pair{i, std::move(elem)} {} + }; + L lattice; const size_t size; @@ -39,13 +46,7 @@ template struct Vector { return Element(size, lattice.getBottom()); } - Element getTop() const noexcept -#if __cplusplus >= 202002L - requires FullLattice -#endif - { - return Element(size, lattice.getTop()); - } + Element getTop() const noexcept { 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. @@ -84,48 +85,70 @@ template struct Vector { assert(joiner.size() == size); bool result = false; for (size_t i = 0; i < size; ++i) { - if constexpr (std::is_same_v) { - // The vector 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]); - } + result |= joinAtIndex(joinee, i, joiner[i]); } - return result; } + bool join(Element& joinee, const SingletonElement& joiner) const noexcept { + const auto& [index, elem] = joiner; + assert(index < joinee.size()); + return joinAtIndex(joinee, index, elem); + } + // Pairwise meet on the elements. - bool meet(Element& meetee, const Element& meeter) const noexcept -#if __cplusplus >= 202002L - requires FullLattice -#endif - { + bool meet(Element& meetee, const Element& meeter) const noexcept { 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) { - // The vector 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]); - } + result |= meetAtIndex(meetee, i, meeter[i]); } return result; } + + bool meet(Element& meetee, const SingletonElement& meeter) const noexcept { + const auto& [index, elem] = meeter; + assert(index < meetee.size()); + return meetAtIndex(meetee, index, elem); + } + +private: + bool joinAtIndex(Element& joinee, + size_t i, + const typename L::Element& elem) const noexcept { + if constexpr (std::is_same_v) { + // The vector 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, elem)) { + joinee[i] = e; + return true; + } + return false; + } else { + return lattice.join(joinee[i], elem); + } + } + + bool meetAtIndex(Element& meetee, + size_t i, + const typename L::Element& elem) const noexcept { + if constexpr (std::is_same_v) { + // The vector 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, elem)) { + meetee[i] = e; + return true; + } + return false; + } else { + return lattice.meet(meetee[i], elem); + } + } }; #if __cplusplus >= 202002L -- cgit v1.2.3