<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.EmailStyle20
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
p.msipheaderc10f11a2, li.msipheaderc10f11a2, div.msipheaderc10f11a2
{mso-style-name:msipheaderc10f11a2;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
.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:58478713;
mso-list-template-ids:-752725842;}
@list l0:level1
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level3
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:1.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level4
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:2.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level5
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:2.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level6
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:3.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level7
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:3.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level8
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:4.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level9
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:4.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1
{mso-list-id:1176306564;
mso-list-template-ids:247481092;}
@list l1:level1
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level2
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level3
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:1.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level4
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:2.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level5
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:2.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level6
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:3.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level7
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:3.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level8
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:4.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level9
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:4.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2
{mso-list-id:1585799117;
mso-list-template-ids:826186780;}
@list l2:level1
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level2
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level3
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:1.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level4
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:2.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level5
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:2.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level6
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:3.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level7
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:3.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level8
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:4.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level9
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:4.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l3
{mso-list-id:1810394870;
mso-list-type:hybrid;
mso-list-template-ids:1402266420 67698689 67698691 67698693 67698689 67698691 67698693 67698689 67698691 67698693;}
@list l3:level1
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:Symbol;}
@list l3:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:"Courier New";}
@list l3:level3
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:Wingdings;}
@list l3:level4
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:Symbol;}
@list l3:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:"Courier New";}
@list l3:level6
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:Wingdings;}
@list l3:level7
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:Symbol;}
@list l3:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:"Courier New";}
@list l3:level9
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:Wingdings;}
@list l4
{mso-list-id:1923097965;
mso-list-template-ids:420390502;}
@list l4:level1
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level2
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level3
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:1.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level4
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:2.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level5
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:2.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level6
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:3.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level7
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:3.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level8
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:4.0in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l4:level9
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:4.5in;
mso-level-number-position:left;
text-indent:-.25in;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l5
{mso-list-id:2046787395;
mso-list-type:hybrid;
mso-list-template-ids:249483016 67698689 67698691 67698693 67698689 67698691 67698693 67698689 67698691 67698693;}
@list l5:level1
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:Symbol;}
@list l5:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:"Courier New";}
@list l5:level3
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:Wingdings;}
@list l5:level4
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:Symbol;}
@list l5:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:"Courier New";}
@list l5:level6
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:Wingdings;}
@list l5:level7
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:Symbol;}
@list l5:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:"Courier New";}
@list l5:level9
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:Wingdings;}
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="msipheaderc10f11a2" style="margin:0in"><span style="font-size:10.0pt;font-family:"Arial",sans-serif;color:green">[Public]</span><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">It’s been a while since I’ve looked at the pipeliner… The lack of discussion and history is because the pipeliner was developed downsteam for a long period of time before it was upstreamed.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Three of the cases are from Figure 6 in the original paper by Llosa and others.<o:p></o:p></p>
<ul style="margin-top:0in" type="disc">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l3 level1 lfo3">If pred_L is a subset of the NodeSet, BottomUp and add subset to work list<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:0in;mso-list:l3 level1 lfo3">If succ_L is s subset of the NodeSet, TopDown and add subset to work list<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:0in;mso-list:l3 level1 lfo3">Otherwise, BottomUp and add node with the highest ASAP to work list<o:p></o:p></li></ul>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I’m pretty sure, at various points, we tried intersection for pred_L and succ_L, but I don’t think that gave us very good results.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">The two additional cases,<o:p></o:p></p>
<ul style="margin-top:0in" type="disc">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l3 level1 lfo3">If intersect(succ_L, NodeSet) is non-empty, TopDown and add intersect to work list<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:0in;mso-list:l3 level1 lfo3">If there is only 1 NodeSet, BottomUp and add nodes at the bottom of the schedule (Succs.size() == 0) to work list<o:p></o:p></li></ul>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">These were added to improve node ordering and the generated schedule, which were identified when analyzing benchmarks. For the first case, if that heuristic is removed, then one of the tests, swp-conv3x3-nested.ll fails. That was an important
kernel to pipeline, and it doesn’t pipeline without that heuristic.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">The SMS algorithm tries to limit the cases when a node has both successors and predecessors scheduled already. This is a concern for node-sets with recurrences (because there is one node that will have successors and predecessors scheduled
already). In loops that contain many node-sets that have recurrences, finding a valid ordering may be difficult. The challenge with the original three cases is that the fallback is to do a bottom-up schedule, and it starts with a single node only. We noticed
that it’s important to choose the correct direction and it’s important to identify the initial set of nodes used (to start going top-down or bottom-up).<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">For the first case, with the intersection, we don’t want to go bottom-up with a single node. Instead, starting top-down is better because the current node-set contains successors of nodes scheduled already. Furthermore, we want to start
with the set of nodes. If we start with a single node going top-down, then the algorithm ends up switching eventually to bottom-up and creating a case where a node has a successor and predecessor scheduled already.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">In the second case, with only 1 node-set, all the nodes in the basic block belong to a single node-set. With the fall back, the algorithm goes bottom-up with a single node, and it may be difficult to choose the best one to start with. This
heuristic chooses multiple nodes to start with so that bottom-up traversal occurs as a wave over a set. That is, rather than going up, and then down, etc. It helped to prime the traversal with multiple nodes rather than a single node. (Unfortunately, there
is no test case that fails if this heuristic is removed).<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Let me know if you have any questions. In your case, are the two new heuristics the reason why your example doesn’t schedule?<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">Brendon<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>Nagurne, James via llvm-dev<br>
<b>Sent:</b> Thursday, September 9, 2021 1:12 PM<br>
<b>To:</b> 'llvm-dev@lists.llvm.org' <llvm-dev@lists.llvm.org><br>
<b>Cc:</b> Jayaraj, Ajay <ajayj@ti.com><br>
<b>Subject:</b> [llvm-dev] Looking for some history on MachinePipeliner<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">[CAUTION: External Email] <o:p></o:p></p>
<div>
<p class="MsoNormal">I’ve been tinkering with the MachinePipeliner for my team’s downstream target, and have run into a particular issue with node ordering in the SMS algorithm. In particular, I’ve noticed that in some cases, I’m receiving an ‘Invalid node
order’ warning in the debug. I’ve tracked this down to how ‘computeNodeOrder’ is implemented.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">computeNodeOrder’s algorithm seems to be relatively untouched from the initial commit:<o:p></o:p></p>
<p class="MsoNormal" style="text-indent:.5in"><a href="https://nam11.safelinks.protection.outlook.com/?url=https%3A%2F%2Freviews.llvm.org%2FD16829&data=04%7C01%7CBrendon.Cahoon%40amd.com%7C0e9df2f911644a1bd86008d973bd538c%7C3dd8961fe4884e608e11a82d994e183d%7C0%7C0%7C637668079257051157%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=NwJ1b72vIA0GilZSKyKeN7ffDy4y2%2FYR9XBbPCAdnMA%3D&reserved=0">https://reviews.llvm.org/D16829</a><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">However, the algorithm is very different from those found in the 3 papers upon which the implementation is based:<o:p></o:p></p>
<p class="MsoNormal"> <a href="https://nam11.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fllvm%2Fllvm-project%2Fblob%2Ff40bba48a593d4297a6d0b4d1534082858b1d0ac%2Fllvm%2Finclude%2Fllvm%2FCodeGen%2FMachinePipeliner.h%23L18&data=04%7C01%7CBrendon.Cahoon%40amd.com%7C0e9df2f911644a1bd86008d973bd538c%7C3dd8961fe4884e608e11a82d994e183d%7C0%7C0%7C637668079257061113%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=PNUKsATxYSr69GCNAGQlLexEobC1gQfgxyBhQ%2FvAwc8%3D&reserved=0">
https://github.com/llvm/llvm-project/blob/f40bba48a593d4297a6d0b4d1534082858b1d0ac/llvm/include/llvm/CodeGen/MachinePipeliner.h#L18</a><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">In the implementation:<o:p></o:p></p>
<p class="MsoNormal"> <a href="https://nam11.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fllvm%2Fllvm-project%2Fblob%2Ff40bba48a593d4297a6d0b4d1534082858b1d0ac%2Fllvm%2Flib%2FCodeGen%2FMachinePipeliner.cpp%23L1877&data=04%7C01%7CBrendon.Cahoon%40amd.com%7C0e9df2f911644a1bd86008d973bd538c%7C3dd8961fe4884e608e11a82d994e183d%7C0%7C0%7C637668079257061113%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=%2Bygn6Cycn02tUeLps4pWF%2FNqk6J9%2BYEcso6d4IUmcW8%3D&reserved=0">
https://github.com/llvm/llvm-project/blob/f40bba48a593d4297a6d0b4d1534082858b1d0ac/llvm/lib/CodeGen/MachinePipeliner.cpp#L1877</a><o:p></o:p></p>
<p class="MsoNormal">The order seems to be:<o:p></o:p></p>
<ul style="margin-top:0in" type="disc">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l3 level1 lfo3">If pred_L is a subset of the NodeSet, BottomUp and add subset to work list<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:0in;mso-list:l3 level1 lfo3">If succ_L is s subset of the NodeSet, TopDown and add subset to work list<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:0in;mso-list:l3 level1 lfo3">If intersect(succ_L, NodeSet) is non-empty, TopDown and add intersect to work list<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:0in;mso-list:l3 level1 lfo3">If there is only 1 NodeSet, BottomUp and add nodes at the bottom of the schedule (Succs.size() == 0) to work list<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:0in;mso-list:l3 level1 lfo3">Otherwise, BottomUp and add node with the highest ASAP to work list<o:p></o:p></li></ul>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">In the papers (Using <a href="https://nam11.safelinks.protection.outlook.com/?url=https%3A%2F%2Fllvm.org%2Fpubs%2F2005-06-17-LattnerMSThesis.html&data=04%7C01%7CBrendon.Cahoon%40amd.com%7C0e9df2f911644a1bd86008d973bd538c%7C3dd8961fe4884e608e11a82d994e183d%7C0%7C0%7C637668079257071072%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=8b8m1J797n7xRi0HyBE%2BpX%2FfJmcL2OqauVLmzVj4GEM%3D&reserved=0">
Tanya Lattner’s master’s thesis</a> as the example), the order is:<o:p></o:p></p>
<ul style="margin-top:0in" type="disc">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l5 level1 lfo8">If intersect(pred_L, NodeSet) is non-empty, BottomUp and add subset to work list<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:0in;mso-list:l5 level1 lfo8">If intersect(succ_L, NodeSet) is non-empty, TopDown and add subset to work list<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:0in;mso-list:l5 level1 lfo8">Otherwise, BottomUp and add node with the highest ASAP to work list<o:p></o:p></li></ul>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Interestingly, when I implement the ordering from the paper, the node order for my loop is valid.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">This difference in implementation is not mentioned or commented on in the review, so I’m wondering if there are any documents or emails I may have missed in my search that would shed some light. Certainly, this ordering is just a heuristic,
so I can understand that the current incarnation just resulted in better performance for the targets utilizing it, but I’m curious if there was something more to the decision.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Regards,<o:p></o:p></p>
<p class="MsoNormal">J.B. Nagurne<o:p></o:p></p>
<p class="MsoNormal">Code Generation<o:p></o:p></p>
<p class="MsoNormal">Texas Instruments<o:p></o:p></p>
</div>
</div>
</body>
</html>