Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!tut.cis.ohio-state.edu!unmvax!deimos.cis.ksu.edu!uxc!tank!mimsy!chris
From: chris@mimsy.UUCP (Chris Torek)
Newsgroups: comp.arch
Subject: Re: Register usage [was Re: 80486 vs. 68040 code size]
Message-ID: <17556@mimsy.UUCP>
Date: 17 May 89 04:52:21 GMT
References: <949@aber-cs.UUCP>
Distribution: eunet,world
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 30

In article <949@aber-cs.UUCP> pcg@aber-cs.UUCP (Piercarlo Grandi) writes:
>... I seem to remember that they used PCC and tuned its (bastardized)
>Sethi Ullman register allocator, which is both pretty good (even the
>[S]CC one was quite good) and with no assumptions at all.

(why is the `distribution' `eunet,world'?)

Anyway:  The Sethi-Ullman algorithm is intended to solve the problem
of computing the number of registers required to evaluate a single
expression.  That is, given any arbitrary chunk of code, one breaks
it into individual expressions, feeds that expression through a S-U
numberer, uses the result to decide what registers get what, when to
spill to memory, and so forth, generates one expression, then frees
up all the registers for the next.  None of the registers carry their
values from one expression to the next.

Modern compilers, on the other hand, usually take entire functions (or,
increasingly, take entire programs, typically in the `link' phase) and
allocate registers globally across the thing.  If a() calls b() and b()
calls c() and c() puts arr[17] in r33 and a() happens to need arr[17],
the compiler leaves the value in r33 by arranging for b() to use r32
and r34 so that when b() returns to a(), a() need not reload r33 (or
any other register).  PCC does not now and never has done this sort of
analysis; it forgets everything between one expression and the next.
(Typically a peephole optimiser attempts to make up for this later.)

In compiler circles, Sethi-Ullman numbers are considered rather passe' :-)
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris@mimsy.umd.edu	Path:	uunet!mimsy!chris