[PATCH] D50168: [Builtins] Implement __builtin_clrsb to be compatible with gcc

2018-08-08 Thread Phabricator via Phabricator via cfe-commits 
This revision was automatically updated to reflect the committed changes.
Closed by commit rC339282: [Builtins] Implement __builtin_clrsb to be 
compatible with gcc (authored by ctopper, committed by ).
Herald added a subscriber: kristina.

Repository:
  rC Clang

https://reviews.llvm.org/D50168

Files:
  include/clang/Basic/Builtins.def
  lib/CodeGen/CGBuiltin.cpp
  test/CodeGen/builtin_clrsb.c


Index: include/clang/Basic/Builtins.def
===
--- include/clang/Basic/Builtins.def
+++ include/clang/Basic/Builtins.def
@@ -413,6 +413,9 @@
 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.
Index: test/CodeGen/builtin_clrsb.c
===
--- test/CodeGen/builtin_clrsb.c
+++ test/CodeGen/builtin_clrsb.c
@@ -0,0 +1,22 @@
+// 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-NEXT: [[INV:%.*]] = xor i32 [[X]], -1
+// CHECK-NEXT: [[SEL:%.*]] = select i1 [[C]], i32 [[INV]], i32 [[X]]
+// CHECK-NEXT: [[CTLZ:%.*]] = call i32 @llvm.ctlz.i32(i32 [[SEL]], i1 false)
+// CHECK-NEXT: [[SUB:%.*]] = sub i32 [[CTLZ]], 1
+  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: [[CTLZ:%.*]] = call i64 @llvm.ctlz.i64(i64 [[SEL]], i1 false)
+// CHECK-NEXT: [[SUB:%.*]] = sub i64 [[CTLZ]], 1
+// CHECK-NEXT: trunc i64 [[SUB]] to i32
+  return __builtin_clrsbll(x);
+}
Index: lib/CodeGen/CGBuiltin.cpp
===
--- lib/CodeGen/CGBuiltin.cpp
+++ lib/CodeGen/CGBuiltin.cpp
@@ -1537,6 +1537,26 @@
 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
+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);
+Value *Ctlz = Builder.CreateCall(F, {Tmp, Builder.getFalse()});
+Value *Result = Builder.CreateSub(Ctlz, llvm::ConstantInt::get(ArgType, 
1));
+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:


Index: include/clang/Basic/Builtins.def
===
--- include/clang/Basic/Builtins.def
+++ include/clang/Basic/Builtins.def
@@ -413,6 +413,9 @@
 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.
Index: test/CodeGen/builtin_clrsb.c
===
--- test/CodeGen/builtin_clrsb.c
+++ test/CodeGen/builtin_clrsb.c
@@ -0,0 +1,22 @@
+// 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-NEXT: [[INV:%.*]] = xor i32 [[X]], -1
+// CHECK-NEXT: [[SEL:%.*]] = select i1 [[C]], i32 [[INV]], i32 [[X]]
+// CHECK-NEXT: [[CTLZ:%.*]] = call i32 @llvm.ctlz.i32(i32 [[SEL]], i1 false)
+// CHECK-NEXT: [[SUB:%.*]] = sub i32 [[CTLZ]], 1
+  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: [[CTLZ:%.*]] = call i64 @llvm.ctlz.i64(i64 [[SEL]], i1 false)
+// CHECK-NEXT: [[SUB:%.*]] = sub i64 [[CTLZ]], 1
+// CHECK-NEXT: trunc i64 [[SUB]] to i32
+

[PATCH] D50168: [Builtins] Implement __builtin_clrsb to be compatible with gcc

2018-08-08 Thread Benjamin Kramer via Phabricator via cfe-commits 
bkramer accepted this revision.
bkramer added a comment.
This revision is now accepted and ready to land.

lg


https://reviews.llvm.org/D50168



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D50168: [Builtins] Implement __builtin_clrsb to be compatible with gcc

2018-08-08 Thread Craig Topper via Phabricator via cfe-commits 
craig.topper updated this revision to Diff 159753.
craig.topper added a comment.

Use ctlz(zero_undef=false) and sub


https://reviews.llvm.org/D50168

Files:
  include/clang/Basic/Builtins.def
  lib/CodeGen/CGBuiltin.cpp
  test/CodeGen/builtin_clrsb.c


Index: test/CodeGen/builtin_clrsb.c
===
--- /dev/null
+++ test/CodeGen/builtin_clrsb.c
@@ -0,0 +1,22 @@
+// 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-NEXT: [[INV:%.*]] = xor i32 [[X]], -1
+// CHECK-NEXT: [[SEL:%.*]] = select i1 [[C]], i32 [[INV]], i32 [[X]]
+// CHECK-NEXT: [[CTLZ:%.*]] = call i32 @llvm.ctlz.i32(i32 [[SEL]], i1 false)
+// CHECK-NEXT: [[SUB:%.*]] = sub i32 [[CTLZ]], 1
+  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: [[CTLZ:%.*]] = call i64 @llvm.ctlz.i64(i64 [[SEL]], i1 false)
+// CHECK-NEXT: [[SUB:%.*]] = sub i64 [[CTLZ]], 1
+// CHECK-NEXT: trunc i64 [[SUB]] to i32
+  return __builtin_clrsbll(x);
+}
Index: lib/CodeGen/CGBuiltin.cpp
===
--- lib/CodeGen/CGBuiltin.cpp
+++ lib/CodeGen/CGBuiltin.cpp
@@ -1537,6 +1537,26 @@
 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
+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);
+Value *Ctlz = Builder.CreateCall(F, {Tmp, Builder.getFalse()});
+Value *Result = Builder.CreateSub(Ctlz, llvm::ConstantInt::get(ArgType, 
1));
+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:
Index: include/clang/Basic/Builtins.def
===
--- include/clang/Basic/Builtins.def
+++ include/clang/Basic/Builtins.def
@@ -413,6 +413,9 @@
 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.


Index: test/CodeGen/builtin_clrsb.c
===
--- /dev/null
+++ test/CodeGen/builtin_clrsb.c
@@ -0,0 +1,22 @@
+// 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-NEXT: [[INV:%.*]] = xor i32 [[X]], -1
+// CHECK-NEXT: [[SEL:%.*]] = select i1 [[C]], i32 [[INV]], i32 [[X]]
+// CHECK-NEXT: [[CTLZ:%.*]] = call i32 @llvm.ctlz.i32(i32 [[SEL]], i1 false)
+// CHECK-NEXT: [[SUB:%.*]] = sub i32 [[CTLZ]], 1
+  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: [[CTLZ:%.*]] = call i64 @llvm.ctlz.i64(i64 [[SEL]], i1 false)
+// CHECK-NEXT: [[SUB:%.*]] = sub i64 [[CTLZ]], 1
+// CHECK-NEXT: trunc i64 [[SUB]] to i32
+  return __builtin_clrsbll(x);
+}
Index: lib/CodeGen/CGBuiltin.cpp
===
--- lib/CodeGen/CGBuiltin.cpp
+++ lib/CodeGen/CGBuiltin.cpp
@@ -1537,6 +1537,26 @@
 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
+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,

[PATCH] D50168: [Builtins] Implement __builtin_clrsb to be compatible with gcc

2018-08-08 Thread Sanjay Patel via Phabricator via cfe-commits 
spatel added a comment.

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()?




Comment at: include/clang/Basic/Builtins.def:416
 BUILTIN(__builtin_popcountll, "iULLi", "nc")
+BUILTIN(__builtin_clrsb  , "ii"  , "nc")
+BUILTIN(__builtin_clrsbl , "iLi" , "nc")

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'.


https://reviews.llvm.org/D50168



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D50168: [Builtins] Implement __builtin_clrsb to be compatible with gcc

2018-08-07 Thread Craig Topper via Phabricator via cfe-commits 
craig.topper updated this revision to Diff 159627.
craig.topper added a comment.

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


https://reviews.llvm.org/D50168

Files:
  include/clang/Basic/Builtins.def
  lib/CodeGen/CGBuiltin.cpp
  test/CodeGen/builtin_clrsb.c


Index: test/CodeGen/builtin_clrsb.c
===
--- /dev/null
+++ test/CodeGen/builtin_clrsb.c
@@ -0,0 +1,24 @@
+// 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);
+}
Index: lib/CodeGen/CGBuiltin.cpp
===
--- lib/CodeGen/CGBuiltin.cpp
+++ lib/CodeGen/CGBuiltin.cpp
@@ -1537,6 +1537,33 @@
 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:
Index: include/clang/Basic/Builtins.def
===
--- include/clang/Basic/Builtins.def
+++ include/clang/Basic/Builtins.def
@@ -413,6 +413,9 @@
 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.


Index: test/CodeGen/builtin_clrsb.c
===
--- /dev/null
+++ test/CodeGen/builtin_clrsb.c
@@ -0,0 +1,24 @@
+// 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);
+}
Index: lib/CodeGen/CGBuiltin.cpp
===
--- lib/CodeGen/CGBuiltin.cpp
+++ lib/CodeGen/CGBuiltin.cpp
@@ -1537,6 +1537,33 @@
 return

[PATCH] D50168: [Builtins] Implement __builtin_clrsb to be compatible with gcc

2018-08-07 Thread Benjamin Kramer via Phabricator via cfe-commits 
bkramer added a comment.

Test case?




Comment at: lib/CodeGen/CGBuiltin.cpp:1563
+Value *Result = Builder.CreateCall(F, {Tmp, Builder.getTrue()});
+if (Result->getType() != ResultType)
+  Result = Builder.CreateIntCast(Result, ResultType, /*isSigned*/true,

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


https://reviews.llvm.org/D50168



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D50168: [Builtins] Implement __builtin_clrsb to be compatible with gcc

2018-08-07 Thread Craig Topper via Phabricator via cfe-commits 
craig.topper added a comment.

Ping


https://reviews.llvm.org/D50168



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D50168: [Builtins] Implement __builtin_clrsb to be compatible with gcc

2018-08-01 Thread Craig Topper via Phabricator via cfe-commits 
craig.topper created this revision.
craig.topper added reviewers: bkramer, efriedma, spatel.
Herald added a reviewer: javed.absar.
Herald added a subscriber: kristof.beyls.

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.


https://reviews.llvm.org/D50168

Files:
  include/clang/Basic/Builtins.def
  lib/CodeGen/CGBuiltin.cpp


Index: lib/CodeGen/CGBuiltin.cpp
===
--- lib/CodeGen/CGBuiltin.cpp
+++ lib/CodeGen/CGBuiltin.cpp
@@ -1537,6 +1537,34 @@
 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()});
+if (Result->getType() != ResultType)
+  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:
Index: include/clang/Basic/Builtins.def
===
--- include/clang/Basic/Builtins.def
+++ include/clang/Basic/Builtins.def
@@ -413,6 +413,9 @@
 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.


Index: lib/CodeGen/CGBuiltin.cpp
===
--- lib/CodeGen/CGBuiltin.cpp
+++ lib/CodeGen/CGBuiltin.cpp
@@ -1537,6 +1537,34 @@
 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