diff options
Diffstat (limited to 'libyul')
| -rw-r--r-- | libyul/optimiser/CommonSubexpressionEliminator.cpp | 5 | ||||
| -rw-r--r-- | libyul/optimiser/DataFlowAnalyzer.cpp | 35 | ||||
| -rw-r--r-- | libyul/optimiser/DataFlowAnalyzer.h | 8 | ||||
| -rw-r--r-- | libyul/optimiser/Disambiguator.h | 3 | ||||
| -rw-r--r-- | libyul/optimiser/FullInliner.cpp | 31 | ||||
| -rw-r--r-- | libyul/optimiser/FullInliner.h | 6 | ||||
| -rw-r--r-- | libyul/optimiser/NameDispenser.cpp | 31 | ||||
| -rw-r--r-- | libyul/optimiser/NameDispenser.h | 26 | ||||
| -rw-r--r-- | libyul/optimiser/Rematerialiser.cpp | 9 | ||||
| -rw-r--r-- | libyul/optimiser/SSATransform.cpp | 130 | ||||
| -rw-r--r-- | libyul/optimiser/SSATransform.h | 98 |
11 files changed, 329 insertions, 53 deletions
diff --git a/libyul/optimiser/CommonSubexpressionEliminator.cpp b/libyul/optimiser/CommonSubexpressionEliminator.cpp index 23d15cad..51737097 100644 --- a/libyul/optimiser/CommonSubexpressionEliminator.cpp +++ b/libyul/optimiser/CommonSubexpressionEliminator.cpp @@ -50,8 +50,8 @@ void CommonSubexpressionEliminator::visit(Expression& _e) if (m_value.at(name)->type() == typeid(Identifier)) { string const& value = boost::get<Identifier>(*m_value.at(name)).name; - if (inScope(value)) - _e = Identifier{locationOf(_e), value}; + assertThrow(inScope(value), OptimizerException, ""); + _e = Identifier{locationOf(_e), value}; } } } @@ -61,6 +61,7 @@ void CommonSubexpressionEliminator::visit(Expression& _e) for (auto const& var: m_value) { assertThrow(var.second, OptimizerException, ""); + assertThrow(inScope(var.first), OptimizerException, ""); if (SyntacticalEqualityChecker::equal(_e, *var.second)) { _e = Identifier{locationOf(_e), var.first}; diff --git a/libyul/optimiser/DataFlowAnalyzer.cpp b/libyul/optimiser/DataFlowAnalyzer.cpp index ca1e5153..7ac42c30 100644 --- a/libyul/optimiser/DataFlowAnalyzer.cpp +++ b/libyul/optimiser/DataFlowAnalyzer.cpp @@ -84,19 +84,19 @@ void DataFlowAnalyzer::operator()(Switch& _switch) void DataFlowAnalyzer::operator()(FunctionDefinition& _fun) { - m_variableScopes.emplace_back(true); + pushScope(true); for (auto const& parameter: _fun.parameters) m_variableScopes.back().variables.insert(parameter.name); for (auto const& var: _fun.returnVariables) m_variableScopes.back().variables.insert(var.name); ASTModifier::operator()(_fun); - m_variableScopes.pop_back(); + popScope(); } void DataFlowAnalyzer::operator()(ForLoop& _for) { // Special scope handling of the pre block. - m_variableScopes.emplace_back(false); + pushScope(false); for (auto& statement: _for.pre.statements) visit(statement); @@ -110,16 +110,15 @@ void DataFlowAnalyzer::operator()(ForLoop& _for) (*this)(_for.post); clearValues(assignments.names()); - - m_variableScopes.pop_back(); + popScope(); } void DataFlowAnalyzer::operator()(Block& _block) { size_t numScopes = m_variableScopes.size(); - m_variableScopes.emplace_back(false); + pushScope(false); ASTModifier::operator()(_block); - m_variableScopes.pop_back(); + popScope(); assertThrow(numScopes == m_variableScopes.size(), OptimizerException, ""); } @@ -148,7 +147,18 @@ void DataFlowAnalyzer::handleAssignment(set<string> const& _variables, Expressio } } -void DataFlowAnalyzer::clearValues(set<string> const& _variables) +void DataFlowAnalyzer::pushScope(bool _functionScope) +{ + m_variableScopes.emplace_back(_functionScope); +} + +void DataFlowAnalyzer::popScope() +{ + clearValues(std::move(m_variableScopes.back().variables)); + m_variableScopes.pop_back(); +} + +void DataFlowAnalyzer::clearValues(set<string> _variables) { // All variables that reference variables to be cleared also have to be // cleared, but not recursively, since only the value of the original @@ -163,16 +173,15 @@ void DataFlowAnalyzer::clearValues(set<string> const& _variables) // This cannot be easily tested since the substitutions will be done // one by one on the fly, and the last line will just be add(1, 1) - set<string> variables = _variables; // Clear variables that reference variables to be cleared. - for (auto const& name: variables) + for (auto const& name: _variables) for (auto const& ref: m_referencedBy[name]) - variables.insert(ref); + _variables.insert(ref); // Clear the value and update the reference relation. - for (auto const& name: variables) + for (auto const& name: _variables) m_value.erase(name); - for (auto const& name: variables) + for (auto const& name: _variables) { for (auto const& ref: m_references[name]) m_referencedBy[ref].erase(name); diff --git a/libyul/optimiser/DataFlowAnalyzer.h b/libyul/optimiser/DataFlowAnalyzer.h index f998eadf..95671467 100644 --- a/libyul/optimiser/DataFlowAnalyzer.h +++ b/libyul/optimiser/DataFlowAnalyzer.h @@ -56,9 +56,15 @@ protected: /// Registers the assignment. void handleAssignment(std::set<std::string> const& _names, Expression* _value); + /// Creates a new inner scope. + void pushScope(bool _functionScope); + + /// Removes the innermost scope and clears all variables in it. + void popScope(); + /// Clears information about the values assigned to the given variables, /// for example at points where control flow is merged. - void clearValues(std::set<std::string> const& _names); + void clearValues(std::set<std::string> _names); /// Returns true iff the variable is in scope. bool inScope(std::string const& _variableName) const; diff --git a/libyul/optimiser/Disambiguator.h b/libyul/optimiser/Disambiguator.h index e16ebfbf..74a491ab 100644 --- a/libyul/optimiser/Disambiguator.h +++ b/libyul/optimiser/Disambiguator.h @@ -47,9 +47,8 @@ public: solidity::assembly::AsmAnalysisInfo const& _analysisInfo, std::set<std::string> const& _externallyUsedIdentifiers = {} ): - m_info(_analysisInfo), m_externallyUsedIdentifiers(_externallyUsedIdentifiers) + m_info(_analysisInfo), m_externallyUsedIdentifiers(_externallyUsedIdentifiers), m_nameDispenser(m_externallyUsedIdentifiers) { - m_nameDispenser.m_usedNames = m_externallyUsedIdentifiers; } protected: diff --git a/libyul/optimiser/FullInliner.cpp b/libyul/optimiser/FullInliner.cpp index aa069506..280d625a 100644 --- a/libyul/optimiser/FullInliner.cpp +++ b/libyul/optimiser/FullInliner.cpp @@ -40,13 +40,9 @@ using namespace dev; using namespace dev::yul; using namespace dev::solidity; -FullInliner::FullInliner(Block& _ast): - m_ast(_ast) +FullInliner::FullInliner(Block& _ast, NameDispenser& _dispenser): + m_ast(_ast), m_nameDispenser(_dispenser) { - assertThrow(m_ast.statements.size() >= 1, OptimizerException, ""); - assertThrow(m_ast.statements.front().type() == typeid(Block), OptimizerException, ""); - m_nameDispenser.m_usedNames = NameCollector(m_ast).names(); - // Determine constants SSAValueTracker tracker; tracker(m_ast); @@ -55,10 +51,11 @@ FullInliner::FullInliner(Block& _ast): m_constants.insert(ssaValue.first); map<string, size_t> references = ReferencesCounter::countReferences(m_ast); - for (size_t i = 1; i < m_ast.statements.size(); ++i) + for (auto& statement: m_ast.statements) { - assertThrow(m_ast.statements.at(i).type() == typeid(FunctionDefinition), OptimizerException, ""); - FunctionDefinition& fun = boost::get<FunctionDefinition>(m_ast.statements.at(i)); + if (statement.type() != typeid(FunctionDefinition)) + continue; + FunctionDefinition& fun = boost::get<FunctionDefinition>(statement); m_functions[fun.name] = &fun; // Always inline functions that are only called once. if (references[fun.name] == 1) @@ -69,9 +66,10 @@ FullInliner::FullInliner(Block& _ast): void FullInliner::run() { - assertThrow(m_ast.statements[0].type() == typeid(Block), OptimizerException, ""); + for (auto& statement: m_ast.statements) + if (statement.type() == typeid(Block)) + handleBlock("", boost::get<Block>(statement)); - handleBlock("", boost::get<Block>(m_ast.statements[0])); // TODO it might be good to determine a visiting order: // first handle functions that are called from many places. for (auto const& fun: m_functions) @@ -157,7 +155,7 @@ vector<Statement> InlineModifier::performInline(Statement& _statement, FunctionC // helper function to create a new variable that is supposed to model // an existing variable. auto newVariable = [&](TypedName const& _existingVariable, Expression* _value) { - string newName = m_nameDispenser.newName(function.name + "_" + _existingVariable.name); + string newName = m_nameDispenser.newName(_existingVariable.name, function.name); variableReplacements[_existingVariable.name] = newName; VariableDeclaration varDecl{_funCall.location, {{_funCall.location, newName, _existingVariable.type}}, {}}; if (_value) @@ -170,7 +168,7 @@ vector<Statement> InlineModifier::performInline(Statement& _statement, FunctionC for (auto const& var: function.returnVariables) newVariable(var, nullptr); - Statement newBody = BodyCopier(m_nameDispenser, function.name + "_", variableReplacements)(function.body); + Statement newBody = BodyCopier(m_nameDispenser, function.name, variableReplacements)(function.body); newStatements += std::move(boost::get<Block>(newBody).statements); boost::apply_visitor(GenericFallbackVisitor<Assignment, VariableDeclaration>{ @@ -203,15 +201,10 @@ vector<Statement> InlineModifier::performInline(Statement& _statement, FunctionC return newStatements; } -string InlineModifier::newName(string const& _prefix) -{ - return m_nameDispenser.newName(_prefix); -} - Statement BodyCopier::operator()(VariableDeclaration const& _varDecl) { for (auto const& var: _varDecl.variables) - m_variableReplacements[var.name] = m_nameDispenser.newName(m_varNamePrefix + var.name); + m_variableReplacements[var.name] = m_nameDispenser.newName(var.name, m_varNamePrefix); return ASTCopier::operator()(_varDecl); } diff --git a/libyul/optimiser/FullInliner.h b/libyul/optimiser/FullInliner.h index 513ffc93..5ecfb57a 100644 --- a/libyul/optimiser/FullInliner.h +++ b/libyul/optimiser/FullInliner.h @@ -71,7 +71,7 @@ class NameCollector; class FullInliner: public ASTModifier { public: - explicit FullInliner(Block& _ast); + explicit FullInliner(Block& _ast, NameDispenser& _dispenser); void run(); @@ -94,7 +94,7 @@ private: /// Variables that are constants (used for inlining heuristic) std::set<std::string> m_constants; std::map<std::string, size_t> m_functionSizes; - NameDispenser m_nameDispenser; + NameDispenser& m_nameDispenser; }; /** @@ -116,8 +116,6 @@ private: boost::optional<std::vector<Statement>> tryInlineStatement(Statement& _statement); std::vector<Statement> performInline(Statement& _statement, FunctionCall& _funCall); - std::string newName(std::string const& _prefix); - std::string m_currentFunction; FullInliner& m_driver; NameDispenser& m_nameDispenser; diff --git a/libyul/optimiser/NameDispenser.cpp b/libyul/optimiser/NameDispenser.cpp index f7385471..d3f10bc2 100644 --- a/libyul/optimiser/NameDispenser.cpp +++ b/libyul/optimiser/NameDispenser.cpp @@ -20,18 +20,43 @@ #include <libyul/optimiser/NameDispenser.h> +#include <libyul/optimiser/NameCollector.h> + +#include <libsolidity/inlineasm/AsmData.h> + using namespace std; using namespace dev; using namespace dev::yul; -string NameDispenser::newName(string const& _prefix) +NameDispenser::NameDispenser(Block const& _ast): + NameDispenser(NameCollector(_ast).names()) +{ +} + +NameDispenser::NameDispenser(set<string> _usedNames): + m_usedNames(std::move(_usedNames)) +{ +} + +string NameDispenser::newName(string const& _nameHint, string const& _context) +{ + // Shortening rules: Use a suffix of _prefix and a prefix of _context. + string prefix = _nameHint; + + if (!_context.empty()) + prefix = _context.substr(0, 10) + "_" + prefix; + + return newNameInternal(prefix); +} + +string NameDispenser::newNameInternal(string const& _nameHint) { - string name = _prefix; size_t suffix = 0; + string name = _nameHint; while (name.empty() || m_usedNames.count(name)) { suffix++; - name = _prefix + "_" + to_string(suffix); + name = _nameHint + "_" + to_string(suffix); } m_usedNames.insert(name); return name; diff --git a/libyul/optimiser/NameDispenser.h b/libyul/optimiser/NameDispenser.h index 64ec318f..5fbf5f8e 100644 --- a/libyul/optimiser/NameDispenser.h +++ b/libyul/optimiser/NameDispenser.h @@ -19,6 +19,8 @@ */ #pragma once +#include <libyul/ASTDataForward.h> + #include <set> #include <string> @@ -27,9 +29,29 @@ namespace dev namespace yul { -struct NameDispenser +/** + * Optimizer component that can be used to generate new names that + * do not conflict with existing names. + * + * Tries to keep names short and appends decimals to disambiguate. + */ +class NameDispenser { - std::string newName(std::string const& _prefix); +public: + /// Initialize the name dispenser with all the names used in the given AST. + explicit NameDispenser(Block const& _ast); + /// Initialize the name dispenser with the given used names. + explicit NameDispenser(std::set<std::string> _usedNames); + + /// @returns a currently unused name that should be similar to _nameHint + /// and prefixed by _context if present. + /// If the resulting name would be too long, trims the context at the end + /// and the name hint at the start. + std::string newName(std::string const& _nameHint, std::string const& _context = {}); + +private: + std::string newNameInternal(std::string const& _nameHint); + std::set<std::string> m_usedNames; }; diff --git a/libyul/optimiser/Rematerialiser.cpp b/libyul/optimiser/Rematerialiser.cpp index dd6653ea..a99db0b6 100644 --- a/libyul/optimiser/Rematerialiser.cpp +++ b/libyul/optimiser/Rematerialiser.cpp @@ -38,16 +38,11 @@ void Rematerialiser::visit(Expression& _e) if (m_value.count(identifier.name)) { string name = identifier.name; - bool expressionValid = true; for (auto const& ref: m_references[name]) - if (!inScope(ref)) - { - expressionValid = false; - break; - } + assertThrow(inScope(ref), OptimizerException, ""); assertThrow(m_value.at(name), OptimizerException, ""); auto const& value = *m_value.at(name); - if (expressionValid && CodeSize::codeSize(value) <= 7) + if (CodeSize::codeSize(value) <= 7) _e = (ASTCopier{}).translate(value); } } 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; +}; + +} +} |