Fix sequence number bug.

This bug resulted in incorrect storage access in some situations.
The reason was that when intersecting states, the sequence numbers
were not handled and thus some operations with too low
sequence numbers were used during code generation.

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); }