aboutsummaryrefslogtreecommitdiffstats
path: root/libyul
diff options
context:
space:
mode:
Diffstat (limited to 'libyul')
-rw-r--r--libyul/CMakeLists.txt2
-rw-r--r--libyul/optimiser/Metrics.cpp12
-rw-r--r--libyul/optimiser/Metrics.h14
-rw-r--r--libyul/optimiser/SSAReverser.cpp114
-rw-r--r--libyul/optimiser/SSAReverser.h74
-rw-r--r--libyul/optimiser/Suite.cpp13
6 files changed, 226 insertions, 3 deletions
diff --git a/libyul/CMakeLists.txt b/libyul/CMakeLists.txt
index 44af2fc3..259f43f8 100644
--- a/libyul/CMakeLists.txt
+++ b/libyul/CMakeLists.txt
@@ -80,6 +80,8 @@ add_library(yul
optimiser/RedundantAssignEliminator.h
optimiser/Rematerialiser.cpp
optimiser/Rematerialiser.h
+ optimiser/SSAReverser.cpp
+ optimiser/SSAReverser.h
optimiser/SSATransform.cpp
optimiser/SSATransform.h
optimiser/SSAValueTracker.cpp
diff --git a/libyul/optimiser/Metrics.cpp b/libyul/optimiser/Metrics.cpp
index df919682..e13940aa 100644
--- a/libyul/optimiser/Metrics.cpp
+++ b/libyul/optimiser/Metrics.cpp
@@ -134,3 +134,15 @@ void CodeCost::visit(Expression const& _expression)
++m_cost;
ASTWalker::visit(_expression);
}
+
+void AssignmentCounter::operator()(Assignment const& _assignment)
+{
+ for (auto const& variable: _assignment.variableNames)
+ ++m_assignmentCounters[variable.name];
+}
+
+size_t AssignmentCounter::assignmentCount(YulString _name) const
+{
+ auto it = m_assignmentCounters.find(_name);
+ return (it == m_assignmentCounters.end()) ? 0 : it->second;
+}
diff --git a/libyul/optimiser/Metrics.h b/libyul/optimiser/Metrics.h
index 03e1b62a..5364646e 100644
--- a/libyul/optimiser/Metrics.h
+++ b/libyul/optimiser/Metrics.h
@@ -77,4 +77,18 @@ private:
size_t m_cost = 0;
};
+/**
+ * Counts the number of assignments to every variable.
+ * Only works after running the Disambiguator.
+ */
+class AssignmentCounter: public ASTWalker
+{
+public:
+ using ASTWalker::operator();
+ void operator()(Assignment const& _assignment) override;
+ std::size_t assignmentCount(YulString _name) const;
+private:
+ std::map<YulString, size_t> m_assignmentCounters;
+};
+
}
diff --git a/libyul/optimiser/SSAReverser.cpp b/libyul/optimiser/SSAReverser.cpp
new file mode 100644
index 00000000..6548ebb5
--- /dev/null
+++ b/libyul/optimiser/SSAReverser.cpp
@@ -0,0 +1,114 @@
+/*
+ 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/>.
+*/
+#include <libyul/optimiser/SSAReverser.h>
+#include <libyul/optimiser/Metrics.h>
+#include <libyul/AsmData.h>
+#include <libdevcore/CommonData.h>
+
+using namespace std;
+using namespace dev;
+using namespace yul;
+
+void SSAReverser::run(Block& _block)
+{
+ AssignmentCounter assignmentCounter;
+ assignmentCounter(_block);
+ SSAReverser{assignmentCounter}(_block);
+}
+
+void SSAReverser::operator()(Block& _block)
+{
+ walkVector(_block.statements);
+ iterateReplacingWindow<2>(
+ _block.statements,
+ [&](Statement& _stmt1, Statement& _stmt2) -> boost::optional<vector<Statement>>
+ {
+ auto* varDecl = boost::get<VariableDeclaration>(&_stmt1);
+
+ if (!varDecl || varDecl->variables.size() != 1 || !varDecl->value)
+ return {};
+
+ // Replaces
+ // let a_1 := E
+ // a := a_1
+ // with
+ // a := E
+ // let a_1 := a
+ if (auto* assignment = boost::get<Assignment>(&_stmt2))
+ {
+ auto* identifier = boost::get<Identifier>(assignment->value.get());
+ if (
+ assignment->variableNames.size() == 1 &&
+ identifier &&
+ identifier->name == varDecl->variables.front().name
+ )
+ {
+ vector<Statement> result;
+ result.emplace_back(Assignment{
+ std::move(assignment->location),
+ assignment->variableNames,
+ std::move(varDecl->value)
+ });
+ result.emplace_back(VariableDeclaration{
+ std::move(varDecl->location),
+ std::move(varDecl->variables),
+ std::make_unique<Expression>(std::move(assignment->variableNames.front()))
+ });
+ return { std::move(result) };
+ }
+ }
+ // Replaces
+ // let a_1 := E
+ // let a := a_1
+ // with
+ // let a := E
+ // let a_1 := a
+ else if (auto* varDecl2 = boost::get<VariableDeclaration>(&_stmt2))
+ {
+ auto* identifier = boost::get<Identifier>(varDecl2->value.get());
+ if (
+ varDecl2->variables.size() == 1 &&
+ identifier &&
+ identifier->name == varDecl->variables.front().name && (
+ m_assignmentCounter.assignmentCount(varDecl2->variables.front().name) >
+ m_assignmentCounter.assignmentCount(varDecl->variables.front().name)
+ )
+ )
+ {
+ vector<Statement> result;
+ auto varIdentifier2 = std::make_unique<Expression>(Identifier{
+ varDecl2->variables.front().location,
+ varDecl2->variables.front().name
+ });
+ result.emplace_back(VariableDeclaration{
+ std::move(varDecl2->location),
+ std::move(varDecl2->variables),
+ std::move(varDecl->value)
+ });
+ result.emplace_back(VariableDeclaration{
+ std::move(varDecl->location),
+ std::move(varDecl->variables),
+ std::move(varIdentifier2)
+ });
+ return { std::move(result) };
+ }
+ }
+
+ return {};
+ }
+ );
+}
diff --git a/libyul/optimiser/SSAReverser.h b/libyul/optimiser/SSAReverser.h
new file mode 100644
index 00000000..67abeb56
--- /dev/null
+++ b/libyul/optimiser/SSAReverser.h
@@ -0,0 +1,74 @@
+/*
+ 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/>.
+*/
+#pragma once
+
+#include <libyul/optimiser/ASTWalker.h>
+
+namespace yul
+{
+
+class AssignmentCounter;
+
+/**
+ * Reverses the SSA transformation.
+ *
+ * In particular, the SSA transform will rewrite
+ *
+ * a := E
+ *
+ * to
+ *
+ * let a_1 := E
+ * a := a_1
+ *
+ * To undo this kind of transformation, the SSAReverser changes this back to
+ *
+ * a := E
+ * let a_1 := a
+ *
+ * Secondly, the SSA transform will rewrite
+ *
+ * let a := E
+ * to
+ *
+ * let a_1 := E
+ * let a := a_1
+ *
+ * To undo this kind of transformation, the SSAReverser changes this back to
+ *
+ * let a := E
+ * let a_1 := a
+ *
+ * After that the CSE can replace references of a_1 by references to a,
+ * after which the unused pruner can remove the declaration of a_1.
+ *
+ * Prerequisites: Disambiguator
+ *
+ */
+class SSAReverser: public ASTModifier
+{
+public:
+ using ASTModifier::operator();
+ void operator()(Block& _block) override;
+
+ static void run(Block& _block);
+private:
+ SSAReverser(AssignmentCounter const& _assignmentCounter): m_assignmentCounter(_assignmentCounter) {}
+ AssignmentCounter const& m_assignmentCounter;
+};
+
+}
diff --git a/libyul/optimiser/Suite.cpp b/libyul/optimiser/Suite.cpp
index 38c0bf49..8cf6e104 100644
--- a/libyul/optimiser/Suite.cpp
+++ b/libyul/optimiser/Suite.cpp
@@ -35,6 +35,7 @@
#include <libyul/optimiser/UnusedPruner.h>
#include <libyul/optimiser/ExpressionSimplifier.h>
#include <libyul/optimiser/CommonSubexpressionEliminator.h>
+#include <libyul/optimiser/SSAReverser.h>
#include <libyul/optimiser/SSATransform.h>
#include <libyul/optimiser/StructuralSimplifier.h>
#include <libyul/optimiser/RedundantAssignEliminator.h>
@@ -88,9 +89,10 @@ void OptimiserSuite::run(
UnusedPruner::runUntilStabilised(_dialect, ast, reservedIdentifiers);
CommonSubexpressionEliminator{_dialect}(ast);
UnusedPruner::runUntilStabilised(_dialect, ast, reservedIdentifiers);
- SSATransform::run(ast, dispenser);
- RedundantAssignEliminator::run(_dialect, ast);
- RedundantAssignEliminator::run(_dialect, ast);
+
+ SSAReverser::run(ast);
+ CommonSubexpressionEliminator{_dialect}(ast);
+ UnusedPruner::runUntilStabilised(_dialect, ast, reservedIdentifiers);
ExpressionJoiner::run(ast);
ExpressionJoiner::run(ast);
@@ -127,6 +129,11 @@ void OptimiserSuite::run(
UnusedPruner::runUntilStabilised(_dialect, ast);
ExpressionJoiner::run(ast);
UnusedPruner::runUntilStabilised(_dialect, ast);
+
+ SSAReverser::run(ast);
+ CommonSubexpressionEliminator{_dialect}(ast);
+ UnusedPruner::runUntilStabilised(_dialect, ast, reservedIdentifiers);
+
ExpressionJoiner::run(ast);
Rematerialiser::run(_dialect, ast);
UnusedPruner::runUntilStabilised(_dialect, ast);
generated by cgit v1.2.3 (git 2.25.1) at 2025-04-04 19:07:40 +0800