Vectorizing remainder loop

Hi Hameeza,

Aside from Ashutosh's patch.....

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.
  VF=2048 // main vector loop
  VF=1024 // vectorized remainder 1
  VF=512 // vectorized remainder 2
  ...
  Vectorize remainder until trip count is small enough for scalar execution.

Direction #1
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.

  For (i=0;i<N;i++){
    body
  }
==>
  For (i=0;i<M;i++){ // where M is a multiple of 2048
    If (I < N) {
      Body
    }
  }

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.

  for (i=0;i<N;i+=2048){
    Vec_body
  }
  for (i<M;i+=1024){ // where M is the smallest multiple of 1024 over N
    If (I < N) {
      Vec_Remainder_Body
    }
  }

If your HW designers insist that the compiler to generate
  VF=2048 // main vector loop
  VF=1024 // vectorized remainder 1
  VF=512 // vectorized remainder 2
  ...
  Remainder is small enough for scalar.
I suggest you go back and tell them to reconsider the HW design such that the Direction #1 works well enough on the HW.

Direction #2
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.

Direction #3
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?

Hopefully, one or more of the four alternative directions to consider, including Ashutosh's patch, would work for you.

Thanks,
Hideki

Thank You so much…
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.

Can you please guide me how to proceed with direction 2?

Thank You
Regards

it cannot afford large size masks for large vectors

So, even a standard way of vectorizing remainder in masked or unmasked fashion wouldn’t work, I suppose. Ouch.

I suppose VPlan should be able to model this kind of gigantic remainder vector code (when the time comes). Not pretty at all, though.

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.

  1. First, look at the comments in createVectorizedLoopSkeleton(). “old scalar loop to handle remainder” is the one you want to vectorize again.
    Near the end of that function, LoopScalarBody is set. This is the loop body of interest. OrigLoop becomes the scalar Loop. First, try attaching
    a new metadata (with VF info) to it.

  2. Create a RemainderVectorizePass, very similar to LoopVectorizePass, but let it work only on the loops that has the metadata. Add it to IPO/PassManagerBuilder
    right after LoopVectorize. You could also try adding a state in LoopVectorize instead of creating a RemainderVectorizePass. You can then read the metadata
    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.

  3. You may have to do some cleanup of primary IV between LoopVectorize and RemainderVectorize. If LoopVectorizationLegality chokes in RemainderVectorize
    (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.

  4. Once you get to that point, just run RemainderVectorize enough times, until VF is small enough.

This shouldn’t require much knowledge on LoopVectorize if things go nice and smooth.

If you opt to go with tweaking Ashutosh’s patch,

Ashutosh’s patch (https://reviews.llvm.org/D30247 ) is doing what I wrote above within LoopVectorize (thus it can skip many things since data structures are still alive), through createVectorEpilog(), 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.

You still have two approaches to unblock yourself in the short term.

Thanks,

Hideki

Thank You so much.

I plan to begin with the 2nd option i.e tweaking Ashutosh’s patch.
How should i begin working on this?
Please guide

I’m looking at his patch deeply enough for the first time. Please take that into account.

  1. Start from making his patch work again.

  2. Study how EpilogVectorizationInfo is passed around.

First vectorization happens at Line 8013-8016 in the patch. It passes EpilogVectorizationInfo with nullptr to EpilogLoopInfo.
Remainder vectorization happens at line 3400-3403 in createVectorEpilog(). This one passes EpilogVectorizationInfo with newly created EpilogLoopInfo.
Notice that this second vectorization is called from InnerLoopVectorizer::vectorize().

So, the call structure is already like below, which is actually what you need. So, what you need to do is to check whether this recursion is working.

vectorize() // first instance of InnerLoopVectorizer

createVectorEpilog()

vectorize() // second instance of InnerLoopVectorizer

createVectorEpilog()

Hopefully, Ashutosh, the author of the patch, can help you more.