Merge pull request #4936 from ethereum/binSelect

Binary search for dispatch.

10 files changed, 276 insertions, 6 deletions

diff --git a/Changelog.md b/Changelog.md
index 2acd60c8..cf3cf9e2 100644
--- a/Changelog.md
+++ b/Changelog.md
@@ -5,6 +5,7 @@ Language Features:
 
 Compiler Features:
  * Inline Assembly: Improve error messages around invalid function argument count.
+ * Code Generator: Use binary search for dispatch function if more efficient. The size/speed tradeoff can be tuned using ``--optimize-runs``.
 
 
 Bugfixes:
diff --git a/libsolidity/codegen/Compiler.cpp b/libsolidity/codegen/Compiler.cpp
index 55f1d252..fe57cff6 100644
--- a/libsolidity/codegen/Compiler.cpp
+++ b/libsolidity/codegen/Compiler.cpp
@@ -34,13 +34,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/ContractCompiler.cpp b/libsolidity/codegen/ContractCompiler.cpp
index ec55ae9b..79c53a1c 100644
--- a/libsolidity/codegen/ContractCompiler.cpp
+++ b/libsolidity/codegen/ContractCompiler.cpp
@@ -268,6 +268,70 @@ 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);
+	}
+}
+
 void ContractCompiler::appendFunctionSelector(ContractDefinition const& _contract)
 {
 	map<FixedHash<4>, FunctionTypePointer> interfaceFunctions = _contract.interfaceFunctions();
@@ -290,13 +354,14 @@ void ContractCompiler::appendFunctionSelector(ContractDefinition const& _contrac
 		CompilerUtils(m_context).loadFromMemory(0, IntegerType(CompilerUtils::dataStartOffset * 8), true);
 
 	// stack now is: <can-call-non-view-functions>? <funhash>
+	vector<FixedHash<4>> sortedIDs;
 	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));
+		sortedIDs.emplace_back(it.first);
 	}
-	m_context.appendJumpTo(notFound);
+	std::sort(sortedIDs.begin(), sortedIDs.end());
+	appendInternalSelector(callDataUnpackerEntryPoints, sortedIDs, notFound, m_optimise_runs);
 
 	m_context << notFound;
 	if (fallback)
diff --git a/libsolidity/codegen/ContractCompiler.h b/libsolidity/codegen/ContractCompiler.h
index 001aec7c..266ace0b 100644
--- a/libsolidity/codegen/ContractCompiler.h
+++ b/libsolidity/codegen/ContractCompiler.h
@@ -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/test/cmdlineTests/gas_test_dispatch.sol b/test/cmdlineTests/gas_test_dispatch.sol
new file mode 100644
index 00000000..a5ca9e7d
--- /dev/null
+++ b/test/cmdlineTests/gas_test_dispatch.sol
@@ -0,0 +1,43 @@
+pragma solidity >=0.0;
+
+contract Large {
+    uint public a;
+    uint[] public b;
+    function f1(uint x) public returns (uint) { a = x; b[uint8(msg.data[0])] = x; }
+    function f2(uint x) public returns (uint) { b[uint8(msg.data[1])] = x; }
+    function f3(uint x) public returns (uint) { b[uint8(msg.data[2])] = x; }
+    function f4(uint x) public returns (uint) { b[uint8(msg.data[3])] = x; }
+    function f5(uint x) public returns (uint) { b[uint8(msg.data[4])] = x; }
+    function f6(uint x) public returns (uint) { b[uint8(msg.data[5])] = x; }
+    function f7(uint x) public returns (uint) { b[uint8(msg.data[6])] = x; }
+    function f8(uint x) public returns (uint) { b[uint8(msg.data[7])] = x; }
+    function f9(uint x) public returns (uint) { b[uint8(msg.data[8])] = x; }
+    function f0(uint x) public pure returns (uint) { require(x > 10); }
+    function g1(uint x) public payable returns (uint) { a = x; b[uint8(msg.data[0])] = x; }
+    function g2(uint x) public payable returns (uint) { b[uint8(msg.data[1])] = x; }
+    function g3(uint x) public payable returns (uint) { b[uint8(msg.data[2])] = x; }
+    function g4(uint x) public payable returns (uint) { b[uint8(msg.data[3])] = x; }
+    function g5(uint x) public payable returns (uint) { b[uint8(msg.data[4])] = x; }
+    function g6(uint x) public payable returns (uint) { b[uint8(msg.data[5])] = x; }
+    function g7(uint x) public payable returns (uint) { b[uint8(msg.data[6])] = x; }
+    function g8(uint x) public payable returns (uint) { b[uint8(msg.data[7])] = x; }
+    function g9(uint x) public payable returns (uint) { b[uint8(msg.data[8])] = x; }
+    function g0(uint x) public payable returns (uint) { require(x > 10); }
+}
+contract Medium {
+    uint public a;
+    uint[] public b;
+    function f1(uint x) public returns (uint) { a = x; b[uint8(msg.data[0])] = x; }
+    function f2(uint x) public returns (uint) { b[uint8(msg.data[1])] = x; }
+    function f3(uint x) public returns (uint) { b[uint8(msg.data[2])] = x; }
+    function g7(uint x) public payable returns (uint) { b[uint8(msg.data[6])] = x; }
+    function g8(uint x) public payable returns (uint) { b[uint8(msg.data[7])] = x; }
+    function g9(uint x) public payable returns (uint) { b[uint8(msg.data[8])] = x; }
+    function g0(uint x) public payable returns (uint) { require(x > 10); }
+}
+contract Small {
+    uint public a;
+    uint[] public b;
+    function f1(uint x) public returns (uint) { a = x; b[uint8(msg.data[0])] = x; }
+    function () external payable {}
+}
diff --git a/test/cmdlineTests/gas_test_dispatch.sol.args b/test/cmdlineTests/gas_test_dispatch.sol.args
new file mode 100644
index 00000000..3684987e
--- /dev/null
+++ b/test/cmdlineTests/gas_test_dispatch.sol.args
@@ -0,0 +1 @@
+--gas
diff --git a/test/cmdlineTests/gas_test_dispatch.sol.stdout b/test/cmdlineTests/gas_test_dispatch.sol.stdout
new file mode 100644
index 00000000..117affad
--- /dev/null
+++ b/test/cmdlineTests/gas_test_dispatch.sol.stdout
@@ -0,0 +1,53 @@
+
+======= gas_test_dispatch.sol:Large =======
+Gas estimation:
+construction:
+   1034 + 998400 = 999434
+external:
+   a():	456
+   b(uint256):	857
+   f0(uint256):	438
+   f1(uint256):	40781
+   f2(uint256):	20722
+   f3(uint256):	20810
+   f4(uint256):	20788
+   f5(uint256):	20766
+   f6(uint256):	20789
+   f7(uint256):	20701
+   f8(uint256):	20701
+   f9(uint256):	20723
+   g0(uint256):	324
+   g1(uint256):	40736
+   g2(uint256):	20699
+   g3(uint256):	20787
+   g4(uint256):	20765
+   g5(uint256):	20721
+   g6(uint256):	20744
+   g7(uint256):	20743
+   g8(uint256):	20721
+   g9(uint256):	20678
+
+======= gas_test_dispatch.sol:Medium =======
+Gas estimation:
+construction:
+   411 + 376600 = 377011
+external:
+   a():	433
+   b(uint256):	857
+   f1(uint256):	40692
+   f2(uint256):	20722
+   f3(uint256):	20766
+   g0(uint256):	324
+   g7(uint256):	20721
+   g8(uint256):	20699
+   g9(uint256):	20655
+
+======= gas_test_dispatch.sol:Small =======
+Gas estimation:
+construction:
+   153 + 107800 = 107953
+external:
+   fallback:	123
+   a():	388
+   b(uint256):	813
+   f1(uint256):	40692
diff --git a/test/cmdlineTests/gas_test_dispatch_optimize.sol b/test/cmdlineTests/gas_test_dispatch_optimize.sol
new file mode 100644
index 00000000..a5ca9e7d
--- /dev/null
+++ b/test/cmdlineTests/gas_test_dispatch_optimize.sol
@@ -0,0 +1,43 @@
+pragma solidity >=0.0;
+
+contract Large {
+    uint public a;
+    uint[] public b;
+    function f1(uint x) public returns (uint) { a = x; b[uint8(msg.data[0])] = x; }
+    function f2(uint x) public returns (uint) { b[uint8(msg.data[1])] = x; }
+    function f3(uint x) public returns (uint) { b[uint8(msg.data[2])] = x; }
+    function f4(uint x) public returns (uint) { b[uint8(msg.data[3])] = x; }
+    function f5(uint x) public returns (uint) { b[uint8(msg.data[4])] = x; }
+    function f6(uint x) public returns (uint) { b[uint8(msg.data[5])] = x; }
+    function f7(uint x) public returns (uint) { b[uint8(msg.data[6])] = x; }
+    function f8(uint x) public returns (uint) { b[uint8(msg.data[7])] = x; }
+    function f9(uint x) public returns (uint) { b[uint8(msg.data[8])] = x; }
+    function f0(uint x) public pure returns (uint) { require(x > 10); }
+    function g1(uint x) public payable returns (uint) { a = x; b[uint8(msg.data[0])] = x; }
+    function g2(uint x) public payable returns (uint) { b[uint8(msg.data[1])] = x; }
+    function g3(uint x) public payable returns (uint) { b[uint8(msg.data[2])] = x; }
+    function g4(uint x) public payable returns (uint) { b[uint8(msg.data[3])] = x; }
+    function g5(uint x) public payable returns (uint) { b[uint8(msg.data[4])] = x; }
+    function g6(uint x) public payable returns (uint) { b[uint8(msg.data[5])] = x; }
+    function g7(uint x) public payable returns (uint) { b[uint8(msg.data[6])] = x; }
+    function g8(uint x) public payable returns (uint) { b[uint8(msg.data[7])] = x; }
+    function g9(uint x) public payable returns (uint) { b[uint8(msg.data[8])] = x; }
+    function g0(uint x) public payable returns (uint) { require(x > 10); }
+}
+contract Medium {
+    uint public a;
+    uint[] public b;
+    function f1(uint x) public returns (uint) { a = x; b[uint8(msg.data[0])] = x; }
+    function f2(uint x) public returns (uint) { b[uint8(msg.data[1])] = x; }
+    function f3(uint x) public returns (uint) { b[uint8(msg.data[2])] = x; }
+    function g7(uint x) public payable returns (uint) { b[uint8(msg.data[6])] = x; }
+    function g8(uint x) public payable returns (uint) { b[uint8(msg.data[7])] = x; }
+    function g9(uint x) public payable returns (uint) { b[uint8(msg.data[8])] = x; }
+    function g0(uint x) public payable returns (uint) { require(x > 10); }
+}
+contract Small {
+    uint public a;
+    uint[] public b;
+    function f1(uint x) public returns (uint) { a = x; b[uint8(msg.data[0])] = x; }
+    function () external payable {}
+}
diff --git a/test/cmdlineTests/gas_test_dispatch_optimize.sol.args b/test/cmdlineTests/gas_test_dispatch_optimize.sol.args
new file mode 100644
index 00000000..814e0591
--- /dev/null
+++ b/test/cmdlineTests/gas_test_dispatch_optimize.sol.args
@@ -0,0 +1 @@
+--optimize --optimize-runs 2 --gas
diff --git a/test/cmdlineTests/gas_test_dispatch_optimize.sol.stdout b/test/cmdlineTests/gas_test_dispatch_optimize.sol.stdout
new file mode 100644
index 00000000..76fa086e
--- /dev/null
+++ b/test/cmdlineTests/gas_test_dispatch_optimize.sol.stdout
@@ -0,0 +1,53 @@
+
+======= gas_test_dispatch_optimize.sol:Large =======
+Gas estimation:
+construction:
+   300 + 262000 = 262300
+external:
+   a():	463
+   b(uint256):	1173
+   f0(uint256):	399
+   f1(uint256):	41164
+   f2(uint256):	21224
+   f3(uint256):	21312
+   f4(uint256):	21290
+   f5(uint256):	21268
+   f6(uint256):	21180
+   f7(uint256):	20960
+   f8(uint256):	21092
+   f9(uint256):	21114
+   g0(uint256):	639
+   g1(uint256):	40876
+   g2(uint256):	20958
+   g3(uint256):	21046
+   g4(uint256):	21024
+   g5(uint256):	21112
+   g6(uint256):	20892
+   g7(uint256):	21002
+   g8(uint256):	20980
+   g9(uint256):	20826
+
+======= gas_test_dispatch_optimize.sol:Medium =======
+Gas estimation:
+construction:
+   190 + 143000 = 143190
+external:
+   a():	463
+   b(uint256):	931
+   f1(uint256):	40944
+   f2(uint256):	20982
+   f3(uint256):	21026
+   g0(uint256):	397
+   g7(uint256):	20892
+   g8(uint256):	20870
+   g9(uint256):	20826
+
+======= gas_test_dispatch_optimize.sol:Small =======
+Gas estimation:
+construction:
+   117 + 67400 = 67517
+external:
+   fallback:	183
+   a():	441
+   b(uint256):	821
+   f1(uint256):	40878