SSA transform - first step.

12 files changed, 314 insertions, 0 deletions

diff --git a/test/libyul/YulOptimizerTest.cpp b/test/libyul/YulOptimizerTest.cpp
index a89711a1..f4ea6d67 100644
--- a/test/libyul/YulOptimizerTest.cpp
+++ b/test/libyul/YulOptimizerTest.cpp
@@ -35,6 +35,7 @@
 #include <libyul/optimiser/ExpressionSimplifier.h>
 #include <libyul/optimiser/UnusedPruner.h>
 #include <libyul/optimiser/ExpressionJoiner.h>
+#include <libyul/optimiser/SSATransform.h>
 
 #include <libsolidity/parsing/Scanner.h>
 #include <libsolidity/inlineasm/AsmPrinter.h>
@@ -171,6 +172,12 @@ bool YulOptimizerTest::run(ostream& _stream, string const& _linePrefix, bool con
 		disambiguate();
 		ExpressionJoiner::run(*m_ast);\
 	}
+	else if (m_optimizerStep == "ssaTransform")
+	{
+		disambiguate();
+		NameDispenser nameDispenser(*m_ast);
+		SSATransform::run(*m_ast, nameDispenser);
+	}
 	else
 	{
 		FormattedScope(_stream, _formatted, {formatting::BOLD, formatting::RED}) << _linePrefix << "Invalid optimizer step: " << m_optimizerStep << endl;
diff --git a/test/libyul/yulOptimizerTests/ssaTransform/branches.yul b/test/libyul/yulOptimizerTests/ssaTransform/branches.yul
new file mode 100644
index 00000000..c089fe70
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/ssaTransform/branches.yul
@@ -0,0 +1,25 @@
+{
+  let a := 1
+  a := add(a, 1)
+  if a {
+    a := add(a, 1)
+  }
+  a := add(a, 1)
+  mstore(a, 1)
+}
+// ----
+// ssaTransform
+// {
+//     let a_1 := 1
+//     let a := a_1
+//     let a_2 := add(a_1, 1)
+//     a := a_2
+//     if a_2
+//     {
+//         let a_3 := add(a_2, 1)
+//         a := a_3
+//     }
+//     let a_4 := add(a, 1)
+//     a := a_4
+//     mstore(a_4, 1)
+// }
diff --git a/test/libyul/yulOptimizerTests/ssaTransform/for_reassign_body.yul b/test/libyul/yulOptimizerTests/ssaTransform/for_reassign_body.yul
new file mode 100644
index 00000000..41640346
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/ssaTransform/for_reassign_body.yul
@@ -0,0 +1,26 @@
+{
+    let a := mload(0)
+    for { mstore(0, a) } a { mstore(0, a) }
+    {
+        a := add(a, 3)
+    }
+    mstore(0, a)
+}
+// ----
+// ssaTransform
+// {
+//     let a_1 := mload(0)
+//     let a := a_1
+//     for {
+//         mstore(0, a_1)
+//     }
+//     a
+//     {
+//         mstore(0, a)
+//     }
+//     {
+//         let a_2 := add(a, 3)
+//         a := a_2
+//     }
+//     mstore(0, a)
+// }
diff --git a/test/libyul/yulOptimizerTests/ssaTransform/for_reassign_init.yul b/test/libyul/yulOptimizerTests/ssaTransform/for_reassign_init.yul
new file mode 100644
index 00000000..821a5b2a
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/ssaTransform/for_reassign_init.yul
@@ -0,0 +1,26 @@
+{
+    let a := mload(0)
+    for { a := add(a, 3) } a { mstore(0, a) }
+    {
+        mstore(0, a)
+    }
+    mstore(0, a)
+}
+// ----
+// ssaTransform
+// {
+//     let a_1 := mload(0)
+//     let a := a_1
+//     for {
+//         let a_2 := add(a_1, 3)
+//         a := a_2
+//     }
+//     a
+//     {
+//         mstore(0, a)
+//     }
+//     {
+//         mstore(0, a)
+//     }
+//     mstore(0, a)
+// }
diff --git a/test/libyul/yulOptimizerTests/ssaTransform/for_reassign_post.yul b/test/libyul/yulOptimizerTests/ssaTransform/for_reassign_post.yul
new file mode 100644
index 00000000..1fc075bc
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/ssaTransform/for_reassign_post.yul
@@ -0,0 +1,26 @@
+{
+    let a := mload(0)
+    for { mstore(0, a) } a { a := add(a, 3) }
+    {
+        mstore(0, a)
+    }
+    mstore(0, a)
+}
+// ----
+// ssaTransform
+// {
+//     let a_1 := mload(0)
+//     let a := a_1
+//     for {
+//         mstore(0, a_1)
+//     }
+//     a
+//     {
+//         let a_2 := add(a, 3)
+//         a := a_2
+//     }
+//     {
+//         mstore(0, a)
+//     }
+//     mstore(0, a)
+// }
diff --git a/test/libyul/yulOptimizerTests/ssaTransform/for_simple.yul b/test/libyul/yulOptimizerTests/ssaTransform/for_simple.yul
new file mode 100644
index 00000000..273d3811
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/ssaTransform/for_simple.yul
@@ -0,0 +1,47 @@
+{
+    let a := mload(0)
+    a := add(a, 1)
+    if a {
+        a := add(a, 2)
+    }
+    {
+        a := add(a, 4)
+    }
+    for { a := add(a, 3) } a { a := add(a, 6) }
+    {
+        a := add(a, 12)
+    }
+    a := add(a, 8)
+}
+// ----
+// ssaTransform
+// {
+//     let a_1 := mload(0)
+//     let a := a_1
+//     let a_2 := add(a_1, 1)
+//     a := a_2
+//     if a_2
+//     {
+//         let a_3 := add(a_2, 2)
+//         a := a_3
+//     }
+//     {
+//         let a_4 := add(a, 4)
+//         a := a_4
+//     }
+//     for {
+//         let a_5 := add(a, 3)
+//         a := a_5
+//     }
+//     a
+//     {
+//         let a_7 := add(a, 6)
+//         a := a_7
+//     }
+//     {
+//         let a_6 := add(a, 12)
+//         a := a_6
+//     }
+//     let a_8 := add(a, 8)
+//     a := a_8
+// }
diff --git a/test/libyul/yulOptimizerTests/ssaTransform/function.yul b/test/libyul/yulOptimizerTests/ssaTransform/function.yul
new file mode 100644
index 00000000..b319d12e
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/ssaTransform/function.yul
@@ -0,0 +1,23 @@
+{
+  function f(a, b) -> c, d {
+    b := add(b, a)
+    c := add(c, b)
+    d := add(d, c)
+    a := add(a, d)
+  }
+}
+// ----
+// ssaTransform
+// {
+//     function f(a, b) -> c, d
+//     {
+//         let b_1 := add(b, a)
+//         b := b_1
+//         let c_1 := add(c, b_1)
+//         c := c_1
+//         let d_1 := add(d, c_1)
+//         d := d_1
+//         let a_1 := add(a, d_1)
+//         a := a_1
+//     }
+// }
diff --git a/test/libyul/yulOptimizerTests/ssaTransform/nested.yul b/test/libyul/yulOptimizerTests/ssaTransform/nested.yul
new file mode 100644
index 00000000..55adfc37
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/ssaTransform/nested.yul
@@ -0,0 +1,32 @@
+{
+  let a := 1
+  a := 2
+  let b := 3
+  b := 4
+  {
+    // b is not reassigned here
+    a := 3
+    a := 4
+  }
+  a := add(b, a)
+}
+// ----
+// ssaTransform
+// {
+//     let a_1 := 1
+//     let a := a_1
+//     let a_2 := 2
+//     a := a_2
+//     let b_1 := 3
+//     let b := b_1
+//     let b_2 := 4
+//     b := b_2
+//     {
+//         let a_3 := 3
+//         a := a_3
+//         let a_4 := 4
+//         a := a_4
+//     }
+//     let a_5 := add(b_2, a)
+//     a := a_5
+// }
diff --git a/test/libyul/yulOptimizerTests/ssaTransform/notransform.yul b/test/libyul/yulOptimizerTests/ssaTransform/notransform.yul
new file mode 100644
index 00000000..297905c6
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/ssaTransform/notransform.yul
@@ -0,0 +1,19 @@
+{
+  let a := 1
+  // this should not be transformed
+  let b := add(a, 2)
+  let c
+  mstore(c, 0)
+  c := add(a, b)
+}
+// ----
+// ssaTransform
+// {
+//     let a := 1
+//     let b := add(a, 2)
+//     let c_1
+//     let c := c_1
+//     mstore(c_1, 0)
+//     let c_2 := add(a, b)
+//     c := c_2
+// }
diff --git a/test/libyul/yulOptimizerTests/ssaTransform/simple.yul b/test/libyul/yulOptimizerTests/ssaTransform/simple.yul
new file mode 100644
index 00000000..6dbce729
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/ssaTransform/simple.yul
@@ -0,0 +1,18 @@
+{
+  let a := 1
+  a := 2
+  a := 3
+  a := 4
+}
+// ----
+// ssaTransform
+// {
+//     let a_1 := 1
+//     let a := a_1
+//     let a_2 := 2
+//     a := a_2
+//     let a_3 := 3
+//     a := a_3
+//     let a_4 := 4
+//     a := a_4
+// }
diff --git a/test/libyul/yulOptimizerTests/ssaTransform/switch.yul b/test/libyul/yulOptimizerTests/ssaTransform/switch.yul
new file mode 100644
index 00000000..bc9b55bb
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/ssaTransform/switch.yul
@@ -0,0 +1,26 @@
+{
+    let a := mload(0)
+    // This could be more efficient:
+    // all cases could use the value of the variable from just before
+    // the switch and not just the first
+    switch a
+    case 0 { a := add(a, 4) }
+    default { a := add(a, 8) }
+    mstore(0, a)
+}
+// ----
+// ssaTransform
+// {
+//     let a_1 := mload(0)
+//     let a := a_1
+//     switch a_1
+//     case 0 {
+//         let a_2 := add(a_1, 4)
+//         a := a_2
+//     }
+//     default {
+//         let a_3 := add(a, 8)
+//         a := a_3
+//     }
+//     mstore(0, a)
+// }
diff --git a/test/libyul/yulOptimizerTests/ssaTransform/used.yul b/test/libyul/yulOptimizerTests/ssaTransform/used.yul
new file mode 100644
index 00000000..ad686ca1
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/ssaTransform/used.yul
@@ -0,0 +1,39 @@
+{
+  let a := 1
+  mstore(a, 0)
+  a := 2
+  mstore(a, 0)
+  {
+    mstore(a, 0)
+    a := 3
+    mstore(a, 0)
+    a := 4
+    mstore(a, 0)
+  }
+  mstore(a, 0)
+  a := 4
+  mstore(a, 0)
+}
+// ----
+// ssaTransform
+// {
+//     let a_1 := 1
+//     let a := a_1
+//     mstore(a_1, 0)
+//     let a_2 := 2
+//     a := a_2
+//     mstore(a_2, 0)
+//     {
+//         mstore(a_2, 0)
+//         let a_3 := 3
+//         a := a_3
+//         mstore(a_3, 0)
+//         let a_4 := 4
+//         a := a_4
+//         mstore(a_4, 0)
+//     }
+//     mstore(a, 0)
+//     let a_5 := 4
+//     a := a_5
+//     mstore(a_5, 0)
+// }