Merge pull request #5620 from ethereum/rematOnlyOne

[Yul] Use rematerializer if variable is only referenced once or value is "cheap".

23 files changed, 261 insertions, 127 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);
diff --git a/test/libyul/YulOptimizerTest.cpp b/test/libyul/YulOptimizerTest.cpp
index 9643a1e9..0c782b17 100644
--- a/test/libyul/YulOptimizerTest.cpp
+++ b/test/libyul/YulOptimizerTest.cpp
@@ -171,7 +171,7 @@ bool YulOptimizerTest::run(ostream& _stream, string const& _linePrefix, bool con
 	else if (m_optimizerStep == "rematerialiser")
 	{
 		disambiguate();
-		(Rematerialiser{})(*m_ast);
+		Rematerialiser::run(*m_ast);
 	}
 	else if (m_optimizerStep == "expressionSimplifier")
 	{
diff --git a/test/libyul/objectCompiler/nested_optimizer.yul b/test/libyul/objectCompiler/nested_optimizer.yul
index 7739ce61..2775c346 100644
--- a/test/libyul/objectCompiler/nested_optimizer.yul
+++ b/test/libyul/objectCompiler/nested_optimizer.yul
@@ -19,31 +19,21 @@ object "a" {
 // Assembly:
 //     /* "source":60:61   */
 //   0x00
-//     /* "source":137:138   */
-//   dup1
-//     /* "source":60:61   */
-//   dup2
+//   0x00
 //     /* "source":47:62   */
 //   calldataload
 //     /* "source":119:139   */
 //   sstore
-//     /* "source":32:143   */
-//   pop
 // stop
 //
 // sub_0: assembly {
 //         /* "source":200:201   */
 //       0x00
-//         /* "source":283:284   */
-//       dup1
-//         /* "source":200:201   */
-//       dup2
+//       0x00
 //         /* "source":187:202   */
 //       calldataload
 //         /* "source":265:285   */
 //       sstore
-//         /* "source":170:291   */
-//       pop
 // }
-// Bytecode: 60008081355550fe
-// Opcodes: PUSH1 0x0 DUP1 DUP2 CALLDATALOAD SSTORE POP INVALID
+// Bytecode: 600060003555fe
+// Opcodes: PUSH1 0x0 PUSH1 0x0 CALLDATALOAD SSTORE INVALID
diff --git a/test/libyul/objectCompiler/simple_optimizer.yul b/test/libyul/objectCompiler/simple_optimizer.yul
index 43b33553..c757dee7 100644
--- a/test/libyul/objectCompiler/simple_optimizer.yul
+++ b/test/libyul/objectCompiler/simple_optimizer.yul
@@ -9,15 +9,10 @@
 // Assembly:
 //     /* "source":38:39   */
 //   0x00
-//     /* "source":109:110   */
-//   dup1
-//     /* "source":38:39   */
-//   dup2
+//   0x00
 //     /* "source":25:40   */
 //   calldataload
 //     /* "source":91:111   */
 //   sstore
-//     /* "source":12:113   */
-//   pop
-// Bytecode: 60008081355550
-// Opcodes: PUSH1 0x0 DUP1 DUP2 CALLDATALOAD SSTORE POP
+// Bytecode: 600060003555
+// Opcodes: PUSH1 0x0 PUSH1 0x0 CALLDATALOAD SSTORE
diff --git a/test/libyul/yulOptimizerTests/fullSuite/abi_example1.yul b/test/libyul/yulOptimizerTests/fullSuite/abi_example1.yul
index efb846f2..b261b5bc 100644
--- a/test/libyul/yulOptimizerTests/fullSuite/abi_example1.yul
+++ b/test/libyul/yulOptimizerTests/fullSuite/abi_example1.yul
@@ -460,14 +460,13 @@
 // {
 //     {
 //         let _1 := 0x20
-//         let _2 := 0
-//         let _485 := mload(_2)
+//         let _485 := mload(0)
 //         let abi_encode_pos := _1
 //         let abi_encode_length_68 := mload(_485)
 //         mstore(_1, abi_encode_length_68)
 //         abi_encode_pos := 64
 //         let abi_encode_srcPtr := add(_485, _1)
-//         let abi_encode_i_69 := _2
+//         let abi_encode_i_69 := 0
 //         for {
 //         }
 //         lt(abi_encode_i_69, abi_encode_length_68)
@@ -477,12 +476,11 @@
 //         {
 //             let _863 := mload(abi_encode_srcPtr)
 //             let abi_encode_pos_71_971 := abi_encode_pos
-//             let abi_encode_length_72_972 := 0x3
 //             let abi_encode_srcPtr_73_973 := _863
-//             let abi_encode_i_74_974 := _2
+//             let abi_encode_i_74_974 := 0
 //             for {
 //             }
-//             lt(abi_encode_i_74_974, abi_encode_length_72_972)
+//             lt(abi_encode_i_74_974, 0x3)
 //             {
 //                 abi_encode_i_74_974 := add(abi_encode_i_74_974, 1)
 //             }
@@ -497,28 +495,24 @@
 //         let a, b, c, d := abi_decode_tuple_t_uint256t_uint256t_array$_t_uint256_$dyn_memory_ptrt_array$_t_array$_t_uint256_$2_memory_$dyn_memory_ptr(mload(_1), mload(0x40))
 //         sstore(a, b)
 //         sstore(c, d)
-//         sstore(_2, abi_encode_pos)
+//         sstore(0, abi_encode_pos)
 //     }
 //     function abi_decode_t_array$_t_array$_t_uint256_$2_memory_$dyn_memory_ptr(offset_3, end_4) -> array_5
 //     {
 //         if iszero(slt(add(offset_3, 0x1f), end_4))
 //         {
-//             revert(array_5, array_5)
+//             revert(0, 0)
 //         }
 //         let length_6 := calldataload(offset_3)
 //         let array_5_254 := allocateMemory(array_allocation_size_t_array$_t_array$_t_uint256_$2_memory_$dyn_memory_ptr(length_6))
 //         array_5 := array_5_254
 //         let dst_7 := array_5_254
 //         mstore(array_5_254, length_6)
-//         let _36 := 0x20
-//         let offset_3_256 := add(offset_3, _36)
-//         dst_7 := add(array_5_254, _36)
-//         let src_8 := offset_3_256
-//         let _38 := 0x40
-//         if gt(add(add(offset_3, mul(length_6, _38)), _36), end_4)
+//         dst_7 := add(array_5_254, 0x20)
+//         let src_8 := add(offset_3, 0x20)
+//         if gt(add(add(offset_3, mul(length_6, 0x40)), 0x20), end_4)
 //         {
-//             let _42 := 0
-//             revert(_42, _42)
+//             revert(0, 0)
 //         }
 //         let i_9 := 0
 //         for {
@@ -529,46 +523,42 @@
 //         }
 //         {
 //             mstore(dst_7, abi_decode_t_array$_t_uint256_$2_memory(src_8, end_4))
-//             dst_7 := add(dst_7, _36)
-//             src_8 := add(src_8, _38)
+//             dst_7 := add(dst_7, 0x20)
+//             src_8 := add(src_8, 0x40)
 //         }
 //     }
 //     function abi_decode_t_array$_t_uint256_$2_memory(offset_11, end_12) -> array_13
 //     {
 //         if iszero(slt(add(offset_11, 0x1f), end_12))
 //         {
-//             revert(array_13, array_13)
+//             revert(0, 0)
 //         }
-//         let length_14 := 0x2
-//         let array_allo__559 := 0x20
-//         let array_allo_size_95_605 := 64
-//         let array_13_263 := allocateMemory(array_allo_size_95_605)
+//         let array_13_263 := allocateMemory(64)
 //         array_13 := array_13_263
 //         let dst_15 := array_13_263
 //         let src_16 := offset_11
-//         if gt(add(offset_11, array_allo_size_95_605), end_12)
+//         if gt(add(offset_11, 64), end_12)
 //         {
-//             let _59 := 0
-//             revert(_59, _59)
+//             revert(0, 0)
 //         }
 //         let i_17 := 0
 //         for {
 //         }
-//         lt(i_17, length_14)
+//         lt(i_17, 0x2)
 //         {
 //             i_17 := add(i_17, 1)
 //         }
 //         {
 //             mstore(dst_15, calldataload(src_16))
-//             dst_15 := add(dst_15, array_allo__559)
-//             src_16 := add(src_16, array_allo__559)
+//             dst_15 := add(dst_15, 0x20)
+//             src_16 := add(src_16, 0x20)
 //         }
 //     }
 //     function abi_decode_t_array$_t_uint256_$dyn_memory_ptr(offset_27, end_28) -> array_29
 //     {
 //         if iszero(slt(add(offset_27, 0x1f), end_28))
 //         {
-//             revert(array_29, array_29)
+//             revert(0, 0)
 //         }
 //         let length_30 := calldataload(offset_27)
 //         let array_29_279 := allocateMemory(array_allocation_size_t_array$_t_uint256_$dyn_memory_ptr(length_30))
@@ -576,13 +566,11 @@
 //         let dst_31 := array_29_279
 //         mstore(array_29_279, length_30)
 //         let _91 := 0x20
-//         let offset_27_281 := add(offset_27, _91)
 //         dst_31 := add(array_29_279, _91)
-//         let src_32 := offset_27_281
+//         let src_32 := add(offset_27, _91)
 //         if gt(add(add(offset_27, mul(length_30, _91)), _91), end_28)
 //         {
-//             let _97 := 0
-//             revert(_97, _97)
+//             revert(0, 0)
 //         }
 //         let i_33 := 0
 //         for {
@@ -621,40 +609,36 @@
 //             let offset_65 := calldataload(add(headStart_58, 96))
 //             if gt(offset_65, 0xffffffffffffffff)
 //             {
-//                 revert(value3, value3)
+//                 revert(0, 0)
 //             }
 //             value3 := abi_decode_t_array$_t_array$_t_uint256_$2_memory_$dyn_memory_ptr(add(headStart_58, offset_65), dataEnd_59)
 //         }
 //     }
 //     function allocateMemory(size) -> memPtr
 //     {
-//         let _199 := 64
-//         let memPtr_315 := mload(_199)
+//         let memPtr_315 := mload(64)
 //         memPtr := memPtr_315
 //         let newFreePtr := add(memPtr_315, size)
 //         if or(gt(newFreePtr, 0xffffffffffffffff), lt(newFreePtr, memPtr_315))
 //         {
-//             let _204 := 0
-//             revert(_204, _204)
+//             revert(0, 0)
 //         }
-//         mstore(_199, newFreePtr)
+//         mstore(64, newFreePtr)
 //     }
 //     function array_allocation_size_t_array$_t_array$_t_uint256_$2_memory_$dyn_memory_ptr(length_92) -> size_93
 //     {
 //         if gt(length_92, 0xffffffffffffffff)
 //         {
-//             revert(size_93, size_93)
+//             revert(0, 0)
 //         }
-//         let _217 := 0x20
-//         size_93 := add(mul(length_92, _217), _217)
+//         size_93 := add(mul(length_92, 0x20), 0x20)
 //     }
 //     function array_allocation_size_t_array$_t_uint256_$dyn_memory_ptr(length_98) -> size_99
 //     {
 //         if gt(length_98, 0xffffffffffffffff)
 //         {
-//             revert(size_99, size_99)
+//             revert(0, 0)
 //         }
-//         let _234 := 0x20
-//         size_99 := add(mul(length_98, _234), _234)
+//         size_99 := add(mul(length_98, 0x20), 0x20)
 //     }
 // }
diff --git a/test/libyul/yulOptimizerTests/fullSuite/medium.yul b/test/libyul/yulOptimizerTests/fullSuite/medium.yul
index fbe243d4..5578452a 100644
--- a/test/libyul/yulOptimizerTests/fullSuite/medium.yul
+++ b/test/libyul/yulOptimizerTests/fullSuite/medium.yul
@@ -20,12 +20,11 @@
 // fullSuite
 // {
 //     {
-//         let _1 := 0x20
 //         let allocate__19 := 0x40
-//         mstore(allocate__19, add(mload(allocate__19), _1))
+//         mstore(allocate__19, add(mload(allocate__19), 0x20))
 //         let allocate_p_24_41 := mload(allocate__19)
 //         mstore(allocate__19, add(allocate_p_24_41, allocate__19))
 //         mstore(add(allocate_p_24_41, 96), 2)
-//         mstore(allocate__19, _1)
+//         mstore(allocate__19, 0x20)
 //     }
 // }
diff --git a/test/libyul/yulOptimizerTests/rematerialiser/branches_for1.yul b/test/libyul/yulOptimizerTests/rematerialiser/branches_for1.yul
index dbd1ee63..3160381f 100644
--- a/test/libyul/yulOptimizerTests/rematerialiser/branches_for1.yul
+++ b/test/libyul/yulOptimizerTests/rematerialiser/branches_for1.yul
@@ -1,5 +1,5 @@
 {
-    let a := 1
+    let a := caller()
     for { pop(a) } a { pop(a) } {
         pop(a)
     }
@@ -7,15 +7,15 @@
 // ----
 // rematerialiser
 // {
-//     let a := 1
+//     let a := caller()
 //     for {
-//         pop(1)
+//         pop(caller())
 //     }
-//     1
+//     caller()
 //     {
-//         pop(1)
+//         pop(caller())
 //     }
 //     {
-//         pop(1)
+//         pop(caller())
 //     }
 // }
diff --git a/test/libyul/yulOptimizerTests/rematerialiser/branches_for2.yul b/test/libyul/yulOptimizerTests/rematerialiser/branches_for2.yul
index 6a52e045..eb092e95 100644
--- a/test/libyul/yulOptimizerTests/rematerialiser/branches_for2.yul
+++ b/test/libyul/yulOptimizerTests/rematerialiser/branches_for2.yul
@@ -1,7 +1,7 @@
 {
-    let a := 1
+    let a := caller()
     for { pop(a) } a { pop(a) } {
-        a := 7
+        a := address()
         let c := a
     }
     let x := a
@@ -9,17 +9,17 @@
 // ----
 // rematerialiser
 // {
-//     let a := 1
+//     let a := caller()
 //     for {
-//         pop(1)
+//         pop(caller())
 //     }
 //     a
 //     {
-//         pop(7)
+//         pop(address())
 //     }
 //     {
-//         a := 7
-//         let c := 7
+//         a := address()
+//         let c := address()
 //     }
 //     let x := a
 // }
diff --git a/test/libyul/yulOptimizerTests/rematerialiser/branches_for_declared_in_init1.yul b/test/libyul/yulOptimizerTests/rematerialiser/branches_for_declared_in_init1.yul
index fc816419..e7c689ca 100644
--- a/test/libyul/yulOptimizerTests/rematerialiser/branches_for_declared_in_init1.yul
+++ b/test/libyul/yulOptimizerTests/rematerialiser/branches_for_declared_in_init1.yul
@@ -1,6 +1,6 @@
 {
     let b := 0
-    for { let a := 1 pop(a) } a { pop(a) } {
+    for { let a := caller() pop(a) } a { pop(a) } {
         b := 1 pop(a)
     }
 }
@@ -9,15 +9,15 @@
 // {
 //     let b := 0
 //     for {
-//         let a := 1
-//         pop(1)
+//         let a := caller()
+//         pop(caller())
 //     }
-//     1
+//     caller()
 //     {
-//         pop(1)
+//         pop(caller())
 //     }
 //     {
 //         b := 1
-//         pop(1)
+//         pop(caller())
 //     }
 // }
diff --git a/test/libyul/yulOptimizerTests/rematerialiser/branches_for_declared_in_init2.yul b/test/libyul/yulOptimizerTests/rematerialiser/branches_for_declared_in_init2.yul
index 3d916890..80ee9233 100644
--- a/test/libyul/yulOptimizerTests/rematerialiser/branches_for_declared_in_init2.yul
+++ b/test/libyul/yulOptimizerTests/rematerialiser/branches_for_declared_in_init2.yul
@@ -1,6 +1,6 @@
 {
     let b := 0
-    for { let a := 1 pop(a) } lt(a, 0) { pop(a) a := add(a, 3) } {
+    for { let a := caller() pop(a) } lt(a, 0) { pop(a) a := add(a, 3) } {
         b := 1 pop(a)
     }
 }
@@ -9,8 +9,8 @@
 // {
 //     let b := 0
 //     for {
-//         let a := 1
-//         pop(1)
+//         let a := caller()
+//         pop(caller())
 //     }
 //     lt(a, 0)
 //     {
diff --git a/test/libyul/yulOptimizerTests/rematerialiser/branches_if.yul b/test/libyul/yulOptimizerTests/rematerialiser/branches_if.yul
index c148c2f2..2aff06d4 100644
--- a/test/libyul/yulOptimizerTests/rematerialiser/branches_if.yul
+++ b/test/libyul/yulOptimizerTests/rematerialiser/branches_if.yul
@@ -1,18 +1,18 @@
 {
-    let a := 1
-    let b := 2
+    let a := caller()
+    let b := address()
     if b { pop(b) b := a }
     let c := b
 }
 // ----
 // rematerialiser
 // {
-//     let a := 1
-//     let b := 2
-//     if 2
+//     let a := caller()
+//     let b := address()
+//     if address()
 //     {
-//         pop(2)
-//         b := 1
+//         pop(address())
+//         b := caller()
 //     }
 //     let c := b
 // }
diff --git a/test/libyul/yulOptimizerTests/rematerialiser/cheap_caller.yul b/test/libyul/yulOptimizerTests/rematerialiser/cheap_caller.yul
new file mode 100644
index 00000000..7e99e428
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/rematerialiser/cheap_caller.yul
@@ -0,0 +1,16 @@
+{
+    // The caller opcode is cheap, so inline it,
+    // no matter how often it is used
+    let a := caller()
+    mstore(a, a)
+    mstore(add(a, a), mload(a))
+    sstore(a, sload(a))
+}
+// ----
+// rematerialiser
+// {
+//     let a := caller()
+//     mstore(caller(), caller())
+//     mstore(add(caller(), caller()), mload(caller()))
+//     sstore(caller(), sload(caller()))
+// }
diff --git a/test/libyul/yulOptimizerTests/rematerialiser/do_not_remat_large_amounts_of_code2.yul b/test/libyul/yulOptimizerTests/rematerialiser/do_not_remat_large_amounts_of_code2.yul
deleted file mode 100644
index d95dc1fc..00000000
--- a/test/libyul/yulOptimizerTests/rematerialiser/do_not_remat_large_amounts_of_code2.yul
+++ /dev/null
@@ -1,10 +0,0 @@
-{
-	let x := add(mul(calldataload(2), calldataload(4)), calldatasize())
-	let b := x
-}
-// ----
-// rematerialiser
-// {
-//     let x := add(mul(calldataload(2), calldataload(4)), calldatasize())
-//     let b := add(mul(calldataload(2), calldataload(4)), calldatasize())
-// }
diff --git a/test/libyul/yulOptimizerTests/rematerialiser/do_not_remat_large_amounts_of_code1.yul b/test/libyul/yulOptimizerTests/rematerialiser/do_remat_large_amounts_of_code_if_used_once.yul
index 016fa0d7..e464d404 100644
--- a/test/libyul/yulOptimizerTests/rematerialiser/do_not_remat_large_amounts_of_code1.yul
+++ b/test/libyul/yulOptimizerTests/rematerialiser/do_remat_large_amounts_of_code_if_used_once.yul
@@ -6,5 +6,5 @@
 // rematerialiser
 // {
 //     let x := add(mul(calldataload(2), calldataload(4)), mul(2, calldatasize()))
-//     let b := x
+//     let b := add(mul(calldataload(2), calldataload(4)), mul(2, calldatasize()))
 // }
diff --git a/test/libyul/yulOptimizerTests/rematerialiser/expression.yul b/test/libyul/yulOptimizerTests/rematerialiser/expression.yul
deleted file mode 100644
index a801677d..00000000
--- a/test/libyul/yulOptimizerTests/rematerialiser/expression.yul
+++ /dev/null
@@ -1,10 +0,0 @@
-{
-    let a := add(mul(calldatasize(), 2), number())
-    let b := add(a, a)
-}
-// ----
-// rematerialiser
-// {
-//     let a := add(mul(calldatasize(), 2), number())
-//     let b := add(add(mul(calldatasize(), 2), number()), add(mul(calldatasize(), 2), number()))
-// }
diff --git a/test/libyul/yulOptimizerTests/rematerialiser/large_constant.yul b/test/libyul/yulOptimizerTests/rematerialiser/large_constant.yul
new file mode 100644
index 00000000..9c7c66f1
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/rematerialiser/large_constant.yul
@@ -0,0 +1,12 @@
+{
+    // Constants cost depending on their magnitude.
+    // Do not rematerialize large constants.
+    let a := 0xffffffffffffffffffffff
+    mstore(a, a)
+}
+// ----
+// rematerialiser
+// {
+//     let a := 0xffffffffffffffffffffff
+//     mstore(a, a)
+// }
diff --git a/test/libyul/yulOptimizerTests/rematerialiser/large_constant_used_once.yul b/test/libyul/yulOptimizerTests/rematerialiser/large_constant_used_once.yul
new file mode 100644
index 00000000..b8a861aa
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/rematerialiser/large_constant_used_once.yul
@@ -0,0 +1,13 @@
+{
+    // Constants cost depending on their magnitude.
+    // Do not rematerialize large constants,
+    // unless they are used exactly once.
+    let a := 0xffffffffffffffffffffff
+    mstore(0, a)
+}
+// ----
+// rematerialiser
+// {
+//     let a := 0xffffffffffffffffffffff
+//     mstore(0, 0xffffffffffffffffffffff)
+// }
diff --git a/test/libyul/yulOptimizerTests/rematerialiser/medium_sized_constant.yul b/test/libyul/yulOptimizerTests/rematerialiser/medium_sized_constant.yul
new file mode 100644
index 00000000..98cdbd09
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/rematerialiser/medium_sized_constant.yul
@@ -0,0 +1,25 @@
+{
+    // Constants cost depending on their magnitude.
+    // Rematerialize small constants only if they are
+    // not used too often.
+    // b is used 5 times
+    let b := 2
+    mstore(b, b)
+    mstore(add(b, b), b)
+    // a is used 7 times
+    let a := 1
+    mstore(a, a)
+    mstore(add(a, a), a)
+    mstore(a, mload(a))
+}
+// ----
+// rematerialiser
+// {
+//     let b := 2
+//     mstore(2, 2)
+//     mstore(add(2, 2), 2)
+//     let a := 1
+//     mstore(a, a)
+//     mstore(add(a, a), a)
+//     mstore(a, mload(a))
+// }
diff --git a/test/tools/yulopti.cpp b/test/tools/yulopti.cpp
index fcbe308f..e88b0538 100644
--- a/test/tools/yulopti.cpp
+++ b/test/tools/yulopti.cpp
@@ -182,7 +182,7 @@ public:
 				RedundantAssignEliminator::run(*m_ast);
 				break;
 			case 'm':
-				Rematerialiser{}(*m_ast);
+				Rematerialiser::run(*m_ast);
 				break;
 			default:
 				cout << "Unknown option." << endl;