Re: strict aliasing benefit examples

[kenner at vlsi1 dot ultra dot nyu dot edu (Richard Kenner)]

> > > I think there are 3 aliasing possibilities here:
> > > 1. known to alias
> > > 2. known to not alias
> > > 3. may alias
> >
> > Actually there is only 2, it may alias or not.
> 
> Actually, he's right (and both you and Richard are wrong).
> 
> The standard taxonomy of classifications for two memory accesses is:
> 
> Must-alias
> May-Alias
> Don't alias (or some variant name).
> 
> This is what you will find in literature, not "conflicts" or anything else.

I don't see a "right" or "wrong" here.  There's often a terminlogy issue with
GCC development in that it often is using concepts before there's accepted
standard definitions of things in the literature, so quite often the GCC term
has a similar but slightly different meaning.  "alias" is one of those case.
When you use the precise terms (as you did), there's no ambiguity, but when
used in the more generic form in the original question, there is potential
for confusion, which is why I used "conflicts", an even more generic term.

I also wouldn't want to argue for having either two or three states because
that's also a terminology issue: one could easily argue that once you find
that two references are the same, you consider them the same, so that the
"must" state excludes that case.  And many optimization "consumers" of the
information might not care between the remaining "must" case and the "might"
case.

But I think this discussion obscures the point some of use were trying to
make, which I think is something we all agree on.  Let me try to make it
again, going to even more generic terms to avoid getting trapped in
terminology issues:

Given two references, each to a byte, there are exactly three cases:

(1) We know the references are always to the same byte.
(2) We know that the references CANNOT be to the same byte.
(3) We can't prove either (1) or (2).

All non-obvious pairs of references start in state (3).  A major goal of the
compiler is moving as many pairs as possible into states (1) or (2).  Tools
to do this include type-based aliasing information and base+offset tracking.
Neither is completely effective and using the combination of the two is
better than either individually.

> There have been studies on what type of analysis is helpful.
> 
> See, e.g. http://portal.acm.org/citation.cfm?id=378806&coll=portal&dl=ACM

Although I find this a reasonably good methodology for evaluating the various
disambiguation methods, it suffers from the academic bias of assuming that
SPEC is good model of real-world application, though it's indeed probably the
best that can be done in such a setting.  The limitation for just C code is
much more significant an issue, especially since that's no longer the
predominant language nor is the style of those codes the predominant style.

Moreover, as far as the type-based aliasing is concerned, there isn't a large
discussion of that mechanism in terms of number of queries and the results
that are given as very sensitive to available optimization opportunities and
methods: that was work done in 2000 and the growth of additional optimization
techniques will affect the results, but it's unclear in what way.