johnhull2008@[EMAIL PROTECTED]
writes:
> I have a very basic question on register allocation, the answer to
> which I cannot find in any textbook....
>
> 1. add R0, R1, R2
> 2. add R3, R4, R5
> 3. add R6, R7, R8
> 4. add R9, R0, R10
>
> Suppose after constructing an interference graph, the register
> allocator decided R0 must be spilled, since it interferes with at
> least 5 registers.
> R0 - R4, R5, R7, R8, R10
Note that R0 also interferes with R3 and R6, because it is live where
they are defined. (The ones you list are those that are live where R0
is defined.)
> Here is the code after insertion of spill and fill codes:
> 1. add R0, R1, R2
> (1-spill.) store (loc), R0
> ...
> My question is, how does this code remove the interference between R0
> and the other registers? When instruction 1. completes and writes back
> to the register file, it still consumes a physical register (although
> just for one cycle), so there should be interferences remaining....
Great question. The answer is that spilling does not necessarily
remove interferences. And even if it does remove interferences, it
may not remove enough interferences to allow coloring to succeed -- at
least, that is the case in classic graph coloring register allocators
(of the Chaitin or Briggs style), which you seem to be assuming. In
the particular example you gave, the interferences with R3 and R6 are
removed, but not the ones you remarked upon. So, if spilling doesn't
necessarily make the graph colorable, then what? The answer is that
the process is iterated. If you look at Chaitin's or Brigg's
allocator, there is a loop back to the begining after inserting spill
code. In practice, shortening the live ranges removes enough
interferences (such as R3 and R6 here) that very few iterations around
this main loop are needed.
Some more recent register allocation work, such by Hack, has shown how
spilling can be decoupled from register allocation. This is
particularly the case with SSA form, which you mention. I find Hack's
dissertation to be very readable and am assigning sections from it to
my students, rather than relying on a textbook. I would suggest the
same to you; you can find it at
http://digbib.ubka.uni-karlsruhe.de/volltexte/do***ents/6532
|
