diff options
| -rw-r--r-- | libevmasm/RuleList.h | 5 | ||||
| -rw-r--r-- | libjulia/optimiser/ExpressionSimplifier.cpp | 49 | ||||
| -rw-r--r-- | libjulia/optimiser/ExpressionSimplifier.h | 45 | ||||
| -rw-r--r-- | libjulia/optimiser/SimplificationRules.cpp | 172 | ||||
| -rw-r--r-- | libjulia/optimiser/SimplificationRules.h | 116 | ||||
| -rw-r--r-- | test/libjulia/Simplifier.cpp | 66 |
6 files changed, 453 insertions, 0 deletions
diff --git a/libevmasm/RuleList.h b/libevmasm/RuleList.h index 70a3ef71..3e7be720 100644 --- a/libevmasm/RuleList.h +++ b/libevmasm/RuleList.h @@ -43,6 +43,11 @@ template <class S> S modWorkaround(S const& _a, S const& _b) return (S)(bigint(_a) % bigint(_b)); } +// TODO: Add a parameter that will cause rules with swapped arguments +// to be added explicitly. This is needed by the new optimizer, but not +// by the old. The new optimizer requires that the order of arbitrary +// expressions is not altered. + /// @returns a list of simplification rules given certain match placeholders. /// A, B and C should represent constants, X and Y arbitrary expressions. /// The third element in the tuple is a boolean flag that indicates whether diff --git a/libjulia/optimiser/ExpressionSimplifier.cpp b/libjulia/optimiser/ExpressionSimplifier.cpp new file mode 100644 index 00000000..1d6d9f8b --- /dev/null +++ b/libjulia/optimiser/ExpressionSimplifier.cpp @@ -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 uses the simplification rules to simplify expressions. + */ + +#include <libjulia/optimiser/ExpressionSimplifier.h> + +#include <libjulia/optimiser/SimplificationRules.h> +#include <libjulia/optimiser/Semantics.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libsolidity/interface/Exceptions.h> + +#include <libdevcore/CommonData.h> + +using namespace std; +using namespace dev; +using namespace dev::julia; +using namespace dev::solidity; + + +void ExpressionSimplifier::visit(Expression& _expression) +{ + ASTModifier::visit(_expression); + while (auto match = SimplificationRules::findFirstMatch(_expression)) + { + // TODO: The check could actually be less strict than "movable". + // We only require "Does not cause side-effects". + if (std::get<2>(*match) && !MovableChecker(_expression).movable()) + return; + _expression = std::get<1>(*match)().toExpression(locationOf(_expression)); + } +} diff --git a/libjulia/optimiser/ExpressionSimplifier.h b/libjulia/optimiser/ExpressionSimplifier.h new file mode 100644 index 00000000..8a9e0e20 --- /dev/null +++ b/libjulia/optimiser/ExpressionSimplifier.h @@ -0,0 +1,45 @@ +/* + 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 uses the simplification rules to simplify expressions. + */ + +#pragma once + +#include <libjulia/ASTDataForward.h> + +#include <libjulia/optimiser/ASTWalker.h> + +namespace dev +{ +namespace julia +{ + +/** + * Applies simplification rules to all expressions. + */ +class ExpressionSimplifier: public ASTModifier +{ +public: + using ASTModifier::operator(); + virtual void visit(Expression& _expression); + +private: +}; + +} +} diff --git a/libjulia/optimiser/SimplificationRules.cpp b/libjulia/optimiser/SimplificationRules.cpp new file mode 100644 index 00000000..5cd13a62 --- /dev/null +++ b/libjulia/optimiser/SimplificationRules.cpp @@ -0,0 +1,172 @@ +/* + 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/>. +*/ +/** + * Module for applying replacement rules against Expressions. + */ + +#include <libjulia/optimiser/SimplificationRules.h> + +#include <libjulia/optimiser/Utilities.h> +#include <libjulia/optimiser/ASTCopier.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libevmasm/RuleList.h> + +using namespace std; +using namespace dev; +using namespace dev::julia; + + +tuple<Pattern, function<Pattern()>, bool> const* SimplificationRules::findFirstMatch(Expression const& _expr) +{ + if (_expr.type() != typeid(FunctionalInstruction)) + return nullptr; + + static SimplificationRules rules; + + FunctionalInstruction const& instruction = boost::get<FunctionalInstruction const&>(_expr); + for (auto const& rule: rules.m_rules[byte(instruction.instruction)]) + { + rules.resetMatchGroups(); + if (std::get<0>(rule).matches(_expr)) + return &rule; + } + return nullptr; +} + +void SimplificationRules::addRules(vector<tuple<Pattern, function<Pattern()>, bool>> const& _rules) +{ + for (auto const& r: _rules) + addRule(r); +} + +void SimplificationRules::addRule(tuple<Pattern, function<Pattern()>, bool> const& _rule) +{ + m_rules[byte(std::get<0>(_rule).instruction())].push_back(_rule); +} + +SimplificationRules::SimplificationRules() +{ + // Multiple occurences of one of these inside one rule must match the same equivalence class. + // Constants. + Pattern A(PatternKind::Constant); + Pattern B(PatternKind::Constant); + Pattern C(PatternKind::Constant); + // Anything. + Pattern X; + Pattern Y; + A.setMatchGroup(1, m_matchGroups); + B.setMatchGroup(2, m_matchGroups); + C.setMatchGroup(3, m_matchGroups); + X.setMatchGroup(4, m_matchGroups); + Y.setMatchGroup(5, m_matchGroups); + + addRules(simplificationRuleList(A, B, C, X, Y)); +} + +Pattern::Pattern(solidity::Instruction _instruction, vector<Pattern> const& _arguments): + m_kind(PatternKind::Operation), + m_instruction(_instruction), + m_arguments(_arguments) +{ +} + +void Pattern::setMatchGroup(unsigned _group, map<unsigned, Expression const*>& _matchGroups) +{ + m_matchGroup = _group; + m_matchGroups = &_matchGroups; +} + +bool Pattern::matches(Expression const& _expr) const +{ + if (m_kind == PatternKind::Constant) + { + if (_expr.type() != typeid(Literal)) + return false; + Literal const& literal = boost::get<Literal const&>(_expr); + if (literal.kind != assembly::LiteralKind::Number) + return false; + if (m_data && *m_data != u256(literal.value)) + return false; + assertThrow(m_arguments.empty(), OptimizerException, ""); + } + else if (m_kind == PatternKind::Operation) + { + if (_expr.type() != typeid(FunctionalInstruction)) + return false; + FunctionalInstruction const& instr = boost::get<FunctionalInstruction const&>(_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))) + return false; + } + else + { + assertThrow(m_arguments.empty(), OptimizerException, ""); + } + // We do not support matching multiple expressions that require the same value. + if (m_matchGroup) + { + if (m_matchGroups->count(m_matchGroup)) + return false; + (*m_matchGroups)[m_matchGroup] = &_expr; + } + return true; +} + +solidity::Instruction Pattern::instruction() const +{ + assertThrow(m_kind == PatternKind::Operation, OptimizerException, ""); + return m_instruction; +} + +Expression Pattern::toExpression(SourceLocation const& _location) const +{ + if (matchGroup()) + return ASTCopier().translate(matchGroupValue()); + if (m_kind == PatternKind::Constant) + { + assertThrow(m_data, OptimizerException, "No match group and no constant value given."); + return Literal{_location, assembly::LiteralKind::Number, m_data->str(), ""}; + } + else if (m_kind == PatternKind::Operation) + { + vector<Expression> arguments; + for (auto const& arg: m_arguments) + arguments.emplace_back(arg.toExpression(_location)); + return FunctionalInstruction{_location, m_instruction, std::move(arguments)}; + } + assertThrow(false, OptimizerException, "Pattern of kind 'any', but no match group."); +} + +u256 Pattern::d() const +{ + Literal const& literal = boost::get<Literal const&>(matchGroupValue()); + assertThrow(literal.kind == assembly::LiteralKind::Number, OptimizerException, ""); + return u256(literal.value); +} + +Expression const& Pattern::matchGroupValue() const +{ + assertThrow(m_matchGroup > 0, OptimizerException, ""); + assertThrow(!!m_matchGroups, OptimizerException, ""); + assertThrow((*m_matchGroups)[m_matchGroup], OptimizerException, ""); + return *(*m_matchGroups)[m_matchGroup]; +} diff --git a/libjulia/optimiser/SimplificationRules.h b/libjulia/optimiser/SimplificationRules.h new file mode 100644 index 00000000..96f3de21 --- /dev/null +++ b/libjulia/optimiser/SimplificationRules.h @@ -0,0 +1,116 @@ +/* + 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/>. +*/ +/** + * Module for applying replacement rules against Expressions. + */ + +#pragma once + +#include <libevmasm/ExpressionClasses.h> + +#include <libjulia/ASTDataForward.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <boost/noncopyable.hpp> + +#include <functional> +#include <vector> + +namespace dev +{ +namespace julia +{ + +class Pattern; + +/** + * Container for all simplification rules. + */ +class SimplificationRules: public boost::noncopyable +{ +public: + SimplificationRules(); + + /// @returns a pointer to the first matching pattern and sets the match + /// groups accordingly. + static std::tuple<Pattern, std::function<Pattern()>, bool> const* findFirstMatch(Expression const& _expr); + +private: + void addRules(std::vector<std::tuple<Pattern, std::function<Pattern()>, bool>> const& _rules); + void addRule(std::tuple<Pattern, std::function<Pattern()>, bool> const& _rule); + + void resetMatchGroups() { m_matchGroups.clear(); } + + std::map<unsigned, Expression const*> m_matchGroups; + std::vector<std::tuple<Pattern, std::function<Pattern()>, bool>> m_rules[256]; +}; + +enum class PatternKind +{ + Operation, + Constant, + Any +}; + +/** + * Pattern to match against an expression. + * Also stores matched expressions to retrieve them later, for constructing new expressions using + * ExpressionTemplate. + */ +class Pattern +{ +public: + /// Matches any expression. + Pattern(PatternKind _kind = PatternKind::Any): m_kind(_kind) {} + // Matches a specific constant value. + Pattern(unsigned _value): Pattern(u256(_value)) {} + // Matches a specific constant value. + Pattern(u256 const& _value): m_kind(PatternKind::Constant), m_data(std::make_shared<u256>(_value)) {} + // Matches a given instruction with given arguments + Pattern(solidity::Instruction _instruction, std::vector<Pattern> const& _arguments = {}); + /// Sets this pattern to be part of the match group with the identifier @a _group. + /// Inside one rule, all patterns in the same match group have to match expressions from the + /// 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) const; + + std::vector<Pattern> arguments() const { return m_arguments; } + + /// @returns the data of the matched expression if this pattern is part of a match group. + u256 d() const; + + solidity::Instruction instruction() const; + + /// Turns this pattern into an actual expression. Should only be called + /// for patterns resulting from an action, i.e. with match groups assigned. + Expression toExpression(SourceLocation const& _location) const; + +private: + Expression const& matchGroupValue() const; + + PatternKind m_kind = PatternKind::Any; + solidity::Instruction m_instruction; ///< Only valid if m_kind is Operation + std::shared_ptr<u256> m_data; ///< Only valid if m_kind is Constant + std::vector<Pattern> m_arguments; + unsigned m_matchGroup = 0; + std::map<unsigned, Expression const*>* m_matchGroups = nullptr; +}; + +} +} diff --git a/test/libjulia/Simplifier.cpp b/test/libjulia/Simplifier.cpp new file mode 100644 index 00000000..83cc7687 --- /dev/null +++ b/test/libjulia/Simplifier.cpp @@ -0,0 +1,66 @@ +/* + 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/>. +*/ +/** + * @date 2017 + * Unit tests for the expression simplifier optimizer stage. + */ + +#include <test/libjulia/Common.h> + +#include <libjulia/optimiser/ExpressionSimplifier.h> + +#include <libsolidity/inlineasm/AsmPrinter.h> + +#include <boost/test/unit_test.hpp> + +#include <boost/range/adaptors.hpp> +#include <boost/algorithm/string/join.hpp> + +using namespace std; +using namespace dev; +using namespace dev::julia; +using namespace dev::julia::test; +using namespace dev::solidity; + + +#define CHECK(_original, _expectation)\ +do\ +{\ + assembly::AsmPrinter p;\ + Block b = *(parse(_original, false).first);\ + (ExpressionSimplifier{})(b);\ + string result = p(b);\ + BOOST_CHECK_EQUAL(result, format(_expectation, false));\ +}\ +while(false) + +BOOST_AUTO_TEST_SUITE(IuliaSimplifier) + +BOOST_AUTO_TEST_CASE(smoke_test) +{ + CHECK("{ }", "{ }"); +} + +BOOST_AUTO_TEST_CASE(constants) +{ + CHECK( + "{ let a := add(1, mul(3, 4)) }", + "{ let a := 13 }" + ); +} + +BOOST_AUTO_TEST_SUITE_END() |