diff options
author | chriseth <chris@ethereum.org> | 2018-10-17 23:22:46 +0800 |
---|---|---|
committer | GitHub <noreply@github.com> | 2018-10-17 23:22:46 +0800 |
commit | c6a6e9ac5d91a0b45eafa4a6ac10fa3e8b3c6ad2 (patch) | |
tree | f5550eb185d22fce5027d76496396163420c88bc | |
parent | fb0ec1c562d1b23f20c76d2d0f818db4e89199c3 (diff) | |
parent | 9fb5feed0513012aed38d45ccdb421e5b8d96838 (diff) | |
download | dexon-solidity-c6a6e9ac5d91a0b45eafa4a6ac10fa3e8b3c6ad2.tar dexon-solidity-c6a6e9ac5d91a0b45eafa4a6ac10fa3e8b3c6ad2.tar.gz dexon-solidity-c6a6e9ac5d91a0b45eafa4a6ac10fa3e8b3c6ad2.tar.bz2 dexon-solidity-c6a6e9ac5d91a0b45eafa4a6ac10fa3e8b3c6ad2.tar.lz dexon-solidity-c6a6e9ac5d91a0b45eafa4a6ac10fa3e8b3c6ad2.tar.xz dexon-solidity-c6a6e9ac5d91a0b45eafa4a6ac10fa3e8b3c6ad2.tar.zst dexon-solidity-c6a6e9ac5d91a0b45eafa4a6ac10fa3e8b3c6ad2.zip |
Merge pull request #5232 from ethereum/inlineHeuristic
[Yul] Add simple inlining heuristic
-rw-r--r-- | libyul/optimiser/FullInliner.cpp | 61 | ||||
-rw-r--r-- | libyul/optimiser/FullInliner.h | 10 | ||||
-rw-r--r-- | libyul/optimiser/Metrics.cpp | 7 | ||||
-rw-r--r-- | libyul/optimiser/Metrics.h | 3 | ||||
-rw-r--r-- | test/libyul/yulOptimizerTests/fullInliner/large_function_multi_use.yul | 43 | ||||
-rw-r--r-- | test/libyul/yulOptimizerTests/fullInliner/large_function_single_use.yul | 36 | ||||
-rw-r--r-- | test/libyul/yulOptimizerTests/fullInliner/recursion.yul | 18 |
7 files changed, 170 insertions, 8 deletions
diff --git a/libyul/optimiser/FullInliner.cpp b/libyul/optimiser/FullInliner.cpp index cd0ed52a..aa069506 100644 --- a/libyul/optimiser/FullInliner.cpp +++ b/libyul/optimiser/FullInliner.cpp @@ -24,6 +24,8 @@ #include <libyul/optimiser/ASTWalker.h> #include <libyul/optimiser/NameCollector.h> #include <libyul/optimiser/Utilities.h> +#include <libyul/optimiser/Metrics.h> +#include <libyul/optimiser/SSAValueTracker.h> #include <libyul/Exceptions.h> #include <libsolidity/inlineasm/AsmData.h> @@ -45,11 +47,23 @@ FullInliner::FullInliner(Block& _ast): assertThrow(m_ast.statements.front().type() == typeid(Block), OptimizerException, ""); m_nameDispenser.m_usedNames = NameCollector(m_ast).names(); + // Determine constants + SSAValueTracker tracker; + tracker(m_ast); + for (auto const& ssaValue: tracker.values()) + if (ssaValue.second && ssaValue.second->type() == typeid(Literal)) + m_constants.insert(ssaValue.first); + + map<string, size_t> references = ReferencesCounter::countReferences(m_ast); for (size_t i = 1; i < m_ast.statements.size(); ++i) { assertThrow(m_ast.statements.at(i).type() == typeid(FunctionDefinition), OptimizerException, ""); FunctionDefinition& fun = boost::get<FunctionDefinition>(m_ast.statements.at(i)); m_functions[fun.name] = &fun; + // Always inline functions that are only called once. + if (references[fun.name] == 1) + m_alwaysInline.insert(fun.name); + updateCodeSize(fun); } } @@ -58,8 +72,18 @@ void FullInliner::run() assertThrow(m_ast.statements[0].type() == typeid(Block), OptimizerException, ""); handleBlock("", boost::get<Block>(m_ast.statements[0])); + // TODO it might be good to determine a visiting order: + // first handle functions that are called from many places. for (auto const& fun: m_functions) + { handleBlock(fun.second->name, fun.second->body); + updateCodeSize(*fun.second); + } +} + +void FullInliner::updateCodeSize(FunctionDefinition& fun) +{ + m_functionSizes[fun.name] = CodeSize::codeSize(fun.body); } void FullInliner::handleBlock(string const& _currentFunctionName, Block& _block) @@ -67,6 +91,33 @@ void FullInliner::handleBlock(string const& _currentFunctionName, Block& _block) InlineModifier{*this, m_nameDispenser, _currentFunctionName}(_block); } +bool FullInliner::shallInline(FunctionCall const& _funCall, string const& _callSite) +{ + // No recursive inlining + if (_funCall.functionName.name == _callSite) + return false; + + FunctionDefinition& calledFunction = function(_funCall.functionName.name); + if (m_alwaysInline.count(calledFunction.name)) + return true; + + // Constant arguments might provide a means for further optimization, so they cause a bonus. + bool constantArg = false; + for (auto const& argument: _funCall.arguments) + if (argument.type() == typeid(Literal) || ( + argument.type() == typeid(Identifier) && + m_constants.count(boost::get<Identifier>(argument).name) + )) + { + constantArg = true; + break; + } + + size_t size = m_functionSizes.at(calledFunction.name); + return (size < 10 || (constantArg && size < 50)); +} + + void InlineModifier::operator()(Block& _block) { function<boost::optional<vector<Statement>>(Statement&)> f = [&](Statement& _statement) -> boost::optional<vector<Statement>> { @@ -90,14 +141,8 @@ boost::optional<vector<Statement>> InlineModifier::tryInlineStatement(Statement& FunctionCall* funCall = boost::apply_visitor(GenericFallbackReturnsVisitor<FunctionCall*, FunctionCall&>( [](FunctionCall& _e) { return &_e; } ), *e); - if (funCall) - { - // TODO: Insert good heuristic here. Perhaps implement that inside the driver. - bool doInline = funCall->functionName.name != m_currentFunction; - - if (doInline) - return performInline(_statement, *funCall); - } + if (funCall && m_driver.shallInline(*funCall, m_currentFunction)) + return performInline(_statement, *funCall); } return {}; } diff --git a/libyul/optimiser/FullInliner.h b/libyul/optimiser/FullInliner.h index 495286c0..513ffc93 100644 --- a/libyul/optimiser/FullInliner.h +++ b/libyul/optimiser/FullInliner.h @@ -75,15 +75,25 @@ public: void run(); + /// Inlining heuristic. + /// @param _callSite the name of the function in which the function call is located. + bool shallInline(FunctionCall const& _funCall, std::string const& _callSite); + FunctionDefinition& function(std::string _name) { return *m_functions.at(_name); } private: + void updateCodeSize(FunctionDefinition& fun); void handleBlock(std::string const& _currentFunctionName, Block& _block); /// The AST to be modified. The root block itself will not be modified, because /// we store pointers to functions. Block& m_ast; std::map<std::string, FunctionDefinition*> m_functions; + /// Names of functions to always inline. + std::set<std::string> m_alwaysInline; + /// Variables that are constants (used for inlining heuristic) + std::set<std::string> m_constants; + std::map<std::string, size_t> m_functionSizes; NameDispenser m_nameDispenser; }; diff --git a/libyul/optimiser/Metrics.cpp b/libyul/optimiser/Metrics.cpp index eb2d39e8..066c6b58 100644 --- a/libyul/optimiser/Metrics.cpp +++ b/libyul/optimiser/Metrics.cpp @@ -39,6 +39,13 @@ size_t CodeSize::codeSize(Expression const& _expression) return cs.m_size; } +size_t CodeSize::codeSize(Block const& _block) +{ + CodeSize cs; + cs(_block); + return cs.m_size; +} + void CodeSize::visit(Statement const& _statement) { ++m_size; diff --git a/libyul/optimiser/Metrics.h b/libyul/optimiser/Metrics.h index 8ed73cca..47c7ec79 100644 --- a/libyul/optimiser/Metrics.h +++ b/libyul/optimiser/Metrics.h @@ -36,6 +36,9 @@ public: /// Returns a metric for the code size of an AST element. /// More specifically, it returns the number of AST nodes. static size_t codeSize(Expression const& _expression); + /// Returns a metric for the code size of an AST element. + /// More specifically, it returns the number of AST nodes. + static size_t codeSize(Block const& _block); private: virtual void visit(Statement const& _statement) override; diff --git a/test/libyul/yulOptimizerTests/fullInliner/large_function_multi_use.yul b/test/libyul/yulOptimizerTests/fullInliner/large_function_multi_use.yul new file mode 100644 index 00000000..0972ac56 --- /dev/null +++ b/test/libyul/yulOptimizerTests/fullInliner/large_function_multi_use.yul @@ -0,0 +1,43 @@ +{ + function f(a) -> b { + let x := mload(a) + b := sload(x) + let c := 3 + mstore(mul(a, b), mload(x)) + let y := add(a, x) + sstore(y, 10) + } + let a := mload(2) + let a2 := 2 + // This should not be inlined because it is not a constant + let r := f(a) + // This should be inlined because it is a constant + let t := f(a2) +} +// ---- +// fullInliner +// { +// { +// let a_1 := mload(2) +// let a2 := 2 +// let r := f(a_1) +// let f_a := a2 +// let f_b +// let f_x := mload(f_a) +// f_b := sload(f_x) +// let f_c := 3 +// mstore(mul(f_a, f_b), mload(f_x)) +// let f_y := add(f_a, f_x) +// sstore(f_y, 10) +// let t := f_b +// } +// function f(a) -> b +// { +// let x := mload(a) +// b := sload(x) +// let c := 3 +// mstore(mul(a, b), mload(x)) +// let y := add(a, x) +// sstore(y, 10) +// } +// } diff --git a/test/libyul/yulOptimizerTests/fullInliner/large_function_single_use.yul b/test/libyul/yulOptimizerTests/fullInliner/large_function_single_use.yul new file mode 100644 index 00000000..3302a35c --- /dev/null +++ b/test/libyul/yulOptimizerTests/fullInliner/large_function_single_use.yul @@ -0,0 +1,36 @@ +{ + function f(a) -> b { + let x := mload(a) + b := sload(x) + let c := 3 + mstore(mul(a, b), mload(x)) + let y := add(a, x) + sstore(y, 10) + } + // Single-use functions are always inlined. + let r := f(mload(1)) +} +// ---- +// fullInliner +// { +// { +// let f_a := mload(1) +// let f_b +// let f_x := mload(f_a) +// f_b := sload(f_x) +// let f_c := 3 +// mstore(mul(f_a, f_b), mload(f_x)) +// let f_y := add(f_a, f_x) +// sstore(f_y, 10) +// let r := f_b +// } +// function f(a) -> b +// { +// let x := mload(a) +// b := sload(x) +// let c := 3 +// mstore(mul(a, b), mload(x)) +// let y := add(a, x) +// sstore(y, 10) +// } +// } diff --git a/test/libyul/yulOptimizerTests/fullInliner/recursion.yul b/test/libyul/yulOptimizerTests/fullInliner/recursion.yul new file mode 100644 index 00000000..3e9a8021 --- /dev/null +++ b/test/libyul/yulOptimizerTests/fullInliner/recursion.yul @@ -0,0 +1,18 @@ +{ + function f(a) { + f(1) + } + f(mload(0)) +} +// ---- +// fullInliner +// { +// { +// let f_a := mload(0) +// f(1) +// } +// function f(a) +// { +// f(1) +// } +// } |