Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!think.com!samsung!crackers!m2c!umvlsi!dime!dime.cs.umass.edu!moss From: moss@cs.umass.edu (Eliot Moss) Newsgroups: comp.arch Subject: Re: registerless architecture Message-ID: Date: 14 Nov 90 14:06:33 GMT References: <1990Nov12.145410.29035@cs.cmu.edu> <56084@brunix.UUCP> <1990Nov14.064225.14406@caliban.uucp> Sender: news@dime.cs.umass.edu Reply-To: moss@cs.umass.edu Organization: Dept of Comp and Info Sci, Univ of Mass (Amherst) Lines: 38 In-reply-to: ig@caliban.uucp's message of 13 Nov 90 17:47:46 GMT In article <1990Nov14.064225.14406@caliban.uucp> ig@caliban.uucp (Iain Bason) writes: I expect many languages other than C can also be made to allocate local variables on the stack. Lisp might be tough, and Smalltalk, but then they usually are on any architecture. LISP is actually pretty easy, I believe; Smalltalk is harder because its "stack frames" can be treated as objects (you can send messages to them!), they can be retained, etc. I suppose that LISPs supporting continuations also present problems, but that the stack can be used most of the time (see the paper in the most recent SIGPLAN conference on the subject). A compiler for a machine like this would obviously be different. For instance, I imagine "register" coloring would be difficult to do when the number of "registers" is variable. You have to take into account the fact that other routines may have data in the cache, and only allocate space if you think it will save this routine more time than it will cost other routines. On the contrary, register allocation via graph coloring would work reasonably well. Ordinary register allocation is trying to compensate for the difference in speed between registers and memory. If you eliminate registers and rely solely on some kind of cache, then register allocation is easy, and equivalent to having as many registers as you like. However, you *should* try to use as few memory locations as possible, and graph coloring is nicely suited to doing that. The nodes of the graph are the original collection of "variables" (including various computed expressions, etc.); when the graph is k-colorable, then these variables fit into k locations. The graph coloring algorithms used in compilers attempt to minimize the number of colors (i.e., locations) used. Hope this is reasonably clear .... -- J. Eliot B. Moss, Assistant Professor Department of Computer and Information Science Lederle Graduate Research Center University of Massachusetts Amherst, MA 01003 (413) 545-4206; Moss@cs.umass.edu