<html 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=Windows-1252">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
        {font-family:"Cambria Math";
        panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
        {font-family:DengXian;
        panose-1:2 1 6 0 3 1 1 1 1 1;}
@font-face
        {font-family:Calibri;
        panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
        {font-family:"\@DengXian";
        panose-1:2 1 6 0 3 1 1 1 1 1;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
        {margin:0in;
        font-size:11.0pt;
        font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
        {mso-style-priority:99;
        color:blue;
        text-decoration:underline;}
span.EmailStyle19
        {mso-style-type:personal-reply;
        font-family:"Calibri",sans-serif;
        color:windowtext;}
.MsoChpDefault
        {mso-style-type:export-only;
        font-size:10.0pt;}
@page WordSection1
        {size:8.5in 11.0in;
        margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
        {page:WordSection1;}
--></style>
</head>
<body lang="EN-US" link="blue" vlink="purple" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal">The existing implementation has a per-callsite a size cap. For a callsite, if the inlining could cause a potential size growth to exceed the given cap (3000 for hot callsites, 45 for cold callsites, 375 for warm callsites, IIRC), the inlining
 will not be done. In <a href="https://nam06.safelinks.protection.outlook.com/?url=https://reviews.llvm.org/D98481&data=04|01|jotrem@microsoft.com|ec116433a82c4401375f08d92ad9ec0a|72f988bf86f141af91ab2d7cd011db47|1|0|637587938476437450|Unknown|TWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0=|3000&sdata=LC/KyqdK44xgMtMpV1QqQTydKTkc8614yPtyXx8wcbs=&reserved=0">https://reviews.llvm.org/D98481</a>, we were thinking about enforcing a global size cap per each inliner. Give the current callsite considered to be inlined, if the size growth makes the inliner size over a given cap, the current inlining and all subsequent
 inlining will be skipped. Could this approach solve your problem?<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Thanks,<o:p></o:p></p>
<p class="MsoNormal">Hongtao<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:.5in">
<b><span style="font-size:12.0pt;color:black">From: </span></b><span style="font-size:12.0pt;color:black">Joseph Tremoulet <jotrem@microsoft.com><br>
<b>Date: </b>Wednesday, June 9, 2021 at 9:42 AM<br>
<b>To: </b>Xinliang David Li <xinliangli@gmail.com><br>
<b>Cc: </b>llvm-dev <llvm-dev@lists.llvm.org>, Hongtao Yu <hoy@fb.com>, Wenlei He <wenlei@fb.com><br>
<b>Subject: </b>RE: [EXTERNAL] Re: [llvm-dev] exponential code explosion during inlining<o:p></o:p></span></p>
</div>
<p class="MsoNormal" style="margin-left:.5in">Related, yes.  I see the conversation there leading toward having a cap on inlinee size (because, at leach level, there is a single huge function, which will be inlined twice into the single function in the next
 level).  I was mistakenly under the impression that our existing threshold effectively imposed a size cap (and therefore effectively imposed a fan-out cap), so one avenue I was considering was limiting the depth of transitive inlines through calls copied from
 inlinees in already-converged SCCs.  But adding the depth cap could make cases such as I’m hitting look a lot like the case that
<a href="https://nam06.safelinks.protection.outlook.com/?url=https://reviews.llvm.org/D98481&data=04|01|jotrem@microsoft.com|ec116433a82c4401375f08d92ad9ec0a|72f988bf86f141af91ab2d7cd011db47|1|0|637587938476437450|Unknown|TWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0=|3000&sdata=LC/KyqdK44xgMtMpV1QqQTydKTkc8614yPtyXx8wcbs=&reserved=0">https://reviews.llvm.org/D98481</a> describes.  So I think that neither the size cap nor the depth cap alone would be sufficient…<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> <o:p></o:p></p>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal" style="margin-left:.5in"><b>From:</b> Xinliang David Li <xinliangli@gmail.com>
<br>
<b>Sent:</b> Tuesday, June 8, 2021 8:03 PM<br>
<b>To:</b> Joseph Tremoulet <jotrem@microsoft.com><br>
<b>Cc:</b> llvm-dev <llvm-dev@lists.llvm.org>; Hongtao Yu <hoy@fb.com>; Wenlei He <wenlei@fb.com><br>
<b>Subject:</b> [EXTERNAL] Re: [llvm-dev] exponential code explosion during inlining<o:p></o:p></p>
</div>
<p class="MsoNormal" style="margin-left:.5in"> <o:p></o:p></p>
<div>
<p class="MsoNormal" style="margin-left:.5in">May be related to <a href="https://nam06.safelinks.protection.outlook.com/?url=https://reviews.llvm.org/D98481&data=04|01|jotrem@microsoft.com|ec116433a82c4401375f08d92ad9ec0a|72f988bf86f141af91ab2d7cd011db47|1|0|637587938476437450|Unknown|TWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0=|3000&sdata=LC/KyqdK44xgMtMpV1QqQTydKTkc8614yPtyXx8wcbs=&reserved=0">https://reviews.llvm.org/D98481</a><o:p></o:p></p>
<div>
<p class="MsoNormal" style="margin-left:.5in"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">David<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal" style="margin-left:.5in"> <o:p></o:p></p>
<div>
<div>
<p class="MsoNormal" style="margin-left:.5in">On Tue, Jun 8, 2021 at 8:43 AM Joseph Tremoulet via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0in;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:.5in">
Hi,<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:.5in">
 <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:.5in">
I filed a bug (PR50485 [1]) a couple weeks ago for some pathological behavior we’ve hit in the inliner, but there hasn’t been any reply on the bug so I figured I’d broaden the audience and ask about the issue here.<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:.5in">
 <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:.5in">
The problem is partially a phase-ordering issue – we run cleanup optimizations after inlining an SCC that reduce the size of functions in the SCC, so a given call foo -> bar that looks unprofitable due to bar’s size while processing the SCC containing foo and
 bar may suddenly look profitable due to bar’s reduced size when later considering a copy of that same callsite that gets created by inlining foo into some function in a later SCC.<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:.5in">
 <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:.5in">
This interacts badly with the approach that the inliner relies on local heuristics to eventually converge (rather than limiting itself with some global budget).  I’ll copy the comment explaining that approach here:<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:.5in">
 <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  // We use a single common worklist for calls across the entire SCC. We<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  // process these in-order and append new calls introduced during inlining to<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  // the end.<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  //<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  // Note that this particular order of processing is actually critical to<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  // avoid very bad behaviors. Consider *highly connected* call graphs where<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  // each function contains a small amount of code and a couple of calls to<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  // other functions. Because the LLVM inliner is fundamentally a bottom-up<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  // inliner, it can handle gracefully the fact that these all appear to be<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  // reasonable inlining candidates as it will flatten things until they become<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  // too big to inline, and then move on and flatten another batch.<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  //<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  // However, when processing call edges *within* an SCC we cannot rely on this<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  // bottom-up behavior. As a consequence, with heavily connected *SCCs* of<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  // functions we can end up incrementally inlining N calls into each of<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  // N functions because each incremental inlining decision looks good and we<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  // don't have a topological ordering to prevent explosions.<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  //<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  // To compensate for this, we don't process transitive edges made immediate<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  // by inlining until we've done one pass of inlining across the entire SCC.<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  // Large, highly connected SCCs still lead to some amount of code bloat in<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  // this model, but it is uniformly spread across all the functions in the SCC<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  // and eventually they all become too large to inline, rather than<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:1.0in">
  // incrementally maknig a single function grow in a super linear fashion.<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:.5in">
 <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:.5in">
The problem in a nutshell is that “eventually they all become too large to inline” is true while inlining is happening in their SCC, but then the cleanup makes them small again and so the inliner goes nuts chasing all the now-profitable paths through the highly
 connected SCC when considering them as transitive inlines into a subsequent SCC.<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:.5in">
 <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:.5in">
I’d love some thoughts on how we might best go about addressing this.  I could imagine trying to address it as a phase ordering issue by running cleanup at the start of inlining an SCC – in the cases where we’ve hit this the cleanup hasn’t actually depended
 on inlining to expose the opportunities, it just happened to first get cleaned up immediately post inlining.  I could also imagine trying to address it by limiting transitive inlines at callsites created by inlining functions from already-converged SCCs, which
 we could either do wholesale (if we’re expecting them to be too big to inline at this point, that shouldn’t be a big loss, right?) or just by capping their depth, say, to cut off exponential explosion.<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:.5in">
 <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:.5in">
 <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:.5in">
Thanks,<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:.5in">
-Joseph<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:.5in">
 <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:.5in">
[1] - <a href="https://nam06.safelinks.protection.outlook.com/?url=https://bugs.llvm.org/show_bug.cgi?id=50485&data=04|01|jotrem@microsoft.com|ec116433a82c4401375f08d92ad9ec0a|72f988bf86f141af91ab2d7cd011db47|1|0|637587938476437450|Unknown|TWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0=|3000&sdata=Zx1+iSOepCFteef7bCEFBPjZaDSSNhUBQs8AlcTv8Rs=&reserved=0" target="_blank">50485 – Exponential code explosion during inlining (llvm.org)</a><o:p></o:p></p>
</div>
</div>
<p class="MsoNormal" style="margin-left:.5in">_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://nam06.safelinks.protection.outlook.com/?url=https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev&data=04|01|jotrem@microsoft.com|ec116433a82c4401375f08d92ad9ec0a|72f988bf86f141af91ab2d7cd011db47|1|0|637587938476447404|Unknown|TWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0=|3000&sdata=xzdwO8Fo6oiv7mYjoseuZJ1hZXEJQhT+1QAsuZ11Wt8=&reserved=0" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><o:p></o:p></p>
</blockquote>
</div>
</div>
</body>
</html>