<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=iso-8859-1">
<meta name="Generator" content="Microsoft Word 12 (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:SimSun;
panose-1:2 1 6 0 3 1 1 1 1 1;}
@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;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
{font-family:SimSun;
panose-1:2 1 6 0 3 1 1 1 1 1;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
text-align:justify;
font-size:10.5pt;
font-family:"Calibri","sans-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:0in;
margin-bottom:.0001pt;
text-align:justify;
font-size:8.0pt;
font-family:"Tahoma","sans-serif";}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
span.EmailStyle18
{mso-style-type:personal;
font-family:"Calibri","sans-serif";
color:windowtext;}
span.EmailStyle19
{mso-style-type:personal;
font-family:"Calibri","sans-serif";
color:windowtext;}
span.BalloonTextChar
{mso-style-name:"Balloon Text Char";
mso-style-priority:99;
mso-style-link:"Balloon Text";
font-family:"Tahoma","sans-serif";}
span.EmailStyle22
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.25in 1.0in 1.25in;}
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" style="text-justify-trim:punctuation">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">Hi Brendon<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><i><span style="font-size:11.0pt">Certainly, there are some real copies that end up being generated, but I think it’s better to exclude the copies from the schedule since most will be eliminated. </span></i><i><span style="font-size:11.0pt;color:#1F497D"><o:p></o:p></span></i></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">I was wondering what was the cause of the real copies that was being generated in your experience? Something that I noticed when experimenting with LLVM on our out-of-tree backend, was that there
are copy instructions generated **because of** modulo scheduling. <o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">For example before modulo scheduling I have
<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">%vreg6<def> = PHI %vreg23, <BB#1>, %vreg17<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">%vreg25<def> = INSN1 %vreg1, %vreg6;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">%</span> <span style="font-size:11.0pt;color:#1F497D">
vreg26<def> = INSN1 %vreg2, %vreg6 </span><span style="font-size:11.0pt;font-family:Wingdings;color:#1F497D">ß</span><span style="font-size:11.0pt;color:#1F497D"> same opcode as previous insn<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">%</span> <span style="font-size:11.0pt;color:#1F497D">
vreg17<def> = INSN2 %vreg6, %vreg5;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">So for the phi node here, if we do phi elimination and register coalescing, we won’t have any copy insn left. But after modulo scheduling the instructions above, now appear like this:<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">%vreg73<def> = PHI %vreg59, <BB#5>, %vreg62, <BB#6>;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">%vreg61<def> = INSN1 %vreg1, %vreg73;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">%vreg62<def> = INSN2 %vreg73, %vreg5;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">%vreg64<def> = INSN1 %vreg2, %vreg73;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">Now if you look right after the third insn after modulo scheduling, both vreg73 and vreg62 are live here. So when we remove the corresponding phi instruction, we end up with a copy instruction
that cannot be removed by register coalescing. <o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">IIUC, this is a byproduct of modulo scheduling. I have not really started tuning modulo scheduling for our target, so I don’t know if this is a result of modulo scheduling not being tuned or
not? Have you seen this type of Copy? Any insights are greatly appreciated.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">Thanks<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">Ehsan<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"><o:p> </o:p></span></p>
<div>
<div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal" align="left" style="text-align:left"><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""> llvm-dev [mailto:llvm-dev-bounces@lists.llvm.org]
<b>On Behalf Of </b>Brendon Cahoon via llvm-dev<br>
<b>Sent:</b> Wednesday, May 31, 2017 8:00 PM<br>
<b>To:</b> zhangqiang (CO); llvm-dev@lists.llvm.org<br>
<b>Subject:</b> Re: [llvm-dev] Some questions about software pipeline in LLVM 4.0.0<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal" align="left" style="text-align:left"><o:p> </o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt">Hi - I replied to the original sender only by mistake. Sorry about that.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt">When we started working on the pipeliner, and added it before the scheduler, we also were concerned that the scheduler or other passes would undo the work of the pipeliner. The initial thought was that we
would add information (using metadata or some other way like you’ve suggested) to the basic block to tell the scheduler not to schedule the block. It turns out, that for us, we never needed to do so. It was pretty rare that the scheduler would “undo” the
work of the pipeliner. Actually, in the cases that it did, it turned out to be a problem with the scheduler since it wasn’t making good decisions.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt">In general, most of the extra copies that are added by prior to the register allocator are eliminated. Certainly, there are some real copies that end up being generated, but I think it’s better to exclude
the copies from the schedule since most will be eliminated. Otherwise, including the copies in the schedule will require resources that may never be used, which is worse in my opinion.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt">We decided to run the pipeliner on SSA form since the presence of the Phis helps identify recurrences and other dependences. Without the Phis, we need another way to identify recurrences. Also, if it’s done
just prior to register allocation we need to re-generate the liveness information for all the new virtual registers and CFG. Unfortunately, you’re correct – there is a lot of code that deals with Phis. The code that generates the Phis in the swp kernel and
epilogs is a mess and very complicated. This portion of the pipeliner really needs some attention to reduce the complexity and improve readability. This has been on my list for quite a while.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt">While I think we could move the location of the pipeliner, I don’t think the extra work to do so would provide much benefit. In general, we’ve been able to work around the cases when extra copies or instructions
are added, or when the scheduler messes up the kernel. Also, for Hexagon, there are many passes that run after the register that deal with scheduling. If you have specific cases where you’re seeing a problem, it would be interesting to take a look at them.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt">Thanks,<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt">Brendon<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><o:p> </o:p></span></p>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal" align="left" style="text-align:left"><b><span style="font-size:11.0pt">From:</span></b><span style="font-size:11.0pt"> zhangqiang (CO) [<a href="mailto:zhangqiang75@huawei.com">mailto:zhangqiang75@huawei.com</a>]
<br>
<b>Sent:</b> Thursday, May 25, 2017 3:33 AM<br>
<b>To:</b> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<b>Cc:</b> <a href="mailto:bcahoon@codeaurora.org">bcahoon@codeaurora.org</a><br>
<b>Subject:</b> Some questions about software pipeline in LLVM 4.0.0<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal" align="left" style="text-align:left"><o:p> </o:p></p>
<p class="MsoNormal">Hi,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I have some questions about the implementation of Software pipeline in MachinePipeliner.cpp.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">First, in hexagon backend, between MachinePipeliner and regalloc pass, there're some other passes like phi eliminate, two-address, register coalescing, which may change or insert intructions like 'copy' in MBB, and swp kernel loop may be
destroyed by these passes. <o:p></o:p></p>
<p class="MsoNormal">Why not put MachinePipeliner just before reg alloc pass like gcc’s modulo scheduler does? In order to keep SSA pattern?
<o:p></o:p></p>
<p class="MsoNormal">I found many codes to process PHI nodes in MachinePipeliner.cpp. So I think if we move MachinePipeliner just before regalloc, it will simplify the data/resource dependency graph for SMS.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Another question, in gcc, there's a flag <b>BB_DISABLE_SCHEDULE</b> in Basic block, which is used by SMS to prevent other schedulers from messing with the loop schedule. So, in llvm , where can I find the similar flag to prevent the machine
scheduler touch the kernel loop?<o:p></o:p></p>
<p class="MsoNormal">I have debug some swp cases(hexagon), and find machine scheduler will re-schedule the SMS kernel loop. Why not add such a flag?<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Best Regards,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Thanks<o:p></o:p></p>
</div>
</body>
</html>