Java Reference
In-Depth Information
Array Bounds Check Elimination
When indexing an array, we must check that the index is within bounds. For example, in
our example of matrix multiplication, in the assignment
c[i][j]=a[i][j]+b[i][j];
The
i
and
j
must be tested to make sure each is greater than or equal than zero, and less
than 1,000. And this must be done for each of
c
,
a
, and
b
. But if we know that
a
,
b
, and
c
are all of like dimensions, then once the check is done for
a
, it need not be repeated for
b
and
c
. Given that the inner loop in our earlier matrix multiplication example is executed
one million times, we have saved two million checks!
Again, a clever compiler can analyze the context in which the statement
c[i][j]=a[i][j]+b[i][j];
is executed (for example, within a nested for-loop) and show that the indices are never out
of bounds. When the arrays for
a
,
b
and
c
are created in a loop header's dominator, this is
straightforward; other more complicated control graphs may warrant more extensive data-
flow analysis (below). Moreover, an array index operation such as
a[i]
can be registered
in the hash table, ensuring that subsequent occurrences, in the same basic block or in
subsequent blocks where the operation is not involved in a Phi function, need not be re-
checked.
Null Check Elimination
Every time we send a message to an object, or access a field of an object, we must insure
that the object is not the special null object. For example, in
...a.f...
we will want to make sure that a is non-null before computing the offset to the field
f
. But
we may know that a is non-null; for example, we may have already checked it as in the
following.
...a.f...
...a.g...
...a.h...
Once we have done the null-check for
...a.f...
there is no reason to do it again for either
a.g
or
a.h
.
Again, the ids of checked operands can be stored in the hash tables attached to blocks.
If they are found subsequently, they need not be checked again.
A Need for Data-Flow Analysis
The HIR does not expose every opportunity for optimization, particularly those involving
back branches (in loops); for this to happen we would need full data-flow analysis where
we compute where in the code computed values remain valid. We use data-flow analysis in
Section 7.4.1 to compute such liveness intervals for virtual registers (variables) in the LIR as
a prerequisite to register allocation; look there for a detailed data-flow analysis algorithm.
On the other hand, the HIR does expose many opportunities for optimization, partic-
ularly for the effort involved. The amount of code improvement achieved in proportion to
the time spent is important in a just-in-time (or hot spot) compiler such as we use for
processing JVM code.
Search WWH ::
Custom Search