From 76db0d69cfba634bdc5f6da41dc30c2abdb66bc2 Mon Sep 17 00:00:00 2001 From: chriseth Date: Tue, 2 Oct 2018 18:07:36 +0200 Subject: SSA value tracker. --- libyul/optimiser/SSAValueTracker.cpp | 53 ++++++++++++++++++++++++++++++++ libyul/optimiser/SSAValueTracker.h | 58 ++++++++++++++++++++++++++++++++++++ 2 files changed, 111 insertions(+) create mode 100644 libyul/optimiser/SSAValueTracker.cpp create mode 100644 libyul/optimiser/SSAValueTracker.h (limited to 'libyul') diff --git a/libyul/optimiser/SSAValueTracker.cpp b/libyul/optimiser/SSAValueTracker.cpp new file mode 100644 index 00000000..a1291d67 --- /dev/null +++ b/libyul/optimiser/SSAValueTracker.cpp @@ -0,0 +1,53 @@ +/* + 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 . +*/ +/** + * Component that collects variables that are never assigned to and their + * initial values. + */ + +#include + +#include + +using namespace std; +using namespace dev; +using namespace dev::yul; + +void SSAValueTracker::operator()(Assignment const& _assignment) +{ + for (auto const& var: _assignment.variableNames) + m_values.erase(var.name); +} + +void SSAValueTracker::operator()(VariableDeclaration const& _varDecl) +{ + if (_varDecl.variables.size() == 1) + setValue(_varDecl.variables.front().name, _varDecl.value.get()); + else + for (auto const& var: _varDecl.variables) + setValue(var.name, nullptr); +} + +void SSAValueTracker::setValue(string const& _name, Expression const* _value) +{ + assertThrow( + m_values.count(_name) == 0, + OptimizerException, + "Source needs to be disambiguated." + ); + m_values[_name] = _value; +} diff --git a/libyul/optimiser/SSAValueTracker.h b/libyul/optimiser/SSAValueTracker.h new file mode 100644 index 00000000..8c39a98e --- /dev/null +++ b/libyul/optimiser/SSAValueTracker.h @@ -0,0 +1,58 @@ +/* + 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 . +*/ +/** + * Component that collects variables that are never assigned to and their + * initial values. + */ + +#pragma once + +#include + +#include +#include +#include + +namespace dev +{ +namespace yul +{ + +/** + * Class that walks the AST and stores the initial value of each variable + * that is never assigned to. + * + * Prerequisite: Disambiguator + */ +class SSAValueTracker: public ASTWalker +{ +public: + using ASTWalker::operator(); + virtual void operator()(VariableDeclaration const& _varDecl) override; + virtual void operator()(Assignment const& _assignment) override; + + std::map const& values() const { return m_values; } + Expression const* value(std::string const& _name) const { return m_values.at(_name); } + +private: + void setValue(std::string const& _name, Expression const* _value); + + std::map m_values; +}; + +} +} -- cgit From a320eec7d38f98a1fbb9f6267e5e30cfae5c59cf Mon Sep 17 00:00:00 2001 From: chriseth Date: Tue, 2 Oct 2018 18:07:50 +0200 Subject: New simplifier via broken expressions. --- libyul/optimiser/ExpressionSimplifier.cpp | 14 +++++++- libyul/optimiser/ExpressionSimplifier.h | 10 ++++++ libyul/optimiser/SimplificationRules.cpp | 56 ++++++++++++++++++++++++------- libyul/optimiser/SimplificationRules.h | 8 +++-- 4 files changed, 73 insertions(+), 15 deletions(-) (limited to 'libyul') diff --git a/libyul/optimiser/ExpressionSimplifier.cpp b/libyul/optimiser/ExpressionSimplifier.cpp index c95fb3d5..64e9d7e7 100644 --- a/libyul/optimiser/ExpressionSimplifier.cpp +++ b/libyul/optimiser/ExpressionSimplifier.cpp @@ -22,6 +22,7 @@ #include #include +#include #include @@ -36,13 +37,24 @@ using namespace dev::solidity; void ExpressionSimplifier::visit(Expression& _expression) { ASTModifier::visit(_expression); - while (auto match = SimplificationRules::findFirstMatch(_expression)) + while (auto match = SimplificationRules::findFirstMatch(_expression, 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". // We only require "Does not cause side-effects". + // Note: References to variables that are only assigned once are always movable, + // so if the value of the variable is not movable, the expression that references + // the variable still is. + if (match->removesNonConstants && !MovableChecker(_expression).movable()) return; _expression = match->action().toExpression(locationOf(_expression)); } } + +void ExpressionSimplifier::run(Block& _ast) +{ + SSAValueTracker ssaValues; + ssaValues(_ast); + ExpressionSimplifier{ssaValues.values()}(_ast); +} diff --git a/libyul/optimiser/ExpressionSimplifier.h b/libyul/optimiser/ExpressionSimplifier.h index 1b9d6960..5419ff6a 100644 --- a/libyul/optimiser/ExpressionSimplifier.h +++ b/libyul/optimiser/ExpressionSimplifier.h @@ -31,6 +31,10 @@ namespace yul /** * Applies simplification rules to all expressions. + * The component will work best if the code is in SSA form, but + * this is not required for correctness. + * + * Prerequisite: Disambiguator. */ class ExpressionSimplifier: public ASTModifier { @@ -38,7 +42,13 @@ public: using ASTModifier::operator(); virtual void visit(Expression& _expression); + static void run(Block& _ast); private: + explicit ExpressionSimplifier(std::map _ssaValues): + m_ssaValues(std::move(_ssaValues)) + {} + + std::map m_ssaValues; }; } diff --git a/libyul/optimiser/SimplificationRules.cpp b/libyul/optimiser/SimplificationRules.cpp index 762473e5..4d0468c7 100644 --- a/libyul/optimiser/SimplificationRules.cpp +++ b/libyul/optimiser/SimplificationRules.cpp @@ -34,7 +34,10 @@ using namespace dev; using namespace dev::yul; -SimplificationRule const* SimplificationRules::findFirstMatch(Expression const& _expr) +SimplificationRule const* SimplificationRules::findFirstMatch( + Expression const& _expr, + map const& _ssaValues +) { if (_expr.type() != typeid(FunctionalInstruction)) return nullptr; @@ -46,7 +49,7 @@ SimplificationRule const* SimplificationRules::findFirstMatch(Expressio for (auto const& rule: rules.m_rules[byte(instruction.instruction)]) { rules.resetMatchGroups(); - if (rule.pattern.matches(_expr)) + if (rule.pattern.matches(_expr, _ssaValues)) return &rule; } return nullptr; @@ -101,13 +104,25 @@ void Pattern::setMatchGroup(unsigned _group, map& _ m_matchGroups = &_matchGroups; } -bool Pattern::matches(Expression const& _expr) const +bool Pattern::matches(Expression const& _expr, map const& _ssaValues) const { + Expression const* expr = &_expr; + + // Resolve the variable if possible. + // Do not do it for "Any" because we can check identity better for variables. + if (m_kind != PatternKind::Any && _expr.type() == typeid(Identifier)) + { + string const& varName = boost::get(_expr).name; + if (_ssaValues.count(varName)) + expr = _ssaValues.at(varName); + } + assertThrow(expr, OptimizerException, ""); + if (m_kind == PatternKind::Constant) { - if (_expr.type() != typeid(Literal)) + if (expr->type() != typeid(Literal)) return false; - Literal const& literal = boost::get(_expr); + Literal const& literal = boost::get(*expr); if (literal.kind != assembly::LiteralKind::Number) return false; if (m_data && *m_data != u256(literal.value)) @@ -116,34 +131,51 @@ bool Pattern::matches(Expression const& _expr) const } else if (m_kind == PatternKind::Operation) { - if (_expr.type() != typeid(FunctionalInstruction)) + if (expr->type() != typeid(FunctionalInstruction)) return false; - FunctionalInstruction const& instr = boost::get(_expr); + FunctionalInstruction const& instr = boost::get(*expr); if (m_instruction != instr.instruction) 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))) + if (!m_arguments[i].matches(instr.arguments.at(i), _ssaValues)) return false; } else { - assertThrow(m_arguments.empty(), OptimizerException, ""); + assertThrow(m_arguments.empty(), OptimizerException, "\"Any\" should not have arguments."); } - // We support matching multiple expressions that require the same value - // based on identical ASTs, which have to be movable. + if (m_matchGroup) { + // We support matching multiple expressions that require the same value + // based on identical ASTs, which have to be movable. + + // TODO: add tests: + // - { let x := mload(0) let y := and(x, x) } + // - { let x := 4 let y := and(x, y) } + + // This code uses `_expr` again for "Any", because we want the comparison to be done + // on the variables and not their values. + // The assumption is that CSE or local value numbering has been done prior to this step. + if (m_matchGroups->count(m_matchGroup)) { + assertThrow(m_kind == PatternKind::Any, OptimizerException, "Match group repetition for non-any."); Expression const* firstMatch = (*m_matchGroups)[m_matchGroup]; assertThrow(firstMatch, OptimizerException, "Match set but to null."); return SyntacticalEqualityChecker::equal(*firstMatch, _expr) && MovableChecker(_expr).movable(); } - else + else if (m_kind == PatternKind::Any) (*m_matchGroups)[m_matchGroup] = &_expr; + else + { + assertThrow(m_kind == PatternKind::Constant, OptimizerException, "Match group set for operation."); + // We do not use _expr here, because we want the actual number. + (*m_matchGroups)[m_matchGroup] = expr; + } } return true; } diff --git a/libyul/optimiser/SimplificationRules.h b/libyul/optimiser/SimplificationRules.h index 25d91573..82ae5d22 100644 --- a/libyul/optimiser/SimplificationRules.h +++ b/libyul/optimiser/SimplificationRules.h @@ -49,7 +49,11 @@ public: /// @returns a pointer to the first matching pattern and sets the match /// groups accordingly. - static SimplificationRule const* findFirstMatch(Expression const& _expr); + /// @param _ssaValues values of variables that are assigned exactly once. + static SimplificationRule const* findFirstMatch( + Expression const& _expr, + std::map const& _ssaValues + ); /// Checks whether the rulelist is non-empty. This is usually enforced /// by the constructor, but we had some issues with static initialization. @@ -92,7 +96,7 @@ public: /// same expression equivalence class. void setMatchGroup(unsigned _group, std::map& _matchGroups); unsigned matchGroup() const { return m_matchGroup; } - bool matches(Expression const& _expr) const; + bool matches(Expression const& _expr, std::map const& _ssaValues) const; std::vector arguments() const { return m_arguments; } -- cgit