Merge pull request #5232 from ethereum/inlineHeuristic

[Yul] Add simple inlining heuristic

7 files changed, 170 insertions, 8 deletions

diff --git a/libyul/optimiser/FullInliner.cpp b/libyul/optimiser/FullInliner.cpp
index cd0ed52a..aa069506 100644
--- a/libyul/optimiser/FullInliner.cpp
+++ b/libyul/optimiser/FullInliner.cpp
@@ -24,6 +24,8 @@
 #include <libyul/optimiser/ASTWalker.h>
 #include <libyul/optimiser/NameCollector.h>
 #include <libyul/optimiser/Utilities.h>
+#include <libyul/optimiser/Metrics.h>
+#include <libyul/optimiser/SSAValueTracker.h>
 #include <libyul/Exceptions.h>
 
 #include <libsolidity/inlineasm/AsmData.h>
@@ -45,11 +47,23 @@ FullInliner::FullInliner(Block& _ast):
 	assertThrow(m_ast.statements.front().type() == typeid(Block), OptimizerException, "");
 	m_nameDispenser.m_usedNames = NameCollector(m_ast).names();
 
+	// Determine constants
+	SSAValueTracker tracker;
+	tracker(m_ast);
+	for (auto const& ssaValue: tracker.values())
+		if (ssaValue.second && ssaValue.second->type() == typeid(Literal))
+			m_constants.insert(ssaValue.first);
+
+	map<string, size_t> references = ReferencesCounter::countReferences(m_ast);
 	for (size_t i = 1; i < m_ast.statements.size(); ++i)
 	{
 		assertThrow(m_ast.statements.at(i).type() == typeid(FunctionDefinition), OptimizerException, "");
 		FunctionDefinition& fun = boost::get<FunctionDefinition>(m_ast.statements.at(i));
 		m_functions[fun.name] = &fun;
+		// Always inline functions that are only called once.
+		if (references[fun.name] == 1)
+			m_alwaysInline.insert(fun.name);
+		updateCodeSize(fun);
 	}
 }
 
@@ -58,8 +72,18 @@ void FullInliner::run()
 	assertThrow(m_ast.statements[0].type() == typeid(Block), OptimizerException, "");
 
 	handleBlock("", boost::get<Block>(m_ast.statements[0]));
+	// TODO it might be good to determine a visiting order:
+	// first handle functions that are called from many places.
 	for (auto const& fun: m_functions)
+	{
 		handleBlock(fun.second->name, fun.second->body);
+		updateCodeSize(*fun.second);
+	}
+}
+
+void FullInliner::updateCodeSize(FunctionDefinition& fun)
+{
+	m_functionSizes[fun.name] = CodeSize::codeSize(fun.body);
 }
 
 void FullInliner::handleBlock(string const& _currentFunctionName, Block& _block)
@@ -67,6 +91,33 @@ void FullInliner::handleBlock(string const& _currentFunctionName, Block& _block)
 	InlineModifier{*this, m_nameDispenser, _currentFunctionName}(_block);
 }
 
+bool FullInliner::shallInline(FunctionCall const& _funCall, string const& _callSite)
+{
+	// No recursive inlining
+	if (_funCall.functionName.name == _callSite)
+		return false;
+
+	FunctionDefinition& calledFunction = function(_funCall.functionName.name);
+	if (m_alwaysInline.count(calledFunction.name))
+		return true;
+
+	// Constant arguments might provide a means for further optimization, so they cause a bonus.
+	bool constantArg = false;
+	for (auto const& argument: _funCall.arguments)
+		if (argument.type() == typeid(Literal) || (
+			argument.type() == typeid(Identifier) &&
+			m_constants.count(boost::get<Identifier>(argument).name)
+		))
+		{
+			constantArg = true;
+			break;
+		}
+
+	size_t size = m_functionSizes.at(calledFunction.name);
+	return (size < 10 || (constantArg && size < 50));
+}
+
+
 void InlineModifier::operator()(Block& _block)
 {
 	function<boost::optional<vector<Statement>>(Statement&)> f = [&](Statement& _statement) -> boost::optional<vector<Statement>> {
@@ -90,14 +141,8 @@ boost::optional<vector<Statement>> InlineModifier::tryInlineStatement(Statement&
 		FunctionCall* funCall = boost::apply_visitor(GenericFallbackReturnsVisitor<FunctionCall*, FunctionCall&>(
 			[](FunctionCall& _e) { return &_e; }
 		), *e);
-		if (funCall)
-		{
-			// TODO: Insert good heuristic here. Perhaps implement that inside the driver.
-			bool doInline = funCall->functionName.name != m_currentFunction;
-
-			if (doInline)
-				return performInline(_statement, *funCall);
-		}
+		if (funCall && m_driver.shallInline(*funCall, m_currentFunction))
+			return performInline(_statement, *funCall);
 	}
 	return {};
 }
diff --git a/libyul/optimiser/FullInliner.h b/libyul/optimiser/FullInliner.h
index 495286c0..513ffc93 100644
--- a/libyul/optimiser/FullInliner.h
+++ b/libyul/optimiser/FullInliner.h
@@ -75,15 +75,25 @@ public:
 
 	void run();
 
+	/// Inlining heuristic.
+	/// @param _callSite the name of the function in which the function call is located.
+	bool shallInline(FunctionCall const& _funCall, std::string const& _callSite);
+
 	FunctionDefinition& function(std::string _name) { return *m_functions.at(_name); }
 
 private:
+	void updateCodeSize(FunctionDefinition& fun);
 	void handleBlock(std::string const& _currentFunctionName, Block& _block);
 
 	/// The AST to be modified. The root block itself will not be modified, because
 	/// we store pointers to functions.
 	Block& m_ast;
 	std::map<std::string, FunctionDefinition*> m_functions;
+	/// Names of functions to always inline.
+	std::set<std::string> m_alwaysInline;
+	/// Variables that are constants (used for inlining heuristic)
+	std::set<std::string> m_constants;
+	std::map<std::string, size_t> m_functionSizes;
 	NameDispenser m_nameDispenser;
 };
 
diff --git a/libyul/optimiser/Metrics.cpp b/libyul/optimiser/Metrics.cpp
index eb2d39e8..066c6b58 100644
--- a/libyul/optimiser/Metrics.cpp
+++ b/libyul/optimiser/Metrics.cpp
@@ -39,6 +39,13 @@ size_t CodeSize::codeSize(Expression const& _expression)
 	return cs.m_size;
 }
 
+size_t CodeSize::codeSize(Block const& _block)
+{
+	CodeSize cs;
+	cs(_block);
+	return cs.m_size;
+}
+
 void CodeSize::visit(Statement const& _statement)
 {
 	++m_size;
diff --git a/libyul/optimiser/Metrics.h b/libyul/optimiser/Metrics.h
index 8ed73cca..47c7ec79 100644
--- a/libyul/optimiser/Metrics.h
+++ b/libyul/optimiser/Metrics.h
@@ -36,6 +36,9 @@ public:
 	/// Returns a metric for the code size of an AST element.
 	/// More specifically, it returns the number of AST nodes.
 	static size_t codeSize(Expression const& _expression);
+	/// Returns a metric for the code size of an AST element.
+	/// More specifically, it returns the number of AST nodes.
+	static size_t codeSize(Block const& _block);
 
 private:
 	virtual void visit(Statement const& _statement) override;
diff --git a/test/libyul/yulOptimizerTests/fullInliner/large_function_multi_use.yul b/test/libyul/yulOptimizerTests/fullInliner/large_function_multi_use.yul
new file mode 100644
index 00000000..0972ac56
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/fullInliner/large_function_multi_use.yul
@@ -0,0 +1,43 @@
+{
+	function f(a) -> b {
+        let x := mload(a)
+        b := sload(x)
+        let c := 3
+        mstore(mul(a, b), mload(x))
+        let y := add(a, x)
+        sstore(y, 10)
+    }
+    let a := mload(2)
+    let a2 := 2
+    // This should not be inlined because it is not a constant
+    let r := f(a)
+    // This should be inlined because it is a constant
+    let t := f(a2)
+}
+// ----
+// fullInliner
+// {
+//     {
+//         let a_1 := mload(2)
+//         let a2 := 2
+//         let r := f(a_1)
+//         let f_a := a2
+//         let f_b
+//         let f_x := mload(f_a)
+//         f_b := sload(f_x)
+//         let f_c := 3
+//         mstore(mul(f_a, f_b), mload(f_x))
+//         let f_y := add(f_a, f_x)
+//         sstore(f_y, 10)
+//         let t := f_b
+//     }
+//     function f(a) -> b
+//     {
+//         let x := mload(a)
+//         b := sload(x)
+//         let c := 3
+//         mstore(mul(a, b), mload(x))
+//         let y := add(a, x)
+//         sstore(y, 10)
+//     }
+// }
diff --git a/test/libyul/yulOptimizerTests/fullInliner/large_function_single_use.yul b/test/libyul/yulOptimizerTests/fullInliner/large_function_single_use.yul
new file mode 100644
index 00000000..3302a35c
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/fullInliner/large_function_single_use.yul
@@ -0,0 +1,36 @@
+{
+	function f(a) -> b {
+        let x := mload(a)
+        b := sload(x)
+        let c := 3
+        mstore(mul(a, b), mload(x))
+        let y := add(a, x)
+        sstore(y, 10)
+    }
+    // Single-use functions are always inlined.
+    let r := f(mload(1))
+}
+// ----
+// fullInliner
+// {
+//     {
+//         let f_a := mload(1)
+//         let f_b
+//         let f_x := mload(f_a)
+//         f_b := sload(f_x)
+//         let f_c := 3
+//         mstore(mul(f_a, f_b), mload(f_x))
+//         let f_y := add(f_a, f_x)
+//         sstore(f_y, 10)
+//         let r := f_b
+//     }
+//     function f(a) -> b
+//     {
+//         let x := mload(a)
+//         b := sload(x)
+//         let c := 3
+//         mstore(mul(a, b), mload(x))
+//         let y := add(a, x)
+//         sstore(y, 10)
+//     }
+// }
diff --git a/test/libyul/yulOptimizerTests/fullInliner/recursion.yul b/test/libyul/yulOptimizerTests/fullInliner/recursion.yul
new file mode 100644
index 00000000..3e9a8021
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/fullInliner/recursion.yul
@@ -0,0 +1,18 @@
+{
+	function f(a) {
+		f(1)
+	}
+	f(mload(0))
+}
+// ----
+// fullInliner
+// {
+//     {
+//         let f_a := mload(0)
+//         f(1)
+//     }
+//     function f(a)
+//     {
+//         f(1)
+//     }
+// }