[RISCV] Convert interleaved store with tail gaps only into strided segment store

[Mel-Chen]

Consider the interleave store with tail gap only:

 for (int i = 0; i < n; i++) {
   a[3*i + 0] = i;
   a[3*i + 1] = i;
   // No access a[3*i + 2] 
 }

Currently, the vectorizer can converts it into a widen masked stores. When the gap mask has only a single true-to-false transition across the lanes, we can try to convert it into a vssseg instruction in the InterleavedAccessPass. I believe this could serve as a good starting point for supporting strided segment instructions.

Note: Masked load/store instructions can only represent strided segment accesses with compile-time constant stride. For runtime stride cases, alternative IR constructs are still required.

@mshockwave

[llvmbot]

@llvm/issue-subscribers-backend-risc-v

Author: Mel Chen (Mel-Chen)

Consider the interleave store with tail gap only: ``` for (int i = 0; i < n; i++) { a[3*i + 0] = i; a[3*i + 1] = i; // No access a[3*i + 2] } ``` Currently, the vectorizer can converts it into a widen masked stores. When the gap mask has only a single true-to-false transition across the lanes, we can try to convert it into a vssseg instruction in the InterleavedAccessPass. I believe this could serve as a good starting point for supporting strided segment instructions.

Note: Masked load/store instructions can only represent strided segment accesses with compile-time constant stride. For runtime stride cases, alternative IR constructs are still required.

@mshockwave

[Mel-Chen]

cc. @topperc @alexey-bataev @lukel97 @preames @LiqinWeng @wangpc-pp @arcbbb @ElvisWang123

[preames]

This is definitely possible, but is it profitable? A strided segment store is a rather complex memory operation. Do we have examples of hardware where trading several (non-segment) strided stores for one segment strided is profitable?

(I'm asking from ignorance, I have not gone and tried to answer this question for any piece of hardware yet.)

[topperc]

This is definitely possible, but is it profitable? A strided segment store is a rather complex memory operation. Do we have examples of hardware where trading several (non-segment) strided stores for one segment strided is profitable?

(I'm asking from ignorance, I have not gone and tried to answer this question for any piece of hardware yet.)

Strided non-segment stores may execute 1 element per cycle. A strided segment store could execute 1 segment per cycle. So it could be faster, but there maybe some other overhead in the segment store for accessing multiple registers.

[mshockwave]

just a FYI that I have a prototype on the codegen side (i.e. InterleavedAccessPass + related TLI hooks) to turn masked.load / vp.load with mask 110110110110 + factor of 3 deinterleaving (via shufflevector) into vlsseg2 (instead of vlseg3) with constant stride to skip the last field. I could send out the patches by this week.

[mshockwave]

just a FYI that I have a prototype on the codegen side (i.e. InterleavedAccessPass + related TLI hooks) to turn masked.load / vp.load with mask 110110110110 + factor of 3 deinterleaving (via shufflevector) into vlsseg2 (instead of vlseg3) with constant stride to skip the last field. I could send out the patches by this week.

PR: #151612 (for loads)

[lukel97]

If we want to support scalable vlseg/vsseg it looks like the pattern to match is much closer that of a strided access, i.e. we don't emit a "strided [de]interleave" intrinsic currently but a getelementptr indexed by a scaled stepvector: https://godbolt.org/z/zqT3xdcMW

It might be easier to match it in RISCVGatherScatterLowering? Although I'm aware you're trying to move this into the loop vectorizer @Mel-Chen.

[Mel-Chen]

just a FYI that I have a prototype on the codegen side (i.e. InterleavedAccessPass + related TLI hooks) to turn masked.load / vp.load with mask 110110110110 + factor of 3 deinterleaving (via shufflevector) into vlsseg2 (instead of vlseg3) with constant stride to skip the last field. I could send out the patches by this week.

PR: #151612 (for loads)

Yes, that's pretty much it. But could you start with handling stores first? Interleaved loads with gaps are less of a problem — we can still use vlseg. However, interleaved stores with gaps currently can't use vsseg at all. That's why I prefer starting with stores rather than loads.

Support for loads will still be useful in the future. For example, if the interleaved stride (i.e., the factor in InterleaveGroup) is greater than 8, we could split the group in the vectorizer and emit multiple vlsseg/vssseg instructions.

But for now, I’d like to focus on stores. I can take vectorizer part to ensure that interleaved stores with only tail gaps generate wide masked stores. @mshockwave Could you help to take the Interleaved Access pass part?

[Mel-Chen]

If we want to support scalable vlseg/vsseg it looks like the pattern to match is much closer that of a strided access, i.e. we don't emit a "strided [de]interleave" intrinsic currently but a getelementptr indexed by a scaled stepvector: https://godbolt.org/z/zqT3xdcMW

It might be easier to match it in RISCVGatherScatterLowering? Although I'm aware you're trying to move this into the loop vectorizer @Mel-Chen.

Interleaved access is essentially a combination of multiple strided accesses. That’s why, when discussing how to implement strided access in VPlan, I kept bringing up its interaction with interleaved access. Once strided access support has landed, we can then introduce a VPlan-based interleave analysis.

[mshockwave]

just a FYI that I have a prototype on the codegen side (i.e. InterleavedAccessPass + related TLI hooks) to turn masked.load / vp.load with mask 110110110110 + factor of 3 deinterleaving (via shufflevector) into vlsseg2 (instead of vlseg3) with constant stride to skip the last field. I could send out the patches by this week.

PR: #151612 (for loads)

Yes, that's pretty much it. But could you start with handling stores first? Interleaved loads with gaps are less of a problem — we can still use vlseg. However, interleaved stores with gaps currently can't use vsseg at all. That's why I prefer starting with stores rather than loads.

Support for loads will still be useful in the future. For example, if the interleaved stride (i.e., the factor in InterleaveGroup) is greater than 8, we could split the group in the vectorizer and emit multiple vlsseg/vssseg instructions.

But for now, I’d like to focus on stores. I can take vectorizer part to ensure that interleaved stores with only tail gaps generate wide masked stores. @mshockwave Could you help to take the Interleaved Access pass part?

Yes absolutely, let me address some of your comments in the load PR (i.e. recognizing additional patterns for creating mask), since I think the support for strided segment store will share many of the infrastructure I created in that PR.