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
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
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/
Chris Lattner wrote:> 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 :).Will do. Right now I'm mostly just experimenting. We keep our own copy of the repository here so it's easy to back out changes.> 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).I'm definitely interested in improving coalescing and it sounds like this would fall under that work. Do you have references to papers that talk about the various algorithms?> 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 :)This is what I was trying to get at, but wasn't entirely clear about. Does the loop nest after the call to joinIntervals in LiveIntervals::runOnMachineFunction do this rewrite? Specifically: // perform a final pass over the instructions and compute spill // weights, coalesce virtual registers and remove identity moves. const LoopInfo &loopInfo = getAnalysis<LoopInfo>(); for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); mbbi != mbbe; ++mbbi) { [...] for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) { const MachineOperand &mop = mii->getOperand(i); if (mop.isRegister() && mop.getReg() && MRegisterInfo::isVirtualRegister(mop.getReg())) { // replace register with representative register unsigned reg = rep(mop.getReg()); mii->getOperand(i).setReg(reg); Doesn't that last statement actually do the rewrite? And how does this interact with the spill cost computation? I'm thinking separating out the spill cost computation is going to be a bit more work because right now it does some of its calculations in concert with this rewriting. But it seems workable.>> For the same reasons, I would like to eventually separate >> the spill cost calculation from the coalescing phase and> This seems fine in principle, but i'd like Evan to chime in when he's > back.Sure.> 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.Good work plan. That's how I'll submit the patches. -Dave