Re: Linux and aliasing?

[Jamie Lokier <egcs@tantalophile.demon.co.uk>]

Jamie's suggestion de jour.

First let me cover the bases.

  Linus wants non-union (ie. non-ugly) casts to do the sensible thing.
  What that is isn't quite clear -- after thinking it through.
  If it's just aesthetics, I don't see why a macro wouldn't do ;-)

  Dave Miller notes that Linux does want to take advantage of full alias
  analysis, alongside code that does hacks to minimise loads and stores
  on current architectures.  I think Dave's trying to eat two cakes at
  once, but since I hack network hardware for profit, I know exactly
  where he's coming from.

  Other folks whose names (I must apologise) seem to have blended
  together in my head right now, have to write compilers.  Good
  compilers that produce the best possible code for standards-conforming
  programs.  And then degrade gracefully for non-conforming programs ;-)

  In particlar, a cast may be conforming, in which case the compiler
  should strive the generate the best allowed code (unless it's
  pathological).  A serious of non-conforming looking casts might be
  conforming too -- cast to void * and back was pointed out as
  conforming _and_ commonplace.

  Issues raised: 

  - Lots of legacy code uses casts, assuming nothing weird will happen.
  - Weird things now happen.

  - "non-conforming cast implies pointer may alias all" + "full flow
    analysis" got proposed.  No one likes it.  Bin.

  - "non-... all" + "*no* flow analysis" got proposed by Linus.  It's a
    simple special case, arguably syntactic.  But it has semantic warts:
       *(foo_t*) &bar = foo; 
    now means something different than:
       { foo_t* p = (foo_t*) &bar; *p = foo; }

    I submit that those two forms ought to be "trivially equivalent" --
    we think in terms of data flow when we write code.  We also think
    that way when we think about how compilers expand expressions, how
    common subexpressions are combined and so on.  A fine distinction
    would, IMO, be a major language misfeature and a cause of many
    subtle bugs in future.

  - "type attribute" got proposed by Linus too.  This I like.

    Type attribute means you can write:
       *(foo_t __alias*)(&bar) = foo;
    and the equivalent:
       { foo_t __alias* p = (foo_t __alias*) &bar; *p = foo; }

    See how the these _are_ trivially equivalent?
    The problem with this is that there are 2 times 10^30 ugly casts
    in the C cosmos that don't have such an attribute, of with 2 times
    10^29 are in Linux kernel.

Jamie's thought of the day
--------------------------

    It looks like the compiler could spot the dodgy casts, including
    some standard-conforming ones, based solely on the types of the
    casts (with attributes).  It could warn that you may be getting
    non-alias optimisations you weren't expecting.  The word access
    casts in the Linux kernel (and lots of other code) would be prime
    candidates.  Hard-core fortran coders have this warning switched
    off.  The compiler proceeds to optimise anyway (you were warned).

    But if you include a suitable type attribute, possible aliasing is
    implied and you don't get the warning.  You get sensible code out.

    There's an alternative attribute, for programs that mix and match,
    where possible aliasing is _not_ implied but it you still don't get
    the warning.  (A bit like __attribute__((unused)) is used solely to
    suppress warnings).

    Thus your thoroughly non-conforming kernel code starts with lots of
    warnings.  You add the __mayalias (or whatever) keyword into all the
    structure manipulation casts -- which the compiler helpfully pointed
    you to.  You add the __doesntalias keyword (is it the same as
    __restrict?) to all those places where you wrote conforming code and
    really do want it fully optimised.  So you get the best of all
    worlds and the compiler helps you get there.

    This way we get:

       - Full optimisation of conforming code.
       - Best optimisation of mostly-conforming code with dodgy casts.
       - No dubious alias flow analysis -- keeps things simple.
       - Code transformations such as rearranging intermediate
         values between expressions, extracting intermediates or merging
         then, continue to be valid transformations.  (IMO v.important).
       - The compiler tells us where to think about aliasing issues.
       - When all the warnings have gone away, then you _know_ it's safe to
         actually use the output of -fstrict-aliasing.
       - If your confident the code is conformant anyway, turn off
         the warning.

    Does this seem (a) implementable, (b) a good, incremental
    maintenance path for the kernel authors?

Enjoy,
-- Jamie