[SOLVED] Can Hotspot eliminate bounds checks when the range of the index is restricted via and?

Can Hotspot eliminate bounds checks when the range of the index is restricted via and?

Consider the following function:

int foo(int[] indices) {
  int[] lookup = new int[256];
  fill(lookup); // populate values, not shown

  int sum = 0;
  for (int i : indices) {
    sum += lookup[i & 0xFF]; // array access
  }

  return sum;
}

Can modern HotSpot eliminate the bounds check on the lookup[i & 0xFF] access? This access cannot be out of bounds since i & 0xFF is in the range 0-255 and the array has 256 elements.

Solution

Yes, this is a relatively simple optimization, which HotSpot definitely can do. JIT compiler deduces possible ranges of expressions, and uses this information to eliminate redundant checks.

We can verify this by printing the assembly code: -XX:CompileCommand=print,Test::foo

...
0x0000020285b5e230: mov     r10d,dword ptr [rcx+r8*4+10h]  # load 'i' from indices array
0x0000020285b5e235: and     r10d,0ffh                      # i = i & 0xff
0x0000020285b5e23c: mov     r11,qword ptr [rsp+8h]         # load 'lookup' into r11
0x0000020285b5e241: add     eax,dword ptr [r11+r10*4+10h]  # eax += r11[i]

There are no comparison instructions between loading i and lookup[i & 0xff].