Add structural simplifier as optimization step for Yul.

12 files changed, 87 insertions, 11 deletions

diff --git a/test/libyul/YulOptimizerTest.cpp b/test/libyul/YulOptimizerTest.cpp
index 96b9d263..ba7eced3 100644
--- a/test/libyul/YulOptimizerTest.cpp
+++ b/test/libyul/YulOptimizerTest.cpp
@@ -39,6 +39,7 @@
 #include <libyul/optimiser/ExpressionJoiner.h>
 #include <libyul/optimiser/SSATransform.h>
 #include <libyul/optimiser/RedundantAssignEliminator.h>
+#include <libyul/optimiser/StructuralSimplifier.h>
 #include <libyul/optimiser/Suite.h>
 #include <libyul/AsmPrinter.h>
 #include <libyul/AsmParser.h>
@@ -213,6 +214,11 @@ bool YulOptimizerTest::run(ostream& _stream, string const& _linePrefix, bool con
 		SSATransform::run(*m_ast, nameDispenser);
 		RedundantAssignEliminator::run(*m_ast);
 	}
+	else if (m_optimizerStep == "structuralSimplifier")
+	{
+		disambiguate();
+		StructuralSimplifier{}(*m_ast);
+	}
 	else if (m_optimizerStep == "fullSuite")
 		OptimiserSuite::run(*m_ast, *m_analysisInfo);
 	else
diff --git a/test/libyul/yulOptimizerTests/fullSuite/abi_example1.yul b/test/libyul/yulOptimizerTests/fullSuite/abi_example1.yul
index 573e7868..61ba11d2 100644
--- a/test/libyul/yulOptimizerTests/fullSuite/abi_example1.yul
+++ b/test/libyul/yulOptimizerTests/fullSuite/abi_example1.yul
@@ -599,10 +599,6 @@
 //                     revert(_2, _2)
 //                 }
 //                 let abi_decode_abi_decode_length_14_1069 := 0x2
-//                 if _2
-//                 {
-//                     revert(_2, _2)
-//                 }
 //                 let allocateMe_memPtr_315 := mload(abi_encode_pos_590)
 //                 let allocateMe_newFreePtr := add(allocateMe_memPtr_315, abi_encode_pos_590)
 //                 if or(gt(allocateMe_newFreePtr, _945), lt(allocateMe_newFreePtr, allocateMe_memPtr_315))
diff --git a/test/libyul/yulOptimizerTests/fullSuite/medium.yul b/test/libyul/yulOptimizerTests/fullSuite/medium.yul
index deb02068..fbe243d4 100644
--- a/test/libyul/yulOptimizerTests/fullSuite/medium.yul
+++ b/test/libyul/yulOptimizerTests/fullSuite/medium.yul
@@ -9,16 +9,23 @@
     pop(allocate(0x20))
     let x := allocate(0x40)
     mstore(array_index_access(x, 3), 2)
+    if 0 {
+        mstore(0x40, 0x20)
+    }
+    if sub(2,1) {
+        for { switch mul(1,2) case 2 { mstore(0x40, 0x20) } } sub(1,1) {} { mstore(0x80, 0x40) }
+    }
 }
 // ----
 // fullSuite
 // {
 //     {
-//         let _18 := 0x20
-//         let allocate__7 := 0x40
-//         mstore(allocate__7, add(mload(allocate__7), _18))
-//         let allocate_p_12_31 := mload(allocate__7)
-//         mstore(allocate__7, add(allocate_p_12_31, allocate__7))
-//         mstore(add(allocate_p_12_31, 96), 2)
+//         let _1 := 0x20
+//         let allocate__19 := 0x40
+//         mstore(allocate__19, add(mload(allocate__19), _1))
+//         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)
 //     }
 // }
diff --git a/test/libyul/yulOptimizerTests/structuralSimplifier/empty_if_movable_condition.yul b/test/libyul/yulOptimizerTests/structuralSimplifier/empty_if_movable_condition.yul
new file mode 100644
index 00000000..ee1975e7
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/structuralSimplifier/empty_if_movable_condition.yul
@@ -0,0 +1,7 @@
+{ let a := mload(0) if a {} }
+// ----
+// structuralSimplifier
+// {
+//     let a := mload(0)
+//     pop(a)
+// }
diff --git a/test/libyul/yulOptimizerTests/structuralSimplifier/empty_if_non_movable_condition.yul b/test/libyul/yulOptimizerTests/structuralSimplifier/empty_if_non_movable_condition.yul
new file mode 100644
index 00000000..5977297b
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/structuralSimplifier/empty_if_non_movable_condition.yul
@@ -0,0 +1,6 @@
+{ if mload(0) {} }
+// ----
+// structuralSimplifier
+// {
+//     pop(mload(0))
+// }
diff --git a/test/libyul/yulOptimizerTests/structuralSimplifier/for_false_condition.sol b/test/libyul/yulOptimizerTests/structuralSimplifier/for_false_condition.sol
new file mode 100644
index 00000000..b881a0a3
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/structuralSimplifier/for_false_condition.sol
@@ -0,0 +1,10 @@
+{
+    for { let a := 42 } 0 { a := a } {
+        let b := a
+    }
+}
+// ----
+// structuralSimplifier
+// {
+//     let a := 42
+// }
diff --git a/test/libyul/yulOptimizerTests/structuralSimplifier/if_false_condition.yul b/test/libyul/yulOptimizerTests/structuralSimplifier/if_false_condition.yul
new file mode 100644
index 00000000..0895b1bb
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/structuralSimplifier/if_false_condition.yul
@@ -0,0 +1,5 @@
+{ if 0 { mstore(0, 0) } }
+// ----
+// structuralSimplifier
+// {
+// }
diff --git a/test/libyul/yulOptimizerTests/structuralSimplifier/if_true_condition.yul b/test/libyul/yulOptimizerTests/structuralSimplifier/if_true_condition.yul
new file mode 100644
index 00000000..ca9cba06
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/structuralSimplifier/if_true_condition.yul
@@ -0,0 +1,6 @@
+{ if 1 { mstore(0, 0) } }
+// ----
+// structuralSimplifier
+// {
+//     mstore(0, 0)
+// }
diff --git a/test/libyul/yulOptimizerTests/structuralSimplifier/nested.yul b/test/libyul/yulOptimizerTests/structuralSimplifier/nested.yul
new file mode 100644
index 00000000..169a84d1
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/structuralSimplifier/nested.yul
@@ -0,0 +1,6 @@
+{ if 1 { if 1 { for { mstore(0, 0) } 0 {} { mstore(2, 3) }  if 0 { mstore(1, 2) } } } }
+// ----
+// structuralSimplifier
+// {
+//     mstore(0, 0)
+// }
diff --git a/test/libyul/yulOptimizerTests/structuralSimplifier/switch_only_default.yul b/test/libyul/yulOptimizerTests/structuralSimplifier/switch_only_default.yul
new file mode 100644
index 00000000..7ca815a7
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/structuralSimplifier/switch_only_default.yul
@@ -0,0 +1,11 @@
+{
+	switch mload(0) default { mstore(1, 2) }
+}
+// ----
+// structuralSimplifier
+// {
+//     pop(mload(0))
+//     {
+//         mstore(1, 2)
+//     }
+// }
diff --git a/test/libyul/yulOptimizerTests/structuralSimplifier/switch_to_if.yul b/test/libyul/yulOptimizerTests/structuralSimplifier/switch_to_if.yul
new file mode 100644
index 00000000..a741ac2f
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/structuralSimplifier/switch_to_if.yul
@@ -0,0 +1,11 @@
+{
+	switch 1 case 2 { mstore(0, 0) }
+}
+// ----
+// structuralSimplifier
+// {
+//     if eq(2, 1)
+//     {
+//         mstore(0, 0)
+//     }
+// }
diff --git a/test/tools/yulopti.cpp b/test/tools/yulopti.cpp
index d6dbc1b1..477de42f 100644
--- a/test/tools/yulopti.cpp
+++ b/test/tools/yulopti.cpp
@@ -46,6 +46,7 @@
 #include <libyul/optimiser/ExpressionJoiner.h>
 #include <libyul/optimiser/RedundantAssignEliminator.h>
 #include <libyul/optimiser/SSATransform.h>
+#include <libyul/optimiser/StructuralSimplifier.h>
 #include <libyul/optimiser/VarDeclPropagator.h>
 
 #include <libdevcore/JSON.h>
@@ -124,7 +125,8 @@ public:
 			}
 			cout << "(q)quit/(f)flatten/(c)se/propagate var(d)ecls/(x)plit/(j)oin/(g)rouper/(h)oister/" << endl;
 			cout << "  (e)xpr inline/(i)nline/(s)implify/(u)nusedprune/ss(a) transform/" << endl;
-			cout << "  (r)edundant assign elim./re(m)aterializer/f(o)r-loop-pre-rewriter? ";
+			cout << "  (r)edundant assign elim./re(m)aterializer/f(o)r-loop-pre-rewriter/" << endl;
+			cout << "  s(t)ructural simplifier? " << endl;
 			cout.flush();
 			int option = readStandardInputChar();
 			cout << ' ' << char(option) << endl;
@@ -165,6 +167,9 @@ public:
 			case 's':
 				ExpressionSimplifier::run(*m_ast);
 				break;
+			case 't':
+				(StructuralSimplifier{})(*m_ast);
+				break;
 			case 'u':
 				UnusedPruner::runUntilStabilised(*m_ast);
 				break;