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

can be folded, that is, replaced by their constant value.
For example, consider the Java method
staticvoidfoo1(){
inti=1;
intj=2;
intk=i+j+3;
}
and corresponding HIR code
B0succ:B1
Locals:
0:0
1:1
2:2
B1[0,10]dom:B0pred:B0
Locals:
0:I3
1:I4
2:I7
I3:1
I4:2
I5:I3+I4
I6:3
I7:I5+I6
8:return
The instruction I3+I4 at I5: can be replaced by the constant 3 , and the I5+I6 at
I7: can replaced by the constant 6 .
A strategy for implementing is to associate a hash table with each basic block for storing
the constant values associated with instruction ids. As we scan a block's instructions, an
instruction defining a constant is added to the hash table, keyed by its id. If we come across
an instruction whose operands are already stored in this hash table of constants, we can
perform the operation immediately and store the result in that same table, keyed by the
instruction's id. This analysis may be carried across basic block boundaries, so long as we
do not store instruction ids for instructions representing Phi functions.
Common Sub-Expression Elimination (CSE) within Basic Blocks
Another optimization one may make is common sub-expression elimination, where we iden-
tify expressions that are re-evaluated even if their operands are unchanged.
For example, consider the following method, unlikely as it may be.
voidfoo(inti){
intj=i*i*i;
intk=i*i*i;
}
We can replace
intk=i*i*i;
in foo() with the more ecient
intk=j;
To see how we might recognize common sub-expressions, consider the HIR code for the
original version of foo(): .