Register Allocation - Introduction to Compiler Construction in a Java World - page 264

Algorithm 7.7 Resolve Data Flow
Input: The version of the control-flow graph g after register allocation (Algorithm 7.4)
Output: The same LIR but with all necessary loads and stores inserted, including those
required to resolve changes in the data flow
// Resolve local (to a block) data flow
for interval i in g.intervals do
if the interval i is marked for spilling then
for child interval c in the interval i do
if c is the first child then
add a store instruction at the end of i's last range
add a load instruction at the start of c's rst range
else
add a store instruction at the end of the previous child's last range
add a load instruction at the start of c's rst range
end if
end for
end if
end for
// Resolve global data flow
for block b in g.blocks do
for block s in b.succesors do
// collect all necessary resolving moves between b and s
for operand register r in s.liveIn do
interval parentInterval g.intervals[r]
interval fromInterval parentInterval.childAt(b.lastOp.id)
interval fromInterval parentInterval.childAt(s.rstOp.id)
if fromInterval 6= toInterval then
add a store instruction after the last use position in the from block
if there is a use in the from block before a define then
add a load instruction before it in the to block
end if
end if
end for
end for
end for
The algorithm has two parts. The first part deals with the local basic block, that is, the
basic block in which the split occurred. The second part deals with other blocks, adding
stores and loads to preserve data flow. Notice the similarity to the algorithm for Phi-
resolution when translating HIR to LIR in Chapter 6.
An interval starts of whole, and may consist of multiple ranges with holes between
them. Once that interval is split, it is either split at a hole or at a range; in either case,
a child is created. The child consists of the remaining range(s). The child's rst range's
start is guaranteed to be at an index after its parent interval's last range's end. The child
is itself an interval with ranges, holes, etc., so it can be split too. The resulting interval
however, is considered the second child to the original parent interval and not the child of
the child. This keeps interval families only one level deep, allowing easy tracking of which
children belong to which parent. Note also that the list of children, if more than one, do
not overlap index-wise and are consecutive according to their position in the children array
of the parent.