diff options
Diffstat (limited to 'libsolidity/codegen')
| -rw-r--r-- | libsolidity/codegen/AsmCodeGen.cpp | 194 | ||||
| -rw-r--r-- | libsolidity/codegen/AsmCodeGen.h | 93 | ||||
| -rw-r--r-- | libsolidity/codegen/Compiler.cpp | 4 | ||||
| -rw-r--r-- | libsolidity/codegen/CompilerContext.cpp | 11 | ||||
| -rw-r--r-- | libsolidity/codegen/ContractCompiler.cpp | 75 | ||||
| -rw-r--r-- | libsolidity/codegen/ContractCompiler.h | 12 |
6 files changed, 375 insertions, 14 deletions
diff --git a/libsolidity/codegen/AsmCodeGen.cpp b/libsolidity/codegen/AsmCodeGen.cpp new file mode 100644 index 00000000..dfcc900b --- /dev/null +++ b/libsolidity/codegen/AsmCodeGen.cpp @@ -0,0 +1,194 @@ +/* + 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 +) +{ + EthAssemblyAdapter assemblyAdapter(_assembly); + CodeTransform( + assemblyAdapter, + _analysisInfo, + false, + false, + _identifierAccess, + _useNamedLabelsForFunctions + )(_parsedData); +} diff --git a/libsolidity/codegen/AsmCodeGen.h b/libsolidity/codegen/AsmCodeGen.h new file mode 100644 index 00000000..4c6d97f4 --- /dev/null +++ b/libsolidity/codegen/AsmCodeGen.h @@ -0,0 +1,93 @@ +/* + 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 + ); +}; + +} +} 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/CompilerContext.cpp b/libsolidity/codegen/CompilerContext.cpp index 5a3a233c..dac09c2e 100644 --- a/libsolidity/codegen/CompilerContext.cpp +++ b/libsolidity/codegen/CompilerContext.cpp @@ -24,10 +24,10 @@ #include <libsolidity/codegen/CompilerUtils.h> #include <libsolidity/ast/AST.h> #include <libsolidity/codegen/Compiler.h> +#include <libsolidity/codegen/AsmCodeGen.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/YulString.h> @@ -361,7 +361,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::Dialect::strictAssemblyForEVM()).parse(scanner, false); #ifdef SOL_OUTPUT_ASM cout << yul::AsmPrinter()(*parserResult) << endl; #endif @@ -373,7 +373,7 @@ void CompilerContext::appendInlineAssembly( errorReporter, m_evmVersion, boost::none, - yul::AsmFlavour::Strict, + yul::Dialect::strictAssemblyForEVM(), identifierAccess.resolve ).analyze(*parserResult); if (!parserResult || !errorReporter.errors().empty() || !analyzerResult) @@ -386,8 +386,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 +394,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/ContractCompiler.cpp b/libsolidity/codegen/ContractCompiler.cpp index aabdbb79..79c53a1c 100644 --- a/libsolidity/codegen/ContractCompiler.cpp +++ b/libsolidity/codegen/ContractCompiler.cpp @@ -23,8 +23,8 @@ #include <libsolidity/codegen/ContractCompiler.h> #include <libsolidity/codegen/ExpressionCompiler.h> #include <libsolidity/codegen/CompilerUtils.h> +#include <libsolidity/codegen/AsmCodeGen.h> #include <libsolidity/ast/AST.h> -#include <libyul/AsmCodeGen.h> #include <liblangutil/ErrorReporter.h> #include <libevmasm/Instruction.h> @@ -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) @@ -618,7 +683,7 @@ bool ContractCompiler::visit(InlineAssembly const& _inlineAssembly) } }; solAssert(_inlineAssembly.annotation().analysisInfo, ""); - yul::CodeGenerator::assemble( + CodeGenerator::assemble( _inlineAssembly.operations(), *_inlineAssembly.annotation().analysisInfo, m_context.nonConstAssembly(), 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; |