[X86][MC] Always emit `rep` prefix for `bsf`

[pengfei]

Summary

BMI new instruction tzcnt has better performance than bsf on new
processors. Its encoding has a mandatory prefix '0xf3' compared to
bsf. If we force emit rep prefix for bsf, we will gain better
performance when the same code run on new processors.

GCC has already done this way: https://c.godbolt.org/z/6xere6fs1

Fixes #34191

[craig.topper]

Assembler should faithful to the original source. This needs to be done at codegen only I would think.

[craig.topper]

Also need to print the rep in the assembly listing so -fno-integrated-as works

[pengfei]

In D130956#3692469, @craig.topper wrote:

Assembler should faithful to the original source. This needs to be done at codegen only I would think.

I see, how about changing the assembly string to "rep bsf{w}\t{$src, $dst|$dst, $src}"?

[skan]

I believe Linus's suggestion is adding a prefix to BSF rather than changing the encoding.
Maybe you can consider implementing it in X86MCInstLower::Lower by using Flags of MCInst.

[skan]

In D130956#3692473, @pengfei wrote:

In D130956#3692469, @craig.topper wrote:

Assembler should faithful to the original source. This needs to be done at codegen only I would think.

I see, how about changing the assembly string to "rep bsf{w}\t{$src, $dst|$dst, $src}"?

No, I don't think it is a good way. It breaks the support of original bsf.

[craig.topper]

This basically need to be done with a CodeGenOnly pseudo instruction. We can’t change assembler or disassembler behavior

[pengfei]

In D130956#3692473, @pengfei wrote:

In D130956#3692469, @craig.topper wrote:

Assembler should faithful to the original source. This needs to be done at codegen only I would think.

I see, how about changing the assembly string to "rep bsf{w}\t{$src, $dst|$dst, $src}"?

Oh, we can't do it consider the decoding. I'll reconsider the solution. Thanks!

Maybe you can consider implementing it in X86MCInstLower::Lower by using Flags of MCInst.

Thanks for the suggestion, let me have a try.

[pengfei]

Compared both methods, adding flag in X86MCInstLower::Lower seems convenient. Thanks Craig and Shengchen!

[nikic]

llvm/lib/Target/X86/X86MCInstLower.cpp

986 ↗

(On Diff #449198)

Add a comment to explain why we do this?

[pengfei]

Add comment. Thanks @nikic

[skan]

llvm/lib/Target/X86/X86MCInstLower.cpp

987 ↗

(On Diff #449203)

Do we need to check any target feature here?

[craig.topper]

llvm/test/CodeGen/X86/clz.ll

49 ↗

(On Diff #449203)

We need to promote bsrw to bsrl. tzcntl is faster than tzcntw. tzcntw has a false dependency to preserve the upper 48 bits of the result register in Intel CPUs. But separate patch please.

[craig.topper]

llvm/lib/Target/X86/X86MCInstLower.cpp

987 ↗

(On Diff #449203)

I don’t think so.

Probably should skip for minsize though?

[skan]

llvm/lib/Target/X86/X86MCInstLower.cpp

987 ↗

(On Diff #449203)

I think it's a good suggestion.

[pengfei]

Add check for minsize.

llvm/lib/Target/X86/X86MCInstLower.cpp

987 ↗

(On Diff #449203)

Agreed. And good point! Added check for minsize.

[aaronpuchert]

By the way, the original bug for this is #34191.

llvm/test/CodeGen/X86/peephole-na-phys-copy-folding.ll

376 ↗

(On Diff #449214)

Goes a bit too far I think. We can turn a generic builtin into rep; bsf, but if the inline assembly explicitly asks for bsf I think we should emit that.

[pengfei]

llvm/test/CodeGen/X86/peephole-na-phys-copy-folding.ll

376 ↗

(On Diff #449214)

You are right. So this is to check *no* REP prefix was generated. :)

[pengfei]

llvm/test/CodeGen/X86/clz.ll

49 ↗

(On Diff #449203)

Can we allow to always do that? The result is not equal for tzcnt if we care the src is 0: https://godbolt.org/z/enahabbM7

[craig.topper]

llvm/test/CodeGen/X86/clz.ll

49 ↗

(On Diff #449203)

I meant in SelectionDAG.

[RKSimon]

llvm/test/CodeGen/X86/clz.ll

1114 ↗

(On Diff #449214)

please can you add a minsize test as well ?

[pengfei]

Add minsize test.

[aaronpuchert]

llvm/test/CodeGen/X86/peephole-na-phys-copy-folding.ll

376 ↗

(On Diff #449214)

Sorry, I missed the -NOT. But is that needed? After all the -NEXT shouldn't match if there is a rep in between.

If there is a reason to keep this, the second occurrence should likely be CHECK64 instead of CHECK32.

[skan]

llvm/test/CodeGen/X86/peephole-na-phys-copy-folding.ll

376 ↗

(On Diff #449214)

I think the two CHECK-NOT are redundant here b/c CHECK-NEXT can gurantee #APP is followed by bsfl.

[craig.topper]

llvm/test/CodeGen/X86/peephole-na-phys-copy-folding.ll

376 ↗

(On Diff #449214)

Doesn't the CHECK-NEXT only guarantee that the next line contains bsfl. It doesn't rule out any text before the bsfl.

[skan]

llvm/test/CodeGen/X86/peephole-na-phys-copy-folding.ll

376 ↗

(On Diff #449214)

I think if there is rep between #APP and #NO_APP, the following check will fail.

; CHECK32-NEXT:    #APP
; CHECK32-NEXT:    bsfl %edx, %edx
; CHECK32-NEXT:    #NO_APP

[craig.topper]

llvm/test/CodeGen/X86/peephole-na-phys-copy-folding.ll

376 ↗

(On Diff #449214)

The test still passes with this change

diff --git a/llvm/test/CodeGen/X86/peephole-na-phys-copy-folding.ll b/llvm/test/CodeGen/X86/peephole-na-phys-copy-folding.ll
index f3d4b6221d08..4c7094d5c5f0 100644
--- a/llvm/test/CodeGen/X86/peephole-na-phys-copy-folding.ll
+++ b/llvm/test/CodeGen/X86/peephole-na-phys-copy-folding.ll
@@ -371,7 +371,7 @@ define i1 @asm_clobbering_flags(ptr %mem) nounwind {
 entry:
   %val = load i32, ptr %mem, align 4
   %cmp = icmp sgt i32 %val, 0
-  %res = tail call i32 asm "bsfl $1,$0", "=r,r,~{cc},~{dirflag},~{fpsr},~{flags}"(i32 %val)
+  %res = tail call i32 asm "rep bsfl $1,$0", "=r,r,~{cc},~{dirflag},~{fpsr},~{flags}"(i32 %val)
   store i32 %res, ptr %mem, align 4
   ret i1 %cmp

That puts rep on the same line before bsfl in the output. Every test change in this review shows rep on the same line as the bsfl.

[pengfei]

Fix the check prefix error.

llvm/test/CodeGen/X86/peephole-na-phys-copy-folding.ll

376 ↗

(On Diff #449214)

Craig is correct. We'd better to add explicit check to avoid false negative, though I think re-generate from tool will emit the rep for the opposite case.

[skan]

LGTM

[fmayer]

This seems related to an error we see on our sanitizer bots: https://lab.llvm.org/buildbot/#/builders/37/builds/15446/steps/33/logs/stdio

FAIL: Builtins-i386-linux :: ffssi2_test.c (2860 of 8387)
******************** TEST 'Builtins-i386-linux :: ffssi2_test.c' FAILED ********************
Script:
--
: 'RUN: at line 1';       /b/sanitizer-x86_64-linux/build/llvm_build64/bin/clang   -gline-tables-only  -m32 -DCOMPILER_RT_HAS_FLOAT16  -fno-builtin -I /b/sanitizer-x86_64-linux/build/llvm-project/compiler-rt/lib/builtins -nodefaultlibs /b/sanitizer-x86_64-linux/build/llvm-project/compiler-rt/test/builtins/Unit/ffssi2_test.c /b/sanitizer-x86_64-linux/build/compiler_rt_build/lib/linux/libclang_rt.builtins-i386.a -lc -lm -o /b/sanitizer-x86_64-linux/build/compiler_rt_build/test/builtins/Unit/I386LinuxConfig/Output/ffssi2_test.c.tmp &&  /b/sanitizer-x86_64-linux/build/compiler_rt_build/test/builtins/Unit/I386LinuxConfig/Output/ffssi2_test.c.tmp
--
Exit Code: 1
Command Output (stdout):
--
error in __ffssi2(0x0) = 33, expected 0
--
********************
Testing:  0.. 10.. 20.. 30.
FAIL: Builtins-x86_64-linux :: ffssi2_test.c (3084 of 8387)
******************** TEST 'Builtins-x86_64-linux :: ffssi2_test.c' FAILED ********************
Script:
--
: 'RUN: at line 1';       /b/sanitizer-x86_64-linux/build/llvm_build64/bin/clang   -gline-tables-only  -m64 -DCOMPILER_RT_HAS_FLOAT16  -fno-builtin -I /b/sanitizer-x86_64-linux/build/llvm-project/compiler-rt/lib/builtins -nodefaultlibs /b/sanitizer-x86_64-linux/build/llvm-project/compiler-rt/test/builtins/Unit/ffssi2_test.c /b/sanitizer-x86_64-linux/build/compiler_rt_build/lib/linux/libclang_rt.builtins-x86_64.a -lc -lm -o /b/sanitizer-x86_64-linux/build/compiler_rt_build/test/builtins/Unit/X86_64LinuxConfig/Output/ffssi2_test.c.tmp &&  /b/sanitizer-x86_64-linux/build/compiler_rt_build/test/builtins/Unit/X86_64LinuxConfig/Output/ffssi2_test.c.tmp
--
Exit Code: 1
Command Output (stdout):
--
error in __ffssi2(0x0) = 33, expected 0
--
********************
Testing:  0.. 10.. 20.. 30.. 40.. 50.. 60.. 70.. 80.. 90..

[craig.topper]

In D130956#3697844, @fmayer wrote:

This seems related to an error we see on our sanitizer bots: https://lab.llvm.org/buildbot/#/builders/37/builds/15446/steps/33/logs/stdio

FAIL: Builtins-i386-linux :: ffssi2_test.c (2860 of 8387)
******************** TEST 'Builtins-i386-linux :: ffssi2_test.c' FAILED ********************
Script:
--
: 'RUN: at line 1';       /b/sanitizer-x86_64-linux/build/llvm_build64/bin/clang   -gline-tables-only  -m32 -DCOMPILER_RT_HAS_FLOAT16  -fno-builtin -I /b/sanitizer-x86_64-linux/build/llvm-project/compiler-rt/lib/builtins -nodefaultlibs /b/sanitizer-x86_64-linux/build/llvm-project/compiler-rt/test/builtins/Unit/ffssi2_test.c /b/sanitizer-x86_64-linux/build/compiler_rt_build/lib/linux/libclang_rt.builtins-i386.a -lc -lm -o /b/sanitizer-x86_64-linux/build/compiler_rt_build/test/builtins/Unit/I386LinuxConfig/Output/ffssi2_test.c.tmp &&  /b/sanitizer-x86_64-linux/build/compiler_rt_build/test/builtins/Unit/I386LinuxConfig/Output/ffssi2_test.c.tmp
--
Exit Code: 1
Command Output (stdout):
--
error in __ffssi2(0x0) = 33, expected 0
--
********************
Testing:  0.. 10.. 20.. 30.
FAIL: Builtins-x86_64-linux :: ffssi2_test.c (3084 of 8387)
******************** TEST 'Builtins-x86_64-linux :: ffssi2_test.c' FAILED ********************
Script:
--
: 'RUN: at line 1';       /b/sanitizer-x86_64-linux/build/llvm_build64/bin/clang   -gline-tables-only  -m64 -DCOMPILER_RT_HAS_FLOAT16  -fno-builtin -I /b/sanitizer-x86_64-linux/build/llvm-project/compiler-rt/lib/builtins -nodefaultlibs /b/sanitizer-x86_64-linux/build/llvm-project/compiler-rt/test/builtins/Unit/ffssi2_test.c /b/sanitizer-x86_64-linux/build/compiler_rt_build/lib/linux/libclang_rt.builtins-x86_64.a -lc -lm -o /b/sanitizer-x86_64-linux/build/compiler_rt_build/test/builtins/Unit/X86_64LinuxConfig/Output/ffssi2_test.c.tmp &&  /b/sanitizer-x86_64-linux/build/compiler_rt_build/test/builtins/Unit/X86_64LinuxConfig/Output/ffssi2_test.c.tmp
--
Exit Code: 1
Command Output (stdout):
--
error in __ffssi2(0x0) = 33, expected 0
--
********************
Testing:  0.. 10.. 20.. 30.. 40.. 50.. 60.. 70.. 80.. 90..

Random guess, we forgot to take into account that tzcnt and bsf don't set the flags the same way. If the flags from the bsf are being used we can't put an f3 in front of it.

[craig.topper]

I'll revert, I'll have to do a fixup for a dependent patch that I committed after this.

[fmayer]

In D130956#3697869, @craig.topper wrote:

I'll revert, I'll have to do a fixup for a dependent patch that I committed after this.

Thanks! I can also verify that a revert actually fixes this, but judging from the Changes in the first build that introduced the failure, I think it's very likely that it was this.

[craig.topper]

In D130956#3697870, @fmayer wrote:

In D130956#3697869, @craig.topper wrote:

I'll revert, I'll have to do a fixup for a dependent patch that I committed after this.

Thanks! I can also verify that a revert actually fixes this, but judging from the Changes in the first build that introduced the failure, I think it's very likely that it was this.

It was definitely this. The ffs in the name of the failing function is 'find first set' bit. That's what the bsf and tzcnt instructions do.

[craig.topper]

llvm/test/CodeGen/X86/dagcombine-select.ll

310 ↗

(On Diff #449601)

This is incorrect. If the instruction is detected as tzcnt, the cmov would need to be cmovaeq not cmovneq. Since we can't know at compile time which CPU we'll be running on. We can't do this transform if the flags are used.

[pengfei]

Make sure EFLAGS is not used.

Didn't notice the differences on the EFLAG. Thanks @fmayer and @craig.topper!

[craig.topper]

LGTM with the comment typo fixed

llvm/lib/Target/X86/X86MCInstLower.cpp

989 ↗

(On Diff #449881)

latter -> later

[pengfei]

Thanks @craig.topper!

llvm/lib/Target/X86/X86InstrInfo.td

def BSWAP64r : RI<0xC8, AddRegFrm, (outs GR64:$dst), (ins GR64:$src),
                   [(set GR64:$dst, (bswap GR64:$src))]>, TB;
 } // Constraints = "$src = $dst", SchedRW
 
 // Bit scan instructions.
 let Defs = [EFLAGS] in {
 def BSF16rr  : I<0xBC, MRMSrcReg, (outs GR16:$dst), (ins GR16:$src),
                  "bsf{w}\t{$src, $dst|$dst, $src}",
                  [(set GR16:$dst, EFLAGS, (X86bsf GR16:$src))]>,
-                  PS, OpSize16, Sched<[WriteBSF]>;
+                  PS, OpSize16, REP, Sched<[WriteBSF]>;
 def BSF16rm  : I<0xBC, MRMSrcMem, (outs GR16:$dst), (ins i16mem:$src),
                  "bsf{w}\t{$src, $dst|$dst, $src}",
                  [(set GR16:$dst, EFLAGS, (X86bsf (loadi16 addr:$src)))]>,
-                 PS, OpSize16, Sched<[WriteBSFLd]>;
+                 PS, OpSize16, REP, Sched<[WriteBSFLd]>;
 def BSF32rr  : I<0xBC, MRMSrcReg, (outs GR32:$dst), (ins GR32:$src),
                  "bsf{l}\t{$src, $dst|$dst, $src}",
                  [(set GR32:$dst, EFLAGS, (X86bsf GR32:$src))]>,
-                 PS, OpSize32, Sched<[WriteBSF]>;
+                 PS, OpSize32, REP, Sched<[WriteBSF]>;
 def BSF32rm  : I<0xBC, MRMSrcMem, (outs GR32:$dst), (ins i32mem:$src),
                  "bsf{l}\t{$src, $dst|$dst, $src}",
                  [(set GR32:$dst, EFLAGS, (X86bsf (loadi32 addr:$src)))]>,
-                 PS, OpSize32, Sched<[WriteBSFLd]>;
+                 PS, OpSize32, REP, Sched<[WriteBSFLd]>;
 def BSF64rr  : RI<0xBC, MRMSrcReg, (outs GR64:$dst), (ins GR64:$src),
                   "bsf{q}\t{$src, $dst|$dst, $src}",
                   [(set GR64:$dst, EFLAGS, (X86bsf GR64:$src))]>,
-                  PS, Sched<[WriteBSF]>;
+                  PS, REP, Sched<[WriteBSF]>;
 def BSF64rm  : RI<0xBC, MRMSrcMem, (outs GR64:$dst), (ins i64mem:$src),
                   "bsf{q}\t{$src, $dst|$dst, $src}",
                   [(set GR64:$dst, EFLAGS, (X86bsf (loadi64 addr:$src)))]>,
-                  PS, Sched<[WriteBSFLd]>;
+                  PS, REP, Sched<[WriteBSFLd]>;
 
 def BSR16rr  : I<0xBD, MRMSrcReg, (outs GR16:$dst), (ins GR16:$src),
                  "bsr{w}\t{$src, $dst|$dst, $src}",
                  [(set GR16:$dst, EFLAGS, (X86bsr GR16:$src))]>,
                  PS, OpSize16, Sched<[WriteBSR]>;
 def BSR16rm  : I<0xBD, MRMSrcMem, (outs GR16:$dst), (ins i16mem:$src),
                  "bsr{w}\t{$src, $dst|$dst, $src}",
                  [(set GR16:$dst, EFLAGS, (X86bsr (loadi16 addr:$src)))]>,

llvm/test/MC/X86/I386-32.s

 // RUN: llvm-mc -triple i386-unknown-unknown --show-encoding %s | FileCheck %s
 
 // CHECK: bsfw %ax, %ax 
-// CHECK: encoding: [0x66,0x0f,0xbc,0xc0]        
+// CHECK: encoding: [0xf3,0x66,0x0f,0xbc,0xc0]        
 bsfw %ax, %ax 
 
 // CHECK: bsrw %ax, %ax 
 // CHECK: encoding: [0x66,0x0f,0xbd,0xc0]        
 bsrw %ax, %ax 
 
 // CHECK: bsfl %eax, %eax 
-// CHECK: encoding: [0x0f,0xbc,0xc0]        
+// CHECK: encoding: [0xf3,0x0f,0xbc,0xc0]        
 bsfl %eax, %eax 
 
 // CHECK: bsrl %eax, %eax 
 // CHECK: encoding: [0x0f,0xbd,0xc0]        
 bsrl %eax, %eax 
 
 // CHECK: btcw $0, %ax 
 // CHECK: encoding: [0x66,0x0f,0xba,0xf8,0x00]        

llvm/test/MC/X86/I386-64.s

 // RUN: llvm-mc -triple x86_64-unknown-unknown --show-encoding %s | FileCheck %s
 
 // CHECK: bsfw %r13w, %r13w 
-// CHECK: encoding: [0x66,0x45,0x0f,0xbc,0xed]        
+// CHECK: encoding: [0xf3,0x66,0x45,0x0f,0xbc,0xed]        
 bsfw %r13w, %r13w 
 
 // CHECK: bsrw %r13w, %r13w 
 // CHECK: encoding: [0x66,0x45,0x0f,0xbd,0xed]        
 bsrw %r13w, %r13w 
 
 // CHECK: bsfl %r13d, %r13d 
-// CHECK: encoding: [0x45,0x0f,0xbc,0xed]        
+// CHECK: encoding: [0xf3,0x45,0x0f,0xbc,0xed]        
 bsfl %r13d, %r13d 
 
 // CHECK: bsrl %r13d, %r13d 
 // CHECK: encoding: [0x45,0x0f,0xbd,0xed]        
 bsrl %r13d, %r13d 
 
 // CHECK: bsfq %r13, %r13 
-// CHECK: encoding: [0x4d,0x0f,0xbc,0xed]        
+// CHECK: encoding: [0xf3,0x4d,0x0f,0xbc,0xed]        
 bsfq %r13, %r13 
 
 // CHECK: bsrq %r13, %r13 
 // CHECK: encoding: [0x4d,0x0f,0xbd,0xed]        
 bsrq %r13, %r13 
 
 
 // CHECK: btcw $0, %r13w 

llvm/test/MC/X86/x86-32-coverage.s

 
 // rdar://8017638
 // CHECK: aeskeygenassist $128, %xmm1, %xmm2
 // CHECK:  encoding: [0x66,0x0f,0x3a,0xdf,0xd1,0x80]
     aeskeygenassist $128, %xmm1, %xmm2
 
 // rdar://7910087
 // CHECK: bsfw  %bx, %bx
-// CHECK:  encoding: [0x66,0x0f,0xbc,0xdb]
+// CHECK:  encoding: [0xf3,0x66,0x0f,0xbc,0xdb]
           bsfw  %bx, %bx
 
 // CHECK: bsfw  3735928559(%ebx,%ecx,8), %bx
-// CHECK:  encoding: [0x66,0x0f,0xbc,0x9c,0xcb,0xef,0xbe,0xad,0xde]
+// CHECK:  encoding: [0xf3,0x66,0x0f,0xbc,0x9c,0xcb,0xef,0xbe,0xad,0xde]
           bsfw  3735928559(%ebx,%ecx,8), %bx
 
 // CHECK: bsrw  %bx, %bx
 // CHECK:  encoding: [0x66,0x0f,0xbd,0xdb]
           bsrw  %bx, %bx
 
 // CHECK: bsrw  305419896, %bx
 // CHECK:  encoding: [0x66,0x0f,0xbd,0x1d,0x78,0x56,0x34,0x12]