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
That's all implementation detail. My main point is spill weight computation is tied to the particular allocator / spiller combo so it should not be a separate pass. Evan On Apr 17, 2007, at 1:59 PM, David Greene wrote:> 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 > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
On Tue, 17 Apr 2007, David Greene wrote:> 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:This is a very detailed design point. I don't think it makes sense to talk about this until we are further along :). I agree that there are pros an cons, but I see these (static specialization vs dynamic dispatch) as two equivalent ways to solve the same problem, just with two different sets of trade-offs. With one you have code duplication (of an entire register allocator??) on the other hand you have dynamic dispatch overhead. In practice, the only way to determine the worth of one approach over the other is careful measurment, which you can't do until you have an implementation :) -Chris -- http://nondot.org/sabre/ http://llvm.org/
Chris Lattner wrote:> This is a very detailed design point. I don't think it makes sense > to talk about this until we are further along :).It's actually a fundamental design decision and therefore needs to be talked about up front. I understand where you're coming from but static polymorphism is the design I'd choose. It's important to get the sense of the community about this early on so I don't go do something that people object to.> I agree that there are pros an cons, but I see these (static > specialization vs dynamic dispatch) as two equivalent ways to solve > the same problem, just with two different sets of trade-offs. With > one you have code duplication (of an entire register allocator??) on > the other hand you have dynamic dispatch overhead.This isn't static specialization. It's the Template Method pattern. There's one generic algorithm that's parameterized through one or more traits classes. The generic algorithm calls into the traits classes to get varying behavior. There is no code duplication. Let's say I write two register allocators. One uses linear scan and the other uses graph coloring. Both need to compute spill weights. A single traits class can be reused as a parameter to both allocators, allowing the spill weight computation code to be shared. If someone else comes along later with a better spill weight algorithm, we can substitute that traits class when we parameterize the allocators. An example is the use of allocators in the standard library. The code for std::vector isn't duplicated. If I want a different allocation strategy I write a new allocator class and pass that as part of the vector type.> In practice, the only way to determine the worth of one approach over > the other is careful measurment, which you can't do until you have an > implementation :)The detailed part of the design is exactly what goes into the traits class(es), and yes, that is something that will be hashed out with experience. But choosing static vs. dynamic polymorphism has important software engineering implications. It's not a simple matter to convert from one to the other mid-stream. -Dave