Simple peephole optimizer that is activated even if not requested.

6 files changed, 226 insertions, 17 deletions

diff --git a/libevmasm/Assembly.cpp b/libevmasm/Assembly.cpp
index 0ee3f421..a813a3a7 100644
--- a/libevmasm/Assembly.cpp
+++ b/libevmasm/Assembly.cpp
@@ -20,13 +20,17 @@
  */
 
 #include "Assembly.h"
-#include <fstream>
+
 #include <libevmasm/CommonSubexpressionEliminator.h>
 #include <libevmasm/ControlFlowGraph.h>
+#include <libevmasm/PeepholeOptimiser.h>
 #include <libevmasm/BlockDeduplicator.h>
 #include <libevmasm/ConstantOptimiser.h>
 #include <libevmasm/GasMeter.h>
+
+#include <fstream>
 #include <json/json.h>
+
 using namespace std;
 using namespace dev;
 using namespace dev::eth;
@@ -314,16 +318,15 @@ void Assembly::injectStart(AssemblyItem const& _i)
 
 Assembly& Assembly::optimise(bool _enable, bool _isCreation, size_t _runs)
 {
-	if (_enable)
-		optimiseInternal(_isCreation, _runs);
+	optimiseInternal(_enable, _isCreation, _runs);
 	return *this;
 }
 
-map<u256, u256> Assembly::optimiseInternal(bool _isCreation, size_t _runs)
+map<u256, u256> Assembly::optimiseInternal(bool _enable, bool _isCreation, size_t _runs)
 {
 	for (size_t subId = 0; subId < m_subs.size(); ++subId)
 	{
-		map<u256, u256> subTagReplacements = m_subs[subId]->optimiseInternal(false, _runs);
+		map<u256, u256> subTagReplacements = m_subs[subId]->optimiseInternal(_enable, false, _runs);
 		BlockDeduplicator::applyTagReplacement(m_items, subTagReplacements, subId);
 	}
 
@@ -333,6 +336,13 @@ map<u256, u256> Assembly::optimiseInternal(bool _isCreation, size_t _runs)
 	{
 		count = 0;
 
+		PeepholeOptimiser peepOpt(m_items);
+		if (peepOpt.optimise())
+			count++;
+
+		if (!_enable)
+			continue;
+
 		// This only modifies PushTags, we have to run again to actually remove code.
 		BlockDeduplicator dedup(m_items);
 		if (dedup.deduplicate())
@@ -399,12 +409,13 @@ map<u256, u256> Assembly::optimiseInternal(bool _isCreation, size_t _runs)
 		}
 	}
 
-	total += ConstantOptimisationMethod::optimiseConstants(
-		_isCreation,
-		_isCreation ? 1 : _runs,
-		*this,
-		m_items
-	);
+	if (_enable)
+		total += ConstantOptimisationMethod::optimiseConstants(
+			_isCreation,
+			_isCreation ? 1 : _runs,
+			*this,
+			m_items
+		);
 
 	return tagReplacements;
 }
diff --git a/libevmasm/Assembly.h b/libevmasm/Assembly.h
index 3ce82cce..f3c56610 100644
--- a/libevmasm/Assembly.h
+++ b/libevmasm/Assembly.h
@@ -101,6 +101,7 @@ public:
 	/// execution gas usage is optimised. @a _isCreation should be true for the top-level assembly.
 	/// @a _runs specifes an estimate on how often each opcode in this assembly will be executed,
 	/// i.e. use a small value to optimise for size and a large value to optimise for runtime.
+	/// If @a _enable is not set, will perform some simple peephole optimizations.
 	Assembly& optimise(bool _enable, bool _isCreation = true, size_t _runs = 200);
 	Json::Value stream(
 		std::ostream& _out,
@@ -112,7 +113,7 @@ public:
 protected:
 	/// Does the same operations as @a optimise, but should only be applied to a sub and
 	/// returns the replaced tags.
-	std::map<u256, u256> optimiseInternal(bool _isCreation, size_t _runs);
+	std::map<u256, u256> optimiseInternal(bool _enable, bool _isCreation, size_t _runs);
 
 	std::string locationFromSources(StringMap const& _sourceCodes, SourceLocation const& _location) const;
 	void donePath() { if (m_totalDeposit != INT_MAX && m_totalDeposit != m_deposit) BOOST_THROW_EXCEPTION(InvalidDeposit()); }
diff --git a/libevmasm/PeepholeOptimiser.cpp b/libevmasm/PeepholeOptimiser.cpp
new file mode 100644
index 00000000..91b0ece1
--- /dev/null
+++ b/libevmasm/PeepholeOptimiser.cpp
@@ -0,0 +1,146 @@
+/*
+	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 PeepholeOptimiser.h
+ * Performs local optimising code changes to assembly.
+ */
+
+#include "PeepholeOptimiser.h"
+
+#include <libevmasm/AssemblyItem.h>
+#include <libevmasm/SemanticInformation.h>
+
+using namespace std;
+using namespace dev::eth;
+using namespace dev;
+
+// TODO: Extend this to use the tools from ExpressionClasses.cpp
+
+struct Identity
+{
+	static size_t windowSize() { return 1; }
+	static bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems> _out)
+	{
+		*_out = *_in;
+		return true;
+	}
+};
+
+struct PushPop
+{
+	static size_t windowSize() { return 2; }
+	static bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems>)
+	{
+		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
+		))
+			return true;
+		else
+			return false;
+	}
+};
+
+struct DoubleSwap
+{
+	static size_t windowSize() { return 2; }
+	static bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems>)
+	{
+		if (_in[0] == _in[1] && SemanticInformation::isSwapInstruction(_in[0]))
+			return true;
+		else
+			return false;
+	}
+};
+
+struct JumpToNext
+{
+	static size_t windowSize() { return 3; }
+	static bool apply(AssemblyItems::const_iterator _in, 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()
+		)
+		{
+			*_out = _in[2];
+			return true;
+		}
+		else
+			return false;
+	}
+};
+
+struct TagConjunctions
+{
+	static size_t windowSize() { return 3; }
+	static bool apply(AssemblyItems::const_iterator _in, 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)
+		)
+		{
+			*_out = _in[0];
+			return true;
+		}
+		else
+			return false;
+	}
+};
+
+struct OptimiserState
+{
+	AssemblyItems const& items;
+	size_t i;
+	std::back_insert_iterator<AssemblyItems> out;
+};
+
+void applyMethods(OptimiserState&)
+{
+	assertThrow(false, OptimizerException, "Peephole optimizer failed to apply identity.");
+}
+
+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
+		applyMethods(_state, _other...);
+}
+
+bool PeepholeOptimiser::optimise()
+{
+	OptimiserState state {m_items, 0, std::back_inserter(m_optimisedItems)};
+	while (state.i < m_items.size())
+		applyMethods(state, PushPop(), DoubleSwap(), JumpToNext(), TagConjunctions(), Identity());
+	if (m_optimisedItems.size() < m_items.size())
+	{
+		m_items = std::move(m_optimisedItems);
+		return true;
+	}
+	else
+		return false;
+
+}
diff --git a/libevmasm/PeepholeOptimiser.h b/libevmasm/PeepholeOptimiser.h
new file mode 100644
index 00000000..dfc9a03b
--- /dev/null
+++ b/libevmasm/PeepholeOptimiser.h
@@ -0,0 +1,53 @@
+/*
+	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 PeepholeOptimiser.h
+ * Performs local optimising code changes to assembly.
+ */
+#pragma once
+
+#include <vector>
+#include <cstddef>
+
+namespace dev
+{
+namespace eth
+{
+class AssemblyItem;
+using AssemblyItems = std::vector<AssemblyItem>;
+
+class PeepholeOptimisationMethod
+{
+public:
+	virtual size_t windowSize() const;
+	virtual bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems> _out);
+};
+
+class PeepholeOptimiser
+{
+public:
+	explicit PeepholeOptimiser(AssemblyItems& _items): m_items(_items) {}
+
+	bool optimise();
+
+private:
+	AssemblyItems& m_items;
+	AssemblyItems m_optimisedItems;
+};
+
+}
+}
diff --git a/libsolidity/codegen/Compiler.cpp b/libsolidity/codegen/Compiler.cpp
index eefa50c5..54639515 100644
--- a/libsolidity/codegen/Compiler.cpp
+++ b/libsolidity/codegen/Compiler.cpp
@@ -41,8 +41,7 @@ void Compiler::compileContract(
 	ContractCompiler creationCompiler(&runtimeCompiler, m_context, m_optimize);
 	m_runtimeSub = creationCompiler.compileConstructor(_contract, _contracts);
 
-	if (m_optimize)
-		m_context.optimise(m_optimizeRuns);
+	m_context.optimise(m_optimize, m_optimizeRuns);
 
 	if (_contract.isLibrary())
 	{
@@ -60,8 +59,7 @@ void Compiler::compileClone(
 	ContractCompiler cloneCompiler(&runtimeCompiler, m_context, m_optimize);
 	m_runtimeSub = cloneCompiler.compileClone(_contract, _contracts);
 
-	if (m_optimize)
-		m_context.optimise(m_optimizeRuns);
+	m_context.optimise(m_optimize, m_optimizeRuns);
 }
 
 eth::AssemblyItem Compiler::functionEntryLabel(FunctionDefinition const& _function) const
diff --git a/libsolidity/codegen/CompilerContext.h b/libsolidity/codegen/CompilerContext.h
index ee3fb068..8ccbddfd 100644
--- a/libsolidity/codegen/CompilerContext.h
+++ b/libsolidity/codegen/CompilerContext.h
@@ -155,7 +155,7 @@ public:
 	/// Prepends "PUSH <compiler version number> POP"
 	void injectVersionStampIntoSub(size_t _subIndex);
 
-	void optimise(unsigned _runs = 200) { m_asm->optimise(true, true, _runs); }
+	void optimise(bool _fullOptimsation, unsigned _runs = 200) { m_asm->optimise(_fullOptimsation, true, _runs); }
 
 	/// @returns the runtime context if in creation mode and runtime context is set, nullptr otherwise.
 	CompilerContext* runtimeContext() { return m_runtimeContext; }