Translating JVM Code to MIPS Code - Introduction to Compiler Construction in a Java World - page 224

B0succ:B1
Locals:I0
I0:LDLOC0
B1[0,12]dom:B0pred:B0
Locals:I0I4I6
I3:I0*I0
I4:I3*I0
I5:I0*I0
I6:I5*I0
7:return
We sequence through the instructions, registering each in the block's hash table, indexed
by the instruction and its operand(s); the value stored is the instruction id. As for constant
propagation, we cannot trust values defined by Phi functions without further data-flow
analysis, so we do not register such instructions.
At I6: , the reference to I5 can replaced by I3 . More importantly, any subsequent
reference to I6 could be replaced by I4 .
Of course, we are not likely to see such a method with such obvious common sub-
expressions. But common sub-expressions do arise in places one might not expect them. For
example, consider the following C Language fragment:
for(i=0;i<1000;i++){
for(j=0;j<1000;j++){
c[i][j]=a[i][j]+b[i][j];
}
}
The C compiler represents the matrices as linear byte sequences, one row of elements after
another; this is called row major form 4 . If a , b , and c are integer matrices, and the base
address of c is c' , then the byte memory address of c[i][j] is
c'+i*4*1000+j*4
The factor i is there because it is the (counting from zero) i th row; the factor 1000 is there
because there are 1,000 elements in a row; and the factor 4 is there (twice) because there
are 4 bytes in an integer word. Likewise, the addresses of a[i][j] and b[i][j] are
a'+i*4*1000+j*4
and
b'+i*4*1000+j*4
respectively. So, eliminating the common offsets, i*4*1000+j*4 can save us a lot
of computation, particularly because the inner loop is executed a million times!
But in Java, matrices are not laid out this way. Rather, in the expression
a[i][j]
the sub-expression a[i] yields an integer array object, call it ai , from which we can index
the j th element,
ai[j]
So, we cannot expect the same savings. On the other hand, the expression a[i] never
changes in the inner loop; only the j is being incremented. We say that, within the inner
4 In FORTRAN, matrices are stored as a sequence of columns, which is incolumnmajorform.