Path: utzoo!attcan!uunet!samsung!xylogics!merk!spdcc!esegue!compilers-sender From: hankd@ecn.purdue.edu (Hank Dietz) Newsgroups: comp.compilers Subject: Re: Reg. Alloc. - Graph Coloring Summary: There are other ways Keywords: code, optimize Message-ID: <9010191556.AA11673@dynamo.ecn.purdue.edu> Date: 19 Oct 90 15:56:00 GMT References: <9010181425.AA15324@cs.clemson.edu> Sender: compilers-sender@esegue.segue.boston.ma.us Reply-To: hankd@ecn.purdue.edu (Hank Dietz) Organization: Purdue University Engineering Computer Network Lines: 102 Approved: compilers@esegue.segue.boston.ma.us 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.