aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--libyul/optimiser/SSATransform.cpp130
-rw-r--r--libyul/optimiser/SSATransform.h98
-rw-r--r--test/libyul/YulOptimizerTest.cpp7
-rw-r--r--test/libyul/yulOptimizerTests/ssaTransform/branches.yul25
-rw-r--r--test/libyul/yulOptimizerTests/ssaTransform/for_reassign_body.yul26
-rw-r--r--test/libyul/yulOptimizerTests/ssaTransform/for_reassign_init.yul26
-rw-r--r--test/libyul/yulOptimizerTests/ssaTransform/for_reassign_post.yul26
-rw-r--r--test/libyul/yulOptimizerTests/ssaTransform/for_simple.yul47
-rw-r--r--test/libyul/yulOptimizerTests/ssaTransform/function.yul23
-rw-r--r--test/libyul/yulOptimizerTests/ssaTransform/nested.yul32
-rw-r--r--test/libyul/yulOptimizerTests/ssaTransform/notransform.yul19
-rw-r--r--test/libyul/yulOptimizerTests/ssaTransform/simple.yul18
-rw-r--r--test/libyul/yulOptimizerTests/ssaTransform/switch.yul26
-rw-r--r--test/libyul/yulOptimizerTests/ssaTransform/used.yul39
14 files changed, 542 insertions, 0 deletions
diff --git a/libyul/optimiser/SSATransform.cpp b/libyul/optimiser/SSATransform.cpp
new file mode 100644
index 00000000..9db7bd03
--- /dev/null
+++ b/libyul/optimiser/SSATransform.cpp
@@ -0,0 +1,130 @@
+/*
+ This file is part of solidity.
+
+ solidity is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ solidity is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with solidity. If not, see <http://www.gnu.org/licenses/>.
+*/
+/**
+ * Optimiser component that turns subsequent assignments to variable declarations
+ * and assignments.
+ */
+
+#include <libyul/optimiser/SSATransform.h>
+
+#include <libyul/optimiser/NameCollector.h>
+#include <libyul/optimiser/NameDispenser.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+#include <libdevcore/CommonData.h>
+
+
+using namespace std;
+using namespace dev;
+using namespace dev::yul;
+using namespace dev::solidity;
+
+void SSATransform::operator()(Identifier& _identifier)
+{
+ if (m_currentVariableValues.count(_identifier.name))
+ _identifier.name = m_currentVariableValues[_identifier.name];
+}
+
+void SSATransform::operator()(ForLoop& _for)
+{
+ // This will clear the current value in case of a reassignment inside the
+ // init part, although the new variable would still be in scope inside the whole loop.
+ // This small inefficiency is fine if we move the pre part of all for loops out
+ // of the for loop.
+ (*this)(_for.pre);
+
+ Assignments assignments;
+ assignments(_for.body);
+ assignments(_for.post);
+ for (auto const& var: assignments.names())
+ m_currentVariableValues.erase(var);
+
+ visit(*_for.condition);
+ (*this)(_for.body);
+ (*this)(_for.post);
+}
+
+
+void SSATransform::operator()(Block& _block)
+{
+ set<string> variablesToClearAtEnd;
+
+ // Creates a new variable (and returns its declaration) with value _value
+ // and replaces _value by a reference to that new variable.
+ auto replaceByNew = [&](SourceLocation _loc, string _varName, string _type, shared_ptr<Expression>& _value) -> VariableDeclaration
+ {
+ string newName = m_nameDispenser.newName(_varName);
+ m_currentVariableValues[_varName] = newName;
+ variablesToClearAtEnd.insert(_varName);
+ shared_ptr<Expression> v = make_shared<Expression>(Identifier{_loc, newName});
+ _value.swap(v);
+ return VariableDeclaration{_loc, {TypedName{_loc, std::move(newName), std::move(_type)}}, std::move(v)};
+ };
+
+ iterateReplacing(
+ _block.statements,
+ [&](Statement& _s) -> boost::optional<vector<Statement>>
+ {
+ if (_s.type() == typeid(VariableDeclaration))
+ {
+ VariableDeclaration& varDecl = boost::get<VariableDeclaration>(_s);
+ if (varDecl.value)
+ visit(*varDecl.value);
+ if (varDecl.variables.size() != 1 || !m_variablesToReplace.count(varDecl.variables.front().name))
+ return {};
+ // Replace "let a := v" by "let a_1 := v let a := v"
+ VariableDeclaration newVarDecl = replaceByNew(
+ varDecl.location,
+ varDecl.variables.front().name,
+ varDecl.variables.front().type,
+ varDecl.value
+ );
+ return vector<Statement>{std::move(newVarDecl), std::move(varDecl)};
+ }
+ else if (_s.type() == typeid(Assignment))
+ {
+ Assignment& assignment = boost::get<Assignment>(_s);
+ visit(*assignment.value);
+ if (assignment.variableNames.size() != 1)
+ return {};
+ assertThrow(m_variablesToReplace.count(assignment.variableNames.front().name), OptimizerException, "");
+ // Replace "a := v" by "let a_1 := v a := v"
+ VariableDeclaration newVarDecl = replaceByNew(
+ assignment.location,
+ assignment.variableNames.front().name,
+ {}, // TODO determine type
+ assignment.value
+ );
+ return vector<Statement>{std::move(newVarDecl), std::move(assignment)};
+ }
+ else
+ visit(_s);
+ return {};
+ }
+ );
+ for (auto const& var: variablesToClearAtEnd)
+ m_currentVariableValues.erase(var);
+}
+
+void SSATransform::run(Block& _ast, NameDispenser& _nameDispenser)
+{
+ Assignments assignments;
+ assignments(_ast);
+ SSATransform{_nameDispenser, assignments.names()}(_ast);
+}
+
diff --git a/libyul/optimiser/SSATransform.h b/libyul/optimiser/SSATransform.h
new file mode 100644
index 00000000..2adc657d
--- /dev/null
+++ b/libyul/optimiser/SSATransform.h
@@ -0,0 +1,98 @@
+/*
+ This file is part of solidity.
+
+ solidity is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ solidity is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with solidity. If not, see <http://www.gnu.org/licenses/>.
+*/
+/**
+ * Optimiser component that turns subsequent assignments to variable declarations
+ * and assignments.
+ */
+#pragma once
+
+#include <libyul/ASTDataForward.h>
+
+#include <libyul/optimiser/ASTWalker.h>
+
+#include <vector>
+
+namespace dev
+{
+namespace yul
+{
+
+class NameDispenser;
+
+/**
+ * Optimizer stage that tries to replace repeated assignments to
+ * existing variables by declarations of new variables as much as
+ * possible.
+ * The reassignments are still there, but all references to the
+ * reassigned variables are replaced by the newly declared variables.
+ *
+ * Example:
+ * {
+ * let a := 1
+ * mstore(a, 2)
+ * a := 3
+ * }
+ * is transformed to
+ * {
+ * let a_1 := 1
+ * let a := a_1
+ * mstore(a_1, 2)
+ * let a_3 := 3
+ * a := a_3
+ * }
+ *
+ * Exact semantics:
+ *
+ * For any variable a that is assigned to somewhere in the code (assignment with
+ * declaration does not count) perform the following transforms:
+ * - replace "let a := v" by "let a_1 := v let a := a_1"
+ * - replace "a := v" by "let a_1 := v a := a_1"
+ * Furthermore, always note the current variable/value assigned to a and replace each
+ * reference to a by this variable.
+ * The current value mapping is cleared for a variable a at the end of each block
+ * in which it was assigned and just after the for loop init block if it is assigned
+ * inside the for loop.
+ *
+ * After this stage, redundantAssignmentRemover is recommended to remove the unnecessary
+ * intermediate assignments.
+ *
+ * This stage provides best results if CSE is run right before it, because
+ * then it does not generate excessive amounts of variables.
+ *
+ * TODO Which transforms are required to keep this idempotent?
+ */
+class SSATransform: public ASTModifier
+{
+public:
+ void operator()(Identifier&) override;
+ void operator()(ForLoop&) override;
+ void operator()(Block& _block) override;
+
+ static void run(Block& _ast, NameDispenser& _nameDispenser);
+
+private:
+ explicit SSATransform(NameDispenser& _nameDispenser, std::set<std::string> const& _variablesToReplace):
+ m_nameDispenser(_nameDispenser), m_variablesToReplace(_variablesToReplace)
+ { }
+
+ NameDispenser& m_nameDispenser;
+ std::set<std::string> const& m_variablesToReplace;
+ std::map<std::string, std::string> m_currentVariableValues;
+};
+
+}
+}
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)
+// }
generated by cgit (git 2.34.1) at 2024-11-18 09:20:38 +0800