Path: utzoo!attcan!uunet!snorkelwacker!spdcc!esegue!compilers-sender
From: preston@rice.edu (Preston Briggs)
Newsgroups: comp.compilers
Subject: Re: Register Allocation and Aliasing
Keywords: code, optimize, analysis
Message-ID: <1990Jul14.222431.13761@esegue.segue.boston.ma.us>
Date: 14 Jul 90 22:24:31 GMT
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: Preston Briggs <preston@rice.edu>
Organization: Compilers Central
Lines: 79
Approved: compilers@esegue.segue.boston.ma.us

Andy Glew writes:
>>    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).

And Ron Guilmette replied:
>Actually, this sounds like a marvelous idea to me!
...
>Having a machine that did this stuff would effectively render alias analysis
>(in compilers) "impotent and obsolete".

I disagree.  Alias analysis has many uses during optimization.
For example, during value numbering (with constant folding),
this example might arise:

	*p = 5;
	*q = -5;	-- does this change *p's value or not?
	if (*p > 0) {
	    ...
	}
	else {
	    ...
	}

With awsome alias analysis, we might be able to determine that p and q
don't point at the same location; therefore, we'd be able to eliminate
the test and the entire else clause.  With inadequate alias analysis
(or none at all), we must be conservative and emit code for the test.

It's easy to construct similar examples with common subexpression 
elimination, loop invariant code motion, &c.

The register allocation question is more difficult to dispose of with
a simple example.  But consider that many of the values kept
in registers are the result of common subexpression elimination or 
loop invariant code motion and you can get a hint of the problem.  
Here's a (very contrived) example:

	do {
	    *p = a[*q];
	    p++;
	} while (p < pp);

Now what we'd really like is to hold a[*q] in a register throughout the
loop, giving

	r = a[*q];
	do {
	    *p = r;
	    p++;
	} while (p < pp);

But what if p = q at some point during the loop?  Boom!
Note that we're not keeping *q in a register, so there's
no hint from the proposed trap hardware.

Basically, it seems as though we can't keep the results
of any expression that includes aliased elements in a register.
More to the point, we can't do any (?) optimization for
such expressions.

The whole scheme strikes me as "cache."  Hank Dietz has argued
(I believe) that the decision to keep a variable in cache or
register should be based on whether or not it is aliased.

For data breakpoints, perhaps there's an easy modification
of cache hardware?

-- 
Preston Briggs				looking for the great leap forward
preston@titan.rice.edu
-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus| world}!esegue.  Meta-mail to compilers-request@esegue.