<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=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Helvetica;
panose-1:2 11 6 4 2 2 2 2 2 4;}
@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:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
@font-face
{font-family:"Lucida Sans Unicode";
panose-1:2 11 6 2 3 5 4 2 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;
color:black;}
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
{mso-style-priority:99;
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;
color:black;}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0in;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";
color:black;}
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;
font-size:11.0pt;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:Consolas;
color:black;}
span.apple-converted-space
{mso-style-name:apple-converted-space;}
span.EmailStyle22
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle23
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle24
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.EmailStyle25
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.EmailStyle26
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle27
{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;}
/* List Definitions */
@list l0
{mso-list-id:105659368;
mso-list-type:hybrid;
mso-list-template-ids:-818480336 67698711 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l0:level1
{mso-level-number-format:alpha-lower;
mso-level-text:"%1\)";
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l1
{mso-list-id:1638341594;
mso-list-type:hybrid;
mso-list-template-ids:-735140576 67698711 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l1:level1
{mso-level-number-format:alpha-lower;
mso-level-text:"%1\)";
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l1:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l1:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l1:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l1:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l1:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l1:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l1:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l1: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 bgcolor="white" lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><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" style="margin-left:.5in"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:windowtext">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:windowtext"> Zaks, Ayal [mailto:ayal.zaks@intel.com]
<br>
<b>Sent:</b> Tuesday, February 28, 2017 2:40 PM<br>
<b>To:</b> Nema, Ashutosh <Ashutosh.Nema@amd.com>; Hal Finkel <hfinkel@anl.gov>; Adam Nemet <anemet@apple.com>; Renato Golin <renato.golin@linaro.org>; mkuper@google.com; Mehdi Amini <mehdi.amini@apple.com><br>
<b>Cc:</b> llvm-dev <llvm-dev@lists.llvm.org><br>
<b>Subject:</b> RE: [llvm-dev] [Proposal][RFC] Epilog loop vectorization<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">Thanks for looking into this.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">1) Issues with re running vectorizer:<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">Vectorizer might generate redundant alias checks while vectorizing epilog loop.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">Redundant alias checks are expensive, we like to reuse the results of already computed alias checks.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">With metadata we can limit the width of epilog loop, but not sure about reusing alias check result.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">Any thoughts on rerunning vectorizer with reusing the alias check result ?<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">2) Best & worst case for epilog vectorization.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">Epilog vectorization incurs additional cost of checks which decides to execute either epilog vector loop or scalar loop.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">These checks are:<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-.25in;mso-list:l0 level1 lfo2">
<![if !supportLists]><span style="mso-list:Ignore">a)<span style="font:7.0pt "Times New Roman"">
</span></span><![endif]>Min trip count check for epilog vector loop.<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-.25in;mso-list:l0 level1 lfo2">
<![if !supportLists]><span style="mso-list:Ignore">b)<span style="font:7.0pt "Times New Roman"">
</span></span><![endif]>Alias result check (only if alias check is generated for first vector version)<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">Where the epilog vector trip count is large epilog vectorization with profitable width likely to give gain. Worst case probably after these additional checks executing the scalar loop.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">3) Benchmarking & results:<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">We have observed 4% improvement in one of our internal benchmark.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">Tried CPU2006 and didn’t found any degrade & improvements.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">On code size increase I have not yet verified yet will check and get back.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">4) What should be the minimum first vector loop width to enable epilog vectorization.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">This count should not be small as it may degrade the performance, with my limited tests I have observed 16 is a point it shows gains with one of our internal benchmark. This require more experiments & testing to
decide what should be the minimum width.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">This minimum width is meant to be a lower bound on EpilogVF, right? The main loop has no such lower bound, but instead uses its cost
model to find the best VF from among {2,4,8,…,maxVF}. Can the remainder loop rely on its cost model as well, possibly improved to better consider short trip counts, w/o enforcing a lower bound? OTOH, if there are obvious lower-bounds, using them for both loops
can save compile-time.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Epilog vectorization is more likely to show gains when high possibility of remainder iterations, this is only possible when the first vector version is vectorized
with large trip count. For this I have kept one threshold in the implementation with default value 16, when first vector version width goes beyond this threshold then only enable epilog vectorization. Epilog vector version width will be less than first vector
version. In the current implementation both first & epilog vector loop profitability get decided by the same costing step. Costing tries to find all profitable vector factor and later for epilog vectorization it finds next profitable vector factor in already
computed profitable vectors.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in">5) Unrolling issues:<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">As Ayal mentioned with large unroll factor the next profitable EpilogVF could be equal to VF.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">With the same reason the current patch enforces UF=1, as unrolling can minimize the possibility of executing epilog vector loop.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">On the contrary: unrolling should promote executing an epilog vector loop. Put differently, if unrolling would have been applied to the
vectorized loop after vectorization, instead of doing the vectorization and unrolling together, we would have had left-over vector iterations.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">My understanding might be wrong here, in the Loop vectorizer first it tries to find the profitable vector factor from among {2,4,6…MaxVF}, then it tries to find
the unroll factor. Does it mean that even without unroll vector loop is profitable with identified vector factor (in addition to it unrolling may give more gains) ?<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Epilog vector loop has very low iterations possibility, and unrolling can further reduce this. i.e. if first loop is vectorized with VF16 then possibility for
epilog scalar loop iterations are 15, if vectorizer generates epilog vector loop with width 4 then it can cater 4 to 15 scalar iterations, but if epilog vector loop get unrolled by 2 then it can only cater 8-15 scalar iterations.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">We have to little careful with unroll, not sure forcing UF=1 for epilog vector loop is a good idea.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Ayal.<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">Example to understand the new layout:<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">void foo (char *A, char *B, char *C, int len) {<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in"> int i = 0;<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in"> for (i=0 ; i< len; i++)<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in"> A[i] = B[i] + C[i];<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">}<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">This loop get vectorize with width 32 and epilog loop get vectorized with width 8.<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-.25in;mso-list:l1 level1 lfo4">
<![if !supportLists]><span style="mso-list:Ignore">a)<span style="font:7.0pt "Times New Roman"">
</span></span><![endif]>Please check attached IR(test.ll)<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-.25in;mso-list:l1 level1 lfo4">
<![if !supportLists]><span style="mso-list:Ignore">b)<span style="font:7.0pt "Times New Roman"">
</span></span><![endif]>To understand how alias check result got used, check temporary “acr.val” usage.
<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">Regards,<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:1.0in">Ashutosh<span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><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" style="margin-left:1.0in"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:windowtext">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:windowtext"> Zaks, Ayal [<a href="mailto:ayal.zaks@intel.com">mailto:ayal.zaks@intel.com</a>]
<br>
<b>Sent:</b> Sunday, February 26, 2017 10:53 PM<br>
<b>To:</b> Hal Finkel <<a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>>; Adam Nemet <<a href="mailto:anemet@apple.com">anemet@apple.com</a>>; Nema, Ashutosh <<a href="mailto:Ashutosh.Nema@amd.com">Ashutosh.Nema@amd.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> RE: [llvm-dev] [Proposal][RFC] Epilog loop vectorization<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal" style="margin-left:1.0in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">+1 for “</span>just rerun the vectorizer<span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">” on the scalar
remainder loop, as the proposed decision process is broken down into “first determine best VF for main loop, then determine best next EpilogVF for remainder loop” anyhow:<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> const LoopVectorizationCostModel::VectorizationFactor EpilogVF =<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> CM.identifyNextProfitableVF(VF.Width);<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Raising some aspects:<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:1.0in">
<span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">o The unroll factor may also affect the best EpilogVF. For instance, if UF=1 then EpilogVF < VF, as the patch currently enforces. But if UF is larger the next profitable EpilogVF
could be equal to VF.<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">o The scalar loop serves two purposes, as determined by its two pre-headers: either as a default in case runtime dependence checks fail,
or as a remainder loop in which case it is known to be vectorizable with trip count less-than VF*UF (or equal-to it*). Would be good to keep this in mind when rerunning.<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">(*) Note that if original loop requiresScalarEpilogue(), the trip count of the remainder loop may be equal to VF*UF, and/or the vectorized
remainder loop may too require a scalar epilogue.<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">o It should be interesting to see how a single masked iteration that uses the original VF, say for UF=1, works. LV should hopefully
already support most of what’s needed.<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">o The original Trip Count clearly affects the profitability of vectorizing the remainder loop. Would be good to leverage any information
that can be derived about TC either statically or based on profiling, when determining EpilogVF. Potential speedups and overheads/slowdowns could possibly be demonstrated using extreme cases; what would the best and worst cases be? Perhaps TinyTripCountVectorThreshold
is also affected?<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">o Finally, VPlan is currently modeling how to vectorize the loop body according to the potentially profitable VF’s. It’s modelling could
be used to generate vector code for both body and remainder, and to consider their combined, overall cost.<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Ayal.<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><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" style="margin-left:1.0in"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:windowtext">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:windowtext"> llvm-dev [</span><a href="mailto:llvm-dev-bounces@lists.llvm.org"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">mailto:llvm-dev-bounces@lists.llvm.org</span></a><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:windowtext">]
<b>On Behalf Of </b>Hal Finkel via llvm-dev<br>
<b>Sent:</b> Friday, February 24, 2017 00:14<br>
<b>To:</b> Adam Nemet <</span><a href="mailto:anemet@apple.com"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">anemet@apple.com</span></a><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:windowtext">>; Nema, Ashutosh <</span><a href="mailto:Ashutosh.Nema@amd.com"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">Ashutosh.Nema@amd.com</span></a><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:windowtext">><br>
<b>Cc:</b> llvm-dev <</span><a href="mailto:llvm-dev@lists.llvm.org"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">llvm-dev@lists.llvm.org</span></a><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:windowtext">><br>
<b>Subject:</b> Re: [llvm-dev] [Proposal][RFC] Epilog loop vectorization<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal" style="margin-left:1.0in"><o:p> </o:p></p>
<p style="margin-left:1.0in"><o:p> </o:p></p>
<div>
<p class="MsoNormal" style="margin-left:1.0in">On 02/22/2017 11:52 AM, Adam Nemet via llvm-dev wrote:<o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal" style="margin-left:1.0in">Hi Ashutosh,<o:p></o:p></p>
</div>
<p class="MsoNormal" style="margin-left:1.0in"><o:p> </o:p></p>
<div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal" style="margin-left:1.0in">On Feb 22, 2017, at 1:57 AM, Nema, Ashutosh via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<o:p></o:p></p>
</div>
<p class="MsoNormal" style="margin-left:1.0in"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white">Hi,</span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white"> </span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white">This is a proposal about epilog loop vectorization.</span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white"> </span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white">Currently Loop Vectorizer inserts an epilogue loop for handling loops that don’t have known iteration counts.</span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white"> </span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white">The Loop Vectorizer supports loops with an unknown trip count, unknown trip count may not be a multiple of the vector
width, and the vectorizer has to execute the last few iterations as scalar code. It keeps a scalar copy of the loop for the remaining iterations.</span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white"> </span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white">Loop with the large width has a high possibility of executing many scalar iterations.</span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white">i.e. i8 data type with 256bits target register can vectorize with vector width 32, with that maximum trip count possibility
for scalar(epilog) loop is 31, which is significant & worth vectorizing.</span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white"> </span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white">Large vector factor has following challenges:</span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div style="margin-left:.5in">
<p class="MsoNormal" style="margin-left:1.0in;text-indent:-.25in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif">1)</span><span style="font-size:7.0pt"> <span class="apple-converted-space"> </span></span><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white">Possibility
of remainder iteration is substantial.</span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div style="margin-left:.5in">
<p class="MsoNormal" style="margin-left:1.0in;text-indent:-.25in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif">2)</span><span style="font-size:7.0pt"> <span class="apple-converted-space"> </span></span><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white">Actual
trip count at runtime is substantial but not meeting minimum trip count to execute vector loop.</span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white"> </span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white">These challenges can be addressed by mask instructions, but these instructions are limited and may not be available to
all targets.</span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white"> </span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white">By epilog vectorization our aim to vectorize epilog loop where original loop is vectorized with large vector factor and
has a high possibility of executing scalar iterations.</span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white"> </span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white">This require following changes:</span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div style="margin-left:.5in">
<p class="MsoNormal" style="margin-left:1.0in;text-indent:-.25in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif">1)</span><span style="font-size:7.0pt"> <span class="apple-converted-space"> </span></span><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white">Costing:
Preserve all profitable vector factor.</span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div style="margin-left:.5in">
<p class="MsoNormal" style="margin-left:1.0in;text-indent:-.25in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif">2)</span><span style="font-size:7.0pt"> <span class="apple-converted-space"> </span></span><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white">Transform:
Create an additional vector loop with next profitable vector factor.</span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in">Is this something that you propose to be on by default for wide VPU architectures without masking support? I.e. how widely is this applicable? If not then perhaps a better strategy would be to just annotate the
remainder loop with some metadata to limit the vectorization factor and just rerun the vectorizer.<o:p></o:p></p>
</div>
</div>
</blockquote>
<p class="MsoNormal" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:1.0in">
<br>
Why would this solution (annotating the remainder loop to limit vectorization and rerunning the vectorization process) not be preferred regardless?<br>
<br>
One issue that might be relevant here are runtime aliasing checks, which are probably going to be redundant, or partially redundant, between the different vectorized versions. Will we be able to do any necessary cleanup after the fact? Moreover, we often don't
hoist (unswitch) these checks out of inner loops (perhaps because they're inside the trip-count checks?); I wonder if the proposed block structure will make this situation better or worse (or have no overall effect).<br>
<br>
Thanks again,<br>
Hal<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in">Adam<o:p></o:p></p>
</div>
<p class="MsoNormal" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:1.0in">
<o:p> </o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white"> </span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white">Please refer attached file (BlockLayout.png) for the details about transformed block layout.</span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white"> </span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white">Patch is available at:<span class="apple-converted-space"> </span></span><a href="https://reviews.llvm.org/D30247"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;color:#954F72;background:white">https://reviews.llvm.org/D30247</span></a><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white"> </span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white">Regards,</span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Lucida Sans Unicode",sans-serif;background:white">Ashutosh</span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> <o:p></o:p></span></p>
</div>
<p class="MsoNormal" style="margin-left:1.0in"><BlockLayout.png><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif">_______________________________________________<br>
LLVM Developers mailing list<br>
</span><a href="mailto:llvm-dev@lists.llvm.org"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif;color:#954F72">llvm-dev@lists.llvm.org</span></a><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif"><br>
</span><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif;color:#954F72">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</span></a><o:p></o:p></p>
</div>
</blockquote>
</div>
<p class="MsoNormal" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:1.0in">
<o:p> </o:p></p>
<pre style="margin-left:1.0in">_______________________________________________<o:p></o:p></pre>
<pre style="margin-left:1.0in">LLVM Developers mailing list<o:p></o:p></pre>
<pre style="margin-left:1.0in"><a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><o:p></o:p></pre>
<pre style="margin-left:1.0in"><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><o:p></o:p></pre>
</blockquote>
<p class="MsoNormal" style="mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:1.0in">
<o:p> </o:p></p>
<pre style="margin-left:1.0in">-- <o:p></o:p></pre>
<pre style="margin-left:1.0in">Hal Finkel<o:p></o:p></pre>
<pre style="margin-left:1.0in">Lead, Compiler Technology and Programming Languages<o:p></o:p></pre>
<pre style="margin-left:1.0in">Leadership Computing Facility<o:p></o:p></pre>
<pre style="margin-left:1.0in">Argonne National Laboratory<o:p></o:p></pre>
<p style="margin-left:1.0in">---------------------------------------------------------------------<br>
Intel Israel (74) Limited<o:p></o:p></p>
<p style="margin-left:1.0in">This e-mail and any attachments may contain confidential material for<br>
the sole use of the intended recipient(s). Any review or distribution<br>
by others is strictly prohibited. If you are not the intended<br>
recipient, please contact the sender and delete all copies.<o:p></o:p></p>
<p style="margin-left:.5in">---------------------------------------------------------------------<br>
Intel Israel (74) Limited<o:p></o:p></p>
<p style="margin-left:.5in">This e-mail and any attachments may contain confidential material for<br>
the sole use of the intended recipient(s). Any review or distribution<br>
by others is strictly prohibited. If you are not the intended<br>
recipient, please contact the sender and delete all copies.<o:p></o:p></p>
</div>
</body>
</html>