1 files changed, 120 insertions, 0 deletions
diff --git a/libevmasm/ControlFlowGraph.h b/libevmasm/ControlFlowGraph.h
new file mode 100644
index 00000000..4480ba49
--- /dev/null
+++ b/libevmasm/ControlFlowGraph.h
@@ -0,0 +1,120 @@
+/*
+	This file is part of cpp-ethereum.
+
+	cpp-ethereum is free software: you can redistribute it and/or modify
+	it under the terms of the GNU General Public License as published by
+	the Free Software Foundation, either version 3 of the License, or
+	(at your option) any later version.
+
+	cpp-ethereum is distributed in the hope that it will be useful,
+	but WITHOUT ANY WARRANTY; without even the implied warranty of
+	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+	GNU General Public License for more details.
+
+	You should have received a copy of the GNU General Public License
+	along with cpp-ethereum.  If not, see <http://www.gnu.org/licenses/>.
+*/
+/**
+ * @file ControlFlowGraph.h
+ * @author Christian <c@ethdev.com>
+ * @date 2015
+ * Control flow analysis for the optimizer.
+ */
+
+#pragma once
+
+#include <vector>
+#include <memory>
+#include <libdevcore/Common.h>
+#include <libdevcore/Assertions.h>
+#include <libevmasm/ExpressionClasses.h>
+
+namespace dev
+{
+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
+ * ID for the inital block.
+ */
+class BlockId
+{
+public:
+	BlockId() { *this = invalid(); }
+	explicit BlockId(unsigned _id): m_id(_id) {}
+	explicit BlockId(u256 const& _id);
+	static BlockId initial() { return BlockId(-2); }
+	static BlockId invalid() { return BlockId(-1); }
+
+	bool operator==(BlockId const& _other) const { return m_id == _other.m_id; }
+	bool operator!=(BlockId const& _other) const { return m_id != _other.m_id; }
+	bool operator<(BlockId const& _other) const { return m_id < _other.m_id; }
+	explicit operator bool() const { return *this != invalid(); }
+
+private:
+	unsigned m_id;
+};
+
+/**
+ * Control flow block inside which instruction counter is always incremented by one
+ * (except for possibly the last instruction).
+ */
+struct BasicBlock
+{
+	/// Start index into assembly item list.
+	unsigned begin = 0;
+	/// End index (excluded) inte assembly item list.
+	unsigned end = 0;
+	/// Tags pushed inside this block, with multiplicity.
+	std::vector<BlockId> pushedTags;
+	/// ID of the block that always follows this one (either non-branching part of JUMPI or flow
+	/// into new block), or BlockId::invalid() otherwise
+	BlockId next = BlockId::invalid();
+	/// ID of the block that has to precede this one (because control flows into it).
+	BlockId prev = BlockId::invalid();
+
+	enum class EndType { JUMP, JUMPI, STOP, HANDOVER };
+	EndType endType = EndType::HANDOVER;
+
+	/// Knowledge about the state when this block is entered. Intersection of all possible ways
+	/// to enter this block.
+	KnownStatePointer startState;
+	/// Knowledge about the state at the end of this block.
+	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 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();
+	void splitBlocks();
+	void resolveNextLinks();
+	void removeUnusedBlocks();
+	void gatherKnowledge();
+	void setPrevLinks();
+	BasicBlocks rebuildCode();
+
+	BlockId generateNewId();
+
+	unsigned m_lastUsedId = 0;
+	AssemblyItems const& m_items;
+	std::map<BlockId, BasicBlock> m_blocks;
+};
+
+
+}
+}