[Qemu-devel] [PATCH v2] utils: Add pow2ceil()

[Qemu-devel] [PATCH v2] utils: Add pow2ceil()

[Alexey Kardashevskiy]

This adds a helper to get closest bigger power-of-two value.

Signed-off-by: Alexey Kardashevskiy <aik@ozlabs.ru>
---
Changes:
v2:
* s/up_pow_of_two/pow2ceil/
---
 include/qemu-common.h | 2 ++
 util/cutils.c         | 9 +++++++++
 2 files changed, 11 insertions(+)

diff --git a/include/qemu-common.h b/include/qemu-common.h
index 644b46d..ae29748 100644
--- a/include/qemu-common.h
+++ b/include/qemu-common.h
@@ -417,6 +417,8 @@ static inline bool is_power_of_2(uint64_t value)
 
 /* round down to the nearest power of 2*/
 int64_t pow2floor(int64_t value);
+/* round up to the nearest power of 2*/
+int64_t pow2ceil(int64_t value);
 
 #include "qemu/module.h"
 
diff --git a/util/cutils.c b/util/cutils.c
index dbe7412..ecaa440 100644
--- a/util/cutils.c
+++ b/util/cutils.c
@@ -483,6 +483,15 @@ int64_t pow2floor(int64_t value)
     return value;
 }
 
+/* round up to the nearest power of 2*/
+int64_t pow2ceil(int64_t value)
+{
+    if (!is_power_of_2(value)) {
+        value = 0x8000000000000000ULL >> (clz64(value) - 1);
+    }
+    return value;
+}
+
 /*
  * Implementation of  ULEB128 (http://en.wikipedia.org/wiki/LEB128)
  * Input is limited to 14-bit numbers
-- 
2.0.0

Re: [Qemu-devel] [PATCH v2] utils: Add pow2ceil()

[Markus Armbruster]

Alexey Kardashevskiy <aik@ozlabs.ru> writes:

> This adds a helper to get closest bigger power-of-two value.
>
> Signed-off-by: Alexey Kardashevskiy <aik@ozlabs.ru>
> ---
> Changes:
> v2:
> * s/up_pow_of_two/pow2ceil/
> ---
>  include/qemu-common.h | 2 ++
>  util/cutils.c         | 9 +++++++++
>  2 files changed, 11 insertions(+)
>
> diff --git a/include/qemu-common.h b/include/qemu-common.h
> index 644b46d..ae29748 100644
> --- a/include/qemu-common.h
> +++ b/include/qemu-common.h
> @@ -417,6 +417,8 @@ static inline bool is_power_of_2(uint64_t value)
>  
>  /* round down to the nearest power of 2*/
>  int64_t pow2floor(int64_t value);
> +/* round up to the nearest power of 2*/
> +int64_t pow2ceil(int64_t value);
>  
>  #include "qemu/module.h"
>  
> diff --git a/util/cutils.c b/util/cutils.c
> index dbe7412..ecaa440 100644
> --- a/util/cutils.c
> +++ b/util/cutils.c
> @@ -483,6 +483,15 @@ int64_t pow2floor(int64_t value)
>      return value;
>  }
>  
> +/* round up to the nearest power of 2*/
> +int64_t pow2ceil(int64_t value)
> +{
> +    if (!is_power_of_2(value)) {
> +        value = 0x8000000000000000ULL >> (clz64(value) - 1);
> +    }
> +    return value;
> +}
> +
>  /*
>   * Implementation of  ULEB128 (http://en.wikipedia.org/wiki/LEB128)
>   * Input is limited to 14-bit numbers

pow2ceil(INT64_MIN) = INT64_MIN.  Should be 1.

pow2ceil(INT64_MAX) = INT64_MIN.  Garbage.

Related: "round down to the nearest power of 2" is defined only for x >
0, but our pow2floor(x) happily returns garbage then.

In particular we return 0x8000000000000000ULL >> 64 when value is 0,.
Undefined behavior.

Here's how I'd do these functions:

int64_t pow2floor(int64_t value)
{
    assert(value > 0);
    return 0x8000000000000000u >> clz64(value);
}

int64_t pow2ceil(int64_t value)
{
    assert(value <= 0x4000000000000000)
    if (value <= 1)
	return 1;
    return 0x8000000000000000u >> (clz64(value - 1) - 1);
}

Re: [Qemu-devel] [PATCH v2] utils: Add pow2ceil()

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 989 bytes --]

On 02/23/2015 06:59 AM, Markus Armbruster wrote:
> Alexey Kardashevskiy <aik@ozlabs.ru> writes:
> 
>> This adds a helper to get closest bigger power-of-two value.
>>

> 
> Here's how I'd do these functions:
> 
> int64_t pow2floor(int64_t value)
> {
>     assert(value > 0);
>     return 0x8000000000000000u >> clz64(value);
> }

Needs to be 0x8000000000000000ull for 32-bit machines to compile correctly.

Why is the parameter int64_t?  Wouldn't it be more useful to have:

uint64_t pow2floor(uint64_t value)

> 
> int64_t pow2ceil(int64_t value)
> {

Again, why allow signed inputs?

>     assert(value <= 0x4000000000000000)
>     if (value <= 1)
> 	return 1;

In particular, this slams all negative values to a result of 1, which
doesn't necessarily make sense.

>     return 0x8000000000000000u >> (clz64(value - 1) - 1);
> }
> 
> 
> 

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH v2] utils: Add pow2ceil()

[Markus Armbruster]

Eric Blake <eblake@redhat.com> writes:

> On 02/23/2015 06:59 AM, Markus Armbruster wrote:
>> Alexey Kardashevskiy <aik@ozlabs.ru> writes:
>> 
>>> This adds a helper to get closest bigger power-of-two value.
>>>
>
>> 
>> Here's how I'd do these functions:
>> 
>> int64_t pow2floor(int64_t value)
>> {
>>     assert(value > 0);
>>     return 0x8000000000000000u >> clz64(value);
>> }
>
> Needs to be 0x8000000000000000ull for 32-bit machines to compile correctly.

Why?

> Why is the parameter int64_t?  Wouldn't it be more useful to have:
>
> uint64_t pow2floor(uint64_t value)

Crossed my mind, too.  However, the existing callers pass *signed*
arguments.

>> int64_t pow2ceil(int64_t value)
>> {
>
> Again, why allow signed inputs?
>
>>     assert(value <= 0x4000000000000000)
>>     if (value <= 1)
>> 	return 1;
>
> In particular, this slams all negative values to a result of 1, which
> doesn't necessarily make sense.

It implements a straightforward contract: return the smallest power of
two greater or equal to the argument.  The function's domain is the set
of int64_t arguments where this value can be represented in int64_t,
i.e. [-2^63..2^62].

Feel free to suggest a more sensible contract.

>>     return 0x8000000000000000u >> (clz64(value - 1) - 1);
>> }
>> 
>> 
>> 

Re: [Qemu-devel] [PATCH v2] utils: Add pow2ceil()

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 1942 bytes --]

On 02/23/2015 10:40 AM, Markus Armbruster wrote:

>>> int64_t pow2floor(int64_t value)
>>> {
>>>     assert(value > 0);
>>>     return 0x8000000000000000u >> clz64(value);
>>> }
>>
>> Needs to be 0x8000000000000000ull for 32-bit machines to compile correctly.
> 
> Why?

Because 0x8000000000000000u is only required to be a 'long', and on
32-bit machines, your constant would overflow long.  See, for example,
commit 5cb6be2ca.  You NEED the 'll' suffix to ensure that the compiler
doesn't reject the constant as an overflow.

> 
>> Why is the parameter int64_t?  Wouldn't it be more useful to have:
>>
>> uint64_t pow2floor(uint64_t value)
> 
> Crossed my mind, too.  However, the existing callers pass *signed*
> arguments.

I guess it means auditing callers either way.

> 
>>> int64_t pow2ceil(int64_t value)
>>> {
>>
>> Again, why allow signed inputs?
>>
>>>     assert(value <= 0x4000000000000000)
>>>     if (value <= 1)
>>> 	return 1;
>>
>> In particular, this slams all negative values to a result of 1, which
>> doesn't necessarily make sense.
> 
> It implements a straightforward contract: return the smallest power of
> two greater or equal to the argument.  The function's domain is the set
> of int64_t arguments where this value can be represented in int64_t,
> i.e. [-2^63..2^62].
> 
> Feel free to suggest a more sensible contract.

But why should I claim that the nearest power of 2 greater than -3 is
positive 1, when I could argue that it should instead be -2 (nearest
positive or negative power of 2 rounding towards +inf) or -4 (nearest
positive or negative power of 2 rounding away from 0)?  Since there are
multiple potential contracts once negative values are involved, I find
it easier to just make the contract require a positive input to begin with.

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH v2] utils: Add pow2ceil()

[Markus Armbruster]

Eric Blake <eblake@redhat.com> writes:

> On 02/23/2015 10:40 AM, Markus Armbruster wrote:
>
>>>> int64_t pow2floor(int64_t value)
>>>> {
>>>>     assert(value > 0);
>>>>     return 0x8000000000000000u >> clz64(value);
>>>> }
>>>
>>> Needs to be 0x8000000000000000ull for 32-bit machines to compile correctly.
>> 
>> Why?
>
> Because 0x8000000000000000u is only required to be a 'long', and on
> 32-bit machines, your constant would overflow long.  See, for example,
> commit 5cb6be2ca.  You NEED the 'll' suffix to ensure that the compiler
> doesn't reject the constant as an overflow.

Not true.

If you're not interested in whether it is true or not, only what suffix
we should use, skip to "Commit 5cb6be2ca".

If you trust me as a language lawyer, you can skip over my experiment to
"Why is this so".

---<lit.c>---
#include <stdio.h>

#define HAS_LIT_TYPE(lit, type) \
    __builtin_types_compatible_p(type, typeof(lit))

#define LIT_TYPE_NAME1(lit, type) \
    (HAS_LIT_TYPE(lit, type) ? #type : NULL)

#define LIT_INT_TYPE_NAME(lit)			\
    (LIT_TYPE_NAME1(lit, int)			\
     ?: LIT_TYPE_NAME1(lit, unsigned)		\
     ?: LIT_TYPE_NAME1(lit, long)		\
     ?: LIT_TYPE_NAME1(lit, unsigned long)	\
     ?: LIT_TYPE_NAME1(lit, long long)		\
     ?: LIT_TYPE_NAME1(lit, unsigned long long) \
     ?: "unknown")

#define PR_LIT_INT_TYPE(lit) \
    printf("%-24s %s\n", #lit, LIT_INT_TYPE_NAME(lit));

int
main(void)
{
    PR_LIT_INT_TYPE(0x8000000000000000);
    PR_LIT_INT_TYPE(0x8000000000000000u);
    PR_LIT_INT_TYPE(0x8000000000000000ull);
    return 0;
}
---<End of lit.c>---

$ gcc -o lit64 -g -O -Wall lit.c
$ gcc -m32 -o lit32 -g -O -Wall lit.c
$ ./lit32
0x8000000000000000       unsigned long long
0x8000000000000000u      unsigned long long
0x8000000000000000ull    unsigned long long
$ ./lit64
0x8000000000000000       unsigned long
0x8000000000000000u      unsigned long
0x8000000000000000ull    unsigned long long

Why is this so?  The type of an integer constant depends on its value,
its suffix, and whether it's decimal or not.  ISO/IEC 9899:1999
§6.4.4.1:

       [#5]  The  type  of  an integer constant is the first of the
       corresponding list in which its value can be represented.

                    |                       | Octal or Hexadecimal
       Suffix       |   Decimal Constant    |       Constant
       -------------+-----------------------+-----------------------
       none         |int                    |int
                    |long int               |unsigned int
                    |long long int          |long int
                    |                       |unsigned long int
                    |                       |long long int
                    |                       |unsigned long long int
       -------------+-----------------------+-----------------------
       u or U       |unsigned int           |unsigned int
                    |unsigned long int      |unsigned long int
                    |unsigned long long int |unsigned long long int
       -------------+-----------------------+-----------------------
       l or L       |long int               |long int
                    |long long int          |unsigned long int
                    |                       |long long int
                    |                       |unsigned long long int
       -------------+-----------------------+-----------------------
       Both u or U  |unsigned long int      |unsigned long int
       and l or L   |unsigned long long int |unsigned long long int
       -------------+-----------------------+-----------------------
       ll or LL     |long long int          |long long int
                    |                       |unsigned long long int
       -------------+-----------------------+-----------------------
       Both u or U  |unsigned long long int |unsigned long long int
       and ll or LL |                       |

A hexadecimal constant without a suffix can have a signed type, which
can surprise the unwary programmer.  But if the suffix contains u, the
constant has an unsigned type.

0x8000000000000000u needs 64 bits to be representable.  Its type is the
narrowest of unsigned, unsigned long, unsigned long long that can
represent it.

Real-world examples:

    data model | int  long  long long | type of 0x8000000000000000u
    LLP64      |  32    32         64 | unsigned long long
    LP64       |  32    64         64 | unsigned long
    IILP64     |  64    64         64 | unsigned

Commit 5cb6be2ca fixes up hexadecimal literals without a suffix.  For
what it's worth, I can't reproduce the warning with gcc -m32.  Whether
and where u-suffixed literals trigger the warning I can't say.

If they do, we'll want whatever suffix it takes.

If they don't, you could argue for suffix ull to avoid ambiguity.
Matter of taste.  I don't particularly care, but the reason is style,
not "won't compile".

>>> Why is the parameter int64_t?  Wouldn't it be more useful to have:
>>>
>>> uint64_t pow2floor(uint64_t value)
>> 
>> Crossed my mind, too.  However, the existing callers pass *signed*
>> arguments.
>
> I guess it means auditing callers either way.
>
>>>> int64_t pow2ceil(int64_t value)
>>>> {
>>>
>>> Again, why allow signed inputs?
>>>
>>>>     assert(value <= 0x4000000000000000)
>>>>     if (value <= 1)
>>>> 	return 1;
>>>
>>> In particular, this slams all negative values to a result of 1, which
>>> doesn't necessarily make sense.
>> 
>> It implements a straightforward contract: return the smallest power of
>> two greater or equal to the argument.  The function's domain is the set
>> of int64_t arguments where this value can be represented in int64_t,
>> i.e. [-2^63..2^62].
>> 
>> Feel free to suggest a more sensible contract.
>
> But why should I claim that the nearest power of 2 greater than -3 is
> positive 1, when I could argue that it should instead be -2 (nearest
> positive or negative power of 2 rounding towards +inf) or -4 (nearest
> positive or negative power of 2 rounding away from 0)?  Since there are
> multiple potential contracts once negative values are involved, I find
> it easier to just make the contract require a positive input to begin with.

-2 is not a power of two!  Ask any mathematician :)

"Round down to the nearest power of 2" is a pefectly obvious function
contract.  The function's domain is the representable numbers >= 1.

Same for "round up", domain is representable numbers <= largest
representable power of two.

My implementations assert the actual argument is in the domain.

If you want to change the two functions' contracts to return the nearest
positive or negative power of two rounding towards whatever, I don't
mind as long as you explicitly write it into their contract, because it
sure isn't obvious from the function names.

If you want to change the functions' parameter and return type to
uint64_t, I don't mind, either.  However, you'll have to handle domain
errors in both functions all the same.

An audit of the callers may be advisable regardless of what we do.

Re: [Qemu-devel] [PATCH v2] utils: Add pow2ceil()

[Peter Maydell]

On 24 February 2015 at 18:39, Markus Armbruster <armbru@redhat.com> wrote:
> Eric Blake <eblake@redhat.com> writes:
>> Because 0x8000000000000000u is only required to be a 'long', and on
>> 32-bit machines, your constant would overflow long.  See, for example,
>> commit 5cb6be2ca.  You NEED the 'll' suffix to ensure that the compiler
>> doesn't reject the constant as an overflow.
>
> Not true.

You need ULL because certain versions of gcc will warn if you do
not. (I have a feeling this includes the elderly gcc I currently
use for mingw builds.) You could argue that this is a gcc bug, and
somebody probably did given that newer gcc don't warn about this.
However we should always use ULL (or LL) for 64-bit constants,
to avoid confusing those versions of gcc.

thanks
-- PMM

Re: [Qemu-devel] [PATCH v2] utils: Add pow2ceil()

[Markus Armbruster]

Peter Maydell <peter.maydell@linaro.org> writes:

> On 24 February 2015 at 18:39, Markus Armbruster <armbru@redhat.com> wrote:
>> Eric Blake <eblake@redhat.com> writes:
>>> Because 0x8000000000000000u is only required to be a 'long', and on
>>> 32-bit machines, your constant would overflow long.  See, for example,
>>> commit 5cb6be2ca.  You NEED the 'll' suffix to ensure that the compiler
>>> doesn't reject the constant as an overflow.
>>
>> Not true.
>
> You need ULL because certain versions of gcc will warn if you do
> not. (I have a feeling this includes the elderly gcc I currently
> use for mingw builds.) You could argue that this is a gcc bug, and
> somebody probably did given that newer gcc don't warn about this.
> However we should always use ULL (or LL) for 64-bit constants,
> to avoid confusing those versions of gcc.

Working around compiler bugs is a perfectly good reason to ull big
constants.

Re: [Qemu-devel] [PATCH v2] utils: Add pow2ceil()

[Alexey Kardashevskiy]

On 02/24/2015 12:59 AM, Markus Armbruster wrote:
> Alexey Kardashevskiy <aik@ozlabs.ru> writes:
>
>> This adds a helper to get closest bigger power-of-two value.
>>
>> Signed-off-by: Alexey Kardashevskiy <aik@ozlabs.ru>
>> ---
>> Changes:
>> v2:
>> * s/up_pow_of_two/pow2ceil/
>> ---
>>   include/qemu-common.h | 2 ++
>>   util/cutils.c         | 9 +++++++++
>>   2 files changed, 11 insertions(+)
>>
>> diff --git a/include/qemu-common.h b/include/qemu-common.h
>> index 644b46d..ae29748 100644
>> --- a/include/qemu-common.h
>> +++ b/include/qemu-common.h
>> @@ -417,6 +417,8 @@ static inline bool is_power_of_2(uint64_t value)
>>
>>   /* round down to the nearest power of 2*/
>>   int64_t pow2floor(int64_t value);
>> +/* round up to the nearest power of 2*/
>> +int64_t pow2ceil(int64_t value);
>>
>>   #include "qemu/module.h"
>>
>> diff --git a/util/cutils.c b/util/cutils.c
>> index dbe7412..ecaa440 100644
>> --- a/util/cutils.c
>> +++ b/util/cutils.c
>> @@ -483,6 +483,15 @@ int64_t pow2floor(int64_t value)
>>       return value;
>>   }
>>
>> +/* round up to the nearest power of 2*/
>> +int64_t pow2ceil(int64_t value)
>> +{
>> +    if (!is_power_of_2(value)) {
>> +        value = 0x8000000000000000ULL >> (clz64(value) - 1);
>> +    }
>> +    return value;
>> +}
>> +
>>   /*
>>    * Implementation of  ULEB128 (http://en.wikipedia.org/wiki/LEB128)
>>    * Input is limited to 14-bit numbers
>
> pow2ceil(INT64_MIN) = INT64_MIN.  Should be 1.
>
> pow2ceil(INT64_MAX) = INT64_MIN.  Garbage.
>
> Related: "round down to the nearest power of 2" is defined only for x >
> 0, but our pow2floor(x) happily returns garbage then.
>
> In particular we return 0x8000000000000000ULL >> 64 when value is 0,.
> Undefined behavior.
>
> Here's how I'd do these functions:
>
> int64_t pow2floor(int64_t value)
> {
>      assert(value > 0);
>      return 0x8000000000000000u >> clz64(value);
> }
>
> int64_t pow2ceil(int64_t value)
> {
>      assert(value <= 0x4000000000000000)
>      if (value <= 1)
> 	return 1;
>      return 0x8000000000000000u >> (clz64(value - 1) - 1);
> }
>


I've read the whole thread, that was cool :)

Do you want me to repost your versions as a patch? I do not feel I should 
since it is totally yours but I can :)


-- 
Alexey

Re: [Qemu-devel] [PATCH v2] utils: Add pow2ceil()

[Markus Armbruster]

Alexey Kardashevskiy <aik@ozlabs.ru> writes:

> On 02/24/2015 12:59 AM, Markus Armbruster wrote:
>> Alexey Kardashevskiy <aik@ozlabs.ru> writes:
>>
>>> This adds a helper to get closest bigger power-of-two value.
>>>
>>> Signed-off-by: Alexey Kardashevskiy <aik@ozlabs.ru>
>>> ---
>>> Changes:
>>> v2:
>>> * s/up_pow_of_two/pow2ceil/
>>> ---
>>>   include/qemu-common.h | 2 ++
>>>   util/cutils.c         | 9 +++++++++
>>>   2 files changed, 11 insertions(+)
>>>
>>> diff --git a/include/qemu-common.h b/include/qemu-common.h
>>> index 644b46d..ae29748 100644
>>> --- a/include/qemu-common.h
>>> +++ b/include/qemu-common.h
>>> @@ -417,6 +417,8 @@ static inline bool is_power_of_2(uint64_t value)
>>>
>>>   /* round down to the nearest power of 2*/
>>>   int64_t pow2floor(int64_t value);
>>> +/* round up to the nearest power of 2*/
>>> +int64_t pow2ceil(int64_t value);
>>>
>>>   #include "qemu/module.h"
>>>
>>> diff --git a/util/cutils.c b/util/cutils.c
>>> index dbe7412..ecaa440 100644
>>> --- a/util/cutils.c
>>> +++ b/util/cutils.c
>>> @@ -483,6 +483,15 @@ int64_t pow2floor(int64_t value)
>>>       return value;
>>>   }
>>>
>>> +/* round up to the nearest power of 2*/
>>> +int64_t pow2ceil(int64_t value)
>>> +{
>>> +    if (!is_power_of_2(value)) {
>>> +        value = 0x8000000000000000ULL >> (clz64(value) - 1);
>>> +    }
>>> +    return value;
>>> +}
>>> +
>>>   /*
>>>    * Implementation of  ULEB128 (http://en.wikipedia.org/wiki/LEB128)
>>>    * Input is limited to 14-bit numbers
>>
>> pow2ceil(INT64_MIN) = INT64_MIN.  Should be 1.
>>
>> pow2ceil(INT64_MAX) = INT64_MIN.  Garbage.
>>
>> Related: "round down to the nearest power of 2" is defined only for x >
>> 0, but our pow2floor(x) happily returns garbage then.
>>
>> In particular we return 0x8000000000000000ULL >> 64 when value is 0,.
>> Undefined behavior.
>>
>> Here's how I'd do these functions:
>>
>> int64_t pow2floor(int64_t value)
>> {
>>      assert(value > 0);
>>      return 0x8000000000000000u >> clz64(value);
>> }
>>
>> int64_t pow2ceil(int64_t value)
>> {
>>      assert(value <= 0x4000000000000000)
>>      if (value <= 1)
>> 	return 1;
>>      return 0x8000000000000000u >> (clz64(value - 1) - 1);
>> }
>>
>
>
> I've read the whole thread, that was cool :)

I indulged in a bit of language lawyering, glad you liked it.

> Do you want me to repost your versions as a patch? I do not feel I
> should since it is totally yours but I can :)

I'll post a patch fixing the existing pow2floor().  I prefer not to add
pow2ceil() without a user.  If you have one, I suggest you do your
patches on top of mine.

Re: [Qemu-devel] [PATCH v2] utils: Add pow2ceil()

[Richard Henderson]

On 02/25/2015 02:45 AM, Markus Armbruster wrote:
> return 0x8000000000000000u >> (clz64(value - 1) - 1);

I realize this was weeks ago, but it would certainly be preferable to shift a
small constant left than a large constant right.

Most RISC machines can't form 0x8000000000000000ull without loading 1 and then
left shifting to start with.  So end the end you're better off with

  return 1ull << (63 - clz64(value));


r~

Re: [Qemu-devel] [PATCH v2] utils: Add pow2ceil()

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 823 bytes --]

On 03/12/2015 09:29 AM, Richard Henderson wrote:
> On 02/25/2015 02:45 AM, Markus Armbruster wrote:
>> return 0x8000000000000000u >> (clz64(value - 1) - 1);
> 
> I realize this was weeks ago, but it would certainly be preferable to shift a
> small constant left than a large constant right.
> 
> Most RISC machines can't form 0x8000000000000000ull without loading 1 and then
> left shifting to start with.  So end the end you're better off with
> 
>   return 1ull << (63 - clz64(value));

Since the value being shifted is a constant either way, can't gcc figure
out the equivalence and generate the optimal code to begin with?  If
not, should it be opened as a gcc bug for potential optimization?

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH v2] utils: Add pow2ceil()

[Richard Henderson]

On 03/12/2015 09:45 AM, Eric Blake wrote:
> On 03/12/2015 09:29 AM, Richard Henderson wrote:
>> On 02/25/2015 02:45 AM, Markus Armbruster wrote:
>>> return 0x8000000000000000u >> (clz64(value - 1) - 1);
>>
>> I realize this was weeks ago, but it would certainly be preferable to shift a
>> small constant left than a large constant right.
>>
>> Most RISC machines can't form 0x8000000000000000ull without loading 1 and then
>> left shifting to start with.  So end the end you're better off with
>>
>>   return 1ull << (63 - clz64(value));
> 
> Since the value being shifted is a constant either way, can't gcc figure
> out the equivalence and generate the optimal code to begin with?  If
> not, should it be opened as a gcc bug for potential optimization?

With the simplest of tests,

unsigned long f(unsigned long x)
{
  return 1UL << (63 - x);
}

unsigned long g(unsigned long x)
{
  return 0x8000000000000000ul >> x;
}

the code is of similar size: 3 operations each.

But if you throw in the whole operation

  1ul << (63 - (__builtin_clzl(x - 1) - 1))
vs
  0x8...0ul >> (__builtin_clzl(x - 1) - 1)

then gcc is able to fold away one of the instructions and the 1UL alternative
is shorter.


r~

Re: [Qemu-devel] [PATCH v2] utils: Add pow2ceil()

[Markus Armbruster]

Richard Henderson <rth@twiddle.net> writes:

> On 02/25/2015 02:45 AM, Markus Armbruster wrote:
>> return 0x8000000000000000u >> (clz64(value - 1) - 1);
>
> I realize this was weeks ago, but it would certainly be preferable to shift a
> small constant left than a large constant right.
>
> Most RISC machines can't form 0x8000000000000000ull without loading 1 and then
> left shifting to start with.  So end the end you're better off with
>
>   return 1ull << (63 - clz64(value));

I intend to respin my own "[PATCH 0/2] Proactive pow2floor() fix, and
dead code removal", and I'll keep your advice in mind for that.