[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

Add a comment to explain why we do this?

[pengfei]

Add comment. Thanks @nikic

[skan]

llvm/lib/Target/X86/X86MCInstLower.cpp

987

Do we need to check any target feature here?

[craig.topper]

llvm/test/CodeGen/X86/clz.ll

49–50

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

I don’t think so.

Probably should skip for minsize though?

[skan]

llvm/lib/Target/X86/X86MCInstLower.cpp

987

I think it's a good suggestion.

[pengfei]

Add check for minsize.

llvm/lib/Target/X86/X86MCInstLower.cpp

987

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

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

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

[pengfei]

llvm/test/CodeGen/X86/clz.ll

49–50

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–50

I meant in SelectionDAG.

[RKSimon]

llvm/test/CodeGen/X86/clz.ll

1128

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

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

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

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

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

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

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

latter -> later

[pengfei]

Thanks @craig.topper!

llvm/lib/Target/X86/X86MCInstLower.cpp

if (MI->getDesc().isCommutable() &&
         (TSFlags & X86II::OpMapMask) == X86II::TB &&
         (TSFlags & X86II::FormMask) == X86II::MRMSrcReg &&
         !(TSFlags & X86II::VEX_W) && (TSFlags & X86II::VEX_4V) &&
         OutMI.getNumOperands() == 3) {
       if (!X86II::isX86_64ExtendedReg(OutMI.getOperand(1).getReg()) &&
           X86II::isX86_64ExtendedReg(OutMI.getOperand(2).getReg()))
         std::swap(OutMI.getOperand(1), OutMI.getOperand(2));
     }
+    // Add an REP prefix to BSF instructions so that new processors can
+    // recognize as TZCNT, which has better performance than BSF.
+    if (X86::isBSF(OutMI.getOpcode()) && !MF.getFunction().hasOptSize()) {
+      // BSF and TZCNT have different interpretations on ZF bit. So make sure
+      // it won't be used later.
+      const MachineOperand *FlagDef = MI->findRegisterDefOperand(X86::EFLAGS);
+      if (FlagDef && FlagDef->isDead())
+        OutMI.setFlags(X86::IP_HAS_REPEAT);
+    }
     break;
   }
   }
 }
 
 void X86AsmPrinter::LowerTlsAddr(X86MCInstLower &MCInstLowering,
                                  const MachineInstr &MI) {
   NoAutoPaddingScope NoPadScope(*OutStreamer);

llvm/test/CodeGen/X86/clz.ll

 declare i8 @llvm.ctlz.i8(i8, i1)
 declare i16 @llvm.ctlz.i16(i16, i1)
 declare i32 @llvm.ctlz.i32(i32, i1)
 declare i64 @llvm.ctlz.i64(i64, i1)
 
 define i8 @cttz_i8(i8 %x)  {
 ; X86-LABEL: cttz_i8:
 ; X86:       # %bb.0:
-; X86-NEXT:    bsfl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    rep bsfl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    # kill: def $al killed $al killed $eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: cttz_i8:
 ; X64:       # %bb.0:
-; X64-NEXT:    bsfl %edi, %eax
+; X64-NEXT:    rep bsfl %edi, %eax
 ; X64-NEXT:    # kill: def $al killed $al killed $eax
 ; X64-NEXT:    retq
 ;
 ; X86-CLZ-LABEL: cttz_i8:
 ; X86-CLZ:       # %bb.0:
 ; X86-CLZ-NEXT:    tzcntl {{[0-9]+}}(%esp), %eax
 ; X86-CLZ-NEXT:    # kill: def $al killed $al killed $eax
 ; X86-CLZ-NEXT:    retl
 ;
 ; X64-CLZ-LABEL: cttz_i8:
 ; X64-CLZ:       # %bb.0:
 ; X64-CLZ-NEXT:    tzcntl %edi, %eax
 ; X64-CLZ-NEXT:    # kill: def $al killed $al killed $eax
 ; X64-CLZ-NEXT:    retq
   %tmp = call i8 @llvm.cttz.i8( i8 %x, i1 true )
   ret i8 %tmp
 }
 
 define i16 @cttz_i16(i16 %x)  {
 ; X86-LABEL: cttz_i16:
 ; X86:       # %bb.0:
-; X86-NEXT:    bsfl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    rep bsfl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: cttz_i16:
 ; X64:       # %bb.0:
-; X64-NEXT:    bsfl %edi, %eax
+; X64-NEXT:    rep bsfl %edi, %eax
 ; X64-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X64-NEXT:    retq
 ;
 ; X86-CLZ-LABEL: cttz_i16:
 ; X86-CLZ:       # %bb.0:
 ; X86-CLZ-NEXT:    tzcntl {{[0-9]+}}(%esp), %eax
 ; X86-CLZ-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X86-CLZ-NEXT:    retl
 ;
 ; X64-CLZ-LABEL: cttz_i16:
 ; X64-CLZ:       # %bb.0:
 ; X64-CLZ-NEXT:    tzcntl %edi, %eax
 ; X64-CLZ-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X64-CLZ-NEXT:    retq
   %tmp = call i16 @llvm.cttz.i16( i16 %x, i1 true )
   ret i16 %tmp
 }
 
 define i32 @cttz_i32(i32 %x)  {
 ; X86-LABEL: cttz_i32:
 ; X86:       # %bb.0:
-; X86-NEXT:    bsfl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    rep bsfl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: cttz_i32:
 ; X64:       # %bb.0:
-; X64-NEXT:    bsfl %edi, %eax
+; X64-NEXT:    rep bsfl %edi, %eax
 ; X64-NEXT:    retq
 ;
 ; X86-CLZ-LABEL: cttz_i32:
 ; X86-CLZ:       # %bb.0:
 ; X86-CLZ-NEXT:    tzcntl {{[0-9]+}}(%esp), %eax
 ; X86-CLZ-NEXT:    retl
 ;
 ; X64-CLZ-LABEL: cttz_i32:
 ; X64-CLZ:       # %bb.0:
 ; X64-CLZ-NEXT:    tzcntl %edi, %eax
 ; X64-CLZ-NEXT:    retq
   %tmp = call i32 @llvm.cttz.i32( i32 %x, i1 true )
   ret i32 %tmp
 }
 
 define i64 @cttz_i64(i64 %x)  {
 ; X86-NOCMOV-LABEL: cttz_i64:
 ; X86-NOCMOV:       # %bb.0:
 ; X86-NOCMOV-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NOCMOV-NEXT:    testl %eax, %eax
 ; X86-NOCMOV-NEXT:    jne .LBB3_1
 ; X86-NOCMOV-NEXT:  # %bb.2:
-; X86-NOCMOV-NEXT:    bsfl {{[0-9]+}}(%esp), %eax
+; X86-NOCMOV-NEXT:    rep bsfl {{[0-9]+}}(%esp), %eax
 ; X86-NOCMOV-NEXT:    addl $32, %eax
 ; X86-NOCMOV-NEXT:    xorl %edx, %edx
 ; X86-NOCMOV-NEXT:    retl
 ; X86-NOCMOV-NEXT:  .LBB3_1:
-; X86-NOCMOV-NEXT:    bsfl %eax, %eax
+; X86-NOCMOV-NEXT:    rep bsfl %eax, %eax
 ; X86-NOCMOV-NEXT:    xorl %edx, %edx
 ; X86-NOCMOV-NEXT:    retl
 ;
 ; X86-CMOV-LABEL: cttz_i64:
 ; X86-CMOV:       # %bb.0:
 ; X86-CMOV-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-CMOV-NEXT:    bsfl %ecx, %edx
-; X86-CMOV-NEXT:    bsfl {{[0-9]+}}(%esp), %eax
+; X86-CMOV-NEXT:    rep bsfl %ecx, %edx
+; X86-CMOV-NEXT:    rep bsfl {{[0-9]+}}(%esp), %eax
 ; X86-CMOV-NEXT:    addl $32, %eax
 ; X86-CMOV-NEXT:    testl %ecx, %ecx
 ; X86-CMOV-NEXT:    cmovnel %edx, %eax
 ; X86-CMOV-NEXT:    xorl %edx, %edx
 ; X86-CMOV-NEXT:    retl
 ;
 ; X64-LABEL: cttz_i64:
 ; X64:       # %bb.0:
-; X64-NEXT:    bsfq %rdi, %rax
+; X64-NEXT:    rep bsfq %rdi, %rax
 ; X64-NEXT:    retq
 ;
 ; X86-CLZ-LABEL: cttz_i64:
 ; X86-CLZ:       # %bb.0:
 ; X86-CLZ-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-CLZ-NEXT:    testl %eax, %eax
 ; X86-CLZ-NEXT:    jne .LBB3_1
 ; X86-CLZ-NEXT:  # %bb.2:

 define i8 @cttz_i8_zero_test(i8 %n) {
 ; X86-LABEL: cttz_i8_zero_test:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movzbl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    testb %al, %al
 ; X86-NEXT:    je .LBB12_1
 ; X86-NEXT:  # %bb.2: # %cond.false
 ; X86-NEXT:    movzbl %al, %eax
-; X86-NEXT:    bsfl %eax, %eax
+; X86-NEXT:    rep bsfl %eax, %eax
 ; X86-NEXT:    # kill: def $al killed $al killed $eax
 ; X86-NEXT:    retl
 ; X86-NEXT:  .LBB12_1:
 ; X86-NEXT:    movb $8, %al
 ; X86-NEXT:    # kill: def $al killed $al killed $eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: cttz_i8_zero_test:
 ; X64:       # %bb.0:
 ; X64-NEXT:    testb %dil, %dil
 ; X64-NEXT:    je .LBB12_1
 ; X64-NEXT:  # %bb.2: # %cond.false
 ; X64-NEXT:    movzbl %dil, %eax
-; X64-NEXT:    bsfl %eax, %eax
+; X64-NEXT:    rep bsfl %eax, %eax
 ; X64-NEXT:    # kill: def $al killed $al killed $eax
 ; X64-NEXT:    retq
 ; X64-NEXT:  .LBB12_1:
 ; X64-NEXT:    movb $8, %al
 ; X64-NEXT:    # kill: def $al killed $al killed $eax
 ; X64-NEXT:    retq
 ;
 ; X86-CLZ-LABEL: cttz_i8_zero_test:

 ; Generate a test and branch to handle zero inputs because bsr/bsf are very slow.
 define i16 @cttz_i16_zero_test(i16 %n) {
 ; X86-LABEL: cttz_i16_zero_test:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movzwl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    testw %ax, %ax
 ; X86-NEXT:    je .LBB13_1
 ; X86-NEXT:  # %bb.2: # %cond.false
-; X86-NEXT:    bsfl %eax, %eax
+; X86-NEXT:    rep bsfl %eax, %eax
 ; X86-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X86-NEXT:    retl
 ; X86-NEXT:  .LBB13_1:
 ; X86-NEXT:    movw $16, %ax
 ; X86-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: cttz_i16_zero_test:
 ; X64:       # %bb.0:
 ; X64-NEXT:    testw %di, %di
 ; X64-NEXT:    je .LBB13_1
 ; X64-NEXT:  # %bb.2: # %cond.false
-; X64-NEXT:    bsfl %edi, %eax
+; X64-NEXT:    rep bsfl %edi, %eax
 ; X64-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X64-NEXT:    retq
 ; X64-NEXT:  .LBB13_1:
 ; X64-NEXT:    movw $16, %ax
 ; X64-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X64-NEXT:    retq
 ;
 ; X86-CLZ-LABEL: cttz_i16_zero_test:

 ; Generate a test and branch to handle zero inputs because bsr/bsf are very slow.
 define i32 @cttz_i32_zero_test(i32 %n) {
 ; X86-LABEL: cttz_i32_zero_test:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    testl %eax, %eax
 ; X86-NEXT:    je .LBB14_1
 ; X86-NEXT:  # %bb.2: # %cond.false
-; X86-NEXT:    bsfl %eax, %eax
+; X86-NEXT:    rep bsfl %eax, %eax
 ; X86-NEXT:    retl
 ; X86-NEXT:  .LBB14_1:
 ; X86-NEXT:    movl $32, %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: cttz_i32_zero_test:
 ; X64:       # %bb.0:
 ; X64-NEXT:    testl %edi, %edi
 ; X64-NEXT:    je .LBB14_1
 ; X64-NEXT:  # %bb.2: # %cond.false
-; X64-NEXT:    bsfl %edi, %eax
+; X64-NEXT:    rep bsfl %edi, %eax
 ; X64-NEXT:    retq
 ; X64-NEXT:  .LBB14_1:
 ; X64-NEXT:    movl $32, %eax
 ; X64-NEXT:    retq
 ;
 ; X86-CLZ-LABEL: cttz_i32_zero_test:
 ; X86-CLZ:       # %bb.0:
 ; X86-CLZ-NEXT:    tzcntl {{[0-9]+}}(%esp), %eax
 ; X86-CLZ-NEXT:    retl
 ;
 ; X64-CLZ-LABEL: cttz_i32_zero_test:
 ; X64-CLZ:       # %bb.0:
 ; X64-CLZ-NEXT:    tzcntl %edi, %eax
 ; X64-CLZ-NEXT:    retq
   %tmp1 = call i32 @llvm.cttz.i32(i32 %n, i1 false)
   ret i32 %tmp1
 }
 
 ; Generate a test and branch to handle zero inputs because bsr/bsf are very slow.
 define i64 @cttz_i64_zero_test(i64 %n) {
 ; X86-NOCMOV-LABEL: cttz_i64_zero_test:
 ; X86-NOCMOV:       # %bb.0:
 ; X86-NOCMOV-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NOCMOV-NOT:     rep
 ; X86-NOCMOV-NEXT:    bsfl {{[0-9]+}}(%esp), %edx
 ; X86-NOCMOV-NEXT:    movl $32, %eax
 ; X86-NOCMOV-NEXT:    je .LBB15_2
 ; X86-NOCMOV-NEXT:  # %bb.1:
 ; X86-NOCMOV-NEXT:    movl %edx, %eax
 ; X86-NOCMOV-NEXT:  .LBB15_2:
 ; X86-NOCMOV-NEXT:    testl %ecx, %ecx
 ; X86-NOCMOV-NEXT:    jne .LBB15_3
 ; X86-NOCMOV-NEXT:  # %bb.4:
 ; X86-NOCMOV-NEXT:    addl $32, %eax
 ; X86-NOCMOV-NEXT:    xorl %edx, %edx
 ; X86-NOCMOV-NEXT:    retl
 ; X86-NOCMOV-NEXT:  .LBB15_3:
-; X86-NOCMOV-NEXT:    bsfl %ecx, %eax
+; X86-NOCMOV-NEXT:    rep bsfl %ecx, %eax
 ; X86-NOCMOV-NEXT:    xorl %edx, %edx
 ; X86-NOCMOV-NEXT:    retl
 ;
 ; X86-CMOV-LABEL: cttz_i64_zero_test:
 ; X86-CMOV:       # %bb.0:
 ; X86-CMOV-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-CMOV-NOT:     rep
 ; X86-CMOV-NEXT:    bsfl {{[0-9]+}}(%esp), %ecx
 ; X86-CMOV-NEXT:    movl $32, %edx
 ; X86-CMOV-NEXT:    cmovnel %ecx, %edx
 ; X86-CMOV-NEXT:    addl $32, %edx
+; X86-CMOV-NOT:     rep
 ; X86-CMOV-NEXT:    bsfl %eax, %eax
 ; X86-CMOV-NEXT:    cmovel %edx, %eax
 ; X86-CMOV-NEXT:    xorl %edx, %edx
 ; X86-CMOV-NEXT:    retl
 ;
 ; X64-LABEL: cttz_i64_zero_test:
 ; X64:       # %bb.0:
 ; X64-NEXT:    testq %rdi, %rdi
 ; X64-NEXT:    je .LBB15_1
 ; X64-NEXT:  # %bb.2: # %cond.false
-; X64-NEXT:    bsfq %rdi, %rax
+; X64-NEXT:    rep bsfq %rdi, %rax
 ; X64-NEXT:    retq
 ; X64-NEXT:  .LBB15_1:
 ; X64-NEXT:    movl $64, %eax
 ; X64-NEXT:    retq
 ;
 ; X86-CLZ-LABEL: cttz_i64_zero_test:
 ; X86-CLZ:       # %bb.0:
 ; X86-CLZ-NEXT:    movl {{[0-9]+}}(%esp), %eax

 }
 
 define i8 @cttz_i8_knownbits(i8 %x)  {
 ; X86-LABEL: cttz_i8_knownbits:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movzbl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    orb $2, %al
 ; X86-NEXT:    movzbl %al, %eax
-; X86-NEXT:    bsfl %eax, %eax
+; X86-NEXT:    rep bsfl %eax, %eax
 ; X86-NEXT:    # kill: def $al killed $al killed $eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: cttz_i8_knownbits:
 ; X64:       # %bb.0:
 ; X64-NEXT:    orb $2, %dil
 ; X64-NEXT:    movzbl %dil, %eax
-; X64-NEXT:    bsfl %eax, %eax
+; X64-NEXT:    rep bsfl %eax, %eax
 ; X64-NEXT:    # kill: def $al killed $al killed $eax
 ; X64-NEXT:    retq
 ;
 ; X86-CLZ-LABEL: cttz_i8_knownbits:
 ; X86-CLZ:       # %bb.0:
 ; X86-CLZ-NEXT:    movzbl {{[0-9]+}}(%esp), %eax
 ; X86-CLZ-NEXT:    orb $2, %al
 ; X86-CLZ-NEXT:    movzbl %al, %eax

 ; X86-NOCMOV-LABEL: cttz_i64_zero_test_knownneverzero:
 ; X86-NOCMOV:       # %bb.0:
 ; X86-NOCMOV-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NOCMOV-NEXT:    testl %eax, %eax
 ; X86-NOCMOV-NEXT:    jne .LBB22_1
 ; X86-NOCMOV-NEXT:  # %bb.2:
 ; X86-NOCMOV-NEXT:    movl $-2147483648, %eax # imm = 0x80000000
 ; X86-NOCMOV-NEXT:    orl {{[0-9]+}}(%esp), %eax
-; X86-NOCMOV-NEXT:    bsfl %eax, %eax
+; X86-NOCMOV-NEXT:    rep bsfl %eax, %eax
 ; X86-NOCMOV-NEXT:    orl $32, %eax
 ; X86-NOCMOV-NEXT:    xorl %edx, %edx
 ; X86-NOCMOV-NEXT:    retl
 ; X86-NOCMOV-NEXT:  .LBB22_1:
-; X86-NOCMOV-NEXT:    bsfl %eax, %eax
+; X86-NOCMOV-NEXT:    rep bsfl %eax, %eax
 ; X86-NOCMOV-NEXT:    xorl %edx, %edx
 ; X86-NOCMOV-NEXT:    retl
 ;
 ; X86-CMOV-LABEL: cttz_i64_zero_test_knownneverzero:
 ; X86-CMOV:       # %bb.0:
 ; X86-CMOV-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; X86-CMOV-NEXT:    movl $-2147483648, %eax # imm = 0x80000000
 ; X86-CMOV-NEXT:    orl {{[0-9]+}}(%esp), %eax
-; X86-CMOV-NEXT:    bsfl %ecx, %edx
-; X86-CMOV-NEXT:    bsfl %eax, %eax
+; X86-CMOV-NEXT:    rep bsfl %ecx, %edx
+; X86-CMOV-NEXT:    rep bsfl %eax, %eax
 ; X86-CMOV-NEXT:    orl $32, %eax
 ; X86-CMOV-NEXT:    testl %ecx, %ecx
 ; X86-CMOV-NEXT:    cmovnel %edx, %eax
 ; X86-CMOV-NEXT:    xorl %edx, %edx
 ; X86-CMOV-NEXT:    retl
 ;
 ; X64-LABEL: cttz_i64_zero_test_knownneverzero:
 ; X64:       # %bb.0:
 ; X64-NEXT:    movabsq $-9223372036854775808, %rax # imm = 0x8000000000000000
 ; X64-NEXT:    orq %rdi, %rax
-; X64-NEXT:    bsfq %rax, %rax
+; X64-NEXT:    rep bsfq %rax, %rax
 ; X64-NEXT:    retq
 ;
 ; X86-CLZ-LABEL: cttz_i64_zero_test_knownneverzero:
 ; X86-CLZ:       # %bb.0:
 ; X86-CLZ-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-CLZ-NEXT:    testl %eax, %eax
 ; X86-CLZ-NEXT:    jne .LBB22_1
 ; X86-CLZ-NEXT:  # %bb.2:
; X64-CLZ-NEXT:    retq
   %ctlz = tail call i32 @llvm.ctlz.i32(i32 %a0, i1 true)
   %xor = xor i32 %ctlz, 31
   %zext = zext i32 %xor to i64
   %gep = getelementptr inbounds [32 x i8], ptr %a1, i64 0, i64 %zext
   %load = load i8, ptr %gep, align 1
   %sext = sext i8 %load to i32
   ret i32 %sext
 }
+
+define i32 @cttz_i32_osize(i32 %x) optsize {
+; X86-LABEL: cttz_i32_osize:
+; X86:       # %bb.0:
+; X86-NOT:     rep
+; X86-NEXT:    bsfl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    retl
+;
+; X64-LABEL: cttz_i32_osize:
+; X64:       # %bb.0:
+; X64-NOT:     rep
+; X64-NEXT:    bsfl %edi, %eax
+; X64-NEXT:    retq
+;
+; X86-CLZ-LABEL: cttz_i32_osize:
+; X86-CLZ:       # %bb.0:
+; X86-CLZ-NEXT:    tzcntl {{[0-9]+}}(%esp), %eax
+; X86-CLZ-NEXT:    retl
+;
+; X64-CLZ-LABEL: cttz_i32_osize:
+; X64-CLZ:       # %bb.0:
+; X64-CLZ-NEXT:    tzcntl %edi, %eax
+; X64-CLZ-NEXT:    retq
+  %tmp = call i32 @llvm.cttz.i32( i32 %x, i1 true)
+  ret i32 %tmp
+}
+
+define i32 @cttz_i32_msize(i32 %x) minsize {
+; X86-LABEL: cttz_i32_msize:
+; X86:       # %bb.0:
+; X86-NOT:     rep
+; X86-NEXT:    bsfl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    retl
+;
+; X64-LABEL: cttz_i32_msize:
+; X64:       # %bb.0:
+; X64-NOT:     rep
+; X64-NEXT:    bsfl %edi, %eax
+; X64-NEXT:    retq
+;
+; X86-CLZ-LABEL: cttz_i32_msize:
+; X86-CLZ:       # %bb.0:
+; X86-CLZ-NEXT:    tzcntl {{[0-9]+}}(%esp), %eax
+; X86-CLZ-NEXT:    retl
+;
+; X64-CLZ-LABEL: cttz_i32_msize:
+; X64-CLZ:       # %bb.0:
+; X64-CLZ-NEXT:    tzcntl %edi, %eax
+; X64-CLZ-NEXT:    retq
+  %tmp = call i32 @llvm.cttz.i32( i32 %x, i1 true)
+  ret i32 %tmp
+}

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

 define i1 @asm_clobbering_flags(ptr %mem) nounwind {
 ; CHECK32-LABEL: asm_clobbering_flags:
 ; CHECK32:       # %bb.0: # %entry
 ; CHECK32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; CHECK32-NEXT:    movl (%ecx), %edx
 ; CHECK32-NEXT:    testl %edx, %edx
 ; CHECK32-NEXT:    setg %al
 ; CHECK32-NEXT:    #APP
+; CHECK32-NOT:     rep
 ; CHECK32-NEXT:    bsfl %edx, %edx
 ; CHECK32-NEXT:    #NO_APP
 ; CHECK32-NEXT:    movl %edx, (%ecx)
 ; CHECK32-NEXT:    retl
 ;
 ; CHECK64-LABEL: asm_clobbering_flags:
 ; CHECK64:       # %bb.0: # %entry
 ; CHECK64-NEXT:    movl (%rdi), %ecx
 ; CHECK64-NEXT:    testl %ecx, %ecx
 ; CHECK64-NEXT:    setg %al
 ; CHECK64-NEXT:    #APP
+; CHECK64-NOT:     rep
 ; CHECK64-NEXT:    bsfl %ecx, %ecx
 ; CHECK64-NEXT:    #NO_APP
 ; CHECK64-NEXT:    movl %ecx, (%rdi)
 ; CHECK64-NEXT:    retq
 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)
   store i32 %res, ptr %mem, align 4
   ret i1 %cmp
 }

llvm/test/CodeGen/X86/stack-folding-x86_64.ll

 ; CHECK-NEXT:    .cfi_offset %r13, -40
 ; CHECK-NEXT:    .cfi_offset %r14, -32
 ; CHECK-NEXT:    .cfi_offset %r15, -24
 ; CHECK-NEXT:    .cfi_offset %rbp, -16
 ; CHECK-NEXT:    movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
 ; CHECK-NEXT:    #APP
 ; CHECK-NEXT:    nop
 ; CHECK-NEXT:    #NO_APP
-; CHECK-NEXT:    bsfl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Folded Reload
+; CHECK-NEXT:    rep bsfl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Folded Reload
 ; CHECK-NEXT:    popq %rbx
 ; CHECK-NEXT:    .cfi_def_cfa_offset 48
 ; CHECK-NEXT:    popq %r12
 ; CHECK-NEXT:    .cfi_def_cfa_offset 40
 ; CHECK-NEXT:    popq %r13
 ; CHECK-NEXT:    .cfi_def_cfa_offset 32
 ; CHECK-NEXT:    popq %r14
 ; CHECK-NEXT:    .cfi_def_cfa_offset 24

 ; CHECK-NEXT:    .cfi_offset %r13, -40
 ; CHECK-NEXT:    .cfi_offset %r14, -32
 ; CHECK-NEXT:    .cfi_offset %r15, -24
 ; CHECK-NEXT:    .cfi_offset %rbp, -16
 ; CHECK-NEXT:    movq %rdi, {{[-0-9]+}}(%r{{[sb]}}p) # 8-byte Spill
 ; CHECK-NEXT:    #APP
 ; CHECK-NEXT:    nop
 ; CHECK-NEXT:    #NO_APP
-; CHECK-NEXT:    bsfq {{[-0-9]+}}(%r{{[sb]}}p), %rax # 8-byte Folded Reload
+; CHECK-NEXT:    rep bsfq {{[-0-9]+}}(%r{{[sb]}}p), %rax # 8-byte Folded Reload
 ; CHECK-NEXT:    popq %rbx
 ; CHECK-NEXT:    .cfi_def_cfa_offset 48
 ; CHECK-NEXT:    popq %r12
 ; CHECK-NEXT:    .cfi_def_cfa_offset 40
 ; CHECK-NEXT:    popq %r13
 ; CHECK-NEXT:    .cfi_def_cfa_offset 32
 ; CHECK-NEXT:    popq %r14
 ; CHECK-NEXT:    .cfi_def_cfa_offset 24