Re: compilers, register allocation, ... (James Larus)
14 Feb 90 15:02:02 GMT

          From comp.compilers

Related articles
compilers, register allocation, ... (Preston Briggs) (1990-02-11)
Re: compilers, register allocation, ... (1990-02-14)
| List of all articles for this month |

From: (James Larus)
Newsgroups: comp.compilers
Date: 14 Feb 90 15:02:02 GMT
References: <>
Organization: University of Wisconsin--Madison

Let me second Preston's sentiments about graph coloring register allocators.
The one that I wrote for SPUR Lisp is about 2,000 lines of commented Lisp
code. That also includes the control-flow analysis, which finds basic
blocks and the live ranges of variables. Frankly, compared to other parts
of a compiler, a graph-coloring allocator is a joy to write. There is a
nice conceptual model of what you are trying to accomplish. The only
difficult is choosing efficient data structures and dealing with the vaguries
of various machine instructions.

My feeling is that register windows are superior for languages like Lisp
in which interprocedural register allocation is impossible (not withstanding
Steenkiste and Hennesey's paper). But, Wall's global allocation is a better
strategy for machines with a sufficient number of registers (64?). It also
appears that a good conventional register allocator can make better use of
a smaller number of registers (32) than a half-hearted allocator can with
register windows.

This point was driven home when I recently examined Sun's compiler for SPARC
(which is a pretty good compiler) to find its register usage convention. As
far as I can tell (the philosophy of "Open systems" does not extend to the
details of register usage apparently), the compiler only uses 2 of the global
registers (apart from R0) as scratch temporaries. The other 5 global
registers are unused. This reduces the set of allocatable temporaries to
18 (8 local + 8 output + 2 global). The problem is that global registers don't
really fit into the C model of the world unless you do interprocedural
register allocation.


Post a followup to this message

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