aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Changelog.md1
-rw-r--r--libsolidity/codegen/Compiler.cpp4
-rw-r--r--libsolidity/codegen/ContractCompiler.cpp71
-rw-r--r--libsolidity/codegen/ContractCompiler.h12
-rw-r--r--test/cmdlineTests/gas_test_dispatch.sol43
-rw-r--r--test/cmdlineTests/gas_test_dispatch.sol.args1
-rw-r--r--test/cmdlineTests/gas_test_dispatch.sol.stdout53
-rw-r--r--test/cmdlineTests/gas_test_dispatch_optimize.sol43
-rw-r--r--test/cmdlineTests/gas_test_dispatch_optimize.sol.args1
-rw-r--r--test/cmdlineTests/gas_test_dispatch_optimize.sol.stdout53
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
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-29 20:22:46 +0800