Linux and aliasing?

[mark@codesourcery.com]

>>>>> "Andi" == Andi Kleen <ak@muc.de> writes:

    Andi> Mark, even when you don't like it, would you as
    Andi> alias-expert-in-residence think that the basic strategy is
    Andi> workable?

I don't know what workable means.  

But, I would argue against your patch.  There are cases where a
pointer is cast to one type, and then cast back to another, and then
used.  These cases are conforming, and I think that Linus' proposal
will disable alias analysis in these cases.  That's bad.  Especially
since often these casts are to `void*' for the express purpose in
storing them in some kind of generic data structure.

Note that I made an alternate, more circumspect, proposal, which has
been ignored by both Linus and yourelf up until now, although there's
been so much traffic that one couldn't really expect anyone to keep up
with all of it:

  Put expressions of the form `*((foo*) (&x))' in alias set zero if
  x does not have type foo, or one of the types that is allowed
  to alias it.

This proposal only affects nonconforming code, and thus changing the
behavior of the compiler will not pessimize any conforming code.  It
is important that `x' be a variable, or a field of a variable, not an
arbitrary expression.  (For example, I don't think this should apply
to `*((foo*) (f()))' since that might be conforming.)  But, if
`x' is a variable, or of the form `x->y' or `x.'y' then we should be
OK (it's not legal to talk about `x->y' if `x' is not of the right
type), then we should be OK.

So, this proposal is, IMO, a workable extension of the standard
semantics.  I don't know if this covers all the cases in the kernel,
but it should be easier to change Linux to fit this model than the
strictly conforming one.

I'm also not sure if this is a good idea.  If we don't document this
behavior, we're not promising it to Linux.  So, we might break it
later.  If we *do* document it, then we have to promise to maintain
this behavior.  That's extra work for us; we have to be convinced
there's a good enough reason, and I'm not convinced yet.  The
questions are:

  o How badly does Linux need the extra cycles that might be squeezed
    out by this extra alias analysis?  How much faster will the 
    average Linux system go?

  o How hard would it be to fix the kernel?

  o How hard will it be to do this be to do in GCC?
  
  o What will the maintenance costs be?

  o What else could we all do with our time that would either improve
    Linux or GNU CC?

Your answers probably won't change my mind.  Not because I don't
respect them, but because I usually need to reach my own conclusions.
Hard numbers might change my mind, but I bet we don't have them.  We
can't know answers to the last four questions.  The first one could be
numerically estimated.  But, if you find a hot-spot in the kernel, you
could always make just enough of the kernel conforming to turn on
strict-aliasing there.

Question four is one of the most important, and historically has been
all too often ignored by GCC developers.  *Your* convenience now is
traded against *our* convenience later.  Today's easy hack may be
tomorrow's maintenance nightmare.  Overall, Linux and GCC are both
part of the GNU project (techincally, I know that Linux may not be,
but in practice we're all on the same side), so we have to do what's
best for the project *as a whole*.

Technically, I suspect that code transformations in the front-ends
(and yes, I'm planning some, like inlining on trees) will make doing
this analysis in the middle-end difficult; we could miss in both
directions, putting things in alias set zero when we should not, and
vice versa.

I think to make the semantics robust, this analysis would have to be
done in the front-ends.  Note that this is a *syntactic* thing, not a
*semantic* thing; it's the use of cast syntax in expressions of a
particular form.  In other words:

  inline foo* f(bar* x) { return (foo*) x; }
  *(f(&x)) /* Does not go in alias set zero, even if all 
              inlining is done.  */

So, in summary, I think:

  o It's not clear we want this behavior that badly.
  o A correct implementation will be difficult.
  o There will be maintenance headaches.

Furthermoe, I bet that by now, if all this energy had been spent
fixing the code in the kernel, you'd have made good headway on some of
the most prominent data structures.  Yes, this will be a tedious
chore, but it's an easy one: you enclose things in a union, compile,
see what doesn't, fix it, and go on.  

--
Mark Mitchell                   mark@codesourcery.com
CodeSourcery, LLC               http://www.codesourcery.com