diff options
Diffstat (limited to 'libyul/optimiser')
50 files changed, 1066 insertions, 187 deletions
diff --git a/libyul/optimiser/ASTCopier.h b/libyul/optimiser/ASTCopier.h index 4d2f18ae..7e5e9c86 100644 --- a/libyul/optimiser/ASTCopier.h +++ b/libyul/optimiser/ASTCopier.h @@ -93,10 +93,11 @@ protected: std::vector<T> translateVector(std::vector<T> const& _values); template <typename T> - std::shared_ptr<T> translate(std::shared_ptr<T> const& _v) + std::unique_ptr<T> translate(std::unique_ptr<T> const& _v) { - return _v ? std::make_shared<T>(translate(*_v)) : nullptr; + return _v ? std::make_unique<T>(translate(*_v)) : nullptr; } + Block translate(Block const& _block); Case translate(Case const& _case); Identifier translate(Identifier const& _identifier); diff --git a/libyul/optimiser/CommonSubexpressionEliminator.cpp b/libyul/optimiser/CommonSubexpressionEliminator.cpp index 9b851333..5f182eba 100644 --- a/libyul/optimiser/CommonSubexpressionEliminator.cpp +++ b/libyul/optimiser/CommonSubexpressionEliminator.cpp @@ -25,6 +25,7 @@ #include <libyul/optimiser/SyntacticalEquality.h> #include <libyul/Exceptions.h> #include <libyul/AsmData.h> +#include <libyul/Dialect.h> using namespace std; using namespace dev; @@ -32,12 +33,24 @@ using namespace yul; void CommonSubexpressionEliminator::visit(Expression& _e) { + bool descend = true; + // If this is a function call to a function that requires literal arguments, + // do not try to simplify there. + if (_e.type() == typeid(FunctionCall)) + if (BuiltinFunction const* builtin = m_dialect.builtin(boost::get<FunctionCall>(_e).functionName.name)) + if (builtin->literalArguments) + // We should not modify function arguments that have to be literals + // Note that replacing the function call entirely is fine, + // if the function call is movable. + descend = false; + // We visit the inner expression first to first simplify inner expressions, // which hopefully allows more matches. // Note that the DataFlowAnalyzer itself only has code for visiting Statements, // so this basically invokes the AST walker directly and thus post-visiting // is also fine with regards to data flow analysis. - DataFlowAnalyzer::visit(_e); + if (descend) + DataFlowAnalyzer::visit(_e); if (_e.type() == typeid(Identifier)) { @@ -61,7 +74,7 @@ void CommonSubexpressionEliminator::visit(Expression& _e) { assertThrow(var.second, OptimizerException, ""); assertThrow(inScope(var.first), OptimizerException, ""); - if (SyntacticalEqualityChecker::equal(_e, *var.second)) + if (SyntacticallyEqual{}(_e, *var.second)) { _e = Identifier{locationOf(_e), var.first}; break; diff --git a/libyul/optimiser/CommonSubexpressionEliminator.h b/libyul/optimiser/CommonSubexpressionEliminator.h index ac1ebe3a..9f416d9f 100644 --- a/libyul/optimiser/CommonSubexpressionEliminator.h +++ b/libyul/optimiser/CommonSubexpressionEliminator.h @@ -26,6 +26,8 @@ namespace yul { +struct Dialect; + /** * Optimisation stage that replaces expressions known to be the current value of a variable * in scope by a reference to that variable. @@ -34,6 +36,9 @@ namespace yul */ class CommonSubexpressionEliminator: public DataFlowAnalyzer { +public: + CommonSubexpressionEliminator(Dialect const& _dialect): DataFlowAnalyzer(_dialect) {} + protected: using ASTModifier::visit; void visit(Expression& _e) override; diff --git a/libyul/optimiser/DataFlowAnalyzer.cpp b/libyul/optimiser/DataFlowAnalyzer.cpp index c8d236dc..b4f2d1f9 100644 --- a/libyul/optimiser/DataFlowAnalyzer.cpp +++ b/libyul/optimiser/DataFlowAnalyzer.cpp @@ -51,8 +51,10 @@ void DataFlowAnalyzer::operator()(VariableDeclaration& _varDecl) for (auto const& var: _varDecl.variables) names.emplace(var.name); m_variableScopes.back().variables += names; + if (_varDecl.value) visit(*_varDecl.value); + handleAssignment(names, _varDecl.value.get()); } @@ -142,7 +144,7 @@ void DataFlowAnalyzer::handleAssignment(set<YulString> const& _variables, Expres static Expression const zero{Literal{{}, LiteralKind::Number, YulString{"0"}, {}}}; clearValues(_variables); - MovableChecker movableChecker; + MovableChecker movableChecker{m_dialect}; if (_value) movableChecker.visit(*_value); else diff --git a/libyul/optimiser/DataFlowAnalyzer.h b/libyul/optimiser/DataFlowAnalyzer.h index 4f12ff6a..5fb5db95 100644 --- a/libyul/optimiser/DataFlowAnalyzer.h +++ b/libyul/optimiser/DataFlowAnalyzer.h @@ -30,6 +30,7 @@ namespace yul { +struct Dialect; /** * Base class to perform data flow analysis during AST walks. @@ -43,6 +44,8 @@ namespace yul class DataFlowAnalyzer: public ASTModifier { public: + explicit DataFlowAnalyzer(Dialect const& _dialect): m_dialect(_dialect) {} + using ASTModifier::operator(); void operator()(Assignment& _assignment) override; void operator()(VariableDeclaration& _varDecl) override; @@ -84,6 +87,7 @@ protected: }; /// List of scopes. std::vector<Scope> m_variableScopes; + Dialect const& m_dialect; }; } diff --git a/libyul/optimiser/Disambiguator.cpp b/libyul/optimiser/Disambiguator.cpp index fda5895b..cb56ee99 100644 --- a/libyul/optimiser/Disambiguator.cpp +++ b/libyul/optimiser/Disambiguator.cpp @@ -23,6 +23,7 @@ #include <libyul/Exceptions.h> #include <libyul/AsmData.h> #include <libyul/AsmScope.h> +#include <libyul/Dialect.h> using namespace std; using namespace dev; @@ -31,7 +32,7 @@ using namespace dev::solidity; YulString Disambiguator::translateIdentifier(YulString _originalName) { - if ((m_externallyUsedIdentifiers.count(_originalName))) + if (m_dialect.builtin(_originalName) || m_externallyUsedIdentifiers.count(_originalName)) return _originalName; assertThrow(!m_scopes.empty() && m_scopes.back(), OptimizerException, ""); diff --git a/libyul/optimiser/Disambiguator.h b/libyul/optimiser/Disambiguator.h index bb83417b..ec6a0879 100644 --- a/libyul/optimiser/Disambiguator.h +++ b/libyul/optimiser/Disambiguator.h @@ -32,6 +32,7 @@ namespace yul { +struct Dialect; /** * Creates a copy of a Yul AST replacing all identifiers by unique names. @@ -40,10 +41,14 @@ class Disambiguator: public ASTCopier { public: explicit Disambiguator( + Dialect const& _dialect, AsmAnalysisInfo const& _analysisInfo, std::set<YulString> const& _externallyUsedIdentifiers = {} ): - m_info(_analysisInfo), m_externallyUsedIdentifiers(_externallyUsedIdentifiers), m_nameDispenser(m_externallyUsedIdentifiers) + m_info(_analysisInfo), + m_dialect(_dialect), + m_externallyUsedIdentifiers(_externallyUsedIdentifiers), + m_nameDispenser(_dialect, m_externallyUsedIdentifiers) { } @@ -58,6 +63,7 @@ protected: void leaveScopeInternal(Scope& _scope); AsmAnalysisInfo const& m_info; + Dialect const& m_dialect; std::set<YulString> const& m_externallyUsedIdentifiers; std::vector<Scope*> m_scopes; diff --git a/libyul/optimiser/EquivalentFunctionCombiner.cpp b/libyul/optimiser/EquivalentFunctionCombiner.cpp new file mode 100644 index 00000000..939e63d2 --- /dev/null +++ b/libyul/optimiser/EquivalentFunctionCombiner.cpp @@ -0,0 +1,41 @@ +/* + 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 combines syntactically equivalent functions. + */ + +#include <libyul/optimiser/EquivalentFunctionCombiner.h> +#include <libyul/AsmData.h> +#include <libdevcore/CommonData.h> + +using namespace std; +using namespace dev; +using namespace yul; +using namespace dev::solidity; + +void EquivalentFunctionCombiner::run(Block& _ast) +{ + EquivalentFunctionCombiner{EquivalentFunctionDetector::run(_ast)}(_ast); +} + +void EquivalentFunctionCombiner::operator()(FunctionCall& _funCall) +{ + auto it = m_duplicates.find(_funCall.functionName.name); + if (it != m_duplicates.end()) + _funCall.functionName.name = it->second->name; + ASTModifier::operator()(_funCall); +} diff --git a/libyul/optimiser/EquivalentFunctionCombiner.h b/libyul/optimiser/EquivalentFunctionCombiner.h new file mode 100644 index 00000000..0c766ded --- /dev/null +++ b/libyul/optimiser/EquivalentFunctionCombiner.h @@ -0,0 +1,49 @@ +/* + 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 combines syntactically equivalent functions. + */ +#pragma once + +#include <libyul/optimiser/ASTWalker.h> +#include <libyul/optimiser/EquivalentFunctionDetector.h> +#include <libyul/AsmDataForward.h> + +namespace yul +{ + +/** + * Optimiser component that detects syntactically equivalent functions and replaces all calls to any of them by calls + * to one particular of them. + * + * Prerequisite: Disambiguator, Function Hoister + */ +class EquivalentFunctionCombiner: public ASTModifier +{ +public: + static void run(Block& _ast); + + using ASTModifier::operator(); + void operator()(FunctionCall& _funCall) override; + +private: + EquivalentFunctionCombiner(std::map<YulString, FunctionDefinition const*> _duplicates): m_duplicates(std::move(_duplicates)) {} + std::map<YulString, FunctionDefinition const*> m_duplicates; +}; + + +} diff --git a/libyul/optimiser/EquivalentFunctionDetector.cpp b/libyul/optimiser/EquivalentFunctionDetector.cpp new file mode 100644 index 00000000..d3a697bd --- /dev/null +++ b/libyul/optimiser/EquivalentFunctionDetector.cpp @@ -0,0 +1,63 @@ +/* + 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 combines syntactically equivalent functions. + */ + +#include <libyul/optimiser/EquivalentFunctionDetector.h> +#include <libyul/optimiser/SyntacticalEquality.h> + +#include <libyul/AsmData.h> +#include <libyul/optimiser/Metrics.h> + +using namespace std; +using namespace dev; +using namespace yul; +using namespace solidity; + +void EquivalentFunctionDetector::operator()(FunctionDefinition const& _fun) +{ + RoughHeuristic heuristic(_fun); + auto& candidates = m_candidates[heuristic]; + for (auto const& candidate: candidates) + if (SyntacticallyEqual{}.statementEqual(_fun, *candidate)) + { + m_duplicates[_fun.name] = candidate; + return; + } + candidates.push_back(&_fun); +} + +bool EquivalentFunctionDetector::RoughHeuristic::operator<(EquivalentFunctionDetector::RoughHeuristic const& _rhs) const +{ + if ( + std::make_tuple(m_fun.parameters.size(), m_fun.returnVariables.size()) == + std::make_tuple(_rhs.m_fun.parameters.size(), _rhs.m_fun.returnVariables.size()) + ) + return codeSize() < _rhs.codeSize(); + else + return + std::make_tuple(m_fun.parameters.size(), m_fun.returnVariables.size()) < + std::make_tuple(_rhs.m_fun.parameters.size(), _rhs.m_fun.returnVariables.size()); +} + +size_t EquivalentFunctionDetector::RoughHeuristic::codeSize() const +{ + if (!m_codeSize) + m_codeSize = CodeSize::codeSize(m_fun.body); + return *m_codeSize; +} diff --git a/libyul/optimiser/EquivalentFunctionDetector.h b/libyul/optimiser/EquivalentFunctionDetector.h new file mode 100644 index 00000000..329fd385 --- /dev/null +++ b/libyul/optimiser/EquivalentFunctionDetector.h @@ -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 <http://www.gnu.org/licenses/>. +*/ +/** + * Optimiser component that combines syntactically equivalent functions. + */ +#pragma once + +#include <libyul/optimiser/ASTWalker.h> +#include <libyul/AsmDataForward.h> + +namespace yul +{ + +/** + * Optimiser component that detects syntactically equivalent functions. + * + * Prerequisite: Disambiguator + */ +class EquivalentFunctionDetector: public ASTWalker +{ +public: + static std::map<YulString, FunctionDefinition const*> run(Block& _block) + { + EquivalentFunctionDetector detector{}; + detector(_block); + return std::move(detector.m_duplicates); + } + + using ASTWalker::operator(); + void operator()(FunctionDefinition const& _fun) override; + +private: + EquivalentFunctionDetector() = default; + /** + * Fast heuristic to detect distinct, resp. potentially equal functions. + * + * Defines a partial order on function definitions. If two functions + * are comparable (one is "less" than the other), they are distinct. + * If not (neither is "less" than the other), they are *potentially* equal. + */ + class RoughHeuristic + { + public: + RoughHeuristic(FunctionDefinition const& _fun): m_fun(_fun) {} + bool operator<(RoughHeuristic const& _rhs) const; + private: + std::size_t codeSize() const; + FunctionDefinition const& m_fun; + mutable boost::optional<std::size_t> m_codeSize; + // In case the heuristic doesn't turn out to be good enough, we might want to define a hash function for code blocks. + }; + std::map<RoughHeuristic, std::vector<FunctionDefinition const*>> m_candidates; + std::map<YulString, FunctionDefinition const*> m_duplicates; +}; + + +} diff --git a/libyul/optimiser/ExpressionInliner.cpp b/libyul/optimiser/ExpressionInliner.cpp index 27d43ac0..858c8733 100644 --- a/libyul/optimiser/ExpressionInliner.cpp +++ b/libyul/optimiser/ExpressionInliner.cpp @@ -56,7 +56,7 @@ void ExpressionInliner::visit(Expression& _expression) bool movable = boost::algorithm::all_of( funCall.arguments, - [=](Expression const& _arg) { return MovableChecker(_arg).movable(); } + [=](Expression const& _arg) { return MovableChecker(m_dialect, _arg).movable(); } ); if (m_inlinableFunctions.count(funCall.functionName.name) && movable) { diff --git a/libyul/optimiser/ExpressionInliner.h b/libyul/optimiser/ExpressionInliner.h index 14e80c0a..e6e710f8 100644 --- a/libyul/optimiser/ExpressionInliner.h +++ b/libyul/optimiser/ExpressionInliner.h @@ -29,6 +29,7 @@ namespace yul { +struct Dialect; /** * Optimiser component that modifies an AST in place, inlining functions that can be @@ -44,8 +45,8 @@ namespace yul class ExpressionInliner: public ASTModifier { public: - ExpressionInliner(Block& _block): - m_block(_block) + ExpressionInliner(Dialect const& _dialect, Block& _block): + m_block(_block), m_dialect(_dialect) {} void run(); @@ -62,6 +63,7 @@ private: std::set<YulString> m_currentFunctions; Block& m_block; + Dialect const& m_dialect; }; diff --git a/libyul/optimiser/ExpressionJoiner.cpp b/libyul/optimiser/ExpressionJoiner.cpp index de2b5d53..02ac4e45 100644 --- a/libyul/optimiser/ExpressionJoiner.cpp +++ b/libyul/optimiser/ExpressionJoiner.cpp @@ -22,7 +22,7 @@ #include <libyul/optimiser/ExpressionJoiner.h> #include <libyul/optimiser/NameCollector.h> -#include <libyul/optimiser/Utilities.h> +#include <libyul/optimiser/OptimizerUtilities.h> #include <libyul/Exceptions.h> #include <libyul/AsmData.h> diff --git a/libyul/optimiser/ExpressionSimplifier.cpp b/libyul/optimiser/ExpressionSimplifier.cpp index cda44e8e..b26e4245 100644 --- a/libyul/optimiser/ExpressionSimplifier.cpp +++ b/libyul/optimiser/ExpressionSimplifier.cpp @@ -36,7 +36,7 @@ using namespace dev::solidity; void ExpressionSimplifier::visit(Expression& _expression) { ASTModifier::visit(_expression); - while (auto match = SimplificationRules::findFirstMatch(_expression, m_ssaValues)) + while (auto match = SimplificationRules::findFirstMatch(_expression, m_dialect, m_ssaValues)) { // Do not apply the rule if it removes non-constant parts of the expression. // TODO: The check could actually be less strict than "movable". @@ -45,15 +45,15 @@ void ExpressionSimplifier::visit(Expression& _expression) // so if the value of the variable is not movable, the expression that references // the variable still is. - if (match->removesNonConstants && !MovableChecker(_expression).movable()) + if (match->removesNonConstants && !MovableChecker(m_dialect, _expression).movable()) return; _expression = match->action().toExpression(locationOf(_expression)); } } -void ExpressionSimplifier::run(Block& _ast) +void ExpressionSimplifier::run(Dialect const& _dialect, Block& _ast) { SSAValueTracker ssaValues; ssaValues(_ast); - ExpressionSimplifier{ssaValues.values()}(_ast); + ExpressionSimplifier{_dialect, ssaValues.values()}(_ast); } diff --git a/libyul/optimiser/ExpressionSimplifier.h b/libyul/optimiser/ExpressionSimplifier.h index fe3507f8..b1122e91 100644 --- a/libyul/optimiser/ExpressionSimplifier.h +++ b/libyul/optimiser/ExpressionSimplifier.h @@ -26,6 +26,7 @@ namespace yul { +struct Dialect; /** * Applies simplification rules to all expressions. @@ -40,12 +41,13 @@ public: using ASTModifier::operator(); virtual void visit(Expression& _expression); - static void run(Block& _ast); + static void run(Dialect const& _dialect, Block& _ast); private: - explicit ExpressionSimplifier(std::map<YulString, Expression const*> _ssaValues): - m_ssaValues(std::move(_ssaValues)) + explicit ExpressionSimplifier(Dialect const& _dialect, std::map<YulString, Expression const*> _ssaValues): + m_dialect(_dialect), m_ssaValues(std::move(_ssaValues)) {} + Dialect const& m_dialect; std::map<YulString, Expression const*> m_ssaValues; }; diff --git a/libyul/optimiser/ExpressionSplitter.cpp b/libyul/optimiser/ExpressionSplitter.cpp index a3b2dc11..2f80fc32 100644 --- a/libyul/optimiser/ExpressionSplitter.cpp +++ b/libyul/optimiser/ExpressionSplitter.cpp @@ -24,6 +24,7 @@ #include <libyul/optimiser/ASTWalker.h> #include <libyul/AsmData.h> +#include <libyul/Dialect.h> #include <libdevcore/CommonData.h> @@ -43,6 +44,11 @@ void ExpressionSplitter::operator()(FunctionalInstruction& _instruction) void ExpressionSplitter::operator()(FunctionCall& _funCall) { + if (BuiltinFunction const* builtin = m_dialect.builtin(_funCall.functionName.name)) + if (builtin->literalArguments) + // We cannot outline function arguments that have to be literals + return; + for (auto& arg: _funCall.arguments | boost::adaptors::reversed) outlineExpression(arg); } @@ -100,7 +106,7 @@ void ExpressionSplitter::outlineExpression(Expression& _expr) m_statementsToPrefix.emplace_back(VariableDeclaration{ location, {{TypedName{location, var, {}}}}, - make_shared<Expression>(std::move(_expr)) + make_unique<Expression>(std::move(_expr)) }); _expr = Identifier{location, var}; } diff --git a/libyul/optimiser/ExpressionSplitter.h b/libyul/optimiser/ExpressionSplitter.h index d4d2b3f6..a72d14ba 100644 --- a/libyul/optimiser/ExpressionSplitter.h +++ b/libyul/optimiser/ExpressionSplitter.h @@ -31,6 +31,7 @@ namespace yul { class NameCollector; +struct Dialect; /** @@ -57,8 +58,8 @@ class NameCollector; class ExpressionSplitter: public ASTModifier { public: - explicit ExpressionSplitter(NameDispenser& _nameDispenser): - m_nameDispenser(_nameDispenser) + explicit ExpressionSplitter(Dialect const& _dialect, NameDispenser& _nameDispenser): + m_dialect(_dialect), m_nameDispenser(_nameDispenser) { } void operator()(FunctionalInstruction&) override; @@ -77,6 +78,7 @@ private: /// List of statements that should go in front of the currently visited AST element, /// at the statement level. std::vector<Statement> m_statementsToPrefix; + Dialect const& m_dialect; NameDispenser& m_nameDispenser; }; diff --git a/libyul/optimiser/FullInliner.cpp b/libyul/optimiser/FullInliner.cpp index 95360dc3..ca6162ec 100644 --- a/libyul/optimiser/FullInliner.cpp +++ b/libyul/optimiser/FullInliner.cpp @@ -23,7 +23,7 @@ #include <libyul/optimiser/ASTCopier.h> #include <libyul/optimiser/ASTWalker.h> #include <libyul/optimiser/NameCollector.h> -#include <libyul/optimiser/Utilities.h> +#include <libyul/optimiser/OptimizerUtilities.h> #include <libyul/optimiser/Metrics.h> #include <libyul/optimiser/SSAValueTracker.h> #include <libyul/Exceptions.h> @@ -80,9 +80,9 @@ void FullInliner::run() } } -void FullInliner::updateCodeSize(FunctionDefinition& fun) +void FullInliner::updateCodeSize(FunctionDefinition const& _fun) { - m_functionSizes[fun.name] = CodeSize::codeSize(fun.body); + m_functionSizes[_fun.name] = CodeSize::codeSize(_fun.body); } void FullInliner::handleBlock(YulString _currentFunctionName, Block& _block) @@ -100,8 +100,13 @@ bool FullInliner::shallInline(FunctionCall const& _funCall, YulString _callSite) if (!calledFunction) return false; + // Inline really, really tiny functions + size_t size = m_functionSizes.at(calledFunction->name); + if (size <= 1) + return true; + // Do not inline into already big functions. - if (m_functionSizes.at(_callSite) > 100) + if (m_functionSizes.at(_callSite) > 45) return false; if (m_singleUse.count(calledFunction->name)) @@ -119,8 +124,7 @@ bool FullInliner::shallInline(FunctionCall const& _funCall, YulString _callSite) break; } - size_t size = m_functionSizes.at(calledFunction->name); - return (size < 10 || (constantArg && size < 30)); + return (size < 6 || (constantArg && size < 12)); } void FullInliner::tentativelyUpdateCodeSize(YulString _function, YulString _callSite) @@ -177,9 +181,9 @@ vector<Statement> InlineModifier::performInline(Statement& _statement, FunctionC variableReplacements[_existingVariable.name] = newName; VariableDeclaration varDecl{_funCall.location, {{_funCall.location, newName, _existingVariable.type}}, {}}; if (_value) - varDecl.value = make_shared<Expression>(std::move(*_value)); + varDecl.value = make_unique<Expression>(std::move(*_value)); else - varDecl.value = make_shared<Expression>(zero); + varDecl.value = make_unique<Expression>(zero); newStatements.emplace_back(std::move(varDecl)); }; @@ -198,7 +202,7 @@ vector<Statement> InlineModifier::performInline(Statement& _statement, FunctionC newStatements.emplace_back(Assignment{ _assignment.location, {_assignment.variableNames[i]}, - make_shared<Expression>(Identifier{ + make_unique<Expression>(Identifier{ _assignment.location, variableReplacements.at(function->returnVariables[i].name) }) @@ -210,7 +214,7 @@ vector<Statement> InlineModifier::performInline(Statement& _statement, FunctionC newStatements.emplace_back(VariableDeclaration{ _varDecl.location, {std::move(_varDecl.variables[i])}, - make_shared<Expression>(Identifier{ + make_unique<Expression>(Identifier{ _varDecl.location, variableReplacements.at(function->returnVariables[i].name) }) @@ -228,10 +232,10 @@ Statement BodyCopier::operator()(VariableDeclaration const& _varDecl) return ASTCopier::operator()(_varDecl); } -Statement BodyCopier::operator()(FunctionDefinition const& _funDef) +Statement BodyCopier::operator()(FunctionDefinition const&) { assertThrow(false, OptimizerException, "Function hoisting has to be done before function inlining."); - return _funDef; + return {}; } YulString BodyCopier::translateIdentifier(YulString _name) diff --git a/libyul/optimiser/FullInliner.h b/libyul/optimiser/FullInliner.h index d2dd3229..32664c96 100644 --- a/libyul/optimiser/FullInliner.h +++ b/libyul/optimiser/FullInliner.h @@ -91,7 +91,7 @@ public: void tentativelyUpdateCodeSize(YulString _function, YulString _callSite); private: - void updateCodeSize(FunctionDefinition& fun); + void updateCodeSize(FunctionDefinition const& _fun); void handleBlock(YulString _currentFunctionName, Block& _block); /// The AST to be modified. The root block itself will not be modified, because diff --git a/libyul/optimiser/FunctionGrouper.cpp b/libyul/optimiser/FunctionGrouper.cpp index 02ce22cd..b9852fcd 100644 --- a/libyul/optimiser/FunctionGrouper.cpp +++ b/libyul/optimiser/FunctionGrouper.cpp @@ -33,6 +33,9 @@ using namespace dev::solidity; void FunctionGrouper::operator()(Block& _block) { + if (alreadyGrouped(_block)) + return; + vector<Statement> reordered; reordered.emplace_back(Block{_block.location, {}}); @@ -45,3 +48,15 @@ void FunctionGrouper::operator()(Block& _block) } _block.statements = std::move(reordered); } + +bool FunctionGrouper::alreadyGrouped(Block const& _block) +{ + if (_block.statements.empty()) + return false; + if (_block.statements.front().type() != typeid(Block)) + return false; + for (size_t i = 1; i < _block.statements.size(); ++i) + if (_block.statements.at(i).type() != typeid(FunctionDefinition)) + return false; + return true; +} diff --git a/libyul/optimiser/FunctionGrouper.h b/libyul/optimiser/FunctionGrouper.h index 3b3f48a7..4b6abf76 100644 --- a/libyul/optimiser/FunctionGrouper.h +++ b/libyul/optimiser/FunctionGrouper.h @@ -38,6 +38,9 @@ class FunctionGrouper { public: void operator()(Block& _block); + +private: + bool alreadyGrouped(Block const& _block); }; } diff --git a/libyul/optimiser/FunctionHoister.cpp b/libyul/optimiser/FunctionHoister.cpp index bd1c781b..4863b94d 100644 --- a/libyul/optimiser/FunctionHoister.cpp +++ b/libyul/optimiser/FunctionHoister.cpp @@ -21,7 +21,7 @@ */ #include <libyul/optimiser/FunctionHoister.h> -#include <libyul/optimiser/Utilities.h> +#include <libyul/optimiser/OptimizerUtilities.h> #include <libyul/AsmData.h> #include <libdevcore/CommonData.h> diff --git a/libyul/optimiser/InlinableExpressionFunctionFinder.cpp b/libyul/optimiser/InlinableExpressionFunctionFinder.cpp index 662cdf25..f57faa7c 100644 --- a/libyul/optimiser/InlinableExpressionFunctionFinder.cpp +++ b/libyul/optimiser/InlinableExpressionFunctionFinder.cpp @@ -20,7 +20,7 @@ #include <libyul/optimiser/InlinableExpressionFunctionFinder.h> -#include <libyul/optimiser/Utilities.h> +#include <libyul/optimiser/OptimizerUtilities.h> #include <libyul/AsmData.h> using namespace std; diff --git a/libyul/optimiser/Metrics.cpp b/libyul/optimiser/Metrics.cpp index 8fc9476e..e13940aa 100644 --- a/libyul/optimiser/Metrics.cpp +++ b/libyul/optimiser/Metrics.cpp @@ -21,7 +21,13 @@ #include <libyul/optimiser/Metrics.h> #include <libyul/AsmData.h> +#include <libyul/Exceptions.h> +#include <libevmasm/Instruction.h> + +#include <libdevcore/Visitor.h> + +using namespace std; using namespace dev; using namespace yul; @@ -50,13 +56,93 @@ void CodeSize::visit(Statement const& _statement) { if (_statement.type() == typeid(FunctionDefinition)) return; + else if (!( + _statement.type() == typeid(Block) || + _statement.type() == typeid(ExpressionStatement) || + _statement.type() == typeid(Assignment) || + _statement.type() == typeid(VariableDeclaration) + )) + ++m_size; - ++m_size; ASTWalker::visit(_statement); } void CodeSize::visit(Expression const& _expression) { - ++m_size; + if (_expression.type() != typeid(Identifier)) + ++m_size; + ASTWalker::visit(_expression); +} + + +size_t CodeCost::codeCost(Expression const& _expr) +{ + CodeCost cc; + cc.visit(_expr); + return cc.m_cost; +} + + +void CodeCost::operator()(FunctionCall const& _funCall) +{ + yulAssert(m_cost >= 1, "Should assign cost one in visit(Expression)."); + m_cost += 49; + ASTWalker::operator()(_funCall); +} + +void CodeCost::operator()(FunctionalInstruction const& _instr) +{ + using namespace dev::solidity; + yulAssert(m_cost >= 1, "Should assign cost one in visit(Expression)."); + Tier gasPriceTier = instructionInfo(_instr.instruction).gasPriceTier; + if (gasPriceTier < Tier::VeryLow) + m_cost -= 1; + else if (gasPriceTier < Tier::High) + m_cost += 1; + else + m_cost += 49; + ASTWalker::operator()(_instr); +} +void CodeCost::operator()(Literal const& _literal) +{ + yulAssert(m_cost >= 1, "Should assign cost one in visit(Expression)."); + size_t cost = 0; + switch (_literal.kind) + { + case LiteralKind::Boolean: + break; + case LiteralKind::Number: + for (u256 n = u256(_literal.value.str()); n >= 0x100; n >>= 8) + cost++; + break; + case LiteralKind::String: + cost = _literal.value.str().size(); + break; + } + + m_cost += cost; +} + +void CodeCost::visit(Statement const& _statement) +{ + ++m_cost; + ASTWalker::visit(_statement); +} + +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 d26ecbd9..5364646e 100644 --- a/libyul/optimiser/Metrics.h +++ b/libyul/optimiser/Metrics.h @@ -30,6 +30,13 @@ namespace yul * More specifically, the number of AST nodes. * Ignores function definitions while traversing the AST. * If you want to know the size of a function, you have to invoke this on its body. + * + * As an exception, the following AST elements have a cost of zero: + * - expression statement (only the expression inside has a cost) + * - block (only the statements inside have a cost) + * - variable references + * - variable declarations (only the right hand side has a cost) + * - assignments (only the value has a cost) */ class CodeSize: public ASTWalker { @@ -39,6 +46,8 @@ public: static size_t codeSize(Block const& _block); private: + CodeSize() {} + void visit(Statement const& _statement) override; void visit(Expression const& _expression) override; @@ -46,4 +55,40 @@ private: size_t m_size = 0; }; +/** + * Very rough cost that takes the size and execution cost of code into account. + * The cost per AST element is one, except for literals where it is the byte size. + * Function calls cost 50. Instructions cost 0 for 3 or less gas (same as DUP), + * 2 for up to 10 and 50 otherwise. + */ +class CodeCost: public ASTWalker +{ +public: + static size_t codeCost(Expression const& _expression); + +private: + void operator()(FunctionCall const& _funCall) override; + void operator()(FunctionalInstruction const& _instr) override; + void operator()(Literal const& _literal) override; + void visit(Statement const& _statement) override; + void visit(Expression const& _expression) override; + +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/NameDispenser.cpp b/libyul/optimiser/NameDispenser.cpp index e7cdc60f..172e6907 100644 --- a/libyul/optimiser/NameDispenser.cpp +++ b/libyul/optimiser/NameDispenser.cpp @@ -22,17 +22,19 @@ #include <libyul/optimiser/NameCollector.h> #include <libyul/AsmData.h> +#include <libyul/Dialect.h> using namespace std; using namespace dev; using namespace yul; -NameDispenser::NameDispenser(Block const& _ast): - NameDispenser(NameCollector(_ast).names()) +NameDispenser::NameDispenser(Dialect const& _dialect, Block const& _ast): + NameDispenser(_dialect, NameCollector(_ast).names()) { } -NameDispenser::NameDispenser(set<YulString> _usedNames): +NameDispenser::NameDispenser(Dialect const& _dialect, set<YulString> _usedNames): + m_dialect(_dialect), m_usedNames(std::move(_usedNames)) { } @@ -51,7 +53,7 @@ YulString NameDispenser::newName(YulString _nameHint, YulString _context) YulString NameDispenser::newNameInternal(YulString _nameHint) { YulString name = _nameHint; - while (name.empty() || m_usedNames.count(name)) + while (name.empty() || m_usedNames.count(name) || m_dialect.builtin(name)) { m_counter++; name = YulString(_nameHint.str() + "_" + to_string(m_counter)); diff --git a/libyul/optimiser/NameDispenser.h b/libyul/optimiser/NameDispenser.h index 664a5265..719743e6 100644 --- a/libyul/optimiser/NameDispenser.h +++ b/libyul/optimiser/NameDispenser.h @@ -27,6 +27,7 @@ namespace yul { +struct Dialect; /** * Optimizer component that can be used to generate new names that @@ -38,9 +39,9 @@ class NameDispenser { public: /// Initialize the name dispenser with all the names used in the given AST. - explicit NameDispenser(Block const& _ast); + explicit NameDispenser(Dialect const& _dialect, Block const& _ast); /// Initialize the name dispenser with the given used names. - explicit NameDispenser(std::set<YulString> _usedNames); + explicit NameDispenser(Dialect const& _dialect, std::set<YulString> _usedNames); /// @returns a currently unused name that should be similar to _nameHint /// and prefixed by _context if present. @@ -51,6 +52,7 @@ public: private: YulString newNameInternal(YulString _nameHint); + Dialect const& m_dialect; std::set<YulString> m_usedNames; size_t m_counter = 0; }; diff --git a/libyul/optimiser/Utilities.cpp b/libyul/optimiser/OptimizerUtilities.cpp index b3b580d5..f9571a4c 100644 --- a/libyul/optimiser/Utilities.cpp +++ b/libyul/optimiser/OptimizerUtilities.cpp @@ -1,4 +1,4 @@ -/*( +/* This file is part of solidity. solidity is free software: you can redistribute it and/or modify @@ -18,10 +18,9 @@ * Some useful snippets for the optimiser. */ -#include <libyul/optimiser/Utilities.h> +#include <libyul/optimiser/OptimizerUtilities.h> #include <libyul/AsmData.h> -#include <libyul/Exceptions.h> #include <libdevcore/CommonData.h> @@ -38,11 +37,3 @@ void yul::removeEmptyBlocks(Block& _block) }; boost::range::remove_erase_if(_block.statements, isEmptyBlock); } - -u256 yul::valueOfNumberLiteral(Literal const& _literal) -{ - assertThrow(_literal.kind == LiteralKind::Number, OptimizerException, ""); - std::string const& literalString = _literal.value.str(); - assertThrow(isValidDecimal(literalString) || isValidHex(literalString), OptimizerException, ""); - return u256(literalString); -} diff --git a/libyul/optimiser/Utilities.h b/libyul/optimiser/OptimizerUtilities.h index 1cfff62b..449a1bc0 100644 --- a/libyul/optimiser/Utilities.h +++ b/libyul/optimiser/OptimizerUtilities.h @@ -29,6 +29,4 @@ namespace yul /// Removes statements that are just empty blocks (non-recursive). void removeEmptyBlocks(Block& _block); -dev::u256 valueOfNumberLiteral(Literal const& _literal); - } diff --git a/libyul/optimiser/RedundantAssignEliminator.cpp b/libyul/optimiser/RedundantAssignEliminator.cpp index 7b18e8ca..f6d7676f 100644 --- a/libyul/optimiser/RedundantAssignEliminator.cpp +++ b/libyul/optimiser/RedundantAssignEliminator.cpp @@ -150,9 +150,9 @@ void RedundantAssignEliminator::operator()(Block const& _block) ASTWalker::operator()(_block); } -void RedundantAssignEliminator::run(Block& _ast) +void RedundantAssignEliminator::run(Dialect const& _dialect, Block& _ast) { - RedundantAssignEliminator rae; + RedundantAssignEliminator rae{_dialect}; rae(_ast); AssignmentRemover remover{rae.m_assignmentsToRemove}; @@ -211,7 +211,7 @@ void RedundantAssignEliminator::finalize(YulString _variable) for (auto& assignment: m_assignments[_variable]) { assertThrow(assignment.second != State::Undecided, OptimizerException, ""); - if (assignment.second == State{State::Unused} && MovableChecker{*assignment.first->value}.movable()) + if (assignment.second == State{State::Unused} && MovableChecker{*m_dialect, *assignment.first->value}.movable()) // TODO the only point where we actually need this // to be a set is for the for loop m_assignmentsToRemove.insert(assignment.first); diff --git a/libyul/optimiser/RedundantAssignEliminator.h b/libyul/optimiser/RedundantAssignEliminator.h index 4f82e7a2..2f4dd380 100644 --- a/libyul/optimiser/RedundantAssignEliminator.h +++ b/libyul/optimiser/RedundantAssignEliminator.h @@ -28,6 +28,7 @@ namespace yul { +struct Dialect; /** * Optimiser component that removes assignments to variables that are not used @@ -98,6 +99,7 @@ namespace yul class RedundantAssignEliminator: public ASTWalker { public: + explicit RedundantAssignEliminator(Dialect const& _dialect): m_dialect(&_dialect) {} RedundantAssignEliminator(RedundantAssignEliminator const&) = default; RedundantAssignEliminator& operator=(RedundantAssignEliminator const&) = default; RedundantAssignEliminator(RedundantAssignEliminator&&) = default; @@ -112,7 +114,7 @@ public: void operator()(ForLoop const&) override; void operator()(Block const& _block) override; - static void run(Block& _ast); + static void run(Dialect const& _dialect, Block& _ast); private: RedundantAssignEliminator() = default; @@ -167,6 +169,7 @@ private: void changeUndecidedTo(YulString _variable, State _newState); void finalize(YulString _variable); + Dialect const* m_dialect; std::set<YulString> m_declaredVariables; // TODO check that this does not cause nondeterminism! // This could also be a pseudo-map from state to assignment. diff --git a/libyul/optimiser/Rematerialiser.cpp b/libyul/optimiser/Rematerialiser.cpp index 4180bfc3..56f6e99c 100644 --- a/libyul/optimiser/Rematerialiser.cpp +++ b/libyul/optimiser/Rematerialiser.cpp @@ -22,6 +22,7 @@ #include <libyul/optimiser/Metrics.h> #include <libyul/optimiser/ASTCopier.h> +#include <libyul/optimiser/NameCollector.h> #include <libyul/Exceptions.h> #include <libyul/AsmData.h> @@ -29,6 +30,17 @@ using namespace std; using namespace dev; using namespace yul; +void Rematerialiser::run(Dialect const& _dialect, Block& _ast) +{ + Rematerialiser{_dialect, _ast}(_ast); +} + +Rematerialiser::Rematerialiser(Dialect const& _dialect, Block& _ast): + DataFlowAnalyzer(_dialect), + m_referenceCounts(ReferencesCounter::countReferences(_ast)) +{ +} + void Rematerialiser::visit(Expression& _e) { if (_e.type() == typeid(Identifier)) @@ -37,12 +49,21 @@ void Rematerialiser::visit(Expression& _e) if (m_value.count(identifier.name)) { YulString name = identifier.name; - for (auto const& ref: m_references[name]) - assertThrow(inScope(ref), OptimizerException, ""); assertThrow(m_value.at(name), OptimizerException, ""); auto const& value = *m_value.at(name); - if (CodeSize::codeSize(value) <= 7) + size_t refs = m_referenceCounts[name]; + size_t cost = CodeCost::codeCost(value); + if (refs <= 1 || cost == 0 || (refs <= 5 && cost <= 1)) + { + assertThrow(m_referenceCounts[name] > 0, OptimizerException, ""); + for (auto const& ref: m_references[name]) + assertThrow(inScope(ref), OptimizerException, ""); + // update reference counts + m_referenceCounts[name]--; + for (auto const& ref: ReferencesCounter::countReferences(value)) + m_referenceCounts[ref.first] += ref.second; _e = (ASTCopier{}).translate(value); + } } } DataFlowAnalyzer::visit(_e); diff --git a/libyul/optimiser/Rematerialiser.h b/libyul/optimiser/Rematerialiser.h index b3841519..731697c8 100644 --- a/libyul/optimiser/Rematerialiser.h +++ b/libyul/optimiser/Rematerialiser.h @@ -26,16 +26,27 @@ namespace yul { /** - * Optimisation stage that replaces variables by their most recently assigned expressions. + * Optimisation stage that replaces variables by their most recently assigned expressions, + * but only if the expression is movable and one of the following holds: + * - the variable is referenced exactly once + * - the value is extremely cheap ("cost" of zero like ``caller()``) + * - the variable is referenced at most 5 times and the value is rather cheap + * ("cost" of at most 1 like a constant up to 0xff) * * Prerequisite: Disambiguator */ class Rematerialiser: public DataFlowAnalyzer { +public: + static void run(Dialect const& _dialect, Block& _ast); + protected: + Rematerialiser(Dialect const& _dialect, Block& _ast); + using ASTModifier::visit; void visit(Expression& _e) override; + std::map<YulString, size_t> m_referenceCounts; }; } 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/SSATransform.cpp b/libyul/optimiser/SSATransform.cpp index 928c0859..33c875b5 100644 --- a/libyul/optimiser/SSATransform.cpp +++ b/libyul/optimiser/SSATransform.cpp @@ -66,12 +66,13 @@ void SSATransform::operator()(Block& _block) // 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, YulString _varName, YulString _type, shared_ptr<Expression>& _value) -> VariableDeclaration + + auto replaceByNew = [&](SourceLocation _loc, YulString _varName, YulString _type, unique_ptr<Expression>& _value) -> VariableDeclaration { YulString newName = m_nameDispenser.newName(_varName); m_currentVariableValues[_varName] = newName; variablesToClearAtEnd.emplace(_varName); - shared_ptr<Expression> v = make_shared<Expression>(Identifier{_loc, newName}); + unique_ptr<Expression> v = make_unique<Expression>(Identifier{_loc, newName}); _value.swap(v); return VariableDeclaration{_loc, {TypedName{_loc, std::move(newName), std::move(_type)}}, std::move(v)}; }; @@ -87,14 +88,16 @@ void SSATransform::operator()(Block& _block) 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( + vector<Statement> v; + // Replace "let a := v" by "let a_1 := v let a := a_1" + v.emplace_back(replaceByNew( varDecl.location, varDecl.variables.front().name, varDecl.variables.front().type, varDecl.value - ); - return vector<Statement>{std::move(newVarDecl), std::move(varDecl)}; + )); + v.emplace_back(move(varDecl)); + return v; } else if (_s.type() == typeid(Assignment)) { @@ -103,14 +106,16 @@ void SSATransform::operator()(Block& _block) if (assignment.variableNames.size() != 1) return {}; assertThrow(m_variablesToReplace.count(assignment.variableNames.front().name), OptimizerException, ""); + vector<Statement> v; // Replace "a := v" by "let a_1 := v a := v" - VariableDeclaration newVarDecl = replaceByNew( + v.emplace_back(replaceByNew( assignment.location, assignment.variableNames.front().name, {}, // TODO determine type assignment.value - ); - return vector<Statement>{std::move(newVarDecl), std::move(assignment)}; + )); + v.emplace_back(move(assignment)); + return v; } else visit(_s); diff --git a/libyul/optimiser/Semantics.cpp b/libyul/optimiser/Semantics.cpp index 91bb2709..7edf97d7 100644 --- a/libyul/optimiser/Semantics.cpp +++ b/libyul/optimiser/Semantics.cpp @@ -22,6 +22,7 @@ #include <libyul/Exceptions.h> #include <libyul/AsmData.h> +#include <libyul/Dialect.h> #include <libevmasm/SemanticInformation.h> @@ -31,7 +32,13 @@ using namespace std; using namespace dev; using namespace yul; -MovableChecker::MovableChecker(Expression const& _expression) +MovableChecker::MovableChecker(Dialect const& _dialect): + m_dialect(_dialect) +{ +} + +MovableChecker::MovableChecker(Dialect const& _dialect, Expression const& _expression): + MovableChecker(_dialect) { visit(_expression); } @@ -50,8 +57,14 @@ void MovableChecker::operator()(FunctionalInstruction const& _instr) ASTWalker::operator()(_instr); } -void MovableChecker::operator()(FunctionCall const&) +void MovableChecker::operator()(FunctionCall const& _functionCall) { + if (BuiltinFunction const* f = m_dialect.builtin(_functionCall.functionName.name)) + if (f->movable) + { + ASTWalker::operator()(_functionCall); + return; + } m_movable = false; } diff --git a/libyul/optimiser/Semantics.h b/libyul/optimiser/Semantics.h index 70c50806..a81a489f 100644 --- a/libyul/optimiser/Semantics.h +++ b/libyul/optimiser/Semantics.h @@ -26,6 +26,7 @@ namespace yul { +struct Dialect; /** * Specific AST walker that determines whether an expression is movable. @@ -33,8 +34,8 @@ namespace yul class MovableChecker: public ASTWalker { public: - MovableChecker() = default; - explicit MovableChecker(Expression const& _expression); + explicit MovableChecker(Dialect const& _dialect); + MovableChecker(Dialect const& _dialect, Expression const& _expression); void operator()(Identifier const& _identifier) override; void operator()(FunctionalInstruction const& _functionalInstruction) override; @@ -48,6 +49,7 @@ public: std::set<YulString> const& referencedVariables() const { return m_variableReferences; } private: + Dialect const& m_dialect; /// Which variables the current expression references. std::set<YulString> m_variableReferences; /// Is the current expression movable or not. diff --git a/libyul/optimiser/SimplificationRules.cpp b/libyul/optimiser/SimplificationRules.cpp index 45b0ca2c..1b620b64 100644 --- a/libyul/optimiser/SimplificationRules.cpp +++ b/libyul/optimiser/SimplificationRules.cpp @@ -20,11 +20,11 @@ #include <libyul/optimiser/SimplificationRules.h> -#include <libyul/optimiser/Utilities.h> #include <libyul/optimiser/ASTCopier.h> #include <libyul/optimiser/Semantics.h> #include <libyul/optimiser/SyntacticalEquality.h> #include <libyul/AsmData.h> +#include <libyul/Utilities.h> #include <libevmasm/RuleList.h> @@ -36,6 +36,7 @@ using namespace yul; SimplificationRule<Pattern> const* SimplificationRules::findFirstMatch( Expression const& _expr, + Dialect const& _dialect, map<YulString, Expression const*> const& _ssaValues ) { @@ -49,7 +50,7 @@ SimplificationRule<Pattern> const* SimplificationRules::findFirstMatch( for (auto const& rule: rules.m_rules[uint8_t(instruction.instruction)]) { rules.resetMatchGroups(); - if (rule.pattern.matches(_expr, _ssaValues)) + if (rule.pattern.matches(_expr, _dialect, _ssaValues)) return &rule; } return nullptr; @@ -104,7 +105,11 @@ void Pattern::setMatchGroup(unsigned _group, map<unsigned, Expression const*>& _ m_matchGroups = &_matchGroups; } -bool Pattern::matches(Expression const& _expr, map<YulString, Expression const*> const& _ssaValues) const +bool Pattern::matches( + Expression const& _expr, + Dialect const& _dialect, + map<YulString, Expression const*> const& _ssaValues +) const { Expression const* expr = &_expr; @@ -139,7 +144,7 @@ bool Pattern::matches(Expression const& _expr, map<YulString, Expression const*> return false; assertThrow(m_arguments.size() == instr.arguments.size(), OptimizerException, ""); for (size_t i = 0; i < m_arguments.size(); ++i) - if (!m_arguments[i].matches(instr.arguments.at(i), _ssaValues)) + if (!m_arguments[i].matches(instr.arguments.at(i), _dialect, _ssaValues)) return false; } else @@ -166,8 +171,8 @@ bool Pattern::matches(Expression const& _expr, map<YulString, Expression const*> Expression const* firstMatch = (*m_matchGroups)[m_matchGroup]; assertThrow(firstMatch, OptimizerException, "Match set but to null."); return - SyntacticalEqualityChecker::equal(*firstMatch, _expr) && - MovableChecker(_expr).movable(); + SyntacticallyEqual{}(*firstMatch, _expr) && + MovableChecker(_dialect, _expr).movable(); } else if (m_kind == PatternKind::Any) (*m_matchGroups)[m_matchGroup] = &_expr; diff --git a/libyul/optimiser/SimplificationRules.h b/libyul/optimiser/SimplificationRules.h index 16aaba04..8213a185 100644 --- a/libyul/optimiser/SimplificationRules.h +++ b/libyul/optimiser/SimplificationRules.h @@ -33,7 +33,7 @@ namespace yul { - +struct Dialect; class Pattern; /** @@ -49,6 +49,7 @@ public: /// @param _ssaValues values of variables that are assigned exactly once. static SimplificationRule<Pattern> const* findFirstMatch( Expression const& _expr, + Dialect const& _dialect, std::map<YulString, Expression const*> const& _ssaValues ); @@ -93,7 +94,11 @@ public: /// same expression equivalence class. void setMatchGroup(unsigned _group, std::map<unsigned, Expression const*>& _matchGroups); unsigned matchGroup() const { return m_matchGroup; } - bool matches(Expression const& _expr, std::map<YulString, Expression const*> const& _ssaValues) const; + bool matches( + Expression const& _expr, + Dialect const& _dialect, + std::map<YulString, Expression const*> const& _ssaValues + ) const; std::vector<Pattern> arguments() const { return m_arguments; } diff --git a/libyul/optimiser/StructuralSimplifier.cpp b/libyul/optimiser/StructuralSimplifier.cpp index bdf4cb2a..727775cb 100644 --- a/libyul/optimiser/StructuralSimplifier.cpp +++ b/libyul/optimiser/StructuralSimplifier.cpp @@ -16,8 +16,8 @@ */ #include <libyul/optimiser/StructuralSimplifier.h> #include <libyul/optimiser/Semantics.h> -#include <libyul/optimiser/Utilities.h> #include <libyul/AsmData.h> +#include <libyul/Utilities.h> #include <libdevcore/CommonData.h> #include <libdevcore/Visitor.h> @@ -51,7 +51,11 @@ void StructuralSimplifier::simplify(std::vector<yul::Statement>& _statements) GenericFallbackReturnsVisitor<OptionalStatements, If, Switch, ForLoop> const visitor( [&](If& _ifStmt) -> OptionalStatements { if (_ifStmt.body.statements.empty()) - return {{makePopExpressionStatement(_ifStmt.location, std::move(*_ifStmt.condition))}}; + { + OptionalStatements s = vector<Statement>{}; + s->emplace_back(makePopExpressionStatement(_ifStmt.location, std::move(*_ifStmt.condition))); + return s; + } if (expressionAlwaysTrue(*_ifStmt.condition)) return {std::move(_ifStmt.body.statements)}; else if (expressionAlwaysFalse(*_ifStmt.condition)) @@ -64,18 +68,24 @@ void StructuralSimplifier::simplify(std::vector<yul::Statement>& _statements) auto& switchCase = _switchStmt.cases.front(); auto loc = locationOf(*_switchStmt.expression); if (switchCase.value) - return {{If{ + { + OptionalStatements s = vector<Statement>{}; + s->emplace_back(If{ std::move(_switchStmt.location), - make_shared<Expression>(FunctionalInstruction{ + make_unique<Expression>(FunctionalInstruction{ std::move(loc), solidity::Instruction::EQ, {std::move(*switchCase.value), std::move(*_switchStmt.expression)} - }), std::move(switchCase.body)}}}; + }), std::move(switchCase.body)}); + return s; + } else - return {{ - makePopExpressionStatement(loc, std::move(*_switchStmt.expression)), - std::move(switchCase.body) - }}; + { + OptionalStatements s = vector<Statement>{}; + s->emplace_back(makePopExpressionStatement(loc, std::move(*_switchStmt.expression))); + s->emplace_back(std::move(switchCase.body)); + return s; + } } else return {}; diff --git a/libyul/optimiser/StructuralSimplifier.h b/libyul/optimiser/StructuralSimplifier.h index bbd8e005..d68a9620 100644 --- a/libyul/optimiser/StructuralSimplifier.h +++ b/libyul/optimiser/StructuralSimplifier.h @@ -38,6 +38,8 @@ namespace yul class StructuralSimplifier: public DataFlowAnalyzer { public: + explicit StructuralSimplifier(Dialect const& _dialect): DataFlowAnalyzer(_dialect) {} + using DataFlowAnalyzer::operator(); void operator()(Block& _block) override; private: diff --git a/libyul/optimiser/Suite.cpp b/libyul/optimiser/Suite.cpp index bfba8dfc..8cf6e104 100644 --- a/libyul/optimiser/Suite.cpp +++ b/libyul/optimiser/Suite.cpp @@ -22,8 +22,10 @@ #include <libyul/optimiser/Disambiguator.h> #include <libyul/optimiser/VarDeclInitializer.h> +#include <libyul/optimiser/BlockFlattener.h> #include <libyul/optimiser/FunctionGrouper.h> #include <libyul/optimiser/FunctionHoister.h> +#include <libyul/optimiser/EquivalentFunctionCombiner.h> #include <libyul/optimiser/ExpressionSplitter.h> #include <libyul/optimiser/ExpressionJoiner.h> #include <libyul/optimiser/ExpressionInliner.h> @@ -33,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> @@ -47,6 +50,7 @@ using namespace dev; using namespace yul; void OptimiserSuite::run( + Dialect const& _dialect, Block& _ast, AsmAnalysisInfo const& _analysisInfo, set<YulString> const& _externallyUsedIdentifiers @@ -54,66 +58,85 @@ void OptimiserSuite::run( { set<YulString> reservedIdentifiers = _externallyUsedIdentifiers; - Block ast = boost::get<Block>(Disambiguator(_analysisInfo, reservedIdentifiers)(_ast)); + Block ast = boost::get<Block>(Disambiguator(_dialect, _analysisInfo, reservedIdentifiers)(_ast)); (VarDeclInitializer{})(ast); (FunctionHoister{})(ast); + (BlockFlattener{})(ast); (FunctionGrouper{})(ast); + EquivalentFunctionCombiner::run(ast); + UnusedPruner::runUntilStabilised(_dialect, ast, reservedIdentifiers); (ForLoopInitRewriter{})(ast); - StructuralSimplifier{}(ast); + (BlockFlattener{})(ast); + StructuralSimplifier{_dialect}(ast); - NameDispenser dispenser{ast}; + NameDispenser dispenser{_dialect, ast}; for (size_t i = 0; i < 4; i++) { - ExpressionSplitter{dispenser}(ast); + ExpressionSplitter{_dialect, dispenser}(ast); SSATransform::run(ast, dispenser); - RedundantAssignEliminator::run(ast); - RedundantAssignEliminator::run(ast); + RedundantAssignEliminator::run(_dialect, ast); + RedundantAssignEliminator::run(_dialect, ast); - CommonSubexpressionEliminator{}(ast); - ExpressionSimplifier::run(ast); - StructuralSimplifier{}(ast); + CommonSubexpressionEliminator{_dialect}(ast); + ExpressionSimplifier::run(_dialect, ast); + StructuralSimplifier{_dialect}(ast); + (BlockFlattener{})(ast); SSATransform::run(ast, dispenser); - RedundantAssignEliminator::run(ast); - RedundantAssignEliminator::run(ast); - UnusedPruner::runUntilStabilised(ast, reservedIdentifiers); - CommonSubexpressionEliminator{}(ast); - UnusedPruner::runUntilStabilised(ast, reservedIdentifiers); - SSATransform::run(ast, dispenser); - RedundantAssignEliminator::run(ast); - RedundantAssignEliminator::run(ast); + RedundantAssignEliminator::run(_dialect, ast); + RedundantAssignEliminator::run(_dialect, ast); + UnusedPruner::runUntilStabilised(_dialect, ast, reservedIdentifiers); + CommonSubexpressionEliminator{_dialect}(ast); + UnusedPruner::runUntilStabilised(_dialect, ast, reservedIdentifiers); + + SSAReverser::run(ast); + CommonSubexpressionEliminator{_dialect}(ast); + UnusedPruner::runUntilStabilised(_dialect, ast, reservedIdentifiers); ExpressionJoiner::run(ast); ExpressionJoiner::run(ast); - ExpressionInliner(ast).run(); - UnusedPruner::runUntilStabilised(ast); + ExpressionInliner(_dialect, ast).run(); + UnusedPruner::runUntilStabilised(_dialect, ast); - ExpressionSplitter{dispenser}(ast); + ExpressionSplitter{_dialect, dispenser}(ast); SSATransform::run(ast, dispenser); - RedundantAssignEliminator::run(ast); - RedundantAssignEliminator::run(ast); - CommonSubexpressionEliminator{}(ast); + RedundantAssignEliminator::run(_dialect, ast); + RedundantAssignEliminator::run(_dialect, ast); + CommonSubexpressionEliminator{_dialect}(ast); + + (FunctionGrouper{})(ast); + EquivalentFunctionCombiner::run(ast); FullInliner{ast, dispenser}.run(); + SSATransform::run(ast, dispenser); - RedundantAssignEliminator::run(ast); - RedundantAssignEliminator::run(ast); - ExpressionSimplifier::run(ast); - StructuralSimplifier{}(ast); - CommonSubexpressionEliminator{}(ast); + RedundantAssignEliminator::run(_dialect, ast); + RedundantAssignEliminator::run(_dialect, ast); + ExpressionSimplifier::run(_dialect, ast); + StructuralSimplifier{_dialect}(ast); + (BlockFlattener{})(ast); + CommonSubexpressionEliminator{_dialect}(ast); SSATransform::run(ast, dispenser); - RedundantAssignEliminator::run(ast); - RedundantAssignEliminator::run(ast); - UnusedPruner::runUntilStabilised(ast, reservedIdentifiers); + RedundantAssignEliminator::run(_dialect, ast); + RedundantAssignEliminator::run(_dialect, ast); + UnusedPruner::runUntilStabilised(_dialect, ast, reservedIdentifiers); + CommonSubexpressionEliminator{_dialect}(ast); } ExpressionJoiner::run(ast); - UnusedPruner::runUntilStabilised(ast); + Rematerialiser::run(_dialect, ast); + UnusedPruner::runUntilStabilised(_dialect, ast); ExpressionJoiner::run(ast); - UnusedPruner::runUntilStabilised(ast); + UnusedPruner::runUntilStabilised(_dialect, ast); ExpressionJoiner::run(ast); - UnusedPruner::runUntilStabilised(ast); + UnusedPruner::runUntilStabilised(_dialect, ast); + + SSAReverser::run(ast); + CommonSubexpressionEliminator{_dialect}(ast); + UnusedPruner::runUntilStabilised(_dialect, ast, reservedIdentifiers); + ExpressionJoiner::run(ast); - UnusedPruner::runUntilStabilised(ast); + Rematerialiser::run(_dialect, ast); + UnusedPruner::runUntilStabilised(_dialect, ast); _ast = std::move(ast); } diff --git a/libyul/optimiser/Suite.h b/libyul/optimiser/Suite.h index 795326b4..376e9889 100644 --- a/libyul/optimiser/Suite.h +++ b/libyul/optimiser/Suite.h @@ -29,6 +29,7 @@ namespace yul { struct AsmAnalysisInfo; +struct Dialect; /** * Optimiser suite that combines all steps and also provides the settings for the heuristics @@ -37,9 +38,9 @@ class OptimiserSuite { public: static void run( + Dialect const& _dialect, Block& _ast, AsmAnalysisInfo const& _analysisInfo, - std::set<YulString> const& _externallyUsedIdentifiers = {} ); }; diff --git a/libyul/optimiser/SyntacticalEquality.cpp b/libyul/optimiser/SyntacticalEquality.cpp index 99ce06e5..53f0b029 100644 --- a/libyul/optimiser/SyntacticalEquality.cpp +++ b/libyul/optimiser/SyntacticalEquality.cpp @@ -22,6 +22,7 @@ #include <libyul/Exceptions.h> #include <libyul/AsmData.h> +#include <libyul/Utilities.h> #include <libdevcore/CommonData.h> @@ -29,48 +30,166 @@ using namespace std; using namespace dev; using namespace yul; -bool SyntacticalEqualityChecker::equal(Expression const& _e1, Expression const& _e2) +bool SyntacticallyEqual::operator()(Expression const& _lhs, Expression const& _rhs) { - if (_e1.type() != _e2.type()) + return boost::apply_visitor([this](auto&& _lhsExpr, auto&& _rhsExpr) -> bool { + // ``this->`` is redundant, but required to work around a bug present in gcc 6.x. + return this->expressionEqual(_lhsExpr, _rhsExpr); + }, _lhs, _rhs); +} + +bool SyntacticallyEqual::operator()(Statement const& _lhs, Statement const& _rhs) +{ + return boost::apply_visitor([this](auto&& _lhsStmt, auto&& _rhsStmt) -> bool { + // ``this->`` is redundant, but required to work around a bug present in gcc 6.x. + return this->statementEqual(_lhsStmt, _rhsStmt); + }, _lhs, _rhs); +} + +bool SyntacticallyEqual::expressionEqual(FunctionalInstruction const& _lhs, FunctionalInstruction const& _rhs) +{ + return + _lhs.instruction == _rhs.instruction && + containerEqual(_lhs.arguments, _rhs.arguments, [this](Expression const& _lhsExpr, Expression const& _rhsExpr) -> bool { + return (*this)(_lhsExpr, _rhsExpr); + }); +} + +bool SyntacticallyEqual::expressionEqual(FunctionCall const& _lhs, FunctionCall const& _rhs) +{ + return + expressionEqual(_lhs.functionName, _rhs.functionName) && + containerEqual(_lhs.arguments, _rhs.arguments, [this](Expression const& _lhsExpr, Expression const& _rhsExpr) -> bool { + return (*this)(_lhsExpr, _rhsExpr); + }); +} + +bool SyntacticallyEqual::expressionEqual(Identifier const& _lhs, Identifier const& _rhs) +{ + auto lhsIt = m_identifiersLHS.find(_lhs.name); + auto rhsIt = m_identifiersRHS.find(_rhs.name); + return + (lhsIt == m_identifiersLHS.end() && rhsIt == m_identifiersRHS.end() && _lhs.name == _rhs.name) || + (lhsIt != m_identifiersLHS.end() && rhsIt != m_identifiersRHS.end() && lhsIt->second == rhsIt->second); +} +bool SyntacticallyEqual::expressionEqual(Literal const& _lhs, Literal const& _rhs) +{ + if (_lhs.kind != _rhs.kind || _lhs.type != _rhs.type) return false; - // TODO This somehow calls strcmp - WHERE? - - // TODO This should be replaced by some kind of AST walker as soon as it gets - // more complex. - if (_e1.type() == typeid(FunctionalInstruction)) - { - auto const& e1 = boost::get<FunctionalInstruction>(_e1); - auto const& e2 = boost::get<FunctionalInstruction>(_e2); - return - e1.instruction == e2.instruction && - equalVector(e1.arguments, e2.arguments); - } - else if (_e1.type() == typeid(FunctionCall)) - { - auto const& e1 = boost::get<FunctionCall>(_e1); - auto const& e2 = boost::get<FunctionCall>(_e2); - return - equal(e1.functionName, e2.functionName) && - equalVector(e1.arguments, e2.arguments); - } - else if (_e1.type() == typeid(Identifier)) - return boost::get<Identifier>(_e1).name == boost::get<Identifier>(_e2).name; - else if (_e1.type() == typeid(Literal)) - { - auto const& e1 = boost::get<Literal>(_e1); - auto const& e2 = boost::get<Literal>(_e2); - return e1.kind == e2.kind && e1.value == e2.value && e1.type == e2.type; - } + if (_lhs.kind == LiteralKind::Number) + return valueOfNumberLiteral(_lhs) == valueOfNumberLiteral(_rhs); else - { - assertThrow(false, OptimizerException, "Invalid expression"); - } - return false; + return _lhs.value == _rhs.value; } -bool SyntacticalEqualityChecker::equalVector(vector<Expression> const& _e1, vector<Expression> const& _e2) +bool SyntacticallyEqual::statementEqual(ExpressionStatement const& _lhs, ExpressionStatement const& _rhs) { - return _e1.size() == _e2.size() && - std::equal(begin(_e1), end(_e1), begin(_e2), SyntacticalEqualityChecker::equal); + return (*this)(_lhs.expression, _rhs.expression); +} +bool SyntacticallyEqual::statementEqual(Assignment const& _lhs, Assignment const& _rhs) +{ + return containerEqual( + _lhs.variableNames, + _rhs.variableNames, + [this](Identifier const& _lhsVarName, Identifier const& _rhsVarName) -> bool { + return this->expressionEqual(_lhsVarName, _rhsVarName); + } + ) && (*this)(*_lhs.value, *_rhs.value); +} + +bool SyntacticallyEqual::statementEqual(VariableDeclaration const& _lhs, VariableDeclaration const& _rhs) +{ + // first visit expression, then variable declarations + if (!compareUniquePtr<Expression, &SyntacticallyEqual::operator()>(_lhs.value, _rhs.value)) + return false; + return containerEqual(_lhs.variables, _rhs.variables, [this](TypedName const& _lhsVarName, TypedName const& _rhsVarName) -> bool { + return this->visitDeclaration(_lhsVarName, _rhsVarName); + }); +} +bool SyntacticallyEqual::statementEqual(FunctionDefinition const& _lhs, FunctionDefinition const& _rhs) +{ + auto compare = [this](TypedName const& _lhsVarName, TypedName const& _rhsVarName) -> bool { + return this->visitDeclaration(_lhsVarName, _rhsVarName); + }; + // first visit parameter declarations, then body + if (!containerEqual(_lhs.parameters, _rhs.parameters, compare)) + return false; + if (!containerEqual(_lhs.returnVariables, _rhs.returnVariables, compare)) + return false; + return statementEqual(_lhs.body, _rhs.body); +} + +bool SyntacticallyEqual::statementEqual(If const& _lhs, If const& _rhs) +{ + return + compareUniquePtr<Expression, &SyntacticallyEqual::operator()>(_lhs.condition, _rhs.condition) && + statementEqual(_lhs.body, _rhs.body); +} + +bool SyntacticallyEqual::statementEqual(Switch const& _lhs, Switch const& _rhs) +{ + static auto const sortCasesByValue = [](Case const* _lhsCase, Case const* _rhsCase) -> bool { + return Less<Literal*>{}(_lhsCase->value.get(), _rhsCase->value.get()); + }; + std::set<Case const*, decltype(sortCasesByValue)> lhsCases(sortCasesByValue); + std::set<Case const*, decltype(sortCasesByValue)> rhsCases(sortCasesByValue); + for (auto const& lhsCase: _lhs.cases) + lhsCases.insert(&lhsCase); + for (auto const& rhsCase: _rhs.cases) + rhsCases.insert(&rhsCase); + return + compareUniquePtr<Expression, &SyntacticallyEqual::operator()>(_lhs.expression, _rhs.expression) && + containerEqual(lhsCases, rhsCases, [this](Case const* _lhsCase, Case const* _rhsCase) -> bool { + return this->switchCaseEqual(*_lhsCase, *_rhsCase); + }); +} + + +bool SyntacticallyEqual::switchCaseEqual(Case const& _lhs, Case const& _rhs) +{ + return + compareUniquePtr<Literal, &SyntacticallyEqual::expressionEqual>(_lhs.value, _rhs.value) && + statementEqual(_lhs.body, _rhs.body); +} + +bool SyntacticallyEqual::statementEqual(ForLoop const& _lhs, ForLoop const& _rhs) +{ + return + statementEqual(_lhs.pre, _rhs.pre) && + compareUniquePtr<Expression, &SyntacticallyEqual::operator()>(_lhs.condition, _rhs.condition) && + statementEqual(_lhs.body, _rhs.body) && + statementEqual(_lhs.post, _rhs.post); +} + +bool SyntacticallyEqual::statementEqual(Instruction const&, Instruction const&) +{ + assertThrow(false, OptimizerException, ""); +} + +bool SyntacticallyEqual::statementEqual(Label const&, Label const&) +{ + assertThrow(false, OptimizerException, ""); +} + +bool SyntacticallyEqual::statementEqual(StackAssignment const&, StackAssignment const&) +{ + assertThrow(false, OptimizerException, ""); +} + +bool SyntacticallyEqual::statementEqual(Block const& _lhs, Block const& _rhs) +{ + return containerEqual(_lhs.statements, _rhs.statements, [this](Statement const& _lhsStmt, Statement const& _rhsStmt) -> bool { + return (*this)(_lhsStmt, _rhsStmt); + }); +} + +bool SyntacticallyEqual::visitDeclaration(TypedName const& _lhs, TypedName const& _rhs) +{ + if (_lhs.type != _rhs.type) + return false; + std::size_t id = m_idsUsed++; + m_identifiersLHS[_lhs.name] = id; + m_identifiersRHS[_rhs.name] = id; + return true; } diff --git a/libyul/optimiser/SyntacticalEquality.h b/libyul/optimiser/SyntacticalEquality.h index 63c51b4f..af240717 100644 --- a/libyul/optimiser/SyntacticalEquality.h +++ b/libyul/optimiser/SyntacticalEquality.h @@ -21,27 +21,69 @@ #pragma once #include <libyul/AsmDataForward.h> +#include <libyul/YulString.h> -#include <vector> +#include <map> +#include <type_traits> namespace yul { + /** * Component that can compare ASTs for equality on a syntactic basis. - * Ignores source locations but requires exact matches otherwise. + * Ignores source locations and allows for different variable names but requires exact matches otherwise. * - * TODO: Only implemented for Expressions for now. - * A future version might also recognize renamed variables and thus could be used to - * remove duplicate functions. + * Prerequisite: Disambiguator (unless only expressions are compared) */ -class SyntacticalEqualityChecker +class SyntacticallyEqual { public: - static bool equal(Expression const& _e1, Expression const& _e2); + bool operator()(Expression const& _lhs, Expression const& _rhs); + bool operator()(Statement const& _lhs, Statement const& _rhs); + + bool expressionEqual(FunctionalInstruction const& _lhs, FunctionalInstruction const& _rhs); + bool expressionEqual(FunctionCall const& _lhs, FunctionCall const& _rhs); + bool expressionEqual(Identifier const& _lhs, Identifier const& _rhs); + bool expressionEqual(Literal const& _lhs, Literal const& _rhs); + + bool statementEqual(ExpressionStatement const& _lhs, ExpressionStatement const& _rhs); + bool statementEqual(Assignment const& _lhs, Assignment const& _rhs); + bool statementEqual(VariableDeclaration const& _lhs, VariableDeclaration const& _rhs); + bool statementEqual(FunctionDefinition const& _lhs, FunctionDefinition const& _rhs); + bool statementEqual(If const& _lhs, If const& _rhs); + bool statementEqual(Switch const& _lhs, Switch const& _rhs); + bool switchCaseEqual(Case const& _lhs, Case const& _rhs); + bool statementEqual(ForLoop const& _lhs, ForLoop const& _rhs); + bool statementEqual(Block const& _lhs, Block const& _rhs); +private: + bool statementEqual(Instruction const& _lhs, Instruction const& _rhs); + bool statementEqual(Label const& _lhs, Label const& _rhs); + bool statementEqual(StackAssignment const& _lhs, StackAssignment const& _rhs); + + bool visitDeclaration(TypedName const& _lhs, TypedName const& _rhs); + + template<typename U, typename V> + bool expressionEqual(U const&, V const&, std::enable_if_t<!std::is_same<U, V>::value>* = nullptr) + { + return false; + } + + template<typename U, typename V> + bool statementEqual(U const&, V const&, std::enable_if_t<!std::is_same<U, V>::value>* = nullptr) + { + return false; + } + + template<typename T, bool (SyntacticallyEqual::*CompareMember)(T const&, T const&)> + bool compareUniquePtr(std::unique_ptr<T> const& _lhs, std::unique_ptr<T> const& _rhs) + { + return (_lhs == _rhs) || (_lhs && _rhs && (this->*CompareMember)(*_lhs, *_rhs)); + } -protected: - static bool equalVector(std::vector<Expression> const& _e1, std::vector<Expression> const& _e2); + std::size_t m_idsUsed = 0; + std::map<YulString, std::size_t> m_identifiersLHS; + std::map<YulString, std::size_t> m_identifiersRHS; }; } diff --git a/libyul/optimiser/UnusedPruner.cpp b/libyul/optimiser/UnusedPruner.cpp index 31aead82..365b255c 100644 --- a/libyul/optimiser/UnusedPruner.cpp +++ b/libyul/optimiser/UnusedPruner.cpp @@ -22,7 +22,7 @@ #include <libyul/optimiser/NameCollector.h> #include <libyul/optimiser/Semantics.h> -#include <libyul/optimiser/Utilities.h> +#include <libyul/optimiser/OptimizerUtilities.h> #include <libyul/Exceptions.h> #include <libyul/AsmData.h> @@ -32,7 +32,8 @@ using namespace std; using namespace dev; using namespace yul; -UnusedPruner::UnusedPruner(Block& _ast, set<YulString> const& _externallyUsedFunctions) +UnusedPruner::UnusedPruner(Dialect const& _dialect, Block& _ast, set<YulString> const& _externallyUsedFunctions): + m_dialect(_dialect) { ReferencesCounter counter; counter(_ast); @@ -69,7 +70,7 @@ void UnusedPruner::operator()(Block& _block) { if (!varDecl.value) statement = Block{std::move(varDecl.location), {}}; - else if (MovableChecker(*varDecl.value).movable()) + else if (MovableChecker(m_dialect, *varDecl.value).movable()) { subtractReferences(ReferencesCounter::countReferences(*varDecl.value)); statement = Block{std::move(varDecl.location), {}}; @@ -87,7 +88,7 @@ void UnusedPruner::operator()(Block& _block) else if (statement.type() == typeid(ExpressionStatement)) { ExpressionStatement& exprStmt = boost::get<ExpressionStatement>(statement); - if (MovableChecker(exprStmt.expression).movable()) + if (MovableChecker(m_dialect, exprStmt.expression).movable()) { // pop(x) should be movable! subtractReferences(ReferencesCounter::countReferences(exprStmt.expression)); @@ -100,11 +101,15 @@ void UnusedPruner::operator()(Block& _block) ASTModifier::operator()(_block); } -void UnusedPruner::runUntilStabilised(Block& _ast, set<YulString> const& _externallyUsedFunctions) +void UnusedPruner::runUntilStabilised( + Dialect const& _dialect, + Block& _ast, + set<YulString> const& _externallyUsedFunctions +) { while (true) { - UnusedPruner pruner(_ast, _externallyUsedFunctions); + UnusedPruner pruner(_dialect, _ast, _externallyUsedFunctions); pruner(_ast); if (!pruner.shouldRunAgain()) return; diff --git a/libyul/optimiser/UnusedPruner.h b/libyul/optimiser/UnusedPruner.h index 64e02b35..72279d4a 100644 --- a/libyul/optimiser/UnusedPruner.h +++ b/libyul/optimiser/UnusedPruner.h @@ -28,6 +28,7 @@ namespace yul { +struct Dialect; /** * Optimisation stage that removes unused variables and functions and also @@ -40,7 +41,11 @@ namespace yul class UnusedPruner: public ASTModifier { public: - explicit UnusedPruner(Block& _ast, std::set<YulString> const& _externallyUsedFunctions = {}); + UnusedPruner( + Dialect const& _dialect, + Block& _ast, + std::set<YulString> const& _externallyUsedFunctions = {} + ); using ASTModifier::operator(); void operator()(Block& _block) override; @@ -49,12 +54,17 @@ public: bool shouldRunAgain() const { return m_shouldRunAgain; } // Run the pruner until the code does not change anymore. - static void runUntilStabilised(Block& _ast, std::set<YulString> const& _externallyUsedFunctions = {}); + static void runUntilStabilised( + Dialect const& _dialect, + Block& _ast, + std::set<YulString> const& _externallyUsedFunctions = {} + ); private: bool used(YulString _name) const; void subtractReferences(std::map<YulString, size_t> const& _subtrahend); + Dialect const& m_dialect; bool m_shouldRunAgain = false; std::map<YulString, size_t> m_references; }; diff --git a/libyul/optimiser/VarDeclInitializer.cpp b/libyul/optimiser/VarDeclInitializer.cpp index 4a26757f..7009cc9b 100644 --- a/libyul/optimiser/VarDeclInitializer.cpp +++ b/libyul/optimiser/VarDeclInitializer.cpp @@ -39,7 +39,7 @@ void VarDeclInitializer::operator()(Block& _block) return {}; else if (_varDecl.variables.size() == 1) { - _varDecl.value = make_shared<Expression>(zero); + _varDecl.value = make_unique<Expression>(zero); return {}; } else @@ -47,7 +47,7 @@ void VarDeclInitializer::operator()(Block& _block) OptionalStatements ret{vector<Statement>{}}; langutil::SourceLocation loc{std::move(_varDecl.location)}; for (auto& var: _varDecl.variables) - ret->push_back(VariableDeclaration{loc, {std::move(var)}, make_shared<Expression>(zero)}); + ret->push_back(VariableDeclaration{loc, {std::move(var)}, make_unique<Expression>(zero)}); return ret; } } |