aboutsummaryrefslogtreecommitdiffstats
path: root/libyul
diff options
context:
space:
mode:
Diffstat (limited to 'libyul')
-rw-r--r--libyul/optimiser/FullInliner.cpp61
-rw-r--r--libyul/optimiser/FullInliner.h10
-rw-r--r--libyul/optimiser/Metrics.cpp7
-rw-r--r--libyul/optimiser/Metrics.h3
4 files changed, 73 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;