Renaming libjulia to libyul

56 files changed, 5418 insertions, 0 deletions

diff --git a/libyul/ASTDataForward.h b/libyul/ASTDataForward.h
new file mode 100644
index 00000000..143b9c46
--- /dev/null
+++ b/libyul/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/libyul/Exceptions.h b/libyul/Exceptions.h
new file mode 100644
index 00000000..48624a56
--- /dev/null
+++ b/libyul/Exceptions.h
@@ -0,0 +1,35 @@
+/*
+	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/>.
+*/
+/**
+ * Exceptions in Yul.
+ */
+
+#pragma once
+
+#include <libdevcore/Exceptions.h>
+#include <libdevcore/Assertions.h>
+
+namespace dev
+{
+namespace julia
+{
+
+struct YulException: virtual Exception {};
+struct OptimizerException: virtual YulException {};
+
+}
+}
diff --git a/libyul/backends/evm/AbstractAssembly.h b/libyul/backends/evm/AbstractAssembly.h
new file mode 100644
index 00000000..b6818923
--- /dev/null
+++ b/libyul/backends/evm/AbstractAssembly.h
@@ -0,0 +1,119 @@
+/*
+	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
+ * Abstract assembly interface, subclasses of which are to be used with the generic
+ * bytecode generator.
+ */
+
+#pragma once
+
+#include <libdevcore/CommonData.h>
+
+#include <functional>
+
+namespace dev
+{
+struct SourceLocation;
+namespace solidity
+{
+enum class Instruction: uint8_t;
+namespace assembly
+{
+struct Instruction;
+struct Identifier;
+}
+}
+namespace julia
+{
+
+///
+/// Assembly class that abstracts both the libevmasm assembly and the new Yul assembly.
+///
+class AbstractAssembly
+{
+public:
+	using LabelID = size_t;
+
+	virtual ~AbstractAssembly() {}
+
+	/// Set a new source location valid starting from the next instruction.
+	virtual void setSourceLocation(SourceLocation const& _location) = 0;
+	/// Retrieve the current height of the stack. This does not have to be zero
+	/// at the beginning.
+	virtual int stackHeight() const = 0;
+	/// Append an EVM instruction.
+	virtual void appendInstruction(solidity::Instruction _instruction) = 0;
+	/// Append a constant.
+	virtual void appendConstant(u256 const& _constant) = 0;
+	/// Append a label.
+	virtual void appendLabel(LabelID _labelId) = 0;
+	/// Append a label reference.
+	virtual void appendLabelReference(LabelID _labelId) = 0;
+	/// Generate a new unique label.
+	virtual LabelID newLabelId() = 0;
+	/// Returns a label identified by the given name. Creates it if it does not yet exist.
+	virtual LabelID namedLabel(std::string const& _name) = 0;
+	/// Append a reference to a to-be-linked symbol.
+	/// Currently, we assume that the value is always a 20 byte number.
+	virtual void appendLinkerSymbol(std::string const& _name) = 0;
+
+	/// Append a jump instruction.
+	/// @param _stackDiffAfter the stack adjustment after this instruction.
+	/// This is helpful to stack height analysis if there is no continuing control flow.
+	virtual void appendJump(int _stackDiffAfter) = 0;
+
+	/// Append a jump-to-immediate operation.
+	/// @param _stackDiffAfter the stack adjustment after this instruction.
+	virtual void appendJumpTo(LabelID _labelId, int _stackDiffAfter = 0) = 0;
+	/// Append a jump-to-if-immediate operation.
+	virtual void appendJumpToIf(LabelID _labelId) = 0;
+	/// Start a subroutine identified by @a _labelId that takes @a _arguments
+	/// stack slots as arguments.
+	virtual void appendBeginsub(LabelID _labelId, int _arguments) = 0;
+	/// Call a subroutine identified by @a _labelId, taking @a _arguments from the
+	/// stack upon call and putting @a _returns arguments onto the stack upon return.
+	virtual void appendJumpsub(LabelID _labelId, int _arguments, int _returns) = 0;
+	/// Return from a subroutine.
+	/// @param _stackDiffAfter the stack adjustment after this instruction.
+	virtual void appendReturnsub(int _returns, int _stackDiffAfter = 0) = 0;
+
+	/// Append the assembled size as a constant.
+	virtual void appendAssemblySize() = 0;
+};
+
+enum class IdentifierContext { LValue, RValue };
+
+/// Object that is used to resolve references and generate code for access to identifiers external
+/// to inline assembly (not used in standalone assembly mode).
+struct ExternalIdentifierAccess
+{
+	using Resolver = std::function<size_t(solidity::assembly::Identifier const&, IdentifierContext, bool /*_crossesFunctionBoundary*/)>;
+	/// Resolve an external reference given by the identifier in the given context.
+	/// @returns the size of the value (number of stack slots) or size_t(-1) if not found.
+	Resolver resolve;
+	using CodeGenerator = std::function<void(solidity::assembly::Identifier const&, IdentifierContext, julia::AbstractAssembly&)>;
+	/// Generate code for retrieving the value (rvalue context) or storing the value (lvalue context)
+	/// of an identifier. The code should be appended to the assembly. In rvalue context, the value is supposed
+	/// to be put onto the stack, in lvalue context, the value is assumed to be at the top of the stack.
+	CodeGenerator generateCode;
+};
+
+
+
+}
+}
diff --git a/libyul/backends/evm/EVMAssembly.cpp b/libyul/backends/evm/EVMAssembly.cpp
new file mode 100644
index 00000000..af0ddbb8
--- /dev/null
+++ b/libyul/backends/evm/EVMAssembly.cpp
@@ -0,0 +1,202 @@
+/*
+	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/>.
+*/
+/**
+ * Assembly interface for EVM and EVM1.5.
+ */
+
+#include <libyul/backends/evm/EVMAssembly.h>
+
+#include <libevmasm/Instruction.h>
+
+#include <libsolidity/interface/Exceptions.h>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+
+namespace
+{
+/// Size of labels in bytes. Four-byte labels are required by some EVM1.5 instructions.
+size_t constexpr labelReferenceSize = 4;
+
+size_t constexpr assemblySizeReferenceSize = 4;
+}
+
+
+void EVMAssembly::setSourceLocation(SourceLocation const&)
+{
+	// Ignored for now;
+}
+
+void EVMAssembly::appendInstruction(solidity::Instruction _instr)
+{
+	m_bytecode.push_back(byte(_instr));
+	m_stackHeight += solidity::instructionInfo(_instr).ret - solidity::instructionInfo(_instr).args;
+}
+
+void EVMAssembly::appendConstant(u256 const& _constant)
+{
+	bytes data = toCompactBigEndian(_constant, 1);
+	appendInstruction(solidity::pushInstruction(data.size()));
+	m_bytecode += data;
+}
+
+void EVMAssembly::appendLabel(LabelID _labelId)
+{
+	setLabelToCurrentPosition(_labelId);
+	appendInstruction(solidity::Instruction::JUMPDEST);
+}
+
+void EVMAssembly::appendLabelReference(LabelID _labelId)
+{
+	solAssert(!m_evm15, "Cannot use plain label references in EMV1.5 mode.");
+	// @TODO we now always use labelReferenceSize for all labels, it could be shortened
+	// for some of them.
+	appendInstruction(solidity::pushInstruction(labelReferenceSize));
+	m_labelReferences[m_bytecode.size()] = _labelId;
+	m_bytecode += bytes(labelReferenceSize);
+}
+
+EVMAssembly::LabelID EVMAssembly::newLabelId()
+{
+	m_labelPositions[m_nextLabelId] = size_t(-1);
+	return m_nextLabelId++;
+}
+
+AbstractAssembly::LabelID EVMAssembly::namedLabel(string const& _name)
+{
+	solAssert(!_name.empty(), "");
+	if (!m_namedLabels.count(_name))
+		m_namedLabels[_name] = newLabelId();
+	return m_namedLabels[_name];
+}
+
+void EVMAssembly::appendLinkerSymbol(string const&)
+{
+	solAssert(false, "Linker symbols not yet implemented.");
+}
+
+void EVMAssembly::appendJump(int _stackDiffAfter)
+{
+	solAssert(!m_evm15, "Plain JUMP used for EVM 1.5");
+	appendInstruction(solidity::Instruction::JUMP);
+	m_stackHeight += _stackDiffAfter;
+}
+
+void EVMAssembly::appendJumpTo(LabelID _labelId, int _stackDiffAfter)
+{
+	if (m_evm15)
+	{
+		m_bytecode.push_back(byte(solidity::Instruction::JUMPTO));
+		appendLabelReferenceInternal(_labelId);
+		m_stackHeight += _stackDiffAfter;
+	}
+	else
+	{
+		appendLabelReference(_labelId);
+		appendJump(_stackDiffAfter);
+	}
+}
+
+void EVMAssembly::appendJumpToIf(LabelID _labelId)
+{
+	if (m_evm15)
+	{
+		m_bytecode.push_back(byte(solidity::Instruction::JUMPIF));
+		appendLabelReferenceInternal(_labelId);
+		m_stackHeight--;
+	}
+	else
+	{
+		appendLabelReference(_labelId);
+		appendInstruction(solidity::Instruction::JUMPI);
+	}
+}
+
+void EVMAssembly::appendBeginsub(LabelID _labelId, int _arguments)
+{
+	solAssert(m_evm15, "BEGINSUB used for EVM 1.0");
+	solAssert(_arguments >= 0, "");
+	setLabelToCurrentPosition(_labelId);
+	m_bytecode.push_back(byte(solidity::Instruction::BEGINSUB));
+	m_stackHeight += _arguments;
+}
+
+void EVMAssembly::appendJumpsub(LabelID _labelId, int _arguments, int _returns)
+{
+	solAssert(m_evm15, "JUMPSUB used for EVM 1.0");
+	solAssert(_arguments >= 0 && _returns >= 0, "");
+	m_bytecode.push_back(byte(solidity::Instruction::JUMPSUB));
+	appendLabelReferenceInternal(_labelId);
+	m_stackHeight += _returns - _arguments;
+}
+
+void EVMAssembly::appendReturnsub(int _returns, int _stackDiffAfter)
+{
+	solAssert(m_evm15, "RETURNSUB used for EVM 1.0");
+	solAssert(_returns >= 0, "");
+	m_bytecode.push_back(byte(solidity::Instruction::RETURNSUB));
+	m_stackHeight += _stackDiffAfter - _returns;
+}
+
+eth::LinkerObject EVMAssembly::finalize()
+{
+	size_t bytecodeSize = m_bytecode.size();
+	for (auto const& ref: m_assemblySizePositions)
+		updateReference(ref, assemblySizeReferenceSize, u256(bytecodeSize));
+
+	for (auto const& ref: m_labelReferences)
+	{
+		size_t referencePos = ref.first;
+		solAssert(m_labelPositions.count(ref.second), "");
+		size_t labelPos = m_labelPositions.at(ref.second);
+		solAssert(labelPos != size_t(-1), "Undefined but allocated label used.");
+		updateReference(referencePos, labelReferenceSize, u256(labelPos));
+	}
+
+	eth::LinkerObject obj;
+	obj.bytecode = m_bytecode;
+	return obj;
+}
+
+void EVMAssembly::setLabelToCurrentPosition(LabelID _labelId)
+{
+	solAssert(m_labelPositions.count(_labelId), "Label not found.");
+	solAssert(m_labelPositions[_labelId] == size_t(-1), "Label already set.");
+	m_labelPositions[_labelId] = m_bytecode.size();
+}
+
+void EVMAssembly::appendLabelReferenceInternal(LabelID _labelId)
+{
+	m_labelReferences[m_bytecode.size()] = _labelId;
+	m_bytecode += bytes(labelReferenceSize);
+}
+
+void EVMAssembly::appendAssemblySize()
+{
+	appendInstruction(solidity::pushInstruction(assemblySizeReferenceSize));
+	m_assemblySizePositions.push_back(m_bytecode.size());
+	m_bytecode += bytes(assemblySizeReferenceSize);
+}
+
+void EVMAssembly::updateReference(size_t pos, size_t size, u256 value)
+{
+	solAssert(m_bytecode.size() >= size && pos <= m_bytecode.size() - size, "");
+	solAssert(value < (u256(1) << (8 * size)), "");
+	for (size_t i = 0; i < size; i++)
+		m_bytecode[pos + i] = byte((value >> (8 * (size - i - 1))) & 0xff);
+}
diff --git a/libyul/backends/evm/EVMAssembly.h b/libyul/backends/evm/EVMAssembly.h
new file mode 100644
index 00000000..30abad97
--- /dev/null
+++ b/libyul/backends/evm/EVMAssembly.h
@@ -0,0 +1,97 @@
+/*
+	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/>.
+*/
+/**
+ * Assembly interface for EVM and EVM1.5.
+ */
+
+#pragma once
+
+#include <libyul/backends/evm/AbstractAssembly.h>
+
+#include <libevmasm/LinkerObject.h>
+
+#include <map>
+
+namespace dev
+{
+namespace julia
+{
+
+class EVMAssembly: public AbstractAssembly
+{
+public:
+	explicit EVMAssembly(bool _evm15 = false): m_evm15(_evm15) { }
+	virtual ~EVMAssembly() {}
+
+	/// Set a new source location valid starting from the next instruction.
+	virtual void setSourceLocation(SourceLocation const& _location) override;
+	/// Retrieve the current height of the stack. This does not have to be zero
+	/// at the beginning.
+	virtual int stackHeight() const override { return m_stackHeight; }
+	/// Append an EVM instruction.
+	virtual void appendInstruction(solidity::Instruction _instruction) override;
+	/// Append a constant.
+	virtual void appendConstant(u256 const& _constant) override;
+	/// Append a label.
+	virtual void appendLabel(LabelID _labelId) override;
+	/// Append a label reference.
+	virtual void appendLabelReference(LabelID _labelId) override;
+	/// Generate a new unique label.
+	virtual LabelID newLabelId() override;
+	/// Returns a label identified by the given name. Creates it if it does not yet exist.
+	virtual LabelID namedLabel(std::string const& _name) override;
+	/// Append a reference to a to-be-linked symbol.
+	/// Currently, we assume that the value is always a 20 byte number.
+	virtual void appendLinkerSymbol(std::string const& _name) override;
+
+	/// Append a jump instruction.
+	/// @param _stackDiffAfter the stack adjustment after this instruction.
+	virtual void appendJump(int _stackDiffAfter) override;
+	/// Append a jump-to-immediate operation.
+	virtual void appendJumpTo(LabelID _labelId, int _stackDiffAfter) override;
+	/// Append a jump-to-if-immediate operation.
+	virtual void appendJumpToIf(LabelID _labelId) override;
+	/// Start a subroutine.
+	virtual void appendBeginsub(LabelID _labelId, int _arguments) override;
+	/// Call a subroutine.
+	virtual void appendJumpsub(LabelID _labelId, int _arguments, int _returns) override;
+	/// Return from a subroutine.
+	virtual void appendReturnsub(int _returns, int _stackDiffAfter) override;
+
+	/// Append the assembled size as a constant.
+	virtual void appendAssemblySize() override;
+
+	/// Resolves references inside the bytecode and returns the linker object.
+	eth::LinkerObject finalize();
+
+private:
+	void setLabelToCurrentPosition(AbstractAssembly::LabelID _labelId);
+	void appendLabelReferenceInternal(AbstractAssembly::LabelID _labelId);
+	void updateReference(size_t pos, size_t size, u256 value);
+
+	bool m_evm15 = false; ///< if true, switch to evm1.5 mode
+	LabelID m_nextLabelId = 0;
+	int m_stackHeight = 0;
+	bytes m_bytecode;
+	std::map<std::string, LabelID> m_namedLabels;
+	std::map<LabelID, size_t> m_labelPositions;
+	std::map<size_t, LabelID> m_labelReferences;
+	std::vector<size_t> m_assemblySizePositions;
+};
+
+}
+}
diff --git a/libyul/backends/evm/EVMCodeTransform.cpp b/libyul/backends/evm/EVMCodeTransform.cpp
new file mode 100644
index 00000000..afc9e608
--- /dev/null
+++ b/libyul/backends/evm/EVMCodeTransform.cpp
@@ -0,0 +1,557 @@
+/*
+	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/>.
+*/
+/**
+ * Common code generator for translating Yul / inline assembly to EVM and EVM1.5.
+ */
+
+#include <libyul/backends/evm/EVMCodeTransform.h>
+
+#include <libsolidity/inlineasm/AsmAnalysisInfo.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;
+
+using Scope = dev::solidity::assembly::Scope;
+
+void CodeTransform::operator()(VariableDeclaration const& _varDecl)
+{
+	solAssert(m_scope, "");
+
+	int const numVariables = _varDecl.variables.size();
+	int height = m_assembly.stackHeight();
+	if (_varDecl.value)
+	{
+		boost::apply_visitor(*this, *_varDecl.value);
+		expectDeposit(numVariables, height);
+	}
+	else
+	{
+		int variablesLeft = numVariables;
+		while (variablesLeft--)
+			m_assembly.appendConstant(u256(0));
+	}
+	for (auto const& variable: _varDecl.variables)
+	{
+		auto& var = boost::get<Scope::Variable>(m_scope->identifiers.at(variable.name));
+		m_context->variableStackHeights[&var] = height++;
+	}
+	checkStackHeight(&_varDecl);
+}
+
+void CodeTransform::operator()(Assignment const& _assignment)
+{
+	int height = m_assembly.stackHeight();
+	boost::apply_visitor(*this, *_assignment.value);
+	expectDeposit(_assignment.variableNames.size(), height);
+
+	m_assembly.setSourceLocation(_assignment.location);
+	generateMultiAssignment(_assignment.variableNames);
+	checkStackHeight(&_assignment);
+}
+
+void CodeTransform::operator()(StackAssignment const& _assignment)
+{
+	m_assembly.setSourceLocation(_assignment.location);
+	generateAssignment(_assignment.variableName);
+	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);
+	solAssert(m_scope, "");
+	solAssert(m_scope->identifiers.count(_label.name), "");
+	Scope::Label& label = boost::get<Scope::Label>(m_scope->identifiers.at(_label.name));
+	m_assembly.appendLabel(labelID(label));
+	checkStackHeight(&_label);
+}
+
+void CodeTransform::operator()(FunctionCall const& _call)
+{
+	solAssert(m_scope, "");
+
+	m_assembly.setSourceLocation(_call.location);
+	EVMAssembly::LabelID returnLabel(-1); // only used for evm 1.0
+	if (!m_evm15)
+	{
+		returnLabel = m_assembly.newLabelId();
+		m_assembly.appendLabelReference(returnLabel);
+		m_stackAdjustment++;
+	}
+
+	Scope::Function* function = nullptr;
+	solAssert(m_scope->lookup(_call.functionName.name, Scope::NonconstVisitor(
+		[=](Scope::Variable&) { solAssert(false, "Expected function name."); },
+		[=](Scope::Label&) { solAssert(false, "Expected function name."); },
+		[&](Scope::Function& _function) { function = &_function; }
+	)), "Function name not found.");
+	solAssert(function, "");
+	solAssert(function->arguments.size() == _call.arguments.size(), "");
+	for (auto const& arg: _call.arguments | boost::adaptors::reversed)
+		visitExpression(arg);
+	m_assembly.setSourceLocation(_call.location);
+	if (m_evm15)
+		m_assembly.appendJumpsub(functionEntryID(_call.functionName.name, *function), function->arguments.size(), function->returns.size());
+	else
+	{
+		m_assembly.appendJumpTo(functionEntryID(_call.functionName.name, *function), function->returns.size() - function->arguments.size() - 1);
+		m_assembly.appendLabel(returnLabel);
+		m_stackAdjustment--;
+	}
+	checkStackHeight(&_call);
+}
+
+void CodeTransform::operator()(FunctionalInstruction const& _instruction)
+{
+	if (m_evm15 && (
+		_instruction.instruction == solidity::Instruction::JUMP ||
+		_instruction.instruction == solidity::Instruction::JUMPI
+	))
+	{
+		bool const isJumpI = _instruction.instruction == solidity::Instruction::JUMPI;
+		if (isJumpI)
+		{
+			solAssert(_instruction.arguments.size() == 2, "");
+			visitExpression(_instruction.arguments.at(1));
+		}
+		else
+		{
+			solAssert(_instruction.arguments.size() == 1, "");
+		}
+		m_assembly.setSourceLocation(_instruction.location);
+		auto label = labelFromIdentifier(boost::get<assembly::Identifier>(_instruction.arguments.at(0)));
+		if (isJumpI)
+			m_assembly.appendJumpToIf(label);
+		else
+			m_assembly.appendJumpTo(label);
+	}
+	else
+	{
+		for (auto const& arg: _instruction.arguments | boost::adaptors::reversed)
+			visitExpression(arg);
+		m_assembly.setSourceLocation(_instruction.location);
+		m_assembly.appendInstruction(_instruction.instruction);
+	}
+	checkStackHeight(&_instruction);
+}
+
+void CodeTransform::operator()(assembly::Identifier const& _identifier)
+{
+	m_assembly.setSourceLocation(_identifier.location);
+	// First search internals, then externals.
+	solAssert(m_scope, "");
+	if (m_scope->lookup(_identifier.name, Scope::NonconstVisitor(
+		[=](Scope::Variable& _var)
+		{
+			if (int heightDiff = variableHeightDiff(_var, false))
+				m_assembly.appendInstruction(solidity::dupInstruction(heightDiff));
+			else
+				// Store something to balance the stack
+				m_assembly.appendConstant(u256(0));
+		},
+		[=](Scope::Label& _label)
+		{
+			m_assembly.appendLabelReference(labelID(_label));
+		},
+		[=](Scope::Function&)
+		{
+			solAssert(false, "Function not removed during desugaring.");
+		}
+	)))
+	{
+		return;
+	}
+	solAssert(
+		m_identifierAccess.generateCode,
+		"Identifier not found and no external access available."
+	);
+	m_identifierAccess.generateCode(_identifier, IdentifierContext::RValue, m_assembly);
+	checkStackHeight(&_identifier);
+}
+
+void CodeTransform::operator()(assembly::Literal const& _literal)
+{
+	m_assembly.setSourceLocation(_literal.location);
+	if (_literal.kind == assembly::LiteralKind::Number)
+		m_assembly.appendConstant(u256(_literal.value));
+	else if (_literal.kind == assembly::LiteralKind::Boolean)
+	{
+		if (_literal.value == "true")
+			m_assembly.appendConstant(u256(1));
+		else
+			m_assembly.appendConstant(u256(0));
+	}
+	else
+	{
+		solAssert(_literal.value.size() <= 32, "");
+		m_assembly.appendConstant(u256(h256(_literal.value, h256::FromBinary, h256::AlignLeft)));
+	}
+	checkStackHeight(&_literal);
+}
+
+void CodeTransform::operator()(assembly::Instruction const& _instruction)
+{
+	solAssert(!m_evm15 || _instruction.instruction != solidity::Instruction::JUMP, "Bare JUMP instruction used for EVM1.5");
+	solAssert(!m_evm15 || _instruction.instruction != solidity::Instruction::JUMPI, "Bare JUMPI instruction used for EVM1.5");
+	m_assembly.setSourceLocation(_instruction.location);
+	m_assembly.appendInstruction(_instruction.instruction);
+	checkStackHeight(&_instruction);
+}
+
+void CodeTransform::operator()(If const& _if)
+{
+	visitExpression(*_if.condition);
+	m_assembly.setSourceLocation(_if.location);
+	m_assembly.appendInstruction(solidity::Instruction::ISZERO);
+	AbstractAssembly::LabelID end = m_assembly.newLabelId();
+	m_assembly.appendJumpToIf(end);
+	(*this)(_if.body);
+	m_assembly.setSourceLocation(_if.location);
+	m_assembly.appendLabel(end);
+	checkStackHeight(&_if);
+}
+
+void CodeTransform::operator()(Switch const& _switch)
+{
+	//@TODO use JUMPV in EVM1.5?
+
+	visitExpression(*_switch.expression);
+	int expressionHeight = m_assembly.stackHeight();
+	map<Case const*, AbstractAssembly::LabelID> caseBodies;
+	AbstractAssembly::LabelID end = m_assembly.newLabelId();
+	for (Case const& c: _switch.cases)
+	{
+		if (c.value)
+		{
+			(*this)(*c.value);
+			m_assembly.setSourceLocation(c.location);
+			AbstractAssembly::LabelID bodyLabel = m_assembly.newLabelId();
+			caseBodies[&c] = bodyLabel;
+			solAssert(m_assembly.stackHeight() == expressionHeight + 1, "");
+			m_assembly.appendInstruction(solidity::dupInstruction(2));
+			m_assembly.appendInstruction(solidity::Instruction::EQ);
+			m_assembly.appendJumpToIf(bodyLabel);
+		}
+		else
+			// default case
+			(*this)(c.body);
+	}
+	m_assembly.setSourceLocation(_switch.location);
+	m_assembly.appendJumpTo(end);
+
+	size_t numCases = caseBodies.size();
+	for (auto const& c: caseBodies)
+	{
+		m_assembly.setSourceLocation(c.first->location);
+		m_assembly.appendLabel(c.second);
+		(*this)(c.first->body);
+		// Avoid useless "jump to next" for the last case.
+		if (--numCases > 0)
+		{
+			m_assembly.setSourceLocation(c.first->location);
+			m_assembly.appendJumpTo(end);
+		}
+	}
+
+	m_assembly.setSourceLocation(_switch.location);
+	m_assembly.appendLabel(end);
+	m_assembly.appendInstruction(solidity::Instruction::POP);
+	checkStackHeight(&_switch);
+}
+
+void CodeTransform::operator()(FunctionDefinition const& _function)
+{
+	solAssert(m_scope, "");
+	solAssert(m_scope->identifiers.count(_function.name), "");
+	Scope::Function& function = boost::get<Scope::Function>(m_scope->identifiers.at(_function.name));
+
+	int const localStackAdjustment = m_evm15 ? 0 : 1;
+	int height = localStackAdjustment;
+	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.parameters | boost::adaptors::reversed)
+	{
+		auto& var = boost::get<Scope::Variable>(varScope->identifiers.at(v.name));
+		m_context->variableStackHeights[&var] = height++;
+	}
+
+	m_assembly.setSourceLocation(_function.location);
+	int stackHeightBefore = m_assembly.stackHeight();
+	AbstractAssembly::LabelID afterFunction = m_assembly.newLabelId();
+
+	if (m_evm15)
+	{
+		m_assembly.appendJumpTo(afterFunction, -stackHeightBefore);
+		m_assembly.appendBeginsub(functionEntryID(_function.name, function), _function.parameters.size());
+	}
+	else
+	{
+		m_assembly.appendJumpTo(afterFunction, -stackHeightBefore + height);
+		m_assembly.appendLabel(functionEntryID(_function.name, function));
+	}
+	m_stackAdjustment += localStackAdjustment;
+
+	for (auto const& v: _function.returnVariables)
+	{
+		auto& var = boost::get<Scope::Variable>(varScope->identifiers.at(v.name));
+		m_context->variableStackHeights[&var] = height++;
+		// Preset stack slots for return variables to zero.
+		m_assembly.appendConstant(u256(0));
+	}
+
+	CodeTransform(
+		m_assembly,
+		m_info,
+		m_yul,
+		m_evm15,
+		m_identifierAccess,
+		m_useNamedLabelsForFunctions,
+		localStackAdjustment,
+		m_context
+	)(_function.body);
+
+	{
+		// The stack layout here is:
+		// <return label>? <arguments...> <return values...>
+		// But we would like it to be:
+		// <return values...> <return label>?
+		// So we have to append some SWAP and POP instructions.
+
+		// This vector holds the desired target positions of all stack slots and is
+		// modified parallel to the actual stack.
+		vector<int> stackLayout;
+		if (!m_evm15)
+			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");
+		while (!stackLayout.empty() && stackLayout.back() != int(stackLayout.size() - 1))
+			if (stackLayout.back() < 0)
+			{
+				m_assembly.appendInstruction(solidity::Instruction::POP);
+				stackLayout.pop_back();
+			}
+			else
+			{
+				m_assembly.appendInstruction(swapInstruction(stackLayout.size() - stackLayout.back() - 1));
+				swap(stackLayout[stackLayout.back()], stackLayout.back());
+			}
+		for (int i = 0; size_t(i) < stackLayout.size(); ++i)
+			solAssert(i == stackLayout[i], "Error reshuffling stack.");
+	}
+
+	if (m_evm15)
+		m_assembly.appendReturnsub(_function.returnVariables.size(), stackHeightBefore);
+	else
+		m_assembly.appendJump(stackHeightBefore - _function.returnVariables.size());
+	m_stackAdjustment -= localStackAdjustment;
+	m_assembly.appendLabel(afterFunction);
+	checkStackHeight(&_function);
+}
+
+void CodeTransform::operator()(ForLoop const& _forLoop)
+{
+	Scope* originalScope = m_scope;
+	// We start with visiting the block, but not finalizing it.
+	m_scope = m_info.scopes.at(&_forLoop.pre).get();
+	int stackStartHeight = m_assembly.stackHeight();
+
+	visitStatements(_forLoop.pre.statements);
+
+	// TODO: When we implement break and continue, the labels and the stack heights at that point
+	// have to be stored in a stack.
+	AbstractAssembly::LabelID loopStart = m_assembly.newLabelId();
+	AbstractAssembly::LabelID loopEnd = m_assembly.newLabelId();
+	AbstractAssembly::LabelID postPart = m_assembly.newLabelId();
+
+	m_assembly.setSourceLocation(_forLoop.location);
+	m_assembly.appendLabel(loopStart);
+
+	visitExpression(*_forLoop.condition);
+	m_assembly.setSourceLocation(_forLoop.location);
+	m_assembly.appendInstruction(solidity::Instruction::ISZERO);
+	m_assembly.appendJumpToIf(loopEnd);
+
+	(*this)(_forLoop.body);
+
+	m_assembly.setSourceLocation(_forLoop.location);
+	m_assembly.appendLabel(postPart);
+
+	(*this)(_forLoop.post);
+
+	m_assembly.setSourceLocation(_forLoop.location);
+	m_assembly.appendJumpTo(loopStart);
+	m_assembly.appendLabel(loopEnd);
+
+	finalizeBlock(_forLoop.pre, stackStartHeight);
+	m_scope = originalScope;
+}
+
+void CodeTransform::operator()(Block const& _block)
+{
+	Scope* originalScope = m_scope;
+	m_scope = m_info.scopes.at(&_block).get();
+
+	int blockStartStackHeight = m_assembly.stackHeight();
+	visitStatements(_block.statements);
+
+	finalizeBlock(_block, blockStartStackHeight);
+	m_scope = originalScope;
+}
+
+AbstractAssembly::LabelID CodeTransform::labelFromIdentifier(Identifier const& _identifier)
+{
+	AbstractAssembly::LabelID label = AbstractAssembly::LabelID(-1);
+	if (!m_scope->lookup(_identifier.name, Scope::NonconstVisitor(
+		[=](Scope::Variable&) { solAssert(false, "Expected label"); },
+		[&](Scope::Label& _label)
+		{
+			label = labelID(_label);
+		},
+		[=](Scope::Function&) { solAssert(false, "Expected label"); }
+	)))
+	{
+		solAssert(false, "Identifier not found.");
+	}
+	return label;
+}
+
+AbstractAssembly::LabelID CodeTransform::labelID(Scope::Label const& _label)
+{
+	if (!m_context->labelIDs.count(&_label))
+		m_context->labelIDs[&_label] = m_assembly.newLabelId();
+	return m_context->labelIDs[&_label];
+}
+
+AbstractAssembly::LabelID CodeTransform::functionEntryID(string const& _name, Scope::Function const& _function)
+{
+	if (!m_context->functionEntryIDs.count(&_function))
+	{
+		AbstractAssembly::LabelID id =
+			m_useNamedLabelsForFunctions ?
+			m_assembly.namedLabel(_name) :
+			m_assembly.newLabelId();
+		m_context->functionEntryIDs[&_function] = id;
+	}
+	return m_context->functionEntryIDs[&_function];
+}
+
+void CodeTransform::visitExpression(Expression const& _expression)
+{
+	int height = m_assembly.stackHeight();
+	boost::apply_visitor(*this, _expression);
+	expectDeposit(1, height);
+}
+
+void CodeTransform::visitStatements(vector<Statement> const& _statements)
+{
+	for (auto const& statement: _statements)
+		boost::apply_visitor(*this, statement);
+}
+
+void CodeTransform::finalizeBlock(Block const& _block, int blockStartStackHeight)
+{
+	m_assembly.setSourceLocation(_block.location);
+
+	// pop variables
+	solAssert(m_info.scopes.at(&_block).get() == m_scope, "");
+	for (size_t i = 0; i < m_scope->numberOfVariables(); ++i)
+		m_assembly.appendInstruction(solidity::Instruction::POP);
+
+	int deposit = m_assembly.stackHeight() - blockStartStackHeight;
+	solAssert(deposit == 0, "Invalid stack height at end of block.");
+	checkStackHeight(&_block);
+}
+
+void CodeTransform::generateMultiAssignment(vector<Identifier> const& _variableNames)
+{
+	solAssert(m_scope, "");
+	for (auto const& variableName: _variableNames | boost::adaptors::reversed)
+		generateAssignment(variableName);
+}
+
+void CodeTransform::generateAssignment(Identifier const& _variableName)
+{
+	solAssert(m_scope, "");
+	auto var = m_scope->lookup(_variableName.name);
+	if (var)
+	{
+		Scope::Variable const& _var = boost::get<Scope::Variable>(*var);
+		if (int heightDiff = variableHeightDiff(_var, true))
+			m_assembly.appendInstruction(solidity::swapInstruction(heightDiff - 1));
+		m_assembly.appendInstruction(solidity::Instruction::POP);
+	}
+	else
+	{
+		solAssert(
+			m_identifierAccess.generateCode,
+			"Identifier not found and no external access available."
+		);
+		m_identifierAccess.generateCode(_variableName, IdentifierContext::LValue, m_assembly);
+	}
+}
+
+int CodeTransform::variableHeightDiff(solidity::assembly::Scope::Variable const& _var, bool _forSwap) const
+{
+	solAssert(m_context->variableStackHeights.count(&_var), "");
+	int heightDiff = m_assembly.stackHeight() - m_context->variableStackHeights[&_var];
+	if (heightDiff <= (_forSwap ? 1 : 0) || heightDiff > (_forSwap ? 17 : 16))
+	{
+		solUnimplemented(
+			"Variable inaccessible, too deep inside stack (" + to_string(heightDiff) + ")"
+		);
+		return 0;
+	}
+	else
+		return heightDiff;
+}
+
+void CodeTransform::expectDeposit(int _deposit, int _oldHeight) const
+{
+	solAssert(m_assembly.stackHeight() == _oldHeight + _deposit, "Invalid stack deposit.");
+}
+
+void CodeTransform::checkStackHeight(void const* _astElement) const
+{
+	solAssert(m_info.stackHeightInfo.count(_astElement), "Stack height for AST element not found.");
+	int stackHeightInAnalysis = m_info.stackHeightInfo.at(_astElement);
+	int stackHeightInCodegen = m_assembly.stackHeight() - m_stackAdjustment;
+	solAssert(
+		stackHeightInAnalysis == stackHeightInCodegen,
+		"Stack height mismatch between analysis and code generation phase: Analysis: " +
+		to_string(stackHeightInAnalysis) +
+		" code gen: " +
+		to_string(stackHeightInCodegen)
+	);
+}
diff --git a/libyul/backends/evm/EVMCodeTransform.h b/libyul/backends/evm/EVMCodeTransform.h
new file mode 100644
index 00000000..6a0941b6
--- /dev/null
+++ b/libyul/backends/evm/EVMCodeTransform.h
@@ -0,0 +1,158 @@
+/*
+	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/>.
+*/
+/**
+ * Common code generator for translating Yul / inline assembly to EVM and EVM1.5.
+ */
+
+#include <libyul/backends/evm/EVMAssembly.h>
+
+#include <libyul/ASTDataForward.h>
+
+#include <libsolidity/inlineasm/AsmScope.h>
+
+#include <boost/variant.hpp>
+#include <boost/optional.hpp>
+
+namespace dev
+{
+namespace solidity
+{
+class ErrorReporter;
+namespace assembly
+{
+struct AsmAnalysisInfo;
+}
+}
+namespace julia
+{
+class EVMAssembly;
+
+class CodeTransform: public boost::static_visitor<>
+{
+public:
+	/// Create the code transformer.
+	/// @param _identifierAccess used to resolve identifiers external to the inline assembly
+	CodeTransform(
+		julia::AbstractAssembly& _assembly,
+		solidity::assembly::AsmAnalysisInfo& _analysisInfo,
+		bool _yul = false,
+		bool _evm15 = false,
+		ExternalIdentifierAccess const& _identifierAccess = ExternalIdentifierAccess(),
+		bool _useNamedLabelsForFunctions = false
+	): CodeTransform(
+		_assembly,
+		_analysisInfo,
+		_yul,
+		_evm15,
+		_identifierAccess,
+		_useNamedLabelsForFunctions,
+		_assembly.stackHeight(),
+		std::make_shared<Context>()
+	)
+	{
+	}
+
+protected:
+	struct Context
+	{
+		using Scope = solidity::assembly::Scope;
+		std::map<Scope::Label const*, AbstractAssembly::LabelID> labelIDs;
+		std::map<Scope::Function const*, AbstractAssembly::LabelID> functionEntryIDs;
+		std::map<Scope::Variable const*, int> variableStackHeights;
+	};
+
+	CodeTransform(
+		julia::AbstractAssembly& _assembly,
+		solidity::assembly::AsmAnalysisInfo& _analysisInfo,
+		bool _yul,
+		bool _evm15,
+		ExternalIdentifierAccess const& _identifierAccess,
+		bool _useNamedLabelsForFunctions,
+		int _stackAdjustment,
+		std::shared_ptr<Context> _context
+	):
+		m_assembly(_assembly),
+		m_info(_analysisInfo),
+		m_yul(_yul),
+		m_evm15(_evm15),
+		m_useNamedLabelsForFunctions(_useNamedLabelsForFunctions),
+		m_identifierAccess(_identifierAccess),
+		m_stackAdjustment(_stackAdjustment),
+		m_context(_context)
+	{}
+
+public:
+	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(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(Expression const& _expression);
+
+	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(Block const& _block, int _blockStartStackHeight);
+
+	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
+	/// the (positive) stack height difference otherwise.
+	int variableHeightDiff(solidity::assembly::Scope::Variable const& _var, bool _forSwap) const;
+
+	void expectDeposit(int _deposit, int _oldHeight) const;
+
+	void checkStackHeight(void const* _astElement) const;
+
+	julia::AbstractAssembly& m_assembly;
+	solidity::assembly::AsmAnalysisInfo& m_info;
+	solidity::assembly::Scope* m_scope = nullptr;
+	bool m_yul = false;
+	bool m_evm15 = false;
+	bool m_useNamedLabelsForFunctions = false;
+	ExternalIdentifierAccess m_identifierAccess;
+	/// Adjustment between the stack height as determined during the analysis phase
+	/// and the stack height in the assembly. This is caused by an initial stack being present
+	/// for inline assembly and different stack heights depending on the EVM backend used
+	/// (EVM 1.0 or 1.5).
+	int m_stackAdjustment = 0;
+	std::shared_ptr<Context> m_context;
+};
+
+}
+}
diff --git a/libyul/optimiser/ASTCopier.cpp b/libyul/optimiser/ASTCopier.cpp
new file mode 100644
index 00000000..c3fe7778
--- /dev/null
+++ b/libyul/optimiser/ASTCopier.cpp
@@ -0,0 +1,184 @@
+/*
+	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 <libyul/optimiser/ASTCopier.h>
+
+#include <libyul/Exceptions.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+#include <libdevcore/Common.h>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+
+Statement ASTCopier::operator()(Instruction const&)
+{
+	assertThrow(false, OptimizerException, "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&)
+{
+	assertThrow(false, OptimizerException, "Invalid operation.");
+	return {};
+}
+
+Statement ASTCopier::operator()(Label const&)
+{
+	assertThrow(false, OptimizerException, "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/libyul/optimiser/ASTCopier.h b/libyul/optimiser/ASTCopier.h
new file mode 100644
index 00000000..ce9226a6
--- /dev/null
+++ b/libyul/optimiser/ASTCopier.h
@@ -0,0 +1,124 @@
+/*
+	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 <libyul/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 ~ExpressionCopier() = default;
+	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 ~StatementCopier() = default;
+	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 Yul AST potentially replacing identifier names.
+ * Base class to be extended.
+ */
+class ASTCopier: public ExpressionCopier, public StatementCopier
+{
+public:
+	virtual ~ASTCopier() = default;
+	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/libyul/optimiser/ASTWalker.cpp b/libyul/optimiser/ASTWalker.cpp
new file mode 100644
index 00000000..042d1f11
--- /dev/null
+++ b/libyul/optimiser/ASTWalker.cpp
@@ -0,0 +1,157 @@
+/*
+	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 <libyul/optimiser/ASTWalker.h>
+
+#include <libsolidity/inlineasm/AsmData.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.body);
+	(*this)(_for.post);
+}
+
+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/libyul/optimiser/ASTWalker.h b/libyul/optimiser/ASTWalker.h
new file mode 100644
index 00000000..b34559a3
--- /dev/null
+++ b/libyul/optimiser/ASTWalker.h
@@ -0,0 +1,122 @@
+/*
+	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 <libyul/ASTDataForward.h>
+
+#include <libyul/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 ~ASTWalker() = default;
+	virtual void operator()(Literal const&) {}
+	virtual void operator()(Instruction const&) { assertThrow(false, OptimizerException, ""); }
+	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&) { assertThrow(false, OptimizerException, ""); }
+	virtual void operator()(StackAssignment const&) { assertThrow(false, OptimizerException, ""); }
+	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& statement: _statements)
+			visit(statement);
+	}
+};
+
+/**
+ * Generic AST modifier (i.e. non-const version of ASTWalker).
+ */
+class ASTModifier: public boost::static_visitor<>
+{
+public:
+	virtual ~ASTModifier() = default;
+	virtual void operator()(Literal&) {}
+	virtual void operator()(Instruction&) { assertThrow(false, OptimizerException, ""); }
+	virtual void operator()(Identifier&) {}
+	virtual void operator()(FunctionalInstruction& _instr);
+	virtual void operator()(FunctionCall& _funCall);
+	virtual void operator()(ExpressionStatement& _statement);
+	virtual void operator()(Label&) { assertThrow(false, OptimizerException, ""); }
+	virtual void operator()(StackAssignment&) { assertThrow(false, OptimizerException, ""); }
+	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/libyul/optimiser/CommonSubexpressionEliminator.cpp b/libyul/optimiser/CommonSubexpressionEliminator.cpp
new file mode 100644
index 00000000..8bb4ca2e
--- /dev/null
+++ b/libyul/optimiser/CommonSubexpressionEliminator.cpp
@@ -0,0 +1,71 @@
+/*(
+	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/>.
+*/
+/**
+ * Optimisation stage that replaces expressions known to be the current value of a variable
+ * in scope by a reference to that variable.
+ */
+
+#include <libyul/optimiser/CommonSubexpressionEliminator.h>
+
+#include <libyul/optimiser/Metrics.h>
+#include <libyul/optimiser/SyntacticalEquality.h>
+#include <libyul/Exceptions.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+
+void CommonSubexpressionEliminator::visit(Expression& _e)
+{
+	// We visit the inner expression first to first simplify inner expressions,
+	// which hopefully allows more matches.
+	// Note that the DataFlowAnalyzer itself only has code for visiting Statements,
+	// so this basically invokes the AST walker directly and thus post-visiting
+	// is also fine with regards to data flow analysis.
+	DataFlowAnalyzer::visit(_e);
+
+	if (_e.type() == typeid(Identifier))
+	{
+		Identifier& identifier = boost::get<Identifier>(_e);
+		string const& name = identifier.name;
+		if (m_value.count(name))
+		{
+			assertThrow(m_value.at(name), OptimizerException, "");
+			if (m_value.at(name)->type() == typeid(Identifier))
+			{
+				string const& value = boost::get<Identifier>(*m_value.at(name)).name;
+				if (inScope(value))
+					_e = Identifier{locationOf(_e), value};
+			}
+		}
+	}
+	else
+	{
+		// TODO this search is rather inefficient.
+		for (auto const& var: m_value)
+		{
+			assertThrow(var.second, OptimizerException, "");
+			if (SyntacticalEqualityChecker::equal(_e, *var.second))
+			{
+				_e = Identifier{locationOf(_e), var.first};
+				break;
+			}
+		}
+	}
+}
diff --git a/libyul/optimiser/CommonSubexpressionEliminator.h b/libyul/optimiser/CommonSubexpressionEliminator.h
new file mode 100644
index 00000000..37cd80ff
--- /dev/null
+++ b/libyul/optimiser/CommonSubexpressionEliminator.h
@@ -0,0 +1,45 @@
+/*
+	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/>.
+*/
+/**
+ * Optimisation stage that replaces expressions known to be the current value of a variable
+ * in scope by a reference to that variable.
+ */
+
+#pragma once
+
+#include <libyul/optimiser/DataFlowAnalyzer.h>
+
+namespace dev
+{
+namespace julia
+{
+
+/**
+ * Optimisation stage that replaces expressions known to be the current value of a variable
+ * in scope by a reference to that variable.
+ *
+ * Prerequisite: Disambiguator
+ */
+class CommonSubexpressionEliminator: public DataFlowAnalyzer
+{
+protected:
+	using ASTModifier::visit;
+	virtual void visit(Expression& _e) override;
+};
+
+}
+}
diff --git a/libyul/optimiser/DataFlowAnalyzer.cpp b/libyul/optimiser/DataFlowAnalyzer.cpp
new file mode 100644
index 00000000..3300a2bd
--- /dev/null
+++ b/libyul/optimiser/DataFlowAnalyzer.cpp
@@ -0,0 +1,193 @@
+/*(
+	This file is part of solidity.
+
+	solidity is free software: you can redistribute it and/or modify
+	it under the terms of the GNU General Public License as published by
+	the Free Software Foundation, either version 3 of the License, or
+	(at your option) any later version.
+
+	solidity is distributed in the hope that it will be useful,
+	but WITHOUT ANY WARRANTY; without even the implied warranty of
+	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+	GNU General Public License for more details.
+
+	You should have received a copy of the GNU General Public License
+	along with solidity.  If not, see <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.
+ */
+
+#include <libyul/optimiser/DataFlowAnalyzer.h>
+
+#include <libyul/optimiser/NameCollector.h>
+#include <libyul/optimiser/Semantics.h>
+#include <libyul/Exceptions.h>
+
+#include <libsolidity/inlineasm/AsmData.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);
+	assertThrow(_assignment.value, OptimizerException, "");
+	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().variables += names;
+	if (_varDecl.value)
+		visit(*_varDecl.value);
+	handleAssignment(names, _varDecl.value.get());
+}
+
+void DataFlowAnalyzer::operator()(If& _if)
+{
+	ASTModifier::operator()(_if);
+
+	Assignments assignments;
+	assignments(_if.body);
+	clearValues(assignments.names());
+}
+
+void DataFlowAnalyzer::operator()(Switch& _switch)
+{
+	visit(*_switch.expression);
+	set<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.emplace_back(true);
+	for (auto const& parameter: _fun.parameters)
+		m_variableScopes.back().variables.insert(parameter.name);
+	for (auto const& var: _fun.returnVariables)
+		m_variableScopes.back().variables.insert(var.name);
+	ASTModifier::operator()(_fun);
+	m_variableScopes.pop_back();
+}
+
+void DataFlowAnalyzer::operator()(ForLoop& _for)
+{
+	// Special scope handling of the pre block.
+	m_variableScopes.emplace_back(false);
+	for (auto& statement: _for.pre.statements)
+		visit(statement);
+
+	Assignments assignments;
+	assignments(_for.body);
+	assignments(_for.post);
+	clearValues(assignments.names());
+
+	visit(*_for.condition);
+	(*this)(_for.body);
+	(*this)(_for.post);
+
+	clearValues(assignments.names());
+
+	m_variableScopes.pop_back();
+}
+
+void DataFlowAnalyzer::operator()(Block& _block)
+{
+	size_t numScopes = m_variableScopes.size();
+	m_variableScopes.emplace_back(false);
+	ASTModifier::operator()(_block);
+	m_variableScopes.pop_back();
+	assertThrow(numScopes == m_variableScopes.size(), OptimizerException, "");
+}
+
+void DataFlowAnalyzer::handleAssignment(set<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.
+		if (_value && movableChecker.movable() && !movableChecker.referencedVariables().count(name))
+			m_value[name] = _value;
+	}
+
+	auto const& referencedVariables = movableChecker.referencedVariables();
+	for (auto const& name: _variables)
+	{
+		m_references[name] = referencedVariables;
+		for (auto const& ref: referencedVariables)
+			m_referencedBy[ref].insert(name);
+	}
+}
+
+void DataFlowAnalyzer::clearValues(set<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.variables.count(_variableName))
+			return true;
+		if (scope.isFunction)
+			return false;
+	}
+	return false;
+}
diff --git a/libyul/optimiser/DataFlowAnalyzer.h b/libyul/optimiser/DataFlowAnalyzer.h
new file mode 100644
index 00000000..054f6bd4
--- /dev/null
+++ b/libyul/optimiser/DataFlowAnalyzer.h
@@ -0,0 +1,84 @@
+/*
+	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 <libyul/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 values 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;
+
+	struct Scope
+	{
+		explicit Scope(bool _isFunction): isFunction(_isFunction) {}
+		std::set<std::string> variables;
+		bool isFunction;
+	};
+	/// List of scopes.
+	std::vector<Scope> m_variableScopes;
+};
+
+}
+}
diff --git a/libyul/optimiser/Disambiguator.cpp b/libyul/optimiser/Disambiguator.cpp
new file mode 100644
index 00000000..87da0391
--- /dev/null
+++ b/libyul/optimiser/Disambiguator.cpp
@@ -0,0 +1,75 @@
+/*
+	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 <libyul/optimiser/Disambiguator.h>
+
+#include <libyul/Exceptions.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+#include <libsolidity/inlineasm/AsmScope.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)
+{
+	assertThrow(!m_scopes.empty() && m_scopes.back(), OptimizerException, "");
+	Scope::Identifier const* id = m_scopes.back()->lookup(_originalName);
+	assertThrow(id, OptimizerException, "");
+	if (!m_translations.count(id))
+		m_translations[id] = m_nameDispenser.newName(_originalName);
+	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)
+{
+	assertThrow(!m_scopes.empty(), OptimizerException, "");
+	assertThrow(m_scopes.back() == &_scope, OptimizerException, "");
+	m_scopes.pop_back();
+}
diff --git a/libyul/optimiser/Disambiguator.h b/libyul/optimiser/Disambiguator.h
new file mode 100644
index 00000000..f6b8fd46
--- /dev/null
+++ b/libyul/optimiser/Disambiguator.h
@@ -0,0 +1,68 @@
+/*
+	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 <libyul/ASTDataForward.h>
+
+#include <libyul/optimiser/ASTCopier.h>
+#include <libyul/optimiser/NameDispenser.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 Yul 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;
+	NameDispenser m_nameDispenser;
+};
+
+}
+}
diff --git a/libyul/optimiser/ExpressionInliner.cpp b/libyul/optimiser/ExpressionInliner.cpp
new file mode 100644
index 00000000..d4f7c4a4
--- /dev/null
+++ b/libyul/optimiser/ExpressionInliner.cpp
@@ -0,0 +1,74 @@
+/*
+	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 performs function inlining inside expressions.
+ */
+
+#include <libyul/optimiser/ExpressionInliner.h>
+
+#include <libyul/optimiser/InlinableExpressionFunctionFinder.h>
+#include <libyul/optimiser/Substitution.h>
+#include <libyul/optimiser/Semantics.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+#include <boost/algorithm/cxx11/all_of.hpp>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+using namespace dev::solidity;
+
+void ExpressionInliner::run()
+{
+	InlinableExpressionFunctionFinder funFinder;
+	funFinder(m_block);
+	m_inlinableFunctions = funFinder.inlinableFunctions();
+
+	(*this)(m_block);
+}
+
+
+void ExpressionInliner::operator()(FunctionDefinition& _fun)
+{
+	ASTModifier::operator()(_fun);
+}
+
+void ExpressionInliner::visit(Expression& _expression)
+{
+	ASTModifier::visit(_expression);
+	if (_expression.type() == typeid(FunctionCall))
+	{
+		FunctionCall& funCall = boost::get<FunctionCall>(_expression);
+
+		bool movable = boost::algorithm::all_of(
+			funCall.arguments,
+			[=](Expression const& _arg) { return MovableChecker(_arg).movable(); }
+		);
+		if (m_inlinableFunctions.count(funCall.functionName.name) && movable)
+		{
+			FunctionDefinition const& fun = *m_inlinableFunctions.at(funCall.functionName.name);
+			map<string, Expression const*> substitutions;
+			for (size_t i = 0; i < fun.parameters.size(); ++i)
+				substitutions[fun.parameters[i].name] = &funCall.arguments[i];
+			_expression = Substitution(substitutions).translate(*boost::get<Assignment>(fun.body.statements.front()).value);
+
+			// TODO Add metric! This metric should perform well on a pair of functions who
+			// call each other recursively.
+		}
+	}
+}
diff --git a/libyul/optimiser/ExpressionInliner.h b/libyul/optimiser/ExpressionInliner.h
new file mode 100644
index 00000000..99fa68c9
--- /dev/null
+++ b/libyul/optimiser/ExpressionInliner.h
@@ -0,0 +1,72 @@
+/*
+	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 performs function inlining.
+ */
+#pragma once
+
+#include <libyul/optimiser/ASTWalker.h>
+
+#include <libyul/ASTDataForward.h>
+
+#include <boost/variant.hpp>
+#include <boost/optional.hpp>
+
+#include <set>
+
+namespace dev
+{
+namespace julia
+{
+
+/**
+ * Optimiser component that modifies an AST in place, inlining functions that can be
+ * inlined inside functional expressions, i.e. functions that
+ *  - return a single value
+ *  - have a body like r := <functional expression>
+ *  - neither reference themselves nor r in the right hand side
+ *
+ * Furthermore, the arguments of the function call cannot have any side-effects.
+ *
+ * This component can only be used on sources with unique names.
+ */
+class ExpressionInliner: public ASTModifier
+{
+public:
+	ExpressionInliner(Block& _block):
+		m_block(_block)
+	{}
+
+	void run();
+
+	using ASTModifier::operator();
+	virtual void operator()(FunctionDefinition& _fun) override;
+
+	virtual void visit(Expression& _expression) override;
+
+private:
+	std::map<std::string, FunctionDefinition const*> m_inlinableFunctions;
+	std::map<std::string, std::string> m_varReplacements;
+	/// Set of functions we are currently visiting inside.
+	std::set<std::string> m_currentFunctions;
+
+	Block& m_block;
+};
+
+
+}
+}
diff --git a/libyul/optimiser/ExpressionJoiner.cpp b/libyul/optimiser/ExpressionJoiner.cpp
new file mode 100644
index 00000000..ebf01346
--- /dev/null
+++ b/libyul/optimiser/ExpressionJoiner.cpp
@@ -0,0 +1,166 @@
+/*
+	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 undoes what the ExpressionSplitter did, i.e.
+ * it more or less inlines variable declarations.
+ */
+
+#include <libyul/optimiser/ExpressionJoiner.h>
+
+#include <libyul/optimiser/NameCollector.h>
+#include <libyul/optimiser/Utilities.h>
+#include <libyul/Exceptions.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+#include <libdevcore/CommonData.h>
+
+#include <boost/range/adaptor/reversed.hpp>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+using namespace dev::solidity;
+
+void ExpressionJoiner::operator()(FunctionalInstruction& _instruction)
+{
+	handleArguments(_instruction.arguments);
+}
+
+void ExpressionJoiner::operator()(FunctionCall& _funCall)
+{
+	handleArguments(_funCall.arguments);
+}
+
+void ExpressionJoiner::operator()(If& _if)
+{
+	visit(*_if.condition);
+	(*this)(_if.body);
+}
+
+void ExpressionJoiner::operator()(Switch& _switch)
+{
+	visit(*_switch.expression);
+	for (auto& _case: _switch.cases)
+		// Do not visit the case expression, nothing to unbreak there.
+		(*this)(_case.body);
+}
+
+void ExpressionJoiner::operator()(Block& _block)
+{
+	resetLatestStatementPointer();
+	for (size_t i = 0; i < _block.statements.size(); ++i)
+	{
+		visit(_block.statements[i]);
+		m_currentBlock = &_block;
+		m_latestStatementInBlock = i;
+	}
+
+	removeEmptyBlocks(_block);
+	resetLatestStatementPointer();
+}
+
+void ExpressionJoiner::visit(Expression& _e)
+{
+	if (_e.type() == typeid(Identifier))
+	{
+		Identifier const& identifier = boost::get<Identifier>(_e);
+		if (isLatestStatementVarDeclOf(identifier) && m_references[identifier.name] == 1)
+		{
+			VariableDeclaration& varDecl = boost::get<VariableDeclaration>(*latestStatement());
+			assertThrow(varDecl.variables.size() == 1, OptimizerException, "");
+			assertThrow(varDecl.value, OptimizerException, "");
+
+			_e = std::move(*varDecl.value);
+			// Delete the variable declaration (also get the moved-from structure back into a sane state)
+			*latestStatement() = Block();
+
+			decrementLatestStatementPointer();
+		}
+	}
+	else
+		ASTModifier::visit(_e);
+}
+
+void ExpressionJoiner::run(Block& _ast)
+{
+	ExpressionJoiner{_ast}(_ast);
+}
+
+ExpressionJoiner::ExpressionJoiner(Block& _ast)
+{
+	ReferencesCounter counter;
+	counter(_ast);
+	m_references = counter.references();
+}
+
+void ExpressionJoiner::handleArguments(vector<Expression>& _arguments)
+{
+	// We have to fill from left to right, but we can only
+	// fill if everything to the right is just an identifier
+	// or a literal.
+	// Also we only descend into function calls if everything
+	// on the right is an identifier or literal.
+
+	size_t i = _arguments.size();
+	for (Expression const& arg: _arguments | boost::adaptors::reversed)
+	{
+		--i;
+		if (arg.type() != typeid(Identifier) && arg.type() != typeid(Literal))
+			break;
+	}
+	// i points to the last element that is neither an identifier nor a literal,
+	// or to the first element if all of them are identifiers or literals.
+
+	for (; i < _arguments.size(); ++i)
+		visit(_arguments.at(i));
+}
+
+void ExpressionJoiner::decrementLatestStatementPointer()
+{
+	if (!m_currentBlock)
+		return;
+	if (m_latestStatementInBlock > 0)
+		--m_latestStatementInBlock;
+	else
+		resetLatestStatementPointer();
+}
+
+void ExpressionJoiner::resetLatestStatementPointer()
+{
+	m_currentBlock = nullptr;
+	m_latestStatementInBlock = size_t(-1);
+}
+
+Statement* ExpressionJoiner::latestStatement()
+{
+	if (!m_currentBlock)
+		return nullptr;
+	else
+		return &m_currentBlock->statements.at(m_latestStatementInBlock);
+}
+
+bool ExpressionJoiner::isLatestStatementVarDeclOf(Identifier const& _identifier)
+{
+	Statement const* statement = latestStatement();
+	if (!statement || statement->type() != typeid(VariableDeclaration))
+		return false;
+	VariableDeclaration const& varDecl = boost::get<VariableDeclaration>(*statement);
+	if (varDecl.variables.size() != 1 || !varDecl.value)
+		return false;
+	return varDecl.variables.at(0).name == _identifier.name;
+}
diff --git a/libyul/optimiser/ExpressionJoiner.h b/libyul/optimiser/ExpressionJoiner.h
new file mode 100644
index 00000000..a7ae50bc
--- /dev/null
+++ b/libyul/optimiser/ExpressionJoiner.h
@@ -0,0 +1,102 @@
+/*
+	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 undoes what the ExpressionSplitter did, i.e.
+ * it more or less inlines variable declarations.
+ */
+#pragma once
+
+#include <libyul/ASTDataForward.h>
+
+#include <libyul/optimiser/ASTWalker.h>
+
+#include <map>
+
+namespace dev
+{
+namespace julia
+{
+
+class NameCollector;
+
+
+/**
+ * Optimiser component that modifies an AST in place, turning sequences
+ * of variable declarations into complex expressions, if the variables
+ * are declared in the right order. This component does the opposite
+ * of ExpressionSplitter.
+ * Since the order of opcode or function evaluation is unchanged,
+ * this transformation does not need to care about conflicting opcodes.
+ *
+ * Code of the form
+ *
+ * let a1 := mload(y)
+ * let a2 := mul(x, 4)
+ * sstore(a2, a1)
+ *
+ * is transformed into
+ *
+ * sstore(mul(x, 4), mload(y))
+ *
+ * The transformation is not applied to loop conditions, because those are
+ * evaluated with each loop.
+ *
+ * The component can be applied to sub-blocks of the AST, you do not
+ * need to pass a full AST.
+ *
+ * Prerequisites: Disambiguator
+ *
+ * Implementation note: We visit the AST, modifying it in place.
+ * The class starts counting references and will only replace variables
+ * that have exactly one reference. It keeps a "latest statement pointer"
+ * which always points to the statement right before the current statement.
+ * Any function call or opcode will reset this pointer. If an identifier
+ * is encountered that was declared in the "latest statement", it is replaced
+ * by the value of the declaration, the "latest statement" is replaced
+ * by an empty block and the pointer is decremented.
+ * A block also resets the latest statement pointer.
+ */
+class ExpressionJoiner: public ASTModifier
+{
+public:
+	virtual void operator()(FunctionalInstruction&) override;
+	virtual void operator()(FunctionCall&) override;
+	virtual void operator()(If&) override;
+	virtual void operator()(Switch&) override;
+	virtual void operator()(Block& _block) override;
+
+	using ASTModifier::visit;
+	virtual void visit(Expression& _e) override;
+
+	static void run(Block& _ast);
+private:
+	explicit ExpressionJoiner(Block& _ast);
+
+	void handleArguments(std::vector<Expression>& _arguments);
+
+	void decrementLatestStatementPointer();
+	void resetLatestStatementPointer();
+	Statement* latestStatement();
+	bool isLatestStatementVarDeclOf(Identifier const& _identifier);
+
+	Block* m_currentBlock = nullptr;
+	size_t m_latestStatementInBlock = 0;
+	std::map<std::string, size_t> m_references;
+};
+
+}
+}
diff --git a/libyul/optimiser/ExpressionSimplifier.cpp b/libyul/optimiser/ExpressionSimplifier.cpp
new file mode 100644
index 00000000..5d89cef0
--- /dev/null
+++ b/libyul/optimiser/ExpressionSimplifier.cpp
@@ -0,0 +1,48 @@
+/*
+	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 uses the simplification rules to simplify expressions.
+ */
+
+#include <libyul/optimiser/ExpressionSimplifier.h>
+
+#include <libyul/optimiser/SimplificationRules.h>
+#include <libyul/optimiser/Semantics.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+#include <libdevcore/CommonData.h>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+using namespace dev::solidity;
+
+
+void ExpressionSimplifier::visit(Expression& _expression)
+{
+	ASTModifier::visit(_expression);
+	while (auto match = SimplificationRules::findFirstMatch(_expression))
+	{
+		// Do not apply the rule if it removes non-constant parts of the expression.
+		// TODO: The check could actually be less strict than "movable".
+		// We only require "Does not cause side-effects".
+		if (match->removesNonConstants && !MovableChecker(_expression).movable())
+			return;
+		_expression = match->action().toExpression(locationOf(_expression));
+	}
+}
diff --git a/libyul/optimiser/ExpressionSimplifier.h b/libyul/optimiser/ExpressionSimplifier.h
new file mode 100644
index 00000000..d11cd5d6
--- /dev/null
+++ b/libyul/optimiser/ExpressionSimplifier.h
@@ -0,0 +1,45 @@
+/*
+	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 uses the simplification rules to simplify expressions.
+ */
+
+#pragma once
+
+#include <libyul/ASTDataForward.h>
+
+#include <libyul/optimiser/ASTWalker.h>
+
+namespace dev
+{
+namespace julia
+{
+
+/**
+ * Applies simplification rules to all expressions.
+ */
+class ExpressionSimplifier: public ASTModifier
+{
+public:
+	using ASTModifier::operator();
+	virtual void visit(Expression& _expression);
+
+private:
+};
+
+}
+}
diff --git a/libyul/optimiser/ExpressionSplitter.cpp b/libyul/optimiser/ExpressionSplitter.cpp
new file mode 100644
index 00000000..e4e2739e
--- /dev/null
+++ b/libyul/optimiser/ExpressionSplitter.cpp
@@ -0,0 +1,105 @@
+/*
+	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 turns complex expressions into multiple variable
+ * declarations.
+ */
+
+#include <libyul/optimiser/ExpressionSplitter.h>
+
+#include <libyul/optimiser/ASTWalker.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+#include <libdevcore/CommonData.h>
+
+#include <boost/range/adaptor/reversed.hpp>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+using namespace dev::solidity;
+
+void ExpressionSplitter::operator()(FunctionalInstruction& _instruction)
+{
+	for (auto& arg: _instruction.arguments | boost::adaptors::reversed)
+		outlineExpression(arg);
+}
+
+void ExpressionSplitter::operator()(FunctionCall& _funCall)
+{
+	for (auto& arg: _funCall.arguments | boost::adaptors::reversed)
+		outlineExpression(arg);
+}
+
+void ExpressionSplitter::operator()(If& _if)
+{
+	outlineExpression(*_if.condition);
+	(*this)(_if.body);
+}
+
+void ExpressionSplitter::operator()(Switch& _switch)
+{
+	outlineExpression(*_switch.expression);
+	for (auto& _case: _switch.cases)
+		// Do not visit the case expression, nothing to break there.
+		(*this)(_case.body);
+}
+
+void ExpressionSplitter::operator()(ForLoop& _loop)
+{
+	(*this)(_loop.pre);
+	// Do not visit the condition because we cannot break expressions there.
+	(*this)(_loop.post);
+	(*this)(_loop.body);
+}
+
+void ExpressionSplitter::operator()(Block& _block)
+{
+	vector<Statement> saved;
+	swap(saved, m_statementsToPrefix);
+
+	function<boost::optional<vector<Statement>>(Statement&)> f =
+			[&](Statement& _statement) -> boost::optional<vector<Statement>> {
+		m_statementsToPrefix.clear();
+		visit(_statement);
+		if (m_statementsToPrefix.empty())
+			return {};
+		m_statementsToPrefix.emplace_back(std::move(_statement));
+		return std::move(m_statementsToPrefix);
+	};
+	iterateReplacing(_block.statements, f);
+
+	swap(saved, m_statementsToPrefix);
+}
+
+void ExpressionSplitter::outlineExpression(Expression& _expr)
+{
+	if (_expr.type() == typeid(Identifier))
+		return;
+
+	visit(_expr);
+
+	SourceLocation location = locationOf(_expr);
+	string var = m_nameDispenser.newName("");
+	m_statementsToPrefix.emplace_back(VariableDeclaration{
+		location,
+		{{TypedName{location, var, ""}}},
+		make_shared<Expression>(std::move(_expr))
+	});
+	_expr = Identifier{location, var};
+}
diff --git a/libyul/optimiser/ExpressionSplitter.h b/libyul/optimiser/ExpressionSplitter.h
new file mode 100644
index 00000000..89757df3
--- /dev/null
+++ b/libyul/optimiser/ExpressionSplitter.h
@@ -0,0 +1,86 @@
+/*
+	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 turns complex expressions into multiple variable
+ * declarations.
+ */
+#pragma once
+
+#include <libyul/ASTDataForward.h>
+
+#include <libyul/optimiser/ASTWalker.h>
+#include <libyul/optimiser/NameDispenser.h>
+
+#include <vector>
+
+namespace dev
+{
+namespace julia
+{
+
+class NameCollector;
+
+
+/**
+ * Optimiser component that modifies an AST in place, turning complex
+ * expressions into simple expressions and multiple variable declarations.
+ *
+ * Code of the form
+ *
+ * sstore(mul(x, 4), mload(y))
+ *
+ * is transformed into
+ *
+ * let a1 := mload(y)
+ * let a2 := mul(x, 4)
+ * sstore(a2, a1)
+ *
+ * The transformation is not applied to loop conditions, because the loop control flow
+ * does not allow "outlining" the inner expressions in all cases.
+ *
+ * The final program should be in a form such that with the exception of a loop condition,
+ * function calls can only appear in the right-hand side of a variable declaration,
+ * assignments or expression statements and all arguments have to be constants or variables.
+ */
+class ExpressionSplitter: public ASTModifier
+{
+public:
+	explicit ExpressionSplitter(NameDispenser& _nameDispenser):
+		m_nameDispenser(_nameDispenser)
+	{ }
+
+	virtual void operator()(FunctionalInstruction&) override;
+	virtual void operator()(FunctionCall&) override;
+	virtual void operator()(If&) override;
+	virtual void operator()(Switch&) override;
+	virtual void operator()(ForLoop&) override;
+	virtual void operator()(Block& _block) override;
+
+private:
+	/// Replaces the expression by a variable if it is a function call or functional
+	/// instruction. The declaration of the variable is appended to m_statementsToPrefix.
+	/// Recurses via visit().
+	void outlineExpression(Expression& _expr);
+
+	/// List of statements that should go in front of the currently visited AST element,
+	/// at the statement level.
+	std::vector<Statement> m_statementsToPrefix;
+	NameDispenser& m_nameDispenser;
+};
+
+}
+}
diff --git a/libyul/optimiser/FullInliner.cpp b/libyul/optimiser/FullInliner.cpp
new file mode 100644
index 00000000..7af642be
--- /dev/null
+++ b/libyul/optimiser/FullInliner.cpp
@@ -0,0 +1,264 @@
+/*
+	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 performs function inlining for arbitrary functions.
+ */
+
+#include <libyul/optimiser/FullInliner.h>
+
+#include <libyul/optimiser/ASTCopier.h>
+#include <libyul/optimiser/ASTWalker.h>
+#include <libyul/optimiser/NameCollector.h>
+#include <libyul/optimiser/Semantics.h>
+#include <libyul/Exceptions.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+#include <libdevcore/CommonData.h>
+
+#include <boost/range/adaptor/reversed.hpp>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+using namespace dev::solidity;
+
+FullInliner::FullInliner(Block& _ast):
+	m_ast(_ast)
+{
+	assertThrow(m_ast.statements.size() >= 1, OptimizerException, "");
+	assertThrow(m_ast.statements.front().type() == typeid(Block), OptimizerException, "");
+	m_nameDispenser.m_usedNames = NameCollector(m_ast).names();
+
+	for (size_t i = 1; i < m_ast.statements.size(); ++i)
+	{
+		assertThrow(m_ast.statements.at(i).type() == typeid(FunctionDefinition), OptimizerException, "");
+		FunctionDefinition& fun = boost::get<FunctionDefinition>(m_ast.statements.at(i));
+		m_functions[fun.name] = &fun;
+		m_functionsToVisit.insert(&fun);
+	}
+}
+
+void FullInliner::run()
+{
+	assertThrow(m_ast.statements[0].type() == typeid(Block), OptimizerException, "");
+	InlineModifier(*this, m_nameDispenser, "").visit(m_ast.statements[0]);
+	while (!m_functionsToVisit.empty())
+		handleFunction(**m_functionsToVisit.begin());
+}
+
+void FullInliner::handleFunction(FunctionDefinition& _fun)
+{
+	if (!m_functionsToVisit.count(&_fun))
+		return;
+	m_functionsToVisit.erase(&_fun);
+	(InlineModifier(*this, m_nameDispenser, _fun.name))(_fun.body);
+}
+
+void InlineModifier::operator()(FunctionalInstruction& _instruction)
+{
+	visitArguments(_instruction.arguments);
+}
+
+void InlineModifier::operator()(FunctionCall&)
+{
+	assertThrow(false, OptimizerException, "Should be handled in visit() instead.");
+}
+
+void InlineModifier::operator()(ForLoop& _loop)
+{
+	(*this)(_loop.pre);
+	// Do not visit the condition because we cannot inline there.
+	(*this)(_loop.post);
+	(*this)(_loop.body);
+}
+
+void InlineModifier::operator()(Block& _block)
+{
+	vector<Statement> saved;
+	saved.swap(m_statementsToPrefix);
+
+	// This is only used if needed to minimize the number of move operations.
+	vector<Statement> modifiedStatements;
+	for (size_t i = 0; i < _block.statements.size(); ++i)
+	{
+		visit(_block.statements.at(i));
+		if (!m_statementsToPrefix.empty())
+		{
+			if (modifiedStatements.empty())
+				std::move(
+					_block.statements.begin(),
+					_block.statements.begin() + i,
+					back_inserter(modifiedStatements)
+				);
+			modifiedStatements += std::move(m_statementsToPrefix);
+			m_statementsToPrefix.clear();
+		}
+		if (!modifiedStatements.empty())
+			modifiedStatements.emplace_back(std::move(_block.statements[i]));
+	}
+	if (!modifiedStatements.empty())
+		_block.statements = std::move(modifiedStatements);
+
+	saved.swap(m_statementsToPrefix);
+}
+
+void InlineModifier::visit(Expression& _expression)
+{
+	if (_expression.type() != typeid(FunctionCall))
+		return ASTModifier::visit(_expression);
+
+	FunctionCall& funCall = boost::get<FunctionCall>(_expression);
+	FunctionDefinition& fun = m_driver.function(funCall.functionName.name);
+
+	m_driver.handleFunction(fun);
+
+	// TODO: Insert good heuristic here. Perhaps implement that inside the driver.
+	bool doInline = funCall.functionName.name != m_currentFunction;
+
+	if (fun.returnVariables.size() > 1)
+		doInline = false;
+
+	{
+		vector<string> argNames;
+		vector<string> argTypes;
+		for (auto const& arg: fun.parameters)
+		{
+			argNames.push_back(fun.name + "_" + arg.name);
+			argTypes.push_back(arg.type);
+		}
+		visitArguments(funCall.arguments, argNames, argTypes, doInline);
+	}
+
+	if (!doInline)
+		return;
+
+	map<string, string> variableReplacements;
+	for (size_t i = 0; i < funCall.arguments.size(); ++i)
+		variableReplacements[fun.parameters[i].name] = boost::get<Identifier>(funCall.arguments[i]).name;
+	if (fun.returnVariables.empty())
+		_expression = noop(funCall.location);
+	else
+	{
+		string returnVariable = fun.returnVariables[0].name;
+		variableReplacements[returnVariable] = newName(fun.name + "_" + returnVariable);
+
+		m_statementsToPrefix.emplace_back(VariableDeclaration{
+			funCall.location,
+			{{funCall.location, variableReplacements[returnVariable], fun.returnVariables[0].type}},
+			{}
+		});
+		_expression = Identifier{funCall.location, variableReplacements[returnVariable]};
+	}
+	m_statementsToPrefix.emplace_back(BodyCopier(m_nameDispenser, fun.name + "_", variableReplacements)(fun.body));
+}
+
+void InlineModifier::visit(Statement& _statement)
+{
+	ASTModifier::visit(_statement);
+	// Replace pop(0) expression statemets (and others) by empty blocks.
+	if (_statement.type() == typeid(ExpressionStatement))
+	{
+		ExpressionStatement& expSt = boost::get<ExpressionStatement>(_statement);
+		if (expSt.expression.type() == typeid(FunctionalInstruction))
+		{
+			FunctionalInstruction& funInstr = boost::get<FunctionalInstruction>(expSt.expression);
+			if (funInstr.instruction == solidity::Instruction::POP)
+				if (MovableChecker(funInstr.arguments.at(0)).movable())
+					_statement = Block{expSt.location, {}};
+		}
+	}
+}
+
+void InlineModifier::visitArguments(
+	vector<Expression>& _arguments,
+	vector<string> const& _nameHints,
+	vector<string> const& _types,
+	bool _moveToFront
+)
+{
+	// If one of the elements moves parts to the front, all other elements right of it
+	// also have to be moved to the front to keep the order of evaluation.
+	vector<Statement> prefix;
+	for (size_t i = 0; i < _arguments.size(); ++i)
+	{
+		auto& arg = _arguments[i];
+		// TODO optimize vector operations, check that it actually moves
+		auto internalPrefix = visitRecursively(arg);
+		if (!internalPrefix.empty())
+		{
+			_moveToFront = true;
+			// We go through the arguments left to right, so we have to invert
+			// the prefixes.
+			prefix = std::move(internalPrefix) + std::move(prefix);
+		}
+		else if (_moveToFront)
+		{
+			auto location = locationOf(arg);
+			string var = newName(i < _nameHints.size() ? _nameHints[i] : "");
+			prefix.emplace(prefix.begin(), VariableDeclaration{
+				location,
+				{{TypedName{location, var, i < _types.size() ? _types[i] : ""}}},
+				make_shared<Expression>(std::move(arg))
+			});
+			arg = Identifier{location, var};
+		}
+	}
+	m_statementsToPrefix += std::move(prefix);
+}
+
+vector<Statement> InlineModifier::visitRecursively(Expression& _expression)
+{
+	vector<Statement> saved;
+	saved.swap(m_statementsToPrefix);
+	visit(_expression);
+	saved.swap(m_statementsToPrefix);
+	return saved;
+}
+
+string InlineModifier::newName(string const& _prefix)
+{
+	return m_nameDispenser.newName(_prefix);
+}
+
+Expression InlineModifier::noop(SourceLocation const& _location)
+{
+	return FunctionalInstruction{_location, solidity::Instruction::POP, {
+		Literal{_location, assembly::LiteralKind::Number, "0", ""}
+	}};
+}
+
+Statement BodyCopier::operator()(VariableDeclaration const& _varDecl)
+{
+	for (auto const& var: _varDecl.variables)
+		m_variableReplacements[var.name] = m_nameDispenser.newName(m_varNamePrefix + var.name);
+	return ASTCopier::operator()(_varDecl);
+}
+
+Statement BodyCopier::operator()(FunctionDefinition const& _funDef)
+{
+	assertThrow(false, OptimizerException, "Function hoisting has to be done before function inlining.");
+	return _funDef;
+}
+
+string BodyCopier::translateIdentifier(string const& _name)
+{
+	if (m_variableReplacements.count(_name))
+		return m_variableReplacements.at(_name);
+	else
+		return _name;
+}
diff --git a/libyul/optimiser/FullInliner.h b/libyul/optimiser/FullInliner.h
new file mode 100644
index 00000000..ecf987f7
--- /dev/null
+++ b/libyul/optimiser/FullInliner.h
@@ -0,0 +1,179 @@
+/*
+	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 performs function inlining for arbitrary functions.
+ */
+#pragma once
+
+#include <libyul/ASTDataForward.h>
+
+#include <libyul/optimiser/ASTCopier.h>
+#include <libyul/optimiser/ASTWalker.h>
+#include <libyul/optimiser/NameDispenser.h>
+#include <libyul/Exceptions.h>
+
+#include <libevmasm/SourceLocation.h>
+
+#include <boost/variant.hpp>
+#include <boost/optional.hpp>
+
+#include <set>
+
+namespace dev
+{
+namespace julia
+{
+
+class NameCollector;
+
+
+/**
+ * Optimiser component that modifies an AST in place, inlining arbitrary functions.
+ *
+ * Code of the form
+ *
+ * function f(a, b) -> c { ... }
+ * h(g(x(...), f(arg1(...), arg2(...)), y(...)), z(...))
+ *
+ * is transformed into
+ *
+ * function f(a, b) -> c { ... }
+ *
+ * let z1 := z(...) let y1 := y(...) let a2 := arg2(...) let a1 := arg1(...)
+ * let c1 := 0
+ * { code of f, with replacements: a -> a1, b -> a2, c -> c1, d -> d1 }
+ * h(g(x(...), c1, y1), z1)
+ *
+ * No temporary variable is created for expressions that are "movable"
+ * (i.e. they are "pure", have no side-effects and also do not depend on other code
+ * that might have side-effects).
+ *
+ * This component can only be used on sources with unique names and with hoisted functions,
+ * i.e. the root node has to be a block that itself contains a single block followed by all
+ * function definitions.
+ */
+class FullInliner: public ASTModifier
+{
+public:
+	explicit FullInliner(Block& _ast);
+
+	void run();
+
+	/// Perform inlining operations inside the given function.
+	void handleFunction(FunctionDefinition& _function);
+
+	FunctionDefinition& function(std::string _name) { return *m_functions.at(_name); }
+
+private:
+	/// The AST to be modified. The root block itself will not be modified, because
+	/// we store pointers to functions.
+	Block& m_ast;
+	std::map<std::string, FunctionDefinition*> m_functions;
+	std::set<FunctionDefinition*> m_functionsToVisit;
+	NameDispenser m_nameDispenser;
+};
+
+/**
+ * Class that walks the AST of a block that does not contain function definitions and perform
+ * the actual code modifications.
+ */
+class InlineModifier: public ASTModifier
+{
+public:
+	InlineModifier(FullInliner& _driver, NameDispenser& _nameDispenser, std::string _functionName):
+		m_currentFunction(std::move(_functionName)),
+		m_driver(_driver),
+		m_nameDispenser(_nameDispenser)
+	{ }
+	~InlineModifier()
+	{
+		assertThrow(m_statementsToPrefix.empty(), OptimizerException, "");
+	}
+
+	virtual void operator()(FunctionalInstruction&) override;
+	virtual void operator()(FunctionCall&) override;
+	virtual void operator()(ForLoop&) override;
+	virtual void operator()(Block& _block) override;
+
+	using ASTModifier::visit;
+	virtual void visit(Expression& _expression) override;
+	virtual void visit(Statement& _st) override;
+
+private:
+
+	/// Visits a list of expressions (usually an argument list to a function call) and tries
+	/// to inline them. If one of them is inlined, all right of it have to be moved to the front
+	/// (to keep the order of evaluation). If @a _moveToFront is true, all elements are moved
+	/// to the front. @a _nameHints and @_types are used for the newly created variables, but
+	/// both can be empty.
+	void visitArguments(
+		std::vector<Expression>& _arguments,
+		std::vector<std::string> const& _nameHints = {},
+		std::vector<std::string> const& _types = {},
+		bool _moveToFront = false
+	);
+
+	/// Visits an expression, but saves and restores the current statements to prefix and returns
+	/// the statements that should be prefixed for @a _expression.
+	std::vector<Statement> visitRecursively(Expression& _expression);
+
+	std::string newName(std::string const& _prefix);
+
+	/// @returns an expression returning nothing.
+	Expression noop(SourceLocation const& _location);
+
+	/// List of statements that should go in front of the currently visited AST element,
+	/// at the statement level.
+	std::vector<Statement> m_statementsToPrefix;
+	std::string m_currentFunction;
+	FullInliner& m_driver;
+	NameDispenser& m_nameDispenser;
+};
+
+/**
+ * Creates a copy of a block that is supposed to be the body of a function.
+ * Applies replacements to referenced variables and creates new names for
+ * variable declarations.
+ */
+class BodyCopier: public ASTCopier
+{
+public:
+	BodyCopier(
+		NameDispenser& _nameDispenser,
+		std::string const& _varNamePrefix,
+		std::map<std::string, std::string> const& _variableReplacements
+	):
+		m_nameDispenser(_nameDispenser),
+		m_varNamePrefix(_varNamePrefix),
+		m_variableReplacements(_variableReplacements)
+	{}
+
+	using ASTCopier::operator ();
+
+	virtual Statement operator()(VariableDeclaration const& _varDecl) override;
+	virtual Statement operator()(FunctionDefinition const& _funDef) override;
+
+	virtual std::string translateIdentifier(std::string const& _name) override;
+
+	NameDispenser& m_nameDispenser;
+	std::string const& m_varNamePrefix;
+	std::map<std::string, std::string> m_variableReplacements;
+};
+
+
+}
+}
diff --git a/libyul/optimiser/FunctionGrouper.cpp b/libyul/optimiser/FunctionGrouper.cpp
new file mode 100644
index 00000000..cbdd215f
--- /dev/null
+++ b/libyul/optimiser/FunctionGrouper.cpp
@@ -0,0 +1,47 @@
+/*
+	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 <libyul/optimiser/FunctionGrouper.h>
+
+#include <libsolidity/inlineasm/AsmData.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/libyul/optimiser/FunctionGrouper.h b/libyul/optimiser/FunctionGrouper.h
new file mode 100644
index 00000000..57279c16
--- /dev/null
+++ b/libyul/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 <libyul/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/libyul/optimiser/FunctionHoister.cpp b/libyul/optimiser/FunctionHoister.cpp
new file mode 100644
index 00000000..99525494
--- /dev/null
+++ b/libyul/optimiser/FunctionHoister.cpp
@@ -0,0 +1,51 @@
+/*
+	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 <libyul/optimiser/FunctionHoister.h>
+#include <libyul/optimiser/Utilities.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+#include <libdevcore/CommonData.h>
+
+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, {}};
+		}
+	}
+	removeEmptyBlocks(_block);
+	if (topLevel)
+		_block.statements += std::move(m_functions);
+}
diff --git a/libyul/optimiser/FunctionHoister.h b/libyul/optimiser/FunctionHoister.h
new file mode 100644
index 00000000..80d55703
--- /dev/null
+++ b/libyul/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 <libyul/ASTDataForward.h>
+
+#include <libyul/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/libyul/optimiser/InlinableExpressionFunctionFinder.cpp b/libyul/optimiser/InlinableExpressionFunctionFinder.cpp
new file mode 100644
index 00000000..e6332f3a
--- /dev/null
+++ b/libyul/optimiser/InlinableExpressionFunctionFinder.cpp
@@ -0,0 +1,70 @@
+/*
+	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 identifies functions to be inlined.
+ */
+
+#include <libyul/optimiser/InlinableExpressionFunctionFinder.h>
+
+#include <libyul/optimiser/Utilities.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+
+void InlinableExpressionFunctionFinder::operator()(Identifier const& _identifier)
+{
+	checkAllowed(_identifier.name);
+	ASTWalker::operator()(_identifier);
+}
+
+void InlinableExpressionFunctionFinder::operator()(FunctionCall const& _funCall)
+{
+	checkAllowed(_funCall.functionName.name);
+	ASTWalker::operator()(_funCall);
+}
+
+void InlinableExpressionFunctionFinder::operator()(FunctionDefinition const& _function)
+{
+	if (_function.returnVariables.size() == 1 && _function.body.statements.size() == 1)
+	{
+		string const& retVariable = _function.returnVariables.front().name;
+		Statement const& bodyStatement = _function.body.statements.front();
+		if (bodyStatement.type() == typeid(Assignment))
+		{
+			Assignment const& assignment = boost::get<Assignment>(bodyStatement);
+			if (assignment.variableNames.size() == 1 && assignment.variableNames.front().name == retVariable)
+			{
+				// FIXME: use code size metric here
+
+				// We cannot overwrite previous settings, because this function definition
+				// would not be valid here if we were searching inside a functionally inlinable
+				// function body.
+				assertThrow(m_disallowedIdentifiers.empty() && !m_foundDisallowedIdentifier, OptimizerException, "");
+				m_disallowedIdentifiers = set<string>{retVariable, _function.name};
+				boost::apply_visitor(*this, *assignment.value);
+				if (!m_foundDisallowedIdentifier)
+					m_inlinableFunctions[_function.name] = &_function;
+				m_disallowedIdentifiers.clear();
+				m_foundDisallowedIdentifier = false;
+			}
+		}
+	}
+	ASTWalker::operator()(_function.body);
+}
diff --git a/libyul/optimiser/InlinableExpressionFunctionFinder.h b/libyul/optimiser/InlinableExpressionFunctionFinder.h
new file mode 100644
index 00000000..69c003e6
--- /dev/null
+++ b/libyul/optimiser/InlinableExpressionFunctionFinder.h
@@ -0,0 +1,69 @@
+/*
+	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 identifies functions to be inlined.
+ */
+
+#pragma once
+
+#include <libyul/ASTDataForward.h>
+#include <libyul/optimiser/ASTWalker.h>
+
+#include <set>
+
+namespace dev
+{
+namespace julia
+{
+
+/**
+ * Optimiser component that finds functions that can be
+ * inlined inside functional expressions, i.e. functions that
+ *  - have a single return parameter r
+ *  - have a body like r := <functional expression>
+ *  - neither reference themselves nor r in the right hand side
+ *
+ * This component can only be used on sources with unique names.
+ */
+class InlinableExpressionFunctionFinder: public ASTWalker
+{
+public:
+
+	std::map<std::string, FunctionDefinition const*> const& inlinableFunctions() const
+	{
+		return m_inlinableFunctions;
+	}
+
+	using ASTWalker::operator();
+	virtual void operator()(Identifier const& _identifier) override;
+	virtual void operator()(FunctionCall const& _funCall) override;
+	virtual void operator()(FunctionDefinition const& _function) override;
+
+private:
+	void checkAllowed(std::string const& _name)
+	{
+		if (m_disallowedIdentifiers.count(_name))
+			m_foundDisallowedIdentifier = true;
+	}
+
+	bool m_foundDisallowedIdentifier = false;
+	std::set<std::string> m_disallowedIdentifiers;
+	std::map<std::string, FunctionDefinition const*> m_inlinableFunctions;
+};
+
+}
+}
diff --git a/libyul/optimiser/MainFunction.cpp b/libyul/optimiser/MainFunction.cpp
new file mode 100644
index 00000000..dfc19574
--- /dev/null
+++ b/libyul/optimiser/MainFunction.cpp
@@ -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/>.
+*/
+/**
+ * Changes the topmost block to be a function with a specific name ("main") which has no
+ * inputs nor outputs.
+ */
+
+#include <libyul/optimiser/MainFunction.h>
+
+#include <libyul/optimiser/NameCollector.h>
+#include <libyul/Exceptions.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+#include <libdevcore/CommonData.h>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+using namespace dev::solidity;
+
+void MainFunction::operator()(Block& _block)
+{
+	assertThrow(_block.statements.size() >= 1, OptimizerException, "");
+	assertThrow(_block.statements[0].type() == typeid(Block), OptimizerException, "");
+	for (size_t i = 1; i < _block.statements.size(); ++i)
+		assertThrow(_block.statements.at(i).type() == typeid(FunctionDefinition), OptimizerException, "");
+	/// @todo this should handle scopes properly and instead of an assertion it should rename the conflicting function
+	assertThrow(NameCollector(_block).names().count("main") == 0, OptimizerException, "");
+
+	Block& block = boost::get<Block>(_block.statements[0]);
+	FunctionDefinition main{
+		block.location,
+		"main",
+		{},
+		{},
+		std::move(block)
+	};
+	_block.statements[0] = std::move(main);
+}
diff --git a/libyul/optimiser/MainFunction.h b/libyul/optimiser/MainFunction.h
new file mode 100644
index 00000000..4d790729
--- /dev/null
+++ b/libyul/optimiser/MainFunction.h
@@ -0,0 +1,41 @@
+/*
+	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/>.
+*/
+/**
+ * Changes the topmost block to be a function with a specific name ("main") which has no
+ * inputs nor outputs.
+ */
+
+#pragma once
+
+#include <libyul/ASTDataForward.h>
+
+namespace dev
+{
+namespace julia
+{
+
+/**
+ * Prerequisites: Function Grouper
+ */
+class MainFunction
+{
+public:
+	void operator()(Block& _block);
+};
+
+}
+}
diff --git a/libyul/optimiser/Metrics.cpp b/libyul/optimiser/Metrics.cpp
new file mode 100644
index 00000000..ce7c1bed
--- /dev/null
+++ b/libyul/optimiser/Metrics.cpp
@@ -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/>.
+*/
+/**
+* Module providing metrics for the optimizer.
+*/
+
+#include <libyul/optimiser/Metrics.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+using namespace dev;
+using namespace dev::julia;
+
+size_t CodeSize::codeSize(Statement const& _statement)
+{
+	CodeSize cs;
+	cs.visit(_statement);
+	return cs.m_size;
+}
+
+size_t CodeSize::codeSize(Expression const& _expression)
+{
+	CodeSize cs;
+	cs.visit(_expression);
+	return cs.m_size;
+}
+
+void CodeSize::visit(Statement const& _statement)
+{
+	++m_size;
+	ASTWalker::visit(_statement);
+}
+
+void CodeSize::visit(Expression const& _expression)
+{
+	++m_size;
+	ASTWalker::visit(_expression);
+}
diff --git a/libyul/optimiser/Metrics.h b/libyul/optimiser/Metrics.h
new file mode 100644
index 00000000..f0d6a203
--- /dev/null
+++ b/libyul/optimiser/Metrics.h
@@ -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/>.
+*/
+/**
+ * Module providing metrics for the optimizer.
+ */
+
+#pragma once
+
+#include <libyul/optimiser/ASTWalker.h>
+
+namespace dev
+{
+namespace julia
+{
+
+class CodeSize: public ASTWalker
+{
+public:
+	/// Returns a metric for the code size of an AST element.
+	/// More specifically, it returns the number of AST nodes.
+	static size_t codeSize(Statement const& _statement);
+	/// Returns a metric for the code size of an AST element.
+	/// More specifically, it returns the number of AST nodes.
+	static size_t codeSize(Expression const& _expression);
+
+private:
+	virtual void visit(Statement const& _statement) override;
+	virtual void visit(Expression const& _expression) override;
+
+private:
+	size_t m_size = 0;
+};
+
+}
+}
diff --git a/libyul/optimiser/NameCollector.cpp b/libyul/optimiser/NameCollector.cpp
new file mode 100644
index 00000000..cbc7aad2
--- /dev/null
+++ b/libyul/optimiser/NameCollector.cpp
@@ -0,0 +1,74 @@
+/*
+	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 <libyul/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);
+	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);
+}
+
+void ReferencesCounter::operator()(Identifier const& _identifier)
+{
+	++m_references[_identifier.name];
+}
+
+void ReferencesCounter::operator()(FunctionCall const& _funCall)
+{
+	++m_references[_funCall.functionName.name];
+	ASTWalker::operator()(_funCall);
+}
+
+map<string, size_t> ReferencesCounter::countReferences(Block const& _block)
+{
+	ReferencesCounter counter;
+	counter(_block);
+	return counter.references();
+}
+
+map<string, size_t> ReferencesCounter::countReferences(Expression const& _expression)
+{
+	ReferencesCounter counter;
+	counter.visit(_expression);
+	return counter.references();
+}
+
+void Assignments::operator()(Assignment const& _assignment)
+{
+	for (auto const& var: _assignment.variableNames)
+		m_names.insert(var.name);
+}
diff --git a/libyul/optimiser/NameCollector.h b/libyul/optimiser/NameCollector.h
new file mode 100644
index 00000000..9ea32674
--- /dev/null
+++ b/libyul/optimiser/NameCollector.h
@@ -0,0 +1,87 @@
+/*
+	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 facts about identifiers and definitions.
+ */
+
+#pragma once
+
+#include <libyul/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:
+	explicit NameCollector(Block const& _block)
+	{
+		(*this)(_block);
+	}
+
+	using ASTWalker::operator ();
+	virtual void operator()(VariableDeclaration const& _varDecl) override;
+	virtual void operator()(FunctionDefinition const& _funDef) override;
+
+	std::set<std::string> names() const { return m_names; }
+private:
+	std::set<std::string> m_names;
+};
+
+/**
+ * Specific AST walker that counts all references to all declarations.
+ */
+class ReferencesCounter: public ASTWalker
+{
+public:
+	using ASTWalker::operator ();
+	virtual void operator()(Identifier const& _identifier);
+	virtual void operator()(FunctionCall const& _funCall);
+
+	static std::map<std::string, size_t> countReferences(Block const& _block);
+	static std::map<std::string, size_t> countReferences(Expression const& _expression);
+
+	std::map<std::string, size_t> const& references() const { return m_references; }
+private:
+	std::map<std::string, size_t> m_references;
+};
+
+/**
+ * Specific AST walker that finds all variables that are assigned to.
+ */
+class Assignments: public ASTWalker
+{
+public:
+	using ASTWalker::operator ();
+	virtual void operator()(Assignment const& _assignment) override;
+
+	std::set<std::string> const& names() const { return m_names; }
+private:
+	std::set<std::string> m_names;
+};
+
+}
+}
diff --git a/libyul/optimiser/NameDispenser.cpp b/libyul/optimiser/NameDispenser.cpp
new file mode 100644
index 00000000..4b177389
--- /dev/null
+++ b/libyul/optimiser/NameDispenser.cpp
@@ -0,0 +1,38 @@
+/*
+	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 can create new unique names.
+ */
+
+#include <libyul/optimiser/NameDispenser.h>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+
+string NameDispenser::newName(string const& _prefix)
+{
+	string name = _prefix;
+	size_t suffix = 0;
+	while (name.empty() || m_usedNames.count(name))
+	{
+		suffix++;
+		name = _prefix + "_" + to_string(suffix);
+	}
+	m_usedNames.insert(name);
+	return name;
+}
diff --git a/libyul/optimiser/NameDispenser.h b/libyul/optimiser/NameDispenser.h
new file mode 100644
index 00000000..91c43d54
--- /dev/null
+++ b/libyul/optimiser/NameDispenser.h
@@ -0,0 +1,37 @@
+/*
+	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 can create new unique names.
+ */
+#pragma once
+
+#include <set>
+#include <string>
+
+namespace dev
+{
+namespace julia
+{
+
+struct NameDispenser
+{
+	std::string newName(std::string const& _prefix);
+	std::set<std::string> m_usedNames;
+};
+
+}
+}
diff --git a/libyul/optimiser/README.md b/libyul/optimiser/README.md
new file mode 100644
index 00000000..faef818b
--- /dev/null
+++ b/libyul/optimiser/README.md
@@ -0,0 +1,157 @@
+Note that the Yul optimiser is still in research phase. Because of that,
+the following description might not fully reflect the current or even
+planned state of the optimiser.
+
+## Yul Optimiser
+
+The Yul 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 end of 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 to a higher-level block 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 looked 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 statement 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.
+
+## Expression Splitter
+
+The expression splitter turns expressions like ``add(mload(x), mul(mload(y), 0x20))``
+into a sequence of declarations of unique variables that are assigned sub-expressions
+of that expression so that each function call has only variables or literals
+as arguments.
+
+The above would be transformed into
+
+    {
+        let _1 := mload(y)
+        let _2 := mul(_1, 0x20)
+        let _3 := mload(x)
+        let z := add(_3, _2)
+    }
+
+Note that this transformation does not change the order of opcodes or function calls.
+
+It is not applied to loop conditions, because the loop control flow does not allow
+this "outlining" of the inner expressions in all cases.
+
+The final program should be in a form such that with the exception of loop conditions,
+function calls can only appear in the right-hand side of a variable declaration,
+assignments or expression statements and all arguments have to be constants or variables.
+
+The benefits of this form are that it is much easier to re-order the sequence of opcodes
+and it is also easier to perform function call inlining. The drawback is that
+such code is much harder to read for humans.
+
+## Expression Joiner
+
+This is the opposite operation of the expression splitter. It turns a sequence of
+variable declarations that have exactly one reference into a complex expression.
+This stage again fully preserves the order of function calls and opcode executions.
+It does not make use of any information concerning the commutability of opcodes;
+if moving the value of a variable to its place of use would change the order
+of any function call or opcode execution, the transformation is not performed.
+
+Note that the component will not move the assigned value of a variable assignment
+or a variable that is referenced more than once.
+
+## Common Subexpression Eliminator
+
+This step replaces a subexpression by the value of a pre-existing variable
+that currently has the same value (only if the value is movable), based
+on a syntactic comparison.
+
+This can be used to compute a local value numbering, especially if the
+expression splitter is used before.
+
+The expression simplifier will be able to perform better replacements
+if the common subexpression eliminator was run right before it.
+
+Prerequisites: Disambiguator
+
+## Full Function Inliner
+
+## Rematerialisation
+
+The rematerialisation stage tries to replace variable references by the expression that
+was last assigned to the variable. This is of course only beneficial if this expression
+is comparatively cheap to evaluate. Furthermore, it is only semantically equivalent if
+the value of the expression did not change between the point of assignment and the
+point of use. The main benefit of this stage is that it can save stack slots if it
+leads to a variable being eliminated completely (see below), but it can also
+save a DUP opcode on the EVM if the expression is very cheap.
+
+The algorithm only allows movable expressions (see above for a definition) in this case.
+Expressions that contain other variables are also disallowed if one of those variables
+have been assigned to in the meantime. This is also not applied to variables where
+assignment and use span across loops and conditionals.
+
+## Unused Definition Pruner
+
+If a variable or function is not referenced, it is removed from the code.
+If there are two assignments to a variable where the first one is a movable expression
+and the variable is not used between the two assignments (and the second is not inside
+a loop or conditional, the first one is not inside), the first assignment is removed.
+
+
+## Function Unifier
+
+## Expression Simplifier
+
+This step can only be applied for the EVM-flavoured dialect of Yul. It applies
+simple rules like ``x + 0 == x`` to simplify expressions.
+
+## Ineffective Statement Remover
+
+This step removes statements that have no side-effects.
+
+## WebAssembly specific
+
+### Main Function
+
+Changes the topmost block to be a function with a specific name ("main") which has no
+inputs nor outputs.
+
+Depends on the Function Grouper.
diff --git a/libyul/optimiser/Rematerialiser.cpp b/libyul/optimiser/Rematerialiser.cpp
new file mode 100644
index 00000000..5f2b9e8b
--- /dev/null
+++ b/libyul/optimiser/Rematerialiser.cpp
@@ -0,0 +1,55 @@
+/*(
+	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/>.
+*/
+/**
+ * Optimisation stage that replaces variables by their most recently assigned expressions.
+ */
+
+#include <libyul/optimiser/Rematerialiser.h>
+
+#include <libyul/optimiser/Metrics.h>
+#include <libyul/optimiser/ASTCopier.h>
+#include <libyul/Exceptions.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+
+void Rematerialiser::visit(Expression& _e)
+{
+	if (_e.type() == typeid(Identifier))
+	{
+		Identifier& identifier = boost::get<Identifier>(_e);
+		if (m_value.count(identifier.name))
+		{
+			string name = identifier.name;
+			bool expressionValid = true;
+			for (auto const& ref: m_references[name])
+				if (!inScope(ref))
+				{
+					expressionValid = false;
+					break;
+				}
+			assertThrow(m_value.at(name), OptimizerException, "");
+			auto const& value = *m_value.at(name);
+			if (expressionValid && CodeSize::codeSize(value) <= 7)
+				_e = (ASTCopier{}).translate(value);
+		}
+	}
+	DataFlowAnalyzer::visit(_e);
+}
diff --git a/libyul/optimiser/Rematerialiser.h b/libyul/optimiser/Rematerialiser.h
new file mode 100644
index 00000000..d06c2754
--- /dev/null
+++ b/libyul/optimiser/Rematerialiser.h
@@ -0,0 +1,48 @@
+/*
+	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/>.
+*/
+/**
+ * Optimisation stage that replaces variables by their most recently assigned expressions.
+ */
+
+#pragma once
+
+#include <libyul/optimiser/DataFlowAnalyzer.h>
+
+#include <string>
+#include <map>
+#include <set>
+
+namespace dev
+{
+namespace julia
+{
+
+/**
+ * Optimisation stage that replaces variables by their most recently assigned expressions.
+ *
+ * Prerequisite: Disambiguator
+ */
+class Rematerialiser: public DataFlowAnalyzer
+{
+protected:
+	using ASTModifier::visit;
+	virtual void visit(Expression& _e) override;
+
+};
+
+}
+}
diff --git a/libyul/optimiser/Semantics.cpp b/libyul/optimiser/Semantics.cpp
new file mode 100644
index 00000000..d610341d
--- /dev/null
+++ b/libyul/optimiser/Semantics.cpp
@@ -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.
+ */
+
+#include <libyul/optimiser/Semantics.h>
+
+#include <libyul/Exceptions.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&)
+{
+	assertThrow(false, OptimizerException, "Movability for statement requested.");
+}
diff --git a/libyul/optimiser/Semantics.h b/libyul/optimiser/Semantics.h
new file mode 100644
index 00000000..1963e7a3
--- /dev/null
+++ b/libyul/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 <libyul/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/libyul/optimiser/SimplificationRules.cpp b/libyul/optimiser/SimplificationRules.cpp
new file mode 100644
index 00000000..ca3f2984
--- /dev/null
+++ b/libyul/optimiser/SimplificationRules.cpp
@@ -0,0 +1,189 @@
+/*
+	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/>.
+*/
+/**
+ * Module for applying replacement rules against Expressions.
+ */
+
+#include <libyul/optimiser/SimplificationRules.h>
+
+#include <libyul/optimiser/Utilities.h>
+#include <libyul/optimiser/ASTCopier.h>
+#include <libyul/optimiser/Semantics.h>
+#include <libyul/optimiser/SyntacticalEquality.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+#include <libevmasm/RuleList.h>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+
+
+SimplificationRule<Pattern> const* SimplificationRules::findFirstMatch(Expression const& _expr)
+{
+	if (_expr.type() != typeid(FunctionalInstruction))
+		return nullptr;
+
+	static SimplificationRules rules;
+	assertThrow(rules.isInitialized(), OptimizerException, "Rule list not properly initialized.");
+
+	FunctionalInstruction const& instruction = boost::get<FunctionalInstruction>(_expr);
+	for (auto const& rule: rules.m_rules[byte(instruction.instruction)])
+	{
+		rules.resetMatchGroups();
+		if (rule.pattern.matches(_expr))
+			return &rule;
+	}
+	return nullptr;
+}
+
+bool SimplificationRules::isInitialized() const
+{
+	return !m_rules[byte(solidity::Instruction::ADD)].empty();
+}
+
+void SimplificationRules::addRules(vector<SimplificationRule<Pattern>> const& _rules)
+{
+	for (auto const& r: _rules)
+		addRule(r);
+}
+
+void SimplificationRules::addRule(SimplificationRule<Pattern> const& _rule)
+{
+	m_rules[byte(_rule.pattern.instruction())].push_back(_rule);
+}
+
+SimplificationRules::SimplificationRules()
+{
+	// Multiple occurrences of one of these inside one rule must match the same equivalence class.
+	// Constants.
+	Pattern A(PatternKind::Constant);
+	Pattern B(PatternKind::Constant);
+	Pattern C(PatternKind::Constant);
+	// Anything.
+	Pattern X;
+	Pattern Y;
+	A.setMatchGroup(1, m_matchGroups);
+	B.setMatchGroup(2, m_matchGroups);
+	C.setMatchGroup(3, m_matchGroups);
+	X.setMatchGroup(4, m_matchGroups);
+	Y.setMatchGroup(5, m_matchGroups);
+
+	addRules(simplificationRuleList(A, B, C, X, Y));
+	assertThrow(isInitialized(), OptimizerException, "Rule list not properly initialized.");
+}
+
+Pattern::Pattern(solidity::Instruction _instruction, vector<Pattern> const& _arguments):
+	m_kind(PatternKind::Operation),
+	m_instruction(_instruction),
+	m_arguments(_arguments)
+{
+}
+
+void Pattern::setMatchGroup(unsigned _group, map<unsigned, Expression const*>& _matchGroups)
+{
+	m_matchGroup = _group;
+	m_matchGroups = &_matchGroups;
+}
+
+bool Pattern::matches(Expression const& _expr) const
+{
+	if (m_kind == PatternKind::Constant)
+	{
+		if (_expr.type() != typeid(Literal))
+			return false;
+		Literal const& literal = boost::get<Literal>(_expr);
+		if (literal.kind != assembly::LiteralKind::Number)
+			return false;
+		if (m_data && *m_data != u256(literal.value))
+			return false;
+		assertThrow(m_arguments.empty(), OptimizerException, "");
+	}
+	else if (m_kind == PatternKind::Operation)
+	{
+		if (_expr.type() != typeid(FunctionalInstruction))
+			return false;
+		FunctionalInstruction const& instr = boost::get<FunctionalInstruction>(_expr);
+		if (m_instruction != instr.instruction)
+			return false;
+		assertThrow(m_arguments.size() == instr.arguments.size(), OptimizerException, "");
+		for (size_t i = 0; i < m_arguments.size(); ++i)
+			if (!m_arguments[i].matches(instr.arguments.at(i)))
+				return false;
+	}
+	else
+	{
+		assertThrow(m_arguments.empty(), OptimizerException, "");
+	}
+	// We support matching multiple expressions that require the same value
+	// based on identical ASTs, which have to be movable.
+	if (m_matchGroup)
+	{
+		if (m_matchGroups->count(m_matchGroup))
+		{
+			Expression const* firstMatch = (*m_matchGroups)[m_matchGroup];
+			assertThrow(firstMatch, OptimizerException, "Match set but to null.");
+			return
+				SyntacticalEqualityChecker::equal(*firstMatch, _expr) &&
+				MovableChecker(_expr).movable();
+		}
+		else
+			(*m_matchGroups)[m_matchGroup] = &_expr;
+	}
+	return true;
+}
+
+solidity::Instruction Pattern::instruction() const
+{
+	assertThrow(m_kind == PatternKind::Operation, OptimizerException, "");
+	return m_instruction;
+}
+
+Expression Pattern::toExpression(SourceLocation const& _location) const
+{
+	if (matchGroup())
+		return ASTCopier().translate(matchGroupValue());
+	if (m_kind == PatternKind::Constant)
+	{
+		assertThrow(m_data, OptimizerException, "No match group and no constant value given.");
+		return Literal{_location, assembly::LiteralKind::Number, formatNumber(*m_data), ""};
+	}
+	else if (m_kind == PatternKind::Operation)
+	{
+		vector<Expression> arguments;
+		for (auto const& arg: m_arguments)
+			arguments.emplace_back(arg.toExpression(_location));
+		return FunctionalInstruction{_location, m_instruction, std::move(arguments)};
+	}
+	assertThrow(false, OptimizerException, "Pattern of kind 'any', but no match group.");
+}
+
+u256 Pattern::d() const
+{
+	Literal const& literal = boost::get<Literal>(matchGroupValue());
+	assertThrow(literal.kind == assembly::LiteralKind::Number, OptimizerException, "");
+	return u256(literal.value);
+}
+
+Expression const& Pattern::matchGroupValue() const
+{
+	assertThrow(m_matchGroup > 0, OptimizerException, "");
+	assertThrow(!!m_matchGroups, OptimizerException, "");
+	assertThrow((*m_matchGroups)[m_matchGroup], OptimizerException, "");
+	return *(*m_matchGroups)[m_matchGroup];
+}
diff --git a/libyul/optimiser/SimplificationRules.h b/libyul/optimiser/SimplificationRules.h
new file mode 100644
index 00000000..2b5bccd5
--- /dev/null
+++ b/libyul/optimiser/SimplificationRules.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/>.
+*/
+/**
+ * Module for applying replacement rules against Expressions.
+ */
+
+#pragma once
+
+#include <libevmasm/ExpressionClasses.h>
+#include <libevmasm/SimplificationRule.h>
+
+#include <libyul/ASTDataForward.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+#include <boost/noncopyable.hpp>
+
+#include <functional>
+#include <vector>
+
+namespace dev
+{
+namespace julia
+{
+
+class Pattern;
+
+/**
+ * Container for all simplification rules.
+ */
+class SimplificationRules: public boost::noncopyable
+{
+public:
+	SimplificationRules();
+
+	/// @returns a pointer to the first matching pattern and sets the match
+	/// groups accordingly.
+	static SimplificationRule<Pattern> const* findFirstMatch(Expression const& _expr);
+
+	/// Checks whether the rulelist is non-empty. This is usually enforced
+	/// by the constructor, but we had some issues with static initialization.
+	bool isInitialized() const;
+private:
+	void addRules(std::vector<SimplificationRule<Pattern>> const& _rules);
+	void addRule(SimplificationRule<Pattern> const& _rule);
+
+	void resetMatchGroups() { m_matchGroups.clear(); }
+
+	std::map<unsigned, Expression const*> m_matchGroups;
+	std::vector<SimplificationRule<Pattern>> m_rules[256];
+};
+
+enum class PatternKind
+{
+	Operation,
+	Constant,
+	Any
+};
+
+/**
+ * Pattern to match against an expression.
+ * Also stores matched expressions to retrieve them later, for constructing new expressions using
+ * ExpressionTemplate.
+ */
+class Pattern
+{
+public:
+	/// Matches any expression.
+	Pattern(PatternKind _kind = PatternKind::Any): m_kind(_kind) {}
+	// Matches a specific constant value.
+	Pattern(unsigned _value): Pattern(u256(_value)) {}
+	// Matches a specific constant value.
+	Pattern(u256 const& _value): m_kind(PatternKind::Constant), m_data(std::make_shared<u256>(_value)) {}
+	// Matches a given instruction with given arguments
+	Pattern(solidity::Instruction _instruction, std::vector<Pattern> const& _arguments = {});
+	/// Sets this pattern to be part of the match group with the identifier @a _group.
+	/// Inside one rule, all patterns in the same match group have to match expressions from the
+	/// same expression equivalence class.
+	void setMatchGroup(unsigned _group, std::map<unsigned, Expression const*>& _matchGroups);
+	unsigned matchGroup() const { return m_matchGroup; }
+	bool matches(Expression const& _expr) const;
+
+	std::vector<Pattern> arguments() const { return m_arguments; }
+
+	/// @returns the data of the matched expression if this pattern is part of a match group.
+	u256 d() const;
+
+	solidity::Instruction instruction() const;
+
+	/// Turns this pattern into an actual expression. Should only be called
+	/// for patterns resulting from an action, i.e. with match groups assigned.
+	Expression toExpression(SourceLocation const& _location) const;
+
+private:
+	Expression const& matchGroupValue() const;
+
+	PatternKind m_kind = PatternKind::Any;
+	solidity::Instruction m_instruction; ///< Only valid if m_kind is Operation
+	std::shared_ptr<u256> m_data; ///< Only valid if m_kind is Constant
+	std::vector<Pattern> m_arguments;
+	unsigned m_matchGroup = 0;
+	std::map<unsigned, Expression const*>* m_matchGroups = nullptr;
+};
+
+}
+}
diff --git a/libyul/optimiser/Substitution.cpp b/libyul/optimiser/Substitution.cpp
new file mode 100644
index 00000000..eafe1da9
--- /dev/null
+++ b/libyul/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 <libyul/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/libyul/optimiser/Substitution.h b/libyul/optimiser/Substitution.h
new file mode 100644
index 00000000..c7e604ca
--- /dev/null
+++ b/libyul/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 <libyul/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;
+};
+
+}
+}
diff --git a/libyul/optimiser/SyntacticalEquality.cpp b/libyul/optimiser/SyntacticalEquality.cpp
new file mode 100644
index 00000000..a235e509
--- /dev/null
+++ b/libyul/optimiser/SyntacticalEquality.cpp
@@ -0,0 +1,76 @@
+/*(
+	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/>.
+*/
+/**
+ * Component that can compare ASTs for equality on a syntactic basis.
+ */
+
+#include <libyul/optimiser/SyntacticalEquality.h>
+
+#include <libyul/Exceptions.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+#include <libdevcore/CommonData.h>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+
+bool SyntacticalEqualityChecker::equal(Expression const& _e1, Expression const& _e2)
+{
+	if (_e1.type() != _e2.type())
+		return false;
+
+	// TODO This should be replaced by some kind of AST walker as soon as it gets
+	// more complex.
+	if (_e1.type() == typeid(FunctionalInstruction))
+	{
+		auto const& e1 = boost::get<FunctionalInstruction>(_e1);
+		auto const& e2 = boost::get<FunctionalInstruction>(_e2);
+		return
+			e1.instruction == e2.instruction &&
+			equalVector(e1.arguments, e2.arguments);
+	}
+	else if (_e1.type() == typeid(FunctionCall))
+	{
+		auto const& e1 = boost::get<FunctionCall>(_e1);
+		auto const& e2 = boost::get<FunctionCall>(_e2);
+		return
+			equal(e1.functionName, e2.functionName) &&
+			equalVector(e1.arguments, e2.arguments);
+	}
+	else if (_e1.type() == typeid(Identifier))
+		return boost::get<Identifier>(_e1).name == boost::get<Identifier>(_e2).name;
+	else if (_e1.type() == typeid(Literal))
+	{
+		auto const& e1 = boost::get<Literal>(_e1);
+		auto const& e2 = boost::get<Literal>(_e2);
+		return e1.kind == e2.kind && e1.value == e2.value && e1.type == e2.type;
+	}
+	else
+	{
+		assertThrow(false, OptimizerException, "Invalid expression");
+	}
+	return false;
+}
+
+bool SyntacticalEqualityChecker::equalVector(vector<Expression> const& _e1, vector<Expression> const& _e2)
+{
+	return _e1.size() == _e2.size() &&
+		std::equal(begin(_e1), end(_e1), begin(_e2), SyntacticalEqualityChecker::equal);
+
+}
diff --git a/libyul/optimiser/SyntacticalEquality.h b/libyul/optimiser/SyntacticalEquality.h
new file mode 100644
index 00000000..58d4f365
--- /dev/null
+++ b/libyul/optimiser/SyntacticalEquality.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/>.
+*/
+/**
+ * Component that can compare ASTs for equality on a syntactic basis.
+ */
+
+#pragma once
+
+#include <libyul/ASTDataForward.h>
+
+#include <vector>
+
+namespace dev
+{
+namespace julia
+{
+
+/**
+ * Component that can compare ASTs for equality on a syntactic basis.
+ * Ignores source locations but requires exact matches otherwise.
+ *
+ * TODO: Only implemented for Expressions for now.
+ * A future version might also recognize renamed variables and thus could be used to
+ * remove duplicate functions.
+ */
+class SyntacticalEqualityChecker
+{
+public:
+	static bool equal(Expression const& _e1, Expression const& _e2);
+
+protected:
+	static bool equalVector(std::vector<Expression> const& _e1, std::vector<Expression> const& _e2);
+};
+
+}
+}
diff --git a/libyul/optimiser/UnusedPruner.cpp b/libyul/optimiser/UnusedPruner.cpp
new file mode 100644
index 00000000..10b1c171
--- /dev/null
+++ b/libyul/optimiser/UnusedPruner.cpp
@@ -0,0 +1,117 @@
+/*(
+	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/>.
+*/
+/**
+ * Optimisation stage that removes unused variables and functions.
+ */
+
+#include <libyul/optimiser/UnusedPruner.h>
+
+#include <libyul/optimiser/NameCollector.h>
+#include <libyul/optimiser/Semantics.h>
+#include <libyul/optimiser/Utilities.h>
+#include <libyul/Exceptions.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+#include <boost/algorithm/cxx11/none_of.hpp>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+
+UnusedPruner::UnusedPruner(Block& _ast)
+{
+	ReferencesCounter counter;
+	counter(_ast);
+
+	m_references = counter.references();
+}
+
+void UnusedPruner::operator()(Block& _block)
+{
+	for (auto&& statement: _block.statements)
+		if (statement.type() == typeid(FunctionDefinition))
+		{
+			FunctionDefinition& funDef = boost::get<FunctionDefinition>(statement);
+			if (!used(funDef.name))
+			{
+				subtractReferences(ReferencesCounter::countReferences(funDef.body));
+				statement = Block{std::move(funDef.location), {}};
+			}
+		}
+		else if (statement.type() == typeid(VariableDeclaration))
+		{
+			VariableDeclaration& varDecl = boost::get<VariableDeclaration>(statement);
+			// Multi-variable declarations are special. We can only remove it
+			// if all vairables are unused and the right-hand-side is either
+			// movable or it return a single value. In the latter case, we
+			// replace `let a := f()` by `pop(f())` (in pure Yul, this will be
+			// `drop(f())`).
+			if (boost::algorithm::none_of(
+				varDecl.variables,
+				[=](TypedName const& _typedName) { return used(_typedName.name); }
+			))
+			{
+				if (!varDecl.value)
+					statement = Block{std::move(varDecl.location), {}};
+				else if (MovableChecker(*varDecl.value).movable())
+				{
+					subtractReferences(ReferencesCounter::countReferences(*varDecl.value));
+					statement = Block{std::move(varDecl.location), {}};
+				}
+				else if (varDecl.variables.size() == 1)
+					// In pure Yul, this should be replaced by a function call to `drop`
+					// instead of `pop`.
+					statement = ExpressionStatement{varDecl.location, FunctionalInstruction{
+						varDecl.location,
+						solidity::Instruction::POP,
+						{*std::move(varDecl.value)}
+					}};
+			}
+		}
+
+	removeEmptyBlocks(_block);
+
+	ASTModifier::operator()(_block);
+}
+
+void UnusedPruner::runUntilStabilised(Block& _ast)
+{
+	while (true)
+	{
+		UnusedPruner pruner(_ast);
+		pruner(_ast);
+		if (!pruner.shouldRunAgain())
+			return;
+	}
+}
+
+bool UnusedPruner::used(string const& _name) const
+{
+	return m_references.count(_name) && m_references.at(_name) > 0;
+}
+
+void UnusedPruner::subtractReferences(map<string, size_t> const& _subtrahend)
+{
+	for (auto const& ref: _subtrahend)
+	{
+		assertThrow(m_references.count(ref.first), OptimizerException, "");
+		assertThrow(m_references.at(ref.first) >= ref.second, OptimizerException, "");
+		m_references[ref.first] -= ref.second;
+		m_shouldRunAgain = true;
+	}
+}
diff --git a/libyul/optimiser/UnusedPruner.h b/libyul/optimiser/UnusedPruner.h
new file mode 100644
index 00000000..305c62a7
--- /dev/null
+++ b/libyul/optimiser/UnusedPruner.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/>.
+*/
+/**
+ * Optimisation stage that removes unused variables and functions.
+ */
+
+#pragma once
+
+#include <libyul/optimiser/ASTWalker.h>
+
+#include <string>
+#include <map>
+#include <set>
+
+namespace dev
+{
+namespace julia
+{
+
+/**
+ * Optimisation stage that removes unused variables and functions.
+ *
+ * TODO: Also remove intermediate variable assignments from movable expressions
+ * which are not referenced until after the next assignment to the same variable.
+ *
+ * Note that this does not remove circular references.
+ *
+ * Prerequisite: Disambiguator
+ */
+class UnusedPruner: public ASTModifier
+{
+public:
+	explicit UnusedPruner(Block& _ast);
+
+	using ASTModifier::operator();
+	virtual void operator()(Block& _block) override;
+
+	// @returns true iff the code changed in the previous run.
+	bool shouldRunAgain() const { return m_shouldRunAgain; }
+
+	// Run the pruner until the code does not change anymore.
+	static void runUntilStabilised(Block& _ast);
+
+private:
+	bool used(std::string const& _name) const;
+	void subtractReferences(std::map<std::string, size_t> const& _subtrahend);
+
+	bool m_shouldRunAgain = false;
+	std::map<std::string, size_t> m_references;
+};
+
+}
+}
diff --git a/libyul/optimiser/Utilities.cpp b/libyul/optimiser/Utilities.cpp
new file mode 100644
index 00000000..7591ed5b
--- /dev/null
+++ b/libyul/optimiser/Utilities.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/>.
+*/
+/**
+ * Some useful snippets for the optimiser.
+ */
+
+#include <libyul/optimiser/Utilities.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
+#include <libdevcore/CommonData.h>
+
+#include <boost/range/algorithm_ext/erase.hpp>
+
+using namespace std;
+using namespace dev;
+using namespace dev::julia;
+
+void dev::julia::removeEmptyBlocks(Block& _block)
+{
+	auto isEmptyBlock = [](Statement const& _st) -> bool {
+		return _st.type() == typeid(Block) && boost::get<Block>(_st).statements.empty();
+	};
+	boost::range::remove_erase_if(_block.statements, isEmptyBlock);
+}
diff --git a/libyul/optimiser/Utilities.h b/libyul/optimiser/Utilities.h
new file mode 100644
index 00000000..ae77d2e0
--- /dev/null
+++ b/libyul/optimiser/Utilities.h
@@ -0,0 +1,34 @@
+/*
+	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/>.
+*/
+/**
+ * Small useful snippets for the optimiser.
+ */
+
+#pragma once
+
+#include <libyul/ASTDataForward.h>
+
+namespace dev
+{
+namespace julia
+{
+
+/// Removes statements that are just empty blocks (non-recursive).
+void removeEmptyBlocks(Block& _block);
+
+}
+}