Page MenuHomePhabricator

[ADT] Add Bitfield utilities - design #1
AbandonedPublic

Authored by gchatelet on Jun 10 2020, 9:01 AM.

Details

Summary

Context: There are places in LLVM where we need to pack typed fields into opaque values.
For instance, the XXXInst classes in llvm/include/llvm/IR/Instructions.h that extract informations from Value::SubclassData via getSubclassDataFromInstruction().
The bit twiddling is done manually: this impairs readability and prevent consistent handling of out of range values (e.g. Instructions.h)
More importantly, the bit pattern is scattered throughout the implementation making it hard to pack additionnal fields or check for overlapping bits.

Design: The Bitfield structs are to be declared together so it is clear which bits are used or not.
The code is designed with simplicity in mind, hence a few limitations:

  • Storage is limited to a single integer that cannot be bigger than uint64_t,
  • Values and storage have to be unsigned or enum (enum class works), (edit: the new design allows signed integer but not signed enums)
  • Is is not possible to store a full uint64_t at once i.e. Bitfield<uint64_t, 0, 64> will fail, (edit: the new design allows this)
  • There are no automatic detection of overlapping fields (packed bitfield declaration should help though),
  • The interface is C like so storage needs to be passed in every time (code is simpler and lifetime considerations more obvious)

Feedback welcome

Diff Detail

Event Timeline

gchatelet created this revision.Jun 10 2020, 9:01 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 10 2020, 9:01 AM

Can you create an example patch rebased on this to show how this changes the bit twiddling code for an example instruction ? Maybe this could go through an RFC ? I'm personally, this would make the code much cleaner.

The only thing that this would not handle is if an instruction does its bit twidling based on some dynamic property, e.g. SubclassData & 1 << (dynamic_value) . But your proposal does not have to be used for that case.

gchatelet added a comment.EditedJun 11 2020, 8:34 AM

Can you create an example patch rebased on this to show how this changes the bit twiddling code for an example instruction ?

Here it is D81662 (edit - this was the wrong patch)
I've added comments to highlight dubious logic.

Maybe this could go through an RFC ?

You're right. I'll send an email, thank you.

The only thing that this would not handle is if an instruction does its bit twidling based on some dynamic property, e.g. SubclassData & 1 << (dynamic_value) . But your proposal does not have to be used for that case.

Yes indeed, this code is for compile time bit fields.

simoll added a subscriber: simoll.Jun 16 2020, 6:04 AM
gchatelet updated this revision to Diff 271127.Jun 16 2020, 9:46 AM
  • Update implementation to reflect changes D81662
gchatelet updated this revision to Diff 271208.Jun 16 2020, 2:35 PM
  • Fix style
gchatelet updated this revision to Diff 271212.Jun 16 2020, 2:47 PM
  • Fix various typos
courbet accepted this revision.Jun 16 2020, 10:56 PM

I have not seen any concerns raised on the mailing lists after your proposal. Let's give it a couple more days before submitting.

This revision is now accepted and ready to land.Jun 16 2020, 10:56 PM
kpdev42 added inline comments.
llvm/include/llvm/ADT/Bitfields.h
91

Maybe it is worth to use std::numeric_limits<T>::digits here?
Like this:

static constexpr auto TypeBits = std::numeric_limits<Unsigned>::digits;

then it will be possible to remove #include <climits> // CHAR_BIT

gchatelet marked an inline comment as done.Jun 17 2020, 12:32 AM
gchatelet added inline comments.
llvm/include/llvm/ADT/Bitfields.h
91

Thx for the suggestion. Unfortunately I also use CHAR_BIT elsewhere in the file and cppreference.com says:

For integer types, this is the number of bits not counting the sign bit and the padding bits (if any)

  • For Bitfield::TypeBits the type may be signed,
  • For Bitfield::Impl::StorageBits I need the full storage space so padding bit must be accounted for.

With this in mind it seems to me that it's still beneficial to keep the climits include.

  • Regular enums under MSVC are always considered signed

@serge-sans-paille the main review is here. I intend to submit this one first, then D81662.

gchatelet edited the summary of this revision. (Show Details)Jun 17 2020, 1:36 AM
gchatelet edited the summary of this revision. (Show Details)
llvm/unittests/ADT/BitFieldsTest.cpp
22

Would that make sense to use the following syntax instead of the setField method ?

Bitfield<bool, 0, 1>(Storage) = true;

This would also have the pro of not providing a relatively generic name setField in the llvm namespace.

gchatelet marked an inline comment as done.Jun 17 2020, 5:15 AM
gchatelet added inline comments.
llvm/unittests/ADT/BitFieldsTest.cpp
22

Are you suggesting the following API changes?

// testField becomes cast to bool operator
if(Bitfield<bool, 0, 1>::testField(Storage))
=>
if(Bitfield<bool, 0, 1>(Storage))

// getField becomes cast to UserType
auto Value = Bitfield<bool, 0, 1>::getField(Storage);
=>
auto Value = Bitfield<bool, 0, 1>(Storage);

// setField becomes returning a UserType assignable object
Bitfield<bool, 0, 1>::setField(Storage, Value);
=>
Bitfield<bool, 0, 1>(Storage) = Value;

Implementation wise this is more complex:

  • we need to create one or two objects (one for test/get, and two for set),
  • for the setter we need to return a type with a reference to Storage so we have to consider Storage lifetime,
  • the returned object must not be copyable nor movable to prevent passing it to functions,
  • cast operators may introduce type promotion so it's harder to understand what's going on,
  • object may introduce indirection that prevent the compiler from generating clean code.

@courbet what do you think?

courbet added inline comments.Jun 17 2020, 7:23 AM
llvm/unittests/ADT/BitFieldsTest.cpp
22

No strong opinion. Just make sure that the wrapper object for set is non movable and copyable for lifetime issues.

gchatelet marked 4 inline comments as done.Jun 17 2020, 3:39 PM
gchatelet added inline comments.
llvm/unittests/ADT/BitFieldsTest.cpp
22

I've created an alternative design in D81662.
I couldn't get the test function as a cast operator because it would conflict with the cast to UserType when UserType is bool.
It is not possible to use enable_if to disable the offending function because SFINAE only works for deduced template arguments, and nothing is to be deduced in this case (see this stackoverflow).

Let me know what you think.

gchatelet marked 2 inline comments as done.Jun 18 2020, 1:42 AM
gchatelet added inline comments.
llvm/unittests/ADT/BitFieldsTest.cpp
22

Sorry I mixed up the patches. the alternative design is here D82058

gchatelet updated this revision to Diff 272456.Jun 22 2020, 8:43 AM

Revert bad patch

Harbormaster completed remote builds in B61244: Diff 272449.
gchatelet retitled this revision from [ADT] Add Bitfield utilities to [ADT] Add Bitfield utilities - design #1.Jun 24 2020, 5:17 AM
gchatelet abandoned this revision.Jun 29 2020, 5:49 AM

Dropped in favor of D82454