diff options
12 files changed, 302 insertions, 0 deletions
diff --git a/libyul/Exceptions.h b/libyul/Exceptions.h index c423b66f..0c421dbf 100644 --- a/libyul/Exceptions.h +++ b/libyul/Exceptions.h @@ -30,6 +30,11 @@ namespace yul struct YulException: virtual Exception {}; struct OptimizerException: virtual YulException {}; +struct YulAssertion: virtual YulException {}; + +/// Assertion that throws an YulAssertion containing the given description if it is not met. +#define yulAssert(CONDITION, DESCRIPTION) \ + assertThrow(CONDITION, ::dev::yul::YulException, DESCRIPTION) } } diff --git a/libyul/optimiser/VarDeclPropagator.cpp b/libyul/optimiser/VarDeclPropagator.cpp new file mode 100644 index 00000000..39337b3d --- /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<string, TypedName> outerEmptyVarDecls; + map<string, 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..8cba8649 --- /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<std::string, TypedName> m_emptyVarDecls; + + /// Holds a list variables (and their TypedName) within the current block. + std::map<std::string, TypedName> m_lazyInitializedVarDecls; +}; + +} +} diff --git a/test/libyul/YulOptimizerTest.cpp b/test/libyul/YulOptimizerTest.cpp index 0378764d..d455c892 100644 --- a/test/libyul/YulOptimizerTest.cpp +++ b/test/libyul/YulOptimizerTest.cpp @@ -22,6 +22,7 @@ #include <test/Options.h> #include <libyul/optimiser/BlockFlattener.h> +#include <libyul/optimiser/VarDeclPropagator.h> #include <libyul/optimiser/Disambiguator.h> #include <libyul/optimiser/CommonSubexpressionEliminator.h> #include <libyul/optimiser/NameCollector.h> @@ -102,6 +103,11 @@ bool YulOptimizerTest::run(ostream& _stream, string const& _linePrefix, bool con disambiguate(); BlockFlattener{}(*m_ast); } + else if (m_optimizerStep == "varDeclPropagator") + { + disambiguate(); + VarDeclPropagator{}(*m_ast); + } else if (m_optimizerStep == "commonSubexpressionEliminator") { disambiguate(); diff --git a/test/libyul/yulOptimizerTests/varDeclPropagator/init_assignment_inside_if.yul b/test/libyul/yulOptimizerTests/varDeclPropagator/init_assignment_inside_if.yul new file mode 100644 index 00000000..54fea2fb --- /dev/null +++ b/test/libyul/yulOptimizerTests/varDeclPropagator/init_assignment_inside_if.yul @@ -0,0 +1,17 @@ +{ + let a := 4 + let x + if a { + x := 2 + } +} +// ---- +// varDeclPropagator +// { +// let a := 4 +// let x +// if a +// { +// x := 2 +// } +// } diff --git a/test/libyul/yulOptimizerTests/varDeclPropagator/multi_assignment_vardecl.yul b/test/libyul/yulOptimizerTests/varDeclPropagator/multi_assignment_vardecl.yul new file mode 100644 index 00000000..4ac07031 --- /dev/null +++ b/test/libyul/yulOptimizerTests/varDeclPropagator/multi_assignment_vardecl.yul @@ -0,0 +1,13 @@ +{ + function f() -> a, b, c {} + let x, y, z + z, x, y := f() +} +// ---- +// varDeclPropagator +// { +// function f() -> a, b, c +// { +// } +// let z, x, y := f() +// } diff --git a/test/libyul/yulOptimizerTests/varDeclPropagator/overwrite.yul b/test/libyul/yulOptimizerTests/varDeclPropagator/overwrite.yul new file mode 100644 index 00000000..ca921500 --- /dev/null +++ b/test/libyul/yulOptimizerTests/varDeclPropagator/overwrite.yul @@ -0,0 +1,11 @@ +{ + let a + a := 4 + a := 5 +} +// ---- +// varDeclPropagator +// { +// let a := 4 +// a := 5 +// } diff --git a/test/libyul/yulOptimizerTests/varDeclPropagator/rewrite_removes_unused_var.yul b/test/libyul/yulOptimizerTests/varDeclPropagator/rewrite_removes_unused_var.yul new file mode 100644 index 00000000..3affcac6 --- /dev/null +++ b/test/libyul/yulOptimizerTests/varDeclPropagator/rewrite_removes_unused_var.yul @@ -0,0 +1,10 @@ +{ + let a, b + a := mload(0) +} +// ---- +// varDeclPropagator +// { +// let b +// let a := mload(0) +// } diff --git a/test/libyul/yulOptimizerTests/varDeclPropagator/simple1.yul b/test/libyul/yulOptimizerTests/varDeclPropagator/simple1.yul new file mode 100644 index 00000000..117e0cc9 --- /dev/null +++ b/test/libyul/yulOptimizerTests/varDeclPropagator/simple1.yul @@ -0,0 +1,9 @@ +{ + let f + f := mload(0) +} +// ---- +// varDeclPropagator +// { +// let f := mload(0) +// } diff --git a/test/libyul/yulOptimizerTests/varDeclPropagator/split_assign_splits_vardecl.yul b/test/libyul/yulOptimizerTests/varDeclPropagator/split_assign_splits_vardecl.yul new file mode 100644 index 00000000..e8c91e10 --- /dev/null +++ b/test/libyul/yulOptimizerTests/varDeclPropagator/split_assign_splits_vardecl.yul @@ -0,0 +1,11 @@ +{ + let a, b + a := mload(0) + b := mload(1) +} +// ---- +// varDeclPropagator +// { +// let a := mload(0) +// let b := mload(1) +// } diff --git a/test/libyul/yulOptimizerTests/varDeclPropagator/use_before_init.yul b/test/libyul/yulOptimizerTests/varDeclPropagator/use_before_init.yul new file mode 100644 index 00000000..5312112a --- /dev/null +++ b/test/libyul/yulOptimizerTests/varDeclPropagator/use_before_init.yul @@ -0,0 +1,12 @@ +{ + let b + let a := b + b := 1 +} +// ---- +// varDeclPropagator +// { +// let b +// let a := b +// b := 1 +// } diff --git a/test/libyul/yulOptimizerTests/varDeclPropagator/use_doesnt_rewrite.yul b/test/libyul/yulOptimizerTests/varDeclPropagator/use_doesnt_rewrite.yul new file mode 100644 index 00000000..e27785dd --- /dev/null +++ b/test/libyul/yulOptimizerTests/varDeclPropagator/use_doesnt_rewrite.yul @@ -0,0 +1,16 @@ +{ + function f(x) {} + let a + f(a) + a := 4 +} +// ---- +// varDeclPropagator +// { +// function f(x) +// { +// } +// let a +// f(a) +// a := 4 +// } |