<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=utf-8"><meta name=Generator content="Microsoft Word 14 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p.MsoAcetate, li.MsoAcetate, div.MsoAcetate
{mso-style-priority:99;
mso-style-link:"Balloon Text Char";
margin:0cm;
margin-bottom:.0001pt;
font-size:8.0pt;
font-family:"Tahoma","sans-serif";}
span.EmailStyle17
{mso-style-type:personal;
font-family:"Calibri","sans-serif";
color:#1F497D;}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
span.BalloonTextChar
{mso-style-name:"Balloon Text Char";
mso-style-priority:99;
mso-style-link:"Balloon Text";
font-family:"Tahoma","sans-serif";}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link=blue vlink=purple><div class=WordSection1><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>I just realized I have sent an e-mail with an automatic disclaimer. Sorry about that. The contents of that e-mail are not confidential or privileged in any way.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><div><div style='border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0cm 0cm 0cm'><p class=MsoNormal><b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'>From:</span></b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'> llvmdev-bounces@cs.uiuc.edu [mailto:llvmdev-bounces@cs.uiuc.edu] <b>On Behalf Of </b>Pablo Barrio<br><b>Sent:</b> 22 December 2014 15:45<br><b>To:</b> Chandler Carruth<br><b>Cc:</b> Jiangning Liu; LLVM Developers Mailing List<br><b>Subject:</b> [LLVMdev] RFC: Recursion inlining<o:p></o:p></span></p></div></div><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>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.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>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.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>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.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>So my questions are:<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'> - 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.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'> - 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.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>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.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>Any thoughts, ideas, recommendations... will help.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>Regards,<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'>Pablo<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'>From:</span></b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'> Chandler Carruth [<a href="mailto:chandlerc@google.com">mailto:chandlerc@google.com</a>] <br><b>Sent:</b> 05 December 2014 10:30<br><b>To:</b> Pablo Barrio<br><b>Cc:</b> LLVM Developers Mailing List<br><b>Subject:</b> Re: [LLVMdev] Recursion inlining<o:p></o:p></span></p><p class=MsoNormal><o:p> </o:p></p><div><div><p class=MsoNormal><o:p> </o:p></p><div><p class=MsoNormal>On Fri, Dec 5, 2014 at 2:10 AM, Pablo Barrio <<a href="mailto:pablo.barrio@arm.com" target="_blank">pablo.barrio@arm.com</a>> wrote:<o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>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?<o:p></o:p></p></div><p class=MsoNormal><br>The reason used to be given in a comment in the code that got lost at some point.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>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.<o:p></o:p></p></div></div><p class=MsoNormal><o:p> </o:p></p></div></body></html>