pkolte@cs.clemson.edu (10/18/90)
We are studying register allocation techniques in our compiler course.
Are there any register allocation techniques that do not use some variation
of graph coloring ? Almost every paper on register allocation seems to
present enhancements or slight modifications to Chaitin's idea. Is anyone
trying (or has tried) anything different from the idea of COLORING
INTERFERENCE GRAPHS ? Thank you.
-Priyadarshan Kolte
Computer Science Dept. Clemson University. Clemson SC 29634
pkolte@cs.clemson.edu
[Before graph coloring, there was the traditional approach of treating the
registers more or less as a stack. -John]
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{ima | spdcc | world}!esegue. Meta-mail to compilers-request@esegue.preston@titan.rice.edu (Preston Briggs) (10/19/90)
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 ? Sure. There's a zillion ideas that work ok for allocation in a basic block. The Dragon Book is a good source, especially the bibliography. Allocation across many basic blocks is more difficult, interesting, and profitable. TN-Binding was developed at CMU as part of the PQCC project and was apparently used in several projects. The best description is in Bruce Leverett's thesis, called (approximately) Register Allocation in an Optimizing Compiler. Check the library. IBM had lots of ideas. I don't know how many have been widely published. Names like Beatty and Harbison (Harrison?) come to mind. Other work was done by Tan. Coloring is attractive in that it offers a nice abstraction, protecting you from a lot of the grundgy details of the job. Further, it offers a nice framework for handling most of these grundgy details when you finally must. The book isn't closed. I know of others who are looking for good alternatives (or perhaps have them). Some of them may publish. -- Preston Briggs looking for the great leap forward preston@titan.rice.edu -- Send compilers articles to compilers@esegue.segue.boston.ma.us {ima | spdcc | world}!esegue. Meta-mail to compilers-request@esegue.
hankd@ecn.purdue.edu (Hank Dietz) (10/19/90)
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.... -- Send compilers articles to compilers@esegue.segue.boston.ma.us {ima | spdcc | world}!esegue. Meta-mail to compilers-request@esegue.
preston@titan.rice.edu (Preston Briggs) (10/24/90)
In article <9010191556.AA11673@dynamo.ecn.purdue.edu> hankd@ecn.purdue.edu (Hank Dietz) writes: >[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 I think you've probably understated Chaitin's contribution. He (and others) built the first graph coloring register allocator. They also published the first 2 papers describing such a beast. Chaitin was listed first in an otherwise alphabetical author list and was the only author on the second paper. Register Allocation via Coloring Chaitin, Auslander, Chandra, Cocke, Hopkins, Markstein Computer Languages 6 (1981) pp. 47-57 Register Allocation and Spilling via Coloring Chaitin Proceedings of the Sigplan '82 Symposium on Compiler Construction pp. 98-105 I agree that the 2nd paper is mainly concerned with the node removal technique; but it also makes some points about implementation (that are unfortunately missed at times). However, the 1st paper makes many contributions: refinements leading to the ultimate notion of interference implementation concerns handling machine details and certainly others I've forgotten. Many implementors would benefit from a careful rereading of this paper. -- Preston Briggs preston@titan.rice.edu -- Send compilers articles to compilers@esegue.segue.boston.ma.us {ima | spdcc | world}!esegue. Meta-mail to compilers-request@esegue.
siritzky@apollo.hp.com (Brian Siritzky) (10/25/90)
In-reply-to: preston@titan.rice.edu's message of 23 Oct 90 22:18 GMT > I think you've probably understated Chaitin's contribution. He (and others) > built the first graph coloring register allocator. They also published the > first 2 papers describing such a beast. Chaitin was listed first in an > otherwise alphabetical author list and was the only author on the second > paper. I beg to differ: The first reference I have found applying graph coloring to the register allocation problem is in the book "On Programming -- An Interim Report on the SETL Project" by Jack Schwartz, 1975. Chaitin's paper is 1982. ^^^^ On page 485 Schwartz gives the graph coloring algorithm for register allocation, attributing ("The first algorithm due to J. Cocke ...") it to Cocke. I would guess that the algorithm he described is in an even earlier SETL Newsletter, but I don't have access to them to check. Brian Siritzky (508) 256-6600 x5445 Hewlett-Packard, Apollo Systems Division siritzky@apollo.hp.com -- Send compilers articles to compilers@esegue.segue.boston.ma.us {ima | spdcc | world}!esegue. Meta-mail to compilers-request@esegue.
preston@titan.rice.edu (Preston Briggs) (10/26/90)
I wrote: >> I think you've probably understated Chaitin's contribution. He (and others) >> built the first graph coloring register allocator. They also published the >> first 2 papers describing such a beast. Chaitin was listed first in an >> otherwise alphabetical author list and was the only author on the second >> paper. and In article <9010251440.AA25798@xuucp.ch.apollo.com> siritzky@apollo.hp.com (Brian Siritzky) writes: >The first reference I have found applying graph coloring to the register >allocation problem is in the book "On Programming -- An Interim Report on the >SETL Project" by Jack Schwartz, 1975. Chaitin's paper is 1982. >On page 485 Schwartz gives the graph coloring algorithm for register >allocation, attributing ("The first algorithm due to J. Cocke ...") it to >Cocke. The 1st Chaitin paper appeared in 1981. John Cocke was a coauthor. Ershov talked about finding opportunities for overlapping storage using graph coloring (and other NP-Complete problems) long ago, perhaps 1967. Janet Fabri did further work in this area. Cocke and Schwartz talked about it some. But Chaitin et al. built it. That means they worked out all the gory details that made it practical and interesting. I think that's a significant contribution. -- Preston Briggs preston@titan.rice.edu -- Send compilers articles to compilers@esegue.segue.boston.ma.us {ima | spdcc | world}!esegue. Meta-mail to compilers-request@esegue.
sasmkg@dev.sas.com (Mark Gass) (11/03/90)
I don't think that "graph coloring" is a register allocation algorithm.
It is really a graph-theoretic formulation of the register allocation
problem. The statement of the problem says nothing about how you will
solve it. Thus, all papers involving graph coloring are not simply
refinements to Chaitin's ideas.
The algorithm proposed in "Register Allocation by Priority Based Coloring"
by Chow and Hennessy (SIGPLAN 84 Compiler Construction Conf.) is completely
different from Chaitin's (most notably because it will split live ranges).
I have not seen any empirical studies comparing the two, but I believe
the Chow and Hennessy approach to be generally superior.
Mark Gass (SASMKG@DEV.SAS.COM)
SAS/C (370) Optimization and Code Generation
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{ima | spdcc | world}!esegue. Meta-mail to compilers-request@esegue.