From eb185f5d0706927db5917bf111afa73c6989b249 Mon Sep 17 00:00:00 2001 From: Bruce He <44327446+zm2he@users.noreply.github.com> Date: Thu, 6 Jul 2023 20:02:07 +0000 Subject: Make the Transfer Function a Generic, Interchangeable Type for the Monotone Analyzer (#5794) This change makes the transfer function an object separate from the monotone analyzer. The transfer function class type is a generic template of the monotone analyzer, and an instance of the transfer function is instantiated and then passed into the monotone analyzer via its constructor. The API of the transfer function is enforced by a static assertion. This change also introduces LivenessTransferFunction as a transfer function for liveness analysis as an example. --- src/analysis/monotone-analyzer-impl.h | 135 ++++++++++------------------------ 1 file changed, 40 insertions(+), 95 deletions(-) (limited to 'src/analysis/monotone-analyzer-impl.h') diff --git a/src/analysis/monotone-analyzer-impl.h b/src/analysis/monotone-analyzer-impl.h index a2e059e29..471dc62f6 100644 --- a/src/analysis/monotone-analyzer-impl.h +++ b/src/analysis/monotone-analyzer-impl.h @@ -13,132 +13,77 @@ namespace wasm::analysis { template inline BlockState::BlockState(const BasicBlock* underlyingBlock, Lattice& lattice) - : index(underlyingBlock->getIndex()), cfgBlock(underlyingBlock), - beginningState(lattice.getBottom()), endState(lattice.getBottom()), - currState(lattice.getBottom()) {} - -// In our current limited implementation, we just update state on gets -// and sets of local indices. -template -inline void BlockState::visitLocalSet(LocalSet* curr) { - currState.set(curr->index, false); -} - -template -inline void BlockState::visitLocalGet(LocalGet* curr) { - currState.set(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 = std::move(currState); -} + : cfgBlock(underlyingBlock), inputState(lattice.getBottom()) {} +// Prints out inforamtion about a CFG node's state, but not intermediate states. template inline void BlockState::print(std::ostream& os) { - os << "State Block: " << index << std::endl; - os << "Beginning State: "; - beginningState.print(os); - os << std::endl << "End State: "; - endState.print(os); + os << "CFG Block: " << cfgBlock->getIndex() << std::endl; + os << "Input State: "; + inputState.print(os); os << std::endl << "Predecessors:"; - for (auto pred : predecessors) { - os << " " << pred->cfgBlock->getIndex(); + for (auto pred : cfgBlock->preds()) { + os << " " << pred.getIndex(); } os << std::endl << "Successors:"; - for (auto succ : successors) { - os << " " << succ->cfgBlock->getIndex(); + for (auto succ : cfgBlock->succs()) { + os << " " << succ.getIndex(); } - os << std::endl << "Intermediate States (reverse order): " << std::endl; - - currState = endState; - currState.print(os); os << std::endl; - auto cfgIter = cfgBlock->rbegin(); - - // Since we don't store the intermediate states in the BlockState, we need to - // re-run the transfer function on all the CFG node expressions to reconstruct - // the intermediate states here. - while (cfgIter != cfgBlock->rend()) { - os << ShallowExpression{*cfgIter} << std::endl; - BlockState::visit(*cfgIter); - currState.print(os); - os << std::endl; - ++cfgIter; - } } -template -inline void MonotoneCFGAnalyzer::fromCFG(CFG* cfg) { - // Construct BlockStates for each BasicBlock and map each BasicBlock to each - // BlockState's index in stateBlocks. - std::unordered_map basicBlockToState; - size_t index = 0; - for (auto it = cfg->begin(); it != cfg->end(); it++) { - stateBlocks.emplace_back(&(*it), lattice); - basicBlockToState[&(*it)] = index++; - } - - // Update predecessors and successors of each BlockState object - // according to the BasicBlock's predecessors and successors. - for (index = 0; index < stateBlocks.size(); ++index) { - BlockState& currBlock = stateBlocks.at(index); - BasicBlock::Predecessors preds = currBlock.cfgBlock->preds(); - BasicBlock::Successors succs = currBlock.cfgBlock->succs(); - for (auto& pred : preds) { - currBlock.predecessors.push_back(&stateBlocks[basicBlockToState[&pred]]); - } +template +inline MonotoneCFGAnalyzer::MonotoneCFGAnalyzer( + Lattice& lattice, TransferFunction& transferFunction, CFG& cfg) + : lattice(lattice), transferFunction(transferFunction), cfg(cfg) { - for (auto& succ : succs) { - currBlock.successors.push_back(&stateBlocks[basicBlockToState[&succ]]); - } + // Construct BlockStates for each BasicBlock. + for (auto it = cfg.begin(); it != cfg.end(); it++) { + stateBlocks.emplace_back(&(*it), lattice); } } -template -inline void MonotoneCFGAnalyzer::evaluate() { - std::queue worklist; +template +inline void MonotoneCFGAnalyzer::evaluate() { + std::queue worklist; - for (auto it = stateBlocks.rbegin(); it != stateBlocks.rend(); ++it) { - worklist.push(it->index); - } + // Transfer function enqueues the work in some order which is efficient. + transferFunction.enqueueWorklist(cfg, worklist); while (!worklist.empty()) { - BlockState& currBlockState = stateBlocks[worklist.front()]; + BlockState& 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. - currBlockState.transfer(); - - // Propagate state to dependents - for (size_t j = 0; j < currBlockState.predecessors.size(); ++j) { - if (currBlockState.predecessors[j]->getLastState().makeLeastUpperBound( - currBlockState.getFirstState())) { - worklist.push(currBlockState.predecessors[j]->index); + typename Lattice::Element outputState = currBlockState.inputState; + transferFunction.transfer(currBlockState.cfgBlock, outputState); + + // Propagate state to dependents of currBlockState. + for (auto& dep : transferFunction.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); } } } } -template -inline void MonotoneCFGAnalyzer::print(std::ostream& os) { +// Currently prints both the basic information and intermediate states of each +// BlockState. +template +inline void +MonotoneCFGAnalyzer::print(std::ostream& os) { os << "CFG Analyzer" << std::endl; for (auto state : stateBlocks) { state.print(os); + typename Lattice::Element temp = state.inputState; + transferFunction.print(os, state.cfgBlock, temp); } os << "End" << std::endl; } -- cgit v1.2.3