<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=us-ascii">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* 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;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle21
{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;}
/* List Definitions */
@list l0
{mso-list-id:56517995;
mso-list-template-ids:681717850;}
@list l0:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
text-indent:-.25in;}
@list l1
{mso-list-id:808860455;
mso-list-template-ids:864730544;}
@list l1:level1
{mso-level-start-at:2;
mso-level-tab-stop:.5in;
mso-level-number-position:left;
text-indent:-.25in;}
@list l1:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2
{mso-list-id:1220282025;
mso-list-type:hybrid;
mso-list-template-ids:1603015706 67698689 67698691 67698693 67698689 67698691 67698693 67698689 67698691 67698693;}
@list l2:level1
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:38.25pt;
text-indent:-.25in;
font-family:Symbol;}
@list l2:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:74.25pt;
text-indent:-.25in;
font-family:"Courier New";}
@list l2:level3
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:110.25pt;
text-indent:-.25in;
font-family:Wingdings;}
@list l2:level4
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:146.25pt;
text-indent:-.25in;
font-family:Symbol;}
@list l2:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:182.25pt;
text-indent:-.25in;
font-family:"Courier New";}
@list l2:level6
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:218.25pt;
text-indent:-.25in;
font-family:Wingdings;}
@list l2:level7
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:254.25pt;
text-indent:-.25in;
font-family:Symbol;}
@list l2:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:290.25pt;
text-indent:-.25in;
font-family:"Courier New";}
@list l2:level9
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:326.25pt;
text-indent:-.25in;
font-family:Wingdings;}
@list l3
{mso-list-id:1576937239;
mso-list-template-ids:-1404895534;}
@list l3:level2
{mso-level-start-at:2;
mso-level-number-format:alpha-lower;
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
text-indent:-.25in;}
@list l4
{mso-list-id:1982231247;
mso-list-type:hybrid;
mso-list-template-ids:1870271422 67698703 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l4:level1
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l4:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l4:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l4:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l4:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l4:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l4:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l4:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l4:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l5
{mso-list-id:2023319129;
mso-list-type:hybrid;
mso-list-template-ids:1870271422 67698703 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l5:level1
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l5:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l5:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l5:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l5:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l5:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l5:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l5:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l5:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
ol
{margin-bottom:0in;}
ul
{margin-bottom:0in;}
--></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" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal">Sorry, I messed up the description of the problem case there. It’s not a long sequence of SCCs, but rather a single SCC with a long sequence of splits and joins. Here’s a corrected version:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Suppose that<o:p></o:p></p>
<ul style="margin-top:0in" type="disc">
<li class="MsoListParagraph" style="margin-left:2.25pt;mso-list:l2 level1 lfo7">F calls A1<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:2.25pt;mso-list:l2 level1 lfo7">A1 calls A2 and B1<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:2.25pt;mso-list:l2 level1 lfo7">A2 calls A1 and B2<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:2.25pt;mso-list:l2 level1 lfo7">B1 calls B2 and C1<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:2.25pt;mso-list:l2 level1 lfo7">B2 calls B1 and C2<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:2.25pt;mso-list:l2 level1 lfo7">C1 calls C2 and D1<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:2.25pt;mso-list:l2 level1 lfo7">C2 calls C1 and D2<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:2.25pt;mso-list:l2 level1 lfo7">…<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:2.25pt;mso-list:l2 level1 lfo7">Z1 calls Z2 and A1<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:2.25pt;mso-list:l2 level1 lfo7">Z2 calls Z1 and A2<o:p></o:p></li></ul>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Then A1,A2,B1,B2,…,Z1,Z2 all together belong to SCC 1.<o:p></o:p></p>
<p class="MsoNormal">And F is alone in SCC 2.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">The order of events is:<o:p></o:p></p>
<ol style="margin-top:0in" start="1" type="1">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l5 level1 lfo3">CGSCCPassManager visits SCC 1<o:p></o:p></li><ol style="margin-top:0in" start="1" type="a">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l5 level2 lfo3">InlinerPass visits SCC 1<o:p></o:p></li></ol>
</ol>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l5 level3 lfo3">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>i.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>Call from A1 to A2 is considered for inlining, A2’s size is A2_large, inline not performed<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l5 level3 lfo3">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>ii.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>Call from A1 to B1 is considered for inlining, B1’s size is B1_large, inline not performed<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l5 level3 lfo3">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>iii.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>Call from A2 to A1 is considered for inlining, A1’s size is A1_large, inline not performed<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l5 level3 lfo3">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>iv.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>…<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l5 level3 lfo3">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>v.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>Call from Z2 to A2 is considered for inlining, A2’s size is A2_large, inline not performed<o:p></o:p></p>
<ol style="margin-top:0in" start="1" type="1">
<ol style="margin-top:0in" start="2" type="a">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l5 level2 lfo3">FunctionSimplificationPipeline runs inside its CGSCCToFunctionPassAdaptor inside the CGSCCPassManager<o:p></o:p></li></ol>
</ol>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l5 level3 lfo3">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>i.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>FunctionSimplificationPipeline runs on A1, now its size is A1_small<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l5 level3 lfo3">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>ii.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>FunctionSimplificationPipeline runs on A2, now its size is A2_small<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l5 level3 lfo3">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>iii.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>FunctionSimplificationPipeline runs on B1, now its size is B1_small<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l5 level3 lfo3">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>iv.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>…<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l5 level3 lfo3">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>v.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>FunctionSimplificationPipeline runs on Z2, now its size is Z2_small<o:p></o:p></p>
<ol style="margin-top:0in" start="2" type="1">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l5 level1 lfo3">CGSCCPassManager visits SCC 2<o:p></o:p></li><ol style="margin-top:0in" start="1" type="a">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l5 level2 lfo3">InlinerPass visits SCC 2<o:p></o:p></li></ol>
</ol>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l5 level3 lfo3">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>i.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>Call from F to A1 is considered, A1’s size is A1_small, inlining is performed. F picks up calls to A2 and B1 in the inlined copy of A1.<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l5 level3 lfo3">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>ii.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>Call from F to A2 (added by inline of A1 into F) is considered, A2’s size is A2_small, inlining is performed, F picks up calls to A1 and B2 in the inlined copy of A2 <-- this
is the first step where we are effectively revisiting the call from A to B<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l5 level3 lfo3">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>iii.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>Call from F to B1 (added by inline of A1 into F) is considered, B1’s size is B1_small, inlining is performed, F picks up calls to B2 and C1 in the inlined copy of B1<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l5 level3 lfo3">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>iv.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>Call from F to A1 (added by inline of A2 into inline of A1 in F) is considered, A1’s size is A1_small, inlining is performed, F picks up calls to A2 and B1 in the new inlined
copy of A1<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l5 level3 lfo3">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>v.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>Call from F to B2 (added by inline of A2 into inline of A1 in F) is considered, B2’s size is B2_small, inlining is performed, F picks up calls to B1 and C2 in the inlined copy
of B2<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l5 level3 lfo3">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>vi.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>Call from F to B2 (added by inline of B1 into inline of A1 in F) is considered, B2’s size is B2_small, inlining is performed, F picks up calls to B1 and C2 in the new inlined
copy of B2<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l5 level3 lfo3">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>vii.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>Call from F to C1 (added by inline of B1 into inline of A1 in F) is considered, C1’s size is C1_small, inlining is performed, F picks up calls to C2 and D1 in the inlined copy
of C1<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l5 level3 lfo3">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>viii.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>Call from F to A2 (added by inline of A1 into inline of A2 into inline of A1 in F) is considered, blocked by InlineHostory check<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l5 level3 lfo3">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>ix.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>Call from F to B1 (added by inline of A1 into inline of A2 into inline of A1 in F) is considered, size is B1_small, inlining is performed, F picks up calls to B2 and C1 in the
new inlined copy of B1<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l5 level3 lfo3">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>x.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>Call from F to B1 (added by inline of B2 into inline of A2 into inline of A1 in F) is considered, size of B1 is B1_small, inlining is performed, F picks up calls to B2 and C1
in the new inlined copy of B1<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l5 level3 lfo3">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>xi.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>… this pattern repeats, and the inline is performed for each of the exponential number of acyclic paths through SCC 1<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b>From:</b> llvm-dev <llvm-dev-bounces@lists.llvm.org> <b>On Behalf Of
</b>Joseph Tremoulet via llvm-dev<br>
<b>Sent:</b> Tuesday, June 8, 2021 10:42 PM<br>
<b>To:</b> aeubanks@google.com<br>
<b>Cc:</b> llvm-dev <llvm-dev@lists.llvm.org><br>
<b>Subject:</b> Re: [llvm-dev] [EXTERNAL] Re: exponential code explosion during inlining<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Yes, I believe it’s from the function simplification pipeline. It happens after inlining *within* an SCC, but since it’s added to the same CFSCCPassManager as the inliner pass, it runs before the inliner pass runs on the *next* SCC, which
effectively revisits the first SCC by transitive inlines.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">To be concrete:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Suppose F calls A, A calls B, B calls A.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Then A and B together belong to SCC 1.<o:p></o:p></p>
<p class="MsoNormal">And F is alone in SCC 2.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">The order of events is:<o:p></o:p></p>
<ol style="margin-top:0in" start="1" type="1">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l4 level1 lfo6">CGSCCPassManager visits SCC 1<o:p></o:p></li><ol style="margin-top:0in" start="1" type="a">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l4 level2 lfo6">InlinerPass visits SCC 1<o:p></o:p></li></ol>
</ol>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l4 level3 lfo6">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>i.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>Call from A to B is considered for inlining, B’s size is B_large, inline not performed<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l4 level3 lfo6">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>ii.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>Call from B to A is considered for inlining, A’s size is A_large, inline not performed<o:p></o:p></p>
<ol style="margin-top:0in" start="1" type="1">
<ol style="margin-top:0in" start="2" type="a">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l4 level2 lfo6">FunctionSimplificationPipeline runs inside its CGSCCToFunctionPassAdaptor inside the CGSCCPassManager<o:p></o:p></li></ol>
</ol>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l4 level3 lfo6">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>i.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>FunctionSimplificationPipeline runs on A, now its size is A_small<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l4 level3 lfo6">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>ii.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>FunctionSimplificationPipeline runs on B, now its size is B_small<o:p></o:p></p>
<ol style="margin-top:0in" start="2" type="1">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l4 level1 lfo6">CGSCCPassManager visits SCC 2<o:p></o:p></li><ol style="margin-top:0in" start="1" type="a">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l4 level2 lfo6">InlinerPass visits SCC 2<o:p></o:p></li></ol>
</ol>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l4 level3 lfo6">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>i.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>Call from F to A is considered, A’s size is A_small, inlining is performed. F picks up a call to B in the inlined copy of A.<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l4 level3 lfo6">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>ii.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>Call form F to B (added by inline just performed) is considered, B’s size is B_small, inlining is performed, F picks up a call to A in the inlined copy of B <-- this is the
step where we are effectively revisiting the call from A to B<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l4 level3 lfo6">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>iii.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>Call from F to A (added by inline just performed) is considered, A’s size is A_small, inlining looks profitable but InlineHistory check blocks it<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">In the small example with just one SCC having just two nodes, the existing InlineHistory check is sufficient to curtail the problem. But in our suites that started failing, instead of just one such SCC, there were ~30 (i.e. A and B each
call each other but also call C and D; C and D call each other but also call E and F; E and F each call each other but also call G and H; and so on), which gave the inliner so many apparently-profitable call chains to inline that it ran until OOM.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">In the reduced repro attached to the bug, each SCC has six nodes, so the code growth is unreasonable with just two or three such SCCs.<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">-Joseph<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b>From:</b> Arthur Eubanks <<a href="mailto:aeubanks@google.com">aeubanks@google.com</a>>
<br>
<b>Sent:</b> Tuesday, June 8, 2021 6:40 PM<br>
<b>To:</b> Joseph Tremoulet <<a href="mailto:jotrem@microsoft.com">jotrem@microsoft.com</a>><br>
<b>Cc:</b> llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>><br>
<b>Subject:</b> [EXTERNAL] Re: [llvm-dev] exponential code explosion during inlining<o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">I may be misunderstanding, but when you say "cleanup", do you mean the function simplification pipeline (since the change that caused this was a change to the function simplification pipeline)? But that happens after inlining, and we won't
revisit the SCC, unless there are some weird SCC splitting/merging things going on.<o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal">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">Hi,<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">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"> <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">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"> <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">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"> <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:.5in">
// 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:.5in">
// 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:.5in">
// the end.<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">
// 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:.5in">
// 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:.5in">
// 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:.5in">
// 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:.5in">
// 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:.5in">
// 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:.5in">
// 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:.5in">
//<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:.5in">
// 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:.5in">
// 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:.5in">
// 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:.5in">
// 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:.5in">
// 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:.5in">
//<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;margin-left:.5in">
// 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:.5in">
// 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:.5in">
// 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:.5in">
// 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:.5in">
// 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:.5in">
// 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"> <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">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"> <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">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"> <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">Thanks,<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">-Joseph<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"> <o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">[1] -
<a href="https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fbugs.llvm.org%2Fshow_bug.cgi%3Fid%3D50485&data=04%7C01%7Cjotrem%40microsoft.com%7C8a876085e9e14adc849808d92af026b3%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637588033197798696%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=kl97vb6Guwk4ASYJQxvydYNHqD36xGnx1jV5m5rv7Ow%3D&reserved=0" target="_blank">
50485 – Exponential code explosion during inlining (llvm.org)</a><o:p></o:p></p>
</div>
</div>
<p class="MsoNormal">_______________________________________________<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%3A%2F%2Flists.llvm.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fllvm-dev&data=04%7C01%7Cjotrem%40microsoft.com%7C8a876085e9e14adc849808d92af026b3%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637588033197808650%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=Zor80zPyQrJ6X3QVgVay8SSEIfdaS9PXZUyDsu%2BmUbY%3D&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>