Re: Coalescing register allocators

firth@sei.cmu.edu wrote:
> [My original figure deleted!]
>
> But that's the wrong representation! It corresponds to the statement
>
> a := if P then X else Y fi
>
> which is very different.


I would not call it the wrong representation. It is just another
representation. It is a representation that makes analysis and
transformation of programs easier, but which makes the code generation
problem harder. Since our main focus is on analysis and transformation,
this is the right representation for us.


> As you point out, this change complicates
> register allocation. Indeed, it leads to sub-optimal allocation,
> because it forces the assumption that 'a' must have the same binding
> on both paths, which in the more global context might not be true.


I believe the allocation problems can be overcome. I have a method to
assign the same virtual register to two nodes in our program
representation graph, if that will always improve on the program. I can
do this before the nodes (and the instructions corresponding to each node)
have been scheduled relative to each other. I do not think I will achieve
a sub-optimal allocation.


> More important, however, is that it forces the values of X and Y to
> a common subtype, before the assignment to a.


This is not true. It is only a question of inserting the right coercion
nodes in the graph before the gamma nodes. Those coercions are implicit
in the original program anyway, given the type information of your
example.


> I respectfully suggest that the problems you are encountering are symptoms
> of a design error in the internal representatiom, and the solution is to
> fix the error.
> [I tend to agree. It looks like you're assigning values to registers much
> too early. See the next message for the classic references on register
> allocation. -John]


Again, I would not call it a design error. Our different points of view are
most likely due to attempts to achieve different goals.


Regarding John's comment: I am actually not allocating registers at this
stage. I am doing register *assignment* (as the term is used in the red
dragon book). The register allocator may be able to perform the
coalescing, but we are also looking into methods to combine the scheduling
and register allocation problem. I want to perform as much coalescing as
possible at this early stage to make the job easier for the combined
scheduler/allocator.


preston@dawn.cs.rice.edu wrote:
> Chaitin's allocator gets rid of copies like those in your example --
> one of the great strengths of his approach (and weaknesses of
> competing approaches).


One weakness of Chaitin's approach is that it requires the instructions to
be scheduled, before it can be applied. We would like to combine the
scheduling and the register allocation phase. To make the job easier for
the combined scheduling/allocation phase, I want to perform register
*assignment* (as the term is used in the red dragon book) before that
phase, coalescing virtual register names whenever beneficial. The
approach I am taking works for unscheduled code. I was looking for
approaches to compare my own approach with, since my previous work has not
been in the area of compiler backends. My knowledge of that field is
therefore pretty limited.


> You should also look at my thesis for more details on how Chaitin's
> allocators work and are implemented as well as some improvements.


I have your thesis, and is the process of reading it. There are some very
interesting ideas in it, some of which we would like to try out in our
compiler.


> As a completely disinterested party, I wonder what other alternatives
> you were considering? And why?


I hope that I have answered the "why". The alternative is an approach of
my own. It is a related to the coalescing part of Chaitin's algorithm,
but as I said, for unscheduled code. I want to work out the final details
and do an implementation before writing it up.


Thanks for the references,


Bjarne Steensgaard
Microsoft Research
--

Return to the comp.compilers page.
Search the comp.compilers archives again.