Merge pull request #2657 from ethereum/jumpdest-remover

Introduce JumpdestRemover optimisation step

9 files changed, 243 insertions, 22 deletions

diff --git a/Changelog.md b/Changelog.md
index f4915db1..c3482c4b 100644
--- a/Changelog.md
+++ b/Changelog.md
@@ -1,6 +1,7 @@
 ### 0.4.17 (unreleased)
 
 Features:
+ * Optimizer: Add new optimization step to remove unused ``JUMPDEST``s.
 
 Bugfixes:
 
diff --git a/libevmasm/Assembly.cpp b/libevmasm/Assembly.cpp
index 0a3bf6b8..8c1f9296 100644
--- a/libevmasm/Assembly.cpp
+++ b/libevmasm/Assembly.cpp
@@ -24,6 +24,7 @@
 #include <libevmasm/CommonSubexpressionEliminator.h>
 #include <libevmasm/ControlFlowGraph.h>
 #include <libevmasm/PeepholeOptimiser.h>
+#include <libevmasm/JumpdestRemover.h>
 #include <libevmasm/BlockDeduplicator.h>
 #include <libevmasm/ConstantOptimiser.h>
 #include <libevmasm/GasMeter.h>
@@ -349,6 +350,7 @@ Assembly& Assembly::optimise(bool _enable, bool _isCreation, size_t _runs)
 {
 	OptimiserSettings settings;
 	settings.isCreation = _isCreation;
+	settings.runJumpdestRemover = true;
 	settings.runPeephole = true;
 	if (_enable)
 	{
@@ -357,18 +359,21 @@ Assembly& Assembly::optimise(bool _enable, bool _isCreation, size_t _runs)
 		settings.runConstantOptimiser = true;
 	}
 	settings.expectedExecutionsPerDeployment = _runs;
-	optimiseInternal(settings);
+	optimise(settings);
 	return *this;
 }
 
 
-Assembly& Assembly::optimise(OptimiserSettings _settings)
+Assembly& Assembly::optimise(OptimiserSettings const& _settings)
 {
-	optimiseInternal(_settings);
+	optimiseInternal(_settings, {});
 	return *this;
 }
 
-map<u256, u256> Assembly::optimiseInternal(OptimiserSettings _settings)
+map<u256, u256> Assembly::optimiseInternal(
+	OptimiserSettings const& _settings,
+	std::set<size_t> const& _tagsReferencedFromOutside
+)
 {
 	// Run optimisation for sub-assemblies.
 	for (size_t subId = 0; subId < m_subs.size(); ++subId)
@@ -376,7 +381,10 @@ map<u256, u256> Assembly::optimiseInternal(OptimiserSettings _settings)
 		OptimiserSettings settings = _settings;
 		// Disable creation mode for sub-assemblies.
 		settings.isCreation = false;
-		map<u256, u256> subTagReplacements = m_subs[subId]->optimiseInternal(settings);
+		map<u256, u256> subTagReplacements = m_subs[subId]->optimiseInternal(
+			settings,
+			JumpdestRemover::referencedTags(m_items, subId)
+		);
 		// Apply the replacements (can be empty).
 		BlockDeduplicator::applyTagReplacement(m_items, subTagReplacements, subId);
 	}
@@ -387,6 +395,13 @@ map<u256, u256> Assembly::optimiseInternal(OptimiserSettings _settings)
 	{
 		count = 0;
 
+		if (_settings.runJumpdestRemover)
+		{
+			JumpdestRemover jumpdestOpt(m_items);
+			if (jumpdestOpt.optimise(_tagsReferencedFromOutside))
+				count++;
+		}
+
 		if (_settings.runPeephole)
 		{
 			PeepholeOptimiser peepOpt(m_items);
@@ -473,8 +488,9 @@ LinkerObject const& Assembly::assemble() const
 	for (auto const& sub: m_subs)
 	{
 		sub->assemble();
-		if (!sub->m_tagPositionsInBytecode.empty())
-			subTagSize = max(subTagSize, *max_element(sub->m_tagPositionsInBytecode.begin(), sub->m_tagPositionsInBytecode.end()));
+		for (size_t tagPos: sub->m_tagPositionsInBytecode)
+			if (tagPos != size_t(-1) && tagPos > subTagSize)
+				subTagSize = tagPos;
 	}
 
 	LinkerObject& ret = m_assembledObject;
diff --git a/libevmasm/Assembly.h b/libevmasm/Assembly.h
index 451b4ea0..680cb1af 100644
--- a/libevmasm/Assembly.h
+++ b/libevmasm/Assembly.h
@@ -100,6 +100,7 @@ public:
 	struct OptimiserSettings
 	{
 		bool isCreation = false;
+		bool runJumpdestRemover = false;
 		bool runPeephole = false;
 		bool runDeduplicate = false;
 		bool runCSE = false;
@@ -110,7 +111,7 @@ public:
 	};
 
 	/// Execute optimisation passes as defined by @a _settings and return the optimised assembly.
-	Assembly& optimise(OptimiserSettings _settings);
+	Assembly& optimise(OptimiserSettings const& _settings);
 
 	/// Modify (if @a _enable is set) and return the current assembly such that creation and
 	/// execution gas usage is optimised. @a _isCreation should be true for the top-level assembly.
@@ -128,8 +129,9 @@ 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(OptimiserSettings _settings);
+	/// returns the replaced tags. Also takes an argument containing the tags of this assembly
+	/// that are referenced in a super-assembly.
+	std::map<u256, u256> optimiseInternal(OptimiserSettings const& _settings, std::set<size_t> const& _tagsReferencedFromOutside);
 
 	unsigned bytesRequired(unsigned subTagSize) const;
 
diff --git a/libevmasm/JumpdestRemover.cpp b/libevmasm/JumpdestRemover.cpp
new file mode 100644
index 00000000..b6016798
--- /dev/null
+++ b/libevmasm/JumpdestRemover.cpp
@@ -0,0 +1,68 @@
+/*
+	This file is part of solidity.
+
+	solidity 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.
+
+	solidity 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 solidity.  If not, see <http://www.gnu.org/licenses/>.
+*/
+/**
+ * @author Alex Beregszaszi
+ * Removes unused JUMPDESTs.
+ */
+
+#include "JumpdestRemover.h"
+
+#include <libsolidity/interface/Exceptions.h>
+
+#include <libevmasm/AssemblyItem.h>
+
+using namespace std;
+using namespace dev::eth;
+using namespace dev;
+
+
+bool JumpdestRemover::optimise(set<size_t> const& _tagsReferencedFromOutside)
+{
+	set<size_t> references{referencedTags(m_items, -1)};
+	references.insert(_tagsReferencedFromOutside.begin(), _tagsReferencedFromOutside.end());
+
+	size_t initialSize = m_items.size();
+	/// Remove tags which are never referenced.
+	auto pend = remove_if(
+		m_items.begin(),
+		m_items.end(),
+		[&](AssemblyItem const& _item)
+		{
+			if (_item.type() != Tag)
+				return false;
+			auto asmIdAndTag = _item.splitForeignPushTag();
+			solAssert(asmIdAndTag.first == size_t(-1), "Sub-assembly tag used as label.");
+			size_t tag = asmIdAndTag.second;
+			return !references.count(tag);
+		}
+	);
+	m_items.erase(pend, m_items.end());
+	return m_items.size() != initialSize;
+}
+
+set<size_t> JumpdestRemover::referencedTags(AssemblyItems const& _items, size_t _subId)
+{
+	set<size_t> ret;
+	for (auto const& item: _items)
+		if (item.type() == PushTag)
+		{
+			auto subAndTag = item.splitForeignPushTag();
+			if (subAndTag.first == _subId)
+				ret.insert(subAndTag.second);
+		}
+	return ret;
+}
diff --git a/libevmasm/JumpdestRemover.h b/libevmasm/JumpdestRemover.h
new file mode 100644
index 00000000..2dad0927
--- /dev/null
+++ b/libevmasm/JumpdestRemover.h
@@ -0,0 +1,50 @@
+/*
+	This file is part of solidity.
+
+	solidity 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.
+
+	solidity 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 solidity.  If not, see <http://www.gnu.org/licenses/>.
+*/
+/**
+ * @author Alex Beregszaszi
+ * Removes unused JUMPDESTs.
+ */
+#pragma once
+
+#include <vector>
+#include <cstddef>
+#include <set>
+
+namespace dev
+{
+namespace eth
+{
+class AssemblyItem;
+using AssemblyItems = std::vector<AssemblyItem>;
+
+class JumpdestRemover
+{
+public:
+	explicit JumpdestRemover(AssemblyItems& _items): m_items(_items) {}
+
+	bool optimise(std::set<size_t> const& _tagsReferencedFromOutside);
+
+	/// @returns a set of all tags from the given sub-assembly that are referenced
+	/// from the given list of items.
+	static std::set<size_t> referencedTags(AssemblyItems const& _items, size_t _subId);
+
+private:
+	AssemblyItems& m_items;
+};
+
+}
+}
diff --git a/test/libevmasm/Optimiser.cpp b/test/libevmasm/Optimiser.cpp
index 6656f15b..9dc49581 100644
--- a/test/libevmasm/Optimiser.cpp
+++ b/test/libevmasm/Optimiser.cpp
@@ -22,6 +22,7 @@
 
 #include <libevmasm/CommonSubexpressionEliminator.h>
 #include <libevmasm/PeepholeOptimiser.h>
+#include <libevmasm/JumpdestRemover.h>
 #include <libevmasm/ControlFlowGraph.h>
 #include <libevmasm/BlockDeduplicator.h>
 #include <libevmasm/Assembly.h>
@@ -840,6 +841,89 @@ BOOST_AUTO_TEST_CASE(peephole_double_push)
 	);
 }
 
+BOOST_AUTO_TEST_CASE(jumpdest_removal)
+{
+	AssemblyItems items{
+		AssemblyItem(Tag, 2),
+		AssemblyItem(PushTag, 1),
+		u256(5),
+		AssemblyItem(Tag, 10),
+		AssemblyItem(Tag, 3),
+		u256(6),
+		AssemblyItem(Tag, 1),
+		Instruction::JUMP,
+	};
+	AssemblyItems expectation{
+		AssemblyItem(PushTag, 1),
+		u256(5),
+		u256(6),
+		AssemblyItem(Tag, 1),
+		Instruction::JUMP
+	};
+	JumpdestRemover jdr(items);
+	BOOST_REQUIRE(jdr.optimise({}));
+	BOOST_CHECK_EQUAL_COLLECTIONS(
+		items.begin(), items.end(),
+		expectation.begin(), expectation.end()
+	);
+}
+
+BOOST_AUTO_TEST_CASE(jumpdest_removal_subassemblies)
+{
+	// This tests that tags from subassemblies are not removed
+	// if they are referenced by a super-assembly. Furthermore,
+	// tag unifications (due to block deduplication) is also
+	// visible at the super-assembly.
+
+	Assembly main;
+	AssemblyPointer sub = make_shared<Assembly>();
+
+	sub->append(u256(1));
+	auto t1 = sub->newTag();
+	sub->append(t1);
+	sub->append(u256(2));
+	sub->append(Instruction::JUMP);
+	auto t2 = sub->newTag();
+	sub->append(t2); // Identical to T1, will be unified
+	sub->append(u256(2));
+	sub->append(Instruction::JUMP);
+	auto t3 = sub->newTag();
+	sub->append(t3);
+	auto t4 = sub->newTag();
+	sub->append(t4);
+	auto t5 = sub->newTag();
+	sub->append(t5); // This will be removed
+	sub->append(u256(7));
+	sub->append(t4.pushTag());
+	sub->append(Instruction::JUMP);
+
+	size_t subId = size_t(main.appendSubroutine(sub).data());
+	main.append(t1.toSubAssemblyTag(subId));
+	main.append(t1.toSubAssemblyTag(subId));
+	main.append(u256(8));
+
+	main.optimise(true);
+
+	AssemblyItems expectationMain{
+		AssemblyItem(PushSubSize, 0),
+		t1.toSubAssemblyTag(subId).pushTag(),
+		t1.toSubAssemblyTag(subId).pushTag(),
+		u256(8)
+	};
+	BOOST_CHECK_EQUAL_COLLECTIONS(
+		main.items().begin(), main.items().end(),
+		expectationMain.begin(), expectationMain.end()
+	);
+
+	AssemblyItems expectationSub{
+		u256(1), t1.tag(), u256(2), Instruction::JUMP, t4.tag(), u256(7), t4.pushTag(), Instruction::JUMP
+	};
+	BOOST_CHECK_EQUAL_COLLECTIONS(
+		sub->items().begin(), sub->items().end(),
+		expectationSub.begin(), expectationSub.end()
+	);
+}
+
 BOOST_AUTO_TEST_CASE(cse_sub_zero)
 {
 	checkCSE({
diff --git a/test/libsolidity/Assembly.cpp b/test/libsolidity/Assembly.cpp
index 99a2996e..56ac8cf5 100644
--- a/test/libsolidity/Assembly.cpp
+++ b/test/libsolidity/Assembly.cpp
@@ -119,11 +119,11 @@ BOOST_AUTO_TEST_CASE(location_test)
 	shared_ptr<string const> n = make_shared<string>("");
 	AssemblyItems items = compileContract(sourceCode);
 	vector<SourceLocation> locations =
-		vector<SourceLocation>(19, SourceLocation(2, 75, n)) +
+		vector<SourceLocation>(18, SourceLocation(2, 75, n)) +
 		vector<SourceLocation>(32, SourceLocation(20, 72, n)) +
 		vector<SourceLocation>{SourceLocation(42, 51, n), SourceLocation(65, 67, n)} +
 		vector<SourceLocation>(2, SourceLocation(58, 67, n)) +
-		vector<SourceLocation>(3, SourceLocation(20, 72, n));
+		vector<SourceLocation>(2, SourceLocation(20, 72, n));
 	checkAssemblyLocations(items, locations);
 }
 
diff --git a/test/libsolidity/JSONCompiler.cpp b/test/libsolidity/JSONCompiler.cpp
index 0fe7636c..541cfbf0 100644
--- a/test/libsolidity/JSONCompiler.cpp
+++ b/test/libsolidity/JSONCompiler.cpp
@@ -120,18 +120,18 @@ BOOST_AUTO_TEST_CASE(basic_compilation)
 	BOOST_CHECK(contract["bytecode"].isString());
 	BOOST_CHECK_EQUAL(
 		dev::test::bytecodeSansMetadata(contract["bytecode"].asString()),
-		"60606040523415600e57600080fd5b5b603680601c6000396000f30060606040525b600080fd00"
+		"60606040523415600e57600080fd5b603580601b6000396000f3006060604052600080fd00"
 	);
 	BOOST_CHECK(contract["runtimeBytecode"].isString());
 	BOOST_CHECK_EQUAL(
 		dev::test::bytecodeSansMetadata(contract["runtimeBytecode"].asString()),
-		"60606040525b600080fd00"
+		"6060604052600080fd00"
 	);
 	BOOST_CHECK(contract["functionHashes"].isObject());
 	BOOST_CHECK(contract["gasEstimates"].isObject());
 	BOOST_CHECK_EQUAL(
 		dev::jsonCompactPrint(contract["gasEstimates"]),
-		"{\"creation\":[62,10800],\"external\":{},\"internal\":{}}"
+		"{\"creation\":[61,10600],\"external\":{},\"internal\":{}}"
 	);
 	BOOST_CHECK(contract["metadata"].isString());
 	BOOST_CHECK(dev::test::isValidMetadata(contract["metadata"].asString()));
@@ -162,18 +162,18 @@ BOOST_AUTO_TEST_CASE(single_compilation)
 	BOOST_CHECK(contract["bytecode"].isString());
 	BOOST_CHECK_EQUAL(
 		dev::test::bytecodeSansMetadata(contract["bytecode"].asString()),
-		"60606040523415600e57600080fd5b5b603680601c6000396000f30060606040525b600080fd00"
+		"60606040523415600e57600080fd5b603580601b6000396000f3006060604052600080fd00"
 	);
 	BOOST_CHECK(contract["runtimeBytecode"].isString());
 	BOOST_CHECK_EQUAL(
 		dev::test::bytecodeSansMetadata(contract["runtimeBytecode"].asString()),
-		"60606040525b600080fd00"
+		"6060604052600080fd00"
 	);
 	BOOST_CHECK(contract["functionHashes"].isObject());
 	BOOST_CHECK(contract["gasEstimates"].isObject());
 	BOOST_CHECK_EQUAL(
 		dev::jsonCompactPrint(contract["gasEstimates"]),
-		"{\"creation\":[62,10800],\"external\":{},\"internal\":{}}"
+		"{\"creation\":[61,10600],\"external\":{},\"internal\":{}}"
 	);
 	BOOST_CHECK(contract["metadata"].isString());
 	BOOST_CHECK(dev::test::isValidMetadata(contract["metadata"].asString()));
diff --git a/test/libsolidity/StandardCompiler.cpp b/test/libsolidity/StandardCompiler.cpp
index 79848c36..24f915c0 100644
--- a/test/libsolidity/StandardCompiler.cpp
+++ b/test/libsolidity/StandardCompiler.cpp
@@ -198,19 +198,19 @@ BOOST_AUTO_TEST_CASE(basic_compilation)
 	BOOST_CHECK(contract["evm"]["bytecode"]["object"].isString());
 	BOOST_CHECK_EQUAL(
 		dev::test::bytecodeSansMetadata(contract["evm"]["bytecode"]["object"].asString()),
-		"60606040523415600e57600080fd5b5b603680601c6000396000f30060606040525b600080fd00"
+		"60606040523415600e57600080fd5b603580601b6000396000f3006060604052600080fd00"
 	);
 	BOOST_CHECK(contract["evm"]["assembly"].isString());
 	BOOST_CHECK(contract["evm"]["assembly"].asString().find(
 		"    /* \"fileA\":0:14  contract A { } */\n  mstore(0x40, 0x60)\n  jumpi(tag_1, iszero(callvalue))\n"
-		"  0x0\n  dup1\n  revert\ntag_1:\ntag_2:\n  dataSize(sub_0)\n  dup1\n  dataOffset(sub_0)\n  0x0\n  codecopy\n  0x0\n"
+		"  0x0\n  dup1\n  revert\ntag_1:\n  dataSize(sub_0)\n  dup1\n  dataOffset(sub_0)\n  0x0\n  codecopy\n  0x0\n"
 		"  return\nstop\n\nsub_0: assembly {\n        /* \"fileA\":0:14  contract A { } */\n"
-		"      mstore(0x40, 0x60)\n    tag_1:\n      0x0\n      dup1\n      revert\n\n"
+		"      mstore(0x40, 0x60)\n      0x0\n      dup1\n      revert\n\n"
 		"    auxdata: 0xa165627a7a7230582") == 0);
 	BOOST_CHECK(contract["evm"]["gasEstimates"].isObject());
 	BOOST_CHECK_EQUAL(
 		dev::jsonCompactPrint(contract["evm"]["gasEstimates"]),
-		"{\"creation\":{\"codeDepositCost\":\"10800\",\"executionCost\":\"62\",\"totalCost\":\"10862\"}}"
+		"{\"creation\":{\"codeDepositCost\":\"10600\",\"executionCost\":\"61\",\"totalCost\":\"10661\"}}"
 	);
 	BOOST_CHECK(contract["metadata"].isString());
 	BOOST_CHECK(dev::test::isValidMetadata(contract["metadata"].asString()));