RFR: 8234331: Add robust and optimized utility for rounding up to next power of two+

[Claes Redestad]

On 2019-12-05 11:26, Thomas Stüfe wrote:
> Hi Claes,
> 
> this looks nice, thank you for your work. Only minor stuff remains, 
> mostly matters of taste. Feel free to ignore them. The patch is already 
> fine as it is for me.
> 
> With your latest patch, AIX still works.

Great!

> 
> ---
> 
> http://cr.openjdk.java.net/~redestad/8234331/open.04/src/hotspot/share/utilities/count_leading_zeros.hpp.udiff.html
> 
> Taste matter: I find the return type for count_leading_zeros as uint32_t 
> oddly specific. Instinctively I would have choosen int or unsigned. The 
> gcc buildins all return int.

No particular reason.

> 
> ---
> 
> Question, why do we treat signed numbers of 8 and 16 bits different wrt 
> to values < 0?
> 
> if you leave behavior as it is, could you please adjust the comment:
> 
>   // Return the number of leading zeros in x, e.g. the zero-based index
>   // of the most significant set bit in x.  Undefined for 0.
> + // For signed numbers whose size is < 32bit, function will
> + // return 0 for values < 0.

Such a comment is a bit redundant since count_leading_zeros will return
0 for any negative input. Maybe we should spell that out more clearly,
though.

The special cases avoided issues with sign extension when upcasting,
e.g, casting int8_t -1 to unsigned returns 0xFFFFFFFF, so
__builtin_clz((int8_t)-1) returns 0, which then messes up the manual
adjustment. But this can be further simplified by masking, avoiding
an extra branch:

template <typename T> struct CountLeadingZerosImpl<T, 1> {
   static uint32_t doit(T v) {
     return __builtin_clz((uint32_t)v & 0xFF) - 24u;
   }
};

template <typename T> struct CountLeadingZerosImpl<T, 2> {
   static uint32_t doit(T v) {
     return __builtin_clz((uint32_t)v & 0xFFFF) - 16u;
   }
};

> 
> ----
> 
> Taste matter: Windows, 64bit version for x86: You could call your own 
> count_leading_zeros<uint32_t>, instead of calling _BitScanReverse.

Sure.

> 
> ----
> 
> http://cr.openjdk.java.net/~redestad/8234331/open.04/test/hotspot/gtest/utilities/test_powerOfTwo.cpp.html
> 
> In the test for next_up, can we have, for completeness sake, a test 
> which tests that with any valid input pow2 the result is the next pow2?
> 
> --- a/test/hotspot/gtest/utilities/test_powerOfTwo.cpp  Thu Dec 05 
> 02:28:58 2019 +0100
> +++ b/test/hotspot/gtest/utilities/test_powerOfTwo.cpp  Thu Dec 05 
> 11:08:47 2019 +0100
> @@ -139,6 +139,11 @@
>       EXPECT_EQ(pow2, next_power_of_2(pow2 - 1))
>         << "value = " << pow2 - 1;
>     }
> +  // next(pow2) should return pow2 * 2
> +  for (T pow2 = T(1); pow2 < t_max_pow2 / 2; pow2 = pow2 * 2) {
> +    EXPECT_EQ(pow2 * 2, next_power_of_2(pow2))
> +      << "value = " << pow2;
> +  }

Fixed.

I also ran into an issue with use of std::numeric_limit<T>::max()
causing obscure issues on some platforms at some call sites (*cough*
Solaris), so I replaced those usages with a portable (but not very
efficient) version of that in place for the few assert/test uses:

http://cr.openjdk.java.net/~redestad/8234331/open.05

Testing: tier1-3, some ongoing

/Claes