diff options
20 files changed, 545 insertions, 0 deletions
diff --git a/libjulia/optimiser/ExpressionJoiner.cpp b/libjulia/optimiser/ExpressionJoiner.cpp new file mode 100644 index 00000000..5b92e332 --- /dev/null +++ b/libjulia/optimiser/ExpressionJoiner.cpp @@ -0,0 +1,166 @@ +/* + 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 undoes what the ExpressionSplitter did, i.e. + * it more or less inlines variable declarations. + */ + +#include <libjulia/optimiser/ExpressionJoiner.h> + +#include <libjulia/optimiser/NameCollector.h> +#include <libjulia/optimiser/Utilities.h> +#include <libjulia/Exceptions.h> + +#include <libsolidity/inlineasm/AsmData.h> + +#include <libdevcore/CommonData.h> + +#include <boost/range/adaptor/reversed.hpp> + +using namespace std; +using namespace dev; +using namespace dev::julia; +using namespace dev::solidity; + +void ExpressionJoiner::operator()(FunctionalInstruction& _instruction) +{ + handleArguments(_instruction.arguments); +} + +void ExpressionJoiner::operator()(FunctionCall& _funCall) +{ + handleArguments(_funCall.arguments); +} + +void ExpressionJoiner::operator()(If& _if) +{ + visit(*_if.condition); + (*this)(_if.body); +} + +void ExpressionJoiner::operator()(Switch& _switch) +{ + visit(*_switch.expression); + for (auto& _case: _switch.cases) + // Do not visit the case expression, nothing to unbreak there. + (*this)(_case.body); +} + +void ExpressionJoiner::operator()(Block& _block) +{ + resetLatestStatementPointer(); + for (size_t i = 0; i < _block.statements.size(); ++i) + { + visit(_block.statements[i]); + m_currentBlock = &_block; + m_latestStatementInBlock = i; + } + + removeEmptyBlocks(_block); + resetLatestStatementPointer(); +} + +void ExpressionJoiner::visit(Expression& _e) +{ + if (_e.type() == typeid(Identifier)) + { + Identifier const& identifier = boost::get<Identifier>(_e); + if (isLatestStatementVarDeclOf(identifier) && m_references[identifier.name] == 1) + { + VariableDeclaration& varDecl = boost::get<VariableDeclaration>(*latestStatement()); + assertThrow(varDecl.variables.size() == 1, OptimizerException, ""); + assertThrow(varDecl.value, OptimizerException, ""); + + _e = std::move(*varDecl.value); + // Delete the variable declaration (also get the moved-from structure back into a sane state) + *latestStatement() = Block(); + + decrementLatestStatementPointer(); + } + } + else + ASTModifier::visit(_e); +} + +void ExpressionJoiner::run(Block& _ast) +{ + ExpressionJoiner{_ast}(_ast); +} + +ExpressionJoiner::ExpressionJoiner(Block& _ast) +{ + ReferencesCounter counter; + counter(_ast); + m_references = counter.references(); +} + +void ExpressionJoiner::handleArguments(vector<Expression>& _arguments) +{ + // We have to fill from left to right, but we can only + // fill if everything to the right is just an identifier + // or a literal. + // Also we only descend into function calls if everything + // on the right is an identifier or literal. + + size_t i = _arguments.size(); + for (Expression const& arg: _arguments | boost::adaptors::reversed) + { + --i; + if (arg.type() != typeid(Identifier) && arg.type() != typeid(Literal)) + break; + } + // i points to the last element that is neither an identifier nor a literal, + // or to the first element if all of them are identifiers or literals. + + for (; i < _arguments.size(); ++i) + visit(_arguments.at(i)); +} + +void ExpressionJoiner::decrementLatestStatementPointer() +{ + if (!m_currentBlock) + return; + if (m_latestStatementInBlock > 0) + --m_latestStatementInBlock; + else + resetLatestStatementPointer(); +} + +void ExpressionJoiner::resetLatestStatementPointer() +{ + m_currentBlock = nullptr; + m_latestStatementInBlock = size_t(-1); +} + +Statement* ExpressionJoiner::latestStatement() +{ + if (!m_currentBlock) + return nullptr; + else + return &m_currentBlock->statements.at(m_latestStatementInBlock); +} + +bool ExpressionJoiner::isLatestStatementVarDeclOf(Identifier const& _identifier) +{ + Statement const* statement = latestStatement(); + if (!statement || statement->type() != typeid(VariableDeclaration)) + return false; + VariableDeclaration const& varDecl = boost::get<VariableDeclaration>(*statement); + if (varDecl.variables.size() != 1 || !varDecl.value) + return false; + return varDecl.variables.at(0).name == _identifier.name; +} diff --git a/libjulia/optimiser/ExpressionJoiner.h b/libjulia/optimiser/ExpressionJoiner.h new file mode 100644 index 00000000..91b45b49 --- /dev/null +++ b/libjulia/optimiser/ExpressionJoiner.h @@ -0,0 +1,102 @@ +/* + 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 undoes what the ExpressionSplitter did, i.e. + * it more or less inlines variable declarations. + */ +#pragma once + +#include <libjulia/ASTDataForward.h> + +#include <libjulia/optimiser/ASTWalker.h> + +#include <map> + +namespace dev +{ +namespace julia +{ + +class NameCollector; + + +/** + * Optimiser component that modifies an AST in place, turning sequences + * of variable declarations into complex expressions, if the variables + * are declared in the right order. This component does the opposite + * of ExpressionSplitter. + * Since the order of opcode or function evaluation is unchanged, + * this transformation does not need to care about conflicting opcodes. + * + * Code of the form + * + * let a1 := mload(y) + * let a2 := mul(x, 4) + * sstore(a2, a1) + * + * is transformed into + * + * sstore(mul(x, 4), mload(y)) + * + * The transformation is not applied to loop conditions, because those are + * evaluated with each loop. + * + * The component can be applied to sub-blocks of the AST, you do not + * need to pass a full AST. + * + * Prerequisites: Disambiguator + * + * Implementation note: We visit the AST, modifying it in place. + * The class starts counting references and will only replace variables + * that have exactly one reference. It keeps a "latest statement pointer" + * which always points to the statement right before the current statement. + * Any function call or opcode will reset this pointer. If an identifier + * is encountered that was declared in the "latest statement", it is replaced + * by the value of the declaration, the "latest statement" is replaced + * by an empty block and the pointer is decremented. + * A block also resets the latest statement pointer. + */ +class ExpressionJoiner: public ASTModifier +{ +public: + virtual void operator()(FunctionalInstruction&) override; + virtual void operator()(FunctionCall&) override; + virtual void operator()(If&) override; + virtual void operator()(Switch&) override; + virtual void operator()(Block& _block) override; + + using ASTModifier::visit; + virtual void visit(Expression& _e) override; + + static void run(Block& _ast); +private: + explicit ExpressionJoiner(Block& _ast); + + void handleArguments(std::vector<Expression>& _arguments); + + void decrementLatestStatementPointer(); + void resetLatestStatementPointer(); + Statement* latestStatement(); + bool isLatestStatementVarDeclOf(Identifier const& _identifier); + + Block* m_currentBlock = nullptr; + size_t m_latestStatementInBlock = 0; + std::map<std::string, size_t> m_references; +}; + +} +} diff --git a/libjulia/optimiser/README.md b/libjulia/optimiser/README.md index 877f8255..4a50d5ca 100644 --- a/libjulia/optimiser/README.md +++ b/libjulia/optimiser/README.md @@ -56,6 +56,47 @@ depend on any side-effects. As an example, neither ``mload`` nor ``mstore`` would be allowed. +## Expression Splitter + +The expression splitter turns expressions like ``add(mload(x), mul(mload(y), 0x20))`` +into a sequence of declarations of unique variables that are assigned sub-expressions +of that expression so that each function call has only variables or literals +as arguments. + +The above would be transformed into + + { + let _1 := mload(y) + let _2 := mul(_1, 0x20) + let _3 := mload(x) + let z := add(_3, _2) + } + +Note that this transformation does not change the order of opcodes or function calls. + +It is not applied to loop conditions, because the loop control flow does not allow +this "outlining" of the inner expressions in all cases. + +The final program should be in a form such that with the exception of loop conditions, +function calls can only appear in the right-hand side of a variable declaration, +assignments or expression statements and all arguments have to be constants or variables. + +The benefits of this form are that it is much easier to re-order the sequence of opcodes +and it is also easier to perform function call inlining. The drawback is that +such code is much harder to read for humans. + +## Expression Joiner + +This is the opposite operation of the expression splitter. It turns a sequence of +variable declarations that have exactly one reference into a complex expression. +This stage again fully preserves the order of function calls and opcode executions. +It does not make use of any information concerning the commutability of opcodes; +if moving the value of a variable to its place of use would change the order +of any function call or opcode execution, the transformation is not performed. + +Note that the component will not move the assigned value of a variable assignment +or a variable that is referenced more than once. + ## Full Function Inliner ## Rematerialisation diff --git a/test/libjulia/YulOptimizerTest.cpp b/test/libjulia/YulOptimizerTest.cpp index 96e36a5b..38765774 100644 --- a/test/libjulia/YulOptimizerTest.cpp +++ b/test/libjulia/YulOptimizerTest.cpp @@ -33,6 +33,7 @@ #include <libjulia/optimiser/Rematerialiser.h> #include <libjulia/optimiser/ExpressionSimplifier.h> #include <libjulia/optimiser/UnusedPruner.h> +#include <libjulia/optimiser/ExpressionJoiner.h> #include <libsolidity/parsing/Scanner.h> #include <libsolidity/inlineasm/AsmPrinter.h> @@ -146,6 +147,11 @@ bool YulOptimizerTest::run(ostream& _stream, string const& _linePrefix, bool con disambiguate(); UnusedPruner::runUntilStabilised(*m_ast); } + else if (m_optimizerStep == "expressionJoiner") + { + disambiguate(); + ExpressionJoiner::run(*m_ast);\ + } else { FormattedScope(_stream, _formatted, {formatting::BOLD, formatting::RED}) << _linePrefix << "Invalid optimizer step: " << m_optimizerStep << endl; diff --git a/test/libjulia/yulOptimizerTests/expressionJoiner/if_condition.yul b/test/libjulia/yulOptimizerTests/expressionJoiner/if_condition.yul new file mode 100644 index 00000000..a1349511 --- /dev/null +++ b/test/libjulia/yulOptimizerTests/expressionJoiner/if_condition.yul @@ -0,0 +1,21 @@ +{ + let a := mload(3) + let b := sload(a) + let c := mload(7) + let d := add(c, b) + if d { + let x := mload(3) + let y := add(x, 3) + } + let z := 3 + let t := add(z, 9) +} +// ---- +// expressionJoiner +// { +// if add(mload(7), sload(mload(3))) +// { +// let y := add(mload(3), 3) +// } +// let t := add(3, 9) +// } diff --git a/test/libjulia/yulOptimizerTests/expressionJoiner/muli_wrong_order3.yul b/test/libjulia/yulOptimizerTests/expressionJoiner/muli_wrong_order3.yul new file mode 100644 index 00000000..0d407c7c --- /dev/null +++ b/test/libjulia/yulOptimizerTests/expressionJoiner/muli_wrong_order3.yul @@ -0,0 +1,13 @@ +{ + let a := mload(3) + let b := mload(6) + let x := mul(add(b, a), mload(2)) + sstore(x, 3) +} +// ---- +// expressionJoiner +// { +// let a := mload(3) +// let b := mload(6) +// sstore(mul(add(b, a), mload(2)), 3) +// } diff --git a/test/libjulia/yulOptimizerTests/expressionJoiner/multi.yul b/test/libjulia/yulOptimizerTests/expressionJoiner/multi.yul new file mode 100644 index 00000000..fd53ca51 --- /dev/null +++ b/test/libjulia/yulOptimizerTests/expressionJoiner/multi.yul @@ -0,0 +1,11 @@ +{ + let a := mload(2) + let b := mload(6) + let x := mul(add(b, a), 2) + sstore(x, 3) +} +// ---- +// expressionJoiner +// { +// sstore(mul(add(mload(6), mload(2)), 2), 3) +// } diff --git a/test/libjulia/yulOptimizerTests/expressionJoiner/multi_reference.yul b/test/libjulia/yulOptimizerTests/expressionJoiner/multi_reference.yul new file mode 100644 index 00000000..078a12a5 --- /dev/null +++ b/test/libjulia/yulOptimizerTests/expressionJoiner/multi_reference.yul @@ -0,0 +1,11 @@ +{ + // This is not joined because a is referenced multiple times + let a := mload(2) + let b := add(a, a) +} +// ---- +// expressionJoiner +// { +// let a := mload(2) +// let b := add(a, a) +// } diff --git a/test/libjulia/yulOptimizerTests/expressionJoiner/multi_wrong_order.yul b/test/libjulia/yulOptimizerTests/expressionJoiner/multi_wrong_order.yul new file mode 100644 index 00000000..965e07e9 --- /dev/null +++ b/test/libjulia/yulOptimizerTests/expressionJoiner/multi_wrong_order.yul @@ -0,0 +1,15 @@ +{ + // We have an interleaved "add" here, so we cannot inline "a" + // (note that this component does not analyze whether + // functions are pure or not) + let a := mload(2) + let b := mload(6) + let x := mul(a, add(2, b)) + sstore(x, 3) +} +// ---- +// expressionJoiner +// { +// let a := mload(2) +// sstore(mul(a, add(2, mload(6))), 3) +// } diff --git a/test/libjulia/yulOptimizerTests/expressionJoiner/multi_wrong_order2.yul b/test/libjulia/yulOptimizerTests/expressionJoiner/multi_wrong_order2.yul new file mode 100644 index 00000000..c577e182 --- /dev/null +++ b/test/libjulia/yulOptimizerTests/expressionJoiner/multi_wrong_order2.yul @@ -0,0 +1,12 @@ +{ + let a := mload(2) + let b := mload(6) + let x := mul(add(a, b), 2) + sstore(x, 3) +} +// ---- +// expressionJoiner +// { +// let a := mload(2) +// sstore(mul(add(a, mload(6)), 2), 3) +// } diff --git a/test/libjulia/yulOptimizerTests/expressionJoiner/no_replacement_across_blocks.yul b/test/libjulia/yulOptimizerTests/expressionJoiner/no_replacement_across_blocks.yul new file mode 100644 index 00000000..a781bb2a --- /dev/null +++ b/test/libjulia/yulOptimizerTests/expressionJoiner/no_replacement_across_blocks.yul @@ -0,0 +1,19 @@ +{ + // The component will remove the empty block after + // it has handled the outer block. + // The idea behind this test is that the component + // does not perform replacements across blocks because + // they usually have contents, but adding contents + // will reduce the scope of the test. + let a := mload(2) + let x := calldataload(a) + { + } + sstore(x, 3) +} +// ---- +// expressionJoiner +// { +// let x := calldataload(mload(2)) +// sstore(x, 3) +// } diff --git a/test/libjulia/yulOptimizerTests/expressionJoiner/no_replacement_in_loop_condition1.yul b/test/libjulia/yulOptimizerTests/expressionJoiner/no_replacement_in_loop_condition1.yul new file mode 100644 index 00000000..75218a5c --- /dev/null +++ b/test/libjulia/yulOptimizerTests/expressionJoiner/no_replacement_in_loop_condition1.yul @@ -0,0 +1,15 @@ +{ + for { let b := mload(1) } b {} {} +} +// ---- +// expressionJoiner +// { +// for { +// let b := mload(1) +// } +// b +// { +// } +// { +// } +// } diff --git a/test/libjulia/yulOptimizerTests/expressionJoiner/no_replacement_in_loop_condition2.yul b/test/libjulia/yulOptimizerTests/expressionJoiner/no_replacement_in_loop_condition2.yul new file mode 100644 index 00000000..d5f7d8fa --- /dev/null +++ b/test/libjulia/yulOptimizerTests/expressionJoiner/no_replacement_in_loop_condition2.yul @@ -0,0 +1,16 @@ +{ + let a := mload(0) + for { } a {} {} +} +// ---- +// expressionJoiner +// { +// let a := mload(0) +// for { +// } +// a +// { +// } +// { +// } +// } diff --git a/test/libjulia/yulOptimizerTests/expressionJoiner/only_assignment.yul b/test/libjulia/yulOptimizerTests/expressionJoiner/only_assignment.yul new file mode 100644 index 00000000..c7411211 --- /dev/null +++ b/test/libjulia/yulOptimizerTests/expressionJoiner/only_assignment.yul @@ -0,0 +1,16 @@ +{ + // This is not joined because a is referenced multiple times + function f(a) -> x { + a := mload(2) + x := add(a, 3) + } +} +// ---- +// expressionJoiner +// { +// function f(a) -> x +// { +// a := mload(2) +// x := add(a, 3) +// } +// } diff --git a/test/libjulia/yulOptimizerTests/expressionJoiner/reassignment.yul b/test/libjulia/yulOptimizerTests/expressionJoiner/reassignment.yul new file mode 100644 index 00000000..1e502353 --- /dev/null +++ b/test/libjulia/yulOptimizerTests/expressionJoiner/reassignment.yul @@ -0,0 +1,13 @@ +{ + // This is not joined because a is referenced multiple times + let a := mload(2) + let b := mload(a) + a := 4 +} +// ---- +// expressionJoiner +// { +// let a := mload(2) +// let b := mload(a) +// a := 4 +// } diff --git a/test/libjulia/yulOptimizerTests/expressionJoiner/simple.yul b/test/libjulia/yulOptimizerTests/expressionJoiner/simple.yul new file mode 100644 index 00000000..b03bcf45 --- /dev/null +++ b/test/libjulia/yulOptimizerTests/expressionJoiner/simple.yul @@ -0,0 +1,10 @@ +{ + let a := mload(2) + let x := calldataload(a) + sstore(x, 3) +} +// ---- +// expressionJoiner +// { +// sstore(calldataload(mload(2)), 3) +// } diff --git a/test/libjulia/yulOptimizerTests/expressionJoiner/single_wrong_order.yul b/test/libjulia/yulOptimizerTests/expressionJoiner/single_wrong_order.yul new file mode 100644 index 00000000..3b433f78 --- /dev/null +++ b/test/libjulia/yulOptimizerTests/expressionJoiner/single_wrong_order.yul @@ -0,0 +1,13 @@ +{ + let a := mload(3) + let b := sload(a) + let c := mload(7) + let d := add(b, c) + sstore(d, 0) +} +// ---- +// expressionJoiner +// { +// let b := sload(mload(3)) +// sstore(add(b, mload(7)), 0) +// } diff --git a/test/libjulia/yulOptimizerTests/expressionJoiner/smoke.yul b/test/libjulia/yulOptimizerTests/expressionJoiner/smoke.yul new file mode 100644 index 00000000..c0e2c6f2 --- /dev/null +++ b/test/libjulia/yulOptimizerTests/expressionJoiner/smoke.yul @@ -0,0 +1,5 @@ +{ } +// ---- +// expressionJoiner +// { +// } diff --git a/test/libjulia/yulOptimizerTests/expressionJoiner/switch_expression.yul b/test/libjulia/yulOptimizerTests/expressionJoiner/switch_expression.yul new file mode 100644 index 00000000..0e4e540e --- /dev/null +++ b/test/libjulia/yulOptimizerTests/expressionJoiner/switch_expression.yul @@ -0,0 +1,28 @@ +{ + let a := mload(3) + let b := sload(a) + let c := mload(7) + let d := add(c, b) + switch d + case 3 { + let x := mload(3) + let y := add(x, 3) + } + default { + sstore(1, 0) + } + let z := 3 + let t := add(z, 9) +} +// ---- +// expressionJoiner +// { +// switch add(mload(7), sload(mload(3))) +// case 3 { +// let y := add(mload(3), 3) +// } +// default { +// sstore(1, 0) +// } +// let t := add(3, 9) +// } diff --git a/test/libjulia/yulOptimizerTests/expressionJoiner/triple.yul b/test/libjulia/yulOptimizerTests/expressionJoiner/triple.yul new file mode 100644 index 00000000..7b722be1 --- /dev/null +++ b/test/libjulia/yulOptimizerTests/expressionJoiner/triple.yul @@ -0,0 +1,12 @@ +{ + let a := mload(2) + let b := mload(6) + let c := mload(7) + let x := mul(add(c, b), a) + sstore(x, 3) +} +// ---- +// expressionJoiner +// { +// sstore(mul(add(mload(7), mload(6)), mload(2)), 3) +// } |