Yul: Implements empty-var-decl-propagation

3 files changed, 197 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;
+};
+
+}
+}