aboutsummaryrefslogtreecommitdiffstats
path: root/libjulia
diff options
context:
space:
mode:
Diffstat (limited to 'libjulia')
-rw-r--r--libjulia/optimiser/DataFlowAnalyzer.cpp195
-rw-r--r--libjulia/optimiser/DataFlowAnalyzer.h78
-rw-r--r--libjulia/optimiser/Rematerialiser.cpp159
-rw-r--r--libjulia/optimiser/Rematerialiser.h29
4 files changed, 284 insertions, 177 deletions
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 <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().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<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.push_back(make_pair(set<string>(), 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<string>(), 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<string>(), 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.
+ // 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<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.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 <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;
+ /// 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<std::pair<std::set<std::string>, 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 <libjulia/optimiser/Rematerialiser.h>
+#include <libjulia/optimiser/Metrics.h>
#include <libjulia/optimiser/ASTCopier.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 Rematerialiser::operator()(Assignment& _assignment)
-{
- set<string> names;
- for (auto const& var: _assignment.variableNames)
- names.insert(var.name);
- handleAssignment(names, _assignment.value.get());
-}
-
-void Rematerialiser::operator()(VariableDeclaration& _varDecl)
-{
- set<string> 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<string> 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<string>(), 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<string>(), 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<string>(), false));
- ASTModifier::operator()(_block);
- m_variableScopes.pop_back();
- solAssert(numScopes == m_variableScopes.size(), "");
-}
-
-void Rematerialiser::handleAssignment(set<string> 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<Identifier>(_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 <libjulia/optimiser/ASTWalker.h>
+#include <libjulia/optimiser/DataFlowAnalyzer.h>
#include <string>
#include <map>
@@ -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<std::string> 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<std::string, Expression const*> m_substitutions;
- /// 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;
- /// 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<std::pair<std::set<std::string>, bool>> m_variableScopes;
};
}