[LLVMdev] Easiest way to rewrite machine instructions when each live range of a LiveInterval may be assigned a different physical register

[Evan Cheng]

On Feb 27, 2009, at 7:20 AM, Roman Levenstein wrote:

> Hi,
>
> I'm working on the implementation of Extended Linear Scan register
> allocator as described by Sarkar & Bodik.
> One of the interesting features of their algorithm is the possibility
> to allocate different physical registers  to different live-ranges of
> the same LiveInterval. Of course, it may require some glue code to be
> inserted in cases, where different physical regs were assigned to
> live-ranges (of the same LiveInterval ) connected by a control-flow
> edge.
>
> I have almost implemented the algorithm for register assignments on a
> live-range basis. But now I need to rewrite the machine instructions
> and replace all virtual registers by assigned physical registers. I
> see different options for doing it:
>
> a) Normally, I'd use the spiller provided by the VirtRegMap class. But
> currently, it assumes that live register has only one physical
> register assigned to it.

Right.

>
>
> b) It could be possible to change LiveIntervalsAnalysis so that it
> creates a new LiveInterval for each live range. But this will probably
> have a negative impact on performance and also reduce coalescing
> possibilities.

Not to mention it will significantly increase memory usage.

>
>
> c) May be LiveIntervals could be split after register allocation, just
> before rewriting? How this could be easily done? May be
> PreAllocSplitting or LiveIntervals::addIntervalsForSpills could be
> used for this purpose by slightly changing them? Interesting point
> here is that such splits can occur only at the MBB borders, since each
> live-ranges may get its own, but only one physical register

Well, are you sure it's a register per live-range? It's possible to  
have multiple live ranges in the same MBB (two-address instruction  
etc.). Or perhaps it's one register per value number?

I would just add a quick pass at the end of your register allocator to  
renumber the virtual registers. VirtRegMap doesn't have the concept of  
liveinterval. Its states are mapping from virtual registers to  
physical registers.

Evan
>
>
> May be there are also some other alternatives?
>
> At the moment, I cannot easily decide which of these approaches is
> easier to implement. Therefore, I'd like to ask for your opinion about
> that.
>
> Thanks,
>  Roman
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev