[RISC-V V] Idea: Interleave independent op-chains by `vsetvli` category

[Validark]

Zig Godbolt

LLC Godbolt

In my real code, I have some 512-bit subtractions, some of which can be run in parallel. Some real code would inline to something like this:

// equivalent to sub(a, b) & sub(c, d)
export fn foo(a: @Vector(8, u64), b: @Vector(8, u64), c: @Vector(8, u64), d: @Vector(8, u64)) @Vector(8, u64) {
    const c1: u8 = @as(u8, @bitCast(a < b));
    const m1: u8 = @as(u8, @bitCast(a == b));
    const s1 = a -% b;
    const ans1 = @select(u64, @as(@Vector(8, bool), @bitCast(m1 ^ ((c1 << 1) +% m1))), s1 +% @as(@Vector(8, u64), @splat(0xffffffffffffffff)), s1);


    const c2: u8 = @as(u8, @bitCast(c < d));
    const m2: u8 = @as(u8, @bitCast(c == d));
    const s2 = c -% d;
    const ans2 = @select(u64, @as(@Vector(8, bool), @bitCast(m2 ^ ((c2 << 1) +% m2))), s2 +% @as(@Vector(8, u64), @splat(0xffffffffffffffff)), s2);

    return ans1 & ans2;
}

Compiled for sifive_x280, we get:

foo:
-       vsetivli        zero, 8, e64, m1, ta, ma
        vle64.v v9, (a1)
        vmv.v.i v8, 0
        vle64.v v10, (a2)
        vmsltu.vv       v11, v9, v10
        vmseq.vv        v12, v9, v10
-       vsetvli zero, zero, e8, mf8, ta, ma
        vmv.x.s a1, v11
        vle64.v v11, (a3)
        vmv.x.s a2, v12
        vle64.v v12, (a4)
        sh1add  a1, a1, a2
        xor     a1, a1, a2
        vmv.s.x v0, a1
-       vsetvli zero, zero, e64, m1, ta, ma
        vmsltu.vv       v14, v11, v12
        vmseq.vv        v15, v11, v12
        vmerge.vim      v13, v8, 1, v0
-       vsetvli zero, zero, e8, mf8, ta, ma
        vmv.x.s a1, v14
        vmv.x.s a2, v15
        sh1add  a1, a1, a2
        xor     a1, a1, a2
        vmv.s.x v0, a1
-       vsetvli zero, zero, e64, m1, ta, ma
        vsub.vv v9, v9, v10
        vsub.vv v10, v11, v12
        vmerge.vim      v8, v8, 1, v0
        vsub.vv v9, v9, v13
        vsub.vv v8, v10, v8
        vand.vv v8, v8, v9
        vse64.v v8, (a0)
        ret

Notice how we have 5 vsetivli/vsetvli? That seems a bit unnecessary. With manual interleaving:

// equivalent to sub(a, b) & sub(c, d)
export fn bar(a: @Vector(8, u64), b: @Vector(8, u64), c: @Vector(8, u64), d: @Vector(8, u64)) @Vector(8, u64) {
    const c1: u8 = @as(u8, @bitCast(a < b));
    const m1: u8 = @as(u8, @bitCast(a == b));
    const c2: u8 = @as(u8, @bitCast(c < d));
    const m2: u8 = @as(u8, @bitCast(c == d));

    const s1 = a -% b;
    const s2 = c -% d;

    const ans1 = @select(u64, @as(@Vector(8, bool), @bitCast(m1 ^ ((c1 << 1) +% m1))), s1 +% @as(@Vector(8, u64), @splat(0xffffffffffffffff)), s1);
    const ans2 = @select(u64, @as(@Vector(8, bool), @bitCast(m2 ^ ((c2 << 1) +% m2))), s2 +% @as(@Vector(8, u64), @splat(0xffffffffffffffff)), s2);

    return ans1 & ans2;
}

We get:

bar:
+       vsetivli        zero, 8, e64, m1, ta, ma
        vle64.v v10, (a1)
        vmv.v.i v9, 0
        vle64.v v11, (a2)
        vle64.v v12, (a3)
        vle64.v v13, (a4)
        vmsltu.vv       v8, v10, v11
        vmseq.vv        v14, v10, v11
        vmsltu.vv       v15, v12, v13
        vmseq.vv        v16, v12, v13
+       vsetvli zero, zero, e8, mf8, ta, ma
        vmv.x.s a1, v8
        vmv.x.s a2, v14
        vmv.x.s a3, v15
        vmv.x.s a4, v16
        sh1add  a1, a1, a2
        xor     a1, a1, a2
        sh1add  a2, a3, a4
        xor     a2, a2, a4
        vmv.s.x v0, a1
        vmv.s.x v8, a2
+       vsetvli zero, zero, e64, m1, ta, ma
        vsub.vv v10, v10, v11
        vmerge.vim      v11, v9, 1, v0
-       vmv1r.v v0, v8
        vsub.vv v8, v12, v13
        vmerge.vim      v9, v9, 1, v0
        vsub.vv v10, v10, v11
        vsub.vv v8, v8, v9
        vand.vv v8, v8, v10
        vse64.v v8, (a0)
        ret

Now there are only 3 vsetivli/vsetvli instructions! We do have an extra vmv1r.v inserted in this version, but my feeling is that that is less expensive than the 2 vsetvli we eliminated.

[llvmbot]

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

Author: Niles Salter (Validark)

[Zig Godbolt](https://zig.godbo.lt/#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaPECAMzwBtMA7AQwFtMQByARg9KtQYEAysib0QXAEx8BBAKoBnTAAUAHpwAMvAFYhptJg1AAvPMFJL6yAngGVG6AMKpaAVxYMJpBwBk8DTAA5dwAjTGIQAGYATlIAB1QFQlsGZzcPLwSkmwE/AOCWMIiYi0wrHIYhAiZiAjT3Ty5S8pSqmoI8oNDwqNiFatr6jKb%2B9s6Cot6ASgtUV2Jkdg4AemWAan5UEABSDQBBVbWj4%2BOANyUCU9o8NeNw1FJb%2B8fMAA5Hlip3teqPpl2DusTidzphLtcnsQHpDoZgAGwAFg%2BTR%2BTD%2BAMOIRqO32h2BR1OLFOXGIADpTmtThpHqdXgCMetMABHVx4U5iRgEH6oNYKVwhCBotYhKZrbaSOG8/kQZCPdBTAGYVQJWobBgbVCoQUgNYAAQAaphrCQIN9XIiZsKdQajURiKbHuaEZbkNbDcb7WaLXK3baTV7naKbR6HWsnaLtgB2ABCAJOaAY/TWyC4OtcrzFkQAInqmAoIOnHrqQoRHHmCILM45hVMFZFY/t4wIkyxU2GM9ts7n84W9SW6uXK52s8Oa3WG3sm4muQouJmc0w1gBacUAVmFnYnU6Thln871lltBcRRbzEGDdtDIU1tEtxdLg9bYtX2DWUBTVc71a4Ecksck66trWlp7uK/7rrqZ4Xv6jregecQGBWGiqFQqFoehGFULWjyzuO9L7HGxwJkmyCSGmHZdpBPbfPeA79DKVZrPKeGNkRzZciwZHtvuVEFjR/ZlvRyDzqOzGboRRzETOkj7sJK4AUx4msZJ7FrLuMmjrqh7WMeSLdue7qXt814uHeAmPhpL5vjKGmRI4X5rD%2BYp/muayccBOEaS5Cm8dBnqwc6RYKAhTBIShmERah2G8pILF7BJazEGC8zqruc7ipK6lKfFkYjgRuKMiybIcoI3JSgKQois5kp8gKspMQq%2BxKiqXJUOqWL2kwvohgGlohN1RkBS6A0wWGcHoCN/ljYGeqGaN4ZijGCVScmbbpjxZ69rRgkVouDkinF24cWtFE5rxW3mfRe3ZqOB3ZUdyZcetmmbfxD5CYxYn1stqmceRG3UUWl0VsJw6ibW2U/dOvLpV2i7yeuIT3Wx0MKLZOZya56CQ8pyaqWlPHaRWTqnvmflXjeZnvRWT7bFZ76w/ZdmOb%2B4FuT%2B0Wgd5EFQXNU3hkFIVhZFkWcz%2ByMqdD6mE2UR4k/p5PGZTQPUxAnHPq%2B762Uz36s657mc15bO%2BXzoYC/BiEQMhIsRYbcUJUlBApWpibpRKLto5DuX4XsHAzLQnCrrwngcFopBbBwABaZi8nMCyYM5kSSLwBCaH7MwIJgTBYBEEAzAA1iAq6SKSGirqukYItEUivNX0SvHCpABxwCK8CwEgaNSIdhxHvAKCA1Kp6HfukHAsBIGgLBxHQ4TkJQk/T/QETGAQxCuAw%2Bd8HQBDhP3ED9cPpAlswxAAJ6cDwR/%2BDUp8APIhNotoX7wk9sIIt8MLQ5%2BH1gISuMAZZaC0H7twXgWAWCGGAOIH%2BeAkrWDZJgEBYclRGlcDvZ%2B5BBBlDTk3PAIRiA32cFgHBq88Dt1AaQU44RrxKCzJgCBRhrhGDTjMKgBhgAKH1HgTAAB3W%2BcRGAYP4IIEQHIJDSGEfIJQagcG6H0JAkAphzDXBCP3SAMxUBxAqCApcLBkBxFcMOJINAqEAH1VCSFeBoZcAxgBgkSngBQyBTiIiXEw1wqhly3wAEqyzzJgAAYuWXgqAqHEGIHgLAai87NFtCkewDAnAuAaBIRuvh/BdEKD0SI1IsjJAEEMRojc8kVHGN0Yo1IiatAGHUZJGQ%2Biy3gQINotQylZIqRYGphSQB9BqW0yYOSZgKDjosPQ/tA7BxwRHW4MdV7r3zm%2BXAhASCJ1iinFhGcs450oAXEACJIykmiAiBEAENCvEjFwM5GguBImbq3Ug7dLkaFLp3V5bzXlNG7iEzgfcB6kCHlobCzdk6kC%2BeHH5/yNmUN3vEhEQA)

LLC Godbolt

In my real code, I have some 512-bit subtractions, some of which can be run in parallel. Some real code would inline to something like this:

// equivalent to sub(a, b) & sub(c, d)
export fn foo(a: @<!-- -->Vector(8, u64), b: @<!-- -->Vector(8, u64), c: @<!-- -->Vector(8, u64), d: @<!-- -->Vector(8, u64)) @<!-- -->Vector(8, u64) {
    const c1: u8 = @<!-- -->as(u8, @<!-- -->bitCast(a &lt; b));
    const m1: u8 = @<!-- -->as(u8, @<!-- -->bitCast(a == b));
    const s1 = a -% b;
    const ans1 = @<!-- -->select(u64, @<!-- -->as(@<!-- -->Vector(8, bool), @<!-- -->bitCast(m1 ^ ((c1 &lt;&lt; 1) +% m1))), s1 +% @<!-- -->as(@<!-- -->Vector(8, u64), @<!-- -->splat(0xffffffffffffffff)), s1);


    const c2: u8 = @<!-- -->as(u8, @<!-- -->bitCast(c &lt; d));
    const m2: u8 = @<!-- -->as(u8, @<!-- -->bitCast(c == d));
    const s2 = c -% d;
    const ans2 = @<!-- -->select(u64, @<!-- -->as(@<!-- -->Vector(8, bool), @<!-- -->bitCast(m2 ^ ((c2 &lt;&lt; 1) +% m2))), s2 +% @<!-- -->as(@<!-- -->Vector(8, u64), @<!-- -->splat(0xffffffffffffffff)), s2);

    return ans1 &amp; ans2;
}

Compiled for sifive_x280, we get:

foo:
-       vsetivli        zero, 8, e64, m1, ta, ma
        vle64.v v9, (a1)
        vmv.v.i v8, 0
        vle64.v v10, (a2)
        vmsltu.vv       v11, v9, v10
        vmseq.vv        v12, v9, v10
-       vsetvli zero, zero, e8, mf8, ta, ma
        vmv.x.s a1, v11
        vle64.v v11, (a3)
        vmv.x.s a2, v12
        vle64.v v12, (a4)
        sh1add  a1, a1, a2
        xor     a1, a1, a2
        vmv.s.x v0, a1
-       vsetvli zero, zero, e64, m1, ta, ma
        vmsltu.vv       v14, v11, v12
        vmseq.vv        v15, v11, v12
        vmerge.vim      v13, v8, 1, v0
-       vsetvli zero, zero, e8, mf8, ta, ma
        vmv.x.s a1, v14
        vmv.x.s a2, v15
        sh1add  a1, a1, a2
        xor     a1, a1, a2
        vmv.s.x v0, a1
-       vsetvli zero, zero, e64, m1, ta, ma
        vsub.vv v9, v9, v10
        vsub.vv v10, v11, v12
        vmerge.vim      v8, v8, 1, v0
        vsub.vv v9, v9, v13
        vsub.vv v8, v10, v8
        vand.vv v8, v8, v9
        vse64.v v8, (a0)
        ret

Notice how we have 5 vsetivli/vsetvli? That seems a bit unnecessary. With manual interleaving:

// equivalent to sub(a, b) & sub(c, d)
export fn bar(a: @<!-- -->Vector(8, u64), b: @<!-- -->Vector(8, u64), c: @<!-- -->Vector(8, u64), d: @<!-- -->Vector(8, u64)) @<!-- -->Vector(8, u64) {
    const c1: u8 = @<!-- -->as(u8, @<!-- -->bitCast(a &lt; b));
    const m1: u8 = @<!-- -->as(u8, @<!-- -->bitCast(a == b));
    const c2: u8 = @<!-- -->as(u8, @<!-- -->bitCast(c &lt; d));
    const m2: u8 = @<!-- -->as(u8, @<!-- -->bitCast(c == d));

    const s1 = a -% b;
    const s2 = c -% d;

    const ans1 = @<!-- -->select(u64, @<!-- -->as(@<!-- -->Vector(8, bool), @<!-- -->bitCast(m1 ^ ((c1 &lt;&lt; 1) +% m1))), s1 +% @<!-- -->as(@<!-- -->Vector(8, u64), @<!-- -->splat(0xffffffffffffffff)), s1);
    const ans2 = @<!-- -->select(u64, @<!-- -->as(@<!-- -->Vector(8, bool), @<!-- -->bitCast(m2 ^ ((c2 &lt;&lt; 1) +% m2))), s2 +% @<!-- -->as(@<!-- -->Vector(8, u64), @<!-- -->splat(0xffffffffffffffff)), s2);

    return ans1 &amp; ans2;
}

We get:

bar:
+       vsetivli        zero, 8, e64, m1, ta, ma
        vle64.v v10, (a1)
        vmv.v.i v9, 0
        vle64.v v11, (a2)
        vle64.v v12, (a3)
        vle64.v v13, (a4)
        vmsltu.vv       v8, v10, v11
        vmseq.vv        v14, v10, v11
        vmsltu.vv       v15, v12, v13
        vmseq.vv        v16, v12, v13
+       vsetvli zero, zero, e8, mf8, ta, ma
        vmv.x.s a1, v8
        vmv.x.s a2, v14
        vmv.x.s a3, v15
        vmv.x.s a4, v16
        sh1add  a1, a1, a2
        xor     a1, a1, a2
        sh1add  a2, a3, a4
        xor     a2, a2, a4
        vmv.s.x v0, a1
        vmv.s.x v8, a2
+       vsetvli zero, zero, e64, m1, ta, ma
        vsub.vv v10, v10, v11
        vmerge.vim      v11, v9, 1, v0
-       vmv1r.v v0, v8
        vsub.vv v8, v12, v13
        vmerge.vim      v9, v9, 1, v0
        vsub.vv v10, v10, v11
        vsub.vv v8, v8, v9
        vand.vv v8, v8, v10
        vse64.v v8, (a0)
        ret

Now there are only 3 vsetivli/vsetvli instructions! We do have an extra vmv1r.v inserted in this version, but my feeling is that that is less expensive than the 2 vsetvli we eliminated.

[wangpc-pp]

Thanks! It is a good idea!

Actually @BeMg and I had tried similar idea before (see also #95924). The result was promising, but there were too many issues we need to fix.

[Validark]

Thanks! It is a good idea!

Actually @BeMg and I had tried similar idea before (see also #95924). The result was promising, but there were too many issues we need to fix.

Oh, nice! Well now you have a tracking issue :)