This is an archive of the discontinued LLVM Phabricator instance.

[ADT] Add llvm::popcount to <bit> helper wrapper
ClosedPublic

Authored by RKSimon on Aug 22 2022, 12:24 PM.

Details

Summary

This patch proposes to move the llvm::detail::PopulationCounter internal helpers into ADT/bit.h and provide a llvm::popcount implementation.

I've left the countPopulation implementation in place in MathExtras.h for now, but updated it to use llvm::popcount.

Hopefully I've got the type_traits correct - I don't use them very often.

Someday we'll move to C++20 with an actual <bit> std header, and we already have this header in place to simplify matters. We'd probably benefit from moving the other <bit> helpers here at some point, but this is a first step.

Diff Detail

Event Timeline

RKSimon created this revision.Aug 22 2022, 12:24 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 22 2022, 12:24 PM
Herald added a subscriber: StephenFan. · View Herald Transcript
RKSimon requested review of this revision.Aug 22 2022, 12:24 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 22 2022, 12:24 PM

clang also supports __builtin_popcount:
https://clang.llvm.org/docs/LanguageExtensions.html

Yeah - its just a copy + paste from MathExtras.h so far - I'll add a __has_builtin()

Tyker added a subscriber: Tyker.Aug 22 2022, 1:02 PM
Tyker added inline comments.
llvm/include/llvm/ADT/bit.h
72–73

std::is_unsigned already implies std::is_integral
and it is preferable to use the *_v variants instead of adding the ::value

RKSimon updated this revision to Diff 454603.Aug 22 2022, 1:15 PM

Use std::is_unsigned_v

No need to change #if defined(__GNUC__) as clang defines this as well

kazu accepted this revision.Aug 22 2022, 1:47 PM

Great cleanup! Thanks!

This revision is now accepted and ready to land.Aug 22 2022, 1:47 PM

clang also supports __builtin_popcount:
https://clang.llvm.org/docs/LanguageExtensions.html

Yeah - its just a copy + paste from MathExtras.h so far - I'll add a __has_builtin()

Does it help? Or can LLVM pretty reliably optimize the code down to the same thing anyway? (be nice to avoid maintaining the different codepaths if they amount to the same thing anyway)

Looks like at least here clang uses the same code in either case (but doesn't use a CPU intrinsic, whereas GCC does (but GCC doesn't optimize the non-intrinsic code into the intrinsic...)): https://godbolt.org/z/G5YM4bcM6 ?

clang also supports __builtin_popcount:
https://clang.llvm.org/docs/LanguageExtensions.html

Yeah - its just a copy + paste from MathExtras.h so far - I'll add a __has_builtin()

Does it help? Or can LLVM pretty reliably optimize the code down to the same thing anyway? (be nice to avoid maintaining the different codepaths if they amount to the same thing anyway)

Looks like at least here clang uses the same code in either case (but doesn't use a CPU intrinsic, whereas GCC does (but GCC doesn't optimize the non-intrinsic code into the intrinsic...)): https://godbolt.org/z/G5YM4bcM6 ?

Sorry I wasn't thinking when I replied - clang has always defined __GNUC__ so it already uses that path - unless we want to handle other compilers that support __has_builtin and __builtin_popcount I don't think we need it.

kazu added a comment.Aug 22 2022, 2:27 PM

Looks like at least here clang uses the same code in either case (but doesn't use a CPU intrinsic, whereas GCC does (but GCC doesn't optimize the non-intrinsic code into the intrinsic...)): https://godbolt.org/z/G5YM4bcM6 ?

I get popcnt with -march=native.

Looks like at least here clang uses the same code in either case (but doesn't use a CPU intrinsic, whereas GCC does (but GCC doesn't optimize the non-intrinsic code into the intrinsic...)): https://godbolt.org/z/G5YM4bcM6 ?

I get popcnt with -march=native.

Ah, great.

Could we remove the intrinsic special case then, and just keep the explicit implementation - if it boils down to the same thing anyway, it saves us maintaining conditional code, etc?

llvm/include/llvm/ADT/bit.h
42–49
55–63

The subject should mention llvm::popcount instead of (Rust style name) llvm::ctpop

RKSimon retitled this revision from [ADT] Add llvm::ctpop to <bit> helper wrapper to [ADT] Add llvm::popcount to <bit> helper wrapper.Aug 22 2022, 11:53 PM
RKSimon edited the summary of this revision. (Show Details)

The subject should mention llvm::popcount instead of (Rust style name) llvm::ctpop

Done - my mind was obviously on other things while writing that summary!

This revision was automatically updated to reflect the committed changes.