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 ++++++++++++++++++++++++++++++++ libjulia/optimiser/DataFlowAnalyzer.h | 78 +++++++++++++ libjulia/optimiser/Rematerialiser.cpp | 159 ++------------------------ libjulia/optimiser/Rematerialiser.h | 29 +---- 4 files changed, 284 insertions(+), 177 deletions(-) create mode 100644 libjulia/optimiser/DataFlowAnalyzer.cpp create mode 100644 libjulia/optimiser/DataFlowAnalyzer.h 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; +} diff --git a/libjulia/optimiser/DataFlowAnalyzer.h b/libjulia/optimiser/DataFlowAnalyzer.h new file mode 100644 index 00000000..16d6e72b --- /dev/null +++ b/libjulia/optimiser/DataFlowAnalyzer.h @@ -0,0 +1,78 @@ +/* + 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. + */ + +#pragma once + +#include + +#include +#include +#include + +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 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 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 m_value; + /// m_references[a].contains(b) <=> the current expression assigned to a references b + std::map> m_references; + /// m_referencedBy[b].contains(a) <=> the current expression assigned to a references b + std::map> m_referencedBy; + /// List of scopes, where each scope is a set of variables and a bool that tells + /// whether it is a function body (true) or not. + std::vector, bool>> m_variableScopes; +}; + +} +} diff --git a/libjulia/optimiser/Rematerialiser.cpp b/libjulia/optimiser/Rematerialiser.cpp index bf7d7d16..eaa75e33 100644 --- a/libjulia/optimiser/Rematerialiser.cpp +++ b/libjulia/optimiser/Rematerialiser.cpp @@ -20,176 +20,35 @@ #include +#include #include -#include #include -#include - -#include - -#include - using namespace std; using namespace dev; using namespace dev::julia; -void Rematerialiser::operator()(Assignment& _assignment) -{ - set names; - for (auto const& var: _assignment.variableNames) - names.insert(var.name); - handleAssignment(names, _assignment.value.get()); -} - -void Rematerialiser::operator()(VariableDeclaration& _varDecl) -{ - set names; - for (auto const& var: _varDecl.variables) - names.insert(var.name); - m_variableScopes.back().first += names; - handleAssignment(names, _varDecl.value.get()); -} - -void Rematerialiser::operator()(If& _if) -{ - ASTModifier::operator()(_if); - - Assignments ass; - ass(_if.body); - handleAssignment(ass.names(), nullptr); -} - -void Rematerialiser::operator()(Switch& _switch) -{ - boost::apply_visitor(*this, *_switch.expression); - set assignedVariables; - for (auto& _case: _switch.cases) - { - (*this)(_case.body); - Assignments ass; - ass(_case.body); - assignedVariables += ass.names(); - // This is a little too destructive, we could retain the old replacements. - handleAssignment(ass.names(), nullptr); - } - handleAssignment(assignedVariables, nullptr); -} - -void Rematerialiser::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 Rematerialiser::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 ass; - ass(_for.body); - ass(_for.post); - handleAssignment(ass.names(), nullptr); - - visit(*_for.condition); - (*this)(_for.body); - (*this)(_for.post); - - handleAssignment(ass.names(), nullptr); - - m_variableScopes.pop_back(); -} - -void Rematerialiser::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 Rematerialiser::handleAssignment(set const& _variables, Expression* _value) -{ - MovableChecker movableChecker; - if (_value) - { - visit(*_value); - movableChecker.visit(*_value); - } - if (_variables.size() == 1) - { - string const& name = *_variables.begin(); - if (movableChecker.movable() && _value) - // TODO Plus heuristic about size of value - // TODO If _value is null, we could use zero. - m_substitutions[name] = _value; - else - m_substitutions.erase(name); - } - else - for (auto const& name: _variables) - m_substitutions.erase(name); - - // Disallow substitutions that use a variable that will be reassigned by this assignment. - for (auto const& name: _variables) - for (auto const& ref: m_referencedBy[name]) - m_substitutions.erase(ref); - // Update the fact which variables are referenced by the newly assigned variables - for (auto const& name: _variables) - { - for (auto const& ref: m_references[name]) - m_referencedBy[ref].erase(name); - m_references[name].clear(); - } - auto const& referencedVariables = movableChecker.referencedVariables(); - for (auto const& name: _variables) - { - m_references[name] = referencedVariables; - for (auto const& ref: referencedVariables) - m_referencedBy[ref].insert(name); - } -} - -bool Rematerialiser::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; -} - void Rematerialiser::visit(Expression& _e) { if (_e.type() == typeid(Identifier)) { Identifier& identifier = boost::get(_e); - if (m_substitutions.count(identifier.name)) + if (m_value.count(identifier.name)) { string name = identifier.name; - bool doSubstitute = true; + bool expressionValid = true; for (auto const& ref: m_references[name]) if (!inScope(ref)) { - doSubstitute = false; + expressionValid = false; break; } - if (doSubstitute) - _e = (ASTCopier{}).translate(*m_substitutions.at(name)); + solAssert(m_value.at(name), ""); + auto const& value = *m_value.at(name); + if (expressionValid && CodeSize::codeSize(value) <= 7) + _e = (ASTCopier{}).translate(value); } } - ASTModifier::visit(_e); + DataFlowAnalyzer::visit(_e); } diff --git a/libjulia/optimiser/Rematerialiser.h b/libjulia/optimiser/Rematerialiser.h index 1accc3f6..60dbfada 100644 --- a/libjulia/optimiser/Rematerialiser.h +++ b/libjulia/optimiser/Rematerialiser.h @@ -20,7 +20,7 @@ #pragma once -#include +#include #include #include @@ -36,37 +36,12 @@ namespace julia * * Prerequisite: Disambiguator */ -class Rematerialiser: public ASTModifier +class Rematerialiser: public DataFlowAnalyzer { -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: using ASTModifier::visit; virtual void visit(Expression& _e) override; -private: - void handleAssignment(std::set const& _names, Expression* _value); - - /// Returns true iff the variable is in scope. - bool inScope(std::string const& _variableName) const; - - /// Substitutions to be performed, if possible. - std::map m_substitutions; - /// m_references[a].contains(b) <=> the current expression assigned to a references b - std::map> m_references; - /// m_referencedBy[b].contains(a) <=> the current expression assigned to a references b - std::map> m_referencedBy; - /// List of scopes, where each scope is a set of variables and a bool that tells - /// whether it is a function body (true) or not. - std::vector, bool>> m_variableScopes; }; } -- cgit