diff options
Diffstat (limited to 'libjulia')
| -rw-r--r-- | libjulia/optimiser/Disambiguator.cpp | 12 | ||||
| -rw-r--r-- | libjulia/optimiser/Disambiguator.h | 3 | ||||
| -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 |
8 files changed, 524 insertions, 16 deletions
diff --git a/libjulia/optimiser/Disambiguator.cpp b/libjulia/optimiser/Disambiguator.cpp index df2984e5..b988dba7 100644 --- a/libjulia/optimiser/Disambiguator.cpp +++ b/libjulia/optimiser/Disambiguator.cpp @@ -38,17 +38,7 @@ string Disambiguator::translateIdentifier(string const& _originalName) Scope::Identifier const* id = m_scopes.back()->lookup(_originalName); solAssert(id, ""); if (!m_translations.count(id)) - { - string translated = _originalName; - size_t suffix = 0; - while (m_usedNames.count(translated)) - { - suffix++; - translated = _originalName + "_" + std::to_string(suffix); - } - m_usedNames.insert(translated); - m_translations[id] = translated; - } + m_translations[id] = m_nameDispenser.newName(_originalName); return m_translations.at(id); } diff --git a/libjulia/optimiser/Disambiguator.h b/libjulia/optimiser/Disambiguator.h index 18ffd157..6fc8a615 100644 --- a/libjulia/optimiser/Disambiguator.h +++ b/libjulia/optimiser/Disambiguator.h @@ -23,6 +23,7 @@ #include <libjulia/ASTDataForward.h> #include <libjulia/optimiser/ASTCopier.h> +#include <libjulia/optimiser/NameDispenser.h> #include <libsolidity/inlineasm/AsmAnalysisInfo.h> @@ -60,7 +61,7 @@ protected: std::vector<solidity::assembly::Scope*> m_scopes; std::map<void const*, std::string> m_translations; - std::set<std::string> m_usedNames; + NameDispenser m_nameDispenser; }; } 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; +}; + +} +} |