[X86] Multiple use shift amount mask not removed from SHLX

[Validark]

(Zig Godbolt) (LLVM Godbolt)

define internal i32 @foo(i32 %0, i32 %1) unnamed_addr align 1 {
Entry:
  %2 = and i32 %1, 31
  %3 = shl i32 %0, %2
  %4 = xor i32 %3, %2
  ret i32 %4
}

Compiles to:

foo:
        and     esi, 31
        shlx    eax, edi, esi
        xor     eax, esi
        ret

Should be:

foo:
        shlx    eax, edi, esi
        and     esi, 31
        xor     eax, esi
        ret

[llvmorg-github-actions]

@llvm/issue-subscribers-backend-x86

Author: Niles Salter (Validark)

Details

([Zig Godbolt](https://zig.godbo.lt/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:16,fontUsePx:'0',j:1,lang:zig,selection:(endColumn:1,endLineNumber:5,positionColumn:1,positionLineNumber:5,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:'export+fn+foo(a:+u32,+b:+u32)+u32+%7B%0A++++const+c+%3D+a+%3C%3C+@truncate(b)%3B%0A++++return+c+%5E+(b+%26+31)%3B%0A%7D%0A'),l:'5',n:'0',o:'Zig+source+%231',t:'0')),k:49.9776655687361,l:'4',m:100,n:'0',o:'',s:0,t:'0'),(g:!((g:!((h:compiler,i:(compiler:ztrunk,filters:(b:'0',binary:'1',binaryObject:'1',commentOnly:'0',debugCalls:'1',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1',verboseDemangling:'0'),flagsViewOpen:'1',fontScale:16,fontUsePx:'0',j:2,lang:zig,libs:!(),options:'-O+ReleaseFast+-target+x86_64-linux+-mcpu%3Dznver5+-fomit-frame-pointer',overrides:!(),selection:(endColumn:18,endLineNumber:7,positionColumn:18,positionLineNumber:7,selectionStartColumn:18,selectionStartLineNumber:7,startColumn:18,startLineNumber:7),source:1),l:'5',n:'0',o:'+zig+trunk+(Editor+%231)',t:'0')),header:(),k:50.022334431263914,l:'4',m:50,n:'0',o:'',s:0,t:'0'),(g:!((h:ir,i:('-fno-discard-value-names':'0',compilerName:'zig+trunk',demangle-symbols:'0',editorid:1,filter-attributes:'0',filter-comments:'0',filter-debug-info:'0',filter-declarations:'1',filter-instruction-metadata:'0',filter-library-functions:'1',fontScale:14,fontUsePx:'0',j:2,selection:(endColumn:1,endLineNumber:10,positionColumn:1,positionLineNumber:10,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),show-optimized:'0',treeid:0,wrap:'1'),l:'5',n:'0',o:'LLVM+IR+Viewer+zig+trunk+(Editor+%231,+Compiler+%232)',t:'0')),header:(),l:'4',m:50,n:'0',o:'',s:0,t:'0')),k:50.022334431263914,l:'3',n:'0',o:'',t:'0')),l:'2',m:100,n:'0',o:'',t:'0')),version:4)) ([LLVM Godbolt](https://llvm.godbo.lt/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:llvm,selection:(endColumn:2,endLineNumber:7,positionColumn:2,positionLineNumber:7,selectionStartColumn:2,selectionStartLineNumber:7,startColumn:2,startLineNumber:7),source:'define+internal+i32+@foo(i32+%250,+i32+%251)+unnamed_addr+align+1+%7B%0AEntry:%0A++%252+%3D+and+i32+%251,+31%0A++%253+%3D+shl+i32+%250,+%252%0A++%254+%3D+xor+i32+%253,+%252%0A++ret+i32+%254%0A%7D'),l:'5',n:'0',o:'LLVM+IR+source+%231',t:'0')),k:53.04858167590479,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:llctrunk,filters:(b:'0',binary:'1',binaryObject:'1',commentOnly:'0',debugCalls:'1',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1',verboseDemangling:'0'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:llvm,libs:!(),options:'-O3+-mcpu%3Dznver5',overrides:!(),selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'+llc+(trunk)+(Editor+%231)',t:'0')),k:46.95141832409521,l:'4',m:100,n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4)) ```llvm define internal i32 @foo(i32 %0, i32 %1) unnamed_addr align 1 { Entry: %2 = and i32 %1, 31 %3 = shl i32 %0, %2 %4 = xor i32 %3, %2 ret i32 %4 } ```

Compiles to:

foo:
        and     esi, 31
        shlx    eax, edi, esi
        xor     eax, esi
        ret

Should be:

foo:
        shlx    eax, edi, esi
        and     esi, 31
        xor     eax, esi
        ret

[RKSimon]

SHRX/SARX suffer from the same issue

[Validark]

Should I open a separate issue for ARM and RISC-V? The same optimization is applicable in GPR's on those arches, and any other that implicitly only look at the bottom bits when deciding how much to shift. In vector space, the optimization is a little more elusive. shld/shrd and rotr/rotl in AVX512_VBMI2 both operate on a truncated part of the register. This is technically applicable to the 52-bit multiply instructions too, but in my code I tend not to have explicit AND's with 52 1 bits. This optimization is important though, because the Zig language forces you to truncate or int-cast for shifts.

[RKSimon]

We need a better way for tablegen to handle this for shift amount masking - we currently just pattern match the AND, which fails if the AND has multiple uses - that could then be used for other targets.

Feel free to raise separate tickets for MADD52 if you can find actual cases.

[Validark]

Right now actual cases of madd52 missed optimizations of this kind are impossible because LLVM doesn't look for even straightforward madd52 opportunities. E.g. this could compile to an madd52luq instruction:

export fn madd52luq(x: @Vector(8, u64), y: @Vector(8, u64)) @Vector(8, u64) {
    const V = @Vector(8, u52);
    return @as(V, @truncate(x)) *% @as(V, @truncate(y));
}

One could imagine I could use the "truncated" x or y in two places, and that would likely trigger the problem in this issue, if it were unlocked by other optimizations.

But I agree, one step at a time. I just wish this sort of thing could be applied generically across all operations that ignore some of the bits in a register.

[RKSimon]

Bear in mind that the result of the MADD52 multiply stage must fit into the a u52 as well (not just the operands) - typically a VPMULUDQ will be better if you're not accumulating after the multiply.