[Builtins] Implement __builtin_clrsb to be compatible with gcc

[craig.topper]

Summary

gcc defines an intrinsic called __builtin_clrsb which counts the number of extra sign bits on a number. This is equivalent to counting the number of leading zeros on a positive number or the number of leading ones on a negative number and subtracting one from the result. Since we can't count leading ones we need to invert negative numbers to count zeros.

The emitted sequence contains a bit of trickery stolen from an LLVM AArch64 test arm64-clrsb.ll to prevent passing a value of 0 to ctlz. I used a icmp slt and a select to conditionally negate, but InstCombine will turn that into an ashr+xor. I can emit that directly if that's prefered. I know @spatel has been trying to remove some of the bit tricks from InstCombine so I'm not sure if the ashr+xor form will be canonical going forward.

This patch will cause the builtin to be expanded inline while gcc uses a call to a function like clrsbdi2 that is implemented in libgcc. But this is similar to what we already do for popcnt. And I don't think compiler-rt supports clrsbdi2.

[craig.topper]

Ping

[bkramer]

Test case?

lib/CodeGen/CGBuiltin.cpp

1563

CreateIntCast just does nothing if the types match, so this check isn't needed.

[craig.topper]

Add the test case that I failed to pick up in the original diff.

[spatel]

About the bit hacking: I don't think clang should be in the optimization business. We should be able to take the most obvious/simple representation for this builtin and reduce it as needed (either in instcombine or the backend). So it would be better to use the version with the subtract rather than shift/or. That version corresponds more directly to the code in APInt::getMinSignedBits()?

include/clang/Basic/Builtins.def

416

Is is intentional that clang doesn't document the behavior of the builtins that it copies from gcc? I'd think logic descriptions for all of these would be handy, but especially for less common ones like 'clrsb'.

[craig.topper]

Use ctlz(zero_undef=false) and sub

[bkramer]

lg

include/clang/Basic/Builtins.def

 BUILTIN(__builtin_ffsl , "iLi" , "Fnc")
 BUILTIN(__builtin_ffsll, "iLLi", "Fnc")
 BUILTIN(__builtin_parity  , "iUi"  , "nc")
 BUILTIN(__builtin_parityl , "iULi" , "nc")
 BUILTIN(__builtin_parityll, "iULLi", "nc")
 BUILTIN(__builtin_popcount  , "iUi"  , "nc")
 BUILTIN(__builtin_popcountl , "iULi" , "nc")
 BUILTIN(__builtin_popcountll, "iULLi", "nc")
+BUILTIN(__builtin_clrsb  , "ii"  , "nc")
+BUILTIN(__builtin_clrsbl , "iLi" , "nc")
+BUILTIN(__builtin_clrsbll, "iLLi", "nc")
 
 // FIXME: These type signatures are not correct for targets with int != 32-bits
 // or with ULL != 64-bits.
 BUILTIN(__builtin_bswap16, "UsUs", "nc")
 BUILTIN(__builtin_bswap32, "UiUi", "nc")
 BUILTIN(__builtin_bswap64, "ULLiULLi", "nc")
 
 BUILTIN(__builtin_bitreverse8, "UcUc", "nc")

lib/CodeGen/CGBuiltin.cpp

RValue CodeGenFunction::EmitBuiltinExpr(const FunctionDecl *FD,
   case Builtin::BI__builtin_cimagl:
   case Builtin::BIcimag:
   case Builtin::BIcimagf:
   case Builtin::BIcimagl: {
     ComplexPairTy ComplexVal = EmitComplexExpr(E->getArg(0));
     return RValue::get(ComplexVal.second);
   }
 
+  case Builtin::BI__builtin_clrsb:
+  case Builtin::BI__builtin_clrsbl:
+  case Builtin::BI__builtin_clrsbll: {
+    // clrsb(x) -> clz(x < 0 ? ~x : x) - 1 or
+    //          -> clz(((x < 0 ? ~x : x) << 1) | 1)
+    Value *ArgValue = EmitScalarExpr(E->getArg(0));
+
+    llvm::Type *ArgType = ArgValue->getType();
+    Value *F = CGM.getIntrinsic(Intrinsic::ctlz, ArgType);
+
+    llvm::Type *ResultType = ConvertType(E->getType());
+    Value *Zero = llvm::Constant::getNullValue(ArgType);
+    Value *IsNeg = Builder.CreateICmpSLT(ArgValue, Zero, "isneg");
+    Value *Inverse = Builder.CreateNot(ArgValue, "not");
+    Value *Tmp = Builder.CreateSelect(IsNeg, Inverse, ArgValue);
+    // Now we need to calculate ctlz(Tmp)-1, but Tmp might be zero. We know
+    // the sign bit is zero, so we can shift it out. Then put a 1 in the LSB.
+    // This removes one leading zero like the subtract does, and replaces it
+    // with a guaranteed one to prevent the value being 0.
+    Value *One = llvm::ConstantInt::get(ArgType, 1);
+    Tmp = Builder.CreateShl(Tmp, One);
+    Tmp = Builder.CreateOr(Tmp, One);
+    Value *Result = Builder.CreateCall(F, {Tmp, Builder.getTrue()});
+    Result = Builder.CreateIntCast(Result, ResultType, /*isSigned*/true,
+                                   "cast");
+    return RValue::get(Result);
+  }
   case Builtin::BI__builtin_ctzs:
   case Builtin::BI__builtin_ctz:
   case Builtin::BI__builtin_ctzl:
   case Builtin::BI__builtin_ctzll: {
     Value *ArgValue = EmitCheckedArgForBuiltin(E->getArg(0), BCK_CTZPassedZero);
 
     llvm::Type *ArgType = ArgValue->getType();
     Value *F = CGM.getIntrinsic(Intrinsic::cttz, ArgType);

test/CodeGen/builtin_clrsb.c

+// RUN: %clang_cc1 %s -emit-llvm -o - | FileCheck %s
+
+int test__builtin_clrsb(int x) {
+// CHECK-LABEL: test__builtin_clrsb
+// CHECK: [[C:%.*]] = icmp slt i32 [[X:%.*]], 0
+// CHECK: [[INV:%.*]] = xor i32 [[X]], -1
+// CHECK: [[SEL:%.*]] = select i1 [[C]], i32 [[INV]], i32 [[X]]
+// CHECK: [[SHL:%.*]] = shl i32 [[SEL]], 1
+// CHECK: [[OR:%.*]] = or i32 [[SHL]], 1
+// CHECK: call i32 @llvm.ctlz.i32(i32 [[OR]], i1 true)
+  return __builtin_clrsb(x);
+}
+
+int test__builtin_clrsbll(long long x) {
+// CHECK-LABEL: test__builtin_clrsbll
+// CHECK: [[C:%.*]] = icmp slt i64 [[X:%.*]], 0
+// CHECK-NEXT: [[INV:%.*]] = xor i64 [[X]], -1
+// CHECK-NEXT: [[SEL:%.*]] = select i1 [[C]], i64 [[INV]], i64 [[X]]
+// CHECK-NEXT: [[SHL:%.*]] = shl i64 [[SEL]], 1
+// CHECK-NEXT: [[OR:%.*]] = or i64 [[SHL]], 1
+// CHECK-NEXT: [[CTLZ:%.*]] = call i64 @llvm.ctlz.i64(i64 [[OR]], i1 true)
+// CHECK-NEXT: trunc i64 [[CTLZ]] to i32
+  return __builtin_clrsbll(x);
+}