Merge pull request #5207 from ethereum/inlineViaBreak

[Yul] Function inliner via "Expression Breaker"

2 files changed, 102 insertions, 212 deletions

diff --git a/libyul/optimiser/FullInliner.cpp b/libyul/optimiser/FullInliner.cpp
index 4e419987..cd0ed52a 100644
--- a/libyul/optimiser/FullInliner.cpp
+++ b/libyul/optimiser/FullInliner.cpp
@@ -23,12 +23,13 @@
 #include <libyul/optimiser/ASTCopier.h>
 #include <libyul/optimiser/ASTWalker.h>
 #include <libyul/optimiser/NameCollector.h>
-#include <libyul/optimiser/Semantics.h>
+#include <libyul/optimiser/Utilities.h>
 #include <libyul/Exceptions.h>
 
 #include <libsolidity/inlineasm/AsmData.h>
 
 #include <libdevcore/CommonData.h>
+#include <libdevcore/Visitor.h>
 
 #include <boost/range/adaptor/reversed.hpp>
 
@@ -49,185 +50,112 @@ FullInliner::FullInliner(Block& _ast):
 		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;
-		m_functionsToVisit.insert(&fun);
 	}
 }
 
 void FullInliner::run()
 {
 	assertThrow(m_ast.statements[0].type() == typeid(Block), OptimizerException, "");
-	InlineModifier(*this, m_nameDispenser, "").visit(m_ast.statements[0]);
-	while (!m_functionsToVisit.empty())
-		handleFunction(**m_functionsToVisit.begin());
-}
-
-void FullInliner::handleFunction(FunctionDefinition& _fun)
-{
-	if (!m_functionsToVisit.count(&_fun))
-		return;
-	m_functionsToVisit.erase(&_fun);
-	(InlineModifier(*this, m_nameDispenser, _fun.name))(_fun.body);
-}
 
-void InlineModifier::operator()(FunctionalInstruction& _instruction)
-{
-	visitArguments(_instruction.arguments);
+	handleBlock("", boost::get<Block>(m_ast.statements[0]));
+	for (auto const& fun: m_functions)
+		handleBlock(fun.second->name, fun.second->body);
 }
 
-void InlineModifier::operator()(FunctionCall&)
+void FullInliner::handleBlock(string const& _currentFunctionName, Block& _block)
 {
-	assertThrow(false, OptimizerException, "Should be handled in visit() instead.");
-}
-
-void InlineModifier::operator()(ForLoop& _loop)
-{
-	(*this)(_loop.pre);
-	// Do not visit the condition because we cannot inline there.
-	(*this)(_loop.post);
-	(*this)(_loop.body);
+	InlineModifier{*this, m_nameDispenser, _currentFunctionName}(_block);
 }
 
 void InlineModifier::operator()(Block& _block)
 {
-	vector<Statement> saved;
-	saved.swap(m_statementsToPrefix);
-
-	// This is only used if needed to minimize the number of move operations.
-	vector<Statement> modifiedStatements;
-	for (size_t i = 0; i < _block.statements.size(); ++i)
-	{
-		visit(_block.statements.at(i));
-		if (!m_statementsToPrefix.empty())
-		{
-			if (modifiedStatements.empty())
-				std::move(
-					_block.statements.begin(),
-					_block.statements.begin() + i,
-					back_inserter(modifiedStatements)
-				);
-			modifiedStatements += std::move(m_statementsToPrefix);
-			m_statementsToPrefix.clear();
-		}
-		if (!modifiedStatements.empty())
-			modifiedStatements.emplace_back(std::move(_block.statements[i]));
-	}
-	if (!modifiedStatements.empty())
-		_block.statements = std::move(modifiedStatements);
-
-	saved.swap(m_statementsToPrefix);
+	function<boost::optional<vector<Statement>>(Statement&)> f = [&](Statement& _statement) -> boost::optional<vector<Statement>> {
+		visit(_statement);
+		return tryInlineStatement(_statement);
+	};
+	iterateReplacing(_block.statements, f);
 }
 
-void InlineModifier::visit(Expression& _expression)
+boost::optional<vector<Statement>> InlineModifier::tryInlineStatement(Statement& _statement)
 {
-	if (_expression.type() != typeid(FunctionCall))
-		return ASTModifier::visit(_expression);
-
-	FunctionCall& funCall = boost::get<FunctionCall>(_expression);
-	FunctionDefinition& fun = m_driver.function(funCall.functionName.name);
-
-	m_driver.handleFunction(fun);
-
-	// TODO: Insert good heuristic here. Perhaps implement that inside the driver.
-	bool doInline = funCall.functionName.name != m_currentFunction;
-
-	if (fun.returnVariables.size() > 1)
-		doInline = false;
-
+	// Only inline for expression statements, assignments and variable declarations.
+	Expression* e = boost::apply_visitor(GenericFallbackReturnsVisitor<Expression*, ExpressionStatement, Assignment, VariableDeclaration>(
+		[](ExpressionStatement& _s) { return &_s.expression; },
+		[](Assignment& _s) { return _s.value.get(); },
+		[](VariableDeclaration& _s) { return _s.value.get(); }
+	), _statement);
+	if (e)
 	{
-		vector<string> argNames;
-		vector<string> argTypes;
-		for (auto const& arg: fun.parameters)
+		// Only inline direct function calls.
+		FunctionCall* funCall = boost::apply_visitor(GenericFallbackReturnsVisitor<FunctionCall*, FunctionCall&>(
+			[](FunctionCall& _e) { return &_e; }
+		), *e);
+		if (funCall)
 		{
-			argNames.push_back(fun.name + "_" + arg.name);
-			argTypes.push_back(arg.type);
-		}
-		visitArguments(funCall.arguments, argNames, argTypes, doInline);
-	}
-
-	if (!doInline)
-		return;
+			// TODO: Insert good heuristic here. Perhaps implement that inside the driver.
+			bool doInline = funCall->functionName.name != m_currentFunction;
 
-	map<string, string> variableReplacements;
-	for (size_t i = 0; i < funCall.arguments.size(); ++i)
-		variableReplacements[fun.parameters[i].name] = boost::get<Identifier>(funCall.arguments[i]).name;
-	if (fun.returnVariables.empty())
-		_expression = noop(funCall.location);
-	else
-	{
-		string returnVariable = fun.returnVariables[0].name;
-		variableReplacements[returnVariable] = newName(fun.name + "_" + returnVariable);
-
-		m_statementsToPrefix.emplace_back(VariableDeclaration{
-			funCall.location,
-			{{funCall.location, variableReplacements[returnVariable], fun.returnVariables[0].type}},
-			{}
-		});
-		_expression = Identifier{funCall.location, variableReplacements[returnVariable]};
-	}
-	m_statementsToPrefix.emplace_back(BodyCopier(m_nameDispenser, fun.name + "_", variableReplacements)(fun.body));
-}
-
-void InlineModifier::visit(Statement& _statement)
-{
-	ASTModifier::visit(_statement);
-	// Replace pop(0) expression statemets (and others) by empty blocks.
-	if (_statement.type() == typeid(ExpressionStatement))
-	{
-		ExpressionStatement& expSt = boost::get<ExpressionStatement>(_statement);
-		if (expSt.expression.type() == typeid(FunctionalInstruction))
-		{
-			FunctionalInstruction& funInstr = boost::get<FunctionalInstruction>(expSt.expression);
-			if (funInstr.instruction == solidity::Instruction::POP)
-				if (MovableChecker(funInstr.arguments.at(0)).movable())
-					_statement = Block{expSt.location, {}};
+			if (doInline)
+				return performInline(_statement, *funCall);
 		}
 	}
+	return {};
 }
 
-void InlineModifier::visitArguments(
-	vector<Expression>& _arguments,
-	vector<string> const& _nameHints,
-	vector<string> const& _types,
-	bool _moveToFront
-)
+vector<Statement> InlineModifier::performInline(Statement& _statement, FunctionCall& _funCall)
 {
-	// If one of the elements moves parts to the front, all other elements right of it
-	// also have to be moved to the front to keep the order of evaluation.
-	vector<Statement> prefix;
-	for (size_t i = 0; i < _arguments.size(); ++i)
-	{
-		auto& arg = _arguments[i];
-		// TODO optimize vector operations, check that it actually moves
-		auto internalPrefix = visitRecursively(arg);
-		if (!internalPrefix.empty())
+	vector<Statement> newStatements;
+	map<string, string> variableReplacements;
+
+	FunctionDefinition& function = m_driver.function(_funCall.functionName.name);
+
+	// helper function to create a new variable that is supposed to model
+	// an existing variable.
+	auto newVariable = [&](TypedName const& _existingVariable, Expression* _value) {
+		string newName = m_nameDispenser.newName(function.name + "_" + _existingVariable.name);
+		variableReplacements[_existingVariable.name] = newName;
+		VariableDeclaration varDecl{_funCall.location, {{_funCall.location, newName, _existingVariable.type}}, {}};
+		if (_value)
+			varDecl.value = make_shared<Expression>(std::move(*_value));
+		newStatements.emplace_back(std::move(varDecl));
+	};
+
+	for (size_t i = 0; i < _funCall.arguments.size(); ++i)
+		newVariable(function.parameters[i], &_funCall.arguments[i]);
+	for (auto const& var: function.returnVariables)
+		newVariable(var, nullptr);
+
+	Statement newBody = BodyCopier(m_nameDispenser, function.name + "_", variableReplacements)(function.body);
+	newStatements += std::move(boost::get<Block>(newBody).statements);
+
+	boost::apply_visitor(GenericFallbackVisitor<Assignment, VariableDeclaration>{
+		[&](Assignment& _assignment)
 		{
-			_moveToFront = true;
-			// We go through the arguments left to right, so we have to invert
-			// the prefixes.
-			prefix = std::move(internalPrefix) + std::move(prefix);
-		}
-		else if (_moveToFront)
+			for (size_t i = 0; i < _assignment.variableNames.size(); ++i)
+				newStatements.emplace_back(Assignment{
+					_assignment.location,
+					{_assignment.variableNames[i]},
+					make_shared<Expression>(Identifier{
+						_assignment.location,
+						variableReplacements.at(function.returnVariables[i].name)
+					})
+				});
+		},
+		[&](VariableDeclaration& _varDecl)
 		{
-			auto location = locationOf(arg);
-			string var = newName(i < _nameHints.size() ? _nameHints[i] : "");
-			prefix.emplace(prefix.begin(), VariableDeclaration{
-				location,
-				{{TypedName{location, var, i < _types.size() ? _types[i] : ""}}},
-				make_shared<Expression>(std::move(arg))
-			});
-			arg = Identifier{location, var};
+			for (size_t i = 0; i < _varDecl.variables.size(); ++i)
+				newStatements.emplace_back(VariableDeclaration{
+					_varDecl.location,
+					{std::move(_varDecl.variables[i])},
+					make_shared<Expression>(Identifier{
+						_varDecl.location,
+						variableReplacements.at(function.returnVariables[i].name)
+					})
+				});
 		}
-	}
-	m_statementsToPrefix += std::move(prefix);
-}
-
-vector<Statement> InlineModifier::visitRecursively(Expression& _expression)
-{
-	vector<Statement> saved;
-	saved.swap(m_statementsToPrefix);
-	visit(_expression);
-	saved.swap(m_statementsToPrefix);
-	return saved;
+		// nothing to be done for expression statement
+	}, _statement);
+	return newStatements;
 }
 
 string InlineModifier::newName(string const& _prefix)
@@ -235,13 +163,6 @@ string InlineModifier::newName(string const& _prefix)
 	return m_nameDispenser.newName(_prefix);
 }
 
-Expression InlineModifier::noop(SourceLocation const& _location)
-{
-	return FunctionalInstruction{_location, solidity::Instruction::POP, {
-		Literal{_location, assembly::LiteralKind::Number, "0", ""}
-	}};
-}
-
 Statement BodyCopier::operator()(VariableDeclaration const& _varDecl)
 {
 	for (auto const& var: _varDecl.variables)
diff --git a/libyul/optimiser/FullInliner.h b/libyul/optimiser/FullInliner.h
index 8112fb4b..495286c0 100644
--- a/libyul/optimiser/FullInliner.h
+++ b/libyul/optimiser/FullInliner.h
@@ -42,29 +42,31 @@ class NameCollector;
 
 
 /**
- * Optimiser component that modifies an AST in place, inlining arbitrary functions.
+ * Optimiser component that modifies an AST in place, inlining functions.
+ * Expressions are expected to be split, i.e. the component will only inline
+ * function calls that are at the root of the expression and that only contains
+ * variables as arguments. More specifically, it will inline
+ *  - let x1, ..., xn := f(a1, ..., am)
+ *  - x1, ..., xn := f(a1, ..., am)
+ * f(a1, ..., am)
  *
- * Code of the form
+ * The transform changes code of the form
  *
  * function f(a, b) -> c { ... }
- * h(g(x(...), f(arg1(...), arg2(...)), y(...)), z(...))
+ * let z := f(x, y)
  *
- * is transformed into
+ * into
  *
  * function f(a, b) -> c { ... }
  *
- * let z1 := z(...) let y1 := y(...) let a2 := arg2(...) let a1 := arg1(...)
- * let c1 := 0
- * { code of f, with replacements: a -> a1, b -> a2, c -> c1, d -> d1 }
- * h(g(x(...), c1, y1), z1)
+ * let f_a := x
+ * let f_b := y
+ * let f_c
+ * code of f, with replacements: a -> f_a, b -> f_b, c -> f_c
+ * let z := f_c
  *
- * No temporary variable is created for expressions that are "movable"
- * (i.e. they are "pure", have no side-effects and also do not depend on other code
- * that might have side-effects).
- *
- * This component can only be used on sources with unique names and with hoisted functions,
- * i.e. the root node has to be a block that itself contains a single block followed by all
- * function definitions.
+ * Prerequisites: Disambiguator, Function Hoister
+ * More efficient if run after: Expression Splitter
  */
 class FullInliner: public ASTModifier
 {
@@ -73,17 +75,15 @@ public:
 
 	void run();
 
-	/// Perform inlining operations inside the given function.
-	void handleFunction(FunctionDefinition& _function);
-
 	FunctionDefinition& function(std::string _name) { return *m_functions.at(_name); }
 
 private:
+	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;
-	std::set<FunctionDefinition*> m_functionsToVisit;
 	NameDispenser m_nameDispenser;
 };
 
@@ -99,46 +99,15 @@ public:
 		m_driver(_driver),
 		m_nameDispenser(_nameDispenser)
 	{ }
-	~InlineModifier()
-	{
-		assertThrow(m_statementsToPrefix.empty(), OptimizerException, "");
-	}
-
-	virtual void operator()(FunctionalInstruction&) override;
-	virtual void operator()(FunctionCall&) override;
-	virtual void operator()(ForLoop&) override;
-	virtual void operator()(Block& _block) override;
 
-	using ASTModifier::visit;
-	virtual void visit(Expression& _expression) override;
-	virtual void visit(Statement& _st) override;
+	virtual void operator()(Block& _block) override;
 
 private:
-
-	/// Visits a list of expressions (usually an argument list to a function call) and tries
-	/// to inline them. If one of them is inlined, all right of it have to be moved to the front
-	/// (to keep the order of evaluation). If @a _moveToFront is true, all elements are moved
-	/// to the front. @a _nameHints and @_types are used for the newly created variables, but
-	/// both can be empty.
-	void visitArguments(
-		std::vector<Expression>& _arguments,
-		std::vector<std::string> const& _nameHints = {},
-		std::vector<std::string> const& _types = {},
-		bool _moveToFront = false
-	);
-
-	/// Visits an expression, but saves and restores the current statements to prefix and returns
-	/// the statements that should be prefixed for @a _expression.
-	std::vector<Statement> visitRecursively(Expression& _expression);
+	boost::optional<std::vector<Statement>> tryInlineStatement(Statement& _statement);
+	std::vector<Statement> performInline(Statement& _statement, FunctionCall& _funCall);
 
 	std::string newName(std::string const& _prefix);
 
-	/// @returns an expression returning nothing.
-	Expression noop(SourceLocation const& _location);
-
-	/// List of statements that should go in front of the currently visited AST element,
-	/// at the statement level.
-	std::vector<Statement> m_statementsToPrefix;
 	std::string m_currentFunction;
 	FullInliner& m_driver;
 	NameDispenser& m_nameDispenser;