[LLVMdev] Regalloc Refactoring

[Chris Lattner]

On Thu, 12 Apr 2007, David Greene wrote:
> As I work toward improving LLVM register allocation, I've
> come across the need to do some refactoring.

cool.  :)  One request: Evan is currently out on vacation until Monday. 
This is an area that he is very interested in and will want to chime in 
on.  Please don't start anything drastic until he gets back :).

> Specifically, I would like to separate register coalescing from live 
> interval analysis.  Right now LiveIntervals handles both. The reason I 
> want to separate them is that other types of register allocators might 
> like to do coalescing differently (e.g. graph coloring does it by 
> examining the interference graph).  It would also allow different 
> heuristics and coalescing strategies.

Ok.  Another thing to ponder on: Our current phi elimination pass is the 
source of many of our coallescing-related issues.  Currently, each phi is 
lowered into one copy for the result and one copy for each input.  This is 
a *lot of copies*!  This is a problem both for coallescing (because it has 
to do so much, it is required to be very aggressive) and compile time (phi 
elim + coallescing is much slower than inserting the right copies to begin 
with).

If you're interested in this, I'd suggest taking a look at some of the 
smart phi elimination algorithms which use dominance properties (i.e., 
they don't require an interference graph).


> So far, this has been pretty easy.  I've created a new
> SimpleRegisterCoalescing pass and the member functions
> divide pretty cleanly between than and LiveIntervals.

Beyond that, one of the issues is the "r2rmap" and "rep" function.  As 
you've noticed, the coallescer basically uses these to avoid rewriting the 
code after it does coallescing.  For example, if r1024 is coallesced with 
r1026, it leaves all uses of both registers in the code, instead of 
rewriting uses of r1026 with r1024 and deleting all memory of r1026. This 
mades sense long ago, but now it is increasingly clear that this is a bad 
idea.  I would much rather have the coallescer be responsible for updating 
the code.  I would suggest doing this as a first step, it is clearly 
goodness :)


> For the same reasons, I would like to eventually separate
> the spill cost calculation from the coalescing phase and
> put the state somewhere besides the LiveInterval class but
> that's a project for later.  Doing this would increase
> compile time slightly as it would require an extra pass
> over the program.  Is this ok?

This seems fine in principle, but i'd like Evan to chime in when he's 
back.

> So I have several questions:
>
> - Does this refactoring sound like a good idea?  Would a patch
>   be accepted?

Yes, but try to break this down into small pieces: first step is to 
eliminate rep/r2rmap.  Second step is to split coallescer off.  PHI elim 
changes are independent of this, but would also be a separate project.

> - Is my plan to separate spill cost calculation from coalescing sound?

Seems fine to me, but I don't know enough :)

> - Where do I send patches for approval?

llvm-commits mailing list please.

-Chris

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