[LLVMdev] global register allocators and spill code

[Alkis Evlogimenos]

Hello LLVMers!

I recently added a generic machine rewriter/spiller that global register 
allocator writers may find useful.

The API provided is the free function:

void eliminateVirtRegs(MachineFunction&, const VirtRegMap&)

declared in lib/CodeGen/VirtRegMap.h and implemented in 
lib/CodeGen/VirtRegMap.cpp.

This function rewrites the machine code of MachineFunction to eliminate 
virtual registers and adds spill code as specified by VirtRegMap. VirtRegMap 
provides a mapping from virtual registers to physical registers and stack 
slots. This object is what a global register allocator must populate in order 
to use the generic spiller. Given a VirtRegMap, after the call to 
eliminateVirtRegs(), all virtual register references are eliminated and spill 
code is added to the instruction stream. Yes it is that simple :-)

Now, what should a VirtRegMap provide for this to work?

1) Each virtual register must (in general*) have a mapping to a physical 
register. The spiller will replace all references to this virtual register 
with the mapped physical register.

2) Each spilled virtual register must also have a mapping to a stack slot. The 
spiller will use the physical register mapping for loads/stores from/to this 
stack slot.

* I say in general because in architectures that support it, folding memory 
operands into instructions may eliminate all references to a virtual register 
(x86 for example). Obviously in that case a mapping to a physical register 
need not be provided.

Hopefully most global register allocator writers will find this useful with 
little or no modifications. Let me know if you have any questions, concerns 
or suggestions!

-- 

Alkis