Re: Reg. Alloc. - Graph Coloring

In article <9010181425.AA15324@cs.clemson.edu> pkolte@cs.clemson.edu 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]


Techniques:


[1] (A bad technique.) Number the locations on an imaginary stack
as registers and generate stack code with names changed. E.g.,
"a+(b+c)" becomes:


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


[2] (A better technique.) Again, use an imaginary stack, but only
generate code as items are REMOVED from the stack. E.g.,
"a+(b+c)" becomes:


push a
push b
push c
add ld r0,b; ld r1,c; add r0,r0,r1
add ld r1,a; add r0,r1,r0


[3] (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.


[4] (A technique which is optimal for blocks.) Notice that [2] and
[3] 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.


[5] (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 [4], the result is optimal only if the search is not
artificially truncated, which might not always be feasible.


[6] (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 [5]).
There have also been various modifications to track more
complex side-effects or multiple classes of registers.


[7] (The easy way out.) Only put compiler-generated temporaries
in registers (as in [1] or [2]) 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
presentation. ;-)


-hankd@ecn.purdue.edu


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 comp.compilers page.
Search the comp.compilers archives again.