diff options
| -rw-r--r-- | Assembly.cpp | 5 | ||||
| -rw-r--r-- | ControlFlowGraph.cpp | 28 | ||||
| -rw-r--r-- | ControlFlowGraph.h | 14 |
3 files changed, 25 insertions, 22 deletions
diff --git a/Assembly.cpp b/Assembly.cpp index aec06aef..9530ded4 100644 --- a/Assembly.cpp +++ b/Assembly.cpp @@ -318,7 +318,10 @@ Assembly& Assembly::optimise(bool _enable) copt << "Performing control flow analysis..."; { ControlFlowGraph cfg(m_items); - AssemblyItems optItems = cfg.optimisedItems(); + AssemblyItems optItems; + for (BasicBlock const& block: cfg.optimisedBlocks()) + copy(m_items.begin() + block.begin, m_items.begin() + block.end, + back_inserter(optItems)); if (optItems.size() < m_items.size()) { copt << "Old size: " << m_items.size() << ", new size: " << optItems.size(); diff --git a/ControlFlowGraph.cpp b/ControlFlowGraph.cpp index 0b0c757d..2e28317a 100644 --- a/ControlFlowGraph.cpp +++ b/ControlFlowGraph.cpp @@ -38,10 +38,10 @@ BlockId::BlockId(u256 const& _id): m_id(_id) assertThrow( _id < initial().m_id, OptimizerException, "Tag number too large."); } -AssemblyItems ControlFlowGraph::optimisedItems() +BasicBlocks ControlFlowGraph::optimisedBlocks() { if (m_items.empty()) - return m_items; + return BasicBlocks(); findLargestTag(); splitBlocks(); @@ -216,17 +216,17 @@ void ControlFlowGraph::gatherKnowledge() { // @todo actually we know that memory is filled with zeros at the beginning, // we could make use of that. - shared_ptr<KnownState> emptyState = make_shared<KnownState>(); + KnownStatePointer emptyState = make_shared<KnownState>(); ExpressionClasses& expr = emptyState->expressionClasses(); bool unknownJumpEncountered = false; - vector<pair<BlockId, shared_ptr<KnownState>>> workQueue({make_pair(BlockId::initial(), emptyState->copy())}); + vector<pair<BlockId, KnownStatePointer>> workQueue({make_pair(BlockId::initial(), emptyState->copy())}); while (!workQueue.empty()) { //@todo we might have to do something like incrementing the sequence number for each JUMPDEST assertThrow(!!workQueue.back().first, OptimizerException, ""); BasicBlock& block = m_blocks.at(workQueue.back().first); - shared_ptr<KnownState> state = workQueue.back().second; + KnownStatePointer state = workQueue.back().second; workQueue.pop_back(); if (block.startState) { @@ -283,7 +283,7 @@ void ControlFlowGraph::gatherKnowledge() } } -AssemblyItems ControlFlowGraph::rebuildCode() +BasicBlocks ControlFlowGraph::rebuildCode() { map<BlockId, unsigned> pushes; for (auto& idAndBlock: m_blocks) @@ -294,7 +294,7 @@ AssemblyItems ControlFlowGraph::rebuildCode() for (auto it: m_blocks) blocksToAdd.insert(it.first); set<BlockId> blocksAdded; - AssemblyItems code; + BasicBlocks blocks; for ( BlockId blockId = BlockId::initial(); @@ -311,22 +311,18 @@ AssemblyItems ControlFlowGraph::rebuildCode() blocksToAdd.erase(blockId); blocksAdded.insert(blockId); - auto begin = m_items.begin() + block.begin; - auto end = m_items.begin() + block.end; - if (begin == end) + if (block.begin == block.end) continue; // If block starts with unused tag, skip it. - if (previousHandedOver && !pushes[blockId] && begin->type() == Tag) - { - ++begin; + if (previousHandedOver && !pushes[blockId] && m_items[block.begin].type() == Tag) ++block.begin; - } + if (block.begin < block.end) + blocks.push_back(block); previousHandedOver = (block.endType == BasicBlock::EndType::HANDOVER); - copy(begin, end, back_inserter(code)); } } - return code; + return blocks; } BlockId ControlFlowGraph::expressionClassToBlockId( diff --git a/ControlFlowGraph.h b/ControlFlowGraph.h index 4310d664..3366dc45 100644 --- a/ControlFlowGraph.h +++ b/ControlFlowGraph.h @@ -35,6 +35,7 @@ namespace eth { class KnownState; +using KnownStatePointer = std::shared_ptr<KnownState>; /** * Identifier for a block, coincides with the tag number of an AssemblyItem but adds a special @@ -81,19 +82,22 @@ struct BasicBlock /// Knowledge about the state when this block is entered. Intersection of all possible ways /// to enter this block. - std::shared_ptr<KnownState> startState; + KnownStatePointer startState; /// Knowledge about the state at the end of this block. - std::shared_ptr<KnownState> endState; + KnownStatePointer endState; }; +using BasicBlocks = std::vector<BasicBlock>; + class ControlFlowGraph { public: /// Initializes the control flow graph. /// @a _items has to persist across the usage of this class. ControlFlowGraph(AssemblyItems const& _items): m_items(_items) {} - /// @returns the collection of optimised items, should be called only once. - AssemblyItems optimisedItems(); + /// @returns vector of basic blocks in the order they should be used in the final code. + /// Should be called only once. + BasicBlocks optimisedBlocks(); private: void findLargestTag(); @@ -102,7 +106,7 @@ private: void removeUnusedBlocks(); void gatherKnowledge(); void setPrevLinks(); - AssemblyItems rebuildCode(); + BasicBlocks rebuildCode(); /// @returns the corresponding BlockId if _id is a pushed jump tag, /// and an invalid BlockId otherwise. |