[LoopInterchange] vectorisation opportunity (tsvc, s231)

[sjoerdmeijer]

Looks like we are 1400% (?!) behind for kernel s231 in TSVC compared to GCC.
Compile this code with -O3 -mcpu=neoverse-v2 -ffast-math:

__attribute__((aligned(64))) float a[32000],b[32000],c[32000],d[32000],e[32000],
                                   aa[256][256],bb[256][256],cc[256][256],tt[256][256];

int dummy(float[32000], float[32000], float[32000], float[32000], float[32000], float[256][256], float[256][256], float[256][256], float);

float s231()
{
    for (int nl = 0; nl < 100*(100000/256); nl++) {
        for (int i = 0; i < 256; ++i) {
            for (int j = 1; j < 256; j++) {
                aa[j][i] = aa[j - 1][i] + bb[j][i];
            }
        }
        dummy(a, b, c, d, e, aa, bb, cc, 0.);
    }
}

Clang's codegen:

.LBB44_3:                               //   Parent Loop BB44_1 Depth=1
                                        //     Parent Loop BB44_2 Depth=2
                                        // =>    This Inner Loop Header: Depth=3
        add     x12, x21, x10
        add     x13, x20, x10
        subs    x11, x11, #5
        add     x10, x10, x19
        ldr     s1, [x12, #1024]
        fadd    s0, s1, s0
        ldr     s1, [x12, #2048]
        str     s0, [x13, #1024]
        fadd    s0, s1, s0
        ldr     s1, [x12, #3072]
        str     s0, [x13, #2048]
        fadd    s0, s1, s0
        ldr     s1, [x12, #4096]
        str     s0, [x13, #3072]
        fadd    s0, s1, s0
        ldr     s1, [x12, #5120]
        str     s0, [x13, #4096]
        fadd    s0, s1, s0
        str     s0, [x13, #5120]
        b.ne    .LBB44_3

vs. GCC's codegen:

.L521:
        ldr     q0, [x8, x0]
        ldr     q1, [x2, x0]
        fadd    v0.4s, v0.4s, v1.4s
        str     q0, [x1, x0]
        add     x0, x0, 16
        cmp     x0, 1024
        bne     .L521

See also:
https://godbolt.org/z/jr9WKW95v

TODO:
root cause analysis.

[llvmbot]

@llvm/issue-subscribers-backend-aarch64

Author: Sjoerd Meijer (sjoerdmeijer)

Looks like we are 1400% (?!) behind for kernel s231 in TSVC compared to GCC. Compile this code with `-O3 -mcpu=neoverse-v2 -ffast-math`:

__attribute__((aligned(64))) float a[32000],b[32000],c[32000],d[32000],e[32000],
                                   aa[256][256],bb[256][256],cc[256][256],tt[256][256];

int dummy(float[32000], float[32000], float[32000], float[32000], float[32000], float[256][256], float[256][256], float[256][256], float);

float s231()
{
    for (int nl = 0; nl < 100*(100000/256); nl++) {
        for (int i = 0; i < 256; ++i) {
            for (int j = 1; j < 256; j++) {
                aa[j][i] = aa[j - 1][i] + bb[j][i];
            }
        }
        dummy(a, b, c, d, e, aa, bb, cc, 0.);
    }
}

Clang's codegen:

.LBB44_3:                               //   Parent Loop BB44_1 Depth=1
                                        //     Parent Loop BB44_2 Depth=2
                                        // =>    This Inner Loop Header: Depth=3
        add     x12, x21, x10
        add     x13, x20, x10
        subs    x11, x11, #<!-- -->5
        add     x10, x10, x19
        ldr     s1, [x12, #<!-- -->1024]
        fadd    s0, s1, s0
        ldr     s1, [x12, #<!-- -->2048]
        str     s0, [x13, #<!-- -->1024]
        fadd    s0, s1, s0
        ldr     s1, [x12, #<!-- -->3072]
        str     s0, [x13, #<!-- -->2048]
        fadd    s0, s1, s0
        ldr     s1, [x12, #<!-- -->4096]
        str     s0, [x13, #<!-- -->3072]
        fadd    s0, s1, s0
        ldr     s1, [x12, #<!-- -->5120]
        str     s0, [x13, #<!-- -->4096]
        fadd    s0, s1, s0
        str     s0, [x13, #<!-- -->5120]
        b.ne    .LBB44_3

vs. GCC's codegen:

.L521:
        ldr     q0, [x8, x0]
        ldr     q1, [x2, x0]
        fadd    v0.4s, v0.4s, v1.4s
        str     q0, [x1, x0]
        add     x0, x0, 16
        cmp     x0, 1024
        bne     .L521

See also:
https://godbolt.org/z/jr9WKW95v

TODO:
root cause analysis.

[m-sai]

The original loop can be vectorized by changing it to a double loop and adding the -enable-loopinterchange option as shown below.

float s231_tmp()
{
        for (int i = 0; i < 256; ++i) {
            for (int j = 1; j < 256; j++) {
                aa[j][i] = aa[j - 1][i] + bb[j][i];
            }
        }
        dummy(a, b, c, d, e, aa, bb, cc, 0.);
}

.LBB0_2:                                // %vector.body
                                        //   Parent Loop BB0_1 Depth=1
                                        // =>  This Inner Loop Header: Depth=2
        ld1w    { z0.s }, p0/z, [x8, x14, lsl #2]
        ld1w    { z1.s }, p0/z, [x9, x14, lsl #2]
        ld1w    { z2.s }, p0/z, [x10, x14, lsl #2]
        add     x15, x8, x14, lsl #2
        add     x16, x9, x14, lsl #2
        fadd    z0.s, z0.s, z2.s
        ld1w    { z3.s }, p0/z, [x11, x14, lsl #2]
        fadd    z1.s, z1.s, z3.s
        inch    x14
        cmp     x14, #256
        st1w    { z0.s }, p0, [x15, x13, lsl #2]
        st1w    { z1.s }, p0, [x16, x13, lsl #2]
        b.ne    .LBB0_2

The original loop cannot be vectorized even with the -enable-loopinterchange option. This is because loop interchange does not work.

The reason loop-interchange doesn't work is because the dependency analysis of the load/store instruction determines that there are dependencies that cannot be loop-interchanged. However, I don't think the original loop has any dependencies, so I think it is a bug in the dependency analysis.

[sjoerdmeijer]

Thanks for the analysis, interesting result/conclusion!

[sebpop]

The reason loop-interchange doesn't work is because the dependency analysis of the load/store instruction determines that there are dependencies that cannot be loop-interchanged. However, I don't think the original loop has any dependencies, so I think it is a bug in the dependency analysis.

Dependence analysis is correct.

Following the discussion on PR #78951 (comment) there are dependences carried by the outermost loop.

Loop-interchange needs to focus on the inner two loops.

[kasuga-fj]

Hi. I'm interested in this issue and have been investigating these days. The PR #78951 tries to implement custom normalize function for LoopInterchange. However I think it's better to change isLegalToInterChangeLoops to accept cases where the leftmost < or > is not changed.

llvm-project/llvm/lib/Transforms/Scalar/LoopInterchange.cpp

Line 200 in e9c561e

static bool isLegalToInterChangeLoops(CharMatrix &DepMatrix,

That is, we don't need to restrict the DepVector to be positive, it's legal if the positive or negative does not change before and after interchange. Looks like the PR I mentioned hasn't made any progress for a while, may I create a new one?

[sjoerdmeijer]

Hi. I'm interested in this issue and have been investigating these days. The PR #78951 tries to implement custom normalize function for LoopInterchange. However I think it's better to change isLegalToInterChangeLoops to accept cases where the leftmost < or > is not changed.

llvm-project/llvm/lib/Transforms/Scalar/LoopInterchange.cpp

Line 200 in e9c561e

static bool isLegalToInterChangeLoops(CharMatrix &DepMatrix,

That is, we don't need to restrict the DepVector to be positive, it's legal if the positive or negative does not change before and after interchange. Looks like the PR I mentioned hasn't made any progress for a while, may I create a new one?

Sure, please go ahead, and thanks for doing that. If you were going to take the same approach, taking over the patch would perhaps be an option (don't know how this works in github though), but since you have a different approach creating a new PR sounds better. Please feel free to add @sebpop and myself as reviewers (among other folks who might be interested in reviewing this).