Merge pull request #5292 from ethereum/redundantAssignEliminator

[Yul] Redundant assign eliminator.

20 files changed, 413 insertions, 0 deletions

diff --git a/test/libyul/YulOptimizerTest.cpp b/test/libyul/YulOptimizerTest.cpp
index 6782f412..67715ac1 100644
--- a/test/libyul/YulOptimizerTest.cpp
+++ b/test/libyul/YulOptimizerTest.cpp
@@ -36,6 +36,7 @@
 #include <libyul/optimiser/UnusedPruner.h>
 #include <libyul/optimiser/ExpressionJoiner.h>
 #include <libyul/optimiser/SSATransform.h>
+#include <libyul/optimiser/RedundantAssignEliminator.h>
 
 #include <libsolidity/parsing/Scanner.h>
 #include <libsolidity/inlineasm/AsmPrinter.h>
@@ -178,6 +179,18 @@ bool YulOptimizerTest::run(ostream& _stream, string const& _linePrefix, bool con
 		NameDispenser nameDispenser(*m_ast);
 		SSATransform::run(*m_ast, nameDispenser);
 	}
+	else if (m_optimizerStep == "redundantAssignEliminator")
+	{
+		disambiguate();
+		RedundantAssignEliminator::run(*m_ast);
+	}
+	else if (m_optimizerStep == "ssaPlusCleanup")
+	{
+		disambiguate();
+		NameDispenser nameDispenser(*m_ast);
+		SSATransform::run(*m_ast, nameDispenser);
+		RedundantAssignEliminator::run(*m_ast);
+	}
 	else
 	{
 		FormattedScope(_stream, _formatted, {formatting::BOLD, formatting::RED}) << _linePrefix << "Invalid optimizer step: " << m_optimizerStep << endl;
diff --git a/test/libyul/yulOptimizerTests/redundantAssignEliminator/for.yul b/test/libyul/yulOptimizerTests/redundantAssignEliminator/for.yul
new file mode 100644
index 00000000..d9bbd86d
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/redundantAssignEliminator/for.yul
@@ -0,0 +1,26 @@
+{
+    for {
+        let a := 2
+        // Should not be removed, even though you might think
+        // it goes out of scope
+        a := 3
+    } a { a := add(a, 1) }
+    {
+        a := 7
+    }
+}
+// ----
+// redundantAssignEliminator
+// {
+//     for {
+//         let a := 2
+//         a := 3
+//     }
+//     a
+//     {
+//         a := add(a, 1)
+//     }
+//     {
+//         a := 7
+//     }
+// }
diff --git a/test/libyul/yulOptimizerTests/redundantAssignEliminator/for_branch.yul b/test/libyul/yulOptimizerTests/redundantAssignEliminator/for_branch.yul
new file mode 100644
index 00000000..7f5e97ce
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/redundantAssignEliminator/for_branch.yul
@@ -0,0 +1,31 @@
+{
+    let x
+    let y
+    // Cannot be removed, because we might skip the loop
+    x := 1
+    for { } calldataload(0) { }
+    {
+        // Cannot be removed
+        x := 2
+        // Can be removed
+        y := 3
+    }
+    y := 8
+    mstore(x, 0)
+}
+// ----
+// redundantAssignEliminator
+// {
+//     let x
+//     let y
+//     x := 1
+//     for {
+//     }
+//     calldataload(0)
+//     {
+//     }
+//     {
+//         x := 2
+//     }
+//     mstore(x, 0)
+// }
diff --git a/test/libyul/yulOptimizerTests/redundantAssignEliminator/for_rerun.yul b/test/libyul/yulOptimizerTests/redundantAssignEliminator/for_rerun.yul
new file mode 100644
index 00000000..65eb2838
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/redundantAssignEliminator/for_rerun.yul
@@ -0,0 +1,27 @@
+{
+    let x
+    // Cannot be removed, because we might run the loop only once
+    x := 1
+    for { } calldataload(0) { }
+    {
+        mstore(x, 2)
+        // Cannot be removed because of the line above
+        x := 2
+    }
+    x := 3
+}
+// ----
+// redundantAssignEliminator
+// {
+//     let x
+//     x := 1
+//     for {
+//     }
+//     calldataload(0)
+//     {
+//     }
+//     {
+//         mstore(x, 2)
+//         x := 2
+//     }
+// }
diff --git a/test/libyul/yulOptimizerTests/redundantAssignEliminator/function.yul b/test/libyul/yulOptimizerTests/redundantAssignEliminator/function.yul
new file mode 100644
index 00000000..5bb920ec
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/redundantAssignEliminator/function.yul
@@ -0,0 +1,23 @@
+{
+    let r
+    r := 1
+    function f(x, y) -> a, b {
+        // Can be removed, is param
+        x := 1
+        y := 2
+        // Cannot be removed, is return param
+        a := 3
+        b := 4
+    }
+    r := 2
+}
+// ----
+// redundantAssignEliminator
+// {
+//     let r
+//     function f(x, y) -> a, b
+//     {
+//         a := 3
+//         b := 4
+//     }
+// }
diff --git a/test/libyul/yulOptimizerTests/redundantAssignEliminator/if.yul b/test/libyul/yulOptimizerTests/redundantAssignEliminator/if.yul
new file mode 100644
index 00000000..958bfc66
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/redundantAssignEliminator/if.yul
@@ -0,0 +1,24 @@
+{
+    let c
+    let d
+    c := calldataload(0)
+    d := 1
+    if c {
+        d := 2
+    }
+    // This enforces that none of the assignments above can be removed.
+    mstore(0, d)
+}
+// ----
+// redundantAssignEliminator
+// {
+//     let c
+//     let d
+//     c := calldataload(0)
+//     d := 1
+//     if c
+//     {
+//         d := 2
+//     }
+//     mstore(0, d)
+// }
diff --git a/test/libyul/yulOptimizerTests/redundantAssignEliminator/if_overwrite_all_branches.yul b/test/libyul/yulOptimizerTests/redundantAssignEliminator/if_overwrite_all_branches.yul
new file mode 100644
index 00000000..e47c31d1
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/redundantAssignEliminator/if_overwrite_all_branches.yul
@@ -0,0 +1,24 @@
+{
+    let c
+    let d
+    c := calldataload(0)
+    // This assignment will be overwritten in all branches and thus can be removed.
+    d := 1
+    if c {
+        d := 2
+    }
+    d := 3
+    mstore(0, d)
+}
+// ----
+// redundantAssignEliminator
+// {
+//     let c
+//     let d
+//     c := calldataload(0)
+//     if c
+//     {
+//     }
+//     d := 3
+//     mstore(0, d)
+// }
diff --git a/test/libyul/yulOptimizerTests/redundantAssignEliminator/if_used_in_one_branch.yul b/test/libyul/yulOptimizerTests/redundantAssignEliminator/if_used_in_one_branch.yul
new file mode 100644
index 00000000..00065ed2
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/redundantAssignEliminator/if_used_in_one_branch.yul
@@ -0,0 +1,25 @@
+{
+    let c
+    let d
+    c := calldataload(0)
+    d := 1
+    if c {
+        // Uses the assignment above
+        d := d
+    }
+    d := 3
+    mstore(0, d)
+}
+// ----
+// redundantAssignEliminator
+// {
+//     let c
+//     let d
+//     c := calldataload(0)
+//     d := 1
+//     if c
+//     {
+//     }
+//     d := 3
+//     mstore(0, d)
+// }
diff --git a/test/libyul/yulOptimizerTests/redundantAssignEliminator/multi_assign.yul b/test/libyul/yulOptimizerTests/redundantAssignEliminator/multi_assign.yul
new file mode 100644
index 00000000..26bcfc72
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/redundantAssignEliminator/multi_assign.yul
@@ -0,0 +1,19 @@
+{
+    function f() -> a, b {}
+    let x, y
+    x := 1
+    x := 2
+    // Will not be used, but is a multi-assign, so not removed.
+    x, y := f()
+    x := 3
+    y := 4
+}
+// ----
+// redundantAssignEliminator
+// {
+//     function f() -> a, b
+//     {
+//     }
+//     let x, y
+//     x, y := f()
+// }
diff --git a/test/libyul/yulOptimizerTests/redundantAssignEliminator/multivar.yul b/test/libyul/yulOptimizerTests/redundantAssignEliminator/multivar.yul
new file mode 100644
index 00000000..cf646126
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/redundantAssignEliminator/multivar.yul
@@ -0,0 +1,15 @@
+{
+    let a := 2
+    a := 7
+    let b := 8
+    b := a
+    a := b
+}
+// ----
+// redundantAssignEliminator
+// {
+//     let a := 2
+//     a := 7
+//     let b := 8
+//     b := a
+// }
diff --git a/test/libyul/yulOptimizerTests/redundantAssignEliminator/non_movable.yul b/test/libyul/yulOptimizerTests/redundantAssignEliminator/non_movable.yul
new file mode 100644
index 00000000..ae3e5226
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/redundantAssignEliminator/non_movable.yul
@@ -0,0 +1,11 @@
+{
+    let a
+    a := 0
+    a := mload(0)
+}
+// ----
+// redundantAssignEliminator
+// {
+//     let a
+//     a := mload(0)
+// }
diff --git a/test/libyul/yulOptimizerTests/redundantAssignEliminator/scopes.yul b/test/libyul/yulOptimizerTests/redundantAssignEliminator/scopes.yul
new file mode 100644
index 00000000..702f854d
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/redundantAssignEliminator/scopes.yul
@@ -0,0 +1,16 @@
+{
+    let a
+    {
+        let b
+        b := 2
+        a := 2
+    }
+}
+// ----
+// redundantAssignEliminator
+// {
+//     let a
+//     {
+//         let b
+//     }
+// }
diff --git a/test/libyul/yulOptimizerTests/redundantAssignEliminator/simple.yul b/test/libyul/yulOptimizerTests/redundantAssignEliminator/simple.yul
new file mode 100644
index 00000000..913a7694
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/redundantAssignEliminator/simple.yul
@@ -0,0 +1,10 @@
+{
+    let a
+    a := 1
+    a := 2
+}
+// ----
+// redundantAssignEliminator
+// {
+//     let a
+// }
diff --git a/test/libyul/yulOptimizerTests/redundantAssignEliminator/switch_overwrite_in_all.yul b/test/libyul/yulOptimizerTests/redundantAssignEliminator/switch_overwrite_in_all.yul
new file mode 100644
index 00000000..96265576
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/redundantAssignEliminator/switch_overwrite_in_all.yul
@@ -0,0 +1,22 @@
+{
+    let x
+    // Will be overwritten in all branches
+    x := 1
+    switch calldataload(0)
+    case 0 { x := 2 }
+    default { x := 3 }
+    mstore(x, 0)
+}
+// ----
+// redundantAssignEliminator
+// {
+//     let x
+//     switch calldataload(0)
+//     case 0 {
+//         x := 2
+//     }
+//     default {
+//         x := 3
+//     }
+//     mstore(x, 0)
+// }
diff --git a/test/libyul/yulOptimizerTests/redundantAssignEliminator/switch_overwrite_in_one.yul b/test/libyul/yulOptimizerTests/redundantAssignEliminator/switch_overwrite_in_one.yul
new file mode 100644
index 00000000..cbe859ed
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/redundantAssignEliminator/switch_overwrite_in_one.yul
@@ -0,0 +1,19 @@
+{
+    let x
+    // Will NOT be overwritten in all branches
+    x := 1
+    switch calldataload(0)
+    case 0 { x := 2 }
+    mstore(x, 0)
+}
+// ----
+// redundantAssignEliminator
+// {
+//     let x
+//     x := 1
+//     switch calldataload(0)
+//     case 0 {
+//         x := 2
+//     }
+//     mstore(x, 0)
+// }
diff --git a/test/libyul/yulOptimizerTests/redundantAssignEliminator/switch_overwrite_use_combination.yul b/test/libyul/yulOptimizerTests/redundantAssignEliminator/switch_overwrite_use_combination.yul
new file mode 100644
index 00000000..1a3b26eb
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/redundantAssignEliminator/switch_overwrite_use_combination.yul
@@ -0,0 +1,23 @@
+{
+    let x
+    // Will be used in some and overwritten in others
+    x := 1
+    switch calldataload(0)
+    case 0 { x := 2 }
+    default { mstore(x, 1) }
+    mstore(x, 0)
+}
+// ----
+// redundantAssignEliminator
+// {
+//     let x
+//     x := 1
+//     switch calldataload(0)
+//     case 0 {
+//         x := 2
+//     }
+//     default {
+//         mstore(x, 1)
+//     }
+//     mstore(x, 0)
+// }
diff --git a/test/libyul/yulOptimizerTests/redundantAssignEliminator/switch_unused.yul b/test/libyul/yulOptimizerTests/redundantAssignEliminator/switch_unused.yul
new file mode 100644
index 00000000..cc78b74d
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/redundantAssignEliminator/switch_unused.yul
@@ -0,0 +1,16 @@
+{
+    let x
+    // Not referenced anywhere.
+    x := 1
+    switch calldataload(0)
+    case 0 { mstore(0, 1) }
+}
+// ----
+// redundantAssignEliminator
+// {
+//     let x
+//     switch calldataload(0)
+//     case 0 {
+//         mstore(0, 1)
+//     }
+// }
diff --git a/test/libyul/yulOptimizerTests/ssaPlusCleanup/control_structures.yul b/test/libyul/yulOptimizerTests/ssaPlusCleanup/control_structures.yul
new file mode 100644
index 00000000..51d1627f
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/ssaPlusCleanup/control_structures.yul
@@ -0,0 +1,35 @@
+{
+    function copy(from, to) -> length {
+        length := mload(from)
+        mstore(to, length)
+        from := add(from, 0x20)
+        to := add(to, 0x20)
+        for { let x := 1 } lt(x, length) { x := add(x, 0x20) } {
+            mstore(add(to, x), mload(add(from, x)))
+        }
+    }
+}
+// ----
+// ssaPlusCleanup
+// {
+//     function copy(from, to) -> length
+//     {
+//         let length_1 := mload(from)
+//         length := length_1
+//         mstore(to, length_1)
+//         let from_1 := add(from, 0x20)
+//         let to_1 := add(to, 0x20)
+//         for {
+//             let x_1 := 1
+//             let x := x_1
+//         }
+//         lt(x, length_1)
+//         {
+//             let x_2 := add(x, 0x20)
+//             x := x_2
+//         }
+//         {
+//             mstore(add(to_1, x), mload(add(from_1, x)))
+//         }
+//     }
+// }
diff --git a/test/libyul/yulOptimizerTests/ssaPlusCleanup/multi_reassign.yul b/test/libyul/yulOptimizerTests/ssaPlusCleanup/multi_reassign.yul
new file mode 100644
index 00000000..ddb33aa0
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/ssaPlusCleanup/multi_reassign.yul
@@ -0,0 +1,17 @@
+{
+    let a := 1
+    a := 2
+    a := 3
+    a := 4
+    mstore(0, a)
+}
+// ----
+// ssaPlusCleanup
+// {
+//     let a_1 := 1
+//     let a := a_1
+//     let a_2 := 2
+//     let a_3 := 3
+//     let a_4 := 4
+//     mstore(0, a_4)
+// }
diff --git a/test/libyul/yulOptimizerTests/ssaPlusCleanup/multi_reassign_with_use.yul b/test/libyul/yulOptimizerTests/ssaPlusCleanup/multi_reassign_with_use.yul
new file mode 100644
index 00000000..67a6c5d3
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/ssaPlusCleanup/multi_reassign_with_use.yul
@@ -0,0 +1,17 @@
+{
+    let a := 1
+    a := add(a, 2)
+    a := add(a, 3)
+    a := mload(add(a, 4))
+    mstore(0, a)
+}
+// ----
+// ssaPlusCleanup
+// {
+//     let a_1 := 1
+//     let a := a_1
+//     let a_2 := add(a_1, 2)
+//     let a_3 := add(a_2, 3)
+//     let a_4 := mload(add(a_3, 4))
+//     mstore(0, a_4)
+// }