RISC-V: RVV register allocation problem causes costly and unecessary spill

[camel-cdr]

Hi, I ran into a problem, where reordering a single RVV intrinsic without changing the program logic caused llvm to spill a vector register, suggesting that the register allocation has trouble reordering in this case:

#include <riscv_vector.h>

void test(int *out, const int *in, size_t n)
{
    for (size_t vl; n > 0; n -= vl, out += vl, in += vl) {
        vl = __riscv_vsetvl_e32m8(n);
        vint32m8_t v1 = __riscv_vle32_v_i32m8(in, vl);
        vint32m8_t v2 = __riscv_vadd(v1, v1, vl);
        vbool4_t mlt = __riscv_vmslt(v1, 0, vl);

#ifdef REORDER
	vint32m8_t v4 = __riscv_vmerge(v2, v1, mlt, vl);
#endif
        vint32m8_t v3 = __riscv_vadd(v1, 3, vl);
#ifndef REORDER
        vint32m8_t v4 = __riscv_vmerge(v2, v1, mlt, vl);
#endif

        vbool4_t mgt = __riscv_vmsgt(v1, 4, vl);
        v1 = __riscv_vadd_mu(__riscv_vmor(mlt, mgt, vl), v1, v3, v4, vl);

        __riscv_vse32(out, v1, vl);
    }
}

See also the godbolt link: https://godbolt.org/z/6vdf4vEjn

This example was adapted from real code, and minimized while still retaining the problematic behavior.

gcc manages to figure out the proper register allocation.

[llvmbot]

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

Author: Camel Coder (camel-cdr)

Hi, I ran into a problem, where reordering a single RVV intrinsic without changing the program logic caused llvm to spill a vector register, suggesting that the register allocation has trouble reordering in this case:

#include <riscv_vector.h>

void test(int *out, const int *in, size_t n)
{
    for (size_t vl; n > 0; n -= vl, out += vl, in += vl) {
        vl = __riscv_vsetvl_e32m8(n);
        vint32m8_t v1 = __riscv_vle32_v_i32m8(in, vl);
        vint32m8_t v2 = __riscv_vadd(v1, v1, vl);
        vbool4_t mlt = __riscv_vmslt(v1, 0, vl);

#ifdef REORDER
	vint32m8_t v4 = __riscv_vmerge(v2, v1, mlt, vl);
#endif
        vint32m8_t v3 = __riscv_vadd(v1, 3, vl);
#ifndef REORDER
        vint32m8_t v4 = __riscv_vmerge(v2, v1, mlt, vl);
#endif

        vbool4_t mgt = __riscv_vmsgt(v1, 4, vl);
        v1 = __riscv_vadd_mu(__riscv_vmor(mlt, mgt, vl), v1, v3, v4, vl);

        __riscv_vse32(out, v1, vl);
    }
}

See also the godbolt link: https://godbolt.org/z/6vdf4vEjn

This example was adapted from real code, and minimized while still retaining the problematic behavior.

gcc manages to figure out the proper register allocation.

[wangpc-pp]

Thanks for reporting! I will take a look first as others are attending LLVM dev meeting I think.

[wangpc-pp]

After a rough investigation, the preliminary conclusion is we are extending the live inteval of vmsgt.
Simply disabling misched to avoid reordering, or using topdown scheduling, can generate desired code: https://godbolt.org/z/n3sKzc8E1

[wangpc-pp]

I have done a deep investigation, and this problem is much more complicated than what I was thinking.
To make a long story short, there are two things I think we should fix:

1. LMUL=1 registers have the same logic of calculating the spill weight as LMUL>1 registers. I should have fixed this in [RegAlloc] Scale the spill weight by target factor #113675.
   After this change, the generated code will be:

test:
	beqz	a2, .LBB0_2
.LBB0_1:
	vsetvli	a3, a2, e32, m8, ta, mu
	vle32.v	v16, (a1)
	vadd.vv	v8, v16, v16
	vmslt.vx	v0, v16, zero
	vadd.vi	v24, v16, 3
	vmsgt.vi	v7, v16, 4
	vmor.mm	v7, v0, v7
	vmerge.vvm	v8, v8, v16, v0
	vmv1r.v	v0, v7
	vadd.vv	v16, v24, v8, v0.t
	vse32.v	v16, (a0)
	sub	a2, a2, a3
	slli	a3, a3, 2
	add	a0, a0, a3
	add	a1, a1, a3
	bnez	a2, .LBB0_1
.LBB0_2:
	ret

2. We shouldn't move masks producing instructions accross masked instructions, or we will extend the live inteval of mask register. For example, we shouldn't move vmor.mm v7, v0, v7 to the front of vmerge.vvm v8, v8, v16, v0. The ideal code should be like:

test:
	beqz	a2, .LBB0_2
.LBB0_1:
	vsetvli	a3, a2, e32, m8, ta, mu
	vle32.v	v16, (a1)
	vadd.vv	v8, v16, v16
	vmslt.vx	v0, v16, zero
	vadd.vi	v24, v16, 3
	vmsgt.vi	v7, v16, 4
-	vmor.mm	v7, v0, v7
	vmerge.vvm	v8, v8, v16, v0
-	vmv1r.v	v0, v7
+	vmor.mm	v0, v0, v7
	vadd.vv	v16, v24, v8, v0.t
	vse32.v	v16, (a0)
	sub	a2, a2, a3
	slli	a3, a3, 2
	add	a0, a0, a3
	add	a1, a1, a3
	bnez	a2, .LBB0_1
.LBB0_2:
	ret

To fix this, I may try to add scheduling DAG mutation that will add a dependency between vmor.mm and vmerge.vvm.