<div dir="ltr">Sorry, you're right, that really wasn't clear.<div>When I wrote "for free", I meant "without having code in the vectorizer dealing specifically with interleaving".<div><br></div><div>Consider a simple loop, like:</div><div><br></div><div>void hot(int *a, int *b) {<br>#pragma clang loop vectorize_width(4) interleave_count(2)<br>#pragma nounroll<br> for (int i = 0; i < 1000; i++) {<br> a[i] += b[i];<br> }<br> return ;<br>}</div><div><br></div><div>We'll get a vector loop with 4-element vectors, that, when compiling for SSE, gets lowered to:</div><div>.LBB0_3: # %vector.body</div><div> # =>This Inner Loop Header: Depth=1</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>movdqu<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>-16(%rsi,%rax,4), %xmm0</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>movdqu<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>(%rsi,%rax,4), %xmm1</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>movdqu<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>-16(%rdi,%rax,4), %xmm2</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>movdqu<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>(%rdi,%rax,4), %xmm3</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>paddd<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>%xmm0, %xmm2</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>paddd<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>%xmm1, %xmm3</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>movdqu<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>%xmm2, -16(%rdi,%rax,4)</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>movdqu<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>%xmm3, (%rdi,%rax,4)</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>addq<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>$8, %rax</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>cmpq<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>$1004, %rax # imm = 0x3EC</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>jne<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>.LBB0_3</div><div><br></div><div>If we instead have<br></div><div>#pragma clang loop vectorize_width(8) interleave_count(1)<br></div><div><br></div><div>We'll get an 8-wide IR vector loop, but end up with almost the same lowering:</div><div><div>.LBB0_3: # %vector.body</div><div> # =>This Inner Loop Header: Depth=1</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>movdqu<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>16(%rsi,%rax,4), %xmm0</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>movdqu<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>(%rsi,%rax,4), %xmm1</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>movdqu<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>16(%rdi,%rax,4), %xmm2</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>movdqu<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>(%rdi,%rax,4), %xmm3</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>paddd<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>%xmm1, %xmm3</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>paddd<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>%xmm0, %xmm2</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>movdqu<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>%xmm2, 16(%rdi,%rax,4)</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>movdqu<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>%xmm3, (%rdi,%rax,4)</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>addq<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>$8, %rax</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>cmpq<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>$1000, %rax # imm = 0x3E8</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>jne<span class="gmail-Apple-tab-span" style="white-space:pre"> </span>.LBB0_3</div></div><div><br></div><div>Legalization splits each 8-wide operation into two 4-wide operations, achieving almost the same result as vectorizing by a factor of 4 and unrolling by 2.</div></div><div>The question is whether the legalizer is actually up to doing this well in general.</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Jun 15, 2016 at 11:46 PM, Das, Dibyendu via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div lang="EN-US" link="blue" vlink="purple">
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">Its not clear how you would get ‘interleaving for free’.<u></u><u></u></span></p><span class="">
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> llvm-dev [mailto:<a href="mailto:llvm-dev-bounces@lists.llvm.org" target="_blank">llvm-dev-bounces@lists.llvm.org</a>]
<b>On Behalf Of </b>Michael Kuperstein via llvm-dev<br>
<b>Sent:</b> Thursday, June 16, 2016 4:18 AM<br>
<b>To:</b> Hal Finkel <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>>; Nadav Rotem <<a href="mailto:nadav.rotem@me.com" target="_blank">nadav.rotem@me.com</a>>; Ayal Zaks <<a href="mailto:ayal.zaks@intel.com" target="_blank">ayal.zaks@intel.com</a>>; Demikhovsky, Elena <<a href="mailto:elena.demikhovsky@intel.com" target="_blank">elena.demikhovsky@intel.com</a>>; Adam Nemet <<a href="mailto:anemet@apple.com" target="_blank">anemet@apple.com</a>>; Sanjoy Das <<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.com</a>>; James Molloy <<a href="mailto:james.molloy@arm.com" target="_blank">james.molloy@arm.com</a>>;
Matthew Simpson <<a href="mailto:mssimpso@codeaurora.org" target="_blank">mssimpso@codeaurora.org</a>>; Sanjay Patel <<a href="mailto:spatel@rotateright.com" target="_blank">spatel@rotateright.com</a>>; Chandler Carruth <<a href="mailto:chandlerc@google.com" target="_blank">chandlerc@google.com</a>>; David Li <<a href="mailto:davidxl@google.com" target="_blank">davidxl@google.com</a>>; Wei Mi <<a href="mailto:wmi@google.com" target="_blank">wmi@google.com</a>>; Dehao Chen <<a href="mailto:dehao@google.com" target="_blank">dehao@google.com</a>>; Cong Hou <<a href="mailto:congh@google.com" target="_blank">congh@google.com</a>><br>
<b>Cc:</b> Llvm Dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br>
<b>Subject:</b> [llvm-dev] [RFC] Allow loop vectorizer to choose vector widths that generate illegal types<u></u><u></u></span></p>
<p class="MsoNormal"><u></u> <u></u></p>
</span><div>
<p class="MsoNormal">Hello,</p><div><div class="h5"><br>
<br>
Currently the loop vectorizer will, by default, not consider vectorization factors that would make it generate types that do not fit into the target platform's vector registers. That is, if the widest scalar type in the scalar loop is i64, and the platform's
largest vector register is 256-bit wide, we will not consider a VF above 4.<br>
<br>
We have a command line option (-mllvm -vectorizer-maximize-bandwidth), that will choose VFs for consideration based on the narrowest scalar type instead of the widest one, but I don't believe it has been widely tested. If anyone has had an opportunity to play
around with it, I'd love to hear about the results.<br>
<br>
What I'd like to do is:<u></u><u></u></div></div><p></p><div><div class="h5">
<div>
<div>
<p class="MsoNormal">Step 1: Make -vectorizer-maximize-bandwidth the default. This should improve the performance of loops that contain mixed-width types.<br>
Step 2: Remove the artificial width limitation altogether, and base the vectorization factor decision purely on the cost model. This should allow us to get rid of the interleaving code in the loop vectorizer, and get interleaving for "free" from the legalizer
instead.<u></u><u></u></p>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">There are two potential road-blocks I see - the cost-model, and the legalizer. To make this work, we need to:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">a) Model the cost of operations on illegal types better. Right now, what we get is sometimes completely ridiculous (e.g. see <a href="http://reviews.llvm.org/D21251" target="_blank">http://reviews.llvm.org/D21251</a>).<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">b) Make sure the cost model actually stops us when the VF becomes too large. This is mostly a question of correctly estimating the register pressure. In theory, that should not be a issue - we already rely on this estimate to choose the
interleaving factor, so using the same logic to upper-bound the VF directly shouldn't make things worse.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">c) Ensure the legalizer is up to the task of emitting good code for overly wide vectors. I've talked about this with Chandler, and his opinion (Chandler, please correct me if I'm wrong) is that on x86, the legalizer is likely to be able
to handle this. This may not be true for other platforms. So, I'd like to try to make this the default on a platform-by-platform basis, starting with x86.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">What do you think? Does this seem like a step in the right direction? Anything important I'm missing?<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Thanks,<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> Michael<u></u><u></u></p>
</div>
</div>
</div>
</div></div></div>
</div>
</div>
<br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
<br></blockquote></div><br></div>