summaryrefslogtreecommitdiff
path: root/src/analysis/monotone-analyzer-impl.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/analysis/monotone-analyzer-impl.h')
-rw-r--r--src/analysis/monotone-analyzer-impl.h99
1 files changed, 40 insertions, 59 deletions
diff --git a/src/analysis/monotone-analyzer-impl.h b/src/analysis/monotone-analyzer-impl.h
index f6b869493..e52ac5759 100644
--- a/src/analysis/monotone-analyzer-impl.h
+++ b/src/analysis/monotone-analyzer-impl.h
@@ -5,74 +5,48 @@
#include <unordered_map>
#include "monotone-analyzer.h"
+#include "support/unique_deferring_queue.h"
namespace wasm::analysis {
-// All states are set to the bottom lattice element using the lattice in this
-// constructor.
-template<Lattice L>
-inline BlockState<L>::BlockState(const BasicBlock* underlyingBlock, L& lattice)
- : cfgBlock(underlyingBlock), inputState(lattice.getBottom()) {}
-
-// Prints out inforamtion about a CFG node's state, but not intermediate states.
-template<Lattice L> inline void BlockState<L>::print(std::ostream& os) {
- os << "CFG Block: " << cfgBlock->getIndex() << std::endl;
- os << "Input State: ";
- inputState.print(os);
- os << std::endl << "Predecessors:";
- for (auto pred : cfgBlock->preds()) {
- os << " " << pred.getIndex();
- }
- os << std::endl << "Successors:";
- for (auto succ : cfgBlock->succs()) {
- os << " " << succ.getIndex();
- }
- os << std::endl;
-}
-
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++) {
- stateBlocks.emplace_back(&(*it), lattice);
- }
-}
+ : lattice(lattice), txfn(txfn), cfg(cfg),
+ states(cfg.size(), lattice.getBottom()) {}
template<Lattice L, TransferFunction TxFn>
inline void
MonotoneCFGAnalyzer<L, TxFn>::evaluateFunctionEntry(Function* func) {
- txfn.evaluateFunctionEntry(func, stateBlocks[0].inputState);
+ txfn.evaluateFunctionEntry(func, states[0]);
}
template<Lattice L, TransferFunction TxFn>
inline void MonotoneCFGAnalyzer<L, TxFn>::evaluate() {
- std::queue<const BasicBlock*> worklist;
+ UniqueDeferredQueue<Index> worklist;
- // Transfer function enqueues the work in some order which is efficient.
- txfn.enqueueWorklist(cfg, worklist);
+ // Start with all blocks on the work list. TODO: optimize the iteration order
+ // using e.g. strongly-connected components.
+ for (Index i = 0; i < cfg.size(); ++i) {
+ worklist.push(i);
+ }
while (!worklist.empty()) {
- BlockState<L>& currBlockState = stateBlocks[worklist.front()->getIndex()];
- worklist.pop();
-
- // For each expression, applies the transfer function, using the expression,
- // on the state of the expression it depends upon (here the next expression)
- // 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;
- txfn.transfer(currBlockState.cfgBlock, outputState);
-
- // Propagate state to dependents of currBlockState.
- 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(
- outputState)) {
- worklist.push(&dep);
+ // The index of the block we will analyze.
+ Index i = worklist.pop();
+
+ // Apply the transfer function to the input state to compute the output
+ // state for the block.
+ auto state = states[i];
+ txfn.transfer(cfg[i], state);
+
+ // Propagate state to the dependent blocks.
+ 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)) {
+ worklist.push(dep.getIndex());
}
}
}
@@ -80,14 +54,12 @@ inline void MonotoneCFGAnalyzer<L, TxFn>::evaluate() {
template<Lattice L, TransferFunction TxFn>
inline void MonotoneCFGAnalyzer<L, TxFn>::collectResults() {
- for (BlockState currBlockState : stateBlocks) {
- typename L::Element inputStateCopy = currBlockState.inputState;
-
+ for (Index i = 0, size = cfg.size(); i < size; ++i) {
// The transfer function generates the final set of states and uses it to
// 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.
- txfn.collectResults(currBlockState.cfgBlock, inputStateCopy);
+ txfn.collectResults(cfg[i], states[i]);
}
}
@@ -96,12 +68,21 @@ inline void MonotoneCFGAnalyzer<L, TxFn>::collectResults() {
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;
- txfn.print(os, state.cfgBlock, temp);
+ for (Index i = 0, size = cfg.size(); i < size; ++i) {
+ os << "CFG Block: " << cfg[i].getIndex() << std::endl;
+ os << "Input State: ";
+ states[i].print(os);
+ for (auto& pred : cfg[i].preds()) {
+ os << " " << pred.getIndex();
+ }
+ os << std::endl << "Successors:";
+ for (auto& succ : cfg[i].succs()) {
+ os << " " << succ.getIndex();
+ }
+ os << "\n";
+ txfn.print(os, cfg[i], states[i]);
}
- os << "End" << std::endl;
+ os << "End\n";
}
} // namespace wasm::analysis