Re: Evaluation Tech. Needed for Register Allocation

yhshiau@csie.nctu.edu.tw (Yuh-Horng Shiau(dcp78804)) writes:
>Instead of defining a live range based on single touchstone, such as
>instruction number in Chaitin's algorithm and basic block number in
>the priority-based algorithm (proposed by Chow and Hennessy)


Before we go further, I need to try and clarify some misunderstandings.
(This might be a better subject for e-mail, but perhaps others will
benefit).


Chow and Hennessy (and Larus and Hilfinger) represent each live range as a
set of basic blocks. Thus, they can determine if two live ranges
interfere by computing the intersection of their two sets -- if the
intersection is empty, there is no interference.


This approach is imprecise (but safely conservative) in that two live
ranges that don't actually interfere may have intersecting live ranges.
For example


A = <expression 1> Block 1
B = A + <expression 2>
if (p)
{ Block 2
C = B + <expression 3>
D = C
}
print C, D Block 2
return


Here, no variables need interfere; however, Chow & Hennessy's approach
would compute that B interferes with A, C, and D and that C and D
interfere with each other. The live ranges of the variables would be:


A { 1 }
B { 1, 2 }
C { 2, 3 }
D { 2, 3 }


By performing the appropriate set intersections, Chow and Hennessy arrive
at their conservative solution.




Chaitin et al. don't really have a similar concept of live range (they use
the words, but in a different sense than Chow and Hennessy). Instead,
they compute interference directly from the control-flow graph and
appropriate data-flow information.


Conceptually, they compute live_out information for each basic block (that
is, the set of variables live at the output of each basic block). For our
example, these would look like


A = <expression 1> Block 1
B = A + <expression 2>
if (p)
{ B }
{
C = B + <expression 3> Block 2
D = C
} { C, D }


print C, D Block 3
return
{ }


The steps to building the interference graph go like this


init the graph G to empty
for each block B, do
init Live to equal B.live_out
for each instruction I in B (in reverse order) do
if I is a copy instruction (e.g. D := C) then
remove the source of the copy (i.e., C) from Live
endif
for each var V defined in I do
for each member M of Live do
add an interference between V and M to G
endfor
endfor
Live := Live - I.defs (remove all defined vars from Live)
Live := Live + I.refs (add all references vars to Live)
endfor
endfor


Note the special handling of copies. It's necessary because otherwise we
might think that C and D interfere even though they obviously have the
same value and may therefore be in the same register.






>we define a live range by using a two-dimensional
>representation (T, B). Where T is a global time stamp for each
>instruction in considering, and B is the basic block number that contains
>the instruction in considering. For example,
>
> +--------+
> | |
> | sr <- | Symbolic register sr is first defined in time Td in block B1.
> | |
> +--------+
> |
> V
> +--------+
> | |
> | <- sr | Symbolic register sr is last used in time Tu in block B2.
> | |
> +--------+
>
>The live range of symbolic register sr is defined as a set of pairs as
>follows:
>
> LR(sr) = {(T, B) | Td <= T <= Tu, B <= {B1, B2}} (simplified).
>
>Using this definition, we can exhibit the real life time of a symbolic
>register (Td --> Tu) that instruction number and basic block number cannot
>exhibit.


I guess I don't understand. It looks like your equation would give


sr = { (B1,Td) (B1,Td+1) ... (B1,Tu-1) (B1,Tu)
(B2,Td) (B2,Td+1) ... (B2,Tu-1) (B2,Tu) }


You'll want to remove all the pairs of (B1,Tn), Tn is not in B1.
Same for T's not in B2.


It looks like you're trying to improve the precision of Chow and Hennessy,
but you pay a large cost in the size of the sets. Additionally, you still
won't handle the case of copies. Why not use Chaitin's approach? It's
faster and more precise.


Preston Briggs
--

Return to the comp.compilers page.
Search the comp.compilers archives again.