[x86-64] Allow branching on shl/shr setting zero flag

[Validark]

Zig Godbolt

export fn shl_test(x: u64, _: u8, _: u8, y: u8) bool {
    return 0 == x << @truncate(y);
}

shl_test:
        shl     rdi, cl
-       test    rdi, rdi
        sete    al
        ret

[GrumpyPigSkin]

This would cause a bug if y == 0. If y is 0 then a shift by 0 is basically a no op and the flags remain unchanged from the last instruction which would be a bug, this is why the test is needed to make sure the flags are set. If the shift is guaranteed > 0, then that test instruction can be optimized away (and it is):

shl_test(int, int):
        sal     edi, 5
        sete    al
        ret

More info on the instructions:
https://www.felixcloutier.com/x86/sal:sar:shl:shr

[llvmbot]

@llvm/issue-subscribers-backend-x86

Author: Niles Salter (Validark)

[Zig Godbolt](https://zig.godbo.lt/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:zig,selection:(endColumn:2,endLineNumber:3,positionColumn:2,positionLineNumber:3,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:'export+fn+shl_test(x:+u64,+_:+u8,+_:+u8,+y:+u8)+bool+%7B%0A++++return+0+%3D%3D+x+%3C%3C+@truncate(y)%3B%0A%7D'),l:'5',n:'0',o:'Zig+source+%231',t:'0')),k:100.00000000000001,l:'4',m:50,n:'0',o:'',s:0,t:'0'),(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:14,fontUsePx:'0',j:2,lang:zig,libs:!(),options:'-O+ReleaseFast+-target+x86_64-linux+-mcpu%3Dicelake_server-bmi2+-fomit-frame-pointer',overrides:!(),selection:(endColumn:12,endLineNumber:5,positionColumn:12,positionLineNumber:5,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'+zig+trunk+(Editor+%231)',t:'0')),header:(),l:'4',m:50,n:'0',o:'',s:0,t:'0')),l:'3',n:'0',o:'',t:'0')),version:4)

export fn shl_test(x: u64, _: u8, _: u8, y: u8) bool {
    return 0 == x &lt;&lt; @<!-- -->truncate(y);
}

shl_test:
        shl     rdi, cl
-       test    rdi, rdi
        sete    al
        ret

[RKSimon]

As well as the shift-by-zero issue, reading eflags from shift by var ops can cause problems due to some additional stalls on some architectures.

[Explorer09]

Um... https://godbolt.org/z/a5e8hMfYx

char shl_test(unsigned long x, int dummy, int dummy2, int y) {
    if (y < 1) __builtin_unreachable();
    if (y > 31) __builtin_unreachable();
    return 0 == (x << y);
}

shl_test:
        shl     rdi, cl
        test    rdi, rdi
        sete    al
        ret

Clang misses when y is not a compile time constant, but declared to be never zero by a conditional if (y == 0) __builtin_unreachable();.

[GrumpyPigSkin]

@Explorer09 I had a quick look at this, I think I have a fix for it, but essentially when we get to the actual shift all the data for:

    if (y < 1) __builtin_unreachable();
    if (y > 31) __builtin_unreachable();

Is gone.

Now detecting that pattern is a pain, but the equivalent (the shift instructions mask any values larger than 31 automatically):

char shl_test(unsigned x, int y) {
    __builtin_assume(y > 0);
    return 0 == (x << y);
}

Is quite easy to detect but it needs some work in order to save the range rather than just deleting the __builtin_assume (which is what normally happens when lowering).

@RKSimon If you think it is worth it, assign this to me and I can make a PR :)

[Explorer09]

@GrumpyPigSkin The point of my if (y < 1) __builtin_unreachable(); is to hint to the compiler that the y is always in the range for a valid shift. A shift value that is >= the bit width is an undefined behavior already. But what i'm telling to the compiler is "don't care for y==0 case", and for that assumption Clang can optimize out the test instruction.

[GrumpyPigSkin]

@Explorer09 I get that, but what I'm saying is if (y < 1) __builtin_unreachable(); is functionally equivalent to __builtin_assume(y > 0); , where the latter is much easier to detect and also less code, so I will add a check in for that and delete the test