Re: [RFC] stdbit.h implementation

[Jakub Jelinek <jakub@redhat.com>]

On Tue, Nov 14, 2023 at 06:02:12PM +0000, Joseph Myers wrote:
> On Tue, 14 Nov 2023, Jakub Jelinek wrote:
> 
> > In order to double-check the __builtin_{clz,ctz,popcount}g builtins
> > I've added today to GCC, I've tried to implement the C23 stdbit.h
> > header (but just the header, not anything further) plus a test (though,
> > in GCC style where it aborts on error and returns 0 otherwise) for it.
> 
> The following is my current in-progress patch (which needs tests and 
> documentation, so it's quite possible some implementations are currently 
> incorrect) - including all the out-of-line implementations (defined so 
> that the out-of-line function implementations use the inline macro 
> implementations from the header).  It doesn't attempt to use the new 
> built-in functions (or, thus, to support _BitInt).  Among my notes for 
> things to cover in tests include that all macros are usable inside sizeof 
> etc. outside of a function (thus, do not use ({ })) - also that 
> type-specific calls have the correct implicit argument conversions, also 
> that both type-specific and type-generic calls evaluate arguments exactly 
> once.  I haven't tested how well-optimized code is for any of these 
> implementations (type-specific or type-generic) - but if it isn't, it 
> probably should be, since I think all of these are among reasonable 
> options for how to express the operations in terms of the underlying 
> built-in functions.

I think the fallback _Generic versions satisfy that, but the
__builtin_{clz,ctz,popcount}g unfortunately do use ({ }) in 3 of them.
In one case it is just an optimization attempt and it isn't strictly
necessary, stdc_bit_width can be implemented as popcount (value) == 1
or as value && (value & (value - 1)) == 0 or as
value && (value & -value) == value, and perhaps we could just optimize
popcount (value) == 1 into the second test in GCC in match.pd.
But, I'm really out of ideas what to do about stdc_bit_floor and
stdc_bit_ceil to
1) evaluate argument just once
2) handle all _BitInts
3) avoid ({ })
One can't use an inline function because of 2), unless 65535+
functions are added, 3) was a way to handle 1).

Actually, maybe
#define stdc_bit_ceil(value) \
  (((__typeof (value)) 1) << ((__builtin_popcountg ((__typeof (value)) ~(__typeof (value)) 0) - __builtin_clzg ((__typeof (value)) (value - 1), 0)) % __builtin_popcountg ((__typeof (value)) ~(__typeof (value)) 0)))
where say on unsigned _BitInt(275)
the above will be
  (((unsigned _BitInt(275)) 1) << ((275 - __builtin_clzg ((__typeof (value)) (value - 1), 0)) % 275))
and so for 0
  (((unsigned _BitInt(275)) 1) << (0 % 275))
and for 1
  (((unsigned _BitInt(275)) 1) << (275 % 275))
Maybe add some unsigned int cast in there to avoid the modulo being
signed and allow e.g. ffor powers of two width to be handled more
efficiently.

But the stdc_bit_floor needs 0 return value for input value of 0
and otherwise 1 << something, so
  ((value) == 0 ? (__typeof (value)) 0 : ((__typeof (value)) 1) << (__builtin_popcountg ((__typeof (value)) ~(__typeof (value)) 0) - 1 - __builtin_clzg (value)))
is inappropriate because if evaluates value twice; and while I can make
the shift count into whatever int value we want for value == 0 when
evaluating it just once, it won't turn the result into 0 unless << -1
would be allowed and result into >> 1.
?: with left out middle operand is yet another way how to avoid evaluating
something twice, but no idea how to use it here.
Maybe one ugly way for unsigned _BitInt with the exception of
unsigned _BitInt(__BITINT_MAXWIDTH__) would be (after
__builtin_classify_type (value) == 18 check) to use
 ((__typeof (value)) (((unsigned _BitInt(__builtin_popcountg ((__typeof (value)) ~(__typeof (value)) 0) + 1) 1) << (__builtin_popcountg ((__typeof (value)) ~(__typeof (value)) 0) - __builtin_clzg (value, __builtin_popcountg ((__typeof (value)) ~(__typeof (value)) 0)))) >> 1))
i.e. perform the left shift in one bit wider _BitInt type than value, say
again for unsigned _BitInt(275) value shift ((unsigned _BitInt(276)) 1) left
by 0 for the value == 0 case and by 1..275 for the other cases, then shift
right by 1 bit and cast.
And perhaps the unsigned _BitInt(__BITINT_MAXWIDTH__) case could be handled
in an static inline function (like the non-_BitInt cases).

BTW, in my stdbit.h version, I've added explicit casts in all the
sizeof/_Generic using type-generic macros, because otherwise GCC
-Wconversion was quite noisy on lots of uses in the testcase.

Anyway, feel free to cherry-pick anything useful from the posted patch.

	Jakub