Thank you for the reply. I enabled recursion inlining in the current inliner and
I already have some promising results. However, I found some trouble extending
the current heuristics. I hope you can all give me some feedback.
First, context: the inliner is a CallGraphSCC pass. I detect recursion here by
checking that, for each CallSite, the caller is the same as the callee (direct
recursion) or at least both belong to the SCC currently being processed
(indirect recursion). The decision whether to inline is taken in the InlineCost
class, with the help of instruction visitor CallAnalyzer and some constants
defined in namespace InlineConstants.
Now the problem. I want to use a different inline cost analysis for recursive
functions. This might include a different/extended list of parameters (another
InlineConstants namespace?) as well as a different cost function (CallAnalyzer),
keeping the same InlineCost class. However, it is not possible to check if a
function is recursive inside InlineCost, because it does not know about the SCC.
So my questions are:
- Shouldn't InlineConstants be part of the InlineCost class?
It looks like they are intended to be used in all InlineCost analyses, but that
might not be what we need.
- What would be the best way of making InlineCost aware that it
is dealing with a "recursive callsite", this is, a callsite that
closes a loop in the call graph? For now I have it hacked as a boolean passed
from the Inliner, but it hurts my eyes every time I see it. Maybe let InlineCost
know about about the current SCC? It would be easy if I could get the SCC that a
function belongs to.
Another option would be to handle recursive function inlining in a separate
Inliner pass, but the callgraph would not be traversed from the leaves to the
root in a single pass.
Any thoughts, ideas, recommendations... will help.
Regards,
Pablo
From: Chandler Carruth [mailto:chandlerc at google.com]
Sent: 05 December 2014 10:30
To: Pablo Barrio
Cc: LLVM Developers Mailing List
Subject: Re: [LLVMdev] Recursion inlining
On Fri, Dec 5, 2014 at 2:10 AM, Pablo Barrio <pablo.barrio at
arm.com<mailto:pablo.barrio at arm.com>> wrote:
The default inliner currently marks all recursive functions as “never” inline
when calculating the cost (CallAnalyzer::analyzeCall() in
lib/Analysis/IPA/InlineCost.cpp). Is there any reason for this?
The reason used to be given in a comment in the code that got lost at some
point.
The idea is that inlining recursive calls is essentially loop unrolling. We need
to model it's cost and effects more like loop unrolling intersected with
inlining, and we don't really have a good model for that yet. It would be
really nice to work up such a model, but would require loooots of benchmarking
and careful tuning to find the right mixture.
-- IMPORTANT NOTICE: The contents of this email and any attachments are
confidential and may also be privileged. If you are not the intended recipient,
please notify the sender immediately and do not disclose the contents to any
other person, use it for any purpose, or store or copy the information in any
medium. Thank you.
ARM Limited, Registered office 110 Fulbourn Road, Cambridge CB1 9NJ, Registered
in England & Wales, Company No: 2557590
ARM Holdings plc, Registered office 110 Fulbourn Road, Cambridge CB1 9NJ,
Registered in England & Wales, Company No: 2548782
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20141222/4e98c7fe/attachment.html>