aboutsummaryrefslogtreecommitdiffstats
path: root/libjulia
diff options
context:
space:
mode:
Diffstat (limited to 'libjulia')
-rw-r--r--libjulia/ASTDataForward.h54
-rw-r--r--libjulia/backends/evm/EVMAssembly.cpp2
-rw-r--r--libjulia/backends/evm/EVMCodeTransform.cpp37
-rw-r--r--libjulia/backends/evm/EVMCodeTransform.h44
-rw-r--r--libjulia/optimiser/ASTCopier.cpp185
-rw-r--r--libjulia/optimiser/ASTCopier.h121
-rw-r--r--libjulia/optimiser/ASTWalker.cpp159
-rw-r--r--libjulia/optimiser/ASTWalker.h120
-rw-r--r--libjulia/optimiser/Disambiguator.cpp85
-rw-r--r--libjulia/optimiser/Disambiguator.h67
-rw-r--r--libjulia/optimiser/FunctionGrouper.cpp49
-rw-r--r--libjulia/optimiser/FunctionGrouper.h46
-rw-r--r--libjulia/optimiser/FunctionHoister.cpp59
-rw-r--r--libjulia/optimiser/FunctionHoister.h52
-rw-r--r--libjulia/optimiser/NameCollector.cpp44
-rw-r--r--libjulia/optimiser/NameCollector.h52
-rw-r--r--libjulia/optimiser/README.md61
-rw-r--r--libjulia/optimiser/Semantics.cpp60
-rw-r--r--libjulia/optimiser/Semantics.h62
-rw-r--r--libjulia/optimiser/Substitution.cpp39
-rw-r--r--libjulia/optimiser/Substitution.h50
21 files changed, 1412 insertions, 36 deletions
diff --git a/libjulia/ASTDataForward.h b/libjulia/ASTDataForward.h
new file mode 100644
index 00000000..143b9c46
--- /dev/null
+++ b/libjulia/ASTDataForward.h
@@ -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/>.
+*/
+/**
+ * @date 2017
+ * Pull in some identifiers from the solidity::assembly namespace.
+ */
+
+#pragma once
+
+#include <libsolidity/inlineasm/AsmDataForward.h>
+
+namespace dev
+{
+namespace julia
+{
+
+using Instruction = solidity::assembly::Instruction;
+using Literal = solidity::assembly::Literal;
+using Label = solidity::assembly::Label;
+using StackAssignment = solidity::assembly::StackAssignment;
+using Identifier = solidity::assembly::Identifier;
+using Assignment = solidity::assembly::Assignment;
+using VariableDeclaration = solidity::assembly::VariableDeclaration;
+using FunctionalInstruction = solidity::assembly::FunctionalInstruction;
+using FunctionDefinition = solidity::assembly::FunctionDefinition;
+using FunctionCall = solidity::assembly::FunctionCall;
+using If = solidity::assembly::If;
+using Case = solidity::assembly::Case;
+using Switch = solidity::assembly::Switch;
+using ForLoop = solidity::assembly::ForLoop;
+using ExpressionStatement = solidity::assembly::ExpressionStatement;
+using Block = solidity::assembly::Block;
+
+using TypedName = solidity::assembly::TypedName;
+
+using Expression = boost::variant<FunctionalInstruction, FunctionCall, Identifier, Literal>;
+using Statement = boost::variant<ExpressionStatement, Instruction, Label, StackAssignment, Assignment, VariableDeclaration, FunctionDefinition, If, Switch, ForLoop, Block>;
+
+}
+}
diff --git a/libjulia/backends/evm/EVMAssembly.cpp b/libjulia/backends/evm/EVMAssembly.cpp
index 1d499b20..07ad05c9 100644
--- a/libjulia/backends/evm/EVMAssembly.cpp
+++ b/libjulia/backends/evm/EVMAssembly.cpp
@@ -26,7 +26,7 @@
using namespace std;
using namespace dev;
-using namespace julia;
+using namespace dev::julia;
namespace
{
diff --git a/libjulia/backends/evm/EVMCodeTransform.cpp b/libjulia/backends/evm/EVMCodeTransform.cpp
index 13d9d011..0c7365fb 100644
--- a/libjulia/backends/evm/EVMCodeTransform.cpp
+++ b/libjulia/backends/evm/EVMCodeTransform.cpp
@@ -31,7 +31,8 @@ using namespace std;
using namespace dev;
using namespace dev::julia;
using namespace dev::solidity;
-using namespace dev::solidity::assembly;
+
+using Scope = dev::solidity::assembly::Scope;
void CodeTransform::operator()(VariableDeclaration const& _varDecl)
{
@@ -76,6 +77,13 @@ void CodeTransform::operator()(StackAssignment const& _assignment)
checkStackHeight(&_assignment);
}
+void CodeTransform::operator()(ExpressionStatement const& _statement)
+{
+ m_assembly.setSourceLocation(_statement.location);
+ boost::apply_visitor(*this, _statement.expression);
+ checkStackHeight(&_statement);
+}
+
void CodeTransform::operator()(Label const& _label)
{
m_assembly.setSourceLocation(_label.location);
@@ -124,11 +132,11 @@ void CodeTransform::operator()(FunctionCall const& _call)
void CodeTransform::operator()(FunctionalInstruction const& _instruction)
{
if (m_evm15 && (
- _instruction.instruction.instruction == solidity::Instruction::JUMP ||
- _instruction.instruction.instruction == solidity::Instruction::JUMPI
+ _instruction.instruction == solidity::Instruction::JUMP ||
+ _instruction.instruction == solidity::Instruction::JUMPI
))
{
- bool const isJumpI = _instruction.instruction.instruction == solidity::Instruction::JUMPI;
+ bool const isJumpI = _instruction.instruction == solidity::Instruction::JUMPI;
if (isJumpI)
{
solAssert(_instruction.arguments.size() == 2, "");
@@ -149,7 +157,8 @@ void CodeTransform::operator()(FunctionalInstruction const& _instruction)
{
for (auto const& arg: _instruction.arguments | boost::adaptors::reversed)
visitExpression(arg);
- (*this)(_instruction.instruction);
+ m_assembly.setSourceLocation(_instruction.location);
+ m_assembly.appendInstruction(_instruction.instruction);
}
checkStackHeight(&_instruction);
}
@@ -289,7 +298,7 @@ void CodeTransform::operator()(FunctionDefinition const& _function)
solAssert(m_info.scopes.at(&_function.body), "");
Scope* varScope = m_info.scopes.at(m_info.virtualBlocks.at(&_function).get()).get();
solAssert(varScope, "");
- for (auto const& v: _function.arguments | boost::adaptors::reversed)
+ for (auto const& v: _function.parameters | boost::adaptors::reversed)
{
auto& var = boost::get<Scope::Variable>(varScope->identifiers.at(v.name));
m_context->variableStackHeights[&var] = height++;
@@ -302,7 +311,7 @@ void CodeTransform::operator()(FunctionDefinition const& _function)
if (m_evm15)
{
m_assembly.appendJumpTo(afterFunction, -stackHeightBefore);
- m_assembly.appendBeginsub(functionEntryID(_function.name, function), _function.arguments.size());
+ m_assembly.appendBeginsub(functionEntryID(_function.name, function), _function.parameters.size());
}
else
{
@@ -311,7 +320,7 @@ void CodeTransform::operator()(FunctionDefinition const& _function)
}
m_stackAdjustment += localStackAdjustment;
- for (auto const& v: _function.returns)
+ for (auto const& v: _function.returnVariables)
{
auto& var = boost::get<Scope::Variable>(varScope->identifiers.at(v.name));
m_context->variableStackHeights[&var] = height++;
@@ -341,9 +350,9 @@ void CodeTransform::operator()(FunctionDefinition const& _function)
// modified parallel to the actual stack.
vector<int> stackLayout;
if (!m_evm15)
- stackLayout.push_back(_function.returns.size()); // Move return label to the top
- stackLayout += vector<int>(_function.arguments.size(), -1); // discard all arguments
- for (size_t i = 0; i < _function.returns.size(); ++i)
+ stackLayout.push_back(_function.returnVariables.size()); // Move return label to the top
+ stackLayout += vector<int>(_function.parameters.size(), -1); // discard all arguments
+ for (size_t i = 0; i < _function.returnVariables.size(); ++i)
stackLayout.push_back(i); // Move return values down, but keep order.
solAssert(stackLayout.size() <= 17, "Stack too deep");
@@ -363,9 +372,9 @@ void CodeTransform::operator()(FunctionDefinition const& _function)
}
if (m_evm15)
- m_assembly.appendReturnsub(_function.returns.size(), stackHeightBefore);
+ m_assembly.appendReturnsub(_function.returnVariables.size(), stackHeightBefore);
else
- m_assembly.appendJump(stackHeightBefore - _function.returns.size());
+ m_assembly.appendJump(stackHeightBefore - _function.returnVariables.size());
m_stackAdjustment -= localStackAdjustment;
m_assembly.appendLabel(afterFunction);
checkStackHeight(&_function);
@@ -458,7 +467,7 @@ AbstractAssembly::LabelID CodeTransform::functionEntryID(string const& _name, Sc
return m_context->functionEntryIDs[&_function];
}
-void CodeTransform::visitExpression(Statement const& _expression)
+void CodeTransform::visitExpression(Expression const& _expression)
{
int height = m_assembly.stackHeight();
boost::apply_visitor(*this, _expression);
diff --git a/libjulia/backends/evm/EVMCodeTransform.h b/libjulia/backends/evm/EVMCodeTransform.h
index 387720a2..0f2aaf95 100644
--- a/libjulia/backends/evm/EVMCodeTransform.h
+++ b/libjulia/backends/evm/EVMCodeTransform.h
@@ -20,8 +20,9 @@
#include <libjulia/backends/evm/EVMAssembly.h>
+#include <libjulia/ASTDataForward.h>
+
#include <libsolidity/inlineasm/AsmScope.h>
-#include <libsolidity/inlineasm/AsmDataForward.h>
#include <boost/variant.hpp>
#include <boost/optional.hpp>
@@ -95,38 +96,39 @@ protected:
{}
public:
- void operator()(solidity::assembly::Instruction const& _instruction);
- void operator()(solidity::assembly::Literal const& _literal);
- void operator()(solidity::assembly::Identifier const& _identifier);
- void operator()(solidity::assembly::FunctionalInstruction const& _instr);
- void operator()(solidity::assembly::FunctionCall const&);
- void operator()(solidity::assembly::Label const& _label);
- void operator()(solidity::assembly::StackAssignment const& _assignment);
- void operator()(solidity::assembly::Assignment const& _assignment);
- void operator()(solidity::assembly::VariableDeclaration const& _varDecl);
- void operator()(solidity::assembly::If const& _if);
- void operator()(solidity::assembly::Switch const& _switch);
- void operator()(solidity::assembly::FunctionDefinition const&);
- void operator()(solidity::assembly::ForLoop const&);
- void operator()(solidity::assembly::Block const& _block);
+ void operator()(Instruction const& _instruction);
+ void operator()(Literal const& _literal);
+ void operator()(Identifier const& _identifier);
+ void operator()(FunctionalInstruction const& _instr);
+ void operator()(FunctionCall const&);
+ void operator()(ExpressionStatement const& _statement);
+ void operator()(Label const& _label);
+ void operator()(StackAssignment const& _assignment);
+ void operator()(Assignment const& _assignment);
+ void operator()(VariableDeclaration const& _varDecl);
+ void operator()(If const& _if);
+ void operator()(Switch const& _switch);
+ void operator()(FunctionDefinition const&);
+ void operator()(ForLoop const&);
+ void operator()(Block const& _block);
private:
- AbstractAssembly::LabelID labelFromIdentifier(solidity::assembly::Identifier const& _identifier);
+ AbstractAssembly::LabelID labelFromIdentifier(Identifier const& _identifier);
/// @returns the label ID corresponding to the given label, allocating a new one if
/// necessary.
AbstractAssembly::LabelID labelID(solidity::assembly::Scope::Label const& _label);
AbstractAssembly::LabelID functionEntryID(std::string const& _name, solidity::assembly::Scope::Function const& _function);
/// Generates code for an expression that is supposed to return a single value.
- void visitExpression(solidity::assembly::Statement const& _expression);
+ void visitExpression(Expression const& _expression);
- void visitStatements(std::vector<solidity::assembly::Statement> const& _statements);
+ void visitStatements(std::vector<Statement> const& _statements);
/// Pops all variables declared in the block and checks that the stack height is equal
/// to @a _blackStartStackHeight.
- void finalizeBlock(solidity::assembly::Block const& _block, int _blockStartStackHeight);
+ void finalizeBlock(Block const& _block, int _blockStartStackHeight);
- void generateMultiAssignment(std::vector<solidity::assembly::Identifier> const& _variableNames);
- void generateAssignment(solidity::assembly::Identifier const& _variableName);
+ void generateMultiAssignment(std::vector<Identifier> const& _variableNames);
+ void generateAssignment(Identifier const& _variableName);
/// Determines the stack height difference to the given variables. Throws
/// if it is not yet in scope or the height difference is too large. Returns
diff --git a/libjulia/optimiser/ASTCopier.cpp b/libjulia/optimiser/ASTCopier.cpp
new file mode 100644
index 00000000..5c47be64
--- /dev/null
+++ b/libjulia/optimiser/ASTCopier.cpp
@@ -0,0 +1,185 @@
+/*
+ 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/>.
+*/
+/**
+ * Creates an independent copy of an AST, renaming identifiers to be unique.
+ */
+
+#include <libjulia/optimiser/ASTCopier.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+#include <libsolidity/interface/Exceptions.h>
+
+#include <libdevcore/Common.h>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+
+
+Statement ASTCopier::operator()(Instruction const&)
+{
+ solAssert(false, "Invalid operation.");
+ return {};
+}
+
+Statement ASTCopier::operator()(ExpressionStatement const& _statement)
+{
+ return ExpressionStatement{ _statement.location, translate(_statement.expression) };
+}
+
+Statement ASTCopier::operator()(VariableDeclaration const& _varDecl)
+{
+ return VariableDeclaration{
+ _varDecl.location,
+ translateVector(_varDecl.variables),
+ translate(_varDecl.value)
+ };
+}
+
+Statement ASTCopier::operator()(Assignment const& _assignment)
+{
+ return Assignment{
+ _assignment.location,
+ translateVector(_assignment.variableNames),
+ translate(_assignment.value)
+ };
+}
+
+Statement ASTCopier::operator()(StackAssignment const&)
+{
+ solAssert(false, "Invalid operation.");
+ return {};
+}
+
+Statement ASTCopier::operator()(Label const&)
+{
+ solAssert(false, "Invalid operation.");
+ return {};
+}
+
+Expression ASTCopier::operator()(FunctionCall const& _call)
+{
+ return FunctionCall{
+ _call.location,
+ translate(_call.functionName),
+ translateVector(_call.arguments)
+ };
+}
+
+Expression ASTCopier::operator()(FunctionalInstruction const& _instruction)
+{
+ return FunctionalInstruction{
+ _instruction.location,
+ _instruction.instruction,
+ translateVector(_instruction.arguments)
+ };
+}
+
+Expression ASTCopier::operator()(Identifier const& _identifier)
+{
+ return Identifier{_identifier.location, translateIdentifier(_identifier.name)};
+}
+
+Expression ASTCopier::operator()(Literal const& _literal)
+{
+ return translate(_literal);
+}
+
+Statement ASTCopier::operator()(If const& _if)
+{
+ return If{_if.location, translate(_if.condition), translate(_if.body)};
+}
+
+Statement ASTCopier::operator()(Switch const& _switch)
+{
+ return Switch{_switch.location, translate(_switch.expression), translateVector(_switch.cases)};
+}
+
+Statement ASTCopier::operator()(FunctionDefinition const& _function)
+{
+ string translatedName = translateIdentifier(_function.name);
+
+ enterFunction(_function);
+ ScopeGuard g([&]() { this->leaveFunction(_function); });
+
+ return FunctionDefinition{
+ _function.location,
+ move(translatedName),
+ translateVector(_function.parameters),
+ translateVector(_function.returnVariables),
+ translate(_function.body)
+ };
+}
+
+Statement ASTCopier::operator()(ForLoop const& _forLoop)
+{
+ enterScope(_forLoop.pre);
+ ScopeGuard g([&]() { this->leaveScope(_forLoop.pre); });
+
+ return ForLoop{
+ _forLoop.location,
+ translate(_forLoop.pre),
+ translate(_forLoop.condition),
+ translate(_forLoop.post),
+ translate(_forLoop.body)
+ };
+}
+
+Statement ASTCopier::operator ()(Block const& _block)
+{
+ return translate(_block);
+}
+
+Expression ASTCopier::translate(Expression const& _expression)
+{
+ return _expression.apply_visitor(static_cast<ExpressionCopier&>(*this));
+}
+
+Statement ASTCopier::translate(Statement const& _statement)
+{
+ return _statement.apply_visitor(static_cast<StatementCopier&>(*this));
+}
+
+Block ASTCopier::translate(Block const& _block)
+{
+ enterScope(_block);
+ ScopeGuard g([&]() { this->leaveScope(_block); });
+
+ return Block{_block.location, translateVector(_block.statements)};
+}
+
+Case ASTCopier::translate(Case const& _case)
+{
+ return Case{_case.location, translate(_case.value), translate(_case.body)};
+}
+
+Identifier ASTCopier::translate(Identifier const& _identifier)
+{
+ return Identifier{_identifier.location, translateIdentifier(_identifier.name)};
+}
+
+Literal ASTCopier::translate(Literal const& _literal)
+{
+ return _literal;
+}
+
+TypedName ASTCopier::translate(TypedName const& _typedName)
+{
+ return TypedName{_typedName.location, translateIdentifier(_typedName.name), _typedName.type};
+}
+
diff --git a/libjulia/optimiser/ASTCopier.h b/libjulia/optimiser/ASTCopier.h
new file mode 100644
index 00000000..36a1ced5
--- /dev/null
+++ b/libjulia/optimiser/ASTCopier.h
@@ -0,0 +1,121 @@
+/*
+ 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/>.
+*/
+/**
+ * Creates an independent copy of an AST, renaming identifiers to be unique.
+ */
+
+#pragma once
+
+#include <libjulia/ASTDataForward.h>
+
+#include <boost/variant.hpp>
+#include <boost/optional.hpp>
+
+#include <vector>
+#include <set>
+#include <memory>
+
+namespace dev
+{
+namespace julia
+{
+
+class ExpressionCopier: public boost::static_visitor<Expression>
+{
+public:
+ virtual Expression operator()(Literal const& _literal) = 0;
+ virtual Expression operator()(Identifier const& _identifier) = 0;
+ virtual Expression operator()(FunctionalInstruction const& _instr) = 0;
+ virtual Expression operator()(FunctionCall const&) = 0;
+};
+
+class StatementCopier: public boost::static_visitor<Statement>
+{
+public:
+ virtual Statement operator()(ExpressionStatement const& _statement) = 0;
+ virtual Statement operator()(Instruction const& _instruction) = 0;
+ virtual Statement operator()(Label const& _label) = 0;
+ virtual Statement operator()(StackAssignment const& _assignment) = 0;
+ virtual Statement operator()(Assignment const& _assignment) = 0;
+ virtual Statement operator()(VariableDeclaration const& _varDecl) = 0;
+ virtual Statement operator()(If const& _if) = 0;
+ virtual Statement operator()(Switch const& _switch) = 0;
+ virtual Statement operator()(FunctionDefinition const&) = 0;
+ virtual Statement operator()(ForLoop const&) = 0;
+ virtual Statement operator()(Block const& _block) = 0;
+};
+
+/**
+ * Creates a copy of a iulia AST potentially replacing identifier names.
+ * Base class to be extended.
+ */
+class ASTCopier: public ExpressionCopier, public StatementCopier
+{
+public:
+ virtual Expression operator()(Literal const& _literal) override;
+ virtual Statement operator()(Instruction const& _instruction) override;
+ virtual Expression operator()(Identifier const& _identifier) override;
+ virtual Expression operator()(FunctionalInstruction const& _instr) override;
+ virtual Expression operator()(FunctionCall const&) override;
+ virtual Statement operator()(ExpressionStatement const& _statement) override;
+ virtual Statement operator()(Label const& _label) override;
+ virtual Statement operator()(StackAssignment const& _assignment) override;
+ virtual Statement operator()(Assignment const& _assignment) override;
+ virtual Statement operator()(VariableDeclaration const& _varDecl) override;
+ virtual Statement operator()(If const& _if) override;
+ virtual Statement operator()(Switch const& _switch) override;
+ virtual Statement operator()(FunctionDefinition const&) override;
+ virtual Statement operator()(ForLoop const&) override;
+ virtual Statement operator()(Block const& _block) override;
+
+ virtual Expression translate(Expression const& _expression);
+ virtual Statement translate(Statement const& _statement);
+
+protected:
+ template <typename T>
+ std::vector<T> translateVector(std::vector<T> const& _values);
+
+ template <typename T>
+ std::shared_ptr<T> translate(std::shared_ptr<T> const& _v)
+ {
+ return _v ? std::make_shared<T>(translate(*_v)) : nullptr;
+ }
+ Block translate(Block const& _block);
+ Case translate(Case const& _case);
+ Identifier translate(Identifier const& _identifier);
+ Literal translate(Literal const& _literal);
+ TypedName translate(TypedName const& _typedName);
+
+ virtual void enterScope(Block const&) { }
+ virtual void leaveScope(Block const&) { }
+ virtual void enterFunction(FunctionDefinition const&) { }
+ virtual void leaveFunction(FunctionDefinition const&) { }
+ virtual std::string translateIdentifier(std::string const& _name) { return _name; }
+};
+
+template <typename T>
+std::vector<T> ASTCopier::translateVector(std::vector<T> const& _values)
+{
+ std::vector<T> translated;
+ for (auto const& v: _values)
+ translated.emplace_back(translate(v));
+ return translated;
+}
+
+
+}
+}
diff --git a/libjulia/optimiser/ASTWalker.cpp b/libjulia/optimiser/ASTWalker.cpp
new file mode 100644
index 00000000..6386b29d
--- /dev/null
+++ b/libjulia/optimiser/ASTWalker.cpp
@@ -0,0 +1,159 @@
+/*
+ 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/>.
+*/
+/**
+ * Generic AST walker.
+ */
+
+#include <libjulia/optimiser/ASTWalker.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+#include <libsolidity/interface/Exceptions.h>
+
+#include <boost/range/adaptor/reversed.hpp>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+using namespace dev::solidity;
+
+
+void ASTWalker::operator()(FunctionalInstruction const& _instr)
+{
+ walkVector(_instr.arguments | boost::adaptors::reversed);
+}
+
+void ASTWalker::operator()(FunctionCall const& _funCall)
+{
+ walkVector(_funCall.arguments | boost::adaptors::reversed);
+}
+
+void ASTWalker::operator()(ExpressionStatement const& _statement)
+{
+ visit(_statement.expression);
+}
+
+void ASTWalker::operator()(Assignment const& _assignment)
+{
+ for (auto const& name: _assignment.variableNames)
+ (*this)(name);
+ visit(*_assignment.value);
+}
+
+void ASTWalker::operator()(VariableDeclaration const& _varDecl)
+{
+ if (_varDecl.value)
+ visit(*_varDecl.value);
+}
+
+void ASTWalker::operator()(If const& _if)
+{
+ visit(*_if.condition);
+ (*this)(_if.body);
+}
+
+void ASTWalker::operator()(Switch const& _switch)
+{
+ visit(*_switch.expression);
+ for (auto const& _case: _switch.cases)
+ {
+ if (_case.value)
+ (*this)(*_case.value);
+ (*this)(_case.body);
+ }
+}
+
+void ASTWalker::operator()(FunctionDefinition const& _fun)
+{
+ (*this)(_fun.body);
+}
+
+void ASTWalker::operator()(ForLoop const& _for)
+{
+ (*this)(_for.pre);
+ visit(*_for.condition);
+ (*this)(_for.post);
+ (*this)(_for.body);
+}
+
+void ASTWalker::operator()(Block const& _block)
+{
+ walkVector(_block.statements);
+}
+
+void ASTModifier::operator()(FunctionalInstruction& _instr)
+{
+ walkVector(_instr.arguments | boost::adaptors::reversed);
+}
+
+void ASTModifier::operator()(FunctionCall& _funCall)
+{
+ walkVector(_funCall.arguments | boost::adaptors::reversed);
+}
+
+void ASTModifier::operator()(ExpressionStatement& _statement)
+{
+ visit(_statement.expression);
+}
+
+void ASTModifier::operator()(Assignment& _assignment)
+{
+ for (auto& name: _assignment.variableNames)
+ (*this)(name);
+ visit(*_assignment.value);
+}
+
+void ASTModifier::operator()(VariableDeclaration& _varDecl)
+{
+ if (_varDecl.value)
+ visit(*_varDecl.value);
+}
+
+void ASTModifier::operator()(If& _if)
+{
+ visit(*_if.condition);
+ (*this)(_if.body);
+}
+
+void ASTModifier::operator()(Switch& _switch)
+{
+ visit(*_switch.expression);
+ for (auto& _case: _switch.cases)
+ {
+ if (_case.value)
+ (*this)(*_case.value);
+ (*this)(_case.body);
+ }
+}
+
+void ASTModifier::operator()(FunctionDefinition& _fun)
+{
+ (*this)(_fun.body);
+}
+
+void ASTModifier::operator()(ForLoop& _for)
+{
+ (*this)(_for.pre);
+ visit(*_for.condition);
+ (*this)(_for.post);
+ (*this)(_for.body);
+}
+
+void ASTModifier::operator()(Block& _block)
+{
+ walkVector(_block.statements);
+}
diff --git a/libjulia/optimiser/ASTWalker.h b/libjulia/optimiser/ASTWalker.h
new file mode 100644
index 00000000..dbf8194b
--- /dev/null
+++ b/libjulia/optimiser/ASTWalker.h
@@ -0,0 +1,120 @@
+/*
+ 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/>.
+*/
+/**
+ * Generic AST walker.
+ */
+
+#pragma once
+
+#include <libjulia/ASTDataForward.h>
+
+#include <libsolidity/interface/Exceptions.h>
+
+#include <boost/variant.hpp>
+#include <boost/optional.hpp>
+
+#include <vector>
+#include <set>
+#include <map>
+
+namespace dev
+{
+namespace julia
+{
+
+/**
+ * Generic AST walker.
+ */
+class ASTWalker: public boost::static_visitor<>
+{
+public:
+ virtual void operator()(Literal const&) {}
+ virtual void operator()(Instruction const&) { solAssert(false, ""); }
+ virtual void operator()(Identifier const&) {}
+ virtual void operator()(FunctionalInstruction const& _instr);
+ virtual void operator()(FunctionCall const& _funCall);
+ virtual void operator()(ExpressionStatement const& _statement);
+ virtual void operator()(Label const&) { solAssert(false, ""); }
+ virtual void operator()(StackAssignment const&) { solAssert(false, ""); }
+ virtual void operator()(Assignment const& _assignment);
+ virtual void operator()(VariableDeclaration const& _varDecl);
+ virtual void operator()(If const& _if);
+ virtual void operator()(Switch const& _switch);
+ virtual void operator()(FunctionDefinition const&);
+ virtual void operator()(ForLoop const&);
+ virtual void operator()(Block const& _block);
+
+ virtual void visit(Statement const& _st)
+ {
+ boost::apply_visitor(*this, _st);
+ }
+ virtual void visit(Expression const& _e)
+ {
+ boost::apply_visitor(*this, _e);
+ }
+
+protected:
+ template <class T>
+ void walkVector(T const& _statements)
+ {
+ for (auto const& st: _statements)
+ visit(st);
+ }
+};
+
+/**
+ * Generic AST modifier (i.e. non-const version of ASTWalker).
+ */
+class ASTModifier: public boost::static_visitor<>
+{
+public:
+ virtual void operator()(Literal&) {}
+ virtual void operator()(Instruction&) { solAssert(false, ""); }
+ virtual void operator()(Identifier&) {}
+ virtual void operator()(FunctionalInstruction& _instr);
+ virtual void operator()(FunctionCall& _funCall);
+ virtual void operator()(ExpressionStatement& _statement);
+ virtual void operator()(Label&) { solAssert(false, ""); }
+ virtual void operator()(StackAssignment&) { solAssert(false, ""); }
+ virtual void operator()(Assignment& _assignment);
+ virtual void operator()(VariableDeclaration& _varDecl);
+ virtual void operator()(If& _if);
+ virtual void operator()(Switch& _switch);
+ virtual void operator()(FunctionDefinition&);
+ virtual void operator()(ForLoop&);
+ virtual void operator()(Block& _block);
+
+ virtual void visit(Statement& _st)
+ {
+ boost::apply_visitor(*this, _st);
+ }
+ virtual void visit(Expression& _e)
+ {
+ boost::apply_visitor(*this, _e);
+ }
+
+protected:
+ template <class T>
+ void walkVector(T&& _statements)
+ {
+ for (auto& st: _statements)
+ visit(st);
+ }
+};
+
+}
+}
diff --git a/libjulia/optimiser/Disambiguator.cpp b/libjulia/optimiser/Disambiguator.cpp
new file mode 100644
index 00000000..df2984e5
--- /dev/null
+++ b/libjulia/optimiser/Disambiguator.cpp
@@ -0,0 +1,85 @@
+/*
+ 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 makes all identifiers unique.
+ */
+
+#include <libjulia/optimiser/Disambiguator.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+#include <libsolidity/inlineasm/AsmScope.h>
+
+#include <libsolidity/interface/Exceptions.h>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+using namespace dev::solidity;
+
+using Scope = dev::solidity::assembly::Scope;
+
+string Disambiguator::translateIdentifier(string const& _originalName)
+{
+ solAssert(!m_scopes.empty() && m_scopes.back(), "");
+ Scope::Identifier const* id = m_scopes.back()->lookup(_originalName);
+ solAssert(id, "");
+ if (!m_translations.count(id))
+ {
+ string translated = _originalName;
+ size_t suffix = 0;
+ while (m_usedNames.count(translated))
+ {
+ suffix++;
+ translated = _originalName + "_" + std::to_string(suffix);
+ }
+ m_usedNames.insert(translated);
+ m_translations[id] = translated;
+ }
+ return m_translations.at(id);
+}
+
+void Disambiguator::enterScope(Block const& _block)
+{
+ enterScopeInternal(*m_info.scopes.at(&_block));
+}
+
+void Disambiguator::leaveScope(Block const& _block)
+{
+ leaveScopeInternal(*m_info.scopes.at(&_block));
+}
+
+void Disambiguator::enterFunction(FunctionDefinition const& _function)
+{
+ enterScopeInternal(*m_info.scopes.at(m_info.virtualBlocks.at(&_function).get()));
+}
+
+void Disambiguator::leaveFunction(FunctionDefinition const& _function)
+{
+ leaveScopeInternal(*m_info.scopes.at(m_info.virtualBlocks.at(&_function).get()));
+}
+
+void Disambiguator::enterScopeInternal(Scope& _scope)
+{
+ m_scopes.push_back(&_scope);
+}
+
+void Disambiguator::leaveScopeInternal(Scope& _scope)
+{
+ solAssert(!m_scopes.empty(), "");
+ solAssert(m_scopes.back() == &_scope, "");
+ m_scopes.pop_back();
+}
diff --git a/libjulia/optimiser/Disambiguator.h b/libjulia/optimiser/Disambiguator.h
new file mode 100644
index 00000000..18ffd157
--- /dev/null
+++ b/libjulia/optimiser/Disambiguator.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/>.
+*/
+/**
+ * Optimiser component that makes all identifiers unique.
+ */
+
+#pragma once
+
+#include <libjulia/ASTDataForward.h>
+
+#include <libjulia/optimiser/ASTCopier.h>
+
+#include <libsolidity/inlineasm/AsmAnalysisInfo.h>
+
+#include <boost/variant.hpp>
+#include <boost/optional.hpp>
+
+#include <set>
+
+namespace dev
+{
+namespace julia
+{
+
+/**
+ * Creates a copy of a iulia AST replacing all identifiers by unique names.
+ */
+class Disambiguator: public ASTCopier
+{
+public:
+ Disambiguator(solidity::assembly::AsmAnalysisInfo const& _analysisInfo):
+ m_info(_analysisInfo)
+ {}
+
+protected:
+ virtual void enterScope(Block const& _block) override;
+ virtual void leaveScope(Block const& _block) override;
+ virtual void enterFunction(FunctionDefinition const& _function) override;
+ virtual void leaveFunction(FunctionDefinition const& _function) override;
+ virtual std::string translateIdentifier(std::string const& _name) override;
+
+ void enterScopeInternal(solidity::assembly::Scope& _scope);
+ void leaveScopeInternal(solidity::assembly::Scope& _scope);
+
+ solidity::assembly::AsmAnalysisInfo const& m_info;
+
+ std::vector<solidity::assembly::Scope*> m_scopes;
+ std::map<void const*, std::string> m_translations;
+ std::set<std::string> m_usedNames;
+};
+
+}
+}
diff --git a/libjulia/optimiser/FunctionGrouper.cpp b/libjulia/optimiser/FunctionGrouper.cpp
new file mode 100644
index 00000000..cc40bc46
--- /dev/null
+++ b/libjulia/optimiser/FunctionGrouper.cpp
@@ -0,0 +1,49 @@
+/*
+ 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 changes the code of a block so that all non-function definition
+ * statements are moved to a block of their own followed by all function definitions.
+ */
+
+#include <libjulia/optimiser/FunctionGrouper.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+#include <libsolidity/interface/Exceptions.h>
+
+#include <boost/range/algorithm_ext/erase.hpp>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+using namespace dev::solidity;
+
+
+void FunctionGrouper::operator()(Block& _block)
+{
+ vector<Statement> reordered;
+ reordered.emplace_back(Block{_block.location, {}});
+
+ for (auto&& statement: _block.statements)
+ {
+ if (statement.type() == typeid(FunctionDefinition))
+ reordered.emplace_back(std::move(statement));
+ else
+ boost::get<Block>(reordered.front()).statements.emplace_back(std::move(statement));
+ }
+ _block.statements = std::move(reordered);
+}
diff --git a/libjulia/optimiser/FunctionGrouper.h b/libjulia/optimiser/FunctionGrouper.h
new file mode 100644
index 00000000..64a71318
--- /dev/null
+++ b/libjulia/optimiser/FunctionGrouper.h
@@ -0,0 +1,46 @@
+/*
+ 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 changes the code of a black so that all non-function definition
+ * instructions are moved to a block of their own followed by all function definitions.
+ */
+
+#pragma once
+
+#include <libjulia/ASTDataForward.h>
+
+namespace dev
+{
+namespace julia
+{
+
+/**
+ * Moves all instructions in a block into a new block at the start of the block, followed by
+ * all function definitions.
+ *
+ * After this step, a block is of the form
+ * { { I...} F... }
+ * Where I are (non-function-definition) instructions and F are function definitions.
+ */
+class FunctionGrouper
+{
+public:
+ void operator()(Block& _block);
+};
+
+}
+}
diff --git a/libjulia/optimiser/FunctionHoister.cpp b/libjulia/optimiser/FunctionHoister.cpp
new file mode 100644
index 00000000..9cf67f23
--- /dev/null
+++ b/libjulia/optimiser/FunctionHoister.cpp
@@ -0,0 +1,59 @@
+/*
+ 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 changes the code so that it consists of a block starting with
+ * a single block followed only by function definitions and with no functions defined
+ * anywhere else.
+ */
+
+#include <libjulia/optimiser/FunctionHoister.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+#include <libsolidity/interface/Exceptions.h>
+
+#include <libdevcore/CommonData.h>
+
+#include <boost/range/algorithm_ext/erase.hpp>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+using namespace dev::solidity;
+
+
+void FunctionHoister::operator()(Block& _block)
+{
+ bool topLevel = m_isTopLevel;
+ m_isTopLevel = false;
+ for (auto&& statement: _block.statements)
+ {
+ boost::apply_visitor(*this, statement);
+ if (statement.type() == typeid(FunctionDefinition))
+ {
+ m_functions.emplace_back(std::move(statement));
+ statement = Block{_block.location, {}};
+ }
+ }
+ auto isEmptyBlock = [](Statement const& _st) -> bool {
+ return _st.type() == typeid(Block) && boost::get<Block>(_st).statements.empty();
+ };
+ // Remove empty blocks
+ boost::range::remove_erase_if(_block.statements, isEmptyBlock);
+ if (topLevel)
+ _block.statements += std::move(m_functions);
+}
diff --git a/libjulia/optimiser/FunctionHoister.h b/libjulia/optimiser/FunctionHoister.h
new file mode 100644
index 00000000..f9f8bce0
--- /dev/null
+++ b/libjulia/optimiser/FunctionHoister.h
@@ -0,0 +1,52 @@
+/*
+ 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 changes the code so that all function definitions are at the top
+ * level block.
+ */
+
+#pragma once
+
+#include <libjulia/ASTDataForward.h>
+
+#include <libjulia/optimiser/ASTWalker.h>
+
+namespace dev
+{
+namespace julia
+{
+
+/**
+ * Moves all functions to the top-level scope.
+ * Applying this transformation to source code that has ambiguous identifiers might
+ * lead to invalid code.
+ *
+ * Prerequisites: Disambiguator
+ */
+class FunctionHoister: public ASTModifier
+{
+public:
+ using ASTModifier::operator();
+ virtual void operator()(Block& _block);
+
+private:
+ bool m_isTopLevel = true;
+ std::vector<Statement> m_functions;
+};
+
+}
+}
diff --git a/libjulia/optimiser/NameCollector.cpp b/libjulia/optimiser/NameCollector.cpp
new file mode 100644
index 00000000..7b4c4793
--- /dev/null
+++ b/libjulia/optimiser/NameCollector.cpp
@@ -0,0 +1,44 @@
+/*
+ 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/>.
+*/
+/**
+ * Specific AST walker that collects all defined names.
+ */
+
+#include <libjulia/optimiser/NameCollector.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+
+void NameCollector::operator()(VariableDeclaration const& _varDecl)
+{
+ for (auto const& var: _varDecl.variables)
+ m_names.insert(var.name);
+}
+
+void NameCollector::operator ()(FunctionDefinition const& _funDef)
+{
+ m_names.insert(_funDef.name);
+ m_functions[_funDef.name] = &_funDef;
+ for (auto const arg: _funDef.parameters)
+ m_names.insert(arg.name);
+ for (auto const ret: _funDef.returnVariables)
+ m_names.insert(ret.name);
+ ASTWalker::operator ()(_funDef);
+}
diff --git a/libjulia/optimiser/NameCollector.h b/libjulia/optimiser/NameCollector.h
new file mode 100644
index 00000000..b7e38f46
--- /dev/null
+++ b/libjulia/optimiser/NameCollector.h
@@ -0,0 +1,52 @@
+/*
+ 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/>.
+*/
+/**
+ * Specific AST walker that collects all defined names.
+ */
+
+#pragma once
+
+#include <libjulia/optimiser/ASTWalker.h>
+
+#include <string>
+#include <map>
+#include <set>
+
+namespace dev
+{
+namespace julia
+{
+
+/**
+ * Specific AST walker that collects all defined names.
+ */
+class NameCollector: public ASTWalker
+{
+public:
+ using ASTWalker::operator ();
+ virtual void operator()(VariableDeclaration const& _varDecl) override;
+ virtual void operator()(FunctionDefinition const& _funDef) override;
+
+ std::set<std::string> const& names() const { return m_names; }
+ std::map<std::string, FunctionDefinition const*> const& functions() const { return m_functions; }
+private:
+ std::set<std::string> m_names;
+ std::map<std::string, FunctionDefinition const*> m_functions;
+};
+
+}
+}
diff --git a/libjulia/optimiser/README.md b/libjulia/optimiser/README.md
new file mode 100644
index 00000000..771cb707
--- /dev/null
+++ b/libjulia/optimiser/README.md
@@ -0,0 +1,61 @@
+## IULIA Optimiser
+
+The iulia optimiser consists of several stages and components that all transform
+the AST in a semantically equivalent way. The goal is to end up either with code
+that is shorter or at least only marginally longer but will allow further
+optimisation steps.
+
+The optimiser currently follows a purely greedy strategy and does not do any
+backtracking.
+
+## Disambiguator
+
+The disambiguator takes an AST and returns a fresh copy where all identifiers have
+names unique to the input AST. This is a prerequisite for all other optimiser stages.
+One of the benefits is that identifier lookup does not need to take scopes into account
+and we can basically ignore the result of the analysis phase.
+
+All subsequent stages have the property that all names stay unique. This means if
+a new identifier needs to be introduced, a new unique name is generated.
+
+## Function Hoister
+
+The function hoister moves all function definitions to the topmost block. This is
+a semantically equivalent transformation as long as it is performed after the
+disambiguation stage. The reason is that moving a definition upwards cannot decrease
+its visibility and it is impossible to reference variables defined in a different function.
+
+The benefit of this stage is that function definitions can be lookup up more easily.
+
+## Function Grouper
+
+The function grouper has to be applied after the disambiguator and the function hoister.
+Its effect is that all topmost elements that are not function definitions are moved
+into a single block which is the first satement of the root block.
+
+After this step, a program has the following normal form:
+
+ { I F... }
+
+Where I is a block that does not contain any function definitions (not even recursively)
+and F is a list of function definitions such that no function contains a function definition.
+
+## Functional Inliner
+
+The functional inliner depends on the disambiguator, the function hoister and function grouper.
+It performs function inlining such that the result of the inlining is an expression. This can
+only be done if the body of the function to be inlined has the form ``{ r := E }`` where ``r``
+is the single return value of the function, ``E`` is an expression and all arguments in the
+function call are so-called movable expressions. A movable expression is either a literal, a
+variable or a function call (or EVM opcode) which does not have side-effects and also does not
+depend on any side-effects.
+
+As an example, neither ``mload`` nor ``mstore`` would be allowed.
+
+## Full Function Inliner
+
+## Variable Eliminator
+
+## Unused Declaration Pruner
+
+## Function Unifier
diff --git a/libjulia/optimiser/Semantics.cpp b/libjulia/optimiser/Semantics.cpp
new file mode 100644
index 00000000..92728c46
--- /dev/null
+++ b/libjulia/optimiser/Semantics.cpp
@@ -0,0 +1,60 @@
+/*(
+ 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/>.
+*/
+/**
+ * Specific AST walkers that collect semantical facts.
+ */
+
+#include <libjulia/optimiser/Semantics.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+#include <libevmasm/SemanticInformation.h>
+
+#include <libdevcore/CommonData.h>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+
+MovableChecker::MovableChecker(Expression const& _expression)
+{
+ visit(_expression);
+}
+
+void MovableChecker::operator()(Identifier const& _identifier)
+{
+ ASTWalker::operator()(_identifier);
+ m_variableReferences.insert(_identifier.name);
+}
+
+void MovableChecker::operator()(FunctionalInstruction const& _instr)
+{
+ if (!eth::SemanticInformation::movable(_instr.instruction))
+ m_movable = false;
+ else
+ ASTWalker::operator()(_instr);
+}
+
+void MovableChecker::operator()(FunctionCall const&)
+{
+ m_movable = false;
+}
+
+void MovableChecker::visit(Statement const&)
+{
+ solAssert(false, "Movability for statement requested.");
+}
diff --git a/libjulia/optimiser/Semantics.h b/libjulia/optimiser/Semantics.h
new file mode 100644
index 00000000..6df5f01a
--- /dev/null
+++ b/libjulia/optimiser/Semantics.h
@@ -0,0 +1,62 @@
+/*
+ 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/>.
+*/
+/**
+ * Specific AST walkers that collect semantical facts.
+ */
+
+#pragma once
+
+#include <libjulia/optimiser/ASTWalker.h>
+
+#include <string>
+#include <map>
+#include <set>
+
+namespace dev
+{
+namespace julia
+{
+
+/**
+ * Specific AST walker that determines whether an expression is movable.
+ */
+class MovableChecker: public ASTWalker
+{
+public:
+ MovableChecker() = default;
+ explicit MovableChecker(Expression const& _expression);
+
+ virtual void operator()(Identifier const& _identifier) override;
+ virtual void operator()(FunctionalInstruction const& _functionalInstruction) override;
+ virtual void operator()(FunctionCall const& _functionCall) override;
+
+ /// Disallow visiting anything apart from Expressions (this throws).
+ virtual void visit(Statement const&) override;
+ using ASTWalker::visit;
+
+ bool movable() const { return m_movable; }
+ std::set<std::string> const& referencedVariables() const { return m_variableReferences; }
+
+private:
+ /// Which variables the current expression references.
+ std::set<std::string> m_variableReferences;
+ /// Is the current expression movable or not.
+ bool m_movable = true;
+};
+
+}
+}
diff --git a/libjulia/optimiser/Substitution.cpp b/libjulia/optimiser/Substitution.cpp
new file mode 100644
index 00000000..668b6cb6
--- /dev/null
+++ b/libjulia/optimiser/Substitution.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/>.
+*/
+/**
+ * Specific AST copier that replaces certain identifiers with expressions.
+ */
+
+#include <libjulia/optimiser/Substitution.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+
+Expression Substitution::translate(Expression const& _expression)
+{
+ if (_expression.type() == typeid(Identifier))
+ {
+ string const& name = boost::get<Identifier>(_expression).name;
+ if (m_substitutions.count(name))
+ // No recursive substitution
+ return ASTCopier().translate(*m_substitutions.at(name));
+ }
+ return ASTCopier::translate(_expression);
+}
diff --git a/libjulia/optimiser/Substitution.h b/libjulia/optimiser/Substitution.h
new file mode 100644
index 00000000..313a08d7
--- /dev/null
+++ b/libjulia/optimiser/Substitution.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/>.
+*/
+/**
+ * Specific AST copier that replaces certain identifiers with expressions.
+ */
+
+#pragma once
+
+#include <libjulia/optimiser/ASTCopier.h>
+
+#include <string>
+#include <map>
+#include <set>
+
+namespace dev
+{
+namespace julia
+{
+
+/**
+ * Specific AST copier that replaces certain identifiers with expressions.
+ */
+class Substitution: public ASTCopier
+{
+public:
+ Substitution(std::map<std::string, Expression const*> const& _substitutions):
+ m_substitutions(_substitutions)
+ {}
+ virtual Expression translate(Expression const& _expression) override;
+
+private:
+ std::map<std::string, Expression const*> const& m_substitutions;
+};
+
+}
+}