Adding back-end support to two bit scanning intrinsics

[opaparo]

Summary

Adding LLVM back-end support to two intrinsics dealing with bit scan: _bit_scan_forward and _bit_scan_reverse.
Their functionality is as described in Intel intrinsics guide:
https://software.intel.com/sites/landingpage/IntrinsicsGuide/#text=_bit_scan_forward&expand=371,370
https://software.intel.com/sites/landingpage/IntrinsicsGuide/#text=_bit_scan_reverse&expand=371,370

[AsafBadouh]

test/CodeGen/X86/bitscan.ll

2

please change "-mcpu=core-avx-i -mattr=+rdrnd " to "-mcpu=corei7"

7

add CHECK-LABE

12

same

[m_zuckerman]

This comment has been deleted.

include/llvm/IR/IntrinsicsX86.td

8722

Add more one line

test/CodeGen/X86/bitscan.ll

2

Why you need -mcpu=core-avx-i?

18

Add more one line

[m_zuckerman]

include/llvm/IR/IntrinsicsX86.td

8716

convention: add _ia32

8719

convention: add _ia32

[RKSimon]

include/llvm/IR/IntrinsicsX86.td

8719

Why doesn't the patch include support for the 16 and 64 bit BSR/BSF instructions as well?

As Michael said, even if the 16 and 64 bit versions aren't included in this patch the intrinsic naming convention should include the type size for consistency if/when they are added added in the future.

[opaparo]

include/llvm/IR/IntrinsicsX86.td

8719

As my implementation follows Intel's Intrinsics guide, the only version of this form of BSR/BSF intrinsics, as specified in the guide, is the 32-bit version. There is another form of the BSR/BSF intrinsics, which has a 32-bit version as well as a 64-bit version, but this form is fully implemented as part of the front-end and has no back-end part.
As for the naming convention - the appropriate change was made.

[RKSimon]

Couple of minors

test/CodeGen/X86/bitscan.ll

2

Please can you test with a 32-bit triple as well?

12

Please run the file through the utils\update_llc_test_checks.py script to test the codegen more thoroughly.

[opaparo]

Added 32-bit test for the intrinsics

[RKSimon]

LGTM

[AsafBadouh]

LGTM

include/llvm/IR/IntrinsicsX86.td

let TargetPrefix = "x86" in {
   def int_x86_sha256rnds2 : GCCBuiltin<"__builtin_ia32_sha256rnds2">,
       Intrinsic<[llvm_v4i32_ty], [llvm_v4i32_ty, llvm_v4i32_ty, llvm_v4i32_ty],
                 [IntrNoMem]>;
   def int_x86_sha256msg1 : GCCBuiltin<"__builtin_ia32_sha256msg1">,
       Intrinsic<[llvm_v4i32_ty], [llvm_v4i32_ty, llvm_v4i32_ty], [IntrNoMem]>;
   def int_x86_sha256msg2 : GCCBuiltin<"__builtin_ia32_sha256msg2">,
       Intrinsic<[llvm_v4i32_ty], [llvm_v4i32_ty, llvm_v4i32_ty], [IntrNoMem]>;
 }
+
+//===----------------------------------------------------------------------===//
+// Bit Scan intrinsics
+let TargetPrefix = "x86" in {
+  def int_x86_bit_scan_forward : GCCBuiltin<"__builtin_ia32_bit_scan_forward">,
+      Intrinsic<[llvm_i32_ty], [llvm_i32_ty], [IntrNoMem]>;
+    
+  def int_x86_bit_scan_reverse : GCCBuiltin<"__builtin_ia32_bit_scan_reverse">,
+      Intrinsic<[llvm_i32_ty], [llvm_i32_ty], [IntrNoMem]>;
+}

lib/Target/X86/X86IntrinsicsInfo.h

   X86_INTRINSIC_DATA(avx512_vcvtss2si32, INTR_TYPE_2OP,
                      X86ISD::SCALAR_FP_TO_SINT_RND, 0),
   X86_INTRINSIC_DATA(avx512_vcvtss2si64, INTR_TYPE_2OP,
                      X86ISD::SCALAR_FP_TO_SINT_RND, 0),
   X86_INTRINSIC_DATA(avx512_vcvtss2usi32, INTR_TYPE_2OP,
                      X86ISD::SCALAR_FP_TO_UINT_RND, 0),
   X86_INTRINSIC_DATA(avx512_vcvtss2usi64, INTR_TYPE_2OP,
                      X86ISD::SCALAR_FP_TO_UINT_RND, 0),
+  X86_INTRINSIC_DATA(bit_scan_forward,  INTR_TYPE_1OP, X86ISD::BSF, 0),
+  X86_INTRINSIC_DATA(bit_scan_reverse,  INTR_TYPE_1OP, X86ISD::BSR, 0),
   X86_INTRINSIC_DATA(fma_vfmadd_pd,        INTR_TYPE_3OP, X86ISD::FMADD, 0),
   X86_INTRINSIC_DATA(fma_vfmadd_pd_256,    INTR_TYPE_3OP, X86ISD::FMADD, 0),
   X86_INTRINSIC_DATA(fma_vfmadd_ps,        INTR_TYPE_3OP, X86ISD::FMADD, 0),
   X86_INTRINSIC_DATA(fma_vfmadd_ps_256,    INTR_TYPE_3OP, X86ISD::FMADD, 0),
   X86_INTRINSIC_DATA(fma_vfmaddsub_pd,     INTR_TYPE_3OP, X86ISD::FMADDSUB, 0),
   X86_INTRINSIC_DATA(fma_vfmaddsub_pd_256, INTR_TYPE_3OP, X86ISD::FMADDSUB, 0),
   X86_INTRINSIC_DATA(fma_vfmaddsub_ps,     INTR_TYPE_3OP, X86ISD::FMADDSUB, 0),
   X86_INTRINSIC_DATA(fma_vfmaddsub_ps_256, INTR_TYPE_3OP, X86ISD::FMADDSUB, 0),

test/CodeGen/X86/bitscan.ll

+; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mcpu=corei7 | FileCheck %s
+declare i32 @llvm.x86.bit.scan.forward(i32 %val)
+declare i32 @llvm.x86.bit.scan.reverse(i32 %val)
+
+define i32 @test_bsf(i32 %val) {
+  %call = call i32 @llvm.x86.bit.scan.forward(i32 %val)
+  ret i32 %call
+; CHECK-LABEL: test_bsf
+; CHECK: bsfl    %edi, %eax
+}
+
+define i32 @test_bsr(i32 %val) {
+  %call = call i32 @llvm.x86.bit.scan.reverse(i32 %val)
+  ret i32 %call
+; CHECK-LABEL: test_bsr
+; CHECK: bsrl    %edi, %eax
+}