This is an archive of the discontinued LLVM Phabricator instance.

[Builtins] Implement __builtin_clrsb to be compatible with gcc
ClosedPublic

Authored by craig.topper on Aug 1 2018, 6:25 PM.

Details

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.

Diff Detail

Event Timeline

craig.topper created this revision.Aug 1 2018, 6:25 PM

Test case?

lib/CodeGen/CGBuiltin.cpp
1563

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

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

spatel added a comment.Aug 8 2018, 6:21 AM

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

Use ctlz(zero_undef=false) and sub

This revision is now accepted and ready to land.Aug 8 2018, 11:18 AM
This revision was automatically updated to reflect the committed changes.