[LLVMdev] Description Linear scan

[Alkis Evlogimenos ('Αλκης Ευλογημένος)]

On 10/11/06, Fernando Magno Quintao Pereira <fernando at cs.ucla.edu> wrote:
>
> Hey, guys,
>
>      could someone tell me some high level things about the version of
> linear scan that you use?
> 1) The heuristics for spilling seems to be:
>    (mop.isUse() + mop.isDef()) * pow(10.0F, (int)loopDepth
>    besides not spilling defs that are immediatly followed by uses, do you
> do any other thing, such as, taking into consideration the size of the
> interval when spilling?

AFAIR we don't take into account the length of the interval.

> 2) How do you avoid conflicts with machine registers already in the target
> code, such as the ones used to pass parameters in Power PC? Do you simply
> try to use the callee save registers as much as possible, and if there are
> conflicts, do you spill, or do you try some optimization?

The input code to the allocator has minimal intervals for those fixed
registers. For example x86 division returns both reminder and quotient
in EAX and EDX IIRC. The result is put in those register and the next
instructions are moves to the virtual registers that use those
results. Linear scan joins those intervals if possible so the move is
eliminated. This has the side effect of making that virtual register
allocated to EAX or EDX in this case (the one it was assigned to). If
the join is not possible this means that the specific machine register
cannot be used for the whole lifetime of that virtual register, so the
move stays and the virtual is allocated as usual. It can be allocated
to another register for its whole lifetime or spilled to the stack
like every other register.

I hope this answers your questions. Please correct me if I am wrong
since I haven't worked on LLVM for more than a year now.

Cheers,

-- 

Alkis