diff options
Diffstat (limited to 'libyul/optimiser')
61 files changed, 5478 insertions, 0 deletions
diff --git a/libyul/optimiser/ASTCopier.cpp b/libyul/optimiser/ASTCopier.cpp new file mode 100644 index 00000000..d0c8dd45 --- /dev/null +++ b/libyul/optimiser/ASTCopier.cpp @@ -0,0 +1,184 @@ +/* + 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/>. +*/ +/** + * Creates an independent copy of an AST, renaming identifiers to be unique. + */ + +#include <libyul/optimiser/ASTCopier.h> + +#include <libyul/Exceptions.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libdevcore/Common.h> + +using namespace std; +using namespace dev; +using namespace dev::yul; + +Statement ASTCopier::operator()(Instruction const&) +{ + assertThrow(false, OptimizerException, "Invalid operation."); + return {}; +} + +Statement ASTCopier::operator()(ExpressionStatement const& _statement) +{ + return ExpressionStatement{ _statement.location, translate(_statement.expression) }; +} + +Statement ASTCopier::operator()(VariableDeclaration const& _varDecl) +{ + return VariableDeclaration{ + _varDecl.location, + translateVector(_varDecl.variables), + translate(_varDecl.value) + }; +} + +Statement ASTCopier::operator()(Assignment const& _assignment) +{ + return Assignment{ + _assignment.location, + translateVector(_assignment.variableNames), + translate(_assignment.value) + }; +} + +Statement ASTCopier::operator()(StackAssignment const&) +{ + assertThrow(false, OptimizerException, "Invalid operation."); + return {}; +} + +Statement ASTCopier::operator()(Label const&) +{ + assertThrow(false, OptimizerException, "Invalid operation."); + return {}; +} + +Expression ASTCopier::operator()(FunctionCall const& _call) +{ + return FunctionCall{ + _call.location, + translate(_call.functionName), + translateVector(_call.arguments) + }; +} + +Expression ASTCopier::operator()(FunctionalInstruction const& _instruction) +{ + return FunctionalInstruction{ + _instruction.location, + _instruction.instruction, + translateVector(_instruction.arguments) + }; +} + +Expression ASTCopier::operator()(Identifier const& _identifier) +{ + return Identifier{_identifier.location, translateIdentifier(_identifier.name)}; +} + +Expression ASTCopier::operator()(Literal const& _literal) +{ + return translate(_literal); +} + +Statement ASTCopier::operator()(If const& _if) +{ + return If{_if.location, translate(_if.condition), translate(_if.body)}; +} + +Statement ASTCopier::operator()(Switch const& _switch) +{ + return Switch{_switch.location, translate(_switch.expression), translateVector(_switch.cases)}; +} + +Statement ASTCopier::operator()(FunctionDefinition const& _function) +{ + YulString translatedName = translateIdentifier(_function.name); + + enterFunction(_function); + ScopeGuard g([&]() { this->leaveFunction(_function); }); + + return FunctionDefinition{ + _function.location, + translatedName, + translateVector(_function.parameters), + translateVector(_function.returnVariables), + translate(_function.body) + }; +} + +Statement ASTCopier::operator()(ForLoop const& _forLoop) +{ + enterScope(_forLoop.pre); + ScopeGuard g([&]() { this->leaveScope(_forLoop.pre); }); + + return ForLoop{ + _forLoop.location, + translate(_forLoop.pre), + translate(_forLoop.condition), + translate(_forLoop.post), + translate(_forLoop.body) + }; +} + +Statement ASTCopier::operator ()(Block const& _block) +{ + return translate(_block); +} + +Expression ASTCopier::translate(Expression const& _expression) +{ + return _expression.apply_visitor(static_cast<ExpressionCopier&>(*this)); +} + +Statement ASTCopier::translate(Statement const& _statement) +{ + return _statement.apply_visitor(static_cast<StatementCopier&>(*this)); +} + +Block ASTCopier::translate(Block const& _block) +{ + enterScope(_block); + ScopeGuard g([&]() { this->leaveScope(_block); }); + + return Block{_block.location, translateVector(_block.statements)}; +} + +Case ASTCopier::translate(Case const& _case) +{ + return Case{_case.location, translate(_case.value), translate(_case.body)}; +} + +Identifier ASTCopier::translate(Identifier const& _identifier) +{ + return Identifier{_identifier.location, translateIdentifier(_identifier.name)}; +} + +Literal ASTCopier::translate(Literal const& _literal) +{ + return _literal; +} + +TypedName ASTCopier::translate(TypedName const& _typedName) +{ + return TypedName{_typedName.location, translateIdentifier(_typedName.name), _typedName.type}; +} + diff --git a/libyul/optimiser/ASTCopier.h b/libyul/optimiser/ASTCopier.h new file mode 100644 index 00000000..b6aceee3 --- /dev/null +++ b/libyul/optimiser/ASTCopier.h @@ -0,0 +1,126 @@ +/* + 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/>. +*/ +/** + * Creates an independent copy of an AST, renaming identifiers to be unique. + */ + +#pragma once + +#include <libyul/ASTDataForward.h> + +#include <libyul/YulString.h> + +#include <boost/variant.hpp> +#include <boost/optional.hpp> + +#include <vector> +#include <set> +#include <memory> + +namespace dev +{ +namespace yul +{ + +class ExpressionCopier: public boost::static_visitor<Expression> +{ +public: + virtual ~ExpressionCopier() = default; + virtual Expression operator()(Literal const& _literal) = 0; + virtual Expression operator()(Identifier const& _identifier) = 0; + virtual Expression operator()(FunctionalInstruction const& _instr) = 0; + virtual Expression operator()(FunctionCall const&) = 0; +}; + +class StatementCopier: public boost::static_visitor<Statement> +{ +public: + virtual ~StatementCopier() = default; + virtual Statement operator()(ExpressionStatement const& _statement) = 0; + virtual Statement operator()(Instruction const& _instruction) = 0; + virtual Statement operator()(Label const& _label) = 0; + virtual Statement operator()(StackAssignment const& _assignment) = 0; + virtual Statement operator()(Assignment const& _assignment) = 0; + virtual Statement operator()(VariableDeclaration const& _varDecl) = 0; + virtual Statement operator()(If const& _if) = 0; + virtual Statement operator()(Switch const& _switch) = 0; + virtual Statement operator()(FunctionDefinition const&) = 0; + virtual Statement operator()(ForLoop const&) = 0; + virtual Statement operator()(Block const& _block) = 0; +}; + +/** + * Creates a copy of a Yul AST potentially replacing identifier names. + * Base class to be extended. + */ +class ASTCopier: public ExpressionCopier, public StatementCopier +{ +public: + virtual ~ASTCopier() = default; + virtual Expression operator()(Literal const& _literal) override; + virtual Statement operator()(Instruction const& _instruction) override; + virtual Expression operator()(Identifier const& _identifier) override; + virtual Expression operator()(FunctionalInstruction const& _instr) override; + virtual Expression operator()(FunctionCall const&) override; + virtual Statement operator()(ExpressionStatement const& _statement) override; + virtual Statement operator()(Label const& _label) override; + virtual Statement operator()(StackAssignment const& _assignment) override; + virtual Statement operator()(Assignment const& _assignment) override; + virtual Statement operator()(VariableDeclaration const& _varDecl) override; + virtual Statement operator()(If const& _if) override; + virtual Statement operator()(Switch const& _switch) override; + virtual Statement operator()(FunctionDefinition const&) override; + virtual Statement operator()(ForLoop const&) override; + virtual Statement operator()(Block const& _block) override; + + virtual Expression translate(Expression const& _expression); + virtual Statement translate(Statement const& _statement); + +protected: + template <typename T> + std::vector<T> translateVector(std::vector<T> const& _values); + + template <typename T> + std::shared_ptr<T> translate(std::shared_ptr<T> const& _v) + { + return _v ? std::make_shared<T>(translate(*_v)) : nullptr; + } + Block translate(Block const& _block); + Case translate(Case const& _case); + Identifier translate(Identifier const& _identifier); + Literal translate(Literal const& _literal); + TypedName translate(TypedName const& _typedName); + + virtual void enterScope(Block const&) { } + virtual void leaveScope(Block const&) { } + virtual void enterFunction(FunctionDefinition const&) { } + virtual void leaveFunction(FunctionDefinition const&) { } + virtual YulString translateIdentifier(YulString _name) { return _name; } +}; + +template <typename T> +std::vector<T> ASTCopier::translateVector(std::vector<T> const& _values) +{ + std::vector<T> translated; + for (auto const& v: _values) + translated.emplace_back(translate(v)); + return translated; +} + + +} +} diff --git a/libyul/optimiser/ASTWalker.cpp b/libyul/optimiser/ASTWalker.cpp new file mode 100644 index 00000000..e29dda6b --- /dev/null +++ b/libyul/optimiser/ASTWalker.cpp @@ -0,0 +1,157 @@ +/* + 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/>. +*/ +/** + * Generic AST walker. + */ + +#include <libyul/optimiser/ASTWalker.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <boost/range/adaptor/reversed.hpp> + +using namespace std; +using namespace dev; +using namespace dev::yul; +using namespace dev::solidity; + + +void ASTWalker::operator()(FunctionalInstruction const& _instr) +{ + walkVector(_instr.arguments | boost::adaptors::reversed); +} + +void ASTWalker::operator()(FunctionCall const& _funCall) +{ + walkVector(_funCall.arguments | boost::adaptors::reversed); +} + +void ASTWalker::operator()(ExpressionStatement const& _statement) +{ + visit(_statement.expression); +} + +void ASTWalker::operator()(Assignment const& _assignment) +{ + for (auto const& name: _assignment.variableNames) + (*this)(name); + visit(*_assignment.value); +} + +void ASTWalker::operator()(VariableDeclaration const& _varDecl) +{ + if (_varDecl.value) + visit(*_varDecl.value); +} + +void ASTWalker::operator()(If const& _if) +{ + visit(*_if.condition); + (*this)(_if.body); +} + +void ASTWalker::operator()(Switch const& _switch) +{ + visit(*_switch.expression); + for (auto const& _case: _switch.cases) + { + if (_case.value) + (*this)(*_case.value); + (*this)(_case.body); + } +} + +void ASTWalker::operator()(FunctionDefinition const& _fun) +{ + (*this)(_fun.body); +} + +void ASTWalker::operator()(ForLoop const& _for) +{ + (*this)(_for.pre); + visit(*_for.condition); + (*this)(_for.body); + (*this)(_for.post); +} + +void ASTWalker::operator()(Block const& _block) +{ + walkVector(_block.statements); +} + +void ASTModifier::operator()(FunctionalInstruction& _instr) +{ + walkVector(_instr.arguments | boost::adaptors::reversed); +} + +void ASTModifier::operator()(FunctionCall& _funCall) +{ + walkVector(_funCall.arguments | boost::adaptors::reversed); +} + +void ASTModifier::operator()(ExpressionStatement& _statement) +{ + visit(_statement.expression); +} + +void ASTModifier::operator()(Assignment& _assignment) +{ + for (auto& name: _assignment.variableNames) + (*this)(name); + visit(*_assignment.value); +} + +void ASTModifier::operator()(VariableDeclaration& _varDecl) +{ + if (_varDecl.value) + visit(*_varDecl.value); +} + +void ASTModifier::operator()(If& _if) +{ + visit(*_if.condition); + (*this)(_if.body); +} + +void ASTModifier::operator()(Switch& _switch) +{ + visit(*_switch.expression); + for (auto& _case: _switch.cases) + { + if (_case.value) + (*this)(*_case.value); + (*this)(_case.body); + } +} + +void ASTModifier::operator()(FunctionDefinition& _fun) +{ + (*this)(_fun.body); +} + +void ASTModifier::operator()(ForLoop& _for) +{ + (*this)(_for.pre); + visit(*_for.condition); + (*this)(_for.post); + (*this)(_for.body); +} + +void ASTModifier::operator()(Block& _block) +{ + walkVector(_block.statements); +} diff --git a/libyul/optimiser/ASTWalker.h b/libyul/optimiser/ASTWalker.h new file mode 100644 index 00000000..38cb85ea --- /dev/null +++ b/libyul/optimiser/ASTWalker.h @@ -0,0 +1,123 @@ +/* + 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/>. +*/ +/** + * Generic AST walker. + */ + +#pragma once + +#include <libyul/ASTDataForward.h> + +#include <libyul/Exceptions.h> +#include <libyul/YulString.h> + +#include <boost/variant.hpp> +#include <boost/optional.hpp> + +#include <vector> +#include <set> +#include <map> + +namespace dev +{ +namespace yul +{ + +/** + * Generic AST walker. + */ +class ASTWalker: public boost::static_visitor<> +{ +public: + virtual ~ASTWalker() = default; + virtual void operator()(Literal const&) {} + virtual void operator()(Instruction const&) { assertThrow(false, OptimizerException, ""); } + virtual void operator()(Identifier const&) {} + virtual void operator()(FunctionalInstruction const& _instr); + virtual void operator()(FunctionCall const& _funCall); + virtual void operator()(ExpressionStatement const& _statement); + virtual void operator()(Label const&) { assertThrow(false, OptimizerException, ""); } + virtual void operator()(StackAssignment const&) { assertThrow(false, OptimizerException, ""); } + virtual void operator()(Assignment const& _assignment); + virtual void operator()(VariableDeclaration const& _varDecl); + virtual void operator()(If const& _if); + virtual void operator()(Switch const& _switch); + virtual void operator()(FunctionDefinition const&); + virtual void operator()(ForLoop const&); + virtual void operator()(Block const& _block); + + virtual void visit(Statement const& _st) + { + boost::apply_visitor(*this, _st); + } + virtual void visit(Expression const& _e) + { + boost::apply_visitor(*this, _e); + } + +protected: + template <class T> + void walkVector(T const& _statements) + { + for (auto const& statement: _statements) + visit(statement); + } +}; + +/** + * Generic AST modifier (i.e. non-const version of ASTWalker). + */ +class ASTModifier: public boost::static_visitor<> +{ +public: + virtual ~ASTModifier() = default; + virtual void operator()(Literal&) {} + virtual void operator()(Instruction&) { assertThrow(false, OptimizerException, ""); } + virtual void operator()(Identifier&) {} + virtual void operator()(FunctionalInstruction& _instr); + virtual void operator()(FunctionCall& _funCall); + virtual void operator()(ExpressionStatement& _statement); + virtual void operator()(Label&) { assertThrow(false, OptimizerException, ""); } + virtual void operator()(StackAssignment&) { assertThrow(false, OptimizerException, ""); } + virtual void operator()(Assignment& _assignment); + virtual void operator()(VariableDeclaration& _varDecl); + virtual void operator()(If& _if); + virtual void operator()(Switch& _switch); + virtual void operator()(FunctionDefinition&); + virtual void operator()(ForLoop&); + virtual void operator()(Block& _block); + + virtual void visit(Statement& _st) + { + boost::apply_visitor(*this, _st); + } + virtual void visit(Expression& _e) + { + boost::apply_visitor(*this, _e); + } + +protected: + template <class T> + void walkVector(T&& _statements) + { + for (auto& st: _statements) + visit(st); + } +}; + +} +} diff --git a/libyul/optimiser/BlockFlattener.cpp b/libyul/optimiser/BlockFlattener.cpp new file mode 100644 index 00000000..04f3ad7f --- /dev/null +++ b/libyul/optimiser/BlockFlattener.cpp @@ -0,0 +1,41 @@ +/* + 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/>. +*/ +#include <libyul/optimiser/BlockFlattener.h> +#include <libsolidity/inlineasm/AsmData.h> +#include <libdevcore/Visitor.h> +#include <libdevcore/CommonData.h> +#include <functional> + +using namespace std; +using namespace dev; +using namespace dev::yul; + +void BlockFlattener::operator()(Block& _block) +{ + ASTModifier::operator()(_block); + + iterateReplacing( + _block.statements, + [](Statement& _s) -> boost::optional<vector<Statement>> + { + if (_s.type() == typeid(Block)) + return std::move(boost::get<Block>(_s).statements); + else + return {}; + } + ); +} diff --git a/libyul/optimiser/BlockFlattener.h b/libyul/optimiser/BlockFlattener.h new file mode 100644 index 00000000..88c49dda --- /dev/null +++ b/libyul/optimiser/BlockFlattener.h @@ -0,0 +1,34 @@ +/* + 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/>. +*/ +#pragma once + +#include <libyul/optimiser/ASTWalker.h> + +namespace dev +{ +namespace yul +{ + +class BlockFlattener: public ASTModifier +{ +public: + using ASTModifier::operator(); + void operator()(Block& _block) override; +}; + +} +} diff --git a/libyul/optimiser/CommonSubexpressionEliminator.cpp b/libyul/optimiser/CommonSubexpressionEliminator.cpp new file mode 100644 index 00000000..64605362 --- /dev/null +++ b/libyul/optimiser/CommonSubexpressionEliminator.cpp @@ -0,0 +1,72 @@ +/*( + 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/>. +*/ +/** + * Optimisation stage that replaces expressions known to be the current value of a variable + * in scope by a reference to that variable. + */ + +#include <libyul/optimiser/CommonSubexpressionEliminator.h> + +#include <libyul/optimiser/Metrics.h> +#include <libyul/optimiser/SyntacticalEquality.h> +#include <libyul/Exceptions.h> + +#include <libsolidity/inlineasm/AsmData.h> + +using namespace std; +using namespace dev; +using namespace dev::yul; + +void CommonSubexpressionEliminator::visit(Expression& _e) +{ + // We visit the inner expression first to first simplify inner expressions, + // which hopefully allows more matches. + // Note that the DataFlowAnalyzer itself only has code for visiting Statements, + // so this basically invokes the AST walker directly and thus post-visiting + // is also fine with regards to data flow analysis. + DataFlowAnalyzer::visit(_e); + + if (_e.type() == typeid(Identifier)) + { + Identifier& identifier = boost::get<Identifier>(_e); + YulString name = identifier.name; + if (m_value.count(name)) + { + assertThrow(m_value.at(name), OptimizerException, ""); + if (m_value.at(name)->type() == typeid(Identifier)) + { + YulString value = boost::get<Identifier>(*m_value.at(name)).name; + assertThrow(inScope(value), OptimizerException, ""); + _e = Identifier{locationOf(_e), value}; + } + } + } + else + { + // TODO this search is rather inefficient. + for (auto const& var: m_value) + { + assertThrow(var.second, OptimizerException, ""); + assertThrow(inScope(var.first), OptimizerException, ""); + if (SyntacticalEqualityChecker::equal(_e, *var.second)) + { + _e = Identifier{locationOf(_e), var.first}; + break; + } + } + } +} diff --git a/libyul/optimiser/CommonSubexpressionEliminator.h b/libyul/optimiser/CommonSubexpressionEliminator.h new file mode 100644 index 00000000..f8aa0ee1 --- /dev/null +++ b/libyul/optimiser/CommonSubexpressionEliminator.h @@ -0,0 +1,45 @@ +/* + 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/>. +*/ +/** + * Optimisation stage that replaces expressions known to be the current value of a variable + * in scope by a reference to that variable. + */ + +#pragma once + +#include <libyul/optimiser/DataFlowAnalyzer.h> + +namespace dev +{ +namespace yul +{ + +/** + * Optimisation stage that replaces expressions known to be the current value of a variable + * in scope by a reference to that variable. + * + * Prerequisite: Disambiguator + */ +class CommonSubexpressionEliminator: public DataFlowAnalyzer +{ +protected: + using ASTModifier::visit; + virtual void visit(Expression& _e) override; +}; + +} +} diff --git a/libyul/optimiser/DataFlowAnalyzer.cpp b/libyul/optimiser/DataFlowAnalyzer.cpp new file mode 100644 index 00000000..134777d0 --- /dev/null +++ b/libyul/optimiser/DataFlowAnalyzer.cpp @@ -0,0 +1,215 @@ +/*( + 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/>. +*/ +/** + * Base class to perform data flow analysis during AST walks. + * Tracks assignments and is used as base class for both Rematerialiser and + * Common Subexpression Eliminator. + */ + +#include <libyul/optimiser/DataFlowAnalyzer.h> + +#include <libyul/optimiser/NameCollector.h> +#include <libyul/optimiser/Semantics.h> +#include <libyul/Exceptions.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libdevcore/CommonData.h> + +#include <boost/range/adaptor/reversed.hpp> + +using namespace std; +using namespace dev; +using namespace dev::yul; + +void DataFlowAnalyzer::operator()(Assignment& _assignment) +{ + set<YulString> names; + for (auto const& var: _assignment.variableNames) + names.emplace(var.name); + assertThrow(_assignment.value, OptimizerException, ""); + visit(*_assignment.value); + handleAssignment(names, _assignment.value.get()); +} + +void DataFlowAnalyzer::operator()(VariableDeclaration& _varDecl) +{ + set<YulString> names; + for (auto const& var: _varDecl.variables) + names.emplace(var.name); + m_variableScopes.back().variables += names; + if (_varDecl.value) + visit(*_varDecl.value); + handleAssignment(names, _varDecl.value.get()); +} + +void DataFlowAnalyzer::operator()(If& _if) +{ + ASTModifier::operator()(_if); + + Assignments assignments; + assignments(_if.body); + clearValues(assignments.names()); +} + +void DataFlowAnalyzer::operator()(Switch& _switch) +{ + visit(*_switch.expression); + set<YulString> assignedVariables; + for (auto& _case: _switch.cases) + { + (*this)(_case.body); + Assignments assignments; + assignments(_case.body); + assignedVariables += assignments.names(); + // This is a little too destructive, we could retain the old values. + clearValues(assignments.names()); + } + clearValues(assignedVariables); +} + +void DataFlowAnalyzer::operator()(FunctionDefinition& _fun) +{ + // Save all information. We might rather reinstantiate this class, + // but this could be difficult if it is subclassed. + map<YulString, Expression const*> value; + map<YulString, set<YulString>> references; + map<YulString, set<YulString>> referencedBy; + m_value.swap(value); + m_references.swap(references); + m_referencedBy.swap(referencedBy); + pushScope(true); + + for (auto const& parameter: _fun.parameters) + m_variableScopes.back().variables.emplace(parameter.name); + for (auto const& var: _fun.returnVariables) + m_variableScopes.back().variables.emplace(var.name); + ASTModifier::operator()(_fun); + + popScope(); + m_value.swap(value); + m_references.swap(references); + m_referencedBy.swap(referencedBy); +} + +void DataFlowAnalyzer::operator()(ForLoop& _for) +{ + // Special scope handling of the pre block. + pushScope(false); + for (auto& statement: _for.pre.statements) + visit(statement); + + Assignments assignments; + assignments(_for.body); + assignments(_for.post); + clearValues(assignments.names()); + + visit(*_for.condition); + (*this)(_for.body); + (*this)(_for.post); + + clearValues(assignments.names()); + popScope(); +} + +void DataFlowAnalyzer::operator()(Block& _block) +{ + size_t numScopes = m_variableScopes.size(); + pushScope(false); + ASTModifier::operator()(_block); + popScope(); + assertThrow(numScopes == m_variableScopes.size(), OptimizerException, ""); +} + +void DataFlowAnalyzer::handleAssignment(set<YulString> const& _variables, Expression* _value) +{ + clearValues(_variables); + + MovableChecker movableChecker; + if (_value) + movableChecker.visit(*_value); + if (_variables.size() == 1) + { + YulString name = *_variables.begin(); + // Expression has to be movable and cannot contain a reference + // to the variable that will be assigned to. + if (_value && movableChecker.movable() && !movableChecker.referencedVariables().count(name)) + m_value[name] = _value; + } + + auto const& referencedVariables = movableChecker.referencedVariables(); + for (auto const& name: _variables) + { + m_references[name] = referencedVariables; + for (auto const& ref: referencedVariables) + m_referencedBy[ref].emplace(name); + } +} + +void DataFlowAnalyzer::pushScope(bool _functionScope) +{ + m_variableScopes.emplace_back(_functionScope); +} + +void DataFlowAnalyzer::popScope() +{ + clearValues(std::move(m_variableScopes.back().variables)); + m_variableScopes.pop_back(); +} + +void DataFlowAnalyzer::clearValues(set<YulString> _variables) +{ + // All variables that reference variables to be cleared also have to be + // cleared, but not recursively, since only the value of the original + // variables changes. Example: + // let a := 1 + // let b := a + // let c := b + // let a := 2 + // add(b, c) + // In the last line, we can replace c by b, but not b by a. + // + // This cannot be easily tested since the substitutions will be done + // one by one on the fly, and the last line will just be add(1, 1) + + // Clear variables that reference variables to be cleared. + for (auto const& name: _variables) + for (auto const& ref: m_referencedBy[name]) + _variables.emplace(ref); + + // Clear the value and update the reference relation. + for (auto const& name: _variables) + m_value.erase(name); + for (auto const& name: _variables) + { + for (auto const& ref: m_references[name]) + m_referencedBy[ref].erase(name); + m_references[name].clear(); + } +} + +bool DataFlowAnalyzer::inScope(YulString _variableName) const +{ + for (auto const& scope: m_variableScopes | boost::adaptors::reversed) + { + if (scope.variables.count(_variableName)) + return true; + if (scope.isFunction) + return false; + } + return false; +} diff --git a/libyul/optimiser/DataFlowAnalyzer.h b/libyul/optimiser/DataFlowAnalyzer.h new file mode 100644 index 00000000..a0c21eee --- /dev/null +++ b/libyul/optimiser/DataFlowAnalyzer.h @@ -0,0 +1,91 @@ +/* + 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/>. +*/ +/** + * Base class to perform data flow analysis during AST walks. + * Tracks assignments and is used as base class for both Rematerialiser and + * Common Subexpression Eliminator. + */ + +#pragma once + +#include <libyul/optimiser/ASTWalker.h> + +#include <libyul/YulString.h> + +#include <map> +#include <set> + +namespace dev +{ +namespace yul +{ + +/** + * Base class to perform data flow analysis during AST walks. + * Tracks assignments and is used as base class for both Rematerialiser and + * Common Subexpression Eliminator. + * + * Prerequisite: Disambiguator + */ +class DataFlowAnalyzer: public ASTModifier +{ +public: + using ASTModifier::operator(); + virtual void operator()(Assignment& _assignment) override; + virtual void operator()(VariableDeclaration& _varDecl) override; + virtual void operator()(If& _if) override; + virtual void operator()(Switch& _switch) override; + virtual void operator()(FunctionDefinition&) override; + virtual void operator()(ForLoop&) override; + virtual void operator()(Block& _block) override; + +protected: + /// Registers the assignment. + void handleAssignment(std::set<YulString> const& _names, Expression* _value); + + /// Creates a new inner scope. + void pushScope(bool _functionScope); + + /// Removes the innermost scope and clears all variables in it. + void popScope(); + + /// Clears information about the values assigned to the given variables, + /// for example at points where control flow is merged. + void clearValues(std::set<YulString> _names); + + /// Returns true iff the variable is in scope. + bool inScope(YulString _variableName) const; + + /// Current values of variables, always movable. + std::map<YulString, Expression const*> m_value; + /// m_references[a].contains(b) <=> the current expression assigned to a references b + std::map<YulString, std::set<YulString>> m_references; + /// m_referencedBy[b].contains(a) <=> the current expression assigned to a references b + std::map<YulString, std::set<YulString>> m_referencedBy; + + struct Scope + { + explicit Scope(bool _isFunction): isFunction(_isFunction) {} + std::set<YulString> variables; + bool isFunction; + }; + /// List of scopes. + std::vector<Scope> m_variableScopes; +}; + +} +} diff --git a/libyul/optimiser/Disambiguator.cpp b/libyul/optimiser/Disambiguator.cpp new file mode 100644 index 00000000..4303f412 --- /dev/null +++ b/libyul/optimiser/Disambiguator.cpp @@ -0,0 +1,78 @@ +/* + 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 makes all identifiers unique. + */ + +#include <libyul/optimiser/Disambiguator.h> + +#include <libyul/Exceptions.h> + +#include <libsolidity/inlineasm/AsmData.h> +#include <libsolidity/inlineasm/AsmScope.h> + +using namespace std; +using namespace dev; +using namespace dev::yul; +using namespace dev::solidity; + +using Scope = dev::solidity::assembly::Scope; + +YulString Disambiguator::translateIdentifier(YulString _originalName) +{ + if ((m_externallyUsedIdentifiers.count(_originalName))) + return _originalName; + + assertThrow(!m_scopes.empty() && m_scopes.back(), OptimizerException, ""); + Scope::Identifier const* id = m_scopes.back()->lookup(_originalName); + assertThrow(id, OptimizerException, ""); + if (!m_translations.count(id)) + m_translations[id] = m_nameDispenser.newName(_originalName); + return m_translations.at(id); +} + +void Disambiguator::enterScope(Block const& _block) +{ + enterScopeInternal(*m_info.scopes.at(&_block)); +} + +void Disambiguator::leaveScope(Block const& _block) +{ + leaveScopeInternal(*m_info.scopes.at(&_block)); +} + +void Disambiguator::enterFunction(FunctionDefinition const& _function) +{ + enterScopeInternal(*m_info.scopes.at(m_info.virtualBlocks.at(&_function).get())); +} + +void Disambiguator::leaveFunction(FunctionDefinition const& _function) +{ + leaveScopeInternal(*m_info.scopes.at(m_info.virtualBlocks.at(&_function).get())); +} + +void Disambiguator::enterScopeInternal(Scope& _scope) +{ + m_scopes.push_back(&_scope); +} + +void Disambiguator::leaveScopeInternal(Scope& _scope) +{ + assertThrow(!m_scopes.empty(), OptimizerException, ""); + assertThrow(m_scopes.back() == &_scope, OptimizerException, ""); + m_scopes.pop_back(); +} diff --git a/libyul/optimiser/Disambiguator.h b/libyul/optimiser/Disambiguator.h new file mode 100644 index 00000000..bfb65682 --- /dev/null +++ b/libyul/optimiser/Disambiguator.h @@ -0,0 +1,73 @@ +/* + 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 makes all identifiers unique. + */ + +#pragma once + +#include <libyul/ASTDataForward.h> + +#include <libyul/optimiser/ASTCopier.h> +#include <libyul/optimiser/NameDispenser.h> + +#include <libsolidity/inlineasm/AsmAnalysisInfo.h> + +#include <boost/variant.hpp> +#include <boost/optional.hpp> + +#include <set> + +namespace dev +{ +namespace yul +{ + +/** + * Creates a copy of a Yul AST replacing all identifiers by unique names. + */ +class Disambiguator: public ASTCopier +{ +public: + explicit Disambiguator( + solidity::assembly::AsmAnalysisInfo const& _analysisInfo, + std::set<YulString> const& _externallyUsedIdentifiers = {} + ): + m_info(_analysisInfo), m_externallyUsedIdentifiers(_externallyUsedIdentifiers), m_nameDispenser(m_externallyUsedIdentifiers) + { + } + +protected: + virtual void enterScope(Block const& _block) override; + virtual void leaveScope(Block const& _block) override; + virtual void enterFunction(FunctionDefinition const& _function) override; + virtual void leaveFunction(FunctionDefinition const& _function) override; + virtual YulString translateIdentifier(YulString _name) override; + + void enterScopeInternal(solidity::assembly::Scope& _scope); + void leaveScopeInternal(solidity::assembly::Scope& _scope); + + solidity::assembly::AsmAnalysisInfo const& m_info; + std::set<YulString> const& m_externallyUsedIdentifiers; + + std::vector<solidity::assembly::Scope*> m_scopes; + std::map<void const*, YulString> m_translations; + NameDispenser m_nameDispenser; +}; + +} +} diff --git a/libyul/optimiser/ExpressionInliner.cpp b/libyul/optimiser/ExpressionInliner.cpp new file mode 100644 index 00000000..07e88191 --- /dev/null +++ b/libyul/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 <http://www.gnu.org/licenses/>. +*/ +/** + * Optimiser component that performs function inlining inside expressions. + */ + +#include <libyul/optimiser/ExpressionInliner.h> + +#include <libyul/optimiser/InlinableExpressionFunctionFinder.h> +#include <libyul/optimiser/Substitution.h> +#include <libyul/optimiser/Semantics.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <boost/algorithm/cxx11/all_of.hpp> + +using namespace std; +using namespace dev; +using namespace dev::yul; +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<FunctionCall>(_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<YulString, Expression const*> 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<Assignment>(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/libyul/optimiser/ExpressionInliner.h b/libyul/optimiser/ExpressionInliner.h new file mode 100644 index 00000000..d903664f --- /dev/null +++ b/libyul/optimiser/ExpressionInliner.h @@ -0,0 +1,72 @@ +/* + 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. + */ +#pragma once + +#include <libyul/optimiser/ASTWalker.h> + +#include <libyul/ASTDataForward.h> + +#include <boost/variant.hpp> +#include <boost/optional.hpp> + +#include <set> + +namespace dev +{ +namespace yul +{ + +/** + * 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 := <functional expression> + * - 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<YulString, FunctionDefinition const*> m_inlinableFunctions; + std::map<YulString, YulString> m_varReplacements; + /// Set of functions we are currently visiting inside. + std::set<YulString> m_currentFunctions; + + Block& m_block; +}; + + +} +} diff --git a/libyul/optimiser/ExpressionJoiner.cpp b/libyul/optimiser/ExpressionJoiner.cpp new file mode 100644 index 00000000..7e57a629 --- /dev/null +++ b/libyul/optimiser/ExpressionJoiner.cpp @@ -0,0 +1,150 @@ +/* + 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 undoes what the ExpressionSplitter did, i.e. + * it more or less inlines variable declarations. + */ + +#include <libyul/optimiser/ExpressionJoiner.h> + +#include <libyul/optimiser/NameCollector.h> +#include <libyul/optimiser/Utilities.h> +#include <libyul/Exceptions.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libdevcore/CommonData.h> + +#include <boost/range/adaptor/reversed.hpp> + +using namespace std; +using namespace dev; +using namespace dev::yul; +using namespace dev::solidity; + +void ExpressionJoiner::operator()(FunctionalInstruction& _instruction) +{ + handleArguments(_instruction.arguments); +} + +void ExpressionJoiner::operator()(FunctionCall& _funCall) +{ + handleArguments(_funCall.arguments); +} + +void ExpressionJoiner::operator()(Block& _block) +{ + resetLatestStatementPointer(); + for (size_t i = 0; i < _block.statements.size(); ++i) + { + visit(_block.statements[i]); + m_currentBlock = &_block; + m_latestStatementInBlock = i; + } + + removeEmptyBlocks(_block); + resetLatestStatementPointer(); +} + +void ExpressionJoiner::visit(Expression& _e) +{ + if (_e.type() == typeid(Identifier)) + { + Identifier const& identifier = boost::get<Identifier>(_e); + if (isLatestStatementVarDeclJoinable(identifier)) + { + VariableDeclaration& varDecl = boost::get<VariableDeclaration>(*latestStatement()); + _e = std::move(*varDecl.value); + + // Delete the variable declaration (also get the moved-from structure back into a sane state) + *latestStatement() = Block(); + + decrementLatestStatementPointer(); + } + } + else + ASTModifier::visit(_e); +} + +void ExpressionJoiner::run(Block& _ast) +{ + ExpressionJoiner{_ast}(_ast); +} + +ExpressionJoiner::ExpressionJoiner(Block& _ast) +{ + m_references = ReferencesCounter::countReferences(_ast); +} + +void ExpressionJoiner::handleArguments(vector<Expression>& _arguments) +{ + // We have to fill from left to right, but we can only + // fill if everything to the right is just an identifier + // or a literal. + // Also we only descend into function calls if everything + // on the right is an identifier or literal. + + size_t i = _arguments.size(); + for (Expression const& arg: _arguments | boost::adaptors::reversed) + { + --i; + if (arg.type() != typeid(Identifier) && arg.type() != typeid(Literal)) + break; + } + // i points to the last element that is neither an identifier nor a literal, + // or to the first element if all of them are identifiers or literals. + + for (; i < _arguments.size(); ++i) + visit(_arguments.at(i)); +} + +void ExpressionJoiner::decrementLatestStatementPointer() +{ + if (!m_currentBlock) + return; + if (m_latestStatementInBlock > 0) + --m_latestStatementInBlock; + else + resetLatestStatementPointer(); +} + +void ExpressionJoiner::resetLatestStatementPointer() +{ + m_currentBlock = nullptr; + m_latestStatementInBlock = size_t(-1); +} + +Statement* ExpressionJoiner::latestStatement() +{ + if (!m_currentBlock) + return nullptr; + else + return &m_currentBlock->statements.at(m_latestStatementInBlock); +} + +bool ExpressionJoiner::isLatestStatementVarDeclJoinable(Identifier const& _identifier) +{ + Statement const* statement = latestStatement(); + if (!statement || statement->type() != typeid(VariableDeclaration)) + return false; + VariableDeclaration const& varDecl = boost::get<VariableDeclaration>(*statement); + if (varDecl.variables.size() != 1 || !varDecl.value) + return false; + assertThrow(varDecl.variables.size() == 1, OptimizerException, ""); + assertThrow(varDecl.value, OptimizerException, ""); + return varDecl.variables.at(0).name == _identifier.name && m_references[_identifier.name] == 1; +} diff --git a/libyul/optimiser/ExpressionJoiner.h b/libyul/optimiser/ExpressionJoiner.h new file mode 100644 index 00000000..0cc61981 --- /dev/null +++ b/libyul/optimiser/ExpressionJoiner.h @@ -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 <http://www.gnu.org/licenses/>. +*/ +/** + * Optimiser component that undoes what the ExpressionSplitter did, i.e. + * it more or less inlines variable declarations. + */ +#pragma once + +#include <libyul/ASTDataForward.h> + +#include <libyul/optimiser/ASTWalker.h> + +#include <map> + +namespace dev +{ +namespace yul +{ + +class NameCollector; + + +/** + * Optimiser component that modifies an AST in place, turning sequences + * of variable declarations into complex expressions, if the variables + * are declared in the right order. This component does the opposite + * of ExpressionSplitter. + * Since the order of opcode or function evaluation is unchanged, + * this transformation does not need to care about conflicting opcodes. + * + * Code of the form + * + * let a1 := mload(y) + * let a2 := mul(x, 4) + * sstore(a2, a1) + * + * is transformed into + * + * sstore(mul(x, 4), mload(y)) + * + * The transformation is not applied to loop conditions, because those are + * evaluated with each loop. + * + * The component can be applied to sub-blocks of the AST, you do not + * need to pass a full AST. + * + * Prerequisites: Disambiguator + * + * Implementation note: We visit the AST, modifying it in place. + * The class starts counting references and will only replace variables + * that have exactly one reference. It keeps a "latest statement pointer" + * which always points to the statement right before the current statement. + * Any function call or opcode will reset this pointer. If an identifier + * is encountered that was declared in the "latest statement", it is replaced + * by the value of the declaration, the "latest statement" is replaced + * by an empty block and the pointer is decremented. + * A block also resets the latest statement pointer. + */ +class ExpressionJoiner: public ASTModifier +{ +public: + static void run(Block& _ast); + +private: + explicit ExpressionJoiner(Block& _ast); + + void operator()(Block& _block) override; + void operator()(FunctionalInstruction&) override; + void operator()(FunctionCall&) override; + + using ASTModifier::visit; + void visit(Expression& _e) override; + + void handleArguments(std::vector<Expression>& _arguments); + + void decrementLatestStatementPointer(); + void resetLatestStatementPointer(); + Statement* latestStatement(); + bool isLatestStatementVarDeclJoinable(Identifier const& _identifier); + +private: + Block* m_currentBlock = nullptr; ///< Pointer to current block holding the statement being visited. + size_t m_latestStatementInBlock = 0; ///< Offset to m_currentBlock's statements of the last visited statement. + std::map<YulString, size_t> m_references; ///< Holds reference counts to all variable declarations in current block. +}; + +} +} diff --git a/libyul/optimiser/ExpressionSimplifier.cpp b/libyul/optimiser/ExpressionSimplifier.cpp new file mode 100644 index 00000000..64e9d7e7 --- /dev/null +++ b/libyul/optimiser/ExpressionSimplifier.cpp @@ -0,0 +1,60 @@ +/* + 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 uses the simplification rules to simplify expressions. + */ + +#include <libyul/optimiser/ExpressionSimplifier.h> + +#include <libyul/optimiser/SimplificationRules.h> +#include <libyul/optimiser/Semantics.h> +#include <libyul/optimiser/SSAValueTracker.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libdevcore/CommonData.h> + +using namespace std; +using namespace dev; +using namespace dev::yul; +using namespace dev::solidity; + + +void ExpressionSimplifier::visit(Expression& _expression) +{ + ASTModifier::visit(_expression); + while (auto match = SimplificationRules::findFirstMatch(_expression, m_ssaValues)) + { + // Do not apply the rule if it removes non-constant parts of the expression. + // TODO: The check could actually be less strict than "movable". + // We only require "Does not cause side-effects". + // Note: References to variables that are only assigned once are always movable, + // so if the value of the variable is not movable, the expression that references + // the variable still is. + + if (match->removesNonConstants && !MovableChecker(_expression).movable()) + return; + _expression = match->action().toExpression(locationOf(_expression)); + } +} + +void ExpressionSimplifier::run(Block& _ast) +{ + SSAValueTracker ssaValues; + ssaValues(_ast); + ExpressionSimplifier{ssaValues.values()}(_ast); +} diff --git a/libyul/optimiser/ExpressionSimplifier.h b/libyul/optimiser/ExpressionSimplifier.h new file mode 100644 index 00000000..5965a1bb --- /dev/null +++ b/libyul/optimiser/ExpressionSimplifier.h @@ -0,0 +1,55 @@ +/* + 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 uses the simplification rules to simplify expressions. + */ + +#pragma once + +#include <libyul/ASTDataForward.h> + +#include <libyul/optimiser/ASTWalker.h> + +namespace dev +{ +namespace yul +{ + +/** + * Applies simplification rules to all expressions. + * The component will work best if the code is in SSA form, but + * this is not required for correctness. + * + * Prerequisite: Disambiguator. + */ +class ExpressionSimplifier: public ASTModifier +{ +public: + using ASTModifier::operator(); + virtual void visit(Expression& _expression); + + static void run(Block& _ast); +private: + explicit ExpressionSimplifier(std::map<YulString, Expression const*> _ssaValues): + m_ssaValues(std::move(_ssaValues)) + {} + + std::map<YulString, Expression const*> m_ssaValues; +}; + +} +} diff --git a/libyul/optimiser/ExpressionSplitter.cpp b/libyul/optimiser/ExpressionSplitter.cpp new file mode 100644 index 00000000..a4b7a909 --- /dev/null +++ b/libyul/optimiser/ExpressionSplitter.cpp @@ -0,0 +1,105 @@ +/* + This file is part of solidity. + + solidity is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + solidity is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with solidity. If not, see <http://www.gnu.org/licenses/>. +*/ +/** + * Optimiser component that turns complex expressions into multiple variable + * declarations. + */ + +#include <libyul/optimiser/ExpressionSplitter.h> + +#include <libyul/optimiser/ASTWalker.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libdevcore/CommonData.h> + +#include <boost/range/adaptor/reversed.hpp> + +using namespace std; +using namespace dev; +using namespace dev::yul; +using namespace dev::solidity; + +void ExpressionSplitter::operator()(FunctionalInstruction& _instruction) +{ + for (auto& arg: _instruction.arguments | boost::adaptors::reversed) + outlineExpression(arg); +} + +void ExpressionSplitter::operator()(FunctionCall& _funCall) +{ + for (auto& arg: _funCall.arguments | boost::adaptors::reversed) + outlineExpression(arg); +} + +void ExpressionSplitter::operator()(If& _if) +{ + outlineExpression(*_if.condition); + (*this)(_if.body); +} + +void ExpressionSplitter::operator()(Switch& _switch) +{ + outlineExpression(*_switch.expression); + for (auto& _case: _switch.cases) + // Do not visit the case expression, nothing to split there. + (*this)(_case.body); +} + +void ExpressionSplitter::operator()(ForLoop& _loop) +{ + (*this)(_loop.pre); + // Do not visit the condition because we cannot split expressions there. + (*this)(_loop.post); + (*this)(_loop.body); +} + +void ExpressionSplitter::operator()(Block& _block) +{ + vector<Statement> saved; + swap(saved, m_statementsToPrefix); + + function<boost::optional<vector<Statement>>(Statement&)> f = + [&](Statement& _statement) -> boost::optional<vector<Statement>> { + m_statementsToPrefix.clear(); + visit(_statement); + if (m_statementsToPrefix.empty()) + return {}; + m_statementsToPrefix.emplace_back(std::move(_statement)); + return std::move(m_statementsToPrefix); + }; + iterateReplacing(_block.statements, f); + + swap(saved, m_statementsToPrefix); +} + +void ExpressionSplitter::outlineExpression(Expression& _expr) +{ + if (_expr.type() == typeid(Identifier)) + return; + + visit(_expr); + + SourceLocation location = locationOf(_expr); + YulString var = m_nameDispenser.newName({}); + m_statementsToPrefix.emplace_back(VariableDeclaration{ + location, + {{TypedName{location, var, {}}}}, + make_shared<Expression>(std::move(_expr)) + }); + _expr = Identifier{location, var}; +} diff --git a/libyul/optimiser/ExpressionSplitter.h b/libyul/optimiser/ExpressionSplitter.h new file mode 100644 index 00000000..339acbf0 --- /dev/null +++ b/libyul/optimiser/ExpressionSplitter.h @@ -0,0 +1,86 @@ +/* + This file is part of solidity. + + solidity is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + solidity is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with solidity. If not, see <http://www.gnu.org/licenses/>. +*/ +/** + * Optimiser component that turns complex expressions into multiple variable + * declarations. + */ +#pragma once + +#include <libyul/ASTDataForward.h> + +#include <libyul/optimiser/ASTWalker.h> +#include <libyul/optimiser/NameDispenser.h> + +#include <vector> + +namespace dev +{ +namespace yul +{ + +class NameCollector; + + +/** + * Optimiser component that modifies an AST in place, turning complex + * expressions into simple expressions and multiple variable declarations. + * + * Code of the form + * + * sstore(mul(x, 4), mload(y)) + * + * is transformed into + * + * let a1 := mload(y) + * let a2 := mul(x, 4) + * sstore(a2, a1) + * + * The transformation is not applied to loop conditions, because the loop control flow + * does not allow "outlining" the inner expressions in all cases. + * + * The final program should be in a form such that with the exception of a loop condition, + * function calls can only appear in the right-hand side of a variable declaration, + * assignments or expression statements and all arguments have to be constants or variables. + */ +class ExpressionSplitter: public ASTModifier +{ +public: + explicit ExpressionSplitter(NameDispenser& _nameDispenser): + m_nameDispenser(_nameDispenser) + { } + + virtual void operator()(FunctionalInstruction&) override; + virtual void operator()(FunctionCall&) override; + virtual void operator()(If&) override; + virtual void operator()(Switch&) override; + virtual void operator()(ForLoop&) override; + virtual void operator()(Block& _block) override; + +private: + /// Replaces the expression by a variable if it is a function call or functional + /// instruction. The declaration of the variable is appended to m_statementsToPrefix. + /// Recurses via visit(). + void outlineExpression(Expression& _expr); + + /// List of statements that should go in front of the currently visited AST element, + /// at the statement level. + std::vector<Statement> m_statementsToPrefix; + NameDispenser& m_nameDispenser; +}; + +} +} diff --git a/libyul/optimiser/FullInliner.cpp b/libyul/optimiser/FullInliner.cpp new file mode 100644 index 00000000..c9057cf3 --- /dev/null +++ b/libyul/optimiser/FullInliner.cpp @@ -0,0 +1,223 @@ +/* + 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 <libyul/optimiser/FullInliner.h> + +#include <libyul/optimiser/ASTCopier.h> +#include <libyul/optimiser/ASTWalker.h> +#include <libyul/optimiser/NameCollector.h> +#include <libyul/optimiser/Utilities.h> +#include <libyul/optimiser/Metrics.h> +#include <libyul/optimiser/SSAValueTracker.h> +#include <libyul/Exceptions.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libdevcore/CommonData.h> +#include <libdevcore/Visitor.h> + +#include <boost/range/adaptor/reversed.hpp> + +using namespace std; +using namespace dev; +using namespace dev::yul; +using namespace dev::solidity; + +FullInliner::FullInliner(Block& _ast, NameDispenser& _dispenser): + m_ast(_ast), m_nameDispenser(_dispenser) +{ + // Determine constants + SSAValueTracker tracker; + tracker(m_ast); + for (auto const& ssaValue: tracker.values()) + if (ssaValue.second && ssaValue.second->type() == typeid(Literal)) + m_constants.emplace(ssaValue.first); + + map<YulString, size_t> references = ReferencesCounter::countReferences(m_ast); + for (auto& statement: m_ast.statements) + { + if (statement.type() != typeid(FunctionDefinition)) + continue; + FunctionDefinition& fun = boost::get<FunctionDefinition>(statement); + m_functions[fun.name] = &fun; + // Always inline functions that are only called once. + if (references[fun.name] == 1) + m_alwaysInline.emplace(fun.name); + updateCodeSize(fun); + } +} + +void FullInliner::run() +{ + for (auto& statement: m_ast.statements) + if (statement.type() == typeid(Block)) + handleBlock({}, boost::get<Block>(statement)); + + // TODO it might be good to determine a visiting order: + // first handle functions that are called from many places. + for (auto const& fun: m_functions) + { + handleBlock(fun.second->name, fun.second->body); + updateCodeSize(*fun.second); + } +} + +void FullInliner::updateCodeSize(FunctionDefinition& fun) +{ + m_functionSizes[fun.name] = CodeSize::codeSize(fun.body); +} + +void FullInliner::handleBlock(YulString _currentFunctionName, Block& _block) +{ + InlineModifier{*this, m_nameDispenser, _currentFunctionName}(_block); +} + +bool FullInliner::shallInline(FunctionCall const& _funCall, YulString _callSite) +{ + // No recursive inlining + if (_funCall.functionName.name == _callSite) + return false; + + FunctionDefinition& calledFunction = function(_funCall.functionName.name); + if (m_alwaysInline.count(calledFunction.name)) + return true; + + // Constant arguments might provide a means for further optimization, so they cause a bonus. + bool constantArg = false; + for (auto const& argument: _funCall.arguments) + if (argument.type() == typeid(Literal) || ( + argument.type() == typeid(Identifier) && + m_constants.count(boost::get<Identifier>(argument).name) + )) + { + constantArg = true; + break; + } + + size_t size = m_functionSizes.at(calledFunction.name); + return (size < 10 || (constantArg && size < 50)); +} + + +void InlineModifier::operator()(Block& _block) +{ + function<boost::optional<vector<Statement>>(Statement&)> f = [&](Statement& _statement) -> boost::optional<vector<Statement>> { + visit(_statement); + return tryInlineStatement(_statement); + }; + iterateReplacing(_block.statements, f); +} + +boost::optional<vector<Statement>> InlineModifier::tryInlineStatement(Statement& _statement) +{ + // Only inline for expression statements, assignments and variable declarations. + Expression* e = boost::apply_visitor(GenericFallbackReturnsVisitor<Expression*, ExpressionStatement, Assignment, VariableDeclaration>( + [](ExpressionStatement& _s) { return &_s.expression; }, + [](Assignment& _s) { return _s.value.get(); }, + [](VariableDeclaration& _s) { return _s.value.get(); } + ), _statement); + if (e) + { + // Only inline direct function calls. + FunctionCall* funCall = boost::apply_visitor(GenericFallbackReturnsVisitor<FunctionCall*, FunctionCall&>( + [](FunctionCall& _e) { return &_e; } + ), *e); + if (funCall && m_driver.shallInline(*funCall, m_currentFunction)) + return performInline(_statement, *funCall); + } + return {}; +} + +vector<Statement> InlineModifier::performInline(Statement& _statement, FunctionCall& _funCall) +{ + vector<Statement> newStatements; + map<YulString, YulString> variableReplacements; + + FunctionDefinition& function = m_driver.function(_funCall.functionName.name); + + // helper function to create a new variable that is supposed to model + // an existing variable. + auto newVariable = [&](TypedName const& _existingVariable, Expression* _value) { + YulString newName = m_nameDispenser.newName(_existingVariable.name, function.name); + variableReplacements[_existingVariable.name] = newName; + VariableDeclaration varDecl{_funCall.location, {{_funCall.location, newName, _existingVariable.type}}, {}}; + if (_value) + varDecl.value = make_shared<Expression>(std::move(*_value)); + newStatements.emplace_back(std::move(varDecl)); + }; + + for (size_t i = 0; i < _funCall.arguments.size(); ++i) + newVariable(function.parameters[i], &_funCall.arguments[i]); + for (auto const& var: function.returnVariables) + newVariable(var, nullptr); + + Statement newBody = BodyCopier(m_nameDispenser, function.name, variableReplacements)(function.body); + newStatements += std::move(boost::get<Block>(newBody).statements); + + boost::apply_visitor(GenericFallbackVisitor<Assignment, VariableDeclaration>{ + [&](Assignment& _assignment) + { + for (size_t i = 0; i < _assignment.variableNames.size(); ++i) + newStatements.emplace_back(Assignment{ + _assignment.location, + {_assignment.variableNames[i]}, + make_shared<Expression>(Identifier{ + _assignment.location, + variableReplacements.at(function.returnVariables[i].name) + }) + }); + }, + [&](VariableDeclaration& _varDecl) + { + for (size_t i = 0; i < _varDecl.variables.size(); ++i) + newStatements.emplace_back(VariableDeclaration{ + _varDecl.location, + {std::move(_varDecl.variables[i])}, + make_shared<Expression>(Identifier{ + _varDecl.location, + variableReplacements.at(function.returnVariables[i].name) + }) + }); + } + // nothing to be done for expression statement + }, _statement); + return newStatements; +} + +Statement BodyCopier::operator()(VariableDeclaration const& _varDecl) +{ + for (auto const& var: _varDecl.variables) + m_variableReplacements[var.name] = m_nameDispenser.newName(var.name, m_varNamePrefix); + return ASTCopier::operator()(_varDecl); +} + +Statement BodyCopier::operator()(FunctionDefinition const& _funDef) +{ + assertThrow(false, OptimizerException, "Function hoisting has to be done before function inlining."); + return _funDef; +} + +YulString BodyCopier::translateIdentifier(YulString _name) +{ + if (m_variableReplacements.count(_name)) + return m_variableReplacements.at(_name); + else + return _name; +} diff --git a/libyul/optimiser/FullInliner.h b/libyul/optimiser/FullInliner.h new file mode 100644 index 00000000..66ce8e2f --- /dev/null +++ b/libyul/optimiser/FullInliner.h @@ -0,0 +1,156 @@ +/* + This file is part of solidity. + + solidity is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + solidity is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with solidity. If not, see <http://www.gnu.org/licenses/>. +*/ +/** + * Optimiser component that performs function inlining for arbitrary functions. + */ +#pragma once + +#include <libyul/ASTDataForward.h> + +#include <libyul/optimiser/ASTCopier.h> +#include <libyul/optimiser/ASTWalker.h> +#include <libyul/optimiser/NameDispenser.h> +#include <libyul/Exceptions.h> + +#include <libevmasm/SourceLocation.h> + +#include <boost/variant.hpp> +#include <boost/optional.hpp> + +#include <set> + +namespace dev +{ +namespace yul +{ + +class NameCollector; + + +/** + * Optimiser component that modifies an AST in place, inlining functions. + * Expressions are expected to be split, i.e. the component will only inline + * function calls that are at the root of the expression and that only contains + * variables as arguments. More specifically, it will inline + * - let x1, ..., xn := f(a1, ..., am) + * - x1, ..., xn := f(a1, ..., am) + * f(a1, ..., am) + * + * The transform changes code of the form + * + * function f(a, b) -> c { ... } + * let z := f(x, y) + * + * into + * + * function f(a, b) -> c { ... } + * + * let f_a := x + * let f_b := y + * let f_c + * code of f, with replacements: a -> f_a, b -> f_b, c -> f_c + * let z := f_c + * + * Prerequisites: Disambiguator, Function Hoister + * More efficient if run after: Expression Splitter + */ +class FullInliner: public ASTModifier +{ +public: + explicit FullInliner(Block& _ast, NameDispenser& _dispenser); + + void run(); + + /// Inlining heuristic. + /// @param _callSite the name of the function in which the function call is located. + bool shallInline(FunctionCall const& _funCall, YulString _callSite); + + FunctionDefinition& function(YulString _name) { return *m_functions.at(_name); } + +private: + void updateCodeSize(FunctionDefinition& fun); + void handleBlock(YulString _currentFunctionName, Block& _block); + + /// The AST to be modified. The root block itself will not be modified, because + /// we store pointers to functions. + Block& m_ast; + std::map<YulString, FunctionDefinition*> m_functions; + /// Names of functions to always inline. + std::set<YulString> m_alwaysInline; + /// Variables that are constants (used for inlining heuristic) + std::set<YulString> m_constants; + std::map<YulString, size_t> m_functionSizes; + 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, YulString _functionName): + m_currentFunction(std::move(_functionName)), + m_driver(_driver), + m_nameDispenser(_nameDispenser) + { } + + virtual void operator()(Block& _block) override; + +private: + boost::optional<std::vector<Statement>> tryInlineStatement(Statement& _statement); + std::vector<Statement> performInline(Statement& _statement, FunctionCall& _funCall); + + YulString 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, + YulString _varNamePrefix, + std::map<YulString, YulString> 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 YulString translateIdentifier(YulString _name) override; + + NameDispenser& m_nameDispenser; + YulString m_varNamePrefix; + std::map<YulString, YulString> m_variableReplacements; +}; + + +} +} diff --git a/libyul/optimiser/FunctionGrouper.cpp b/libyul/optimiser/FunctionGrouper.cpp new file mode 100644 index 00000000..3d2e5322 --- /dev/null +++ b/libyul/optimiser/FunctionGrouper.cpp @@ -0,0 +1,47 @@ +/* + 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 changes the code of a block so that all non-function definition + * statements are moved to a block of their own followed by all function definitions. + */ + +#include <libyul/optimiser/FunctionGrouper.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <boost/range/algorithm_ext/erase.hpp> + +using namespace std; +using namespace dev; +using namespace dev::yul; +using namespace dev::solidity; + + +void FunctionGrouper::operator()(Block& _block) +{ + vector<Statement> reordered; + reordered.emplace_back(Block{_block.location, {}}); + + for (auto&& statement: _block.statements) + { + if (statement.type() == typeid(FunctionDefinition)) + reordered.emplace_back(std::move(statement)); + else + boost::get<Block>(reordered.front()).statements.emplace_back(std::move(statement)); + } + _block.statements = std::move(reordered); +} diff --git a/libyul/optimiser/FunctionGrouper.h b/libyul/optimiser/FunctionGrouper.h new file mode 100644 index 00000000..63cfbfb1 --- /dev/null +++ b/libyul/optimiser/FunctionGrouper.h @@ -0,0 +1,46 @@ +/* + 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 changes the code of a black so that all non-function definition + * instructions are moved to a block of their own followed by all function definitions. + */ + +#pragma once + +#include <libyul/ASTDataForward.h> + +namespace dev +{ +namespace yul +{ + +/** + * Moves all instructions in a block into a new block at the start of the block, followed by + * all function definitions. + * + * After this step, a block is of the form + * { { I...} F... } + * Where I are (non-function-definition) instructions and F are function definitions. + */ +class FunctionGrouper +{ +public: + void operator()(Block& _block); +}; + +} +} diff --git a/libyul/optimiser/FunctionHoister.cpp b/libyul/optimiser/FunctionHoister.cpp new file mode 100644 index 00000000..c196dead --- /dev/null +++ b/libyul/optimiser/FunctionHoister.cpp @@ -0,0 +1,51 @@ +/* + 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 changes the code so that it consists of a block starting with + * a single block followed only by function definitions and with no functions defined + * anywhere else. + */ + +#include <libyul/optimiser/FunctionHoister.h> +#include <libyul/optimiser/Utilities.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libdevcore/CommonData.h> + +using namespace std; +using namespace dev; +using namespace dev::yul; +using namespace dev::solidity; + +void FunctionHoister::operator()(Block& _block) +{ + bool topLevel = m_isTopLevel; + m_isTopLevel = false; + for (auto&& statement: _block.statements) + { + boost::apply_visitor(*this, statement); + if (statement.type() == typeid(FunctionDefinition)) + { + m_functions.emplace_back(std::move(statement)); + statement = Block{_block.location, {}}; + } + } + removeEmptyBlocks(_block); + if (topLevel) + _block.statements += std::move(m_functions); +} diff --git a/libyul/optimiser/FunctionHoister.h b/libyul/optimiser/FunctionHoister.h new file mode 100644 index 00000000..823b9e2b --- /dev/null +++ b/libyul/optimiser/FunctionHoister.h @@ -0,0 +1,52 @@ +/* + 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 changes the code so that all function definitions are at the top + * level block. + */ + +#pragma once + +#include <libyul/ASTDataForward.h> + +#include <libyul/optimiser/ASTWalker.h> + +namespace dev +{ +namespace yul +{ + +/** + * Moves all functions to the top-level scope. + * Applying this transformation to source code that has ambiguous identifiers might + * lead to invalid code. + * + * Prerequisites: Disambiguator + */ +class FunctionHoister: public ASTModifier +{ +public: + using ASTModifier::operator(); + virtual void operator()(Block& _block); + +private: + bool m_isTopLevel = true; + std::vector<Statement> m_functions; +}; + +} +} diff --git a/libyul/optimiser/InlinableExpressionFunctionFinder.cpp b/libyul/optimiser/InlinableExpressionFunctionFinder.cpp new file mode 100644 index 00000000..deaaee97 --- /dev/null +++ b/libyul/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 <http://www.gnu.org/licenses/>. +*/ +/** + * Optimiser component that identifies functions to be inlined. + */ + +#include <libyul/optimiser/InlinableExpressionFunctionFinder.h> + +#include <libyul/optimiser/Utilities.h> + +#include <libsolidity/inlineasm/AsmData.h> + +using namespace std; +using namespace dev; +using namespace dev::yul; + +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) + { + YulString retVariable = _function.returnVariables.front().name; + Statement const& bodyStatement = _function.body.statements.front(); + if (bodyStatement.type() == typeid(Assignment)) + { + Assignment const& assignment = boost::get<Assignment>(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. + assertThrow(m_disallowedIdentifiers.empty() && !m_foundDisallowedIdentifier, OptimizerException, ""); + m_disallowedIdentifiers = set<YulString>{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/libyul/optimiser/InlinableExpressionFunctionFinder.h b/libyul/optimiser/InlinableExpressionFunctionFinder.h new file mode 100644 index 00000000..baf4bbfc --- /dev/null +++ b/libyul/optimiser/InlinableExpressionFunctionFinder.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 <http://www.gnu.org/licenses/>. +*/ +/** + * Optimiser component that identifies functions to be inlined. + */ + +#pragma once + +#include <libyul/ASTDataForward.h> +#include <libyul/optimiser/ASTWalker.h> + +#include <set> + +namespace dev +{ +namespace yul +{ + +/** + * 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 := <functional expression> + * - 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<YulString, FunctionDefinition const*> 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(YulString _name) + { + if (m_disallowedIdentifiers.count(_name)) + m_foundDisallowedIdentifier = true; + } + + bool m_foundDisallowedIdentifier = false; + std::set<YulString> m_disallowedIdentifiers; + std::map<YulString, FunctionDefinition const*> m_inlinableFunctions; +}; + +} +} diff --git a/libyul/optimiser/MainFunction.cpp b/libyul/optimiser/MainFunction.cpp new file mode 100644 index 00000000..f3306598 --- /dev/null +++ b/libyul/optimiser/MainFunction.cpp @@ -0,0 +1,54 @@ +/* + 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/>. +*/ +/** + * Changes the topmost block to be a function with a specific name ("main") which has no + * inputs nor outputs. + */ + +#include <libyul/optimiser/MainFunction.h> + +#include <libyul/optimiser/NameCollector.h> +#include <libyul/Exceptions.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libdevcore/CommonData.h> + +using namespace std; +using namespace dev; +using namespace dev::yul; +using namespace dev::solidity; + +void MainFunction::operator()(Block& _block) +{ + assertThrow(_block.statements.size() >= 1, OptimizerException, ""); + assertThrow(_block.statements[0].type() == typeid(Block), OptimizerException, ""); + for (size_t i = 1; i < _block.statements.size(); ++i) + assertThrow(_block.statements.at(i).type() == typeid(FunctionDefinition), OptimizerException, ""); + /// @todo this should handle scopes properly and instead of an assertion it should rename the conflicting function + assertThrow(NameCollector(_block).names().count(YulString{"main"}) == 0, OptimizerException, ""); + + Block& block = boost::get<Block>(_block.statements[0]); + FunctionDefinition main{ + block.location, + YulString{"main"}, + {}, + {}, + std::move(block) + }; + _block.statements[0] = std::move(main); +} diff --git a/libyul/optimiser/MainFunction.h b/libyul/optimiser/MainFunction.h new file mode 100644 index 00000000..4a73283a --- /dev/null +++ b/libyul/optimiser/MainFunction.h @@ -0,0 +1,41 @@ +/* + 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/>. +*/ +/** + * Changes the topmost block to be a function with a specific name ("main") which has no + * inputs nor outputs. + */ + +#pragma once + +#include <libyul/ASTDataForward.h> + +namespace dev +{ +namespace yul +{ + +/** + * Prerequisites: Function Grouper + */ +class MainFunction +{ +public: + void operator()(Block& _block); +}; + +} +} diff --git a/libyul/optimiser/Metrics.cpp b/libyul/optimiser/Metrics.cpp new file mode 100644 index 00000000..066c6b58 --- /dev/null +++ b/libyul/optimiser/Metrics.cpp @@ -0,0 +1,59 @@ +/*( + 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/>. +*/ +/** +* Module providing metrics for the optimizer. +*/ + +#include <libyul/optimiser/Metrics.h> + +#include <libsolidity/inlineasm/AsmData.h> + +using namespace dev; +using namespace dev::yul; + +size_t CodeSize::codeSize(Statement const& _statement) +{ + CodeSize cs; + cs.visit(_statement); + return cs.m_size; +} + +size_t CodeSize::codeSize(Expression const& _expression) +{ + CodeSize cs; + cs.visit(_expression); + return cs.m_size; +} + +size_t CodeSize::codeSize(Block const& _block) +{ + CodeSize cs; + cs(_block); + return cs.m_size; +} + +void CodeSize::visit(Statement const& _statement) +{ + ++m_size; + ASTWalker::visit(_statement); +} + +void CodeSize::visit(Expression const& _expression) +{ + ++m_size; + ASTWalker::visit(_expression); +} diff --git a/libyul/optimiser/Metrics.h b/libyul/optimiser/Metrics.h new file mode 100644 index 00000000..47c7ec79 --- /dev/null +++ b/libyul/optimiser/Metrics.h @@ -0,0 +1,52 @@ +/* + 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/>. +*/ +/** + * Module providing metrics for the optimizer. + */ + +#pragma once + +#include <libyul/optimiser/ASTWalker.h> + +namespace dev +{ +namespace yul +{ + +class CodeSize: public ASTWalker +{ +public: + /// Returns a metric for the code size of an AST element. + /// More specifically, it returns the number of AST nodes. + static size_t codeSize(Statement const& _statement); + /// Returns a metric for the code size of an AST element. + /// More specifically, it returns the number of AST nodes. + static size_t codeSize(Expression const& _expression); + /// Returns a metric for the code size of an AST element. + /// More specifically, it returns the number of AST nodes. + static size_t codeSize(Block const& _block); + +private: + virtual void visit(Statement const& _statement) override; + virtual void visit(Expression const& _expression) override; + +private: + size_t m_size = 0; +}; + +} +} diff --git a/libyul/optimiser/NameCollector.cpp b/libyul/optimiser/NameCollector.cpp new file mode 100644 index 00000000..36f55b99 --- /dev/null +++ b/libyul/optimiser/NameCollector.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 <http://www.gnu.org/licenses/>. +*/ +/** + * Specific AST walker that collects all defined names. + */ + +#include <libyul/optimiser/NameCollector.h> + +#include <libsolidity/inlineasm/AsmData.h> + +using namespace std; +using namespace dev; +using namespace dev::yul; + +void NameCollector::operator()(VariableDeclaration const& _varDecl) +{ + for (auto const& var: _varDecl.variables) + m_names.emplace(var.name); +} + +void NameCollector::operator ()(FunctionDefinition const& _funDef) +{ + m_names.emplace(_funDef.name); + for (auto const arg: _funDef.parameters) + m_names.emplace(arg.name); + for (auto const ret: _funDef.returnVariables) + m_names.emplace(ret.name); + ASTWalker::operator ()(_funDef); +} + +void ReferencesCounter::operator()(Identifier const& _identifier) +{ + ++m_references[_identifier.name]; +} + +void ReferencesCounter::operator()(FunctionCall const& _funCall) +{ + ++m_references[_funCall.functionName.name]; + ASTWalker::operator()(_funCall); +} + +map<YulString, size_t> ReferencesCounter::countReferences(Block const& _block) +{ + ReferencesCounter counter; + counter(_block); + return counter.references(); +} + +map<YulString, size_t> ReferencesCounter::countReferences(Expression const& _expression) +{ + ReferencesCounter counter; + counter.visit(_expression); + return counter.references(); +} + +void Assignments::operator()(Assignment const& _assignment) +{ + for (auto const& var: _assignment.variableNames) + m_names.emplace(var.name); +} diff --git a/libyul/optimiser/NameCollector.h b/libyul/optimiser/NameCollector.h new file mode 100644 index 00000000..b76eec30 --- /dev/null +++ b/libyul/optimiser/NameCollector.h @@ -0,0 +1,86 @@ +/* + This file is part of solidity. + + solidity is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + solidity is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with solidity. If not, see <http://www.gnu.org/licenses/>. +*/ +/** + * Specific AST walkers that collect facts about identifiers and definitions. + */ + +#pragma once + +#include <libyul/optimiser/ASTWalker.h> + +#include <map> +#include <set> + +namespace dev +{ +namespace yul +{ + +/** + * Specific AST walker that collects all defined names. + */ +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<YulString> names() const { return m_names; } +private: + std::set<YulString> m_names; +}; + +/** + * Specific AST walker that counts all references to all declarations. + */ +class ReferencesCounter: public ASTWalker +{ +public: + using ASTWalker::operator (); + virtual void operator()(Identifier const& _identifier); + virtual void operator()(FunctionCall const& _funCall); + + static std::map<YulString, size_t> countReferences(Block const& _block); + static std::map<YulString, size_t> countReferences(Expression const& _expression); + + std::map<YulString, size_t> const& references() const { return m_references; } +private: + std::map<YulString, size_t> m_references; +}; + +/** + * Specific AST walker that finds all variables that are assigned to. + */ +class Assignments: public ASTWalker +{ +public: + using ASTWalker::operator (); + virtual void operator()(Assignment const& _assignment) override; + + std::set<YulString> const& names() const { return m_names; } +private: + std::set<YulString> m_names; +}; + +} +} diff --git a/libyul/optimiser/NameDispenser.cpp b/libyul/optimiser/NameDispenser.cpp new file mode 100644 index 00000000..3c870fa5 --- /dev/null +++ b/libyul/optimiser/NameDispenser.cpp @@ -0,0 +1,62 @@ +/* + 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 <libyul/optimiser/NameDispenser.h> + +#include <libyul/optimiser/NameCollector.h> + +#include <libsolidity/inlineasm/AsmData.h> + +using namespace std; +using namespace dev; +using namespace dev::yul; + +NameDispenser::NameDispenser(Block const& _ast): + NameDispenser(NameCollector(_ast).names()) +{ +} + +NameDispenser::NameDispenser(set<YulString> _usedNames): + m_usedNames(std::move(_usedNames)) +{ +} + +YulString NameDispenser::newName(YulString _nameHint, YulString _context) +{ + // Shortening rules: Use a suffix of _prefix and a prefix of _context. + YulString prefix = _nameHint; + + if (!_context.empty()) + prefix = YulString{_context.str().substr(0, 10) + "_" + prefix.str()}; + + return newNameInternal(prefix); +} + +YulString NameDispenser::newNameInternal(YulString _nameHint) +{ + YulString name = _nameHint; + while (name.empty() || m_usedNames.count(name)) + { + m_counter++; + name = YulString(_nameHint.str() + "_" + to_string(m_counter)); + } + m_usedNames.emplace(name); + return name; +} diff --git a/libyul/optimiser/NameDispenser.h b/libyul/optimiser/NameDispenser.h new file mode 100644 index 00000000..7311440b --- /dev/null +++ b/libyul/optimiser/NameDispenser.h @@ -0,0 +1,61 @@ +/* + 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 <libyul/ASTDataForward.h> + +#include <libyul/YulString.h> + +#include <set> + +namespace dev +{ +namespace yul +{ + +/** + * Optimizer component that can be used to generate new names that + * do not conflict with existing names. + * + * Tries to keep names short and appends decimals to disambiguate. + */ +class NameDispenser +{ +public: + /// Initialize the name dispenser with all the names used in the given AST. + explicit NameDispenser(Block const& _ast); + /// Initialize the name dispenser with the given used names. + explicit NameDispenser(std::set<YulString> _usedNames); + + /// @returns a currently unused name that should be similar to _nameHint + /// and prefixed by _context if present. + /// If the resulting name would be too long, trims the context at the end + /// and the name hint at the start. + YulString newName(YulString _nameHint, YulString _context = {}); + +private: + YulString newNameInternal(YulString _nameHint); + + std::set<YulString> m_usedNames; + size_t m_counter = 0; +}; + +} +} diff --git a/libyul/optimiser/README.md b/libyul/optimiser/README.md new file mode 100644 index 00000000..c2575179 --- /dev/null +++ b/libyul/optimiser/README.md @@ -0,0 +1,159 @@ +Note that the Yul optimiser is still in research phase. Because of that, +the following description might not fully reflect the current or even +planned state of the optimiser. + +## Yul Optimiser + +The Yul optimiser consists of several stages and components that all transform +the AST in a semantically equivalent way. The goal is to end up either with code +that is shorter or at least only marginally longer but will allow further +optimisation steps. + +The optimiser currently follows a purely greedy strategy and does not do any +backtracking. + +## Disambiguator + +The disambiguator takes an AST and returns a fresh copy where all identifiers have +names unique to the input AST. This is a prerequisite for all other optimiser stages. +One of the benefits is that identifier lookup does not need to take scopes into account +and we can basically ignore the result of the analysis phase. + +All subsequent stages have the property that all names stay unique. This means if +a new identifier needs to be introduced, a new unique name is generated. + +## Function Hoister + +The function hoister moves all function definitions to the end of the topmost block. This is +a semantically equivalent transformation as long as it is performed after the +disambiguation stage. The reason is that moving a definition to a higher-level block cannot decrease +its visibility and it is impossible to reference variables defined in a different function. + +The benefit of this stage is that function definitions can be looked up more easily. + +## Function Grouper + +The function grouper has to be applied after the disambiguator and the function hoister. +Its effect is that all topmost elements that are not function definitions are moved +into a single block which is the first statement of the root block. + +After this step, a program has the following normal form: + + { I F... } + +Where I is a block that does not contain any function definitions (not even recursively) +and F is a list of function definitions such that no function contains a function definition. + +## Functional Inliner + +The functional inliner depends on the disambiguator, the function hoister and function grouper. +It performs function inlining such that the result of the inlining is an expression. This can +only be done if the body of the function to be inlined has the form ``{ r := E }`` where ``r`` +is the single return value of the function, ``E`` is an expression and all arguments in the +function call are so-called movable expressions. A movable expression is either a literal, a +variable or a function call (or EVM opcode) which does not have side-effects and also does not +depend on any side-effects. + +As an example, neither ``mload`` nor ``mstore`` would be allowed. + +## Expression Splitter + +The expression splitter turns expressions like ``add(mload(x), mul(mload(y), 0x20))`` +into a sequence of declarations of unique variables that are assigned sub-expressions +of that expression so that each function call has only variables or literals +as arguments. + +The above would be transformed into + + { + let _1 := mload(y) + let _2 := mul(_1, 0x20) + let _3 := mload(x) + let z := add(_3, _2) + } + +Note that this transformation does not change the order of opcodes or function calls. + +It is not applied to loop conditions, because the loop control flow does not allow +this "outlining" of the inner expressions in all cases. + +The final program should be in a form such that with the exception of loop conditions, +function calls can only appear in the right-hand side of a variable declaration, +assignments or expression statements and all arguments have to be constants or variables. + +The benefits of this form are that it is much easier to re-order the sequence of opcodes +and it is also easier to perform function call inlining. The drawback is that +such code is much harder to read for humans. + +## Expression Joiner + +This is the opposite operation of the expression splitter. It turns a sequence of +variable declarations that have exactly one reference into a complex expression. +This stage again fully preserves the order of function calls and opcode executions. +It does not make use of any information concerning the commutability of opcodes; +if moving the value of a variable to its place of use would change the order +of any function call or opcode execution, the transformation is not performed. + +Note that the component will not move the assigned value of a variable assignment +or a variable that is referenced more than once. + +## Common Subexpression Eliminator + +This step replaces a subexpression by the value of a pre-existing variable +that currently has the same value (only if the value is movable), based +on a syntactic comparison. + +This can be used to compute a local value numbering, especially if the +expression splitter is used before. + +The expression simplifier will be able to perform better replacements +if the common subexpression eliminator was run right before it. + +Prerequisites: Disambiguator + +## Full Function Inliner + +## Rematerialisation + +The rematerialisation stage tries to replace variable references by the expression that +was last assigned to the variable. This is of course only beneficial if this expression +is comparatively cheap to evaluate. Furthermore, it is only semantically equivalent if +the value of the expression did not change between the point of assignment and the +point of use. The main benefit of this stage is that it can save stack slots if it +leads to a variable being eliminated completely (see below), but it can also +save a DUP opcode on the EVM if the expression is very cheap. + +The algorithm only allows movable expressions (see above for a definition) in this case. +Expressions that contain other variables are also disallowed if one of those variables +have been assigned to in the meantime. This is also not applied to variables where +assignment and use span across loops and conditionals. + +## Unused Definition Pruner + +If a variable or function is not referenced, it is removed from the code. +If there are two assignments to a variable where the first one is a movable expression +and the variable is not used between the two assignments (and the second is not inside +a loop or conditional, the first one is not inside), the first assignment is removed. + +This step also removes movable expression statements. + + +## Function Unifier + +## Expression Simplifier + +This step can only be applied for the EVM-flavoured dialect of Yul. It applies +simple rules like ``x + 0 == x`` to simplify expressions. + +## Ineffective Statement Remover + +This step removes statements that have no side-effects. + +## WebAssembly specific + +### Main Function + +Changes the topmost block to be a function with a specific name ("main") which has no +inputs nor outputs. + +Depends on the Function Grouper. diff --git a/libyul/optimiser/RedundantAssignEliminator.cpp b/libyul/optimiser/RedundantAssignEliminator.cpp new file mode 100644 index 00000000..b7217074 --- /dev/null +++ b/libyul/optimiser/RedundantAssignEliminator.cpp @@ -0,0 +1,230 @@ +/* + 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 removes assignments to variables that are not used + * until they go out of scope or are re-assigned. + */ + +#include <libyul/optimiser/RedundantAssignEliminator.h> + +#include <libyul/optimiser/Semantics.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libdevcore/CommonData.h> + +#include <boost/range/algorithm_ext/erase.hpp> + +using namespace std; +using namespace dev; +using namespace dev::yul; +using namespace dev::solidity; + +void RedundantAssignEliminator::operator()(Identifier const& _identifier) +{ + changeUndecidedTo(_identifier.name, State::Used); +} + +void RedundantAssignEliminator::operator()(VariableDeclaration const& _variableDeclaration) +{ + ASTWalker::operator()(_variableDeclaration); + + for (auto const& var: _variableDeclaration.variables) + m_declaredVariables.emplace(var.name); +} + +void RedundantAssignEliminator::operator()(Assignment const& _assignment) +{ + visit(*_assignment.value); + for (auto const& var: _assignment.variableNames) + changeUndecidedTo(var.name, State::Unused); + + if (_assignment.variableNames.size() == 1) + // Default-construct it in "Undecided" state if it does not yet exist. + m_assignments[_assignment.variableNames.front().name][&_assignment]; +} + +void RedundantAssignEliminator::operator()(If const& _if) +{ + visit(*_if.condition); + + RedundantAssignEliminator branch{*this}; + branch(_if.body); + + join(branch); +} + +void RedundantAssignEliminator::operator()(Switch const& _switch) +{ + visit(*_switch.expression); + + bool hasDefault = false; + vector<RedundantAssignEliminator> branches; + for (auto const& c: _switch.cases) + { + if (!c.value) + hasDefault = true; + branches.emplace_back(*this); + branches.back()(c.body); + } + + if (hasDefault) + { + *this = std::move(branches.back()); + branches.pop_back(); + } + for (auto& branch: branches) + join(branch); +} + +void RedundantAssignEliminator::operator()(FunctionDefinition const& _functionDefinition) +{ + (*this)(_functionDefinition.body); + + for (auto const& param: _functionDefinition.parameters) + { + changeUndecidedTo(param.name, State::Unused); + finalize(param.name); + } + for (auto const& retParam: _functionDefinition.returnVariables) + { + changeUndecidedTo(retParam.name, State::Used); + finalize(retParam.name); + } +} + +void RedundantAssignEliminator::operator()(ForLoop const& _forLoop) +{ + // This will set all variables that are declared in this + // block to "unused" when it is destroyed. + BlockScope scope(*this); + + // We need to visit the statements directly because of the + // scoping rules. + walkVector(_forLoop.pre.statements); + + // We just run the loop twice to account for the + // back edge. + // There need not be more runs because we only have three different states. + + visit(*_forLoop.condition); + + RedundantAssignEliminator zeroRuns{*this}; + + (*this)(_forLoop.body); + (*this)(_forLoop.post); + + visit(*_forLoop.condition); + + RedundantAssignEliminator oneRun{*this}; + + (*this)(_forLoop.body); + (*this)(_forLoop.post); + + visit(*_forLoop.condition); + + // Order does not matter because "max" is commutative and associative. + join(oneRun); + join(zeroRuns); +} + +void RedundantAssignEliminator::operator()(Block const& _block) +{ + // This will set all variables that are declared in this + // block to "unused" when it is destroyed. + BlockScope scope(*this); + + ASTWalker::operator()(_block); +} + +void RedundantAssignEliminator::run(Block& _ast) +{ + RedundantAssignEliminator rae; + rae(_ast); + + AssignmentRemover remover{rae.m_assignmentsToRemove}; + remover(_ast); +} + +template <class K, class V, class F> +void joinMap(std::map<K, V>& _a, std::map<K, V>&& _b, F _conflictSolver) +{ + // TODO Perhaps it is better to just create a sorted list + // and then use insert(begin, end) + + auto ita = _a.begin(); + auto aend = _a.end(); + auto itb = _b.begin(); + auto bend = _b.end(); + + for (; itb != bend; ++ita) + { + if (ita == aend) + ita = _a.insert(ita, std::move(*itb++)); + else if (ita->first < itb->first) + continue; + else if (itb->first < ita->first) + ita = _a.insert(ita, std::move(*itb++)); + else + { + _conflictSolver(ita->second, std::move(itb->second)); + ++itb; + } + } +} + +void RedundantAssignEliminator::join(RedundantAssignEliminator& _other) +{ + m_assignmentsToRemove.insert(begin(_other.m_assignmentsToRemove), end(_other.m_assignmentsToRemove)); + + joinMap(m_assignments, std::move(_other.m_assignments), []( + map<Assignment const*, State>& _assignmentHere, + map<Assignment const*, State>&& _assignmentThere + ) + { + return joinMap(_assignmentHere, std::move(_assignmentThere), State::join); + }); +} + +void RedundantAssignEliminator::changeUndecidedTo(YulString _variable, RedundantAssignEliminator::State _newState) +{ + for (auto& assignment: m_assignments[_variable]) + if (assignment.second == State{State::Undecided}) + assignment.second = _newState; +} + +void RedundantAssignEliminator::finalize(YulString _variable) +{ + for (auto& assignment: m_assignments[_variable]) + { + assertThrow(assignment.second != State::Undecided, OptimizerException, ""); + if (assignment.second == State{State::Unused} && MovableChecker{*assignment.first->value}.movable()) + // TODO the only point where we actually need this + // to be a set is for the for loop + m_assignmentsToRemove.insert(assignment.first); + } + m_assignments.erase(_variable); +} + +void AssignmentRemover::operator()(Block& _block) +{ + boost::range::remove_erase_if(_block.statements, [=](Statement const& _statement) -> bool { + return _statement.type() == typeid(Assignment) && m_toRemove.count(&boost::get<Assignment>(_statement)); + }); + + ASTModifier::operator()(_block); +} diff --git a/libyul/optimiser/RedundantAssignEliminator.h b/libyul/optimiser/RedundantAssignEliminator.h new file mode 100644 index 00000000..76106aae --- /dev/null +++ b/libyul/optimiser/RedundantAssignEliminator.h @@ -0,0 +1,193 @@ +/* + 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 removes assignments to variables that are not used + * until they go out of scope or are re-assigned. + */ + +#pragma once + +#include <libyul/ASTDataForward.h> + +#include <libyul/optimiser/ASTWalker.h> + +#include <map> + +namespace dev +{ +namespace yul +{ + +/** + * Optimiser component that removes assignments to variables that are not used + * until they go out of scope or are re-assigned. This component + * respects the control-flow and takes it into account for removal. + * + * Example: + * + * { + * let a + * a := 1 + * a := 2 + * b := 2 + * if calldataload(0) + * { + * b := mload(a) + * } + * a := b + * } + * + * In the example, "a := 1" can be removed because the value from this assignment + * is not used in any control-flow branch (it is replaced right away). + * The assignment "a := 2" is also overwritten by "a := b" at the end, + * but there is a control-flow path (through the condition body) which uses + * the value from "a := 2" and thus, this assignment cannot be removed. + * + * Detailed rules: + * + * The AST is traversed twice: in an information gathering step and in the + * actual removal step. During information gathering, we maintain a + * mapping from assignment statements to the three states + * "unused", "undecided" and "used". + * When an assignment is visited, it is added to the mapping in the "undecided" state + * (see remark about for loops below) and every other assignment to the same variable + * that is still in the "undecided" state is changed to "unused". + * When a variable is referenced, the state of any assignment to that variable still + * in the "undecided" state is changed to "used". + * At points where control flow splits, a copy + * of the mapping is handed over to each branch. At points where control flow + * joins, the two mappings coming from the two branches are combined in the following way: + * Statements that are only in one mapping or have the same state are used unchanged. + * Conflicting values are resolved in the following way: + * "unused", "undecided" -> "undecided" + * "unused", "used" -> "used" + * "undecided, "used" -> "used". + * + * For for-loops, the condition, body and post-part are visited twice, taking + * the joining control-flow at the condition into account. + * In other words, we create three control flow paths: Zero runs of the loop, + * one run and two runs and then combine them at the end. + * Running at most twice is enough because there are only three different states. + * + * For switch statements that have a "default"-case, there is no control-flow + * part that skips the switch. + * + * When a variable goes out of scope, all statements still in the "undecided" + * state are changed to "unused", unless the variable is the return + * parameter of a function - there, the state changes to "used". + * + * In the second traversal, all assignments that are in the "unused" state are removed. + * + * + * This step is usually run right after the SSA transform to complete + * the generation of the pseudo-SSA. + * + * Prerequisite: Disambiguator. + */ +class RedundantAssignEliminator: public ASTWalker +{ +public: + RedundantAssignEliminator(RedundantAssignEliminator const&) = default; + RedundantAssignEliminator& operator=(RedundantAssignEliminator const&) = default; + RedundantAssignEliminator(RedundantAssignEliminator&&) = default; + RedundantAssignEliminator& operator=(RedundantAssignEliminator&&) = default; + + void operator()(Identifier const& _identifier) override; + void operator()(VariableDeclaration const& _variableDeclaration) override; + void operator()(Assignment const& _assignment) override; + void operator()(If const& _if) override; + void operator()(Switch const& _switch) override; + void operator()(FunctionDefinition const&) override; + void operator()(ForLoop const&) override; + void operator()(Block const& _block) override; + + static void run(Block& _ast); + +private: + RedundantAssignEliminator() {} + + class State + { + public: + enum Value { Unused, Undecided, Used }; + State(Value _value = Undecided): m_value(_value) {} + inline bool operator==(State _other) const { return m_value == _other.m_value; } + inline bool operator!=(State _other) const { return !operator==(_other); } + static inline void join(State& _a, State const& _b) + { + // Using "max" works here because of the order of the values in the enum. + _a.m_value = Value(std::max(int(_a.m_value), int(_b.m_value))); + } + private: + Value m_value = Undecided; + }; + + /** + * Takes care about storing the list of declared variables and + * sets them to "unused" when it is destroyed. + */ + class BlockScope + { + public: + explicit BlockScope(RedundantAssignEliminator& _rae): m_rae(_rae) + { + swap(m_rae.m_declaredVariables, m_outerDeclaredVariables); + } + ~BlockScope() + { + // This should actually store all declared variables + // into a different mapping + for (auto const& var: m_rae.m_declaredVariables) + m_rae.changeUndecidedTo(var, State::Unused); + for (auto const& var: m_rae.m_declaredVariables) + m_rae.finalize(var); + swap(m_rae.m_declaredVariables, m_outerDeclaredVariables); + } + + private: + RedundantAssignEliminator& m_rae; + std::set<YulString> m_outerDeclaredVariables; + }; + + /// Joins the assignment mapping with @a _other according to the rules laid out + /// above. + /// Will destroy @a _other. + void join(RedundantAssignEliminator& _other); + void changeUndecidedTo(YulString _variable, State _newState); + void finalize(YulString _variable); + + std::set<YulString> m_declaredVariables; + // TODO check that this does not cause nondeterminism! + // This could also be a pseudo-map from state to assignment. + std::map<YulString, std::map<Assignment const*, State>> m_assignments; + std::set<Assignment const*> m_assignmentsToRemove; +}; + +class AssignmentRemover: public ASTModifier +{ +public: + explicit AssignmentRemover(std::set<Assignment const*> const& _toRemove): + m_toRemove(_toRemove) + {} + void operator()(Block& _block) override; + +private: + std::set<Assignment const*> const& m_toRemove; +}; + +} +} diff --git a/libyul/optimiser/Rematerialiser.cpp b/libyul/optimiser/Rematerialiser.cpp new file mode 100644 index 00000000..38d50ef4 --- /dev/null +++ b/libyul/optimiser/Rematerialiser.cpp @@ -0,0 +1,50 @@ +/*( + 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/>. +*/ +/** + * Optimisation stage that replaces variables by their most recently assigned expressions. + */ + +#include <libyul/optimiser/Rematerialiser.h> + +#include <libyul/optimiser/Metrics.h> +#include <libyul/optimiser/ASTCopier.h> +#include <libyul/Exceptions.h> + +#include <libsolidity/inlineasm/AsmData.h> + +using namespace std; +using namespace dev; +using namespace dev::yul; + +void Rematerialiser::visit(Expression& _e) +{ + if (_e.type() == typeid(Identifier)) + { + Identifier& identifier = boost::get<Identifier>(_e); + if (m_value.count(identifier.name)) + { + YulString name = identifier.name; + for (auto const& ref: m_references[name]) + assertThrow(inScope(ref), OptimizerException, ""); + assertThrow(m_value.at(name), OptimizerException, ""); + auto const& value = *m_value.at(name); + if (CodeSize::codeSize(value) <= 7) + _e = (ASTCopier{}).translate(value); + } + } + DataFlowAnalyzer::visit(_e); +} diff --git a/libyul/optimiser/Rematerialiser.h b/libyul/optimiser/Rematerialiser.h new file mode 100644 index 00000000..f82465eb --- /dev/null +++ b/libyul/optimiser/Rematerialiser.h @@ -0,0 +1,44 @@ +/* + 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/>. +*/ +/** + * Optimisation stage that replaces variables by their most recently assigned expressions. + */ + +#pragma once + +#include <libyul/optimiser/DataFlowAnalyzer.h> + +namespace dev +{ +namespace yul +{ + +/** + * Optimisation stage that replaces variables by their most recently assigned expressions. + * + * Prerequisite: Disambiguator + */ +class Rematerialiser: public DataFlowAnalyzer +{ +protected: + using ASTModifier::visit; + virtual void visit(Expression& _e) override; + +}; + +} +} diff --git a/libyul/optimiser/SSATransform.cpp b/libyul/optimiser/SSATransform.cpp new file mode 100644 index 00000000..f209ee7b --- /dev/null +++ b/libyul/optimiser/SSATransform.cpp @@ -0,0 +1,130 @@ +/* + 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 turns subsequent assignments to variable declarations + * and assignments. + */ + +#include <libyul/optimiser/SSATransform.h> + +#include <libyul/optimiser/NameCollector.h> +#include <libyul/optimiser/NameDispenser.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libdevcore/CommonData.h> + + +using namespace std; +using namespace dev; +using namespace dev::yul; +using namespace dev::solidity; + +void SSATransform::operator()(Identifier& _identifier) +{ + if (m_currentVariableValues.count(_identifier.name)) + _identifier.name = m_currentVariableValues[_identifier.name]; +} + +void SSATransform::operator()(ForLoop& _for) +{ + // This will clear the current value in case of a reassignment inside the + // init part, although the new variable would still be in scope inside the whole loop. + // This small inefficiency is fine if we move the pre part of all for loops out + // of the for loop. + (*this)(_for.pre); + + Assignments assignments; + assignments(_for.body); + assignments(_for.post); + for (auto const& var: assignments.names()) + m_currentVariableValues.erase(var); + + visit(*_for.condition); + (*this)(_for.body); + (*this)(_for.post); +} + + +void SSATransform::operator()(Block& _block) +{ + set<YulString> variablesToClearAtEnd; + + // Creates a new variable (and returns its declaration) with value _value + // and replaces _value by a reference to that new variable. + auto replaceByNew = [&](SourceLocation _loc, YulString _varName, YulString _type, shared_ptr<Expression>& _value) -> VariableDeclaration + { + YulString newName = m_nameDispenser.newName(_varName); + m_currentVariableValues[_varName] = newName; + variablesToClearAtEnd.emplace(_varName); + shared_ptr<Expression> v = make_shared<Expression>(Identifier{_loc, newName}); + _value.swap(v); + return VariableDeclaration{_loc, {TypedName{_loc, std::move(newName), std::move(_type)}}, std::move(v)}; + }; + + iterateReplacing( + _block.statements, + [&](Statement& _s) -> boost::optional<vector<Statement>> + { + if (_s.type() == typeid(VariableDeclaration)) + { + VariableDeclaration& varDecl = boost::get<VariableDeclaration>(_s); + if (varDecl.value) + visit(*varDecl.value); + if (varDecl.variables.size() != 1 || !m_variablesToReplace.count(varDecl.variables.front().name)) + return {}; + // Replace "let a := v" by "let a_1 := v let a := v" + VariableDeclaration newVarDecl = replaceByNew( + varDecl.location, + varDecl.variables.front().name, + varDecl.variables.front().type, + varDecl.value + ); + return vector<Statement>{std::move(newVarDecl), std::move(varDecl)}; + } + else if (_s.type() == typeid(Assignment)) + { + Assignment& assignment = boost::get<Assignment>(_s); + visit(*assignment.value); + if (assignment.variableNames.size() != 1) + return {}; + assertThrow(m_variablesToReplace.count(assignment.variableNames.front().name), OptimizerException, ""); + // Replace "a := v" by "let a_1 := v a := v" + VariableDeclaration newVarDecl = replaceByNew( + assignment.location, + assignment.variableNames.front().name, + {}, // TODO determine type + assignment.value + ); + return vector<Statement>{std::move(newVarDecl), std::move(assignment)}; + } + else + visit(_s); + return {}; + } + ); + for (auto const& var: variablesToClearAtEnd) + m_currentVariableValues.erase(var); +} + +void SSATransform::run(Block& _ast, NameDispenser& _nameDispenser) +{ + Assignments assignments; + assignments(_ast); + SSATransform{_nameDispenser, assignments.names()}(_ast); +} + diff --git a/libyul/optimiser/SSATransform.h b/libyul/optimiser/SSATransform.h new file mode 100644 index 00000000..bb642549 --- /dev/null +++ b/libyul/optimiser/SSATransform.h @@ -0,0 +1,98 @@ +/* + 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 turns subsequent assignments to variable declarations + * and assignments. + */ +#pragma once + +#include <libyul/ASTDataForward.h> + +#include <libyul/optimiser/ASTWalker.h> + +#include <vector> + +namespace dev +{ +namespace yul +{ + +class NameDispenser; + +/** + * Optimizer stage that tries to replace repeated assignments to + * existing variables by declarations of new variables as much as + * possible. + * The reassignments are still there, but all references to the + * reassigned variables are replaced by the newly declared variables. + * + * Example: + * { + * let a := 1 + * mstore(a, 2) + * a := 3 + * } + * is transformed to + * { + * let a_1 := 1 + * let a := a_1 + * mstore(a_1, 2) + * let a_3 := 3 + * a := a_3 + * } + * + * Exact semantics: + * + * For any variable a that is assigned to somewhere in the code (assignment with + * declaration does not count) perform the following transforms: + * - replace "let a := v" by "let a_1 := v let a := a_1" + * - replace "a := v" by "let a_1 := v a := a_1" + * Furthermore, always note the current variable/value assigned to a and replace each + * reference to a by this variable. + * The current value mapping is cleared for a variable a at the end of each block + * in which it was assigned and just after the for loop init block if it is assigned + * inside the for loop. + * + * After this stage, redundantAssignmentRemover is recommended to remove the unnecessary + * intermediate assignments. + * + * This stage provides best results if CSE is run right before it, because + * then it does not generate excessive amounts of variables. + * + * TODO Which transforms are required to keep this idempotent? + */ +class SSATransform: public ASTModifier +{ +public: + void operator()(Identifier&) override; + void operator()(ForLoop&) override; + void operator()(Block& _block) override; + + static void run(Block& _ast, NameDispenser& _nameDispenser); + +private: + explicit SSATransform(NameDispenser& _nameDispenser, std::set<YulString> const& _variablesToReplace): + m_nameDispenser(_nameDispenser), m_variablesToReplace(_variablesToReplace) + { } + + NameDispenser& m_nameDispenser; + std::set<YulString> const& m_variablesToReplace; + std::map<YulString, YulString> m_currentVariableValues; +}; + +} +} diff --git a/libyul/optimiser/SSAValueTracker.cpp b/libyul/optimiser/SSAValueTracker.cpp new file mode 100644 index 00000000..491117da --- /dev/null +++ b/libyul/optimiser/SSAValueTracker.cpp @@ -0,0 +1,53 @@ +/* + 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/>. +*/ +/** + * Component that collects variables that are never assigned to and their + * initial values. + */ + +#include <libyul/optimiser/SSAValueTracker.h> + +#include <libsolidity/inlineasm/AsmData.h> + +using namespace std; +using namespace dev; +using namespace dev::yul; + +void SSAValueTracker::operator()(Assignment const& _assignment) +{ + for (auto const& var: _assignment.variableNames) + m_values.erase(var.name); +} + +void SSAValueTracker::operator()(VariableDeclaration const& _varDecl) +{ + if (_varDecl.variables.size() == 1) + setValue(_varDecl.variables.front().name, _varDecl.value.get()); + else + for (auto const& var: _varDecl.variables) + setValue(var.name, nullptr); +} + +void SSAValueTracker::setValue(YulString _name, Expression const* _value) +{ + assertThrow( + m_values.count(_name) == 0, + OptimizerException, + "Source needs to be disambiguated." + ); + m_values[_name] = _value; +} diff --git a/libyul/optimiser/SSAValueTracker.h b/libyul/optimiser/SSAValueTracker.h new file mode 100644 index 00000000..d1539c86 --- /dev/null +++ b/libyul/optimiser/SSAValueTracker.h @@ -0,0 +1,57 @@ +/* + 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/>. +*/ +/** + * Component that collects variables that are never assigned to and their + * initial values. + */ + +#pragma once + +#include <libyul/optimiser/ASTWalker.h> + +#include <map> +#include <set> + +namespace dev +{ +namespace yul +{ + +/** + * Class that walks the AST and stores the initial value of each variable + * that is never assigned to. + * + * Prerequisite: Disambiguator + */ +class SSAValueTracker: public ASTWalker +{ +public: + using ASTWalker::operator(); + virtual void operator()(VariableDeclaration const& _varDecl) override; + virtual void operator()(Assignment const& _assignment) override; + + std::map<YulString, Expression const*> const& values() const { return m_values; } + Expression const* value(YulString _name) const { return m_values.at(_name); } + +private: + void setValue(YulString _name, Expression const* _value); + + std::map<YulString, Expression const*> m_values; +}; + +} +} diff --git a/libyul/optimiser/Semantics.cpp b/libyul/optimiser/Semantics.cpp new file mode 100644 index 00000000..3c49016e --- /dev/null +++ b/libyul/optimiser/Semantics.cpp @@ -0,0 +1,62 @@ +/*( + 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/>. +*/ +/** + * Specific AST walkers that collect semantical facts. + */ + +#include <libyul/optimiser/Semantics.h> + +#include <libyul/Exceptions.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libevmasm/SemanticInformation.h> + +#include <libdevcore/CommonData.h> + +using namespace std; +using namespace dev; +using namespace dev::yul; + +MovableChecker::MovableChecker(Expression const& _expression) +{ + visit(_expression); +} + +void MovableChecker::operator()(Identifier const& _identifier) +{ + ASTWalker::operator()(_identifier); + m_variableReferences.emplace(_identifier.name); +} + +void MovableChecker::operator()(FunctionalInstruction const& _instr) +{ + if (!eth::SemanticInformation::movable(_instr.instruction)) + m_movable = false; + else + ASTWalker::operator()(_instr); +} + +void MovableChecker::operator()(FunctionCall const&) +{ + m_movable = false; +} + +void MovableChecker::visit(Statement const&) +{ + assertThrow(false, OptimizerException, "Movability for statement requested."); +} diff --git a/libyul/optimiser/Semantics.h b/libyul/optimiser/Semantics.h new file mode 100644 index 00000000..620a91cb --- /dev/null +++ b/libyul/optimiser/Semantics.h @@ -0,0 +1,60 @@ +/* + 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/>. +*/ +/** + * Specific AST walkers that collect semantical facts. + */ + +#pragma once + +#include <libyul/optimiser/ASTWalker.h> + +#include <set> + +namespace dev +{ +namespace yul +{ + +/** + * Specific AST walker that determines whether an expression is movable. + */ +class MovableChecker: public ASTWalker +{ +public: + MovableChecker() = default; + explicit MovableChecker(Expression const& _expression); + + virtual void operator()(Identifier const& _identifier) override; + virtual void operator()(FunctionalInstruction const& _functionalInstruction) override; + virtual void operator()(FunctionCall const& _functionCall) override; + + /// Disallow visiting anything apart from Expressions (this throws). + virtual void visit(Statement const&) override; + using ASTWalker::visit; + + bool movable() const { return m_movable; } + std::set<YulString> const& referencedVariables() const { return m_variableReferences; } + +private: + /// Which variables the current expression references. + std::set<YulString> m_variableReferences; + /// Is the current expression movable or not. + bool m_movable = true; +}; + +} +} diff --git a/libyul/optimiser/SimplificationRules.cpp b/libyul/optimiser/SimplificationRules.cpp new file mode 100644 index 00000000..5721042f --- /dev/null +++ b/libyul/optimiser/SimplificationRules.cpp @@ -0,0 +1,222 @@ +/* + 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/>. +*/ +/** + * Module for applying replacement rules against Expressions. + */ + +#include <libyul/optimiser/SimplificationRules.h> + +#include <libyul/optimiser/Utilities.h> +#include <libyul/optimiser/ASTCopier.h> +#include <libyul/optimiser/Semantics.h> +#include <libyul/optimiser/SyntacticalEquality.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libevmasm/RuleList.h> + +using namespace std; +using namespace dev; +using namespace dev::yul; + + +SimplificationRule<Pattern> const* SimplificationRules::findFirstMatch( + Expression const& _expr, + map<YulString, Expression const*> const& _ssaValues +) +{ + if (_expr.type() != typeid(FunctionalInstruction)) + return nullptr; + + static SimplificationRules rules; + assertThrow(rules.isInitialized(), OptimizerException, "Rule list not properly initialized."); + + FunctionalInstruction const& instruction = boost::get<FunctionalInstruction>(_expr); + for (auto const& rule: rules.m_rules[uint8_t(instruction.instruction)]) + { + rules.resetMatchGroups(); + if (rule.pattern.matches(_expr, _ssaValues)) + return &rule; + } + return nullptr; +} + +bool SimplificationRules::isInitialized() const +{ + return !m_rules[uint8_t(solidity::Instruction::ADD)].empty(); +} + +void SimplificationRules::addRules(vector<SimplificationRule<Pattern>> const& _rules) +{ + for (auto const& r: _rules) + addRule(r); +} + +void SimplificationRules::addRule(SimplificationRule<Pattern> const& _rule) +{ + m_rules[uint8_t(_rule.pattern.instruction())].push_back(_rule); +} + +SimplificationRules::SimplificationRules() +{ + // Multiple occurrences of one of these inside one rule must match the same equivalence class. + // Constants. + Pattern A(PatternKind::Constant); + Pattern B(PatternKind::Constant); + Pattern C(PatternKind::Constant); + // Anything. + Pattern X; + Pattern Y; + A.setMatchGroup(1, m_matchGroups); + B.setMatchGroup(2, m_matchGroups); + C.setMatchGroup(3, m_matchGroups); + X.setMatchGroup(4, m_matchGroups); + Y.setMatchGroup(5, m_matchGroups); + + addRules(simplificationRuleList(A, B, C, X, Y)); + assertThrow(isInitialized(), OptimizerException, "Rule list not properly initialized."); +} + +Pattern::Pattern(solidity::Instruction _instruction, vector<Pattern> const& _arguments): + m_kind(PatternKind::Operation), + m_instruction(_instruction), + m_arguments(_arguments) +{ +} + +void Pattern::setMatchGroup(unsigned _group, map<unsigned, Expression const*>& _matchGroups) +{ + m_matchGroup = _group; + m_matchGroups = &_matchGroups; +} + +bool Pattern::matches(Expression const& _expr, map<YulString, Expression const*> const& _ssaValues) const +{ + Expression const* expr = &_expr; + + // Resolve the variable if possible. + // Do not do it for "Any" because we can check identity better for variables. + if (m_kind != PatternKind::Any && _expr.type() == typeid(Identifier)) + { + YulString varName = boost::get<Identifier>(_expr).name; + if (_ssaValues.count(varName)) + expr = _ssaValues.at(varName); + } + assertThrow(expr, OptimizerException, ""); + + if (m_kind == PatternKind::Constant) + { + if (expr->type() != typeid(Literal)) + return false; + Literal const& literal = boost::get<Literal>(*expr); + if (literal.kind != assembly::LiteralKind::Number) + return false; + if (m_data && *m_data != u256(literal.value.str())) + return false; + assertThrow(m_arguments.empty(), OptimizerException, ""); + } + else if (m_kind == PatternKind::Operation) + { + if (expr->type() != typeid(FunctionalInstruction)) + return false; + FunctionalInstruction const& instr = boost::get<FunctionalInstruction>(*expr); + if (m_instruction != instr.instruction) + return false; + assertThrow(m_arguments.size() == instr.arguments.size(), OptimizerException, ""); + for (size_t i = 0; i < m_arguments.size(); ++i) + if (!m_arguments[i].matches(instr.arguments.at(i), _ssaValues)) + return false; + } + else + { + assertThrow(m_arguments.empty(), OptimizerException, "\"Any\" should not have arguments."); + } + + if (m_matchGroup) + { + // We support matching multiple expressions that require the same value + // based on identical ASTs, which have to be movable. + + // TODO: add tests: + // - { let x := mload(0) let y := and(x, x) } + // - { let x := 4 let y := and(x, y) } + + // This code uses `_expr` again for "Any", because we want the comparison to be done + // on the variables and not their values. + // The assumption is that CSE or local value numbering has been done prior to this step. + + if (m_matchGroups->count(m_matchGroup)) + { + assertThrow(m_kind == PatternKind::Any, OptimizerException, "Match group repetition for non-any."); + Expression const* firstMatch = (*m_matchGroups)[m_matchGroup]; + assertThrow(firstMatch, OptimizerException, "Match set but to null."); + return + SyntacticalEqualityChecker::equal(*firstMatch, _expr) && + MovableChecker(_expr).movable(); + } + else if (m_kind == PatternKind::Any) + (*m_matchGroups)[m_matchGroup] = &_expr; + else + { + assertThrow(m_kind == PatternKind::Constant, OptimizerException, "Match group set for operation."); + // We do not use _expr here, because we want the actual number. + (*m_matchGroups)[m_matchGroup] = expr; + } + } + return true; +} + +solidity::Instruction Pattern::instruction() const +{ + assertThrow(m_kind == PatternKind::Operation, OptimizerException, ""); + return m_instruction; +} + +Expression Pattern::toExpression(SourceLocation const& _location) const +{ + if (matchGroup()) + return ASTCopier().translate(matchGroupValue()); + if (m_kind == PatternKind::Constant) + { + assertThrow(m_data, OptimizerException, "No match group and no constant value given."); + return Literal{_location, assembly::LiteralKind::Number, YulString{formatNumber(*m_data)}, {}}; + } + else if (m_kind == PatternKind::Operation) + { + vector<Expression> arguments; + for (auto const& arg: m_arguments) + arguments.emplace_back(arg.toExpression(_location)); + return FunctionalInstruction{_location, m_instruction, std::move(arguments)}; + } + assertThrow(false, OptimizerException, "Pattern of kind 'any', but no match group."); +} + +u256 Pattern::d() const +{ + Literal const& literal = boost::get<Literal>(matchGroupValue()); + assertThrow(literal.kind == assembly::LiteralKind::Number, OptimizerException, ""); + assertThrow(isValidDecimal(literal.value.str()) || isValidHex(literal.value.str()), OptimizerException, ""); + return u256(literal.value.str()); +} + +Expression const& Pattern::matchGroupValue() const +{ + assertThrow(m_matchGroup > 0, OptimizerException, ""); + assertThrow(!!m_matchGroups, OptimizerException, ""); + assertThrow((*m_matchGroups)[m_matchGroup], OptimizerException, ""); + return *(*m_matchGroups)[m_matchGroup]; +} diff --git a/libyul/optimiser/SimplificationRules.h b/libyul/optimiser/SimplificationRules.h new file mode 100644 index 00000000..b608ca91 --- /dev/null +++ b/libyul/optimiser/SimplificationRules.h @@ -0,0 +1,124 @@ +/* + 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/>. +*/ +/** + * Module for applying replacement rules against Expressions. + */ + +#pragma once + +#include <libevmasm/ExpressionClasses.h> +#include <libevmasm/SimplificationRule.h> + +#include <libyul/ASTDataForward.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <boost/noncopyable.hpp> + +#include <functional> +#include <vector> + +namespace dev +{ +namespace yul +{ + +class Pattern; + +/** + * Container for all simplification rules. + */ +class SimplificationRules: public boost::noncopyable +{ +public: + SimplificationRules(); + + /// @returns a pointer to the first matching pattern and sets the match + /// groups accordingly. + /// @param _ssaValues values of variables that are assigned exactly once. + static SimplificationRule<Pattern> const* findFirstMatch( + Expression const& _expr, + std::map<YulString, Expression const*> const& _ssaValues + ); + + /// Checks whether the rulelist is non-empty. This is usually enforced + /// by the constructor, but we had some issues with static initialization. + bool isInitialized() const; +private: + void addRules(std::vector<SimplificationRule<Pattern>> const& _rules); + void addRule(SimplificationRule<Pattern> const& _rule); + + void resetMatchGroups() { m_matchGroups.clear(); } + + std::map<unsigned, Expression const*> m_matchGroups; + std::vector<SimplificationRule<Pattern>> m_rules[256]; +}; + +enum class PatternKind +{ + Operation, + Constant, + Any +}; + +/** + * Pattern to match against an expression. + * Also stores matched expressions to retrieve them later, for constructing new expressions using + * ExpressionTemplate. + */ +class Pattern +{ +public: + /// Matches any expression. + Pattern(PatternKind _kind = PatternKind::Any): m_kind(_kind) {} + // Matches a specific constant value. + Pattern(unsigned _value): Pattern(u256(_value)) {} + // Matches a specific constant value. + Pattern(u256 const& _value): m_kind(PatternKind::Constant), m_data(std::make_shared<u256>(_value)) {} + // Matches a given instruction with given arguments + Pattern(solidity::Instruction _instruction, std::vector<Pattern> const& _arguments = {}); + /// Sets this pattern to be part of the match group with the identifier @a _group. + /// Inside one rule, all patterns in the same match group have to match expressions from the + /// same expression equivalence class. + void setMatchGroup(unsigned _group, std::map<unsigned, Expression const*>& _matchGroups); + unsigned matchGroup() const { return m_matchGroup; } + bool matches(Expression const& _expr, std::map<YulString, Expression const*> const& _ssaValues) const; + + std::vector<Pattern> arguments() const { return m_arguments; } + + /// @returns the data of the matched expression if this pattern is part of a match group. + u256 d() const; + + solidity::Instruction instruction() const; + + /// Turns this pattern into an actual expression. Should only be called + /// for patterns resulting from an action, i.e. with match groups assigned. + Expression toExpression(SourceLocation const& _location) const; + +private: + Expression const& matchGroupValue() const; + + PatternKind m_kind = PatternKind::Any; + solidity::Instruction m_instruction; ///< Only valid if m_kind is Operation + std::shared_ptr<u256> m_data; ///< Only valid if m_kind is Constant + std::vector<Pattern> m_arguments; + unsigned m_matchGroup = 0; + std::map<unsigned, Expression const*>* m_matchGroups = nullptr; +}; + +} +} diff --git a/libyul/optimiser/Substitution.cpp b/libyul/optimiser/Substitution.cpp new file mode 100644 index 00000000..9b3d4c03 --- /dev/null +++ b/libyul/optimiser/Substitution.cpp @@ -0,0 +1,39 @@ +/* + 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/>. +*/ +/** + * Specific AST copier that replaces certain identifiers with expressions. + */ + +#include <libyul/optimiser/Substitution.h> + +#include <libsolidity/inlineasm/AsmData.h> + +using namespace std; +using namespace dev; +using namespace dev::yul; + +Expression Substitution::translate(Expression const& _expression) +{ + if (_expression.type() == typeid(Identifier)) + { + YulString name = boost::get<Identifier>(_expression).name; + if (m_substitutions.count(name)) + // No recursive substitution + return ASTCopier().translate(*m_substitutions.at(name)); + } + return ASTCopier::translate(_expression); +} diff --git a/libyul/optimiser/Substitution.h b/libyul/optimiser/Substitution.h new file mode 100644 index 00000000..59ee4620 --- /dev/null +++ b/libyul/optimiser/Substitution.h @@ -0,0 +1,50 @@ +/* + 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/>. +*/ +/** + * Specific AST copier that replaces certain identifiers with expressions. + */ + +#pragma once + +#include <libyul/optimiser/ASTCopier.h> + +#include <libyul/YulString.h> + +#include <map> + +namespace dev +{ +namespace yul +{ + +/** + * Specific AST copier that replaces certain identifiers with expressions. + */ +class Substitution: public ASTCopier +{ +public: + Substitution(std::map<YulString, Expression const*> const& _substitutions): + m_substitutions(_substitutions) + {} + virtual Expression translate(Expression const& _expression) override; + +private: + std::map<YulString, Expression const*> const& m_substitutions; +}; + +} +} diff --git a/libyul/optimiser/Suite.cpp b/libyul/optimiser/Suite.cpp new file mode 100644 index 00000000..7d52a5a8 --- /dev/null +++ b/libyul/optimiser/Suite.cpp @@ -0,0 +1,120 @@ +/* + 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 suite that combines all steps and also provides the settings for the heuristics. + */ + +#include <libyul/optimiser/Suite.h> + +#include <libyul/optimiser/Disambiguator.h> +#include <libyul/optimiser/FunctionGrouper.h> +#include <libyul/optimiser/FunctionHoister.h> +#include <libyul/optimiser/ExpressionSplitter.h> +#include <libyul/optimiser/ExpressionJoiner.h> +#include <libyul/optimiser/ExpressionInliner.h> +#include <libyul/optimiser/FullInliner.h> +#include <libyul/optimiser/Rematerialiser.h> +#include <libyul/optimiser/UnusedPruner.h> +#include <libyul/optimiser/ExpressionSimplifier.h> +#include <libyul/optimiser/CommonSubexpressionEliminator.h> +#include <libyul/optimiser/SSATransform.h> +#include <libyul/optimiser/RedundantAssignEliminator.h> +#include <libyul/optimiser/VarDeclPropagator.h> + +#include <libsolidity/inlineasm/AsmAnalysisInfo.h> +#include <libsolidity/inlineasm/AsmData.h> + +#include <libsolidity/inlineasm/AsmPrinter.h> + +#include <libdevcore/CommonData.h> + +using namespace std; +using namespace dev; +using namespace dev::yul; + +void OptimiserSuite::run( + Block& _ast, + solidity::assembly::AsmAnalysisInfo const& _analysisInfo, + set<YulString> const& _externallyUsedIdentifiers +) +{ + set<YulString> reservedIdentifiers = _externallyUsedIdentifiers; + + Block ast = boost::get<Block>(Disambiguator(_analysisInfo, reservedIdentifiers)(_ast)); + + (FunctionHoister{})(ast); + (FunctionGrouper{})(ast); + + NameDispenser dispenser{ast}; + + for (size_t i = 0; i < 4; i++) + { + ExpressionSplitter{dispenser}(ast); + SSATransform::run(ast, dispenser); + RedundantAssignEliminator::run(ast); + VarDeclPropagator{}(ast); + RedundantAssignEliminator::run(ast); + + CommonSubexpressionEliminator{}(ast); + ExpressionSimplifier::run(ast); + SSATransform::run(ast, dispenser); + RedundantAssignEliminator::run(ast); + RedundantAssignEliminator::run(ast); + UnusedPruner::runUntilStabilised(ast, reservedIdentifiers); + CommonSubexpressionEliminator{}(ast); + UnusedPruner::runUntilStabilised(ast, reservedIdentifiers); + SSATransform::run(ast, dispenser); + RedundantAssignEliminator::run(ast); + RedundantAssignEliminator::run(ast); + + ExpressionJoiner::run(ast); + ExpressionJoiner::run(ast); + ExpressionInliner(ast).run(); + UnusedPruner::runUntilStabilised(ast); + + ExpressionSplitter{dispenser}(ast); + SSATransform::run(ast, dispenser); + RedundantAssignEliminator::run(ast); + RedundantAssignEliminator::run(ast); + CommonSubexpressionEliminator{}(ast); + FullInliner{ast, dispenser}.run(); + VarDeclPropagator{}(ast); + SSATransform::run(ast, dispenser); + RedundantAssignEliminator::run(ast); + VarDeclPropagator{}(ast); + RedundantAssignEliminator::run(ast); + ExpressionSimplifier::run(ast); + CommonSubexpressionEliminator{}(ast); + SSATransform::run(ast, dispenser); + RedundantAssignEliminator::run(ast); + VarDeclPropagator{}(ast); + RedundantAssignEliminator::run(ast); + UnusedPruner::runUntilStabilised(ast, reservedIdentifiers); + } + ExpressionJoiner::run(ast); + VarDeclPropagator{}(ast); + UnusedPruner::runUntilStabilised(ast); + ExpressionJoiner::run(ast); + UnusedPruner::runUntilStabilised(ast); + ExpressionJoiner::run(ast); + VarDeclPropagator{}(ast); + UnusedPruner::runUntilStabilised(ast); + ExpressionJoiner::run(ast); + UnusedPruner::runUntilStabilised(ast); + + _ast = std::move(ast); +} diff --git a/libyul/optimiser/Suite.h b/libyul/optimiser/Suite.h new file mode 100644 index 00000000..5b564c56 --- /dev/null +++ b/libyul/optimiser/Suite.h @@ -0,0 +1,55 @@ +/* + 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 suite that combines all steps and also provides the settings for the heuristics. + */ + +#pragma once + +#include <libyul/ASTDataForward.h> +#include <libyul/YulString.h> + +#include <set> + +namespace dev +{ +namespace solidity +{ +namespace assembly +{ +struct AsmAnalysisInfo; +} +} +namespace yul +{ + +/** + * Optimiser suite that combines all steps and also provides the settings for the heuristics + */ +class OptimiserSuite +{ +public: + static void run( + Block& _ast, + solidity::assembly::AsmAnalysisInfo const& _analysisInfo, + + std::set<YulString> const& _externallyUsedIdentifiers = {} + ); +}; + +} +} diff --git a/libyul/optimiser/SyntacticalEquality.cpp b/libyul/optimiser/SyntacticalEquality.cpp new file mode 100644 index 00000000..66912383 --- /dev/null +++ b/libyul/optimiser/SyntacticalEquality.cpp @@ -0,0 +1,77 @@ +/*( + 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/>. +*/ +/** + * Component that can compare ASTs for equality on a syntactic basis. + */ + +#include <libyul/optimiser/SyntacticalEquality.h> + +#include <libyul/Exceptions.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libdevcore/CommonData.h> + +using namespace std; +using namespace dev; +using namespace dev::yul; + +bool SyntacticalEqualityChecker::equal(Expression const& _e1, Expression const& _e2) +{ + if (_e1.type() != _e2.type()) + return false; + // TODO This somehow calls strcmp - WHERE? + + // TODO This should be replaced by some kind of AST walker as soon as it gets + // more complex. + if (_e1.type() == typeid(FunctionalInstruction)) + { + auto const& e1 = boost::get<FunctionalInstruction>(_e1); + auto const& e2 = boost::get<FunctionalInstruction>(_e2); + return + e1.instruction == e2.instruction && + equalVector(e1.arguments, e2.arguments); + } + else if (_e1.type() == typeid(FunctionCall)) + { + auto const& e1 = boost::get<FunctionCall>(_e1); + auto const& e2 = boost::get<FunctionCall>(_e2); + return + equal(e1.functionName, e2.functionName) && + equalVector(e1.arguments, e2.arguments); + } + else if (_e1.type() == typeid(Identifier)) + return boost::get<Identifier>(_e1).name == boost::get<Identifier>(_e2).name; + else if (_e1.type() == typeid(Literal)) + { + auto const& e1 = boost::get<Literal>(_e1); + auto const& e2 = boost::get<Literal>(_e2); + return e1.kind == e2.kind && e1.value == e2.value && e1.type == e2.type; + } + else + { + assertThrow(false, OptimizerException, "Invalid expression"); + } + return false; +} + +bool SyntacticalEqualityChecker::equalVector(vector<Expression> const& _e1, vector<Expression> const& _e2) +{ + return _e1.size() == _e2.size() && + std::equal(begin(_e1), end(_e1), begin(_e2), SyntacticalEqualityChecker::equal); + +} diff --git a/libyul/optimiser/SyntacticalEquality.h b/libyul/optimiser/SyntacticalEquality.h new file mode 100644 index 00000000..e9fbebe0 --- /dev/null +++ b/libyul/optimiser/SyntacticalEquality.h @@ -0,0 +1,50 @@ +/* + 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/>. +*/ +/** + * Component that can compare ASTs for equality on a syntactic basis. + */ + +#pragma once + +#include <libyul/ASTDataForward.h> + +#include <vector> + +namespace dev +{ +namespace yul +{ + +/** + * Component that can compare ASTs for equality on a syntactic basis. + * Ignores source locations but requires exact matches otherwise. + * + * TODO: Only implemented for Expressions for now. + * A future version might also recognize renamed variables and thus could be used to + * remove duplicate functions. + */ +class SyntacticalEqualityChecker +{ +public: + static bool equal(Expression const& _e1, Expression const& _e2); + +protected: + static bool equalVector(std::vector<Expression> const& _e1, std::vector<Expression> const& _e2); +}; + +} +} diff --git a/libyul/optimiser/UnusedPruner.cpp b/libyul/optimiser/UnusedPruner.cpp new file mode 100644 index 00000000..71e86798 --- /dev/null +++ b/libyul/optimiser/UnusedPruner.cpp @@ -0,0 +1,129 @@ +/*( + 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/>. +*/ +/** + * Optimisation stage that removes unused variables and functions. + */ + +#include <libyul/optimiser/UnusedPruner.h> + +#include <libyul/optimiser/NameCollector.h> +#include <libyul/optimiser/Semantics.h> +#include <libyul/optimiser/Utilities.h> +#include <libyul/Exceptions.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <boost/algorithm/cxx11/none_of.hpp> + +using namespace std; +using namespace dev; +using namespace dev::yul; + +UnusedPruner::UnusedPruner(Block& _ast, set<YulString> const& _externallyUsedFunctions) +{ + ReferencesCounter counter; + counter(_ast); + + m_references = counter.references(); + for (auto const& f: _externallyUsedFunctions) + ++m_references[f]; +} + +void UnusedPruner::operator()(Block& _block) +{ + for (auto&& statement: _block.statements) + if (statement.type() == typeid(FunctionDefinition)) + { + FunctionDefinition& funDef = boost::get<FunctionDefinition>(statement); + if (!used(funDef.name)) + { + subtractReferences(ReferencesCounter::countReferences(funDef.body)); + statement = Block{std::move(funDef.location), {}}; + } + } + else if (statement.type() == typeid(VariableDeclaration)) + { + VariableDeclaration& varDecl = boost::get<VariableDeclaration>(statement); + // Multi-variable declarations are special. We can only remove it + // if all vairables are unused and the right-hand-side is either + // movable or it return a single value. In the latter case, we + // replace `let a := f()` by `pop(f())` (in pure Yul, this will be + // `drop(f())`). + if (boost::algorithm::none_of( + varDecl.variables, + [=](TypedName const& _typedName) { return used(_typedName.name); } + )) + { + if (!varDecl.value) + statement = Block{std::move(varDecl.location), {}}; + else if (MovableChecker(*varDecl.value).movable()) + { + subtractReferences(ReferencesCounter::countReferences(*varDecl.value)); + statement = Block{std::move(varDecl.location), {}}; + } + else if (varDecl.variables.size() == 1) + // In pure Yul, this should be replaced by a function call to `drop` + // instead of `pop`. + statement = ExpressionStatement{varDecl.location, FunctionalInstruction{ + varDecl.location, + solidity::Instruction::POP, + {*std::move(varDecl.value)} + }}; + } + } + else if (statement.type() == typeid(ExpressionStatement)) + { + ExpressionStatement& exprStmt = boost::get<ExpressionStatement>(statement); + if (MovableChecker(exprStmt.expression).movable()) + { + // pop(x) should be movable! + subtractReferences(ReferencesCounter::countReferences(exprStmt.expression)); + statement = Block{std::move(exprStmt.location), {}}; + } + } + + removeEmptyBlocks(_block); + + ASTModifier::operator()(_block); +} + +void UnusedPruner::runUntilStabilised(Block& _ast, set<YulString> const& _externallyUsedFunctions) +{ + while (true) + { + UnusedPruner pruner(_ast, _externallyUsedFunctions); + pruner(_ast); + if (!pruner.shouldRunAgain()) + return; + } +} + +bool UnusedPruner::used(YulString _name) const +{ + return m_references.count(_name) && m_references.at(_name) > 0; +} + +void UnusedPruner::subtractReferences(map<YulString, size_t> const& _subtrahend) +{ + for (auto const& ref: _subtrahend) + { + assertThrow(m_references.count(ref.first), OptimizerException, ""); + assertThrow(m_references.at(ref.first) >= ref.second, OptimizerException, ""); + m_references[ref.first] -= ref.second; + m_shouldRunAgain = true; + } +} diff --git a/libyul/optimiser/UnusedPruner.h b/libyul/optimiser/UnusedPruner.h new file mode 100644 index 00000000..b5aea3dd --- /dev/null +++ b/libyul/optimiser/UnusedPruner.h @@ -0,0 +1,65 @@ +/* + 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/>. +*/ +/** + * Optimisation stage that removes unused variables and functions. + */ + +#pragma once + +#include <libyul/optimiser/ASTWalker.h> +#include <libyul/YulString.h> + +#include <map> +#include <set> + +namespace dev +{ +namespace yul +{ + +/** + * Optimisation stage that removes unused variables and functions and also + * removes movable expression statements. + * + * Note that this does not remove circular references. + * + * Prerequisite: Disambiguator + */ +class UnusedPruner: public ASTModifier +{ +public: + explicit UnusedPruner(Block& _ast, std::set<YulString> const& _externallyUsedFunctions = {}); + + using ASTModifier::operator(); + virtual void operator()(Block& _block) override; + + // @returns true iff the code changed in the previous run. + bool shouldRunAgain() const { return m_shouldRunAgain; } + + // Run the pruner until the code does not change anymore. + static void runUntilStabilised(Block& _ast, std::set<YulString> const& _externallyUsedFunctions = {}); + +private: + bool used(YulString _name) const; + void subtractReferences(std::map<YulString, size_t> const& _subtrahend); + + bool m_shouldRunAgain = false; + std::map<YulString, size_t> m_references; +}; + +} +} diff --git a/libyul/optimiser/Utilities.cpp b/libyul/optimiser/Utilities.cpp new file mode 100644 index 00000000..df01ed39 --- /dev/null +++ b/libyul/optimiser/Utilities.cpp @@ -0,0 +1,39 @@ +/*( + 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/>. +*/ +/** + * Some useful snippets for the optimiser. + */ + +#include <libyul/optimiser/Utilities.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libdevcore/CommonData.h> + +#include <boost/range/algorithm_ext/erase.hpp> + +using namespace std; +using namespace dev; +using namespace dev::yul; + +void dev::yul::removeEmptyBlocks(Block& _block) +{ + auto isEmptyBlock = [](Statement const& _st) -> bool { + return _st.type() == typeid(Block) && boost::get<Block>(_st).statements.empty(); + }; + boost::range::remove_erase_if(_block.statements, isEmptyBlock); +} diff --git a/libyul/optimiser/Utilities.h b/libyul/optimiser/Utilities.h new file mode 100644 index 00000000..5b18a27c --- /dev/null +++ b/libyul/optimiser/Utilities.h @@ -0,0 +1,34 @@ +/* + 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/>. +*/ +/** + * Small useful snippets for the optimiser. + */ + +#pragma once + +#include <libyul/ASTDataForward.h> + +namespace dev +{ +namespace yul +{ + +/// Removes statements that are just empty blocks (non-recursive). +void removeEmptyBlocks(Block& _block); + +} +} diff --git a/libyul/optimiser/VarDeclPropagator.cpp b/libyul/optimiser/VarDeclPropagator.cpp new file mode 100644 index 00000000..537b7020 --- /dev/null +++ b/libyul/optimiser/VarDeclPropagator.cpp @@ -0,0 +1,129 @@ +/* + 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/>. +*/ + +#include <libyul/optimiser/VarDeclPropagator.h> +#include <libsolidity/inlineasm/AsmData.h> +#include <libdevcore/CommonData.h> +#include <boost/range/algorithm_ext/erase.hpp> +#include <algorithm> +#include <map> + +using namespace std; +using namespace dev; +using namespace dev::yul; + +using dev::solidity::assembly::TypedName; +using dev::solidity::assembly::TypedNameList; + +void VarDeclPropagator::operator()(Block& _block) +{ + map<YulString, TypedName> outerEmptyVarDecls; + map<YulString, TypedName> outerLazyInitializedVarDecls; + swap(m_emptyVarDecls, outerEmptyVarDecls); + swap(m_lazyInitializedVarDecls, outerLazyInitializedVarDecls); + + ASTModifier::operator()(_block); + + iterateReplacing( + _block.statements, + [this](Statement& _stmt) -> boost::optional<vector<Statement>> + { + if (_stmt.type() == typeid(VariableDeclaration)) + { + VariableDeclaration& varDecl = boost::get<VariableDeclaration>(_stmt); + boost::remove_erase_if( + varDecl.variables, + [&](TypedName const& _typedName) { return m_lazyInitializedVarDecls.count(_typedName.name); } + ); + if (varDecl.variables.empty()) + return vector<Statement>{}; + else + return {}; + } + else if (_stmt.type() == typeid(Assignment)) + { + Assignment& assignment = boost::get<Assignment>(_stmt); + if (isFullyLazyInitialized(assignment.variableNames)) + return vector<Statement>{recreateVariableDeclaration(assignment)}; + else + return {}; + } + else + return {}; + } + ); + + swap(m_emptyVarDecls, outerEmptyVarDecls); + swap(m_lazyInitializedVarDecls, outerLazyInitializedVarDecls); +} + +void VarDeclPropagator::operator()(VariableDeclaration& _varDecl) +{ + if (_varDecl.value) + visit(*_varDecl.value); + else + for (TypedName const& typedName: _varDecl.variables) + m_emptyVarDecls[typedName.name] = typedName; +} + +void VarDeclPropagator::operator()(Assignment& _assignment) +{ + visit(*_assignment.value); + + if (allVarNamesUninitialized(_assignment.variableNames)) + for (Identifier const& ident: _assignment.variableNames) + m_lazyInitializedVarDecls[ident.name] = m_emptyVarDecls[ident.name]; + + for (Identifier& name: _assignment.variableNames) + (*this)(name); +} + +void VarDeclPropagator::operator()(Identifier& _ident) +{ + m_emptyVarDecls.erase(_ident.name); +} + +bool VarDeclPropagator::allVarNamesUninitialized(vector<Identifier> const& _variableNames) const +{ + return all_of( + begin(_variableNames), + end(_variableNames), + [&](Identifier const& _ident) -> bool { return m_emptyVarDecls.count(_ident.name); } + ); +} + +bool VarDeclPropagator::isFullyLazyInitialized(vector<Identifier> const& _variableNames) const +{ + return all_of( + begin(_variableNames), + end(_variableNames), + [&](Identifier const& ident) -> bool { return m_lazyInitializedVarDecls.count(ident.name); } + ); +} + +VariableDeclaration VarDeclPropagator::recreateVariableDeclaration(Assignment& _assignment) +{ + TypedNameList variables; + + for (Identifier const& varName: _assignment.variableNames) + { + variables.emplace_back(move(m_lazyInitializedVarDecls.at(varName.name))); + m_lazyInitializedVarDecls.erase(varName.name); + } + + return VariableDeclaration{move(_assignment.location), move(variables), std::move(_assignment.value)}; +} diff --git a/libyul/optimiser/VarDeclPropagator.h b/libyul/optimiser/VarDeclPropagator.h new file mode 100644 index 00000000..4522d23a --- /dev/null +++ b/libyul/optimiser/VarDeclPropagator.h @@ -0,0 +1,63 @@ +/* + 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/>. +*/ + +#pragma once + +#include <libyul/ASTDataForward.h> +#include <libyul/optimiser/ASTWalker.h> +#include <libyul/Exceptions.h> +#include <libsolidity/inlineasm/AsmDataForward.h> +#include <vector> +#include <set> +#include <map> + +namespace dev +{ +namespace yul +{ + +/** + * Rewrites Assignment statements into VariableDeclaration when the assignment's LHS + * variables had no value yet. + * + * It recursively walks through the AST and moves each declaration of variables to + * the first assignment within the same block (if possible).. + */ +class VarDeclPropagator: public ASTModifier +{ +public: + using ASTModifier::operator(); + void operator()(Block& _block) override; + void operator()(VariableDeclaration& _varDecl) override; + void operator()(Assignment& _assignment) override; + void operator()(Identifier& _ident) override; + +private: + bool allVarNamesUninitialized(std::vector<Identifier> const& _variableNames) const; + bool isFullyLazyInitialized(std::vector<Identifier> const& _variableNames) const; + VariableDeclaration recreateVariableDeclaration(Assignment& _assignment); + +private: + /// Holds a list of variables from current Block that have no value assigned yet. + std::map<YulString, TypedName> m_emptyVarDecls; + + /// Holds a list variables (and their TypedName) within the current block. + std::map<YulString, TypedName> m_lazyInitializedVarDecls; +}; + +} +} |