Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!cs.utexas.edu!rice!titan.rice.edu!preston
From: preston@titan.rice.edu (Preston Briggs)
Newsgroups: comp.arch
Subject: Re: Register Allocation and Aliasing
Keywords: optimize, analysis
Message-ID: <9737@brazos.Rice.edu>
Date: 10 Jul 90 00:39:02 GMT
References: <1990Jul9.073203.3358@xavax.com>
Sender: root@rice.edu
Organization: Rice University, Houston
Lines: 89

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 adequate 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 a little more difficult.
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.

Phil Harbison writes:
>This sounds like an interesting idea.  What if we just added a tag
>to each register in the CPU.  The tag would store the address which
>the register represents.  A valid bit would be set if the tag was
>in use, and cleared for empty or scratch registers.  A dirty bit
>could be set when the register was not consistent with memory.  All
>load/store instructions would have to check the tags, so the tags
>would have to be fully associative.  Registers with the dirty bit
>set could be automatically written back when they were reused.

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?

(BTW, a similar post will appear someday on comp.compilers,
but it's been delayed somewhat.)

--
Preston Briggs				looking for the great leap forward
preston@titan.rice.edu