diff options
35 files changed, 2559 insertions, 191 deletions
@@ -1,6 +1,6 @@ version: 2 jobs: - build: + build_emscripten: docker: - image: trzeci/emscripten:sdk-tag-1.37.21-64bit steps: @@ -48,3 +48,52 @@ jobs: - store_artifacts: path: build/solc/soljson.js destination: soljson.js + build_x86: + docker: + - image: buildpack-deps:artful + steps: + - checkout + - run: + name: Install build dependencies + command: | + apt-get -qq update + apt-get -qy install ccache cmake libboost-all-dev libz3-dev + - run: + name: Init submodules + command: | + git submodule update --init + - run: + name: Store commit hash and prerelease + command: | + date -u +"nightly.%Y.%-m.%-d" > prerelease.txt + echo -n "$CIRCLE_SHA1" > commit_hash.txt + - restore_cache: + key: ccache-{{ arch }}-{{ .Branch }} + key: ccache-{{ arch }} + key: ccache + - run: + name: Build + command: ./scripts/build.sh RelWithDebInfo + - save_cache: + key: ccache-{{ arch }}-{{ .Branch }} + paths: + - ~/.ccache + - run: + name: Commandline tests + command: test/cmdlineTests.sh + - run: mkdir -p test_results + - run: + name: Test without optimizer (exclude IPC tests) + command: build/test/soltest --logger=JUNIT,test_suite,test_results/no_opt.xml -- --no-ipc + - run: + name: Test with optimizer (exclude IPC tests) + command: build/test/soltest --logger=JUNIT,test_suite,test_results/opt.xml -- --optimize --no-ipc + - store_test_results: + path: test_results/ + +workflows: + version: 2 + build_all: + jobs: + - build_emscripten + - build_x86 diff --git a/libevmasm/ExpressionClasses.cpp b/libevmasm/ExpressionClasses.cpp index fc283b0b..69b33ec5 100644 --- a/libevmasm/ExpressionClasses.cpp +++ b/libevmasm/ExpressionClasses.cpp @@ -181,7 +181,7 @@ string ExpressionClasses::fullDAGToString(ExpressionClasses::Id _id) const return str.str(); } -ExpressionClasses::Id ExpressionClasses::tryToSimplify(Expression const& _expr, bool _secondRun) +ExpressionClasses::Id ExpressionClasses::tryToSimplify(Expression const& _expr) { static Rules rules; @@ -202,14 +202,7 @@ ExpressionClasses::Id ExpressionClasses::tryToSimplify(Expression const& _expr, //cout << "with rule " << match->first.toString() << endl; //ExpressionTemplate t(match->second()); //cout << "to " << match->second().toString() << endl; - return rebuildExpression(ExpressionTemplate(match->second(), _expr.item->location())); - } - - if (!_secondRun && _expr.arguments.size() == 2 && SemanticInformation::isCommutativeOperation(*_expr.item)) - { - Expression expr = _expr; - swap(expr.arguments[0], expr.arguments[1]); - return tryToSimplify(expr, true); + return rebuildExpression(ExpressionTemplate(match->action(), _expr.item->location())); } return -1; diff --git a/libevmasm/ExpressionClasses.h b/libevmasm/ExpressionClasses.h index 6b426e97..df8082f9 100644 --- a/libevmasm/ExpressionClasses.h +++ b/libevmasm/ExpressionClasses.h @@ -108,8 +108,7 @@ public: private: /// Tries to simplify the given expression. /// @returns its class if it possible or Id(-1) otherwise. - /// @param _secondRun is set to true for the second run where arguments of commutative expressions are reversed - Id tryToSimplify(Expression const& _expr, bool _secondRun = false); + Id tryToSimplify(Expression const& _expr); /// Rebuilds an expression from a (matched) pattern. Id rebuildExpression(ExpressionTemplate const& _template); diff --git a/libevmasm/RuleList.h b/libevmasm/RuleList.h new file mode 100644 index 00000000..2312d673 --- /dev/null +++ b/libevmasm/RuleList.h @@ -0,0 +1,255 @@ +/* + 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 2018 + * Templatized list of simplification rules. + */ + +#pragma once + +#include <vector> +#include <functional> + +#include <libevmasm/Instruction.h> +#include <libevmasm/SimplificationRule.h> + +#include <libdevcore/CommonData.h> + +namespace dev +{ +namespace solidity +{ + +template <class S> S divWorkaround(S const& _a, S const& _b) +{ + return (S)(bigint(_a) / bigint(_b)); +} + +template <class S> S modWorkaround(S const& _a, S const& _b) +{ + return (S)(bigint(_a) % bigint(_b)); +} + +/// @returns a list of simplification rules given certain match placeholders. +/// A, B and C should represent constants, X and Y arbitrary expressions. +/// The simplifications should neven change the order of evaluation of +/// arbitrary operations. +template <class Pattern> +std::vector<SimplificationRule<Pattern>> simplificationRuleList( + Pattern A, + Pattern B, + Pattern C, + Pattern X, + Pattern Y +) +{ + std::vector<SimplificationRule<Pattern>> rules; + rules += std::vector<SimplificationRule<Pattern>>{ + // arithmetics on constants + {{Instruction::ADD, {A, B}}, [=]{ return A.d() + B.d(); }, false}, + {{Instruction::MUL, {A, B}}, [=]{ return A.d() * B.d(); }, false}, + {{Instruction::SUB, {A, B}}, [=]{ return A.d() - B.d(); }, false}, + {{Instruction::DIV, {A, B}}, [=]{ return B.d() == 0 ? 0 : divWorkaround(A.d(), B.d()); }, false}, + {{Instruction::SDIV, {A, B}}, [=]{ return B.d() == 0 ? 0 : s2u(divWorkaround(u2s(A.d()), u2s(B.d()))); }, false}, + {{Instruction::MOD, {A, B}}, [=]{ return B.d() == 0 ? 0 : modWorkaround(A.d(), B.d()); }, false}, + {{Instruction::SMOD, {A, B}}, [=]{ return B.d() == 0 ? 0 : s2u(modWorkaround(u2s(A.d()), u2s(B.d()))); }, false}, + {{Instruction::EXP, {A, B}}, [=]{ return u256(boost::multiprecision::powm(bigint(A.d()), bigint(B.d()), bigint(1) << 256)); }, false}, + {{Instruction::NOT, {A}}, [=]{ return ~A.d(); }, false}, + {{Instruction::LT, {A, B}}, [=]() -> u256 { return A.d() < B.d() ? 1 : 0; }, false}, + {{Instruction::GT, {A, B}}, [=]() -> u256 { return A.d() > B.d() ? 1 : 0; }, false}, + {{Instruction::SLT, {A, B}}, [=]() -> u256 { return u2s(A.d()) < u2s(B.d()) ? 1 : 0; }, false}, + {{Instruction::SGT, {A, B}}, [=]() -> u256 { return u2s(A.d()) > u2s(B.d()) ? 1 : 0; }, false}, + {{Instruction::EQ, {A, B}}, [=]() -> u256 { return A.d() == B.d() ? 1 : 0; }, false}, + {{Instruction::ISZERO, {A}}, [=]() -> u256 { return A.d() == 0 ? 1 : 0; }, false}, + {{Instruction::AND, {A, B}}, [=]{ return A.d() & B.d(); }, false}, + {{Instruction::OR, {A, B}}, [=]{ return A.d() | B.d(); }, false}, + {{Instruction::XOR, {A, B}}, [=]{ return A.d() ^ B.d(); }, false}, + {{Instruction::BYTE, {A, B}}, [=]{ return A.d() >= 32 ? 0 : (B.d() >> unsigned(8 * (31 - A.d()))) & 0xff; }, false}, + {{Instruction::ADDMOD, {A, B, C}}, [=]{ return C.d() == 0 ? 0 : u256((bigint(A.d()) + bigint(B.d())) % C.d()); }, false}, + {{Instruction::MULMOD, {A, B, C}}, [=]{ return C.d() == 0 ? 0 : u256((bigint(A.d()) * bigint(B.d())) % C.d()); }, false}, + {{Instruction::MULMOD, {A, B, C}}, [=]{ return A.d() * B.d(); }, false}, + {{Instruction::SIGNEXTEND, {A, B}}, [=]() -> u256 { + if (A.d() >= 31) + return B.d(); + unsigned testBit = unsigned(A.d()) * 8 + 7; + u256 mask = (u256(1) << testBit) - 1; + return u256(boost::multiprecision::bit_test(B.d(), testBit) ? B.d() | ~mask : B.d() & mask); + }, false}, + + // invariants involving known constants + {{Instruction::ADD, {X, 0}}, [=]{ return X; }, false}, + {{Instruction::ADD, {0, X}}, [=]{ return X; }, false}, + {{Instruction::SUB, {X, 0}}, [=]{ return X; }, false}, + {{Instruction::MUL, {X, 0}}, [=]{ return u256(0); }, true}, + {{Instruction::MUL, {0, X}}, [=]{ return u256(0); }, true}, + {{Instruction::MUL, {X, 1}}, [=]{ return X; }, false}, + {{Instruction::MUL, {1, X}}, [=]{ return X; }, false}, + {{Instruction::MUL, {X, u256(-1)}}, [=]() -> Pattern { return {Instruction::SUB, {0, X}}; }, false}, + {{Instruction::MUL, {u256(-1), X}}, [=]() -> Pattern { return {Instruction::SUB, {0, X}}; }, false}, + {{Instruction::DIV, {X, 0}}, [=]{ return u256(0); }, true}, + {{Instruction::DIV, {0, X}}, [=]{ return u256(0); }, true}, + {{Instruction::DIV, {X, 1}}, [=]{ return X; }, false}, + {{Instruction::SDIV, {X, 0}}, [=]{ return u256(0); }, true}, + {{Instruction::SDIV, {0, X}}, [=]{ return u256(0); }, true}, + {{Instruction::SDIV, {X, 1}}, [=]{ return X; }, false}, + {{Instruction::AND, {X, ~u256(0)}}, [=]{ return X; }, false}, + {{Instruction::AND, {~u256(0), X}}, [=]{ return X; }, false}, + {{Instruction::AND, {X, 0}}, [=]{ return u256(0); }, true}, + {{Instruction::AND, {0, X}}, [=]{ return u256(0); }, true}, + {{Instruction::OR, {X, 0}}, [=]{ return X; }, false}, + {{Instruction::OR, {0, X}}, [=]{ return X; }, false}, + {{Instruction::OR, {X, ~u256(0)}}, [=]{ return ~u256(0); }, true}, + {{Instruction::OR, {~u256(0), X}}, [=]{ return ~u256(0); }, true}, + {{Instruction::XOR, {X, 0}}, [=]{ return X; }, false}, + {{Instruction::XOR, {0, X}}, [=]{ return X; }, false}, + {{Instruction::MOD, {X, 0}}, [=]{ return u256(0); }, true}, + {{Instruction::MOD, {0, X}}, [=]{ return u256(0); }, true}, + {{Instruction::EQ, {X, 0}}, [=]() -> Pattern { return {Instruction::ISZERO, {X}}; }, false }, + {{Instruction::EQ, {0, X}}, [=]() -> Pattern { return {Instruction::ISZERO, {X}}; }, false }, + + // operations involving an expression and itself + {{Instruction::AND, {X, X}}, [=]{ return X; }, true}, + {{Instruction::OR, {X, X}}, [=]{ return X; }, true}, + {{Instruction::XOR, {X, X}}, [=]{ return u256(0); }, true}, + {{Instruction::SUB, {X, X}}, [=]{ return u256(0); }, true}, + {{Instruction::EQ, {X, X}}, [=]{ return u256(1); }, true}, + {{Instruction::LT, {X, X}}, [=]{ return u256(0); }, true}, + {{Instruction::SLT, {X, X}}, [=]{ return u256(0); }, true}, + {{Instruction::GT, {X, X}}, [=]{ return u256(0); }, true}, + {{Instruction::SGT, {X, X}}, [=]{ return u256(0); }, true}, + {{Instruction::MOD, {X, X}}, [=]{ return u256(0); }, true}, + + // logical instruction combinations + {{Instruction::NOT, {{Instruction::NOT, {X}}}}, [=]{ return X; }, false}, + {{Instruction::XOR, {X, {Instruction::XOR, {X, Y}}}}, [=]{ return Y; }, true}, + {{Instruction::XOR, {X, {Instruction::XOR, {Y, X}}}}, [=]{ return Y; }, true}, + {{Instruction::XOR, {{Instruction::XOR, {X, Y}}, X}}, [=]{ return Y; }, true}, + {{Instruction::XOR, {{Instruction::XOR, {Y, X}}, X}}, [=]{ return Y; }, true}, + {{Instruction::OR, {X, {Instruction::AND, {X, Y}}}}, [=]{ return X; }, true}, + {{Instruction::OR, {X, {Instruction::AND, {Y, X}}}}, [=]{ return X; }, true}, + {{Instruction::OR, {{Instruction::AND, {X, Y}}, X}}, [=]{ return X; }, true}, + {{Instruction::OR, {{Instruction::AND, {Y, X}}, X}}, [=]{ return X; }, true}, + {{Instruction::AND, {X, {Instruction::OR, {X, Y}}}}, [=]{ return X; }, true}, + {{Instruction::AND, {X, {Instruction::OR, {Y, X}}}}, [=]{ return X; }, true}, + {{Instruction::AND, {{Instruction::OR, {X, Y}}, X}}, [=]{ return X; }, true}, + {{Instruction::AND, {{Instruction::OR, {Y, X}}, X}}, [=]{ return X; }, true}, + {{Instruction::AND, {X, {Instruction::NOT, {X}}}}, [=]{ return u256(0); }, true}, + {{Instruction::AND, {{Instruction::NOT, {X}}, X}}, [=]{ return u256(0); }, true}, + {{Instruction::OR, {X, {Instruction::NOT, {X}}}}, [=]{ return ~u256(0); }, true}, + {{Instruction::OR, {{Instruction::NOT, {X}}, X}}, [=]{ return ~u256(0); }, true}, + }; + + // Double negation of opcodes with boolean result + for (auto const& op: std::vector<Instruction>{ + Instruction::EQ, + Instruction::LT, + Instruction::SLT, + Instruction::GT, + Instruction::SGT + }) + rules.push_back({ + {Instruction::ISZERO, {{Instruction::ISZERO, {{op, {X, Y}}}}}}, + [=]() -> Pattern { return {op, {X, Y}}; }, + false + }); + + rules.push_back({ + {Instruction::ISZERO, {{Instruction::ISZERO, {{Instruction::ISZERO, {X}}}}}}, + [=]() -> Pattern { return {Instruction::ISZERO, {X}}; }, + false + }); + + rules.push_back({ + {Instruction::ISZERO, {{Instruction::XOR, {X, Y}}}}, + [=]() -> Pattern { return { Instruction::EQ, {X, Y} }; }, + false + }); + + // Associative operations + for (auto const& opFun: std::vector<std::pair<Instruction,std::function<u256(u256 const&,u256 const&)>>>{ + {Instruction::ADD, std::plus<u256>()}, + {Instruction::MUL, std::multiplies<u256>()}, + {Instruction::AND, std::bit_and<u256>()}, + {Instruction::OR, std::bit_or<u256>()}, + {Instruction::XOR, std::bit_xor<u256>()} + }) + { + auto op = opFun.first; + auto fun = opFun.second; + // Moving constants to the outside, order matters here - we first add rules + // for constants and then for non-constants. + // xa can be (X, A) or (A, X) + for (auto xa: {std::vector<Pattern>{X, A}, std::vector<Pattern>{A, X}}) + { + rules += std::vector<SimplificationRule<Pattern>>{{ + // (X+A)+B -> X+(A+B) + {op, {{op, xa}, B}}, + [=]() -> Pattern { return {op, {X, fun(A.d(), B.d())}}; }, + false + }, { + // (X+A)+Y -> (X+Y)+A + {op, {{op, xa}, Y}}, + [=]() -> Pattern { return {op, {{op, {X, Y}}, A}}; }, + false + }, { + // B+(X+A) -> X+(A+B) + {op, {B, {op, xa}}}, + [=]() -> Pattern { return {op, {X, fun(A.d(), B.d())}}; }, + false + }, { + // Y+(X+A) -> (Y+X)+A + {op, {Y, {op, xa}}}, + [=]() -> Pattern { return {op, {{op, {Y, X}}, A}}; }, + false + }}; + } + } + + // move constants across subtractions + rules += std::vector<SimplificationRule<Pattern>>{ + { + // X - A -> X + (-A) + {Instruction::SUB, {X, A}}, + [=]() -> Pattern { return {Instruction::ADD, {X, 0 - A.d()}}; }, + false + }, { + // (X + A) - Y -> (X - Y) + A + {Instruction::SUB, {{Instruction::ADD, {X, A}}, Y}}, + [=]() -> Pattern { return {Instruction::ADD, {{Instruction::SUB, {X, Y}}, A}}; }, + false + }, { + // (A + X) - Y -> (X - Y) + A + {Instruction::SUB, {{Instruction::ADD, {A, X}}, Y}}, + [=]() -> Pattern { return {Instruction::ADD, {{Instruction::SUB, {X, Y}}, A}}; }, + false + }, { + // X - (Y + A) -> (X - Y) + (-A) + {Instruction::SUB, {X, {Instruction::ADD, {Y, A}}}}, + [=]() -> Pattern { return {Instruction::ADD, {{Instruction::SUB, {X, Y}}, 0 - A.d()}}; }, + false + }, { + // X - (A + Y) -> (X - Y) + (-A) + {Instruction::SUB, {X, {Instruction::ADD, {A, Y}}}}, + [=]() -> Pattern { return {Instruction::ADD, {{Instruction::SUB, {X, Y}}, 0 - A.d()}}; }, + false + } + }; + return rules; +} + +} +} diff --git a/libevmasm/SimplificationRule.h b/libevmasm/SimplificationRule.h new file mode 100644 index 00000000..7b4dea68 --- /dev/null +++ b/libevmasm/SimplificationRule.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/>. +*/ +/** + * Expression simplification pattern. + */ + +#pragma once + +#include <functional> + +namespace dev +{ +namespace solidity +{ + +/** + * Rule that contains a pattern, an action that can be applied + * after the pattern has matched and a bool that indicates + * whether the action would remove something from the expression + * than is not a constant literal. + */ +template <class Pattern> +struct SimplificationRule +{ + Pattern pattern; + std::function<Pattern()> action; + bool removesNonConstants; +}; + +} +} diff --git a/libevmasm/SimplificationRules.cpp b/libevmasm/SimplificationRules.cpp index e6c51f95..53a5f9fc 100644 --- a/libevmasm/SimplificationRules.cpp +++ b/libevmasm/SimplificationRules.cpp @@ -23,7 +23,6 @@ #include <libevmasm/ExpressionClasses.h> #include <utility> -#include <tuple> #include <functional> #include <boost/range/adaptor/reversed.hpp> #include <boost/noncopyable.hpp> @@ -31,12 +30,14 @@ #include <libevmasm/CommonSubexpressionEliminator.h> #include <libevmasm/SimplificationRules.h> +#include <libevmasm/RuleList.h> + using namespace std; using namespace dev; using namespace dev::eth; -pair<Pattern, function<Pattern()> > const* Rules::findFirstMatch( +SimplificationRule<Pattern> const* Rules::findFirstMatch( Expression const& _expr, ExpressionClasses const& _classes ) @@ -46,32 +47,22 @@ pair<Pattern, function<Pattern()> > const* Rules::findFirstMatch( assertThrow(_expr.item, OptimizerException, ""); for (auto const& rule: m_rules[byte(_expr.item->instruction())]) { - if (rule.first.matches(_expr, _classes)) + if (rule.pattern.matches(_expr, _classes)) return &rule; resetMatchGroups(); } return nullptr; } -void Rules::addRules(std::vector<std::pair<Pattern, std::function<Pattern ()> > > const& _rules) +void Rules::addRules(std::vector<SimplificationRule<Pattern>> const& _rules) { for (auto const& r: _rules) addRule(r); } -void Rules::addRule(std::pair<Pattern, std::function<Pattern()> > const& _rule) +void Rules::addRule(SimplificationRule<Pattern> const& _rule) { - m_rules[byte(_rule.first.instruction())].push_back(_rule); -} - -template <class S> S divWorkaround(S const& _a, S const& _b) -{ - return (S)(bigint(_a) / bigint(_b)); -} - -template <class S> S modWorkaround(S const& _a, S const& _b) -{ - return (S)(bigint(_a) % bigint(_b)); + m_rules[byte(_rule.pattern.instruction())].push_back(_rule); } Rules::Rules() @@ -84,165 +75,13 @@ Rules::Rules() // Anything. Pattern X; Pattern Y; - Pattern Z; 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); - Z.setMatchGroup(6, m_matchGroups); - - addRules(vector<pair<Pattern, function<Pattern()>>>{ - // arithmetics on constants - {{Instruction::ADD, {A, B}}, [=]{ return A.d() + B.d(); }}, - {{Instruction::MUL, {A, B}}, [=]{ return A.d() * B.d(); }}, - {{Instruction::SUB, {A, B}}, [=]{ return A.d() - B.d(); }}, - {{Instruction::DIV, {A, B}}, [=]{ return B.d() == 0 ? 0 : divWorkaround(A.d(), B.d()); }}, - {{Instruction::SDIV, {A, B}}, [=]{ return B.d() == 0 ? 0 : s2u(divWorkaround(u2s(A.d()), u2s(B.d()))); }}, - {{Instruction::MOD, {A, B}}, [=]{ return B.d() == 0 ? 0 : modWorkaround(A.d(), B.d()); }}, - {{Instruction::SMOD, {A, B}}, [=]{ return B.d() == 0 ? 0 : s2u(modWorkaround(u2s(A.d()), u2s(B.d()))); }}, - {{Instruction::EXP, {A, B}}, [=]{ return u256(boost::multiprecision::powm(bigint(A.d()), bigint(B.d()), bigint(1) << 256)); }}, - {{Instruction::NOT, {A}}, [=]{ return ~A.d(); }}, - {{Instruction::LT, {A, B}}, [=]() -> u256 { return A.d() < B.d() ? 1 : 0; }}, - {{Instruction::GT, {A, B}}, [=]() -> u256 { return A.d() > B.d() ? 1 : 0; }}, - {{Instruction::SLT, {A, B}}, [=]() -> u256 { return u2s(A.d()) < u2s(B.d()) ? 1 : 0; }}, - {{Instruction::SGT, {A, B}}, [=]() -> u256 { return u2s(A.d()) > u2s(B.d()) ? 1 : 0; }}, - {{Instruction::EQ, {A, B}}, [=]() -> u256 { return A.d() == B.d() ? 1 : 0; }}, - {{Instruction::ISZERO, {A}}, [=]() -> u256 { return A.d() == 0 ? 1 : 0; }}, - {{Instruction::AND, {A, B}}, [=]{ return A.d() & B.d(); }}, - {{Instruction::OR, {A, B}}, [=]{ return A.d() | B.d(); }}, - {{Instruction::XOR, {A, B}}, [=]{ return A.d() ^ B.d(); }}, - {{Instruction::BYTE, {A, B}}, [=]{ return A.d() >= 32 ? 0 : (B.d() >> unsigned(8 * (31 - A.d()))) & 0xff; }}, - {{Instruction::ADDMOD, {A, B, C}}, [=]{ return C.d() == 0 ? 0 : u256((bigint(A.d()) + bigint(B.d())) % C.d()); }}, - {{Instruction::MULMOD, {A, B, C}}, [=]{ return C.d() == 0 ? 0 : u256((bigint(A.d()) * bigint(B.d())) % C.d()); }}, - {{Instruction::MULMOD, {A, B, C}}, [=]{ return A.d() * B.d(); }}, - {{Instruction::SIGNEXTEND, {A, B}}, [=]() -> u256 { - if (A.d() >= 31) - return B.d(); - unsigned testBit = unsigned(A.d()) * 8 + 7; - u256 mask = (u256(1) << testBit) - 1; - return u256(boost::multiprecision::bit_test(B.d(), testBit) ? B.d() | ~mask : B.d() & mask); - }}, - - // invariants involving known constants (commutative instructions will be checked with swapped operants too) - {{Instruction::ADD, {X, 0}}, [=]{ return X; }}, - {{Instruction::SUB, {X, 0}}, [=]{ return X; }}, - {{Instruction::MUL, {X, 0}}, [=]{ return u256(0); }}, - {{Instruction::MUL, {X, 1}}, [=]{ return X; }}, - {{Instruction::DIV, {X, 0}}, [=]{ return u256(0); }}, - {{Instruction::DIV, {0, X}}, [=]{ return u256(0); }}, - {{Instruction::DIV, {X, 1}}, [=]{ return X; }}, - {{Instruction::SDIV, {X, 0}}, [=]{ return u256(0); }}, - {{Instruction::SDIV, {0, X}}, [=]{ return u256(0); }}, - {{Instruction::SDIV, {X, 1}}, [=]{ return X; }}, - {{Instruction::AND, {X, ~u256(0)}}, [=]{ return X; }}, - {{Instruction::AND, {X, 0}}, [=]{ return u256(0); }}, - {{Instruction::OR, {X, 0}}, [=]{ return X; }}, - {{Instruction::OR, {X, ~u256(0)}}, [=]{ return ~u256(0); }}, - {{Instruction::XOR, {X, 0}}, [=]{ return X; }}, - {{Instruction::MOD, {X, 0}}, [=]{ return u256(0); }}, - {{Instruction::MOD, {0, X}}, [=]{ return u256(0); }}, - {{Instruction::EQ, {X, 0}}, [=]() -> Pattern { return {Instruction::ISZERO, {X}}; } }, - - // operations involving an expression and itself - {{Instruction::AND, {X, X}}, [=]{ return X; }}, - {{Instruction::OR, {X, X}}, [=]{ return X; }}, - {{Instruction::XOR, {X, X}}, [=]{ return u256(0); }}, - {{Instruction::SUB, {X, X}}, [=]{ return u256(0); }}, - {{Instruction::EQ, {X, X}}, [=]{ return u256(1); }}, - {{Instruction::LT, {X, X}}, [=]{ return u256(0); }}, - {{Instruction::SLT, {X, X}}, [=]{ return u256(0); }}, - {{Instruction::GT, {X, X}}, [=]{ return u256(0); }}, - {{Instruction::SGT, {X, X}}, [=]{ return u256(0); }}, - {{Instruction::MOD, {X, X}}, [=]{ return u256(0); }}, - - // logical instruction combinations - {{Instruction::NOT, {{Instruction::NOT, {X}}}}, [=]{ return X; }}, - {{Instruction::XOR, {{{X}, {Instruction::XOR, {X, Y}}}}}, [=]{ return Y; }}, - {{Instruction::OR, {{{X}, {Instruction::AND, {X, Y}}}}}, [=]{ return X; }}, - {{Instruction::AND, {{{X}, {Instruction::OR, {X, Y}}}}}, [=]{ return X; }}, - {{Instruction::AND, {{{X}, {Instruction::NOT, {X}}}}}, [=]{ return u256(0); }}, - {{Instruction::OR, {{{X}, {Instruction::NOT, {X}}}}}, [=]{ return ~u256(0); }}, - }); - - // Double negation of opcodes with binary result - for (auto const& op: vector<Instruction>{ - Instruction::EQ, - Instruction::LT, - Instruction::SLT, - Instruction::GT, - Instruction::SGT - }) - addRule({ - {Instruction::ISZERO, {{Instruction::ISZERO, {{op, {X, Y}}}}}}, - [=]() -> Pattern { return {op, {X, Y}}; } - }); - - addRule({ - {Instruction::ISZERO, {{Instruction::ISZERO, {{Instruction::ISZERO, {X}}}}}}, - [=]() -> Pattern { return {Instruction::ISZERO, {X}}; } - }); - - addRule({ - {Instruction::ISZERO, {{Instruction::XOR, {X, Y}}}}, - [=]() -> Pattern { return { Instruction::EQ, {X, Y} }; } - }); - - // Associative operations - for (auto const& opFun: vector<pair<Instruction,function<u256(u256 const&,u256 const&)>>>{ - {Instruction::ADD, plus<u256>()}, - {Instruction::MUL, multiplies<u256>()}, - {Instruction::AND, bit_and<u256>()}, - {Instruction::OR, bit_or<u256>()}, - {Instruction::XOR, bit_xor<u256>()} - }) - { - auto op = opFun.first; - auto fun = opFun.second; - // Moving constants to the outside, order matters here! - // we need actions that return expressions (or patterns?) here, and we need also reversed rules - // (X+A)+B -> X+(A+B) - addRules(vector<pair<Pattern, function<Pattern()>>>{{ - {op, {{op, {X, A}}, B}}, - [=]() -> Pattern { return {op, {X, fun(A.d(), B.d())}}; } - }, { - // X+(Y+A) -> (X+Y)+A - {op, {{op, {X, A}}, Y}}, - [=]() -> Pattern { return {op, {{op, {X, Y}}, A}}; } - }, { - // For now, we still need explicit commutativity for the inner pattern - {op, {{op, {A, X}}, B}}, - [=]() -> Pattern { return {op, {X, fun(A.d(), B.d())}}; } - }, { - {op, {{op, {A, X}}, Y}}, - [=]() -> Pattern { return {op, {{op, {X, Y}}, A}}; } - }}); - } - // move constants across subtractions - addRules(vector<pair<Pattern, function<Pattern()>>>{ - { - // X - A -> X + (-A) - {Instruction::SUB, {X, A}}, - [=]() -> Pattern { return {Instruction::ADD, {X, 0 - A.d()}}; } - }, { - // (X + A) - Y -> (X - Y) + A - {Instruction::SUB, {{Instruction::ADD, {X, A}}, Y}}, - [=]() -> Pattern { return {Instruction::ADD, {{Instruction::SUB, {X, Y}}, A}}; } - }, { - // (A + X) - Y -> (X - Y) + A - {Instruction::SUB, {{Instruction::ADD, {A, X}}, Y}}, - [=]() -> Pattern { return {Instruction::ADD, {{Instruction::SUB, {X, Y}}, A}}; } - }, { - // X - (Y + A) -> (X - Y) + (-A) - {Instruction::SUB, {X, {Instruction::ADD, {Y, A}}}}, - [=]() -> Pattern { return {Instruction::ADD, {{Instruction::SUB, {X, Y}}, 0 - A.d()}}; } - }, { - // X - (A + Y) -> (X - Y) + (-A) - {Instruction::SUB, {X, {Instruction::ADD, {A, Y}}}}, - [=]() -> Pattern { return {Instruction::ADD, {{Instruction::SUB, {X, Y}}, 0 - A.d()}}; } - } - }); + addRules(simplificationRuleList(A, B, C, X, Y)); } Pattern::Pattern(Instruction _instruction, std::vector<Pattern> const& _arguments): diff --git a/libevmasm/SimplificationRules.h b/libevmasm/SimplificationRules.h index a4da5849..53f7e595 100644 --- a/libevmasm/SimplificationRules.h +++ b/libevmasm/SimplificationRules.h @@ -24,6 +24,7 @@ #pragma once #include <libevmasm/ExpressionClasses.h> +#include <libevmasm/SimplificationRule.h> #include <functional> #include <vector> @@ -47,19 +48,21 @@ public: /// @returns a pointer to the first matching pattern and sets the match /// groups accordingly. - std::pair<Pattern, std::function<Pattern()>> const* findFirstMatch( + SimplificationRule<Pattern> const* findFirstMatch( Expression const& _expr, ExpressionClasses const& _classes ); private: - void addRules(std::vector<std::pair<Pattern, std::function<Pattern()>>> const& _rules); - void addRule(std::pair<Pattern, std::function<Pattern()>> const& _rule); + void addRules(std::vector<SimplificationRule<Pattern>> const& _rules); + void addRule(SimplificationRule<Pattern> const& _rule); void resetMatchGroups() { m_matchGroups.clear(); } std::map<unsigned, Expression const*> m_matchGroups; - std::vector<std::pair<Pattern, std::function<Pattern()>>> m_rules[256]; + /// Pattern to match, replacement to be applied and flag indicating whether + /// the replacement might remove some elements (except constants). + std::vector<SimplificationRule<Pattern>> m_rules[256]; }; /** diff --git a/libjulia/optimiser/ASTWalker.cpp b/libjulia/optimiser/ASTWalker.cpp index 6386b29d..03444984 100644 --- a/libjulia/optimiser/ASTWalker.cpp +++ b/libjulia/optimiser/ASTWalker.cpp @@ -86,8 +86,8 @@ void ASTWalker::operator()(ForLoop const& _for) { (*this)(_for.pre); visit(*_for.condition); - (*this)(_for.post); (*this)(_for.body); + (*this)(_for.post); } void ASTWalker::operator()(Block const& _block) diff --git a/libjulia/optimiser/ASTWalker.h b/libjulia/optimiser/ASTWalker.h index dbf8194b..97891381 100644 --- a/libjulia/optimiser/ASTWalker.h +++ b/libjulia/optimiser/ASTWalker.h @@ -71,8 +71,8 @@ protected: template <class T> void walkVector(T const& _statements) { - for (auto const& st: _statements) - visit(st); + for (auto const& statement: _statements) + visit(statement); } }; diff --git a/libjulia/optimiser/DataFlowAnalyzer.cpp b/libjulia/optimiser/DataFlowAnalyzer.cpp new file mode 100644 index 00000000..56653393 --- /dev/null +++ b/libjulia/optimiser/DataFlowAnalyzer.cpp @@ -0,0 +1,193 @@ +/*( + 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/>. +*/ +/** + * Base class to perform data flaw analysis during AST walks. + * Tracks assignments and is used as base class for both Rematerialiser and + * Common Subexpression Eliminator. + */ + +#include <libjulia/optimiser/DataFlowAnalyzer.h> + +#include <libjulia/optimiser/NameCollector.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libjulia/optimiser/Semantics.h> + +#include <libdevcore/CommonData.h> + +#include <boost/range/adaptor/reversed.hpp> + +using namespace std; +using namespace dev; +using namespace dev::julia; + +void DataFlowAnalyzer::operator()(Assignment& _assignment) +{ + set<string> names; + for (auto const& var: _assignment.variableNames) + names.insert(var.name); + solAssert(_assignment.value, ""); + visit(*_assignment.value); + handleAssignment(names, _assignment.value.get()); +} + +void DataFlowAnalyzer::operator()(VariableDeclaration& _varDecl) +{ + set<string> names; + for (auto const& var: _varDecl.variables) + names.insert(var.name); + m_variableScopes.back().variables += names; + if (_varDecl.value) + visit(*_varDecl.value); + handleAssignment(names, _varDecl.value.get()); +} + +void DataFlowAnalyzer::operator()(If& _if) +{ + ASTModifier::operator()(_if); + + Assignments assignments; + assignments(_if.body); + clearValues(assignments.names()); +} + +void DataFlowAnalyzer::operator()(Switch& _switch) +{ + visit(*_switch.expression); + set<string> assignedVariables; + for (auto& _case: _switch.cases) + { + (*this)(_case.body); + Assignments assignments; + assignments(_case.body); + assignedVariables += assignments.names(); + // This is a little too destructive, we could retain the old values. + clearValues(assignments.names()); + } + clearValues(assignedVariables); +} + +void DataFlowAnalyzer::operator()(FunctionDefinition& _fun) +{ + m_variableScopes.emplace_back(true); + for (auto const& parameter: _fun.parameters) + m_variableScopes.back().variables.insert(parameter.name); + for (auto const& var: _fun.returnVariables) + m_variableScopes.back().variables.insert(var.name); + ASTModifier::operator()(_fun); + m_variableScopes.pop_back(); +} + +void DataFlowAnalyzer::operator()(ForLoop& _for) +{ + // Special scope handling of the pre block. + m_variableScopes.emplace_back(false); + for (auto& statement: _for.pre.statements) + visit(statement); + + Assignments assignments; + assignments(_for.body); + assignments(_for.post); + clearValues(assignments.names()); + + visit(*_for.condition); + (*this)(_for.body); + (*this)(_for.post); + + clearValues(assignments.names()); + + m_variableScopes.pop_back(); +} + +void DataFlowAnalyzer::operator()(Block& _block) +{ + size_t numScopes = m_variableScopes.size(); + m_variableScopes.emplace_back(false); + ASTModifier::operator()(_block); + m_variableScopes.pop_back(); + solAssert(numScopes == m_variableScopes.size(), ""); +} + +void DataFlowAnalyzer::handleAssignment(set<string> const& _variables, Expression* _value) +{ + clearValues(_variables); + + MovableChecker movableChecker; + if (_value) + movableChecker.visit(*_value); + if (_variables.size() == 1) + { + string const& name = *_variables.begin(); + // Expression has to be movable and cannot contain a reference + // to the variable that will be assigned to. + if (_value && movableChecker.movable() && !movableChecker.referencedVariables().count(name)) + m_value[name] = _value; + } + + auto const& referencedVariables = movableChecker.referencedVariables(); + for (auto const& name: _variables) + { + m_references[name] = referencedVariables; + for (auto const& ref: referencedVariables) + m_referencedBy[ref].insert(name); + } +} + +void DataFlowAnalyzer::clearValues(set<string> const& _variables) +{ + // All variables that reference variables to be cleared also have to be + // cleared, but not recursively, since only the value of the original + // variables changes. Example: + // let a := 1 + // let b := a + // let c := b + // let a := 2 + // add(b, c) + // In the last line, we can replace c by b, but not b by a. + // + // This cannot be easily tested since the substitutions will be done + // one by one on the fly, and the last line will just be add(1, 1) + + set<string> variables = _variables; + // Clear variables that reference variables to be cleared. + for (auto const& name: variables) + for (auto const& ref: m_referencedBy[name]) + variables.insert(ref); + + // Clear the value and update the reference relation. + for (auto const& name: variables) + m_value.erase(name); + for (auto const& name: variables) + { + for (auto const& ref: m_references[name]) + m_referencedBy[ref].erase(name); + m_references[name].clear(); + } +} + +bool DataFlowAnalyzer::inScope(string const& _variableName) const +{ + for (auto const& scope: m_variableScopes | boost::adaptors::reversed) + { + if (scope.variables.count(_variableName)) + return true; + if (scope.isFunction) + return false; + } + return false; +} diff --git a/libjulia/optimiser/DataFlowAnalyzer.h b/libjulia/optimiser/DataFlowAnalyzer.h new file mode 100644 index 00000000..4cb3d4cd --- /dev/null +++ b/libjulia/optimiser/DataFlowAnalyzer.h @@ -0,0 +1,84 @@ +/* + 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/>. +*/ +/** + * Base class to perform data flow analysis during AST walks. + * Tracks assignments and is used as base class for both Rematerialiser and + * Common Subexpression Eliminator. + */ + +#pragma once + +#include <libjulia/optimiser/ASTWalker.h> + +#include <string> +#include <map> +#include <set> + +namespace dev +{ +namespace julia +{ + +/** + * Base class to perform data flow analysis during AST walks. + * Tracks assignments and is used as base class for both Rematerialiser and + * Common Subexpression Eliminator. + * + * Prerequisite: Disambiguator + */ +class DataFlowAnalyzer: public ASTModifier +{ +public: + using ASTModifier::operator(); + virtual void operator()(Assignment& _assignment) override; + virtual void operator()(VariableDeclaration& _varDecl) override; + virtual void operator()(If& _if) override; + virtual void operator()(Switch& _switch) override; + virtual void operator()(FunctionDefinition&) override; + virtual void operator()(ForLoop&) override; + virtual void operator()(Block& _block) override; + +protected: + /// Registers the assignment. + void handleAssignment(std::set<std::string> const& _names, Expression* _value); + + /// Clears information about the valuse assigned to the given variables, + /// for example at points where control flow is merged. + void clearValues(std::set<std::string> const& _names); + + /// Returns true iff the variable is in scope. + bool inScope(std::string const& _variableName) const; + + /// Current values of variables, always movable. + std::map<std::string, Expression const*> m_value; + /// m_references[a].contains(b) <=> the current expression assigned to a references b + std::map<std::string, std::set<std::string>> m_references; + /// m_referencedBy[b].contains(a) <=> the current expression assigned to a references b + std::map<std::string, std::set<std::string>> m_referencedBy; + + struct Scope + { + explicit Scope(bool _isFunction): isFunction(_isFunction) {} + std::set<std::string> variables; + bool isFunction; + }; + /// List of scopes. + std::vector<Scope> m_variableScopes; +}; + +} +} diff --git a/libjulia/optimiser/ExpressionInliner.cpp b/libjulia/optimiser/ExpressionInliner.cpp new file mode 100644 index 00000000..450769fd --- /dev/null +++ b/libjulia/optimiser/ExpressionInliner.cpp @@ -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/>. +*/ +/** + * Optimiser component that performs function inlining inside expressions. + */ + +#include <libjulia/optimiser/ExpressionInliner.h> + +#include <libjulia/optimiser/InlinableExpressionFunctionFinder.h> +#include <libjulia/optimiser/Substitution.h> +#include <libjulia/optimiser/Semantics.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <boost/algorithm/cxx11/all_of.hpp> + +using namespace std; +using namespace dev; +using namespace dev::julia; +using namespace dev::solidity; + +void ExpressionInliner::run() +{ + InlinableExpressionFunctionFinder funFinder; + funFinder(m_block); + m_inlinableFunctions = funFinder.inlinableFunctions(); + + (*this)(m_block); +} + + +void ExpressionInliner::operator()(FunctionDefinition& _fun) +{ + ASTModifier::operator()(_fun); +} + +void ExpressionInliner::visit(Expression& _expression) +{ + ASTModifier::visit(_expression); + if (_expression.type() == typeid(FunctionCall)) + { + FunctionCall& funCall = boost::get<FunctionCall>(_expression); + + bool movable = boost::algorithm::all_of( + funCall.arguments, + [=](Expression const& _arg) { return MovableChecker(_arg).movable(); } + ); + if (m_inlinableFunctions.count(funCall.functionName.name) && movable) + { + FunctionDefinition const& fun = *m_inlinableFunctions.at(funCall.functionName.name); + map<string, Expression const*> substitutions; + for (size_t i = 0; i < fun.parameters.size(); ++i) + substitutions[fun.parameters[i].name] = &funCall.arguments[i]; + _expression = Substitution(substitutions).translate(*boost::get<Assignment>(fun.body.statements.front()).value); + + // TODO Add metric! This metric should perform well on a pair of functions who + // call each other recursively. + } + } +} diff --git a/libjulia/optimiser/ExpressionInliner.h b/libjulia/optimiser/ExpressionInliner.h new file mode 100644 index 00000000..10d7659c --- /dev/null +++ b/libjulia/optimiser/ExpressionInliner.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/>. +*/ +/** + * Optimiser component that performs function inlining. + */ +#pragma once + +#include <libjulia/optimiser/ASTWalker.h> + +#include <libjulia/ASTDataForward.h> + +#include <libsolidity/interface/Exceptions.h> + +#include <boost/variant.hpp> +#include <boost/optional.hpp> + +#include <set> + +namespace dev +{ +namespace julia +{ + +/** + * Optimiser component that modifies an AST in place, inlining functions that can be + * inlined inside functional expressions, i.e. functions that + * - return a single value + * - have a body like r := <functional expression> + * - neither reference themselves nor r in the right hand side + * + * Furthermore, the arguments of the function call cannot have any side-effects. + * + * This component can only be used on sources with unique names. + */ +class ExpressionInliner: public ASTModifier +{ +public: + ExpressionInliner(Block& _block): + m_block(_block) + {} + + void run(); + + using ASTModifier::operator(); + virtual void operator()(FunctionDefinition& _fun) override; + + virtual void visit(Expression& _expression) override; + +private: + std::map<std::string, FunctionDefinition const*> m_inlinableFunctions; + std::map<std::string, std::string> m_varReplacements; + /// Set of functions we are currently visiting inside. + std::set<std::string> m_currentFunctions; + + Block& m_block; +}; + + +} +} diff --git a/libjulia/optimiser/ExpressionSimplifier.cpp b/libjulia/optimiser/ExpressionSimplifier.cpp new file mode 100644 index 00000000..3d471cb3 --- /dev/null +++ b/libjulia/optimiser/ExpressionSimplifier.cpp @@ -0,0 +1,50 @@ +/* + 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)) + { + // 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". + if (match->removesNonConstants && !MovableChecker(_expression).movable()) + return; + _expression = match->action().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/InlinableExpressionFunctionFinder.cpp b/libjulia/optimiser/InlinableExpressionFunctionFinder.cpp new file mode 100644 index 00000000..2097e091 --- /dev/null +++ b/libjulia/optimiser/InlinableExpressionFunctionFinder.cpp @@ -0,0 +1,70 @@ +/* + 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 identifies functions to be inlined. + */ + +#include <libjulia/optimiser/InlinableExpressionFunctionFinder.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libsolidity/interface/Exceptions.h> + +using namespace std; +using namespace dev; +using namespace dev::julia; + +void InlinableExpressionFunctionFinder::operator()(Identifier const& _identifier) +{ + checkAllowed(_identifier.name); + ASTWalker::operator()(_identifier); +} + +void InlinableExpressionFunctionFinder::operator()(FunctionCall const& _funCall) +{ + checkAllowed(_funCall.functionName.name); + ASTWalker::operator()(_funCall); +} + +void InlinableExpressionFunctionFinder::operator()(FunctionDefinition const& _function) +{ + if (_function.returnVariables.size() == 1 && _function.body.statements.size() == 1) + { + string const& retVariable = _function.returnVariables.front().name; + Statement const& bodyStatement = _function.body.statements.front(); + if (bodyStatement.type() == typeid(Assignment)) + { + Assignment const& assignment = boost::get<Assignment>(bodyStatement); + if (assignment.variableNames.size() == 1 && assignment.variableNames.front().name == retVariable) + { + // FIXME: use code size metric here + + // We cannot overwrite previous settings, because this function definition + // would not be valid here if we were searching inside a functionally inlinable + // function body. + solAssert(m_disallowedIdentifiers.empty() && !m_foundDisallowedIdentifier, ""); + m_disallowedIdentifiers = set<string>{retVariable, _function.name}; + boost::apply_visitor(*this, *assignment.value); + if (!m_foundDisallowedIdentifier) + m_inlinableFunctions[_function.name] = &_function; + m_disallowedIdentifiers.clear(); + m_foundDisallowedIdentifier = false; + } + } + } + ASTWalker::operator()(_function.body); +} diff --git a/libjulia/optimiser/InlinableExpressionFunctionFinder.h b/libjulia/optimiser/InlinableExpressionFunctionFinder.h new file mode 100644 index 00000000..36cb557a --- /dev/null +++ b/libjulia/optimiser/InlinableExpressionFunctionFinder.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 identifies functions to be inlined. + */ + +#pragma once + +#include <libjulia/ASTDataForward.h> +#include <libjulia/optimiser/ASTWalker.h> + +#include <libsolidity/interface/Exceptions.h> + +#include <set> + +namespace dev +{ +namespace julia +{ + +/** + * Optimiser component that finds functions that can be + * inlined inside functional expressions, i.e. functions that + * - have a single return parameter r + * - have a body like r := <functional expression> + * - neither reference themselves nor r in the right hand side + * + * This component can only be used on sources with unique names. + */ +class InlinableExpressionFunctionFinder: public ASTWalker +{ +public: + + std::map<std::string, FunctionDefinition const*> const& inlinableFunctions() const + { + return m_inlinableFunctions; + } + + using ASTWalker::operator(); + virtual void operator()(Identifier const& _identifier) override; + virtual void operator()(FunctionCall const& _funCall) override; + virtual void operator()(FunctionDefinition const& _function) override; + +private: + void checkAllowed(std::string const& _name) + { + if (m_disallowedIdentifiers.count(_name)) + m_foundDisallowedIdentifier = true; + } + + bool m_foundDisallowedIdentifier = false; + std::set<std::string> m_disallowedIdentifiers; + std::map<std::string, FunctionDefinition const*> m_inlinableFunctions; +}; + +} +} diff --git a/libjulia/optimiser/NameCollector.cpp b/libjulia/optimiser/NameCollector.cpp index 7b4c4793..510ee289 100644 --- a/libjulia/optimiser/NameCollector.cpp +++ b/libjulia/optimiser/NameCollector.cpp @@ -42,3 +42,34 @@ void NameCollector::operator ()(FunctionDefinition const& _funDef) m_names.insert(ret.name); ASTWalker::operator ()(_funDef); } + +void ReferencesCounter::operator()(Identifier const& _identifier) +{ + ++m_references[_identifier.name]; +} + +void ReferencesCounter::operator()(FunctionCall const& _funCall) +{ + ++m_references[_funCall.functionName.name]; + ASTWalker::operator()(_funCall); +} + +map<string, size_t> ReferencesCounter::countReferences(Block const& _block) +{ + ReferencesCounter counter; + counter(_block); + return counter.references(); +} + +map<string, size_t> ReferencesCounter::countReferences(Expression const& _expression) +{ + ReferencesCounter counter; + counter.visit(_expression); + return counter.references(); +} + +void Assignments::operator()(Assignment const& _assignment) +{ + for (auto const& var: _assignment.variableNames) + m_names.insert(var.name); +} diff --git a/libjulia/optimiser/NameCollector.h b/libjulia/optimiser/NameCollector.h index b7e38f46..2d4a1d4b 100644 --- a/libjulia/optimiser/NameCollector.h +++ b/libjulia/optimiser/NameCollector.h @@ -15,7 +15,7 @@ along with solidity. If not, see <http://www.gnu.org/licenses/>. */ /** - * Specific AST walker that collects all defined names. + * Specific AST walkers that collect facts about identifiers and definitions. */ #pragma once @@ -48,5 +48,37 @@ private: std::map<std::string, FunctionDefinition const*> m_functions; }; +/** + * Specific AST walker that counts all references to all declarations. + */ +class ReferencesCounter: public ASTWalker +{ +public: + using ASTWalker::operator (); + virtual void operator()(Identifier const& _identifier); + virtual void operator()(FunctionCall const& _funCall); + + static std::map<std::string, size_t> countReferences(Block const& _block); + static std::map<std::string, size_t> countReferences(Expression const& _expression); + + std::map<std::string, size_t> const& references() const { return m_references; } +private: + std::map<std::string, size_t> m_references; +}; + +/** + * Specific AST walker that finds all variables that are assigned to. + */ +class Assignments: public ASTWalker +{ +public: + using ASTWalker::operator (); + virtual void operator()(Assignment const& _assignment) override; + + std::set<std::string> const& names() const { return m_names; } +private: + std::set<std::string> m_names; +}; + } } diff --git a/libjulia/optimiser/README.md b/libjulia/optimiser/README.md index 771cb707..e7134440 100644 --- a/libjulia/optimiser/README.md +++ b/libjulia/optimiser/README.md @@ -54,8 +54,36 @@ As an example, neither ``mload`` nor ``mstore`` would be allowed. ## Full Function Inliner -## Variable Eliminator +## Rematerialisation + +The rematerialisation stage tries to replace variable references by the expression that +was last assigned to the variable. This is of course only beneficial if this expression +is comparatively cheap to evaluate. Furthermore, it is only semantically equivalent if +the value of the expression did not change between the point of assignment and the +point of use. The main benefit of this stage is that it can save stack slots if it +leads to a variable being eliminated completely (see below), but it can also +save a DUP opcode on the EVM if the expression is very cheap. + +The algorithm only allows movable expressions (see above for a definition) in this case. +Expressions that contain other variables are also disallowed if one of those variables +have been assigned to in the meantime. This is also not applied to variables where +assignment and use span across loops and conditionals. + +## Unused Definition Pruner + +If a variable or function is not referenced, it is removed from the code. +If there are two assignments to a variable where the first one is a movable expression +and the variable is not used between the two assignments (and the second is not inside +a loop or conditional, the first one is not inside), the first assignment is removed. -## Unused Declaration Pruner ## Function Unifier + +## Expression Simplifier + +This step can only be applied for the EVM-flavoured dialect of iulia. It applies +simple rules like ``x + 0 == x`` to simplify expressions. + +## Ineffective Statement Remover + +This step removes statements that have no side-effects. diff --git a/libjulia/optimiser/Rematerialiser.cpp b/libjulia/optimiser/Rematerialiser.cpp new file mode 100644 index 00000000..eaa75e33 --- /dev/null +++ b/libjulia/optimiser/Rematerialiser.cpp @@ -0,0 +1,54 @@ +/*( + 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/>. +*/ +/** + * Optimisation stage that replaces variables by their most recently assigned expressions. + */ + +#include <libjulia/optimiser/Rematerialiser.h> + +#include <libjulia/optimiser/Metrics.h> +#include <libjulia/optimiser/ASTCopier.h> + +#include <libsolidity/inlineasm/AsmData.h> + +using namespace std; +using namespace dev; +using namespace dev::julia; + +void Rematerialiser::visit(Expression& _e) +{ + if (_e.type() == typeid(Identifier)) + { + Identifier& identifier = boost::get<Identifier>(_e); + if (m_value.count(identifier.name)) + { + string name = identifier.name; + bool expressionValid = true; + for (auto const& ref: m_references[name]) + if (!inScope(ref)) + { + expressionValid = false; + break; + } + solAssert(m_value.at(name), ""); + auto const& value = *m_value.at(name); + if (expressionValid && CodeSize::codeSize(value) <= 7) + _e = (ASTCopier{}).translate(value); + } + } + DataFlowAnalyzer::visit(_e); +} diff --git a/libjulia/optimiser/Rematerialiser.h b/libjulia/optimiser/Rematerialiser.h new file mode 100644 index 00000000..60dbfada --- /dev/null +++ b/libjulia/optimiser/Rematerialiser.h @@ -0,0 +1,48 @@ +/* + 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/>. +*/ +/** + * Optimisation stage that replaces variables by their most recently assigned expressions. + */ + +#pragma once + +#include <libjulia/optimiser/DataFlowAnalyzer.h> + +#include <string> +#include <map> +#include <set> + +namespace dev +{ +namespace julia +{ + +/** + * Optimisation stage that replaces variables by their most recently assigned expressions. + * + * Prerequisite: Disambiguator + */ +class Rematerialiser: public DataFlowAnalyzer +{ +protected: + using ASTModifier::visit; + virtual void visit(Expression& _e) override; + +}; + +} +} diff --git a/libjulia/optimiser/SimplificationRules.cpp b/libjulia/optimiser/SimplificationRules.cpp new file mode 100644 index 00000000..a439caef --- /dev/null +++ b/libjulia/optimiser/SimplificationRules.cpp @@ -0,0 +1,182 @@ +/* + 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 <libjulia/optimiser/Semantics.h> +#include <libjulia/optimiser/SyntacticalEquality.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libevmasm/RuleList.h> + +using namespace std; +using namespace dev; +using namespace dev::julia; + + +SimplificationRule<Pattern> 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 (rule.pattern.matches(_expr)) + return &rule; + } + return nullptr; +} + +void SimplificationRules::addRules(vector<SimplificationRule<Pattern>> const& _rules) +{ + for (auto const& r: _rules) + addRule(r); +} + +void SimplificationRules::addRule(SimplificationRule<Pattern> const& _rule) +{ + m_rules[byte(_rule.pattern.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 support matching multiple expressions that require the same value + // based on identical ASTs, which have to be movable. + if (m_matchGroup) + { + if (m_matchGroups->count(m_matchGroup)) + { + Expression const* firstMatch = (*m_matchGroups)[m_matchGroup]; + assertThrow(firstMatch, OptimizerException, "Match set but to null."); + return + SyntacticalEqualityChecker::equal(*firstMatch, _expr) && + MovableChecker(_expr).movable(); + } + else + (*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..68b640b1 --- /dev/null +++ b/libjulia/optimiser/SimplificationRules.h @@ -0,0 +1,117 @@ +/* + 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 <libevmasm/SimplificationRule.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 SimplificationRule<Pattern> const* findFirstMatch(Expression const& _expr); + +private: + void addRules(std::vector<SimplificationRule<Pattern>> const& _rules); + void addRule(SimplificationRule<Pattern> const& _rule); + + void resetMatchGroups() { m_matchGroups.clear(); } + + std::map<unsigned, Expression const*> m_matchGroups; + std::vector<SimplificationRule<Pattern>> 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/libjulia/optimiser/SyntacticalEquality.cpp b/libjulia/optimiser/SyntacticalEquality.cpp new file mode 100644 index 00000000..2b90b091 --- /dev/null +++ b/libjulia/optimiser/SyntacticalEquality.cpp @@ -0,0 +1,75 @@ +/*( + 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/>. +*/ +/** + * Component that can compare ASTs for equality on a syntactic basis. + */ + +#include <libjulia/optimiser/SyntacticalEquality.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; + +bool SyntacticalEqualityChecker::equal(Expression const& _e1, Expression const& _e2) +{ + if (_e1.type() != _e2.type()) + return false; + + // 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; + } + else + { + solAssert(false, "Invlid expression"); + } + return false; +} + +bool SyntacticalEqualityChecker::equalVector(vector<Expression> const& _e1, vector<Expression> const& _e2) +{ + return _e1.size() == _e2.size() && + std::equal(begin(_e1), end(_e1), begin(_e2), SyntacticalEqualityChecker::equal); + +} diff --git a/libjulia/optimiser/SyntacticalEquality.h b/libjulia/optimiser/SyntacticalEquality.h new file mode 100644 index 00000000..b7c09330 --- /dev/null +++ b/libjulia/optimiser/SyntacticalEquality.h @@ -0,0 +1,50 @@ +/* + 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/>. +*/ +/** + * Component that can compare ASTs for equality on a syntactic basis. + */ + +#pragma once + +#include <libjulia/ASTDataForward.h> + +#include <vector> + +namespace dev +{ +namespace julia +{ + +/** + * Component that can compare ASTs for equality on a syntactic basis. + * Ignores source locations 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. + */ +class SyntacticalEqualityChecker +{ +public: + static bool equal(Expression const& _e1, Expression const& _e2); + +protected: + static bool equalVector(std::vector<Expression> const& _e1, std::vector<Expression> const& _e2); +}; + +} +} diff --git a/libjulia/optimiser/UnusedPruner.cpp b/libjulia/optimiser/UnusedPruner.cpp new file mode 100644 index 00000000..50038431 --- /dev/null +++ b/libjulia/optimiser/UnusedPruner.cpp @@ -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/>. +*/ +/** + * Optimisation stage that removes unused variables and functions. + */ + +#include <libjulia/optimiser/UnusedPruner.h> + +#include <libjulia/optimiser/NameCollector.h> +#include <libjulia/optimiser/Semantics.h> +#include <libjulia/optimiser/Utilities.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <boost/algorithm/cxx11/none_of.hpp> + +using namespace std; +using namespace dev; +using namespace dev::julia; + +UnusedPruner::UnusedPruner(Block& _ast) +{ + ReferencesCounter counter; + counter(_ast); + + m_references = counter.references(); +} + +void UnusedPruner::operator()(Block& _block) +{ + for (auto&& statement: _block.statements) + if (statement.type() == typeid(FunctionDefinition)) + { + FunctionDefinition& funDef = boost::get<FunctionDefinition>(statement); + if (!used(funDef.name)) + { + subtractReferences(ReferencesCounter::countReferences(funDef.body)); + statement = Block{std::move(funDef.location), {}}; + } + } + else if (statement.type() == typeid(VariableDeclaration)) + { + VariableDeclaration& varDecl = boost::get<VariableDeclaration>(statement); + // Multi-variable declarations are special. We can only remove it + // if all vairables are unused and the right-hand-side is either + // movable or it return a single value. In the latter case, we + // replace `let a := f()` by `pop(f())` (in pure IULIA, this will be + // `drop(f())`). + if (boost::algorithm::none_of( + varDecl.variables, + [=](TypedName const& _typedName) { return used(_typedName.name); } + )) + { + if (!varDecl.value) + statement = Block{std::move(varDecl.location), {}}; + else if (MovableChecker(*varDecl.value).movable()) + { + subtractReferences(ReferencesCounter::countReferences(*varDecl.value)); + statement = Block{std::move(varDecl.location), {}}; + } + else if (varDecl.variables.size() == 1) + // In pure IULIA, this should be replaced by a function call to `drop` + // instead of `pop`. + statement = ExpressionStatement{varDecl.location, FunctionalInstruction{ + varDecl.location, + solidity::Instruction::POP, + {*std::move(varDecl.value)} + }}; + } + } + + removeEmptyBlocks(_block); + + ASTModifier::operator()(_block); +} + +void UnusedPruner::runUntilStabilised(Block& _ast) +{ + while (true) + { + UnusedPruner pruner(_ast); + pruner(_ast); + if (!pruner.shouldRunAgain()) + return; + } +} + +bool UnusedPruner::used(string const& _name) const +{ + return m_references.count(_name) && m_references.at(_name) > 0; +} + +void UnusedPruner::subtractReferences(map<string, size_t> const& _subtrahend) +{ + for (auto const& ref: _subtrahend) + { + solAssert(m_references.count(ref.first), ""); + solAssert(m_references.at(ref.first) >= ref.second, ""); + m_references[ref.first] -= ref.second; + m_shouldRunAgain = true; + } +} diff --git a/libjulia/optimiser/UnusedPruner.h b/libjulia/optimiser/UnusedPruner.h new file mode 100644 index 00000000..73e8de7c --- /dev/null +++ b/libjulia/optimiser/UnusedPruner.h @@ -0,0 +1,67 @@ +/* + 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/>. +*/ +/** + * Optimisation stage that removes unused variables and functions. + */ + +#pragma once + +#include <libjulia/optimiser/ASTWalker.h> + +#include <string> +#include <map> +#include <set> + +namespace dev +{ +namespace julia +{ + +/** + * Optimisation stage that removes unused variables and functions. + * + * TODO: Also remove intermediate variable assignments from movable expressions + * which are not referenced until after the next assignment to the same variable. + * + * Note that this does not remove circular references. + * + * Prerequisite: Disambiguator + */ +class UnusedPruner: public ASTModifier +{ +public: + explicit UnusedPruner(Block& _ast); + + using ASTModifier::operator(); + virtual void operator()(Block& _block) override; + + // @returns true iff the code changed in the previous run. + bool shouldRunAgain() const { return m_shouldRunAgain; } + + // Run the pruner until the code does not change anymore. + static void runUntilStabilised(Block& _ast); + +private: + bool used(std::string const& _name) const; + void subtractReferences(std::map<std::string, size_t> const& _subtrahend); + + bool m_shouldRunAgain = false; + std::map<std::string, size_t> m_references; +}; + +} +} diff --git a/libjulia/optimiser/Utilities.cpp b/libjulia/optimiser/Utilities.cpp new file mode 100644 index 00000000..ff108b89 --- /dev/null +++ b/libjulia/optimiser/Utilities.cpp @@ -0,0 +1,39 @@ +/*( + 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/>. +*/ +/** + * Some useful snippets for the optimiser. + */ + +#include <libjulia/optimiser/Utilities.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libdevcore/CommonData.h> + +#include <boost/range/algorithm_ext/erase.hpp> + +using namespace std; +using namespace dev; +using namespace dev::julia; + +void dev::julia::removeEmptyBlocks(Block& _block) +{ + auto isEmptyBlock = [](Statement const& _st) -> bool { + return _st.type() == typeid(Block) && boost::get<Block>(_st).statements.empty(); + }; + boost::range::remove_erase_if(_block.statements, isEmptyBlock); +} diff --git a/libjulia/optimiser/Utilities.h b/libjulia/optimiser/Utilities.h new file mode 100644 index 00000000..e3b4b087 --- /dev/null +++ b/libjulia/optimiser/Utilities.h @@ -0,0 +1,39 @@ +/* + 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/>. +*/ +/** + * Small useful snippets for the optimiser. + */ + +#pragma once + +#include <libjulia/ASTDataForward.h> + +#include <libdevcore/Exceptions.h> + +namespace dev +{ +namespace julia +{ + +struct IuliaException: virtual Exception {}; +struct OptimizerException: virtual IuliaException {}; + +/// Removes statements that are just empty blocks (non-recursive). +void removeEmptyBlocks(Block& _block); + +} +} diff --git a/scripts/travis-emscripten/build_emscripten.sh b/scripts/travis-emscripten/build_emscripten.sh index 56826997..fd643429 100755 --- a/scripts/travis-emscripten/build_emscripten.sh +++ b/scripts/travis-emscripten/build_emscripten.sh @@ -42,6 +42,15 @@ fi WORKSPACE=/root/project +# Increase nodejs stack size +if [ -e ~/.emscripten ] +then + sed -i -e 's/NODE_JS="nodejs"/NODE_JS=["nodejs", "--stack_size=8192"]/' ~/.emscripten +else + echo 'NODE_JS=["nodejs", "--stack_size=8192"]' > ~/.emscripten +fi + + # Boost echo -en 'travis_fold:start:compiling_boost\\r' cd "$WORKSPACE"/boost_1_57_0 diff --git a/test/libjulia/Inliner.cpp b/test/libjulia/Inliner.cpp new file mode 100644 index 00000000..88b51f28 --- /dev/null +++ b/test/libjulia/Inliner.cpp @@ -0,0 +1,199 @@ +/* + 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 iulia function inliner. + */ + +#include <test/libjulia/Common.h> + +#include <libjulia/optimiser/ExpressionInliner.h> +#include <libjulia/optimiser/InlinableExpressionFunctionFinder.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; + +namespace +{ +string inlinableFunctions(string const& _source) +{ + auto ast = disambiguate(_source); + + InlinableExpressionFunctionFinder funFinder; + funFinder(ast); + + return boost::algorithm::join( + funFinder.inlinableFunctions() | boost::adaptors::map_keys, + "," + ); +} + +string inlineFunctions(string const& _source, bool _julia = true) +{ + auto ast = disambiguate(_source, _julia); + ExpressionInliner(ast).run(); + return assembly::AsmPrinter(_julia)(ast); +} +} + +BOOST_AUTO_TEST_SUITE(IuliaInlinableFunctionFilter) + +BOOST_AUTO_TEST_CASE(smoke_test) +{ + BOOST_CHECK_EQUAL(inlinableFunctions("{ }"), ""); +} + +BOOST_AUTO_TEST_CASE(simple) +{ + BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256 { x := 2:u256 } }"), "f"); + BOOST_CHECK_EQUAL(inlinableFunctions("{" + "function g(a:u256) -> b:u256 { b := a }" + "function f() -> x:u256 { x := g(2:u256) }" + "}"), "f,g"); +} + +BOOST_AUTO_TEST_CASE(simple_inside_structures) +{ + BOOST_CHECK_EQUAL(inlinableFunctions("{" + "switch 2:u256 " + "case 2:u256 {" + "function g(a:u256) -> b:u256 { b := a }" + "function f() -> x:u256 { x := g(2:u256) }" + "}" + "}"), "f,g"); + BOOST_CHECK_EQUAL(inlinableFunctions("{" + "for {" + "function g(a:u256) -> b:u256 { b := a }" + "} 1:u256 {" + "function f() -> x:u256 { x := g(2:u256) }" + "}" + "{" + "function h() -> y:u256 { y := 2:u256 }" + "}" + "}"), "f,g,h"); +} + +BOOST_AUTO_TEST_CASE(negative) +{ + BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256 { } }"), ""); + BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256 { x := 2:u256 {} } }"), ""); + BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256 { x := f() } }"), ""); + BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256 { x := x } }"), ""); + BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256, y:u256 { x := 2:u256 } }"), ""); +} + + +BOOST_AUTO_TEST_SUITE_END() + +BOOST_AUTO_TEST_SUITE(IuliaFunctionInliner) + +BOOST_AUTO_TEST_CASE(simple) +{ + BOOST_CHECK_EQUAL( + inlineFunctions("{ function f() -> x:u256 { x := 2:u256 } let y:u256 := f() }"), + format("{ function f() -> x:u256 { x := 2:u256 } let y:u256 := 2:u256 }") + ); +} + +BOOST_AUTO_TEST_CASE(with_args) +{ + BOOST_CHECK_EQUAL( + inlineFunctions("{ function f(a:u256) -> x:u256 { x := a } let y:u256 := f(7:u256) }"), + format("{ function f(a:u256) -> x:u256 { x := a } let y:u256 := 7:u256 }") + ); +} + +BOOST_AUTO_TEST_CASE(no_inline_with_mload) +{ + // Does not inline because mload could be moved out of sequence + BOOST_CHECK_EQUAL( + inlineFunctions("{ function f(a) -> x { x := a } let y := f(mload(2)) }", false), + format("{ function f(a) -> x { x := a } let y := f(mload(2)) }", false) + ); +} + +BOOST_AUTO_TEST_CASE(no_move_with_side_effects) +{ + // The calls to g and h cannot be moved because g and h are not movable. Therefore, the call + // to f is not inlined. + BOOST_CHECK_EQUAL( + inlineFunctions("{" + "function f(a, b) -> x { x := add(b, a) }" + "function g() -> y { y := mload(0) mstore(0, 4) }" + "function h() -> z { mstore(0, 4) z := mload(0) }" + "let r := f(g(), h())" + "}", false), + format("{" + "function f(a, b) -> x { x := add(b, a) }" + "function g() -> y { y := mload(0) mstore(0, 4) }" + "function h() -> z { mstore(0, 4) z := mload(0) }" + "let r := f(g(), h())" + "}", false) + ); +} + +BOOST_AUTO_TEST_CASE(complex_with_evm) +{ + BOOST_CHECK_EQUAL( + inlineFunctions("{ function f(a) -> x { x := add(a, a) } let y := f(calldatasize()) }", false), + format("{ function f(a) -> x { x := add(a, a) } let y := add(calldatasize(), calldatasize()) }", false) + ); +} + +BOOST_AUTO_TEST_CASE(double_calls) +{ + BOOST_CHECK_EQUAL( + inlineFunctions("{" + "function f(a) -> x { x := add(a, a) }" + "function g(b, c) -> y { y := mul(mload(c), f(b)) }" + "let y := g(calldatasize(), 7)" + "}", false), + format("{" + "function f(a) -> x { x := add(a, a) }" + "function g(b, c) -> y { y := mul(mload(c), add(b, b)) }" + "let y_1 := mul(mload(7), add(calldatasize(), calldatasize()))" + "}", false) + ); +} + +BOOST_AUTO_TEST_CASE(double_recursive_calls) +{ + BOOST_CHECK_EQUAL( + inlineFunctions("{" + "function f(a, r) -> x { x := g(a, g(r, r)) }" + "function g(b, s) -> y { y := f(b, f(s, s)) }" + "let y := g(calldatasize(), 7)" + "}", false), + format("{" + "function f(a, r) -> x { x := g(a, f(r, f(r, r))) }" + "function g(b, s) -> y { y := f(b, g(s, f(s, f(s, s))))}" + "let y_1 := f(calldatasize(), g(7, f(7, f(7, 7))))" + "}", false) + ); +} + +BOOST_AUTO_TEST_SUITE_END() diff --git a/test/libjulia/Rematerialiser.cpp b/test/libjulia/Rematerialiser.cpp new file mode 100644 index 00000000..8f928f8e --- /dev/null +++ b/test/libjulia/Rematerialiser.cpp @@ -0,0 +1,179 @@ +/* + 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 rematerialiser optimizer stage. + */ + +#include <test/libjulia/Common.h> + +#include <libjulia/optimiser/Rematerialiser.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 = disambiguate(_original, false);\ + (Rematerialiser{})(b);\ + string result = p(b);\ + BOOST_CHECK_EQUAL(result, format(_expectation, false));\ +}\ +while(false) + +BOOST_AUTO_TEST_SUITE(IuliaRematerialiser) + +BOOST_AUTO_TEST_CASE(smoke_test) +{ + CHECK("{ }", "{ }"); +} + +BOOST_AUTO_TEST_CASE(trivial) +{ + CHECK( + "{ let a := 1 let b := a mstore(0, b) }", + "{ let a := 1 let b := 1 mstore(0, 1) }" + ); +} + +BOOST_AUTO_TEST_CASE(expression) +{ + CHECK( + "{ let a := add(mul(calldatasize(), 2), number()) let b := add(a, a) }", + "{ let a := add(mul(calldatasize(), 2), number()) let b := add(" + "add(mul(calldatasize(), 2), number())," + "add(mul(calldatasize(), 2), number())" + ") }" + ); +} + +BOOST_AUTO_TEST_CASE(reassign) +{ + CHECK( + "{ let a := extcodesize(0) let b := a let c := b a := 2 let d := add(b, c) pop(a) pop(b) pop(c) pop(d) }", + "{ let a := extcodesize(0) let b := a let c := a a := 2 let d := add(b, c) pop(2) pop(b) pop(c) pop(add(b, c)) }" + ); +} + +BOOST_AUTO_TEST_CASE(non_movable_instr) +{ + CHECK( + "{ let a := 1 let b := mload(a) let c := a mstore(add(a, b), c) }", + "{ let a := 1 let b := mload(1) let c := 1 mstore(add(1, b), 1) }" + ); +} + +BOOST_AUTO_TEST_CASE(non_movable_fun) +{ + CHECK( + "{ function f(x) -> y {} let a := 1 let b := f(a) let c := a mstore(add(a, b), c) }", + "{ function f(x) -> y {} let a := 1 let b := f(1) let c := 1 mstore(add(1, b), 1) }" + ); +} + +BOOST_AUTO_TEST_CASE(branches_if) +{ + CHECK( + "{ let a := 1 let b := 2 if b { pop(b) b := a } let c := b }", + "{ let a := 1 let b := 2 if 2 { pop(2) b := 1 } let c := b }" + ); +} + +BOOST_AUTO_TEST_CASE(branches_switch) +{ + CHECK( + "{ let a := 1 let b := 2 switch number() case 1 { b := a } default { let x := a let y := b b := a } pop(add(a, b)) }", + "{ let a := 1 let b := 2 switch number() case 1 { b := 1 } default { let x := 1 let y := b b := 1 } pop(add(1, b)) }" + ); +} + +BOOST_AUTO_TEST_CASE(branches_for) +{ + CHECK( + "{ let a := 1 for { pop(a) } a { pop(a) } { pop(a) } }", + "{ let a := 1 for { pop(1) } 1 { pop(1) } { pop(1) } }" + ); + CHECK( + "{ let a := 1 for { pop(a) } a { pop(a) } { a := 7 let c := a } let x := a }", + "{ let a := 1 for { pop(1) } a { pop(7) } { a := 7 let c := 7 } let x := a }" + ); +} + +BOOST_AUTO_TEST_CASE(branches_for_declared_in_init) +{ + CHECK( + "{ let b := 0 for { let a := 1 pop(a) } a { pop(a) } { b := 1 pop(a) } }", + "{ let b := 0 for { let a := 1 pop(1) } 1 { pop(1) } { b := 1 pop(1) } }" + ); + CHECK( + "{ let b := 0 for { let a := 1 pop(a) } lt(a, 0) { pop(a) a := add(a, 3) } { b := 1 pop(a) } }", + "{ let b := 0 for { let a := 1 pop(1) } lt(a, 0) { pop(a) a := add(a, 3) } { b := 1 pop(a) } }" + ); +} + +BOOST_AUTO_TEST_CASE(reassignment) +{ + CHECK( + "{ let a := 1 pop(a) if a { a := 2 } let b := mload(a) pop(b) }", + "{ let a := 1 pop(1) if 1 { a := 2 } let b := mload(a) pop(b) }" + ); +} + +BOOST_AUTO_TEST_CASE(update_assignment_remat) +{ + // We cannot substitute `a` in `let b := a` + CHECK( + "{ let a := extcodesize(0) a := mul(a, 2) let b := a }", + "{ let a := extcodesize(0) a := mul(a, 2) let b := a }" + ); +} + +BOOST_AUTO_TEST_CASE(do_not_move_out_of_scope) +{ + // Cannot replace by `let b := x` by `let b := a` since a is out of scope. + CHECK( + "{ let x { let a := sload(0) x := a } let b := x }", + "{ let x { let a := sload(0) x := a } let b := x }" + ); +} + +BOOST_AUTO_TEST_CASE(do_not_remat_large_amounts_of_code) +{ + CHECK( + "{ let x := add(mul(calldataload(2), calldataload(4)), mul(2, calldatasize())) let b := x }", + "{ let x := add(mul(calldataload(2), calldataload(4)), mul(2, calldatasize())) let b := x }" + ); + CHECK( + "{ let x := add(mul(calldataload(2), calldataload(4)), calldatasize()) let b := x }", + "{ let x := add(mul(calldataload(2), calldataload(4)), calldatasize()) let b := add(mul(calldataload(2), calldataload(4)), calldatasize()) }" + ); +} + +BOOST_AUTO_TEST_SUITE_END() diff --git a/test/libjulia/Simplifier.cpp b/test/libjulia/Simplifier.cpp new file mode 100644 index 00000000..b48d45c8 --- /dev/null +++ b/test/libjulia/Simplifier.cpp @@ -0,0 +1,130 @@ +/* + This file is part of solidity. + + solidity is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + solidity is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with solidity. If not, see <http://www.gnu.org/licenses/>. +*/ +/** + * @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_CASE(invariant) +{ + CHECK( + "{ let a := mload(sub(7, 7)) let b := sub(a, 0) }", + "{ let a := mload(0) let b := a }" + ); +} + +BOOST_AUTO_TEST_CASE(reversed) +{ + CHECK( + "{ let a := add(0, mload(0)) }", + "{ let a := mload(0) }" + ); +} + +BOOST_AUTO_TEST_CASE(constant_propagation) +{ + CHECK( + "{ let a := add(7, sub(mload(0), 7)) }", + "{ let a := mload(0) }" + ); +} + +BOOST_AUTO_TEST_CASE(identity_rules_simple) +{ + CHECK( + "{ let a := mload(0) let b := sub(a, a) }", + "{ let a := mload(0) let b := 0 }" + ); +} + +BOOST_AUTO_TEST_CASE(identity_rules_complex) +{ + CHECK( + "{ let a := sub(calldataload(0), calldataload(0)) }", + "{ let a := 0 }" + ); +} + +BOOST_AUTO_TEST_CASE(identity_rules_negative) +{ + CHECK( + "{ let a := sub(calldataload(1), calldataload(0)) }", + "{ let a := sub(calldataload(1), calldataload(0)) }" + ); +} + +BOOST_AUTO_TEST_CASE(including_function_calls) +{ + CHECK( + "{ function f() -> a {} let b := add(7, sub(f(), 7)) }", + "{ function f() -> a {} let b := f() }" + ); +} + +BOOST_AUTO_TEST_CASE(inside_for) +{ + CHECK( + "{ for { let a := 10 } iszero(eq(a, 0)) { a := add(a, 1) } {} }", + "{ for { let a := 10 } iszero(iszero(a)) { a := add(a, 1) } {} }" + ); +} + +BOOST_AUTO_TEST_SUITE_END() diff --git a/test/libjulia/UnusedPruner.cpp b/test/libjulia/UnusedPruner.cpp new file mode 100644 index 00000000..b86a54b3 --- /dev/null +++ b/test/libjulia/UnusedPruner.cpp @@ -0,0 +1,129 @@ +/* + 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 pruning of unused variables and functions. + */ + +#include <test/libjulia/Common.h> + +#include <libjulia/optimiser/UnusedPruner.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 = disambiguate(_original, false);\ + UnusedPruner::runUntilStabilised(b);\ + string result = p(b);\ + BOOST_CHECK_EQUAL(result, format(_expectation, false));\ +}\ +while(false) + +BOOST_AUTO_TEST_SUITE(IuliaUnusedPruner) + +BOOST_AUTO_TEST_CASE(smoke_test) +{ + CHECK("{ }", "{ }"); +} + +BOOST_AUTO_TEST_CASE(trivial) +{ + CHECK( + "{ let a := 1 let b := 1 mstore(0, 1) }", + "{ mstore(0, 1) }" + ); +} + +BOOST_AUTO_TEST_CASE(multi_declarations) +{ + CHECK( + "{ let x, y }", + "{ }" + ); +} + +BOOST_AUTO_TEST_CASE(multi_assignments) +{ + CHECK( + "{ let x, y x := 1 y := 2 }", + "{ let x, y x := 1 y := 2 }" + ); +} + +BOOST_AUTO_TEST_CASE(multi_partial_assignments) +{ + CHECK( + "{ let x, y x := 1 }", + "{ let x, y x := 1 }" + ); +} + +BOOST_AUTO_TEST_CASE(functions) +{ + CHECK( + "{ function f() { let a := 1 } function g() { f() } }", + "{ }" + ); +} + +BOOST_AUTO_TEST_CASE(intermediate_assignment) +{ + CHECK( + "{ let a := 1 a := 4 let b := 1 }", + "{ let a := 1 a := 4 }" + ); +} + +BOOST_AUTO_TEST_CASE(intermediate_multi_assignment){ + CHECK( + "{ let a, b function f() -> x { } a := f() b := 1 }", + "{ let a, b function f() -> x { } a := f() b := 1 }" + ); +} + +BOOST_AUTO_TEST_CASE(multi_declare) +{ + CHECK( + "{ function f() -> x, y { } let a, b := f() }", + "{ function f() -> x, y { } let a, b := f() }" + ); +} + +BOOST_AUTO_TEST_CASE(multi_assign) +{ + CHECK( + "{ let a let b function f() -> x, y { } a, b := f() }", + "{ let a let b function f() -> x, y { } a, b := f() }" + ); +} + +BOOST_AUTO_TEST_SUITE_END() |