[WIP UNREVIEWED SLOP] Add a BoundedConstraint utility It supports bounded conjunctions of <, <=, >, and >= relations with both arbitrary 64-bit integer constants and locals (represented with their indices). When the finite number of constraints would be exceeded, prioritize keeping the integer constraints and drop the extra variable constraints.
diff --git a/src/analysis/lattices/flat.h b/src/analysis/lattices/flat.h index a26b145..e0f6909 100644 --- a/src/analysis/lattices/flat.h +++ b/src/analysis/lattices/flat.h
@@ -116,10 +116,25 @@ } WASM_UNREACHABLE("unexpected comparison result"); } + + bool meet(Element& meetee, const Element& meeter) const noexcept { + switch (compare(meetee, meeter)) { + case GREATER: + meetee = meeter; + return true; + case NO_RELATION: + meetee = Element{Bot{}}; + return true; + case LESS: + case EQUAL: + return false; + } + WASM_UNREACHABLE("unexpected comparison result"); + } }; #if defined(__cpp_lib_concepts) -static_assert(Lattice<Flat<int>>); +static_assert(FullLattice<Flat<int>>); #endif } // namespace wasm::analysis
diff --git a/src/analysis/lattices/one-of.h b/src/analysis/lattices/one-of.h index ac1ff8c..4f27927 100644 --- a/src/analysis/lattices/one-of.h +++ b/src/analysis/lattices/one-of.h
@@ -27,6 +27,7 @@ #endif #include "analysis/lattice.h" +#include "analysis/lattices/bool.h" #include "support/utilities.h" namespace wasm::analysis {
diff --git a/src/ir/CMakeLists.txt b/src/ir/CMakeLists.txt index 9190697..5521529 100644 --- a/src/ir/CMakeLists.txt +++ b/src/ir/CMakeLists.txt
@@ -2,6 +2,7 @@ set(ir_SOURCES ExpressionAnalyzer.cpp ExpressionManipulator.cpp + constraint.cpp drop.cpp effects.cpp eh-utils.cpp
diff --git a/src/ir/constraint.cpp b/src/ir/constraint.cpp new file mode 100644 index 0000000..0ad880e --- /dev/null +++ b/src/ir/constraint.cpp
@@ -0,0 +1,119 @@ +/* + * Copyright 2026 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. + */ + +#include "ir/constraint.h" + +namespace wasm { + +using namespace analysis; + +// Defines a total order on Flat<Index>::Element that linearly extends the +// flat lattice partial order (where Bot < Index < Top, and different indices +// are unrelated). +// We order Bot < Index (ordered by index value) < Top. +std::strong_ordering orderFlatElements(const typename Flat<Index>::Element& a, + const typename Flat<Index>::Element& b) { + auto get_key = [](const typename Flat<Index>::Element& x) { + if (x.isBottom()) + return 0u; + if (x.isTop()) + return 2u; + return 1u; + }; + auto k1 = get_key(a); + auto k2 = get_key(b); + if (k1 != k2) + return k1 <=> k2; + // If both are Index, compare their uint32_t values. + if (k1 == 1) { + return *a.getVal() <=> *b.getVal(); + } + return std::strong_ordering::equal; +} + +// BoundedConstraintsBase::orderElements implements the total order for the +// OneOf elements. +// +// It satisfies the requirement to be a linear extension of the OneOf lattice +// partial order, and additionally orders constant bounds (index 0) before +// variable bounds (index 1) so that variable bounds are dropped first when +// the size limit N is exceeded in BoundedConjunction. +std::strong_ordering +BoundedConstraintsBase::orderElements(const typename L::Element& a, + const typename L::Element& b) const { + // If they belong to different component lattices, order constants (index 0) + // before variables (index 1). + if (a.index() != b.index()) { + return a.index() <=> b.index(); + } + + // If they belong to the same component lattice, we define a total order + // within that component that extends the component's lattice order. + + if (a.index() == 0) { + // Bound<Int64> component. + Bound<Int64> bound_int(Int64{}); + const auto& va = std::get<0>(a); + const auto& vb = std::get<0>(b); + + // If they are related in the lattice, use that order. + auto comp = bound_int.compare(va, vb); + if (comp == LESS) + return std::strong_ordering::less; + if (comp == GREATER) + return std::strong_ordering::greater; + if (comp == EQUAL) + return std::strong_ordering::equal; + + // If they are unrelated (e.g. x < 5 and x >= 3), we use an arbitrary + // total order on their representation: first by relation, then by value. + const auto& c1 = std::get<typename Bound<Int64>::Constraint>(va); + const auto& c2 = std::get<typename Bound<Int64>::Constraint>(vb); + if (c1.rel != c2.rel) { + return c1.rel <=> c2.rel; + } + return c1.val <=> c2.val; + } + + if (a.index() == 1) { + // Bound<Flat<Index>> component. + Bound<Flat<Index>> bound_flat(Flat<Index>{}); + const auto& va = std::get<1>(a); + const auto& vb = std::get<1>(b); + + // If they are related in the lattice, use that order. + auto comp = bound_flat.compare(va, vb); + if (comp == LESS) + return std::strong_ordering::less; + if (comp == GREATER) + return std::strong_ordering::greater; + if (comp == EQUAL) + return std::strong_ordering::equal; + + // If they are unrelated, compare by relation, then by the total order + // on Flat<Index> elements. + const auto& c1 = std::get<typename Bound<Flat<Index>>::Constraint>(va); + const auto& c2 = std::get<typename Bound<Flat<Index>>::Constraint>(vb); + if (c1.rel != c2.rel) { + return c1.rel <=> c2.rel; + } + return orderFlatElements(c1.val, c2.val); + } + + return std::strong_ordering::equal; +} + +} // namespace wasm
diff --git a/src/ir/constraint.h b/src/ir/constraint.h new file mode 100644 index 0000000..3234752 --- /dev/null +++ b/src/ir/constraint.h
@@ -0,0 +1,78 @@ +/* + * Copyright 2026 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_ir_constraint_h +#define wasm_ir_constraint_h + +#include "analysis/lattices/bound.h" +#include "analysis/lattices/bounded-conjunction.h" +#include "analysis/lattices/flat.h" +#include "analysis/lattices/int.h" +#include "analysis/lattices/one-of.h" +#include "support/index.h" +#include <compare> + +namespace wasm { + +// BoundedConstraintsBase defines the underlying lattice type and the total +// order on its elements. +// +// The underlying lattice is a OneOf lattice containing two types of bounds: +// 1. Bound<Int64>: Bounds against 64-bit integer constants (e.g. x < 5). +// The Int64 lattice is ordered by <. +// 2. Bound<Flat<Index>>: Bounds against other variables, represented by their +// local/parameter Index (e.g. x < $1). The Flat<Index> lattice has no +// order between different variable indices. +// +// An element of OneOf can be either a constant bound, a variable bound, Top, +// or Bottom. +struct BoundedConstraintsBase { + using L = analysis::OneOf<analysis::Bound<analysis::Int64>, + analysis::Bound<analysis::Flat<Index>>>; + + // Defines a total order on OneOf elements to be used by BoundedConjunction. + // It orders constant bounds before variable bounds (so variable bounds are + // dropped first when the size limit N is exceeded), and otherwise defines + // a linear extension of the OneOf lattice partial order. + std::strong_ordering orderElements(const typename L::Element& a, + const typename L::Element& b) const; +}; + +// BoundedConstraints<N> represents a conjunction of up to N constraints on a +// variable. Each constraint is either a constant bound or a variable bound. +// +// It is implemented as a BoundedConjunction over the OneOf lattice defined +// in BoundedConstraintsBase. +template<std::size_t N> +struct BoundedConstraints + : BoundedConstraintsBase, + analysis::BoundedConjunction<BoundedConstraints<N>, + typename BoundedConstraintsBase::L, + N> { + using Super = analysis::BoundedConjunction<BoundedConstraints<N>, + typename BoundedConstraintsBase::L, + N>; + + BoundedConstraints() + : BoundedConstraintsBase(), + Super(typename BoundedConstraintsBase::L( + analysis::Bound<analysis::Int64>(analysis::Int64{}), + analysis::Bound<analysis::Flat<Index>>(analysis::Flat<Index>{}))) {} +}; + +} // namespace wasm + +#endif // wasm_ir_constraint_h
diff --git a/test/gtest/CMakeLists.txt b/test/gtest/CMakeLists.txt index 4bd3580..8db8671 100644 --- a/test/gtest/CMakeLists.txt +++ b/test/gtest/CMakeLists.txt
@@ -9,6 +9,7 @@ arena.cpp cast-check.cpp cfg.cpp + constraint.cpp dataflow.cpp delta_debugging.cpp dfa_minimization.cpp
diff --git a/test/gtest/constraint.cpp b/test/gtest/constraint.cpp new file mode 100644 index 0000000..dd23dae --- /dev/null +++ b/test/gtest/constraint.cpp
@@ -0,0 +1,94 @@ +/* + * Copyright 2026 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. + */ + +#include "ir/constraint.h" +#include "gtest/gtest.h" + +using namespace wasm; +using namespace wasm::analysis; + +TEST(ConstraintTest, Basic) { + BoundedConstraints<2> lattice; + + auto bot = lattice.getBottom(); + BoundedConstraints<2>::Element top{ + inplace_vector<BoundedConstraintsBase::L::Element, 2>{}}; + + Bound<Int64> bound_int(Int64{}); + Bound<Flat<Index>> bound_flat(Flat<Index>{}); + + auto make_int_bound = [&](BoundRelation rel, int64_t val) { + return BoundedConstraintsBase::L::Element(std::in_place_index<0>, + bound_int.makeBound(rel, val)); + }; + + auto make_var_bound = [&](BoundRelation rel, Index var) { + return BoundedConstraintsBase::L::Element( + std::in_place_index<1>, + bound_flat.makeBound(rel, Flat<Index>{}.get(var))); + }; + + auto make_constraints = + [&](std::initializer_list<BoundedConstraintsBase::L::Element> elms) { + inplace_vector<BoundedConstraintsBase::L::Element, 2> vec; + for (const auto& e : elms) { + vec.push_back(e); + } + return BoundedConstraints<2>::Element{vec}; + }; + + auto c_int1 = make_int_bound(BoundRelation::LT, 5); // x < 5 + auto c_int2 = make_int_bound(BoundRelation::GE, 3); // x >= 3 + auto c_var1 = make_var_bound(BoundRelation::LE, 1); // x <= $1 + auto c_var2 = make_var_bound(BoundRelation::GT, 2); // x > $2 + + // Test compare + auto e_int1 = make_constraints({c_int1}); + auto e_int2 = make_constraints({c_int2}); + auto e_var1 = make_constraints({c_var1}); + + EXPECT_EQ(lattice.compare(bot, e_int1), LESS); + EXPECT_EQ(lattice.compare(top, e_int1), GREATER); + + EXPECT_EQ(lattice.compare(e_int1, e_int2), NO_RELATION); + EXPECT_EQ(lattice.compare(e_int1, e_var1), NO_RELATION); + + // Test boundedMeet (conjunction) + // Meet {x < 5} and {x >= 3} -> {x < 5, x >= 3} + { + auto meetee = e_int1; + EXPECT_TRUE(lattice.boundedMeet(meetee, e_int2)); + EXPECT_EQ(meetee, make_constraints({c_int1, c_int2})); + } + + // Meet {x < 5, x >= 3} and {x <= $1} -> exceeds N=2! + // It should keep constants (c_int1, c_int2) and drop variable (c_var1). + { + auto meetee = make_constraints({c_int1, c_int2}); + EXPECT_FALSE(lattice.boundedMeet(meetee, e_var1)); + EXPECT_EQ(meetee, make_constraints({c_int1, c_int2})); + } + + // Meet {x < 5, x <= $1} and {x > $2} -> exceeds N=2! + // Sorted: c_int1 (const), c_var1 (LE), c_var2 (GT). + // LE < GT, so c_var1 is kept, c_var2 is dropped. + { + auto meetee = make_constraints({c_int1, c_var1}); + auto meeter = make_constraints({c_var2}); + EXPECT_FALSE(lattice.boundedMeet(meetee, meeter)); + EXPECT_EQ(meetee, make_constraints({c_int1, c_var1})); + } +}