Java Reference
In-Depth Information
loop, the expression
a[i]
is invariant; that is, it is a loop invariant expression. We deal with
these in the next section.
And as we shall see below, there is still much to be gained from common sub-expression
elimination when it comes to dealing with Java arrays.
Lifting Loop Invariant Code
Loop invariant expressions can be lifted out of the loop and computed in the predecessor
block to the loop header.
For example, consider the j-- code for summing the two matrices from the previous
section
5
.
inti=0;
while(i<=999){
intj=0;
while(j<=999){
c[i][j]=a[i][j]+b[i][j];
j=j+1;;
}
i=i+1;
}
This can be rewritten as
inti=0;
while(i<=999){
int[]ai=a[i];
int[]bi=b[i];
int[]ci=c[i];
intj=0;
while(j<=999)
{
ci[j]=ai[j]+bi[j];
j=j+1;;
}
i=i+1;
}
Thus,
a[i]
,
b[i]
, and
c[i]
need be evaluated just 1,000 times instead of 1,000,000 times.
This optimization is more dicult than the others. Basically, the expression
a[i]
is
invariant if either
1.
i
is constant, or
2. All the definitions of
i
that reach the expression are outside the loop, or
3. Only one definition of
i
reaches the expression, and the definition is loop invariant.
But that the HIR conforms to SSA makes it possible. Any code that is lifted must be lifted
to an additional block, which is inserted before the loop header.
Invariant expressions can be distinguished from expressions defined within the loop by
the fact that they are registered in the hash tables for dominators of the loop header.
Both a loop header and its immediate dominator are stored in the blocks. To find previous
dominators, one just links back through the block list via the immediate dominator links.
Computations involving invariant operands may be moved to the end of a loop header's
immediate dominator block.
5
The for-loop is not part of the j--language so we use the equivalent while-loop notation. If you have
implemented for-loops in your compiler by rewriting them as while-loops, then you should produce similar
HIR.
Search WWH ::
Custom Search