Merge pull request #3332 from ethereum/elimination_descirption

Rematerialisation step.

9 files changed, 600 insertions, 3 deletions

diff --git a/libjulia/optimiser/ASTWalker.cpp b/libjulia/optimiser/ASTWalker.cpp
index 6386b29d..03444984 100644
--- a/libjulia/optimiser/ASTWalker.cpp
+++ b/libjulia/optimiser/ASTWalker.cpp
@@ -86,8 +86,8 @@ void ASTWalker::operator()(ForLoop const& _for)
 {
 	(*this)(_for.pre);
 	visit(*_for.condition);
-	(*this)(_for.post);
 	(*this)(_for.body);
+	(*this)(_for.post);
 }
 
 void ASTWalker::operator()(Block const& _block)
diff --git a/libjulia/optimiser/DataFlowAnalyzer.cpp b/libjulia/optimiser/DataFlowAnalyzer.cpp
new file mode 100644
index 00000000..56653393
--- /dev/null
+++ b/libjulia/optimiser/DataFlowAnalyzer.cpp
@@ -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/>.
+*/
+/**
+ * Base class to perform data flaw analysis during AST walks.
+ * Tracks assignments and is used as base class for both Rematerialiser and
+ * Common Subexpression Eliminator.
+ */
+
+#include <libjulia/optimiser/DataFlowAnalyzer.h>
+
+#include <libjulia/optimiser/NameCollector.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+#include <libjulia/optimiser/Semantics.h>
+
+#include <libdevcore/CommonData.h>
+
+#include <boost/range/adaptor/reversed.hpp>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+
+void DataFlowAnalyzer::operator()(Assignment& _assignment)
+{
+	set<string> names;
+	for (auto const& var: _assignment.variableNames)
+		names.insert(var.name);
+	solAssert(_assignment.value, "");
+	visit(*_assignment.value);
+	handleAssignment(names, _assignment.value.get());
+}
+
+void DataFlowAnalyzer::operator()(VariableDeclaration& _varDecl)
+{
+	set<string> names;
+	for (auto const& var: _varDecl.variables)
+		names.insert(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<string> 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)
+{
+	m_variableScopes.emplace_back(true);
+	for (auto const& parameter: _fun.parameters)
+		m_variableScopes.back().variables.insert(parameter.name);
+	for (auto const& var: _fun.returnVariables)
+		m_variableScopes.back().variables.insert(var.name);
+	ASTModifier::operator()(_fun);
+	m_variableScopes.pop_back();
+}
+
+void DataFlowAnalyzer::operator()(ForLoop& _for)
+{
+	// Special scope handling of the pre block.
+	m_variableScopes.emplace_back(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());
+
+	m_variableScopes.pop_back();
+}
+
+void DataFlowAnalyzer::operator()(Block& _block)
+{
+	size_t numScopes = m_variableScopes.size();
+	m_variableScopes.emplace_back(false);
+	ASTModifier::operator()(_block);
+	m_variableScopes.pop_back();
+	solAssert(numScopes == m_variableScopes.size(), "");
+}
+
+void DataFlowAnalyzer::handleAssignment(set<string> const& _variables, Expression* _value)
+{
+	clearValues(_variables);
+
+	MovableChecker movableChecker;
+	if (_value)
+		movableChecker.visit(*_value);
+	if (_variables.size() == 1)
+	{
+		string const& 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].insert(name);
+	}
+}
+
+void DataFlowAnalyzer::clearValues(set<string> const& _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)
+
+	set<string> variables = _variables;
+	// Clear variables that reference variables to be cleared.
+	for (auto const& name: variables)
+		for (auto const& ref: m_referencedBy[name])
+			variables.insert(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(string const& _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/libjulia/optimiser/DataFlowAnalyzer.h b/libjulia/optimiser/DataFlowAnalyzer.h
new file mode 100644
index 00000000..4cb3d4cd
--- /dev/null
+++ b/libjulia/optimiser/DataFlowAnalyzer.h
@@ -0,0 +1,84 @@
+/*
+	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 <libjulia/optimiser/ASTWalker.h>
+
+#include <string>
+#include <map>
+#include <set>
+
+namespace dev
+{
+namespace julia
+{
+
+/**
+ * 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<std::string> const& _names, Expression* _value);
+
+	/// Clears information about the valuse assigned to the given variables,
+	/// for example at points where control flow is merged.
+	void clearValues(std::set<std::string> const& _names);
+
+	/// Returns true iff the variable is in scope.
+	bool inScope(std::string const& _variableName) const;
+
+	/// Current values of variables, always movable.
+	std::map<std::string, Expression const*> m_value;
+	/// m_references[a].contains(b) <=> the current expression assigned to a references b
+	std::map<std::string, std::set<std::string>> m_references;
+	/// m_referencedBy[b].contains(a) <=> the current expression assigned to a references b
+	std::map<std::string, std::set<std::string>> m_referencedBy;
+
+	struct Scope
+	{
+		explicit Scope(bool _isFunction): isFunction(_isFunction) {}
+		std::set<std::string> variables;
+		bool isFunction;
+	};
+	/// List of scopes.
+	std::vector<Scope> m_variableScopes;
+};
+
+}
+}
diff --git a/libjulia/optimiser/NameCollector.cpp b/libjulia/optimiser/NameCollector.cpp
index f94104b7..510ee289 100644
--- a/libjulia/optimiser/NameCollector.cpp
+++ b/libjulia/optimiser/NameCollector.cpp
@@ -67,3 +67,9 @@ map<string, size_t> ReferencesCounter::countReferences(Expression const& _expres
 	counter.visit(_expression);
 	return counter.references();
 }
+
+void Assignments::operator()(Assignment const& _assignment)
+{
+	for (auto const& var: _assignment.variableNames)
+		m_names.insert(var.name);
+}
diff --git a/libjulia/optimiser/NameCollector.h b/libjulia/optimiser/NameCollector.h
index 7fe386f7..2d4a1d4b 100644
--- a/libjulia/optimiser/NameCollector.h
+++ b/libjulia/optimiser/NameCollector.h
@@ -66,5 +66,19 @@ private:
 	std::map<std::string, 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<std::string> const& names() const { return m_names; }
+private:
+	std::set<std::string> m_names;
+};
+
 }
 }
diff --git a/libjulia/optimiser/README.md b/libjulia/optimiser/README.md
index 771cb707..24ee429c 100644
--- a/libjulia/optimiser/README.md
+++ b/libjulia/optimiser/README.md
@@ -54,8 +54,27 @@ As an example, neither ``mload`` nor ``mstore`` would be allowed.
 
 ## Full Function Inliner
 
-## Variable Eliminator
+## 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.
 
-## Unused Declaration Pruner
 
 ## Function Unifier
diff --git a/libjulia/optimiser/Rematerialiser.cpp b/libjulia/optimiser/Rematerialiser.cpp
new file mode 100644
index 00000000..eaa75e33
--- /dev/null
+++ b/libjulia/optimiser/Rematerialiser.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/>.
+*/
+/**
+ * Optimisation stage that replaces variables by their most recently assigned expressions.
+ */
+
+#include <libjulia/optimiser/Rematerialiser.h>
+
+#include <libjulia/optimiser/Metrics.h>
+#include <libjulia/optimiser/ASTCopier.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+
+void Rematerialiser::visit(Expression& _e)
+{
+	if (_e.type() == typeid(Identifier))
+	{
+		Identifier& identifier = boost::get<Identifier>(_e);
+		if (m_value.count(identifier.name))
+		{
+			string name = identifier.name;
+			bool expressionValid = true;
+			for (auto const& ref: m_references[name])
+				if (!inScope(ref))
+				{
+					expressionValid = false;
+					break;
+				}
+			solAssert(m_value.at(name), "");
+			auto const& value = *m_value.at(name);
+			if (expressionValid && CodeSize::codeSize(value) <= 7)
+				_e = (ASTCopier{}).translate(value);
+		}
+	}
+	DataFlowAnalyzer::visit(_e);
+}
diff --git a/libjulia/optimiser/Rematerialiser.h b/libjulia/optimiser/Rematerialiser.h
new file mode 100644
index 00000000..60dbfada
--- /dev/null
+++ b/libjulia/optimiser/Rematerialiser.h
@@ -0,0 +1,48 @@
+/*
+	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 <libjulia/optimiser/DataFlowAnalyzer.h>
+
+#include <string>
+#include <map>
+#include <set>
+
+namespace dev
+{
+namespace julia
+{
+
+/**
+ * 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/test/libjulia/Rematerialiser.cpp b/test/libjulia/Rematerialiser.cpp
new file mode 100644
index 00000000..8f928f8e
--- /dev/null
+++ b/test/libjulia/Rematerialiser.cpp
@@ -0,0 +1,179 @@
+/*
+    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/>.
+*/
+/**
+ * @date 2017
+ * Unit tests for the rematerialiser optimizer stage.
+ */
+
+#include <test/libjulia/Common.h>
+
+#include <libjulia/optimiser/Rematerialiser.h>
+
+#include <libsolidity/inlineasm/AsmPrinter.h>
+
+#include <boost/test/unit_test.hpp>
+
+#include <boost/range/adaptors.hpp>
+#include <boost/algorithm/string/join.hpp>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+using namespace dev::julia::test;
+using namespace dev::solidity;
+
+
+#define CHECK(_original, _expectation)\
+do\
+{\
+	assembly::AsmPrinter p;\
+	Block b = disambiguate(_original, false);\
+	(Rematerialiser{})(b);\
+	string result = p(b);\
+	BOOST_CHECK_EQUAL(result, format(_expectation, false));\
+}\
+while(false)
+
+BOOST_AUTO_TEST_SUITE(IuliaRematerialiser)
+
+BOOST_AUTO_TEST_CASE(smoke_test)
+{
+	CHECK("{ }", "{ }");
+}
+
+BOOST_AUTO_TEST_CASE(trivial)
+{
+	CHECK(
+		"{ let a := 1 let b := a mstore(0, b) }",
+		"{ let a := 1 let b := 1 mstore(0, 1) }"
+	);
+}
+
+BOOST_AUTO_TEST_CASE(expression)
+{
+	CHECK(
+		"{ let a := add(mul(calldatasize(), 2), number()) let b := add(a, a) }",
+		"{ let a := add(mul(calldatasize(), 2), number()) let b := add("
+			"add(mul(calldatasize(), 2), number()),"
+			"add(mul(calldatasize(), 2), number())"
+		") }"
+	);
+}
+
+BOOST_AUTO_TEST_CASE(reassign)
+{
+	CHECK(
+		"{ let a := extcodesize(0) let b := a let c := b a := 2 let d := add(b, c) pop(a) pop(b) pop(c) pop(d) }",
+		"{ let a := extcodesize(0) let b := a let c := a a := 2 let d := add(b, c) pop(2) pop(b) pop(c) pop(add(b, c)) }"
+	);
+}
+
+BOOST_AUTO_TEST_CASE(non_movable_instr)
+{
+	CHECK(
+		"{ let a := 1 let b := mload(a) let c := a mstore(add(a, b), c) }",
+		"{ let a := 1 let b := mload(1) let c := 1 mstore(add(1, b), 1) }"
+	);
+}
+
+BOOST_AUTO_TEST_CASE(non_movable_fun)
+{
+	CHECK(
+		"{ function f(x) -> y {} let a := 1 let b := f(a) let c := a mstore(add(a, b), c) }",
+		"{ function f(x) -> y {} let a := 1 let b := f(1) let c := 1 mstore(add(1, b), 1) }"
+	);
+}
+
+BOOST_AUTO_TEST_CASE(branches_if)
+{
+	CHECK(
+		"{ let a := 1 let b := 2 if b { pop(b) b := a } let c := b }",
+		"{ let a := 1 let b := 2 if 2 { pop(2) b := 1 } let c := b }"
+	);
+}
+
+BOOST_AUTO_TEST_CASE(branches_switch)
+{
+	CHECK(
+		"{ let a := 1 let b := 2 switch number() case 1 { b := a } default { let x := a let y := b b := a } pop(add(a, b)) }",
+		"{ let a := 1 let b := 2 switch number() case 1 { b := 1 } default { let x := 1 let y := b b := 1 } pop(add(1, b)) }"
+	);
+}
+
+BOOST_AUTO_TEST_CASE(branches_for)
+{
+	CHECK(
+		"{ let a := 1 for { pop(a) } a { pop(a) } { pop(a) } }",
+		"{ let a := 1 for { pop(1) } 1 { pop(1) } { pop(1) } }"
+	);
+	CHECK(
+		"{ let a := 1 for { pop(a) } a { pop(a) } { a := 7 let c := a } let x := a }",
+		"{ let a := 1 for { pop(1) } a { pop(7) } { a := 7 let c := 7 } let x := a }"
+	);
+}
+
+BOOST_AUTO_TEST_CASE(branches_for_declared_in_init)
+{
+	CHECK(
+		"{ let b := 0 for { let a := 1 pop(a) } a { pop(a) } { b := 1 pop(a) } }",
+		"{ let b := 0 for { let a := 1 pop(1) } 1 { pop(1) } { b := 1 pop(1) } }"
+	);
+	CHECK(
+		"{ let b := 0 for { let a := 1 pop(a) } lt(a, 0) { pop(a) a := add(a, 3) } { b := 1 pop(a) } }",
+		"{ let b := 0 for { let a := 1 pop(1) } lt(a, 0) { pop(a) a := add(a, 3) } { b := 1 pop(a) } }"
+	);
+}
+
+BOOST_AUTO_TEST_CASE(reassignment)
+{
+	CHECK(
+		"{ let a := 1 pop(a) if a { a := 2 } let b := mload(a) pop(b) }",
+		"{ let a := 1 pop(1) if 1 { a := 2 } let b := mload(a) pop(b) }"
+	);
+}
+
+BOOST_AUTO_TEST_CASE(update_assignment_remat)
+{
+	// We cannot substitute `a` in `let b := a`
+	CHECK(
+		"{ let a := extcodesize(0) a := mul(a, 2) let b := a }",
+		"{ let a := extcodesize(0) a := mul(a, 2) let b := a }"
+	);
+}
+
+BOOST_AUTO_TEST_CASE(do_not_move_out_of_scope)
+{
+	// Cannot replace by `let b := x` by `let b := a` since a is out of scope.
+	CHECK(
+		"{ let x { let a := sload(0) x := a } let b := x }",
+		"{ let x { let a := sload(0) x := a } let b := x }"
+	);
+}
+
+BOOST_AUTO_TEST_CASE(do_not_remat_large_amounts_of_code)
+{
+	CHECK(
+		"{ let x := add(mul(calldataload(2), calldataload(4)), mul(2, calldatasize())) let b := x }",
+		"{ let x := add(mul(calldataload(2), calldataload(4)), mul(2, calldatasize())) let b := x }"
+	);
+	CHECK(
+		"{ let x := add(mul(calldataload(2), calldataload(4)), calldatasize()) let b := x }",
+		"{ let x := add(mul(calldataload(2), calldataload(4)), calldatasize()) let b := add(mul(calldataload(2), calldataload(4)), calldatasize()) }"
+	);
+}
+
+BOOST_AUTO_TEST_SUITE_END()