From 6de2d92f20d48d38797a628ee35e7615170cd63f Mon Sep 17 00:00:00 2001 From: Daniel Kirchner Date: Wed, 16 Jan 2019 11:44:45 +0100 Subject: Add SSAReverser to the yul optimiser. --- libyul/CMakeLists.txt | 2 ++ libyul/optimiser/SSAReverser.cpp | 71 ++++++++++++++++++++++++++++++++++++++++ libyul/optimiser/SSAReverser.h | 54 ++++++++++++++++++++++++++++++ libyul/optimiser/Suite.cpp | 13 ++++++-- 4 files changed, 137 insertions(+), 3 deletions(-) create mode 100644 libyul/optimiser/SSAReverser.cpp create mode 100644 libyul/optimiser/SSAReverser.h (limited to 'libyul') 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/SSAReverser.cpp b/libyul/optimiser/SSAReverser.cpp new file mode 100644 index 00000000..313a677a --- /dev/null +++ b/libyul/optimiser/SSAReverser.cpp @@ -0,0 +1,71 @@ +/* + 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 . +*/ +#include +#include +#include + +using namespace std; +using namespace dev; +using namespace yul; + +void SSAReverser::operator()(Block& _block) +{ + walkVector(_block.statements); + iterateReplacingWindow<2>( + _block.statements, + [&](Statement& _stmt1, Statement& _stmt2) -> boost::optional> + { + // Replaces + // let a_1 := E + // a := a_1 + // with + // a := E + // let a_1 := a + + auto* varDecl = boost::get(&_stmt1); + auto* assignment = boost::get(&_stmt2); + + if (!varDecl || !assignment) + return {}; + + auto* identifier = boost::get(assignment->value.get()); + + if ( + varDecl->variables.size() == 1 && + varDecl->value && + assignment->variableNames.size() == 1 && + identifier && + identifier->name == varDecl->variables.front().name + ) + { + vector 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(std::move(assignment->variableNames.front())) + }); + return { std::move(result) }; + } + return {}; + } + ); +} diff --git a/libyul/optimiser/SSAReverser.h b/libyul/optimiser/SSAReverser.h new file mode 100644 index 00000000..a4a11074 --- /dev/null +++ b/libyul/optimiser/SSAReverser.h @@ -0,0 +1,54 @@ +/* + 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 . +*/ +#pragma once + +#include + +namespace yul +{ + +/** + * Reverses the SSA transformation. + * + * In particular, the SSA transform will rewrite + * + * a := E + * + * to + * + * let a_1 := E + * a := a_1 + * + * To undo this transformation, the SSAReverser changes this back to + * + * 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: None + * + */ +class SSAReverser: public ASTModifier +{ +public: + using ASTModifier::operator(); + void operator()(Block& _block) override; +}; + +} diff --git a/libyul/optimiser/Suite.cpp b/libyul/optimiser/Suite.cpp index 38c0bf49..63931554 100644 --- a/libyul/optimiser/Suite.cpp +++ b/libyul/optimiser/Suite.cpp @@ -35,6 +35,7 @@ #include #include #include +#include #include #include #include @@ -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{}(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{}(ast); + CommonSubexpressionEliminator{_dialect}(ast); + UnusedPruner::runUntilStabilised(_dialect, ast, reservedIdentifiers); + ExpressionJoiner::run(ast); Rematerialiser::run(_dialect, ast); UnusedPruner::runUntilStabilised(_dialect, ast); -- cgit