Introduce JumpdestRemover optimisation step

5 files changed, 147 insertions, 10 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;
+};
+
+}
+}