From 1eb60cbb3952df395df79ca1737f41708a658d4b Mon Sep 17 00:00:00 2001 From: Daniel Kirchner Date: Mon, 3 Dec 2018 17:19:37 +0100 Subject: Add structural simplifier as optimization step for Yul. --- libyul/CMakeLists.txt | 1 + libyul/optimiser/SimplificationRules.cpp | 5 +- libyul/optimiser/StructuralSimplifier.cpp | 138 ++++++++++++++++++++++++++++++ libyul/optimiser/StructuralSimplifier.h | 49 +++++++++++ libyul/optimiser/Suite.cpp | 4 + libyul/optimiser/Utilities.cpp | 9 ++ libyul/optimiser/Utilities.h | 3 + 7 files changed, 205 insertions(+), 4 deletions(-) create mode 100644 libyul/optimiser/StructuralSimplifier.cpp create mode 100644 libyul/optimiser/StructuralSimplifier.h (limited to 'libyul') 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(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(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 . +*/ +#include +#include +#include +#include +#include +#include + +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& _statements) +{ + using OptionalStatements = boost::optional>; + GenericFallbackReturnsVisitor 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(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( + [&](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( + [&](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 . +*/ +#pragma once + +#include +#include + +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& _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 #include #include +#include #include #include #include @@ -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 #include +#include #include @@ -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 #include 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); + } -- cgit v1.2.3