Merge pull request #1429 from ethereum/unreachablepeephole

Some dead code elimination

4 files changed, 179 insertions, 67 deletions

diff --git a/Changelog.md b/Changelog.md
index 0b10cd0c..b5e48173 100644
--- a/Changelog.md
+++ b/Changelog.md
@@ -1,5 +1,8 @@
 ### 0.4.7 (unreleased)
 
+Features:
+ * Optimizer: Some dead code elimination.
+
 Bugfixes:
  * Type checker: string literals that are not valid UTF-8 cannot be converted to string type
 
diff --git a/libevmasm/Assembly.cpp b/libevmasm/Assembly.cpp
index 96306750..edbb9828 100644
--- a/libevmasm/Assembly.cpp
+++ b/libevmasm/Assembly.cpp
@@ -337,7 +337,7 @@ map<u256, u256> Assembly::optimiseInternal(bool _enable, bool _isCreation, size_
 		count = 0;
 
 		PeepholeOptimiser peepOpt(m_items);
-		if (peepOpt.optimise())
+		while (peepOpt.optimise())
 			count++;
 
 		if (!_enable)
diff --git a/libevmasm/PeepholeOptimiser.cpp b/libevmasm/PeepholeOptimiser.cpp
index 901e310e..b96b0295 100644
--- a/libevmasm/PeepholeOptimiser.cpp
+++ b/libevmasm/PeepholeOptimiser.cpp
@@ -30,51 +30,96 @@ using namespace dev;
 
 // TODO: Extend this to use the tools from ExpressionClasses.cpp
 
-struct Identity
+struct OptimiserState
+{
+	AssemblyItems const& items;
+	size_t i;
+	std::back_insert_iterator<AssemblyItems> out;
+};
+
+template <class Method, size_t Arguments>
+struct ApplyRule
 {
-	static size_t windowSize() { return 1; }
-	static bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems> _out)
+};
+template <class Method>
+struct ApplyRule<Method, 3>
+{
+	static bool applyRule(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems> _out)
 	{
-		*_out = *_in;
-		return true;
+		return Method::applySimple(_in[0], _in[1], _in[2], _out);
+	}
+};
+template <class Method>
+struct ApplyRule<Method, 2>
+{
+	static bool applyRule(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems> _out)
+	{
+		return Method::applySimple(_in[0], _in[1], _out);
+	}
+};
+template <class Method>
+struct ApplyRule<Method, 1>
+{
+	static bool applyRule(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems> _out)
+	{
+		return Method::applySimple(_in[0], _out);
 	}
 };
 
-struct PushPop
+template <class Method, size_t WindowSize>
+struct SimplePeepholeOptimizerMethod
 {
-	static size_t windowSize() { return 2; }
-	static bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems>)
+	static bool apply(OptimiserState& _state)
 	{
-		auto t = _in[0].type();
-		if (_in[1] == Instruction::POP && (
-			SemanticInformation::isDupInstruction(_in[0]) ||
-			t == Push || t == PushString || t == PushTag || t == PushSub ||
-			t == PushSubSize || t == PushProgramSize || t == PushData || t == PushLibraryAddress
-		))
+		if (
+			_state.i + WindowSize <= _state.items.size() &&
+			ApplyRule<Method, WindowSize>::applyRule(_state.items.begin() + _state.i, _state.out)
+		)
+		{
+			_state.i += WindowSize;
 			return true;
+		}
 		else
 			return false;
 	}
 };
 
-struct AddPop
+struct Identity: SimplePeepholeOptimizerMethod<Identity, 1>
 {
-	static size_t windowSize() { return 2; }
-	static bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems> _out)
+	static bool applySimple(AssemblyItem const& _item, std::back_insert_iterator<AssemblyItems> _out)
 	{
-		if (_in[1] == Instruction::POP &&
-			_in[0].type() == Operation
-		)
+		*_out = _item;
+		return true;
+	}
+};
+
+struct PushPop: SimplePeepholeOptimizerMethod<PushPop, 2>
+{
+	static bool applySimple(AssemblyItem const& _push, AssemblyItem const& _pop, std::back_insert_iterator<AssemblyItems>)
+	{
+		auto t = _push.type();
+		return _pop == Instruction::POP && (
+			SemanticInformation::isDupInstruction(_push) ||
+			t == Push || t == PushString || t == PushTag || t == PushSub ||
+			t == PushSubSize || t == PushProgramSize || t == PushData || t == PushLibraryAddress
+		);
+	}
+};
+
+struct OpPop: SimplePeepholeOptimizerMethod<OpPop, 2>
+{
+	static bool applySimple(
+		AssemblyItem const& _op,
+		AssemblyItem const& _pop,
+		std::back_insert_iterator<AssemblyItems> _out
+	)
+	{
+		if (_pop == Instruction::POP && _op.type() == Operation)
 		{
-			Instruction i0 = _in[0].instruction();
-			if (instructionInfo(i0).ret == 1 &&
-				!SemanticInformation::invalidatesMemory(i0) &&
-				!SemanticInformation::invalidatesStorage(i0) &&
-				!SemanticInformation::altersControlFlow(i0) &&
-				!instructionInfo(i0).sideEffects
-			)
+			Instruction instr = _op.instruction();
+			if (instructionInfo(instr).ret == 1 && !instructionInfo(instr).sideEffects)
 			{
-				for (int j = 0; j < instructionInfo(i0).args; j++)
+				for (int j = 0; j < instructionInfo(instr).args; j++)
 					*_out = Instruction::POP;
 				return true;
 			}
@@ -83,33 +128,33 @@ struct AddPop
 	}
 };
 
-struct DoubleSwap
+struct DoubleSwap: SimplePeepholeOptimizerMethod<DoubleSwap, 2>
 {
-	static size_t windowSize() { return 2; }
-	static bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems>)
+	static size_t applySimple(AssemblyItem const& _s1, AssemblyItem const& _s2, std::back_insert_iterator<AssemblyItems>)
 	{
-		if (_in[0] == _in[1] && SemanticInformation::isSwapInstruction(_in[0]))
-			return true;
-		else
-			return false;
+		return _s1 == _s2 && SemanticInformation::isSwapInstruction(_s1);
 	}
 };
 
-struct JumpToNext
+struct JumpToNext: SimplePeepholeOptimizerMethod<JumpToNext, 3>
 {
-	static size_t windowSize() { return 3; }
-	static bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems> _out)
+	static size_t applySimple(
+		AssemblyItem const& _pushTag,
+		AssemblyItem const& _jump,
+		AssemblyItem const& _tag,
+		std::back_insert_iterator<AssemblyItems> _out
+	)
 	{
 		if (
-			_in[0].type() == PushTag &&
-			(_in[1] == Instruction::JUMP || _in[1] == Instruction::JUMPI) &&
-			_in[2].type() == Tag &&
-			_in[0].data() == _in[2].data()
+			_pushTag.type() == PushTag &&
+			(_jump == Instruction::JUMP || _jump == Instruction::JUMPI) &&
+			_tag.type() == Tag &&
+			_pushTag.data() == _tag.data()
 		)
 		{
-			if (_in[1] == Instruction::JUMPI)
-				*_out = AssemblyItem(Instruction::POP, _in[1].location());
-			*_out = _in[2];
+			if (_jump == Instruction::JUMPI)
+				*_out = AssemblyItem(Instruction::POP, _jump.location());
+			*_out = _tag;
 			return true;
 		}
 		else
@@ -117,19 +162,23 @@ struct JumpToNext
 	}
 };
 
-struct TagConjunctions
+struct TagConjunctions: SimplePeepholeOptimizerMethod<TagConjunctions, 3>
 {
-	static size_t windowSize() { return 3; }
-	static bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems> _out)
+	static bool applySimple(
+		AssemblyItem const& _pushTag,
+		AssemblyItem const& _pushConstant,
+		AssemblyItem const& _and,
+		std::back_insert_iterator<AssemblyItems> _out
+	)
 	{
 		if (
-			_in[0].type() == PushTag &&
-			_in[2] == Instruction::AND &&
-			_in[1].type() == Push &&
-			(_in[1].data() & u256(0xFFFFFFFF)) == u256(0xFFFFFFFF)
+			_pushTag.type() == PushTag &&
+			_and == Instruction::AND &&
+			_pushConstant.type() == Push &&
+			(_pushConstant.data() & u256(0xFFFFFFFF)) == u256(0xFFFFFFFF)
 		)
 		{
-			*_out = _in[0];
+			*_out = _pushTag;
 			return true;
 		}
 		else
@@ -137,11 +186,35 @@ struct TagConjunctions
 	}
 };
 
-struct OptimiserState
+/// Removes everything after a JUMP (or similar) until the next JUMPDEST.
+struct UnreachableCode
 {
-	AssemblyItems const& items;
-	size_t i;
-	std::back_insert_iterator<AssemblyItems> out;
+	static bool apply(OptimiserState& _state)
+	{
+		auto it = _state.items.begin() + _state.i;
+		auto end = _state.items.end();
+		if (it == end)
+			return false;
+		if (
+			it[0] != Instruction::JUMP &&
+			it[0] != Instruction::RETURN &&
+			it[0] != Instruction::STOP &&
+			it[0] != Instruction::SUICIDE
+		)
+			return false;
+
+		size_t i = 1;
+		while (it + i != end && it[i].type() != Tag)
+			i++;
+		if (i > 1)
+		{
+			*_state.out = it[0];
+			_state.i += i;
+			return true;
+		}
+		else
+			return false;
+	}
 };
 
 void applyMethods(OptimiserState&)
@@ -152,9 +225,7 @@ void applyMethods(OptimiserState&)
 template <typename Method, typename... OtherMethods>
 void applyMethods(OptimiserState& _state, Method, OtherMethods... _other)
 {
-	if (_state.i + Method::windowSize() <= _state.items.size() && Method::apply(_state.items.begin() + _state.i, _state.out))
-		_state.i += Method::windowSize();
-	else
+	if (!Method::apply(_state))
 		applyMethods(_state, _other...);
 }
 
@@ -162,7 +233,7 @@ bool PeepholeOptimiser::optimise()
 {
 	OptimiserState state {m_items, 0, std::back_inserter(m_optimisedItems)};
 	while (state.i < m_items.size())
-		applyMethods(state, PushPop(), AddPop(), DoubleSwap(), JumpToNext(), TagConjunctions(), Identity());
+		applyMethods(state, PushPop(), OpPop(), DoubleSwap(), JumpToNext(), UnreachableCode(), TagConjunctions(), Identity());
 	if (m_optimisedItems.size() < m_items.size())
 	{
 		m_items = std::move(m_optimisedItems);
diff --git a/test/libsolidity/SolidityOptimizer.cpp b/test/libsolidity/SolidityOptimizer.cpp
index ecb44272..a53a2638 100644
--- a/test/libsolidity/SolidityOptimizer.cpp
+++ b/test/libsolidity/SolidityOptimizer.cpp
@@ -20,17 +20,21 @@
  * Tests for the Solidity optimizer.
  */
 
-#include <string>
-#include <tuple>
-#include <memory>
-#include <boost/test/unit_test.hpp>
-#include <boost/lexical_cast.hpp>
 #include <test/libsolidity/SolidityExecutionFramework.h>
+
 #include <libevmasm/CommonSubexpressionEliminator.h>
+#include <libevmasm/PeepholeOptimiser.h>
 #include <libevmasm/ControlFlowGraph.h>
 #include <libevmasm/Assembly.h>
 #include <libevmasm/BlockDeduplicator.h>
 
+#include <boost/test/unit_test.hpp>
+#include <boost/lexical_cast.hpp>
+
+#include <string>
+#include <tuple>
+#include <memory>
+
 using namespace std;
 using namespace dev::eth;
 
@@ -1121,6 +1125,40 @@ BOOST_AUTO_TEST_CASE(block_deduplicator_loops)
 	BOOST_CHECK_EQUAL(pushTags.size(), 1);
 }
 
+BOOST_AUTO_TEST_CASE(clear_unreachable_code)
+{
+	AssemblyItems items{
+		AssemblyItem(PushTag, 1),
+		Instruction::JUMP,
+		u256(0),
+		Instruction::SLOAD,
+		AssemblyItem(Tag, 2),
+		u256(5),
+		u256(6),
+		Instruction::SSTORE,
+		AssemblyItem(PushTag, 1),
+		Instruction::JUMP,
+		u256(5),
+		u256(6)
+	};
+	AssemblyItems expectation{
+		AssemblyItem(PushTag, 1),
+		Instruction::JUMP,
+		AssemblyItem(Tag, 2),
+		u256(5),
+		u256(6),
+		Instruction::SSTORE,
+		AssemblyItem(PushTag, 1),
+		Instruction::JUMP
+	};
+	PeepholeOptimiser peepOpt(items);
+	BOOST_REQUIRE(peepOpt.optimise());
+	BOOST_CHECK_EQUAL_COLLECTIONS(
+		items.begin(), items.end(),
+		expectation.begin(), expectation.end()
+	);
+}
+
 BOOST_AUTO_TEST_CASE(computing_constants)
 {
 	char const* sourceCode = R"(