[comp.lang.c] Important Question

smryan@garth.UUCP (Steven Ryan) (07/30/88)

>The discussion about noalias is way over my head. Exactly what is 'aliasing',
>and why does it make such a difference?

Two or more paths to the same memory location.

Often, when a compiler generates a load or store, the memory address is a
constant plus some base address. In such cases the compiler can determine
if two loads or stores reference the exact same location. However if the
address is computed or indirect, it may be impossible to decide if the
references do or do not reference the same location.

Examples of potential aliassing are references to a global variable, say a,
and to a function, say f, parameter. If f was called as f(a), the location
address by a and the parameter would be the same.

Pointers can point to the same location.

The same array with two different subscripts, say a[i] and a[j], is an alias
if i==j.

Aliassing in and of itself is not a problem. The problem occurs when a compiler
tries to outsmart the programmer (aka optimisation). For example in
   a=b+c
   *d=e
   f=b+c
If *d cannot change the value of b or c, the both occurrences of b+c must yield
the exact same value. An optimiser will detect this and do something clever like
   temp=b+c
   a=temp
   *d=e
   f=temp
However if *d can change the value of b or c, the occurrences of b+c may be
different. The only way the *d=e can change b or c is if *d and b or *d and c
are aliasses.

Some languages prohibit accessing the same location through aliasses. This
is called the alias ban or the alias taboo. Fortran has an alias ban so that
formal parameters and global parameters cannot be aliasses. C has no such ban.
I do not know what the original noalias proposal was, but it was an attempt
to implement some form of the alias ban.

It is controversial because it is hard to come up with a runtime check
of the alias ban. This means any optimiser which depends on it is
on faith rather than demonstrable facts.

henry@utzoo.uucp (Henry Spencer) (08/02/88)

In article <1105@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes:
>I do not know what the original noalias proposal was, but it was an attempt
>to implement some form of the alias ban.
>
>It is controversial because it is hard to come up with a runtime check
>of the alias ban...

Well, not really.  At least, this wasn't the reason why putting it in C
was controversial.  The X3J11 noalias proposal was controversial because
almost nobody understood it well, because it had all-pervading effects, 
because it was an X3J11 invention rather than a codification of prior
art, and above all because it was introduced at the last minute, at a
time when the draft standard was theoretically approaching stability,
yet was perceived to be a significant change whose implications were not
fully understood.

C probably does need some way of doing something about the aliasing problem,
and a revised noalias might perhaps be the way to do it (although I have my
doubts), but it will have to wait for the next revision of the standard
(by which time, one hopes, there will be some actual C experience with
experimental features along those lines).
-- 
MSDOS is not dead, it just     |     Henry Spencer at U of Toronto Zoology
smells that way.               | uunet!mnetor!utzoo!henry henry@zoo.toronto.edu