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

4:if_icmple17
7:iload_1
8:iload_0
9:iinc 0,-1
12:imul
13:istore_1
14:goto2
17:iload_1
18:ireturn
We have inserted line breaks to delineate basic blocks. The entry point is the iconst_1
instruction at location 0 so that begins a basic block; let us call it B1. The iload_0 at
location 2 is the target of the goto instruction (at 14) so that also must start a basic block;
we call it B2. B2 extends through the if_icmple instruction; the block must end there
because it is a branch. The next basic block (B3) begins at location 7 and extends to the
goto at location 14. Finally, the iload_1 at location 17 is the target of the if_icmple
branch at location 4 so it starts basic block B4. B4 extends to the end of the method and
is terminated by the ireturn instruction.
The control-flow graph, expressed as a graph constructed from these basic blocks is
illustrated in Figure 6.7; we have added an extra special entry block B0, for making further
analysis simpler. The boxes represent the basic blocks and the arrows indicate the flow of
control among the blocks; indeed, all control flow information is captured in the graph.
Notice that the boxes and arrows are not really necessary to follow the flow of control
among blocks; we put them there in the figure only for emphasis. You will notice that the
first line of text within each box identifies the block, a list of any successor blocks (labeled
by succ: ) and a list of any predecessor blocks (labeled by pred: ). For example, block B3
has a predecessor B2 indicating that control flows from the end of block B2 into the start
of B3; B3 also has a successor B2 indicating that control flows from the end of B3 to the
start of block B3. We add an extra beginning block B0 for the method's entry point.
The denotation [LH] on the rst line of B2 indicates that B2 is a loop header |the rst
block in a loop. The denotation [LT] on the first line of B3 indicates that B3 is a loop
tail |the last block in a loop (and a predecessor of the loop header). This information is
used later in identifying loops for performing optimizations and ordering blocks for optimal
register allocation.
The pairs of numbers within square brackets, for example [7,14] on the first line of
B3, denote the ranges of JVM instructions captured in the block.
The keyword dom: labels the basic block's immediate dominator. In our graph, a node d
is said to dominate a node n if every path from the entry node (B0) to n must go through
d. A node d strictly dominates n if it dominates n but is not the same as n. Finally, node d
is an immediate dominator of node n if d strictly dominates n but does not dominate any
other node that strictly dominates n. That is, it is the node on the path from the entry node
to n that is the \closest" to n. Dominators are useful for certain optimizations, including
the lifting of loop-invariant code (see Section 6.3.3).
The State Vector
Local variables are tracked in a state vector called locals and are indexed in this vector
by their location in the JVM stack frame. The current state of this vector at the end of a
block's instruction sequence is printed on the block's second line and labeled with Locals: .
The values are listed in positional order and each value is represented by the instruction id
for the instruction that computes it.
For example, in B0 this vector has just one element, corresponding to the method's