From f2872bfa9990c483fddc72757ee764cbc79d126c Mon Sep 17 00:00:00 2001 From: chriseth Date: Tue, 22 Nov 2016 15:43:51 +0100 Subject: Peephole optimizer for unreacheable code. --- libevmasm/PeepholeOptimiser.cpp | 110 ++++++++++++++++++++++----------- test/libsolidity/SolidityOptimizer.cpp | 48 ++++++++++++-- 2 files changed, 116 insertions(+), 42 deletions(-) diff --git a/libevmasm/PeepholeOptimiser.cpp b/libevmasm/PeepholeOptimiser.cpp index 901e310e..16ca9535 100644 --- a/libevmasm/PeepholeOptimiser.cpp +++ b/libevmasm/PeepholeOptimiser.cpp @@ -30,36 +30,55 @@ using namespace dev; // TODO: Extend this to use the tools from ExpressionClasses.cpp -struct Identity +struct OptimiserState { - static size_t windowSize() { return 1; } - static bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator _out) + AssemblyItems const& items; + size_t i; + std::back_insert_iterator out; +}; + +template +struct SimplePeepholeOptimizerMethod +{ + static bool apply(OptimiserState& _state) + { + if ( + _state.i + WindowSize <= _state.items.size() && + Method::applySimple(_state.items.begin() + _state.i, _state.out) + ) + { + _state.i += WindowSize; + return true; + } + else + return false; + } +}; + +struct Identity: SimplePeepholeOptimizerMethod +{ + static bool applySimple(AssemblyItems::const_iterator _in, std::back_insert_iterator _out) { *_out = *_in; return true; } }; -struct PushPop +struct PushPop: SimplePeepholeOptimizerMethod { - static size_t windowSize() { return 2; } - static bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator) + static size_t applySimple(AssemblyItems::const_iterator _in, std::back_insert_iterator) { auto t = _in[0].type(); - if (_in[1] == Instruction::POP && ( + return _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 AddPop +struct AddPop: SimplePeepholeOptimizerMethod { - static size_t windowSize() { return 2; } static bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator _out) { if (_in[1] == Instruction::POP && @@ -83,22 +102,17 @@ struct AddPop } }; -struct DoubleSwap +struct DoubleSwap: SimplePeepholeOptimizerMethod { - static size_t windowSize() { return 2; } - static bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator) + static size_t applySimple(AssemblyItems::const_iterator _in, std::back_insert_iterator) { - if (_in[0] == _in[1] && SemanticInformation::isSwapInstruction(_in[0])) - return true; - else - return false; + return _in[0] == _in[1] && SemanticInformation::isSwapInstruction(_in[0]); } }; -struct JumpToNext +struct JumpToNext: SimplePeepholeOptimizerMethod { - static size_t windowSize() { return 3; } - static bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator _out) + static size_t applySimple(AssemblyItems::const_iterator _in, std::back_insert_iterator _out) { if ( _in[0].type() == PushTag && @@ -117,10 +131,41 @@ struct JumpToNext } }; -struct TagConjunctions +/// Removes everything after a JUMP (or similar) until the next JUMPDEST. +struct UnreachableCode { - static size_t windowSize() { return 3; } - static bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator _out) + static bool apply(OptimiserState& _state) + { + auto it = _state.items.begin() + _state.i; + auto end = _state.items.end(); + if (it == end) + return false; + if ( + it[0] != Instruction::JUMP && + it[0] != Instruction::RETURN && + it[0] != Instruction::STOP && + it[0] != Instruction::SUICIDE + ) + return false; + + size_t i = 1; + while (it + i != end && it[i].type() != Tag) + i++; + if (i > 1) + { + *_state.out = it[0]; + _state.i += i; + return true; + } + else + return false; + } +}; + + +struct TagConjunctions: SimplePeepholeOptimizerMethod +{ + static bool applySimple(AssemblyItems::const_iterator _in, std::back_insert_iterator _out) { if ( _in[0].type() == PushTag && @@ -137,13 +182,6 @@ struct TagConjunctions } }; -struct OptimiserState -{ - AssemblyItems const& items; - size_t i; - std::back_insert_iterator out; -}; - void applyMethods(OptimiserState&) { assertThrow(false, OptimizerException, "Peephole optimizer failed to apply identity."); @@ -152,9 +190,7 @@ void applyMethods(OptimiserState&) template 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 + if (!Method::apply(_state)) applyMethods(_state, _other...); } @@ -162,7 +198,7 @@ bool PeepholeOptimiser::optimise() { OptimiserState state {m_items, 0, std::back_inserter(m_optimisedItems)}; while (state.i < m_items.size()) - applyMethods(state, PushPop(), AddPop(), DoubleSwap(), JumpToNext(), TagConjunctions(), Identity()); + applyMethods(state, PushPop(), AddPop(), DoubleSwap(), JumpToNext(), UnreachableCode(), TagConjunctions(), Identity()); if (m_optimisedItems.size() < m_items.size()) { m_items = std::move(m_optimisedItems); diff --git a/test/libsolidity/SolidityOptimizer.cpp b/test/libsolidity/SolidityOptimizer.cpp index ecb44272..a53a2638 100644 --- a/test/libsolidity/SolidityOptimizer.cpp +++ b/test/libsolidity/SolidityOptimizer.cpp @@ -20,17 +20,21 @@ * Tests for the Solidity optimizer. */ -#include -#include -#include -#include -#include #include + #include +#include #include #include #include +#include +#include + +#include +#include +#include + using namespace std; using namespace dev::eth; @@ -1121,6 +1125,40 @@ BOOST_AUTO_TEST_CASE(block_deduplicator_loops) BOOST_CHECK_EQUAL(pushTags.size(), 1); } +BOOST_AUTO_TEST_CASE(clear_unreachable_code) +{ + AssemblyItems items{ + AssemblyItem(PushTag, 1), + Instruction::JUMP, + u256(0), + Instruction::SLOAD, + AssemblyItem(Tag, 2), + u256(5), + u256(6), + Instruction::SSTORE, + AssemblyItem(PushTag, 1), + Instruction::JUMP, + u256(5), + u256(6) + }; + AssemblyItems expectation{ + AssemblyItem(PushTag, 1), + Instruction::JUMP, + AssemblyItem(Tag, 2), + u256(5), + u256(6), + Instruction::SSTORE, + AssemblyItem(PushTag, 1), + Instruction::JUMP + }; + PeepholeOptimiser peepOpt(items); + BOOST_REQUIRE(peepOpt.optimise()); + BOOST_CHECK_EQUAL_COLLECTIONS( + items.begin(), items.end(), + expectation.begin(), expectation.end() + ); +} + BOOST_AUTO_TEST_CASE(computing_constants) { char const* sourceCode = R"( -- cgit v1.2.3 From 612c1726d9b0dd1cb5bccd9b93ace69f6516f9ea Mon Sep 17 00:00:00 2001 From: chriseth Date: Wed, 23 Nov 2016 14:50:20 +0100 Subject: Templatize. --- libevmasm/PeepholeOptimiser.cpp | 112 +++++++++++++++++++++++++++------------- 1 file changed, 75 insertions(+), 37 deletions(-) diff --git a/libevmasm/PeepholeOptimiser.cpp b/libevmasm/PeepholeOptimiser.cpp index 16ca9535..c8a28afc 100644 --- a/libevmasm/PeepholeOptimiser.cpp +++ b/libevmasm/PeepholeOptimiser.cpp @@ -37,6 +37,35 @@ struct OptimiserState std::back_insert_iterator out; }; +template +struct ApplyRule +{ +}; +template +struct ApplyRule +{ + static bool applyRule(AssemblyItems::const_iterator _in, std::back_insert_iterator _out) + { + return Method::applySimple(_in[0], _in[1], _in[2], _out); + } +}; +template +struct ApplyRule +{ + static bool applyRule(AssemblyItems::const_iterator _in, std::back_insert_iterator _out) + { + return Method::applySimple(_in[0], _in[1], _out); + } +}; +template +struct ApplyRule +{ + static bool applyRule(AssemblyItems::const_iterator _in, std::back_insert_iterator _out) + { + return Method::applySimple(_in[0], _out); + } +}; + template struct SimplePeepholeOptimizerMethod { @@ -44,7 +73,7 @@ struct SimplePeepholeOptimizerMethod { if ( _state.i + WindowSize <= _state.items.size() && - Method::applySimple(_state.items.begin() + _state.i, _state.out) + ApplyRule::applyRule(_state.items.begin() + _state.i, _state.out) ) { _state.i += WindowSize; @@ -57,20 +86,20 @@ struct SimplePeepholeOptimizerMethod struct Identity: SimplePeepholeOptimizerMethod { - static bool applySimple(AssemblyItems::const_iterator _in, std::back_insert_iterator _out) + static bool applySimple(AssemblyItem const& _item, std::back_insert_iterator _out) { - *_out = *_in; + *_out = _item; return true; } }; struct PushPop: SimplePeepholeOptimizerMethod { - static size_t applySimple(AssemblyItems::const_iterator _in, std::back_insert_iterator) + static size_t applySimple(AssemblyItem const& _push, AssemblyItem const& _pop, std::back_insert_iterator) { - auto t = _in[0].type(); - return _in[1] == Instruction::POP && ( - SemanticInformation::isDupInstruction(_in[0]) || + auto t = _push.type(); + return _pop == Instruction::POP && ( + SemanticInformation::isDupInstruction(_push) || t == Push || t == PushString || t == PushTag || t == PushSub || t == PushSubSize || t == PushProgramSize || t == PushData || t == PushLibraryAddress ); @@ -104,26 +133,55 @@ struct AddPop: SimplePeepholeOptimizerMethod struct DoubleSwap: SimplePeepholeOptimizerMethod { - static size_t applySimple(AssemblyItems::const_iterator _in, std::back_insert_iterator) + static size_t applySimple(AssemblyItem const& _s1, AssemblyItem const& _s2, std::back_insert_iterator) { - return _in[0] == _in[1] && SemanticInformation::isSwapInstruction(_in[0]); + return _s1 == _s2 && SemanticInformation::isSwapInstruction(_s1); } }; struct JumpToNext: SimplePeepholeOptimizerMethod { - static size_t applySimple(AssemblyItems::const_iterator _in, std::back_insert_iterator _out) + static size_t applySimple( + AssemblyItem const& _pushTag, + AssemblyItem const& _jump, + AssemblyItem const& _tag, + std::back_insert_iterator _out + ) + { + if ( + _pushTag.type() == PushTag && + (_jump == Instruction::JUMP || _jump == Instruction::JUMPI) && + _tag.type() == Tag && + _pushTag.data() == _tag.data() + ) + { + if (_jump == Instruction::JUMPI) + *_out = AssemblyItem(Instruction::POP, _jump.location()); + *_out = _tag; + return true; + } + else + return false; + } +}; + +struct TagConjunctions: SimplePeepholeOptimizerMethod +{ + static bool applySimple( + AssemblyItem const& _pushTag, + AssemblyItem const& _pushConstant, + AssemblyItem const& _and, + std::back_insert_iterator _out + ) { if ( - _in[0].type() == PushTag && - (_in[1] == Instruction::JUMP || _in[1] == Instruction::JUMPI) && - _in[2].type() == Tag && - _in[0].data() == _in[2].data() + _pushTag.type() == PushTag && + _and == Instruction::AND && + _pushConstant.type() == Push && + (_pushConstant.data() & u256(0xFFFFFFFF)) == u256(0xFFFFFFFF) ) { - if (_in[1] == Instruction::JUMPI) - *_out = AssemblyItem(Instruction::POP, _in[1].location()); - *_out = _in[2]; + *_out = _pushTag; return true; } else @@ -162,26 +220,6 @@ struct UnreachableCode } }; - -struct TagConjunctions: SimplePeepholeOptimizerMethod -{ - static bool applySimple(AssemblyItems::const_iterator _in, std::back_insert_iterator _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; - } -}; - void applyMethods(OptimiserState&) { assertThrow(false, OptimizerException, "Peephole optimizer failed to apply identity."); -- cgit v1.2.3 From 8a78b1951600a936fadae6ea1644a49e491366f0 Mon Sep 17 00:00:00 2001 From: chriseth Date: Wed, 23 Nov 2016 14:53:59 +0100 Subject: Changelog. --- Changelog.md | 3 +++ 1 file changed, 3 insertions(+) diff --git a/Changelog.md b/Changelog.md index 0b10cd0c..b5e48173 100644 --- a/Changelog.md +++ b/Changelog.md @@ -1,5 +1,8 @@ ### 0.4.7 (unreleased) +Features: + * Optimizer: Some dead code elimination. + Bugfixes: * Type checker: string literals that are not valid UTF-8 cannot be converted to string type -- cgit v1.2.3 From f5216249527a82834162d66f93f15a50346e38d4 Mon Sep 17 00:00:00 2001 From: chriseth Date: Thu, 24 Nov 2016 21:08:30 +0100 Subject: Integrate AddPop. --- libevmasm/Assembly.cpp | 2 +- libevmasm/PeepholeOptimiser.cpp | 27 ++++++++++++--------------- 2 files changed, 13 insertions(+), 16 deletions(-) diff --git a/libevmasm/Assembly.cpp b/libevmasm/Assembly.cpp index 96306750..edbb9828 100644 --- a/libevmasm/Assembly.cpp +++ b/libevmasm/Assembly.cpp @@ -337,7 +337,7 @@ map Assembly::optimiseInternal(bool _enable, bool _isCreation, size_ count = 0; PeepholeOptimiser peepOpt(m_items); - if (peepOpt.optimise()) + while (peepOpt.optimise()) count++; if (!_enable) diff --git a/libevmasm/PeepholeOptimiser.cpp b/libevmasm/PeepholeOptimiser.cpp index c8a28afc..b96b0295 100644 --- a/libevmasm/PeepholeOptimiser.cpp +++ b/libevmasm/PeepholeOptimiser.cpp @@ -95,7 +95,7 @@ struct Identity: SimplePeepholeOptimizerMethod struct PushPop: SimplePeepholeOptimizerMethod { - static size_t applySimple(AssemblyItem const& _push, AssemblyItem const& _pop, std::back_insert_iterator) + static bool applySimple(AssemblyItem const& _push, AssemblyItem const& _pop, std::back_insert_iterator) { auto t = _push.type(); return _pop == Instruction::POP && ( @@ -106,23 +106,20 @@ struct PushPop: SimplePeepholeOptimizerMethod } }; -struct AddPop: SimplePeepholeOptimizerMethod +struct OpPop: SimplePeepholeOptimizerMethod { - static bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator _out) + static bool applySimple( + AssemblyItem const& _op, + AssemblyItem const& _pop, + std::back_insert_iterator _out + ) { - if (_in[1] == Instruction::POP && - _in[0].type() == Operation - ) + if (_pop == Instruction::POP && _op.type() == Operation) { - Instruction i0 = _in[0].instruction(); - if (instructionInfo(i0).ret == 1 && - !SemanticInformation::invalidatesMemory(i0) && - !SemanticInformation::invalidatesStorage(i0) && - !SemanticInformation::altersControlFlow(i0) && - !instructionInfo(i0).sideEffects - ) + Instruction instr = _op.instruction(); + if (instructionInfo(instr).ret == 1 && !instructionInfo(instr).sideEffects) { - for (int j = 0; j < instructionInfo(i0).args; j++) + for (int j = 0; j < instructionInfo(instr).args; j++) *_out = Instruction::POP; return true; } @@ -236,7 +233,7 @@ bool PeepholeOptimiser::optimise() { OptimiserState state {m_items, 0, std::back_inserter(m_optimisedItems)}; while (state.i < m_items.size()) - applyMethods(state, PushPop(), AddPop(), DoubleSwap(), JumpToNext(), UnreachableCode(), TagConjunctions(), Identity()); + applyMethods(state, PushPop(), OpPop(), DoubleSwap(), JumpToNext(), UnreachableCode(), TagConjunctions(), Identity()); if (m_optimisedItems.size() < m_items.size()) { m_items = std::move(m_optimisedItems); -- cgit v1.2.3