diff --git a/llvm/lib/Target/X86/X86InstrInfo.td b/llvm/lib/Target/X86/X86InstrInfo.td
--- a/llvm/lib/Target/X86/X86InstrInfo.td
+++ b/llvm/lib/Target/X86/X86InstrInfo.td
@@ -1491,27 +1491,27 @@
 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}",
diff --git a/llvm/test/MC/X86/I386-32.s b/llvm/test/MC/X86/I386-32.s
--- a/llvm/test/MC/X86/I386-32.s
+++ b/llvm/test/MC/X86/I386-32.s
@@ -1,7 +1,7 @@
 // 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 
@@ -9,7 +9,7 @@
 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 
diff --git a/llvm/test/MC/X86/I386-64.s b/llvm/test/MC/X86/I386-64.s
--- a/llvm/test/MC/X86/I386-64.s
+++ b/llvm/test/MC/X86/I386-64.s
@@ -1,7 +1,7 @@
 // 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 
@@ -9,7 +9,7 @@
 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 
@@ -17,7 +17,7 @@
 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 
diff --git a/llvm/test/MC/X86/x86-32-coverage.s b/llvm/test/MC/X86/x86-32-coverage.s
--- a/llvm/test/MC/X86/x86-32-coverage.s
+++ b/llvm/test/MC/X86/x86-32-coverage.s
@@ -10023,11 +10023,11 @@
 
 // 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