Re: __builtin_clzll and uintmax_t

Re: __builtin_clzll and uintmax_t

[FX]

Salut Marc !

> We have a variable of type uintmax_t and want to count the leading zeros. Can we just call __builtin_clzll on it?

Yes.

> In particular, can uintmax_t be larger than unsigned long long in gcc?

uintmax_t is the largest of the standard unsigned C types, so it cannot be larger than unsigned long long. On x86_64, for example:

> #include <stdio.h>
> #include <stdint.h>
> 
> int main (void)
> {
>   printf ("%lu ", sizeof (uintmax_t));
>   printf ("%lu ", sizeof (int));
>   printf ("%lu ", sizeof (long int));
>   printf ("%lu ", sizeof (long long int));
>   printf ("%lu\n", sizeof (__int128));
> }

gives : 8 4 8 8 16


> Is __builtin_clzll available on all platforms?

Yes, we emit calls to this built-in unconditionally in the Fortran front-end, and it has caused no trouble.


FX

Re: __builtin_clzll and uintmax_t

[Marc Glisse]

Coucou FX,

On Sat, 5 Mar 2011, FX wrote:

> uintmax_t is the largest of the standard unsigned C types, so it cannot be larger than unsigned long long.

That's a gcc property then. The C99 standard only guarantees that 
uintmax_t is at least as large as unsigned long long, but it is allowed to 
be some other larger type:

"The following type designates an unsigned integer type capable of 
representing any value of any unsigned integer type: uintmax_t"


> On x86_64, for example:
>
>> #include <stdio.h>
>> #include <stdint.h>
>>
>> int main (void)
>> {
>>   printf ("%lu ", sizeof (uintmax_t));
>>   printf ("%lu ", sizeof (int));
>>   printf ("%lu ", sizeof (long int));
>>   printf ("%lu ", sizeof (long long int));
>>   printf ("%lu\n", sizeof (__int128));
>> }
>
> gives : 8 4 8 8 16

I am not sure how legal that is. __int128 is an extended signed integer 
type, and thus the statement about intmax_t should apply to it as well. So 
gcc is just pretending that __int128 is not really there.

>> Is __builtin_clzll available on all platforms?
>
> Yes, we emit calls to this built-in unconditionally in the Fortran 
> front-end, and it has caused no trouble.

Thank you, that's the best guarantee I could ask for about the existence 
of __builtin_clzll.

-- 
Marc Glisse

Re: __builtin_clzll and uintmax_t

[Jakub Jelinek]

On Sun, Mar 06, 2011 at 09:56:52AM +0100, Marc Glisse wrote:
> >uintmax_t is the largest of the standard unsigned C types, so it cannot be larger than unsigned long long.
> 
> That's a gcc property then. The C99 standard only guarantees that
> uintmax_t is at least as large as unsigned long long, but it is
> allowed to be some other larger type:

Yeah, it could be larger than unsigned long long.
On no target GCC supports currently it is larger than long long though currently.
Just
grep INTMAX_TYPE gcc/{,config/,config/*/}*.h
to see it.

> >On x86_64, for example:
> >
> >>#include <stdio.h>
> >>#include <stdint.h>
> >>
> >>int main (void)
> >>{
> >>  printf ("%lu ", sizeof (uintmax_t));
> >>  printf ("%lu ", sizeof (int));
> >>  printf ("%lu ", sizeof (long int));
> >>  printf ("%lu ", sizeof (long long int));
> >>  printf ("%lu\n", sizeof (__int128));
> >>}
> >
> >gives : 8 4 8 8 16
> 
> I am not sure how legal that is. __int128 is an extended signed
> integer type, and thus the statement about intmax_t should apply to
> it as well. So gcc is just pretending that __int128 is not really
> there.

It is also an ABI issue, you can't change what uintmax_t was
once you use some particular type in an ABI.

What you could do is use __builtin_clzll if sizeof (uintmax_t) == sizeof (unsigned long long),
for sizeof (uintmax_t) == 2 * sizeof (unsigned long long) perhaps use

int
clzmax (uintmax_t x)
{
  const union
    {
      uintmax_t ll;
#if __BYTE_ORDER__ != __ORDER_LITTLE_ENDIAN__
      struct { unsigned long long high, low; } s;
#else
      struct { unsigned long long low, high; } s;
#endif
    } uu = { .ll = x };
  uintmax_t word;
  unsigned long long add;

  if (uu.s.high)
    word = uu.s.high, add = 0;
  else
    word = uu.s.low, add = sizeof (unsigned long long) * __CHAR_BIT__;

  return __builtin_clzll (word) + add;
}

and give up for other cases.

	Jakub

Re: __builtin_clzll and uintmax_t

[Joern Rennecke]

Quoting Jakub Jelinek <jakub@redhat.com>:

> On Sun, Mar 06, 2011 at 09:56:52AM +0100, Marc Glisse wrote:
>> >uintmax_t is the largest of the standard unsigned C types, so it   
>> cannot be larger than unsigned long long.
>>
>> That's a gcc property then. The C99 standard only guarantees that
>> uintmax_t is at least as large as unsigned long long, but it is
>> allowed to be some other larger type:
>
> Yeah, it could be larger than unsigned long long.
> On no target GCC supports currently it is larger than long long   
> though currently.

But it's not too far out that a future target might have that.
E.g. if the arc/mxp toolchain was revived, with the 128 bit word with
of the mxp, it would be natural to have a named integer type for 128bit.
Right now, the branch has 16 bit short, 16 or 32 bit int, 32 bit long,
64 bit long long, and an anonymous 128 bit type to handle words.
(The preferred size to compute addresses, loop counters and
  vectorizable integers is 16 bit.)

Even if the GCC mxp port never gets integrated in mainline, I think
it is likely that in the future, we'll have a GPU port or CPU vector
extension support with an intmax_t type wider than long long.

> It is also an ABI issue, you can't change what uintmax_t was
> once you use some particular type in an ABI.

As long as you define the libc view of the kernel interface appropriately,
you should be able to multilib around this issue.

Bonus points if anyone implements a scheme so that only those object files
for which it matters need to exist in multiple versions.
I.e. if we don't have any function argument / return value, aggregate member,
or debug info involving intmax_t / unitmax_t, we should be able to use the
same object file with code of either intmax_t size.

At any rate, for embedded and/or new targets, ABI churn is often
more acceptable.

> What you could do is use __builtin_clzll if sizeof (uintmax_t) ==  
> sizeof > (unsigned long long),
> for sizeof (uintmax_t) == 2 * sizeof (unsigned long long) perhaps use

> int
> clzmax (uintmax_t x)
> {
...
> and give up for other cases.

The main point is to have the code fail to compile if the size is not
supported, and implement this abstraction in one place, so handling of
new sizes can be added in an efficient manner.

In fact, without the ability to test the 2*long long code, I would
prefer the code to be written so that the compiler will complain initially
when this code is used, so people have to explicitly enable it to be used,
and are thus aware of what might not quite work.

__builtin_clzll and uintmax_t

[Marc Glisse]

Hello,

the following question came up for a libstdc++ patch. We have a variable 
of type uintmax_t and want to count the leading zeros. Can we just call 
__builtin_clzll on it?

In particular, can uintmax_t be larger than unsigned long long in gcc? Is 
__builtin_clzll available on all platforms? Is there a good reason to use 
__builtin_clzl instead on platforms where long and long long have the same 
size?

In case it matters, this is strictly for compile-time computations 
(templates, constexpr).

-- 
Marc Glisse