[LLVMdev] Regalloc Refactoring

[Evan Cheng]

On Apr 18, 2007, at 9:20 AM, David Greene wrote:

> 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.

Template instantiation is static specialization. That, unfortunately,  
causes a lot of code duplication. It's not suitable for many classes.  
We are very concerned about overall footprint of LLVM.

Seriously, it's not important to get every design point decided  
before we proceed. We like incremental development. :-) See http:// 
llvm.org/docs/DeveloperPolicy.html#incremental

Evan

>
> 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
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev