summaryrefslogtreecommitdiff
path: root/src/analysis
diff options
context:
space:
mode:
Diffstat (limited to 'src/analysis')
-rw-r--r--src/analysis/lattice.h13
-rw-r--r--src/analysis/lattices/powerset-impl.h13
-rw-r--r--src/analysis/lattices/powerset.h14
-rw-r--r--src/analysis/lattices/stack.h92
-rw-r--r--src/analysis/monotone-analyzer-impl.h2
5 files changed, 70 insertions, 64 deletions
diff --git a/src/analysis/lattice.h b/src/analysis/lattice.h
index 7865de20b..ab75e0829 100644
--- a/src/analysis/lattice.h
+++ b/src/analysis/lattice.h
@@ -46,16 +46,17 @@ concept Lattice = requires(const L& lattice,
// Lattices must have elements.
typename L::Element;
requires std::copyable<typename L::Element>;
- // We need to be able to get the bottom element.
+ // Get the bottom element of this lattice.
{ lattice.getBottom() } noexcept -> std::same_as<typename L::Element>;
- // Elements should be comparable. TODO: use <=> and std::three_way_comparable
- // once we support C++20 everywhere.
+ // Compare two elements of this lattice. TODO: use <=> and
+ // std::three_way_comparable once we support C++20 everywhere.
{
lattice.compare(constElem, constElem)
} noexcept -> std::same_as<LatticeComparison>;
- // We need to be able to get the least upper bound of two elements and know
- // whether any change was made.
- { elem.makeLeastUpperBound(constElem) } noexcept -> std::same_as<bool>;
+ // Modify `elem` in-place to be the join (aka least upper bound) of `elem` and
+ // `constElem`, returning true iff `elem` was modified, i.e. if it was not
+ // already an upper bound of `constElem`.
+ { lattice.join(elem, constElem) } noexcept -> std::same_as<bool>;
};
#else // __cplusplus >= 202002L
diff --git a/src/analysis/lattices/powerset-impl.h b/src/analysis/lattices/powerset-impl.h
index 3390934d3..e210a9e85 100644
--- a/src/analysis/lattices/powerset-impl.h
+++ b/src/analysis/lattices/powerset-impl.h
@@ -78,17 +78,18 @@ inline size_t FiniteIntPowersetLattice::Element::count() const {
// Least upper bound is implemented as a logical OR between the bitvectors on
// both sides. We return true if a bit is flipped in-place on the left so the
// worklist algorithm will know if when to enqueue more work.
-inline bool FiniteIntPowersetLattice::Element::makeLeastUpperBound(
- const FiniteIntPowersetLattice::Element& other) noexcept {
+inline bool
+FiniteIntPowersetLattice::join(Element& self,
+ const Element& other) const noexcept {
// Both must be from powerset lattice of the same set.
- assert(other.bitvector.size() == bitvector.size());
+ assert(other.bitvector.size() == self.bitvector.size());
bool modified = false;
- for (size_t i = 0; i < bitvector.size(); ++i) {
+ for (size_t i = 0; i < self.bitvector.size(); ++i) {
// Bit is flipped on self only if self is false and other is true when self
// and other are OR'ed together.
- modified |= (!bitvector[i] && other.bitvector[i]);
- bitvector[i] = bitvector[i] || other.bitvector[i];
+ modified |= (!self.bitvector[i] && other.bitvector[i]);
+ self.bitvector[i] = self.bitvector[i] || other.bitvector[i];
}
return modified;
diff --git a/src/analysis/lattices/powerset.h b/src/analysis/lattices/powerset.h
index 92159da12..6b3a2779a 100644
--- a/src/analysis/lattices/powerset.h
+++ b/src/analysis/lattices/powerset.h
@@ -71,11 +71,6 @@ public:
bool isTop() const { return count() == bitvector.size(); }
bool isBottom() const { return count() == 0; }
- // Calculates the LUB of this element with some other element and sets
- // this element to the LUB in place. Returns true if this element before
- // this method call was different than the LUB.
- bool makeLeastUpperBound(const Element& other) noexcept;
-
// Prints out the bits in the bitvector for a lattice element.
void print(std::ostream& os);
@@ -89,6 +84,11 @@ public:
// Returns an instance of the bottom lattice element.
Element getBottom() const noexcept;
+
+ // Modifies `self` to be the join (aka least upper bound) of `self` and
+ // `other`. Returns true if `self` was modified, i.e. if it was not already an
+ // upper bound of `other`.
+ bool join(Element& self, const Element& other) const noexcept;
};
// A layer of abstraction over FiniteIntPowersetLattice which maps
@@ -149,6 +149,10 @@ public:
}
Element getBottom() const noexcept { return intLattice.getBottom(); }
+
+ bool join(Element& self, const Element& other) const noexcept {
+ return intLattice.join(self, other);
+ }
};
} // namespace wasm::analysis
diff --git a/src/analysis/lattices/stack.h b/src/analysis/lattices/stack.h
index 988da036b..59a179010 100644
--- a/src/analysis/lattices/stack.h
+++ b/src/analysis/lattices/stack.h
@@ -127,51 +127,6 @@ public:
return value;
}
- // When taking the LUB, we take the LUBs of the elements of each stack
- // starting from the top of the stack. So, LUB([b, a], [b', a']) is
- // [LUB(b, b'), LUB(a, a')]. If one stack is higher than the other,
- // the bottom of the higher stack will be kept, while the LUB of the
- // corresponding tops of each stack will be taken. For instance,
- // LUB([d, c, b, a], [b', a']) is [d, c, LUB(b, b'), LUB(a, a')].
- //
- // We start at the top because it makes taking the LUB of stacks with
- // different scope easier, as mentioned at the top of the file. It also
- // fits with the conception of the stack starting at the top and having
- // an infinite bottom, which allows stacks of different height and scope
- // to be easily joined.
- bool makeLeastUpperBound(const Element& other) noexcept {
- // Top element cases, since top elements don't actually have the stack
- // value.
- if (isTop()) {
- return false;
- } else if (other.isTop()) {
- stackValue.reset();
- return true;
- }
-
- bool modified = false;
-
- // Merge the shorter height stack with the top of the longer height
- // stack. We do this by taking the LUB of each pair of matching elements
- // from both stacks.
- auto otherIt = other.stackValue->crbegin();
- auto thisIt = stackValue->rbegin();
- for (;
- thisIt != stackValue->rend() && otherIt != other.stackValue->crend();
- ++thisIt, ++otherIt) {
- modified |= thisIt->makeLeastUpperBound(*otherIt);
- }
-
- // If the other stack is higher, append the bottom of it to our current
- // stack.
- for (; otherIt != other.stackValue->crend(); ++otherIt) {
- stackValue->push_front(*otherIt);
- modified = true;
- }
-
- return modified;
- }
-
void print(std::ostream& os) {
if (isTop()) {
os << "TOP STACK" << std::endl;
@@ -188,6 +143,8 @@ public:
friend StackLattice;
};
+ Element getBottom() const noexcept { return Element{}; }
+
// Like in computing the LUB, we compare the tops of the two stacks, as it
// handles the case of stacks of different scopes. Comparisons are done by
// element starting from the top.
@@ -258,7 +215,50 @@ public:
}
}
- Element getBottom() const noexcept { return Element{}; }
+ // When taking the LUB, we take the LUBs of the elements of each stack
+ // starting from the top of the stack. So, LUB([b, a], [b', a']) is
+ // [LUB(b, b'), LUB(a, a')]. If one stack is higher than the other,
+ // the bottom of the higher stack will be kept, while the LUB of the
+ // corresponding tops of each stack will be taken. For instance,
+ // LUB([d, c, b, a], [b', a']) is [d, c, LUB(b, b'), LUB(a, a')].
+ //
+ // We start at the top because it makes taking the LUB of stacks with
+ // different scope easier, as mentioned at the top of the file. It also
+ // fits with the conception of the stack starting at the top and having
+ // an infinite bottom, which allows stacks of different height and scope
+ // to be easily joined.
+ bool join(Element& self, const Element& other) const noexcept {
+ // Top element cases, since top elements don't actually have the stack
+ // value.
+ if (self.isTop()) {
+ return false;
+ } else if (other.isTop()) {
+ self.stackValue.reset();
+ return true;
+ }
+
+ bool modified = false;
+
+ // Merge the shorter height stack with the top of the longer height
+ // stack. We do this by taking the LUB of each pair of matching elements
+ // from both stacks.
+ auto selfIt = self.stackValue->rbegin();
+ auto otherIt = other.stackValue->crbegin();
+ for (; selfIt != self.stackValue->rend() &&
+ otherIt != other.stackValue->crend();
+ ++selfIt, ++otherIt) {
+ modified |= lattice.join(*selfIt, *otherIt);
+ }
+
+ // If the other stack is higher, append the bottom of it to our current
+ // stack.
+ for (; otherIt != other.stackValue->crend(); ++otherIt) {
+ self.stackValue->push_front(*otherIt);
+ modified = true;
+ }
+
+ return modified;
+ }
};
} // namespace wasm::analysis
diff --git a/src/analysis/monotone-analyzer-impl.h b/src/analysis/monotone-analyzer-impl.h
index e52ac5759..1f8182908 100644
--- a/src/analysis/monotone-analyzer-impl.h
+++ b/src/analysis/monotone-analyzer-impl.h
@@ -45,7 +45,7 @@ inline void MonotoneCFGAnalyzer<L, TxFn>::evaluate() {
for (auto& dep : txfn.getDependents(cfg[i])) {
// If the input state for the dependent block changes, we need to
// re-analyze it.
- if (states[dep.getIndex()].makeLeastUpperBound(state)) {
+ if (lattice.join(states[dep.getIndex()], state)) {
worklist.push(dep.getIndex());
}
}
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-04 22:43:56 +0000