blob: 12e066d8551d1c8966ad41cb6711b06e73556ed3 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
/*
* 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_powerset_impl_h
#define wasm_analysis_lattices_powerset_impl_h
#include <iostream>
#include "powerset.h"
namespace wasm::analysis {
inline LatticeComparison FiniteIntPowersetLattice::compare(
const FiniteIntPowersetLattice::Element& left,
const FiniteIntPowersetLattice::Element& right) const noexcept {
// Both must be from the powerset lattice of the same set.
assert(left.bitvector.size() == right.bitvector.size());
// True in left, false in right.
bool leftNotRight = false;
// True in right, false in left.
bool rightNotLeft = false;
size_t size = left.bitvector.size();
for (size_t i = 0; i < size; ++i) {
leftNotRight |= (left.bitvector[i] && !right.bitvector[i]);
rightNotLeft |= (right.bitvector[i] && !left.bitvector[i]);
// We can end early if we know neither is a subset of the other.
if (leftNotRight && rightNotLeft) {
return NO_RELATION;
}
}
if (!leftNotRight) {
if (!rightNotLeft) {
return EQUAL;
}
return LESS;
} else if (!rightNotLeft) {
return GREATER;
}
return NO_RELATION;
}
inline FiniteIntPowersetLattice::Element
FiniteIntPowersetLattice::getBottom() const noexcept {
FiniteIntPowersetLattice::Element result(setSize);
return result;
}
// We count the number of element members present in the element by counting the
// trues in the bitvector.
inline size_t FiniteIntPowersetLattice::Element::count() const {
size_t count = 0;
for (auto it : bitvector) {
count += it;
}
return count;
}
// 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::join(Element& joinee,
const Element& joiner) const noexcept {
// Both must be from powerset lattice of the same set.
assert(joiner.bitvector.size() == joinee.bitvector.size());
bool modified = false;
for (size_t i = 0; i < joinee.bitvector.size(); ++i) {
// Bit is flipped on joinee only if joinee is false and joiner is true when
// joinee and joiner are OR'ed together.
modified |= (!joinee.bitvector[i] && joiner.bitvector[i]);
joinee.bitvector[i] = joinee.bitvector[i] || joiner.bitvector[i];
}
return modified;
}
inline void FiniteIntPowersetLattice::Element::print(std::ostream& os) {
// Element member 0 is on the left, element member N is on the right.
for (auto it : bitvector) {
os << it;
}
}
}; // namespace wasm::analysis
#endif // wasm_analysis_lattices_powerset_impl_h
|
