[AVX-512] vpternlogq fails to be emitted for longer chains of bitmanipulations

[Validark]

Consider: (Godbolt link)

export fn foo(a: @Vector(8, u64), b: @Vector(8, u64), c: @Vector(8, u64)) @Vector(8, u64) {
    return (a & ~(b & ~c));
}

export fn bar(a: @Vector(8, u64), b: @Vector(8, u64), c: @Vector(8, u64)) @Vector(8, u64) {
    return a & ~b & ~c;
}

export fn foobar(a: @Vector(8, u64), b: @Vector(8, u64), c: @Vector(8, u64), d: @Vector(8, u64), e: @Vector(8, u64)) @Vector(8, u64) {
    return bar(foo(a, b, c), d, e);
}

LLVM IR (Godbolt link):

define dso_local <8 x i64> @foo(<8 x i64> %0, <8 x i64> %1, <8 x i64> %2) local_unnamed_addr {
Entry:
  %.not = xor <8 x i64> %1, <i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1>
  %3 = or <8 x i64> %.not, %2
  %4 = and <8 x i64> %3, %0
  ret <8 x i64> %4
}

define dso_local <8 x i64> @bar(<8 x i64> %0, <8 x i64> %1, <8 x i64> %2) local_unnamed_addr {
Entry:
  %3 = or <8 x i64> %2, %1
  %4 = xor <8 x i64> %3, <i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1>
  %5 = and <8 x i64> %4, %0
  ret <8 x i64> %5
}

define dso_local <8 x i64> @foobar(<8 x i64> %0, <8 x i64> %1, <8 x i64> %2, <8 x i64> %3, <8 x i64> %4) local_unnamed_addr {
Entry:
  %.not.i = xor <8 x i64> %1, <i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1>
  %5 = or <8 x i64> %.not.i, %2
  %6 = and <8 x i64> %5, %0
  %7 = or <8 x i64> %4, %3
  %8 = xor <8 x i64> %7, <i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1>
  %9 = and <8 x i64> %6, %8
  ret <8 x i64> %9
}

Emit (from LLVM IR godbolt):

foo:
        vpternlogq      zmm0, zmm2, zmm1, 208
        ret

bar:
        vpternlogq      zmm0, zmm2, zmm1, 16
        ret

foobar:
        vpandnq zmm1, zmm2, zmm1
        vporq   zmm3, zmm4, zmm3
        vpternlogq      zmm0, zmm1, zmm3, 16
        ret

foobar should be:

foobar:
        vpternlogq      zmm0, zmm1, zmm2, 176
        vpternlogq      zmm0, zmm3, zmm4, 16
        ret

[llvmbot]

@llvm/issue-subscribers-backend-x86

Author: Niles Salter (Validark)

Consider: ([Godbolt link](https://zig.godbo.lt/#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaPECAMzwBtMA7AQwFtMQByARg9KtQYEAysib0QXACx8BBAKoBnTAAUAHpwAMvAFYTStJg1AAvPMFJL6yAngGVG6AMKpaAVxYM9DgDJ4GmADl3ACNMYhAAZgBWUgAHVAVCWwZnNw89eMSbAV9/IJZQ8OiLTCtshiECJmICVPdPLhKy5MrqglzAkLDImIUqmrr0xr62jvzCnoBKC1RXYmR2DkxVeJqAaioGDdRUCCYQNYABADVMaxIIAA5SNdcANklpteCDk7OiYiub%2B8eb5FfTudPtdbg9JpMjoCPl9QY81gBSADsACF4RoAIJrLFrYiYAhzLZ7BEAJjuawAfhBgiSyeTkOD4RFURikQARNHojmbbaoAD6TAULD2APeFxBPyeL0houB3zBfxFQJhEohbyV4rBCJRHOxOLxBLWADdYgQwgxaKhgHsbsE/jcuIi7pNGczOYj2SyMctVgQNltgtVhdL1XLfs9FdCNWH/sHI6HwbGxfGta7dbj8cQtkwaRTqfDSRTkC6OWySxjucYdvzBUG1XHYZKI0mGwrE7KG6qoc2JSmddj0wbjabMxarUwbXa1lwncWWe6y%2BjvSRfdz%2BKgA599m3lfLw9uo08Y3Xu7v0E32xKbux9/HOzKd3Ckan%2B/rM89A2vrc8/k90FfnUyJbzp6i4rMufo8hu1ZClux4XruUpwQ%2Bh7nshNxnjeLZrNeSEHneIYNr2GJpq%2BWyVnyApCmu0Ffraaz0uh/6zm6HqcuWWxDmao4QIaZy8lwqEHjcvHILyxKCfGwl8REElYWgLAmngbBrBQKkRMS%2BH1j2T59lihrVHqCiuLQvqMqyRp8VwzG6pRRouEwNj0GsEC6bqCJRI48IeUaJpcZaACOJJRF5yJKSwXmsjc%2BbBVEyIibyEQRVFxIxXFfHEklQUhfFVlRKxbnYgc2WWRFJIZcSyKqPmxLObiRkmc6xEFWsRWxfFGV5WVVXEjVPHpU8xWiYlnXVd1vXxREA2xWFpXVQw1XOXg0yubqICuQBz5YgOb51cZBDMaWGIcNMtCcFEvCeBwWikKgnAAFpmGsCizPMmAkhEPCkAQmjHdMADWIBRBo%2BicJIF0/TdnC8AoIDA99V3HaQcCwEg8mxHQYTkJQaMY%2BExgEMQrgMH9fB0MOMNUhDwR%2BNUACenCfdTzDELTADywTaO8DO8PJbCCKz5r0wjpBYMErjAI4Yi0DD3C8FgLCGMA4jC/guLWHgvEy9dyxnK4prc%2BQgilBDtB4MExB084WAQwTSkG7xxDBAkmCspgCtGKbRg/dMVAGMACjHHgmAAO6s7EjAG/wggiGI7BSDIgiKCo6jC7oxL6IrICmOYpvBDDkDTKgikCDLAC0rNrAASqUmACpgABiAq%2BqX/TAHiayqJcdy8g8pee64qhrKXLDILErhmcYDAO%2BdN0O8QeBYPnEDTJY7zJPYDBOC49ReJvYxdOEjSZEkAiDA0cQJCfDD7wU3TDDX6sCK0Azb0MTRr0//TtH4nS34fFhfzPnoEYNQb4TC4CvF6CwJAnTOuDYWt0OBrGzmsAmRM/rOVwIQEg70IG8HhlocEpAEC1ywOEZepAAZAxBhwMGpAWASA0MDS611EHQ1hl9b2sCODEngawqGnCEZEIdokOwkggA))

export fn foo(a: @<!-- -->Vector(8, u64), b: @<!-- -->Vector(8, u64), c: @<!-- -->Vector(8, u64)) @<!-- -->Vector(8, u64) {
    return (a &amp; ~(b &amp; ~c));
}

export fn bar(a: @<!-- -->Vector(8, u64), b: @<!-- -->Vector(8, u64), c: @<!-- -->Vector(8, u64)) @<!-- -->Vector(8, u64) {
    return a &amp; ~b &amp; ~c;
}

export fn foobar(a: @<!-- -->Vector(8, u64), b: @<!-- -->Vector(8, u64), c: @<!-- -->Vector(8, u64), d: @<!-- -->Vector(8, u64), e: @<!-- -->Vector(8, u64)) @<!-- -->Vector(8, u64) {
    return bar(foo(a, b, c), d, e);
}

LLVM IR (Godbolt link):

define dso_local &lt;8 x i64&gt; @<!-- -->foo(&lt;8 x i64&gt; %0, &lt;8 x i64&gt; %1, &lt;8 x i64&gt; %2) local_unnamed_addr {
Entry:
  %.not = xor &lt;8 x i64&gt; %1, &lt;i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1&gt;
  %3 = or &lt;8 x i64&gt; %.not, %2
  %4 = and &lt;8 x i64&gt; %3, %0
  ret &lt;8 x i64&gt; %4
}

define dso_local &lt;8 x i64&gt; @<!-- -->bar(&lt;8 x i64&gt; %0, &lt;8 x i64&gt; %1, &lt;8 x i64&gt; %2) local_unnamed_addr {
Entry:
  %3 = or &lt;8 x i64&gt; %2, %1
  %4 = xor &lt;8 x i64&gt; %3, &lt;i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1&gt;
  %5 = and &lt;8 x i64&gt; %4, %0
  ret &lt;8 x i64&gt; %5
}

define dso_local &lt;8 x i64&gt; @<!-- -->foobar(&lt;8 x i64&gt; %0, &lt;8 x i64&gt; %1, &lt;8 x i64&gt; %2, &lt;8 x i64&gt; %3, &lt;8 x i64&gt; %4) local_unnamed_addr {
Entry:
  %.not.i = xor &lt;8 x i64&gt; %1, &lt;i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1&gt;
  %5 = or &lt;8 x i64&gt; %.not.i, %2
  %6 = and &lt;8 x i64&gt; %5, %0
  %7 = or &lt;8 x i64&gt; %4, %3
  %8 = xor &lt;8 x i64&gt; %7, &lt;i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1, i64 -1&gt;
  %9 = and &lt;8 x i64&gt; %6, %8
  ret &lt;8 x i64&gt; %9
}

Emit (from LLVM IR godbolt):

foo:
        vpternlogq      zmm0, zmm2, zmm1, 208
        ret

bar:
        vpternlogq      zmm0, zmm2, zmm1, 16
        ret

foobar:
        vpandnq zmm1, zmm2, zmm1
        vporq   zmm3, zmm4, zmm3
        vpternlogq      zmm0, zmm1, zmm3, 16
        ret

foobar should be:

foobar:
        vpternlogq      zmm0, zmm1, zmm2, 176
        vpternlogq      zmm0, zmm3, zmm4, 16
        ret

[Validark]

One hazard I notice is that sometimes LLVM will fold a bitwise-NOT into a vpternlogq by passing in a vector of all 1's... Not unlike how it looks in LLVM IR (xor -1):

export fn foo(a: @Vector(8, u64), b: @Vector(8, u64), c: @Vector(8, u64)) @Vector(8, u64) {
    return ~a & ~b & ~c;
}

foo:
        vporq   zmm1, zmm1, zmm0
        vpternlogd      zmm0, zmm0, zmm0, 255
        vpternlogq      zmm0, zmm1, zmm2, 30
        ret

[RKSimon]

TERNLOG matching is very cautious with multi-use nodes, it might be that we're hitting that.

[Validark]

Also (LLC Godbolt, Zig Godbolt)

export fn fubar(a: @Vector(8, u64), b: @Vector(8, u64), c: @Vector(8, u64), d: @Vector(8, u64), e: @Vector(8, u64), f: @Vector(8, u64), g: @Vector(8, u64), h: @Vector(8, u64), i: @Vector(8, u64)) @Vector(8, u64) {
    return a|b|c|d|e|f|g|h|i;
}

fubar:
        vpternlogq      zmm0, zmm2, zmm1, 254
        vpternlogq      zmm0, zmm4, zmm3, 254
        vpternlogq      zmm0, zmm6, zmm5, 254
        vpternlogq      zmm0, zmm7, zmmword ptr [rbp + 16], 254

Should be:

should_be:
        vpternlogq      zmm6, zmm7, zmmword ptr [rbp + 16], 254
        vpternlogq      zmm0, zmm1, zmm2, 254
        vpternlogq      zmm3, zmm4, zmm5, 254
        vpternlogq      zmm0, zmm3, zmm6, 254

[RKSimon]

CC @yichi170 - are you interested in looking at this after #164863?

[yichi170]

Sure, I'll take a look at it