diff options
| -rw-r--r-- | libdevcore/CommonData.h | 33 | ||||
| -rw-r--r-- | libjulia/optimiser/ExpressionBreaker.cpp | 105 | ||||
| -rw-r--r-- | libjulia/optimiser/ExpressionBreaker.h | 86 | ||||
| -rw-r--r-- | test/libdevcore/IterateReplacing.cpp | 97 | ||||
| -rw-r--r-- | test/libjulia/ExpressionBreaker.cpp | 156 |
5 files changed, 477 insertions, 0 deletions
diff --git a/libdevcore/CommonData.h b/libdevcore/CommonData.h index e410af5c..98136b44 100644 --- a/libdevcore/CommonData.h +++ b/libdevcore/CommonData.h @@ -25,11 +25,14 @@ #include <libdevcore/Common.h> +#include <boost/optional.hpp> + #include <vector> #include <type_traits> #include <cstring> #include <string> #include <set> +#include <functional> namespace dev { @@ -229,6 +232,36 @@ bool contains(T const& _t, V const& _v) return std::end(_t) != std::find(std::begin(_t), std::end(_t), _v); } + +/// Function that iterates over a vector, calling a function on each of its +/// elements. If that function returns a vector, the element is replaced by +/// the returned vector. During the iteration, the original vector is only valid +/// on the current element and after that. The actual replacement takes +/// place at the end, but already visited elements might be invalidated. +/// If nothing is replaced, no copy is performed. +template <class T> +void iterateReplacing(std::vector<T>& _vector, std::function<boost::optional<std::vector<T>>(T&)> _f) +{ + bool useModified = false; + std::vector<T> modifiedVector; + for (size_t i = 0; i < _vector.size(); ++i) + { + if (boost::optional<std::vector<T>> r = _f(_vector[i])) + { + if (!useModified) + { + std::move(_vector.begin(), _vector.begin() + i, back_inserter(modifiedVector)); + useModified = true; + } + modifiedVector += std::move(*r); + } + else if (useModified) + modifiedVector.emplace_back(std::move(_vector[i])); + } + if (useModified) + _vector = std::move(modifiedVector); +} + /// @returns true iff @a _str passess the hex address checksum test. /// @param _strict if false, hex strings with only uppercase or only lowercase letters /// are considered valid. diff --git a/libjulia/optimiser/ExpressionBreaker.cpp b/libjulia/optimiser/ExpressionBreaker.cpp new file mode 100644 index 00000000..2273fa98 --- /dev/null +++ b/libjulia/optimiser/ExpressionBreaker.cpp @@ -0,0 +1,105 @@ +/* + 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/>. +*/ +/** + * Optimiser component that turns complex expressions into multiple variable + * declarations. + */ + +#include <libjulia/optimiser/ExpressionBreaker.h> + +#include <libjulia/optimiser/ASTWalker.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libdevcore/CommonData.h> + +#include <boost/range/adaptor/reversed.hpp> + +using namespace std; +using namespace dev; +using namespace dev::julia; +using namespace dev::solidity; + +void ExpressionBreaker::operator()(FunctionalInstruction& _instruction) +{ + for (auto& arg: _instruction.arguments | boost::adaptors::reversed) + outlineExpression(arg); +} + +void ExpressionBreaker::operator()(FunctionCall& _funCall) +{ + for (auto& arg: _funCall.arguments | boost::adaptors::reversed) + outlineExpression(arg); +} + +void ExpressionBreaker::operator()(If& _if) +{ + outlineExpression(*_if.condition); + (*this)(_if.body); +} + +void ExpressionBreaker::operator()(Switch& _switch) +{ + outlineExpression(*_switch.expression); + for (auto& _case: _switch.cases) + // Do not visit the case expression, nothing to break there. + (*this)(_case.body); +} + +void ExpressionBreaker::operator()(ForLoop& _loop) +{ + (*this)(_loop.pre); + // Do not visit the condition because we cannot break expressions there. + (*this)(_loop.post); + (*this)(_loop.body); +} + +void ExpressionBreaker::operator()(Block& _block) +{ + vector<Statement> saved; + swap(saved, m_statementsToPrefix); + + function<boost::optional<vector<Statement>>(Statement&)> f = + [&](Statement& _statement) -> boost::optional<vector<Statement>> { + m_statementsToPrefix.clear(); + visit(_statement); + if (m_statementsToPrefix.empty()) + return {}; + m_statementsToPrefix.emplace_back(std::move(_statement)); + return std::move(m_statementsToPrefix); + }; + iterateReplacing(_block.statements, f); + + swap(saved, m_statementsToPrefix); +} + +void ExpressionBreaker::outlineExpression(Expression& _expr) +{ + if (_expr.type() != typeid(FunctionalInstruction) && _expr.type() != typeid(FunctionCall)) + return; + + visit(_expr); + + SourceLocation location = locationOf(_expr); + string var = m_nameDispenser.newName(""); + m_statementsToPrefix.emplace_back(VariableDeclaration{ + location, + {{TypedName{location, var, ""}}}, + make_shared<Expression>(std::move(_expr)) + }); + _expr = Identifier{location, var}; +} diff --git a/libjulia/optimiser/ExpressionBreaker.h b/libjulia/optimiser/ExpressionBreaker.h new file mode 100644 index 00000000..28cfdbc9 --- /dev/null +++ b/libjulia/optimiser/ExpressionBreaker.h @@ -0,0 +1,86 @@ +/* + 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/>. +*/ +/** + * Optimiser component that turns complex expressions into multiple variable + * declarations. + */ +#pragma once + +#include <libjulia/ASTDataForward.h> + +#include <libjulia/optimiser/ASTWalker.h> +#include <libjulia/optimiser/NameDispenser.h> + +#include <vector> + +namespace dev +{ +namespace julia +{ + +class NameCollector; + + +/** + * Optimiser component that modifies an AST in place, turning complex + * expressions into simple expressions and multiple variable declarations. + * + * Code of the form + * + * sstore(mul(x, 4), mload(y)) + * + * is transformed into + * + * let a1 := mload(y) + * let a2 := mul(x, 4) + * sstore(a2, a1) + * + * The transformation is not applied to loop conditions, because the loop control flow + * does not allow "outlining" the inner expressions in all cases. + * + * The final program should be in a form such that with the exception of a loop condition, + * function calls can only appear in the right-hand side of a variable declaration, + * assignments or expression statements and all arguments have to be constants or variables. + */ +class ExpressionBreaker: public ASTModifier +{ +public: + explicit ExpressionBreaker(NameDispenser& _nameDispenser): + m_nameDispenser(_nameDispenser) + { } + + virtual void operator()(FunctionalInstruction&) override; + virtual void operator()(FunctionCall&) override; + virtual void operator()(If&) override; + virtual void operator()(Switch&) override; + virtual void operator()(ForLoop&) override; + virtual void operator()(Block& _block) override; + +private: + /// Replaces the expression by a variable if it is a function call or functional + /// instruction. The declaration of the variable is appended to m_statementsToPrefix. + /// Recurses via visit(). + void outlineExpression(Expression& _expr); + + /// List of statements that should go in front of the currently visited AST element, + /// at the statement level. + std::vector<Statement> m_statementsToPrefix; + NameDispenser& m_nameDispenser; +}; + +} +} diff --git a/test/libdevcore/IterateReplacing.cpp b/test/libdevcore/IterateReplacing.cpp new file mode 100644 index 00000000..08cd1e22 --- /dev/null +++ b/test/libdevcore/IterateReplacing.cpp @@ -0,0 +1,97 @@ +/* + 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/>. +*/ +/** + * Unit tests for the iterateReplacing function + */ + +#include <libdevcore/CommonData.h> + +#include <test/Options.h> + +using namespace std; + +namespace dev +{ +namespace test +{ + +BOOST_AUTO_TEST_SUITE(IterateReplacing) + +BOOST_AUTO_TEST_CASE(no_replacement) +{ + vector<string> v{"abc", "def", "ghi"}; + function<boost::optional<vector<string>>(string&)> f = [](string&) -> boost::optional<vector<string>> { return {}; }; + iterateReplacing(v, f); + vector<string> expectation{"abc", "def", "ghi"}; + BOOST_CHECK(v == expectation); +} + +BOOST_AUTO_TEST_CASE(empty_input) +{ + vector<string> v; + function<boost::optional<vector<string>>(string&)> f = [](string&) -> boost::optional<vector<string>> { return {}; }; + iterateReplacing(v, f); + vector<string> expectation; + BOOST_CHECK(v == expectation); +} + +BOOST_AUTO_TEST_CASE(delete_some) +{ + vector<string> v{"abc", "def", "ghi"}; + function<boost::optional<vector<string>>(string&)> f = [](string& _s) -> boost::optional<vector<string>> { + if (_s == "def") + return vector<string>(); + else + return {}; + }; + iterateReplacing(v, f); + vector<string> expectation{"abc", "ghi"}; + BOOST_CHECK(v == expectation); +} + +BOOST_AUTO_TEST_CASE(inject_some_start) +{ + vector<string> v{"abc", "def", "ghi"}; + function<boost::optional<vector<string>>(string&)> f = [](string& _s) -> boost::optional<vector<string>> { + if (_s == "abc") + return vector<string>{"x", "y"}; + else + return {}; + }; + iterateReplacing(v, f); + vector<string> expectation{"x", "y", "def", "ghi"}; + BOOST_CHECK(v == expectation); +} + +BOOST_AUTO_TEST_CASE(inject_some_end) +{ + vector<string> v{"abc", "def", "ghi"}; + function<boost::optional<vector<string>>(string&)> f = [](string& _s) -> boost::optional<vector<string>> { + if (_s == "ghi") + return vector<string>{"x", "y"}; + else + return {}; + }; + iterateReplacing(v, f); + vector<string> expectation{"abc", "def", "x", "y"}; + BOOST_CHECK(v == expectation); +} + +BOOST_AUTO_TEST_SUITE_END() + +} +} diff --git a/test/libjulia/ExpressionBreaker.cpp b/test/libjulia/ExpressionBreaker.cpp new file mode 100644 index 00000000..de8d2251 --- /dev/null +++ b/test/libjulia/ExpressionBreaker.cpp @@ -0,0 +1,156 @@ +/* + 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/>. +*/ +/** + * Unit tests for the expression breaker. + */ + +#include <test/libjulia/Common.h> + +#include <libjulia/optimiser/ExpressionBreaker.h> +#include <libjulia/optimiser/NameCollector.h> + +#include <libsolidity/inlineasm/AsmPrinter.h> + +#include <boost/test/unit_test.hpp> + +#include <boost/range/adaptors.hpp> +#include <boost/algorithm/string/join.hpp> + +using namespace std; +using namespace dev; +using namespace dev::julia; +using namespace dev::julia::test; +using namespace dev::solidity; + + +#define CHECK(_original, _expectation)\ +do\ +{\ + auto result = parse(_original, false);\ + NameDispenser nameDispenser;\ + nameDispenser.m_usedNames = NameCollector(*result.first).names();\ + ExpressionBreaker{nameDispenser}(*result.first);\ + BOOST_CHECK_EQUAL(assembly::AsmPrinter{}(*result.first), format(_expectation, false));\ +}\ +while(false) + +BOOST_AUTO_TEST_SUITE(YulExpressionBreaker) + +BOOST_AUTO_TEST_CASE(smoke_test) +{ + CHECK("{ }", "{ }"); +} + +BOOST_AUTO_TEST_CASE(trivial) +{ + CHECK( + "{ mstore(add(calldataload(2), mload(3)), 8) }", + "{ let _1 := mload(3) let _2 := calldataload(2) let _3 := add(_2, _1) mstore(_3, 8) }" + ); +} + +BOOST_AUTO_TEST_CASE(control_flow) +{ + string input = R"({ + let x := calldataload(0) + if mul(add(x, 2), 3) { + for { let a := 2 } lt(a, mload(a)) { a := add(a, mul(a, 2)) } { + let b := mul(add(a, 2), 4) + sstore(b, mul(b, 2)) + } + } + })"; + string expectation = R"({ + let x := calldataload(0) + let _1 := add(x, 2) + let _2 := mul(_1, 3) + if _2 + { + for { let a := 2 } lt(a, mload(a)) + { + let _3 := mul(a, 2) + a := add(a, _3) + } + { + let _4 := add(a, 2) + let b := mul(_4, 4) + let _5 := mul(b, 2) + sstore(b, _5) + } + } + })"; + CHECK(input, expectation); +} + +BOOST_AUTO_TEST_CASE(switch_) +{ + string input = R"({ + let x := 8 + switch add(2, calldataload(0)) + case 0 { sstore(0, mload(2)) } + default { mstore(0, mload(3)) } + x := add(mload(3), 4) + })"; + string expectation = R"({ + let x := 8 + let _1 := calldataload(0) + let _2 := add(2, _1) + switch _2 + case 0 { + let _3 := mload(2) + sstore(0, _3) + } + default { + let _4 := mload(3) + mstore(0, _4) + } + let _5 := mload(3) + x := add(_5, 4) + })"; + + CHECK(input, expectation); +} + +BOOST_AUTO_TEST_CASE(inside_function) +{ + string input = R"({ + let x := mul(f(0, mload(7)), 3) + function f(a, b) -> c { + c := mul(a, mload(add(b, c))) + } + sstore(x, f(mload(2), mload(2))) + })"; + string expectation = R"({ + let _1 := mload(7) + let _2 := f(0, _1) + let x := mul(_2, 3) + function f(a, b) -> c + { + let _3 := add(b, c) + let _4 := mload(_3) + c := mul(a, _4) + } + let _5 := mload(2) + let _6 := mload(2) + let _7 := f(_6, _5) + sstore(x, _7) + })"; + + CHECK(input, expectation); +} + +BOOST_AUTO_TEST_SUITE_END() |