diff options
Diffstat (limited to 'libyul')
-rw-r--r-- | libyul/optimiser/SSATransform.cpp | 130 | ||||
-rw-r--r-- | libyul/optimiser/SSATransform.h | 98 |
2 files changed, 228 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; +}; + +} +} |