OpenJ9's optimization for array operations issue

[TemporaryRepos]

Affected versions

We found a test case with execution problems. To facilitate analysis, we simplified the test case and the simplified class file can ben found at attachment.

Linux Ubuntu20.04

Java -version output under Linux

openjdk version "1.8.0_402"
IBM Semeru Runtime Open Edition (build 1.8.0_402-b06)
Eclipse OpenJ9 VM (build openj9-0.43.0, JRE 1.8.0 Linux amd64-64-Bit Compressed References 20240131_861 (JIT enabled, AOT enabled)
OpenJ9   - 2c3d78b48
OMR      - ea8124dbc
JCL      - 0fa9d9c532 based on jdk8u402-b06)

openjdk version "11.0.22" 2024-01-16
IBM Semeru Runtime Open Edition 11.0.22.0 (build 11.0.22+7)
Eclipse OpenJ9 VM 11.0.22.0 (build openj9-0.43.0, JRE 11 Linux amd64-64-Bit Compressed References 20240131_966 (JIT enabled, AOT enabled)
OpenJ9   - 2c3d78b48
OMR      - ea8124dbc
JCL      - 7876cac747 based on jdk-11.0.22+7)

openjdk version "17.0.10" 2024-01-16
IBM Semeru Runtime Open Edition 17.0.10.0 (build 17.0.10+7)
Eclipse OpenJ9 VM 17.0.10.0 (build openj9-0.43.0, JRE 17 Linux amd64-64-Bit Compressed References 20240116_670 (JIT enabled, AOT enabled)
OpenJ9   - 2c3d78b48
OMR      - ea8124dbc
JCL      - 2aad089841f based on jdk-17.0.10+7)

Problem summary

The test case contains loops and simple array operations, but when we set -Xcomp OpenJ9-8 reports ArrayIndexOutOfBoundsException, but OpenJ9-11 and 17 execute fine. We think this is similar to the previous issue.

Steps to Reproduce

java/bin/java  compiler.c1.TestArrayCopy 

Expected Result

nothing

Actual Result

ArrayIndexOutOfBoundsException

Source Code

package compiler.c1;

public class TestArrayCopy {
    public TestArrayCopy() {
    }
    public static void main(String[] var0) {
        int var1 = Integer.MIN_VALUE;
        for(int var3 = 0; var3 < 1000000; ++var3) {
            boolean[] var4 = new boolean[100];
            if (var1 * 2 < var4.length) {
                var4[var1 * 2] = false;
            }
        }
    }
}

Attachment

202403141134.zip

[pshipton]

The previous issue being https://github.com/eclipse-openj9/openj9/issues/19014? I reproduced this one with jdk11 but not jdk8.

@hzongaro fyi

[TemporaryRepos]

I think it's similar with https://github.com/eclipse-openj9/openj9/issues/19014, it's an optimization issue with array operations. But the OpenJ9 version affected is different, so the root cause of the two test cases is different.

[hzongaro]

I am able to reproduce the problem at optLevel warm with lastOptIndex=30, which corresponds to Tree Simplification in this case, so it might well be a duplicate of #19014.

$ java -Xjit:{*TestArrayCopy.main*}\(optLevel=warm,lastOptIndex=29\)  compiler.c1.TestArrayCopy
root@ubuntu-1-hz1:/home/henry/docker-hostdir/defects/issue19139
$ java -Xjit:{*TestArrayCopy.main*}\(optLevel=warm,lastOptIndex=30\)  compiler.c1.TestArrayCopy
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException
        at compiler.c1.TestArrayCopy.main(TestArrayCopy.java:11)

@nbhuiyan, may I ask you to look at this one together with #19014?

[nbhuiyan]

I can confirm that this issue and #19014 has the same root cause.

We face this problem due to an optimization during tree simplification that simplifies the BNDCHK calculation for the store into the boolean array.

This is the snippet of the IL that are of interest to us before the transformation:

n48n      BNDCHK [#1]                                                                         [0x7f04241c4650] bci=[-1,31,-] rc=0 vc=38 vn=- li=- udi=- nc=2
n46n        ==>iconst 100
n43n        imul (cannotOverflow )                                                            [0x7f04241c44c0] bci=[-1,29,-] rc=2 vc=38 vn=- li=- udi=- nc=2 flg=0x1000
n41n          iload  <auto slot 2>[#425  Auto] [flags 0x3 0x0 ] (cannotOverflow )             [0x7f04241c4420] bci=[-1,27,-] rc=1 vc=38 vn=- li=12 udi=12 nc=0 flg=0x1000
n42n          iconst 2 (X!=0 X>=0 )                                                           [0x7f04241c4470] bci=[-1,28,-] rc=1 vc=38 vn=- li=- udi=- nc=0 flg=0x104
n53n      bstorei  <array-shadow>[#227  Shadow] [flags 0x80000601 0x0 ]                       [0x7f042423f050] bci=[-1,31,-] rc=0 vc=38 vn=- li=- udi=- nc=2
n52n        aladd (X>=0 internalPtr )                                                         [0x7f042423f000] bci=[-1,31,-] rc=1 vc=38 vn=- li=- udi=- nc=2 flg=0x8100
n40n          ==>aload
n51n          lsub (highWordZero X>=0 cannotOverflow )                                        [0x7f04241c4740] bci=[-1,31,-] rc=1 vc=38 vn=- li=- udi=- nc=2 flg=0x5100
n50n            i2l (highWordZero X>=0 )                                                      [0x7f04241c46f0] bci=[-1,31,-] rc=1 vc=38 vn=- li=- udi=- nc=1 flg=0x4100
n43n              ==>imul
n49n            lconst -8 (X!=0 X<=0 )                                                        [0x7f04241c46a0] bci=[-1,31,-] rc=1 vc=38 vn=- li=- udi=- nc=0 flg=0x204
n83n        bconst   0 (X==0 X>=0 X<=0 )                                                      [0x7f042423f9b0] bci=[-1,0,-] rc=1 vc=38 vn=- li=- udi=- nc=0 flg=0x302
n4n       BBEnd </block_5> =====                                                              [0x7f04241c3890] bci=[-1,31,-] rc=0 vc=35 vn=- li=- udi=- nc=0

For the BNDCHK node above, the first child is the array length which is constant 100 as set in the Java code. For getting the index where the write will be attempted, we obtain the result of the following multiplication of a variable with a constant value: <auto slot 2> * 2. The BNDCHK would evaluate to true if the index child (the result of the multiplication) is >= 0 but less than 100. However, since the array size is divisible by the fixed multiplication factor used to obtain the index, and the array size is known, we can simplify the operation such that this multiplication can be skipped by dividing the array length by 2, and transform the trees into the following:

n48n      BNDCHK [#1]                                                                         [0x7f04241c4650] bci=[-1,31,-] rc=0 vc=41 vn=- li=- udi=- nc=2
n95n        iconst 50 (X!=0 X>=0 )                                                            [0x7f042423fd70] bci=[-1,31,-] rc=1 vc=0 vn=- li=- udi=- nc=0 flg=0x104
n41n        iload  <auto slot 2>[#425  Auto] [flags 0x3 0x0 ] (cannotOverflow )               [0x7f04241c4420] bci=[-1,27,-] rc=2 vc=41 vn=- li=- udi=12 nc=0 flg=0x1000

Here is where things go wrong. <auto slot 2> corresponds to the following in the Java code:

int var1 = Integer.MIN_VALUE;

Integer.MIN_VALUE is 0x80000000. This Java code was relying on causing an overflow to be able to write to the array at all. 0x80000000 * 2, i.e., 0x80000000 << 2 would overflow into 0, so every array store was being made at that slot in the loop.

When the tree simplifier eliminates the multiplication operation which results in the overflow into a valid array index, we run into this issue.

If we wanted to fix this, we would need to disable the tree simplification optimization that technically does the right thing, only to benefit a very specific sort of use case that relies on intentionally overflowing an int value. I do not think we should be going that route.

[nbhuiyan]

Given the description of the problem above, I do not think this failure warrants making any changes to the optimization responsible for causing the failure and this issue should be closed as not planned.

The optimization responsible for this problem could be modified to detect possible overflows so that we do not run into this issue. I am currently working on a solution.

[jdmpapin]

If n43n imul can overflow, then why is it flagged cannotOverflow?

[jdmpapin]

This transformation should be valid when the multiplication actually can't overflow

[nbhuiyan]

the imul node gets the cannotOverflow flag sometime during VP, although I am not sure exactly which part.

Before global VP:

n41n      BNDCHK [#1]                                                                         [0x7fd7d57163e0] bci=[-1,29,9] rc=0 vc=33 vn=26 li=- udi=- nc=2
n39n        ==>arraylength
n36n        imul                                                                              [0x7fd7d5716250] bci=[-1,27,9] rc=2 vc=33 vn=23 li=- udi=- nc=2
n34n          iload  <auto slot 1>[#423  Auto] [flags 0x3 0x0 ]                               [0x7fd7d57161b0] bci=[-1,25,9] rc=1 vc=33 vn=8 li=- udi=10 nc=0
n35n          iconst 2 (X!=0 X>=0 )                                                           [0x7fd7d5716200] bci=[-1,26,9] rc=1 vc=33 vn=22 li=- udi=- nc=0 flg=0x104

During VP:

Processing ttNode n41n BNDCHK
   imul [00007FD7D5716250] has existing constraint: value 23 is (TR::getMinSigned<TR::Int32>() to 99)I
   iconst [00007FD7D5716200] found existing global constraint value number 22 (00007FD7D5859A50): 2 I 
symRef 423 is not stored on all paths - treating as unknown
   iload [00007FD7D57161B0] looking at def value 8, istore [00007FD7D5791320]: no constraint
Node n34n has already been processed by mergeDefConstraints - returning NULL
Node n34n has already been processed by mergeDefConstraints - returning NULL
   iconst [00007FD7D5716200] has existing global constraint: value 22 is 2 I 
   imul [00007FD7D5716250] has existing constraint: value 23 is (TR::getMinSigned<TR::Int32>() to 99)I
Node n39n has already been processed by mergeDefConstraints - returning NULL
   iconst [00007FD7D5716340] has existing global constraint: value 24 is 100 I 
   imul [00007FD7D5716250] has existing constraint: value 23 is (TR::getMinSigned<TR::Int32>() to 99)I
{{{ IntRange.intersect1
  self: (TR::getMinSigned<TR::Int32>() to 99)I
  other: (0 to 99)I
IntRange.intersect1 }}}
{{{ IntRange.intersect1
  self: (0 to 99)I
  other: (TR::getMinSigned<TR::Int32>() to 99)I
{{{ IntRange.intersect1
  self: (TR::getMinSigned<TR::Int32>() to 99)I
  other: (0 to 99)I
IntRange.intersect1 }}}
IntRange.intersect1 }}}
   n36n imul gets new constraint: value 23 is (0 to 99)I
type of constraint - longConstraint: 0000000000000000, intConstraint: 00007FD7D585A060, shortConstraint: 0000000000000000

After global VP:

n41n      BNDCHK [#1]                                                                         [0x7fd7d57163e0] bci=[-1,29,9] rc=0 vc=37 vn=26 li=- udi=- nc=2
n39n        ==>iconst 100
n36n        imul (cannotOverflow )                                                            [0x7fd7d5716250] bci=[-1,27,9] rc=2 vc=37 vn=23 li=- udi=- nc=2 flg=0x1000
n34n          iload  <auto slot 1>[#423  Auto] [flags 0x3 0x0 ] (cannotOverflow )             [0x7fd7d57161b0] bci=[-1,25,9] rc=1 vc=37 vn=8 li=- udi=10 nc=0 flg=0x1000
n35n          iconst 2 (X!=0 X>=0 )                                                           [0x7fd7d5716200] bci=[-1,26,9] rc=1 vc=37 vn=22 li=- udi=- nc=0 flg=0x104

Disabling VP results in the imul node not being tagged as cannotOverflow, but the failure still happens because the BNDCHK simplifier does not care about whether there can be an overflow.

To deal with this, my plan is to fix the issue that is causing VP to incorrectly determine that the imul is something within (0 to 99)I and marking it as cannotOverflow (which would be correct if we did not actually allow modifications to the multiplier), and having BNDCHK simplifier make use of that information before simplifying the imul node.