summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/analysis/cfg-impl.h15
-rw-r--r--src/analysis/lattice.h6
-rw-r--r--src/analysis/monotone-analyzer-impl.h39
-rw-r--r--src/analysis/monotone-analyzer.h67
-rw-r--r--src/analysis/transfer-function.h67
-rw-r--r--src/analysis/visitor-transfer-function.h9
-rw-r--r--src/tools/wasm-fuzz-lattices.cpp111
7 files changed, 138 insertions, 176 deletions
diff --git a/src/analysis/cfg-impl.h b/src/analysis/cfg-impl.h
index 14fadd22c..861a4471e 100644
--- a/src/analysis/cfg-impl.h
+++ b/src/analysis/cfg-impl.h
@@ -27,7 +27,7 @@ namespace wasm::analysis {
template<typename T> struct _indirect_ptr_iterator {
using iterator_category = std::random_access_iterator_tag;
using value_type = T;
- using different_type = off_t;
+ using difference_type = off_t;
using reference = const T&;
using pointer = const T*;
@@ -75,6 +75,10 @@ template<typename T> struct _indirect_ptr_iterator {
return it;
}
+ off_t operator-(const _indirect_ptr_iterator& other) const {
+ return ptr - other.ptr;
+ }
+
bool operator==(const _indirect_ptr_iterator& other) const {
return ptr == other.ptr;
}
@@ -98,8 +102,17 @@ template<typename T> struct _indirect_ptr_iterator {
bool operator>=(const _indirect_ptr_iterator& other) const {
return ptr >= other.ptr;
}
+
+ friend _indirect_ptr_iterator operator+(off_t n,
+ const _indirect_ptr_iterator& it) {
+ return it + n;
+ }
};
+#if __cplusplus >= 202002L
+static_assert(std::random_access_iterator<_indirect_ptr_iterator<int>>);
+#endif
+
template<typename T>
_indirect_ptr_iterator<T> operator+(int n,
const _indirect_ptr_iterator<T>& it) {
diff --git a/src/analysis/lattice.h b/src/analysis/lattice.h
index f3dd6122e..8d2b22243 100644
--- a/src/analysis/lattice.h
+++ b/src/analysis/lattice.h
@@ -17,6 +17,10 @@
#ifndef wasm_analysis_lattice_h
#define wasm_analysis_lattice_h
+#if __cplusplus >= 202002L
+#include <concepts>
+#endif
+
namespace wasm::analysis {
enum LatticeComparison { NO_RELATION, EQUAL, LESS, GREATER };
@@ -35,8 +39,6 @@ inline LatticeComparison reverseComparison(LatticeComparison comparison) {
#if __cplusplus >= 202002L
-#include <concepts>
-
template<typename L>
concept Lattice = requires(const L& lattice,
const typename L::Element& constElem,
diff --git a/src/analysis/monotone-analyzer-impl.h b/src/analysis/monotone-analyzer-impl.h
index a87ba4282..f6b869493 100644
--- a/src/analysis/monotone-analyzer-impl.h
+++ b/src/analysis/monotone-analyzer-impl.h
@@ -30,10 +30,11 @@ template<Lattice L> inline void BlockState<L>::print(std::ostream& os) {
os << std::endl;
}
-template<Lattice L, typename TransferFunction>
-inline MonotoneCFGAnalyzer<L, TransferFunction>::MonotoneCFGAnalyzer(
- L& lattice, TransferFunction& transferFunction, CFG& cfg)
- : lattice(lattice), transferFunction(transferFunction), cfg(cfg) {
+template<Lattice L, TransferFunction TxFn>
+inline MonotoneCFGAnalyzer<L, TxFn>::MonotoneCFGAnalyzer(L& lattice,
+ TxFn& txfn,
+ CFG& cfg)
+ : lattice(lattice), txfn(txfn), cfg(cfg) {
// Construct BlockStates for each BasicBlock.
for (auto it = cfg.begin(); it != cfg.end(); it++) {
@@ -41,18 +42,18 @@ inline MonotoneCFGAnalyzer<L, TransferFunction>::MonotoneCFGAnalyzer(
}
}
-template<Lattice L, typename TransferFunction>
-inline void MonotoneCFGAnalyzer<L, TransferFunction>::evaluateFunctionEntry(
- Function* func) {
- transferFunction.evaluateFunctionEntry(func, stateBlocks[0].inputState);
+template<Lattice L, TransferFunction TxFn>
+inline void
+MonotoneCFGAnalyzer<L, TxFn>::evaluateFunctionEntry(Function* func) {
+ txfn.evaluateFunctionEntry(func, stateBlocks[0].inputState);
}
-template<Lattice L, typename TransferFunction>
-inline void MonotoneCFGAnalyzer<L, TransferFunction>::evaluate() {
+template<Lattice L, TransferFunction TxFn>
+inline void MonotoneCFGAnalyzer<L, TxFn>::evaluate() {
std::queue<const BasicBlock*> worklist;
// Transfer function enqueues the work in some order which is efficient.
- transferFunction.enqueueWorklist(cfg, worklist);
+ txfn.enqueueWorklist(cfg, worklist);
while (!worklist.empty()) {
BlockState<L>& currBlockState = stateBlocks[worklist.front()->getIndex()];
@@ -63,10 +64,10 @@ inline void MonotoneCFGAnalyzer<L, TransferFunction>::evaluate() {
// to arrive at the expression's state. The beginning and end states of the
// CFG block will be updated.
typename L::Element outputState = currBlockState.inputState;
- transferFunction.transfer(currBlockState.cfgBlock, outputState);
+ txfn.transfer(currBlockState.cfgBlock, outputState);
// Propagate state to dependents of currBlockState.
- for (auto& dep : transferFunction.getDependents(currBlockState.cfgBlock)) {
+ for (auto& dep : txfn.getDependents(currBlockState.cfgBlock)) {
// If we need to change the input state of a dependent, we need
// to enqueue the dependent to recalculate it.
if (stateBlocks[dep.getIndex()].inputState.makeLeastUpperBound(
@@ -77,8 +78,8 @@ inline void MonotoneCFGAnalyzer<L, TransferFunction>::evaluate() {
}
}
-template<Lattice L, typename TransferFunction>
-inline void MonotoneCFGAnalyzer<L, TransferFunction>::collectResults() {
+template<Lattice L, TransferFunction TxFn>
+inline void MonotoneCFGAnalyzer<L, TxFn>::collectResults() {
for (BlockState currBlockState : stateBlocks) {
typename L::Element inputStateCopy = currBlockState.inputState;
@@ -86,19 +87,19 @@ inline void MonotoneCFGAnalyzer<L, TransferFunction>::collectResults() {
// produce useful information. For example, in reaching definitions
// analysis, these final states are used to populate a mapping of
// local.get's to a set of local.set's that affect its value.
- transferFunction.collectResults(currBlockState.cfgBlock, inputStateCopy);
+ txfn.collectResults(currBlockState.cfgBlock, inputStateCopy);
}
}
// Currently prints both the basic information and intermediate states of each
// BlockState.
-template<Lattice L, typename TransferFunction>
-inline void MonotoneCFGAnalyzer<L, TransferFunction>::print(std::ostream& os) {
+template<Lattice L, TransferFunction TxFn>
+inline void MonotoneCFGAnalyzer<L, TxFn>::print(std::ostream& os) {
os << "CFG Analyzer" << std::endl;
for (auto state : stateBlocks) {
state.print(os);
typename L::Element temp = state.inputState;
- transferFunction.print(os, state.cfgBlock, temp);
+ txfn.print(os, state.cfgBlock, temp);
}
os << "End" << std::endl;
}
diff --git a/src/analysis/monotone-analyzer.h b/src/analysis/monotone-analyzer.h
index 480cf2185..f2a593223 100644
--- a/src/analysis/monotone-analyzer.h
+++ b/src/analysis/monotone-analyzer.h
@@ -7,6 +7,7 @@
#include "cfg.h"
#include "lattice.h"
+#include "transfer-function.h"
namespace wasm::analysis {
@@ -26,76 +27,16 @@ template<Lattice L> struct BlockState {
void print(std::ostream& os);
};
-// A transfer function using a lattice <Lattice> is required to have the
-// following methods:
-
-// Lattice::Element transfer(const BasicBlock* cfgBlock, Lattice::Element&
-// inputState);
-
-// This function takes in a pointer to a CFG BasicBlock and the input state
-// associated with it and modifies the input state in-place into the ouptut
-// state for the basic block by applying the analysis transfer function to each
-// expression in the CFG BasicBlock. Starting with the input state, the transfer
-// function is used to change the state to new intermediate states based on each
-// expression until we reach the output state. The outuput state will be
-// propagated to dependents of the CFG BasicBlock by the worklist algorithm in
-// MonotoneCFGAnalyzer.
-
-template<typename TransferFunction, Lattice L>
-constexpr bool has_transfer =
- std::is_invocable_r<void,
- decltype(&TransferFunction::transfer),
- TransferFunction,
- const BasicBlock*,
- typename L::Element&>::value;
-
-// void enqueueWorklist(CFG&, std::queue<const BasicBlock*>& value);
-
-// Loads CFG BasicBlocks in some order into the worklist. Custom specifying the
-// order for each analysis brings performance savings. For example, when doing a
-// backward analysis, loading the BasicBlocks in reverse order will lead to less
-// state propagations, and therefore better performance. The opposite is true
-// for a forward analysis.
-
-template<typename TransferFunction, Lattice L>
-constexpr bool has_enqueueWorklist =
- std::is_invocable_r<void,
- decltype(&TransferFunction::enqueueWorklist),
- TransferFunction,
- CFG&,
- std::queue<const BasicBlock*>&>::value;
-
-// BasicBlock::BasicBlockIterable getDependents(const BasicBlock* currBlock);
-
-// Returns an iterable to the CFG BasicBlocks which depend on currBlock for
-// information (e.g. predecessors in a backward analysis). Used to select which
-// blocks to propagate to after applying the transfer function to a block.
-
-template<typename TransferFunction>
-constexpr bool has_getDependents =
- std::is_invocable_r<BasicBlock::BasicBlockIterable,
- decltype(&TransferFunction::getDependents),
- TransferFunction,
- const BasicBlock*>::value;
-
-// Combined TransferFunction assertions.
-template<typename TransferFunction, Lattice L>
-constexpr bool is_TransferFunction = has_transfer<TransferFunction, L> &&
- has_enqueueWorklist<TransferFunction, L> &&
- has_getDependents<TransferFunction>;
-
-template<Lattice L, typename TransferFunction> class MonotoneCFGAnalyzer {
- static_assert(is_TransferFunction<TransferFunction, L>);
-
+template<Lattice L, TransferFunction TxFn> class MonotoneCFGAnalyzer {
L& lattice;
- TransferFunction& transferFunction;
+ TxFn& txfn;
CFG& cfg;
std::vector<BlockState<L>> stateBlocks;
public:
// Will constuct BlockState objects corresponding to BasicBlocks from the
// given CFG.
- MonotoneCFGAnalyzer(L& lattice, TransferFunction& transferFunction, CFG& cfg);
+ MonotoneCFGAnalyzer(L& lattice, TxFn& txfn, CFG& cfg);
// Runs the worklist algorithm to compute the states for the BlockState graph.
void evaluate();
diff --git a/src/analysis/transfer-function.h b/src/analysis/transfer-function.h
new file mode 100644
index 000000000..88fd8a1b1
--- /dev/null
+++ b/src/analysis/transfer-function.h
@@ -0,0 +1,67 @@
+/*
+ * 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_transfer_function_h
+#define wasm_analysis_transfer_function_h
+
+#if __cplusplus >= 202002L
+#include <concepts>
+#include <iterator>
+#include <ranges>
+#endif
+
+#include <queue>
+
+#include "cfg.h"
+#include "lattice.h"
+
+namespace wasm::analysis {
+
+#if __cplusplus >= 202002L
+
+template<typename T>
+concept BasicBlockInputRange =
+ std::ranges::input_range<T> &&
+ std::is_same<std::ranges::range_value_t<T>, BasicBlock>::value;
+
+template<typename TxFn, typename L>
+concept TransferFunctionImpl = requires(TxFn& txfn,
+ const CFG& cfg,
+ BasicBlock* bb,
+ typename L::Element& elem,
+ std::queue<const BasicBlock*>& bbq) {
+ // Apply the transfer function to update a lattice element with information
+ // from a basic block.
+ { txfn.transfer(bb, elem) } noexcept -> std::same_as<void>;
+ // Initializes the worklist of basic blocks, which can affect performance
+ // depending on the direction of the analysis. TODO: Unlock performance
+ // benefits while exposing fewer implementation details.
+ { txfn.enqueueWorklist(cfg, bbq) } noexcept -> std::same_as<void>;
+ // Get a range over the basic blocks that depend on the given block.
+ { txfn.getDependents(bb) } noexcept -> BasicBlockInputRange;
+};
+
+#define TransferFunction TransferFunctionImpl<L>
+
+#else
+
+#define TransferFunction typename
+
+#endif // __cplusplus >= 202002L
+
+} // namespace wasm::analysis
+
+#endif // wasm_analysis_transfer_function_h
diff --git a/src/analysis/visitor-transfer-function.h b/src/analysis/visitor-transfer-function.h
index 699840ff3..79acf00da 100644
--- a/src/analysis/visitor-transfer-function.h
+++ b/src/analysis/visitor-transfer-function.h
@@ -35,7 +35,8 @@ protected:
public:
// Returns an iterable to all the BasicBlocks which depend on currBlock for
// information.
- BasicBlock::BasicBlockIterable getDependents(const BasicBlock* currBlock) {
+ BasicBlock::BasicBlockIterable
+ getDependents(const BasicBlock* currBlock) noexcept {
if constexpr (Direction == AnalysisDirection::Backward) {
return currBlock->preds();
} else {
@@ -46,7 +47,8 @@ public:
// Executes the transfer function on all the expressions of the corresponding
// CFG node, starting with the node's input state, and changes the input state
// to the final output state of the node in place.
- void transfer(const BasicBlock* cfgBlock, typename L::Element& inputState) {
+ void transfer(const BasicBlock* cfgBlock,
+ typename L::Element& inputState) noexcept {
// If the block is empty, we propagate the state by inputState =
// outputState.
@@ -71,7 +73,8 @@ public:
// analysis, we push all the blocks in order, while for backward analysis, we
// push them in reverse order, so that later blocks are evaluated before
// earlier ones.
- void enqueueWorklist(CFG& cfg, std::queue<const BasicBlock*>& worklist) {
+ void enqueueWorklist(const CFG& cfg,
+ std::queue<const BasicBlock*>& worklist) noexcept {
if constexpr (Direction == AnalysisDirection::Backward) {
for (auto it = cfg.rbegin(); it != cfg.rend(); ++it) {
worklist.push(&(*it));
diff --git a/src/tools/wasm-fuzz-lattices.cpp b/src/tools/wasm-fuzz-lattices.cpp
index 8aa94020e..fe801ba12 100644
--- a/src/tools/wasm-fuzz-lattices.cpp
+++ b/src/tools/wasm-fuzz-lattices.cpp
@@ -22,6 +22,7 @@
#include "analysis/lattices/stack.h"
#include "analysis/liveness-transfer-function.h"
#include "analysis/reaching-definitions-transfer-function.h"
+#include "analysis/transfer-function.h"
#include "support/command-line.h"
#include "tools/fuzzing.h"
@@ -44,26 +45,26 @@ uint64_t getSeed() {
// Utility class which provides methods to check properties of the transfer
// function and lattice of an analysis.
-template<Lattice L, typename TransferFunction> struct AnalysisChecker {
+template<Lattice L, TransferFunction TxFn> struct AnalysisChecker {
L& lattice;
- TransferFunction& transferFunction;
+ TxFn& txfn;
std::string latticeName;
- std::string transferFunctionName;
+ std::string txfnName;
uint64_t latticeElementSeed;
Name funcName;
AnalysisChecker(L& lattice,
- TransferFunction& transferFunction,
+ TxFn& txfn,
std::string latticeName,
- std::string transferFunctionName,
+ std::string txfnName,
uint64_t latticeElementSeed,
Name funcName)
- : lattice(lattice), transferFunction(transferFunction),
- latticeName(latticeName), transferFunctionName(transferFunctionName),
- latticeElementSeed(latticeElementSeed), funcName(funcName) {}
+ : lattice(lattice), txfn(txfn), latticeName(latticeName),
+ txfnName(txfnName), latticeElementSeed(latticeElementSeed),
+ funcName(funcName) {}
void printFailureInfo(std::ostream& os) {
- os << "Error for " << transferFunctionName << " and " << latticeName
+ os << "Error for " << txfnName << " and " << latticeName
<< " at lattice element seed " << latticeElementSeed << " and function "
<< funcName << ".\n";
}
@@ -81,8 +82,7 @@ template<Lattice L, typename TransferFunction> struct AnalysisChecker {
y.print(os);
os << ",\n";
z.print(os);
- os << "\nfor " << funcName << " to test " << transferFunctionName
- << ".\n\n";
+ os << "\nfor " << funcName << " to test " << txfnName << ".\n\n";
}
// Checks reflexivity of a lattice element, i.e. x = x.
@@ -263,11 +263,11 @@ public:
for (auto cfgIter = cfg.begin(); cfgIter != cfg.end(); ++cfgIter) {
// Apply transfer function on each lattice element.
typename L::Element xResult = x;
- transferFunction.transfer(&(*cfgIter), xResult);
+ txfn.transfer(&(*cfgIter), xResult);
typename L::Element yResult = y;
- transferFunction.transfer(&(*cfgIter), yResult);
+ txfn.transfer(&(*cfgIter), yResult);
typename L::Element zResult = z;
- transferFunction.transfer(&(*cfgIter), zResult);
+ txfn.transfer(&(*cfgIter), zResult);
// Check monotonicity for every pair of transfer function outputs.
checkMonotonicity(&(*cfgIter), x, y, xResult, yResult);
@@ -279,12 +279,12 @@ public:
// Struct to set up and check liveness analysis lattice and transfer function.
struct LivenessChecker {
- LivenessTransferFunction transferFunction;
+ LivenessTransferFunction txfn;
FiniteIntPowersetLattice lattice;
AnalysisChecker<FiniteIntPowersetLattice, LivenessTransferFunction> checker;
LivenessChecker(Function* func, uint64_t latticeElementSeed, Name funcName)
: lattice(func->getNumLocals()), checker(lattice,
- transferFunction,
+ txfn,
"FiniteIntPowersetLattice",
"LivenessTransferFunction",
latticeElementSeed,
@@ -321,28 +321,27 @@ struct LivenessChecker {
struct ReachingDefinitionsChecker {
LocalGraph::GetSetses getSetses;
LocalGraph::Locations locations;
- ReachingDefinitionsTransferFunction transferFunction;
+ ReachingDefinitionsTransferFunction txfn;
AnalysisChecker<FinitePowersetLattice<LocalSet*>,
ReachingDefinitionsTransferFunction>
checker;
ReachingDefinitionsChecker(Function* func,
uint64_t latticeElementSeed,
Name funcName)
- : transferFunction(func, getSetses, locations),
- checker(transferFunction.lattice,
- transferFunction,
+ : txfn(func, getSetses, locations),
+ checker(txfn.lattice,
+ txfn,
"FinitePowersetLattice<LocalSet*>",
"ReachingDefinitionsTransferFunction",
latticeElementSeed,
funcName) {}
FinitePowersetLattice<LocalSet*>::Element getRandomElement(Random& rand) {
- FinitePowersetLattice<LocalSet*>::Element result =
- transferFunction.lattice.getBottom();
+ FinitePowersetLattice<LocalSet*>::Element result = txfn.lattice.getBottom();
// Uses rand to randomly select which members are to be included (i. e. flip
// bits in the bitvector).
- for (size_t i = 0; i < transferFunction.lattice.getSetSize(); ++i) {
+ for (size_t i = 0; i < txfn.lattice.getSetSize(); ++i) {
result.set(i, rand.oneIn(2));
}
return result;
@@ -363,65 +362,6 @@ struct ReachingDefinitionsChecker {
}
};
-// Struct to set up and check the stack lattice. Uses the
-// FiniteIntPowersetLattice as to model stack contents.
-struct StackLatticeChecker {
- FiniteIntPowersetLattice contentLattice;
- StackLattice<FiniteIntPowersetLattice> stackLattice;
-
- // Here only as a placeholder, since the checker utility currently wants a
- // transfer function.
- LivenessTransferFunction transferFunction;
-
- AnalysisChecker<StackLattice<FiniteIntPowersetLattice>,
- LivenessTransferFunction>
- checker;
-
- StackLatticeChecker(Function* func,
- uint64_t latticeElementSeed,
- Name funcName)
- : contentLattice(func->getNumLocals()), stackLattice(contentLattice),
- checker(stackLattice,
- transferFunction,
- "StackLattice<FiniteIntPowersetLattice>",
- "LivenessTransferFunction",
- latticeElementSeed,
- funcName) {}
-
- StackLattice<FiniteIntPowersetLattice>::Element
- getRandomElement(Random& rand) {
- StackLattice<FiniteIntPowersetLattice>::Element result =
- stackLattice.getBottom();
-
- // Randomly decide on a stack height. A max height of 15 stack elements is
- // arbitrarily chosen.
- size_t stackHeight = rand.upTo(15);
-
- for (size_t j = 0; j < stackHeight; ++j) {
- // Randomly generate a FiniteIntPowersetLattice and push it onto the
- // stack.
- FiniteIntPowersetLattice::Element content = contentLattice.getBottom();
- for (size_t i = 0; i < contentLattice.getSetSize(); ++i) {
- content.set(i, rand.oneIn(2));
- }
- result.push(std::move(content));
- }
- return result;
- }
-
- // Runs all checks for the StackLattice analysis.
- void runChecks(Random& rand, bool verbose) {
- StackLattice<FiniteIntPowersetLattice>::Element x = getRandomElement(rand);
- StackLattice<FiniteIntPowersetLattice>::Element y = getRandomElement(rand);
- StackLattice<FiniteIntPowersetLattice>::Element z = getRandomElement(rand);
- if (verbose) {
- checker.printVerboseFunctionCase(std::cout, x, y, z);
- }
-
- checker.checkLatticeElements(x, y, z);
- }
-};
-
struct Fuzzer {
bool verbose;
@@ -443,7 +383,7 @@ struct Fuzzer {
CFG cfg = CFG::fromFunction(func);
- switch (rand.upTo(3)) {
+ switch (rand.upTo(2)) {
case 0: {
LivenessChecker livenessChecker(func, latticeElementSeed, func->name);
livenessChecker.runChecks(cfg, rand, verbose);
@@ -455,11 +395,6 @@ struct Fuzzer {
reachingDefinitionsChecker.runChecks(cfg, rand, verbose);
break;
}
- default: {
- StackLatticeChecker stackLatticeChecker(
- func, latticeElementSeed, func->name);
- stackLatticeChecker.runChecks(rand, verbose);
- }
}
}
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-05 02:54:48 +0000