Xref: utzoo comp.arch:17123 comp.compilers:1040
Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!yale!mintaka!snorkelwacker!spdcc!esegue!compilers-sender
From: pur-ee!hankd@dynamo.ecn.purdue.edu (Hank Dietz)
Newsgroups: comp.arch,comp.compilers
Subject: Re: Register Allocation and Aliasing
Summary: It's been done -- they're called CRegs
Keywords: optimize, analysis
Message-ID: <1990Jul14.224339.14074@esegue.segue.boston.ma.us>
Date: 14 Jul 90 22:43:39 GMT
References: <1990Jul05.155937.13214@esegue.segue.boston.ma.us>
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: pur-ee!hankd@dynamo.ecn.purdue.edu (Hank Dietz)
Organization: Purdue University Engineering Computer Network
Lines: 43
Approved: compilers@esegue.segue.boston.ma.us

In article <1990Jul05.155937.13214@esegue.segue.boston.ma.us> aglew@oberon.crhc.uiuc.edu (Andy Glew) writes:
>How often are quantities that *might* be allocated to registers *not*
>allocated to registers, because of the remote *possibility* of
>aliasing via some circuitous pointers?
>
>    Hare brained idea: allocate quantities that *might* be aliased to
>registers anyway.  Provide a register to contain the true memory
>address of the aliased quantity, which causes a trap when the address
>is accessed (or automagically forwards to/from the register).

If you look back in the IEEE proceedings from Supercomputing '88, you'll see
a paper that I and Chi-Hung Chi did addressing exactly this issue (the title
is something Like "CRegs: A New Type of Memory for Accessing Arrays and
Pointers").  The CReg mechanism augments registers with address fields which
are used associatively to keep the register contents coherent...  we also
pointed-out that with proper compiler analysis, the associativity could be
limited to a rather small set size without ill effect (e.g., a set size of 4
rather than fully associative -- this keeps the speed of CRegs competitive
with that of ordinary registers).

>Evaluation framework:
...
>Unfortunately, I don't have any idea of what the parameters are like.

Some preliminary results on CRegs appear in the aforementioned paper.
The results were pretty good.  However, some of the most significant
benefits are not the obvious ones.  E.g., you don't need to do
explicit stores as often (ever?) -- you can even use a dirty bit and a
lazy store mechanism.  Likewise, you don't need as many loads, and you
certainly don't need to fetch as many addresses, which reduces the
INSTRUCTION FETCH bandwidth required.

					-hankd@ecn.purdue.edu

PS: Chi and I had actually tried to get this stuff patented back in
    1987, and it looked like we had some very nice claims, but Purdue
    University basically put it on hold until it had been over a year
    since public disclosure...  oh well.

PPS: We've also looked at using CRegs for instructions (vs. data).
-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus| world}!esegue.  Meta-mail to compilers-request@esegue.