|Reg. Alloc. - Graph Coloring firstname.lastname@example.org (1990-10-18)|
|Re: Reg. Alloc. - Graph Coloring email@example.com (1990-10-18)|
|Re: Reg. Alloc. - Graph Coloring firstname.lastname@example.org (1990-10-19)|
|Re: Reg. Alloc. - Graph Coloring email@example.com (1990-10-23)|
|Re: Reg. Alloc. - Graph Coloring firstname.lastname@example.org (1990-10-25)|
|Re: Reg. Alloc. - Graph Coloring email@example.com (1990-10-26)|
|Re: Reg. Alloc. - Graph Coloring firstname.lastname@example.org (1990-11-02)|
|From:||email@example.com (Hank Dietz)|
|Summary:||There are other ways|
|Organization:||Purdue University Engineering Computer Network|
|Date:||Fri, 19 Oct 90 10:56:00 -0500|
In article <9010181425.AA15324@cs.clemson.edu> firstname.lastname@example.org writes:
>Are there any register allocation techniques that do not use some variation
>of graph coloring ?
>[Before graph coloring, there was the traditional approach of treating the
>registers more or less as a stack. -John]
 (A bad technique.) Number the locations on an imaginary stack
as registers and generate stack code with names changed. E.g.,
push a ld r0,a
push b ld r1,b
push c ld r2,c
add add r1,r1,r2
add add r0,r0,r1
 (A better technique.) Again, use an imaginary stack, but only
generate code as items are REMOVED from the stack. E.g.,
add ld r0,b; ld r1,c; add r0,r0,r1
add ld r1,a; add r0,r1,r0
 (A technique which is optimal for trees.) Build the
expression tree and then walk it in the order determined by
the Sethi-Ullman numbering, allocating registers as you go.
Unfortunately, this technique only deals with a single
expression tree at a time -- e.g., it can't be used with a DAG
resulting from removal of common subexpressions... although
there are sub-optimal versions of this to deal with DAGs.
 (A technique which is optimal for blocks.) Notice that  and
 are really more concerned with the order of evaluation than
with the register allocation per se; in studying the problem
of code scheduling for pipelines, Nisar and I created a very
efficient way of searching all possibly optimal orders. We
don't yet have a full paper out describing the technique, but
it is essentially the same as discussed in ICPP 1990, "Optimal
Code Scheduling for Multiple Pipeline Processors," vol. II,
pp. 61-64. Actually, it isn't always optimal because the
search must be artificially curtailed about 2% of the time.
 (A globally optimal technique.) Back in the 1960's, Karp et
al. proposed a technique for allocating index registers based
on finding the shortest path through a state transition
diagram representing all possible register assignments. This
technique was essentially killed in Kennedy's PhD thesis,
which gave some rather depressing observations about the
complexity. However, a few years ago, Chi and I came up with
a new angle on it that significantly reduces the complexity.
This is discussed in a paper we had at HICSS in 1988, "Register
Allocation for GaAs Computer Systems," vol. 1, pp. 266-274.
As in , the result is optimal only if the search is not
artificially truncated, which might not always be feasible.
 (A cheap approximate global technique.) The interference
graph coloring that is most often credited to Chaitin.
Actually, Chaitin's primary contribution appears to have been
the node-removal coloring scheme (optimal graph coloring isn't
feasible). A number of researchers have extended Chaitin's
technique to consider more information when making spill
decisions; Chi and I also tried using a random-walk instead of
node-removal for the coloring (see the paper noted in ).
There have also been various modifications to track more
complex side-effects or multiple classes of registers.
 (The easy way out.) Only put compiler-generated temporaries
in registers (as in  or ) and modify the language so
the user can do register allocation -- as in C.
The above is not, unfortunately, a complete list -- there was a lot done even
back in the 1950's (e.g., Stone's work), but most of that work centered on
evaluation ordering to improve register/function unit usage rather than on
global allocation of registers. There are also various more modern
techniques; e.g., for passing function parameters in registers such that no
register-to-register moves are needed, but that's really a fairly simple
optimization, not a complete register allocation policy.
I suppose that I should also explain that my involvement with register
allocation techniques grew out of working on compiler-managed cache, which is
a closely related (but more difficult) problem. This is also how Chi, who
was my PhD student, got involved. This may have biased the above
PS: It is *TRIVIAL* to allocate registers UNTIL YOU NEED TO SPILL.
Another dimension along which register allocation can be viewed
is how to decide which to spill (spill LRU, use a variation on
MIN, use heuristic costs, etc.) and what to spill (a variable,
a value, a compiler-generated temporary, etc.). These complexities
are why so many techniques focus on evaluation ordering to avoid
running out of registers....
Return to the
Search the comp.compilers archives again.