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

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

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

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?

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

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?

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