<div dir="ltr"><div>Thank You so much.</div><div><br></div><div>I plan to begin with the 2nd option i.e <span style="font-size:11pt;font-family:"Calibri",sans-serif;color:rgb(31,73,125)">tweaking Ashutosh’s patch</span>.</div><div>How should i begin working on this?</div><div>Please guide<br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Aug 4, 2018 at 12:30 AM, Saito, Hideki <span dir="ltr"><<a href="mailto:hideki.saito@intel.com" target="_blank">hideki.saito@intel.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div link="blue" vlink="purple" lang="EN-US">
<div class="m_-3281591399880670589WordSection1"><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">>it cannot afford large size masks for large vectors<span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> <u></u></span></p>
</span><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">So, even a standard way of vectorizing remainder in masked or unmasked fashion wouldn’t work, I suppose. Ouch.<u></u><u></u></span></p>
<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"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">I suppose VPlan should be able to model this kind of gigantic remainder vector code (when the time comes). Not pretty at all, though.<u></u><u></u></span></p>
<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"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">Now, be fully aware that Direction #2 is really a poor (or rather extremely poor) person’s remainder loop vectorization approach. Nowhere close to do it right.
If you really have to go down that path…… the following would be the basics steps.<u></u><u></u></span></p>
<p class="MsoNormal"><a name="m_-3281591399880670589__MailEndCompose"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> <u></u></span></a></p>
<p class="m_-3281591399880670589MsoListParagraph"><u></u><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><span>1)<span style="font:7.0pt "Times New Roman"">
</span></span></span><u></u><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">First, look at the comments in createVectorizedLoopSkeleton()<wbr>. “old scalar loop to handle remainder” is the one you want to vectorize again.<br>
Near the end of that function, LoopScalarBody is set. This is the loop body of interest. OrigLoop becomes the scalar Loop. First, try attaching<br>
a new metadata (with VF info) to it. <u></u><u></u></span></p>
<p class="m_-3281591399880670589MsoListParagraph"><u></u><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><span>2)<span style="font:7.0pt "Times New Roman"">
</span></span></span><u></u><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">Create a RemainderVectorizePass, very similar to LoopVectorizePass, but let it work only on the loops that has the metadata. Add it to IPO/PassManagerBuilder<br>
right after LoopVectorize. You could also try adding a state in LoopVectorize instead of creating a RemainderVectorizePass. You can then read the metadata<br>
and try to vectorize the loop with half the VF. This will result in another remainder loop. Attach (or modify) the metadata with the halved VF.<u></u><u></u></span></p>
<p class="m_-3281591399880670589MsoListParagraph"><u></u><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><span>3)<span style="font:7.0pt "Times New Roman"">
</span></span></span><u></u><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">You may have to do some cleanup of primary IV between LoopVectorize and RemainderVectorize. If LoopVectorizationLegality chokes in RemainderVectorize<br>
(i.e., thinks the loop is not legal to vectorize), try resolving what it is complaining. Legality should be the same between main vector loop and remainder ------ in theory.<u></u><u></u></span></p>
<p class="m_-3281591399880670589MsoListParagraph"><u></u><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><span>4)<span style="font:7.0pt "Times New Roman"">
</span></span></span><u></u><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">Once you get to that point, just run RemainderVectorize enough times, until VF is small enough.<u></u><u></u></span></p>
<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"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">This shouldn’t require much knowledge on LoopVectorize if things go nice and smooth.<u></u><u></u></span></p>
<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"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">If you opt to go with tweaking Ashutosh’s patch,<u></u><u></u></span></p>
<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"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">Ashutosh’s patch (<a href="https://reviews.llvm.org/D30247" target="_blank">https://reviews.llvm.org/<wbr>D30247</a> ) is doing what I wrote above within LoopVectorize (thus it can skip many things since data structures are still
alive), through </span><span style="font-size:9.0pt;font-family:Consolas;color:black">createVectorEpilog()</span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">, instantiating InnerLoopVectorizer inside InnerLoopVectorizer. That
takes care of one remainder loop vectorization step. You need to modify so that it can do more than one step (like using an vector of EpilogLoopInfo). If you struggle in convincing LoopVectorizationLegality to think remainder is just as legal to vectorize
as main vector loop, you should be able to avoid that if you take this approach.<u></u><u></u></span></p>
<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"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">You still have two approaches to unblock yourself in the short term.<u></u><u></u></span></p>
<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"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">Thanks,<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">Hideki<u></u><u></u></span></p>
<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"><a name="m_-3281591399880670589______replyseparator"></a><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"> hameeza ahmed [mailto:<a href="mailto:hahmed2305@gmail.com" target="_blank">hahmed2305@gmail.com</a>]
<br>
<b>Sent:</b> Friday, August 03, 2018 10:58 AM<br>
<b>To:</b> Saito, Hideki <<a href="mailto:hideki.saito@intel.com" target="_blank">hideki.saito@intel.com</a>><br>
<b>Cc:</b> Craig Topper <<a href="mailto:craig.topper@gmail.com" target="_blank">craig.topper@gmail.com</a>>; Hal Finkel <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>>; Friedman, Eli <<a href="mailto:efriedma@codeaurora.org" target="_blank">efriedma@codeaurora.org</a>>; <a href="mailto:ashutosh.nema@amd.com" target="_blank">ashutosh.nema@amd.com</a>; <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<b>Subject:</b> Re: Vectorizing remainder loop<u></u><u></u></span></p><div><div class="h5">
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<div>
<p class="MsoNormal">Thank You so much...<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">The hardware is designed already and it cannot afford large size masks for large vectors. So I m opting for direction 2. Also I did try the patch but i was getting some errors.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Can you please guide me how to proceed with direction 2?<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Thank You<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">Regards<u></u><u></u></p>
</div>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<p class="MsoNormal">On Fri, Aug 3, 2018 at 3:28 AM, Saito, Hideki <<a href="mailto:hideki.saito@intel.com" target="_blank">hideki.saito@intel.com</a>> wrote:<u></u><u></u></p>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<p class="MsoNormal" style="margin-bottom:12.0pt"><br>
Hi Hameeza,<br>
<br>
Aside from Ashutosh's patch.....<br>
<br>
When the vector width is that large, we can't keep vectorizing remainder like below. It'll be a huge code size if nothing else ---- hitting ITLB miss because of this is very bad, for example.<br>
VF=2048 // main vector loop<br>
VF=1024 // vectorized remainder 1<br>
VF=512 // vectorized remainder 2<br>
...<br>
Vectorize remainder until trip count is small enough for scalar execution.<br>
<br>
Direction #1<br>
Does your HW support efficient masking? If so, the first thing to try is VF=2048 with masking so that you won't have any remainder loop. In other words, bump up the trip count to the multiple of 2048 and then have an IF branch inside the loop body so that beyond
the original trip count is a no-op. Then vectorize that loop.<br>
<br>
For (i=0;i<N;i++){<br>
body<br>
}<br>
==><br>
For (i=0;i<M;i++){ // where M is a multiple of 2048<br>
If (I < N) {<br>
Body<br>
}<br>
}<br>
<br>
If your HW can't execute vector version of the above loop efficiently enough, it's already busted. Typically, when VF is that large, what you'll get in the remainder is masked vector like below, and vec_remainder_body is reasonably hot as you say in your original
mail. As such, remainder loop vectorization isn't a solution for that problem.<br>
<br>
for (i=0;i<N;i+=2048){<br>
Vec_body<br>
}<br>
for (i<M;i+=1024){ // where M is the smallest multiple of 1024 over N<br>
If (I < N) {<br>
Vec_Remainder_Body<br>
}<br>
}<br>
<br>
If your HW designers insist that the compiler to generate<br>
VF=2048 // main vector loop<br>
VF=1024 // vectorized remainder 1<br>
VF=512 // vectorized remainder 2<br>
...<br>
Remainder is small enough for scalar.<br>
I suggest you go back and tell them to reconsider the HW design such that the Direction #1 works well enough on the HW.<br>
<br>
Direction #2<br>
In the meantime, if you are really stuck in the situation (i.e,, HW is already built and you don't have much time), the simplest thing for you to do is to run the LV second (third/fourth/...) time, after marking the remainder loop with the metadata so that
you know which loops you want to deal with in the second round. It's very much of a hack but it'll be a small change you need to make and that way you are not much impacted by other changes VPlan project is making. If you have a major change outside of the
trunk, you may be hit hard.<br>
<br>
Direction #3<br>
If you are given time to do the right implementation of remainder loop vectorization, please join the VPlan bandwagon and work on it there. Major development like this should happen on VPlans. Please let us know if you can do that. Ashutosh, how about you?<br>
<br>
Hopefully, one or more of the four alternative directions to consider, including Ashutosh's patch, would work for you.<br>
<br>
Thanks,<br>
Hideki<br>
-------------------<br>
Date: Mon, 30 Jul 2018 05:16:15 +0000<br>
From: "Nema, Ashutosh via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br>
<span class="m_-3281591399880670589im">To: hameeza ahmed <<a href="mailto:hahmed2305@gmail.com" target="_blank">hahmed2305@gmail.com</a>>, Craig Topper</span><br>
<span class="m_-3281591399880670589im"> <<a href="mailto:craig.topper@gmail.com" target="_blank">craig.topper@gmail.com</a>>, Hal Finkel <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>>, "Friedman,</span><br>
<span class="m_-3281591399880670589im"> Eli" <<a href="mailto:efriedma@codeaurora.org" target="_blank">efriedma@codeaurora.org</a>></span><br>
<span class="m_-3281591399880670589im">Cc: llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span><br>
<span class="m_-3281591399880670589im">Subject: Re: [llvm-dev] Vectorizing remainder loop</span><br>
<br>
<span class="m_-3281591399880670589im">Hi Hameeza,</span><br>
<br>
<span class="m_-3281591399880670589im">At this point Loop Vectorizer does not have capability to vectorize epilog/remainder loop.</span><br>
<span class="m_-3281591399880670589im">Sometime back there is an RFC on epilog loop vectorization but it did not went through because of concerns.</span><br>
<span class="m_-3281591399880670589im">This RFC has a patch as well, maybe you can give a try with it.</span><br>
<span class="m_-3281591399880670589im"><a href="http://llvm.1065342.n5.nabble.com/llvm-dev-Proposal-RFC-Epilog-loop-vectorization-tt106322.html#none" target="_blank">http://llvm.1065342.n5.nabble.<wbr>com/llvm-dev-Proposal-RFC-<wbr>Epilog-loop-vectorization-<wbr>tt106322.html#none</a></span><br>
<br>
<span class="m_-3281591399880670589im">- Ashutosh</span><br>
<br>
<span class="m_-3281591399880670589im">From: llvm-dev <<a href="mailto:llvm-dev-bounces@lists.llvm.org" target="_blank">llvm-dev-bounces@lists.llvm.<wbr>org</a>> On Behalf Of hameeza ahmed via llvm-dev</span><br>
<span class="m_-3281591399880670589im">Sent: Sunday, July 29, 2018 10:24 PM</span><br>
<span class="m_-3281591399880670589im">To: llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>>; Craig Topper <<a href="mailto:craig.topper@gmail.com" target="_blank">craig.topper@gmail.com</a>>; Hal Finkel <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>>; Friedman,
Eli <<a href="mailto:efriedma@codeaurora.org" target="_blank">efriedma@codeaurora.org</a>></span><br>
<span class="m_-3281591399880670589im">Subject: Re: [llvm-dev] Vectorizing remainder loop</span><br>
<br>
<span class="m_-3281591399880670589im">Please help in solving this issue. the issue of scalar remainder loop is really big and significant with large vector widths.</span><br>
<br>
<span class="m_-3281591399880670589im">Please help</span><br>
<br>
<span class="m_-3281591399880670589im">Thank You</span><u></u><u></u></p>
<div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt">On Sun, Jul 29, 2018 at 2:52 PM, hameeza ahmed <<a href="mailto:hahmed2305@gmail.com" target="_blank">hahmed2305@gmail.com</a><mailto:<a href="mailto:hahmed2305@gmail.com" target="_blank">h<wbr>ahmed2305@gmail.com</a>>> wrote:<br>
Hello, I m working on a hardware with very large vector width till v2048. Now when I vectorize using llvm default vectorizer maximum 2047 iterations are scalar remainder loop. These are not vectorized by llvm which increases the cost. However these should be
vectorized using next available vector width I.e v1024, v512, v256, v128, v64, v32, v16, v8, v4.....<br>
<br>
The issue of scalar remainder loop has been there in llvm but this issue is enhanced and can't be ignored with large vector width. This is very important and significant to solve this issue.<br>
<br>
Please help. I m trying to see loopvectorizer.cpp but unable to figure out actual code to make changes.<br>
<br>
It's very important for me to solve this issue.<br>
<br>
Please help.<br>
<br>
Thank you<br>
<br>
<u></u><u></u></p>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
</div></div></div>
</div>
</blockquote></div><br></div>