From 9a4bec7e474a310c7f93ff3b84928e0e9ba9cce6 Mon Sep 17 00:00:00 2001 From: Christian Parpart Date: Mon, 15 Oct 2018 11:52:35 +0200 Subject: Renaming libjulia to libyul --- libyul/optimiser/DataFlowAnalyzer.cpp | 193 ++++++++++++++++++++++++++++++++++ 1 file changed, 193 insertions(+) create mode 100644 libyul/optimiser/DataFlowAnalyzer.cpp (limited to 'libyul/optimiser/DataFlowAnalyzer.cpp') diff --git a/libyul/optimiser/DataFlowAnalyzer.cpp b/libyul/optimiser/DataFlowAnalyzer.cpp new file mode 100644 index 00000000..3300a2bd --- /dev/null +++ b/libyul/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 . +*/ +/** + * 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. + */ + +#include + +#include +#include +#include + +#include + +#include + +#include + +using namespace std; +using namespace dev; +using namespace dev::julia; + +void DataFlowAnalyzer::operator()(Assignment& _assignment) +{ + set names; + for (auto const& var: _assignment.variableNames) + names.insert(var.name); + assertThrow(_assignment.value, OptimizerException, ""); + visit(*_assignment.value); + handleAssignment(names, _assignment.value.get()); +} + +void DataFlowAnalyzer::operator()(VariableDeclaration& _varDecl) +{ + set 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 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(); + assertThrow(numScopes == m_variableScopes.size(), OptimizerException, ""); +} + +void DataFlowAnalyzer::handleAssignment(set 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 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 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; +} -- cgit v1.2.3 From 1304361b9c48438d5c55903492b5f11c3dac73e5 Mon Sep 17 00:00:00 2001 From: Christian Parpart Date: Mon, 15 Oct 2018 11:58:51 +0200 Subject: Renaming namespace dev::julia to dev::yul. --- libyul/optimiser/DataFlowAnalyzer.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'libyul/optimiser/DataFlowAnalyzer.cpp') diff --git a/libyul/optimiser/DataFlowAnalyzer.cpp b/libyul/optimiser/DataFlowAnalyzer.cpp index 3300a2bd..ca1e5153 100644 --- a/libyul/optimiser/DataFlowAnalyzer.cpp +++ b/libyul/optimiser/DataFlowAnalyzer.cpp @@ -34,7 +34,7 @@ using namespace std; using namespace dev; -using namespace dev::julia; +using namespace dev::yul; void DataFlowAnalyzer::operator()(Assignment& _assignment) { -- cgit v1.2.3 From 48749146da6bd335928126855053ea0e3b66aee4 Mon Sep 17 00:00:00 2001 From: chriseth Date: Thu, 18 Oct 2018 14:45:11 +0200 Subject: Fix a bug in CSE where a variable that was already out of scope was used. --- libyul/optimiser/DataFlowAnalyzer.cpp | 35 ++++++++++++++++++++++------------- 1 file changed, 22 insertions(+), 13 deletions(-) (limited to 'libyul/optimiser/DataFlowAnalyzer.cpp') diff --git a/libyul/optimiser/DataFlowAnalyzer.cpp b/libyul/optimiser/DataFlowAnalyzer.cpp index ca1e5153..7ac42c30 100644 --- a/libyul/optimiser/DataFlowAnalyzer.cpp +++ b/libyul/optimiser/DataFlowAnalyzer.cpp @@ -84,19 +84,19 @@ void DataFlowAnalyzer::operator()(Switch& _switch) void DataFlowAnalyzer::operator()(FunctionDefinition& _fun) { - m_variableScopes.emplace_back(true); + pushScope(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(); + popScope(); } void DataFlowAnalyzer::operator()(ForLoop& _for) { // Special scope handling of the pre block. - m_variableScopes.emplace_back(false); + pushScope(false); for (auto& statement: _for.pre.statements) visit(statement); @@ -110,16 +110,15 @@ void DataFlowAnalyzer::operator()(ForLoop& _for) (*this)(_for.post); clearValues(assignments.names()); - - m_variableScopes.pop_back(); + popScope(); } void DataFlowAnalyzer::operator()(Block& _block) { size_t numScopes = m_variableScopes.size(); - m_variableScopes.emplace_back(false); + pushScope(false); ASTModifier::operator()(_block); - m_variableScopes.pop_back(); + popScope(); assertThrow(numScopes == m_variableScopes.size(), OptimizerException, ""); } @@ -148,7 +147,18 @@ void DataFlowAnalyzer::handleAssignment(set const& _variables, Expressio } } -void DataFlowAnalyzer::clearValues(set const& _variables) +void DataFlowAnalyzer::pushScope(bool _functionScope) +{ + m_variableScopes.emplace_back(_functionScope); +} + +void DataFlowAnalyzer::popScope() +{ + clearValues(std::move(m_variableScopes.back().variables)); + m_variableScopes.pop_back(); +} + +void DataFlowAnalyzer::clearValues(set _variables) { // All variables that reference variables to be cleared also have to be // cleared, but not recursively, since only the value of the original @@ -163,16 +173,15 @@ void DataFlowAnalyzer::clearValues(set const& _variables) // 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 variables = _variables; // Clear variables that reference variables to be cleared. - for (auto const& name: variables) + for (auto const& name: _variables) for (auto const& ref: m_referencedBy[name]) - variables.insert(ref); + _variables.insert(ref); // Clear the value and update the reference relation. - for (auto const& name: variables) + for (auto const& name: _variables) m_value.erase(name); - for (auto const& name: variables) + for (auto const& name: _variables) { for (auto const& ref: m_references[name]) m_referencedBy[ref].erase(name); -- cgit v1.2.3 From 674e17c2a895eff6729357d8c10db709ac368b79 Mon Sep 17 00:00:00 2001 From: chriseth Date: Mon, 29 Oct 2018 15:12:02 +0100 Subject: Performance: Replace string by special single-copy YulString class. --- libyul/optimiser/DataFlowAnalyzer.cpp | 26 +++++++++++++------------- 1 file changed, 13 insertions(+), 13 deletions(-) (limited to 'libyul/optimiser/DataFlowAnalyzer.cpp') diff --git a/libyul/optimiser/DataFlowAnalyzer.cpp b/libyul/optimiser/DataFlowAnalyzer.cpp index 7ac42c30..1ff1d2f0 100644 --- a/libyul/optimiser/DataFlowAnalyzer.cpp +++ b/libyul/optimiser/DataFlowAnalyzer.cpp @@ -38,9 +38,9 @@ using namespace dev::yul; void DataFlowAnalyzer::operator()(Assignment& _assignment) { - set names; + set names; for (auto const& var: _assignment.variableNames) - names.insert(var.name); + names.emplace(var.name); assertThrow(_assignment.value, OptimizerException, ""); visit(*_assignment.value); handleAssignment(names, _assignment.value.get()); @@ -48,9 +48,9 @@ void DataFlowAnalyzer::operator()(Assignment& _assignment) void DataFlowAnalyzer::operator()(VariableDeclaration& _varDecl) { - set names; + set names; for (auto const& var: _varDecl.variables) - names.insert(var.name); + names.emplace(var.name); m_variableScopes.back().variables += names; if (_varDecl.value) visit(*_varDecl.value); @@ -69,7 +69,7 @@ void DataFlowAnalyzer::operator()(If& _if) void DataFlowAnalyzer::operator()(Switch& _switch) { visit(*_switch.expression); - set assignedVariables; + set assignedVariables; for (auto& _case: _switch.cases) { (*this)(_case.body); @@ -86,9 +86,9 @@ void DataFlowAnalyzer::operator()(FunctionDefinition& _fun) { pushScope(true); for (auto const& parameter: _fun.parameters) - m_variableScopes.back().variables.insert(parameter.name); + m_variableScopes.back().variables.emplace(parameter.name); for (auto const& var: _fun.returnVariables) - m_variableScopes.back().variables.insert(var.name); + m_variableScopes.back().variables.emplace(var.name); ASTModifier::operator()(_fun); popScope(); } @@ -122,7 +122,7 @@ void DataFlowAnalyzer::operator()(Block& _block) assertThrow(numScopes == m_variableScopes.size(), OptimizerException, ""); } -void DataFlowAnalyzer::handleAssignment(set const& _variables, Expression* _value) +void DataFlowAnalyzer::handleAssignment(set const& _variables, Expression* _value) { clearValues(_variables); @@ -131,7 +131,7 @@ void DataFlowAnalyzer::handleAssignment(set const& _variables, Expressio movableChecker.visit(*_value); if (_variables.size() == 1) { - string const& name = *_variables.begin(); + YulString 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)) @@ -143,7 +143,7 @@ void DataFlowAnalyzer::handleAssignment(set const& _variables, Expressio { m_references[name] = referencedVariables; for (auto const& ref: referencedVariables) - m_referencedBy[ref].insert(name); + m_referencedBy[ref].emplace(name); } } @@ -158,7 +158,7 @@ void DataFlowAnalyzer::popScope() m_variableScopes.pop_back(); } -void DataFlowAnalyzer::clearValues(set _variables) +void DataFlowAnalyzer::clearValues(set _variables) { // All variables that reference variables to be cleared also have to be // cleared, but not recursively, since only the value of the original @@ -176,7 +176,7 @@ void DataFlowAnalyzer::clearValues(set _variables) // Clear variables that reference variables to be cleared. for (auto const& name: _variables) for (auto const& ref: m_referencedBy[name]) - _variables.insert(ref); + _variables.emplace(ref); // Clear the value and update the reference relation. for (auto const& name: _variables) @@ -189,7 +189,7 @@ void DataFlowAnalyzer::clearValues(set _variables) } } -bool DataFlowAnalyzer::inScope(string const& _variableName) const +bool DataFlowAnalyzer::inScope(YulString _variableName) const { for (auto const& scope: m_variableScopes | boost::adaptors::reversed) { -- cgit v1.2.3 From b2b11eaa00de3174ead7dbeb77bbc315719bd79d Mon Sep 17 00:00:00 2001 From: chriseth Date: Sun, 28 Oct 2018 12:57:13 +0100 Subject: Fix data flow analyzer for function definitions. --- libyul/optimiser/DataFlowAnalyzer.cpp | 13 +++++++++++++ 1 file changed, 13 insertions(+) (limited to 'libyul/optimiser/DataFlowAnalyzer.cpp') diff --git a/libyul/optimiser/DataFlowAnalyzer.cpp b/libyul/optimiser/DataFlowAnalyzer.cpp index 1ff1d2f0..134777d0 100644 --- a/libyul/optimiser/DataFlowAnalyzer.cpp +++ b/libyul/optimiser/DataFlowAnalyzer.cpp @@ -84,13 +84,26 @@ void DataFlowAnalyzer::operator()(Switch& _switch) void DataFlowAnalyzer::operator()(FunctionDefinition& _fun) { + // Save all information. We might rather reinstantiate this class, + // but this could be difficult if it is subclassed. + map value; + map> references; + map> referencedBy; + m_value.swap(value); + m_references.swap(references); + m_referencedBy.swap(referencedBy); pushScope(true); + for (auto const& parameter: _fun.parameters) m_variableScopes.back().variables.emplace(parameter.name); for (auto const& var: _fun.returnVariables) m_variableScopes.back().variables.emplace(var.name); ASTModifier::operator()(_fun); + popScope(); + m_value.swap(value); + m_references.swap(references); + m_referencedBy.swap(referencedBy); } void DataFlowAnalyzer::operator()(ForLoop& _for) -- cgit v1.2.3