Roman Levenstein
2009-Feb-27 15:20 UTC
[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
Evan Cheng
2009-Feb-27 18:44 UTC
[LLVMdev] Easiest way to rewrite machine instructions when each live range of a LiveInterval may be assigned a different physical register
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 registerWell, 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
Roman Levenstein
2009-Feb-28 08:10 UTC
[LLVMdev] Easiest way to rewrite machine instructions when each live range of a LiveInterval may be assigned a different physical register
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
Seemingly Similar Threads
- [LLVMdev] Easiest way to rewrite machine instructions when each live range of a LiveInterval may be assigned a different physical register
- [LLVMdev] Easiest way to rewrite machine instructions when each live range of a LiveInterval may be assigned a different physical register
- [LLVMdev] Spillers
- [LLVMdev] Possible bug in LiveIntervals (triggered on the XCore target)?
- [LLVMdev] NumLoads/NumStores for linearscan?