Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!mailrus!cornell!uw-beaver!teknowledge-vaxc!sri-unix!garth!smryan
From: smryan@garth.UUCP (Steven Ryan)
Newsgroups: comp.lang.c
Subject: Re: Important Question
Summary: The only stupid question is the one never asked.
Message-ID: <1105@garth.UUCP>
Date: 29 Jul 88 21:05:10 GMT
References: <16680@brl-adm.ARPA>
Reply-To: smryan@garth.UUCP (Steven Ryan)
Organization: INTERGRAPH (APD) -- Palo Alto, CA
Lines: 44

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