Implement MS _BitScan intrinsics

[agutowski]

Summary

_BitScan intrinsics (and some others, for example _Interlocked and _bittest) are supposed to work on both ARM and x86. This is an attempt to isolate them, avoiding repeating their code or writing separate function for each builtin.

[majnemer]

lib/CodeGen/CGBuiltin.cpp

2640–2647

This should be in an anonymous namespace. Also, consider using an enum class instead of an enum nested inside a namespace.

2656–2684

Does this do the right thing if the arg is zero? I think it would if you gave the call to the intrinsic an operand of false instead of true.

[agutowski]

lib/CodeGen/CGBuiltin.cpp

2656–2684

MSDN doesn't specify what should be put under the "Index" address when the argument is zero; as I checked, VS2015 with optimizations puts undefined value there, and I hope that's what I'm doing here.

[rnk]

Nice, probably ready to land with one revision.

lib/CodeGen/CGBuiltin.cpp

2640–2647

Let's also use a more specific name than MSVC, maybe MSVCIntrin or something.

[agutowski]

lib/CodeGen/CGBuiltin.cpp

2640–2647

I can see three options:
(1) put the existing code inside an anonymous namespace;
(2) create a private enum class in CodeGenFunction;
(3) pull EmitMSVCBuiltinExpr outside of CodeGenFunction and take CGF object as an argument (and then make enum class inside an anonymous namespace);
I don't really like any of them. Enum class sounds nice as I can imagine someone trying to pass the global builtin ID (like X86::BI_BitScanForward) instead of the one from MSVCIntrin namespace (although it should fail on any test; still, it would compile without enum class). But builtins use CGF methods all of the time, so pulling it out will make the code of every bulitin uglier. So I guess I'll try to go with the private enum class inside the CodeGenFunction, but if you have any better ideas, I'm eager to listen.

[agutowski]

change enum in MSVC namespace to enum class MSVCIntrin in CodeGenFunction; cover all control paths

[rnk]

lib/CodeGen/CodeGenFunction.h

2964

Does this work on Linux? I thought you had to give it an explicit underlying type (enum class MSVCIntrin : unsigned;) to make that work.

[agutowski]

lib/CodeGen/CodeGenFunction.h

2964

Yes, it seems to work on Linux too. According to the cppreference.com, it "declares a scoped enumeration type whose underlying type is int".

[majnemer]

lib/CodeGen/CGBuiltin.cpp

2656–2684

Intel (https://software.intel.com/en-us/node/523362) says the following:
Sets *p to the bit index of the least significant set bit of b or leaves it unchanged if b is zero. The function returns a non-zero result when b is non-zero and returns zero when b is zero.

This seems to mesh with this Mozilla bug report: https://bugzilla.mozilla.org/show_bug.cgi?id=1182370

[agutowski]

make _BitScan intrinsics compatible with Intel specification when the mask is zero

[agutowski]

lib/CodeGen/CGBuiltin.cpp

2665

Is this line needed? I took it from __builtin_fpclassify, but I don't know what could be its purpose (it's repeated below, where the "bitscan_end" block really starts).

[majnemer]

lib/CodeGen/CGBuiltin.cpp

2665

It's needed for the call to CreatePHI to be in the correct basic block.

[agutowski]

rebase

[majnemer]

This looks right to me.

include/clang/Basic/BuiltinsARM.def

 #   define LANGBUILTIN(ID, TYPE, ATTRS, BUILTIN_LANG) BUILTIN(ID, TYPE, ATTRS)
 #endif
 
+#if defined(BUILTIN) && !defined(TARGET_HEADER_BUILTIN)
+#  define TARGET_HEADER_BUILTIN(ID, TYPE, ATTRS, HEADER, LANG, FEATURE) BUILTIN(ID, TYPE, ATTRS)
+#endif
+
 // In libgcc
 BUILTIN(__clear_cache, "vv*v*", "i")
 

 LANGBUILTIN(_MoveToCoprocessor, "vUiIUiIUiIUiIUiIUi", "", ALL_MS_LANGUAGES)
 LANGBUILTIN(_MoveToCoprocessor2, "vUiIUiIUiIUiIUiIUi", "", ALL_MS_LANGUAGES)
 
+TARGET_HEADER_BUILTIN(_BitScanForward, "UcULi*ULi", "n", "intrin.h", ALL_MS_LANGUAGES, "")
+TARGET_HEADER_BUILTIN(_BitScanReverse, "UcULi*ULi", "n", "intrin.h", ALL_MS_LANGUAGES, "")
+TARGET_HEADER_BUILTIN(_BitScanForward64, "UcULi*ULLi", "n", "intrin.h", ALL_MS_LANGUAGES, "")
+TARGET_HEADER_BUILTIN(_BitScanReverse64, "UcULi*ULLi", "n", "intrin.h", ALL_MS_LANGUAGES, "")
+
 #undef BUILTIN
 #undef LANGBUILTIN
+#undef TARGET_HEADER_BUILTIN

include/clang/Basic/BuiltinsX86.def

 TARGET_BUILTIN(__builtin_ia32_monitorx, "vv*UiUi", "", "mwaitx")
 TARGET_BUILTIN(__builtin_ia32_mwaitx, "vUiUiUi", "", "mwaitx")
 
+// MSVC
+TARGET_HEADER_BUILTIN(_BitScanForward, "UcULi*ULi", "n", "intrin.h", ALL_MS_LANGUAGES, "")
+TARGET_HEADER_BUILTIN(_BitScanReverse, "UcULi*ULi", "n", "intrin.h", ALL_MS_LANGUAGES, "")
+
 #undef BUILTIN
 #undef TARGET_BUILTIN
 #undef TARGET_HEADER_BUILTIN

include/clang/Basic/BuiltinsX86_64.def

 TARGET_HEADER_BUILTIN(__mulh,  "LLiLLiLLi",    "nch", "intrin.h", ALL_MS_LANGUAGES, "")
 TARGET_HEADER_BUILTIN(__umulh, "ULLiULLiULLi", "nch", "intrin.h", ALL_MS_LANGUAGES, "")
 
+TARGET_HEADER_BUILTIN(_BitScanForward64, "UcULi*ULLi", "n", "intrin.h", ALL_MS_LANGUAGES, "")
+TARGET_HEADER_BUILTIN(_BitScanReverse64, "UcULi*ULLi", "n", "intrin.h", ALL_MS_LANGUAGES, "")
+
 #undef BUILTIN
 #undef TARGET_HEADER_BUILTIN

lib/Basic/Targets.cpp

   { #ID, TYPE, ATTRS, nullptr, LANG, nullptr },
 #define LIBBUILTIN(ID, TYPE, ATTRS, HEADER) \
   { #ID, TYPE, ATTRS, HEADER, ALL_LANGUAGES, nullptr },
+#define TARGET_HEADER_BUILTIN(ID, TYPE, ATTRS, HEADER, LANGS, FEATURE) \
+  { #ID, TYPE, ATTRS, HEADER, LANGS, FEATURE },
 #include "clang/Basic/BuiltinsARM.def"
 };
 

lib/CodeGen/CGBuiltin.cpp

   }
 }
 
+// Many of MSVC builtins are on both x64 and ARM; to avoid repeating code, we
+// handle them here.
+enum class CodeGenFunction::MSVCIntrin {
+  _BitScanForward,
+  _BitScanReverse
+};
+
+Value *CodeGenFunction::EmitMSVCBuiltinExpr(MSVCIntrin BuiltinID,
+                                            const CallExpr *E) {
+  switch (BuiltinID) {
+  case MSVCIntrin::_BitScanForward:
+  case MSVCIntrin::_BitScanReverse: {
+    Value *ArgValue = EmitScalarExpr(E->getArg(1));
+
+    llvm::Type *ArgType = ArgValue->getType();
+    llvm::Type *IndexType =
+        EmitScalarExpr(E->getArg(0))->getType()->getPointerElementType();
+    llvm::Type *ResultType = ConvertType(E->getType());
+
+    Value *ArgZero = llvm::Constant::getNullValue(ArgType);
+    Value *ResZero = llvm::Constant::getNullValue(ResultType);
+    Value *ResOne = llvm::ConstantInt::get(ResultType, 1);
+
+    BasicBlock *Begin = Builder.GetInsertBlock();
+    BasicBlock *End = createBasicBlock("bitscan_end", this->CurFn);
+    Builder.SetInsertPoint(End);
+    PHINode *Result = Builder.CreatePHI(ResultType, 2, "bitscan_result");
+
+    Builder.SetInsertPoint(Begin);
+    Value *IsZero = Builder.CreateICmpEQ(ArgValue, ArgZero);
+    BasicBlock *NotZero = createBasicBlock("bitscan_not_zero", this->CurFn);
+    Builder.CreateCondBr(IsZero, End, NotZero);
+    Result->addIncoming(ResZero, Begin);
+
+    Builder.SetInsertPoint(NotZero);
+    Address IndexAddress = EmitPointerWithAlignment(E->getArg(0));
+
+    if (BuiltinID == MSVCIntrin::_BitScanForward) {
+      Value *F = CGM.getIntrinsic(Intrinsic::cttz, ArgType);
+      Value *ZeroCount = Builder.CreateCall(F, {ArgValue, Builder.getTrue()});
+      ZeroCount = Builder.CreateIntCast(ZeroCount, IndexType, false);
+      Builder.CreateStore(ZeroCount, IndexAddress, false);
+    } else {
+      unsigned ArgWidth = cast<llvm::IntegerType>(ArgType)->getBitWidth();
+      Value *ArgTypeLastIndex = llvm::ConstantInt::get(IndexType, ArgWidth - 1);
+
+      Value *F = CGM.getIntrinsic(Intrinsic::ctlz, ArgType);
+      Value *ZeroCount = Builder.CreateCall(F, {ArgValue, Builder.getTrue()});
+      ZeroCount = Builder.CreateIntCast(ZeroCount, IndexType, false);
+      Value *Index = Builder.CreateNSWSub(ArgTypeLastIndex, ZeroCount);
+      Builder.CreateStore(Index, IndexAddress, false);
+    }
+    Builder.CreateBr(End);
+    Result->addIncoming(ResOne, NotZero);
+
+    Builder.SetInsertPoint(End);
+    return Result;
+  }
+  }
+  llvm_unreachable("Incorrect MSVC intrinsic!");
+}
+
 Value *CodeGenFunction::EmitTargetBuiltinExpr(unsigned BuiltinID,
                                               const CallExpr *E) {
   if (getContext().BuiltinInfo.isAuxBuiltinID(BuiltinID)) {

     return Builder.CreateCall(F, {Ops[1], Ops[2], Ops[0],
                                   Ops[3], Ops[4], Ops[5]});
   }
+  case ARM::BI_BitScanForward:
+  case ARM::BI_BitScanForward64:
+    return EmitMSVCBuiltinExpr(MSVCIntrin::_BitScanForward, E);
+  case ARM::BI_BitScanReverse:
+  case ARM::BI_BitScanReverse64:
+    return EmitMSVCBuiltinExpr(MSVCIntrin::_BitScanReverse, E);
   }
 
   // Get the last argument, which specifies the vector type.

     HigherBits = Builder.CreateIntCast(HigherBits, ResType, IsSigned);
     return HigherBits;
   }
+
+  case X86::BI_BitScanForward:
+  case X86::BI_BitScanForward64:
+    return EmitMSVCBuiltinExpr(MSVCIntrin::_BitScanForward, E);
+  case X86::BI_BitScanReverse:
+  case X86::BI_BitScanReverse64:
+    return EmitMSVCBuiltinExpr(MSVCIntrin::_BitScanReverse, E);
   }
 }
 

lib/CodeGen/CodeGenFunction.h

   llvm::Value *EmitWebAssemblyBuiltinExpr(unsigned BuiltinID,
                                           const CallExpr *E);
 
+private:
+  enum class MSVCIntrin;
+
+public:
+  llvm::Value *EmitMSVCBuiltinExpr(MSVCIntrin BuiltinID, const CallExpr *E);
+
   llvm::Value *EmitObjCProtocolExpr(const ObjCProtocolExpr *E);
   llvm::Value *EmitObjCStringLiteral(const ObjCStringLiteral *E);
   llvm::Value *EmitObjCBoxedExpr(const ObjCBoxedExpr *E);

lib/Headers/intrin.h

 |* Bit Counting and Testing
 \*----------------------------------------------------------------------------*/
 static __inline__ unsigned char __DEFAULT_FN_ATTRS
-_BitScanForward(unsigned long *_Index, unsigned long _Mask) {
-  if (!_Mask)
-    return 0;
-  *_Index = __builtin_ctzl(_Mask);
-  return 1;
-}
-static __inline__ unsigned char __DEFAULT_FN_ATTRS
-_BitScanReverse(unsigned long *_Index, unsigned long _Mask) {
-  if (!_Mask)
-    return 0;
-  *_Index = 31 - __builtin_clzl(_Mask);
-  return 1;
-}
-static __inline__ unsigned char __DEFAULT_FN_ATTRS
 _bittest(long const *_BitBase, long _BitPos) {
   return (*_BitBase >> _BitPos) & 1;
 }

 #endif
 #ifdef __x86_64__
 static __inline__ unsigned char __DEFAULT_FN_ATTRS
-_BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask) {
-  if (!_Mask)
-    return 0;
-  *_Index = __builtin_ctzll(_Mask);
-  return 1;
-}
-static __inline__ unsigned char __DEFAULT_FN_ATTRS
-_BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask) {
-  if (!_Mask)
-    return 0;
-  *_Index = 63 - __builtin_clzll(_Mask);
-  return 1;
-}
-static __inline__ unsigned char __DEFAULT_FN_ATTRS
 _bittest64(__int64 const *_BitBase, __int64 _BitPos) {
   return (*_BitBase >> _BitPos) & 1;
 }

test/CodeGen/ms-intrinsics.c

 // RUN: %clang_cc1 -ffreestanding -fms-extensions -fms-compatibility -fms-compatibility-version=17.00 \
 // RUN:         -triple i686--windows -Oz -emit-llvm %s -o - \
-// RUN:         | FileCheck %s -check-prefix CHECK -check-prefix CHECK-I386
+// RUN:         | FileCheck %s -check-prefix=CHECK -check-prefix=CHECK-I386
 // RUN: %clang_cc1 -ffreestanding -fms-extensions -fms-compatibility -fms-compatibility-version=17.00 \
 // RUN:         -triple thumbv7--windows -Oz -emit-llvm %s -o - \
-// RUN:         | FileCheck %s
+// RUN:         | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-ARM-X64
 // RUN: %clang_cc1 -ffreestanding -fms-extensions -fms-compatibility -fms-compatibility-version=17.00 \
 // RUN:         -triple x86_64--windows -Oz -emit-llvm %s -o - \
-// RUN:         | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-X64
+// RUN:         | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-X64 --check-prefix=CHECK-ARM-X64
 
 // intrin.h needs size_t, but -ffreestanding prevents us from getting it from
 // stddef.h.  Work around it with this typedef.

 
 #include <intrin.h>
 
+unsigned char test_BitScanForward(unsigned long *Index, unsigned long Mask) {
+  return _BitScanForward(Index, Mask);
+}
+// CHECK: define{{.*}}i8 @test_BitScanForward(i32* {{[a-z_ ]*}}%Index, i32 {{[a-z_ ]*}}%Mask){{.*}}{
+// CHECK:   [[ISNOTZERO:%[a-z0-9._]+]] = icmp eq i32 %Mask, 0
+// CHECK:   br i1 [[ISNOTZERO]], label %[[END_LABEL:[a-z0-9.]+]], label %[[ISNOTZERO_LABEL:[0-9]+]]
+// CHECK: ; <label>:[[END_LABEL]]:
+// CHECK:   [[RESULT:%[a-z0-9._]+]] = phi i8 [ 0, %[[ISZERO_LABEL:[0-9]+]] ], [ 1, %[[ISNOTZERO_LABEL]] ]
+// CHECK:   ret i8 [[RESULT]]
+// CHECK: ; <label>:[[ISNOTZERO_LABEL]]:
+// CHECK:   [[INDEX:%[0-9]+]] = tail call i32 @llvm.cttz.i32(i32 %Mask, i1 true)
+// CHECK:   store i32 [[INDEX]], i32* %Index, align 4
+// CHECK:   br label %[[END_LABEL]]
+
+unsigned char test_BitScanReverse(unsigned long *Index, unsigned long Mask) {
+  return _BitScanReverse(Index, Mask);
+}
+// CHECK: define{{.*}}i8 @test_BitScanReverse(i32* {{[a-z_ ]*}}%Index, i32 {{[a-z_ ]*}}%Mask){{.*}}{
+// CHECK:   [[ISNOTZERO:%[0-9]+]] = icmp eq i32 %Mask, 0
+// CHECK:   br i1 [[ISNOTZERO]], label %[[END_LABEL:[a-z0-9.]+]], label %[[ISNOTZERO_LABEL:[0-9]+]]
+// CHECK: ; <label>:[[END_LABEL]]:
+// CHECK:   [[RESULT:%[a-z0-9._]+]] = phi i8 [ 0, %[[ISZERO_LABEL:[0-9]+]] ], [ 1, %[[ISNOTZERO_LABEL]] ]
+// CHECK:   ret i8 [[RESULT]]
+// CHECK: ; <label>:[[ISNOTZERO_LABEL]]:
+// CHECK:   [[REVINDEX:%[0-9]+]] = tail call i32 @llvm.ctlz.i32(i32 %Mask, i1 true)
+// CHECK:   [[INDEX:%[0-9]+]] = xor i32 [[REVINDEX]], 31
+// CHECK:   store i32 [[INDEX]], i32* %Index, align 4
+// CHECK:   br label %[[END_LABEL]]
+
+#if defined(__x86_64__) || defined(__arm__)
+unsigned char test_BitScanForward64(unsigned long *Index, unsigned __int64 Mask) {
+  return _BitScanForward64(Index, Mask);
+}
+// CHECK-ARM-X64: define{{.*}}i8 @test_BitScanForward64(i32* {{[a-z_ ]*}}%Index, i64 {{[a-z_ ]*}}%Mask){{.*}}{
+// CHECK-ARM-X64:   [[ISNOTZERO:%[a-z0-9._]+]] = icmp eq i64 %Mask, 0
+// CHECK-ARM-X64:   br i1 [[ISNOTZERO]], label %[[END_LABEL:[a-z0-9.]+]], label %[[ISNOTZERO_LABEL:[0-9]+]]
+// CHECK-ARM-X64: ; <label>:[[END_LABEL]]:
+// CHECK-ARM-X64:   [[RESULT:%[a-z0-9._]+]] = phi i8 [ 0, %[[ISZERO_LABEL:[0-9]+]] ], [ 1, %[[ISNOTZERO_LABEL]] ]
+// CHECK-ARM-X64:   ret i8 [[RESULT]]
+// CHECK-ARM-X64: ; <label>:[[ISNOTZERO_LABEL]]:
+// CHECK-ARM-X64:   [[INDEX:%[0-9]+]] = tail call i64 @llvm.cttz.i64(i64 %Mask, i1 true)
+// CHECK-ARM-X64:   [[TRUNC_INDEX:%[0-9]+]] = trunc i64 [[INDEX]] to i32
+// CHECK-ARM-X64:   store i32 [[TRUNC_INDEX]], i32* %Index, align 4
+// CHECK-ARM-X64:   br label %[[END_LABEL]]
+
+unsigned char test_BitScanReverse64(unsigned long *Index, unsigned __int64 Mask) {
+  return _BitScanReverse64(Index, Mask);
+}
+// CHECK-ARM-X64: define{{.*}}i8 @test_BitScanReverse64(i32* {{[a-z_ ]*}}%Index, i64 {{[a-z_ ]*}}%Mask){{.*}}{
+// CHECK-ARM-X64:   [[ISNOTZERO:%[0-9]+]] = icmp eq i64 %Mask, 0
+// CHECK-ARM-X64:   br i1 [[ISNOTZERO]], label %[[END_LABEL:[a-z0-9.]+]], label %[[ISNOTZERO_LABEL:[0-9]+]]
+// CHECK-ARM-X64: ; <label>:[[END_LABEL]]:
+// CHECK-ARM-X64:   [[RESULT:%[a-z0-9._]+]] = phi i8 [ 0, %[[ISZERO_LABEL:[0-9]+]] ], [ 1, %[[ISNOTZERO_LABEL]] ]
+// CHECK-ARM-X64:   ret i8 [[RESULT]]
+// CHECK-ARM-X64: ; <label>:[[ISNOTZERO_LABEL]]:
+// CHECK-ARM-X64:   [[REVINDEX:%[0-9]+]] = tail call i64 @llvm.ctlz.i64(i64 %Mask, i1 true)
+// CHECK-ARM-X64:   [[TRUNC_REVINDEX:%[0-9]+]] = trunc i64 [[REVINDEX]] to i32
+// CHECK-ARM-X64:   [[INDEX:%[0-9]+]] = xor i32 [[TRUNC_REVINDEX]], 63
+// CHECK-ARM-X64:   store i32 [[INDEX]], i32* %Index, align 4
+// CHECK-ARM-X64:   br label %[[END_LABEL]]
+#endif
+
 void *test_InterlockedExchangePointer(void * volatile *Target, void *Value) {
   return _InterlockedExchangePointer(Target, Value);
 }