diff options
| -rw-r--r-- | ControlFlowGraph.cpp | 40 | ||||
| -rw-r--r-- | KnownState.cpp | 6 | ||||
| -rw-r--r-- | KnownState.h | 5 |
3 files changed, 33 insertions, 18 deletions
diff --git a/ControlFlowGraph.cpp b/ControlFlowGraph.cpp index 5adb951a..1ad54d8c 100644 --- a/ControlFlowGraph.cpp +++ b/ControlFlowGraph.cpp @@ -221,22 +221,36 @@ void ControlFlowGraph::gatherKnowledge() KnownStatePointer emptyState = make_shared<KnownState>(); bool unknownJumpEncountered = false; - vector<pair<BlockId, KnownStatePointer>> workQueue({make_pair(BlockId::initial(), emptyState->copy())}); + struct WorkQueueItem { + BlockId blockId; + KnownStatePointer state; + set<BlockId> blocksSeen; + }; + + vector<WorkQueueItem> workQueue{WorkQueueItem{BlockId::initial(), emptyState->copy(), set<BlockId>()}}; + auto addWorkQueueItem = [&](WorkQueueItem const& _currentItem, BlockId _to, KnownStatePointer const& _state) + { + WorkQueueItem item; + item.blockId = _to; + item.state = _state->copy(); + item.blocksSeen = _currentItem.blocksSeen; + item.blocksSeen.insert(_currentItem.blockId); + workQueue.push_back(move(item)); + }; + while (!workQueue.empty()) { + WorkQueueItem item = move(workQueue.back()); + workQueue.pop_back(); //@todo we might have to do something like incrementing the sequence number for each JUMPDEST - assertThrow(!!workQueue.back().first, OptimizerException, ""); - if (!m_blocks.count(workQueue.back().first)) - { - workQueue.pop_back(); + assertThrow(!!item.blockId, OptimizerException, ""); + if (!m_blocks.count(item.blockId)) continue; // too bad, we do not know the tag, probably an invalid jump - } - BasicBlock& block = m_blocks.at(workQueue.back().first); - KnownStatePointer state = workQueue.back().second; - workQueue.pop_back(); + BasicBlock& block = m_blocks.at(item.blockId); + KnownStatePointer state = item.state; if (block.startState) { - state->reduceToCommonKnowledge(*block.startState); + state->reduceToCommonKnowledge(*block.startState, !item.blocksSeen.count(item.blockId)); if (*state == *block.startState) continue; } @@ -270,12 +284,12 @@ void ControlFlowGraph::gatherKnowledge() unknownJumpEncountered = true; for (auto const& it: m_blocks) if (it.second.begin < it.second.end && m_items[it.second.begin].type() == Tag) - workQueue.push_back(make_pair(it.first, emptyState->copy())); + workQueue.push_back(WorkQueueItem{it.first, emptyState, set<BlockId>()}); } } else for (auto tag: tags) - workQueue.push_back(make_pair(BlockId(tag), state->copy())); + addWorkQueueItem(item, BlockId(tag), state); } else if (block.begin <= pc && pc < block.end) state->feedItem(m_items.at(pc++)); @@ -287,7 +301,7 @@ void ControlFlowGraph::gatherKnowledge() block.endType == BasicBlock::EndType::HANDOVER || block.endType == BasicBlock::EndType::JUMPI ) - workQueue.push_back(make_pair(block.next, state->copy())); + addWorkQueueItem(item, block.next, state); } // Remove all blocks we never visited here. This might happen because a tag is pushed but diff --git a/KnownState.cpp b/KnownState.cpp index 55e860e2..39cce3e8 100644 --- a/KnownState.cpp +++ b/KnownState.cpp @@ -175,7 +175,7 @@ template <class _Mapping> void intersect(_Mapping& _this, _Mapping const& _other it = _this.erase(it); } -void KnownState::reduceToCommonKnowledge(KnownState const& _other) +void KnownState::reduceToCommonKnowledge(KnownState const& _other, bool _combineSequenceNumbers) { int stackDiff = m_stackHeight - _other.m_stackHeight; for (auto it = m_stackElements.begin(); it != m_stackElements.end();) @@ -213,9 +213,11 @@ void KnownState::reduceToCommonKnowledge(KnownState const& _other) intersect(m_storageContent, _other.m_storageContent); intersect(m_memoryContent, _other.m_memoryContent); + if (_combineSequenceNumbers) + m_sequenceNumber = max(m_sequenceNumber, _other.m_sequenceNumber); } -bool KnownState::operator==(const KnownState& _other) const +bool KnownState::operator==(KnownState const& _other) const { if (m_storageContent != _other.m_storageContent || m_memoryContent != _other.m_memoryContent) return false; diff --git a/KnownState.h b/KnownState.h index 6dff74a5..c1c602dc 100644 --- a/KnownState.h +++ b/KnownState.h @@ -100,13 +100,12 @@ public: void reset() { resetStorage(); resetMemory(); resetStack(); } unsigned sequenceNumber() const { return m_sequenceNumber; } - /// Manually increments the storage and memory sequence number. - void incrementSequenceNumber() { m_sequenceNumber += 2; } /// Replaces the state by the intersection with _other, i.e. only equal knowledge is retained. /// If the stack heighht is different, the smaller one is used and the stack is compared /// relatively. - void reduceToCommonKnowledge(KnownState const& _other); + /// @param _combineSequenceNumbers if true, sets the sequence number to the maximum of both + void reduceToCommonKnowledge(KnownState const& _other, bool _combineSequenceNumbers); /// @returns a shared pointer to a copy of this state. std::shared_ptr<KnownState> copy() const { return std::make_shared<KnownState>(*this); } |