[LLVMdev] Regalloc Refactoring

[Roman Levenstein]

Hi David,

--- David Greene <greened at obbligato.org> wrote:
> 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.

My experience with implementing Wimmer's version of the linear scan
also shows that register coalescing should be a separate pass, possibly
even selectable independently from the register allocation algorithm.
And for graph coloring register allocators coalescing is usually done
very differently, as you point out.
 
> 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?

I also agree that it is cleaner to have it in a separate source file in
a more modular fashion. If you don't want to increase the compile time,
may be some sort of plugin or policy driven approach approach can be
used? In this case, the pass over the program is still done by the
LiveIntervalAnalysis, but the logic for cost computation could be
implemented somewhere else and would be just called from the
LiveIntervalAnalysis. The kind of spill cost computation could be even
defined by a command-line option.
 
> 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.

r2rMap_ is used for selecting a representative register for a group of
coalesced registers. This is required during coalescing and for
rewriting of the code, when replacing the coalesced registers by
representative ones. This approach is used by many linear scan
implementations. But it is not required for many other kinds of
register allocations. For example, in Wimmer's version of linear scan
coalescing is done during the allocation and therefore the
implementation maintains its own mapping similar to r2rMap_.

In my opinion, current implementation of LiveIntervalAnalysis as well
some other related things is very tied to the specific flavor of the
linear scan register allocation algorithm and is not generic enough to
support many other kinds of register allocation. So, any work making it
more generic would open possibilities for easier addition of new
register allocators to LLVM. 
 
> So I have several questions:
> 
> - Does this refactoring sound like a good idea?  

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

Most likely - yes.
 
> - What is LiveIntervals::CreateNewLiveInterval used for?

I guess for splitting live intervals and similar things.
 
-Roman


       
____________________________________________________________________________________
We won't tell. Get more on shows you hate to love 
(and love to hate): Yahoo! TV's Guilty Pleasures list.
http://tv.yahoo.com/collections/265