<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)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><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.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
margin-bottom:.0001pt;
text-align:justify;
font-size:10.5pt;
font-family:"Calibri","sans-serif";}
span.BalloonTextChar
{mso-style-name:"Balloon Text Char";
mso-style-priority:99;
mso-style-link:"Balloon Text";
font-family:"Tahoma","sans-serif";}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal0;
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";}
p.msochpdefault, li.msochpdefault, div.msochpdefault
{mso-style-name:msochpdefault;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:10.0pt;
font-family:"Times New Roman","serif";}
span.balloontextchar0
{mso-style-name:balloontextchar;
font-family:"Tahoma","sans-serif";}
span.emailstyle20
{mso-style-name:emailstyle20;
font-family:"Calibri","sans-serif";
color:windowtext;}
span.emailstyle21
{mso-style-name:emailstyle21;
font-family:"Calibri","sans-serif";
color:windowtext;}
span.emailstyle22
{mso-style-name:emailstyle22;
font-family:"Calibri","sans-serif";
color:#1F497D;}
span.emailstyle23
{mso-style-name:emailstyle23;
font-family:"Calibri","sans-serif";
color:windowtext;}
span.EmailStyle26
{mso-style-type:personal-compose;
font-family:"Tahoma","sans-serif";
color:black;}
.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;}
/* List Definitions */
@list l0
{mso-list-id:763261428;
mso-list-type:hybrid;
mso-list-template-ids:-1357339818 -1828965300 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l0:level1
{mso-level-text:%1-;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
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">
<div class="WordSection1">
<div>
<p class="MsoNormal" align="left" style="text-align:left"><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif";color:black">Hi Brendon
<o:p></o:p></span></p>
<div>
<p class="MsoNormal" align="left" style="text-align:left"><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif";color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal" align="left" style="text-align:left"><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif";color:black">Thanks for the answer. I completely agree with your comments. The main reason that I brought up this issue is the following:
Inserting a COPY instruction that cannot be eliminated, means that the loop has an instruction that was not taken into account during modulo scheduling analysis. If we see these kind of copies frequently enough, do you think it is worthwhile to work on the
algorithm, so these instructions are predicted and taken into account during the scheduling? Or maybe we already do this and I am not aware of it?<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" align="left" style="text-align:left"><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif";color:black"><o:p> </o:p></span></p>
<p class="MsoNormal" align="left" style="text-align:left"><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif";color:black">Some other remarks/questions:<o:p></o:p></span></p>
<p class="MsoNormal" align="left" style="text-align:left"><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif";color:black"><o:p> </o:p></span></p>
<p class="MsoNormal" align="left" style="text-align:left"><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif";color:black">IIUC, these kind of copies will be generated even if we implement SMS after register coalescing. Is this correct?<o:p></o:p></span></p>
<p class="MsoNormal" align="left" style="text-align:left"><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif";color:black"><o:p> </o:p></span></p>
<p class="MsoNormal" align="left" style="text-align:left"><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif";color:black">For us, so far we have enabled machine pipeliner for our backend and we see these kind of copy generated frequently for our
workloads. Some times multiple copies inserted in a relatively small loop. IIUC, you don’t see it frequently though. Is that correct?<o:p></o:p></span></p>
<p class="MsoNormal" align="left" style="text-align:left"><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif";color:black"><o:p> </o:p></span></p>
<p class="MsoNormal" align="left" style="text-align:left"><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif";color:black">Thanks<o:p></o:p></span></p>
<p class="MsoNormal" align="left" style="text-align:left"><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif";color:black">Ehsan<o:p></o:p></span></p>
<p class="MsoNormal" align="left" style="text-align:left"><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif";color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal" align="left" style="text-align:left"><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif";color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal" align="left" style="text-align:left"><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif";color:black"><o:p> </o:p></span></p>
<div>
<div class="MsoNormal" align="center" style="text-align:center"><span style="font-size:12.0pt;font-family:"Times New Roman","serif";color:black">
<hr size="2" width="100%" align="center">
</span></div>
<div id="divRpF525237">
<p class="MsoNormal" align="left" style="margin-bottom:12.0pt;text-align:left"><b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif";color:black">From:</span></b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif";color:black"> Brendon
Cahoon [bcahoon@codeaurora.org]<br>
<b>Sent:</b> Monday, June 26, 2017 6:22 PM<br>
<b>To:</b> Ehsan Amiri<br>
<b>Cc:</b> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<b>Subject:</b> RE: [llvm-dev] Some questions about software pipeline in LLVM 4.0.0</span><span style="font-size:12.0pt;font-family:"Times New Roman","serif";color:black"><o:p></o:p></span></p>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black">Hi Ehsan,</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black">In some cases modulo scheduling will insert copy instruction that end up as real copies in the final code. It unavoidable in some cases. For example, let’s say a instruction defining a value
is scheduled in the first iteration, but one of its uses is scheduled two iterations later. In this case, the kernel needs to create a copy because there will be two values live in the kernel, from two other iterations.</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> = R1 // use of the value from iteration n-2</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> = R0 // use of the value from iteration n-1</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> R0 = insn // def at iteration n</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> R1 = R0 </span>
<span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black">If all the uses of an instruction occur at most one iteration away, and the uses appear before the definition, then the copies should be coalesced away.</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black">In the examples that you show below, it all depends in which iteration each instruction is scheduled and/or the order in which the instructions are scheduled.</span><span style="color:black"><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>;</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"> %vreg61<def> = INSN1 %vreg1, %vreg73;</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"> %vreg62<def> = INSN2 %vreg73, %vreg5;</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"> %vreg64<def> = INSN1 %vreg2, %vreg73;</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black">For some reason, the instruction defining vreg64 was scheduled after the instruction defining vreg62, which causes the copy to be generated. Then, the question is why did that happen? That can
be hard to answer without seeing the debug output from the pipeliner. In what order were the instructions scheduled? I would assume that its either vreg73, vreg61, vreg64, and then vreg62 , or it’s the opposite order. If that’s the case, then there was a
cycle gap in between the scheduling of vreg61 and vreg64, so vreg62 was inserted in between them. Perhaps, there are multi-cycle latencies that left the hole? Also, can multiple instructions be executed in parallel in the same cycle?</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black">Let me know if any of that isn’t clear. I apologize for the delay in replying to your original email.</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black">Thanks,</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black">Brendon</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><span style="color:black"><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;color:black">From:</span></b><span style="font-size:11.0pt;color:black"> Ehsan Amiri [<a href="mailto:ehsan.amiri@huawei.com">mailto:ehsan.amiri@huawei.com</a>]
<br>
<b>Sent:</b> Monday, June 19, 2017 1:55 AM<br>
<b>To:</b> Brendon Cahoon <<a href="mailto:bcahoon@codeaurora.org">bcahoon@codeaurora.org</a>><br>
<b>Cc:</b> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<b>Subject:</b> RE: [llvm-dev] Some questions about software pipeline in LLVM 4.0.0</span><span style="color:black"><o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal" align="left" style="text-align:left"><span style="color:black"> <o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">Hi Brendon</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"> </span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><i><span style="font-size:11.0pt;color:black">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><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"> </span><span style="color:black"><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. </span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"> </span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">For example before modulo scheduling I have
</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"> </span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">%vreg6<def> = PHI %vreg23, <BB#1>, %vreg17</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">%vreg25<def> = INSN1 %vreg1, %vreg6;</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">%</span><span style="color:black">
</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</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">%</span><span style="color:black">
</span><span style="font-size:11.0pt;color:#1F497D">vreg17<def> = INSN2 %vreg6, %vreg5;</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"> </span><span style="color:black"><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:</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"> </span><span style="color:black"><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>;</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">%vreg61<def> = INSN1 %vreg1, %vreg73;</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">%vreg62<def> = INSN2 %vreg73, %vreg5;</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">%vreg64<def> = INSN1 %vreg2, %vreg73;</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"> </span><span style="color:black"><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. </span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"> </span><span style="color:black"><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.</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"> </span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">Thanks</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">Ehsan</span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"> </span><span style="color:black"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="color:black"> <o:p></o:p></span></p>
</div>
</div>
</div>
</div>
</div>
</div>
</body>
</html>