CODEWITHSUNDEEP
design-patternstreecompiler-constructioncpu-registers
Jon Snow
Jon Snow

Reputation: 1

How does compiler know if a variable is spilled in code generation?

I am implementing a compiler using visitor pattern.

Here is the general algorithm I use.

regs gives the number of registers needed and top give the next free register.

generate(T,n) =
    if T is a leaf write ``load top(), T"
    if T is an internal node with children l and r then
    if regs(r) = 0 then { generate(l); write ``op top(), r" }
    else{
        generate(l,n)//Stored in Rn
        generate(r,n+1)//Stored in Rn+1
        write "op Rn, Rn+1" // rresult is stored in Rn
        push(R) }

But in the case where there's not enough registers, we need to spill variables. Suppose we use a greedy allocator that spills the last used register. It means that, when we generate(r) if there's no register left to store the result, we push Rn to the stack and store result in Rn and then retrieve spilled variable to compute the operation.

The complete schema become:

generate(l,n)//Stored in Rn
push Rn // push to stack
generate(r,n)//Stored in Rn 
mov Rn R0 // move
pop Rn // retrieve from stack
write ``op Rn, R0" // result is stored in Rn

What I tried is to modifty the function top to make it return a register if any available and push last register before returning it if no-one is available so when generating r children, we can save to stack if there's no space...

generate(l,top())//Stored in Rn
generate(r,top())//Spill if no space and store in Rn 
mov Rn R0 <--- my problem is here
pop Rn <--- my problem is here
write ``op Rn, R0" <---my problem here

But after generation of l and r, how does the operation knows that it needs to unspill* some variable (if it has to) ?

My question is :

Programmatically, how can I implement it in the compiler to make it oblivious to operation code.

Ideally ... code should look like:

generate(l,something())//Stored in Rn
generate(r,something())
write ``op somethingelse(), againsomethingelse()" <--- taking into account when space is available or not

Upvotes: 0

Views: 125

Answers (1)

Hadley Siqueira
Hadley Siqueira

Reputation: 163

The comments made by contificate are right. I'll just try to elaborate a little more.

First, I suggest you to read the following slides: https://web.cs.wpi.edu/~kal/courses/compilers/module6/RastislavBodikregalloc.PDF

On slide number 28, you can see how spilling works. You enter a loop: try to assign the registers by coloring. If it fails, spill a register and try to coloring again. Repeat until you're successful.

How do you track which variable are spilled or not? You don't. When you rewrite the code to accommodate the spilling, you get for free the tracking. On slide 28 it says

Before each operation that uses f, insert f := load fa

After each operation that defines f, insert store f, fa

So if in your program, you have a

t2 = t0 + t1
...
t10 = t2 + t3

And by whatever reason you can't assign a register for temporary t2, this means that its interference graph is overloaded with too many edges. You need to eliminate some of those edges. How do you do that? By making a variable alive for less time. How do you achieve that? By inserting loads and stores as soon as you need to use the variable. So the example I gave becomes:

t2 = t0 + t1
store t2    // immediately stores t2 after its use
...
// loads t2 just right before it is used
t2 = load t2
t10 = t2 + t3

This way t2 is going to be alive just for a brief moment of time. This will reduce the pressure in the interference graph which will allow a new round trying to assign registers to the temporaries in a graph with fewer interferences. If can't again find a colouring, choose another temporary, spill it (insert loads and stores where needed) and repeat.

This is isn't the only way to do it, but I believe it is one of the simplest.

Upvotes: 1

Related Questions