aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorchriseth <c@ethdev.com>2016-11-22 22:43:51 +0800
committerchriseth <c@ethdev.com>2016-11-25 23:10:02 +0800
commitf2872bfa9990c483fddc72757ee764cbc79d126c (patch)
tree6591cd087a83bc57bb8db26966e40e3b61c34435
parent721b6a969685e99078e296d88135ef84f6c001eb (diff)
downloaddexon-solidity-f2872bfa9990c483fddc72757ee764cbc79d126c.tar.gz
dexon-solidity-f2872bfa9990c483fddc72757ee764cbc79d126c.tar.zst
dexon-solidity-f2872bfa9990c483fddc72757ee764cbc79d126c.zip
Peephole optimizer for unreacheable code.
-rw-r--r--libevmasm/PeepholeOptimiser.cpp110
-rw-r--r--test/libsolidity/SolidityOptimizer.cpp48
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<AssemblyItems> _out)
+ AssemblyItems const& items;
+ size_t i;
+ std::back_insert_iterator<AssemblyItems> out;
+};
+
+template <class Method, size_t WindowSize>
+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<Identity, 1>
+{
+ static bool applySimple(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems> _out)
{
*_out = *_in;
return true;
}
};
-struct PushPop
+struct PushPop: SimplePeepholeOptimizerMethod<PushPop, 2>
{
- static size_t windowSize() { return 2; }
- static bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems>)
+ static size_t applySimple(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems>)
{
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<AddPop, 2>
{
- static size_t windowSize() { return 2; }
static bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems> _out)
{
if (_in[1] == Instruction::POP &&
@@ -83,22 +102,17 @@ struct AddPop
}
};
-struct DoubleSwap
+struct DoubleSwap: SimplePeepholeOptimizerMethod<DoubleSwap, 2>
{
- static size_t windowSize() { return 2; }
- static bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems>)
+ static size_t applySimple(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems>)
{
- 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<JumpToNext, 3>
{
- static size_t windowSize() { return 3; }
- static bool apply(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems> _out)
+ static size_t applySimple(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems> _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<AssemblyItems> _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<TagConjunctions, 3>
+{
+ static bool applySimple(AssemblyItems::const_iterator _in, std::back_insert_iterator<AssemblyItems> _out)
{
if (
_in[0].type() == PushTag &&
@@ -137,13 +182,6 @@ struct TagConjunctions
}
};
-struct OptimiserState
-{
- AssemblyItems const& items;
- size_t i;
- std::back_insert_iterator<AssemblyItems> out;
-};
-
void applyMethods(OptimiserState&)
{
assertThrow(false, OptimizerException, "Peephole optimizer failed to apply identity.");
@@ -152,9 +190,7 @@ void applyMethods(OptimiserState&)
template <typename Method, typename... OtherMethods>
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 <string>
-#include <tuple>
-#include <memory>
-#include <boost/test/unit_test.hpp>
-#include <boost/lexical_cast.hpp>
#include <test/libsolidity/SolidityExecutionFramework.h>
+
#include <libevmasm/CommonSubexpressionEliminator.h>
+#include <libevmasm/PeepholeOptimiser.h>
#include <libevmasm/ControlFlowGraph.h>
#include <libevmasm/Assembly.h>
#include <libevmasm/BlockDeduplicator.h>
+#include <boost/test/unit_test.hpp>
+#include <boost/lexical_cast.hpp>
+
+#include <string>
+#include <tuple>
+#include <memory>
+
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"(