On Monday 09 July 2007 16:49, Reid Spencer wrote:> The only thing that comes to mind is that creating and running the > coalescer are separate operations so you might want to do the creation > of it in alias analysis style. Then, the allocator can a) determine if a > coalescer was created, b) obtain the coalescer that was created, if any, > and c) run it at the right time for the allocator's algorithm, or even > not at all.Ok, that sounds like a good plan. I'll brush up on how alias analysis works and work from there. -Dave
On Monday 09 July 2007 17:07, David Greene wrote:> On Monday 09 July 2007 16:49, Reid Spencer wrote: > > The only thing that comes to mind is that creating and running the > > coalescer are separate operations so you might want to do the creation > > of it in alias analysis style. Then, the allocator can a) determine if a > > coalescer was created, b) obtain the coalescer that was created, if any, > > and c) run it at the right time for the allocator's algorithm, or even > > not at all. > > 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. Does this sound like a reasonable plan? I want to keep the infrastructure as flexible as possible, to allow multiple implementations that can be chosen at run-time. But the interfaces need to be specific enough to be useful for more powerful algorithms. Discuss away! -Dave
>> 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