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

[Emanuel Peter]

On Fri, 14 Feb 2025 13:44:40 GMT, Tobias Hartmann <thartmann at openjdk.org> wrote:

>> Jasmine Karthikeyan has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   Improve explanation of logic
>
> Ah, right, makes sense. Thanks for checking, Emanuel. And nice to see that limitation being addressed.

I looked at @TobiHartmann Examples. I rewrote them a little, to make things more apparent.


public class TestByte {

    static byte[] vals = new byte[1024];
    static byte[] results = new byte[1024];

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

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

Running it like this:

java -Xbatch -XX:-TieredCompilation -XX:UseAVX=2 -XX:CompileCommand=compileonly,TestByte::test -XX:+TraceNewVectors TestByte.java 
CompileCommand: compileonly TestByte.test bool compileonly = true
TraceNewVectors [AutoVectorization]:  1190  LoadVector  === 943 1080 1055  [[ ]]  @byte[int:>=0] (java/lang/Cloneable,java/io/Serializable):NotNull:exact+any *, idx=7; mismatched #vectory<B,32> (does not depend only on test, unknown control)
TraceNewVectors [AutoVectorization]:  1191  CountLeadingZerosV  === _ 1190  [[ ]]  #vectory<B,32>
TraceNewVectors [AutoVectorization]:  1192  StoreVector  === 1079 1080 1021 1191  [[ ]]  @byte[int:>=0] (java/lang/Cloneable,java/io/Serializable):NotNull:exact+any *, idx=7; mismatched  Memory: @byte[int:>=0] (java/lang/Cloneable,java/io/Serializable):NotNull:exact+any *, idx=7;
Exception in thread "main" java.lang.RuntimeException: Wrong result: 8 at 24
	at TestByte.main(TestByte.java:18)

See the error message: `Wrong result: 8 at 24`, we get `8` instead of the expected `32`.

We see that we have a `LoadVector` of `bytes` going directly into `CountLeadingZerosV` for `bytes`, and the result is stored as `bytes` with `StoreVector`.

But this is not ok, because `CountLeadingZerosV` for `bytes` will have a different result, it only operates on `8 bytes`, and so if it sees a `zero = 0`, it sees only `8` leading zeros. But we called `Integer.numberOfLeadingZeros`, which expects to operate on `32 bit` integers, where a zero has `32` leading zeros.

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

Let's do the same with `shorts`:

public class TestShort {

    static short[] vals = new short[1024];
    static short[] results = new short[1024];

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

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

And we get:

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  CountLeadingZerosV  === _ 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 16 at 12
	at TestShort.main(TestShort.java:41)

Here we get `16` leading zeros because a `short` has `16` bits, rather than the expected `32` from `Integer.numberOfLeadingZeros`. Again, because `CountLeadingZerosV` for `short` operates on `shorts` and not `ints`.

How did we not catch this with testing. I mean this is so trivial to catch with any vectorizing example 🙈

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

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