From 33abdfab766da674514f490904c351286b1784c1 Mon Sep 17 00:00:00 2001 From: chriseth Date: Thu, 23 Nov 2017 17:42:06 +0100 Subject: Inlinable function filter. --- libjulia/optimiser/InlinableFunctionFilter.cpp | 68 ++++++++++++++++++++++++ libjulia/optimiser/InlinableFunctionFilter.h | 71 ++++++++++++++++++++++++++ 2 files changed, 139 insertions(+) create mode 100644 libjulia/optimiser/InlinableFunctionFilter.cpp create mode 100644 libjulia/optimiser/InlinableFunctionFilter.h diff --git a/libjulia/optimiser/InlinableFunctionFilter.cpp b/libjulia/optimiser/InlinableFunctionFilter.cpp new file mode 100644 index 00000000..db9f812d --- /dev/null +++ b/libjulia/optimiser/InlinableFunctionFilter.cpp @@ -0,0 +1,68 @@ +/* + 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 identifies functions to be inlined. + */ + +#include + +#include + +#include + +using namespace std; +using namespace dev; +using namespace dev::julia; + +void InlinableFunctionFilter::operator()(Identifier const& _identifier) +{ + checkAllowed(_identifier.name); + ASTWalker::operator()(_identifier); +} + +void InlinableFunctionFilter::operator()(FunctionCall const& _funCall) +{ + checkAllowed(_funCall.functionName.name); + ASTWalker::operator()(_funCall); +} + +void InlinableFunctionFilter::operator()(FunctionDefinition const& _function) +{ + if (_function.returnVariables.size() == 1 && _function.body.statements.size() == 1) + { + string const& retVariable = _function.returnVariables.front().name; + Statement const& bodyStatement = _function.body.statements.front(); + if (bodyStatement.type() == typeid(Assignment)) + { + Assignment const& assignment = boost::get(bodyStatement); + if (assignment.variableNames.size() == 1 && assignment.variableNames.front().name == retVariable) + { + // We cannot overwrite previous settings, because this function definition + // would not be valid here if we were searching inside a functionally inlinable + // function body. + solAssert(m_disallowedIdentifiers.empty() && !m_foundDisallowedIdentifier, ""); + m_disallowedIdentifiers = set{retVariable, _function.name}; + boost::apply_visitor(*this, *assignment.value); + if (!m_foundDisallowedIdentifier) + m_inlinableFunctions[_function.name] = &_function; + m_disallowedIdentifiers.clear(); + m_foundDisallowedIdentifier = false; + } + } + } + ASTWalker::operator()(_function.body); +} diff --git a/libjulia/optimiser/InlinableFunctionFilter.h b/libjulia/optimiser/InlinableFunctionFilter.h new file mode 100644 index 00000000..e0265059 --- /dev/null +++ b/libjulia/optimiser/InlinableFunctionFilter.h @@ -0,0 +1,71 @@ +/* + 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 identifies functions to be inlined. + */ + +#pragma once + +#include +#include + +#include + +#include + +namespace dev +{ +namespace julia +{ + +/** + * Optimiser component that finds functions that can be + * inlined inside functional expressions, i.e. functions that + * - have a single return parameter r + * - have a body like r := + * - neither reference themselves nor r in the right hand side + * + * This component can only be used on sources with unique names. + */ +class InlinableFunctionFilter: public ASTWalker +{ +public: + + std::map const& inlinableFunctions() const + { + return m_inlinableFunctions; + } + + using ASTWalker::operator(); + virtual void operator()(Identifier const& _identifier) override; + virtual void operator()(FunctionCall const& _funCall) override; + virtual void operator()(FunctionDefinition const& _function) override; + +private: + void checkAllowed(std::string const& _name) + { + if (m_disallowedIdentifiers.count(_name)) + m_foundDisallowedIdentifier = true; + } + + bool m_foundDisallowedIdentifier = false; + std::set m_disallowedIdentifiers; + std::map m_inlinableFunctions; +}; + +} +} -- cgit v1.2.3 From 4bd9bcbc774cd1e9bf9f5db385ea82dd1dd54c2e Mon Sep 17 00:00:00 2001 From: chriseth Date: Thu, 23 Nov 2017 17:42:42 +0100 Subject: Tests for inlinable function filter. --- test/libjulia/Inliner.cpp | 102 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 102 insertions(+) create mode 100644 test/libjulia/Inliner.cpp diff --git a/test/libjulia/Inliner.cpp b/test/libjulia/Inliner.cpp new file mode 100644 index 00000000..b583fafc --- /dev/null +++ b/test/libjulia/Inliner.cpp @@ -0,0 +1,102 @@ +/* + 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 . +*/ +/** + * @date 2017 + * Unit tests for the iulia function inliner. + */ + +#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::assembly; + +namespace +{ +string inlinableFunctions(string const& _source) +{ + auto ast = disambiguate(_source); + + InlinableFunctionFilter filter; + filter(*ast); + + return boost::algorithm::join( + filter.inlinableFunctions() | boost::adaptors::map_keys, + "," + ); +} + +} + +BOOST_AUTO_TEST_SUITE(IuliaInliner) + +BOOST_AUTO_TEST_CASE(smoke_test) +{ + BOOST_CHECK_EQUAL(inlinableFunctions("{ }"), ""); +} + +BOOST_AUTO_TEST_CASE(simple) +{ + BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256 { x := 2:u256 } }"), "f"); + BOOST_CHECK_EQUAL(inlinableFunctions(R"({ + function g(a:u256) -> b:u256 { b := a } + function f() -> x:u256 { x := g(2:u256) } + })"), "f,g"); +} + +BOOST_AUTO_TEST_CASE(simple_inside_structures) +{ + BOOST_CHECK_EQUAL(inlinableFunctions(R"({ + switch 2:u256 + case 2:u256 { + function g(a:u256) -> b:u256 { b := a } + function f() -> x:u256 { x := g(2:u256) } + } + })"), "f,g"); + BOOST_CHECK_EQUAL(inlinableFunctions(R"({ + for { + function g(a:u256) -> b:u256 { b := a } + } 1:u256 { + function f() -> x:u256 { x := g(2:u256) } + } + { + function h() -> y:u256 { y := 2:u256 } + } + })"), "f,g,h"); +} + +BOOST_AUTO_TEST_CASE(negative) +{ + BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256 { } }"), ""); + BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256 { x := 2:u256 {} } }"), ""); + BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256 { x := f() } }"), ""); + BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256 { x := x } }"), ""); + BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256, y:u256 { x := 2:u256 } }"), ""); +} + + +BOOST_AUTO_TEST_SUITE_END() -- cgit v1.2.3 From e7ef227226fb3548ecea59d44108a5923afeffc6 Mon Sep 17 00:00:00 2001 From: chriseth Date: Wed, 22 Nov 2017 11:11:48 +0100 Subject: Function inliner. --- libjulia/optimiser/FunctionalInliner.cpp | 71 ++++++++++++++++++++++++++ libjulia/optimiser/FunctionalInliner.h | 69 +++++++++++++++++++++++++ libjulia/optimiser/InlinableFunctionFilter.cpp | 2 + test/libjulia/Inliner.cpp | 67 +++++++++++++++++++++++- 4 files changed, 207 insertions(+), 2 deletions(-) create mode 100644 libjulia/optimiser/FunctionalInliner.cpp create mode 100644 libjulia/optimiser/FunctionalInliner.h diff --git a/libjulia/optimiser/FunctionalInliner.cpp b/libjulia/optimiser/FunctionalInliner.cpp new file mode 100644 index 00000000..0544ee5d --- /dev/null +++ b/libjulia/optimiser/FunctionalInliner.cpp @@ -0,0 +1,71 @@ +/* + 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 performs function inlining. + */ + +#include + +#include +#include +#include + +#include + +#include + +using namespace std; +using namespace dev; +using namespace dev::julia; +using namespace dev::solidity; + +void FunctionalInliner::run() +{ + InlinableFunctionFilter filter; + filter(m_block); + m_inlinableFunctions = filter.inlinableFunctions(); + + (*this)(m_block); +} + + +void FunctionalInliner::visit(Expression& _expression) +{ + ASTModifier::visit(_expression); + if (_expression.type() == typeid(FunctionCall)) + { + FunctionCall& funCall = boost::get(_expression); + + bool movable = boost::algorithm::all_of( + funCall.arguments, + [=](Expression const& _arg) { return MovableChecker(_arg).movable(); } + ); + if (m_inlinableFunctions.count(funCall.functionName.name) && movable) + { + FunctionDefinition const& fun = *m_inlinableFunctions.at(funCall.functionName.name); + map substitutions; + for (size_t i = 0; i < fun.parameters.size(); ++i) + substitutions[fun.parameters[i].name] = &funCall.arguments[i]; + _expression = Substitution(substitutions).translate(*boost::get(fun.body.statements.front()).value); + + // TODO actually in the process of inlining, we could also make a function non-inlinable + // because it could now call itself + + // If two functions call each other, we have to exit after some iterations. + } + } +} diff --git a/libjulia/optimiser/FunctionalInliner.h b/libjulia/optimiser/FunctionalInliner.h new file mode 100644 index 00000000..30c972ff --- /dev/null +++ b/libjulia/optimiser/FunctionalInliner.h @@ -0,0 +1,69 @@ +/* + 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 performs function inlining. + */ +#pragma once + +#include + +#include + +#include + +#include +#include + +#include + +namespace dev +{ +namespace julia +{ + +/** + * Optimiser component that modifies an AST in place, inlining functions that can be + * inlined inside functional expressions, i.e. functions that + * - return a single value + * - have a body like r := + * - neither reference themselves nor r in the right hand side + * + * Furthermore, the arguments of the function call cannot have any side-effects. + * + * This component can only be used on sources with unique names. + */ +class FunctionalInliner: public ASTModifier +{ +public: + FunctionalInliner(Block& _block): + m_block(_block) + {} + + void run(); + +private: + virtual void visit(Expression& _expression) override; + + std::map m_inlinableFunctions; + std::map m_varReplacements; + + Block& m_block; +}; + + +} +} diff --git a/libjulia/optimiser/InlinableFunctionFilter.cpp b/libjulia/optimiser/InlinableFunctionFilter.cpp index db9f812d..37e21f0d 100644 --- a/libjulia/optimiser/InlinableFunctionFilter.cpp +++ b/libjulia/optimiser/InlinableFunctionFilter.cpp @@ -51,6 +51,8 @@ void InlinableFunctionFilter::operator()(FunctionDefinition const& _function) Assignment const& assignment = boost::get(bodyStatement); if (assignment.variableNames.size() == 1 && assignment.variableNames.front().name == retVariable) { + // FIXME: use code size metric here + // We cannot overwrite previous settings, because this function definition // would not be valid here if we were searching inside a functionally inlinable // function body. diff --git a/test/libjulia/Inliner.cpp b/test/libjulia/Inliner.cpp index b583fafc..53776acf 100644 --- a/test/libjulia/Inliner.cpp +++ b/test/libjulia/Inliner.cpp @@ -24,6 +24,8 @@ #include #include +#include + #include #include @@ -42,7 +44,7 @@ string inlinableFunctions(string const& _source) auto ast = disambiguate(_source); InlinableFunctionFilter filter; - filter(*ast); + filter(ast); return boost::algorithm::join( filter.inlinableFunctions() | boost::adaptors::map_keys, @@ -50,9 +52,15 @@ string inlinableFunctions(string const& _source) ); } +string inlineFunctions(string const& _source, bool _julia = true) +{ + auto ast = disambiguate(_source, _julia); + FunctionalInliner(ast).run(); + return AsmPrinter(_julia)(ast); +} } -BOOST_AUTO_TEST_SUITE(IuliaInliner) +BOOST_AUTO_TEST_SUITE(IuliaInlinableFunctionFilter) BOOST_AUTO_TEST_CASE(smoke_test) { @@ -99,4 +107,59 @@ BOOST_AUTO_TEST_CASE(negative) } +BOOST_AUTO_TEST_SUITE_END() + +BOOST_AUTO_TEST_SUITE(IuliaFunctionInliner) + +BOOST_AUTO_TEST_CASE(simple) +{ + BOOST_CHECK_EQUAL( + inlineFunctions("{ function f() -> x:u256 { x := 2:u256 } let y:u256 := f() }"), + format("{ function f() -> x:u256 { x := 2:u256 } let y:u256 := 2:u256 }") + ); +} + +BOOST_AUTO_TEST_CASE(with_args) +{ + BOOST_CHECK_EQUAL( + inlineFunctions("{ function f(a:u256) -> x:u256 { x := a } let y:u256 := f(7:u256) }"), + format("{ function f(a:u256) -> x:u256 { x := a } let y:u256 := 7:u256 }") + ); +} + +BOOST_AUTO_TEST_CASE(no_inline_with_mload) +{ + // Does not inline because mload could be moved out of sequence + BOOST_CHECK_EQUAL( + inlineFunctions("{ function f(a) -> x { x := a } let y := f(mload(2)) }", false), + format("{ function f(a) -> x { x := a } let y := f(mload(2)) }", false) + ); +} + +BOOST_AUTO_TEST_CASE(complex_with_evm) +{ + BOOST_CHECK_EQUAL( + inlineFunctions("{ function f(a) -> x { x := add(a, a) } let y := f(calldatasize()) }", false), + format("{ function f(a) -> x { x := add(a, a) } let y := add(calldatasize(), calldatasize()) }", false) + ); +} + +BOOST_AUTO_TEST_CASE(double_calls) +{ + BOOST_CHECK_EQUAL( + inlineFunctions(R"({ + function f(a) -> x { x := add(a, a) } + function g(b, c) -> y { y := mul(mload(c), f(b)) } + let y := g(calldatasize(), 7) + })", false), + format(R"({ + function f(a) -> x { x := add(a, a) } + function g(b, c) -> y { y := mul(mload(c), add(b, b)) } + let y_1 := mul(mload(7), add(calldatasize(), calldatasize())) + })", false) + ); +} + +// TODO test double recursive calls + BOOST_AUTO_TEST_SUITE_END() -- cgit v1.2.3 From a7ae7c6d04c77f3cdc51644f929d9dbaaa687220 Mon Sep 17 00:00:00 2001 From: chriseth Date: Tue, 5 Dec 2017 18:41:26 +0100 Subject: Tests for functional inliner. --- test/libjulia/Inliner.cpp | 24 ++++++++++++++++++++++-- 1 file changed, 22 insertions(+), 2 deletions(-) diff --git a/test/libjulia/Inliner.cpp b/test/libjulia/Inliner.cpp index 53776acf..93444500 100644 --- a/test/libjulia/Inliner.cpp +++ b/test/libjulia/Inliner.cpp @@ -35,7 +35,7 @@ using namespace std; using namespace dev; using namespace dev::julia; using namespace dev::julia::test; -using namespace dev::solidity::assembly; +using namespace dev::solidity; namespace { @@ -56,7 +56,7 @@ string inlineFunctions(string const& _source, bool _julia = true) { auto ast = disambiguate(_source, _julia); FunctionalInliner(ast).run(); - return AsmPrinter(_julia)(ast); + return assembly::AsmPrinter(_julia)(ast); } } @@ -136,6 +136,26 @@ BOOST_AUTO_TEST_CASE(no_inline_with_mload) ); } +BOOST_AUTO_TEST_CASE(no_move_with_side_effects) +{ + // The calls to g and h cannot be moved because g and h are not movable. Therefore, the call + // to f is not inlined. + BOOST_CHECK_EQUAL( + inlineFunctions(R"({ + function f(a, b) -> x { x := add(b, a) } + function g() -> y { y := mload(0) mstore(0, 4) } + function h() -> z { mstore(0, 4) z := mload(0) } + let r := f(g(), h()) + })", false), + format(R"({ + function f(a, b) -> x { x := add(b, a) } + function g() -> y { y := mload(0) mstore(0, 4) } + function h() -> z { mstore(0, 4) z := mload(0) } + let r := f(g(), h()) + })", false) + ); +} + BOOST_AUTO_TEST_CASE(complex_with_evm) { BOOST_CHECK_EQUAL( -- cgit v1.2.3 From 3960f4184da94ebc469ab4a38f5b30579386520e Mon Sep 17 00:00:00 2001 From: chriseth Date: Tue, 6 Feb 2018 15:30:36 +0100 Subject: Rename expression inliner. --- libjulia/optimiser/ExpressionInliner.cpp | 74 ++++++++++++++++++++++ libjulia/optimiser/ExpressionInliner.h | 74 ++++++++++++++++++++++ libjulia/optimiser/FunctionalInliner.cpp | 71 --------------------- libjulia/optimiser/FunctionalInliner.h | 69 -------------------- .../InlinableExpressionFunctionFinder.cpp | 70 ++++++++++++++++++++ .../optimiser/InlinableExpressionFunctionFinder.h | 71 +++++++++++++++++++++ libjulia/optimiser/InlinableFunctionFilter.cpp | 70 -------------------- libjulia/optimiser/InlinableFunctionFilter.h | 71 --------------------- 8 files changed, 289 insertions(+), 281 deletions(-) create mode 100644 libjulia/optimiser/ExpressionInliner.cpp create mode 100644 libjulia/optimiser/ExpressionInliner.h delete mode 100644 libjulia/optimiser/FunctionalInliner.cpp delete mode 100644 libjulia/optimiser/FunctionalInliner.h create mode 100644 libjulia/optimiser/InlinableExpressionFunctionFinder.cpp create mode 100644 libjulia/optimiser/InlinableExpressionFunctionFinder.h delete mode 100644 libjulia/optimiser/InlinableFunctionFilter.cpp delete mode 100644 libjulia/optimiser/InlinableFunctionFilter.h diff --git a/libjulia/optimiser/ExpressionInliner.cpp b/libjulia/optimiser/ExpressionInliner.cpp new file mode 100644 index 00000000..450769fd --- /dev/null +++ b/libjulia/optimiser/ExpressionInliner.cpp @@ -0,0 +1,74 @@ +/* + 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 performs function inlining inside expressions. + */ + +#include + +#include +#include +#include + +#include + +#include + +using namespace std; +using namespace dev; +using namespace dev::julia; +using namespace dev::solidity; + +void ExpressionInliner::run() +{ + InlinableExpressionFunctionFinder funFinder; + funFinder(m_block); + m_inlinableFunctions = funFinder.inlinableFunctions(); + + (*this)(m_block); +} + + +void ExpressionInliner::operator()(FunctionDefinition& _fun) +{ + ASTModifier::operator()(_fun); +} + +void ExpressionInliner::visit(Expression& _expression) +{ + ASTModifier::visit(_expression); + if (_expression.type() == typeid(FunctionCall)) + { + FunctionCall& funCall = boost::get(_expression); + + bool movable = boost::algorithm::all_of( + funCall.arguments, + [=](Expression const& _arg) { return MovableChecker(_arg).movable(); } + ); + if (m_inlinableFunctions.count(funCall.functionName.name) && movable) + { + FunctionDefinition const& fun = *m_inlinableFunctions.at(funCall.functionName.name); + map substitutions; + for (size_t i = 0; i < fun.parameters.size(); ++i) + substitutions[fun.parameters[i].name] = &funCall.arguments[i]; + _expression = Substitution(substitutions).translate(*boost::get(fun.body.statements.front()).value); + + // TODO Add metric! This metric should perform well on a pair of functions who + // call each other recursively. + } + } +} diff --git a/libjulia/optimiser/ExpressionInliner.h b/libjulia/optimiser/ExpressionInliner.h new file mode 100644 index 00000000..10d7659c --- /dev/null +++ b/libjulia/optimiser/ExpressionInliner.h @@ -0,0 +1,74 @@ +/* + 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 performs function inlining. + */ +#pragma once + +#include + +#include + +#include + +#include +#include + +#include + +namespace dev +{ +namespace julia +{ + +/** + * Optimiser component that modifies an AST in place, inlining functions that can be + * inlined inside functional expressions, i.e. functions that + * - return a single value + * - have a body like r := + * - neither reference themselves nor r in the right hand side + * + * Furthermore, the arguments of the function call cannot have any side-effects. + * + * This component can only be used on sources with unique names. + */ +class ExpressionInliner: public ASTModifier +{ +public: + ExpressionInliner(Block& _block): + m_block(_block) + {} + + void run(); + + using ASTModifier::operator(); + virtual void operator()(FunctionDefinition& _fun) override; + + virtual void visit(Expression& _expression) override; + +private: + std::map m_inlinableFunctions; + std::map m_varReplacements; + /// Set of functions we are currently visiting inside. + std::set m_currentFunctions; + + Block& m_block; +}; + + +} +} diff --git a/libjulia/optimiser/FunctionalInliner.cpp b/libjulia/optimiser/FunctionalInliner.cpp deleted file mode 100644 index 0544ee5d..00000000 --- a/libjulia/optimiser/FunctionalInliner.cpp +++ /dev/null @@ -1,71 +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 performs function inlining. - */ - -#include - -#include -#include -#include - -#include - -#include - -using namespace std; -using namespace dev; -using namespace dev::julia; -using namespace dev::solidity; - -void FunctionalInliner::run() -{ - InlinableFunctionFilter filter; - filter(m_block); - m_inlinableFunctions = filter.inlinableFunctions(); - - (*this)(m_block); -} - - -void FunctionalInliner::visit(Expression& _expression) -{ - ASTModifier::visit(_expression); - if (_expression.type() == typeid(FunctionCall)) - { - FunctionCall& funCall = boost::get(_expression); - - bool movable = boost::algorithm::all_of( - funCall.arguments, - [=](Expression const& _arg) { return MovableChecker(_arg).movable(); } - ); - if (m_inlinableFunctions.count(funCall.functionName.name) && movable) - { - FunctionDefinition const& fun = *m_inlinableFunctions.at(funCall.functionName.name); - map substitutions; - for (size_t i = 0; i < fun.parameters.size(); ++i) - substitutions[fun.parameters[i].name] = &funCall.arguments[i]; - _expression = Substitution(substitutions).translate(*boost::get(fun.body.statements.front()).value); - - // TODO actually in the process of inlining, we could also make a function non-inlinable - // because it could now call itself - - // If two functions call each other, we have to exit after some iterations. - } - } -} diff --git a/libjulia/optimiser/FunctionalInliner.h b/libjulia/optimiser/FunctionalInliner.h deleted file mode 100644 index 30c972ff..00000000 --- a/libjulia/optimiser/FunctionalInliner.h +++ /dev/null @@ -1,69 +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 performs function inlining. - */ -#pragma once - -#include - -#include - -#include - -#include -#include - -#include - -namespace dev -{ -namespace julia -{ - -/** - * Optimiser component that modifies an AST in place, inlining functions that can be - * inlined inside functional expressions, i.e. functions that - * - return a single value - * - have a body like r := - * - neither reference themselves nor r in the right hand side - * - * Furthermore, the arguments of the function call cannot have any side-effects. - * - * This component can only be used on sources with unique names. - */ -class FunctionalInliner: public ASTModifier -{ -public: - FunctionalInliner(Block& _block): - m_block(_block) - {} - - void run(); - -private: - virtual void visit(Expression& _expression) override; - - std::map m_inlinableFunctions; - std::map m_varReplacements; - - Block& m_block; -}; - - -} -} diff --git a/libjulia/optimiser/InlinableExpressionFunctionFinder.cpp b/libjulia/optimiser/InlinableExpressionFunctionFinder.cpp new file mode 100644 index 00000000..2097e091 --- /dev/null +++ b/libjulia/optimiser/InlinableExpressionFunctionFinder.cpp @@ -0,0 +1,70 @@ +/* + 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 identifies functions to be inlined. + */ + +#include + +#include + +#include + +using namespace std; +using namespace dev; +using namespace dev::julia; + +void InlinableExpressionFunctionFinder::operator()(Identifier const& _identifier) +{ + checkAllowed(_identifier.name); + ASTWalker::operator()(_identifier); +} + +void InlinableExpressionFunctionFinder::operator()(FunctionCall const& _funCall) +{ + checkAllowed(_funCall.functionName.name); + ASTWalker::operator()(_funCall); +} + +void InlinableExpressionFunctionFinder::operator()(FunctionDefinition const& _function) +{ + if (_function.returnVariables.size() == 1 && _function.body.statements.size() == 1) + { + string const& retVariable = _function.returnVariables.front().name; + Statement const& bodyStatement = _function.body.statements.front(); + if (bodyStatement.type() == typeid(Assignment)) + { + Assignment const& assignment = boost::get(bodyStatement); + if (assignment.variableNames.size() == 1 && assignment.variableNames.front().name == retVariable) + { + // FIXME: use code size metric here + + // We cannot overwrite previous settings, because this function definition + // would not be valid here if we were searching inside a functionally inlinable + // function body. + solAssert(m_disallowedIdentifiers.empty() && !m_foundDisallowedIdentifier, ""); + m_disallowedIdentifiers = set{retVariable, _function.name}; + boost::apply_visitor(*this, *assignment.value); + if (!m_foundDisallowedIdentifier) + m_inlinableFunctions[_function.name] = &_function; + m_disallowedIdentifiers.clear(); + m_foundDisallowedIdentifier = false; + } + } + } + ASTWalker::operator()(_function.body); +} diff --git a/libjulia/optimiser/InlinableExpressionFunctionFinder.h b/libjulia/optimiser/InlinableExpressionFunctionFinder.h new file mode 100644 index 00000000..36cb557a --- /dev/null +++ b/libjulia/optimiser/InlinableExpressionFunctionFinder.h @@ -0,0 +1,71 @@ +/* + 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 identifies functions to be inlined. + */ + +#pragma once + +#include +#include + +#include + +#include + +namespace dev +{ +namespace julia +{ + +/** + * Optimiser component that finds functions that can be + * inlined inside functional expressions, i.e. functions that + * - have a single return parameter r + * - have a body like r := + * - neither reference themselves nor r in the right hand side + * + * This component can only be used on sources with unique names. + */ +class InlinableExpressionFunctionFinder: public ASTWalker +{ +public: + + std::map const& inlinableFunctions() const + { + return m_inlinableFunctions; + } + + using ASTWalker::operator(); + virtual void operator()(Identifier const& _identifier) override; + virtual void operator()(FunctionCall const& _funCall) override; + virtual void operator()(FunctionDefinition const& _function) override; + +private: + void checkAllowed(std::string const& _name) + { + if (m_disallowedIdentifiers.count(_name)) + m_foundDisallowedIdentifier = true; + } + + bool m_foundDisallowedIdentifier = false; + std::set m_disallowedIdentifiers; + std::map m_inlinableFunctions; +}; + +} +} diff --git a/libjulia/optimiser/InlinableFunctionFilter.cpp b/libjulia/optimiser/InlinableFunctionFilter.cpp deleted file mode 100644 index 37e21f0d..00000000 --- a/libjulia/optimiser/InlinableFunctionFilter.cpp +++ /dev/null @@ -1,70 +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 identifies functions to be inlined. - */ - -#include - -#include - -#include - -using namespace std; -using namespace dev; -using namespace dev::julia; - -void InlinableFunctionFilter::operator()(Identifier const& _identifier) -{ - checkAllowed(_identifier.name); - ASTWalker::operator()(_identifier); -} - -void InlinableFunctionFilter::operator()(FunctionCall const& _funCall) -{ - checkAllowed(_funCall.functionName.name); - ASTWalker::operator()(_funCall); -} - -void InlinableFunctionFilter::operator()(FunctionDefinition const& _function) -{ - if (_function.returnVariables.size() == 1 && _function.body.statements.size() == 1) - { - string const& retVariable = _function.returnVariables.front().name; - Statement const& bodyStatement = _function.body.statements.front(); - if (bodyStatement.type() == typeid(Assignment)) - { - Assignment const& assignment = boost::get(bodyStatement); - if (assignment.variableNames.size() == 1 && assignment.variableNames.front().name == retVariable) - { - // FIXME: use code size metric here - - // We cannot overwrite previous settings, because this function definition - // would not be valid here if we were searching inside a functionally inlinable - // function body. - solAssert(m_disallowedIdentifiers.empty() && !m_foundDisallowedIdentifier, ""); - m_disallowedIdentifiers = set{retVariable, _function.name}; - boost::apply_visitor(*this, *assignment.value); - if (!m_foundDisallowedIdentifier) - m_inlinableFunctions[_function.name] = &_function; - m_disallowedIdentifiers.clear(); - m_foundDisallowedIdentifier = false; - } - } - } - ASTWalker::operator()(_function.body); -} diff --git a/libjulia/optimiser/InlinableFunctionFilter.h b/libjulia/optimiser/InlinableFunctionFilter.h deleted file mode 100644 index e0265059..00000000 --- a/libjulia/optimiser/InlinableFunctionFilter.h +++ /dev/null @@ -1,71 +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 identifies functions to be inlined. - */ - -#pragma once - -#include -#include - -#include - -#include - -namespace dev -{ -namespace julia -{ - -/** - * Optimiser component that finds functions that can be - * inlined inside functional expressions, i.e. functions that - * - have a single return parameter r - * - have a body like r := - * - neither reference themselves nor r in the right hand side - * - * This component can only be used on sources with unique names. - */ -class InlinableFunctionFilter: public ASTWalker -{ -public: - - std::map const& inlinableFunctions() const - { - return m_inlinableFunctions; - } - - using ASTWalker::operator(); - virtual void operator()(Identifier const& _identifier) override; - virtual void operator()(FunctionCall const& _funCall) override; - virtual void operator()(FunctionDefinition const& _function) override; - -private: - void checkAllowed(std::string const& _name) - { - if (m_disallowedIdentifiers.count(_name)) - m_foundDisallowedIdentifier = true; - } - - bool m_foundDisallowedIdentifier = false; - std::set m_disallowedIdentifiers; - std::map m_inlinableFunctions; -}; - -} -} -- cgit v1.2.3 From d7863e2054fe5617aa1de93bb9410b487d1af5d4 Mon Sep 17 00:00:00 2001 From: chriseth Date: Tue, 6 Feb 2018 15:30:43 +0100 Subject: Test about recursively calling functions. --- test/libjulia/Inliner.cpp | 28 +++++++++++++++++++++------- 1 file changed, 21 insertions(+), 7 deletions(-) diff --git a/test/libjulia/Inliner.cpp b/test/libjulia/Inliner.cpp index 93444500..b6a7b921 100644 --- a/test/libjulia/Inliner.cpp +++ b/test/libjulia/Inliner.cpp @@ -21,8 +21,8 @@ #include -#include -#include +#include +#include #include @@ -43,11 +43,11 @@ string inlinableFunctions(string const& _source) { auto ast = disambiguate(_source); - InlinableFunctionFilter filter; - filter(ast); + InlinableExpressionFunctionFinder funFinder; + funFinder(ast); return boost::algorithm::join( - filter.inlinableFunctions() | boost::adaptors::map_keys, + funFinder.inlinableFunctions() | boost::adaptors::map_keys, "," ); } @@ -55,7 +55,7 @@ string inlinableFunctions(string const& _source) string inlineFunctions(string const& _source, bool _julia = true) { auto ast = disambiguate(_source, _julia); - FunctionalInliner(ast).run(); + ExpressionInliner(ast).run(); return assembly::AsmPrinter(_julia)(ast); } } @@ -180,6 +180,20 @@ BOOST_AUTO_TEST_CASE(double_calls) ); } -// TODO test double recursive calls +BOOST_AUTO_TEST_CASE(double_recursive_calls) +{ + BOOST_CHECK_EQUAL( + inlineFunctions(R"({ + function f(a, r) -> x { x := g(a, g(r, r)) } + function g(b, s) -> y { y := f(b, f(s, s)) } + let y := g(calldatasize(), 7) + })", false), + format(R"({ + function f(a, r) -> x { x := g(a, f(r, f(r, r))) } + function g(b, s) -> y { y := f(b, g(s, f(s, f(s, s))))} + let y_1 := f(calldatasize(), g(7, f(7, f(7, 7)))) + })", false) + ); +} BOOST_AUTO_TEST_SUITE_END() -- cgit v1.2.3 From 9429e18dda7d65bea0c3e67756b5b3a6405664c7 Mon Sep 17 00:00:00 2001 From: chriseth Date: Tue, 6 Feb 2018 23:00:33 +0100 Subject: Fix tests for old precompiler. --- test/libjulia/Inliner.cpp | 106 +++++++++++++++++++++++----------------------- 1 file changed, 53 insertions(+), 53 deletions(-) diff --git a/test/libjulia/Inliner.cpp b/test/libjulia/Inliner.cpp index b6a7b921..88b51f28 100644 --- a/test/libjulia/Inliner.cpp +++ b/test/libjulia/Inliner.cpp @@ -70,31 +70,31 @@ BOOST_AUTO_TEST_CASE(smoke_test) BOOST_AUTO_TEST_CASE(simple) { BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256 { x := 2:u256 } }"), "f"); - BOOST_CHECK_EQUAL(inlinableFunctions(R"({ - function g(a:u256) -> b:u256 { b := a } - function f() -> x:u256 { x := g(2:u256) } - })"), "f,g"); + BOOST_CHECK_EQUAL(inlinableFunctions("{" + "function g(a:u256) -> b:u256 { b := a }" + "function f() -> x:u256 { x := g(2:u256) }" + "}"), "f,g"); } BOOST_AUTO_TEST_CASE(simple_inside_structures) { - BOOST_CHECK_EQUAL(inlinableFunctions(R"({ - switch 2:u256 - case 2:u256 { - function g(a:u256) -> b:u256 { b := a } - function f() -> x:u256 { x := g(2:u256) } - } - })"), "f,g"); - BOOST_CHECK_EQUAL(inlinableFunctions(R"({ - for { - function g(a:u256) -> b:u256 { b := a } - } 1:u256 { - function f() -> x:u256 { x := g(2:u256) } - } - { - function h() -> y:u256 { y := 2:u256 } - } - })"), "f,g,h"); + BOOST_CHECK_EQUAL(inlinableFunctions("{" + "switch 2:u256 " + "case 2:u256 {" + "function g(a:u256) -> b:u256 { b := a }" + "function f() -> x:u256 { x := g(2:u256) }" + "}" + "}"), "f,g"); + BOOST_CHECK_EQUAL(inlinableFunctions("{" + "for {" + "function g(a:u256) -> b:u256 { b := a }" + "} 1:u256 {" + "function f() -> x:u256 { x := g(2:u256) }" + "}" + "{" + "function h() -> y:u256 { y := 2:u256 }" + "}" + "}"), "f,g,h"); } BOOST_AUTO_TEST_CASE(negative) @@ -141,18 +141,18 @@ BOOST_AUTO_TEST_CASE(no_move_with_side_effects) // The calls to g and h cannot be moved because g and h are not movable. Therefore, the call // to f is not inlined. BOOST_CHECK_EQUAL( - inlineFunctions(R"({ - function f(a, b) -> x { x := add(b, a) } - function g() -> y { y := mload(0) mstore(0, 4) } - function h() -> z { mstore(0, 4) z := mload(0) } - let r := f(g(), h()) - })", false), - format(R"({ - function f(a, b) -> x { x := add(b, a) } - function g() -> y { y := mload(0) mstore(0, 4) } - function h() -> z { mstore(0, 4) z := mload(0) } - let r := f(g(), h()) - })", false) + inlineFunctions("{" + "function f(a, b) -> x { x := add(b, a) }" + "function g() -> y { y := mload(0) mstore(0, 4) }" + "function h() -> z { mstore(0, 4) z := mload(0) }" + "let r := f(g(), h())" + "}", false), + format("{" + "function f(a, b) -> x { x := add(b, a) }" + "function g() -> y { y := mload(0) mstore(0, 4) }" + "function h() -> z { mstore(0, 4) z := mload(0) }" + "let r := f(g(), h())" + "}", false) ); } @@ -167,32 +167,32 @@ BOOST_AUTO_TEST_CASE(complex_with_evm) BOOST_AUTO_TEST_CASE(double_calls) { BOOST_CHECK_EQUAL( - inlineFunctions(R"({ - function f(a) -> x { x := add(a, a) } - function g(b, c) -> y { y := mul(mload(c), f(b)) } - let y := g(calldatasize(), 7) - })", false), - format(R"({ - function f(a) -> x { x := add(a, a) } - function g(b, c) -> y { y := mul(mload(c), add(b, b)) } - let y_1 := mul(mload(7), add(calldatasize(), calldatasize())) - })", false) + inlineFunctions("{" + "function f(a) -> x { x := add(a, a) }" + "function g(b, c) -> y { y := mul(mload(c), f(b)) }" + "let y := g(calldatasize(), 7)" + "}", false), + format("{" + "function f(a) -> x { x := add(a, a) }" + "function g(b, c) -> y { y := mul(mload(c), add(b, b)) }" + "let y_1 := mul(mload(7), add(calldatasize(), calldatasize()))" + "}", false) ); } BOOST_AUTO_TEST_CASE(double_recursive_calls) { BOOST_CHECK_EQUAL( - inlineFunctions(R"({ - function f(a, r) -> x { x := g(a, g(r, r)) } - function g(b, s) -> y { y := f(b, f(s, s)) } - let y := g(calldatasize(), 7) - })", false), - format(R"({ - function f(a, r) -> x { x := g(a, f(r, f(r, r))) } - function g(b, s) -> y { y := f(b, g(s, f(s, f(s, s))))} - let y_1 := f(calldatasize(), g(7, f(7, f(7, 7)))) - })", false) + inlineFunctions("{" + "function f(a, r) -> x { x := g(a, g(r, r)) }" + "function g(b, s) -> y { y := f(b, f(s, s)) }" + "let y := g(calldatasize(), 7)" + "}", false), + format("{" + "function f(a, r) -> x { x := g(a, f(r, f(r, r))) }" + "function g(b, s) -> y { y := f(b, g(s, f(s, f(s, s))))}" + "let y_1 := f(calldatasize(), g(7, f(7, f(7, 7))))" + "}", false) ); } -- cgit v1.2.3