[LLVMdev] [RFC] WebAssembly Backend

[Matthias Braun]

If you don't have any register constraints SSA coloring boils down to: "Walk the program in dominance order and assign a fresh register to each def and release the register on a last use". However you need a way to implement register swaps for phi instructions afterwards although with infinite temp registers this is trivial.
I'd definitely recommend implementing a simple allocator from scratch, maybe reusing the liveness calculation, as you don't need all the tricks necessary to deal with register constraints, two-address instructions, precolored registers, spill code placement, ...

- Matthias

> On Jun 19, 2015, at 9:50 AM, Quentin Colombet <qcolombet at apple.com> wrote:
> 
>> 
>> On Jun 19, 2015, at 7:49 AM, Jakob Stoklund Olesen <stoklund at 2pi.dk <mailto:stoklund at 2pi.dk>> wrote:
>> 
>> 
>>> On Jun 18, 2015, at 6:47 AM, JF Bastien <jfb at google.com <mailto:jfb at google.com>> wrote:
>>> 
>>> We foresee having an infinite number of locals per function, but we plan to pre-color them so that locals whose lifetimes don't interfere can be merged. We can get clever and do this in an interesting order.
>> 
>> The NVPTX target does this with the existing register allocator by defining 800 physical registers of each type. It means you have to deal with unwanted spill code for those programs that exhaust the 800 registers.
>> 
>> The greedy register allocator doesn’t scale too well along that axis IMO. I think you get something like O(#vregs x #colors-used) behavior. It’s really designed to handle a small, fixed number of physical registers.
>> 
>> Matthias, Quentin: How well do the SSA-based register allocator algorithms work with infinite colors available?
> 
> The SSA-based register allocators work in linear time of the number of instructions.
> 
> Cheers,
> Q.
> 
>> 
>> Thanks,
>> /jakob

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150619/39d91bae/attachment.html>