From f950973eb2b0dea16d7fd8d0f70309ff38b23337 Mon Sep 17 00:00:00 2001 From: chriseth Date: Wed, 10 Oct 2018 16:23:35 +0200 Subject: Rename ExpressionBreaker to ExpressionSplitter. --- libjulia/optimiser/ExpressionBreaker.cpp | 105 -------------------- libjulia/optimiser/ExpressionBreaker.h | 86 ---------------- libjulia/optimiser/ExpressionSplitter.cpp | 105 ++++++++++++++++++++ libjulia/optimiser/ExpressionSplitter.h | 86 ++++++++++++++++ test/libjulia/ExpressionBreaker.cpp | 156 ------------------------------ test/libjulia/ExpressionSplitter.cpp | 156 ++++++++++++++++++++++++++++++ 6 files changed, 347 insertions(+), 347 deletions(-) delete mode 100644 libjulia/optimiser/ExpressionBreaker.cpp delete mode 100644 libjulia/optimiser/ExpressionBreaker.h create mode 100644 libjulia/optimiser/ExpressionSplitter.cpp create mode 100644 libjulia/optimiser/ExpressionSplitter.h delete mode 100644 test/libjulia/ExpressionBreaker.cpp create mode 100644 test/libjulia/ExpressionSplitter.cpp diff --git a/libjulia/optimiser/ExpressionBreaker.cpp b/libjulia/optimiser/ExpressionBreaker.cpp deleted file mode 100644 index 2273fa98..00000000 --- a/libjulia/optimiser/ExpressionBreaker.cpp +++ /dev/null @@ -1,105 +0,0 @@ -/* - 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 . -*/ -/** - * Optimiser component that turns complex expressions into multiple variable - * declarations. - */ - -#include - -#include - -#include - -#include - -#include - -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 saved; - swap(saved, m_statementsToPrefix); - - function>(Statement&)> f = - [&](Statement& _statement) -> boost::optional> { - 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(std::move(_expr)) - }); - _expr = Identifier{location, var}; -} diff --git a/libjulia/optimiser/ExpressionBreaker.h b/libjulia/optimiser/ExpressionBreaker.h deleted file mode 100644 index 28cfdbc9..00000000 --- a/libjulia/optimiser/ExpressionBreaker.h +++ /dev/null @@ -1,86 +0,0 @@ -/* - 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 . -*/ -/** - * Optimiser component that turns complex expressions into multiple variable - * declarations. - */ -#pragma once - -#include - -#include -#include - -#include - -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 m_statementsToPrefix; - NameDispenser& m_nameDispenser; -}; - -} -} diff --git a/libjulia/optimiser/ExpressionSplitter.cpp b/libjulia/optimiser/ExpressionSplitter.cpp new file mode 100644 index 00000000..4448a15b --- /dev/null +++ b/libjulia/optimiser/ExpressionSplitter.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 . +*/ +/** + * Optimiser component that turns complex expressions into multiple variable + * declarations. + */ + +#include + +#include + +#include + +#include + +#include + +using namespace std; +using namespace dev; +using namespace dev::julia; +using namespace dev::solidity; + +void ExpressionSplitter::operator()(FunctionalInstruction& _instruction) +{ + for (auto& arg: _instruction.arguments | boost::adaptors::reversed) + outlineExpression(arg); +} + +void ExpressionSplitter::operator()(FunctionCall& _funCall) +{ + for (auto& arg: _funCall.arguments | boost::adaptors::reversed) + outlineExpression(arg); +} + +void ExpressionSplitter::operator()(If& _if) +{ + outlineExpression(*_if.condition); + (*this)(_if.body); +} + +void ExpressionSplitter::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 ExpressionSplitter::operator()(ForLoop& _loop) +{ + (*this)(_loop.pre); + // Do not visit the condition because we cannot break expressions there. + (*this)(_loop.post); + (*this)(_loop.body); +} + +void ExpressionSplitter::operator()(Block& _block) +{ + vector saved; + swap(saved, m_statementsToPrefix); + + function>(Statement&)> f = + [&](Statement& _statement) -> boost::optional> { + 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 ExpressionSplitter::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(std::move(_expr)) + }); + _expr = Identifier{location, var}; +} diff --git a/libjulia/optimiser/ExpressionSplitter.h b/libjulia/optimiser/ExpressionSplitter.h new file mode 100644 index 00000000..324d2b13 --- /dev/null +++ b/libjulia/optimiser/ExpressionSplitter.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 . +*/ +/** + * Optimiser component that turns complex expressions into multiple variable + * declarations. + */ +#pragma once + +#include + +#include +#include + +#include + +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 ExpressionSplitter: public ASTModifier +{ +public: + explicit ExpressionSplitter(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 m_statementsToPrefix; + NameDispenser& m_nameDispenser; +}; + +} +} diff --git a/test/libjulia/ExpressionBreaker.cpp b/test/libjulia/ExpressionBreaker.cpp deleted file mode 100644 index de8d2251..00000000 --- a/test/libjulia/ExpressionBreaker.cpp +++ /dev/null @@ -1,156 +0,0 @@ -/* - 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 . -*/ -/** - * Unit tests for the expression breaker. - */ - -#include - -#include -#include - -#include - -#include - -#include -#include - -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() diff --git a/test/libjulia/ExpressionSplitter.cpp b/test/libjulia/ExpressionSplitter.cpp new file mode 100644 index 00000000..9707fa86 --- /dev/null +++ b/test/libjulia/ExpressionSplitter.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 . +*/ +/** + * Unit tests for the expression breaker. + */ + +#include + +#include +#include + +#include + +#include + +#include +#include + +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();\ + ExpressionSplitter{nameDispenser}(*result.first);\ + BOOST_CHECK_EQUAL(assembly::AsmPrinter{}(*result.first), format(_expectation, false));\ +}\ +while(false) + +BOOST_AUTO_TEST_SUITE(YulExpressionSplitter) + +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() -- cgit