Use rematerializer if variable is unreferenced or value is "cheap".

5 files changed, 124 insertions, 4 deletions

diff --git a/libyul/optimiser/Metrics.cpp b/libyul/optimiser/Metrics.cpp
index 8fc9476e..a351f1d1 100644
--- a/libyul/optimiser/Metrics.cpp
+++ b/libyul/optimiser/Metrics.cpp
@@ -21,6 +21,9 @@
 #include <libyul/optimiser/Metrics.h>
 
 #include <libyul/AsmData.h>
+#include <libyul/Exceptions.h>
+
+#include <libevmasm/Instruction.h>
 
 using namespace dev;
 using namespace yul;
@@ -60,3 +63,64 @@ void CodeSize::visit(Expression const& _expression)
 	++m_size;
 	ASTWalker::visit(_expression);
 }
+
+
+size_t CodeCost::codeCost(Expression const& _expr)
+{
+	CodeCost cc;
+	cc.visit(_expr);
+	return cc.m_cost;
+}
+
+
+void CodeCost::operator()(FunctionCall const& _funCall)
+{
+	yulAssert(m_cost >= 1, "Should assign cost one in visit(Expression).");
+	m_cost += 49;
+	ASTWalker::operator()(_funCall);
+}
+
+void CodeCost::operator()(FunctionalInstruction const& _instr)
+{
+	using namespace dev::solidity;
+	yulAssert(m_cost >= 1, "Should assign cost one in visit(Expression).");
+	Tier gasPriceTier = instructionInfo(_instr.instruction).gasPriceTier;
+	if (gasPriceTier < Tier::VeryLow)
+		m_cost -= 1;
+	else if (gasPriceTier < Tier::High)
+		m_cost += 1;
+	else
+		m_cost += 49;
+	ASTWalker::operator()(_instr);
+}
+void CodeCost::operator()(Literal const& _literal)
+{
+	yulAssert(m_cost >= 1, "Should assign cost one in visit(Expression).");
+	size_t cost = 0;
+	switch (_literal.kind)
+	{
+	case LiteralKind::Boolean:
+		break;
+	case LiteralKind::Number:
+		for (u256 n = u256(_literal.value.str()); n >= 0x100; n >>= 8)
+			cost++;
+		break;
+	case LiteralKind::String:
+		cost = _literal.value.str().size();
+		break;
+	}
+
+	m_cost += cost;
+}
+
+void CodeCost::visit(Statement const& _statement)
+{
+	++m_cost;
+	ASTWalker::visit(_statement);
+}
+
+void CodeCost::visit(Expression const& _expression)
+{
+	++m_cost;
+	ASTWalker::visit(_expression);
+}
diff --git a/libyul/optimiser/Metrics.h b/libyul/optimiser/Metrics.h
index d26ecbd9..d8a1b279 100644
--- a/libyul/optimiser/Metrics.h
+++ b/libyul/optimiser/Metrics.h
@@ -46,4 +46,26 @@ private:
 	size_t m_size = 0;
 };
 
+/**
+ * Very rough cost that takes the size and execution cost of code into account.
+ * The cost per AST element is one, except for literals where it is the byte size.
+ * Function calls cost 50. Instructions cost 0 for 3 or less gas (same as DUP),
+ * 2 for up to 10 and 50 otherwise.
+ */
+class CodeCost: public ASTWalker
+{
+public:
+	static size_t codeCost(Expression const& _expression);
+
+private:
+	void operator()(FunctionCall const& _funCall) override;
+	void operator()(FunctionalInstruction const& _instr) override;
+	void operator()(Literal const& _literal) override;
+	void visit(Statement const& _statement) override;
+	void visit(Expression const& _expression) override;
+
+private:
+	size_t m_cost = 0;
+};
+
 }
diff --git a/libyul/optimiser/Rematerialiser.cpp b/libyul/optimiser/Rematerialiser.cpp
index 4180bfc3..247defda 100644
--- a/libyul/optimiser/Rematerialiser.cpp
+++ b/libyul/optimiser/Rematerialiser.cpp
@@ -22,6 +22,7 @@
 
 #include <libyul/optimiser/Metrics.h>
 #include <libyul/optimiser/ASTCopier.h>
+#include <libyul/optimiser/NameCollector.h>
 #include <libyul/Exceptions.h>
 #include <libyul/AsmData.h>
 
@@ -29,6 +30,16 @@ using namespace std;
 using namespace dev;
 using namespace yul;
 
+void Rematerialiser::run(Block& _ast)
+{
+	Rematerialiser{_ast}(_ast);
+}
+
+Rematerialiser::Rematerialiser(Block& _ast):
+	m_referenceCounts(ReferencesCounter::countReferences(_ast))
+{
+}
+
 void Rematerialiser::visit(Expression& _e)
 {
 	if (_e.type() == typeid(Identifier))
@@ -37,12 +48,21 @@ void Rematerialiser::visit(Expression& _e)
 		if (m_value.count(identifier.name))
 		{
 			YulString name = identifier.name;
-			for (auto const& ref: m_references[name])
-				assertThrow(inScope(ref), OptimizerException, "");
 			assertThrow(m_value.at(name), OptimizerException, "");
 			auto const& value = *m_value.at(name);
-			if (CodeSize::codeSize(value) <= 7)
+			size_t refs = m_referenceCounts[name];
+			size_t cost = CodeCost::codeCost(value);
+			if (refs <= 1 || cost == 0 || (refs <= 5 && cost <= 1))
+			{
+				assertThrow(m_referenceCounts[name] > 0, OptimizerException, "");
+				for (auto const& ref: m_references[name])
+					assertThrow(inScope(ref), OptimizerException, "");
+				// update reference counts
+				m_referenceCounts[name]--;
+				for (auto const& ref: ReferencesCounter::countReferences(value))
+					m_referenceCounts[ref.first] += ref.second;
 				_e = (ASTCopier{}).translate(value);
+			}
 		}
 	}
 	DataFlowAnalyzer::visit(_e);
diff --git a/libyul/optimiser/Rematerialiser.h b/libyul/optimiser/Rematerialiser.h
index b3841519..c34353de 100644
--- a/libyul/optimiser/Rematerialiser.h
+++ b/libyul/optimiser/Rematerialiser.h
@@ -26,16 +26,27 @@ namespace yul
 {
 
 /**
- * Optimisation stage that replaces variables by their most recently assigned expressions.
+ * Optimisation stage that replaces variables by their most recently assigned expressions,
+ * but only if the expression is movable and one of the following holds:
+ *  - the variable is referenced exactly once
+ *  - the value is extremely cheap ("cost" of zero like ``caller()``)
+ *  - the variable is referenced at most 5 times and the value is rather cheap
+ *    ("cost" of at most 1 like a constant up to 0xff)
  *
  * Prerequisite: Disambiguator
  */
 class Rematerialiser: public DataFlowAnalyzer
 {
+public:
+	static void run(Block& _ast);
+
 protected:
+	Rematerialiser(Block& _ast);
+
 	using ASTModifier::visit;
 	void visit(Expression& _e) override;
 
+	std::map<YulString, size_t> m_referenceCounts;
 };
 
 }
diff --git a/libyul/optimiser/Suite.cpp b/libyul/optimiser/Suite.cpp
index bfba8dfc..c0fd15a2 100644
--- a/libyul/optimiser/Suite.cpp
+++ b/libyul/optimiser/Suite.cpp
@@ -105,14 +105,17 @@ void OptimiserSuite::run(
 		RedundantAssignEliminator::run(ast);
 		RedundantAssignEliminator::run(ast);
 		UnusedPruner::runUntilStabilised(ast, reservedIdentifiers);
+		CommonSubexpressionEliminator{}(ast);
 	}
 	ExpressionJoiner::run(ast);
+	Rematerialiser::run(ast);
 	UnusedPruner::runUntilStabilised(ast);
 	ExpressionJoiner::run(ast);
 	UnusedPruner::runUntilStabilised(ast);
 	ExpressionJoiner::run(ast);
 	UnusedPruner::runUntilStabilised(ast);
 	ExpressionJoiner::run(ast);
+	Rematerialiser::run(ast);
 	UnusedPruner::runUntilStabilised(ast);
 
 	_ast = std::move(ast);