[X86] For lzcnt/tzcnt intrinsics use cttz/ctlz intrinsics with zero_undef flag set to false.

[craig.topper]

Summary

Previously we used a select and the zero_undef=true intrinsic. In -O2 this pattern will get optimized to zero_undef=false. But in -O0 this optimization won't happen. This results in a compare and cmov being wrapped around a tzcnt/lzcnt instruction.

By using the zero_undef=false intrinsic directly without the select, we can improve the -O0 codegen to just an lzcnt/tzcnt instruction.

[RKSimon]

Are there other targets that would benefit from this and if so should we provide a more generic intrinsic?

[craig.topper]

The only other header that uses the existing builtins is arm_acle.h. But
ARM returns false in isCLZForZeroUndef. So they should be creating the
cttz/ctlz intrinsics with false for the second argument from
__builtin_clz/ctz. The sanitizer code
in CodeGenFunction::EmitCheckedArgForBuiltin also checks isCLZForZeroUndef
to determine if it should emit a runtime check to flag 0 as a sanitizer
error.

~Craig

[RKSimon]

LGTM, thanks for checking.

Please update the *-intrinsics-fast-isel.ll llvm test cases to match the *-builtins.c changes.

include/clang/Basic/BuiltinsX86.def

 TARGET_BUILTIN(__builtin_ia32_addcarryx_u32, "UcUcUiUiUi*", "n", "adx")
 TARGET_BUILTIN(__builtin_ia32_addcarry_u32, "UcUcUiUiUi*", "n", "")
 TARGET_BUILTIN(__builtin_ia32_subborrow_u32, "UcUcUiUiUi*", "n", "")
 
 // RDSEED
 TARGET_BUILTIN(__builtin_ia32_rdseed16_step, "UiUs*", "n", "rdseed")
 TARGET_BUILTIN(__builtin_ia32_rdseed32_step, "UiUi*", "n", "rdseed")
 
+// LZCNT
+TARGET_BUILTIN(__builtin_ia32_lzcnt_u16, "UsUs", "nc", "lzcnt")
+TARGET_BUILTIN(__builtin_ia32_lzcnt_u32, "UiUi", "nc", "lzcnt")
+
 // BMI
 TARGET_BUILTIN(__builtin_ia32_bextr_u32, "UiUiUi", "nc", "bmi")
+TARGET_BUILTIN(__builtin_ia32_tzcnt_u16, "UsUs", "nc", "")
+TARGET_BUILTIN(__builtin_ia32_tzcnt_u32, "UiUi", "nc", "")
 
 // BMI2
 TARGET_BUILTIN(__builtin_ia32_bzhi_si, "UiUiUi", "nc", "bmi2")
 TARGET_BUILTIN(__builtin_ia32_pdep_si, "UiUiUi", "nc", "bmi2")
 TARGET_BUILTIN(__builtin_ia32_pext_si, "UiUiUi", "nc", "bmi2")
 
 // TBM
 TARGET_BUILTIN(__builtin_ia32_bextri_u32, "UiUiIUi", "nc", "tbm")

include/clang/Basic/BuiltinsX86_64.def

 TARGET_BUILTIN(__builtin_ia32_rdsspq, "ULLiULLi", "n", "shstk")
 TARGET_BUILTIN(__builtin_ia32_wrssq, "vULLiv*", "n", "shstk")
 TARGET_BUILTIN(__builtin_ia32_wrussq, "vULLiv*", "n", "shstk")
 TARGET_BUILTIN(__builtin_ia32_addcarryx_u64, "UcUcULLiULLiULLi*", "n", "adx")
 TARGET_BUILTIN(__builtin_ia32_addcarry_u64, "UcUcULLiULLiULLi*", "n", "")
 TARGET_BUILTIN(__builtin_ia32_subborrow_u64, "UcUcULLiULLiULLi*", "n", "")
 TARGET_BUILTIN(__builtin_ia32_rdrand64_step, "UiULLi*", "n", "rdrnd")
 TARGET_BUILTIN(__builtin_ia32_rdseed64_step, "UiULLi*", "n", "rdseed")
+TARGET_BUILTIN(__builtin_ia32_lzcnt_u64, "ULLiULLi", "nc", "lzcnt")
 TARGET_BUILTIN(__builtin_ia32_bextr_u64, "ULLiULLiULLi", "nc", "bmi")
+TARGET_BUILTIN(__builtin_ia32_tzcnt_u64, "ULLiULLi", "nc", "")
 TARGET_BUILTIN(__builtin_ia32_bzhi_di, "ULLiULLiULLi", "nc", "bmi2")
 TARGET_BUILTIN(__builtin_ia32_pdep_di, "ULLiULLiULLi", "nc", "bmi2")
 TARGET_BUILTIN(__builtin_ia32_pext_di, "ULLiULLiULLi", "nc", "bmi2")
 TARGET_BUILTIN(__builtin_ia32_bextri_u64, "ULLiULLiIULLi", "nc", "tbm")
 TARGET_BUILTIN(__builtin_ia32_lwpins64, "UcULLiUiUi", "n", "lwp")
 TARGET_BUILTIN(__builtin_ia32_lwpval64, "vULLiUiUi", "n", "lwp")
 TARGET_BUILTIN(__builtin_ia32_vcvtsd2si64, "LLiV2dIi", "ncV:128:", "avx512f")
 TARGET_BUILTIN(__builtin_ia32_vcvtsd2usi64, "ULLiV2dIi", "ncV:128:", "avx512f")

lib/CodeGen/CGBuiltin.cpp

case X86::BI__rdtsc: {
     return Builder.CreateCall(CGM.getIntrinsic(Intrinsic::x86_rdtsc));
   }
   case X86::BI__builtin_ia32_rdtscp: {
     Value *Call = Builder.CreateCall(CGM.getIntrinsic(Intrinsic::x86_rdtscp));
     Builder.CreateDefaultAlignedStore(Builder.CreateExtractValue(Call, 1),
                                       Ops[0]);
     return Builder.CreateExtractValue(Call, 0);
   }
+  case X86::BI__builtin_ia32_lzcnt_u16:
+  case X86::BI__builtin_ia32_lzcnt_u32:
+  case X86::BI__builtin_ia32_lzcnt_u64: {
+    Value *F = CGM.getIntrinsic(Intrinsic::ctlz, Ops[0]->getType());
+    return Builder.CreateCall(F, {Ops[0], Builder.getInt1(false)});
+  }
+  case X86::BI__builtin_ia32_tzcnt_u16:
+  case X86::BI__builtin_ia32_tzcnt_u32:
+  case X86::BI__builtin_ia32_tzcnt_u64: {
+    Value *F = CGM.getIntrinsic(Intrinsic::cttz, Ops[0]->getType());
+    return Builder.CreateCall(F, {Ops[0], Builder.getInt1(false)});
+  }
   case X86::BI__builtin_ia32_undef128:
   case X86::BI__builtin_ia32_undef256:
   case X86::BI__builtin_ia32_undef512:
     // The x86 definition of "undef" is not the same as the LLVM definition
     // (PR32176). We leave optimizing away an unnecessary zero constant to the
     // IR optimizer and backend.
     // TODO: If we had a "freeze" IR instruction to generate a fixed undef
     // value, we should use that here instead of a zero.

lib/Headers/bmiintrin.h

 ///
 /// \param __X
 ///    An unsigned 16-bit integer whose trailing zeros are to be counted.
 /// \returns An unsigned 16-bit integer containing the number of trailing zero
 ///    bits in the operand.
 static __inline__ unsigned short __RELAXED_FN_ATTRS
 __tzcnt_u16(unsigned short __X)
 {
-  return __X ? __builtin_ctzs(__X) : 16;
+  return __builtin_ia32_tzcnt_u16(__X);
 }
 
 /// Performs a bitwise AND of the second operand with the one's
 ///    complement of the first operand.
 ///
 /// \headerfile <x86intrin.h>
 ///
 /// This intrinsic corresponds to the <c> ANDN </c> instruction.

 ///
 /// \param __X
 ///    An unsigned 32-bit integer whose trailing zeros are to be counted.
 /// \returns An unsigned 32-bit integer containing the number of trailing zero
 ///    bits in the operand.
 static __inline__ unsigned int __RELAXED_FN_ATTRS
 __tzcnt_u32(unsigned int __X)
 {
-  return __X ? __builtin_ctz(__X) : 32;
+  return __builtin_ia32_tzcnt_u32(__X);
 }
 
 /// Counts the number of trailing zero bits in the operand.
 ///
 /// \headerfile <x86intrin.h>
 ///
 /// This intrinsic corresponds to the <c> TZCNT </c> instruction.
 ///
 /// \param __X
 ///    An unsigned 32-bit integer whose trailing zeros are to be counted.
 /// \returns An 32-bit integer containing the number of trailing zero bits in
 ///    the operand.
 static __inline__ int __RELAXED_FN_ATTRS
 _mm_tzcnt_32(unsigned int __X)
 {
-  return __X ? __builtin_ctz(__X) : 32;
+  return __builtin_ia32_tzcnt_u32(__X);
 }
 
 #ifdef __x86_64__
 
 #define _andn_u64(a, b)   (__andn_u64((a), (b)))
 
 /* _bextr_u64 != __bextr_u64 */
 #define _blsi_u64(a)      (__blsi_u64((a)))

 ///
 /// \param __X
 ///    An unsigned 64-bit integer whose trailing zeros are to be counted.
 /// \returns An unsigned 64-bit integer containing the number of trailing zero
 ///    bits in the operand.
 static __inline__ unsigned long long __RELAXED_FN_ATTRS
 __tzcnt_u64(unsigned long long __X)
 {
-  return __X ? __builtin_ctzll(__X) : 64;
+  return __builtin_ia32_tzcnt_u64(__X);
 }
 
 /// Counts the number of trailing zero bits in the operand.
 ///
 /// \headerfile <x86intrin.h>
 ///
 /// This intrinsic corresponds to the <c> TZCNT </c> instruction.
 ///
 /// \param __X
 ///    An unsigned 64-bit integer whose trailing zeros are to be counted.
 /// \returns An 64-bit integer containing the number of trailing zero bits in
 ///    the operand.
 static __inline__ long long __RELAXED_FN_ATTRS
 _mm_tzcnt_64(unsigned long long __X)
 {
-  return __X ? __builtin_ctzll(__X) : 64;
+  return __builtin_ia32_tzcnt_u64(__X);
 }
 
 #endif /* __x86_64__ */
 
 #undef __DEFAULT_FN_ATTRS
 #undef __RELAXED_FN_ATTRS
 
 #endif /* __BMIINTRIN_H */

lib/Headers/lzcntintrin.h

 ///
 /// \param __X
 ///    An unsigned 16-bit integer whose leading zeros are to be counted.
 /// \returns An unsigned 16-bit integer containing the number of leading zero
 ///    bits in the operand.
 static __inline__ unsigned short __DEFAULT_FN_ATTRS
 __lzcnt16(unsigned short __X)
 {
-  return __X ? __builtin_clzs(__X) : 16;
+  return __builtin_ia32_lzcnt_u16(__X);
 }
 
 /// Counts the number of leading zero bits in the operand.
 ///
 /// \headerfile <x86intrin.h>
 ///
 /// This intrinsic corresponds to the \c LZCNT instruction.
 ///
 /// \param __X
 ///    An unsigned 32-bit integer whose leading zeros are to be counted.
 /// \returns An unsigned 32-bit integer containing the number of leading zero
 ///    bits in the operand.
 /// \see _lzcnt_u32
 static __inline__ unsigned int __DEFAULT_FN_ATTRS
 __lzcnt32(unsigned int __X)
 {
-  return __X ? __builtin_clz(__X) : 32;
+  return __builtin_ia32_lzcnt_u32(__X);
 }
 
 /// Counts the number of leading zero bits in the operand.
 ///
 /// \headerfile <x86intrin.h>
 ///
 /// This intrinsic corresponds to the \c LZCNT instruction.
 ///
 /// \param __X
 ///    An unsigned 32-bit integer whose leading zeros are to be counted.
 /// \returns An unsigned 32-bit integer containing the number of leading zero
 ///    bits in the operand.
 /// \see __lzcnt32
 static __inline__ unsigned int __DEFAULT_FN_ATTRS
 _lzcnt_u32(unsigned int __X)
 {
-  return __X ? __builtin_clz(__X) : 32;
+  return __builtin_ia32_lzcnt_u32(__X);
 }
 
 #ifdef __x86_64__
 /// Counts the number of leading zero bits in the operand.
 ///
 /// \headerfile <x86intrin.h>
 ///
 /// This intrinsic corresponds to the \c LZCNT instruction.
 ///
 /// \param __X
 ///    An unsigned 64-bit integer whose leading zeros are to be counted.
 /// \returns An unsigned 64-bit integer containing the number of leading zero
 ///    bits in the operand.
 /// \see _lzcnt_u64
 static __inline__ unsigned long long __DEFAULT_FN_ATTRS
 __lzcnt64(unsigned long long __X)
 {
-  return __X ? __builtin_clzll(__X) : 64;
+  return __builtin_ia32_lzcnt_u64(__X);
 }
 
 /// Counts the number of leading zero bits in the operand.
 ///
 /// \headerfile <x86intrin.h>
 ///
 /// This intrinsic corresponds to the \c LZCNT instruction.
 ///
 /// \param __X
 ///    An unsigned 64-bit integer whose leading zeros are to be counted.
 /// \returns An unsigned 64-bit integer containing the number of leading zero
 ///    bits in the operand.
 /// \see __lzcnt64
 static __inline__ unsigned long long __DEFAULT_FN_ATTRS
 _lzcnt_u64(unsigned long long __X)
 {
-  return __X ? __builtin_clzll(__X) : 64;
+  return __builtin_ia32_lzcnt_u64(__X);
 }
 #endif
 
 #undef __DEFAULT_FN_ATTRS
 
 #endif /* __LZCNTINTRIN_H */

test/CodeGen/bmi-builtins.c

 // are for compatibility with Intel's BMI interface.
 // Apart from the underscores, the interfaces are identical
 // except in one case: although the 'bextr' register-form
 // instruction is identical in hardware, the AMD and Intel
 // intrinsics are different!
 
 unsigned short test__tzcnt_u16(unsigned short __X) {
   // CHECK-LABEL: test__tzcnt_u16
-  // CHECK: zext i16 %{{.*}} to i32
-  // CHECK: icmp ne i32 %{{.*}}, 0
-  // CHECK: i16 @llvm.cttz.i16(i16 %{{.*}}, i1 true)
+  // CHECK: i16 @llvm.cttz.i16(i16 %{{.*}}, i1 false)
   return __tzcnt_u16(__X);
 }
 
 unsigned int test__andn_u32(unsigned int __X, unsigned int __Y) {
   // CHECK-LABEL: test__andn_u32
   // CHECK: xor i32 %{{.*}}, -1
   // CHECK: and i32 %{{.*}}, %{{.*}}
   return __andn_u32(__X, __Y);
unsigned int test__blsr_u32(unsigned int __X) {
   // CHECK-LABEL: test__blsr_u32
   // CHECK: sub i32 %{{.*}}, 1
   // CHECK: and i32 %{{.*}}, %{{.*}}
   return __blsr_u32(__X);
 }
 
 unsigned int test__tzcnt_u32(unsigned int __X) {
   // CHECK-LABEL: test__tzcnt_u32
-  // CHECK: icmp ne i32 %{{.*}}, 0
-  // CHECK: i32 @llvm.cttz.i32(i32 %{{.*}}, i1 true)
+  // CHECK: i32 @llvm.cttz.i32(i32 %{{.*}}, i1 false)
   return __tzcnt_u32(__X);
 }
 
 int test_mm_tzcnt_32(unsigned int __X) {
   // CHECK-LABEL: test_mm_tzcnt_32
-  // CHECK: icmp ne i32 %{{.*}}, 0
-  // CHECK: i32 @llvm.cttz.i32(i32 %{{.*}}, i1 true)
+  // CHECK: i32 @llvm.cttz.i32(i32 %{{.*}}, i1 false)
   return _mm_tzcnt_32(__X);
 }
 
 unsigned long long test__andn_u64(unsigned long __X, unsigned long __Y) {
   // CHECK-LABEL: test__andn_u64
   // CHECK: xor i64 %{{.*}}, -1
   // CHECK: and i64 %{{.*}}, %{{.*}}
   return __andn_u64(__X, __Y);
unsigned long long test__blsr_u64(unsigned long long __X) {
   // CHECK-LABEL: test__blsr_u64
   // CHECK: sub i64 %{{.*}}, 1
   // CHECK: and i64 %{{.*}}, %{{.*}}
   return __blsr_u64(__X);
 }
 
 unsigned long long test__tzcnt_u64(unsigned long long __X) {
   // CHECK-LABEL: test__tzcnt_u64
-  // CHECK: icmp ne i64 %{{.*}}, 0
-  // CHECK: i64 @llvm.cttz.i64(i64 %{{.*}}, i1 true)
+  // CHECK: i64 @llvm.cttz.i64(i64 %{{.*}}, i1 false)
   return __tzcnt_u64(__X);
 }
 
 long long test_mm_tzcnt_64(unsigned long long __X) {
   // CHECK-LABEL: test_mm_tzcnt_64
-  // CHECK: icmp ne i64 %{{.*}}, 0
-  // CHECK: i64 @llvm.cttz.i64(i64 %{{.*}}, i1 true)
+  // CHECK: i64 @llvm.cttz.i64(i64 %{{.*}}, i1 false)
   return _mm_tzcnt_64(__X);
 }
 
 // Intel intrinsics
 
 unsigned short test_tzcnt_u16(unsigned short __X) {
   // CHECK-LABEL: test_tzcnt_u16
-  // CHECK: zext i16 %{{.*}} to i32
-  // CHECK: icmp ne i32 %{{.*}}, 0
-  // CHECK: i16 @llvm.cttz.i16(i16 %{{.*}}, i1 true)
+  // CHECK: i16 @llvm.cttz.i16(i16 %{{.*}}, i1 false)
   return _tzcnt_u16(__X);
 }
 
 unsigned int test_andn_u32(unsigned int __X, unsigned int __Y) {
   // CHECK-LABEL: test_andn_u32
   // CHECK: xor i32 %{{.*}}, -1
   // CHECK: and i32 %{{.*}}, %{{.*}}
   return _andn_u32(__X, __Y);
unsigned int test_blsr_u32(unsigned int __X) {
   // CHECK-LABEL: test_blsr_u32
   // CHECK: sub i32 %{{.*}}, 1
   // CHECK: and i32 %{{.*}}, %{{.*}}
   return _blsr_u32(__X);
 }
 
 unsigned int test_tzcnt_u32(unsigned int __X) {
   // CHECK-LABEL: test_tzcnt_u32
-  // CHECK: icmp ne i32 %{{.*}}, 0
-  // CHECK: i32 @llvm.cttz.i32(i32 %{{.*}}, i1 true)
+  // CHECK: i32 @llvm.cttz.i32(i32 %{{.*}}, i1 false)
   return _tzcnt_u32(__X);
 }
 
 unsigned long long test_andn_u64(unsigned long __X, unsigned long __Y) {
   // CHECK-LABEL: test_andn_u64
   // CHECK: xor i64 %{{.*}}, -1
   // CHECK: and i64 %{{.*}}, %{{.*}}
   return _andn_u64(__X, __Y);
unsigned long long test_blsr_u64(unsigned long long __X) {
   // CHECK-LABEL: test_blsr_u64
   // CHECK: sub i64 %{{.*}}, 1
   // CHECK: and i64 %{{.*}}, %{{.*}}
   return _blsr_u64(__X);
 }
 
 unsigned long long test_tzcnt_u64(unsigned long long __X) {
   // CHECK-LABEL: test_tzcnt_u64
-  // CHECK: icmp ne i64 %{{.*}}, 0
-  // CHECK: i64 @llvm.cttz.i64(i64 %{{.*}}, i1 true)
+  // CHECK: i64 @llvm.cttz.i64(i64 %{{.*}}, i1 false)
   return _tzcnt_u64(__X);
 }

test/CodeGen/lzcnt-builtins.c

 // RUN: %clang_cc1 -ffreestanding %s -triple=x86_64-apple-darwin -target-feature +lzcnt -emit-llvm -o - | FileCheck %s
 
 
 #include <immintrin.h>
 
 unsigned short test__lzcnt16(unsigned short __X)
 {
-  // CHECK: @llvm.ctlz.i16
+  // CHECK: @llvm.ctlz.i16(i16 %{{.*}}, i1 false)
   return __lzcnt16(__X);
 }
 
 unsigned int test_lzcnt32(unsigned int __X)
 {
-  // CHECK: @llvm.ctlz.i32
+  // CHECK: @llvm.ctlz.i32(i32 %{{.*}}, i1 false)
   return __lzcnt32(__X);
 }
 
 unsigned long long test__lzcnt64(unsigned long long __X)
 {
-  // CHECK: @llvm.ctlz.i64
+  // CHECK: @llvm.ctlz.i64(i64 %{{.*}}, i1 false)
   return __lzcnt64(__X);
 }
 
 unsigned int test_lzcnt_u32(unsigned int __X)
 {
-  // CHECK: @llvm.ctlz.i32
+  // CHECK: @llvm.ctlz.i32(i32 %{{.*}}, i1 false)
   return _lzcnt_u32(__X);
 }
 
 unsigned long long test__lzcnt_u64(unsigned long long __X)
 {
-  // CHECK: @llvm.ctlz.i64
+  // CHECK: @llvm.ctlz.i64(i64 %{{.*}}, i1 false)
   return _lzcnt_u64(__X);
 }