Java Reference
In-Depth Information
x
1
=3;
x
1
=x
1
+y
1
;
In the HIR, we represent a variable's value by the instruction that computed it and we
track these values in the state vector. The value in a state vector's element may change as
we sequence through the block's instructions. If the next block has just one predecessor, it
can copy the predecessor's state vector at its start; if there are more than two predecessors,
the states must be merged.
For example, consider the following j-- method, where the variables are in SSA form.
staticintssa(intw
1
){
if(w
1
>0){
w
2
=1;
}
else{
w
3
=2;
}
returnw
?
;
}
In the statement,
returnw
?
;
which
w
do we return,
w
2
or
w
3
? Well, it depends on which of the two paths is taken through
the if-then-else statement. In terms of basic blocks, it is as illustrated in Figure 6.9.
FIGURE 6.9 The SSA merge problem.
We solve this problem using what is called a Phi function, a special HIR instruction
that captures the possibility of a variable having one of several values. In our example, the
final block would contain the following code.
w
4
= [
w
2
w
3
];
returnw
4
;
The [
w
2
w
3
] represents a Phi function with two operands: the operand w
2
captures the
possibility that one branch of the if-then-else was taken and the
w
3
captures the possibility
that the other branch was taken. Of course, the target SPIM has no representation for
this but we shall remove these special Phi instructions before attempting to generate SPIM
instructions. We can still do analysis on it. The data flow is illustrated in Figure 6.10.
Search WWH ::
Custom Search