diff options
| -rw-r--r-- | libjulia/optimiser/FullInliner.cpp | 262 | ||||
| -rw-r--r-- | libjulia/optimiser/FullInliner.h | 178 | ||||
| -rw-r--r-- | libjulia/optimiser/NameCollector.cpp | 1 | ||||
| -rw-r--r-- | libjulia/optimiser/NameCollector.h | 9 | ||||
| -rw-r--r-- | libjulia/optimiser/NameDispenser.cpp | 38 | ||||
| -rw-r--r-- | libjulia/optimiser/NameDispenser.h | 37 | ||||
| -rw-r--r-- | test/libjulia/Inliner.cpp | 166 |
7 files changed, 676 insertions, 15 deletions
diff --git a/libjulia/optimiser/FullInliner.cpp b/libjulia/optimiser/FullInliner.cpp new file mode 100644 index 00000000..05d70729 --- /dev/null +++ b/libjulia/optimiser/FullInliner.cpp @@ -0,0 +1,262 @@ +/* + 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 performs function inlining for arbitrary functions. + */ + +#include <libjulia/optimiser/FullInliner.h> + +#include <libjulia/optimiser/ASTCopier.h> +#include <libjulia/optimiser/ASTWalker.h> +#include <libjulia/optimiser/NameCollector.h> +#include <libjulia/optimiser/Semantics.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libsolidity/interface/Exceptions.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; + + + +FullInliner::FullInliner(Block& _ast): + m_ast(_ast) +{ + solAssert(m_ast.statements.size() >= 1, ""); + solAssert(m_ast.statements.front().type() == typeid(Block), ""); + m_nameDispenser.m_usedNames = NameCollector(m_ast).names(); + + for (size_t i = 1; i < m_ast.statements.size(); ++i) + { + solAssert(m_ast.statements.at(i).type() == typeid(FunctionDefinition), ""); + FunctionDefinition& fun = boost::get<FunctionDefinition>(m_ast.statements.at(i)); + m_functions[fun.name] = &fun; + m_functionsToVisit.insert(&fun); + } +} + +void FullInliner::run() +{ + solAssert(m_ast.statements[0].type() == typeid(Block), ""); + InlineModifier(*this, m_nameDispenser, "").visit(m_ast.statements[0]); + while (!m_functionsToVisit.empty()) + handleFunction(**m_functionsToVisit.begin()); +} + +void FullInliner::handleFunction(FunctionDefinition& _fun) +{ + if (!m_functionsToVisit.count(&_fun)) + return; + m_functionsToVisit.erase(&_fun); + (InlineModifier(*this, m_nameDispenser, _fun.name))(_fun.body); +} + +void InlineModifier::operator()(FunctionalInstruction& _instruction) +{ + visitArguments(_instruction.arguments); +} + +void InlineModifier::operator()(FunctionCall&) +{ + solAssert(false, "Should be handled in visit() instead."); +} + +void InlineModifier::operator()(ForLoop& _loop) +{ + (*this)(_loop.pre); + // Do not visit the condition because we cannot inline there. + (*this)(_loop.post); + (*this)(_loop.body); +} + +void InlineModifier::operator()(Block& _block) +{ + // This is only used if needed to minimize the number of move operations. + vector<Statement> modifiedStatements; + for (size_t i = 0; i < _block.statements.size(); ++i) + { + visit(_block.statements.at(i)); + if (!m_statementsToPrefix.empty()) + { + if (modifiedStatements.empty()) + std::move( + _block.statements.begin(), + _block.statements.begin() + i, + back_inserter(modifiedStatements) + ); + modifiedStatements += std::move(m_statementsToPrefix); + m_statementsToPrefix.clear(); + } + if (!modifiedStatements.empty()) + modifiedStatements.emplace_back(std::move(_block.statements[i])); + } + if (!modifiedStatements.empty()) + _block.statements = std::move(modifiedStatements); +} + +void InlineModifier::visit(Expression& _expression) +{ + if (_expression.type() != typeid(FunctionCall)) + return ASTModifier::visit(_expression); + + FunctionCall& funCall = boost::get<FunctionCall>(_expression); + FunctionDefinition& fun = m_driver.function(funCall.functionName.name); + + m_driver.handleFunction(fun); + + // TODO: Insert good heuristic here. Perhaps implement that inside the driver. + bool doInline = funCall.functionName.name != m_currentFunction; + + if (fun.returnVariables.size() > 1) + doInline = false; + + { + vector<string> argNames; + vector<string> argTypes; + for (auto const& arg: fun.parameters) + { + argNames.push_back(fun.name + "_" + arg.name); + argTypes.push_back(arg.type); + } + visitArguments(funCall.arguments, argNames, argTypes, doInline); + } + + if (!doInline) + return; + + map<string, string> variableReplacements; + for (size_t i = 0; i < funCall.arguments.size(); ++i) + variableReplacements[fun.parameters[i].name] = boost::get<Identifier>(funCall.arguments[i]).name; + if (fun.returnVariables.empty()) + _expression = noop(funCall.location); + else + { + string returnVariable = fun.returnVariables[0].name; + variableReplacements[returnVariable] = newName(fun.name + "_" + returnVariable); + + m_statementsToPrefix.emplace_back(VariableDeclaration{ + funCall.location, + {{funCall.location, variableReplacements[returnVariable], fun.returnVariables[0].type}}, + {} + }); + _expression = Identifier{funCall.location, variableReplacements[returnVariable]}; + } + m_statementsToPrefix.emplace_back(BodyCopier(m_nameDispenser, fun.name + "_", variableReplacements)(fun.body)); +} + +void InlineModifier::visit(Statement& _statement) +{ + ASTModifier::visit(_statement); + // Replace pop(0) expression statemets (and others) by empty blocks. + if (_statement.type() == typeid(ExpressionStatement)) + { + ExpressionStatement& expSt = boost::get<ExpressionStatement&>(_statement); + if (expSt.expression.type() == typeid(FunctionalInstruction)) + { + FunctionalInstruction& funInstr = boost::get<FunctionalInstruction&>(expSt.expression); + if (funInstr.instruction == solidity::Instruction::POP) + if (MovableChecker(funInstr.arguments.at(0)).movable()) + _statement = Block{expSt.location, {}}; + } + } +} + +void InlineModifier::visitArguments( + vector<Expression>& _arguments, + vector<string> const& _nameHints, + vector<string> const& _types, + bool _moveToFront +) +{ + // If one of the elements moves parts to the front, all other elements right of it + // also have to be moved to the front to keep the order of evaluation. + vector<Statement> prefix; + for (size_t i = 0; i < _arguments.size(); ++i) + { + auto& arg = _arguments[i]; + // TODO optimize vector operations, check that it actually moves + auto internalPrefix = visitRecursively(arg); + if (!internalPrefix.empty()) + { + _moveToFront = true; + // We go through the arguments left to right, so we have to invert + // the prefixes. + prefix = std::move(internalPrefix) + std::move(prefix); + } + else if (_moveToFront) + { + auto location = locationOf(arg); + string var = newName(i < _nameHints.size() ? _nameHints[i] : ""); + prefix.emplace(prefix.begin(), VariableDeclaration{ + location, + {{TypedName{location, var, i < _types.size() ? _types[i] : ""}}}, + make_shared<Expression>(std::move(arg)) + }); + arg = Identifier{location, var}; + } + } + m_statementsToPrefix += std::move(prefix); +} + +vector<Statement> InlineModifier::visitRecursively(Expression& _expression) +{ + vector<Statement> saved; + saved.swap(m_statementsToPrefix); + visit(_expression); + saved.swap(m_statementsToPrefix); + return saved; +} + +string InlineModifier::newName(string const& _prefix) +{ + return m_nameDispenser.newName(_prefix); +} + +Expression InlineModifier::noop(SourceLocation const& _location) +{ + return FunctionalInstruction{_location, solidity::Instruction::POP, { + Literal{_location, assembly::LiteralKind::Number, "0", ""} + }}; +} + +Statement BodyCopier::operator()(VariableDeclaration const& _varDecl) +{ + for (auto const& var: _varDecl.variables) + m_variableReplacements[var.name] = m_nameDispenser.newName(m_varNamePrefix + var.name); + return ASTCopier::operator()(_varDecl); +} + +Statement BodyCopier::operator()(FunctionDefinition const& _funDef) +{ + solAssert(false, "Function hoisting has to be done before function inlining."); + return _funDef; +} + +string BodyCopier::translateIdentifier(string const& _name) +{ + if (m_variableReplacements.count(_name)) + return m_variableReplacements.at(_name); + else + return _name; +} diff --git a/libjulia/optimiser/FullInliner.h b/libjulia/optimiser/FullInliner.h new file mode 100644 index 00000000..d3628e1a --- /dev/null +++ b/libjulia/optimiser/FullInliner.h @@ -0,0 +1,178 @@ +/* + 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 performs function inlining for arbitrary functions. + */ +#pragma once + +#include <libjulia/ASTDataForward.h> + +#include <libjulia/optimiser/ASTCopier.h> +#include <libjulia/optimiser/ASTWalker.h> +#include <libjulia/optimiser/NameDispenser.h> + +#include <libsolidity/interface/Exceptions.h> + +#include <boost/variant.hpp> +#include <boost/optional.hpp> + +#include <set> + +namespace dev +{ +namespace julia +{ + +class NameCollector; + + +/** + * Optimiser component that modifies an AST in place, inlining arbitrary functions. + * + * Code of the form + * + * function f(a, b) -> c { ... } + * h(g(x(...), f(arg1(...), arg2(...)), y(...)), z(...)) + * + * is transformed into + * + * function f(a, b) -> c { ... } + * + * let z1 := z(...) let y1 := y(...) let a2 := arg2(...) let a1 := arg1(...) + * let c1 := 0 + * { code of f, with replacements: a -> a1, b -> a2, c -> c1, d -> d1 } + * h(g(x(...), c1, y1), z1) + * + * No temporary variable is created for expressions that are "movable" + * (i.e. they are "pure", have no side-effects and also do not depend on other code + * that might have side-effects). + * + * This component can only be used on sources with unique names and with hoisted functions, + * i.e. the root node has to be a block that itself contains a single block followed by all + * function definitions. + */ +class FullInliner: public ASTModifier +{ +public: + explicit FullInliner(Block& _ast); + + void run(); + + /// Perform inlining operations inside the given function. + void handleFunction(FunctionDefinition& _function); + + FunctionDefinition& function(std::string _name) { return *m_functions.at(_name); } + +private: + /// The AST to be modified. The root block itself will not be modified, because + /// we store pointers to functions. + Block& m_ast; + std::map<std::string, FunctionDefinition*> m_functions; + std::set<FunctionDefinition*> m_functionsToVisit; + NameDispenser m_nameDispenser; +}; + +/** + * Class that walks the AST of a block that does not contain function definitions and perform + * the actual code modifications. + */ +class InlineModifier: public ASTModifier +{ +public: + InlineModifier(FullInliner& _driver, NameDispenser& _nameDispenser, std::string _functionName): + m_currentFunction(std::move(_functionName)), + m_driver(_driver), + m_nameDispenser(_nameDispenser) + { } + ~InlineModifier() + { + solAssert(m_statementsToPrefix.empty(), ""); + } + + virtual void operator()(FunctionalInstruction&) override; + virtual void operator()(FunctionCall&) override; + virtual void operator()(ForLoop&) override; + virtual void operator()(Block& _block) override; + + using ASTModifier::visit; + virtual void visit(Expression& _expression) override; + virtual void visit(Statement& _st) override; + +private: + + /// Visits a list of expressions (usually an argument list to a function call) and tries + /// to inline them. If one of them is inlined, all right of it have to be moved to the front + /// (to keep the order of evaluation). If @a _moveToFront is true, all elements are moved + /// to the front. @a _nameHints and @_types are used for the newly created variables, but + /// both can be empty. + void visitArguments( + std::vector<Expression>& _arguments, + std::vector<std::string> const& _nameHints = {}, + std::vector<std::string> const& _types = {}, + bool _moveToFront = false + ); + + /// Visits an expression, but saves and restores the current statements to prefix and returns + /// the statements that should be prefixed for @a _expression. + std::vector<Statement> visitRecursively(Expression& _expression); + + std::string newName(std::string const& _prefix); + + /// @returns an expression returning nothing. + Expression noop(SourceLocation const& _location); + + /// List of statements that should go in front of the currently visited AST element, + /// at the statement level. + std::vector<Statement> m_statementsToPrefix; + std::string m_currentFunction; + FullInliner& m_driver; + NameDispenser& m_nameDispenser; +}; + +/** + * Creates a copy of a block that is supposed to be the body of a function. + * Applies replacements to referenced variables and creates new names for + * variable declarations. + */ +class BodyCopier: public ASTCopier +{ +public: + BodyCopier( + NameDispenser& _nameDispenser, + std::string const& _varNamePrefix, + std::map<std::string, std::string> const& _variableReplacements + ): + m_nameDispenser(_nameDispenser), + m_varNamePrefix(_varNamePrefix), + m_variableReplacements(_variableReplacements) + {} + + using ASTCopier::operator (); + + virtual Statement operator()(VariableDeclaration const& _varDecl) override; + virtual Statement operator()(FunctionDefinition const& _funDef) override; + + virtual std::string translateIdentifier(std::string const& _name) override; + + NameDispenser& m_nameDispenser; + std::string const& m_varNamePrefix; + std::map<std::string, std::string> m_variableReplacements; +}; + + +} +} diff --git a/libjulia/optimiser/NameCollector.cpp b/libjulia/optimiser/NameCollector.cpp index 510ee289..c0d0b707 100644 --- a/libjulia/optimiser/NameCollector.cpp +++ b/libjulia/optimiser/NameCollector.cpp @@ -35,7 +35,6 @@ void NameCollector::operator()(VariableDeclaration const& _varDecl) void NameCollector::operator ()(FunctionDefinition const& _funDef) { m_names.insert(_funDef.name); - m_functions[_funDef.name] = &_funDef; for (auto const arg: _funDef.parameters) m_names.insert(arg.name); for (auto const ret: _funDef.returnVariables) diff --git a/libjulia/optimiser/NameCollector.h b/libjulia/optimiser/NameCollector.h index 2d4a1d4b..29856172 100644 --- a/libjulia/optimiser/NameCollector.h +++ b/libjulia/optimiser/NameCollector.h @@ -37,15 +37,18 @@ namespace julia class NameCollector: public ASTWalker { public: + explicit NameCollector(Block const& _block) + { + (*this)(_block); + } + using ASTWalker::operator (); virtual void operator()(VariableDeclaration const& _varDecl) override; virtual void operator()(FunctionDefinition const& _funDef) override; - std::set<std::string> const& names() const { return m_names; } - std::map<std::string, FunctionDefinition const*> const& functions() const { return m_functions; } + std::set<std::string> names() const { return m_names; } private: std::set<std::string> m_names; - std::map<std::string, FunctionDefinition const*> m_functions; }; /** diff --git a/libjulia/optimiser/NameDispenser.cpp b/libjulia/optimiser/NameDispenser.cpp new file mode 100644 index 00000000..e4f0e4f6 --- /dev/null +++ b/libjulia/optimiser/NameDispenser.cpp @@ -0,0 +1,38 @@ +/* + 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 can create new unique names. + */ + +#include <libjulia/optimiser/NameDispenser.h> + +using namespace std; +using namespace dev; +using namespace dev::julia; + +string NameDispenser::newName(string const& _prefix) +{ + string name = _prefix; + size_t suffix = 0; + while (name.empty() || m_usedNames.count(name)) + { + suffix++; + name = _prefix + "_" + std::to_string(suffix); + } + m_usedNames.insert(name); + return name; +} diff --git a/libjulia/optimiser/NameDispenser.h b/libjulia/optimiser/NameDispenser.h new file mode 100644 index 00000000..91c43d54 --- /dev/null +++ b/libjulia/optimiser/NameDispenser.h @@ -0,0 +1,37 @@ +/* + 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 can create new unique names. + */ +#pragma once + +#include <set> +#include <string> + +namespace dev +{ +namespace julia +{ + +struct NameDispenser +{ + std::string newName(std::string const& _prefix); + std::set<std::string> m_usedNames; +}; + +} +} diff --git a/test/libjulia/Inliner.cpp b/test/libjulia/Inliner.cpp index 88b51f28..464dcd93 100644 --- a/test/libjulia/Inliner.cpp +++ b/test/libjulia/Inliner.cpp @@ -1,18 +1,18 @@ /* - This file is part of solidity. + 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 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. + 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/>. + You should have received a copy of the GNU General Public License + along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** * @date 2017 @@ -23,6 +23,9 @@ #include <libjulia/optimiser/ExpressionInliner.h> #include <libjulia/optimiser/InlinableExpressionFunctionFinder.h> +#include <libjulia/optimiser/FullInliner.h> +#include <libjulia/optimiser/FunctionHoister.h> +#include <libjulia/optimiser/FunctionGrouper.h> #include <libsolidity/inlineasm/AsmPrinter.h> @@ -58,8 +61,17 @@ string inlineFunctions(string const& _source, bool _julia = true) ExpressionInliner(ast).run(); return assembly::AsmPrinter(_julia)(ast); } +string fullInline(string const& _source, bool _julia = true) +{ + Block ast = disambiguate(_source, _julia); + (FunctionHoister{})(ast); + (FunctionGrouper{})(ast);\ + FullInliner(ast).run(); + return assembly::AsmPrinter(_julia)(ast); +} } + BOOST_AUTO_TEST_SUITE(IuliaInlinableFunctionFilter) BOOST_AUTO_TEST_CASE(smoke_test) @@ -197,3 +209,135 @@ BOOST_AUTO_TEST_CASE(double_recursive_calls) } BOOST_AUTO_TEST_SUITE_END() + +BOOST_AUTO_TEST_SUITE(IuliaFullInliner) + +BOOST_AUTO_TEST_CASE(simple) +{ + BOOST_CHECK_EQUAL( + fullInline("{" + "function f(a) -> x { let r := mul(a, a) x := add(r, r) }" + "let y := add(f(sload(mload(2))), mload(7))" + "}", false), + format("{" + "{" + "let _1 := mload(7)" + "let f_a := sload(mload(2))" + "let f_x" + "{" + "let f_r := mul(f_a, f_a)" + "f_x := add(f_r, f_r)" + "}" + "let y := add(f_x, _1)" + "}" + "function f(a) -> x" + "{" + "let r := mul(a, a)" + "x := add(r, r)" + "}" + "}", false) + ); +} + +BOOST_AUTO_TEST_CASE(multi_fun) +{ + BOOST_CHECK_EQUAL( + fullInline("{" + "function f(a) -> x { x := add(a, a) }" + "function g(b, c) -> y { y := mul(mload(c), f(b)) }" + "let y := g(f(3), 7)" + "}", false), + format("{" + "{" + "let g_c := 7 " + "let f_a_1 := 3 " + "let f_x_1 " + "{ f_x_1 := add(f_a_1, f_a_1) } " + "let g_y " + "{" + "let g_f_a := f_x_1 " + "let g_f_x " + "{" + "g_f_x := add(g_f_a, g_f_a)" + "}" + "g_y := mul(mload(g_c), g_f_x)" + "}" + "let y_1 := g_y" + "}" + "function f(a) -> x" + "{" + "x := add(a, a)" + "}" + "function g(b, c) -> y" + "{" + "let f_a := b " + "let f_x " + "{" + "f_x := add(f_a, f_a)" + "}" + "y := mul(mload(c), f_x)" + "}" + "}", false) + ); +} + +BOOST_AUTO_TEST_CASE(move_up_rightwards_arguments) +{ + BOOST_CHECK_EQUAL( + fullInline("{" + "function f(a, b, c) -> x { x := add(a, b) x := mul(x, c) }" + "let y := add(mload(1), add(f(mload(2), mload(3), mload(4)), mload(5)))" + "}", false), + format("{" + "{" + "let _1 := mload(5)" + "let f_c := mload(4)" + "let f_b := mload(3)" + "let f_a := mload(2)" + "let f_x" + "{" + "f_x := add(f_a, f_b)" + "f_x := mul(f_x, f_c)" + "}" + "let y := add(mload(1), add(f_x, _1))" + "}" + "function f(a, b, c) -> x" + "{" + "x := add(a, b)" + "x := mul(x, c)" + "}" + "}", false) + ); +} + +BOOST_AUTO_TEST_CASE(pop_result) +{ + // This tests that `pop(r)` is removed. + BOOST_CHECK_EQUAL( + fullInline("{" + "function f(a) -> x { let r := mul(a, a) x := add(r, r) }" + "pop(add(f(7), 2))" + "}", false), + format("{" + "{" + "let _1 := 2 " + "let f_a := 7 " + "let f_x " + "{" + "let f_r := mul(f_a, f_a) " + "f_x := add(f_r, f_r)" + "}" + "{" + "}" + "}" + "function f(a) -> x" + "{" + "let r := mul(a, a) " + "x := add(r, r)" + "}" + "}", false) + ); +} + + +BOOST_AUTO_TEST_SUITE_END() |