From 04612936c2ceb41e1c63bfa637eb65f000319c23 Mon Sep 17 00:00:00 2001 From: Christian Parpart Date: Mon, 15 Oct 2018 15:17:20 +0200 Subject: Yul: Introduces a block flattening pass + tests --- libdevcore/CommonData.h | 5 +-- libyul/optimiser/BlockFlattener.cpp | 41 ++++++++++++++++++++++ libyul/optimiser/BlockFlattener.h | 34 ++++++++++++++++++ test/libyul/YulOptimizerTest.cpp | 6 ++++ .../yulOptimizerTests/blockFlattener/basic.yul | 20 +++++++++++ .../yulOptimizerTests/blockFlattener/for_stmt.yul | 19 ++++++++++ .../yulOptimizerTests/blockFlattener/if_stmt.yul | 20 +++++++++++ .../blockFlattener/many_nested_blocks.yul | 28 +++++++++++++++ 8 files changed, 171 insertions(+), 2 deletions(-) create mode 100644 libyul/optimiser/BlockFlattener.cpp create mode 100644 libyul/optimiser/BlockFlattener.h create mode 100644 test/libyul/yulOptimizerTests/blockFlattener/basic.yul create mode 100644 test/libyul/yulOptimizerTests/blockFlattener/for_stmt.yul create mode 100644 test/libyul/yulOptimizerTests/blockFlattener/if_stmt.yul create mode 100644 test/libyul/yulOptimizerTests/blockFlattener/many_nested_blocks.yul diff --git a/libdevcore/CommonData.h b/libdevcore/CommonData.h index 98136b44..f208c425 100644 --- a/libdevcore/CommonData.h +++ b/libdevcore/CommonData.h @@ -239,9 +239,10 @@ bool contains(T const& _t, V const& _v) /// on the current element and after that. The actual replacement takes /// place at the end, but already visited elements might be invalidated. /// If nothing is replaced, no copy is performed. -template -void iterateReplacing(std::vector& _vector, std::function>(T&)> _f) +template +void iterateReplacing(std::vector& _vector, const F& _f) { + // Concept: _f must be Callable, must accept param T&, must return optional> bool useModified = false; std::vector modifiedVector; for (size_t i = 0; i < _vector.size(); ++i) diff --git a/libyul/optimiser/BlockFlattener.cpp b/libyul/optimiser/BlockFlattener.cpp new file mode 100644 index 00000000..04f3ad7f --- /dev/null +++ b/libyul/optimiser/BlockFlattener.cpp @@ -0,0 +1,41 @@ +/* + This file is part of solidity. + + solidity is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + solidity is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with solidity. If not, see . +*/ +#include +#include +#include +#include +#include + +using namespace std; +using namespace dev; +using namespace dev::yul; + +void BlockFlattener::operator()(Block& _block) +{ + ASTModifier::operator()(_block); + + iterateReplacing( + _block.statements, + [](Statement& _s) -> boost::optional> + { + if (_s.type() == typeid(Block)) + return std::move(boost::get(_s).statements); + else + return {}; + } + ); +} diff --git a/libyul/optimiser/BlockFlattener.h b/libyul/optimiser/BlockFlattener.h new file mode 100644 index 00000000..88c49dda --- /dev/null +++ b/libyul/optimiser/BlockFlattener.h @@ -0,0 +1,34 @@ +/* + 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 . +*/ +#pragma once + +#include + +namespace dev +{ +namespace yul +{ + +class BlockFlattener: public ASTModifier +{ +public: + using ASTModifier::operator(); + void operator()(Block& _block) override; +}; + +} +} diff --git a/test/libyul/YulOptimizerTest.cpp b/test/libyul/YulOptimizerTest.cpp index 8b37830f..ea8e4b5e 100644 --- a/test/libyul/YulOptimizerTest.cpp +++ b/test/libyul/YulOptimizerTest.cpp @@ -21,6 +21,7 @@ #include +#include #include #include #include @@ -93,6 +94,11 @@ bool YulOptimizerTest::run(ostream& _stream, string const& _linePrefix, bool con if (m_optimizerStep == "disambiguator") disambiguate(); + else if (m_optimizerStep == "blockFlattener") + { + disambiguate(); + BlockFlattener{}(*m_ast); + } else if (m_optimizerStep == "commonSubexpressionEliminator") { disambiguate(); diff --git a/test/libyul/yulOptimizerTests/blockFlattener/basic.yul b/test/libyul/yulOptimizerTests/blockFlattener/basic.yul new file mode 100644 index 00000000..adcaedd0 --- /dev/null +++ b/test/libyul/yulOptimizerTests/blockFlattener/basic.yul @@ -0,0 +1,20 @@ +{ + let _1 := mload(0) + let f_a := mload(1) + let f_r + { + f_a := mload(f_a) + f_r := add(f_a, calldatasize()) + } + let z := mload(2) +} +// ---- +// blockFlattener +// { +// let _1 := mload(0) +// let f_a := mload(1) +// let f_r +// f_a := mload(f_a) +// f_r := add(f_a, calldatasize()) +// let z := mload(2) +// } diff --git a/test/libyul/yulOptimizerTests/blockFlattener/for_stmt.yul b/test/libyul/yulOptimizerTests/blockFlattener/for_stmt.yul new file mode 100644 index 00000000..07bd5c18 --- /dev/null +++ b/test/libyul/yulOptimizerTests/blockFlattener/for_stmt.yul @@ -0,0 +1,19 @@ +{ + for { let a := 1 } iszero(eq(a, 10)) { a := add(a, 1) } { + a := add(a, 1) + } +} +// ---- +// blockFlattener +// { +// for { +// let a := 1 +// } +// iszero(eq(a, 10)) +// { +// a := add(a, 1) +// } +// { +// a := add(a, 1) +// } +// } diff --git a/test/libyul/yulOptimizerTests/blockFlattener/if_stmt.yul b/test/libyul/yulOptimizerTests/blockFlattener/if_stmt.yul new file mode 100644 index 00000000..4d6ccf0e --- /dev/null +++ b/test/libyul/yulOptimizerTests/blockFlattener/if_stmt.yul @@ -0,0 +1,20 @@ +{ + if add(mload(7), sload(mload(3))) + { + let y := add(mload(3), 3) + { + y := add(y, 7) + } + } + let t := add(3, 9) +} +// ---- +// blockFlattener +// { +// if add(mload(7), sload(mload(3))) +// { +// let y := add(mload(3), 3) +// y := add(y, 7) +// } +// let t := add(3, 9) +// } diff --git a/test/libyul/yulOptimizerTests/blockFlattener/many_nested_blocks.yul b/test/libyul/yulOptimizerTests/blockFlattener/many_nested_blocks.yul new file mode 100644 index 00000000..ae2a066b --- /dev/null +++ b/test/libyul/yulOptimizerTests/blockFlattener/many_nested_blocks.yul @@ -0,0 +1,28 @@ +{ + let a := 3 + let b := 4 + { + a := add(b, 3) + let c := 5 + { + b := add(b, 4) + { + c := add(a, 5) + } + b := add(a, b) + } + a := add(a, c) + } +} +// ---- +// blockFlattener +// { +// let a := 3 +// let b := 4 +// a := add(b, 3) +// let c := 5 +// b := add(b, 4) +// c := add(a, 5) +// b := add(a, b) +// a := add(a, c) +// } -- cgit