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
> 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?Some suggestions: @InProceedings{Budimlic02, AUTHOR = {Zoran Budimlic and Keith D. Cooper and Timothy J. Harvey and Ken Kennedy and Timothy S. Oberg and Steven W. Reeves}, YEAR = "2002", TITLE = "Fast copy coalescing and live-range identification", BOOKTITLE = "PLDI", PAGES = "25-32", PUBLISHER = "ACM Press" } @InProceedings{Sreedhar99, AUTHOR = "Vugranam C. Sreedhar and Roy Dz-ching Ju and David M. Gillies and Vatsa Santhanam", YEAR = 1999, TITLE = "Translating out of Static Single Assignment Form", booktitle = {SAS}, publisher = {Springer-Verlag}, pages = {194-210} } And I have a quite fast algo that I believe is simpler than [Budimlic02] and I can share it with you :) Fernando
> > 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?Probably, you've seen this paper: http://gcc-ca.internet.bs/summit/2003/Graph%20Coloring%20Register%20Allocation.pdf The author depicts everything you could do with register allocation :) He touches different ways of coalescing, spilling, simplifying, splitting etc. Good place to get started. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070413/626cad1f/attachment.html>
> And I have a quite fast algo that I believe is simpler than [Budimlic02] > and I can share it with you :)Do you have a paper on this? I'd be interested in seeing it. -Tanya> > Fernando > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >
On Thu, 12 Apr 2007, Fernando Magno Quintao Pereira wrote:>> 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? > > Some suggestions: > > @InProceedings{Budimlic02, > AUTHOR = {Zoran Budimlic and Keith D. Cooper and Timothy J. Harvey > and Ken Kennedy and Timothy S. Oberg and Steven W. Reeves}, > YEAR = "2002", > TITLE = "Fast copy coalescing and live-range identification",Yep, this is the one I was thinking of. It is available online here: http://www.cs.rice.edu/~keith/LACSI/pldi02.pdf> And I have a quite fast algo that I believe is simpler than [Budimlic02] > and I can share it with you :)Can you briefly explain what it simplifies? -Chris -- http://nondot.org/sabre/ http://llvm.org/
On Thu, 12 Apr 2007, David Greene wrote:>> 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?I didn't think anything did, but...> 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?Hrm, yes, yes it appears so. Question is: doesn't this make the r2r map dead? Does something else fill it in? My memory is hazy here :). If it is dead, we should rip it out (actually, we should make it private to the coallescer function).> 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.Makes sense to me.>> 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.Great! -Chris -- http://nondot.org/sabre/ http://llvm.org/
Chris Lattner wrote:>> Doesn't that last statement actually do the rewrite? > > Hrm, yes, yes it appears so. Question is: doesn't this make the r2r map > dead? Does something else fill it in? My memory is hazy here :). If it > is dead, we should rip it out (actually, we should make it private to the > coallescer function).I'm trying an experiment to eliminate the r2r map altogether. Is there an efficient way to replace all references to a virtual register? That is, given a virtual register number, is there an easy way to get a list of all Instructions and/or Operands that reference it? I've been looking at the Use and Value classes and am wondering if there is something there I could use. -Dave
On Apr 12, 2007, at 2:37 PM, David Greene wrote:> 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.Yay!>> 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.Right. r2rmap is dead after coalescing. Chris' suggestion (colaescer owns it) makes sense.> >>> 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.While I agree spill cost computation does not belong in coalescer, I am not sure if it should go into a separate pass. To me, spill cost formulas should be register allocator specific. Perhaps it ought to belong to a generic register allocator class. Each derivative allocator is responsible for overriding it and calling it if it deems necessary. I am not too concerned about the potential increase in compile time. But please measure it nevertheless. :-) One of these days we will provide a reg -> uses mapping to help to mitigate the cost. Evan> >> 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 > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Evan Cheng wrote:> While I agree spill cost computation does not belong in coalescer, I > am not sure if it should go into a separate pass. To me, spill cost > formulas should be register allocator specific. Perhaps it ought to > belong to a generic register allocator class. Each derivative > allocator is responsible for overriding it and calling it if it deems > necessary.I'm actually fairly nervous about using inheritance this way. I know it's done like this all over LLVM but the Template Method pattern is often better. You don't _really_ need dynamic polymorphism for things like this. Static polymorphism is sufficient and it has the advantage of more flexibility for reuse (doesn't depend on a specific base class). For example, if I'm writing a register allocator, one way to do what you're saying without inheritance is to parameterize the allocator with a traits class and call into that for the custom routines: template<class RegallocTraits> class GCRegAlloc { void doAlloc() { ... RegallocTraits::computeSpillCost(someValue); ... }; }; An alternative to think about during these discussions. -Dave