From 3ebb78a886b606cad345534758b4dcc4ab2863d0 Mon Sep 17 00:00:00 2001 From: chriseth Date: Tue, 4 Dec 2018 15:20:29 +0100 Subject: Adjust include paths. --- libsolidity/codegen/ContractCompiler.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'libsolidity/codegen/ContractCompiler.cpp') diff --git a/libsolidity/codegen/ContractCompiler.cpp b/libsolidity/codegen/ContractCompiler.cpp index aabdbb79..286e5856 100644 --- a/libsolidity/codegen/ContractCompiler.cpp +++ b/libsolidity/codegen/ContractCompiler.cpp @@ -23,8 +23,8 @@ #include #include #include +#include #include -#include #include #include -- cgit v1.2.3 From 7ee1ddc172a29ed1ccdd545a996d19f4c2a145a3 Mon Sep 17 00:00:00 2001 From: chriseth Date: Tue, 4 Dec 2018 15:36:03 +0100 Subject: Switch namespaces. --- libsolidity/codegen/ContractCompiler.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'libsolidity/codegen/ContractCompiler.cpp') diff --git a/libsolidity/codegen/ContractCompiler.cpp b/libsolidity/codegen/ContractCompiler.cpp index 286e5856..ec55ae9b 100644 --- a/libsolidity/codegen/ContractCompiler.cpp +++ b/libsolidity/codegen/ContractCompiler.cpp @@ -618,7 +618,7 @@ bool ContractCompiler::visit(InlineAssembly const& _inlineAssembly) } }; solAssert(_inlineAssembly.annotation().analysisInfo, ""); - yul::CodeGenerator::assemble( + CodeGenerator::assemble( _inlineAssembly.operations(), *_inlineAssembly.annotation().analysisInfo, m_context.nonConstAssembly(), -- cgit v1.2.3 From 7f39c3e52226e133d4224a7afb763a3c5b4c525e Mon Sep 17 00:00:00 2001 From: chriseth Date: Mon, 10 Sep 2018 12:09:42 +0200 Subject: Binary search for dispatch. --- libsolidity/codegen/ContractCompiler.cpp | 71 ++++++++++++++++++++++++++++++-- 1 file changed, 68 insertions(+), 3 deletions(-) (limited to 'libsolidity/codegen/ContractCompiler.cpp') 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, eth::AssemblyItem const> const& _entryPoints, + vector> const& _ids, + eth::AssemblyItem const& _notFoundTag, + size_t _runs +) +{ + // Code for selecting from n functions without split: + // n times: dup1, push4 , eq, push2/3 , jumpi + // push2/3 jump + // (called SELECT[n]) + // Code for selecting from n functions with split: + // dup1, push4 , gt, push2/3, 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> larger{_ids.begin() + pivotIndex, _ids.end()}; + appendInternalSelector(_entryPoints, larger, _notFoundTag, _runs); + m_context << lessTag; + // Here, we have funid < pivot + vector> 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, 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: ? + vector> 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) -- cgit v1.2.3 From 2f6dc2e773148f63f4e2b9d9b3f9bb7eb092fde8 Mon Sep 17 00:00:00 2001 From: Mathias Baumann Date: Mon, 10 Dec 2018 19:02:39 +0100 Subject: Replace push_back with emplace_back where it makes sense --- libsolidity/codegen/ContractCompiler.cpp | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) (limited to 'libsolidity/codegen/ContractCompiler.cpp') diff --git a/libsolidity/codegen/ContractCompiler.cpp b/libsolidity/codegen/ContractCompiler.cpp index 79c53a1c..67876721 100644 --- a/libsolidity/codegen/ContractCompiler.cpp +++ b/libsolidity/codegen/ContractCompiler.cpp @@ -721,14 +721,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); @@ -739,7 +739,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); @@ -770,8 +770,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 @@ -997,7 +997,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(), ""); -- cgit v1.2.3 From ab7667627149e5793343b81af43f3fa1b328097d Mon Sep 17 00:00:00 2001 From: Leonardo Alt Date: Mon, 17 Dec 2018 17:06:11 +0100 Subject: Sort includes in libsolidity/codegen --- libsolidity/codegen/ContractCompiler.cpp | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-) (limited to 'libsolidity/codegen/ContractCompiler.cpp') diff --git a/libsolidity/codegen/ContractCompiler.cpp b/libsolidity/codegen/ContractCompiler.cpp index 67876721..16c90b60 100644 --- a/libsolidity/codegen/ContractCompiler.cpp +++ b/libsolidity/codegen/ContractCompiler.cpp @@ -20,19 +20,18 @@ * Solidity compiler. */ +#include +#include +#include #include #include -#include -#include -#include -#include #include #include #include +#include #include - #include using namespace std; -- cgit v1.2.3 From 1b8570f829ead5859c60e92e51e814e3baa50dc9 Mon Sep 17 00:00:00 2001 From: Mathias Baumann Date: Tue, 11 Dec 2018 16:42:09 +0100 Subject: Only generate sort/search code when interface functions exist --- libsolidity/codegen/ContractCompiler.cpp | 51 +++++++++++++++++++++++++------- 1 file changed, 41 insertions(+), 10 deletions(-) (limited to 'libsolidity/codegen/ContractCompiler.cpp') diff --git a/libsolidity/codegen/ContractCompiler.cpp b/libsolidity/codegen/ContractCompiler.cpp index 16c90b60..b051d260 100644 --- a/libsolidity/codegen/ContractCompiler.cpp +++ b/libsolidity/codegen/ContractCompiler.cpp @@ -331,6 +331,25 @@ void ContractCompiler::appendInternalSelector( } } +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, FunctionTypePointer> interfaceFunctions = _contract.interfaceFunctions(); @@ -342,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 @@ -350,23 +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: ? - vector> sortedIDs; - for (auto const& it: interfaceFunctions) - { - callDataUnpackerEntryPoints.insert(std::make_pair(it.first, m_context.newTag())); - sortedIDs.emplace_back(it.first); + // stack now is: ? + vector> 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); } - std::sort(sortedIDs.begin(), sortedIDs.end()); - appendInternalSelector(callDataUnpackerEntryPoints, sortedIDs, notFound, m_optimise_runs); m_context << notFound; + if (fallback) { solAssert(!_contract.isLibrary(), ""); - if (!fallback->isPayable()) + if (!fallback->isPayable() && needToAddCallvalueCheck) appendCallValueCheck(); solAssert(fallback->isFallback(), ""); @@ -396,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. -- cgit v1.2.3