diff options
Diffstat (limited to 'libjulia/optimiser')
23 files changed, 1545 insertions, 6 deletions
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); + +} +} |