On Tuesday 17 July 2007 14:21, David Greene wrote:> > I don't care for a MachineFunctionPass that can be directly called. I > > think it's a very good idea to keep the coalescers independent from > > the allocators. If that's desired, we should enhance passmanager so > > each allocator can run some sub-passes as part of the allocation > > pass. > > I agree that this is a good long-term goal. Unfortunately, I don't have > the time resources to implement it right now. If someone else can take up > this as a sub-project, that would be great! I agree that several other > passes could make use of it.I've got something in the works that provides an interface for the coalescer to query an interference object. So the RegisterAllocator class no longer exists and coalescers don't directly depend on register allocators. As a bonus, the interference interface doesn't make any assumptions about the underlying representation but has the interfaces necessary to make equivalent queries to what a coalescer might ask an interference graph. As a proof of concept, I have an example of what the linear scan algorithm might provide. It's very inefficient and in practice linear scan probably won't ever interact with a coalescer that partners with the allocator but it serves to show that the interface can be met by something that doesn't use a graph. I've also implemented a graph-based realization using what I currently have, but as I said in another message, I'm not at liberty to release that publicly. It's pretty straightforward code, though. The RegisterCoalescer interface still exists because register allocators need to be able to invoke the coalescer, sometimes repeatedly. PassManager can't do that. The current SimpleRegisterCoalescer (which should really be named AggressiveRegisterCoalescer -- another patch on the way) inherits from both MachineFunctionPass and RegisterCoalescer. The former because it is run and managed by PassManager and the latter because it needs to belong to the RegisterAllocator AnalysisGroup, similar to how alias analysis works. We need a way for register allocators to ask PassManager for the coalescer object (even if the coalescer doesn't inherit from MachineFunctionPass) and this is the only way I know how to do it until someone takes on revamping how PassManager works and providing the capability of constructing hierarchies of PassManagers. I'm still working out getting things to build, etc. and will post a patch when I've got through all that. But does this sound like something closer to what we want? -Dave
Roman Levenstein
2007-Jul-18 06:14 UTC
[LLVMdev] [PATCH] Re: Pluggable Register Coalescers
Hi David, Just as an idea, you could try to use a coloring register allocator submitted by Bill Wendling some time ago on the mailing list? See this thread for more information http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-April/008489.html This allocator is already implemented using LLVM and could be probably useful for testing your new infrastructure and refactored interfaces. At least you would be able to do it for the linear scan and graph coloring allocators, which represent a major part of potentially possible allocators. And you don't need to contribute your own register allocation code in this case. -Roman --- "David A. Greene" <greened at obbligato.org> schrieb:> On Tuesday 17 July 2007 14:21, David Greene wrote: > > > > I don't care for a MachineFunctionPass that can be directly > called. I > > > think it's a very good idea to keep the coalescers independent > from > > > the allocators. If that's desired, we should enhance passmanager > so > > > each allocator can run some sub-passes as part of the allocation > > > pass. > > > > I agree that this is a good long-term goal. Unfortunately, I don't > have > > the time resources to implement it right now. If someone else can > take up > > this as a sub-project, that would be great! I agree that several > other > > passes could make use of it. > > I've got something in the works that provides an interface for the > coalescer > to query an interference object. So the RegisterAllocator class no > longer > exists and coalescers don't directly depend on register allocators. > As a > bonus, the interference interface doesn't make any assumptions about > the underlying representation but has the interfaces necessary to > make > equivalent queries to what a coalescer might ask an interference > graph. > > As a proof of concept, I have an example of what the linear scan > algorithm > might provide. It's very inefficient and in practice linear scan > probably > won't ever interact with a coalescer that partners with the allocator > but > it serves to show that the interface can be met by something that > doesn't > use a graph. > > I've also implemented a graph-based realization using what I > currently have, > but as I said in another message, I'm not at liberty to release that > publicly. > It's pretty straightforward code, though. > > The RegisterCoalescer interface still exists because register > allocators need > to be able to invoke the coalescer, sometimes repeatedly. > PassManager can't > do that. The current SimpleRegisterCoalescer (which should really be > named > AggressiveRegisterCoalescer -- another patch on the way) inherits > from both > MachineFunctionPass and RegisterCoalescer. The former because it is > run and > managed by PassManager and the latter because it needs to belong to > the > RegisterAllocator AnalysisGroup, similar to how alias analysis works. > We need > a way for register allocators to ask PassManager for the coalescer > object > (even if the coalescer doesn't inherit from MachineFunctionPass) and > this is > the only way I know how to do it until someone takes on revamping how > > PassManager works and providing the capability of constructing > hierarchies > of PassManagers. > > I'm still working out getting things to build, etc. and will post a > patch when > I've got through all that. But does this sound like something closer > to what > we want? > > -Dave > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >__________________________________ Alles was der Gesundheit und Entspannung dient. BE A BETTER MEDIZINMANN! www.yahoo.de/clever
On Wednesday 18 July 2007 01:14, Roman Levenstein wrote:> Just as an idea, you could try to use a coloring register allocator > submitted by Bill Wendling some time ago on the mailing list? > See this thread for more information > http://lists.cs.uiuc.edu/pipermail/llvmdev/2007-April/008489.htmlThis allocator isn't complete and is a bit bit-rotted at this point. But if someone wants to take it and run with it, I think it would be a very good idea. Unfortunately, my job doesn't provide me the time to write two allocators. :( Some other folks have been working on other algorithms, but I don't know what stage they're at. -Dave
On Jul 17, 2007, at 8:49 PM, David A. Greene wrote:> On Tuesday 17 July 2007 14:21, David Greene wrote: > >>> I don't care for a MachineFunctionPass that can be directly >>> called. I >>> think it's a very good idea to keep the coalescers independent from >>> the allocators. If that's desired, we should enhance passmanager so >>> each allocator can run some sub-passes as part of the allocation >>> pass. >> >> I agree that this is a good long-term goal. Unfortunately, I >> don't have >> the time resources to implement it right now. If someone else can >> take up >> this as a sub-project, that would be great! I agree that several >> other >> passes could make use of it. > > I've got something in the works that provides an interface for the > coalescer > to query an interference object. So the RegisterAllocator class no > longer > exists and coalescers don't directly depend on register > allocators. As a > bonus, the interference interface doesn't make any assumptions about > the underlying representation but has the interfaces necessary to make > equivalent queries to what a coalescer might ask an interference > graph.Great!> As a proof of concept, I have an example of what the linear scan > algorithm > might provide. It's very inefficient and in practice linear scan > probably > won't ever interact with a coalescer that partners with the > allocator but > it serves to show that the interface can be met by something that > doesn't > use a graph.Is this something you are going to contribute back to the repository?> > I've also implemented a graph-based realization using what I > currently have, > but as I said in another message, I'm not at liberty to release > that publicly. > It's pretty straightforward code, though.Ok.> The RegisterCoalescer interface still exists because register > allocators need > to be able to invoke the coalescer, sometimes repeatedly. > PassManager can't > do that. The current SimpleRegisterCoalescer (which should really > be named > AggressiveRegisterCoalescer -- another patch on the way) inherits > from both > MachineFunctionPass and RegisterCoalescer. The former because it > is run and > managed by PassManager and the latter because it needs to belong to > the > RegisterAllocator AnalysisGroup, similar to how alias analysis > works. We need > a way for register allocators to ask PassManager for the coalescer > object > (even if the coalescer doesn't inherit from MachineFunctionPass) > and this is > the only way I know how to do it until someone takes on revamping how > PassManager works and providing the capability of constructing > hierarchies > of PassManagers.Ok. I am willing to be flexible if it helps moving things along. Just make sure you pick decorative names for the entry points. For example, rather than invoke(), use something like CoalesceFunction(). And please try to limit the number of such entries.> > I'm still working out getting things to build, etc. and will post a > patch when > I've got through all that. But does this sound like something > closer to what > we want?Ok. Thanks! Evan> > -Dave > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
On Wednesday 18 July 2007 13:08, Evan Cheng wrote:> > As a proof of concept, I have an example of what the linear scan > > algorithm > > might provide. It's very inefficient and in practice linear scan > > probably > > won't ever interact with a coalescer that partners with the > > allocator but > > it serves to show that the interface can be met by something that > > doesn't > > use a graph. > > Is this something you are going to contribute back to the repository?Yes, that's the plan.> Ok. I am willing to be flexible if it helps moving things along. Just > make sure you pick decorative names for the entry points. For > example, rather than invoke(), use something like CoalesceFunction(). > And please try to limit the number of such entries.Agreed.> > I'm still working out getting things to build, etc. and will post a > > patch when > > I've got through all that. But does this sound like something > > closer to what > > we want? > > Ok. Thanks!Great. I'll keep working at it and post when ready. -Dave