Re: Register Allocation and Aliasing

Preston Briggs <preston@rice.edu>
Sat, 14 Jul 90 22:24:31 GMT

          From comp.compilers

Related articles
Register Allocation and Aliasing aglew@oberon.crhc.uiuc.edu (1990-07-05)
Re: Register Allocation and Aliasing rfg@ncd.com (1990-07-06)
Re: Register Allocation and Aliasing preston@rice.edu (Preston Briggs) (1990-07-14)
Re: Register Allocation and Aliasing pur-ee!hankd@dynamo.ecn.purdue.edu (1990-07-14)
Re: Register Allocation and Aliasing torbenm@diku.dk (1990-07-14)
Re: Register Allocation and Aliasing mike@vlsivie.at (1990-07-15)
Re: Register Allocation and Aliasing aglew@dwarfs.crhc.uiuc.edu (1990-07-16)
Re: Register Allocation and Aliasing phorgan@cup.portal.com (Patrick Horgan) (1990-07-17)
Re: Register Allocation and Aliasing heggy@cs.pitt.edu (1990-07-17)
[4 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
From: Preston Briggs <preston@rice.edu>
Keywords: code, optimize, analysis
Organization: Compilers Central
Date: Sat, 14 Jul 90 22:24:31 GMT

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
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.