I have a very basic question on register allocation, the answer to
which I cannot find in any textbook.
Suppose you have a code that consists of 4 instructions before
register allocation, and registers are all virtual, like in SSA
format. The first operand is the destination, the remaining two
operands are the sources. The architecture I have in mind is a
textbook pipelined RISC, like the one you find in H&P architecture
books.
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
Here is the code after insertion of spill and fill codes:
1. add R0, R1, R2
(1-spill.) store (loc), R0
2. add R3, R4, R5
3. add R6, R7, R8
(1-fill.) load R0, (loc)
4.add R9, R1, R10
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.
Since register allocation is a problem that has been studied for
decades, there must be something I am missing, but I can't find what
it is.
I would appreciate it very much if you could explain how this works.
Thank you for reading my post.
|
