Refactor data flow analysis out of remat.

4 files changed, 284 insertions, 177 deletions

diff --git a/libjulia/optimiser/DataFlowAnalyzer.cpp b/libjulia/optimiser/DataFlowAnalyzer.cpp
new file mode 100644
index 00000000..389f8715
--- /dev/null
+++ b/libjulia/optimiser/DataFlowAnalyzer.cpp
@@ -0,0 +1,195 @@
+/*(
+	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().first += 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.push_back(make_pair(set<string>(), true));
+	for (auto const& parameter: _fun.parameters)
+		m_variableScopes.back().first.insert(parameter.name);
+	for (auto const& var: _fun.returnVariables)
+		m_variableScopes.back().first.insert(var.name);
+	ASTModifier::operator()(_fun);
+	m_variableScopes.pop_back();
+}
+
+void DataFlowAnalyzer::operator()(ForLoop& _for)
+{
+	// Special scope handling of the pre block.
+	m_variableScopes.push_back(make_pair(set<string>(), 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.push_back(make_pair(set<string>(), 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.
+		// TODO: Add a test for that
+		if (_value && movableChecker.movable() && !movableChecker.referencedVariables().count(name))
+			// TODO If _value is null, we could use zero.
+			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.first.count(_variableName))
+			return true;
+		if (scope.second)
+			return false;
+	}
+	return false;
+}
diff --git a/libjulia/optimiser/DataFlowAnalyzer.h b/libjulia/optimiser/DataFlowAnalyzer.h
new file mode 100644
index 00000000..16d6e72b
--- /dev/null
+++ b/libjulia/optimiser/DataFlowAnalyzer.h
@@ -0,0 +1,78 @@
+/*
+	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;
+	/// List of scopes, where each scope is a set of variables and a bool that tells
+	/// whether it is a function body (true) or not.
+	std::vector<std::pair<std::set<std::string>, bool>> m_variableScopes;
+};
+
+}
+}
diff --git a/libjulia/optimiser/Rematerialiser.cpp b/libjulia/optimiser/Rematerialiser.cpp
index bf7d7d16..eaa75e33 100644
--- a/libjulia/optimiser/Rematerialiser.cpp
+++ b/libjulia/optimiser/Rematerialiser.cpp
@@ -20,176 +20,35 @@
 
 #include <libjulia/optimiser/Rematerialiser.h>
 
+#include <libjulia/optimiser/Metrics.h>
 #include <libjulia/optimiser/ASTCopier.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 Rematerialiser::operator()(Assignment& _assignment)
-{
-	set<string> names;
-	for (auto const& var: _assignment.variableNames)
-		names.insert(var.name);
-	handleAssignment(names, _assignment.value.get());
-}
-
-void Rematerialiser::operator()(VariableDeclaration& _varDecl)
-{
-	set<string> names;
-	for (auto const& var: _varDecl.variables)
-		names.insert(var.name);
-	m_variableScopes.back().first += names;
-	handleAssignment(names, _varDecl.value.get());
-}
-
-void Rematerialiser::operator()(If& _if)
-{
-	ASTModifier::operator()(_if);
-
-	Assignments ass;
-	ass(_if.body);
-	handleAssignment(ass.names(), nullptr);
-}
-
-void Rematerialiser::operator()(Switch& _switch)
-{
-	boost::apply_visitor(*this, *_switch.expression);
-	set<string> assignedVariables;
-	for (auto& _case: _switch.cases)
-	{
-		(*this)(_case.body);
-		Assignments ass;
-		ass(_case.body);
-		assignedVariables += ass.names();
-		// This is a little too destructive, we could retain the old replacements.
-		handleAssignment(ass.names(), nullptr);
-	}
-	handleAssignment(assignedVariables, nullptr);
-}
-
-void Rematerialiser::operator()(FunctionDefinition& _fun)
-{
-	m_variableScopes.push_back(make_pair(set<string>(), true));
-	for (auto const& parameter: _fun.parameters)
-		m_variableScopes.back().first.insert(parameter.name);
-	for (auto const& var: _fun.returnVariables)
-		m_variableScopes.back().first.insert(var.name);
-	ASTModifier::operator()(_fun);
-	m_variableScopes.pop_back();
-}
-
-void Rematerialiser::operator()(ForLoop& _for)
-{
-	// Special scope handling of the pre block.
-	m_variableScopes.push_back(make_pair(set<string>(), false));
-	for (auto& statement: _for.pre.statements)
-		visit(statement);
-
-	Assignments ass;
-	ass(_for.body);
-	ass(_for.post);
-	handleAssignment(ass.names(), nullptr);
-
-	visit(*_for.condition);
-	(*this)(_for.body);
-	(*this)(_for.post);
-
-	handleAssignment(ass.names(), nullptr);
-
-	m_variableScopes.pop_back();
-}
-
-void Rematerialiser::operator()(Block& _block)
-{
-	size_t numScopes = m_variableScopes.size();
-	m_variableScopes.push_back(make_pair(set<string>(), false));
-	ASTModifier::operator()(_block);
-	m_variableScopes.pop_back();
-	solAssert(numScopes == m_variableScopes.size(), "");
-}
-
-void Rematerialiser::handleAssignment(set<string> const& _variables, Expression* _value)
-{
-	MovableChecker movableChecker;
-	if (_value)
-	{
-		visit(*_value);
-		movableChecker.visit(*_value);
-	}
-	if (_variables.size() == 1)
-	{
-		string const& name = *_variables.begin();
-		if (movableChecker.movable() && _value)
-			// TODO Plus heuristic about size of value
-			// TODO If _value is null, we could use zero.
-			m_substitutions[name] = _value;
-		else
-			m_substitutions.erase(name);
-	}
-	else
-		for (auto const& name: _variables)
-			m_substitutions.erase(name);
-
-	// Disallow substitutions that use a variable that will be reassigned by this assignment.
-	for (auto const& name: _variables)
-		for (auto const& ref: m_referencedBy[name])
-			m_substitutions.erase(ref);
-	// Update the fact which variables are referenced by the newly assigned variables
-	for (auto const& name: _variables)
-	{
-		for (auto const& ref: m_references[name])
-			m_referencedBy[ref].erase(name);
-		m_references[name].clear();
-	}
-	auto const& referencedVariables = movableChecker.referencedVariables();
-	for (auto const& name: _variables)
-	{
-		m_references[name] = referencedVariables;
-		for (auto const& ref: referencedVariables)
-			m_referencedBy[ref].insert(name);
-	}
-}
-
-bool Rematerialiser::inScope(string const& _variableName) const
-{
-	for (auto const& scope: m_variableScopes | boost::adaptors::reversed)
-	{
-		if (scope.first.count(_variableName))
-			return true;
-		if (scope.second)
-			return false;
-	}
-	return false;
-}
-
 void Rematerialiser::visit(Expression& _e)
 {
 	if (_e.type() == typeid(Identifier))
 	{
 		Identifier& identifier = boost::get<Identifier>(_e);
-		if (m_substitutions.count(identifier.name))
+		if (m_value.count(identifier.name))
 		{
 			string name = identifier.name;
-			bool doSubstitute = true;
+			bool expressionValid = true;
 			for (auto const& ref: m_references[name])
 				if (!inScope(ref))
 				{
-					doSubstitute = false;
+					expressionValid = false;
 					break;
 				}
-			if (doSubstitute)
-				_e = (ASTCopier{}).translate(*m_substitutions.at(name));
+			solAssert(m_value.at(name), "");
+			auto const& value = *m_value.at(name);
+			if (expressionValid && CodeSize::codeSize(value) <= 7)
+				_e = (ASTCopier{}).translate(value);
 		}
 	}
-	ASTModifier::visit(_e);
+	DataFlowAnalyzer::visit(_e);
 }
diff --git a/libjulia/optimiser/Rematerialiser.h b/libjulia/optimiser/Rematerialiser.h
index 1accc3f6..60dbfada 100644
--- a/libjulia/optimiser/Rematerialiser.h
+++ b/libjulia/optimiser/Rematerialiser.h
@@ -20,7 +20,7 @@
 
 #pragma once
 
-#include <libjulia/optimiser/ASTWalker.h>
+#include <libjulia/optimiser/DataFlowAnalyzer.h>
 
 #include <string>
 #include <map>
@@ -36,37 +36,12 @@ namespace julia
  *
  * Prerequisite: Disambiguator
  */
-class Rematerialiser: public ASTModifier
+class Rematerialiser: public DataFlowAnalyzer
 {
-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:
 	using ASTModifier::visit;
 	virtual void visit(Expression& _e) override;
 
-private:
-	void handleAssignment(std::set<std::string> const& _names, Expression* _value);
-
-	/// Returns true iff the variable is in scope.
-	bool inScope(std::string const& _variableName) const;
-
-	/// Substitutions to be performed, if possible.
-	std::map<std::string, Expression const*> m_substitutions;
-	/// 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;
-	/// List of scopes, where each scope is a set of variables and a bool that tells
-	/// whether it is a function body (true) or not.
-	std::vector<std::pair<std::set<std::string>, bool>> m_variableScopes;
 };
 
 }