From 17bcabb6cfb42a3983ecb79768d44622507ce292 Mon Sep 17 00:00:00 2001 From: Alex Beregszaszi Date: Thu, 29 Mar 2018 12:10:39 +0100 Subject: Remove useless SWAP1 in front of commutative operations --- Changelog.md | 1 + libevmasm/PeepholeOptimiser.cpp | 21 ++++++++++++++++- test/libevmasm/Optimiser.cpp | 51 +++++++++++++++++++++++++++++++++++++++++ 3 files changed, 72 insertions(+), 1 deletion(-) diff --git a/Changelog.md b/Changelog.md index 34c3b0e9..cdfdf6ae 100644 --- a/Changelog.md +++ b/Changelog.md @@ -5,6 +5,7 @@ Features: * Commandline interface: Error when missing or inaccessible file detected. Suppress it with the ``--ignore-missing`` flag. * General: Support accessing dynamic return data in post-byzantium EVMs. * Interfaces: Allow overriding external functions in interfaces with public in an implementing contract. + * Optimizer: Remove useless ``SWAP1`` instruction preceding a commutative instruction (such as ``ADD``, ``MUL``, etc). * Optimizer: Optimize across ``mload`` if ``msize()`` is not used. * Syntax Checker: Issue warning for empty structs (or error as experimental 0.5.0 feature). diff --git a/libevmasm/PeepholeOptimiser.cpp b/libevmasm/PeepholeOptimiser.cpp index 168d1109..30646545 100644 --- a/libevmasm/PeepholeOptimiser.cpp +++ b/libevmasm/PeepholeOptimiser.cpp @@ -154,6 +154,25 @@ struct DoublePush: SimplePeepholeOptimizerMethod } }; +struct CommutativeSwap: SimplePeepholeOptimizerMethod +{ + static bool applySimple(AssemblyItem const& _swap, AssemblyItem const& _op, std::back_insert_iterator _out) + { + // Remove SWAP1 if following instruction is commutative + if ( + _swap.type() == Operation && + _swap.instruction() == Instruction::SWAP1 && + SemanticInformation::isCommutativeOperation(_op) + ) + { + *_out = _op; + return true; + } + else + return false; + } +}; + struct JumpToNext: SimplePeepholeOptimizerMethod { static size_t applySimple( @@ -260,7 +279,7 @@ bool PeepholeOptimiser::optimise() { OptimiserState state {m_items, 0, std::back_inserter(m_optimisedItems)}; while (state.i < m_items.size()) - applyMethods(state, PushPop(), OpPop(), DoublePush(), DoubleSwap(), JumpToNext(), UnreachableCode(), TagConjunctions(), Identity()); + applyMethods(state, PushPop(), OpPop(), DoublePush(), DoubleSwap(), CommutativeSwap(), JumpToNext(), UnreachableCode(), TagConjunctions(), Identity()); if (m_optimisedItems.size() < m_items.size() || ( m_optimisedItems.size() == m_items.size() && ( eth::bytesRequired(m_optimisedItems, 3) < eth::bytesRequired(m_items, 3) || diff --git a/test/libevmasm/Optimiser.cpp b/test/libevmasm/Optimiser.cpp index 28f6b8c0..6b588e75 100644 --- a/test/libevmasm/Optimiser.cpp +++ b/test/libevmasm/Optimiser.cpp @@ -858,6 +858,57 @@ BOOST_AUTO_TEST_CASE(peephole_pop_calldatasize) BOOST_CHECK(items.empty()); } +BOOST_AUTO_TEST_CASE(peephole_commutative_swap1) +{ + AssemblyItems items{ + u256(1), + u256(2), + Instruction::SWAP1, + Instruction::ADD, + u256(4), + u256(5) + }; + AssemblyItems expectation{ + u256(1), + u256(2), + Instruction::ADD, + u256(4), + u256(5) + }; + PeepholeOptimiser peepOpt(items); + BOOST_REQUIRE(peepOpt.optimise()); + BOOST_CHECK_EQUAL_COLLECTIONS( + items.begin(), items.end(), + expectation.begin(), expectation.end() + ); +} + +BOOST_AUTO_TEST_CASE(peephole_noncommutative_swap1) +{ + AssemblyItems items{ + u256(1), + u256(2), + Instruction::SWAP1, + Instruction::SUB, + u256(4), + u256(5) + }; + AssemblyItems expectation{ + u256(1), + u256(2), + Instruction::SWAP1, + Instruction::SUB, + u256(4), + u256(5) + }; + PeepholeOptimiser peepOpt(items); + BOOST_REQUIRE(!peepOpt.optimise()); + BOOST_CHECK_EQUAL_COLLECTIONS( + items.begin(), items.end(), + expectation.begin(), expectation.end() + ); +} + BOOST_AUTO_TEST_CASE(jumpdest_removal) { AssemblyItems items{ -- cgit From be6051beadcc54705f35738d37af017d654c2c01 Mon Sep 17 00:00:00 2001 From: Alex Beregszaszi Date: Tue, 3 Apr 2018 18:05:06 +0200 Subject: Test multiple instructions with the (non)commutative peephole optimiser --- test/libevmasm/Optimiser.cpp | 99 +++++++++++++++++++++++++++----------------- 1 file changed, 62 insertions(+), 37 deletions(-) diff --git a/test/libevmasm/Optimiser.cpp b/test/libevmasm/Optimiser.cpp index 6b588e75..b622b4fb 100644 --- a/test/libevmasm/Optimiser.cpp +++ b/test/libevmasm/Optimiser.cpp @@ -860,53 +860,78 @@ BOOST_AUTO_TEST_CASE(peephole_pop_calldatasize) BOOST_AUTO_TEST_CASE(peephole_commutative_swap1) { - AssemblyItems items{ - u256(1), - u256(2), - Instruction::SWAP1, - Instruction::ADD, - u256(4), - u256(5) - }; - AssemblyItems expectation{ - u256(1), - u256(2), + vector ops{ Instruction::ADD, - u256(4), - u256(5) + Instruction::MUL, + Instruction::EQ, + Instruction::AND, + Instruction::OR, + Instruction::XOR }; - PeepholeOptimiser peepOpt(items); - BOOST_REQUIRE(peepOpt.optimise()); - BOOST_CHECK_EQUAL_COLLECTIONS( + for (Instruction const op: ops) + { + AssemblyItems items{ + u256(1), + u256(2), + Instruction::SWAP1, + op, + u256(4), + u256(5) + }; + AssemblyItems expectation{ + u256(1), + u256(2), + op, + u256(4), + u256(5) + }; + PeepholeOptimiser peepOpt(items); + BOOST_REQUIRE(peepOpt.optimise()); + BOOST_CHECK_EQUAL_COLLECTIONS( items.begin(), items.end(), - expectation.begin(), expectation.end() - ); + expectation.begin(), expectation.end() + ); + } } BOOST_AUTO_TEST_CASE(peephole_noncommutative_swap1) { - AssemblyItems items{ - u256(1), - u256(2), - Instruction::SWAP1, + // NOTE: not comprehensive + vector ops{ Instruction::SUB, - u256(4), - u256(5) - }; - AssemblyItems expectation{ - u256(1), - u256(2), - Instruction::SWAP1, - Instruction::SUB, - u256(4), - u256(5) + Instruction::DIV, + Instruction::SDIV, + Instruction::MOD, + Instruction::SMOD, + Instruction::EXP, + Instruction::LT, + Instruction::GT }; - PeepholeOptimiser peepOpt(items); - BOOST_REQUIRE(!peepOpt.optimise()); - BOOST_CHECK_EQUAL_COLLECTIONS( + for (Instruction const op: ops) + { + AssemblyItems items{ + u256(1), + u256(2), + Instruction::SWAP1, + op, + u256(4), + u256(5) + }; + AssemblyItems expectation{ + u256(1), + u256(2), + Instruction::SWAP1, + op, + u256(4), + u256(5) + }; + PeepholeOptimiser peepOpt(items); + BOOST_REQUIRE(!peepOpt.optimise()); + BOOST_CHECK_EQUAL_COLLECTIONS( items.begin(), items.end(), - expectation.begin(), expectation.end() - ); + expectation.begin(), expectation.end() + ); + } } BOOST_AUTO_TEST_CASE(jumpdest_removal) -- cgit