[LLVMdev] Regalloc Refactoring

[David Greene]

Hi all,

As I work toward improving LLVM register allocation, I've
come across the need to do some refactoring.  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.

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.

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?

The problem is LiveIntervals::CreateNewLiveInterval.  This
member references LiveIntervals::rep, which as far as I can
tell makes use of temporary state (r2rMap_) generated
during the coalescing pass.  My reading indicates that
at final loop nest of LiveIntervals::runOnMachineFunction
replaces operand registers with using rep() which makes
use of r2rMap_.

So why does LiveIntervals::CreateNewLiveInterval use r2rMap_?
Actually, in the official sources, this member is not used by
anyone according to the Doxygen pages.  The only use I see is
in RegAllocGraphColoring.cpp which was posted to the mailing
list some time ago.

So I have several questions:

- Does this refactoring sound like a good idea?  Would a patch
   be accepted?

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

- Where do I send patches for approval?

- What is LiveIntervals::CreateNewLiveInterval used for?

- Why does LiveIntervals::CreateNewLiveInterval reference r2rMap_?

                                 -Dave