Xref: utzoo comp.arch:16945 comp.compilers:1032
Path: utzoo!attcan!uunet!samsung!zaphod.mps.ohio-state.edu!usc!snorkelwacker!spdcc!ima!esegue!compilers-sender
From: aglew@oberon.crhc.uiuc.edu (Andy Glew)
Newsgroups: comp.arch,comp.compilers
Subject: Register Allocation and Aliasing
Keywords: optimize, analysis
Message-ID: <1990Jul05.155937.13214@esegue.segue.boston.ma.us>
Date: 5 Jul 90 15:59:37 GMT
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: aglew@oberon.crhc.uiuc.edu (Andy Glew)
Organization: University of Illinois, Computer Systems Group
Lines: 46
Approved: compilers@esegue.segue.boston.ma.us

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).  Not
only are aliasing problems avoided, but you've got a set of data
address breakpoint registers as well! (ie. this technique could be
experimentally evaluated on machines that have data address
breakpoints).

Evaluation framework:
    Na is the number of such data address breakpoint registers provided.
    V(1)..V(Na) are possibly aliased values placed in registers.

    Tr is the performance (CPI) assuming V(1)..V(Na) are all in registers,
	and no aliasing occurs.

    Tm is the performance (CPI) assuming V(1)..V(Na) are placed in 
	memory whenever there is a possibility of aliasing.

    Fa is the frequency of actual aliasing

    Ca is the cost of handling the aliasing, using the data address breakpoints
	(large in SW, less but still significant in HW) 

    Obviously, Tr = Tr( V(1)..V(Na) ) = Tr(Na), and so on.

Then we compare to Tr(1-Fa) + Tr(Fa)(1+Ca) to Tm for a particular Na.

Unfortunately, I don't have any idea of what the parameters are like.
I have the impression that Fa is low, and I can ballpark Ca. But what
is Tm/Tr? Given the amount of fuss (number of papers) about aliasing
in compilers, Tm/Tr would seem to be large, but I'm not sure.
Especially as Na is varied?


(Well, let's see if I've embarassed myself as much as I did in my last
posting, where I said that 24-10=4. ;-} )
--
Andy Glew, aglew@uiuc.edu
-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus| world}!esegue.  Meta-mail to compilers-request@esegue.