diff options
| -rw-r--r-- | Changelog.md | 1 | ||||
| -rw-r--r-- | libevmasm/Assembly.cpp | 30 | ||||
| -rw-r--r-- | libevmasm/Assembly.h | 8 | ||||
| -rw-r--r-- | libevmasm/JumpdestRemover.cpp | 68 | ||||
| -rw-r--r-- | libevmasm/JumpdestRemover.h | 50 | ||||
| -rw-r--r-- | test/libevmasm/Optimiser.cpp | 84 | ||||
| -rw-r--r-- | test/libsolidity/Assembly.cpp | 4 | ||||
| -rw-r--r-- | test/libsolidity/JSONCompiler.cpp | 12 | ||||
| -rw-r--r-- | test/libsolidity/StandardCompiler.cpp | 8 |
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())); |