[LLVMdev] Regalloc Refactoring

[David Greene]

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