In Masterminds of Programming, James Gosling says:

- One of the magics of modern compilers is that they’re able to “theorem-prove away” potentially all [array] subscript checks… You might do a little bit of checking on the outside of the loop, but inside the loop, it just screams.
- [The VM] had a crew of really bright people working on it for a decade, a lot of PhD compiler jockeys.

To underline this, the following experiment can be done (in Z423)

Start with this typical piece of imperative code

```
for (int i = 0; i<n; i++) {
for (int k = 0; k<n; k++) {
int s = 0;
for (int j = 0; j<n; j++) {
s += a[i][j] * b[j][k];
}
res [i][k] = s;
}
}
```

This is a naive implementation of matrix multiplication (full source code). It does not matter what the code actually does, the point is that the statement in the innermost loop

`s += a[i][j] * b[j][k];`

contains one multiplication, one addition, and 4 array indexing operations. Now Java array access is safe: the language requires that for each access, the index value must be checked to be in range.

We view the Java byte code with `javap -c Run.java`

. The above loop gets compiled to

```
static int[][] amul(int, int[][], int[][]);
...
31: iload 7 ; iload_0 ; if_icmpge 63
iload 6
aload_1 ; iload 4; 42: aaload; iload 7; 45: iaload
aload_2 ; iload 7; 49: aaload; iload 5; 52: iaload
53: imul ; iadd ; istore 6 ; iinc 7, 1
goto 31
63: ...
```

This has 4 array access operations (aaload at 42 and 49, iaload at 45 and 52) and each is required to do two checks (compare to lower bound, compare to upper bound). A straightforward compilation would produce 8 comparisons.

The “magic of modern compilers” is in the Java virtual machine: it will hot-spot compile this code. We can observe actual assembly code with

`java -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly Run`

(notes on installing the disassembler) and the relevant part of the output (note the bytecode labels coincide with the above) is

```
0x00007f0745112ce3: mov 0x10(%rdx,%r10,4),%r13d ;*aaload
; - Run::amul@49 (line 9)
0x00007f0745112ce8: mov 0xc(%r13),%eax ; implicit exception: dispatches to 0x00007f0745112e2c
0x00007f0745112cec: mov 0x10(%rsi,%r10,4),%r8d ;*iaload
; - Run::amul@45 (line 9)
0x00007f0745112cf1: cmp %eax,%edi
0x00007f0745112cf3: jae 0x00007f0745112d9d ;*iaload
; - Run::amul@52 (line 9)
0x00007f0745112cf9: imul 0x10(%r13,%rdi,4),%r8d
0x00007f0745112cff: add %r8d,%ebx ;*iadd
; - Run::amul@54 (line 9)
0x00007f0745112d02: inc %r10d ;*iinc
; - Run::amul@57 (line 8)
0x00007f0745112d05: cmp $0x1,%r10d
0x00007f0745112d09: jl 0x00007f0745112ce3 ;*if_icmpge
```

This is our inner loop, and there are three computations (`imul`

and `add`

, as well as `inc`

for increasing the inner loop variable) and just two tests (`cmp`

). One (the last one) is needed for exiting the loop, so our observation is:

- of the 8 required access checks, just one remains, and indeed the others had been
*theorem-proved away*.