From fd9d04ccd615b185e65a765e3587eae3f72aa867 Mon Sep 17 00:00:00 2001 From: Bruce He <44327446+zm2he@users.noreply.github.com> Date: Fri, 23 Jun 2023 22:56:48 +0000 Subject: Liveness Analysis Proof of Concept (#5771) This introduces a limited monotone flow-sensitive liveness analysis on local indices as an initial proof of concept for the creation of a monotone flow-sensitive static analysis framework. Tests are included in test/gtest/cfg.cpp. --- src/analysis/CMakeLists.txt | 1 + src/analysis/cfg.h | 6 ++ src/analysis/lattice.h | 57 +++++++++++++ src/analysis/monotone-analyzer-impl.h | 153 ++++++++++++++++++++++++++++++++++ src/analysis/monotone-analyzer.h | 77 +++++++++++++++++ src/analysis/powerset-lattice-impl.h | 67 +++++++++++++++ src/analysis/sign-lattice.cpp | 49 +++++++++++ 7 files changed, 410 insertions(+) create mode 100644 src/analysis/lattice.h create mode 100644 src/analysis/monotone-analyzer-impl.h create mode 100644 src/analysis/monotone-analyzer.h create mode 100644 src/analysis/powerset-lattice-impl.h create mode 100644 src/analysis/sign-lattice.cpp (limited to 'src') diff --git a/src/analysis/CMakeLists.txt b/src/analysis/CMakeLists.txt index ea0494859..2fc4be305 100644 --- a/src/analysis/CMakeLists.txt +++ b/src/analysis/CMakeLists.txt @@ -1,6 +1,7 @@ file(GLOB analysis_HEADERS *.h) set(analysis_SOURCES cfg.cpp + sign-lattice.cpp ${analysis_HEADERS} ) add_library(analysis OBJECT ${analysis_SOURCES}) diff --git a/src/analysis/cfg.h b/src/analysis/cfg.h index ba4d7a774..c14cf70f4 100644 --- a/src/analysis/cfg.h +++ b/src/analysis/cfg.h @@ -40,6 +40,10 @@ struct BasicBlock { iterator end() const { return insts.cend(); } size_t size() const { return insts.size(); } + using reverse_iterator = std::vector::const_reverse_iterator; + reverse_iterator rbegin() const { return insts.rbegin(); } + reverse_iterator rend() const { return insts.rend(); } + // Iterables for predecessor and successor blocks. struct Predecessors; struct Successors; @@ -48,6 +52,8 @@ struct BasicBlock { void print(std::ostream& os, Module* wasm = nullptr, size_t start = 0) const; + Index getIndex() const { return index; } + private: Index index; std::vector insts; diff --git a/src/analysis/lattice.h b/src/analysis/lattice.h new file mode 100644 index 000000000..bad11284f --- /dev/null +++ b/src/analysis/lattice.h @@ -0,0 +1,57 @@ +#ifndef wasm_analysis_lattice_h +#define wasm_analysis_lattice_h + +#include "wasm.h" +#include +#include + +namespace wasm::analysis { + +enum LatticeComparison { NO_RELATION, EQUAL, LESS, GREATER }; + +template +constexpr bool has_compare = std::is_invocable_r::value; +template +constexpr bool has_getLeastUpperBound = std:: + is_invocable_r::value; +template +constexpr bool has_isTop = + std::is_invocable_r::value; +template +constexpr bool has_isBottom = + std::is_invocable_r::value; + +template +constexpr bool is_lattice = + has_compare&& has_getLeastUpperBound&& has_isTop&& has_isBottom; + +// Represents a powerset lattice element (i.e. a set) as a bitvector. A true +// means that an element is present in the set. +template struct BitsetPowersetLattice { + std::bitset value; + + static BitsetPowersetLattice getBottom(); + static bool isTop(const BitsetPowersetLattice& element); + static bool isBottom(const BitsetPowersetLattice& element); + + // Compares two lattice elements and returns a result indicating the + // left element's relation to the right element. + static LatticeComparison compare(const BitsetPowersetLattice& left, + const BitsetPowersetLattice& right); + + // Calculates the LUB of this current (left) lattice element with some right + // element. It then updates this current lattice element to the LUB in place. + void getLeastUpperBound(const BitsetPowersetLattice& right); + + // Prints out the bits in the bitvector for a lattice element. + void print(std::ostream& os); +}; + +} // namespace wasm::analysis + +#include "powerset-lattice-impl.h" + +#endif // wasm_analysis_lattice_h diff --git a/src/analysis/monotone-analyzer-impl.h b/src/analysis/monotone-analyzer-impl.h new file mode 100644 index 000000000..61cd2ad0e --- /dev/null +++ b/src/analysis/monotone-analyzer-impl.h @@ -0,0 +1,153 @@ +#ifndef wasm_analysis_monotone_analyzer_impl_h +#define wasm_analysis_monotone_analyzer_impl_h + +#include +#include + +#include "monotone-analyzer.h" + +namespace wasm::analysis { +template +inline BlockState::BlockState(const BasicBlock* underlyingBlock) + : index(underlyingBlock->getIndex()), cfgBlock(underlyingBlock), + beginningState(BitsetPowersetLattice::getBottom()), + endState(BitsetPowersetLattice::getBottom()), + currState(BitsetPowersetLattice::getBottom()) {} + +template inline void BlockState::addPredecessor(BlockState* pred) { + predecessors.push_back(pred); +} + +template inline void BlockState::addSuccessor(BlockState* succ) { + successors.push_back(succ); +} + +template +inline BitsetPowersetLattice& BlockState::getFirstState() { + return beginningState; +} + +template +inline BitsetPowersetLattice& BlockState::getLastState() { + return endState; +} + +// In our current limited implementation, we just update a new live variable +// when it it is used in a get or set. +template inline void BlockState::visitLocalSet(LocalSet* curr) { + currState.value[curr->index] = false; +} + +template inline void BlockState::visitLocalGet(LocalGet* curr) { + currState.value[curr->index] = true; +} + +template inline void BlockState::transfer() { + // If the block is empty, we propagate the state by endState = currState, then + // currState = beginningState + + // compute transfer function for all expressions in the CFG block + auto cfgIter = cfgBlock->rbegin(); + currState = endState; + + while (cfgIter != cfgBlock->rend()) { + // run transfer function. + BlockState::visit(*cfgIter); + ++cfgIter; + } + beginningState = currState; +} + +template inline void BlockState::print(std::ostream& os) { + os << "State Block: " << index << std::endl; + os << "State at beginning: "; + beginningState.print(os); + os << std::endl << "State at end: "; + endState.print(os); + os << std::endl << "Intermediate States (reverse order): " << std::endl; + + currState = endState; + currState.print(os); + os << std::endl; + auto cfgIter = cfgBlock->rbegin(); + + while (cfgIter != cfgBlock->rend()) { + // run transfer function. + os << ShallowExpression{*cfgIter} << std::endl; + BlockState::visit(*cfgIter); + currState.print(os); + os << std::endl; + ++cfgIter; + } +} + +template +MonotoneCFGAnalyzer inline MonotoneCFGAnalyzer::fromCFG(CFG* cfg) { + MonotoneCFGAnalyzer result; + + // Map BasicBlocks to each BlockState's index + std::unordered_map basicBlockToState; + size_t index = 0; + for (auto it = cfg->begin(); it != cfg->end(); it++) { + result.stateBlocks.emplace_back(&(*it)); + basicBlockToState[&(*it)] = index++; + } + + // Update predecessors and successors of each BlockState object + // according to the BasicBlock's predecessors and successors. + for (index = 0; index < result.stateBlocks.size(); ++index) { + BlockState& currBlock = result.stateBlocks.at(index); + BasicBlock::Predecessors preds = currBlock.cfgBlock->preds(); + BasicBlock::Successors succs = currBlock.cfgBlock->succs(); + for (auto pred : preds) { + currBlock.addPredecessor(&result.stateBlocks[basicBlockToState[&pred]]); + } + + for (auto succ : succs) { + currBlock.addSuccessor(&result.stateBlocks[basicBlockToState[&succ]]); + } + } + + return result; +} + +template inline void MonotoneCFGAnalyzer::evaluate() { + std::queue worklist; + + for (auto it = stateBlocks.rbegin(); it != stateBlocks.rend(); ++it) { + worklist.push(it->index); + } + + while (!worklist.empty()) { + BlockState& currBlockState = stateBlocks[worklist.front()]; + worklist.pop(); + currBlockState.transfer(); + + // Propagate state to dependents + for (size_t j = 0; j < currBlockState.predecessors.size(); ++j) { + BitsetPowersetLattice& predLast = + currBlockState.predecessors[j]->getLastState(); + + LatticeComparison cmp = BitsetPowersetLattice::compare( + predLast, currBlockState.getFirstState()); + + if (cmp == LatticeComparison::NO_RELATION || + cmp == LatticeComparison::LESS) { + predLast.getLeastUpperBound(currBlockState.getFirstState()); + worklist.push(currBlockState.predecessors[j]->index); + } + } + } +} + +template inline void MonotoneCFGAnalyzer::print(std::ostream& os) { + os << "CFG Analyzer" << std::endl; + for (auto state : stateBlocks) { + state.print(os); + } + os << "End" << std::endl; +} + +} // namespace wasm::analysis + +#endif // wasm_analysis_monotone_analyzer_impl_h diff --git a/src/analysis/monotone-analyzer.h b/src/analysis/monotone-analyzer.h new file mode 100644 index 000000000..dfe6143d5 --- /dev/null +++ b/src/analysis/monotone-analyzer.h @@ -0,0 +1,77 @@ +#ifndef wasm_analysis_monotone_analyzer_h +#define wasm_analysis_monotone_analyzer_h + +#include +#include +#include + +#include "cfg.h" +#include "lattice.h" +#include "wasm-traversal.h" + +namespace wasm::analysis { + +template struct MonotoneCFGAnalyzer; + +// A node which contains all the lattice states for a given CFG node. +template struct BlockState : public Visitor> { + static_assert(is_lattice>); + BlockState(const BasicBlock* underlyingBlock); + + void addPredecessor(BlockState* pred); + void addSuccessor(BlockState* succ); + + BitsetPowersetLattice& getFirstState(); + BitsetPowersetLattice& getLastState(); + + // Transfer function implementation. Modifies the state for a particular + // expression type. + void visitLocalSet(LocalSet* curr); + void visitLocalGet(LocalGet* curr); + + // Executes the transfer function on all the expressions of the corresponding + // CFG and then propagates the state to all predecessors (which depend on the + // current node). + void transfer(); + + // prints out all states. + void print(std::ostream& os); + +private: + // The index of the block is same as the CFG index. + Index index; + const BasicBlock* cfgBlock; + // State at beginning of CFG node. + BitsetPowersetLattice beginningState; + // State at the end of the CFG node. + BitsetPowersetLattice endState; + // Holds intermediate state values. + BitsetPowersetLattice currState; + std::vector predecessors; + std::vector successors; + + friend MonotoneCFGAnalyzer; +}; + +template struct MonotoneCFGAnalyzer { + static_assert(is_lattice>); + + // Constructs a graph of BlockState objects which parallels + // the CFG graph. Each CFG node corresponds to a BlockState node. + static MonotoneCFGAnalyzer fromCFG(CFG* cfg); + + // Runs the worklist algorithm to compute the states for the BlockList graph. + void evaluate(); + + void print(std::ostream& os); + +private: + std::vector> stateBlocks; + friend BlockState; +}; + +} // namespace wasm::analysis + +#include "monotone-analyzer-impl.h" + +#endif // wasm_analysis_monotone_analyzer_h diff --git a/src/analysis/powerset-lattice-impl.h b/src/analysis/powerset-lattice-impl.h new file mode 100644 index 000000000..6207c2bec --- /dev/null +++ b/src/analysis/powerset-lattice-impl.h @@ -0,0 +1,67 @@ +#ifndef wasm_analysis_lattice_impl_h +#define wasm_analysis_lattice_impl_h + +#include "lattice.h" + +namespace wasm::analysis { + +template +inline BitsetPowersetLattice BitsetPowersetLattice::getBottom() { + // Return the empty set as the bottom lattice element. + BitsetPowersetLattice result{0}; + return result; +} + +template +inline bool +BitsetPowersetLattice::isTop(const BitsetPowersetLattice& element) { + // Top lattice element is the set containing all possible elements. + return element.value.all(); +} + +template +inline bool +BitsetPowersetLattice::isBottom(const BitsetPowersetLattice& element) { + // Bottom lattice element is the empty set. + return element.value.none(); +} + +template +inline LatticeComparison +BitsetPowersetLattice::compare(const BitsetPowersetLattice& left, + const BitsetPowersetLattice& right) { + size_t leftCount = left.value.count(); + size_t rightCount = right.value.count(); + + // If left has more elements, left might be a superset of right. + if (leftCount > rightCount) { + if ((left.value | right.value) == left.value) { + return GREATER; + } + // If right has more elements, right might be a superset of left. + } else if (leftCount < rightCount) { + if ((left.value | right.value) == right.value) { + return LESS; + } + } else if (left.value == right.value) { + return EQUAL; + } + + return NO_RELATION; +} + +// Implement LUB as an OR of the two bitsets. +template +inline void BitsetPowersetLattice::getLeastUpperBound( + const BitsetPowersetLattice& right) { + value |= right.value; +} + +template +inline void BitsetPowersetLattice::print(std::ostream& os) { + os << value; +} + +}; // namespace wasm::analysis + +#endif // wasm_analysis_lattice_impl_h diff --git a/src/analysis/sign-lattice.cpp b/src/analysis/sign-lattice.cpp new file mode 100644 index 000000000..9baa2f2fd --- /dev/null +++ b/src/analysis/sign-lattice.cpp @@ -0,0 +1,49 @@ +#include "lattice.h" +#include + +namespace wasm::analysis { + +struct SignLattice { +public: + enum Sign { BOTTOM, NEGATIVE, ZERO, POSITIVE, TOP }; + +private: + Sign value; + +public: + static bool isTop(const SignLattice& element) { return element.value == TOP; } + + static bool isBottom(const SignLattice& element) { + return element.value == BOTTOM; + } + + static LatticeComparison compare(const SignLattice& left, + const SignLattice& right) { + if (left.value == right.value) { + return EQUAL; + } else if (left.value == BOTTOM || right.value == TOP) { + return LESS; + } else if (left.value == TOP || right.value == BOTTOM) { + return GREATER; + } else { + return NO_RELATION; + } + } + + // Modifies the left lattice element to the least upper bound between + // it and the right hand lattice element in-place. Returns true + // if the left lattice element has been changed. + void getLeastUpperBound(const SignLattice& right) { + if (value == right.value || value == TOP || right.value == BOTTOM) { + return; + } else if (value == BOTTOM || right.value == TOP) { + value = right.value; + } else { + value = TOP; + } + } +}; + +static_assert(is_lattice); + +} // namespace wasm::analysis -- cgit v1.2.3