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

17 files changed, 136 insertions, 122 deletions

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))
+// }