RFR: 8349637: Integer.numberOfLeadingZeros outputs incorrectly in certain cases [v3]

[Emanuel Peter]

On Wed, 12 Feb 2025 19:45:34 GMT, Jasmine Karthikeyan <jkarthikeyan at openjdk.org> wrote:

>> Hi all,
>> This is a fix for a miscompile in the AVX2 implementation of `CountLeadingZerosV` for int types. Currently, the implementation turns ints into floats, in order to calculating the leading zeros based on the exponent part of the float. Unfortunately, floats can only accurately represent integers up to 2^24. After that, multiple integer values can map onto the same floating point value. The issue manifests when an int is converted to a floating point representation that is higher than it, crossing a bit boundary. As an example, `(float)0x01FFFFFF == (float)0x02000000`, but `lzcnt(0x01FFFFFF) == 7` and `lzcnt(0x02000000) == 6`. The values are incorrectly rounded up.
>> 
>> This patch fixes the issue by masking the input in the cases where it is larger than 2^24, to set the low bits to 0. Removing these bits prevents the accidental rounding behavior. I've added these cases to`TestNumberOfContinuousZeros`, and removed the set random seed so that it can produce random inputs to test with.
>> 
>> Reviews would be appreciated!
>
> Jasmine Karthikeyan has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Improve explanation of logic

Here the reproducer for `Integer.reverse` **truncation** issue.


public class TestShort {

    static short[] vals = new short[1024];
    static short[] results = new short[1024];
    static short v = (short)0x01234567;
    static short r = (short)Integer.reverse(v);

    public static void test() {
        for (int i = 0; i < 1024; ++i) {
            //results[i] = (short)Integer.numberOfLeadingZeros(vals[i]);
            //results[i] = (short)Integer.numberOfTrailingZeros(vals[i]);
            results[i] = (short)Integer.reverse(vals[i]);
        }
   }

    public static void main(String[] args) {
        for (int i = 0; i < 1024; ++i) {
            vals[i] = v;
        }
        for (int j = 0; j < 10_000; ++j) {
            test();
            for (int i = 0; i < 1024; ++i) {
                if (results[i] != r) throw new RuntimeException("Wrong result " + results[i] + " at " + i + " expected " + r);
            }
        }
    }
}



java -Xbatch -XX:-TieredCompilation -XX:UseAVX=2 -XX:CompileCommand=compileonly,TestShort::test -XX:+TraceNewVectors TestShort.java 
CompileCommand: compileonly TestShort.test bool compileonly = true
TraceNewVectors [AutoVectorization]:  980  LoadVector  === 813 885 864  [[ ]]  @short[int:>=0] (java/lang/Cloneable,java/io/Serializable):NotNull:exact+any *, idx=7; mismatched #vectory<S,16> (does not depend only on test, unknown control)
TraceNewVectors [AutoVectorization]:  981  ReverseV  === _ 980  [[ ]]  #vectory<S,16>
TraceNewVectors [AutoVectorization]:  982  StoreVector  === 882 885 866 981  [[ ]]  @short[int:>=0] (java/lang/Cloneable,java/io/Serializable):NotNull:exact+any *, idx=7; mismatched  Memory: @short[int:>=0] (java/lang/Cloneable,java/io/Serializable):NotNull:exact+any *, idx=7;
Exception in thread "main" java.lang.RuntimeException: Wrong result -6494 at 12 expected 0
	at TestShort.main(TestShort.java:48)


With `-Xint` this test passes.

-------------

PR Comment: https://git.openjdk.org/jdk/pull/23579#issuecomment-2659622652