aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--libyul/Exceptions.h5
-rw-r--r--libyul/optimiser/VarDeclPropagator.cpp129
-rw-r--r--libyul/optimiser/VarDeclPropagator.h63
-rw-r--r--test/libyul/YulOptimizerTest.cpp6
-rw-r--r--test/libyul/yulOptimizerTests/varDeclPropagator/init_assignment_inside_if.yul17
-rw-r--r--test/libyul/yulOptimizerTests/varDeclPropagator/multi_assignment_vardecl.yul13
-rw-r--r--test/libyul/yulOptimizerTests/varDeclPropagator/overwrite.yul11
-rw-r--r--test/libyul/yulOptimizerTests/varDeclPropagator/rewrite_removes_unused_var.yul10
-rw-r--r--test/libyul/yulOptimizerTests/varDeclPropagator/simple1.yul9
-rw-r--r--test/libyul/yulOptimizerTests/varDeclPropagator/split_assign_splits_vardecl.yul11
-rw-r--r--test/libyul/yulOptimizerTests/varDeclPropagator/use_before_init.yul12
-rw-r--r--test/libyul/yulOptimizerTests/varDeclPropagator/use_doesnt_rewrite.yul16
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
+// }