Hi all, Tanya and Reid's ideas are very good. I think we want to go towards pluggable register coalescers. That said, I don't think the longer term plan to stop short term progress. To me, it's totally acceptable for the allocator to directly call the coalescers at this point. I would love to see a smarter coalescer. That's something we can use today! :-) Thanks, Evan On Jul 11, 2007, at 10:41 AM, Tanya M. Lattner wrote:> >>> Ok, that sounds like a good plan. I'll brush up on how alias >>> analysis >>> works and work from there. >> >> I've been looking at this and it's become clear to me that we need >> some kind >> of abstract coalescing interface similar to what the AliasAnalysis >> class >> provides. I think we need the same thing for register allocators. >> >> LLVM's existing coalescer is very simple. It just goes and >> replaces every >> copy it can. In general, a coalescer will want to query the register >> allocator about which copies it should remove. For example, Briggs' >> conservative coalescer will not remove copies that could >> potentially cause >> spills. Only the register allocator has the information to make that >> decision. >> A coalescing interface needs to provide hooks for the register >> allocator to >> invoke it potentially multiple times with a potentially restricted >> scope. The >> register allocator needs to provide an interface for the coalescer >> to ask >> questions like, "is this copy here to split live ranges?" and, "will >> coalescing this copy potentially cause a spill?" >> >> AI think all this will require is new RegisterCoalescer and >> RegisterAllocator >> interface classes that can be multiply-inherited (with >> MachineFunctionPass) >> by the various implementations. >> >> It's not totally clear to me whether coalescers should even >> inherit from >> MachineFunctionPass as they are really invoked by the register >> allocator, >> not PassManager. But then again, I can imagine some coalescers >> (like the >> existing one) being independent enough to run on their own at any >> time. >> Opinions on this are welcome. > > I think the coalescer should be flexible enough to be run > independent of > the register allocator. For example, you may want to expose the copies > induced by transforming out of SSA to the scheduler. If the > scheduler is > run before register allocation, then you would want the coalescing to > happen before as well. > > -Tanya > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>> Ok, that sounds like a good plan. I'll brush up on how alias analysis >> works and work from there. > > I've been looking at this and it's become clear to me that we need some kind > of abstract coalescing interface similar to what the AliasAnalysis class > provides. I think we need the same thing for register allocators. > > LLVM's existing coalescer is very simple. It just goes and replaces every > copy it can. In general, a coalescer will want to query the register > allocator about which copies it should remove. For example, Briggs' > conservative coalescer will not remove copies that could potentially cause > spills. Only the register allocator has the information to make that > decision. > A coalescing interface needs to provide hooks for the register allocator to > invoke it potentially multiple times with a potentially restricted scope. The > register allocator needs to provide an interface for the coalescer to ask > questions like, "is this copy here to split live ranges?" and, "will > coalescing this copy potentially cause a spill?" > > AI think all this will require is new RegisterCoalescer and RegisterAllocator > interface classes that can be multiply-inherited (with MachineFunctionPass) > by the various implementations. > > It's not totally clear to me whether coalescers should even inherit from > MachineFunctionPass as they are really invoked by the register allocator, > not PassManager. But then again, I can imagine some coalescers (like the > existing one) being independent enough to run on their own at any time. > Opinions on this are welcome.I think the coalescer should be flexible enough to be run independent of the register allocator. For example, you may want to expose the copies induced by transforming out of SSA to the scheduler. If the scheduler is run before register allocation, then you would want the coalescing to happen before as well. -Tanya
On Wednesday 11 July 2007 12:41, Tanya M. Lattner wrote:> I think the coalescer should be flexible enough to be run independent of > the register allocator. For example, you may want to expose the copies > induced by transforming out of SSA to the scheduler. If the scheduler is > run before register allocation, then you would want the coalescing to > happen before as well.I agree that we want to allow for this possibility, but there are some coalescers that cannot run independent of the register allocator. So how do we handle both? If I as a user ask for a regalloc-dependent coalescer, what should it do if someone tries to run it as an independent pass? It could provide a fallback, perhaps invoking the existing coalescer, but that would cause coalescing the user might not want. It could do nothing and count on the register allocator to run it at some point, but not all register allocators will necessarily run a coalescing pass. I agree with Evan that we don't want to strangle short-term gain, but these are the kinds of questions we should keep in mind as we design interfaces. Interfaces can always change later, of course, but it's good to get them as right as possible initially. -Dave
On Jul 11, 2007, at 11:39 AM, David Greene wrote:> On Wednesday 11 July 2007 12:41, Tanya M. Lattner wrote: > >> I think the coalescer should be flexible enough to be run >> independent of >> the register allocator. For example, you may want to expose the >> copies >> induced by transforming out of SSA to the scheduler. If the >> scheduler is >> run before register allocation, then you would want the coalescing to >> happen before as well. > > I agree that we want to allow for this possibility, but there are some > coalescers that cannot run independent of the register allocator. > So how do we handle both? If I as a user ask for a regalloc-dependent > coalescer, what should it do if someone tries to run it as an > independent > pass?Could it be possible for there to be a harness type interface that would allow coalescers that support both modes to be hooked into the pass registration, and those that depend on the allocator not be registered as passes? -- Christopher Lamb -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070711/a431ebe3/attachment.html>