17 files changed, 482 insertions, 83 deletions
diff --git a/libsolidity/codegen/ABIFunctions.cpp b/libsolidity/codegen/ABIFunctions.cpp
index b02623de..c1ab03e3 100644
--- a/libsolidity/codegen/ABIFunctions.cpp
+++ b/libsolidity/codegen/ABIFunctions.cpp
@@ -24,7 +24,6 @@
 
 #include <libsolidity/ast/AST.h>
 #include <libsolidity/codegen/CompilerUtils.h>
-
 #include <libdevcore/Whiskers.h>
 
 #include <boost/algorithm/string/join.hpp>
@@ -141,8 +140,8 @@ string ABIFunctions::tupleDecoder(TypePointers const& _types, bool _fromMemory)
 			vector<string> valueNamesLocal;
 			for (size_t j = 0; j < sizeOnStack; j++)
 			{
-				valueNamesLocal.push_back("value" + to_string(stackPos));
-				valueReturnParams.push_back("value" + to_string(stackPos));
+				valueNamesLocal.emplace_back("value" + to_string(stackPos));
+				valueReturnParams.emplace_back("value" + to_string(stackPos));
 				stackPos++;
 			}
 			bool dynamic = decodingTypes[i]->isDynamicallyEncoded();
diff --git a/libsolidity/codegen/ABIFunctions.h b/libsolidity/codegen/ABIFunctions.h
index d2132258..1e0cf7fa 100644
--- a/libsolidity/codegen/ABIFunctions.h
+++ b/libsolidity/codegen/ABIFunctions.h
@@ -22,14 +22,13 @@
 
 #pragma once
 
-#include <liblangutil/EVMVersion.h>
-
 #include <libsolidity/ast/ASTForward.h>
+#include <liblangutil/EVMVersion.h>
 
-#include <vector>
 #include <functional>
-#include <set>
 #include <map>
+#include <set>
+#include <vector>
 
 namespace dev {
 namespace solidity {
diff --git a/libsolidity/codegen/ArrayUtils.cpp b/libsolidity/codegen/ArrayUtils.cpp
index 4878f9f3..f9678f7c 100644
--- a/libsolidity/codegen/ArrayUtils.cpp
+++ b/libsolidity/codegen/ArrayUtils.cpp
@@ -21,13 +21,15 @@
  */
 
 #include <libsolidity/codegen/ArrayUtils.h>
-#include <libevmasm/Instruction.h>
+
+#include <libsolidity/ast/Types.h>
 #include <libsolidity/codegen/CompilerContext.h>
 #include <libsolidity/codegen/CompilerUtils.h>
-#include <libsolidity/ast/Types.h>
-#include <liblangutil/Exceptions.h>
 #include <libsolidity/codegen/LValue.h>
 
+#include <libevmasm/Instruction.h>
+#include <liblangutil/Exceptions.h>
+
 using namespace std;
 using namespace dev;
 using namespace langutil;
diff --git a/libsolidity/codegen/AsmCodeGen.cpp b/libsolidity/codegen/AsmCodeGen.cpp
new file mode 100644
index 00000000..c04c1c34
--- /dev/null
+++ b/libsolidity/codegen/AsmCodeGen.cpp
@@ -0,0 +1,197 @@
+/*
+	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/>.
+*/
+/**
+ * Adaptor between the abstract assembly and eth assembly.
+ */
+
+#include <libsolidity/codegen/AsmCodeGen.h>
+
+#include <libyul/AsmData.h>
+#include <libyul/AsmAnalysisInfo.h>
+
+#include <libyul/backends/evm/AbstractAssembly.h>
+#include <libyul/backends/evm/EVMCodeTransform.h>
+
+#include <libevmasm/Assembly.h>
+#include <libevmasm/AssemblyItem.h>
+#include <libevmasm/Instruction.h>
+
+#include <liblangutil/SourceLocation.h>
+
+#include <libdevcore/FixedHash.h>
+
+#include <memory>
+#include <functional>
+
+using namespace std;
+using namespace dev;
+using namespace langutil;
+using namespace yul;
+using namespace dev::solidity;
+
+EthAssemblyAdapter::EthAssemblyAdapter(eth::Assembly& _assembly):
+	m_assembly(_assembly)
+{
+}
+
+void EthAssemblyAdapter::setSourceLocation(SourceLocation const& _location)
+{
+	m_assembly.setSourceLocation(_location);
+}
+
+int EthAssemblyAdapter::stackHeight() const
+{
+	return m_assembly.deposit();
+}
+
+void EthAssemblyAdapter::appendInstruction(solidity::Instruction _instruction)
+{
+	m_assembly.append(_instruction);
+}
+
+void EthAssemblyAdapter::appendConstant(u256 const& _constant)
+{
+	m_assembly.append(_constant);
+}
+
+void EthAssemblyAdapter::appendLabel(LabelID _labelId)
+{
+	m_assembly.append(eth::AssemblyItem(eth::Tag, _labelId));
+}
+
+void EthAssemblyAdapter::appendLabelReference(LabelID _labelId)
+{
+	m_assembly.append(eth::AssemblyItem(eth::PushTag, _labelId));
+}
+
+size_t EthAssemblyAdapter::newLabelId()
+{
+	return assemblyTagToIdentifier(m_assembly.newTag());
+}
+
+size_t EthAssemblyAdapter::namedLabel(std::string const& _name)
+{
+	return assemblyTagToIdentifier(m_assembly.namedTag(_name));
+}
+
+void EthAssemblyAdapter::appendLinkerSymbol(std::string const& _linkerSymbol)
+{
+	m_assembly.appendLibraryAddress(_linkerSymbol);
+}
+
+void EthAssemblyAdapter::appendJump(int _stackDiffAfter)
+{
+	appendInstruction(solidity::Instruction::JUMP);
+	m_assembly.adjustDeposit(_stackDiffAfter);
+}
+
+void EthAssemblyAdapter::appendJumpTo(LabelID _labelId, int _stackDiffAfter)
+{
+	appendLabelReference(_labelId);
+	appendJump(_stackDiffAfter);
+}
+
+void EthAssemblyAdapter::appendJumpToIf(LabelID _labelId)
+{
+	appendLabelReference(_labelId);
+	appendInstruction(solidity::Instruction::JUMPI);
+}
+
+void EthAssemblyAdapter::appendBeginsub(LabelID, int)
+{
+	// TODO we could emulate that, though
+	solAssert(false, "BEGINSUB not implemented for EVM 1.0");
+}
+
+void EthAssemblyAdapter::appendJumpsub(LabelID, int, int)
+{
+	// TODO we could emulate that, though
+	solAssert(false, "JUMPSUB not implemented for EVM 1.0");
+}
+
+void EthAssemblyAdapter::appendReturnsub(int, int)
+{
+	// TODO we could emulate that, though
+	solAssert(false, "RETURNSUB not implemented for EVM 1.0");
+}
+
+void EthAssemblyAdapter::appendAssemblySize()
+{
+	m_assembly.appendProgramSize();
+}
+
+pair<shared_ptr<AbstractAssembly>, AbstractAssembly::SubID> EthAssemblyAdapter::createSubAssembly()
+{
+	shared_ptr<eth::Assembly> assembly{make_shared<eth::Assembly>()};
+	auto sub = m_assembly.newSub(assembly);
+	return {make_shared<EthAssemblyAdapter>(*assembly), size_t(sub.data())};
+}
+
+void EthAssemblyAdapter::appendDataOffset(AbstractAssembly::SubID _sub)
+{
+	auto it = m_dataHashBySubId.find(_sub);
+	if (it == m_dataHashBySubId.end())
+		m_assembly.pushSubroutineOffset(size_t(_sub));
+	else
+		m_assembly << eth::AssemblyItem(eth::PushData, it->second);
+}
+
+void EthAssemblyAdapter::appendDataSize(AbstractAssembly::SubID _sub)
+{
+	auto it = m_dataHashBySubId.find(_sub);
+	if (it == m_dataHashBySubId.end())
+		m_assembly.pushSubroutineSize(size_t(_sub));
+	else
+		m_assembly << u256(m_assembly.data(h256(it->second)).size());
+}
+
+AbstractAssembly::SubID EthAssemblyAdapter::appendData(bytes const& _data)
+{
+	eth::AssemblyItem pushData = m_assembly.newData(_data);
+	SubID subID = m_nextDataCounter++;
+	m_dataHashBySubId[subID] = pushData.data();
+	return subID;
+}
+
+EthAssemblyAdapter::LabelID EthAssemblyAdapter::assemblyTagToIdentifier(eth::AssemblyItem const& _tag)
+{
+	u256 id = _tag.data();
+	solAssert(id <= std::numeric_limits<LabelID>::max(), "Tag id too large.");
+	return LabelID(id);
+}
+
+void CodeGenerator::assemble(
+	Block const& _parsedData,
+	AsmAnalysisInfo& _analysisInfo,
+	eth::Assembly& _assembly,
+	ExternalIdentifierAccess const& _identifierAccess,
+	bool _useNamedLabelsForFunctions,
+	bool _optimize
+)
+{
+	EthAssemblyAdapter assemblyAdapter(_assembly);
+	CodeTransform(
+		assemblyAdapter,
+		_analysisInfo,
+		_parsedData,
+		*EVMDialect::strictAssemblyForEVM(),
+		_optimize,
+		false,
+		_identifierAccess,
+		_useNamedLabelsForFunctions
+	)(_parsedData);
+}
diff --git a/libsolidity/codegen/AsmCodeGen.h b/libsolidity/codegen/AsmCodeGen.h
new file mode 100644
index 00000000..516b0a36
--- /dev/null
+++ b/libsolidity/codegen/AsmCodeGen.h
@@ -0,0 +1,92 @@
+/*
+	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/>.
+*/
+/**
+ * Adaptor between the abstract assembly and eth assembly.
+ */
+
+#pragma once
+
+#include <libyul/AsmAnalysis.h>
+#include <libyul/backends/evm/AbstractAssembly.h>
+#include <liblangutil/SourceLocation.h>
+#include <functional>
+
+namespace yul
+{
+struct Block;
+}
+
+namespace dev
+{
+namespace eth
+{
+class Assembly;
+class AssemblyItem;
+}
+
+namespace solidity
+{
+
+class EthAssemblyAdapter: public yul::AbstractAssembly
+{
+public:
+	explicit EthAssemblyAdapter(eth::Assembly& _assembly);
+	void setSourceLocation(langutil::SourceLocation const& _location) override;
+	int stackHeight() const override;
+	void appendInstruction(solidity::Instruction _instruction) override;
+	void appendConstant(u256 const& _constant) override;
+	void appendLabel(LabelID _labelId) override;
+	void appendLabelReference(LabelID _labelId) override;
+	size_t newLabelId() override;
+	size_t namedLabel(std::string const& _name) override;
+	void appendLinkerSymbol(std::string const& _linkerSymbol) override;
+	void appendJump(int _stackDiffAfter) override;
+	void appendJumpTo(LabelID _labelId, int _stackDiffAfter) override;
+	void appendJumpToIf(LabelID _labelId) override;
+	void appendBeginsub(LabelID, int) override;
+	void appendJumpsub(LabelID, int, int) override;
+	void appendReturnsub(int, int) override;
+	void appendAssemblySize() override;
+	std::pair<std::shared_ptr<AbstractAssembly>, SubID> createSubAssembly() override;
+	void appendDataOffset(SubID _sub) override;
+	void appendDataSize(SubID _sub) override;
+	SubID appendData(dev::bytes const& _data) override;
+
+private:
+	static LabelID assemblyTagToIdentifier(eth::AssemblyItem const& _tag);
+
+	eth::Assembly& m_assembly;
+	std::map<SubID, dev::u256> m_dataHashBySubId;
+	size_t m_nextDataCounter = std::numeric_limits<size_t>::max() / 2;
+};
+
+class CodeGenerator
+{
+public:
+	/// Performs code generation and appends generated to _assembly.
+	static void assemble(
+		yul::Block const& _parsedData,
+		yul::AsmAnalysisInfo& _analysisInfo,
+		dev::eth::Assembly& _assembly,
+		yul::ExternalIdentifierAccess const& _identifierAccess = yul::ExternalIdentifierAccess(),
+		bool _useNamedLabelsForFunctions = false,
+		bool _optimize = false
+	);
+};
+
+}
+}
diff --git a/libsolidity/codegen/Compiler.cpp b/libsolidity/codegen/Compiler.cpp
index 55f1d252..a22e6e9d 100644
--- a/libsolidity/codegen/Compiler.cpp
+++ b/libsolidity/codegen/Compiler.cpp
@@ -21,8 +21,9 @@
  */
 
 #include <libsolidity/codegen/Compiler.h>
-#include <libevmasm/Assembly.h>
+
 #include <libsolidity/codegen/ContractCompiler.h>
+#include <libevmasm/Assembly.h>
 
 using namespace std;
 using namespace dev;
@@ -34,13 +35,13 @@ void Compiler::compileContract(
 	bytes const& _metadata
 )
 {
-	ContractCompiler runtimeCompiler(nullptr, m_runtimeContext, m_optimize);
+	ContractCompiler runtimeCompiler(nullptr, m_runtimeContext, m_optimize, m_optimizeRuns);
 	runtimeCompiler.compileContract(_contract, _contracts);
 	m_runtimeContext.appendAuxiliaryData(_metadata);
 
 	// This might modify m_runtimeContext because it can access runtime functions at
 	// creation time.
-	ContractCompiler creationCompiler(&runtimeCompiler, m_context, m_optimize);
+	ContractCompiler creationCompiler(&runtimeCompiler, m_context, m_optimize, 1);
 	m_runtimeSub = creationCompiler.compileConstructor(_contract, _contracts);
 
 	m_context.optimise(m_optimize, m_optimizeRuns);
diff --git a/libsolidity/codegen/Compiler.h b/libsolidity/codegen/Compiler.h
index 48d9e9d6..784d7f8c 100644
--- a/libsolidity/codegen/Compiler.h
+++ b/libsolidity/codegen/Compiler.h
@@ -24,11 +24,9 @@
 
 #include <libsolidity/codegen/CompilerContext.h>
 #include <liblangutil/EVMVersion.h>
-
 #include <libevmasm/Assembly.h>
-
-#include <ostream>
 #include <functional>
+#include <ostream>
 
 namespace dev {
 namespace solidity {
diff --git a/libsolidity/codegen/CompilerContext.cpp b/libsolidity/codegen/CompilerContext.cpp
index 5a3a233c..be681b2e 100644
--- a/libsolidity/codegen/CompilerContext.cpp
+++ b/libsolidity/codegen/CompilerContext.cpp
@@ -21,18 +21,22 @@
  */
 
 #include <libsolidity/codegen/CompilerContext.h>
-#include <libsolidity/codegen/CompilerUtils.h>
+
 #include <libsolidity/ast/AST.h>
+#include <libsolidity/codegen/AsmCodeGen.h>
 #include <libsolidity/codegen/Compiler.h>
+#include <libsolidity/codegen/CompilerUtils.h>
 #include <libsolidity/interface/Version.h>
-#include <liblangutil/SourceReferenceFormatter.h>
+
 #include <libyul/AsmParser.h>
-#include <libyul/AsmCodeGen.h>
 #include <libyul/AsmAnalysis.h>
 #include <libyul/AsmAnalysisInfo.h>
+#include <libyul/backends/evm/EVMDialect.h>
 #include <libyul/YulString.h>
+
 #include <liblangutil/ErrorReporter.h>
 #include <liblangutil/Scanner.h>
+#include <liblangutil/SourceReferenceFormatter.h>
 
 #include <boost/algorithm/string/replace.hpp>
 
@@ -361,7 +365,7 @@ void CompilerContext::appendInlineAssembly(
 	ErrorList errors;
 	ErrorReporter errorReporter(errors);
 	auto scanner = make_shared<langutil::Scanner>(langutil::CharStream(_assembly, "--CODEGEN--"));
-	auto parserResult = yul::Parser(errorReporter, yul::AsmFlavour::Strict).parse(scanner, false);
+	auto parserResult = yul::Parser(errorReporter, yul::EVMDialect::strictAssemblyForEVM()).parse(scanner, false);
 #ifdef SOL_OUTPUT_ASM
 	cout << yul::AsmPrinter()(*parserResult) << endl;
 #endif
@@ -373,7 +377,7 @@ void CompilerContext::appendInlineAssembly(
 			errorReporter,
 			m_evmVersion,
 			boost::none,
-			yul::AsmFlavour::Strict,
+			yul::EVMDialect::strictAssemblyForEVM(),
 			identifierAccess.resolve
 		).analyze(*parserResult);
 	if (!parserResult || !errorReporter.errors().empty() || !analyzerResult)
@@ -386,8 +390,7 @@ void CompilerContext::appendInlineAssembly(
 		for (auto const& error: errorReporter.errors())
 			message += SourceReferenceFormatter::formatExceptionInformation(
 				*error,
-				(error->type() == Error::Type::Warning) ? "Warning" : "Error",
-				[&](string const&) -> Scanner const& { return *scanner; }
+				(error->type() == Error::Type::Warning) ? "Warning" : "Error"
 			);
 		message += "-------------------------------------------\n";
 
@@ -395,7 +398,7 @@ void CompilerContext::appendInlineAssembly(
 	}
 
 	solAssert(errorReporter.errors().empty(), "Failed to analyze inline assembly block.");
-	yul::CodeGenerator::assemble(*parserResult, analysisInfo, *m_asm, identifierAccess, _system);
+	CodeGenerator::assemble(*parserResult, analysisInfo, *m_asm, identifierAccess, _system);
 
 	// Reset the source location to the one of the node (instead of the CODEGEN source location)
 	updateSourceLocation();
diff --git a/libsolidity/codegen/CompilerContext.h b/libsolidity/codegen/CompilerContext.h
index 02369813..dedcd95f 100644
--- a/libsolidity/codegen/CompilerContext.h
+++ b/libsolidity/codegen/CompilerContext.h
@@ -22,24 +22,21 @@
 
 #pragma once
 
-#include <libsolidity/codegen/ABIFunctions.h>
-
-#include <liblangutil/EVMVersion.h>
-
+#include <libsolidity/ast/ASTAnnotations.h>
 #include <libsolidity/ast/ASTForward.h>
 #include <libsolidity/ast/Types.h>
-#include <libsolidity/ast/ASTAnnotations.h>
+#include <libsolidity/codegen/ABIFunctions.h>
 
-#include <libevmasm/Instruction.h>
 #include <libevmasm/Assembly.h>
-
+#include <libevmasm/Instruction.h>
+#include <liblangutil/EVMVersion.h>
 #include <libdevcore/Common.h>
 
+#include <functional>
 #include <ostream>
 #include <stack>
 #include <queue>
 #include <utility>
-#include <functional>
 
 namespace dev {
 namespace solidity {
diff --git a/libsolidity/codegen/CompilerUtils.cpp b/libsolidity/codegen/CompilerUtils.cpp
index 7d2ad9d2..bbc703c7 100644
--- a/libsolidity/codegen/CompilerUtils.cpp
+++ b/libsolidity/codegen/CompilerUtils.cpp
@@ -23,12 +23,10 @@
 #include <libsolidity/codegen/CompilerUtils.h>
 
 #include <libsolidity/ast/AST.h>
+#include <libsolidity/codegen/ABIFunctions.h>
 #include <libsolidity/codegen/ArrayUtils.h>
 #include <libsolidity/codegen/LValue.h>
-#include <libsolidity/codegen/ABIFunctions.h>
-
 #include <libevmasm/Instruction.h>
-
 #include <libdevcore/Whiskers.h>
 
 using namespace std;
@@ -1205,7 +1203,7 @@ void CompilerUtils::storeStringData(bytesConstRef _data)
 {
 	//@todo provide both alternatives to the optimiser
 	// stack: mempos
-	if (_data.size() <= 128)
+	if (_data.size() <= 32)
 	{
 		for (unsigned i = 0; i < _data.size(); i += 32)
 		{
diff --git a/libsolidity/codegen/CompilerUtils.h b/libsolidity/codegen/CompilerUtils.h
index 5f7dce22..7e4f47ba 100644
--- a/libsolidity/codegen/CompilerUtils.h
+++ b/libsolidity/codegen/CompilerUtils.h
@@ -22,8 +22,8 @@
 
 #pragma once
 
-#include <libsolidity/codegen/CompilerContext.h>
 #include <libsolidity/ast/ASTForward.h>
+#include <libsolidity/codegen/CompilerContext.h>
 
 namespace dev {
 namespace solidity {
diff --git a/libsolidity/codegen/ContractCompiler.cpp b/libsolidity/codegen/ContractCompiler.cpp
index aabdbb79..b051d260 100644
--- a/libsolidity/codegen/ContractCompiler.cpp
+++ b/libsolidity/codegen/ContractCompiler.cpp
@@ -20,19 +20,18 @@
  * Solidity compiler.
  */
 
+#include <libsolidity/ast/AST.h>
+#include <libsolidity/codegen/AsmCodeGen.h>
+#include <libsolidity/codegen/CompilerUtils.h>
 #include <libsolidity/codegen/ContractCompiler.h>
 #include <libsolidity/codegen/ExpressionCompiler.h>
-#include <libsolidity/codegen/CompilerUtils.h>
-#include <libsolidity/ast/AST.h>
-#include <libyul/AsmCodeGen.h>
-#include <liblangutil/ErrorReporter.h>
 
 #include <libevmasm/Instruction.h>
 #include <libevmasm/Assembly.h>
 #include <libevmasm/GasMeter.h>
+#include <liblangutil/ErrorReporter.h>
 
 #include <boost/range/adaptor/reversed.hpp>
-
 #include <algorithm>
 
 using namespace std;
@@ -268,6 +267,89 @@ void ContractCompiler::appendDelegatecallCheck()
 	// "We have not been called via DELEGATECALL".
 }
 
+void ContractCompiler::appendInternalSelector(
+	map<FixedHash<4>, eth::AssemblyItem const> const& _entryPoints,
+	vector<FixedHash<4>> const& _ids,
+	eth::AssemblyItem const& _notFoundTag,
+	size_t _runs
+)
+{
+	// Code for selecting from n functions without split:
+	//   n times: dup1, push4 <id_i>, eq, push2/3 <tag_i>, jumpi
+	//   push2/3 <notfound> jump
+	// (called SELECT[n])
+	// Code for selecting from n functions with split:
+	//   dup1, push4 <pivot>, gt, push2/3<tag_less>, jumpi
+	//     SELECT[n/2]
+	//   tag_less:
+	//     SELECT[n/2]
+	//
+	// This means each split adds 16-18 bytes of additional code (note the additional jump out!)
+	// The average execution cost if we do not split at all are:
+	//   (3 + 3 + 3 + 3 + 10) * n/2 = 24 * n/2 = 12 * n
+	// If we split once:
+	//    (3 + 3 + 3 + 3 + 10) + 24 * n/4 = 24 * (n/4 + 1) = 6 * n + 24;
+	//
+	// We should split if
+	//     _runs * 12 * n > _runs * (6 * n + 24) + 17 * createDataGas
+	// <=> _runs * 6 * (n - 4) > 17 * createDataGas
+	//
+	// Which also means that the execution itself is not profitable
+	// unless we have at least 5 functions.
+
+	// Start with some comparisons to avoid overflow, then do the actual comparison.
+	bool split = false;
+	if (_ids.size() <= 4)
+		split = false;
+	else if (_runs > (17 * eth::GasCosts::createDataGas) / 6)
+		split = true;
+	else
+		split = (_runs * 6 * (_ids.size() - 4) > 17 * eth::GasCosts::createDataGas);
+
+	if (split)
+	{
+		size_t pivotIndex = _ids.size() / 2;
+		FixedHash<4> pivot{_ids.at(pivotIndex)};
+		m_context << dupInstruction(1) << u256(FixedHash<4>::Arith(pivot)) << Instruction::GT;
+		eth::AssemblyItem lessTag{m_context.appendConditionalJump()};
+		// Here, we have funid >= pivot
+		vector<FixedHash<4>> larger{_ids.begin() + pivotIndex, _ids.end()};
+		appendInternalSelector(_entryPoints, larger, _notFoundTag, _runs);
+		m_context << lessTag;
+		// Here, we have funid < pivot
+		vector<FixedHash<4>> smaller{_ids.begin(), _ids.begin() + pivotIndex};
+		appendInternalSelector(_entryPoints, smaller, _notFoundTag, _runs);
+	}
+	else
+	{
+		for (auto const& id: _ids)
+		{
+			m_context << dupInstruction(1) << u256(FixedHash<4>::Arith(id)) << Instruction::EQ;
+			m_context.appendConditionalJumpTo(_entryPoints.at(id));
+		}
+		m_context.appendJumpTo(_notFoundTag);
+	}
+}
+
+namespace
+{
+
+// Helper function to check if any function is payable
+bool hasPayableFunctions(ContractDefinition const& _contract)
+{
+	FunctionDefinition const* fallback = _contract.fallbackFunction();
+	if (fallback && fallback->isPayable())
+		return true;
+
+	for (auto const& it: _contract.interfaceFunctions())
+		if (it.second->isPayable())
+			return true;
+
+	return false;
+}
+
+}
+
 void ContractCompiler::appendFunctionSelector(ContractDefinition const& _contract)
 {
 	map<FixedHash<4>, FunctionTypePointer> interfaceFunctions = _contract.interfaceFunctions();
@@ -279,6 +361,15 @@ void ContractCompiler::appendFunctionSelector(ContractDefinition const& _contrac
 	}
 
 	FunctionDefinition const* fallback = _contract.fallbackFunction();
+	solAssert(!_contract.isLibrary() || !fallback, "Libraries can't have fallback functions");
+
+	bool needToAddCallvalueCheck = true;
+	if (!hasPayableFunctions(_contract) && !interfaceFunctions.empty() && !_contract.isLibrary())
+	{
+		appendCallValueCheck();
+		needToAddCallvalueCheck = false;
+	}
+
 	eth::AssemblyItem notFound = m_context.newTag();
 	// directly jump to fallback if the data is too short to contain a function selector
 	// also guards against short data
@@ -287,22 +378,26 @@ void ContractCompiler::appendFunctionSelector(ContractDefinition const& _contrac
 
 	// retrieve the function signature hash from the calldata
 	if (!interfaceFunctions.empty())
+	{
 		CompilerUtils(m_context).loadFromMemory(0, IntegerType(CompilerUtils::dataStartOffset * 8), true);
 
-	// stack now is: <can-call-non-view-functions>? <funhash>
-	for (auto const& it: interfaceFunctions)
-	{
-		callDataUnpackerEntryPoints.insert(std::make_pair(it.first, m_context.newTag()));
-		m_context << dupInstruction(1) << u256(FixedHash<4>::Arith(it.first)) << Instruction::EQ;
-		m_context.appendConditionalJumpTo(callDataUnpackerEntryPoints.at(it.first));
+		// stack now is: <can-call-non-view-functions>? <funhash>
+		vector<FixedHash<4>> sortedIDs;
+		for (auto const& it: interfaceFunctions)
+		{
+			callDataUnpackerEntryPoints.emplace(it.first, m_context.newTag());
+			sortedIDs.emplace_back(it.first);
+		}
+		std::sort(sortedIDs.begin(), sortedIDs.end());
+		appendInternalSelector(callDataUnpackerEntryPoints, sortedIDs, notFound, m_optimise_runs);
 	}
-	m_context.appendJumpTo(notFound);
 
 	m_context << notFound;
+
 	if (fallback)
 	{
 		solAssert(!_contract.isLibrary(), "");
-		if (!fallback->isPayable())
+		if (!fallback->isPayable() && needToAddCallvalueCheck)
 			appendCallValueCheck();
 
 		solAssert(fallback->isFallback(), "");
@@ -332,7 +427,7 @@ void ContractCompiler::appendFunctionSelector(ContractDefinition const& _contrac
 		m_context.setStackOffset(0);
 		// We have to allow this for libraries, because value of the previous
 		// call is still visible in the delegatecall.
-		if (!functionType->isPayable() && !_contract.isLibrary())
+		if (!functionType->isPayable() && !_contract.isLibrary() && needToAddCallvalueCheck)
 			appendCallValueCheck();
 
 		// Return tag is used to jump out of the function.
@@ -618,7 +713,7 @@ bool ContractCompiler::visit(InlineAssembly const& _inlineAssembly)
 		}
 	};
 	solAssert(_inlineAssembly.annotation().analysisInfo, "");
-	yul::CodeGenerator::assemble(
+	CodeGenerator::assemble(
 		_inlineAssembly.operations(),
 		*_inlineAssembly.annotation().analysisInfo,
 		m_context.nonConstAssembly(),
@@ -656,14 +751,14 @@ bool ContractCompiler::visit(WhileStatement const& _whileStatement)
 
 	eth::AssemblyItem loopStart = m_context.newTag();
 	eth::AssemblyItem loopEnd = m_context.newTag();
-	m_breakTags.push_back({loopEnd, m_context.stackHeight()});
+	m_breakTags.emplace_back(loopEnd, m_context.stackHeight());
 
 	m_context << loopStart;
 
 	if (_whileStatement.isDoWhile())
 	{
 		eth::AssemblyItem condition = m_context.newTag();
-		m_continueTags.push_back({condition, m_context.stackHeight()});
+		m_continueTags.emplace_back(condition, m_context.stackHeight());
 
 		_whileStatement.body().accept(*this);
 
@@ -674,7 +769,7 @@ bool ContractCompiler::visit(WhileStatement const& _whileStatement)
 	}
 	else
 	{
-		m_continueTags.push_back({loopStart, m_context.stackHeight()});
+		m_continueTags.emplace_back(loopStart, m_context.stackHeight());
 		compileExpression(_whileStatement.condition());
 		m_context << Instruction::ISZERO;
 		m_context.appendConditionalJumpTo(loopEnd);
@@ -705,8 +800,8 @@ bool ContractCompiler::visit(ForStatement const& _forStatement)
 	if (_forStatement.initializationExpression())
 		_forStatement.initializationExpression()->accept(*this);
 
-	m_breakTags.push_back({loopEnd, m_context.stackHeight()});
-	m_continueTags.push_back({loopNext, m_context.stackHeight()});
+	m_breakTags.emplace_back(loopEnd, m_context.stackHeight());
+	m_continueTags.emplace_back(loopNext, m_context.stackHeight());
 	m_context << loopStart;
 
 	// if there is no terminating condition in for, default is to always be true
@@ -932,7 +1027,7 @@ void ContractCompiler::appendModifierOrFunctionCode()
 
 	if (codeBlock)
 	{
-		m_returnTags.push_back({m_context.newTag(), m_context.stackHeight()});
+		m_returnTags.emplace_back(m_context.newTag(), m_context.stackHeight());
 		codeBlock->accept(*this);
 
 		solAssert(!m_returnTags.empty(), "");
diff --git a/libsolidity/codegen/ContractCompiler.h b/libsolidity/codegen/ContractCompiler.h
index 001aec7c..40871f0d 100644
--- a/libsolidity/codegen/ContractCompiler.h
+++ b/libsolidity/codegen/ContractCompiler.h
@@ -22,11 +22,11 @@
 
 #pragma once
 
-#include <ostream>
-#include <functional>
 #include <libsolidity/ast/ASTVisitor.h>
 #include <libsolidity/codegen/CompilerContext.h>
 #include <libevmasm/Assembly.h>
+#include <functional>
+#include <ostream>
 
 namespace dev {
 namespace solidity {
@@ -38,8 +38,9 @@ namespace solidity {
 class ContractCompiler: private ASTConstVisitor
 {
 public:
-	explicit ContractCompiler(ContractCompiler* _runtimeCompiler, CompilerContext& _context, bool _optimise):
+	explicit ContractCompiler(ContractCompiler* _runtimeCompiler, CompilerContext& _context, bool _optimise, size_t _optimise_runs = 200):
 		m_optimise(_optimise),
+		m_optimise_runs(_optimise_runs),
 		m_runtimeCompiler(_runtimeCompiler),
 		m_context(_context)
 	{
@@ -81,6 +82,14 @@ private:
 	/// This is done by inserting a specific push constant as the first instruction
 	/// whose data will be modified in memory at deploy time.
 	void appendDelegatecallCheck();
+	/// Appends the function selector. Is called recursively to create a binary search tree.
+	/// @a _runs the number of intended executions of the contract to tune the split point.
+	void appendInternalSelector(
+		std::map<FixedHash<4>, eth::AssemblyItem const> const& _entryPoints,
+		std::vector<FixedHash<4>> const& _ids,
+		eth::AssemblyItem const& _notFoundTag,
+		size_t _runs
+	);
 	void appendFunctionSelector(ContractDefinition const& _contract);
 	void appendCallValueCheck();
 	void appendReturnValuePacker(TypePointers const& _typeParameters, bool _isLibrary);
@@ -122,6 +131,7 @@ private:
 	void storeStackHeight(ASTNode const* _node);
 
 	bool const m_optimise;
+	size_t const m_optimise_runs = 200;
 	/// Pointer to the runtime compiler in case this is a creation compiler.
 	ContractCompiler* m_runtimeCompiler = nullptr;
 	CompilerContext& m_context;
diff --git a/libsolidity/codegen/ExpressionCompiler.cpp b/libsolidity/codegen/ExpressionCompiler.cpp
index 121585d9..be2709ae 100644
--- a/libsolidity/codegen/ExpressionCompiler.cpp
+++ b/libsolidity/codegen/ExpressionCompiler.cpp
@@ -20,21 +20,23 @@
  * Solidity AST to EVM bytecode compiler for expressions.
  */
 
-#include <utility>
-#include <numeric>
-#include <boost/range/adaptor/reversed.hpp>
-#include <boost/algorithm/string/replace.hpp>
-#include <libdevcore/Common.h>
-#include <libdevcore/Keccak256.h>
-#include <libsolidity/ast/AST.h>
 #include <libsolidity/codegen/ExpressionCompiler.h>
+
+#include <libsolidity/ast/AST.h>
 #include <libsolidity/codegen/CompilerContext.h>
 #include <libsolidity/codegen/CompilerUtils.h>
 #include <libsolidity/codegen/LValue.h>
-#include <libevmasm/GasMeter.h>
 
+#include <libevmasm/GasMeter.h>
+#include <libdevcore/Common.h>
+#include <libdevcore/Keccak256.h>
 #include <libdevcore/Whiskers.h>
 
+#include <boost/algorithm/string/replace.hpp>
+#include <boost/range/adaptor/reversed.hpp>
+#include <numeric>
+#include <utility>
+
 using namespace std;
 using namespace langutil;
 
@@ -833,10 +835,12 @@ bool ExpressionCompiler::visit(FunctionCall const& _functionCall)
 		case FunctionType::Kind::RIPEMD160:
 		{
 			_functionCall.expression().accept(*this);
-			static const map<FunctionType::Kind, u256> contractAddresses{{FunctionType::Kind::ECRecover, 1},
-															   {FunctionType::Kind::SHA256, 2},
-															   {FunctionType::Kind::RIPEMD160, 3}};
-			m_context << contractAddresses.find(function.kind())->second;
+			static map<FunctionType::Kind, u256> const contractAddresses{
+				{FunctionType::Kind::ECRecover, 1},
+				{FunctionType::Kind::SHA256, 2},
+				{FunctionType::Kind::RIPEMD160, 3}
+			};
+			m_context << contractAddresses.at(function.kind());
 			for (unsigned i = function.sizeOnStack(); i > 0; --i)
 				m_context << swapInstruction(i);
 			appendExternalFunctionCall(function, arguments);
diff --git a/libsolidity/codegen/ExpressionCompiler.h b/libsolidity/codegen/ExpressionCompiler.h
index 2bfaab43..4a6e43ff 100644
--- a/libsolidity/codegen/ExpressionCompiler.h
+++ b/libsolidity/codegen/ExpressionCompiler.h
@@ -21,14 +21,17 @@
  * Solidity AST to EVM bytecode compiler for expressions.
  */
 
-#include <functional>
-#include <memory>
-#include <boost/noncopyable.hpp>
-#include <libdevcore/Common.h>
-#include <liblangutil/SourceLocation.h>
+#pragma once
+
 #include <libsolidity/ast/ASTVisitor.h>
 #include <libsolidity/codegen/LValue.h>
 #include <liblangutil/Exceptions.h>
+#include <liblangutil/SourceLocation.h>
+#include <libdevcore/Common.h>
+
+#include <boost/noncopyable.hpp>
+#include <functional>
+#include <memory>
 
 namespace dev {
 namespace eth
diff --git a/libsolidity/codegen/LValue.cpp b/libsolidity/codegen/LValue.cpp
index 6d71d36f..70dbee81 100644
--- a/libsolidity/codegen/LValue.cpp
+++ b/libsolidity/codegen/LValue.cpp
@@ -21,10 +21,11 @@
  */
 
 #include <libsolidity/codegen/LValue.h>
-#include <libevmasm/Instruction.h>
-#include <libsolidity/ast/Types.h>
+
 #include <libsolidity/ast/AST.h>
+#include <libsolidity/ast/Types.h>
 #include <libsolidity/codegen/CompilerUtils.h>
+#include <libevmasm/Instruction.h>
 
 using namespace std;
 using namespace dev;
diff --git a/libsolidity/codegen/LValue.h b/libsolidity/codegen/LValue.h
index d854857b..3072ff11 100644
--- a/libsolidity/codegen/LValue.h
+++ b/libsolidity/codegen/LValue.h
@@ -22,10 +22,10 @@
 
 #pragma once
 
+#include <libsolidity/codegen/ArrayUtils.h>
+#include <liblangutil/SourceLocation.h>
 #include <memory>
 #include <vector>
-#include <liblangutil/SourceLocation.h>
-#include <libsolidity/codegen/ArrayUtils.h>
 
 namespace dev
 {
@@ -49,7 +49,7 @@ protected:
 		m_context(_compilerContext), m_dataType(_dataType) {}
 
 public:
-	virtual ~LValue() {}
+	virtual ~LValue() = default;
 	/// @returns the number of stack slots occupied by the lvalue reference
 	virtual unsigned sizeOnStack() const { return 1; }
 	/// Copies the value of the current lvalue to the top of the stack and, if @a _remove is true,