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

[Roman Levenstein]

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.

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.

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

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