From 2b6a7665ee79e1397f72cca8fb21e44e29045844 Mon Sep 17 00:00:00 2001 From: chriseth Date: Fri, 2 Feb 2018 15:23:44 +0100 Subject: Refactor data flow analysis out of remat. --- libjulia/optimiser/DataFlowAnalyzer.cpp | 195 ++++++++++++++++++++++++++++++++ 1 file changed, 195 insertions(+) create mode 100644 libjulia/optimiser/DataFlowAnalyzer.cpp (limited to 'libjulia/optimiser/DataFlowAnalyzer.cpp') diff --git a/libjulia/optimiser/DataFlowAnalyzer.cpp b/libjulia/optimiser/DataFlowAnalyzer.cpp new file mode 100644 index 00000000..389f8715 --- /dev/null +++ b/libjulia/optimiser/DataFlowAnalyzer.cpp @@ -0,0 +1,195 @@ +/*( + 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 flaw 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 + +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); + solAssert(_assignment.value, ""); + 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().first += 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.push_back(make_pair(set(), true)); + for (auto const& parameter: _fun.parameters) + m_variableScopes.back().first.insert(parameter.name); + for (auto const& var: _fun.returnVariables) + m_variableScopes.back().first.insert(var.name); + ASTModifier::operator()(_fun); + m_variableScopes.pop_back(); +} + +void DataFlowAnalyzer::operator()(ForLoop& _for) +{ + // Special scope handling of the pre block. + m_variableScopes.push_back(make_pair(set(), 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.push_back(make_pair(set(), false)); + ASTModifier::operator()(_block); + m_variableScopes.pop_back(); + solAssert(numScopes == m_variableScopes.size(), ""); +} + +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. + // TODO: Add a test for that + if (_value && movableChecker.movable() && !movableChecker.referencedVariables().count(name)) + // TODO If _value is null, we could use zero. + 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.first.count(_variableName)) + return true; + if (scope.second) + return false; + } + return false; +} -- cgit v1.2.3 From 88a5d152d028d597fd8cd90bd99ee5b7f1388191 Mon Sep 17 00:00:00 2001 From: chriseth Date: Mon, 5 Feb 2018 18:02:32 +0100 Subject: Introduce struct for scopes. --- libjulia/optimiser/DataFlowAnalyzer.cpp | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) (limited to 'libjulia/optimiser/DataFlowAnalyzer.cpp') diff --git a/libjulia/optimiser/DataFlowAnalyzer.cpp b/libjulia/optimiser/DataFlowAnalyzer.cpp index 389f8715..9ee3215d 100644 --- a/libjulia/optimiser/DataFlowAnalyzer.cpp +++ b/libjulia/optimiser/DataFlowAnalyzer.cpp @@ -51,7 +51,7 @@ void DataFlowAnalyzer::operator()(VariableDeclaration& _varDecl) set names; for (auto const& var: _varDecl.variables) names.insert(var.name); - m_variableScopes.back().first += names; + m_variableScopes.back().variables += names; if (_varDecl.value) visit(*_varDecl.value); handleAssignment(names, _varDecl.value.get()); @@ -84,11 +84,11 @@ void DataFlowAnalyzer::operator()(Switch& _switch) void DataFlowAnalyzer::operator()(FunctionDefinition& _fun) { - m_variableScopes.push_back(make_pair(set(), true)); + m_variableScopes.emplace_back(true); for (auto const& parameter: _fun.parameters) - m_variableScopes.back().first.insert(parameter.name); + m_variableScopes.back().variables.insert(parameter.name); for (auto const& var: _fun.returnVariables) - m_variableScopes.back().first.insert(var.name); + m_variableScopes.back().variables.insert(var.name); ASTModifier::operator()(_fun); m_variableScopes.pop_back(); } @@ -96,7 +96,7 @@ void DataFlowAnalyzer::operator()(FunctionDefinition& _fun) void DataFlowAnalyzer::operator()(ForLoop& _for) { // Special scope handling of the pre block. - m_variableScopes.push_back(make_pair(set(), false)); + m_variableScopes.emplace_back(false); for (auto& statement: _for.pre.statements) visit(statement); @@ -117,7 +117,7 @@ void DataFlowAnalyzer::operator()(ForLoop& _for) void DataFlowAnalyzer::operator()(Block& _block) { size_t numScopes = m_variableScopes.size(); - m_variableScopes.push_back(make_pair(set(), false)); + m_variableScopes.emplace_back(false); ASTModifier::operator()(_block); m_variableScopes.pop_back(); solAssert(numScopes == m_variableScopes.size(), ""); @@ -186,9 +186,9 @@ bool DataFlowAnalyzer::inScope(string const& _variableName) const { for (auto const& scope: m_variableScopes | boost::adaptors::reversed) { - if (scope.first.count(_variableName)) + if (scope.variables.count(_variableName)) return true; - if (scope.second) + if (scope.isFunction) return false; } return false; -- cgit v1.2.3 From c0abddc9dcbf1f0437ac04119a0c8c238fad44c8 Mon Sep 17 00:00:00 2001 From: chriseth Date: Tue, 6 Feb 2018 12:58:51 +0100 Subject: Test for self-referring assignment. --- libjulia/optimiser/DataFlowAnalyzer.cpp | 2 -- 1 file changed, 2 deletions(-) (limited to 'libjulia/optimiser/DataFlowAnalyzer.cpp') diff --git a/libjulia/optimiser/DataFlowAnalyzer.cpp b/libjulia/optimiser/DataFlowAnalyzer.cpp index 9ee3215d..56653393 100644 --- a/libjulia/optimiser/DataFlowAnalyzer.cpp +++ b/libjulia/optimiser/DataFlowAnalyzer.cpp @@ -135,9 +135,7 @@ void DataFlowAnalyzer::handleAssignment(set const& _variables, Expressio string const& name = *_variables.begin(); // Expression has to be movable and cannot contain a reference // to the variable that will be assigned to. - // TODO: Add a test for that if (_value && movableChecker.movable() && !movableChecker.referencedVariables().count(name)) - // TODO If _value is null, we could use zero. m_value[name] = _value; } -- cgit v1.2.3