Invalid MVE tail-predication in ARMLowOverheadLoops

[statham-arm]

When compiling the following C source using MVE vector intrinsics, the ARMLowOverheadLoops pass changes the semantics of the code by performing tail-predication.

// clang --target=arm-none-eabi -mcpu=cortex-m52 -mfloat-abi=hard -fno-inline-functions -O1 -S -o - 162644.c

#include <arm_mve.h>

float32x4_t inactive = {0.0, 0.0, 0.0, 0.0};

float32x4_t test_func(float32_t *array, int32_t len) {
    float32x4_t acc = vdupq_n_f32(0.1f);

    do {
        mve_pred16_t tailpred = vctp32q(len);
        float32x4_t vecSrc = vldrwq_z_f32(array, tailpred);
        acc = vaddq_m_f32(inactive, acc, vecSrc, tailpred);
        array += 4;
        len -= 4;
    } while (len > 0);

    return acc;
}

The source code loads four floats at a time from the input array, and adds them elementwise to the vector acc. In case len is not a multiple of 4, an explicit MVE predicate is constructed using vctp32q so that the final loop iteration will load fewer than 4 floats.

Usually in this kind of code the vaddq_m_32 instruction would pass acc as its first operand as well as its second, so that any vector lanes disabled by the predicate would be left unchanged from their value in the previous iteration. However, in this code, the vaddq_m_32 takes its inactive lanes from the constant all-zero vector inactive.

So the semantics of this code as written is that any vector lane not used by the last loop iteration will be zero in the returned vector, rather than containing the sum of array elements from previous iterations.

Compiling this code with the extra option -mllvm -arm-loloops-disable-tailpred, the ARMLowOverheadLoops pass generates a low-overhead loop using dls and le, but leaves the tail-predication alone. The vmov q0,q1 in the middle of the loop is unpredicated, and copies all of the inactive vector into q0, including the lanes disabled by the current loop iteration's predicate. Then the predicated vaddt after that overwrites only the active lanes with the sum of the previous acc with the loaded values, just as the source code says.

        dls         lr, r2
.LBB0_1:
        vctp.32     r1
        vmov        q2, q0
        vpst
        vldrwt.u32  q3, [r0], #16 // tail-predicated: load from input array
        vmov        q0, q1        // unpredicated: copy 'inactive' into q0
        vpst
        vaddt.f32   q0, q2, q3    // tail-pred: overwrite some of q0 with q2+q3
        subs        r1, #4
        le          lr, .LBB0_1

But removing -mllvm -arm-loloops-disable-tailpred causes ARMLowOverheadLoops to perform a transformation that changes the semantics (as of commit b256d0a):

        dlstp.32    lr, r1
.LBB0_1:
        vmov        q2, q0
        vldrw.u32   q3, [r0], #16 // tail-predication now done by LTPSIZE
        vmov        q0, q1        // ALSO TAIL-PREDICATED but shouldn't be
        vadd.f32    q0, q2, q3    // tail-predicated as before
        letp        lr, .LBB0_1

Now the tail-predication in the last loop iteration is done by the dlstp and letp instructions setting the LTPSIZE field in FPSCR, instead of by constructing a predicate in VPR. This means that all the instructions in the loop are affected by the tail-predication. In particular, the vmov q0,q1 is now copying only the active lanes into q0. So the inactive lanes in the final iteration will not be zeroed: they will take whatever value was left in q0 after the previous iteration.

In this situation, ARMLowOverheadLoops should recognize that tail-predicating the loop via LTPSIZE is an invalid transformation: the inactive lanes written by that vmov are needed, so the write to them cannot be discarded.

[llvmbot]

@llvm/issue-subscribers-backend-arm

Author: Simon Tatham (statham-arm)

When compiling the following C source, the ARMLowOverheadLoops pass changes the semantics of the code by performing tail-predication. ```c // clang --target=arm-none-eabi -mcpu=cortex-m52 -mfloat-abi=hard -fno-inline-functions -O1 -S -o - -mllvm -print-before-all llvmaeng4598.c

#include <arm_mve.h>

float32x4_t inactive = {0.0, 0.0, 0.0, 0.0};

float32x4_t test_func(float32_t *array, int32_t len) {
float32x4_t acc = vdupq_n_f32(0.1f);

do {
    mve_pred16_t tailpred = vctp32q(len);
    float32x4_t vecSrc = vldrwq_z_f32(array, tailpred);
    acc = vaddq_m_f32(inactive, acc, vecSrc, tailpred);
    array += 4;
    len -= 4;
} while (len > 0);

return acc;

}

The source code loads four floats at a time from the input array, and adds them elementwise to the vector `acc`. In case `len` is not a multiple of 4, an explicit MVE predicate is constructed using `vctp32q` so that the final loop iteration will load fewer than 4 floats.

Usually in this kind of code the `vaddq_m_32` instruction would pass `acc` as its first operand as well as its second, so that any vector lanes disabled by the predicate would be left unchanged from their value in the previous iteration. However, in _this_ code, the `vaddq_m_32` takes its inactive lanes from the constant all-zero vector `inactive`.

So the semantics of this code as written is that any vector lane not used by the last loop iteration will be _zero_ in the returned vector, rather than containing the sum of array elements from previous iterations.

Compiling this code with the extra option `-mllvm -arm-loloops-disable-tailpred`, the ARMLowOverheadLoops pass generates a low-overhead loop using `dls` and `le`, but leaves the tail-predication alone. The `vmov q0,q1` in the middle of the loop is unpredicated, and copies _all_ of the `inactive` vector into q0, including the lanes disabled by the current loop iteration's predicate. Then the predicated `vaddt` after that overwrites only the active lanes with the sum of the previous `acc` with the loaded values, just as the source code says.

    dls         lr, r2

.LBB0_1:
vctp.32 r1
vmov q2, q0
vpst
vldrwt.u32 q3, [r0], #16 // tail-predicated: load from input array
vmov q0, q1 // unpredicated: copy 'inactive' into q0
vpst
vaddt.f32 q0, q2, q3 // tail-pred: overwrite some of q0 with q2+q3
subs r1, #4
le lr, .LBB0_1

But removing `-mllvm -arm-loloops-disable-tailpred` causes ARMLowOverheadLoops to perform a transformation that changes the semantics (as of commit b256d0a7aa00079e7ff0e64d52b8055ed6440682):

    dlstp.32    lr, r1

.LBB0_1:
vmov q2, q0
vldrw.u32 q3, [r0], #16 // tail-predication now done by LTPSIZE
vmov q0, q1 // ALSO TAIL-PREDICATED but shouldn't be
vadd.f32 q0, q2, q3 // tail-predicated as before
letp lr, .LBB0_1

Now the tail-predication in the last loop iteration is done by the `dlstp` and `letp` instructions setting the LTPSIZE field in FPSCR, instead of by constructing a predicate in VPR. This means that _all_ the instructions in the loop are affected by the tail-predication. In particular, the `vmov q0,q1` is now copying only the _active_ lanes into q0. So the inactive lanes in the final iteration will not be zeroed: they will take whatever value was left in q0 after the previous iteration.

In this situation, ARMLowOverheadLoops should recognize that tail-predicating the loop via LTPSIZE is an invalid transformation: the inactive lanes written by that `vmov` are needed, so the write to them cannot be discarded.
</details>

[statham-arm]

I've been struggling to make sense of the ARMLowOverheadLoops pass. I think the relevant function is ValidateLiveOuts, which ought to spot that the value in acc used after the loop potentially takes part of its value from the vmov q0,q1 which has changed what it wrote to q0 due to the tail predication. But the code in there is confusing.

I think the root cause is that when ValidateLiveOuts looks at the relation between a definition of a MQPR vector value and an instruction using it, it doesn't pay any attention to whether that instruction reads from only the active lanes of that vector register, or whether the instruction uses the register in the slot tied to the output, with the semantics "this input is where the inactive lanes of the output register come from". In this example, the vadd is represented by

  renamable $q0 = MVE_VADDf32 killed renamable $q2, killed renamable $q3, 1, killed renamable $vpr, renamable $lr, killed renamable $q0(tied-def 0)

which means that it's reading the active lanes of q2 and q3 to generate part of the output, but the inactive lanes of (the previous value of) q0. So if the instruction that wrote q2 or q3 were modified in a way that only affected the active lanes, it wouldn't matter to this vadd. But when the instruction that writes q0 is modified in that way, it does matter. ValidateLiveOuts doesn't seem to contain any code that takes account of that difference, or even finds out about it in the first place (e.g. by checking if the register is in the last sub-operand slot of a VPRED_R).

I'm not sure how to add that check without a major rewrite of ValidateLiveOuts, though. (And I'm suspicious of the urge to "just rewrite" any code I don't 100% understand, because surely that sometimes leads to fresh bugs because of failing to understand what the previous code did right!)

@davemgreen, @sparker-arm, any thoughts? Have I completely misunderstood?

[statham-arm]

I'm also a bit suspicious of the output MIR for another reason, and I'm not sure if it's related. The current output code looks like this:

    $q2 = MVE_VORR killed $q0, killed $q0, 0, $noreg, $noreg, undef $q2
    renamable $r0, renamable $q3 = MVE_VLDRWU32_post killed renamable $r0, 16, 0, $noreg, renamable $lr :: (load unknown-size from %ir.13, align 4)
    $q0 = MVE_VORR $q1, $q1, 0, $noreg, $noreg, undef $q0
    renamable $q0 = MVE_VADDf32 killed renamable $q2, killed renamable $q3, 0, killed $noreg, renamable $lr, killed renamable $q0
    $lr = MVE_LETP killed renamable $lr, %bb.1

The $q0 = MQPRCopy $q1 in the input has been turned into an explicit MVE_VORR in the output, reflecting the fact that due to the implicit tail-predication via LTPSIZE, it's not actually making a full copy of the input register any more. But the register liveness indications haven't been updated to match. Surely the instruction ought to list the previous value of q0 as an input, and the killed flag on q0 in the previous MVE_VORR ought not to be there any more? And there should be a reference to $lr, which is apparently how MIR signals the dependence on the LTPSIZE tail predication mechanism in a low-overhead loop. I would expect to see something more like this:

    $q2 = MVE_VORR $q0, $q0, 0, $noreg, renamable $lr, undef $q2
    renamable $r0, renamable $q3 = MVE_VLDRWU32_post killed renamable $r0, 16, 0, $noreg, renamable $lr :: (load unknown-size from %ir.13, align 4)
    $q0 = MVE_VORR $q1, $q1, 0, $noreg, renamable $lr, killed $q0
    renamable $q0 = MVE_VADDf32 killed renamable $q2, killed renamable $q3, 0, killed $noreg, renamable $lr, killed renamable $q0
    $lr = MVE_LETP killed renamable $lr, %bb.1

in which the first vorr no longer lists $q0 as killed, the second one doesn't list it as undef, and both of them mention $lr. This seems to be at least a risk that further MIR passes introduce bugs by not knowing about those data dependencies. But I haven't worked out whether it's also part of the cause of this bug.

[statham-arm]

… or, then again, perhaps the point is that we should only tail-predicate a loop if only the active lanes of the output are logically live, so that it's morally right to ignore the theoretical dependency on the previous value of the output register, because it doesn't matter if later passes rewrite it. It only matters in this case because we tail-predicated the loop wrongly.

[sparker-arm]

it doesn't pay any attention to whether that instruction reads from only the active lanes of that vector register, or whether the instruction uses the register in the slot tied to the output

This is hopefully what the call to isVectorPredicated is considering. My MVE memory is fading, but I thought all predicated instructions (maybe not reductions?) have their output tied to the input.

So, I doubt the VADD is the problem. QPRCopy is special-cased, and introduced specifically for tail predication, so that's where I would start. ValidateLiveOuts sounds like the right place too. Maybe we're not correctly tracking that the QPRCopy, into Q0, is LiveOut and this possibly caused by a bug in ReachingDefInfo?

[statham-arm]

This is hopefully what the call to isVectorPredicated is considering. My MVE memory is fading, but I thought all predicated instructions (maybe not reductions?) have their output tied to the input.

Not all, no. Only the ones with merging semantics – write to only the active lanes of a vector register, leaving the inactive lanes unmodified, so that they contain whatever was in that part of the same register beforehand. As you say, reductions don't have merging semantics, because they don't output a vector at all. But loads also don't have merging semantics, because they're defined to zero the inactive lanes instead of leaving them unmodified. (Hence the producesFalseLanesZero function.)

The difference in the LLVM MC representation is that the instruction definitions contain two types of predicate operand cluster, vpred_n and vpred_r, with the difference being that vpred_r has an extra input vector register which ends up tied to the output register. Loads and reductions use vpred_n instead.

But I think the point is that in an instruction which does have that extra input operand, ValidateLiveOuts ought to be doing something different depending on whether an instruction reads a register via that parameter or via another one, because it makes a difference. isVectorPredicated is only testing that a predicate operand exists, and doesn't say whether it's vpred_n or vpred_r, or which input vector register is the vpred_r inactive-lanes operand.

QPRCopy is special-cased, and introduced specifically for tail predication, so that's where I would start.

Yes. In fact I think the special-casing is a large part of the problem, because it has its own code path which seems to handwave away the idea that a "copy" of a vector register stops being a complete copy once you move it into a region of code where LTPSIZE is doing something nontrivial.