From 4c656af3ec922c8db8a254d2e4a9880e9779106b Mon Sep 17 00:00:00 2001 From: chriseth Date: Fri, 27 Mar 2015 20:59:49 +0100 Subject: SHA3 optimizations. --- SolidityOptimizer.cpp | 168 +++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 165 insertions(+), 3 deletions(-) (limited to 'SolidityOptimizer.cpp') diff --git a/SolidityOptimizer.cpp b/SolidityOptimizer.cpp index 4fedd642..ca72f4fe 100644 --- a/SolidityOptimizer.cpp +++ b/SolidityOptimizer.cpp @@ -56,8 +56,16 @@ public: m_nonOptimizedContract = m_contractAddress; m_optimize = true; bytes optimizedBytecode = compileAndRun(_sourceCode, _value, _contractName); + size_t nonOptimizedSize = 0; + eth::eachInstruction(nonOptimizedBytecode, [&](Instruction, u256 const&) { + nonOptimizedSize++; + }); + size_t optimizedSize = 0; + eth::eachInstruction(optimizedBytecode, [&](Instruction, u256 const&) { + optimizedSize++; + }); BOOST_CHECK_MESSAGE( - nonOptimizedBytecode.size() > optimizedBytecode.size(), + nonOptimizedSize > optimizedSize, "Optimizer did not reduce bytecode size." ); m_optimizedContract = m_contractAddress; @@ -75,11 +83,16 @@ public: "\nOptimized: " + toHex(optimizedOutput)); } - void checkCSE(AssemblyItems const& _input, AssemblyItems const& _expectation) + AssemblyItems getCSE(AssemblyItems const& _input) { eth::CommonSubexpressionEliminator cse; BOOST_REQUIRE(cse.feedItems(_input.begin(), _input.end()) == _input.end()); - AssemblyItems output = cse.getOptimizedItems(); + return cse.getOptimizedItems(); + } + + void checkCSE(AssemblyItems const& _input, AssemblyItems const& _expectation) + { + AssemblyItems output = getCSE(_input); BOOST_CHECK_EQUAL_COLLECTIONS(_expectation.begin(), _expectation.end(), output.begin(), output.end()); } @@ -569,6 +582,155 @@ BOOST_AUTO_TEST_CASE(cse_jumpi_jump) }); } +BOOST_AUTO_TEST_CASE(cse_empty_sha3) +{ + AssemblyItems input{ + u256(0), + Instruction::DUP2, + Instruction::SHA3 + }; + checkCSE(input, { + u256(sha3(bytesConstRef())) + }); +} + +BOOST_AUTO_TEST_CASE(cse_partial_sha3) +{ + AssemblyItems input{ + u256(0xabcd) << (256 - 16), + u256(0), + Instruction::MSTORE, + u256(2), + u256(0), + Instruction::SHA3 + }; + checkCSE(input, { + u256(0xabcd) << (256 - 16), + u256(0), + Instruction::MSTORE, + u256(sha3(bytes{0xab, 0xcd})) + }); +} + +BOOST_AUTO_TEST_CASE(cse_sha3_twice_same_location) +{ + // sha3 twice from same dynamic location + AssemblyItems input{ + Instruction::DUP2, + Instruction::DUP1, + Instruction::MSTORE, + u256(64), + Instruction::DUP2, + Instruction::SHA3, + u256(64), + Instruction::DUP3, + Instruction::SHA3 + }; + checkCSE(input, { + Instruction::DUP2, + Instruction::DUP1, + Instruction::MSTORE, + u256(64), + Instruction::DUP2, + Instruction::SHA3, + Instruction::DUP1 + }); +} + +BOOST_AUTO_TEST_CASE(cse_sha3_twice_same_content) +{ + // sha3 twice from different dynamic location but with same content + AssemblyItems input{ + Instruction::DUP1, + u256(0x80), + Instruction::MSTORE, // m[128] = DUP1 + u256(0x20), + u256(0x80), + Instruction::SHA3, // sha3(m[128..(128+32)]) + Instruction::DUP2, + u256(12), + Instruction::MSTORE, // m[12] = DUP1 + u256(0x20), + u256(12), + Instruction::SHA3 // sha3(m[12..(12+32)]) + }; + checkCSE(input, { + u256(0x80), + Instruction::DUP2, + Instruction::DUP2, + Instruction::MSTORE, + u256(0x20), + Instruction::SWAP1, + Instruction::SHA3, + u256(12), + Instruction::DUP3, + Instruction::SWAP1, + Instruction::MSTORE, + Instruction::DUP1 + }); +} + +BOOST_AUTO_TEST_CASE(cse_sha3_twice_same_content_dynamic_store_in_between) +{ + // sha3 twice from different dynamic location but with same content, + // dynamic mstore in between, which forces us to re-calculate the sha3 + AssemblyItems input{ + u256(0x80), + Instruction::DUP2, + Instruction::DUP2, + Instruction::MSTORE, // m[128] = DUP1 + u256(0x20), + Instruction::DUP1, + Instruction::DUP3, + Instruction::SHA3, // sha3(m[128..(128+32)]) + u256(12), + Instruction::DUP5, + Instruction::DUP2, + Instruction::MSTORE, // m[12] = DUP1 + Instruction::DUP12, + Instruction::DUP14, + Instruction::MSTORE, // destroys memory knowledge + Instruction::SWAP2, + Instruction::SWAP1, + Instruction::SWAP2, + Instruction::SHA3 // sha3(m[12..(12+32)]) + }; + checkCSE(input, input); +} + +BOOST_AUTO_TEST_CASE(cse_sha3_twice_same_content_noninterfering_store_in_between) +{ + // sha3 twice from different dynamic location but with same content, + // dynamic mstore in between, but does not force us to re-calculate the sha3 + AssemblyItems input{ + u256(0x80), + Instruction::DUP2, + Instruction::DUP2, + Instruction::MSTORE, // m[128] = DUP1 + u256(0x20), + Instruction::DUP1, + Instruction::DUP3, + Instruction::SHA3, // sha3(m[128..(128+32)]) + u256(12), + Instruction::DUP5, + Instruction::DUP2, + Instruction::MSTORE, // m[12] = DUP1 + Instruction::DUP12, + u256(12 + 32), + Instruction::MSTORE, // does not destoy memory knowledge + Instruction::DUP13, + u256(128 - 32), + Instruction::MSTORE, // does not destoy memory knowledge + u256(0x20), + u256(12), + Instruction::SHA3 // sha3(m[12..(12+32)]) + }; + // if this changes too often, only count the number of SHA3 and MSTORE instructions + AssemblyItems output = getCSE(input); + BOOST_CHECK_EQUAL(4, count(output.begin(), output.end(), AssemblyItem(Instruction::MSTORE))); + BOOST_CHECK_EQUAL(1, count(output.begin(), output.end(), AssemblyItem(Instruction::SHA3))); +} + BOOST_AUTO_TEST_SUITE_END() } -- cgit v1.2.3 From 68b61432aea5f99f179b74f5a7a63138a5d2b09a Mon Sep 17 00:00:00 2001 From: chriseth Date: Tue, 7 Apr 2015 16:33:13 +0200 Subject: Typos and docs. --- SolidityOptimizer.cpp | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-) (limited to 'SolidityOptimizer.cpp') diff --git a/SolidityOptimizer.cpp b/SolidityOptimizer.cpp index ca72f4fe..f523847f 100644 --- a/SolidityOptimizer.cpp +++ b/SolidityOptimizer.cpp @@ -715,15 +715,15 @@ BOOST_AUTO_TEST_CASE(cse_sha3_twice_same_content_noninterfering_store_in_between Instruction::DUP5, Instruction::DUP2, Instruction::MSTORE, // m[12] = DUP1 - Instruction::DUP12, - u256(12 + 32), - Instruction::MSTORE, // does not destoy memory knowledge - Instruction::DUP13, - u256(128 - 32), - Instruction::MSTORE, // does not destoy memory knowledge - u256(0x20), - u256(12), - Instruction::SHA3 // sha3(m[12..(12+32)]) + Instruction::DUP12, + u256(12 + 32), + Instruction::MSTORE, // does not destoy memory knowledge + Instruction::DUP13, + u256(128 - 32), + Instruction::MSTORE, // does not destoy memory knowledge + u256(0x20), + u256(12), + Instruction::SHA3 // sha3(m[12..(12+32)]) }; // if this changes too often, only count the number of SHA3 and MSTORE instructions AssemblyItems output = getCSE(input); -- cgit v1.2.3 From cf9515c750474fdd7f31e53efd30be7438786b96 Mon Sep 17 00:00:00 2001 From: chriseth Date: Thu, 2 Apr 2015 19:20:30 +0200 Subject: Control flow analysis. --- SolidityOptimizer.cpp | 80 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 80 insertions(+) (limited to 'SolidityOptimizer.cpp') diff --git a/SolidityOptimizer.cpp b/SolidityOptimizer.cpp index f523847f..450ae3c2 100644 --- a/SolidityOptimizer.cpp +++ b/SolidityOptimizer.cpp @@ -28,6 +28,7 @@ #include #include #include +#include #include using namespace std; @@ -96,6 +97,18 @@ public: BOOST_CHECK_EQUAL_COLLECTIONS(_expectation.begin(), _expectation.end(), output.begin(), output.end()); } + void checkCFG(AssemblyItems const& _input, AssemblyItems const& _expectation) + { + AssemblyItems output = _input; + // Running it four times should be enough for these tests. + for (unsigned i = 0; i < 4; ++i) + { + eth::ControlFlowGraph cfg(output); + output = cfg.optimisedItems(); + } + BOOST_CHECK_EQUAL_COLLECTIONS(_expectation.begin(), _expectation.end(), output.begin(), output.end()); + } + protected: Address m_optimizedContract; Address m_nonOptimizedContract; @@ -731,6 +744,73 @@ BOOST_AUTO_TEST_CASE(cse_sha3_twice_same_content_noninterfering_store_in_between BOOST_CHECK_EQUAL(1, count(output.begin(), output.end(), AssemblyItem(Instruction::SHA3))); } +BOOST_AUTO_TEST_CASE(control_flow_graph_remove_unused) +{ + // remove parts of the code that are unused + AssemblyItems input{ + AssemblyItem(PushTag, 1), + Instruction::JUMP, + u256(7), + AssemblyItem(Tag, 1), + }; + checkCFG(input, {}); +} + +BOOST_AUTO_TEST_CASE(control_flow_graph_remove_unused_loop) +{ + AssemblyItems input{ + AssemblyItem(PushTag, 3), + Instruction::JUMP, + AssemblyItem(Tag, 1), + u256(7), + AssemblyItem(PushTag, 2), + Instruction::JUMP, + AssemblyItem(Tag, 2), + u256(8), + AssemblyItem(PushTag, 1), + Instruction::JUMP, + AssemblyItem(Tag, 3), + u256(11) + }; + checkCFG(input, {u256(11)}); +} + +BOOST_AUTO_TEST_CASE(control_flow_graph_reconnect_single_jump_source) +{ + // move code that has only one unconditional jump source + AssemblyItems input{ + u256(1), + AssemblyItem(PushTag, 1), + Instruction::JUMP, + AssemblyItem(Tag, 2), + u256(2), + AssemblyItem(PushTag, 3), + Instruction::JUMP, + AssemblyItem(Tag, 1), + u256(3), + AssemblyItem(PushTag, 2), + Instruction::JUMP, + AssemblyItem(Tag, 3), + u256(4), + }; + checkCFG(input, {u256(1), u256(3), u256(2), u256(4)}); +} + +BOOST_AUTO_TEST_CASE(control_flow_graph_do_not_remove_returned_to) +{ + // do not remove parts that are "returned to" + AssemblyItems input{ + AssemblyItem(PushTag, 1), + AssemblyItem(PushTag, 2), + Instruction::JUMP, + AssemblyItem(Tag, 2), + Instruction::JUMP, + AssemblyItem(PushTag, 1), + u256(2) + }; + checkCFG(input, {u256(2)}); +} + BOOST_AUTO_TEST_SUITE_END() } -- cgit v1.2.3 From 4362c93ebfcf0c8b5f8de227b6161aee2fb63a66 Mon Sep 17 00:00:00 2001 From: chriseth Date: Wed, 15 Apr 2015 18:43:40 +0200 Subject: Fixed test. --- SolidityOptimizer.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'SolidityOptimizer.cpp') diff --git a/SolidityOptimizer.cpp b/SolidityOptimizer.cpp index 450ae3c2..f57380ac 100644 --- a/SolidityOptimizer.cpp +++ b/SolidityOptimizer.cpp @@ -805,7 +805,7 @@ BOOST_AUTO_TEST_CASE(control_flow_graph_do_not_remove_returned_to) Instruction::JUMP, AssemblyItem(Tag, 2), Instruction::JUMP, - AssemblyItem(PushTag, 1), + AssemblyItem(Tag, 1), u256(2) }; checkCFG(input, {u256(2)}); -- cgit v1.2.3