[LLVMdev] Regalloc Refactoring

[Chris Lattner]

On Tue, 17 Apr 2007, Roman Levenstein wrote:
>> The point is, the current code needs a lot of massaging. If you are
>> interested (after your first rounds of refactoring), please consider
>> a replacement for LiveInterval that keeps more accurate info that can
>> be plugged into the same existing allocator. The next step is to do
>> away with the r2rmap and rep().
>
> While implementing Wimmer's linear scan, which is heavily based on
> splitting of live intervals, I already extended LiveInterval to contain
> more detailed info about all def-use occurrences. I also implemented
> the functionality for splitting a live interval at any place.
> Additionally, the logic for selecting an "optimal" splitting position
> is done according to Wimmer's paper.

Excellent.

> Classes that I changed were: LiveInterval, LiveIntervalAnalysis,
> RegAllocLinearScan. To avoid conflicts with recent changes by Evan, I
> did the modifications on my copies of these classes which I named
> WimmerLiveInterval, WimmerLiveIntervalAnalysis,
> WimmerRegAllocLinearScan.

Would it be possible to merge those back into the main data structures? 
I'd much rather have the main liveintervals capture def/use information 
for the registers in the interval than have two forked data structures. 
This info can be used for many other things as well of course.

> I'm currently working on documenting the code and adding comments as
> well as some refactoring to make it cleaner. I plan to contribute the
> code rather soon, hopefully in May. In case of interest, I could post
> the code for my WimmerLiveInterval and WimmerLiveIntervalAnalysis
> classes even earlier.

Ok.

> Overall, this register allocator is rather functional already, at least
> for X86.

Great.

> The remaining issues with the allocator are:
> - Better coalescing decisions (here some insights from Fernando's paper
> and may be some others could help)
>
> - Reducing the number of moves between splitted parts of live
> intervals, when they are allocated to different physical registers.
>
> - Use of spill weights information and other heuristics for selection
> of  a live interval to spill - currently this is not taken into account
> at all, as in Wimmer's paper.
>
> - Handling of rematerialization
>
> - Better handling of memory folding - Wimmer's linear scan does it
> during register allocation time and only conditionally, and not in
> LiveIntervalAnalysis as it is done now. It distinguishes between SHOULD
> and MUST occurrences of the register in instructions. But current LLVM
> infrastructure for memory folding does it unconditionally. This
> requires probably some minor changes, e.g. providing different
> functions for asking if folding is potentially possible and for doing
> memory folding later, if the decision to do so is taken.

I'd suggest focusing on getting the basic pieces as solid as possible, and 
hopefully get it into CVS.  Once there, it can be improved and refined. 
Once your RA is better than the current one on average, and has similar or 
better compile-time requirements, we would make it the default.

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/