diff options
19 files changed, 292 insertions, 15 deletions
diff --git a/libyul/CMakeLists.txt b/libyul/CMakeLists.txt index 4bc8200c..a75c5908 100644 --- a/libyul/CMakeLists.txt +++ b/libyul/CMakeLists.txt @@ -36,6 +36,7 @@ add_library(yul optimiser/SSAValueTracker.cpp optimiser/Semantics.cpp optimiser/SimplificationRules.cpp + optimiser/StructuralSimplifier.cpp optimiser/Substitution.cpp optimiser/Suite.cpp optimiser/SyntacticalEquality.cpp diff --git a/libyul/optimiser/SimplificationRules.cpp b/libyul/optimiser/SimplificationRules.cpp index 8ed63fa8..45b0ca2c 100644 --- a/libyul/optimiser/SimplificationRules.cpp +++ b/libyul/optimiser/SimplificationRules.cpp @@ -208,10 +208,7 @@ Expression Pattern::toExpression(SourceLocation const& _location) const u256 Pattern::d() const { - Literal const& literal = boost::get<Literal>(matchGroupValue()); - assertThrow(literal.kind == LiteralKind::Number, OptimizerException, ""); - assertThrow(isValidDecimal(literal.value.str()) || isValidHex(literal.value.str()), OptimizerException, ""); - return u256(literal.value.str()); + return valueOfNumberLiteral(boost::get<Literal>(matchGroupValue())); } Expression const& Pattern::matchGroupValue() const diff --git a/libyul/optimiser/StructuralSimplifier.cpp b/libyul/optimiser/StructuralSimplifier.cpp new file mode 100644 index 00000000..5fcfdae4 --- /dev/null +++ b/libyul/optimiser/StructuralSimplifier.cpp @@ -0,0 +1,138 @@ +/* + 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/>. +*/ +#include <libyul/optimiser/StructuralSimplifier.h> +#include <libyul/optimiser/Semantics.h> +#include <libyul/optimiser/Utilities.h> +#include <libyul/AsmData.h> +#include <libdevcore/CommonData.h> +#include <libdevcore/Visitor.h> + +using namespace std; +using namespace dev; +using namespace yul; + +namespace { + +ExpressionStatement makePopExpressionStatement(langutil::SourceLocation const& _location, Expression&& _expression) +{ + return {_location, FunctionalInstruction{ + _location, + solidity::Instruction::POP, + {std::move(_expression)} + }}; +} + +} + +void StructuralSimplifier::operator()(Block& _block) +{ + pushScope(false); + simplify(_block.statements); + popScope(); +} + +void StructuralSimplifier::simplify(std::vector<yul::Statement>& _statements) +{ + using OptionalStatements = boost::optional<vector<Statement>>; + GenericFallbackReturnsVisitor<OptionalStatements, If, Switch, ForLoop> const visitor( + [&](If& _ifStmt) -> OptionalStatements { + if (_ifStmt.body.statements.empty()) + return {{makePopExpressionStatement(_ifStmt.location, std::move(*_ifStmt.condition))}}; + if (expressionAlwaysTrue(*_ifStmt.condition)) + return {std::move(_ifStmt.body.statements)}; + else if (expressionAlwaysFalse(*_ifStmt.condition)) + return {{}}; + return {}; + }, + [](Switch& _switchStmt) -> OptionalStatements { + if (_switchStmt.cases.size() == 1) + { + auto& switchCase = _switchStmt.cases.front(); + auto loc = locationOf(*_switchStmt.expression); + if (switchCase.value) + return {{If{ + std::move(_switchStmt.location), + make_shared<Expression>(FunctionalInstruction{ + std::move(loc), + solidity::Instruction::EQ, + {std::move(*switchCase.value), std::move(*_switchStmt.expression)} + }), std::move(switchCase.body)}}}; + else + return {{ + makePopExpressionStatement(loc, std::move(*_switchStmt.expression)), + std::move(switchCase.body) + }}; + } + else + return {}; + }, + [&](ForLoop& _forLoop) -> OptionalStatements { + if (expressionAlwaysFalse(*_forLoop.condition)) + return {std::move(_forLoop.pre.statements)}; + else + return {}; + } + ); + + iterateReplacing( + _statements, + [&](Statement& _stmt) -> OptionalStatements + { + visit(_stmt); + OptionalStatements result = boost::apply_visitor(visitor, _stmt); + if (result) + simplify(*result); + return result; + } + ); +} + +bool StructuralSimplifier::expressionAlwaysTrue(Expression const& _expression) +{ + return boost::apply_visitor(GenericFallbackReturnsVisitor<bool, Identifier const, Literal const>( + [&](Identifier const& _identifier) -> bool { + if (auto expr = m_value[_identifier.name]) + return expressionAlwaysTrue(*expr); + return false; + }, + [](Literal const& _literal) -> bool { + static YulString const trueString("true"); + return + (_literal.kind == LiteralKind::Boolean && _literal.value == trueString) || + (_literal.kind == LiteralKind::Number && valueOfNumberLiteral(_literal) != u256(0)) + ; + } + ), _expression); +} + +bool StructuralSimplifier::expressionAlwaysFalse(Expression const& _expression) +{ + return boost::apply_visitor(GenericFallbackReturnsVisitor<bool, Identifier const, Literal const>( + [&](Identifier const& _identifier) -> bool { + if (auto expr = m_value[_identifier.name]) + return expressionAlwaysFalse(*expr); + return false; + }, + [](Literal const& _literal) -> bool { + static YulString const falseString("false"); + return + (_literal.kind == LiteralKind::Boolean && _literal.value == falseString) || + (_literal.kind == LiteralKind::Number && valueOfNumberLiteral(_literal) == u256(0)) + ; + } + ), _expression); +} diff --git a/libyul/optimiser/StructuralSimplifier.h b/libyul/optimiser/StructuralSimplifier.h new file mode 100644 index 00000000..bbd8e005 --- /dev/null +++ b/libyul/optimiser/StructuralSimplifier.h @@ -0,0 +1,49 @@ +/* + This file is part of solidity. + + solidity is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + solidity is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with solidity. If not, see <http://www.gnu.org/licenses/>. +*/ +#pragma once + +#include <libyul/optimiser/ASTWalker.h> +#include <libyul/optimiser/DataFlowAnalyzer.h> + +namespace yul +{ + +/** + * Structural simplifier. Performs the following simplification steps: + * - replace if with empty body with pop(condition) + * - replace if with true condition with its body + * - remove if with false condition + * - turn switch with single case into if + * - replace switch with only default case with pop(expression) and body + * - remove for with false condition + * + * Prerequisites: Disambiguator + * + * Important: Can only be used on EVM code. + */ +class StructuralSimplifier: public DataFlowAnalyzer +{ +public: + using DataFlowAnalyzer::operator(); + void operator()(Block& _block) override; +private: + void simplify(std::vector<Statement>& _statements); + bool expressionAlwaysTrue(Expression const &_expression); + bool expressionAlwaysFalse(Expression const &_expression); +}; + +} diff --git a/libyul/optimiser/Suite.cpp b/libyul/optimiser/Suite.cpp index 36f0e1eb..ad22bfa3 100644 --- a/libyul/optimiser/Suite.cpp +++ b/libyul/optimiser/Suite.cpp @@ -33,6 +33,7 @@ #include <libyul/optimiser/ExpressionSimplifier.h> #include <libyul/optimiser/CommonSubexpressionEliminator.h> #include <libyul/optimiser/SSATransform.h> +#include <libyul/optimiser/StructuralSimplifier.h> #include <libyul/optimiser/RedundantAssignEliminator.h> #include <libyul/optimiser/VarDeclPropagator.h> #include <libyul/AsmAnalysisInfo.h> @@ -58,6 +59,7 @@ void OptimiserSuite::run( (FunctionHoister{})(ast); (FunctionGrouper{})(ast); (ForLoopInitRewriter{})(ast); + StructuralSimplifier{}(ast); NameDispenser dispenser{ast}; @@ -71,6 +73,7 @@ void OptimiserSuite::run( CommonSubexpressionEliminator{}(ast); ExpressionSimplifier::run(ast); + StructuralSimplifier{}(ast); SSATransform::run(ast, dispenser); RedundantAssignEliminator::run(ast); RedundantAssignEliminator::run(ast); @@ -98,6 +101,7 @@ void OptimiserSuite::run( VarDeclPropagator{}(ast); RedundantAssignEliminator::run(ast); ExpressionSimplifier::run(ast); + StructuralSimplifier{}(ast); CommonSubexpressionEliminator{}(ast); SSATransform::run(ast, dispenser); RedundantAssignEliminator::run(ast); diff --git a/libyul/optimiser/Utilities.cpp b/libyul/optimiser/Utilities.cpp index b8cdd339..b3b580d5 100644 --- a/libyul/optimiser/Utilities.cpp +++ b/libyul/optimiser/Utilities.cpp @@ -21,6 +21,7 @@ #include <libyul/optimiser/Utilities.h> #include <libyul/AsmData.h> +#include <libyul/Exceptions.h> #include <libdevcore/CommonData.h> @@ -37,3 +38,11 @@ void yul::removeEmptyBlocks(Block& _block) }; boost::range::remove_erase_if(_block.statements, isEmptyBlock); } + +u256 yul::valueOfNumberLiteral(Literal const& _literal) +{ + assertThrow(_literal.kind == LiteralKind::Number, OptimizerException, ""); + std::string const& literalString = _literal.value.str(); + assertThrow(isValidDecimal(literalString) || isValidHex(literalString), OptimizerException, ""); + return u256(literalString); +} diff --git a/libyul/optimiser/Utilities.h b/libyul/optimiser/Utilities.h index c543b119..1cfff62b 100644 --- a/libyul/optimiser/Utilities.h +++ b/libyul/optimiser/Utilities.h @@ -20,6 +20,7 @@ #pragma once +#include <libdevcore/Common.h> #include <libyul/AsmDataForward.h> namespace yul @@ -28,4 +29,6 @@ namespace yul /// Removes statements that are just empty blocks (non-recursive). void removeEmptyBlocks(Block& _block); +dev::u256 valueOfNumberLiteral(Literal const& _literal); + } diff --git a/test/libyul/YulOptimizerTest.cpp b/test/libyul/YulOptimizerTest.cpp index 96b9d263..ba7eced3 100644 --- a/test/libyul/YulOptimizerTest.cpp +++ b/test/libyul/YulOptimizerTest.cpp @@ -39,6 +39,7 @@ #include <libyul/optimiser/ExpressionJoiner.h> #include <libyul/optimiser/SSATransform.h> #include <libyul/optimiser/RedundantAssignEliminator.h> +#include <libyul/optimiser/StructuralSimplifier.h> #include <libyul/optimiser/Suite.h> #include <libyul/AsmPrinter.h> #include <libyul/AsmParser.h> @@ -213,6 +214,11 @@ bool YulOptimizerTest::run(ostream& _stream, string const& _linePrefix, bool con SSATransform::run(*m_ast, nameDispenser); RedundantAssignEliminator::run(*m_ast); } + else if (m_optimizerStep == "structuralSimplifier") + { + disambiguate(); + StructuralSimplifier{}(*m_ast); + } else if (m_optimizerStep == "fullSuite") OptimiserSuite::run(*m_ast, *m_analysisInfo); else diff --git a/test/libyul/yulOptimizerTests/fullSuite/abi_example1.yul b/test/libyul/yulOptimizerTests/fullSuite/abi_example1.yul index 573e7868..61ba11d2 100644 --- a/test/libyul/yulOptimizerTests/fullSuite/abi_example1.yul +++ b/test/libyul/yulOptimizerTests/fullSuite/abi_example1.yul @@ -599,10 +599,6 @@ // revert(_2, _2) // } // let abi_decode_abi_decode_length_14_1069 := 0x2 -// if _2 -// { -// revert(_2, _2) -// } // let allocateMe_memPtr_315 := mload(abi_encode_pos_590) // let allocateMe_newFreePtr := add(allocateMe_memPtr_315, abi_encode_pos_590) // if or(gt(allocateMe_newFreePtr, _945), lt(allocateMe_newFreePtr, allocateMe_memPtr_315)) diff --git a/test/libyul/yulOptimizerTests/fullSuite/medium.yul b/test/libyul/yulOptimizerTests/fullSuite/medium.yul index deb02068..fbe243d4 100644 --- a/test/libyul/yulOptimizerTests/fullSuite/medium.yul +++ b/test/libyul/yulOptimizerTests/fullSuite/medium.yul @@ -9,16 +9,23 @@ pop(allocate(0x20)) let x := allocate(0x40) mstore(array_index_access(x, 3), 2) + if 0 { + mstore(0x40, 0x20) + } + if sub(2,1) { + for { switch mul(1,2) case 2 { mstore(0x40, 0x20) } } sub(1,1) {} { mstore(0x80, 0x40) } + } } // ---- // fullSuite // { // { -// let _18 := 0x20 -// let allocate__7 := 0x40 -// mstore(allocate__7, add(mload(allocate__7), _18)) -// let allocate_p_12_31 := mload(allocate__7) -// mstore(allocate__7, add(allocate_p_12_31, allocate__7)) -// mstore(add(allocate_p_12_31, 96), 2) +// let _1 := 0x20 +// let allocate__19 := 0x40 +// mstore(allocate__19, add(mload(allocate__19), _1)) +// let allocate_p_24_41 := mload(allocate__19) +// mstore(allocate__19, add(allocate_p_24_41, allocate__19)) +// mstore(add(allocate_p_24_41, 96), 2) +// mstore(allocate__19, _1) // } // } diff --git a/test/libyul/yulOptimizerTests/structuralSimplifier/empty_if_movable_condition.yul b/test/libyul/yulOptimizerTests/structuralSimplifier/empty_if_movable_condition.yul new file mode 100644 index 00000000..ee1975e7 --- /dev/null +++ b/test/libyul/yulOptimizerTests/structuralSimplifier/empty_if_movable_condition.yul @@ -0,0 +1,7 @@ +{ let a := mload(0) if a {} } +// ---- +// structuralSimplifier +// { +// let a := mload(0) +// pop(a) +// } diff --git a/test/libyul/yulOptimizerTests/structuralSimplifier/empty_if_non_movable_condition.yul b/test/libyul/yulOptimizerTests/structuralSimplifier/empty_if_non_movable_condition.yul new file mode 100644 index 00000000..5977297b --- /dev/null +++ b/test/libyul/yulOptimizerTests/structuralSimplifier/empty_if_non_movable_condition.yul @@ -0,0 +1,6 @@ +{ if mload(0) {} } +// ---- +// structuralSimplifier +// { +// pop(mload(0)) +// } diff --git a/test/libyul/yulOptimizerTests/structuralSimplifier/for_false_condition.sol b/test/libyul/yulOptimizerTests/structuralSimplifier/for_false_condition.sol new file mode 100644 index 00000000..b881a0a3 --- /dev/null +++ b/test/libyul/yulOptimizerTests/structuralSimplifier/for_false_condition.sol @@ -0,0 +1,10 @@ +{ + for { let a := 42 } 0 { a := a } { + let b := a + } +} +// ---- +// structuralSimplifier +// { +// let a := 42 +// } diff --git a/test/libyul/yulOptimizerTests/structuralSimplifier/if_false_condition.yul b/test/libyul/yulOptimizerTests/structuralSimplifier/if_false_condition.yul new file mode 100644 index 00000000..0895b1bb --- /dev/null +++ b/test/libyul/yulOptimizerTests/structuralSimplifier/if_false_condition.yul @@ -0,0 +1,5 @@ +{ if 0 { mstore(0, 0) } } +// ---- +// structuralSimplifier +// { +// } diff --git a/test/libyul/yulOptimizerTests/structuralSimplifier/if_true_condition.yul b/test/libyul/yulOptimizerTests/structuralSimplifier/if_true_condition.yul new file mode 100644 index 00000000..ca9cba06 --- /dev/null +++ b/test/libyul/yulOptimizerTests/structuralSimplifier/if_true_condition.yul @@ -0,0 +1,6 @@ +{ if 1 { mstore(0, 0) } } +// ---- +// structuralSimplifier +// { +// mstore(0, 0) +// } diff --git a/test/libyul/yulOptimizerTests/structuralSimplifier/nested.yul b/test/libyul/yulOptimizerTests/structuralSimplifier/nested.yul new file mode 100644 index 00000000..169a84d1 --- /dev/null +++ b/test/libyul/yulOptimizerTests/structuralSimplifier/nested.yul @@ -0,0 +1,6 @@ +{ if 1 { if 1 { for { mstore(0, 0) } 0 {} { mstore(2, 3) } if 0 { mstore(1, 2) } } } } +// ---- +// structuralSimplifier +// { +// mstore(0, 0) +// } diff --git a/test/libyul/yulOptimizerTests/structuralSimplifier/switch_only_default.yul b/test/libyul/yulOptimizerTests/structuralSimplifier/switch_only_default.yul new file mode 100644 index 00000000..7ca815a7 --- /dev/null +++ b/test/libyul/yulOptimizerTests/structuralSimplifier/switch_only_default.yul @@ -0,0 +1,11 @@ +{ + switch mload(0) default { mstore(1, 2) } +} +// ---- +// structuralSimplifier +// { +// pop(mload(0)) +// { +// mstore(1, 2) +// } +// } diff --git a/test/libyul/yulOptimizerTests/structuralSimplifier/switch_to_if.yul b/test/libyul/yulOptimizerTests/structuralSimplifier/switch_to_if.yul new file mode 100644 index 00000000..a741ac2f --- /dev/null +++ b/test/libyul/yulOptimizerTests/structuralSimplifier/switch_to_if.yul @@ -0,0 +1,11 @@ +{ + switch 1 case 2 { mstore(0, 0) } +} +// ---- +// structuralSimplifier +// { +// if eq(2, 1) +// { +// mstore(0, 0) +// } +// } diff --git a/test/tools/yulopti.cpp b/test/tools/yulopti.cpp index d6dbc1b1..477de42f 100644 --- a/test/tools/yulopti.cpp +++ b/test/tools/yulopti.cpp @@ -46,6 +46,7 @@ #include <libyul/optimiser/ExpressionJoiner.h> #include <libyul/optimiser/RedundantAssignEliminator.h> #include <libyul/optimiser/SSATransform.h> +#include <libyul/optimiser/StructuralSimplifier.h> #include <libyul/optimiser/VarDeclPropagator.h> #include <libdevcore/JSON.h> @@ -124,7 +125,8 @@ public: } cout << "(q)quit/(f)flatten/(c)se/propagate var(d)ecls/(x)plit/(j)oin/(g)rouper/(h)oister/" << endl; cout << " (e)xpr inline/(i)nline/(s)implify/(u)nusedprune/ss(a) transform/" << endl; - cout << " (r)edundant assign elim./re(m)aterializer/f(o)r-loop-pre-rewriter? "; + cout << " (r)edundant assign elim./re(m)aterializer/f(o)r-loop-pre-rewriter/" << endl; + cout << " s(t)ructural simplifier? " << endl; cout.flush(); int option = readStandardInputChar(); cout << ' ' << char(option) << endl; @@ -165,6 +167,9 @@ public: case 's': ExpressionSimplifier::run(*m_ast); break; + case 't': + (StructuralSimplifier{})(*m_ast); + break; case 'u': UnusedPruner::runUntilStabilised(*m_ast); break; |