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

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

Hi Evan,

Thanks a lot for your reply!

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

Hi Evan,

Thanks a lot for your reply!

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