Merge pull request #5247 from ethereum/yul-vardecl-propagation

Yul: Implements empty-var-decl-propagation

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
+// }