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

Question

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.

Lanitalank

Isn't that rather something that the compiler should optimize? I think HotSpot is more about optimization in context of "a function is called often, so let's make the call faster". – Jodhpur

@Jodhpur - in Java the compiler does very few optimizations. Almost all of the standard compiler optimizations are applied at runtime by the JIT. That doesn't really answer whether it "should" be this way, but just how it is in practice. In this case, I don't think the compiler can optimize it: the bounds check is implied in the array access bytecode (unlike compile-to-native compilers where the bounds check would use some explicit instructions before the access): so absent some kind of "unsafe array access" bytecode, only the JVM can optimize this. – Lanitalank

Answer 1

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].

Succinylsulfathiazole

Surprising to see the load into r11 there, it is invariant so shouldn't it be moved out of the loop? – Raquel

Looking at this yesterday with IGV and wondering why I don't see the range check after parsing, but it turns out the range check is never even emitted: github.com/openjdk/jdk/blob/master/src/hotspot/share/opto/… Another way to find this is to use -XX:+LogComilation and look for <observe that='!need_range_check'/> for the iaload instruction (can match up bci with javap output). So yeah, really a very simple optimization :) – Eastbourne

@Raquel Indeed, there is a redundant load on JDK 8. When I ran the same code on JDK 11, it went away (so that the loop body consisted of just 3 instructions). – Succinylsulfathiazole