From 0a366fd4534cfdf5105ccc8f634a6deffa3e5f65 Mon Sep 17 00:00:00 2001 From: chriseth Date: Thu, 7 Dec 2017 15:43:23 +0100 Subject: Full inliner. --- libjulia/optimiser/FullInliner.cpp | 237 +++++++++++++++++++++++++++++++++++++ libjulia/optimiser/FullInliner.h | 180 ++++++++++++++++++++++++++++ 2 files changed, 417 insertions(+) create mode 100644 libjulia/optimiser/FullInliner.cpp create mode 100644 libjulia/optimiser/FullInliner.h (limited to 'libjulia') diff --git a/libjulia/optimiser/FullInliner.cpp b/libjulia/optimiser/FullInliner.cpp new file mode 100644 index 00000000..f5721617 --- /dev/null +++ b/libjulia/optimiser/FullInliner.cpp @@ -0,0 +1,237 @@ +/* + 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 for arbitrary functions. + */ + +#include + +#include +#include +#include + +#include + +#include + +#include + +#include + +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, ""); + m_nameDispenser.m_usedNames = NameCollector(m_ast).names(); + + for (size_t i = 1; i < m_ast.statements.size(); ++i) + { + FunctionDefinition& fun = boost::get(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) +{ + // TODO: optimize the number of moves here. + for (size_t i = 0; i < _block.statements.size(); ++i) + { + visit(_block.statements.at(i)); + if (size_t length = m_statementsToPrefix.size()) + { + _block.statements.insert( + _block.statements.begin() + i, + std::make_move_iterator(m_statementsToPrefix.begin()), + std::make_move_iterator(m_statementsToPrefix.end()) + ); + i += length; + m_statementsToPrefix.clear(); + } + } +} + +void InlineModifier::visit(Expression& _expression) +{ + if (_expression.type() != typeid(FunctionCall)) + return ASTModifier::visit(_expression); + + FunctionCall& funCall = boost::get(_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 argNames; + vector 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 variableReplacements; + string returnVariable = fun.returnVariables[0].name; + for (size_t i = 0; i < funCall.arguments.size(); ++i) + variableReplacements[fun.parameters[i].name] = boost::get(funCall.arguments[i]).name; + variableReplacements[returnVariable] = newName(fun.name + "_" + returnVariable); + + m_statementsToPrefix.emplace_back(VariableDeclaration{ + funCall.location, + {{funCall.location, variableReplacements[returnVariable], fun.returnVariables[0].type}}, + {} + }); + m_statementsToPrefix.emplace_back(BodyCopier(m_nameDispenser, fun.name + "_", variableReplacements)(fun.body)); + _expression = Identifier{funCall.location, variableReplacements[returnVariable]}; +} + +void InlineModifier::visitArguments( + vector& _arguments, + vector const& _nameHints, + vector 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 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(std::move(arg)) + }); + arg = Identifier{location, var}; + } + } + m_statementsToPrefix += std::move(prefix); +} + +vector InlineModifier::visitRecursively(Expression& _expression) +{ + vector saved; + saved.swap(m_statementsToPrefix); + visit(_expression); + saved.swap(m_statementsToPrefix); + return saved; +} + +string InlineModifier::newName(string const& _prefix) +{ + return m_nameDispenser.newName(_prefix); +} + +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; +} + +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/FullInliner.h b/libjulia/optimiser/FullInliner.h new file mode 100644 index 00000000..e9a7e4fc --- /dev/null +++ b/libjulia/optimiser/FullInliner.h @@ -0,0 +1,180 @@ +/* + 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 for arbitrary functions. + */ +#pragma once + +#include + +#include +#include + +#include + +#include +#include + +#include + +namespace dev +{ +namespace julia +{ + +class NameCollector; + +struct NameDispenser +{ + std::string newName(std::string const& _prefix); + std::set m_usedNames; +}; + + + +/** + * 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 m_functions; + std::set 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; + +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& _arguments, + std::vector const& _nameHints = {}, + std::vector 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 visitRecursively(Expression& _expression); + + std::string newName(std::string const& _prefix); + + /// List of statements that should go in front of the currently visited AST element, + /// at the statement level. + std::vector 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 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 m_variableReplacements; +}; + + +} +} -- cgit v1.2.3