Merge pull request #3236 from ethereum/inliner

Expression Inliner

5 files changed, 488 insertions, 0 deletions

diff --git a/libjulia/optimiser/ExpressionInliner.cpp b/libjulia/optimiser/ExpressionInliner.cpp
new file mode 100644
index 00000000..450769fd
--- /dev/null
+++ b/libjulia/optimiser/ExpressionInliner.cpp
@@ -0,0 +1,74 @@
+/*
+	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/>.
+*/
+/**
+ * Optimiser component that performs function inlining inside expressions.
+ */
+
+#include <libjulia/optimiser/ExpressionInliner.h>
+
+#include <libjulia/optimiser/InlinableExpressionFunctionFinder.h>
+#include <libjulia/optimiser/Substitution.h>
+#include <libjulia/optimiser/Semantics.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+#include <boost/algorithm/cxx11/all_of.hpp>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+using namespace dev::solidity;
+
+void ExpressionInliner::run()
+{
+	InlinableExpressionFunctionFinder funFinder;
+	funFinder(m_block);
+	m_inlinableFunctions = funFinder.inlinableFunctions();
+
+	(*this)(m_block);
+}
+
+
+void ExpressionInliner::operator()(FunctionDefinition& _fun)
+{
+	ASTModifier::operator()(_fun);
+}
+
+void ExpressionInliner::visit(Expression& _expression)
+{
+	ASTModifier::visit(_expression);
+	if (_expression.type() == typeid(FunctionCall))
+	{
+		FunctionCall& funCall = boost::get<FunctionCall>(_expression);
+
+		bool movable = boost::algorithm::all_of(
+			funCall.arguments,
+			[=](Expression const& _arg) { return MovableChecker(_arg).movable(); }
+		);
+		if (m_inlinableFunctions.count(funCall.functionName.name) && movable)
+		{
+			FunctionDefinition const& fun = *m_inlinableFunctions.at(funCall.functionName.name);
+			map<string, Expression const*> substitutions;
+			for (size_t i = 0; i < fun.parameters.size(); ++i)
+				substitutions[fun.parameters[i].name] = &funCall.arguments[i];
+			_expression = Substitution(substitutions).translate(*boost::get<Assignment>(fun.body.statements.front()).value);
+
+			// TODO Add metric! This metric should perform well on a pair of functions who
+			// call each other recursively.
+		}
+	}
+}
diff --git a/libjulia/optimiser/ExpressionInliner.h b/libjulia/optimiser/ExpressionInliner.h
new file mode 100644
index 00000000..10d7659c
--- /dev/null
+++ b/libjulia/optimiser/ExpressionInliner.h
@@ -0,0 +1,74 @@
+/*
+	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/>.
+*/
+/**
+ * Optimiser component that performs function inlining.
+ */
+#pragma once
+
+#include <libjulia/optimiser/ASTWalker.h>
+
+#include <libjulia/ASTDataForward.h>
+
+#include <libsolidity/interface/Exceptions.h>
+
+#include <boost/variant.hpp>
+#include <boost/optional.hpp>
+
+#include <set>
+
+namespace dev
+{
+namespace julia
+{
+
+/**
+ * Optimiser component that modifies an AST in place, inlining functions that can be
+ * inlined inside functional expressions, i.e. functions that
+ *  - return a single value
+ *  - have a body like r := <functional expression>
+ *  - neither reference themselves nor r in the right hand side
+ *
+ * Furthermore, the arguments of the function call cannot have any side-effects.
+ *
+ * This component can only be used on sources with unique names.
+ */
+class ExpressionInliner: public ASTModifier
+{
+public:
+	ExpressionInliner(Block& _block):
+		m_block(_block)
+	{}
+
+	void run();
+
+	using ASTModifier::operator();
+	virtual void operator()(FunctionDefinition& _fun) override;
+
+	virtual void visit(Expression& _expression) override;
+
+private:
+	std::map<std::string, FunctionDefinition const*> m_inlinableFunctions;
+	std::map<std::string, std::string> m_varReplacements;
+	/// Set of functions we are currently visiting inside.
+	std::set<std::string> m_currentFunctions;
+
+	Block& m_block;
+};
+
+
+}
+}
diff --git a/libjulia/optimiser/InlinableExpressionFunctionFinder.cpp b/libjulia/optimiser/InlinableExpressionFunctionFinder.cpp
new file mode 100644
index 00000000..2097e091
--- /dev/null
+++ b/libjulia/optimiser/InlinableExpressionFunctionFinder.cpp
@@ -0,0 +1,70 @@
+/*
+	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/>.
+*/
+/**
+ * Optimiser component that identifies functions to be inlined.
+ */
+
+#include <libjulia/optimiser/InlinableExpressionFunctionFinder.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+#include <libsolidity/interface/Exceptions.h>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+
+void InlinableExpressionFunctionFinder::operator()(Identifier const& _identifier)
+{
+	checkAllowed(_identifier.name);
+	ASTWalker::operator()(_identifier);
+}
+
+void InlinableExpressionFunctionFinder::operator()(FunctionCall const& _funCall)
+{
+	checkAllowed(_funCall.functionName.name);
+	ASTWalker::operator()(_funCall);
+}
+
+void InlinableExpressionFunctionFinder::operator()(FunctionDefinition const& _function)
+{
+	if (_function.returnVariables.size() == 1 && _function.body.statements.size() == 1)
+	{
+		string const& retVariable = _function.returnVariables.front().name;
+		Statement const& bodyStatement = _function.body.statements.front();
+		if (bodyStatement.type() == typeid(Assignment))
+		{
+			Assignment const& assignment = boost::get<Assignment>(bodyStatement);
+			if (assignment.variableNames.size() == 1 && assignment.variableNames.front().name == retVariable)
+			{
+				// FIXME: use code size metric here
+
+				// We cannot overwrite previous settings, because this function definition
+				// would not be valid here if we were searching inside a functionally inlinable
+				// function body.
+				solAssert(m_disallowedIdentifiers.empty() && !m_foundDisallowedIdentifier, "");
+				m_disallowedIdentifiers = set<string>{retVariable, _function.name};
+				boost::apply_visitor(*this, *assignment.value);
+				if (!m_foundDisallowedIdentifier)
+					m_inlinableFunctions[_function.name] = &_function;
+				m_disallowedIdentifiers.clear();
+				m_foundDisallowedIdentifier = false;
+			}
+		}
+	}
+	ASTWalker::operator()(_function.body);
+}
diff --git a/libjulia/optimiser/InlinableExpressionFunctionFinder.h b/libjulia/optimiser/InlinableExpressionFunctionFinder.h
new file mode 100644
index 00000000..36cb557a
--- /dev/null
+++ b/libjulia/optimiser/InlinableExpressionFunctionFinder.h
@@ -0,0 +1,71 @@
+/*
+	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/>.
+*/
+/**
+ * Optimiser component that identifies functions to be inlined.
+ */
+
+#pragma once
+
+#include <libjulia/ASTDataForward.h>
+#include <libjulia/optimiser/ASTWalker.h>
+
+#include <libsolidity/interface/Exceptions.h>
+
+#include <set>
+
+namespace dev
+{
+namespace julia
+{
+
+/**
+ * Optimiser component that finds functions that can be
+ * inlined inside functional expressions, i.e. functions that
+ *  - have a single return parameter r
+ *  - have a body like r := <functional expression>
+ *  - neither reference themselves nor r in the right hand side
+ *
+ * This component can only be used on sources with unique names.
+ */
+class InlinableExpressionFunctionFinder: public ASTWalker
+{
+public:
+
+	std::map<std::string, FunctionDefinition const*> const& inlinableFunctions() const
+	{
+		return m_inlinableFunctions;
+	}
+
+	using ASTWalker::operator();
+	virtual void operator()(Identifier const& _identifier) override;
+	virtual void operator()(FunctionCall const& _funCall) override;
+	virtual void operator()(FunctionDefinition const& _function) override;
+
+private:
+	void checkAllowed(std::string const& _name)
+	{
+		if (m_disallowedIdentifiers.count(_name))
+			m_foundDisallowedIdentifier = true;
+	}
+
+	bool m_foundDisallowedIdentifier = false;
+	std::set<std::string> m_disallowedIdentifiers;
+	std::map<std::string, FunctionDefinition const*> m_inlinableFunctions;
+};
+
+}
+}
diff --git a/test/libjulia/Inliner.cpp b/test/libjulia/Inliner.cpp
new file mode 100644
index 00000000..88b51f28
--- /dev/null
+++ b/test/libjulia/Inliner.cpp
@@ -0,0 +1,199 @@
+/*
+    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 iulia function inliner.
+ */
+
+#include <test/libjulia/Common.h>
+
+#include <libjulia/optimiser/ExpressionInliner.h>
+#include <libjulia/optimiser/InlinableExpressionFunctionFinder.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;
+
+namespace
+{
+string inlinableFunctions(string const& _source)
+{
+	auto ast = disambiguate(_source);
+
+	InlinableExpressionFunctionFinder funFinder;
+	funFinder(ast);
+
+	return boost::algorithm::join(
+		funFinder.inlinableFunctions() | boost::adaptors::map_keys,
+		","
+	);
+}
+
+string inlineFunctions(string const& _source, bool _julia = true)
+{
+	auto ast = disambiguate(_source, _julia);
+	ExpressionInliner(ast).run();
+	return assembly::AsmPrinter(_julia)(ast);
+}
+}
+
+BOOST_AUTO_TEST_SUITE(IuliaInlinableFunctionFilter)
+
+BOOST_AUTO_TEST_CASE(smoke_test)
+{
+	BOOST_CHECK_EQUAL(inlinableFunctions("{ }"), "");
+}
+
+BOOST_AUTO_TEST_CASE(simple)
+{
+	BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256 { x := 2:u256 } }"), "f");
+	BOOST_CHECK_EQUAL(inlinableFunctions("{"
+		"function g(a:u256) -> b:u256 { b := a }"
+		"function f() -> x:u256 { x := g(2:u256) }"
+	"}"), "f,g");
+}
+
+BOOST_AUTO_TEST_CASE(simple_inside_structures)
+{
+	BOOST_CHECK_EQUAL(inlinableFunctions("{"
+		"switch 2:u256 "
+		"case 2:u256 {"
+			"function g(a:u256) -> b:u256 { b := a }"
+			"function f() -> x:u256 { x := g(2:u256) }"
+		"}"
+	"}"), "f,g");
+	BOOST_CHECK_EQUAL(inlinableFunctions("{"
+		"for {"
+			"function g(a:u256) -> b:u256 { b := a }"
+		"} 1:u256 {"
+			"function f() -> x:u256 { x := g(2:u256) }"
+		"}"
+		"{"
+			"function h() -> y:u256 { y := 2:u256 }"
+		"}"
+	"}"), "f,g,h");
+}
+
+BOOST_AUTO_TEST_CASE(negative)
+{
+	BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256 { } }"), "");
+	BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256 { x := 2:u256 {} } }"), "");
+	BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256 { x := f() } }"), "");
+	BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256 { x := x } }"), "");
+	BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256, y:u256 { x := 2:u256 } }"), "");
+}
+
+
+BOOST_AUTO_TEST_SUITE_END()
+
+BOOST_AUTO_TEST_SUITE(IuliaFunctionInliner)
+
+BOOST_AUTO_TEST_CASE(simple)
+{
+	BOOST_CHECK_EQUAL(
+		inlineFunctions("{ function f() -> x:u256 { x := 2:u256 } let y:u256 := f() }"),
+		format("{ function f() -> x:u256 { x := 2:u256 } let y:u256 := 2:u256 }")
+	);
+}
+
+BOOST_AUTO_TEST_CASE(with_args)
+{
+	BOOST_CHECK_EQUAL(
+		inlineFunctions("{ function f(a:u256) -> x:u256 { x := a } let y:u256 := f(7:u256) }"),
+		format("{ function f(a:u256) -> x:u256 { x := a } let y:u256 := 7:u256 }")
+	);
+}
+
+BOOST_AUTO_TEST_CASE(no_inline_with_mload)
+{
+	// Does not inline because mload could be moved out of sequence
+	BOOST_CHECK_EQUAL(
+		inlineFunctions("{ function f(a) -> x { x := a } let y := f(mload(2)) }", false),
+		format("{ function f(a) -> x { x := a } let y := f(mload(2)) }", false)
+	);
+}
+
+BOOST_AUTO_TEST_CASE(no_move_with_side_effects)
+{
+	// The calls to g and h cannot be moved because g and h are not movable. Therefore, the call
+	// to f is not inlined.
+	BOOST_CHECK_EQUAL(
+		inlineFunctions("{"
+			"function f(a, b) -> x { x := add(b, a) }"
+			"function g() -> y { y := mload(0) mstore(0, 4) }"
+			"function h() -> z { mstore(0, 4) z := mload(0) }"
+			"let r := f(g(), h())"
+		"}", false),
+		format("{"
+			"function f(a, b) -> x { x := add(b, a) }"
+			"function g() -> y { y := mload(0) mstore(0, 4) }"
+			"function h() -> z { mstore(0, 4) z := mload(0) }"
+			"let r := f(g(), h())"
+		"}", false)
+	);
+}
+
+BOOST_AUTO_TEST_CASE(complex_with_evm)
+{
+	BOOST_CHECK_EQUAL(
+		inlineFunctions("{ function f(a) -> x { x := add(a, a) } let y := f(calldatasize()) }", false),
+		format("{ function f(a) -> x { x := add(a, a) } let y := add(calldatasize(), calldatasize()) }", false)
+	);
+}
+
+BOOST_AUTO_TEST_CASE(double_calls)
+{
+	BOOST_CHECK_EQUAL(
+		inlineFunctions("{"
+			"function f(a) -> x { x := add(a, a) }"
+			"function g(b, c) -> y { y := mul(mload(c), f(b)) }"
+			"let y := g(calldatasize(), 7)"
+		"}", false),
+		format("{"
+			"function f(a) -> x { x := add(a, a) }"
+			"function g(b, c) -> y { y := mul(mload(c), add(b, b)) }"
+			"let y_1 := mul(mload(7), add(calldatasize(), calldatasize()))"
+		"}", false)
+	);
+}
+
+BOOST_AUTO_TEST_CASE(double_recursive_calls)
+{
+	BOOST_CHECK_EQUAL(
+		inlineFunctions("{"
+			"function f(a, r) -> x { x := g(a, g(r, r)) }"
+			"function g(b, s) -> y { y := f(b, f(s, s)) }"
+			"let y := g(calldatasize(), 7)"
+		"}", false),
+		format("{"
+			"function f(a, r) -> x { x := g(a, f(r, f(r, r))) }"
+			"function g(b, s) -> y { y := f(b, g(s, f(s, f(s, s))))}"
+			"let y_1 := f(calldatasize(), g(7, f(7, f(7, 7))))"
+		"}", false)
+	);
+}
+
+BOOST_AUTO_TEST_SUITE_END()