Incorrect output for test involving switch with fall-through case
hzongaro opened this issue · 3 comments
hzongaro commented
The following test produces incorrect output with OpenJ9:
class Test {
final int N = 256;
long instanceCount;
float fFld;
int iFld;
short sFld;
long vMeth_check_sum;
void vMeth(int i2) {
int i17 = -244, i19 = 23560, iArr[] = new int[N], iArr2[][] = new int[N][N];
init(iArr2, 11);
for (int i3 : iArr) {
int i16;
i3 = (int) instanceCount++;
i2 *= instanceCount;
switch ((i2 >>> 1) % 6 + 6) {
case 6:
for (i17 = 2; i17 > 1; i17 -= 3) i16 = (int) instanceCount;
case 7:
iArr2[(i17 >>> 1) % N][i19 % N] *= fFld;
case 8:
break;
case 10:
vMeth_check_sum += checkSum(iArr2);
}
}
}
void vSmallMeth(int i, short s, int i1) {
vMeth(i);
}
void mainTest(String[] strArr1) {
for (int smallinvoc = 0; smallinvoc < 238; smallinvoc++) vSmallMeth(25982, sFld, iFld);
System.out.println(vMeth_check_sum);
}
public static void main(String[] strArr) {
boolean ax$16;
Test _instance = new Test();
_instance.mainTest(strArr);
}
public static void init(int[][] a, int seed) {
for (int j = 0; j < a.length; j++) {
init(a[j], seed);
}
}
public static void init(int[] a, int seed) {
for (int j = 0; j < a.length; j++) {
a[j] = (j % 2 == 0) ? seed + j : seed - j;
}
}
public static long checkSum(int[] a) {
long sum = 0;
for (int j = 0; j < a.length; j++) {
sum += (a[j] / (j + 1) + a[j] % (j + 1));
}
return sum;
}
public static long checkSum(int[][] a) {
long sum = 0;
for (int j = 0; j < a.length; j++) {
sum += checkSum(a[j]);
}
return sum;
}
}FYI. The result of HotSpot JDK8/11/17 and the Android Runtime is -7725525924.
Originally posted by @connglli in #15306 (comment)
hzongaro commented
The problem appears to be that Global VP folds the first array index for iArr2 in case 7 to be 255 - it's ignoring the reaching definition for i17 from i17 = -244:
int i17 = -244
...
switch ((i2 >>> 1) % 6 + 6) {
case 6:
for (i17 = 2; i17 > 1; i17 -= 3) i16 = (int) instanceCount;
case 7:
iArr2[(i17 >>> 1) % N][i19 % N] *= fFld;
Before Global VP:
15n BBStart <block_2> (freq 153) [0x7f46017585c0] bci=[-1,0,10] rc=0 vc=419 vn=74 li=- udi=- nc=0
n18n istore <auto slot 2>[#419 Auto] [flags 0x3 0x0 ] [0x7f46017586b0] bci=[-1,3,10] rc=0 vc=419 vn=10 li=3 udi=1 nc=1
n17n iconst -244 (X!=0 X<=0 ) [0x7f4601758660] bci=[-1,0,10] rc=1 vc=419 vn=10 li=- udi=- nc=0 flg=0x204
...
n78n treetop [0x7f46017d3820] bci=[-1,81,15] rc=0 vc=47 vn=104 li=- udi=- nc=1
n77n irem [0x7f46017d37d0] bci=[-1,81,15] rc=2 vc=47 vn=38 li=- udi=- nc=2
n75n iushr [0x7f46017d3730] bci=[-1,78,15] rc=1 vc=47 vn=37 li=- udi=- nc=2
n73n iload <parm 1 I>[#418 Parm] [flags 0x40000103 0x0 ] [0x7f46017d3690] bci=[-1,76,15] rc=1 vc=47 vn=34 li=11 udi=21 nc=0
n74n iconst 1 [0x7f46017d36e0] bci=[-1,77,15] rc=1 vc=47 vn=3 li=- udi=- nc=0
n76n iconst 6 [0x7f46017d3780] bci=[-1,79,15] rc=1 vc=47 vn=36 li=- udi=- nc=0
n84n table () [0x7f46017d3a00] bci=[-1,85,15] rc=0 vc=47 vn=111 li=- udi=- nc=7 flg=0x20
n82n iadd [0x7f46017d3960] bci=[-1,85,15] rc=1 vc=47 vn=39 li=- udi=- nc=2
n77n ==>irem
n81n iconst 0 [0x7f46017d3910] bci=[-1,85,15] rc=1 vc=47 vn=16 li=- udi=- nc=0
n83n default --> block_9 BBStart at n3n [0x7f46017d39b0] bci=[-1,85,15] rc=1 vc=47 vn=105 li=- udi=- nc=0
n85n 0 --> block_5 BBStart at n5n [0x7f46017d3a50] bci=[-1,85,15] rc=1 vc=47 vn=106 li=- udi=- nc=0
n86n 1 --> block_6 BBStart at n7n [0x7f46017d3aa0] bci=[-1,85,15] rc=1 vc=47 vn=107 li=- udi=- nc=0
n87n 2 --> block_9 BBStart at n3n [0x7f46017d3af0] bci=[-1,85,15] rc=1 vc=47 vn=108 li=- udi=- nc=0
n88n 3 --> block_9 BBStart at n3n [0x7f46017d3b40] bci=[-1,85,15] rc=1 vc=47 vn=109 li=- udi=- nc=0
n89n 4 --> block_8 BBStart at n11n [0x7f46017d3b90] bci=[-1,85,15] rc=1 vc=47 vn=110 li=- udi=- nc=0
n48n BBEnd </block_4> ===== [0x7f4601759010] bci=[-1,85,15] rc=0 vc=47 vn=112 li=- udi=- nc=0
n5n BBStart <block_5> (freq 9077) (in loop 3) [0x7f46017582a0] bci=[-1,120,17] rc=0 vc=47 vn=113 li=- udi=- nc=0
n98n istore <auto slot 2>[#419 Auto] [flags 0x3 0x0 ] [0x7f46017d3e60] bci=[-1,121,17] rc=0 vc=47 vn=17 li=6 udi=10 nc=1
n97n iconst -1 [0x7f46017d3e10] bci=[-1,120,17] rc=1 vc=47 vn=17 li=- udi=- nc=0
n6n BBEnd </block_5> ===== [0x7f46017582f0] bci=[-1,121,17] rc=0 vc=47 vn=114 li=- udi=- nc=0
n7n BBStart <block_6> (freq 9107) (in loop 3) [0x7f4601758340] bci=[-1,147,21] rc=0 vc=47 vn=115 li=- udi=- nc=0
n105n treetop [0x7f46017d4090] bci=[-1,130,19] rc=0 vc=47 vn=116 li=- udi=- nc=1
n104n isub [0x7f46017d4040] bci=[-1,130,19] rc=3 vc=47 vn=49 li=- udi=- nc=2
n102n iushr [0x7f46017d3fa0] bci=[-1,126,19] rc=3 vc=47 vn=42 li=- udi=- nc=2
n100n iload <auto slot 2>[#419 Auto] [flags 0x3 0x0 ] [0x7f46017d3f00] bci=[-1,124,19] rc=1 vc=47 vn=41 li=12 udi=22 nc=0
n101n iconst 1 [0x7f46017d3f50] bci=[-1,125,19] rc=1 vc=47 vn=3 li=- udi=- nc=0
n267n iand [0x7f46017d7330] bci=[-1,130,19] rc=1 vc=47 vn=48 li=- udi=- nc=2
n266n iadd [0x7f46017d72e0] bci=[-1,130,19] rc=1 vc=47 vn=47 li=- udi=- nc=2
n264n iushr [0x7f46017d7240] bci=[-1,130,19] rc=1 vc=47 vn=46 li=- udi=- nc=2
n262n ishr [0x7f46017d71a0] bci=[-1,130,19] rc=1 vc=47 vn=45 li=- udi=- nc=2
n102n ==>iushr
n263n iconst 7 [0x7f46017d71f0] bci=[-1,130,19] rc=1 vc=47 vn=44 li=- udi=- nc=0
n265n iconst 24 [0x7f46017d7290] bci=[-1,130,19] rc=1 vc=47 vn=43 li=- udi=- nc=0
n102n ==>iushr
n268n iconst -256 [0x7f46017d7380] bci=[-1,130,19] rc=1 vc=47 vn=40 li=- udi=- nc=0
...
n117n compressedRefs [0x7f46017d4450] bci=[-1,131,19] rc=0 vc=47 vn=117 li=- udi=- nc=2
n115n aloadi <array-shadow>[#232 Shadow] [flags 0x80000607 0x0 ] [0x7f46017d43b0] bci=[-1,131,19] rc=5 vc=47 vn=58 li=- udi=- nc=1
n114n aladd (X>=0 internalPtr sharedMemory ) [0x7f46017d4360] bci=[-1,131,19] rc=1 vc=47 vn=57 li=- udi=- nc=2 flg=0x8100
n99n ==>aload
n113n lsub [0x7f46017d4310] bci=[-1,131,19] rc=1 vc=47 vn=56 li=- udi=- nc=2
n111n lmul [0x7f46017d4270] bci=[-1,131,19] rc=1 vc=47 vn=55 li=- udi=- nc=2
n110n i2l (X>=0 ) [0x7f46017d4220] bci=[-1,131,19] rc=1 vc=47 vn=54 li=- udi=- nc=1 flg=0x100
n104n ==>isub
n109n lconst 4 [0x7f46017d41d0] bci=[-1,131,19] rc=1 vc=47 vn=24 li=- udi=- nc=0
n112n lconst -16 [0x7f46017d42c0] bci=[-1,131,19] rc=1 vc=47 vn=23 li=- udi=- nc=0
n116n lconst 0 (highWordZero ) [0x7f46017d4400] bci=[-1,131,19] rc=1 vc=47 vn=53 li=- udi=- nc=0 flg=0x4000
After Global VP, node n113n is folded from an lsub to an lconst 1036:
n78n treetop [0x7f46017d3820] bci=[-1,81,15] rc=0 vc=419 vn=95 li=- udi=- nc=1
n77n irem (cannotOverflow ) [0x7f46017d37d0] bci=[-1,81,15] rc=2 vc=419 vn=34 li=- udi=- nc=2 flg=0x1000
n75n iushr (X>=0 cannotOverflow ) [0x7f46017d3730] bci=[-1,78,15] rc=1 vc=419 vn=33 li=- udi=- nc=2 flg=0x1100
n73n iload <parm 1 I>[#418 Parm] [flags 0x40000103 0x0 ] (cannotOverflow ) [0x7f46017d3690] bci=[-1,76,15] rc=2 vc=419 vn=30 li=12 udi=20 nc=0 flg=0x1000
n74n iconst 1 (X!=0 X>=0 ) [0x7f46017d36e0] bci=[-1,77,15] rc=1 vc=419 vn=8 li=- udi=- nc=0 flg=0x104
n76n iconst 6 (X!=0 X>=0 ) [0x7f46017d3780] bci=[-1,79,15] rc=1 vc=419 vn=32 li=- udi=- nc=0 flg=0x104
n324n treetop [0x7f46017d8500] bci=[-1,76,15] rc=0 vc=419 vn=96 li=- udi=- nc=1
n73n ==>iload
n84n table () [0x7f46017d3a00] bci=[-1,85,15] rc=0 vc=419 vn=103 li=- udi=- nc=7 flg=0x20
n77n ==>irem
n83n default --> block_9 BBStart at n3n [0x7f46017d39b0] bci=[-1,85,15] rc=1 vc=419 vn=97 li=- udi=- nc=0
n85n 0 --> block_5 BBStart at n5n [0x7f46017d3a50] bci=[-1,85,15] rc=1 vc=419 vn=98 li=- udi=- nc=0
n86n 1 --> block_6 BBStart at n7n [0x7f46017d3aa0] bci=[-1,85,15] rc=1 vc=419 vn=99 li=- udi=- nc=0
n87n 2 --> block_9 BBStart at n3n [0x7f46017d3af0] bci=[-1,85,15] rc=1 vc=419 vn=100 li=- udi=- nc=0
n88n 3 --> block_9 BBStart at n3n [0x7f46017d3b40] bci=[-1,85,15] rc=1 vc=419 vn=101 li=- udi=- nc=0
n89n 4 --> block_8 BBStart at n11n [0x7f46017d3b90] bci=[-1,85,15] rc=1 vc=419 vn=102 li=- udi=- nc=0
n48n BBEnd </block_4> ===== [0x7f4601759010] bci=[-1,85,15] rc=0 vc=419 vn=104 li=- udi=- nc=0
n5n BBStart <block_5> (freq 9077) (in loop 4) [0x7f46017582a0] bci=[-1,120,17] rc=0 vc=419 vn=105 li=- udi=- nc=0
n98n istore <auto slot 2>[#419 Auto] [flags 0x3 0x0 ] [0x7f46017d3e60] bci=[-1,121,17] rc=0 vc=419 vn=16 li=6 udi=10 nc=1
n97n iconst -1 (X!=0 X<=0 ) [0x7f46017d3e10] bci=[-1,120,17] rc=1 vc=419 vn=16 li=- udi=- nc=0 flg=0x204
n6n BBEnd </block_5> ===== [0x7f46017582f0] bci=[-1,121,17] rc=0 vc=419 vn=106 li=- udi=- nc=0
n7n BBStart <block_6> (freq 9107) (in loop 4) [0x7f4601758340] bci=[-1,147,21] rc=0 vc=419 vn=107 li=- udi=- nc=0
n295n treetop [0x7f46017d7bf0] bci=[-1,126,19] rc=0 vc=419 vn=108 li=- udi=- nc=1
n102n iushr (X>=0 cannotOverflow ) [0x7f46017d3fa0] bci=[-1,126,19] rc=3 vc=419 vn=36 li=- udi=- nc=2 flg=0x1100
n100n iload <auto slot 2>[#419 Auto] [flags 0x3 0x0 ] (cannotOverflow ) [0x7f46017d3f00] bci=[-1,124,19] rc=2 vc=419 vn=35 li=13 udi=21 nc=0 flg=0x1000
n101n iconst 1 (X!=0 X>=0 ) [0x7f46017d3f50] bci=[-1,125,19] rc=1 vc=419 vn=8 li=- udi=- nc=0 flg=0x104
n325n treetop [0x7f46017d8550] bci=[-1,124,19] rc=0 vc=419 vn=109 li=- udi=- nc=1
n100n ==>iload
n105n treetop [0x7f46017d4090] bci=[-1,130,19] rc=0 vc=419 vn=110 li=- udi=- nc=1
n104n isub [0x7f46017d4040] bci=[-1,130,19] rc=3 vc=419 vn=39 li=- udi=- nc=2
n102n ==>iushr
n267n iand (cannotOverflow ) [0x7f46017d7330] bci=[-1,130,19] rc=1 vc=419 vn=38 li=- udi=- nc=2 flg=0x1000
n102n ==>iushr
n268n iconst -256 (X!=0 X<=0 ) [0x7f46017d7380] bci=[-1,130,19] rc=1 vc=419 vn=37 li=- udi=- nc=0 flg=0x204
...
n117n compressedRefs [0x7f46017d4450] bci=[-1,131,19] rc=0 vc=419 vn=114 li=- udi=- nc=2
n115n aloadi <array-shadow>[#232 Shadow] [flags 0x80000607 0x0 ] [0x7f46017d43b0] bci=[-1,131,19] rc=5 vc=419 vn=44 li=- udi=- nc=1
n114n aladd (X>=0 internalPtr sharedMemory ) [0x7f46017d4360] bci=[-1,131,19] rc=1 vc=419 vn=43 li=- udi=- nc=2 flg=0x8100
n99n ==>aload
n113n lconst 1036 (highWordZero X!=0 X>=0 cannotOverflow ) [0x7f46017d4310] bci=[-1,131,19] rc=1 vc=419 vn=42 li=- udi=- nc=0 flg=0x5104
n116n lconst 0 (highWordZero X==0 X>=0 X<=0 ) [0x7f46017d4400] bci=[-1,131,19] rc=1 vc=419 vn=41 li=- udi=- nc=0 flg=0x4302
hzongaro commented
I think I was mistaken about Global VP ignoring the reaching definition of i17 = -244. I think now that Global VP decides that the only possible value for the isub operation at node n104n (after passing through a BNDCHK) is 255. There could be an error in the constraints it computed leading up to that.
I've annotated the part of the tree for the isub computation with constraints from Global VP below:
n104n isub {(TR::getMinSigned<TR::Int32>() to -122)I, (255 to TR::getMaxSigned<TR::Int32>())I}4040] bci=[-1,130,19] rc=3 vc=47 vn=49 li=- udi=- nc=2
n102n iushr {2147483647 to 2147483526} [0x7f6d818a3fa0] bci=[-1,126,19] rc=3 vc=47 vn=42 li=- udi=- nc=2
n100n iload <auto slot 2>[#419 Auto] [flags 0x3 0x0 ] {-1,-244} [0x7f6d818a3f00] bci=[-1,124,19] rc=1 vc=47 vn=41 li=12 udi=22 nc=0
n101n iconst 1 [0x7f6d818a3f50] bci=[-1,125,19] rc=1 vc=47 vn=3 li=- udi=- nc=0
n267n iand (TR::getMinSigned<TR::Int32>() to 2147483392) [0x7f6d818a7330] bci=[-1,130,19] rc=1 vc=47 vn=48 li=- udi=- nc=2
n266n iadd {2147483647 to 2147483526} [0x7f6d818a72e0] bci=[-1,130,19] rc=1 vc=47 vn=47 li=- udi=- nc=2
n264n iushr {0} [0x7f6d818a7240] bci=[-1,130,19] rc=1 vc=47 vn=46 li=- udi=- nc=2
n262n ishr {(0 to 16777215)I} [0x7f6d818a71a0] bci=[-1,130,19] rc=1 vc=47 vn=45 li=- udi=- nc=2
n102n ==>iushr
n263n iconst 7 [0x7f6d818a71f0] bci=[-1,130,19] rc=1 vc=47 vn=44 li=- udi=- nc=0
n265n iconst 24 [0x7f6d818a7290] bci=[-1,130,19] rc=1 vc=47 vn=43 li=- udi=- nc=0
n102n ==>iushr {2147483647 to 2147483526}
n268n iconst -256 [0x7f6d818a7380] bci=[-1,130,19] rc=1 vc=47 vn=40 li=- udi=- nc=0
The constraint for the isub is {(TR::getMinSigned<TR::Int32>() to -122)I, (255 to TR::getMaxSigned<TR::Int32>())I}, and the subsequent BNDCHK compares with an arraylength of 255 256, so it thinks the only possible value for the isub on the path after the BNDCHK is 255.
I'll look over the constraints for the other operations in the tree for the isub to understand whether some range that's been computed is incorrect.
hzongaro commented
The problem appears to be with the range that is created for the iushr operation. The lower and upper bounds of the first operand are used to calculate the lower and upper bounds, respectively, of the result, without regard to the possible change of sign.
The incorrect behaviour can be reproduced using this simplified test case:
public class Experiment15874 {
public static final void sub(int i) {
int val = (i == 1) ? 0x9FFFFFFF : ((i == 2) ? 0xFFFFFFFF : 0xAFFFFFFF);
if (val >>> 29 == 5) System.out.println("val >>> 29 is 5");
else System.out.println("val >>> 29 is not 5");
}
public static final void main(String[] args) {
sub(1);
sub(2);
sub(3);
}
}
Running with the interpreter produces this output:
java -Xint Experiment15874
val >>> 29 is not 5
val >>> 29 is not 5
val >>> 29 is 5
Forcing Experiment15874.sub to be compiled results in this (incorrect output), because Value Propagation determines that val >>> 29 can never be five.
$ java -Xjit:limit={Experiment15874.sub*},count=0 Experiment15874
val >>> 29 is not 5
val >>> 29 is not 5
val >>> 29 is not 5