[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 28, 2009, at 12:10 AM, Roman Levenstein wrote:

> Hi Evan,
>
> Thanks a lot for your reply!
>
> 2009/2/27 Evan Cheng <evan.cheng at apple.com>:
>>
>> 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.
>
> Yes, true.
>
>>> 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?
>
> Hmm. Good question! In the original algorithm of Sarkar & Bodik they
> consider only a register per live-range.
> But on the other hand, they do not have a concept of a value-number.
> So, one possible refinement later could be to apply their ideas at the
> value-number level. I'm not sure though it will work out. Extended
> linear scan, just like LLVM's linear scan, only works with start and
> end points of live intervals and live ranges of those intervals. It
> does not explicitly take into account value numbers.
>
>> I would just add a quick pass at the end of your register allocator  
>> to
>> renumber the virtual registers.
>
> How do you mean that? Do you mean by renumbering that I just replace
> in machine instructions references to the original virtual register by
> references to the new virtual register, which corresponds to a given
> live range of the original register? And additionally I'd need to
> provide the mappings from those virtual regs to physical regs to the
> VirtRegMap. Is it correct a correct understanding?

Yes.

>
> (BTW, do I need to update any kill/dead markers, so that VirtRegMap
> can still work properly afterwards?)

Yes.

>
> Sounds rather easy to implement. Much easier than what I was  
> expecting!
>
>> VirtRegMap doesn't have the concept of
>> liveinterval. Its states are mapping from virtual registers to
>> physical registers.
>
> OK. If do it as you you suggest, will VirtRegMap be still able to use
> all its tricks to reuse (spilled) values hold on registers, etc?

It should, assuming all of the live ranges of the same live interval  
maps to the same spill stack slot.

Evan
>
> Thanks again for this advice!
>
> - Roman
>
>>> 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